Adversarial Robustness of SimilarityBased Link Prediction 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 similaritybased 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 analystu0027s 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 NPHard 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.

ADMIRING: Adversarial Multinetwork Mining Multisourced networks naturally appear in many application domains, ranging from bioinformatics, social networks, neuroscience to management. Although stateoftheart offers rich models and algorithms to find various patterns when input networks are given, it has largely remained nascent on how vulnerable the mining results are due to the adversarial attacks. In this paper, we address the problem of attacking multinetwork mining through the way of deliberately perturbing the networks to alter the mining results. The key idea of the proposed method (Admiring) is effective influence functions on the Sylvester equation defined over the input networks, which plays a central and unifying role in various multinetwork mining tasks. The proposed algorithms bear two main advantages, including (1) effectiveness, being able to accurately quantify the rate of change of the mining results in response to attacks; and (2) generality, being applicable to a variety of multinetwork mining tasks ( e.g., graph kernel, network alignment, crossnetwork node similarity) with different attacking strategies (e.g., edgenode removal, attribute alteration).