Consistency of spectral hypergraph partitioning under planted partition model
From MaRDI portal
(Redirected from Publication:524460)
Abstract: Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received attention in the literature as compared to the extensive studies on the guarantees of graph partitioning. For instance, consistency results of spectral graph partitioning under the stochastic block model are well known. In this paper, we present a planted partition model for sparse random non-uniform hypergraphs that generalizes the stochastic block model. We derive an error bound for a spectral hypergraph partitioning algorithm under this model using matrix concentration inequalities. To the best of our knowledge, this is the first consistency result related to partitioning non-uniform hypergraphs.
Recommendations
- Uniform hypergraph partitioning: provable tensor methods and sampling techniques
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- Graph-Theoretic Concepts in Computer Science
- Spectral Clustering by Recursive Partitioning
- Community detection in the sparse hypergraph stochastic block model
Cited in
(34)- Sparse random tensors: concentration, regularization and applications
- Testing community structure for hypergraphs
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Tensor clustering with planted structures: statistical optimality and computational limits
- Limiting distribution of short cycles in inhomogeneous random uniform hypergraph
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm
- Sharp detection boundaries on testing dense subhypergraph
- A bounded-confidence model of opinion dynamics on hypergraphs
- Test dense subgraphs in sparse uniform hypergraph
- Nonparametric modeling of higher-order interactions via hypergraphons
- A sharp blockwise tensor perturbation bound for orthogonal iteration
- Uniform hypergraph partitioning: provable tensor methods and sampling techniques
- Graph-Theoretic Concepts in Computer Science
- Multilayer hypergraph clustering using the aggregate similarity matrix
- Marchenko–Pastur law with relaxed independence conditions
- On the efficacy of higher-order spectral clustering under weighted stochastic block models
- Community detection in the sparse hypergraph stochastic block model
- Community Detection in General Hypergraph Via Graph Embedding
- Generalizing p-Laplacian: spectral hypergraph theory and a partitioning algorithm
- A family of pairwise multi-marginal optimal transports that define a generalized metric
- Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs
- What Are Higher-Order Networks?
- Phase transitions in a power-law uniform hypergraph
- Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
- Community Detection in Censored Hypergraph
- Model-based clustering in simple hypergraphs through a stochastic blockmodel
- Latent Space Modeling of Hypergraph Data
- Sparse random hypergraphs: non-backtracking spectra and community detection
- Heterogeneous dense subhypergraph detection
- Optimal and exact recovery on the general nonuniform hypergraph stochastic block model
- Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
- Modeling Hypergraphs with Diversity and Heterogeneous Popularity
- Phase transition detection in the community detection for hypergraph network via tensor method
- Independent sets in semi-random hypergraphs
This page was built for publication: Consistency of spectral hypergraph partitioning under planted partition model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q524460)
