GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing

1 Introduction

Graphs are crucial in various fields [Hamilton et al., 2017; Song et al., 2023; Xv et al., 2023; Fout et al., 2017; Hamaguchi et al., 2017]. Their growing size offers more information but requires substantial computational resources [Kumar et al., 2023; Xu et al., 2018; Duan et al., 2022]. Efficient processing methods, such as graph coarsening, are essential for processing large-scale graphs [Hashemi et al., 2024].

Graph coarsening aims to simplify graphs while preserving their key properties and improving the efficiency of downstream tasks [Hashemi et al., 2024]. Most existing works have focused on spectrum-preserving [Loukas, 2019; Jin et al., 2020; Chen et al., 2023]. This involves ensuring that the eigenvalues of the original graph closely match those of the coarsened graph. Although spectrum-preserving methods have many advantages, they involve the eigenvalue problem of the Laplacian matrix, which overly relies on the global properties of the graph and may hinder their application in processing large graph data due to high computational costs. Graph coarsening also finds applications in deep learning [Huang et al., 2021; Pang et al., 2021], with its challenges such as excessive information loss when coarsening is not executed properly, potentially resulting in a decline in model performance. Some works suggest that training Graph Neural Networks (GNNs) is often computationally expensive. A potential solution to alleviate the mentioned problems is dataset condensation or distillation [Jin et al., 2021; Jin et al., 2022]. The goal is to construct a small synthetic set to train the GNN, thereby reducing costs to some extent. However, these studies overlook the granularity characteristics of the graph structure.

The process of graph coarsening does not eliminate any of the original nodes, but instead merges the nodes into supernodes according to some coarsening rules, and aggregates the original edges into superedges. Taking the right half of Figure 1 as an example, the graph typically consists of subregions with different levels of granularity, where nodes within the same subregion show a high degree of connectivity and similarity, and these nodes should be aggregated into one supernode. Initially, the original graph can be viewed as a coarsest structure, and then further refine through finer granularity until the final coarsening results are obtained. Ignoring the multi-granularity characteristics of the graph structure, as shown in the left half of Figure 1, can affect the quality of the coarsened graph and the efficiency of subsequent tasks. By taking advantage of the multi-granularity characteristics of graph structure, the various structural information of the graph can be more fully understood, which can lead to more precise generation of supernodes while improving efficiency.

Actually, it is not easy to coarsen the original graph and model granularity characteristics of the graph structure, which mainly faces two challenges: (1) How to efficiently and effectively aggregate the nodes in the original graph into the supernodes in the coarsened graph? Nodes with a high degree of connectivity and similarity should be more inclined to be aggregated into a supernode, which is a key consideration in graph coarsening. Inspired by the advantages of granular-ball computing in distinguishing multi-granularity of discrete data [Xia et al., 2023], and since granular-ball computing has not yet been applied in the field of graphs, we further explore its potential in graph coarsening and propose an adaptive granular-ball graph refinement mechanism. (2) How to generate coarsening results according to the multigranularity characteristics of the graph structure? The graph structure has multiple levels of granularity features, which exhibit unique topological structures at different levels. Using this feature to guide the process of graph coarsening not only improves the efficiency of graph coarsening, but also enhances the model's ability to understand complex graph structure. Therefore, it is very important to develop a coarsening method that can capture the relationship between the nodes in the original graph and the supernodes in the coarsening graph from a multi-granularity perspective.

To this end, we propose a new multi-granularity, efficient, and adaptive coarsening method via granular-ball. Specifically, for challenge (1), the original graph is initialized as coarse-grained granular-balls, which are then iteratively split by a fine-grained binary splitting mechanism. In the initial stage, the method only uses global calculation, and the subsequent steps rely on local calculation for iterative splitting, and the computational complexity is low. For challenge (2), according to the multi-granularity characteristics of the graph structure, our proposed method can adaptively use multiple granular-balls of different sizes to generate coarsening results. Extensive experiments conducted on several graph datasets show that our proposed method can outperform the state-of-the-art methods. Our contributions are summarized as follows:

1 Code is available from https://anonymous.4open.science/r/GBGC. Supplementary materials are available from https://github.com/ Wangwangguanguan/Supplementary-materials.git.

• We emphasize the importance of multi-granularity characteristics of the graph structure in graph coarsening.
• We propose a new graph coarsening method called granular-ball graph coarsening (GBGC), which adaptively uses different sizes of granular-balls to represent supernodes in the coarsened graph. GBGC involves global calculation (calculating the distance between all pairs of nodes in a graph) only in the initialization, thus reducing the time complexity.
• Extensive testing and comparison of datasets confirms the validity and accuracy of GBGC, and we provide a new perspective on graph coarsening methods.

2 RelatedWork

The spectrum of the Laplacian matrix reflects the graph's structure, and spectral distance serves as a measure of structural similarity between graphs [Wilson and Zhu, 2008]. Loukas et al. introduced "restricted spectral similarity" (RSS), where the eigenvalues and eigenvectors of the coarsened graph approximate those of the original graph within the main feature subspace [Loukas and Vandergheynst, 2018; Loukas, 2019]. Jin et al. used spectral distance to evaluate spectral preservation and developed coarsening algorithms to minimize this distance [Jin et al., 2020]. Imre et al. proposed a near-linear time-preserving sparse algorithm for large graphs [Imre et al., 2020]. Chen et al. applied GromovWasserstein (GW) distance to limit the spectral difference between graphs and their coarsenings, proving an upper bound related to spectral difference [Chen et al., 2023].

Graph coarsening methods have gained popularity in deep learning in recent years. Xie et al. proposed MLC-GCN, a multilevel coarsening classification method for GCNs that retains both local and global graph information and learns representations at multiple levels [Xie et al., 2020b]. Fahrbach et al. introduced an efficient coarsening method based on the Schur complement, which reduces computational time by embedding related vertices on the coarsened graph [Fahrbach et al., 2020]. Huang et al. used graph coarsening for scalable GNN training, reducing the number of graph nodes by up to 10 times without significant accuracy loss [Huang et al., 2021]. Pang et al. proposed InfomaxPooling (CGIPool), which maximizes mutual information between each pooling layer's input and the coarsened graph to preserve graph-level dependencies [Pang et al., 2021].

Training GNNs is computationally expensive, and dataset condensation [Fang et al., 2024] or distillation [Wang et al., 2018] can help reduce costs by creating smaller synthetic graph datasets for training. Zhao et al. proposed a condensation method called DC, which matches network parameter gradients between a small synthetic and a large real dataset [Zhao et al., 2020]. Jin et al. introduced GCOND, a graph compression method that reduces nodes by compressing both node features and structure in a supervised way [Jin et al., 2021]. They also proposed DosCond, a framework that uses gradient matching to effectively compress real graphs into smaller, discrete information graphs [Jin et al., 2022].

Above methods have significantly enhanced the efficiency of various downstream tasks, making them a focal point of ongoing research and development. Despite these advancements, many of the existing approaches tend to overlook the inherent granularity of the graph structure. This oversight can limit their effectiveness in capturing the complex relationships between nodes. In contrast, our work addresses this gap by explicitly considering the granularity characteristics of the graph. We propose a novel approach that captures and utilizes the relationships between nodes from a multi-granularity perspective, enabling more effective graph coarsening.

3 Methodology

3.1 Notations and problem statement

We denote an original graph as G = (V, E), whose node set is V with size |V| = N, and whose edge set is E with size |E| = E. The adjacency matrix of G is denoted as A ∈ {0, 1}N×N , and Aij = 1 if there is an edge between nodes vi and vj . The Laplacian matrix is denoted as L = D - A, where D is the degree matrix with Dii = ∑j Aij. The normalized Laplacian matrix is ˆL = D- 1 2LD- 12 . Given an original graph G, graph coarsening methods aim to find a smaller coarsened graph denoted as G = (V, E) to approximate G. The number of nodes in G is denoted as N, the number of edges is denoted as E, and N < N, E < E. The adjacency matrix of G is denoted as A ∈ {0, 1}N×N , and Aij = 1 if there is an edge between supernodes vi and vj. In the matrix form, we use C ∈ RN×N to denote a projection matrix that maps nodes in V to supernodes in V, and Cij = 1 if node i in V is mapped to supernode j in V. The Laplacian matrix of the coarsened graph can be denoted as L = CT LC. This computation ensures that the spectral properties of the original graph are preserved in the coarsened graph.

Our proposed GBGC seeks to obtain a coarsened graph G to approximate G. The original graph G is refined into multiple non-overlapping subdomains as follows:

where ˜ Vi and ˜ Ei represent the set of nodes and edges of the graph ˜ Gi contained inside the granular-ball GBi, with ˜ Vi ⊂ V being a subset of nodes from G. N is the number of supernodes in G, and each GB corresponds to a supernode in G. In the process of graph coarsening implementation, the information loss between the original graph and the coarsened graph should be minimized, the number of granular-balls should be as few as possible, and the adaptive quality requirements should be met.

3.2 Model introduction

Figure 2 illustrates the overall framework of GBGC, which consists of two stages: (I) the process of granular-balls formation; (II) the graph coarsening results.

(I) The process of granular-balls formation

This stage consists of four steps. Step 1 is based on the law of "global precedence" [Chen, 1982], the original graph as the coarsest granular-ball. Step 2 generates √N initial granularballs. Mathematically,

The value of √N is an empirical choice, referenced from previous work [Xie et al., 2020a; Yu and Cheng, 2001], which has been shown to balance the trade-off between size and quantity of granular-balls.

The procedure for generating GBinit is as follows. Firstly, we select the node with the highest degree vcenter = arg max v∈V deg(v) as the initial center. Subsequently, breadthfirst search (BFS) starts with the vcenter, traversing layer by layer until the number of nodes at layer i exceeds √N :

where |Ni| denotes the number of nodes at layer i. Then delete these nodes from V:

Continue to find the next center with the highest degree v′center = argmax v∈V ′ deg(v) in V ′ , and so on through the entire graph to determine GBinit.

All nodes participate in the calculation, so global calculation is involved in this step. This approach not only accelerates subsequent granular-ball splitting processes but also provides an effective starting point for granular-ball coarsening in graphs with a small number of nodes. Step 3 is to calculate the quality of each granular-ball, which is defined as follows.

Definition 1 For a granular-ball GB, its quality is formulated as follows:

where ˜ E and ˜ N represent the number of edges and nodes within the graph contained inside GB, respectively. ˜Amn indicates the presence ( ˜Amn = 1) or absence ( ˜Amn = 0) of an edge between nodes ˜m and ˜n ( ˜m, ˜n =˜i, ˜j, ˜k) inside GB.

Quality is composed of two components: the average degree and the global clustering coefficient (also known as the transitivity). The first component quantifies the average number of edges connected to each node in the graph, serving as an intuitive measure of the connectivity within the graph. In the second component, ∑˜i̸=˜j̸=˜k ˜A˜i˜j ˜A˜j˜k ˜A˜k˜i , represents the number of actual triangles present in the graph. In contrast, ∑˜i̸=˜j̸=˜k ˜A˜i˜j ˜A˜i˜k denotes the total number of possible triples in the graph, where a triple is defined as a central node connected to two other nodes, regardless of whether the two peripheral nodes are directly connected. The second component measures the local clustering of nodes within the graph, and its computation relies on the number of triangles and triples.

The higher the quality of the granular-ball, the more tightly connected the nodes inside the granular-ball. This method of quantifying the quality of the granular-ball ensures that the structural properties of the graph are considered and balanced in subsequent splitting of the granular-ball.

Step 4 is to perform a fine-grained binary splitting for each granular-ball GBj in GBinit. The fine-grained splitting identifies the two nodes with the highest degree of parent granular-ball (GBj) as the splitting centers of the two child granular-balls (GBjA and GBjB ), which are denoted as

where ˜ Vj represents the set of nodes within the granular-ball GBj. Each center node traverses the remaining nodes layer by layer through BFS, and other non-center nodes are assigned to the node according to who was first traversed by a center node's BFS. Only the nodes within granular-balls are involved in the calculation, so Steps 3 and 4 involve local calculation. The adaptive splitting condition of parent granularball splitting is given by the following formula:

where quality(GBjA + GBjB ) denotes the sum of the qualities of the two child granular-balls, and quality(GBj) denotes the quality of the parent granular-ball. This formula is employed to decide whether to proceed with splitting granular-balls. If there is a notable difference in quality between the parent granular-ball and its child granular-balls, suggesting that further splitting improves the overall system performance, the splitting operation will continue. This strategy ensures both the precision and efficiency of the splitting process, preventing unnecessary computational complexity from arising.

(II) The graph coarsening results

This stage consists of Step 5, which is to generate the coarsening results. In the process of graph coarsening, GBGC splits the nodes of the original graph from coarse-grained to fine-grained, and generates the supernodes of the coarsened graph. Therefore, each granular-ball GB corresponds to a supernode in the coarsened graph G. Mathematically,

which covers all nodes in G. If there is already an edge between the nodes contained within two different granularballs, then an edge is created between the two granular-balls. The process can be represented as follows:

This methodology enhances the representation of graph by focusing on broader connectivity patterns, while maintaining the critical properties of the graph.

3.3 Theoretical analysis of GBGC

Due to the difference in the number of nodes between the original graph G and the coarsened graph G, we introduce appropriate intrinsic functionals such as the Rayleigh quotient (which is a quantity related to the structure of the graph and does not vary with the arrangement of nodes). The projection matrix C, where Cij = 1 if vi belongs to GBj, ensures that the spectral information of the two graphs becomes comparable [Cai et al., 2021]. Therefore, we first give the definitions of the Rayleigh quotient of the original graph and the coarsened graph respectively. Then the coarsening effect of GBGC is proved by the Rayleigh quotient.

Definition 2 For an original graph G, its Rayleigh quotient is defined as:

where L is the Laplace matrix of G, x is the eigenvector of L. According to the definition of the projection matrix C in Section 3.1, the Rayleigh quotient of the coarsened graph obtained by GBGC is given, which is defined as follows:

Definition 3 For the coarsened graph G, its Rayleigh quotient is defined as:

where L is the Laplace matrix of G.

Theorem 1 Assuming C is a generalized orthogonal matrix (i.e. CT C ≈ I, where I is the identity matrix), we have:

Proof. Considering the assumption thatCis a generalized orthogonal matrix. For the denominator of Rc(L, x), using the orthogonality of C, we get (CT x)T (CT x) ≈ xT CCT x = xT Ix = xT x. And then, for the numerator of Rc(L, x), we have (CT x)T L(CT x) ≈ xT CLCT x. According to L = CT LC, we obtain CLCT ≈ L. Thus, xT CLCT x ≈ xT Lx. Finally, using these approximations, the Rayleigh quotient of the coarsened graph obtained by GBGC can be approximated as Rc(L, x) ≈ Ro(L, x).

4 Experiments

In this section, we design experiments to evaluate our GBGC and answer the following research questions (RQs): RQ1: Does our method achieve better performance compared to the state-of-the-art methods? RQ2: How does GBGC perform with respect to time consume? RQ3: What impact do the key components have on GBGC's performance? RQ4: How do hyperparameters effect GBGC's performance? RQ5: How does GBGC perform in visualization?

4.1 Experimental setup

Datasets: We use several standard graph classification datasets, which are shown in Table 1. See Appendix for implementation details.

Baselines: We compare with six baseline methods also for graph-level tasks: Variation Neighborhood Graph Coarsening (VNGC) [Loukas, 2019]; Variation Edge Graph Coarsening (VEGC) [Loukas, 2019]; Multilevel Graph Coarsening (MGC) [Jin et al., 2020]; Spectral Graph Coarsening (SGC) [Jin et al., 2020]; Dataset One-Step Condensation (DosCond) [Jin et al., 2022]; Kernel Graph Coarsening (KGC) [Chen et al., 2023].

Evaluation index of coarsening effect: In this paper, we mainly use accuracy (ACC) and spectral distance (SD) to measure the effect of coarsening of GBGC. According to the reference [Wilson and Zhu, 2008], since the spectrum of the Laplacian distills information about the graph structure, one may interpret the spectral distance as a proxy for the structural similarity of the two graphs. The spectral distance between the original graph and the coarsened graph is defined by calculating the Euclidean distance between the eigenvalue vectors of the two graphs, i.e., SD(G, G) = √∑i (λ(G) i -λ(G) i )2 , where λ(G) i and λ(G) i are the i-th eigenvalues of the Laplace matrix of the original and coarsened graphs, respectively. When the spectra have different sizes, then the smaller one can be padded with zeros (while maintaining the magnitude ordering). This is equivalent to adding disjoint nodes to the smaller graph to make both graphs have

the same number of nodes.

4.2 Performance of coarsening method for graph classification (RQ1)

Graph classification is a key data mining task, however, the complexity and diversity of large-scale graph data bring great challenges to classification. Graph coarsening can reduce graph size, speeding up training and inference for graph classification models. However, improper coarsening may cause information loss, reducing accuracy. Thus, we evaluate various coarsening methods by comparing their performance with the same classifier applied to the original graph.

Our GBGC is free of randomness. To evaluate comparison models thoroughly, we used multiple random seeds and applied cross-validation with repeated runs. The DosCond method, which doesn't use a ratio for computation, averages results from ten repeated experiments to ensure more reliable accuracy metrics. This reduces the impact of chance errors on final results, making them more robust. To ensure a fair comparison, the identical coarsening parameter ra, as determined by the adaptive coarsening process of GBGC, is utilized across the VNGC, VEGC, MGC, SGC, and KGC. The performance results are shown in Table 2. From Table 2, we have the following observations:

• It is evident that GBGC achieves higher graph classification accuracy compared to baseline methods on most datasets. GBGC performs better on most datasets than comparison baseline methods and FULL. For the P388H dataset, the accuracy of GBGC was not significantly different from that of DosCond. However, GBGC consistently excels in graph classification, especially in maintaining stable performance across multiple datasets. This indicates that GBGC better preserves the original graph's properties while reducing its size, effectively capturing structural information and improving classification accuracy.
• GBGC demonstrates high accuracy in graph classification after coarsening the original graph. GBGC outperforms the full dataset in classification accuracy on most datasets. This is due to the coarsened graph reducing noise and the granular-ball effectively capturing data distribution. Similar to other work related to granularball computing, GBGC is robust and generalizable. It uses multi-granularity representation and granular-ball splitting to generate supernodes, preserving key graph structure information for better classification. However, GBGC performs worse than FULL on IMDB-BINARY and PROTEINS datasets, likely because these datasets have better distribution and less noise, reducing the benefits of coarsening.

We refer to references [Loukas, 2019] and [Wilson and Zhu, 2008] and use SD to evaluate the performance of the coarsening methods. Figure 3 shows an intuitive comparison of SD. It can be seen that the spectral distance of the GBGC is better than that of comparison methods.

4.3 How does GBGC performwith respect to time consume?(RQ2)

This section evaluates the efficiency of GBGC and other coarsening methods. Since DosCond's runtime depends on GNN training, we exclude it from the comparison for fairness and focus on the runtime of GBGC and the other five methods. The runtime comparison is shown in Table 3. From the results in Table 3, we observe that:

• The running time of GBGC is tens to hundreds of times faster than comparison methods, which is significantly lower than other methods. Especially on the P388H dataset, the advantages of GBGC are even more significant.
• The high efficiency of GBGC can be attributed to its unique granular-ball generation and splitting strategies. These strategies use global computation for coarsegrained granular-ball initialization and local computation for fine-grained binary splitting, ensuring low time complexity and high efficiency. Importantly, GBGC maintains accuracy while achieving efficiency. By using granular-balls of varying sizes, GBGC effectively captures the original data, often outperforming the FULL in classification accuracy.

4.4 Ablation studies (RQ3)

In this section, we perform ablation experiments on several datasets to examine GBGC, including GBGC-w/o finegrained binary splitting and GBGC-w/o coarse-grained initialization. The results are shown in Table 4. We have the following observations:

• Removing the fine-grained binary splitting mechanism in GBGC significantly reduces the model's performance, emphasizing its importance. This mechanism is crucial for capturing the graph's inherent granularity and preserving node relationships. Without this mechanism, the model struggles to effectively represent the multigranularity features of the graph, underscoring its necessity for achieving optimal performance in tasks that rely on precise graph coarsening and representation.
• Removing the coarse-grained initialization from GBGC leads to a significant performance drop, highlighting its crucial role in the model. It provides an initial representation that captures the graph's broader structure, enabling the model to handle higher-level node relationships. Its absence highlights the substantial contribution it makes to the model's ability to process and represent the graph effectively, making it an indispensable component to achieve strong performance.

4.5 Hyper-parameter sensitivity analysis (RQ4)

In this section, we design a non-adaptive GBGC (see Algorithm 4 in Appendix for algorithm design) to evaluate the performance of different r. Following the experimental settings of [Chen et al., 2023], we studied the effect of different r ∈ (0, 1) with a step size of 0.1 on GBGC performance, as shown in Figure 4. The model performs best when GBGC adaptively generates the coarsening rate, ra. This is because GBGC uses a mix of large granular-balls for simple data distributions and many smaller ones for complex distributions, effectively representing the data and improving accuracy.

4.6 Case study (RQ5)

GBGC retains essential graph structure information, enabling classifiers to use it more efficiently for accurate graph classification. This section focuses on the MUTAG, DHFR, and OVCAR-8H datasets. For MUTAG, GBGC identifies molecular structures related to toxicity; for DHFR, it captures correlations between molecular fragments and drug activity; and for OVCAR-8H, it highlights key molecular features influencing drug response, aiding drug screening and personalized treatment prediction. Figure 5 illustrates GBGC's analysis, where colored circles represent granular-balls (supernodes), showing its ability to capture node correlations.

5 Conclusion

In this work, we propose a new multi-granularity, efficient, and adaptive coarsening method via granular-ball(GBGC). The experimental results show that GBGC has higher accuracy compared with several state-of-the-art methods. At the same time, the speed of GBGC is increased by tens to hundreds of times, showing a low time complexity O(N 32 + E√N). Additionally, an intriguing observation is that the accuracy of GBGC is almost consistently higher than that achieved on the original datasets, attributable to its robustness and generalizability. While our current approach focuses on graph classification tasks, other downstream tasks can be explored in the future to further broaden the applicability of our coarsening approach.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant Nos. 62221005, 62450043, 62222601, and 62176033.