Research map / Graph learning / GNN architectures

Graph neural networks and non-commuting operators

NeurIPS 2024 · Graph learning › GNN architectures · approach: Simple and scalable GNNs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends GNNs to multiple non-commuting graph shift operators (graph-tuple NNs), proves stability and a universal transferability theorem via graphon-tuple limits, and proposes a penalty-based training procedure enforcing stability.

Problem

GNNs assume a single graph, but multimodal settings have several graphs sharing one vertex set whose shift operators do not commute; stability and transferability of such networks are not understood, and prior bounds (Hilbert-Schmidt based) fail to transfer on Erdos-Renyi-type sequences.

Approach

Replace univariate polynomial graph filters with non-commutative polynomials in k shift operators, bound stability with block operator norms and expansion constants (sums of absolute coefficients), define graphon-tuple limits, and prove universal transferability under operator-norm convergence; constrain expansion constants during training to guarantee stability.

Key results

• Adding stability constraints barely changes prediction: test R^2 0.6866 for GtNN vs 0.6543 for stable GtNN on the synthetic task.
• Universal transferability: every graphon-tuple neural network transfers over convergent graph-tuple sequences in operator norm, with transferability error going to zero as graph size grows.
• On MovieLens 100k, a two-graph GtNN (2ONN) is compared against a GNN on the best single graph across ridge regularization values.

Measured effects reported in the paper

Surprising findings

• The Hilbert-Schmidt norm is not topologically equivalent to the operator norm on graphons: Erdos-Renyi graph sequences do not converge to the graphon in HS norm, so HS-based transferability results do not apply even to Erdos-Renyi graphs.

Limitations

• Transferability bounds rely on operator-norm convergence of graph tuples and equispaced vertex sets; interpolation identity fails for non-equispaced points.
• Experiments are small-scale: synthetic circulant graphs and MovieLens 100k with a single-layer model.
• Stability training uses a penalty method with a fixed large penalty coefficient, so constraints are only approximately enforced.

Experimental setup

Datasets: MovieLens 100k synthetic weighted circulant graphs

Benchmarks: MovieLens 100k

Metrics: R squared mean squared error stability bound tightness output perturbation norm

Baselines: standard GNN on best single graph standard GtNN (unconstrained)

Builds on: graphon transferability theory (Ruiz et al.) algebraic neural networks (Parada-Mayorga et al.) graph convolutional networks

Closest papers by meaning

• Graphon Neural Networks and the Transferability of Graph Neural Networks (NeurIPS 2020 · similarity 0.92)
• Limits, approximation and size transferability for GNNs on sparse graphs via graphops (NeurIPS 2023 · similarity 0.90)
• Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.89)
• What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.89)
• Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.88)