Asymptotics of $\ell_2$ Regularized Network Embeddings
Authors: Andrew Davison
Venue: NeurIPS 2022 Accept (2022)
Keywords: networks
embeddings
graphons
representation learning
network embeddings
regularization
asymptotics
exchangeable graphs

Abstract: A common approach to solving prediction tasks on large networks, such as node classification or link prediction, begin by learning a Euclidean embedding of the nodes of the network, from which traditional machine learning methods can then be applied. This includes methods such as DeepWalk and node2vec, which learn embeddings by optimizing stochastic losses formed over subsamples of the graph at each iteration of stochastic gradient descent. In this paper, we study the effects of adding an $\ell_2$ penalty of the embedding vectors to the training loss of these types of methods. We prove that, under some exchangeability assumptions on the graph, this asymptotically leads to learning a graphon with a nuclear-norm-type penalty, and give guarantees for the asymptotic distribution of the learned embedding vectors. In particular, the exact form of the penalty depends on the choice of subsampling method used as part of stochastic gradient descent. We also illustrate empirically that concatenating node covariates to $\ell_2$ regularized node2vec embeddings leads to comparable, when not superior, performance to methods which incorporate node covariates and the network structure in a non-linear manner..

Asymptotics of l Regularized Network Embeddings
Andrew Davison Department of Statistics Columbia University
New York, NY 10027
ad3395@columiia. edu
Abstract
A common approach solving prediction tasks on large networks, such node classification or link prediction, begins by learning a Euclidean embedding of the nodes of the network, from which traditional machine learning methods can then be applied. This includes methods such as DeepWalk and node2vee, which learn embeddings by optimizing stochastic losses formed over subsamples of the graph at each iteration of stochastic gradient descent. In this paper, we study the effects of adding an l2 penalty of the embedding vectors to the training loss of these types of methods. We prove that, under some exchangeability assumptions on the graph, this asymptotically leads learning a graphon with a nuclear- seeeaar-oom-ttyee penalty, and give guarantees for the asymptotic distribution of the learned embedding vectors. particular, the exact form of the penalty depends on the choice of subsampling method used as part of stochastic gradient descent. We also illustrate empirically that concatenating node covariates to & regularized node2vec embeddings leads to comparable, when not superior, performance to methods which incorporate node covariates and the network structure a non-linear manner.
1 Introduction
Network embedding methods (see e.g 6, 24-27, 48, 58, 64] aim to find a latent representation of the nodes of the network within Euclidean space, in order facilitate the solution of tasks such as node classification and link prediction, by using the produced embeddings as features for machine learning algorithms designed for Euclidean data. For example, they can be used for recommender systems in social networks, or to predict whether two proteins should be linked in a protein- ppretinn interaction graph. Generally, such methods obtain -tate-of-the-ar performance on these type of tasks.
classical approach to representation learning is to use the principal components of the Laplacian of the network [6]; however, this approach is computationally prohibitive for large datasets. In order to scale to large datasets, methods such as DeepWalk [48] and node2vec [25] learn embeddings via optimizing a loss formed over stochastic subsamples of the graph. Letting G (V, E) denote an undirected graph, and writing Wa Rd for the embedding of a vertex V with embedding
dimension d such that < [V], these methods learn embeddings by itcrating over the following process: we take random walk (u))is over the graph, form a loss
C= Σ
Σ
( Ww,))
E ((H1s)) log(1 a(Wwe, wo, mo.)i)] (1)
1=1 gg
and then perform gradient updates of the form We + Wa 7 L for some step size 7) > 0. Here (+-)) denotes the Euclidean inner product, W is a window size, NV-lu) a negative sampling distribution for vertex v and (v) == (1 + --ー the sigmoid function.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Other methods take variations on this approach for example. LINE [58] replaces the random walk by sampling edges uniformly from the edge set of the graph. One can generalize (I) capture both these cases, by considering embeddings learned via stochastic updates
We f- Wu - V... C
where
C
(p((w,wu)) + Σ (x(((w),)))) (t.))P
Σ
(2)
(K.))N
P,N C Vx V random subsamples of the graph called positive and negative samples respectively [see e.g 32], and fp(-) and (x(()) are chosen to force the embeddings of vertex pairs appearing in P close together, and those in N far away. Usually
-ogg (vy) and (vr - -log of -y) For example, in node2vec P is formed by taking concurrent edges in random walk, and LINE, P is formed by uniform edge sampling; in both methods N is taken be the same negative sampling distribution (ulu) deg(u)3/4 [46]. The scheme in (2) attempts to minimize
takes (p(y)
R = (P((())) P)Cp((u, w))) 5( E (N)
obtained by averaging over the random process used create P and N at each iteration of stochastic gradient descent [55, 63]; see Appendix 1.1 for a detailed derivation.
In the case where (p(y) = log (vy) and (x(() = log (-y), with P and N being random subsets of & and (V x V) \ E (such as in LINE, or node2vec with a window length of 1), then we can view (3) the function obtained via trying to minimize the negative log-likelhhood (equivalent to maximizing the log- log-likelihood) of a probabilistic model
Gav Was Wr ~ Bernoulli(o (aanoulll((((wa, (Ww, w.))) independently for < S,
(aur 11 indicating (u, u) is edge) using the stochastic gradient descent scheme specified in (2) (see Appendix B.2). If it is assumed that the embedding vectors are drawn i.i.d from some latent distribution, then this corresponds to implicitly fitting an exchangeable model the graph [44] Appendix A for a brief discussion on these models. Here the distribution of the adjacency matrix (aww) a.v is invariant to joint permutations of the vertices of the network, or equivalently (by the Aldous-Hoover theorem [1]) arise from a probabilistic model
Ay ~ Un, 1J) independently,
auv Au A ~ Bernoulli (Au, X,)) independently, (5)
for some symmetric measurable function W [0, 1]2 + [0. 1] called a graphon. We highlight that the model in (4) is implicitly fitting dense graph model to the data, even when the observed graph data are sparse, as is the case with real world networks. One way of partially addressing this issue is to consider a sparsified exchangeable graph with W > p., W for some sparsifying sequence Pr. -> 0.
natural example of a prior distribution on embedding vectors is W; ~ Normal (2g)-1/21a) for some constant & >> O, so that the contribution to the negative log-likelihood of each embedding is & [w. The full negative log- likellood of (4) with such a prior distribution is then given by
(as log ((w,, w/)) + (1 02y) log ( w/))3 + E Σ 1
(6)
which depends only on the matrix Gij = (w), this loss can also arise by considering a weight decay optimization scheme [see e,g 38]. In either case, letting l2 E gaxd be the matrix whose rows are the wi, so = S21T we get that
1
1 113
Wi
(nnT), tr() i=1
(7)
i=1 j=1
i=1 j=1
where ||G|| is the nuclear norm, which equals the sum of the singular values of G.
As result, we can view (6) as a regularized matrix factorization problem, where the nuclear-nore norm penalty on the matrix G is well known to shrink the singular values of G' exactly towards zero, and to make G low rank [see e.g 4, 19. 37, 54]. This consequently lowers the effective dimension of the embeddings. From computation perspective, this is advantageous compared to treating the embedding dimension as a tunable hyperparameter, as warm-start procedures can be used to efficiently tune the regularization weight & (and consequently the effective embedding dimension). Tuning

---

the dimension optimality is also desirable, as generally networks have exact factorizations than the embedding dimensions usually chosen in embedding models [16].
In this paper, our interest is in studying the effects of such a regularizer in the scenario where embeddings are learned via subsampling, in which case the corresponding version of (3) becomes
Σ (P((i.) E
e ())e + Σ P(i +Ep(i V(PUN)) (8)
where V(PUM is the set of vertices which appear either in P or M (see Appendix B.3). The first part of the likelihood can still be thought of corresponding see e.g [50]. However, we note that for certain sampling schemes (e.g random walk samplers), the probability vertex is sampled is not equiprobable across vertices, and so the regularizer will not be the same form as in (7). Despite this, we still want to analyze the extent to which nuclear norm type regularization (and hence effective dimension reduction) may still arise. To do so, we study minimizers (W1,.... (x,) of (8) assuming the graph arises from sparsified exchangeable graph, and obtain guarantees of the form
matrix factorization term-
Σ (())0))) - K(A, K(A,,,))) (1( and min QEO(d)
Σ @ 0100112= = o2(1) (9)
for some functions K 10. R and vb [0, 1- Rd obtained through the process of minimizing the population objective (Section 3). Our results allow us to recover the motivation above that the regularization acts to reduce the effective dimension of the learned embedding vectors. We also illustrate experimentally that using such regularization can give performance competitive to architectures such as GraphSAGE (Section 4). We note that our theoretical results apply in the regime < n, reflecting chosen embedding dimensions in practice. This means that (8) is con-covex in the matrix Gt (y)) due to rank constraints, which complicates the theoretical analysis (as compared to e.g (50].)
1.1 Related works
Guarantees for embedding methods: We highlight that there is an extensive literature on the embeddings formed by the eigenvectors of the adjacency or Laplacian matrices of a network [e.g 3, 40-42, 56, 59]. Under various latent space models for the network, these works give guarantees on quantities of the form max; |ā; Q for some orthogonal matrix Q and vectors the to discuss community detection task. Stronger
recovery of latent variables and/or obtain exact recovery bounds obtained in this setting they are able to directly apply matrix eigenvector perturbation methods to study the embeddings, which we cannot with our approach; as a tradeoff, our approach allows us study embeddings learned via variety of subsampling schemes, which these works do not. We highlight that the second bound in (9) can still be used to give guarantees for weak recovery of community detection [41]. There a few works discussing random walk methods like node2vec, albeit circumventing the non-convexity in the problem: [50] discusses the unconstrained minima of the loss (1) when d = n, with [68] then examining the best rank approximation to this matrix when the generating model is a stochastic block model with communities and r S k. [21] covers the non-convex regime d < in the case where &.. 0, ie without regularization.
Nuclear norm penalties and le regularized embeddings: In the context of matrix factorization (so the matrix factors embedding matrices), the effects of Frobenius norm penalties inducing nuclear norm penaltics are well known [e.g 53, 61]: generally, there is an extensive literature on the effects of nuclear norm penalization in the finite-dimensional setting [e.g 4, 19, 37, 54]. In [67], it is also shown that & regularized node2vec gives an improvement in performance on downstream tasks.
Graphon estimation: We mention that our guarantees on the gram matrix formed by the learned embeddings are similar to those obtained the graphon estimation literature [see e.g 8, 9, 18. 22, 35, 39, 65, 66]. Depending on the choice of sampling scheme and loss, it is possible for the limiting matrix ((2,, X₂)) to be an invertible transformation of W(A, Ag), and so we compare our rates of convergence in such a scenario (sce Remark 6 in Appendix D).
3

---

2 Framework and assumptions of analysis
Given a sequence of graphs 9n (Vn, E,), and writing wn = (wi,...,,.p) with wa E R denoting the d-dimensional embedding of vertex u, we study the regularized empirical risk function
(w,) + En (Rn((w)) where (n(ww)== = Σ
P((..) E S(G.) (.)) (() 1.jinl
*F
(10)
(w)) =
Σ EE(m
P( e V(S(G)) (..))
for E. 2 Here, we define a subsample S(G) of graph & as a collection of vertices V(S()) and symmetric subset of V(S(G)) x V(S(g)). we will soon assume that the Gn also arise from probabilistic model. We note (10) arises from (8) whenever P and N are random subsets of e,, and V x V &n respectively (see Appendix B.4).
The sampling probabilities are conditional on 9n as
Throughout, f(y,)) either the cross-entropy loss (y, x²) == -x log (y)) (1 - x)) logo(-y) or the squared loss (2, x) := (y- z)². We now discuss our assumptions on the generative model of the graph. Recall in the introduction we argued embedding methods are implicitly fitting an exchangeable graph model; consequently, as first step to analysis, we will assume that the graph arises from sparsified graphon (to account for the sparsity in graphs observed in the real world).
Assumption We assume that the sequence of graphs (Gn)n21 have vertex sets Vn = [n] and arise from a graphon process with generating graphon Wn P. W with Pa > log(n)/n, so that
X Unif[O, 1] for i [n], a.yldi, 22 indep Bernoulli W(,, for
We moreover suppose that W E Ic, some >> O, and either a) W is piecewise constant partition Q x where a partition of [0, 1] of size (so the model a stochastie block model), or b) W is Hölder([O, 113, Lw) for some exponents and constants Sw E (0, 1] and Lw < co.
We provide an introduction to graphon models in Appendix A.
Remark Here we use the canonical choice of uniform latent variables for the graphon as guaranteed by the Aldous-Hoover theorem for vertex exchangeable graphs [1]; in principle, our results can extend to graphons on higher dimensional latent spaces by the same style of arguments ssee egg 21]. We highlight that our assumptions and and spursity conditions; while it is common to allow On. >> log(n)/ /n je.g 47, 65] in which case the degree structure is regular, not necessarily realistic of real world networks it is also common to work in the regime where Pn. = (log(()) general graphons, regardless of the sparsity factor, tend not give rise graphs with power-law or heavy-tailed type degree structures, which is frequent with real world networks [15, 69/.
somewhat restrictive with regards to the boundedness
m)/nn) /n) or smaller g 9, 66]. We highlight that in
For subsampling schemes used in practice (such as random walk and uniform edge samplers), the sampling probability of vertices and edges depends only on local features of the graph. Following [21], we can formalize this as follows:
Assumption 2. There exist sequences of measurable functions (fa)22 and (ān)m21 and sequence 8n = o(1), such that
n n²P(((,5) ((9.))9n) (nis)djj;
(i V(S(G.)) 19.)
max M
Op()s,,
max
=Op(s))
:E(n]
(a():)
and moreover [B]s(AA,, A2 (12) = 0(1) [B ,2
BLG (A1)) = O,
This assumption allows us to replace the sampling probabilities in the empirical risk by functions which depend on the latent variables and edge assignments in the model, from which the exchange- ability in the model can be used to allow for a large sample analysis. Examples of sampling schemes satisfying this condition are given in Section 3.2. We additionally impose some regularity conditions on the "averaged" versions of the above functions defined by
f,,1,11, f,,,,'', (1,)
Fa(1,(',) = fn(1,", (w,((,))
(1I)
4

---

Assumption 3. We assume the the functions fn(1, fn(1, I., .0) and (1) are uniformly bounded above by M and away from zero by M for some constant M (0, (0)) We also suppose that either a) there exists a partition Q of [0, 1] into K. parts such that fn(1, 1) and fn(1, I', 0) are piecewise constant on Q x Q. and In (I) is piecewise constant on Q: or b) the fn(,, (', 1) and fn .0) are Hölder([0, 1]2. L), and that the (1) are Hölder((0, 11, B. L.).
Assumption 3 will follow as consequence of Assumptions and 2 for the sampling schemes discussed Section 3.2, with depending on Sw and the hyper-parameters of the sampling scheme.
3 Theoretical results
Our theoretical results take the following flavour: we identify the correct population versions (in reference to an infinite graphon on vertex set N) of R., (wn) and R. R in the large sample limit n + oo to give a regularized population risk, and then use this to give guarantees about any minimizers of R,, (w,, E, R. R.,(,,))) (w..) being close (in some sense) the unique minimizer of the regularized population risk. As network embedding methods are used on very large networks, such a large sample statistical analysis is appropriate.
We introduce the population versions of RR, and R, (w)) respectively as
[ == /
Σ (((),,))((((()))..)))))) didl',
I [
[. (() dl, (12)
10.11 xE/0,11
[K] was first introduced in [21]. The formula given for Z.e(K' holds only for K whose diagonal is well defined; in general, if K admits a decomposition
defined over functions K [0, 1
I,
where L. (0:00,s (1)
{o
if J.
K(I11) = Σ (())))))))
(13)
otherwise.
and μ4 (K) 2 for (understood as a limit L2((0, 1j²)), then we can extend the definition of the regularizer to be I [=*[K]] :- D p4; (K). Consequently, the penalty corresponds to the trace of K, when viewed as the kernel of a Hilbert-Schmidt operator. This means that I [K] should be viewed nuclear-norm penalty on the kernel K, which encourages the (²(K)) to be shrunk exactly towards zero, similar to the finite dimensional scenario; also see e.g. Theorem 5.
3.1 Guarantees on the learned embedding vectors
We hegin with a result which guarantees that I,
+ Ina K] once restricted to an appropriate domain, is the correct population version of RR, (w,)) En Ru (w,))
[K] [n[K]]
Theorem 1. Suppose that Assumptions 2 and 3 hold, and that & 0()) Define
(A) = {K {
K(1,'' ((()))))))))) [0, [-,, E N
Then we have that
min W.ElllA.AA)jy
{ (wn) + En (.T.(( (wm)} (A)
[In[K] + +nIT (r(r)) min
where Tn Sn + (d /npm) tn. with t, (log 1/2 under Assumption 3a), t, (og(n)//28/(1+2))) 1/2 under Assumption 3b), p 3 for the cross-entropy loss and p for the squared loss.
See Appendix C for the proof and a discussion of the rates given; we note that it is necessary that d & n in order for r, + O. The rates can be improved to give p = 1, under additional restrictions on
the parameter space (Remark 3). The interpretation of the set 2 (A4) ( is as follows: if [-A, A]d is the embedding of vertex u, in the population limit r)(,,, E [- A]d should give the embedding of a vertex with latent feature Aa. As (10) parameterized through terms of the form (wi, wo), the population version of (10) should be parameterized through functions K (Xu, Av) (m(Aa), ((.)))
5

---

We note that the assumption that the embedding vectors belong to a hypercube [-A, A]a not restrictive: for example, in practice embedding vectors are usually initialized randomly and uniformly over [-1.1] Moreover, our results allow for A to grow logarütmiically with n, and only change the bound by poly-log factor. vectors will shrink towards O as n + 0o (as seen in Figure 1). This is because the proof of Theorem I shows that any minimizer must satisfy n -1 "i= || 12 = 0p((n)) = (1) in such a regime.
Remark 2.
highlight that if En. -> 0o as - Dc, then the embedding
We now give convergence guarantees for any sequence of embedding vectors minimizing (10).
Theorem 2. Suppose that Assumptions 2 and hold and that En = O1). Then for each there exists a unique minimizer to the optimization problem
K n = arg min [In[K] + E.IN5[K] where z = cl U ( KEZ20
d21
is free of A 0 (see Proposition 2 for details). Moreover, under some regularity conditions on the Kü (see Theorem 7 in Appendix D), there exists A' < oc free of n and a sequence of embedding dimensions d(n) & n. such that, for any sequence of minimizers
Wn E
arg min w., W,EE([-A A1,)""")
(Ro(wa) + En (T satisfying max (a,, & A2
i
with AI, A2 2 A', we have that
Σ -)(,))))) 4.jmm
n²
Moreover, when Assumption 3a) holds, K can be computed via a finite dimensional convex program, and is of rank r S K, that an expansion of the form (13) holds with (T,(K), = 0 > r.
The case where &n 0 is proven in [21], which also verifies the convergence on simulated data. A proof is given in Appendix D. Under certain circumstances, this allows us to give guarantees about the distribution of the embedding vectors themselves.
Theorem 3. Suppose that K₁ is regular in the sense of Theorem 2, with the conclusions of the theorem holding. Moreover suppose that K; is a kernel of rank r < 0o, has a decomposition of the form (1, (') Ei=1 án,;(1 (l))(()) (I') (") for some functions on,i [0. R. and the dimension d of the embedding vectors is chosen to be equal to r. Writing @n(1) = (On, (1)) we have
min QEO(r)
Σ
| Qon (p()
(14)
The assumption that d r in Theorem is a restrictive one, given that embedding dimensions in practice are usually chosen to be one of either 128, 256 or 512. This can be alleviated by instead giving a guarantee for the optimal r dimensional projection of the embedding vectors.
Theorem 4. If instead d > in Theorem 3, let G e gax= denote the best rank approximation the matrix Giz := ((0t, ((Dt,,y))s kij, and write G Ω for some á E Raxr, Then n -2I Gllß- = (1),
and writing Wن for the rows of 22 the guarantee in (14) holds with 24 replacing the W.
Informally, this says that the embedding vectors approximately lie r-dimensional subspace which contains some latent information about the network, depending on the minimizing kernel K We now highlight that the assumption that K; is of finite rank оo restrictive even when W is not a SBM; this is a consequence of the effect of the regularization penalty I [K].
Theorem Let Eyy, x) be the squared loss, and suppose that pn 1, Ia(,,',) f. (). Ci and Jn (1) = C2 for some constants Cı, C2 >> 0 (see e.g. Algorithm in Section 3.2). Then if W is Hölder((0. (0, 1]2,33 L), the minima of I [K] + En [K] over 2 of finite rank for any & >
and is also Hölder continuous of exponent 3.
We highlight that this result also shows that the regularizer acts to shrink the singular values of mini- mizer of [K] + I..% [K] exactly towards zero. See Appendix E for proofs of Theorems 3, 4 and 5.

---

3.2 Sampling schemes satisfying Assumption
We now discuss some examples of frequently used sampling schemes which satisfy Assumption Proofs of the results in this section can be found in Appendix F. We introduce the notation
W(A,)) = S. w().
v) dy, Ew(a) := S. w (2) dA, Ew == Ew (1).
(15)
Algorithm (Uniform vertex sampling). Given a graph 9n and number of samples k. we select vertices from In uniformly and without replacement, and then return S(gn) as the induced subgraph using these sampled vertices.
1), (rs) = l and Lemma 1. For Algorithm 1, Assumption holds with fn >3. Aiÿ) = k(k 1),
8n = 1/nn.
Algorithm (Uniform edge sampling [58]). Given a graph Gn. number of edges to sample k; and number of negative samples per positive sample,
i) We form a sample So(g.) by sampling edges from Gn uniformly and without replacement;
ii) We form a sample set of negative samples Sns(gn) by drawing, for each u E V(So(Gn)), I vertices U1,-.., Ut ii.d according to the unigrum distribution
Ug. (v) x PP
V(So(9.))1G.))
and then adjoining (u, vz) - Sno if auv. = O.
We then return S(Gn) as the union of So(Gn) and (nn(
Lemma 2. For Algorithm 2, Assumption 2 holds with 8n (log(n)/npm))
2k [n(Ai, >3, 0) Ew Ewewaa
2kl
(n(A,,2;11) Ew En
(A W(A,, (WW
(A,) 2A,(A,, 2kI
1 (1- (1-Pa (A).))))(().)) dy.
Ew
(wE
Algorithm 3 (Random walk sampling [25, 48)). Given a graph Ga, a walk length k. number of negative samples per positively sampled vertex and unigram parameter a, we
i) Perform a simple random walk on Gn of length k beginning from its stationary distribution, to form a path (f:)eck+1, and report (0t, 01+1) for S k as part of So(Gn);
i) For each vertex iú we select vertices (1b))s independently and identicully according to the unigram distribution
Ug (v & PPOū; = for some i S ke (n))
and then form Sas as the collection of vertex pairs (ūa, mī)) which are not an edge in Gn-
We then return S(Gu) as the union of So(gu) and Sns(Gn)
Lemma 3. For Algorithm 3, Assumption 2 holds with 8n = (log(n)/rp..)")
In(A 1, EwPh In(As,)) 1(k 1)
2k:
(W (W + (
(w)
(k: 1))W
S' (1- -1. (L. ())
(A,)
+
-
Ew
Ew (a)Ew
Examining the formula for In (A) above, we see that for random walk samplers the shrinkage provided to the learned kernel will be greater for vertices with larger degrees. Indeed, as K(,, A) (A)
for K E (A). the larger 9n (A) is, [ln())]13 will be forced closer towards zero.
7

---

g
(b) 5 10
(c) E 10
(d) 5 10"
Figure 1: TSNE visualizations of Cora network embeddings, learnt using node2vec for different regularization penalties ç, with different colors representing different classes, As increases, the classes begin to cluster together and separate, and then eventually collapse towards the origin.
3.2.1 An illustrating example
We give brief illustration of theoretical results under simple graphon model. To do so, we consider a sparsified SBM with & communities, each equiprobable, and with probabilities PrP and Pr. (p 9) denoting the within-community and www.eenn-oommuityy edge probabilities. Writing A; = [[i 1)/K, i/K) for E [k], this can be represented as graphon model with graphon Wn P. W, where W (u,,) = p (u,v) u) II: A; x A; and W (u, v) q otherwise.
Theorem 6. Suppose that the graph arises from the model discussed above, we use cross-entropy loss and the random walk sampling scheme as described Algorithum 3. Then Theorem holds such that, for any minimizer Wn = [ (.) satisfying (2) of Theorem 2, we have that
Σ (1)) A,)) (1) where K, (u, (Ka)as (f, v) E A,
and Kn E BRX is defined as the unique positive semi-definite minimizer of the function
(2kc1 (pd:) + q(1 - -.5)) (K,, + 20(k + log a (-KK)) + [c2l|
). In particular, for the above example we see that the form of the regularizer is exactly the muclear norm of K, and so as & increases, the singular values of the minimizer will be shrunk towards zero.
where we write 01 == ((p+ (K- 1)4)/k²) k)) and C2 = ls 1(k: + 1)(1 -
4 Experiments
We now examine the performance in using regularized node2vec embeddings for link prediction and node classification tasks, and illustrate comparable, when not superior, performance more complicated encoders for network embeddings. We perform experiments on the Cora, CiteSeer and PubMedDiabetes citation network datasets (see Appendix G for more details), which they are commonly used benchmark datasets see e.g [26, 28, 34, 64].
4.1 Methods used for comparison
For our experiments, we consider 128 dimensional node2vec embeddings learned with either no regularization, or l2 penalty on the embedding vectors with weight Ç E {1, x 10 63,455,6,7788 and with without the node features concatenated. We compare these against methods which incorporate the network and covariate structure together in a non-linear fashion. We consider three methods- two layer GCN [33] with 256 dimensional output embeddings trained in an unsupervised fashion through the node2vec loss, two layer GraphSAGE architecture [26] with 256 dimensional output embeddings trained through the node2vee loss, and a single layer 256 dimensional GCN trained using Deep Graph Infomax (DGI) [64]. We highlight that the GCN, GraphS AGE and DGI always have access to the nodal features during training. All of our experiments used the Stellargraph [20] implementations for each method. Further experimental details given in Appendix G.

---

Table PR AUC scores for link prediction experiments, and macro Fl scores for node classification experiments. "n2v" stands for node2vec without regularization; "m2v" stands for regularized node2vec with the best score over the specified grid of penalty values; "NF" indicates that node features were concatenated to the learned node embeddings.
PR AUC (link prediction)
Macro Fl (node classification)
Methods
Cora
CiteSeer
PubMed
Cora
CiteSeer
PubMed
n2v
0.84 + 0.01
0.80 + 0.02
0.86 + 0.01
0.67 + 0.04
0.48 + 0.03
0.76 0.00
rn2v
0.90 + 0.01
0.88 + 0.02
0.91 + 0.00
0.73 + 0.03
0.55 + 0.04
0.77 + 0.00
n2v+NF
0.88 0.01
0.90 + 0.01
0.92
0.54 0.03
0.79
m2v+NN
0.92 0.01
0.93 0.01
0.74
0.58 0.04
0.84 0.00
GCN
0.90 0
0.07
0.00
0.07
0.48 0
0.80
GSAGE
0
0.90 0.01
0.88
0.04
0.56
0.79
DGI
0.91 0.01
0.93 0.01
0.95
0.02 0.03
0.84 0.00
4.2
Link prediction experiments
For the link prediction experiments, create training graph by removing 10% of both the edges and non-edges within the network, and use this to learn an embedding of the network. We then form link embeddings by taking the entry-wise product of the corresponding node embeddings, use 10% of the held-out edges to build a logistic classifier for the link categories, and then evaluate the performance on the remaining edges, repeating this process 50 times.
The PR AUC scores are given Table and visualized in Figure 2. Provided the regularization parameter is chosen optimally, we see improvement in performance compared to using no regularization, with the jump in performance slightly greater when nodal features are not incorporated into the embedding. The optimally regularized version of node2vec, even without including the node features, is competitive with the GCN and GraphSAGE (being equal or outperforming at least one of them across the three datasets), and that the version with concatenated node features is as good the GCN trained using DGI. For all the datasets, we observe a sharp decrease in performance after the optimal weight, suggesting that it needs to be chosen carefully to avoid removing the informative network structure. As seen in Figure 1, this occurs as the learned embeddings become randomly distributed at the origin once the regularization weight is too large.
4.3 Node classification experiments
To evaluate performance for the node classification task, we learn network embedding without access to the node labels, and then learn/evaluate a one-versus-rest multinomial node classifier using 5%/95% stratified training/test splits of the node labels. We repeat this over 25 training runs of the embeddings, and further 25 training/test splits for the node classifiers per embedding. Table I and Figure 2 show the average macro Fl scores and their standard deviation for each method and dataset. Similar to the link prediction experiments, we see that the optimally regularized node2vec methods are competitive, if not outperforming. the GCN and GraphSAGE trained through the node2vec loss, and is outperformed by the GCN learned using DGI by no more than two percentage points. In these experiments, the standard deviations correspond partially to the randomness induced by the training/test splits of the node labels, and suggest that the regularized version of node2vec is no less robust to particular choices of training/test splits than the other methods.
Interestingly, we note that the optimal performance on PubMed is given by the regularized node2vec with node features. However, as the highest level of performance is performed when the regularization weight is so large that the learnt embeddings are uninformative (as illustrated by the massive decrease in performance of the regularized method without node features), this suggests that the nodes can be classified using only the covariate information, and that the network features are not needed. As the dataset only has three distinct classes corresponding to the academic field, and the node features are TF-IDF embeddings of the academic papers, this is not too surprising.

---

0.C
0.-
D44
041
1o-07
15-05
16
1o
fe
1e
1e407
1er00
(a) PR AUC scores on Cora
(b) PR AUC scores on CiteSeer
(c) PR AUC scores on PubMed
06-
08-
07-
0.0
0.5
0.5
0.4
0.4
0.3
1o-07
1e-d5 1ex00
1ex07
1w/0
1wx07
1ei00
(d) Macro Fl scores on Cora
(e) Macro Fl scores on CiteSeer
(f) Macro Fl scores on PubMed
Figure 2: Plots of average PR AUC scores for link prediction and macro Fl scores for node classification (bands representing plus/minus one standard deviation), against the regularization penalty used for node2vec with (purple) and without (blue) concatenated node features. The results from GCN, GraphSAGE and DGI are given as horizontal bars in yellow, green and red respectively.
5 Conclusion
In this paper we have theoretically described the effects of performing la regularization network emhedding vectors learned by schemes such as node2vec, describing the asymptotic distribution of the embedding vectors learned through such schemes, and showed that the regularization helps to reduce the effective dimensionality of the learned embeddings by penalizing the singular values of the limiting distribution of the embeddings towards zero. We do so the non-convex regime d < n, reflecting how embedding dimensions are chosen in the real world. We moreover highlight empirically that using l regularization with node2vec leads to competitive performance on downstream tasks, when compared to embeddings produced from more recent encoding and training architectures.
We end with brief discussion of some limitations of our works, and directions for future work. Generally, graphons are not realistic models for graphs; we suggest that our work could be extended to frameworks such as graphexes [10. 11, 62] which can produce more realistic degree distributions for networks, but have enough underlying latent exchangeability for our arguments to go through. We ignore aspects of optimization, i.e whether the minima of (10) are obtained in practice, which we believe would be an interesting area of future research. As for our experimental results, we note that methods such GraphSAGE are better than node2vec in that they provide embeddings for data unobserved during training, and also scale better to larger networks. Consequently, we believe our experiments should be used primarily as motivation investigate better methods for incorporating nodal covariates into network embedding models, and how to regularize embeddings produced by encoder methods such as GCNs or GraphSAGE.
Acknowledgments and Disclosure of Funding
We thank Morgane Austern for helpful discussions, along with several anonymous reviewers for their comments on the current version of the paper, along with a prior version. We also acknowledge computing resources from Columbia University's 's Shared Research Computing Facility project, which is supported by NIH Research Facility Improvement Grant IG20RR030893-011 and associated funds from the New York State Empire State Development, Division of Science Technology and Innovation (NYSTAR) Contract C090171, both awarded April 15, 2010.
10

---

References
[1] D. J. Aldous. "Representations for partially exchangeable arrays of random variables". en. In: Journal of Multivariate Analysis 11.4 (Dec. 1981). pp. 581-598, ISSN: 0047-259X, DOI:
10. 1016/0047 -59X 9009993.
[2] C. D. Aliprantis and K. Border. Infinite Dimensional Analyss:: A Hitchhiker's 's Guide. en. 3rd ed. Berlin Heidelberg: Springer- Verlag, 2006. ISBN: 978-3-540-29588-00 DOI: 10.1007/3-540 29587-9.
[3] A. Athreya et al. "Statistical Inference Random Dot Product Graphs: a Survey". In: Journal of Machine Learning Research 18.226 (2018), pp. 1-92. ISSN: 1533-7928.
[4] F. R. Bach. "Consistency of Trace Norm Minimization". In: The Journal of Machine Learning Research (June 2008), pp. 1019-1048. ISSN: 1532-4435.
[5] V. Barbu and T. Precupanu. Convexity and Optimization in Banach Spaces. en. 4th ed. Springer Monographs in Mathematics. Springer Netherlands, 2012. ISBN: 978- 94--000-2246--.
[6] M. Belkin and P. Niyogi. "Laplacian Eigenmaps for Dimensionality Reduction and Data Representation". In: Neural Computation 15.6 (June 2003), pp. 1373-1396. ISSN: 0899-76677.
DOT: 10. 1112/1168888 089976603321111100 780317.
[7] D. P. Bertsekas and J. N. Tsitsiklis. "Gradient Convergence in Gradient methods with Errors". In: SIAM Journal on Optimization 10.3 (Jan. 2000). Publisher: Society for Industrial and
Applied Mathematics, pp. 627-642. ISSN: 1052-6234. DOI: 10. 1137 ///////0222222731116666
[8] Borgs, J. Chayes, and A. Smith. "Private Graphon Estimation for Sparse Graphs". In: Advances in Neural Information Processing Systems. Vol. 28. Curran Associates, Inc., 2015.
[9] C. Borgs et al. "Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation". In: arXiv: 1810:088000101 183 [cs, math, stat] (Oct. 2018).
[10] C. Borgs et al. "'Sappling perspectives on sparse exchangeable graphs". In: The Annals of Probability 47.5 (Sept. 2019). Publisher: Institute of Mathematical Statistics, pp. 2754-2800.
ISSN: 0091-1798, 2168-894X. DOI: 10. 1214/18- ADP12000122
[11] C. Borgs al. "Sparse Exchangeable Graphs and Their Limits via Graphon Processes". In: Journal of Machine Learning Research 18.210 (2018), 8), pp. 1-71.
[12] L. Bottou. "Une approche théorique de l'apprentissage connexioniste applications à la reconnaissance de la parole". These de doctorat. Paris 11, Jan. 1991.
[13] L. Bottou, F. F. Curtis, and J. Nocedal. Optimization Methods for Large-Scale Machine Learning. Tech. rep. 1606:06666.04500 Feb. 2018. DOI: 10. 40l.888550/50 /a15500/XXiii aaiiiv.iviiivv 1606. 04838.
arXiv:1606.0es 00438 [es, math, stat] type: article, arXiv,
[14] H. Brézis. Functional analysis, Sobolev spaces and partial differential equations. New York London: Springer, 2011. ISBN: 978-0-388-770914-7
[15] A. D. Broido and A. Clauset. "Scale-free networks rare". In: Nature Communications 10.1 (Dec. 2019). arXiv: 1801.03400, p. 1017. ISSN: 2041-1723. DOI: 10. 1038 s41467-019 087 5.
[16] S. Chanpuriya et al. "Node Embeddings and Exact Low-Rank Representations of Complex Networks". In: arXiv:2006.05597 [cs, stat] (Oct. 2020). arXiv: 2006.05592.
[17] S. Chatterjee. "Concentration inequalities with exchangeable pairs (Ph.D. thesis)". In: arXiv:math/0007526 (July 2005). arXiv: math/0507526.
[18] S. Chatterjee. "Matrix estimation by Universal Singular Value Thresholding". In: The Annals of Statistics 43.1 (Feb. 2015). Publisher: Institute of Mathematical Statistics, pp. 177-214.
ISSN: 0090-5364, 2668-88 8966. DOI: 10. 1214/14-A081777
[19] K. Chen. H. Dong, and K.-S. Chan. "Reduced rank regression via adaptive nuclear norm penalization". In: Biometrika 100.4 (Dec. 2013), pp. 901-920. ISSN: 0006-3444, DOL: 10. 1093 htte//iime.... t.me///tt03.......

---

[20] C. Dataól. StellarGraph Machine Learning Library. Publication Title: GitHub Repository.
2018.
[21] A. Davison and M. Austem. "Asymptotics of Network Embeddings Learned via Subsampling". In: urXiv:2107.02360 [es, math, stat] (July 2021). arXiv: 2107.02363.
[22] C. Gao, Y. Lu, and H. H. Zhou. "Rate-optimal graphon estimation". In: The Annals of Statistics 43.6 (Dec. 2015). Publisher: Institute of Mathematical Statistics, pp. 2624-2652. ISSN: 0090- 5364, 2168-8966. DOI: 10. 12t./11111111 -
[23] S. Ghadimi and G. Lan. "Stochastic First- and Zeroth-Ordee Methods for Nonconvex Stochastic Programming". In: SIAM Journal on Optimization 23,4 4 (Jan. 2013). Publisher: Society for Industrial and Applied Mathematics, pp. 2341-2368 ISSN: 1052-6234. DOr: 10 1137 / 120880811.
[24] P. Goyal and E. Ferrara. "Graph embedding techniques, applications, and performance: A survey". In: Knowledge-Bacd
Systems 151 (July 2018), pp. 78-94. ISSN: 0950-7051. DOI:
10. 10.1016/j knosys 2018 .0......0000 022.
[25] A. Grover and J. Leskovec. "node2vec: Scalable Feature Learning for Networks". In: ACM, ISBN: 978-1 1-550--42322 DOI: 10. 2946/299772. 2939754.
Aug. 2016, pp. 855-864,
[26] W. Hamilton, Z. Ying, and J. Leskovec. "Inductive Representation Learning on Large Graphs". In: Advances Neural Information Processing Systems. Ed. by I. Guyon al. Vol. 30. Curran Associates, Inc., 2017.
[27] W. L. Hamilton, R. Ying, and J. Leskovec. "Representation Learning Graphs: Methods and Applications." In: IEEE Data Eng. Bull. 40.3 (2017). Number: 3, pp. 52-74.
[28] K. Hassani and A. H. Khasahmadi. "Contrastive Multi-View Representation Learning on Graphs". en. In: Proceedings of the 37th International Conference on Machine Learning. ISSN: 2640-3498. PMLR, Nov. 2020, pp. 4116-4126.
[29] C. Heil. Metrics, Norms, Inner Products, and Operator Theory, en. Applied and Numerical Harmonic Analysis. Birkhäuser Basel, 2018. ISBN: 978-3-319-65321--1 DOI: 10. 1907/978- --19-65322-8.
[30] A. J. Hoffman and H. W. Wielandt. "The variation of the spectrum of a normal matrix". In: Duke Mathematical Journal 20 (1953), pp. 37-39. ISSN: 0012-7094.
[31] P. W. Holland, K. B. Laskey, and S. Leinhardt. "Stochastic blockmodels: First steps". en. In: Social Networks 5.2 (June 1983). Number: 2, pp. 109-137. ISSN: 0378-8733, DOI: 10. 1016/
0378- 1378-8733(C)) (83) (778-8733883900222 90021-7.
[32] P. H. Le-Khac, G. Healy, and A. F. Smeaton. "Contrastive Representation Learning: A Frame- work and Review"". In: JEEE Access 8 (2020). arXiv: 2010.05113, pp. 193907-193934, ISSN: 2169-3536. DOL: 10. 10/11199//CCO
2020. 3031549.
[33] T. N. Kipf and M. Welling "Semi-Supervised Classification with Graph Convolutional Net- works". In: /609v:/609.00000 /609 02907 [cs, stat) (Feb. 2017). arXiv: 6699072077
[34] T. N. Kipf and M. Welling. "Variational Graph Auto-Encoders". en. In: (Nov. 2016). DOI:
10. 48550 aaw.iii........ 1.w.1611.7700 07308.
[35] O. Klopp, A. B. Tsybakov, and N. Verzelen. "Oracle Inequalities For Network Models and Sparse Graphon Estimation". In: The Annals of Statistics 45.1 (2017). Publisher: Institute of Mathematical Statistics, pp. 316-354. ISSN: 0090-5364.
[36] V. Koltchinskii and E. Giné. "Random Matrix Approximation of Spectra of Integral Operators".
In: Bernoulli 6.1 (2000). Publisher: International Statistical Institute (ISI) and Bernoulli Society for Mathematical Statistics and Probability, pp. 167. ISSN: 1350-7265. DOI: 10. 22307/3318880
[37] V. Koltchinskii, K. Lounici, and A. B. Tsybakov. "Nuclear-Norm Penalization and Optimal Rates for Noisy Low-Rank Matrix Completion". In: The Annals of Statistics 39.5 (2011). Publisher: Institute of Mathematical Statistics, pp. 2302-2329, ISSN: 0090-5364.
12

---

[38] A. Krogh and J. A. Hertz. "A simple weight decay can improve generalization", In: Proceedings of the 4th International Conference on Neural Information Processing Systems. NIPS'91. San Francisco, CA. USA: Morgan Kaufmann Publishers Inc., Dec. 1991, pp. 950-957. ISBN: 978- 978-1-55880-222--
[39] P. Latouche and S. Robin. "Variational Bayes model averaging for graphon functions and motff frequencies inference in W-graph models". en. In: Statistics and Computing 26.6 (Nov. 2016),
pp. 1173-1185. ISSN: 1573-1375. DOI: 10. 1007
[40] Lei. "Network representation using graph root distributions". . In: The Annals of Statistics 49.2 (Apr. 2021). Publisher: Institute of Mathematical Statistics, pp. 745-768. ISSN: 0090-5364, 2168-8966 DO1: 10. 1214/20- A0S1976.
[41] J. Lei and A. Rinaldo. "Consistency of spectral clustering in stochastic block models". In: The Annals of Statistics 43.1 (Feb. 2015). arXiv: 1312.2050. ISSN: 0090-5364. DOT: 10. 20.1214/144 AQS1274.
[42] K. D. Levin et al. "Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings". In: Journal of Machine Learning Research 22.194 (2021), pp. 1-59, ISSN: 1533-7928.
[43] X. Li and F. Orabona. "On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes". en. In: Proceedings of the Swenty-Secont International Conference on Artificial Intelligence and Statistics. ISSN: 2640-3498. PMLR, Apr. 2019, pp. 983-992.
[44] L. Lovász. Large Networks and Graph Limits. Vol. 60. Colloquium Publications. American Mathematical Society, 2012. ISBN: 777-008218-9085-11
[45] O. Marchal and Arbel. "On the sub-Gaussianity of the Beta and Dirichlet distributions". EN. In: Electronic Communications in Probability 22 (2017). Publisher: The Institute of Mathematical Statistics and the Bernoulli Society. ISSN: 1083-589X. DOE: 10. 1214/17 ECP92.
[46] T. Mikolov al. "Distributed Representations of Words and Phrases and their Composi- tionality". en. In: Advances in Neural Information Processing Systems 26 (2013), pp. 3111- 3119.
[47] Oono and T. Suzuki. "Graph Neural Networks Exponentially Lose Expressive Power for Node Classification". In: arXiv: 10947 [cs, stat] (Jan. 2021). arXiv: 1905.10947.
[48] B. Perozzi, R. Al-Rfou, and S. Skiena. "DeepWalk: Online Learning of Social Representations" In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining- KDD '14 (2014), arXiv: 1403.6652, pp. 701-710. DOI: 10. 11445/22233330.
2623732.
[49] J. Peypouquet. Convex Optimization in Normed Spaces: Theory, Methods and Examples. en. SpringerBriefss Optimization. Springer International Publishing, 2015. ISBN: 978-3-319- 13709-4.
[50] J. Qiu et al. "Network Embedding as Matrix Factorization: and node2vec". In: Proceedings of the Eleventh ACM International Conference Web Search and Data Mining WSDM '18 (2018), arXiv: 1710.02971, pp. 459-467. DOI: 10. 1145/ 3159652.c 3159706.
Unifying DeepWalk, LINE, PTE,
[51] J. Reade. "Eigen-values of Lipschitz kernels", en. In: Mathematical Proceedings of the Cambridge Philosophical Society 93.1 (Jan. 1983). Number: Publisher: Cambridge University Press, pp. 135-140. ISSN: 1469-8064, 0305-0041. DOI: 10. 1017 10177/50300004100000411
[52] J. B. Reade. "Eigenvalues of Positive Definite Kernels". In: SIAM Journal on Mathematical Analysis 14.1 (Jan. 1983). Number: Publisher: Society for Industrial and Applied Mathemat-
ics, pp. 152-157. ISSN: 0036-1410 DOI: 10. 117700554412
[53] B. Recht, M. Fazel, and P. A. Parrilo. "Guaranteed Minimum-Ran Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization".. en. In: (June 2007). DOI: 10. 00.1117777777780
[54] B. Recht, M. Fazel, and P. A. Parrilo. "Guaranteed Minimum-Ran Solutions of Linear Matrix Equations via Nuclear Norm Minimization". In: SIAM Review 52.3 (Jan. 2010). Publisher:
13

---

Society for Industrial and Applied Mathematics, pp. 471-501. ISSN: 0036- 1445. DOE: 10. 1137/070697835
[55] H. Robbins and S. Monro. "A Stochastic Approximation Method". In: The Annals of Mathemat- ical Statistics 22.3 (Sept. 1951). Publisher: Institute of Mathematical Statistics, pp. 400-407.
ISSN: 0003-4851, 2168-8990. DOI: 10.
[56] P. Rubin-Delanchy et al. "A statistical interpretation of spectral embedding: the generalised random dot product graph". In: arXiv: (et::0:09000000 [cs, stat] (Sept. 2017). arXiv: 1709.05506.
[57] V. S. Sunder. Operators on Hilbert Space, en. Texts and Readings in Mathematics. Springer Singapore, 2016. ISBN: 978-981- 1--11-18116-9 Dor: www.10000977080
1816-..-9.
[58] J. Tang et al. "LINE: Large-scale Information Network Embedding". In: Proceedings of the 24th International Conference World Wide Web (May 2015). arXiv: 1503.03578, pp. 1067-
1077. DOT: 10. 145/2736277 .741779777
[59] M. Tang and C. E. Priebe. "Limit theorems for eigenvectors of the normalized Laplacian for random graphs". In: The Annals of Statistics 46.5 (Oct. 2018). Publisher: Institute of Mathematical Statistics, pp. 2360-2415. ISSN: 0090-5364, 2168-8966. DOI: 10. 1214/17- AOS1623.
[60] S. Tu et al. "Low-rank Solutions of Linear Matrix Equations via Procrustes Flow". en. In: Proceedings of The 33rd International Conference on Machine Learning. ISSN: 1938-7228. PMLR, June 2016, pp. 964-973.
[61] M. Udell et al. "Generalized Low Rank Models". In: arX:vv: [cs, math, stat) (May 2015). Xiv: 1410.0342.
[62] V. Veitch and D. M. Roy. "The Class of Random Graphs Arising from Exchangeable Random Measures", In: arXiv: 151.03399 [cs, math, stat] (Dec. 2015), arXiv: 1512.03099.
[63] V. Veitch et al. "Empirical Risk Minimization and Stochastic Gradient Descent for Relational Data". en. In: The 22nd International Conference on Artificial Intelligence and Statistics. ISSN: 2640-3498. PMLR, Apr. 2019, pp. 1733-1742.
[64] P. Veličković al. "Deep Graph Infomax". In: 100.vv1809.10344 [es, math, stat] (Dec. 2018).
arxiv: 1809. 1009.10341 10341.
[65] P. J. Wolfe and S. C. Olhede. "Nonparametric graphon estimation". In: arXiv: [math, stat] (Sept. 2013). arXiv: 1309.5936.
[66] J. Xu. "Rates of Convergence of Spectral Methods for Graphon Estimation". en. In: Proceed- ings of the 35th International Conference on Machine Learning. ISSN: 2640-3498. PMLR, July 2018, pp. 5433-5442.
[67] Y. Zhang. J. Lu, and O. Shai. "Improve Network Embeddings with Regularization". In: Proceedings of the 27th ACM International Conference on Information and Knowledge Man- agement. CIKM '18. New York, NY, USA: Association for Computing Machinery, Oct. 2018, DOI: 10. 11111/115/22266 3269320.
pp. 1643-1646. ISBN:
[68] Y. Zhang and M. Tang. "Consistency of mandom-walk based network embedding algorithms". In: arXiv:2101 07354 [cs, stat] (Jan. 2021). arXiv: 2101.07354.
[69] B. Zhou, X. Meng, and H. E. Stanley. "Power-law distribution of degree-degree distance: A better representation of the scale-freg property of complex networks". In: Proceedings of the National Academy of Sciences 1 117.26 (June 2020). Publisher: Proceedings of the National Academy of Sciences, pp. 14812-1481 11112--1888 18.
DO1: 10. 1073///as...... 1918901117.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
14

---

(b) Did you describe the limitations of your work? [Yes] See the first paragraph in the related works section; Remark the paragraph between Theorem 3 and 4; the conclusion; Remark 6 in the appendix re: our rates of convergence.
(c) Did you discuss any potential negative societal impacts of your work? [No] The paper discusses the theoretical effects particular type of regularization scheme, and does not advocate for any methodological changes or gives particular applications; I believe that making any types of claims about the societal impacts of this work would be excessively speculative, to be frank.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to ips CabblicEEticsGullee ines).
them? [Yes] Yes
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section and the relevant theorem statements; the one theorem in the main body which does not state them fully (Theorem 2) mentions the corresponding version of the theorem the appendix (Theorem 7) which has the full regularity conditions.
(b) Did you include complete proofs of all theoretical results? [Yes] See the appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or a URL.)? [Yes) See Appendix G.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and Appendix G.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Table 1 and Figure 2.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix G.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets... (a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4.1 and Appendix G.
(b) Did you mention the license of the assets? [Yes] See Appendix G.
(c) Did you include any new assets either in the supplemental material or as URL? [N/A] new assets were created.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] Standard datasets were used, which do not contain information
about/curated from individuals.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Datsets used were standard citation network datasets with no identifiable/textual information provided.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] No crowdsourcing/hune
subjects were used.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] No crowdsourcing/huuan subjects were used.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] No crowdsourcinghhuman subjects were used.
15


Reviews:
[{"review_id": "fDjp7xD62XB", "reviewer": "Reviewer_Bk2Z", "summary": "This work studies the effects of adding a l2-penalty of the embedding vectors to the training loss of network embedding methods. Mainly, the work gives guarantees on the asymptotic distribution of learned embedding vectors under certain assumptions. Particularly, when the embedding vectors are sampled i.i.d from some latent distribution, the distribution of adjacency matrices arise from a probabilistic model characterized by a graphon. Riding on this assumption, the authors work with the population versions of the empirical risk function and give guarantees for a unique minimizer for the regularized population risk in the large sample limit.", "questions": "It is not clear why an exchangeable graph model and consequently an underlying graphon process for graph generation is a valid starting point. There is not enough motivation in the paper behind this critical assumption. \n\nFurther analysis on the role of the sparsifying sequence rho needs to be provided. As the graphon implicitly gives rise to dense graphs, different choices of rho might be influential to model different types of graphs. An analysis relevant to the experimental datasets chosen is lacking. \n\nTheorems 1-5 are very interesting and concisely derived. They show that working with population versions is a promising line of enquiry and even simple prior distributions on the embeddings gives rise to very interesting asymptotic dynamics.\n\nMotivation behind assumption 2 is opaque. It is not perfectly clear to me why this assumption is important and how it helps in arriving at results seen in theorem 1-5. \n\nMore details about the relationship between the assumptions in the paper and the network datasets chosen for experimental validation are warranted. These details are currently missing in the experimental results section.\n\nNotes: \n\nEq 1: \\langle is not defined.\n\n31: N and \\mathcal{N} are mixed up. This occurs many times. Same with P and \\mathcal{P}. \n\n\"Correct population version\": This is not a precise statement; define \"population version\".\n\n133: Assumption not explained.     \n\n168: \"a discussion of the rates give\".\n\nEq 4: a_uv is not defined. ", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has interesting theoretical results and insightful application of graph theoretical concepts to asymptotic analysis of network embeddings. Theorems have very interesting results and are concisely derived. The paper lacks a clear explanation for the motivation behind the assumptions and impact of the assumptions on the experimental datasets of choice and real world datasets in general. Overall, this work is an interesting line of enquiry and might spur additional investigations along similar lines.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VM2ULLaoCoD", "reviewer": "Reviewer_xqKB", "summary": "This paper studies the effects of adding an $\\ell_2$ regularizer to classic unsupervised network embedding objectives. This paper analyzes the asymptotic distribution of the embedding vectors learned through such schemes, and showed that the regularization helps to reduce the effective dimensionality of the learned embeddings. This method is simple and effective, and achieves good performance on the citation datasets. In summary, the theoretical analysis of the paper is well presented. The motivations and the authors' insights to this model is well explained. But the experimental part is weak.  It would be nice to have more experiments on versatile and larger datasets.", "questions": "$\\ell_2$ regularization  is a common operation and the overall enhancement regarding to accuracy over baselines seems very marginal, which makes the whole novelty a little weaker.  It is better for the authors to provide more experiment to demonstrate the advantages of this method, such as extend $\\ell_2$ regularization to other network embedding.", "limitations": "I don't see any potential negative societal impact.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. Provide some theoretical insights on a simple and commonly used approach.\n2. Reasonable motivation.\n\n\n**Weaknesses**\n1. The theoretical results might be useful, but the asymptotical analyses build on many assumptions, which makes the theory less practical. Moreover, the paper is dense, and it is easy to get lost in the very technical definitions and derivations. The paper advocates $\\ell_2$ regularization is good, which is well-known empirically, but the theoretical \"take away message\" is not quite clear based on the presentation.\n2. In the experimental part, this article only tests the performance on Cora, Citeseer and Pubmed. These datasets are old and small-scale. I suggest that the author test on large datasets such as Flickr, Reddit and Arxiv. On the other hand, it would be more convincing to use more unsupervised models such as VGAE，MVGRL as baseline models.  ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OIOeI09K1zl", "reviewer": "Reviewer_XosH", "summary": "This paper proposes to study from both a practical and theoretical perspective, node embeddings methods whose embeddings are regularized with an $\\ell_2$ loss. In particular, the authors propose considering here node embedding methods that, given a graph, embed the nodes in Euclidian space, typically by minimizing a loss over small batches/ subgraphs (eg Node2vec, deepwalk).  The authors show that this corresponds to trying to learn the underlying graphon and latent representations, ie, the function W  and latent representations  $\\lambda_u$ such that:\n$$  \\lambda_u \\sim \\text{Unif}([0,1]), \\quad a_{uv} | \\lambda_u, \\lambda_v \\sim \\text{Bernouilli}(W(\\lambda_u, \\lambda_v))$$\nSince this only yields dense graph (Aldous Hoover theorem), this requires to be sparsified, and consider $\\rho_n W$ where $\\rho_n \\to 0$.\nThe authors note that if we assume the embeddings here (called $\\omega_i$)  to be Gaussian, then this is equivalent to adding a Gaussian penalty in the reconstruction of the objective function, and the embedding reconstruction can be interpreted as matching a graphon kernel:\n$$ \\frac{1}{n^2}  \\sum_{ij} (<\\omega_i, \\omega_j> - K(\\lambda_i, \\lambda_j))^2 = o_p(1)$$\nwhere $K :[0,1]^2 \\to [0,1]$. \n\nThe authors then show that the minimum of the population estimates for their risk function should converge to the same as for the risk function;  The paper then details the procedure that the authors suggest to estimate the embeddings: in particular, they suggest a couple of sampling schemes that are aligned with the assumptions that the authors made in the derivations of their theorems.\nOn the practical/experiments side, the authors show that concatenating their purely structural embedding with node features yields better performance than GNNs.", "questions": "NA", "limitations": " These approaches are purely structural: the node features are considered independently of the graph structure. Graphons are further not suitable to the modeling of a number of real-life graphs, including power laws.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- this is a solid paper, that attempts to shed light into the mechanisms underpinning node embeddings. The authors' method is interesting, as it draws ties behind (what we could perhaps qualified as \"heuristics-based\") approaches in ML and the extensive non-parametric literature on graphon estimation. Tying the two together, and including an $\\ell_2$ regularisation as a prior on the embedding is a nice way of drawing the two pieces of literature together.\nThe paper makes a nice theoretical analysis of structural embeddings --- which can then be added to node features for classification --- and shows good performance in their experiments.\n\n\nLimitations:\n- These approaches are purely structural: the node features are considered independently of the graph structure.\n\n\n\nTypos:\n-l2: \"begin\" instead of \"begins\"", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KzyYtEQO4E", "reviewer": "Reviewer_ocw3", "summary": "The authors start with background on skip-gram node embedding methods like DeepWalk and node2vec, then review some prior theoretical work on guarantees for embedding methods. They then establish some fairly strong assumptions for the following analysis. The bulk of the paper concerns establishing new guarantees for embedding methods, improving on prior guarantees by additionally handling $\\ell_2$ regularization, which is commonly used and known to increase performance; other theory work includes partially justifying the assumptions by showing that common sampling schemes for embedding methods satisfy some of them. Finally, some experiments on real-world datasets establish that 1) there is a sweet spot of regularization strength for best performance of node2vec on downstream tasks; 2) performance is generally improved by concatenating node features to embeddings; and 3) performance is often competitive with deep methods.", "questions": "I am not familiar with the \"Asymptotics of Network Embeddings Learned via Subsampling\" paper, which is cited here as studying a similar non-convex setting with $d \\ll n$, but without regularization. The authors note some similarities in the analyses, but I cannot judge the extent to which the theory work here is original. Some discussion of how the regularization requires new proof steps/techniques may be of interest.\n\nThe setting here seems to concern methods where a single embedding vector is produced per node, and the probability of an edge between two nodes increases monotonically with the dot product of their embeddings. Limitations of this setting have been discussed previously (\"The impossibility of low-rank representations for triangle-rich complex networks,\" \"Node Embeddings and Exact Low-Rank Representations of Complex Networks,\" among others). DeepWalk and node2vec themselves produce two embeddings per node (\"word\" and \"context\" embeddings, per word2vec's terminology), though they may discard one or aggregate them in the end. Do the authors have any comment on how this affects the analysis, and whether extensions to the two-embedding / non-PSD setting are possible?\n\nMinor comments:\n+ Line 31: uses $N$ for negative sampling function, while Equation 1 uses $\\mathcal{N}$\n+ Line 40: same as above\n+ \"e.g\" vs \"e.g.\" (not necessarily a mistake, but NeurIPS seems to use the latter, e.g., in the checklist instructions)\n+ \"node covariates\" and \"node features\" are both used interchangeably throughout the paper; I rarely see the former, so sticking to the latter may improve clarity\n+ a graphical legend for Figure 2 would improve readability a bit, though the caption and trends in the plot are clear enough as is\n+ Is $n$ used both for the number of nodes and indexing the sequence of graphs/graphons? If so, it is likely worth changing one for clarity (perhaps $t$?).", "limitations": "The others note some limitations of their work in the conclusion, including certain strong assumptions required for the proof, which seems sufficient. They decline to discuss potential negative societal impacts given the theoretical nature of the work, saying that it would be excessively speculative. Though some generic discussion of potential impacts seems possible based on the NeurIPS guidelines, their viewpoint is understandable.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The writing is well-structured and grammatical, if a bit dense, though that may be inevitable given the technicality of this work.\n+ The work advances theory for node embeddings learned with regularization, for which better theoretical understanding is of great interest to graph machine learning.\n+ Though I did not go through the extensive appendix or even understand all parts of the main paper, the parts that I did understand generally seem sound.\n\nWeaknesses\n+ As the authors note, the assumptions required for the proofs are quite strong and preclude some common characteristics of real-world graphs.\n\nNotes (Neutral)\n+ The paper is quite technical and assumes a lot of prior knowledge. If accepted, it would increase the reach of the paper if the extra page were used to add some background/intuition on exchangeability, graphons, etc. and how they are used in the assumptions/proofs, perhaps using the specific case of SBMs (which does seem to arise in the appendix) for a concrete example.\n+ It is difficult for me to judge the originality of the work, as I discuss in the Questions section.\n+ The empirical section does not seem particularly original or specific to the main work of this paper; it is generally the case that there will be some sweet spot of regularization strength for downstream performance. It would be more interesting if an experiment somehow validated or demonstrated the theoretical findings.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept