* Poincaré sphere Example 4.3.2
  * polar decompositions §5.1
  * principal logarithm §5.2
  * rescaled exponential map §4.3.2, Definition 4.3.1
  * Riemannian submersion §6.2, Definition 6.2.2
  * $S(\nu)$ §1.5
  * $\mathrm{Se}(N)$ Theorem
  * separating set Definition 3.1.3, §4.2.2
  * singular value decomposition §3.2, §3.2
  * SVD decomposition §5.1
  * tangent focal point Definition 4.2.2
  * Thom space §4.3.2
  * triangulable §4.3.1
  * variation of a curve §2.3.2
  * vector bundle §4.3.2
  * vertical bundle §6.2
  * vertical vector field 1st item
  * $X(d)$ §1.7
  * $\gamma_{v}$ §1.5
  * $\nu$ §1.5, §2.1.1
  * $\rho$ §1.5


# Network community detection via neural embeddings

Sadamori Kojaku  Center for Complex Networks and Systems Research, Luddy
School of Informatics, Computing, and Engineering, Indiana University,
Bloomington, USA  Filippo Radicchi  Center for Complex Networks and Systems
Research, Luddy School of Informatics, Computing, and Engineering, Indiana
University, Bloomington, USA  Yong-Yeol Ahn  Center for Complex Networks and
Systems Research, Luddy School of Informatics, Computing, and Engineering,
Indiana University, Bloomington, USA  IU Network Science Institute (IUNI),
Indiana University, Bloomington, USA  Santo Fortunato  Center for Complex
Networks and Systems Research, Luddy School of Informatics, Computing, and
Engineering, Indiana University, Bloomington, USA  IU Network Science
Institute (IUNI), Indiana University, Bloomington, USA
<EMAIL_ADDRESS>
###### Abstract

Recent advances in machine learning research have produced powerful neural
graph embedding methods, which learn useful, low-dimensional vector
representations of network data. These neural methods for graph embedding
excel in graph machine learning tasks and are now widely adopted. However, how
and why these methods work—particularly how network structure gets encoded in
the embedding—remain largely unexplained. Here, we show that shallow neural
graph embedding methods encode community structure as well as, or even better
than, spectral embedding methods for both dense and sparse networks, with and
without degree and community size heterogeneity. Our results provide the
foundations for the design of novel effective community detection methods as
well as theoretical studies that bridge network science and machine learning.

## Significance statement

Graph embeddings map network data onto low-dimensional vector representations,
which can be easily integrated into machine learning applications. We
demonstrate that, for networks with planted communities, shallow linear neural
networks for graph embedding—node2vec, DeepWalk, and LINE—capture the
community structure down to the theoretical community detectability limit.
Using benchmark networks with built-in communities, we show that neural
embedding is a practical and robust approach to representing community
structure, with comparable or even superior performance with respect to
spectral embedding methods. Our results reveal that neural graph embedding can
achieve the fundamental limit of community detectability without the need for
deep layers and non-linear activation functions, laying the foundation for
future research at the interface between network science and machine learning.

##  1 Introduction

Networks represent the structure of complex systems as sets of nodes connected
by edges [1, 2, 3] and are ubiquitous across diverse domains, including social
sciences [4, 5], transportation [6, 7], finance [8, 9], science of science
[10, 11], neuroscience [12, 13], and biology [14, 15, 16]. Networks are
complex, high-dimensional, and discrete objects, making it highly non-trivial
to obtain useful representations of their structure. For instance,
recommendation systems for social networks typically require informative
variables (or “features”) that capture the most important structural
characteristics. Often, these features are designed through trial and error,
and may not be generalizable across networks.

Graph embeddings automatically identify useful structural features for network
elements, most commonly for the nodes [17, 18]. Each node is represented as a
point in a compact and continuous vector space. Such a vector representation
enables the direct application of powerful machine learning methods, capable
of solving various tasks, such as visualization [19, 20], clustering [21, 22],
and prediction [23, 18, 24]. This representation can facilitate the
operationalization of abstract concepts using vectorial operations [25, 26,
20, 27, 28]. Graph embeddings have been studied in various contexts. For
example, spectral embedding stems from the spectral analysis of networks [17,
29]. A closely related formulation is matrix factorization [30, 31]. Recent
years have witnessed a substantial shift towards a new paradigm of graph
embeddings based on neural networks [32, 33, 34, 35, 36, 37, 20, 38, 22, 39,
40], which have demonstrated remarkable effectiveness across many
computational tasks [23, 34, 38, 39, 35, 39, 40]. Yet, due to the inherent
black-box nature of neural networks, how and why these methods work is still
largely unknown, and we lack firm understanding of the process of encoding
certain network structure onto embeddings.

One of the fundamental and ubiquitous features of networks is community
structure, i.e., the existence of cohesive groups of nodes, characterized by a
density of within-group edges that is higher than the density of edges between
them [41, 42, 43]. In practice, neural graph embedding methods are widely used
to discover communities from networks [31, 34, 38, 26].

The stochastic block model (SBM) is a basic generative model of networks with
community structure [44, 45] and is regularly used as a benchmark for
community detection algorithms. Some clustering methods are able to correctly
classify all nodes into communities in large and dense networks generated by
the SBM, provided that the average degree increases as the number of nodes
increases [46, 47, 48, 21, 49, 50]. However, most networks of interest in
applications are sparse [51, 1], in that their average degree is usually much
smaller than the network size. The task of community detection is particularly
hard on very sparse networks. For instance, the performance of many spectral
methods significantly worsens as the graph gets sparser [52, 53], which has
led to the development of remedies such as non-backtracking walks [52, 54, 53]
and consensus clustering [55]. However, it remains unclear how neural graph
embeddings perform on sparse networks, how much edge sparsity hampers their
ability to detect communities, and how they fare for traditional clustering
techniques, especially spectral methods.

Here, we prove that graph embedding methods based on a shallow neural network
without non-linear activation—such as DeepWalk [38], LINE [39], and node2vec
[34]—can detect communities all the way down to the information-theoretical
limit on graphs generated by the SBM [56]. Our results imply that two common
components of deep learning—multiple “deep” layers and non-linear
activation—are not necessary to achieve the optimal limit of community
detectability. Numerical experiments reveal that they have a remarkable
performance also in the limit of sparse networks, getting close to the
theoretically optimal performance curve of the belief propagation (BP) method
[56] for networks generated by the SBM. In particular, node2vec [34] learns
the community structure in more realistic networks with heterogeneous
distributions of degree and community size substantially better than spectral
embeddings, BP, and traditional clustering techniques. The excellent
performance of node2vec is consistent across different levels of edge
sparsity, community sizes, and degree heterogeneity. Our results might inform
powerful community detection algorithms and improve our theoretical
understanding of clustering via neural embeddings. We have made available the
code to reproduce all the results at [57].

##  2 Results

###  2.1 Detectability limit of communities

We first consider the standard setting studied in papers concerning community
detectability [53, 52, 58]. We focus on undirected and unweighted networks
with community structure generated according to the planted partition model
(PPM) [59], a special case of the SBM where nodes are divided into $q$ equal-
sized communities, and two nodes are connected with probability
$p_{\text{in}}$ if they are in the same community and with probability
$p_{\text{out}}$ if they are in different communities. We assume that the
networks are sparse, i.e., $p_{\text{in}}$ and $p_{\text{out}}$ are inversely
proportional to the number $n$ of nodes. Therefore, the average degree
$\langle k\rangle$ and the ratio of edge probabilities
$p_{\text{in}}/p_{\text{out}}$ do not depend on $n$. We specify the edge
probabilities via the mixing parameter $\mu=np_{\text{out}}/\langle k\rangle$.
The mixing parameter indicates how blended communities are with each other. As
$\mu\rightarrow 0$, communities are well separated and easily detectable. For
larger values of $\mu$, community detection becomes harder. For $\mu=1$, which
corresponds to $p_{\text{in}}=p_{\text{out}}$, the network is an Erdős-Rényi
random graph and, as such, has no community structure. We note that the mixing
parameter $\mu$ is slightly different from the traditional mixing parameter
$\mu_{\text{LFR}}$ used in the Lancichinetti-Fortunato-Radicchi (LFR)
benchmark, which is defined as
$\mu_{\text{LFR}}=(1-\frac{1}{q})np_{\text{out}}/\langle k\rangle$. The
difference between $\mu$ and $\mu_{\text{LFR}}$ is negligible for large $q$.

Communities are present for all $\mu$-values in the range $[0,1)$, because the
edges are more densely distributed within communities than between them. For a
given algorithm, communities are detectable if the partition found by the
algorithm has greater similarity with the planted partition than the trivial
division in which node labels are randomly shuffled. However, it is shown that
there is a regime $\mu^{*}\leq\mu<1$, in which communities are not detectable
by any algorithm [58, 56]. This is because, due to fluctuations in the numbers
of neighbors within and between the groups, the true communities are
effectively indistinguishable from random subgraphs with the same size, with
respect to the imbalance between the internal and the external degree of the
nodes. The threshold $\mu^{*}$ marks the information-theoretical detectability
limit of communities in graphs generated by the PPM.

###  2.2 Detectability limit of node2vec

We determine the maximum mixing parameter $\mu^{*}_{A}$ below which
communities are detectable by an algorithm, which we refer to as the
algorithmic detectability limit. We first give a high-level description of our
derivation of the algorithmic detectability limit for node2vec. We note that
our derivation can be directly applied to other neural graph embeddings such
as DeepWalk [38] and LINE [39]. See the Methods section for the step-by-step
derivations.

Our analysis is based on the fact that node2vec generates its embedding by
effectively factorizing a matrix when the number of dimensions is sufficiently
large [30]. This insight enables us to study node2vec as a spectral method
(see Methods). Spectral algorithms identify communities by computing the
eigenvectors associated with the largest or smallest eigenvalues of a
reference operator such as the combinatorial and normalized Laplacian
matrices. Each eigenvector corresponds to a community in a network, with the
entries having similar values for the nodes in that community. Therefore, when
using eigenvectors to represent the network in vector space, nodes in the same
community are projected onto points in space lying close to each other so that
a data clustering algorithm can separate them [17].

The existence of such localized eigenvectors can be inferred by analyzing the
spectrum of the reference operator using random matrix theory. For instance,
this approach has been applied to determine the detectability limit of the
normalized Laplacian matrix generated by the PPM [60]. We find that, under
some mild conditions, the spectrum of the node2vec matrix is equivalent to
that of the normalized Laplacian matrix. Hence, the detectability limit of
node2vec matches that of the spectral embedding with the normalized Laplacian
matrix [60]:

$\mu^{*}_{\text{n2v}}=\mu^{*}=1-\frac{1}{\sqrt{\langle k\rangle}}.$ (1)

See Supporting Information Section 2 for the expression of the detectability
limit in terms of the mixing parameter $\mu$. This threshold exactly
corresponds to the information-theoretical detectability limit $\mu^{*}$ of
the PPM [58, 55]. In other words, node2vec has the ability to detect
communities down to the information-theoretic limit in principle. However,
like in the case of spectral modularity maximization [58], our analysis is
only valid when the average degree is sufficiently large. Nevertheless, as we
shall see, our numerical simulations show that node2vec performs well even if
the average degree is small.

###  2.3 Experiment setup

As baselines, we use two spectral embedding methods whose detectability limit
matches the information-theoretical one: spectral modularity maximization [58]
and Laplacian EigenMap [61]. In addition, we use two other neural embeddings,
DeepWalk [38] and LINE [39]. DeepWalk and LINE share the same architecture as
node2vec but are trained with different objective functions [30, 62].
Furthermore, we employ the spectral algorithm based on the leading
eigenvectors of the non-backtracking matrix, which reaches the information-
theoretical limit even in the sparse case for networks generated by the PPM
[52]. For all embedding methods, we set the number of dimensions, $C$, to
$64$. Finally, we employ three community detection algorithms: Infomap [63],
statistical inference of the microscopic degree-corrected SBM [44], and the BP
algorithm [56]. Note that we set the initial parameters of the BP algorithm
based on the ground-truth communities to yield the maximal performance. See
Supporting Information Section 4 for the parameter choices of the models and
the implementations we used.

Community detection via graph embedding is a two-step process:

  * •

First, the network is embedded, which yields a projection of nodes onto points
in a vector space.

  * •

Second, the points are divided into groups using a data clustering method
(e.g., $K$-means clustering).

Thus, the performance of community detection depends on both the quality of
the embedding and the performance of the subsequent data clustering procedure.
Since we focus on the ability of neural embedding methods to generate
representations where clusters are detectable, we want to control the second
step by using an ideal clustering method that can optimally find the clusters
for a given representation. To do so, we use a $K$-means algorithm with fixed
centroids (i.e., Voronoi clustering), whose positions are determined by the
locations of the true communities in the embedding space, and clustering is
performed by assigning each point/node to the centroid/cluster with the
highest cosine similarity. See Supporting Information Section 6 for the
results for the ordinal $K$-means algorithm. By using this algorithm, we can
focus on the question of whether an embedding method can successfully encode
community structure or not.

We assess the performance by comparing the similarity between the planted
partition of the network and the detected partition of the algorithm. We used
the element-centric similarity [64], denoted by $S$, with an adjustment such
that a random shuffling of the community memberships for the two partitions
yields $S=0$ on expectation (See Supporting Information Section 1). This way,
for planted divisions into equal-sized communities, $S=0$ represents the
baseline performance of the trivial algorithm, while $S>0$ indicates that
communities are detectable by the given algorithm.

###  2.4 Simulations: Planted Partition Model

Figure 1:  Performance of community detection methods for networks generated
by the PPM as a function of the mixing parameter $\mu$. We generated networks
with $n=10^{5}$ nodes, different edge sparsity ($\langle k\rangle=5$ in A and
D, $\langle k\rangle=10$ in B and E, $\langle k\rangle=50$ in C and F), and
the different number of communities ($q=2$ for A–C and $q=50$ for D–F). The
dashed vertical line indicates the theoretical detectability limit $\mu^{*}$
given by (1): communities are detectable (i.e., $S>0$), in principle, below
$\mu^{*}$. Spectral embedding methods detect communities up to the theoretical
limit for dense networks (C and F), supporting the algorithmic limit derived
by previous studies [58, 60]. However, for sparse networks, they fall short
even at low $\mu$-values (A and D). node2vec outperforms spectral methods,
with the performance curve close to that of the BP algorithm, which is
supposed to be optimal. Note that even the BP algorithm falls short of the
exact recovery of some easily-detectable communities in the case of $q=50$
communities, even with the initial parameters set according to the ground-
truth communities.

We test the graph embedding and community detection algorithms on networks of
$n=100,000$ nodes generated by the PPM, with $q\in\\{2,50\\}$ communities of
equal size and average degree $\langle k\rangle\in\\{5,10,50\\}$ (Fig. 1).
Spectral methods find communities better than random guessing below the
detectability limit $\mu^{*}$, i.e. $S>0$, for $\mu<\mu^{*}$ and $\langle
k\rangle=50$ (Figs. 1C and F). However, their performance is much worse when
the average degree is small ($\langle k\rangle=5$, Figs. 1A and D). For
example, Laplacian EigenMap falls short below the detectability limit
($\mu<\mu^{*}$), despite having the optimal detectability limit when the
average degree is sufficiently large [65]. All techniques, including BP, which
is supposed to be optimal for sparse networks, fail the exact recovery of the
clusters for sparse networks even if the value of $\mu$ is low ($\langle
k\rangle=5$, Figs. 1A and D). We find that misclassifications are inevitable
for these highly sparse networks because some nodes end up being connected
with other communities more densely than with their own community by random
chance. The BP algorithm also fails for the networks with $q=50$ communities,
even for small $\mu$ values. This may be because BP employs a greedy
optimization strategy that may converge to a suboptimal solution near the
starting point. Notably, the poor performance of the BP algorithm is mainly
observed in the networks with 50 communities ($q=50$), where the prevalence of
many local minima may exacerbate the limitations of the greedy optimization.

On the other hand, node2vec is substantially better than the spectral methods,
and its performance is the closest to that of the BP algorithm for sparse
networks (Figs. 1A and D). node2vec consistently achieves a good performance
across different numbers of communities and different network sparsity.
Furthermore, node2vec performs well even if we reduce the embedding dimension
$C$ from $64$ to $16$, which is smaller than the number of communities in the
cases where $q=50$ (Supporting Information Section 5).

###  2.5 Simulations: LFR benchmark

Figure 2:  Performance of community detection methods on the LFR benchmark
networks, as a function of the mixing parameter $\mu$. We generated networks
with $n=10^{4}$ nodes with different edge sparsity ($\langle k\rangle=5$ in A
and D, $\langle k\rangle=10$ in B and E, $\langle k\rangle=50$ in C and F).
The degree exponent $\tau_{1}=2.1$ in A, B, and C, and $\tau_{1}=3$ in D, E,
and F. node2vec consistently performs well across different sparsity regimes
for most $\mu$-values, with a larger margin for sparser networks. The BP
algorithm, which is provably optimal for networks generated by the PPM, fails
to identify some easily-detectable communities, even with the initial
parameters set according to the ground-truth communities.

The PPM is a stylized model that lacks key characteristics of empirical
community structure. We test the graph embedding using more realistic networks
generated by the LFR model [66], which produces networks with heterogeneous
degree and community size distributions, to assess the performance of the
methods in a more practical context. Unlike the PPM, however, the theoretical
detectability limit of communities in LFR networks is not known. We build the
LFR networks by using the following parameter values: number of nodes
$n=10,000$, degree exponent $\tau_{1}\in\\{2.1,3\\}$, average degree $\langle
k\rangle\in\\{5,10,50\\}$, maximum degree $\sqrt{10n}$, community-size
exponent $\tau_{2}=1$, community size range $[50,\sqrt{10n}]$.

In LFR networks, the BP algorithm and the non-backtracking embedding—which
have an excellent performance on the PPM networks, at least in
theory—underperform noticeably, suggesting that optimal methods for the
standard PPM may not perform well in practice. On the other hand, node2vec
consistently has the best performance, with a larger margin in sparser
networks (Fig. 2). The performance of node2vec is also consistent across
networks with different levels of degree heterogeneity. Even with the smaller
embedding dimension $C=16$, node2vec performs comparably well with Infomap,
which is known to be very accurate on LFR networks [67] (Supporting
Information Section 5).

##  3 Discussion

We investigated the ability of neural graph embeddings to encode communities
by focusing on shallow linear graph neural networks—node2vec, DeepWalk, and
LINE—and comparing them with traditional spectral approaches. We proved that,
for not too sparse networks created by the PPM, node2vec is an optimal method
to encode their community structure in that the algorithmic detectability
limit coincides with the information-theoretic limit. In particular, our
experiments on the PPM and LFR benchmarks show that node2vec consistently
excels on sparse networks with small and moderate average degree, with
homogeneous and heterogeneous degrees and community sizes in the detectable
regime, demonstrating its high robustness and potential in the analysis of
empirical networks.

Our results provide an alternative perspective to the common design principles
of neural networks widely accepted for text and image processing. In these
applications, deep neural structures and non-linear activation are considered
indispensable in order to achieve high performance. The neural network
architecture is also critical for graph neural networks for community
detection task [68]. Our findings further demonstrate that a simple neural
network with only one hidden layer and no non-linear activation can achieve
the information-theoretical detectability limit of communities with
performance close to or superior than the best methods for community
detection.

DeepWalk [38] and LINE [39] are also optimal in terms of the detectability
limit of communities (Supplementary Information Section 2). However, node2vec
surpasses both DeepWalk and LINE in numerical tests, owing to two key
features. First, node2vec learns degree-agnostic embeddings, which are highly
robust against degree heterogeneity [62]. By contrast, DeepWalk tends to learn
node degree as the primary dimension in the embedding space [62].
Consequently, degree heterogeneity introduces considerable noise to the
community structure in the DeepWalk embedding. Second, LINE is a specific
instance of node2vec with window size $T=1$ [30], and thus learns the dyadic
relationships between nodes. As is the case for node2vec, LINE is resilient to
degree heterogeneity, and performed closely to node2vec for some networks in
our simulations. However, it did not perform as well as node2vec, and this
discrepancy may be attributed to LINE’s emphasis on learning stochastic and
noisy dyadic relationships, as opposed to the indirect relationships that
node2vec captures.

Our results come with caveats. First, we focused on the best achievable
clustering performance—by using Voronoi clustering with the centroids of the
planted communities—because we wanted to control any factors coming from the
data clustering step so that we could focus on the representation learning.
However, we also fine-tuned other community detection methods—the SBM and the
BP algorithm—using the information on the planted partition, such as the
number of communities, their sizes, and edge probabilities. Thus, caution
should be taken when interpreting the results: our analysis reports an upper
bound on the performance, and the actual performance in practice will depend
on the choice and configuration of the data clustering method. Indeed, a
previous study [22] using the $K$-means algorithm demonstrated that node2vec
did not perform as well as standard community detection methods even if its
hyperparameters are fine-tuned. By contrast, we did not fine-tune the
parameters of our embedding methods. Hence, we believe that the previous
results [22] are primarily due to the limitations of the $K$-means clustering
algorithm (when the initial position of the centroids is arbitrarily chosen),
rather than to the embedding.

Second, in our analytical derivations, we assumed that the average degree is
sufficiently large, as is the case for the corresponding analysis of spectral
modularity maximization [58]. Thus, the optimality may not hold if networks
are substantially sparse. However, our simulations suggested that node2vec is
resilient to network sparsity compared with traditional spectral embedding
methods. Understanding the factor inducing such resilience will be interesting
for future work.

Third, while we restricted ourselves to the community detection task, graph
embeddings have been used for other tasks, including link prediction, node
classification, and anomaly detection. Investigating the theoretical
foundation behind the performance of neural embeddings in other tasks is a
promising research direction.

Even with these caveats, we believe that our study will provide the foundation
for future studies that uncover the inner workings of neural embedding methods
and bridge the study of artificial neural networks to network science.

##  4 Methods

###  4.1 node2vec as spectral embedding

node2vec learns the structure of a given network based on random walks. A
random walk traverses a given network by following randomly chosen edges and
generates the sequence of nodes $x^{(1)},x^{(2)},\ldots$. The sequence is then
fed into skip-gram word2vec [69], which learns how likely it is that a node
$j$ appears in the surrounding of another node $i$ up to a certain time lag
$T$ (i.e., window length) through the conditional probability

$\displaystyle P(x^{(t+\tau)}=j\mid x^{(t)}=i,1\leq|\tau|\leq
T)=\frac{1}{Z}\exp({\bm{u}}_{i}^{\top}{\bm{v}}_{j}),$

where ${\bm{u}}_{i}\in\mathbb{R}^{C\times 1}$,
${\bm{v}}_{j}\in\mathbb{R}^{C\times 1}$, and $Z$ is a normalization constant.
Each node $i$ is associated to two vectors: vector ${\bm{u}}_{i}$ represents
the embedding of node $i$; ${\bm{v}}_{i}$ represents node $i$ as a context of
other nodes. Because the normalization constant is computationally expensive,
node2vec uses a heuristic training algorithm, i.e., negative sampling [69].
When trained with negative sampling, skip-gram word2vec is equivalent to a
spectral embedding that factorizes matrix $\mathbf{R}^{\text{n2v}}$ with
elements [70, 30]:

$\displaystyle
R^{\text{n2v}}_{ij}=\log\frac{1}{T}\sum_{\tau=1}^{T}\left[\frac{P(x^{(t+\tau)}=j\mid
x^{(t)}=i)}{P(x^{(t)}=j)}\right],$ (2)

in the limit of $C\rightarrow n$ with $T$ greater than or equal to the network
diameter, where $P(x^{(t)}=i)$ is the probability that the $t^{\text{th}}$
node in the given sequence is node $i$ (see Supporting Information Section 3
for the step-by-step derivation). This interpretation of node2vec as a
spectral embedding allows us to derive the algorithmic detectability limit
from the spectrum of $\mathbf{R}^{\text{n2v}}$.

Deriving the spectrum of $\mathbf{R}^{\text{n2v}}$ in a closed form is
challenging because $\mathbf{R}^{\text{n2v}}$ involves element-wise
logarithms. We approximate the element-wise logarithm by a linear function by
assuming that the window length $T$ is sufficiently large. To demonstrate our
argument, let us describe $R_{ij}^{\text{n2v}}$ in the language of random
walks. Given that the network is undirected and unweighted, the probability
$P(x^{(t)}=j)$ corresponds to the long-term probability of finding the random
walker at node $j$. The probability $P(x^{(t+\tau)}=j\mid x^{(t)}=i)$ refers
to the transition of a walker from node $i$ to node $j$ after $\tau$ steps. In
the limit $\tau\rightarrow\infty$, the walker reaches the stationary state,
and $P(x^{(t+\tau)}=j\mid x^{(t)}=i)$ approaches $P(x^{(t)}=j)$. Thus, in the
regime of a sufficiently large $T$, we take the Taylor expansion of
$R^{\text{n2v}}_{ij}=\log\left(1+\epsilon_{ij}\right)$ around
$\epsilon_{ij}=\sum_{\tau=1}^{T}P(x^{(t+\tau)}=j\mid
x^{(t)}=i)/[TP(x^{(t)}=j)]-1$ and obtain

$\displaystyle R^{\text{n2v}}_{ij}\simeq\hat{R}^{\text{n2v}}_{ij}$
$\displaystyle:=\frac{1}{T}\sum_{\tau=1}^{T}\left[\frac{P(x^{(t+\tau)}=j\mid
x^{(t)}=i)}{P(x^{(t)}=j)}\right]-1.$ (3)

In matrix form,

$\displaystyle\mathbf{\hat{R}}^{\text{n2v}}$
$\displaystyle=\frac{2m}{T}\left[\sum_{\tau=1}^{T}\left(\mathbf{D}^{-1}\mathbf{A}\right)^{\tau}\right]\mathbf{D}^{-1}-\mathbf{1}_{n\times
n},$ (4)

where $\mathbf{A}$ is the adjacency matrix, $\mathbf{D}$ is a diagonal matrix
whose diagonal element $D_{ii}$ is the degree $k_{i}$ of node $i$, $m$ is the
number of edges in the network, and $\mathbf{1}_{n\times n}$ is the $n\times
n$ all-one matrix. We used $P(x^{(t)}=j)=k_{j}/2m$ and
$\left(\mathbf{D}^{-1}\mathbf{A}\right)^{\tau}_{ij}=P(x^{(t+\tau)}=j\mid
x^{(t)}=i)$, derived from the fact that $P(x^{(t)}=j)$ is proportional to
degree in undirected networks; $\mathbf{D}^{-1}\mathbf{A}$ is the transition
matrix, whose $\tau$th power represents the random walk transition probability
after $\tau$ steps.

The node2vec matrix $\mathbf{\hat{R}}^{\text{n2v}}$ has a connection to the
normalized Laplacian matrix, ${\mathbf{L}}$, which is tightly related to the
characteristics of random walks and network communities [71]. The normalized
Laplacian matrix is defined by
${\mathbf{L}}:=\mathbf{I}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$.
By using an alternative expression of the transition probability, i.e.,
$(\mathbf{D}^{-1}\mathbf{A})^{\tau}=\mathbf{D}^{-\frac{1}{2}}(\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}})^{\tau}\mathbf{D}^{\frac{1}{2}}$,
we rewrite $\mathbf{\hat{R}}^{\text{n2v}}$ as

$\displaystyle\mathbf{\hat{R}}^{\text{n2v}}$
$\displaystyle=\frac{2m}{T}\left[\sum_{\tau=1}^{T}\mathbf{D}^{-\frac{1}{2}}\left(\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\right)^{\tau}\mathbf{D}^{-\frac{1}{2}}\right]-\mathbf{1}_{n\times
n}$
$\displaystyle=2m\mathbf{D}^{-\frac{1}{2}}\left[\frac{1}{T}\sum_{\tau=1}^{T}\left(\mathbf{I}-{\mathbf{L}}\right)^{\tau}-\frac{\mathbf{D}^{\frac{1}{2}}{\bm{1}}_{n}}{\sqrt{2m}}\frac{\mathbf{1}_{n}^{\top}\mathbf{D}^{\frac{1}{2}}}{\sqrt{2m}}\right]\mathbf{D}^{-\frac{1}{2}},$
(5)

where $\mathbf{1}_{n}$ is a column vector of length $n$. We note that vector
$\mathbf{D}^{1/2}\mathbf{1}_{n}/\sqrt{2m}$ is a trivial eigenvector of
${\mathbf{L}}$ associated with the null eigenvalue, $\lambda_{1}=0$.
Furthermore, $\left(\mathbf{I}-{\mathbf{L}}\right)^{\tau}$ changes the
eigenvalues while keeping the eigenvectors intact. This means that
$\mathbf{\hat{R}}^{\text{n2v}}$ can be specified by using the spectrum of
${\mathbf{L}}$, i.e.,

$\displaystyle\mathbf{\hat{R}}^{\text{n2v}}$
$\displaystyle=\mathbf{D}^{-\frac{1}{2}}\mathbf{\Gamma}\begin{bmatrix}\phi(\lambda_{1})&&0\\\
&\ddots&\\\ 0&&\phi(\lambda_{n})\\\
\end{bmatrix}\mathbf{\Gamma}^{\top}\mathbf{D}^{-\frac{1}{2}},$ (6)

where $\mathbf{\Gamma}\in{\mathbb{R}}^{n\times n}$ is the matrix of the
eigenvectors of ${\mathbf{L}}$, and $\phi$ is a graph kernel [18] that
transforms the eigenvalues $\lambda_{i}$ ($i=1,2,\ldots,n$) of ${\mathbf{L}}$
by

$\displaystyle\phi(\lambda_{i})=\left\\{\begin{array}[]{ll}\dfrac{2m(1-\lambda_{i})\left[1-(1-\lambda_{i})^{T}\right]}{T\lambda_{i}}&(\lambda_{i}\neq
0),\\\ 0&(\lambda_{i}=0),\end{array}\right.$ (9)

or equivalently
$\phi(\lambda_{i})=\frac{2m}{T}\sum_{\tau=1}^{T}(1-\lambda_{i})^{\tau}$ if
$\lambda_{i}\neq 0$ (Fig. 3). Equation (6) tells us that the eigenvectors
$\mathbf{U}$ of $\mathbf{\hat{R}}^{\text{n2v}}$ are equivalent to the
eigenvectors $\mathbf{\Gamma}$ of the normalized Laplacian matrix, up to a
linear transformation given by

$\displaystyle\mathbf{U}:=\mathbf{D}^{\frac{1}{2}}\mathbf{\Gamma}.$ (10)

Figure 3: Graph kernel $\phi(\lambda_{i};T)$ of node2vec matrix
$\mathbf{\hat{R}}^{\text{n2v}}$ across different $T$ values. The function
$\phi(\lambda_{i})$ is non-negative and monotonically decreasing for
$0<\lambda_{i}\leq 1$ and $\phi(\lambda_{i})\leq 0$ for $1<\lambda_{i}\leq 2$.

Building on the correspondence between the normalized Laplacian ${\mathbf{L}}$
and the node2vec matrix $\mathbf{\hat{R}}^{\text{n2v}}$, we derive the
algorithmic community detectability limit of node2vec. Following [58, 65, 60],
we assume that the network consists of two communities generated by the PPM.
Then, the non-trivial eigenvector of ${\mathbf{L}}$ encodes the communities
and has the optimal detectability limit of communities, provided that the
average degree is large ((1)) [58, 65, 60]. This non-trivial eigenvector of
$\mathbf{L}$ corresponds to the principal eigenvector of
$\mathbf{\hat{R}}^{\text{n2v}}$. Specifically, the non-trivial eigenvector of
$\mathbf{L}$ is associated with the smallest non-zero eigenvalue
$\lambda_{2}$, which is $\lambda_{2}<1$ when each community is densely
connected within itself and sparsely with other communities [17]. The
eigenvalues are mirrored in the eigenvalues $\phi(\lambda_{i})$ of
$\mathbf{\hat{R}}^{\text{n2v}}$, and $\lambda_{2}$—the smallest non-zero
eigenvalue—yields the maximum $\phi$-value (Fig. 3)

This correspondence of non-trivial eigenvectors between
$\mathbf{\hat{R}}^{\text{n2v}}$ and ${\mathbf{L}}$ suggests that communities
detectable by ${\mathbf{L}}$ are also detectable by
$\mathbf{\hat{R}}^{\text{n2v}}$ and vice versa. Thus, spectral embedding with
$\mathbf{\hat{R}}^{\text{n2v}}$ has the same information-theoretic
detectability limit as spectral methods relying on eigenvectors of
${\mathbf{L}}$, for networks with sufficiently high degree.

###  4.2 Detectability limit of DeepWalk

We expand our argument to include DeepWalk [38]. Similar to node2vec, DeepWalk
also trains word2vec but with a different objective function. Furthermore,
DeepWalk is equivalent to a matrix factorization if the embedding dimension is
sufficiently large and the window size $T$ is greater than the network’s
diameter [30, 62]. More specifically, DeepWalk generates an embedding by
factorizing a matrix with entries [62]:

$\displaystyle R^{\text{DW}}_{ij}$
$\displaystyle:=\log\left(\frac{1}{T}\sum_{\tau=1}^{T}\frac{P(x^{(t)}=i,x^{(t+\tau)}=j)}{P(x^{(t)}=i)\cdot\frac{1}{n}}\right),$
(11)

in the limit of $C\rightarrow n$ with $T$ being greater than the network
diameter. When the random walker is in the stationary state at time $t$ and
makes sufficiently many steps $(\tau\gg 1)$, we have

$\displaystyle\lim_{\tau\rightarrow\infty}P(x^{(t)}=i,x^{(t+\tau)}=j)$
$\displaystyle=P(x^{(t)}=i)P(x^{(t)}=j)$
$\displaystyle=P(x^{(t)}=i)\cdot\frac{k_{j}}{n\langle k\rangle}$ (12)

In particular, if the degree distribution is Poisson and the average degree is
sufficiently large,

$\displaystyle\frac{k_{j}}{n\langle k\rangle}\simeq\frac{1}{n},$ (13)

which is true for the PPM. By substituting (13) into (12), we obtain

$\displaystyle P(x^{(t)}=i,x^{(t+\tau)}=j)\simeq
P(x^{(t)}=i)\cdot\frac{1}{n}\quad\text{ for }\tau\gg 1.$ (14)

Armed with this result, let us derive the detectability limit of DeepWalk.
Assuming that the window length $T$ is large, we take the Taylor expansion of
(11) around
$\epsilon_{ij}^{\prime}=\sum_{\tau=1}^{T}P(x^{(t)}=i,x^{(t+\tau)}=j)/[T(P(x^{(t)}=i)\cdot
1/n)]-1$ and obtain

$\displaystyle R^{\text{DW}}_{ij}\simeq{\hat{R}}^{\text{DW}}_{ij}$
$\displaystyle:=\left(\frac{1}{T}\sum_{\tau=1}^{T}\frac{P(x^{(t)}=i,x^{(t+\tau)}=j)}{P(x^{(t)}=i)\cdot\frac{1}{n}}\right)-1.$
(15)

In matrix form,

$\displaystyle\mathbf{\hat{R}}^{\text{DW}}:=\frac{n}{T}\left[\sum_{\tau=1}^{T}\left(\mathbf{D}^{-1}\mathbf{A}\right)^{\tau}\right]-\mathbf{1}_{n\times
n}.$ (16)

Note that $\mathbf{\hat{R}}^{\text{DW}}$ is similar to the node2vec matrix
$\mathbf{\hat{R}}^{\text{n2v}}$ ((4)). The right/left eigenvectors of
$\mathbf{\hat{R}}^{\text{DW}}$ are obtained from those of the normalized
Laplacian by simple multiplications by the operators $\mathbf{D}^{1/2}$ and
$\mathbf{D}^{-1/2}$, respectively. Therefore, DeepWalk has the information-
theoretical detectability limit as well.

###  4.3 Detectability limit of LINE

LINE [39] is a special version of node2vec with the window length being $T=1$.
The corresponding matrix factorized by LINE is given by [30]:

$\displaystyle R^{\text{LINE}}_{ij}$
$\displaystyle:=\log\left(\frac{A_{ij}}{k_{i}k_{j}}+a_{0}\right)+\log 2m.$
(17)

For LINE, although Ref. [30] shows
$\log\left(\frac{A_{ij}}{k_{i}k_{j}}\right)+\log 2m$, we introduce a small
positive value $a_{0}$ $(a_{0}>0)$ to prevent the matrix elements from being
infinite for $A_{ij}=0$. To obtain the spectrum of $\mathbf{R}^{\text{LINE}}$,
we exploit the Taylor expansion $\log(x+a_{0})\simeq\frac{x}{a_{0}}+\log
a_{0}$ around $x=0$, where $a_{0}>0$. Specifically, assuming that the average
degree is sufficiently large, we obtain

$\displaystyle\hat{R}^{\text{LINE}}_{ij}$
$\displaystyle=\frac{A_{ij}}{a_{0}k_{i}k_{j}}+\log a_{0}+\log 2m,$ (18)

or equivalently in matrix form

$\displaystyle\mathbf{\hat{R}}^{\text{LINE}}$
$\displaystyle=\frac{1}{a_{0}}\mathbf{D}^{-1}\mathbf{A}\mathbf{D}^{-1}+a_{1}\mathbf{1}_{n\times
n}$
$\displaystyle=\frac{1}{a_{0}}\mathbf{D}^{-1/2}(\mathbf{I}-\mathbf{L})\mathbf{D}^{-1/2}+a_{1}\mathbf{1}_{n\times
n}$
$\displaystyle=\frac{1}{a_{0}}\mathbf{D}^{-1/2}\left(\mathbf{I}-\mathbf{L}+2a_{0}a_{1}m\frac{\mathbf{D}^{\frac{1}{2}}\mathbf{1}_{n}}{\sqrt{2m}}\frac{\mathbf{1}_{n}^{\top}\mathbf{D}^{\frac{1}{2}}}{\sqrt{2m}}\right)\mathbf{D}^{-1/2}.$
(19)

where $a_{1}:=\log a_{0}+\log(2m)$. Equation (19) is reminiscent of (5) for
node2vec. Comparing Eqs. (19) and (5), it immediately follows that they share
the same eigenvectors, and thus node2vec and LINE have the same detectability
threshold.

### Acknowledgement

This project was partially supported by the Army Research Office under
contract number W911NF-21-1-0194, by the Air Force Office of Scientific
Research under award numbers FA9550-19-1-0391 and FA9550-21-1-0446, and by the
National Science Foundation under award numbers 1927418, and by the National
Institutes of Health under awards U01 AG072177 and U19 AG074879.

### Contributions

All authors conceived the research, discussed, and wrote the manuscript. S.K.
and F.R. performed the analysis and experiments.

### Competing interest

The authors have no competing interest.

### Data sharing plans

We made available the code and documentations to reproduce all results. See
[57] for details.

## References

  * [1] Albert-László Barabási and Márton Pósfai.  Network Science.  Cambridge University Press, Cambridge, United Kingdom, 1st edition edition, 2016.
  * [2] Filippo Menczer, Santo Fortunato, and Clayton A. Davis.  A First Course in Network Science.  Cambridge University Press, Cambridge, 1st edition edition, 2020.
  * [3] Mark Newman.  Networks.  Oxford University Press, Oxford, United Kingdom ; New York, NY, United States of America, 2nd edition edition, 2018.
  * [4] Alan Mislove, Sune Lehmann, Yong-Yeol Ahn, Jukka-Pekka Onnela, and J. Rosenquist.  Understanding the Demographics of Twitter Users.  Proceedings of the International AAAI Conference on Web and Social Media, 5(1):554–557, 2011.
  * [5] Sadamori Kojaku, Laurent Hébert-Dufresne, Enys Mones, Sune Lehmann, and Yong-Yeol Ahn.  The effectiveness of backward contact tracing in networks.  Nature Physics, 17(5):652–658, 2021.
  * [6] Marc Barthélemy.  Spatial networks.  Physics Reports, 499(1):1–101, 2011.
  * [7] Vittoria Colizza, Alain Barrat, Marc Barthélemy, and Alessandro Vespignani.  The role of the airline transportation network in the prediction and predictability of global epidemics.  Proceedings of the National Academy of Sciences, 103(7):2015–2020, 2006.
  * [8] Marco Bardoscia, Paolo Barucca, Stefano Battiston, Fabio Caccioli, Giulio Cimini, Diego Garlaschelli, Fabio Saracco, Tiziano Squartini, and Guido Caldarelli.  The physics of financial networks.  Nature Reviews Physics, 3(7):490–507, 2021.
  * [9] Paolo Barucca, Marco Bardoscia, Fabio Caccioli, Marco D’Errico, Gabriele Visentin, Guido Caldarelli, and Stefano Battiston.  Network valuation in financial systems.  Mathematical Finance, 30(4):1181–1204, 2020.
  * [10] M. E. J. Newman.  The structure of scientific collaboration networks.  Proceedings of the National Academy of Sciences, 98(2):404–409, 2001.
  * [11] Aaron Clauset, Samuel Arbesman, and Daniel B. Larremore.  Systematic inequality and hierarchy in faculty hiring networks.  Science Advances, 1(1):e1400005, 2015.
  * [12] Danielle S. Bassett and Olaf Sporns.  Network neuroscience.  Nature Neuroscience, 20(3):353–364, 2017.
  * [13] Danielle Smith Bassett and ED Bullmore.  Small-world brain networks.  The neuroscientist, 12(6):512–523, 2006.
  * [14] Junil Kim, Sang-Min Park, and Kwang-Hyun Cho.  Discovery of a kernel for controlling biomolecular regulatory networks.  Scientific Reports, 3, 2013.
  * [15] Regina Samaga and Steffen Klamt.  Modeling approaches for qualitative and semi-quantitative analysis of cellular signaling networks.  Cell Communication and Signaling : CCS, 11:43 – 43, 2013.
  * [16] Jordan C. Rozum, Jorge Gómez Tejeda Zañudo, Xiao Gan, Dávid Deritei, and Réka Albert.  Parity and time reversal elucidate both decision-making in empirical models and attractor scaling in critical boolean networks.  Science Advances, 7, 2020.
  * [17] Ulrike von Luxburg.  A tutorial on spectral clustering.  Statistics and Computing, 17(4):395–416, 2007.
  * [18] Jérôme Kunegis and Andreas Lommatzsch.  Learning spectral graph transformations for link prediction.  In Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, pages 561–568, New York, NY, USA, 2009\. Association for Computing Machinery.
  * [19] Maximillian Nickel and Douwe Kiela.  Poincaré Embeddings for Learning Hierarchical Representations.  In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [20] Hao Peng, Qing Ke, Ceren Budak, Daniel M. Romero, and Yong-Yeol Ahn.  Neural embeddings of scholarly periodicals reveal complex disciplinary organizations.  Science Advances, 7(17):eabb9004, 2021.
  * [21] Aman Barot, Shankar Bhamidi, and Souvik Dhara.  Community detection using low-dimensional network embedding algorithms.  (arXiv:2111.05267), 2021.
  * [22] Aditya Tandon, Aiiad Albeshri, Vijey Thayananthan, Wadee Alhalabi, Filippo Radicchi, and Santo Fortunato.  Community detection in networks using graph embeddings.  Physical Review E, 103(2):022316, 2021.
  * [23] Hongxu Chen, Hongzhi Yin, Weiqing Wang, Hao Wang, Quoc Viet Hung Nguyen, and Xue Li.  PME: Projected Metric Embedding on Heterogeneous Networks for Link Prediction.  In Proceedings of the 24th ACM SIGKDD International Conference on KDD, KDD ’18, pages 1177–1186, New York, NY, USA, 2018\. Association for Computing Machinery.
  * [24] Farzan Masrour, Tyler Wilson, Heng Yan, Pang-Ning Tan, and Abdol Esfahanian.  Bursting the Filter Bubble: Fairness-Aware Network Link Prediction.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(01):841–848, 2020.
  * [25] Haewoon Kwak, Jisun An, Elise Jing, and Yong-Yeol Ahn.  FrameAxis: Characterizing microframe bias and intensity with word embedding.  PeerJ Computer Science, 7:e644, 2021.
  * [26] Dakota Murray, Jisung Yoon, Sadamori Kojaku, Rodrigo Costas, Woo-Sung Jung, Staša Milojević, and Yong-Yeol Ahn.  Unsupervised embedding of trajectories captures the latent structure of mobility.  (arXiv:2012.02785), 2021.
  * [27] Jamshid Sourati and James Evans.  Accelerating science with human versus alien artificial intelligences.  (arXiv:2104.05188), 2021.
  * [28] Vahe Tshitoyan, John Dagdelen, Leigh Weston, Alexander Dunn, Ziqin Rong, Olga Kononova, Kristin A. Persson, Gerbrand Ceder, and Anubhav Jain.  Unsupervised word embeddings capture latent knowledge from materials science literature.  Nature, 571(7763):95–98, 2019.
  * [29] M. E. J. Newman.  Finding community structure in networks using the eigenvectors of matrices.  Physical Review E, 74(3):036104, 2006.
  * [30] 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 WSDM, WSDM ’18, pages 459–467, New York, NY, USA, 2018. Association for Computing Machinery.
  * [31] Jeffrey Pennington, Richard Socher, and Christopher Manning.  GloVe: Global Vectors for Word Representation.  In Proceedings of the 2014 Conference on EMNLP, pages 1532–1543, Doha, Qatar, 2014. Association for Computational Linguistics.
  * [32] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik.  Towards a unified framework for fair and stable graph representation learning.  In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 2114–2124. PMLR, 2021.
  * [33] Arash Dehghan-Kooshkghazi, Bogumił Kamiński, Łukasz Kraiński, Paweł Prałat, and François Théberge.  Evaluating node embeddings of complex networks.  Journal of Complex Networks, 10(4):cnac030, 2022.
  * [34] Aditya Grover and Jure Leskovec.  Node2vec: Scalable Feature Learning for Networks.  In Proceedings of the 22nd ACM SIGKDD International Conference on KDD, KDD ’16, pages 855–864, New York, NY, USA, 2016. Association for Computing Machinery.
  * [35] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive Representation Learning on Large Graphs.  In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [36] Lu Liu, Nima Dehmamy, Jillian Chown, C. Lee Giles, Dashun Wang, and Dashun Wang.  Understanding the onset of hot streaks across artistic, cultural, and scientific careers.  Nature Communications, 12(1):5392, 2021.
  * [37] Lingqi Meng and Naoki Masuda.  Analysis of node2vec random walks on networks.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 476(2243):20200447, 2020.
  * [38] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  DeepWalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD International Conference on KDD, KDD ’14, pages 701–710, New York, NY, USA, 2014. Association for Computing Machinery.
  * [39] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  LINE: Large-scale Information Network Embedding.  In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, pages 1067–1077, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee.
  * [40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  International Conference on Learning Representations, 2018.  accepted as poster.
  * [41] Santo Fortunato.  Community detection in graphs.  Physics Reports, 486(3):75–174, 2010.
  * [42] Santo Fortunato and Darko Hric.  Community detection in networks: A user guide.  Physics Reports, 659:1–44, 2016.
  * [43] Santo Fortunato and Mark E. J. Newman.  20 years of network community detection.  Nature Physics, 18(8):848–850, 2022.
  * [44] Tiago P. Peixoto.  Parsimonious module inference in large networks.  Physical Review Letters, 110(14):148701, 2013.
  * [45] Brian Karrer and M. E. J. Newman.  Stochastic blockmodels and community structure in networks.  Physical Review E, 83(1):016107, 2011.
  * [46] Yichi Zhang and Minh Tang.  Exact Recovery of Community Structures Using DeepWalk and Node2vec.  (arXiv:2101.07354), 2022.
  * [47] Pin-Yu Chen and Alfred O. Hero.  Universal phase transition in community detectability under a stochastic block model.  Physical Review E, 91(3):032804, 2015.
  * [48] Pin-Yu Chen and Alfred O. Hero.  Phase Transitions in Spectral Community Detection.  IEEE Transactions on Signal Processing, 63(16):4339–4347, 2015\.
  * [49] Yichi Zhang and Minh Tang.  Consistency of random-walk based network embedding algorithms.  (arXiv:2101.07354), 2021.
  * [50] Emmanuel Abbe and Colin Sandon.  Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery.  2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670–688, 2015.
  * [51] M. E. J. Newman.  Networks: An introduction.  Oxford University Press, Oxford; New York, 2010.
  * [52] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang.  Spectral redemption in clustering sparse networks.  Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.
  * [53] Florent Benaych-Georges, Charles Bordenave, and Antti Knowles.  Spectral radii of sparse random matrices.  Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 56(3):2141 – 2161, 2020.
  * [54] M. E. J. Newman.  Spectral community detection in sparse networks.  (arXiv:1308.6494), 2013.
  * [55] Pan Zhang and Cristopher Moore.  Scalable detection of statistically significant communities and hierarchies, using message passing for modularity.  PNAS, 111(51):18144–18149, 2014.
  * [56] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová.  Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.  Physical Review E, 84(6):066106, 2011.
  * [57] Code: Network clustering via neural embedding.  https://github.com/skojaku/research_graph_emb_detec_limit, 2023\.  Accessed: 2023-06-08.
  * [58] Raj Rao Nadakuditi and M. E. J. Newman.  Graph Spectra and the Detectability of Community Structure in Networks.  Physical Review Letters, 108(18):188701, 2012.
  * [59] Anne Condon and Richard M. Karp.  Algorithms for Graph Partitioning on the Planted Partition Model.  In Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, and Alistair Sinclair, editors, Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques, Lecture Notes in Computer Science, pages 221–232, Berlin, Heidelberg, 1999\. Springer.
  * [60] Filippo Radicchi.  Detectability of communities in heterogeneous networks.  Phys. Rev. E, 88:010801, 7 2013.
  * [61] Mikhail Belkin and Partha Niyogi.  Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.  Neural Computation, 15(6):1373–1396, 2003.
  * [62] Sadamori Kojaku, Jisung Yoon, Isabel Constantino, and Yong-Yeol Ahn.  Residual2Vec: Debiasing graph embedding with random graphs.  In Advances in Neural Information Processing Systems, volume 34, pages 24150–24163. Curran Associates, Inc., 2021.
  * [63] Martin Rosvall and Carl T. Bergstrom.  Maps of random walks on complex networks reveal community structure.  Proceedings of the National Academy of Sciences, 105(4):1118–1123, 2008.
  * [64] Alexander J. Gates, Ian B. Wood, William P. Hetrick, and Yong-Yeol Ahn.  Element-centric clustering comparison unifies overlaps and hierarchy.  Scientific Reports, 9(1):8574, 2019.
  * [65] Filippo Radicchi.  A paradox in community detection.  EPL (Europhysics Letters), 106(3):38001, 2014.
  * [66] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi.  Benchmark graphs for testing community detection algorithms.  Physical Review E, 78(4):046110, 2008.
  * [67] Andrea Lancichinetti and Santo Fortunato.  Community detection algorithms: a comparative analysis.  Physical review E, 80(5):056117, 2009.
  * [68] Tatsuro Kawamoto, Masashi Tsubaki, and Tomoyuki Obuchi.  Mean-field theory of graph neural networks in graph partitioning.  In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [69] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed Representations of Words and Phrases and their Compositionality.  In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
  * [70] Omer Levy and Yoav Goldberg.  Neural Word Embedding as Implicit Matrix Factorization.  In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [71] Naoki Masuda, Mason A. Porter, and Renaud Lambiotte.  Random walks and diffusion on networks.  Physics Reports, 716–717:1–58, 2017.