A Tensor Approach to Learning Mixed Membership Community Models

Community detection, spectral methods, tensor methods, moment-based estimation, mixed membership models.

Introduction

Studying communities forms an integral part of social network analysis. A community generally refers to a group of individuals with shared interests (e.g. music, sports), or relationships (e.g. friends, co-workers). Community formation in social networks has been studied by many sociologists, e.g. (Moreno, 1934; Lazarsfeld et al., 1954; McPherson et al., 2001; Currarini et al., 2009), starting with the seminal work of Moreno (1934). They posit various factors such as homophilyThe term homophily refers to the tendency that individuals belonging to the same community tend to connect more than individuals in different communities. among the individuals to be responsible for community formation. Various probabilistic and non-probabilistic network models attempt to explain community formation. In addition, they also attempt to quantify interactions and the extent of overlap between different communities, relative sizes among the communities, and various other network properties. Studying such community models are also of interest in other domains, e.g. in biological networks.

While there exists a vast literature on community models, learning these models is typically challenging, and various heuristics such as Markov Chain Monte Carlo (MCMC) or variational expectation maximization (EM) are employed in practice. Such heuristics tend to scale poorly for large networks. On the other hand, community models with guaranteed learning methods tend to be restrictive. A popular class of probabilistic models, termed as stochastic blockmodels, have been widely studied and enjoy strong theoretical learning guarantees, e.g. (White et al., 1976; Holland et al., 1983; Fienberg et al., 1985; Wang and Wong, 1987; Snijders and Nowicki, 1997; McSherry, 2001). On the other hand, they posit that an individual belongs to a single community, which does not hold in most real settings (Palla et al., 2005).

In this paper, we consider a class of mixed membership community models, originally introduced by Airoldi et al. (2008), and recently employed by Xing et al. (2010) and Gopalan et al. (2012). The model has been shown to be effective in many real-world settings, but so far, no learning approach exists with provable guarantees. In this paper, we provide a novel learning approach for learning these mixed membership models and prove that these methods succeed under a set of sufficient conditions.

The mixed membership community model of Airoldi et al. (2008) has a number of attractive properties. It retains many of the convenient properties of the stochastic block model. For instance, conditional independence of the edges is assumed, given the community memberships of the nodes in the network. At the same time, it allows for communities to overlap, and for every individual to be fractionally involved in different communities. It includes the stochastic block model as a special case (corresponding to zero overlap among the different communities). This enables us to compare our learning guarantees with existing works for stochastic block models and also study how the extent of overlap among different communities affects the learning performance.

We now summarize the main contributions of this paper. We propose a novel approach for learning mixed membership community models of Airoldi et al. (2008). Our approach is a method of moments estimator and incorporates tensor spectral decomposition. We provide guarantees for our approach under a set of sufficient conditions. Finally, we compare our results to existing ones for the special case of the stochastic block model, where nodes belong to a single community.

We present a tensor-based approach for learning the mixed membership stochastic block model (MMSB) proposed by Airoldi et al. (2008). In the MMSB model, the community membership vectors are drawn from the Dirichlet distribution, denoted by $\operatorname{Dir}(\alpha)$, where $\alpha$ is known the Dirichlet concentration vector. Employing the Dirichlet distribution results in sparse community memberships in certain regimes of $\alpha$, which is realistic. The extent of overlap between different communities under the MMSB model is controlled (roughly) via a single scalar parameter, $\alpha_{0}:=\sum_{i}\alpha_{i}$, where $\alpha:=[\alpha_{i}]$ is the Dirichlet concentration vector. When $\alpha_{0}\to 0$, the mixed membership model degenerates to a stochastic block model and we have non-overlapping communities.

We propose a unified tensor-based learning method for the MMSB model and establish recovery guarantees under a set of sufficient conditions. These conditions are in in terms of the network size $n$, the number of communities $k$, extent of community overlaps (through $\alpha_{0}$), and the average edge connectivity across various communities. Below, we present an overview of our guarantees for the special case of equal sized communities (each of size $n/k$) and homogeneous community connectivity: let $p$ be the probability for any intra-community edge to occur, and $q$ be the probability for any inter-community edge. Let $\Pi$ be the community membership matrix, where $\Pi^{(i)}$ denotes the $i^{{\mbox{\tiny th}}}$ row, which is the vector of membership weights of the nodes for the $i^{{\mbox{\tiny th}}}$ community. Let $P$ be the community connectivity matrix such that $P(i,i)=p$ and $P(i,j)=q$ for $i\neq j$.

our estimated community membership matrix $\hat{\Pi}$ and the edge connectivity matrix $\hat{P}$ satisfy with high probability (w.h.p.)

Further, our support estimates $\hat{S}$ satisfy w.h.p.,

where $\Pi$ is the true community membership matrix and the threshold is chosen as $\xi=\Omega(\epsilon_{P})$.

The complete details are in Section 4. We first provide some intuitions behind the sufficient conditions in (1). We require the network size $n$ to be large enough compared to the number of communities $k$, and for the separation $p-q$ to be large enough, so that the learning method can distinguish the different communities. This is natural since a zero separation $(p=q)$ implies that the communities are indistinguishable. Moreover, we see that the scaling requirements become more stringent as $\alpha_{0}$ increases. This is intuitive since it is harder to learn communities with more overlap, and we quantify this scaling. For the Dirichlet distribution, it can be shown that the number of “significant” entries is roughly $O(\alpha_{0})$ with high probability, and in many settings of practical interest, nodes may have significant memberships in only a few communities, and thus, $\alpha_{0}$ is a constant (or growing slowly) in many instances.

In addition, we quantify the error bounds for estimating various parameters of the mixed membership model in (2) and (3). These errors decay under the sufficient conditions in (1). Lastly, we establish zero-error guarantees for support recovery in (4): our learning method correctly identifies (w.h.p) all the significant memberships of a node and also identifies the set of communities where a node does not have a strong presence, and we quantify the threshold $\xi$ in Theorem 1.1. Further, we present the results for a general (non-homogeneous) MMSB model in Section 4.2.

A byproduct of our analysis yields novel identifiability results for the MMSB model based on low order graph moments. We establish that the MMSB model is identifiable, given access to third order moments in the form of counts of $3$-star subgraphs, i.e. a star subgraph consisting of three leaves, for each triplet of leaves, when the community connectivity matrix $P$ is full rank. Our learning approach involves decomposition of this third order tensor. Previous identifiability results required access to high order moments and were limited to the stochastic block model setting; see Section 1.3 for details.

Our results have implications for learning stochastic block models, which is a special case of the MMSB model with $\alpha_{0}\to 0$. In this case, the sufficient conditions in (1) reduce to

The scaling requirements in (5) match with the best known boundsThere are many methods which achieve the best known scaling for $n$ in (5), but have worse scaling for the separation $p-q$. This includes variants of the spectral clustering method, e.g. Chaudhuri et al. (2012). See Chen et al. (2012) for a detailed comparison. (up to poly-log factors) for learning uniform stochastic block models and were previously achieved by Chen et al. (2012) via convex optimization involving semi-definite programming (SDP). In contrast, we propose an iterative non-convex approach involving tensor power iterations and linear algebraic techniques, and obtain similar guarantees. For a detailed comparison of learning guarantees under various methods for learning (homogeneous) stochastic block models, see Chen et al. (2012).

Thus, we establish learning guarantees explicitly in terms of the extent of overlap among the different communities for general MMSB models. Many real-world networks involve sparse community memberships and the total number of communities is typically much larger than the extent of membership of a single individual, e.g. hobbies/interests of a person, university/company networks that a person belongs to, the set of transcription factors regulating a gene, and so on. Thus, we see that in this regime of practical interest, where $\alpha_{0}=\Theta(1)$, the scaling requirements in (1) match those for the stochastic block model in (5) (up to polylog factors) without any degradation in learning performance. Thus, we establish that learning community models with sparse community memberships is akin to learning stochastic block models and we present a unified approach and analysis for learning these models.

To the best of our knowledge, this work is the first to establish polynomial time learning guarantees for probabilistic network models with overlapping communities and we provide a fast and an iterative learning approach through linear algebraic techniques and tensor power iterations. While the results of this paper are mostly limited to a theoretical analysis of the tensor method for learning overlapping communities, we note recent results which show that this method (with improvements and modifications) is very accurate in practice on real datasets from social networks, and is scalable to graphs with millions of nodes (Huang et al., 2013).

2 Overview of Techniques

We now describe the main techniques employed in our learning approach and in establishing the recovery guarantees.

We propose an efficient learning algorithm based on low order moments, viz., counts of small subgraphs. Specifically, we employ a third-order tensor which counts the number of $3$-stars in the observed network. A $3$-star is a star graph with three leaves (see figure 1) and we count the occurrences of such $3$-stars across different partitions. We establish that (an adjusted) $3$-star count tensor has a simple relationship with the model parameters, when the network is drawn from a mixed membership model. We propose a multi-linear transformation using edge-count matrices (also termed as the process of whitening), which reduces the problem of learning mixed membership models to the canonical polyadic (CP) decomposition of an orthogonal symmetric tensor, for which tractable decomposition exists, as described below. Note that the decomposition of a general tensor into its rank-one components is referred to as its CP decomposition (Kolda and Bader, 2009) and is in general NP-hard (Hillar and Lim, 2012). However, the decomposition is tractable in the special case of an orthogonal symmetric tensor considered here.

Our tensor decomposition method is based on the popular power iterations (e.g. see Anandkumar et al. (2012a)). It is a simple iterative method to compute the stable eigen-pairs of a tensor. In this paper, we propose various modifications to the basic power method to strengthen the recovery guarantees under perturbations. For instance, we introduce adaptive deflation techniques (which involves subtracting out the eigen-pairs previously estimated). Moreover, we initialize the tensor power method with (whitened) neighborhood vectors from the observed network, as opposed to random initialization. In the regime, where the community overlaps are small, this leads to an improved performance. Additionally, we incorporate thresholding as a post-processing operation, which again, leads to improved guarantees for sparse community memberships, i.e., when the overlap among different communities is small. We theoretically establish that all these modifications lead to improvement in performance guarantees and we discuss comparisons with the basic power method in Section 4.4.

We establish that our learning approach correctly recovers the model parameters and the community memberships of all nodes under exact moments. We then carry out a careful analysis of the empirical graph moments, computed using the network observations. We establish tensor concentration bounds and also control the perturbation of the various quantities used by our learning algorithm via matrix Bernstein’s inequality (Tropp, 2012, thm. 1.4) and other inequalities. We impose the scaling requirements in (1) for various concentration bounds to hold.

3 Related Work

There is extensive work on modeling communities and various algorithms and heuristics for discovering them. We mostly limit our focus to works with theoretical guarantees.

The method of moments approach dates back to Pearson (1894) and has been applied for learning various community models. Here, the moments correspond to counts of various subgraphs in the network. They typically consist of aggregate quantities, e.g., number of star subgraphs, triangles etc. in the network. For instance, Bickel et al. (2011) analyze the moments of a stochastic block model and establish that the subgraph counts of certain structures, termed as “wheels” (a family of trees), are sufficient for identifiability under some natural non-degeneracy conditions. In contrast, we establish that moments up to third order (corresponding to edge and $3$-star counts) are sufficient for identifiability of the stochastic block model, and also more generally, for the mixed membership Dirichlet model. We employ subgraph count tensors, corresponding to the number of subgraphs (such as stars) over a set of labeled vertices, while the work of Bickel et al. (2011) considers only aggregate (i.e. scalar) counts. Considering tensor moments allows us to use simple subgraphs (edges and $3$ stars) corresponding to low order moments, rather than more complicated graphs (e.g. wheels considered by Bickel et al. (2011)) with larger number of nodes, for learning the community model.

The method of moments is also relevant for the family of random graph models termed as exponential random graph models (Holland and Leinhardt, 1981; Frank and Strauss, 1986). Subgraph counts of fixed graphs such as stars and triangles serve as sufficient statistics for these models. However, parameter estimation given the subgraph counts is in general NP-hard, due to the normalization constant in the likelihood (the partition function) and the model suffers from degeneracy issues; see Rinaldo et al. (2009); Chatterjee and Diaconis (2011) for detailed discussion. In contrast, we establish in this paper that the mixed membership model is amenable to simple estimation methods through linear algebraic operations and tensor power iterations using subgraph counts of $3$-stars.

Many algorithms provide learning guarantees for stochastic block models. For a detailed comparison of these methods, see the recent work by Chen et al. (2012). A popular method is based on spectral clustering (McSherry, 2001), where community memberships are inferred through projection onto the spectrum of the Laplacian matrix (or its variants). This method is fast and easy to implement (via singular value decomposition). There are many variants of this method, e.g. the work of Chaudhuri et al. (2012) employs normalized Laplacian matrix to handle degree heterogeneities. In contrast, the work of Chen et al. (2012) uses convex optimization techniques via semi-definite programming learning block models. For a detailed comparison of learning guarantees under various methods for learning stochastic block models, see Chen et al. (2012).

The classical approach to community detection tries to directly exploit the properties of the graph to define communities, without assuming a probabilistic model. Girvan and Newman (2002) use betweenness to remove edges until only communities are left. However, Bickel and Chen (2009) show that these algorithms are (asymptotically) biased and that using modularity scores can lead to the discovery of an incorrect community structure, even for large graphs. Jalali et al. (2011) define community structure as the structure that satisfies the maximum number of edge constraints (whether two individuals like/dislike each other). However, these models assume that every individual belongs to a single community.

Recently, some non-probabilistic approaches have been introduced with overlapping community models by Arora et al. (2012) and Balcan et al. (2012). The analysis of Arora et al. (2012) is mostly limited to dense graphs (i.e. $\Theta(n^{2})$ edges for a $n$ node graph), while our analysis provides learning guarantees for much sparser graphs (as seen by the scaling requirements in (1)). Moreover, the running time of the method of Arora et al. (2012) is quasipolynomial time (i.e. $O(n^{\log n})$) for the general case, and is based on a combinatorial learning approach. In contrast, our learning approach is based on simple linear algebraic techniques and the running time is a low-order polynomial (roughly it is $O(n^{2}k)$ for a $n$ node network with $k$ communities under a serial computation model and $O(n+k^{3})$ under a parallel computation model). The work of Balcan et al. (2012) assumes endogenously formed communities, by constraining the fraction of edges within a community compared to the outside. They provide a polynomial time algorithm for finding all such “self-determined” communities and the running time is $n^{O(\log 1/\alpha)/\alpha}$, where $\alpha$ is the fraction of edges within a self-determined community, and this bound is improved to linear time when $\alpha>1/2$. On the other hand, the running time of our algorithm is mostly independent of the parameters of the assumed model, (and is roughly $O(n^{2}k)$). Moreover, both these works are limited to homophilic models, where there are more edges within each community, than between any two different communities. However, our learning approach is not limited to this setting and also does not assume homogeneity in edge connectivity across different communities (but instead it makes probabilistic assumptions on community formation). In addition, we provide improved guarantees for homophilic models by considering additional post-processing steps in our algorithm. Recently, Abraham et al. (2012) provide an algorithm for approximating the parameters of an Euclidean log-linear model in polynomial time. However, there setting is considerably different than the one in this paper.

Inhomogeneous random graphs have been analyzed in a variety of settings (e.g., Bollobás et al. (2007); Lovász (2009)) and are generalizations of the stochastic block model. Here, the probability of an edge between any two nodes is characterized by a general function (rather than by a $k\times k$ matrix as in the stochastic block model with $k$ blocks). Note that the mixed membership model considered in this work is a special instance of this general framework. These models arise as the limits of convergent (dense) graph sequences and for this reason, the functions are also termed as “graphons” or graph limits (Lovász, 2009). A deep result in this context is the regularity lemma and its variants. The weak regularity lemma proposed by Frieze and Kannan (1999), showed that any convergent dense graph can be approximated by a stochastic block model. Moreover, they propose an algorithm to learn such a block model based on the so-called $d_{2}$ distance. The $d_{2}$ distance between two nodes measures similarity with respect to their “two-hop” neighbors and the block model is obtained by thresholding the $d_{2}$ distances. However, the method is limited to learning block models and not overlapping communities.

The community models considered in this paper are closely related to the probabilistic topic models (Blei, 2012), employed for text modeling and document categorization. Topic models posit the occurrence of words in a corpus of documents, through the presence of multiple latent topics in each document. Latent Dirichlet allocation (LDA) is perhaps the most popular topic model, where the topic mixtures are assumed to be drawn from the Dirichlet distribution. In each document, a topic mixture is drawn from the Dirichlet distribution, and the words are drawn in a conditional independent manner, given the topic mixture. The mixed membership community model considered in this paper can be interpreted as a generalization of the LDA model, where a node in the community model can function both as a document and a word. For instance, in the directed community model, when the outgoing links of a node are considered, the node functions as a document, and its outgoing neighbors can be interpreted as the words occurring in that document. Similarly, when the incoming links of a node in the network are considered, the node can be interpreted as a word, and its incoming links, as documents containing that particular word. In particular, we establish that certain graph moments under the mixed membership model have similar structure as the observed word moments under the LDA model. This allows us to leverage the recent developments from Anandkumar et. al. (Anandkumar et al., 2012c, a, b) for learning topic models, based on the method of moments. These works establish guaranteed learning using second- and third-order observed moments through linear algebraic and tensor-based techniques. In particular, in this paper, we exploit the tensor power iteration method of Anandkumar et al. (2012b), and propose additional improvements to obtain stronger recovery guarantees. Moreover, the sample analysis is quite different (and more challenging) in the community setting, compared to topic models analyzed in Anandkumar et al. (2012c, a, b). We clearly spell out the similarities and differences between the community model and other latent variable models in Section 4.4.

The work of Feldman et al. (2012) provides lower bounds on the complexity of statistical algorithms, and shows that for cliques of size $O(n^{1/2-\delta})$, for any constant $\delta>0$, at least $n^{\Omega(\log\log n)}$ queries are needed to find the cliques. There are works relating the hardness of finding hidden cliques and the use of higher order moment tensors for this purpose. Frieze and Kannan (2008) relate the problem of finding a hidden clique to finding the top eigenvector of the third order tensor, corresponding to the maximum spectral norm. Brubaker and Vempala (2009) extend the result to arbitrary $r^{{\mbox{\tiny th}}}$-order tensors and the cliques have to be size $\Omega(n^{1/r})$ to enable recovery from $r^{{\mbox{\tiny th}}}$-order moment tensors in a $n$ node network. However, this problem (finding the top eigenvector of a tensor) is known to be NP-hard in general (Hillar and Lim, 2012). Thus, tensors are useful for finding smaller hidden cliques in network (albeit by solving a computationally hard problem). In contrast, we consider tractable tensor decomposition through reduction to orthogonal tensors (under the scaling requirements of (1)), and our learning method is a fast and an iterative approach based on tensor power iterations and linear algebraic operations. Mossel et al. (2012) provide lower bounds on the separation $p-q$, the edge connectivity between intra-community and inter-community, for identifiability of communities in stochastic block models in the sparse regime (when $p,q\sim n^{-1}$), when the number of communities is a constant $k=O(1)$. Our method achieves the lower bounds on separation of edge connectivity up to poly-log factors.

Another class of approaches for learning MMSB models are based on optimizing the observed likelihood. Traditional approaches such as Gibbs sampling or expectation maximization (EM) can be too expensive apply in practice for MMSB models. Variational approaches which optimize the so-called evidence lower bound (Hoffman et al., 2012; Gopalan et al., 2012), which is a lower bound on the marginal likelihood of the observed data (typically by applying a mean-field approximation), are efficient for practical implementation. Stochastic versions of the variational approach provide even further gains in efficiency and are state-of-art practical learning methods for MMSB models (Gopalan et al., 2012). However, these methods lack theoretical guarantees; since they optimize a bound on the likelihood, they are not guaranteed to recover the underlying communities consistently. A recent work (Celisse et al., 2012) establishes consistency of maximum likelihood and variational estimators for stochastic block models, which are special cases of the MMSB model. However, it is not known if the results extend to general MMSB models. Moreover, the framework of Celisse et al. (2012) assumes a fixed number of communities and growing network size, and provide only asymptotic consistency guarantees. Thus, they do not allow for high-dimensional settings, where the parameters of the learning problem also grow as the observed dimensionality grows. In contrast, in this paper, we allow for the number of communities to grow, and provide precise constraints on the scaling bounds for consistent estimation under finite samples. It is an open problem to obtain such bounds for maximum likelihood and variational estimators. On the practical side, a recent work deploying the tensor approach proposed in this paper by Huang et al. (2013) shows that the tensor approach is more than an order of magnitude faster in recovering the communities than the variational approach, is scalable to networks with millions of nodes, and also has better accuracy in recovering the communities.

Community Models and Graph Moments

In this section, we describe the mixed membership community model based on Dirichlet priors for the community draws by the individuals. We first introduce the special case of the popular stochastic block model, where each node belongs to a single community.

In this model, each individual is independently assigned to a single community, chosen at random: each node $i$ chooses community $j$ independently with probability $\widehat{\alpha}_{j}$, for $i\in[n],j\in[k]$, and we assign $\pi_{i}=e_{j}$ in this case, where $e_{j}\in\{0,1\}^{k}$ is the $j^{{\mbox{\tiny th}}}$ coordinate basis vector. Given the community assignments $\Pi$, every directedWe limit our discussion to directed networks in this paper, but note that the results also hold for undirected community models, where $P$ is a symmetric matrix, and an edge $(u,v)$ is formed with probability $\pi_{u}^{\top}P\pi_{v}=\pi_{v}^{\top}P\pi_{u}$. edge in the network is independently drawn: if node $u$ is in community $i$ and node $v$ is in community $j$ (and $u\neq v$), then the probability of having the edge $(u,v)$ in the network is $P_{i,j}$. Here, $P\in^{k\times k}$ and we refer to it as the community connectivity matrix. This implies that given the community membership vectors $\pi_{u}$ and $\pi_{v}$, the probability of an edge from $u$ to $v$ is $\pi_{u}^{\top}P\pi_{v}$ (since when $\pi_{u}=e_{i}$ and $\pi_{v}=e_{j}$, we have $\pi_{u}^{\top}P\pi_{v}=P_{i,j}$.). The stochastic model has been extensively studied and can be learnt efficiently through various methods, e.g. spectral clustering (McSherry, 2001), convex optimization (Chen et al., 2012). and so on. Many of these methods rely on conditional independence assumptions of the edges in the block model for guaranteed learning.

We now consider the extension of the stochastic block model which allows for an individual to belong to multiple communities and yet preserves some of the convenient independence assumptions of the block model. In this model, the community membership vector $\pi_{u}$ at node $u$ is a probability vector, i.e., $\sum_{i\in[k]}\pi_{u}(i)=1$, for all $u\in[n]$. Given the community membership vectors, the generation of the edges is identical to the block model: given vectors $\pi_{u}$ and $\pi_{v}$, the probability of an edge from $u$ to $v$ is $\pi_{u}^{\top}P\pi_{v}$, and the edges are independently drawn. This formulation allows for the nodes to be in multiple communities, and at the same time, preserves the conditional independence of the edges, given the community memberships of the nodes.

where $\Gamma(\cdot)$ is the Gamma function and the ratio of the Gamma function serves as the normalization constant.

The Dirichlet distribution is widely employed for specifying priors in Bayesian statistics, e.g. latent Dirichlet allocation (Blei et al., 2003). The Dirichlet distribution is the conjugate prior of the multinomial distribution which makes it attractive for Bayesian inference.

The stochastic block model is a limiting case of the mixed membership model when the Dirichlet parameter is $\alpha=\alpha_{0}\cdot\widehat{\alpha}$, where the probability vector $\widehat{\alpha}$ is held fixed and $\alpha_{0}\to 0$. In the other extreme when $\alpha_{0}\to\infty$, the Dirichlet distribution becomes peaked around a single point, for instance, if $\alpha_{i}\equiv c$ and $c\to\infty$, the Dirichlet distribution is peaked at $k^{-1}\cdot\vec{1}$, where $\vec{1}$ is the all-ones vector. Thus, the parameter $\alpha_{0}$ serves as a measure of the average sparsity of the Dirichlet draws or equivalently, of how concentrated the Dirichlet measure is along the different coordinates. This in effect, controls the extent of overlap among different communities.

When the Dirichlet parameter vector satisfiesThe assumption that the Dirichlet distribution be in the sparse regime is not strictly needed. Our results can be extended to general Dirichlet distributions, but with worse scaling requirements on the network size $n$ for guaranteed learning. $\alpha_{i}<1$, for all $i\in[k]$, the Dirichlet distribution $\operatorname{Dir}(\alpha)$ generates “sparse” vectors with high probabilityRoughly the number of entries in $\pi$ exceeding a threshold $\tau$ is at most $O(\alpha_{0}\log(1/\tau))$ with high probability, when $\pi\sim\operatorname{Dir}(\alpha)$.; see Telgarsky (2012) (and in the extreme case of the block model where $\alpha_{0}\to 0$, it generates $1$-sparse vectors). Many real-world settings involve sparse community membership and the total number of communities is typically much larger than the extent of membership of a single individual, e.g. hobbies/interests of a person, university/company networks that a person belongs to, the set of transcription factors regulating a gene, and so on. Our learning guarantees are limited to the sparse regime of the Dirichlet model.

2 Graph Moments Under Mixed Membership Models

Our approach for learning a mixed membership community model relies on the form of the graph momentsWe interchangeably use the term first order moments for edge counts and third order moments for $3$-star counts. under the mixed membership model. We now describe the specific graph moments used by our learning algorithm (based on $3$-star and edge counts) and provide explicit forms for the moments, assuming draws from a mixed membership model.

Recall that $G$ denotes the adjacency matrix and that $G_{X,A}$ denotes the submatrix corresponding to edges going from $X$ to $A$. Recall that $P\in^{k\times k}$ denotes the community connectivity matrix. Define

Our learning algorithm uses moments up to the third-order, represented as a tensor. A third-order tensor $T$ is a three-dimensional array whose $(p,q,r)$-th entry denoted by $T_{p,q,r}$. The symbol $\otimes$ denotes the standard Kronecker product: if $u$, $v$, $w$ are three vectors, then

A tensor of the form $u\otimes v\otimes w$ is referred to as a rank-one tensor. The decomposition of a general tensor into a sum of its rank-one components is referred to as canonical polyadic (CP) decomposition Kolda and Bader (2009). We will subsequently see that the graph moments can be expressed as a tensor and that the CP decomposition of the graph-moment tensor yields the model parameters and the community vectors under the mixed membership community model.

2.1 Graph moments under Stochastic Block Model

We first analyze the graph moments in the special case of a stochastic block model (i.e., $\alpha_{0}=\sum_{i}\alpha_{i}\to 0$ in the Dirichlet prior in (6)) and then extend it to general mixed membership model. We provide explicit expressions for the graph moments corresponding to edge counts and $3$-star counts. We later establish in Section 3 that these moments are sufficient to learn the community memberships of the nodes and the model parameters of the block model.

The primary quantity of interest is a third-order tensor which counts the number of $3$-stars. A $3$-star is a star graph with three leaves $\{a,b,c\}$ and we refer to the internal node $x$ of the star as its “head”, and denote the structure by $x\rightarrow\{a,b,c\}$ (see figure 1). We partition the network into fourFor sample complexity analysis, we require dividing the graph into more than four partitions to deal with statistical dependency issues, and we outline it in Section 3. parts and consider $3$-stars such that each node in the $3$-star belongs to a different partition. This is necessary to obtain a simple form of the moments, based on the conditional independence assumptions of the block model, see Proposition 2.1. Specifically, considerTo establish our theoretical guarantees, we assume that the partitions $A,B,C,X$ are randomly chosen and are of size $\Theta(n)$. a partition $A,B,C,X$ of the network. We count the number of $3$-stars from $X$ to $A,B,C$ and our quantity of interest is

which is the normalized count of the number of $3$-stars with leaves $a,b,c$ such that its “head” is in set $X$.

We now relate the tensor $\operatorname{T}_{X\rightarrow\{A,B,C\}}$ to the parameters of the stochastic block model, viz., the community connectivity matrix $P$ and the community probability vector $\widehat{\alpha}$, where $\widehat{\alpha}_{i}$ is the probability of choosing community $i$.

Given partitions $A,B,C,X$, and $F:=\Pi^{\top}P^{\top}$, where $P$ is the community connectivity matrix and $\Pi$ is the matrix of community membership vectors, we have

where $\widehat{\alpha}_{i}$ is the probability for a node to select community $i$.

Note the form of the $3$-star count tensor $\operatorname{T}$ in (12). It provides a CP decomposition of $\operatorname{T}$ since each term in the summation, viz., $\widehat{\alpha}_{i}(F_{A})_{i}\otimes(F_{B})_{i}\otimes(F_{C})_{i}$, is a rank one tensor. Thus, we can learn the matrices $F_{A},F_{B},F_{C}$ and the vector $\widehat{\alpha}$ through CP decomposition of tensor $\operatorname{T}$. Once these parameters are learnt, learning the communities is straight-forward under exact moments: by exploiting (11), we find $\Pi_{X}$ as

Similarly, we can consider another tensor consisting of $3$-stars from $A$ to $X,B,C$, and obtain matrices $F_{X},F_{B}$ and $F_{C}$ through a CP decomposition, and so on. Once we obtain matrices $F$ and $\Pi$ for the entire set of nodes in this manner, we can obtain the community connectivity matrix $P$, since $F:=\Pi^{\top}P^{\top}$. Thus, in principle, we are able to learn all the model parameters ($\widehat{\alpha}$ and $P$) and the community membership matrix $\Pi$ under the stochastic block model, given exact moments. This establishes identifiability of the model given moments up to third order and forms a high-level approach for learning the communities. When only samples are available, we establish that the empirical versions are close to the exact moments considered above, and we modify the basic learning approach to obtain robust guarantees. See Section 3 for details.

The main property exploited in proving the tensor form in (12) is the conditional-independence assumption under the stochastic block model: the realization of the edges in each $3$-star, say in $x\rightarrow\{a,b,c\}$, is conditionally independent given the community membership vector $\pi_{x}$, when $x\neq a\neq b\neq c$. This is because the community membership vectors $\Pi$ are assumed to be drawn independently at the different nodes and the edges are drawn independently given the community vectors. Considering $3$-stars from $X$ to $A,B,C$ where $X,A,B,C$ form a partition ensures that this conditional independence is satisfied for all the $3$-stars in tensor $\operatorname{T}$.

Proof: Recall that the probability of an edge from $u$ to $v$ given $\pi_{u},\pi_{v}$ is

The equation follows from the conditional-independence assumption of the edges (assuming $a\neq b\neq c$). Now taking expectation over the nodes in $X$, we have

where the last step follows from the fact that $\pi=e_{j}$ with probability $\widehat{\alpha}_{j}$ and the result holds when $x\neq a,b,c$. Recall that $(F_{a})_{j}$ denotes the $j^{{\mbox{\tiny th}}}$ column of $F_{a}$ (since $F_{a}e_{j}=(F_{a})_{j}$). Collecting all the elements of the tensor, we obtain the desired result. $\Box$

2.2 Graph Moments under Mixed Membership Dirichlet Model

We now analyze the graph moments for the general mixed membership Dirichlet model. Instead of the raw moments (i.e. edge and $3$-star counts), we consider modified moments to obtain similar expressions as in the case of the stochastic block model.

We now define a modified adjacency matrixTo compute the modified moments $G^{\alpha_{0}}$, and $\operatorname{T}^{\alpha_{0}}$, we need to know the value of the scalar $\alpha_{0}:=\sum_{i}\alpha_{i}$, which is the concentration parameter of the Dirichlet distribution and is a measure of the extent of overlap between the communities. We assume its knowledge here. $G_{X,A}^{\alpha_{0}}$ as

In the special case of the stochastic block model $(\alpha_{0}\to 0)$, $G_{X,A}^{\alpha_{0}}=G_{X,A}$ is the submatrix of the adjacency matrix $G$. Similarly, we define modified third-order statistics,

and it reduces to (a scaled version of) the $3$-star count $\operatorname{T}_{X\rightarrow\{A,B,C\}}$ defined in (9) for the stochastic block model $(\alpha_{0}\to 0)$. The modified adjacency matrix and the $3$-star count tensor can be viewed as a form of “centering” of the raw moments which simplifies the expressions for the moments. The following relationships hold between the modified graph moments $G^{\alpha_{0}}_{X,A}$, $\operatorname{T}^{\alpha_{0}}$ and the model parameters $P$ and $\widehat{\alpha}$ of the mixed membership model.

Given partitions $A,B,C,X$ and $G^{\alpha_{0}}_{X,A}$ and $\operatorname{T}^{\alpha_{0}}$, as in (14) and (15), normalized Dirichlet concentration vector $\widehat{\alpha}$, and $F:=\Pi^{\top}P^{\top}$, where $P$ is the community connectivity matrix and $\Pi$ is the matrix of community memberships, we have

where $(F_{A})_{i}$ corresponds to $i^{{\mbox{\tiny th}}}$ column of $F_{A}$ and $\Psi_{X}$ relates to the community membership matrix $\Pi_{X}$ as

Recall that $\alpha_{0}$ quantifies the extent of overlap among the communities. The computation of the modified moment $T^{\alpha_{0}}$ requires the knowledge of $\alpha_{0}$, which is assumed to be known. Since this is a scalar quantity, in practice, we can easily tune this parameter via cross validation.

On lines of the proof of Proposition 2.1 for the block model, the expectation in (17) involves multi-linear map of the expectation of the tensor products $\pi\otimes\pi\otimes\pi$ among other terms. Collecting these terms, we have that

is a diagonal tensor, in the sense that its $(p,p,p)$-th entry is $\widehat{\alpha}_{p}$, and its $(p,q,r)$-th entry is 0 when $p,q,r$ are not all equal. With this, we have (17). $\Box$

Note the nearly identical forms of the graph moments for the stochastic block model in (11), (12) and for the general mixed membership model in (16), (17). In other words, the modified moments $G^{\alpha_{0}}_{X,A}$ and $\operatorname{T}^{\alpha_{0}}$ have similar relationships to underlying parameters as the raw moments in the case of the stochastic block model. This enables us to use a unified learning approach for the two models, outlined in the next section.

Algorithm for Learning Mixed Membership Models

The simple form of the graph moments derived in the previous section is now utilized to recover the community vectors $\Pi$ and model parameters $P,\widehat{\alpha}$ of the mixed membership model. The method is based on the so-called tensor power method, used to obtain a tensor decomposition. We first outline the basic tensor decomposition method below and then demonstrate how the method can be adapted to learning using the graph moments at hand. We first analyze the simpler case when exact moments are available in Section 3.2 and then extend the method to handle empirical moments computed from the network observations in Section 3.3.

In this section, we review the basic method for tensor decomposition based on power iterations for a special class of tensors, viz., symmetric orthogonal tensors. Subsequently, in Section 3.2 and 3.3, we modify this method to learn the mixed membership model from graph moments, described in the previous section. For details on the tensor power method, refer to Anandkumar et al. (2012a); Kolda and Mayo (2011).

Recall that a third-order tensor $T$ is a three-dimensional array and we use $T_{p,q,r}$ to denote the $(p,q,r)$-th entry of the tensor $T$. The standard symbol $\otimes$ is used to denote the Kronecker product, and $(u\otimes v\otimes w)$ is a rank one tensor. The decomposition of a tensor into its rank one components is called the CP decomposition.

The term multilinear map arises from the fact that the above map is linear in each of the coordinates, e.g. if we replace $V_{1}$ by $aV_{1}+bW_{1}$ in the above equation, where $W_{1}$ is a matrix of appropriate dimensions, and $a,b$ are any scalars, the output is a linear combination of the outputs under $V_{1}$ and $W_{1}$ respectively. We will use the above notion of multi-linear transforms to describe various tensor operations. For instance, $T(I,I,v)$ yields a matrix, $T(I,v,v)$, a vector, and $T(v,v,v)$, a scalar.

where $r$ denotes the tensor CP rank and we use the notation $v_{i}^{\otimes 3}:=v_{i}\otimes v_{i}\otimes v_{i}$. It is convenient to first analyze methods for decomposition of symmetric tensors and we then extend them to the general case of asymmetric tensors.

For symmetric tensors $T$ possessing an orthogonal decomposition of the form in (19), each pair $(\lambda_{i},v_{i})$, for $i\in[r]$, can be interpreted as an eigen-pair for the tensor $T$, since

due to the fact that $\left<v_{i},v_{j}\right>=\delta_{i,j}$. Thus, the vectors $\{v_{i}\}_{i\in[r]}$ can be interpreted as fixed points of the map

where $\|\cdot\|$ denotes the spectral norm (and $\|T(I,v,v)\|$ is a vector norm), and is used to normalize the vector $v$ in (20).

A straightforward approach to computing the orthogonal decomposition of a symmetric tensor is to iterate according to the fixed-point map in (20) with an arbitrary initialization vector. This is referred to as the tensor power iteration method. Additionally, it is known that the vectors $\{v_{i}\}_{i\in[r]}$ are the only stable fixed points of the map in (20). In other words, the set of initialization vectors which converge to vectors other than $\{v_{i}\}_{i\in[r]}$ are of measure zero. This ensures that we obtain the correct set of vectors through power iterations and that no spurious answers are obtained. See (Anandkumar et al., 2012b, Thm. 4.1) for details. Moreover, after an approximately fixed point is obtained (after many power iterations), the estimated eigen-pair can be subtracted out (i.e., deflated) and subsequent vectors can be similarly obtained through power iterations. Thus, we can obtain all the stable eigen-pairs $\{\lambda_{i},v_{i}\}_{i\in[r]}$ which are the components of the orthogonal tensor decomposition. The method needs to be suitably modified when the tensor $T$ is perturbed (e.g. as in the case when empirical moments are used) and we discuss it in Section 3.3.

2 Learning Mixed Membership Models Under Exact Moments

We first describe the learning approach when exact moments are available. In Section 3.3, we suitably modify the approach to handle perturbations, which are introduced when only empirical moments are available.

We now employ the tensor power method described above to obtain a CP decomposition of the graph moment tensor $\operatorname{T}^{\alpha_{0}}$ in (15). We first describe a “symmetrization” procedure to convert the graph moment tensor $\operatorname{T}^{\alpha_{0}}$ to a symmetric orthogonal tensor through a multi-linear transformation of $\operatorname{T}^{\alpha_{0}}$. We then employ the power method to obtain a symmetric orthogonal decomposition. Finally, the original CP decomposition is obtained by reversing the multi-linear transform of the symmetrization procedure. This yields a guaranteed method for obtaining the decomposition of graph moment tensor $\operatorname{T}^{\alpha_{0}}$ under exact moments. We note that this symmetrization approach has been earlier employed in other contexts, e.g. for learning hidden Markov models (Anandkumar et al., 2012b, Sec. 3.3).

Recall from Proposition 2.2 that the modified $3$-star count tensor $\operatorname{T}^{\alpha_{0}}$ has a CP decomposition as

We now describe a symmetrization procedure to convert $\operatorname{T}^{\alpha_{0}}$ to a symmetric orthogonal tensor through a multi-linear transformation using the modified adjacency matrix $G^{\alpha_{0}}$, defined in (14). Consider the singular value decomposition (SVD) of the modified adjacency matrix $G^{\alpha_{0}}$ under exact moments:

Define $W_{A}:=U_{A}D_{A}^{-1},$ and similarly define $W_{B}$ and $W_{C}$ using the corresponding matrices $G_{X,B}^{\alpha_{0}}$ and $G_{X,C}^{\alpha_{0}}$ respectively. Now define

Proof: Recall that the modified adjacency matrix $G^{\alpha_{0}}$ satisfies

From the definition of $\Psi_{X}$ above, we see that it has rank $k$ when $\Pi_{X}$ has rank $k$. Using the Sylvester’s rank inequality, we have that the rank of $F_{A}\operatorname{Diag}(\widehat{\alpha}^{1/2})\Psi_{X}$ is at least $2k-k=k$. This implies that the whitening matrix $W_{A}$ also has rank $k$. Notice that

or in other words, $|X|^{-1}MM^{\top}=I$, where $M:=W_{A}^{\top}F_{A}\operatorname{Diag}(\widehat{\alpha}^{1/2})\Psi_{X}$. We now have that

With the above result in place, we are now ready to describe the high-level approach for learning the mixed membership model under exact moments. First, symmetrize the graph-moment tensor $\operatorname{T}^{\alpha_{0}}$ as described above and then apply the tensor power method described in the previous section. This enables us to obtain the vector of eigenvalues $\lambda:=\widehat{\alpha}^{-1/2}$ and the matrix of eigenvectors $\Phi=W_{A}^{\top}F_{A}\operatorname{Diag}(\widehat{\alpha}^{0.5})$ using tensor power iterations. We can then recover the community membership vectors of set $A^{c}$ (i.e., nodes not in set $A$) under exact moments as

3 Learning Algorithm Under Empirical Moments

In the previous section, we explored a tensor-based approach for learning mixed membership model under exact moments. However, in practice, we only have samples (i.e. the observed network), and the method needs to be robust to perturbations when empirical moments are employed.

In the previous section, we partitioned the nodes into four sets $A,B,C,X$ for learning under exact moments. However, we require more partitions under empirical moments to avoid statistical dependency issues and obtain stronger reconstruction guarantees. We now divide the network into five non-overlapping sets $A,B,C,X,Y$. The set $X$ is employed to compute whitening matrices $\hat{W}_{A}$, $\hat{W}_{B}$ and $\hat{W}_{C}$, described in detail subsequently, the set $Y$ is employed to compute the $3$-star count tensor $\operatorname{T}^{\alpha_{0}}$ and sets $A,B,C$ contain the leaves of the $3$-stars under consideration. The roles of the sets can be interchanged to obtain the community membership vectors of all the sets.

The whitening procedure is along the same lines as described in the previous section, except that now empirical moments are used. Specifically, consider the $k$-rank singular value decomposition (SVD) of the modified adjacency matrix $G^{\alpha_{0}}$ defined in (14),

Define $\hat{W}_{A}:=U_{A}D_{A}^{-1},$ and similarly define $\hat{W}_{B}$ and $\hat{W}_{C}$ using the corresponding matrices $G_{X,B}^{\alpha_{0}}$ and $G_{X,C}^{\alpha_{0}}$ respectively. Now define

and similarly define $\hat{R}_{AC}$. The whitened and symmetrized graph-moment tensor is now computed as

where $\operatorname{T}^{\alpha_{0}}$ is given by (15) and the multi-linear transformation of a tensor is defined in (3.1).

3.2 Modifications to the tensor power method

Recall that under exact moments, the stable eigen-pairs of a symmetric orthogonal tensor can be computed in a straightforward manner through the basic power iteration method in (20), along with the deflation procedure. However, this is not sufficient to get good reconstruction guarantees under empirical moments. We now propose a robust tensor method, detailed in Procedure 2. The main modifications involve: (i) efficient initialization and (ii) adaptive deflation, which are detailed below. Employing these modifications allows us to tolerate a far greater perturbation of the third order moment tensor, than the basic tensor power procedure employed in Anandkumar et al. (2012b). See remarks following Theorem A.1 in Appendix A for the precise comparison.

Recall that the basic tensor power method incorporates generic initialization vectors and this procedure recovers all the stable eigenvectors correctly (except for initialization vectors over a set of measure zero). However, under empirical moments, we have a perturbed tensor, and here, it is advantageous to instead employ specific initialization vectors. For instance, to obtain one of the eigenvectors $(\Phi)_{i}$, it is advantageous to initialize with a vector in the neighborhood of $(\Phi)_{i}$. This not only reduces the number of power iterations required to converge (approximately), but more importantly, this makes the power method more robust to perturbations. See Theorem A.1 in Appendix A.1 for a detailed analysis quantifying the relationship between initialization vectors, tensor perturbation and the resulting guarantees for recovery of the tensor eigenvectors.

For a mixed membership model in the sparse regime, recall that the community membership vectors $\Pi$ are sparse (with high probability). Under this regime of the model, we note that the whitened neighborhood vectors contain good initializers for the power iterations. Specifically, in Procedure 2, we initialize with the whitened neighborhood vectors $\hat{W}_{A}^{\top}G_{i,A}^{\top}$, for $i\notin A$. The intuition behind this is as follows: for a suitable choice of parameters (such as the scaling of network size $n$ with respect to the number of communities $k$), we expect neighborhood vectors $G_{i,A}^{\top}$ to concentrate around their mean values, viz., , $F_{A}\pi_{i}$. Since $\pi_{i}$ is sparse (w.h.p) for the model regime under consideration, this implies that there exist vectors $\hat{W}_{A}^{\top}F_{A}\pi_{i}$, for $i\in A^{c}$, which concentrate (w.h.p) on only along a few eigen-directions of the whitened tensor, and hence, serve as an effective initializer.

Recall that in the basic power iteration procedure, we can obtain the eigen-pairs one after another through simple deflation: subtracting the estimates of the current eigen-pairs and running the power iterations again to obtain new eigenvectors. However, it turns out that we can establish better theoretical guarantees (in terms of greater robustness) when we adaptively deflate the tensor in each power iteration. In Procedure 2, among the estimated eigen-pairs, we only deflate those which “compete” with the current estimate of the power iteration. In other words, if the vector in the current iteration $\theta_{t}^{(\tau)}$ has a significant projection along the direction of an estimated eigen-pair $\phi_{j}$, i.e.

for some threshold $\xi$, then the eigen-pair is deflated; otherwise the eigenvector $\phi_{j}$ is not deflated. This allows us to carefully control the error build-up for each estimated eigenpair in our analysis. Intuitively, if an eigenvector does not have a good correlation with the current estimate, then it does not interfere with the update of the current vector, while if the eigenvector has a good correlation, then it is pertinent that it be deflated so as to discourage convergence in the direction of the already estimated eigenvector. See Theorem A.1 in Appendix A.1 for details.

Finally, we note that stabilization, as proposed by Kolda and Mayo (2011) for general tensor eigen-decomposition (as opposed to orthogonal decomposition in this paper), can be effective in improving convergence, especially on real data, and we defer its detailed analysis to future work.

3.3 Reconstruction after tensor power method

Recall that previously in Section 3.2, when exact moments are available, estimating the community membership vectors $\Pi$ is straightforward, once we recover all the stable tensor eigen-pairs. However, in case of empirical moments, we can obtain better guarantees with the following modification: the estimated community membership vectors $\Pi$ are further subject to thresholding so that the weak values are set to zero. Since we are limiting ourselves to the regime of the mixed membership model, where the community vectors $\Pi$ are sparse (w.h.p), this modification strengthens our reconstruction guarantees. This thresholding step is incorporated in Algorithm 1.

based on estimates $\hat{\Pi}$, and the matrix $\hat{P}$ is obtained as $\hat{P}\leftarrow\hat{Q}G\hat{Q}^{\top}$. We subsequently establish that $\hat{Q}\hat{\Pi}^{\top}\approx I$, under a set of sufficient conditions outlined in the next section.

A sub-class of community model are those satisfying homophily. As discussed in Section 1, homophily or the tendency to form edges within the members of the same community has been posited as an important factor in community formation, especially in social settings. Many of the existing learning algorithms, e.g. Chen et al. (2012) require this assumption to provide guarantees in the stochastic block model setting. Moreover, our procedure described below can be easily modified to work in situations where the order of intra-connectivity and inter-connectivity among communities is reversed, i.e. in the community connectivity matrix $P\in^{k\times k}$, $P(i,i)\equiv p<P(i,j)\equiv q$, for all $i\neq j$. For instance, in the $k$-coloring model (McSherry, 2001), $p=0$ and $q>0$.

We describe the post-processing method in Procedure 3 for models with community connectivity matrix $P$ satisfying $P(i,i)\equiv p>P(i,j)\equiv q$ for all $i\neq j$. For such models, we can obtain improved estimates by averaging. Specifically, consider nodes in set $C$ and edges going from $C$ to nodes in $B$. First, consider the special case of the stochastic block model: for each node $c\in C$, compute the number of neighbors in $B$ belonging to each community (as given by the estimate $\hat{\Pi}$ from Algorithm 1), and declare the community with the maximum number of such neighbors as the community of node $c$. Intuitively, this provides a better estimate for $\Pi_{C}$ since we average over the edges in $B$. This method has been used before in the context of spectral clustering (McSherry, 2001).

The same idea can be extended to the general mixed membership (homophilic) models: declare communities to be significant if they exceed a certain threshold, as evaluated by the average number of edges to each community. The correctness of the procedure can be gleaned from the fact that if the true $F$ matrix is input, it satisfies

and if the true $P$ matrix is input, $H=p$ and $L=q$. Thus, under a suitable threshold $\xi$, the entries $F_{j,i}$ provide information on whether the corresponding community weight $\Pi_{i,j}$ is significant.

In the next section, we establish that in certain regime of parameters, this support recovery procedure can lead to zero-error support recovery of significant community memberships of the nodes and also rule out communities where a node does not have a strong presence.

We note that the computational complexity of the method, implemented naively, is $O(n^{2}k+k^{4.43}\widehat{\alpha}_{\min}^{-1})$ when $\alpha_{0}>1$ and $O(n^{2}k)$ when $\alpha_{0}<1$. This is because the time for computing whitening matrices is dominated by SVD of the top $k$ singular vectors of $n\times n$ matrix, which takes $O(n^{2}k)$ time. We then compute the whitened tensor $T$ which requires time $O(n^{2}k+k^{3}n)=O(n^{2}k)$, since for each $i\in Y$, we multiply $G_{i,A},G_{i,B},G_{i,C}$ with the corresponding whitening matrices, and this step takes $O(nk)$ time. We then average this $k\times k\times k$ tensor over different nodes $i\in Y$ to the result, which takes $O(k^{3})$ time in each step.

For the tensor power method, the time required for a single iteration is $O(k^{3})$. We need at most $\log n$ iterations per initial vector, and we need to consider $O(\widehat{\alpha}_{\min}^{-1}k^{0.43})$ initial vectors (this could be smaller when $\alpha_{0}<1$). Hence the total running time of tensor power method is $O(k^{4.43}\widehat{\alpha}_{\min}^{-1})$ (and when $\alpha_{0}$ is small this can be improved to $O(k^{4}\widehat{\alpha}_{\min}^{-1})$ which is dominated by $O(n^{2}k)$.

In the process of estimating $\Pi$ and $P$, the dominant operation is multiplying $k\times n$ matrix by $n\times n$ matrix, which takes $O(n^{2}k)$ time. For support recovery, the dominant operation is computing the “average degree”, which again takes $O(n^{2}k)$ time. Thus, we have that the overall computational time is $O(n^{2}k+k^{4.43}\widehat{\alpha}_{\min}^{-1})$ when $\alpha_{0}>1$ and $O(n^{2}k)$ when $\alpha_{0}<1$.

Note that the above bound on complexity of our method nearly matches the bound for spectral clustering method (McSherry, 2001), since computing the $k$-rank SVD requires $O(n^{2}k)$ time. Another method for learning stochastic block models is based on convex optimization involving semi-definite programming (SDP) (Chen et al., 2012), and it provides the best scaling bounds (for both the network size $n$ and the separation $p-q$ for edge connectivity) known so far. The specific convex problem can be solved via the method of augmented Lagrange multipliers (Lin et al., 2010), where each step consists of an SVD operation and q-linear convergence is established by Lin et al. (2010). This implies that the method has complexity $O(n^{3})$, since it involves taking SVD of a general $n\times n$ matrix, rather than a $k$-rank SVD. Thus, our method has significant advantage in terms of computational complexity, when the number of communities is much smaller than the network size $(k\ll n)$.

Further, a subsequent work provides a more sophisticated implementation of the proposed tensor method through parallelization and the use of stochastic gradient descent for tensor decomposition (Huang et al., 2013). Additionally, the $k$-rank SVD operations are approximated via randomized methods such as the Nystrom’s method leading to more efficient implementations (Gittens and Mahoney, 2013). Huang et al. (2013) deploy the tensor approach for community detection and establish that it has a running time of $O(n+k^{3})$ using $nk$ cores under a parallel computation model (JáJá, 1992).

Sample Analysis for Proposed Learning Algorithm

It is easier to first present the results for our proposed algorithm for the special case, where all the communities have the same expected size and the entries of the community connectivity matrix $P$ are equal on diagonal and off-diagonal locations:

In other words, the probability of an edge according to $P$ only depends on whether it is between two individuals of the same community or between different communities. The above setting is also well studied for stochastic block models $(\alpha_{0}=0)$, allowing us to compare our results with existing ones. The results for general mixed membership models are deferred to Section 4.2.

The community membership vectors are drawn from the Dirichlet distribution, $\operatorname{Dir}(\alpha)$, under the mixed membership model. We assume that $\alpha_{i}<1$ for $i\in[k]$ (see Section 2.1 for an extended discussion on the sparse regime of the Dirichlet distribution) and that $\alpha_{0}$ is known.

Given the concentration parameter of the Dirichlet distribution, $\alpha_{0}:=\sum_{i}\alpha_{i}$, we require that

Recall that $p$ is the probability of intra-community connectivity and $q$ is the probability of inter-community connectivity. We require that

The above condition is on the standardized separation between intra-community and inter-community connectivity (note that $\sqrt{p}$ is the standard deviation of a Bernoulli random variable). The above condition is required to control the perturbation in the whitened tensor (computed using observed network samples), thereby, providing guarantees on the estimated eigen-pairs through the tensor power method.

We assume that the number of iterations $N$ of the tensor power method in Procedure 2 satisfies

The threshold $\tau$ for obtaining estimates $\hat{\Pi}$ of community membership vectors in Algorithm 1 is chosen as

For the stochastic block model $(\alpha_{0}=0)$, since $\pi_{i}$ is a basis vector, we can use a large threshold. For general models $(\alpha_{0}\neq 0)$, $\tau$ can be viewed as a regularization parameter and decays as $n^{-1/2}$ when other parameters are held fixed. We are now ready to state the error bounds on the estimates of community membership vectors $\Pi$ and the block connectivity matrix $P$. $\hat{\Pi}$ and $\hat{P}$ are the estimates computed in Algorithm 1.

Recall that for a matrix $M$, $(M)^{i}$ and $(M)_{i}$ denote the $i^{{\mbox{\tiny th}}}$ row and column respectively. We say that an event holds with high probability, if it occurs with probability $1-n^{-c}$ for some constant $c>0$.

Under assumptions A1-A5, we have with high probability

The proofs are given in the Appendix and a proof outline is provided in Section 4.3.

The main ingredient in establishing the above result is the tensor concentration bound and additionally, recovery guarantees under the tensor power method in Procedure 2. We now provide these results below.

Recall that $F_{A}:=\Pi_{A}^{\top}P^{\top}$ and $\Phi=W_{A}^{\top}F_{A}\operatorname{Diag}(\widehat{\alpha}^{1/2})$ denotes the set of tensor eigenvectors under exact moments in (23), and $\hat{\Phi}$ is the set of estimated eigenvectors under empirical moments, obtained using Procedure 1. We establish the following guarantees.

Under the assumptions A1-A4, the recovered eigenvector-eigenvalue pairs $(\hat{\Phi}_{i},\hat{\lambda}_{i})$ from the tensor power method in Procedure 2 satisfies with high probability, for a permutation $\theta$, such that

The tensor perturbation bound $\varepsilon_{T}$ is given by

where $\|T\|$ for a tensor $T$ refers to its spectral norm.

For stochastic block models, assumptions A2 and A3 reduce to

This matches with the best known scaling (up to poly-log factors), and was previously achieved via convex optimization by Chen et al. (2012) for stochastic block models. However, our results in Theorem 4.1 do not provide zero error guarantees as in Chen et al. (2012). We strengthen our results to provide zero-error guarantees in Section 4.1.1 below and thus, match the scaling of Chen et al. (2012) for stochastic block models. Moreover, we also provide zero-error support recovery guarantees for recovering significant memberships of nodes in mixed membership models in Section 4.1.1.

The guarantees degrade as $\alpha_{0}$ increases, which is intuitive since the extent of community overlap increases. The requirement for scaling of $n$ also grows as $\alpha_{0}$ increases. Note that the guarantees on $\varepsilon_{\pi}$ and $\varepsilon_{P}$ can be improved by assuming a more stringent scaling of $n$ with respect to $\alpha_{0}$, rather than the one specified by A2.

1.1 Zero-error guarantees for support recovery

Recall that we proposed Procedure 3 as a post-processing step to provide improved support recovery estimates. We now provide guarantees for this method.

We now specify the threshold $\xi$ for support recovery in Procedure 3.

We assume that the threshold $\xi$ in Procedure 3 satisfies

where $\varepsilon_{P}$ is specified in Theorem 4.1. We now state the guarantees for support recovery.

Assuming A1-A6 and (25) hold, the support recovery method in Procedure 3 has the following guarantees on the estimated support set $\hat{S}$: with high probability,

where $\Pi$ is the true community membership matrix.

Thus, the above result guarantees that the Procedure 3 correctly recovers all the “large” entries of $\Pi$ and also correctly rules out all the “small” entries in $\Pi$. In other words, we can correctly infer all the significant memberships of each node and also rule out the set of communities where a node does not have a strong presence.

The only shortcoming of the above result is that there is a gap between the “large” and “small” values, and for an intermediate set of values (in $[\xi/2,\xi]$), we cannot guarantee correct inferences about the community memberships. Note this gap depends on $\varepsilon_{P}$, the error in estimating the $P$ matrix. This is intuitive, since as the error $\varepsilon_{P}$ decreases, we can infer the community memberships over a large range of values.

For the special case of stochastic block models (i.e. $\lim\alpha_{0}\rightarrow 0$), we can improve the above result and give a zero error guarantee at all nodes (w.h.p). Note that we no longer require a threshold $\xi$ in this case, and only infer one community for each node.

Assuming A1-A5 and (25) hold, the support recovery method in Procedure 3 correctly identifies the community memberships for all nodes with high probability in case of stochastic block models $(\alpha_{0}\to 0)$.

Thus, with the above result, we match the state-of-art results of Chen et al. (2012) for stochastic block models in terms of scaling requirements and recovery guarantees.

2 General (Non-Homogeneous) Mixed Membership Models

In the previous sections, we provided learning guarantees for learning homogeneous mixed membership models. Here, we extend the results to learning general non-homogeneous mixed membership models under a sufficient set of conditions, involving scaling of various parameters such as network size $n$, number of communities $k$, concentration parameter $\alpha_{0}$ of the Dirichlet distribution (which is a measure of overlap of the communities) and so on.

Given the concentration parameter of the Dirichlet distribution, $\alpha_{0}:=\sum_{i}\alpha_{i}$, and $\widehat{\alpha}_{\min}:=\alpha_{\min}/\alpha_{0}$, the expected size of the smallest community, define

We require that the network size scale as

Recall that $P\in^{k\times k}$ denotes the block connectivity matrix. Define

where $\sigma_{\min}(P)$ is the minimum singular value of $P$. We require that

Intuitively, the above condition requires the ratio of maximum and minimum expected community sizes to be not too large and for the matrix $P$ to be well conditioned. The above condition is required to control the perturbation in the whitened tensor (computed using observed network samples), thereby, providing guarantees on the estimated eigen-pairs through the tensor power method. The above condition can be interpreted as a separation requirement between intra-community and inter-community connectivity in the special case considered in Section 4.1. Specifically, for the special case of homogeneous mixed membership model, we have

Thus, the assumptions A2 and A3 in Section 4.1 given by

are special cases of the assumptions B2 and B3 above.

We assume that the number of iterations $N$ of the tensor power method in Procedure 2 satisfies

The threshold $\tau$ for obtaining estimates $\hat{\Pi}$ of community membership vectors in Algorithm 1 is chosen as

We are now ready to state the error bounds on the estimates of community membership vectors $\Pi$ and the block connectivity matrix $P$. $\hat{\Pi}$ and $\hat{P}$ are the estimates computed in Algorithm 1.

Recall that for a matrix $M$, $(M)^{i}$ and $(M)_{i}$ denote the $i^{{\mbox{\tiny th}}}$ row and column respectively. We say that an event holds with high probability, if it occurs with probability $1-n^{-c}$ for some constant $c>0$.

Under assumptions B1-B5, The estimates $\hat{P}$ and $\hat{\Pi}$ obtained from Algorithm 1 satisfy with high probability,

The proofs are in Appendix B and a proof outline is provided in Section 4.3.

The main ingredient in establishing the above result is the tensor concentration bound and additionally, recovery guarantees under the tensor power method in Procedure 2. We now provide these results below.

Recall that $F_{A}:=\Pi_{A}^{\top}P^{\top}$ and $\Phi=W_{A}^{\top}F_{A}\operatorname{Diag}(\widehat{\alpha}^{1/2})$ denotes the set of tensor eigenvectors under exact moments in (23), and $\hat{\Phi}$ is the set of estimated eigenvectors under empirical moments, obtained using Procedure 1. We establish the following guarantees.

Under the assumptions B1-B4, the recovered eigenvector-eigenvalue pairs $(\hat{\Phi}_{i},\hat{\lambda}_{i})$ from the tensor power method in Procedure 2 satisfies with high probability, for a permutation $\theta$, such that

The tensor perturbation bound $\varepsilon_{T}$ is given by

where $\|T\|$ for a tensor $T$ refers to its spectral norm, $\rho$ is defined in (37) and $\zeta$ in (39).

2.1 Application to Planted Clique Problem

The planted clique problem is a special case of the stochastic block model Condon and Karp (1999), and is arguably the simplest setting for the community problem. Here, a clique of size $s$ is uniformly planted (or placed) in an Erdős-Rényi graph with edge probability $0.5$. This can be viewed as a stochastic block model with $k=2$ communities, where $\widehat{\alpha}_{\min}=s/n$ is the probability of a node being in a clique and $\widehat{\alpha}_{\max}=1-s/n$. The connectivity matrix is $P=[1,q;q,q]$ with $q=0.5$, since the probability of connectivity within the clique is $1$ and the probability of connectivity for any other node pair is $0.5$.

Since the planted clique setting has unequal sized communities, the general result in Section 4.3 is applicable, and we demonstrate how the assumptions $(B1)$-$(B5)$ simplify for the planted clique setting. We have that $\alpha_{0}=0$, since the communities are non-overlapping. For assumption $B2$, we have that

For assumption $B3$, we have that $\sigma_{\min}(P)=\Theta(1)$ and that $\max_{i}(P\widehat{\alpha})_{i}\leq s/n+q\leq 2$, and thus the assumption $B3$ simplifies as

3 Proof Outline

We now summarize the main techniques involved in proving Theorem 4.3. The details are in the Appendix. The main ingredient is the concentration of the adjacency matrix: since the edges are drawn independently conditioned on the community memberships, we establish that the adjacency matrix concentrates around its mean under the stated assumptions. See Appendix C.4 for details. With this in hand, we can then establish concentration of various quantities used by our learning algorithm.

We first establish concentration bounds on the whitening matrices $\hat{W}_{A}$, $\hat{W}_{B}$, $\hat{W}_{C}$ computed using empirical moments, described in Section 3.3.1. With this in hand, we can approximately recover the span of matrix $F_{A}$ since $\hat{W}_{A}^{\top}F\operatorname{Diag}(\widehat{\alpha}_{i})^{1/2}$ is a rotation matrix. The main technique employed is the Matrix Bernstein’s inequality (Tropp, 2012, thm. 1.4). See Appendix C.2 for details.

Recall that we use the whitening matrices to obtain a symmetric orthogonal tensor. We establish that the whitened and symmetrized tensor concentrates around its mean. (Note that the empirical third order tensor $T_{X\rightarrow A,B,C}$ tends to its expectation conditioned on $\Pi_{A},\Pi_{B},\Pi_{C}$ when $|X|\to\infty$). This is done in several stages and we carefully control the tensor perturbation bounds. See Appendix C.1 for details.

We analyze the performance of Procedure 2 under empirical moments. We employ the various improvements, detailed in Section 3.3.2 to establish guarantees on the recovered eigen-pairs. This includes coming up with a condition on the tensor perturbation bound, for the tensor power method to succeed. It also involves establishing that there exist good initializers for the power method among (whitened) neighborhood vectors. This allows us to obtain stronger guarantees for the tensor power method, compared to earlier analysis by Anandkumar et al. (2012b). This analysis is crucial for us to obtain state-of-art scaling bounds for guaranteed recovery (for the special case of stochastic block model). See Appendix A for details.

To simplify the argument, consider the stochastic block model. Recall that Procedure 3 readjusts the community membership estimates based on degree averaging. For each vertex, if we count the average degree towards these “approximate communities”, for the correct community the result is concentrated around value $p$ and for the wrong community the result is around value $q$. Therefore, we can correctly identify the community memberships of all the nodes, when $p-q$ is sufficiently large, as specified by A3. The argument can be easily extended to general mixed membership models. See Appendix B.4 for details.

4 Comparison with Previous Results

We now compare the results of this paper to our previous work (Anandkumar et al., 2012b) on the use of tensor-based approaches for learning various latent variable models such as topic models, hidden Markov models (HMM) and Gaussian mixtures. At a high level, the tensor approach is exploited in a similar manner in all these models (including the community model in this paper), viz., that the conditional-independence relationships of the model result in a low rank tensor, constructed from low order moments under the given model. However, there are several important differences between the community model and the other latent variable models considered by Anandkumar et al. (2012b) and we list them below. We also precisely list the various algorithmic improvements proposed in this paper with respect to the tensor power method, and how they can be applicable to other latent variable models.

Among the latent variable models studied by Anandkumar et al. (2012b), the topic model, viz., latent Dirichlet allocation (LDA), bears the closest resemblance to MMSB. In fact, the MMSB model was originally inspired by the LDA model. The analogy between the MMSB model and the LDA is direct under our framework and we describe it below.

Recall that for learning MMSBs, we consider a partition of the nodes $\{X,A,B,C\}$ and we consider the set of $3$-stars from set $X$ to $A,B,C$. We can construct an equivalent topic model as follows: the nodes in $X$ form the “documents” and for each document $x\in X$, the neighborhood vectors $G_{xA}^{\top},G_{xB}^{\top},G_{xC}^{\top}$ form the three “words” or “views” for that document. In each document $x\in X$, the community vector $\pi_{x}$ corresponds to the “topic vector” and the matrices $F_{A}$, $F_{B}$ and $F_{C}$ correspond to the topic-word matrices. Note that the three views $G_{xA}^{\top},G_{xB}^{\top},G_{xC}^{\top}$ are conditionally independent given the topic vector $\pi_{x}$. Thus, the community model can be cast as a topic model or a multi-view model. See Figure 2.

Although the community model can be viewed as a topic model, it has some important special properties which allows us to provide better guarantees. The topic-word matrices $F_{A},F_{B},F_{C}$ are not arbitrary matrices. Recall that $F_{A}:=\Pi_{A}^{\top}P^{\top}$ and similarly $F_{B},F_{C}$ are random matrices and we can provide strong concentration bounds for these matrices by appealing to random matrix theory. Moreover, each of the views in the community model has additional structure, viz., the vector $G^{\top}_{x,A}$ has independent Bernoulli entries conditioned on the community vector $\pi_{x}$, while in a general multi-view model, we only specify the conditional distribution of each view given the hidden topic vector. This further allows us to provide specialized concentration bounds for the community model. Importantly, we can recover the community memberships (or topic vectors) accurately while for a general multi-view model this cannot be guaranteed and we can only hope to recover the model parameters.

4.2 Improvements to tensor recovery guarantees in this paper

In this paper, we make modifications to the tensor power method of Anandkumar et al. (2012b) and obtain better guarantees for the community setting. Recall that the two modifications are adaptive deflation and initialization using whitened neighborhood vectors. The adaptive deflation leads to a weaker gap condition for an initialization vector to succeed in estimating a tensor eigenvector efficiently. Initialization using whitened neighborhood vectors allows us to tolerate more noise in the estimated $3$-star tensor, thereby improving our sample complexity result. We make this improvement precise below.

If we directly apply the tensor power method of Anandkumar et al. (2012b), without considering the modifications, we require a stronger condition on the sample complexity and edge connectivity. For simplicity, consider the homogeneous setting of Section 4.1. The conditions $(A2)$ and $(A3)$ now need to be replaced with stronger conditions:

The edge connectivity parameters $p,q$ satisfy

Thus, we obtain significant improvements in recovery guarantees via algorithmic modifications and careful analysis of concentration bounds.

The guarantees derived in this paper are specific to the community setting, and we outlined previously the special properties of the community model when compared to a general multi-view model. However, when the documents of the topic model are sufficiently long, the word frequency vector within a document has good concentration, and our modified tensor method has better recovery guarantees in this setting as well. Thus, the improved tensor recovery guarantees derived in this paper are applicable in scenarios where we have access to better initialization vectors rather than simple random initialization.

Conclusion

In this paper, we presented a novel approach for learning overlapping communities based on a tensor decomposition approach. We established that our method is guaranteed to recover the underlying community memberships correctly, when the communities are drawn from a mixed membership stochastic block model (MMSB). Our method is also computationally efficient and requires simple linear algebraic operations and tensor iterations. Moreover, our method is tight for the special case of the stochastic block model (up to poly-log factors), both in terms of sample complexity and the separation between edge connectivity within a community and across different communities.

We now note a number of interesting open problems and extensions. While we obtained tight guarantees for MMSB models with uniform sized communities, our guarantees are weak when the community sizes are drastically different, such as in the planted clique setting where we do not match the computational lower bound (Feldman et al., 2012). The whitening step in the tensor decomposition method is particularly sensitive to the ratio of community sizes and it is interesting to see if modifications can be made to our algorithm to provide tight guarantees under unequal community sizes. While this paper mostly dealt with the theoretical analysis of the tensor method for community detection, we note recent experimental results where the tensor method is deployed on graphs with millions of nodes with very good accuracy and running times (Huang et al., 2013). In fact, the running times are more than an order of magnitude better than the state-of-art variational approach for learning MMSB models. The work of (Huang et al., 2013) makes an important modification to make the method scalable, viz., that the tensor decomposition is carried out through stochastic updates in parallel unlike the serial batch updates considered here. Establishing theoretical guarantees for stochastic tensor decomposition is an important problem. Moreover, we have limited ourselves to the MMSB models, which assumes a linear model for edge formation, which is not applicable universally. For instance, exclusionary relationships, where two nodes cannot be connected because of their memberships in certain communities cannot be imposed in the MMSB model. Are there other classes of mixed membership models which do not suffer from this restriction, and yet are identifiable and are amenable for learning? Moreover, the Dirichlet distribution in the MMSB model imposes constraints on the memberships across different communities. Can we incorporate mixed memberships with arbitrary correlations? The answers to these questions will further push the boundaries of tractable learning of mixed membership communities models.

We thank the JMLR Action Editor Nathan Srebro and the anonymous reviewers for comments which significantly improved this manuscript. We thank Jure Leskovec for helpful discussions regarding various community models. Part of this work was done when AA and RG were visiting MSR New England. AA is supported in part by the Microsoft faculty fellowship, NSF Career award CCF-1254106, NSF Award CCF-1219234 and the ARO YIP Award W911NF-13-1-0084.

References

Appendix A Tensor Power Method Analysis

In this section, we leverage on the perturbation analysis for tensor power method in Anandkumar et al. [2012b]. As discussed in Section 3.3.2, we propose the following modifications to the tensor power method and obtain guarantees below for the modified method. The two main modifications are: (1) we modify the tensor deflation process in the robust power method in Procedure 2. Rather than a fixed deflation step after obtaining an estimate of the eigenvalue-eigenvector pair, in this paper, we deflate adaptively depending on the current estimate, and (2)rather than selecting random initialization vectors, as in Anandkumar et al. [2012b], we initialize with vectors obtained from adjacency matrix.

Below in Section A.1, we establish success of the modified tensor method under “good” initialization vectors, as defined below. This involves improved error bounds for the modified deflation procedure provided in Section A.2. In Section C.5, we subsequently establish that under the Dirichlet distribution (for small $\alpha_{0}$), we obtain “good” initialization vectors.

We now show that when “good” initialization vectors are input to tensor power method in Procedure 2, we obtain good estimates of eigen-pairs under appropriate choice of number of iterations $N$ and spectral norm $\epsilon$ of tensor perturbation.

We call an initialization vector $u$ to be $(\gamma,R_{0})$-good if there exists $v_{i}$ such that $\left<u,v_{i}\right>>R_{0}$ and

There exists universal constants $C_{1},C_{2}>0$ such that the following holds.

Assume there is at least one good initialization vector corresponding to each $v_{i}$, $i\in[k]$. The parameter $\xi$ for choosing deflation vectors in each iteration of the tensor power method in Procedure 2 is chosen as $\xi\geq 25\epsilon$. We obtain eigenvalue-eigenvector pairs $(\hat{\lambda}_{1},\hat{v}_{1}),(\hat{\lambda}_{2},\hat{v}_{2}),\dotsc,(\hat{\lambda}_{k},\hat{v}_{k})$ such that there exists a permutation $\pi$ on $[k]$ with

We now compare the above result with the result in [Anandkumar et al., 2012b, Thm. 5.1], where similar guarantees are obtained for a simpler version of the tensor power method without any adaptive deflation and using random initialization. The main difference is in our requirement of the gap $\gamma$ in (51) for an initialization vector is weaker than the gap requirement in [Anandkumar et al., 2012b, Thm. 5.1]. This is due to the use of adaptive deflation in this paper.

In this paper, we employ whitened neighborhood vectors generated under the MMSB model for initialization, while [Anandkumar et al., 2012b, Thm. 5.1] assumes a random initialization. Under random initialization, we obtain $R_{0}\sim 1/\sqrt{k}$ (with poly$(k)$ trials), while for initialization using whitened neighborhood vectors, we subsequently establish that $R_{0}=\Omega(1)$ is a constant, when number of samples $n$ is large enough. We also establish that the gap requirement in (51) is satisfied for the choice of $\gamma=1/100$ above. See Lemma C.9 for details. Thus, we can tolerate much larger perturbation $\epsilon$ of the third order moment tensor, when non-random initializations are employed.

Proof: The proof is on lines of the proof of [Anandkumar et al., 2012b, Thm. 5.1] but here, we consider the modified deflation procedure, which improves the condition on $\epsilon$ in (52). We provide the full proof below for completeness.

We prove by induction on $i$, the number of eigenpairs estimated so far by Procedure 2. Assume that there exists a permutation $\pi$ on $[k]$ such that the following assertions hold.

For all $j\leq i$, $\|v_{\pi(j)}-\hat{v}_{j}\|\leq 8\epsilon/\lambda_{\pi(j)}$ and $|\lambda_{\pi(j)}-\hat{\lambda}_{j}|\leq 12\epsilon$.

$D(u,i)$ is the set of deflated vectors given current estimate of the power method is $u\in S^{k-1}$:

where $\hat{\theta}_{i}:=\left<u,\hat{v}_{i}\right>$.

We take $i=0$ as the base case, so we can ignore the first assertion, and just observe that for $i=0$, $D(u,0;\xi)=\emptyset$ and thus

Now fix some $i\in[k]$, and assume as the inductive hypothesis. The power iterations now take a subset of $j\in[i]$ for deflation, depending on the current estimate. Set

On the other hand, by the triangle inequality,

where $j^{*}:=\arg\max_{j\geq i}\lambda_{\pi(j)}|\theta_{\pi(j),N}|$. Therefore

Squaring both sides and using the fact that $\theta_{\pi(j^{*}),N}^{2}+\theta_{\pi(j),N}^{2}\leq 1$ for any $j\neq j^{*}$,

This means that $\theta_{N}$ is $(1/4)$-separated relative to $\pi(j^{*})$. Also, observe that

Since $\hat{v}_{i}=\hat{\theta}$ and $\hat{\lambda}_{i}=\hat{\lambda}$, the first assertion of the inductive hypothesis is satisfied, as we can modify the permutation $\pi$ by swapping $\pi(i)$ and $\pi(j^{*})$ without affecting the values of $\{\pi(j):j\leq i-1\}$ (recall $j^{*}\geq i$).

To prove that (54) holds, for any unit vector $u\in S^{k-1}$ such that there exists $j^{\prime}\geq i+1$ with $(u^{\scriptscriptstyle\top}v_{\pi(j^{\prime})})^{2}\geq 1-(168\epsilon/\lambda_{\pi(j^{\prime})})^{2}$. We have (via the second bound on $C_{1}$ in (55) and the corresponding assumed bound $\epsilon\leq C_{1}\cdot\lambda_{\min}R_{0}^{2}$)

A.2 Deflation Analysis

For some $t\in[k]$ and a unit vector $u\in S^{k-1}$ such that $u=\sum_{i\in[k]}\theta_{i}v_{i}$ and $\hat{\theta}_{i}:=\left<u,\hat{v}_{i}\right>$, we have for $i\in[t]$,

Proof: The proof is on lines of deflation analysis in [Anandkumar et al., 2012b, Lemma B.5], but we improve the bounds based on additional properties of vector $u$. From Anandkumar et al. [2012b], we have that for all $i\in[t]$, and any unit vector $u$,

Appendix B Proof of Theorem 4.3

We now prove the main results on error bounds claimed in Theorem 4.3 for the estimated community vectors $\hat{\Pi}$ and estimated block probability matrix $\hat{P}$ in Algorithm 1. Below, we first show that the tensor perturbation bounds claimed in Lemma 4.2 holds.

B.1 Proof of Lemma 4.2

From Theorem A.1 in Appendix A, we see that the tensor power method returns eigenvalue-vector pair $(\hat{\lambda}_{i},\hat{\Phi}_{i})$ such that there exists a permutation $\theta$ with

when the perturbation of the tensor is small enough, according to

for some constant $C_{1}$, when initialized with a $(\gamma,r_{0})$ good vector.

With the above result, two aspects need to be established: (1) the whitened tensor perturbation $\epsilon_{T}$ is as claimed, (2) the condition in (61) is satisfied and (3) there exist good initialization vectors when whitened neighborhood vectors are employed. The tensor perturbation bound $\epsilon_{T}$ is established in Theorem C.1 in Appendix C.1.

Lemma C.9 establishes that when $\zeta=O(\sqrt{n}r_{0}^{2}/\rho)$, we have good initialization vectors with Recall $r_{0}^{2}=\Omega(1/\widehat{\alpha}_{\max}k)$ when $\alpha_{0}>1$ and $r_{0}^{2}=\Omega(1)$ for $\alpha_{0}\leq 1$, and $\gamma=1/100$ with probability $1-9\delta$ under Dirichlet distribution, when

which is satisfied since we assume $\widehat{\alpha}_{\min}^{-2}<n$.

We now show that the condition in (61) is satisfied under the assumptions B1-B4. Since $\epsilon_{T}$ is given by

the condition in (61) is equivalent to $\zeta=O(\sqrt{n}r_{0}^{2}/\rho)$. Therefore when $\zeta=O(\sqrt{n}r_{0}^{2}/\rho)$, the assumptions of Theorem A.1 are satisfied.

B.2 Reconstruction of ΠΠ\Pi after tensor power method

Let $(M)^{i}$ and $(M)_{i}$ denote the $i^{{\mbox{\tiny th}}}$ row and $i^{{\mbox{\tiny th}}}$ column in matrix $M$ respectively. Let $Z\subseteq A^{c}$ denote any subset of nodes not in $A$, considered in Procedure LearnPartition Community. Define

Assuming Lemma 4.2 holds and the tensor power method recovers eigenvectors and eigenvalues up to the guaranteed errors, we have with probability $1-122\delta$,

where $\varepsilon_{T}$ is given by (71).

The third term in (65) dominates the last term in (67) since $(\alpha_{0}+1)\log k/\delta<n\widehat{\alpha}_{\min}$ (due to assumption B2 on scaling of $n$). $\Box$

where $\eta=\widehat{\alpha}_{\max}$ when $\alpha_{0}<1$ and $\eta=\alpha_{\max}$ when $\alpha_{0}\in[1,k)$.

Proof: Let $S_{i}:=\{j:\hat{\Pi}_{Z}(i,j)>2\tau\}$. For a vector $v$, let $v_{S}$ denote the sub-vector by considering entries in set $S$. We now have

For the other term, from Lemma C.10, we have

Applying Bernstein’s bound we have with probability $1-\delta$

For $\hat{\Pi}^{i}_{S_{i}^{c}}$, we further divide $S_{i}^{c}$ into $T_{i}$ and $U_{i}$, where $T_{i}:=\{j:\tau/2<\Pi_{Z}(i,j)\leq 2\tau\}$ and $U_{i}:=\{j:\Pi_{Z}(i,j)\leq\tau/2\}$.

From Lemma C.10, we see that the results hold when we replace $\widehat{\alpha}_{\max}$ with $\alpha_{\max}$. $\Box$

B.3 Reconstruction of P𝑃P after tensor power method

We propose an alternative estimator $\hat{Q}$ for $\hat{\Pi}^{\dagger}$ and use it to find $\hat{P}$ in Algorithm 1. Recall that the $i$-th row of $\hat{Q}$ is given by