When two patients, users, or records share only a few observed features, the similarity between them is unreliable. Two users who agree on a single obscure item get a correlation of 1.0. The standard fix, called significance weighting, multiplies the similarity by a penalty that grows with the number of co-observed entries, for example "full confidence once 50 items overlap." That penalty depends only on the count. It ignores something that often matters more: whether the missing entries can be predicted from the ones that are present. If a patient's missing albumin is almost determined by her observed labs, a low overlap costs little. If the missing features are unpredictable, even a moderate overlap should be distrusted. This proposal replaces the count-based penalty with one computed by multiple imputation. Multiple imputation fills each gap several times with plausible values drawn from a model of the data. We compute the similarity on every completed copy and treat the spread across copies as the uncertainty of the similarity. We then rank neighbors by a pessimistic, variance-penalized score rather than by the raw or count-discounted value.
In two sentences: generate $K$ plausible completions of the sparse data, compute each pairwise similarity $K$ times, and down-weight pairs whose similarity swings across completions. The penalty therefore reflects how much the missing data could change the answer, not merely how much data is missing. The cost is roughly $K$ times more storage and compute, so we measure where this pays off on an accuracy-versus-cost frontier, and we test whether a cheap single-model variance estimate does just as well.
Core Claim
The significance-weighting literature has converged on count-based penalties of the form $r'_{uv} = r_{uv}\, w(|I_u \cap I_v|)$. This includes heuristic weighting that protects neighbor pools (Prugel-Bennett et al., Ma et al.), explicit confidence coefficients (Su et al.), proportional variants that normalize by each user's activity (Sun et al.), and empirical-Bayes shrinkage toward zero (Ning et al., Zhang et al.). These papers motivate the proposal: they show that low-overlap similarity is harmful. They also leave its two admitted weaknesses open. The saturation thresholds are arbitrary, and the penalty is blind to which entries are missing.
The closest method is PRISM. PRISM learns a deterministic per-feature confidence from global missingness and time since last measurement, and uses it to weight patient similarity before building prototype cohorts. PRISM's confidence is a point estimate per feature. It does not ask how much a particular pair's similarity would change under plausible values of that pair's missing entries.
We use Rubin's combining rules, which merge estimates across imputed datasets, to define the weight. Let $s^{(m)}_{uv}$ be the similarity between entities $u$ and $v$ on completed dataset $m = 1,\dots,K$. Let $\bar s_{uv}$ be their mean, $B_{uv}$ their variance across completions, and $W_{uv}$ the ordinary sampling variance of the similarity on one completed dataset. We rank neighbors by
$$\tilde s_{uv} = \bar s_{uv} - \kappa \sqrt{W_{uv} + (1 + 1/K)\, B_{uv}},$$
where $\kappa \ge 0$ sets how pessimistic the ranking is. The term $B_{uv}$ is the new part. It is small when the imputation model is confident about the entries that matter for that pair, and large otherwise.
The claim is falsifiable. The gain should appear specifically in pairs that have low overlap but highly predictable missing features. In pairs where the count-based and imputation-based uncertainty agree, the two methods should tie.
Research Program
The method supplies its own engine: fully conditional specification, also called MICE (multivariate imputation by chained equations). MICE imputes one variable at a time from the others and draws values rather than inserting means. We choose it because a 73-method, 24-dataset benchmark found that mice_cart, mice_pmm and mice_rf recover data distributions better than deep generative imputers (Do we Need Dozens of Methods). That finding matters here because a variance-based weight is only as honest as the spread of the imputations. Mean-like imputers, which score well on RMSE while collapsing variance, would produce $B_{uv} \approx 0$ and silently undo the weighting. As a second engine we use RefiDiff, a tree warm-up followed by diffusion refinement that is reported to be about 4× faster than DIFFPUTER. With it we check that the conclusions do not hinge on MICE.
We build three things. The first is the scoring rule above, applied to Pearson and cosine similarity, with $\kappa$ chosen on validation data. The second is a cheap approximation: a single imputation model that outputs per-cell predictive variances, propagated to $B_{uv}$ by a first-order expansion of the similarity. This removes the need for $K$ stored copies, and it is the obvious thing a reviewer would ask for.
The third is a cost-aware implementation, and it is where the hybrid-memory literature enters as a constraint rather than a centerpiece. Hybrid memory means pairing a small fast tier (DRAM) with a large slower tier (non-volatile or far memory). Storing $K$ completions of an $N \times p$ matrix multiplies memory by $K$. The observed cells are identical across copies, so we store them once. The $K$ draws for each missing cell are stored contiguously, so that scoring one pair reads one block. We place the read-only draw array in a capacity tier and the per-query candidate lists in DRAM.
This follows the object-granularity placement of Hassan et al., who report under 3.9% slowdown against DRAM-only while saving up to 81.5% energy against NVM-only. It also follows the static-versus-dynamic split of NGraph, which reaches roughly 84% of pure-DRAM performance with read-mostly data in NVM. Our case differs from both: the "static" object is a posterior sample, not an edge list, and it is written once after imputation and never updated. That write-once pattern suits wear-limited media. Whether this layout matters at all depends on scale, and we report that honestly.
Multi-objective optimization serves as the evaluation lens. Here $K$ and $\kappa$ trade retrieval quality against memory and time, and those objectives conflict. We report the non-dominated set: configurations where no objective can improve without another getting worse. Following Optimal Scalarizations for Sublinear Hypervolume Regret, we sweep configurations with hypervolume scalarization rather than a fixed linear weighting. That paper shows linear weightings cannot reach concave parts of a frontier. We expect such concave regions here, because quality likely saturates in $K$ while cost grows linearly.
Baselines
The naive reference point is unweighted similarity on whatever is observed, plus a single deterministic imputation (mean, or last observation carried forward) followed by plain similarity. Both run on the identical splits and feature sets. Their role is to show that the problem exists on our data. Beating them is necessary but not interesting.
The strongest classical competitor is a tuned count-based penalty. It takes the best of three forms: a saturating threshold $\min(n, \tau)/\tau$ (Prugel-Bennett et al.), proportional weighting (Sun et al.), and James-Stein-style shrinkage (Zhang et al.). We also include a Fisher-z lower confidence bound on the overlap-only correlation. The threshold $\tau$, the shrinkage constant, and the bound level each get the same validation tuning budget as our $\kappa$. This is the baseline most likely to tie us, because on many datasets predictability and overlap are correlated. Beating it means a statistically reliable improvement in downstream metrics, and specifically in the low-overlap, high-predictability stratum defined below.
The strongest learned competitor is PRISM on MIMIC-III, MIMIC-IV, PhysioNet Challenge-2012 and eICU. PRISM reports relative AUPRC gains of up to 6.40% for in-hospital mortality and 1.38% for 30-day readmission over its best baselines, and robustness at 97.47% feature missingness. No reported result was found on Lacuna for PRISM's absolute AUPRC values. We will therefore rerun PRISM with its published configuration on our splits.
The comparison is structural. We keep PRISM's architecture fixed and replace only its confidence-weighted patient similarity with $\tilde s_{uv}$. We give both variants equal training epochs and hyperparameter trials. Beating PRISM means higher mortality and readmission AUPRC with the swap, on at least three of the four datasets.
Three ablations isolate the key ingredient. The first sets $B_{uv} = 0$ while keeping everything else, which is ours minus the imputation variance. The second replaces multiple imputation with a single draw. The third keeps $B_{uv}$ but uses a variance-collapsing conditional-mean imputer. If the second or third matches the full method, the imputation spread is not doing the work.
Why not just…?
Why not just tune the count-based penalty's threshold per dataset? This is the most serious threat. A tuned threshold removes the "arbitrary constant" complaint without any imputation. The proposal's value then rests entirely on pairs where count and predictability disagree. We construct that stratum explicitly, and if the tuned threshold matches us there, we will report that the count is sufficient. The imputation benchmark gives some reason for optimism, because real tabular data has strong cross-feature dependence that tree-based chained equations exploit (Do we Need Dozens of Methods). That dependence is exactly what a count cannot see.
Why not just impute once and compute ordinary similarity? Single imputation fills gaps with fitted values and then treats them as data. That understates uncertainty, so similarity on filled-in entries looks as trustworthy as similarity on measured ones. The biobank analysis of Chen et al. shows the downstream consequence in a related setting: plugging ML predictions directly into association tests produced a 100% Type I error rate in almost all scenarios. The single-draw and conditional-mean ablations test the similarity analogue directly.
Why not just get the variance from one probabilistic imputation model instead of storing $K$ copies? This is also a real threat, and if it wins it is the better outcome, because it removes the memory problem. A first-order propagation of per-cell predictive variances ignores dependence between a pair's missing cells, and similarity is non-linear in them. We compare the analytic $B_{uv}$ against the $K$-sample estimate. We report where on the cost frontier each sits. If the approximation is within noise, we recommend it and drop the tiered-memory layout.
Why not just let PRISM-style learned confidence absorb this? PRISM's confidence is per feature and per patient history. It is not per pair, and it is trained end to end on one clinical objective. The swap experiment above tests whether a pair-level uncertainty adds anything on top of an architecture that already learns confidence.
Proposed Experiments
The first check is controlled. On fully observed tables from the imputation benchmark (airfoil, concrete, adult, diabetes) and the RefiDiff datasets (California, Magic, Letter, Adult, Default), we mask entries under MCAR, MAR and MNAR at 50–95% missingness. Because the data were fully observed before masking, we know the true pairwise similarity. We measure how well each method's penalty tracks the actual error of the similarity estimate (rank correlation between penalty and absolute error). We also measure neighbor recall@k against the true nearest neighbors.
Pairs are stratified by overlap and by the imputation model's out-of-sample $R^2$ on the pair's missing features. The decisive prediction is a gain concentrated in the low-overlap, high-$R^2$ cell and a tie in the rest. A uniform small gain, or no gain, would falsify the mechanism.
The MNAR condition addresses the most direct contradiction to this idea. Chen et al. prove that imputation-based inference stays unbiased under MNAR only when prediction error is independent of missingness. When that fails, our imputations can agree with each other and still be wrong, producing confidently wrong neighbors. We expect the count-based penalty to be more robust there, and we will report the crossover missingness strength at which it overtakes us.
The second check is applied. On MIMIC-III, MIMIC-IV, Challenge-2012 and eICU we evaluate two things: k-nearest-neighbor mortality prediction on its own, and PRISM with its similarity replaced, both scored by AUPRC and stratified by patient missingness rate.
The third check is the cost frontier. For $K \in \{1, 5, 10, 20, 50\}$ and a grid of $\kappa$, we record neighbor recall, downstream AUPRC, peak memory and wall-clock time. We compute the hypervolume of the non-dominated set for three variants: the full method, the analytic-variance approximation, and the tuned count baseline. We run the tiered layout against a DRAM-only run and against plain operating-system paging at a synthetic scale-up of the EHR cohort. The purpose is to report whether tiering changes which configurations are non-dominated. If it does not at realistic cohort sizes, we will say so and treat the memory layout as unnecessary.
References
- Novel Significance Weighting Schemes for Collaborative Filtering: Generating Improved Recommendations in Sparse Environments
- Effective missing data prediction for collaborative filtering
- Rating Prediction in Recommender Systems Based on User Behavior Probability and Complex Network Modeling
- QoS prediction for Web service in Mobile Internet environment
- Trust Your Neighbors: A Comprehensive Survey of Neighborhood-Based Methods for Recommender Systems
- A Hybrid Interpolation Weighted Collaborative Filtering Method for Anti-cancer Drug Response Prediction
- PRISM: Mitigating EHR Data Sparsity via Learning from Missing Feature Calibrated Prototype Patient Representations
- Do we Need Dozens of Methods for Real World Missing Value Imputation?
- RefiDiff: Progressive Refinement Diffusion for Efficient Missing Data Imputation
- Software-managed energy-efficient hybrid DRAM/NVM main memory
- NGraph: Parallel Graph Processing in Hybrid Memory Systems
- Optimal Scalarizations for Sublinear Hypervolume Regret
- Prediction-based Inference in Electronic Health Record (EHR)-linked Biobanks