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

Guan Wang; Shuyin Xia; Lei Qian; Tao Wu; Guoyin Wang; Yi Wang; Wei Wang

cs.LGMar 31, 2026

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

Authors: Guan Wang, Shuyin Xia, Lei Qian, Tao Wu, Guoyin Wang, Yi Wang, Wei Wang

Organizations: School of Computer Science and Technology, Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, Sichuan-Chongqing Co-construction Key Laboratory of Digital Economy Intelligence and Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China. · School of Computer Science and Technology, School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China. · Chongqing Key Laboratory of Brain-Inspired Cognitive Computing and Educational Rehabilitation for Children with Special Needs, Chongqing Normal University, Chongqing, 401331, China. · Chongqing Ant Consumer Finance Co,. Ltd, Ant Group.

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/.

Figures & tables

Fig. 1: The neighborhood expansion difference between traditional GCN and our proposed method. The red node is the starting node for neighborhood nodes expansion. The traditional GCN has an exponential neighborhood expansion problem, while our method can limit the scope of neighborhood expansion by capturing multi-granularity structural information in the graph from coarse-grained to fine-grained.

Notation	Meaning	Notation	Meaning
$\mathcal{D}$	A dataset composed of discrete data points	$\mathcal{\overline{G}}$	The coarsened graph of $\mathcal{G}$
$\mathcal{GB}$	Granular-ball	$\mathcal{\overline{V}}$	The node set of $\mathcal{\overline{G}}$
$K$	The number of $\mathcal{GB}$ generated based on $\mathcal{D}$	$\mathcal{\overline{E}}$	The edge set of $\mathcal{\overline{G}}$
$g$	The discrete data points contained in $\mathcal{GB}$	$R$	Rayleigh quotient
$m$	The number of discrete data points contained in $\mathcal{GB}$	$\overline{N}$	The number of nodes in $\mathcal{\overline{G}}$
$c$	The center of $\mathcal{GB}$	$\overline{E}$	The number of edges in $\mathcal{\overline{G}}$

TABLE I: Table of Notations.

Fig. 2: The framework of our proposed GB-CGNN. (1) In the Adaptive Granular-ball Coarsening Graph Formation module , we split the coarsest granular-ball from coarse-grained to fine-grained based on the adaptive splitting condition to obtain the granular-ball coarsening graph, where each granular-ball corresponds to each subgraph of the original graph. (2) In the Training GCN with Granular-ball Coarsening Graph module , we randomly sampled some granular-balls to form subgraphs and trained them with GCN, ultimately obtaining the results of node classification.

Datasets	Nodes	Edges	Features	Classes
Cora	2,708	5,429	1433	7 (s)
Citeseer	3,327	4,732	3703	6 (s)
PubMed	19,717	44,338	500	3 (s)
Photo	7,650	119,081	745	8 (s)
Computers	13,752	245,861	767	10 (s)
Co-Cs	18,333	182,121	6805	15 (s)

TABLE II: Summary of information from the benchmark datasets (“m” stands for multi-label, and “s” for single-label).

Methods	Cora	Citeseer	PubMed	Photo	Computers	Co-Cs	Co-phy	PPI	Flickr	Reddit	Yelp	Amazon
SGBGC	1.07	0.91	42.10	23.32	44.44	44.70	92.75	59.03	625.63	30329.22	74421.28	-
GBGC	3.70	4.28	51.53	66.83	225.51	58.21	205.74	561.76	1453.01	-	-	-
SCAL	2.58	3.41	18.45	19.00	35.01	32.29	275.54	124.06	130.20	2769.17	-	-
FGC	7.19	14.37	314.87	222.08	1711.53	879.99	4487.78	-	-	2062.22	-	-
JCGC	8.59	9.34	169.26	25.71	361.94	301.98	1357.26	-	2895.46	-	-	-
GSGC	10.40	10.10	1797.42	34.95	1634.49	1203.65	6356.16	-	13075.61	-	-	-

TABLE III: Comparison of the running time for coarsening in graph coarsening methods (Unit: Second), where the best results are bolded. Results not reported are due to out-of-memory or unavailable. GB: GB-CGNN.

Methods	Cora	Citeseer	PubMed	Photo	Computers	Co-Cs	Co-phy	Flickr	Reddit
GCN	0.8577	0.7368	0.8619	0.9242	0.8651	0.6030	0.9565	0.4197	0.9330
GAT	0.8637	0.7300	0.8780	0.8200	0.8093	0.9231	0.9231	-	-
GraphSAGE	0.8017	0.6385	0.8777	0.9266	0.8230	0.9252	0.9564	0.3992	0.9479
FastGCN	0.8408	0.7640	0.8692	0.8865	0.8970	0.9010	0.8960	0.4207	0.9240
AS-GCN	0.8037	0.6771	0.8486	-	-	-	-	0.4197	0.9580
Cluster	0.8513	0.6879	0.8809	0.9467	0.8958	0.9287	0.9581	0.4553	0.9625

TABLE IV: The result of

ACC

for node classification on single-label datasets. The results not reported are due to out-of-memory or unavailable. Cluster: Cluster-GCN.

Methods	PPI	Yelp	Amazon
GCN	0.4608	0.1741	0.2810
GAT	0.9730	0.6122	0.4750
GraphSAGE	0.5761	0.6163	0.4842
FastGCN	0.4608	0.2651	0.5490
AS-GCN	0.6623	-	-
Cluster-GCN	0.9903	0.6030	0.7121

TABLE V: The result of

Micro\_F1

score for node classification on multi-label datasets. The results not reported are due to out-of-memory or unavailable.

Panel of Figure 8 — Fig. 3: Hyperparameter sensitivity analysis on $L,H,D$ .

Fig. 4: Hyperparameter sensitivity analysis on different initial centers.

Panel of Figure 10 — Fig. 5: The node embeddings are visualized on four datasets, with different colors representing distinct node classes.

Evaluation	Cora	PubMed	Co-phy	Reddit	Yelp	Amazon
Coarsening Time (unit: second)
I	0.59	16.77	41.24	7999.37	-	-
II	0.06	0.41	1.53	116.63	248.20	5304.75
GB	0.07	0.70	1.80	121.56	307.18	4791.81
Node Classification Performance
I	0.8148	0.8676	0.9533	0.9464	-	-

TABLE VI: Comparison of coarsening time and performance for different quality evaluations. The results not reported are due to out-of-memory and the best results are bolded. “I” means using

P

as the quality evaluation, and “II” means using

P

AD

as the quality evaluation. GB: GB-CGNN.

Explore similar work

CoRe-GNN: Multilevel Message passing on Coarsened graphs
Aug 3, 2026Antonin Joly, Nicolas Keriven, Aline RoumyGraph Neural Networks Graph Coarsening
CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE
Global to Local: Topology-Preserving Adaptive Graph Pooling via Granular-Ball
Sep 4, 2026Sen Zhao, Gaojie Xu, Shuyin Xia +4Graph Pooling Hierarchical Representation Learning
Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle
May 13, 2026Xu Bai, Bin Lu, Kun Zhang +4Graph Coarsening
School of Information Science and Electronic Engineering, Shanghai Jiao Tong University, Shanghai, China · School of Environment Science and Engineering, Shanghai Jiao Tong University, Shanghai, China · School of Artificial Intelligence, Nanchang University, Nanchang, China +2

Aug 3, 2026J/K move · Enter open · S save

CoRe-GNN: Multilevel Message passing on Coarsened graphs

Antonin Joly, Nicolas Keriven, Aline Roumy

CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE

Graph Neural Networks Graph Coarsening Message Passing Neural Networks Node Classification

Open paper AskPDF arXiv

Training Graph Neural Networks on large graphs is challenged by the memory cost of storing all node representations across layers. We show that several existing scalable approaches can be written as structured modifications of the GNN propagation matrix, providing a unified perspective that exposes their respective limitations. In particular, graph coarsening replaces it by a low-rank approximation that enables spectral guarantees but assigns uniform representations to clustered nodes, while Cluster-GCN restricts the propagation matrix to intra-cluster connections that allow efficient batching but sever long-range information. These are complementary failures of the same decomposition of the graph into groups of nodes. To obtain the best of both worlds, we propose CoRe-GNN, which performs both propagations in parallel at each layer: a coarsened inter-cluster term capturing long-range structure, and a local intra-cluster term preserving per-node discriminability. We prove that CoRe-GNN inherits analogous approximation guarantees to those of graph coarsening, and introduce a natural cluster-based batching scheme that scales to graphs with millions of nodes. On node classification benchmarks spanning homophilic, heterophilic, large-scale, and long-range graphs, CoRe-GNN outperforms both graph coarsening and Cluster-GCN baselines. Notably, CoRe-GNN reaches competitive accuracy on long-range tasks, while remaining memory-efficient through batching.

Abstract

Explore similar work

CoRe-GNN: Multilevel Message passing on Coarsened graphs

Global to Local: Topology-Preserving Adaptive Graph Pooling via Granular-Ball

Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle