Consistency of Spectral Clustering on Hierarchical Stochastic Block Models

• URL: http://arxiv.org/abs/2004.14531v2
• Date: Thu, 18 Nov 2021 18:12:41 GMT
• Title: Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
• Authors: Lihua Lei, Xiaodong Li, and Xingmei Lou
• Abstract summary: We study the hierarchy of communities in real-world networks under a generic block model. We prove the strong consistency of this method under a wide range of model parameters. Unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude.
• Score: 5.983753938303726
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the hierarchy of communities in real-world networks under a generic stochastic block model, in which the connection probabilities are structured in a binary tree. Under such model, a standard recursive bi-partitioning algorithm is dividing the network into two communities based on the Fiedler vector of the unnormalized graph Laplacian and repeating the split until a stopping rule indicates no further community structures. We prove the strong consistency of this method under a wide range of model parameters, which include sparse networks with node degrees as small as $O(\log n)$. In addition, unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude, which comprise an important class of models that are practically relevant but technically challenging to deal with. Finally we demonstrate the performance of our algorithm on synthetic data and real-world examples.

Related papers

• Nested stochastic block model for simultaneously clustering networks and nodes [9.860884833526407]
  We introduce the nested block model (NSBM) to cluster a collection of networks while simultaneously detecting communities within each network. NSBM has several appealing features including the ability to work on unlabeled networks with potentially different node sets.
  arXiv  Detail & Related papers  (2023-07-18T12:46:34Z)
• Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering [4.264842058017711]
  Community detection is a critical challenge in analysing real graphs. This article proposes three new, general, hierarchical frameworks to deal with this task. We compare over a hundred module combinations on the Block Model graphs and real-life datasets.
  arXiv  Detail & Related papers  (2023-03-21T22:12:53Z)
• Linear Connectivity Reveals Generalization Strategies [54.947772002394736]
  Some pairs of finetuned models have large barriers of increasing loss on the linear paths between them. We find distinct clusters of models which are linearly connected on the test loss surface, but are disconnected from models outside the cluster. Our work demonstrates how the geometry of the loss surface can guide models towards different functions.
  arXiv  Detail & Related papers  (2022-05-24T23:43:02Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  Block model is a canonical random graph model for clustering and community detection on network-structured data. No estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. We prove that with an arbitrary fraction of the labels feasible throughout the parameter domain.
  arXiv  Detail & Related papers  (2022-05-24T00:03:25Z)
• Bayesian Structure Learning with Generative Flow Networks [85.84396514570373]
  In Bayesian structure learning, we are interested in inferring a distribution over the directed acyclic graph (DAG) from data. Recently, a class of probabilistic models, called Generative Flow Networks (GFlowNets), have been introduced as a general framework for generative modeling. We show that our approach, called DAG-GFlowNet, provides an accurate approximation of the posterior over DAGs.
  arXiv  Detail & Related papers  (2022-02-28T15:53:10Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Tractably Modelling Dependence in Networks Beyond Exchangeability [0.0]
  We study the estimation, clustering and degree behavior of the network in our setting. This explores why and under which general conditions non-exchangeable network data can be described by a block model.
  arXiv  Detail & Related papers  (2020-07-28T17:13:59Z)
• A Multi-Semantic Metapath Model for Large Scale Heterogeneous Network Representation Learning [52.83948119677194]
  We propose a multi-semantic metapath (MSM) model for large scale heterogeneous representation learning. Specifically, we generate multi-semantic metapath-based random walks to construct the heterogeneous neighborhood to handle the unbalanced distributions. We conduct systematical evaluations for the proposed framework on two challenging datasets: Amazon and Alibaba.
  arXiv  Detail & Related papers  (2020-07-19T22:50:20Z)
• Monotone operator equilibrium networks [97.86610752856987]
  We develop a new class of implicit-depth model based on the theory of monotone operators, the Monotone Operator Equilibrium Network (monDEQ) We show the close connection between finding the equilibrium point of an implicit network and solving a form of monotone operator splitting problem. We then develop a parameterization of the network which ensures that all operators remain monotone, which guarantees the existence of a unique equilibrium point.
  arXiv  Detail & Related papers  (2020-06-15T17:57:31Z)
• Struct-MMSB: Mixed Membership Stochastic Blockmodels with Interpretable Structured Priors [13.712395104755783]
  Mixed membership blockmodel (MMSB) is a popular framework for community detection and network generation. We present a flexible MMSB model, textitStruct-MMSB, that uses a recently developed statistical relational learning model, hinge-loss Markov random fields (HL-MRFs) Our model is capable of learning latent characteristics in real-world networks via meaningful latent variables encoded as a complex combination of observed features and membership distributions.
  arXiv  Detail & Related papers  (2020-02-21T19:32:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.