Almost exact recovery in noisy semi-supervised learning

Abstract

Graph-based semi-supervised learning methods combine the graph structure and labeled data to classify unlabeled data. In this work, we study the effect of a noisy oracle on classification. In particular, we derive the maximum a posteriori (MAP) estimator for clustering a degree corrected stochastic block model when a noisy oracle reveals a fraction of the labels. We then propose an algorithm derived from a continuous relaxation of the MAP, and we establish its consistency. Numerical experiments show that our approach achieves promising performance on synthetic and real data sets, even in the case of very noisy labeled data.

1. Introduction

Semi-supervised learning (SSL) aims at achieving superior learning performance by combining unlabeled and labeled data. Since typically the amount of unlabeled data is large compared to the amount of labeled data, SSL methods are relevant when the performance of unsupervised learning is low, or when the cost of getting a large amount of labeled data for supervised learning is too high. Unfortunately, many standard SSL methods have been shown to not efficiently use the unlabeled data, leading to unsatisfactory or unstable performance [11, Chap. 4], [9, 12]. Moreover, noise in the labeled data can further degrade the performance. In practice, the noise can come from a tired or non-diligent expert carrying out the labeling task or even from adversarial data corruption.

In this paper, we investigate the problem of graph clustering, where one aims to group the nodes of a graph into different classes. Our working model is the two-class degree corrected stochastic block model (DC-SBM), with side information on some node’s community assignment given by a noisy oracle. The DC-SBM was introduced in [18] to account for degree heterogeneity and block structure. Let n be the number of nodes. Each node $i \in [n]$ is given a community label $Z_i \in \{-1,1\}$ chosen uniformly at random and a parameter $\theta_i \gt 0$. Given $Z = (Z_1, \dots, Z_n)$ and $\theta = \left( \theta_1, \dots, \theta_n \right)$, an undirected edge is added between nodes i and j with probability $\min( 1, \theta_i \theta_j p_{\rm in})$, if $Z_i = Z_j$, and with probability $\min(1, \theta_i\theta_j p_{\rm out})$, otherwise. This model reduces to the standard stochastic block model (SBM) [1] if $\theta_i = 1$ for every node i. The unsupervised clustering problem consists of inferring the latent community structure Z given one observation of a DC-SBM graph. We make the problem semi-supervised by introducing a noisy oracle. For every node, this oracle reveals the correct community label with probability η ₁, a wrong community label with probability η ₀, and reveals nothing with probability $1-\eta_1-\eta_0$.

We first derive the maximum a posteriori (MAP) estimator for SSL-clustering in a DC-SBM graph given the a priori information induced by a noisy oracle and graph structure. We note that, despite its simplicity, this result did not appear previously in the literature, neither for a perfect oracle nor for SBM. In particular, we show that the MAP is the solution to a minimization problem that involves a trade-off between three factors: a cut-based term (as in the unsupervised scenario), a regularization term (penalizing solutions with unbalanced clusters), and a loss term (penalizing predictions that differ from the oracle information).

As solving the MAP estimator is NP-hard, we propose a continuous relaxation and derive an SSL version of a spectral method based on the adjacency matrix. We establish a bound on the ratio of misclassified nodes for this continuous relaxation, and we show that this ratio goes to zero under the hypothesis that the average degree diverges and an almost perfect oracle (see Corollary 3.2 for a rigorous statement). As a result, the proposed SSL method guarantees almost exact recovery (recovering all but o(n) labels when n goes to infinity) even when a part of the side information is incorrect. We note that even though we work with the case of two clusters, most of our results are extendable to the setting of more than two clusters at the expense of more cumbersome notations.

One can make several parallels between our continuous relaxation and state-of-the-art techniques. Indeed, SSL-clustering often relies on minimization frameworks (see [5, 11] for an overview). The idea of minimizing a well-chosen energy function was proposed in [30], under the constraint of keeping the labeled nodes’ predictions equal to the oracle labels. As we show in the numerical section, this hard constraint is unsuitable if the oracle reveals false information. Consequently, Belkin et al. [8] introduced an additional loss term in the energy function to allow the prediction to differ from the oracle information. We recover this loss term with an additional theoretical justification because it comes from a relaxation of the MAP.

Moreover, the regularization term is necessary to prevent the solution from being flat and making classification rely on second-order fluctuations. This phenomenon was previously observed by [23] in the limit of an infinite amount of unlabeled data, as well as by [21] in the large dimension limit. The regularization term here consists of subtracting a constant term from all the entries of the adjacency matrix. It resembles previous regularization techniques, like the centering of the adjacency matrix proposed in [22]. However, contrary to [22], we study a noisy framework without assuming a large-dimension asymptotic regime. Moreover, we solve exactly the relaxed minimization problem instead of giving a heuristic with an extra parameter.

It was shown in [25] that even with a perfect oracle revealing a constant fraction of the labels, the phase transition phenomena for exact recovery in SBM (recovering all the correct labels with high probability) remains unchanged. Thus, for the exact recovery problem, one could discard all the side information and simply use unsupervised algorithms when the number of data points goes to infinity. Of course, wasting potentially valuable information is not entirely satisfactory. Thus, in the present work, we consider the case of almost exact recovery and an oracle with noisy information. In [7, 17] criteria different from the exact recovery have also been considered in the framework of SSL.

The paper is structured as follows. We introduce the model and main notations in Section 2, along with the derivation of the MAP estimator (Section 2.2). A continuous relaxation of the MAP is presented in Section 3 as well as the guarantee of its convergence to the true community structure (Subsection 3.2). We postpone some proofs to the Appendix and leave in the main text only those we consider important to the material exposition. We conclude the paper with numerical results (Section 4), emphasizing the effect of the noise on the clustering accuracy. In particular, we outperform state-of-the-art graph-based SSL methods in a difficult regime (few label points or large noise).

Lastly, the present paper is a follow-up work on [3]. However, there are very important developments. In [3] we have only established almost exact recovery on SBM for Label Spreading [29] heuristic algorithm with a linear number of labeled nodes (see [3, Assumption 3]). In the present work, we extend the analysis to DC-SBM, investigate the effect of noisy labeled data, and allow a potentially sublinear number of labeled nodes. We also add experiments with real and synthetic data that illustrate our theoretical results.

2. MAP estimator in a noisy semi-supervised setting

2.1. Problem formulation and notations

A homogeneous DC-SBM is parametrized by the number of nodes n, two class-affinity parameters $p_{\rm in}, p_{\rm out}$, and a pair $(\theta, Z)$ where $\theta \in \mathbf{R}^n$ is a vector of intrinsic connection intensities and $Z \in \{-1,1\}^n$ is the community labeling vector. Given $(p_{\rm in}, p_{\rm out}, \theta, Z)$, the graph adjacency matrix $A = (a_{ij})$ is generated as

(2.1)\begin{align} A_{ij} = A_{ji} \sim \left\{ \begin{array}{ll} \operatorname{Ber} \left( \theta_i \theta_j p_{\rm in} \right), & \qquad \mathrm{if}\quad Z_i = Z_j, \\ \operatorname{Ber} \left( \theta_i \theta_j p_{\rm out} \right), & \qquad \mathrm{otherwise,} \\ \end{array} \right. \end{align}

for $i \not= j$, and $A_{ii} = 0$. We assume throughout the paper that $Z_i \sim \operatorname{Uni} \left( \{-1,1\} \right) $, and that the entries of θ are independent random variables satisfying $\theta_i \in [ \theta_{\min}, \theta_{\max} ]$ with $\mathbb{E} \theta_i = 1$, $\theta_{\min} \gt 0$, and $\theta_{\max}^2 \max(p_{\rm in}, p_{\rm out}) \leq 1$. In particular, when all the θ_i’s are equal to one, the model reduces to the SBM:

(2.2)\begin{align} A_{ij} = A_{ji} \sim \left\{ \begin{array}{ll} \operatorname{Ber} \left( p_{\rm in} \right), & \qquad \mathrm{if}\quad Z_i = Z_j, \\ \operatorname{Ber} \left( p_{\rm out} \right), & \qquad \mathrm{otherwise.} \\ \end{array} \right. \end{align}

In addition to the observation of the graph adjacency matrix A, an oracle gives us extra information about the cluster assignment of some nodes. This can be represented as a vector $s \in \{0,-1,1\}^n$, whose entries s_i are independent and distributed as follows:

(2.3)\begin{align} s_{i} \ = \ \left\{ \begin{array}{ll} Z_i, & \qquad \mathrm{with \ probability} \quad \eta_1, \\ -Z_i, & \qquad \mathrm{with \ probability} \quad \eta_0, \\ 0, & \qquad \mathrm{otherwise}. \end{array} \right. \end{align}

In other words, the oracle (2.3) reveals the correct cluster assignment of node i with probability η ₁ and gives a false cluster assignment with probability η ₀. It reveals nothing with probability $1-\eta_1-\eta_0$. The quantity $\mathbb{P}\left( s_i \not = Z_i \, | \, s_i \not= 0 \right)$ is the rate of mistakes of the oracle (i.e., the probability that the oracle reveals false information given that it reveals something), and is equal to $\eta_0/(\eta_1+\eta_0)$. The oracle is informative if this quantity is less than $1/2$, which is equivalent to $\eta_1 \gt \eta_0$. In the following, we will always assume that the oracle is informative.

Assumption 2.1. The oracle is informative, that is, $\eta_1 \gt \eta_0$.

Given the observation of A and s, the goal of clustering is to recover the community labeling vector Z. For an estimator $\widehat{Z} \in \{-1,1\}^n$ of Z, the relative error is defined as the proportion of misclassified nodes

(2.4)\begin{align} L \left( \widehat{Z} , Z \right) \ = \ \frac{1}{n} \sum_{i=1}^n 1\left( \widehat{Z} _i \not= Z_i \right). \end{align}

Note that, unlike unsupervised clustering, we do not take a minimum over the permutations of the predicted labels since we should be able to learn the correct community labels from the informative oracle.

Notations Given an oracle s, we let $\ell$ be the set of labeled nodes, that is $\ell := \{i \in V : s_i \not= 0 \}$, and denote $\mathcal{P}$ the diagonal matrix with entries $\left( \mathcal{P} \right)_{ii} = 1$, if $i \in \ell$, and $\left(\mathcal{P} \right)_{ii} = 0$, otherwise.

The notation I_n stands for the identity matrix of size n × n, and 1_n (resp., 0_n) is the vector of size n × 1 of all ones (resp., of all zeros).

For any matrix $A = \left(a_{ij}\right)_{i \in [n], j \in [m]}$ and two sets $S \subset [n]$, $T \subset [m]$, we denote $A_{S,T} = \left(a_{ij}\right)_{i \in S, j \in T}$ the matrix obtained from A by keeping elements, whose row indices are in S and column indices are in T. We denote by $\|x\|$ the Euclidean norm of a vector x and by $\|A\|$ the spectral norm of a matrix $A \in \mathbf{R}^{n\times m}$. Finally, $A \odot B$ refers to the entry-wise matrix product between two matrices A and B of the same size.

2.2. MAP estimator for semi-supervised recovery in DC-SBM

Given a realization of a DC-SBM graph adjacency matrix A and the oracle information s, the MAP estimator is defined as

(2.5)\begin{align} \widehat{Z} ^{\operatorname{MAP}} & \ = \ \mathrm{arg\,max}_{z \in \{-1,1\}^n } \mathbb{P}( z \, | \, A, s). \end{align}

This estimator is known to be optimal (in the sense that if it fails then any other estimator would also fail, see, e.g., [16]) for the exact recovery of all the community labels. Theorem 2.2 provides an expression of the MAP.

Theorem 2.2 Let G be a graph drawn from DC-SBM as defined in (2.1) and s be the oracle information as defined in (2.3). Denote $ M \ = \ (F_1-F_0) \odot A + F_0, $ where $F_0 = \left(f^{(0)}_{ij} \right)$ and $F_1 = \left(f^{(1)}_{ij} \right)$ such that $f^{(a)}_{ij} = \log \frac{\mathbb{P}(A_{ij} = a \, | \, z_i = z_j )}{\mathbb{P}(A_{ij} = a \, | \, z_i \not= z_j ) } $ for $a \in \{0,1\}$. The MAP estimator defined in (2.5) is given by

(2.6)\begin{equation} \widehat{Z} ^{\operatorname{MAP}} \ = \ \mathrm{arg\,min}_{\substack {z \in \{-1,1\}^n } } \, \left( z^T M z + \log \left( \frac{\eta_1}{\eta_0} \right) \left\| \mathcal{P} z - s \right\|^2 \right). \end{equation}

For a perfect oracle $(\eta_0 = 0)$ this reduces to

(2.7)\begin{equation} \widehat{Z} ^{\operatorname{MAP}} \ = \ \mathrm{arg\,min}_{\substack{z \in \{-1,1\}^n \\ z_{\ell} = s_{\ell} } } z^T M z. \end{equation}

The proof of Theorem 2.2 is standard and postponed to Appendix A. We note that, despite being a priori standard, this result did not appear previously in the literature (neither for the standard SBM nor for the perfect oracle).

The minimization problem (2.6) consists of a trade-off between minimizing a quadratic function $z^T M z$ and a penalty term. This trade-off reads as follows: for each labeled node such that the prediction contradicts the oracle, a penalty $\log \left( \frac{\eta_1}{\eta_0} \right) \gt 0$ is added. In particular, when the oracle is uninformative, that is $\eta_1 = \eta_0$, then this term is null, and Expression (2.6) reduces to the MAP for unsupervised clustering.

The following Corollary 2.3, whose proof is in Appendix A, provides the expression of the MAP estimator for a standard SBM.

Corollary 2.3. The MAP estimator for semi-supervised clustering on SBM graph with $p_{\rm in} \gt p_{\rm out}$ and with an oracle s defined in (2.3) is given by

(2.8)\begin{align} \widehat{Z} ^{\operatorname{MAP}} \ = \ \mathrm{arg\,min}_{z \in \{-1,1\}^n } \, \left( - z^T \left(A - \tau 1_n 1_n^T \right) z + \lambda^* \left\| \mathcal{P} z - s \right\|_2^2 \right), \end{align}

where $ \tau = \dfrac{\log \Big( \dfrac{1-p_{\rm out}}{1-p_{\rm in}} \Big) }{\log \Big( \dfrac{p_{\rm in} (1-p_{\rm out})}{p_{\rm out} (1-p_{\rm in})} \Big) }$ and $\lambda^* = \dfrac{\log \Big( \dfrac{\eta_1}{\eta_0} \Big)}{\log \bigg( \dfrac{p_{\rm in} (1-p_{\rm out})}{p_{\rm out}(1-p_{\rm in})} \bigg)}. $ For the perfect oracle, this reduces to

(2.9)\begin{equation} \widehat{Z} ^{\operatorname{MAP}} \ = \ \mathrm{arg\,min}_{\substack{z \in \{-1,1\}^n \\ z_{\ell} = s_{\ell} } } \, z^T \left( -A + \tau 1_n 1_n^T \right) z. \end{equation}

3. Almost exact recovery using a continuous relaxation

As finding the MAP estimate is NP-hard[26], we perform a continuous relaxation (Section 3.1). We then give an upper bound on the number of misclassified nodes in Section 3.2.

3.1. Continuous relaxation of the MAP

For the sake of presentation simplicity, we focus on the MAP for SBM, that is, minimization problem (2.8). We perform a continuous relaxation mirroring what is commonly done for spectral methods [24], namely

(3.1)\begin{align} \widehat{X} \ = \ \mathrm{arg\,min}_{\substack{x \in \mathbf{R}^{n} \\ \sum_i \kappa_i x_i^2 = \sum_i \kappa_i } } \left( -x^T A_\tau x + \lambda ( s - \mathcal{P} x )^T ( s - \mathcal{P} x ) \right), \end{align}

where $A_{\tau} = A - \tau 1_n 1_n^T$ and $\kappa = (\kappa_1, \dots, \kappa_n)$ is a vector of positive entries. We choose to constrain x on the hyper-sphere $\|x\|^2 = n$ by letting $\kappa_i = 1$, but other choices would lead to a similar analysis. In particular, in the numerical Section 4 we will compare this choice with a degree-normalization approach (i.e., $\kappa_i = d_i$).

We further note that for the perfect oracle, the corresponding relaxation of (2.9) is

(3.2)\begin{equation} \widehat{X} = \mathrm{arg\,min}_{\substack{x \in \mathbf{R}^n \\ x_{\ell} = s_{\ell} \\ \|x\|^2 = n } } \left( - x^T A_\tau x \right). \end{equation}

Given the classification vector $\widehat{X} \in \mathbf{R}^{n}$, node i is classified into cluster $\widehat{Z} _i \in \{-1, 1\}$ such that

(3.3)\begin{equation} \widehat{Z} _i \ = \ \left\{ \begin{array}{ll} 1, & \qquad \mathrm{if}\quad \widehat{X} _i \gt 0, \\ -1, & \qquad \mathrm{otherwise}. \\ \end{array} \right. \end{equation}

Let us solve the minimization problem (3.1). By letting $\gamma \in \mathbf{R}$ be the Lagrange multiplier associated with the constraint $\|x\|^2 = n$, the Lagrangian of the optimization problem (3.1) is

\begin{equation*} -x^T A_\tau x + \lambda ( s - \mathcal{P} x )^T ( s - \mathcal{P} x ) - \gamma \left( x^T x - n \right). \end{equation*}

This leads to the constrained linear system

(3.4)\begin{align} \left\{ \begin{array}{rc} \left( - A_\tau + \lambda \mathcal{P} - \gamma I_n \right) x \ = \ & \lambda s, \\ x^T x \ = \ & n, \end{array} \right. \end{align}

whose unknowns are γ and x.

While [22] let γ to be a hyper-parameter (hence the norm constraint $x^T x = n$ is no longer verified), the exact optimal value of γ can be found explicitly following [14]. Firstly, we note that if $(\gamma_1,x_1)$ and $(\gamma_2,x_2)$ are solutions of the system (3.4), then (see Lemma D.1 for the derivations)

\begin{align*} \mathcal{C} (x_1) - \mathcal{C} (x_2) \ = \ \frac{\gamma_1 - \gamma_2 }{2} \, \left\| x_1 - x_2 \right\|^2, \end{align*}

where $\mathcal{C}(x) = - x^T A_\tau x + \lambda (s-\mathcal{P} x)^T (s-\mathcal{P} x)$ is the cost function minimized in (3.1). Hence, among the solution pairs $(\gamma, x)$ of the system (3.4), the solution of the minimization problem (3.1) is the vector x associated with the smallest γ.

Secondly, the eigenvalue decomposition of $-A_{\tau} + \lambda \mathcal{P}$ reads as

\begin{align*} -A_{\tau} + \lambda \mathcal{P} \ = \ Q \Delta Q^T, \end{align*}

where $\Delta = \mathrm{diag} ( \delta_1, \dots, \delta_n)$ with $\delta_1 \leq \dots \leq \delta_n$ and $Q^T Q = I_n$. Therefore, after the change of variables $u = Q^T x$ and $b = \lambda Q^T s$, the system (3.4) is transformed to

\begin{align*} \left\{ \begin{array}{rl} \Delta u & \ = \ \gamma u + b, \\ u^T u & \ = \ n. \end{array} \right. \end{align*}

Thus, the solution $\widehat{X} $ of the optimization problem (3.1) satisfies

(3.5)\begin{align} \left( - A_\tau + \lambda \mathcal{P} - \gamma_* I_n \right) \widehat{X} & \ = \ \lambda s, \end{align}

where $\gamma_*$ is the smallest solution of the explicit secular equation [14]

(3.6)\begin{align} \sum_{i=1}^n \left( \frac{b_i }{ \delta_i - \gamma } \right)^2 - n \ = \ 0. \end{align}

We summarize this in Algorithm 1. Note that for the sake of generality, we let λ and τ be hyper-parameters of the algorithm. If the model parameters are known, we can use the expressions of λ and τ derived in Corollary 2.3. The choice of λ and τ is further discussed in Section 4. We must use power iterations or Krylov subspace methods to apply Algorithm 1 to large data sets. The main computational bottleneck in those methods will be the matrix-vector product $A_\tau v$. The matrix A_τ is not sparse. Since A_τ is a sum of a sparse matrix and a rank-one matrix, the computation of $A_\tau v = Av - \tau (1_n^T v) 1_n$ can be done efficiently by subtracting the same scalar $\tau (1_n^T v)$ from all the entries of the result of the sparse matrix-vector multiplication.

Algorithm 1. Semi-supervised learning with regularized adjacency matrix.

3.2. Ratio of misclassified nodes

This section gives bounds on the number of unlabeled nodes misclassified by Algorithm 1. We then specialize the results for some particular cases.

Theorem 3.1 Consider a DC-SBM with a noisy oracle as defined in (2.1) and (2.3). Let $\bar{d} = \frac{n}{2}(p_{\rm in} + p_{\rm out})$ and $\bar{\alpha} = \frac{n}{2}(p_{\rm in} - p_{\rm out})$. Suppose that $\tau \gt p_{\rm out}$ and that $\eta_0 n \sqrt{\eta_1+\eta_0} \ll \lambda$, and let $\widehat{Z} $ be the output of Algorithm 1. Then, for any r > 0, there exists a constant C such that the proportion of misclassified unlabeled nodes satisfies

\begin{equation*} L \left( \widehat{Z} _u , Z_u \right) \ \le \ C \left( \frac{p_{\rm in} + p_{\rm out} }{p_{\rm in} - p_{\rm out} } \right)^2 \Bigg(\dfrac{\bar{\alpha } + \lambda }{ \lambda } \Bigg)^2 \frac{1 }{(\eta_1 + \eta_0) \left( \eta_1 - \eta_0 \right)^2 \bar{d} }, \end{equation*}

with probability at least $1 - n^{-r}$.

The value of λ in Theorem 3.1 serves as a hyper-parameter of the algorithm and may not necessarily be equal to the value $\lambda^*$ computed in Corollary 2.3. Consequently, one can opt for a λ significantly larger than $\eta_0 n \sqrt{\eta_0+\eta_1}$, even if the $\lambda^*$ from Corollary 2.3 is not much larger than $\eta_0 n \sqrt{\eta_0+\eta_1}$. Selecting $\lambda \gt \lambda^*$ indicates an excessive reliance on the information provided by the oracle, but it has a benign effect on the error bound of the unlabeled nodes given in Theorem 3.1.

The core of the proof relies on the concentration of the adjacency matrix toward its expectation. This result, as presented in [19], holds under loose assumptions: it is valid for any random graph whose edges are independent of each other. To use this result for $\bar{d} = o\big(\log n \big)$, one needs to replace the matrix A_τ by $A_\tau' = A' - \tau 1_n 1_n^T$, where Aʹ is the adjacency matrix of the graph obtained after reducing the weights on the edges incident to the high degree vertices. We refer to [19, Sect. 1.4] for more details. This extra technical step is not necessary when $\bar{d} = \Omega(\log n)$. Moreover, concentration also occurs if we replace the adjacency matrix with the normalized Laplacian in Eq. (3.5). In that case, we obtain a generalization of the Label Spreading algorithm [29], [11, Chap. 11].

In the following, the mean-field graph refers to the weighted graph formed by the expected adjacency matrix of a DC-SBM graph. Furthermore, we assume without loss of generality that the first $n/2$ nodes are in the first cluster and the last $n/2$ are in the second cluster. Therefore, $ \mathbb{E} A = Z B Z^T $ with $ B = \begin{pmatrix} p_{\rm in} & p_{\rm out} \\ p_{\rm out} & p_{\rm in} \end{pmatrix} $ and $ Z = \begin{pmatrix} 1_{n/2} & 0_{n/2} \\ 0_{n/2} & 1_{n/2} \end{pmatrix} . $ In particular, the coefficients θ_i disappear because $\mathbb{E} \theta_i = 1$. We consider the setting in which the diagonal elements of $\mathbb{E} A$ are not zeros. This accounts for modifying the definition of DC-SBM, where we can have self-loops with probability p _in. Nevertheless, we could set the diagonal elements of $\mathbb{E} A$ to zeros and our results would still hold at the expense of cumbersome expressions. Note that the matrix $\mathbb{E} A$ has two non-zero eigenvalues: $\bar{d} = n \frac{p_{\rm in} + p_{\rm out}}{2} $ and $\bar{\alpha } = n \frac{p_{\rm in} - p_{\rm out}}{2} $.

Proof of Theorem 3.1

We prove the statement in three steps. We first show that the solution $\widehat{X} $ of the constrained linear system (3.4) is concentrated around the solution $\bar{x} $ of the same system for the mean-field model. Then, we compute $\bar{x} $ and show that we can retrieve the correct cluster assignment from it. We finally conclude with the derivation of the bound.

1. (i) Similarly to [4] and [3], let us rewrite Eq. (3.5) as a perturbation of a system of linear equations corresponding to the mean-field solution. We thus have

   \begin{equation*} \big( \mathbb{E} \tilde{\mathcal{L}} + \Delta \tilde{\mathcal{L}} \big) \big( \bar{x} + \Delta x \big) = \lambda s, \end{equation*}

   where $\tilde{\mathcal{L}} = - A_\tau + \lambda \mathcal{P} - \gamma_* I_n$, $\Delta x := \widehat{X} - \bar{x} $ and $\Delta \tilde{\mathcal{L}} := \tilde{\mathcal{L}} - \mathbb{E} \tilde{\mathcal{L}}$.

We recall that a perturbation of a system of linear equations $ (A + \Delta A) (x + \Delta x) = b $ leads to the following sensitivity inequality (see, e.g., [15, Sect. 5.8]):

\begin{equation*} \dfrac{\|\Delta x\|}{\|x\|} \ \le \ \kappa(A) \dfrac{\| \Delta A \| }{\| A \| }, \end{equation*}

where $\|.\|$ is the operator norm associated with a vector norm $\|.\|$ (we use the same notations for simplicity) and $\kappa(A) := \|A^{-1}\| \cdot \|A\|$ is the condition number. In our case, the above inequality can be rewritten as follows:

(3.7)\begin{equation} \dfrac{\left\| \widehat{X} - \bar{x} \right\| }{\left\| \bar{x} \right\| } \ \le \ \left\| \left( \mathbb{E} \: \tilde{\mathcal{L}} \right)^{-1} \right\| \cdot \left\| \Delta \: \tilde{\mathcal{L}} \right\|, \end{equation}

employing the Euclidean vector norm and spectral operator norm. The spectral study of $\mathbb{E} \: \tilde{\mathcal{L}}$ (see Corollary B.3 in Appendix B.1) gives:

\begin{align*} \left\| \left( \mathbb{E} \: \tilde{\mathcal{L}}\right)^{-1} \right\| & \ = \ \dfrac{1}{\min \big \{|\lambda| : \lambda \in \mathrm{Sp} \big( \mathbb{E} \: \tilde{\mathcal{L}} \big) \big \} } = \dfrac{1}{- t_2^+ -\bar{\gamma}_* }, \end{align*}

where $t_2^+$ is defined in Corollary B.3 in Appendix B.1 and $\bar{\gamma}_*$ is the solution of Eq. (3.6) for the mean-field model. Lemma B.4 in Appendix B.1.1 leads to

(3.8)\begin{align} \left\| \left( \mathbb{E} \: \tilde{\mathcal{L}} \right)^{-1} \right\| & \ \le \ \frac{1}{\lambda + \bar{\alpha} }. \end{align}

The last ingredient needed is the concentration of the adjacency matrix around its expectation. We have

\begin{align*} \Big\|\tilde{\mathcal{L}} - \mathbb{E} \tilde{\mathcal{L}} \Big\| \ \le \ \left\| \left( \gamma_* - \bar{\gamma }_* \right) I_n \right\| + \| A - \mathbb{E} \: A \| \ \le \ \left| \: \gamma_* - \bar{\gamma }_* \: \right| + \| A - \mathbb{E} \: A \|. \end{align*}

Proposition B.5 in Appendix B.1.2 shows that

\begin{align*} \left| \: \gamma_* - \bar{\gamma} _* \: \right| & \ \le \ \left( 1 + \frac{\left( \bar{\alpha} + \lambda \right)^3 }{2 \sqrt{\eta_1+\eta_0} ( \eta_1 - \eta_0 ) \bar{\alpha}^2 \lambda } \right) \sqrt{\overline{d}}. \end{align*}

Moreover, when $d = \Omega(\log n)$, it is shown in [13] that for every r > 0 there exists a constant Cʹ such that $\left\| A - \mathbb{E} \: A \right\| \ \le \ C' \sqrt{\overline{d}}$ holds with probability at least $1-n^{-r}$. If $\bar{d} = o(\log n)$, the same result holds with a proper preprocessing on A, and we refer the reader to [19] for more details. We will omit this extra step in the proof to keep notations short. Using this concentration bound, we have

\begin{align*} \Big\|\tilde{\mathcal{L}} - \mathbb{E} \tilde{\mathcal{L}} \Big\| & \ \le \ \left( C' + \frac{27 \left( \bar{\alpha} + \lambda \right)^3 }{\sqrt{2} \sqrt{\eta_1+\eta_0} ( \eta_1 - \eta_0 ) \bar{\alpha}^2 \lambda } \right) \sqrt{\overline{d}} \\ & \ \le \ \left( C' + \frac{27}{\sqrt{2}} \right) \frac{(\lambda+\bar{\alpha})^3 }{\bar{\alpha}^2 \lambda } \frac{\sqrt{\overline{d}}}{\sqrt{\eta_1+\eta_0} \left( \eta_1-\eta_0 \right)} \end{align*}

for some constant Cʹ. Let $C = C' + \frac{27}{\sqrt{2}}$. By combining the above with inequality (3.8), the inequality (3.7) becomes

(3.9)\begin{equation} \dfrac{\left\| \widehat{X} - \bar{x} \right\| }{\left\| \bar{x} \right\| } \ \le \ C \, \frac{(\lambda+\bar{\alpha})^2 }{\bar{\alpha}^2 \lambda } \frac{\sqrt{\overline{d}} }{\sqrt{\eta_1+\eta_0} \left( \eta_1-\eta_0 \right)}. \end{equation}

1. (ii) Node i in the mean-field model is correctly classified by decision rule (3.3) if the sign of $\bar{x} _i$ equals the sign of Z_i. Corollary C.2 in Appendix C shows that this is indeed the case for the unlabeled nodes.

2. (iii) Finally, for an unlabeled node i to be correctly classified, the node’s value $\widehat{X} _{i}$ should be close enough to its mean-field value $\bar{x} _{i}$.

In particular, part (ii) shows that if $|\widehat{X} _{i} - \bar{x} _{i}|$ is smaller than some non-vanishing constant β, then an unlabeled node i will be correctly classified. An unlabeled node i is said to be β-bad if $\left| \widehat{X} _i - \bar{x} _i \right| \gt \beta$. We denote by S_β the set of β-bad nodes. The nodes that are not β-bad are almost surely correctly classified, and thus $ L \left( \widehat{Z} _u, Z_u \right) \le \frac{| S_\beta | }{n } $.

From $\left\| \widehat{X} - \bar{x} \right\|^2 \geq \sum\limits_{i \in S_{\beta} } \left| \widehat{X} _i - \bar{x} _i \right|^2$, it follows that $\left\| \widehat{X} - \bar{x} \right\|^2 \geq | S_{\beta} | \times \beta^2$. Thus, using inequality (3.9) and the norm constraint $\left\| \bar{x} \right\|^2 = n$, we have with probability at least $1-n^{-r}$,

\begin{align*} \left| S_{\beta} \right| & \ \le \ \dfrac{1}{\beta^2} \left( \frac{C}{\eta_1 - \eta_0} \frac{\bar{\alpha} + \lambda }{\bar{\alpha} \lambda} \sqrt{\overline{d}} \right)^2 n, \end{align*}

for some constant C. We end the proof by noticing that $\frac{\bar{d} }{\bar{\alpha} } = \frac{p_{\rm in} + p_{\rm out}}{p_{\rm in} - p_{\rm out}}$.

Corollary 3.2. (Almost exact recovery in the diverging degree regime)

Consider a DC-SBM such that $\bar{d} \gg 1$, $\frac{p_{\rm in} + p_{\rm out}}{p_{\rm in} - p_{\rm out}} = O(1)$, $\sqrt{\eta_0+\eta_1}(\eta_1 - \eta_0) \gg \frac{1}{\sqrt{\overline{d}}}$, and $\eta_0 n \sqrt{\eta_0+\eta_1} \ll \lambda$. Suppose that $\tau \gt p_{\rm out}$ and $\lambda \gt rsim \bar{\alpha }$. Then, Algorithm 1 correctly classifies almost all the unlabeled nodes.

Proof. With the corollary’s assumptions $(\eta_1-\eta_0)^2 \bar{d} \rightarrow +\infty$ and $\frac{\bar{\alpha } + \lambda}{\lambda} = O(1)$, by Theorem 3.1 the fraction of misclassified nodes is of the order o(1).

The quantity $(\eta_1 - \eta_0)n$ is the expected difference between the number of nodes correctly labeled and the number of nodes wrongly labeled by the oracle. In particular, Corollary 3.2 allows for a sub-linear number of labeled nodes since η ₀ and η ₁ can go to zero.

Corollary 3.3. (Detection in the constant degree regime)

Consider a DC-SBM such that $p_{\rm in} = \frac{c_{\rm in}}{n}$ and $p_{\rm out} = \frac{c_{\rm out}}{n}$ where $c_{\rm in}, c_{\rm out}$ are constants. Suppose that $\sqrt{\eta_0+\eta_1}(\eta_1 - \eta_0)$ is a non-zero constant, and let $\tau \gt 2p_{\rm out}$ and $\lambda \gt rsim 1$. Assume furthermore that $\eta_0 n \sqrt{\eta_0+\eta_1} \ll \lambda$. Then, for $\frac{(c_{\rm in} - c_{\rm out})^2}{c_{\rm in} + c_{\rm out}}$ bigger than some constant, w.h.p. Algorithm 1 performs better than a random guess.

Proof. According to Theorem 3.1, the fraction of misclassified nodes is smaller than $\frac{1}{2}$ when $\frac{(c_{\rm in} - c_{\rm out})^2}{c_{\rm in} + c_{\rm out}}$ is larger than $\frac{4C}{(\eta_1 - \eta_0)^2} \left( \frac{\bar{\alpha } + \lambda}{\lambda} \right)^2$, which is indeed lower-bounded by a constant.

The quantity $\frac{(c_{\rm in} - c_{\rm out})^2}{c_{\rm in} + c_{\rm out}}$ can be interpreted as the signal-to-noise ratio. It is unfortunate that Corollary 3.3 does not allow us to control the constant in the statement of the corollary. This constant comes from the concentration of the adjacency matrix. Similar remarks were made in [19] for the analysis of spectral clustering in the constant degree regime for SBMs graph.

4. Numerical experiments

This section presents numerical experiments both on simulated data sets generated from DC-SBMs and on real networks. In particular, we discuss the impact of the oracle mistakes (defined by the ratio $\frac{\eta_0}{\eta_0+\eta_1}$) on the performance of the algorithms. The code for the numerical experiments is available on GitHub at https://github.com/mdreveton/ssl-sbm

4.1. Synthetic data sets

4.1.1. Choice of λ and τ

Let us denote by σ ₁ and σ ₂ the largest and second largest eigenvalues of A. We choose $\tau = \frac{4}{n} (\sigma_1+\sigma_2)$ and $\lambda = \frac{\log \frac{\eta_1}{\eta_0} }{\log \frac{\sigma_1 + \sigma_2}{\sigma_1-\sigma_2} }$, if $\eta_0 \not=0$, and $\lambda = \frac{\log \left( n \eta_1 \right) }{\log \frac{\sigma_1 + \sigma_2}{\sigma_1-\sigma_2} }$, otherwise. The heuristic for this choice is as follows. For an SBM graph, we have $\sigma_1 \approx \frac{n}{2}\left(p_{\rm in} + p_{\rm out} \right)$ and $\sigma_2 \approx \frac{n}{2} ( p_{\rm in} - p_{\rm out})$, hence $ \frac{4}{n} (\sigma_1+\sigma_2) = 2 p_{\rm in} \gt p_{\rm out} $, and τ satisfies the condition of Theorem 3.1. For λ, we have $ \frac{\log \frac{\eta_1}{\eta_0} }{\log \frac{\sigma_1 + \sigma_2}{\sigma_1-\sigma_2} } \approx \frac{\log \frac{\eta_1}{\eta_0} }{\log \frac{p_{\rm in}}{p_{\rm out}} }$, which is indeed close to the expression of λ derived in Corollary 2.3 if $p_{\rm in}, p_{\rm out} = o(1)$.

4.1.2. Choice of relaxation

We first compare the choice of the constraint in the continuous relaxation (3.1). Specifically, we compare the choice $\sum_i x_i^2 = n$ (we refer to it as standard relaxation) versus $\sum_i d_i x_i^2 = 2|E|$ (we refer to it as degree-normalized relaxation). This leads to two versions of Algorithm 1, whose cost obtained on SBMs graph with a noisy oracle is presented in Figure 1. In particular, we observe that the normalized choice leads to a smaller cost. Therefore, in the following we will only consider the version of Algorithm 1 solving the relaxed problem (3.1) with constraint $\sum_{i} d_i x_i^2 = 2 |E|$ instead of $\sum_i x_i^2 = n$, as it gives better numerical results.

Figure 1. Cost in Algorithm 1 with the standard and normalized versions of the constraint, on 50 realizations of SBM with $n = 500, p_{\rm out} = 0.03$ and 50 labeled nodes with $10\%$ noise.

4.1.3. Experiments on synthetic graphs

We first consider clustering on DC-SBM. We set n = 2000, $p_{\rm in} = 0.04$, and $p_{\rm out} = 0.02$. We consider three scenarios.

• • In Figure 2(a) we consider a standard SBM ($\theta_i= 1$ for all i);

• • In Figure 2(b) we generate θ_i according to $|\mathcal{N}( 0, \sigma^2)| + 1 - \sigma \sqrt{2/\pi} $ where $| \mathcal{N}(0, \sigma^2) |$ denotes the absolute value of a normal random variable with mean 0 and variance σ ². We take σ = 0.25. Note that this definition enforces $\mathbb{E} \theta_i = 1$.

• • In Figure 2(c) we generate θ_i from Pareto distribution with density function $f(x) = \frac{a m^a}{x^{a+1} } 1(x \geq m)$ with a = 3 and $m = 2/3$ (chosen such that $\mathbb{E} \theta_i = 1$).

We compare the performance of Algorithm 1 with that of the algorithm of [22] (referred to as Centered similarities) and the Poisson learning algorithm described in [10]. We chose these two algorithms as references since they perform very well on real data sets and are designed to avoid flat solutions. Results are shown in Figure 2. We observe that when the oracle noise is low, the performance of Algorithm 1 is comparable to Centered similarities. But, when the noise becomes non-negligible, the performance of Centered similarities deteriorates, while the accuracy of Algorithm 1 remains high. We notice that Poisson learning gives poor results on synthetic data sets.

Figure 2. Average accuracy obtained by different semi-supervised clustering methods on DC-SBM graphs, with $n = 2000,\ p_{\rm in} = 0.04$, and $ p_{\rm out} = 0.02$ with different distributions for θ. The number of labeled nodes is equal to 40. Accuracies are computed on the unlabeled nodes, and are averaged over 100 realizations; the error bars show the standard error.

4.2. Experiments on real data

We next use real data to show that even if real networks are not generated by the DC-SBM, Algorithm 1 still performs well.

4.2.1. MNIST

As a real-life example, we perform simulations on the standard MNIST data set [20]. As preprocessing, we select 1000 images corresponding to two digits and compute the k-nearest-neighbors graph (we take k = 8) with Gaussian weights $w_{ij} = \exp\left( - \|x_i - x_j\|^2 / s_i^2 \right)$ where x_i represents the data for image i and s_i is the average distance between x_i and its K-nearest neighbors. Figure 3 gives accuracy for different digit pairs. While the performance of Poisson learning is excellent, it can suffer from the oracle noise. On the other hand, the accuracy of Algorithm 1 remains unchanged.

Figure 3. Average accuracy obtained on a subset of the MNIST data set by different semi-supervised algorithms as a function of the oracle-misclassification ratio, when the number of labeled nodes is equal to 10. Accuracy is averaged over 100 random realizations, and the error bars show the standard error.

To further highlight the influence of the noise, we plot in Figure 4 the accuracy obtained by the three algorithms on the unlabeled nodes, the correctly labeled nodes, and the wrongly labeled nodes. We observe that the hard constraint $X_\ell = s_\ell$ imposed by Centered similarities forces the correctly labeled nodes to be correctly classified. In contrast, the wrongly labeled nodes are not classified much better than a random guess. This heavily penalizes the unlabeled nodes’ accuracy in an extremely noisy setting. On the contrary, Algorithm 1 allows for a smoother recovery: the unlabeled, correctly labeled, and wrongly labeled nodes have roughly the same classification accuracy. While some correctly labeled nodes are misclassified, many wrongly labeled nodes become correctly classified, and the unlabeled nodes are better recovered. Finally, Poisson learning shows a performance somewhere in between these two extreme cases: its accuracy on the unlabeled nodes is excellent, but it fails at correctly classifying the erroneously labeled nodes.

Figure 4. Average accuracy obtained on the unlabeled, correctly labeled, and wrongly labeled nodes by the oracle. Simulations are done on the 1,000 digits (2,4). The noisy oracle correctly classifies 24 nodes and misclassifies 16 nodes, and the boxplots show 100 realizations.

4.2.2. Common benchmark networks

Finally, we perform simulations on three benchmark networks: Political Blogs, LiveJournal, and DBLP. These networks are commonly used for graph clustering since the “ground truth” clusters are known. For LiveJournal and DBLP, we consider only the two largest clusters. The dimension of the data sets is given in Table 1 and the performances of semi-supervised algorithms in Figure 5. We observe that Algorithm 1 and Poisson learning outperform Centered similarities and can still achieve good accuracy even in the presence of noise in labeled data.

Figure 5. Average accuracy obtained on real networks by different semi-supervised algorithms as a function of the oracle-misclassification ratio. The number of labeled nodes is 30 for Political Blogs and LiveJournal, and 100 for DBLP. Accuracy is averaged over 50 random realizations, and the error bars show the standard error.

Table 1. Parameters of the real data sets. n₁ (resp., n₂) corresponds to the size of the first (resp., second) cluster, and $|E|$ is the number of edges of the network.