Community Detection Guarantees using Embeddings Learned by Node2Vec
Authors: Andrew Davison
Samuel Carlyle Morgan
Owen G. Ward
Venue: NeurIPS 2024 poster (2024)
Keywords: Network Embedding
Node2Vec
Community Detection
Networks
Primary area: probabilistic_methods
TL;DR: We show theoretical guarantees for community detection using node2vec embeddings of networks.

Abstract: Embedding the nodes of a large network into an Euclidean space is a common objective in modern
machine learning, with a variety of tools available. These embeddings can then be used as features for
tasks such as community detection/node clustering or link prediction, where they achieve state of the art
performance. With the exception of spectral clustering methods, there is little theoretical understanding
for commonly used approaches to learning embeddings. In this work we examine the theoretical
properties of the embeddings learned by node2vec. Our main result shows that the use of k-means
clustering on the embedding vectors produced by node2vec gives weakly consistent community recovery
for the nodes in (degree corrected) stochastic block models. We also discuss the use of these embeddings
for node and link prediction tasks. We demonstrate this result empirically for both
real and simulated networks, and examine how this relates
to other embedding tools for network data.

Community Detection Guarantees using Embeddings Learned by Node2Vec
Andrew Davison Department of Statistics Columbia University
Carlyle Morgan
Department of Statistics University of Michigan Ann Arbor, MA 48 109 scmorgan@umi
New York, NY 10027 ad3395@columbia. edu
Owen G. Ward
Department of Statistics and Actuarial Science
Simon Fraser University Burnaby, British Columbia owen_ward@sfu. ca.
Abstract
Embedding the nodes of a large network into an Euclidean space is common objective modern machine learning, with a variety of tools available. These em- beddings can then be used as features for tasks such as community detection/node clustering or link prediction, where they achieve state of the art performance. With the exception of spectral clustering methods, there is little theoretical understanding for commonly used approaches learning embeddings. the theoretical properties of the embeddings learned by node2vec. Our main result shows that the use of k-means clustering on the embedding vectors produced by node2vec gives weakly consistent community recovery for the nodes in (degree corrected) stochastic block models. We demonstrate this result empirically for both real and simulated networks, and examine how this relates to other embedding tools and machine learning procedures for network data.
this work we examine
Introduction
Within network science, widely applicable and important inference task is to understand how the behavior of interactions between different units (nodes) within the network depend on their latent characteristics. This occurs within wide array of disciplines, from sociological [14] biological 33 networks.
One simple and interpretable model for such task is the stochastic block model (SBM) (00 which assumes that nodes within the network are assigned a discrete community label. Edges between nodes in the network are then formed independently across all pairs of edges, conditional on these community assignments. While such a model is simplistic, various extensions have been proposed. These include the degree corrected SBM (DCSBM), used to handle degree heterogenity (3], and membersipp SBMs, used to allow for more complex community structures These extensions have seen wide degree of empirical success 26 28
restriction of the stochastic block model and its generalizations is the requirement for a discrete community assignment as latent representation of the units within the network. While the statistical community has previously considered more flexible latent representations [19], over the past decade, there have been significant advancements in general embedding methods for networks. These produce
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

general vector representations of units within a network, and can achieve start-of of-the-art performance downstream tasks for node classification and link prediction.
An early example of such a method is spectral clustering [37], which constructs an embedding of the nodes in the network from an eigendecomposition of the graph Laplacian. The k smallest cigenvectors provides a A dimensional representation of each of the nodes in the network. This has been shown to allow consistent community recovery [30], however it may not be computationally feasible on the large networks which are now common. More recently, machine learning methods for producing vector representations have sought inspiration from NLP methods and the broader machine learning literature, such as the node2vec algorithm [16], graph convolutional networks [51], graph attention networks [46] and others. There are now wide class of embedding methods which are available to practitioners which can be applied across mixture of unsupervised and supervised settings. 8 provides a survey of relatively recent developments and [49 reviews the connection between the embedding procedure and the potential downstream task.
Embedding methods such Deepwalk [38] and node2vec [16] consider random walks on the graph, where the probability of such a walk is a function of the embedding of the associated nodes. Given embedding vectors Wa, We Ra of nodes u and v respectively, from graph & with vertex set V, the probability of a random walk from node u to node v is modeled as
exp( Wr)) P(vlu) Eiev exp( (.)))
where (x, y) is the inner product of z and y. This leads to representation of each of the nodes in the network as a vector in d dimensional Fuclidean space. This representation is then amenable to potential downstream tasks about the network. For example, if we wish cluster the nodes in the network we can simply cluster their embedding vectors. Or, if we wish to classify the nodes in the network, we can use these embeddings to construct multinomial classifier. We note that the sampling schemes introduced by Deep Walk and node2vec motivate more complex models such as GraphSAGI [17] and Deep Graph Infomax 47, which utilise similar node sampling schemes for learning embeddings of networks.
As such, one of the key goals of learning vector representations of the units within networks is to allow for easy use for a multitude of downstream tasks. However, there is little theoretical understanding to what information is carried within these representations, and whether they be applied successfully and efficiently to downstream tasks. This paper aims to address this gap by examining whether learned embeddings can facilitate community detection tasks in unsupervised setting.
1.1 Summary of main results
Our main contribution to describe the asymptotic distribution of the embeddings learned by the node2vec procedure, and to then use this to give consistency guarantees when these embeddings are used for community detection. A simple and informal form of our results, the scenario of balanced two block stochastic block model (SBM), is given below:
Theorem 1. (Informal) Suppose observe sequence of graphs Gn n vertices arising from a two-dimensional stochastic block model: for each vertex u E [n] we assign a community label c(u) E {0,1) 1} with equal probability, and then form edges in the graph independently with probability
{{a { (c(u)=c(() =
(P(u and u are connected) = otherwise
where ğ + q. Suppose that (aa) are two-dimensional embeddings learned by node2vec on the above graph (where we hide the dependence on n). Then there exists some distinct vectors Ne(u) E IR2 such that
1 n I ue(ui)l 0 in probability as n. - CO.
Consequently, if we apply a k-means algorithm to the embeddings learned via node2vec, as n. oo we will classify at least 100(1- - 3)% of vertices to the correct community (up to permutation) with asymptotic probability 1. for any 0.
2

---

We give formal theorem statements, complete with full conditions, in Section we note that our results extend to graph models beyond SBMs and are not limited to the dense regime. To give some brief intuition for the method of proof, we show that the probability that a pair (u, v) is positively or negatively sampled within node2vec concentrates around a function which depends only on the underlying communities c(u) and c(v) of u and v. With this, we are able to argue that the 2ede2vec loss concentrates uniformly (in a neighborhood of their minima) around a function whose minima M is such that M M(( for some matrix M. This allows us to show that any set of embeddings which minimize the node2vec loss will converge (up rotation) to vectors which depend only on the community label, which consequently allows us to give consistency guarantees for clustering algorithms such as k-means.
We highlight that while the theoretical properties of spectral clustering are well studied in the literature, there relatively few theoretical guarantees provided for more modern embedding procedures such as node2vec. Our work provides some of the first theoretical results for models of this form. Our main contributions are the following:
We give convergence guarantees for embeddings learned via node2vec, under various sparsity regimes of (degree corrected) stochastic block models. We then use this to give weak consistency guarantees for community detection, when using the embeddings as features within a k-means clustering algorithm.
ii) We verify the theoretical guarantees for simulated networks and examine the the performance of this procedure on real networks. We also empirically investigate important extensions these theoretical results, relating to rates of recovery for community detection between node2vec and spectral clustering methods. We identify that as these networks grow the sampling parameters node2vec have little impact on the performance of the proposed procedure.
The layout of the paper is follows. In Section 2 we formulate the problem of constructing an embedding of the nodes in a network and state the criterion under which we consider community detection. In Section 3 we give the main result of this paper, the conditions under which k-means clustering of the node2vec embedding of a network gives consistent community recovery. In Section we verify these theoretical results empirically and investigate potential further results. In Section we summarize our contributions and consider potential extensions.
1.2 Related Works
Community detection for networks is widely studied area with large literature of existing work. Several notions of theoretical guarantees for community recovery are provided in [1, along with a survey of many existing approaches. There are many existing works which consider the embeddings obtained from the eigenvectors of the adjacency matrix of Laplacian of a network. For example, [30] considers spectral clustering using the eigenvectors of the adjacency matrix for stochastic block model. Spectral clustering has provided such guarantees for a wide variety of network models, including 35| 12
32 29).
With the more recent development of random walk based embeddings, several recent works have begun to examine the theoretical properties of such embeddings, however the treatment is limited compared to spectral embeddings. 440 study the global minimizers of the node2vec loss in the setting matrix factorization problem. If M* is the global minimizing
where d = n. viewing the problem matrix, we highlight that their results apply for any d 2 rank(M*) That said, this minimizer equals the entrywise logarithm of functions of the adjacency matrix A; we note that entrywise logarithms of matrices typically blow up their rank, and that even when "in expectation" the adjacency matrix is of low rank, the actual adjacency matrix is of full rank with high probability [7]. This means that it is unlikely when d < n that the global minimizer is the actual minimizer, which is the regime where embedding dimensions are considered in practice. We contrast that with our results, where we can take d = ((k where e is the number of communities, and obtain rigorous guarantees for the embeddings.
52 then studies the concentration of the best rank d approximation (with respect to the Frobenius norm) of the matrix M about it's expected value under SBM and DCSBM models for node2vec with p = = only, to argue that the best rank d approximation can be used for strongly consistent community detection. We note that our results can be applied to node2vec without this restriction on
3

---

the hyperparameters. Otherwise, they give similar types of guarantees as our paper in similar sparsity regimes and with similar rates, but stronger norms. The key difference between our work and that of [52 is that we are able to give guarantees for the the actual minimizers of the node2vec loss as soon as (1)),, whereas [52] use an approximation to the global minimizer, without studying the gap between this matrix and any minimizer of the node2vec loss (which is cross-entropy loss, and therefore difficult to relate to a Frobenius norm approximation). [0] and [T] study node2vec with in the constrained setting (where U = V), and focus on giving more abstract guarantees for the gram matrix in the setting of graphons. In [ the norm guarantees extend only to the L norm between the gram matrix of the embeddings and the minimizer, which is not sufficient to give guarantees on the individual embeddings. In [10] the norm guarantees are upgraded to the L2 norm, albeit with less optimal rates of convergence than what we show here. Our results also give guarantees for node2vee in full generality (no restriction on p and g) and give the calculation details for SBMs and DCSBMs to explicitly describe the asymptotic distribution in certain regimes.
2 Framework
We consider a network 9 consisting of a vertex set V of size n and edge set &. We can express this also using an n x n symmetric adjacency matrix A, where Aur = 1 indicates there is an undirected edge between node and node v, with Aue 0 otherwise, where such a network, we wish to examine models for community structure of the nodes the network. We then examine the embeddings which can be obtained from node2vec and examine how they can be used for community detection.
E V. Given realisation of
2.1 Probabilistic models for community detection
The most widely studied statistical model for community detection is the Stochastic Block Model (SBM) 20 The SBM specifies a distribution for the communities, placing each of the n nodes into one of communities, where these community assignments are drawn from some categorical distribution Categorical Writing c(u) E [x] for the community u, the connection probabilities between edges are independent, conditional on these community assignments, with probability
IP(Awe = 1/((w),((v) = Pn (()))
(4)
where P is a x A matrix of probabilities, and Pv. is the overall network sparsity (so that the network has (p edges on average). As special case, the planted-partiiin model considers P as being a matrix with p along its diagonal and the value elsewhere, with k equally balanced communities, so π (x .K...." 1) We will denote such a model by SBM(n, K. P. q. Pn).
The most widely studied extension of the SBM is to incorporate a degree correction, equipping each node with non negative degree parameter fn drawn from some distribution independently of the community assignments
[4. This alters the previous model, instead giving
P(A I(((u), c(v), On, 0.) = Pr.,,O,Po(uu).ceo
(5)
Degree corrected SBM models can be more appropriate for modeling the degree heterogeneity seen within communities in real world network data [23].
Performance of stochastic block models is assessed in terms of their ability to recover the true community assignments of the nodes in a network, from the observed adjacency matrix A. Given an estimated community assignment vector é E [k]] and the true communities then can compute the agreement hetween these two assignment vectors, up to a relabeling of c, as
L(C,
min Σ ( + a(((i))]
(6)
oeS, n
where S, denotes the symmetric group of permutations a [s] - [s]. We can also control the worst-case misclassification rate across all the different communities. If C. is the set of nodes belonging to community k; then this is defined as
L(c, c) max min
Σ 1 + [kk)
kEja oES.
|Cx|
ieC

---

Guarantees of the form L(č, c) (1) as n - oo are known as weak consistency guarantees in the community detection literature. Strong consistency considers the stronger setting where L(c, with asymptotic probability 1. [ provides review of results for guarantees of these forms. In this work we consider only the weak consistency setting; we highlight that stricter assumptions are necessary in order to give these type of guarantees.
2.2 Obtaining embeddings from node2vec
Machine learning methods such as node2vec aim obtain an embedding each node network. In general, for each node two d-dimensional embedding vectors are learned, centered representation Wi Id and a context representation W; IR. node2vec modifies the simple random walk considered in DeepWalk (38], incorporating tuning parameters p, which encourage the walk to return to previously sampled nodes or transition to new nodes. Formally, this defined by sampling concurrent pairs of vertices in the second-order random walk (Xa)n21 defined via
0
if (u, 8) E if du.r 0 and (u, 8) E E if du, 1 and (u, 8) E,
1/p
P(X,. = LuuuNnn =,, 8n v) x
(8)
1
1/q
if du. and (u, s) E E.
where a denotes the length of the shortest path between u and s, after selecting some initial two vertices. Here we consider the case where (Xo, X2,) is drawn uniformly from the set of edges in order to initialize the walk. We note that when down simple random walk, in which case the initial distribution samples vertex proportionally to their degree.
= 1, corresponding to DeepWalk, this reduces
A negative sampling approach is also used to approximate the computationally intractable loss function, replacing - (vv()) in with
- log a (Wi. (.)) - Σ log or (- (Wer Wn,)),
(9)
where (2) (1+6->)-1, the sigmoid function. The vertices n1..... ny are sampled according to negative sampling distribution, which we denote as Pro(-lu). This is usually chosen as the unigram distribution,
deg(v)"
P(ulu) Evey deg(v')a'
(10)
which does not depend on the current location of the random walk, u. This unigram distribution has parameter a, which is commonly chosen as 3/4, was used by word2vec (36). Given this, and using ( the loss considered by node2vec for random walk of length can be written as
K+1 =Σ
Σ
log or (WWr, 2e,1)
Σ Emg- (11,,) (too..) log ol (Wo, 2mm))) @w))))))mi)) 1=1
(11)
Here we use (m.-P...((or)) to denote the procedure to sample a draw from the negative sampling distribution, with W commonly chosen. Given this loss function, stochastic gradient updates are used to estimate the embedding vector for each node. This amounts to minimizing empirical risk function (e.g 4T 451), which we can write as
(U. = Σ ( (..(()))) (o)) -,))) E log(1)o w,)))} (12)
where P (,,()) := 10 and P P(Gn) and N = (V.... are sets of positive and negative samples respectively. We consider a sequence of graphs Gn with | and study the behavior of this loss function when n is large.
explicit, P,,, (T,( E P) denotes the probability (conditional on realization of the graph) that the vertices (i,j) appear concurrently within random walk of length k, and IP,, ((i.j) E ) denotes the probability that (i,j) is selected as pair of edges through the negative sampling scheme (conditional on the random walk process in the first stage).
5

---

The loss depends on two matrices U, V.V& E Raxd, with ug 1/ E R2 denoting the i-th and j-th rows of U and V respectively. The rows of U correspond the "centered representations" of each node, while the rows of V correspond to the "context representation" (borrowing the terminology used by practice we can constrain the embedding vectors u4 and t; to equal we wish; we will consider both approaches in this paper. (If these are not constrained to be equal, the centered representation commonly used for downstream tasks.) We highlight Equation (12) is defined only as a function of UV" There are two potential approaches to deal with this. We can regularize the objective function to enforce U = V"V, which does not change the matrix UV? that we recover [53]. Alternatively, if these matrices initialized to be balanced then they will remain balanced during the gradient descent procedure [34]. Either procedure can be used to implicitly enforce U VTV, which reduces the symmetry group of (U, V) + UV to the orthogonal group. Similarly, if we constrain U = V then we obtain the same reduction.
e-g Word2Vec).
2.3 Using embeddings for community detection
Having learned embedding vectors wi for each node, we seek to use them for a further task, such as node clustering or classification. For community detection a natural procedure is to perform k-means clustering on the embedding vectors, using the estimated cluster assignments as inferred communities. k-means clustering [18] aims to find & vectors 2i.... .......... I E Id which minimize the within cluster sum of squares. This can be formulated terms of a matrix X E gxxd and a membership matrix O E {0, 1 1|n** where each row of ( has exactly k 1 zero entries. Then the k-means clustering objective can be written as
1 1 e 71
Lk-maans (0,
(13)
where Ω E RRa is the matrix whose rows are the Wj. The non-zero entries in each row of θ gives the estimated community assignments. Finding exact minima this minimization problem NP-hard in general [5). For theoretical purposes, we will give guarantees for any (1 + e)-minimizer to the above
problem, which returns any pair (Ô, X) for which Lx-maans (, s (1 mine, Lk-means ( X). and can be solved efficiently [25].
3 Results
Within this section, we give theoretical results which allow us to describe what happens when we use node2vec to learn embedding vectors for each node in the network, and then use these as features for a k-means clustering algorithm to perform community detection. Throughout, we assume that observe sequence of graphs (G,)
n vertices drawn from probabilistic model and fit node2vec model, according to one of the three scenarios below:
(i) We use DeepWalk (p = q = 1 in node2vec), and the graph is drawn according to a SBM with Pn >> log(n)/n;
(ii) We node2vec, and the graph is drawn according to SBM with Pr. na for some a < a', where a' depends on node2vec's hyperparameters;
(iii) We use DeepWalk and a unigram parameter of a = 1, and the graph is drawn according to a DCSBM with Pn > log(n)/n where the degree heterogeneity parameters 0., [C--_ C] for some C' < oc.
All probabilistic statements below are with respect to the joint law of 9n and the sampling which occurs to form the node2vec loss. All proofs are deferred the Appendix. There also provide extensions for the tasks of node classification and link prediction.
3.1 Asymptotic distribution of the embeddings
We begin with result which describes the asymptotic distribution of the gram matrices formed by the embeddings which minmmize the loss L.. V) over matrices U, V E RRd
Theorem There exist constants Aso and Az,so (depending on n, and the sampling scheme) and matrix M* xxx (also depending π, P and the sampling scheme) such that when d 2 rk(M"")

---

for any minimizer (U*, V*) of V) over X x X where
X = E Ruxd ; |10| s Aoo: ||0| S Azoai:
we have that
M Maw)aan)= C. SOp(( (1())
( max n.d) 1122) under scenarios (i) and (iii);
1 Σ LgE(m]
nPn
n
under scenario (ii);
where C a constant depending on the (DC)SBM parameters, the node2vec hyperparameters, Age and 22. In the case where we constrain U V within node2vec, the same result holds under scenarios i) and ii). Moreover, under all scenarios can allow the number of communities k to grow with n provided is = o(npa) and still maintain consistency as n -> DC.
To give some intuition, we describe the form of M when the graph arises from a SBM((n, K. K, Pa) model when using DeepWalk. In this case, we show in the Appendix that
Min a 6im + 8 6tm) for L, m [x]
for some constants and 3 and 6tm is the Kronecker delta. In the unconstrained case we have that
kP
Kq
a' = log 1 k (R 1) 8 = log k p+ -+
(14)
In the constrained case we instead have that 8 = -a" /(s 1), and that a" is function of p/g which is non-negative iff p q, and equals zero when p S q. With regards to the constants Aox and Az,c, we have that || (()og((//a))) Additionally, it is possible to write M = U (VM) ) where ||U o0 and || oo upper bounded by (([((p//))))/)) In particular, this means that Axe and A2 do not have any implicit dependence is not affecting the rate here.
ic, and so the constant in Theorem)
While Theorem gives guarantees from the gram matrices formed by the embeddings, in practice we want guarantees for the actual embedding vectors themselves. For convenience we suppose that the embedding dimension is chosen exactly be the rank of M upon doing so, can then obtain guarantees for the embedding vectors themselves. We recall that in the unconstrained case, implicitly suppose that we find embedding matrices U and V which are balanced in that (U*)"U* = (V*)TV*. """
Theorem 3. Suppose that the conclusion of Theorem holds, and further suppose that d equals the rank of the matrix M". Then there exists matrix Ü+ Rxxd such that
|ut T. 012 = C c.fo SO
max 22/2)
under scenarios (i) and (iii; (15) under scenario (ii);
min QEO(d) n
(1,,(1)
3.2 Guarantees for community detection
With Theorem 3 we are now in a position to give guarantees for machine learning methods which the embeddings features for downstream task. We only discuss using the embeddings for clustering; in Appendix D.2 we discuss what can be said for other downstream tasks.
Theorem 4. Suppose that we have embedding vectors iy E Rd for E [n]] such that
min QEO(d) n
Σ
Th ((1) Q11 = (r(rr))
(16)
for some rate function Fa -
30 and vectors ni Rd for [x]. Moreover suppose that 5 := ming l|ū ū l2 > 0. Then if c(i) is the community assignment of node produced by the matrix whose columns are the
applying (1 (1+6 -pprroximmtt k-means clustering with k.
u, we have that L(c,ê) = (8 2r,) and L(c. é) = Op(8-2 rr.). In the case where the RHS of
16 is only (1) instead, then instead L(c, é) and L(c, c, è) are 8 8-2 (,))
7

---

Within the SBM(n. K. P. q. Px) model, we can show in the unconstrained case that 8² @ (()())) and in the constrained case that 8² (((p/)). As a result, this suggests that as p/ú approaches 1, the task of distinguishing the communities becomes more difficult. This is inline with basic intuition, along with our experimental results in Section [ We note that, due to the nature of the embedding vectors, for any proportion of vertices arbitrarily close to 1, the nodes will, with high probability for sufficiently large n, be separated in the embedding space according to their community assignments. This separation allows clustering methods, such as DBSCAN, to accurately recover the communities of these nodes also.
Recall that from the discussion before, we know that M equals the zero matrix in the constrained regime when á I q (and therefore the embeddings asymptotically contain no information about the network). As in the case where p > q we can show that ō > O, we get the immediate corollary.
Corollary 5. Under scenario (i), suppose the embedding vectors learned through the node2vee vec loss are oblained by constraining the embedding matrices U = V. Then the embeddings can be used for weakly consistent recovery of the communitiies if and only i >> q.
As result, the constrained model can be disadvantageous if used without a-priori knowledge of the network beforehand (in that within-community connections outnumber -commntyy connections), even though it avoids interpretability issues about which embedding vector should be used as single representation for the node.
4 Experiments
In this section we provide simulation and real data experiments to empirically validate the previous theoretical results. We demonstrate the performance, in terms of community detection, of k-means clustering of the embedding vectors learned by node2vec, for both the regular and degree corrected stochastic block model. We also investigate the role of the negative sampling parameter a and the node2vec tuning parameters p and q, before examining performance real network with known community structure.
We first simulate data from the planted partition stochastic block model, SBM(n/K, k. P, (.))). We consider q = 53 for a range of values of [ < 1, giving varying strengths of associative community structure. In each setting we vary both the number of true communities present and the number of nodes in each community, considering n = 200 to n 5000 and K 2, 3, 4, 5. We use node2vee to construct an embedding of the nodes in the network. We use an embedding dimension of 64 and do not modify other default tuning parameters for the embedding procedure unless specified, so that p = q 1. We investigate the role of these tuning parameters below, allowing them to vary as is considered in node2vec. We pass these embedding vectors into k-means clustering, where k = k. the true number of communities present in the network. This estimates community assignment for each of the nodes in the network.
To evaluate the performance of our procedure, we compute the proportion of nodes correctly classified, up to permutation of the community assignments. For each simulation setting we perform 10 replications. We show the resulting estimates in Figure [[)) for the relatively sparse setting where Pn = log(n)/n. For all settings, the proportion of nodes assigned to the correct community by k-means clustering of the node2vec embeddings is high, particularly when the ratio of the between to within community edge probabilities, B, is small. As expected, as we increase the number of nodes in the network, larger proportion of nodes are correctly recovered. We examine the empirical rate of convergence of this procedure in the Appendix. This appears to be approximately super-linear for dense networks and sub-linear for relatively sparse networks. Compared to the results of [50), this indicates that node2vec may be supoptimal. In the Appendix we also show community recovery using normalized mutual information (NMI) [9. We also see good performance.
We can similarly evaluate the performance of node2vec for data generated from a degree corrected SBM (DC-SBM). To generate such networks we modify the simulation setting used by [15. We generate the degree correction parameters 02 = |Zul + - (2m)-1/² where Z,, ~ N NN0, a = 0.25) and incorporate these into the SBM(n/ K. P. q. Pn) considered previously. Two nodes u and v the same community will have connection probability 0.0.pnP while for nodes in different communities
'e use the implementation of node2vec available at https:: httpt/..cooo/aoor////eeeeeeeeeee without any modifications.
8

---

2=
K=8
k=
K=3
0.75
0.75
0.50
0.50
Prop Recovered
0.25
Prop Recovered
0.25
K=5
0.06
K
K 5
0.06
1.00
0.1
0.1
0.15
0:15
0.50
0.50
0.25
0.25
100
1000
500
1000
100
500
1000
100
1000
Nodes per Community
Nodes per Community
(a) A relatively sparse SBM.
(b) A degree corrected relatively sparse SBM.
Figure 1: Proportion of nodes correctly recovered for both the regular and degree corrected relatively sparse SBM.
will be OnO. We again learn an embedding of the nodes using default implementation of node2vec and cluster these embedding vectors using k-means clustering. We show the corresponding results, in terms of the proportion of the nodes assigned to their correct communities under this setting in Figure As expected, the degree corrections make community recovery somewhat more challenging however as we increase the number of nodes in the network, we are able to correctly recover high proportion of nodes.
We next wish examine empirically the role of the unigram parameter a of Equation TT). and how this affects community detection. While the previous theoretical results require a for weak consistency of community recovery the DC-SBM, we investigate if good empirical performance is possible with other choices of this parameter. We consider the DC-SBM simulation described previously, where we now vary (- 0.25, 0.5, 0.75, 1} when learning the node embeddings. consider the proportion of nodes
For each of these settings (with all other parameters before) correctly recovered. We show this result for networks with k = 2 communities in Figure 2 These experiments indicate similar performance for range of values of a. Further work is needed to confirm the guarantees do indeed extend to these alternative choices of a, and we investigate this for real networks in Section A of the appendix.
We also investigate the role of the node2vec tuning parameters p and on performance. For we consider 3 = 0.01 and 3 0.2, giving networks with strong and weak associative community structure respectively. We simulate from the previous relatively sparse DC-SBM with varying numbers of nodes and fit node2vec, using p, E (0.5. 1, As the number of nodes in the network increases all choices of p and give similar good performance for both choices B. This indicates that the impact of these sampling parameters becomes limited as the networks become sufficiently large. We provide further discussion and a visualization of this result in Appendix A.
Finally, we briefly examine the performance of our community detection procedure on the political blog data collected by (2). As highlighted by (33), degree heterogeneity makes community recovery challenging for methods which do not account for this. We see similar performance if we cluster using a Gaussian mixture model rather than k-means clustering. In particular, spectral clustering struggles regardless of the graph Laplacian used. Our procedure shows excellent community recovery (average NMT of 0.75) for range of embedding dimensions and unigram parameter settings as shown with further details and additional real network example in Appendix A.
in Figure 3

---

0.25
1,0
1.00
0.8
0.75
Prop. Recovered
4/3
0.7
0.01
NM
0.02
0.50
cz-
0.5
0x
0.75
0. -
0.05
1.0
0.15
0.9
0.25
0.00
0.7
Spectral Clustering
100
500
1000
100
500
1000
100
500
1000
Nodes per Community
Figure 3: Node2vec with k- means clustering the communities in the political blog data while spectral cluster- ing fails.
recover
Figure 2: Proportion of nodes correctly recovered as we vary the negative sampling parameter in node2vec with mean and one standard error for each setting. We see similar performance for each choice of a.
5 Conclusion and Future Work
In this work we consider the theoretical properties of node embeddings learned from node2vec. We show, when the network is generated from a (degree corrected) stochastic block model, that the embeddings learned from Deep Walk and node2vec converge asymptotically to vectors depending only on their community assignment. As result, we show that K-means clustering of the node2vec embedding vectors can provide weakly consistent estimates of the true community assignments of the nodes the network. We verify these results empirically using simulated networks.
There are several important future directions which can extend this work. One direction in extending the recovery results within the degree corrected SBM to the full range of hyperparmaeters for node2vec, as our simulation studies indicate that more general result may hold. There is also the matter of increasing the strength of our results to give better rates and strongly consistent community detection; one possible avenue of exploration would be to see whether our results and the results of [22 could be combined to achieve this. Another improvement would be study the behavior of the random walk on the graph in the sparse regime, although this would require generalization of e.g the result of [13]. We have also not considered the task of estimating K, the number of communities in SBM model, using the embeddings obtained by node2vec. This has been considered for alternative approaches to community detection, (22 27 are some recent results) but not the context of general embedding of the nodes. Finally, there is a desire to obtain consistency results for more recent
and complex network embedding methods, such as and
References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of 2017.
Machine Learning Research,
[2] Lada A. Adamic and Natalie Glance. The political blogosphere and the 2004 u.s. election: divided they blog. In Proceedings the 3rd International Workshop Link Discovery, LinkKDD '05, page 33.43. New York, NY. USA, 2005. Association for Computing Machinery. ISBN 1595932151. doi: 10.1145/1 134271. 13347.7 URI htttp:://oi...... org/10.
1134277
[3] Edoardo M Airoldi, David M. Blei, Stephen E. Fienberg. Eric P. Xing. and Tommi Jaakkola. Mixed membership stochastic block models for relational data with application to protein-protein interactions. In Proceedings of the international biometrics society annual meeting, volume 15, page 1, 2006.
10

---

[4] Edoardo M Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. Mixed membership stochastic blockmodels. Advances in neural information processing systems, 21, 2008
[5] Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. NP-hardness of Euclidean sum-of- squares clustering. Machine Learming, 75(2):245-24) 248. May 2009. ISSN 1573-0565. doi: 10.1007/ 110994-009-51033 httLtttp::///ooo wttp://///oooooo/////////////o// org/10. 1007/ 019--0
[6] Béla Bollobás. Threshold functions for small subgraphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 90, pages 197-206. Cambridge University Press, 1981.
[7] Kevin P. Costello and Van H. Vu. The rank of random graphs. Random Structures & Algorithms, 33(3): 269 269. 2008 doi: http:://oi.orr//III wtt..or//.0.00///a..00000000 doi/abs/10 1002/rsa. 20219
URL BRLLittts///ooliieliiiraa wile...rrrwiii.coooo..oo..e.... com/
[8] Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu, survey on network embedding. IEEE transactions on knowledge and data engineering, 31(5):833-88) 852, 2018.
[9] Leon Danon, Albert Diaz-Guilera, Jordi Duch, and Alex Arenas. Comparing community structure identification. Journal of statistical mechanics: Theory and experiment, 2005(09): 2005.
[10] Andrew Davison. Asymptotics of f_2 regularized network embeddings. Advances in Neural Information Processing Systems, 35:24960-24974 2022.
[11] Andrew Davison and Morgane Austern, Asymptotics of network embedkings learned via subsampling. Journal of Machine Learning Research, 141138):1-120, 2023.
[12] Shaofeng Deng, Shuyang Ling, and Thomas Strohmer. Strong consistency, graph laplacians, and the stochastic block model. The Journal of Machine Learning Research, 22(1):5210-525. 2021.
[13] Jian Ding, Eyal Lubetzky, and Yuval Peres. Anatomy of the giant component: The strictly supercritical regime. Eur. J. Comb. 35:155-168, January 2014. ISSN 0195-6698. doi: 10. 00.1016fj..c.22013.6..00 URL.
https: //ooi. org/10. nrrg/10.10 1016/j ejc. 2013. 16.06..000 .0.004
[14] Linton Freeman. The development of social network analysis. A Study in the Sociology of Science, 1(687); 159-167, 2004.
[15] Chao Gao, Zongming Ma, Anderson Y. Zhang, and Harrison H. Zhou. Community detection in degree- corrected block models. The Annals of Statistics, 46(5):2153 2185, 2018. doi: 10.1214/17-ASS1115 /tt.ptttps///oo..or 1tt.://..00/111111177---03030330
[16] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[17] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[18] John A Hartigan and Manchek A Wong. Algorithm 136: k-means clustering algorithm. Journal of the royal statistical society. series c (applied statistics), 28(1):100-108, 1979.
[19] Peter Hoff, Adrian Raftery, Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 10900000,,, 2002.
[20] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2): 109-137, 1983.
[21] Roger A. Horn and Charles Johnson. Matrix Analysis. Cambridge University Press, New York, NY. USA, 2nd edition, 2012. ISBN 978-0-521-54823-6
[22] Jiashun Jin, Zheng Tracy Ke, Shengming Luo, and Minzhe Wang. Optimal estimation of the number of network communities. Journal of the American Statistical Association, pages 1 1-16, 2022.
[23] Brian Karrer and Mark Newman. Stochastic blockmodels and community structure in networks. Physical review E, (3110116, 2011.
[24] Vladimir Koltchinskii and Evarist Giné, Random Matrix Approximation of Spectra of Integral Operators. Bermoulli, 611) 167, 2000. ISSN 1350-7265. doi: 10.2307/3318636 URL utLhhtpp:/ /ttttp://ww... http://ww..sstt. jstor org/ stable/ Stable/33186333 3318636 Number: 1 Publisher: International Statistical Institute (ISI) and Bernouli Society for
Mathematical Statistics and Probability.

---

[25] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear Time Algorithms for Clustering Problems in Any Dimensions. In Luís Caires, Giuseppe Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung. editors, Automata, Languages and Programming, Lecture Notes in Computer Science, pages 1374-1385, Berlin, Hcidelberg, 2005. Springer. ISBN 978-3-540-31691-6 doi: 1.11007/1153366,,
[26] Pierre Latouche, Etienne Birmelé, and Christophe Ambroise. Overlapping stochastic block models with application to the French political blogosphere. The Annals of Applied Statistics, 5(1):309 - 336, 2011. doi: 0..111410-A0ASS66
httLhhtps:/// :/tpss://doi... org/ 10. 1214/10-11- ADAS382.
[27] Can M Le and Elizaveta Levina. Estimating the number of communities by spectral methods. Electronic Journal of Statistics, 16(1)3331-3333 2022.
[28] Sirio I Legramanti, Tommaso Rigon, Danicle Durante, and David B Dunson. Extended stochastic block models with application criminal networks. The Annals of Applied Statistics, 16(4):2369, 2022.
[29] Jing Lei. Network representation using graph root distributions. The Annals of Stotistics, 49(2):745 768. 2021.
[30] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1):215 237, 2015. doi: 10.121414-A0S1274, /t//ttts:://dbo.orr///
1214/14- 1144/14-A00 A4411774
[31] Jure Leskovee and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. //anap. comap.stanfors. stw.sfrrd...........m...oo edu/data June 2014.
http
[32] Keith D Levin, Fred Roosta, Minh Tang, Michael W Mahoney, and Carey E Priebe. Limit theorems for out-of-sample extensions of the adjacency and laplacian spectral embeddings. The Journal of Machine Learning Rexearch, 22 221):8777-8765, 2021.
[33] Feng Luo, Yunfeng Yang. Chin-Fu Chen, Roger Chang, Jizhong Zhou, and Richard H Scheuermann. Modular organization of protein interaction networks. Bioinformatics, 23(2):207-214, 2007.
[34] Cong Ma, Yuanxin Li, and Yuejie Chi. Beyond procrustes: Balancing-free gradient descent for asymmetric low-rank matrix sensing. IEEE Transactions on Signal Processing, 69:867-877, 2021.
[35] Shujie Ma, Liangjun Su, and Yichong Zhang. Determining the number of communities in degree-corrected stochastic block models. The Journal of Machine Learning Research, (2(1):32173327, 2021.
[36] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26,
2013.
[37] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing rystems, 14, 2001.
[38] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pages 701-710, 2014.
[39] Yannik Pitcan. A note on concentration incqualities for u-statistics, 2019.
[40] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang. and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the eleventh ACM international conference on web search and data mining, pages 459 467,447, 2018.
[41] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 400444400- September 1951. ISSN 0003-4851, 2168-8990. doi: 10. /114///m//1177729555
URL Lssuse3/A-Stoccassti---ppp httppaasiee--ppprprraaaaaaaaaaaa 1200/0.21112200 atth///mm/////// 1t514//0mm/1177725555
volume-22 22/
full Number: 3 Publisher: Institute of Mathematical Statisties.
[42] P Rubin-Delanchy, CE Priebe, M Tang, and J Cape. statistical interpretation of spectral embedding: the generalised random dot product graph. arxiv e-prints. arXiv prepriin 1709: 05506, 2017.
[43] Michel Talagrand. Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge A Series of Modern Surveys in Mathematics. Springer-Vette Berlin Heidelberg, 2014. ISBN 978-3-642-5507777 54074-5
doi: 1001
978-3-642.
httLhtts::///ee httt::://wwwwsprnngerr wwtp://pp/bo...///8//5333.//////
12

---

[44] Stephen Tu, Ross Boczar. Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank Solutions of Linear Matrix Equations via Procrustes Flow. In Proceedings The 33rd International Conference on Machine Learning, pages 964-973, PMLR, June 2016, URL https::/ mlr, pll....ree//v88/
tu16.html ISSN: 1938-7228.
[45] Vietor Veitch, Morgane Austemn Wenda Zhou, David M Blei, and Peter Orbanz. Empirical risk minimiza- tion and stochastic gradient descent for relational data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1733-1742. PMLR, 2019.
[46] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
[47] Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep Graph Infomax. orXiv:1809. 1034/ [cs, math, stat), December 2018. URL http:///://rri org abs/ Abs/1809.0 10341
arXiv: 1809.10341.
[48] V. H. Vu. Concentration of non non-lipschitz functions and applications. Random Structures & Algoritims. 20(3):262-316, 2002. doi: https://oii.org otg/ 1002/rsa. 10032. URL http:/ccss//onnnnellirreeee wiley
com/do3/aba/10.1t 1002/00a....... 10032
[49] Owen G Ward, Zhen Huang, Andrew Davison, and Tian Zheng. Next waves in veridical network embedding. Statistical Analysis and Data Mining: The ASA Data Science Journal, 14(1):5 17, 2021.
[50] Anderson Ye Zhang. Fundamental limits of spectral clustering in stochastic block models. arXiv preprint (oXiv:3301.0929,, 2023.
[51] Si Zhang. Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: compre- hensive review. Computational Social Nenworks, 6(1):1-23, 2019.
[52] Yichi Zhang and Minh Tang. theoretical analysis of deepwalk and node2vec for exact recovery of community structures stochastic blockmodels. IEEE Transactions Pattern Analysis and Machine Intelligence, 46(2):1065 1078, 2024. doi: 10. 2000/TTAA..2022333322222
[53] Zhihui Zhu, Qiuwei Li, Gongguo Tang, Michael Wakin. The global optimization geometry of low-rank matrix optimization. IEEE Transactions on Information Theory, 67(2): 308-1331, 2021.
13

---

Appendix - Community Detection Guarantees using Embeddings Learned by Node2Vec
The Appendix consists of the proofs of the results stated within the paper, along with some extra discussions which would detract from the flow of the main paper. We also provide some additional simulation results relating to node classification, and further simulated and real data experiments examining community detection.
A Additional Experimental Results
Here we provide additional details describing the experimental results presented in the main paper. We also describe additional experiments. All experiments were run computing cluster utilising 4 cores of an Intel E5-2683 v4 Broadwell 2.1GHz CPU or similar with 2 GB memory per core. Each individual experimental
required at most hours of computing time. All experiments, including initial preliminary experiments, required approximately 25k CPU hours. All code required reproduce all results is included in the code repository in the supplemental files.
Additional Simulation, Node Classification We provide a simple experiment to support the theoretical results on node classification demonstrated in Section D of the appendix. We simulate data from a SBM(n// K. p, q Pr)) before with p3 as in the main text. We learn an embedding of each node using node2vec with embedding dimension of 64 and all other parameters set their default values. We then use the true community labels of 10% of these nodes to train (multinomial logistic regression classifier, and predict the class label for the remaining 90% of nodes in the network. We examine the performance of this classification tool using the node2vec embeddings in terms of classification accuracy. We show these results Figure Si for p.. = log /n/n,, with 10 simulations for each setting, with the mean across these simulations and error bars indicating one standard error. This classifier has excellent accuracy at predicting the labels of other nodes.
= 2
K =
1.00
0.75
Classification Accuracy
q/p
0.25
0.01
0.00
0.02
K K=4
K = 5
0.05
1.00
0.1
0.15
0.75
0.2
0.50
0.25
0.00
100
500
1000
100
500
1000
Nodes per Community
Figure S1: Classification accuracy using 10% the node embeddings to learn a multinomial logistic regression classifier. Mean and one standard error shown.
Additional Results, Community Detection Here we include additional simulation results which were omitted from the main text. In particular, for the simulations considered in the main manuscript we now examine the community recovery performance terms
normalized mutual information I.. We show the average NMI score across these simulations, along with error bars corresponding to one standard error. In each case, the NMI metric is similar to the proportion of nodes correctly recovered. As we increase the number of nodes this performance improves.
14

---

K =
K =
0.75
0.50
q/p
0.25
0.01
0.00
0.02
K 5
0.05
1.00
0.1
0.15
0.2
0.50
0.25
100
500
1000
100
500
1000
Nodes per Community
Figure S2: NMI for relatively sparse SBM. Mean and one standard error shown.
K =
1.00
0.75
0.50
q/p
0.25
0.02
K =
5=5
0.05
0.1
0.15
0.75
0.2
0.50
0.25
0.00
100
500
1000
100
500
1000
Nodes per Community
Figure S3: NMI for relatively sparse DC-SBM. Mean and one standard error shown.
Rates Convergence We can also investigate the empirical convergence of these methods. Here, we consider the same simulated SBM data as above, and examine the convergence in the proportion of nodes correctly recovered, as we increase the number of nodes the network, for k = 2,3, 4, We empirically investigate this convergence using log-log plot, which is shown in Figure S5 for a relatively sparse SBM. Our node2vee procedures demonstrates empirical convergence which super-linear for dense networks while being sub-linear for relatively sparse networks.
Varying the node2vec walk parameters We also wish to examine the performance of our proposed clustering procedure when the parameters of the random walk are varied. While p and q are both commonly chosen to be 1, resulting in simple random walk, other values are possible. We consider data simulated from the relatively sparse DC-SBM considered previously with consider the within between community probability ratio 3 -01 and B = 0.2, corresponding to an easier and harder setting to recover the communities respectively. We then consider p.g E (0.5, 1,2]. the common possible values and vary the number of nodes in each community before. For each
communities and
15

---

-1
0
0.25
0.75
0.50
q/p
0.25
0.01
NMI
0.02
0.5
0.75
0
0.05
0.1
0.15
0.75
0.2
0.50
100
500
1000
100
500
1000
100
500
1000
Nodes per Community
Figure S4: NMI varying for relatively sparse DC-SBM. Mean and one standard eπror shown.
0.100
q/p
0.01
Error
0000
0.02
0.010
0.05
0.1
0.15
0.2
0.001
300
1000
3000
Number of Nodes
Figure S5: Log-Log plot showing the rate of convergence as we increase the number of nodes in the network. We show a fitted regression for each of the values of B, showing better convergence when difference between the within and between community edge probabilities higher.
of these settings we perform community detection using node2vec and spectral clustering. When 0.01 weobtain excellent community recovery for all values of and as shown in Figure S6 a). When 3 = 0.2 community recovery is more challenging for small networks for all values of p and As the number of nodes increases, Figure b)(b) shows that all choices of p and q result in good performance.
A.1 Performance on Real Networks
We wish to further examine the performance this community detection procedure real networks, with known community structure. We also wish to compare this procedure to spectral clustering, which is widely used in practice for community detection. We use two publicly available networks containing known community structure. We first consider network of emails between 1005 members
16

---

n= 100
0= 100
1.00
1.00
0.50
0.50
200
Prop. Recavered
1.00
Reoovered
0.75
0.75
0.50
0.50
500
500
1.00
1.00
0.75
0.75
n= 1000
n= 1000
1.00
0.50
0.50
p-0.5.
p-d.5,
p-0.5.
p-1.
pm1.
p-1.
P-2.
P-2.
R-2
p-0.5.
p-O.5,
p-0.5, p-1.
Q-0.5
q-1
3-0.5
9-2
Q-1
9-0.5
9-2
0-0.6
0-2
G-0.5
Node2Vec Parameters
Node2Vec Parameters
(a) 3 0.01
(b) B 0.2
Figure S6: Varying the node2vec sampling parameters for DC-SBMs with 3 0.01 (left) and 3 = 0.2 (right). Community recovery is harder when 3 is larger and this is seen for all values of and for small networks. As the number of nodes increases we get good community recovery for all choices of and
of large research institution, available part of the Stanford Network Analysis Project [31] There are 25571 directed edges between the nodes in this network, with known ground truth communities consisting of 42 departments present in this institution. We also consider widely used dataset of directed edges between 1490 U.S political blogs, collected before the 2004 elections (2 Here the directed edges correspond to hyperlinks, with ground truth communities corresponding to whether the blogs has been identified as liberal or conservative.
For each of these datasets we compare the community recovery of Ved and traditional spectral clustering, using the normalized graph Laplacian. As common the literature, we remove the direction from these edges and take the largest connected component, forming symmetric adjacency matrices with 986 and 1222 nodes respectively. We then use the previously described procedure to perform community detection using Node2 Vec. We consider a range of embedding dimensions (d = 16, 32, 64, 128, 256) and unigram sampling parameter (a = -1, 0.0, 0.25, 0.5, 0.75, 1.0), while keeping all other parameters fixed at the defaults considered before. With the true number of communities known, we then compare the estimated communities from 10 simulations for each of these parameter settings, along with performing 10 simulations of spectral clustering for each of these settings.
In Figure we compare the performance of Vode2Vec and spectral clustering for the Email network and Figure S8 we use the Political Blogs network. We measure community recovery in terms of the normalized mutual information (NMI) between the estimated and true communities. Other metries such as the adjusted rand index (ARI) showing similar results. In each case the communities estimated by Vece2Vec are substantially closer to the true communities than those estimated by spectral clustering. As highlighted by Karrer and Newman (23 for the political blog data, models which do not account for degree heterogeneity can struggle to recover the underlying community structure. As shown in Figure S8 spectral clustering is unable to recover the communities due to this heterogeneity, while clustering using the Vec embedding shows strong performance at community recovery.
We also further expand on the role of the embedding parameters in the performance of Node2 Vec on these real networks. In Figure we examine community recovery for the Email data as we vary the embedding dimension d and the unigram sampling parameter a. As vary each of these parameters we see good community recovery in all settings. For this dataset all choices of embedding dimension and unigram parameter give good NMI scores.
B Additional Notation
We give brief recap of some of the notation introduced in the main paper, along with some more notation which is used purely within the Supplemntary Material. Throughout, will suppose that
17

---

1.00
0.75
NMI
0.50
0.25
0.00
Node2Vec
Spectral Clustering
Figure S7: Community recovery for the Email data, using both Nede2 and Spectral Clustering. Node2Vec can better recover true communities.
1.00
0.75
0.50
0.00
Node2Vec
Spectral Clustering
Figure S8: Community recovery for the Political Blog data, using both Nede2 and Spectral Clustering. Node2Vec can better recover the true communities.
the graph 9 (V,E) is drawn according the following generative model: each vertex E V
have latent variables A, (c(u), 0w) where c(u) E [K] is community assignment, and 0,, is hettre-thtrr correction factor. We then suppose that the edges Our E (0, 1} in the graph G, on vertices arise independently with probability
P( = 1 Aua Xw) = P...O.PPaaie (((()))))))))
(SI)
for u v, with Oue avu by symmetry for u > P The factor On. accounts for sparsity in the network. The above model corresponds to a degree corrected stochastic block model [23];
"To prevent notation overloading when is used to indicate constants, we use ane to describe the presence or absence of an edge between nodes and v in the supplement, rather than Anw which was used in the main text.
18

---

1.00
1.00
0.75
0.70
NM0
0.50
0.25
0.00
dr64
de128
dm256
-1
0.25
0.5
0.75
Node2Vec Dimension
Unirram Parameter
(a) Varying the embedding dimension used.
(b) Varying the Unigram Parameter
Figure 89: The effect of different Node2 parameters on community recovery, measure in terms of Normalized Mutual Information (NMI), for the Email Data.
highlight that the case where Ow is constant across all V corresponds the original stochastic block model [20]. For convenience, we will write
W WDu Ao) = P. c(w).c())
so P(Auu = 11 Ao) P.. W Hr,W(Aus Ao).
(S2)
We then introduce the notation
-( = (W, X²) X.). (a == (A,(, for > 0.
(S3)
Note that under the assumptions that the community assignments are drawn i.i.d from Categorical(m random variable, and the degree correction factors are drawn i.idd from a distri- bution & independently of the community assignments, we have
W(A,,) = 0, [E[ Bj~Cas(m) Pacss cc(i] = 0g E[
Ty Pet.i
(S4)
==1
(a( = R[ E(0
J P i.
(S5)
For convenience, we will write Po(e Σド= my Pc()).-
Recall that node2vec attempts to minimize the objective
VV, Σ ((i,)) e P(G.)) (..) log(a((u,, 12)))
$
- -((i))) E N(G)) (n) log(1 a(uu, v,}))}
where U,V E gaxd with E Rd denoting the i-th and j-th rows of U and V respectively, and (x) == (1+ e --)- denoting the sigmoid function. Here P and N correspond to the positive and negative sampling schemes induced by the random walk and unigram mechanisms respectively.
C Proof of Theorems 2 and 3
C.1 Proof overview
To give overview of the proof approach, work by forming successive approximations to the function C., (U, V) where we have uniform convergence of the approximation error as n - oo over either level sets of the function considered, or the overall domain of optimization of the embedding matrices and V. We break these approximations up into multiple steps:
1. Theorems SI S2
S3 and Proposition S4
We begin by working with an approximation
(U, V) of C.. (U. where the sampling weights P((i,)) P(G.) G.)) and (P(())) e N(G..) G..) are replaced by functions of the latent variables (As, Ay) of the vertices i and along with ai in the case of fo (Ai, Aÿ).
19

---

2. The resulting approximation (U, V) has a dependence on the adjacency matrix of the network. We argue that this loss function converges uniformly its average over the adjacency matrix when the vertex latent variables remain fixed; this is the contents of Theorem SS
3. So far, the loss function only looks between interactions of in and vy for i * j. For theoretical purposes, it is more convenient to work with loss function where the term with
= j is included. This is handled within Lemma S6
4. Now that we have an averaged version of the loss function to work with, we are able to examine the minima of this loss function, and find that there is unique minima (in the sense that for any pair of optima matrices U and V*, the matrix ('(V)*² is unique). Moreover, in certain circumstances we can give closed forms for these minima. This is the contents of Section C.6
5. This is then all combined together in order to give Theorems S13 and S14 which correspond to Theorems 1 and of the main text.
We recap that consider three scenarios referred to as Scenario (i), (ii) and (iii throughout when proving the following result:
(i) We use WeepWalk (p (p=9) q = 1 in node2vec), and the graph is drawn according to a SBM with Pr >> log(n)/n;
(ii) We use node2vec, and the graph is drawn according to SBM with Pr. = n n for some
a < a', where a' depends on node2vec's hyperparameters;
(iii) We use DeepWalk and a unigram parameter a = 1, and the graph is drawn according to a DCSBM with Pr > log(n)/n n where the degree heterogeneity parameters 0g, E [C--__ C] for some > oc.
Generally speaking, the approach is the exact same for all three scenarios. As we have closed formula in the case where we examine DeepWalk, we will consistently provide the details for the Deep Walk case first, and then discuss afterwards how the results and proofs change (if at all) when considering node2vec in generality. Throughout, we also contextualize the proof by examining what it says for a SBM(n, K. P. 4. Pn)) model. This corresponds to balanced network with म (K ,....,""""
C.2 Replacing the sampling weights
Before giving an approximation L., V), we need first come up with approximate forms of j(i,j) P(Gn) Gm)) and (((( E (G Gn). The next three results give examples of this. In this section we prove three main results. The first two give us guarantees for the sampling probabilities of vertex pairs (u, v) for node2vee for any choice of the hyperparameters (p, (p.g). In particular they will allow us to argue that when the underlying graph arises from a SBM, the sampling probabilities asymptotically depend only the underlying communities. The last specializes this to the case of DeepWalf (where additional information, such closed formula for these sampling probabilities, which be used in the case where the graph arises through a DCSBM.
= 1), which has enough structure to allow us to get some
Theorem S1. There exists a sufficiently small, depending on the walk length k. such that if Pm n then there exists a symmetric measurable (with respect to the sigma field generated by W) W) function fr (>, (x,) X') which is bounded below away from zero, and bounded above by Cp for some constant
C. 30, such that
na n..P((i.)) E P(9 aij X3))
max $
(z)
(S6)
Theorem S2. There exists a sufficiently small, depending on the walk length k. such that if Pn. = n then there exists a symmetric measurable (with respect to the sigma field generated by W) Wuncction (x, X') which is bounded below away from zero, and bounded above by some constant C. < 0c, such that
TT (I,s) ((()))l9n) = (1).
max x
(S7)
fr)(A11))
20

---

The proof of these two results are given in Appendix E.1.1 and E.T.2 respectively. We note that while in principle we could give closed formula for fp and fN in this scenario, they are sufficiently intractable to inspection that doing so would not provide any benefit.
In the of DeepWalk where ? 1, the calculations involved tractable enough such that we can improve the sparsity constraints, give closed forms for the measurable functions discussed above, and also provide rates of convergence.
Theorem S3. Denote
2k
(p()s,2))
= OrEw(1)
(S8)
1(k + 1)
(x))
- (W(N..)W((,,)))
(S9)
Ew (L)(Wwa
Then we have that
n²P((i,)) E P(GN))
= =Op( log 1/2
)
max
(S10)
npp
n (, E (GG))) 2g)
= Op ((
(logn) 1/2
max $
(S11)
npn
Proof. This is consequence of [1] Proposition 26]. We highlight the referenced result supposes that for the negative sampling scheme, vertices for which a, are rejected, whereas this does not happen here. Other than for the factor of (1 asy) in the quoted result, the proof is otherwise unchanged, which gives the statement above for (((t,) E (G..) 9...
With this, we then get the following result:
Proposition S4. Denote
(U, and define the
1 n
Σ{
fo Ay)ay log(a((u,,,))) (()) fxr(A,, 2y) log(1- - ((u,, ey)))} (S12)
171
U.V gnxd C.(U.V) (Onxd 0nxd) gaad Raxd
(S13)
for any constant À where Oaxd denotes the matrix in Baxd Then for any set X C Raxd x IR" xd containing the pair of zero matrices Onxd: we have under Scenario i) and iii) that
sup (U,V)EVANX
(U, ZZ =0
07
log 1/2
(S14)
nPa
P arg min (U, V) U arg min Ž., (U.V) C C Wanx) = 1-0().
(S15)
(U.V)E
(U.VEEX
Scenario (ii), the Op(.) bound replaced by an o, bound.
Proof. The proof is essentially equivalent to Lemma 32 of up to changes in notation, and so we do not repeat the details.
Note that in practice we can choose A be any constant greater than but fixed with n - e.g 10. and have the result hold. We will do so going forward.
C.3 Averaging over the adjacency matrix of the graph
Following the proof outline, the next step is to argue that L, (U, is close to its expectation when average over the adjacency matrix of the graph G,, We begin with showing what occurs in the
21

---

DeepWalk case (Scenarios (i) and (ii)), and at the end of the section we discuss how the proof changes for the more general node2vec case, Note that we have
(U,
-Sp( Az)en lo b;))) o (u;,,))))
0;)))}
(S16)
and so
(U, = (1)
- -E(
(S17)
2k
Pr
Prilass asj - W (- log o ((ui, vy))).
(S18)
n (
Note that EIE, () and so it therefore suffices to control E, () E(,, -I
uniformly over embedding matrices U, V Re This is the contents of the next theorem. Theorem S5. Begin by defining the
(A200)) = E Ruxd ||0| S A20o].
(S19)
Then we have the bound
En(U, = Op (Ab,00 d 1/2 )13)
(npt))
sup
(S20)
U.VE Bg (0)
In particular, we also have that
AB Ew (1)
d
sup
V) [EC, = Op
(S21)
U.VE D.VeRa.
Proof. Begin by noting that for any set C' C pnxd Baxd for which Onxd X Onxd C2 we have that
sup (U,V)EC
EE, (U,
sup (U,))EC
(U, En (Onxd, Oxxa) + [En Onxa)]
(S22)
sup (U.))
E. - (Ū, V) + E,, (Onxds Onxa]]-
(S23)
We therefore need to control these two terms. We begin with the second; note that as
(nnxxx Onxa) 1
Σ i41
Pn azj W()e:2))) n2
(S24)
n²
it follows by Lemma $30 that this term is (p((n²²p)) pm) ) For the first term, we make use of
a chaining bound. Note that if we write Tij = - log a ((us, v,)) and Sig = - -log o ((ūi, ū2)) for
i [ri], then we have that
E.(U, - En
n² Σ
( (Tij Std).
(S25)
Because the function I + - log (I)) is I-Lipschitz, it follows that
- < | 1
| I -1VV - tV. 11
(S26)
and consequently we have that
(U,VV (U, V) 2 u)
(S27)
$ 2exp (- min {
u²
128p
--4 UVT
16p 1 - U ÜVT 0c
(S28)
22

---

as result of Lemma S30 Now, as U. V E By(Ap) n 02 (A2, by Lemma S19 if we define the metries
dr ((U,, Vi), (U2, V2)) [U1 U2|| 11 V2lle,
(S29)
d2 (1U1, Vi), (U2, 12)) = IU1 - -U2/12,00 + ||V - V2212,007
(S30)
then we have that
(U, (U, V) 2 u)
(S31)
(-min -imin
s 2 exp
128pm -1 n - d (U, V), (U, (), 16pm nn- o2 (U, (Ü. V))
(S32)
As result of Corollary S22 it therefore follows that
sup VUE
(U V) - E, V) = 0, (A npn
(-0
(md)
1/2 )
A m
(S33)
npn
The desired conclusion follows by combining the bounds (S24) and (S33)
For the more abstract node2vec case under Scenario (ii), we highlight that we can take
En(U,V) 1 n2
Σ S
oij - (Ai;))))) (- ((u,, pnntp(in
(S34)
Now, as fp(A Ap) is a function of the community assignments only within the SBM case, we can replace this by matrix of constants fP, for c, [ks]. and therefore the error term can be decomposed into a sum
(patr.aro)))
Σ 19
(pi - W(A:, 2,)) (- lo-oo ( Uy))),
(S35)
01.02
=cc(u)=11
jic(u)=
where we recall that max,i.es (Pn (P, < oo as guaranteed by Theorem SI Each of these terms (of which there finitely many) can be controlled using the exact same argument as in Theorem [S5]
and so the conclusion the Theorem also holds with the same overall rate of convergence Scenario (ii).
C.4 Adding in diagonal term
Currently the sum in E,C,, (U, V) A] is defined only terms i, with i * j it is more convenient to work with the version where the diagonal term is added in:
R₂ (U,V)
1
Σ i.jEnn]
{
fr(M, A))pnW((...). Xo) log(o
(S36)
n
- -Nv(A, log( oluu, m3)1)
(S37)
We show that this does not significantly change the size of the loss function.
Lemma S6. With the same notation as in Theorem SS
we have that
(U, EIE,,
sup (A
= =0, (- - (Iee.fo(A +1[x((,,))1l.)))
In particular, in the case of Deep we have that
VR.(U.V) (UC Oz A
2k| Ew(1)
21(k: + 1) ))
sup
A3
+
Ew (w) (a)
C.V.BB.ocAg...
23

---

Proof. Begin by noting that
0 5 (U, V) B(
Σ Ir(2,, A5) W (Aus An) log(o v))) fAr(A,, A,) log(1 (lus, 0s}))}.
(S38)
Note that we can bound
log(o(((;; 0z)) S (u,, ea) I I1ullllleellz
(S39)
and similarly log(1 - o(u,, wx))) & Kus ui)l & ||s/||/|ee122 Moreover, we have the bounds s ( X)W (A, 2l < oc, oo, 23) s IA, 00
[r( under our assumptions. As result, because U. E 00 (A2, we end up with the final bound
(S40)
V) - (U, & A2,00 (IPmfo(A, X' X IIf (S41)
n
which gives the stated result as the RHS is free of U and
C.5 Chaining up the loss function approximations
By chaining the prior results, we end up with the following result:
Proposition S7. There exists non-empty set V, for each n. such that, for any set X C Raxd Raxd containing Onxd x Ouxd we have for Deep Walk that
(0p(( (logn)
1/2
A2,00 ) 1/2
Cn, () RU, -
sup (U,V)EV,, (12 x22 and min (A )x
+
(S42)
12p
(U.
arg min (A
V. R₂ C Vo ( nxx)
=1 =1-((1)
(S43)
For node2vec, the same result holds when we replace the (log n/ n//pp)) 1 term with an (1( term and add the constraint that d & upn. The same result also holds when we constrain U V, but otherwise keep everything else unchanged.
C.6 Minimizers of (R,
Recall that we have earlier defined
R. (U,
{ [JE
Σ
So(A,, An)n, log(o((u,
n
(S44)
- fx log(1 - o mz)1)}
We now want to reason about the minima of these functions. To do so, note that the optimization domain is non-convex firstly due to the rank constraints on the matrix UVT and secondly due to the fact that the loss function is invariant to any mapping (U,V) + (UM, VM-1) for any invertible d matrix M. To handle the second part, we consider the global minima of this function when parameterized only in term of the matrix UVT, We will then see that the minima matrix is already low rank.
We first begin by giving some basic facts about the function R,, V) when parameterized as a function of UVT.
Lemma S8.
Define the modified function
R,
Σ
fr()i, Xy) W Aa) (M,()(M)))) - far(As, log(1 - (M,))).
n
L.jE[n]
(845)
over all matrices M BaxR, Then we have the following:
24

---

a) The function (M) is strictly convex in M.
b) The global minimizer of Rn (M) is given by
f W far(As,)s)
Mij = log
(S46)
and satisfies V (M) 0.
When restricted cone of semi-positive definite matrices M E MM there exists a unique minimizer to Re, (M) over this set, which call M Moreover, M has the property that (V Rn, (MR (M**), M, M) < 0 for all M M
Proof. For part a), this follows by the fact that the functions - (x)) and log(1 - (x)) are positive and strictly convex functions of E. the fact that (A, X An (Ag, Aÿ) and fx( Xj) are positive quantities which are bounded above (see e.g Lemma S6), and the fact that the sum of strictly convex functions strictly convex. For part b), this follows by noting that each of the M are pointwise minima of the functions
Tij (z) fP, Ag) W (Au An) log(o(z))) (y
(S47)
defined over x E R. Indeed, note that
drij dr
(S48)
so setting this equal to zero, rearranging and making use of the equality (a + b)) (og((/b) gives the stated result. Part c) a consequence strong convexity, the optimization domain being convex and self dual, and the KKT conditions.
To understand the form of the the global minimizer of R., (M) in the DeepWalk case, by substituting in the values for fr(2, (As; Xj) and (Ai, >ラ) we end up with
2P 2
Mi log
(S49)
(1+
E 1000000000 1
Pa(t) aU) + 1
ali) (
Patt))
(a)(a)
Pa(i),e()
=log
(S50)
(1+
Pat) (0 pa-11
+ -0
10-1pa-1 pa-1)
d(i)
c(i)
In particular, from the above formula we the following lemma as a consequence:
Lemma 89. Suppose that Scenarios (i) or (iii holds, so that either a) 0 is constant for all i, or b) a 1. Then we write IIc E R for the matrix where (Icc) =[((()) II, and define the matrix
2 (a)
Phm PmP
(Ma) = log (1 + k K-+ E0
for m E [rc],
(S51)
P
then we have that M = 1.1 In particular, as soon as the matrix Hl is of rank (which occurs with asymptotic probability 1), then the rank M equals the rank of M Moreover, as soon as d greater than or equal to the rank of M (U.V) V) a minimizer of (U, V) if and only UV M*
Under Scenario (ii), the same result applies noting that fo and fNr are functions only of the underling communities, and if we abuse notation and write J (1, m) to indicate the value of JT (Ni, Xj) when c(i) and c(j) = m, one can take
fp(l, m))mPPm
)m log
(S52)
fl)
and have the above result hold.
25

---

We discuss in Appendix Fhhtt happens when we apply DeepWalk in the DCSBM regime when a * 1. To give an example of what M looks like. we write it down in the case of (B, K, p. 9. Pn. model, which is frequently used to illustrate the behavior of various community detection algorithms. Such model assumes that the community assignments лт 1/M for all I E [x:] and that
k
PRI =
(S53)
In this case, we have that
p= P + k(q 1) 1)
(i+ (N (K=1)ā
1)
for 1 E [n]]
Ew(a) E
(S54)
Substituting these values into the matrix Ma gives
B[00]
kp
B
Kq
(Ma)m log
dpm +oo
8tm
+1001++-1)
p+ 1)7
[1 + (00(1++-2)000 ア+
1)
(S55)
We highlight this is a matrix of the form adim + 3(1 dtm). and so is straightforward to describe the spectral behavior of the matrix (see Lemma S31).
C.6.1 Minimizers in the constrained regime U V
In the case where have constrained U , it is not possible in general to write down the closed form of the minimizer of (M) over M $ However, it is still possible to draw enough conclusions about the form of the minimizer in order to give guarantees for community detection. We begin with the proposition below. We state the next two results for DeepWalk only, but note that the first generalizes to the node2vec case immediately.
Proposition S10. Suppose that 0g is constant across all i. Supposing that M E RRNN is of the form M -UUT for matrices Ü E IRxdd, define the function
R,,(M) Σ (m))) ( 22 log o ((u,, um)) (PiPm + + P log(1 -1 - (lu,, Um))))
1.mE(r]]
(S56)
where we define (n) := =n Ki c(i) = for E [k]. Then Rr is strongly convex, and moreover has unique minimizer as soon as 2 K.
Moreover, any minimizer of (M) over matrices M of the form M UUT where U E R must take the form M = -IcMMII where (IIc)a 1[c(i) = 0 where M is a minimizer of Rr(M) In particular, once K, there a unique minimizer to R., (M).
Proof. The properties of (M) are immediate by similar arguments to Lemma S8 and standard facts in convex analysis. We begin by noting that if we substitute in the values
2h (()..c)))
Pn M.W(A,,A))PMM.
(S57)
(1)
1(k: + 1)
(x));, Ew (1)Ew
(Poo) + PoLT) Pog))
(S58)
for fr(As, 2ÿ) and fN(Ai, X1), then we can write that (recalling that Mij = {ui u₁})
R. RM == 77 1.jE|m]
Σ
2kP 2kPa(0. (oga((u,,))
(S59)
1(k 1(k+1)
(Pet)) Paj) + Payy Pat)) log(1 - o((u,, xy)))
(S60)
(1(E))
Σ (m)
{ 2kPPm Cil
Σ
log a ((s,,
(S61)
SECIJEC..
- -(Pa + Pocy CillCml sECrJEE...
Σ
log(1 - (lu,, ((u,,,))))
(S62)
26

---

where for E [R] we define (.(()) := n 1 e(t) 171, along with the sets C₁ = fi : c(i) = 1). Now, note that as the functions - log(((())) and log o (z)) are strictly convex, by Jensen's inequality we have that e.g
Cml
E
-log -logo((uu uy)) - -log ( (1c)
|cl
Uii
C.
Σ jECm
43)
(S63)
VECI.JEC..
EEC
(where also used bilinearity of the inner product) where equality holds above if and only if the U4 are constant are across all indices i. In particular, any minimizer R, must have the uy
constant across i E C2 for each E [k], which defines the function (M). This gives the claimed statement.
In certain cases, we are able to give closed form to the minimizer. We illustrate this for the case of the SBM(n, K. Q Pn) model.
Proposition S11. Let M be the unique minimizer of RR (M) as introduced in Proposition S10 In the case of a SBM(n, k, P. q, Pn)) model, we have that M -M Ox((x k/ 1/4). where M is of the form
(M");; = a 8ij
0ig)
(S64)
for some a* a (p. ②) 2 O. Moreover, a > 0 iff q.
Proof. We begin by arguing that the objective function R.(( converges uniformly to the objective
(M 1
Σ
2k log a(uu, wm))- Pf + PPPP.. log(1-a(((e)) um))) (S65)
[mE(x]
over set containing the minimizers of both functions. Note that this function is also strictly convex, and has unique minimizer as soon K.. To do so, we highlight that as we have that
pn (1) (k)
x= Op ((< log 1/2
max
(S66)
Aigel
K
Y2
by standard concentration results for Binomial random variables (e.g Proposition 47 of [ follows that
Ru (M) RR (M)) S R. (M) O, log N 1/2 (.)).
(("llgg
(S67)
Consequently, (M) converges to R2
RM, (M) uniformly over any level set of R2 (M), which neces-
sarily contains the minima of R., (M). If one does so over the set (for example)
A = (M R. (M) S (0)
(S68)
(for example), then as R., (0) is constant across n, we have uniform convergence of SS67 over the set at rate of Op (logx/ng) x/ /np) 12).. This argument can reversed, which therefore ensures uniform convergence (over the same set) which contains the minimizers (with the minimizer of R., (M) being contained within this set with asymptotic probability 1) at a rate of Op ((x log 2/2)
With this, we note that an application of Lemma $33 gives that for any matrices M1 and Ma we have that
(M,) 2 (M,) + (AR,, (M2), Mr -M2
(S69)
Σ
min min(((M2) (M.),) (Mo)
(S70)
KJE(M)
where save on notation, we define
C :
- | oc
min(2kP , Pm P. I.m
(S71)
27

---

In particular, if M2 = MM* is an optimum of (M), then by the KKT conditions (similarly as in Lemma S8) we have that
C R2
Σ
min(((M"); (Mi)iy P.2((M (M (M)
(S72)
In particular, if then let M be any minimizer of (M)), then we have that
C
Σ
min (I(M)),, 2((7))) - (M))
(S73)
R
(
S R..Ms (M1) - (M S (M,) - RM( + (M - (M
(S74)
sup (M) R,,
(S75)
MEA
on an event of asymptotic probability Consequently, it follows by Lemma S34 that
M M ((
(S76)
We now need to find the minimizing positive semi-definite matrix which optimizes R, (M). To do so, we will argue that one can find for which
My adis 11
(1- dey), VR, C1 = (1,.... 11)
for some positive constant C, as then the KKT conditions for the constrained optimization prob- lem will hold. Indeed, for any positive definite matrix M, as by definition of M we have that (VR, (M), .M) 0 as all of the eigenvectors of M are orthogonal to the unit vector 1x (Lemma S31 It consequently follows that as VR, (M) is itself positive definite, we get that { RR, (M) M M) = (VR,(M) M) 2 O. We now need to verify the existence of constant for which this condition holds. We note that as Mij constant across i j. and also constant across (M) ) is proportional to 1 1 it suffices to check whether the i * j. to verify the condition that V.R,,,
on and off diagonal terms of RR,,, (M) are equal to each other. This gives the equation
a(a): (kp 1(k 1) (Is 1)q -1)1
K
k(p q) + aa(aa((K- 1)) kq + 1(k: + 1) x+ (n 1)õ
By applying Lemma $32 this has a singular positive solution in if and only if A: 7) 2 k(p ((5-()1 12/
which holds iff p 2 4-
In the case where p < q. it follows that the solution has a 0.
C.7 Strong convexity properties of the minima matrix
Proposition S12. Define the modified fanction
(M) n
Σ
(x(,,, (e)Ai,A))pMM (Aus Av) log()(M;))) (x((i,)g)) - (M
LJE(M]
(S77)
all matrices M Ruxn
Then we have for any matrices M2 R with
|| M|2lloc I Aoo that
Če-dx 1
(M)) (M2) + (M2), Mi M2)
2 n² | M2 (S78)
prar P m) for Scenarios (i) and (iii), and Č where δ min [2k
> 0 for Scenario (ii), Moreover,
28

---

i) If RM,(M is constrained over set X' {M UV U. E Ra || S Aooh. and there exists M in X such that VR, 0, then we have that
1 1 IIM - - & 2 (Ra(M) - (R((M)) for all MEX. n2
(S79)
ii R, (M) is constrained over a set X = {M = UU U Ruxd ||M 1 < Axx I. and there exists M in X22 such that (VR((M") we get the same inequality in part i) above.
M*) 2 for all E X22 then
Proof. The first inequality follows by an application of Lemma following by applying the conditions stated and rearranging.
S33 with the second and third parts
C.8 Convergence of the gram matrices of the embeddings
By combining together Proposition S12 and Proposition S7
we end up with the following result:
Theorem S13. Suppose that the conditions of Lemma S9 hold. (In particular, recall that d 2 k.) Then there exist constants Ax and 22 (depending on the parameters of the model and sampling scheme) and a matrix M TR (also depending on the parameters of the model and the sampling scheme) such that for any minimizer (U*, V*) of CUU V) over the set
X = ((UV)) |00| [V S Azo, 1|V S A2,00):
(S80)
we have that
M Mo =c C. Sop( (1((1)
max(logn.d) 112) 7pn
under Scenarios (i) and (iii);
Σ (J((m]
((u)
under Scenario (ii);
(S81)
for some constant C depending on the model, the node2vec hyperparameters, Ass and A2. In the case where constrain U = V. the same result holds provided the conditions Proposition SIO hold.
Proof. We note that by Lemma S9 there exists minimizer M for (M) of the form M IM**ITT for matrix M R We then take Ago and Âz 2 M* Iloe and 2 2|| 11. We highlight that we can do this even when d >> as we can embed M into the block diagonal matrix diag(M", Od-,,dxx), which preserves both the norms above. Lemma and Proposition S12 then guarantee that
1 -U'(V')'-M'' - C (R..(UVVT)) R. (M)))
(S82)
for some constant Ò depending only on the quantities mentioned the theorem statement. As X' is subset of B2 (, and (U*, V*) is a minimizer of L(U, V), we end up getting that
(UV( Rr (M)))
(S83)
R. (UV2) - (..UU*V)+++ +7)+C((M') - R. (M*)
(S84)
< 2 sup (U. - (U,V)
(S85)
(U.V)EX
from which we can apply Proposition
t7 then give the claimed result.
We give some brief intuition to the size of the constants involved here, understand any potential hidden dependencies involved in them. Of greatest concern are the constants Aoo and A2. (as the remaining constants are explicit throughout the proof, and depend only on the hyperparameters of the sampling schema and the model
polynomial fashion). Note that in the case where k is large and we have SBM(n, P, q, Pw)) model and we apply the DeepWalk scheme, from the discussion after Lemma S9 the minimizing matrix M takes the form
KIJ
(M*)) s log
8m + log
(1 6pm)
(S86)
5 (k 1)
5 (K 1)
29

---

Supposing for simplicity that P q. it follows that we can take can take Aso to be of the order ((log(p/)) when is large. In the rate from Proposition S12 this gives a rate of O(p/q) from the emw factor, note that the dependence on the parameters of the models here are not unreasonable. As for 22, we first highlight the fact that
KQ
p-9 as 0G.
(x log
(S87)
p
By Lemma S31 we can therefore take 2g, to be scalar multiple of log(5/7)) avoiding any implicit dependence on k or the embedding dimension d.
C.9 Convergence of the embedding vectors
We can then get results guaranteeing the convergence of the individual embedding vectors (rather than their gram matrix) up rotations, stated by the following theorem.
Theorem S14. Suppose that the conclusion of Theorem S73 holds, and further suppose that equals the rank of the matrix M Then there exists matrix U E Rxxd such that
Sopp maxx(lg (log(l n.d) 12/2)
min QEO(d) n Iug ( Q11 = - = (000))
under Scenarios (i) and (iii); (S88)
ape
(z)(1)
under Scenario (ii);
Proof. We handle the cases where + and = separately. For the case where * V. we note that without loss of generality we can suppose that UU VVT" in which case we can apply Lemma S23 and TS133o give the stated result. To so, we note that by Lemma S23 we have that ddl IIM" 2 (AM) for some constant with asymptotic probability I, result of the fact that (II) 2 1//2nTT with asymptotic probability uniformly across all communities A E [x]. As moreover have that n n-1n--- "[V'V IIM"II' llop I -'''VV" -IIM-II''| op(1), the condition that |/VV II ol (/Loa(IIMM'M
holds with asymptotic probability 1, we have verified the conditions Lemma S23 giving the desired result. In the case where we longer need verify the condition that is sufficiently small, and so we have concluded in this case also.
constrain U = V, the same argument holds, except
||U -
In the case a SBM(n, K, p, q, P..) model it is actually able to give closed form expressions for the embedding vectors which converged to by factorizing the minima matrix M in the way described by the above proof. These details are given in Lemma S31
D Proof of Theorem 4 and Corollary 5
D.1 Guarantees for community detection
We begin with discussion of how we can get guarantees for community detection via approximate k-means clustering method, using the convergence criteria for embeddings have derived already. To do so, suppose we have matrix U e pn corresponding of columns of d-dimensional vectors. Defining the set
Mr.K == [II E {0, 10,n, each row of Il has exactly K 1 zero entries].
(S89)
we seek to find a factorization ze ILX for matrices II E Mn.K and X e R K xd To do so, we minimize the objective
L. (II, X) = -IX-I
(S90)
In practice this minimization problem is NP-hard (5). but we can find (1 + apprroixiaa solutions in polynomial time (25). As a result, we consider any minimizers 1l and X such that
La (1i, < (1 + e) min Ca X11,
(S91)
11.
30

---

We want to examine the behavior of k-means clustering on the matrix U. when it is close to matrix
U which has an exact factorization U* II* Xx" for some matrices II* Ma, and X E R Rxd
We introduce the notation
GR(MT)= (i [n] 1 = 1),
nh (TT) |G (z))
(S92)
for the columns of which are assigned closest to the k-th column of X as according to the matrix II.
We make use of the following theorem from Lei and Rinaldo 30 which we restate for ease of use.
Proposition S15 (Lemma 5.3 of Lei and Rinaldo [0). Let (II, X) be any (1 + c) ap-roxximaaee minimizer to the k-means problem given a matrix U Raxd, Suppose that U IT2 X* for some
matrices II E Mn,x. and X E Rexd. Fix any óy I ming4 ||X -X ll, and suppose that the condition
+ 166+8e)lle - 112./8/ < nx(I)) all k E [m]
(S93)
holds. Then there exist subsets Sy C Gx((I) and permutation matrix E -Rax such that the following holds:
For G = Ux (G&((T))) \ Ss), we have that (II*) oll.. In words, outside of the sets Sa we recover the assignments given by II up to re-labelling of the clusters.
ii The inequality Ek=1 15. S (16 + Sc)l - U² holds.
In particular, can then apply this our consistency results with the embeddings learned by node2vec. Recall that we are interested the following metrics measuring recovery of communities by any given procedure:
[(c,O) := min ()
((((1) + a(((1)).
(S94)
[(c, G) == max
min
[[((i) + [kk)
(S95)
kE(N] @ESym(K)
|C
iEC.
These measure the overall misclassification rate and worst-case class misclassification rate respec- tively. Corollary S16. Suppose that we have embedding vectors wi E Rd for i E [n]] such that
1 Σ | Q13 1 Op(rn)
min QEO(d)
(S96)
for some rate function Fa + 0 as + 0c and vectors mn E Rd for E [x]. Moreover suppose that δ- : minzya ||m 12ll22 O. Then é(i) are the community assignments produced by applying a (1 + a)apprexxmmaee k-means clustering to the matrix whose columns are the Wa we have that L(c,e) = Op(6-2rn) and L(c,e) (8-22. If the RHS of (S96) is instead o,(1), then replace Op(ra) by (1) in the stalements for L(e, i) and I.c,
Proof. We apply Proposition S15 with II" corresponding to the matrix of community assignments according to c(-), ), and X* the matrix whose columns are the Qn for e [k]] where Q E (d) attains the minimizer in (S96). Letting U be the matrix whose columns are the w; and taking òn 8, the condition (S93) to verify becomes
16 8
IW - Qua < CCkl for all [s]].
(S97)
82
T1
As + and Giln c > 0 for some constant uniformly across vertices [*] with asymptotic probability (as a result of the community generation mechanism, the communities are balanced),
the above event will be satisfied with asymptotic probability 1. The desired conclusion follows by making use of the inequalities
L(c, 2) < n
Σ 14kh
E(c, < max
Syl S
max kE[m]
n C
S
(S98)
KE[M] C2
NEI
[EIN)
31

---

which hold by the first consequence in Proposition ST5
and then applying the bound
16 + 8c
S
|
Qee
(S99)
82
kE[N]
==1
We note that in order to apply this theorem, we require the further separation criterion of ő >> 0. As result of Lemma S31 we can guarantee this for the SBM(n, K; 4 (n.) model when either a) DeepWalk& is trained in the unconstrained setting, or b) we are in the constrained setting with ğ > q. As we know that the embedding vectors converge to the zero vector on average when are in the constrained setting with p S q. as a result we know that community detection is possible in the constrained setting iff p > q. which gives Corollary of the main paper.
D.2 Guarantees for node classification and link prediction
We now discuss what guarantees we can make when using the embedding vectors for classification. In this section, we suppose that we have guarantee
1 min n QEO(d)
Σ llu, TC Q13 < C(T)r. holds with probability 2 1
(S100)
for some constant C(T) and rate function rn + 0 as n - oc. This is the same as saying that the LHS is Op(rn) it will happen to be more convenient to use this formulation. We also suppose that there exists positive constant > 0 for which
8 < min I mill2-
(S101)
We begin with a lemma which discusses the underlying geometry when we take a small sample of the embedding vectors.
Lemma S17. Suppose we sample K embeddings from the set (un)iejn) which we denote as ........ Us Define the sets
S = (i C₁ : [|u, - now l12 < 8/4).
(S102)
Then there exists no(K, 8,)) such that if na. with probability 1 - T' we have that ui, Se(tg) for all j E [K].
Proof. Without loss of generality, we will suppose that Q I. For each I E [xi], define the sets S = (i C. : l|u, mll2 < 5/4). Then by the condition (S100). by Markov's inequality we know that with probability 1- - T we have that
Σ CIASSS 48 (C(T/2)r.
(S103)
TI
LE(A)
We now suppose that we sample K embeddings uniformly at random; for convenience, we suppose that they are done so with replacement. Then the probability that all of the embeddings are outside the set UC, St) is given by (1 - n Σ, Si) 2 1 K Σ, [C, \ S)). In particular, this means with probability no less than - T 4K8 C(T) if we sample K embeddings with indices i1, -.,-.-; at random from the set of n embeddings, they lie within the sets Sc(i):-..- Sc(x)) respectively. The desired result then follows by noting that we take = r1/2, and choose such that 48 48-2C(T (0((((())),,, <22
To understand how this lemma can give insights into the downstream use of embeddings, suppose that we have access to an oracle which provides the community assignments of a vertex when requested, but otherwise the community assignments are unseen.
We note that in practice, only small number of labels are needed to be provided embedding vectors in order to achieve good classification results (see e.g the experiments in Hamilton et al. 17], Veličković al. 47 As a result, we can imagine keeping K fixed in the regime where n large. Moreover, the constant 8 simply reflects the underlying geometry of the learned embeddings. and r' a tolerance we can choose such that the stated result is very likely hold (by e-g choosing T' 10-2 or 10 10-3). As consequence, the above lemma tells us with high probability,
32

---

i) learn a classifier which is able to distinguish between the sets Si given use of the sampled embeddings u......, Vi and the labels c(i1): ((fi)....,,(() c(ix), provided the classifier is flexible enough to separate x disjoint convex sets; and
ii) as a consequence of (S103). this classifier will correctly classify a large proportion of vertices within the correct sets St-
The same argument applies if instead we have classes assigned to embedding vectors which form coarser partitioning of the underlying community assignments. The importance of the above result is that in order to understand the behavior of embedding methods for classification, it suffices to understand which geometries particular classifiers are able to separate - for example, when the numher of classes equals 2, this reduces down to the classic concept of linear separability, in which case logistic classifier would suffice.
We end with discussion to the task of link prediction, which asks to predict whether two vertices are connected or not given a partial observation of the network. To do so, we suppose that from the observed network, we delete half of the edges in the network, and then train node2vec resulting network. Note that the node2vec mechanism only makes explicit use of known edges within the network. This corresponds to training the node2vec model on the data with sparsity factor Pn + Pa/2: in particular, this leaves the underlying asymptotic representations unchanged and slows the rate of convergence by factor of 2. With this, link prediction classifier is formed by the following process:
the
1. Take a set of edges J S. {(i.j) a. = 1} for which the node2vec algorithm was not trained on, and set of non-edges J C {(i,j) aaj = 0). As in practice networks are sparse, these sets are not sampled randomly from the network, but are assumed to be sampled in a balanced fashion so that the sets J and J are roughly balanced in size. One way of doing so is to pick a number of edges in advance, say E, and then sample E elements from the set of edges and non-edges in order to form J and J respectively.
2. Form edge embeddings Gij- = [us, Uz) given some symmetric function f(x, y) and node embeddings ug. Two popular choices of functions are the average function f(z y) (xr + /2 and the Hadamard product f(r,y) y) = (2..)))<((;
3. Using the features eij and the labels provided by the sets J and J. build classifier using your favorite ML algorithm.
By our convergence guarantees, we know that the asymptotic distribution of the edge embeddings eij will approach some vectors Me(x).c()) E Rdd, giving at most x² distinct vectors overall. Note that these embedding vectors in of themselves contain little information about whether the edges are connected; that said, even given perfect information of the communities and the connectivity matrix P. one can only form probabilistic guesses as to whether two vertices are connected. That said, by clustering together the link embeddings we can identify together edges as having vertices belonging to particular pair of communities. With knowledge of the sampling mechanism, it is then possible to backout estimates for y and y by counting the overlap of the sets J and J in the neighbourhoods of the clustered node embeddings.
We note that in practice, MI. classification algorithms such as logistic regression are used instead. This instead depends on the typical geometry of the sets J and J. Suppose we have a SBM(n, 2, p. q. Pn) model. In this case, the set J will approximately consist of p/2( + 9) x E vectors from 711- p/2(ō + x E vectors from 7/22, q/2(ğ + @) x E vectors from 1/12 and q/ 2/2(ā + 7) x E vectors from 7/1- In contrast, the set J will approximately have E/4 of each of 7/11 7/2. 721 and 7/22. As result, in the case where p >> g. a linear classifier (for example) will be biased towards classifying more frequently vectors with c(i) c(j), which is at least directionally correct.
So far, we have not talked about the particular mechanism used to form link embeddings from the node embeddings. The Hadamard product is popular, but particularly difficult to analyze given our results, as does not remain invariant to an orthogonal rotation of the embedding vectors. In contrast, the average link function retains this information. In the SBM(n, 2. T, Pn), it ends up giving embeddings which will asymptotically depend on only whether e(i) = <(j) or not (i.e, whether the vertices belong to the same community or not).
33

---

E Intermediate results
E.1 Sampling probabilities for node2vec
In this section, we derive asymptotic results for the sampling probabilities of edges within node2vec. We begin by recapping the second-order random walk defined for node2vec. To do so, define random process (Xn)n21 via the second-ordes Markov property
0
if (u, 8) E
1/p
if du,e = 0 and (u, s) E,
P(X, = = Xn 8, xn- t) &
(S104)
if du 1 and (u, 8) E, 1/q if da 2 and (u, E E.
where du,s denotes the length of the shortest path between w. and 8. Given the extra information that (u, s) is an edge, du = 0 occurs iff u = v, du.v = 1 occurs iff (u, v) is an edge, and du, = occurs iff (u,)) v) is not edge (as given that (u.s) is an edge, the shortest path must be v With this, we select positive samples by selecting concurrent edges within the walk (via taking a walk of length k 1).
u).
To initialize the random walk, we note that for the second order walk we need to specify distribution on the first two vertices; for DeepWalk where this collapses down to a first order walk, we only need to specify a distribution on ther first vertex. To do so generally, we consider an initial distribution of
selecting the first vertex via (u)) = deg(u)) >,. deg(u) = deg(u)/2E, with En being the number of edges in the graph (single counting (u, v) E & and (v, u) E), and select the second vertex uniformly random from those connected to the first. (Note that this is the transition kernel used for Deep Walk, and so we handle both cases via this argument.) One can show this is equivalent to selecting edge uniformly at random.
For the negative sampling mechanism, we consider the vertices which arose as part of the positive sampling process which we denote V(P) and then sample 1 vertices independently according to the unigram distribution
deg(u)
Uga (v u, Gn)
(S (S105)
Ev f/u deg(v)a
where u E (P).. We note that the case where a + 0 corresponds to the uniform distribution on vertices not equal to
E.1.1 Proof of Theorem
In this section and the next, it will be convenient to use the notation ~o to indicate that two positive random variables X,, and Y, are asymptotic in the sense that |X,/Y, 1| = (1))) when n -> co. If we say such a bound happens uniformly over some free variables say X ~'p Y,, uniformly over k - then this means max; |x,,k/ Ya,k 1| (p). We also make extensive
use of the result that if (() ~p r. for 1) and y-(0) [C-1_ C] for C > 1, then xx")) +x(") ~p Fn (Y:10) y Indeed, if we write x,(0) y, Tn (1 + where d (1), then
Y(())
n + (()) = (Y + Y.O) (1+
(0)
(1) Y + (I) 7
(S106)
from which the claimed result follows as the terms weighting the (1) can be bounded below away from zero, and are bounded above by 1. We also note that x x (r,)), meaning that the order of magnitude of terms cannot increase (only decrease) by subtracting them.
As we are interested in the sampling probability of edges within node2vec, it will be convenient to instead study the first order Markov process Y, = XXn,X,,1) as then we instead study the sampling probability of individual states in a regular Markov chain. We note that normally we use the notation (u, u) refer an unordered pair belonging to an edge in graph, but for the Markov process (Yx)211 the order matters, we will write Y,, = cv-ou whenever X,, u and X = In such a scenario, the random walk is therefore defined on the state space
S = U
{eu-ve
(W,
34

---

with the law of Y given by
P(Yn = et-tu - (x-ts) 1f
(S107)
if (s. u) E otherwise.
P(Y, Ce-tu Yn-1 Qv-t)) a I/u= + 1(u o ()(r + 1-aue
(S108)
One can calculate the normalizing factor for the probability distribution being
6 q )) - deg(s) + (1-1
Σ
asuauv:
(S109)
q
"EV((t)
from which we observe that when = = 1 we recover the simple random walk defined by DeepWalk, as then the probability an edge selected with source node uniform over edges (u, v) where v is a neighbour of u.
With this in mind, define the transition matrix
P Po- Usu {1[u v] 1/p + 1fu + v + 1/q. (1 ann))
(S110)
deg(s) + Enevr(v) Oxulur
governing the transition probabilities on the above chain. We note that by [ Proposition 72] and Theorem $26 respectively that
deg(s) ~y Topr, W (Xs,-);
(S111)
asuQuu up ni T T()TT(>ss An) where T(ss; Ap) = B Ux- (A, Av) Aus Av]
(EV
(S112)
uniformly over all 8, U, U. As result, we define
P Po---s-a = Osu {q-1 (1 (-1))amm )mm + Suv 1-
(S113)
( ( tmp, W (A...)) (1- npp
) (hon Xu)
where duv == 1/v 2| and the numerator is the same as in Po-te,a-u (only written in a more convenient use fashion), and the denominator makes use of the asymptotic statements (SIII) and (1122). As a result, we have that Po-te.e+u ~p Po-tea--u uniformly over v, 8, u. particular, we have that Po-ts.s-u (a (nmm((pp))) (mpm)=1) uniformly over all triples of indices 8,)..
}. We then note that the sampling probability of (u, r) being sampled within the first l: + steps of the second order random walk is given by
Let Ay(u v) {Y; eu-
IP U u( - u) u))..) jSk
(S114)
To ease on the notation going forward, we write P-(()) = PP( By the inclusion-exclusion principle, we can write this probability as equalling
Σ (-1)ktm+1
Σ K
P. (n (u v) n Asa + - 1mmm
(S115)
Lm21 L+m
ASI
We note that the number of terms in this sum is bounded above by (2k)! (some terms will be zero, as we cannot select Eu-vv two times in a row), and so for asymptotic purposes we can focus on the individual terms.
We now address the individual probabilities making up this sum. Intuitively, want show the following: that the terms for which (1, m) o (1,0) or (0, 1) are asymptotically negligible, and that asymptotically these terms are functions only of Ap). We fix particular instance of the i it
and Ji...., Jm. and denote 31 < 32 < ... < 3ttm for the ordering of these indices. As we use indices is to denote the direction - v and ja for the direction > u, we write
A, + v) Ap(u,
Aş(u u) Ag(u, v, 1)
(S116)
35

---

where the third argument (which we refer to as the orientation herein) indicates which of the first two arguments are used as the source node for the edge. For each B5 for & I m, we write og to denote this orientation. As a result, it suffices for us to analyze
Pr
in K51+m
Aga (u, U, 0k))
(S117)
over all sequences 1 S 31 < B2 <.... < 3m and orientations (ox) For this, we then note that by the Markov property of the random walk, we able to write this probability as
II 1el4m-11
Pn Sn (u, v, 04.1) As, (u, (u, Pn (A8, (u, v,,)
(S118)
Pn (A0 2,0001 A A1 (u, o.))) Pn (u,
II keltm-1
(S119)
Focusing now the terms the product, if 3k-1 3x then this term equals zero og 0k=1. or otherwise equals c.g Pu tu which is (p((pp.))) as discussed above. If the walk is longer, then by the same argument as in [I] Proposition 73], by conditioning on the second step the walk one can show this probability is asymptotically of the same order of walk of length 8k+1 3g 1 initialized from the uniform distribution on the edges of Gn. As result, we therefore only need to analyze events of the form
P. (As(u, v, 0,)))
(S120)
which will allow us then show that the events of the form m) = (1, or (0, 1) are the only ones we need to consider in the asymptotic expansion. Going forward, we assume that o = 0, as the sum (S115) is symmetric in the orientation o and the arguments are unchanged.
To do so, we begin by writing writing n' = (amv// ( for the initial distribution provided to Y,. To P (Ag(u, u, 0)). note that when B = we trivially have that this probability equals awe//e /|]| and we know that [8] ~p n²² En (1). In the case where 3 2 2, we consider the set of sequences a = (ao...,, E 2 where we then have that
analyze Ps (u, v. (3) == P,
1
(n,u, 2.2)
aco.u Pao vuuu+
(S121)
E
ag
B II
1
Pn(u, 1,
amo.0
Paş 1 -00 1 Pag 20 1.08 1 1-0,0--
3
j=l
(S122)
for 3 2 3.
To study these sums, we begin by noting that they are asymptotic to their versions where we replace P P. Indeed, we note that if we have positive sequences (a;) and (b,). then
1 bE 1)] Σ, aj Σ,b,
max 1/-
aj 3 by
(S123)
Σ,b,
and so the fact that we know Prp P uniformly, means that we can apply this to obtain asymptotic formulae for their sums also. With this. if we write (A),,A)) for the denominator of Pr- Pa Pa(u, v, (8) can be asymptotically be decomposed into a linear combination of terms (bounded in number by function of i independent of of the form
c(p, g)u
Σ
(II
[II
N(AaL.)dad)) 25i58
II i58-1
aá a., II
aa as+1
II kEK
d 881-1,
[3]
-
jEJ
(S124)
where:
36

---

we write ā for the concatenation (a, v), meaning á is of length 8 + 1, with dj = ag for k S B 1, 0, = and 3 u;
c(p, q) = (a-1)s- - a
is polynomial in inp" p- and q q=
J and K are possibly empty subsets of (1, which are disjoint.
The more tedious part to handle is when the set K is non-empty; each delta function acts to contract the sum along one variable, doing so allows us to rewrite (S124) as
auv [8]
(p, 9)
Σ
II 25153-1K]
)att))
II KS8-1-JK
II jEJ
&j+1
OEVS 1 |K|
(S125)
after performing some relabeling of the indices and modification to the set J, give a new J which is subset of . ,
[K]] and b) introducing some multiplicities n, which sum to
3 - 1. By Theorem S26 we uniformly have that this quantity is asymptotic, uniformly over all the
free variables in the expression,
Pn
JI
(pp E E1)
Hiss 1- 1( X 1G
N/+1) | Av (S126)
(npn) )
I2SiSR-IKI 1.)
where we write X' = (Ao...., - Au, Aa) and Ā is an independent copy of X, and N'(A,, Ap) = (mpm)-1N(Au. Ao) As npfa - oo under the prescribed conditions, we only need to consider leading terms of the order Pr, n² which shows that the sampling probability asymptotic (uniformly over all vertices) to Pr n² for some function gr Aę). To argue that this function is bounded above away from zero, note that the terms where |J + |K] > will be asymptotically negligible, and the remainder of the terms give a positive weighted sum.
E.1.2 Proof of Theorem S2
To understand the selection probability for the vertex pair (u, v) be selected via negative sampling, define the events
At(u) (X:= Bi(olu)- selected via negative sampling from u}
(S127)
so then
k (P())P(((A(()) (olu)) B((ll)) (Ai(v)) ((4l))))))))))) 1=0
(((u,v) E EV(GG))
(S128)
We note that
((A(()) n (e(u)) ((A G.) (.t.)..PPPPBBannn [(,iiomial((, (vlu) 1l))).
(S129)
As result, we need to begin by understanding the asymptotic probabilities (PA,(v)) (.) and
unigram sampling probability. We begin with understanding the first probability. If E {0, 1), then we have that (P) 9.)) = deg(u)/2E: ~p W(Av: :): /) (1) uniformly in v Proposition 72]. For i > 2, we have that
P P(A(t))
Σ (A (n)
(S130)
using the same notation in Appendix E.I.I
Consequently, via the same arguments as in Ap- pendix E.I.I will be asymptotic to positive linear combination statistics of the form
c(p,q) q) [3
Σ
II
II {5B-|K]
aa- &es
aay daaz- jEJ
II
(S131)
25150-IK]
where write à (a, v) for E ya. Using the same relabeling and arguments as given in Appendix I.
will be asymptotic to
Pn
c(p.9) 9) n1w(1)
I |R| W(X X)) II W W(N-11
E
Av
(S132)
1233s3- ,
37

---

uniformly in all the free variables involved, where X' = dent copy of X. (We note that while AheoremmS266jp expressed terms of concentration of quantities around functions which depend on both X, and Au. the exact same reasoning will apply for statistics which only end up depending on A..) particular by taking the highest order terms of this expansion, we have that there exists some measurable function g+(-) which is bounded below and above, for each i, such that ((A,(u) (n)) ~'p n -- (A(()) uniformly in u.
13-1-181, Ax) and is an indepen-
As for the unigram sampling term, we note that by Proposition 77] we have that
(Aur.))) NEW (a)
P(Binomial((, Uga (vlu)) ~p
(S133)
uniformly in the vertices v, u. With this, we note that the same arguments via self-intersection allow us argue that
P((u, v) (( ~p n²
E i=0 Ew(a)
(Bi(AN) (Au, + (Au.)))))
(Au:
(S134)
which gives the claimed result.
E.2 Chaining and bounds on Talagrand functionals
In this section, let L >> 0 denote universal constant (which may differ across occurrences) and ((a) a universal constant which depends on a variable a (but for fixed a also differs across occurrences). For metric space (T', d), we define the diameter of T
A(T)
sup t2) 1
(S135)
We also define the entropy and covering numbers respectively by (T, d, e) == min n E N F T. S n, d(t, S e for t
e T}.
(S136)
en (T) == inf ( sup dtt, Tw) T, CT, T. < 2²") = inf {c > 0 N(t. (t. c) 2²").
(S137)
EE
We then define the Talagrand Ya functional
43 of the metric space (I" d) by
%a (T, d)
inf sup 2n/a (AA
(S138)
LET n20
where the infimum is taking over all admissable sequences; these are increasing sequences (An)) n20 of T such that |Aoll = 1 and |A,, S 2²" for all n, with (t) being the unique element A,, which contains t. We will shortly that this quantity helps to control the supremum of empirical processes on the metric space dT, We first give some generic properties for the above functional.
Lemma S18.
a) Suppose that d is a metric on T, and M > is a constant. Then (TT, Md) MTa(T, (T, d). UfU T,, then (U, S (T,
b) Suppose that (Tı, d2) and (T2, de) metric spaces, so d d1 + d2 is metric the product space T = T1 x T2. Then ya (T, d) S K(a)(Ta d2) + Ya (T2, dz)).
c) We have the upper bounds
%a < K(a)
20imen (n(
(log ( (IogN((T [(aaa/" (
de. (S139)
n20
d) Suppose thut || - is norm on R.m. d is the metric induced by - 1|, and BA = {o | & A). Then one has the bound A, e) S max((3A/e])] "a. 1}, and consequently Na (a (Ba, d) < Am) //a
Proof. The first statement in a) immediate, and the second part is Theorem 2.7.5 a) of Talagrand 43
38

---

For part b), suppose that A are admissable sequences for (T;, dz) such that
sup
2 2n/a (t)) - 27 (Ti, d,) for i = 1.
(S140)
E n20
If we then form the sequence of sets B, == { x A2 A E 1 for 2 and Bo = Ti x T2. we have that B, is partition of T for each n, |Bol 1 and |Bm.| = AA! || |A | 2 for each
n, meaning that B, is an admissable sequence for the metric space (T, d). Moreover, note that we have
( x (2) (2) ((A)())) + A(A2((2)
(S141)
for all sets A C Ti, A2 S 72 and 4 Ti, E T2. As result, if write (211,12) 1
(11) x A (12) for the unique set in B, for which the point (2) lies within it, then have that
2"/a 2n/a A(Bu(441, (2)) 2
Σ T 11/0 2 1//1//////AA/
A(4 n-
(41) + Σ 2 1/1 D21
(S142)
A00
In particular, taking supremum over all I. T then gives the result, as the resuling LHS is lower bounded by %o (T, d), and the resulting RHS is upper bounded by (T%,(T1, d1) Ya (T2, d2)).
For part c), the first incquality is Corollary 2.3.2 in Talagrand 43 As for the second inequality, note that if c S (T), then (TT, d) > 2 and consequently N(T, d, c) 2 2 + 1 (recall that both quantities are integers). Writing N,, = 2²", this implies that
(2))
(log(1 + Nn)) 1/a (en( ea+1 (T))
(log N(T,d,))) de.
(S143)
(T))(T)
As log(1 + N,.) s 2" 12g(2) for all n 2 0, summation over all n 2 0 implies that
Σ 2n/a (T) en+ (T)) s /. (oo(T)
(log 2/
de.
(S144)
n20
As we have that
en+1 2 cc)) 2 (1-21) 21/)
> 2m/"en (T))
(S145)
n20
combining this and the prior inequality gives the stated result.
For part d), we can calculate that
33 (a m 1/a m/ - Nlog d.)) 1/a de $
(log(3A//)) la de S 3Am!/o /' (log(1/))))o dy.
(S146)
For the remaining integral, note that if we make the substitution y = exp(-t"), then the integral equals
L (log(1/2))) dy J / 1e dl
(S147)
which we recognize as the mean of an Exp(1) random variabe in the case where = 1, and the variance of unnormalized N(0, 2) density in the case where a 2, and so in both cases the integral finite. The desired conclusion follows.
Before stating a corollary of this result involving bounds on the f-functional of some of the sets introduced in Theorem S5 we discuss some of the properties of these sets.
Lemma S19. Define the sets
(A = {U nad | S AA,, B2,0(A) = {U Raxd 10||,,00 $ A].
(S148)
(S149)
39

---

Moreover, define the metrics
dr (1U(1 V1), (U2, V2)) = [U1 - U221 + 11 12lla
(S150)
d2 (UU1, Vi), (U2, V2)) = [U1 -22122,00 [[V V22l2,00
(S151)
defined on the space Ru R=xd of pfirs of n matrices. Then we have that for U1, U2, V1, V2 (p(AF) (22, that
-U2V | I Apdr((U1, V1), (U2, V2)),
-U2 S 02, (UU1, Vi), (U2, V2)).
(S152)
Moreover, U (A), then U Br(ynA) also, and consequently if 22, then we have that U E 02 (A2,00 Bp cx)))
Proof. Begin by noting that, if U1, V1, U2 1/2 E Raxd are matrices, then have that
| U2V |F [V - 13)= + (U1 - U2) |Uil|=I|V - V2lle + 10 - U2]1=||V211=
and similarly
||, U2V2 = (1U - 1z) + (U1 U2) |x S |1 VV - V22l2,00 ||U U2|12,00
|V2|12.00
As result, we therefore have that in the case where U,, V1, U2 V22 all have 1-11 S Ap, then
V U2V2' S AF AF(1UI U211 F + [[V V2lle)
(S153)
and similarly if each of U1, V/1 U2 1/2 have 112,00 S A2 then
U - U2 s A (1IU1 02| + VIV V2ll2,0o)
(S154)
giving the first result of the lemma. The second part follows by noting that
max 8E(N) j=1
Uij
(S155)
i=1 1=
and taking square roots.
Corollary S20. With the same notation as in Lemma we have that for any constant >> 0 that
S19 and writing T Br(AF) (0
%o (T Cdx) 7o. (BrrA))) Cdr) < K(o)- CAr(nd) < K(a) 2/ 2/241/a ////
(S156)
(T T, C222 7a (B (A2, CdF) K(a) (nd)
(S157)
Proof. This a combination of Lemma S18 and Lemma S19
We now state result which illustrates the usefulness of the above quantity when trying to control the supremum of empirical processes on a metric space (T,
Theorem S21. Suppose (X,)t T mean-zero stochastic process, where dj and da are two metrics on T. Suppose for all s, f E T we have the inequality
P(XX, Xel 2 w) 2 ( (-min min
dz(s.t)² (pp'd((stt))) 1):
2
(S158)
Then have that
P sup [X, - XX| 2 Lu Lu(12(T,d)) d2) + +T, < Lex((-u).
(S159)
STET
Proof. This can be found within the proof of Theorem 2.2.23 in Talagrand 43
40

---

Corollary S22. With the notation of Theorem S5 bound
Lemma S79 and Corollary S20 if we have the
P(IE,, V) E (U, 22221
(S160)
2
< 2exp
(-min 128pm n "e (A, (U, V))2 16pm n- A2, 22 (1U, V), (Ü, V))
(S161)
then as a consequence we can deduce that
sup EU,( - - (
1/2
d A22 mpn
(S162)
(
npn
Proof. This is consequence of Corollary S20 and Theorem
S2I
E.3 Matrix Algebra
Proposition S23. Suppose that we have matrices U, X E Raxd with 2 d, and suppose that X is full rank matrix so a x²) ) > O. Then we have that
n --U - Xx min 1 =IUU 1 S QEO(d)
(S163)
V2(V2- - [0(n==o((XX)]
Now instead suppose we have matrices U.V E Raxd and matrix M E Raxd of rank d. Let M UM EVE M be a SVD of M. Moreover suppose that U-U = VVV, and |IVT M lop (a(MM/
Then we have that
min 1 - UM QEO(d) n
2n 2n -1- M
<
(S164)
(V2 1)nm)
Proof. The first part of the theorem statement is Lemma 5.4 of Tu et al. [44]. For the second part, we note that by Proposition S24 we can let = UM and V = VM E//2 for some orthonormal matrix Q. where ÚΣV the SVD of UVT, As a result, we can therefore apply without loss of generality Lemma 5.14 of Tu al. 44
which then gives the desired statement.
D
Proposition S24. Suppose that U.V E Raxd are matrices such that UV = M for some rank d matrix M R Moreover suppose that U VTV. Let M UM M be the SVD of M.
Then there exists an orthonormal matrix Q (d) such that V VM 1//2. particular, the symmetry group of the mapping (U, - UVT under the constraint U = VTV is exactly the orthogonal group (d).
Proof. Begin by noting that the condition U = VTV forces there to exist an orthonormal matrix R E (n) such that RU = V (e.g by Theorem 7.3.11 11 of Horn and Johnson (21). As consequence,
we therefore have that M = R R-V This is polar decomposition of M, and therefore as
the semi-positive definite factor is unique, we have that VV (Var 1/2 (V As E 22/227" where
M EV is the SVD of M, and we highlight that the polar decomposition of M is usually represented by M (UMVV77 (VM (VEVV)) As VVT = (Va, (1,/)//VVV (VM (V, again by e.g
Theorem 1.1 of Horn and Johnson (21 we have that there exists an orthonormal matrix Q E (d)
such that V E/22, giving the desired result.
Lemma S25. Suppose X E Ra
x is a symmetric matrix such that X = HAII where A E Rdxd
is full rank, and II Rnxd is the assignment matrix for partition of (n); that is, there exists partition of [n] into d sets B(1).... (dd) such that πy 1li E B()). Suppose further that II is of
full rank. Then have that a (X) A) min [[)].
Proof. Let A diag((B())) [(1) ..... (2). Then note that we can write
X= (ITA -1) AAA (MA)
(S165)
where (1)-1) is an orthonormal matrix. As result, can simply concentrate on the spectrum of the matrix AAA. As the smallest singular value of matrix product is less than the product of the smallest singular values, the stated result follows.
41

---

E.4
Concentration inequalities
Theorem S26. Suppose that H. is a graph on a verlex set friy..., nt, Ui...., U where the vertices are referred to root vertices, and the remaining verlices free vertices. We refer to such graph as a rooted graph. Suppose that all the edges in H have at least one free vertex as an endpoint. Write x (Z1...., 2m) for the collection of m variables 24 and let Y be statistic of the form
Y Σ
9x
II Kar,ayy
(S166)
2m E(p)
where the random variables tzy,z, are independent and {0, 1) valued with Cp I P( 1) I 1 Cp for all Vi, Wiz the coefficients Cg S 9r S |1g| < oo for some cg > 0; and i ~M j iff
(i is an edge within the graph H. Suppose that P. = n- for some < 1/m where ml (H) maxg<jsk(i
())( 2), v(j) minjAl2 A|2 v(A) and v(A) for a set of edges A indicates the number of vertices in A. Then there exist constants c, ô, A which depend only on Cg. Cp. |o H and a such that
P(|Y |[M]| P S exp((-A)
(S167)
for all A A
Proof. Without loss of generality suppose that ||gll 1. The proof is essentially the same as Vu 48 Corollary 6.4], where we extend the result derived for the asymptotics of subgraph counts that of a weighted count of rooted subgraph counts. To do so, we introduce some notation introduced within [48]. H has edges, and
set of pairs (z,,2,), we write 0ĄT for the polynomial ILEA O,T when interpreting T as a formal sum in the variables ax.s, (which we recall are {0, 1}
valued. We then define for 1 S j I & the quantities
E, [ max E[0AY1, = max (t)(t). (/A
(S168)
2
Let (A) denote the number of vertices specified within the set A, and let v(j) min| | v(A). With this, we note that E[y] (nn" p*))) and E[OAY) = mm o(A) have that
k-1A1) Consequently, we
E Y
max O nh P - EEEEEEEEEEE Ommin n (M) ph) h2)
(S169)
h2j
where the implied constants depend only on k. Cg and Cp- The same arguments as given in Claim 6.2 and Corollary 6.4 in 48 then be applied verbatim give the claimed result.
Lemma S27. Let T be statistic of the form
T
Σ
g(Ae,....,, )rm)
(S170)
where cg 5.(()) lo Then have that
E- =ecggn//m
P 2 eE(r')) s 2 2exp
(S171)
2 221g911
Consequently, we define
Ti Σ
g(Aay.... dems Ne), Ty
Σ
godey..., A Nt)
(S172)
where cg S 5.(-) S Io < oo as above, then we have that
Ti
= Oz (z log 1/2
)/2)
max L.K
(S173)
E.
TT
where the implied constant depends only and Cg-
42

---

Proof. The first part is an immediate consequence of Hoeffding's inequality for U-statistics [39] which states that for ((n m)!/nl) 'I' that
1-Pln/m
[ - -[]) = 21) - 2xp
(S174)
1
by substituting in 1 [E[U] and making of the bound [E[U] 2 Cg-
For the second part, we work conditionally on A₁ AE and note we can decompose Ti.m for each 1, m into a sum of statisties of the form T', one of order (p(nn) and (*) of order (n (corresponding to when some of the indices I; are equal) for S k S m. By applying the first concentration inequality to these m! n²² random variables, conditional on the (Ar, Aς), we note the RHS is independent of these quantities, and so the probability bounds hold unconditionally. Consequently, we know that asymptotically Ti, asymptotic to Ty from which we can then apply the resulting concentration bound for this term.
Theorem S28. Suppose we huve statistic of the form T Ax) = Pn ---111
E
...aa....>aa--..... Auz Ao)
II aā.
II Gā 00 (S175) JEJ
-EV3-1
$58
where à = (a, u, v) is a concatenation of u and v in order, g: 9: R8+1 + R is a positive function which satisfies Cy I g I 11 < 0o
sor for some constant Cg. and J is a possibly empty set of indices. Define X' (No, A3-1, Aus )o) where X is independent copy of X. Further define the statistic Tn, )w) = (n - 3)! n!
E ((( II W(X XD II W(G N4+1) Au, do]. (S176)
$58
JEJ
Then for any Pr = a a for a sufficiently small, we have that
(.u, - 1| =0x((1 (( )12)
max B,J.u.
(S177)
Tv n. (Au, do)
Proof. For this, we apply the above results. We begin by working conditionally on all of the X, whose collection we denote X, and note that by Theorem S26 by taking X = (log n) for some k >> I and union bound, we have that
T Tn, (dur Av) EETn,,, Aw) |^] (1+ E where E - -((( (log 1/2
n ((pp))
(S178)
uniformly over all Om n²) random variables with probability exp(O((logn)) As we have that E[Tn,e,. 2o) 1
Σ oEV8-1
g(Aag ... Aap-;; Av) II
w (Aaai,: II W WWaa dajm1)
$58
JEJ
(S179)
where the function is bounded below by co cp 8+11 and is bounded above by || we can make use of Lemma S27 show that
E ETnn Ao) Ao) 1N] = (( (( 1/2)
max
(S180)
S.Jau.
Th (Nur Av)
n1
from which the claimed result follows.
Remark 1. One natural question to ask about the necessity of the range of values of pn specified above. Generally speaking, one can show for Erdos-Rent Renyi graphs G(n.p) that the number of subgraphs Yn of H in Gn satisfy zero-one law, where
o(1) ifp < an -0000000p00000
P(Y: =0 = ((1) ip -
(S181)
for some constant cf c(H) which relates to the geometry of the graph G [6]. the latter regime, one can then show that Yμ ~ E(yul asymptotically again, and in the former this shows that the term asymptotically negligible. As the purpose of this result is to derive an asymptotic expansion for the sum of various statistics of the form Tf to the highest order, provided Pa. is of an order which avoids any of the "phase transition" " stages of the form above we could eventually generalize our results further. As this involves even more additional book- keeping, do not do here.
43

---

Lemma S29. Let be a finite index set of size [I] = m. Suppose that there exist constants 7 > 0, bounded non-negative sequence (pi)ier such that p; S for all and a real sequence (ti)ker- Define the random variable
x=
E a. - m
where
ax
indep
Bernoulli(Tp)) I.
(S182)
Then for all we have that
u² P([X) 2 u) 22ep (-min min 17 2 2111 27 m 110
(S183)
Proof. This follows by an application of Bernstein's 's inequality, by noting that X is a sum of independent mean zero random variables X; m--mm "rr-aa aa pt)t, which satisfy
X - S m- for all i, B[X S m 2
Lemma S30. Define the random variable
Y n - 1)
Σ
(pntaij (WA,,A)))TT.
(S184)
for some constants (Tzy). Write |T = Eitf T3 and || max [Ty). Then we have that
P P( 22 u) s eexp (eopp-mmin) min 128pm. n -1 17113
u²
u
(S185)
16pm n - -1
particular, when Túj = 1 for all i + j, we have that Y
Proof. Note that under the assumptions on the model (where we have that aij aji and W();, AU)
W(4, Ae) for all F j), we can write
Y
2
Σ (pm aij
W(A,, - TT.).
(S186)
n(n 1)/2
Note that
E(Ti + Tx+)² <
(T + + < 2
(S187)
{<}
max
[Te + T3: < max [Tyl
max زوح
Ty+1 < 2|
(S188)
i<j
Kgj
where have used the inequality (a + 6)2 < 2aa + 12) which holds for all a, b IR. Consequently, as a result Lemma S29 we have conditional on that
2
P P(M s 2exp (-min) mim
128pm- in 41T 16p 21 })
(S189)
As the right hand side no dependence on X, taking expectations gives the first part of the lemma statement. For the second part, note that if Ti for all * then we have that | < n² and
[| = 1, and consequently
2
F( 2 u) 2exp (
(-min min 128pm n 2 16pm n
(S190)
In particular, this implies that Y Op((n² Op.((22p))11/3) 11/22)
44

---

E,5 Miscellaneous results
Lemma S31. Suppose that A E Rm is matrix whose diagonal entries are a, and off-diagonal
entries are 5, so Ai, ad;z + (1(1)s;)) where 5zz is the Kronecker delta. Then A has an eigenvalue a (m -1)3 of multiplicity one with eigenvector Lms and an eigenvalue 3 of multiplicity
whose eigenvectors form an orthonormal basis of the subspace (v (v, 1m) = 0). For the subspace {v (v, mm) 0}, we can take the eigenvectors to be
V/-
(em,1 em,i+1) for [m V2
where em, are the unit column vectors in IRm, The singular values of A are la- B] and la+ (K 1)3). Consequently, we can write A = UVT for matrices U, V.V& E TRmx with UUT VVT, where the rows of U satisfy
Us. a + 3(m 1)12/2
la
3/1/2
em,
em,
(S191)
Vm
V2
U,. la + 3(m 1)12/2
|a- 1a-31 -1112
Em,1
fmr (2....,
(S192)
Vm
v2
1/2 for all and Consequently, we then have that ||Uz.112 < (2/a 3(m 1)1/m + - -1112) mingzs [|U, -U, UU-l12 = (lx=3)))/22
Further suppose that B = am/(mmm 1). Then provided a > 0, A is positive semi-definite, is of rank m 1, with singular non-zero eigenvalue cmm(m 1) of multiplicity m 1. Consequently one can write A UUT where U (m-1) and whose columns equal the v /am/ - T)us. In particular, the rows of equal
U1 ( 2(m -
(22m-) 22mm-1) 1)
U.. = 2(m - 1) 1 1/2 C 1,11
1122 c 1m for m].
Consequently, one has that ||U Vam/(m- for all and moreover we have the separability condition minigi</sm ||4 - 1111122 = (am/(m 1))
Proof. It is straightforward to verify that A has eigenvalue of a - (n 1)3 with the claimed eigenvector. For the second part, we note that the characteristic polynomial of is
det(A- - tl) = (a
-)== (a+ (n 1)3 1 t)
always take and A has eigenvalues equal to 8: A is symmetric, know that cigenvectors to be orthogonal to each other, and consequently the cigenspace associated with such an eigenvalue must be subspace of {e (v. 1m) 0). As both of these subspaces of dimension m - 1, it consequently follows that they are equal. We then highlight that if is a symmetric matrix with eigendecomposition A QAQ" for an orthogonal matrix Q, then the SVD is given by QlAlsgn(A)QQ" and
write A UVT with U A|A[1/2 and V Qsgn( A|) such that
UUT = VV*. This allows us to derive the remaining statements about the matrix which hold in generality. The remaining parts discussing what occurs when -a/(m - 1) follow by routine calculation.
Lemma S32. Let (z)) (1 + exp(-x)) be the sigmoid function. Then there exists a unique E IR which solves the equation
ao (v) B + (
(S193)
for a. 8 s > and 3 IR if and only if 3 a and 8 + > 0. Moreover y > if and only if + 7/2 a/2.
Proof. Note that (xr) function whose range (0, a) on E (-o0, and strictly monotone increasing on the domain. Similarly, B + (o(-y/s) is strictly monotone decreasing with range (8, 3 + 7), and so simple geometric considerations of the graphs of the two functions gives the existence result. For the second part, note that the ranges of the functions on the LHS and the RHS on the range y > are (a>/,.a) and (8, 3 + 7/2] respectively, and so the same considerations as above give the second claim.
D
45

---

Lemma S33, (e) = (e1)/(1 + c²) be the sigmoid function. Then any x, y E R, we have that
- -log(1 -(x)) 2 - log(1 (v)) + ( - y) + E(x y)
(S194)
where
2 A=2 122 E(2)
= |u| - A, if either |>| S A or b A.
(S195)
1 min (22, 2//1
Proof. Note that by the integral version of Taylor's theorem, for a twice differentiable function f one has for all æ, y E IR that
f(x) f(v) (1( - y) f (1 (f= (1-1
(1- y)² dt.
(S196)
Applying this to f(x) = - log (z) gives
/ (1- (1-t)(x y)² (1- ())) dt (S197)
log (I) log (yy + (-1+ 4)+ /
where d'(x) e" (1 -=)2 Applying this to f(x) = log(1 - o (z)) gives
-log(1 ( = - 1og(1- - (w)) + (z) v)+ / (1- y)²o (tx + (1 - (1-))y) dt (S198)
As the integral terms are the same, we concentrate on lower bounding this quantity. To do so, we make use of the lower bound o' (1x 2 e /4 (Lemma 68 Davison and Austern [11] which holds for all x E R. We then note that if [x]. ly| S A, then we have that
log(11 (x)) - log(1 (v)) + (v) v) + S (1 - ()(=-))00 + (1 t)y) dt (S199)
2 logo - + (v) y) + --1
2 (x y)
(S200)
Alternatively, we only make use of the fact that |x| I (without loss of generality the argument
essentially equivalent if only assume that lyl A), then we have that
S. (1 (1-1)o'( 1)o'(1x (1 - (3))(x y)² di 2
(1 l)e les (1 (1-))(( y)² dl
(S201)
t)e-lllle -1--0)00-- (x y)² dt
(S202)
e |a| 1| yl + e |k-y/ -13
(S203)
min (xr y) 2/xr yl}
(S204)
and consequently we get that
1 e minf lx - y1 2/x -y
- llog(1 - (x)) 2 - log((1 (1)) + +z - y) +
(S205)
as claimed.
Lemma S34. Suppose that we have a function
m
f(X)
min (x2 2(x,11
(S206)
m
++=11
Then if f(X) S r, we have that m Eii=1 [Xis
1r 1/2
Proof. To proceed, note that if we have that
E[min{ 2x r
(S207)
for non-negative random variable X, then by Jensen's 's inequality we get that
(E[XI[X~ < 2]]) + | 2 2] < B[min(X² 2X Sr
(S208)
and consequently E[x] < + by decomposing E[X] into the parts where X > 2 and X < 2. Applying this result to the empirical measure on the |X,yl across indices i, E [m]] gives the desired result.
46

---

F Minimizers for degree corrected SBMs when a /
In this section, we give an informal discussion of how to study the minimizers of R., (MM) for degree corrected SBMs when the unigram parameter & 1. We begin by highlighting that (M)) does not concentrate around its expectation when averaging over only the degree heterogenity parameters 8,, which rules out using similar proof approach as to what was carried out earlier in Appendix 1.
Recall that we were able derive that the global minima of (M) was the matrix
2Ew(a) Mi log BBO
Pa(i).c())
(S209)
Para Pct) (0, P + +,5 p(g)) c())
When a 1 or the 0g are constant, this allows us to write M = IMMIT where II is the matrix of community assignments for the network and M is some matrix, which allows us simplify the problem. If we supposed that the 0 actually had some dependence on the c(i) and were discrete in that 0g le(i) = Q for some discrete distributions Qi for [ki], then we could fact employ the same type of argument as done throughout the paper. The major change is that then the embedding vectors would each concentrate around vector decided by both a) their community assignment, and b) the particular degree correction parameter they were assigned. This would then potentially effect our ability to perform community detection depending on the underlying geometry of these vectors. One possible idea would be to explore R,, (M) partially averaged over the 0, we divide the 0 into B bins where B = T& for some 3 E (0, 1), and average over only over the refinement of the 0g as belonging to the different bins. This would be similar to the argument employed Davison and Austern 11
alternative perspective to give some type guarantee on the concentration of the embedding vectors is to study the rank of the matrix M If we are able to prove that is of finite rank even as n grows large, then we are able give a convergence result for the embeddings embedding dimension d is greater than or equal to r. To study this, it suffices to look at the matrix
soon as the
(M log (0 pa-1 + 1
(S210)
and argue that this is low rank (due to the logarithm, we can write M as the difference between this matrix and matrix of rank k, which therefore also low rank). The entry-wise logarithm is complicating factor here, as otherwise it is straightforward to argue that the entry-wise exponential of this matrix is rank 2. One can reduce studying the rank of the matrix Mr studying the rank of the kernel
KM ((x, (z), (y, cy)) log (x--1 pa--1 + y pap
(S211)
of an operator (2(P)) > (P), where P is the product measure induced by 0 and the community assigmment mechanism c. As KM is finite rank r if and only if it can be written as
KM (xx,
Σ ca(x,,c))iaa
(S212)
for some functions 6i, vi, it follows that the matrix (M)) will be of finite rank r also. Indeed, this representation forces that M TVT for some matrices 4; V Raxr, meaning that Mi of rank S r; Corollary 5.5 of Koltchinskii and Giné (24 then guarantees convergence of the eigenvalues of the matrix M the operator K M so that M is actually of full rank.
47

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction match the theoretical contributions of the paper. These are supported by experimental verification. Similarly, where theoretical results are not obtained we investigate these scenarios using simulation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We highlight and discuss the assumptions required for the theoretical results presented within the paper and detail in the appendix. We demonstrate empirically the performance of procedure when these assumptions are relaxed, if theoretical results were not obtained.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
48

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Due space constraints all proofs appear in the supplemental material. We provide intuition for these proofs in the paper where space allows. Complete proofs are included in the supplemental material, along with all required Lemmas and exact assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We detail the experimental setup used in this work in the supplemental procedure, along with providing all code required to run and replicate these experiments also.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
49

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have included anonymized version of the code repository used create all experimental results in this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ wttppsscccppbllic////ccc
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
We provide sufficient detail in the main text to understand the experimental results presented. In the appendíx, completely detail all experimental details, along with providing the exact code used as supplemental material.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For all experimental results we either show error bars corresponding one standard error or all simulation results (in the case of box plots).
50

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computation required for individual experiments was relatively small (in terms of both memory and time) and is detailed in the appendix. These were run computing cluster.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have ensured the research conforms with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
51

---

Answer: [NA]
Justification: This paper provides theoretical guarantees for community detection a specific class of statistical network models. Any potential societal impacts, positive or negative, will be ancillary from the theoretical focus of this paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: As this work thcoretical guarantees for community detection in specific class statistical network models, such safeguards are not applicable.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We credit the original owners code and data used.
Guidelines:
The answer NA means that the paper does not existing assets.
52

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
We provide an anonymized zip file which details the code used to generate all results.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Crowdsourcing or human subjects were not used in this research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Crowdsourcing human subjects not used in this research.
53

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
54


Reviews:
[{"review_id": "1NFBdylyrH", "reviewer": "Reviewer_NUS8", "summary": "The performance of node2vec for community detection in the degree-corrected stochastic block model is studied. It is proven that for sufficiently sparse DCSBMs, node2vec followed by $k$-means results in a clustering with only a vanishing fraction of misclassified vertices. Experiments are performed to demonstrate the results.", "questions": "Is there any hope of extending the results to partial recovery in the sparse regime? That is,  $\\rho_n=\\Theta(n^{-1})$ so that the average degree remains bounded as $n\\rightarrow\\infty$.\n\nCan the results be extended to the case where the number of communities grows with $n$? If so, how fast can it grow with $n$?\n\nThe NMI$\\approx0$ that is shown in Figure 3 is surprising. Can we improve this by taking a different Laplacian?", "limitations": "The authors have adequately addressed the limitations by clearly stating the assumptions.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is very well-written and pleasant to read. \n\nThe results are extremely useful in understanding the performance of node2vec in downstream tasks.", "weaknesses": "The presented results are interesting, but not much intuition is provided.\n\nMinor comments:\n* The sentence from lines 21 to 24 is unnecessarily long and difficult.\n* on line 110: shouldn't $d\\ge O(\\kappa)$ be $d=\\Omega(\\kappa)$? Or do you mean something else?\n* Brackets mismatch in the $\\log\\sigma$ at the end of (10)\n* The $\\mathcal{E}$ (presumably the edge-set) of (7) is not introduced\n* The notation $A_{2,\\infty}$ in Theorem 2 collides with the adjacency matrix notation.\n* Figures are too small", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading of our paper and pointing out some further details which can improve it. Below we address each of the mentioned weaknesses and questions. \n\n## Weaknesses\n\n> The presented results are interesting, but not much intuition is provided.\n\nWe aren't certain whether this is asking for intuition about the proof technique or the bounds produced (or something else). Here’s some intuition for the proof technique - we are happy to provide further summaries where it would be helpful and can add to the revised version of the paper.\nKeeping to the SBM case, the proof works as follows - we show that the probability that an edge $(u, v)$ is positively or negatively sampled within node2vec concentrates around a function only of the underlying communities of vertices $u$ and $v$, which we label $c(u)$ and $c(v)$ respectively. With this, we are able to argue that the node2vec loss concentrates uniformly (in a neighborhood of their minima) around a function whose minima \n$M^*\\\\in \\\\mathbb{R}^{n \\\\times n}$ \nsatisfies \n$M^*_{u, v} = \\\\tilde{M}_{c(u), c(v)}$ \nfor some matrix $M$. \n\nThis allows us to show that any set of embeddings $\\\\omega_u$ which minimize the node2vec loss will converge (up to rotation) to vectors $\\\\eta_{c(u)}$ which depend only on the community label, which consequently allows us to give consistency guarantees for clustering algorithms such as k-means.\n\n> Minor Comments\n\nThanks for pointing these out, in particular the typo about $d=\\\\Omega(\\\\kappa)$, the poor use of $A_{2,\\\\infty}$ and the unnecessarily long sentences. We have updated these and the bracket mismatch. $\\\\mathcal{E}$ is defined at the start of section 2, but we should highlight this again when we first use it. We will also make all figures larger and clearer when the paper is revised.\n\n## Questions\n\n> Extend to partial recovery in the sparse regime\n\nDoing so would be very interesting but challenging, as studying random walks on the graph in the exactly sparse regime is substantially more difficult than in the denser regimes. To give some intuition for why, suppose we simply have an Erdos-Renyi graph (i.e a single community) with probability $p = \\\\lambda / n$ for $\\\\lambda > 1$ (so we are in the regime where the graph has a single giant component), and that we restrict the graph to this giant component. A more tractable contiguous model - based around taking a random multigraph, expanding the edges to be paths of random length, and then attaching Galton-Watson trees to each vertex - for such graphs is given by Ding, Lubetzky and Peres [1]. This has been used successfully to describe properties of random walks on this graph (see for example the paper [2] discussing mixing times of the simple random walk on an Erdos-Renyi graph). This is one possible avenue which could be explored, although it would require being able to generalize the structure theorem of [1] to stochastic block models.\n\n[1] Jian Ding, Eyal Lubetzky, Yuval Peres. Anatomy of the giant component: The strictly supercritical regime. European Journal of Combinatorics, Volume 35, 2014, pp. 155-168.\n\n[2] Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres and Allan Sly. Random Walks on the Random Graph. The Annals of Probability, Vol. 46, No. 1 (January 2018), pp. 456-490.\n\n> Number of communities growing in $n$\n\nYes, this is the case. In Theorem 3 (and consequently Theorem 4, which gives the actual guarantees for community detection) the embedding dimension $d$ is said to equal the rank of the matrix $M^*$. It turns out that typically equals the number of communities themselves - this can be seen to be the case for the SBM($n$, $\\\\kappa$, $\\\\tilde{p}$, $\\\\tilde{q}$, $\\\\rho_n$) model as described in the example below Theorem 2. As a result, from the rates we can take $\\kappa = o(n \\\\rho_n)$ and maintain consistency. (While this is clear under scenarios (i) and (iii) from the stated bound, this is also the case in scenario (ii), as the $o_p(1)$ bound arises from a term which dominates the $(\\max( \\\\log n, d) / n \\\\rho_n)^{1/2}$ term which is still present in this scenario.)\n\n> Choice of Laplacian for Figure 3\n\nFor the results shown here we used the normalized Laplacian. Some quick experiments indicate that choosing the standard Laplacian or\ndifferent clustering methods (see rebuttal to znFf) would lead to the same results.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ad29fAz99n", "reviewer": "Reviewer_znFf", "summary": "Theoretical results showing the consistency of node2vec embedding for community detection in SBMs and DCSBMs using k-means clustering.  Versions of this problem have been approached in other work, for example, node2vec rephrased as a matrix factorisation problem [39], and rank $d$ approximations for DeepWalk [51]. This paper addresses the issues in previous works relating to approximations made within previous work, such as an Frobenius norm approximation to the cross-entropy loss, at the cost of weaker consistency results, $\\ell^2$-norm as opposed to two-to-infinity norm.", "questions": "The main issue is how do the results here compare to the work of [10] and [11]? Section 1.2 on Related Works describes how this work extends [39] and [51], but the fact that these two strongly relevant papers are only given a brief sentence feels a significant oversight.\n\nWhat conditions are needed/prevent two-to-infinity norm consistency compared to the $\\ell_2$-norm in this setting?\n\nWhat about other clustering algorithms other that k-means? The results show asymptotically k-means will give the correct clustering, other papers [41] show that there are issues for fixed $n$ which are avoided by other clustering algorithms such as fitting Gaussian mixture models. Practically, any matrix $M$ transformation $U \\rightarrow UM$ and $V \\rightarrow VM^{-\\top}$ is a valid embedding which will affect the k-means clusters.\n\nSimilar results for core-periphery SBMs (On a 'two-truths' phenomenon in spectral graph clustering, Priebe et al), another important type of SBM for practical embeddings?", "limitations": "Error bars needed in Figures 1 and 2 showing the multiple experiments described in Lines 296-297. Needs comparison to other embedding algorithms, for example, spectral embedding. Misleading experiment given in Figure 3 (see above).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The strength and novelty of this work lies in the technical results in the Appendix. The paper would be better served with this material given more attention, perhaps in a journal rather than conference paper. However, I was unable to give the material in the Appendix a full read through, so I am working under the assumption that these results are technically sound. More clarity would be needed to show how the results differ from previous work (see below).\n\nThere are some important insights about the use of node2vec for node clustering in different types of SBM and DCSBM. For example, setting $U = V$ in constrained DeepWalk where $p \\le q$ is unable to cope with disassortitive (DC)SBMs. This feels like a significant issue and I would be interested to learn more why random walk based embedding algorithms fail on bipartite-like networks. It is also interesting that node2vec on DCSBMs produce clusters that only depend on the SBM community and that the degree parameters $\\theta$ are unimportant. Being able to perform k-means clustering directly on the node2vec embedding is an advantage over, say, spectral methods where hyperplane or spherical projection is required to remove the effect of $\\theta$ from the embeddings.", "weaknesses": "Without delving too deeply into the mathematics in the Appendix, it is not obvious to me how this paper extends the results in [10] and [11] which only get briefly mentioned on Lines 121-123. These two papers analyse the asymptotic distribution of the node2vec embedding for latent position graph models, a wide range of models which include the SBM and DCSBM. It is not clear how the theoretical results in this paper extend those results, except for looking at the consistency for k-means clustering, which is non-specific to the node2vec embedding stage. I don't want to say that the contribution in this work is 'poor', but it is hard to know what is new here in the current state.\n\nUnderstanding random walk embedding algorithms is important, but they have been overtaken by graph neural networks designed for this exact problem, rather than ideas shoehorned in from natural language processing.\n\nThe experiment shown in Figure 3 is somewhat misleading. I read this plot as showing that k-means clustering is unsuitable for spectral embeddings of DCSBM, like the political blog network, rather than spectral embedding failing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed reading of our paper and the constructive feedback.\n\n## Weaknesses\n\n> ... how this paper extends the\nresults in [10] and [11] ...\n\nThe comparison in the paper was limited due to space constraints, and we will expand the discussion. In summary, [10] and [11] study node2vec with $p=q=1$ in the constrained setting (where $U = V$), and focus on giving more abstract guarantees for the gram matrix in the abstract setting of graphons. In [10] the norm guarantees extend only to the L1 norm between the gram matrix of the embeddings and the minimizer, which is not sufficient to give guarantees on the individual embeddings. In [11] the norm guarantees are upgraded to the L2-norm, albeit with less optimal rates of convergence than our paper. In our paper we also give guarantees for node2vec in full generality (no restriction on p/q) and give the calculation details for SBMs and DCSBMs to explicitly show what the asymptotic distribution can be in certain regimes.\n\n> ... overtaken by graph neural networks ...\n\nWhile GNNs are more performant than node2vec and reflect the current state of art, there is value in understanding why methods transferred from NLP work (when a-priori there is no apparent reason why they should). We answer this by showing that random walks on the graph recover the latent information required for community detection (in models with community structure). We argue there is also partial relevance of these results even for GNNs - for example, in the unsupervised setting the GraphSAGE authors [1] recommend using the GraphSAGE encoder within the node2vec loss. In the absence of nodal covariates or a supervised loss, the only way in which GNNs can learn relevant information is if graph sub-samples carry relevant latent information for downstream tasks at hand, which is the flavor of our type of results.\n\n[1] Hamilton, William L. and Ying, Rex and Leskovec, Jure. Inductive Representation Learning on Large Graphs. Neural Information Proccessing Systems, 2017.\n\n> The experiment shown in Figure 3 is somewhat misleading...\n\nWe included this experiment to highlight that many community detection methods struggle with this degree heterogeneity. As discussed in the rebuttal to NUS8, we see this same performance for different variations of the graph laplacian. We considered using a gaussian mixture model rather than k-means with the spectral embeddings and saw the same poor performance. \n\n## Questions\n\n> The main issue is how do the results here compare to the work of [10] and [11]? \n\nSee the above discussion. We will expand this in the revised paper.\n\n> ... two-to-infinity norm consistency compared to the $\\ell_2$-norm in this setting?\n\nTo provide additional context for why this is relevant - obtaining two-to-infinity norm consistency as a result would allow for our theoretical guarantees for community detection to be upgraded to say that exact recovery holds with asymptotic probability 1. With our current approach, this is out of reach as we apply results similar in flavor to the Davis-Kahan Theorem in order to go from bounds between gram matrices to those of the individual factors. These bounds are tight in general, and so in order to obtain tighter bounds we need some explicit structure on the minimizers of the loss function. For example in [2] and [3], the authors use theorems which exploit the fact spectral clustering takes the eigenvectors of matrices with an explicit rich probabilistic structure. In our scenario, the mix of the cross-entropy loss with a low-rank matrix factorization problem prevents us from being able to write down an explicit minimizer, which means being able to apply these type of results is (unfortunately) unlikely.\n\n- [2] Strong Consistency, Graph Laplacians, and the Stochastic Block Model. Shaofeng Deng, Shuyang Ling, Thomas Strohmer. Journal of Machine Learning Research, 22(117):1−44, 2021.\n- [3] Strong Consistency of Spectral Clustering for Stochastic Block Models. Liangjun Su; Wuyi Wang; Yichong Zhang. IEEE Transactions on Information Theory, Volume: 66, Issue: 1, January 2020.\n\n> What about other clustering algorithms other that k-means?...\n\nThis is an interesting question. Doing some reviewing of the literature on GMMs, they frequently assume that the data are derived from a GMM in order to give guarantees, and don’t seem easily applicable in our scenario. One way of interpreting our results is that for e.g 99% of nodes, with asymptotic probability 1 as $n \\to \\infty$, nodes in separate communities are contained within separated spheres of radius $\\delta/4$, and the minimum distance between spheres is $\\delta$. This implies that e.g a DBSCAN algorithm (ignoring the distinction between core and border points) with an Eps parameter of $\\delta/4$ would correctly recover the communities of >99% of nodes. One could probably use similar logic to argue that a sufficiently well initialized EM algorithm (with a robust maximization step) would converge, but this is orthogonal to the work of the paper. We will add a discussion for DBSCAN as it follows very quickly from the definition of that algorithm, and if we are able to find any references for GMMs which are easily applicable in our scenario, we will include this also.\n\n> ..core-periphery SBMs ...\n\nThis is doable with our results. We do not have space to include it here (we can provide it as an additional comment if desired) but we can show that for the core-periphery 2 group SBM as given in the paper, the learned embeddings will be separated with a gap of order of the largest edge probability, allowing community detection. The finite sample performance would be an interesting future direction.\n\n## Limitations\n\n> Error Bars\n\nThese are included but are too small. We will increase the size.\n\n> Comparison to other embedding algorithms\n\nIn the appendix we examined the rates of convergence for our proposed method. We also included an additional real data example, getting similar results.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DT8rWY0D02", "reviewer": "Reviewer_DE6D", "summary": "The paper presents theoretical results for the quality of embeddings learned by random walk based methods like DeepWalk and its generalization node2vec. More precisely, the main result shows that embeddings learned node2vec, and DeepWalk as a special case of node2vec, preserve the community structure of graphs that exhibit a community structure. This is formalized for graphs generated by a stochastic block model (SBM), a common tool for the analysis community detection algorithms. The paper is mostly theoretical with experimental results based on synthetic graphs generated by SBM.", "questions": "Comment on the above issues, in particular why the influence of p and q in node2vec(p,q) is not thoroughly analyzed. I see the short discussion after Theorem 2 but cannot gain much from it. Also, Corollary 5 does not make sense as scenario i) is DeepWalk with p=q=1.  Should the corollary read $\\tilde{p} > \\tilde{q}$ ?", "limitations": "The paper does not present a new approach so the limitation section does not really apply here. The assumptions for the theoretical results are correctly shown, if this can be considered a limitation.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper provides theoretical insights into a widely used embedding algorithm.\n- The theoretical results are non-trivial, and the proof techniques are advanced.\n- Overall, the paper is well-written.", "weaknesses": "- The considered problem is too specific. Of course, DeepWalk and node2vec are widely used but community detection is just one of the application of node embeddings. In the appendix, the authors discuss node classification and link prediction but my understanding is that this is again based on community structures and not really convincing. There are other factors that influence node labels such as structural roles, node degree, etc.\n- The paper is about node2vec but the effect of the p and q parameters is not really analyzed. The results would have been much more interesting if they analyzed the interplay of p and q in node2vec and p and q in SBM. In particular, given a graph G generated by SBM(p, q) what values p, q in node2vec(p,q) would be necessary to preserve the community structure of G.\n- The informal Theorem 1 is actually confusing. It does not say anything about the structure of the graph or the number of communities c(u). If the graph consists of connected components or the number of communities is n, then the result is trivial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed reading of our work. Below are our responses to some of the weaknesses and questions about the paper.\n\n## Weaknesses\n\n> The considered problem is too specific...\n\nIt is true that there are other frequent applications of embeddings, which our paper does not focus on (with the exception of the remarks in the appendix). This is a criticism which applies more broadly across the theoretical literature (e.g the literature on the theory for spectral clustering of networks). The reason why our discussion in the appendix ends up being based on community structures is because we assume the graph arises from a model where community labels are the main nodal latent information, and our results show that that the embeddings learned do reflect this structure. Generally, if learned embeddings capture some statistic of nodal attributes, it is also necessary that these attributes are predictive for the task in order to say something meaningful about the task performance. \n\nBecause our approach depends on applying a generative model to a graph, we need suitable graph models which reflect these additional factors - such as node degree - to be able to analyze them. We highlight that part of our results apply for DCSBMs models, which take the node degree into account. For these models, we show that Deepwalk (node2vec with p = q = 1) learns a representation which is free of the degree heterogeneity parameters, even though it is an important predictive factor for whether two nodes are connected. As a result, one can not always assume learned embeddings capture all the relevant information to complete these tasks. We do ultimately agree though that more in-depth investigations along these lines would be interesting and valuable work. \n\n> the effect of $p$ and $q$ is not really analysed\n\nThis is true, and is because the formula for the sampling probabilities for the second order random walk are substantially more complicated to specify, than when $p = q = 1$ in which case the random walk resolves to a (stationary) first order random walk. There are some things which could be potentially investigated numerically - for example, given a particular 2-block SBM model, one could numerically calculate the gap between the two vectors which the embeddings cluster around as a function of $(p, q)$. In theory, the larger this gap, the quicker the convergence of the community detection (as given by Theorem 4). However our numerical experiments seem to suggest that, at least within the regime we study, the effects of $(p, q)$ on the downstream performance seem to be minimal as soon as $n$ is moderately sized (see e.g Figure S6), and so the value add of such a simulation seems minimal. \n\n> The informal Theorem 1 is confusing...\n\nThere is some additional context above the informal theorem statement which avoids these trivialities. We can revise the theorem statement to make it more clear by explicitly including the description of the SBM (and highlighting that it is connected w.h.p) within the theorem statement - thank you for highlighting this.\n\n## Questions\n\n> why the influence of p and q in node2vec(p,q) is not thoroughly analyzed...\n\nThe discussion after Theorem 2 relates specifically to Deepwalk, and considering what happens for a particular SBM model (the planted partition model). If this comment concerns how this discussion relates to node2vec, one possible source of confusion is that the node2vec parameters $p$ and $q$ are also frequently used as the parameters in the planted partition model, which is discussed after Theorem 2. While we use $\\\\tilde{p}$ and $\\\\tilde{q}$ for the planted partition model parameters to prevent notation overloading, we can see that this could either do with changing (or be introduced more strongly) to prevent any possibility of confusion. We will improve the clarity of this when we revise the paper.\n\n> should read $\\\\tilde{p} > \\\\tilde{q}$?\n\nCorrect, thanks for catching this!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would again like to thank each of the reviewers for their time and effort in reviewing our paper, and their thoughtful comments and feedback - particularly around typos and some parts of the paper which could be made clearer - which will help us to improve our paper. We have responded to the comments re: weaknesses and questions for each of the reviewers as a response to the individual reviews, and are happy to respond to any additional inquiries.

Meta-review: The paper examines the problem of community recovery based on node embeddings learned by the well-studied Node2Vec model. Despite the fact that random walk embeddings have been widely studied in the past ten years (and have currently been overtaken by GNNs), such theoretical studies are still very relevant providing several insights about their functioning.  The authors have adequately addressed most of the reviewers' concerns. Therefore, I recommend accepting the paper, suggesting the authors to properly address the reviewers' comments in the final version.
Decision: Accept (poster)