Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Large Deviations of Semi-supervised Learning in the Stochastic Block
  Model   In community detection on graphs, the semi-supervised learning problem
entails inferring the ground-truth membership of each node in a graph, given
the connectivity structure and a limited number of revealed node labels.
Different subsets of revealed labels can in principle lead to higher or lower
information gains and induce different reconstruction accuracies. In the
framework of the dense stochastic block model, we employ statistical physics
methods to derive a large deviation analysis for this problem, in the
high-dimensional limit. This analysis allows the characterization of the
fluctuations around the typical behaviour, capturing the effect of correlated
label choices and yielding an estimate of their informativeness and their
rareness among subsets of the same size. We find theoretical evidence of a
non-monotonic relationship between reconstruction accuracy and the free energy
associated to the posterior measure of the inference problem. We further
discuss possible implications for active learning applications in community
detection.

30
The categories of this paper are: q-alg
13
The categories of this paper are: quant-ph
28
The categories of this paper are: alg-geom
5
The categories of this paper are: gr-qc
26
The categories of this paper are: bayes-an
14
The categories of this paper are: math-ph
21
The categories of this paper are: adap-org
27
The categories of this paper are: comp-gas
3
The categories of this paper are: physics
36
The categories of this paper are: cmp-lg
8
The categories of this paper are: hep-ex
19
The categories of this paper are: eess
18
The categories of this paper are: econ
1
The categories of this paper are: cs
10
The categories of this paper are: q-bio
33
The categories of this paper are: plasm-ph