# Survey on Applications of Neurosymbolic Artificial Intelligence

Djallel Bouneffouf, Charu C. Aggarwal  IBM Research
<EMAIL_ADDRESS>
New York, USA

###### Abstract

In recent years, the Neurosymbolic framework has attracted a lot of attention
in various applications, from recommender systems and information retrieval to
healthcare and finance. This success is due to its stellar performance
combined with attractive properties, such as learning and reasoning. The new
emerging Neurosymbolic field is currently experiencing a renaissance, as novel
frameworks and algorithms motivated by various practical applications are
being introduced, building on top of the classical neural and reasoning
problem setting. This article aims to provide a comprehensive review of
significant recent developments in real-world applications of Neurosymbolic
Artificial Intelligence. Specifically, we introduce a taxonomy of common
Neurosymbolic applications and summarize the state-of-the-art for each of
those domains. Furthermore, we identify important current trends and provide
new perspectives pertaining to the future of this burgeoning field.

###### Index Terms:

Neurosymbolic AI, Learning, Reasoning, neural logical, Logical Neural Networks

##  I Introduction

Neuro-Symbolic artificial intelligence focuses on bringing together the neural
and the symbolic traditions in AI. Here, the term “neural” refers to the use
of artificial neural networks and symbolic refers to the use of explicit
symbol manipulation through formal logic. These fields have traditionally been
separate, although recent years have seen the benefit of bringing them
together in order to gain the best of both worlds.

Many practical applications require learning and reasoning abilities — on the
neural side, the desirable strengths would include learning from raw data,
while on the symbolic side one would like to retain the natural explanatory
power of these systems. Examples of such applications include medical
diagnosis [1], recommender systems [2] and text-mining [1], as well as the
ease of making use of deep human expert knowledge in their design and
function.

The drawbacks of neural networks lie in their inability to provide an
explanation of the underlying reasoning mechanisms, which results in their
being considered black-box models [3]. Symbolic systems can explain their
inference process and use powerful declaration languages for knowledge
representation. They allow explicit control, fast initial coding, dynamic
variable binding, and knowledge abstraction [4]. Problems of symbolic systems
are their inability to handle incomplete information and to generalize.

On the one hand, there are rule based systems, which require a lot of work in
system development and adaptation. On the other hand there are supervised
machine learning approaches, that require a lot of learning samples.

In terms of functional features, by utilizing symbolic approaches in
combination with deep learning, one would hope to do better on issues like
training from small data sets, recovery from errors, and in general,
explainability, as opposed to systems that rely on deep learning alone.

We will now provide an extensive overview including various applications of
the Neurosymbolic framework, both in real-life problem setting arising in
multiple practical domains (healthcare, computer network routing, finance, and
beyond), as well as in computer science and machine-learning in particular.

##  II Real-Life Applications of Neurosymbolic

As a general mathematical framework, the Neurosymbolic setting addresses the
following challenges:

##  III Healthcare

Artificial intelligence and machine learning methods offer a lot of promise in
medicine. In the health domain, the challenge is to build a transparent
artificial intelligence. Among the fields which use AI techniques, is Drug
Repurposing (DR) which involves finding a new indication for an existing drug.
In this work[5], authors describe the use of neuro-symbolic algorithm in order
to explain the process of link prediction in a knowledge graph-based
computational drug repurposing. Link prediction consists of generating
hypotheses about the relationships between a known molecule and a given
target.

Author work done in [6] propose a novel probabilistic programmed deep kernel
learning approach that works well in predicting cognitive decline in
Alzheimer’s disease. The authors shows that the proposed method is a powerful
tool in neurodegenerative disease diagnosis and prognostic modeling and they
suggest that the system will perform well in other disease areas.

The neuro-symbolic approach has advantageous medical-AI characteristics such
as data-efficiency, model and prediction interpretability. At a higher level,
they have compared two per spectives on AI-based longitudinal disease
modeling: data driven with neural networks, and domain-engineered with
probabilistic programs.

##  IV Image Processing

Efficient multimedia event processing is a key enabler for real-time and
complex decision making in streaming media. The need for expressive queries to
detect high-level human understandable spatial and temporal events in
multimedia streams is inevitable due to the explosive growth of multimedia
data in smart cities and internet [7]. The recent work in visual [7],
reasoning inspires the integration of visual and commonsense reasoning in
multimedia processing. This work discuss why techniques integrating
connectionist and symbolic paradigms are the most efficient solutions to
produce explanations and propose a reasoning model, to explain a neural
network’s decision and use explanation in order to correct bias.

##  V Business Management

The complexity of current organization systems, and the increase in importance
of the realization of internal controls in firms, make it necessary to
construct models that automate and facilitate the work of auditors.

Authors in [8] developed a system to automate the internal control process.
This system is composed of two case-based reasoning systems. The objective of
the system is to facilitate the process of internal auditing in small and
medium firms from the textile sector. The system, analyses the data that
characterises each one of the activities carried out by the firm, then
determines the state of each activity, calculates the associated risk, detects
the erroneous processes, and generates recommendations to improve these
processes.

The system is a useful tool for the internal auditor in order to make
decisions based on the risk generated. Each one of the case-based reasoning
systems uses a different problem solving method in each of the steps of the
reasoning cycle: fuzzy clustering during the retrieval phase, a radial basis
function network and a multi-criterion discreet method during the reuse phase
and a rule based system for recommendation generation.

##  VI Brain and behavioral modeling.

Machine perception is a research field that is still in its infancy and is
confronted with many unsolved problems. In contrast, humans generally perceive
their environment without problems. These facts were the motivation to develop
a bionic model for human-like machine perception, which is based on
neuroscientific and neuropsychological research findings about the structural
organization and function of the perceptual system of the human brain. Having
systems available that are capable of a human-like perception of their
environment would allow the automation of processes for which, today, human
observers and their cognitive abilities are necessary. The challenge to be
faced is to merge and interpret large amounts of data coming from different
sources.

For this purpose, authors in [9] an information processing principle called
neuro-symbolic information processing is introduced using neuro-symbols as
basic information processing units. Neuro-symbols are connected in a modular
hierarchical fashion to a so-called neuro-symbolic network to process sensor
data. The architecture of the neuro-symbolic network is derived from the
structural organization of the perceptual system of the human brain.
Connections and correlations between neuro-symbols can be acquired from
examples in different learning phases. Besides sensor data processing, memory,
knowledge, and focus of attention influence perception to resolve ambiguous
sensory information and to devote processing power to relevant features.

##  VII Finance

Assessment is the ability of dealing with loan demands. Different loan
programs from different banks may be proposed according to the applicant’s
characteristics [10].

For these tasks, authors in [10] present the design, implementation and
evaluation of intelligent methods that assess bank loan applications where two
separate intelligent systems have been developed and evaluated: a fuzzy expert
system and a neuro-symbolic expert system. The former employs fuzzy rules
based on knowledge elicited from experts. The latter is based on neurules, a
type of neuro-symbolic rules that combine a symbolic and a connectionist
representation. Neurules were produced from available patterns.

Based on the results, we can say that synergies from using both (rule-based)
domain theory and empirical data may result in effective systems.

##  VIII Recommender Systems

Recommender System (RS) is ubiquitous on today’s Internet to provide
multifaceted personalized information services. While an enormous success has
been made in pushing forward high-accuracy recommendations, the other side of
the coin — the recommendation explainability — needs to be better handled for
pursuing persuasiveness, especially for the era of deep learning based
recommendation.

In this paper, the authors propose a model-based explainable recommendation
approach, called Neuro-Symbolic Interpretable Collaborative Filtering. the
proposed system learns interpretable recommendation rules (consisting of user
and item attributes) based on neural networks with two innovations: (1) a
three-tower architecture tailored for the user and item sides in the RS
domain; an improved architecture that is tailored for the user and item sides
in recommendation; (2) fusing the powerful personalized representations of
users and items to achieve adaptive rule weights and without sacrificing
interpretability.

Authors in [11, 12] development of mobile applications provides a considerable
amount of data of all types. In this sense, Mobile Context-aware Recommender
Systems (MCRS) suggest the user suitable information depending on her/his
situation and interests. the proposed work consists in applying machine
learning techniques and reasoning process in order to adapt dynamically the
MCRS to the evolution of the user’s interest. To achieve this goal, the
authors propose to combine bandit algorithm and case-based reasoning in order
to define a contextual recommendation process based on different context
dimensions (social, temporal and location). This paper describes a work on the
implementation of a MCRS based on a $hybrid-\epsilon-greedy$ algorithm. It
also presents results by comparing the $hybrid-\epsilon-greedy$ and the
standard $\epsilon-greedy$ algorithm.

##  IX Natural language processing

In recent years, AI research has demonstrated enormous potential for the
benefit of humanity and society. While often better than its human
counterparts in classification and pattern recognition tasks, however, AI
still struggles with complex tasks that require commonsense reasoning such as
natural language understanding. In this context, the key limitations of
current AI models are: dependency, reproducibility, trustworthiness,
interpretability, and explainability. In this work, [13] they propose a
commonsense framework that overcome these issues in sentiment analysis. They
use auto-regressive language models to build trustworthy symbolic
representations that convert natural language to a protolanguage and, extract
polarity from text.As a result, SenticNet 7 is unsupervised, reproducible,
interpretable, trustworthy, and explainable.

##  X Information Retrieval

Authors in [14, 15] development of mobile information retrieval. The proposed
work consists in applying machine learning techniques and reasoning process in
order to adapt dynamically the information retrieval system to the evolution
of the user’s interest. To achieve this goal, they propose to combine bandit
algorithm and case-based reasoning in order to define a contextual information
retrieval process based on different context dimensions (social, temporal and
location).

Part-of-speech tagging (POS) assigns grammatical tags (like noun, verb, etc.)
to a word depending on its definition and its context. It is a first step
before parsing may be applied. POS tagging has an important role in
information retrieval. Authors in [16] propose a new approach that conjoins
both, by retaining the advantages of rule based methods and of machine
learning methods. This is done by using a neural network but instead of
randomizing the weights, they initialized the network using rules that express
background knowledge.

They show that the combined system outperforms a machine learning system when
only limited samples are available. Syntactic word-class tagging, usually
assigns grammatical tags to a word, depending on its definition and its
context. There are several applications of word tagging in text mining, either
using the tags directly or by requiring the tags to become more semantically,
or simply task oriented.

They showed that the methods of neural symbolic integration can be success
fully applied in the context of POS tagging. Furthermore, they showed that the
embedding of generic background knowledge is particularly helpful if only
limited training data is available.

##  XI Language generation

Although they are currently riding a technological wave of personal
assistants, many of these agents still struggle to communicate appropriately.

Automated story generation is an area of AI research that aims to create
agents that tell good stories. Previous story generation systems use symbolic
representations to create new stories, but these systems require a vast amount
of knowledge engineering. In contrast, neural language models lose coherence
over time.

Authors in this work [17] focus on the perceived coherence of stories. Where
they created automated story generation systems that improved coherence by
leveraging various symbolic approaches for neural systems. They did by
separating semantic event generation from syntactic sentence generation,
manipulating neural event generation to make it goal-driven, improving
syntactic sentence generation to be more coherent, and creating a rule-based
infrastructure to aid neural networks in causal reasoning.

##  XII Dialogue Systems

The interpretability of task oriented dialogue systems is a big problem.
Previously, most neural-based task-oriented dialogue systems employ an
implicit reasoning strategy that makes the model predictions uninterpretable
to humans [18, 19].

To obtain a trans parent reasoning process, authors in [20] introduce neuro
symbolic to perform explicit reasoning that justifies model decisions by
reasoning chains. Since deriving reasoning chains requires multi hop reasoning
for task-oriented dialogues, Authors propose a two phase approach that
consists of a hypothesis generator and a reasoner. The system first obtain
multiple potential operations to perform the desired task, through the
hypothesis generator. Each hypothesis is then verified by the reasoner, and
the valid one is selected to conduct the final prediction.

###  XII-A Question Answering

Understanding narratives requires reasoning about implicit world knowledge
related to the causes, effects, and states of situations described in text. At
the core of this challenge is how to access contextually relevant knowledge on
demand and reason over it. In this work [21], authors present initial studies
toward zero-shot commonsense question answering by formulating the task as
inference over dynamically generated commonsense knowledge graphs. In contrast
to previous studies for knowledge integration that rely on retrieval of
existing knowledge from static knowledge graphs, the proposed system requires
commonsense knowledge integration where contextually relevant knowledge is
often not present in existing knowledge bases. Therefore, they present a novel
approach that generates contextually-relevant symbolic knowledge structures on
demand using generative neural commonsense knowledge models. Empirical results
on two datasets demonstrate the efficacy of the proposed approach for
dynamically constructing knowledge graphs for reasoning. the proposed model
approach achieves significant performance boosts over pretrained language
models and vanilla knowledge models, all while providing interpretable
reasoning paths for its predictions.

##  XIII Cyber Security

A phishing attack is defined as a type of cybersecurity attack that uses URLs
that lead to phishing sites and steals credentials and personal information.
Since there is a limitation on traditional deep learning to detect phishing
URLs from only the linguistic features of URLs, attempts have been made to
detect the misclassified URLs by integrating security expert knowledge with
deep learning [22].

Authors in [22], a genetic algorithm is proposed to find combinatorial
optimization of logic programmed constraints and deep learning from given
components, which are rule-based and neural component. The genetic algorithm
explores numerous searching spaces of combinations of rules with deep learning
to get an optimal combination of the components.

##  XIV Education System

Predicting student problem-solving strategies is a complex problem but one
that can significantly impact automated instruction systems since they can
adapt or personalize the system to suit the learner. While for small datasets,
learning experts may be able to manually analyze data to infer student
strategies, for large datasets, this approach is infeasible. Authors in [23]
develop a Machine Learning model to predict strategies from student data.
While Deep Neural Network (DNN) based methods such as LSTMs can be applied for
this task, they often have long convergence times for large datasets and like
several other DNN-based methods have the inherent problem of overfitting the
data. To address these issues, they develop a Neuro-symbolic approach for
strategy prediction, namely a model that combines strengths of symbolic AI
(that can encode domain knowledge) with DNNs. Specifically, they encode
relationships in the data using Markov Logic and use symmetries among these
relationships to train an LSTM.

##  XV  Robotic

In [24], authors outline the design of novel robotic arms using convolutional
neural networks and symbolic AI for logical control and affordance indexing.
They describe robotic arms built with a humanlike mechanical configuration and
aesthetic, with 28 degrees of freedom, touch sensors, and series elastic
actuators. The arms were modeled with URDF models, and implemented motion
control solutions for solving the casino card game, rock paper scissors, hand
shaking, and drawing. The uses of the work extend across domains, and include
arts and social human-robot interaction, as well as targeting more general co-
bot applications.

##  XVI Smart City

Smart building and smart city with innovative use cases are in need of
Artificial Intelligence (AI). However, today’s AI mainly concerns machine
learning, whereas the first years of AI were essentially about expert [25].

Authors in [25] propose to merge the two AI trends for a smart city, and point
the way towards a complete integration of the two technologies, compatible
with standard software. The city and the building are complex systems, and
developing new AI applications for urban systems calls for the merging of a
data-oriented approach (machine learning and ANN) with knowledge-based
systems, and possibly other types of models. With this objective, they argue
that a Neuro-symbolic AI software architecture able to encapsulate all kinds
of models and libraries should be based on (1) knowledge primitives at the
conceptual level, (2) a knowledge representation language (resembling frames)
for the symbolic level.

##  XVII Safe machine learning

In the recent past, reinforcement learning has seen numerous advances and
found applications in safety-critical settings [26, 27, 28, 29]. System
failures in this setting can result in loss of property. Authors in [30] takes
a step towards solving this problem by guaranteeing that RL agents do not
violate safety properties. they present REVEL, a partially neural
reinforcement learning (RL) framework for provably safe exploration in
continuous state and action spaces. The challenge here is to repeatedly verify
neural networks within a learning loop without a high computational cost. The
authors address this challenge using neurosymbolic approach with approximate
gradients. At each iteration, it safely lifts a symbolic policy into the
neurosymbolic space, performs safe gradient updates to the resulting policy,
and projects the updated policy into the safe symbolic subset, all without
requiring explicit verification of neural networks.

###  XVII-A Neurosymbolic in Real-Life Applications: Summary and Analysis

Their is different ways to bring together the neural and symbolic traditions.”
In the brief address, only a few examples were given of corresponding work. In
a much older survey from 2005 [4], work on NeSy AI was classified according to
eight dimensions, grouped into three aspects:

###  XVII-B Interrelation

(1) Integrated versus hybrid: here we are checking how the aggregation is
done, hybrid or a symbolic functionalities emerge from neural structures.

(2) Neuronal versus connectionist: here the question is whether the artificial
neural network architecture is chosen to mimic biological neural networks
versus a more technological approach that focused on computational properties.

(3) Local versus distributed: here we check how symbolic information is
represented within the neural system, one dedicated neurons for a symbolic
piece of knowledge) or a representation consists of a larger number of
activation values.

(4) Standard versus nonstandard: whether the system implement a standard
artificial neural network architectures that are widely used.

TABLE I: Neurosymbolic Interrelation for Each Domain | Integrated | Neuronal | Local | Standard
---|---|---|---|---
| vs | vs Connect- | vs Distri- | vs non-
| Hybrid | ionist | buted | Standard
Healthcare | H | C | L | S
Image processing | H | N | L | S
Business management | H | C | L | S
Brain modeling | H | N | L | S
Fiance | H | C | L | S
RS | H | C | L | S
NLP | H | N | L | S
Information Retrieval | H | C | L | S
LG | H | N | L | S
Question answering | H | N | L | S
Dialogue system | H | N | L | S
Cyber security | H | C | L | S
Education system | H | C | L | S
Robotic | H | C | L | S
Smart city | H | C | L | S
Safe machine learning | H | C | L | S

from table I we can say that most Neurosymbolic technique are hybrid approach
and standard, which mainly show a lack on the integrated technology that
combine both learning and reasoning as one component, we also do not see much
distributed work along the line of neural symbolic which could be a next
challenge.

###  XVII-C Language

\- Symbolic versus logical: whether it is based on formal logic or structured
datatypes like graphs.

\- Propositional versus first-order: whether the underlying logic is
propositional, or expressive ( quantifiers).

TABLE II: Neurosymbolic Language in each domain | symbolic | logical | Propositional | First-order
---|---|---|---|---
Healthcare | $\surd$ |  | $\surd$ |
Image processing |  | $\surd$ | $\surd$ |
Business management |  | $\surd$ | $\surd$ |
Brain modeling | $\surd$ |  | $\surd$ |
Finance |  | $\surd$ | $\surd$ |
RS |  | $\surd$ | $\surd$ |
NLP | $\surd$ |  | $\surd$ |
LG | $\surd$ |  | $\surd$ |
Information Retrieval | $\surd$ |  | $\surd$ |
Language generation |  | $\surd$ |  | $\surd$
Question answering | $\surd$ |  | $\surd$ |
Dialogue system |  | $\surd$ |  | $\surd$
Cyber security | $\surd$ |  | $\surd$ |
Education system |  |  |  |
Robotic | $\surd$ |  | $\surd$ |
Smart city | $\surd$ |  | $\surd$ |
Safe machine learning |  |  |  | $\surd$

We can say from this table that the need of first order logic is not as high
as a propositional logic. This could be explained by the simplicity of the
propositional logic.

###  XVII-D Usage

(7) Extraction versus representation: whether the information flow within the
system primarily extracts symbolic information from a neural, or it is based
on neural representations of symbolic knowledge.

(8) Learning versus reasoning: whether the system focus is on machine learning
or on automated symbolic reasoning.

TABLE III: Neurosymbolic usage for each domain | Extraction | Represent | Learning | Reasoning
---|---|---|---|---
Healthcare |  | $\surd$ | $\surd$ |
Image processing |  | $\surd$ | $\surd$ |
Business management |  | $\surd$ |  | $\surd$
Brain modeling |  | $\surd$ | $\surd$ |
Fiance | $\surd$ | $\surd$ | $\surd$ |
RS |  | $\surd$ | $\surd$ |
NLP |  | $\surd$ | $\surd$ |
Information Retrieval | $\surd$ | $\surd$ | $\surd$ |
Question answering |  | $\surd$ |  | $\surd$
Dialogue system |  | $\surd$ | $\surd$ | $\surd$
Cyber security |  | $\surd$ | $\surd$ |
Education system |  | $\surd$ | $\surd$ |
Robotic |  | $\surd$ | $\surd$ |
Smart city |  | $\surd$ |  | $\surd$
Safe machine learning |  | $\surd$ | $\surd$ |

We observe from this table that most applications are classification driven
and representation driven. This observation gives an assessment of the actual
need in term of reasoning vs classification in the different domains.

##  XVIII Conclusions

In this article, we reviewed some of the most notable recent work on
applications of Neurosymbolic AI. We summarized, in an organized way (Tables
1, Tables 2 and Tables 3), various existing applications, by types of
Neurosymbolic settings used, and discussed the advantages of using
Neurosymbolic techniques in each domain. We briefly outlines of several
important open problems and promising future extensions.

In summary, the Neurosymbolic framework, is currently very active and
promising research areas, and there are multiple novel techniques and
applications emerging each year. We hope our survey can help the reader better
understand some key aspects of this exciting field and get a better
perspective on its notable advancements and future promises.

## References

  * [1] T. Kang, A. Turfah, J. Kim, A. Perotte, and C. Weng, “A neuro-symbolic method for understanding free-text medical evidence,” Journal of the American Medical Informatics Association, vol. 28, no. 8, pp. 1703–1711, 2021.
  * [2] Y. Xian, Z. Fu, Q. Huang, S. Muthukrishnan, and Y. Zhang, “Neural-symbolic reasoning over knowledge graph for multi-stage explainable recommendation,” arXiv preprint arXiv:2007.13207, 2020.
  * [3] V. Buhrmester, D. Münch, and M. Arens, “Analysis of explainers of black box deep neural networks for computer vision: A survey,” Machine Learning and Knowledge Extraction, vol. 3, no. 4, pp. 966–989, 2021.
  * [4] R. Velik and D. Bruckner, “Neuro-symbolic networks: Introduction to a new information processing principle,” in 2008 6th IEEE International Conference on Industrial Informatics, pp. 1042–1047, IEEE, 2008.
  * [5] M. Drancé, “Neuro-symbolic xai: Application to drug repurposing for rare diseases,” in International Conference on Database Systems for Advanced Applications, pp. 539–543, Springer, 2022.
  * [6] A. Lavin, “Neuro-symbolic neurodegenerative disease modeling as probabilistic programmed deep kernels,” in International Workshop on Health Intelligence, pp. 49–64, Springer, 2021.
  * [7] A. Bennetot, J.-L. Laurent, R. Chatila, and N. Díaz-Rodríguez, “Towards explainable neural-symbolic visual reasoning,” arXiv preprint arXiv:1909.09065, 2019.
  * [8] J. M. Corchado, M. L. Borrajo, M. A. Pellicer, and J. C. Yáñez, “Neuro-symbolic system for business internal control,” in Industrial conference on data mining, pp. 1–10, Springer, 2004.
  * [9] R. Velik, “Towards human-like machine perception 2. 0,” International Review on Computers and Software, vol. 5, no. 4, pp. 476–488, 2010.
  * [10] I. Hatzilygeroudis and J. Prentzas, “Fuzzy and neuro-symbolic approaches to assessment of bank loan applicants,” in Artificial Intelligence Applications and Innovations, pp. 82–91, Springer, 2011.
  * [11] D. Bouneffouf, “Freshness-aware thompson sampling,” in Neural Information Processing - 21st International Conference, ICONIP 2014, Kuching, Malaysia, November 3-6, 2014. Proceedings, Part III (C. K. Loo, K. S. Yap, K. W. Wong, A. T. B. Jin, and K. Huang, eds.), vol. 8836 of Lecture Notes in Computer Science, pp. 373–380, Springer, 2014.
  * [12] D. Bouneffouf, A. Bouzeghoub, and A. L. Gançarski, “A contextual-bandit algorithm for mobile context-aware recommender system,” in International Conference on Neural Information Processing, pp. 324–331, Springer, 2012.
  * [13] E. Cambria, Q. Liu, S. Decherchi, F. Xing, and K. Kwok, “Senticnet 7: a commonsense-based neurosymbolic ai framework for explainable sentiment analysis,” Proceedings of LREC 2022, 2022.
  * [14] D. Bouneffouf, “Context-based information retrieval in risky environment,” Aust. J. Intell. Inf. Process. Syst., vol. 14, no. 1, 2014.
  * [15] D. Bouneffouf, A. Bouzeghoub, and A. L. Gançarski, “Contextual bandits for context-based information retrieval,” in Neural Information Processing - 20th International Conference, ICONIP 2013, Daegu, Korea, November 3-7, 2013. Proceedings, Part II (M. Lee, A. Hirose, Z. Hou, and R. M. Kil, eds.), vol. 8227 of Lecture Notes in Computer Science, pp. 35–42, Springer, 2013.
  * [16] N. C. Marques1a, S. Bader2b, V. Rocio3c, and S. Hölldobler2d, “Neuro-symbolic word tagging,” International Review on Computers and Software, 2021.
  * [17] L. J. Martin, Neurosymbolic Automated Story Generation.  PhD thesis, Georgia Institute of Technology, 2021.
  * [18] D. Bouneffouf, R. Feraud, S. Upadhyay, M. Agarwal, Y. Khazaeni, and I. Rish, “Toward skills dialog orchestration with online learning,” in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3600–3604, IEEE, 2021.
  * [19] D. Bouneffouf, R. Feraud, S. Upadhyay, I. Rish, and Y. Khazaeni, “Toward optimal solution for the context-attentive bandit problem,” in International Joint Conference on Artificial Intelligence, 2021.
  * [20] S. Yang, R. Zhang, S. Erfani, and J. H. Lau, “An interpretable neuro-symbolic reasoning framework for task-oriented dialogue generation,” arXiv preprint arXiv:2203.05843, 2022.
  * [21] A. Bosselut, R. Le Bras, and Y. Choi, “Dynamic neuro-symbolic knowledge graph construction for zero-shot commonsense question answering,” in Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021\.
  * [22] K.-W. Park, S.-J. Bu, and S.-B. Cho, “Evolutionary optimization of neuro-symbolic integration for phishing url detection,” in International Conference on Hybrid Artificial Intelligence Systems, pp. 88–100, Springer, 2021.
  * [23] A. Shakya, V. Rus, and D. Venugopal, “Student strategy prediction using a neuro-symbolic approach.,” International Educational Data Mining Society, 2021.
  * [24] D. Hanson, A. Imran, A. Vellanki, and S. Kanagaraj, “A neuro-symbolic humanlike arm controller for sophia the robot,” arXiv preprint arXiv:2010.13983, 2020.
  * [25] G. Morel, “Neuro-symbolic ai for the smart city,” in Journal of Physics: Conference Series, p. 012018, IOP Publishing, 2021.
  * [26] A. Balakrishnan, D. Bouneffouf, N. Mattei, and F. Rossi, “Incorporating behavioral constraints in online AI systems,” in The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pp. 3–11, AAAI Press, 2019.
  * [27] P. Zhao, P. Ram, S. Lu, Y. Yao, D. Bouneffouf, X. Lin, and S. Liu, “Learning to generate image source-agnostic universal adversarial perturbations,” in International Joint Conference on Artificial Intelligence, 2022.
  * [28] J. P. Epperlein, R. Overko, S. Zhuk, C. King, D. Bouneffouf, A. Cullen, and R. Shorten, “Reinforcement learning with algorithms from probabilistic structure estimation,” Automatica, vol. 144, p. 110483, 2022.
  * [29] E. Nelson, D. Bhattacharjya, T. Gao, M. Liu, D. Bouneffouf, and P. Poupart, “Linearizing contextual bandits with latent state dynamics,” in The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
  * [30] G. Anderson, A. Verma, I. Dillig, and S. Chaudhuri, “Neurosymbolic reinforcement learning with formally verified exploration,” Advances in neural information processing systems, vol. 33, pp. 6172–6183, 2020.


# Structack: Structure-based Adversarial Attacks
on Graph Neural Networks

Hussain Hussain<EMAIL_ADDRESS>Graz University of TechnologyAustria Know
Center GmbHAustria ,  Tomislav Duricic<EMAIL_ADDRESS>Graz University of
TechnologyAustria Know Center GmbHAustria ,  Elisabeth Lex
<EMAIL_ADDRESS>Graz University of TechnologyAustria ,  Denis Helic
<EMAIL_ADDRESS>Graz University of TechnologyAustria ,  Markus Strohmaier
<EMAIL_ADDRESS>RWTH AachenGermany GESIS - Leibniz
Institute for the Social SciencesGermany and  Roman Kern<EMAIL_ADDRESS>Graz
University of TechnologyAustria Know Center GmbHAustria

(2021)

###### 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.

Graph neural networks; adversarial attacks; network centrality; network
similarity

††copyright: rightsretained††journalyear: 2021††conference: Proceedings of the
32nd ACM Conference on Hypertext and Social Media; August 30-September 2,
2021; Virtual Event, Ireland††booktitle: Proceedings of the 32nd ACM
Conference on Hypertext and Social Media (HT ’21), August 30-September 2,
2021, Virtual Event, Ireland††doi: 10.1145/3465336.3475110††isbn:
978-1-4503-8551-0/21/08††ccs: Computing methodologies Machine learning††ccs:
Computing methodologies Adversarial learning††ccs: Computing methodologies
Neural networks

##  1\. Introduction

Figure 1. Illustration of Structack on GNN classification. In (a) we show a
standard GNN classification with all node features and labels available to the
algorithm. In (b) we depict an informed attack, which has access to the same
information that the GNN classification task itself has. Based on this
information, adversarial edges are added to attack GNN performance. In (c), we
show an uninformed attack strategy, i.e. an attack that has no access to
information about node attributes (labels, features), but only to the
structure of the graph. A naive strategy could add edges based on topological
graph features, for example add edges between pairs of nodes with high
centrality or high similarity. In (d), we show a Structack attack which also
has no access to information about node attributes, but attacks more
successfully by adding edges between nodes with low centrality and low
similarity. Structack approaches the performance of informed attacks such as
Metattack (Zügner and Günnemann, 2019) with less available information.

Graph neural networks (GNNs) are state-of-the-art models for tasks on graphs
such as node classification (Kipf and Welling, 2017), link prediction (Zhang
and Chen, 2018) and graph classification (Hamilton et al., 2017). Recent work
has shown that GNNs are vulnerable to adversarial attacks, which can cause
GNNs to fail by carefully manipulating node attributes (Ma et al., 2020),
graph structure (Ma et al., 2019; Zügner and Günnemann, 2019) or both (Zügner
et al., 2018). For example, adversarial attacks on social networks can add
links via fake accounts, or change the personal data of a controlled account.
Most existing attacks (Zügner et al., 2018; Zügner and Günnemann, 2019; Xu et
al., 2019; Dai et al., 2018; Ma et al., 2019; Ma et al., 2020) assume that
information about node attributes (e.g., demographics of users) are available
to the attacker. In practice however, attackers have limited access to such
attribute information. We thus differentiate between two cases: the informed
case where both graph structure and node attributes are available to the
attacker, and the uninformed case where only information about the structure
is available (see Figure 1).

#### Objectives.

In this work, we investigate _uninformed_ adversarial attacks that aim to
reduce the overall accuracy of node classification with GNNs by manipulating
the graph structure. Our aim is to study (i) potential strategies for
uninformed attacks and (ii) how effective they are in practical settings.

#### Approach.

Insights in (Zügner and Günnemann, 2019; Ma et al., 2020; Jin et al., 2020b)
have shown a considerable influence of node degree and shortest paths on GNN
robustness. However, these insights are not well investigated. Therefore, we
further inspect the effect of degree centrality and shortest path lengths on
GNN adversarial attacks. First, we theoretically show that with standard
degree normalization, low-degree neighbors surprisingly have more influence on
a node’s representation than higher-degree neighbors. Second, we discuss the
results showing the dependency of GNNs on links within graph communities (Li
et al., 2018; Hussain et al., 2020), which are ubiquitous in real-world
graphs. Based on that, we argue that adversarial edges should link nodes with
longer paths between them. Experimentally, we verify these insights on degrees
and distance through simulating attacks on empirical datasets. We then
introduce our uninformed structure-based adversarial attack (Structack), which
generalizes these findings, and injects links between nodes of low structural
centrality and similarity. Finally, we evaluate Structack compared to state-
of-the-art attacks in terms of (i) reducing GNN accuracy, (ii) computational
efficiency, and (iii) the ability to remain undetected.

#### Contribution and Impact.

We introduce Structack 111We provide the implementation Structack and the
experiments for reproducibility at https://github.com/sqrhussain/structack., a
novel structure-based uninformed adversarial attack on GNNs. In experiments on
empirical datasets, Structack performs on a level that is comparable to more
informed state-of-the-art attacks (Xu et al., 2019; Zügner and Günnemann,
2019), while using less information about the graph and significantly lower
computational requirements. We give insights on the detection of attacks, such
as Structack, by analyzing their ability to be undetected. With our work, we
introduce a new unstudied category of attacks that could be applied to real-
world networks. Our findings highlight the vulnerability of GNNs to uninformed
attacks that have no knowledge about node attributes or the attacked model.
Hence, our work contributes toward building more robust predictive and
defensive models for graph data.

##  2\. Background

Figure 2.  Impact of degree and distance on adversarial attacks on GNN
classification. Top: GNN accuracy when we link nodes of varying degrees to
other nodes of varying degrees as well, i.e., low-to-low degrees (top-left
corner) up to high-to-high (bottom-right corner). Linking nodes with lower
node degrees appears to result in more effective attacks. Bottom: GNN accuracy
when adding edges between pairs of nodes with the lowest distance up to the
highest distance. Linking nodes with higher distance (lower similarity)
results in a more effective attack. Degrees and distances are grouped into
10-quantiles. The presented accuracy comes from training a GNN model (namely
GCN(Kipf and Welling, 2017)) on the perturbed graphs of $5$ empirical
datasets.

#### Preliminaries.

Let $G=(A,X,Y)$ be an attributed undirected graph with an unweighted adjacency
matrix $A\in\\{0,1\\}^{n\times n}$, a feature matrix $X\in$IRn×f, and a label
matrix $Y\in\\{0,1\\}^{n\times|L|}$, where $L$ is the set of labels. We refer
to the set of nodes as $V=\\{1,...,n\\}$, and the set of edges as $E$, where
$|E|=m$ and $(i,j)\in E$ iff $A_{i,j}=1$. Each node $u\in V$ has a feature
vector $x_{u}\in$IRf, where $f$ is the feature vector dimension, and a label
$y_{u}\in L$. The feature vectors are encoded in $X$, where $u$’s feature
vector $x_{u}^{T}$ is the row $u$ of matrix $X$. The labels of all the nodes
are accordingly encoded in $Y$ as well, with one-hot encoding in each row. We
use the notation $D$ to refer to the degree matrix, a diagonal matrix where
$D_{i,i}=d_{i}$ is the degree of node $i$.

#### Graph neural networks.

GNNs are multi-layer machine learning models that process graph-structured
data. They follow a message passing and aggregation scheme, where nodes
aggregate the messages received from their neighbors and update their
representation on this basis. For a GNN with $K$ layers, Kipf and Welling
(2017) describe the propagation rule in a simple form as follows

(1)
$H^{\prime(k+1)}=\sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{\prime(k)}W^{(k)})$

for $k=0,1,...,K-1$, where $\tilde{A}=A+I$, $\tilde{D}=D+I$, $H^{\prime(0)}=X$
are the given node features, $W^{(k)}$ is a trainable weight matrix, and
$\sigma$ is an activation function, which is typically non-linear, e.g., ReLU.
This formula is usually written as
$H^{\prime(k+1)}=\sigma(\hat{A}H^{\prime(k)}W^{(k)})$ with
$\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$.

#### Node classification with GNNs.

For node classification, we set the activation function of the last layer of
the GNN to softmax

(2) $Z=f(\Theta;A,X)=\text{softmax}(\hat{A}H^{\prime(K-1)}W^{(K-1)}),$

where $\Theta=\\{W^{(0)},...,W^{(K-1)}\\}$ is the set of model parameters
which we aim to optimize, and $Z_{u,c}$ represents the model confidence that a
node $u$ belongs to label $c$. Given the labels of a subset of nodes
$V^{\prime}\subseteq V$, the goal of node classification is to find the labels
of the unlabeled nodes $V\setminus V^{\prime}$. To achieve this with GNNs, a
common choice is to minimize the cross entropy error in $V^{\prime}$

(3) $\mathcal{L}(Y,Z)=-\sum_{u\in V^{\prime}}{\ln Z_{u,y_{u}}},$

where $Z_{u,y_{u}}$ represents the model confidence that node $u$ belongs to
its ground-truth class $y_{u}$.

#### Adversarial attacks on GNNs.

GNNs are prone to global adversarial attacks on the graph structure (i.e., the
adjacency matrix $A$) (Jin et al., 2020a). These attacks aim to reduce the
overall (i.e., global) node classification accuracy of a GNN model. To that
end, these attacks follow different strategies to perturb the graph structure
by adding or removing up to a budget of $k$ edges.

##  3\. Impact of the structure on attacks

This section presents examples of graph structural properties and analyzes
their effect on adversarial attacks on graph structure. Findings from related
work show that node degrees have an impact on graph controllability (Liu et
al., 2011) and on the selection of targeted nodes in adversarial attacks on
node attributes (Ma et al., 2020). Besides, an analysis of Metattack (a state-
of-the-art attack) in (Zügner and Günnemann, 2019) shows a slight tendency of
the attack to link pairs of nodes with longer shortest paths (i.e., longer
distances222We refer to shortest path lengths as distances for brevity.).
However, these works do not particularly focus on the impact of node degrees
and distances on adversarial attacks or the reasoning behind it. Therefore, in
the following analysis, we study the impact of node degrees and distances on
GNNs from a theoretical perspective, and consequently verify this impact
empirically.

###  3.1. Impact of degree and distance

#### Node degree impact.

We aim to theoretically assess the role of node degree on the propagation in
GNNs (Equation 1). For this study, we investigate the common degree
normalization form as in Equation 1, i.e., normalization by the degree square
root of two adjacent nodes. Using other less common forms of degree
normalization or no degree normalization can be investigated in future work.
We first simplify the update rule given in Equation 1 by ignoring the non-
linearity in the intermediate layers, i.e., linearizing the equation (inspired
by (Zügner et al., 2018) and (Wu et al., 2019b))

(4) $H^{\prime(K)}:=\text{softmax}(H^{(K)}W)=\text{softmax}(\hat{A}^{K}XW),$

where weight matrices $W^{(k)}$ for $k\in\\{0,1,..,K-1\\}$ are absorbed by
$W=W^{(0)}W^{(1)}...W^{(K-1)}\in$IRf×|L|. We use
$H^{(k)}=\hat{A}^{k}X\in$IRn×f to represent node intermediate representations
at layer $k$ in the linearized model. Each row $u$ of matrix $H^{(k)}$,
denoted as $(h_{u}^{(k)})^{T}\in$IRf, is the intermediate representation of
node $u$ at layer $k$. As $H^{(k)}=\hat{A}H^{(k-1)}$, we can write the
representation in layer $k$ of node $u$ (i.e., $h_{u}^{(k)}$) in terms of the
representations of its neighboring nodes $\mathcal{N}(u)$ in the previous
layer $k-1$ as follows

(5)
$h_{u}^{(k)}=\sum_{v\in\mathcal{N}(u)}{\frac{1}{\sqrt{d_{u}d_{v}}}h_{v}^{(k-1)}}.\\\
$

To show the impact of the degree of a specific neighbor $w\in\mathcal{N}(u)$
on the node $u$, we compute the derivative of $u$’s final representation
$h_{u}^{(K)}$ with respect to $w$’s initial representation $h_{w}^{(0)}$
(i.e., the input features for node $w$), that is, the Jacobian matrix
$\mathbf{J}^{u,w}\in$IRf×f with $J_{i,j}^{u,w}=\partial
h_{u,i}^{(K)}/\partial h_{w,j}^{(0)}$. Equation 5 shows that the $i$-th vector
component of $h_{u}^{(k)}:k>0$ (i.e., $h_{u,i}^{(k)}$) only depends on the
vector component $h_{w,i}^{(k-1)}$ of the neighbor $w$, and not on any other
component $h_{w,j}^{(k-1)}$ with $i\neq j$333This argument is possible due to
linearizing the Equation 1.. By induction, we can show that, for
$w\in\mathcal{N}(u)$, the $i$-th vector component of $h_{u}^{(k)}$ only
depends on the $i$-th vector component of $h_{w}^{(0)}$. This fact leads to
the Jacobian matrix being diagonal. Therefore, it is sufficient to compute the
partial of an arbitrary component $i$

(6) $J_{i,i}^{u,w}=\frac{\partial h_{u,i}^{(K)}}{\partial
h_{w,i}^{(0)}}=\frac{\partial(\sum_{v\in\mathcal{N}(u)}{\frac{1}{\sqrt{d_{u}d_{v}}}h_{v}^{(k-1)}})}{\partial
h_{w,i}^{(0)}}.\\\ $

By applying the chain rule, we get

(7)
$\begin{split}J_{i,i}^{u,w}&=\sum_{v_{1}\in\mathcal{N}(u)}{\frac{1}{\sqrt{d_{u}d_{v_{1}}}}\frac{\partial
h_{v_{1},i}^{(K-1)}}{\partial h_{w,i}^{(0)}}}\\\ \end{split}$

By repeatedly applying the chain rule $K$ times, we end up at the partial of a
node’s initial representation $h_{v_{K},i}^{(0)}$ in terms of $w$’s initial
representation $h_{w,i}^{(0)}$, that is

(8) $\frac{\partial h_{v_{K},i}^{(0)}}{\partial
h_{w,i}^{(0)}}=\begin{cases}1:v_{K}=w\\\ 0:v_{K}\neq w.\end{cases}$

When we propagate this back to Equation 7, we arrive at

(9)
$\begin{split}J_{i,i}^{u,w}&=\sum_{v_{1}\in\mathcal{N}(u)}{\frac{1}{\sqrt{d_{u}d_{v_{1}}}}(...(\sum_{v_{K}\in\\{w\\}}{\frac{1}{\sqrt{d_{v_{K-1}}d_{v_{K}}}}})...)}\\\
\end{split}$

We can rewrite Equation 9 for each (not necessarily simple) path of length $K$
between $u$ and $w$, that is, with $K-1$ intermediate nodes
$[v_{1},v_{2},...,v_{K-1}]\in\texttt{Paths}(u,w,K)$, as follows

(10)
$\begin{split}J_{i,i}^{u,w}&=\frac{1}{\sqrt{d_{u}d_{w}}}\sum_{[v_{1},v_{2},...,v_{K-1}]\in\texttt{Paths}(u,w,K)}{\prod_{i=1}^{K-1}{\frac{1}{d_{v_{i}}}}}\\\
\end{split}$

This final term is $O((d_{u}d_{w})^{-1/2})$ in terms of the two neighbors
degrees. This shows that high-degree nodes have less impact on the
representations of their neighbors, and that the degree normalization is the
main reason. While the normalization is essential to reduce the bias towards
nodes with very high degree, e.g., hubs, it can also make GNNs more vulnerable
to attacks from nodes with low degrees.

#### Node distance impact.

To explain the impact of node distance on attacks, we start by discussing the
relationship between GNNs and network communities. Then we infer the role of
the distance in this context. Communities are densely connected subgraphs, and
are very common in empirical networks, e.g., social networks and co-author
networks. The GNN update rule (Equation 1) is a special form of Laplacian
smoothing (Li et al., 2018). Crucially, GNNs assume that nodes within the same
community tend to share the same label and have similar features (Hussain et
al., 2020; Li et al., 2018). This indicates that linking nodes from different
communities effectively perturbs the GNN accuracy.

Findings in (Bhattacharyya and Bickel, 2014) show that nodes within similar
communities tend to have shorter paths between them. This supports that
linking nearby nodes is likely adding intra-community links, while linking
more remote nodes is likely adding inter-community links. Therefore, we
hypothesize that linking distant nodes would result in more effective attacks.

###  3.2. Empirical validation

Table 1. Dataset statistics. Dataset | Nodes | Edges | Features | Labels
---|---|---|---|---
Citeseer (Sen et al., 2008) | 2,110 | 3,668 | 3,703 | 6
Cora (Sen et al., 2008) | 2,485 | 5,069 | 1,433 | 7
Cora-ML (McCallum et al., 2000) | 2,810 | 7,981 | 2,879 | 7
Polblogs (Adamic and Glance, 2005) | 1,222 | 16,714 | 1,490 | 2
Pubmed (Namata et al., 2012) | 19,717 | 44,325 | 500 | 3

Next, we empirically verify the hypotheses from the previous analysis on the
datasets, summarized in Table 1. We perform perturbation by adding edges to
the graph following different strategies. Then we observe the accuracy of
training a GNN model on the perturbed graph. We choose the well-known non-
linear GCN (Kipf and Welling, 2017) model444As the reader might notice, the
analysis in Section 3.1 does not only apply to this particular family of GNNs
since feature propagation and normalization are necessary components of GNNs.
Our work studies SGC models theoretically and GCN models empirically. to
empirically show that our theoretical analysis of a linearized GNN model
extends to a non-linear one. In the next experiments, we have a budget of
$k=\lfloor r\times m\rfloor$ edges to add to the graph, where $r$ is the
perturbation rate which we set to $0.05$.

#### Node degree.

The first experiment aims to compare linking low-degree nodes to linking high-
degree nodes. We group the nodes into $10$ equal-sized subsets based on their
degrees. For each pair of subsets, we try adding $k$ adversarial edges between
random pairs of nodes in the two subsets and observe the GCN accuracy. We
obtain the results in Figure 2 (top). These results support our discussion
(Section 3.1) and show an increase in accuracy, i.e., a decrease in attack
effectiveness, when linking pairs of high-degree nodes. As a result, we assume
that attacks are more effective when they link pairs of low-degree nodes.

#### Node distance.

The second experiment aims to compare linking distant pairs of nodes to
linking nearby pairs. We perform this experiment in $10$ trials, with trial
$1$ linking nodes with lowest distances and trial $10$ with highest distances.
In each trial, we observe the GCN accuracy after adding $k$ adversarial edges.
In trial $i\in\\{1,..,10\\}$, for each adversarial edge (to be added), we
randomly pick one node $u$ from the graph and attach one end of that edge to
$u$. Then, we group all the nodes in the graph into $10$ equal-sized subsets
based on their distance from $u$. Finally, we link $u$ to a random node in the
$i$-th subset. Figure 2 (bottom) depicts this comparison and shows the
accuracy of each trial. The figure suggests that linking distant nodes results
in more effective attacks than linking nearby nodes.

##  4\. Structack

In this section, we introduce our attack strategy Structack (Structure-based
attack), built upon the findings from Section 3. We outline the attacker’s
goal, capabilities and knowledge, explain the attack strategy, provide a
complexity analysis, and discuss insights on the detection of the attack.

###  4.1. Attacker’s capabilities and restrictions

In our setting, the attacker aims to minimize the overall GNN accuracy on node
classification. We limit the knowledge of the attacker to the adjacency
matrix, as opposed to existing work (Zügner et al., 2018; Zügner and
Günnemann, 2019; Xu et al., 2019; Ma et al., 2019; Dai et al., 2018; Ma et
al., 2020). The attacker has no access to the features or the label of any
node. They also do not have any information about the attacked GNN model or
its parameters. We assume that the attacker is able to add edges between any
pair of nodes555This ability might not directly translate to real-world
attacks, but it is necessary to study the extent of different attack
approaches, including the baselines that we evaluate as well. in the graph, up
to a limit $k$, called the budget. As a result, the attack generates a
poisoned adjacency matrix $A^{\prime}$, where $||A-A^{\prime}||_{0}\leq k$.
According to the taxonomy suggested by (Jin et al., 2020a), our attack is an
untargeted (global) poisoning attack on graph structure.

###  4.2. Attack strategy

The findings in Section 3 show the impact of low node degrees and long node
distances in the graph on adversarial attacks. Following these findings, an
efficient strategy to exploit this impact is to (1) select nodes with low
degrees, and (2) link pairs of nodes with high distances. Node degree is a
measure of node centrality, and distance represents one form of node
dissimilarity (e.g., Katz similarity (Newman, 2018) gives higher weights to
shorter paths). We generalize node degree and distance to a diverse set of
measures of centrality and similarity. Therefore, Structack consists of
selecting nodes with the lowest centrality and linking these nodes so that the
similarity between linked nodes is minimized.

For a budget $k$, Structack chooses $2k$ nodes with the lowest centrality. We
then split these nodes into two sets $U_{1}$ and $U_{2}$, both of size $k$,
based on their centrality, i.e., $U_{1}$ has the $k$ nodes with lowest
centrality. Then Structack finds the matching between nodes in $U_{1}$ and
$U_{2}$, which minimizes the sum of similarities between the matched nodes. To
solve this minimization problem, we use the Hungarian algorithm. Finally,
Structack adds edges between matched nodes.

For selection and linking steps, we investigate different choices of
centrality and similarity measures (Table 2). Otherwise, we follow
conventional procedures, e.g., splitting lowest-centrality nodes in order, and
using the sum of similarities as a criterion for the matching problem. Please
note, investigating other splitting and matching criteria can be interesting,
e.g., using interleaving splitting. However, we leave this for future work as
we are more interested in the impact of centrality and similarity choices.

###  4.3. Complexity analysis

After computing the centrality for each node, obtaining the $2k$ lowest-
centrality nodes for the splitting step requires $\mathcal{O}(n\log k)$ time.
At the final step of Structack, finding the optimal node matching is a minimum
cost maximum bipartite matching problem. We solve this problem using the
Hungarian algorithm, which has the complexity of $\mathcal{O}(k^{3})$ time.

In Table 2, we list the centrality and similarity measures we used with their
corresponding time and memory complexity. These measures are well defined in
the literature, along with their complexity. However, to make our paper self-
contained, we explain essential details about how we compute similarity and
give the resulting time complexity.

#### Community-based similarity:

First, we perform community detection using Louvain method (Blondel et al.,
2008), which splits the graph into $C$ disjoint communities. We then build a
community similarity matrix $\mathbf{S}\in$IRC×C encoding the original
density of edges, i.e., $\mathbf{S}_{i,j}$ represents the edge density of
links between community $i$ and community $j$. Then we set the similarity
between two nodes $u$ and $v$ to the similarity of their corresponding
communities $\mathbf{S}_{Comm(u),Comm(v)}$, where $Comm(x)$ is the community
of node $x$ as per Louvain method. For the community-based similarity, the
time complexity of Louvain community detection is considered to be linear in
the number of edges on typical and sparse data (Blondel et al., 2008)
$\mathcal{O}(m)$, and the edge density computation step is also of order
$\mathcal{O}(m)$, making this similarity calculation of order $\mathcal{O}(m)$
as well.

#### Distance-based similarity:

We use breadth-first search (BFS) to get single-source shortest paths from
each node in $U_{1}$ to all nodes in $U_{2}$ (which, in the worst case, means
to all nodes in the graph). We choose BFS because we assume that the input
graph is unweighted as mentioned in Section 2. We restrict BFS sources to
nodes in $U_{1}$ since the distance between nodes outside $U_{1}$ and $U_{2}$
are not relevant for Structack. For the shortest path length computation, and
if we do not consider parallelization, the BFS algorithm is repeated $k$ times
(once for each node in $U_{1}$), which gives a time complexity of $O(km)$.
Please note that a higher distance indicates a lower similarity.

#### Katz similarity:

This notion is a measure of regular equivalence of nodes (Newman, 2018) . It
counts paths of all lengths and weighs them differently, i.e., shorter paths
with higher weights. We can write Katz similarity matrix as
$\sum_{i=0}^{\infty}{(\alpha A)^{i}},$ where $\alpha$ is a constant which
needs to be less than the inverse of the largest eigenvalue of $A$. We
approximate the similarity matrix without matrix inversion using inverse
iteration until the matrix converges after $t$ iterations. With sparse matrix
multiplication, the time complexity turns into $\mathcal{O}(tm)$. The number
of iterations goes down to the desired precision of the similarity. For a
typical choice of $\alpha=0.85$, we obtain a precision of $10^{-6}$ with
$t=100$ iterations666This argument also applies for computing Pagerank which
is also $\mathcal{O}(tm)$..

Table 2. Description of considered centrality/similarity metrics with their time and memory complexity. We list abbreviations for the metric names to use later in results tables. $n$ and $m$ represent the number of nodes and edges in the graph respectively, and $k$ is the attack budget. $t$ is the number of iterations for computing Pagerank centrality and Katz similarity. Centrality metric | Time complexity | Memory complexity
---|---|---
Degree (DG) | $\mathcal{O}(m)$ | $\mathcal{O}(m)$
Eigenvector (EV) (Newman, 2008) | $\mathcal{O}(m)$ | $\mathcal{O}(n+m)$
Pagerank (PR) (Page et al., 1999) | $\mathcal{O}(tm)$ | $\mathcal{O}(n+m)$
Betweenness (BT) (Newman, 2008; Brandes, 2001) | $\mathcal{O}(nm)$ | $\mathcal{O}(n+m)$
Closeness (CL) (Newman, 2008; Freeman, 1978) | $\mathcal{O}(nm)$ | $\mathcal{O}(n+m)$
Similarity metric | Time complexity | Memory complexity
Katz (Katz) (Newman, 2018) | $\mathcal{O}(tm)$ | $\mathcal{O}(n^{2})$
Community-based (Comm) | $\mathcal{O}(m)$ | $\mathcal{O}(m)$
Distance-based (Dist) | $\mathcal{O}(km)$ | $\mathcal{O}(m)$

###  4.4. Insights on attack detection

Structack selects nodes with low centrality, which typically have few edges.
Therefore, the attack can cause a significant change in the degree
distribution. We hence suggest observing the changes in the degree
distribution, similar to (Zügner et al., 2018).

Moreover, Structack links pairs of nodes with low structural similarity, which
are likely to have few common neighbors. The local clustering coefficient of a
node is lower with fewer edges shared among its neighbors (Newman, 2018).
Based on that, we expect that Structack causes a significant change in the
local clustering coefficients of the nodes being linked. Therefore, we also
suggest observing the changes in the local clustering coefficient
distribution.

We define two criteria to detect the attack by comparing the original and the
perturbed graphs. First, we test if the node degrees of both graphs stem from
the same distribution. Second, we test if the local clustering coefficient
values of both graphs also stem from the same distribution. If values are
assumed to stem from the same distribution in both cases, we consider the
attack to be unnoticeable.

##  5\. Experimental evaluation

###  5.1. Adversarial attack evaluation

The goal of the experimental evaluation is to test the efficacy of Structack
perturbations on GNNs. To this end, we evaluate Structack against informed
baseline attacks as well as the random (uninformed) baseline. Notice that our
attacks as well as the evaluated baselines apply structural perturbations only
and not feature perturbations. For a perturbation rate $r$, we allow each
attack to perturb the graph by adding (or removing in case of some studied
baselines) a budget of $k=\lfloor r\times m\rfloor$ edges. We evaluate each
attack on three different criteria: (i) Effectiveness in terms of GNN
misclassification rate, (ii) Efficiency in terms of computation time and
memory requirements, and (iii) Unnoticeability in terms of changes of degree
and clustering coefficient distributions. With this evaluation, we aim to
demonstrate a performance trade-off of these three aspects.

###  5.2. Experimental setup

We evaluate $24$ different combinations of (Structack) derived from combining
$6$ different possibilities for node selection (including random selection)
with $4$ different possibilities for node linking (including random linking)
as listed in Table 2. We include random selection and random linking to
evaluate whether the effectiveness of certain centrality or similarity choices
stem from randomness. We perform the following evaluations on the $5$ datasets
described in Table 1.

#### Effectiveness.

To evaluate effectiveness (misclassification), we train a GNN model on the
perturbed graph and report the classification accuracy on its test set. Aiming
for more robust evaluation (inspired by (Shchur et al., 2018)), we use $5$
different random splits (10% train, 10% validation, and 80% test) for each
dataset. Our GNN model of choice is the well-known GCN (Kipf and Welling,
2017) model, which we initialize $5$ times with different random weights for
each perturbed input graph. For the effectiveness evaluation, we set the
perturbation rate to $0.05$.

#### Efficiency.

Another criterion for evaluating adversarial attacks is their ability to
efficiently use available resources in terms of computation time and used
memory. More efficient attacks have a lower runtime and use less memory.
Please note that we ran all experiments on a machine running Linux Ubuntu OS
version 16.04 with Intel Xeon E5-2630 Processor with 40 CPUs, 256GB RAM, and a
dedicated NVIDIA Tesla P100 16GB GPU. For these efficiency experiments, we
also set the perturbation rate to 0.05. If an attack did not fit into the GPU
memory for a particular dataset, we ran it with CPU settings for that dataset.

#### Unnoticeability.

To evaluate attack unnoticeability, we run each attack for different
perturbation rates $r\in$ {0.001, 0.002, 0.003, 0.004, 0.005, 0.0075, 0.01,
0.025,0.05, 0.075, 0.10, 0.15, 0.20}. We report results in terms of the
critical perturbation rate $r_{critical}$, i.e., largest $r$ for which the
attack is still deemed unnoticeable. We consider the attack to be unnoticeable
if the changes in the node degree and local clustering coefficient values made
by the attack are not significant. A commonly used approach for comparing two
node degree distributions is the Two-Sample Kolmogorov-Smirnov statistical
test (KS test) (Aliakbary et al., 2014). Therefore, we use the KS test to
determine whether two compared samples (original graph versus perturbed graph)
stem from the same distribution. We apply this test to obtain the significance
in change for both degree and local clustering coefficient distributions. Here
the null hypothesis of the KS test is that two samples are drawn from the same
continuous distribution. We set the probability of rejecting the null
hypothesis $\alpha$ to $0.05$.

#### Baselines.

We evaluate the most effective combinations of Structack against the following
baselines in terms of the three evaluation criteria.

Random: A simple uninformed baseline attack that selects random node pairs and
adds an edge between them. This is the only uninformed baseline against which
we compare Structack.

DICE (Waniek et al., 2018): A simple heuristic, which is explicitly based on
disconnecting nodes with the same label and connecting nodes with different
labels. This attack is informed as it has access to node labels.

Metattack (Zügner and Günnemann, 2019): State-of-the-art optimization-based
attack on graphs via meta-learning. It treats the adjacency matrix as a
parameter of the optimization problem, which is minimizing the accuracy of a
surrogate model. Metattack does not require access to the GNN model
parameters, and uses the surrogate model instead.

PGD and MinMax (Xu et al., 2019): State-of-the-art optimization-based attacks
on graphs. Both attacks apply projected gradient descent to solve the
optimization problem after convex relaxation. MinMax attempts to build a more
robust attack through attacking a re-trainable GNN. These two attacks require
access to the GNN model parameters.

In addition to the graph structure, Metattack, PGD, and MinMax have access to
the feature vectors of all nodes and the labels of some nodes (typically,
nodes in the training set). Thus, these three attacks are informed in our
definition. These attacks involve randomization, which is why we initialize
each of them $5$ times with different random weights for each attack setting.

Figure 3. Comparison of Structack combinations’ effectiveness. This plot shows
combinations from most to least effective (lowest to highest GCN
classification accuracy) presented from left to right. Thick horizontal bars
represent no significant difference between the combinations they mark. We
find that the best seven combinations are not significantly different, while
being significantly better than the rest. We also see that the stronger impact
lies in the choice of centrality with the degree and Pagerank centralities
with random linking outperforming half of the other combinations.

##  6\. Results and discussion

Next we present evaluation results, discuss trade-offs, and outline the
limitations of our work. In the results tables, we use the abbreviations
defined in Table 2 to describe the centrality and similarity measures of
Structack combinations.

#### Effectiveness.

First, we apply Structack combinations to each graph dataset and obtain the
GCN accuracy. Then we compute the average rank of each combination in terms of
classification accuracy. We visualize the ranking in Figure 3 with a critical
difference diagram. The thick horizontal bars in this figure group together
the combinations with no significant difference777For details on the
computation of significance, we refer to the documentation of the R package
scmamp https://cran.r-project.org/web/packages/scmamp/scmamp.pdf. in ranks
between them. The six lowest-ranked combinations (which involve randomness)
perform significantly worse than the rest. This confirms that the improvement
of Structack does not stem from randomness. We observe that the seven most
effective combinations are not significantly different. Among these
combinations, we frequently see Pagerank centrality, degree centrality and
Katz similarity, which implies the effectiveness of these three measures. Node
centrality in Structack has a substantial impact on effectiveness, relative to
the node similarity. For example, performing selection with degree or Pagerank
centrality and linking at random (Degree.Random and Pagerank.Random in Figure
3) seems to perform better than some combinations that do not involve random
linking.

As the seven most effective combinations do not differ significantly from each
other, we consequently compare them to the baselines as presented in Table 3.
Structack combinations show a comparable performance to state-of-the-art
methods, although they have no access to node attributes.

Table 3. Adversarial attack effectiveness. This table gives the accuracy of a GCN model trained on the perturbed graph generated by applying each adversarial attack (lower accuracy $\rightarrow$ more effective attack). Structack (in boldface) is comparable with the state-of-the-art attacks on most datasets with minimum knowledge. According to a Wilcoxon signed-rank test, each Structack approach is significantly more effective than the uninformed Random approach with $p<0.01$ (after Bonferroni correction). * Metattack could not run for Pubmed with 16GB GPU, and did not finish with CPU settings after 3 weeks running | Dataset | Citeseer | Cora | Cora-ML | Polblogs | Pubmed
---|---|---|---|---|---|---
| Clean |  71.90$\pm$1.9 |  83.44$\pm$1.1 |  85.11$\pm$0.7 |  94.66$\pm$1.2 |  86.51$\pm$0.3
Informed | DICE |  70.63$\pm$1.8 |  80.09$\pm$2.1 |  80.74$\pm$2.4 |  82.44$\pm$6.1 |  83.32$\pm$2.6
Metattack |  69.21$\pm$1.7 |  76.83$\pm$1.3 |  80.01$\pm$1.0 |  76.98$\pm$0.9 | N/A*
MinMax |  68.95$\pm$0.8 |  78.45$\pm$1.1 |  83.39$\pm$0.5 |  85.02$\pm$2.2 |  84.97$\pm$0.6
PGD |  63.80$\pm$0.9 |  75.15$\pm$1.4 |  80.17$\pm$0.7 |  83.28$\pm$3.3 |  82.58$\pm$0.4
Uninformed | Random |  72.64$\pm$1.2 |  80.56$\pm$0.5 |  82.24$\pm$0.6 |  83.57$\pm$3.4 |  85.90$\pm$0.3
BT*Katz |  71.83$\pm$1.0 |  78.77$\pm$0.5 |  80.27$\pm$0.7 |  76.41$\pm$1.8 |  84.38$\pm$0.2
DG*Comm |  71.89$\pm$0.9 |  78.51$\pm$0.6 |  80.12$\pm$0.6 |  75.65$\pm$1.3 |  84.79$\pm$0.3
DG*Dist |  71.66$\pm$1.0 |  78.80$\pm$0.5 |  80.15$\pm$0.5 |  78.87$\pm$2.0 |  84.55$\pm$0.3
DG*Katz |  71.33$\pm$1.1 |  78.98$\pm$0.5 |  80.17$\pm$0.6 |  76.27$\pm$1.4 |  84.34$\pm$0.3
PR*Comm |  71.67$\pm$1.0 |  78.85$\pm$0.5 |  80.51$\pm$0.6 |  75.25$\pm$1.4 |  84.54$\pm$0.4
PR*Dist |  71.38$\pm$1.0 |  78.53$\pm$0.5 |  80.19$\pm$0.6 |  78.09$\pm$2.2 |  84.20$\pm$0.3
PR*Katz |  71.67$\pm$1.0 |  78.40$\pm$0.5 |  80.06$\pm$0.7 |  75.99$\pm$1.6 |  84.08$\pm$0.3

#### Efficiency.

In Tables 4 and 5, we respectively show the runtime and the memory consumption
of our most effective Structack combinations and existing adversarial attack
methods. We notice a significant drop in runtime and memory consumption for
Structack compared to the optimization-based attacks (Metattack, PGD, and
MinMax). These three attacks did not fit in the available GPU memory for
Pubmed, and therefore we ran them with CPU settings for this dataset. For
Structack combinations, the similarity measure generally has a substantial
effect on runtime and memory consumption, with community-based similarity
being the most efficient. An exception to this rule is the runtime of
Betweenness and Closeness centralities. For example on Pubmed, Betweenness and
Closeness computation takes $325$ and $66$ minutes respectively, while the
computation of Katz similarity takes $100$ minutes. The time complexity of
computing these two measures (Table 2) is $\mathcal{O}(nm)$ making them
impractically slow for large graphs.

Table 4. Runtime in minutes with 0.05 perturbation rate. Structack is in boldface.  | Dataset | Citeseer | Cora | Cora-ML | Polblogs | Pubmed
---|---|---|---|---|---|---
Informed | DICE | 0.05 | 0.07 | 0.13 | 0.08 | 3.07
Metattack | 7.75 | 7.65 | 22.38 | 8.80 | N/A
MinMax | 12.83 | 13.03 | 13.68 | 12.58 | 2,645.87
PGD | 12.15 | 12.08 | 12.35 | 11.10 | 1,569.55
Uninformed | BT*Katz | 3.33 | 5.12 | 7.42 | 3.87 | 379.00
DG*Comm | 0.03 | 0.05 | 0.10 | 0.25 | 1.70
DG*Dist | 0.05 | 0.10 | 0.23 | 0.82 | 8.08
DG*Katz | 0.98 | 1.30 | 1.55 | 0.63 | 97.98
PR*Comm | 0.05 | 0.08 | 0.15 | 0.27 | 1.90
PR*Dist | 0.10 | 0.12 | 0.27 | 0.87 | 8.13
PR*Katz | 0.93 | 1.32 | 1.52 | 0.72 | 93.28
Table 5. Memory consumption in Megabytes with 0.05 perturbation rate. Structack is in boldface. * Snapshot taken after 3 weeks of running.  | Dataset | Citeseer | Cora | Cora-ML | Polblogs | Pubmed
---|---|---|---|---|---|---
Informed | DICE | 313 | 1,623 | 1,213 | 1,230 | 773
Metattack | 2,074 | 2,096 | 2,123 | 2,078 | *58,394
MinMax | 2,176 | 2,243 | 2,318 | 2,109 | 20,554
PGD | 2,155 | 2,232 | 2,299 | 2,110 | 19,779
Uninformed | BT*Katz | 578 | 626 | 677 | 442 | 13,918
DG*Comm | 316 | 322 | 337 | 403 | 901
DG*Dist | 433 | 431 | 430 | 433 | 1,995
DG*Katz | 556 | 587 | 662 | 440 | 13,918
PR*Comm | 445 | 443 | 443 | 460 | 928
PR*Dist | 445 | 443 | 442 | 450 | 2,021
PR*Katz | 570 | 617 | 668 | 441 | 13,919

#### Unnoticeability.

We report the critical perturbation rate $r_{critical}$ for which the
respective attack remains unnoticeable as per our definition in Sections 5.2.
We present $r_{critical}$ for each approach in Table 6. For most datasets,
Structack’s $r_{critical}$ is on par or slightly lower than the informed
approaches. We also observe that the choice for node selection strategy in
Structack has a greater influence on the attack unnoticeability than the node
linking strategy.

Table 6. Maximum unnoticeable perturbation rate. We evaluate unnoticeability in terms of critical perturbation rate $r_{critical}$, which we define as as the maximum perturbation rate for which the attack remains unnoticeable as per definition in Section 5.2. We present the results for $r_{critical}$ per dataset and per adversarial attack. Structack is in boldface.  | Dataset | Citeseer | Cora | Cora-ML | Polblogs | Pubmed
---|---|---|---|---|---|---
Informed | DICE | 0.0750 | 0.0500 | 0.0500 | 0.0100 | 0.0100
Metattack | 0.0100 | 0.0100 | 0.0100 | 0.0040 | N/A
MinMax | 0.0750 | 0.0750 | 0.0750 | 0.0500 | 0.0040
PGD | 0.1000 | 0.0750 | 0.0500 | 0.1000 | 0.0040
Uninformed | Random | 0.0250 | 0.0250 | 0.0250 | 0.0100 | 0.0050
BT*Katz | 0.0100 | 0.0100 | 0.0075 | 0.0020 | 0.0030
DG*Comm | 0.0100 | 0.0075 | 0.0050 | 0.0020 | 0.0030
DG*Dist | 0.0100 | 0.0075 | 0.0050 | 0.0020 | 0.0030
DG*Katz | 0.0100 | 0.0075 | 0.0050 | 0.0020 | 0.0030
PR*Comm | 0.0100 | 0.0075 | 0.0050 | 0.0020 | 0.0030
PR*Dist | 0.0100 | 0.0075 | 0.0050 | 0.0020 | 0.0030
PR*Katz | 0.0100 | 0.0075 | 0.0050 | 0.0020 | 0.0030

#### Performance trade-off.

Structack provides competitive effectiveness and high efficiency. However, it
shows to be relatively noticeable compared to baseline approaches. On the
other hand, optimization-based informed attacks achieve better unnoticeability
but with much lower efficiency compared to Structack. This low efficiency
prevents them from running on larger graphs, with Pubmed as a toy example
(this has been recently noted by Geisler et al. (2021)). A deeper look into
Structack shows that the selection strategy (i.e., centrality measure) has
more impact on effectiveness and unnoticeability. Conversely, the linking
strategy (i.e., similarity measure) has more impact on the efficiency.

All in all, we assume an attack to be effective (cause high misclassification
rate) if one of the 7 most effective combinations is picked. When running on
big graphs, attackers would tend to choose efficient combinations such as
DG$\times$Comm. To hide their behavior, attackers would tend to choose less
noticeable combinations such as BT$\times$Katz.

#### Limitations.

Our study focuses on exploiting the structure information using centrality and
similarity measures. One could study other centrality and similarity measures,
and even other graph structural properties. Moreover, instead of the
theoretical strategy defined in Section 4.2, one could define a more practical
heuristic to exploit these structural features. Furthermore, other forms of
degree normalization in the target GNN model could result in different
strategies than Structack, which is an interesting direction for future work.
However, the aim of our work is to illustrate the extent to which uninformed
attacks are successful, and we demonstrate that through our Structack
strategy, which covers a range of possibilities of uninformed attacks.

Our unnoticeability measure was limited to degree and clustering coefficient
distributions. Different unnoticeability tests could be investigated for this
purpose. In this regard, Structack appears more noticeable than existing
informed attacks due to its greediness in selecting nodes with lowest
centrality. The unnoticeability results motivate us to look into approaches
that intrinsically consider both effectiveness and unnoticeability. More
careful selection could improve Structack’s unnoticeability, at the possible
cost of effectiveness.

Additionally, comparing distributions of the clean graph and the perturbed one
is not practical for dynamic networks, where edges and nodes are added and
removed constantly. This comparison does not consider the natural growth of
the network. This type of comparison is a common practice in works on
adversarial attacks on graphs, and it should be improved. This could be
alleviated by using graph growth models or dedicated datasets with edge
timestamps.

##  7\. Related work

#### Information available to attackers.

Many recent works have introduced attack models for GNNs with different
knowledge and capabilities. These models adhere to various restrictions on the
practicality of the adversarial attacks and the limitations of the attacker.
However, the majority of these models assume the attacker’s knowledge of the
targeted GNN model (Xu et al., 2019; Wu et al., 2019a) or their access to node
attributes (Ma et al., 2020; Zügner and Günnemann, 2019; Zügner et al., 2018;
Sun et al., 2020), i.e., feature vectors and some labels. We have referred to
such adversarial attacks as informed attacks. A recent survey (Jin et al.,
2020a) describes the level of knowledge of (i) the targeted GNN model and (ii)
graph data as one characteristic of the attack. Our work differentiates
between these two descriptions and focuses on the knowledge of graph data
regardless of the knowledge of the targeted model.

#### Node centrality.

Earlier findings in network science on controlling complex networks (Liu et
al., 2011) show that fewer nodes are needed to control the network, if one
aims to control nodes with low degrees. Another study about the stability of
node embedding (Schumacher et al., 2020) shows that high-centrality nodes have
more stable embeddings compared to low-centrality nodes. In the context of
GNNs, Metattack(Zügner and Günnemann, 2019) shows a slight tendency to connect
nodes with low degree. Zhu et al. (2019) experimentally consider attacks on
nodes with higher than $10$ degrees for noticeability considerations. Ma et
al. (2020) introduce practical adversarial attacks by targeting nodes with
high importance score, e.g., PageRank, node degree, and betweenness. The
authors argue that nodes with too high importance score, e.g., hubs, are hard
to control, hence the attack approach avoids such nodes. Our work conversely
builds theoretical grounds and experimental support to show that attacks are
more effective if they focus on low degree nodes.

#### Node similarity.

A study on the behavior of GNNs (Li et al., 2018) shows that feature and label
smoothness are the reason why GNNs work. Some works on GNN adversarial attacks
(Jin et al., 2020a, b) analyze the poisoned graphs of popular attack models
and show a tendency of the attackers to add edges between nodes with different
labels and low-similarity features. Waniek et al. (2018) introduce an attack
that is explicitly based on disconnecting nodes with the same label and
connecting nodes with different labels (Disconnect Internally, Connect
Externally - DICE). More insights on structure in Metattack (Zügner and
Günnemann, 2019) suggest that attacks tend to link pairs of nodes with higher-
than-average shortest path length. Finally, a preprocessing-based defense
mechanism for GNNs (Wu et al., 2019a) is based on reducing the weight of edges
between nodes with a low Jaccard similarity score of their features. Our work
builds on these findings to investigate more in structural node similarity and
build an uninformed structure-based adversarial attack strategy.

##  8\. Conclusion

We investigated the effectiveness of uninformed adversarial attacks on GNNs,
i.e. attacks that have no access to information about node labels or feature
vectors in a graph. With theoretical considerations and experimental support,
we demonstrated that uninformed attacks can exploit structural features of the
graph, such as node centrality and similarity. We presented Structack, a novel
uninformed attack strategy that selects nodes with low centrality and links
pairs of nodes with low similarity. In experiments on five graph datasets
Structack showed comparable performance to state-of-the-art attacks, while
having less information about the graph (no access to node attributes),
exhibiting higher efficiency, and reasonable unnoticeability. Our work shows
that uninformed adversarial attacks are successful with only structural
knowledge, sometimes outperforming informed attacks. The feasibility of
Structack on real-world graphs makes it vital to develop more structure-aware
defense mechanisms for more reliable GNN prediction.

## Acknowledgements

The Know‐Center is funded within the Austrian COMET Program – Competence
Centers for Excellent Technologies – under the auspices of the Austrian
Federal Ministry of Transport, Innovation and Technology, the Austrian Federal
Ministry of Economy, Family and Youth and by the State of Styria. COMET is
managed by the Austrian Research Promotion Agency FFG. This work is supported
by the H2020 project TRUSTS (GA: 871481) and the “DDAI” COMET Module within
the COMET Program, funded by the Austrian Federal Ministry for Transport,
Innovation and Technology (bmvit), the Austrian Federal Ministry for Digital
and Economic Affairs (bmdw), the Austrian Research Promotion Agency (FFG), the
province of Styria (SFG) and partners from industry and academia.

## References

  * (1)
  * Adamic and Glance (2005) 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
  * Aliakbary et al. (2014) 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
  * Bhattacharyya and Bickel (2014) Sharmodeep Bhattacharyya and Peter J Bickel. 2014.  Community detection in networks using graph distance.  _arXiv preprint arXiv:1401.3915_ (2014).
  * Blondel et al. (2008) 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_ 2008, 10 (2008), P10008.
  * Brandes (2001) Ulrik Brandes. 2001\.  A faster algorithm for betweenness centrality.  _Journal of mathematical sociology_ 25, 2 (2001), 163–177.
  * Dai et al. (2018) 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).
  * Freeman (1978) Linton C Freeman. 1978\.  Centrality in social networks conceptual clarification.  _Social networks_ 1, 3 (1978), 215–239.
  * Geisler et al. (2021) 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_.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs. In _Advances in Neural Information Processing Systems_. 1024–1034.
  * Hussain et al. (2020) 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.
  * Jin et al. (2020a) Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, and Jiliang Tang. 2020a.  Adversarial Attacks and Defenses on Graphs: A Review and Empirical Study.  _arXiv preprint arXiv:2003.00653_ (2020).
  * Jin et al. (2020b) Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. 2020b.  _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
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _International Conference on Learning Representations (ICLR)_.
  * Li et al. (2018) 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
  * Liu et al. (2011) Yang-Yu Liu, Jean-Jacques Slotine, and Albert-László Barabási. 2011\.  Controllability of complex networks.  _nature_ 473, 7346 (2011), 167–173.
  * Ma et al. (2020) 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).
  * Ma et al. (2019) Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, and Jiliang Tang. 2019.  Attacking graph convolutional networks via rewiring.  _arXiv preprint arXiv:1906.03750_ (2019).
  * McCallum et al. (2000) Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. 2000.  Automating the construction of internet portals with machine learning.  _Information Retrieval_ 3, 2 (2000), 127–163.
  * Namata et al. (2012) 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.
  * Newman (2018) Mark Newman. 2018\.  _Networks_.  Oxford university press.
  * Newman (2008) Mark EJ Newman. 2008\.  The mathematics of networks.  _The new palgrave encyclopedia of economics_ 2, 2008 (2008), 1–12.
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999.  _The PageRank citation ranking: Bringing order to the web._ Technical Report. Stanford InfoLab.
  * Schumacher et al. (2020) 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).
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008\.  Collective classification in network data.  _AI magazine_ 29, 3 (2008), 93–93.
  * Shchur et al. (2018) Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018\.  Pitfalls of Graph Neural Network Evaluation.  _Relational Representation Learning Workshop, NeurIPS 2018_ (2018).
  * Sun et al. (2020) 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
  * Waniek et al. (2018) Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. 2018.  Hiding individuals and communities in a social network.  _Nature Human Behaviour_ 2, 2 (2018), 139–147.
  * Wu et al. (2019b) Felix Wu, Tianyi Zhang, Amaur Holanda de Souza, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. 2019b.  Simplifying graph convolutional networks.  _Proceedings of Machine Learning Research_ (2019).
  * Wu et al. (2019a) Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. 2019a.  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.
  * Xu et al. (2019) 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
  * Zhang and Chen (2018) Muhan Zhang and Yixin Chen. 2018.  Link prediction based on graph neural networks. In _Advances in Neural Information Processing Systems_. 5165–5175.
  * Zhu et al. (2019) 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.
  * Zügner et al. (2018) 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.
  * Zügner and Günnemann (2019) 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

##  Appendix A Detailed effectiveness results

Table shows the accuracy of GCN (Kipf and Welling, 2017) for node
classification on the considered datasets after changing the structure using
different combinations of Structack with a perturbation rate $r=0.05$. These
are the detailed results of what Figure 3 summarizes.

Table 7. GCN accuracy on each dataset after applying Structack with each centrality$\times$similarity combination. The lowest accuracy (best combination) in each dataset is shown in boldface. | Similarity | Community | Distance | Katz | Random
---|---|---|---|---|---
Dataset | Centrality |  |  |  |
Citeseer | Betweenness |  72.06$\pm$0.9 |  72.04$\pm$1.0 |  71.83$\pm$1.0 |  72.22$\pm$1.0
Closeness |  72.75$\pm$0.7 |  71.99$\pm$1.0 |  72.22$\pm$1.1 |  72.88$\pm$1.1
Degree |  71.89$\pm$0.9 |  71.66$\pm$1.0 | 71.33$\pm$1.1 |  71.86$\pm$0.9
Eigenvector |  72.44$\pm$1.1 |  72.55$\pm$0.8 |  72.46$\pm$1.3 |  73.05$\pm$0.8
Pagerank |  71.67$\pm$1.0 |  71.38$\pm$1.0 |  71.67$\pm$1.0 |  72.18$\pm$0.7
Random |  73.08$\pm$1.1 |  73.08$\pm$1.1 |  73.04$\pm$0.9 |  72.64$\pm$1.2
Cora | Betweenness |  79.05$\pm$0.5 |  79.11$\pm$0.4 |  78.77$\pm$0.5 |  79.65$\pm$0.5
Closeness |  79.99$\pm$0.4 |  79.99$\pm$0.6 |  79.57$\pm$0.5 |  80.33$\pm$0.4
Degree |  78.51$\pm$0.6 |  78.80$\pm$0.5 |  78.98$\pm$0.5 |  79.63$\pm$0.5
Eigenvector |  80.19$\pm$0.5 |  79.80$\pm$0.5 |  79.93$\pm$0.6 |  80.53$\pm$0.5
Pagerank |  78.85$\pm$0.5 |  78.53$\pm$0.5 | 78.40$\pm$0.5 |  78.99$\pm$0.5
Random |  80.35$\pm$0.5 |  80.44$\pm$0.5 |  80.31$\pm$0.5 |  80.56$\pm$0.5
Cora-ML | Betweenness |  80.50$\pm$0.7 |  80.16$\pm$0.5 |  80.27$\pm$0.7 |  80.85$\pm$0.7
Closeness |  81.42$\pm$0.7 |  81.32$\pm$0.7 |  81.58$\pm$0.6 |  82.14$\pm$0.6
Degree |  80.12$\pm$0.6 |  80.15$\pm$0.5 |  80.17$\pm$0.6 |  80.51$\pm$0.7
Eigenvector |  81.72$\pm$0.8 |  81.60$\pm$0.5 |  81.48$\pm$0.7 |  82.09$\pm$0.7
Pagerank |  80.51$\pm$0.6 |  80.19$\pm$0.6 | 80.06$\pm$0.7 |  80.99$\pm$0.8
Random |  82.23$\pm$0.7 |  82.00$\pm$0.6 |  82.10$\pm$0.6 |  82.24$\pm$0.6
Polblogs | Betweenness | 75.19$\pm$0.9 |  77.88$\pm$3.0 |  76.41$\pm$1.8 |  83.17$\pm$2.5
Closeness |  75.87$\pm$1.4 |  79.09$\pm$2.4 |  75.72$\pm$1.8 |  83.02$\pm$2.0
Degree |  75.65$\pm$1.3 |  78.87$\pm$2.0 |  76.27$\pm$1.4 |  82.48$\pm$2.9
Eigenvector |  76.52$\pm$0.9 |  77.69$\pm$2.1 |  76.62$\pm$1.7 |  82.41$\pm$2.7
Pagerank |  75.25$\pm$1.4 |  78.09$\pm$2.2 |  75.99$\pm$1.6 |  82.73$\pm$2.6
Random |  79.93$\pm$3.3 |  80.25$\pm$2.9 |  80.13$\pm$3.4 |  83.57$\pm$3.4
Pubmed | Betweenness |  84.93$\pm$0.3 |  84.71$\pm$0.2 |  84.38$\pm$0.2 |  85.21$\pm$0.3
Closeness |  85.42$\pm$0.3 |  85.38$\pm$0.2 |  85.24$\pm$0.3 |  85.58$\pm$0.3
Degree |  84.79$\pm$0.3 |  84.55$\pm$0.3 |  84.34$\pm$0.3 |  85.08$\pm$0.4
Eigenvector |  85.45$\pm$0.3 |  85.49$\pm$0.2 |  85.40$\pm$0.3 |  85.65$\pm$0.2
Pagerank |  84.54$\pm$0.4 |  84.20$\pm$0.3 | 84.08$\pm$0.3 |  85.13$\pm$0.2
Random |  85.83$\pm$0.3 |  85.74$\pm$0.3 |  85.64$\pm$0.3 |  85.90$\pm$0.3

##  Appendix B Detailed efficiency results

We show the detailed runtime for Structack combinations in Table 8 and the
memory consumption in Table 9. Runtime and memory consumption results are
obtained after setting random linking with each selection method, and random
selection with each linking method. We chose random because its time and
memory requirements are negligible for our comparison. For these experiments,
we also set the perturbation rate $r$ to 0.05.

Table 8. Runtime in seconds for each selection/linking method. | Dataset | Citeseer | Cora | Cora-ML | Polblogs | Pubmed
---|---|---|---|---|---|---
Centrality | Betweenness | 170.42 | 242.02 | 398.90 | 233.17 | 19,507.80
Closeness | 36.95 | 54.19 | 91.24 | 66.79 | 3,938.98
Degree | 0.18 | 0.42 | 0.46 | 0.96 | 2.82
Eigenvector | 1.04 | 2.10 | 6.12 | 5.57 | 21.56
Pagerank | 2.01 | 2.22 | 3.09 | 4.65 | 20.86
Similarity | Community | 2.38 | 3.06 | 5.60 | 13.48 | 110.42
Distance | 3.27 | 5.86 | 13.48 | 49.53 | 468.35
Katz | 58.75 | 79.47 | 85.60 | 38.30 | 5,978.16
Table 9. Memory consumption in Megabytes for each selection/linking method. | Dataset | Citeseer | Cora | Cora-ML | Polblogs | Pubmed
---|---|---|---|---|---|---
Centrality | Betweenness | 367 | 366 | 363 | 364 | 438
Closeness | 369 | 367 | 365 | 365 | 438
Degree | 316 | 318 | 321 | 323 | 423
Eigenvector | 357 | 354 | 353 | 361 | 437
Pagerank | 349 | 349 | 354 | 367 | 500
Similarity | Community | 368 | 367 | 370 | 387 | 1,055
Distance | 387 | 382 | 400 | 409 | 2,150
Katz | 549 | 609 | 659 | 432 | 1,3881

##  Appendix C Detailed unnoticeability results

We show the unnoticeability of different combinations of Structack and with
different perturbation rates $r\in$ {0.001, 0.002, 0.003, 0.004, 0.005,
0.0075, 0.01, 0.025,0.05, 0.075, 0.10, 0.15, 0.20}. These are the detailed
results of what Figure 6 summarizes.

Notice that the choice of similarity has no impact on $r_{critical}$. For
Citeseer, Cora and Cora-ML, closeness centrality and eigenvector centrality
are the least noticeable. For the other two datasets (Polblogs and Pubmed),
all centrality measures have the same $r_{critical}$

Table 10. Attack unnoticeability on each dataset after applying Structack with each centrality$\times$similarity combination. The centrality measure (excpet random) with the highest critical perturbation rate $r_{critical}$ in each dataset is shown in boldface. | Similarity | Community | Distance | Katz | Random
---|---|---|---|---|---
Dataset | Centrality |  |  |  |
Citeseer | Betweenness | 0.0100 | 0.0100 | 0.0100 | 0.0100
Closeness | 0.0250 | 0.0250 | 0.0250 | 0.0250
Degree | 0.0100 | 0.0100 | 0.0100 | 0.0100
Eigenvector | 0.0250 | 0.0250 | 0.0250 | 0.0250
Pagerank | 0.0100 | 0.0100 | 0.0100 | 0.0100
Random | 0.0500 | 0.0500 | 0.0500 | 0.0500
Cora | Betweenness | 0.0100 | 0.0100 | 0.0100 | 0.0100
Closeness | 0.0250 | 0.0250 | 0.0250 | 0.0250
Degree | 0.0075 | 0.0075 | 0.0075 | 0.0075
Eigenvector | 0.0250 | 0.0250 | 0.0250 | 0.0250
Pagerank | 0.0075 | 0.0075 | 0.0075 | 0.0075
Random | 0.0250 | 0.0250 | 0.0250 | 0.0250
Cora-ML | Betweenness | 0.0100 | 0.0100 | 0.0100 | 0.0100
Closeness | 0.0100 | 0.0100 | 0.0100 | 0.0100
Degree | 0.0050 | 0.0050 | 0.0050 | 0.0050
Eigenvector | 0.0100 | 0.0100 | 0.0100 | 0.0100
Pagerank | 0.0050 | 0.0050 | 0.0005 | 0.0050
Random | 0.0250 | 0.0250 | 0.0250 | 0.0250
Polblogs | Betweenness | 0.0020 | 0.0020 | 0.0020 | 0.0020
Closeness | 0.0020 | 0.0020 | 0.0020 | 0.0020
Degree | 0.0020 | 0.0020 | 0.0020 | 0.0020
Eigenvector | 0.0020 | 0.0020 | 0.0020 | 0.0020
Pagerank | 0.0020 | 0.0020 | 0.0020 | 0.0020
Random | 0.0100 | 0.0100 | 0.0100 | 0.0100
Pubmed | Betweenness | 0.0030 | 0.0030 | 0.0030 | 0.0030
Closeness | 0.0030 | 0.0030 | 0.0030 | 0.0030
Degree | 0.0030 | 0.0030 | 0.0030 | 0.0030
Eigenvector | 0.0030 | 0.0030 | 0.0030 | 0.0030
Pagerank | 0.0030 | 0.0030 | 0.0030 | 0.0030
Random | 0.0050 | 0.0050 | 0.0050 | 0.0050