PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, Michael M. Bronstein

arXiv:2006.09252v3cs.LGcs.SIstat.ML

TL;DR

Standard GNNs are limited by WL-bounded message passing and cannot reliably capture or count important graph substructures. The paper proposes GSN, which encodes substructure counts into message passing, proves greater expressivity and sufficient conditions for universality, and reports state-of-the-art real-world performance. Generalization still depends on choosing structurally relevant substructures rather than simply maximizing disambiguation.

  • Problem

    Standard GNNs are WL-bounded and limited in detecting or counting graph substructures, despite substructures being related to properties in domains such as chemistry and network science.

  • Method

    GSN enhances message passing by transforming neighbor contributions according to structural relationships encoded through counts of selected substructures.

  • Results

    GSN is strictly more expressive than traditional GNNs for most substructures, can be universal under sufficient conditions, and achieves state-of-the-art results on evaluated real-world networks.

  • Takeaways & Limitations

    Substructure-aware message passing can distinguish graph pairs that 1-WL cannot and retain locality while using domain-specific structural inductive biases.

  • Takeaways & Limitations

    Good generalization is not guaranteed by stronger vertex disambiguation, so substructures should be selected using prior knowledge of their importance in particular network distributions.

Abstract

from arXiv · show

While Graph Neural Networks (GNNs) have achieved remarkable results in a variety of applications, recent studies exposed important shortcomings in their ability to capture the structure of the underlying graph. It has been shown that the expressive power of standard GNNs is bounded by the Weisfeiler-Leman (WL) graph isomorphism test, from which they inherit proven limitations such as the inability to detect and count graph substructures. On the other hand, there is significant empirical evidence, e.g. in network science and bioinformatics, that substructures are often intimately related to downstream tasks. To this end, we propose "Graph Substructure Networks" (GSN), a topologically-aware message passing scheme based on substructure encoding. We theoretically analyse the expressive power of our architecture, showing that it is strictly more expressive than the WL test, and provide sufficient conditions for universality. Importantly, we do not attempt to adhere to the WL hierarchy; this allows us to retain multiple attractive properties of standard GNNs such as locality and linear network complexity, while being able to disambiguate even hard instances of graph isomorphism. We perform an extensive experimental evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings including molecular graphs and social networks. The code is publicly available at https://github.com/gbouritsas/graph-substructure-networks.

1 Introduction

Standard GNNs use permutation-invariant message passing but are limited by the WL test in exploiting graph structure and counting substructures. GSN addresses this by encoding substructure-based structural relationships while retaining isomorphism invariance and locality.

  • 1 Introduction: GNN message passing aggregates neighboring information while remaining invariant to neighborhood permutations and graph isomorphism.This symmetry supports graph processing without a canonical node ordering, but may not distinguish structurally different neighbors.
  • 1 Introduction: Because message-passing GNNs are at most as powerful as WL, they have limited ability to exploit graph structure and count substructures.The paper identifies this as important because substructures such as molecular rings and functional groups relate to downstream properties.
  • 1 Introduction: The paper frames GNN design around breaking local symmetry, incorporating structural characteristics, and preserving isomorphism invariance for generalization.These goals are presented as three major questions for architecture design.
  • 1 Introduction: GSN transforms each neighbor’s message according to its structural relationship with the central node, expressed through counts of selected substructures.Substructure counts are vertex invariants, so the resulting network remains invariant to isomorphism; selected substructures also provide distribution-specific inductive biases.
  • 1 Introduction: GSN is theoretically more expressive than traditional GNNs for most substructures while retaining local message passing, and its limiting form can be universal.Experiments include hard graph-isomorphism instances and real-world social and biological networks, where domain-specific structural biases achieve state-of-the-art results.

2 Preliminaries

The preliminaries define subgraphs, graph isomorphism, automorphism-based structural roles, and the WL test. They also position higher-order WL variants as stronger alternatives operating on node tuples.

  • 2 Preliminaries: A subgraph consists of selected vertices and edges, and is induced when it contains every graph edge whose endpoints are selected.The definition distinguishes arbitrary subgraphs from induced subgraphs.
  • 2 Preliminaries: Graph isomorphism is an adjacency-preserving bijection between vertex sets, while an automorphism maps a graph onto itself.Automorphisms capture the graph’s internal symmetries.
  • 2 Preliminaries: Automorphisms partition vertices into orbits that group nodes with equivalent structural roles.Examples include path endpoints and vertices of a cycle.
  • 2 Preliminaries: Vertex automorphisms induce edge automorphisms, which partition edges into edge orbits according to preserved adjacency relationships.This extends structural-role analysis from vertices to edges.
  • 2 Preliminaries: The WL test iteratively refines vertex colors by aggregating neighboring information and compares graphs using their final color histograms.Different histograms prove non-isomorphism, whereas identical histograms do not guarantee isomorphism; GNN aggregation is its learnable analogue.
  • 2 Preliminaries: Higher-order WL generalizations operate on k-tuples of nodes, with 2-FWL strictly stronger than 1-WL.These methods form a hierarchy of increasing expressive power.

3 Graph Substructure Networks

GSN encodes structural roles through substructure counts in permutation-equivariant message passing, making it more expressive than 1-WL and MPNNs while retaining locality and linear training/inference complexity. Its expressivity extends to hard isomorphism cases and can be universal under a Reconstruction Conjecture-based condition, although selecting substructures that generalise well remains open.

  • 3.1 Structural features: GSN encodes node and edge structural roles by counting substructure occurrences and automorphism orbits.The resulting counts are combined into structural feature vectors used in message passing.
  • 3.2 Structure-aware message passing: Structural features transform each neighbour’s message according to its topological relationship with the central node while preserving permutation equivariance.Subgraph isomorphism generates identifiers equivariantly, so GSNs remain invariant to graph isomorphism.
  • 3.3 How powerful are GSNs?: GSN is strictly more powerful than MPNNs and 1-WL for broad substructure families, excluding star graphs under non-induced matching and single edges or nodes under induced matching.Cycle counting can distinguish non-isomorphic graphs that 1-WL cannot distinguish.
  • 3.3 How powerful are GSNs?: If the Reconstruction Conjecture holds and GSN uses all graphs of size n − 1, it can distinguish every non-isomorphic graph of size n and is therefore universal.The paper conjectures that real-world graphs may require far fewer substructures, but this is not established generally.
  • 3.3 How powerful are GSNs?: GSN-e is at least as expressive as GSN-v, and constant-size substructure families can match or exceed 2-FWL on selected graph pairs.A 4-clique distinguishes the Rook’s 4x4 and Shrikhande graphs, while 2-FWL fails on this pair.
  • 3.4 How to choose the substructures?: Substructure choice affects generalisation: cycle-based GSNs achieve a smaller molecular-property generalisation gap and generalise better with less training data than traditional MPNNs.Choosing the best collection remains an open combinatorial problem, with motif frequencies and feature selection suggested as heuristics.
  • 3.3 How powerful are GSNs?: Training and inference cost O(|E|), while substructure counting is separate preprocessing whose practical burden is often negligible for small sparse graphs.Exact VF2 counting has worst-case complexity O(n^k), but empirical runtime is substantially better for several real-world graph distributions.

4 Related Work

Prior work extends GNN expressivity through higher-order WL-inspired methods, identifiers, equivariant message passing, and substructure-based representations, while highlighting trade-offs in complexity and principled symmetry breaking.

  • Unique identifiers: Identifier-based approaches use local orderings, random features, or random colorings to increase expressivity, but lack a principled permutation-equivariant choice of identifiers.Considering all vertex permutations is a possible workaround but has O(n!) complexity.
  • More expressive permutation equivariant GNNs: Equivariant message-passing methods assign message transformations using local isomorphism classes, but accounting for all such classes can limit weight sharing.This creates a trade-off between structural specificity and parameter sharing.
  • Quantifying expressivity: Expressivity analyses increasingly measure substructure-counting ability because distinguishing non-isomorphic graphs alone lacks sufficient granularity.The 1-WL test can already distinguish almost all non-isomorphic graphs probabilistically.
  • Substructures in network analysis: Network motifs and graphlets provide established topological descriptors, with graphlets differing from motifs by being induced subgraphs.Graphlet degree vectors use graphlet counting as node-wise descriptors for network similarity.
  • Substructures in machine learning: Substructure information also underlies graph kernels, motif-based embeddings, and diffusion operators, whereas larger-neighborhood and higher-order-path GNNs can have prohibitive complexity.The paper presents its formulation as a unifying framework for these methods and analyzes expressive power.

5 Experimental Evaluation

The experiments evaluate GSN across graph classification, molecular regression, HIV-related molecular classification, and controlled comparisons of substructure choices and training-set size.

  • Benchmark evaluation: GSN is evaluated across bioinformatics, computational social science, molecular regression, and molecular graph classification benchmarks.The evaluation uses TUD datasets, ZINC logP regression, and OGB-MOLHIV classification.
  • Benchmark evaluation: GSN variants with and without edge features achieve state-of-the-art results, outperforming all baseline architectures on the reported molecular task.Both variants are compared directly against the selected baselines.
  • Substructure collections: Training error tracks disambiguation score, but test error does not: cycle-based identifiers generalise better despite lower disambiguation scores.The comparison motivates selecting structurally meaningful identifiers rather than maximally discriminative ones.
  • Training-set size: GSN generalises better than vanilla MPNN with only 20% of the training samples.The comparison uses training and test errors across different fractions of the ZINC training set.

6 Conclusion

The paper concludes that subgraph-isomorphism-derived structural features provide a structure-aware message-passing design with improved expressivity and empirical performance while preserving permutation equivariance.

  • Conclusion: GSN enhances message passing with structural features extracted by subgraph isomorphism to capture topological properties.The conclusion presents this as the paper’s central design contribution.
  • Future work: The authors identify exploring GSN expressivity, generalisation, and data-driven substructure discovery as future directions.They also propose studying how GNNs compose substructures.
  • Permutation equivariance: The construction is permutation equivariant because vertex and edge structural identifiers transform equivariantly under vertex permutations.GSN-v and GSN-e can be expressed through permutation-equivariant MPNN operations.
  • Permutation equivariance: A GSN network is permutation equivariant, and becomes permutation invariant when followed by a permutation-invariant READOUT function.This follows from composing permutation-equivariant layers with the final readout.

A.2 Proof of Theorem 3.1: GSN is at least as powerful as the 1-WL test

The proof establishes that GSN can match or exceed 1-WL’s vertex distinctions by using injective updates, messages, and neighbour aggregation.

  • Proof scope: The result is formulated for vertex-labelled graphs, while an extension incorporating edge labels follows by concatenating edge labels with neighbour colours.The proof compares graph-level multisets of vertex representations with 1-WL colour histograms.
  • Graph-level conclusion: Equal GSN graph representations imply equal corresponding 1-WL colour multisets under the proof’s injectivity conditions.The argument compares distinct hidden representations and their multiplicities across graphs.
  • Expressivity proof: GSN is at least as expressive as 1-WL when its update and aggregation functions preserve the required injectivity.The proof constructs a model whose vertex partition is at least as fine-grained as 1-WL’s partition.
  • Inductive argument: The argument inductively transfers 1-WL colour distinctions into GSN hidden representations across message-passing iterations.The base case uses identical initial vertex features, and the induction step applies injective updates.

A.3 Proof of Corollary 3.2

The universality proof uses substructures of size n − 1 to recover each vertex-deleted subgraph and thereby distinguish graph isomorphism classes.

  • Universality construction: When the substructure collection contains all graphs of size n − 1, GSN can infer the isomorphism classes of all vertex-deleted subgraphs.These vertex-deleted subgraphs form the graph’s deck.
  • Graph reconstruction: The deck is sufficient to distinguish non-isomorphic graphs because graphs with at least three vertices are isomorphic exactly when their decks match.The proof relies on the reconstruction conjecture.
  • Deck representation: The deck is represented as a vector whose dimensions count vertex-deleted subgraphs matching each graph in the size-(n − 1) collection.The structural features are computed using substructure matches and orbit information.
  • Universality conclusion: Orbit-wise aggregation and a sum readout allow GSN-v to infer the deck, and GSN-e inherits universality because it can represent GSN-v.The construction uses a linear layer with depth equal to |H| and normalization by n − 1.

A.4 Proof of Theorem 3.3

The proof shows how edge-based structural identifiers can recover the vertex-based GSN formulation, after which standard message passing completes the simulation.

  • Proof strategy: The proof first establishes that a vertex identifier can be inferred from the identifiers of its incident edges.The argument relies on directed edge identifiers and orbit-based neighbourhood information.
  • Structural identifiers: Vertex and edge orbits are indexed separately, with structural features assigned to orbit pairs.Orbit neighbourhoods collect the multiset of neighbour orbits, while orbit degree records the common degree within a vertex orbit.
  • Inductive argument: For a matched subgraph, the proof considers each vertex orbit and relates its incident edge identifiers to the corresponding vertex role.The induction tracks matched subgraphs and vertices whose mappings belong to a specified orbit.
  • Simulation result: A GSN-e with L+1 layers can simulate a GSN-v with L layers by using a first layer of width d_in^V+d_in^E.The first layer computes the required edge-to-vertex transformation, and the remaining L layers implement a traditional MPNN.
  • Simulation result: The proof uses a universal multiset function approximator to implement the first-layer transformation before applying the original message-passing computation.The subsequent layers receive the reconstructed vertex features.
  • WL terminology: The appendix distinguishes the k-FWL convention used here from the alternative k-WL terminology common in GNN expressivity and graph-isomorphism literature.Under this convention, the discussed k-FWL family operates on k-tuples of vertices and refines their colours using tuple replacements.

B.2 Why does 2-FWL fail on strongly regular graphs?

The analysis explains why 2-FWL cannot distinguish strongly regular graphs sharing the same parameters: tuple colours stabilize after one refinement.

  • Strongly regular graphs: Strongly regular graphs SR(n,d,λ,µ) are regular graphs whose adjacent and non-adjacent vertex pairs have fixed common-neighbour counts λ and µ, respectively.These four parameters determine the regularity and pairwise common-neighbour conditions used in the analysis.
  • Tuple types: For simple undirected graphs without self-loops, 2-tuples have vertex, edge, or non-edge isomorphism types.The initial colours are denoted cα, cγ, and cβ for these three types.
  • Refinement mechanism: The 2-FWL analysis constructs generalized neighbours by replacing one coordinate of a tuple with an arbitrary vertex.The resulting generalized neighbour is another ordered 2-tuple, whose colour contributes to refinement.
  • Failure on SR graphs: For strongly regular graphs, all 2-tuples of the same initial type receive the same colour after the first iteration.The cases considered include vertex-type, non-edge-type, and edge-type tuples.
  • Failure on SR graphs: 2-FWL therefore cannot further partition the tuples and terminates on these graphs.The refinement stabilizes because tuples sharing an initial type remain indistinguishable after the update.
  • Failure on SR graphs: Any two strongly regular graphs with identical n,d,λ,µ parameters obtain the same 2-FWL colour distribution and are deemed isomorphic by the test.This is the stated failure mode for the strongly regular graph family.

C Experimental Settings - Additional Details

The experiments were designed for reproducibility and to isolate the contribution of structural identifiers by adding them to baseline architectures where possible.

  • Infrastructure: Experiments used eight Tesla V100 16 GB GPUs, except Collab, which used one Tesla V100 GPU with 32 GB RAM.Experimental tracking and hyperparameter optimization used Weights & Biases.
  • Infrastructure: The implementation uses native PyTorch sparse operations to support complete reproducibility.The passage presents sparse operations as the implementation basis for the experiments.
  • Experimental design: The experiments evaluate structural identifiers independently of the architecture while suppressing other confounding factors where possible.Models are built on top of baseline architectures whenever feasible.
  • Experimental design: In most cases, replacing only the first layer of the baseline architecture was sufficient.This observation supports the intended modular use of structural identifiers.
  • Structural features: Structural identifiers are one-hot encoded using the unique count values present in each dataset.Normalization or binning was considered unnecessary because the datasets usually contained relatively few unique values.

C.1 Synthetic Experiment

The synthetic experiment evaluates GSN on strongly regular graph families, using graphlet counting and a compact graph-classification architecture; the authors identify broader hard-instance testing as future work.

  • Dataset: The six families contain 15, 10, 4, 41, 3854, and 227 graphs, respectively.The counts correspond to SR(25,12,5,6), SR(26,10,3,4), SR(28,12,6,4), SR(29,14,6,7), SR(35,16,6,8), and SR(35,18,9,9).
  • Dataset: The experiment contains approximately 7 ∗ 10^7 non-isomorphic pairs of the same size.This quantifies the scale of the strongly regular graph comparison set.
  • Model: The model uses two layers of width 64, sum readout, and MLP-based message, update, and prediction functions.Message aggregation follows the general formulation of the paper’s Eq. (5).
  • Structural features: Graphlet counting supplies the substructures used in the synthetic experiment.The passage notes that motifs such as cycles of length up to 7 are among the relevant substructures.
  • Scope and future work: The authors leave evaluation on other hard graph-isomorphism instances, including CFI counterexamples for k-WL, to future work.They also identify further exploration of expressive power and combinatorial properties as an open direction.

C.2 TUD Graph Classification Benchmarks

The experiments evaluate GSN variants built by augmenting GIN-like message passing with vertex- or edge-level structural identifiers. Model selection searches substructure families and sizes, with cycles favored for molecular tasks and triangles or cliques considered for social-network tasks.

  • Architecture: GSN extends GIN-like message passing by concatenating or embedding structural identifiers with vertex or edge features.For GSN-v, structural information is incorporated into vertex representations; for GSN-e, it is incorporated into edge representations.
  • Model selection: Model selection tunes substructure type and maximum size using validation performance, considering graphlets versus motifs and GSN-v versus GSN-e.The reported searches include cycles with k = 3, . . . , 12 for molecular datasets and cliques with k = 3, 4, 5 for social networks.
  • Benchmarks: The benchmark suite comprises seven datasets shared by the GIN and PPGN baseline studies, alongside comparisons with other GNNs and graph-kernel methods.GIN is described as matching the expressive power of the 1-WL test, while PPGN is described as matching 2-FWL.
  • Selected substructures: The chosen molecular configurations include cycle graphlets of 10 vertices for GSN and cycle motifs of 8 vertices for GSN-EF.For the ogbg-molhiv setting, the selected configuration is GSN-e with cycle graphlets of 6 vertices.
  • Evaluation: The evaluation reports ROC-AUC or test MAE after validation-based model selection, with repeated runs using different random seeds.For one experiment, the test MAE is reported as the mean and standard deviation over 10 seeds; molecular ROC-AUC experiments likewise repeat runs 10 times.
Loading 2006.09252v3…