Why Don’t You Take a Walk? Ranking and Risk With Walk Averaging

Random walks can improve link prediction in network embeddings without adding information to the observed graph. We study when this occurs at fixed embedding width. In a degree-corrected graphon model, we derive conditions for walk averaging to improve ranking or probability loss. The conditions depend on the interaction between retained and omitted structure, with different weights for the two metrics. Under weak contrast and a separated rank cutoff, we identify the bounded, rank-constrained skip-gram with negative sampling (SGNS) optimum and apply the metric criteria to its decoded predictions. We also characterize the probability error removable by monotone calibration. Population calculations recover the predicted regimes. On sampled graphs, optimization of the expected SGNS objective reproduces opposite ranking responses in a controlled setting, but the smaller gain is not recovered with a finite sampled corpus. Real-network results motivate the analysis but do not establish a window-selection rule.