Community detection: publish tonight's community labels or keep yesterday's¶
A nightly job clusters your user graph (who messages whom, who works with whom, who buys from whom) and publishes community labels that a recommender, a marketing segment builder or an org-analytics dashboard then treats as fact. Clustering algorithms always return groups, even when the graph has no real group structure, so the labels look the same whether they mean something or not. This page shows how the library lets the nightly publish go ahead only when the graph is able to support community labels at all, and keeps yesterday's labels otherwise. It is written for the data scientist or graph team that owns the job, and for the product owner who consumes the labels; the maths is in collapsed boxes and linked pages.
At a glance
| Decision | Publish tonight's community labels (publish_community_labels) or keep yesterday's. |
| Owner | The data team that runs the nightly clustering job. |
| Today's rule | Run the clustering every night and publish whatever it returns. |
| What this adds | Before publishing, check on a set of users whose community you already know that the interaction graph is dense enough and separated enough for communities to be recoverable. Otherwise hold. |
| Demo outcome | 3 nights: 1 published, 2 held (one for blurred communities, one for too few interactions). |
| Example id | community_detection (uv run grounded-decision examples community_detection) |
The decision today¶
Every night the job reruns spectral clustering, Louvain or a similar method and overwrites the published labels. Nobody checks them, because there is no ground truth for most users.
| Mistake | What it costs |
|---|---|
| Publish labels that are noise | Recommender features, segments and dashboards silently reshuffle; downstream teams draw conclusions from structure that is not there. |
| Hold labels that were fine | One more day of yesterday's labels, marked stale. |
Where today's rule goes wrong¶
The demo has 120 users whose department is known from the HR system: 60 in Engineering, 60 in Sales. Three nights, three interaction graphs among those users:
- Well separated. About 20 interactions per user, 85 % of them inside the user's own department. The departments really are visible in the graph. Publishing is right.
- Blurred. Just as many interactions, but only 60 % inside the department. There are plenty of links; they just do not follow department lines much more than chance. The clustering still returns two tidy groups. Publishing ships noise.
- Sparse. About 4 interactions per user, 80 % inside the department. The signal is there in principle, but the graph is so thin that it is on the verge of breaking into disconnected pieces, and tomorrow's handful of new links could reshape the groups entirely.
Today's rule publishes all three.
What the system checks, in your terms¶
The library does not look at tonight's clustering output. It looks at the interaction graph among a labelled reference set: users whose community you know from outside the graph (an HR department, a self-declared team, a billing region). It asks whether that graph could support community labels at all. If it cannot, no clustering of it can be trusted.
It runs six checks; all six must pass to publish. Two check the policy
itself and pass every night here (see
the six checks). Three of the four
that read your data are below; the fourth, support, is not measured in this example and passes with support not measured:
| Check | Question, in graph-team terms | Reads | Fails when | What a hold means |
|---|---|---|---|---|
| Neighbour agreement | Do reference users who interact tend to share a community, often enough and with enough links per user, that communities are recoverable from the graph? | Interactions among reference users and their known communities | Too few links per user, or links cross community lines nearly as often as they stay inside | "The communities are not distinct in this graph." |
| Knife-edge | Is the graph's link density clearly away from the density at which a random graph of this size falls apart into pieces? | Number of reference users and links | Density is inside the uncertainty window around that line | "Not enough interactions yet; the graph is barely holding together." |
| Unusual cases | Is tonight's held-out error on the reference set in line with the errors of recently published refreshes? | Tonight's disagreement rate on held-out reference users; the last 30 published refreshes' rates (the calibration set) | Tonight's rate is higher than almost all of them | "Tonight's clustering did worse than usual on users we can check." |
What these checks do NOT verify
- Tonight's partition. The first two checks say whether the graph can support communities, not whether tonight's algorithm found them. Only the unusual-cases check looks at the clustering's output, and only through the disagreement rate you compute and send.
- In this demo, the unusual-cases check cannot fail. The demo sends
the same disagreement rate, 0.12, on all three nights, although on
the blurred night a real held-out error would be far higher. With
your real rate, a night with a rate of about 0.19 or more would be
held (computed with
uv run python -con the demo's calibration set: p-value 0.097 at 0.19, below the 0.10 level). - Which community a user is in. Agreement measures whether linked users share labels, not which labels; that is fine here, because the decision is "publish or not", not "assign this user".
Data you provide¶
| Input | Source system | Refresh | Owner | Minimum / quality bar |
|---|---|---|---|---|
| Labelled reference set: user ids with a known community | HR system, self-declared team, billing region | Monthly, or when the source changes | Data team | Large enough that the knife-edge window is narrow (see the table below); a few hundred users is a sensible start. Must not be chosen by looking at the graph. |
| Interactions among reference users in a fixed window (30 days in the demo) | Event log | Nightly | Data engineering | Same window every night, so densities are comparable. |
| Tonight's disagreement rate on held-out reference users | The clustering job | Nightly | Data team | Hold out reference users from any step that tunes the clustering. |
Calibration set: disagreement rates of recent published refreshes (RECENT_SEED_DISAGREEMENT_RATES, 30 in the demo) |
Job history | Append on each publish | Data team | At least 9 at the default 10 % level, or the check can never pass. |
seed_set_evidence in community_detection.py turns these into the
evidence summary. (The code calls the reference set the "seed set".)
How big must the reference set be? The knife-edge window shrinks as the
set grows. Its cut-off here is the density at which a random graph becomes
connected, \(\ln n / n\), which also shrinks. Half-widths below are from
the library's formula, computed with uv run python -c:
| Reference users \(n\) | Window half-width | Connectivity cut-off \(\ln n / n\) | So the graph must have density above about |
|---|---|---|---|
| 16 | 0.209 | 0.173 | 0.38 |
| 40 | 0.118 | 0.092 | 0.21 |
| 80 | 0.084 | 0.055 | 0.14 |
| 120 (demo) | 0.070 | 0.040 | 0.11 |
| 200 | 0.057 | 0.027 | 0.08 |
| 1000 | 0.034 | 0.007 | 0.04 |
With a small reference set, almost every realistic interaction graph is held by this check alone.
Worked example¶
These rows come from uv run grounded-decision examples community_detection.
| Night | Graph | Agreement check | Knife-edge check | Unusual-cases check | Today's rule | This system |
|---|---|---|---|---|---|---|
| 1 | Well separated: 1,189 interactions among 120 users | Pass: many links, mostly within department | Pass: density well above the connectivity line | Pass (fixed rate 0.12) | publish | act publish_community_labels |
| 2 | Blurred: 1,172 interactions | Fail: links barely follow departments | Pass | Pass (fixed rate 0.12) | publish | hold; proposed publish kept on the record |
| 3 | Sparse: 236 interactions | Pass: few links, but they follow departments | Fail: density sits on the connectivity line | Pass (fixed rate 0.12) | publish | hold; proposed publish kept on the record |
The two holds have different reasons, and the data team needs to know
which: night 2 says "the communities are not distinct", night 3 says "not
enough interactions yet". Over three nights today's rule publishes three
times; this system publishes once (blocked_overconfident_acts: 2 in the
--json summary).
The numbers behind each check
\(d\) is the average number of links per reference user; \(\lambda\) is how much more often linked users share a community than chance (for two communities, if a fraction \(f\) of links stay inside a community, \(\lambda = 2f - 1\)). Evidence strength \(d\lambda^2\) must be above \(1.05\).
| Well separated | Blurred | Sparse | |
|---|---|---|---|
| links per user \(d\) | 19.82 | 19.53 | 3.933 |
| agreement \(\lambda\) | 0.692 | 0.171 | 0.661 |
| evidence strength \(d\lambda^2\) | 9.494 (pass) | 0.569 (fail) | 1.719 (pass) |
| link density \(\hat p\) | 0.167 | 0.164 | 0.033 |
| connectivity cut-off \(\ln 120/120\) | 0.040 | 0.040 | 0.040 |
| distance from cut-off vs half-width 0.070 | 0.127 (outside: pass) | 0.124 (pass) | 0.007 (inside: fail) |
| unusualness p-value | 0.677 | 0.677 | 0.677 |
The p-value is \((1 + \#\{\text{calibration rates} \ge 0.12\}) / (1 + 30)\); the calibration rates run from 0.080 to 0.196.
For two equal-sized communities in a random graph with planted communities (the stochastic block model), \(d\lambda^2 > 1\) is the Kesten–Stigum line: above it, communities can be recovered better than chance; below it, no method can. The 0.05 margin is policy. With five or more communities, recovery can be possible below this line, so holding below it becomes a conservative choice rather than a theorem. See recovering a label from related cases.
The record's reason on night 2 reads
d λ² = 0.5688 vs 1+0.050 (at or below KS; abstain); on night 3,
evidence density inside operational window (…).
What happens next¶
| Verdict | Who is told | What they see | Time limit | If nobody acts | Feedback |
|---|---|---|---|---|---|
| Act | Downstream consumers (normal publish) | New labels | Nightly | n/a | Append tonight's disagreement rate to the calibration set. |
| Hold | Data team (ticket or channel), consumers (stale flag) | proposed_action=publish_community_labels, failed checks, reason |
Before the next nightly run | Keep yesterday's labels, marked stale. After several consecutive holds (pick a number, for example three), escalate to the job owner: the graph may have changed for good. | Do not add held nights to the calibration set. |
Do not publish tonight's labels as a "draft" to the same table; consumers will read them as fact. Each night is decided independently; there is no state carried between nights.
Tuning and expected workload¶
| Setting | Policy or data? | How to choose | Too tight | Too loose |
|---|---|---|---|---|
| Reference-set size | Data | See the size table above | — | Small sets are held almost every night by the knife-edge check |
| Agreement margin (0.05) | Policy | Keep the default | More holds on borderline graphs | Publishes on graphs barely above the line |
| Density cut-off (\(\ln n / n\)) | Built into the example | Replace it if your consumers care about a different density | — | — |
| Unusualness level α (0.10) and calibration size (30) | Policy / data | α is the share of normal nights you accept holding | More held nights | Bad nights slip through |
Expected holds. On a stable product graph, expect holds only when interaction volume drops (holidays, outages) or when communities genuinely merge. Measure it by replaying the last few months of nights before you switch the gate on: Estimate impact before launch.
Limits, risks and compliance¶
- Reference-set bias. The checks only see users with a known community. If those are, say, only employees of large departments, the verdict says nothing about the rest of the graph. Draw the reference set so it resembles the users you label.
- The demo's unusual-cases check is decorative (fixed rate 0.12), as described above.
- More than two communities. The demo has two. With many communities the agreement line is a conservative policy, not a theorem (see the numbers box).
- Synthetic data. The three graphs are sampled from a random model with planted communities and a fixed random seed.
- What is being certified. A publish means "the reference graph could support communities and tonight's held-out error was normal". It does not certify tonight's labels for users outside the reference set.
Wiring it in¶
- Choose a labelled reference set with communities known from outside the graph.
- Nightly, query interactions among reference users over a fixed window, and compute the clustering's disagreement rate on held-out reference users.
- Decide before the publish step:
from grounded_decision.examples.community_detection import build, seed_set_evidence
from grounded_decision.types import Event
module = build() # scheduled_refresh -> publish_community_labels
record = module.decide(
Event("scheduled_refresh", {"graph": "nightly"}),
seed_set_evidence(
known_communities, # one community id per reference user
interactions, # index pairs of reference users who interacted
todays_disagreement_rate=held_out_rate,
),
)
if record.verdict == "act":
publish(labels)
else:
mark_stale_and_file(record.reason)
publish and mark_stale_and_file are your own functions. Persist
record.to_dict() with the job run.
- The policy also accepts
analyst_request, which proposesshare_labels_with_analystunder the same checks.
Run it yourself¶
uv run grounded-decision examples community_detection
uv run grounded-decision examples community_detection --json
How to read the report:
Example library: reading a report. HOLD
and hold_for_human in the output are this page's "hold" (the record's
verdict field says abstain). THIN marks night 2's evidence and
FLICKER night 3's (inside the knife-edge window).
Further reading¶
- Naive vs grounded: the same pattern across cases.
- Build evidence from your data and Choose thresholds and calibration.
- Theory: recovering a label from related cases (Kesten–Stigum), knife-edge densities (Friedgut–Kalai), conformal prediction.
Results this case relies on
| Check | Result | Math catalog number | Trust level of the check |
|---|---|---|---|
| Neighbour agreement | Kesten–Stigum reconstruction | 229 | proven (lean) above the line; holding at or below it is policy (paper on a failing row) |
| Knife-edge | Friedgut–Kalai sharp thresholds | 186 | practical (operational): the proven width is far wider than 1 at this size |
| Unusual cases | Split conformal prediction | — | published |
| Policy shape and progress | Star height; parity and mean-payoff games | 134, 104 | proven (lean) |