Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation
Jul 24, 2023
Speakers
Joonhyuk Yang
Speaker · 0 followers
Dongpil Shin
Speaker · 0 followers
Hye Won Chung
Speaker · 0 followers
About
We consider the problem of graph matching or learning vertex correspondence between two correlated stochastic block models (SBM).The graph matching problem arises in various fields including computer vision, natural language processing and bioinformatics, and in particular, matching graphs with inherent community structure has significance related to de-anonymization of correlated social networks. Compared to the correlated Erdos-Renyi (ER) model, where various efficient algorithms have been developed among which a few algorithms have been proven to achieve the exact matching in constant edge correlation, no low-order polynomial algorithm has been known to achieve the exact matching for the correlated SBM graphs with constant correlation. In this work, we propose an efficient algorithm for matching graphs with community structure, based on the comparison between partition trees rooted from each vertex, by extending the idea of Mao et al. (2021) to graphs with communities. The partition tree divides the large neighborhoods of each vertex into disjoint subsets using their edge statistics to different communities. Our algorithm is the first low-order polynomial-time algorithm achieving the exact matching between two correlated SBM with high probability in dense graphs.We consider the problem of graph matching or learning vertex correspondence between two correlated stochastic block models (SBM).The graph matching problem arises in various fields including computer vision, natural language processing and bioinformatics, and in particular, matching graphs with inherent community structure has significance related to de-anonymization of correlated social networks. Compared to the correlated Erdos-Renyi (ER) model, where various efficient algorithms have been dev…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Kernel Logistic Regression Approximation of an Understandable ReLU Neural Network
Watch later
Fairness in Matching under Uncertainty
Watch later
Sid Devic, …
The Quest for Small Models (and what it might tell us about bigger ones)
Watch later
MALTS: Matching After Learning to Stretch
Watch later
PAC-Bayesian Offline Contextual Bandits with Guarantees
Watch later
Otmane Sakhi, …
