Monday Theory: Reconstruction Conjecture + GRL 🏗

A few months back in this channel we discussed the Reconstruction Conjecture as one of the grand challenges still open in graph theory. In simple words, the conjecture says that two graphs are the same iff their decks (one-vertex-deleted subgraphs) are the same. Does it have something to do with GNNs, you ask? It certainly has!

A recently accepted NeurIPS'21 paper Reconstruction for Powerful Graph Representations is dedicated exactly to this connection. We invited the first authors, Leonardo Cotta and Christopher Morris, to explain below the main intuition and experimental results of this wonderful work.


Although GNNs are extremely popular right now, they have clear limitations. Their expressive power is limited by the 1-Weisfeiler-Leman algorithm, a simple heuristic for the graph isomorphism problem. For example, GNNs cannot approximate graph properties such as diameter, radius, girth, and subgraph counts, inspiring architectures based on the more powerful k-dimensional Weisfeiler-Leman algorithm (k-WL). However, such architectures do not scale to large graphs. Hence, it remains an open challenge to design more expressive architectures that scale to large graphs while generalizing to unseen areas.

In our work, we first show how the k-reconstruction of graphs—reconstruction from induced k-vertex subgraphs—induces a natural class of expressive GRL architectures for supervised learning with graphs, denoted k-Reconstruction Neural Networks. We then show how several existing works have their expressive power limited by k-reconstruction. Further, we show how the reconstruction conjecture’s insights lead to a provably most-expressive representation of graphs.

To make our models scalable, we propose k-Reconstruction GNNs, a general tool for boosting the expressive power and performance of GNNs with graph reconstruction. Theoretically, we characterize their expressive power showing that k-Reconstruction GNNs can distinguish graph classes that the 1-WL and 2-WL cannot, such as cycle graphs and strongly regular graphs, respectively. Further, to explain gains in real-world tasks, we show how reconstruction can act as a lower-variance estimator of the risk when the graph-generating distribution is invariant to vertex removals.

Empirically, we show that reconstruction enhances GNNs’ expressive power, making them solve multiple synthetic graph property tasks in the literature not solvable by the original GNN. On real-world datasets, we show that the increase in expressive power coupled with the lower-variance risk estimator boosts GNN’s performance up to 25%. Our theoretical and empirical results combined make another important connection between graph theory and GRL.