Recovering communities in the general stochastic block model without knowing the parameters

Introduction

This paper studies the problem of recovering communities in the general stochastic block model with linear size communities, for constant and slowly diverging degree regimes. In contrast to [AS15], this paper does not require knowledge of the SBM parameters. In particular, the problem of learning the model parameters is solved when average degrees are diverging. We next provide some motivations on the problem and further background on the model.

Detecting communities (or clusters) in graphs is a fundamental problem in networks, computer science and machine learning. This applies to a large variety of complex networks (e.g., social and biological networks) as well as to data sets engineered as networks via similarly graphs, where one often attempts to get a first impression on the data by trying to identify groups with similar behavior. In particular, finding communities allows one to find like-minded people in social networks [GN02, NWS], to improve recommendation systems [LSY03, XWZ+14], to segment or classify images [SM97, SHB07], to detect protein complexes [CY06, MPN+99], to find genetically related sub-populations [PSD00, JTZ04], or discover new tumor subclasses [SPT+01].

While a large variety of community detection algorithms have been deployed in the past decades, the understanding of the fundamental limits of community detection has only appeared more recently, in particular for the SBM [Co10, DKMZ11, Mas14, MNS14, ABH14, MNSb, YC14, AS15]. The SBM is a canonical model for community detection [HLL83, WBB76, FMW85, WW87, BC09, KN11, BCLS87, DF89, Bop87, JS98, CK99, CI01, SN97, McS01, BC09, RCY11, CWA12, CSX12], where $n$ vertices are partitioned into $k$ communities of relative size $p_{i}$, $i\in[k]$, and pairs of nodes in communities $i$ and $j$ connect independently with probability $W_{i,j}$.

Recently the SBM came back to the center of the attention at both the practical level, due to extensions allowing overlapping communities [ABFX08] that have proved to fit well real data sets in massive networks [GB13], and at the theoretical level due to new phase transition phenomena [Co10, DKMZ11, Mas14, MNS14, ABH14, MNSb]. The latter works focus exclusively on the SBM with two symmetric communities, i.e., each community is of the same size and the connectivity in each community is identical. Denoting by $p$ the intra- and $q$ the extra-cluster probabilities, most of the results are concerned with two figure of merits: (i) recovery (also called exact recovery or strong consistency), which investigates the regimes of $p$ and $q$ for which there exists an algorithm that recovers with high probability the two communities completely [BCLS87, DF89, Bop87, JS98, CK99, CI01, SN97, McS01, BC09, RCY11, CWA12, CSX12, Vu14, YC14], (ii) detection, which investigates the regimes for which there exists an algorithm that recovers with high probability a positively correlated partition [Co10, DKMZ11, MNS12, Mas14, MNS14].

The sharp threshold for exact recovery was obtained in [ABH14, MNSb], showing[MNSb] generalizes this to $a,b=\Theta(1)$. that for $p=a\log(n)/n$, $q=b\log(n)/n$, $a,b>0$, exact recovery is solvable if and only if $\sqrt{a}-\sqrt{b}\geq 2$, with efficient algorithms achieving the threshold provided in [ABH14, MNSb]. In addition, [ABH14] introduces an SDP proved to achieve the threshold in [BH14, Ban15], while [YP14] shows that a spectral algorithm also achieves the threshold. Prior to these, the sharp threshold for detection was obtained in [Mas14, MNS14], showing that detection is solvable (and so efficiently) if and only if $(a-b)^{2}>2(a+b)$, when $p=a/n$, $q=b/n$, settling a conjecture made in [DKMZ11] and improving on [Co10].

Besides the detection and the recovery properties, one may ask about the partial recovery of the communities, studied in [MNSa, GV14, Vu14, CRV15, AS15]. Of particular interest to this paper is the case of almost exact recovery (also called weak consistency), where only a vanishing fraction of the nodes is allowed to be misclassified. For two-symmetric communities, [MNSb] shows that almost exact recovery is possible if and only if $n(p-q)^{2}/(p+q)$ diverges, generalized in [AS15] for general SBMs.

In the next section, we discuss the results for the general SBM of interest in this paper and the problem of learning the model parameters. We conclude this section by providing motivations on the problem of achieving the threshold with an efficient and universal algorithm.

Threshold phenomena have long been studied in fields such as information theory (e.g., Shannon’s capacity) and constraint satisfaction problems (e.g., the SAT threshold). In particular, the quest of achieving the threshold has generated major algorithmic developments in these fields (e.g., LDPC codes, polar codes, survey propagation to name a few). Likewise, identifying thresholds in community detection models is key to benchmark and guide the development of clustering algorithms. Most reasonable algorithms may succeed in some regimes, while in others they may be doomed to fail due to computational barriers. However, it is particularly crucial to develop benchmarks that do not depend sensitively on the knowledge of the model parameters. A natural question is hence whether one can solve the various recovery problems in the SBM without having access to the parameters. This paper answers this question by the affirmative for the exact and almost exact recovery of the communities.

Most of the previous works are concerned with the SBM having symmetric communities (mainly 2 or sometimes $k$), with the exception of [Vu14] which provides some achievability results for the general SBM.[GV14] also study variations of the $k$-symmetric model. Recently, [AS15] studied the fundamental limits for the general SBM, with results as follows (where SBM$(n,p,W)$ is the SBM with community prior $p$ and connectivity matrix $W$).

The algorithm Sphere-comparison is proposed that solves partial recovery with exponential accuracy and quasi-linear complexity when the SNR diverges, solving in particular almost exact recovery.

Note that for $k$ symmetric clusters, SNR reduces to $\frac{(a-b)^{2}}{k(a+(k-1)b)}$, which is the quantity of interest for detection [DKMZ11, MNS12]. Moreover, the SNR must diverge to ensure almost exact recovery in the symmetric case [AS15]. The following is an important consequence of the previous theorem, as it shows that Sphere-comparison achieves almost exact recovery when the entries of $Q$ are scaled.

II. Exact recovery in the general SBM. The second result in [AS15] is for the regime where the connectivity matrix scales as $\log(n)Q/n$, $Q$ fixed, where it is shown that exact recovery has a sharp threshold characterized by the divergence function

named the CH-divergence in [AS15]. Specifically, if all pairs of columns in $\operatorname{diag}(p)Q$ are at $D_{+}$-distance at least 1 from each other, then exact recovery is solvable in the general SBM. This provides in particular an operational meaning to a new divergence function analog to the KL-divergence in the channel coding theorem (see Section 2.3 in [AS15]). Moreover, an algorithm (Degree-profiling) is developed that solves exact recovery down to the $D_{+}$ limit in quasi-linear time, showing that exact recovery has no informational to computational gap (as opposed to the conjectures made for detection with more than 4 communities [DKMZ11]). The following gives a more general statement characterizing which subset of communities can be extracted — see Definition 3 for formal definitions.

In particular, exact recovery is information-theoretically solvable in SBM$(n,p,Q\log(n)/n)$ if and only if $\min_{i,j\in[k],i\neq j}D_{+}((PQ)_{i}||(PQ)_{j})\geq 1$. (ii) The Degree-profiling algorithm (see [AS15]) recovers the finest partition that can be recovered with probability $1-o_{n}(1)$ and runs in $o(n^{1+\epsilon})$ time for all $\epsilon>0$. In particular, exact recovery is efficiently solvable whenever it is information-theoretically solvable.

In summary, exact or almost exact recovery is closed for the general SBM (and detection is closed for 2 symmetric communities). However this is for the case where the parameters of the SBM are assumed to be known, and with linear-size communities.

2 Estimating the parameters

For the estimation of the parameter, some results are known for two-symmetric communities. In the logarithmic degree regime, since the SDP is agnostic to the parameters (it is a relaxation of the min-bisection), and the parameters can be estimated by recovering the communities [ABH14, BH14, Ban15]. For the constant-degree regime, [MNS12] shows that the parameters can be estimated above the threshold by counting cycles (which is efficiently approximated by counting non-backtracking walks). These are however for a fixed number of communities, namely 2. We also became recently aware of a parallel work [BCS15], which considers private graphon estimation (including SBMs). In particular, for the logarithmic degree regime, [BCS15] obtains a procedure to estimate parameters of graphons in an appropriate version of the $L_{2}$ norm. This procedure is however not efficient.

For the general SBM, the results of [AS15] allow to find communities efficiently, however these rely on the knowledge of the parameters. Hence, a major open problem is to understand if these results can be extended without such a knowledge.

Results

Agnostic algorithms are developed for the constant and diverging node degrees. These afford optimal accuracy scaling for large node degrees and achieve the CH-divergence limit for logarithmic node degrees in quasi-linear time. In particular, these solve the parameter estimation problems for SBM$(n,p,\omega(1)Q)$ without knowing the number of communities. An example with real data is provided in Section 4.

The general stochastic block model $\text{SBM}(n,p,W)$ is a random graph ensemble defined on the vertex-set $V=[n]$, where each vertex $v\in V$ is assigned independently a hidden (or planted) label $\sigma_{v}$ in $[k]$ under a probability distribution $p=(p_{1},\dots,p_{k})$ on $[k]$, and each (unordered) pair of nodes $(u,v)\in V\times V$ is connected independently with probability $W_{\sigma_{u},\sigma_{v}}$, where $W_{\sigma_{u},\sigma_{v}}$ is specified by a symmetric $k\times k$ matrix $W$ with entries in $$. Note that$G\sim\text{SBM}(n,p,W)$denotes a random graph drawn under this model, without the hidden (or planted) clusters (i.e., the labels$\sigma_{v}$ ) revealed. The goal is to recover these labels by observing only the graph.

This paper focuses on $p$ independent of $n$ (the communities have linear size), $W$ dependent on $n$ such that the average node degrees are either constant or logarithmically growing, and $k$ fixed. These assumptions on $p$ and $k$ could be relaxed, for example to slowly growing $k$, but we leave this for future work. As discussed in the introduction, the above regimes for $W$ are both motivated by applications, as networks are typically sparse [LLDM08, Str01] though the average degrees may not be small, and by the fact that interesting mathematical phenomena take place in these regimes. For convenience, we attribute specific notations for the model in these regimes:

(Partial recovery.) An algorithm recovers or detects communities in $\text{SBM}(n,p,W)$ with an accuracy of $\alpha\in$, if it outputs a labelling of the nodes $\{\sigma^{\prime}(v),v\in V\}$, which agrees with the true labelling $\sigma$ on a fraction $\alpha$ of the nodes with probability $1-o_{n}(1)$. The agreement is maximized over relabellings of the communities.

(Exact recovery.) Exact recovery is solvable in $\text{SBM}(n,p,W)$ for a community partition $[k]=\sqcup_{s=1}^{t}A_{s}$, where $A_{s}$ is a subset of $[k]$, if there exists an algorithm that takes $G\sim SBM(n,p,W)$ and assigns to each node in $G$ an element of $\{A_{1},\dots,A_{t}\}$ that contains its true communityThis is again up to relabellings of the communities. with probability $1-o_{n}(1)$. Exact recovery is solvable in $\text{SBM}(n,p,W)$ if it is solvable for the partition of $[k]$ into $k$ singletons, i.e., all communities can be recovered.

The problem is solvable information-theoretically if there exists an algorithm that solves it, and efficiently if the algorithm runs in polynomial-time in $n$. Note that exact recovery for the partition $[k]=\{i\}\sqcup([k]\setminus\{i\})$ is equivalent to extracting community $i$. In general, recovering a partition $[k]=\sqcup_{s=1}^{t}A_{s}$ is equivalent to merging the communities that are in a common subset $A_{s}$ and recovering the merged communities. Note also that exact recovery in $\text{SBM}(n,p,W)$ requires the graph not to have vertices of degree in multiple communities with high probability (i.e., connectivity in the symmetric case). Therefore, for exact recovery, we focus below on $W=\frac{\ln(n)}{n}Q$ where $Q$ is fixed.

2 Partial recovery

Our main result in the Appendix (Theorme 6) applies to SBM$(n,p,Q/n)$ with arbitrary $Q$. We provided here a specific instance which is easier to parse.

Note that a vertex in community $i$ has degree with probability exponential in $c$, and there is no way to differentiate between vertices of degree from different communities. So, an error rate that decreases exponentially with $c$ is optimal. The above gives in particular the parameter estimation in the case $c=\omega(1)$ (see also Lemma 17 in the Appendix).

The general result in the Appendix yields the following refined results in the $k$-block symmetric case.

Consider the $k$-block symmetric case. In other words, $p_{i}=\frac{1}{k}$ for all $i$, and $Q_{i,j}$ is $\alpha$ if $i=j$ and $\beta$ otherwise. The vector whose entries are all $1$s is an eigenvector of $PQ$ with eigenvalue $\frac{\alpha+(k-1)\beta}{k}$, and every vector whose entries add up to is an eigenvector of $PQ$ with eigenvalue $\frac{\alpha-\beta}{k}$. So, $\lambda=\frac{\alpha+(k-1)\beta}{k}$ and $\lambda^{\prime}=\frac{\alpha-\beta}{k}$ and $\frac{(\lambda^{\prime})^{2}}{\lambda}=\frac{(a-b)^{2}}{k(a+(k-1)\beta)}.$ Then, as long as $\frac{160}{9}k(\alpha+(k-1)\beta)^{7}<(\alpha-\beta)^{8}$ and $4k(\alpha+(k-1)\beta)^{3}<(\alpha-\beta)^{4}$, there exist a constant $c>0$ such that Agnostic-sphere-comparison($G,1/k$) detects communities with an accuracy of $1-O(e^{-c(\alpha-\beta)^{2}/(\alpha+(k-1)\beta)})$ for sufficiently large $(\alpha-\beta)^{2}/(\alpha+(k-1)\beta)$.

We refer to Section 4 for an example of implementation with real data.

3 Exact recovery

We next show that this can be achieved without knowing the parameters. Recall that the finest partition is the largest partition of $[k]$ that ensure (19).

The proof assumes that the entries of $Q$ are non-zero, see Remark 1 for zero entries. To achieve this result we rely on a two step procedure. First an algorithm is developed to recover all but a vanishing fraction of nodes — this is the main focus of our partial recovery result — and then a procedure is used to “clean up” the leftover graphs using the node degrees of the preliminary classification. This turns out to be much more efficient than aiming for an algorithm that directly achieves exact recovery. We already used this technique in [AS15], but here we also deal with the difficulties resulting from not knowing the SBM’s parameters.

Proof Techniques and Algorithms

For any vertex $v$, let $N_{r}(v)$ be the set of all vertices with shortest path to $v$ of length $r$. We also refer to the vector with $i$-th entry equal to the number of vertices in $N_{r}(v)$ that are in community $i$ as $N_{r}(v)$. If there are multiple graphs that $v$ could be considered a vertex in, let $N_{r[G]}(v)$ be the set of all vertices with shortest paths in $G$ to $v$ of length $r$.

One could probably determine $PQ$ and $e_{\sigma}$ given the values of $(PQ)^{r}e_{\sigma_{v}}$ for a few different $r$, but using $N_{r}(v)$ to approximate that would require knowing how many of the vertices in $N_{r}(v)$ are in each community. So, we attempt to get information relating to how many vertices in $N_{r}(v)$ are in each community by checking how it connects to $N_{r^{\prime}}(v^{\prime})$ for some vertex $v^{\prime}$ and integer $r^{\prime}$. The obvious way to do this would be to compute the cardinality of their intersection. Unfortunately, whether a given vertex in community $i$ is in $N_{r}(v)$ is not independent of whether it is in $N_{r^{\prime}}(v^{\prime})$, which causes the cardinality of $|N_{r}(v)\cap N_{r^{\prime}}(v^{\prime})|$ to differ from what one would expect badly enough to disrupt plans to use it for approximations.

In order to get around this, we randomly assign every edge in $G$ to a set $E$ with probability $c$. We hence define the following.

Note that $E$ and $G\backslash E$ are disjoint; however, $G$ is sparse enough that even if they were generated independently a given pair of vertices would have an edge between them in both with probability $O(\frac{1}{n^{2}})$. So, $E$ is approximately independent of $G\backslash E$. Thus, for any $v_{1}\in N_{r[G/E]}(v)$ and $v_{2}\in N_{r^{\prime}[G/E]}(v^{\prime})$, $(v_{1},v_{2})\in E$ with a probability of approximately $cQ_{\sigma_{v_{1}},\sigma_{v_{2}}}/n$. As a result,

Let $\lambda_{1},...,\lambda_{h}$ be the distinct eigenvalues of $PQ$, ordered so that $|\lambda_{1}|\geq|\lambda_{2}|\geq...\geq|\lambda_{h}|\geq 0$. Also define $h^{\prime}$ so that $h^{\prime}=h$ if $\lambda_{h}\neq 0$ and $h^{\prime}=h-1$ if $\lambda_{h}=0$. If $W_{i}$ is the eigenspace of $PQ$ corresponding to the eigenvalue $\lambda_{i}$, and $P_{W_{i}}$ is the projection operator on to $W_{i}$, then

where the final equality holds because for all $i\neq j$,

and since $\lambda_{i}\neq\lambda_{j}$, this implies that $P_{W_{i}}(e_{\sigma_{v}})\cdot P^{-1}P_{W_{j}}(e_{\sigma_{v^{\prime}}})=0$. In order to simplify the terminology,

Let $\zeta_{i}(v\cdot v^{\prime})=P_{W_{i}}(e_{\sigma_{v}})\cdot P^{-1}P_{W_{i}}(e_{\sigma_{v^{\prime}}})$ for all $i$, $v$, and $v^{\prime}$.

Equation (14) is dominated by the $\lambda_{1}^{r+r^{\prime}+1}$ term, so getting good estimate of the $\lambda_{2}^{r+r^{\prime}+1}$ through $\lambda_{h^{\prime}}^{r+r^{\prime}+1}$ terms requires cancelling it out somehow. As a start, if $\lambda_{1}>\lambda_{2}>\lambda_{3}$ then

Note that the left hand side of this expression is equal to $\det{}\begin{vmatrix}N_{r,r^{\prime}[E]}(v\cdot v^{\prime})&N_{r+1,r^{\prime}[E]}(v\cdot v^{\prime})\\ N_{r+1,r^{\prime}[E]}(v\cdot v^{\prime})&N_{r+2,r^{\prime}[E]}(v\cdot v^{\prime})\end{vmatrix}$. More generally, in order to get an expression that can be used to estimate the $\lambda_{i}$ and $\zeta_{i}(v\cdot v^{\prime})$, we consider the determinant of the following.

Let $M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime})$ be the $m\times m$ matrix such that $M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime})_{i,j}=N_{r+i+j,r^{\prime}[E]}(v\cdot v^{\prime})$ for each $i$ and $j$.

To the degree that approximation 8 holds and $c$ is small, each column of $M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime})$ is a linear combination of the vectors

with coefficients that depend only on $\{\lambda_{1},...,\lambda_{h}\}$. So, by linearity of the determinant in one column, $\det(M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime}))$ is a linear combination of these vector’s wedge products with coefficients that are independent of $r$ and $r^{\prime}$. By antisymmetry of wedge products, only the products that use $m$ different such vectors contribute to the determinant, and the products involving the eigenvalues of highest magnitude will dominate. As a result, there exist constants $\gamma(\lambda_{1},...,\lambda_{m})$ and $\gamma^{\prime}(\lambda_{1},...,\lambda_{m})$ such that

if $|\lambda_{m}|=|\lambda_{m+1}|$. These facts suggest the following plan for estimating the eigenvalues corresponding to a graph. First, pick several vertices at random. Then, use the fact that $|N_{r[G\backslash E]}(v)|\approx((1-c)\lambda_{1})^{r}$ for any good vertex $v$ to estimate $\lambda_{1}$. Next, use the formulas above about $\det(M_{m,r,r^{\prime}[E]}(v\cdot v))$ to get an approximation of $h^{\prime}$ and all of $PQ$’s eigenvalues for each selected vertex. Finally, take the median of these estimates.

Now, note that whether or not $|\lambda_{m}|=|\lambda_{m+1}|$, we have

This fact can be used in combination with estimates of $PQ$’s eigenvalues to approximate $\zeta_{i}(v\cdot v^{\prime})$ for arbitrary $v$, $v^{\prime}$, and $i$.

Of course, this requires $r$ and $r^{\prime}$ to be large enough that

is large relative to the error terms for all $i\leq h^{\prime}$. At a minimum, that requires that $|(1-c)\lambda_{i}|^{r+r^{\prime}+1}=\omega(n)$.

On a different note, for any $v$ and $v^{\prime}$,

with equality for all $i$ if and only if $\sigma_{v}=\sigma_{v^{\prime}}$, so sufficiently good approximations of $\zeta_{i}(v\cdot v),\zeta_{i}(v\cdot v^{\prime})$ and $\zeta_{i}(v^{\prime}\cdot v^{\prime})$ can be used to determine which pairs of vertices are in the same community.

One could generate a reasonable classification based solely on this method of comparing vertices. However, that would require computing $N_{r,r^{\prime}[E]}(v\cdot v)$ for every vertex in the graph with fairly large $r+r^{\prime}$, which would be slow. Instead, we use the fact that for any vertices $v$, $v^{\prime}$, and $v^{\prime\prime}$ with $\sigma_{v}=\sigma_{v^{\prime}}\neq\sigma_{v^{\prime\prime}}$,

for all $i$, and the inequality is strict for at least one $i$. So, subtracting $\zeta_{i}(v\cdot v)$ from both sides gives us that

for all $i$, and the inequality is still strict for at least one $i$.

So, given a representative vertex in each community, we can determine which of them a given vertex, $v$, is in the same community as without needing to know the value of $\zeta_{i}(v\cdot v)$.

This runs fairly quickly if $\zeta_{i}(v\cdot v^{\prime})$ is approximated using $N_{r,r^{\prime}[E]}(v^{\prime}\cdot v)$ such that $r$ is large and $r^{\prime}$ is small because the algorithm only requires focusing on $|N_{r^{\prime}}(v)|$ vertices. This leads to the following plan for partial recovery. First, randomly select a set of vertices that is large enough to contain at least one vertex from each community with high probability. Next, compare all of the selected vertices in an attempt to determine which of them are in the same communities. Then, pick one in each community. After that, use the algorithm referred to above to attempt to determine which community each of the remaining vertices is in. As long as there actually was at least one vertex from each community in the initial set and none of the approximations were particularly bad, this should give a reasonably accurate classification.

The risk that this randomly gives a bad classification due to a bad set of initial vertices can be mitigated as follows. First, repeat the previous classification procedure several times. Assuming that the procedure gives a good classification more often than not, the good classifications should comprise a set that contains more than half the classifications and which has fairly little difference between any two elements of the set. Furthermore, any such set would have to contain at least one good classification, so none of its elements could be too bad. So, find such a set and average its classifications together. This completes the Agnostic-Sphere-comparison-algorithm. We refer to Section 6 for a detailed version.

2 Exact recovery and the Agnostic-degree-profiling algorithm

This is proved in [AS15]. In the case of unknown parameters, the algorithmic approach is largely unchanged, adding a step where the best known classification is used to estimate $P$ and $Q$ prior to any step in which vertices are classified based on their neighbors. The analysis of the algorithm requires however some careful handling.

First, it is necessary to prove that given a labelling of the graph’s vertices with an error rate of $x$, one can compute approximations of $P$ and $Q$ that are within $O(x+\log(n)/\sqrt{n})$ of their true values with probability $1-o(1)$. Secondly, one needs to modify the robust degree profiling lemma to show that attempting to determine vertices’ communities based on estimates of $p$ and $Q$ that are off by at most $\delta$, $p^{\prime}$ and $Q^{\prime}$, and a classification of its neighbors that has an error rate of $\delta$ classifies the vertices with an error rate only $e^{O(\delta\log n)}$ times higher than it would be given accurate values of $p$ and $Q$ and accurate classifications of the vertices’ neighbors. Combining these yields the conclusion that any errors in the estimates of the SBM’s parameters do not disrupt vertex classification any worse than the errors in the preliminary classifications already were.

The Agnostic-degree-profiling algorithm. The inputs are $(G,\gamma)$, where $G$ is a graph, and $\gamma\in$ (see Theorem 7 for how to set $\gamma$).

The algorithm outputs an assignment of each vertex to one of the groups of communities $\{A_{1},\dots,A_{t}\}$, where $A_{1},\dots,A_{t}$ is the partition of $[k]$ in to the largest number of subsets such that $D_{+}((pQ)_{i},(pQ)_{j})\geq 1$ for all $i,j$ in $[k]$ that are in different subsets (this is called the “finest partition”). It does the following:

(1) Define the graph $g^{\prime}$ on the vertex set $[n]$ by selecting each edge in $g$ independently with probability $\gamma$, and define the graph $g^{\prime\prime}$ that contains the edges in $g$ that are not in $g^{\prime}$.

(2) Run Agnostic-sphere-comparison on $g^{\prime}$ to obtain the preliminary classification $\sigma^{\prime}\in[k]^{n}$ (see Section 7.1.)

(3) Determine the size of each alleged community, and the edge density between each pair of alleged communities.

(4) For each node $v\in[n]$, determine in which community node $v$ is most likely to belong to based on its degree profile computed from the preliminary classification $\sigma^{\prime}$ (see Section 7.2.2), and call it $\sigma^{\prime\prime}_{v}$

(5) Use $\sigma^{\prime\prime}_{v}$ to get new estimates of $p$ and $Q$.

(6) For each node $v\in[n]$, determine in which group $A_{1},\dots,A_{t}$ node $v$ is most likely to belong to based on its degree profile computed from the preliminary classification $\sigma^{\prime\prime}$ (see Section 7.2.2).

An example with real data

We have tested a simplified version of our algorithm on the data from “The political blogosphere and the 2004 US Election” [AG05], which contains a list of political blogs that were classified as liberal or conservative, and links between the blogs.

The algorithm we used has a few major modifications relative to our standard algorithm. First of all, instead of using $N_{r,r^{\prime}}(v\cdot v^{\prime})$ as its basic tool for comparing vertices, it uses a different measure, $N^{\prime}_{r,r^{\prime}}(v\cdot v^{\prime})$ which is defined as the fraction of pairs of an edge leaving the ball of radius $r$ centered on $v$ and an edge leaving the ball of radius $r^{\prime}$ centered on $v^{\prime}$ which hit the same vertex but are not the same edge. Making the measure a fraction of the pairs rather than a count of pairs was necessary to prevent $N^{\prime}_{r,r^{\prime}}(v\cdot v^{\prime})$ from being massively dependent on the degrees of $v$ and $v^{\prime}$, which would have resulted in the increased variance in vertex degree obscuring the effects of $\sigma_{v}$ and $\sigma_{v^{\prime}}$ on $N^{\prime}_{r,r^{\prime}}(v\cdot v^{\prime})$. The other changes to the definition make the measure somewhat less reliable, but it is still useable as long as the average degree is fairly high and $v\neq v^{\prime}$.

Secondly, the version of Vertex-comparison-algorithm we used simply concludes that two vertices, $v$ and $v^{\prime}$, are in different communities if $N^{\prime}_{r,r^{\prime}}(v\cdot v^{\prime})$ is below average and the same community otherwise. This is reasonable because of the following facts. For one thing, because the normalization converts the dominant term to a constant, $N^{\prime}_{r,r^{\prime}}(v\cdot v^{\prime})$ is approximately affine in $(\lambda_{2}/\lambda_{1})^{r+r^{\prime}}\zeta_{2}(v\cdot v^{\prime})/n$. Also, as a result of the symmetry between communities, $\zeta_{2}(v\cdot v)$ is the same for all $v$. So, $\zeta_{2}(v\cdot v)-2\zeta_{2}(v\cdot v^{\prime})+\zeta_{2}(v^{\prime}\cdot v^{\prime})$ is also affine in $\zeta_{2}(v\cdot v^{\prime})$. Furthermore, there are only two possible values of $\zeta_{2}(v\cdot v^{\prime})$ by symmetry, and $\lambda_{2}>0$, so $\zeta_{2}(v\cdot v)-2\zeta_{2}(v\cdot v^{\prime})+\zeta_{2}(v^{\prime}\cdot v^{\prime})>0$ iff $(\lambda_{2}/\lambda_{1})^{r+r^{\prime}}\zeta_{2}(v\cdot v^{\prime})/n$ is below average. Finally, because both communities have the same average degree, $\zeta_{1}(v,v^{\prime})$ is independent of $v$ and $v^{\prime}$ so $\zeta_{1}(v\cdot v)-2\zeta_{1}(v\cdot v^{\prime})+\zeta_{1}(v^{\prime}\cdot v^{\prime})$ is always . The version of Vertex-classification-algorithm we used is comparably modified.

Finally, our algorithm generates reference vertices by repeatedly picking two vertices at random and comparing them. If it concludes that they are in different communities and they both have above-average degree, it accepts them as reference vertices; otherwise it tries again. Requiring above-average degree is useful because a higher degree vertex is less likely to have its neighborhood distorted by a couple of atypical neighbors.

Out of $40$ trials, the resulting algorithm gave a reasonably good classification $37$ times. Each of these classified all but $56$ to $67$ of the $1222$ vertices in the graph’s main component correctly. The state-of-the-art described in [CG15] gives a lowest value at 58, with the best algorithms around $60$, while algorithms regularized spectral methods such as the one in [QR13] obtain about 80 errors.

Open problems

The current result should also extend directly to a slowly growing number of communities (e.g., up to logarithmic). It would be interesting to extend the current approach to smaller sized communities or larger numbers of communities (watching the complexity scaling with the number of communities), as well as more general models with corrected-degrees, labeled-edges, or overlapping communities (though linear-sized overlapping communities can be treated with the approach of [AS15]).

References

The Agnostic-sphere-comparison algorithm in details

Recall the following motivation and definitions.

For any vertex $v$, let $N_{r}(v)$ be the set of all vertices with shortest path to $v$ of length $r$. We also refer to the vector with $i$-th entry equal to the number of vertices in $N_{r}(v)$ that are in community $i$ as $N_{r}(v)$. If there are multiple graphs that $v$ could be considered a vertex in, let $N_{r[G]}(v)$ be the set of all vertices with shortest paths in $G$ to $v$ of length $r$.

One could probably determine $PQ$ and $e_{\sigma}$ given the values of $(PQ)^{r}e_{\sigma_{v}}$ for a few different $r$, but using $N_{r}(v)$ to approximate that would require knowing how many of the vertices in $N_{r}(v)$ are in each community. So, we attempt to get information relating to how many vertices in $N_{r}(v)$ are in each community by checking how it connects to $N_{r^{\prime}}(v^{\prime})$ for some vertex $v^{\prime}$ and integer $r^{\prime}$. The obvious way to do this would be to compute the cardinality of their intersection. Unfortunately, whether a given vertex in community $i$ is in $N_{r}(v)$ is not independent of whether it is in $N_{r^{\prime}}(v^{\prime})$, which causes the cardinality of $|N_{r}(v)\cap N_{r^{\prime}}(v^{\prime})|$ to differ from what one would expect badly enough to disrupt plans to use it for approximations.

In order to get around this, we randomly assign every edge in $G$ to a set $E$ with probability $c$. We hence define the following.

Note that $E$ and $G\backslash E$ are disjoint; however, $G$ is sparse enough that even if they were generated independently a given pair of vertices would have an edge between them in both with probability $O(\frac{1}{n^{2}})$. So, $E$ is approximately independent of $G\backslash E$. Thus, for any $v_{1}\in N_{r[G/E]}(v)$ and $v_{2}\in N_{r^{\prime}[G/E]}(v^{\prime})$, $(v_{1},v_{2})\in E$ with a probability of approximately $cQ_{\sigma_{v_{1}},\sigma_{v_{2}}}/n$. As a result,

Let $\lambda_{1},...,\lambda_{h}$ be the distinct eigenvalues of $PQ$, ordered so that $|\lambda_{1}|\geq|\lambda_{2}|\geq...\geq|\lambda_{h}|\geq 0$. Also define $h^{\prime}$ so that $h^{\prime}=h$ if $\lambda_{h}\neq 0$ and $h^{\prime}=h-1$ if $\lambda_{h}=0$. If $W_{i}$ is the eigenspace of $PQ$ corresponding to the eigenvalue $\lambda_{i}$, and $P_{W_{i}}$ is the projection operator on to $W_{i}$, then

where the final equality holds because for all $i\neq j$,

and since $\lambda_{i}\neq\lambda_{j}$, this implies that $P_{W_{i}}(e_{\sigma_{v}})\cdot P^{-1}P_{W_{j}}(e_{\sigma_{v^{\prime}}})=0$. In order to simplify the terminology,

Let $\zeta_{i}(v\cdot v^{\prime})=P_{W_{i}}(e_{\sigma_{v}})\cdot P^{-1}P_{W_{i}}(e_{\sigma_{v^{\prime}}})$ for all $i$, $v$, and $v^{\prime}$.

Equation (14) is dominated by the $\lambda_{1}^{r+r^{\prime}+1}$ term, so getting good estimate of the $\lambda_{2}^{r+r^{\prime}+1}$ through $\lambda_{h^{\prime}}^{r+r^{\prime}+1}$ terms requires cancelling it out somehow. As a start, if $\lambda_{1}>\lambda_{2}>\lambda_{3}$ then

Note that the left hand side of this expression is equal to $\det{}\begin{vmatrix}N_{r,r^{\prime}[E]}(v\cdot v^{\prime})&N_{r+1,r^{\prime}[E]}(v\cdot v^{\prime})\\ N_{r+1,r^{\prime}[E]}(v\cdot v^{\prime})&N_{r+2,r^{\prime}[E]}(v\cdot v^{\prime})\end{vmatrix}$. More generally, in order to get an expression that can be used to estimate the $\lambda_{i}$ and $\zeta_{i}(v\cdot v^{\prime})$, we consider the determinant of the following.

Let $M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime})$ be the $m\times m$ matrix such that $M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime})_{i,j}=N_{r+i+j,r^{\prime}[E]}(v\cdot v^{\prime})$ for each $i$ and $j$.

To the degree that approximation 8 holds and $c$ is small, each column of $M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime})$ is a linear combination of the vectors

with coefficients that depend only on $\{\lambda_{1},...,\lambda_{h}\}$. So, by linearity of the determinant in one column, $\det(M_{m,r,r^{\prime}[E]}(v\cdot v^{\prime}))$ is a linear combination of these vector’s wedge products with coefficients that are independent of $r$ and $r^{\prime}$. By antisymmetry of wedge products, only the products that use $m$ different such vectors contribute to the determinant, and the products involving the eigenvalues of highest magnitude will dominate. As a result, there exist constants $\gamma(\lambda_{1},...,\lambda_{m})$ and $\gamma^{\prime}(\lambda_{1},...,\lambda_{m})$ such that

if $|\lambda_{m}|=|\lambda_{m+1}|$. In the later case, $\lambda_{m}=-\lambda_{m+1}$, so either $\gamma(\lambda_{1},...,\lambda_{m})\lambda_{m}^{r+r^{\prime}+1}$ and $\gamma^{\prime}(\lambda_{1},...,\lambda_{m})\lambda_{m+1}^{r+r^{\prime}+1}$ have the same sign or $\gamma(\lambda_{1},...,\lambda_{m})\lambda_{m}^{r+r^{\prime}+2}$ and $\gamma^{\prime}(\lambda_{1},...,\lambda_{m})\lambda_{m}^{r+r^{\prime}+2}$ have the same sign. In any of these cases,

This suggests the following algorithm for finding $PQ$’s eigenvalues.

The Basic-Eigenvalue-approximation-algorithm The inputs are $(E,c,v)$, where $v$ is a vertex of the graph, $c\in(0,1)$, and $E$ is a subset of $G$’s edges.

The algorithm ouputs a claim about how many distinct nonzero eigenvalues $PQ$ has and a list of approximations of them.

(1) Compute $N_{r[G\backslash E]}(v)$ for each $r$ until $|N_{r[G\backslash E]}(v)|>\sqrt{n}$, and then set $\lambda_{1}^{\prime\prime}=\sqrt[2r]{n}/(1-c)$.

(2) Set $r=r^{\prime}=\frac{2}{3}\log n/\log((1-c)\lambda^{\prime\prime}_{1})-\sqrt{\ln n}$. Then, compute

until an $m$ is found for which this expression is less than $((1-c)\lambda^{\prime\prime}_{1})^{3/4}+\frac{1}{\sqrt{\ln n}}$. Then, set $h^{\prime\prime}=m-1$.

unless $|\det(M_{i,r+1,r^{\prime}[E]}(v\cdot v^{\prime}))|<\sqrt{|\det(M_{i,r,r^{\prime}[E]}(v\cdot v^{\prime}))|\cdot|\det(M_{i,r+2,r^{\prime}[E]}(v\cdot v^{\prime}))|}$, in which case set

Repeat this for each $i\leq h^{\prime\prime}$

(4) Next, for each $i<h^{\prime\prime}$, if $||\lambda^{\prime}_{i}|-|\lambda^{\prime}_{i+1}||<\frac{1}{\ln n}$ then set $\lambda^{\prime}_{i}=|\lambda^{\prime}_{i}|$ and $\lambda^{\prime}_{i+1}=-|\lambda^{\prime}_{i+1}|$. For each $i\leq h^{\prime\prime}$ such that $||\lambda^{\prime}_{i}|-|\lambda^{\prime}_{i+1}||\geq\frac{1}{\ln n}$ and $||\lambda^{\prime}_{i-1}|-|\lambda^{\prime}_{i}||\geq\frac{1}{\ln n}$ set

(5) Return $(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$

The risk when using this algorithm is that if the set of edges in $v$’s immediate neighborhood is sufficiently atypical it may not work correctly. This can be solved by repeating it for several vertices and taking the median estimates.

The Improved-Eigenvalue-approximation-algorithm The input is $c\in(0,1)$

The algorithm ouputs a claim about how many distinct nonzero eigenvalues $PQ$ has and a list of approximations of them.

(1) Create a set of edges $E$, that each of $G$’s edges is independently assigned to with probability $c$.

(2) Randomly select $\sqrt{\ln n}$ of $G$’s vertices, $v$, $v$,…, $v[\sqrt{\ln n}]$.

(3) Run Basic-Eigenvalue-approximation-algorithm(E,c,v[i]) for each $i\leq\sqrt{\ln n}$, stopping the algorithm prematurely if it takes more than $O(n\sqrt{\ln n})$ time.

(4) Return $(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$ where $h^{\prime\prime}$ and $\lambda_{i}$ are the median outputs of the executions of Basic-Eigenvalue-approximation-algorithm for each $i$.

Now, note that whether or not $|\lambda_{m}|=|\lambda_{m+1}|$, we have

This fact can be used in combination with estimates of $PQ$’s eigenvalues to approximate $\zeta_{i}(v\cdot v^{\prime})$ for arbitrary $v$, $v^{\prime}$, and $i$ as follows.

The algorithm outputs $(z_{1}(v\cdot v^{\prime}),...,z_{h^{\prime\prime}}(v\cdot v^{\prime}))$ such that $z_{i}(v\cdot v^{\prime})\approx\zeta_{i}(v\cdot v^{\prime})$ for all $i$.

(1) For each $i\leq h^{\prime\prime}$, set

(2) Return $(z_{1}(v\cdot v^{\prime}),...,z_{h^{\prime\prime}}(v\cdot v^{\prime}))$.

Of course, this requires $r$ and $r^{\prime}$ to be large enough that

is large relative to the error terms for all $i\leq h^{\prime}$. At a minimum, that requires that $|(1-c)\lambda_{i}|^{r+r^{\prime}+1}=\omega(n)$, so

because otherwise the graph will start running out of vertices before one gets $r$ steps away from $v$ or $r^{\prime}$ steps away from $v^{\prime}$.

Furthermore, for any $v$ and $v^{\prime}$,

with equality for all $i$ if and only if $\sigma_{v}=\sigma_{v^{\prime}}$, so sufficiently good approximations of $\zeta_{i}(v\cdot v),\zeta_{i}(v\cdot v^{\prime})$ and $\zeta_{i}(v^{\prime}\cdot v^{\prime})$ can be used to determine which pairs of vertices are in the same community as follows.

The Vertex-comparison-algorithm. The inputs are $(v,v^{\prime},r,r^{\prime},E,x,c,(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}}))$, where $v,v^{\prime}$ are two vertices, $r,r^{\prime}$ are positive integers, $E$ is a subset of $G$’s edges, $x$ is a positive real number, $c$ is a real number between and $1$, and $(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$ are real numbers.

The algorithm outputs a decision on whether $v$ and $v^{\prime}$ are in the same community or not. It proceeds as follows.

(1) Run Vertex-product-approximation-algorithm(v,v’,r,r’,E,c,$(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$),Vertex-product-approximation-algorithm(v,v,r,r’,E,c,$(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$), and Vertex-product-approximation- algorithm(v’,v’,r,r’,E,c,$(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$).

(2) If $\exists i:z_{i}(v\cdot v)-2z_{i}(v\cdot v^{\prime})+z_{i}(v^{\prime}\cdot v^{\prime})>5(2x(\min p_{j})^{-1/2}+x^{2})$ then conclude that $v$ and $v^{\prime}$ are in different communities. Otherwise, conclude that $v$ and $v^{\prime}$ are in the same community.

One could generate a reasonable classification based solely on this method of comparing vertices (with an appropriate choice of the parameters, as later detailed). However, that would require computing $N_{r,r^{\prime}[E]}(v\cdot v)$ for every vertex in the graph with fairly large $r+r^{\prime}$, which would be slow. Instead, we use the fact that for any vertices $v$, $v^{\prime}$, and $v^{\prime\prime}$ with $\sigma_{v}=\sigma_{v^{\prime}}\neq\sigma_{v^{\prime\prime}}$,

for all $i$, and the inequality is strict for at least one $i$. So, subtracting $\zeta_{i}(v\cdot v)$ from both sides gives us that

for all $i$, and the inequality is still strict for at least one $i$.

So, given a representative vertex in each community, we can determine which of them a given vertex, $v$, is in the same community as without needing to know the value of $\zeta_{i}(v\cdot v)$ as follows.

The Vertex-classification-algorithm. The inputs are $(v[],v^{\prime},r,r^{\prime},E,c,\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}}))$, where $v[]$ is a list of vertices, $v^{\prime}$ is a vertex, $r,r^{\prime}$ are positive integers, $E$ is a subset of $G$’s edges, $c$ is a real number between and $1$, and $(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$ are real numbers. It is assumed that $z_{i}(v[\sigma]\cdot v[\sigma])$ has already been computed for each $i$ and $\sigma$.

The algorithm is supposed to output $\sigma$ such that $v^{\prime}$ is in the same community as $v[\sigma]$. It works as follows.

(1) Run Vertex-product-approximation-algorithm($v[\sigma]$,v’,r,r’,E,c,$(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$) for each $\sigma$.

(2) Find a $\sigma$ that minimizes the value of

and conclude that $v^{\prime}$ is in the same community as $v[\sigma]$.

This runs fairly quickly if $r$ is large and $r^{\prime}$ is small because the algorithm only requires focusing on $N_{r^{\prime}}(v^{\prime})$ vertices. This leads to the following plan for partial recovery. First, randomly select a set of vertices that is large enough to contain at least one vertex from each community with high probability. Next, compare all of the selected vertices in an attempt to determine which of them are in the same communities. Then, pick one anchor vertex in each community. After that, use the algorithm above to attempt to determine which community each of the remaining vertices is in. As long as there actually was at least one vertex from each community in the initial set and none of the approximations were particularly bad, this should give a reasonably accurate classification.

The Unreliable-graph-classification-algorithm. The inputs are $(G,c,m,\epsilon,x,(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}}))$, where $G$ is a graph, $c$ is a real number between and $1$, $m$ is a positive integer, $\epsilon$ is a real number between and $1$, $x$ is a positive real number, and $(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$ are real numbers.

The algorithm outputs an alleged list of communities for $G$. It works as follows.

(1) Randomly assign each edge in $G$ to $E$ independently with probability $c$.

(2) Randomly select $m$ vertices in $G$, $v,...,v[m-1]$.

(3) Set $r=(1-\frac{\epsilon}{3})\log n/\log((1-c)\lambda^{\prime}_{1})-\sqrt{\ln n}$ and $r^{\prime}=\frac{2\epsilon}{3}\cdot\log n/\log((1-c)\lambda^{\prime}_{1})$

(4) Compute $N_{r^{\prime\prime}[G\backslash E]}(v[i])$ for each $r^{\prime\prime}<r+2h^{\prime\prime}+3$ and $0\leq i<m$.

(5) Run vertex-comparison-algorithm(v[i],v[j],r,r’,E,x,$(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$) for every $i$ and $j$

(6) If these give consistent results, randomly select one alleged member of each community $v^{\prime}[\sigma]$. Otherwise, fail.

(7) For every $v^{\prime\prime}$ in the graph, compute $N_{r^{\prime\prime}[G\backslash E]}(v^{\prime\prime})$ for each $r^{\prime\prime}\leq r^{\prime}$. Then, run Vertex-classification-algorithm(v’[],v”, r,r’,E,$(\lambda^{\prime}_{1},...,\lambda^{\prime}_{h^{\prime\prime}})$) in order to get a hypothesized classification of $v^{\prime\prime}$

The risk that this randomly gives a bad classification due to a bad set of initial vertices can be mitigated as follows. First, repeat the previous classification procedure several times. Assuming that the procedure gives a good classification more often than not, the good classifications should comprise a set that contains more than half the classifications and which has fairly little difference between any two elements of the set. Furthermore, any such set would have to contain at least one good classification, so none of its elements could be too bad. So, find such a set and average its classifications together.

So, the overall Agnostic-sphere-comparison-algorithm starts by estimating $PQ$’s eigenvalues. Then, it uses those estimates to pick appropriate values of $x$ and $\epsilon$ for the Unreliable-graph-classification-algorithm. Finally, it runs it several times and combines the resulting classifications as explained above. The only inputs it requires are the graph itself and some $\delta>0$ such that $p_{i}\geq\delta$ for all $i$.