# A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models

arXiv: https://arxiv.org/abs/1908.01297 · HTML: https://mlsanity.com/paper/1908.01297/

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2019.

## Built on by (most cited first, 30 of 68)

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Understanding and Improving Graph Injection Attack by Promoting Unnoticeability](https://mlsanity.com/paper/2202.08057/) (2022)
- [Unnoticeable Backdoor Attacks on Graph Neural Networks](https://mlsanity.com/paper/2303.01263/) (2023)
- [Spectral Augmentation for Self-Supervised Learning on Graphs](https://mlsanity.com/paper/2210.00643/) (2022)
- [Mind the Label Shift of Augmentation-based Graph OOD Generalization](https://mlsanity.com/paper/2303.14859/) (2023)
- [Recognizing Predictive Substructures with Subgraph Information Bottleneck](https://mlsanity.com/paper/2103.11155/) (2021)
- [G-Refer: Graph Retrieval-Augmented Large Language Model for Explainable Recommendation](https://mlsanity.com/paper/2502.12586/) (2025)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications](https://mlsanity.com/paper/2106.07767/) (2021)
- [Adversarial Attack on Graph Neural Networks as An Influence Maximization Problem](https://mlsanity.com/paper/2106.10785/) (2021)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [Jointly Attacking Graph Neural Network and its Explanations](https://mlsanity.com/paper/2108.03388/) (2021)
- [Graph-Fraudster: Adversarial Attacks on Graph Neural Network Based Vertical Federated Learning](https://mlsanity.com/paper/2110.06468/) (2021)
- [Graph Structural Attack by Perturbing Spectral Distance](https://mlsanity.com/paper/2111.00684/) (2021)
- [Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias](https://mlsanity.com/paper/2304.00010/) (2023)
- [Knowledge Graph Completion with Counterfactual Augmentation](https://mlsanity.com/paper/2302.13083/) (2023)
- [Path-based Explanation for Knowledge Graph Completion](https://mlsanity.com/paper/2401.02290/) (2024)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Learning on Graphs with Large Language Models(LLMs): A Deep Dive into Model Robustness](https://mlsanity.com/paper/2407.12068/) (2024)
- [Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge](https://mlsanity.com/paper/2105.12419/) (2021)
- [Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attack](https://mlsanity.com/paper/2202.07114/) (2022)
- [Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees](https://mlsanity.com/paper/2205.03546/) (2022)
- [GraphAttacker: A General Multi-Task GraphAttack Framework](https://mlsanity.com/paper/2101.06855/) (2021)
- [Revisiting Adversarial Attacks on Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/2208.06651/) (2022)
- [Neighboring Backdoor Attacks on Graph Convolutional Network](https://mlsanity.com/paper/2201.06202/) (2022)
- [Adversarially Robust Neural Architecture Search for Graph Neural Networks](https://mlsanity.com/paper/2304.04168/) (2023)
- [Query Driven-Graph Neural Networks for Community Search: From Non-Attributed, Attributed, to Interactive Attributed](https://mlsanity.com/paper/2104.03583/) (2021)
- [Minimum Topology Attacks for Graph Neural Networks](https://mlsanity.com/paper/2403.02723/) (2024)
- [Adversarial Attacks on Graph Classification via Bayesian Optimisation](https://mlsanity.com/paper/2111.02842/) (2021)

## Abstract (arXiv)

With the great success of graph embedding model on both academic and industry area, the robustness of graph embedding against adversarial attack inevitably becomes a central problem in graph learning domain. Regardless of the fruitful progress, most of the current works perform the attack in a white-box fashion: they need to access the model predictions and labels to construct their adversarial loss. However, the inaccessibility of model predictions in real systems makes the white-box attack impractical to real graph learning system. This paper promotes current frameworks in a more general and flexible sense -- we demand to attack various kinds of graph embedding model with black-box driven. To this end, we begin by investigating the theoretical connections between graph signal processing and graph embedding models in a principled way and formulate the graph embedding model as a general graph signal process with corresponding graph filter. As such, a generalized adversarial attacker: GF-Attack is constructed by the graph filter and feature matrix. Instead of accessing any knowledge of the target classifiers used in graph embedding, GF-Attack performs the attack only on the graph filter in a black-box attack fashion. To validate the generalization of GF-Attack, we construct the attacker on four popular graph embedding models. Extensive experimental results validate the effectiveness of our attacker on several benchmark datasets. Particularly by using our attack, even small graph perturbations like one-edge flip is able to consistently make a strong attack in performance to different graph embedding models.