Seeded graph matching for correlated Erdős-Rényi graphs
From MaRDI portal
(Redirected from Publication:5249582)
Abstract: Graph matching is an important problem in machine learning and pattern recognition. Herein, we present theoretical and practical results on the consistency of graph matching for estimating a latent alignment function between the vertex sets of two graphs, as well as subsequent algorithmic implications when the latent alignment is partially observed. In the correlated ErdH{o}s-R'enyi graph setting, we prove that graph matching provides a strongly consistent estimate of the latent alignment in the presence of even modest correlation. We then investigate a tractable, restricted-focus version of graph matching, which is only concerned with adjacency involving vertices in a partial observation of the latent alignment; we prove that a logarithmic number of vertices whose alignment is known is sufficient for this restricted-focus version of graph matching to yield a strongly consistent estimate of the latent alignment of the remaining vertices. We show how Frank-Wolfe methodology for approximate graph matching, when there is a partially observed latent alignment, inherently incorporates this restricted focus graph matching. Lastly, we illustrate the relationship between seeded graph matching and restricted-focus graph matching by means of an illuminating example from human connectomics.
Recommendations
Cited in
(22)- Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
- On a complete and sufficient statistic for the correlated Bernoulli random graph model
- Correlated randomly growing graphs
- Shuffled graph classification: theory and connectome applications
- Efficient random graph matching via degree profiles
- Vertex nomination via seeded graph matching
- Matchability of heterogeneous networks pairs
- scientific article; zbMATH DE number 7626795 (Why is no real title available?)
- Vertex Nomination Between Graphs via Spectral Embedding and Quadratic Programming
- Aligning random graphs with a sub-tree similarity message-passing algorithm
- Dynamic Stochastic Blockmodel Regression for Network Data: Application to International Militarized Conflicts
- Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis
- Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
- Matching recovery threshold for correlated random graphs
- A computational transition for detecting correlated stochastic block models by low-degree polynomials
- Low-degree hardness of detection for correlated Erdős-Rényi graphs
- Alignment and comparison of directed networks via transition couplings of random walks
- Efficiently matching random inhomogeneous graphs via degree profiles
- A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
- The algorithmic phase transition of random graph alignment problem
- Graph matching based on similarities in structure and attributes
- On Seeded Subgraph-to-Subgraph Matching: The ssSGM Algorithm and Matchability Information Theory
This page was built for publication: Seeded graph matching for correlated Erdős-Rényi graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249582)
