Source-linked AI summary
A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Honglei Zhang, Peng Cui, Wenwu Zhu, Junzhou Huang
TL;DR
Graph embedding models are vulnerable to adversarial manipulation, but many existing attacks require information unavailable in restricted black-box settings. The paper introduces GF-Attack, which models embeddings as graph filtering processes and attacks the filter using graph structure and features. Experiments report effective attacks across multiple graph embedding models without access to the classifier, while evaluation is scoped by assumptions such as the SGC-to-GCN extension and local candidate-edge selection.
Problem
Restricted black-box attacks on graph embedding models are challenging because they must operate with limited training-input information rather than model predictions, labels, or parameters.
Method
GF-Attack formulates graph embedding models as graph signal processes with corresponding filters and constructs an embedding-quality objective from the filter, adjacency matrix, and feature matrix.
Results
GF-Attack effectively attacks popular unsupervised and semi-supervised graph embedding models on real-world datasets without access to the classifier.
Takeaways & Limitations
The framework provides a general restricted-black-box attack across graph embedding models that can be represented as graph signal processes.
Takeaways & Limitations
For multi-layer nonlinear GCNs, the attack extends the SGC loss based on similar filtering behavior, and experiments restrict candidate flips to edges incident to target vertices.
Abstract
from arXiv · showhide
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.
Introduction
Graph embedding models are vulnerable to adversarial attacks, while restricted black-box attacks remain challenging because they rely only on training input. GF-Attack addresses this gap by attacking graph filters rather than target-model loss functions and works across multiple embedding models.
- Motivation: Graph embedding models have been shown vulnerable to attacks that can compromise downstream systems such as recommendation.Prior work reports vulnerabilities in Graph Convolutional Networks, DeepWalk, and other graph embedding methods.
- Attack procedure: GF-Attack does not modify the target embedding model and instead produces adversarial graph edges to misclassify selected vertices.The illustrated procedure deletes one edge and adds another while leaving the common embedding block unchanged.
- Motivation: Restricted black-box attacks are more challenging and practically meaningful because they rely on limited information from the training input.The supplied discussion contrasts restricted black-box attacks with white-box and practical white-box settings.
- GF-Attack: GF-Attack formulates graph embedding as graph signal processing with a graph filter and constructs an embedding-quality measure from the filter and feature matrix.The resulting optimization is posed as a T-rank approximation problem rather than a target-classifier loss.
- GF-Attack: GF-Attack attacks the graph filter using adjacency and feature information, enabling restricted black-box attacks on models expressible as general graph signal processes.The framework provides quality-measure constructions for GCN, SGC, DeepWalk, and LINE.
- Results: GF-Attack effectively attacks popular unsupervised and semi-supervised graph embedding models on real-world datasets without accessing the classifier.This is the paper's stated empirical outcome.
Related work
Prior work provided insights into individual graph embedding frameworks and demonstrated adversarial vulnerability or transferability, but lacked a theoretical connection across embedding methods. This paper supplies that connection and derives a general restricted-black-box optimization framework.
- Prior analyses: Earlier analyses examined Graph Convolutional Networks and sampling-based embeddings, but focused on proposing frameworks rather than establishing a theoretical connection between them.These studies addressed separate method families.
- Adversarial attacks: Existing graph attacks differ in access assumptions and capabilities, including edge-only attacks under restricted black-box settings and label-dependent attacks under practical white-box settings.The cited methods also differ in whether they support edge insertion and deletion and whether transferability is evaluated.
- Research gap: Prior experiments showed transferability among graph embedding methods, but did not provide theoretical analysis of the underlying connection.The paper positions its contribution as addressing this missing analysis.
- This work: This work theoretically connects different graph embedding models and derives a general optimization problem with an effective algorithm under the restricted black-box setting.The framework is based on parametric graph signal processing.
Preliminary
The preliminary formulation represents an attributed graph through its adjacency and feature matrices, defines structural perturbations as edge changes, and expresses attack damage through the output embedding quality under a fixed budget. The paper focuses on structural attacks while keeping learned model parameters fixed during attack.
- Graph representation: An attributed graph is represented by an adjacency matrix A for edge connections and a feature matrix X for vertex attributes.The graph has vertex set V and edge set E, with A and X encoding structure and features.
- Graph operators: The normalized adjacency matrix and two normalized Laplacians provide alternative graph-structure operators used in the formulation.The supplied definitions include symmetric and random-walk normalized Laplacians.
- Attack targets: Graph attacks can modify vertices, edges, or attributes, but this work focuses on structural attacks that add or delete edges in A.The paper motivates attacking graph structure as more practical than modifying other graph components.
- Attack formulation: Under a fixed budget β, the adversary perturbs a bounded number of adjacency entries and evaluates the resulting embedding output.For an undirected graph, the stated budget permits modification of 2β entries in A.
- Attack formulation: The attack objective measures damage to output embeddings through a loss L(A′, Z), where lower loss corresponds to higher embedding quality.The embedding is Z = M_Θ(A′, X), and white-box attackers can construct this measure from the target loss.
- Attack assumption: During attack, the model parameters learned on the clean graph remain fixed rather than being retrained.The paper sets Θ* as the parameters learned by minimizing the clean-graph objective.
Methodologies
The paper recasts graph embedding models as graph-signal processes governed by graph filters, then builds GF-Attack by perturbing those filters and feature matrices without target-model parameters. It connects this framework to convolutional and sampling-based embedding models, enabling a general restricted black-box attack formulation.
- General graph-filter formulation: Graph embedding models are formulated as graph-signal processes that apply a graph filter H and feature transformation to input signals.The feature matrix X is treated as graph signals, while H captures graph-dependent processing.
- General graph-filter formulation: GF-Attack constructs a restricted black-box loss from the graph filter and feature matrix rather than accessing the target model parameters.The attack uses a T-rank approximation and optimizes an upper bound because directly optimizing the embedding loss is difficult.
- General graph-filter formulation: The framework explains transferability because edge modifications to A implicitly perturb graph-filter eigenvalues.This provides a theoretical connection between attacks transferred across different graph embedding models.
- GF-Attack on graph convolutional networks: ChebyNet, GCN, and SGC are represented through polynomial graph filters, with SGC equivalent to a K-localized single-layer ChebyNet.For SGC and GCN, the shared graph-shift filter is Ssym = 2I_n − L_sym = Â + I_n.
- GF-Attack on graph convolutional networks: The convolutional formulation extends from SGC to multi-layer GCN despite nonlinear activation functions because both exhibit similar graph-filtering behavior.The paper reports that experiments validate applying the SGC attack model to multi-layer GCN.
- GF-Attack on sampling-based graph embedding: LINE and DeepWalk are connected to graph signal processing by interpreting their learned representations as outputs of graph-signal filtering.LINE is presented as a special case that supports extending the connection to K-window DeepWalk.
Experiments
Experiments evaluate GF-Attack under restricted black-box conditions across graph embedding models, perturbation budgets, filter orders, and computational costs. GF-Attack generally outperforms the compared attackers, transfers across architectures, remains effective with larger budgets, and is faster than developed baselines.
- Experimental Setup: The evaluation uses Cora, Citeseer, and Pubmed citation networks, with RBA baselines including Random, Degree, RL-S2V, and Aclass.The attack configuration limits attackers to a single edge addition or deletion unless otherwise indicated.
- Attack Performance Evaluation: GF-Attack outperforms other attackers on all datasets and models evaluated with Graph Convolutional Networks.It also performs well on two-layer nonlinear GCNs, indicating generalization across GCN settings.
- Attack Performance Evaluation: GF-Attack achieves the best performance nearly on all sampling-based graph embedding models.The attack performs better on LINE than on DeepWalk, which the authors associate with LINE’s deterministic structure and DeepWalk’s random sampling.
- Evaluation of Multi-layer GCNs: All tested GF-Attack graph-filter orders effectively attack multi-layer GCNs and SGC, with GF-Attack-5 performing best in most cases.SGC is attacked more effectively than GCN under all settings; the authors conjecture that GCN nonlinearity adds robustness.
- Evaluation under Multi-edge Perturbation Settings: As the number of perturbed edges increases, attack performance improves for every attacker, while GF-Attack outperforms baselines in all reported Cora cases.These results are reported under the RBA setting for multi-edge perturbations.
- Computational Efficiency Analysis: GF-Attack is slower than Random and Degree but much faster than RL-S2V and Aclass on Citeseer.The comparison reports 10-times average running times for processing a single node.
Conclusion
The paper studies adversarial attacks on diverse graph embedding models under a restricted black-box setting. It formulates embedding methods through graph filters, constructs an attacker using only adjacency and feature matrices, and reports vulnerability across model types.
- Conclusion: The framework models graph embedding methods as graph signal processes with corresponding graph filters.GF-Attack constructs a general optimization problem by measuring embedding quality and derives an algorithm to solve it.
- Conclusion: GF-Attack attacks graph filters using only the adjacency matrix and feature matrix under the restricted black-box setting.The framework is intended for different kinds of graph embedding models.
- Conclusion: Experiments show vulnerability of different kinds of graph embedding models to the proposed attack framework.