Graph-Regularized Rating Completion

00Overview

Every sports model is at its worst in Week 1. You have almost no games, the "who-beat-whom" matrix is nearly empty, and you're forced to lean on priors that everyone else has too. This project takes a 2026 numerical-optimization result — graph-regularized low-rank matrix completion (arXiv:2607.09546) — and uses it to fill that empty early-season ratings matrix by borrowing strength across teams that a prior graph says should be similar (division rivals, roster-continuity, coaching trees, prior-season profile).

The bet: in the exact window where books and Polymarket are softest — the first few weeks, before the market has data either — a principled prior beats the ad-hoc "regress 1/3 to the mean" every public model uses. We start with the NFL because it has the densest priors and the deepest betting markets, prove or kill it there, then expand.

01The early-season problem

A power-rating system wants a full N×N matrix of relative team strength. You get there by observing games. But early in a season:

• The matrix is ~97% empty. In NFL Week 3, each of 32 teams has played 2 of its 31 possible opponents. The head-to-head graph is disconnected — most pairs share no common opponent yet, so "strength of schedule" adjustments have almost nothing to chew on.
• The few observations are high-variance. One fluky game (a pick-six, a missed FG, weather) swings a team's whole rating when it's one of only two data points.
• Rosters just changed. Free agency, the draft, trades, and — in college — the transfer portal mean last year's ratings are stale in a way that's hard to quantify.

So early-season modeling is fundamentally a blending problem: how much do you trust the sparse, noisy new data versus a prior built from last year and the offseason? Every model answers this, mostly with a hand-tuned knob. This project answers it with a structured optimization instead.

02How it's modeled today

The status quo across public and sharp models is a handful of prior-blending heuristics:

The common gap: none of them let an unobserved team inherit strength from the specific other teams it resembles. They pool toward a global average or apply a scalar prior. Graph regularization is exactly the missing piece — it pools toward your neighbors in a similarity graph, which is a much more informative prior than "the league."

03The method — GR-RTRMC

Paper: Graph-Regularized Low-Rank Matrix Completion by Variable Projection — Loucheur, Absil, Journée (arXiv:2607.09546). Absil co-authored the standard text on optimization over matrix manifolds, so this is a serious numerical group.

Classic matrix completion assumes your partly-observed matrix M is approximately low-rank, M ≈ UW, and fills the gaps. This paper bolts graph regularization onto a fast solver (RTRMC): side-information graphs say which rows and which columns should be similar, and the optimizer is penalized when connected entities get different latent vectors.

The objective

h(U,W) = ½‖C ⊙ (UW − M)‖²_Ω        fit the games actually played (C = confidence)
       + (λ²/2)‖UW‖²_Ω̄             shrink predictions where you have NO data
       + (λu/2)·Tr(Uᵀ Lu U)        row-graph smoothness  (team similarity)
       + (λw/2)·Tr(W Lw Wᵀ)        column-graph smoothness

Lu, Lw are graph Laplacians. That third term expands to Σ A_ij (U_i − U_j)² — literally "penalize the squared difference in latent strength between any two teams the graph connects, weighted by edge strength." That single line is the whole idea: soft-tie the ratings of similar teams so sparse data on one informs the other.

The clever machinery

• Variable projection — for fixed U, the best W is a closed-form least-squares solve; substitute it back to optimize over U alone. Fewer variables, better conditioning.
• Grassmann manifold — quality depends only on U's column space, so optimize over subspaces (orthonormal U), removing gauge redundancy.
• Riemannian trust-region — a robust second-order optimizer on that manifold. You don't implement this — you call Pymanopt.

04Why it fits early-season

The method's best-case regime is "very sparse observations + a prior graph the signal is genuinely smooth over." Early-season NFL is almost a textbook instance:

• Genuinely sparse: 2–4 games played out of 31 opponents → the exact >90% missingness where naive completion fails and a prior earns its keep.
• Genuinely smooth over a good graph: team strength really is correlated with division, prior-season profile, roster continuity, and coaching lineage. Those make honest edges.
• The prior decays gracefully: as real games accumulate, the fit term (‖C⊙(UW−M)‖²_Ω) dominates and the graph prior fades — automatically handing control from prior to data. That's the blend knob the status-quo models set by hand, solved as optimization.

In other words, the thing this method is uniquely good at is exactly the thing early-season models are uniquely bad at.

05NFL first — the rollout

The original analysis pointed at college basketball (maximum sparsity). We're starting with the NFL instead, on purpose:

• Densest priors of any league. ~80%+ roster continuity year-to-year, and QB continuity is a single dominant signal that makes clean, high-weight graph edges. The prior graph is more trustworthy here than anywhere else.
• Small, well-understood system. 32 teams, a rigid division/conference structure, exhaustive public data (EPA, DVOA, PFF, snap counts) — the graph practically writes itself.
• Slow information = a long prior window. One game per week means the early-season prior stays load-bearing for 4–6 weeks, not 4–6 days. More weeks of edge per season.
• Deep, liquid markets (see §07). Unlike thin college totals with tiny limits, NFL spreads/totals and Polymarket NFL markets are bettable at real size.

The NFL prior graph

Edges (row/column similarity) we'd build the Laplacian from:

06Roadmap

The engine is league-agnostic — a "complete a sparse rating matrix with a prior graph" module. Each new league is a new M, a new graph, and a new backtest, not new math.

07Polymarket & sportsbooks

A better early-season rating is only worth building if it converts to money. Two venues, two shapes of edge:

Polymarket

• Season win-total & futures markets. "Will the Bengals win 10.5+ games?", division winner, playoff berth, conference/Super Bowl. Feed completed early-season ratings into a season simulator → win-distribution per team → a probability you can compare against Polymarket's price. Polymarket pricing on these is often slower and thinner than a sharp book, so a genuinely better power rating in Weeks 1–4 has room to be right before the market corrects.
• Weekly game markets. Moneyline / winner markets each week; your model's win prob vs. Polymarket's implied prob → take the mispriced side, size by edge.
• Resolution mechanics fit us: these are exactly the medium-horizon, prior-dominated questions where an offseason-informed rating should beat a market that's also data-starved early.

Sportsbooks (via SharpLab)

• Spreads & totals, Weeks 1–6. Completed rating → projected spread/total → bet when it diverges from the opener, then grade against the close.
• CLV is the honest scoreboard. SharpLab already tracks closing-line value. The single validation question is: do bets flagged by the completed-rating model beat the closing line on the early-season slice, more than a plain ridge/Elo blend does? If yes, the edge is real; if not, kill it — no story about "better RMSE" survives a CLV null.
• Capacity reality: NFL limits are high enough that a real edge is bettable at size — unlike the thin college totals the method's sparsity would otherwise point you toward.

08Build plan & timeline

Off-the-shelf Pymanopt does the manifold optimization, so nearly all real work is data engineering and honest evaluation. With Claude Code pairing on the plumbing:

Total: ≈1.5–2 weekends of focused work to a real go/no-go. V2 (player-level completion, learned edge weights, custom Hessian for speed, multi-league) waits until V1 shows CLV — per the paper, marginal gains mean heavy V2 investment is likely wasted otherwise.

Core code shape

1. Assemble M (team×team margin), mask Ω (games played), weights C
2. Build Lu, Lw from prior graphs (normalized Laplacians; tune edge weights)
3. Cost f(U): closed-form W(U) least-squares  (the λw·(Lw⊗I) coupling is the fiddly bit)
   Euclidean grad ∇f(U) = R_U·W_Uᵀ + λu·Lu·U   → let Pymanopt handle the Riemannian part
4. Cross-validate r, λu, λw, λ² on held-out games
5. Baseline to beat = tuned ridge/RAPM + prior-season rating  (NOT a strawman)

09Why it might not work

Going in clear-eyed. The reasons to not build this, straight from the paper's own evidence:

• Ridge already does ~80% of this. RAPM is regularized regression; graph-Laplacian regularization is "ridge with a fancier penalty matrix." The open question is whether the specific graph adds signal beyond a well-tuned scalar prior + prior-season rating. Often it won't.
• The paper's gains are marginal and sometimes negative — it lost to SoftImpute in one scenario. A bump you can't distinguish from noise is worthless for betting.
• Small-sample validation. Only ~272 NFL games/season, and we only care about the first ~6 weeks — so a few seasons of backtest has low statistical power to confirm a real CLV edge. This is the NFL-specific risk: it may take several seasons to know.
• 2–3× compute for the graph term is a bad trade unless accuracy clearly converts to CLV.