Timezone: »

 
Poster
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
Boaz Barak · Chi-Ning Chou · Zhixian Lei · Tselil Schramm · Yueqi Sheng

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #210
in Theory -- Computational Complexity »
We consider the graph matching/similarity problem of determining how similar two given graphs $G_0,G_1$ are and recovering the permutation $\pi$ on the vertices of $G_1$ that minimizes the symmetric difference between the edges of $G_0$ and $\pi(G_1)$. Graph matching/similarity has applications for pattern matching, vision, social network anonymization, malware analysis, and more. We give the first efficient algorithms proven to succeed in the correlated Erdös-Rényi model (Pedarsani and Grossglauser, 2011). Specifically, we give a polynomial time algorithm for the graph similarity/hypothesis testing task which works for every constant level of correlation between the two graphs that can be arbitrarily close to zero. We also give a quasi-polynomial ($n^{O(\log n)}$ time) algorithm for the graph matching task of recovering the permutation minimizing the symmetric difference in this model. This is the first algorithm to do so without requiring as additional input a ``seed'' of the values of the ground truth permutation on at least $n^{\Omega(1)}$ vertices. Our algorithms follow a general framework of counting the occurrences of subgraphs from a particular family of graphs allowing for tradeoffs between efficiency and accuracy.
Keywords: Theory
[ Paper]  [ Slides] 

Author Information

Boaz Barak (Harvard University)
Chi-Ning Chou (Harvard University)
Zhixian Lei (Harvard University)
Tselil Schramm (Harvard University)
Yueqi Sheng (Harvard University )

More from the Same Authors