Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

• URL: http://arxiv.org/abs/2603.14846v2
• Date: Sun, 22 Mar 2026 08:14:20 GMT
• Title: Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
• Abstract summary: We define a generic class of functions that captures most conceivable aggregations for Graph Graph Neural Networks (MP-GNNs)<n>We prove that any MP-GNN model with such aggregations induces only 2-variants of equivalence classes on all graphs.
• Score: 2.233624388203003
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We define a generic class of functions that captures most conceivable aggregations for Message-Passing Graph Neural Networks (MP-GNNs), and prove that any MP-GNN model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is doubly-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2-iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous results state that MP-GNNs match full CR, however they concern a weak, 'non-uniform', notion of distinguishing-power where each graph size may required a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.

Related papers

• Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum [17.27380476408333]
  Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power.<n>We propose a method to provably improve SGNNs' expressivity on simple spectrum graphs.
  arXiv  Detail & Related papers  (2025-06-05T19:26:29Z)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [53.27010448621372]
  We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs with node attributes.<n>We prove a universal approximation theorem for GNNs and bounds generalization for GNNs on any data distribution of attributed graphs.<n>Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points.
  arXiv  Detail & Related papers  (2024-11-08T10:34:24Z)
• Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions? [2.7398542529968477]
  Graph Neural Networks (GNNs) have paved the way for being a cornerstone in graph-related learning tasks.<n>Yet, the ability of GNNs to capture structural interactions within graphs remains under-explored.<n>We propose Graph Partitioning Neural Networks (GPNNs), a novel architecture that efficiently enhances the expressive power of GNNs in learning structural interactions.
  arXiv  Detail & Related papers  (2023-12-14T06:08:35Z)
• Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
  We consider continuous extensions of both $1$-WL and MPNNs to graphons. We show that the continuous variant of $1$-WL delivers an accurate topological characterization of the expressive power of MPNNs on graphons. We also evaluate different MPNN architectures based on their ability to preserve graph distances.
  arXiv  Detail & Related papers  (2023-06-06T14:12:23Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  We propose a novel heterogeneous graph neural network with sequential node representation, namely Seq-HGNN. We conduct extensive experiments on four widely used datasets from Heterogeneous Graph Benchmark (HGB) and Open Graph Benchmark (OGB)
  arXiv  Detail & Related papers  (2023-05-18T07:27:18Z)
• A Topological characterisation of Weisfeiler-Leman equivalence classes [0.0]
  Graph Neural Networks (GNNs) are learning models aimed at processing graphs and signals on graphs. In this article, we rely on the theory of covering spaces to fully characterize the classes of graphs that GNNs cannot distinguish. We show that the number of indistinguishable graphs in our dataset grows super-exponentially with the number of nodes.
  arXiv  Detail & Related papers  (2022-06-23T17:28:55Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching [42.55928561326902]
  Graph neural networks (GNNs) and message passing neural networks (MPNNs) have been proven to be expressive for subgraph structures. We propose dual message passing neural networks (DMPNNs) to enhance the substructure representation learning.
  arXiv  Detail & Related papers  (2021-12-16T10:23:48Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs) first augments node features with certain multi-hop operators on the graph. We prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth.
  arXiv  Detail & Related papers  (2020-10-28T17:59:59Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  Graph neural networks (GNNs) are emerging machine learning models on graphs. Permutation-equivariance and proximity-awareness are two important properties highly desirable for GNNs. We show that existing GNNs, mostly based on the message-passing mechanism, cannot simultaneously preserve the two properties. In order to preserve node proximities, we augment the existing GNNs with node representations.
  arXiv  Detail & Related papers  (2020-09-05T16:46:56Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework [5.835421173589977]
  We cast neural networks defined on graphs as message-passing neural networks (MPNNs) We consider two variants of MPNNs: anonymous MPNNs and degree-aware MPNNs. We obtain lower and upper bounds on the distinguishing power of MPNNs in terms of the distinguishing power of the Weisfeiler-Lehman (WL) algorithm.
  arXiv  Detail & Related papers  (2020-04-06T12:14:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.