Rethinking GNN Expressive Power from a Distributed Computational Model Perspective

• URL: http://arxiv.org/abs/2410.01308v3
• Date: Wed, 28 May 2025 11:20:36 GMT
• Title: Rethinking GNN Expressive Power from a Distributed Computational Model Perspective
• Authors: Guanyu Cui, Yuhe Guo, Zhewei Wei, Hsin-Hao Su,
• Abstract summary: We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness.<n>We show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems.<n>Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective.
• Score: 21.723600297533835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The success of graph neural networks (GNNs) has motivated theoretical studies on their expressive power, often through alignments with the Weisfeiler-Lehman (WL) tests. However, such analyses typically focus on the ability of GNNs to distinguish between graph structures, rather than to compute or approximate specific function classes. The latter is more commonly studied in machine learning theory, including results such as the Turing completeness of recurrent networks and the universal approximation property of feedforward networks. We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness. Within this framework, we show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems. We also show that the lower bound on a GNN's capacity (depth multiplied by width) to simulate one iteration of the WL test actually grows nearly linearly with graph size, indicating that the WL test is not locally computable and is misaligned with message-passing GNNs. Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective. Finally, we highlight several open problems regarding GNN expressiveness 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 of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  Graph neural networks (GNNs) have demonstrated their effectiveness in various tasks supported by their generalization capabilities. In this paper, we examine GNNs that operate on geometric graphs generated from manifold models. Our analysis reveals the robustness of the GNN generalization in the presence of such model mismatch.
  arXiv  Detail & Related papers  (2024-08-25T16:00:44Z)
• LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework [30.54068909225463]
  We aim to streamline the GNN design process and leverage the advantages of Large Language Models (LLMs) to improve the performance of GNNs on downstream tasks. We formulate a new paradigm, coined "LLMs-as-Consultants," which integrates LLMs with GNNs in an interactive manner. We empirically evaluate the effectiveness of LOGIN on node classification tasks across both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2024-05-22T18:17:20Z)
• Unleash Graph Neural Networks from Heavy Tuning [33.948899558876604]
  Graph Neural Networks (GNNs) are deep-learning architectures designed for graph-type data. We propose a graph conditional latent diffusion framework (GNN-Diff) to generate high-performing GNNs directly by learning from checkpoints saved during a light-tuning coarse search.
  arXiv  Detail & Related papers  (2024-05-21T06:23:47Z)
• The Expressive Power of Graph Neural Networks: A Survey [9.08607528905173]
  We conduct a first survey for models for enhancing expressive power under different forms of definition. The models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.
  arXiv  Detail & Related papers  (2023-08-16T09:12:21Z)
• 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)
• Understanding and Improving Deep Graph Neural Networks: A Probabilistic Graphical Model Perspective [22.82625446308785]
  We propose a novel view for understanding graph neural networks (GNNs) In this work, we focus on deep GNNs and propose a novel view for understanding them. We design a more powerful GNN: coupling graph neural network (CoGNet)
  arXiv  Detail & Related papers  (2023-01-25T12:02:12Z)
• 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)
• EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks [51.42338058718487]
  Graph Neural Networks (GNNs) have received extensive research attention for their promising performance in graph machine learning. Existing approaches, such as GCN and GPRGNN, are not robust in the face of homophily changes on test graphs. We propose EvenNet, a spectral GNN corresponding to an even-polynomial graph filter.
  arXiv  Detail & Related papers  (2022-05-27T10:48:14Z)
• 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)
• Graph Neural Networks with Parallel Neighborhood Aggregations for Graph Classification [14.112444998191698]
  We focus on graph classification using a graph neural network (GNN) model that precomputes the node features using a bank of neighborhood aggregation graph operators arranged in parallel. These GNN models have a natural advantage of reduced training and inference time due to the precomputations. We demonstrate via numerical experiments that the developed model achieves state-of-the-art performance on many diverse real-world datasets.
  arXiv  Detail & Related papers  (2021-11-22T19:19:40Z)
• Edge-Level Explanations for Graph Neural Networks by Extending Explainability Methods for Convolutional Neural Networks [33.20913249848369]
  Graph Neural Networks (GNNs) are deep learning models that take graph data as inputs, and they are applied to various tasks such as traffic prediction and molecular property prediction. We extend explainability methods for CNNs, such as Local Interpretable Model-Agnostic Explanations (LIME), Gradient-Based Saliency Maps, and Gradient-Weighted Class Activation Mapping (Grad-CAM) to GNNs. The experimental results indicate that the LIME-based approach is the most efficient explainability method for multiple tasks in the real-world situation, outperforming even the state-of-the
  arXiv  Detail & Related papers  (2021-11-01T06:27:29Z)
• 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)
• GNNLens: A Visual Analytics Approach for Prediction Error Diagnosis of Graph Neural Networks [42.222552078920216]
  Graph Neural Networks (GNNs) aim to extend deep learning techniques to graph data. GNNs behave like a black box with their details hidden from model developers and users. It is therefore difficult to diagnose possible errors of GNNs. This paper fills the research gap with an interactive visual analysis tool, GNNLens, to assist model developers and users in understanding and analyzing GNNs.
  arXiv  Detail & Related papers  (2020-11-22T16:09:08Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  Graph Neural Networks (GNNs) have risen to prominence in learning representations for graph structured data. In this work, we establish mathematically that the aggregation processes in a group of representative GNN models can be regarded as solving a graph denoising problem. We instantiate a novel GNN model, ADA-UGNN, derived from UGNN, to handle graphs with adaptive smoothness across nodes.
  arXiv  Detail & Related papers  (2020-10-05T04:57:18Z)
• 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)
• Attentive Graph Neural Networks for Few-Shot Learning [74.01069516079379]
  Graph Neural Networks (GNN) has demonstrated the superior performance in many challenging applications, including the few-shot learning tasks. Despite its powerful capacity to learn and generalize the model from few samples, GNN usually suffers from severe over-fitting and over-smoothing as the model becomes deep. We propose a novel Attentive GNN to tackle these challenges, by incorporating a triple-attention mechanism.
  arXiv  Detail & Related papers  (2020-07-14T07:43:09Z)
• 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)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  Markov Logic Networks (MLNs) can be used to address many knowledge graph problems. Inference in MLN is computationally intensive, making the industrial-scale application of MLN very difficult. We propose a graph neural network (GNN) variant, named ExpressGNN, which strikes a nice balance between the representation power and the simplicity of the model.
  arXiv  Detail & Related papers  (2020-01-29T23:34:36Z)

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.