# Graph matching beyond perfectly-overlapping Erd\H{o}s--R\'enyi random graphs

@article{Hu2020GraphMB, title={Graph matching beyond perfectly-overlapping Erd\H\{o\}s--R\'enyi random graphs}, author={Ya Ting Hu and Wanjie Wang and Yi Yu}, journal={arXiv: Methodology}, year={2020} }

Graph matching is a fruitful area in terms of both algorithms and theories. In this paper, we exploit the degree information, which was previously used only in noiseless graphs and perfectly-overlapping Erdős--Renyi random graphs matching. We are concerned with graph matching of partially-overlapping graphs and stochastic block models, which are more useful in tackling real-life problems. We propose the edge exploited degree profile graph matching method and two refined varations. We conduct a… Expand

#### Figures and Tables from this paper

#### References

SHOWING 1-10 OF 35 REFERENCES

Seeded graph matching

- Computer Science, Mathematics
- Pattern Recognit.
- 2019

The state-of-the-art approximategraph matching algorithm "FAQ" of Vogelstein et al. (2015) is modified to make it a fast approximate seeded graph matching algorithm, adapt its applicability to include graphs with differently sized vertex sets, and extend the algorithm so as to provide, for each individual vertex, a nomination list of likely matches. Expand

Efficient random graph matching via degree profiles

- Mathematics, Computer Science
- ArXiv
- 2018

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

Seeded graph matching for correlated Erdös-Rényi graphs

- Mathematics, Computer Science
- J. Mach. Learn. Res.
- 2014

It is proved 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. Expand

Vertex nomination via seeded graph matching

- Computer Science, Mathematics
- Stat. Anal. Data Min.
- 2020

This work presents a principled methodology appropriate for situations in which the networks are too large for brute-force graph matching, and identifies Vertices in a local neighborhood of the vertices of interest in the first network that have verifiable corresponding vertices in the second network. Expand

A Graduated Assignment Algorithm for Graph Matching

- Mathematics, Computer Science
- IEEE Trans. Pattern Anal. Mach. Intell.
- 1996

A graduated assignment algorithm for graph matching is presented which is fast and accurate even in the presence of high noise, and not restricted to any special class of graph, is applied to subgraph isomorphism, weighted graph matching, and attributed relational graph matching. Expand

Graph Matching: Relax at Your Own Risk

- Computer Science, Mathematics
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 2016

It is proved that an indefinite relaxation (when solved exactly) almost always discovers the optimal permutation, while a common convex relaxation almost always fails to discover the optimalpermutation. Expand

When can two unlabeled networks be aligned under partial overlap?

- Mathematics, Computer Science
- 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)
- 2015

This paper defines a random bigraph model that generates two correlated graphs G1,2 and identifies a threshold for perfect matchability, and shows that network alignment is fundamentally robust to partial edge and node overlaps. Expand

A Short Survey of Recent Advances in Graph Matching

- Computer Science
- ICMR
- 2016

The aim is to provide a systematic and compact framework regarding the recent development and the current state-of-the-arts in graph matching. Expand

An Extended Path Following Algorithm for Graph-Matching Problem

- Mathematics, Computer Science
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 2012

The path following algorithm is extended to the matching problems on directed graph models by proposing a concave relaxation for the problem, based on the concave and convex relaxations, and the Frank-Wolfe algorithm is utilized to minimize them. Expand

Improved random graph isomorphism

- Computer Science, Mathematics
- J. Discrete Algorithms
- 2008

This work gives a simple, linear time, high probability algorithm for the canonical labeling of a G(n,p) random graph for p@?[@w(ln^4n/nlnlnn),1-@w-@Q(lnN/n)], and shows that the random graph isomorphism problem can be solved efficiently for p. Expand