Relational Pooling for Graph Representations

This work generalizes graph neural networks (GNNs) beyond those based on the Weisfeiler-Lehman (WL) algorithm, graph Laplacians, and diffusions. Our approach, denoted Relational Pooling (RP), draws from the theory of finite partial exchangeability to provide a framework with maximal representation power for graphs. RP can work with existing graph representation models and, somewhat counterintuitively, can make them even more powerful than the original WL isomorphism test. Additionally, RP allows architectures like Recurrent Neural Networks and Convolutional Neural Networks to be used in a theoretically sound approach for graph classification. We demonstrate improved performance of RP-based graph representations over state-of-the-art methods on a number of tasks.

• Publication year

  2019

• Venue

  International Conference on Machine Learning

• Publication date

  2019-03-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1903.02541
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Probabilistic Symmetries and Invariant Neural Networks

  2020cited by this paper
• On the Universality of Invariant Networks

  2019cited by this paper
• Hierarchical Graph Representation Learning with Differentiable Pooling

  2018cited by this paper
• Invariant and Equivariant Graph Networks

  2018cited by this paper
• Pitfalls of Graph Neural Network Evaluation

  2018cited by this paper
• Representation Learning on Graphs with Jumping Knowledge Networks

  2018cited by this paper
• Graph Classification using Structural Attention

  2018cited by this paper
• Deep Models of Interactions Across Sets

  2018cited by this paper
• Relational inductive biases, deep learning, and graph networks

  2018cited by this paper
• Subgraph Pattern Neural Networks for High-Order Graph Evolution Prediction

  2018cited by this paper
• Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs

  2018influential reference
• Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

  2018influential reference
• Graph Pattern Mining and Learning through User-Defined Relations

  2018cited by this paper
• How Powerful are Graph Neural Networks?

  2018influential reference
• Inverse molecular design using machine learning: Generative models for matter engineering

  2018cited by this paper
• enchmark for molecular machine learning †

  2017cited by this paper
• Deep Sets

  2017cited by this paper
• Equivariance Through Parameter-Sharing

  2017cited by this paper
• Kernel Graph Convolutional Neural Networks

  2017cited by this paper
• Neural Message Passing for Quantum Chemistry

  2017cited by this paper
• On the Combinatorial Power of the Weisfeiler-Lehman Algorithm

  2017influential reference
• Representation Learning on Graphs: Methods and Applications

  2017influential reference
• Graph Attention Networks

  2017cited by this paper
• Inductive Representation Learning on Large Graphs

  2017influential reference
• Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs

  2016influential reference
• Tox21Challenge to Build Predictive Models of Nuclear Receptor and Stress Response Pathways as Mediated by Exposure to Environmental Chemicals and Drugs

  2016cited by this paper
• Group Equivariant Convolutional Networks

  2016cited by this paper
• Molecular graph convolutions: moving beyond fingerprints

  2016cited by this paper
• Volumetric and Multi-view CNNs for Object Classification on 3D Data

  2016cited by this paper
• Learning Convolutional Neural Networks for Graphs

  2016influential reference
• Low Data Drug Discovery with One-Shot Learning

  2016cited by this paper
• Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

  2016cited by this paper
• Semi-Supervised Classification with Graph Convolutional Networks

  2016cited by this paper
• DeepTox: Toxicity Prediction using Deep Learning

  2016influential reference
• Geometric Deep Learning: Going beyond Euclidean data

  2016cited by this paper
• A Structural Smoothing Framework For Robust Graph Comparison

  2015cited by this paper
• Convolutional Networks on Graphs for Learning Molecular Fingerprints

  2015influential reference
• Graph Isomorphism, Color Refinement, and Compactness

  2015cited by this paper
• Diffusion-Convolutional Neural Networks

  2015cited by this paper
• Adam: A Method for Stochastic Optimization

  2014cited by this paper
• Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference

  2014cited by this paper
• Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation

  2014cited by this paper
• Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures

  2013influential reference
• Spectral Networks and Locally Connected Networks on Graphs

  2013cited by this paper
• Learning Invariant Representations of Molecules for Atomization Energy Prediction

  2012cited by this paper
• Stochastic Gradient Descent Tricks

  2012cited by this paper
• ImageNet classification with deep convolutional neural networks

  2012cited by this paper
• Weisfeiler-Lehman Graph Kernels

  2011cited by this paper
• Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

  2011influential reference
• Efficient graphlet kernels for large graph comparison

  2009cited by this paper
• The Graph Neural Network Model

  2009cited by this paper
• Maximum Unbiased Validation (MUV) Data Sets for Virtual Screening Based on PubChem Bioactivity Data

  2009influential reference
• Graph limits and exchangeable random graphs

  2007cited by this paper
• Infinite latent feature models and the Indian buffet process

  2005cited by this paper
• Graph Theory and Its Applications

  2004cited by this paper
• The Convergence of Contrastive Divergences

  2004cited by this paper
• 4-Circulant Graphs

  2002cited by this paper
• Graph theory and its applications

  2000cited by this paper
• On the convergence of markovian stochastic algorithms with rapidly decreasing ergodicity rates

  1999cited by this paper
• Long Short-Term Memory

  1997influential reference
• An optimal lower bound on the number of variables for graph identification

  1992influential reference
• An optimal lower bound on the number of variables for graph identification

  1989cited by this paper
• Multilayer feedforward networks are universal approximators

  1989cited by this paper
• Backpropagation Applied to Handwritten Zip Code Recognition

  1989cited by this paper
• Machine learning research

  1981cited by this paper
• Representations for partially exchangeable arrays of random variables

  1981cited by this paper
• A Stochastic Approximation Method

  1951cited by this paper
• La prévision : ses lois logiques, ses sources subjectives

  1937cited by this paper
• Série Scientifique Scientific Series No Unbiased Estimator of the Variance of K-fold Cross-validation No Unbiased Estimator of the Variance of K-fold Cross-validation

  year unknowncited by this paper

• Representing Tuple in Graph with Trail Structure

  2026cites this paper
• Plain Transformers are Surprisingly Powerful Link Predictors

  2026influential citation
• FlowSymm: Physics Aware, Symmetry Preserving Graph Attention for Network Flow Completion

  2026cites this paper
• Diffeomorphism-Equivariant Neural Networks

  2026cites this paper
• XIMP: Cross Graph Inter-Message Passing for Molecular Property Prediction

  2026cites this paper
• Position-aware Hypergraph Message-Passing Neural Network

  2025cites this paper
• Visual Graph Arena: Evaluating Visual Conceptualization of Vision and Multimodal Large Language Models

  2025cites this paper
• HOPSE: Scalable Higher-Order Positional and Structural Encoder for Combinatorial Representations

  2025cites this paper
• Towards Invariance to Node Identifiers in Graph Neural Networks

  2025cites this paper
• Semantic Refinement with LLMs for Graph Representations

  2025cites this paper
• TCIP: Network with topology capture and incongruity perception for sarcasm detection

  2025cites this paper
• Learning Efficient Positional Encodings with Graph Neural Networks

  2025cites this paper
• Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks

  2025cites this paper
• Message Passing on the Edge: Towards Scalable and Expressive GNNs

  2025influential citation
• Beyond Message Passing: Neural Graph Pattern Machine

  2025cites this paper
• HyperSGT: Scalable and Efficient Graph Transformer via Hyper Sparse Attention and Graph Sparsification

  2025cites this paper
• Accurate and Scalable Graph Neural Networks via Message Invariance

  2025cites this paper
• Exact Subgraph Isomorphism Network with Mixed $L_{0,2}$ Norm Constraint for Predictive Graph Mining

  2025cites this paper
• Learning Repetition-Invariant Representations for Polymer Informatics

  2025influential citation
• RoToR: Towards More Reliable Responses for Order-Invariant Inputs

  2025cites this paper
• Generalization Bounds for Canonicalization: A Comparative Study with Group Averaging

  2025cites this paper
• Graph Representation Learning of Multilayer Spatial–Temporal Networks for Stock Predictions

  2025cites this paper
• Efficient Mixed Precision Quantization in Graph Neural Networks

  2025cites this paper
• Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs

  2025cites this paper
• Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs

  2025influential citation
• Regularity in Canonicalized Models: A Theoretical Perspective

  2025cites this paper
• Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality

  2025cites this paper
• Bridging Theory and Practice in Link Representation with Graph Neural Networks

  2025cites this paper
• Architectural change in neural networks using fuzzy vertex pooling

  2025cites this paper
• Graph Adaptive Autoregressive Moving Average Models

  2025influential citation
• Random Search Neural Networks for Efficient and Expressive Graph Learning

  2025cites this paper
• Studying and Improving Graph Neural Network-based Motif Estimation

  2025cites this paper
• Holographic Node Representations: Pre-training Task-Agnostic Node Embeddings

  2025cites this paper
• Synthetic Sentiment Cue Enhanced Graph Relation-Attention Network for Aspect-Level Sentiment Analysis

  2025cites this paper
• Resolving Indirect Calls in Binary Code via Cross-Reference Augmented Graph Neural Networks

  2025cites this paper
• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings

  2025influential citation
• Graph Representation Learning Enhanced Semi-Supervised Feature Selection

  2024cites this paper
• On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks

  2024influential citation
• Revisiting Random Walks for Learning on Graphs

  2024influential citation
• Modeling Brain Functional Networks Using Graph Neural Networks: A Review and Clinical Application

  2024cites this paper
• Deep Homomorphism Networks

  2024cites this paper
• AsEP: Benchmarking Deep Learning Methods for Antibody-specific Epitope Prediction

  2024cites this paper
• Mega: More Efficient Graph Attention for GNNs

  2024cites this paper
• Instruction-Based Molecular Graph Generation with Unified Text-Graph Diffusion Model

  2024cites this paper
• Non-convolutional Graph Neural Networks

  2024influential citation
• Optimizing Federated Graph Learning with Inherent Structural Knowledge and Dual-Densely Connected GNNs

  2024cites this paper
• Foundations and Frontiers of Graph Learning Theory

  2024cites this paper
• PF-GNN: Differentiable particle filtering based approximation of universal graph representations

  2024influential citation
• Rethinking the Effectiveness of Graph Classification Datasets in Benchmarks for Assessing GNNs

  2024cites this paper
• Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodings

  2024cites this paper
• A Scalable and Effective Alternative to Graph Transformers

  2024cites this paper
• SE-VGAE: Unsupervised Disentangled Representation Learning for Interpretable Architectural Layout Design Graph Generation

  2024cites this paper
• Enhancing Size Generalization in Graph Neural Networks through Disentangled Representation Learning

  2024cites this paper
• A Canonicalization Perspective on Invariant and Equivariant Learning

  2024influential citation
• Graph External Attention Enhanced Transformer

  2024cites this paper
• Probabilistic Graph Rewiring via Virtual Nodes

  2024cites this paper
• KAGNNs: Kolmogorov-Arnold Networks meet Graph Learning

  2024cites this paper
• On the Utilization of Unique Node Identifiers in Graph Neural Networks

  2024cites this paper
• GRANOLA: Adaptive Normalization for Graph Neural Networks

  2024cites this paper
• Training-free Graph Neural Networks and the Power of Labels as Features

  2024cites this paper
• Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

  2024cites this paper
• Graph Mamba: Towards Learning on Graphs with State Space Models

  2024cites this paper
• ListT5: Listwise Reranking with Fusion-in-Decoder Improves Zero-shot Retrieval

  2024cites this paper
• Contextualized Messages Boost Graph Representations

  2024cites this paper
• Graph Neural Networks are More Powerful than We Think

  2024cites this paper
• Topology-Informed Graph Transformer

  2024cites this paper
• Baking Symmetry into GFlowNets

  2024cites this paper
• Counting Graph Substructures with Graph Neural Networks

  2024cites this paper
• Weisfeiler-Leman at the margin: When more expressivity matters

  2024cites this paper
• The Expressive Power of Path-Based Graph Neural Networks

  2024influential citation
• GraphSPNs: Sum-Product Networks Benefit From Canonical Orderings

  2024cites this paper
• Universal Normalization Enhanced Graph Representation Learning for Gene Network Prediction

  2023cites this paper
• Exphormer: Sparse Transformers for Graphs

  2023cites this paper
• Recurrent Temporal Revision Graph Networks

  2023cites this paper
• Equivariant Polynomials for Graph Neural Networks

  2023cites this paper
• Are More Layers Beneficial to Graph Transformers?

  2023cites this paper
• An Efficient Subgraph GNN with Provable Substructure Counting Power

  2023cites this paper
• Probabilistically Rewired Message-Passing Neural Networks

  2023cites this paper
• G-Signatures: Global Graph Propagation With Randomized Signatures

  2023cites this paper
• Attending to Graph Transformers

  2023cites this paper
• On the Two Sides of Redundancy in Graph Neural Networks

  2023cites this paper
• Double Permutation Equivariance for Knowledge Graph Completion

  2023cites this paper
• Benchmarking Graph Neural Networks

  2023influential citation
• Graph Contrastive Learning with Positional Representation for Recommendation

  2023cites this paper
• When Geometric Deep Learning Meets Pretrained Protein Language Models

  2023cites this paper
• A Comprehensive Survey of Graph-level Learning

  2023cites this paper
• WL meet VC

  2023cites this paper
• On the Substructure Countability of Graph Neural Networks

  2023influential citation
• Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding

  2023cites this paper
• Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structure

  2023cites this paper
• All in a Row: Compressed Convolution Networks for Graphs

  2023cites this paper
• An Empirical Study of Realized GNN Expressiveness

  2023cites this paper
• A Systematic Approach to Universal Random Features in Graph Neural Networks

  2023influential citation
• Prot2Text: Multimodal Protein's Function Generation with GNNs and Transformers

  2023cites this paper
• Improving Network Delay Predictions Using GNNs

  2023cites this paper
• Cycle to Clique (Cy2C) Graph Neural Network: A Sight to See beyond Neighborhood Aggregation

  2023cites this paper
• Graph Positional and Structural Encoder

  2023cites this paper
• WL meet VC

  2023cites this paper
• Nexus sine qua non : Essentially connected neural networks for spatial-temporal forecasting of multivariate time series

  2023cites this paper
• Substructure Aware Graph Neural Networks

  2023cites this paper