Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training

• URL: http://arxiv.org/abs/2312.15520v1
• Date: Sun, 24 Dec 2023 16:07:14 GMT
• Title: Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training
• Authors: Charles Dickens, Eddie Huang, Aishwarya Reganti, Jiong Zhu, Karthik Subbian, Danai Koutra
• Abstract summary: We propose the Coarsening Via Convolution Matching (CONVMATCH) algorithm and a highly scalable variant, A-CONVMATCH, for creating summarized graphs. We evaluate CONVMATCH on six real-world link prediction and node classification graph datasets.
• Score: 22.411609128594982
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph summarization as a preprocessing step is an effective and complementary technique for scalable graph neural network (GNN) training. In this work, we propose the Coarsening Via Convolution Matching (CONVMATCH) algorithm and a highly scalable variant, A-CONVMATCH, for creating summarized graphs that preserve the output of graph convolution. We evaluate CONVMATCH on six real-world link prediction and node classification graph datasets, and show it is efficient and preserves prediction performance while significantly reducing the graph size. Notably, CONVMATCH achieves up to 95% of the prediction performance of GNNs on node classification while trained on graphs summarized down to 1% the size of the original graph. Furthermore, on link prediction tasks, CONVMATCH consistently outperforms all baselines, achieving up to a 2x improvement.

Related papers

• Improving the interpretability of GNN predictions through conformal-based graph sparsification [9.550589670316523]
  Graph Neural Networks (GNNs) have achieved state-of-the-art performance in solving graph classification tasks. We propose a GNN emphtraining approach that finds the most predictive subgraph by removing edges and/or nodes. We rely on reinforcement learning to solve the resulting bi-level optimization with a reward function based on conformal predictions.
  arXiv  Detail & Related papers  (2024-04-18T17:34:47Z)
• Graph Property Prediction on Open Graph Benchmark: A Winning Solution by Graph Neural Architecture Search [37.89305885538052]
  We design a graph neural network framework for graph classification task by introducing PAS(Pooling Architecture Search) We improve it based on the GNN topology design method F2GNN to further improve the performance of the model in the graph property prediction task. It is proved that the NAS method has high generalization ability for multiple tasks and the advantage of our method in processing graph property prediction tasks.
  arXiv  Detail & Related papers  (2022-07-13T08:17:48Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• 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)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations.
  arXiv  Detail & Related papers  (2021-09-24T08:01:23Z)
• GraphTheta: A Distributed Graph Neural Network Learning System With Flexible Training Strategy [5.466414428765544]
  We present a new distributed graph learning system GraphTheta. It supports multiple training strategies and enables efficient and scalable learning on big graphs. This work represents the largest edge-attributed GNN learning task conducted on a billion-scale network in the literature.
  arXiv  Detail & Related papers  (2021-04-21T14:51:33Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects. To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
  arXiv  Detail & Related papers  (2020-07-08T19:48:19Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
  Graph Neural Networks (GNNs) provide a data-driven solution for this task. Existing GNN-based methods, which either respectively embeds two graphs or deploy cross-graph interactions for whole graph pairs, are still not able to achieve competitive results. We propose the "embedding-coarsening-matching" framework CoSimGNN, which first embeds and coarsens large graphs with adaptive pooling operation and then deploys fine-grained interactions on the coarsened graphs for final similarity scores.
  arXiv  Detail & Related papers  (2020-05-14T16:33:13Z)

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.