✗ Mechanism failed 2026

Directed distance-curvature positional encoding

Implementation & benchmark of arXiv:2607.04878 — Steinerberger Curvature On Digraphs -- Discrete Bonnet-Myers and Lichnerowicz Theorems

Usefulness6/10

Difficulty5/10

Novelty8/10

Geometry Accuracy Sample efficiency Generalization Graph nn Attention Embedding Graph theory Linear algebra Geometry Metric geometry

Source paper: Steinerberger Curvature On Digraphs -- Discrete Bonnet-Myers and Lichnerowicz Theorems arXiv:2607.04878 ⓘ · analyzed Aug 30, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Add global directed-curvature features to every node in a graph neural network or directed graph transformer. The features distinguish how a node functions as a source versus a destination in the graph's asymmetric metric, potentially exposing bottlenecks, hubs, sinks, and structurally central nodes that local message passing cannot identify.

Formulas

$$\sum_{w\in V} d(v,w)\mu(w)=|V|,\qquad\text{equivalently }D\mu=n\mathbf{1}.$$

$$\mu^{\mathrm{out}}=D^{\dagger}(n\mathbf{1}),\qquad \mu^{\mathrm{in}}=(D^{T})^{\dagger}(n\mathbf{1}).$$

$$\|\mu^{\mathrm{out}}\|_{\ell_{1}}=\langle\mu^{\mathrm{out}},\mathbf{1}\rangle=\left\langle\mu^{\mathrm{out}},\frac{1}{n}D^{T}\mu^{\mathrm{in}}\right\rangle=\left\langle\frac{1}{n}D\mu^{\mathrm{out}},\mu^{\mathrm{in}}\right\rangle=\langle\mathbf{1},\mu^{\mathrm{in}}\rangle=\|\mu^{\mathrm{in}}\|_{\ell_{1}}.$$

$$s=\frac{\|\mu^{\mathrm{out}}\|_{1}+\|\mu^{\mathrm{in}}\|_{1}}{2n}+\varepsilon,\qquad h_i=\left[x_i\,\middle\|\,\operatorname{clip}\left(\frac{\mu^{\mathrm{out}}_i}{s},-c,c\right)\,\middle\|\,\operatorname{clip}\left(\frac{\mu^{\mathrm{in}}_i}{s},-c,c\right)\right].$$

Mathematical statement

For a strongly connected directed graph with n vertices, let D be the n by n directed distance matrix, with D_{ij}=d(i,j), the length of a shortest directed path from vertex i to vertex j. The paper defines out-curvature mu^{out} and in-curvature mu^{in} through the linear systems D mu^{out}=n 1 and D^T mu^{in}=n 1, where 1 is the all-ones vector in R^n. If D is singular, the construction uses the Moore-Penrose solutions mu^{out}=D^{dagger}(n 1) and mu^{in}=(D^T)^{dagger}(n 1). The values can be signed, so their signs and magnitudes encode global metric geometry rather than probabilities. The paper proves, when the displayed systems are satisfied, that ||mu^{out}||_1=||mu^{in}||_1, providing a common normalization scale. If permutation matrices P and Q satisfy P D Q=D^T, then invertibility implies mu^{out}=Q mu^{in}; this identifies a symmetry case in which the two channels contain equivalent information.

Implementation notes

(1) Integration point: use a directed graph transformer or message-passing GNN whose node feature matrix is X in R^{n by d}. Precompute the directed shortest-path distance matrix D for every graph. Solve D mu_out=n times the all-ones vector and D^T mu_in=n times the all-ones vector using an SVD-based Moore-Penrose pseudoinverse. Concatenate two normalized scalar channels to each node before the first graph layer. Use h_i=[x_i concatenated with clip(mu_out_i/s,-c,c) concatenated with clip(mu_in_i/s,-c,c)], where s=(||mu_out||_1+||mu_in||_1)/(2n)+epsilon, epsilon=10^{-6}, and c=5. Preserve signs; do not apply ReLU to these channels. (2) Pseudocode: for each graph, compute D; calculate its SVD U,S,V^T; set inverse singular values to 1/S_j when S_j is greater than 10^{-6} times the largest singular value and zero otherwise; compute mu_out=V diag(S^{-1}) U^T (n ones); repeat with D^T to obtain mu_in; normalize and concatenate; run the unchanged GNN and task loss. (3) The paper supplies the distance systems, pseudoinverse construction, and equal-l1 normalization identity. Estimate the clipping threshold, channel projection weights, and optional attention coefficients empirically. For a second variant, add b_ij=alpha mu_out_i+beta mu_in_j to directed attention logits, with learned alpha and beta initialized to zero. (4) First cheap experiment: train a four-layer directed GAT or graph transformer on a synthetic directed stochastic-block-model node-classification task and one citation or transaction graph. Compare the baseline against degree, PageRank, Laplacian eigenvectors, shortest-path summaries, and curvature using five seeds and multiple labeled-node budgets. Measure accuracy, calibration, and preprocessing time. Success means consistent low-label accuracy gains, particularly for nodes with similar local degree but different global reachability, without unacceptable distance-matrix memory or SVD cost.

Verification

Mechanism failed

Stage 1 · Toy mechanism gate: Failed ✗

Stage 2 · Mechanism transferred to benchmark: Not tested

Stage 2 · Practical benchmark result: Not run

Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works

Stage 1 — Mechanism check agent confidence 9/10

Built experiment.py with directed shortest-path curvature features, SVD pseudoinverse computation, a numerical system check, and a seeded low-label directed node-classification comparison. The systems were solved accurately with maximum residual 6.8e-12, and signed sums matched, but the claimed absolute l1 equality failed: all 20 graphs had signed curvature values, with mean absolute l1 mismatch 207.3 and maximum 2956.3. Curvature gave a small low-label accuracy increase from 0.465 to 0.479 and improved Brier score from 0.487 to 0.467, but at the higher label budget accuracy decreased from 0.521 to 0.511, so there is no consistent observed win and the stated l1 claim is contradicted for signed solutions.

Agent confidence: 9/10

Baseline: 5 labels/class: accuracy 0.4651 +/- 0.0353, Brier 0.4869; 10 labels/class: accuracy 0.5211 +/- 0.0271, Brier 0.4414
Idea: 5 labels/class: accuracy 0.4791 +/- 0.0604, Brier 0.4671; 10 labels/class: accuracy 0.5105 +/- 0.0466, Brier 0.4333; maximum linear-system residual 6.8e-12, mean absolute l1 mismatch 207.3

Limitations: Only a small synthetic 96-node graph task was tested; no citation or transaction graph, GAT or transformer attention variant, degree/PageRank/eigenvector controls, calibration curves, FLOP accounting, or extensive labeled-node budgets were evaluated. The experiment used five seeds and two label budgets.

How to run: python3 experiment.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Artifacts

Implementation overview ⬇ Download all as ZIP 2 files · code, reports and structured results

🐍 experiment.py 4.3 KB View Raw
📄 report.md 1.6 KB View