Summary
Theoretical results showing the consistency of node2vec embedding for community detection in SBMs and DCSBMs using k-means clustering. Versions of this problem have been approached in other work, for example, node2vec rephrased as a matrix factorisation problem [39], and rank $d$ approximations for DeepWalk [51]. This paper addresses the issues in previous works relating to approximations made within previous work, such as an Frobenius norm approximation to the cross-entropy loss, at the cost of weaker consistency results, $\ell^2$-norm as opposed to two-to-infinity norm.
Strengths
The strength and novelty of this work lies in the technical results in the Appendix. The paper would be better served with this material given more attention, perhaps in a journal rather than conference paper. However, I was unable to give the material in the Appendix a full read through, so I am working under the assumption that these results are technically sound. More clarity would be needed to show how the results differ from previous work (see below).
There are some important insights about the use of node2vec for node clustering in different types of SBM and DCSBM. For example, setting $U = V$ in constrained DeepWalk where $p \le q$ is unable to cope with disassortitive (DC)SBMs. This feels like a significant issue and I would be interested to learn more why random walk based embedding algorithms fail on bipartite-like networks. It is also interesting that node2vec on DCSBMs produce clusters that only depend on the SBM community and that the degree parameters $\theta$ are unimportant. Being able to perform k-means clustering directly on the node2vec embedding is an advantage over, say, spectral methods where hyperplane or spherical projection is required to remove the effect of $\theta$ from the embeddings.
Weaknesses
Without delving too deeply into the mathematics in the Appendix, it is not obvious to me how this paper extends the results in [10] and [11] which only get briefly mentioned on Lines 121-123. These two papers analyse the asymptotic distribution of the node2vec embedding for latent position graph models, a wide range of models which include the SBM and DCSBM. It is not clear how the theoretical results in this paper extend those results, except for looking at the consistency for k-means clustering, which is non-specific to the node2vec embedding stage. I don't want to say that the contribution in this work is 'poor', but it is hard to know what is new here in the current state.
Understanding random walk embedding algorithms is important, but they have been overtaken by graph neural networks designed for this exact problem, rather than ideas shoehorned in from natural language processing.
The experiment shown in Figure 3 is somewhat misleading. I read this plot as showing that k-means clustering is unsuitable for spectral embeddings of DCSBM, like the political blog network, rather than spectral embedding failing.
Questions
The main issue is how do the results here compare to the work of [10] and [11]? Section 1.2 on Related Works describes how this work extends [39] and [51], but the fact that these two strongly relevant papers are only given a brief sentence feels a significant oversight.
What conditions are needed/prevent two-to-infinity norm consistency compared to the $\ell_2$-norm in this setting?
What about other clustering algorithms other that k-means? The results show asymptotically k-means will give the correct clustering, other papers [41] show that there are issues for fixed $n$ which are avoided by other clustering algorithms such as fitting Gaussian mixture models. Practically, any matrix $M$ transformation $U \rightarrow UM$ and $V \rightarrow VM^{-\top}$ is a valid embedding which will affect the k-means clusters.
Similar results for core-periphery SBMs (On a 'two-truths' phenomenon in spectral graph clustering, Priebe et al), another important type of SBM for practical embeddings?
Limitations
Error bars needed in Figures 1 and 2 showing the multiple experiments described in Lines 296-297. Needs comparison to other embedding algorithms, for example, spectral embedding. Misleading experiment given in Figure 3 (see above).