Search Results

Documents authored by Mossel, Elchanan

Document
DOI: 10.4230/LIPIcs.ITCS.2024.30
Influence Maximization in Ising Models

Authors: Zongchen Chen and Elchanan Mossel

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Given a complex high-dimensional distribution over {± 1}ⁿ, what is the best way to increase the expected number of +1’s by controlling the values of only a small number of variables? Such a problem is known as influence maximization and has been widely studied in social networks, biology, and computer science. In this paper, we consider influence maximization on the Ising model which is a prototypical example of undirected graphical models and has wide applications in many real-world problems. We establish a sharp computational phase transition for influence maximization on sparse Ising models under a bounded budget: In the high-temperature regime, we give a linear-time algorithm for finding a small subset of variables and their values which achieve nearly optimal influence; In the low-temperature regime, we show that the influence maximization problem cannot be solved in polynomial time under commonly-believed complexity assumption. The critical temperature coincides with the tree uniqueness/non-uniqueness threshold for Ising models which is also a critical point for other computational problems including approximate sampling and counting.
Cite as

Zongchen Chen and Elchanan Mossel. Influence Maximization in Ising Models. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2024.30,
  author =	{Chen, Zongchen and Mossel, Elchanan},
  title =	{{Influence Maximization in Ising Models}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.30},
  URN =		{urn:nbn:de:0030-drops-195588},
  doi =		{10.4230/LIPIcs.ITCS.2024.30},
  annote =	{Keywords: Influence maximization, Ising model, phase transition, correlation decay}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.15
Is This Correct? Let’s Check!

Authors: Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, and Madhu Sudan

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Societal accumulation of knowledge is a complex process. The correctness of new units of knowledge depends not only on the correctness of new reasoning, but also on the correctness of old units that the new one builds on. The errors in such accumulation processes are often remedied by error correction and detection heuristics. Motivating examples include the scientific process based on scientific publications, and software development based on libraries of code. Natural processes that aim to keep errors under control, such as peer review in scientific publications, and testing and debugging in software development, would typically check existing pieces of knowledge - both for the reasoning that generated them and the previous facts they rely on. In this work, we present a simple process that models such accumulation of knowledge and study the persistence (or lack thereof) of errors. We consider a simple probabilistic model for the generation of new units of knowledge based on the preferential attachment growth model, which additionally allows for errors. Furthermore, the process includes checks aimed at catching these errors. We investigate when effects of errors persist forever in the system (with positive probability) and when they get rooted out completely by the checking process. The two basic parameters associated with the checking process are the probability of conducting a check and the depth of the check. We show that errors are rooted out if checks are sufficiently frequent and sufficiently deep. In contrast, shallow or infrequent checks are insufficient to root out errors.
Cite as

Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, and Madhu Sudan. Is This Correct? Let’s Check!. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 15:1-15:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2023.15,
  author =	{Ben-Eliezer, Omri and Mikulincer, Dan and Mossel, Elchanan and Sudan, Madhu},
  title =	{{Is This Correct? Let’s Check!}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{15:1--15:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.15},
  URN =		{urn:nbn:de:0030-drops-175180},
  doi =		{10.4230/LIPIcs.ITCS.2023.15},
  annote =	{Keywords: Error Propagation, Preferential Attachment}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.45
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't

Authors: Yan Jin, Elchanan Mossel, and Govind Ramnarayan

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We consider a variation of the problem of corruption detection on networks posed by Alon, Mossel, and Pemantle '15. In this model, each vertex of a graph can be either truthful or corrupt. Each vertex reports about the types (truthful or corrupt) of all its neighbors to a central agency, where truthful nodes report the true types they see and corrupt nodes report adversarially. The central agency aggregates these reports and attempts to find a single truthful node. Inspired by real auditing networks, we pose our problem for arbitrary graphs and consider corruption through a computational lens. We identify a key combinatorial parameter of the graph m(G), which is the minimal number of corrupted agents needed to prevent the central agency from identifying a single corrupt node. We give an efficient (in fact, linear time) algorithm for the central agency to identify a truthful node that is successful whenever the number of corrupt nodes is less than m(G)/2. On the other hand, we prove that for any constant alpha > 1, it is NP-hard to find a subset of nodes S in G such that corrupting S prevents the central agency from finding one truthful node and |S| <= alpha m(G), assuming the Small Set Expansion Hypothesis (Raghavendra and Steurer, STOC '10). We conclude that being corrupt requires being clever, while detecting corruption does not. Our main technical insight is a relation between the minimum number of corrupt nodes required to hide all truthful nodes and a certain notion of vertex separability for the underlying graph. Additionally, this insight lets us design an efficient algorithm for a corrupt party to decide which graphs require the fewest corrupted nodes, up to a multiplicative factor of O(log n).
Cite as

Yan Jin, Elchanan Mossel, and Govind Ramnarayan. Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.ITCS.2019.45,
  author =	{Jin, Yan and Mossel, Elchanan and Ramnarayan, Govind},
  title =	{{Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.45},
  URN =		{urn:nbn:de:0030-drops-101388},
  doi =		{10.4230/LIPIcs.ITCS.2019.45},
  annote =	{Keywords: Corruption detection, PMC Model, Small Set Expansion, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.8
Linear Sketching over F_2

Authors: Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We initiate a systematic study of linear sketching over F_2. For a given Boolean function treated as f : F_2^n -> F_2 a randomized F_2-sketch is a distribution M over d x n matrices with elements over F_2 such that Mx suffices for computing f(x) with high probability. Such sketches for d << n can be used to design small-space distributed and streaming algorithms. Motivated by these applications we study a connection between F_2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F_2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F_2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F_2-sketching is optimal (up to constant factors) for uniformly distributed inputs. Furthermore, we show that (non-uniform) streaming algorithms that have to process random updates over F_2 can be constructed as F_2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require the stream length to be triply exponential in n and holds for streams of length O(n) constructed through uniformly random updates.
Cite as

Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev. Linear Sketching over F_2. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 8:1-8:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kannan_et_al:LIPIcs.CCC.2018.8,
  author =	{Kannan, Sampath and Mossel, Elchanan and Sanyal, Swagato and Yaroslavtsev, Grigory},
  title =	{{Linear Sketching over F\underline2}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{8:1--8:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.8},
  URN =		{urn:nbn:de:0030-drops-88819},
  doi =		{10.4230/LIPIcs.CCC.2018.8},
  annote =	{Keywords: Linear sketch, Streaming algorithms, XOR-functions, Communication complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.10
Noise Stability Is Computable and Approximately Low-Dimensional

Authors: Anindya De, Elchanan Mossel, and Joe Neeman

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
Questions of noise stability play an important role in hardness of approximation in computer science as well as in the theory of voting. In many applications, the goal is to find an optimizer of noise stability among all possible partitions of R^n for n >= 1 to k parts with given Gaussian measures mu_1, ..., mu_k. We call a partition epsilon-optimal, if its noise stability is optimal up to an additive epsilon. In this paper, we give an explicit, computable function n(epsilon) such that an epsilon-optimal partition exists in R^{n(epsilon)}. This result has implications for the computability of certain problems in non-interactive simulation, which are addressed in a subsequent work.
Cite as

Anindya De, Elchanan Mossel, and Joe Neeman. Noise Stability Is Computable and Approximately Low-Dimensional. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 10:1-10:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.CCC.2017.10,
  author =	{De, Anindya and Mossel, Elchanan and Neeman, Joe},
  title =	{{Noise Stability Is Computable and Approximately Low-Dimensional}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{10:1--10:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.10},
  URN =		{urn:nbn:de:0030-drops-75390},
  doi =		{10.4230/LIPIcs.CCC.2017.10},
  annote =	{Keywords: Gaussian noise stability; Plurality is stablest; Ornstein Uhlenbeck operator}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.34
Lower Bounds on Same-Set Inner Product in Correlated Spaces

Authors: Jan Hazla, Thomas Holenstein, and Elchanan Mossel

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
Let P be a probability distribution over a finite alphabet Omega^L with all L marginals equal. Let X^(1), ..., X^(L), where X^(j) = (X_1^(j), ..., X_n^(j)) be random vectors such that for every coordinate i in [n] the tuples (X_i^(1), ..., X_i^(L)) are i.i.d. according to P. The question we address is: does there exist a function c_P independent of n such that for every f: Omega^n -> [0, 1] with E[f(X^(1))] = m > 0 we have E[f(X^(1)) * ... * f(X^(n))] > c_P(m) > 0? We settle the question for L=2 and when L>2 and P has bounded correlation smaller than 1.
Cite as

Jan Hazla, Thomas Holenstein, and Elchanan Mossel. Lower Bounds on Same-Set Inner Product in Correlated Spaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hazla_et_al:LIPIcs.APPROX-RANDOM.2016.34,
  author =	{Hazla, Jan and Holenstein, Thomas and Mossel, Elchanan},
  title =	{{Lower Bounds on Same-Set Inner Product in Correlated Spaces}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{34:1--34:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.34},
  URN =		{urn:nbn:de:0030-drops-66571},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.34},
  annote =	{Keywords: same set hitting, product spaces, correlation, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.15
Invariance Principle on the Slice

Authors: Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We prove a non-linear invariance principle for the slice. As applications, we prove versions of Majority is Stablest, Bourgain's tail theorem, and the Kindler-Safra theorem for the slice. From the latter we deduce a stability version of the t-intersecting Erdos-Ko-Rado theorem.
Cite as

Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. Invariance Principle on the Slice. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 15:1-15:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.CCC.2016.15,
  author =	{Filmus, Yuval and Kindler, Guy and Mossel, Elchanan and Wimmer, Karl},
  title =	{{Invariance Principle on the Slice}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{15:1--15:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.15},
  URN =		{urn:nbn:de:0030-drops-58236},
  doi =		{10.4230/LIPIcs.CCC.2016.15},
  annote =	{Keywords: analysis of boolean functions, invariance principle, Johnson association scheme, the slice}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.16
Harmonicity and Invariance on Slices of the Boolean Cube

Authors: Yuval Filmus and Elchanan Mossel

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree functions. Here we provide an alternative proof for general low-degree functions, with no constraints on the influences. We show that any real-valued function on the slice, whose degree when written as a harmonic multi-linear polynomial is o(sqrt(n)), has approximately the same distribution under the slice and cube measure. Our proof is based on a novel decomposition of random increasing paths in the cube in terms of martingales and reverse martingales. While such decompositions have been used in the past for stationary reversible Markov chains, ours decomposition is applied in a non-reversible non-stationary setup. We also provide simple proofs for some known and some new properties of harmonic functions which are crucial for the proof. Finally, we provide independent simple proofs for the known facts that 1) one cannot distinguish between the slice and the cube based on functions of little of of n coordinates and 2) Boolean symmetric functions on the cube cannot be approximated under the uniform measure by functions whose sum of influences is o(sqrt(n)).
Cite as

Yuval Filmus and Elchanan Mossel. Harmonicity and Invariance on Slices of the Boolean Cube. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{filmus_et_al:LIPIcs.CCC.2016.16,
  author =	{Filmus, Yuval and Mossel, Elchanan},
  title =	{{Harmonicity and Invariance on Slices of the Boolean Cube}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.16},
  URN =		{urn:nbn:de:0030-drops-58240},
  doi =		{10.4230/LIPIcs.CCC.2016.16},
  annote =	{Keywords: analysis of boolean functions, invariance principle, Johnson association scheme, the slice}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.931
Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent

Authors: Elchanan Mossel and Sebastien Roch

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We consider the reconstruction of a phylogeny from multiple genes under the multispecies coalescent. We establish a connection with the sparse signal detection problem, where one seeks to distinguish between a distribution and a mixture of the distribution and a sparse signal. Using this connection, we derive an information-theoretic trade-off between the number of genes needed for an accurate reconstruction and the sequence length of the genes.
Cite as

Elchanan Mossel and Sebastien Roch. Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 931-942, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{mossel_et_al:LIPIcs.APPROX-RANDOM.2015.931,
  author =	{Mossel, Elchanan and Roch, Sebastien},
  title =	{{Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{931--942},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.931},
  URN =		{urn:nbn:de:0030-drops-53455},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.931},
  annote =	{Keywords: phylogenetic reconstruction, multispecies coalescent, sequence length requirement.}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.779
Global and Local Information in Clustering Labeled Block Models

Authors: Varun Kanade, Elchanan Mossel, and Tselil Schramm

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
The stochastic block model is a classical cluster-exhibiting random graph model that has been widely studied in statistics, physics and computer science. In its simplest form, the model is a random graph with two equal-sized clusters, with intra-cluster edge probability p, and inter-cluster edge probability q. We focus on the sparse case, i.e. p, q = O(1/n), which is practically more relevant and also mathematically more challenging. A conjecture of Decelle, Krzakala, Moore and Zdeborova, based on ideas from statistical physics, predicted a specific threshold for clustering. The negative direction of the conjecture was proved by Mossel, Neeman and Sly (2012), and more recently the positive direction was proven independently by Massoulie and Mossel, Neeman, and Sly. In many real network clustering problems, nodes contain information as well. We study the interplay between node and network information in clustering by studying a labeled block model, where in addition to the edge information, the true cluster labels of a small fraction of the nodes are revealed. In the case of two clusters, we show that below the threshold, a small amount of node information does not affect recovery. On the other hand, we show that for any small amount of information efficient local clustering is achievable as long as the number of clusters is sufficiently large (as a function of the amount of revealed information).
Cite as

Varun Kanade, Elchanan Mossel, and Tselil Schramm. Global and Local Information in Clustering Labeled Block Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 779-792, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kanade_et_al:LIPIcs.APPROX-RANDOM.2014.779,
  author =	{Kanade, Varun and Mossel, Elchanan and Schramm, Tselil},
  title =	{{Global and Local Information in Clustering Labeled Block Models}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{779--792},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.779},
  URN =		{urn:nbn:de:0030-drops-47384},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.779},
  annote =	{Keywords: stochastic block models, information flow on trees}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact