REVIEW 3 major objections 5 minor 28 references
Adversarial Robustness of Similarity-Based Link Prediction
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Similarity-based link prediction can be made robust against targeted edge-deletion attacks by spending a small budget on reliable link queries, even though computing the attacker's exact best response is NP-hard.
desk verdict First defense model for similarity-based link prediction under adversarial edge deletion, with a real NP-hardness result, but the headline robustness claim is undercut by testing defenses only against attackers that share the paper's independence approximation. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the damage graph plus the independent damage approximation. For a sample graph and a target edge $(V_1,V_2)$, the attacker's only useful deletions are edges from $V_1$ or $V_2$ to a common neighbor $w$; each such link is assigned a damage $c_{jr}$, the change in the defender's loss if that link alone is removed. The independence approximation treats the total damage from a deletion set as the sum of these per-link damages, which decouples the attacker's tie-breaking choice per tuple $(V_1,w,V_2)$. IDOpt turns the defender's resulting minimization into an integer program that is linearized and solved over all samples; IDRank accumulates the per-tuple weights $\min\{c_{j1},c_{j2}\}$ across samples and protects the top-ranked edges. The same machinery also explains why random defenses fail: the important edges are only those whose deletion changes the defender's loss, not all links incident to the target nodes.
What would settle it
A reader could settle the main approximation by enumerating all defender query sets $S_D$ with $|S_D| \le k_D$ and all attacker deletion sets $S_A$ with $|S_A| \le k_A$ on a small synthetic graph, computing the exact Strong Stackelberg equilibrium through the full expected loss, and comparing the defender's loss with the loss obtained by IDOpt's selected query set; if the exact loss is substantially lower on graphs where two candidate deletions share a common neighbor, then the independence approximation causes the defense to protect the wrong edges.
Extended reading notes
Core claim
The paper's central claim is that the defender's query-selection problem can be approximated well enough to protect link prediction: even though choosing the query set solves a Bayesian Stackelberg game whose attacker-side best response is NP-hard (Theorem 1 reduces the tie-breaking problem to MaxCut), replacing the true attack with an independent-damage model makes the defender problem tractable and practically useful. On the independent-damage model, the attacker's tie-breaking best response is a per-common-neighbor comparison: for symmetric metrics, delete the cheaper of the two edges incident to the target; for asymmetric metrics, delete the required number of edges in ascending order of damage difference (Propositions 1 and 2). The resulting defenses, IDOpt and IDRank, select reliable queries by minimizing or ranking accumulated damages across sampled graphs. In the reported experiments, a few percent of reliable queries recovers most of the loss caused by the strongest considered attack, while random protection of the same number of queries has almost no effect; conversely, the paper observes cases where the attack can lower the defender's loss, reflecting the non-zero-sum nature of the game.
Load-bearing premise
The load-bearing premise is the independent damage approximation, namely that the damage caused by deleting any one link is the same regardless of which other links are also deleted; if deleting links interact, the reliable-query sets produced by IDOpt and IDRank are optimal only for an approximate attack model.
Editorial extensions
If this is right
- A defender who does not know which link the attacker will target can still protect link prediction by choosing reliable queries according to accumulated damage scores, provided the attacker is limited to deleting edges incident to the target's common neighbors.
- Because the same per-edge damage scores drive IDOpt and IDRank, the defense approach carries over to other local similarity metrics without re-deriving the game for each one.
- The observation that random reliable queries can sometimes increase the defender's loss implies that query budgets should be allocated by an optimization criterion, not by uniform sampling.
- The NP-hardness of tie-breaking best responses means exact robust defense is out of reach for larger networks, making approximation quality the central performance question rather than an implementation detail.
Reading between the lines
- A stress test that violates the independence model, for instance an attacker who coordinates deletions across common neighbors to maximize summed damage, would reveal whether the defended query sets are near-optimal under the true game or only under the approximate one.
- The same reliable-query formulation could be extended beyond local metrics by replacing the two-hop damage graph with a wider neighborhood, making the defense applicable to path-based and random-walk similarity measures but also enlarging the attacker's action space.
- The damage graph could double as a diagnostic: networks whose per-link damage scores are weakly correlated are intrinsically easier to defend, and a defender could estimate that correlation from samples before committing a query budget.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes a defense for similarity-based link prediction against adversarial edge deletion. The analyst (defender) can choose up to kD reliable node-pair queries; the attacker observes this choice and then deletes up to kA edges among the remaining queries to minimize the similarity score of a target link. The interaction is formalized as a Bayesian Stackelberg game, with the attacker's type given by the underlying graph and the target link. For local similarity metrics, the paper claims (Theorem 1) that computing the attacker's tie-breaking best response is NP-hard, and then introduces the independent damage approximation (Section VI-A), under which Propositions 1 and 2 characterize the attacker's best response. Based on this, the paper proposes IDOpt, an integer-programming approach, and IDRank, a ranking heuristic, for selecting reliable queries, and evaluates them with the damage prevention ratio (DPR) on four datasets under three attacks.
Significance. If the results are correct, the paper would make a meaningful contribution to adversarial network analysis: a principled game-theoretic formulation of robust link prediction with reliable queries, two scalable heuristics, and evidence that small budgets of reliable queries substantially reduce attack damage. Strengths include the explicit Stackelberg formulation, a concrete NP-hardness target, clear algorithm descriptions, and experiments across multiple metrics and real/synthetic networks. However, the central effectiveness claim is currently supported only by a circular evaluation: the main attack, LinkDel, is derived from the same independent damage approximation used by both defense algorithms, and no exact or dependency-aware attacker is tested. The result is potentially significant, but the present evidence does not yet establish robustness against the true Stackelberg adversary.
major comments (3)
- [VI-A, VII-B (Eqs. (5)-(6), Propositions 1-2)] The central claim that IDOpt and IDRank can alleviate much of the damage caused by attacks is not yet supported for the exact game. The defender's objective in Eq. (6) sums per-link damages under the independent damage approximation, and the primary attack LinkDel is explicitly implemented according to Propositions 1 and 2, which are derived from that same approximation. Thus the DPR curves in Figs. 2-5 measure performance against an attacker that already accepts the defender's simplified model. The two alternative attacks, UnbiasDel and RandDel, do not optimize the attacker's utility and therefore do not probe worst-case behavior. To support the claim, the paper should compare against an exact attacker (for example, by exhaustive search on small graphs) and should provide some bound or empirical estimate of the error introduced by the independence assumption.
- [V (Theorem 1)] The proof of Theorem 1 only works out the reduction for Common Neighbors; the statement that the proof extends straightforwardly to all metrics in Table I is not demonstrated. For asymmetric metrics such as Salton, the unconstrained attacker's optimal response is not an arbitrary partition of the common neighbors but must satisfy a fixed number k* of deletions on each side (as used later in Proposition 2), so the MaxCut reduction needs additional structure. Since NP-hardness for the full list is a headline claim, this gap must be closed by giving a formal reduction for each metric class, or the theorem must be restricted.
- [VI-B] The solution approach and experiments restrict the attacker to the strong case k_i^A = |N(V_i^1,V_i^2)|, i.e., the attacker deletes one incident edge for every common neighbor. The game model in Section IV-B allows any budget kA up to the number of available links, and the NP-hardness result concerns the general problem. With a smaller budget, the attacker must also choose which common neighbors to attack, and the per-link damage ranking used by IDRank and the objective in Eq. (7) may no longer be appropriate. The paper should either extend Propositions 1-2 and the algorithms to general kA, or explicitly state and justify the strong-attacker restriction as a modeling assumption.
minor comments (5)
- [V (Theorem 1 proof)] The symbol SD is overloaded: in the proof it denotes both the defender's reliable query set and the accumulated damage sum, and the decision problem asks for 'SD = ka'. Please use distinct notation for these two quantities.
- [V (MaxCut reduction)] The text defines MaxCut as deciding whether the cut size is 'at most k', but the reduction uses the standard formulation of whether a cut of size at least k exists. This should be corrected.
- [VII (loss parameters)] The values of the loss parameters beta and theta in l(e) = exp(-y_e beta (Sim(e) - theta)) are not reported, and no sensitivity analysis is provided; the reported DPR could depend on these choices.
- [VII-C (DPR metric)] The DPR denominator L_A - L_0 is near zero in the random-attack scenarios (Table II shows damages around 0.02% to 2%), so DPR values in those settings should be interpreted with care; please report raw losses or confidence intervals.
- [Algorithms 1 and 2] The pseudocode contains typographical artifacts such as the symbols '⊿' and the word 'Enq' in Algorithm 1, and the annotation '⊿ reliable queries' in both algorithms; these should be cleaned up before publication.
Circularity Check
Defense effectiveness is evaluated against an attacker that already assumes the paper's independent-damage approximation.
-
other
[Section VI-A, Eq. (6); Section VI-B, Propositions 1-2; Section VII-B, LinkDel]
"To make the problem tractable, we make the approximation that deleting a link will cause a damage which is independent of the states of other links. Our experiments subsequently demonstrate the effectiveness of this approach."
The independent-damage approximation is the design basis of both sides of the evaluation. IDOpt and IDRank minimize the summed per-link damages C(x) in Eqs. (5)-(7), while the primary attack LinkDel 'will delete links according to Proposition 1 and Proposition 2,' and those propositions are derived 'under the independent damage assumption' using the same additive objective (Eq. (4)). Thus DPR under LinkDel measures how well the optimizer reduces its own model objective, not how the defenses behave against the exact Stackelberg adversary whose hardness is Theorem 1. The paper provides no exact-attacker baseline or bound on the approximation error, so the headline robustness claim rests on a self-consistent model.
full rationale
The paper's NP-hardness result (Theorem 1) is an independent MaxCut reduction and is not circular. The self-citations to the authors' prior paper [25] are used for the attacker's optimal deletion structure, but that is prior peer-reviewed work with falsifiable content, so I do not count it as circular by itself. The circularity is in the evaluation of the approximation: the defense algorithms and the LinkDel attack are both constructed from the same independent-damage assumption, so the primary DPR experiments (Figs. 2-5) are a consistency check rather than an external validation. The additional UnbiasDel and RandDel attacks are not built on the approximation, but they are heuristic and do not optimize the attacker's utility, so they do not probe the worst-case exact adversary. This makes the practical claim that the approximation and defenses 'alleviate much of the damage caused by attacks' only partially supported. Score 6 reflects partial circularity in the central empirical claim while acknowledging the independent complexity result and algorithm design.
Assumptions & free parameters
free parameters (3)
- Exponential loss parameter beta =
not reported
- Prediction threshold theta =
not reported
- Number of samples K for defense =
4000 in experiments
assumptions (4)
- ad hoc to paper Damage from deleting each link is independent of the states of other links (independent damage approximation).
- domain assumption For local metrics, the optimal way to hide a target link is to delete, for each common neighbor, one of its two incident edges to the target nodes (from Zhou et al. [25]).
- standard math Strong Stackelberg equilibrium with attacker tie-breaking in the defender's favor is the operative solution concept.
- domain assumption The defender's prior over attacker types is approximated by K independent samples drawn from the same random graph models used in evaluation.
Cite this review
Pith. "Pith review of Adversarial Robustness of Similarity-Based Link Prediction." pith.science (2026). https://pith.science/paper/V66RLV5P
@misc{pith2026190901432,
author = {Pith},
title = {Pith review of: Adversarial Robustness of Similarity-Based Link Prediction},
year = {2026},
howpublished = {\url{https://pith.science/paper/V66RLV5P}},
note = {Machine review of arXiv:1909.01432}
}
read the original abstract
Link prediction is one of the fundamental problems in social network analysis. A common set of techniques for link prediction rely on similarity metrics which use the topology of the observed subnetwork to quantify the likelihood of unobserved links. Recently, similarity metrics for link prediction have been shown to be vulnerable to attacks whereby observations about the network are adversarially modified to hide target links. We propose a novel approach for increasing robustness of similarity-based link prediction by endowing the analyst with a restricted set of reliable queries which accurately measure the existence of queried links. The analyst aims to robustly predict a collection of possible links by optimally allocating the reliable queries. We formalize the analyst problem as a Bayesian Stackelberg game in which they first choose the reliable queries, followed by an adversary who deletes a subset of links among the remaining (unreliable) queries by the analyst. The analyst in our model is uncertain about the particular target link the adversary attempts to hide, whereas the adversary has full information about the analyst and the network. Focusing on similarity metrics using only local information, we show that the problem is NP-Hard for both players, and devise two principled and efficient approaches for solving it approximately. Extensive experiments with real and synthetic networks demonstrate the effectiveness of our approach.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Emergence of scaling in random networks
Albert-L ´aszl´o Barab ´asi and R ´eka Albert. Emergence of scaling in random networks. science, 286(5439):509–512, 1999
work page 1999
-
[2]
Generation of uncorrelated random scale-free networks
Michele Catanzaro, Mari ´an Bogun ´a, and Romualdo Pastor-Satorras. Generation of uncorrelated random scale-free networks. Physical Review E, 71(2):027103, 2005
work page 2005
-
[3]
Computing the optimal strategy to commit to
Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceedings of the 7th ACM conference on Electronic commerce, pages 82–90. ACM, 2006
work page 2006
-
[4]
Francois Fouss, Alain Pirotte, Jean-Michel Renders, and Marco Saerens. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on knowledge and data engineering , 19(3):355–369, 2007
work page 2007
-
[5]
Centrality in social networks conceptual clarification
Linton C Freeman. Centrality in social networks conceptual clarification. Social networks, 1(3):215–239, 1978
1978
-
[6]
Quality- bounded solutions for finite bayesian stackelberg games: Scaling up
Manish Jain, Christopher Kiekintveld, and Milind Tambe. Quality- bounded solutions for finite bayesian stackelberg games: Scaling up. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 3, pages 997–1004. International Foundation for Autonomous Agents and Multiagent Systems, 2011
work page 2011
-
[7]
A new status index derived from sociometric analysis
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953
1953
-
[8]
Christopher Kiekintveld, Janusz Marecki, and Milind Tambe. Ap- proximation methods for infinite bayesian stackelberg games: Modeling distributional payoff uncertainty. In The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 3 , pages 1005–
Show all 28 references
-
[9]
Semi-supervised classification with graph convolutional networks
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 , 2016
2016 arXiv
-
[10]
Stackelberg vs
Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe. Stackelberg vs. nash in security games: An extended investigation of interchangeability, equivalence, and unique- ness. Journal of Artificial Intelligence Research , 41:297–327, 2011
2011
-
[11]
Vertex similarity in networks
Elizabeth A Leicht, Petter Holme, and Mark EJ Newman. Vertex similarity in networks. Physical Review E , 73(2):026120, 2006
2006
-
[12]
Sampling from large graphs
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 631–636. ACM, 2006
2006
-
[13]
Snap: A general-purpose network analysis and graph-mining library
Jure Leskovec and Rok Sosi ˇc. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016
2016
-
[14]
The link-prediction problem for social networks
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology , 58(7):1019–1031, 2007
2007
-
[15]
Similarity index based on local paths for link prediction of complex networks
Linyuan L ¨u, Ci-Hang Jin, and Tao Zhou. Similarity index based on local paths for link prediction of complex networks. Physical Review E, 80(4):046122, 2009
2009
-
[16]
Link prediction in complex networks: A survey
Linyuan L ¨u and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications , 390(6):1150–1170, 2011
2011
-
[17]
Deepwalk: Online learning of social representations
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710. ACM, 2014
-
[18]
Gemsec: Graph embedding with self clustering
Benedek Rozemberczki, Ryan Davies, Rik Sarkar, and Charles Sut- ton. Gemsec: Graph embedding with self clustering. arXiv preprint arXiv:1802.03997, 2018
2018 arXiv
-
[19]
Stackelberg security games: Looking beyond a decade of success
Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: Looking beyond a decade of success. In IJCAI, pages 5494–5501, 2018
2018
-
[20]
Adversarial machine learning
Yevgeniy V orobeychik and Murat Kantarcioglu. Adversarial machine learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 12(3):1–169, 2018
2018
-
[21]
Link predic- tion in social networks: the state-of-the-art
Peng Wang, BaoWen Xu, YuRong Wu, and XiaoYu Zhou. Link predic- tion in social networks: the state-of-the-art. Science China Information Sciences, 58(1):1–38, 2015
2015
-
[22]
Hiding individuals and communities in a social network
Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in a social network. Nature Human Behaviour, 2(2):139, 2018
2018
-
[23]
How to hide ones relationships from link prediction algorithms
Marcin Waniek, Kai Zhou, Yevgeniy V orobeychik, Esteban Moro, Tomasz P Michalak, and Talal Rahwan. How to hide ones relationships from link prediction algorithms. Scientific Reports, 9(1):1–10, 2019
2019
-
[24]
Measuring the robustness of link prediction algorithms under noisy environment
Peng Zhang, Xiang Wang, Futian Wang, An Zeng, and Jinghua Xiao. Measuring the robustness of link prediction algorithms under noisy environment. Scientific reports, 6:18881, 2016
2016
-
[25]
Attacking similarity-based link prediction in social networks
Kai Zhou, Tomasz P Michalak, Marcin Waniek, Talal Rahwan, and Yevgeniy V orobeychik. Attacking similarity-based link prediction in social networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems , pages 305–313. Inter- national ...
2019
-
[26]
Adversarial attacks on neural networks for graph data
Daniel Z ¨ugner, Amir Akbarnejad, and Stephan G ¨unnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847–2856. ACM, 2018
2018
-
[27]
Adversarial attacks on graph neural networks via meta learning
Daniel Z ¨ugner and Stephan G ¨unnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations, 2019
2019
-
[1012]
International Foundation for Autonomous Agents and Multiagent Systems, 2011
2011
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.