Source-linked AI summary
Graph Neural Networks: Architectures, Stability and Transferability
Luana Ruiz, Fernando Gama, Alejandro Ribeiro
TL;DR
The paper asks why GNNs perform well on graph-supported signals and transfer across graphs of different sizes. It analyzes graph filters and nonlinear layered extensions through permutation equivariance, perturbation stability, and graphon limits. The analyses show robust transferability and explain how nonlinearities support discriminability while preserving stability.
Problem
The paper investigates why graph filters and GNNs outperform generic parametrizations and why GNNs transfer to networks with different numbers of nodes.
Method
The paper analyzes GNNs as nonlinear layered extensions of graph filters, studying permutation equivariance, stability under graph perturbations, and convergence toward graphon neural networks.
Results
GNNs are stable under relative perturbations, use pointwise nonlinearities to retain discriminability, and exhibit transferability across graphs with different numbers of nodes.
Takeaways & Limitations
Pointwise nonlinearities help explain GNN gains by enabling discrimination while retaining robustness, and graphon convergence supports execution across graphs of different sizes.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) are information processing architectures for signals supported on graphs. They are presented here as generalizations of convolutional neural networks (CNNs) in which individual layers contain banks of graph convolutional filters instead of banks of classical convolutional filters. Otherwise, GNNs operate as CNNs. Filters are composed with pointwise nonlinearities and stacked in layers. It is shown that GNN architectures exhibit equivariance to permutation and stability to graph deformations. These properties help explain the good performance of GNNs that can be observed empirically. It is also shown that if graphs converge to a limit object, a graphon, GNNs converge to a corresponding limit object, a graphon neural network. This convergence justifies the transferability of GNNs across networks with different number of nodes. Concepts are illustrated by the application of GNNs to recommendation systems, decentralized collaborative control, and wireless communication networks.
I. INTRODUCTION
GNNs adapt convolutional processing to graph-supported signals while leveraging graph structure. The paper analyzes equivariance, stability, and transferability to explain their generalization potential and empirical performance.
- Motivation: GNNs parameterize learning problems so relationships among graph-supported signal components are explicitly leveraged.They are presented as graph adaptations of convolutional filters and CNNs.
- Empirical motivation: Graph filters and GNNs outperform arbitrary linear and fully connected parametrizations when sufficient training data is available.In recommendation systems, graph filters improve rating estimates over arbitrary linear maps, while GNNs improve over fully connected networks.
- Empirical motivation: GNNs predict ratings better than graph filters and can execute on graphs with more nodes than those used during training.These observations motivate analyses of nonlinear processing and transferability across graph sizes.
- Theoretical analyses: Graph filters and GNNs are permutation equivariant, while GNNs provide a better discriminability–stability tradeoff under graph perturbations.These properties support analogous operations on structurally similar neighborhoods and robustness to nonidentical local structures.
- Theoretical analyses: As graphs converge to graphons, GNN outputs converge to graphon neural-network outputs, supporting transfer across networks with different numbers of nodes.The paper also relates these results to graphon filters and neural networks.
- Scope: The paper is tutorial in focus and does not discuss training, including optimization techniques, objectives, or graph-filter realization.Those choices are described as important for realizing the generalization potential implied by the theory.
A. Learning Parametrizations
The paper frames learning as selecting a function class that maps graph signals to outputs and illustrates this choice through collaborative filtering. The recommendation setup constructs graph-based inputs and targets for predicting withheld ratings.
- Learning parametrizations: Empirical risk minimization selects a parametrized function Φ(x; H) rather than searching over all possible functions.The parametrization determines both the admissible function class and its generalization from observed to unobserved signals.
- Learning parametrizations: Linear functions, neural networks, graph filters, and GNNs are alternative learning parametrizations for the same input-output problem.The system designer’s principal choice is the class of functions spanned by H.
- Recommendation systems: Collaborative filtering builds a product-similarity graph and represents each customer’s ratings as a graph signal on product nodes.Edges encode product similarity derived from customers’ rating histories.
- Recommendation systems: Training pairs hide one observed rating in the target vector and retain the customer’s other ratings as the input signal.This construction is repeated for every rated product and customer.
- Recommendation systems: The loss compares predicted and target ratings for the withheld product component.The canonical basis vector extracts the relevant output component for this comparison.
- Recommendation systems: At execution, the learned map predicts unrated products from rated-product signals, with success depending on the chosen parametrization for unseen inputs.Inputs encountered during training can be predicted accurately by construction, whereas novel signals depend on the learned function class.
III. GRAPH NEURAL NETWORKS
Graph filters process graph signals through polynomials of graph-shift operators, while GNNs extend them through stacked nonlinear layers. Their permutation equivariance supports generalization across relabeled or structurally similar graph regions.
- Graph Filters: Graph filters are polynomial transformations of a graph-shift operator and propagate information through adjacent nodes via a diffusion sequence.The diffusion sequence recursively applies the shift operator, making graph-filter processing local.
- Permutation Equivariance: Permutation equivariance makes graph-filter processing independent of node labeling and preserves consistent outputs under graph and signal permutations.For a permutation matrix P, Φ(Px; h, PSPT) = PΦ(x; h, S).
- GNN Construction: A graph perceptron combines a graph convolutional filter with a pointwise nonlinearity, preserving locality and permutation equivariance.Stacking these operations yields multilayer GNNs whose output is produced by recursively applying filter-and-nonlinearity layers.
- Generalization: Graph filters can generalize predictions across symmetric graph neighborhoods where arbitrary linear transformations may not.In the recommendation example, analogous neighborhoods allow prediction at node 6 from training information associated with node 3.
- Generalization: Near permutation symmetries retain some predictive transfer, although their generalization is weaker than under perfect symmetry.The continuity of graph-filter operations extends some predictive power from one approximately symmetric configuration to another.
A. Graph Perceptrons
Graph perceptrons apply pointwise nonlinearities after graph filtering, and multilayer GNNs compose these operations recursively. Because both components preserve permutation equivariance, the resulting network does as well.
- Graph Perceptrons: A graph perceptron applies a pointwise nonlinearity independently to each component after graph filtering.The graph filter mixes signal components, while the nonlinearity processes them element-wise.
- Graph Perceptrons: Graph perceptrons retain the locality and permutation equivariance of graph convolutional filters.The nonlinearity does not mix signal components, so it preserves these structural properties.
- Multilayer GNNs: Multilayer GNNs are formed by composing graph perceptrons so that each layer output becomes the next layer’s input.The network recursively applies filtering and pointwise nonlinearities across L layers, producing xL as the output.
- Training: GNN filter coefficients are learned by minimizing a training loss for a fixed graph-shift operator.Optimization is performed over the filter matrix H while S remains given.
- Permutation Equivariance: Since each perceptron is permutation equivariant, their composition—the whole GNN—is also permutation equivariant.This inheritance follows from composing equivariant layer operators.
C. Multiple Feature Networks
Multiple-feature GNNs use filter banks to transform several input graph signals into several output features at each layer. This increases representation power while preserving permutation equivariance and local implementation.
- Feature Representation: The feature matrix Xl ∈ Rn×Fl stores Fl graph signals, with each column representing one feature.The input and output feature counts can vary by layer.
- Multiple-Feature Layers: Multiple-feature GNN layers use MIMO graph filters that accept Fl−1 input graph signals and produce Fl output graph signals.Each layer contains Fl−1 × Fl filters represented by coefficient matrices Hlk.
- Layer Structure: Multiple-feature layers apply pointwise nonlinearities after filter-bank processing, retaining the layered GNN structure.The intermediate feature matrix Ul is transformed into the layer output through a pointwise nonlinearity.
- Permutation Equivariance: Each multiple-feature GNN layer is permutation equivariant, so the complete network is permutation equivariant by composition.Filter banks are equivariant, and pointwise nonlinearities do not mix signal components.
- Local Implementation: The diffusion-sequence form gives MIMO graph filters a local implementation useful for decentralized collaborative systems.Locality follows from recursively propagating feature signals through graph shifts.
D. Recommendation System Experiments
Recommendation experiments show that graph-structured parametrizations improve rating prediction, while GNN nonlinearities provide additional gains and support transfer across related graphs. The stability analysis explains these gains through permutation equivariance and perturbation stability, while identifying limits of the bound and perturbation model.
- Prediction performance: The 2-layer multi-feature GNN achieves the best average RMSE across 10 data splits, while graph filters outperform generic linear and fully connected neural parametrizations.The graph filter uses significantly fewer parameters than the generic linear model, and the FCNN has worse RMSE than the graph-based models despite having about 10^5 parameters.
- Mechanisms: Permutation equivariance lets graph filters and GNNs exploit graph structure to generalize better to unseen signals on the same graph.Each GNN layer combines permutation-equivariant filter banks with pointwise nonlinearities, so the composed network remains permutation equivariant.
- Mechanisms: Nonlinearities give GNNs a better stability-discriminability tradeoff than graph filters by enabling simultaneous stability and discrimination.The paper attributes this effect to a demodulating action in the frequency domain.
- Stability analysis: Integral Lipschitz filters and the GNNs built from them have output changes bounded proportionally to relative graph-support perturbations.The bound is linear in perturbation size and applies to graphs with the same number of nodes, establishing Lipschitz continuity with respect to the support.
- Stability analysis: The stability bound depends on eigenvector misalignment, whose general bound can be conservative, while absolute perturbations may miss important changes in graph structure.The paper therefore focuses on relative perturbations, which tie edge-weight changes to local graph structure.
B. Discussion and insights
Integral Lipschitz filters provide stability under graph perturbations but lose discriminability at high eigenvalues. GNN nonlinearities spread spectral information, allowing subsequent stable filters to distinguish signals that linear stable filters cannot.
- Integral Lipschitz filters are stable under relative graph perturbations but cannot discriminate information at high eigenvalues.Their discriminability can be arbitrarily high at low eigenvalues but vanishes at high eigenvalues.
- For an edge dilation, Lipschitz filters can produce large output changes at large eigenvalues even when the perturbation is small.The bound |h(λ̂_i) − h(λ_i)| ≤ Cελ_i grows with λ_i.
- The stability–discriminability trade-off limits integral Lipschitz filters when relevant signal information lies outside the low-eigenvalue spectrum.Lower C improves stability, while larger C extends discrimination toward higher eigenvalues without changing low-eigenvalue discriminability.
- Pointwise nonlinearities spread signal information throughout the spectrum, creating frequency content where none existed before.The effect is described as analogous to frequency demodulation.
- After nonlinear spectral spreading, integral Lipschitz filters can discriminate signals using low-eigenvalue content while retaining stability.The paper illustrates this with signals x = v_n and y = v_n−1, whose nonlinear transformations have different frequency content.
V. TRANSFERABILITY OF GNNS
Transferability treats replacing a graph with another graph in the same structurally similar family as a form of stability. The paper studies transferability of graph filters and GNNs across graph families represented by graphons.
- Different instances of a network problem may produce structurally similar graphs, including graphs with different numbers of nodes.This motivates studying graph families and whether processing architectures transfer within them.
- Transferability allows systems to be reused across related graphs without retraining or redesigning.
- From the architecture perspective, transferability is a type of stability because it replaces the graph with another graph in the same family.
- The analysis focuses on transferability of graph filters and GNNs within families of undirected graphs identified by graphons.The results assume the multi-layer, single-feature architecture described earlier.
A. Graphons and graph families
Graphons are limit objects representing structurally related undirected graph families. Graph convergence is characterized through convergence of motif densities, enabling graph sequences of different sizes to be associated with graphons.
- A graphon is a bounded, symmetric, measurable function W: [0, 1]^2 → [0, 1] representing an undirected graph with an uncountable number of nodes.The exponential graphon assigns edge weights according to the distance between node locations on the unit interval.
- A graph sequence converges when the densities of specified finite motifs converge.Motif densities are defined through the relative frequency of adjacency-preserving homomorphisms.
- Graph convergence to a graphon is defined by convergence of motif homomorphism densities for every finite, unweighted, undirected graph.
- Every graphon is the limit of a convergent graph sequence, and every convergent graph sequence converges to a graphon.This associates graphons with graph families of different sizes that share structural similarities.
- Deterministic graphs formed by regularly partitioning the unit interval provide graph sequences that converge to the generating graphon.The stated convergence mode also permits more general graph sequences.
B. Graphon filters
Graphon filters extend graph filtering to graphon signals through an integral-operator shift and spectral representations. Their shared coefficients with graph filters enable filter design on graphons and comparison across graph realizations of different sizes.
- Graphon signals are L2 functions on [0, 1] that can be transformed by graphon operations parameterized by an integral-operator shift.
- The graphon shift operator is self-adjoint and Hilbert–Schmidt, supporting a spectral basis of graphon eigenvalues and eigenfunctions.
- Graphon convolutions are shift-and-sum operations whose shift is implemented by the graphon shift operator.
- The spectral representation of a graphon filter depends only on graphon eigenvalues and filter coefficients.The polynomial representation is h(λ) = Σ_k h_k λ^k.
- Using the same coefficients for graphon and graph filters makes graphon filters generating models for filters on graph realizations.
- Graphon-generated filters decouple filter design from a specific graph realization and support comparison across graphs of different sizes.
2) Approximating graph filters with graphon filters:
Graph filters on graphs approximating a graphon converge toward the corresponding graphon filter, with error controlled by graph, filter, and signal regularity. Convergence requires filters to be constant near zero, where eigenvalue matching is difficult.
- Approximation framework: Graph filters instantiated from a graphon filter increasingly approximate the graphon filter as the graph sequence converges.Theorem 3 compares the discrete output with the graphon filter induced by that output.
- Approximation framework: The c-band cardinality B_nc counts graphon-induced eigenvalues with absolute value at least c, while δ_nc measures the corresponding eigenvalue margin.These quantities enter the transferability bound.
- Approximation conditions: Under Lipschitz assumptions on the graphon, filter response, and signal, a filter constant for |λ| < c admits an asymptotic approximation bound.The filter must also be non-amplifying through the stated spectral-response assumption.
- Approximation error: The error contains a term proportional to √A1(A2 + πB_nc/δ_nc)n^-0.5 and a fixed signal-discretization term.For large n, the first term dominates, making the transferability constant central to approximation quality.
- Approximation error: The transferability constant decreases asymptotically with n but worsens with graphon variability, filter-response variability, passband length, and small eigengaps.Eigenvalues near zero are difficult to match because graph and graphon eigenvalues converge while graphon eigenvalues accumulate there.
C. Graph filter transferability
Graph filters transfer across graphs in the same graphon family because their outputs approach a common graphon-filter limit. The transfer guarantee depends on graph sizes and on keeping the spectral passband sufficiently controlled.
- Transfer guarantee: Theorem 4 bounds the difference between identical graph filters applied to graphs of different sizes from the same graphon family.The shared spectral response must be constant for |λ| < c under the stated assumptions.
- Transfer guarantee: Graphon eigenvalues are approximated by graph eigenvalues as graph size grows, while graphon eigenvalues accumulate at zero.This explains why small-eigenvalue matching is difficult.
- Scalability: For sufficiently large graphs, a filter designed for one graph can transfer to another with an error bound that decreases asymptotically with both graph sizes.The result also supports applying the filter to larger graphs beyond a specified error threshold.
- Graphon neural networks: A graphon neural network is the limit architecture of a GNN defined on a convergent graph sequence, with the input signal at the first layer and the final layer producing the output.Its filter coefficients are grouped in H and the output is Y = X_L.
- Graphon neural networks: The same parameters H can generate GNNs on graphs of different sizes, disconnecting the architecture from any single fixed graph.Changing the graph allows scaling and adds a further degree of freedom alongside optimizing H.
- GNN limits: Under normalized Lipschitz activations and the graphon assumptions, GNN outputs approximate WNN outputs with an error that decreases asymptotically with graph size.The bound scales with the number of layers and includes a fixed signal-discretization term.
E. GNN transferability
GNNs are transferable between different-sized graphs in the same graphon family. Their bound improves with graph sizes, while nonlinearities partially mitigate the transferability–discriminability trade-off.
- Transfer guarantee: Theorem 6 establishes transferability for L-layer GNNs applied to different-sized graphs generated from the same graphon.The convolutional response is required to be constant for |λ| < c under the stated assumptions.
- Implications: A trained GNN can be transferred to another sufficiently large graph without retraining, with an error bound inversely related to both graph sizes.This supports replicating the same task across multiple networks and training on smaller graphs than those used in deployment.
- Error bound: The approximation error combines a transferability term proportional to L^F L−1√A1(A2 + πB_c/δ_c)(n_1^-0.5 + n_2^-0.5) with a fixed signal term.Both terms decrease asymptotically with graph sizes.
- Error bound: For asymptotic transfer, the number of eigenvalues in [c, 1] must satisfy B_c < √n_1.This restriction prevents mismatching eigenvalues when transferring between graphs.
- Nonlinearities: Nonlinearities partially overcome the transferability–discriminability trade-off by scattering spectral components associated with small λ toward the middle of the spectrum.This extends the role nonlinearities play beyond the linear-filter transferability bound.
- Flocking application: In decentralized flocking, offline-trained GNNs were evaluated on networks differing from those observed during training, and numerical results corroborated transferability.The task requires cohesive motion without collisions under local information constraints.
VII. WIRELESS COMMUNICATION NETWORKS
In wireless networks, GNNs parameterize power allocation as a function of the random channel state. REGNN training outperforms standard heuristics for both tested network sizes, while fully connected networks fail to train at the larger size.
- Problem formulation: The wireless objective maximizes expected sum rate over fading-channel realizations, yielding an optimal power allocation for each channel state.The expectation defines long-term performance over realizations of S.
- REGNN formulation: A random-edge GNN represents power allocation as p(S) = Φ(x; H, S), treating the shift operator S as an input and setting x = 1.This parametrization is called a REGNN.
- Results: For 20 communicating pairs, the REGNN and fully connected network outperform the heuristics and attain similar performance.The REGNN uses fewer parameters.
- Results: For 50 communicating pairs, the REGNN still outperforms standard heuristics, while the fully connected network fails to train.The comparison includes WMMSE and equal-power heuristics.
- Conclusion: The paper presents GNNs as graph-filter extensions whose empirical performance is supported by equivariance, stability, and transferability analyses.The conclusion also states that GNNs show more robust transferability than linear graph filters.
- Scope: The paper leaves perturbations of graph-shift eigenvectors and several alternative graph limits and GNN architectures for future study.These are identified as remaining gaps in the conclusion.