Adversarial Robustness of Similarity-Based Link Prediction
Adversarial Robustness of Similarity-Based Link Prediction
复制标题
DOI：
10.1109/icdm.2019.00103
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Kai Zhou;Tomasz P. Michalak;Yevgeniy Vorobeychik
中科院分区：
文献类型：
--
作者：
Kai Zhou;Tomasz P. Michalak;Yevgeniy Vorobeychik
链接预测是社会网络分析的基本问题之一。一组常见的链路预测技术依赖于相似性度量，相似性度量使用观察到的子网的拓扑来量化未观察到的链路的可能性。最近，链接预测的相似性度量已被证明容易受到攻击，即对网络的观察进行对抗性修改以隐藏目标链接。我们提出了一种新的方法，通过赋予分析人员一组有限的可靠查询来提高基于相似性的链接预测的鲁棒性，这些查询可以准确地测量所查询链接的存在性。分析人员的目标是通过最优地分配可靠查询来健壮地预测可能的链接集合。我们将分析人员的问题形式化为贝叶斯Stackelberg博弈，其中他们首先选择可靠的查询，然后对手删除分析人员剩余（不可靠）查询中的链接子集。在我们的模型中，分析人员不确定攻击者试图隐藏的特定目标链接，而攻击者拥有关于分析人员和网络的全部信息。通过只使用局部信息的相似性度量，我们证明了问题对双方都是np困难的，并设计了两种原则和有效的方法来近似解决它。大量的真实和合成网络实验证明了我们方法的有效性。
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's 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.