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.

arXiv commentAccepted to NeurIPS 2021

References in corpus (25)

• Improving neural networks by preventing co-adaptation of feature detectors
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Fast Graph Representation Learning with PyTorch Geometric
• Representation Learning on Graphs with Jumping Knowledge Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• TUDataset: A collection of benchmark datasets for learning with graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Graph Isomorphism in Quasipolynomial Time
• Hyperbolic Graph Convolutional Neural Networks
• Benchmarking Graph Neural Networks
• Order Matters: Sequence to sequence for sets
• Universal Invariant and Equivariant Graph Neural Networks
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• On Explainability of Graph Neural Networks via Subgraph Explorations
• Position-aware Graph Neural Networks
• Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Models
• Probabilistic symmetries and invariant neural networks
• 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
• Directional Graph Networks
• 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 (2)

• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings