Towards Understanding and Avoiding Limitations of Convolutions on Graphs

• URL: http://arxiv.org/abs/2602.04709v1
• Date: Wed, 04 Feb 2026 16:21:18 GMT
• Title: Towards Understanding and Avoiding Limitations of Convolutions on Graphs
• Authors: Andreas Roth,
• Abstract summary: We provide an in-depth theoretical analysis of message-passing neural networks (MPNNs)<n>We identify several key properties limiting the performance of MPNNs.<n>We propose several frameworks that address these shortcomings.
• Score: 0.152292571922932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While message-passing neural networks (MPNNs) have shown promising results, their real-world impact remains limited. Although various limitations have been identified, their theoretical foundations remain poorly understood, leading to fragmented research efforts. In this thesis, we provide an in-depth theoretical analysis and identify several key properties limiting the performance of MPNNs. Building on these findings, we propose several frameworks that address these shortcomings. We identify two properties exhibited by many MPNNs: shared component amplification (SCA), where each message-passing iteration amplifies the same components across all feature channels, and component dominance (CD), where a single component gets increasingly amplified as more message-passing steps are applied. These properties lead to the observable phenomenon of rank collapse of node representations, which generalizes the established over-smoothing phenomenon. By generalizing and decomposing over-smoothing, we enable a deeper understanding of MPNNs, more targeted solutions, and more precise communication within the field. To avoid SCA, we show that utilizing multiple computational graphs or edge relations is necessary. Our multi-relational split (MRS) framework transforms any existing MPNN into one that leverages multiple edge relations. Additionally, we introduce the spectral graph convolution for multiple feature channels (MIMO-GC), which naturally uses multiple computational graphs. A localized variant, LMGC, approximates the MIMO-GC while inheriting its beneficial properties. To address CD, we demonstrate a close connection between MPNNs and the PageRank algorithm. Based on personalized PageRank, we propose a variant of MPNNs that allows for infinitely many message-passing iterations, while preserving initial node features. Collectively, these results deepen the theoretical understanding of MPNNs.

Related papers

• Position: Message-passing and spectral GNNs are two sides of the same coin [60.47572761832418]
  Graph neural networks (GNNs) are commonly divided into message-passing neural networks (MPNNs) and spectral graph neural networks (SGNs)<n>This paper argues that this divide is mostly artificial, hindering progress in the field.
  arXiv  Detail & Related papers  (2026-02-10T17:53:40Z)
• Improving the Effective Receptive Field of Message-Passing Neural Networks [17.98720458446544]
  We show and theoretically explain the limited Effective Receptive Field problem in MPNNs.<n>We propose an Interleaved Multiscale Message-Passing Neural Networks architecture to address these problems.<n>Our method incorporates a hierarchical coarsening of the graph, enabling message-passing across multiscale representations.
  arXiv  Detail & Related papers  (2025-05-29T07:23:07Z)
• Multigraph Message Passing with Bi-Directional Multi-Edge Aggregations [5.193718340934995]
  MEGA-GNN is a unified framework for message passing on multigraphs.<n>We show that MEGA-GNN is not only permutation equivariant but also universal given a strict total ordering on the edges.<n>Experiments show that MEGA-GNN significantly outperforms state-of-the-art solutions by up to 13% on Anti-Money Laundering datasets.
  arXiv  Detail & Related papers  (2024-11-29T20:15:18Z)
• 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.<n>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)
• Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs [77.42221150848535]
  We propose a novel message passing function called Multiset to Multiset GNN(M2M-GNN) Our theoretical analyses and extensive experiments demonstrate that M2M-GNN effectively alleviates the aforementioned limitations of SMP, yielding superior performance in comparison.
  arXiv  Detail & Related papers  (2024-05-31T07:39:22Z)
• How does over-squashing affect the power of GNNs? [39.52168593457813]
  Graph Neural Networks (GNNs) are the state-of-the-art model for machine learning on graph-structured data. We provide a rigorous analysis to determine which function classes of node features can be learned by an MPNN of a given capacity. We prove that, to guarantee sufficient communication between pairs of nodes, the capacity of the MPNN must be large enough.
  arXiv  Detail & Related papers  (2023-06-06T11:15:53Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• DPGNN: Dual-Perception Graph Neural Network for Representation Learning [21.432960458513826]
  Graph neural networks (GNNs) have drawn increasing attention in recent years and achieved remarkable performance in many graph-based tasks. Most existing GNNs are based on the message-passing paradigm to iteratively aggregate neighborhood information in a single topology space. We present a novel message-passing paradigm, based on the properties of multi-step message source, node-specific message output, and multi-space message interaction.
  arXiv  Detail & Related papers  (2021-10-15T05:47:26Z)
• Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks [68.9026534589483]
  RioGNN is a novel Reinforced, recursive and flexible neighborhood selection guided multi-relational Graph Neural Network architecture. RioGNN can learn more discriminative node embedding with enhanced explainability due to the recognition of individual importance of each relation.
  arXiv  Detail & Related papers  (2021-04-16T04:30:06Z)
• 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)

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.