Graph-based Clustering

By default, Kanoniv uses simple clustering (union-find with transitive closure) to group matched records into entities. This works well when your match threshold is high and your data is clean. But transitive closure has a known weakness: it can chain together records that have no direct relationship.

Graph-based clustering solves this by building a weighted graph of match decisions, dropping weak edges, and checking that every cluster is internally coherent before finalizing it.

The Problem with Transitive Closure

Consider three records:

• A and B match at confidence 0.95 (strong match - same email, similar name)
• B and C match at confidence 0.62 (weak match - similar name only)
• A and C were never directly compared (different blocking keys)

With simple clustering (transitive closure), all three end up in the same cluster: A matches B, B matches C, therefore A and C are the same entity. But A and C might be completely different people who happen to share a weak connection through B.

Simple clustering (transitive closure):

  A ──0.95──> B ──0.62──> C
  └─────────────────────────┘
         Same cluster

Graph-based clustering:

  A ──0.95──> B    C  (separate)
  └───────────┘    └┘
   Cluster 1    Cluster 2

  Edge B-C dropped (0.62 < min_edge_weight 0.7)

This problem gets worse at scale. In a dataset with 100,000 records, a single weak link can merge two large clusters that have nothing in common.

Configuration

Add a clustering block inside your spec's decision section:

decision:
  thresholds:
    match: 0.85
    review: 0.6
  clustering:
    method: graph          # or "simple" (default, backward compatible)
    min_edge_weight: 0.7   # drop edges below this confidence
    min_cluster_coherence: 0.6  # avg internal weight threshold
    max_cluster_size: 100  # force coherence check above this

Parameters

Parameter	Type	Default	Description
method	string	simple	Clustering algorithm: simple (union-find) or graph (weighted graph)
min_edge_weight	float	0.7	Drop edges with confidence below this value before clustering
min_cluster_coherence	float	0.6	Split clusters whose average internal edge weight falls below this
max_cluster_size	integer	100	Force a coherence check on any cluster larger than this

How It Works

Graph-based clustering runs in four steps after scoring and decision:

Step 1: Build the weighted graph

Every match decision becomes an edge in a weighted graph. The weight is the pair's confidence score.

Records:  A    B    C    D    E

Edges:
  A -- B  (0.95)
  B -- C  (0.62)
  A -- D  (0.88)
  D -- E  (0.91)

Step 2: Drop weak edges

Any edge with weight below min_edge_weight is removed. This prevents weak transitive chains from forming.

min_edge_weight: 0.7

  A -- B  (0.95)  KEEP
  B -- C  (0.62)  DROP
  A -- D  (0.88)  KEEP
  D -- E  (0.91)  KEEP

After filtering:

  A -- B  (0.95)
  A -- D  (0.88)
  D -- E  (0.91)
  C        (isolated)

Step 3: Find connected components

The remaining graph is partitioned into connected components. Each component becomes a candidate cluster.

Cluster 1: {A, B, D, E}
Cluster 2: {C}  (singleton)

Step 4: Check coherence

For each cluster, compute the average internal edge weight - the mean confidence across all edges within the cluster.

Cluster 1 edges: A-B (0.95), A-D (0.88), D-E (0.91)
Average weight:  (0.95 + 0.88 + 0.91) / 3 = 0.913

min_cluster_coherence: 0.6
0.913 >= 0.6 -> KEEP cluster intact

If a cluster's average weight falls below min_cluster_coherence, the engine splits it by removing the weakest edges until all sub-clusters are coherent.

The max_cluster_size parameter forces a coherence check on large clusters even if they would otherwise pass. This catches cases where a few strong edges mask many weak ones in a large cluster.

Practical Examples

Conservative: High-confidence matching

When you need high precision and can tolerate lower recall (financial data, healthcare):

decision:
  thresholds:
    match: 0.90
    review: 0.70
  clustering:
    method: graph
    min_edge_weight: 0.85
    min_cluster_coherence: 0.80
    max_cluster_size: 50

This configuration aggressively drops weak edges and requires strong internal coherence. Clusters will be smaller and more precise.

Balanced: General customer data

A good starting point for most use cases:

decision:
  thresholds:
    match: 0.85
    review: 0.60
  clustering:
    method: graph
    min_edge_weight: 0.70
    min_cluster_coherence: 0.60
    max_cluster_size: 100

Permissive: Marketing deduplication

When recall matters more than precision (you would rather over-merge than miss duplicates):

decision:
  thresholds:
    match: 0.75
    review: 0.50
  clustering:
    method: graph
    min_edge_weight: 0.55
    min_cluster_coherence: 0.50
    max_cluster_size: 200

Comparing Simple vs Graph Clustering

Run both methods on the same data to see the difference:

from kanoniv import Spec, Source, reconcile

sources = [
    Source.from_csv("crm", "crm_contacts.csv"),
    Source.from_csv("billing", "stripe_customers.csv"),
    Source.from_csv("support", "zendesk_users.csv"),
]

# Run with simple clustering
spec_simple = Spec.from_file("spec-simple.yaml")
result_simple = reconcile(sources, spec_simple)

# Run with graph clustering
spec_graph = Spec.from_file("spec-graph.yaml")
result_graph = reconcile(sources, spec_graph)

print(f"{'Metric':<25} {'Simple':>10} {'Graph':>10}")
print("-" * 47)
print(f"{'Clusters':<25} {result_simple.cluster_count:>10} {result_graph.cluster_count:>10}")
print(f"{'Merge rate':<25} {result_simple.merge_rate:>10.2%} {result_graph.merge_rate:>10.2%}")
print(f"{'Singletons':<25} {result_simple.singleton_count:>10} {result_graph.singleton_count:>10}")

Typical results:

Metric	Simple	Graph
Clusters	2,233	2,380
Merge rate	65.9%	63.6%
Singletons	432	510
Largest cluster	47	18

Graph clustering produces more clusters (fewer merges) because it breaks weak transitive chains. The largest cluster shrinks significantly - a sign that false transitive merges have been eliminated.

When to Use Graph Clustering

Use graph when:

• You have 3+ sources and transitive chains are a concern
• Your data has many near-threshold matches (scores between 0.60 and 0.85)
• You see suspiciously large clusters in your results
• Precision matters more than recall (financial, healthcare, compliance)
• You are using Fellegi-Sunter scoring, where confidence values are calibrated probabilities

Stick with simple when:

• You have only 2 sources (transitive chains require at least 3 nodes)
• Your match threshold is already very high (0.95+)
• You need maximum recall and accept some false merges
• Performance is critical and you have millions of match decisions

Backward Compatibility

The default clustering method is simple. If your spec has no clustering block, behavior is identical to previous versions. You can add graph clustering to an existing spec without changing any other configuration:

# Before (implicit simple clustering)
decision:
  thresholds:
    match: 0.85
    review: 0.6

# After (explicit graph clustering, everything else unchanged)
decision:
  thresholds:
    match: 0.85
    review: 0.6
  clustering:
    method: graph
    min_edge_weight: 0.7
    min_cluster_coherence: 0.6
    max_cluster_size: 100

Tuning Tips

1. Start with min_edge_weight slightly below your match threshold. If your match threshold is 0.85, try min_edge_weight: 0.70. This filters the weakest matches without being too aggressive.

2. Watch the singleton count. If switching to graph clustering causes a large increase in singletons, your min_edge_weight may be too high. Lower it by 0.05 and re-run.

3. Check your largest clusters. If the largest cluster has 50+ records, something is wrong - either your blocking is too broad or weak transitive chains are pulling unrelated records together. Graph clustering with max_cluster_size: 50 will catch this.

4. Use evaluate() with ground truth. The best way to compare clustering methods is with labeled data:

result_simple = reconcile(sources, spec_simple)
result_graph = reconcile(sources, spec_graph)

eval_simple = result_simple.evaluate()
eval_graph = result_graph.evaluate()

print(f"Simple  - P: {eval_simple.precision:.3f}  R: {eval_simple.recall:.3f}  F1: {eval_simple.f1:.3f}")
print(f"Graph   - P: {eval_graph.precision:.3f}  R: {eval_graph.recall:.3f}  F1: {eval_graph.f1:.3f}")

Graph clustering typically improves precision (fewer false merges) at a small cost to recall (some true matches at the boundary get separated).

Next Steps

• Tuning Match Quality - Systematic workflow for improving precision and recall
• Scoring Strategies - How composite scores are calculated
• Decision - Full decision block reference
• Identity Graph - How Kanoniv builds and maintains the identity graph