Spectral Graph Coarsening Using Inner Product Preservation and the Grassmann Manifold

Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us significantly improve the manuscript. Our responses to the specific weaknesses and questions you raised and the modifications we made following them are:

Weakness 1 - Theorem 3 Implication

Theorem 3 establishes a connection between the second term in our optimization (Equation (12)) and bounds on two known coarsening metrics: REE and DEE. The maximum value of the second term $\text{tr}(U^{(k)} (U^{(k)})^\top C C^\top)$ is $k$, which occurs only when $U^{(k)}$ and $C$ represent the same point on the Grassmann manifold, i.e., $C = O U^{(k)}$ where $O$ is an orthogonal matrix.

In the theorem, $x_c$ is the coarsened vector derived from the coarsening operator $C$ , which satisfies

$

\text{tr}(U^{(k)} (U^{(k)})^\top C C^\top) = k - \epsilon,

$

where $\epsilon$ is the deviation from the optimal value of our second term. The theorem demonstrates that smaller $\epsilon$ leads to tighter bounds on REE and DEE, providing theoretical justification for including the second term in the coarsening objective.

Weakness 2 - Convergence Analysis

Following your comment, we added a convergence analysis in Appendix D.

In Appendix D, we added a new Figure (3) that provides an illustrative example of our methods' convergence rates on two datasets. The figure demonstrates a trade-off between convergence speed and final objective loss: higher learning rates lead to faster convergence but result in a higher final loss.

Weakness 3 - Complexity Analysis

Following your comment, we added a new complexity analysis section in Appendix C.

The table below (also included in the new appendix) summarizes the gradient expressions and time complexities of our methods and the baseline method FGC (the only optimization-based approach among our baselines). We observe that SINGC is the most efficient, while INGC remains competitive with FGC, as both FGC and INGC are governed by $O(n^2(k+p))$ , whereas SINGC is governed by $O(n^2k)$ .

Table 1. Comparison of gradient expressions and time complexities for FGC, INGC, and SINGC.

The total time complexity for node classification on the original graph is $O(n^2lp + nle$), where $n$ is the of nodes, $e$ number of edges, $p$ number of node feature and $l$ number of layers. Since the number of coarsened nodes $k$ is typically greater than the number of node features $p$, applying coarsening before a GCN is particularly beneficial for dense graphs where $e > n$. Coarsening reduces the graph size while keeping the dominant complexity term at $O(n^2)$.

Questions

1. If we plug in the relation $L_c=C^T L C$ and $X_c=C^\dagger X$ to the first expression of eqaution (11) (the IPE) we get:\

$

|X^TLX -X^T (C^\dagger)^T C^T L C (C^\dagger) X |_F,

$

the derivative with respect to $C$ does not have a closed-form expression. 2. The $l_{1,2}$ norm used in our paper follows the same definition as in [Kumar et al. (2023)], originally defined in [Ming et al. (2023)], as $\left\lvert C^T \right\rvert_{1,2} = \sum_{i=1}^n ( \sum_{j=1}^k\left\lvert C_{i, j} \right\rvert)^2$. To handle the non-smoothness of this expression around 0, we limit the elements of $C$ to be non-negative. Then we use the relation shown in [Kumar et al. (2023)], that this norm can be equivalently phrased as $\left\lvert C^T \right\rvert_{1,2} = \text{tr}(\boldsymbol{1}^\top C^\top C \boldsymbol{1})$ (see Equation (50) in their appendix), and we use the corresponding derivative. 3. The second term in Equation (11) minimizes the IPE for general unseen signals (node features) that satisfy Assumption 1 (smoothness on the graph). We notice that both the coarsening operator $C$ and the subspace of general smooth signals lie on the Grassmann manifold. Theorem 2 suggests that any equivalent representation of the same point on the Grassmann manifold as $U^{(k)}$ minimizes the IPE for any signal that satisfies the smoothness assumption. Therefore, the second term in our objective maximizes the geodesic similarity (defined in Equation (4)) between $C$ and $U^{(k)}$. Theorem 3 connects the optimization of this term to minimizing common graph coarsening metrics such as REE and DEE. 4. The expression $X^\top X$ measures the standard inner product between two signals without considering the structure of the grid on which they are defined, i.e.,

$

\langle x, y \rangle = x^\top y = \sum_{i=1}^n x(i)y(i).

$

Our proposed IPE incorporates the graph structure on which the signals are defined and quantifies their similarity with respect to this structure:

$

x^\top L y = \sum_{(i,j) \in E} w_{ij} (x(i) - x(j))(y(i) - y(j)),
$

where $w_{ij}$ are edge weights, and $x(i), y(i)$ are the values of the features at node $i$ . Thus, the IPE captures both node feature and graph structure information, making it particularly beneficial for tasks where both are of interest. Following your question we explicitly added this relation when defining $\langle x, y \rangle_L$ and clarified its contribution throughout the paper.

Weakness 4 - Ablation and Hyperparameter study

In response to your comments, we have added an ablation and hyperparameter study in a new Appendix E.

In appendix E, we display a new Figure (4) that presents the contribution of each parameter in our methods. It illustrates the sensitivity of each parameter and evaluates the impact of deviations from optimal values on various metrics.

The figure shows that varying $\alpha$ results in minimal sensitivity across metrics, except for IPE, where changes up to an order of magnitude still yield similar results. It also demonstrates that our methods are more sensitive to $\lambda$ compared to the other parameters, highlighting $\lambda$'s critical role in performance.

The Table below presents a new ablation study on the parameter $\beta$ - that govern the second term in our objective - for the node classification task across various datasets and coarsening ratios $r$ (shown also in the new Appendix E). The comparison includes three methods: INGC with $\beta = 0$ (ignoring the term $\text{tr}(U^{(k)} (U^{(k)})^\top C C^\top)$ for minimizing IPE for general smooth signals), INGC with the optimal $\beta$ , 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 the second-best results underlined. For each metric, other hyperparameters are set to their optimal values. The results demonstrate the importance of balancing the two complementary approaches to minimizing IPE. INGC with $\beta = 0$ generally underperforms compared to the other methods.

Table 2. Ablation study of the parameter $\beta$ 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 $\beta = 0$ , the fourth column corresponds to the optimal $\beta$ value, and the fifth column shows the results of SINGC. 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.

Follow-up Questions

1. You are correct. The derivative of this expression does not have a closed-form solution but it may be differentiable. A key condition for $\text{pinv}(C)$ to be differentiable is that the rank of $C$ remains constant within an open neighborhood around $C$. This condition is not explicitly addressed as part of our optimization process. We thank the reviewer for this clarification and have revised our paper to reflect this distinction more accurately.

2. Following your comment, we conducted an additional experiment comparing the performance of our suggested IPE with the standard inner product:

$

|X^\top X - X_c^\top X_c|_F^2 = |X^\top X - X^\top \text{pinv}(C)^\top \text{pinv}(C) X|_F^2.

$

Since the derivative of this expression with respect to $C$ does not have a closed-form solution, we relaxed $\text{pinv}(C)$ to $C^\top$ to avoid using derivative numerical approximations, which could result in an unfair comparison between the methods.

We conducted experiments on two medium-sized datasets: Cora and Citeseer. The table below summarizes the performance of the two approaches across different datasets and coarsening ratios ( $r = \frac{k}{n} = 0.7, 0.5,$ and $0.3$ ). The first approach uses our proposed method (INGC) with $\beta = 0$ (i.e., using only the IPE), and the second approach that uses the standard inner product as suggested by the reviewer(SIP).

We observe that incorporating the graph structure (L) into the inner product definition is beneficial in most cases.

3. We determined the optimal hyperparameters in all our experiments through a grid search. This grid search can always be applied to optimize a specific graph coarsening metric, as evaluating the score only requires the original and coarsened graphs. We observe in Tables 7, 8, and 9 in the Appendix that the parameter values leading good performance in node classification tasks often align with low values of REE and INP. Therefore, we recommend that practitioners first optimize the hyperparameters by minimizing REE and INP, and then apply those parameters to their application.

Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us significantly improve the manuscript. Our responses to the specific weaknesses and questions you raised and the modifications we made following them are:

Weakness 1 - IPE Importance

The practical importance of the IPE lies in its ability to capture both node feature information and graph structure, making it particularly beneficial for tasks that rely on both, such as node classification and link prediction.

Following your comment, we added clarifications throughout the paper, highlighting its utility. In the background section, we introduced the relation

$

x^\top L y = \sum_{(i,j) \in E} w_{ij} (x(i) - x(j))(y(i) - y(j)),
$

which provides intuition on how the inner product captures relationships between functions with respect to the graph structure.

We then clarified the contribution of our theoretical guarantees. Theorem 1 explains how preserving these relationships also preserves the graph structure, while Theorem 3 demonstrates that minimizing IPE for general smooth signals ensures the preservation of important graph properties, such as dominant eigenvalues and signal norms.

Finally, the motivation for using IPE is strengthened by our empirical results, where we show that it outperforms current state-of-the-art coarsening methods in common graph coarsening benchmarks and demonstrates its applicability for more efficient GNN training.

Weakness 2 - Smoothness Assumption

We wish to clarify two key points. First, please note that the signal smoothness assumption pertains to the graph structure, meaning that connected nodes tend to have similar features. Second, even when node features are not available, Theorem 2 demonstrates that maximizing the second term in our objective (which does not depend on the given node features) minimizes the IPE for any signal (including unseen ones) that satisfies the smoothness assumption. Additionally, our proposed algorithm termed SINGC does not rely on node features during the coarsening optimization.

In response to your comment, we have added a clarification following the presentation of our proposed approach to better highlight the distinction between the two terms and the contributions of our work.

Weakness 3 - Main Contribution

We briefly review the primary contribution of our work: we propose a new graph coarsening framework that focuses on preserving the inner products of signals with respect to the graph structure. This ensures that both node feature relationships and graph structural properties are maintained during coarsening, which is crucial for downstream graph learning tasks. By recognizing that the coarsening operator and the subspace of smooth signals can both be represented as points on the Grassmann manifold, we efficiently generalize this objective to any signal satisfying a smoothness assumption, enabling us to coarsen a graph while preserving mutual information between node features, even when the node feature are unknown. We provide theoretical justification for our approach, link it to established coarsening metrics, and demonstrate its superior performance through extensive experiments on graph coarsening benchmarks.

Weakness 4 - General Questions

1. We thank the reviewer for spotting this confusion in our notation. The first condition relates to the columns of $C$. Each column should have at least one non-zero element, denoted by $\left\lvert C_{\text{:}, i} \right\rvert_0 \geq 1$. The second condition relates to the rows of $C$. Every row of $C$ should have exactly one non-zero element. Following your comment, in the revised paper we changed the notation of this condition to $\left\lvert C_{i,\text{:}} \right\rvert_0= 1$ and specified after equation (10) that $C_{i,:}$ denotes the $i$-th row of C.

2. Please note that Theorem 1 is not the same as Proposition 2.4 in Loucas 2019. Proposition 2.4 states that for any vector $x = \Pi x$ , the norm of the signal is preserved after coarsening and lifting:

$

x_c^\top L x_c = x^\top \Pi L \Pi x = x^\top L x.

$

However, it does not directly imply that the full graph structure can be reconstructed after lifting. In contrast, Theorem 1 states that if the inner products between all signals are preserved, then if the of the original Laplacian is less than $(n-k)$, the original Laplacian can be fully reconstructed. A key difference is a necessary condition that the rank of $L$ is less than k (the number of super-nodes), which is not part of Proposition 2.4.

3. Thank you for this correction, in the revised paper we added a square in all relevant equations.

4. The second term in Equation (11) minimizes the IPE for general unseen signals (node features) that satisfy Assumption 1 (smoothness on the graph). Please note that both the coarsening operator $C$ and the subspace of general smooth signals lie on the Grassmann manifold. Theorem 2 suggests that any equivalent representation of the same point on the Grassmann manifold as $U^{(k)}$ minimizes the IPE for any signal that satisfies the smoothness assumption. Therefore, the second term in our objective maximizes the geodesic similarity (defined in Equation (4)) between $C$ and $U^{(k)}$. Theorem 3 connects the optimization of our second term to minimizing common graph coarsening metrics such as REE and DEE. Satisfying our first term for any two node features is a strong condition, but our second term allows this to be relaxed by focusing only on node features that satisfy a common smoothness assumption.

5. The $l_{1,2}$ norm used in our paper follows the same definition as in Kumar et al. (2023), originally defined in Ming et al. (2019), as $\left\lvert C^T \right\rvert_{1,2} = \sum_{i=1}^n ( \sum_{j=1}^k\left\lvert C_{i, j} \right\rvert)^2$. Ming et al. (2019) demonstrated that this regularization promotes sparsity within groups (the rows of $C$, in our case). Consistent with Kumar et al. (2023), we expressed this norm equivalently as $\left\lvert C^T \right\rvert_{1,2} = \text{tr}(\boldsymbol{1}^\top C^\top C \boldsymbol{1})$ (see Equation (50) in their appendix), and our derivative formula is derived accordingly. You are correct that for this equivalence to hold, the elements of $C$ must be non-negative; otherwise, the derivative would also need to include $\text{sign}(C)$ . This assumption is inferred from the condition $C \in \mathcal{C}$, where $\mathcal{C}$ is the set of valid coarsening matrices. This was unintentionally omitted from equation (12) in the original manuscript. Following your comment, we added this assumption as a constraint in the optimization problem including a full definition of the $l_{1,2}$ norm, and clarified the derivation of the derivative in the revised paper.

6. Thank you for this comment. We made sure $\kappa$ is defined at the end of the Theorem.

7. After we train the GCN on the coarsened graph using the coarsened Laplacian $L_c$, features matrix $X_c$, and coarsened labels $Y_c$, we apply the weights of the learned network to the full graph Laplacian and features matrix, i.e., $\hat{y}=GCN(L,X)$, and evaluate its performance based on the RMSE. Following your comment, we added this clarification in the revised paper.

8. Fixed. Thank you.

Questions

1. This is a typo. We meant IPE (as defined in definition 5) and fixed it. Thank you.
2. The assumption in Theorem 1 aids in mathematical tractability and rigorous derivation. In practice, most graphs are connected or have only a few components. However, we show that even when this criterion is not met (as in all of our datasets), our method still achieves the lowest reconstruction error (RE) compared to other methods, highlighting its broader applicability.
3. We wish to clarify our choice of coarsening rates. In Table 2, small coarsening ratios were used to support effective downscale for GNNs, and the specific ratio values were chosen to align with the baseline experimental setups for fair comparison. In Table 1, which involves small and medium-sized datasets, using the same coarsening ratios as in Table 2 (e.g., 0.1 or 0.05) would result in overly small coarsened graphs, losing meaningful structure.

Weakness 3 and 4 - Ablation and Hyperparameter study

We selected the hyperparameters in our experiments through a grid search. In response to your comments, we have added an ablation and hyperparameter study in a new Appendix E.

In appendix E, we display a new Figure (4) that presents the contribution of each parameter in our methods. It illustrates the sensitivity of each parameter and evaluates the impact of deviations from optimal values on various metrics.

The figure shows that varying $\alpha$ results in minimal sensitivity across metrics, except for IPE, where changes up to an order of magnitude still yield similar results. It also demonstrates that our methods are more sensitive to $\lambda$ compared to the other parameters, highlighting $\lambda$'s critical role in performance.

The Table below presents a new ablation study on the parameter $\beta$ - that govern the second term in our objective - for the node classification task across various datasets and coarsening ratios $r$ (shown also in the new Appendix E). The comparison includes three methods: INGC with $\beta = 0$ (ignoring the term $\text{tr}(U^{(k)} (U^{(k)})^\top C C^\top)$ for minimizing IPE for general smooth signals), INGC with the optimal $\beta$ , 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 the second-best results underlined. For each metric, other hyperparameters are set to their optimal values. The results demonstrate the importance of balancing the two complementary approaches to minimizing IPE. INGC with $\beta = 0$ generally underperforms compared to the other methods.

Table 2. Ablation study of the parameter $\beta$ 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 $\beta = 0$ , the fourth column corresponds to the optimal $\beta$ value, and the fifth column shows the results of SINGC. 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.

Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us significantly improve the manuscript. Our responses to the specific weaknesses and questions you raised and the modifications we made following them are:

Weakness 1 - Comparison to Other Methods

In our experimental setting, we compared our results to methods considered state-of-the-art in their respective contexts. LVN and LVE are known to perform best for evaluating graph coarsening metrics that measure how well graph structural properties are preserved (e.g., REE and RE). FGC is widely regarded as the leading method for metrics that also consider node features, as it incorporates node features into the coarsening process. Thus, Section 4.2 focused on comparing our performance against these methods across various graph metrics.

In Section 4.3, we repeated the experimental setting used in FGC (2023) and SCAL (2021) and reported the results of only the top-performing method in each of these settings from those papers. This means that our method also outperforms the other multigrid coarsening approaches, such as those proposed by Livne et al. (2012) [1] and Ron et al. (2011) [2], as reported in SCAL (2021).

[1] Oren E Livne and Achi Brandt. Lean algebraic multigrid (lamg): Fast graph laplacian linear solver. SIAM Journal on Scientific Computing, 34(4):B499–B522, 2012.

[2] Dorit Ron, Ilya Safro, and Achi Brandt. Relaxation-based coarsening and multiscale graph organization. Multiscale Modeling and Simulation, 9(1):407–423, 2011.

Weakness 2 - Time Complexity

Following your comment, we added a new complexity analysis section in Appendix C.

The table below (also included in the new appendix) summarizes the gradient expressions and time complexities of our methods and the baseline method FGC (the only optimization-based approach among our baselines). We observe that SINGC is the most efficient, while INGC remains competitive with FGC, as both FGC and INGC are governed by $O(n^2(k+p))$ , whereas SINGC is governed by $O(n^2k)$ .

Table 1. Comparison of gradient expressions and time complexities for FGC, INGC, and SINGC.

Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us significantly improve the manuscript. Our responses to the specific weaknesses and questions you raised and the modifications we made following them are:

Weakness 1 - Dot Product Definition

You are correct that $x^\top L x = 0$ for any constant vector $x$ , and thus $x^\top L x$ does not induce a norm but rather a semi-norm. In response to your comment, we have added a clarification in the revised paper that $x^\top L y$ can be viewed as an inner product on the subspace of $\mathbb{R}^n$ orthogonal to the constant vector $\mathbf{1}$ , following several prior works on spectral graph theory (e.g., [Von Luxburg, 2007]).

Additionally, we clarified that the inner product indeed captures signal smoothness wrt the graph by adding the explicit expression:

$

x^\top L y = \sum_{(i,j) \in E} w_{ij} (x(i) - x(j))(y(i) - y(j)),

$

where $w_{ij}$ are edge weights and $x(i), y(i)$ are the values of the signals at node $i$ . This form measures the variation and alignment of $x$ and $y$ across connected nodes, reflecting their relationship with the graph structure.

Weakness 2a - Complexity Analysis

Following your comment, we added a new complexity analysis section in Appendix C.

The table below (also included in the new appendix) summarizes the gradient expressions and time complexities of our methods and the baseline method FGC (the only optimization-based approach among our baselines). We observe that SINGC is the most efficient, while INGC remains competitive with FGC, as both FGC and INGC are governed by $O(n^2(k+p))$ , whereas SINGC is governed by $O(n^2k)$ .

Table 1. Comparison of gradient expressions and time complexities for FGC, INGC, and SINGC.

The total time complexity for node classification on the original graph is $O(n^2lp + nle$), where $n$ is the of nodes, $e$ number of edges, $p$ number of node feature and $l$ number of layers. Since the number of coarsened nodes $k$ is typically greater than the number of node features $p$, applying coarsening before a GCN is particularly beneficial for dense graphs where $e > n$. Coarsening reduces the graph size while keeping the dominant complexity term at $O(n^2)$.

Weakness 2b - Convergence Analysis

Following your comment, we added a convergence analysis in Appendix D.

In Appendix D, we added a new Figure (3) that provides an illustrative example of our methods' convergence rates on two datasets. The figure demonstrates a trade-off between convergence speed and final objective loss: higher learning rates lead to faster convergence but result in a higher final loss.

Questions:

1. The trace $\text{tr}(X^\top L X)$ measures the smoothness of individual signals with respect to the graph but neglects the relationships between different signals. Our approach considers the full term $\|X^\top L X\|_F$, which incorporates both the smoothness of individual signals and their relationships with respect to the graph structure. This ensures the preservation of both node-level information and critical structural properties, as validated by our empirical results and theoretical analysis.

   Our approach can be considered a generalization of FGC, as it focuses not only on signal norms ($\langle x, x \rangle_L$) but also on the cross-relations.

2. Fixed. Thank you.

3. Fixed. Thank you.

4. $\mathcal{C}$ is the group of valid coarsening matrices as presented in equation (10). Following this comment, we added a clarification after presenting equation (11) in the updated manuscript.

5. Fixed. Thank you.