Scalable Expressiveness through Preprocessed Graph Perturbations

• URL: http://arxiv.org/abs/2406.11714v2
• Date: Mon, 5 Aug 2024 18:02:55 GMT
• Title: Scalable Expressiveness through Preprocessed Graph Perturbations
• Authors: Danial Saber, Amirali Salehi-Abari,
• Abstract summary: Graph Neural Networks (GNNs) have emerged as the predominant method for analyzing graph-structured data. We introduce Scalable Expressiveness through Preprocessed Graph Perturbation (SE2P) SE2P offers a flexible balance between scalability and generalizability with four distinct configuration classes. Our results indicate that, depending on the chosen SE2P configuration, the model can enhance generalizability compared to benchmarks while achieving significant speed improvements of up to 8-fold.
• Score: 1.6574413179773764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) have emerged as the predominant method for analyzing graph-structured data. However, canonical GNNs have limited expressive power and generalization capability, thus triggering the development of more expressive yet computationally intensive methods. One such approach is to create a series of perturbed versions of input graphs and then repeatedly conduct multiple message-passing operations on all variations during training. Despite their expressive power, this approach does not scale well on larger graphs. To address this scalability issue, we introduce Scalable Expressiveness through Preprocessed Graph Perturbation (SE2P). This model offers a flexible, configurable balance between scalability and generalizability with four distinct configuration classes. At one extreme, the configuration prioritizes scalability through minimal learnable feature extraction and extensive preprocessing; at the other extreme, it enhances generalizability with more learnable feature extractions, though this increases scalability costs. We conduct extensive experiments on real-world datasets to evaluate the generalizability and scalability of SE2P variants compared to various state-of-the-art benchmarks. Our results indicate that, depending on the chosen SE2P configuration, the model can enhance generalizability compared to benchmarks while achieving significant speed improvements of up to 8-fold.

Related papers

• VecFormer: Towards Efficient and Generalizable Graph Transformer with Graph Token Attention [61.96837866507746]
  VecFormer is an efficient and highly generalizable model for node classification.<n>VecFormer outperforms the existing Graph Transformer in both performance and speed.
  arXiv  Detail & Related papers  (2026-02-23T09:10:39Z)
• GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chaining [25.437138336163827]
  GraphChain is a framework that enables Large Language Models (LLMs) to analyze complex graphs through dynamic sequences of specialized tools.<n>Our approach introduces two key innovations: (1) Progressive Graph Distillation, a reinforcement learning mechanism that generates optimized tool sequences balancing task relevance with information compression, and (2) Structure-aware Test-Time Adaptation, which efficiently tailors tool selection strategies to diverse graph topologies.
  arXiv  Detail & Related papers  (2025-11-01T08:47:05Z)
• 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)
• 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) This framework provides a standardized setting to evaluate GNNs across diverse datasets. We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Towards Scalable and Deep Graph Neural Networks via Noise Masking [59.058558158296265]
  Graph Neural Networks (GNNs) have achieved remarkable success in many graph mining tasks. scaling them to large graphs is challenging due to the high computational and storage costs. We present random walk with noise masking (RMask), a plug-and-play module compatible with the existing model-simplification works.
  arXiv  Detail & Related papers  (2024-12-19T07:48:14Z)
• Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodings [36.58861528662219]
  positional and structural encodings (PSEs) have been integrated into graph neural networks (GNNs) This paper investigates the fine-tuning efficiency, scalability with sample size, generalization and capability of learnable PSEs across diverse graph datasets.
  arXiv  Detail & Related papers  (2024-12-10T10:58:47Z)
• DA-MoE: Addressing Depth-Sensitivity in Graph-Level Analysis through Mixture of Experts [70.21017141742763]
  Graph neural networks (GNNs) are gaining popularity for processing graph-structured data. Existing methods generally use a fixed number of GNN layers to generate representations for all graphs. We propose the depth adaptive mixture of expert (DA-MoE) method, which incorporates two main improvements to GNN.
  arXiv  Detail & Related papers  (2024-11-05T11:46:27Z)
• Enhancing GNNs with Architecture-Agnostic Graph Transformations: A Systematic Analysis [0.4069144210024563]
  This study explores the impact of various graph transformations as pre-processing steps on the performance of common graph neural network (GNN) architectures across standard datasets. Our findings reveal that certain transformations, particularly those augmenting node features with centrality measures, consistently improve expressivity. However, these gains come with trade-offs, as methods like graph encoding, while enhancing expressivity, introduce numerical inaccuracies widely-used python packages.
  arXiv  Detail & Related papers  (2024-10-11T12:19:17Z)
• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• What Can We Learn from State Space Models for Machine Learning on Graphs? [11.38076877943004]
  We propose Graph State Space Convolution (GSSC) as a principled extension of State Space Models (SSMs) to graph-structured data. By leveraging global permutation-equivariant set aggregation and factorizable graph kernels, GSSC preserves all three advantages of SSMs. Our findings highlight the potential of GSSC as a powerful and scalable model for graph machine learning.
  arXiv  Detail & Related papers  (2024-06-09T15:03:36Z)
• Dynamic Graph Representation Learning via Graph Transformer Networks [41.570839291138114]
  We propose a Transformer-based dynamic graph learning method named Dynamic Graph Transformer (DGT) DGT has spatial-temporal encoding to effectively learn graph topology and capture implicit links. We show that DGT presents superior performance compared with several state-of-the-art baselines.
  arXiv  Detail & Related papers  (2021-11-19T21:44:23Z)
• Graph Contrastive Learning Automated [94.41860307845812]
  Graph contrastive learning (GraphCL) has emerged with promising representation learning performance. The effectiveness of GraphCL hinges on ad-hoc data augmentations, which have to be manually picked per dataset. This paper proposes a unified bi-level optimization framework to automatically, adaptively and dynamically select data augmentations when performing GraphCL on specific graph data.
  arXiv  Detail & Related papers  (2021-06-10T16:35:27Z)
• 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)
• Graph Contrastive Learning with Augmentations [109.23158429991298]
  We propose a graph contrastive learning (GraphCL) framework for learning unsupervised representations of graph data. We show that our framework can produce graph representations of similar or better generalizability, transferrability, and robustness compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-10-22T20:13:43Z)
• Robust Optimization as Data Augmentation for Large-scale Graphs [117.2376815614148]
  We propose FLAG (Free Large-scale Adversarial Augmentation on Graphs), which iteratively augments node features with gradient-based adversarial perturbations during training. FLAG is a general-purpose approach for graph data, which universally works in node classification, link prediction, and graph classification tasks.
  arXiv  Detail & Related papers  (2020-10-19T21:51:47Z)

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.