Reproduce “The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models” 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
Lee M Gunderson, Gecia Bravo-Hermsdorff, Peter Orbanz
The Graph Pencil Method translates subgraph densities into parameters of a fixed-K stochastic block model. Star patterns recover block normalized degrees and proportions, while bistar patterns recover pairwise connection probabilities through a matrix-pencil construction. For degree-separated SBMs, stars through 2K-1 edges and bistars of maximum degree K suffice in the population-density setting, not as a finite-sample guarantee.
Key insights
- Homomorphism densities of star subgraphs up to 2K-1 edges and bistar subgraphs with maximum degree at most K are sufficient statistics to uniquely determine the parameters of a K-block degree-separated SBM.
- A generalization of Prony's method, via constructing matrix pencils from specific subgraph densities, allows for the direct recovery of SBM block degrees and connectivity probabilities as eigenvalues of matrix products.
- Incorporating densities from "two-hop" subgraphs (e.g., triangles) can significantly enhance the robustness and accuracy of the inferred connectivity matrix, especially for assortative or disassortative SBMs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.