Consider a database of @math objects, e.g., a set of videos, where each object has a binary attribute, e.g., a video's suitability for children. The attributes of the objects are to be determined under a crowdsourcing model: a worker is queried about the labels of a chosen subset of objects and either responds with a correct binary answer or declines to respond. Here we propose a parity response model: the worker is asked to check whether the number of objects having a given attribute in the chosen subset is even or odd. For example, if the subset includes two objects, the worker checks whether the two belong to the same class or not. We propose a method for designing the sequence of subsets of objects to be queried so that the attributes of the objects can be identified with high probability using few ( @math ) answers. The method is based on an analogy to the design of Fountain codes for erasure channels. We define the query difficulty @math as the average size of the query subsets and we define the sample complexity @math as the minimum number of collected answers required to attain a given recovery accuracy. We obtain fundamental tradeoffs between recovery accuracy, query difficulty, and sample complexity. In particular, the necessary and sufficient sample complexity required for recovering all @math attributes with high probability is @math and the sample complexity for recovering a fixed proportion @math of the attributes for @math is @math , where @math .
The main contribution in this paper is to characterize the fundamental tradeoffs between recovery accuracy, query difficulty, and sample complexity for this parity crowdsourcing model under the exact and almost exact recovery conditions. These recovery conditions have also been considered for community detection as reviewed in @cite_13 . However, different from almost exact recovery for community detection, where the recovery is said to be successful if any @math fraction of attributes can be recovered with high probability, we consider the exact missing fraction @math and analyze the necessary and sufficient sample complexity, obtaining an explicit expression as a function of @math . Thus, our results show how the missing fraction @math affects the required sample complexity @math in guaranteeing the recovery of the @math attributes.
@cite_13
2602671714
The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences. This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds. The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.