Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

• URL: http://arxiv.org/abs/2403.13749v2
• Date: Wed, 06 Nov 2024 19:37:01 GMT
• Title: Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning
• Authors: Raffaele Paolino, Sohir Maskey, Pascal Welke, Gitta Kutyniok,
• Abstract summary: 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.
• Score: 17.646846505225735
• License:
• Abstract: We introduce $r$-loopy Weisfeiler-Leman ($r$-$\ell{}$WL), 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. This strictly extends classical 1-WL, which can only count homomorphisms of trees and, in fact, is incomparable to $k$-WL for any fixed $k$. 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. The code is available at https://github.com/RPaolino/loopy

Related papers

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• 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)
• Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
  Large language models (LLMs) suffer from hallucinations, especially on knowledge-intensive tasks. Existing works propose to augment LLMs with individual text units retrieved from external knowledge corpora. We propose a framework called Graph Chain-of-thought (Graph-CoT) to augment LLMs with graphs by encouraging LLMs to reason on the graph iteratively.
  arXiv  Detail & Related papers  (2024-04-10T15:41:53Z)
• On dimensionality of feature vectors in MPNNs [49.32130498861987]
  We revisit the classical result of Morris et al.(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test.
  arXiv  Detail & Related papers  (2024-02-06T12:56:55Z)
• 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)
• Improving Expressivity of Graph Neural Networks using Localization [1.323700980948722]
  We analyze the power of Local $k-$WL and prove that it is more expressive than $k-$WL and at most as expressive as $(k+1)-$WL. We also propose a fragmentation technique that guarantees the exact count of all induced subgraphs of size at most 4 using just $1-$WL.
  arXiv  Detail & Related papers  (2023-05-31T08:46:11Z)
• Listing Maximal k-Plexes in Large Real-World Graphs [21.79007529359561]
  Listing dense subgraphs in large graphs plays a key task in varieties of network analysis applications like community detection. In this paper, we continue the research line of listing all maximal $k$-plexes and maximal $k$-plexes of prescribed size. Our first contribution is algorithm ListPlex that lists all maximal $k$-plexes in $O*(gammaD)$ time for each constant $k$, where $gamma$ is a value related to $k$ but strictly smaller than 2, and $D$ is the degeneracy of the graph that is far less
  arXiv  Detail & Related papers  (2022-02-17T16:25:56Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  Existing deep neural methods require $Omega(n2)$ complexity by building up the adjacency matrix. We develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix. During training this autoregressive model can be parallelized with $O(log n)$ synchronization stages.
  arXiv  Detail & Related papers  (2020-06-28T04:37:57Z)
• 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)

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.