# Adversarial contamination of networks in the setting of vertex nomination: a new trimming method

arXiv: https://arxiv.org/abs/2208.09710 · HTML: https://mlsanity.com/paper/2208.09710/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 72 references that are in the map.
- First posted on arXiv 20 Aug 2022.

## Builds on (most cited first, 29 of 29)

- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Adversarial Attack on Large Scale Graph](https://mlsanity.com/paper/2009.03488/) (2020)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothing](https://mlsanity.com/paper/2002.03421/) (2020)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Network histograms and universality of blockmodel approximation](https://mlsanity.com/paper/1312.5306/) (2013)
- [A goodness-of-fit test for stochastic block models](https://mlsanity.com/paper/1412.4857/) (2014)
- [Robust and computationally feasible community detection in the presence of arbitrary outlier nodes](https://mlsanity.com/paper/1404.6000/) (2014)
- [Limit theorems for eigenvectors of the normalized Laplacian for random graphs](https://mlsanity.com/paper/1607.08601/) (2016)
- [Hypothesis Testing for Automated Community Detection in Networks](https://mlsanity.com/paper/1311.2694/) (2013)
- [Community detection in networks: Modularity optimization and maximum likelihood are equivalent](https://mlsanity.com/paper/1606.02319/) (2016)
- [Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral](https://mlsanity.com/paper/1710.10936/) (2017)
- [Vertex nomination schemes for membership prediction](https://mlsanity.com/paper/1312.2638/) (2013)
- [Vertex Nomination, Consistent Estimation, and Adversarial Modification](https://mlsanity.com/paper/1905.01776/) (2019)
- [Vertex nomination: The canonical sampling and the extended spectral nomination schemes](https://mlsanity.com/paper/1802.04960/) (2018)
- [On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models](https://mlsanity.com/paper/2003.14250/) (2020)
- [Vertex Nomination Via Seeded Graph Matching](https://mlsanity.com/paper/1705.00674/) (2017)
- [On consistent vertex nomination schemes](https://mlsanity.com/paper/1711.05610/) (2017)
- [On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching](https://mlsanity.com/paper/1607.01369/) (2016)
- [Correcting a Nonparametric Two-sample Graph Hypothesis Test for Graphs with Different Numbers of Vertices with Applications to Connectomics](https://mlsanity.com/paper/2008.09434/) (2020)
- [Vertex nomination between graphs via spectral embedding and quadratic programming](https://mlsanity.com/paper/2010.14622/) (2020)
- [Valid Two-Sample Graph Testing via Optimal Transport Procrustes and Multiscale Graph Correlation with Applications in Connectomics](https://mlsanity.com/paper/1911.02741/) (2019)
- [Computational modeling of Human-nCoV protein-protein interaction network](https://mlsanity.com/paper/2005.04108/) (2020)

## Abstract (arXiv)

As graph data becomes more ubiquitous, the need for robust inferential graph algorithms 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 and algorithmic performance. We study this phenomenon 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 embeddings, which have been shown to provide both good algorithmic performance and flexible settings in which regularization techniques can be implemented to help mitigate 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 resulting graph. We propose a new trimming method that operates in model space which can address both block structure contamination and white noise contamination (contamination whose distribution is unknown). This model trimming is more amenable to theoretical analysis while also demonstrating superior performance in a number of simulations, compared to direct trimming.