Source-linked AI summary
Transferability of Spectral Graph Convolutional Neural Networks
Ron Levie, Wei Huang, Lorenzo Bucci, Michael M. Bronstein, Gitta Kutyniok
TL;DR
The paper addresses whether spectral graph ConvNets can generalize across unseen graphs in multi-graph settings. It models comparable graphs as discretizations of a shared topological space and derives transferability conditions from Laplacian approximation and sampling-interpolation consistency. The resulting theory and experiments support spectral filters and ConvNets as transferable, including across graphs with different dimensions and topologies.
Problem
The paper addresses the claim that spectral graph methods are not transferable across graphs, despite the need for ConvNets to generalize to unseen graphs in multi-graph datasets.
Method
The paper models graphs as discretizations of an underlying topological space and analyzes transferability through sampling-interpolation, Laplacian approximation, and consistency errors.
Results
The paper proves that spectral graph filters and ConvNets are transferable under small Laplacian-transferability and consistency errors, including for graphs with different dimensions and topologies.
Takeaways & Limitations
Spectral graph ConvNets should be considered for multi-graph settings because the paper supports their transferability in theory and practice.
Takeaways & Limitations
The theory treats graphs as discretizations of topological spaces, an ansatz whose modeling validity depends on the situation and graph-dataset construction.
Abstract
from arXiv · showhide
This paper focuses on spectral graph convolutional neural networks (ConvNets), where filters are defined as elementwise multiplication in the frequency domain of a graph. In machine learning settings where the dataset consists of signals defined on many different graphs, the trained ConvNet should generalize to signals on graphs unseen in the training set. It is thus important to transfer ConvNets between graphs. Transferability, which is a certain type of generalization capability, can be loosely defined as follows: if two graphs describe the same phenomenon, then a single filter or ConvNet should have similar repercussions on both graphs. This paper aims at debunking the common misconception that spectral filters are not transferable. We show that if two graphs discretize the same "continuous" space, then a spectral filter or ConvNet has approximately the same repercussion on both graphs. Our analysis is more permissive than the standard analysis. Transferability is typically described as the robustness of the filter to small graph perturbations and re-indexing of the vertices. Our analysis accounts also for large graph perturbations. We prove transferability between graphs that can have completely different dimensions and topologies, only requiring that both graphs discretize the same underlying space in some generic sense.
1 Introduction
The paper argues that spectral graph ConvNets can transfer across graphs representing the same phenomenon, including graphs with different structures, by modeling them as discretizations of a shared topological space. Its theory links filter transferability to Laplacian approximation and sampling-interpolation consistency, and extends these conditions to ConvNets.
- Theoretical settings of transferability: Graphs are comparable when they discretize the same underlying topological space, even when their dimensions and topologies differ substantially.This modeling choice permits analysis of graph changes that may be large under standard graph-distance measures.
- Theoretical settings of transferability: The analysis compares filtered graph signals by sampling a continuous signal onto each graph, filtering, and interpolating both outputs back to the shared continuous space.Transferability is established when the two interpolated filtered signals are approximately equal.
- Concept-based and principle transferability: The paper distinguishes learned concept-based transferability from principle transferability, and isolates the latter through zero-shot experiments trained on one graph and tested on others.In that setting, performance only partially degrades, and spectral methods outperform spatial methods in the isolated comparison.
- Overview of transferability results: The transferability inequality bounds filter transferability by Laplacian transferability plus consistency error.Thus, accurate graph-Laplacian approximation and low sampling-interpolation error provide sufficient conditions for spectral-filter transferability.
- Sufficient conditions for transferability: The paper extends the filter conditions to spectral ConvNets, requiring small Laplacian-transferability and consistency errors at each coarsened graph level.The authors also develop a DSP framework for sampled topological spaces and analyze controlled random sampling, while noting that the assumptions depend on how graph datasets are constructed.
- Introduction: Spectral graph ConvNets are argued to be transferable across graphs representing the same phenomenon, countering the claim that spectral methods fail on unseen graphs.The paper frames transferability as a generalization capability in multi-graph settings and states that spectral ConvNets are appropriate for such data.
2 Theoretical framework of graph spectral methods
Graph spectral methods define graph frequencies through a self-adjoint shift operator and apply filters by frequency-wise multiplication. Functional-calculus filters avoid eigendecomposition instability, making them stable under graph perturbations and applicable beyond symmetric graphs.
- Spectral graph filtering: Spectral graph filters use a graph shift operator’s eigenvalues as frequencies and eigenvectors as harmonics, then multiply frequency components by filter coefficients.The graph Fourier transform and filtering are defined from a Laplacian or another self-adjoint operator.
- Spectral graph filtering: Permutation equivariance ensures that re-indexing graph vertices produces the same re-indexing in the filter output.
- Limitations of direct spectral implementation: Direct eigendecomposition-based filters can be computationally demanding and unstable for large graphs because they require Laplacian eigendecomposition and graph Fourier transforms.
- Functional-calculus filters: Functional calculus implements filters as functions of operators, including through compositions, linear combinations, and inversions, without explicitly computing eigendecompositions or Fourier transforms.For rational filters, the functional-calculus and operator-composition definitions are equivalent.
- Transferability and stability: The apparent non-transferability of spectral filters stems from eigendecomposition sensitivity, whereas functional-calculus filters remain stable because changes in g(λ_n) compensate for eigenbasis instability.The paper distinguishes the instability of direct frequency-coefficient implementations from the stability of functional-calculus implementations.
- Directed graphs: Functional calculus also extends spectral filtering to directed graphs by applying the theory under an inner product that makes diagonalizable non-normal operators normal.
3 The transferability inequality
The transferability framework compares filtering on an original space with filtering after sampling onto a finite domain and interpolating back. Its central inequality bounds filter error using Laplacian transferability error and sampling-interpolation consistency error.
- Transferability inequality: The transferability inequality bounds filter transferability error by Laplacian transferability error plus sampling-interpolation consistency error.This provides the paper’s generic bound for comparing filters across domains.
- Transferability framework: Transferability compares filtering a signal directly on the original space with sampling it to a graph, filtering there, and interpolating the result back.Sampling and interpolation are represented by linear operators S_λ and R_λ.
- Transferability framework: The framework applies to measure spaces with separable signal spaces and uses normal operators with discrete spectra to define Laplacians, harmonics, and functional-calculus filters.
- Bandwidth and limitations: Transferability bounds trade off signal bandwidth against approximation accuracy: low cut-off frequencies support lower Laplacian error for smoother signals, while higher frequencies model less-smooth signals with typically higher error.The bounds depend on the chosen Paley-Wiener space and cut-off frequency.
- Concrete settings: The analysis covers graph sampling, graph coarsening, and graph perturbation, with perturbation transferability corresponding to stability when sampling and interpolation are both identity maps.
- Bandwidth and limitations: The tightness of the dependence on the number of low-frequency eigenvalues in the operator-norm bounds remains unresolved.
4 Transferability of spectral graph filters and ConvNets
The paper establishes sufficient conditions under which spectral graph filters and complete ConvNets transfer between graph discretizations of the same underlying space, including through coarsening and pooling. Transferability improves as graph Laplacians approximate the common Laplacian more closely, while network depth and bias can increase instability.
- 4.1 Sufficient conditions for transferability: Under boundedness, asymptotic reconstruction, convergence, and Lipschitz filters, spectral filters achieve asymptotic perfect transferability on fixed bands.The result extends to band-unlimited signals through an increasing sequence of usable bands.
- 4.2 Transferability of graph ConvNets: For complete ConvNets, transferability requires small Laplacian and consistency errors at every coarsened layer, with sampling approximately commuting with activation functions.The framework covers networks with or without pooling and uses layer-specific sampling, interpolation, Laplacians, and frequency bands.
- 4.2 Transferability of graph ConvNets: Adding bias increases transferability instability with depth from linear to quadratic, while the theorem suggests regularizing convolution operators in the infinity norm.The network theorem assumes Lipschitz filters and norm-reducing pooling.
- 4.3 Transferability experiments: On the Bunny mesh, experiments compare original signals and filtered Laplacian outputs with their coarsened-graph reconstructions to demonstrate transferability.A separate experiment evaluates the theoretical bound relating filter transferability to Laplacian transferability.
5 Transferability of graph discretizing topological spaces
The paper develops a discrete signal-processing framework in which graphs sample topological-measure spaces, then proves convergence and transferability properties under quadrature conditions.
- 5 Transferability of graph discretizing topological spaces: The framework treats topological spaces as analog domains and graphs as digital domains, using sampling and interpolation to compare signals and operators.The construction parallels classical Nyquist–Shannon sampling while allowing graph coarsening and other sampling mechanisms.
- 5 Transferability of graph discretizing topological spaces: For contractive positively homogeneous activations, sampling asymptotically commutes with the activation function when the Laplacian respects continuity.The result applies within the DSP framework with quadrature relative to reconstruction and the activation function.
- 5 Transferability of graph discretizing topological spaces: Under quadrature assumptions, graph Laplacians converge to topological-space Laplacians, while sampling and interpolation become asymptotically reconstructive and bounded.The reconstruction bound is C = 1 in the stated result.
- 5 Transferability of graph discretizing topological spaces: With random sample points and sufficiently controlled frequency bands, graph filters and ConvNets approximate their topological-measure counterparts and are therefore transferable.The interpretation follows from the paper’s transferability theorems and includes explicit bounds in the cited theorem’s appendix.
6 Conclusion
The paper concludes that spectral graph filters and ConvNets are transferable when graphs are modeled as samples of a shared continuous Borel space. It presents this framework as a starting point for future theoretical and experimental work.
- 6 Conclusion: The paper proves transferability by modeling graphs as samples of an underlying continuous Borel space and comparing graph outputs through sampling and interpolation.The sampling model includes pointwise sampling and graph coarsening.
- 6 Conclusion: The conclusion reports that later ChebNet experiments found spectral methods competitive with, and especially favorable to, vanilla spatial methods on synthetic continuous-model graph data.This external study is described as validating the paper’s transferability claim experimentally.
- 6 Conclusion: The authors propose their mathematical treatment of shared phenomena and similar network repercussions as a starting point for future transferability research.They call for mathematical models, experimental or heuristic justification, and corresponding transferability error bounds.
A Laplacians of directed graphs as normal operators
The appendix explains how functional calculus extends spectral filtering to directed graphs represented by non-symmetric adjacency matrices by viewing diagonalizable matrices as normal under suitable inner products.
- A Laplacians of directed graphs as normal operators: Functional calculus can define spectral filters for directed graphs represented by non-symmetric adjacency matrices.The extension applies the theory through an appropriate operator and inner-product formulation.
- A Laplacians of directed graphs as normal operators: A diagonalizable matrix can be regarded as a normal operator under a suitable inner product, preserving its eigenvalues and eigenspaces.The matrix’s eigenstructure is algebraic, while normality depends on the chosen inner-product structure.
- A Laplacians of directed graphs as normal operators: The induced inner product is constructed from the eigenvector matrix, allowing adjoints and normality to be expressed in matrix form.This formulation distinguishes operator properties from ordinary symmetry of a matrix representation.
- A Laplacians of directed graphs as normal operators: The paper emphasizes that a non-symmetric matrix may represent a self-adjoint operator, motivating its Hilbert-space formulation over ordinary matrix products.Transpose and adjoint, and symmetric matrices and self-adjoint operators, are not interchangeable notions here.
B.1 Proof of Theorem 5
The proof derives transferability bounds by reducing the analysis to Laplacian eigenvectors, decomposing the graph operator spectrally, and applying functional calculus together with norm inequalities.
- B.1 Proof of Theorem 5: The proof begins with a Laplacian eigenvector and extends the argument to linear combinations using projections onto eigenspaces of the graph operator.Orthogonality of these projections supports the subsequent norm estimates.
- B.1 Proof of Theorem 5: Functional calculus and the transferability relation are combined to compare filtered signals across the continuous and graph operators.The derivation proceeds through the displayed intermediate identities cited in the proof.
- B.1 Proof of Theorem 5: The remaining transferability bounds follow from the filter Lipschitz bound, normalized eigenvectors, Hölder’s inequality, and repeated triangle-inequality estimates.The proof explicitly derives one bound and states that analogous arguments give the others.
B.2 Proof of Theorem 17
The proof bounds approximation errors through convolution, pooling, and recursive layer estimates. It uses norm reduction from pooling and projection to establish the stated network-level bound.
- Pooling and projection decrease the norm under the stated assumption, enabling the recursive error bound.
- The proof tracks the error introduced by one convolution between continuous and discrete signals.
- The network output error is decomposed before and after pooling.
B.3 Proof of Proposition 27
The proof establishes uniform convergence by combining compactness, Lipschitz control, and pointwise convergence of the relevant sequence. A contradiction argument rules out a nonzero limiting maximum.
- The proof applies positive homogeneity to reduce the analysis to the unit sphere in the bandlimited space.
- The mappings are uniformly Lipschitz-bounded, with constants C = 2 and D = 3 for sufficiently large n.
- Uniform convergence is obtained from pointwise convergence on the compact unit sphere S(λ).
- A subsequence contradiction shows that the maximum cannot converge to a nonzero limit.
B.4 Proof of Theorem 33
The proof combines several sampling lemmas to show convergence of graph-based approximations with high probability. Expected mean-square errors vanish, and the required bounds hold simultaneously on a high-probability subsequence.
- The graph Laplacians coincide on average with the topological-measure Laplacian.
- The expected mean-square error satisfies the bound derived from the sampling analysis.
- Monte Carlo concentration converts expected-error bounds into high-probability guarantees using inequalities such as Markov’s.
- With probability more than 1 − δ, the bounds from Lemmas 37, 38, and 41 hold simultaneously along an infinite subsequence.
- The bounds converge as n grows when the sampling dimensions satisfy the stated asymptotic conditions.
B.5 Proof of Proposition 35
The proof bounds the interpolation and sampling terms using spectral-basis and matrix-norm estimates. The resulting interpolation norm is eventually bounded by 2 with probability exceeding 1 − 2δ.
- The second error term is analyzed in the eigenbasis {φ_m} and bounded using the induced l2 norm and Frobenius norm.
- The proof combines the bounds to show that the interpolation constant approaches 1 before applying the final large-n bound.
- For sufficiently large n, the interpolation norm satisfies C < 2 with probability more than 1 − 2δ.
B.6 Proof of Claim 31
The proof fixes an error tolerance and bandlimited signals, then selects parameters that control the subsequent perturbation argument.
- B.6 Proof of Claim 31: The proof begins with bandlimited signals f and g in PW(λ), assuming their ℓ2 distance is less than 1.
- B.6 Proof of Claim 31: The proof chooses δ below a bound depending on ϵ, N(ϵ), and κ, then assumes ∥f−g∥ is below min{δ,1}.