SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds

Weakness 1: Some of the contents are unclear, making the paper difficult to follow.

We acknowledge that we cannot include every detail due to the page limitation. Could you please share more information regarding the unclear contents? In the revised version, we will refine these explanations.

Weakness 2: Some technical parts of the paper may need further justification.

We agree that additional justification would strengthen the technical sections. However, due to the page limitation, we provided more detailed explanations of the theoretical underpinnings of our approach in the Appendix. Could you please share more information on which part needs further justification?

---

Question 1:

In our framework, PGMs are used to learn the structure of graph-based manifolds from data embeddings. The metric we employ on these manifolds is the effective resistance distance, which captures both local and global structural information. This metric remains consistent during GNN propagation because it is computed based on the constructed manifolds prior to GNN processing. However, after GNN propagation, the output manifold (constructed from the GNN outputs) may exhibit changes in this metric due to the transformations applied by the GNN. By analyzing the changes between the input and output manifolds using DMD, we can effectively assess node-level robustness.

Question 2:

Thank you for highlighting this oversight. We define a node as unstable if small perturbations in the input (e.g. graph topology or node features) lead to significant changes in the output, indicated by a high Distance Mapping Distortion (DMD) value. Conversely, a stable node has a low DMD value, reflecting robustness to input variations. We will include a formal definition and specify thresholds (e.g., based on statistical deviations from the mean DMD value) used to categorize nodes, providing clear criteria for stability assessment.

Question 3:

You raise an important point. Our method is indeed most effective for GNNs that perform feature smoothing, common in homophilic graphs. However, for heterophilic graphs, we still observed SAGMAN distinguish stable and unstable nodes, as shown in Appendix Figure 10. We will discuss these considerations and potential extensions in the paper, acknowledging this limitation and proposing it as future work.

Question 4:

We agree that a hyperparameter study would provide valuable insights into the robustness and sensitivity of our method. Due to space constraints, we could not include this in the main paper. However, we will add a hyperparameter analysis in the supplementary material, examining the impact of key parameters such as the number of nearest neighbor$k$, sparsification thresholds , and others. This will demonstrate how these parameters affect performance and guide practitioners in selecting appropriate values.

Question 5:

Thank you for this suggestion. We will refine the paper's structure by including a comprehensive flowchart or diagram that outlines the entire SAGMAN pipeline. Additionally, we will enhance the transitions between sections with interconnecting text that explains how each component leads to the next. This will provide a cohesive narrative and help readers understand how the components integrate into a unified framework.

---

Minor Comments:

• On row 234, the input embedding matrix $X = U_k$; I think $X$ should be the initial feature?

As we mentioned in row 232, $X = U_k$ represents the spectral embedding matrix derived from the graph's Laplacian eigenvectors, not the initial node features. We will clarify this in the text to prevent confusion, ensuring that the distinction between the initial features and the embedding matrix is clear.

• On row 759, the Appendix A.1 is self-referred.

We apologize for this error. We will correct the reference to point to the appropriate section, ensuring all cross-references are accurate.

---

We hope that these clarifications address your concerns. Your feedback has been invaluable in helping us improve the clarity and quality of our paper. We will incorporate these revisions to enhance the presentation and technical depth. Thank you again for your thoughtful review.

Weakness 1:

We appreciate your suggestion to assess the generalizability of SAGMAN across different GNN tasks. Applicability to Link Prediction:

Link prediction primarily focuses on inferring missing edges or predicting future connections between nodes based on local neighborhood information and connectivity patterns. This task is inherently localized, relying heavily on immediate node proximities and the existence of common neighbors or local subgraph structures.

SAGMAN, on the other hand, is designed to assess the stability of GNNs by capturing global structural properties through effective resistance distances, which consider the entire graph's topology. The metrics and methods we employ are optimized for scenarios where global connectivity and long-range interactions significantly impact the model's performance and stability.

Applying SAGMAN to link prediction may not yield meaningful insights because:

• Local vs. Global Focus: Link prediction's reliance on local structures means that global stability measures may not accurately reflect the task's requirements or the GNN's performance in this context.
• Distance Metrics: The effective resistance distance used in SAGMAN captures global graph properties, which might obscure the local patterns critical for successful link prediction.

Therefore, while theoretically possible, using SAGMAN for link prediction might not provide additional value and could potentially misrepresent the model's stability concerning this task.

Applicability to Community Detection:

Community detection involves partitioning the graph into clusters or communities based on densely connected nodes.

While SAGMAN's global perspective might seem beneficial, the specific nature of community detection means that alternative methods tailored to detect and preserve community structures would be more appropriate.

Weakness 2:

We acknowledge the importance of comparing SAGMAN with existing robustness techniques. However, as you pointed out, while many studies focus on enhancing the robustness of GNN architectures, fewer have explicitly proposed methods that evaluate and rank node-level robustness. This scarcity makes direct comparisons challenging.

Nevertheless, we can discuss the differences between SAGMAN and existing methods. Most robustness techniques aim to improve overall model robustness through architectural changes or training strategies, without providing fine-grained, node-level stability assessments. In contrast, SAGMAN offers a spectral framework to quantify stability at the individual node level, which can guide targeted interventions such as focused attacks or stability enhancements.

In future revisions, we will include a discussion comparing SAGMAN conceptually with existing robustness methods, highlighting its unique contributions and potential integration with other techniques.

Weakness 3:

You raise a valid point regarding the complexity analysis. We agree that in the worst-case scenario of a complete graph, the average degree 'd' is O(|V|), making the time complexity O(|V|^2 m). However, most real-world graphs are sparse, with average degrees much smaller than the number of nodes. [1] In these cases, 'd' can be considered a constant or grows slowly with |V|, making the overall time complexity nearly linear in practice.

To address this, we will revise the complexity analysis in the paper to explicitly account for 'd' and clarify that the near-linear time complexity holds for sparse graphs, which are common in practical applications.

Question:

Indeed, SAGMAN's effectiveness is tied to the graph's spectral properties, particularly the presence of a significant eigengap, which allows for meaningful dimensionality reduction while preserving structural information. For graphs that do not naturally exhibit significant eigengaps or are not well-represented in low-dimensional spaces, SAGMAN's performance may be limited.

To address this limitation, one potential approach is to apply graph preprocessing techniques that enhance the spectral properties of the graph. For example, techniques like graph coarsening or spectral clustering can be used to restructure the graph into a form that has a more pronounced eigengap. Alternatively, augmenting the graph with additional edges or weights based on domain knowledge could improve its spectral characteristics.

We acknowledge this as an important area for future research and plan to investigate methods to extend SAGMAN's applicability to a broader class of graphs.

[1] Miao, Jianyu, et al. "Graph-based clustering via group sparsity and manifold regularization." IEEE Access 7 (2019): 172123-172135.

Weaknesses

1. Combination of Existing Approaches

   We appreciate the reviewer's feedback. As demonstrated in Section 3.3 and detailed in Appendix A.6, the previous DMD metric cannot be directly applied to GNN stability analysis, underscoring the necessity and uniqueness of the proposed SAGMAN framework.

   The contribution is summarized as follows (as highlighted in Section 3): (1) SAGMAN introduces an innovative approach to convert the original input graph that may lie in a high-dimensional space into a low-dimensional graph-based manifold by leveraging PGMs. (2) To this end, an embedding matrix construction method and a scalable PGM construction approach are proposed, which will assure the preservation of graph resistance distances. (3) A novel spectral sparsification based on the short-cycle decomposition of weighted graphs is proposed to allow for the highly scalable construction of PGMs (low-dimensional graph-based manifolds).

   A key contribution of our work lies in the synergistic integration of these components, which enables fine-grained, node-level stability analysis in GNNs—an aspect largely overlooked by prior approaches that focus on improving overall robustness.

2. Lack of Strong Theoretical Guarantees

   In our work, we build upon theoretical results related to the DMD metric and effective resistance distances. The previous method [1] provides guarantees for recovering sparse graph structures preserving effective resistance distances. However, this method for learning PGMs may require numerous iterations to achieve convergence.

   To address this, we propose a scalable PGM using spectral sparsification and graph decomposition, as detailed in Section 3.3. In Appendices A.4 and A.9, we provide theoretical analyses demonstrating that PGM can be obtained by our pruning strategy. These analyses offer strong theoretical guarantees on the accurate estimation of low-dimensional manifolds.

3. Existing Stability Bounds for Feature Perturbations

   Could you please offer more information regarding the [R1] paper?

4. Restriction to Evasion Attacks

   While previous work [2] focuses exclusively on poisoning attacks, SAGMAN specifically addresses evasion attacks. However, since SAGMAN is a versatile plug-in method, we can easily deploy SAGMAN into the poisoning attacks and combine with other robustness techniques.

   To demonstrate this, we present the GCN robustness improvement results under the DICE poisoning attack, comparing SAGMAN with the previous SOTA method [2]. The results highlight the accuracy improvement on the 10% most unstable samples:

   DICE number of edge perturb	1	10	50	100
   LipReLU	0.7862	0.7903	0.7782	0.7822
   SAGMAN	0.8588	0.8427	0.8508	0.8548
   LipReLU +SAGMAN	0.8468	0.8467	0.8467	0.8427

Questions

1. Performance Against Sophisticated Attacks (Metattack, PGD)

   We would like to highlight that our evaluation already includes sophisticated attacks, such as Nettack. Also, we appreciate the reviewer’s suggestion to include more sophisticated attacks such as PGD. In response, we have conducted additional experiments using these attacks. Below, we present GAT case demonstrating the robustness under PGD on cora:

   PGD Perturbation	0.05	0.10	0.15
   Robust Accuracy	1.0000	1.0000	1.0000
   Non-Robust Accuracy	0.9630	0.8889	0.8148

   Regarding Metattack, it is designed for global attacks that perturb the entire graph structure to degrade overall model performance. Since our framework focuses on node-level stability analysis, Metattack does not align well with our evaluation objectives. Metattack's global perturbations make it unsuitable for assessing the robustness of individual nodes in the context of our methodology.

2. Analysis on Adaptive Attacks

   Could you please offer more information regarding the [R2] paper?

3. Performance on OGBN Datasets

   Please see Figure 7 and Figure 11 in the Appendix for the OGBN results.

4. Empirical Comparison with Lipschitz-based Stability Methods

   Response:

   We compared the one Lipschitz method against poisoning attacks. Please refer to the table in Weaknesses No.4 above.

[1] Feng, Zhuo. "SGL: Spectral graph learning from measurements." 2021 58th ACM/IEEE Design Automation Conference (DAC). IEEE, 2021.

[2] Jia, Yaning, et al. "Enhancing node-level adversarial defenses by lipschitz regularization of graph neural networks." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.

Weakness 1: "Graph robustness is a widely discussed problem. However, a comprehensive discussion of related works is needed in this literature. Moreover, more baselines and benchmarks are needed to be provided in the experimental part. Survey paper [1] can help you gain more understanding about more recent works."

We agree that a more comprehensive discussion of related work would strengthen the paper. In the revised version, we will expand the related work section to include recent studies on graph robustness, particularly those highlighted in the survey paper [1] you mentioned. We acknowledge that while many studies focus on enhancing the robustness of GNN architectures, fewer have explicitly proposed methods for evaluating and ranking node-level robustness. This scarcity limits the availability of direct baselines for our experiments.

Weakness 2: "For this metric of GNN stability, is there any conclusion from the experiments? Have various graph robustness algorithms been applied with this new metric? Any comparison between this metric and other graph stability metrics? For example, the prediction drop."

Yes, our experiments yield several conclusions about the effectiveness of the SAGMAN metric:

1. Effectiveness in Stability Assessment: SAGMAN successfully distinguishes between stable and unstable nodes across multiple datasets and GNN architectures.
2. Enhancing Adversarial Attacks: Using SAGMAN to guide adversarial attacks results in higher error rates compared to traditional methods, indicating its utility in identifying vulnerable nodes.
3. Enhancing defense regarding evasion attack: Using SAGMAN significantly enhances defense against evasion attacks.

Under perturbations, we have demonstrated in Table 5 that SAGMAN achieves higher accuracy than the SOTA GOOD-AT. Since the GOOD-AT paper does not report a prediction drop, we did not include it in our comparison. However, we provide the prediction accuracy for both approaches on the unperturbed graph here for reference.

Weakness 3: "From my opinion, applying DMD on graphs is a problem as the manifold on graph is hard to define. Although the PGMs can provide a solution, how good this PGMs can form the graph manifold is still a considerable question. Will the change of graph topology influence the mapping between graph structures and labels? This also needs to be analyzed."

We acknowledge that defining manifolds on discrete graphs is challenging. To address this, we first embed the graph into a continuous space using spectral methods, specifically Laplacian Eigenmaps. This spectral embedding preserves essential structural properties of the original graph and approximates the effective resistance distances. Then we leverage PGMs to learn a graph structure that captures these dependencies from the spectral embeddings. By constructing PGMs from the embedding matrix Uk (as defined in Definition 3.1), we obtain a graph manifold that reflects both the data's inherent structure and the conditional dependencies.

We understand your concern about whether changes in graph topology might affect the mapping between graph structures and labels. Our method focuses on preserving important structural features while simplifying the graph. By maintaining effective resistance distances through PGM construction, we retain both local and global connectivity patterns relevant to the labels.

Question 1: "In Figure 1, do the three graphs represent internal views of the same input graph within the framework, or are they independent examples with no connection to each other?"

Yes, it is the internal view. This sequential representation illustrates how the original input graph is transformed into low-dimensional (smooth) graph-based manifold through our framework to facilitate stability analysis.

Question 2: "How about the efficiency of the proposed algorithm?"

As section 3.6 introduced, the SAGMAN framework has a nearly linear time complexity. In our experiments in Appendix A.13, we demonstrate that SAGMAN can handle large datasets efficiently.

We hope that our responses adequately address your concerns. We are committed to improving the paper based on your feedback and believe that the revisions will enhance the clarity and impact of our work.

Thank you again for your thoughtful review.

[1] A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability.

[2] Feng, Zhuo. "SGL: Spectral graph learning from measurements." 2021 58th ACM/IEEE Design Automation Conference (DAC). IEEE, 2021.