AH-UGC: $\underline{\text{A}}$daptive and $\underline{\text{H}}$eterogeneous-$\underline{\text{U}}$niversal $\underline{\text{G}}$raph $\underline{\text{C}}$oarsening

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.

Q1) The paper is not well-written. It is a little difficult to understand the paper clearly which including motivation and the key contributions of the paper.

Ans) We thank the reviewer for the feedback and fully appreciate the importance of clarity in presentation.

To provide context, the flow of the introduction begins by discussing the landscape of homogeneous vs. heterogeneous graphs, and the growing need for scalable solutions due to rapidly increasing graph sizes. We introduce graph coarsening as a practical remedy for scalability, but highlight two key limitations in existing methods: (1) lack of adaptive reduction, and (2) lack of support for heterogeneous graphs.

These points lead directly to the motivation for our work. From lines 54–67, we clearly enumerate our core contributions, which include:

• A unified, adaptive coarsening framework that uses Locality-Sensitive Hashing (LSH) and Consistent Hashing (CH) to enable multi-resolution, one-pass coarsening — eliminating the need to re-run the algorithm for different compression levels.
• A heterogeneity-aware extension that introduces type-isolated coarsening to handle multi-typed nodes and edges, enabling compression of heterogeneous graphs without mixing semantics or feature dimensions.
• In addition, our framework naturally supports streaming settings, heterophilic graphs, large-scale graphs, and dynamically growing structures, making AH-UGC a general-purpose and scalable solution across a wide range of graph modalities.

In the background section, we define key concepts related to graphs and heterogeneous graphs, and formulate two explicit goals tied to the aforementioned challenges. The Related Work section then analyzes the limitations of existing methods, with Figure 2 summarizing the capabilities of prior work and visually situating our contributions.

We hope this clarifies the structural intent and narrative of the paper. That said, we remain open to revising the introduction and background sections further to improve clarity and accessibility in the final version.

Q2) The overall structure of the paper appears to lack clarity. ......, it is unclear which specific conclusions the experimental results are intended to support.

Ans)

Clarifying Goal Coverage

1. Goal 1 (Adaptivity) is addressed in Section 3.1, with theoretical support from Theorem 3.1 and Lemma 1, and experimental validation in:
   • Table 1 (coarsening time for multiple ratios)
   • Table 2 (spectral property preservation)
   • Table 3 (node classification performance)
   • Figure 3 (probabilistic guarantees of projection proximity)
2. Goal 2 (Heterogeneous Graph Coarsening) is tackled in Section 3.2 via type-isolated coarsening, supported by:
   • Table 4 (node classification accuracy on heterogeneous datasets)
   • Figure 4 (supernode purity)
   • Figure 5 (accuracy vs. coarsening ratio under type-aware settings)

While Goal 2 occupies fewer lines in the paper, it includes a complete algorithm, theory, and empirical evaluation. If the reviewer feels additional elaboration would improve clarity, we are happy to revise and expand those sections accordingly.

Regarding Theorems and Lemma Interpretation

In Section 3.1, we use LSH and Consistent Hashing to project high-dimensional augmented features.

• Theorem 3.1 states that for two nodes x and y that are close in feature space, their hash projections h(x) and h(y) will also be close with high probability: $h(x) = floor((⟨r, x⟩ + b)/w), h(y) = floor((⟨r, y⟩ + b)/w)$
• Lemma 1 builds on this by showing that the probability of a distant third node z falling between h(x) and h(y) is very low. This supports our merging strategy by formally bounding the intrusion of dissimilar nodes in merge regions.

These theoretical results draw upon and generalize classical results from LSH theory (e.g., Datar et al., Indyk and Motwani). We’ve cited these at lines 56, 155, and 175 and will further clarify their role in Section 3.

Empirical Validation:

To support these theoretical claims, we conducted an ablation study where each node is merged with its $k^{th}$ rightmost neighbor (for k=1 to 5). The table below reports node classification accuracy on four benchmark datasets using the coarsened graph:

As seen, the performance degrades monotonically with increasing k, validating that:

• When k=1, we are most likely merging semantically similar nodes—consistent with Theorem 3.1.
• As k increases, we begin merging less similar nodes, and accuracy declines—supporting Lemma 1, which predicts that further neighbors are less likely to preserve semantic proximity in projection space.

Regarding Experimental Design and Its Purpose

Each experimental section was designed to directly validate the two goals:

Goal 1: Adaptive Coarsening Support

• Table 1: Validates efficiency and scalability across coarsening ratios.
• Table 2: Evaluates spectral preservation of coarsened graphs.
• Figure 3: Empirically validates Theorem 3.1’s claim that projected distances preserve local neighborhoods.
• Table 3: Shows practical utility by training on coarsened graphs and testing on original ones — a key validation of coarsening quality.

Goal 2: Heterogeneous Graph Coarsening

• Table 4: Demonstrates AH-UGC’s effectiveness on heterogeneous graphs compared to baselines.
• Figure 4: Shows how AH-UGC avoids impurity in supernodes by respecting node types.
• Figure 5: Analyzes how downstream accuracy behaves with increasing compression — clearly showing graceful degradation in AH-UGC vs. sudden collapse in others. This also highlights the trade-off between graph size reduction and information retention, which is dataset-dependent.

We hope this clarifies the logical flow from problem motivation to design, theory, and experiments.

Q3) What is the motivation and contributions of this paper?.......I hope it can help me understand the paper correctly.

Ans) Please refer to Answer 1)

Q4) In the problems formulation section, the goal 2 is to learn a coarsening matrix. But the learning details is not clear in section 3.2 (if I understand correctly that section 3.2 is for it).

Ans) Indeed, Goal 2 involves learning a coarsening matrix C that satisfies the structural and semantic constraints introduced in lines 111–112.

To handle heterogeneous graphs, we adopt a type-isolated approach (lines 213–218), where the graph is partitioned into subgraphs based on node types. On each type-specific subgraph, we apply the AH-UGC framework described earlier (Lines 152–174) to compute the respective coarsening matrix C, as formalized in Lines 192–200.

This results in a set of coarsening matrices — one per node type — which are then used to reconstruct the heterogeneous coarsened graph. To avoid redundancy, we kept the explanation in Section 3.2 concise, assuming familiarity with the shared logic described in Section 3.1.

We appreciate the reviewer pointing out that this connection could be made more explicit and will revise Section 3.2 to better highlight how coarsening matrices are computed per type and how they contribute to the final heterogeneous graph construction.

Q5) The proofs for the theorems are unclear. In Appendix D, it appears that the authors did not provide a proof for Theorem 3.1 and instead proved a theorem that seems unrelated.

Ans)

Theorem 3.1 (Projection Proximity for Similar Points)

Let $x, y \in \mathbb{R}^d$, and define the projection function:

$$h(x) = \sum_{j=1}^\ell r_j^\top x, \quad \text{where } r_j \sim \mathcal{N}(0, I_d) \text{ i.i.d.}$$

Then the difference $h(x) - h(y)$ follows:

$$h(x) - h(y) \sim \mathcal{N}(0, \ell \|x - y\|^2)$$

and for any $\varepsilon > 0$:

$$\Pr\left[ |h(x) - h(y)| \leq \varepsilon \right] = \operatorname{erf} \left( \frac{\varepsilon}{\sqrt{2\ell} \|x - y\|} \right)$$

Proof:

Let $z = x - y \in \mathbb{R}^d$. Then:

$$h(x) - h(y) = \sum_{j=1}^\ell r_j^\top x - \sum_{j=1}^\ell r_j^\top y = \sum_{j=1}^\ell r_j^\top (x - y) = \sum_{j=1}^\ell r_j^\top z$$

Each term $r_j^\top z$ is the projection of a standard Gaussian vector onto a fixed vector $z$, so:

$$r_j^\top z \sim \mathcal{N}(0, \|z\|^2) = \mathcal{N}(0, \|x - y\|^2)$$

Since the $r_j$ are independent, their sum is distributed as:

$$h(x) - h(y) \sim \mathcal{N}(0, \ell \|x - y\|^2)$$

Now consider the probability:

$$\Pr\left[ |h(x) - h(y)| \leq \varepsilon \right]$$

This is the cumulative probability within $\varepsilon$ of a zero-mean Gaussian with variance $\ell \|x - y\|^2$. Let $\sigma^2 = \ell \|x - y\|^2$, then:

$$\Pr\left[ |Z| \leq \varepsilon \right] = \operatorname{erf} \left( \frac{\varepsilon}{\sqrt{2\sigma^2}} \right) = \operatorname{erf} \left( \frac{\varepsilon}{\sqrt{2\ell} \|x - y\|} \right)$$

This completes the proof.

This result gives a formal probabilistic bound showing that closer points in the original feature space are also closer in projected space with high probability — a core property required for our merge strategy to maintain neighborhood consistency.

This theorem is closely aligned with prior LSH theory (e.g., Indyk & Motwani, Datar et al.), but adapted for summed projections, which is specific to our use of consistent hashing over LSH outputs.

Q6) What is the significance of Lemma 1? Its purpose and role within the paper are unclear.

Ans) Please see Regarding Theorems and Lemma Interpretation in Answer 2.

Q7). Which conclusions do the experiments support? This is somewhat unclear and leaves me a bit confused.

Ans) Please see Regarding Experimental Design and Its Purpose in Answer 2.

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper. Due to space limits, we refer to responses given to other reviewers for some similar concerns.

W1) Several experimental details are either unclear or missing.

Ans) The experimental setup and details are provided in Appendix E. The configurations and implementation details are summarized in Table 7, and when applicable, we cite existing works for architectures adopted directly (see lines 554–558).

That said, we appreciate the suggestion and are happy to add a brief discussion in Appendix E to summarize these details more explicitly, if recommended.

W2) Certain assumptions ....(e.g., Lemma 1) lack complete proofs.

Ans) Please see Answer 4.

W3) The paper proposes a limited novelty.

Ans) Please see Reviewer PQfo Weakness 1.

Q1) The heterophily factor in Line 147 .....

Ans) We clarify that node labels are not used during the coarsening process. The heterophily factor (line 147) is computed once beforehand using only the training nodes whose labels are available.

Q2) The current node merging ....

Ans) We appreciate this concern and clarify that AH-UGC is inherently structure-aware. The input to LSH is not raw node features but an augmented feature vector that blends node attributes with structural context — ensuring that nodes close in this joint space have similar hash scores.

Further, Theorem 3.1 and Lemma 1 provide formal guarantees: nodes that are close in the augmented space are projected close together with high probability, while distant nodes rarely fall between them, preserving locality during merging.

Our theoretical guarantees are supported by empirical results on spectral preservation (Table 2), node classification (Tables 3–4), and performance under aggressive coarsening (Figure 5). Additionally, AH-UGC is fast, adaptive, and general-purpose, scaling well to homophilic, heterophilic, heterogeneous, and streaming graphs, giving it an edge over other exisitng methods.

To further support Theorem 3.1 and Lemma 1, we conducted an ablation study. We kindly refer the reviewer to Reviewer RpVB – Answer 3.

Q3) Is the proposed coarsening approach specifically designed for node classification tasks..

Ans) AH-UGC is not limited to a specific downstream task. To assess its generality, we conducted experiments on link prediction

Following are the accuracies for link prediction

Q4) Lemma 1 is given without any proof ....

Ans) Thank you for pointing this out. Lemma 1 is adapted from classical results in randomized projections and order statistics—similar results have been derived in prior works on locality-sensitive hashing (e.g., [Datar et al., 2004], [Indyk & Motwani, 1998]). However, for completeness, we now provide a formal proof below

Lemma 1 (Separation Probability by Far Point)

Let $x, y, z \in \mathbb{R}^d$ with $\|x - y\| \ll \|x - z\|$. Then,

$$\Pr[h(x) < h(z) < h(y)] \leq \Phi\left( \frac{\|x - y\|}{\sqrt{\ell} \|x - z\|} \right)$$

Proof:
We analyze the chance that a far-away point z lies between two close points x and y in the projected order.

Let:

a = h(x) = \sum_j r_j^\top x, \quad b = h(y), \quad c = h(z)$$ Define the difference $d = h(y) - h(x) \sim \mathcal{N}(0, \ell \|x - y\|^2) \)$. Assume without loss of generality that h(x) < h(y). Then:

\Pr[h(x) < h(z) < h(y)] = \Pr[c - a \in (0, d)]

Since $h(z) - h(x) \sim \mathcal{N}(0, \ell \|x - z\|^2)$, we compute:

\Pr[0 < h(z) - h(x) < d] = \int_0^d \frac{1}{\sqrt{2\pi \ell |x - z|^2}} \exp\left( -\frac{t^2}{2\ell |x - z|^2} \right) dt \leq \Phi\left( \frac{d}{\sqrt{\ell} |x - z|} \right)

Taking expectation over $ d $, this gives the desired bound. **Q5)** Theoretical results very similar to Theorem 3.1 have been studied in the literature... **Ans)** We appreciate the reviewer’s suggestion and will add the proposed citation to appropriately acknowledge related prior work. **Q6)** For the runtime comparisons in Table 1, do the reported times represent averages across all coarsening ratios or cumulative totals? **Ans)** The runtimes reported in Table 1 represent cumulative totals across all coarsening ratios, reflecting the total cost incurred by each method to generate multiple coarsened graphs. **Q7)** In Tables 2 and 3, spectral preservation and classification ..... **Ans)** The 50% coarsening ratio was chosen arbitrarily as a representative midpoint for comparison across methods. The relation between coarsening ratio and accuracy can be seen from the below Table i.e. if we reduce the graph more and more, we start to see a slight decrease in accuracy values. Hence, there will always be a trade-off when it comes to the coarsening ratio and the quality of the reduced graph. |Ratio| Cite. | Cora | CS | DBLP | Pub. | Phy. | |-|-|-|-|-|-|-| | 30 | 67.21 | 80.60 | 93.02 | 76.16 | 85.65 | 96.12 | | 50 | 65.46 | 77.34 | 92.40 | 75.59 | 80.27 | 94.88 | | 70 | 61.91 | 75.16 | 88.29 | 74.83 | 78.15 | 92.43 | **Q8)** Are the reported results based on a single run .. **Ans)** Please see Reviewer PQfo Answer 2. **Q9)** What is the dimensionality of .. **Ans)** As stated in line 154, the projection matrix has shape (d × l). We set l = 1000 in our experiments. While LSH theory suggests that larger l improves generalization, we observed that performance and stability remain consistent for any l > 1000, making it a reliable default across datasets. **Q10)** While the paper claims that the proposed method can be applied to various graph types (e.g., streaming ... **Ans)** Thank you for the suggestion. While our main focus in AH-UGC is on adaptivity and heterogeneous graphs, we agree that supporting streaming graphs is equally important. Since AH-UGC builds upon the principles of UGC (which is designed for streaming), our framework naturally supports incremental coarsening without recomputation. To further support this claim, we have now conducted additional experiments simulating streaming graph settings. Below are the accuracy and coarsening time results across time intervals for 3 datasets: **Table: Accuracy and Coarsening Time for Streaming Graphs** | Interval (% of data) | Cora (Acc — Time) | Pubmed (Acc — Time) | Physics (Acc — Time) | |-|-|-|-| |0–20|65.01-0.21|81.74-0.35|93.67-4.82| |20–30|73.43-0.06|82.91-0.09|94.17-0.99| |30–40|74.40-0.05|83.24-0.17|93.73-0.94| |40–50|80.01-0.09|83.98-0.21|94.59-1.10| |50–60|80.60-0.12|84.31-0.24|94.75-1.33| |60–70|82.69-0.13|84.51-0.30|94.90-1.37| |70–80|86.37-0.15|85.12-0.34|95.31-1.57| |80–90|86.00-0.18|85.32-0.35|96.40-1.39| |90–100|86.19-0.10|85.49-0.38|96.12-2.17| This table presents the **accuracy (Acc)** and **coarsening time (Time)** of AH-UGC on 3 benchmark datasets under a **streaming graph setting**. We assume data arrives in **incremental batches** (10–20% of nodes at a time), and coarsening is applied at each time step without recomputing the entire graph. **Q11)** The caption of Table 1 refers to ratios, ..... **Ans)** We thank the reviewer for catching this. This is indeed a typographical error — the intended coarsening ratios range from 0.55 to 0.10, not from 55 to 10. We will correct the notation in the caption to clearly indicate that the ratios lie between 0 and 1 (e.g., 0.5 instead of 50%). ### Additional Comments **1)** Line 38 contains an incomplete sentence: it lacks a verb. **Ans)** We have modified the line 38 as: "Most existing graph reduction techniques, including pooling [16], sampling-based [17], condensation [18], and coarsening-based methods [4, 19, 20], aim to compress graph structures while preserving important properties." **2)** In Definition 2.2, the meaning of ... **Ans)** Thank you for pointing this out. In Definition 2.2, “target labels y(target_type)” refers to the labels associated with nodes of the target type, i.e., the specific node type we aim to classify. In heterogeneous graphs with multiple node types, it is common to perform supervised tasks (e.g., classification) only on one type of node — such as papers in DBLP or movies in IMDB. The term target_type reflects this focus. We will revise the definition to make this explanation explicit in the final version. **3)** Definitions 2.1 and 2.2 use inconsistent notation: in one case, the second entry denotes an adjacency matrix, and in another, it seems to represent the edge set. **Ans)** We appreciate the reviewer’s observation. The apparent inconsistency arises because Definition 2.2 explicitly introduces two standard representations for heterogeneous graphs: The entity-based form: $G(V, E, Φ, Ψ)$, where E is the edge list and $Φ, Ψ$ capture node and edge types. The type-based form: $G({X(node_{type})}, {A(edge_{type})}, {y(target_{type})})$, where edges are represented using adjacency matrices grouped by edge type. In contrast, Definition 2.1 (homogeneous graphs) uses the form G(V, A, X), where A is a single adjacency matrix. This is consistent with standard practice and reflects the structural differences between homogeneous and heterogeneous graphs. We will add a clarifying statement to explain that both notations are intentionally used based on the graph type and level of abstraction required. **4)** In the appendix, the proof .. **Ans)** Thank you for catching this oversight. We will revise the appendix to present the proof of Theorem 3.1 first, followed by Theorem 3.2.

Dear Reviewer uJX8,

Thank you again for taking the time to review our submission and for sharing your thoughtful feedback; it has been invaluable in helping us refine our work. We’ve done our best to address all the raised concerns carefully in the rebuttal, and we’re very open to further discussion.

Since we’re midway through the discussion phase, we just wanted to gently check in to see if there are any remaining questions or points of clarification we could help with while there’s still time. We’d be more than happy to elaborate on any aspect that might need further explanation.

And if you feel that your concerns have been adequately addressed, we would be sincerely grateful if you would consider updating your rating to reflect your current assessment of the work.

Best,

Authors

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.

Q1) Similarity to UGC The proposed method is highly similar to UGC. Like UGC, AH-UGC uses LSH, runs in linear time, and supports heterophilic graphs. The main differences lie in adaptivity and heterogeneous support, but the core framework remains largely the same.

Ans) While AH-UGC builds on UGC’s core idea of LSH-based coarsening, it introduces two key innovations that substantially extend its capabilities:

• Unlike UGC, which requires recomputing the entire coarsening process for each ratio (via bin-width tuning), AH-UGC introduces consistent hashing that enables multi-resolution coarsening in a single pass, with theoretical guarantees (Theorem 3.1, Lemma 1). This makes AH-UGC fundamentally adaptive and incrementally refinable — a feature UGC lacks.

• AH-UGC is the first to coarsen heterogeneous graphs while preserving type semantics. We introduce type-isolated coarsening and per-type compression strategies (Section 3.2), allowing us to handle varying feature dimensions and avoid type mixing — a critical limitation in UGC.

We also want to clarify that, empirically, AH-UGC is 4–5× faster than UGC when generating multiple coarsened graphs (Table 1), and achieves +20–30% absolute gain in classification accuracy on heterogeneous datasets (Table 4), demonstrating clear practical advantages.

Q2) Reliance on Random LSH The method depends on LSH, which is inherently randomized. It's unclear how robust the results are across different random seeds. Do the authors average over multiple runs or use a fixed seed? Additionally, is there potential to improve performance by learning the hashing function instead of using random projections?

Ans) We address LSH randomness by using multiple independent projectors, whose aggregation ensures robustness across seeds. The results across 4 different seeds are given below for both runtime and node classification accuracies:

Run time experiments (Across 4 seeds [123, 456, 789, 999])

Homophilic and Heterophilic datasets accuracy over multiple runs

Heterogenous accuracy experiments (5 trails with different model initialization)

Q3) Questionable Effectiveness of Coarsening The benefits of graph coarsening are unclear. As shown in Tables 3 and 4, applying a 30%-50% coarsening ratio often leads to a drop of over 10% in accuracy. Figure 5 shows that pushing the coarsening ratio beyond 40% causes a sharp decline in performance. If coarsening brings only modest efficiency gains but significantly harms model quality, it's worth questioning whether the tradeoff is worthwhile.

Ans) We agree that in a few datasets (1–2 cases), aggressive coarsening (e.g., >70%) results in noticeable accuracy drops. However, for most datasets, AH-UGC maintains high performance even at substantial compression — see Tables 3, 8, and 9.

Importantly, Figure 5 shows that AH-UGC degrades gradually, unlike other methods which suffer sharp drops due to supernode impurity. Our type-aware coarsening ensures semantic preservation even under strong compression (graph size reduced by 60%-70%).

Additionally, coarsening offers significant computational benefits (Table 1). In large-scale settings where training on the full graph is infeasible due to memory or time constraints, graph coarsening may be the only practical option.

Q4) Is it possible to replace random LSH with a learned hashing function? Would this improve performance?

Ans) Thank you for the question. The core goal of AH-UGC is to enable super-fast, training-free graph coarsening. Introducing a learned hash function would defeat this purpose by requiring training, thereby increasing computational cost and losing the key advantage of scalability.

While it is indeed feasible to learn task-specific hash functions, doing so shifts the method closer to condensation-based approaches like GCond, SFGC, or FGCond (see lines 127–129), which are more expensive and often model-dependent. Our design deliberately avoids this to maintain generality and speed.

Q5) How does graph coarsening impact other downstream tasks, such as graph-level prediction?

Ans) Graph coarsening is especially beneficial in scenarios involving large graphs, where reducing the graph size leads to substantial computational savings without sacrificing structural integrity. For graph-level prediction tasks such as graph classification, the situation is more nuanced. These datasets often consist of multiple small graphs, where the computational benefits of coarsening may be limited. In such settings, applying graph coarsening could potentially result in information loss, leading to degraded classification performance.

Importantly, we emphasize that coarsening is not restricted to node classification alone. We have also successfully employed AH-UGC for link prediction, demonstrating its versatility. The results for link prediction using coarsened graphs are included in the table below:

Accuracies for link prediction

Dear Reviewer PQfo,

Thank you again for taking the time to review our submission and for sharing your thoughtful feedback; it has been invaluable in helping us refine our work. We’ve done our best to address all the raised concerns carefully in the rebuttal, and we’re very open to further discussion.

Since we’re midway through the discussion phase, we just wanted to gently check in to see if there are any remaining questions or points of clarification we could help with while there’s still time. We’d be more than happy to elaborate on any aspect that might need further explanation.

And if you feel that your concerns have been adequately addressed, we would be sincerely grateful if you would consider updating your rating to reflect your current assessment of the work.

Best,

Authors

We thank the reviewer for their valuable comments and insights and for taking the time to go through our paper.

Q1) I am not sure about the degree of technical novelty in the paper, in particular regarding the use of consistent hashing.

Ans) While AH-UGC builds on UGC’s core idea of LSH-based coarsening, it introduces two key innovations that substantially extend its capabilities:

• Unlike UGC, which requires recomputing the entire coarsening process for each ratio (via bin-width tuning), AH-UGC introduces consistent hashing that enables multi-resolution coarsening in a single pass, with theoretical guarantees (Theorem 3.1, Lemma 1). This makes AH-UGC fundamentally adaptive and incrementally refinable — a feature UGC lacks.
• AH-UGC is the first to coarsen heterogeneous graphs while preserving type semantics. We introduce type-isolated coarsening and per-type compression strategies (Section 3.2), allowing us to handle varying feature dimensions and avoid type mixing — a critical limitation in UGC.

We also want to clarify that, empirically, AH-UGC is 4–5× faster than UGC when generating multiple coarsened graphs (Table 1), and achieves +20–30% absolute gain in classification accuracy on heterogeneous datasets (Table 4), demonstrating clear practical advantages.

Q2) For GNN node classification, the baselines (such as GCN) are too outdated.

Ans)

We would like to clarify that the primary goal of AH-UGC is not to introduce a new GNN model, but rather to introduce a more scalable, adaptive and heterogenous graph coarsening method.

The downstream node classification task is used as a proxy to evaluate the quality of the learned structure. To demonstrate that AH-UGC produces model-agnostic coarsened graph, we deliberately use widely adopted and well-understood GNN backbones for different graph modalities.

We would like to emphasize that we have carefully selected GNN models appropriate to different graph modalities:

• For homophilic graphs, we evaluate five widely-used GNNs: GCN, GIN, GAT, GraphSAGE, and APPNP. Please refer to Table 3 (main paper) and Table 8 in Appendix D for results.
• For heterophilic graphs, we consider another set of five GNNs designed to handle non-homophilic edge patterns: GCN-II, SGC, GPRGNN, MixHop, and GAT-JK. Please refer to Table 3 (main paper) and Table 9 in Appendix D for results.
• For heterogeneous graphs, we use three specialized models tailored for relational and multi-typed graph settings: HeteroSGC, HeteroGCN, and HeteroGCN2. Please refer to Table 4 (main paper).

In total, our evaluation spans 13 different GNN architectures, carefully chosen to reflect the diversity of real-world graphs across homophilic, heterophilic, and heterogeneous modalities. As suggested by reviewer, we have also incorporated graph transformer-based GNNs in an extended comparison table,

Q3) An ablation analysis would be required to compare the effect of LSH and CH.

Ans) We appreciate the reviewer’s suggestion. In our CH (Consistent Hashing) strategy, once the nodes are projected using LSH projectors, each node is instructed to merge with its k-th rightmost neighbor in the sorted projected space. We empirically analyze the effect of varying this k in terms of downstream node classification accuracy on coarsened graphs (90% coarsening rate).

The table below shows the classification accuracy when nodes are merged with their 1st to 5th rightmost neighbors. The results clearly indicate a monotonic decline in performance as k increases, validating that the quality of the coarsened graph deteriorates with increasing k:

This trend is consistent with our theoretical results:

• Theorem 3.1 establishes that two nodes that are close in the original feature space are projected close to each other with high probability.

• Lemma 1 further shows that the probability of a distant node being placed between two similar nodes in the projected space is very low.

Hence, when k=1, the merged node pairs are most likely to be semantically similar, resulting in the highest accuracy and best quality coarsened graph. As $k$ increases, we merge less similar nodes, degrading the representational quality of the graph.

Dear Reviewer,

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

Your support in this final phase would be immensely appreciated.

regards,

Authors

Dear Reviewer,

We thank you for the insightful comments on our work. We will incorporate your suggestions in our revision, and we are eagerly waiting for your feedback. We are especially grateful for your positive evaluation and for assigning a Borderline Accept rating, which reflects your recognition of the contributions of our work.

As the author-reviewer discussion phase is approaching its conclusion, we are reaching out to inquire if there are any remaining concerns or points that require clarification. Your feedback is crucial to ensure the completeness and quality of our work.

If you now feel confident in the completeness and quality of the revised submission, we would be grateful if you might consider revisiting your rating. Even a small adjustment at this stage could make a meaningful difference to the outcome, and your support in the final phase would be immensely appreciated

Warm Regards,

Authors