Regularized spectral methods for clustering signed networks

Cucuringu, Mihai; Singh, Apoorv Vikram; Sulem, Deborah; Tyagi, Hemant

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.48550/arXiv.2011.01737

Titre :

Regularized spectral methods for clustering signed networks

Auteur(s) :

Cucuringu, Mihai [Auteur]
Department of Statistics [Oxford]
Singh, Apoorv Vikram [Auteur]
New York University [New York] [NYU]
Sulem, Deborah [Auteur]
Department of Statistics [Oxford]
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]

Titre de la revue :

Journal of Machine Learning Research

Pagination :

1-79

Éditeur :

Microtome Publishing

Date de publication :

2021-11

ISSN :

1532-4435

Discipline(s) HAL :

Mathématiques [math]/Statistiques [math.ST]

Résumé en anglais : [en]

We study the problem of k-way clustering in signed graphs. Considerable attention in recent years has been devoted to analyzing and modeling signed graphs, where the affinity measure betweennodes takes either positive ...
Lire la suite >We study the problem of k-way clustering in signed graphs. Considerable attention in recent years has been devoted to analyzing and modeling signed graphs, where the affinity measure betweennodes takes either positive or negative values. Recently, [CDGT19] proposed a spectral method,namely SPONGE (Signed Positive over Negative Generalized Eigenproblem), which casts the clustering task as a generalized eigenvalue problem optimizing a suitably defined objective function.This approach is motivated by social balance theory, where the clustering task aims to decomposea given network into disjoint groups, such that individuals within the same group are connected byas many positive edges as possible, while individuals from different groups are mainly connected bynegative edges. Through extensive numerical simulations, SPONGE was shown to achieve state-of-the-art empirical performance. On the theoretical front, [CDGT19] analyzed SPONGE, as well asthe popular Signed Laplacian based spectral method under the setting of a Signed Stochastic BlockModel, for k=2 equal-sized clusters, in the regime where the graph is moderately dense. In this work, we build on the results in [CDGT19] on two fronts for the normalized versions of SPONGE and the Signed Laplacian. Firstly, for both algorithms, we extend the theoretical analysisin [CDGT19] to the general setting of k>2 unequal-sized clusters in the moderately dense regime. Secondly, we introduce regularized versions of both methods to handle sparse graphs – a regime where standard spectral methods are known to underperform – and provide theoretical guaranteesunder the same setting of a Signed Stochastic Block Model. To the best of our knowledge, regularized spectral methods have so far not been considered in the setting of clustering signed graphs. Wecomplement our theoretical results with an extensive set of numerical experiments on synthetic data.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Fichiers

document
Accès libre
Accéder au document

reg_spec_clust_signed_graphs.pdf
Accès libre
Accéder au document

Regularized spectral methods for clustering ... BibTeX CSV Excel RIS

Fichiers

Regularized spectral methods for clustering ...

BibTeX

CSV

Excel

RIS