Source-linked AI summary
Graphon Neural Networks and the Transferability of Graph Neural Networks
Luana Ruiz, Luiz F. O. Chamon, Alejandro Ribeiro
TL;DR
GNN parameters are graph-size independent, raising the question of when learned models transfer across related graphs. The paper introduces graphon neural networks as limit objects, proves convergence and transferability bounds for deterministic graphon-generated graphs, and identifies a trade-off between transferability and discriminability.
Problem
The paper asks when a GNN can preserve performance across graphs of different sizes or changing network structure without retraining.
Method
The paper introduces graphon neural networks as limit objects and uses them to approximate GNNs and analyze transferability between deterministic graphs generated from a common graphon.
Results
Under mild conditions, the output difference between fixed-parameter GNNs on graphon-generated graphs decreases at O(n^-0.5), with bandlimited filters supporting the bound.
Takeaways & Limitations
Transferability improves asymptotically for small passing bands, revealing a trade-off between representation power and stability in deterministic graphon-based GNNs.
Takeaways & Limitations
The transferability bound is dominated by the smaller graph, so it may be weak when one graph is small; the theory also assumes deterministic graphon-generated graphs.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) rely on graph convolutions to extract local features from network data. These graph convolutions combine information from adjacent nodes using coefficients that are shared across all nodes. Since these coefficients are shared and do not depend on the graph, one can envision using the same coefficients to define a GNN on another graph. This motivates analyzing the transferability of GNNs across graphs. In this paper we introduce graphon NNs as limit objects of GNNs and prove a bound on the difference between the output of a GNN and its limit graphon-NN. This bound vanishes with growing number of nodes if the graph convolutional filters are bandlimited in the graph spectral domain. This result establishes a tradeoff between discriminability and transferability of GNNs.
1 Introduction
GNN parameters are independent of graph size, motivating transfer across related graphs without retraining. The paper uses graphons to characterize graph families and proves transferability for deterministic graphs generated from a common graphon.
- Motivation: GNN parameters do not depend on the number of graph nodes, so learned models can be applied to other graphs by replacing the graph shift.This motivates asking when performance is preserved across graphs.
- Motivation: Transferability is useful both for applying a trained model to a similar graph and for handling networks whose size changes over time.The latter includes growing-user-network recommender systems.
- Graphon framework: Graphons represent families of graphs whose structural motif densities are preserved in the limit.They are bounded symmetric kernels that can also generate deterministic graphs.
- Main result: Theorem 2 shows that fixed-parameter GNNs are transferable between deterministic graphs with different sizes obtained from the same graphon.The informal theorem bounds the output difference under mild conditions.
- Implications: The result identifies a trade-off between transferability and discriminability linked to restrictions on graph convolutional filter passing bands.The proof uses graphon neural networks as theoretical limit objects and generating models for graph-based architectures.
- Scope: The paper studies deterministic graphon-instantiated graphs and does not cover stochastic graphon samples or sparser graphs modeled by graphings.Two numerical experiments illustrate transferability, and proofs and additional experiments are deferred to supplementary material.
2 Related Work
Prior work studies graphon limits, GNN stability, and transferability, but the paper distinguishes its graphon-based varying-size regime from related settings.
- Graphon research: Graphons and convergent graph sequences have been studied in mathematics and applied to statistics, game theory, network science, and control.Recent work also uses graphons to study network information processing in the limit.
- GNN transferability: Stability analyses of GNNs typically address graph perturbations, while some work studies random-graph stability and transferability as graph size grows.The cited transferability work treats graphs as discretizations of generic topological spaces, yielding a different asymptotic regime.
3 Preliminary Definitions
The paper defines GNNs through graph shifts and spectral graph convolutions, then introduces graphons as limit objects with analogous convolutional operators and data representations.
- Graph neural networks: A GNN layer combines graph convolutional filters with a nonlinear activation function to learn representations of network data.Its parameters are shared independently of graph size, enabling inference on another graph after replacing the graph shift.
- Graph neural networks: A graph is represented by nodes, weighted edges, and a graph shift operator encoding adjacency or another network structure.The paper uses the adjacency matrix as its graph shift operator, while also noting degree and Laplacian alternatives.
- Graph convolution: The graph shift diffuses node data to neighboring nodes, and graph convolution forms a weighted sum of shifts across at most K−1 hops.The coefficients are the filter parameters.
- Graph convolution: For undirected graphs, graph convolution has a spectral representation h(λ)=Σ_k h_kλ^k determined by filter coefficients and graph eigenvalues.Diagonalizing the symmetric shift operator yields the graph spectral basis.
- GNN architecture: A GNN maps input graph signals through L layers, with feature counts F_ℓ describing the channels between successive layers.The architecture can be written compactly as y=Φ(H;S;x), grouping learnable parameters in H.
- Graphons: A graphon is a bounded symmetric measurable kernel on [0,1]^2 that acts as an undirected graph with an uncountable node set.Graph sequences can converge to graphons, which thereby identify graph families across sizes.
- Graphon limits: Graph motif density characterizes convergence when the density of homomorphisms from every finite motif converges to its graphon counterpart.The density t(F,G) measures the relative frequency of motif F in graph G.
- Graphon limits: The paper constructs deterministic graph sequences by evaluating a graphon at regularly spaced points and assigning kernel values as edge weights.These sequences satisfy the motif-density convergence condition.
4 Graphon Neural Networks
Graphon neural networks (WNNs) provide graph-independent limit architectures from which GNNs can be instantiated on deterministic graphs. The resulting GNN outputs approximate the WNN with an error that decays as O(n^-0.5) under spectral and filter conditions.
- Graphon neural networks: A WNN is a composition of graphon convolutions and nonlinear activations, with graphon-agnostic filter parameters H.Its output is represented as Y = Φ(H; W; X).
- WNNs as generating models: GNNs can be instantiated from WNNs by evaluating the graphon and graphon signal at node locations, while sharing the same parameters H.For deterministic graphs, [S_n]ij = W(ui, uj) and [x_n]i = X(ui).
- WNNs as generating models: This construction treats graphs as tunable model components, enabling scalable adaptation when the graph is uncertain but its graphon is known.The graphon-induced construction permits changing G_n in addition to optimizing H.
- Comparing WNNs and GNNs: An induced WNN Φ(H; W_n; X_n) represents a GNN through piecewise-constant graphon and signal functions, enabling direct comparison between their outputs.The partition of [0, 1] uses intervals I_i = [(i − 1)/n, i/n].
- Approximation guarantees: The approximation error between the induced WNN and the original WNN is controlled by a transferability term and a fixed signal-variability term, both decaying as O(n^-0.5).The transferability term depends on graphon and GNN parameters, while the fixed term depends on graphon signal variability.
- Approximation guarantees: Asymptotic convergence requires limited filter variability and n_c ≪ n, specifically n_c < √n, with eigenvalue convergence supporting the condition.Filter variability is controlled by the Lipschitz constant A2 and the band length [c, 1].
5 Transferability of Graph Neural Networks
The paper proves transferability of fixed-parameter GNNs between deterministic graphs of different sizes generated from the same graphon. The guarantee depends on filter design, graph size, graphon variability, and network architecture, revealing a transferability–discriminability trade-off.
- Transferability: GNNs with fixed parameters can transfer between deterministic graphs of different sizes obtained from the same graphon, with performance guarantees.The theorem compares the induced graphon neural networks through an L2 output bound.
- Filter design: Filters constant for |λ| < c impose the spectral restriction underlying the transferability guarantee.The theorem assumes graph convolutions are constant below the cutoff c.
- Transferability: The transferability bound decays as O(1/√min n1, n2), so it is dominated by the smaller graph.A small source or target graph can therefore weaken the guarantee even when the other graph is large.
- Transferability: The bound depends on graphon variability, signal mismatch, filter parameters, depth, and width.The transferability constant reflects graphon variability and the GNN architecture, while the fixed error term measures graph-signal differences.
- Filter design: Smaller c improves discriminability but worsens transferability because filters can distinguish more eigenvalues while the transfer error increases.For |λ| ∈ [c, 1], filters need not be constant; nonlinearities make the trade-off less rigid than for graph filters.
6 Numerical Results
Numerical experiments evaluate transferability in movie recommendation and citation-network node classification. The experiments transfer models trained on smaller subnetworks to larger networks and compare their test performance using relative error or accuracy differences.
- Experimental settings: The experiments illustrate GNN transferability in graph-signal classification and node classification.The settings are MovieLens movie recommendation and the Cora citation network.
- Movie recommendation: The MovieLens experiment predicts ratings for user 405 using a one-layer GNN trained on subnetworks of 100 to 900 users.User 405 has rated 737 movies, and the model uses 32 features with a five-class readout.
- Movie recommendation: MovieLens transferability is measured by the relative difference between test RMSEs on the training subnetwork and the full user network.The reported comparison averages relative RMSE differences over random splits.
- Cora citation network: The Cora experiment trains one-layer GNNs on citation subgraphs with 271, 542, or 1354 nodes and transfers them to the full 2708-node network.The task classifies publications into seven classes using the prescribed train, validation, and test split.
- Cora citation network: As the Cora subgraph size increases, the relative accuracy difference decreases, indicating the asymptotic behavior predicted by Theorem 2.The accompanying table reports average test accuracy on subnetworks and the full network, together with average relative accuracy difference.
7 Conclusions
The paper introduces graphon neural networks as generating models and limit objects for GNNs on deterministic graph sequences. It proves asymptotic approximation and transferability, while identifying a trade-off between representation power and stability.
- Contributions: Graphon neural networks generate GNNs on deterministic graphs evaluated from a graphon.They also provide the limit objects that organize the approximation analysis.
- Contributions: The approximation error between GNNs and their graphon neural networks decays asymptotically with O(n^-0.5).This approximation result supports the transferability theorem for deterministic graphs associated with the same graphon.
- Conclusions: For graph convolutional filters with small passing bands, GNN transferability increases asymptotically with O(n^-0.5).The conclusion frames this as a trade-off between representation power and stability.
- Conclusions: Numerical experiments demonstrate transferability in graph-signal classification and node classification.The paper identifies extension to stochastic graphs sampled from graphons as future research.
Broader Impact
GNN transferability can allow models to be replicated across different networks without redesign, potentially reducing data and computational requirements. Because the approach uses standard supervised training, it may inherit biases from data collection.
- Implications: Replicating learned models across different networks without redesign can potentially save data and computational resources.This is presented as an implication of GNN transferability.
- Caveat: Using standard supervised training may carry biases such as data collection bias into the transferred models.The paper identifies this as a limitation of its training approach.
Proof of Theorem 1
The proof bounds the difference between graphon convolutions and their graph-induced approximations, then extends this bound through GNN layers to obtain Theorem 1.
- Graphon-to-graph approximation: Graphon convolutions are treated as generative models for graph convolutions, with graph-induced signals and kernels represented on partitions of [0, 1].The construction defines W_n and X_n piecewise over intervals I_i and generates y_n = H_n(S_n)x_n from the graphon convolution.
- Graphon-to-graph approximation: Theorem 3 establishes approximation bounds for graphon convolutions when filters are constant for |λ| < c.The proof handles filters vanishing below the cutoff and decomposes constant-low-frequency filters into a Lipschitz component and a bandpass component.
- Bounding the convolution error: The approximation analysis uses Lipschitz graphons and signals, spectral separation, eigenvalue comparisons, and Hilbert-Schmidt norm bounds.Propositions 1–4 control graphon discretization, spectral perturbations, signal discretization, and eigenvalue differences.
- Extending to GNNs: When the graph signal equals its graphon-induced representation, the signal-discretization terms vanish, yielding the theorem’s second bound.The proof explicitly sets X = X_n so the corresponding terms in the convolution approximation disappear.
- Extending to GNNs: The GNN-level proof applies triangle and Cauchy-Schwarz inequalities layer by layer, using normalized-Lipschitz nonlinearities and bounded graphon filters.The resulting recursion is evaluated at the final layer after substituting the initial conditions and feature dimensions.
Proof of Theorem 2
Theorem 2 compares the outputs of the same GNN on two deterministic graphs generated from one graphon by applying Theorem 1 to both graph sizes.
- Triangle-inequality reduction: The proof decomposes the output difference between the two graphs through the common graphon neural network using the triangle inequality.The decomposition is ∥Y_n1 − Y_n2∥L2 ≤ ∥Y_n1 − Y∥L2 + ∥Y − Y_n2∥L2.
- Triangle-inequality reduction: Theorem 1 bounds each graph-to-graphon term, and combining those bounds gives the transferability result for the two graph sizes.The proof applies the bound separately to n1 and n2 before substituting the resulting expressions.
Additional Numerical Results: Consensus
Consensus experiments evaluate transferability by training GNNs on smaller graphs and testing them on larger graphs while varying width, filter taps, and depth.
- Experimental setup: The consensus task drives each node’s signal value toward the average of the graph signal over all nodes.The experiments use folded multivariate-normal inputs and split the data into 8400 training, 200 validation, and 200 testing pairs.
- Experimental setup: Transferability is measured by the relative difference between test rRMSE on the training-size graph and on a larger graph with N = 2000.Models are trained on n = 50, 250, 500, or 1000 nodes and evaluated after transferring their learned parameters to the larger network.
- Transferability results: Across all configurations of F, K, and L, the average relative rRMSE difference and its standard deviation decrease as n increases.This pattern agrees with Theorem 2; Figure 3 reports averages and standard deviations over three graph and three data realizations.
- Hyperparameter effects: Increasing the number of features increases error-bar size for smaller n, while varying filter taps has little apparent effect on transferability.For smaller networks, F = 4 has smaller error bars than F = 8 and F = 16; changes in K show little effect.
- Hyperparameter effects: Increasing the number of layers clearly increases the size of the transferability error bars.The depth effect is reported for the fixed-F and fixed-K configuration in Figure 3c.