Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix

Kalle Alaluusua; Konstantin Avrachenkov; B. R.Vinay Kumar; Lasse Leskelä

doi:10.1007/978-3-031-32296-9_6

Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix

Kalle Alaluusua^*
, Konstantin Avrachenkov
, B. R.Vinay Kumar
, Lasse Leskelä

^*Corresponding author for this work

INRIA Rennes

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

4 Citations (Scopus)

Abstract

We consider the community recovery problem on a multilayer variant of the hypergraph stochastic block model (HSBM). Each layer is associated with an independent realization of a d-uniform HSBM on N vertices. Given the similarity matrix containing the aggregated number of hyperedges incident to each pair of vertices, the goal is to obtain a partition of the N vertices into disjoint communities. In this work, we investigate a semidefinite programming (SDP) approach and obtain information–theoretic conditions on the model parameters that guarantee exact recovery both in the assortative and the disassortative cases.

Original language	English
Title of host publication	Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings
Editors	Megan Dewar, François Théberge, Paweł Prałat, Przemysław Szufel, Małgorzata Wrzosek
Publisher	Springer
Pages	83-98
Number of pages	16
ISBN (Print)	978-3-031-32295-2
DOIs	https://doi.org/10.1007/978-3-031-32296-9_6
Publication status	Published - 2023
MoE publication type	A4 Conference publication
Event	Workshop on Algorithms and Models for the Web Graph - Toronto, Canada Duration: 23 May 2023 → 26 May 2023 Conference number: 18

Publication series

Name	Lecture Notes in Computer Science
Volume	13894 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	Workshop on Algorithms and Models for the Web Graph
Abbreviated title	WAW
Country/Territory	Canada
City	Toronto
Period	23/05/2023 → 26/05/2023

Keywords

clustering
community detection
hypergraph SBM
multilayer
planted partition
semidefinite programming

Access to Document

10.1007/978-3-031-32296-9_6

https://arxiv.org/abs/2301.11657

Cite this

Alaluusua, K., Avrachenkov, K., Kumar, B. R. V., & Leskelä, L. (2023). Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix. In M. Dewar, F. Théberge, P. Prałat, P. Szufel, & M. Wrzosek (Eds.), Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings (pp. 83-98). (Lecture Notes in Computer Science; Vol. 13894 LNCS). Springer. https://doi.org/10.1007/978-3-031-32296-9_6

Alaluusua, Kalle ; Avrachenkov, Konstantin ; Kumar, B. R.Vinay et al. / Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix. Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings. editor / Megan Dewar ; François Théberge ; Paweł Prałat ; Przemysław Szufel ; Małgorzata Wrzosek. Springer, 2023. pp. 83-98 (Lecture Notes in Computer Science).

@inproceedings{9e4ff38ad1e74a3fb1e77482063b49de,

title = "Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix",

abstract = "We consider the community recovery problem on a multilayer variant of the hypergraph stochastic block model (HSBM). Each layer is associated with an independent realization of a d-uniform HSBM on N vertices. Given the similarity matrix containing the aggregated number of hyperedges incident to each pair of vertices, the goal is to obtain a partition of the N vertices into disjoint communities. In this work, we investigate a semidefinite programming (SDP) approach and obtain information–theoretic conditions on the model parameters that guarantee exact recovery both in the assortative and the disassortative cases.",

keywords = "clustering, community detection, hypergraph SBM, multilayer, planted partition, semidefinite programming",

author = "Kalle Alaluusua and Konstantin Avrachenkov and Kumar, \{B. R.Vinay\} and Lasse Leskel{\"a}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; Workshop on Algorithms and Models for the Web Graph, WAW ; Conference date: 23-05-2023 Through 26-05-2023",

year = "2023",

doi = "10.1007/978-3-031-32296-9\_6",

language = "English",

isbn = "978-3-031-32295-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "83--98",

editor = "Megan Dewar and Fran{\c c}ois Th{\'e}berge and Pawe{\l} Pra{\l}at and Przemys{\l}aw Szufel and Ma{\l}gorzata Wrzosek",

booktitle = "Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings",

address = "Germany",

}

Alaluusua, K, Avrachenkov, K, Kumar, BRV & Leskelä, L 2023, Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix. in M Dewar, F Théberge, P Prałat, P Szufel & M Wrzosek (eds), Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings. Lecture Notes in Computer Science, vol. 13894 LNCS, Springer, pp. 83-98, Workshop on Algorithms and Models for the Web Graph, Toronto, Ontario, Canada, 23/05/2023. https://doi.org/10.1007/978-3-031-32296-9_6

Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix. / Alaluusua, Kalle; Avrachenkov, Konstantin; Kumar, B. R.Vinay et al.
Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings. ed. / Megan Dewar; François Théberge; Paweł Prałat; Przemysław Szufel; Małgorzata Wrzosek. Springer, 2023. p. 83-98 (Lecture Notes in Computer Science; Vol. 13894 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix

AU - Alaluusua, Kalle

AU - Avrachenkov, Konstantin

AU - Kumar, B. R.Vinay

AU - Leskelä, Lasse

N1 - Conference code: 18

PY - 2023

Y1 - 2023

N2 - We consider the community recovery problem on a multilayer variant of the hypergraph stochastic block model (HSBM). Each layer is associated with an independent realization of a d-uniform HSBM on N vertices. Given the similarity matrix containing the aggregated number of hyperedges incident to each pair of vertices, the goal is to obtain a partition of the N vertices into disjoint communities. In this work, we investigate a semidefinite programming (SDP) approach and obtain information–theoretic conditions on the model parameters that guarantee exact recovery both in the assortative and the disassortative cases.

AB - We consider the community recovery problem on a multilayer variant of the hypergraph stochastic block model (HSBM). Each layer is associated with an independent realization of a d-uniform HSBM on N vertices. Given the similarity matrix containing the aggregated number of hyperedges incident to each pair of vertices, the goal is to obtain a partition of the N vertices into disjoint communities. In this work, we investigate a semidefinite programming (SDP) approach and obtain information–theoretic conditions on the model parameters that guarantee exact recovery both in the assortative and the disassortative cases.

KW - clustering

KW - community detection

KW - hypergraph SBM

KW - multilayer

KW - planted partition

KW - semidefinite programming

UR - https://www.scopus.com/pages/publications/85161243343

U2 - 10.1007/978-3-031-32296-9_6

DO - 10.1007/978-3-031-32296-9_6

M3 - Conference article in proceedings

AN - SCOPUS:85161243343

SN - 978-3-031-32295-2

T3 - Lecture Notes in Computer Science

SP - 83

EP - 98

BT - Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings

A2 - Dewar, Megan

A2 - Théberge, François

A2 - Prałat, Paweł

A2 - Szufel, Przemysław

A2 - Wrzosek, Małgorzata

PB - Springer

T2 - Workshop on Algorithms and Models for the Web Graph

Y2 - 23 May 2023 through 26 May 2023

ER -

Alaluusua K, Avrachenkov K, Kumar BRV, Leskelä L. Multilayer Hypergraph Clustering Using the Aggregate Similarity Matrix. In Dewar M, Théberge F, Prałat P, Szufel P, Wrzosek M, editors, Algorithms and Models for the Web Graph - 18th International Workshop, WAW 2023, Proceedings. Springer. 2023. p. 83-98. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-32296-9_6