- Rating
- 3
- Confidence
- 4
- Informativeness
- 3(+1)
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper extends two lines of research that explore the information propagation of graph neural networks (GNNs) to overcome the limitations of message passing neural networks (MPNNs). Combining the line of work on using wave-like equations on graphs, and enriching the graph structure to that of a sheaf structure, the paper explores the benefits of such a combination. The paper justifies the construction theoretically, and evaluates the proposed architecture mainly on synthetic benchmarks, but also on a real world benchmark in the appendix.
Critical strengths
- Combining wave equations and sheaves is a very natural next step in exploring alternative information propagation on graphs. It clearly builds on the literature and connects two research directions that have not been connected so far.
- The paper is very well written, the theory is well-justified, and the experiments are informative.
Critical weaknesses
- The theory is relatively straightforward extensions of the theory on sheaves and on wave equations on graphs.
- The experiments do not clearly identify and separate how combining the strength of both sheaves and waves distinguishes the architecture to sheaf heat diffusion and to graph wave equation. I would love to see a synthetic task where graph wave equation succeeds but sheaf heat equation fails, one task where graph wave equation fails but sheaf heat equation fails, and finally one task task where both graph wave equation and sheaf heat equation fails. The Table 2 suggests that sheaves do not work there, but it was introduced in BuNNs (Bamberger et. al) to argue that they can overcome oversquashing. Similarly, I would be curious to see the performance of BuNNs on the ECHO tasks.
- The authors did not cite the most relevant prior work: "Surfing on the Neural Sheaf" by Suk et. al (Neurips workshop 2022, link below). The reference is a very short workshop extended abstract and do not weaken the contributions of the current work. However, the work should be cited, and discussed in the main text.
Questions for authors
- The theory is nice but assumes identity weights and no nonlinearity. It would be nice of proposition 1 could be extended to at least include the learnable weights, and ideally also the nonlinearity (i.e. closed form Jacobian computation for one block in the continuous time setting).
- How did the time t parameter influence the synthetic task performance? Each synthetic task chose is intended to test for long-range propagation and/or oversquashing. The parameter that influences this seems to be the propagation time t. I would be curious to see an ablation of the performance of various t on each (or some) of the tasks.
- It would be helpful to see the empirical runtime of running a forward as a function of step size and propagation time t, and how it compares to wave-only equation.
- What I found interesting in the theory is that this architecture overcomes over-smoothing without requiring assumptions on the sheaf structure. Namely, Bodnar et al requires the sheaf to be path-independence for the long time result to hold, this property does not generally hold. BuNNs use flat vector bundles, which guarantee that this property holds. I wonder if path-dependence/independence has any impact in this theory here. Do you have any thoughts on this?
8 comments
Response 2/3
Q1. We thank the Reviewer for this suggestion, which has helped us improve the theoretical analysis and clarify its connection to the architecture. Following this suggestion, we have extended the theoretical discussion in Appendix A. Here, we summarize the new statements and findings.
First, Appendix A.4 makes the Jacobian interpretation of our source-to-target sensitivity precise. Lemma 3 establishes that this sensitivity is exactly the corresponding block of the Jacobian, describing how the target state changes under a perturbation of the source’s initial state. This provides the foundation for extending the analysis to additional components of the model. In Appendix A.5, we augment the analysis, as suggested by the Reviewer, to include multiple feature channels, learnable weights acting on stalk coordinates, mixing feature channels, and the learned velocity initialization . Proposition 3 then provides an exact expression for the continuous-time Jacobian of a propagation block and its expansion over graph walks. The result preserves the interpretation established in Proposition 1: source-to-target sensitivity is expressed through compositions of local transport operators along walks. The learned propagation weights enter these operators, while the input-dependent velocity initialization contributes an additional term to the Jacobian. This extension therefore retains the original analytical structure while incorporating additional architectural components.
Finally, Corollary 1 incorporates the nodewise MLPs applied between propagation blocks, which introduce nonlinear transformations in ONDA. Whenever these maps are differentiable, their Jacobians compose with the propagation Jacobians from Proposition 3 through the chain rule. Repeating this composition gives the Jacobian of the resulting sequence of propagation blocks and nonlinear maps. This result illustrates how the source-to-target sensitivity analysis extends to the whole learnable model.
Q2. We thank the reviewer for pointing out the importance of the propagation time in ONDA, which intuitively describes how long nodes were able to exchange information. We remark that, in the continuous formulation, it describes the elapsed time within a propagation block, while the discrete model approximates these dynamics through updates of step size , giving a propagation horizon of exactly . Increasing at fixed extends this horizon without changing the number of local aggregation steps, whereas increasing at fixed increases both. Since also determines the time discretization, we study these choices through two complementary performance ablations. On ECHO, we vary the step size while keeping the number of updates and all other hyperparameters fixed at the configuration selected for each task. Table 12 shows that increasing the step size from to reduces the mean test MAE from to on SSSP and from to on eccentricity. Diameter prediction exhibits a different pattern: the error decreases from at to at , then increases to at . Thus, extending the propagation horizon through a larger step size does not improve performance uniformly across tasks, showing that small variations in the step size have little impact on the performance, while small variations in the step size have little impact on the performance.
In Table 11, we complement the above comparison with a controlled experiment on the Barbell task with nodes in each clique. We vary the step size and the number of updates . Results are means over five training seeds at validation-selected checkpoints, with forcing and dissipation disabled. The comparison across step sizes illustrates that must be considered together with . For , step sizes , and give horizons of , and , with MSEs , and , respectively.The substantial variation in error across these settings highlights the importance of choosing the step size and the number of propagation steps jointly, rather than attributing performance to alone. For your convenience we report Table 11 below.
| Step size / updates | 6 | 8 | 10 | 12 | 14 | 16 |
|---|---|---|---|---|---|---|
| 1.0 | 0.3280 | 0.1182 | 0.0724 | 0.0445 | 0.0344 | 0.0293 |
| 0.5 | 0.9116 | 0.7019 | 0.3454 | 0.2161 | 0.1797 | 0.1383 |
| 0.2 | 0.9478 | 0.9429 | 0.9397 | 0.9202 | 0.9149 | 0.8775 |
Response 3/3
Q3. We thank the Reviewer for this helpful suggestion to extend the computational evaluation. Table 9 (in the original manuscript, now Table 13) already provides a comparison between ONDA and the wave-based SONAR model, including forward inference latency. Both models use approximately 100k trainable parameters, four blocks, and 12 propagation updates per block.
For a fixed graph and model configuration, the number of updates determines the propagation cost, since it determines how many times the propagation operator is applied. As discussed in Q2, together with the step size , it determines the horizon . Changing while keeping fixed changes this horizon without changing the number of operations, i.e., the computational cost of a forward/backward pass. Moreover, plays the role of the number of local aggregation steps, providing a natural basis for comparison with the message-passing depth of other architectures.
To complement the existing comparison, we report additional inference-time measurements on ogbn-arxiv, using a single block with increasing numbers of updates () for ONDA, SONAR, and corresponding numbers of message-passing layers for NSD and CSNN. The results are reported in Table 14 in Appendix D and can also be found below for your convenience. Here we clearly observe that, although runtime differs based on the type of restriction maps, ONDA scales graciously while increasing the iterations, and at , every ONDA variant uses less training time and memory than its corresponding NSD variant and CSNN.
computational costs on ogbn-arxiv wrt
| Model | L=1 Mem. | L=1 Train | L=2 Mem. | L=2 Train | L=3 Mem. | L=3 Train | L=5 Mem. | L=5 Train | L=8 Mem. | L=8 Train |
|---|---|---|---|---|---|---|---|---|---|---|
| SONAR | 2193.9 | 23.6 | 2661.3 | 32.6 | 3127.0 | 42.1 | 4061.5 | 59.8 | 5461.2 | 86.4 |
| Diag-NSD | 3511.7 | 66.6 | 5689.0 | 131.4 | 7866.2 | 196.9 | 12218.9 | 325.7 | 18750.2 | 535.7 |
| Ortho-NSD | 4136.9 | 124.1 | 6859.3 | 257.2 | 9580.3 | 376.0 | 15025.1 | 626.0 | 23191.8 | 985.0 |
| General-NSD | 4693.2 | 213.0 | 8226.1 | 425.6 | 11759.6 | 640.7 | 18827.2 | 1068.2 | 29427.6 | 1731.6 |
| CSNN | 2478.2 | 74.7 | 3738.7 | 148.2 | 4998.4 | 222.7 | 7517.7 | 370.3 | 11295.2 | 591.5 |
| Diag-ONDA | 3512.4 | 67.9 | 4139.7 | 90.2 | 4767.1 | 112.4 | 6021.8 | 158.5 | 7903.8 | 225.3 |
| Ortho-ONDA | 3995.6 | 125.7 | 4423.0 | 161.2 | 4788.3 | 197.4 | 5479.0 | 269.8 | 6513.0 | 378.1 |
| General-ONDA | 4693.2 | 216.6 | 5320.4 | 266.4 | 5948.5 | 317.7 | 7203.3 | 420.9 | 9084.7 | 575.7 |
Q4. We thank the Reviewer for this insightful observation. As discussed in [1], over-smoothing is closely related to contractive propagation dynamics and vanishing gradients. ONDA addresses this through non-dissipative oscillatory dynamics, which prevent the systematic attenuation of information, as established in Section 4. Therefore, as correctly observed by the Reviewer, ONDA avoids the over-smoothing mechanism associated with dissipative propagation. In diffusion-based SNNs, path independence plays an important role because the long-time behavior is determined by the kernel of the sheaf Laplacian, whose dimension can be related to the underlying transport structure (see for instance Bodnar et al., 2022, Lemma 6). In contrast, ONDA's non-decaying behavior does not rely on the existence of a nontrivial kernel, since its oscillatory dynamics preserve contributions from positive-eigenvalue modes, as becomes clear from Proposition 2, which shows that the positive-eigenvalue contributions do not decay. Thus, persistence of a nontrivial source-to-target sensitivity does not rely on a nontrivial harmonic space or on path-independent transport, and can hold even when the harmonic space is trivial This is a fundamental distinction between ONDA and dissipative models. Path dependence can still influence the spectral structure and the resulting information propagation patterns, but it does not alter the non-decaying nature of nonzero source-to-target sensitivities established in Section 4.
We hope these clarifications, revisions and additional experiments have addressed the Reviewer’s concerns.
Response 1/3
We thank the Reviewer for their thoughtful feedback and for recognizing the clarity of the presentation, the informativeness of our experiments, and the theoretical motivations of our work. We further appreciate that the reviewer found our work to be closing the gap between two previously unconnected fields and that our architecture overcomes over-smoothing without requiring assumptions on the sheaf structure. We address the Reviewer’s concerns below.
W1. We thank the Reviewer for the comment and we would like to clarify the nature of our contribution, which we believe is not a straightforward extension. This perspective was also recognized by Reviewer PGhW, who described our contribution as “a potentially useful research direction” and noted that our work “can help researchers to follow a similar path, modifying how nodes exchange information within sheaf-based architectures”.
Specifically, extending the wave equation from graphs to the sheaf setting requires introducing a different class of operators and mathematical tools, leading to substantially different and more involved theoretical development than in conventional GNNs. Our contribution therefore requires characterizing how matrix-valued transport interacts with oscillatory dynamics and influences long-range information propagation. We think the seemingly “straightforward extension” instead reflects our efforts to establish a clear and intuitive connection between the mathematical frameworks of sheaf theory and wave equations, despite the underlying technical complexity. In the paper, we complement this formulation with an extensive analysis of source-to-target sensitivity, which, to the best of our knowledge, has not previously been developed in the sheaf setting. Specifically, we investigate how matrix-valued transport shapes information propagation, with particular attention to the relationship between continuous-time dynamics and the discrete updates underlying ONDA. During the rebuttal phase, we have further strengthened this analysis through the Jacobian interpretation (lines 987-1025), extensions incorporating learnable weights, learned velocity initialization and nonlinear transformations between blocks (lines 1068-1133), and additional sensitivity bounds (lines 1350-1472). These developments are presented in the revised theoretical appendix and are also discussed in our responses below.
W2. We thank the reviewer for the raised comment, which allows us to further discuss and show the benefits of the combination of sheaves and the wave equation, compared to their use in isolation. To show the importance of both components, we consider the following three settings to illustrate the differences in behavior between NSD (isolating the sheaf component), SONAR (isolating the wave component on a non-sheaf architecture), and ONDA (combining both):