Skip to content

Can the related cases recover the hidden label? (Kesten–Stigum)

A fraud model flags a card, and the card's account shares devices with other accounts whose fraud reviews you already know. Sometimes those related cases tell you a lot about this one; sometimes they are too few or too mixed to tell you anything. This page explains the mathematics the library uses to tell the two apart — Kesten–Stigum reconstruction, catalog result 229 — and exactly how far the code's check follows it.

It assumes you know what a graph and a correlation are. Symbols are collected on How to read these pages; the plain-language version of this check, with no formulas, is Neighbour agreement.

The situation

Every decision the library makes carries evidence: a description of the related cases around it (the corroboration graph). Cases are dots; a line joins two cases that share something — a device, an employer, a near-duplicate post, an adjacent sensor. Each case you have already resolved carries a label (fraud or not, defaulted or repaid, out of limits or in).

The question this check answers is: if this case's true label were hidden, could the labels of its related cases recover it? If yes, the evidence is informative and an automated action may use it. If no, the related cases are noise, and the library holds the decision for a person — while still recording the action it would have taken (proposed_action).

Intuition: a copying game on a tree

Picture the hidden label at the root of a family tree. Each case passes its label to each of its \(d\) children, but the copy is noisy: with some probability the child gets the parent's label, otherwise a random one. Neighbour agreement \(\lambda\) measures how faithful one copy is: \(\lambda = 1\) means children always copy, \(\lambda = 0\) means the child's label is unrelated to the parent's.

flowchart TD
    R["root: hidden label"] -->|"copy, agreement λ"| A["child"]
    R -->|"copy, agreement λ"| B["child"]
    A -->|λ| A1["grandchild"]
    A -->|λ| A2["grandchild"]
    B -->|λ| B1["grandchild"]
    B -->|λ| B2["grandchild"]

Follow one path down \(h\) generations. The correlation between the root and the case at the end is \(\lambda^h\), which fades quickly. But there are \(d^h\) such paths. Adding up the leaves' votes, the signal about the root grows like \(d^h\lambda^{2h} = (d\lambda^2)^h\) relative to the noise. So everything turns on one number, the evidence strength \(d\lambda^2\):

  • above 1, the signal compounds with every generation, and the distant related cases still say something about the root;
  • below 1, it decays geometrically, and adding more distant cases does not help.

For the fraud ring below, \(d\lambda^2 = 1.5125\), so the signal-to-noise ratio after 1, 2, 3 and 5 generations is 1.51, 2.29, 3.46 and 7.92. For the thin chain, \(d\lambda^2 = 0.1667\): 0.17, 0.028, 0.0046, 0.0001. (Computed with uv run python -c "print([round((5*0.55**2)**h, 4) for h in (1,2,3,5)])" and the same for \(d = 1.5\), \(\lambda = 1/3\).)

Worked example: a fraud ring and a shared laptop

Run:

uv run grounded-decision examples fraud_review

The example builds the evidence from raw login rows with snapshot_from_graph, which computes three numbers from the graph:

  • \(d\) = mean number of links per case, \(2|E|/n\);
  • \(\lambda\) from the share of links whose two ends carry the same label, \(p_{\mathrm{same}}\): [ \lambda = \frac{q\,p_{\mathrm{same}} - 1}{q - 1}, ] where \(q\) is the number of label values (n_states, default 2, so \(\lambda = 2p_{\mathrm{same}} - 1\));
  • the link density \(\hat p\), used by the knife-edge check, not this one.
Evidence Cases Links \(d\) \(p_{\mathrm{same}}\) \(\lambda\) \(d\lambda^2\) Check
16-account device ring, 13 confirmed fraud 16 40 5 31/40 = 0.775 0.55 1.5125 pass (above 1.05)
4 accounts on a chain of shared laptops 4 3 1.5 2/3 0.3333 0.1667 fail

The example prints these as

neighborhood d=5  λ=0.55  strength dλ²=1.513  (need > 1.05)  STRONG — above KS
neighborhood d=1.5  λ=0.3333  strength dλ²=0.1667  (need > 1.05)  TOO THIN — below KS

and the second authorisation is held with the reason d λ² = 0.1667 vs 1+0.050 (at or below KS; abstain) and proposed_action=block kept on the record. You can reproduce the thin case directly:

from grounded_decision.evidence.graph import snapshot_from_graph
from grounded_decision.evidence.reconstruction import reconstruction_report

snap = snapshot_from_graph([1, 1, 1, 0], [(0, 1), (1, 2), (2, 3)], p_threshold=0.08)
print(snap.degree, snap.lambda_hat)  # 1.5 0.333...
print(reconstruction_report(snap.degree, snap.lambda_hat).summary)
# d λ² = 0.1667 vs 1+0.050 (at or below KS; abstain)

A second example shows the same line in community detection, where the "label" is a user's department and the question is whether clustering the graph would recover it:

uv run grounded-decision examples community_detection
Graph (120 users) \(d\) \(\lambda\) \(d\lambda^2\) Reconstruction
well separated (85% of links inside a department) 19.82 0.6922 9.494 pass
blurred (60% inside) 19.53 0.1706 0.5688 fail — publishing would be noise
sparse (~4 links per user) 3.933 0.661 1.719 pass (held by the knife-edge check instead)

The blurred graph has as many links as the well-separated one. Link count is not evidence strength; agreement squared is what matters.

The precise statement

The model. A label \(\sigma_{\mathrm{root}} \in \{1,\dots,q\}\) is drawn uniformly at the root of an infinite tree in which every vertex has \(d\) children (or a random Poisson number with mean \(d\)). Each child keeps its parent's label with probability \(\lambda + (1-\lambda)/q\) and otherwise takes one of the other \(q-1\) values uniformly (the \(q\)-state symmetric channel; \(\lambda\) is its second eigenvalue). Reconstruction means the labels at depth \(h\) give an estimate of the root that beats random guessing by an amount that does not vanish as \(h \to \infty\).

Kesten–Stigum bound. If \(d\lambda^2 > 1\), reconstruction holds — in fact simply counting the labels at depth \(h\) already works. This holds for every \(q\).

Below the bound the picture depends on \(q\):

  • \(q = 2\) (binary symmetric channel): if \(d\lambda^2 \le 1\), reconstruction fails. The bound is exactly the threshold.
  • \(q = 3\) and \(q = 4\): the bound is known to be the threshold only in some regimes (for example, large degree), and the general case has been open in the published literature.
  • \(q \ge 5\): reconstruction is possible strictly below \(d\lambda^2 = 1\) for suitable \(d\). Below the line does not imply unrecoverable.

Where this result stands

In the wider literature: reconstruction above the line \(d\lambda^2 > 1\) is classical (Kesten and Stigum, 1966) for every \(q\). That the line is exact is established for the binary symmetric channel (Bleher, Ruiz and Zagrebnov; Evans, Kenyon, Peres and Schulman), known only in some regimes for three and four states (Sly), and false for five or more states (Mossel; Sly). For two-community stochastic block models the same line is the detection threshold (Mossel, Neeman and Sly; Massoulié).

In this project's math catalog (result 229): the manuscript claims the exact threshold \(d\lambda^2 > 1\), with non-reconstruction at equality, for three-state symmetric and four-state ferromagnetic channels on regular and Poisson trees, and the weak-recovery threshold for the three-community block model. The machine-checked (Lean) statement in the catalog covers only the supercritical direction: three-state reconstruction when \(d\lambda^2 > 1\). Non-reconstruction is manuscript only.

What this library relies on: only "above the line, the related cases are informative". Holding below the line is a product policy. See Where each result stands.

What the code does

reconstruction_report(degree, lambda_hat) in grounded_decision/evidence/reconstruction.py:

\[ \text{pass} \iff d\lambda^2 > 1 + m, \qquad m = \texttt{reconstruction\_margin} = 0.05 \text{ by default.} \]
  • A pass is tagged proven (trust="lean"), because it is the supercritical direction the Lean statement covers. A fail is tagged published (trust="paper"): holding there leans on the manuscript's non-reconstruction claim and on the binary case, and is a policy choice. See trust levels.
  • Exactly on the line fails: \(d = 4\), \(\lambda = 0.5\) gives \(d\lambda^2 = 1.0\) and fails even with margin=0, because the test is strict.
  • \(\lambda\) is squared, so strong disagreement counts as signal: \(\lambda = -0.55\) gives the same 1.5125 as \(\lambda = 0.55\). Perfectly alternating labels predict each other as well as perfectly matching ones.
  • \(q\) is used only in the estimator lambda_from_agreements. With eight agreeing links out of ten, \(\lambda = 0.6\) for \(q = 2\) and \(0.7\) for \(q = 3\).
  • The record's metrics carry degree, lambda_hat, d_lambda_sq, margin and kesten_stigum=1.0, so a dashboard can plot the line.

Where the code departs from the theorem:

  1. Your graph is not a tree. The theorem is about trees, where every path to the root is independent. Real graphs have loops (the fraud ring is a cycle of shared phones), and loops let the same evidence be counted twice, which inflates agreement.
  2. Mean degree is not the branching number. The theorem's \(d\) is the number of children per vertex. On graphs that look locally like a Poisson random graph, mean degree is the right number. On a regular graph each vertex has one parent and \(d - 1\) children, so the code's \(d\) is one too high: the fraud ring with \(d - 1 = 4\) gives \(4 \times 0.55^2 = 1.21\), still above 1.05, but a graph sitting just above the line could be below it.
  3. "Chance" means balanced labels. The estimator assumes each label value is equally common. The fraud ring has 13 fraud and 3 cleared accounts; labels scattered at random with that mix would still agree on about 70% of links (\((13/16)^2 + (3/16)^2 = 0.695\)), giving \(\lambda \approx 0.39\). On a graph with \(d = 8\) that alone would score \(8 \times 0.39^2 = 1.22\) and pass. When one label dominates, check \(\lambda\) against a shuffled-label baseline.
  4. \(\lambda\) is an estimate. From 40 links, the share of agreeing links has a standard error of about 0.066, so a 95% interval for \(\lambda\) in the fraud ring is roughly 0.29 to 0.81 and for \(d\lambda^2\) roughly 0.42 to 3.27. The margin of 0.05 is a dead band against flapping on the line, not a confidence interval.
  5. For \(q \ge 5\), holding below the line is a policy, not a theorem (see above).

Limits, and what to do about them

This check is direction-blind

The check measures how informative the related cases are, not which outcome they support. In fraud_review, a clean event on the dense fraud ring (13 of 16 accounts confirmed fraud) passes reconstruction exactly as a suspicious event does. The direction of the decision comes from the event you send; this check only asks whether the related cases are strong enough to act on at all. "The neighbours agree with this action" is the support check's job: in the same example it holds the pass, because only 3 of the 16 accounts were cleared.

  • It gates your label; it does not compute one. The library runs no belief propagation, spectral clustering or message passing. Compute your label elsewhere, then ask this check whether to act on it.
  • Garbage in, garbage out. The code trusts the degree and lambda_hat on the snapshot. Never pass a classifier probability as \(\lambda\): \(\lambda = 0.9\) with \(d = 8\) passes whatever the graph looks like. Use snapshot_from_graph, or compute agreement along real links.
  • Near the line. If your traffic often lands between 0.8 and 1.5, the estimation noise in item 4 matters more than the margin. Widen the margin with Limits(reconstruction_margin=...) to hold more, or collect more links per case before deciding. Choosing the margin and the other knobs is covered in Choose parameters.
  • It does not look at density or the score. A dense graph can be uninformative (the blurred community graph), and an informative graph can still sit on a cut-off (knife-edge check) or carry an unusual case (unusualness check). A lone alarm inside a large, quiet graph passes this check — its neighbours agree with each other, just not with it — and it is the unusualness check that holds it in manufacturing_spc.