Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization

Alexander Jung

doi:10.1109/IEEECONF51394.2020.9443311

Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization

^*Corresponding author for this work

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

2 Citations (Scopus)

Abstract

A main task in data analysis is to organize data points into coherent groups or clusters. The stochastic block model is a probabilistic model for the cluster structure. This model prescribes different probabilities for the presence of edges within a cluster and between different clusters. We assume that the cluster assignments are known for at least one data point in each cluster. In such a partially labeled stochastic block model, clustering amounts to estimating the cluster assignments of the remaining data points. We study total variation minimization as a method for this clustering task. We implement the resulting clustering algorithm as a highly scalable message passing protocol. We also provide a condition on the model parameters such that total variation minimization allows for accurate clustering.

Original language	English
Title of host publication	Conference Record of the 54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020
Editors	Michael B. Matthews
Publisher	IEEE
Pages	731-735
Number of pages	5
ISBN (Electronic)	9780738131269
DOIs	https://doi.org/10.1109/IEEECONF51394.2020.9443311
Publication status	Published - 1 Nov 2020
MoE publication type	A4 Conference publication
Event	Asilomar Conference on Signals, Systems & Computers - Pacific Grove, United States Duration: 1 Nov 2020 → 5 Nov 2020 Conference number: 54

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
Publisher	IEEE Computer Society
Volume	2020-November
ISSN (Print)	1058-6393

Conference

Conference	Asilomar Conference on Signals, Systems & Computers
Abbreviated title	ACSSC
Country/Territory	United States
City	Pacific Grove
Period	01/11/2020 → 05/11/2020

Access to Document

10.1109/IEEECONF51394.2020.9443311

https://arxiv.org/abs/1911.00958

Cite this

Jung, A. (2020). Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization. In M. B. Matthews (Ed.), Conference Record of the 54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020 (pp. 731-735). Article 9443311 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2020-November). IEEE. https://doi.org/10.1109/IEEECONF51394.2020.9443311

@inproceedings{b80699cffe064dba8cf804632cda5e2b,

title = "Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization",

abstract = "A main task in data analysis is to organize data points into coherent groups or clusters. The stochastic block model is a probabilistic model for the cluster structure. This model prescribes different probabilities for the presence of edges within a cluster and between different clusters. We assume that the cluster assignments are known for at least one data point in each cluster. In such a partially labeled stochastic block model, clustering amounts to estimating the cluster assignments of the remaining data points. We study total variation minimization as a method for this clustering task. We implement the resulting clustering algorithm as a highly scalable message passing protocol. We also provide a condition on the model parameters such that total variation minimization allows for accurate clustering.",

author = "Alexander Jung",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; Asilomar Conference on Signals, Systems \& Computers, ACSSC ; Conference date: 01-11-2020 Through 05-11-2020",

year = "2020",

month = nov,

day = "1",

doi = "10.1109/IEEECONF51394.2020.9443311",

language = "English",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE",

pages = "731--735",

editor = "Matthews, \{Michael B.\}",

booktitle = "Conference Record of the 54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020",

address = "United States",

}

Jung, A 2020, Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization. in MB Matthews (ed.), Conference Record of the 54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020., 9443311, Conference Record - Asilomar Conference on Signals, Systems and Computers, vol. 2020-November, IEEE, pp. 731-735, Asilomar Conference on Signals, Systems & Computers, Pacific Grove, California, United States, 01/11/2020. https://doi.org/10.1109/IEEECONF51394.2020.9443311

Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization. / Jung, Alexander.
Conference Record of the 54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020. ed. / Michael B. Matthews. IEEE, 2020. p. 731-735 9443311 (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2020-November).

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

TY - GEN

T1 - Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization

AU - Jung, Alexander

N1 - Conference code: 54

PY - 2020/11/1

Y1 - 2020/11/1

N2 - A main task in data analysis is to organize data points into coherent groups or clusters. The stochastic block model is a probabilistic model for the cluster structure. This model prescribes different probabilities for the presence of edges within a cluster and between different clusters. We assume that the cluster assignments are known for at least one data point in each cluster. In such a partially labeled stochastic block model, clustering amounts to estimating the cluster assignments of the remaining data points. We study total variation minimization as a method for this clustering task. We implement the resulting clustering algorithm as a highly scalable message passing protocol. We also provide a condition on the model parameters such that total variation minimization allows for accurate clustering.

AB - A main task in data analysis is to organize data points into coherent groups or clusters. The stochastic block model is a probabilistic model for the cluster structure. This model prescribes different probabilities for the presence of edges within a cluster and between different clusters. We assume that the cluster assignments are known for at least one data point in each cluster. In such a partially labeled stochastic block model, clustering amounts to estimating the cluster assignments of the remaining data points. We study total variation minimization as a method for this clustering task. We implement the resulting clustering algorithm as a highly scalable message passing protocol. We also provide a condition on the model parameters such that total variation minimization allows for accurate clustering.

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

U2 - 10.1109/IEEECONF51394.2020.9443311

DO - 10.1109/IEEECONF51394.2020.9443311

M3 - Conference article in proceedings

AN - SCOPUS:85099890381

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 731

EP - 735

BT - Conference Record of the 54th Asilomar Conference on Signals, Systems and Computers, ACSSC 2020

A2 - Matthews, Michael B.

PB - IEEE

T2 - Asilomar Conference on Signals, Systems & Computers

Y2 - 1 November 2020 through 5 November 2020

ER -

Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this