Spectral Graph Coarsening Using Inner Product Preservation and the Grassmann Manifold
Authors: Ido Cohen
Ronen Talmon
Venue: NeurIPS 2025 poster ()
Keywords: Graph coarsening
Grassmann manifold
Graph signals
Spectral methods
Primary area: general_machine_learning
TL;DR: A novel graph coarsening method that focuses on preserving the inner products between node features and demonstrates superior performance on graph coarsening benchmarks.

Abstract: We propose a novel functorial graph coarsening method that preserves inner products between node features, a property often overlooked by existing approaches focusing primarily on structural fidelity.
By treating node features as functions on the graph and preserving their inner products, our method retains both structural and feature relationships, facilitating substantial benefits for downstream tasks. 
To formalize this, we introduce the Inner Product Error (IPE), which quantifies how the inner products between node features are preserved. 
Leveraging the underlying geometry of the problem on the Grassmann manifold, we formulate an optimization objective that minimizes the IPE, also for unseen smooth functions. We show that minimizing the IPE improves standard coarsening metrics, and illustrate our method’s properties through visual examples that highlight its clustering ability. Empirical results on benchmarks for graph coarsening and node classification show that our approach outperforms existing state-of-the-art methods.

Spectral Graph Coarsening Using Inner Product Preservation and the Grassmann Manifold
Ido Cohen
Ronen Talmon
Electrical and Computer Engineering Technion-Israee Institute of Technology sidoc&campus technion. ac
Electrical and Computer Engineering Technion-Israe Institute Technology ronen@ee. technion, ac
Abstract
We propose novel functorial graph coarsening method that preserves inner prod- ucts between node features, a property often overlooked by existing approaches focusing primarily on structural fidelity. By treating node features as functions on the graph and preserving their inner products, our method retains both structural and feature relationships, facilitating substantial benefits for downstream tasks. To formalize this, we introduce the Inner Product Error (IPE), which quantifies how the inner products between node features are preserved. Leveraging the underlying geometry the problem on the Grassmann manifold, we formulate an optimiza- tion objective that minimizes the IPE, also for unseen smooth funetions. We show that minimizing the IPE improves standard coarsening metrics, and illustrate our method's properties through visual examples that highlight its clustering ability. Empirical results on benchmarks for graph coarsening and node classification show that approach outperforms existing state-of-the-ard methods.
Introduction
Graph-structured data has become ubiquitous a wide range of domains, including social net- works [1) biological systems (2). and recommendation systems (3) due its ability model complex relationships and interactions. With the exponential increase data availability, the size of graphs in many applications has also grown significantly. This surge in graph size presents major challenges, as traditional and even advanced graph processing techniques often become computa- tionally infeasible excessively time-consuming when applied large-scale graphs. To address these issues, graph reduction techniques are developed with the aim of simplifying large graphs while retaining key structural features, thereby enhancing computational efficiency. There are three main strategies for graph reduction graph sparsification, graph condensation, and graph coarsening.
Graph sparsification 5 reduces graph size by selectively removing edges and nodes while maintaining overall structural properties. However, there a limit to how much graph can be sparsified without compromising its integrity. Graph condensation methods 7 g aim reduce graph size by generating smaller, synthetic graph that replicates the performance of the original graph specific tasks, such as training Graph Neural Network (GNN), Although condensation significantly lowers computational costs, it may not retain a clear structural interpretation. making difficult understand how or why certain nodes or edges are represented in the reduced version.
In contrast, graph coarsening [9] a traditional approach that reduces graph size by grouping similar nodes into super-nodes, aiming to approximate the original structure. These methods typically seek to preserve key structural properties such as spectral characteristics [10], connectivity [11], and Most existing coarsening methods focus primarily structure and often overlook node features, which play a critical role in many graph learning tasks. These methods typically operate solely on the graph topology, neglecting the rich information encoded in the node
community structure 212 [
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

features. Recently, the Featured Graph Coarsening (FGC) method was proposed to address this limitation by incorporating node features into the coarsening process [4. FGC emphasizes the reconstruction of the node features after coarsening and promotes smoothness in the coarsened graph as part of its optimization objective. However, since FGC focuses on preserving the individual characteristics of the node features, it does not fully exploit their mutual relationships, which may encode valuable information.
In this work, we propose new approach to graph coarsening from a functorial perspective. We treat node features as functions, or signals, defined on the graph, focusing on preserving the relationships between these functions by maintaining their inner products during coarsening. Our method intro- duces a new coarsening metric, the Inner Product Error (IPE), which measures how the inner products between graph signals are preserved. We postulate that minimizing IPE ensures that the coarsened graph retains structural consistency and node feature relationships crucial for graph learning tasks. We exploit the geometry of the problem by recognizing that both the coarsening operator and the matrix spanning the node features (under a smoothness assumption) can be viewed as points on the Grassmann manifold. Leveraging the properties of the Grassmann manifold, we extend IPE minimization beyond observed node features, enabling our method to generalize to unseen features that satisfy the smoothness assumption. This approach is formulated as optimization problem, and we compute the coarsening operator using gradient descent. Additionally, we theoretically show that minimizing our proposed approach leads to improvements in common graph coarsening metrics.
To demonstrate the effectiveness of our method, we present visual and empirical results showing that, while our method focuses on the functional relationships between node features, it also captures the global structure of the graph. We validate its performance through extensive experiments on multiple graph coarsening and node classification benchmarks, where our method consistently outperforms state-of-the-ar coarsening methods, demonstrating its practical utility.
Background
Grassman manifold The set of n x k matrices whose columns orthonormal vectors forms Riemannian manifold called the Stiefel manifold [15] defined by,
St(n,, k) == {U U" = [xxa].
(I)
where I lxc is a rank-k identity matrix. The Grassmann manifold Gr(n, k) is a quotient manifold representing the set of k-dimensional subspaces of the Euclidean space RT. Two points on the Stiefel manifold that span the same subspace represent the same point on the Grassmann manifold [66] 17 In general, a point on Gr(n, k) is represented by an equivalence class
[U] = (UO: O E (OK)),
(2)
where U E St(n,k), k), and SO(k) are all A x k rotation matrices (also known the special or- thogonal group), such that any O E SO(k) satisfies 00 O Ixck- The principal angles between two subspaces U, and U2 are the angles that measure the smallest angular sep- aration between basis vectors in one subspace and basis vectors in the other subspace. We de- note them by 0 [0(1), ((2) "0......te 0((0). Given two subspaces Un and U2 the Grassmann manifold Gr(n, k)), the cosine of the principal angles between them can be computed using the SVD decomposition of U²
AOB", where the singular values on the diagonal of θ are (o0)( cos cos ()(+)))
The geodesic similarity the Grassmann manifold is defined using the principal angles between subspaces [17]. The authors in [18] showed that this geodesic similarity can be computed by,
Gr Σ cos? (B(9) -t(UU)(UUUU)
Graph coarsening A graph with node features is denoted by the quadruplet g = (V,E, W.X). where is a set of vertices, E is set of edges, W E R a weighted adjacency matrix, and X E Ruxp is node features matrix such that each row specifies the values of the p features for each node. Each node feature, represented as a column of X, can also be considered as graph signal IR", assigning real value to each vertex, namely, V + R. The graph Laplacian matrix L is

---

defined by -= D W. where D = diag W is the diagonal degree matrix. We define the inner product between two graph signals z, y E R with respect to the graph g by:
(a, g) = x² Ly Σ wiy (x)(<(() x (())((())) y(i)),
(GJ)ER
where wi are edge weights, and 2+1), 7(1) are the values of the features at node i. Since L is a positive semi-definite matrix, x: Læ induces a semi-norm and defines an inner product on the subspace of I orthogonal the constant vector as discussed in Von Luxburg [9]] We denote the graph Laplacian eigen decomposition by L U UUT where the columns of U are the eigenvectors of L, and A is diagonal matrix consisting of its corresponding eigenvalues.
Given graph G (V,E, W. X) with nodes, the goal of graph coarsening is to construct coarsened graph G. = (Ve. Eo, W c: Xx) with k < n nodes, while preserving the main structural properties of G, thereby simplifying subsequent analysis and computations. The coarsening procedure defined through a linear mapping π : V + Ve that maps nodes in 9 to nodes in Ge, termed 'super- nodes'. This linear mapping is defined by the coarsening matrix P E R*x". such that X. = PX. Each non-zero entry of P indicates mapping from node in G to super-node in Ge. i... if and only if the j-th node g is mapped to the i-th super-node of Ge. then Pi.j > 0. Let L E RR=x and Le E R** be the respective Laplacian matrices of & and Gc, and let L E R=** and X E R=*p be the lifted Laplacian and feature matrices, i.e., the reconstructed full graph matrices after the coarsening procedure. The relationships between the coarse graph Laplacian and features and the original graph Laplacian and features 20
= = LC,
X. = PX
(5)
LPPP-PP
X CX.
(6)
where C' E BR is the pseudo-inverse of P, i.e. C The non-zero entries of C also imply node mapping from G to Gc. such that Cij > 0 the i-th node of g is mapped to the j-th super-node of Go. We note that the matrix C belongs the following set:
C (C 2 ( Czz)= =0 Vi * j.
(C.,, d,, |C, 2 1,
where C.,; is the i-th orthogonal column of C, C.,; is the i-th row of C, ( is the standard inner product, and d; is some positive number. Since the columns of a valid coarsening matrix C are orthogonal, it can also be viewed as a point the Grassmann manifold Gr(n, k:).
Numerous evaluation metrics exist for graph coarsening, each assessing how well specific graph properties are preserved during reduction. Next, we review the main ones.
Definition 2.1 (Relative Eigen Error (REE (10) The REE defined as REE + Acas where X; and deς are the k dominant eigenvalues of the original graph Laplacian matrix L annd the coarsened graph Laplacian matrix L., respectively.
Definition 2.2 (Reconstruction Error (RE) (21)) The RE between the original graph Laplacian L and the lifted graph Laplacian L₁ is defined by RE | L.
The REE and RE are coarsening metrics independent of the graphs' node features. The REE measures the spectral similarity between graphs and how global properties such as important edges are preserved, while the RE quantifies how local information is preserved during coarsening.
Definition 2.3 (Hyperbolic Error (HE) (22) The HE between the original Laplacian matrix L and
lifted Laplacian matrix Lı is defined as HE arccosh (1+ 2X X L'XX) node features matrix of the original graph.
L,) If IX II
where X is the
Definition 2.4 (Dirichlet Energy Error (DEE)) The Dirichlet Energy (DE) of a graph is defined by DE = ir( tr(X LX), where L denotes the graph Laplacian and X denotes the node feature matrix of the graph (23). We define the DEE between the original graph G and its coarsened version Ge as DEg DEE = log DFC.
where DEg and DEg, are the DE of the original and coarsened graphs.
The HE and DEE are coarsening measures that consider the node features. The HE measures distortion in the geometric structure of the data in hyperbolic space. This is useful when the graph
3

---

has hierarchical structure (e.g., trees), as hyperbolic spaces are suited for representing such data. The DE measures the smoothness of the node features on graph; lower DE values suggest that the node features are closely aligned with the graph structure. Consequently, we define the DEE which quantifies the extent to which the intrinsic graph structure in the node features preserved during the coarsening process. We note that the authors in Kumar et al. [14] suggest minimizing the DE of the coarsened graph as part of their graph coarsening optimization objective.
3 Proposed method
Our method adopts a functorial perspective for graph coarsening, focusing on maintaining the relationships between different functions defined on the graph. Specifically, aims to preserve the inner products between functions defined on the graph. To achieve this, we first introduce the following new graph coarsening metric that quantifies how the inner products between given graph signals (i.c., node features) are preserved during the coarsening process.
Definition 3.1 (Inner Product Error (IPE)) Let L and X be the original graph Laplacian and node features matrix, and let Le and X, be their respective coarsened graph Laplacian and features matrix. The Inner Product Error (IPE) is defined by IPE || LX L.
The motivation for this approach is based on the following:
Proposition 3.2 Let L and Lc be the graph Laplacians of a graph G and its coarsened graph Ge- respectively. for all pairs of graph signals x, y E I2,, the inner product between the two signals preserved under the coarsening process, iee.:
x. Ly = = L.Yes
then the graph Laplacian of the original graph, L, can be fully reconstructed from Le via:
L, P L.P
See App. A. for proof. Prop. 3.2 shows that preserving inner products of graph signals maintains key structural properties, enabling graph reconstruction. We note that a necessary condition for the assumption in Proposition 3.2 to hold that rank [)) k. which implies that the graph has least n k connected components, a condition that is rarely met in practice. Yet, we show in Sec. 4 that our approach achieves the lowest reconstruction error (RE) among baselines, even when this criterion is violated, demonstrating its broad applicability. In Sec. 3.1] we provide analytical evidence that minimizing IPE leads the minimization of other coarsening metrics well.
Preserving inner products using the Grassmann manifold. We propose an optimization approach for graph coarsening preserve inner products between graph signals. The objective function and constraints are given by:
min f(C)((())))))))( = X LX - - (+)( +g(C)) ah(L.) C
(8)
s.t. L- CC =C'x L.=.'IC...--x...05
where C' E paak is the coarsening operator: L E Raxn and X E R2 are the given graph Laplacian and feature matrix of the original graph; U is matrix containing the k leading eigenvectors of L; L E k and X E R are the Laplacian and feature matrix of the coarsened graph, and C is the set defined in Zp. The function Gr(,,) is the Grassmann similarity score defined in 33, and functions h((-) and g(.) are regularization functions for L. and C, while X, > are positive regularization parameters.
The objective in (8) minimize the IPE using two complementary terms. The first involves directly minimizing the IPE on the given node features. Although this improves performance on the available data, does not generalize well to new signals, as its effectiveness depends heavily on the specific information encoded in the feature matrix X. The second term aims to maximize the Grassmann similarity (3) between the coarsening matrix C' and the leading eigenvectors (+()) of L. Sec. 3.1 we show analytically that this alignment promotes IPE minimization for general unseen smooth signals, e.g., satisfying smoothness assumption (Prop. 3.4), and preserves important structural properties (Prop. 3.5). The parameter 3 balances the two terms, adjusting the emphasis between performance on the observed data and generalization to new signals. Our empirical results show that both terms contribute to the coarsening process.

---

Proposed algorithms. One limitation of the objective in (8) is that the derivative of the first term does not have a closed-form expression with respect to C. As a remedy. we adopt the multi-block optimization framework suggested by Kumar et al. [4] recasting our objective function as:
min = LX -X- -C
(9)
+ +X|10" - a
s.t. CI CEC
where the terms involving Grassmann similarity and L. written explicitly. We adopt the same regularization functions as in Kumar et al. [14), which promote balanced super-node assignment and
(C,yl) is an bbase group penalty that, as shown in [24] [14], encourages valid coarsening operators. The second regularization term is lz) = log det L. + J), where J = R This term ensures that 1, which guarantees that the coarsened graph Ge is
connectivity in the coarsened graph. The function g(C) = ||c' 11; Σi= |E)=|Ct,g]
Le J is full rank, implying rank (Le)
connected 25 26
In this recast, the derivative of the modified objective function has closed-form expression with respect to C, and the gradient is presented in App. AA.4 We optimize this objective by applying projected gradient descent [27] to estimate the matrix C. Specifically, applying ordinary gradient descent steps could deviate from the feasible set C on the Grassmann manifold. Therefore, we use projected gradient descent to periodically project C' back onto the Grassmann manifold after fixed number of gradient descent steps using the operator Hardmax (C). Hardmax (C) applies a hard maximum at each row of C, ensuring column-wise orthogonality, which coincides with the structural constraints of the Grassmann manifold.
A full description of this method is in Algorithm| 1 termed INGC. In Algorithm 2. we present another version, where we omit the first term in (9). In this case, we denote the algorithm' 's objective function by J(C). This version focuses on minimizing the IPE via Grassmann similarity, removes dependence on the feature matrix X, and enables estimating C using standard gradient descent. We refer to this algorithm as We note that, for SINGC, we empirically observed that projecting only once at the end of the optimization yields performance similar to using intermediate projections, done for INGC. Therefore, for simplicity and efficiency, we chose to apply standard gradient descent throughout the iterations and perform the projection using Hardmax C)) only at the end.
Algorithm INGC Algorithm
Algorithm 2 SINGC Algorithm
Input: L E Raxn X E RRXP
Input: L E Raxn
Parameters:
3, X, a, 7. titers Citer
Parameters: X, a, 7, titer
Output:
Le E Rk
X. Rexp
Output:
Le E IR
1: Compute (k).
1: Compute U(k)
2: Initialize Co. 0.
2: Initialize Co,
3: while ||Cr+1 Ctllr <, Ec < liter do
3: while ||Cr+1 C.IlF 60 or < late do
4: C+(o)= =C,-
5: Compute Vcf(Xe, e, C) (see (66)
4: Compute Vcf(C) (see 17
6: for i in range(Guerr) do
7:
Update Cr+1 using the gradient
5: Update C.+1 using the gradient descent
descent step:
step:
C((141) <- -C V/Vc c(t); C(a)
C++1 + C, -.-nvef(..)
8:
end for
9:
C++1 = Hardmax Cz (((eee)))
6: t=t+1
X x((++1)= C,,1, 1=1+1
11: end while
7: end while
Hardmax(C)
8: Hardmax(C)
13: return L. = C. LC, X. =
9: return L, C, LC
5

---

3.1
Theoretical analysis
Next, we present two key analytical results. First, we show that the second term in ( minimizes the IPE for general smooth graph signals. Second, we connect this minimization and common graph coarsening metrics, such as DEE and REE. We begin by defining smooth graph signal. Dong et al. 28 model a smooth graph signal generation mechanism as:
a - + G,
(10)
where L
TAUT is the Laplacian of the respective graph signal, h (N) E R", ~ N(0,Inxx) E IR", and En > 0 is the noise standard deviation. This model suggests that smooth graph signal combination of the first eigenvectors of L and scaled noise.
Assumption 3.3 (k-smooth graph signal (29]) A graph signal æ E IK" is termed "k-smooth" on the graph 9 if it can be fully expressed by the first eigenvectors of its corresponding Laplacian L, i.e. x Σ c = c(U where the columns of U [w ,..,,,............. [h] E gaxk are the k k-leading eigenvectors of L.
Table in App.
shows the extent to which this assumption holds in real datasets. Based on the following result provides motivation incorporate the Grassmann similarity
Assumption 3.3
score Gr(C, (()) defined in (3) into our proposed objective.
Proposition 3.4 Let X be a feature matrix of graph G with Laplacian matrix L, where each column of X is k-smooth on the graph G. Then, any mapping L. = CLC X = C. X, such
that C (kk) O satisfies:
where the columns of ( E - are the k-leading eigenvectors of L, and O E SO(k).
See App. A.2 for proof. Proposition 3.4 1.4mmplies that any coarsening operator C' whose columns span the same subspace as U (k) minimizes the IPE in 3.1 for any k-smooth signals on the original graph.
Thus, the second term in our objective (8) maximizes the Grassmann similarity (3) between C and (k), aiming find valid coarsening operator (i.e., C C) that satisfies C (k)
Next, we present a theorem that provides bounds on the DEE (Def. 2.4p and REE (Def. 2.1 as functions of c, which quantifies the deviation of the second term in objective from its optimal value (if C and (4) span the same subspace, then tr(T)()) (U(K))T TC Proposition 3.5 Lei L be the Laplacian of a connected graph 9, and let ( ing is k-leading eigenvectors. Suppose L. = -C LC is the Laplacian of a coarsened graph derived using a coarsening operator C such that tr(U(() (
k).
(k) be the matrix contain-
k e, and the constant vector in Thn is spanned by the columns of C. Then, the eigenvalues of the original graphs {X)}= and the coarsened graph {Xe)= satisfy,
1xO <A
1
S 1
en) H4 (Xx))((()A((11)
10
25i5k
F1
and the Dirichlet energies of a k-smooth graph signal æ on the graph, the inequalities:
(1 (x=ex)?(<=l111 Sllxoolle. s (1 ex)
(2) whenever eR X0i Here R
AmalL)
X() Amax L)) the maximum eigenvalue of L.P C², Pi.Pa
and the first and i eigenvalues of the matrix PPT,
||~|| = x Læ |xelle, = L.L.e.
See App for proof. Prop. 3.5 shows that the bounds for both REE (Def. 2.1 and DEE (Def. 2.4 become tighter decreases. Combining Prop. 3.4 and 3.5 implies that minimizing the IPE for general smooth signals reduces both the REE and DEE graph coarsening metrics.
Complexity. Our approach formulates coarsening an optimization problem, so its applicability depends on both computational complexity and convergence time. In App. C we compare the complexity of our methods with FGC [14), optimization-bart coarsening approach considered

---

FGC
LVE
LVN
SINGC
INGC
FGC
1.36
1VF
2.65
UVN
3.57
SINGC
3.70
INGC
3.78
Ideal
3,86
Grassmann Similarity GrIC, U_K0
Figure 1: Node assignments of all methods on a synthetic graph generated from an SBM. Nodes with the same color belong the same class (super-node). The bar plot on the right shows the Grassmann similarity between each method's coarsening matrix C' and the leading four eigenvectors ((k) of the graph Laplacian. The bottom bar shows the similarity for the ideal partitioning -ie., between the
block-model-braee -ased C' and U (k), The maximum similarity in this case is 4.
state-of-the-an on many benchmarks, which has been shown to accelerate GNNs training time. We show that our methods are similarly efficient while achieving better results. Moreover, show that applying coarsening before GCN particularly advantageous for dense graphs with significantly more edges than nodes. Runtime comparisons supporting this claim are presented in App. C Finally, App. D provides convergence plots illustrating the trade-off between speed and final objective value.
4 Experimental results
Visual illustration. A key aspect of graph coarsening is how well the global graph's 's structure is preserved. This can be assessed by how effectively the partitioning into super-nodes captures To illustrate this property, we provide a visual example showing how the super-nodes generated by our method align with the graph's global structure. This example highlights how our approach maintains meaningful graph representation, despite focusing solely on functional relationships.
The example is based synthetic graph generated using Stochastic Block Model (SBM) (30
with four classes, each containing 10 vertices (N 40), an intra-class probability of 0.9, and an inter-class probability of q 0.05. The feature matrix X is generated following the same graph signal generation mechanism described in (TO). We set the target coarsened graph for all coarsening methods have A = 4 super-nodes. In Figure 1 we present the results obtained by our methods (INGC/SINGC), alongside three other graph coarsening baselines: Feature- based Graph Coarsening (FGC) [14, which incorporates node features into the coarsening process, and the Local Variation Neighborhood (LVN) and Local Variation Edges (LVE) methods [10). which use the original graph Laplacian eigenvectors as part of their coarsening objectives. We observe that the super-nodes assignment of our methods closely aligns with the partitioning of the nodes to four classes according the SBM, indicated by the node colors in Figure On the right-hand side of Figure we present bar plot comparing the Grassmann similarity between the coarsening matrices C' (which encode the vertex partitioning) produced by each method and the top four eigenvectors the original graph Laplacian, (k), The bottom bar represents the matrix C that encodes the ideal partition based on the baseline. We observe that method achieves the highest similarity, closely approaching the ideal partitioning. Note that when the coarsening matrix
underlying block model of the graph, serving
C' and the eigenvector matrix (k) span the same subspace, the Grassmann similarity reaches its maximum of 4. This comparison highlights our motivation for incorporating Grassmann similarity into our coarsening objective, as it preserves the graph's 's global structure. Numerically, this property reflected in the REE metrie; we present an extensive evaluation of this and other metrics in the following section. For more visual comparisons, see App.B

---

Table 1: Comparison of coarsening methods four datasets using multiple metrics and coarsening
ratios (r)) For each method, we report REE, RE, HE, DEE, and INP on each dataset. Best results are in bold; second-best underlined. The last two columns count how often each method achieved the best or second-best performance.
Method
Karate Club
Les Miserables
Cora
Citeseer
#Best #2 Best
0.7
0.5
0.3
0.7
0.5
0.3
0.7
0.5
0.3
0.7
0.5
0.3
REF
0.30
1.52
3.15
0.36
1.39
7.82
0.57
1.31
4.23
0.68
1.58
4.11
3
RE
9.71
9.87
10.31
11.42
11.91
11.91
11.42
11.62
11.70
10.85
11.05
11.14
0
LVN
HE
1.74
1.89
2.25
1.92
2.60
2.54
1.89
2.50
3.17
1.93
2.52
3.43
0
DER 36.2
47.8
46.6
65.1
99.4
90.2
39.1
70.7
90.2
40.0
66.3
111.1
0
0.71
0.72
2.02
2.56
1.91
2.87
2.23
1.73
0.93
0.98
1.09
0
REE 0.82
0.48
2.26
1.05
4.56
7.60
0.81
1.94
5.14
0.79
1.62
4.26
3
RE 9.39
9.91
9.97
11.55
12.14
12.48
10.62
11.51
11.69
10.52
11.02
11.14
0
LVE
HE 1.40
1.93
2.16
2.89
1.29
2.31
3.10
1.61
2.50
3.40
DEE 17.3
19.1
20.6
63.6
22.5
44.9
78.1
30.1
63.5
109.0
0
IPE 0.66
0.88
0.92
1.59
2.77
3.87
0.58
1.19
1.54
0.61
0.79
0.88
0
REE 1.35
3.94
7.54
3.08
10.31
33.18
1.78
5.40
15.99
1.58
8.92
35.88
0
RE 8.70
8.81
9.26
9.97
9.98
10.91
9.70
10.82
10.76
10.47
10.23
10.31
0
FGC
HE 1.03
1.23
1.80
0.82
0.87
1.58
0.76
1.40
1.56
1.89
1.39
1.61
0
DER 8.05
11.57
21.36
4.78
7.65
9.74
0.20
0.41
5.01
19.5
7.87
1.34
0
IPE 0.55
0.58
0.94
1.05
2.17
3.67
0.41
1.01
3.67
1.10
0.49
0.68
0
REE 0.78
1.30
2.97
0.08
1.30
10.40
0.86
0.84
0.76
0.71
0.62
0.42
6
INGC (Ours)
RE 6.27
7.00
8.28
5.43
8.08
9.79
9.49
10.17
10.42
8.86
9.85
10.10
9
HE 0.29
0.45
1.00
0.08
0.33
0.83
0.67
1.04
1.37
0.64
1.21
1.61
9
DEE
0.01
0.03
0.02
0.04
0.02
0.10
0.03
0.40
3.12
0.02
0.66
1.01
11
0.19
0.31
0.48
0.30
0.57
0.86
0.31
0.43
0.68
0.24
0.34
0.58
8
REE 0.86
1.78
0.50
2.32
7.78
0.86
0.84
5.10
0.83
0.62
0.42
3
SINGC (Ours)
RE 6.09
8.05
8.74
9.07
9.60
10.49
9.54
10.17
10.95
9.32
9.76
9.92
4
HE 0.27
0.85
1.46
0.51
0.72
1.29
0.69
1.04
1.84
0.83
1.14
1.27
4
DER 0.02
0.51
6.56
0.47
0.35
0.10
0.03
0.40
8.12
1.01
1.45
0.10
4
IPE 0.19
0.43
0.59
0.21
0.63
1.07
0.31
0.43
0.69
0.27
0.25
0.47
6
Graph coarsening metrics. Here, we evaluate the performance of our methods on several bench- mark datasets using the coarsening metrics from Sec. 2 We compare them with current SOTA coarsening methods LVN and LVE-which are known to perform best aruuctuaal-rrsserver metrics (e.g.. REE, RE), and FGC, which is considered the leading method for metrics that also consider the features of the nodes. We conduct experiments on four datasets: The Karate Club 3I), Les Miserables 32). (3ra and Citeseer (34]. Note that the Cora and Citeseer datasets include node features, whereas the Karate Club and Les Miserables datasets do not. For the latter two, generated node features using the signal generation mechanism presented in Section 3.1
Table I summarizes the performance of our methods (INGC and SINGC) and the baselines (FGC, LVN and LVE) across different datasets and coarsening ratios (r k = 0.7, 0.5, and 0.3). The best performance for each metric is highlighted in bold, and the second-bess last two columns summarize the number of settings in which each method achieved the lowest or second-lowest score compared to others. We observe that INGC achieves the best overall performance across all graph metrics. SINGC, more efficient variant, is also highly competitive -ofteofeen ranking second and occasionally achieving the best results. Bascline methods (LVN, LVE, and FGC) show mixed performance. LVN and LVE perform well on REE for some datasets, indicating good spectral preservation, but generally underperform on metrics involving node features. FGC, the only baseline that incorporates node features in coarsening, outperforms the others related metrics. However, both our methods consistently surpass FGC. The strong RE score of our approach demonstrates its broader ability to preserve graph structure, even beyond the theoretical setting of Theorem 3.2 the datasets used are connected or have far fewer than n connected components.
underlined. The
The hyperparameters in these experiments were selected via grid search, a standard approach in graph coarsening when aiming to minimize a specific metrie. The best results for each metric were obtained using different hyperparameters, reported in App. G.3 This variability highlights the
8

---

Table 2: Node classification accuracy across datasets and coarsening ratios (r). Best results
bolded; second- best are underlined. The last two rows count best and second-best -est results per method.
Dataset
GCOND
SCAL(IV)
FGC
MGC
INGC (Ours)
SINGC (Ours)
0.3
81.56
0.00
79.42 1.71
85.19 + 0.24
84.56 1.40
87.55 0.16
84.51 0.33
Cora
0.1
81.37
0.40
71.38 t 3.62
81.46 +: 0.79
76.02 + 0.93
83.38 0.47
82.76 + 0.32
0.05
79.93
= 0.44
55.32 + 7.03
80.01 = 0.51
77.42 0.78
77.81 = 0.08
0.3
72.43 1 0.94
68.87 1: 1.37
74.64 1.37
74,60 1: 1.20
76.89 1: 0.23
76.66 = 0.27
Citeseer
0.1
70.46
0.47
71.38 + 3.62
73.36 + 0.53
70.37 # 1.25
72.63 + 0.25
69.71 = 0.72
0.05
64.03
2.40
55.32 + 7.03
71.02 = 0.96
66.02 0.32
66.37 = 0.57
0.05
93.05
0.26
73.00 1 7.41
94.27 1: 0.25
94.52 0.19
94.29 0.10
94.04 1 0.06
Co-phy
0.03
92.81
0.31
63.65 + 9.65
94.02 + 0.20
93.64 0.25
94.20
0.13
93.52 0.13
0.01
92.79
0.40
31.08 +: 2.65
93.08 1: 0.22
93.95 0.20
93:20 0.10
0.05
78.16 = 0.30
72.82 + 2.62
80.73 + 0.44
81.89 + 0.01
83.59 + 0.22
83.55 0.32
Pubmed
0.03
78.04 + 0.47
70.24 + 2.63
79.91 + 0.30
80.70 + 0.01
81.93 + 0.22
83.19 + 0.18
0.01
77.20 0.20
54.49 + 10.5
78.42 + 0.43
79.09 0.26
79.96 + 0.34
0.05
86,29 0.63
34.45 = 10.0
89.60 = 0.39
90.84 0.12
90.92 + 0.22
Co-CS
0.03
86.32
26.
9.29
88.29 1 0.79
89,59 0.38
89.99 1 0.41
0.01
0.02 84.01
14.42 + 8.50
86.37 + 1.36
87.93 0.33
83.39 0.33
#Best
0
3
1
#2-Best
1
1
need to tune hyperparameters based the specific application and the most relevant coarsening metric. For example, minimizing REE may be crucial for clustering, while tasks like graph pooling and node classification whhch-hhchhhhh rely heavily node INP during tuning. App. presentss a hyperparameter study showing each parameter's 's contribution and sensitivity across metrics.
from prioritizing DEE and
Node classification. Next, we evaluate our method on node classification using several benchmark datasets. This task assesses how well coarsened graphs preserve structural and feature information for accurate label prediction 4 Following Kumar et al. [14), we train a Graph Neural Network (GNN) on the coarsened graph and predict node labels for the original graph, reducing training time due to fewer nodes and edges. Specifically, we: (1) generate a coarsened graph using a selected method; (2) compute super-node labels via Ve C'y: (3) train GNN on the coarsened graph; and (4) evaluate predictions ý GNN X) against the original labels y. Note that this task used solely for evaluation, with all labels y available throughout
We replicated the experimental settings from Kumar al. [14] and Huang et al. 133 both of which employ a Graph Convolutional Network (GCN) [6). We then compared the performance of our methods (INGC and SINGC) with the top-performing methods in those papers that considered to be SOTA, namely SCAL (55, Featured Graph Coarsening (FGC) [14), Graph Condensation (GCOND) 77. and Multi-Component Coarsening (MGC) (37). The datasets include two medium- sized graphs (Cora and Citeseer) and three large-scale graphs (Co-Physics, Pubmed, and Co-CS). Each method's effectiveness was evaluated using 10-fold validation. A detailed description of the experimental setup is in App. G.2
The results reported in Table with mean accuracy and standard deviation across the folds for each method at different coarsening ratios r. We observe that INGC outperforms the SOTA methods on large datasets (Co-Physics, Pubmed, and Co-CS), and matches their performance sized datasets. SINGC outperforms baseline methods in most settings, despite having a simpler optimization objective. A key takeaway from the results is that the integration of node features into the coarsening process gives FGC, INGC and SINGC a competitive advantage over methods that primarily focus on structural properties, such as SCAL and GCOND, was also indicated in (14). This relationship is intuitive, as node classification relies not only on structural relationships but also on the meaningful preservation of node features.
medium-
App. Fressenns an ablation study on 8, highlighting the role of the Grassmann similarity term. App. E discusses Assumption 3.3] evaluates its validity on real datasets, and shows our method remains effective even when it is not fully met. Moreover, our empirical results indicate that SINGC benefits when larger fraction of signal energy resides in the low-frequency band, and its best performance reported on PubMed, where this assumption is most valid.
The source code for all experiments is available at: Code

---

Conclusion
In this paper, we introduced a new graph coarsening method that focuses on preserving the inner products of graph signals during the coarsening process. We demonstrated that, although primarily considering node features, our approach also maintains the global structure of the graph. Our methods, INGC and SINGC, outperform state-of-the-an art techniques across various graph coarsening metrics and tasks (e.g.. node classification), showcasing their versatility and effectiveness in preserving essential graph properties. These results highlight the potential of our approach for graph-based learning applications. However, similar to other optimization-ban method faces scalability limitations when applied to extremely large graphs. This challenge may be addressed practical scenarios by partitioning the graph into manageable subgraphs, processing each subgraph independently, potentially in parallel, and subsequently reconnecting them (38), A critical assumption underlying our work is that the node features exhibit smoothness with respect to the graph topology, an attribute closely related to homophily. Consequently, our evaluation is restricted to homophilic graphs. For future research, an extension to heterophilic datasets could involve adapting the second term in objective facilitate alignment with alternative frequency bands. For example, the low-fread frequency basis ( may be replaced with different basis representing mid or high frequencies, guided by prior knowledge of label-frequency alignment. Future directions also include integrating our coarsening into graph pooling and evaluating impact on improving GNN performance.
coarsening techniques, our
Acknowledgments
We thank the anonymous reviewers for their insightful feedback. This work was supported by the European Union's 's Horizon 2020 research and innovation programme under grant agreement No. 802735-ERC-DIFFOP.
References
[1] Stanley Wasserman and Katherine Faust. Social network analysis: Methods and applications. 1994.
[2] Georgios A Pavlopoulos, Maria Secrier, Charalampos N Moschopoulos, Theodoros G Soldatos, Sophia Kossida, Jan Aerts, Reinhard Schneider, and Pantelis G Bagos. Using graph theory to analyze biological networks. BioData mining, 4:1-27, 2011.
[3] Maarten Van Steen. Graph theory and complex networks. An introduction, 144(1), 2010.
[4] Mohammad Hashemi, Shengbo Gong, Juntong Ni, Wenqi Fan, B Aditya Prakash, and Wei Jin. A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation. arXiv preprint 24XX::22002033338 2024.
[5] Joshua D Batson, Daniel A Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers, In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 255-262, 2009.
[6] Ryan Wickman, Xiaofci Zhang, and Weizi Li. A generic graph sparsification framework using deep reinforcement learning. 2022 IEEE International Conference on Data Mining (ICDM), pages 1221-1226 IEEE, 2022.
[7] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. arXiv preprint I 2021.
[8] Yang Liu, Deyu Bo, and Chuan Shi. Graph condensation via eigenbasis matching. arXiv preprint arXiv:2310.09202. 2023.
[9] Jie Chen, Yousef Saad, and Zechen Zhang. Graph coarsening: from scientific computing to machine learning. SeMA Journal, 79(1):187-223, 2022.
[10] Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In International conference machine learning, pages 3237-3246. PMLR, 2018.
10

---

[11] Kristen LeFevre and Evimaria Terzi. Grass: Graph structure summarization. In Proceedings of the 2010 SIAM International Conference on Data Mining, pages 454 465. SIAM, 2010.
[12] Yuanyuan Tian, Richard A Hankins, and Jignesh M Patel. Efficient aggregation for graph sum- marization. In Proceedings the 2008 ACM SIGMOD international conference Management of data, pages 567-580, 2008.
[13] Sorour E Amiri, Bijaya Adhikari, Aditya Bharadwaj, and B Aditya Prakash. Netgist: Learning to generate task-based network summaries. In 2018 IEEE International Conference on Data Mining (ICDM), pages 857-862. IEEE, 2018.
[14] Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Sandeep Kumar. Featured graph coarsening with similarity guarantees. In International Conference on Machine Learning, pages 17953-17975. PMLR, 2023.
[15] Ioan Mackenzie James. The topology of Stiefel manifolds, volume 24. Cambridge University Press, 1976.
[16] Thomas Bendokat, Ralf Zimmermann, and P-A Absil. A grassmann manifold handbook: Basic geometry and computational aspects. arXiv preprint arXiv:2011.13699 2020.
[17] Alan Edelman, Tomás A Arias, and Steven T Smith. The geometry of algorithms with or- thogonality constraints. SIAM journal on Matrix Analysis and Applications, 20(2):03-353,, 1998.
[18] Ido Cohen and Ronen Talmon. Functorial comparison of graph signals using the geodesic distance on the grassmann manifold. arXiv preprint arXiv:2406.06600 06989, 2024.
[19] Ulrike Von Luxburg. A tutorial spectral clustering. Statistics and computing, 17:395-416. 2007.
[20] Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research, 20(116):1-42, 2019.
[21] Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra, Graph summarization methods and applications: A survey. ACM computing surveys (CSUR), 51(3):1-34, 2018
[22] Gecia Bravo Hermsdorff and Lee Gunderson. unifying framework for spectrum-preserving graph sparsification and coarsening. Advances in Neural Information Processing Systems, 32, 2019.
[23] Vassilis Kalofolias and Nathanaël Perraudin. Large scale graph learning from smooth signals. arXiv preprint 170.00550 2017.
[24] Di Ming, Chris Ding, and Feiping Nie. A probabilistic derivation of lasso and 112-norm feature selections. Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4586-4593 2019.
[25] Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
[26] Vassilis Kalofolias. How to learn graph from smooth signals. In Artificial intelligence and statistics, pages 920-929. PMLR, 2016.
[27] Dimitri Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48 (3):334-334, 1997.
[28] Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, 64 (23):6160-6177) 6173, 2016.
[29] Felix Dietrich, Or Yair, Rotem Mulayoff, Ronen Talmon, and loannis G Kevrekidis. Spectral discovery jointly smooth features for multimodal data. SIAM Journal on Mathematies of Data Science, 4(1):410-430, 2022.

---

[30] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-6)) 1511644666631,,,, 2017.
[31 Wayne W Zachary, An information flow model for conflict and fission small groups. Journal of anthropological research, 33(4):452-473, 1977.
[32] Donald Ervin Knuth. The Stanford GraphBase: a platform for combinatorial computing. volume 1. AcM Press New York, 1993.
[33] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163,
2000.
[34] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. Proceedings of the third ACM conference on Digital libraries, pages 89-98, 1998.
[35] Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neural networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 675 675-684, 2021.
[36] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: (6f.:02079029 2016.
[37] Subhanu Halder, Manoj Kumar, and Sandeep Kumar. Multi-component coarsened graph learning for scaling graph machine learning. In Companion Proceedings of the ACM on Web Conference 2025, pages 1001-1004, 2025.
[38] George Karypis and Vipin Kumar. fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, (0(1):359-392 1998.
[39] Daniel Spielman. Spectral and algebraic graph theory. Yale lecture notes, draft of December, 4: 47, 2019.
[40] Anil K Jain and Richard C Dubes. Algorithms for clustering data. Prentice-Hale Inc., 1988.
[41] Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability: view from function space. Advances in Neural Information Processing Systems, 34:17749-
17761, 2021.
[42] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5)8808-825 828, 2018
12

---

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]
The abstract and introduction accurately summarize main contributions: graph coarsening method that preserves inner products of node features, maintaining both structural and feature fidelity. In Section 3.1, support analytical claims, explicitly stating that they hold for signals satisfying a smoothness assumption, as noted in the abstract. The practical advantages of our approach are demonstrated empirically in Section 4.
Justification:
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 or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We address the limitation of formulating coarsening as optimization prob- lem, including discussion of its runtime and convergence trade-offs, and the conditions under which it is beneficial (Sec. 3.1 and D). We also conduct hyperparameter study (Sec. 4 and F) to highlight sensitivity and tuning importance. Additionally, we evaluate the practical validity of our main smoothness assumption across datasets (App. and discuss the implications when it only partially satisfied.
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 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-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect 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 low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant 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 of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper presents multiple theoretical results, with all assumptions clearly stated in the text and formalized within the propositions. All results that are built on prior work are explicitly referenced. Complete proofs for all propositions provided in the 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- referenced.
All assumptions should be clearly stated or referenced 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 are encouraged provide short proof sketch to provide intuition.
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 Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper provides all the necessary details reproduce the main results. Algorithms 1 and outlines the full optimization procedure, and Appendix[G specifies all experimental settings, including dataset descriptions, evaluation metries, and the exact hyperparameters used for each experiment.
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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how 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 submis- sions 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) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
14

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Due time constraints, we were unable to prepare the code for inclusion the supplementary material. However, we plan to release the full source code upon acceptance. All experiments were conducted on publicly available datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttpccccpppppppp...e.eeee.eo.ctt weriii/gguies//OeC /ooeeSusmm ssiinni ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Appendix G provides all experimental settings, including dataset descriptions, evaluation metrics, and the exact hyperparameters used for each experiment.
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, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
15

---

Answer: [Yes]
Justification: We use standard deviation to indicate the spread of results across folds. Table reports mean accuracy and standard deviation computed over 10-fold valsidaaliotionn for the node classification task.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 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 to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix G provides details on the computing environment, including hard- ware specifications. Appendix C presents a runtime analysis conducted on the specified hardware.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of 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).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics Ettiih/ttttsss//rrrppppp.ppppppp http://wwwp.....ppooo/aaaaaaaaaa
Answer: [Yes]
Justification:
The research conducted in this paper adheres the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
16

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The proposed method has no societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimesss considerations (e.g., deploymeet 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 particular applications, let alone deployments. However, if there is 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 to generate deepfakes for disinformation. On the other hand, it is not needed to point that a 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
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)?
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 a 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 (c.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]
17

---

We ensure proper attribution to the original papers and owners of all external data, code, and models utilized in this work.
Justification:
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 dataset.
The authors should state which version of the asset used and, 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 /daaaset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The documentation our source code will be provided alongside the code, upon acceptance.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing 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 crowdsoureing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as 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.
Institutional review board (IRB) approvals or equivalent for research with human subjects
18

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on 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 to 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 applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy hattsss/meerrpps.cc//oofeeerrree for what should or should not be described.
19

---

A Appendix Theorems' proofs
A.1 Proof of Proposition 3.2
[Proof of Proposition 3.2 Given a graph 9 with graph Laplacian L and its coarsened graph G. with graph Laplacian L. C² LC, and assume that for any graph signals æ, y RR" the following condition is satisfied:
Ly x. Ley.
(11)
We plug in the the definitions of Ie = Px and y. = Py in and obtain:
x Ly =x LaYle
= =(ax) Py
= =x P L.
x =xLLi Liy.
(12)
where in the last equality we plug-in the definition of the lifted Laplacian (reconstructed Laplacian) L, p" L.P.
Assuming 12 holds for every pair of signals x, y E R", one can choose specific signals such that [[i,j] L i. for all i = 1,....,,,, n, allowing to conclude:
L
This implics that the full Laplacian can be fully reconstructed for Le.
A.2 Proof of Proposition 3.4
[Proof Proposition 3.4 Let x. E R" be two k-smooth signals on the graph 9 with graph
Laplacian L. Define x - x, Yo = C y E TRk and let L = C' LC, where C = (T(k) O, and O E O is some k-dimension rotation matrix. Then, the following relation holds:
x T Ly x. Lay. = x Ly ((C x) C LCC y
) O) LU LU OO x T Ly x (v)) 00 (U(())) O0 (Ur(K))
Ly ((U T x)
x Ly U (1lh) LU (V)
= x Ly x Ly
where the third equality holds because is a rotation matrix satisfying 00 Ixck The fifth equality holds because æ and are k-smooth and satisfy x = (+)) (Ur())) x and y = (ra) (0))))
Thus, for any matrix X whose columns k-smooth signals, have:
X LX x L.X 0.
A.3 Proof of Proposition 3.5
The proof of Proposition 3.5 relies on the following definition and lemma.
Definition A.1 (Restricted spectral approximation [10] Let R be a k-dimensional subspace of R", Matrices L. and L are (R, e) -s-miilaar if there exists an 6 > O such that
ærllı. S e||æ:||r, for all a E R
where C.
20

---

Lemma A.2 Let L be the Laplacian matrix of a connected graph G, and let U be the matrix containing its k-leading eigenvectors. Suppose Le C LC is the Laplacian matrix of a coarsened graph derived using a coarsening operator C with normalized columns such that
= =
Then, the matrices L and Le are (R, ck)-similar where &. )ar(L) and R = span(U >2(L))
[Proof of Lemma A.2 We the projection matrix defined by C II CC Given the trace condition (r(U((k)
TTT))))))))))))))))) = k e, we can express as:
tr (U( Icc = tr((U((M)) (l) = k c.
From this, immediately obtain:
((((U(k))T(L (I =c.
(13)
This follows from the fact that:
= = (((()) IIxa (I(((U(() (8)) ()U + (n((()()) T (I-IC)
where the first equality holds because (k) is orthonormal matrix.
Next, express the term || z. Since the columns of C are orthogonal, we æ;
CP2 CC CC æ, and obtain:
| xille
(x CC x) L(x-CCT x) = ((I-CC' )x)) L(I - CC )a.
(14)
Using the Rayleigh quotient [39 we can bound by:
- 21112 = ((I - CC CC L( L (1-1CCT CC
Amax (I) )013
(15)
Next, we proceed to bound the term ||(I CC )= (k) z. Therefore, we get:
Since æ spanned by (k),, we write
[[(T -C- Jan T CC (1)
From 13). we know that the maximum eigenvalue (T((K)TTII (U) is bounded by c. Thus, by applying the Rayleigh quotient, obtain:
[I -C cCTTcl
c||2||3 <||== ||
Substituting this bound into
15 we have:
| wille edmax (Z)
21

---

Since L is the graph Laplacian of a connected graph, it has only one zero eigenvalue, corresponding
the constant vector. Assuming æ not constant vector, we can bound x [ using the Rayleigh quotient:
|
|
(L
Substituting this into the previous inequality, obtain:
x æille S Amuix L
||a|| [L
ex||œ||z.
(2)
where Amn (L) is the condition number of L. [2]
Finally, if x: is constant vector, then since the columns of C' span the constant vector, we have:
x æellz ||
CC æ||z = 0.
Thus, for all æ E (A)) we conclude that:
| æille I cx||=]|Le
ie L and Le (R, EK) similar.
Then, according to Theorem 13 and Corollary 12 20), the full graph Laplacian L and the coarsen graph Laplacian are L. are (Ur()) exx)-similar, they satisfy the following inequalities:
(1 - [x][|<]| L I ||0| L. I (1 + ex)||2011
(1 + ex)²
X
1
2
P2 (ex)2()(0/103))
H1
according Proposition
3.5 where
Anco (L) and μi 224 and the first and & eigenvalues of the Ax(L)
matrix PPT.
Figure 2: Clustering of the Karate Club network using (a) SINGC method and (b) conventional k- means clustering eigenvectors. Each color represents distinct cluster, and the coarsened graph is obtained by mapping nodes from the same cluster (color) single super-node. We observe that the clusters produced by SINGC are more balanced, which is advanta- geous for downstream graph learn- ing tasks.
the leading
(
(
A.4 Gradient Computation
We start with a recap of our suggested objective function:
min f(X C) x.C
|| LX -x] LCX11C- (trr-Btt((( [C)
+ x 1|, - a log dL.
stt
x
22

---

The gradient of each term with respect to C' is:
(c(-tr(U(((()))) TCC))) -2
Ve(IX LX X LCX, -2LCXX LX- (XC
+2L +2L LX -CX)) LCx.) ICX.)X.)
Ve(IIC" Claxk
co Le J)) LC(C LC JJ-
where the third shown in [4 assuming all elements of C' non-negative (since C C. The
full gradient with respect to C of 9 is:
Vcf(C, x,) (A (
-2LCX (X LX -LXX.
+ 2 CX. LX (CX.) (CXX)''XXX)X
+ACl*xk - a(LC(C LC +J-
(16)
We note that in case of the SINGC Algorithm the computed gradient is simpler and can be express as:
Vol(C, 20 ( AC1 aLLC(C" LC + +)
(17)
INGC
SINGC
1.0
Citeseer, Ir=1e:5
1.00
Citeseer, Ir-1e-5
Ir=1e-4
Citeseer, Ir=1e-4
0.9
Citeseer, In-1e-3
0.99
Citeseer, Ir-1e-3
0.8
Cora, Ir-1e-4
Core, Ir=le:5
0.98
Cora, Ir=1e-4
Cora, Ir=le:5
Cora, Ir=1e-3
Cora; 1e-3
Loss
Loss
0.97
0.6
0.96
0.5
0.95
0.4
0.94
0.3
200
400
600
800
1000
200
400
800
1000
Gradient steps
Gradient steps
Figure 3: Convergence rates of INGC and SINGC methods for Cora and Citeseer datasets. Citeseer results shown in blue with varying line styles for different learning rates, while Cora results shown in red. Gradient steps are on the x-axis, and normalized loss values are on the y-axis.
B Methods Performance Visual Comparison
Table 3: Comparison of gradient expressions and time complexities for FGC, INGC, and SINGC.
FGC
INGC
SINGC
Gradient Expression
Vef(C, =x) 2(
Vef(C, x.) 287
Vef(C) = (7
x( + *CClex
[2L(CX)) LX
+XC1
(LCX.) (CX.))
-a(OO(C +C+ [((COC"(LC+)))1
AC1xX
aLLC(C LC LC+
Theoretical Complexity
Time
O(1((k+ +9)
(nn +))
O 2 + nk? +k2)
+ nddk + nol k3)
In Section 4 we demonstrated the global preservation property of our method on a specific task with low number of super-nodes, similar clustering task. However, in typical coarsening scenarios,
23

---

Table 4: Runtime comparison of our methods and FGC for coarsening ratio of 0.03, where all times are reported in seconds. Columns 2-5 show the runtime of each coarsening algorithm. Column 6 reports the training time of GCN on the original graph, while Column reports the training time on the coarsened graph. The final column shows in percentage how much training time was saved by applying coarsening before training, compared to training on the full graph.
Dataset
FGC
INGC
SINGC
INGC(8 0)
GCN full
GCN coarse
Speedup
Citeseer
04.67
09.38
04.04
06.11
42.02
26.03
14-29%
Pubmed
20.54
75.27
49,47
33.05
93.15
23.92
21-38%
Co-CS
70.80
284.13
180.33
120.66
369.10
40.86
12-56%
Co-Phy 266.83
1200.76
720.22
540.50
883.96
52.26
12-32%
there are usually a larger number of super-nodes. this section, we present the performance of this property in more practical coarsening scenarios, showing how our method continues to preserve the global structure of the graph.
In Figures 5 and
present the results obtained by our methods (INGC/SINGC), alongside the three baseline methods described in Section on the Karate Club and Les Miserables datasets. Each row in the figures shows the partitioning produced by each method at different coarsening ratios. Nodes of the same color are grouped into same super-node. We observe that our method groups adjacent nodes into super-nodes, thereby preserving the global structure of the graph.
Since our method leverages the graph Laplacian eigenvectors partition the vertices, we also compare it to the commonly used spectral clustering approach [19], which partitions the vertices by applying k-means 40 on the leading graph Laplacian eigenvectors.
Figure 2 we present the clustering results obtained by the SINGC method on the well-known Karate Club dataset which consists of 34 nodes. We apply our method with a target of 2 17 super-nodes and compare the results to those obtained by spectral clustering applied to the top & leading eigenvectors. In the figure, each color represents distinct cluster: We observe that the clusters produced by our method are more balanced compared to those generated by spectral clustering, which tends to form one large cluster alongside several smaller, single-node node clusters. This balance advantageous for downstream graph learning tasks, such as graph pooling.
C Complexity Analysis
For an input graph with nodes, edges, and node features of dimension p. the coarsened graph has nodes and e, edges. The dominant computational cost of the coarsening process arises from the gradient computation performed at each optimization step. Table 3 summarizes the gradient expressions and their time complexities, highlighting that SINGC is the most efficient, while INGC remains competitive with FGC, considering the gradient computation.
Both INGC and SINGC have additional overhead beyond the optimization itself due the computa- tion of the top-k Laplacian eigenvectors, which typically requires O(nkk) operations. This step can significantly increase the total runtime. However, this cost can be avoided by setting / = O, which removes the Grassmann similarity term from the objective. As shown in Table 6 even without this term, our methods still outperform the baselines.
Table reports the runtime our methods and FGC, demonstrating their efficiency in reducing GNN training time. Specifically, compare the time required to train a GCN the original graph versus the coarse graph, including the coarsening time. The results confirm that applying coarsening before GCN training yields substantial time savings summarized in the last column of the Table.
All runtime values are reported in seconds. Experiments were conducted on a machine with 12th- Intel i7 CPU, NVIDIA RTX A5000 GPU, and 64 GB of RAM.
24

---

Table 5: Average fraction of signal energy captured by the first & Laplacian eigenvectors (i.e..
k-smoothness) for each dataset and coarsening ratio.
Dataset
r=l
r=0.7
r=0.5
r=0.3
r=0.1
r=0.05
r=0.03
r=0.01
Cora 0.85
0.74
0.60
0.38
0.27
0.19
0.08
Citeseer 0.86
0.76
0.63
0.34
0.25
0.18
0.10
Pubmed
0.87
0.77
0.65
0.50
0.43
0.39
0.32
Co-CS
0.77
0.67
0.55
0.34
0.26
0.22
0.14
D
Convergence Analysis
Figure B iillustrates the convergence rates of the INGC and SINGC methods on the Cora dataset for coarsening ratio r = 0.3. The left subplot shows the performance of INGC, while the right subplot depicts SINGC. For both methods, Citeseer results are in blue with varying line styles for different learning rates, and Cora results in red with corresponding line styles. The x-axis represents gradient steps, and the y-axis shows normalized loss values.
The results reveal a typical convergence pattern for different learning rates. A trade-off is observed between convergence speed and final objective loss: higher learning rates lead faster convergence but result in a higher final loss. This phenomenon is consistent across both datasets. We note that recent work has shown that lower learning rates achieve lower minimal loss values but may risk unstable solutions 41
E Smoothness Assumption
Assumption 3.3 a standard premise graph signal processing and learning on graphs, closely related to the notion of homogeneity and homophily in datasets [42]. To assess how frequently this assumption holds in practice, we evaluate the k-smoothness of node features by computing the fraction of their energy captured by the subspace spanned by the first A: Laplacian eigenvectors.
Table 5) reports the average energy concentration across all datasets used in our experiments for various values of k.
Notably, our method performs well even when the smoothness assumption is only partially satisfied. This highlights its robustness and broader applicability beyond the ideal smooth setting.
F Hyperparameters Discussion and Ablation Study
We review the purpose of each term our optimization and clarify the motivations behind selecting the hyperparameters values. The parameter 3 promotes minimizing the IPE for general smooth signals. As shown in Proposition 3, minimizing the respective term also bounds the REE (related to preserving the graph's 's global structure) and DE (related to preserving the norm of node features). Therefore, 33 is significant when these properties are prioritized in coarsening. The parameter enforces group sparsity in each row, ensuring the validity of the obtained coarsening operator C. Since C lacks meaningful structure without this term, we did not perform an ablation study on A. Finally, the parameter a promotes connectivity in the coarsened graph, making it significant in scenarios where preserving graph connectivity is essential.
Figure Soureepreseee presents experiment analyzing each parameter's contribution and our method's sensitivity to their variations. The bars represent normalized scores for different values of given byperparameter, with distinct colors denoting specific values. For all metrics, lower values indicate better performance. The other two parameters are set to their optimal values for each metric as specified in Table The figure illustrates the sensitivity of each parameter and evaluates the impact of deviations from optimal values on various metrics.
In Figures 4 a) bb) varying shows minimal sensitivity across metrics, except for IPE, where changes up to an order magnitude still yield similar results. Additionally, the figures include an ablation study on the parameter a illustrating its contribution to the optimization process. In Higures[cc) and varying À demonstrates that our methods are more sensitive to this parameter, highlighting its critical role in performance.
25

---

INGC
SINGC
1.0
Valaes
0.00
0+00
0.1
0=01
Normalzed
1-10
Normalzed
0=100
0.4
16.
10.3
d 1000
1000
02
0.0
0.0
Metrics
(a) Sensitivity to a (INGC)
(b) Sensitivity to a (SINGC)
0.8-
Valaes
A-0.1
A-1.0
Normalzzed Scores
0.8
A-011
A=10
Nornaized
0.-
A 160.0
A-10.
A=18.
Aw 110000
0.4
A 200.0
A-200.0
02-
REE
RE
DE
REE
4E
HE
DE
IFE
Metrics
Metrics
(c) Sensitivity A (INGC)
(d) Sensitivity A (SINGC)
Figure 4: Ablation study the sensitivity and contribution of the hyperparameters and across different metrics on the Cora dataset with a coarsening ratio r = 0.3. (a) and (b) show the sensitivity of the parameter a across metrics. (c) and (d) illustrate the sensitivity of the methods parameter A. The bars represent normalized scores for different values of the respective hyperparameter, with distinct colors denoting specific values. Lower bar values indicate better performance.
Table 6: Ablation study of the parameter 3 on node classification tasks. The table reports the accuracy on various datasets for different coarsening ratios r using different coarsening methods. The third column presents the results of our INGC method with 0, the fourth column corresponds to the optimal 3 value, and the fifth column shows the results SINGC, Best results are bold; underlined. The last two indicate the number of times each method achieved the best and second best performance.
second- best results
Dataset
INGC(3 0)
INGC
SINGC
0.3
84.62
0.59
87.55 I 0.16
84.51 0.33
Cora
0.1
83.01 + 0.53
83.38 + 0.47
82.76 + 0.32
0.05
76.92
1.11
77.42 + 0.78
77.81 0.68
0.3
76.25 0.28
76.89 0.23
76.66 0.27
Citeseer
0.1
67.07 + 0.59
72.63 + 0.25
69.71 0.72
0.05
60.66 1.58
66.02 + 0.32
66.37 + 0.57
0.05
83.60
+ 0.23
83.59 + 0.22
83.55 + 0.32
Pubmed
0.03
81.62 0.14
81.93 0.22
83.19
0.18
0.01
79.08 0.72
79.09 + 0.26
79.96 + 0.34
0.05
90.42
90.84 + 0.12
90.92 0.22
Co-CS
0.03
89.28 0.21
89.59 = 0.38
89.99 + 0.41
0.01
77.79 1.15
87.93 + 0.33
83.39 + 0.33
#Best
6
#2-Best
6
5
In Table 6 we present an ablation study on the parameter for the node classification task across various datasets and coarsening ratios The comparison includes three methods: INGC with 3 = 0 (ignoring the term (r(( (T)()) CCT) for minimizing IPE for general smooth signals). INGC with the optimal B, and SINGC (our second proposed method, which omits the first term of the objective entirely). The table reports node classification accuracy, with the best results highlighted in bold and second-best results underlined. For each metric, other hyperparameters are set their optimal values. The results demonstrate the importance of balancing the two complementary approaches to minimizing IPE. INGC with 3 0 generally underperforms compared to the other methods, emphasizing the significance of the smooth signal term in achieving high classification accuracy.
26

---

G
Additional Details on the Experimental Study
Reproducibility Statement
We ensure reproducibility by providing detailed description of methodology, including algorith- mic steps (Algorithms 2 evaluation procedures, and hyperparameter settings (Appendix Gr. The code used in this paper will be made available in public repository upon acceptance. Full proofs of the theoretical results are included in the appendix, along with precise descriptions of our experimental setups.
(..3 G.2).
G.1 Datasets Details
Table 7: Graph coarsening metrics experimental setting: Chosen hyperparameters for the Karate Club dataset different coarsening ratios (r) and metrics.
Karate Club dataset
Metric
Method
== 0.7
r = 0.5
r 0.3
INGC
3-0, 10100, a=0.1
3-200, A=10, a=1
B=100, x=100, a=0.1
REE
SINGC
x-0.1,
X=0.1,
1=0.1,
INGC
8-0, a=1,
3=200, A=0.1, a02
8=200, x=1,
SINGC
X-0.1,
a=
X=1,
INGC
3-0,
8 200,
A-0.1,
202
8-200, 7-1, -02
SINGC
A=0.1,
A=0.1,
a=200
X=10, o=
INGC
8=0, a=
200, X=1, a=2
1=0.1, a=00
SINGC
x= 10=0.e0 a00
a=20
2= a=200
Table 8: Graph coarsening metrics experimental setting: Chosen hyperparameters for the Les Miserables dataset at different coarsening ratios (r) and metrics.
Les Miserables dataset
Metric
Method
0.7
0.5
0.3
INGC
8=100, X=200, a=0.1
8=200, \=10, a=0.1
-=200, 2-200, a=1
REE
SINGC
1=0.1,
X=100, a.0.1
>=0.1, a=0.1
INGC
B-200, A=10, 1=100
3=200,
1=
8=200, 1=000
RE
SINGC
1=0.1,a=100
>=1, a=200
>=100, a=100
INGC
B=200, X= a=100
8=200, 1=10, a=200
3=200,
1= 0=200
HE
SINGC
A=0.1, 1=0 10000
>=0.1, o=20
A=100, 1=00
INGC
8=0, 20200, 2=200
0=0.1, X=0.1, 1=10
8=0.1, A=0.1,
DEE
SINGC
A=100, 1=100
X=10, a=100
10100, a=200
G.2 Node Classification Experiments Setting
The GCN model used in experiments consists of two graph convolutional layers and is imple- mented using Py Torch and Py PoTrch Geometric libraries. The architecture is as follows:
Layer 1: A Graph Convolutional Network (GCNConv) layer that takes the input node feature matrix X (with X.shape[1] features) and outputs a hidden representation of size 64.
Layer 2: A second GCNConv layer that maps the 64-dimensional hidden representation to the number of output classes (NUM_ OF_CLASSES)
We use ReLU for non-line con-eincayyty and dropout for regularization during training.
27

---

Table 9: Graph coarsening metrics experimental setting: Chosen hyperparameters for the Cora dataset at different coarsening ratios (r) and metrics.
Cora dataset
Metric
Method
r 0.7
r
INGC
3-10, X=1, 0=1
8=100, A=1, a=1
8=200, A=10, a=10
REE
SINGC
X=1, a=10
1=100, a=100
A=200, a=0.1
INGC
B=10. 10, 1000,, a=200
B=100,
2 a=200
8=100,
10 a=200
RE
SINGC
x=100, o=200
A=0.1, a=100
X=100, a=100
INGC
B= 1=100, a=200
8=100,
2020 a=200
8=100, 1=10, a=
HE
SINGC
10100, 2=200
x=1, a=10
A=100, x= 100
INGC
8= X=10, a= 10
DEE
SINGC
3=100,a=200
A=10, a=100
1=100, a=200
Table 10: Graph coarsening metrics experimental setting: Chosen hyperparameters for the Citeseer dataset different coarsening ratios (r) and metrics.
Citescer dataset
Metric
Method
T == 0.7
r 0.5
T= 0.3
INGC
3=200, 2-200, a=200
B=100,
10, a=0.1
8=100, A=10, a=0.1
REE
SINGC
X=10, a=0.1
100, a=0.1
1=10, a=1
INGC
B-100, X=10,
B-100,
X=1, 1=
8-0, x=10, a=0.1
RE
SINGC
a=100=100
A=10, 0=100
>=100, a=200
INGC
8=100,
0=100
A=100,
8=200, A=0.1, a=0.1
HE
SINGC
a=10
x=1,
X=100, a=200
INGC
8=1, X=0.1, a=01 2=2 a=1,
a= 10
DEE
SINGC
1=100,
1=100 a=200
A=100, a=100
For SINGC, we set titer 2000 in all experiments, and for INGC, we set titer 20 and Citer = 100. Tables 12 and II present the hyperparameters of our methods for each experiment. The results for the three baseline methods presented in Table 2 are sourced from Kumar et al. [14.
We note that tuning the hyperparameters our methods is crucial for achieving optimal performance. By reviewing some of the corresponding setting in Tables [0] and 11 we can observe that good performance often aligns with low values of REE and INP in this application. Therefore, we recommend that practitioners first optimize the hyperparameters by minimizing REE and INP. Once optimized, the coarsened graph can be used in the GNN for training and evaluation, leading to improved classification accuracy.
The additional details of real datasets are as follows:
Table 11: Node classification experimental setting: Chosen hyperparameters for the Cora Citeseer dataset different coarsening ratios (r) and metrics.
Node Classification Parameters Medium datasets
Dataset
Method
0.3
0.1
0.05
INGC
B= 1=000 a=10
1000, a=1
1= 1= 100, a= 100
Cora
SINGC
>=10, 000.1
>= 1000, a=1
\= 1000, a00.01
INGC
1=000 10
3 10, x= 1000, a= a= 1000
3=0, 0=0, X= a=
Citeseer
SINGC
3=50,
3-300, a=100
A=50, a=10
28

---

Table 12: Node classification experimental setting: Chosen hyperparameters for the Co-phy, Pubmed,
Co-CS dataset at different coarsening ratios (r) and metrics.
Node Classification Parameters Laarge datasets
Dataset
Method
0.05
0.03
0.01
INGC
3= 10, 1=10, 0.0.1
-= x= 1000, a=0.01
3=10, X= 1000, a=100
Co-phy
SINGC
x=100, a=0.1
A=10, a=1
X= a=100
INGC
8=0, A=1000, 000000
B=0.1, a=10
0.1,, 1000, a=100
Pubmed
SINGC
1=1000, a=0.001
x=100, a=0.1
A=10, a=
INGC
B=1, x=1000, a=10
0=1,,
3= 10, x=100, a= 100
Co-CS
SINGC
x=40, a=10
>=10, a=10
x=100, a=100
| 78- Here, nodes represent members of karate club, and edges represent friendships between them. Synthetic features generated using the signal model presented at Section 3.1
Karate nl - 30, =
Les Miserables = 77. p= 50, |8| = 254 Nodes represent characters in the novel *Les Miserables and edges indicate co-occurrence in the same chapter. Synthetic features generated using the signal model presented Section 3.1
Cora n 2, 708, p 1, 433, |E| 5, 429 Nodes represent research papers, and edges represent citation links between them. Node features correspond to the presence of specific words in each paper, and class labels indicate the paper's research field. Number of classes =7.
Citeseer - = 3, 32,327,1 p 3, 703, |3| = 4, 732 Nodes represent research papers, and edges represent citation relationships. Node features are based on word occurrences each paper, and class labels indicate the paper's s topic. Number of classes = 6.
Co-Physics n = 34, 493, = 8, 415, E = 247, 962 Nodes represent physics research papers, and edges represent citations. Node features represent article keywords, and class labels indicate different fields of physics. Number classes 5.
PubMed n 19, 717, p 500, |E| 44, 338 Nodes represent biomedical research papers, and edges represent citations. Node features derived from TF-IDF scores of medical terms, and class labels indicate disease categories. Number of classes = 3.
Co-Computer - 13, 752, p 767,
245, 861 Nodes represent products in co-purchase network, and edges indicate products frequently purchased together. Node features describe product attributes, and class labels represent product categories. Number of classes = 10.
Co-CS = 18, 333, = 7005 |8| = 163, 788 Here, nodes are authors, that are connected by edge if they co-authored paper; node features represent paper keywords for each author's papers, and class labels indicate most active fields of study for each author. Number of classes 15.
G.3 Graph Coarsening Metries Experiments Setting
Tables 7 9 and 10 present the hyperparameters of our methods for each experiment. For SINGC, Fiter 2000 all experiments, and for INGC, we set ther 20 and Cuer 100.
Regarding the implementation of the baseline comparison methods, the FGC hyperparameters were selected based on their optimal values reported in their paper. The LVN and LVE methods were implemented using their provided graph coarsening libraries, with the maximum value of the parameter K ke
29

---

Karate Club
LVN
LVE
FGC
INGC
SINGC
T= 0.7
r= 0.5
r= 0.3
Figure 5: Visual comparison of coarsening methods on the Karate Club dataset. Each row displays the partitioning produced by each method at different coarsening ratio. Nodes of the same color grouped into the same super-node.
30

---

Les Miserables
LVN
LVE
FGC
INGC
SINGC
T= 0.7
r= 0.5
== 0.3
Figure 6: Visual comparison of coarsening methods on the Les Miserables dataset. Each row displays the partitioning produced by each method different coarsening ratio. Nodes of the same color grouped into the same super-node.
31

---

Planner Graph
LVN
LVE
FGC
INGC
SINGC
0.7
r= 0.5
r r= 0.3
Figure 7: Visual comparison of coarsening methods on a planner graph. Each row displays the partitioning produced by each method different coarsening ratio. Nodes of the same color grouped into the same super-node.
32


Reviews:
[{"review_id": "O7dclbS6XJ", "reviewer": "Reviewer_XzK6", "summary": "This paper proposes the inner product error as a loss function for evaluating the quality of a graph coarsening. In particular, for a graph Laplacian $L$ with node features $X$ and a coarsened Laplacian $L_c$ with coarsened features $X_c$, the proposed inner product error is defined $\\| X^TLX - X_c^TL_cX \\|_F^2$. The authors further propose the INGC algorithm for graph coarsening. INGC finds a coarsening by solving a constrained optimization problem (Equations 8 and 9). The loss function includes the inner product error between the original graph and the coarsened graph, as well as smoothness conditions on the coarsening and regularization terms aimed at making the coarsening well-defined and the coarsened graph connected. The paper also presents some theoretical justfications of the inner-product loss, as well as experiments on several benchmark datasets.", "questions": "## Questions\n\n(1) The statement of Proposition 3.2 requires a certain condition (the graph has n-k connected components), but I cannot see where this condition is used in the proof. Why is this condition needed?\n\n(2) Does the runtime of INGC in Table 3 in Supplement account for the time to do the projection?\n\n## Suggestions\n\n- I believe for the properties of Equation (7) to hold, it needs to be the case that P_{i,j} > 0 if *and only if* j is mapped to the ith super node above. The way it is written in your paper, only one of these conditions is required for P. (I am basing this off the proof of Proposition 6 in [Loukas, 2020])\n\n- The proof environments seem a little weird. I would suggest to use the \\begin{proof}\\end{proof} commands that are a part of amsthm.\n\n## Typos\n\n- Line 148: rank(L) < k\n\n- Proposition 3.2: The phrasing \"for any two graph signals\" is ambiguous, as \"for any\" could either mean for all or there exists. I would recommend changing this to \"for all pairs of graph signals\".\n\n- Proposition 3.2: In this main text, this result is called a \"Proposition\", but in the appendix, it is called a \"Theorem\". Likewise, Line 209 refers to Proposition 3.4 as \"Theorem 3.4\".\n\n- Appendix, Line 818: The LaTeX commands \\log and \\det should be used.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The inner-product loss makes a lot of sense. The authors use theoretical results to justify the two main components of their loss terms. Propostions 3.5 show that minimizing the proposed loss also minimizes the losses REE and RE (definitions 2.1 and 2.2), two existing losses from the graph coarsening literature. While Proposition 3.2 and 3.4 don't hold in all cases, Proposition 3.5 provides an analysis that works in all cases and that gives better theoretical results the lower the loss. Moreover, the authors perform a simple experiment (table 5) to show the conditions of Proposition 3.5 are realistic.\n\n- The proposed coarsenings outperform existing coarsening techniques on several datasets and on several evaluation metrics (Table 1). \n\n\n## Weaknesses  \n\n- While the proposed inner-product loss is new and well-motivated, its contribution appears a llittle incremental. For the theoretical results, the conditions for Proposition 3.2 are too strong, and Proposition 3.4 is not surprising.  (Proposition 3.5 is the most interesting result of the paper in my view.) \n\n- While Table 1 shows better graph coarsening metrics of proposed methods, the advantage in node classification is not large (Table 2). At the same, the time to compute INGC and SINGC can be quite a bit slower than existing method FGC – see Table 4 in the Supplement – even though they have similar asymptotic runtimes.", "was_revised": true, "final_justification": "I appreciate the authors' responses. Nevertheless, I think the main weakness I listed in the original reviews stand and I will maintain my rating.", "rebuttal": "Thank you for the time and effort you put into reviewing our paper. Your\ncomments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are:\n\n# *Theoretical results clarifications*\n\nWe thank the reviewer for their valuable comment on Proposition~3.2. We acknowledge that the rank condition stated in the proposition might be too strong and is not required for the proof. It is sufficient to state that if the inner product is preserved for all pairs of graph signals, i.e., $\\boldsymbol{x}^\\top \\boldsymbol{L} \\boldsymbol{y} = \\boldsymbol{x}_c^\\top \\boldsymbol{L}_c \\boldsymbol{y}_c$, then the original Laplacian $\\boldsymbol{L}$ can be exactly recovered from $\\boldsymbol{L}_c$. However, a necessary condition for the first identity to hold is that the rank of $\\boldsymbol{L}$ is at most $k$; otherwise, it is not feasible to recover $\\boldsymbol{L} \\in \\mathbb{R}^{n \\times n}$ from $\\boldsymbol{L}_c \\in \\mathbb{R}^{k \\times k}$. \n\nFollowing your suggestion, we will revise the paper and remove the rank assumption from the proposition statement and instead include it as a remark immediately following the result. We will also clarify that, although this condition is unrealistic in most practical settings, the result is not intended to imply that exact reconstruction is feasible in general. Rather, it is meant to theoretically motivate our focus on minimizing inner product error as a meaningful proxy for preserving the graph’s structure during coarsening.\n\nAlthough the results of Proposition~3.4 may not be surprising, the proposition supports the development of our method. It formally establishes the connection between minimizing the IPE and maximizing the Grassmann similarity between the coarsening operator $\\boldsymbol{C}$ and the top-$k$ eigenvectors of the original Laplacian, $\\boldsymbol{U}^{(k)}$.\nIn particular, it shows that maximizing Grassmann similarity leads to IPE minimization for all graph signals that satisfy the smoothness assumption, enabling a principled method that generalizes to unseen smooth signals as well.\n\nThis connection is also crucial for understanding the implications of Proposition~3.5, as it provides a theoretical bridge: minimizing IPE for general smooth signals implies improvements in both REE and DEE metrics.\n\nImportantly, our formulation is based on Grassmann similarity rather than distance, which enables us to incorporate it directly into a differentiable loss term.\n\n# *Method and run time clarification*\n\nThe runtime results in Table~3 include all major computational steps: spectral decomposition, optimization, and the final projection of the features and Laplacian, i.e., computing $\\boldsymbol{X}_c = \\boldsymbol{P} \\boldsymbol{X}$ and $\\boldsymbol{L}_c = \\boldsymbol{C}^\\top \\boldsymbol{L} \\boldsymbol{C}$.\n\nWe acknowledge that INGC is slower compared to other methods, which is expected since it considers richer structural information by preserving pairwise feature relationships. In contrast, SINGC is significantly more efficient, as its main computational cost arises from the eigenvalue decomposition, while the optimization step is relatively efficient. We believe this trade-off is justified given the consistent improvement in coarsening quality.\n\nIt is important to note that our approach is not adversarial to FGC. While FGC focuses on reconstructing individual node features and enforcing smoothness on the coarsened graph, our method aims to preserve the mutual relationships between node features by minimizing the IPE. These objectives are complementary, and in principle, both approaches could be integrated into a unified framework. However, to clearly isolate and demonstrate the advantages of our proposed perspective, we evaluate it independently of FGC in this work, using the same regularization terms.\n\n# *Other suggestions and Typos*\nThank you for pointing out our formatting issues. We accept all your suggestions and will fix them in the revised version of the paper."}, {"review_id": "01eismgXQt", "reviewer": "Reviewer_pbs3", "summary": "This work presents a graph coarsening method aimed at preserving inner products between node features. A new Inner Product Error (IPE) metric is introduced to measure how the inner products between graph signals are preserved. New connections between IPE minimization and structural consistency of the coarsened graph are established to confirm the effectiveness of IPE. In experiments, both SBM random graph model and real-world graphs are employed to evaluate the proposed INGC model.", "questions": "1. Is the proposed method applicable to heterophilic graphs where nearby nodes are likely from different classes?\n2. Given a graph Laplacian $L$ and graph signals $X$, Dirichlet Energy considers only the diagonal elements of $X^TLX$, i.e. $tr(X^TLX)$, while the proposed IPE additionally considers off-diagonal elements. **In addition to existing theoretical results in Prop. 3.4**, how to understand the contributions of these off-diagonal elements?\n3. How to handle graphs without node attributes?", "limitations": "scalablity and applicability to graphs of varying homophily could be discussed.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The proposed IPE appears novel.\n2. Comprehensive theoretical analyses are provided to explain why IPE minimization is beneficial.\n3. The paper is well-written and probably easy to follow.\n\nWeaknesses:\n\n1. The overall contribution is somewhat limited. Apart from the IPE term, the rest of the objective is heavily borrowed from FGC [14]. Notably, the Grassmann manifold-based inner product preservation is a commonly used technique in graph signal processing, so I don't consider it a novel contribution.\n2. As described in the first paragraph of the Introduction, the motivation is to speed up graph machine learning by reducing the graph. However, the theoretical time complexity of the proposed method is quadratic in the number of nodes, making it hard to handle large-scale graphs in practice. For small-to-medium scale graphs, there is typically no need to perform graph reduction beforehand. This nature makes the proposed method less meaningful. There are also no experiments conducted on large-scale graphs such as ogbn-products and ogbn-papers100M.\n3. The baselines are outdated.", "was_revised": true, "final_justification": "After discussing with the authors, the major weaknesses identified from my original review still apply, so I decided to maintain the rating. Nevertheless, the overall quality of the work is commendable, and I am inclined to recommend its acceptance.", "rebuttal": "Thank you for the time and effort you put into reviewing our paper. Your\ncomments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are:\n\n# *Contribution and relation to FGC*\n\nOur method proposes a complementary approach to FGC that addresses a different aspect of the coarsening problem. While FGC focuses on preserving individual node features via reconstruction (i.e., minimizing $\\|\\boldsymbol{X} - \\boldsymbol{C} \\boldsymbol{X}_c\\|$) and promoting smoothness on the coarsened graph (i.e., minimizing $tr(\\boldsymbol{X}_c^\\top \\boldsymbol{L}_c \\boldsymbol{X}_c)$), our method aims to preserve the mutual relationships between node features by minimizing the IPE. These objectives are complementary, and in principle, both approaches could be combined into a unified framework.\n\nThe diagonal elements of $\\boldsymbol{X}^\\top \\boldsymbol{L} \\boldsymbol{X}$ reflect only the individual smoothness of signals/node features (i.e., their Dirichlet energy) with respect to the graph, and ignore the cross-relationships between different signals. In contrast, the off-diagonal elements capture the pairwise interactions between different node features. Specifically, the $(s,k)$-th entry is given by:\n\\begin{align*}\n\\boldsymbol{X}^\\top \\boldsymbol{L} \\boldsymbol{X}[s,k] = \\boldsymbol{x}^{(s)\\top} \\boldsymbol{L} \\boldsymbol{x}^{(k)} = \\sum_{(i,j) \\in E} w_{ij} \\left( x^{(s)}(i) - x^{(s)}(j) \\right)\\left( x^{(k)}(i) - x^{(k)}(j) \\right),    \n\\end{align*}\nwhere $\\boldsymbol{x}^{(s)} = \\boldsymbol{X}[s,:]$ and $\\boldsymbol{x}^{(k)} = \\boldsymbol{X}[k,:]$ are the $s$-th and $k$-th node feature vectors, respectively. These terms reflect how similarly pairs of features vary across the graph, thus encoding valuable structural information.\n\nProposition 3.4 establishes a connection between these off-diagonal terms and the Grassmann similarity. Together with Proposition 3.5, they imply that maximizing the Grassmann similarity leads to IPE minimization for smooth signals and improves both the REE and DEE coarsening metrics. This result provides theoretical justification for including the Grassmann term in our objective function.\n\nWe note that the only components borrowed from FGC are the regularization terms. These were intentionally reused to ensure a fair and controlled comparison, allowing us to isolate and evaluate the contribution of our proposed IPE term and overall coarsening approach.\n\nImportantly, our formulation is based on Grassmann similarity rather than distance, which enables us to incorporate it directly into a differentiable loss term with a closed-form expression. This choice is key to allowing efficient gradient-based optimization and is central to the novelty of our method.\n\n# *Datasets and baselines*\n\n**Baselines:** We note there exist two recent graph coarsening methods—CMGC [1] and SGBGC [2] that could be considered as baselines; however, their experimental setups differ significantly from ours. Specifically, they adopt a 60/20/20 data split and evaluate classification performance via cross-validation on only 20\\% of the labels.\n\nIn contrast, we follow the evaluation protocol established in SCAL and FGC, where a Graph Neural Network (GNN) is trained on the coarsened graph and used to predict all node labels for the original graph.\n\nWe attempted to include CMGC and SGBGC in our experiments, but were unable to reproduce their code due to missing information (e.g., missing README in SGBGC and broken repository link for CMGC). As a result, we were unable to evaluate their methods in our experimental setup and therefore did not include them in the original comparison.\n\nFollowing your comment, we conducted an additional search and identified a third recent method, MGC[3], that is compatible with our setting. \nA comparison between our methods and the additional baseline is detailed in the table below.\nWe will include MGC as an additional baseline in Table~2 of the revised paper, and our results continue to demonstrate the strong performance of our proposed method. \n\n|   Dataset   |   r  |            MGC[3]           |          INGC (Ours)          |         SINGC (Ours)        |\n|-------------|:----:|:---------------------------:|:-----------------------------:|:---------------------------:|\n| Cora        |  0.3 |  $\\underline{84.56\\pm1.40}$ |  $\\boldsymbol{87.55\\pm0.16}$  |        $84.51\\pm0.33$       |\n|             |  0.1 |        $76.02\\pm0.93$       |  $\\boldsymbol{83.38\\pm0.47}$  |  $\\underline{82.76\\pm0.32}$ |\n| Citeseer    |  0.3 |        $74.60\\pm1.20$       |  $\\boldsymbol{76.89\\pm0.23}$  |  $\\underline{76.66\\pm0.27}$ |\n|             |  0.1 |  $\\underline{70.57\\pm1.25}$ |         $72.63\\pm0.25$        |        $69.71\\pm0.72$       |\n| Co-phy      | 0.05 | $\\boldsymbol{94.52\\pm0.19}$ |   $\\underline{94.29\\pm0.10}$  |        $94.04\\pm0.06$       |\n|             | 0.03 |  $\\underline{93.64\\pm0.25}$ | $\\boldsymbol{94.20 \\pm 0.13}$ |       $93.52 \\pm 0.13$      |\n| Pubmed      | 0.05 |        $81.89\\pm0.00$       |  $\\boldsymbol{83.59\\pm0.22}$  |  $\\underline{83.55\\pm0.32}$ |\n|             | 0.03 |        $80.70\\pm0.00$       |   $\\underline{81.93\\pm0.22}$  | $\\boldsymbol{83.19\\pm0.18}$ |\n| # Best      |      |              1              |               5               |              1              |\n| # 2- Best   |      |              3              |               2               |              3              |\n**Table 2.** Node classification accuracy across datasets and coarsening ratios ($r$). Best results are in bold; second-best results are underlined. The last two rows indicate the number of times each method achieved the best and second-best performance.\n\n**Hetrophily graphs:**  A central assumption in our work is that node features are smooth with respect to the graph structure, which is connected to the graph homophily assumption. This smoothness assumption underlies both our formulation and theoretical guarantees. For this reason, we do not include heterophilic datasets in our experimental evaluation.\n\nMore specifically, the second term in our objective relies on this smoothness assumption, as it encourages alignment with the subspace spanned by the low-frequency eigenvectors of the graph Laplacian. In heterophilic graphs, this assumption does not hold, and our theoretical results would no longer be valid. \n\nOne potential direction for adapting our method to such settings is to modify the second term in the objective to project onto a different frequency range—e.g., using $\\boldsymbol{U}^{(k)}$ corresponding to mid- or high-frequency eigenvectors if prior knowledge of label-frequency alignment is available. However, such a modification would require a fundamentally different theoretical treatment, which we believe is beyond the scope of this work. \n\nFollowing your suggestion, we will add a discussion of this limitation and possible future extensions to the Conclusion section of the revised manuscript.\n\n# *Scalability*\nWe acknowledge that optimization-based coarsening methods—including ours and FGC—have scalability limitations when applied to extremely large graphs. A commonly adopted strategy to address this issue is to partition the graph into smaller, manageable subgraphs[4], process each independently (and potentially in parallel), and then reconnect them.\n\nWe will clarify this limitation in the updated paper and explain how such a strategy can be incorporated into our framework to extend its applicability to large-scale graphs.\n\n# *Additional Clarification*\n\nPlease note that our second proposed algorithm, SINGC, does not use node attributes as part of its objective; its optimization is performed solely based on the graph structure via the eigenvectors of the Laplacian $\\boldsymbol{U}^{(k)}$. As a result, it is directly applicable to graphs without node features.\n\n\n\n[1] Dickens et al. \"Graph coarsening via convolution matching for scalable graph neural network training.\" Companion Proceedings of the ACM Web Conference 2024.\n\n[2] Shuyin Xia et al. \"Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training\" The Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25).\n\n[3] Halder et al. \"Multi-Component Coarsened Graph Learning for Scaling Graph Machine Learning\" Companion Proceedings of the ACM on Web Conference 2025.\n\n[4] Karypis et al. \"A fast and high quality multilevel scheme for partitioning irregular graphs.\" SIAM Journal on scientific Computing 20.1 (1998): 359-392."}, {"review_id": "O0VfORNB1K", "reviewer": "Reviewer_9tpS", "summary": "The paper proposes a novel graph coarsening method based on a similarity metric in the Grassmann manifold and the inner product defined in graph theory. The authors analyze the principle of the proposed method solidly, and compare it with the previous method in theory. It provides a geometric view to consider the graph coarsening problem. The extensive experiments show the effectiveness of the proposed INGC and SINGC.", "questions": "1. Can you make a further discussion about that if a graph truly has $n-k$ connected components, will the proposed method achieve the zero error theoretically?\n2. The weights in coarsening matrix $C$ are soft or hard, i.e., the element ranges in $[0, 1]$ or $\\\\{0, 1 \\\\}$ ?\n3. Can you discuss how the Grassmann manifold plays a vital role in the proposed methods?\n4. Others refer to the **Weakness**.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Pros:\n1. The view that considers the coarsening problem with the Grassmann manifold has novelty and insight. It proposed a new coarsening metric.\n2. The authors make some reasonable assumptions, making theoretical analysis more solid.\n3. The experiments are detailed and convincing, since the authors analyze the model in detail by ablation study and visualization, even validating the sense of assumption.\n\nCons:\n1. In Assumption 3.3 of the $k$-smooth graph signal, I think there is a typo that $x=c^T U^{(k)}$, the correct formula is $x=U^{(k)}c$, since the vector $c$ may be a column vector. Otherwise the dimension is mismatched, and $x=U^{(k)}(U^{(k)})^Tx$ will not hold in Appendix A.2, line 779.\n2. Although the proposed method is solid in theory, I am concerned about the assumption for the $(n-k)$-connected components. Since for a large-scale graph, the inter-community structure is also important, but the proposed method is based on the situation for $(n-k)$-connected components, which may lose information about inter-community connecting patterns.\n3. I think the usage of the Grassmann manifold in the gradient descent (GD) algorithm has a misunderstanding. I do not find any projection on gradients. Since in Eq. 8, you think the coarsening matrix $C$ is also in the Grassmann manifold, but as you apply GD to the point in the Grassmann manifold, if you do not project gradients, you can not guarantee that the gradient vector is in the tangent space, making the updated $C$ destroy the orthogonal property.", "was_revised": true, "final_justification": "After discussing with authors, my concerns are already addressed. Especially for the gradient projection process in learning the assignment matrix, the authors provide detailed clarification about algorithms. In all, I think the originality and novelty of this work are great. It proposes a new framework for graph coarsening that leverages the properties of the Grassmann manifold, which will promote the development of Riemannian graph learning to a certain extent.", "rebuttal": "Thank you for the time and effort you put into reviewing our paper. Your\ncomments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are: \n\n# *Theoretical Results Clarifications*\nThe main purpose of Proposition 3.2 is to provide theoretical motivation for focusing on minimizing the IPE as a meaningful proxy for preserving the graph’s structure during coarsening. As noted, exact recovery of the original Laplacian $\\boldsymbol{L} \\in \\mathbb{R}^{n \\times n}$ from a coarsened Laplacian $\\boldsymbol{L}_c \\in \\mathbb{R}^{k \\times k}$ with $k \\ll n$ is only possible under highly specific conditions, such as when the graph has more than $n - k$ connected components. However, the proposition highlights that preserving pairwise signal inner products during coarsening can help retain important structural properties of the original graph.\n\nImportantly, as also noted by another reviewer, we do not rely on this result in our formal proof. Thus, the condition in Proposition 3.2 can be relaxed to the following statement:  \n\"If the inner product is preserved for all pairs of graph signals, i.e., $\\boldsymbol{x}^\\top \\boldsymbol{L} \\boldsymbol{y} = \\boldsymbol{x}_c^\\top \\boldsymbol{L}_c \\boldsymbol{y}_c$, then the original Laplacian $\\boldsymbol{L}$ can be exactly recovered from $\\boldsymbol{L}_c$.\"\nHowever, a necessary condition for the first to hold is that the rank of $\\boldsymbol{L}$ is at most $k$ (implying $n-k$ connected components).\n\nFollowing your comment, we will revise the manuscript to reflect this relaxed version of Proposition 3.2 and include a remark noting the required rank condition. We will also clarify that, although this assumption is unrealistic in most practical settings, the result is not intended to suggest that exact reconstruction is feasible in general. Rather, it serves to conceptually motivate the use of IPE minimization as a principled structural preservation objective in graph coarsening. \n\n# *The Role of the Grassmann Manifold*\nBoth the coarsening matrix $\\boldsymbol{C}$ and the matrix of leading Laplacian eigenvectors $\\boldsymbol{U}^{(k)}$ can be viewed as points on the Grassmann manifold, as they represent $k$-dimensional subspaces in $\\mathbb{R}^n$. In Proposition 3.4, we establish that maximizing the Grassmann similarity between these subspaces leads to minimization of the IPE for any pair of graph signals that satisfy the smoothness assumption. This insight directly motivates the second term in our objective, which explicitly promotes subspace alignment on the Grassmann manifold—thereby ensuring low IPE not only for observed features but also for unseen smooth signals.\n\nFurthermore, Propositions 3.4 and 3.5 together suggest that this subspace alignment provides theoretical guarantees for standard graph coarsening metrics. Specifically, minimizing IPE for general signals under the smoothness assumption leads to improvements in REE and DEE, offering a principled geometric justification for our method’s effectiveness.\n\n# *Optimization process*\nWe thank the reviewer for raising this important point regarding the usage of the Grassmann manifold and projection steps in our gradient-based optimization.\n\nYou are correct that, in general, gradient descent updates may move the coarsening matrix $\\boldsymbol{C}$ outside the Grassmann manifold, and projection is needed to maintain the orthogonality constraint. In our approach, we follow a projected gradient descent scheme, where we periodically project the matrix $\\boldsymbol{C}$ back onto the manifold using the operator Hardmax$(\\boldsymbol{C})$. This operator maps $\\boldsymbol{C}$ back to the Grassmann manifold by enforcing a column-wise orthogonality constraint consistent with the Grassmann manifold structure.\n\nIn INGC Algorithm 1, this projection/mapping step is performed after every $c_{\\text{iter}}$ iterations—specifically, before each update of $\\boldsymbol{X}_c$. We agree that this design could be made clearer in the current algorithm description, and we will revise Algorithm 1 in the updated manuscript by inserting the projection step between Lines 8 and 9, and explicitly referring to the \"Hardmax\" operator.\n\nFor SINGC Algorithm 2, we empirically observed that projecting only once at the end of the optimization yields performance similar to using intermediate projections. Therefore, for simplicity and efficiency, we chose to use standard gradient descent and apply the projection step only at the end in this case. We will add this clarification in the updated manuscript.\n\nWe thank the reviewer again for pointing this out and helping us improve the clarity and correctness of the manuscript.\n\n# *Additional clarification*\n1.) You are correct, there is a typo in Assumption 3.3, the correct formula that aligns with our notation is $x=c (U^{(k)})^\\top$.\n\n2.) The matrix $\\boldsymbol{C}$ applies \"hard coarsening\", with elements in {0, 1}. We denote this assignment using the Hardmax$(\\boldsymbol{C})$ operator, which is applied in the last line of both of our proposed algorithms."}, {"review_id": "LvMTGDxKPo", "reviewer": "Reviewer_sNPx", "summary": "This paper introduces a new graph coarsening method for node-featured graphs. For this, the authors define the Inner-Product Error (IPE) $||X^\\top LX - X_c^\\top L_c X_c ||_F^2$ as a metric that captures how well coarsened graphs preserve the Laplacian-induced inner products of node features. The authors design a minimization objective that couples IPE with a Grassmann-alignment term encouraging coarsening maps to be aligned with the top $k$ Laplacian eigenvectors of the graph, and they propose two coarsening algorithms, the feature-aware INGC and the feature-agnostic SINGC. They then provide some theoretical justification for their choice of objective. Finally, they demonstrate superiority of their method through an empirical study, comparing it to common coarsening methods (local variation neighborhood/edges, feature-based graph coarsening), as well as downstream performance on standard node classification tasks.", "questions": "- Regarding the Laplacian regularization term in the objective in Eq. (9), in lines 179-180 you state that this \"guarantees that the coarsened graph $\\mathcal{G}_c$ is connected\". Why enforce connectivity unconditionally? Does your method assume the original graph is connected, and if not, wouldn’t this merge naturally disconnected components and reduce generality? I would appreciate if you could clarify the rationale.\n- In the beginning of § 3.1/Eq. (10), a \"smooth graph signal generation mechanism\" is introduced, but it seems that this is never really mentioned again later, as Assumption 3.3 proceeds with defining such signals simply as being exactly in the column space of the top $k$ eigenvectors. Is there any point in stating it, other than motivating Assumption 3.3?\n- In several of the visualizations (like pages 29/30) it is quite difficult to visually discern which coarsening method performs better. Perhaps including more structured or (close to) planar graphs could help. Also, since one of the method's key selling points is preserving node-feature relationships, a small example that actually displays how features are mapped could greatly improve intuition.\n- A few times you mention your method is \"functorial\". Is this a standard term in this context that I'm not aware of? When skimming the abstract for the first time I thought there might be some connection to category theory, but it seems you are using the term more loosely to mean \"functional\" or \"structure-preserving\". I might suggest tweaking the wording.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n- Incorporating node features into graph coarsening methods is important as it is widely acknowledged that node features can be just as important for downstream tasks as the actual graph structure. To my knowledge, the introduced IPE metric is novel.\n- The empirical results (e.g, Table 1) look compelling, as INGC and SINGC (i.e., even not taking into account node features and using just the Grassmannian term) improve standard coarsening methods more or less across the board.\n\n**Weaknesses:**\n- I feel like the theoretical justification is somewhat limited, as, e.g., Proposition 3.4 assumes *perfectly* $k$-smooth features and a coarsening operator $C$ that *precisely* spans the column space of the top $k$ eigenvectors. Also, technical novelty is rather modest, e.g., Proposition 3.5 is a reduction to Thm 13 of [1].\n- The design and theoretical justifications for the method hinge on spectral smoothness of the node features, which real-world graphs might violate. The authors briefly discuss this in § E of the appendix. While they show that standard datasets like Cora, Citeseer etc. fulfill this approximately, I would assume that this would struggle with more heterophilic graphs where node features would also typically be of high frequency. It could strengthen the work to analyze more thoroughly when/how feature non-smoothness actually degrades the coarsening quality.\n- The presentation and clarity could be improved, as not all details were immediately clear to me. For example, it was not obvious to me from the text description what constraint one would project onto with PSGD in INGC. I am adding a few other (though minor) suggestions to improve the clarity under \"Questions\".\n\n[1] Andreas Loukas. *Graph Reduction with Spectral and Cut Guarantees.* JMLR 20 (2019) 1-42.", "was_revised": true, "final_justification": "The authors addressed most of my concerns, and with more visualizations and improved presentation I think this paper could be accepted. Yet, in my view, the feature smoothness assumption remains a notable limitation of the work as is, which is why I did not change my score.", "rebuttal": "Thank you for the time and effort you put into reviewing our paper. Your\ncomments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are:\n\n# *Theoretical Contribution*\nOur theoretical justification is composed of three components that together support the design of our method.\n\n(i) Proposition 3.2 provides a conceptual foundation for minimizing the IPE as a meaningful proxy for preserving graph structure during coarsening. While we acknowledge that the conditions under which this proposition holds—such as the rank constraints—are unrealistic in most practical settings, the result is not intended to suggest that exact Laplacian reconstruction is feasible. Rather, it serves to motivate the use of IPE minimization as a principled structural preservation objective.\n\n(ii) Proposition 3.4 shows that maximizing the Grassmann similarity between the coarsening operator and the subspace spanned by the top-$k$ Laplacian eigenvectors leads to IPE minimization for graph signals that satisfy the smoothness assumption. This observation directly motivates the second term in our objective function, which promotes subspace alignment on the Grassmann manifold. As a result, our method ensures low IPE not only for observed features but also for unseen smooth signals.\n\n(iii) Proposition 3.5 connects this subspace alignment to improvements in widely used graph coarsening metrics such as REE and DEE. Although the proof of Proposition 3.5 leverages Theorem 13 from [1], its combination with Proposition 3.4 provides a stronger theoretical insight: that minimizing IPE for general smooth signals leads to improved structural preservation. We believe this connection offers a principled geometric justification for the effectiveness of our approach.\n\n# *Smoothness Assumption*\n\nA central assumption in our work is that node features are smooth with respect to the graph structure, which is connected to the graph homophily assumption. This smoothness assumption underlies both our formulation and theoretical guarantees. For this reason, we do not include heterophilic datasets in our experimental evaluation.\n\nMore specifically, the second term in our objective relies on this smoothness assumption, as it encourages alignment with the subspace spanned by the low-frequency eigenvectors of the graph Laplacian. In heterophilic graphs, this assumption may not hold, and our theoretical results would no longer apply.\n\nOne potential direction for adapting our method to such settings is to modify the second term in the objective to project onto a different frequency range—e.g., using $\\boldsymbol{U}^{(k)}$ corresponding to mid- or high-frequency eigenvectors if prior knowledge about label-frequency alignment is available. However, such a modification would require a fundamentally different theoretical treatment, which we believe is beyond the scope of this work.\n\nFollowing your suggestion, we have emphasized this limitation and possible extensions in the Conclusion section of the revised manuscript.\n\nWe note that our empirical results indicate that our proposed methods remain competitive even when the smoothness assumption is only weakly satisfied. For example, Table 5 in Appendix E shows that when roughly 25\\% of a signal’s energy lies in the low-frequency spectrum—as in the Cora, Citeseer, and Co-CS datasets at $r = 0.05$—our method still matches state-of-the-art baselines.\n\nMoreover, Table 5 and our main experimental results (Table 2) illustrate that the advantage of SINGC becomes more pronounced as a larger fraction of signal energy resides in the low-frequency band. For instance, on the Pubmed dataset, where about 35\\% of the energy is concentrated in the relevant spectrum, SINGC surpasses all competing baselines, highlighting its advantage in such scenarios. Following the reviewer's comment, we clarified this property at the end of Section 4.\n\n# *Demonstrative Visualizations*\n\nWe thank the reviewer for the helpful suggestions regarding the visualizations.\n\nFollowing your comment, we added an additional visualization using a planar graph with 40 vertices, where all methods are applied. The clustering behavior of our method is indeed more visually clear in this example(unfortunately, we cannot share it here due to format constraints). The figures demonstrate the \"cluster-preserving\" properties of our approach—despite being guided by feature similarity rather than explicit structural information, our method produces clusters that closely resemble those generated by structure-based methods such as LVE and LVN, which do not use node features. This suggests that our method is capable of capturing meaningful structural patterns through the lens of feature similarity.\nWe also note that this property is further illustrated in Figure 2 in the Appendix B. \n\nIn addition, we will incorporate a new figure in Appendix B to visually demonstrate the preservation of node-feature relationships. Specifically, we compare two heatmaps:\n\\begin{align*}\nH = \\boldsymbol{X}^\\top \\boldsymbol{L} \\boldsymbol{X} \\quad and \\quad H_c = \\boldsymbol{X}_c^\\top \\boldsymbol{L}_c \\boldsymbol{X}_c,    \n\\end{align*}\n\nwhere the $(s,k)$-th entry of $H$ (and similarly for $H_c$) is given by:\n\n\\begin{align*}\nH[s,k]=\\boldsymbol{x}^{(s)\\top} \\boldsymbol{L} \\boldsymbol{x}^{(k)} = \\sum_{(i,j) \\in E} w_{ij} \\left( x^{(s)}(i) - x^{(s)}(j) \\right)\\left( x^{(k)}(i) - x^{(k)}(j) \\right),    \n\\end{align*}\n\nand $\\boldsymbol{x}^{(s)} = \\boldsymbol{X}[s,:]$ and $\\boldsymbol{x}^{(k)} = \\boldsymbol{X}[k,:]$ are the $s$-th and $k$-th node feature vectors, respectively.\n\nThis comparison—performed on our SBM experiment — visually demonstrates how our method preserves the original feature relationships. We note that, by the definition of the coarsening matrix $\\boldsymbol{P}$, the super-node features are formed as the average of their respective groups, further supporting the intuitive interpretation of feature aggregation under our framework. \n\n# *Additional clarification*\n 1.) In INGC (Algorithm 1), the projection step is performed every $c_{\\text{iter}}$ iterations—specifically, before each update of $\\boldsymbol{X}_c$. This is done using the Hardmax$(\\boldsymbol{C})$ operator, which projects $\\boldsymbol{C}$ onto the constraint set $\\mathcal{C}$ by enforcing a column-wise orthogonality constraint consistent with the Grassmann manifold structure. We agree that this design could be made clearer in the current algorithm description, and we will revise Algorithm~1 in the updated manuscript by inserting the projection step between Lines 8 and 9 and explicitly referencing the Hardmax operator.\n\n 2.) We chose to adopt the same regularization terms as FGC to ensure a fair and controlled comparison, allowing us to isolate and evaluate the contribution of our proposed IPE term and overall coarsening approach. This includes the connectivity regularization term, which is controlled by the hyperparameter $\\alpha$. Importantly, $\\alpha$ can be adjusted based on the desired application.\n\n3.)  Equation (10) is presented for two main reasons. The first, as you correctly noted, is to motivate Assumption 3.3 by illustrating that assuming signals lie in the span of the top $k$ Laplacian eigenvectors is standard in graph signal processing. \nSecond, we use this signal generation model to construct node features in datasets where such features are not available- specifically in the toy example, the Karate Club graph, and the Les Misérables network.\n\n4.) We use the term “functorial” to explain that our method operates from a function-based perspective. Following your suggestion, we will revise the wording to use “functional” instead, in order to avoid confusion and improve clarity. \n\n5.) Thank you for pointing out our formatting issues. We accept all your suggestions and will fix them in the revised version of the paper."}]

Author rebuttal:

Meta-review: The paper introduces a new loss for graph coarsening, the Inner Product Error (IPE), that aims to preserve node features during the coarsening process. The paper also develops two algorithms, INGC and SINGC, which minimize IPE while incorporating Grassmann alignment with Laplacian eigenvectors, showing consistent improvements in coarsening metrics and competitive node classification performance.

Reviewers particularly appreciated the theoretical motivation for the use of the IPE loss provided by the authors. At the same time, after the rebuttal, some concerns about the assumptions behind the theoretical analysis remain unresolved. In particular, the reviewers are concerned about the reliance on feature smoothness, which restricts applicability to homophilic graphs and leaves heterophilic settings unaddressed. Reviewers also noted that the spectral decomposition might be a bottleneck on larger graphs.

Overall, while not without limitations, the paper presents a technically sound and reasonably novel perspective on graph coarsening, with clear theoretical motivation and empirical support.
Decision: Accept (poster)