Source
Hashimoto, Alvarez-Melis and Jaakkola (2016), LIT-1801, §4.1 (Lemma 1, p. 277), Appendix A (Corollary 6 and proof, pp. 282–283) and Appendix B (Lemma 7, p. 283); read in NOTE-1329.
What was actually shown
The model. Points xᵢ drawn i.i.d. from a density bounded below on a compact Riemannian manifold; a spatial graph with an edge i → j present with probability h(ρ(xᵢ, xⱼ)²/σn(xᵢ)²), h piecewise continuous with sub-Gaussian tails (Definition 2, p. 282); a simple random walk on it, read as a corpus. In the main text, eq. (1): P(Xt = j | Xt−1 = i) = h(‖xᵢ − xⱼ‖²/σ).
The result. “if we consider co-occurrences over a sufficiently large window, the log co-occurrence instead converges to −‖xi − xj‖²/σ, i.e. it directly relates to the underlying metric” (p. 277). Precisely (Corollary 6): for any δ, γ, n₀ there are t̂, n > n₀ and terms bⱼⁿ such that, with probability at least 1 − γ, |−t̂ log P(walk at xⱼ after t̂gn⁻² steps | start at xᵢ) − t̂bⱼⁿ − ρσ(xᵢ, xⱼ)²| ≤ δ uniformly over pairs. The proof joins three results: the walk converges to an Itô diffusion (Theorem 3, from the authors’ earlier work), its marginal densities converge (Lemma 4), and Varadhan’s formula gives −t log p_t(x, y) → ρ(x, y)² as t → 0 (Theorem 5). The link function h drops out: “for this reason, we do not need to know the link function h” (p. 277).
What it gives an embedding. Under exact recovery of −log Cᵢⱼ up to per-word terms, the true coordinates are a global optimum of GloVe’s weighted MDS objective, and the PMI matrix tends to ⟨xᵢ, xⱼ⟩ so that SVD (or classical MDS, after centring) recovers the coordinates “under the same equivalence class”, up to an orthogonal map (Lemma 7, p. 283). Distances are the invariants; coordinates are fixed up to isometry and the per-word terms are not identified.
My check. 1,500 uniform points in the unit square, an unweighted ε-ball graph (ε = 0.08), exact t-step transition matrices (numpy). Fitting −log Pᵗᵢⱼ = c‖xᵢ − xⱼ‖² + aᵢ + bⱼ over pairs closer than 0.3 explained 0% of the variance at t = 1, 94% at t = 4 and t = 8 (slopes 98 and 41, roughly ∝ 1/t), and 75% at t = 40, when the walk spans the square. The step kernel was a box, so the quadratic form is not in h; it appears with steps and fades with mixing, as the corollary’s small-t̂ limit says.
What could have failed. The log co-occurrence could have kept the shape of h at every window, or converged to something other than squared distance. The proof excludes both under its conditions, and the simulation shows the box kernel’s flat profile replaced by a quadratic one.
What this does not say
- That language is such a random walk. “it is not intended as a model of language but rather as a tool to understand the recovery problem” (p. 277), and the model “ignores the role of syntax and function words” (n. 4).
- That it holds at practical windows. The theorem needs a window that grows with the vocabulary and a small rescaled time t̂; the paper’s experiments use a window of 5 (Appendix C).
- That it holds for directed graphs unconditionally. Uniform equicontinuity of the marginals is known for undirected spatial graphs; “for directed graphs it is an open conjecture” (n. 10, p. 282). A k-nearest-neighbour graph is directed.
- That word2vec’s minimizers converge to the true embedding. Theorem 8 shows only that the objective value at the truth approaches the global minimum (p. 284).
- That the recovered distance is Euclidean. It is the geodesic ρσ under the local scale σ, which equals ‖xᵢ − xⱼ‖ only on a flat space with constant σ, as in Lemma 1’s statement.
- That a spectral embedding of the co-occurrences themselves recovers the metric. The result concerns their logarithm; factorizing the kernel matrix instead gives its eigenfunctions (THEORY-183).