When Witnesses Defend: A Witness Graph Topological Layer for Adversarial Graph Learning

Thank you for considering our response. We are glad to be able to resolve your concerns partially. If you have any further questions so as to resolve your concerns fully, please let us know. Otherwise, please kindly consider changing your score accordingly.

We thank the reviewer for the feedback to improve our experimental analysis and exposition.

(1) Further comparison with different baselines

In the revised draft, we demonstrate the performance of WGTL with different GNN backbones, with a backbone specific to heterophilic graphs. In addition, we also compare WGTL with another existing defense mechanism.

(a) Performance of WGTL with different GNN backbones: In addition to GCN, We have added two more backbones, GAT [6] (Tables 14-15) and GraphSAGE [1] (Tables 16-17) in Appendix F and shown the effectiveness of WGTL on Cora-ML and Polblogs under mettack and nettack. We observe that incorporating WGTL into all of the backbones improves their corresponding performances under a range of perturbation rates. The following table summarizes the %improvement in mean accuracy with respect to the corresponding backbone models:

(URL to Tables 14-15)

(URL to Tables 16-17)

(b) Performance of WGTL with a heterophilic graph-specific backbone (H$_2$GCN [3]): Following [4], We experiment with snap-patents, a strongly heterophilic graph under mettack. We incorporated global topology encoding into H${_2}$GCN [3], a popular method with 580+ citations proposed to handle heterophilic graphs. In Table 20 of Appendix F3, we have shown that H${_2}$GCN+WGTL improves the robustness of H$_2$GCN by up to 4%. Note that the most adversarially robust method on this dataset, APPNP by [5], has been shown to have an accuracy of $27.76\%$ under 20% perturbation (c.f. Table 3, [4]). Improving on that, we observe that H${_2}$GCN+WGTL achieves $28.21\%$ average accuracy under $20\%$ perturbation.

(c) Comparing with more SOTA defenses for GNNs: In Appendix F.2, we have compared WGTL with two SOTA defense methods in the paper: ProGNN (Table 5) and GNNGuard [2] (Tables 18-19). With respect to ProGNN (with GCN backbone) SOTA, our method ProGNN+WGTL gains 0.68% - 4.96% of relative improvements on Cora-ML and Citeseer under mettack. On Cora-ML under mettack, our method GCN+GNNGuard+WGTL yields more than 2.25%, 1.12%, and 1.85% relative improvements with respect to GCN, GCN+GNNGuard (SOTA defence), and GCN+WGTL, respectively.

(URL to Table 5)

(URL to Tables 18-19)

(2) Positioning the attacks in the main paper

Thank you for this suggestion. Due to page limitations, we are unable to move Appendix B to the main body. Presently, we provide a brief description of different attacks considered in the experiments (Section 5) in the paragraph “Adversarial Attacks: Local and Global.” (page 7). However, if the reviewer thinks it to be critical, we will try our best to do it.

References:

[1] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 30, 2017.

[2] Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. NeurIPS, 33:9263–9275, 2020

[3] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, 33:7793–7804, 2020

[4] Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. How does heterophily impact the robustness of graph neural networks? theoretical connections and practical implications. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2637–2647, 2022

[5] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Gunnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018

[6] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.

We thank the reviewer for his detailed feedback to improve the paper and specially, for introducing us to the interesting line of works on graphs with heterophily to instantiate flexibility and generality of WGTL.

(1) Further comparison with different baselines

Thank you for pointing out this limitation. We have compared and demonstrated improvement over non-topological works, in particular those that use neighboring structure or connectivity patterns using other concepts such as GraphSAGE, GNNGuard, and H$_2$GCN.

(a) Performance with GraphSAGE [1]: Table 16 shows the performance of GraphSAGE and the proposed GraphSAGE+WGTL on the Cora-ML and Polblogs datasets under mettack. We observe that GraphSAGE+WGTL improves robustness with respect to the baseline GraphSAGE by 3.2% - 42.6% on Cora-ML and 1.5% - 40.8% on Polblogs. Table 17 shows the performance under nettack. We observe that GraphSAGE+WGTL improves robustness with respect to the baseline GraphSAGE by 3% - 4% on Cora-ML and 0.4% - 1.7% on Polblogs.

(URL to Tables 16-17)

(b) Comparison with GNNGuard [2]: In Appendix F.2, we have compared the proposed WGTL with GNNGuard (Tables 18-19). On Cora-ML under mettack (Table 18), our method GCN+GNNGuard+WGTL yields more than 2.25%, 1.12%, and 1.85% relative improvements with respect to GCN, GCN+GNNGuard (SOTA defence), and GCN+WGTL, respectively.

(URL to Tables 18-19)

(c) Performance with H${_2}$GCN [3]: Following [4], we run experiments on snap-patents, a strongly heterophilic graph under mettack. We incorporated global topology encoding into H${_2}$GCN [3], a popular method with 580+ citations proposed to handle heterophilic graphs. H${_2}$GCN proposes a set of key design techniques to improve the performance of GNNs on heterophilic graphs: (1) separation of ego- and neighbor-embedding, (2) incorporation of higher-order neighborhoods, and (3) combination of intermediate representations using skip-connections. In Table 20 of Appendix F3, we have shown that H${_2}$GCN+WGTL improves the robustness of H2GCN by up to 4%. Note that the most adversarially robust method on this dataset, APPNP by [5], has been shown to have an accuracy of $27.76\%$ under 20% perturbation (c.f. Table 3, [4]). Improving on that, we observe that H${_2}$GCN+WGTL achieves $28.21\%$ average accuracy under $20\%$ perturbation.

(2) Conduct experiments on more recent graph neural networks than GCN

In addition to GCN in the main paper, we have added two more backbones, GAT [6] (Tables 14-15) and GraphSAGE [1] (Tables 16-17), in Appendix F and shown the effectiveness of WGTL on Cora-ML and Polblogs under mettack and nettack. We observe that incorporating WGTL into all of the backbones improves their corresponding performances under a range of perturbation rates. The following table summarizes the %improvement in mean accuracy with respect to the corresponding backbone models:

(URL to Tables 14-15)

(URL to Tables 16-17)

(3) Experiments with WGTL on heterophilic graphs

As a response to this question, we refer the reviewer to point (c) Comparison with H${_2}$GCN [3] of the answer to question (1), and Appendix F.3 in the revised draft.

(4) Positioning “Related Works” after “Introduction”

Thank you for this suggestion. We have moved the "Related Works" after the "Introduction" section in the revised manuscript.

References:

[1] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.

[2] Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. Advances in neural information processing systems, 33:9263–9275, 2020

[3] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793–7804, 2020

[4] Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. How does heterophily impact the robustness of graph neural networks? theoretical connections and practical implications. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2637–2647, 2022

[5] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Gunnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018

[6] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.

Dear Reviewer REKj,

Thank you again for the time and effort that you dedicated to providing invaluable feedback on our paper. We would very much appreciate if you could consider updating the scores before the deadline (rapidly approaching). Please let us know If there are any remaining concerns.

Best,

Paper ID 5896 Authors

(7) Computational complexity of the Witness complex-based topological features

Thank you for pointing out this issue. We have corrected the computational complexity segment in Section 5 as per the following:

Landmark selection (top-$|\mathfrak{L}|$ degree nodes) has complexity $\mathcal{O}(N\log(N))$. To compute witness topological features, one needs to compute (1) landmarks-to-witness distances costing $\mathcal{O}(|\mathfrak{L}|(N+|\mathcal{E}|))$ due to BFS-traversal from landmarks, (2) landmark-to-landmark distances costing $\mathcal{O}(|\mathfrak{L}|^2)$, and finally (3) persistent homology via boundary matrix construction and reduction [7]. Matrix reduction algorithm costs $\mathcal{O}(\zeta^3)$, where $\zeta$ is the number of simplices in a filtration. Overall, the computational complexity of computing witness topological feature on the graph is $\mathcal{O}(|\mathfrak{L}|(N+|\mathcal{E}|)+|\mathfrak{L}|^2+\zeta^3)$.

(8) Specific remarks

Thank you for pointing out these mistakes/typos. We have addressed them in our updated manuscript. Here, we address two specific questions mentioned in this list.

page 2 "complementary information" - complementary to what? it is not very clear

By complementary information here, we understand more traditional graph summaries that are not extracted using any tools of persistent homology.

page 9 "the homologically persistent graph skeleton" - what is meant by this?

We have reformulated this sentence as follows: “Another interesting research direction is to investigate the linkage between the attacker's budget, number of landmarks, and topological attacks targeting the skeleton shape, that is, topological properties of the graph induced by the most important nodes (landmarks).”

References:

[1] Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. Advances in neural information processing systems, 33:9263–9275, 2020

[2] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.

[3] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793–7804, 2020

[4] Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. How does heterophily impact the robustness of graph neural networks? theoretical connections and practical implications. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2637–2647, 2022

[5] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Gunnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018

[6] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.

[7] Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28:511–533, 2002

[8] Naheed Anjum Arafat, Debabrota Basu, and Stephane Bressan. ε-net induced lazy witness complexes on graphs. arXiv preprint arXiv:2009.13071, 2020

(2) Discussions on different aspects of Witness complex construction

Here, we elaborate on four points regarding different aspects of Witness complex construction and how we address in this work the four drawbacks mentioned by the reviewer.

a. The landmark selection heuristic employed is deterministic because we select the top 5% highest-degree nodes as landmarks. Since there is no randomness in such deterministic selection, there is no instability in the final performance.

b. The accuracy is indeed dependent on the number of landmarks. Figure 3 (Appendix E) shows that with an increased number of landmarks, the accuracy increases.

c. Indeed, with an increased number of landmarks, the computational cost increases, as we have shown in Figure 3. However, Table 13 indicates that even after such an increase, the computation time is still substantially less than that of Vietoris-Rips. Furthermore, Figure 3 (Appendix E) shows that the accuracy increases, becoming closer to what is obtained by GCN+VRGTL.

d. It is not clear what the reviewer meant by “different situations”; hence, we consider the following two scenarios:

1. The relation between persistence diagrams induced by different sets of landmarks of the same cardinality: [8] show that irrespective of the choice of landmarks, if the landmarks are $\epsilon$-net of the graph $G = (V, E)$, it produces a $(3log3 + 2\epsilon)$-approximations to Vietoris-Rips complex of $G$. Let us assume two sets of landmarks $L$, $L’$ such that $|L| = |L’|$ and both are $\epsilon$-net of the graph $G = (V, E)$. Then, both choices give us the same approximation error w.r.t Vietoris-Rips.

2. The relations between encoding induced by different sets of #landmarks of the same cardinality: Proposition 2 shows that the encoding $Z_{WGTL}$ is stable under adversarial perturbation. The guarantee is dependent on $\epsilon$ but does not depend on the particular choices of landmarks. Let us assume two sets of landmarks $L$, $L’$ such that $|L| = |L’|$ and both are $\epsilon$-net of the graph $G = (V, E)$. Then, both choices of the landmark set give us the same stability guarantee in terms of encoding $Z_{WGTL}$.

(3) Explaining the choice concerning the number of the landmarks and its impact

The choice of the number of landmarks is indeed an important hyperparameter for the pipeline to work. We varied the number of landmarks and made an assessment of their impact on accuracy as well as the increased computation time. Figure 3 (Appendix E) shows that increasing the number of landmarks indeed slightly increases the accuracy, albeit with the expense of increased computation time. Due to this trade-off, the selection of an optimal number of landmarks is dependent on how much robustness is desired by a user with a given computation time budget. Appendix E.1 includes a more elaborate discussion on this point.

(URL to Figure 3)

(4) Using the standard Vietoris-Rips complexes in the pipeline

Thank you for bringing this interesting point to our attention. The Vietoris-Rips complexes can be used with the proposed pipeline, which is indicative of the flexibility offered by the proposed method.

In Appendix E.2, we have implemented GCN + VRGTL, where instead of encoding witness topological features, we have encoded the Vietoris-Rips features. Table 12 shows that the accuracy is comparable to that of GCN+WGTL while at the cost of a significant increase in computation time (Table 13). In our implementation, we adopted Ripser (SOTA for CPU-based computation) for computing both Vietoris-Rips and Witness topological features. Hence, if a GPU-accelerated implementation,e.g., Ripser++, were to be used, it would have accelerated Vietoris-Rips as well as Witness feature computations.

(URL to Tables 12-13)

(5) Clarification of theoretical results

We have clarified the theoretical results in the main paper. In addition, we have included in Appendix D a nomenclature of notations (Appendix D.1) and detailed derivations of the proofs to enhance clarity. Please consider the revised draft for the changes.

(6) Specifying the dimensions used in the persistence diagrams

Thank you for your detailed observation. Our theoretical results hold true once we fix the dimension of the persistence $d \in Z_{\geq 0}$ to be computed and use it throughout the pipeline. In our experiments, we used 0-dimensional persistence. We have added it in Section 5 (paragraph 1) of our updated manuscript.

We thank the reviewer for his detailed review with minute observations and comments to improve the paper.

(1) Further comparison with different baselines

In the revised draft, we demonstrate the performance of WGTL with different GNN backbones (for both graphs with homophily and heterophily), and in comparison with an existing defense mechanism. We elaborate the results below.

(a) Existing Defenses for GNNs: In Appendix F.2, we have compared WGTL with two SOTA defense methods in the paper: ProGNN (Table 5) and GNNGuard [1] (Tables 18-19). With respect to ProGNN (with GCN backbone) SOTA, our method ProGNN+WGTL gains 0.68% - 4.96% of relative improvements on Cora-ML and Citeseer under mettack. On Cora-ML under mettack, our method GCN+GNNGuard+WGTL yields more than 2.25%, 1.12%, and 1.85% relative improvements with respect to GCN, GCN+GNNGuard (SOTA defense), and GCN+WGTL, respectively.

(URL to Table 5)

(URL to Tables 18-19)

(b) Different GNN Backbone Architectures: In addition to GCN, We have added two more backbones, GAT [6] (Tables 14-15) and GraphSAGE [2] (Tables 16-17) in Appendix F, and shown the effectiveness of WGTL on Cora-ML and Polblogs under mettack and nettack. We observe that incorporating WGTL into all of the backbones improves their corresponding performances under a range of perturbation rates. The following table summarizes the %improvement in mean accuracy with respect to the corresponding backbone models:

(URL to Tables 14-15)

(URL to Tables 16-17)

(c) Performance for Heterophlic Graphs: Furthermore, following [4], we incorporated the proposed global topology encoding into H${_2}$GCN [3], a popular method proposed to handle heterophilic graphs. We experiment with snap-patents, a strongly heterophilic graph under mettack. In Table 20 of Appendix F3, we have shown that H${_2}$GCN+WGTL improves the robustness of H2GCN by up to 4%.

Note that the most adversarially robust method on this dataset, APPNP by [5], has been shown to have an accuracy of $27.76\%$ under 20% perturbation (c.f. Table 3, [4]). Improving on that, we observe that H${_2}$GCN+WGTL achieves $28.21\%$ average accuracy under $20\%$ perturbation.

This table is included in the paper as Table 20.

(d) Comparison with Vietoris-Rips based encodings: In Appendix E.2, we have implemented GCN + VRGTL, where instead of encoding witness topological features, we have encoded the Vietoris-Rips features. Table 12 compares them on Cora-ML and Citeseer under mettack. We observe that both models have a comparable accuracy. However, Table 13 shows that Vietoris-Rips topological features take significantly more time than Witness feature computation. Hence, GCN+VRGTL does not bring much of a benefit at the expense of significantly higher computational resources.

(URL to Tables 12-13)

Dear Reviewer UAFj,

Thank you again for the time and effort that you dedicated to providing invaluable feedback on our paper. We would very much appreciate if you could consider updating the scores before the deadline (rapidly approaching). Please let us know If there are any remaining concerns.

Best,

Paper ID 5896 Authors