PaperlayerView exact revision on arXiv

Source-linked AI summary

On the equivalence between graph isomorphism testing and function approximation with GNNs

Zhengdao Chen, Soledad Villar, Lei Chen, Joan Bruna

arXiv:1905.12560v2cs.LGstat.ML

TL;DR

GNN expressive power can be studied through both invariant-function approximation and graph-isomorphism testing, but their relationship and comparative framework require clarification. The paper proves these perspectives equivalent, characterizes them with sigma-algebras, and introduces Ring-GNN, which distinguishes regular graphs that 2-IGN cannot. Its broader taxonomy remains incomplete, and weaker graph-distance notions are left for future work.

  • Problem

    The paper addresses how to relate and compare GNNs’ ability to approximate permutation-invariant graph functions with their ability to test graph isomorphism.

  • Method

    It proves an equivalence between the two expressive-power perspectives, characterizes function families through induced sigma-algebras, and extends 2-IGN with ring operations on invariant matrices.

  • Results

    Ring-GNN is more expressive than 2-IGN and distinguishes non-isomorphic regular graphs where 2-IGN provably fails, while retaining tractable complexity.

  • Takeaways & Limitations

    The framework unifies two ways of evaluating GNN expressiveness and supports tractable higher-order interactions through matrix multiplication.

  • Takeaways & Limitations

    The proposed GNN taxonomy is incomplete, and the relevant Ring-GNN operators for different applications require deeper analysis.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as tests for graph isomorphism. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs together with other graph isomorphism tests. In particular, we prove that the second-order Invariant Graph Network fails to distinguish non-isomorphic regular graphs with the same degree. Then, we extend it to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs and achieves good performances on real-world datasets.

1 Introduction

The paper connects GNN function approximation with graph-isomorphism testing and uses this framework to compare expressive power, motivate Ring-GNN, and study practical tractability.

  • 1 Introduction: High-order IGN models can be universal, but tensor orders growing with graph size are difficult to implement in practice.Prior work establishes universality when tensor order grows quadratically with graph size.
  • 1 Introduction: The paper establishes an equivalence between distinguishing every pair of non-isomorphic graphs and approximating every continuous invariant graph function.This connects the two main perspectives used to study GNN expressive power.
  • 1 Introduction: Sigma-algebras induced by function families provide a taxonomy for comparing GNN expressive power.The taxonomy is based on inclusion relationships among the induced sigma-algebras.
  • 1 Introduction: Ring-GNN extends 2-IGN using invariant matrices closed under addition and multiplication, increasing expressiveness while remaining tractable.The architecture is designed to explore the ring of matrix operations.

2 Related Work

Related work studies GNN power through graph-isomorphism tests and invariant-function approximation, while this paper explicitly proves these perspectives equivalent and analyzes their limits.

  • 2 Related Work: Neighborhood-aggregation GNNs cannot distinguish graph pairs that 1-WL fails to distinguish, while suitable architectures can match 1-WL using injective set functions.Higher-order IGNs are also related to higher-dimensional Weisfeiler–Lehman tests.
  • 2 Related Work: Invariant and equivariant neural networks have been studied for universal approximation under symmetry, including graph permutation invariance.k-IGNs achieve universality when tensor order grows quadratically with graph size, which is prohibitive in practice.
  • 2 Related Work: This paper presents an explicit equivalence between graph-isomorphism testing and approximation of permutation-invariant graph functions for finite and continuous feature spaces.It also proves an upper bound showing that 2-IGN cannot distinguish regular graphs with equal degrees.

3 Graph Isomorphism Testing and Universal Approximation

The paper establishes an equivalence between graph-isomorphism discrimination and universal approximation of continuous permutation-invariant graph functions, with a two-layer neural-network augmentation enabling the reverse implication. The results apply first to finite feature spaces and extend to compact continuous feature spaces.

  • Definitions: A permutation-invariant function class is GIso-discriminating when some function separates every pair of non-isomorphic graphs.Universal approximation requires uniformly approximating every continuous permutation-invariant function, while GIso discrimination requires distinguishing all non-isomorphic graph pairs.
  • Finite feature space: For finite feature spaces, universal approximation implies GIso discrimination by approximating an isomorphism-class indicator function with precision ϵ = 0.1.The indicator equals 1 on one graph’s isomorphism class and 0 elsewhere, so its approximation separates that graph from any non-isomorphic graph.
  • Finite feature space: For finite feature spaces, GIso discrimination implies universal approximation after augmenting the class with at most two feed-forward neural-network layers.The NN-augmented class combines outputs of functions in the original class and applies a ReLU feed-forward network.
  • Continuous feature space: For compact continuous feature spaces, universal approximation implies GIso discrimination, and continuous GIso-discriminating classes become universal approximators after two-layer augmentation.These extensions retain the same two-way relationship under the stated continuity and compactness assumptions.

4 Characterizing Expressive Power through Sigma-Algebras

The paper formalizes GNN expressive power through the sigma-algebras generated by permutation-invariant function classes. In this framework, maximal expressiveness corresponds to recovering exactly the partition of graphs into isomorphism classes.

  • Isomorphism classes: For finite graph spaces, graphs are grouped into isomorphism classes, and the collection of these classes forms the quotient space Q = G/≃.The quotient records the equivalence classes induced by graph isomorphism.
  • Sigma-algebra characterization: A permutation-invariant function is exactly measurable with respect to the sigma-algebra generated by the isomorphism classes.This identifies permutation invariance with measurability relative to σ(Q).
  • Sigma-algebra characterization: The sigma-algebra σ(C) generated by a function class C captures its expressive power, with finer sigma-algebras representing more expressive classes.For permutation-invariant classes, σ(C) is contained in σ(Q); maximal expressiveness means equality.
  • Expressiveness results: If C is GIso-discriminating, then σ(C) = σ(Q), so C generates exactly the information needed to identify graph isomorphism classes.Universal approximation also yields σ(C) = σ(Q) through the earlier implication from approximation to GIso discrimination.
  • Expressiveness results: Conversely, σ(C) = σ(Q) implies that C is GIso-discriminating, and sigma-algebra inclusion formally compares expressive power between function classes.The framework defines C1 as no more expressive than C2 when σ(C1) ⊆ σ(C2).

5 Ring-GNN: Exploring the Ring of Graph Operators with a GNN

The section shows that second-order IGNs cannot distinguish certain regular graphs, then introduces Ring-GNN, a tractable matrix-ring extension designed to recover this expressive power.

  • 5.1 Limitation of the 2-Invariant Graph Network (2-IGN): 2-IGN cannot distinguish non-isomorphic regular graphs with the same degree.This limitation is formalized as Theorem 7.
  • 5.2 Ring-GNN as an extension of 2-IGN: Ring-GNN extends 2-IGN without higher-order tensors by using a ring of invariant matrices under addition and multiplication.The architecture is intended to distinguish regular graphs where 2-IGN fails.
  • 5.2 Ring-GNN as an extension of 2-IGN: Ring-GNN builds layers from permutation-equivariant linear maps represented using 15 basis functions and trainable bias terms.The model starts from a tensor input and iteratively applies the defined layers.
  • 5.1 Limitation of the 2-Invariant Graph Network (2-IGN): CSL graphs provide an example that 1-WL and 2-IGN fail to distinguish despite being non-isomorphic.For CSL graphs, non-isomorphism requires differing n or k values beyond the stated modular equivalence.
  • 5.2 Ring-GNN as an extension of 2-IGN: Matrix multiplication lets Ring-GNN capture higher-order graph interactions while its forward-model complexity grows as O(n^2.38), compared with Ω(n^k) for k-IGN.Ring-GNN reduces to 2-IGN when the additional multiplication terms are absent.

6 Experiments

Experiments compare GNNs on synthetic CSL classification and real-world graph datasets. Ring-GNN shows expressive gains over 2-IGN, while GIN and 2-IGN fail on the CSL task in line with their theoretical limitations.

  • 6.1 Classifying Circular Skip Links (CSL) graphs: The CSL experiment uses ten equal-sized isomorphism classes, making 10% accuracy the naive uniform-classifier baseline.The graphs are fixed at n = 41, with ten specified k values.
  • 6.1 Classifying Circular Skip Links (CSL) graphs: GIN and 2-IGN do not outperform the 10% baseline when classifying CSL graphs.The empirical failures are consistent with their limitations as graph-isomorphism tests.
  • 6.1 Classifying Circular Skip Links (CSL) graphs: CSL classification performance can vary because graph-isomorphism tests are not entirely well-posed as classification tasks.The passage attributes this variation to randomness.
  • 6.1 Classifying Circular Skip Links (CSL) graphs: Ring-GNN’s relatively high maximum accuracy indicates that its function class contains many functions that distinguish CSL graphs.The paper frames this experiment as connecting function fitting with graph-isomorphism testing.
  • 6.3 Other real-world datasets: On COLLAB, MUTAG, PTC, and PROTEINS, Ring-GNN outperforms 2-IGN on all four datasets and GIN on one.These results use 10-fold cross-validation; the bioinformatics datasets contain node features.

7 Conclusions

The paper organizes GNN expressive power through an equivalence between graph-isomorphism testing and invariant function approximation, then uses this framework to motivate a tractable ring-based augmentation of 2-IGN.

  • The paper shows that graph-isomorphism testing and permutation-invariant function approximation are equivalent perspectives on GNN expressive power.
  • Its framework characterizes expressive power through sigma-algebras generated on graph space, enabling comparisons among GNN function classes.
  • The proof of the equivalence constructs functions that vanish exactly on a graph’s isomorphism class from pairwise distinguishing functions.
  • The augmented collection adds a feed-forward neural-network layer to functions in the original class.

A.1.2 Proof of Lemma 2

For finite graph spaces, distinguishing isomorphism classes yields exact representation of every permutation-invariant function; for continuous compact spaces, class localization leads to universal approximation.

  • For finite feature spaces, every permutation-invariant function belongs to the one-layer augmented class, so approximation is unnecessary.
  • The finite-space proof builds graph-isomorphism indicators with bump functions and combines them to represent arbitrary invariant functions.
  • For distinct graphs, the Frobenius-distance-to-orbit function is continuous and invariant, allowing an approximating function to distinguish the pair.
  • In the continuous setting, the proof defines localization around each isomorphism class and uses compactness to extract a finite cover.
  • Continuity and permutation invariance ensure that sufficiently small localization values imply closeness to the target graph up to node permutation.
  • Uniform continuity and a partition of unity produce a continuous approximation target, which a sufficiently wide feed-forward network can approximate arbitrarily well.

B Proofs for Section 4

The sigma-algebra proof shows that a GIso-discriminating function class generates exactly the measurable distinctions corresponding to graph isomorphism classes.

  • For a GIso-discriminating class, each graph’s isomorphism class can be expressed through finite intersections of function preimages.
  • The generated sigma-algebra therefore contains all isomorphism classes and is contained in the sigma-algebra generated by the class’s functions.
  • If an isomorphism class were absent from the function-generated sigma-algebra, its smallest containing measurable set would also contain a non-isomorphic graph.
  • That containment contradicts GIso discrimination, because a separating function would create a measurable preimage isolating the two graphs.

C.2 Details of Figure 2

Figure 2 compares graph-isomorphism tests and GNN architectures through their induced distinctions, including relaxations, spectral operators, WL tests, and matrix-multiplication-based models.

  • The comparison assumes graphs are represented only by adjacency matrices and summarizes partial expressive-power relationships among architectures and tests.
  • Spectral GNNs: Spectral GNNs recursively transform graph-signal vectors using selected linear operators and finish by summing the output entries.
  • Spectral GNNs: Power-graph adjacency matrices provide multi-scale information and distinguish some regular graphs that 1-WL cannot distinguish.
  • Matrix-multiplication models: PPGN extends 2-IGN with matrix multiplication and is reported to be as powerful as 3-WL, as is Ring-GNN.
  • Linear Programming: Fractional isomorphism corresponds exactly to indistinguishability by 1-WL, defining a sigma-algebra through the LP objective.
  • Relaxations: LP is less expressive than the SDP relaxation, while the Lasserre/SoS hierarchy requires 2^Omega(n) to solve graph isomorphism.
  • Spectral comparisons: Adjacency spectra and WL tests are incomparable on some graph pairs: each can distinguish examples the other cannot.
  • Additional discussions: The sigma-algebra framework differs from maximal-invariant analysis by assigning the property to function classes and comparing classes that need not be GIso-discriminating.

E Theoretical Limitation of the 2-IGN model

The proof shows that 2-IGNs produce identical outputs for non-isomorphic regular graphs with the same degree. It establishes this by tracking layer representations across edge, non-edge, and diagonal node-pair classes.

  • Theoretical limitation: 2-IGNs cannot distinguish non-isomorphic regular graphs with the same degree.The theorem is proved by showing that the model returns the same output on both graphs.
  • 2-IGN setup: A 2-IGN applies permutation-equivariant linear layers and pointwise activations to tensors of order at most two, followed by invariant processing.Each hidden state can be viewed as a matrix whose entries are attached to ordered pairs of nodes.
  • Inductive structure: The proof partitions node pairs into edges, non-edges, and diagonal pairs, then shows each layer assigns a shared value to every pair in each class.The induction starts from adjacency matrices and preserves this three-class representation through equivariant layers and activations.
  • Identical outputs: Because same-degree regular graphs have equal numbers of edges, non-edges, and diagonal pairs, invariant aggregation gives identical outputs.The proof concludes F(A) = F(A′) after applying the invariant layer and final MLP.
  • Combinatorial counts: The equivariant update depends on combinatorial counts of equivalent tuples, encoded by mE, mN, and mS, rather than finer graph structure.These functions count related pairs in the three classes and are determined by the node-pair equivalence class and tuple pattern.

F GNN Models in the Experiments

The experiments compare several spectral, line-graph, invariant, relational-pooling, and Ring-GNN architectures. Models use dataset-specific training settings, with additional cross-validation procedures for CSL graphs.

  • Model settings: Spectral GNNs and LGNN use 5 layers with hidden dimension 64 and Adam learning rate 0.01.The same optimizer settings and hidden dimension are specified for both model families.
  • Ring-GNN settings: Ring-GNN matches the 2-IGN depth and hidden-layer widths on IMDB experiments and uses a 2-layer, 64-unit configuration for its degree variant.The degree variant is followed by jump knowledge and a fully connected layer with 32 hidden units.
  • Ring-GNN optimization: Ring-GNN parameters are initialized with specified distributions, and Ring-GNN training uses Adam at learning rate 0.00001 for 350 epochs.The initialization differs across k(t)_1 and k(t)_2, with k(t)_2 initialized using a distribution scaled independently of the first parameter.
  • Real-world datasets: For other real-world datasets, models train with Adam at learning rate 0.001 for 350 epochs, using 1–3 layers depending on the dataset.Each layer has 64 hidden units, followed by jump knowledge and a fully connected layer with 32 hidden units.
  • Evaluation protocol: CSL experiments use 5-fold cross-validation, while Ring-GNN repeats training and cross-validation 20 times with different random seeds.The repeated procedure applies specifically to Ring-GNN.
Loading 1905.12560v2…