- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies information propagation in GNNs using linear message-passing recurrences. This allows the authors to derive exact state-to-state Jacobians and separate graph propagation from feature transformation. They propose BUMP, which combines propagation over the given graph and a learned doubly stochastic graph, followed by nonlinear fusion. Experiments cover graph property prediction, heterophilic node classification, and temporal forecasting.
Critical strengths
The paper addresses an important problem and provides an interpretable framework. Separating graph propagation from feature transformation makes it possible to analyse their contributions explicitly. The distinction between fixed and time-varying graph operators is particularly useful, since stability under repeated application of one operator does not automatically extend to products of changing operators.
The empirical evaluation is broad and promising. The authors evaluate the method on 16 tasks across several settings, with particularly strong reported results on graph property prediction and temporal forecasting. Comparisons with simple propagation methods such as SGC and APPNP, together with component ablations, help assess whether the additional architectural choices are useful.
Critical weaknesses
The lower bound in Theorem 3.5 is incorrect as stated. The proof turns an asymptotic approximation into an exact inequality. For example, take W = I and a symmetric doubly stochastic matrix A with rows (3/4, 1/4) and (1/4, 3/4). The minimum entry of A^k is (1 − 2^(−k))/2, which is below the claimed bound 1/n = 1/2 at every finite depth. Equation (14) therefore needs an error term or a limiting formulation.
Theorem D.1 is not established by the provided proof. The ReLU derivative is evaluated at one neighbour’s contribution rather than the full preactivation. The full node-to-node Jacobian also involves a sum over walks, including residual paths. Furthermore, the argument uses the same contraction factors for masked and unmasked trajectories without justification. These issues undermine the claimed 2^(−k/2) comparison with nonlinear GCNs.
The non-vanishing claims go beyond what the analysis proves. The lower bound in Theorem 3.9 still depends on ||W^k||, which can vanish, for example when W = 0.5I. The results concern linear propagation within a block and do not establish non-vanishing gradients through nonlinear fusion and stacked blocks. Appendix B also uses only five Sinkhorn iterations, whereas the guarantees assume exact double stochasticity. The paper should distinguish these guarantees from properties of the implemented model.
The experiments do not clearly establish the benefit of the central normalization choice. There is no controlled comparison between learned streams using row normalization and doubly stochastic normalization. The given-graph stream already accounts for much of the improvement and outperforms full BUMP on eccentricity in Table 16. Moreover, the runtime comparison in Table 15 evaluates only BUMP-GF, leaving the practical overhead of the complete architecture unclear.
Questions for authors
Can you provide a corrected finite-depth version of Theorem 3.5 and a rigorous revision of Theorem D.1 addressing the issues above?
What constraints, if any, prevent the learned feature transformations from producing vanishing or exploding sensitivities? How do the guarantees extend to nonlinear fusion, stacked blocks, and approximate Sinkhorn normalization?
Can you compare row-normalized and doubly stochastic learned streams under the same architecture and training setup, and report runtime and memory consumption for full BUMP?