On the expressive power of message-passing neural networks as global feature map transformers

• URL: http://arxiv.org/abs/2203.09555v1
• Date: Thu, 17 Mar 2022 18:37:21 GMT
• Title: On the expressive power of message-passing neural networks as global feature map transformers
• Authors: Floris Geerts, Jasper Steegmans and Jan Van den Bussche
• Abstract summary: We investigate the power of message-passing neural networks (MPNNs) in their capacity to transform the numerical features stored in the nodes of their input graphs. Our focus is on global expressive power, uniformly over all input graphs, or over graphs of bounded degree with features from a bounded domain.
• Score: 5.040463208115643
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the power of message-passing neural networks (MPNNs) in their capacity to transform the numerical features stored in the nodes of their input graphs. Our focus is on global expressive power, uniformly over all input graphs, or over graphs of bounded degree with features from a bounded domain. Accordingly, we introduce the notion of a global feature map transformer (GFMT). As a yardstick for expressiveness, we use a basic language for GFMTs, which we call MPLang. Every MPNN can be expressed in MPLang, and our results clarify to which extent the converse inclusion holds. We consider exact versus approximate expressiveness; the use of arbitrary activation functions; and the case where only the ReLU activation function is allowed.

Related papers

• Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs [34.8056394030225]
  We propose a new concept called fractal nodes, inspired by the fractal structure observed in real-world networks.<n>We show that fractal nodes alleviate the over-squashing problem by providing direct shortcut connections.<n>Experiment results show that our method improves the expressive power of MPNNs and achieves comparable or better performance to graph Transformers.
  arXiv  Detail & Related papers  (2025-11-17T06:11:52Z)
• LEAP: Local ECT-Based Learnable Positional Encodings for Graphs [15.740515132423205]
  Graph positional encoding (PE) has emerged as a promising direction to address these limitations.<n>We propose LEAP, a new end-to-end trainable local structural PE for graphs.<n>Our results underline the potential of LEAP-based encodings as a powerful component for graph representation learning pipelines.
  arXiv  Detail & Related papers  (2025-10-01T10:44:01Z)
• Expressive Power of Graph Transformers via Logic [7.89576199021427]
  We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson ( 2020) and GPS-networks by Ramp'asek et al. (2022)<n>With reals, we show that GPS-networks have the same expressive power as graded modal logic (GML) with the global modality.<n>With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality.
  arXiv  Detail & Related papers  (2025-08-01T20:59:13Z)
• Learning Efficient Positional Encodings with Graph Neural Networks [109.8653020407373]
  We introduce PEARL, a novel framework of learnable PEs for graphs. PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power. Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power.
  arXiv  Detail & Related papers  (2025-02-03T07:28:53Z)
• Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification [9.967313792318606]
  We propose the Structure-aware Multi-token Graph Transformer (Tokenphormer) It generates multiple tokens to capture local and structural information and explore global information at different levels of granularity. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.
  arXiv  Detail & Related papers  (2024-12-19T10:44:18Z)
• Scalable Message Passing Neural Networks: No Need for Attention in Large Graph Representation Learning [15.317501970096743]
  We show that by integrating standard convolutional message passing into a Pre-Layer Normalization Transformer-style block instead of attention, we can produce high-performing deep message-passing-based Graph Neural Networks (GNNs) Results are competitive with the state-of-the-art in large graph transductive learning, without requiring the otherwise computationally and memory-expensive attention mechanism.
  arXiv  Detail & Related papers  (2024-10-29T17:18:43Z)
• Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graph [9.498398257062641]
  We show that operating on multiple directed acyclic graphs always satisfies our condition and propose to obtain these by defining a strict partial ordering of the nodes. We conduct comprehensive experiments that confirm the benefits of operating on multi-relational graphs to achieve more informative node representations.
  arXiv  Detail & Related papers  (2024-09-17T19:16:03Z)
• Probabilistic Graph Rewiring via Virtual Nodes [21.273828055299408]
  Message-passing graph neural networks (MPNNs) have emerged as a powerful paradigm for graph-based machine learning. MPNNs face challenges such as under-reaching and over-squashing, where limited receptive fields and structural bottlenecks hinder information flow in the graph. Here, we propose implicitly rewired message-passing neural networks (IPR-MPNNs), a novel approach that integrates implicit probabilistic graph rewiring into MPNNs.
  arXiv  Detail & Related papers  (2024-05-27T16:11:49Z)
• Contextualized Messages Boost Graph Representations [1.5178009359320295]
  This paper investigates the ability of graph networks (GNNs) to process data that may be represented as graphs. It shows that only a few GNNs are investigated across all levels of capability. A mathematical discussion on the relationship between SIRGCN and widely used GNNs is laid out to put the contribution into context.
  arXiv  Detail & Related papers  (2024-03-19T08:05:49Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  Graph Networks (GNN) are inherently limited in their expressive power. This paper introduces an alternative power hierarchy based on the ability of GNNs to calculate equivariants of certain degree. These enhanced GNNs demonstrate state-of-the-art results in experiments across multiple graph learning benchmarks.
  arXiv  Detail & Related papers  (2023-02-22T18:53:38Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  We mathematically analyze the power of RPE-based Transformers regarding whether the model is capable of approximating any continuous sequence-to-sequence functions. We present a negative result by showing there exist continuous sequence-to-sequence functions that RPE-based Transformers cannot approximate no matter how deep and wide the neural network is. We develop a novel attention module, called Universal RPE-based (URPE) Attention, which satisfies the conditions.
  arXiv  Detail & Related papers  (2022-05-26T14:51:30Z)
• Graph Neural Networks with Learnable Structural and Positional Representations [83.24058411666483]
  A major issue with arbitrary graphs is the absence of canonical positional information of nodes. We introduce Positional nodes (PE) of nodes, and inject it into the input layer, like in Transformers. We observe a performance increase for molecular datasets, from 2.87% up to 64.14% when considering learnable PE for both GNN classes.
  arXiv  Detail & Related papers  (2021-10-15T05:59:15Z)
• MSG-Transformer: Exchanging Local Spatial Information by Manipulating Messenger Tokens [129.10351459066501]
  We propose a specialized token for each region that serves as a messenger (MSG) By manipulating these MSG tokens, one can flexibly exchange visual information across regions. We then integrate the MSG token into a multi-scale architecture named MSG-Transformer.
  arXiv  Detail & Related papers  (2021-05-31T17:16:42Z)
• Rethinking Global Context in Crowd Counting [70.54184500538338]
  A pure transformer is used to extract features with global information from overlapping image patches. Inspired by classification, we add a context token to the input sequence, to facilitate information exchange with tokens corresponding to image patches.
  arXiv  Detail & Related papers  (2021-05-23T12:44:27Z)
• Building powerful and equivariant graph neural networks with structural message-passing [74.93169425144755]
  We propose a powerful and equivariant message-passing framework based on two ideas. First, we propagate a one-hot encoding of the nodes, in addition to the features, in order to learn a local context matrix around each node. Second, we propose methods for the parametrization of the message and update functions that ensure permutation equivariance.
  arXiv  Detail & Related papers  (2020-06-26T17:15:16Z)

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.