- Rating
- 3(+1)
- Confidence
- 1
- Informativeness
- 1(−1)
- Presentation
- 2(+1)
- Soundness
- 2
Read review
Paper summary
This paper studies that random walks can still improve link prediction at a fixed embedding width using a degree-corrected graphon model. To leading order, walk averaging shrinks the retained spectral component. Prediction improves if this shrinkage offsets the error from the structure omitted by the width constraint, and worsens otherwise. The resulting conditions differ between AUC and NLL, since the two metrics weight the same error differently (Theorem 1). The paper further show that these criteria apply to the global bounded, rank-constrained SGNS optimum (Theorem 2), and give conditions under which fits on sampled graphs recover this population optimum (Theorem 3).
Critical strengths
[S1] The paper gives a clear theoretical account of when random walks help or hurt link prediction despite adding no new information, and shows that the answer can differ across evaluation metrics.
[S2] The theory extends from a simplified spectral setting to the actual SGNS objective and to sampled graphs, which makes the analysis well-structured and practically relevant.
Critical weaknesses
[W1] The presentation could be improved. The introduction does not clearly contrast the limitations of prior work with the paper’s contributions, and the notation and assumptions are presented very densely with little intuitive explanation, which makes the paper difficult to follow. Adding intuitive examples or explaining what each assumption means would help.
[W2] The sampled-graph theory and the synthetic experiments assume dense graphs, whereas most real-world networks are sparse. The real-network experiments are also not connected to the theoretical coefficients and show mixed results, so the practical applicability of the theory remains unclear.
Questions for authors
Q. The theory is restricted to dense graphs. Could the authors explain which steps of the analysis rely on density, and why the current approach cannot be directly applied to sparse graphs?
3 comments
Thank you for the readability improvements. I find the theoretical findings interesting and useful to the community, and I have raised my score.
response to b7jE
Thank you for reading the revision and for raising your score!
Response to reviewer 3
Thank you for your review and I’m sorry it was hard to read. I can see where you’re coming from and I’ve tried to rewrite the intro / abstract to use less technical language and to explain the introduction of concepts and notation. I’ve also added additional commentary around the assumptions. Could you take a look again, and let me know if anything is unclear, and we can try keep on working on readability.
W2 Agreed on both, I’ve tried to make the density assumption more explicit in the paper. The real-network results are not tied to the coefficients because those need the omitted part r, which can’t be observed on a real graph. They are there to show that both directions occur, and Section 5.3 says they do not give a rule.
Q (which steps need density). My sampling theorem needs it but the fitted score does not: the population objective (18) depends on the graphon only through the co-occurrence ratio (2), which is unchanged if every edge probability is multiplied by the same sparsity factor, so Theorem 2 is unaffected. The metrics also see the sparsity factor. The AUC criterion is invariant to it, but the native-NLL benefit is not: its cross term is of higher order in the factor, so the range of walk mass that improves NLL shrinks as the graph gets sparser.
Theorem 3 is different. It needs the observed degrees and walk weights to concentrate around their population values (Lemma 3). With degrees of order n, the relative error is about logn/n. With edge probabilities of order ρn→0 it becomes logn/(nρn) and at bounded degree it does not go away. The gains we study are of order η2 so on a sparse graph they are swamped. There the main effect of longer walks is on estimation, which is the question Zhang and Tang (2024) study (great paper!).