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.
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
D
A dataset composed of discrete data points
G
The coarsened graph of G
GB
Granular-ball
V
The node set of G
K
The number of GB generated based on D
E
The edge set of G
g
The discrete data points contained in GB
R
Rayleigh quotient
m
The number of discrete data points contained in GB
N
The number of nodes in G
c
The center of GB
E
The number of edges in 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.
Fig. 3: Hyperparameter sensitivity analysis on L,H,D .
Fig. 4: Hyperparameter sensitivity analysis on different initial centers.
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.
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.
Antonin Joly, Nicolas Keriven, Aline Roumy
CNRS, IRISA, Rennes, FRANCE · INRIA, Rennes, FRANCE
Graph pooling aims to compress the graph, including both node embeddings and their underlying topological patterns, into a more compact representation. Previous works focus primarily on the overly fine-grained representation of nodes, progressively coarsening the graph by removing nodes or merging them into clusters, thus neglecting the global-to-local patterns and adaptive granularity of the graph's topological structure. In the real scenario, graphs as a whole can be considered the coarsest level of granularity, encapsulating the global topological structure, with progressively finer-grained local topological structures represented from top to bottom. This process continues until the adaptive granularity for each subdomain is reached. To this end, we propose a novel Topology-Preserving Adaptive Graph Pooling (TPAGP) method that dynamically partitions graphs into granular balls by integrating node features and topological information, enabling the generation of multi-granularity representations that effectively capture both local and global structural patterns. Additionally, we design a multi-granularity graph network model that facilitates feature interaction and optimization across different granularities, significantly enhancing performance in graph classification tasks. Experimental results demonstrate that TPAGP outperforms existing pooling methods across various benchmark datasets, effectively mitigating information loss caused by fixed-granularity strategies.
Graph coarsening is a graph dimensionality reduction technique that aims to construct a smaller and more tractable graph while preserving the essential structural and semantic properties of the original graph. However, most existing methods rely on pair-wise similarity matching, where each node independently searches for its best partner based on global information. This selfishness matching paradigm incurs substantial computational and memory overhead. To address this problem, we shift to a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening, and propose an efficient method named NOPE, which achieves linear memory consumption and near-linear computational complexity in the number of nodes. Furthermore, we derive a faster variant NOPE*, which reduces O(δ\dot d) interference evaluation to O(d) based on the local isotropy assumption, and consequently alleviates the computational bottleneck for high-degree nodes. Experimental results show that NOPE* achieves 1.8-10\times speedup over NOPE and surpass almost all baselines with 1-3 orders of magnitude acceleration. Meanwhile, learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning owing to compact graph information. The code can be available at https://github.com/dazonglian/NOPE-main.
Xu Bai, Bin Lu, Kun Zhang +4
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