Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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:
$$  \lambda_u \sim \text{Unif}([0,1]), \quad a_{uv} | \lambda_u, \lambda_v \sim \text{Bernouilli}(W(\lambda_u, \lambda_v))$$
Since this only yields dense graph (Aldous Hoover theorem), this requires to be sparsified, and consider $\rho_n W$ where $\rho_n \to 0$.
The 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:
$$ \frac{1}{n^2}  \sum_{ij} (<\omega_i, \omega_j> - K(\lambda_i, \lambda_j))^2 = o_p(1)$$
where $K :[0,1]^2 \to [0,1]$. 

The 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.
On the practical/experiments side, the authors show that concatenating their purely structural embedding with node features yields better performance than GNNs.
strengths_and_weaknesses: Strengths:
- 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.
The 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.


Limitations:
- These approaches are purely structural: the node features are considered independently of the graph structure.



Typos:
-l2: "begin" instead of "begins"
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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: **Strengths:**

1. Provide some theoretical insights on a simple and commonly used approach.
2. Reasonable motivation.


**Weaknesses**
1. 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.
2. 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.  
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.




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. 

Further 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. 

Theorems 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.

Motivation 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. 

More 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.

Notes: 

Eq 1: \langle is not defined.

31: N and \mathcal{N} are mixed up. This occurs many times. Same with P and \mathcal{P}. 

"Correct population version": This is not a precise statement; define "population version".

133: Assumption not explained.     

168: "a discussion of the rates give".

Eq 4: a_uv is not defined. 
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths
+ The writing is well-structured and grammatical, if a bit dense, though that may be inevitable given the technicality of this work.
+ The work advances theory for node embeddings learned with regularization, for which better theoretical understanding is of great interest to graph machine learning.
+ 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.

Weaknesses
+ As the authors note, the assumptions required for the proofs are quite strong and preclude some common characteristics of real-world graphs.

Notes (Neutral)
+ 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.
+ It is difficult for me to judge the originality of the work, as I discuss in the Questions section.
+ 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.
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.

The 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?

Minor comments:
+ Line 31: uses $N$ for negative sampling function, while Equation 1 uses $\mathcal{N}$
+ Line 40: same as above
+ "e.g" vs "e.g." (not necessarily a mistake, but NeurIPS seems to use the latter, e.g., in the checklist instructions)
+ "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
+ a graphical legend for Figure 2 would improve readability a bit, though the caption and trends in the plot are clear enough as is
+ 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.
review_title: null

Meta-review: metareview: Overall, reviews on this paper are universally positive. The paper presents an interesting theoretical analysis of l_2 regularized node embeddings via an asymptotic graphon model based approach. The reviewers find this approach interesting, and hopefully the techniques will be valuable in further theoretical progress on understanding node embedding algorithms.

The paper does have some weaknesses, including a somewhat lacking empirical validation and experiments that don't clearly confirm or complement the theoretical insights. The paper could also do a better job contextualizing the main theoretical insight, which seems to be that regularization can be used to control effect dimensionality of the node embeddings. As discussed, connecting this high level conclusion to prior work on analysis of node embeddings as matrix factorization would be valuable.

The reviewers gave helpful feedback on many aspects of the paper and the authors have agreed to include much of this feedback in a revised draft. I hope that the authors will do so, as it will strengthen the presentation significantly. 
confidence: Certain
Decision: Accept