acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph embedding, link prediction, spectral methods, finite-sample analysis, random walks

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_b7jEOpenReview ↗
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
AuthorsOpenReview ↗

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\sqrt{log n / n}. With edge probabilities of order ρn→0\rho_n \rightarrow 0 it becomes logn/(nρn)\sqrt{log n / (n \rho_n)} and at bounded degree it does not go away. The gains we study are of order η2\eta^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!).

Thank you for the readability improvements. I find the theoretical findings interesting and useful to the community, and I have raised my score.

AuthorsOpenReview ↗

response to b7jE

Thank you for reading the revision and for raising your score!

Reviewer_qx33OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks when replacing one-step edge pairs (LINE) by random-walk co-occurrence pairs (DeepWalk) improves link prediction at a fixed embedding width, given that a walk reveals no new edges. It works in a degree-corrected graphon Bη=B0(1+ηk)B_\eta = B_0(1+\eta k) with B0=v w⊗wB_0 = v\,w\otimes w and weak contrast η↓0\eta \downarrow 0. Walking with lag law ω\omega replaces kk by ∑ℓωℓηℓ−1Kℓ\sum_\ell \omega_\ell \eta^{\ell-1} K^\ell, which to first order simply scales the retained spectral component ff by ω1=1−t\omega_1 = 1-t. Theorem 1 expands the change in NLL and AUC as η22(t2A+2tC)\frac{\eta^2}{2}(t^2 A + 2tC) with metric-specific coefficients: AA measures retained structure, CC the interaction between retained and omitted structure, weighted by Z/(1−Z)Z/(1-Z) for NLL and by degree-conditional covariances for AUC. Walking helps iff C<−tA/2C < -tA/2; the two metrics can disagree. Proposition 1 characterizes what a monotone scalar calibration removes. Theorem 2 identifies the unique bounded rank-dd population SGNS optimum under spectral separation and shows it satisfies the first-order form, with an explicit second-order term separating walk composition from constrained logistic fitting. Theorem 3 transfers population sign comparisons to sampled fits under dense sampling and optimization success. Experiments: population quadrature checks match predicted coefficients to a few percent (72/72 signs); sampled dense graphs (n≤3200n\le3200, width 2) recover the negative AUC direction robustly and the positive one weakly (11% of population magnitude, not with a finite corpus); nine small real networks show both directions and metric disagreement, which the authors explicitly say does not establish a window-selection rule.

Critical strengths

A sharp, well-posed question with a clean answer. Separating “which pairs are represented” (walk) from “how well they can be represented” (width) is the right decomposition, and the finding that walking acts, to leading order, as shrinkage of the retained component whose benefit depends on the sign of a retained–omitted covariance is a genuinely clarifying picture.

Theorem 2 is a real contribution. Davison & Austern prove existence of rank-constrained population minimizers; this paper identifies the minimizer in closed form (to second order) for a nontrivial family, including a moving subspace, and certifies global optimality with a quadratic gap.

Metric dependence is made explicit. Showing that AUC, native NLL, and calibrated NLL have different break-even points (0.139 / 0.018 / 0.051 in the example) and why (different weightings of the same error) is a useful corrective to “walking helps” folklore.

Critical weaknesses
  1. The analyzed regime removes the mechanism that makes walking interesting. At weak contrast, ηℓKℓ\eta^\ell K^\ell for ℓ≥2\ell\ge2 is higher order, so walking reduces to multiplying every retained eigenvalue by the same scalar ω1\omega_1. The classic reason walking helps — polynomial reweighting λ↦∑ℓωℓλℓ\lambda\mapsto\sum_\ell\omega_\ell\lambda^\ell that amplifies dominant modes and suppresses weak ones (the low-pass-filter view underlying NetMF/InfiniteWalk) — is absent to leading order. The paper proves things about a regime in which “walking” is indistinguishable from a temperature parameter on the logit. That is a legitimate limiting case, but it is far from DeepWalk as used.

  2. Consequently, a trivial control is missing. If walking’s first-order effect is f↦(1−t)ff\mapsto(1-t)f, then one-step training followed by scaling the non-constant part of the score by (1−t)(1-t) should achieve the same NLL/AUC change at a fraction of the cost. The paper’s own Propositions B.1/B.2 show that at constant degrees an affine or power rescaling makes windows equivalent to O(η4)O(\eta^4). The natural conclusion — “in this regime, walking is a clumsy way to shrink” — is never stated, and no experiment compares walking against optimally shrunk one-step scores. Without this, the practical content of Theorem 1 is unclear.

  3. The effects are tiny by construction and vanish with width. All metric differences are O(η2)O(\eta^2); in Table 1 they are 10−410^{-4} in AUC at η=5⋅10−4\eta=5\cdot10^{-4}, and 10−410^{-4} on sampled graphs at η=0.3\eta=0.3. The benefit exists only through the omitted component rr, which shrinks as width grows; at practical widths (64–128) on graphs with a handful of strong modes, rr is negligible and the theory predicts walking does nothing. The paper should state explicitly what it predicts for realistic widths.

  4. Empirical support for transfer is weak and the experimental regime is unrealistic. Sampled graphs have mean degree ~192 at n=3200n=3200 (dense) and width 2. Even there, the positive AUC direction for graphon C is recovered at 11% of its population magnitude, fails at t=0.2t=0.2, fails at η=0.4\eta=0.4, and fails entirely with a 2M-pair corpus (0/8 at t=0.2t=0.2). Theorem 3 requires N/[nlog⁡(nN)]→∞N/[n\log(nN)]\to\infty independent trajectories, continuous kernels (violated by the block generator used), and optimization within oP(1)o_P(1) of the optimum. Sparse graphs — where DeepWalk is actually used and where Zhang & Tang show walks help via estimation — are explicitly outside scope.

Questions for authors

In the weak-contrast regime, is walking equivalent to scaling the non-constant part of the one-step logit by 1−t1-t? If so, please add a control: one-step SGNS followed by the best scalar shrinkage (or temperature), and report whether walking ever beats it on NLL or AUC in the population or sampled experiments.

What does the theory predict for realistic widths (e.g., d=64d=64) when the omitted spectrum is small? Does the benefit of walking vanish as O(∥r∥2)O(\|r\|^2)?

Can C/AC/A, or equivalently t∗t^*, be estimated from the observed graph (e.g., by a wider auxiliary fit providing a proxy for rr)? This would turn Theorem 1 into a window-selection rule and connect to Watch Your Step.

At finite contrast the eigenvalue polynomial ∑ℓωℓ(ηλ)ℓ\sum_\ell\omega_\ell(\eta\lambda)^\ell reweights modes non-uniformly. Does the sign criterion survive when ηλj\eta\lambda_j is not small, and can the failures at η=0.4\eta=0.4 be attributed to the score cap versus the breakdown of the expansion?

6 comments
AuthorsOpenReview ↗

Response to reviewer 2

Thank you for your review. This review made me think a lot and changed the paper the most. You’re right on the main point: with varying degrees, walking is a rescaling of the one-step score to the order of Theorem 1. I’ve added this to the abstract and prove it as Corollary 2. I also agree with W3 and W4 as written. The effects are O(η2\eta^2) by construction. They vanish once the width covers the spectrum: the new Proposition A.2 bounds the leading gain by η2\eta^2 times the sum of squared omitted eigenvalues. And the transfer experiments are dense, width two, and only partly successful. I’ve added a note so that Section 4.3 now says where density enters. The control you asked for (one-step plus the best rescaling, against walking) I’m going to set up shortly, and we will post it when we have it ready.

  • W1, W2, Q1 To first order, yes you’re right here. This is in Corollary 2(i), and a rescaled one-step score would reproduce Table 1 and Figure 1. At second order the two scores differ by η2ω2F2+ω1t,SK(Mb)\eta^2{\omega_2\mathsf F^2+\omega_1 t,\mathcal S_K(M_b)}. With varying degrees this is below the order of Theorem 1. With constant degrees it is the leading ranking term, because no rescaling can change the one-step ranking there. Appendix A.4.1 that I’ve added has a working example you might find helpful. What Theorem 1 still tells you is how much shrinkage each metric wants, −C/A, and that AUC and NLL disagree about it. I think this now-stated equivalence that you’ve helped us with sharpens the result: it reduces “when does walking help at fixed width” to one number per metric, −C/A, proved at the global optimum of the trained objective and not for a spectral surrogate, and it shows that AUC and NLL want different amounts of it, which Table 1 confirms to a few percent. So for this reason I really appreciated your comments.

  • Q2 (realistic widths). If the width covers every nonzero residual mode, the theory predicts no leading effect from walking; otherwise the effect is bounded by the omitted tail. Whether the tail beyond d = 64–128 matters on a real graph is an empirical question that I don’t really think is in scope for this paper. The remainders in Theorem 1 are not uniform in the width, so this holds at each fixed width.

  • Q3 (estimating C/A). We haven’t tried this, but our existing theory says something about it. By (29), 1 + C/A is the regression coefficient of k on f in the metric’s quadratic form. So at leading order, choosing t amounts to tuning one scalar on the one-step logit, which can be done on held-out pairs without estimating r. This also bears on Watch Your Step, which learns the lag weights against the training objective: Theorem 1 says the best weights depend on the evaluation metric, so one learned distribution cannot be best for both AUC and NLL when their break-even points differ, as they do in Figure 1. We haven’t tested the held-out tuning and don’t claim a selection rule but I’m going to try to play around with this in the next few days and get back to you.

  • Q4 (finite contrast). In the population, the direction found at η = .3 persists at η = .4: graphon C still gains AUC at t = .05, .10 and .20 (Table 6). We have not compared it with the sign of the asymptotic coefficient. What fails is transfer to sampled graphs. We can’t blame the cap alone. At .4 the population optimum sits on it (Table 4), but the gain is also two to four times smaller, and the expansion is further from its regime.

Thank you for the thorough response and for the substantive revisions.

On the equivalence (W1/W2/Q1). Corollary 2 settles the question I raised, and Proposition A.2’s bound — walking recovers at most a fraction ρM2\rho_M^2 of the one-step regret, itself bounded by η2∑omittedλj2\eta^2\sum_{\text{omitted}}\lambda_j^2 — is a clean statement of what the width leaves on the table. I’d note that the paper’s practical conclusion is now a negative one: at weak contrast with varying degrees, one-step training plus a single metric-specific temperature, tuned on held-out pairs, achieves everything walking achieves at leading order. That is a useful result and I would encourage the authors to say it this directly in the introduction rather than only in the abstract.

On the constant-degree example (A.4.1). This is a nice addition, but I want to make sure its implication is stated. The authors show that the O(η2)O(\eta^2) AUC change there is “not specific to walks”: replacing a fraction tt of pairs by random pairs gives the same effect, so it is a consequence of fitting at reduced contrast ω1η\omega_1\eta, not of walking. The only genuinely walk-specific term is ω2F2\omega_2 F^2, which reweights each retained mode by its own eigenvalue and matters only when two retained eigenvalues differ. This is precisely the mode-reweighting mechanism behind the usual “walks as a spectral filter” intuition, and the revision isolates it without analyzing it. Could the authors provide, even numerically, a two-retained-mode example with λ1≠λ2\lambda_1\neq\lambda_2 where the ω2F2\omega_2F^2 term determines the sign of the AUC change? That would be the first result in the paper about walking per se, as opposed to shrinkage.

On the promised experiments (Q1 control, Q3 held-out tuning). By Corollary 2(i) the control will reproduce Table 1 on the population grid, so its value is on the sampled graphs: does one-step plus the best rescaling match or beat walking at n=3200n=3200, and in particular does it recover the graphon-C gain that walking recovers only at 11% magnitude? Similarly, the held-out tuning of tt (or β\beta) is the one experiment that would make the theory actionable.

On Q2 and Q4. I accept the responses. The statement that remainders are not uniform in the width is an appropriate caveat. Also, the revised paper is more honest and sharper than the original, and its mathematics is sound.

AuthorsOpenReview ↗

response to qx33

Thank you for the follow-up. So, in short and see my revision and more below, rescaling the one-step score recovers the graphon-C gain that walking mostly loses, and a temperature tuned on held-out labels does better than the best walk on AUC. I also built the two-mode example you asked for, see later in this reply. The sampled-graph experiments are at eta = .3, n = 3200, width two, on the eight graphs per graphon of Table 2, with AUC and NLL changes ×1e4 against edge probabilities. The full tables are in the appendix of the revision (E.2 and A.4.2).

On rescaling control: as you said, at the contrast of Table 1 the rescaled score just reproduces the table, so the sampled graphs are where it gets interesting in this paper. There, rescaling the one-step fit gives graphon C a positive AUC change on every draw at all three t, and a much larger one than walking gets (Table 11; at t = .05 it is +2.65 against +0.45). At t = .20 walking has the wrong sign and rescaling still has the right one. For D both lose AUC, as predicted. What I can't explain is why, for C, walking loses most of its population gain and rescaling doesn't. For D the two behave about the same.

On NLL neither approach appears to helps. Walking makes it worse on every draw and a mild rescaling barely moves it.

Now, on held-out tuning, I played around with this this week and it works. I picked beta by AUC on the labels of an independent graph on the same nodes (the calibration draw from Section 5.2), and it ends up being really close to the beta I would have picked knowing the true probabilities, for both graphons. For C the tuned score gains several times more than the best walk. For D the tuned beta comes out above one, so it sharpens the score and gains AUC. Tuning t the same way does find the best walk I tried, it's just that the best walk doesn't do much (a small gain for C, nothing for D). For NLL there is basically nothing to gain from tuning. Check out the numbers in appendix E.2 that I added.

I agree this should be said in the introduction and not only in the abstract. It is now in the contributions paragraph, pretty much as you put it.

On two retained modes: I added this (Appendix A.4.2, Table 4), but I see it as a side point rather than the main point of my paper. The paper is about a first-order account, meaning Theorems 1 and 2 and walking as a rescaling of the one-step score, which is what the control above tests. The second-order term only shows up in Proposition A.1, under constant degrees. The example shows this term can decide the sign, so it's more of an exercise but maybe some readers will find it fun, so I put it in the appendix.

Reviewer_KCbUOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies an interesting question in graph representation learning: why and when does training node embeddings on multi-step random walks (such as the DeepWalk) can outperform one-step edge training (the example is LINE) for link prediction, given that walks introduce no new topological information beyond the observed graph? By separating finite-sample estimation benefits from fixed-width approximation effects, the authors analyze the problem in a population degree-corrected graphon model (Bη(x,y)=B0(x,y){1+ηk(x,y)}B_\eta(x,y) = B_0(x,y)\{1 + \eta k(x,y)\}) under a weak-contrast (η→0\eta \to 0) perturbation expansion.

Contributions: (1) (Theorem 1) Metric-Dependent Error Interaction. Walk averaging acts to first order as shrinkage of the retained spectral component, which can improve predictions if it counteracts the error from omitted structure. Because Negative Log-Likelihood (NLL) and AUC weight edge errors differently across node degree baselines, they can favor different walk distributions.

(2) (Proposition 1) Limits of Scalar Calibration. Monotone calibration removes the average error conditioned on baseline edge probabilities, but it cannot fix the within-baseline variance or resolve differing metric preferences.

(3) (Theorems 2 & 3) Exact Rank-Constrained SGNS Optimum: Under weak contrast and separated spectrum, the bounded rank-constrained SGNS optimum matches spectral truncation to first order, with an explicit second-order correction for subspace rotation. These population rankings and risks provably transfer to fits on sampled dense graphs as sampling errors vanish.

Critical strengths

(1) (Theorem 2) Exact Characterization of the Constrained SGNS Optimum. Analyzing rank-constrained non-linear logistic objectives is notoriously difficult because low-rank truncation does not commute with entrywise logarithms. Using a normal-gradient optimality certificate in Lemma 2, the authors can prove rigorously global optimality for bounded rank-dd SGNS. This establishes its first-order equivalence to spectral truncation and deriving the exact second-order subspace rotation.

(2) (Theorem 1 & Proposition 1) Principled Isolation of Fixed-Width Approximation Effects. Rather than attributing the benefit of random walks solely to finite-sample variance reduction, the paper analyzes the population limit to show how walk averaging acts as first-order shrinkage that can offset omitted spectral structure. Showing how μ2\mu^2-orthogonality is broken by distinct ζ2\zeta^2 metric weightings (Z/(1−Z)Z/(1-Z) for NLL vs. equal-baseline conditional covariance for AUC) cleanly explains why walk windows affect ranking and probability calibration differently.

Critical weaknesses

(1) Fragility of the Positive Ranking Regime Under Sampled Corpora. On sampled graphs (Section 5.2), the regime where walking improves AUC (Graphon C) only appears when optimizing the exact expected objective at η=0.3\eta=0.3 (recovering just 11% of the population gain at n=3200n=3200). When using a finite corpus of 2×1062\times 10^6 walk pairs—the actual mechanism of DeepWalk—or increasing contrast to η=0.4\eta=0.4 where the score cap becomes active, the positive ranking gain disappears entirely.

(2) Restrictive Modeling Assumptions. The theory relies on dense graphons, weak residual contrast (η→0\eta \to 0), stationary negative sampling (rather than DeepWalk/word2vec's standard 0.750.75 degree-power smoothing), and a known degree baseline B0B_0 in the decoder. Consequently, the asymptotic theory cannot predict optimal walk windows on sparse, real-world networks where finite-sample estimation effects dominate.

Questions for authors
  1. Symmetrized Readout Rank in Experiments (Appendix E.2 & E.3): In Theorem 2, the optimization and rank constraint d=m+1d = m + 1 apply directly to F=UV⊤F = UV^\top, where the population minimizer is shown to be symmetric. --- However, in the sampled-graph and real-network experiments (lines 1806 and 2047), predictions use the symmetrized score S=(UV⊤+VU⊤)/2S = (UV^\top + VU^\top)/2, which can have rank up to 2d2d. Why was post-hoc symmetrization needed if the population target is symmetric, and does allowing rank up to 2d2d at readout alter the effective omitted residual rr in the sampled experiments?

  2. Sampled Corpus Budget on Graphon C (Section 5.2): In Table 2 / Table 8, training on a 2×1062 \times 10^6-pair corpus fails to recover the +3.97×10−4+3.97 \times 10^{-4} population AUC gain for Graphon C at n=3200n=3200 (which has ≈5.1×106\approx 5.1 \times 10^6 unordered pairs). Since 2×1062 \times 10^6 positive pairs means each node pair is sampled less than 0.4 times on average, the corpus noise is still relatively high compared to the O(10−4)O(10^{-4}) signal. Have the authors tested whether increasing the corpus size NN (e.g., 10710^7 or 5×1075 \times 10^7 pairs) eventually recovers the expected-objective positive sign as predicted by Theorem 3, or is the solver getting trapped in local stationary points on the noisy objective?

2 comments
AuthorsOpenReview ↗

Response to reviewer KCbU

Thank you for the careful review, and for the two helpful questions. I agree with both weaknesses. The positive ranking effect is fragile on sampled graphs, which is why I tried to make these failures clear in the main text. And the assumptions (dense graphs, weak contrast, stationary negatives) are indeed restrictive (but they allow for this interesting angle of analysis!). One small correction: the known baseline B0B_0 is used only in the population results. Theorem 3 and the sampled experiments use observed degrees.

  • Q1 (symmetrized readout). Under Theorem 2 the minimizer is already symmetric, so symmetrizing changes nothing there. The experiments run at contrast .3 and .4 with independent factors U and V, where we have no such guarantee. So we symmetrized, and used the same readout for the population reference to keep the comparison like for like. You’re right that if F were noticeably asymmetric, S could pick up part of the omitted structure, but I didn’t check for this. Now I’m be computing ∣∣F−FT∣∣/∣∣F∣∣||F-F^T||/||F|| and the unsymmetrized metrics for all fits and I’ll post them as soon as I get the results.

  • Q2 (corpus budget). We haven’t run larger corpora yet; N = 10⁷ and 10⁸ are running in the background now. There are two things I want to note from the existing tables. First, the fair comparison for a corpus fit is the expected-objective fit on the same graph, and at t = .05 that recovers only +4.5e-5. The corpus draws spread over about 2e-4 (Table 8 )so noise alone could hide it. For what it’s worth, N/[n log(nN)] is only about 28 here, so Theorem 3 promises little at this budget. Second, I’m thinking noise may not be the whole story. For C the corpus means sit below the expected-objective means by 0.7, 1.7 and 2.5 (e-4) at t = .05, .10, .20, and D shows no such trend. So I’m not sure if it’s the solver or the sample and I’ll experiment here.

AuthorsOpenReview ↗

additional expeirmental results for KcBu

Sorry I'm a bit late on following up on experimental results, I was trying to run a few different things for other reviewers as well. The results are with eta = .3, n = 3200, on the graphs of Table 2, and the tables are in Appendix E.2 of the revision.

Q1 (symmetrized readout). For the expected-objective fits it makes no difference. F is symmetric to within 4e-4 there and the readout has rank two like F, so nothing changes when I score F directly. With a finite corpus the results are pretty different. The fitted F is clearly asymmetric (by about a third at two million pairs, down to a few percent at 1e8), and symmetrizing helps AUC. It shrinks as the corpus grows and never shows up in the expected-objective fits, so I think symmetrizing is averaging out corpus noise and not picking up omitted structure. It does mean that the corpus column of Table 2 depends on this and I've added more commentary to the paper to make this more clear. On the five small real networks every comparison keeps its sign without symmetrizing. I haven't rechecked the four larger networks or the eta = .4 fits.

Q2 (corpus budget). It was indeed the budget here. With larger corpora the graphon-C sign comes back at t = .05 and .10, and by 1e8 pairs it is positive on every draw and close to the expected-objective value (Table 10). It does not come back at t = .20, but the expected-objective fit is negative there too, so I don't think that one is a corpus effect.

I don't see any sign of a solver problem. I reran every corpus fit starting from the expected-objective solution, and it ends up in the same place. Both starts could still hit the same bad stationary point, but since the sign also comes back as N grows I think it's the sample. My earlier guess that the solver was part of it looks wrong. I've rewritten the corpus paragraph in Section 5.2 accordingly.

See also my reply to qx33 as it has some commentary relevant to your first weakness. If I rescale the one-step score instead of walking, graphon C gets a positive AUC change on every draw at all three t, and a much larger one than walking gets (Table 11).

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to reviewers

Thank you to all three reviewers. I’ve added a new revised PDF trying to address most of your comments, please let me know what you think, and I’ll respond to you all individually shortly. Here’s what’s new:

  • I’ve rewritten the abstract, introduction, and section 2 a bit, and have tried to make the assumptions easier to parse by explaining them.
  • Corollary 2 (Section 4.2). With varying degrees, rescaling the one-step score by γ1\gamma_1 matches walking to the order of Theorem 1. The two differ at order η2\eta^2, and with constant degrees that difference changes rankings. Appendix A.4.1. I’ve added a worked constant-degree example in which walking changes AUC by η2⋅t⋅4ϵ[45(1−5)]\eta^2 \cdot t \cdot 4\epsilon [45(1-5)]
  • Proposition A.2. The leading gain from walking is bounded by the sum of squared omitted eigenvalues, so it vanishes as the width grows.
  • Section 4.3 now says where the sampling theorem needs dense graphs (and I’ve tried to talk about density a bit more throughout).

I’m still working on experiments and will get back on those!

AuthorsOpenReview ↗

update on experiments

Hi all, I've uploaded a revision with the experiments I previously promised, sorry it took some time to run and verify. The details are in the individual replies.

  • Rescaling the one-step score, instead of walking, recovers the graphon-C AUC gain on the sampled graphs, and a temperature tuned on held-out labels does better than the best walk I tried (thanks qx33 for the relevant comments, and you can see that reply for more details).
  • The graphon-C sign at t = .05 and .10 comes back as the corpus grows, and I found no indications that the solver was the problem. The symmetrized readout only matters for the finite-corpus fits (see my response to KCbU).
  • I built a numerical two-mode example where the lag-two term decides the sign of the AUC change for qx33.
  • On eleven real networks, a rule based on rescaling predicts the direction of the AUC change at small widths and stops working at larger ones on the weakly structured graphs (Appendix E.5), which are both about what we would expect from the theorems.
  • small changes to introduction based on qx33's reply.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.