Knowledge graph reasoning (KGR) — answering complex logical queries over
large knowledge graphs — represents an important artificial intelligence task,
entailing a range of applications (e.g., cyber threat hunting). However,
despite its surging popularity, the potential security risks of KGR are largely
unexplored, which is concerning, given the increasing use of such capability in
security-critical domains.

This work represents a solid initial step towards bridging the striking gap.
We systematize the security threats to KGR according to the adversary’s
objectives, knowledge, and attack vectors. Further, we present ROAR, a new
class of attacks that instantiate a variety of such threats. Through empirical
evaluation in representative use cases (e.g., medical decision support, cyber
threat hunting, and commonsense reasoning), we demonstrate that ROAR is highly
effective to mislead KGR to suggest pre-defined answers for target queries, yet
with negligible impact on non-target ones. Finally, we explore potential
countermeasures against ROAR, including filtering of potentially poisoning
knowledge and training with adversarially augmented queries, which leads to
several promising research directions.