Abstract
Standard Graph Neural Networks (GNNs) are theoretically limited in their ability to distinguish complex graph structures, often bounded by the 1-dimensional Weisfeiler-Leman (1-WL) isomorphism test. This paper introduces $k$-Reconstruction GNNs, a framework that represents a graph by analyzing its "deck"—the multiset of its subgraphs. By leveraging the mathematical theory of graph reconstruction, the authors create a scalable meta-architecture that boosts the expressive power and real-world performance of any existing GNN architecture.
Introduction
Despite their widespread success, GNNs face a fundamental "glass ceiling" regarding their expressive power. Most popular architectures cannot distinguish between certain non-isomorphic graphs, such as regular graphs or cycles of different lengths, and struggle to compute global properties like diameter or radius. While higher-order GNNs (e.g., $k$-WL GNNs) offer theoretical solutions, they are often computationally expensive and difficult to scale. The challenge lies in enhancing GNN power without sacrificing simplicity or efficiency.
Methodology: The Power of the Deck
The authors draw inspiration from a classic graph theory problem: the Reconstruction Conjecture. This conjecture posits that an undirected graph can be uniquely identified by its "deck"—the collection of all subgraphs formed by deleting exactly one vertex.
The paper proposes three main architectures:
- $k$-Reconstruction Neural Networks: A theoretical model utilizing the most expressive representations of $k$-vertex subgraphs.
- Full Reconstruction Neural Networks: A recursive scheme building representations from the bottom up.
- $k$-Reconstruction GNNs: A practical, scalable version that runs a standard GNN (e.g., GIN or GCN) on a collection of subgraphs.
To ensure scalability, the framework employs subgraph sampling. Instead of processing the entire deck, the model samples a small subset of subgraphs during training. The final representation aggregates these subgraph embeddings, effectively "breaking the symmetry" that typically limits standard message-passing GNNs.
Key Insights
- Symmetry Breaking: Standard GNNs fail on regular graphs because every node appears identical to the message-passing algorithm. Removing a vertex to create subgraphs introduces structural variation that the GNN can detect.
- Hereditary Inductive Bias: Many graph properties (e.g., planarity) are hereditary. The authors prove that reconstruction acts as a lower-variance risk estimator for these properties, aiding generalization.
- Meta-Architecture: The $k$-Reconstruction framework acts as a wrapper, enhancing any base GNN architecture without requiring internal modifications.
Experimental Results
The framework was evaluated across synthetic and real-world benchmarks:
- Synthetic Tasks: On the CSL (Circular Skip Link) dataset, where standard GNNs perform no better than random guessing (~5%), $k$-Reconstruction GNNs achieved 100% accuracy.
- Molecular Datasets: On the ZINC dataset, the framework improved performance by up to 25%.
- OGB Benchmarks: The models matched or exceeded the performance of specialized higher-order GNNs (like 3-WL PPGNs) while remaining significantly simpler to implement.
- Efficiency: Sampling as few as 10-15 subgraphs was found to be sufficient for near-optimal performance, making the method computationally viable for large datasets.
Conclusion
$k$-Reconstruction GNNs provide a powerful yet practical path toward more expressive graph representations. By shifting the focus from the whole graph to its constituent subgraphs, this framework overcomes the theoretical limits of 1-WL GNNs. Future work will explore intelligent subgraph selection and extensions to directed graphs, where the reconstruction theory is more complex.
Summary updated