UGC: Universal Graph Coarsening
Authors: Mohit Kataria
Sandeep Kumar
Jayadeva Jayadeva
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Coarsening
Graph Neural Networks
Locality sensitive hashing
Heterophilic Graph
Scaling Graph Learning
Primary area: graph_neural_networks
TL;DR: UGC is a graph coarsening framework which is extremely fast, has lower eigen-error, and yields superior performance on downstream processing tasks.

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.

UGC: Universal Graph Coarsening
Mohit Kataria'
Sandeep Kumar
Jayadeva?!
Mataa.Kat seai an
ksandeep @ee. iee.iitdacciin
jayadeva@ee.itdda.. iitd.aac.inn
Yardi School of Artificial Intelligence
Department of Electrical Engineering
Bharti School of Telecommunication Technology and Management
Indian Institute of Technology Delhi
Abstract
In the era big data, graphs have emerged as 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 coars- ening seeks to simplify large graphs while maintaining the basic statistics of the graphs, such as spectral properties and e-similarity in the coarsened graph. This ensures that downstream processes are more efficient and effective. Most published methods suitable for homophilic datasets, limmting their universal use. We propose Universal Graph Coarsening (UGC), a framework equally suitable for homophilic and heterophilic datasets. UGC integrates node attributes and adjacency information, leveraging the dataset's s heterophily factor. Results on benchmark datasets demonstrate that UGC preserves spectral similarity while coarsening. In comparison to existing methods, UGC 4x to 15 x faster, has lower eigen-error, and yields superior performance on downstream processing tasks even at 70% coarsening ratios."
1 Introduction
Graphs have emerged as highly expressive tools to represent diverse structures and knowledge in various fields such as social networks, bio-informatics, transportation, and natural language processing [1-3]. They
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(GC), a widely used technique simplify graphs while retaining vital information, making them more manageable for analysis [4]. It has been applied successfully in various tasks [5-10]. Preserving the structural information of the graph is crucial in graph coarsening algorithms to ensure the fidelity of the coarsened graphs. A high-qualing coarsened graph retains essential features and relationships, enabling accurate results for downstream tasks. Additionally, computational efficiency is equally vital for scalability, as large-scale graphs are common real-world applications. 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 provide us with advantages in terms computational efficiency. As a result, our approach exhibits a linear time complexity, making it highly efficient even for large graphs
efficient coarsening method should ensure that the
Graph datasets often exhibit a blend of homophilic and heterophilic traits [11, 12]. Graph Coarsening (GC) has been widely explored on homophilic datasets, but, to the best of our knowledge, has never been applied to heterophilic graphs. We propose Universal Graph Coarsening UGC, an approach that works well on both. Figure 2 illustrates how UGC uses graph's adjacency matrix as
Code available UGC
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

{1 -
<P-P3
P22
glV, A)
Augmented Peatures
Hashing
A Fe
Gen (rain(G.)
UGCH ''euclEsation
Downstream Tasks usingg.
A.,F
Node formatioo
Coarsening Matrix
This figure illustrates our framework, UGC, which has three main modules a) Generation of an augmented matrix by incorporating feature and adjacency matrices while using heterophily measure b) Generation of coarsening matrix C using augmented features via Hashing, and c) Generation of coarsened graph Ge from C followed by its utilization downstream tasks.
Figure 2:
well as the node feature matrix. UGC relies hashing, lending computational efficiency. UGC exhibits linear time complexity, enabling fast processing of large datasets. Figure demonstrates the computational time gains of UGC among graph coarsening methods. UGC surpasses the fastest existing methods by about 6x on the Physics dataset and 9x on the Squirrel dataset. UGC enhances the performance of Graph Neural Networks (GNN) models in classification tasks, indicating its suitability for downstream processing. UGC coarsened graphs retain essential spectral properties and show low eigen error, hyperbolic error, and c-similarity measure. In nutshell, UGC is fast, universally applicable, and information-preservinp preserving.
Key Contributions.
We proposed novel framework that is extremely fast compared to other existing methods for graph coarsening. It is also shown to be helpful and effective for graph- based downstream tasks.
153
Squirell
The
UGC is the first to handle het- erophilic datasets for coarsening.
UGC can retain important spectral properties, such as eigen error, hy- perbolic error, and e-similarity mea- sure, which ensures the preservation key characteristics and informa- tion of the original graph during the graph coarsening.
Figure 1: This figure illustrates the computational time com- parison among graph coarsening methods to learn coars- ened graph over ten iterations. UGC outperforms the fastest existing methods by approximately 6x on the Physics dataset and 9 x on the Squirrel dataset.
Background and Problem Formulation
A graph is represented using G(V, A, X) where V = {U denotes set of N vertices,
A E N is the adjacency matrix and Aij > 0 indicates edge (v,, (0),0;) between nodes e; and uj-
X E IRM xx denotes the feature matrix where 5th row of X is feature vector X; R. associated with node V;. The degree matrix D is a diagonal matrix, where Dj E, Ag- L R N is
Lij < 0, Vi + j; La - E Luj) as defined in [14, 15]. The adjacency matrix A and Laplacian matrix L associated with the graph are related as follows: Ag Lig for i o and A., 0 for i
Laplacian matrix, L = D - A [13], and it belongs to the set S₁ { E RNxNILj:

---

1
1
1
0
0
07
CT
0
0
ge
0
0
0
1
g
(a)
(h)
Figure 3: Graph coarsening toy example, a) Coarsening matrix, b) Original graph 9 and corresponding coarsened graph Ge
Both I. and can represent the same graph. Hence, a graph G(V, A, X) can also be represented as X), with either representation utilized required within the paper.
Problem. The objective is reduce an input graph g(V, A, X) with N-nodes into a new graph G.(V, X).. with n-nodes and X E Rndd where nt < N. The Graph Coarsening(GC)) problem requires learning of coarsening matrix C E RNNx, which is linear mapping from V V. A linear mapping ensures that similar nodes in 9 are mapped to the same super-node in ge- s.t. X C² X. Every non-zero entry Cij denotes the mapping of the 7th node of G to the jth super-node Go. This C matrix belongs to the following set:
s=
=, 1, (CT 0, V. J. (C,C)) = d7. |1 110 2 21} (1) S SE C.j E (0, =
where di, means the number of nodes in the supeennoo. The condition (C,, .T)) 0 ensures that each node of G is mapped to a unique super-node. The constraint ||CT 2 1 requires that each super-node contains at least one node. Consider the 8-node graph in Figure 3b. Nodes 1, 2, 3, and 4 are mapped to super-node A, while nodes 6, 7, and 8 are mapped to super-node C. Hence, the coarsening matrix C is given in Figure 3a. The goal is to learn this C matrix such that G and G. are similar. The E- -iimilarity is a widely used similarity measure for graphs with node features, as entails comparing the Laplacian norms of the respective feature matrices. The graphs g(V, A, X) and (V. A, X) are said to be e-similar if there exist 2 such that
(2) where L and Le are the Laplacian matrices of G and G. respectively, |X|| = (tr(XTLX) and
(1 - X|I, < |1. S (1 + X||
|| = /tr ( The quantity tr(XT = - Ei, L,g|=;; 2, 112 is known as Dirichlet
Energy (DE), which is employed to measure the smoothness of node features where x; and xy are the node features of nodes i and [14].
Goal: Given a graph A,,,A, X) of N nodes, construct a coarsened graph G.(V, X) with nodes, such that they are é é similar.
Homophilic and Heterophilic datasets. Graph datasets may demonstrate homophily and heterophily properties [16-19]. Homophily refers to the tendency of nodes to be connected to other nodes of the same class type, while heterophily signifies the tendency of nodes connect with nodes of different classes. heterophily factor 0 I a < 1 may be used to denote the degree of heterophily. is calculated as the fraction of edges between nodes of different classes to the total number of edges. A strongly heterophilic graph (a + 1) has the most edges between nodes different classes, suggesting diverse network with mixed interactions. Conversely, weak heterophily strong homophily (a >> 0) occurs in networks where nodes predominantly connect with others of the same class.
Locality Sensitive Hashing. Locality Sensitive Hashing (LSH) is a linear time, efficient similarity search technique for high dimensional data [20-23]. It maps gigh-dimensional vectors to lower dimensions while ensuring that similar vectors collide with high probability. LSH uses a family of hash functions map vectors to buckets, enabling fast retrieval and similarity search. It has found applications in image retrieval [24], data mining [25], and similarity search algorithms [26]. LSH family is defined as
Definition 2.1 Let d be a distance measure, and let dj < d2 be two distances. A family of functions F is said to be (di, d2, p1,
-sensivvee if for every F the following two conditions hold:
1. If (xx y) S di then probability [f(x:) = [()) 2 P1
2. If d(zz v) de then probability [f(z) f(y) P2
3

---

UGC uses LSH with a set of random projectors to map similar nodes to the same super-node. The projection is computed as <am where wy is a randomly selected d-dimensional projector
vector from a p-stable distribution (see Appendix A); æ represents the d' didimnnsional data sample, and r is the width of each quantization bin.
Related Works. The literature is replete with graph reduction methods and their applications; they may be broadly classified into three categories:
1. Optimization and Heuristics: Loukas [15] proposed advanced spectral graph coarsening algo- rithms based on local variation to preserve the original graph's 's spectral properties. Two variants, viz. edge-based (LVE) and neighhorhood- based (LVN), select contraction sets with small local variation in each stage but have limitations in achieving arbitrary coarsening levels. Heavy edge matching (HE) [9. 27]. determines the contraction family by computing maximum- meight matching based on the weight of each contraction set. The Algebraic Distance method proposed in [27, 28] calculates the weight of each candidate set using an algebraic distance measure. The affinity method [29]. inspired by algebraic distance, uses the vertex proximity heuristic. The Kron reduction method [30] was originally proposed for electrical networks but is too slow for large networks. FGC [14, 31] considers both the graph structure and the node attributes as the input and, alternatively, optimizes C. The above-mentioned methods are computationally and memory-intensive.
2. GNN based: GCond [32] and SFGC [33] GNN-based graph condensation methods. These works proposed the online gradient matching schema between the synthesized small-scale graph and the large-scale graph. However, these methods have significant issues regarding computational time and generalization ability. First, they require training GNN models on the original graph to get smaller graph as they imitate the GNN training trajectory on the original graph through gradient matching. Due to this, these methods are extremely computationally demanding and may not be suitable for the scalability of GNN models. However, these methods can be beneficial for other tasks, like solving storage and visualization issues. Second, the condensed graph obtained using GCond [32] shows poor generalization ability across different GNN models [33] because different GNN models vary in their convolution operations along graph structures.
Scaling GNN viz. Graph Coarsening: SCAL [34] and GOREN [35] proposed to enhance the scalability for training GNN models using graph coarsening. It is worth noting that SCAL and GOREN are not standalone graph coarsening techniques. SCAL uses Louka's [15] work to coarsen the graph, then trains GNN models using the coarsened graph. While GOREN trying to improve the coarsening quality of existing methods.
3
The Proposed Framework: Universal Graph Coarsening (UGC)
The proposed UGC framework comprises three main components: (a) First, obtaining an augmented feature matrix F containing both node feature and structural information, (b) Secondly, using locality- sensitive hashing to derive the coarsening matrix C, (c) and Finally, obtaining the coarsened graph adjacency matrix Ae and coarsened features Fe.
Construction of Augmented Feature Matrix F. In order to create a universal GC framework suitable for all, it is important to consider features at both i) the node level, i.e., features, and ii) the structure-level, i.e., adjacency matrix, together. In this regard, we create an augmented feature matrix F, where each node's 's feature vector X; is augmented with its binary adjacency vector A,. We use the heterophily factor a discussed in Section 2 to balance the emphasis between node-level and structure- level information. The augmented feature vector for node v; is given using F; = (1: A.) where @ and denote the concatenation and dot product operations, respectively. Figure 11 in Appendix K illustrates a toy example of the process involved in calculating 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 GC is discussed in Appendix K (Figure 12).
Construction of Coarsening Matrix C. Let F; E IRd represent the augmented feature vector of node V/ Let W dxxl and b E R' be the hashing matrices used in UGC, with denoting the number of hash functions. The hash indices generated by 4h hash/projector function for hth node is given as
1 ht - *W, F, + ba)l
(3)
4

---

where r is hyperparameter called bin-width. The hash index that has the maximum occurrence among the hash indices generated by all hash functions is the hash value assigned the graph node Hence, the hash value for node u is given by
h4 = maaoOcurre .?.....
r controls the size of the coarsened graph Ge: empirically, we find that increasing r means reducing the size of the coarsened graph Ge- All nodes assigned with the same hash value map to the same super-node in Ge. The reader may like to refer to Algorithm for the steps in UGC. The element of coarsening matrix, Cij equals if vertex v; is associated with super-node Vj. Crucially, every node is assigned a unique la, value, ensuring an exclusive mapping to super-node. This constraint aligns with the formulation of super-node and guarantees at least one node per super-node. Thus, each row of C contains only one non-zero entry, leading to orthogonal columns. This matrix C satisfies the conditions specified in Equation I.
Algorithm 1 UGC: Universal Graph Coarsening
Require: Input GVV, X. Number of Projectors, WinWhdth
I: K(o.aje Erg. =Bul!
is heterophily factor, yı E R is node labels, E denotes edge list
[E] X
2: F {(1-
3: W ~ D(); W E gxxt denotes / projectors, and D is p-stable distribution
4: b ~ D(.); be R denotes sampled bias
5: H [
H E RNxt
6: n; < maxOccurence(H4;
(.,,3,,..,NN))...
7: for every node in V do
8: [o]] (-1
9: A.(i,) < 2(uEn-1
Ann. Vi,j E 21.
10: Fe(1)- i ---( Euex-1(u)) 1(0)) Fu, Vi m1,
11: return (V(Ve, Ac; Fol,C
Construction of Coarsened Graph G.. Let (V, A, F) represent the coarsened graph that is to be built. A pair of super-nodes, say 0; and Vy. in the coarsened graph Ge are connected, if any of the nodes, say n (T;) has edge to any of the nodes, say v E π -Tū) in the original graph, i... 3 (ū)) x -x>1() (et) such that Auo * O. The coarsened graph Ge is weighted, and the weight assigned the edge between nodes o and oj., is given by A.j = "(uen (()e)---(()))e-=>>00 A.r where Auv refers to the element (u, u) in the adjacency matrix A of graph G. The features of super-nodes are taken to be the average of the features of the nodes in the super-node i.e., F, 1ST [(JJ Emer- Fu. The super-node's 's label is chosen as the class that has the most instances.
From the C matrix, we can directly calculate the adjacency À matrix of G. using = C* AC which is the same as A.j. F can also be obtained using F = CT F where C is the coarsening matrix discussed earlier. Because each super-edge combines multiple edges from the original graph, the number of edges in the coarse graph is also much less than m. In general, the adjacency matrix has a substantially smaller number of non-zero elements than A. The pseudocode for UGC is listed in Algorithm 1. UGC gives coarsened graph Go(Lo, F) which also satisfies e-iimilarity (e 2 0).
Theorem 3.1 The input graph GLL, F) and the coarsened graph Ge(Le, F) obtained using the proposed UGC algorithm are e-similar with 2 0, i.e.
(1 -1- 1F I [IFILL, I (1+c)
(5)
where L and Le are the laplacian matrices of G and G. respectively.
Proof: The proof is deferred in Appendix I.
Universal Graph Coarsening with feature re-learning for Bounded c-similarity. The coarsened graph Ge generated through UGC exhibits a high degree of similarity, within the range of to the original graph G. It has also been empirically demonstrated that this coarsened representation performs exceptionally well across various downstream tasks. Nonetheless, to achieve a tighter e-bound, where (e < 1), potential step involves introducing modifications to the feature learning procedure of the super-nodes G..
5

---

It is important to note that the e-similarity measure introduced in [15] does not incorporate features. Instead, relies on the eigenvector of the laplacian matrix compute similarity, which limits its ability to capture the characteristics of the associated features along with the graph structure. Once we
get the loading matrix C using UGC discussed in Section we used F; |-- ((,) Euex-i(E. Fu
to learn the feature-vectors of super-nodes. Using F; we can satisfy the Theorem 3.1. However, to give strict bound on the similarity we updated F to F by minimizing the term
min f(F) tr(F CJ C LCF) a IIFF-FI
-
(6)
We aim to enforce the Dirichlet smoothness condition in super-node features using Equation The above equation is convex optimization problem from which we get a closed-form solution by putting the gradient w.r.t to F equal zero. Update rule for / can be derived as:
2C LCF + ac FF) - f f22
CF
We now have re-learnt features for super-nodes, please refer Algorithm 2 in Appendix which we call as UGC-FL UGC with feature learning. Using F we can give a more strict bound on simmilariiy.
Theorem 3.2 The original graph G(L, F) and coursened graph Ge(Lec F) obtained using the pro- posed UGC-FL algorithm are similar with 0 < S 1, i.e.
(1 (l-f)l S 111112, (1++))]
where I. and The the laplacian matrices of 9 and 9e respectively, and F and F are features matrix associated with original and coarsened graphs, respectively.
Proof: The proof deferred in Appendix J.
Novelty: The majority of current techniques involve coarsening the original graph and simultaneously learning the graph structure, which makes them computationally intensive. The UGC decouples this process, making it incredibly fast, first learning the coarsening mapping C' by capturing the similarity of features through hashing and then using the adjacency matrix only once as A CT AC for learning the coarsened graph's 's structure all at once. The UGC is easy to use, extremely fast, and produces better results for tasks requiring downstream processing.
Time Complexity Analysis of UGC. We have three phases for our framework. For the first phase, can Algorithm Line 5 is driving the complexity of the algorithm, where we multiply two F E TRNx xd and W E ddxx matrices, which results in (NVd).. In the second pass, the super-nodes for the coarsened graphs are constructed with the help of the accumulation of nodes in the bins. The main contribution of UGC is to these two phases i.e., Line 1-8. Till now, time-complexity is ((Nld) ONCC) where C is constant.
In the third phase. Lines 10-11 11, we calculate the adjacency and features of the super-nodes of the coarsened graph Ge. The computational cost of this operation is (m). where is the number of edges in the original graph G. and this is a one-time step. Indeed, the overall time complexity of all three phases combined is O(N + m) where m the number of edges. However, it's important to note that the primary contribution of UGC lies in the process of finding the coarsening matrix, whose time complexity O(N). We have compared the computational time for obtaining the coarsening matrix via UGC with the existing methods.
4 Experiments
In this section, we conduct extensive experiments to evaluate the proposed UGC against the existing graph coarsening algorithms. The conducted experiments establish the performance of UGC concern- ing i) computational efficiency, ii) preservation of spectral properties, and iii) potential extensions of coarsened graph G. into real-world applications.
We compare our proposed algorithm with the following coarsening algorithms, discussed in Section 2. UGC (feat) represents a specific scenario within our framework, wherein only the feature values are considered for hashing, thereby obtaining the mapping of super-nodes. To comprehend the

---

significance of incorporating the adjacency vector, we have added the results for both UGC (feat) and UGC (augmented feat).
Datasets, Our experiments cover widely adopted benchmarks, including Cora Citeseer, Pubmed [36], CS, Physics [37], DBLP [38]. Additionally, UGC effectively coarsens large datasets like Flickr, Yelp [39], and Reddit [40], previously challenging for existing techniques, We also present datasets like Squirrel, Chameleon, Texas, Film, Wisconsin [11, 12, 16, 17], characterized by dominant heterophilic factors. Table 6 in Appendix G provides comprehensive dataset details.
Table 1: Summary of run-time in seconds averaged over runs to reduce the graph to 50%.
Data/Method
Cora
Cite.
CS
PubMed
DBLP
Physies
Fliekr
Reddit
Yelp
Squirrel
Cham.
Cor.
Texas
Film
Neigh.
8.72
24.38
22.79
0OM
00M
33.25
12.2
Var. Edges
5.34
1.37
16.72
18.69
20.59
67.16
00M
00M
00M
46.45
12.65
1.31
0.76
26.6
Var. Clig.
7.29
9.8
21.59
61.85
36
69.80
00M
00M
00M
28.91
10.55
1.56
1.14
33.04
Heavy Edge
0.7
1.41
T.500
12.03
8.39
39.77
00M
00M
00M
18.08
5,41
1,62
1.17
11.79
Alg Dist
01.93
1.55
9.63
10.48
9.67
46.42
0OM
00M
DOM
18.03
5.24
1.58
0.81
12.65
Affinity GS
2.38
2.50
169.05
169.3
110.9
924.7
0OM
00M
00M
20,00
5.83
1,81
1.24
20.65
Kron
0.63
1.37
8.72
5.81
7.09
34.53
0OM
0OM
0OM
20.62
7.25
1.73
0.97
12,29
UGC
0.41
0.71
3.1
1.62
1,86
6.4
8,9
16.17
170,91
2.14
0.49
0.04
0.03
1,38
Run-Time Analysis. UGC's main contribution lies in its computational efficiency. The time required to compute the coarsening matrix C is summarized in Table 1. By referring to this Table, it becomes evident that UGC exhibits a remarkable advantage. surpassing all existing methods across diverse datasets. Our model outperforms existing methods by a substantial margin. While other methods struggle at large datasets like Physics( 34. 4k nodes), UGC is able to coarsen down massive datasets like Yelp(716, (.k nodes), which was previously not possible. It should be emphasized that the time taken by UGC on the Reddit 9k nodes) dataset, which has 7x the number of nodes compared to Physics is one-third the time taken by the fastest existing methods on Physics dataset.
Spectral Properties Preservation.
Relative Eigen Error (REE); REE used [14, 15,41 41] gives the means to quantify the measure of the eigen properties of the original graph G that are preserved in coarsened graph Ge.
Definition 4.1 REE is defined as follows: REF(L,, Tee 1/b E |x:- where X and X are top k eigenvalues of original graph Laplacian (L) and coarsened graph Laplacian (Le) matrix, respectively.
2. Hyperbolic error (HE): HE [42] indicates the structural similarity between 9 and Ge with the help of a lifted matrix along with the feature matrix X of the original graph.
II( T-an) x x
II
Definition 4.2 HE is defined as follows: HE- = arccosh( 2trace(X" LX strace X Laax +1) where xdd is the feature matrix of the original input graph, Lun is
is the Laplacian matrix and X E N&x the lifted Laplacian matrix defined in [41] as Tain CL.CCT where C. E R xn is the coarsening matrix and Tee is the Laplacian of 9
Figure 4: Top 100 eigenvalues of the original graph G and coarsened graph Ge at different coarsening ratios: 30%, 50%, and 70%.
Eigenvalue preservation can be seen in Figure 4 where we have plotted the top 100 eigenvalues of G and of ge. We can see that the spectral property preserved even for 70% coarsened graphs. This approximation is more accurate for a lower coarsening ratio, i.e., the smaller the graph, the bigger the REE. The REE for all approaches across all datasets is shown Table for a fixed 50% coarsening ratio. UGC stands out by giving the best REE values in 8 out of 12 datasets. Although we also have coarsened graphs for large datasets like Yelp and Reddit, eigen error calculation for these datasets was out of memory, so have used EOOM while other methods fail to find even the coarsened
7

---

Table 2: This table illustrates Relative Eigen Error 50% coarsening ratio. UGC stands out by giving the best REE values in 8 out of 12 datasets.
Data/Methhd
Corn
Citc.
CS
PubMed
DHLP
Physics
Flickr
Reddit
Yelp
Squirel
Cham.
Cor.
Texas
Film
Noigh.
0.180
0.248
02273
00M
0.637
0.301
Var. Edges
0.129
0.136
0.049
0.965
0.135
0.042
00M
00M
0OM
0.298
0.597
0.485
0.489
21.8
Var. Cli.
0.085
0.064
0.026
1.208
0.082
0.039
00M
00M
00M
0.369
0.456
0.550
0.463
22.95
0.086
Alg. Dist.
0.107
0.111
0.087
0.403
0.047
0.117
0OM
00M
0OM
0,245
0.413
0.552
0.465
5.71
All. GS
0.095
0.057
0.063
0.063
0.073
0.052
00M
00M
0OM
M0M
0.236
0.413
0.569
0.489
5.56
Kron
0.069
0.028
0.056
0.378
0.060
0.064
0OM
00M
OOM
0.246
0.413
0.554
0.491
6.12
(GG((ea.)
0.340
0.179
0.145
0.016
0.014
ROOM
F00M
7.594
0.420
UGC((a+Ad)
0.130
0.070
0.050
0.004
0.004
0.018
0.0153
B0OM
800M
0,546
0.409
0.215
0.204
0.075
107
GCN Accuracy
5 2
$00%
Coarsening Ratio
Coarsening Ratio
Coarsening Ratio
Figure 5: This figure compares graph coarsening methods in terms of REE, HE, and GCN accuracy on the Pubmed dataset.
graph, hence the term OOM. Figure illustrates the trends for eigen error, hyperbolic error and GCN accuracy for different methods as the coarsening ratio is altered.
LSH Similarity and e-Bounded Results The LSH family used in our framework is based on p-stable distributions DD see Appendix A. This ensures that the probability of two nodes going to the same super-node directly related the distance between their features (augmented features F for UGC).
Theorem 4.1 As given in [43], the probability that two nodes v and u will collide and go to a super-node under hash function drawn uniformly at random from a 2-stable distribution is inversely proportional to e 11u-ul and it is represented by p(c) = Prwb [hw = (w))
So L (1) (1-
In our experiments, we empirically validated the Theorem 4.1. We examined the feature distance between any node pair was below a specific threshold, and then using the coarsening matrix C given by UGC, we verified if they shared the same super-node or not. Our evaluation involved counting successful matches, where nodes belonged to the same super-node, and failures, where they did not. We subsequently calculated probability measure based on these counts. Figure 6a and 6b plot this probabilistic function for two datasets, namely Cora and Citeseer distance between two nodes. Re-visiting the Definition 2. for the Cora dataset, we denote our LSH family as H11,3, 3, 1, 0.20). Suppose d denotes the distance between the nodes {u, v). In the notation H(1,3, 1, 0.20), this implies that d < 1, there is a 100% probability that u, v will be grouped into the same noder-node. Conversely, if d 3, the probability of [u, v} being grouped into the same super-node is 20%. Figure 6c plots different values of e at different coarsening ratios. We used Equation 6 for updating the augmented feature matrix F given by UGC and as mentioned, got < similarity guarantees for the coarsened graph. Hence proving Theorem 3.2.
function of
Scalable Training of Graph Neural Networks. Graph neural networks (GNNs), tailored for non- Euclidean data [44-4]] have shown promise in various applications [47, 48]. However, scalability remains challenge. Building on [34], we investigate how graph coarsening approach can enhance GNN scalability for training, bridging the gap between GNNs and efficient processing of large-scale data.
GNN parameter details. We employed a single hidden layer GCN model with standard hyper- parameters values [13] see Appendix H for the node-classification task. Coarsened graph G. used to train the GCN model, and all the predictions are made on test data from the orig- inal graph. The relation between coarsening ratio and accuracy is evident from Table in Appendix H. Specifically, as we progressively coarsen the graph, a slight decrease in aceu- racy values becomes noticeable. Hence, there will always be trade-off when it comes to the
8

---

Posssiit Superr
Epsiton Valuee
Prosess Samme
Coarsening ratio
(a)
(b)
(c)
Figure 6: a) Cora and b) Citeseer demonstrate the inverse relationship between the probability two nodes belonging to the same super-node and the distance between them. c) plots the values ($ 1) for Cora, Citeseer, and CS datasets.
Table 4: This table illustrates the accuracy of GCN model when trained with 50% coarsen graph. UGC demonstrated superior performance compared to existing methods in 7 out of the 9 datasets.
Data/Method
Cora
DBLP
PubMed
Physics
Squirrel
Cham.
Cor.
Texas
Film
Vai.Neigh.
79.75
77.05
77.87
93.74
19.67
20.03
52.49
34.51
15.67
Var.Edges
81.57
79.93
78.34
93.86
20.22
29.95
55.32
30.59
21.8
Var. Var.Clique
80.92
79.15
73.32
92.94
19.54
31.92
58.8
33.92
20.35
Heavy Edge
79.90
77.46
74.66
93.03
20.36
33.3
54.67
29.18
19.16
Alg. Dis.
79.83
74.51
74.59
93.94
19.96
28.81
59.91
18.61
19.23
Aff. GS
80.20
78.15
80.53
93.06
20.00
27.58
54.06
21.18
20.34
Kron
80.71
77.79
74.89
92.26
18.03
29.1
55.02
31.14
17.41
UGC(fea.)
83.92
75.50
85.65
94.70
20.71
29.9
55.6
52.4
22.6
UGC(fea+Ad)
86.30
75.50
84.77
96.12
31.62
48.7
54.7
57.1
25.4
coarsening ratio and quality of the reduced graph. To emphasize the contribution of UGC in terms of both computational time and code-claasification accuracy, we have included Figure 7.
This figure illustrates the improve- ments in computational time and the corresponding changes in accuracy values when compared to the currently best-performing model across various datasets. Table 4 compares the racy among all the approaches with all datasets when they are coarsened down by 50%. UGC demonstrated su- perior performance compared to exist- ing methods in 7 out of the datasets. We have used t-SNE [49] algorithm for visualization of predicted node la- bels shown in Figure 10 Appendix H. It is evident that even with highly coarsened graph training, the GCN model can maintain its accuracy.
x5s Accuracy Ga
X% Accurscy Loss
Computationa gain
Computation computations/ Corn
Accura M8
Figure 7: Computational and accuracy gains of UGC. In the bar plot, dashed bars represent the gain or loss accu- racy when compared to the existing best- rest-performin method, while plain bars indicate the computational gains. All datasets are coarsened down by 50%.
UGC is Model-Agnostic.. While our initial validation utilized GCN to assess the quality of our coarsened graph G. our framework is bound to any specific GNN ar- chitecture. We extended our evaluations to include other prominent graph neural network models. Results from three diverse models, namely GCN [13], GraphSage [40], GIN [50], and GAT [51], have been incorporated into our analysis. All the models were trained using 50% coarsened graph G.. Results from Table demonstrate the robustness and model-agnostic nature of UGC. Refer to Table 7 in
Table 3: This table demonstrates UGC's model-agnostic nature, it doesn't 't rely on any specific GNN model.
Model/Data
Cora
Pubmed
Physics
Squirrel
GraphSage GIN
69.39
85.72
94.49
61.23
67.23
84.12
85.15
44.72
GAT
74.21
84.37
92.60
48.75

---

Appendix H for a comprehensive analysis of node classification accuracy results for various GNN models. We believe this flexibility further enhances the upplicability and utility of our proposed framework in various graph-based applications.
Gained Performance on Heterophilic Graphs. Existing work for GC is focused on homophilic datasets. A notable contribution of our framework is its ability to generalize to all datasets, including heterophilic datasets as well. Building upon the observations made in Table 2 and Table 4 our methods, UGC (feat) and UGC (aug. feat.), showcase notable improvements in both node classification accuracy and REE values when applied to heterophilic datasets. comparison of these results reveals that conventional approaches demonstrate poor code-classificatio accuracy on heterophilic graphs. In contrast, our UGC (features) method achieves substantial accuracy enhancements, surpassing the performance of these traditional approaches. Furthermore, the true potential of our approach becomes evident with augmented features F i.e., UGC (aug. feat.). This approach exhibits remarkable accuracy gains, outperforming all other methods by a considerable margin, signifying the importance of augmented features
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. 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 properties of the original graph. Furthermore, it is worth noting that UGC represents the first work in the domain of graph coarsening for heterophilic datasets. This framework addresses the unique challenges posed by heterophilic graphs and has demonstrated significant increase in node classification accuracy following graph coarsening. 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.
Acknovledgement
Mohit Kataria acknowledges the generous grant received from Google Research India to sponsor his travel to NeurIPS 2024. Additionally, this work is supported by DST INSPIRE faculty grant MI02322G and Yardi-ScAI, IIT Delhi research fund.
References
[1] Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, L. Wang. C. Li, and M. Sun, "Graph neural networks:
A review of methods and applications," ArXiv preprint, 2018
[2] A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur, "Protein interface prediction using graph convolu-
tional networks," Advances in neural information processing systems, vol. 30, 2017.
[3] Y. Wu, D. Lian, Y. Xu, L. Wu, and E. Chen, "Graph convolutional networks with markov random field reasoning for social spammer detection." in Proceedings of the AAAI conference on artificial intelligence, vol. 34, pp. 1054-1061, 2020.
[4] S. Kumar, J. Ying, J. V. de Miranda Cardoso, and D. P. Palomar, "A unified framework for structured graph learning via spectral constraints."" Mach. Learn. Res., vol. 21, no. 22, pp. 1 1-60, 2020.
[5] M. Kataria, A. Khandelwal, R. Das, S. Kumar, and J. Jayadeva, "Linear complexity framework for feature-aware graph coarsening via hashing," in NeurlPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
[6] B. Hendrickson and R. Leland, "A multilevel algorithm for partitioning graphs," " in Proceedings of the 1995 ACM/IEEE Conference on Supercomputing. Supercomputing '95, (New York, NY, USA), p. 28--28 es, Association for Computing Machinery, 1995.
[7] G. Karypis and V. Kumar, "Kumar, v.: A fast and high quality multilevel scheme for partition- ing irregular graphs. siam journal on scientific computing 20(1), 359-392," Siam Journal on Scientific Computing, vol. 20, 01 1999.
10

---

[8] D. Kushmir, M. Galun, and A. Brandt, "Fast multiscale clustering and manifold identification." " Pattern Recognition, vol. 39, no. 10, pp. 1876-1891, 2006. Similarity- -bssd Pattern Recognition.
[9] I. S. Dhillon, Y. Guan, and B. Kulis, "Weighted graph cuts without eigenvectors a multilevel approach," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 11, pp. 1944-1957, 2007.
[10] L. Wang, Y. Xiao, B. Shao, and H. Wang, "How to partition billion-node graph," in 2014 IEEE 30th International Conference on Data Engineering, (Chicago, IL, USA), pp. 568-579, IEEE, 2014.
[11] Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, "Beyond homophily in graph neural networks: Current limitations and effective designs," in Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and Lin, eds.), vol. 33, pp. 7793-7804, Curran Associates, Inc., 2020.
[12] H. Pei, B. Wei, K. C.-C. Chang. Lei, and B. Yang. "Geom-gen: Geometric graph convolutional networks," arXiv preprint 0rXiv:2002.052887, 2020.
[13] T. N. Kipf and M. Welling, "Semi-supperviedd classification with graph convolutional networks," 2016.
[14] M. Kumar, A. Sharma, and S. Kumar, "A unified framework for optimization-based graph coarsening," Journal of Machine Learning Research, vol. 24, no. 118, pp. 1-50, 2023.
[15] A. Loukas, "Graph reduction with spectral and cut guarantees," Journal of Machine Learning Research, vol. 20, no. 116, pp. 1 1-42, 2019.
[16] J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra, "Graph neural networks with heterophily," in Proceedings of the AAAI conference on artificial intelligence, vol. 35, pp. 11168-11176, 2021.
[17] L. Du, X. Shi, Q. Fu, X. Ma, H. Liu, S. Han, and D. Zhang, "Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily." in Proceedings of the ACM Web Conference 2022, pp. 1550-1558 2022.
[18] M. McPherson, L. Smith- and J. M. Cook, "Birds of a feather: Homophily in social networks," Annual review of sociology, no. 1, 2001.
[19] C. R. Shalizi and A. C. Thomas, "Homophily and contagion are generically confounded in observational social network studies," Sociological methods & research, no. 2, 2011.
[20] P. Indyk and R. Motwani, "Approximate nearest neighbors: Towards removing the curse of dimensionalityy" in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Com- puting, STOC '98, (New York, NY, USA), p. 604-613. Association for Computing Machinery, 1998.
[21] B. Kulis and K. Grauman, "Kernelized Docality-sensiteee hashing for scalable image search," in 2009 IEEE 12th international conference on computer vision, (Kyoto, Japan), pp. 2130-2137, IEEE, IEEE, 2009.
[22] Buhler, "Efficient lcrge-scale sequence comparison by locality hashing," Bioinfor- matics, vol. 17, no. 5, pp. 419-428, 428, 2001.
[23] V. Satuluri and Parthasarathy, "Bayesian locality sensitive hashing for fast similarity search." " Proc. VLDB Endow., vol. 5, p. 430-441, jan 2012.
[24] B. Kulis and K. Grauman, "Kernelized Docality-sensitive hashing for scalable image search," in 2009 IEEE 12th international conference on computer vision, pp. 2130-2137, IEEF, 2009.
[25] D. Ravichandran, P. Pantel, and E. Hovy, "Randomized algorithms and nlp: Using locality sensitive hash functions for high speed noun clustering," " in Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'O5), pp. 622-629, 2005.
11

---

[26] O. Chum, J. Philbin, M. Isard, and A. Zisserman, "Scalable near identical image and shot detection." " in Proceedings of the 6th ACM international conference on Image and video retrieval. pp. 1469,5562200 2007.
[27] D. Ron. I. Safro, and A. Brandt, Irelaxation-based coarsening and multiscale graph organiza- tion," 2010.
[28] Chen and I. Safro, "Algebraic distance on graphs," SIAM Scientific Computing, vol. 33, pp.
12 2011.
[29] O. E. Livne and A. Brandt, "Lean algebraic multigrid (lamg): Fast graph laplacian linear solver." 2011.
[30] Dorfler and F. Bullo, "Kron reduction of graphs with applications to electrical networks," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 60, no. 1, pp. 150-163, 2013.
[31] M. Kumar, A. Sharma, S. Saxena, and S. Kumar, "Featured graph coarsening with similarity guarantees," in International Conference on Machine Learning, pp. 17975, PMLR, 2023.
[32] W. Jin, Zhao, S. Zhang, Y. Liu, J. Tang, and N. Shah, "Graph condensation for graph neural networks," 2021.
[33] X. Zheng, M. Zhang, C. Chen, Q. V. H. Nguyen, X. Zhu, and Pan, "Structure-free graph condensation: From large-scale graphs to condensed graph-free data," Advances in Neural Information Processing Systems, vol. 36, 2024.
[34] Z. Huang, S. Zhang, C. Xi, T. Liu, and M. Zhou, "Scaling up graph neural networks via graph coarsening," 2021.
[35] C. Cai, D. Wang, and Y. Wang, "Graph coarsening with neural networks," arXiv preprint 1rXiv:210..01350, 2021.
[36] Z. Yang, W. W. Cohen, and Salakhutdinov, "Revisiting semi-supervised learning with graph embeddings." in Proceedings of the 33nd International Conference on Machine Learning, ICMI. 2016, New York City, NY, USA, June 19-24, 2016, JMLR Workshop and Conference Proceedings, 2016.
[37] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann, "Pitfalls of graph neural network evaluation," " ArXiv preprint, 2018
[38] X. Fu, J. Zhang, Z. Meng, and King, "Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding." in Proceedings of The Web Conference 2020, pp. 2331-2341, 2020.
[39] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna, "Graphsaint: Graph sampling based inductive learning method," arXiv preprint 197.v:190,,04931, 2019.
[40] W. I.. Hamilton, R. Ying, and J. Leskovec, "Inductive representation learning on large graphs." 2017.
[41] A. Loukas and P. Vandergheynst. "Spectrally approximating large graphs with smaller graphs," in Proceedings of the 35th International Conference on Machine Learning (J. Dy and A. Krause, eds.), vol. 80 of Proceedings of Machine Learning Research, (PMLR 80:3237-3246, 2018), pp. 3237-3266, PMLR, 10-15 Jul 2018
[42] G. Bravo Hermsdorff and L. Gunderson, "A unifying framework for spectrum-pressrvingg graph sparsification and coarsening." Advances in Neural Information Processing Systems, vol. 32, 12, 2019.
[43] P. Indyk, "Stable distributions, pseudorandom generators, embeddings, and data stream compu- tation." " Journal of the ACM (JACM), vol. 53, no. 3, pp. 307-323, 2006.
[44] Bruna, W. Zaremba, A. Szlam, and Y. LeCun, "Spectral networks and locally connected networks graphs," 2013.
12

---

[45] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li, "Simple and deep graph convolutional networks," 2020.
[46] M. Defferrard, X. Bresson, and P. Vandergheynst, "Convolutional neural networks on graphs with fast localized spectral filtering." in Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, (Red Hook, NY, USA), p. 3844-3851 Curran Associates Inc., 2016.
[47] C. Li and D. Goldwasser, "Encoding social information with graph convolutional networks forPolitical perspective detection in news media," in Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, (Florence, Italy), pp. 2594-2604, Association for Computational Linguisties, July 2019.
[48] A. Paliwal, F. Gimeno, V. Nair, Y. Li, M. Lubin, P. Kohli, and O. Vinyals, "Reinforced genetic algorithm learning for optimizing computation graphs," 2019.
[49] L. van der Maaten and Hinton, "Visualizing data using t-sne," Journal of Machine Learning Research, vol. 9, no. 86, pp. 2579-2605, 2008.
[50] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How powerful are graph neural networks?," 2018.
[51] Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph attention networks," in 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
[52] M. Datar, N. Immorlica, P. Indyk, and Mirrokni, "Locality-sensitive sensitive hashing scheme based on p-stable distributions," in Proceedings of the twentieth annual symposium on Computational geometry, pp. 253-262,, 2004.
[53] V. Zolatarev, "One-dimensional stable distributions, vol. 65 of" translations mathematical monographs," "," American Mathematical Society. Translation from the original, 1983.
[54] J.M. J. Chambers, Mallows, and B. Stuck, "A method for simulating stable random variables," Journal of the american statistical association, vol. 71, no. 354, pp. 340-344, 1976.
[55] J. Nolan, "An introduction to stable distributions"" in on web, 2005.
13

---

Appendix
A Stable Distribution
A distribution D over R is called p-stable if there exists 2 0 such that for any real numbers e1....y, and ii.d. variables X,....,, with distribution the random variable E; 2y_X, has the same distribution as the variable (2; iy 11))/)//X where X is a random variable with distribution [52]. is known [53] that stable distributions exist for p E (0,2).
Cauchy distribution De, defined by the density function c(x) # 1 1-stable.
=2
Gaussian (normal) distribution Dg, defined by the density function g(x) V2* e is 2-stable.
However, it is known [54] 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 [55] for details). In computer science, they are utilized for "sketching" high-dimensional vectors, demonstrated by Indyk ([43]). The key property of p-stable distributions, mentioned in the definition, enables sketching technique for high-dimensional vectors. This technique involves generating random vector w of dimension d, with each entry independently chosen from p-stable distribution. Given vector v of dimension the dot product dot products, corresponding to different w's, is termed as the sketch of the vector and can be used to estimate ||и||p [43]. However, instead 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 point on the real line, which then split into equal-width segments to represent buckets. two vectors and If you are close, they will have small difference between 1p norms |/e ullp: and they should collide with a high probability
also a random variable. small collection of such
B Algorithm for UGC-FL
Algorithm 2 UGC-FL: Universal Graph Coarsening with feature re-learning
Require: Input G(V, A, X), 1 <- Number of Projectors, r 4- binWidth
1: Go(V A, F), UGC(G,I,)
Ell.,))EE...300 a is heterophily factor, yi E R denotes node labels, E denotes edge
2: a
[E]
list
3: F ((1-a) 1 A} Augmented features
4: F- (C C
5: return F,,
Size of coarsened graph Controlled by Bin-Width C
This section discusses the impact of bin-width on the coarsening ratio see Figure 8. Algorithm outlines the procedure for determining the appropriate bin-width value that corresponds to desired coarsening ratio. The parameter bin-width decides the size of the coarsened graph G... For particular coarsening ratio we find the corresponding by divide and conquer approach on the real axis, which is similar to binary search. Algorithm 3 shows the method by which we find the r for any given R for G.. Figure shows the relation
with R two datasets: a) Cora, and Coauthor CS. It is observed that the R increases as the increases. For each dataset, is hyper-parament that needs to be calculated only once, and hence computational cost not included in the reported time complexity.
14

---

1.0
Coarsening Ratio
0.8
Coarsening Ratio
0.
0.4
0.2
0.000
0.625
0.050
0.075
0.100
0.125
0.150
0.125
0.200
0.000
0.025
0.050
0,075
0.100
0.125
0.150
0.175
0.200
Bin-widths (Core)
Bin-widths (Coeuthar CS)
Figure 8: This figure shows the trend of coarsening ratio as the bin-width increases on two datasets: Cora and Coauthor CS.
Algorithm 3 Bin-width Finder
Require: Input g(V, A, X), L + Number of Projectors, R +- Coarsening Ratio, <- precision of coarsening
Ensure: bin-width h
1: r <- 1, ralio +- 1, < |
2: while R ratiol > do
3: if ralio > then
4:
0.5
5: else
6:
+ 1.5 7: n + UGC(G, L,r); denotes number of supernodes in Ge
8: ratio t (1 n
9:
return r
D Proof of Theorem 4.1
Let ft) denote the probability density function of the absolute value of our stable distribu- tion(Normal distribution), and let = |/ - ullp for two node vectors and r is the bin-width. Since we have random vector w from our stable distribution, v.w u.w distributed as eX where X is random variable from our stable distribution. Therefore our probability function is
1 ( (1
(1- dt
(8) For fixed win-width the probability of collision decreases monotonically with c ||0 u For Definition, 2.1 the hash family will be (r1, 12, P2 )sensitiee where p1 = p(1) and p2 = p(c) for 7a 71
p(c) Prab [ha,(v) ha hu,,(u))
For 2-stable distribution
fx(x)
22/2, Equation 9 will be
V2x
2
(2))
2
1 12)
p(c)
c
dt
(9)
2 0
22 J
=S,(c) S2(c)
Note that (i(c) 1.
S2(c) 2 C I" e (2))
(10)
V2x nn
2
12c
S2(c)
2 dy
(11)
2n
22
Sz(c) =
1 6
(22
(12)
2n
15

---

We have p(1) - that the probability that collides with v is at least (1 A) e Thus the algorithm is correct with the constant probability.
2 2 for some constant A This implies
V2
If 8² then we have
2 2T
p(c) S
(13)
E 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 the same bin decreases, hence we will have more number of super-nodes now. By increasing the bin-width, we can effectively reduce the number of super-nodes. This phenomenon evident when considering the average distance between node pairs various graphs and the corresponding bin-width required to achieve a 30% coarsening ratio. The table below illustrates these findings:
Table 5: Average Distance and Bin-Width for 30% Coarsening
Dataset
Average Distance
Bin- Width
Citeseer 7.748
0.0029
Cora 5,810
0,0021
Dblp 3.168
0,000068
Pubmed
0.540
0.000025
The results in the table clearly demonstrate that as the average distance between nodes increases, the required hin-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 super-nodes and achieve desired coarsening ratios. Figure shows the trend of coarsening ratio when we change bin-width.
System Specifications:
All the experiments conducted for this work were performed on an Intel Xeon W-295 CPU and 64GB of RAM desktop using the Python environment.
G Datasets
Table 6: Summary of the datasets. H.R shows heterophily factor.
Data
Nodes
Edges
Features
Class
H.R(o)
Cora
2,708
5,429
1,433
7
0.19
Citeseer
3,327
9,104
3,703
6
0.26
DBLP
17,716
52,867
1,639
0.18 4
CS
18,333
163,788
6,805
0.20 15
PubMed
19,717
44,338
500
3
0.20
Phy.
34,493
247,962
8,415
5
0.07
Flickr
89,250
899,756
500
7
0.69
Reddit
232,965
114.61M
602
41
0.25
Yelp
716,847
13.95M
300
100
Texas
183
309
1703
5
0.91
Coreell
183
295
1703
5
0.70
Film
7600
33544
931
5
0.78
Squirrel
5201
217073
2089
5
0.78
Chameleon
2277
36101
2325
5
0.75
16

---

H Application of coarsened graph for GNNs
This section contains additional results related to the scalable GNN training. Figure shows the GNN training pipeline. Figure 10 shows the visualization of GCN predicted nodes when training done using the coarsened graph.
We used four GNN models, namely GCN, GraphSage, GIN, and GAT. Table 7 contains node classification accuracy results for across various methodologies employing different GNN models. Table 8 contains parameter details used in UGC across different GNN models. We have used these parameters across all methods.
Table 7: Evaluation of node classification accuracy of different GNN models when trained with 50%
coarsen graph.
Dataset
Model
Var.Neigh
Var.Edges
Var.Clique
Heavy Edge
Alg. Dis.
Atf. GS
Kron
UGC
GCN
20.03
29.95
31.92
33.30
28.81
27.58
29.
48.70)
Chamelcon
GruphSage
20.03
20.02
22.05
23.03
19.88
20.02
27.62
58.86
GIN
20.22
19.53
25.25
19.98
18.20
18.06
21.50
54.92
GAT
22.94
19.33
26.44
21.95
23.72
18.06
21.95
55.58
GCN
19.67
20.22
19.54
20.36
19.96
20.00
18.03
31.62
Squirel
GraphSage
20.00
20.03
20.03
19.93
20.00
19.98
$7.61)
GIN
18.54
19.65
18.98
21.65
19.47
18.29
20.56
35.64
GAT
20.90
18.56
20.68
19.93
20.46
20.05
20.08
32.28
GCN
13.67
21.80
20.35
19.16
19.23
20.34
17.41
25,40
Film
GraphSage
22.32
26.05
24.01
21.49
21.88
21.50
23.73
21.12
GIN
23.51
17.51
21,93
21.12
GAT
17.50
21.73
17.82
21.18
17.94
17.40
24.15
21.71
GCN
77.87
78.34
73,32
74,66
74,59
80.53
74.89
84.77
Pubmed
GraphSage
78.85
62.73
67.18
60.11
63.09
71.25
62.00
83.76
74.77
39.29
46.19
35.97
32.13
49.63
39.29
76.36
GAT
75.22
72.63
74.81
60.04
69.47
59.76
71.92
83.56
GCN
93.74
93,86
92.94
93.03
93,94
93,06
92.26
96.12
Physies
GraphSage
OOM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
OOM
GAT
92.04
91.80
91.48
91.80
92.94
93.33
91.60
93.80
GCN
77.05
79,93
79.15
77.46
74.51
78.15
T7.39
75.50
DBLP
GraphSage
68.54
60.17
74.17
72.70
72.19
71.81
71.76
68.25
33.93
35.12
24.16
$1.47
47.30
42.24
55.28
GAT
70.20
74.07
72.82
71.35
71.17
76.12
72.27
73.49
GCN
79.75
81.57
80.92
79.90
79.83
80.20
80.71
86.30
Cora
GraphSage
70.49
68.48
70.16
69.17
72.26
67.77
73.20
69.39
GIN
47.65
35.03
52.91
34.00
63.05
23.49
48.56
67.23
GAT
74.02
75.92
73.09
73.24
74,21
Oriinal
Graph
9.5
Training network
7AS
GON for Node Classil cation
2A
Figure 9: GCN training pipeline
17

---

(a) Original
(b) 30% coarsen
(c) 50% coarsen
(d) 70% coarsen
Figure 10: Visualization GCN predicted nodes when training is done using the coarsened graph of
Physics dataset.
Table 8: GNN model parameters.
MODEL
HIDDEN LAYERS
LEARNING RATE
DECAY
EPOCH
GCN
[64, 64)
0.003
0.0005
500
GRAPHSAGE
[64, 64)
0.003
0.0005
500
GIN
(64, 64)
0.003
0.0005
500
GAT
(64, 64]
0.003
0.0005
500
Table We report the accuracy of GCN on node classification after coarsening by UGC different
ratios.
Ratio/Data
Cora
DBLP
Pub.
Phy.
30
86.30
75.50
85.65
96.70
50
86.30
75.50
84.77
96.12
70
84.63
74.82
80.57
92.43
We randomly split data in 60%, 20%, 20% for the training-validation-
I Proof of Theorem 3.1
Theorem I.1 Given a Graph G and a coarsened graph Ge they are said to be similar if there exists some 2 O such that:
(1 (|=l) S || S (1 +
(14)
where T. and Lu are the Laplacian matrices of G and G. respectively.
Proof: Let S be defined such that I.= S 5, by Cholesky's decomposition:
||| - || r..1 |||Sa||2 - |SSP++llll < Srx - SP+ Px = || E|| < ||>||
(15)
(16)
The conversion from th norm to 2nd -oor or vice-versa as follows:
|| V W V-I 5T Sx |||||
J Proof of Bounded Theorem 3.2
Theorem J. Given a graph G(L, coarsened graph GL F.), the enhanced features F
obtained by enforcing smoothness condition. The original graph GLL, F) and coarsened graph
Ge( F), are said to be e similar with 0 < 1
(1 <) Fll < |1 < (1+
(17)
18

---

where L and Le are the Laplacian matrices, F and F. are the augmented feature vector given by UGC, F is the relearned enhanced features by enforcing the smoothness condition discussed in Equation 6.
Proof:
Fl || 1 (r(FTIFF) (r((FTT. L.F
(18)
As is positive semi-definite matrix write I. 5T using Cholesky's decomposition and by writing Lt = C we get,
-
(19)
1 ||SPPPP =|| -
(20)
-SF--SPPPPl
(21)
< Se||F11
(22)
Using the new update rule of [| we have Fi, S || we get
<
(23)
|
where < S refer [14] for more details. See Figure 6 which plots different values of at different coarsening ratios. As mentioned for fixed values of got similarity guarantees for the coarsened graph.
K Importance of Augmented Features
See Figure 12 which showcases the importance considering the augmented feature vector. be from the figure that when coarsened using Augmented features super-nodes have more intra-node similarity.
1.4
(F.)
3/5ND
(-7
-0.)
1.3
0.7
0
0.6
0
0.6
0.6
-0.28
0.2
0.52
-0.36
1.5
B
-10
Node Feature of B
B
0.6
0.6
0.04
-0.52
0.4
0.6
(X²)
C
-0.52
0.5
0.3
0.8
0.6
0
0.04
-0.52
0.4 0.6
0.9
-.2
E
0.6
0
0.04
-0.52
0.4
0.6
1.0
Heterophily factor 3/5
1.2
Augmented Feature (A) a
E
.0.6
0.1
Adjacency Feature of A,
Figure 11: A toy example illustrating the computation of augmented features of given graph.
19

---

Festure Motrix
AND Adjacency
Aspccency
Feature Nubix OR Adjacency
2.3
C7
0.1
4.4
0.11
MX1
28
24
08
080
+02
18
18
36
08:
-000
10
2.
32)
Hetemphily
This figure highlights the significance of the augmented vector and showcases coarsening outcomes, specifically when coarsening performed solely using the adjacency or feature matrix compared to when the augmented matrix is taken into account.
Figure 12:
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, all the claims are reflected in paper. See Section 4 and Appendix. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the
paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the
results can be expected to generalize to other settings, is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section (Need efficient implementations and sparse tensor methods to represent the matrix) and Section 5 (Exploration different hash functions and novel applications for the framework).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech- to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't I acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: See Appendix. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referencee..
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors encouraged to provide short proof sketch to provide intuition.
21

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and I Lemmas that the proof relies upon should be properly referenced.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: See Section 4 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make
their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e-g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily architecture clearly and fully.
model architecture, the paper should describe the
(c) If the contribution is be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with open-source dataset instructions for how to construct the dataset).
model (e.g., a large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers have some path to reproducing or verifying the results. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All datasets used are publicly available. See Section and link UGC-NeurIPS
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (tttp:://nips.cc/ppblic
quides/CodeSuuee
sssssnoliicss icy for more details.
While encourage the release of code and data, understand that this might not be possible,
so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce cc/public/ the results. See the NeurIPS code and data submission guidelines (https: c/tii/ g
ssi onPoliccy for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
22

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: See Section 4 and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is
necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report eπror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: See Section and Appendix. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (c.g.. Normally distributed errors). It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [Yes]
Justification: See Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type compute workers CPU or GPU, internal cluster, or cloud
provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethies https: h/tp//inuiipppppe/e cc/ppbbicc/tthiiccuuieelll...
http::/ppppp.//.p.paccaaaaaaaaaa Answer: [Yes]
23

---

Justification:
Research conducted in the paper conform, in every respect, with the NeurIPS Code
of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation
from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also diseuss possible mitigation strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Assets are properly credited and publicly available.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
24

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should
be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's
creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human
subjects.
Including this information the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
25


Reviews:
[{"review_id": "LQcNTwYdcz", "reviewer": "Reviewer_FD1i", "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.", "questions": "See Weaknesses.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: This work proposes to use hashing method to graph coarsening and works well on universal homophilic and heterophilic graphs, which is interesting and rational to me.\n\n\nS2: The overall logic, problem definition, and the solution, are well described and clearly illustrated. The presentation is good and not hard to follow.\n\nS3: UGC is faster compared to existing methods. It achieves a reduction in graph size with lower computational time, making it suitable for large datasets.", "weaknesses": "Here are some questions need to be further addressed:\n\nW1: 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?\n\n\nW2: Some figures, e.g., figure 1 and figure 4, is not very clear for visualization.\n\nW3: 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.\n\nW4: Is there any ablation study to show the effectiveness of the proposed augmented feature vector?\n\nW5: 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.\n\n**Ques 1)** *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*\n\n**Ans 1)**  We thank the reviewer for bringing this typo to our attention.  The augmented feature vector is *calculated by scaling and concatenation operation* instead of *dot product and concatenation*.\n\nThe augmented feature vector of node *$v_i$* is calculated by scaling the adjacency vector *$A_i$* by ($\\alpha$) and feature vector *$X_i$* by *(1 - $\\alpha$)*, followed by the concatenation operations of the two vectors as (1 - $\\alpha$)*$X_i$ || ($\\alpha$) * $A_i$, where $\\alpha$ is the heterophily factor.\n\nA detailed illustration of this process is given in Figure 11 in Appendix K. This figure provides a toy example demonstrating how the augmentation matrix is formulated. It is also mentioned in the main manuscript, specifically on lines 150-151.\n\n**Ques 2)** *Some figures, e.g., figure 1 and figure 4, is not very clear for visualization.*\n\n**Ans 2)** Thank you for bringing this to our attention. We will address this issue by increasing the size of the axis labels in Figure 1 and Figure 4 to enhance their clarity. We appreciate your feedback and will make these adjustments in the updated manuscript.\n\n**Ques 3)**  *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.*\n\n**Ans 3)** We thank the reviewer for the suggestion. We have added the accuracy of GCond in the following table.\n\nGCond accuracy and time\nData | GCond Accuracy | GCond Coarsening Time |GCN training time on original graph|UGC Coarsening Time(x Fast compared to GCond) |UGC accuracy|\n|-------|-------------|---------------|--|---------------|--|\n|Cora|80.43|2640|25.77|0.41(x6440)|86.30|\n|Pubmed|76.98|1620|114.55|1.62(x1000)|84.77|\n|Physics|OOM|-|1195.56|6.4|96.12|\n|DBLP|82.63|25500|174.10|1.86(x13710)|75.50|\n|Squirrel|59.64|7860|228.52|2.14(x3673)|31.62|\n|Chameleon|52.29|7740|54.34|0.49(x15796)|48.7|\n\nAs mentioned in the paper, these methods are computationally demanding, which is also evident from the table above. Specifically, the time required to coarsen the graph exceeds the time needed to train the GNN on the original graphs.\n\nThese results can be included in Table 1 and Table 4 if suggested by the reviewer.\n\n**Ques 4)** *Is there any ablation study to show the effectiveness of the proposed augmented feature vector?*\n\n**Ans 4)** Yes, the ablation study to demonstrate the effectiveness of the proposed augmented feature vector is included in Table 4. In this table, \"UGC feat.\" denotes the scenario where $\\alpha$ is set to zero, meaning only the feature matrix is considered, while \"UGC-feat. + adj.\" denotes the case where $\\alpha$ is set to heterophily factor, thereby incorporating the adjacency vector.\n\nFor heterophilic datasets, node classification accuracy improves significantly when using the augmented feature vector. This highlights the importance of the adjacency vector in the augmented feature vector.\n\n \n**Ques 5)** *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?*\n\n**Ans 5)** We thank the reviewer for bringing this up. We have observed that the heterophily factor can be directly utilized as the $\\alpha$ value. When we extrapolated the results for different $\\alpha$ values, it was observed that setting $\\alpha$ around the heterophily factor yielded the best results.\n\nThe results are shown in the table below for two heterophilic datasets, Squirrel and Chameleon. For both datasets, the heterophily factor is approximately 0.78. We observed that the best results for these datasets are obtained when $\\alpha$ is set around heterophily factor.\n\n\n| $\\alpha$ value | GCN accuracy for Squirrel| GCN accuracy for Chameleon|\n|-------------|---------------|-|\n|0|20.71|29.90|\n|0.1|24.14|38.02|\n|0.2|26.71|42.86|\n|0.3|27.03|43.74|\n|0.4|28.12|41.98|\n|0.5|27.89|40.00|\n|0.6|28.93|47.91|\n|0.7|29.82|**49.49**|\n|0.8|**31.62**|49.45|\n|0.9|29.93|46.59|\n|1.0|28.46|46.15|", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l5TGbrHdFc", "reviewer": "Reviewer_C55f", "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.", "questions": "For Table 4, why only GCN results are shown? I also expected results for GIN GAT and GraphSage.", "limitations": "Limitation is discussed in detail in papers.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The approach is intuitive and easy to understand.\n2. The approach has a lower computational cost than most common method (Var.Neigh. etc,.)", "weaknesses": "For ScalableTrainingof Graph Neural Networks section, there are no detailed discussion on GNN models except GCN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.\n\n**Ques 1)** *For ScalableTrainingof Graph Neural Networks section, there are no detailed discussion on GNN models except GCN.*\n\n**Ans 1)** Due to the limited space of the manuscript, we have only added a discussion about GCN to the manuscript. If the reviewer suggests, the following detailed discussion can be added to the paper:\n\n*GraphSAGE [1] is a scalable inductive framework for generating node embeddings in graphs. It leverages a neighborhood sampling and aggregation approach, allowing it to generalize to unseen nodes. This makes GraphSAGE particularly effective for large-scale graphs where retraining the model for new nodes would be computationally prohibitive. The Graph Isomorphism Network (GIN) [2] takes a different approach, designed to be as powerful as the Weisfeiler-Lehman graph isomorphism test. GIN uses a sum aggregation function, ensuring that different graph structures produce distinct embeddings. This ability to distinguish graph structures makes GIN a robust choice for tasks requiring high discriminative power. Graph Attention Networks (GAT) [3], on the other hand, introduce attention mechanisms to graph neural networks. GATs assign different importance to nodes in a neighborhood, which enhances the model's capability to focus on the most relevant parts of the graph. This attention mechanism allows GATs to achieve state-of-the-art performance on various node classification tasks by effectively capturing the underlying structure of the graph.*\n\n[1] Hamilton, Will, Zhitao Ying, and Jure Leskovec. \"Inductive representation learning on large graphs.\" Advances in neural information processing systems 30 (2017).\n\n[2] Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2018). How powerful are graph neural networks?. arXiv preprint arXiv:1810.00826.\n\n[3] Veličković, Petar, et al. \"Graph attention networks.\" arXiv preprint arXiv:1710.10903 (2017).\n\n**Ques 2)** *For Table 4, why only GCN results are shown? I also expected results for GIN GAT and GraphSage.*\n\n**Ans 2)** Due to space limitations in the manuscript, we included only GCN results in the main manuscript. However, we had already conducted experiments with GraphSage, GIN, and GAT for two homophilic and two heterophilic datasets, as shown in Table 3, to demonstrate the model-agnostic behavior of UGC.\n\nAs suggested by the reviewer, we have now conducted experiments using GIN, GAT, and GraphSage models for Table 4. These results further demonstrate that UGC is not restricted to any specific model.\n\n| Dataset | Model | Var.Neigh | Var.Edges | Var.Clique | Heavy Edge | Alg. Dis. | Aff. GS | Kron | UGC |\n|-|-|-|-|-|-|-|-|-|-|\n||||||||||||\n|    | gcn | 20.03 | 29.95 | 31.92 | 33.3 | 28.81 |27.58| 29.10| **48.7** |\n| Cham. | graphSage | 20.03| 20.02 | 22.05 | 23.03|19.88  |20.02| 27.62|**58.86** |\n| | gin |20.22 | 19.53| 25.25 |19.98  | 18.20   |   18.06 |  21.50 | **54.92** |\n| | gat |22.94|19.33 |26.44| 21.95 |23.72 | 18.06  | 21.95 | **55.58** |\n||||||||||||\n|           | gcn | 19.67 | 20.22 | 19.54 | 20.36 | 19.96 |20.00|18.03 |**31.62** |\n| Squ. | graphSage | 19.87| 20.00 | 20.03 | 20.03 | 19.93  |20.00|19.98 |**57.60** |\n| | gin |18.54 | 19.65 | 18.98 | 21.65 |19.47 | 18.29   |20.56   | **35.64** |\n| | gat |20.90| 18.56|20.68| 19.93 |20.46 | 20.05  | 20.08 |**32.28**  |\n||||||||||||\n|    | gcn | 15.67 | 21.80 |20.35  |19.16 |19.23| 20.34|17.41 | **25.40** |\n| Film | graphSage |22.32|26.05  |24.01 |21.49 | 21.88 |21.50|**23.73** |21.12 |\n| | gin |**24.20** |23.51  |17.51  |11.49  | 13.90|21.93 |18.04   |21.12 |\n| | gat |17.50|21.73 |17.82| 21.18 |17.94 | 17.40  |**24.15**  |21.71 |\n||||||||||||||\n|    | gcn | 77.87 | 78.34 |73.32  | 74.66 | 74.59 |80.53|74.89 |**84.77**|\n| pubmed | graphSage |78.85 | 62.73 |67.18 |60.11 |63.09  |71.25|62.00 |**83.76** |\n| | gin |74.77 | 39.29 | 46.19 |35.97  | 32.13  | 49.63 | 39.29  | **76.36** |\n| | gat |75.22|72.63 | 74.81|60.04  |69.47| 59.76  | 71.92 |**83.56** |\n||||||||||||\n|    | gcn |93.74  |93.86|92.94|93.03|93.94|93.06|92.26 |**96.12** |\n| physics | graphSage |OOM |OOM|OOM |OOM |OOM|OOM|OOM |OOM |\n| | gin |OOM |OOM |OOM  |OOM  |OOM |OOM|OOM| OOM |\n| | gat |92.04|91.80|91.48 | 91.80 | 92.94 |  93.33 | 91.60 | **93.80**  |\n||||||||||||\n|    | gcn | 77.05 | **79.93** | 79.15 |77.46 | 74.51 |78.15|77.79 | 75.50  |\n| dblp | graphSage |68.54 |60.17  |**74.17** |72.70 | 72.19 |71.81| 71.76| 68.25 |\n| | gin |35.84 |33.93  |35.12  | 24.16 |  51.47  |  47.30  | 42.24  |**55.28**|\n| | gat |70.20|**74.07** |72.82| 71.35 | 71.17| 76.12  | 72.27 |73.49|\n||||||||||||\n|    | gcn | 79.75 | 81.57 |80.92  |79.90 |79.83  |80.20|80.71 |**86.30** |\n| cora | graphSage |70.49 | 68.48 |70.16 |69.17 | 72.26 |67.77|**73.20** | 69.39 |\n| | gin |47.65 | 35.03 | 52.91 |34.00  |  63.05  | 23.49  | 48.56  | **67.23**  |\n| | gat |69.26|74.02 |**75.92**| 68.95 |73.09 | 73.83  |73.24 | 74.21 |\n||||||||||||\n\nIf the reviewer suggests, we can include these additional results in the Appendix and refer to them in the caption of Table 4 as follows:\n\nTable 4: This table illustrates the accuracy of the GCN model when trained with a 50% coarsened graph. UGC demonstrated superior performance compared to existing methods in 7 out of the 9 datasets. Please refer to Appendix H for results with GraphSage, GIN, and GAT models.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V2Bp2BAJ2e", "reviewer": "Reviewer_mriD", "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.", "questions": "Please see the weakness section.", "limitations": "The authors have adequately addressed the limitation of the potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Derive the coarsening matrix over graphs with heterophily property is an interesting idea, and Locality Sensitive Hashing (LSH) technique significantly reduces the algorithm's complexity.\n* UGC offers significant speed improvements and is capable of handling both homogeneous and heterogeneous graphs.\n* The experiments has demonstrated UGC’s limitations and possibility to improve the effectiveness across datasets.\n* The paper is also very clear with thorough experiments and analysis.", "weaknesses": "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?\n2. The paper lacks a detailed description of the experimental setup, including software and hardware environments, as well as the parameters used for different algorithms.\n3. 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?\n4. 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?\n5. 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?\n6. Minor issues：\n    * In Figure 2, the specific meanings of a, b, and c are not labeled in the diagram.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.\n\n**Ques 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?*\n\n**Ans 1)** The memory space overhead by UGC arises from two steps\n\na) Random sampling of *$l \\in R^d$* different projectors,\n\nb) Storing the hash values of each of 'n' nodes across these *l* projectors. \n\nHence, the additional space complexity is bounded by O(l\\*d + n\\*l). *l* is a hyperparameter, for all our experiments, and all datasets, we have used 3000 different projectors(*l*). It is worth noting that for some datasets, the value of *l* can be as low as 1000.\n\nAdditionally, due to its construction, UGC is suitable for online or streaming data as it does not require the entire feature matrix to be present simultaneously. In scenarios with limited memory space, the feature matrix can be split into different chunks, and UGC can be applied to each chunk separately, ensuring that the same memory is reused for all chunks. In this case, the required additional space complexity is bounded by O(l\\*d + n'\\*l) where n' is the size of the chunk and it can vary from 1 to n.\n\n**Ques 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.*\n\n**Ans 2)** The details are included in the Appendix due to limited space in the main manuscript. For convenience, we also provide the details here:\n\nAppendix H contains a detailed discussion about the experimental setup as mentioned in Line 301. Figure 9 provides an overview of the GCN training pipeline, while Table 7 includes information on the hyper-parameters used for training.\n\nAppendix F contains details about the hardware specifications.\n\n\"All experiments conducted for this work were performed on a desktop with an Intel Xeon W-295 CPU and 64GB of RAM using the Python environment.\"\n\n**Ques 3) and Ques4)** \n* *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?*\n\n* *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?*\n\n**Ans 3) and Ans4)** In Figure 5, lower coarsening ratios indicate that the graph is significantly reduced. We observe that the RRE error for UGC is optimal when the graph is reduced by approximately 0-65%. For HE error, we acknowledge that UGC is not the best-performing algorithm, but it is comparable to existing methods. However, for the node classification task, we can see that UGC gives the best results. How these properties are related to downstream tasks is not well understood yet and warrants further investigation.\n\nWe have noticed the monotonic relationship that the reviewer mentioned but at the moment we are trying to analyze the data from additional experiments so that we can make an objective statement after a thorough assessment.\n\n\n**Ques 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?*\n\n**Ans 5)** \n\nWe have added the results of 3WL-GNN methods. It is to be noted that originally 3WL-GNN was a graph classification method, we have made the necessary changes to adapt it to node classification task. \n\n\nData\\Model | Var.Neigh | Var.Edges | Var.Clique | Heavy Edge | Alg. Dis. | Aff. GS | Kron | UGC | Full Dataset |\n|-|-|-|-|-|-|-|-|-|-|\n|Cora|**57.55**|43.30|53.12|60.31|60.01|52.93|56.75|55.32|63.45|\n|DBLP|48.60|49.83|51.76|51.95|51.74|52.13|52.19|**53.10**|61.58|\n|Physics|85.99|84.83|87.02|83.49|82.12|85.89|87.88|**88.56**|92.87|\n|Pubmed|69.94|64.29|70.42|63.11|53.55|27.04|62.30|**84.15**|86.68|\n|Squirrel|19.83|19.28|19.71|20.03|20.86|20.04|20.82|**61.92**|31.73|\n|Film|17.13|26.10|10.93|22.72|26.33|**27.16**|18.31|24.82|31.64|\n|Chameleon|18.40|22.59|20.03|23.78|23.04|16.63|23.24|**69.01**|44.61|\n\nIn 5 out of 7 datasets UGC gives the best results for 3WL-GNN.\n\n**Ques 6)** *In Figure 2, the specific meanings of a, b, and c are not labeled in the diagram.*\n\n**Ans 6)** We thank the reviewer for pointing it out, Given the opportunity, we will improve the diagram to avoid any confusion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wHfj6UxIiV", "reviewer": "Reviewer_QBq8", "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.", "questions": "-\tLine 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.\n-\tLine 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.\n-\tLine 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.\n-\tLine 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’.\n-\tLine 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.\n-\tAgain, 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.\n-\tWhat 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.\n-\tLine 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.\n-\tWhere is the introduction of baselines from `Var.Neigh.’ to ` Kron’? If somewhere else, I suggest moving to Chap experiments.\n-\tFigure 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": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "-\tThis paper is one of the pioneering works exploring graph coarsening in heterophilic graph datasets.\n-\tAggregating hypernodes through a hash function instead of neighbors is a promising solution to perform heterophilic graph coarsening.", "weaknesses": "-\tThe presentation of this paper is unclear. Check out `Questions’.\n-\tThe current formulation of the proposed `Hash functions’ is ambiguous and biased. Check out `Questions’.\n-\tSome claims were in fact wrong. Check out `Questions’.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.\n\n**Ques 1)** Regarding .. *Line 4. vital insights’ *\n\n**Ans 1)**  We thank the reviewer for the suggestion.  By *vital insights* and *vital information*, we mean retaining 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. Given the opportunity, we can integrate these clarifications into the manuscript.\n\n**Ques 2)** Regarding *Line 67-68. The Graph Coarsening(GC) problem ..*\n\n**Ans 2)** The Graph Coarsening (GC) problem is indeed about learning a coarsening matrix. This definition is well-established in the literature [1, Section 2], [2, Section 2.2]. The objective and problem formulation are also discussed in Section 2.\n\n[1] Hashemi, Mohammad, et al. \"A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation.\" arXiv preprint arXiv:2402.03358 (2024).\n\n[2] Kumar, Manoj, et al. \"Featured graph coarsening with similarity guarantees.\" International Conference on Machine Learning. PMLR, 2023.\n\n**Ques 3)** Regarding *Line 128-129. Due to this, these methods ....*\n\n**Ans 3)** We thank the reviewer for the suggestion. The main reason behind this statement was the following results, where we compared the coarsening time using GCond with the whole graph training time. As it can be seen from the table, the time it takes to coarsen the graph is multiple times higher than the training time. However, the above-mentioned statement can be rephrased as : \n\n*...these methods are extremely computationally demanding and may not be suitable for the scalability of GNN models. However, these methods can be beneficial for other tasks, like solving storage and visualization issues.*\n\nGCond accuracy and time\nData | GCond Acc | GCond Coarsen Time |GCN training time on original graph|UGC Coarsening Time(x Fast compared to GCond) |\n|--|--|--|--|--|\n|Cora|80.43|2640|25.77|0.41(x6440)|\n|Pubmed|76.98|1620|114.55|1.62(x1000)|\n|Physics|OOM|-|1195.56|6.4|\n|DBLP|82.63|25500|174.10|1.86(x13710)|\n|Squirrel|59.64|7860|228.52|2.14(x3673)|\n|Chameleon|52.29|7740|54.34|0.49(x15796)|\n\n**Ques 4)** Regarding *Line 143-144.The concepts of homophily and heterophily .....*\n\n**Ans 4)** We understand the statement mentioned can be misleading and therefore we have corrected the line to the following:\n\n *The concepts of homophily and heterophily in graphs are primarily concerned with whether the edges between two nodes align with their respective labels.*\n\n**Ques 5)** Regarding.. *Line 155-160. The current formulation hash function ... Consider this example that a graph has 1 node whose degree is 999 and......*\n\n**Ans 5)** We appreciate your concern. To clarify, in the example cited by the reviewer, the node with a degree of 999 will indeed produce a higher hash value and will be collapsed into a super-node. This is reasonable because it is an important node and should be assigned to a different super-node. It is important to note that we ensure no super-node is empty during the formulation of the super-nodes. If there is no hash value between the range of 11-89, we will not create a super-node for this range. For the other nodes with a degree of 1, as these nodes are connected to the same high-degree node, the distinction between the hash values will be governed by their node feature vectors. The super-node index is determined by setting the appropriate bin-width value \"r\".\n\n**Ques 6)** Regarding.. *Again, concat the adj with node feature is ambiguous...*\n\n**Ans 6)** We appreciate your concern. To clarify, the order of the nodes is fixed and consistent across all *l* projectors at the start of the coarsening and does not change during the process. Once the node order is established, the LSH framework's locality-preserving property ensures that the hashing process remains stable.\n\n**Ques 7)** Regarding. *What is ‘|||’ in the proof of Theorem 3.1 in l......*\n\n**Ans 7)** We thank the reviewer for pointing out the typo. $||.||_p$ denotes $p^{th}$ norm. We have corrected the Proof of Theorem 3.1 here is the revised version:\n\n**Proof:** Let S be defined such that L = $S^TS$, by  Cholesky’s decomposition:\n\n\n$| \\lVert x\\rVert_{L} - \\lVert x_c\\rVert_{L_c} | = | \\lVert Sx\\rVert_{2} - \\lVert SP^+Px\\rVert_{2}| $\n\nFrom Modulus inequality property,\n\n\\begin{gather}\n    \\leq ||Sx - SP^+Px||_2 = ||x - \\widetilde{x}||_L \\leq ||x||_L\n\\end{gather}\n\nThe conversion from $L-norm$ to $2^{nd}-norm$ or vice-versa is as follows:\n\n $\\lVert x\\lVert_L = \\sqrt{x^T L x} = \\sqrt{x^T S^T S x} = \\lVert Sx\\lVert_2$\n\n**Ques 8)** Regarding.  *Line 180-181. \"It means that the adjacency matrix A~ has a substantially smaller number of non-zero elements .....*\n\n**Ans 8)** As mentioned in the Line 177 coarsened graph, adjacency ($A_c$) is directly calculated from *$C^T A C$*. In general, $A_c$ has a substantially smaller number of non-zero elements than A. However, such extreme cases may exist where the number of edges remains the same and we will make a mention of such cases in the text if given an opportunity.\n\n**Ques 9)** Regarding *Where is the introduction of baselines .....*\n\n**Ans 9)** Section 2 includes the introduction to baseline(line 111-122)\n\n* UGC: Universal Graph Coarsening, our proposed method\n* VAN: Variation Neighborhood\n* VAE: Variation Edge\n* VC:  Variation Clique\n* HE:  Heavy Edge\n* aJC: Algebraic Distance\n* aGS: Affinity\n* Kron: Kron\n\n**Ques 10)** Regarding *Figure 7 is confusing. Present actual time saved’.....*\n\n**Ans 10)** The reason this figure is being presented is because the downstream tasks take substantially longer time as compared to the coarsening time in our case, whereas it is not true for the other methods. Adding a large number (downstream time) to a smaller one (coarsening time) could diminish the emphasis on coarsening, which is the focus of this work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their insights and constructive suggestions. A comprehensive point-by-point response to the reviewers' comments is presented below. The major additional changes are listed below.

**Additional experiments**: We have incorporated all of the additional experiments requested by the reviewers spanning

* Adding the GCond node classification accuracies and computational time in the rebuttal.
* Extending Table 4 results to include GraphSage, GIN, and GAT models.
* Conducting experiments with varying values of the $\alpha$ hyperparameter from [0,1] to justify the UGC design for handling heterophily datasets.
* Including node classification experiments with the 3WL-GNNs model.

We hope these revisions will satisfactorily address the concerns raised by the reviewers and elevate the overall quality of our work.

Meta-review: 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.
Decision: Accept (poster)