PaperlayerView exact revision on arXiv

Source-linked AI summary

Community Detection and Classification in Hierarchical Stochastic Blockmodels

Vince Lyzinski, Minh Tang, Avanti Athreya, Youngser Park, Carey E. Priebe

arXiv:1503.02115v5stat.MLstat.AP

TL;DR

The paper addresses scalable detection and comparison of communities and subcommunities in large graphs. It combines graph embedding, clustering, and nonparametric comparison recursively within a hierarchical stochastic blockmodel framework. The method has theoretical guarantees and is feasibly applied to the Drosophila connectome and the massive Friendster network, where it detects and classifies multiple similar communities.

  • Problem

    The paper addresses the need to consistently and scalably estimate communities and compare structurally similar subgraphs in large, complex networks.

  • Method

    The method embeds graphs, clusters vertices into subgraphs, tests subgraph distributions for equivalence, clusters motifs, and recursively analyzes representative subgraphs.

  • Results

    The algorithm has consistency guarantees for hierarchical stochastic blockmodels and is feasibly deployed on the Drosophila connectome and Friendster, detecting and classifying multiple similar communities.

  • Takeaways & Limitations

    Recursive community detection and classification can uncover finer-grained statistically similar structure in real biological and social graphs.

  • Takeaways & Limitations

    Finite-sample robustness to misclustered vertices and robustness when recursively clustering errorfully observed motifs remain open questions.

Abstract

from arXiv · show

We propose a robust, scalable, integrated methodology for community detection and community comparison in graphs. In our procedure, we first embed a graph into an appropriate Euclidean space to obtain a low-dimensional representation, and then cluster the vertices into communities. We next employ nonparametric graph inference techniques to identify structural similarity among these communities. These two steps are then applied recursively on the communities, allowing us to detect more fine-grained structure. We describe a hierarchical stochastic blockmodel---namely, a stochastic blockmodel with a natural hierarchical structure---and establish conditions under which our algorithm yields consistent estimates of model parameters and motifs, which we define to be stochastically similar groups of subgraphs. Finally, we demonstrate the effectiveness of our algorithm in both simulated and real data. Specifically, we address the problem of locating similar subcommunities in a partially reconstructed Drosophila connectome and in the social network Friendster.

1 INTRODUCTION

The paper develops a scalable framework for detecting communities and comparing their structural similarity across hierarchical graphs. It targets consistent, fine-grained recovery in settings ranging from connectomes to massive social networks.

  • Theory: Unlike conventional results focused on vanishing misclassification proportions, the paper studies recovery with no misclassified vertices.This stronger guarantee is presented for hierarchical stochastic blockmodels under suitable assumptions.
  • Theory: The paper provides a provably consistent algorithm for uncovering communities and subgraphs at multiple scales, including guarantees of perfect clustering under stated conditions.The required average degree grows at least at order √n log2(n).
  • Method: The framework embeds graphs into low-dimensional Euclidean spaces, clusters vertices into subgraphs, and compares subgraphs to identify statistically similar motifs.The procedure is applied recursively to uncover finer-grained hierarchical structure.
  • Model: The hierarchical stochastic blockmodel represents a large graph as smaller subgraphs that are themselves approximately stochastic blockmodels.The theory relies on an affinity assumption at each hierarchy level.
  • Applications: Experiments apply the methodology to repeated motifs in the Drosophila connectome and to 15 large Friendster subgraphs with hundreds of thousands of vertices.Friendster contains approximately 60 million users and 2 billion edges.

2 BACKGROUND

The paper frames graphs through random dot product and hierarchical stochastic blockmodels, then combines spectral embedding, subgraph clustering, and graph comparison to recover hierarchical structure and motifs.

  • Hierarchical stochastic blockmodels: A hierarchical stochastic blockmodel partitions vertices into subgraphs, each of which is itself a stochastic blockmodel.
  • Assumptions and limitations: The theoretical framework assumes affinity and subspace structure, while k-means alone cannot guarantee perfect subgraph clustering under only the affinity assumption.
  • Algorithm: The method embeds the graph, clusters vertices into subgraphs, compares induced subgraphs nonparametrically, and recursively analyzes representative subgraphs within motifs.
  • Spectral embedding: Adjacency spectral embedding consistently estimates latent positions, with 2→∞ concentration providing stronger control of individual row errors than Frobenius-norm bounds.
  • Clustering guarantees: Under mild model assumptions, the clustering procedure asymptotically perfectly clusters the rows of the estimated embedding.
  • Motif comparison: Motifs are collections of distributionally equivalent random dot product graphs, and a consistent hypothesis test identifies whether two graphs belong to the same motif.

3 DETECTING HIERARCHICAL STRUCTURE IN THE HSBM

The method embeds and clusters a graph, compares the resulting subgraphs with nonparametric inference, and recursively refines the hierarchy. Under the 2-level HSBM assumptions, it consistently estimates subgraphs and their motif similarities, recovering three motifs in simulation.

  • Algorithm: Algorithm 1 clusters the adjacency spectral embedding, compares induced subgraphs using a nonparametric test, and recurses within representative subgraphs for finer structure.The recursion embeds representative subgraphs into a lower-dimensional space before repeating the procedure.
  • Simulation: The 4,100-vertex synthetic HSBM contains eight blocks with three distinct motifs and inter-block edge probability bounded by p = 0.01.The block sizes are (300, 600, 600, 600, 700, 600, 300, 400).
  • Simulation: The algorithm correctly recovers three motif communities: {bH3, bH7}, {bH1, bH2, bH8}, and {bH4, bH5, bH6}.The heatmap represents community similarity from white, highly similar, to red, highly dissimilar.
  • Theory: Theorem 9 proves that, under its assumptions, the procedure perfectly estimates all subgraphs and the dissimilarity matrix asymptotically almost surely.The estimated dissimilarity entries converge to their population values as n →∞.
  • Theory: For different motifs, estimated-test p-values converge to 0, while p-values for the same motif remain bounded away from 0, enabling consistent motif clustering.Corollary 10 formalizes consistent clustering of the subgraphs from the matrix of p-values.
  • Theory: Theorem 9 is a proof-of-concept result for simple hierarchical structure and motivates extension to more complex hierarchies.

4 MULTILEVEL HSBM

The paper extends the hierarchical stochastic blockmodel and its inference procedure from two levels to arbitrarily many levels under multilevel assumptions. The resulting theory gives perfect motif detection at every level, while highlighting sparsity and recursive-error boundaries.

  • Theory: The multilevel theory follows from the two-level result by induction, extending the hierarchical graph structure beyond two levels.
  • Model: An ℓ-level HSBM recursively partitions a graph into subgraphs, each itself an h-level HSBM with h ≤ ℓ−1 and at least one component at level ℓ−1.The model is also an RDPG, and can be viewed as an SBM with potentially more than R(ℓ) blocks.
  • Assumptions: The multilevel model assumes affinity p^(k) < q^(k) at every level and imposes a subspace-structure condition on the latent positions.
  • Results: Theorem 12 states that Algorithm 1 achieves perfect motif detection and classification at every hierarchy level under modest assumptions.The proof relies on a 2 →∞ norm bound for the adjacency spectral embedding residuals.
  • Limitations: Perfect recovery is guaranteed only when the average degree is at least of order √n log^2(n); sparser-regime guarantees are conjectured for more robust inference tasks.
  • Limitations: When real graphs violate HSBM assumptions, recursive error propagation can arise from clustering errors, motif estimation, and subsequent analysis within erroneous subgraphs.The paper identifies finite-sample clustering as one source of degradation in motif-test power.
  • Limitations: Although testing is asymptotically robust to o(max_i nπ(i)) misclustered vertices, its finite-sample robustness remains open.

5 EXPERIMENTS

Experiments apply the methodology to the Drosophila connectome and Friendster, uncovering repeated motifs at multiple hierarchical levels. Recursive analysis further suggests that Friendster motifs capture stochastic blockmodel substructure.

  • Drosophila connectome: The Drosophila analysis applies adjacency spectral embedding, spherical projection, clustering, and estimated dissimilarity analysis to a 1,748-vertex connectome.The graph's largest connected component contains 1,748 vertices, and the embedding uses R13.
  • Drosophila connectome: Hierarchical clustering identifies Drosophila motifs {1, 4} and {2, 6, 8}, with second-level repetition within {6, 8}.The repeated motifs are obtained by clustering subgraphs using the estimated dissimilarity matrix bS.
  • Friendster network: Friendster contains roughly 60 million users, 2 billion edges, and 1 million local communities, motivating distributional comparison among community graphs.The analysis uses FlashGraph, embeds the graph into R14, and selects 15 coarse-grained clusters.
  • Friendster network: Hierarchical clustering of 15 Friendster communities suggests repeated motif structure at the coarse-grained level.The estimated pairwise dissimilarities are displayed in a 15×15 heat map and clustered with a dendrogram.
  • Friendster network: Comparing three Friendster subgraphs suggests that the repeated structure uncovered by the algorithm is stochastic blockmodel substructure.The analysis embeds, aligns, clusters, and estimates block connection and membership parameters before comparing the subgraphs.
  • Friendster network: Recursive analysis of subgraph bH11 produces 13 level-two clusters and reveals repeated motifs, including subgraphs 8 and 12.The method can be recursively applied to increasingly fine-grained scales.

6 CONCLUSION

The paper concludes with a theoretically supported algorithm for detecting and classifying communities in hierarchical stochastic blockmodels. Applications to Drosophila and Friendster demonstrate feasibility on real graphs, while recursive analysis targets finer-grained structure.

  • Contributions: The proposed algorithm combines consistent graph embedding with asymptotically powerful nonparametric tests to identify distributionally equivalent subgraphs called motifs.For two-level hierarchical stochastic blockmodels, the paper establishes consistency of induced-subgraph estimates and validity of subsequent tests.
  • Scope: The hierarchical stochastic blockmodel captures smaller densely connected subgraphs that are somewhat loosely connected across, a structure present in many networks.The theoretical results are situated primarily in random dot product graphs, which can approximate many independent-edge graphs.
  • Empirical scope: Applications to the Drosophila connectome and Friendster demonstrate feasible deployment on real graphs, including a very large network.The implementation leverages FlashGraph and igraph to reduce computation time.
  • Empirical scope: Both real-data analyses detect and classify multiple similar communities, and recursive application can uncover finer-grained structure.The paper identifies functional or structural interpretation of these communities as ongoing research.

APPENDIX

The appendix defines the random dot product graph and its spectral embedding, then states the asymptotic result that underpins the embedding analysis. The model uses latent positions, a sparsity factor, and a rank-d second moment matrix.

  • RDPG definition: An RDPG samples independent latent positions X1,…,Xn from F and forms P = ρnXX⊤.The distribution satisfies x⊤y ∈ [0,1], and the sparsity factor obeys ρn ≤ 1.
  • RDPG definition: Conditional on the latent positions, the adjacency matrix is symmetric, hollow, and has independent upper-triangular edges.The edge probabilities are determined by the latent-position model.
  • Assumptions: The latent-position second moment matrix Δ is assumed to have rank d.This rank condition determines the embedding dimension used in the model.
  • Embedding: The adjacency spectral embedding estimates latent positions from the d eigenvalues and eigenvectors of the adjacency matrix, with an analogous decomposition for P.The embedding uses the eigenvalues of largest magnitude and the corresponding eigenvectors.
  • Asymptotic result: Theorem 5 follows from a more general theorem asserting asymptotically almost sure accuracy under the stated RDPG conditions.Theorem 15 is formulated for rank-d second moment matrices and sparsity factor ρn.

Proof of Theorem 15

The proof controls spectral embedding error by bounding perturbations of the adjacency matrix and its eigenspaces. It combines concentration, subspace perturbation, and orthogonal-alignment arguments to obtain asymptotic accuracy.

  • Proof strategy: The proof reduces embedding accuracy to controlling the perturbation A−P and the alignment between empirical and population eigenspaces.The argument uses residual projections, singular values, and an orthogonal transformation.
  • Eigenspace control: A Davis–Kahan sin(Θ) argument controls the principal angles between the empirical and population eigenspaces.The eigengap is expressed through λd(P), while the spectral norm of A−P supplies the perturbation bound.
  • Concentration: Hoeffding’s inequality bounds entries of (A−P)UP, yielding an asymptotically almost sure O(log n) control after a union bound.The bound is applied across indices and columns of UP.
  • Error bound: The resulting aligned spectral embedding error is O(log n(nρn)^−1/2) asymptotically almost surely.The rate follows by relating perturbation terms to the diagonal spectral scaling.
  • Extension: Theorem 18 extends adjacency spectral embedding Frobenius-norm accuracy to cases where the second moment matrix lacks distinct eigenvalues.The theorem states an asymptotically almost sure event involving an orthogonal alignment.
  • Conclusion: The proof combines orthogonal transformations to establish the final aligned embedding guarantee.The concluding step uses the fact that the product of orthogonal matrices is orthogonal.

Proof of Lemma 6

The proof establishes that Algorithm 2 asymptotically preserves one representative from each community while adding vertices from previously unrepresented communities. This follows from Proposition 19 and the asymptotic separation condition ˆp < ˆq.

  • Proof of Lemma 6: The proof concludes Lemma 6 from Proposition 19 together with the fact that ˆp < ˆq asymptotically almost surely.
  • Proposition 19: Proposition 19 shows that the event governing Algorithm 2’s set S_n occurs asymptotically almost surely.The proposition applies under the assumptions of Lemmas 5 and 6.
  • Proof of Proposition 19: If a vertex from C_j is absent from S_{i−1}, Algorithm 2 adds its row bX(i, :) to S_{i−1}.The proof uses the bound max s∈S_{i−1}⟨bX(i, :), s⟩ ≤ ˆp.
  • Proof of Proposition 19: If S_{i−1} contains exactly one element s from C_j, then s remains in S_i rather than being removed.When another community has two representatives, the pigeonhole principle gives an inner product at least ˆq, supporting the preservation argument.
  • Proof of Lemma 6: Asymptotically almost surely, S_n contains a single row of bξ(j) for every community j.The proof of Lemma 6 then uses the asymptotic inequality ˆp < ˆq.
Loading 1503.02115v5…