Reconstruction for Powerful Graph Representations

Leonardo Cotta, Christopher Morris, Bruno Ribeiro

Graph neural networks (GNNs) have become the standard for learning on graph-structured data, but they suffer from fundamental limitations in expressive power. Theoretically, the ability of standard message-passing GNNs to distinguish different graph structures is upper-bounded by the 1-dimensional Weisfeiler-Leman (1-WL) test. Consequently, they cannot distinguish between certain non-isomorphic graphs (like different types of cycles) and struggle to compute basic properties such as a graph's diameter.

While higher-order GNNs offer more power, they are computationally expensive, difficult to implement, and often fail to outperform well-tuned standard GNNs in practice. This paper introduces a novel framework based on the classical graph theory concept of "graph reconstruction" to significantly boost the expressive power and performance of standard GNNs without sacrificing scalability.

The Power of Graph Reconstruction

The core innovation lies in representing a graph through its subgraphs. In graph theory, the "reconstruction conjecture" posits that a graph can be uniquely identified by its "deck"—the multiset of all its subgraphs formed by deleting exactly one vertex at a time.

A graph G and its deck of subgraphs formed by removing one vertex at a time.

Leveraging this concept, the authors propose two main architectures:

  1. $k$-Reconstruction Neural Networks: A theoretical model that learns representations for all induced subgraphs of size $k$ and aggregates them.
  2. $k$-Reconstruction GNNs: A practical, scalable version that uses standard GNNs (like GIN or GCN) to process the subgraphs instead of relying on a theoretically "most-expressive" representation.

To mitigate the computational cost of processing an entire deck of subgraphs, the framework employs subgraph sampling during training. This makes the method a practical, plug-and-play enhancement for existing GNN architectures.

Key Insights: Why Reconstruction Works

The reconstruction approach provides several distinct advantages for graph representation learning:

  • Breaking Symmetry: Standard GNNs often fail due to local symmetries in a graph. Removing a vertex to create a subgraph breaks these symmetries, making the resulting structures easier for a GNN to distinguish.
  • Hereditary Inductive Bias: Many crucial graph properties (e.g., being a tree, planar, or acyclic) are "hereditary"—if the main graph has the property, its subgraphs do as well. Reconstruction provides a natural inductive bias for learning these tasks.
  • Variance Reduction: The authors demonstrate theoretically that for distributions invariant to vertex removals, reconstruction acts as a lower-variance risk estimator, which leads to better generalization.
  • The Power of $n-1$: Aligning with the classical Reconstruction Conjecture, simply removing one vertex ($k=n-1$) is often sufficient to provide a massive performance boost.

Empirical Results

The authors evaluated their approach across a wide range of synthetic and real-world benchmarks, demonstrating significant improvements.

  • Solving the "Unsolvable": On synthetic tasks where standard GNNs fail (such as Circular Skip Link graphs), $k$-Reconstruction GNNs achieved near 100% accuracy, representing a 10x to 20x improvement over baseline models.
  • Real-World Performance: The method consistently improved performance across nine real-world datasets (including ZINC, ALCHEMY, and various OGBG benchmarks). It boosted GNN performance by up to 5% on OGBG benchmarks and up to 25% on datasets like ZINC.
  • Architecture Agnostic: The reconstruction wrapper successfully improved the performance of GCN, GIN, and PNA architectures alike, demonstrating its versatility as a general tool for the graph representation learning toolkit.

Limitations and Future Directions

While powerful, the approach has limitations. Even with sampling, processing multiple subgraphs per graph incurs a higher computational overhead than a single GNN pass. Furthermore, the Reconstruction Conjecture is known to be false for directed graphs; while the method can still be applied empirically, the theoretical guarantees regarding "most-expressive representations" currently only hold for undirected graphs.

Future work may explore more sophisticated, task-specific sampling strategies to optimize efficiency and further extend the power of graph reconstruction in deep learning.

Summary updated

Abstract

Graph neural networks (GNNs) have limited expressive power, failing to represent many graph classes correctly. While more expressive graph representation learning (GRL) alternatives can distinguish some of these classes, they are significantly harder to implement, may not scale well, and have not been shown to outperform well-tuned GNNs in real-world tasks. Thus, devising simple, scalable, and expressive GRL architectures that also achieve real-world improvements remains an open challenge. In this work, we show the extent to which graph reconstruction---reconstructing a graph from its subgraphs---can mitigate the theoretical and practical problems currently faced by GRL architectures. First, we leverage graph reconstruction to build two new classes of expressive graph representations. Secondly, we show how graph reconstruction boosts the expressive power of any GNN architecture while being a (provably) powerful inductive bias for invariances to vertex removals. Empirically, we show how reconstruction can boost GNN's expressive power---while maintaining its invariance to permutations of the vertices---by solving seven graph property tasks not solvable by the original GNN. Further, we demonstrate how it boosts state-of-the-art GNN's performance across nine real-world benchmark datasets.
BibTeX
@inproceedings{cotta2021reconstruction,
  author = {Leonardo Cotta and Christopher Morris and Bruno Ribeiro},
  title = {{Reconstruction for Powerful Graph Representations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=bgJDUm99Ic9},
}
Figure