Vertex nomination, consistent estimation, and adversarial modification
From MaRDI portal
Publication:2199707
Abstract: Given a pair of graphs and and a vertex set of interest in , the vertex nomination (VN) problem seeks to find the corresponding vertices of interest in (if they exist) and produce a rank list of the vertices in , with the corresponding vertices of interest in 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.
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
Cites work
- A generalized solution of the orthogonal Procrustes problem
- A limit theorem for scaled eigenvectors of random dot product graphs
- A nonparametric two-sample hypothesis testing problem for random graphs
- A nonparametric view of network models and Newman–Girvan and other modularities
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Automatic dimensionality selection from the scree plot via the use of profile likelihood
- Community structure in social and biological networks
- Concentration and regularization of random graphs
- Fast unfolding of communities in large networks
- MCLUST: Software for model-based cluster analysis
- Matrix estimation by universal singular value thresholding
- Network classification with applications to brain connectomics
- On consistent vertex nomination schemes
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Random graph models of social networks
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Spectral clustering and the high-dimensional stochastic blockmodel
- 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
- Vertex nomination via seeded graph matching
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
Cited in
(8)- Maximum a posteriori inference of random dot product graphs via conic programming
- 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
- Vertex nomination schemes for membership prediction
- On consistent vertex nomination schemes
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
- Spectral analysis of networks with latent space dynamics and signs
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)
