Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks

• URL: http://arxiv.org/abs/2305.19659v4
• Date: Wed, 05 Nov 2025 19:46:35 GMT
• Title: Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks
• Authors: Shubhajit Roy, Shrutimoy Das, Binita Maity, Anant Kumar, Anirban Dasgupta,
• Abstract summary: Subgraph counting is a fundamental task for analyzing structural patterns in graph-structured data.<n>We propose localized versions of the Weisfeiler-Leman (WL) algorithms to improve both expressivity and computational efficiency for this task.
• Score: 3.993513380816159
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Subgraph counting is a fundamental task for analyzing structural patterns in graph-structured data, with important applications in domains such as computational biology and social network analysis, where recurring motifs reveal functional and organizational properties. In this paper, we propose localized versions of the Weisfeiler-Leman (WL) algorithms to improve both expressivity and computational efficiency for this task. We introduce Local $k$-WL, which we prove to be more expressive than $k$-WL and at most as expressive as $(k+1)$-WL, and provide a characterization of patterns whose subgraph and induced subgraph counts are invariant under Local $k$-WL equivalence. To enhance scalability, we present two variants -- Layer $k$-WL and Recursive $k$-WL -- that achieve greater time and space efficiency compared to applying $k$-WL on the entire graph. Additionally, we propose a novel fragmentation technique that decomposes complex subgraphs into simpler subpatterns, enabling the exact count of all induced subgraphs of size at most $4$ using only $1$-WL, with extensions possible for larger patterns when $k>1$. Building on these ideas, we develop a three-stage differentiable learning framework that combines subpattern counts to compute counts of more complex motifs, bridging combinatorial algorithm design with machine learning approaches. We also compare the expressive power of Local $k$-WL with existing GNN hierarchies and demonstrate that, under bounded time complexity, our methods are more expressive than prior approaches.

Related papers

• <SOG_k>: One LLM Token for Explicit Graph Structural Understanding [57.017902343605364]
  We propose to incorporate one special token SOG_k> to fully represent the Structure Of Graph within a unified token space.<n>SOG_k> empowers LLMs to understand, generate, and reason in a concise and accurate manner.
  arXiv  Detail & Related papers  (2026-02-02T07:55:09Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• How to Make LLMs Strong Node Classifiers? [70.14063765424012]
  Language Models (LMs) are challenging the dominance of domain-specific models, such as Graph Neural Networks (GNNs) and Graph Transformers (GTs)<n>We propose a novel approach that empowers off-the-shelf LMs to achieve performance comparable to state-of-the-art (SOTA) GNNs on node classification tasks.
  arXiv  Detail & Related papers  (2024-10-03T08:27:54Z)
• 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)
• Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning [17.646846505225735]
  We introduce a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, $r$-$ell$MPNN, that can count cycles up to length $r + 2$. Most notably, we show that $r$-$ell$WL can count homomorphisms of cactus graphs. We empirically validate the expressive and counting power of the proposed $r$-$ell$MPNN on several synthetic datasets and present state-of-the-art predictive performance on various real-world datasets.
  arXiv  Detail & Related papers  (2024-03-20T16:58:28Z)
• On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters [9.599347633285637]
  The $k$-dimensional Weisfeiler-Leman ($k$WL) test is a widely-recognized method for verifying graph isomorphism. This paper provides a precise characterization of the WL-dimension of labeled graph motif parameters.
  arXiv  Detail & Related papers  (2023-09-29T08:26:44Z)
• Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
  We uncover misalignments between graph machine learning practitioners' conceptualizations of expressive power and $k$-WL. We argue for extensional definitions and measurement of expressive power based on benchmarks.
  arXiv  Detail & Related papers  (2023-07-11T20:06:12Z)
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman [66.23316415757456]
  Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. We propose an extension, $(k,t)$-FWL, which considers any equivariant set as neighbors instead of all nodes. N$2$-GNN achieves record-breaking results on ZINC-Subset (0.059), outperforming previous SOTA results by 10.6%.
  arXiv  Detail & Related papers  (2023-06-05T21:35:32Z)
• From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks [8.121462458089141]
  We show how to assign labels to nodes to improve expressive power of message passing neural networks. We experimentally prove that our method is universally compatible and capable of improving the expressivity of any base GNN model. Our $k,l$-GNNs achieve superior performance on many synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-05-08T18:00:50Z)
• A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests [30.558563815430418]
  Subgraph neural networks (GNNs) have emerged as an important direction for developing expressive graph neural networks (GNNs) This paper conducts a systematic study of general node-based subgraph GNNs through the lens of Subgraph Weisfeiler-Lehman Tests (SWL) We prove that any node-based subgraph GNN falls into one of the six SWL equivalence classes, among which $mathsfSSWL$ achieves the maximal expressive power.
  arXiv  Detail & Related papers  (2023-02-14T14:42:54Z)
• A Practical, Progressively-Expressive GNN [27.267362661067285]
  Message passing neural networks (MPNNs) have become a dominant flavor of graph neural networks (GNNs) in recent years. MPNNs come with notable limitations; they are at most as powerful as the 1-dimensional Weisfeiler-Leman (1-WL) test in distinguishing graphs in a graph isomorphism testing frame-work. We propose the (k, c)(=)-SETWL hierarchy with greatly reduced complexity from k-WL, achieved by moving from k-tuples of nodes to sets with =k nodes defined over =c connected components in
  arXiv  Detail & Related papers  (2022-10-18T01:27:21Z)
• Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction [61.01337335214126]
  Link prediction is one important application of graph neural networks (GNNs) Most existing GNNs for link prediction are based on one-dimensional Weisfeiler-Lehman (1-WL) test. We study a completely different approach which can directly obtain node pair (link) representations based on textittwo-dimensional Weisfeiler-Lehman (2-WL) tests.
  arXiv  Detail & Related papers  (2022-06-20T04:50:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification [48.087302573188396]
  We propose a novel graph isomorphism test method, namely Twin-WL, which simultaneously passes node labels and node identities. We prove that the two Twin-GNNs both have higher expressive power than traditional message passing GNNs.
  arXiv  Detail & Related papers  (2022-03-22T12:58:03Z)
• Graph Representation Learning with Individualization and Refinement [19.436520792345064]
  Graph Neural Networks (GNNs) have emerged as prominent models for representation learning on graph structured data. In this work, we follow the classical approach of Individualization and Refinement (IR) Our technique lets us learn richer node embeddings while keeping the computational complexity manageable.
  arXiv  Detail & Related papers  (2022-03-17T07:50:48Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  We study tradeoffs of computational cost and expressive power of Graph Neural Networks (GNNs) We show that a new model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. In several cases, the proposed algorithm can greatly reduce computational complexity compared to the existing higher-order $k$-GNNs.
  arXiv  Detail & Related papers  (2020-12-06T03:42:54Z)
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks [4.355567556995855]
  We introduce a new type of MPNN, $ell$-walk MPNNs, which aggregate features along walks of length $ell$ between vertices. We show that $2$-walk MPNNs match 2-WL in expressive power. In particular, to match W[$ell$] in expressive power, we allow $ell-1$ matrix multiplications in each layer.
  arXiv  Detail & Related papers  (2020-06-16T20:24:01Z)
• 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)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)

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.