Enhancing Graph Neural Network Expressivity via Subgraphs

74 concepts58 papers1 proposal

Standard Graph Neural Networks (GNNs) process graphs by aggregating information from a node's immediate neighbors. While intuitive, this local message-passing mechanism has a fundamental mathematical limitation: it is at most as powerful as the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test.

To understand why, imagine how a standard GNN views a node's neighborhood. During aggregation, it flattens the neighborhood into a tree-like structure (a multiset of neighbor features). In doing so, it completely misses how those neighbors are connected to each other. For instance, a standard GNN cannot distinguish between a graph made of disconnected triangles and a graph made of a single large cycle if all nodes have the same degree. The network suffers from a structural "blind spot," failing to count basic motifs like triangles, cliques, or rings.

To bypass this theoretical ceiling, a prominent research direction focuses on shifting the fundamental computational unit of GNNs from individual nodes to structured subgraphs.

Shifting from Rooted Trees to Rooted Subgraphs

The core intuition behind overcoming the 1-WL limit is to preserve the internal "texture" of local neighborhoods. Instead of unfolding a neighborhood into a tree, we can treat it as a distinct, localized subgraph.

Muhan Zhang et al. formalize this shift in Nested Graph Neural Networks (NGNNs). By performing message passing over rooted subgraphs rather than rooted subtrees, the model retains the internal connectivity of a node's neighborhood. This allows it to distinguish complex motifs while maintaining linear computational complexity relative to the number of nodes. Similarly, Lingxiao Zhao et al. introduce a wrapper framework (GNN-AK) that uplifts standard GNNs by shifting from simple neighbor aggregation to local subgraph encoding, achieving the theoretical power of higher-order GNNs without their prohibitive computational cost.

By decomposing the graph into a collection of subgraphs, models can break the symmetry of regular graphs that standard architectures find identical. As Leonardo Cotta et al. demonstrate, representing a graph through its subgraphs allows neural networks to exceed traditional limits and differentiate non-isomorphic structures like specific cycles.

Hanqing Zeng et al. show that localized subgraph message passing allows the network to surpass the 1-WL limit precisely because it isolates structural variations that global aggregation averages out. In fact, DingYi Zeng demonstrates that performing message passing on decomposed "Cut" and "Ego" subgraphs allows the model to identify structural differences that standard isomorphism tests cannot detect, leading to significant error reductions in molecular property prediction.

Breaking Symmetry via Node Marking and Labeling

Why does operating on a subgraph suddenly make a GNN more powerful? The secret lies in symmetry breaking. In a highly regular graph, every node looks identical to a local message-passing algorithm. However, if we isolate a subgraph and uniquely "mark" certain nodes, we destroy this uniformity.

A prominent example of this is the "labeling trick." Xiyuan Wang et al. introduce GLASS, a framework that augments node features with binary membership indicators specifying whether a node is "inside" or "outside" a target subgraph. This simple modification allows the GNN to compute critical boundary-sensitive properties like cut ratios and internal density—metrics that standard architectures are mathematically incapable of recovering because they cannot distinguish between edges within a subgraph and those connecting to the external graph.

Symmetry breaking can also be achieved through continuous perturbations or hierarchical structures. Yam Eitan et al. show that computing high-order derivatives of node features with respect to input perturbations acts as a continuous form of node marking, encoding rich structural information that pushes standard models higher up the WL hierarchy. On the logical side, Arie Soeteman et al. prove that the expressive power of a GNN increases strictly with the depth of a recursive node-marking hierarchy, eventually becoming capable of distinguishing any two non-isomorphic graphs when the depth matches the number of nodes.

Explicit Topological Augmentation and Homomorphism Counting

Instead of changing the message-passing mechanism itself, another powerful strategy is to directly inject topological descriptors into the node features. If a GNN cannot count triangles on its own, we can count them beforehand and hand that information to the network.

A straightforward implementation of this is seen in Graph Substructure Networks (GSN), where node features are augmented with explicit counts of small subgraphs like cycles or cliques. Pál András Papp et al. provide a rigorous theoretical map of these extensions, proving that relatively simple structural augmentations—such as counting small connected subgraphs incident to each node—allow GNNs to bypass the 1-WL limit and even surpass the 2-WL expressivity barrier without the full computational complexity of higher-order WL tests.

However, simply adding raw subgraph counts is not always optimal. Emily Jin et al. show that providing a network with the full homomorphism basis of a graph pattern offers strictly greater expressive power than providing individual subgraph or homomorphism counts alone, allowing models to learn more complex structural functions from the underlying components. To scale this idea, Takanori Maehara et al. introduce Deep Homomorphism Networks (DHNs), which stack simple homomorphism layers to recognize an exponentially growing set of non-tree patterns iteratively by combining simpler base patterns into larger motifs.

Alternative Paths to Structural Awareness

The literature explores several other creative mechanisms to embed subgraph awareness into graph representations:

  • Kernel Integration: Aosong Feng et al. introduce KerGNNs, which integrate trainable "hidden graphs" as filters and utilize random walk graph kernels. By measuring subgraph-to-filter similarity instead of simple neighbor aggregation, the model effectively bypasses traditional expressivity limits.
  • Statistical Moments: Rather than deterministic counting, Charilaos I. Kanatsoulis et al. prove that incorporating high-order statistical moments (like variance and skewness) of random node inputs allows standard message-passing architectures to mathematically derive counts of complex substructures like cycles and cliques.
  • Virtual and Fractal Nodes: To prevent information from being "squashed" over long distances, architectures can be augmented with global communication hubs. Jeongwhan Choi et al. introduce "fractal nodes" that act as subgraph-level representatives, enhancing expressive power beyond 1-WL while maintaining linear scalability.
  • Domain-Specific Priors: In molecular modeling, rings are critical structural units. Jinhua Zhu et al. propose $\mathcal{O}$-GNN, which explicitly incorporates ring priors, enabling the network to distinguish isomorphic subgraphs on different rings within a single layer.

By shifting the computational focus from individual nodes to structured subgraphs, these diverse approaches fundamentally repair the topological blindness of standard GNNs, offering a scalable path toward truly expressive graph representation learning.

Key Foundational Work

Graph Neural Networks with Local Graph Parameters (2021) — contributed 2 concept elements to this direction.
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020) — contributed 1 concept elements to this direction.
Expressive Graph Informer Networks (2021) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_subgraph_based_expressivity_3fe7c302,
  title = {subgraph-based expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subgraph-based-expressivity/rdr_3fe7c302819640c1acadb5cec6612164},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_subgraph_based_expressivity_3fe7c302_v1,
  title = {subgraph-based expressivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subgraph-based-expressivity/rdr_3fe7c302819640c1acadb5cec6612164/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake