Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are:

Theoretical Contribution

Our theoretical justification is composed of three components that together support the design of our method.

(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.

(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.

(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.

Smoothness Assumption

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.

More 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.

One 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.

Following your suggestion, we have emphasized this limitation and possible extensions in the Conclusion section of the revised manuscript.

We 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.

Moreover, 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.

Demonstrative Visualizations

We thank the reviewer for the helpful suggestions regarding the visualizations.

Following 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. We also note that this property is further illustrated in Figure 2 in the Appendix B.

In addition, we will incorporate a new figure in Appendix B to visually demonstrate the preservation of node-feature relationships. Specifically, we compare two heatmaps:

$

H = \boldsymbol{X}^\top \boldsymbol{L} \boldsymbol{X} \quad and \quad H_c = \boldsymbol{X}_c^\top \boldsymbol{L}_c \boldsymbol{X}_c,

$

where the $(s,k)$-th entry of $H$ (and similarly for $H_c$) is given by:

$

H[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),

$

and $\boldsymbol{x}^{(s)} = \boldsymbol{X}[s,:]$ and $\boldsymbol{x}^{(k)} = \boldsymbol{X}[k,:]$ are the $s$-th and $k$-th node feature vectors, respectively.

This 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.

Additional clarification

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.

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.

3.) 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. Second, 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.

4.) 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.

5.) Thank you for pointing out our formatting issues. We accept all your suggestions and will fix them in the revised version of the paper.

Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are:

Theoretical Results Clarifications

The 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.

Importantly, 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:
"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 to hold is that the rank of $\boldsymbol{L}$ is at most $k$ (implying $n-k$ connected components).

Following 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.

The Role of the Grassmann Manifold

Both 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.

Furthermore, 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.

Optimization process

We thank the reviewer for raising this important point regarding the usage of the Grassmann manifold and projection steps in our gradient-based optimization.

You 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.

In 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.

For 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.

We thank the reviewer again for pointing this out and helping us improve the clarity and correctness of the manuscript.

Additional clarification

1.) 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$.

2.) 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.

We thank the reviewer for their follow-up and the opportunity to clarify the projection step in our method. We will revise our paper with the following detailed modifications:

1.) Clarification in the main text: We will expand the explanation about the projection step and the $`Hardmax`$ operator immediately after introducing projected gradient descent. The updated sentence in lines 182–183 in our paper will read:

“We optimize this objective by applying projected gradient descent [27] to estimate the matrix $\boldsymbol{C}$. Specifically, applying ordinary gradient descent steps could deviate from the feasible set $\mathcal{C}$ on the Grassmann manifold. Therefore, we use projected gradient descent to periodically project $\boldsymbol{C}$ back onto the Grassmann manifold after a fixed number of gradient descent steps using the operator $`Hardmax`(\boldsymbol{C})$. $`Hardmax`(\boldsymbol{C})$ applies a hard maximum at each row of $\boldsymbol{C}$, ensuring column-wise orthogonality, which coincides with the structural constraints of the Grassmann manifold.”

2.) Modification of Algorithm 1: We will revise Line 9 in Algorithm 1 to explicitly include the projection step using the $`Hardmax`$ operator. The revised line in the algorithm will include:

" 9. $\boldsymbol{C}_{t+1} = `Hardmax`(\boldsymbol{C}_t^*)$ , "

where $\boldsymbol{C}_t^*$ denotes the value of $\boldsymbol{C}$ after a fixed number of gradient steps.

3.) Clarification for SINGC in the main text: After introducing the SINGC algorithm and noting that it uses standard gradient descent, we will add the following clarification:

“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, as done for INGC. Therefore, for simplicity and efficiency, we chose to apply standard gradient descent throughout the iterations and perform the projection using $`Hardmax`(\boldsymbol{C})$ only at the end.”

The above note will be inserted at line 187 in our main text.

We hope this detailed explanation and revision plan address the reviewer’s concern. If there are any further questions, we would be happy to address them.

Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are:

Contribution and relation to FGC

Our 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.

The 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:

$

\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),

$

where $\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.

Proposition 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.

We 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.

Importantly, 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.

Datasets and baselines

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.

In 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.

We 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.

Following your comment, we conducted an additional search and identified a third recent method, MGC[3], that is compatible with our setting. A comparison between our methods and the additional baseline is detailed in the table below. We 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.

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.

More 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.

One 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.

Following your suggestion, we will add a discussion of this limitation and possible future extensions to the Conclusion section of the revised manuscript.

Scalability

We 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.

We 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.

Additional Clarification

Please 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.

[1] Dickens et al. "Graph coarsening via convolution matching for scalable graph neural network training." Companion Proceedings of the ACM Web Conference 2024.

[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).

[3] Halder et al. "Multi-Component Coarsened Graph Learning for Scaling Graph Machine Learning" Companion Proceedings of the ACM on Web Conference 2025.

[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.

Thank you for the time and effort you put into reviewing our paper. Your comments were very constructive and helped us improve the manuscript. Our responses to the main concerns you raised are:

Theoretical results clarifications

We 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}$.

Following 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.

Although 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)}$. In 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.

This 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.

Importantly, our formulation is based on Grassmann similarity rather than distance, which enables us to incorporate it directly into a differentiable loss term.

Method and run time clarification

The 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}$.

We 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.

It 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.

Other suggestions and Typos

Thank you for pointing out our formatting issues. We accept all your suggestions and will fix them in the revised version of the paper.