Reconstruction for Powerful Graph Representations

2021/10/01 by Leonardo Cotta, Cotta, Leonardo, Christopher Morris +3 · 6 citations
Computer Science · Engineering · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Machine Learning (cs.LG) #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2110.00577

openalex publication_date 2021/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Improving neural networks by preventing co-adaptation of feature detectors
• Neural Network for Graphs: A Contextual Constructive Approach
• Supervised neural networks for the classification of structures
• Order Matters: Sequence to sequence for sets
• Graph Isomorphism in Quasipolynomial Time
• Neural Message Passing for Quantum Chemistry
• Inductive Representation Learning on Large Graphs
• Fast Graph Representation Learning with PyTorch Geometric
• Universal Invariant and Equivariant Graph Neural Networks
• Position-aware Graph Neural Networks
• Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Models
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
• Hyperbolic Graph Convolutional Neural Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• A Deep Learning Approach to Antibiotic Discovery
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• TUDataset: A collection of benchmark datasets for learning with graphs
• The expressive power of kth-order invariant graph networks
• Directional Graph Networks
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural\n Networks
• On Explainability of Graph Neural Networks via Subgraph Explorations
• A Comprehensive Survey on Graph Neural Networks

Cited by

• GoMS: Graph of Molecule Substructure Network for Molecule Property Prediction
• On The Expressive Power of GNN Derivatives
• Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
• Flock: A Knowledge Graph Foundation Model via Learning on Random Walks
• Exact Subgraph Isomorphism Network with Mixed L_0,2 Norm Constraint for Predictive Graph Mining
• Heat Kernel Goes Topological

Related

• How Powerful are Graph Neural Networks?
• Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structure
• Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks
• A Survey on The Expressive Power of Graph Neural Networks
• Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability