Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality

• URL: http://arxiv.org/abs/2501.03113v2
• Date: Mon, 07 Jul 2025 23:34:36 GMT
• Title: Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
• Authors: Joshua Southern, Yam Eitan, Guy Bar-Shalom, Michael Bronstein, Haggai Maron, Fabrizio Frasca,
• Abstract summary: Subgraph GNNs have emerged as promising architectures that overcome the limitations of Graph Neural Networks (GNNs) by processing bags of subgraphs.<n>Subgraph GNNs process bags whose size grows linearly in the number of nodes, hindering their applicability to larger graphs.<n>We propose an effective and easy-to-implement approach to dramatically alleviate the computational cost of Subgraph GNNs.
• Score: 16.85143734063591
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Subgraph GNNs have emerged as promising architectures that overcome the expressiveness limitations of Graph Neural Networks (GNNs) by processing bags of subgraphs. Despite their compelling empirical performance, these methods are afflicted by a high computational complexity: they process bags whose size grows linearly in the number of nodes, hindering their applicability to larger graphs. In this work, we propose an effective and easy-to-implement approach to dramatically alleviate the computational cost of Subgraph GNNs and unleash broader applications thereof. Our method, dubbed HyMN, leverages walk-based centrality measures to sample a small number of relevant subgraphs and drastically reduce the bag size. By drawing a connection to perturbation analysis, we highlight the strength of the proposed centrality-based subgraph sampling, and further prove that these walk-based centralities can be additionally used as Structural Encodings for improved discriminative power. A comprehensive set of experimental results demonstrates that HyMN provides an effective synthesis of expressiveness, efficiency, and downstream performance, unlocking the application of Subgraph GNNs to dramatically larger graphs. Not only does our method outperform more sophisticated subgraph sampling approaches, it is also competitive, and sometimes better, than other state-of-the-art approaches for a fraction of their runtime.

Related papers

• Self-supervised Subgraph Neural Network With Deep Reinforcement Walk Exploration [13.489730726871421]
  Graph data represents complex real-world phenomena like chemical compounds, protein structures, and social networks. Traditional Graph Neural Networks (GNNs) primarily utilize the message-passing mechanism, but their expressive power is limited and their prediction lacks explainability. Subgraph neural networks (SGNNs) and GNN explainers have emerged as potential solutions, but each has its limitations. We propose a novel framework that integrates SGNNs with the generation approach of GNN explainers, named the Reinforcement Walk Exploration SGNN (RWE-SGNN)
  arXiv  Detail & Related papers  (2025-02-03T20:40:33Z)
• FIT-GNN: Faster Inference Time for GNNs Using Coarsening [1.323700980948722]
  coarsening-based methods are used to reduce the graph into a smaller graph, resulting in faster computation.<n>Prior research has not adequately addressed the computational costs during the inference phase.<n>This paper presents a novel approach to improve the scalability of GNNs by reducing computational burden during both training and inference phases.
  arXiv  Detail & Related papers  (2024-10-19T06:27:24Z)
• Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks [37.41604955004456]
  Graph neural networks (GNNs) have demonstrated remarkable success in graph representation learning. Various sampling approaches have been proposed to scale GNNs to applications with large-scale graphs.
  arXiv  Detail & Related papers  (2024-10-07T18:29:02Z)
• A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening [18.688057947275112]
  Subgraph GNNs enhance message-passing GNNs expressivity by representing graphs as sets of subgraphs.<n>Previous approaches attempted to generate smaller subsets of subgraphs through random or learnable sampling.<n>This paper introduces a new Subgraph GNN framework to address these issues.
  arXiv  Detail & Related papers  (2024-06-13T16:29:06Z)
• Continuous Spiking Graph Neural Networks [43.28609498855841]
  Continuous graph neural networks (CGNNs) have garnered significant attention due to their ability to generalize existing discrete graph neural networks (GNNs) We introduce the high-order structure of COS-GNN, which utilizes the second-order ODE for spiking representation and continuous propagation. We provide the theoretical proof that COS-GNN effectively mitigates the issues of exploding and vanishing gradients, enabling us to capture long-range dependencies between nodes.
  arXiv  Detail & Related papers  (2024-04-02T12:36:40Z)
• HGAttack: Transferable Heterogeneous Graph Adversarial Attack [63.35560741500611]
  Heterogeneous Graph Neural Networks (HGNNs) are increasingly recognized for their performance in areas like the web and e-commerce. This paper introduces HGAttack, the first dedicated gray box evasion attack method for heterogeneous graphs.
  arXiv  Detail & Related papers  (2024-01-18T12:47:13Z)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  A particular line of work proposed subgraph GNNs that use subgraph information to improve GNNs' expressivity and achieved great success. Such effectivity sacrifices the efficiency of GNNs by enumerating all possible subgraphs. We propose Magnetic Graph Neural Network (MAG-GNN), a reinforcement learning (RL) boosted GNN, to solve the problem.
  arXiv  Detail & Related papers  (2023-10-29T20:32:21Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• Bregman Graph Neural Network [27.64062763929748]
  In node classification tasks, the smoothing effect induced by GNNs tends to assimilate representations and over-homogenize labels of connected nodes. We propose a novel bilevel optimization framework for GNNs inspired by the notion of Bregman distance.
  arXiv  Detail & Related papers  (2023-09-12T23:54:24Z)
• Information Flow in Graph Neural Networks: A Clinical Triage Use Case [49.86931948849343]
  Graph Neural Networks (GNNs) have gained popularity in healthcare and other domains due to their ability to process multi-modal and multi-relational graphs. We investigate how the flow of embedding information within GNNs affects the prediction of links in Knowledge Graphs (KGs) Our results demonstrate that incorporating domain knowledge into the GNN connectivity leads to better performance than using the same connectivity as the KG or allowing unconstrained embedding propagation.
  arXiv  Detail & Related papers  (2023-09-12T09:18:12Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptive Residual Module [65.81781176362848]
  Graph Neural Networks (GNNs) can learn from graph-structured data through neighborhood information aggregation. As the number of layers increases, node representations become indistinguishable, which is known as over-smoothing. We propose a textbfPosterior-Sampling-based, Node-distinguish Residual module (PSNR).
  arXiv  Detail & Related papers  (2023-05-09T12:03:42Z)
• Task-Agnostic Graph Neural Network Evaluation via Adversarial Collaboration [11.709808788756966]
  GraphAC is a principled, task-agnostic, and stable framework for evaluating Graph Neural Network (GNN) research for molecular representation learning. We introduce a novel objective function: the Competitive Barlow Twins, that allow two GNNs to jointly update themselves from direct competitions against each other.
  arXiv  Detail & Related papers  (2023-01-27T03:33:11Z)
• Spiking Variational Graph Auto-Encoders for Efficient Graph Representation Learning [10.65760757021534]
  We propose an SNN-based deep generative method, namely the Spiking Variational Graph Auto-Encoders (S-VGAE) for efficient graph representation learning. We conduct link prediction experiments on multiple benchmark graph datasets, and the results demonstrate that our model consumes significantly lower energy with the performances superior or comparable to other ANN- and SNN-based methods for graph representation learning.
  arXiv  Detail & Related papers  (2022-10-24T12:54:41Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
  GNNAutoScale (GAS) is a framework for scaling arbitrary message-passing GNNs to large graphs. Gas prunes entire sub-trees of the computation graph by utilizing historical embeddings from prior training iterations. Gas reaches state-of-the-art performance on large-scale graphs.
  arXiv  Detail & Related papers  (2021-06-10T09:26:56Z)
• 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)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  Graph Neural Networks (GNNs) have made significant advances on several fundamental inference tasks. Despite GNNs' impressive performance, it has been observed that carefully crafted perturbations on graph structures lead them to make wrong predictions. We propose a general framework which leverages the greedy search algorithms and zeroth-order methods to obtain robust GNNs.
  arXiv  Detail & Related papers  (2020-02-25T15:17:58Z)

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.