On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles

• URL: http://arxiv.org/abs/2502.03703v1
• Date: Thu, 06 Feb 2025 01:25:22 GMT
• Title: On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles
• Authors: Ziang Chen, Qiao Zhang, Runzhong Wang,
• Abstract summary: This work investigates $k$-hop subgraph GNNs that aggregate information from neighbors with distances up to $k$. We prove that the $k$-hop subgraph GNNs can approximate any permutation-invariant/equivariant continuous function over graphs without cycles of length greater than $2k+1$ within any error tolerance.
• Score: 17.29046077604317
• License:
• Abstract: Graph neural networks (GNNs) have been widely used in graph-related contexts. It is known that the separation power of GNNs is equivalent to that of the Weisfeiler-Lehman (WL) test; hence, GNNs are imperfect at identifying all non-isomorphic graphs, which severely limits their expressive power. This work investigates $k$-hop subgraph GNNs that aggregate information from neighbors with distances up to $k$ and incorporate the subgraph structure. We prove that under appropriate assumptions, the $k$-hop subgraph GNNs can approximate any permutation-invariant/equivariant continuous function over graphs without cycles of length greater than $2k+1$ within any error tolerance. We also provide an extension to $k$-hop GNNs without incorporating the subgraph structure. Our numerical experiments on established benchmarks and novel architectures validate our theory on the relationship between the information aggregation distance and the cycle size.

Related papers

• Global Graph Counterfactual Explanation: A Subgraph Mapping Approach [54.42907350881448]
  Graph Neural Networks (GNNs) have been widely deployed in various real-world applications. Counterfactual explanation aims to find minimum perturbations on input graphs that change the GNN predictions. We propose GlobalGCE, a novel global-level graph counterfactual explanation method.
  arXiv  Detail & Related papers  (2024-10-25T21:39:05Z)
• Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
  We propose textitsubstructure encoding function to uplift the expressive power of any $K$-hop message-passing GNN. Our method is provably more powerful than previous works on $K$-hop graph neural networks and 1-WL subgraph GNNs.
  arXiv  Detail & Related papers  (2024-06-27T15:10:56Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  We propose Spatio-Spectral Graph Networks (S$2$GNNs) S$2$GNNs combine spatially and spectrally parametrized graph filters. We show that S$2$GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs.
  arXiv  Detail & Related papers  (2024-05-29T14:28:08Z)
• An Efficient Subgraph GNN with Provable Substructure Counting Power [32.44487589958533]
  We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs.
  arXiv  Detail & Related papers  (2023-03-19T05:35:59Z)
• From Local to Global: Spectral-Inspired Graph Neural Networks [28.858773653743075]
  Graph Neural Networks (GNNs) are powerful deep learning methods for Non-Euclidean data. MPNNs are message-passing algorithms that aggregate and combine signals in a local graph neighborhood. MPNNs can suffer from issues like over-smoothing or over-squashing.
  arXiv  Detail & Related papers  (2022-09-24T17:19:00Z)
• $p$-Laplacian Based Graph Neural Networks [27.747195341003263]
  Graph networks (GNNs) have demonstrated superior performance for semi-supervised node classification on graphs. We propose a new $p$-Laplacian based GNN model, termed as $p$GNN, whose message passing mechanism is derived from a discrete regularization framework. We show that the new message passing mechanism works simultaneously as low-pass and high-pass filters, thus making $p$GNNs effective on both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2021-11-14T13:16:28Z)
• Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
  Local graph parameters can be added to any Graph Neural Networks (GNNs) architecture. Our results connect GNNs with deep results in finite model theory and finite variable logics.
  arXiv  Detail & Related papers  (2021-06-12T07:43:51Z)
• 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)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  Graph Neural Networks (GNNs) are information processing architectures for signals supported on graphs. They are generalizations of convolutional neural networks (CNNs) in which individual layers contain banks of graph convolutional filters.
  arXiv  Detail & Related papers  (2020-08-04T18:57:36Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  Graphs neural networks (GNNs) learn node features by aggregating and combining neighbor information. GNNs are mostly treated as black-boxes and lack human intelligible explanations. We propose a novel approach, known as XGNN, to interpret GNNs at the model-level.
  arXiv  Detail & Related papers  (2020-06-03T23:52:43Z)

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.