We sincerely thank the reviewer for their time, effort, and constructive comments. Below are our responses.

Comment 1: Preserve all eigenvalues and the smallest eigenvalues are not increased in theoretical & experimental results

Our method indeed increases the smallest eigenvalues. Here is a more detailed explanation:

1. Theoretical Results. In Theorem 4.1, we show that $(1 - \\epsilon) x^T L x \\leq x^T \\tilde{L} x \\leq (1 + \\epsilon) x^T L x$ holds conditional on $\\kappa = \\kappa(x)$, a function of the eigenvector $x$. Specifically, we choose the leading eigenvector $x_l$ (with the largest eigenvalue), and derive the sampling count $q \\ge \\frac{\\kappa(x_l)^2}{2\\epsilon^2} \\log 8$. This derivation focuses on preserving the larger eigenvalues and does not account for the smallest eigenvalues.

2. Experimental Results. Our experiments do show that the smallest eigenvalues are increased. However, due to the large range of eigenvalues, particularly the largest eigenvalue, observing this increment directly can be challenging. For instance, in Figure 2 (right), the spectral gap increases from nearly 0 to 0.5. Given that the largest eigenvalue is around 14, this makes the smallest eigenvalue changes difficult to observe. To make this clearer, we will include a zoom-in on the smallest eigenvalues for better visualization.

Comment 2: How to reduce Effective Resistance (ER) While Preserving Eigenvalues

Note that the total ER, $R_{\\text{tot}} = n \\sum_{i=2}^n \\frac{1}{\\lambda_i}$, is sensitive to smallest eigenvalues. For example, as shown in Figure 2 (right), the largest eigenvalue is approximately 14, contributing only $\\frac{1}{14}$ to $R_{\\text{tot}}$. On the other hand, the second smallest eigenvalue $\\lambda_2 = 0.05$ contributes significantly more ($\\frac{1}{\\lambda_2} = 20$). By increasing the smallest eigenvalue, for instance, to $\\lambda_2 = 0.5$, its contribution reduces to 2. Hence, by slightly increasing a few of the smallest eigenvalues, we can significantly reduce $R_{\\text{tot}}$, while maintaining a similar spectrum for others.

See visualization for this trade-off on a single graph: https://anonymous.4open.science/r/Submission3560_Rebuttal_for_Reviewer_EEAT/Fig.pdf

Comment 3: Ablation Study on $S_e$

We provide the following clarifications for the impact of $S_e$:

• Impact of $S _e$: The sampling probability is determined by $(1 + S_e)R_e$, where $S_e \\in [0,1]$ adds only a bias term to the factor 1, and $R _e$ remains the dominant factor. For example, consider two edges $a$ and $b$ with $S_a = 1$, $R_a = 0.5$ and $S _b = 0.5$, $R_b = 1$. We get: $(1+S_a)R_a = 2 \\times 0.5 = 1$ and $(1+S _b)R_b = 1.5 \\times 1 = 1.5$. Here, $R_e$ plays a more significant role than $S_e$. This is why our focus is on preserving the spectrum.

• Ablation Results: We conduct an ablation study to analyze the role of $S_e$ in graph-level and node classification tasks across both homophily and heterophily datasets. We find that the utilization of $S_e$ contributes less to performance in graph-level and homophily tasks. On the other hand, Delaunay Rewiring, which disregards the original graph topology, still performs well in certain datasets. This is due to Delaunay triangulation’s inherent properties that ensure the graph remains well-connected, which is crucial for graph-level tasks.

Here is the ablation study:

Comment 4: Writing suggestions on adding a None row to Table 3, restating the theorems & Relational-GNN

We thank the reviewer for the valuable suggestions and feedback!

1. We will explicitly mention that model used in Table 3 is the GCN models from Table 1. We also agree with adding a "None" row for clarity and restating the theorem statements in the appendix, which we believe will make it more reader-friendly. We will follow this suggestion in our future works as well. Thank you!
2. We will clarify that methods such as FOSR, GTR, or LASER leverage Relational-GNN to preserve graph structure, whereas our method has the advantage that it doesn’t require the use of Relational-GNN to achieve this. This distinction will help readers better understand the literature and our contributions.

Comment 5: Theoretical guarantees for entire algorithm

We acknowledge that while the sparsification algorithm provides provable spectral sparsifiers, the reverse process (densification) does not have the same theoretical guarantees. It performs well empirically. The number of edges added during densification is derived using Theorem 4.1 and the leading eigenvector by $q \\ge \\frac{\\kappa(x_l)^2}{2\\epsilon^2} \\log 8$, rather than being chosen heuristically.

We sincerely thank the reviewer for their time, effort, and constructive comments. Here are our responses.

Comment 1: Choices of Spectral Sparsification Algorithms

We appreciate the reviewer’s interest in the choice of spectral sparsification algorithms. It is important to note that our approach is designed to be algorithm-agnostic, meaning it does not rely on any particular sparsification method. However, we acknowledge that different algorithms may offer distinct advantages, and we discuss two such algorithms here as representative examples. Other similar algorithms can also be considered within our framework.

1. Algorithm 1: Algorithm 1 is designed to selectively increase the smaller eigenvalues while maintaining the larger ones. This is particularly important when the goal is to approximate the spectral properties of the graph. In Theorem 4.1, we show that for any vector $x$, the following inequality holds:

   $$(1 - \\epsilon) x^T L x \\leq x^T \\tilde{L} x \\leq (1 + \\epsilon) x^T L x$$

   This result is conditional on $\\kappa = \\kappa(x)$, which is a function of the eigenvector $x$. Specifically, we choose the leading eigenvector $x_l$ (corresponding to the largest eigenvalue) and derive the minimum required sampling count, $q \\geq \\frac{\\kappa(x_l)^2}{2\\epsilon^2} \\log 8$. This derivation focuses on ensuring that the larger eigenvalues are preserved, while the smaller eigenvalues are not explicitly accounted for in this process.

2. Algorithm 2: This algorithm assigns higher probabilities to edges with larger effective resistance, which is aligned with our objective of preserving important edges during the sparsification process. We believe this approach is well-suited to maintain key structural properties of the graph. The algorithm presented in [1] is one such effective candidate for implementing Algorithm 2, but we note that other algorithms with similar principles could also be used within the framework of our method.

Comment 2: Randomness in Sampling

Our theorems explicitly account for the randomness in the sampling process by providing probability lower bounds for the properties of the sampled graphs. Specifically, once the sampling count $q$ exceeds a certain threshold, we show that the generated graphs exhibit the desired spectral properties with high probability. These theoretical results ensure that, despite the inherent randomness in the sampling, the method remains reliable and effective.

To further substantiate the reliability of our approach, we conducted extensive empirical validation. As shown in Tables 1 and 2, our results are based on the average of 100 independent runs with different random seeds. This approach allows us to assess the variability and consistency of our algorithm. The results demonstrate that the confidence intervals of our algorithm are comparable to those of deterministic methods, which reinforces the robustness of our approach despite the use of random sampling.

We believe that these empirical and theoretical analyses collectively validate the effectiveness of our algorithm, providing confidence in its consistency and reliability.

We again thank the reviewer for the constructive feedback and valuable suggestions. Please do not hesitate to reach out if any further clarifications are needed.

References

[1] Spielman, Daniel A., and Shang-Hua Teng. "Spectral sparsification of graphs." SIAM Journal on Computing 40.4 (2011): 981-1025.

We sincerely thank the reviewer for their time, effort, and constructive comments. Below are our responses.

Comment 1 (Claims And Evidence 2, Theoretical Claims 2&3): Lack of probability bounds, impact of feature similarity in Theorem 4.2 & feature similarity term in ISS (Algorithm2)

• For $q= 32c^2n\\log n/\\epsilon^2$, the lower bound is $3/4$.
• Theorem 4.2 already accounts for feature similarity (Eq. 9 in Appendix).
• We don't prioritize feature similarity. For instance, given edges $a$ and $b$ with $S_a=1,R_a=0.5$ and $S_b=0.5,R_b=1$, we have sampling probabilities proportional to $(1+1)*0.5=1$ for $a$ and $(1+0.5)*1=1.5$ for $b$.

Comment 2 (Claims And Evidence 1 & Experimental Designs 2): Time complexity

• We discuss the time complexity of approximating ER in Sec. 4.3 as $\\mathcal{O}(m \\cdot \\text{poly}(\\log n)/\\delta^2)$, where $\\text{poly}(\\log n)$ is a polynomial in $\\log n$.
• If $|E'|$ is too large, $\\mathcal{O}(|E'| m)$ is not sublinear. However, this is not an issue in practice: in dense graphs, we don’t need large $|E'|$ to achieve good connectivity. In sparse graphs (small $m$), large $|E'|$ won’t significantly increase $|E'| m$. For Tables 1 and 2, we chose $|E'|$ from {5, 10, 15, 20, 25, 30}.

Comment 3 (Weaknesses 2, Suggestions 1 & Claims And Evidence 3): Measurement of reduction in over-squashing & quantitative measurements of spectrum similarity

• We measure the reduction in over-squashing by comparing pairwise ER between the original and rewired graphs in Fig. 3, which shows that ER values decrease post-rewiring.
• Smaller ER $R_{u,v}$ leads to larger $\\left\\| \\frac{\\partial h_u^{(r)}}{\\partial x_v} \\right\\|$(Black, Mitchell, et al.) the same metric as in Di Giovanni et al. Smaller $R_{u,v}$ also implies more and shorter paths.

See visualization: https://anonymous.4open.science/r/Submission3560_Rebuttal_for_Reviewer_geiv/Fig.pdf

Comment 4: Not discussed references

We mainly focused on rewiring-based work in the submission. Thanks for providing these excellent references! We will discuss them in the revision.

Q1: $\\alpha$ and $\\beta$ search spaces

Apologies for any confusion. The search spaces for $\\alpha$ and $\\beta$ in page 7 apply to Tables 1 and 2.

• $\\alpha$ in the Appendix: Table 8 analyzes $\\alpha$ sensitivity, not GOKU vs. baselines. For the 2000-node, 80k-edge graphs, a small search space for $\\alpha$ (5 to 30) is too limited for capturing meaningful difference. We use $0.05|E|, 0.1|E|, 0.15|E|$ for this reason.
• $\\beta$ values: For the main experiments, we use $\\{0.5, 0.6, 0.7, 0.8, 0.9, 1.0\\}$. For Table 8, we use $\\{0.5, 0.7,1.0\\}$ to avoid an overly large table while capturing key trends.

Q2: Sensitivity studies

We summarize the average accuracy across $18 = 3 \\times 6$ settings in Table 8:

• $\\alpha = (0.05|E|, 0.1|E|, 0.15|E|)$: 0.705, 0.728, 0.731
• $\\beta = (0.5, 0.7, 1.0)$: 0.730, 0.717, 0.705
  The variances of the average accuracies are relatively small.

Q3: USS

USS assigns low probabilities to important edges, often leading to their removal. However, we don't apply USS directly; instead, we reverse the process (densification) to reintroduce important edges, mitigating over-squashing.

Q4: Range of $\\beta$

To ensure efficiency, we constrain $\\beta \\leq 1$ to avoid denser output graphs than input. We set $\\beta \\geq 0.5$ empirically to prevent overly sparse graphs and reduce the hyperparameter search space.

Q5: ER Approximation error $\\delta$

The error bound $1 \\pm (1+(\\delta))\\epsilon$ can be derived by scaling $p_e$ as in Eq. 9 of the Appendix. Our experiments show minimal performance drops for $\\delta = 0.4$ compared to Table 1($\\delta=0.1$).

Q6: ER changes in Fig. 1

Sparsification is not meant to further improve connectivity after densification. ER increases when edges are removed (Rayleigh Monotonicity). There is a trade-off: as discussed in Page 8, sparsification provides two benefits: reducing edge density and retaining spectral similarity. Fig. 1 shows that sparsified graph has a more similar spectrum to the original graph.

Q7 & Q8: Newly added edges survival

While sparsification may remove newly added edges, they are assigned higher sampling probabilities during sparsification as they are topologically important. We computed the survival rate using the three datasets mentioned above. Over 90% of these edges were retained after sparsification.

Q9: reversing the order of DSR

We have not explored reversing the order of densification and sparsification. If we apply sparsification first, we have to densify a weighted graph, which is more diffcult. We leave this interesting question for future work.

We sincerely thank the reviewer for their time, effort, and constructive comments. Below are our responses.

Comment 1: Why $x^TLx$ as spectral similarity & advantages over degree distribution in SDRF

Summary: Our approach defines similarity via the Laplacian quadratic form, aligning with the graph spectral sparsification literature and covering broader structural properties beyond degree distribution.

Consider two graph $G$ and $\\tilde{G}$ with $(1-\\epsilon)x^TLx \\leq x^T\\tilde{L}x \\leq (1+\\epsilon)x^TLx$, we have:

1. Eigenvalue Similarity: The relationship $(1 - \\epsilon) \\lambda _i \\leq \\tilde{\\lambda} _i \\leq (1 + \\epsilon) \\lambda _i$ holds[1].
2. Graph Cut Similarity: The graph cut, $\text{cut}(G, S) = \\sum W(u, v)$, where $u \\in S$, $v \\in V - S$, and $W(u, v)$ is edge weight. Since $x^T L x = \\sum W(u, v) (x(u) - x(v))$, setting $x$ as indicator (1 inside $S$, 0 outside) gives $(1 - \\epsilon)\\text{cut}(G, S) \\leq \\text{cut}(\\tilde{G}, S) \\leq (1 + \\epsilon)\\text{cut}(G, S)$.
3. Degree Distribution Similarity: For node $u$, setting $x_u = 1$ and $x_v = 0$ for $v \\neq u$, we get $x^T L x = \\text{deg}(u)$. In other words, $(1-\\epsilon)\\text{deg}(G)(u) \\leq \\text{deg}(\\tilde{G})(u) \\leq (1+\\epsilon)\\text{deg}_G(u)$ for all $u \\in V$.
4. Eigenvector Similarity: By matrix perturbation theory, the eigenvectors $v _i$ and $\\tilde{v} _i$ of $L$ and $\\tilde{L}$ are close, with $\\| v _i - \\tilde{v} _i \\|_2 \\leq \\frac{\\| L - \\tilde{L} \\|_2}{|\\lambda _i - \\tilde{\\lambda} _i|}$.

See SDRF visualization: https://anonymous.4open.science/r/Submission3560_Rebuttal_for_Reviewer_1faH/Fig.pdf

Comment 2: Literature review regarding SDRF.

We appreciate your valuable suggestions and will revise the paper to rephrase them more accurately. Thank you!

1. SDRF also considers edge deletion: We will clarify it to avoid confusion. We acknowledge SDRF does involve both edge addition and deletion, as noted in our paper: "Curvature-based methods (citing SDRF) optimize connectivity by adding and removing edges." A key difference is that SDRF requires adding and removing nearly the same number of edges to preserve degree distribution. In contrast, our method allows a large edge reduction while keeping spectral similarity using weighted edges.
2. Edge density and over-smoothing. We agree that increased edge density does not necessarily lead to over-smoothing, as connection patterns also play a role.
3. Why stochastic manner to edit edges. SDRF uses a stochastic mechanism to select edges for addition, and our method extends this by also randomly selecting edges for deletion. We consider stochastic mechanism a means (not a goal). GOKU maintains spectral similarity even with a significant reduction in edge count ($0.5 \\leq \\beta \\leq 1$). This is made possible by spectral sparsification, which relies on stochastic sampling.

Comment 3: Spectrum and specific learning tasks & LASER performs well in some cases while not preserving spectrum well.

1. We summarize the average similarity of eigenvalue distributions between graphs from the same and different classes below. We use the fastdtw algorithm to compute distance between vectors of different sizes, and sim = $1/(0.01 + dis)$. It shows that graphs from the same class exhibit more similar spectra. Preserving spectrum could help classification tasks. Additionally, $x^TLx$ captures important graph anomaly signal, which helps anomaly detection [2].
2. Apart from spectrum, others such as connectivity also matter. While LASER distorts the spectrum more than GOKU, it also improves the spectral gap more. GOKU seeks to balance connectivity improvements with spectral similarity, as evidenced by the best overall performance.

Comment 4: Notations, $G$ and $G_d$ are confusing at times.

$G_d$ is not an input to either the densification or sparsification processes, but a candidate latent graph. $G$ represents the input graph fed into the rewiring process. In densification, given $G$, we aim to find a latent graph $G_l$ that maximizes the probability as $G_l = \\arg \\max P(\\phi(G_d) = G)$, where $G$ is the actual input.

Comment 5: Why two-stage approach.

The two-stage approach is simple and practical: in densification, when adding edges (Eq. 3, $\prod_{e \\in E} (1 - (1 - p_e)^q)^{w_e} \\prod_{e' \\in E'} ((1 - p_{e'})^q)^{\\bar{w}}$), we assume original edges $E$ are preserved, so we only need to find the $E'$ that maximizes the objective from the complement graph. However, allowing edge removal adds complexity, as we must also find an optimal subset from $E$ to delete.

[1] Spectral sparsification of graphs: theory and algorithms.

[2] Rethinking GNNs for Anomaly Detection.