UGC: Universal Graph Coarsening

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:45:26

Abstract: In the era of big data, graphs have emerged as a natural representation of intricate relationships. However, graph sizes often become unwieldy, leading to storage, computation, and analysis challenges. A crucial demand arises for methods that can effectively downsize large graphs while retaining vital insights. Graph coarsening seeks to simplify large graphs while maintaining the basic statistics of the graphs, such as spectral properties and $\epsilon$-similarity in the coarsened graph. This ensures that downstream processes are more efficient and effective. Most published methods are suitable for homophilic datasets, limiting their universal use. We propose **U**niversal **G**raph **C**oarsening (UGC), a framework equally suitable for homophilic and heterophilic datasets. UGC integrates node attributes and adjacency information, leveraging the dataset's heterophily factor. Results on benchmark datasets demonstrate that UGC preserves spectral similarity while coarsening. In comparison to existing methods, UGC is 4x to 15x faster, has lower eigen-error, and yields superior performance on downstream processing tasks even at 70% coarsening ratios.

Main paper: 
 introduction: 
 Graphs have emerged as highly expressive tools to represent diverse structures and knowledge in various fields such as social networks, bioinformatics, transportation, and natural language processing. They are essential for tasks like community detection, drug discovery, route optimization, and text analysis. With the growing importance of graph-based solutions, dealing with large graphs has become a challenge. Graph coarsening, a widely used technique to simplify graphs while retaining vital information, making them more manageable for analysis Kumar et al. (2020) . It has been applied successfully in various tasks Hendrickson & Leland (1995) ; Karypis & Kumar (1999) ; Kushnir et al. (2006) ; Dhillon et al. (2007) ; Wang et al. (2014) . Preserving the structural information of the graph is crucial in graph coarsening algorithms to ensure the fidelity of the coarsened graphs. A high-quality coarsened graph retains essential features and relationships, enabling accurate results for downstream tasks. Additionally, computational efficiency is equally vital for scalability, as largescale graphs are common in real-world applications. Efficient coarsening method should ensure that the reduction in graph size does not come at the expense of excessive computation time but existing graph coarsening methods often face trade-offs between scalability and the quality of the coarsened graph. Our method draws inspiration from hashing techniques, which provides us with advantages in terms of computational efficiency. As a result, our approach exhibits a linear time complexity, making it highly efficient even for large graphs. Graph datasets often exhibit a blend of homophilic and heterophilic traits Zhu et al. (2020) ; Pei et al. (2020) . GC has been widely explored on homophilic datasets, but, to the best of our knowledge, has never been applied on heterophilic graphs. We propose Universal Graph Coarsening U GC, an approach that works well on both. Figure 1 illustrates how UGC uses a graph's adjacency matrix as well as the node feature matrix. UGC relies on hashing, lending computational efficiency. UGC exhibits linear time complexity, enabling fast processing of large datasets. UGC enhances the performance of Graph Convolutional Networks (GCN) in classification tasks, indicating its suitability for downstream processing. UGC coarsened graphs retain essential spectral properties, and show low eigen error, hyperbolic error, and ϵ-similarity measure. In a nutshell, UGC is fast, universally applicable, and information preserving. Outline: The paper is organized as follows: Section 2 briefly describes the related background and our problem formulation. We explain our framework in Section 3. We then provide assurances for quality similarities for coarsened graph in Section 4. Section 5 demonstrates the effectiveness of our algorithm with extensive experimentation. And then finally, the conclusion in Section 6.Figure 1 : This figure illustrates our framework UGC, which depicts a) Generation of an augmented matrix by incorporating feature and adjacency matrices, while using heterophily measure α. b) Coarsening the original graph using augmented features via Hashing. c) Validating reduced graph's quality and its utilization in subsequent downstream tasks. 
background and problem formulation: 
 A graph G = (V, E, A, X) whereV = {v 1 , v 2 , • • • , v |N | } is the set of N vertices, E is the set of edges (v i , v j ) ⊆ (V × V ) . A ∈ R N ×Nis the adjacency matrix. A non-zero entry A ij indicates there is an edge between nodes i and j. The i-th row of the feature matrix X ∈ R N ×d , vector X i ∈ R d , is the vector of features associated with the i-th node of G. The degree matrix D is diagonal, with D = diag (D i,i ), where D ii = j A ij . The Graph Laplacian matrix L = D -A Kipf & Welling (2016). L ∈ R N ×N is a Laplacian matrix if it belongs to the set S L = L ∈ R N ×N |L ji = L ij ≤ 0, ∀i ̸ = j; L ii = -j̸ =i L ij .The objective is to reduce an input Graph G into a new graph G c ( Ṽ , Ẽ, Ã, X), with n-nodes and X ∈ R n×d where n << N nodes. The GC problem may be thought of as learning a coarsening matrix C ∈ R N ×n , which is a linear mapping from V → Ṽ . A linear mapping ensures that similar nodes in G are mapped to the same super-node in G c , s.t. X = C T X. Every non-zero entry in C ij in C denotes the merger of the i th node of G to the j th supernode. This C matrix belongs to the following set:S = C ∈ R N ×n , Cij ∈ {0, 1}, ∥C T i ∥ = 1, ⟨Ci, Cj⟩ = 0, ∀i ̸ = j, ⟨C l , C l ⟩ = di, ∥Ci∥0 ≥ 1 (1) C T = 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 (2)where d i is the degree of the i th -node. The condition ⟨C i , C j ⟩ = 0 ennsures that each node of G is mapped to a unique super-node. The constraint ∥C i ∥ 0 ≥ 1 requires that each super-node contains at least one node.Consider the 8-node graph in Fig. 2 . Nodes 1, 2, 3, and 4 are mapped to supernode A, while nodes 6, 7, and 8 are mapped to supernode C. Hence, the loading matrix C is given as Equation 2. (2009b) ; Buhler (2001) ; Satuluri & Parthasarathy (2012) . It maps high dimensional vectors to lower dimensions, while ensuring that similar vectors collide with high probability. LSH uses a family of hash functions to map vectors to buckets, enabling fast retrieval and similarity search. It has found applications in image retrieval Kulis & Grauman (2009a) , data mining Ravichandran et al. (2005) , and similarity search algorithms Chum et al. (2007) . LSH is defined as Definition 2.1 Let d be a distance measure, and let d 1 < d 2 be two distances. A family of functions F is said to be (d 1 , d 2 , p 1 , p 2 )-sensitive if for every f ∈ F the following two conditions hold• If d(x, y) ≤ d 1 then probability [f (x) = f (y)] ≥ p 1 • If d(x, y) ≥ d 2 then probability [f (x) = f (y)] ≤ p 2UGC uses LSH with a set of random projectors to map similar nodes to the same super node. The projection is computed ash i (x) = <x,ai>-bi w, where a i is randomly selected from a distribution (such as Gaussian); x represents the original high dimensional data sample, and w is the width of each quantization bin.The literature is replete with graph reduction methods, that aim to shrink a graph through deleting nodes by using vertex selection, re-combination schemes, or aggregation. Loukas proposed advanced spectral graph coarsening algorithms based on local variation, to preserve the original graph's spectral properties Loukas (2019) . Two variants, viz. edge-based local variation and neighborhood-based local variation, select contraction sets with small local variation in each stage, but have limitations in achieving arbitrary coarsening levels Loukas (2019) . Heavy edge matching (HEM), determines the contraction family by computing a maximum-weight matching based on the weight of each contraction set Dhillon et al. (2007) ; Ron et al. (2010) . The Algebraic Distance method calculates the weight of each candidate set using an algebraic distance measure Ron et al. (2010) ; Chen & Safro (2011) . The affinity method, inspired by algebraic distance, uses a vertex proximity heuristic Livne & Brandt (2011) . The Kron reduction method Dorfler & Bullo (2013) was originally proposed for electrical networks, but is too slow for for large networks. Most of the above mentioned methods ignore node features during graph coarsening, and are usually memory intensive. UGC efficiently utilizes node features to achieve fast coarsening. The proposed UGC framework comprises three main components, i) First, obtaining an augmented feature matrix containing both node feature and the structural information, ii) locality-sensitive hashing to derive the coarsening matrix, iii) finally, obtaining the coarsened graph adjacency matrix and coarsened features. 
proposed framework universal graph coarsening (ugc): 
 3.1 Augmented Feature The concepts of homophily and heterophily in graphs are primarily concerned with whether the edges between two nodes align with their respective features. Therefore, in order to create a universal framework for graph coarsening suitable for all, it is important to consider both the node-level features and the structure-level features, such as the neighborhood structure of any given node, together. In this regard we create an augmented feature matrix F , where each node's feature vector X i is augmented with its one-hot adjacency vector A i , with the heterophily hyperparameter α balancing the emphasis between feature and adjacency information. The augmented feature vector of each node is given by 3 provides a toy example of the augmented feature vector. While larger graphs may result in long vectors, efficient implementations, and sparse tensor methods may alleviate this hurdle. A motivating example demonstrating the need for augmented features while doing graph coarsening is discussed in the Appendix A.8, See figure 11.F i = (1 -α) • X i ⊕ α • A i .. Figure3.2 Proposed framework UGC Let F i ∈ R d represent node v i 's augmented feature vector. Let P ∈ R L×d and b ∈ R L be the hashing matrices used in UGC, with L denoting the number of projectors. The hash value given to the graph node is its most frequent hash index generated across all hash functions. Node v i 's hash value is h i = maxOccured{⌊ 1 r * (P • X i + b)⌋}, where r is the bin-width. This hyperparameter controls the coarsened graph G c 's size. Empirically, we find that increasing r shrinks G c . All nodes assigned the same hash value map to the same supernode in G c .Algorithm 1 UGC: Universal Attributed Graph Coarsening via Hashing r] 7:Require: Input G(V, A, X), L ← # of Projectors, r ← bin-width, α ← heterophilic factor, n ← # of supernodes. 1: F = (α)(X) ⊕ (1 -α)(A)P ℓ i ∼ U [0, 1] ∀i ∈ {1, 2, 3, ....., d}, b ℓ ∼ U [-r,h ℓ i ← ⌊ 1 r × ( j=d j=1 (F j i × P ℓ j ) + b ℓ )⌋ ∀i ∈ {1, 2, 3, ....., N } 8: end for 9: h i ← maxOccurence{h ℓ i ; ℓ ∈ {1, 2, 3, ..., L}}∀i ∈ {1, 2, 3, ....., N } 10: π ← Dictionary mapping every node in G to supernode ∈ {1, 2, ..., n} in G c 11: for every node v in V do 12: C[v, π[v]] ← 1 13: end for 14: A c (i, j) ← (u∈π -1 (ṽi),v∈π -1 (ṽj )) A uv , ∀i, j ∈ {1, 2, ..., n} 15: F c (i) ← 1 |π -1 (ṽi)| u∈π -1 (ṽi) F u , ∀i ∈ {1, 2, ..., n} 16: return G c (V c , A c , F c ) , nWhen G is coarsened to G c , any supernode pair ( ṽi , ṽj ), where ṽi , ṽj ∈ G c , are joined by an edge, if there exists at least one node u ∈ G that maps to ṽi , that shares an edge with at least one node v ∈ G that is mapped to ṽj ∈ G c . The weight of each edge in G c ,denoted by A c (ij), embodies the cumulative edge strength between the corresponding supernodes. This weight is determined by the sum of A uv for all (u, v) pairs where u ∈ ṽi and v ∈ ṽj . The features of supernodes are derived as the average of constituent node features:F c (i) = 1 |( ṽi)| u∈( ṽi) F u .Notably, the label of a supernode is assigned based on the most prevalent class within it. The reader may like to refer to Algorithm 1 for the steps in UGC. A matrix C ∈ 0, 1 N ×n represents the partition of nodes, with N as the count of nodes in the initial graph. The element C ij equals 1 if vertex v i is associated with supernode ṽj . Crucially, every node is assigned a unique h i value, ensuring an exclusive mapping to a supernode. This constraint harmonizes with the formulation of supernode guarantees at least one node per supernode. Thus, each row of C contains only one non-zero entry, leading to orthogonal columns. This matrix C satisfies the conditions specified in equation 1.By utilizing C, we calculate the adjacency matrix A c for G c by A c = AC. As each super-edge consolidates multiple edges from the original graph, the total edge count in the coarsened graph is notably fewer than m. This results in a considerably sparser adjacency matrix A c compared to A. The parameter bin-width r decides the size of the coarsened graph G c . For a particular coarsening ratio R, we find the corresponding r by divide and conquer approach on the real axis, which is similar to binary search. Algorithm 2 shows the method by which we find the r for any given R for G c . Figure 8 shows the relation of r with R for two datasets: Cora & Coauthor CS. It is observed that the R increases as the r increases. For each dataset Bin-width finder is a hyper-parameter that needs to be run only once, and hence it is not included in the reported time complexity.where N is the node count, L is the number of projectors, and d is the feature vector dimension. Key contributions come from three phases: hashing nodes(Line 1-7), aggregating bins(Line 8-12), and computing supernode features(Line 14-18). This analysis demonstrates UGC's scalability for large-scale graph coarsening tasks while maintaining vital structural characteristics. For detailed anaylsis please refer Appendix A.10. 
quality of the coarsened graph: 
 It is desired that coarsened graph G c is similar to the original graph G. In this section, we have introduced various measures to assess the quality of coarsened graphs from multiple perspectives. Even though each of these characteristics has a unique sense of similarity, coarsening is better when these error levels are lower across all of them. Spectral similarities: REE compares the Laplacian matrices of the coarsened and the original graph, as it measures the similarity between the eigenspace of G and G c . A low value of REE is desired for higher spectral similarity. REE is defined asREE(L, L c , k) = 1 k k i=1 | λi-λi| λiwhere λ i and λi are top k eigenvalues of Laplacian original (L) and Laplacian coarsened graph(L c ) matrix respectively. Please refer to Section 5.3 for results.Structural similarities: When moving from a G c representation back to the G, we quantify the disparity between the original and projected data using the Hyperbolic Error (HE). HE indicates the structural similarity between G and G c with the help of a lifted matrix along with the feature matrix X of the original graph. HE Bravo Hermsdorff & Gunderson (2019) defined as HE = arccosh(||(L-Llift)X|| 2 F ||X|| 2 F 2trace(X T LX)trace(X T LliftX) + 1)where L and X ∈ R N ×d are the Laplacian, and X is the feature matrix of the original input graph, and L lift is the lifted Laplacian matrix defined in Loukas & Vandergheynst (2018) asL lift = CL c C T where C ∈ R n×N is the coarsening/loading matrix and L c is the Laplacian of G c .LSH ensuring intra supernode similarity: The LSH family used in our framework is based on p-stable distributions, which ensures that the probability of two nodes going to the same supernode is directly related to the distance between their features (augmented features for UGC). This is expressed in the below Theorem from Indyk & Motwani (1998):Theorem 4.1 The probability that two nodes v and u will collide and go to a supernode under a hash function drawn uniformly at random from a 2-stable distribution is inversely proportional toEQUATIONThe above result will be used to check if the mapping of the nodes to the supernode ensures the distance and hence similarity property.Proof : The proof is deferred to appendix A.4ϵ-similarity: The previously discussed metrics primarily utilize either the adjacency matrix or the feature matrix independently. However, as we are using augmented feature matrix for hashing, it becomes essential to introduce a measure that takes both feature and adjacency information into account simultaneously. The Dirichlet energy (DE), employed to measure the smoothness of graph signals, is defined utilizing the graph Laplacian matrix L ∈ S L and the feature matrix X as Loukas (2019) suggested to use the follow-DE(L, X) = tr(X T LX) = -i,j L ij ∥x i -x j ∥ 2 .ing induced semi-norms ∥X∥ L = √ x T Lx, ∥X c ∥ Lc = x T c L cx c and defined ϵ-similarity via Theorem 4.2.Theorem 4.2 Given a Graph G and a coarsened graph G c they are said to be ϵ similar if there exists some ϵ ≥ 0 such that:(1 -ϵ)∥X∥ L ≤ ∥X c ∥ Lc ≤ (1 + ϵ)∥X∥ L (4)where L and L c are the Laplacian matrices of G and G c respectively.Proof: The proof is deferred in the Appendix A.6This definition is directly applied to our framework UGC as our loading matrix C discussed in section 2.1 follows constraints discussed in equation 1 making L c an laplacian matrix(L c = C T LC).The coarsened graph G c generated through UGC exhibits a high degree of similarity, within the range of ϵ, to the original graph G. It has been empirically demonstrated that this coarsened representation performs exceptionally well across various downstream tasks. Nonetheless, for the purpose of achieving a more refined and stringent upper limit on the permissible ϵ value (where ϵ ≤ 1), a potential step involves introducing modifications to the feature learning procedure of the supernodes G c .Bounded ϵ-similarity: It is important to note that the ϵ-similarity measure introduced in Loukas (2019) does not incorporate features. Instead, it relies on the eigenvector of the Laplacian matrix to compute similarity, which limits its ability to capture the characteristics of the associated features along with the graph structure. Kumar et al. (2023) re-define Theorem 4.2 but with feature matrix. Once we get the loading matrix C using UGC as discussed in Section 3.2 we usedF c (i) = 1 |π -1 ( ṽi)|u∈π -1 ( ṽi) F u to learn the new feature-vectors of our super-nodes, where F u is the augmented feature vector of node u from G. To give a bound on the ϵ similarity(≤ 1) we suggest to update F c ( F ) by minimizing the termmin F f ( F ) = tr( F T C T LC F ) + α 2 ∥C F -F ∥ 2 F (5)Proof: The proof is deferred in the Appendix A.7.Using the new update rule of ∥ F ∥ Lc we have FLc ≤ ∥F ∥ L , we get ϵ Kumar et al. (2023) for more details. Scalable Training of GNNs: In addition to above comprehensive analysis, we have rigorously assessed the practical utility of our coarsened graph in downstream tasks. The coarsened graph is employed for training a Graph Convolutional Network (GCN) model, which is subsequently utilized to make predictions on the test data of the original nodes. It is important to emphasize that the intricacies of the Graph Neural Network (GNN) architectures fall outside the scope of this paper, as our primary focus remains the validation of our coarsened graphs. To this end, we adopted a standardized 2-layer GCN model, with detailed parameters conforming to the guidelines outlined in Huang et al. (2021) . This study advocated the utilization of coarsened graphs for scalable GNN training. Results are discussed in Section 5.5. experiments conducted for this work were performed on an Intel Xeon W-295 CPU and 64GB of RAM desktop using the Python environment.= |∥F ∥ L -∥ F ∥ Lc | ∥F ∥ L ≤ 1 where ϵ ≤ 1 refer 
experiments for: 
 Run-time analysis. The primary focus of our algorithm's contribution lies in computational efficiency. The findings of this section provide empirical support for our assertions regarding time complexity. The time required to derive the coarsening matrix C using UGC is summarized in Table 2 . By referring to this Table, it becomes evident that UGC exhibits a remarkable advantage, surpassing all current algorithms across diverse datasets. Our model outperforms existing methods by a substantial margin. While other methods struggles at large datasets like physics, UGC is able to coarsen down massive datasets like Yelp, which was previously not possible. It should be emphasized that the time taken by UGC on the Reddit dataset which has 7× more number of nodes compared to Physics is one-third the time taken by the fastest state-of-the-art methods on the Physics dataset. This Table also encompasses heterophilic datasets, computational efficancy is clearly visible with these datasets as well. Figure 4 : Top 100 eigenvalues of the original and coarsened graph at three different coarsening ratios: 30%, 50%, and 70%. We can observe that the spectral property is maintained across all coarsening ratios for all coarsened graphs. For a lower coarsening ratio, this approximation (REE) is more accurate.As mentioned in section 4, we use relative eigen error (REE) and hyperbolic error (HE) as the evaluation metrics to measure the spectral and structural similarity of our coarsened graph. Eigenvalues preservation can be clearly seen in Figure 4 where we have plotted the top 100 eigenvalues of original and of coarsened graphs. We can see that spectral property is preserved even for 70% coarsened graph for most of the datasets. This approximation is more accurate for a lower coarsening ratio i.e smaller the graph the bigger is Relative Eigen Error (REE). The Relative Eigen Error for all approaches across all datasets is shown in Table 3 for a fixed 50% coarsening ratio. REE value of UGC is comparable with most of the algorithms. Although we also have coarsened Graphs for large datasets like Yelp and Reddit, eigen error calculation for these datasets was out of memory so we have used EOOM while other methods fail to find even the coarsened graph hence the term OOM. Figure 5 illustrates how, for different techniques, the eigen error, hyperbolic error, and GCN accuracy change as the coarsening ratio is altered. 5.4 LSH similarity and ϵ-bounded results In our experiments, we empirically validated the equation 3. We achieved this validation by utilizing a distance matrix derived from node features. We examined if the distance between any node pair was below a specific threshold, and then using the partition matrix given by UGC we verified if they shared the same supernode or not.Our evaluation involved counting successful matches, where nodes belonged to the same supernode, and failures, where they did not. We subsequently calculated a probability measure based on these counts. Part a) and b) of Figure 6 2021), we investigate how our graph coarsening approach can enhance GNN scalability for training, bridging the gap between GNNs and efficient processing of large-scale data. UGC(feat) represents a specific scenario within our framework, wherein only the feature values are considered for hashing, thereby obtaining the mapping of supernodes. To comprehend the significance of incorporating the adjacency vector, we have added the results for both UGC(feat) and UGC(augmented feat).Experimental Details. We employed a single hidden layer GCN model with standard hyperparameters values Kipf & Welling (2016) . Coarsened data is used to train the GCN model and all the prediction is being done on original graph data. The learned weights on the coarsened graph G c , are then used for making predictions on the original graph, G. The relation between coarsening ratio and accuracy can be clearly seen from the Table 6 i.e if we reduce the graph more and more we starts to see a slight decrease in accuracy values. Hence there will always be a trade-off when it comes to coarsening ratio and quality of reduced graph. We have included a Figure 7 which shows how much we have gained in computational time and what is the change in the accuracy values when compared to the existing best model for different datasets. Table 4 compares the accuracy among all the approaches with all datasets when they are coarsened down by 50%. We have used t-SNE van der Maaten & Hinton ( 2008) algorithm for visualization of predicted node labels shown in Figure 9 . It is evident that even with 70% coarsened data training GCN model is able to maintain its accuracy. Very few of the data points are miss-classified(mostly outliers) when we increase our coarsening ratio to reduce the original graph. 3 and Table 4 . Our methods, UGC(feat) and UGC(aug. feat.), demonstrate significant enhancements in node classification accuracy and REE values across heterophilic datasets. Comparing these results, we observe that traditional approaches exhibits moderate performance in terms of accuracy. However, when employing our method UGC(features), we achieve notable improvements in accuracy, surpassing the performance of these traditional approaches. Moreover, the true potential of our approach is unleashed when incorporating both features and adjacency information i.e augmented features. This combined approach showcases remarkable accuracy gains, outperforming all other methods by a considerable margin. Our method not only yields competitive results in the homophilic graph scenario but also exhibits substantial improvements when applied to heterophilic datasets. 
conclusion: 
 In this paper, we present a framework UGC for reducing a larger graph to a smaller graph. We use hashing of augmented node features inspired by Locality Sensitive Hashing (LSH). As expected, the benefits of LSH are also reflected in the proposed coarsening algorithm. UGC has linear time complexity with respect to the number of nodes. To the best of our knowledge, it is the fastest algorithm for graph coarsening. Through extensive experiments, we have also shown that our algorithm is not only fast but also preserves the spectrum and smoothness properties of the original graph. Furthermore, it is worth noting that UGC represents a first work in the domain of graph coarsening for heterophilic datasets. This framework addresses the unique challenges posed by heterophilic graphs and has demonstrated a significant increase in node classification accuracy following graph coarsening. This is a significant accomplishment, as it opens up new possibilities for training GNNs on large and complex graphs. In conclusion, we believe that our framework, is a major contribution to the field of graph coarsening and offers a fast and effective solution for simplifying large networks. Our future research goals include the exploration of different hash functions and novel applications for the framework. 
 
 Appendix: A.1 Stable Distribution A distribution D over R is called p-stable, if there exists p ≥ 0 such that for any n real numbers v 1 ....v n and i.i.d. variables X 1 ....X n with distribution D, the random variable i v i X i has the same distribution as the variable ( i |v i | p ) 1/p X where X is a random variable with distribution D Datar et al. (2004) . It is known Zolatarev (1983) that stable distributions exists for p ∈ (0,2].• Cauchy distribution D c , defined by the density function c(x) = 1 π 1 1+x 2 , is 1-stable.• Gaussian (normal) distribution D g , defined by the density function g(x) = 1 √ 2π e -x 2 2 is 2-stable.However, it is known Chambers et al. (1976) that one can create p-stable random variables effectively from two independent variables distributed uniformly across [0,1] despite the lack of closed form density and distribution functions.Stable distributions have diverse applications across various fields (see survey Nolan (2005) for details). In computer science, they are utilized for "sketching" high-dimensional vectors, as demonstrated by Indyk (Indyk (2006) ). The key property of p-stable distributions, mentioned in the definition, enables a sketching technique for high-dimensional vectors. This technique involves generating a random vector w of dimension d, with each entry independently chosen from a p-stable distribution. Given a vector v of dimension d, the dot product w • v is also random variable. A small collection of such dot products, corresponding to different w's, is termed as the sketch of the vector v and can be used to estimate ||v|| p Indyk (2006) . However, instead of using the sketch to estimate the vector norm we are using it to assign hash values to each vector. These values map each vector to a point on the real line, which is then splitted into equal width segments to represent buckets. If two vectors v and u are close, they will have a small difference between l p norms ∥v -u∥ p , and they should collide with a high probability.A.2 Additional experiments for LSH scheme We have further validated our theoretical results through a secondary experiment. This LSH family which we discussed above says as the distance between two nodes increases, the likelihood of them being assigned to the same bin decreases, hence we will have more number of supernodes now. By increasing the bin-width, we can effectively reduce the number of supernodes. This phenomenon is evident when considering the average distance between node pairs in various graphs and the corresponding binwidth required to achieve a 30% coarsening ratio. The table below illustrates these findings: The results in the table clearly demonstrate that as the average distance between nodes increases, the required bin-width also increases when maintaining the same coarsening ratio. This observation highlights the importance of considering the distance metric and bin-width selection during the graph coarsening process to effectively control the number of supernodes and achieve desired coarsening ratios. Figure 8 shows trend of coarsening ratio when we change bin-width.A.3 Bin-width This section discusses the impact of bin-width on the coarsening ratio see Figure 8 . Algorithm 2 outlines the procedure for determining the appropriate bin-width value that corresponds to a desired coarsening ratio. , n ← UGC(G, L, h, N ) 9:ratio ← (1 -n N ) 10: end while 11: return r A.4 Proof of Theorem 4.1 Let f p (t) denote the probability density function of absolute value of our stable distribution(Normal distribution), and let c = ||v -u|| p for two node vectors v, u and r is the bin-width. Since we have a random vector w from our stable distribution, v.w-u.w is distributed as cX where X is a random variable from our stable distribution. Therefore our probability function isEQUATIONFor a fixed bin-width r the probability of collision decreases monotonically with c = ||v -u|| 2 . For Defination, 2.1 the hash family will be (r 1 , r 2 , p 1 , p 2 )-sensitive where p 1 = p(1) and p 2 = p(c) forEQUATIONWe have p(1) = S 1 (1) -S 2 (1) ≥ 1 -e r 2 2 -2 √ 2πr ≥ 1 -A r, for some constant A > 0. This implies that the probability that u collides with v is at least (1 -A r ) ≈ e -A . Thus the algorithm is correct with the constant probability. If c 2 ≤ r 2 2 , then we haveEQUATIONA.5 Application of coarsened graph for GNNs This section contains additional results related to the scalable GNN training. Figure 10 shows the GNN training pipeline. Figure 9 shows Visualization of GCN predicted nodes when training is done using the coarsened graph. Table 6 illustrates a direct correlation between accuracy and coarsening ratio. As the graph is coarsened more aggressively, we observe a corresponding decrease in the classification accuracy of the GCN model. A.8 Importance of Augmented Features See Figure 11 which showcase the importance of considering the augmented feature vector. It can be seen from the figure that when coarsened using Augmented features supernodes have more intra-node similarity.A.9 Additional Results Table 7 and time complexity is O(N). We have compared the partition matrix computational of all other methods with ours.A.11 UGC is model-agnostic While our initial validation utilized GCN to assess the quality of our coarsened graph but our framework is not bound to any specific graph convolutional network (GCN) architecture. We extended our evaluations to include other prominent graph neural network models. Results from three diverse models, namely GraphSage, GIN (Graph Isomorphism Network), and GAT (Graph Attention Network), have been incorporated into our analysis. We have provided empirical evidences in Table 9 . These additional experiments demonstrate the robustness and model-agnostic nature of our framework. We believe this flexibility further enhances the applicability and utility of our proposed framework in various graph-based applications. 


Decision: This paper present a framework for graph coarsening to reduce a larger graph to a smaller graph that works on both homophilic and heterophilic graphs. Empirical results verify the effectiveness of the method in preserving graph properties as well as in in coarsening speed.

Reviews: review: paper_summary: paper_summary: This paper present a framework UGC for graph coarsening to reduce a larger graph to a smaller graph. It uses Locality Sensitive Hashing (LSH) of augmented node features, and works on both homophily and heterophilic graphs. Experiments could verify its effectiveness in original graph property perservation and efficiency in coarsening speed.
strength_weakness: strength_weakness: Here are some questions need to be further addressed:

W1: In lines 149-150, it claims that the augmented feature vector is calculated by dot product and concatenation, it is not very clear that how to concate A with node features X?


W2: Some figures, e.g., figure 1 and figure 4, is not very clear for visualization.

W3: In table 4, for comparisons in GNN classification accuracy, it would be better to involve some other graph size reduction methods, like GCOND, SFGC to show the performance.

W4: Is there any ablation study to show the effectiveness of the proposed augmented feature vector?

W5: More detailed explanations and analysis of whether the proposed method could adapt heterophilic graph well are expected. Is there any specific design targeting for heterophily?
questions: questions: See Weaknesses.
limitations: limitations: Yes.
paper_summary: paper_summary: The authors propose a novel Universal Graph Coarsening (UGC) framework, which is suitable for both homophilic and heterophilic datasets. UGC integrates node attributes and adjacency information to leverage dataset heterogeneity effectively. The results demonstrate that UGC is significantly faster (4x to 15x), maintains spectral similarity, and outperforms existing methods in terms of computational efficiency, eigen-error, and downstream processing tasks, especially at 70% coarsening ratios. The key contributions highlight UGC's universal applicability, efficiency, and information preservation.
strength_weakness: strength_weakness: For ScalableTrainingof Graph Neural Networks section, there are no detailed discussion on GNN models except GCN.
questions: questions: For Table 4, why only GCN results are shown? I also expected results for GIN GAT and GraphSage.
limitations: limitations: Limitation is discussed in detail in papers.
paper_summary: paper_summary: This paper proposes a new Universal Graph Coarsening (UGC) framework designed to handle both homophilic and heterophilic graphs. The UGC framework is capable of retaining important spectral properties, including eigenvalue error, hyperbolic error, and 𝜖-similarity measure. Experimental results demonstrate significant improvements in both performance and effectiveness with the UGC framework.
strength_weakness: strength_weakness: 1. Although the LSH strategy is much faster than other methods, the memory space overhead is non-negligible. Could you please measure the space complexity and provide a further empirical evaluation of the method? Additionally, how is the number of hash functions (𝑙) configured?
2. The paper lacks a detailed description of the experimental setup, including software and hardware environments, as well as the parameters used for different algorithms.
3. From Figure 5, we can see that UGC does not exhibit lower errors (RRE and HE) at lower Coarsening Ratios. I think it questions the claimed advantage of preserving spectral properties. Can the authors give a detail explanation?
4. Figure 5 illustrates that the methods (e.g., VAE, VC) do not maintain a monotonic relationship between the Coarsening Ratio and RRE/HE Error. Additionally, UGC does not exhibit a clear advantage across the overall Coarsening Ratio. Can the authors make a further clarify?
5. Table 3 does not prove the claim of “UGC (features) method achieves substantial accuracy enhancements” over GCN, GraphSAGE, GIN and GAT. Can the authors utilize UGC to more recent models, e.g., 3WL-GNNs, heterogeneous graph neural networks?
6. Minor issues：
    * In Figure 2, the specific meanings of a, b, and c are not labeled in the diagram.
questions: questions: Please see the weakness section.
limitations: limitations: The authors have adequately addressed the limitation of the potential negative societal impact of their work.
paper_summary: paper_summary: Graph coarsening aims at scaling an original large graph into a small graph. This paper proposes a graph coarsening method which was designed to be equally suitable for homophilic and heterophilic datasets, specifically, aggregating node clusters identified by a hash function. This paper is one of the pioneering works exploring graph coarsening in heterophilic graph datasets, and the proposed solution seems promising. However, the current formulation of the proposed method and some of the claims in the paper are not rigorous and solid enough.
strength_weakness: strength_weakness: -	The presentation of this paper is unclear. Check out `Questions’.
-	The current formulation of the proposed `Hash functions’ is ambiguous and biased. Check out `Questions’.
-	Some claims were in fact wrong. Check out `Questions’.
questions: questions: -	Line 4. `vital insights’, `essential features’ in line 5. and ‘vital information’ in line 20. are too vague. I suggest being more specific and keeping the phrasing unchanged.
-	Line 67-68. `The Graph Coarsening(GC) problem \bf{may be} thought of as learning a coarsening matrix….’ Is it or is it not? A formal definition of the Graph Coarsening problem is required whether cited from others or by you.
-	Line 128-129. `Due to this, these methods are extremely computationally demanding and defeat the purpose of reducing the original graph.’ This statement suggests that ‘GNN-based Graph Condensation’ is useless. I suggest being more objective.
-	Line 143-144.` The concepts of homophily and heterophily in graphs are primarily concerned with whether the edges between two nodes align with their respective features.’ is not correct. Recall that homophily and heterophily are defined by whether edges align with labels, not features. You need to state a hypothesis or experimentally verify that: `the same labels imply similar features’.
-	Line 155-160. The current formulation hash function is biased to node degree distribution since you concat the adj with node feature. Consider this example that a graph has 1 node whose degree is 999 and other 999 nodes’ degree is 1 (a radial graph). In this case, the hash value of the degree 999 node will be significantly larger than the other nodes, e.g. 90-99 to 1-10, and setting `r’ parameter only makes it worse. Meanwhile, the 11-89’th hypernode is empty. This is an extreme case of long-tail distribution of node degrees, however, simple concatenation inevitably causes the number of aggregated nodes in the hypernode to be uneven, specifically strongly correlated with the node distribution.
-	Again, concat the adj with node feature is ambiguous. Considering that the hash result will change w.r.t. the change of index order of nodes.
-	What is ‘|||’ in the proof of Theorem 3.1 in line 575? Moreover, the derivation in the proof is speculative. You need to explain clearly why each step of the inequality holds.
-	Line 180-181. `It means that the adjacency matrix A~ has a substantially smaller number of non-zero elements than A.’ is not correct. Consider a chain graph with N nodes, N-1 edges, and if the head node and the tail node were aggregated, it became a circle with N-1 nodes and N-1 edges, where the number of edges remains unchanged.
-	Where is the introduction of baselines from `Var.Neigh.’ to ` Kron’? If somewhere else, I suggest moving to Chap experiments.
-	Figure 7 is confusing. Present `actual time saved’ (time by downstream task on original graph – time by downstream task on coarsened graph + time by coarsening the graph) together with downstream task performance loss/gain by your method and baselines will be more meaningful.
limitations: limitations: The authors have adequately addressed the limitations.

Comments: title: Looking forward to your feedback on rebuttal
Eagerly awaiting feedback on rebuttal
Looking forward to your feedback on rebuttal
comment: Thanks for your reply. It resolved my concern, and I decided to increase my rating.
Dear Reviewer,

We thank you for the insightful comments on our work. Your suggestions have now been incorporated in our revision and we are eagerly waiting for your feedback. As the author-reviewer discussion phase is approaching its conclusion in just a few hours, we are reaching out to inquire if there are any remaining concerns or points that require clarification. Your feedback is crucial to ensure the completeness and quality of our work.

We are pleased to share that the responses from other reviewers also indicate a positive inclination toward acceptance. Your support in this final phase, would be immensely appreciated.

regards,

Authors
Dear Reviewer,

Since we are only a day away from the completion of the discussion phase, we are eagerly awaiting your feedback on the rebuttal.

Your review pointed out important empirical studies that further enhanced our work. We have incorporated all of them and we thank the reviewer again for the deep insightful comments on our work. We would love to discuss more if any concern remains unaddressed. Otherwise, we would really appreciate it if you could support the paper by increasing the score.

regards,

Authors
I have read your replies and the replies corresponding to those of other fellow reviewers. My questions Q1, Q2, Q3, Q4, Q5, Q7, Q8, Q9, Q10 are settled; Q6 remains a shortcoming of the proposed method for the need of fixed node ordering, which should not be the concern of a `Graph model'; Consider the progresses been made, I recommend to consider `Borderline Accept' this paper where reasons to accept outweigh reasons to reject.
Thank you very much for your reply. My assessment of the paper remains positive.
Dear Reviewers,

Thank you once again for all of your constructive comments, which have helped us significantly improve the paper! As detailed below, we have performed several additional experiments and analyses to address the comments and concerns raised by the reviewers.

Since we are into the last two days of the discussion phase, we are eagerly looking forward to your post-rebuttal responses.

Please do let us know if there are any additional clarifications or experiments that we can offer. We would love to discuss more if any concern still remains. Otherwise, we would appreciate it if you could support the paper by increasing the score.

Thank you!

Authors