Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification

• URL: http://arxiv.org/abs/2603.29148v1
• Date: Tue, 31 Mar 2026 01:53:56 GMT
• Title: Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification
• Abstract summary: Graph Convolutional Network (GCN) is a model that can effectively handle graph data tasks and has been successfully applied.<n>For large-scale graph datasets, GCN still faces the challenge of high computational overhead.<n>We propose a new framework called Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification.
• Score: 35.030106057913834
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Convolutional Network (GCN) is a model that can effectively handle graph data tasks and has been successfully applied. However, for large-scale graph datasets, GCN still faces the challenge of high computational overhead, especially when the number of convolutional layers in the graph is large. Currently, there are many advanced methods that use various sampling techniques or graph coarsening techniques to alleviate the inconvenience caused during training. However, among these methods, some ignore the multi-granularity information in the graph structure, and the time complexity of some coarsening methods is still relatively high. In response to these issues, based on our previous work, in this paper, we propose a new framework called Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification. Specifically, this method first uses a multi-granularity granular-ball graph coarsening algorithm to coarsen the original graph to obtain many subgraphs. The time complexity of this stage is linear and much lower than that of the exiting graph coarsening methods. Then, subgraphs composed of these granular-balls are randomly sampled to form minibatches for training GCN. Our algorithm can adaptively and significantly reduce the scale of the original graph, thereby enhancing the training efficiency and scalability of GCN. Ultimately, the experimental results of node classification on multiple datasets demonstrate that the method proposed in this paper exhibits superior performance. The code is available at https://anonymous.4open.science/r/1-141D/.

Related papers

• Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training [30.354103857690777]
  We employ granular-ball computing to effectively compress graph data.<n>We construct a coarsened graph network by iteratively splitting the graph into granular-balls based on a purity threshold.<n>Our algorithm can adaptively perform splitting without requiring a predefined coarsening rate.
  arXiv  Detail & Related papers  (2024-12-18T13:36:03Z)
• FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarsening [1.1345413192078595]
  This paper presents a novel approach to improve the scalability of Graph Neural Networks (GNNs) by reducing computational burden during the inference phase using graph coarsening.<n>Our study extends the application of graph coarsening for graph-level tasks, including graph classification and graph regression.<n>Results show that the proposed method achieves orders of magnitude improvements in single-node inference time compared to traditional approaches.
  arXiv  Detail & Related papers  (2024-10-19T06:27:24Z)
• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNs iteratively update each node's representation in an input graph by aggregating messages from the node's neighbors.<n>MPNNs might quickly become prohibitive for large graphs provided they are not very sparse.<n>We propose approximating the input graph as an intersecting community graph (ICG) -- a combination of intersecting cliques.
  arXiv  Detail & Related papers  (2024-05-31T09:26:26Z)
• HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs [13.01983932286923]
  We propose a Multi-Level Embedding framework of nodes on a heterogeneous graph (HeteroMILE) HeteroMILE repeatedly coarsens the large sized graph into a smaller size while preserving the backbone structure of the graph before embedding it. It then refines the coarsened embedding to the original graph using a heterogeneous graph convolution neural network.
  arXiv  Detail & Related papers  (2024-03-31T22:22:10Z)
• 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)
• GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
  Graph neural networks learn to represent nodes by aggregating information from their neighbors.<n>Several existing methods address this by sampling a small subset of nodes, scaling GNNs to much larger graphs.<n>We introduce GRAPES, an adaptive sampling method that learns to identify the set of nodes crucial for training a GNN.
  arXiv  Detail & Related papers  (2023-10-05T09:08:47Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• DOTIN: Dropping Task-Irrelevant Nodes for GNNs [119.17997089267124]
  Recent graph learning approaches have introduced the pooling strategy to reduce the size of graphs for learning. We design a new approach called DOTIN (underlineDrunderlineopping underlineTask-underlineIrrelevant underlineNodes) to reduce the size of graphs. Our method speeds up GAT by about 50% on graph-level tasks including graph classification and graph edit distance.
  arXiv  Detail & Related papers  (2022-04-28T12:00:39Z)
• Scaling R-GCN Training with Graph Summarization [71.06855946732296]
  Training of Relation Graph Convolutional Networks (R-GCN) does not scale well with the size of the graph. In this work, we experiment with the use of graph summarization techniques to compress the graph. We obtain reasonable results on the AIFB, MUTAG and AM datasets.
  arXiv  Detail & Related papers  (2022-03-05T00:28:43Z)
• 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)
• Graph Coarsening with Neural Networks [8.407217618651536]
  We propose a framework for measuring the quality of coarsening algorithm and show that depending on the goal, we need to carefully choose the Laplace operator on the coarse graph. Motivated by the observation that the current choice of edge weight for the coarse graph may be sub-optimal, we parametrize the weight assignment map with graph neural networks and train it to improve the coarsening quality in an unsupervised way.
  arXiv  Detail & Related papers  (2021-02-02T06:50:07Z)

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.