Beyond Message Passing: Neural Graph Pattern Machine

• URL: http://arxiv.org/abs/2501.18739v2
• Date: Sun, 25 May 2025 14:54:53 GMT
• Title: Beyond Message Passing: Neural Graph Pattern Machine
• Authors: Zehong Wang, Zheyuan Zhang, Tianyi Ma, Nitesh V Chawla, Chuxu Zhang, Yanfang Ye,
• Abstract summary: We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
• Score: 50.78679002846741
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph learning tasks often hinge on identifying key substructure patterns -- such as triadic closures in social networks or benzene rings in molecular graphs -- that underpin downstream performance. However, most existing graph neural networks (GNNs) rely on message passing, which aggregates local neighborhood information iteratively and struggles to explicitly capture such fundamental motifs, like triangles, k-cliques, and rings. This limitation hinders both expressiveness and long-range dependency modeling. In this paper, we introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures. GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies. Empirical evaluations across four standard tasks -- node classification, link prediction, graph classification, and graph regression -- demonstrate that GPM outperforms state-of-the-art baselines. Further analysis reveals that GPM exhibits strong out-of-distribution generalization, desirable scalability, and enhanced interpretability. Code and datasets are available at: https://github.com/Zehong-Wang/GPM.

Related papers

• Generating Large Semi-Synthetic Graphs of Any Size [0.4419843514606336]
  Graph generation is an important area in network science.<n>Recent advancements in deep learning have enabled data-driven methods to learn and generate graphs.<n>We propose Latent Graph Sampling Generation (LGSG) to generate graphs of varying sizes without retraining.
  arXiv  Detail & Related papers  (2025-07-02T21:46:28Z)
• Scalable Graph Generative Modeling via Substructure Sequences [37.64864614356634]
  We introduce Generative Graph Pattern Machine (G$2$PM), a generative Transformer pre-training framework for graphs.<n>G$2$PM represents graph instances as sequences of substructures, and employs generative pre-training over the sequences to learn generalizable, transferable representations.<n>On the ogbn-arxiv benchmark, G$2$PM continues to improve with model sizes up to 60M parameters, outperforming prior generative approaches that plateau at significantly smaller scales.
  arXiv  Detail & Related papers  (2025-05-22T02:16:34Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning [3.6881508872690825]
  We introduce a novel edge filtration-based persistence diagram, named Topological Edge Diagram (TED) TED is mathematically proven to preserve node embedding information as well as contain additional topological information. We propose a neural network based algorithm, named Line Graph Vietoris-Rips (LGVR) Persistence Diagram, that extracts edge information by transforming a graph into its line graph.
  arXiv  Detail & Related papers  (2024-12-23T10:46:44Z)
• LLM-Based Multi-Agent Systems are Scalable Graph Generative Models [73.28294528654885]
  GraphAgent-Generator (GAG) is a novel simulation-based framework for dynamic, text-attributed social graph generation.<n>GAG simulates the temporal node and edge generation processes for zero-shot social graph generation.<n>The resulting graphs exhibit adherence to seven key macroscopic network properties, achieving an 11% improvement in microscopic graph structure metrics.
  arXiv  Detail & Related papers  (2024-10-13T12:57:08Z)
• Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention [12.409982249220812]
  We introduce Graph Attention with Structures (GRASS), a novel GNN architecture, to enhance graph relative attention. GRASS rewires the input graph by superimposing a random regular graph to achieve long-range information propagation. It also employs a novel additive attention mechanism tailored for graph-structured data.
  arXiv  Detail & Related papers  (2024-07-08T06:21:56Z)
• SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
  Graph neural networks (GNNs) have revolutionized the field of machine learning on non-Euclidean data such as graphs and networks. We propose a concatenation-based graph convolution mechanism that injectively updates node representations. We also design a novel graph pooling module, called WL-SortPool, to learn important subgraph patterns in a deep-learning manner.
  arXiv  Detail & Related papers  (2024-04-21T13:11:59Z)
• An end-to-end attention-based approach for learning on graphs [8.552020965470113]
  transformer-based architectures for learning on graphs are motivated by attention as an effective learning mechanism.<n>We propose a purely attention-based approach consisting of an encoder and an attention pooling mechanism.<n>Despite its simplicity, the approach outperforms fine-tuned message passing baselines and recently proposed transformer-based methods on more than 70 node and graph-level tasks.
  arXiv  Detail & Related papers  (2024-02-16T16:20:11Z)
• Expander Graph Propagation [0.0]
  We propose an elegant approach based on propagating information over expander graphs. We show that EGP is able to address all of the above concerns, while requiring minimal effort to set up. We believe our analysis paves the way to a novel class of scalable methods to counter oversquashing in GNNs.
  arXiv  Detail & Related papers  (2022-10-06T15:36:37Z)
• Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
  Modelling long-range dependencies is critical for scene understanding tasks in computer vision. A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive. We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
  arXiv  Detail & Related papers  (2022-09-20T14:41:37Z)
• MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
  We propose an end-to-end model named MentorGNN that aims to supervise the pre-training process of GNNs across graphs. We shed new light on the problem of domain adaption on relational data (i.e., graphs) by deriving a natural and interpretable upper bound on the generalization error of the pre-trained GNNs.
  arXiv  Detail & Related papers  (2022-08-21T15:12:08Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Motif-based Graph Self-Supervised Learning forMolecular Property Prediction [12.789013658551454]
  Graph Neural Networks (GNNs) have demonstrated remarkable success in various molecular generation and prediction tasks. Most existing self-supervised pre-training frameworks for GNNs only focus on node-level or graph-level tasks. We propose a novel self-supervised motif generation framework for GNNs.
  arXiv  Detail & Related papers  (2021-10-03T11:45:51Z)
• Hierarchical graph neural nets can capture long-range interactions [8.067880298298185]
  We study hierarchical message passing models that leverage a multi-resolution representation of a given graph. This facilitates learning of features that span large receptive fields without loss of local information. We introduce Hierarchical Graph Net (HGNet), which for any two connected nodes guarantees existence of message-passing paths of at most logarithmic length.
  arXiv  Detail & Related papers  (2021-07-15T16:24:22Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Graph Information Bottleneck [77.21967740646784]
  Graph Neural Networks (GNNs) provide an expressive way to fuse information from network structure and node features. Inheriting from the general Information Bottleneck (IB), GIB aims to learn the minimal sufficient representation for a given task. We show that our proposed models are more robust than state-of-the-art graph defense models.
  arXiv  Detail & Related papers  (2020-10-24T07:13:00Z)
• 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.