CurvGAD: Leveraging Curvature for Enhanced Graph Anomaly Detection

We sincerely thank the reviewer for their insightful feedback, valuable assessment and constructive suggestions.

[Q1] Scalability and Complexity

Thank you for this important point. We provide a detailed time complexity (and scalability) analysis in Appendix C. Specifically:

1. Appendix C.1.2 explains our linear-time approximation of Ollivier-Ricci Curvature (ORC), which scales as $\mathcal{O}(|\mathcal{E}|)$ and is fully parallelizable.

Summary of Preprocessing Complexity (Appendix C.1.4)

• Ollivier-Ricci Curvature (ORC): $\mathcal{O}(|\mathcal{E}|)$ (linear time)
• Ricci Flow Regularization: $\mathcal{O}(|\mathcal{E}|)$ (empirically bounded by a constant number of iterations)
• Total Preprocessing Complexity: $\mathcal{O}(|\mathcal{E}|)$ (parallelizable and scalable)

2. Appendix C.2 presents runtime comparisons (Table 5, Figure 4), showing CurvGAD’s efficiency across diverse datasets. Figure 4 lays down the average runtime per epoch comparision of CurvGAD with other baselines.

The linear time approximation of ORC ensures that our model is scalable to million-scale graphs. Despite using multiple curvature manifolds and filters, CurvGAD achieves runtime comparable to or better than baselines like BGNN, XGBOD, and KGCN. For example, on Reddit, CurvGAD is faster than KGCN and significantly more efficient than XGBOD, while being far more expressive. Thus, our design ensures both scalability and geometric fidelity for large graphs.

[Q2] Robustness to adversarial perturbations?

We appreciate this insightful suggestion. Robustness to adversarial attacks is a valuable direction—especially for anomaly detection—but it lies beyond the current scope of this work. CurvGAD focuses on the role of mixed-curvature geometry in identifying anomalies. Our results establish curvature as a fundamental tool for GAD and pave the way for future advancements in geometry-aware graph learning while of- fering new avenues for exploring geometric anomalies in topologically complex networks. We are actively exploring robustness extensions in future work.

Other suggestions

• Typos & Visuals: Thank you for pointing these out. We will fix the typo (“compliment” → “complement” in Section 5.5(e)) and enhance Figures 1 & 3 with clearer legends and annotations in the camera-ready version.
• Baseline Hyperparameters: We acknowledge this concern and will include detailed hyperparameter settings for all baselines in the camera-ready version and code repository. Due to the rebuttal length constraint, these could not be included here.

We sincerely thank the reviewer for their detailed and thoughtful comments. We deeply value the opportunity to clarify our contributions and improve our work based on your feedback.

[Q1] Why curvature?

The core aim of our work is to learn node representations on a non-Euclidean manifold and study how the underlying geometry—characterized by curvature—reveals anomalies. While several geometric metrics exist, curvature helps in quantifying the intrinsic structural irregularities in graphs (our hypothesis for this paper).

Unlike static scalar descriptors (e.g., clustering coefficients or local assortativity), curvature allows us to reason about how node-pair relations behave in a global geometric context, making it suitable for tasks like anomaly detection that are sensitive to subtle perturbations in local structure. Furthermore, graph regularization via Ricci Flow allows us to isolate non-geometric anomalies for reconstruction. If there are specific alternative geometric properties you had in mind, we would be eager to understand and consider them in future work.

[Q2, Q4] Homophiliy (Heterophily) and Low-pass (High-pass) Filtering

We appreciate this clarification and fully agree that homophily and low-pass filtering are not the same concept. We apologize if this was inadvertently conflated in the phrasing. Our intention was not to equate them, but to note that low-pass filters are particularly effective in capturing homophilic signals, which tend to lie in the low-frequency eigenspectrum of the graph Laplacian (and high-pass for heterophilic).

To support our statement, we sincerely refer to the source cited by the reviewer [1], which states:

• “High-frequency signal, which can catch the neighborhood dissimilarity, is found to be helpful for heterophily.”
• “It is commonly stated that low-pass filter mainly captures the smooth components of the signals (neighborhood similarity), while high-pass filter mainly extracts the non-smooth ones (neighborhood dissimilarity).”

Thus, we only argue that low-pass filters assist with homophilic patterns and high-pass filters help capture heterophilic patterns, which aligns with the aforementioned literature. We will revise our phrasing in the CR version to avoid ambiguity.

[1] The heterophilic graph learning handbook. 2024 Jul 12.

[Q3] Novelty of Equations 2-4

Yes, Equations (2–5) are indeed novel contributions of our work. They extend Chebyshev spectral filtering to the mixed-curvature Riemannian setting, and define the filterbank using the $\kappa$-stereographic model. Specifically:

• Eq. (2): Projects Euclidean features to the manifold.
• Eq. (3–4): Define manifold-aware Chebyshev filtering and aggregation. They extend the typical Chebyshev recurrence to the mixed-curvature spaces.

These gyrovector operations (Mobius addition, $\kappa-$matrix multiplication) are standard in non-Euclidean geometry and are described in Appendix B.2. They help us extend the Euclidean operations to the product manifold.

[Q5] Heterogeneous or heterophilic?

This is correct and we apologize for the typo (and therefore, the unintended abuse of terminology). We indeed meant "heterophilic" and "homophilic", not "homogeneous" or "heterogeneous" in the sentence mentioned. We will rectify in the CR version.

[Q6] Additional Experimentation on Heterophilic Networks

Thank you for this valuable suggestion. We initially evaluated CurvGAD on a diverse mix of homophilic and heterophilic benchmarks:

• Homophilic: Reddit, Weibo, Amazon, YelpChi, Tolokers, Questions
• Heterophilic: T-Finance, Elliptic, DGraph, T-Social

Based on the feedback we conducted additional experiments on heterophilic datasets from [1]:

• Malignant: Cornell, Texas
• Ambiguous: snap-patents, twitch-gamers

As these datasets lack organic anomaly labels, we follow a common setup by treating the minority class as anomalous. We compare CurvGAD against strong (select) baselines (due to spatial and time constraints): GCN, ADAGAD, KGCN, and BWGNN.

AUROC (%) Results on more Heterophilic Datasets

These results demonstrate CurvGAD’s generalization to heterophilic graphs. We will include full analysis (all baselines) in the CR version.

We sincerely thank the reviewer for their positive assessment and thoughtful questions. Please find our detailed responses below:

[Q1] Could the authors provide visualizations or quantitative results showing the curvature of the regularized graph?

We thank the reviewer for pointing this out. We would like to clarify that Figure 3 in the main paper visualizes the Karate Club graph before and after Ricci Flow regularization. The edge curvatures are color-coded—red/blue indicating positive/negative curvature before the flow, and grey edges (≈0 curvature) after the flow. This demonstrates that Ricci Flow effectively neutralizes geometric irregularities, enabling subsequent modules to focus on non-geometric anomalies. We shall add similar visualisations (and their corresponding curvature values) for other example graphs in the camera ready version.

[Q2] Which specific components of the model contribute to its effectiveness in such cases? (Homophily)

We appreciate this insightful question. CurvGAD is equipped to handle both homophilic and heterophilic settings through a learned spectral filter bank, as described in Section 4.1.1. This bank consists of:

• Low-pass filters to capture smooth, homophilic signals,
• High-pass filters for heterophilic patterns, and
• An identity (unfiltered) pathway to retain raw structural information.

These filters are assigned learnable weights, enabling the model to adaptively emphasize the appropriate frequency bands depending on the graph type. As a result, CurvGAD is able to generalize across both homophilic and heterophilic graphs by selectively attending to different parts of the eigenspectrum, which is reflected in its strong performance on diverse benchmarks.

[Q3] Does this curvature difference extend to non-graph data?

The idea of using curvature as a measure of structural irregularity indeed extends beyond graphs, particularly in data types that can be embedded into metric or manifold spaces, such as text, images, or time series. While such extensions are beyond the scope of the current paper, we are actively exploring them in future work.

[Q4] The proposed method includes two scores for anomaly detection.

We appreciate the opportunity to clarify this. Yes, all the three reconstruction-based anomaly scores (curvature, features, adjacency matrix) are normalised using min-max scaling. We shall clarify and highlight this more explicitly in the camera-ready draft and code repository. We also use learnable trade-off weights $(\lambda_{\mathbf{C}}, \lambda_{\mathbf{A}}, \lambda_{\mathbf{X}}, \lambda_{\text{cls}})$ to adaptively balance the contributions of all losses. This ensures that no single score dominates (Section 4.3). We further perform extensive ablation studies to isolate the impact of different scores (Table 2). Section 5.5 entails the different CurvGAD variants which omit specific losses out of these four scores.

We sincerely thank the reviewer again for their thoughtful and constructive feedback, which will help us further improve the clarity and completeness of our work.

We sincerely thank the reviewer for their insightful feedback and constructive suggestions. We hereby address the raised concerns.

Computational Considerations for ORC

Computing ORC is computationally expensive

We appreciate your concern and apologize for not sufficiently emphasizing this aspect in the main paper. To clarify, we employ a linear-time combinatorial approximation for computing Ollivier-Ricci Curvature (ORC), which avoids the expensive optimal transport computations typically involved. A detailed analysis of the computational considerations for ORC is provided in Appendix C.1, particularly in Section C.1.2.

As outlined in Theorem C.1 and Appendix C.1, our approximation computes curvature using only local structural properties—specifically node degrees and triangle counts—allowing each edge's ORC to be estimated as the average of analytically derived upper and lower bounds. This approach results in a linear-time computational complexity $(\mathcal{O}(|\mathcal{E}|))$. Furthermore, because the computation for each edge is independent, the process is naturally parallelizable, making it scalable and efficient even for large graphs.

Summary of Preprocessing Complexity (Appendix C.1.4)

• Ollivier-Ricci Curvature (ORC): $\mathcal{O}(|\mathcal{E}|)$ (linear time)
• Ricci Flow Regularization: $\mathcal{O}(|\mathcal{E}|)$ (empirically bounded by a constant number of iterations)
• Total Preprocessing Complexity: $\mathcal{O}(|\mathcal{E}|)$ (parallelizable and scalable)

I don't think "my model wins" is appropriate in a scientific paper.

We thank the reviewer for pointing this out. The caption could be more formal and we will revise it to adopt a more appropriate and professional tone in the camera-ready version.