PaperlayerView exact revision on arXiv

Source-linked AI summary

Oscillatory Neural Dynamics over Sheaves

Jan-Willem Van Looy, Alessandro Trenta, Alessio Gravina, Alessio Borgi, Ferdinando Zanchetta, Pietro Liò, Davide Bacciu, Rita Fioresi

arXiv:2610.10018v1cs.LG

TL;DR

Deeper graph propagation does not guarantee that distant nodes effectively influence one another, and expressive sheaf transport alone does not solve that communication challenge. ONDA couples learned matrix-valued transport with second-order oscillatory dynamics; the paper reports persistent cross-influence and strong performance across several graph-learning tasks.

  • Problem

    Increasing propagation depth does not guarantee effective influence between distant nodes, while matrix-valued sheaf transport alone also leaves long-range communication unresolved.

    Source: §1 · p. 1, §3.2 · p. 4

  • Method

    ONDA combines learned sheaf transport, which transforms information between neighboring stalks, with second-order oscillatory dynamics that govern its propagation.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    ONDA’s analysis shows connected nodes can influence one another regardless of distance, and experiments report strong performance across long-range propagation, bottleneck transfer, and heterophilic tasks.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The reported findings support coupling persistent wave propagation with expressive local sheaf geometry for graph learning across the evaluated tasks.

    Source: §1 · p. 2, §6 · p. 9

    The theoretical response result assumes fixed restriction maps, identity weights, a single feature channel, and h^2λmax(LF) < 4.

    Source: §4 · pp. 5, 7

Abstract

from arXiv · show

Effective long-range propagation remains a central challenge in graph neural networks, as increasing a model's propagation depth does not guarantee that distant nodes effectively influence each other. Sheaf neural networks enrich graph propagation through matrix-valued transport between stalks; still, this expressivity alone does not automatically imply effective long-range communication. We introduce ONDA, a long-range graph learning framework based on operator-valued information waves. Stalk-valued representations evolve through second-order dynamics governed by learned sheaf transport operators, combining wave-like propagation with expressive local geometry. We characterize long-range influence through a stalk-wise sensitivity analysis and show that the cross-influence never vanishes. Across long-range propagation, severe graph bottlenecks, graph transfer, and heterophilic benchmarks, ONDA consistently improves over scalar wave propagation, diffusive sheaf baselines, and state-of-the-art models, demonstrating the benefit of coupling wave dynamics with matrix-valued transport.

1 INTRODUCTION

Deeper message passing expands a graph network’s receptive field but does not ensure effective communication between distant nodes. ONDA combines second-order wave dynamics with learned sheaf transport to preserve influence while transforming signals across the graph.

1 INTRODUCTION

  • Greater propagation depth does not guarantee distant-node communication, as over-smoothing, over-squashing, and vanishing gradients can impede information exchange.The introduction frames effective long-range propagation as a central graph representation learning challenge.Source: §1 · p. 1
  • Existing approaches modify graph paths, enable direct attention between nodes, or change propagation dynamics while retaining sparse local interactions.Oscillatory DE-GNNs use second-order wave dynamics on the original graph.Source: §1 · p. 1
  • Sheaf neural networks learn matrix-valued couplings between neighboring stalks, but richer local transport alone does not ensure effective long-range communication.Repeated dissipative propagation means distant information must pass through successive sheaf transformations.Source: §1 · p. 2
  • ONDA uses learned sheaf Laplacians to govern second-order oscillatory dynamics, so restriction maps shape signal transformations and interference as information propagates.The learned sheaf acts as a propagation medium combining wave persistence with expressive local geometry.Source: §1 · p. 2
  • The paper presents a theoretical analysis of distant influence and reports empirical performance across long-range propagation, over-squashing mitigation, and heterophilic graph learning.These are the paper’s three stated contributions alongside introducing ONDA.Source: §1 · p. 2

2 RELATED WORK

Prior approaches to long-range graph learning alter topology, use attention, or modify propagation dynamics, while sheaf models enrich local transport. ONDA combines oscillatory propagation with learned matrix-valued sheaf transport.

2 RELATED WORK

  • Long-range methods include graph rewiring, Graph Transformers, and changes to propagation dynamics, including oscillatory GNNs that use second-order dynamics on the original graph.ONDA differs by introducing oscillatory dynamics into sheaf neural networks.Source: §2 · p. 2
  • ONDA’s single-edge schematic shows restriction maps placing oscillating node states in a shared edge stalk, where mapped signals can interfere constructively or destructively.The blue curve represents the superposition of the mapped signals.Source: Figure 1 · p. 3
  • Cellular sheaves provide matrix-valued restriction maps, but most existing sheaf neural networks remain diffusion-centered and can struggle with long-range interactions.Prior sheaf work includes parametrizations, polynomial filters, large-scale diffusion, and directional routing.Source: §2 · p. 3

3 ONDA

ONDA is a sheaf neural network that combines stalk-valued graph representations with learned transport and second-order oscillatory dynamics. Its dynamics are discretized for computation and can be organized into blocks with fixed or adaptive restriction maps.

3 ONDA

  • ONDA introduces second-order oscillatory dynamics into sheaf neural networks so stalk-valued information can remain relevant as it traverses the graph.The framework is presented as a new class of sheaf neural networks.Source: §3 · p. 3

3.1 NOTATION AND PRELIMINARIES

  • A cellular sheaf assigns vector spaces to vertices and edges and linear restriction maps to incidences; its Laplacian compares neighboring states after mapping them into a common edge space.The adjoint maps each discrepancy back to an incident node for aggregation.Source: §3.1 · p. 3
  • The continuous node-state dynamics are implemented through numerical discretization, with X(ℓ) denoting features after ℓ integration steps of size h.The discrete features approximate the continuous state at time tℓ = hℓ.Source: §3.1 · p. 4

3.2 OSCILLATORY NEURAL DYNAMICS ON SHEAVES

  • ONDA evolves stalk-valued representations with a second-order equation whose sheaf Laplacian term shapes propagation, while state-dependent terms provide dissipation and external forcing.The equation also uses weights acting on stalk coordinates and feature channels.Source: §3.2 · p. 4
  • With zero dissipation and forcing and identity weights, the dynamics reduce to a cellular-sheaf generalization of the graph wave equation; learned dissipation and forcing allow task-adaptive behavior.Dissipation attenuates propagated information, while forcing supplies an additional learned drive.Source: §3.2 · p. 4
  • Multiple propagation instances can be stacked with MLP transformations, and restriction maps may be fixed within a block or recomputed at each step from current features.The fixed setting infers maps from the block input; the adaptive setting lets evolving states reshape the propagation medium.Source: §3.2 · pp. 4–5

4 THEORETICAL ANALYSIS

The analysis tracks source-to-target stalk sensitivity in ONDA’s conservative second-order sheaf dynamics. It shows how connected-node influence is assembled from walks and remains oscillatory rather than vanishing, with a discrete analogue under a stability condition.

4 THEORETICAL ANALYSIS

  • With restriction maps fixed, identity weights, and one feature channel, the conservative block follows the second-order equation X¨ + L_FX = 0.Initial node features and velocities determine the trajectory through sheaf cosine and sine operators.Source: §4 · p. 5
  • A source-stalk perturbation produces a matrix-valued target response that captures both interaction strength and how source directions transform at the target.In the small-perturbation limit, this response is the sheaf analogue of a GNN sensitivity-analysis Jacobian.Source: §4 · pp. 5–6
  • For nodes at distance r, shortest-path walks contribute first; longer propagation times bring progressively longer walks into the response.Walk contributions are weighted by time-dependent coefficients, so graph distance delays communication but does not prevent it between connected nodes.Source: §4 · p. 6
  • Positive-eigenvalue contributions oscillate, so source-to-target sensitivity may vary in strength but cannot decay to zero, unlike heat-flow sheaf models.The zero-eigenvalue contribution remains constant; positive-eigenvalue components can reinforce or cancel over time.Source: §4 · pp. 6–7
  • Under h²λ_max(L_F) < 4, discrete source-to-target response is bounded and, if nonzero at any step, does not converge to zero.Communication requires at least ℓ ≥ r updates for nodes at distance r; as ℓh approaches fixed T while h shrinks, the spectral expansion recovers the continuous-time expression.Source: §4 · p. 7

5 EXPERIMENTS

The experiments probe long-range propagation, severe graph bottlenecks, and transfer across graph topologies, and also include heterophilic benchmarks.

5.1 LONG-RANGE PROPAGATION: ECHO BENCHMARK

  • ONDA achieves the lowest error on ECHO-Synth SSSP and eccentricity and remains competitive on diameter prediction.It also surpasses the closely related oscillatory baselines SONAR and GraphCON, as well as sheaf models NSD and CSNN.Source: §5.1 · p. 8, Table 1 · p. 8

5.2 GRAPH BOTTLENECK INFORMATION TRANSFER: BARBELL BENCHMARK

  • At N = 50, ONDA alone satisfies the Barbell solving criterion, while all baselines show only limited information transfer.ONDA also solves the task near-perfectly at N = 10 and N = 20.Source: §5.2 · p. 8

5.3 GRAPH TRANSFER TASK

  • ONDA has the lowest error at almost all tested distances across Line, Ring, and Crossed-Ring graphs, outperforming oscillatory baselines and favorably comparing with GPS.GPS uses graph-wide attention, whereas ONDA relies on local propagation.Source: §5.3 · p. 9, Figure 2 · p. 9

6 CONCLUSION

ONDA couples learned matrix-valued transport with second-order oscillatory dynamics to support long-range propagation.

6 CONCLUSION

  • The learned sheaf determines how information transforms between stalks, while wave-like dynamics keep transformed signals influential as they travel across the graph.Theoretical analysis finds that connected nodes can influence one another regardless of distance.Source: §6 · p. 9
  • Across long-range propagation, short-range over-squashing, and heterophilic benchmarks, ONDA demonstrates strong empirical performance.The conclusion reports state-of-the-art performance on long-range propagation and short-range over-squashing tasks.Source: §6 · p. 9
  • The conclusion presents the coupling of oscillatory dynamics and matrix-valued transport as ONDA’s central design.This design is framed as enabling effective long-range information propagation.Source: §6 · p. 9

A MATHEMATICAL BACKGROUND AND PROOFS

Appendix A supplies mathematical background and proofs for the paper’s theoretical results. It establishes operator conventions, spectral properties, the continuous wave solution, and pathwise and spectral response representations.

A.1 PRELIMINARIES ON INNER PRODUCTS AND NORMS

  • In finite-dimensional spaces, operator and Hilbert–Schmidt norms are equivalent, and absolute convergence of an operator series ensures operator-norm convergence.The appendix also records basic operator-norm bounds and conventions for inner products and orthonormal bases.Source: §A.1 · pp. 15–16

A.2 SHEAF LAPLACIAN AND SPECTRAL BOUNDS

  • The symmetrically normalized sheaf Laplacian is self-adjoint with eigenvalues in [0, 2]; the directed variant need not be self-adjoint.Identifying the two oriented edge stalks and sharing their restriction maps recovers the undirected operator.Source: §A.2 · p. 16

A.3 SOLUTION OF THE SHEAF WAVE EQUATION

  • For fixed L_F and initial position X and velocity V, the unique wave-equation solution is X(t) = C_F(t)X + S_F(t)V.The derivation rewrites the second-order dynamics as a first-order system and uses its operator exponential.Source: §A.3 · p. 17

A.4 PROOF OF PROPOSITION 1

  • The pathwise response sums compositions of sheaf-Laplacian blocks over length-k walks, including stationary steps; at the graph distance, these are shortest paths.If nodes lie in different connected components, the walk sets are empty and the corresponding response vanishes.Source: §A.4 · pp. 17–18

A.5 PROOF OF PROPOSITION 2

  • The spectral representation uses orthogonal projectors onto the eigenspaces of the positive-semidefinite self-adjoint sheaf Laplacian, including the projector onto its kernel.The kernel projector is zero when zero is absent from the spectrum.Source: §A.5 · p. 18

A.6 PROOF OF THEOREM 1

Appendix A.6 proves properties of ONDA’s discrete response, including locality, boundedness, non-vanishing, and convergence to the continuous response. The appendix also documents experimental details, restriction-map choices, and baseline families.

A.6 PROOF OF THEOREM 1

  • The discrete response is a degree-at-most-ℓ polynomial in L_F, so nodes more than ℓ hops apart have zero response.Its polynomial form yields the finite-step locality result.Source: §A.6 · pp. 19–20
  • Under h²λmax(L_F) < 4, the discrete response remains bounded with depth, and any response nonzero at one step does not converge to zero.The proof excludes convergence to zero using a strictly positive limit for the Cesàro average of squared Hilbert–Schmidt norms.Source: §A.6 · pp. 20–21
  • For fixed propagation time T, the discrete spectral coefficients converge to their continuous counterparts as h tends to zero.The result is stated for each eigenvalue of a fixed self-adjoint positive-semidefinite L_F.Source: §A.6 · p. 22

B ADDITIONAL EXPERIMENTAL DETAILS

B.1 RESTRICTION-MAP PARAMETRIZATIONS

  • Diagonal, orthogonal, low-rank, and general restriction maps vary the transport constraints while retaining the same ONDA update rule and oscillatory dynamics.The general map is unconstrained and has O(d²) storage and application complexity.Source: §B.1 · p. 22

B.2 EMPLOYED BASELINES

  • The evaluated baselines span classical and heterophily-specific GNNs, dynamical and sheaf neural networks, graph transformers, and higher-order GNNs.Source: §B.2 · pp. 22–23

B.3 HYPERPARAMETER SEARCH SPACES FOR THE EXPERIMENTS IN SECTION 5

The section reports hyperparameter search spaces for experiments and says Bayesian optimization selects the best settings.

B.3 HYPERPARAMETER SEARCH SPACES FOR THE EXPERIMENTS IN SECTION 5

C.1 RESTRICTION MAP PARAMETRIZATION ABLATION

The ablation compares four restriction-map parametrizations in ONDA and NSD; ONDA improves over matched NSD variants, while greater map expressivity alone does not ensure better transfer.

C.1 RESTRICTION MAP PARAMETRIZATION ABLATION

  • The ablation compares diagonal, orthogonal, low-rank, and general maps in both ONDA and NSD using a single-layer MLP-based map learner.The ONDA configurations omit forcing and dissipation to focus on propagation.Source: §C.1 · p. 24
  • Across restriction-map parametrizations and graph sizes, ONDA substantially improves over the corresponding NSD variant.The comparison evaluates matched parametrizations to assess transfer across severe Barbell bottlenecks.Source: §C.1 · p. 24
  • At N = 10, all four ONDA parametrizations solve the task, while diagonal maps achieve the lowest mean error at N = 20 and N = 50.Diagonal and orthogonal variants remain below the solving threshold across the tested sizes; general maps are not systematically preferable despite greater expressivity.Source: §C.1 · p. 24
  • Table 6 reports Barbell test MSE (×10−3; lower is better) for N ∈ {10, 20, 50}, averaged over five seeds for each model’s best validation-selected configuration.The table marks the best, second-best, and third-best result in each column.Source: Table 6 · p. 24

C.2 HETEROPHILIC TASKS

ONDA is evaluated on five heterophilic benchmarks despite not being designed specifically for them. It ranks third overall and improves over its closest oscillatory and standard sheaf counterparts.

C.2 HETEROPHILIC TASKS

  • The evaluation compares ONDA with conventional MPNNs, graph Transformers, heterophily-specific architectures, and recent sheaf neural networks.The benchmarks are from Platonov et al. (2023).Source: §C.2 · p. 25
  • Hyperparameters are selected by sequential local searches and Bayesian optimization, with final configurations chosen by validation performance.Restriction maps may be learned from GNN encoder representations; at depth zero, an MLP learns them from endpoint node features.Source: §C.2 · p. 25
  • Table 7 reports the hyperparameter values considered for the heterophilic benchmarks.The search proceeds over subsets of candidate values as well as through Bayesian optimization.Source: Table 7 · p. 25, §C.2 · p. 25
  • ONDA ranks third overall by average rank across five heterophilic datasets and consistently improves over SONAR and NSD on every dataset.It remains competitive with BuNN and CSNN.Source: §C.2 · p. 25

D TIME AND MEMORY COMPLEXITY ANALYSIS

The complexity analysis attributes ONDA’s graph-local propagation cost to stalk dimension, feature channels, and restriction-map parameterization, with separate stalk and channel transformations.

D TIME AND MEMORY COMPLEXITY ANALYSIS

  • ONDA’s computational cost depends on stalk dimension, feature channels, and restriction-map parameterization because propagation is graph-local.The analysis defines n = |V| and m = |E|.Source: D TIME AND MEMORY COMPLEXITY ANALYSIS · p. 25
  • The state and velocity each contain ndc scalar entries; the stalk transformation costs O(nd^2c), while channel mixing costs O(ndc^2).The cost of applying the sheaf operator depends on the restriction-map family.Source: D TIME AND MEMORY COMPLEXITY ANALYSIS · p. 25
  • The analysis treats stalk transformation, channel mixing, and sheaf-operator application as distinct components of a propagation step.The sheaf-operator component varies with restriction-map family.Source: D TIME AND MEMORY COMPLEXITY ANALYSIS · p. 25

MPNNs

ONDA retains sparse graph scaling while adding matrix-valued sheaf transport. In matched-parameter Barbell measurements, its variants have lower inference latency than SONAR across tested graph sizes, with higher peak training memory at N = 50.

MPNNs

  • A propagation step includes restriction-map learner cost, sparse sheaf-operator application, and node-wise stalk and channel transformations.Applying the sheaf operator costs O(mq(d)c), where q(d) is the cost of applying one restriction map to one feature channel.Source: MPNNs · p. 27
  • For fixed stalk dimension, feature dimension, and restriction-map parametrization, ONDA’s computational cost scales linearly with n + m, unlike dense Graph Transformers’ O(n^2) dependence on nodes.This preserves sparse message-passing scaling despite matrix-valued local transport.Source: MPNNs · p. 27
  • ONDA’s state and velocity require O(ndc) memory, while unrolled training dynamics require retaining intermediate activations without checkpointing.The analysis also notes that learned restriction maps require additional storage.Source: MPNNs · p. 27
  • The empirical cost comparison uses Barbell graphs, approximately 100k parameters, four blocks, and 12 propagation steps per block.Measurements use batch size one on an RTX 5080.Source: MPNNs · p. 27, Table 9 · p. 28
  • At N = 50, Diag-ONDA and Ortho-ONDA reduce training time by 15.1% and 9.1% versus SONAR, and all four ONDA variants have lower inference latency across N ∈ {10, 20, 50}.At N = 50, peak training memory ranges from 159.9 to 241.8 MB for sheaf variants versus 120.7 MB for SONAR.Source: Table 9 · p. 28, MPNNs · p. 28

Related papers

Loading 2610.10018v1…