Black-box attacks on dynamic graphs via adversarial topology perturbations

Area of Science:

• Computer Science
• Graph Theory
• Machine Learning

Background:

• Attacks on dynamic graphs are crucial for understanding information system vulnerabilities.
• Existing graph rewiring attacks are often impractical for real-world dynamic graphs.

Purpose of the Study:

• To propose the first study on attacking dynamic graphs using adversarial topology perturbations in a restricted black-box setting.
• To develop a novel attack strategy by injecting fake nodes and links into dynamic graphs.

Main Methods:

• A hierarchical reinforcement learning based black-box attack (HRBBA) framework is proposed.
• Dynamic graph perturbations are modeled as a sequential decision-making process with three sub-tasks.
• An imperceptible perturbation constraint is incorporated for attack concealment.
• The HRBBA framework is optimized using an actor-critic process.

Main Results:

• The HRBBA framework significantly degrades the performance of various dynamic graph learning methods.
• Experiments were conducted on four real-world dynamic graphs.
• Victim methods for link prediction, node classification, and network clustering were substantially impacted.

Conclusions:

• The proposed HRBBA framework offers an effective method for attacking dynamic graphs in a black-box setting.
• Injecting fake nodes and links is a viable strategy for adversarial topology perturbations.
• The HRBBA attack demonstrates the vulnerability of current dynamic graph learning methods to sophisticated attacks.