research-article

Open access

Structack: Structure-based Adversarial Attacks on Graph Neural Networks

Authors:

Hussain Hussain,

Tomislav Duricic,

Markus Strohmaier,

Roman KernAuthors Info & Claims

HT '21: Proceedings of the 32nd ACM Conference on Hypertext and Social Media

Pages 111 - 120

https://doi.org/10.1145/3465336.3475110

Published: 29 August 2021 Publication History

Abstract

Recent work has shown that graph neural networks (GNNs) are vulnerable to adversarial attacks on graph data. Common attack approaches are typically informed, i.e. they have access to information about node attributes such as labels and feature vectors. In this work, we study adversarial attacks that are uninformed, where an attacker only has access to the graph structure, but no information about node attributes. Here the attacker aims to exploit structural knowledge and assumptions, which GNN models make about graph data. In particular, literature has shown that structural node centrality and similarity have a strong influence on learning with GNNs. Therefore, we study the impact of centrality and similarity on adversarial attacks on GNNs. We demonstrate that attackers can exploit this information to decrease the performance of GNNs by focusing on injecting links between nodes of low similarity and, surprisingly, low centrality. We show that structure-based uninformed attacks can approach the performance of informed attacks, while being computationally more efficient. With our paper, we present a new attack strategy on GNNs that we refer to as Structack. Structack can successfully manipulate the performance of GNNs with very limited information while operating under tight computational constraints. Our work contributes towards building more robust machine learning approaches on graphs.

Supplementary Material

MP4 File (HT21-fp044.mp4)

Presentation video

Download
38.42 MB

References

[1]

Lada A. Adamic and Natalie Glance. 2005. The Political Blogosphere and the 2004 U.S. Election: Divided They Blog. In Proceedings of the 3rd International Workshop on Link Discovery (Chicago, Illinois) (LinkKDD '05). Association for Computing Machinery, New York, NY, USA, 36--43. https://doi.org/10.1145/1134271.1134277

[2]

Sadegh Aliakbary, Jafar Habibi, and Ali Movaghar. 2014. Quantification and comparison of degree distributions in complex networks. In 7'th International Symposium on Telecommunications (IST'2014). 464--469. https://doi.org/10.1109/ISTEL.2014.7000748

[3]

Sharmodeep Bhattacharyya and Peter J Bickel. 2014. Community detection in networks using graph distance. arXiv preprint arXiv:1401.3915 (2014).

[4]

Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, Vol. 2008, 10 (2008), P10008.

[5]

Ulrik Brandes. 2001. A faster algorithm for betweenness centrality. Journal of mathematical sociology, Vol. 25, 2 (2001), 163--177.

[6]

Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. 2018. Adversarial attack on graph structured data. arXiv preprint arXiv:1806.02371 (2018).

[7]

Linton C Freeman. 1978. Centrality in social networks conceptual clarification. Social networks, Vol. 1, 3 (1978), 215--239.

[8]

Simon Geisler, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnemann. 2021. Attacking Graph Neural Networks at Scale. In Deep Learning for Graphs at AAAI Conference on Artificial Intelligence 2021, AAAI workshop 2021.

[9]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. 1024--1034.

[10]

Hussain Hussain, Tomislav Duricic, Elisabeth Lex, Roman Kern, and Denis Helic. 2020. On the Impact of Communities on Semi-supervised Classification Using Graph Neural Networks. In International Conference on Complex Networks and Their Applications. Springer, 15--26.

[11]

Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, and Jiliang Tang. 2020 a. Adversarial Attacks and Defenses on Graphs: A Review and Empirical Study. arXiv preprint arXiv:2003.00653 (2020).

[12]

Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. 2020 b. Graph Structure Learning for Robust Graph Neural Networks .Association for Computing Machinery, New York, NY, USA, 66--74. https://doi.org/10.1145/3394486.3403049

[13]

Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR).

[14]

Qimai Li, Zhichao Han, and Xiao Ming Wu. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. In 32nd AAAI Conference on Artificial Intelligence, AAAI 2018. arxiv: 1801.07606

[15]

Yang-Yu Liu, Jean-Jacques Slotine, and Albert-László Barabási. 2011. Controllability of complex networks. nature, Vol. 473, 7346 (2011), 167--173.

[16]

Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. 2020. Black-Box Adversarial Attacks on Graph Neural Networks with Limited Node Access. arXiv preprint arXiv:2006.05057 (2020).

[17]

Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang. 2019. Attacking graph convolutional networks via rewiring. arXiv preprint arXiv:1906.03750 (2019).

[18]

Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. 2000. Automating the construction of internet portals with machine learning. Information Retrieval, Vol. 3, 2 (2000), 127--163.

Digital Library

[19]

Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. 2012. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, Vol. 8.

[20]

Mark Newman. 2018. Networks .Oxford university press.

[21]

Mark EJ Newman. 2008. The mathematics of networks. The new palgrave encyclopedia of economics, Vol. 2, 2008 (2008), 1--12.

[22]

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Technical Report. Stanford InfoLab.

[23]

Tobias Schumacher, Hinrikus Wolf, Martin Ritzert, Florian Lemmerich, Jan Bachmann, Florian Frantzen, Max Klabunde, Martin Grohe, and Markus Strohmaier. 2020. The Effects of Randomness on the Stability of Node Embeddings. arXiv preprint arXiv:2005.10039 (2020).

[24]

Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine, Vol. 29, 3 (2008), 93--93.

[25]

Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of Graph Neural Network Evaluation. Relational Representation Learning Workshop, NeurIPS 2018 (2018).

[26]

Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung-Yu Hsieh, and Vasant Honavar. 2020. Adversarial Attacks on Graph Neural Networks via Node Injections: A Hierarchical Reinforcement Learning Approach .Association for Computing Machinery, New York, NY, USA, 673--683. https://doi.org/10.1145/3366423.3380149

[27]

Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. 2018. Hiding individuals and communities in a social network. Nature Human Behaviour, Vol. 2, 2 (2018), 139--147.

[28]

Felix Wu, Tianyi Zhang, Amaur Holanda de Souza, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. 2019 b. Simplifying graph convolutional networks. Proceedings of Machine Learning Research (2019).

[29]

Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. 2019 a. Adversarial examples for graph data: deep insights into attack and defense. In Proceedings of the 28th International Joint Conference on Artificial Intelligence. AAAI Press, 4816--4823.

[30]

Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. 2019. Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. International Joint Conferences on Artificial Intelligence Organization, 3961--3967. https://doi.org/10.24963/ijcai.2019/550

[31]

Muhan Zhang and Yixin Chen. 2018. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems. 5165--5175.

[32]

Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. 2019. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 1399--1407.

Digital Library

[33]

Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. 2018. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2847--2856.

Digital Library

[34]

Daniel Zügner and Stephan Günnemann. 2019. Adversarial Attacks on Graph Neural Networks via Meta Learning. In International Conference on Learning Representations. https://openreview.net/forum?id=Bylnx209YX

Cited By

Ghasemi AZeraatkar EMoradikia MZekavat S(2024)Adversarial Attacks on Graph Neural Networks Based Spatial Resource Management in P2P Wireless CommunicationsIEEE Transactions on Vehicular Technology10.1109/TVT.2024.336014573:6(8847-8863)Online publication date: Jun-2024
https://doi.org/10.1109/TVT.2024.3360145
Zhang MWang XShi CLyu LYang TDu J(2023)Minimum Topology Attacks for Graph Neural NetworksProceedings of the ACM Web Conference 202310.1145/3543507.3583509(630-640)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583509
Amjath MHenna S(2023)Rényi Differential Privacy Analysis of Graph-Based Federated Learning Under Internet of Health Things2023 31st Irish Conference on Artificial Intelligence and Cognitive Science (AICS)10.1109/AICS60730.2023.10470479(1-5)Online publication date: 7-Dec-2023
https://doi.org/10.1109/AICS60730.2023.10470479
Show More Cited By

Index Terms

Structack: Structure-based Adversarial Attacks on Graph Neural Networks
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Reinforcement learning
        Adversarial learning
    2. Machine learning approaches
      1. Neural networks

Recommendations

Graph Structure Learning for Robust Graph Neural Networks
KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Graph Neural Networks (GNNs) are powerful tools in representation learning for graphs. However, recent studies show that GNNs are vulnerable to carefully-crafted perturbations, called adversarial attacks. Adversarial attacks can easily fool GNNs in ...
Adversarial Attacks on Graph Neural Networks: Perturbations and their Patterns
Special Issue on KDD 2018, Regular Papers and Survey Paper

Deep learning models for graphs have achieved strong performance for the task of node classification. Despite their proliferation, little is known about their robustness to adversarial attacks. Yet, in domains where they are likely to be used, e.g., the ...
Explanatory subgraph attacks against Graph Neural Networks
Abstract
Graph Neural Networks (GNNs) are often viewed as black boxes due to their lack of transparency, which hinders their application in critical fields. Many explanation methods have been proposed to address the interpretability issue of GNNs. These ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

HT '21: Proceedings of the 32nd ACM Conference on Hypertext and Social Media

August 2021

306 pages

ISBN:9781450385510

DOI:10.1145/3465336

General Chair:
Owen Conlan
Trinity College Dublin, Ireland
,
Program Chair:
Eelco Herder
Radboud Universiteit Nijmegen, Netherlands

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 August 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DDAI COMET Module
TRUSTS

Conference

HT '21

Sponsor:

HT '21: 32nd ACM Conference on Hypertext and Social Media

August 30 - September 2, 2021

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 378 of 1,158 submissions, 33%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
535
Total Downloads

Downloads (Last 12 months)250
Downloads (Last 6 weeks)16

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghasemi AZeraatkar EMoradikia MZekavat S(2024)Adversarial Attacks on Graph Neural Networks Based Spatial Resource Management in P2P Wireless CommunicationsIEEE Transactions on Vehicular Technology10.1109/TVT.2024.336014573:6(8847-8863)Online publication date: Jun-2024
https://doi.org/10.1109/TVT.2024.3360145
Zhang MWang XShi CLyu LYang TDu J(2023)Minimum Topology Attacks for Graph Neural NetworksProceedings of the ACM Web Conference 202310.1145/3543507.3583509(630-640)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583509
Amjath MHenna S(2023)Rényi Differential Privacy Analysis of Graph-Based Federated Learning Under Internet of Health Things2023 31st Irish Conference on Artificial Intelligence and Cognitive Science (AICS)10.1109/AICS60730.2023.10470479(1-5)Online publication date: 7-Dec-2023
https://doi.org/10.1109/AICS60730.2023.10470479
Nair ASurendran GPrathyun KSivaprasad VPrathibhamol C(2022)Comparative study of Centrality based Adversarial Attacks on Graph Convolutional Network model for Node classification2022 7th International Conference on Communication and Electronics Systems (ICCES)10.1109/ICCES54183.2022.9835948(731-736)Online publication date: 22-Jun-2022
https://doi.org/10.1109/ICCES54183.2022.9835948
Dai JZhu WLuo X(2022)A Targeted Universal Attack on Graph Convolutional Network by Using Fake NodesNeural Processing Letters10.1007/s11063-022-10764-254:4(3321-3337)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s11063-022-10764-2

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents