Graph-Coupled Oscillator Networks

T. Konstantin RuschBen ChamberlainJames RowbottomSiddhartha MishraMichael M. Bronstein

article2022ICML177 citations

Develops a physics-inspired framework based on coupled second-order oscillator differential equations that wraps existing graph neural network layers to mitigate oversmoothing and gradient instability in very deep architectures.

Listen

Graph Neural Networks serve as a standard approach for analyzing relational data across applications such as molecular modeling, transportation, and social network analysis. However, standard architectures struggle to scale effectively with network depth due to two major technical hurdles: oversmoothing, where node representations exponentially converge toward identical values as layers are added, and vanishing or exploding gradients, which impede model training. Consequently, practitioners are frequently forced to deploy shallow models, limiting the model's expressive capacity.

The article introduces and evaluates Graph-Coupled Oscillator Networks, a general mathematical framework for deep graph learning inspired by physics. The primary objective is to demonstrate that modeling graph dynamics as a system of controlled, damped oscillators mitigates both oversmoothing and gradient degradation, enabling the successful training of significantly deeper graph networks.

The authors formulate their approach by viewing graph layers as time steps within a discretized second-order system of ordinary differential equations. This design acts as a modular wrapper capable of incorporating standard graph operations, such as convolutional or attentional mechanisms. The framework's validity is established through mathematical proofs of dynamic stability and gradient bounds, alongside empirical testing across varied benchmark tasks, including transductive and inductive node classification, molecular property regression, and image-derived graph classification.

The investigation yields several key findings:

Theoretical analysis confirms that zero-energy states associated with oversmoothing are dynamically unstable under the proposed formulation, preventing node features from collapsing into a single average value as network depth increases.
Mathematical derivations prove that training gradients remain bounded and do not vanish exponentially with added layers, resolving standard optimization bottlenecks in deep architectures.
Across empirical benchmarks, the framework consistently outperformed baseline models; on heterophilic network datasets where neighboring nodes differ significantly, classification accuracy rose substantially (e.g., from approximately 52–55% with standard baselines to 82–85% on the Texas benchmark).
In molecular regression tasks on the ZINC dataset, the model cut prediction errors by roughly half relative to baseline graph convolutional and attention networks (reducing Mean Absolute Error from ~0.46–0.47 down to 0.22–0.23), with performance scaling favorably as depth expanded up to 20–32 layers.

These results demonstrate that deep graph architectures can be successfully deployed without encountering traditional degradation issues. By enabling deeper information propagation without a corresponding explosion in parameter count, organizations can improve predictive accuracy on complex relational datasets without incurring excessive computational parameter overhead. The findings differ from conventional expectations by showing that deeper models can monotonically improve performance rather than degrade it.

Organizations evaluating or deploying graph learning systems should consider incorporating oscillator-based wrappers into existing convolutional or attention pipelines, particularly for complex tasks involving heterophilic graphs or long-range dependencies. Prior to large-scale deployment, teams should conduct internal hyperparameter tuning on the system's damping and frequency controls, as extreme damping values can constrain model effectiveness. Confidence in the mathematical and empirical results is high across the evaluated academic benchmarks; however, practitioners should pilot the framework on domain-specific, large-scale industrial graphs to assess runtime memory overhead during training before broad enterprise adoption.

ETH Zurich Twitter University of Oxford deep learning graph-based ode Graph-Coupled Oscillator Networks graph neural networks graph convolution

tk-rusch/GraphCON Rusch et al (2022).pdf

Paper: Simple and Deep Graph Convolutional Networks, Ming Chen et al. (2020). Introduces GCNII and provides fundamental insights and baselines for addressing the over-smoothing and vanishing gradient problems in deep multi-layer graph neural networks.
Paper: Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View, Deli Chen et al. (2019). Formalizes metrics and topological explanations for the over-smoothing problem in GNNs, providing essential motivation for GraphCON's dynamical system formulation.
Paper: Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning, Qimai Li et al. (2018). Analyzes graph convolutions as Laplacian smoothing that leads to oversmoothing across deeper layers, establishing the theoretical baseline problem that GraphCON seeks to overcome via second-order ODE dynamics.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). Introduces standard graph convolutional networks, which GraphCON uses as foundational coupling layers within its continuous oscillator framework.
Paper: A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights, Weijie Su et al. (2014). Provides foundational theoretical analysis on modeling accelerated dynamical algorithms through second-order ordinary differential equations with damping and friction terms.
Paper: DeepGCNs: Can GCNs Go As Deep As CNNs?, Guohao Li et al. (2019). Investigates architectural modifications to enable very deep graph neural networks without suffering from vanishing gradients or oversmoothing.
Paper: DropEdge: Towards Deep Graph Convolutional Networks on Node Classification, Yu Rong et al. (2019). Presents an empirical approach to preventing oversmoothing in deep GCN architectures, serving as important context for training deep graph models.

Paper: Benchmarking Graph Neural Networks, Vijay Prakash Dwivedi et al. (2023). Establishes a standardized, medium-scale benchmarking suite that provides a rigorous evaluation platform for continuous and discrete deep GNN architectures like GraphCON.

Cover for Graph-Coupled Oscillator Networks

Abstract

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.

Topics

deep learning graph-based ode network architecture

Keywords

Graph-Coupled Oscillator Networks graph neural networks graph convolution Dirichlet energy dynamical systems neighborhood coupling differential equations MNIST superpixel molecular graphs

1. Introduction
2. GraphCON
3. Properties of GraphCON
4. Related Work
5. Experimental results
5.1. Evolution of Dirichlet Energy.
5.2. Transductive node classification
5.3. Inductive node classification
5.4. Molecular graph property regression
5.5. MNIST Superpixel graph classification
6. Conclusions
References
A. Further experimental results
A.1. Performance of GraphCON with respect to number of layers
A.2. Sensitivity of performance of GraphCON to hyperparameters α and γ
B. Training details
C. Mathematical details for Section 3 of main text
C.1. Proof of Proposition 3.1
C.2. Proof of Proposition 3.3
C.3. Proof of Proposition 3.4
C.4. Proofs of Propositions 3.5 and 3.6
C.4.1. PROOF OF PROPOSITION 3.5
C.4.2. PROOF OF PROPOSITION 3.6

Knowls

Knowl 1 — Graph-Coupled Oscillator Network (GraphCON) Framework
model/method
GraphCON is a framework for deep learning on graphs inspired by networks of coupled, controlled, and damped non-linear oscillators. For an undirected graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ with $v = |\mathcal{V}|$ nodes, node 1-neighborhoods $\mathcal{N}_i = \{j \in \mathcal{V} : \{i, j\} \in \mathcal{E}\}$ , and a time-dependent node feature matrix $X(t) \in \mathbb{R}^{v \times m}$ , the continuous dynamics are governed by the second-order ordinary differential equation (ODE) system:

$X'' = \sigma(F_\theta(X, t)) - \gamma X - \alpha X'$

where $\sigma: \mathbb{R} \to \mathbb{R}$ is an element-wise activation function, $\gamma > 0$ is a frequency parameter, $\alpha \ge 0$ is a damping parameter, and $F_\theta: \mathbb{R}^{v \times m} \times \mathbb{R} \to \mathbb{R}^{v \times m}$ is a learnable 1-neighborhood coupling function parameterized by $\theta$ .

Introducing an auxiliary velocity matrix $Y(t) = X'(t) \in \mathbb{R}^{v \times m}$ gives the equivalent first-order system:

$\begin{aligned} Y' &= \sigma(F_\theta(X, t)) - \gamma X - \alpha Y \\ X' &= Y \end{aligned}$

Given input features $X(0)$ (with initial velocities typically set as $Y(0) = X(0)$ ), this system is discretized across $N$ layers with a fixed time-step $\Delta t > 0$ using an implicit-explicit (IMEX) numerical scheme:

$\begin{aligned} Y^n &= Y^{n-1} + \Delta t \left[\sigma(F_\theta(X^{n-1}, t^{n-1})) - \gamma X^{n-1} - \alpha Y^{n-1}\right] \\ X^n &= X^{n-1} + \Delta t Y^n \end{aligned}$

for $n = 1, \dots, N$ , where $X^n, Y^n \in \mathbb{R}^{v \times m}$ denote the hidden node features and velocities at discrete time $t^n = n\Delta t$ .

Standard coupling choices for $F_\theta(X^n, t^n)$ include:
- Graph Attention (GAT) coupling: $(F_\theta(X^n, t^n))_i = \sum_{j \in \mathcal{N}_i} A_{ij}^n X_j^n W^n$ , where $W^n \in \mathbb{R}^{m \times m}$ is a weight matrix and $A_{ij}^n$ are attention coefficients computed via LeakyReLU over transformed features.
- Graph Convolutional (GCN) coupling: $F_\theta(X^n, t^n) = \hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} X^n W^n$ , with $\hat{A} = A + I_v$ and $\hat{D} = \text{diag}(\sum_l \hat{A}_{kl})$ .
Knowl 2 — Recovery of Standard Message-Passing GNNs as Steady States of GraphCON
theoretical result
For an autonomous coupling function $F_\theta(X)$ (such as standard GCN or GAT operators without explicit time dependence), the steady states $(X^*, Y^*)$ of the continuous GraphCON dynamical system satisfy $Y^* = 0$ and:

$X^* = \frac{\Delta t}{\gamma} \sigma(F_\theta(X^*))$

Applying a fixed-point iteration to solve for $X^*$ yields the multi-layer iterative scheme:

$X^n = \frac{\Delta t}{\gamma} \sigma(F_\theta(X^{n-1})) \quad \text{for } n = 1, \dots, N$

Up to a rescaling factor $\frac{\Delta t}{\gamma}$ , this fixed-point iteration corresponds exactly to the standard update equation of an $N$ -layer message-passing Graph Neural Network (GNN). Consequently, while standard GNN architectures can be interpreted as seeking steady states of the graph dynamical system, GraphCON evolves node features along dynamic trajectories, enabling feature vectors to explore a richer latent feature space rather than remaining confined to the vicinity of fixed points.
Knowl 3 — Energy Conservation in Undamped Linear GraphCON
theoretical result
Consider the GraphCON ODE system with an identity activation function $\sigma(x) = x$ , zero damping $\alpha = 0$ , frequency parameter $\gamma = 1$ , and a time-independent, symmetric, right-stochastic coupling matrix $A \in \mathbb{R}^{v \times v}$ (satisfying $0 \le A_{ij} \le 1$ , $A_{ij} = A_{ji}$ for all $j \in \mathcal{N}_i$ , $A_{ij} = 0$ for $j \notin \mathcal{N}_i$ , and $\sum_{j \in \mathcal{N}_i} A_{ij} = 1$ for all $i \in \mathcal{V}$ ):

$\begin{aligned} X_i' &= Y_i \\ Y_i' &= \sum_{j \in \mathcal{N}_i} A_{ij} X_j - X_i \end{aligned}$

For all $t > 0$ , the total energy $\mathcal{E}(t)$ of the system is strictly conserved:

$\sum_{i \in \mathcal{V}} \|Y_i(t)\|^2 + \sum_{i \in \mathcal{V}} \sum_{j \in \mathcal{N}_i} A_{ij} \|X_i(t) - X_j(t)\|^2 = \sum_{i \in \mathcal{V}} \|Y_i(0)\|^2 + \sum_{i \in \mathcal{V}} \sum_{j \in \mathcal{N}_i} A_{ij} \|X_i(0) - X_j(0)\|^2$

where $\|\cdot\|$ is the Euclidean norm in $\mathbb{R}^m$ . The feature trajectories are constrained to lie on the level sets of this energy functional, redistributing energy across graph nodes without producing or destroying total energy.
Knowl 4 — Dynamical Characterization of GNN Oversmoothing via Fixed-Point Stability
theoretical result
On an undirected graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ with $v = |\mathcal{V}|$ nodes, the Dirichlet energy of node features $X \in \mathbb{R}^{v \times m}$ is defined by:

$E(X) = \frac{1}{v} \sum_{i \in \mathcal{V}} \sum_{j \in \mathcal{N}_i} \|X_i - X_j\|^2$

Oversmoothing in an $N$ -layer GNN is defined as the exponential convergence to zero of the layer-wise Dirichlet energy, $E(X^n) \le C_1 e^{-C_2 n}$ for $C_1, C_2 > 0$ (or $E(X(t)) \le C_1 e^{-C_2 t}$ for continuous time $t > 0$ ).

For the first-order GraphCON dynamical system:

$Y' = \sigma(F_\theta(X, t)) - \gamma X - \alpha Y, \quad X' = Y$

oversmoothing occurs if and only if the zero-Dirichlet energy states $(X^*, Y^*) = (c\mathbf{1}_v^\top, 0)$ are exponentially stable steady states (fixed points) of the ODE system for some constant feature vector $c \in \mathbb{R}^m$ , where $\mathbf{1}_v \in \mathbb{R}^v$ is the vector of all ones and $0$ is the $v \times m$ zero matrix.
Knowl 5 — Mitigation of Oversmoothing via Instability of Zero-Dirichlet Energy Fixed Points
theoretical result
Consider the GraphCON ODE system with coupling matrix $A(X_i, X_j)$ :

$X_i' = Y_i, \quad Y_i' = \sigma\left(\sum_{j \in \mathcal{N}_i} A_{ij} X_j\right) - X_i - \alpha Y_i \quad \text{for all } i \in \mathcal{V}$

where $\sigma(x) = \max(x, 0)$ (ReLU) and the coupling entries satisfy $0 \le A_{ij} \le 1$ and $\sum_{j \in \mathcal{N}_i} A_{ij} = 1$ .

For any constant vector $c \in \mathbb{R}^m$ with non-negative entries ( $c_\ell \ge 0$ for all $1 \le \ell \le m$ ), the state $(c, 0)$ is a steady state of the ODE. Under the damping condition $\alpha \ge \frac{1}{2}$ (or more generally $\alpha \ge \frac{\bar{D} - \underline{D}}{2\underline{D}\bar{D}}$ , where $\bar{D} = \max_{i \in \mathcal{V}} \text{deg}(i)$ and $\underline{D} = \min_{i \in \mathcal{V}} \text{deg}(i)$ ):
1. Small perturbations around the steady state $(c, 0)$ grow algebraically over short time intervals rather than decaying exponentially.
2. The zero-Dirichlet energy steady states $(c, 0)$ are not exponentially stable.
Because zero-Dirichlet energy steady states are unstable, small perturbations drive trajectories away from uniform node representations, preventing exponential decay of Dirichlet energy and mitigating oversmoothing by construction.
Knowl 6 — Mitigation of Exploding Gradients in Deep GraphCON-GCN
theoretical result
Consider an $N$ -layer GraphCON-GCN model with scalar node features ( $m=1$ ) and $\alpha = \gamma = 1$ , where the discrete dynamics are:

$Y_i^n = (1 - \Delta t) Y_i^{n-1} + \Delta t \sigma(C_i^{n-1}) - \Delta t X_i^{n-1}, \quad C_i^{n-1} = \frac{w_i^n}{d_i} X_i^{n-1} + \sum_{j \in \mathcal{N}_i} \frac{w_j^n X_j^{n-1}}{\sqrt{d_i d_j}}, \quad X_i^n = X_i^{n-1} + \Delta t Y_i^n$

with node degrees $d_i = \text{deg}(i)$ , learnable layer weights $w^n \in \mathbb{R}^v$ , bounded activation $|\sigma(x)| \le \beta$ , $|\sigma'(x)| \le \beta'$ , and mean squared error loss $J(w) = \frac{1}{2v} \sum_{i \in \mathcal{V}} |X_i^N - \bar{X}_i|^2$ against target $\bar{X} \in \mathbb{R}^v$ .

For sufficiently small time step $\Delta t \ll 1$ , the gradient of the loss with respect to any weight parameter $w_k^\ell$ ( $1 \le k \le v, 1 \le \ell \le N$ ) is bounded by:

$\left|\frac{\partial J}{\partial w_k^\ell}\right| \le \frac{\beta' \hat{D} \Delta t (1 + \Gamma N \Delta t)}{v} \max_{1 \le i \le v} (|X_i^0| + |Y_i^0|) + \frac{\beta' \hat{D} \Delta t (1 + \Gamma N \Delta t)}{v} \left(\max_{1 \le i \le v} |\bar{X}_i| + \beta \sqrt{N \Delta t}\right)^2$

where $\hat{D} = \max_{i, j \in \mathcal{V}} \frac{1}{\sqrt{d_i d_j}}$ and $\Gamma = 6 + 4\beta' \hat{D} \max_{1 \le n \le N} \|w^n\|_1$ .

This bound guarantees that:
- If $\Delta t \sim N^{-1}$ , the gradient bound is globally constant and completely independent of the total depth $N$ .
- If $\Delta t$ is held constant, the gradient bound grows at most quadratically in $N$ , preventing exponential explosion of gradients.
Knowl 7 — Mitigation of Vanishing Gradients in Deep GraphCON-GCN
theoretical result
In the $N$ -layer GraphCON-GCN model with time step $\Delta t$ , scalar features ( $m=1$ ), and loss $J(w) = \frac{1}{2v} \sum_{i \in \mathcal{V}} |X_i^N - \bar{X}_i|^2$ , the gradient with respect to any weight parameter $w_k^\ell$ at layer $\ell$ and node $k$ satisfies the expansion for $\Delta t \ll 1$ :

$\frac{\partial J}{\partial w_k^\ell} = \frac{2\Delta t^2}{v} \sum_{j \in \mathcal{N}_k} \frac{\sigma'(C_j^{\ell-1}) X_j^{\ell-1} (X_j^N - \bar{X}_j)}{\sqrt{d_j d_k}} + \mathcal{O}(\Delta t^3)$

where $d_i = \text{deg}(i)$ and $C_j^{\ell-1} = \frac{w_j^\ell}{d_j} X_j^{\ell-1} + \sum_{p \in \mathcal{N}_j} \frac{w_p^\ell X_p^{\ell-1}}{\sqrt{d_j d_p}}$ .

To leading order in the time-step parameter $\Delta t$ , the gradient $\frac{\partial J}{\partial w_k^\ell}$ is completely independent of the total network depth $N$ . If $\Delta t$ is chosen to scale polynomially with depth as $\Delta t \sim N^{-s}$ for $s > 0$ , the gradient decays at most polynomially in $N$ , precluding exponential vanishing of gradients as layers are added.

Knowl 8 — Transductive Node Classification Performance on Homophilic and Heterophilic Graphs

data/table

GraphCON models were evaluated on transductive node classification across homophilic citation networks (Cora, Citeseer, Pubmed) and heterophilic WebKB datasets (Texas, Wisconsin, Cornell). Hyperparameters were set to $\Delta t = 1$ , with $\alpha = \gamma = 1$ on homophilic graphs and $\alpha = \gamma = 0$ on heterophilic graphs. Results represent mean accuracy $\pm$ standard deviation in % across test splits:

Dataset	Cora	Citeseer	Pubmed	Texas	Wisconsin	Cornell
Homophily level	0.81	0.74	0.80	0.11	0.21	0.30
GCN	81.5 $\pm$ 1.3	71.9 $\pm$ 1.9	77.8 $\pm$ 2.9	55.1 $\pm$ 5.2	51.8 $\pm$ 3.1	60.5 $\pm$ 5.3
GraphCON-GCN	81.9 $\pm$ 1.7	72.9 $\pm$ 2.1	78.8 $\pm$ 2.6	85.4 $\pm$ 4.2	87.8 $\pm$ 3.3	84.3 $\pm$ 4.8
GAT	81.8 $\pm$ 1.3	71.4 $\pm$ 1.9	78.7 $\pm$ 2.3	52.2 $\pm$ 6.6	49.4 $\pm$ 4.1	61.9 $\pm$ 5.1
GraphCON-GAT	83.2 $\pm$ 1.4	73.2 $\pm$ 1.8	79.5 $\pm$ 1.8	82.2 $\pm$ 4.7	85.7 $\pm$ 3.6	83.2 $\pm$ 7.0
GRAND	83.6 $\pm$ 1.0	73.4 $\pm$ 0.5	78.8 $\pm$ 1.7	-	-	-
GraphCON-Tran	84.2 $\pm$ 1.3	74.2 $\pm$ 1.7	79.4 $\pm$ 1.3	-	-	-
H2GCN	-	-	-	84.9 $\pm$ 7.2	87.7 $\pm$ 5.0	82.7 $\pm$ 5.3

GraphCON consistently outperforms the base models (GCN, GAT, and Transformer attention). On heterophilic datasets, standard GCN and GAT struggle (51.8% to 61.9%), whereas GraphCON-GCN and GraphCON-GAT reach 82.2% to 87.8%, outperforming architectures designed specifically for heterophily such as H2GCN and GCNII.

Knowl 9 — Depth Scaling and Accuracy on Molecular Property Regression and Superpixel Classification

data/table

GraphCON was evaluated on the ZINC 12k molecular property regression benchmark (constrained solubility without edge features, $\sim$ 100k parameter budget, metric: Mean Absolute Error $\downarrow$ ) and MNIST Superpixel 75 classification (metric: test accuracy in % $\uparrow$ ).

Performance comparison on ZINC 12k and MNIST Superpixel 75:

Model	ZINC Test MAE $\downarrow$	MNIST-75 Test Acc (%) $\uparrow$
ChebNet	-	75.62
GIN / GraphCON-GIN	0.41 $\pm$ 0.008 / -	97.23 / 98.53
GatedGCN / GraphCON-GatedGCN	0.42 $\pm$ 0.006 / -	97.95 / 98.27
GraphSAGE	0.41 $\pm$ 0.005	-
MoNet	0.41 $\pm$ 0.007	91.11
PNA	0.32 $\pm$ 0.032	-
DGN	0.22 $\pm$ 0.010	-
PNCNN	-	98.76
SplineCNN	-	95.22
GCN / GraphCON-GCN	0.47 $\pm$ 0.002 / 0.22 $\pm$ 0.004	88.89 / 98.68
GAT / GraphCON-GAT	0.46 $\pm$ 0.002 / 0.23 $\pm$ 0.004	96.19 / 98.91

Depth scaling across layers $N$ shows that GraphCON benefits from increased depth while standard GCN degrades:

On ZINC, GCN MAE worsens with depth (0.442 at $N=5$ , 0.463 at $N=10$ , 0.478 at $N=15$ , 0.489 at $N=20$ ), whereas GraphCON-GCN MAE decreases monotonically (0.241 at $N=5$ , 0.233 at $N=10$ , 0.228 at $N=15$ , 0.214 at $N=20$ ).
On MNIST-75, GCN accuracy drops with depth (88.09% at $N=4$ , 87.26% at $N=8$ , 86.78% at $N=16$ , 85.67% at $N=32$ ), while GraphCON-GCN accuracy improves (97.78% at $N=4$ , 98.51 $at$ N=8 $, 98.55% at$ N=16 $, 98.68% at$ N=32$) with shared parameters across all layers.

Knowl 10 — Inductive Node Classification Performance on PPI Dataset

data/table

GraphCON was evaluated on inductive multi-label node classification using the Protein-Protein Interaction (PPI) dataset. Performance is measured by micro-averaged $F_1$ score:

Model	Micro-averaged $F_1$
GraphSAGE	61.2
GAT	97.3
JKNet	97.6
VR-GCN	97.8
GCN	98.5
GeniePath	98.5
PDE-GCN	99.2
Cluster-GCN	99.4
GraphCON-GAT	99.4
GCNII	99.5
GraphCON-GCN	99.6

Wrapping standard GAT and GCN layers within the GraphCON framework improves test micro- $F_1$ score from 97.3 to 99.4 for GAT, and from 98.5 to 99.6 for GCN, matching or outperforming specialized GNN models on the inductive PPI benchmark.

Coverage note — None was omitted; all primary methodological contributions, theoretical propositions (energy conservation, oversmoothing mitigation, exploding and vanishing gradient bounds), and empirical benchmark evaluations from the paper are covered.

References

1.Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In ICML, 2021.
2.Avelar, P. H. C., Tavares, A. R., , Gori, M., and Lamb, L. C. Discrete and continuous deep residual learning over graphs. arXiv preprint, 2019.
3.Beani, D., Passaro, S., Létourneau, V., Hamilton, W., Corso, G., and Liò, P. Directional graph networks. In ICML. PMLR, 2021.
4.Belkin, M. and Niyogi, P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373–1396, 2003.
5.Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv:1711.07553, 2017.
6.Bronstein, M. M., Bruna, J., Cohen, T., and Veličković, P. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv:2104.13478, 2021.
7.Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. Spectral networks and locally connected networks on graphs. In 2nd International Conference on Learning Representations, ICLR 2014, 2014.
8.Chakrabarti, S. Dynamic personalized pagerank in entity-relation graphs. In WWW, 2007.
9.Chamberlain, B., Rowbottom, J., Eynard, D., Di Giovanni, F., Dong, X., and Bronstein, M. Beltrami flow and neural diffusion on graphs. In NeurIPS, 2021a.
10.Chamberlain, B., Rowbottom, J., Gorinova, M. I., Bronstein, M. M., Webb, S., and Rossi, E. GRAND: graph neural diffusion. In Proceedings of the 38th International Conference on Machine Learning, ICML, volume 139 of Proceedings of Machine Learning Research, pp. 1407–1418. PMLR, 2021b.
11.Chen, J., Zhu, J., and Song, L. Stochastic training of graph convolutional networks with variance reduction. arXiv:1710.10568, 2017.
12.Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In ICML. PMLR, 2020.
13.Chen, R. T., Rubanova, Y., Bettencourt, J., and Duvenaud, D. K. Neural ordinary differential equations. In NeurIPS, 2018.
14.Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsieh, C.-J. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In KDD, 2019.
15.Coifman, R. R. and Lafon, S. Diffusion maps. Applied and computational harmonic analysis, 21(1):5–30, 2006.
16.Corso, G., Cavalleri, L., Beaini, D., Liò, P., and Veličković, P. Principal neighbourhood aggregation for graph nets. arXiv:2004.05718, 2020.
17.Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844–3852, 2016.
18.Derrow-Pinion, A., She, J., Wong, D., Lange, O., Hester, T., Perez, L., Nunkesser, M., Lee, S., Guo, X., Battaglia, P. W., Gupta, V., Li, A., Xu, Z., Sanchez-Gonzalez, A., Li, Y., and Veličković, P. Traffic Prediction with Graph Neural Networks in Google Maps. 2021.
19.Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. arXiv:2003.00982, 2020.
20.Eliasof, M., Haber, E., and Treister, E. Pde-gcn: Novel architectures for graph neural networks motivated by partial differential equations. In NeurIPS, 2021.
21.Fey, M., Lenssen, J. E., Weichert, F., and Müller, H. Splinecnn: Fast geometric deep learning with continuous b-spline kernels. In CVPR, 2018.
22.Finzi, M. A., Bondesan, R., and Welling, M. Probabilistic numeric convolutional neural networks. In 9th International Conference on Learning Representations, ICLR, 2021.
23.Frasconi, P., Gori, M., and Sperduti, A. A general framework for adaptive processing of data structures. IEEE Trans. Neural Networks, 9(5):768–786, 1998.
24.Gaudelet, T., Day, B., Jamasb, A. R., Soman, J., Regep, C., Liu, G., Hayter, J. B., Vickers, R., Roberts, C., Tang, J., et al. Utilizing graph machine learning within drug discovery and development. Briefings in Bioinformatics, 22(6), 2021.
25.Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In ICML, 2017.
26.Goller, C. and Kuchler, A. Learning task-dependent distributed representations by backpropagation through structure. In ICNN, 1996.
27.Gori, M., Monfardini, G., and Scarselli, F. A new model for learning in graph domains. In IJCNN, 2005.
28.Haber, E. and Ruthotto, L. Stable architectures for deep neural networks. Inverse Problems, 34, 2018.
29.Hairer, E., Norsett, S. P., and Wanner, G. Solving ordinary differential equations I. Springer, 1987.
30.Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning on large graphs. In NeurIPS, 2017.
31.Irwin, J. J., Sterling, T., Mysinger, M. M., Bolstad, E. S., and Coleman, R. G. Zinc: a free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7):1757–1768, 2012.
32.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
33.LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. Proc. IEEE, 86(11):2278–2324, 1998.
34.Liu, Z., Chen, C., Li, L., Zhou, J., Li, X., Song, L., and Qi, Y. Geniepath: Graph neural networks with adaptive receptive paths. In AAAI, 2019.
35.McCallum, A. K., Nigam, K., Rennie, J., and Seymore, K. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127–163, 2000.
36.Monti, F., Boscaini, D., Masci, J., Rodola, E., Svoboda, J., and Bronstein, M. M. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR, 2017.
37.Namata, G., London, B., Getoor, L., Huang, B., and EDU, U. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, pp. 1, 2012.
38.Nt, H. and Maehara, T. Revisiting graph neural networks: all we have is low pass filters. arXiv:1812.08434v4, 2019.
39.Oono, K. and Suzuki, T. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
40.Page, L., Brin, S., Motwani, R., and Winograd, T. The pagerank citation ranking: Bringing order to the web. Technical report, 1999.
41.Pascanu, R., Mikolov, T., and Bengio, Y. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on Machine Learning, volume 28 of ICML’13, pp. III–1310–III–1318. JMLR.org, 2013.
42.Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-gcn: Geometric graph convolutional networks. arXiv:2002.05287, 2020.
43.Poli, M., Massaroli, S., Park, J., Yamashita, A., Asama, H., and Park, J. Graph neural ordinary differential equations. arXiv:1911.07532, 2019a.
44.Poli, M., Massaroli, S., Park, J., Yamashita, A., Asama, H., and Park, J. Graph neural ordinary differential equations. pp. 6571–6583, 2019b.
45.Rong, Y., Huang, W., Xu, T., and Huang, J. Towards deep graph convolutional networks on node classification. In ICLR, 2020.
46.Rusch, T. K. and Mishra, S. Coupled oscillatory recurrent neural network (cornn): An accurate and (gradient) stable architecture for learning long time dependencies. In ICLR, 2021a.
47.Rusch, T. K. and Mishra, S. Unicornn: A recurrent model for learning very long time dependencies. In ICML, 2021b.
48.Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Trans. Neural Networks, 20(1):61–80, 2008.
49.Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T. Collective classification in network data. AI Magazine, 29(3):93–93, 2008.
50.Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv:1811.05868, 2018.
51.Shlomi, J., Battaglia, P., and Vlimant, J.-R. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
52.Sperduti, A. Encoding labeled graphs by labeling RAAM. In NIPS, 1994.
53.Sperduti, A. and Starita, A. Supervised neural networks for the classification of structures. IEEE Trans. Neural Networks, 8(3):714–735, 1997.
54.Stiefel, K. M. and Ermentrout, G. B. Neurons as oscillators. Journal of Neurophysiology, 116:2950–2960, 2016.
55.Strogatz, S. Nonlinear Dynamics and Chaos. Westview, Boulder CO, 2015.
56.Topping, J., Di Giovanni, F., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv:2111.14522, 2021.
57.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. In NeurIPS, 2017.
58.Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In 6th International Conference on Learning Representations, ICLR, 2018.
59.Wiggins, S. Introduction to nonlinear dynamical systems and chaos. Springer, 2003.
60.Xhonneux, L.-P., Qu, M., and Tang, J. Continuous graph neural networks. In ICML. PMLR, 2020a.
61.Xhonneux, L.-p. A. C., Qu, M., and Tang, J. Continuous graph neural networks. In ICML, 2020b.
62.Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv:1810.00826, 2018a.
63.Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In ICML. PMLR, 2018b.
64.Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., and Leskovec, J. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018.
65.Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., Wang, L., , Li, C., and Sun, M. Graph neural networks: a review of methods and applications. arXiv:1812.08434v4, 2019.
66.Zhuang, J., Dvornek, N., Li, X., and Duncan, J. S. Ordinary differential equations on graph networks. Technical Report, 2020.
67.Zitnik, M. and Leskovec, J. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33 (14):i190–i198, 2017.

Citation

MLA

Rusch, T. K., et al. “Graph-Coupled Oscillator Networks”. International Conference on Machine Learning, vol. 162, 2022, pp. 18888–909, https://proceedings.mlr.press/v162/rusch22a.html.

APA

Rusch, T. K., Chamberlain, B., Rowbottom, J., Mishra, S., & Bronstein, M. (2022). Graph-Coupled Oscillator Networks. International Conference on Machine Learning, 162, 18888–18909. https://proceedings.mlr.press/v162/rusch22a.html

Chicago

Rusch, T. K., B. Chamberlain, J. Rowbottom, S. Mishra, and M. Bronstein. 2022. “Graph-Coupled Oscillator Networks”. International Conference on Machine Learning 162: 18888–909. https://proceedings.mlr.press/v162/rusch22a.html.

Harvard

Rusch, T.K. et al. (2022) “Graph-Coupled Oscillator Networks”, International Conference on Machine Learning. PMLR, pp. 18888–18909. Available at: https://proceedings.mlr.press/v162/rusch22a.html.

Vancouver

1. Rusch TK, Chamberlain B, Rowbottom J, Mishra S, Bronstein M (2022) Graph-Coupled Oscillator Networks. In: International Conference on Machine Learning. PMLR, pp 18888–18909

BibTeX

@InProceedings{pmlr-v162-rusch22a,
  title = 	 {Graph-Coupled Oscillator Networks},
  author =       {Rusch, T. Konstantin and Chamberlain, Ben and Rowbottom, James and Mishra, Siddhartha and Bronstein, Michael},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {18888--18909},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/rusch22a/rusch22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/rusch22a.html},
  abstract = 	 {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.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Graph-Coupled Oscillator Networks

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Graph-Coupled Oscillator Network (GraphCON) Framework

Knowl 2 — Recovery of Standard Message-Passing GNNs as Steady States of GraphCON

Knowl 3 — Energy Conservation in Undamped Linear GraphCON

Knowl 4 — Dynamical Characterization of GNN Oversmoothing via Fixed-Point Stability

Knowl 5 — Mitigation of Oversmoothing via Instability of Zero-Dirichlet Energy Fixed Points

Knowl 6 — Mitigation of Exploding Gradients in Deep GraphCON-GCN

Knowl 7 — Mitigation of Vanishing Gradients in Deep GraphCON-GCN

Knowl 8 — Transductive Node Classification Performance on Homophilic and Heterophilic Graphs

Knowl 9 — Depth Scaling and Accuracy on Molecular Property Regression and Superpixel Classification

Knowl 10 — Inductive Node Classification Performance on PPI Dataset

References

Citation

BibTeX

Source Code

Access the Paper