Subgraph Graph Neural Networks: Balancing Scalability and Expressivity

Graph Neural Networks (GNNs) have become a vibrant research area in deep learning because they combine graph theory with neural models to exploit topological information, addressing the limitations of Euclidean‑space methods.

Two major challenges hinder GNN development: (1) the exponential growth of computation when applying k‑hop message passing on large‑scale industrial graphs, and (2) limited expressive power in graph isomorphism tests such as the Weisfeiler‑Lehman (WL) test.

Meta AI Research Scientist Hanqing Zeng proposes subgraph‑centric solutions. By training GNNs on proportionally scaled subgraphs, one can approximate full‑graph training while reducing computational and storage costs. Subgraphs also serve as enriched topological information, enabling new GNN modules that surpass full‑graph GNNs in isomorphism testing.

Future work must balance efficiency and expressivity; Zeng suggests jointly optimizing node‑level and graph‑level tasks with shared subgraph‑GNN cores.

Table of Contents

1. Fundamentals of Graph Neural Networks

2. Scalable Applications of Subgraph GNNs

3. Expressivity Applications of Subgraph GNNs

4. Future Outlook

1. Graph Neural Networks and Graph Representation Learning

Graph representation learning includes node, edge, and graph embeddings. Node embeddings are generated per vertex, while graph embeddings are obtained by pooling node embeddings.

2. Subgraph GNN vs. Full‑Graph GNN

Differences lie in topology acquisition, feature extraction, message passing, and pooling. Subgraphs are parts of the full graph; computations on subgraphs can be reused for the whole graph.

3. Existing Problems of GNNs

Industrial graphs are massive, causing scalability and expressivity issues. Full‑graph GNNs struggle with computational complexity, and traditional message‑passing GNNs are theoretically limited to 1‑WL discriminative power.

4. Recent Works

Recent papers focus on subgraph sampling, subgraph‑enhanced message passing, and novel architectures.

Subgraph GNNs for Scalability

GraphSAINT samples subgraphs that retain the original graph’s characteristics, enabling mini‑batch training with reduced complexity. By limiting neighbor counts, it prevents exponential growth of computation.

GraphSAINT’s pipeline: (1) importance/node/edge sampling, random walk, or variants to obtain subgraphs; (2) neural network computation on each subgraph; (3) normalization to mitigate sampling bias; (4) variance reduction and optional Cluster‑GNN as another sampling scheme.

Overall, subgraph sampling reduces cost while approximating full‑graph results.

Subgraph GNNs for Expressivity

Traditional GNNs are bounded by 1‑WL. Subgraph‑based methods such as Shadow‑GNN treat each subgraph as a “fingerprint” for a target node, allowing deeper GNNs (e.g., 5 layers) on small local subgraphs, thereby surpassing 1‑WL.

Nested GNNs first compute subgraph embeddings (inner GNN) and then pool them globally (outer GNN), achieving higher expressive power.

GNN‑AK extends Nested GNN by stacking multiple subgraph embeddings, further enhancing expressivity beyond 1‑WL and even distinguishing some 3‑WL‑indistinguishable graphs. Larger k‑hop subgraphs increase expressive power.

OSAN defines the set of all k‑node subgraphs to generate richer initial colors for WL, effectively enhancing node features. ESAN adds inter‑subgraph message passing by aggregating outputs from the same layer across different subgraphs, further enriching information flow.

Edge‑deletion based subgraph construction for ESAN demonstrates multiple ways to generate subgraphs by removing edges.

Future Outlook

Scalability and expressivity often conflict: more expressive subgraph GNNs are computationally heavy. Challenges include handling a massive number of subgraphs, exponential growth with k‑hop depth, and the sheer count of node‑deleted subgraphs. Further sampling strategies are needed to retain expressivity while reducing cost.

Different downstream tasks impose distinct requirements: molecular graphs favor embedding tasks, while node classification on social networks demands scalable solutions.

Future work may combine Shadow‑GNN with task‑specific subgraph GNNs to achieve a better balance between scalability and expressivity, applying small, high‑expressivity subgraphs to massive social networks.

Thank you for reading.