OctoInformBeta

OpenAI preprint, September 2026 · Section 4. Local walks and entropy

Local kernels, the triangle law and weighted entropy: Directed edges carry neighborhood transitions, lazy smoothing and mean row variation

Local walks combine triangle weights and entropy.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Neighborhood walks study adjacency inside the neighborhood of a fixed vertex. Let GG be a finite simple graph on VV, with a real vertex weight w:V→ℝw:V\to\mathbb R. The neighborhood N(u)N(u) of a vertex uu is its set of adjacent vertices, and the mass w(S)w(S) of a vertex set S⊆VS\subseteq V is its total weight, as in (1): N(u)={v∈V:uv∈E(G)},w(S)=∑v∈Swv.N(u)=\{v\in V:uv\in E(G)\},\qquad w(S)=\sum_{v\in S}w_v.(1) The common neighborhood mass cuvc_{uv} of vertices u,vu,v is the weight of their common neighbors, defined in (2): cuv=w(N(u)∩N(v)).c_{uv}=w\bigl(N(u)\cap N(v)\bigr).(2)✦

The oriented edges of GG are the ordered pairs E→(G)={(u,v)∈V2:uv∈E(G)}\vec E(G)=\{(u,v)\in V^2:uv\in E(G)\}.✦ An oriented edge e=(u,v)e=(u,v) has tail uu and head vv. A kernel KK on a finite state set II is a real matrix indexed by I×II\times I.✦ Write IdI\mathrm{Id}_I for the identity matrix on II. Quotients with zero denominator are taken to be zero. For real arguments, log⁡t\log t means the natural logarithm of |t||t| when t≠0t\ne0, with log⁡0=0\log0=0; zero mass contributes zero to weighted entropy.

The Definition

Definition 1. Let GG be a finite simple graph with real vertex weight ww. The neighborhood transition kernel PP on E→(G)\vec E(G) is the matrix in (3): P((u,v),(u′,z))={wz/cuv,u=u′ and vz∈E(G),0,otherwise.P\bigl((u,v),(u',z)\bigr)= \begin{cases} w_z/c_{uv},&u=u'\text{ and }vz\in E(G),\\ 0,&\text{otherwise}. \end{cases}(3)✦ The local walk normalizer ZZ of a finite simple graph GG with real vertex weight ww is the scalar in (4): Z=∑(u,v)∈E→(G)wuwvcuv.Z=\sum_{(u,v)\in\vec E(G)}w_uw_vc_{uv}.(4)✦ For a finite simple graph GG with real vertex weight ww, the local walk edge law μ\mu is the real weight on E→(G)\vec E(G) given by (5): μ(u,v)=wuwvcuvZ.\mu(u,v)=\frac{w_uw_vc_{uv}}{Z}.(5)✦ For a finite simple graph GG with real vertex weight ww, the destination weight ω\omega is the real weight on E→(G)\vec E(G) given by (6): ω(u,v)=wv.\omega(u,v)=w_v.(6)✦

Let KK be a kernel on a finite set II. The lazy kernel L(K)L(K) of a kernel KK on a finite state set II is the matrix on I×II\times I in (7): L(K)=IdI+K2.L(K)=\frac{\mathrm{Id}_I+K}{2}.(7)✦ For a kernel KK on a finite state set II and an integer j≥0j\ge0, the smoothed kernel Sj(K)S_j(K) is the jjth power of the average of KK and the identity kernel. Sj(K)=KL(K)j.S_j(K)=K\,L(K)^j.(8)✦

For real weights η,p\eta,p on a finite state set II, the weighted entropy Hη(p)H_\eta(p) is the scalar in (9): Hη(p)=∑i∈Ip(i)log⁡η(i)p(i).H_\eta(p)=\sum_{i\in I}p(i)\log\frac{\eta(i)}{p(i)}.(9)✦ For a kernel KK and real weights π,η\pi,\eta on a finite state set II, the average row entropy ℋπ,η(K)\mathcal H_{\pi,\eta}(K) is the scalar given by the weighted sum in (10): ℋπ,η(K)=∑i∈Iπ(i)Hη(K(i,⋅)).\mathcal H_{\pi,\eta}(K) =\sum_{i\in I}\pi(i)H_\eta\bigl(K(i,\cdot)\bigr).(10)✦ The total variation distance TV⁡(p,q)\operatorname{TV}(p,q) of real weights p,qp,q on a finite state set II is the scalar in (11): TV⁡(p,q)=12∑i∈I|p(i)−q(i)|.\operatorname{TV}(p,q)=\frac12\sum_{i\in I}|p(i)-q(i)|.(11)✦ For a finite simple graph GG with real vertex weight ww and an integer n≥0n\ge0, the mean row variation DnD_n of its neighborhood walk is the scalar in (12): Dn=∑e∈E→(G)μ(e)∑f∈E→(G)P(e,f)TV⁡(Sn(P)(e,⋅),Sn(P)(f,⋅)).D_n=\sum_{e\in\vec E(G)}\mu(e) \sum_{f\in\vec E(G)}P(e,f)\, \operatorname{TV}\bigl(S_n(P)(e,\cdot),S_n(P)(f,\cdot)\bigr).(12)✦

In the paper, the result reads: let GG have positive vertex weights, satisfy the cross-mass bound with C≥1C\ge1, and have an edge, fix x≥32x\ge32, assume su=w(N(u))≤exs_u=w(N(u))\le e^x for every uu and cuv≥1/xc_{uv}\ge1/x on every edge, and put hu=∑v∈N(u)wvcuvh_u=\sum_{v\in N(u)}w_vc_{uv}; at each nonisolated uu, set πu(v)=wvcuv/hu\pi_u(v)=w_vc_{uv}/h_u, Pu(v,z)=wz𝟏{vz∈E(G)}/cuvP_u(v,z)=w_z\mathbf1_{\{vz\in E(G)\}}/c_{uv}, Qu=(IdN(u)+Pu)/2Q_u=(\mathrm{Id}_{N(u)}+P_u)/2 and Kuj=PuQujK_u^j=P_uQ_u^j; put Z=∑uwuhu=6TG(w)>0Z=\sum_uw_uh_u=6T_G(w)>0, where TG(w)T_G(w) is the sum of wuwvwzw_uw_vw_z over unordered triangles, and μ(u,v)=wuwvcuv/Z\mu(u,v)=w_uw_vc_{uv}/Z on directed edges; sampling (u,v)(u,v) from μ\mu and zz from Pu(v,⋅)P_u(v,\cdot) gives probability wuwvwz/Zw_uw_vw_z/Z to each ordered triangle; define Hw(a)=∑y:a(y)>0a(y)log⁡(wy/a(y))H_w(a)=\sum_{y:a(y)>0}a(y)\log(w_y/a(y)), Hj=𝔼μHw(Kuj(v,⋅))H_j=\mathbb E_\mu H_w(K_u^j(v,\cdot)) and TV⁡(a,b)=12∑y|a(y)−b(y)|\operatorname{TV}(a,b)=\tfrac12\sum_y|a(y)-b(y)|.

What Is Checked

The definitions are stated over finite simple graphs with real vertex weights, their oriented edges, and real matrix kernels and real weights on finite state sets.