Towards understanding and avoiding limitations of convolutions on graphs
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Alternative Title(s)
Abstract
Many challenging tasks involve data with an inherent graph structure. Examples of such graphs include molecules, road networks, and transaction records. As such data becomes increasingly available, the need for methods that can effectively leverage graphstructured data grows accordingly. While message-passing neural networks (MPNNs) have shown promising results, their impact on real-world applications remains limited. Although various phenomena have been identified as possible causes that limit the performance of MPNNs, 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 and analyze 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 dominantly amplified as more message-passing steps are applied. These properties lead to the observable phenomenon of rank collapse of node
representations, which we identify as a generalization of the established over-smoothing phenomenon. By generalizing and decomposing over-smoothing, we enable a deeper understanding of MPNNs, more targeted solutions, the identification of the relevance of each property, and more precise communication within the field.
To avoid SCA, we show that utilizing multiple computational graphs or edge relations is necessary. We propose the multi-relational split (MRS) framework, which transforms any existing MPNN into a variant that employs multiple edge relations. We identify edge splitting properties that enable the resulting MPNN to avoid SCA. Additionally, we define the spectral graph convolution for multiple feature channels (MIMO-GC), which naturally uses multiple computational graphs. We propose localized MIMO-GCs (LMGC) as a framework for MPNNs that approximate the MIMO-GC and inherit its beneficial properties.We show that LMGCs can avoid SCA and be injective on multisets.
To address CD, we demonstrate the close connection between MPNNs and the Page-Rank algorithm. This connection allows us to transfer insights and modifications from PageRank to MPNNs. Based on personalized PageRank, we propose a variant of MPNNs that similarly allows for infinitely many message-passing iterations, while preserving initial node features.
Collectively, these results contribute to a more complete theoretical understanding of MPNNs, allowing future research to be more targeted. Our findings also establish frameworks for constructing MPNNs that exhibit favorable properties.
Description
Table of contents
Keywords
Machine learning, Graph, Neural networks
Subjects based on RSWK
Maschinelles Lernen, Graph, Neuronales Netz