-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
328 lines (279 loc) · 18 KB
/
Copy pathindex.html
File metadata and controls
328 lines (279 loc) · 18 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>GOTTACK: Universal Adversarial Attacks On Graph Neural Networks Via Graph Orbits Learning ICLR 2025 Conference</title>
<style>
body {
text-align: center;
font-family: Arial, sans-serif;
line-height: 1.6;
color: #333;
margin: 0;
padding: 0;
}
p{
margin: 0 auto;
width: 80%;
}
ul, ol, figure {
text-align: justify;
margin: 0 auto;
width: 80%;
}
main p {
text-align: justify; /* Only justify paragraphs inside <main> */
}
h1, h2, h3, h4 {
text-align: center;
}
figure {
display: flex;
justify-content: center;
align-items: center;
flex-direction: column;
}
figcaption {
margin-top: 10px;
font-style: italic;
}
header, footer {
background-color: #f8f9fa;
padding: 10px 0;
text-align: center;
}
header h1 {
margin: 0;
font-size: 24px;
color: #333;
}
footer {
display: flex; /* Flexbox ensures proper centering */
justify-content: center;
align-items: center;
text-align: center;
background-color: #f8f9fa;
width: 100%;
padding: 10px 0;
margin: 0;
box-sizing: border-box;
}
footer p {
text-align: center;
margin: 0;
font-size: 14px;
color: #666;
}
.authors {
margin-top: 10px;
font-size: 16px;
color: #555;
}
.universities {
font-size: 14px;
color: #777;
}
.buttons {
margin: 20px;
}
.button {
display: inline-block;
background-color: #333;
color: #fff;
text-decoration: none;
padding: 10px 20px;
border-radius: 20px;
font-size: 16px;
margin: 10px;
}
.button:hover {
background-color: #555;
}
.bibtex-box {
background-color: #f8f9fa;
border: 1px solid #ccc;
border-radius: 5px;
padding: 20px;
margin: 30px auto;
width: 80%;
text-align: left;
font-family: "Courier New", Courier, monospace;
color: #333;
word-wrap: break-word;
}
</style>
<!-- MathJax for LaTeX Math Rendering -->
<script type="text/javascript" async
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.2/es5/tex-mml-chtml.js">
</script>
</head>
<body>
<!-- Header -->
<header>
<h1>GOttack: Universal Adversarial Attacks on Graph Neural Networks via Graph Orbits Learning
<a href="https://iclr.cc/" target="_blank" style="color: inherit; text-decoration: none;">ICLR 2025 Conference</a>
</h1>
</header>
<!-- Authors Section -->
<div style="text-align: center; margin-top: 20px; margin-bottom: 20px;">
<p style="font-size: 18px; line-height: 1.6;">
Zulfikar Alom<sup>1</sup>, Tran Gia Bao Ngo<sup>1</sup>, Murat Kantarcioglu<sup>2</sup>, Cuneyt Gurcan Akcora<sup>3</sup>
</p>
<p style="font-size: 16px; line-height: 1.4;">
<sup>1</sup>University of Manitoba, <sup>2</sup>Virginia Tech, <sup>3</sup>University of Central Florida
</p>
</div>
<!-- Buttons -->
<div class="buttons">
<a href="https://github.com/cakcora/GOttack" class="button" target="_blank">Code</a>
<a href="https://github.com/cakcora/GOttack/tree/master/dataset" class="button" target="_blank">Dataset</a>
<a href="https://arxiv.org" class="button" target="_blank">arXiv</a>
</div>
<!-- Main Content -->
<main>
<h2>Abstract</h2>
<p>Graph Neural Networks (GNNs) have demonstrated superior performance in node classification tasks across diverse applications. However, their vulnerability to adversarial attacks, where minor perturbations can mislead model predictions, poses significant challenges. This study introduces GOttack, a novel adversarial attack framework that exploits the topological structure of graphs to undermine the integrity of GNN predictions systematically. </p>
<p>By defining a topology-aware method to manipulate graph orbits, our approach generates adversarial modifications that are both subtle and effective, posing a severe test to the robustness of GNNs. We evaluate the efficacy of GOttack across multiple prominent GNN architectures using standard benchmark datasets. Our results show that GOttack outperforms existing state-of-the-art adversarial techniques and completes training in approximately 55% of the time required by the fastest competing model, achieving the highest average misclassification rate in 155 tasks.
This work not only sheds light on the susceptibility of GNNs to structured adversarial attacks but also shows that certain topological patterns may play a significant role in the underlying robustness of the GNNs.</p>
<h2>Problem Statement</h2>
<p>Consider an initial graph
\( \mathcal{G} = (\mathcal{A}, \mathcal{X}) \), a target node
\( v \), and its true class \( y_v \). Our goal is to modify the graph's structure such that the classification of
\( v \) changes from \( y_v \) to \( y_{v^\prime} \), where \( y_v \neq y_{v^\prime} \), thereby maximizing the difference from its original classification. The proposed attacks can be mathematically formulated as a bi-level optimization problem:</p>
</p>
<p>
\[
\arg \max_{(\mathcal{A}', \mathcal{X}) \in \mathcal{G'}} \max_{y_{v^\prime} \neq y_v} \ln Z^*_{v,y_{v^\prime}} - \ln Z^*_{v,y_v}
\]
</p>
<p>
where \( \mathbf{Z}^* = f_{\theta^*}(\mathcal{A}', \mathcal{X}) \) and
\( \theta^* = \arg \min_{\theta} \mathcal{L}(\theta; \mathcal{A}', \mathcal{X}) \) subject to the budget constraint. Specifically, we aim to find a modified graph
\( \mathcal{G}' = (\mathcal{A}', \mathcal{X}) \) in which the target node
\( v \) is assigned a label \( y_{v^\prime} \) that maximizes the difference from its original label \( y_v \) in terms of probability scores.
</p>
<h2>Graphlet and Orbits</h2>
<p>We compute Graph Orbit Vectors from all graphlets to develop a multi-orbit based attack strategy.</p>
<p><strong>Graphlet.</strong> A graphlet \(G_{gp}\) within a larger graph \(G = (V, E, X)\) is a connected induced subgraph \(Gs' = (V', E', X')\), where \( V' \subseteq V \), and E' includes all edges \(e_{uv} \in E\) with both u and v in V', and |V'| typically equals 5.</p>
<p><strong>Orbits.</strong> Orbits are defined by automorphisms of the graphlet. An automorphism σ of a graphlet \( G_{gp} \) satisfies \( \sigma(G_{gp}) = G_{gp} \). Nodes \( v \) and \( w \) in \( V \) are considered similar if there exists an automorphism σ such that \( \sigma(v) = w \). The orbit of a node \( v \), denoted by \( \text{Orb}(G_{gp}, v) \), is the set of all nodes \( w \in V \) that can be mapped onto \( v \) by some automorphism of the graphlet.</p>
<p> Mathematically, orbit of a node \( v \), denoted by \( \text{Orb}(\mathcal{G}_{gp}, v) \), is defined as:
\(
\text{Orb}(\mathcal{G}_{gp}, v) = \left\{ w \in \mathcal{V} \,\middle|\, \sigma \in \text{Aut}(\mathcal{G}_{gp}) : \sigma(v) = w \right\}.
\).
Here, \( \text{Aut}(\mathcal{G}_{gp}) \) represents the group of automorphisms of the graphlet \( \mathcal{G}_{gp} \). Each orbit is denoted by \( \text{Orb}_j \), where \( j \) is a unique identifier corresponding to a specific orbit within the graphlet.
</p>
<p>
A node \( v \) is said to <em>touch</em> an orbit \( \text{Orb}_j \) if it is part of an induced subgraph in the graph and belongs to \( \text{Orb}_j \). A node may appear in multiple graphlets and therefore can belong to multiple orbits.
</p>
<p>
For example, in Figure 1, node \( x \) appears in graphlets with node sets \( \{x, v, k, l, w\} \) and \( \{x, v, k, y, l\} \), among others.
</p>
<p>
In total, the 30 distinct graphlets generate \(\mathbf{73}\) <strong>distinct orbits</strong>. The number of graphlets and corresponding orbits is uniquely determined by the choice of using 5-node graphlets.
</p>
<p><strong>Graph Orbit Vector.</strong> A numerical representation of a node’s participation across the 73 orbits in a graph. Consequently, \(GOV_v\) a node 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. </p>
<div style="display: flex; justify-content: center; gap: 1px; align-items: flex-start;">
<figure style="text-align: center; width: 15%;">
<img src="figs/motif.png" alt="Motif" style="width: 100%;">
<figcaption>Figure 1. A toy graph where shared node colors imply similar orbit counts. Nodes u, z, and w have 15 and 18 orbits, respectively.</figcaption>
</figure>
<figure style="text-align: center; width: 12%;">
<img src="figs/glet.png" alt="Glet" style="width: 100%;">
<figcaption>Figure 2. Graphlets where orbits 15 and 18 are defined.</figcaption>
</figure>
</div>
<h2>Graph Structure Poisoning via Orbit Learning</h2>
<p>Our topological observation is influenced by the Mapper philosophy:</p>
<ol>
<li><strong>Orbit Proxy.</strong> Under the homophily assumption, node classification posits that graph neighbors are similar to a node in the label. Consequently, nodes in more distant positions, as can be identified by orbits, are less similar.</li>
<li><strong>Periphery Orbits.</strong> Orbits \(15\) and \(18\) indicate the topological periphery in a graph and provide a useful proxy for identifying distant nodes that differ in labels.</li>
</ol>
<p> We claim that the path distance within the graph encodes a notion of remoteness, which in turn yields minimal information about a node's label. This indicates that physical proximity within the network strongly influences the predictive accuracy regarding node labels. </p>
<p> In Theorem, we formally state that nodes located in orbits \(15\) and \(18\), due to their peripheral placement, are particularly effective for establishing paths to remote parts of the graph. This has significant implications for designing network protocols and algorithms that rely on efficient data traversal and retrieval mechanisms.</p>
<p><strong>Theorem 1 (Remote Connection Candidates).</strong> Let \( H(v, w) \) denote the expected random walk hitting time from node \( v \) to node \( w \) in \( \mathcal{G} \). For any target node \( v \in V \), nodes in orbits \(15\) and \(18\) are the most effective candidates of \( w \) for establishing paths to the most remote parts of \( \mathcal{G} \), due to their longer expected hitting times \( H(v, w) \) compared to other nodes not in these orbits.
</p>
<p>
The Periphery Orbits observation forms the backbone of our attack strategy. We identify nodes of periphery orbits (i.e., \(15\) and \(18\)) and affect the adjacency matrix (i.e., add or remove edges to these nodes) accordingly to confuse a GNN into misclassifying a target.
</p>
<p>
Consider the target node \( v \) in Figure 2. Our hypothesis posits that creating an edge from \( v \) (or any other node) to either of the orbit \(15\) or \(18\) nodes \( u \), \( z \), or \( w \) will yield the highest misclassification error in GCN. The selection among periphery nodes uses a gradient-based method, as we detail below in the surrogate loss section.
</p>
<p><strong>Orbits \( (15, 18) \).</strong> We define two ordered orbit categories based on the highest and second-highest orbit counts. The highest is given by:
\(
Orb^v_{\text{max}} = \arg\max(\text{GOV}_v)
\). If multiple orbits share this count, one is chosen arbitrarily. The second-highest is: \(
Orb^v_{\text{sec}} = \arg\max\left( \{ j \in \text{GOV}_v \mid j \neq Orb^v_{\text{max}} \} \right)
\). Each node is then assigned an orbit category:\(
Orb^v = Orb_{\text{max}} \Vert Orb_{\text{sec}}
\), where order does not matter. </p>
<h2>Experimental Setup</h2>
<p><strong>Datasets.</strong> We use three citation networks Cora, Citeseer, Pubmed and two blogs data Polblogs and BlogCatalog. </p>
<p><strong>Models.</strong> We use four SOTA models (Nettack, FGA, SGA and PRBCD) and three backbone GNNs (GCN, GIN and GraphSAGE) to evaluate adversarial attacks.</p>
<p><strong>Hardware.</strong> The experiments were conducted using Python (Version 3.8.19) and PyTorch Version 3.10.0. The computational environment was a Linux cluster equipped with an AMD Ryzen Threadripper 3960X 24-core processor, 2520GB RAM and NVIDIA RTX A6000 with 49GB RAM GPUs</p>
<h2>Experimental Results</h2>
<br>
<p> Table 1 shows the misclassification rate achieved with a single edge perturbation (addition or deletion). GOttack yields the highest misclassification rates in 7 out of 15 attack settings and ranks second in 5 other settings. SGAttack yields 4 best attacks, while PRBCD and Nettack each perform best in 2 attack settings. PRBCD, a widely used method adopted by PyTorch, yields surprisingly low rates in two datasets for GSAGE and GIN. GOttack yields the highest overall rate of 52.08, whereas the second best Nettack yields 47.02. </p>
<br>
<figure>
<img src="figs/attack_res.png" alt="Motif" style="width: 70%;">
<figcaption> Table 1. Misclassification rate (in %) (↑) of target nodes in five datasets where three backbone GNNs are attacked in node classification with budget ∆ = 1.
</figcaption>
</figure>
<br>
<figure>
<img src="figs/all_result.png" alt="Motif" style="width: 70%;">
<figcaption> Figure 3. Budgeted (∆ = 1 to 5) attack results on the Citeseer dataset.</figcaption>
</figure>
<br>
<p> In Figure 3, we gradually increase the attack budget and represent the corresponding misclassification rates on the Citeseer dataset. We observe that for GraphSAGE, GOttack yields better misclassification results, reaching a maximum misclassification score of 97% with 5 perturbations. Similarly, for the GCN and GIN models, the proposed approach attains misclassification scores of 77% and 76%, respectively, outperforming the SOTA models. </p>
<figure>
<img src="figs/dif_res.png" alt="Motif" style="width: 70%;">
<figcaption> Table 2. Misclassification rate (in %) (↑) of target nodes in different datasets against four defense models are attacked in node classification.</figcaption>
</figure>
<br>
<p> Table 2 shows the misclassification rates of the top-3 attack models on defense models with a single edge perturbation. GOttack yields the highest misclassification rates in 7 out of 16 attack settings and ranks second in 7 other settings, while SGA achieves the best performance in 7 attack settings. GOttack achieves the highest overall rate of 33.07, whereas SGA has a rate of 32.5. </p>
<br>
<figure>
<img src="figs/GNNExplainer.png" alt="Motif" style="width: 60%;">
<figcaption> Figure 4. The computation graph for the targeted node 1978 from the CORA datasets, as identified by GNNExplainer. The edge (1978, 387) is added during the successful attack. Edge importances change considerably after the attack and negative class gains importance due to the newly added nodes.
</figcaption>
</figure>
<br>
<p>
<strong>Time Complexity.</strong> Orbit discovery is the primary computational cost of GOttack.
The time complexity for computing all orbits for all nodes is
<span style="white-space: nowrap;">O(|E| × d + |V| × d<sup>4</sup>)</span>,
where <span style="white-space: nowrap;">O(|V| × d<sup>4</sup>)</span> corresponds to the time required
to enumerate all five-node graphlets, and <em>d</em> denotes the maximum degree in the graph.
For instance, orbit discovery on the CORA dataset takes only <strong>0.17 seconds</strong>.
</p>
<br>
<figure>
<img src="figs/time.png" alt="Motif" style="width: 70%;">
<figcaption> Table 3. Time Experiment Results in Seconds (↓).</figcaption>
</figure>
<h2>Conclusion</h2>
<p> We have identified a key equivalence group for graph nodes based on their topological positions within the graph and demonstrated that gradient-based attack models frequently target this group in their attacks. Our approach, GOttack, introduces a seminal topological strategy in adversarial graph machine learning. By uncovering this previously unexplored vulnerability tied to graph topology, our work highlights the susceptibility of graph neural networks to topology-based attacks and paves the way for developing efficient attack models. GOttack not only enhances misclassification rates but does so in a scalable manner. For future work, we aim to study topological defenses against attack models.</p>
<br>
<p>For additional details and experimental results, please refer to our main paper. Thank you!</p>
<br><br>
</main>
<!-- BibTeX Box -->
<div class="bibtex-box" style="text-align: left; background-color: #f8f9fa; border-left: 4px solid #007acc; padding: 20px; width: 80%; margin: 20px auto;">
<h2 style="color:#2c5dff; margin-top: 0; text-align: left;">BibTeX</h2>
<pre style="margin: 0; font-family: 'Courier New', Courier, monospace; font-size: 14px; color: #333;">
@article{zulfikar2025gottack,
title={GOttack: Universal Adversarial Attacks on Graph Neural Networks via Graph Orbits Learning},
author={Zulfikar Alom, Tran Gia Bao Ngo, Murat Kantarcioglu, Cuneyt Gurcan Akcora},
journal={The Thirteenth International Conference on Learning Representations, ICLR},
year={2025}
}
</pre>
</div>
<!-- Footer -->
<footer>
<p>Accepted in ICLR 2025</p>
</footer>
</body>
</html>