Learning communities in the presence of errors

Research output: Contribution to journalConference article

5 Citations (Scopus)

Abstract

We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige-Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) posed an open question about whether an almost exact recovery is possible when the adversary is allowed to add o(n) edges. Our work answers this question affirmatively even in the case of k > 2 communities. We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is εm close to SBM in the Kullback-Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.

Original languageEnglish (US)
Pages (from-to)1258-1291
Number of pages34
JournalJournal of Machine Learning Research
Volume49
Issue numberJune
StatePublished - Jun 6 2016
Event29th Conference on Learning Theory, COLT 2016 - New York, United States
Duration: Jun 23 2016Jun 26 2016

Fingerprint

Recovery
Modeling Error
Model
Community Detection
Kullback-Leibler Divergence
Graph Partitioning
Community
Learning
Social sciences
Robust Algorithm
Social Sciences
Graph in graph theory
Outlier
Learning systems
Monotone
Machine Learning
Partition
Statistics
Lower bound
Partial

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Cite this

@article{e2c2ed2cc9c541e2a46d408b93ce4486,
title = "Learning communities in the presence of errors",
abstract = "We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige-Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) posed an open question about whether an almost exact recovery is possible when the adversary is allowed to add o(n) edges. Our work answers this question affirmatively even in the case of k > 2 communities. We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is εm close to SBM in the Kullback-Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.",
author = "Konstantin Makarychev and Yury Makarychev and Aravindan Vijayaraghavan",
year = "2016",
month = "6",
day = "6",
language = "English (US)",
volume = "49",
pages = "1258--1291",
journal = "Journal of Machine Learning Research",
issn = "1532-4435",
publisher = "Microtome Publishing",
number = "June",

}

Learning communities in the presence of errors. / Makarychev, Konstantin; Makarychev, Yury; Vijayaraghavan, Aravindan.

In: Journal of Machine Learning Research, Vol. 49, No. June, 06.06.2016, p. 1258-1291.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Learning communities in the presence of errors

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Vijayaraghavan, Aravindan

PY - 2016/6/6

Y1 - 2016/6/6

N2 - We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige-Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) posed an open question about whether an almost exact recovery is possible when the adversary is allowed to add o(n) edges. Our work answers this question affirmatively even in the case of k > 2 communities. We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is εm close to SBM in the Kullback-Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.

AB - We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige-Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) posed an open question about whether an almost exact recovery is possible when the adversary is allowed to add o(n) edges. Our work answers this question affirmatively even in the case of k > 2 communities. We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is εm close to SBM in the Kullback-Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.

UR - http://www.scopus.com/inward/record.url?scp=85072253290&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85072253290&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85072253290

VL - 49

SP - 1258

EP - 1291

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

IS - June

ER -