PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-Coupled Oscillator Networks

T. Konstantin Rusch, Benjamin P. Chamberlain, James Rowbottom, Siddhartha Mishra, Michael M. Bronstein

arXiv:2202.02296v2cs.LGmath.DSstat.ML

TL;DR

GraphCON addresses oversmoothing and unstable gradients in deep graph neural networks. It builds GNNs from discretized controlled, damped oscillator dynamics with flexible GNN coupling functions, and reports theoretical mitigation of both problems alongside competitive performance across graph-learning tasks.

  • Problem

    Deep GNNs face oversmoothing and exploding or vanishing gradients, which can limit expressive power and impede training.

  • Method

    GraphCON constructs deep GNNs by discretizing oscillator ODEs whose nodes are coupled through the graph and whose coupling function can be a standard GNN layer.

  • Results

    GraphCON theoretically mitigates oversmoothing and exploding or vanishing gradients and performs competitively across node- and graph-level classification and regression tasks.

  • Takeaways & Limitations

    GraphCON provides a flexible framework for constructing deep GNNs with theoretical guarantees and empirical performance across varied graph-learning tasks.

  • Takeaways & Limitations

    The treatment of zero-Dirichlet energy steady states depends on the activation function, with corresponding states specified through roots of σ(c) = c.

Abstract

from arXiv · show

We propose Graph-Coupled Oscillator Networks (GraphCON), a novel framework for deep learning on graphs. It is based on discretizations of a second-order system of ordinary differential equations (ODEs), which model a network of nonlinear controlled and damped oscillators, coupled via the adjacency structure of the underlying graph. The flexibility of our framework permits any basic GNN layer (e.g. convolutional or attentional) as the coupling function, from which a multi-layer deep neural network is built up via the dynamics of the proposed ODEs. We relate the oversmoothing problem, commonly encountered in GNNs, to the stability of steady states of the underlying ODE and show that zero-Dirichlet energy steady states are not stable for our proposed ODEs. This demonstrates that the proposed framework mitigates the oversmoothing problem. Moreover, we prove that GraphCON mitigates the exploding and vanishing gradients problem to facilitate training of deep multi-layer GNNs. Finally, we show that our approach offers competitive performance with respect to the state-of-the-art on a variety of graph-based learning tasks.

1. Introduction

GraphCON is a physically inspired framework that builds deep graph neural networks from discretized oscillator dynamics. It targets oversmoothing and gradient instability while supporting flexible GNN couplings and competitive performance across graph-learning tasks.

  • Framework: GraphCON models nonlinear controlled and damped oscillators coupled through the adjacency structure of the underlying graph.Its dynamics are discretized to construct a graph-learning framework.
  • Flexibility: Any standard GNN layer, including GAT or GCN, can serve as GraphCON’s coupling function for constructing deep networks.The framework acts as a wrapper around an underlying basic GNN layer.
  • Oversmoothing: Zero-Dirichlet energy steady states are not exponentially stable, so GraphCON mitigates oversmoothing by construction.The paper formulates oversmoothing through the stability of these steady states.
  • Gradient stability: GraphCON rigorously mitigates exploding and vanishing gradients, improving the trainability of deep multi-layer GNNs.This is presented as a theoretical property of the resulting GNN.
  • Empirical evaluation: GraphCON achieves competitive performance across transductive and inductive node classification, graph regression, and graph classification tasks.The evaluation covers a wide variety of graph-learning tasks.

2. GraphCON

GraphCON discretizes a second-order graph dynamical system whose oscillator states evolve through a learnable neighborhood coupling. Its time-stepping scheme becomes a deep GNN, while dynamic trajectories extend standard steady-state message passing.

  • Graph dynamical system: GraphCON defines node features on an undirected graph and models their evolution with a nonlinear graph dynamical system.The system uses time-dependent node features and a learnable neighborhood coupling.
  • Graph dynamical system: The framework introduces velocity as an auxiliary variable, converting the second-order ODEs into a first-order system.This reformulation supports iterative numerical solution.
  • Discretization: GraphCON uses an IMEX time-stepping scheme extending symplectic Euler to systems with damping.The fixed time step produces hidden node features at successive times.
  • Discretization: The discretized iterations function as an N-layer GNN, with the coupling function serving as the message-passing mechanism.The output may also include linear input and readout layers.
  • Coupling functions: GraphCON supports neighborhood couplings based on GraphSAGE, attention, convolution, SplineCNN, or MoNet mechanisms.The paper focuses particularly on attentional and convolutional choices.
  • Relation to standard GNNs: Standard GNNs correspond to steady-state or fixed-point iterations, whereas GraphCON dynamically explores richer latent feature trajectories.This dynamic sampling may provide greater expressive power and enables a flexible wrapper around basic GNN layers.

3. Properties of GraphCON

GraphCON uses oscillator dynamics to evolve node features and address oversmoothing and gradient instability in deep GNNs. Its dynamics can preserve or redistribute energy, avoid stable zero-Dirichlet-energy states, and keep gradients controlled with suitable discretization.

  • GraphCON dynamics: GraphCON models graph-coupled oscillators whose node features evolve dynamically through coupling functions based on neighboring nodes.The framework includes uncoupled and coupled oscillator cases, with unit-frequency oscillations in the simplest uncoupled setting.
  • GraphCON dynamics: GraphCON’s oscillatory node-feature dynamics depend on graph adjacency and are illustrated on a ZINC molecular graph using GraphCON-GCN.The figure propagates initial positions through time using random weights and compares t = 0 with t = 20.
  • Oversmoothing: Oversmoothing occurs when deep GNN node features converge exponentially toward a common constant, equivalently when layer-wise Dirichlet energy vanishes exponentially.GraphCON formulates this behavior through stability of zero-Dirichlet-energy steady states.
  • Oversmoothing: For the analyzed GraphCON ODEs and structure-preserving discretizations, zero-Dirichlet-energy steady states are not exponentially stable, mitigating oversmoothing by construction.In the general nonlinear time-dependent case, small perturbations can grow polynomially rather than decay exponentially.
  • GraphCON dynamics: Standard GNN layers can be recovered as steady states, whereas GraphCON samples trajectories through latent feature space and can therefore provide richer representations.The trajectories may explore large parts of the latent space, contributing to expressive power.
  • Gradient stability: GraphCON controls deep-network gradients: gradients are globally bounded when ∆t ∼ N^-1, while in the coupled linear case their leading order is independent of layer count.These results address exploding and vanishing gradients under the stated assumptions, including sufficiently small ∆t.

4. Related Work

GraphCON builds on differential-equation approaches to machine learning and differs from diffusion-based graph models through its second-order temporal dynamics. Related work also includes dissipative wave models and coupled-oscillator RNNs.

  • Differential-equation approaches: Earlier differential-equation approaches informed nonlinear dimensionality reduction, ranking, Neural ODEs, and graph neural networks.Graph-based examples include diffusion-type PDEs with graph differential operators and learnable neighborhood coupling.
  • Relation to diffusion models: Removing GraphCON’s second-order time derivative under specific parameter settings recovers graph diffusion PDEs, distinguishing GraphCON by its second-order temporal term.The comparison is made for identity activation with α = γ = 1.
  • Wave-based models: A damped wave or Telegrapher’s equation from related graph models can arise as a special case of GraphCON with identity activation.
  • Oscillator-based models: Networks of coupled, controlled oscillators were also previously used to design recurrent neural networks.

5. Experimental results

GraphCON is evaluated across diverse graph-learning tasks using GCN- and GAT-based couplings, with experiments showing reduced oversmoothing and competitive or improved performance over baseline GNNs.

  • Dirichlet energy: 100-layer experiments show standard GAT and GCN energies converge exponentially to zero, whereas GraphCON avoids this behavior and stabilizes after initial decay for α = 0.5.The experiment propagates random features through GAT, GCN, GraphCON-GAT, and GraphCON-GCN on a 10 × 10 grid with γ = 1.
  • Homophilic node classification: GraphCON-GCN and GraphCON-GAT consistently outperform pure GCN and GAT on homophilic citation-network node classification, with GraphCON models performing best overall.The comparison includes Cora, Citeseer, and Pubmed, alongside standard and differential-equation-based baselines.
  • Heterophilic node classification: On heterophilic graphs, GraphCON-GCN and GraphCON-GAT outperform their underlying models and recent heterophily-specific baselines, including 85.4% and 82.2% on Texas versus 55.1% and 52.2%.The reported Texas results are mean accuracies for GraphCON-GCN, GraphCON-GAT, GCN, and GAT, respectively.
  • Inductive node classification: On PPI, GraphCON raises test micro-average F1 from 97.4% to 99.4% for GAT and from 98.5% to 99.6% for GCN, with GraphCON-GCN achieving the benchmark’s top result.The evaluation follows the protocol of Hamilton et al. and compares GraphCON with standard GNN baselines.
  • Molecular graph regression: On ZINC molecular regression, both GraphCON-GAT and GraphCON-GCN outperform GAT and GCN by a factor of 2, while GraphCON-GCN matches DGN with lower standard deviation.The benchmark uses 12K molecular graphs, no edge features, and networks restricted to approximately 100K parameters.
  • MNIST superpixel classification: On MNIST superpixel graph classification, GraphCON-GCN improves test accuracy from 88.89% for GCN to 98.70%, while GraphCON-GAT reaches 98.91% and outperforms all other methods.The models share parameters across layers, so GraphCON-GCN’s improvement is attributed to additional iterations rather than more parameters.

6. Conclusions

GraphCON is a flexible deep-GNN framework that uses oscillator dynamics to build layered networks with theoretical mitigation of oversmoothing and gradient instability. Experiments across graph tasks show improved performance over base GNNs and competitiveness with state-of-the-art methods.

  • Framework: GraphCON discretizes controlled, damped oscillator ODEs to propagate information through multiple GNN layers.Its coupling function can be any standard GNN hidden layer, including GAT or GCN.
  • Framework: Any standard GNN layer can serve as GraphCON’s coupling function, enabling a flexible framework for very deep GNNs.
  • Theoretical properties: GraphCON mitigates oversmoothing because zero-Dirichlet-energy steady states are not exponentially stable under its oscillator dynamics.Small perturbations move node features away from a constant feature vector.
  • Theoretical properties: GraphCON rigorously mitigates exploding and vanishing gradients, facilitating efficient training of deep GNNs.
  • Empirical evaluation: Across node- and graph-level classification and regression tasks, GraphCON models outperform their base GNNs and are on par with or better than state-of-the-art models.The evaluation includes heterophilic datasets that are challenging for standard GNNs.

A.1. Performance of GraphCON with respect to number of layers

Experiments examine how GraphCON performance changes with depth and oscillator hyperparameters. Unlike standard GCNs, GraphCON generally improves as layers increase and remains robust across broad parameter ranges.

  • Performance versus depth: For ZINC regression, standard GCN mean absolute error increases with depth, whereas GraphCON-GCN mean absolute error decreases as layers are added.The comparison covers models with up to 20 layers.
  • Performance versus depth: On MNIST Superpixel classification, increasing depth worsens GCN test accuracy but improves GraphCON-GCN test accuracy through 32 layers.
  • Performance versus depth: GraphCON-GCN improves or retains performance over GCN+DropEdge across a large increase in layers on Cora.The comparison uses depths N = 2, 4, 8, 16, 32, 64.
  • Hyperparameter sensitivity: GraphCON’s damping parameter α and frequency-control parameter γ are evaluated for sensitivity using the MNIST Superpixel graph-classification task.The study varies α and γ over [0, 2] while fixing the other parameter at a best-performing value.
  • Hyperparameter sensitivity: GraphCON accuracy is robust across a broad reasonable range of α and γ values, with deterioration only at high damping or very small frequency control.

B. Training details

The experiments use fixed implementation settings and validation-based hyperparameter selection. Supplementary derivations document the mathematical steps underlying the reported results.

  • Experimental settings: Experiments use a fixed time-step Δt = 1, with α and γ set according to dataset-specific experimental settings.Cora, Citeseer, and Pubmed use α = γ = 1, while Texas, Cornell, and Wisconsin use α = γ = 0.
  • Experimental settings: The best-performing GraphCON hyperparameters α and γ for each model are selected using a validation set.
  • Mathematical details: The supplementary mathematical results derive identities by summing over graph nodes, using adjacency symmetry, and integrating over time.

C.2. Proof of Proposition 3.3

The proof connects convergence to constant node features with exponentially stable steady states. This establishes the dynamical characterization used to analyze oversmoothing.

  • Proof of Proposition 3.3: If all hidden node features converge to the same vector c exponentially, the corresponding steady state is a candidate oversmoothing state.
  • Proof of Proposition 3.3: Oversmoothing is equivalent to (c, 0) being an exponentially stable fixed point of the oscillator dynamics.
  • Proof of Proposition 3.3: An exponentially stable steady state forces trajectories to converge exponentially, causing the node-feature Dirichlet energy to vanish.

C.3. Proof of Proposition 3.4

The proof analyzes perturbations around the steady state (c, 0) through a linearized energy identity. Dissipative and growth terms combine to produce algebraic growth, so the steady state is not exponentially stable.

  • Perturbation analysis: The proof studies small perturbations around the fixed point (c, 0) using the linearized system.The nonlinear ODE is globally Lipschitz, and sufficiently small-time perturbation dynamics can be approximated by the linearized system.
  • Energy balance: The perturbation energy is balanced by dissipation, production, and a coupling-asymmetry term.The dissipative term damps perturbations exponentially, while the positive production term grows them; the third term depends on asymmetry in the graph-coupling matrix.
  • Energy balance: The production term has leading algebraic growth with respect to the initial perturbations.This follows after using the right-stochasticity of the coupling matrix in the energy identity.
  • Conclusion: For α ≥1/2, the overall balance yields algebraic growth rather than exponential decay, so small perturbations leave (c, 0).Thus the steady state is not exponentially stable, completing Proposition 3.4.
  • Conclusion: The proof uses α ≥1/2 only as a sufficient condition and indicates that it can be replaced by a weaker condition.The subsequent remark qualifies the parameter restriction used in Proposition 3.4.

C.4. Proofs of Propositions 3.5 and 3.6

The proofs establish bounds on hidden states and gradients for GraphCON under time-step and activation assumptions. In particular, the leading gradient behavior is independent of depth, preventing exponential decay with the number of layers.

  • Hidden-state bounds: The hidden-state estimate is proved by combining the GraphCON update, activation-function bounds, and a sufficiently small time step.The proof repeatedly applies elementary identities and chooses Δt small enough to close the estimate.
  • Hidden-state bounds: Proposition 3.5 derives an upper bound on hidden node features for GraphCON when the time step satisfies the stated condition.The bound depends on the global activation bound β and is obtained by iterating a one-step estimate.
  • Gradient bounds: The proofs use order notation for scalar and matrix bounds and differentiate the loss to analyze gradients.These steps establish the notation and derivative expressions used in Proposition 3.6.
  • Gradient bounds: The gradient proof represents layerwise derivatives through products of bounded matrices and applies the product rule to obtain the target bound.The argument uses the representation formula and bounds on the matrices E and F.
  • Gradient bounds: To leading order in Δt, the gradient is independent of the number of layers N, so increasing depth does not make it vanish.Although the gradient may be small because Δt is small, polynomial dependence Δt ∼N^-s still prevents exponential decay in N.
Loading 2202.02296v2…