An Empirical Study of Realized GNN Expressiveness

• URL: http://arxiv.org/abs/2304.07702v4
• Date: Sat, 1 Jun 2024 08:37:02 GMT
• Title: An Empirical Study of Realized GNN Expressiveness
• Authors: Yanbo Wang, Muhan Zhang,
• Abstract summary: We study the realized expressive power that a practical model instance can achieve using a novel expressiveness dataset, BREC. We synthetically test 23 models with higher-than-1-WL expressiveness on BREC. Our experiment gives the first thorough measurement of the realized expressiveness of those state-of-the-art beyond-1-WL GNN models.
• Score: 27.458151256734947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Research on the theoretical expressiveness of Graph Neural Networks (GNNs) has developed rapidly, and many methods have been proposed to enhance the expressiveness. However, most methods do not have a uniform expressiveness measure except for a few that strictly follow the $k$-dimensional Weisfeiler-Lehman ($k$-WL) test hierarchy, leading to difficulties in quantitatively comparing their expressiveness. Previous research has attempted to use datasets for measurement, but facing problems with difficulty (any model surpassing 1-WL has nearly 100% accuracy), granularity (models tend to be either 100% correct or near random guess), and scale (only several essentially different graphs involved). To address these limitations, we study the realized expressive power that a practical model instance can achieve using a novel expressiveness dataset, BREC, which poses greater difficulty (with up to 4-WL-indistinguishable graphs), finer granularity (enabling comparison of models between 1-WL and 3-WL), a larger scale (consisting of 800 1-WL-indistinguishable graphs that are non-isomorphic to each other). We synthetically test 23 models with higher-than-1-WL expressiveness on BREC. Our experiment gives the first thorough measurement of the realized expressiveness of those state-of-the-art beyond-1-WL GNN models and reveals the gap between theoretical and realized expressiveness. Dataset and evaluation codes are released at: https://github.com/GraphPKU/BREC.

Related papers

• Enhanced Expressivity in Graph Neural Networks with Lanczos-Based Linear Constraints [7.605749412696919]
  Graph Neural Networks (GNNs) excel in handling graph-structured data but often underperform in link prediction tasks. We present a novel method to enhance the expressivity of GNNs by embedding induced subgraphs into the graph Laplacian matrix's eigenbasis. Our method achieves 20x and 10x speedup by only requiring 5% and 10% data from the PubMed and OGBL-Vessel datasets.
  arXiv  Detail & Related papers  (2024-08-22T12:22:00Z)
• Path Neural Networks: Expressive and Accurate Graph Neural Networks [23.824156607376697]
  Graph neural networks (GNNs) have recently become the standard approach for learning with graph-structured data. In this paper, we propose Path Neural Networks (PathNNs), a model that updates node representations by aggregating paths emanating from nodes. We prove that two of these variants are strictly more powerful than the 1-WL algorithm, and we experimentally validate our theoretical results.
  arXiv  Detail & Related papers  (2023-06-09T15:11:49Z)
• Probing Graph Representations [77.7361299039905]
  We use a probing framework to quantify the amount of meaningful information captured in graph representations. Our findings on molecular datasets show the potential of probing for understanding the inductive biases of graph-based models. We advocate for probing as a useful diagnostic tool for evaluating graph-based models.
  arXiv  Detail & Related papers  (2023-03-07T14:58:18Z)
• 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)
• 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)
• 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)
• 1-WL Expressiveness Is (Almost) All You Need [3.4012007729454807]
  It has been shown that a message passing neural networks (MPNNs) are at most as expressive as the first-order Weisfeiler-Leman (1-WL) graph isomorphism test. In this work, we analyze if the limited expressiveness is actually a limiting factor for MPNNs and other WL-based models in standard graph datasets.
  arXiv  Detail & Related papers  (2022-02-21T12:05:06Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks [52.121819834353865]
  We show that for many standard transductive node classification benchmarks, we can exceed or match the performance of state-of-the-art GNNs. We call this overall procedure Correct and Smooth (C&S) Our approach exceeds or nearly matches the performance of state-of-the-art GNNs on a wide variety of benchmarks.
  arXiv  Detail & Related papers  (2020-10-27T02:10:52Z)
• 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)
• 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.