This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
ADR 0113: Representative density graph: unlabeled×unlabeled + unlabeled×representative pairwise computation (semisupervised-v3)
Status: accepted Date: 2026-10-15
Context
Every owner_face_recognition run rebuilds the cosine threshold graph over ALL faces of the embeddings feed — L labeled anchor faces (owner-confirmed assignments) plus the U-face unlabeled pool — via clustering._density_graph: blockwise float32 tiles, label-broadcast cannot-link, never a full N×N matrix (memory-safe since ISSUE-081 / PR#975; measured n=26213: 12 s, 2.4 GiB peak for the graph alone, adjacency byte-identical to brute force), but still all-pairs O((L+U)²·d) arithmetic over every pair of faces in the feed. fetch_owner_face_embeddings (main.py) delivers the ENTIRE labeled+unlabeled library on every run, so the steady state after a handful of new photos is a graph over ~22k nodes (owner library, ISSUE-133) and a full run costs 10–14 min of sustained CPU; any library change re-arms the run through the 60 s FaceRecognitionReconcileScheduler (10-min RE_ARM_INTERVAL debounce). The ADR 0108 multi-representant representation already exists and is CV-measured as the BETTER identity summary: per person, the deterministic average-linkage decomposition (cosine, Lance-Williams updates, row-major argmin ties) of its assigned usable faces cut at representative_split_distance (V155, default 0.50), one unit-mean centroid per subcluster; owner-library CV (2796 faces / 36 persons) measured top-1 97.0% / wrong-suggest 2.7% at 0.50 versus 86.3% / 8.7% for the single centroid, with the dominant Christian-to-Nathalie (51x) and Christian-to-Jesper (40x) confusions dropped below 3. Yet the representatives are used ONLY for the B-outcome pessimistic target choice (ADR 0106/0108, 97 representatives for the 1142-face person at 0.50); the threshold graph itself still carries every raw anchor face as a labeled node. _person_representatives is additionally recomputed from scratch on every run over the whole labeled library — deterministic on unchanged input, O(n²)-memory / O(n³)-time per person, minutes at cap-sized persons (REPRESENTATIVE_SPLIT_MAX_FACES = 2000). This ADR therefore turns the graph into BOTH a performance decision and an identity-structure decision: the spec 050 outcome gates read anchor adjacency from the graph (qualifying(u) = identities with ≥1 adjacent anchor; wholeGroup(U) = identity adjacent to EVERY unlabeled member) and group formation (v1 greedy clique growth, v2 constrained HAC per ADR 0104) reads the same edges, so swapping raw anchors for representatives changes edge sets in edge cases and therefore candidate payloads, churn-suppression keys and review traffic — it is NOT a pure optimization and must ship as a new method with a contract-version bump, never as a silent in-place change of v2.
Decision
V1 — New registry method, coexistence, no default change: clustering.py registers SEMISUPERVISED_V3_METHOD = "semisupervised-v3" in CLUSTERING_METHODS and SINGLE_PASS_METHODS alongside v1/v2; the owner selects it per domain via discovery_domains.clustering_method (PeopleClusteringResetController allowlist, Core processing-mode routing and the WorkerResultService isSemisupervised matrix gain v3). v1 and v2 stay byte-identical and remain selectable; DEFAULT_CLUSTERING_METHOD is untouched; the operator off-switch is simply staying on (or returning to) v2 — v2 code is never modified by this ADR.
V2 — Graph construction (the core change): per (modelName, modelVersion) pair, the threshold graph node set is U ∪ R — the unlabeled pool plus one node per ADR 0108 representative of every person in the pair (R = union of all persons' representatives at the job-snapshotted representative_split_distance; an over-cap >2000-face person contributes its single centroid, a faceless person nothing) — and the pairwise computation is restricted to the U×U and U×R blocks. No L×L, no L×U, no L×R block is ever computed: anchor faces are NOT graph nodes at all (this is NOT _density_graph over L+U with rows discarded — a block-restricted build over the U∪R node matrix). Each representative node is LABELED with its person id (node_labels entry = person_id, not None), so _density_graph's cannot-link broadcast keeps representatives of different persons non-adjacent exactly as anchors of different persons are today; representative nodes are unit vectors by construction and carry no faceAnnotationId — they are identity evidence, never group members, never consumed, never in any candidate payload. Node order is [U..., R...]. Steady-state pair count drops from (L+U)² to U² + U·R (owner scale, U≈500 / L≈12k / R in the hundreds: ~2 orders of magnitude fewer pairs), and the downstream HAC input shrinks to at most |U| nodes, growing headroom under SCALABLE_MAX_HAC_NODES = 30000 (ISSUE-100, PR#1036).
V3 — Group formation: groups are formed from the U×U SUBGRAPH only — connected components over U nodes (exact by the threshold-graph property) partitioned by the SAME constrained average-linkage HAC as v2 (hac_linkage scalable-exact partition, smallest-index tie break, fail-closed ComponentTooLarge above the cap). Representative nodes never form, extend or split groups. Because v3 groups contain no labeled members, the HAC identity-conflict merge rule is vacuous inside a group; identity separation is carried entirely by the gates (V4) plus representative cannot-link. An unlabeled face adjacent to representatives of two persons qualifies both identities, yielding wholeGroup = ∅ and the ambiguous review-only demotion — the exact density-bridge semantics v1/v2 ship today (test_density_bridge_yields_only_ambiguous_weak_suggestion), now anchored on representatives.
V4 — Outcome gates: _emit_group_candidates is generalized, NOT forked: its labeled-neighbor view (today labeled_offset = len(L), members over L+U indices) is parameterized so that under v3 the labeled neighbors are representative nodes at offsets ≥ len(U), member indices always address the U pool, and qualifying(u) = identities with ≥1 adjacent REPRESENTATIVE of that person; wholeGroup(U) = identity adjacent to EVERY member. A/B/C shapes, the ambiguity demotion (conflictingPersonIds = union of member qualifying sets), ADR 0103 qualityScore, ADR 0106 pessimistic target choice fed by the ADR 0108 model_representatives argument, candidate keys, emission-based consumption and run-global physical-face ownership are unchanged — v1/v2 call sites keep byte-identical behavior, pinned by their existing suites. The known representational distortion is accepted explicitly: an unlabeled face within threshold of a raw anchor but marginally beyond from all of that person's representatives loses its qualifying edge (and vice versa); ADR 0108's CV shows representative distance is the more robust summary (systematically shrinks distances; correct top-1 median 0.325 vs 0.409), the split threshold remains an owner setting, and the suggest-band recalibration knob (suggest_max_distance) remains the operator's post-deploy lever — no recalibration ships with this ADR.
V5 — Contract versioning: v3 stamps clusteringContractVersion = 2 (new constant SEMISUPERVISED_V3_CONTRACT_VERSION; the accepted (method, version) matrix becomes v1@1, v2@1, v3@2), enforced fail-closed on both sides: the worker handler rejects an explicitly requested semisupervised job with an unsupported version (existing unsupported_clustering_contract issue path) and Core's WorkerResultService — today hard-requiring the integral version 1 for every semisupervised payload — validates against the matrix instead. Justification for the bump: candidate SHAPES are unchanged (ADR 0103/0106/0108 optional fields ride along), but candidate CONTENT is derived from different adjacency semantics (representative adjacency instead of raw-anchor adjacency), and the version exists exactly so a stale enqueue payload or an older worker fails closed rather than silently mixing gate semantics (ADR 0104 D1 principle). Enqueue snapshots the version per method (WorkerJobEnqueueService); in-flight jobs keep their frozen settings stamps (ADR 0104 D6 semantics), so a mid-stream method switch never reinterprets a running job.
V6 — Representative caching (sub-decision, method-independent — it benefits v2 immediately): stop recomputing _person_representatives per run when the input did not change. Cache source of truth: the ADR 0109 persisted person_instance_representatives set (V156, full-replaced in the candidate-ingestion transaction of every completed run). Per (model pair, person) the worker computes a face-set fingerprint = hash over the sorted pair-local accepted usable faceAnnotationIds plus (representative_split_distance, modelName, modelVersion) — sound because accepted-face embeddings are immutable within a model pair (a re-embedding ships a new modelVersion); the worker ships the fingerprint as an additive per-person field on the personRepresentatives envelope (validated fail-closed like the rest of the field, ADR 0109 style; V156 gains a nullable fingerprint column by migration), and the next run reuses the persisted [(centroid, cluster_size)] list on a fingerprint hit. Any miss — face added/removed, split threshold changed, model pair changed, cap crossing, absent set (fresh person, pre-v3 owner) — falls back to today's full recompute, and the run's envelope full-replaces the set (ADR 0109 empty-array-is-a-replacement semantics unchanged). A cache hit must return byte-identical output to a recompute (decomposition is a pure function of usable embeddings + split threshold, both fingerprinted); parity is a test gate (validation plan G4). The worker-side plumbing choice (embeddings feed vs settings payload for delivering the persisted set) is implementation planning, not a decision of this ADR.
V7 — Explicit scope limits: (a) the win requires U ≪ L+R: in the bulk-import regime (U ≈ N) the U² term dominates and today's cost remains — the bulk lever is approximate nearest-neighbor indexing (e.g. HNSW over the persisted representatives and pool), recorded as the follow-up alternative, NOT part of this ADR; (b) no feed-level incrementality here: the API still ships the whole library every run — the recorded future path is per-run feeds of new/changed faces only plus persisted representatives as the identity summary (steady state O(U² + U·R) at the FEED level), which requires API-side dirty-face bookkeeping out of scope; (c) no default change, no qualityScore refit, no suggest-band recalibration, no v1/v2 behavior change, no tentative-semantics change (ADR 0102 untouched: tentative faces remain movable pool members).
Consequences
Expected wins: at the owner steady state (U≈500, L≈12k, R in the hundreds) the per-pair graph work falls from ~(L+U)²/2 ≈ 7.8e7 pairs to U²/2 + U·R ≈ 5e5 pairs — roughly two orders of magnitude — HAC partitions at most |U| nodes instead of |L+U|, and the fingerprint-keyed representative cache removes the per-run O(n³)-time / O(n²)-memory decomposition for unchanged persons (minutes of redundant CPU per run at cap-sized persons, plus the same win for existing v2 operators). The validation plan targets a <60 s full steady-state run on the 16 GB deploy host versus the 10–14 min of ISSUE-133. Costs: gates are re-derived from representative adjacency, so this is identity-structure change with an optimization payoff — edge sets differ from v2 in edge cases, candidate payloads and churn-suppression keys shift accordingly, and review traffic moves with them (v2 stays the untouched comparison baseline and the operator rollback); one more registry method plus the (method, contractVersion) matrix on both worker and Core sides; the personRepresentatives envelope and V156 gain an additive fingerprint field/column; and the ADR 0108 confusion-hub watch item sharpens — representatives are now gate evidence, so a hub person's broad representatives can qualify more faces (monitored via the wrong-suggest and per-person regression gates of the validation plan). Representative-induced edge flips near the threshold are an accepted, documented distortion (V4), mitigated by the CV-measured robustness of representative distance and the existing suggest_max_distance recalibration lever, deliberately deferred to post-deploy measurement. Operational: v3 ships dark (registry/allowlist/matrix additions only, no default change), the operator A/Bs per domain and can always fall back to v2; already-persisted v2/v1 candidates are never retro-affected (results persist per job stamp). Follow-ups recorded, not scheduled: ANN indexing for the bulk regime, feed-level incremental recognition (dirty faces + persisted representatives), representative-cache adoption by the API read path.
Memories Wiki
Using Memories
- Accounts, the Library Hub, and Data Export
- Albums and Automatic Suggestions
- Explore and Discovery Domains
- The Media Viewer
- People and Faces
- Places and Map
- Plants (In Development)
- Datenschutzerklärung (Privacy Policy)
- Fast, Progressive Image Loading
- Search
- Sharing and Households
- Timeline and Photos
- Uploading and Import
Self-Hosting
- Backup and Restore
- CLI Password Reset
- Deployment Architecture
- Known Issues and Operator Diagnostics
- Map Tiles and Place Data Privacy
- Storage Layout
- Upgrades and Versioning
- Workers
Reference