acceptodds
Under review as a conference paper at ICLR 2027

Unrolling Message-Passing to Understand Information Propagation in Graphs

Abstract

Message-passing neural networks (MPNNs) propagate information over graphs through repeated aggregation, yet the mechanisms governing signal preservation and degradation remain difficult to characterize exactly. We study this question through unrolled linear message-passing dynamics, where graph propagation is separated from nonlinear feature transformation. This separation makes it possible to derive exact node-to-node Jacobians and to measure two explicit propagation quantities: local sensitivity, which measures pairwise information transfer across the graph, and global sensitivity, which captures depth-induced collapse of information flow. Our analysis links propagation to graph topology and graph shift operators, identifying doubly stochastic learned operators as a principled way to prevent graph-side collapse in the deep regime. The theory also distinguishes topology-dependent degradation, related to over-squashing, from global vanishing caused by repeated nonlinear message passing. Guided by this analysis, we instantiate the theory in Bi-stream Unrolled Message Passing (BUMP), which combines a given graph operator with a learned doubly stochastic operator and fuses their representations after linear propagation. The framework applies to static and temporal graphs, and achieves strong empirical performance on long-range graph prediction, heterophilic node classification, and temporal graph forecasting.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Information Propagation, Graph Dynamical Systems

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_q5qUOpenReview ↗
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?

Reviewer_jejWOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies how information propagates in message-passing GNNs. It uses a linear recurrence over the graph, where all nonlinearities are moved outside the propagation step. Because the recurrence is linear, the authors can write down the node-to-node Jacobians exactly. They use these to define a local and a global sensitivity, and they derive bounds for two kinds of graph shift operators: the usual normalized adjacency, and a learned doubly stochastic operator.

Based on this analysis, they propose BUMP. BUMP has two linear streams, one over the given graph and one over a learned, Sinkhorn-normalized attention matrix, and it mixes the two with node-wise gating. Experiments cover synthetic long-range tasks, heterophilic node classification, LRGB and temporal forecasting.

Critical strengths
  1. The paper is well written and easy to follow. Splitting the Jacobian into a graph part and a channel part is a clean way to explain propagation.

  2. The time-varying case is a nice addition. Showing that products of doubly stochastic operators cannot collapse to zero, while products of normalized adjacencies can (the small counterexample in the appendix), is a useful observation.

  3. The experimental coverage is broad (static, temporal, node-level and graph-level tasks), and the single-stream model runs at roughly the speed of a GCN.

Critical weaknesses

My major concern is novelty. Almost all of the theory, the single-stream model, the fast implementation and several result tables already appear in "Message-Passing State-Space Models" (MP-SSM, NeurIPS 2025), and that paper is not cited. What is left is the learned doubly stochastic stream. The theory for it is fairly elementary, and in the experiments it adds little over the published single-stream model. I also find that the claims about generality (heterophily, topology, expressiveness) are not really tested. I flag up major comments below.

  1. Overlap with MP-SSM. The recurrence, the GSO, the block design, the static/temporal treatment and the fast diagonalized implementation are the same as in MP-SSM (Ceni et al., NeurIPS 2025). The same goes for most of the theory:
    • the exact Jacobian
    • the deep-regime approximation
    • the lower bounds on local and global sensitivity
    • the chain-of-cliques example
    • the "GCN vanishes 2^(-k/2) faster" result

Several appendix sections read almost word for word like the MP-SSM appendix. Some numbers are also identical. MP-SSM was published well before the deadline, so it has to be cited, compared against, and the new parts clearly separated from the old ones. In its current form, the paper presents published results as new contributions.

  1. The second stream does not add much. If we compare BUMP with the published MP-SSM numbers, most of the gains on the heterophilic and temporal benchmarks are within one standard deviation. Clear gains only show up on SSSP and Minesweeper. On Eccentricity the full model is actually worse than its own single-stream version (Table 16) and much less stable. Yet the ablation text says the bi-stream design improves results across all tasks.

On its own, the learned stream (BUMP-LF) is the weakest variant almost everywhere, sometimes clearly below simple baselines like SGC. So the component that the theory recommends does not seem to be what drives performance.

  1. The theory does not support the main message.

    • The learned doubly stochastic operator converges to the uniform matrix (1/n)11^T. This means every node ends up with the same influence from every other node, which is exactly over-smoothing. The paper calls this "non-collapsing", but it is collapse in rank, not in norm. The over-smoothing literature is not discussed at all (e.g. Oono & Suzuki 2020; Wu et al. 2023, who show that attention-based aggregation, including time-varying operators, still over-smooths).
    • All lower bounds are scaled by the norm of W^(t-s), and nothing in the model controls the spectrum of W. So the "non-vanishing" guarantee can still decay exponentially.
    • The 1/n bound is very weak on real graphs. On Questions (about 49k nodes) it is essentially zero.
    • The deep-regime results are approximations whose error depends on the spectral gap, and no rate is given. On bottleneck graphs, which are the motivating case, this regime needs many more steps than the at most 20 recurrences used in the experiments. So the bounds do not describe any of the trained models.
  2. The implementation does not match the theory.

    • Only five Sinkhorn iterations are used, so the learned operator is only approximately doubly stochastic, and the "spectral radius exactly 1" result does not hold exactly.
    • The hyperparameter table also lists a "top-k attention" option that is never explained. Top-k sparsification would break the positivity and symmetry assumptions used in the proofs.
    • The fast implementation in Appendix A needs a fixed, diagonalizable operator, so it does not apply to the learned, input-dependent (and time-varying) stream.
    • The runtimes reported are only for the single-stream model. Cost and memory for the full bi-stream model are not reported, and it is not said whether the dense or the low-rank attention was used on each dataset.
    • Finally, the learned operator of one block depends on the output of the previous block, so the "exact Jacobian" only holds inside a block.
  3. Missing related work and baselines.

    • Several closely related lines of work are missing:
      • Linear and state-space graph models: MP-SSM, GRAMA, and LRU, whose diagonal complex parameterization the fast implementation closely follows.
      • Models that combine the given graph with a learned or global one: IDGL, NodeFormer, SGFormer, Polynormer.
      • Polynomial spectral filters: in the static case, each block is a polynomial filter in A, and this connection and its known expressivity limits (GPR-GNN, BernNet, Wang & Zhang 2022) should be discussed.
    • On the heterophilic benchmarks, the baselines are outdated. Tuned classic GNNs (Luo et al., NeurIPS 2024) and Polynormer are on par with or better than BUMP on most of the five datasets. For example, Polynormer is better on Roman-empire, and a tuned GCN is better on Minesweeper and Questions. So the claim that BUMP "consistently matches or outperforms" the state of the art is too strong.
    • Results are averaged over 4 seeds, while the benchmark comes with 10 fixed splits. Is the comparison fair here?
  4. Generality is claimed but not tested.

    • There are no homophilous node classification datasets and no controlled heterophily sweep (e.g. a synthetic CSBM with varying homophily).
    • The fusion weights are never analyzed against node homophily, which would be the natural way to show the second stream adapts.
    • The chain-of-cliques worst case is constructed in theory but never tested.
    • The synthetic long-range graphs are small (25 to 35 nodes), and sensitivities are never measured on trained models.
    • Expressiveness is not discussed: the given-graph stream is bounded by 1-WL, and the learned stream only sees node features, not structure. There are no expressivity benchmarks.

Some typos and minor points:

  1. "Physiologically small" in Remark 3.8 sounds odd.
  2. Appendix D refers to "Lemma 3.4"; it should be Theorem 3.4.
  3. In the proof of Theorem 3.3, the one-step Jacobian is written with (A)_ji, but the theorem uses (A)_ij. This does not matter for a symmetric A, but it does for the time-varying product.
  4. In Eqs. (36) and (37) the exponent should be W^l, not W^i.
  5. The dimension d in Eqs. (5)-(7) is not defined.
  6. Theorem D.1 relies on an i.i.d. Bernoulli assumption and approximations, so it reads more like a heuristic estimate than a theorem.
  7. Table 6 has no standard deviations.
Questions for authors
  1. Please clarify the relation to MP-SSM. What exactly is new in this submission, in theory, method and results?
  2. How close to doubly stochastic is the learned operator after five Sinkhorn iterations? What is the "top-k attention" option, and how does it fit with the assumptions of Theorems 3.4, 3.5 and 3.9?
  3. What are the runtime and memory of the full bi-stream model? Which attention variant was used on which dataset?
  4. How do the fusion weights relate to node homophily? Can you add homophilous datasets and a controlled homophily sweep?
  5. How do you reconcile the convergence to the uniform matrix with over-smoothing?
  6. How does BUMP compare to tuned GCN/GAT/SAGE (Luo et al. 2024) and Polynormer under the same protocol?
Reviewer_WyvfOpenReview ↗
Rating
1
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Dear AC,

It appears that the margins of this paper have been manually adjusted.

  • Between line 90 and line 92 (Section 2, Methodology)
  • The bottom of page 6
  • The bottom of page 7 (Table 3)
  • Line 408 (Section 5, Related Works)
  • Line 471 (Section 6, Conclusions)

As far as I remember, this may be grounds for desk rejection.

I would appreciate it if you could look into this matter.

Best regards,

Critical strengths

To be updated if the issue is not critical

Critical weaknesses

To be updated if the issue is not critical

Questions for authors

To be updated if the issue is not critical

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.