{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T05:43:03Z","timestamp":1769924583345,"version":"3.49.0"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T00:00:00Z","timestamp":1708473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T00:00:00Z","timestamp":1708473600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100006831","name":"U.S. Air Force","doi-asserted-by":"publisher","award":["FA8702-15-D-0001"],"award-info":[{"award-number":["FA8702-15-D-0001"]}],"id":[{"id":"10.13039\/100006831","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006831","name":"U.S. Air Force","doi-asserted-by":"publisher","award":["FA8702-15-D-0001"],"award-info":[{"award-number":["FA8702-15-D-0001"]}],"id":[{"id":"10.13039\/100006831","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014819","name":"U.S. Army Combat Capabilities Development Command","doi-asserted-by":"publisher","award":["W911NF-13-2-0045"],"award-info":[{"award-number":["W911NF-13-2-0045"]}],"id":[{"id":"10.13039\/100014819","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014819","name":"U.S. Army Combat Capabilities Development Command","doi-asserted-by":"publisher","award":["W911NF-13-2-0045"],"award-info":[{"award-number":["W911NF-13-2-0045"]}],"id":[{"id":"10.13039\/100014819","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Northeastern University USA"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Vertex classification using graph convolutional networks is susceptible to targeted poisoning attacks, in which both graph structure and node attributes can be changed in an attempt to misclassify a target node. This vulnerability decreases users' confidence in the learning method and can prevent adoption in high-stakes contexts. Defenses have been proposed, focused on filtering edges before creating the model or aggregating information from neighbors more robustly. This paper considers an alternative: we investigate the ability to exploit network phenomena in the training data selection process to improve classifier robustness. We propose two alternative methods of selecting training data: (1) to select the highest-degree nodes and (2) to select nodes with many connections to the test data. In four real datasets, we show that changing the training set often results in far more perturbations required for a successful attack on the graph structure; often a factor of 2 over the random training baseline. We also run a simulation study in which we demonstrate conditions under which the proposed methods outperform random selection, finding that they improve performance most when homophily is higher, clustering coefficient is higher, node degrees are more homogeneous, and attributes are less informative. In addition, we show that the methods are effective when applied to adaptive attacks, alleviating concerns about generalizability.<\/jats:p>","DOI":"10.1007\/s41109-024-00611-9","type":"journal-article","created":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T07:02:20Z","timestamp":1708498940000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Complex network effects on the robustness of graph convolutional networks"],"prefix":"10.1007","volume":"9","author":[{"given":"Benjamin A.","family":"Miller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Chan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tina","family":"Eliassi-Rad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,21]]},"reference":[{"issue":"6794","key":"611_CR1","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1038\/35019019","volume":"406","author":"R Albert","year":"2000","unstructured":"Albert R, Jeong H, Barab\u00e1si AL (2000) Error and attack tolerance of complex networks. Nature 406(6794):378\u2013382","journal-title":"Nature"},{"key":"611_CR2","unstructured":"Athalye A, Carlini N (2018) On the robustness of the CVPR 2018 white-box adversarial example defenses. CoRR abs\/1804.03286"},{"key":"611_CR3","unstructured":"Athalye A, Carlini N, Wagner D (2018) Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In: ICML, pp 274\u2013283"},{"key":"611_CR4","unstructured":"Bojchevski A, G\u00fcnnemann S (2019) Certifiable robustness to graph perturbations. In: NeurIPS, pp 8317\u20138328"},{"key":"611_CR5","unstructured":"Carlini N et\u00a0al (2019) On evaluating adversarial robustness. arXiv preprint arXiv:1902.06705"},{"key":"611_CR6","doi-asserted-by":"crossref","unstructured":"Carlini N, Wagner D (2017) Towards evaluating the robustness of neural networks. In: SP, pp 39\u201357","DOI":"10.1109\/SP.2017.49"},{"key":"611_CR7","doi-asserted-by":"crossref","unstructured":"Chen L, Li J, Peng Q et\u00a0al (2021) Understanding structural vulnerability in graph convolutional networks. In: IJCAI","DOI":"10.24963\/ijcai.2021\/310"},{"key":"611_CR8","unstructured":"Chen J, Wu Y, Xu X et\u00a0al (2018) Fast gradient attack on network embedding. arXiv preprint arXiv:1809.02797"},{"key":"611_CR9","doi-asserted-by":"crossref","unstructured":"Chung FR (1997) Spectral Graph Theory. American Mathematical Soc","DOI":"10.1090\/cbms\/092"},{"key":"611_CR10","unstructured":"Croce F, Andriushchenko M, Hein M (2019) Provable robustness of relu networks via maximization of linear regions. In: AISTATS, pp 2057\u20132066"},{"key":"611_CR11","doi-asserted-by":"crossref","unstructured":"Dai E, Jin W, Liu H et\u00a0al (2022) Towards robust graph neural networks for noisy graphs with sparse labels. In: WSDM, pp 181\u2013191","DOI":"10.1145\/3488560.3498408"},{"key":"611_CR12","unstructured":"Dai H, Li H, Tian T et\u00a0al (2018) Adversarial attack on graph structured data. In: ICML, pp 1115\u20131124"},{"key":"611_CR13","unstructured":"Dapello J, Feather J, Le H et al (2021) Neural population geometry reveals the role of stochasticity in robust perception. In: Ranzato M, Beygelzimer A, Dauphin Y, et al (eds) NeurIPS, vol 34. Curran Associates, Inc., pp 15595\u201315607, https:\/\/proceedings.neurips.cc\/paper\/2021\/file\/8383f931b0cefcc631f070480ef340e1-Paper.pdf"},{"key":"611_CR14","unstructured":"Defferrard M, Bresson X, Vandergheynst P (2016) Convolutional neural networks on graphs with fast localized spectral filtering. In: Lee D, Sugiyama M, Luxburg U et\u00a0al (eds) NeurIPS, https:\/\/proceedings.neurips.cc\/paper\/2016\/file\/04df4d434d481c5bb723be1b6df1ee65-Paper.pdf"},{"key":"611_CR15","doi-asserted-by":"crossref","unstructured":"Entezari N, Al-Sayouri SA, Darvishzadeh A et\u00a0al (2020) All you need is low (rank): defending against adversarial attacks on graphs. In: WSDM, pp 169\u2013177","DOI":"10.1145\/3336191.3371789"},{"key":"611_CR16","doi-asserted-by":"publisher","first-page":"1926","DOI":"10.1109\/TIFS.2023.3256706","volume":"18","author":"A Ficara","year":"2023","unstructured":"Ficara A, Curreri F, Fiumara G et al (2023) Human and social capital strategies for mafia network disruption. IEEE Trans Inf Forensics Secur 18:1926\u20131936","journal-title":"IEEE Trans Inf Forensics Secur"},{"key":"611_CR17","unstructured":"Geisler S, Z\u00fcgner D, G\u00fcnnemann S (2020) Reliable graph neural networks via robust aggregation. In: NeurIPS, pp 13272\u201313284"},{"key":"611_CR18","unstructured":"Goodfellow IJ, Shlens J, Szegedy C (2015) Explaining and harnessing adversarial examples. In: ICLR"},{"key":"611_CR19","unstructured":"Hamilton WL, Ying Z, Leskovec J (2017) Inductive representation learning on large graphs. In: NeurIPS, pp 1025\u20131035"},{"key":"611_CR20","doi-asserted-by":"crossref","unstructured":"Jia R, Liang P (2017) Adversarial examples for evaluating reading comprehension systems. In: EMNLP, pp 2021\u20132031","DOI":"10.18653\/v1\/D17-1215"},{"key":"611_CR21","doi-asserted-by":"crossref","unstructured":"Jin W, Derr T, Wang Y et\u00a0al (2021) Node similarity preserving graph convolutional networks. In: WSDM, pp 148\u2013156","DOI":"10.1145\/3437963.3441735"},{"key":"611_CR22","unstructured":"Jin W, Li Y, Xu H et\u00a0al (2020a) Adversarial attacks and defenses on graphs: a review, a tool and empirical studies. arXiv preprint arXiv:2003.00653"},{"key":"611_CR23","doi-asserted-by":"crossref","unstructured":"Jin W, Ma Y, Liu X et\u00a0al (2020b) Graph structure learning for robust graph neural networks. In: KDD, pp 66\u201374","DOI":"10.1145\/3394486.3403049"},{"key":"611_CR24","unstructured":"Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: ICLR, https:\/\/openreview.net\/forum?id=SJU4ayYgl"},{"issue":"1","key":"611_CR25","first-page":"82","volume":"35","author":"J Li","year":"2021","unstructured":"Li J, Xie T, Liang C et al (2021) Adversarial attack on large scale graph. IEEE Trans Knowl Data Eng 35(1):82\u201395","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"611_CR26","unstructured":"Li Y, Jin W, Xu H et\u00a0al (2020) DeepRobust: A PyTorch library for adversarial attacks and defenses. arXiv preprint arXiv:2005.06149"},{"key":"611_CR27","unstructured":"Liu X, Si S, Zhu J et\u00a0al (2019) A unified framework for data poisoning attack to graph-based semi-supervised learning. NeurIPS"},{"key":"611_CR28","unstructured":"Ma Y, Wang S, Derr T et\u00a0al (2019) Attacking graph convolutional networks via rewiring. arXiv preprint arXiv:1906.03750"},{"key":"611_CR29","unstructured":"Miller BA, \u00c7amurcu M, Gomez AJ et\u00a0al (2019) Improving robustness to attacks against vertex classification. In: MLG Workshop"},{"issue":"2","key":"611_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3622941","volume":"18","author":"BA Miller","year":"2023","unstructured":"Miller BA, Shafi Z, Ruml W et al (2023) Attacking shortest paths by cutting edges. ACM Trans Knowl Discov Data 18(2):1\u201342","journal-title":"ACM Trans Knowl Discov Data"},{"key":"611_CR31","doi-asserted-by":"crossref","unstructured":"Moore J, Neville J (2017) Deep collective inference. In: AAAI, pp 2364\u20132372","DOI":"10.1609\/aaai.v31i1.10868"},{"key":"611_CR32","doi-asserted-by":"crossref","unstructured":"Moosavi-Dezfooli SM, Fawzi A, Frossard P (2016) Deepfool: a simple and accurate method to fool deep neural networks. In: CVPR, pp 2574\u20132582","DOI":"10.1109\/CVPR.2016.282"},{"key":"611_CR33","unstructured":"Mujkanovic F, Geisler S, G\u00fcnnemann S et\u00a0al (2022) Are defenses for graph neural networks robust? In: NeurIPS, https:\/\/openreview.net\/forum?id=yCJVkELVT9d"},{"key":"611_CR34","doi-asserted-by":"crossref","unstructured":"Neville J, Gallagher B, Eliassi-Rad T (2009) Evaluating statistical tests for within-network classifiers of relational data. In: ICDM, pp 397\u2013406","DOI":"10.1109\/ICDM.2009.50"},{"key":"611_CR35","doi-asserted-by":"crossref","unstructured":"Palowitch J, Tsitsulin A, Mayer B et\u00a0al (2022) GraphWorld: fake graphs bring real insights for GNNs. In: KDD, pp 3691\u20133701","DOI":"10.1145\/3534678.3539203"},{"key":"611_CR36","doi-asserted-by":"crossref","unstructured":"Papernot N, McDaniel P, Jha S et\u00a0al (2016a) The limitations of deep learning in adversarial settings. In: EuroSP, pp 372\u2013387","DOI":"10.1109\/EuroSP.2016.36"},{"key":"611_CR37","doi-asserted-by":"crossref","unstructured":"Papernot N, McDaniel P, Wu X et\u00a0al (2016b) Distillation as a defense to adversarial perturbations against deep neural networks. In: SP, pp 582\u2013597","DOI":"10.1109\/SP.2016.41"},{"key":"611_CR38","doi-asserted-by":"crossref","unstructured":"Pareja A, Domeniconi G, Chen J et al (2020) EvolveGCN: evolving graph convolutional networks for dynamic graphs. In: AAAI, pp 5363\u20135370","DOI":"10.1609\/aaai.v34i04.5984"},{"issue":"46","key":"611_CR39","doi-asserted-by":"publisher","first-page":"17916","DOI":"10.1073\/pnas.0705081104","volume":"104","author":"J Park","year":"2007","unstructured":"Park J, Barab\u00e1si AL (2007) Distribution of node characteristics in complex networks. Proc Nat Acad Sci 104(46):17916\u201317920. https:\/\/doi.org\/10.1073\/pnas.0705081104","journal-title":"Proc Nat Acad Sci"},{"key":"611_CR40","doi-asserted-by":"crossref","unstructured":"Prakash A, Moran N, Garber S et\u00a0al (2018) Deflecting adversarial attacks with pixel deflection. In: CVPR, pp 8571\u20138580","DOI":"10.1109\/CVPR.2018.00894"},{"key":"611_CR41","doi-asserted-by":"crossref","unstructured":"Sharma K, Trivedi R, Sridhar R et\u00a0al (2023) Temporal dynamics-aware adversarial attacks on discrete-time dynamic graph models. In: KDD, p 2023\u20132035","DOI":"10.1145\/3580305.3599517"},{"key":"611_CR42","unstructured":"Sun Y, Wang S, Tang X et\u00a0al (2019) Node injection attacks on graphs via reinforcement learning. arXiv preprint arXiv:1909.06543"},{"key":"611_CR43","unstructured":"Szegedy C, Zaremba W, Sutskever I et\u00a0al (2014) Intriguing properties of neural networks. In: ICLR"},{"key":"611_CR44","unstructured":"Tsipras D, Santurkar S, Engstrom L et\u00a0al (2019) Robustness may be at odds with accuracy. In: ICLR"},{"key":"611_CR45","unstructured":"Veli\u010dkovi\u0107 P, Cucurull G, Casanova A et\u00a0al (2018) Graph attention networks. In: ICLR"},{"key":"611_CR46","unstructured":"Wong E, Kolter Z (2018) Provable defenses against adversarial examples via the convex outer adversarial polytope. In: ICML, pp 5286\u20135295"},{"key":"611_CR47","unstructured":"Wu F, Souza A, Zhang T et\u00a0al (2019a) Simplifying graph convolutional networks. In: ICML, pp 6861\u20136871"},{"key":"611_CR48","doi-asserted-by":"crossref","unstructured":"Wu H, Wang C, Tyshetskiy Y et\u00a0al (2019b) Adversarial examples for graph data: deep insights into attack and defense. In: IJCAI, pp 4816\u20134823","DOI":"10.24963\/ijcai.2019\/669"},{"key":"611_CR49","unstructured":"Xie C, Wang J, Zhang Z et\u00a0al (2018) Mitigating adversarial effects through randomization. In: ICLR"},{"key":"611_CR50","doi-asserted-by":"crossref","unstructured":"Xu K, Chen H, Liu S et\u00a0al (2019) Topology attack and defense for graph neural networks: an optimization perspective. In: IJCAI, pp 3961\u20133967","DOI":"10.24963\/ijcai.2019\/550"},{"key":"611_CR51","unstructured":"Yu S, Vorobeychik Y, Alfeld S (2018) Adversarial classification on social networks. In: AAMAS, pp 211\u2013219"},{"key":"611_CR52","unstructured":"Zhang X, Zitnik M (2020) GNNGuard: Defending graph neural networks against adversarial attacks. In: NeurIPS, pp 9263\u20139275"},{"key":"611_CR53","doi-asserted-by":"crossref","unstructured":"Zhu J, Rossi RA, Rao AB et\u00a0al (2021) Graph neural networks with heterophily. In: AAAI, pp 11168\u201311176","DOI":"10.1609\/aaai.v35i12.17332"},{"key":"611_CR54","unstructured":"Zhu J, Yan Y, Zhao L et\u00a0al (2020) Beyond homophily in graph neural networks: Current limitations and effective designs. In: NeurIPS, pp 7793\u20137804"},{"key":"611_CR55","doi-asserted-by":"crossref","unstructured":"Zhu D, Zhang Z, Cui P et\u00a0al (2019) Robust graph convolutional networks against adversarial attacks. In: KDD, pp 1399\u20131407","DOI":"10.1145\/3292500.3330851"},{"key":"611_CR56","doi-asserted-by":"crossref","unstructured":"Z\u00fcgner D, Akbarnejad A, G\u00fcnnemann S (2018) Adversarial attacks on neural networks for graph data. In: KDD, pp 2847\u20132856","DOI":"10.1145\/3219819.3220078"},{"key":"611_CR57","doi-asserted-by":"crossref","unstructured":"Z\u00fcgner D, G\u00fcnnemann S (2019a) Adversarial attacks on graph neural networks via meta learning. In: ICLR","DOI":"10.24963\/ijcai.2019\/872"},{"key":"611_CR58","doi-asserted-by":"crossref","unstructured":"Z\u00fcgner D, G\u00fcnnemann S (2019b) Certifiable robustness and robust training for graph convolutional networks. In: KDD, pp 246\u2013256","DOI":"10.1145\/3292500.3330905"},{"key":"611_CR59","doi-asserted-by":"crossref","unstructured":"Z\u00fcgner D, G\u00fcnnemann S (2020) Certifiable robustness of graph convolutional networks under structure perturbations. In: KDD, pp 1656\u20131665","DOI":"10.1145\/3394486.3403217"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-024-00611-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-024-00611-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-024-00611-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,21]],"date-time":"2024-02-21T07:36:26Z","timestamp":1708500986000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-024-00611-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,21]]},"references-count":59,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["611"],"URL":"https:\/\/doi.org\/10.1007\/s41109-024-00611-9","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,21]]},"assertion":[{"value":"18 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"5"}}