GOttack: Universal Adversarial Attacks on Graph Neural Networks via Graph Orbits Learning

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

W1: The improvement over attack baselines is not very convincing. In Table 2, GOttack outperforms the baselines by less than 1% in many cases—an improvement smaller than the standard deviation reported in Appendix D. This raises concerns that GOttack may not consistently outperform these baselines, as using a different random seed could potentially alter the ranking of attack methods in Table 2.

Response: Thank you for this observation. While we acknowledge that in Table 2, GOttack's improvements over baseline methods may appear modest (less than 1%) and within the reported standard deviation range from Appendix D, we would like to emphasize two important points. i) Our results are stable across multiple runs, and while variations can occur due to different random seeds, the general trend remains consistent, demonstrating GOttack's effectiveness in leveraging topological insights for adversarial attacks. ii) More importantly, the key contribution of GOttack lies in demonstrating the importance of topological information for designing attack strategies. The topological approach in GOttack can be adopted as a preprocessing step to augment other attack methods, thereby improving their effectiveness. This finding underlines the critical role of topological structures in adversarial graph attack strategies. It also highlights how incorporating topological insights can provide a foundation for future advancements. In this sense, GOttack may play an influential role in this domain.

---

W2: GOttack underperforms compared to attack baselines in most cases when the budget exceeds 1, as shown in Tables 9–13.

Response: Thank you for this review. The proposed GOttack method achieved the highest performance in 8 out of 25 tasks, while PRBCD attained the highest performance in 10 tasks across Tables 9-13. Of the 8 tasks where GOttack excelled, only one was at budget level 1. SGA ranked best in 5 tasks. After calculating the averages, PRBCD has the highest mean value of 0.57 in Tables 9-13, while GOttack comes second with a mean of 0.55. We acknowledge that GOttack's results for the GCN model are close to those of the previous state-of-the-art methods; however, GOttack remains more scalable than the competitor.

---

W3: GOttack appears ineffective on heterophilic graphs, as suggested by the homophily assumption in line 256 and the empirical results in Appendix D.

Response: Thank you for this interesting insight. We believe that GOttack can be effective on heterophilic graphs, but we also acknowledge that we have not yet tested it extensively on heterophilic datasets. In Figure 7 of Appendix C.3, we present the orbit hierarchy and discuss how orbit transitions take place, particularly focusing on cases where orbit 1518 may be ineffective or absent in heterophilic graphs. This analysis shows the adaptability of GOttack’s strategy in varying graph structures and demonstrates its potential applicability beyond homophilic settings.

W4: Some recent and more effective defense methods are missing from the experiments. The authors only consider defense methods published before 2021, while several more powerful approaches have been proposed in the past two years. For example, GARNET [1] and SG-GSR [2] have shown stronger results than the defense methods included in this work.

Response: Thank you for the suggestion. We have added the new defense methods, as shown below. Gottack has the best results in GCORN and second best results in GARNET and GCNGuard.

Table 3: Miscl. rate (↑) on CORA against the GNNGuard defense

Table 4: Miscl. rate (↑) on CORA against the GCORN defense

Table 5: Miscl. rate (↑) on CORA against the GARNET defense (We updated the results that were missing at the time we submitted the response)

---

Q1: What is the runtime of the preprocessing stage?

Response: The time complexity of orbit discovery, as discussed in Section 4.3 is defined as $O(|E| \times d + |V| \times d^4)$, where $d$ is the maximum node degree in the graph. It is essential to note that the orbit discovery is performed only once per static graph as a pre-processing phase. The costs are not prohibitive, as we show in the table 1 below:

Table 1: Orbit discovery time on Cora, Citeseer, Polblogs, Blogcatalog and Pubmed.

---

Q2: How large of a graph can GOttack scale to?

Response: We have used Gottack on the OGB-ARXIV dataset without problems. The dataset, which is considered a large one in adversarial settings, has 169K nodes and 1.1M edges.

Table: Misclassification rate (↑) on OGB-Arxiv (GCN backbone)

Q3: In Table 2, why is there a significant difference (over 30%) between GOttack-GCN and GOttack-GSAGE on BlogCatalog?

Response: Thank you for the review. After re-evaluating the experiment, the difference between their performance was almost the same (around 29%, as given below). This outcome aligns with the nature of the BlogCatalog dataset. GCN is more effective for datasets with high homophily. However, BlogCatalog is a heterophilic dataset, posing challenges for GCN.

Table 6: Miscl. rate (↑) on BlogCatalog (GSAGE backbone)

Thank you to the authors for their response and the inclusion of new experiments. However, I have several remaining concerns:

the key contribution of GOttack lies in ... . The topological approach in GOttack can be adopted as a preprocessing step to augment other attack methods, thereby improving their effectiveness.

If this is the key contribution of this work, authors should put it in the list of contributions in the Introduction section. Additionally, there are currently no empirical results supporting the claim that GOttack enhances the performance of other attack methods. It would be beneficial for the authors to include such data. Moreover, authors should conduct more comparisons with preprocessing defense methods, such as ProGNN and GARNET, to strengthen the preprocessing efficacy for the proposed approach.

We have added the new defense methods, as shown below. Gottack has the best results in GCORN and second best results in GARNET and GCNGuard.

It seems these newly added defense methods are more difficult to attack. I strongly encourage the authors to conduct more comprehensive experiments on these methods across all datasets, not just Cora, as this will provide a more convincing validation of Gottack's effectiveness. Results from these extensive tests, particularly against stronger defense methods, should be included in the revision to strengthen the empirical findings.

Overall, I find the concept of this work appealing, though I still have several concerns regarding the experiments. I concur with Reviewer EmAo on the need for a more detailed discussion on adaptive attacks. Trusting that the authors will effectively incorporate new experiments into the main text, I increase my score to 6.

Given the extension of the discussion period, I request that the authors address my two remaining concerns as outlined above. Specifically, I am looking for an updated list of contributions in the Introduction section (mentioning a key contribution of GOttack is to augment other attack methods), new results that demonstrate the integration of GOttack with other attack methods on at least a couple of datasets (considering the time constraints for Rebuttal), and more comprehensive results from applying GOttack to preprocessing-based defense methods such as ProGNN or GARNET.

I will reevaluate my score based on authors' response.

We integrated GOttack with PRBCD, GO-PRBCD, and evaluated it on Citeseer. The table below shows that GO-PRBCD performs best for budget 2 but not as well as PRBCD or GOttack. We attribute this to the block sampling strategy that scales up PRBCD. In contrast, GOtack presents a non-sampling-based, principled approach to identifying the best candidate nodes. We thank you again for your thoughtful reviews, which strengthened our work. Due to the time limit, we evaluated GOttack on three defense models (GCORN, GARNET, and GCNGuard) upon your request. We also evaluated new models on two datasets, Cora and Citeseer. We will revise our manuscript accordingly.

We note your comment on standard deviations; we will bring at least the stdevs of the main results table and perhaps move some defense results to the appendix to make space.

W3: [Also at Question 3] The theoretical insights presented in Theorem 1 are very interesting. It would be great to also validate the claims experimentally. One first experimental setting would be to consider the effect of choosing nodes in the orbits 15 and 18 and other orbits to see the effect of the hitting times.

Response: We have prepared the average first hitting times of orbits (top 15 results) when starting max 1000 step fixed-length random walks from the 40 attack nodes (repeated 5 times). Lower ranks indicate shorter first hitting times. As the tables show, 1518 hitting times are bigger than most orbits. Furthermore, orbits such as 6_19 that appear higher are embedded in graphlets of similar long-chains, however nodes of these orbits are much rarer than 1518 orbits, hence their hitting times are biased for longer values.

---

Q2 and Q4: The theoretical analysis doesn’t seem to take into account the node features ? Could you please clarify on that? Is your framework also adaptable to node-feature based adversarial attacks ? As it seems you refer to it in general attack formulation in Section 2 (mainly Eq. 1).

Response: Gottack analysis focuses on graph topology, and GOttack does not consider node features initially when limiting the attack to 1518 nodes for adversarial perturbations. However, the surrogate loss function in GOttack (Section 4.3) incorporates node features as it optimizes misclassification probabilities which ensures that the combined effect of structure and attributes is accounted for during attacks.

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

W1: The authors only consider RGCN, GCN-Jaccard, GCN-SVD and MediaGCN as a defense method to attack. Recent work have clearly shown the failure of these defense in defending (specifically targeted attacks). I would rather consider adding other benchmarks such as GCNGuard [1] and specifically the newly presented GCORN [2].

Response: Thank you for the suggestions. We have prepared the results for three recent defense models as given below in tables (the suggested GCNGuard was the GNNGuard article). As the results show, Gottack has the best results in GCORN and second best results in GARNET and GCNGuard.

Table: Misclassification rate (↑) on CORA against the GCORN defense

Table: Misclassification rate (↑) on CORA against the GNNGuard defense

Table: Misclassification rate (↑) on CORA against the GARNET defense (we have updated the results that were previously missing at the time we submitted the response)

---

W2: [Also at Question 1] The Budgeted attack results are rather focusing on the GCN, GIN and GraphSage and ignores the defense methods. Typically in the adversarial litterature, we are rather interested in the attack success rate when subject to the defense method, as by definition the original models are rather known to be vulnerable to attacks.

Response: Thank you for pointing this out. In Table 3 of the article we report the performance against four defense models, and we have prepared three new models, as given in tables above. These results provide further evidence for the good performance of our attack method.

Minor

Review: The authors might want to note that the reliability of GNN explanations is debated [2,3]

Response: Thank you for the reference; we have cited the articles and mentioned this issue in Section 5.2.

---

Questions

Q1: Have the authors tried to scale to larger graphs? E.g., OGB arXiv, Products, or Papers100M (as PRBCD does)?

Response: We report Arxiv results in the Table below. As the table indicates, Gottack yields the best results on the Arxiv dataset.

Table 2: Misclassification rate (↑) on OGB-Arxiv (GCN backbone)}

---

Q2: Is $\mathcal{G}{g p} = \mathcal{G}{s'}$ in Definition 2

Response: Yes, Definition 2 states that the graphlet $\mathcal{G}{g p}$ is a connected induced subgraph, which directly corresponds to $\mathcal{G}{s'}$. Therefore, $\mathcal{G}{g p} = \mathcal{G}{s'}$ holds true in this context.

---

Q3: Are orbits 15 and 18 special regardless of the number of nodes? If so, could the authors please elaborate a bit more?

Response: The orbits are agnostic of the node count in the graph,but depend on the graphlets size. As we show in Fig 6, graphlets uniquely determine the number and position of orbits. If the orbits do not exist, topology offers new orbits to attack, such as 1519 and 1922, as we study and report in Appendix D. We have also created a graph-algebra-based orbit selection scheme in Appendix C.3 that can attack i) a graph of any size and ii) a graph without the periphery orbits of 1518. However, we note that in all the datasets used, nodes belonging to orbit 1518 were particularly common (Fig 8).

---

Q4: Why do the authors focus on very small budgets 1..5? Usually, the budget is made relative to the degree of the attacked node.

Response: The primary reason is to make our attack model more realistic. For instance, in a social network setting, altering 10% of someone's friends—especially for an individual with thousands of connections may not be practical. On the other hand, convincing a person to establish a link with a single fake account could be more feasible. Therefore, we aim to evaluate the performance of the attacks under realistic threat models.

---

Q5: How is the preprocessing of Gottack included in the times reported in Table 4?

Response: Our results, reported in Table 4, include the total computation time (end-to-end), which includes the orbit discovery process.

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

---

W1: Indirect attack

Review: The attack is an indirect attack using a surrogate (i.e., non-adaptive [1]). This severe limitation should be discussed prominently in the text. Moreover, GOttack seems to transfer evasion attacks to the poisoning setting and the attack is not evaluated against adaptive attacks (except for GCN; e.g. directly attack GSAGE/GIN with PRBCD and not the GCN surrogate).

Response:
Thank you for your feedback. Our attack operates in a grey-box setting, where the attacker has access to partial information, specifically some of the training labels, but does not have direct access to the target model's architecture or parameters. This is a realistic and common scenario in adversarial machine learning, particularly in applications where full model transparency cannot be assumed. In such settings, using a surrogate model to craft training-phase attacks is a practical approach, as the actual model deployed in practice is expected to be trained on the perturbed dataset generated by the surrogate.

Our evaluation shows that the perturbations generated using a surrogate model still transfer effectively to other architectures, such as GSAGE and GIN, demonstrating the robustness and generalizability of the GOttack strategy. This reinforces the utility of our method even when adaptive, model-specific adjustments are not feasible.

We recognize that testing GOttack in a fully adaptive setting could be an interesting extension of this work. We hope this clarifies our design choices and the scope of our current work.

---

W2: Numbers

Review: I had a hard time following some of the discussion Section 4.2 since it is not clear when numbers are general constants or tailored to the example in Figure 2.

Response:
Thank you for the review; all the numbers in the section are due to the nature of graphlets and orbits. These are defined by subgraph sizes and node degrees; as such, none of the values are tailored or modified by us. We have added the following sentence to section 4.2:
“The number of graphlets and orbits are all uniquely determined by the choice of using 5-node graphlets.”

---

W3: Scalability

Review: The attack does not seem scalable due to the required preprocessing.
Response: The time complexity of orbit discovery, as discussed in Section 4.3, is defined as $O(|E| \times d + |V| \times d^4)$, where $d$ is the maximum node degree in the graph. It is essential to note that the orbit discovery is performed only once per static graph as a pre-processing phase. The costs are not prohibitive, as we show in Table 1 below:

Table 1: Orbit discovery time on Cora, Citeseer, Polblogs, Blogcatalog, and Pubmed

As GOttack is highly scalable, we now report experimental results on the large-scale OGB-Arxiv dataset in Table 2 below, where GOttack yields the best performance.

Table 2: Misclassification rate (↑) on OGB-Arxiv (GCN backbone)}

W4: Quadratic Scalability

Review: The authors do not properly discuss scalable attacks on GNNs. For example, the authors compare with PRBCD but ignore its properties in their discussion. For example, the argument on ll. 517-519 does not necessarily apply to PRBCD. Also, the statement that PRBCD was of quadratic scalability seems wrong/imprecise (Section B.2).

Response: Thank you for pointing out this issue. In fact, PR-BCD isn’t quadratic; the correct time complexity of PR-BCD is defined in the article’s Table E.3 $O(|E| \times b log(b)$, where E is the number of epochs, b is the number of blocks - a hyperparameter of PR-BCD. We have revised the text in B.2.

---

W5: SOTA

Review: The evaluated defenses are not state-of-the-art [1].

Response: We have prepared the results for three recent defense models as given below in Table 3. As the results show, Gottack has the best results in GCORN and second best results in GARNET and GCNGuard.

Table 3: Misclassification rate (↑) on CORA against the GNNGuard defense

Table 4: Misclassification rate (↑) on CORA against the GCORN defense

Table 5: Misclassification rate (↑) on CORA against the GARNET defense (we have updated the results that were previously missing at the time we submitted the response)

---

Minor: Mettack

Review: It is not clear why Metattack is mentioned in the related work, but there is no further discussion about the differences.

Response: Thank you for the review. Metattack is an adversarial attack designed for a global attack setting, where the main goal is to degrade the performance of the GNNs on the whole test set. Our GOttack, however, focuses on targeted attacks, and we leave the global attack version of GOttack as future work. We will discuss the difference between targeted and global attack methods, especially Mettack in our manuscript for the camera-ready version.

Indirect: Thank you for the review; it clarified what was meant in the earlier review. We agree with your opinion that we have not mentioned what is known about data/model and what it implies. Accordingly, we have included the following changes in the manuscript.

---

Section 4.3 (Line 292): "This work assumes access to the complete graph and its training set labels, where adversaries leverage pre-existing knowledge about the graph structure and annotations. By contrast, we do not assume access to the target model, as our primary focus is on transferable attack strategies that can generalize across models. We believe that this setting applies to domains such as social networks and transaction networks,where the graph is visible to the adversary (e.g., visible friendships on social media, visible citations on citation graphs, visible transaction values on cryptocurrencies etc.."

---

Discussion of Results (Section 5.1, Line 420): "Our empirical evaluation demonstrates that GOttack outperforms existing methods in transferability across different GNN architectures. However, we acknowledge the limitations inherent in assuming access to the entire graph and training label set. To address potential critiques of over-optimistic assumptions, we compared GOttack to adaptive attacks, which consider specific model architectures during attack generation. Results (Appendix D.3) reveal that while adaptive attacks outperform in single-model scenarios, GOttack's transferable perturbations exhibit broader applicability across diverse settings, reinforcing its utility in exploratory research on adversarial robustness."

---

Limitations (in Section 5.2, Line 513): "A notable limitation of our study is the assumption of access to complete graph and training set label information, which may not always hold in real-world scenarios. However, this assumption allows us to explore the theoretical upper bounds of adversarial transferability and provides insights into model-agnostic attack strategies. Future work could investigate relaxing these assumptions to enhance practical applicability while retaining the theoretical contributions."

---

Numbers: Thank you for pointing out the need for clarification regarding the dimensionality of GOV​. We have revised the manuscript to better explain the reasoning behind this aspect. Specifically, we elaborate on how the 73 dimensions arise from the combination of 30 graphlets and their corresponding orbit definitions, which collectively form the feature space for the graph orbit vector.

---

Replace the original paragraph: "We propose a Graph Orbit Vector (GOV) as a numerical representation of a node’s participation across different orbits in a graph. Let $GOV_v \in \mathbb{Z}^n_{\geq 0}$ be an n=73-dimensional vector. "

With: "We propose a Graph Orbit Vector (GOV) as a numerical representation of a node’s participation across different orbits in a graph. Each orbit corresponds to a distinct position within a graphlet, determined by the automorphism group of the graphlet. Specifically, for the 30 graphlets with up to 5 nodes (as defined in Kloks et al., 2000), there are a total of 73 distinct orbits. These orbits are derived from automorphisms that identify equivalent positions within each graphlet (Figure 6 in Appendix). Consequently, $GOV_v$ is an n=73-dimensional vector, where each dimension corresponds to the count of a specific orbit touched by node v. This dimensionality reflects the full set of topological positions a node can occupy across all 5-node graphlets, making it a comprehensive description of a node’s structural embedding."

---

Add a Note to Figure 6 (Appendix): "Figure 6: The 30 graphlets with 5 nodes and their corresponding 73 orbits. Each orbit represents a unique position within a graphlet as determined by its automorphism group. The total of 73 orbits corresponds to the feature dimensions of $GOV_v$."

Budget: Thank you for raising the important point regarding budget selection and its context-dependence on node degrees. We agree that the budget should ideally account for the structural properties of the graph, including node degrees. In the revised manuscript, we include a discussion on how the budget was chosen in our experiments, its implications for nodes with varying degrees, and its relationship to established settings in the literature. This will also serve as a useful reference for a current work of ours.

We evaluated four adversarial methods, including SGA, Nettack, PRBCD and our GOttack with established settings with $\epsilon$ is the relative budget w.r.t to the degree of target node $u$, i.e. $\Delta_u$ = $\epsilon * d_u$, where $d_u$ is the degree of node $u$. We have compiled the results to illustrate the impact of the epsilon budget on three datasets, as presented in Tables 3 to 5. The findings reveal that GOttack achieves the best performance in all 3 tasks on CITESEER and 2 out of 3 tasks on PUBMED. However, on CORA, GOttack secures the second-best performance in 1 out of 3 tasks.

Section 4.1: Attack Model

We will expand the paragraph discussing the budget:

"In our attack model, the budget Δ represents the maximum allowable number of perturbations to the graph structure, such as edge additions or deletions. While the choice of Δ is a critical parameter, its optimal value depends on the graph's structural properties, particularly node degrees. For nodes with low degrees, a relatively small budget (e.g., Δ=1 or Δ=2) can represent a significant structural change, whereas for nodes with very high degrees, larger budgets may be more appropriate. To balance these considerations, we adopt fixed budget values (e.g., Δ=1,...,5) that align with prior works (e.g., Nettack, FGA) and enable comparisons across models."

---

A Note to Section 5: Experiments

We will include a clarification:

"We recognize that the budget Δ affects the severity of the attack relative to a node’s degree. For example, a budget of 5 for a node with degree 2 introduces a disproportionate perturbation compared to the same budget applied to a node with degree 2000. While our experiments use fixed budgets for consistency with existing benchmarks, adaptive budget schemes that scale with degree could be explored to provide more nuanced attack scenarios. This could offer a more realistic approximation of adversarial capability in heterogeneous graphs."

---

A Subsection in the Discussion

Title: On Budget Selection and Structural Implications

"The choice of the attack budget Δ plays a pivotal role in determining the effectiveness and practicality of adversarial attacks. Fixed budgets, as employed in this study, provide consistency for benchmarking but may oversimplify real-world scenarios where the impact of a perturbation is context-dependent. For instance, a single added edge can drastically alter the local topology of a low-degree node, whereas multiple perturbations may be required to significantly affect a high-degree node. Future work could explore dynamic or adaptive budget strategies that account for the degree distribution and other structural factors, aligning the perturbation severity with the node's topological importance. Such approaches could improve the interpretability and applicability of adversarial attacks in diverse graph settings."

---

Table 3: Misclassification rate (↑) on CORA (GCN backbone)

Table 4: Misclassification rate (↑) on CITESEER (GCN backbone)

Table 5: Misclassification rate (↑) on PUBMED (GCN backbone)

We thank the reviewer for their valuable feedback, which, along with comments from others, has guided significant improvements to our paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

W1. Explicit Use of Topology in GOttack

Thank you for your question. Existing methods often manipulate node features or edges for adversarial outcomes but lack structured consideration of graph topology.

Nettack (Zügner et al., 2018) and Fast Gradient Attack (Chen et al., 2018) optimize targeted node misclassification via local adjustments without addressing the broader graph structure. SGA (Li et al., 2021) targets subgraph neighborhoods but ignores higher-order properties like orbits or equivalence classes. Methods like PRBCD may indirectly affect topology but do not explicitly leverage topological constructs such as node orbits.

GOttack’s unique advantages are multifold:

• Explicit Topology Use: GOttack employs graph orbits to identify equivalence classes of nodes. This allows for perturbations influencing a broader range of structural properties, not just immediate neighbors. For instance, targeting nodes in orbits 15 and 18, representing periphery nodes, strategically disrupts information propagation and increases misclassification rates (Section 4.3, Figure 2).
• Efficiency in Search Space: By leveraging orbits, GOttack reduces the candidate search space for edge modifications, ensuring modifications are impactful and computationally efficient. This prioritization amplifies the adversarial effect while minimizing computational costs.

While existing methods may inadvertently affect topology, GOttack’s explicit use of topological constructs offers a principled and efficient approach for enhancing attack success.

---

W2. Scalability and Practical Applicability

We appreciate your feedback regarding orbit discovery's time complexity. Orbit discovery is performed only once in pre-processing. Its time complexity is $O(|E| \times d + |V| \times d^4)$, where $d$ is the maximum node degree. As shown in Table 1, the costs are manageable for commonly used datasets.

Table 1: Orbit Discovery Time (in seconds)

For large-scale datasets like OGB-arxiv, orbit discovery can be restricted to leaf nodes ($|V_{\text{leaf}}| = 0.12|V|$), significantly reducing time complexity to $O(|E_{\text{leaf}}| \times d + |V_{\text{leaf}}| \times d^4)$.

• Dynamic Graphs: Instead of recomputing orbits from scratch, we can update orbit counts only for nodes affected by local changes (e.g., edge additions), significantly reducing computational overhead.

• Runtime: On Pubmed (19,7K nodes), orbit discovery takes 2.48 seconds. For OGB-arxiv, GOttack (including orbit discovery) ran successfully in under 23 hours, demonstrating scalability to large graphs with millions of nodes and edges. Future work will focus only on key orbits like 15 and 18.

---

W3. Specific Orbits

Thank you for pointing out these important aspects. Orbits 15 and 18 represent periphery nodes, which are particularly effective for disrupting information propagation in GNNs. If these orbits are absent, topology offers alternative candidates, such as orbits 1519 and 1922 (Appendix D). Appendix C.3 details a graph-algebra-based orbit selection scheme that generalizes GOttack to any graph topology.

---

W4. Large-Scale Experiments

Experimental results on OGB-Arxiv are given in Table 2, where GOttack demonstrates superior performance.

Table 2: Misclassification Rate (↑) on OGB-Arxiv (GCN Backbone)

---

5. Additional Reviewer Questions

Q1: Why does GOttack use 5-node graphlets? We experimented with k=3, 4 and 5-node graphlets. However, we found that k=5 yields better attacks. In particular, 5-node orbits create 73 distinct orbit types, compared to 15 orbit types from 4-node orbit and 4 from 3-node orbit (Appendix Figure 6 shows 3,4 and 5-node graphlets).Also, k=5 subsumes the k=3 and 4. Going beyond 5 incurs prohibitive orbit extraction costs.

Q2 & Q3: Does the runtime include orbit discovery? Yes, the reported runtimes are end-to-end, including orbit extraction.