Reproduce “Exact Recovery in the Data Block Model” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Amir R. Asadi, Akbar Davoodi, Ramin Javadi, Farzad Parvaresh
A new information-theoretic measure, the Chernoff–TV divergence, characterizes a sharp threshold for exact community recovery in the Data Block Model, which integrates both network structure and node attributes. This framework enables perfect community identification with a polynomial-time algorithm, consistently outperforming graph-only methods by achieving high exact recovery probability at lower network densities.
Key insights
- The Chernoff–TV divergence precisely quantifies the combined power of network topology and node attributes for exact community recovery in the Data Block Model.
- A sharp phase transition exists for exact recovery: it is achievable if and only if the normalized Chernoff–TV separation for all distinct community pairs exceeds one.
- Node-associated data provides a quantifiable advantage, allowing exact community recovery in scenarios where the graph structure alone is too sparse or uninformative for successful detection.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.