Reconstruction for Powerful Graph Representations

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.

Accepted to NeurIPS 2021

References in corpus (13)

• Improving neural networks by preventing co-adaptation of feature detectors
• Fast Graph Representation Learning with PyTorch Geometric
• TUDataset: A collection of benchmark datasets for learning with graphs
• Hyperbolic Graph Convolutional Neural Networks
• On Explainability of Graph Neural Networks via Subgraph Explorations
• Position-aware Graph Neural Networks
• Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Models
• A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• The expressive power of kth-order invariant graph networks
• GraLSP: Graph Neural Networks with Local Structural Patterns

Cited by in corpus (1)

• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings