PaperlayerView exact revision on arXiv

Source-linked AI summary

Stability Properties of Graph Neural Networks

Fernando Gama, Joan Bruna, Alejandro Ribeiro

arXiv:1905.04497v5cs.LGstat.ML

TL;DR

The paper asks how changes in graph topology affect GNN outputs and why GNNs can combine stability with high-frequency discrimination. It analyzes permutation equivariance and graph-filter stability, then shows that integral Lipschitz filters with nonlinear frequency mixing provide both properties, unlike linear graph filters.

  • Problem

    The paper addresses the tension between stability to graph-topology changes and discrimination of high-frequency graph information.

  • Method

    The paper uses graph Fourier analysis to study permutation equivariance and stability under graph perturbations, including integral Lipschitz filters and nonlinear frequency mixing.

  • Results

    GNNs can be both stable and discriminative because nonlinearities move high-eigenvalue information toward frequencies where integral Lipschitz filters can discriminate it.

  • Takeaways & Limitations

    The stability and discriminability of GNNs arise from combining graph convolutions with nonlinear frequency mixing rather than relying on linear graph filters alone.

Abstract

from arXiv · show

Graph neural networks (GNNs) have emerged as a powerful tool for nonlinear processing of graph signals, exhibiting success in recommender systems, power outage prediction, and motion planning, among others. GNNs consists of a cascade of layers, each of which applies a graph convolution, followed by a pointwise nonlinearity. In this work, we study the impact that changes in the underlying topology have on the output of the GNN. First, we show that GNNs are permutation equivariant, which implies that they effectively exploit internal symmetries of the underlying topology. Then, we prove that graph convolutions with integral Lipschitz filters, in combination with the frequency mixing effect of the corresponding nonlinearities, yields an architecture that is both stable to small changes in the underlying topology and discriminative of information located at high frequencies. These are two properties that cannot simultaneously hold when using only linear graph filters, which are either discriminative or stable, thus explaining the superior performance of GNNs.

I. INTRODUCTION

The paper studies why graph neural networks can outperform linear graph filters, focusing on stability to topology changes and discrimination of high-frequency information. It argues that graph convolutions, nonlinear frequency mixing, and suitable filter constraints jointly explain this advantage.

  • I. INTRODUCTION: The paper relates prior work on scattering-transform and wavelet stability to its analysis of GNNs under graph perturbations and adversarial topology changes.Earlier graph-wavelet studies considered permutation and spectral perturbations, while other work studied malicious edge and signal changes.
  • I. INTRODUCTION: GNNs generalize graph signal processing by cascading graph convolution filter banks with pointwise nonlinearities.Graph filters are polynomial functions of a matrix representation of the graph.
  • I. INTRODUCTION: Pointwise nonlinearities mix frequencies, moving high-eigenvalue information toward low eigenvalues where stable filters can discriminate it.This mechanism parallels the frequency-mixing role described for scattering transforms.
  • I. INTRODUCTION: Linear graph filters cannot simultaneously remain stable and discriminate features associated with large graph eigenvalues.The paper presents this as analogous to the stability–discriminability limitation of linear Euclidean filters and wavelet banks.
  • I. INTRODUCTION: The paper analyzes how permutations and perturbations of the underlying graph affect graph-filter and GNN outputs.Its development covers permutation equivariance, absolute perturbations, relative perturbations, and stability transfer to GNN architectures.

II. STABILITY PROPERTIES OF GRAPH FILTERS

The paper models graphs through graph shift operators and graph signals, then defines graph convolutions as polynomial filters of those operators. It studies how filter outputs change when the underlying shift operator changes.

  • II. STABILITY PROPERTIES OF GRAPH FILTERS: A graph is represented by nodes, edges, weights, and a sparse graph shift operator S, including adjacency and Laplacian variants.The shift operator encodes the graph’s sparsity pattern.
  • II. STABILITY PROPERTIES OF GRAPH FILTERS: Graph signals are node-indexed vectors, and applying S exchanges information locally between neighboring nodes.Repeated shifts motivate polynomial graph convolutional filters.
  • II. STABILITY PROPERTIES OF GRAPH FILTERS: A graph convolutional filter is a polynomial H(S)=Σ_k h_kS^k whose coefficients are shared as filter taps across graphs.The same taps define H(S) and H(Ŝ) for different shift operators.
  • II. STABILITY PROPERTIES OF GRAPH FILTERS: The analysis characterizes filter differences through differences between the corresponding shift operators.It separately considers permutations and perturbations of the graph support.

A. Permutation Equivariance of Graph Filters

Graph filters are equivariant to consistent node relabeling: permuting both the graph and its signal permutes the resulting output in the same way. This motivates measuring operators modulo permutation.

  • A. Permutation Equivariance of Graph Filters: A permutation matrix reorders signal entries and correspondingly reorders the rows and columns of the graph shift operator.The relabeled graph and signal represent the same topology and data under a consistent node relabeling.
  • A. Permutation Equivariance of Graph Filters: For S and Ŝ=P^TSP, filtering corresponding signals x and P^Tx produces outputs related by the same permutation.This is the stated permutation-equivariance proposition for graph filters.
  • A. Permutation Equivariance of Graph Filters: Permutation equivariance means that graph relabeling is inconsequential when the graph and signal are relabeled together.This property supports applications where node labels have no intrinsic meaning.
  • A. Permutation Equivariance of Graph Filters: The paper defines operator distance modulo permutation by minimizing the largest unit-vector output discrepancy over permutations.The minimizing permutation aligns the operators as closely as possible.
  • A. Permutation Equivariance of Graph Filters: If two shift operators differ only by a permutation, their graph filters also have zero distance modulo permutation.The result follows because the same permutation relates the filtered outputs.

B. Effect of Absolute Graph Perturbations on Graph Filters

The paper analyzes graph-filter stability through the graph Fourier domain, where filters act pointwise through their frequency responses. It shows that absolute perturbation stability depends on filter smoothness and perturbation geometry, while relative perturbations expose additional nonuniformity across graph scales.

  • B. Effect of Absolute Graph Perturbations on Graph Filters: In the graph Fourier domain, graph filters act pointwise because H(Λ) is diagonal.The graph Fourier transform is obtained by projecting the signal onto the eigenvector basis of the shift operator.
  • B. Effect of Absolute Graph Perturbations on Graph Filters: A graph’s eigenvalues determine which samples of the filter frequency response are instantiated on that graph.The underlying function h(λ) is graph-independent, while each graph selects values at its own eigenvalues.
  • B. Effect of Absolute Graph Perturbations on Graph Filters: Graph perturbations can change the spectrum, so frequency-response variation directly affects filter stability.This motivates imposing a Lipschitz condition on the frequency response.
  • B. Effect of Absolute Graph Perturbations on Graph Filters: For Lipschitz filters, the operator distance between filters under absolute perturbations is bounded using the filter’s Lipschitz constant and eigenvector misalignment.The theorem provides the corresponding stability bound.
  • B. Effect of Absolute Graph Perturbations on Graph Filters: The absolute-perturbation stability bound is uniform over graphs with N nodes, but its eigenvector-misalignment factor depends on perturbation structure and cannot be controlled by filter design.The filter Lipschitz constant is controllable through design, whereas the perturbation-dependent factor is not.
  • B. Effect of Absolute Graph Perturbations on Graph Filters: A relative perturbation model scales the perturbation constraint by ||S||, but its stability constant is not uniform across graphs with the same number of nodes.Increasing ||S|| can make the bound’s constant arbitrarily large.
  • B. Effect of Absolute Graph Perturbations on Graph Filters: Global relative perturbation norms can permit large relative changes in low-weight graph regions when other regions have large weights.This motivates a model tying local properties of the shift and error matrices.

C. Effect of Relative Graph Perturbations on Graph Filters

Relative perturbations tie graph-edge changes to local topology, while integral Lipschitz filters remain stable under these perturbations and can discriminate finely near λ ≈0.

  • Relative perturbations scale edge-weight changes with local graph structure, unlike absolute perturbations that change edges by the same amount.Weaker links change proportionally less than stronger links under the relative model.
  • Integral Lipschitz filters have frequency responses that are flat for large λ but may vary rapidly around λ = 0.Their rate of change is constrained more strongly as the interval midpoint moves away from zero.
  • Under relative perturbations, integral Lipschitz filters satisfy a stability bound controlled by the perturbation norm, filter constant C, and eigenvector misalignment δ.The stability constant has the form 2C(1+δ√N).
  • A structural perturbation constraint removes the stability bound’s dependence on the graph size N and yields a bound uniform across graph sizes.The constraint requires the error matrix to be approximately a scaled identity.
  • Integral Lipschitz filters can discriminate arbitrarily close spectral features near λ ≈0 while remaining stable, but cannot discriminate nearby features at large λ.Higher selectivity at larger eigenvalues requires a higher C and reduces stability.
  • The eigenvector-misalignment factor δ is bounded by 8 but can make the stability bound loose as N grows.Computing δ requires an eigendecomposition of the perturbation-related matrices.

III. STABILITY PROPERTIES OF GRAPH NEURAL NETWORKS

The paper models GNNs as cascades of graph-filter banks and pointwise nonlinearities, with multiple feature signals propagated across layers on a graph.

  • Each GNN layer processes incoming feature signals with a bank of graph filters, sums filtered outputs, and applies a pointwise nonlinearity.The same nonlinearity acts independently on every feature at every node.
  • A GNN maps an input signal on graph S to an output determined by the graph, learned filter coefficients, layer structure, and nonlinearities.The paper studies the resulting operator’s stability when S changes.
  • The formulation accommodates common graph convolutional architectures, including ChebNets, GCNs, and Selection GNNs.The paper states these architectures can be equivalently described by the adopted model.

A. Permutation Equivariance of GNNs

GNNs are permutation equivariant: relabeling graph nodes and correspondingly relabeling the input produces the correspondingly relabeled output.

  • For ˆS = P^TSP and ˆx = P^Tx, the GNN output transforms consistently under the same permutation.This is the stated permutation-equivariance property of the architecture.
  • Permutation equivariance makes GNN processing independent of node relabelings and preserves a property inherited from linear graph filters.The operator distance modulo permutation is therefore used to compare GNNs across graph perturbations.
  • The operator distance modulo permutation compares nonlinear operators after applying the same permutation at their inputs and outputs.It measures how far the operators are from matching up to a node relabeling.

B. Stability of GNNs to Perturbations of the Graph

GNN stability follows from the stability of their graph filters, with perturbation type, filter regularity, and architecture size determining the resulting bound.

  • The GNN stability constant grows linearly with depth L and exponentially with the number of features F.The paper notes that deeper and wider architectures make the theoretical bound less stable and quite loose.
  • GNNs are Lipschitz stable with respect to graph-support changes, not changes in the input signal.Lipschitz filters support absolute perturbations, while integral Lipschitz filters support relative perturbations.
  • The bound factors into the filter’s (integral) Lipschitz constant, an architecture term LF L−1, and an eigenvector-misalignment term involving δ and N.Filter design or training can affect C, whereas δ is determined by the perturbation family.
  • For absolute perturbations, larger C permits narrower, more selective filters but increases sensitivity, while δ reflects spectral-basis changes and graph size.The eigenvector-misalignment contribution grows with the number of nodes.
  • For relative perturbations, integral Lipschitz filters can be arbitrarily selective near λ ≈0 without affecting overall stability.At higher eigenvalues, C controls where the response becomes approximately flat; increasing C improves selectivity at the expense of stability.
  • Figure 2 shows that eigenvalue displacement grows with λ, while integral Lipschitz filters mitigate the resulting high-frequency response change by becoming nearly constant.Lipschitz filters instead exhibit much larger response differences at high frequencies.
  • The relative-perturbation bound can become quite loose for large graphs because of its dependence on N.A restricted perturbation family is proposed to overcome this degradation.

IV. DISCUSSIONS

The discussion explains why linear graph filters face a stability–selectivity trade-off, and how integral Lipschitz filters plus pointwise nonlinearities preserve stability while recovering high-frequency information. It also shows that GNN outputs respect graph permutations and exploit internal signal symmetries.

  • Stability and selectivity: Lipschitz filters are stable under absolute perturbations, but increasing stability reduces filter selectivity.This trade-off limits the ability of linear filters to discriminate features at high eigenvalues.
  • Graph dilation: A small graph dilation scales eigenvalues by (1 + ε) while preserving eigenvectors, changing filter responses from h(λ_i) to h((1 + ε)λ_i).This spectral view motivates the stability analysis for integral Lipschitz filters.
  • Integral Lipschitz stability: Under relative perturbations, integral Lipschitz filters remain stable even when graph eigenvalues vary substantially.Their frequency-response changes taper as eigenvalues grow, keeping filter responses close despite large spectral shifts.
  • Pointwise nonlinearities: Pointwise nonlinearities spread high-frequency information into lower frequencies, where stable linear filter banks can collect it.This frequency-mixing effect enables stable processing of information that linear filters cannot directly isolate at high eigenvalues.
  • High-frequency feature identification: Stable linear filters cannot isolate high-eigenvalue features because small graph perturbations can cause large eigenvalue changes.Sharp filters centered at high frequencies may lose those features when perturbed eigenvalues move outside their narrow pass bands.
  • Permutation equivariance: GNN outputs are equivariant to graph permutations, making learned features independent of labeling and allowing internal signal symmetries to be exploited.Signals related by graph-preserving permutations produce correspondingly permuted outputs, supporting transfer across such signal arrangements.

V. NUMERICAL EXPERIMENTS

The numerical experiments evaluate GNN stability in movie recommendation under synthetic graph perturbations and graph-estimation errors. Integral Lipschitz GNNs maintain comparable baseline RMSE while showing greater stability than linear and unrestricted-filter GNN architectures.

  • Movie Recommendation: The movie-recommendation task models movies as graph nodes, rating similarities as edge weights, and each user's ratings as a graph signal.The goal is to predict a user's rating for an unseen movie from ratings of other movies and graph similarities.
  • Baseline Evaluation: Baseline RMSE is 0.84(±0.15) for Linear, 0.84(±0.16) for GNN, and 0.83(±0.14) for GNN (IL).Performance is reported over five random dataset partitions.
  • Dataset and Graph: MovieLens-100k provides 100,000 ratings from 943 users over 1,582 movies, with a 10-nearest-neighbor graph built from Pearson correlations.The graph support is estimated using 90% of the ratings for training.
  • Architectures: The compared models are two single-layer GNN architectures, including integral Lipschitz filters, alongside a learned linear graph filter.The architectures use 64 output features, five filter taps, ReLU nonlinearities for the GNNs, and a local linear readout.
  • Synthetic Perturbations: As synthetic perturbation size ε grows, GNN (IL) produces smaller RMSE and output changes than both Linear and GNN architectures.For small ε, output changes are virtually indistinguishable; the stability advantage appears as ε increases.

VI. CONCLUSIONS

The conclusions establish permutation equivariance and stability properties for GNNs under graph perturbations. Integral Lipschitz filters and nonlinear frequency mixing support stability while retaining discrimination across frequencies, although the bounds and perturbation scope remain limited.

  • Permutation Equivariance: GNNs are permutation equivariant, so permuting the graph and signals permutes the outputs consistently across every layer.The proof uses permutation equivariance of graph filters and pointwise nonlinearities.
  • Absolute Perturbations: Under absolute perturbations, Lipschitz graph filters are stable, but greater stability comes at the expense of discriminative power.The paper characterizes this trade-off through graph Fourier representations of the filters.
  • Relative Perturbations: Under relative perturbations, GNN filters need to be integral Lipschitz for the architecture to be stable.Integral Lipschitz filters may be selective near low-eigenvalue frequencies but require a flat high-eigenvalue response.
  • Frequency Mixing: Nonlinearities mix frequencies, spreading information so that GNNs can remain discriminative while using filters with constrained high-frequency responses.This mechanism distinguishes the nonlinear architecture from linear graph filters.
  • Overall Conclusion: The experiments support the view that GNNs combine stability and discriminability, whereas linear graph filters can satisfy only one of these properties.The movie-recommendation experiments also show that the theoretical bounds are not tight.
  • Scope and Future Work: Theorem 4 applies to perturbations preserving the original number of nodes, and its general bounds can be improved for specific perturbation models and graphs.The paper identifies extensions to different graph sizes as an active research area.

APPENDIX C STABILITY UNDER RELATIVE PERTURBATIONS

The relative-perturbation analysis expands graph-filter stability bounds through first-order perturbation terms and eigenvalue-dependent filter responses. Under the structural constraint, the remaining error is bounded at second order in ε.

  • Perturbation Expansion: The proof expands the perturbed filter H(Ŝ) around H(S), separating first-order terms from a second-order remainder.The remainder has operator norm O(∥E∥^2).
  • Spectral Terms: For an eigenvector v_i, the expansion uses the eigenvalue λ_i and the filter derivative h′(λ_i) to characterize perturbation effects.The proof separately treats diagonal and cross-frequency contributions.
  • Relative Constraint: The relative perturbation condition bounds the perturbation eigenvalues after normalization by the largest magnitude eigenvalue.Ordering |m_1| ≤ ··· ≤ |m_N| gives ∥E∥ = |m_N| and ∥E/m_N − I∥ ≤ ε.
  • Bound: The resulting first-order contribution is bounded by 2Cε, while the remaining term is O(ε^2).These bounds complete the relative-perturbation stability proof.

APPENDIX D PERMUTATION EQUIVARIANCE OF GNNS

The appendix proves permutation equivariance for each GNN layer and therefore for the full cascade. Its stability analysis compares outputs evaluated on different graph shift operators using Lipschitz nonlinearities and filter bounds.

  • Filter Equivariance: A permuted graph shift operator produces a correspondingly permuted graph-filter output when the input signal is permuted.This follows from the relation between powers of the original and permuted shift operators.
  • Nonlinearity: Pointwise nonlinearities commute with permutation, so applying them after graph filtering preserves equivariance.The proof uses σ(P^T x) = P^Tσ(x).
  • Full Network: Because every layer is permutation equivariant, the complete GNN is permutation equivariant across all layers.The result holds for any layer ℓ = 1, …, L.
  • Stability Setup: The stability proof measures the difference between GNN outputs evaluated on shift operators S and Ŝ.It propagates per-layer filter discrepancies through the cascade using Lipschitz continuity of the nonlinearity.
  • Layerwise Bound: The layerwise recursion combines filter perturbation bounds with feature norms to obtain a final output bound.The derivation applies bounds on perturbed and unperturbed filters across layers.
Loading 1905.04497v5…