Source-linked AI summary
Adversarial Attacks on Node Embeddings via Graph Poisoning
Aleksandar Bojchevski, Stephan Günnemann
TL;DR
Node embeddings are widely used to represent graph structure, yet the robustness of unsupervised random-walk methods to adversarial attacks had not been studied. The paper derives efficient edge-flip poisoning attacks and shows that they significantly damage embeddings and downstream tasks, transfer across models, and remain effective under restrictions.
Problem
The paper addresses the lack of robustness analysis for widely used unsupervised random-walk node embeddings and asks whether they can be attacked without exploiting a specific supervision signal.
Method
The authors formulate edge additions and removals as a discrete bi-level poisoning problem and use eigenvalue perturbation theory with a PMI-based surrogate to derive efficient attacks.
Results
The attacks significantly degrade embedding quality and downstream tasks, transfer across models, and outperform baselines even when candidate nodes are restricted.
Takeaways & Limitations
Node embeddings are sensitive to relatively small graph perturbations, indicating that stronger defenses are needed before relying on them in production systems.
Takeaways & Limitations
The attack uses a surrogate loss because the spectrum of the elementwise-log-transformed PMI matrix cannot currently be analyzed directly.
Abstract
from arXiv · showhide
The goal of network representation learning is to learn low-dimensional node embeddings that capture the graph structure and are useful for solving downstream tasks. However, despite the proliferation of such methods, there is currently no study of their robustness to adversarial attacks. We provide the first adversarial vulnerability analysis on the widely used family of methods based on random walks. We derive efficient adversarial perturbations that poison the network structure and have a negative effect on both the quality of the embeddings and the downstream tasks. We further show that our attacks are transferable since they generalize to many models and are successful even when the attacker is restricted.
1. Introduction
The paper examines adversarial vulnerability in unsupervised random-walk node embeddings, where graph structure can be poisoned without relying on a specific downstream task. It develops an efficient attack strategy and finds that relatively few changes can significantly damage embeddings, including under attacker restrictions.
- Motivation: Random-walk node embeddings are widely used to capture graph structure for downstream tasks such as classification, link prediction, and community detection.These methods are popular partly because random walks incorporate higher-order relational information.
- Research gap: Existing graph attacks focus on semi-supervised models, leaving adversarial perturbations of unsupervised embeddings unstudied.The paper frames this gap as important because false graph data can be injected in settings such as social networks and the web.
- Research gap: Graph poisoning is challenging because embeddings are learned after discrete edge changes without a fixed downstream objective or static model.Gradient-based methods designed for continuous data are poorly suited to the discrete, combinatorial graph domain.
- Approach: The authors use eigenvalue perturbation theory to efficiently address the poisoning attack’s bi-level optimization problem.The attacker is assumed to know the data and model, while transferability and restricted attacker capabilities are also evaluated.
- Findings: The attacks significantly damage embedding quality with relatively few graph changes and remain effective when the attacker is restricted.The study motivates further work on robust node embeddings for production systems.
2. Related Work
The related work spans random-walk and spectral embeddings, adversarial attacks on machine learning and semi-supervised graph models, graph manipulation, and robustness methods. The paper distinguishes its focus on poisoning unsupervised embedding systems from these neighboring areas.
- Embedding methods: The paper focuses on unsupervised random-walk embeddings and extends its vulnerability analysis to spectral-based embeddings.Unsupervised methods are emphasized for their flexibility across multiple downstream tasks.
- Adversarial attacks: Earlier adversarial-attack research established vulnerability in traditional models, neural networks, and domains beyond image classification.The broader literature characterizes attacks by goals, knowledge, and attacker capabilities.
- Graph attacks: Prior attacks on graph models target semi-supervised graph classification using edge or feature scores, reinforcement learning, or meta-gradients.These approaches exploit a classification objective and do not address unsupervised embeddings directly.
- Graph manipulation: Graph-structure manipulation has been studied for objectives including information spread, opinions, shortest paths, PageRank, and clustering.This literature provides context for treating edge changes as a means of altering network behavior.
- Scope distinction: Robustification and adversarial training aim to improve models, whereas this paper analyzes the vulnerability of existing embedding methods.Those defense-oriented approaches are explicitly outside the paper’s scope.
3. Attacking Node Embeddings
The paper formulates graph poisoning as a discrete bi-level optimization problem over edge flips, then develops efficient spectral approximations for random-walk embeddings. It uses these approximations to select perturbations that maximize embedding loss and can also target individual nodes.
- Attack model: The attack modifies a fixed number of adjacency entries by adding or removing edges, with the goal of damaging embeddings and downstream tasks.Both general attacks on the whole network and targeted attacks on selected nodes are considered.
- Attack model: The attacker maximizes embedding loss while the model minimizes that loss on the poisoned graph, yielding a discrete bi-level optimization problem.The optimal embedding is recomputed after the graph is modified, making the problem difficult to solve directly.
- Random-walk formulation: DeepWalk can be analyzed through a PMI-derived co-occurrence matrix, allowing the embedding objective to be expressed through its low-rank approximation and singular values.This removes the need to explicitly sample random walks or learn the embedding during attack optimization.
- Efficient optimization: Eigenvalue perturbation theory provides closed-form approximations of spectral changes for candidate edge flips without recomputing a full decomposition each time.The approximation is accurate for small perturbations, while the discrete flip setting limits the usefulness of ordinary gradients.
- Efficient optimization: The sparse approach bounds changes in singular values after edge flips, making attack evaluation more efficient on large graphs.The method derives this approximation from the generalized spectrum of intermediate graph matrices.
- Approximation caveat: The method uses a surrogate loss because the spectrum of the elementwise-log-transformed PMI matrix cannot currently be analyzed directly.Experiments indicate that this surrogate can attack embeddings based on both the actual co-occurrence matrix and the original skip-gram model.
- Targeted attack: For targeted attacks, candidate flips are ranked by the resulting classification margin, with negative margins indicating misclassification.The procedure selects the top f flips with the smallest margins and averages results across ten logistic-regression classifiers.
4. Experimental Evaluation
Experiments evaluate approximation quality, general and targeted attacks, restricted settings, adversarial-edge characteristics, downstream damage, and transferability across models. The attacks consistently degrade embeddings and downstream performance, remain effective under restrictions, and transfer beyond the model used to construct them.
- Approximation Quality: R(LDW3, LDW1) = 0.90 versus R(LDW2, LDW1) = 0.11 for K = 32, showing the closed-form approximation more closely matches the actual loss.The comparison also holds for K = 64 and 128.
- General Attack: On PolBlogs, adding only 6% edges decreased classification performance by more than 23%, while Cora attacks caused up to around 5% more damage than the strongest baseline.The proposed strategies significantly outperformed baselines on downstream node classification.
- Restricted Attacks: With restricted nodes pr = 10%, 25%, and 50%, the attack caused less damage but still outperformed the baselines and remained successful.The restriction was implemented by discarding candidate edge flips involving designated restricted nodes.
- Adversarial Edge Analysis: Adversarial edges included low-, medium-, and high-degree nodes, and their edge-centrality distribution showed no clear distinction from remaining edges.Degree centrality and edge centrality therefore could not identify the selected adversarial edges.
- Targeted Node Classification: 77.89% of Cora nodes were successfully misclassified on average, compared with 33.64% for Brnd, and the attack remained effective across degree bins.High-degree nodes were generally more robust, but the proposed method successfully attacked them while baselines had 0% success.
- Targeted Attacks and Transferability: Alink decreased Cora link-prediction performance by almost 10% after flipping around 12.5% of edges, while selected adversarial edges also damaged DeepWalk, GCN, and Label Propagation.The transferability comparison found significantly more damage than the strongest baseline Beig.
5. Conclusion
The paper demonstrates that node embeddings are vulnerable to efficiently computed adversarial attacks, including under restricted perturbation budgets, and that the resulting adversarial edges transfer across models.
- Adversarial attacks can efficiently damage node embeddings and downstream tasks such as node classification and link prediction with relatively small perturbations.The attacks remain possible under restrictions, and their adversarial edges transfer across different models.
6. Appendix
The appendix evaluates spectral approximations used by the attack strategy and finds that they closely match true eigenvalue and singular-value quantities, supporting the resulting loss approximation.
- Approximation quality: Theorem 2 approximates perturbed generalized eigenvalues after a single edge flip using eigenvalue perturbation theory.The approximation avoids recomputing the full eigen-decomposition for every candidate flip.
- Approximation quality: The singular values of the perturbed matrix are bounded using approximated generalized eigenvalues and a permutation-free sorting procedure.The bound is obtained by applying the singular-value inequality after computing and sorting the relevant terms.
- Attacking spectral embedding: The spectral embedding minimizes a trace objective whose solution uses the eigenvectors associated with the K smallest Laplacian eigenvalues.The unnormalized, normalized random-walk, and normalized symmetric Laplacians are related through their definitions and spectra.
- Attacking spectral embedding: The normalized random-walk and symmetric Laplacians share eigenvalues, allowing one attack strategy to target both efficiently.The shared spectrum follows from their equivalence through the generalized eigen-problem.
- Attacking spectral embedding: Theorem 5 approximates the eigenvalue change of the unnormalized Laplacian after flipping a single edge from the corresponding adjacency and degree changes.The Laplacian perturbation is expressed directly through the edge-flip-induced matrix changes.
- Approximation quality: Across 5K randomly selected Cora flips, the true and approximated eigenvalues differed by several orders of magnitude less than the eigenvalues themselves.The related terms used in the singular-value bound were likewise negligible.
- Approximation quality: The singular-value upper-bound gap varied across graphs but was relatively small overall, supporting a good approximation of the loss.Together, the eigenvalue and singular-value evaluations demonstrate the quality of the approximation.