Vertex nomination, consistent estimation, and adversarial modification

DOI10.1214/20-EJS1744zbMATH Open1448.62087arXiv1905.01776OpenAlexW3086536119MaRDI QIDQ2199707FDOQ2199707

Authors: Yanyan Li 

Publication date: 14 September 2020

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: Given a pair of graphs $G_1$ and $G_2$ and a vertex set of interest in $G_1$, the vertex nomination (VN) problem seeks to find the corresponding vertices of interest in $G_2$ (if they exist) and produce a rank list of the vertices in $G_2$, with the corresponding vertices of interest in $G_2$ concentrating, ideally, at the top of the rank list. In this paper, we define and derive the analogue of Bayes optimality for VN with multiple vertices of interest, and we define the notion of maximal consistency classes in vertex nomination. This theory forms the foundation for a novel VN adversarial contamination model, and we demonstrate with real and simulated data that there are VN schemes that perform effectively in the uncontaminated setting, and adversarial network contamination adversely impacts the performance of our VN scheme. We further define a network regularization method for mitigating the impact of the adversarial contamination, and we demonstrate the effectiveness of regularization in both real and synthetic data.

Full work available at URL: https://arxiv.org/abs/1905.01776

Recommendations

• On consistent vertex nomination schemes
• On the consistency of the likelihood maximization vertex nomination scheme: bridging the gap between maximum likelihood estimation and graph matching
• Vertex nomination schemes for membership prediction
• Vertex nomination: the canonical sampling and the extended spectral nomination schemes
• Toward quantifying vertex similarity in networks

zbMATH Keywords

statisticsnetworksrandom graphsadversarial machine learningvertex nomination

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Applications of graph theory (05C90) Estimation in multivariate analysis (62H12) Probabilistic graphical models (62H22)

Cites Work

• MCLUST: Software for model-based cluster analysis
• A nonparametric view of network models and Newman–Girvan and other modularities
• Spectral clustering and the high-dimensional stochastic blockmodel
• Automatic dimensionality selection from the scree plot via the use of profile likelihood
• Matrix estimation by universal singular value thresholding
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Community structure in social and biological networks
• Concentration and regularization of random graphs
• A generalized solution of the orthogonal Procrustes problem
• Fast unfolding of communities in large networks
• A nonparametric two-sample hypothesis testing problem for random graphs
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Vertex nomination via seeded graph matching
• A limit theorem for scaled eigenvectors of random dot product graphs
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• Random graph models of social networks
• Statistical inference on random dot product graphs: a survey
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Vertex nomination schemes for membership prediction
• Network classification with applications to brain connectomics
• Vertex nomination: the canonical sampling and the extended spectral nomination schemes
• Title not available (Why is that?)

Cited In (6)

• Vertex Nomination Between Graphs via Spectral Embedding and Quadratic Programming
• Subgraph nomination: query by example subgraph retrieval in networks
• Hypothesis testing for equality of latent positions in random graphs
• Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming
• Spectral analysis of networks with latent space dynamics and signs
• Vertex nomination: the canonical sampling and the extended spectral nomination schemes

Uses Software

• mclust

This page was built for publication: Vertex nomination, consistent estimation, and adversarial modification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2199707)