The graph matching problem aims to find the latent vertex correspondence between two edge-correlated graphs and has many practical applications . In this work , we study 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.  Specifically, consider two correlated graphs whose edges are sampled independently with probability s from a parent \ER graph G(n,p). Furthermore, a mapping between the vertices of the two graphs is provided as seeds, of which an unknown \beta fraction is correct. This problem was first studied in \mbox{%DIFAUXCMD lubars2018correcting0pt%DIFAUXCMD where an algorithm is proposed and shown to perfectly recover the correct vertex mapping with high probability if \beta\geq\max}%DIFDELCMD < \left\{%%% \frac{8{3}p,16\log{n}{nps^2}}%DIFDELCMD < \right\}%%% . We improve their condition to \beta\geq\max%DIFDELCMD < \left\{%%% 30\sqrt{\frac{\log n{n(1-p)^2s^2}},\frac{45\log{n}}{np(1-p)^2s^2}}%DIFDELCMD < \right)%%% . However, when p=O%DIFDELCMD < \left( %%% \sqrt{{\log n/{ns^2}}}%DIFDELCMD < \right)%%% , our improved condition still requires that \beta must increase inversely proportional to np. In order to improve the matching performance for sparse graphs, we propose a new algorithm that uses "witnesses" in the 2-hop neighborhood, instead of only 1-hop neighborhood as in \mbox{%DIFAUXCMD \cite{lubars2018correcting}\hspace{0pt}%DIFAUXCMD . We show that when np^2\leq\frac{1}{135\log n}, our new algorithm can achieve perfect recovery with high probability if \beta\geq\max}%DIFDELCMD < \left\{%%% 900\sqrt{\frac{np^3(1-s)\log n{s}}, 600\sqrt{\frac{\log n}{ns^4}}, \frac{1200\log n}{n^2p^2s^4}}%DIFDELCMD < \right\} %%% and nps^2\geq 128\log n }\hspace{0pt}%DIFAUXCMD when p}\ge . For instance, when p is a constant or p=n^{-3/4}, we show that only \Omega(\sqrt{n\log n}) correct seeds suffice for perfect matching, while the previously best-known results demand \Omega(n) and \Omega(n^{3/4}\log n) correct seeds, respectively} . Numerical experiments on both synthetic and real graphs corroborate our theoretical findings and show that our 2-hop algorithm significantly outperforms the 1-hop algorithm when the graphsare relatively sparse .
Graph matching aims to find the latent vertex correspondence between two edge-correlated graphs and has found numerous applications across different fields . In this paper , we study a seeded graph matching problem, which assumes that a set of seeds, i.e., pre-mapped vertex-pairs, is given in advance. While most previous work requires all seeds to be correct, we focus on the setting where the seeds are partially correct. Specifically, consider two correlated graphs whose edges are sampled independently from a parent \ER graph G(n,p). A mapping between the vertices of the two graphs is provided as seeds, of which an unknown \beta fraction is correct. 0pt%DIFAUXCMD where an algorithm is proposed and shown to perfectly recover the correct vertex mapping with high probability if \beta\geq\max}%DIFDELCMD < \left\{%%% {3}p,16\log{n}{nps^2}}%DIFDELCMD < \right\}%%% %DIFDELCMD < \left\{%%% {n(1-p)^2s^2}},\frac{45\log{n}}{np(1-p)^2s^2}}%DIFDELCMD < \right)%%% %DIFDELCMD < \left( %%% /{ns^2}}}%DIFDELCMD < \right)%%% We first analyze a simple algorithm that matches vertices based on the number of common seeds in the 1-hop neighborhoods, and then further propose a new algorithm that uses seeds in the 2-hop neighborhoods. We establish non-asymptotic performance guarantees of perfect matching for both 1-hop }\hspace{0pt}%DIFAUXCMD . We show that when np^2\leq\frac{1}{135\log n}, our new algorithm can achieve perfect recovery with high probability if \beta\geq\max}%DIFDELCMD < \left\{%%% {s}}, 600\sqrt{\frac{\log n}{ns^4}}, \frac{1200\log n}{n^2p^2s^4}}%DIFDELCMD < \right\} %%% and 2-hop algorithms, showing that our new 2-hop algorithm requires substantially fewer correct seeds than the 1-hop algorithm when graphs are sparse. Moreover, by combining our new performance guarantees for the 1-hop and 2-hop algorithms, we attain the best-known results (in terms of the required fraction of correct seeds) across the entire range of graph sparsity and significantly improve the previous results in \mbox{%DIFAUXCMD \cite{10.14778/2794367.2794371,lubars2018correcting }\hspace{0pt}%DIFAUXCMD when p}\ge n^{-5/6. For instance, when p is a constant or p=n^{-3/4}, we show that only \Omega(\sqrt{n\log n}) correct seeds suffice for perfect matching, while the previously best-known results demand \Omega(n) and \Omega(n^{3/4}\log n) correct seeds, respectively} . Numerical experiments corroborate our theoretical findings , demonstrating the superiority of our 2-hop algorithm on a variety of synthetic and real graphs .
R
The graph matching problem
Graph matching
R
many practical applications
found numerous applications across different fields
R
work
paper
D
version of the
A
While most previous work requires all seeds to be correct, we focus on the setting where the seeds are partially correct.
D
with probability s
R
Furthermore, a
A
D
This problem was first studied in \mbox{%DIFAUXCMD lubars2018correcting
D
\frac{8
D
. We improve their condition to \beta\geq\max
D
30\sqrt{\frac{\log n
D
. However, when p=O
D
\sqrt{{\log n
R
, our improved condition still requires that \beta must increase inversely proportional to np. In order to improve the matching performance for sparse graphs, we
We first analyze a simple algorithm that matches vertices based on the number of common seeds in the 1-hop neighborhoods, and then further
R
"witnesses"
seeds
R
neighborhood, instead of only
neighborhoods. We establish non-asymptotic performance guarantees of perfect matching for both
D
neighborhood as in \mbox{%DIFAUXCMD \cite{lubars2018correcting
D
900\sqrt{\frac{np^3(1-s)\log n
R
and nps^2\geq 128\log n
and 2-hop algorithms, showing that our new 2-hop algorithm requires substantially fewer correct seeds than the 1-hop algorithm when graphs are sparse. Moreover, by combining our new performance guarantees for the 1-hop and 2-hop algorithms, we attain the best-known results (in terms of the required fraction of correct seeds) across the entire range of graph sparsity and significantly improve the previous results in \mbox{%DIFAUXCMD \cite{10.14778/2794367.2794371,lubars2018correcting
A
n^{-5/6
D
on both synthetic and real graphs
R
and show that
, demonstrating the superiority of
R
significantly outperforms the 1-hop algorithm when the graphsare relatively sparse
on a variety of synthetic and real graphs