Rethinking GNN Expressive Power Research in the Machine Learning Community: Limitations, Issues, and Corrections

• URL: http://arxiv.org/abs/2410.01308v2
• Date: Sat, 15 Feb 2025 12:13:08 GMT
• Title: Rethinking GNN Expressive Power Research in the Machine Learning Community: Limitations, Issues, and Corrections
• Authors: Guanyu Cui, Zhewei Wei, Hsin-Hao Su,
• Abstract summary: We argue that using well-defined computational models is a reasonable approach to characterizing and exploring GNNs' expressive power. We show that the WL test is not locally computable and is misaligned with the message-passing GNNs. We highlight several open problems regarding GNN expressive power for further exploration.
• Score: 21.683245760896313
• License:
• Abstract: The success of graph neural networks (GNNs) has spurred theoretical explorations into their expressive power. In the graph machine learning community, researchers often equate GNNs with the Weisfeiler-Lehman (WL) tests as a foundation for theoretical analysis. However, we identify two major limitations of this approach: (1) the semantics of WL tests involve verifying purely structural equivalences through a set of logical sentences. As a result, they do not align well with the concept of expressive power, which is typically defined as the class of functions that GNNs can express, and they are not well-suited for handling graphs with features; (2) by leveraging communication complexity, we show that the lower bound on a GNN's capacity (depth multiplied by width) to simulate one iteration of the WL test grows almost linearly with the graph size. This finding indicates that the WL test is not locally computable and is misaligned with the message-passing GNNs. Furthermore, we show that allowing unlimited precomputation or directly integrating features computed by external models, while claiming that these precomputations enhance the expressiveness of GNNs, can sometimes lead to issues. Such problems can even be observed in an influential paper published in a top-tier machine learning conference. We argue that using well-defined computational models, such as the CONGEST model from distributed computing, is a reasonable approach to characterizing and exploring GNNs' expressive power. Following this approach, we present some results on the effects of virtual nodes and edges. Finally, we highlight several open problems regarding GNN expressive power for further exploration.

Related papers

• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data. This paper explores the computational limitations of GNNs through the lens of circuit complexity. Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism.
  arXiv  Detail & Related papers  (2025-01-11T05:54:10Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  Graph Neural Networks (GNNs) have emerged as a powerful tool for data-driven learning on various graph domains. We establish new generalization properties and fundamental limits of GNNs in the context of learning so-called identity effects. Our study is motivated by the need to understand the capabilities of GNNs when performing simple cognitive tasks.
  arXiv  Detail & Related papers  (2023-06-30T20:56:38Z)
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity [45.4674360883544]
  We introduce a novel class of expressivity metrics via graph biconnectivity and highlight their importance in both theory and practice. We introduce a principled and more efficient approach, called the Generalized Distance Weisfeiler-Lehman (GD-WL) Practically, we show GD-WL can be implemented by a Transformer-like architecture that preserves and enjoys full parallelizability.
  arXiv  Detail & Related papers  (2023-01-23T15:58:59Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  This paper pinpoints the major source of GNNs' performance gain to their intrinsic capability, by introducing an intermediate model class dubbed as P(ropagational)MLP. We observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training.
  arXiv  Detail & Related papers  (2022-12-18T08:17:32Z)
• Expressiveness and Approximation Properties of Graph Neural Networks [6.1323142294300625]
  We provide an elegant way to obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests. We use tensor language to define Higher-Order Message-Passing Neural Networks (or k-MPNNs), a natural extension of MPNNs. Our approach provides a toolbox with which GNN architecture designers can analyze the separation power of their GNNs.
  arXiv  Detail & Related papers  (2022-04-10T11:33:04Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  Graph Neural Networks (GNNs) have been studied from the lens of expressive power and generalization. We study the dynamics of GNNs by studying deep skip optimization. Our results provide first theoretical support for the success of GNNs.
  arXiv  Detail & Related papers  (2021-05-10T17:59:01Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• 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)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  We show that Folklore Graph Neural Networks (FGNN) are the most expressive architectures proposed so far for a given tensor order. FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms.
  arXiv  Detail & Related papers  (2020-06-28T16:35:45Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  It is known that the current graph neural networks (GNNs) are difficult to make themselves deep due to the problem known as over-smoothing. Multi-scale GNNs are a promising approach for mitigating the over-smoothing problem. We derive the optimization and generalization guarantees of transductive learning algorithms that include multi-scale GNNs.
  arXiv  Detail & Related papers  (2020-06-15T17:06:17Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  Graph Neural Networks (GNNs) are emerging machine learning models on graphs. Most existing GNN models in practice are shallow and essentially feature-centric. We show empirically and analytically that the existing shallow GNNs cannot preserve graph structures well. We propose Eigen-GNN, a plug-in module to boost GNNs ability in preserving graph structures.
  arXiv  Detail & Related papers  (2020-06-08T02:47:38Z)

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.