Towards Faster Graph Partitioning via Pre-training and Inductive Inference

• URL: http://arxiv.org/abs/2409.00670v1
• Date: Sun, 1 Sep 2024 09:11:34 GMT
• Title: Towards Faster Graph Partitioning via Pre-training and Inductive Inference
• Authors: Meng Qin, Chaorui Zhang, Yu Gao, Yibin Ding, Weipeng Jiang, Weixi Zhang, Wei Han, Bo Bai,
• Abstract summary: We propose PR-GPT (Pre-trained & Refined Graph ParTitioning) based on a novel pre-training & refinement paradigm. PR-GPT can ensure faster GP on large-scale graphs without significant quality degradation, compared with running a refinement method from scratch.
• Score: 7.962080448174845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph partitioning (GP) is a classic problem that divides the node set of a graph into densely-connected blocks. Following the IEEE HPEC Graph Challenge and recent advances in pre-training techniques (e.g., large-language models), we propose PR-GPT (Pre-trained & Refined Graph ParTitioning) based on a novel pre-training & refinement paradigm. We first conduct the offline pre-training of a deep graph learning (DGL) model on small synthetic graphs with various topology properties. By using the inductive inference of DGL, one can directly generalize the pre-trained model (with frozen model parameters) to large graphs and derive feasible GP results. We also use the derived partition as a good initialization of an efficient GP method (e.g., InfoMap) to further refine the quality of partitioning. In this setting, the online generalization and refinement of PR-GPT can not only benefit from the transfer ability regarding quality but also ensure high inference efficiency without re-training. Based on a mechanism of reducing the scale of a graph to be processed by the refinement method, PR-GPT also has the potential to support streaming GP. Experiments on the Graph Challenge benchmark demonstrate that PR-GPT can ensure faster GP on large-scale graphs without significant quality degradation, compared with running a refinement method from scratch. We will make our code public at https://github.com/KuroginQin/PRGPT.

Related papers

• A Unified Graph Selective Prompt Learning for Graph Neural Networks [20.595782116049428]
  Graph Prompt Feature (GPF) has achieved remarkable success in adapting pre-trained models for Graph Neural Networks (GNNs) We propose a new unified Graph Selective Prompt Feature learning (GSPF) for GNN fine-tuning.
  arXiv  Detail & Related papers  (2024-06-15T04:36:40Z)
• Inductive Graph Alignment Prompt: Bridging the Gap between Graph Pre-training and Inductive Fine-tuning From Spectral Perspective [13.277779426525056]
  "Graph pre-training and fine-tuning" paradigm has significantly improved Graph Neural Networks(GNNs) However, due to the immense gap of data and tasks between the pre-training and fine-tuning stages, the model performance is still limited. We propose a novel graph prompt based method called Inductive Graph Alignment Prompt(IGAP)
  arXiv  Detail & Related papers  (2024-02-21T06:25:54Z)
• Fine-tuning Graph Neural Networks by Preserving Graph Generative Patterns [13.378277755978258]
  We show that the structural divergence between pre-training and downstream graphs significantly limits the transferability when using the vanilla fine-tuning strategy. We propose G-Tuning to preserve the generative patterns of downstream graphs. G-Tuning demonstrates an average improvement of 0.5% and 2.6% on in-domain and out-of-domain transfer learning experiments.
  arXiv  Detail & Related papers  (2023-12-21T05:17:10Z)
• Learning Large Graph Property Prediction via Graph Segment Training [61.344814074335304]
  We propose a general framework that allows learning large graph property prediction with a constant memory footprint. We refine the GST paradigm by introducing a historical embedding table to efficiently obtain embeddings for segments not sampled for backpropagation. Our experiments show that GST-EFD is both memory-efficient and fast, while offering a slight boost on test accuracy over a typical full graph training regime.
  arXiv  Detail & Related papers  (2023-05-21T02:53:25Z)
• When to Pre-Train Graph Neural Networks? From Data Generation Perspective! [19.239863500722983]
  Graph pre-training aims to acquire transferable knowledge from unlabeled graph data to improve downstream performance. This paper introduces a generic framework W2PGNN to answer the question of when to pre-train. W2PGNN offers three broad applications: providing the application scope of graph pre-trained models, the feasibility of pre-training, and assistance in selecting pre-training data to enhance downstream performance.
  arXiv  Detail & Related papers  (2023-03-29T05:05:02Z)
• 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)
• Similarity-aware Positive Instance Sampling for Graph Contrastive Pre-training [82.68805025636165]
  We propose to select positive graph instances directly from existing graphs in the training set. Our selection is based on certain domain-specific pair-wise similarity measurements. Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
  arXiv  Detail & Related papers  (2022-06-23T20:12:51Z)
• 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)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  We propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL) for jointly and iteratively learning graph structure and graph embedding. Our experiments show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2020-06-21T19:49:15Z)

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.