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.

本文提出了一种基于可靠查询的网络链路预测方法，通过 Bayesian Stackelberg 游戏框架，自动化地选择可靠查询，增加链路预测的鲁棒性和数据安全性，实验结果表明该方法有效性较好。