# Random Graph Matching with Improved Noise Robustness

@article{Mao2021RandomGM, title={Random Graph Matching with Improved Noise Robustness}, author={Cheng Mao and Mark Rudelson and Konstantin E. Tikhomirov}, journal={ArXiv}, year={2021}, volume={abs/2101.11783} }

Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a… Expand

#### 3 Citations

Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities

- Mathematics, Computer Science
- ArXiv
- 2021

It is shown how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. Expand

Exact Matching of Random Graphs with Constant Correlation

- Mathematics, Computer Science
- ArXiv
- 2021

This is the first polynomial-time algorithm that recovers the exact matching between vertices of correlated Erdős–Rényi graphs with constant correlation with high probability, based on comparison of partition trees associated with the graph vertices. Expand

Testing network correlation efficiently via counting trees

- Mathematics
- 2021

We propose a new procedure for testing whether two networks are edge-correlated through some latent vertex correspondence. The test statistic is based on counting the co-occurrences of signed trees… Expand

#### References

SHOWING 1-10 OF 44 REFERENCES

Efficient random graph matching via degree profiles

- Mathematics, Computer Science
- Probability Theory and Related Fields
- 2020

This work develops an O ~ ( n d 2 + n 2 ) -time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least d = \varOmega (\log ^2 n) and the two graphs differ by at most d = O ( log - 2 ( n) ) fraction of edges. Expand

Correlated randomly growing graphs

- Mathematics, Computer Science
- ArXiv
- 2020

A new model of correlated randomly growing graphs is introduced and it is shown that whenever the seed graph has an influence in the underlying graph growth model, then correlation can be detected in this model, even if the graphs are grown together for just a single time step. Expand

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

- Computer Science, Mathematics
- NeurIPS
- 2019

A quasipolynomial time algorithm that given a pair of $\gamma$-correlated $G(n,p)$ graphs, recovers the "ground truth" permutation $\pi\in S_n$ that matches the vertices of $G_0$ to the Vertices of G_n in the way that minimizes the number of mismatched edges. Expand

Seeded Graph Matching via Large Neighborhood Statistics

- Computer Science, Mathematics
- SODA
- 2019

It is shown that it is possible to achieve the information-theoretic limit of graph sparsity in time polynomial in the number of vertices, which can be as low as $n^{3\epsilon}$ in the sparse graph regime (with the average degree smaller than $n^{\epsil on}$) and $\Omega(\log n) $ in the dense graph regime. Expand

Growing a Graph Matching from a Handful of Seeds

- Computer Science
- Proc. VLDB Endow.
- 2015

A new graph--matching algorithm is given that can operate with a much smaller seed set than previous approaches, with only a small increase in matching errors, and is characterized a phase transition in matching performance as a function of the seed set size. Expand

Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs

- Mathematics, Computer Science
- IEEE Transactions on Information Theory
- 2021

This work develops a polynomial-time algorithm that attains the threshold for exact recovery under the small-world model and analyzes several computationally efficient algorithms that provide sufficient conditions under which they achieve exact/almost exact recovery. Expand

From tree matching to sparse graph alignment

- Computer Science, Mathematics
- COLT
- 2020

This paper considers alignment of sparse graphs, for which the Neighborhood Tree Matching Algorithm (NTMA) is introduced, and proves that the algorithm returns a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. Expand

Graph Matching with Partially-Correct Seeds

- Computer Science, Mathematics
- ArXiv
- 2020

This work studies a version of the seeded graph matching problem, which assumes that a set of seeds, i.e., pre-mapped vertex-pairs, is given in advance, and proposes a new algorithm that uses "witnesses" in the 2-hop neighborhood, instead of only 1-hop Neighborhood as in lubars2018correcting. Expand

Partial Recovery in the Graph Alignment Problem

- Mathematics, Computer Science
- ArXiv
- 2020

This paper considers the graph alignment problem, which is the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap and shows that it is possible to achieve partial recovery in the $nqs=\Theta(1)$ regime under certain additional assumptions. Expand

Partial Recovery of Erdős-Rényi Graph Alignment via k-Core Alignment

- Computer Science
- Abstracts of the 2020 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems
- 2020

The k-core alignment estimator is introduced and a matching converse bound is proved that recovery of the alignment for a fraction of the vertices tending to one is possible when the average degree of the intersection of the graph pair tends to infinity. Expand