12 - Adversarial contamination of network data

As graph data becomes more ubiquitous, the need for robust inferential graph algo- rithms to operate in these complex data domains is crucial. In many cases of interest, inference is further complicated by the presence of adversarial data contamination. The effect of the adversary is frequently to change the data distribution in ways that negatively affect statistical inference and algorithmic performance. We study this phe- nomenon in the context of vertex nomination, a semi-supervised information retrieval task for network data. Here, a common suite of methods relies on spectral graph em- beddings, which have been shown to provide both good algorithmic performance and flexible settings in which regularization techniques can be implemented to help miti- gate the effect of an adversary. Many current regularization methods rely on direct network trimming to effectively excise the adversarial contamination, although this direct trimming often gives rise to complicated dependency structures in the result- ing graph. We propose a new trimming method that operates in model space, which is more amenable to theoretical analysis and demonstrates superior performance in a number of simulations. We then extend this method to a more general setting, where the network is contaminated through both block structure contamination and white noise contamination (contamination whose distribution is unknown).