Reproduce “Reconstruction for Powerful Graph Representations” on OpenResearch

About this paper

Leonardo Cotta, Christopher Morris, Bruno Ribeiro

Researchers from Purdue University and Mila developed k-Reconstruction GNNs, a scalable architecture that enhances Graph Neural Network performance by integrating principles from graph reconstruction theory. The method improves GNNs' expressive power for challenging graph properties and consistently boosts accuracy by up to 25% on real-world molecular datasets through variance reduction.

Key insights

• Graph reconstruction provides a powerful inductive bias for GNNs, significantly enhancing their expressive power to distinguish graph classes (e.g., cycle graphs, CSL graphs) that traditional GNNs cannot.
• Performance improvements on real-world datasets are primarily driven by the reconstruction's ability to act as an inductive bias for invariances to vertex removals, leading to reduced variance in empirical risk and better generalization, even when standard GNNs are theoretically expressive enough.
• The optimal subgraph size ('k') for k-Reconstruction GNNs is generally close to the original graph size ('n'), specifically `k=n-1`, `n-2`, or `n-3`, as removing a few vertices provides sufficient distinguishing information without losing too much global context.

Summary by alphaXiv.