Partition Voting: Making Random Forests Vote on Whole Clusters, Not Pairs

Entity resolution means deciding which records in a database refer to the same real-world thing. Most systems do it in two steps. A classifier first scores pairs of records as "same" or "different", and then the system takes the transitive closure: if A matches B and B matches C, all three become one entity. The second step is fragile. A single wrong pairwise "match" acts as a bridge that welds two unrelated entities together, and the damage compounds as databases grow. Barnes et al. show that non-matching pairs grow quadratically while true matches grow linearly, so precision can collapse when a system tuned on hundreds of records is run on thousands (Performance Bounds for Pairwise Entity Resolution). The fix that works best today is cluster editing: an integer program that adds and deletes edges until every group is fully consistent. It is NP-hard, so its users drop every connected component larger than 50 records (Exploiting Transitivity for Entity Matching).

We propose a cheap alternative that uses something a random forest already has: many partly independent trees. The usual pipeline averages the trees' votes on each pair and only then takes the closure, so whatever bridge survives the average gets amplified. We reverse the order. Each tree's thresholded votes define its own match graph, we take the transitive closure separately for each tree, and we then measure, for every pair of records, the fraction of trees in which they land in the same entity. A false bridge that only some trees believe in then fails to propagate through the other trees' closures. A true but weakly scored match that many trees reach through different paths is kept. Because the averaged quantity is a mixture of equivalence relations, it has a structural guarantee that averaged pair probabilities lack, and that guarantee allows fast clustering with no size cap.

Core Claim

Let a forest have $T$ trees. Each tree $t$ thresholds its leaf estimate on each candidate pair to give a match graph $G_t$, whose connected components form a partition $\pi_t$ of the records. Define the co-association

$$C(i,j) = \frac{1}{T}\sum_{t=1}^{T} \mathbf{1}[\pi_t(i) = \pi_t(j)],$$

the fraction of trees whose own transitive closure puts records $i$ and $j$ in the same entity. Each indicator $1-\mathbf{1}[\cdot]$ is a pseudo-metric, because "different blocks of a partition" obeys the triangle inequality. A convex combination of pseudo-metrics is again one, so $1 - C$ satisfies $d(i,k) \le d(i,j) + d(j,k)$ by construction. Averaged pair probabilities have no such property.

This gives two outputs. The first is a hard, transitively consistent clustering at a confidence level of our choosing. At the strict end, the common refinement of all $\pi_t$ (records together only if every tree's closure agrees) is itself a valid partition and needs no $k$. The second is a metric-consistent weight matrix for fast, randomized pivot-style correlation clustering. Such clustering is better behaved on weights that respect the triangle inequality, which here replaces the integer program.

The central empirical claim follows. Closing each tree before aggregating cuts false bridges that averaging-then-closing keeps. The advantage should grow as tree errors become less correlated and as the database grows. The first prediction comes from the ensemble-variance identity $\rho\sigma^2 + (1-\rho)\sigma^2/B$ in the research file: only the decorrelated part of bridge errors is filtered. The second comes from Barnes et al.'s quadratic growth in opportunities for false bridges.

Relation to Prior Work

The closest relative is the Minimum Spanning Random Forest of Generalized Transitive Distance with Minimum Spanning Random Forest. It builds many perturbed spanning trees over a fixed distance graph and max-pools their path distances so that a noise bridge in one tree is "stretched back out." It supplies our core intuition: diversity across trees suppresses bridges. We differ in three ways. Our trees are supervised decision trees trained on record attributes with bagging and feature subsampling, not spanning trees over precomputed affinities. We aggregate equivalence relations rather than path distances. And our output yields discrete classes directly, whereas their ultrametric needs $k$-means with a chosen $k$, which suits entity resolution poorly because the number of entities is unknown.

Baas et al. supply the strongest method and the benchmark. Their cluster editing turns classifier log-odds into signed edge weights and solves an integer program per component. They used only SVMs and logistic regression, and they discarded components over 50 records. We keep their objective as the quality reference and attack its cost.

Two lines of work motivate the proposal but also limit it. Raad et al. flag bad owl:sameAs links from graph topology alone, using community bridges and link symmetry (Detecting Erroneous Identity Links on the Web Using Network Metrics). They report that topology fails on naturally sparse communities and on intermediate-confidence links. MultiEM prunes density outliers after hierarchical merging (MultiEM), which by design cannot split two dense clusters joined by one bridge. Both point to a need for an attribute-aware signal about bridges, and that is what per-tree closure provides.

Wick et al. show that scoring whole clusters beats pairwise closure (Learning Field Compatibilities to Extract Database Records from Unstructured Text). We take the same lesson but obtain cluster-level evidence without hand-built set features.

Machamp evaluates random forests only as isolated pair classifiers (Machamp). It also finds pretrained language-model matchers stronger at the pair level, a fact we treat as a constraint below. Finally, (RF)² uses forests inside random-field inference for spatial labeling ((RF)^2 - Random Forest Random Field). It shows forests can drive structured inference, but it does not deal with transitivity.

Research Program

We build the pipeline on the candidate pairs produced by a fixed blocking step. For each tree, union-find over the candidate edges gives its partition in roughly linear time in the number of edges. Computing $C$ only over candidate pairs plus pairs inside final components keeps memory sparse. On top of $C$ we study three decoders. The first is a quantile rule: link a pair if $C \ge q$ and take components. This is not transitive by itself, but it is cheap and serves as a probe. The second is the strict meet of all tree partitions together with its relaxation to a random subset of trees. The third is randomized pivot correlation clustering with weights $C - \tfrac{1}{2}$, which carries no cap on component size.

We will also measure how bridge-error correlation $\rho$ across trees depends on the forest's design: feature subsample size, bootstrap fraction, and depth. The aim is to test whether $\rho$ predicts the size of the gain from per-tree closure.

On the theory side, we will try to bound the probability that a single bridge survives into the final clustering in terms of per-tree bridge rates and $\rho$. We will then relate this bound to Barnes et al.'s precision lower bound as $N$ grows.

Baselines

The naive reference is the standard pipeline: average the forest's probabilities, threshold, and take transitive closure. It is what practitioners run, and it isolates exactly the ordering we change. A second naive point is the same pipeline with an aggressively raised threshold.

The strongest existing method is Baas et al.'s weighted cluster editing solved exactly by integer programming. For fairness, it receives the same averaged forest probabilities as input, in addition to their SVM. We run it under their 50-record cap, and also with a time budget equal to five times our method's wall-clock time on uncapped components, so it gets a generous compute allowance. On Ecartico the reported figure to beat is the maximum $F_{0.5} = 0.70$ on $D_{10}$ for SVM with cosine similarity plus cluster editing (Exploiting Transitivity for Entity Matching). For the multi-table setting, MultiEM reports an average F1 of 72.0 on Geo, Music, and Shopee (MultiEM). That system is unsupervised, so we report it as context rather than as a like-for-like competitor. On Machamp we found no reported random-forest number in the file. On Barnes et al.'s scaling datasets, the file gives qualitative results only and no numbers.

The ablation that isolates our key ingredient is averaged forest probabilities fed to the same pivot correlation-clustering decoder. It has identical trees and an identical decoder, and differs only in whether closure happens per tree. A second ablation swaps decision trees for bagged logistic regressions with the same bootstrap scheme, to test whether the gain needs trees' diverse, axis-aligned errors or just any bootstrap ensemble. A third ablation is MSRF-style random jitter of a single model's probabilities, which tests whether the diversity must come from training.

All methods share the blocking, features (Baas et al.'s embedding cosine and Hadamard features on Ecartico, attribute similarities elsewhere), training labels, and a fixed hyperparameter search budget on a validation split. Beating the field means two things. We must match exact cluster editing within noise on components it can solve. We must also exceed it in $F_{0.5}$ overall once large components are included, and beat the averaging ablation significantly across seeds.

Why not just…?

Why not just average the forest and run cluster editing or pivot clustering on the averaged probabilities? This is the real threat, and it is the main ablation. If per-tree closure adds nothing over a good decoder on averaged scores, our claim fails, and we will report that. The argument for a difference is that averaging forgets which trees produced which edges. A bridge supported by 60% of trees and a pair reached through many different paths look alike in marginal edge probabilities. They differ in co-association, and only $C$ carries the triangle-inequality guarantee. The prediction that settles it is that the gap should widen as feature subsampling lowers $\rho$ and vanish when all trees are identical.

Why not just raise the threshold? Baas et al. found that higher thresholds avoid linkset explosion but discard fuzzy true duplicates. Barnes et al.'s quadratic argument implies any fixed threshold eventually fails as $N$ grows. Our scaling experiment tests this directly by tuning the threshold at $N=100$ and evaluating at full size.

Why not just prune with topology (Louvain) or density (DBSCAN)? Raad et al. report that topology misjudges sparse niche communities and intermediate-confidence links. Density pruning in MultiEM removes outliers but cannot separate two dense entities joined by one edge. We will inject controlled bridges between dense true clusters, following Raad et al.'s injection protocol, and compare recovery rates.

Why not just use a pretrained language-model matcher? Machamp shows such matchers beat forests on pairs. They still score pairs independently and are equally exposed to closure cascades. Our method only needs an ensemble of diverse pair scorers. As an extension, we will test a bootstrap ensemble of small fine-tuned matchers on Machamp's text-heavy splits to see whether partition voting transfers beyond trees.

Proposed Experiments

On Ecartico $D_{10}$, $D_{25}$, and $D_{50}$ we report $F_{0.5}$, linkset size relative to ground truth, and largest-component size. We report these both on components of at most 50 records and on all components.

On Restaurant, Abt-Buy, Dirty Escort, and the synthetic Gaussian data from Barnes et al., we tune every method at $N=100$. We then evaluate at increasing $N$ and plot precision against $N$ along with their theoretical lower bound. The decisive check is whether partition voting stays at or above the bound where averaging-then-closure crashes.

Across all datasets, we vary feature subsample size to sweep $\rho$. The second decisive check is a positive relationship between decorrelation and the gap between per-tree closure and averaging. If that relationship is absent, our mechanism is not what drives any gain.

Finally, we report wall-clock time against exact cluster editing as component size grows. This tests whether the 50-record cap can be dropped at no loss in quality.