PaperlayerView exact revision on arXiv

Source-linked AI summary

Can Graph Neural Networks Count Substructures?

Zhengdao Chen, Lei Chen, Soledad Villar, Joan Bruna

arXiv:2002.04025v4cs.LGcs.DMstat.ML

TL;DR

The paper asks how expressive GNN architectures are at counting attributed graph substructures, a capability relevant to graph-structured tasks. It develops a theoretical framework, proves positive and negative counting results across MPNNs, WL tests, and IGNs, and introduces Local Relational Pooling. The results identify limits of common architectures while showing that LRP supports substructure counting and competitive molecular prediction.

  • Problem

    Substructure counts matter in computational chemistry, biology, and social-network studies, but the expressive power of GNNs for counting attributed subgraphs and induced subgraphs requires characterization.

  • Method

    The paper formalizes subgraph-count and induced-subgraph-count abilities, analyzes MPNNs, k-WL, and k-IGNs theoretically, and proposes Local Relational Pooling for learned local substructure processing.

  • Results

    MPNNs and 2-IGNs cannot induced-subgraph-count connected patterns with 3 or more nodes but can subgraph-count star-shaped patterns, while LRP counts both types and achieves competitive molecular-dataset performance.

  • Takeaways & Limitations

    Substructure counting provides a framework for comparing GNN expressive power and motivates architectures that preserve local relational information beyond iterative aggregation.

  • Takeaways & Limitations

    The theory addresses expressive power rather than optimization or generalization, and its worst-case results do not predict average-case performance.

Abstract

from arXiv · show

The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computational chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed graph substructures, extending recent works that examine their power in graph isomorphism testing and function approximation. We distinguish between two types of substructure counting: induced-subgraph-count and subgraph-count, and establish both positive and negative answers for popular GNN architectures. Specifically, we prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL) and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count of substructures consisting of 3 or more nodes, while they can perform subgraph-count of star-shaped substructures. As an intermediary step, we prove that 2-WL and 2-IGNs are equivalent in distinguishing non-isomorphic graphs, partly answering an open problem raised in Maron et al. (2019). We also prove positive results for k-WL and k-IGNs as well as negative results for k-WL with a finite number of iterations. We then conduct experiments that support the theoretical results for MPNNs and 2-IGNs. Moreover, motivated by substructure counting and inspired by Murphy et al. (2019), we propose the Local Relational Pooling model and demonstrate that it is not only effective for substructure counting but also able to achieve competitive performance on molecular prediction tasks.

1 Introduction

The paper studies GNN expressive power through attributed substructure counting, motivated by the importance of graph patterns and limitations of existing characterization approaches. It proves both impossibility and capability results for major architectures and proposes Local Relational Pooling for practical counting and molecular prediction.

  • Attributed substructure counting is relevant to computational chemistry, biology, social networks, molecular fingerprints, graph kernels, and spectral analysis.
  • The paper formalizes GNN expressive power through counts of attributed patterns appearing as subgraphs or induced subgraphs.
  • MPNNs and 2-IGNs cannot induced-subgraph-count connected patterns with 3 or more nodes, using indistinguishable graph pairs with different counts.
  • MPNNs and 2-IGNs can subgraph-count star-shaped patterns, while k-WL and k-IGNs can count subgraphs and induced subgraphs for patterns of size k.
  • T iterations of k-WL cannot induced-subgraph-count path patterns with (k + 1)2T or more nodes, highlighting an interaction between model order and depth.
  • Local Relational Pooling counts subgraphs and induced subgraphs on random synthetic graphs and achieves competitive molecular-dataset performance while learning relevant substructures.

2 Framework

The framework defines attributed graphs, subgraphs, induced subgraphs, and two counting tasks based on isomorphic pattern occurrences. Counting ability is operationalized by whether a function family distinguishes graphs with different counts.

  • Two counting types: Figure 1 illustrates that a pattern can have equal subgraph and induced-subgraph counts or a larger subgraph-count than induced-subgraph-count.
  • Attributed graphs: An attributed graph specifies vertices, edges, node features, and edge features; its adjacency matrix records edge presence.
  • Attributed graphs: Node indices are representation-dependent, while graph isomorphism preserves adjacency and node and edge features under a bijection.
  • Subgraphs and induced subgraphs: A subgraph selects vertex and edge subsets, whereas an induced subgraph includes every original edge whose endpoints lie in the selected vertex set.
  • Two counting types: Subgraph-count CS counts subgraphs isomorphic to a pattern, while induced-subgraph-count CI counts isomorphic induced subgraphs, with CI(G; G[P]) ≤ CS(G; G[P]).
  • Counting ability: A function family can count a pattern when some function distinguishes every graph pair having different subgraph or induced-subgraph counts.

3 Message Passing Neural Networks and k-Weisfeiler-Lehman tests

The paper characterizes substructure-counting limits of MPNNs and k-WL tests, showing sharp positive and negative results that depend on pattern size, shape, and iteration depth.

  • Message Passing Neural Networks: A T-layer MPNN computes node messages by neighborhood aggregation and produces a graph-level prediction through a readout over final node states.The initial node states use node features, while message, update, and readout functions can contain learnable parameters.
  • Message Passing Neural Networks: 2-WL-indistinguishable attributed graphs cannot be distinguished by any MPNN, extending the correspondence to graphs with edge features.
  • Substructure counting by 2-WL and MPNNs: 2-WL cannot induced-subgraph-count any connected pattern with 3 or more nodes, whereas patterns with 1 or 2 nodes are countable.The paper constructs graph pairs with different induced-subgraph counts that remain indistinguishable by 2-WL; the same negative result transfers to MPNNs.
  • Substructure counting by 2-WL and MPNNs: MPNNs and 2-WL can perform subgraph-count of star-shaped patterns, including node and edge features.The MPNN result uses message functions capable of approximating arbitrary functions on multisets, and the 2-WL result follows from the MPNN comparison.
  • Substructure counting by k-WL: At initialization, k-WL can perform both induced-subgraph-count and subgraph-count for patterns containing at most k nodes.This yields a potential hierarchy of increasing counting power as k increases.
  • Substructure counting by k-WL: T iterations of k-WL cannot induced-subgraph-count path patterns of (k + 1)2^T or more nodes, a bound relevant to finite-depth models.The paper notes that many practical GNNs are shallow, although the bound grows quickly as T increases.

4 Invariant Graph Networks

Invariant Graph Networks (IGNs) represent attributed graphs as tensors and process them through equivariant layers, activations, and invariant readout. The section establishes that 2-IGNs are exactly as powerful as 2-WL, yielding corresponding substructure-counting limits and capabilities.

  • Representation: Attributed graphs can be encoded as second-order tensors containing node features, edge features, and the adjacency matrix.Without node or edge features, this representation reduces to the adjacency matrix.
  • Architecture: A k-IGN composes linear equivariant layers, pointwise activations, a linear invariant layer, and an MLP.The resulting function maps kth-order tensor representations to a graph-level output.
  • Expressive power: 2-IGNs are exactly as powerful as 2-WL in distinguishing non-isomorphic graphs.The result resolves the upper-bound question by showing that 2-IGNs cannot distinguish graphs that 2-WL cannot distinguish.
  • Substructure counting: 2-IGNs cannot perform induced-subgraph-count for any connected pattern with 3 or more nodes, but can perform subgraph-count for star-shaped patterns.These results follow from the established equivalence with 2-WL and earlier counting theorems.
  • Substructure counting: k-IGNs can perform both induced-subgraph-count and subgraph-count for patterns consisting of at most k nodes.This follows because k-IGNs are no less powerful than k-WL.

5 Local Relational Pooling

Local Relational Pooling (LRP) applies permutation symmetrization to small rooted egonets, combining local graph structure with a learnable function. Its design restricts orderings and adds degree-dependent normalization to improve tractability and robustness to irrelevant edges.

  • Motivation: LRP addresses the limitations of iterative equivariant aggregation by applying relational pooling to sufficiently local egonets.The motivation is that substructures can be found in sufficiently large local neighborhoods, while standard aggregation may fail to preserve their induced counts.
  • Relational pooling: Relational pooling averages a permutation-sensitive function over node permutations to produce a permutation-invariant graph representation.The underlying function may be a general MLP applied to a tensorized graph representation.
  • Local computation: LRP reduces full permutation averaging to BFS-compatible orderings because egonets are rooted graphs.This makes exact computation tractable on the small egonets used by the model.
  • Local computation: The model further restricts orderings to ordered subsets compatible with k-truncated-BFS, which visits at most k children per node and uses zero padding when needed.This truncation reduces the ordering space while retaining a structured local representation.
  • Normalization: A learnable degree-dependent normalization factor adjusts for irrelevant edges changing the fraction of permutations in which a target substructure appears.The factor is vector-valued and matches the output dimension of the local function.
  • Model variants: The model is called depth-l-size-k LRP, and its node aggregation can use summation or averaging depending on the task.For fixed l and k with bounded node degrees, its time complexity grows linearly in n.
  • Model variants: The experiments focus on variants with l = 1 or k = 1, using MLPs applied to root-node or path-node degrees for normalization.Deep LRP extends the procedure iteratively to utilize multi-scale information.

6 Experiments

The experiments evaluate GNNs on synthetic substructure-counting tasks and molecular prediction datasets. They support the theoretical distinctions between subgraph and induced-subgraph counting, while LRP performs strongly across counting and molecular benchmarks.

  • Synthetic counting tasks: The synthetic evaluation includes subgraph-counting of 3-stars and induced-subgraph-counting of triangles, tailed triangles, chordal cycles, and attributed triangles.The five patterns are illustrated in Figure 3 and evaluated on random graph datasets.
  • Synthetic evaluation: The synthetic datasets comprise Erdős-Rényi and random regular graphs, with ground-truth labels computed by a substructure-counting algorithm.Models include LRP, GraphSAGE, GIN, GCN, 2-IGN, PPGN, and spectral GNNs, trained with MSE.
  • Synthetic evaluation: Test errors are normalized by the variance of the ground-truth pattern counts, with Table 1 reporting best and median performances over five random seeds.The table covers induced triangle counts and subgraph counts of 3-stars.
  • Molecular prediction: On ogbg-molhiv, Deep LRP-1-3 with early stopping achieves higher testing ROC-AUC than the baseline models.The early-stopped variant is trained for fewer epochs to address overfitting under scaffold splitting.

7 Conclusions

The paper develops substructure counting as a framework for analyzing GNN expressive power and proposes LRP as a practical architecture. Its conclusions combine theoretical counting guarantees, supporting experiments, and molecular prediction results, while noting that the theory does not address optimization or generalization.

  • Conclusions: The framework distinguishes subgraph-count from induced-subgraph-count and uses these abilities to study GNN expressive power.The paper connects counting, graph-function approximation, and graph discrimination in its theoretical development.
  • Theoretical results: MPNNs and 2-IGNs cannot induced-subgraph-count connected structures with 3 or more nodes, whereas k-IGNs and k-WL can count patterns of size k.The paper also derives an upper bound for path-shaped patterns under finite iterations of k-WL.
  • Theoretical results: The paper proves that 2-IGNs and 2-WL are equivalent for distinguishing non-isomorphic graphs and that MPNNs are no more powerful than 2-WL on attributed graphs.The 2-IGN result partly answers an open problem identified in prior work.
  • Empirical results: Experiments support the theoretical results and show that Local Relational Pooling can count certain substructures successfully.LRP is also evaluated on molecular prediction tasks in the experimental study.
  • Limitations: The theory addresses expressive power but not GNN optimization or generalization, and its worst-case results cannot predict average-case performance.The authors identify further questions involving broader k-WL and k-IGN characterizations and the relevance of counting in empirical tasks.

Broader impact

The paper frames substructure counting as a practical and theoretical test of GNN expressive power, while relating approximation to graph discrimination on finite graph spaces.

  • Formal framework: The paper formalizes induced-subgraph-count and subgraph-count functions for attributed patterns and studies whether GNN families can approximate them.
  • Formal framework: Graph discrimination provides an equivalent working perspective because approximating count functions requires distinguishing graphs with different counts.
  • Formal framework: On finite graph spaces, a one-layer neural augmentation can approximate a target count function when the underlying function family distinguishes every pair with different target values.
  • Formal framework: For MPNN and k-IGN families, parallel execution and a final MLP do not increase expressive power beyond larger hidden states, messages, or the readout function.

D Proof of Theorem 3.2 (MPNNs are no more powerful than 2-WL)

The proof establishes that an MPNN cannot distinguish graphs that 2-WL cannot distinguish, by inductively matching hidden states to 2-WL colors and therefore obtaining identical readouts.

  • Inductive correspondence: Assuming an MPNN distinguishes two graphs, the proof tracks their messages and hidden states across layers.
  • Inductive correspondence: The induction uses 2-WL color equality to establish matching node-pair states, with edge features and adjacency values included in the correspondence.
  • Inductive correspondence: At each layer, a permutation matching 2-WL colors transfers the relevant neighborhood multisets between the two graphs.
  • Conclusion: The induction extends symmetrically across both endpoints of each node pair, yielding corresponding hidden states at the final MPNN layer.
  • Conclusion: Identical final hidden representations produce identical MPNN outputs, contradicting the assumption that the two graphs were distinguished.

E Proof of Theorem 3.3 (2-WL is unable to induced-subgraph-count patterns of 3 or more nodes)

The proof constructs graph pairs with different induced counts for every connected pattern of at least three nodes, while preserving all 2-WL color multisets through a color-preserving bijection.

  • Counterexample construction: For any connected pattern with more than two nodes, the construction uses two copies of the pattern and modifies four cross-copy edges differently.
  • Counterexample construction: The resulting graphs have different induced-subgraph counts: one contains no copy of the pattern, whereas the other contains at least two.
  • Counterexample construction: For clique patterns, the construction likewise produces zero copies in one graph and two in the other while retaining the same 2-WL limitation.
  • 2-WL indistinguishability: A bijection on node pairs maps the special pairs between the graphs and preserves 2-WL colors at initialization.
  • 2-WL indistinguishability: The inductive argument shows that the bijection remains color-preserving at every iteration, so 2-WL cannot distinguish the constructed graphs.

G Proof of Theorem 3.7 (k-WL is able to count patterns of k or fewer nodes)

The proof shows that k-WL can distinguish graphs differing in counts of patterns with at most k nodes directly from the initial colors assigned to k-tuples.

  • k-WL initializes tuple colors according to isomorphism types, including node and edge attributes.
  • If two graphs differ in the matching-count or containment-count of a pattern with at most k nodes, their k-tuple counts differ by isomorphism type.
  • The differing multiset of initial tuple colors lets k-WL distinguish the graphs at iteration 0.

H Proof of Theorem 3.9 (T iterations of k-WL cannot induced-subgraph-count path patterns of size (k + 1)2T or more)

The proof constructs two graphs that T iterations of k-WL cannot distinguish, yet whose induced counts of sufficiently long path patterns differ. The construction uses tuple permutations preserving k-WL colors through the iterations.

  • Graph construction: For m ≥ (k + 1)2^T, the proof constructs two graphs G[1] and G[2] from two copies of a path with different endpoint-crossing edges.The graphs share the doubled-path edge set but connect endpoints differently.
  • Permutation construction: A counting lemma guarantees an index i whose length-2^T interval avoids the residues of every k-tuple s.This permits defining χ(s) as the smallest such index and using it to choose a tuple permutation.
  • Permutation construction: The map η(s) = ζχ(s)(s) is a permutation because χ(s) = χ(η(s)) and each underlying τi permutation is self-inverse.Consequently, applying η twice returns every k-tuple to itself.
  • Color preservation: Induction shows that η preserves the k-WL color of every k-tuple through iteration T.The inductive step constructs bijections between corresponding neighbor sets, while the base case preserves tuple isomorphism types, node features, and edge features.
  • Conclusion: The two graphs have different matching-counts of the target path pattern, while k-WL cannot distinguish them after T iterations.The result establishes the finite-depth limitation for induced-subgraph counting of path patterns with at least (k + 1)2^T nodes.

I Proof of Theorem 4.2 (2-IGNs are no more powerful than 2-WL)

The proof establishes that every 2-IGN produces identical outputs on graph pairs that 2-WL cannot distinguish. It does so by relating 2-WL color classes to tensor representations and preserving the required symmetries through equivariant layers.

  • Inductive proof: Induction shows that matching 2-WL color multisets imply matching 2-IGN representations for both edge pairs and diagonal node pairs.The argument treats distinct pairs and diagonal pairs separately, using the corresponding partitions of V^2.
  • Color-to-tensor correspondence: The proof partitions ordered node pairs into structural equivalence classes and uses these classes to compare 2-WL colors with 2-IGN tensor entries.For distinct-node pairs, nine classes are defined according to the equivalence type of the associated 4-tuples.
  • Equivariance: A linear equivariant 2-IGN layer depends on 4-tuples only through their equivalence classes, allowing corresponding pair classes in the two graphs to receive identical transformations.The proof explicitly uses permutation-equivalence of the relevant 4-tuples.
  • Conclusion: The final invariant pooling step yields m ◦ h(B(T)) = m ◦ h(B′(T)), so the 2-IGN outputs are identical.Thus, any 2-IGN cannot distinguish the graph pair whenever 2-WL cannot distinguish it.

L Theoretical limitations of GraphSAGE in substructure counting

The section identifies structural limits of GraphSAGE for substructure counting when aggregation uses full 1-hop neighborhoods or broader neighborhood summaries. These limits contrast with LRP, which retains higher-order local structure.

  • Aggregation scope: Full 1-hop GraphSAGE aggregation is bounded by WL-like expressive power, as in MPNNs, when each iteration uses only a 1-hop neighborhood.The section therefore excludes random node sampling to keep substructure counting well-defined.
  • Information representation: GraphSAGE aggregates neighborhoods as sets or sequences rather than tensors, losing edge-feature and higher-order-structure information relative to LRP.This information loss limits the structures GraphSAGE can distinguish and count.
  • Edge features: GraphSAGE cannot distinguish the Figure 6 graph pair even when immediate edge features are incorporated into node features, whereas LRP-1-2 can.The stated augmentation uses an invariant function such as summing or averaging over immediate-edge features.
  • Synthetic results: GraphSAGE + LSTM counts stars but not triangles on the synthetic tasks, consistent with the limitations of full 1-hop neighborhood information.The experiment uses full 1-hop neighborhood aggregation.

M.2.2 Additional results

Additional experiments evaluate induced-subgraph counting on three patterns and molecular prediction on ZINC and ogbg-molhiv. They also report training-time costs for Deep LRP models on ogbg-molhiv.

  • Synthetic counting results: Deep LRP-1-3 achieves the best overall performance across the three additional induced-subgraph-counting patterns on the synthetic datasets.The patterns are tailed triangles, chordal cycles, and attributed triangles.
  • Synthetic counting results: All three evaluated models perform well on each additional induced-subgraph-counting pattern on at least one of the two synthetic datasets.
  • Training cost: Deep LRP-1-3 takes approximately 5–8× as much training time as GIN on ogbg-molhiv, decreasing to 3–5× with more data-loading workers.The N2P, E2P, and Ppl operations account for most of the forward running time.
  • Molecular prediction: ZINC experiments report that LRP models outperform all other baselines with the same level of parameter counts.The evaluation uses Mean Absolute Error for regression.
Loading 2002.04025v4…