💻 computer science

Knowledge Graph Representations for Robust Patient Stratification under Unknown Missingness Mechanisms: a Comparative Computational Study

This study demonstrates that knowledge graph embeddings provide a more robust and stable patient stratification than traditional imputation-based pipelines under unknown missingness mechanisms, particularly in specialist clinical data where missing values are often Missing Not At Random (MNAR).

Original authors: Francesco Orciuoli, Giuseppe Murdaca

Published 2026-10-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Francesco Orciuoli, Giuseppe Murdaca

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of modern medicine, doctors rely on vast digital records to understand their patients. These electronic health records are a collection of facts: symptoms a patient reports, tests a doctor orders, and results from the laboratory. However, these records are rarely complete. A doctor does not order every possible test for every patient; they order specific tests based on what they suspect is wrong. Similarly, a patient might not mention a symptom if it seems minor or if they forget to bring it up. In the language of data science, this is not just random noise. The missing information is often linked to the very thing that is missing. If a doctor suspects a specific disease, they run the test; if they do not, the test result is simply absent. This creates a tricky situation for computers trying to find patterns in the data. If a computer sees a blank space where a test result should be, it has to guess what goes there. The standard approach is to fill that blank with an average value, assuming the missing data is just a random gap. But in medicine, a missing test is often a deliberate choice, not a random accident. Treating a missing result the same as a confirmed negative result can lead the computer to draw the wrong conclusions about who is sick and who is healthy.

Researchers Francesco Orciuoli and Giuseppe Murdaca set out to solve this problem by testing different ways to represent patient data for computer analysis. They worked with a group of 359 patients from a specialized allergy and immunology clinic in Italy. These patients had complex conditions ranging from chronic hives to autoimmune diseases, and their records were filled with the kinds of gaps described above: some antibody tests were never ordered, and some symptoms were only written down if they were severe. The team wanted to see if they could group these patients into meaningful clusters based on their data, without telling the computer what the final diagnosis was. They compared five different methods. Four of these methods used the traditional approach: they took the raw data, filled in the missing numbers with estimates, and then used a mathematical tool to compress the information into a simpler form before grouping the patients. The fifth method took a completely different path. Instead of filling in the blanks, they built a knowledge graph. In this system, each patient is a point, and every piece of confirmed information is a line connecting that patient to a specific fact. If a test was never done, no line is drawn. The computer simply sees that the connection does not exist, rather than guessing what the connection might be.

The results of this comparison were stark and clear. The traditional method, which involves filling in missing data and then compressing it, performed poorly in almost every scenario the researchers tested. When the missing data followed the realistic pattern found in hospitals—where tests are ordered selectively based on suspicion—this standard method failed to find the correct groups of patients. In the worst cases, the computer's grouping was so poor that it was barely better than random chance. The researchers found that the process of filling in the missing numbers created a false structure in the data. When the computer then tried to simplify this data, it amplified these errors, locking the patients into the wrong groups. It was as if the computer was trying to map a territory based on a map that had been filled in with guesses, and then the mapmaker made those guesses look like solid ground.

In contrast, the knowledge graph approach proved to be the most reliable. Because this method never guesses what is missing, it avoids the trap of creating false patterns. It only uses the facts that are actually there. When the researchers tested this method against the others, it consistently produced the best groups of patients, regardless of how the data was missing. The groups it created made medical sense. For example, it successfully separated patients with respiratory allergies from those with autoimmune diseases, and it identified a large group of patients who had been screened for autoimmune issues but tested negative. To prove these groups were real and not just an artifact of the math, the researchers checked them against seven independent blood markers that were not used to create the groups in the first place. These markers, such as white blood cell counts and inflammation levels, varied significantly across the different groups, confirming that the computer had found genuine biological differences.

The study suggests that when dealing with complex medical records where missing information is common and meaningful, the safest and most effective strategy is to stop trying to fill in the blanks. Instead, researchers should build representations that respect the absence of data as a valid piece of information. The knowledge graph method achieved this by treating a missing test as a missing connection, rather than a zero or an average. This approach allowed the computer to see the true shape of the patient population without the distortion caused by guessing. While the traditional method of imputing data and then reducing its complexity failed repeatedly, the graph-based method remained stable and accurate. The researchers conclude that for specialists working with real-world patient data, where the reasons for missing information are often unknown, using a knowledge graph is a more robust way to understand patient subgroups. This method not only helps in grouping patients for better care but also creates a clear, factual map of the data that can be used by future tools to answer specific medical questions, ensuring that the computer's understanding is built on what is known, not on what is guessed.

Technical Summary: Knowledge Graph Representations for Robust Patient Stratification under Unknown Missingness Mechanisms

Problem Statement
Unsupervised patient stratification pipelines typically rely on a sequence of imputing missing values, applying dimensionality reduction, and clustering. However, in specialist clinical databases, particularly in Allergology and Clinical Immunology, data are predominantly Missing Not At Random (MNAR). Two specific mechanisms drive this:

Test-ordering bias: Autoantibody tests are ordered only when a specific diagnosis is suspected, meaning missing results are dependent on the unobserved disease status.
Selective recording: Symptoms are documented almost exclusively when present and clinically salient; a missing entry does not signify absence but rather a lack of elicitation or relevance.

Standard imputation strategies (e.g., median imputation) treat untested antibodies and confirmed negatives identically, violating their own assumptions. Furthermore, when these imputed values are processed by nonlinear dimensionality reduction techniques like UMAP, the manifold learning algorithms treat the distorted, imputed structure as real, geometrically amplifying the bias. The core challenge is that the missingness mechanism is rarely identifiable in advance, rendering pipelines that perform well under one mechanism but fail under another clinically unreliable.

Methodology
The authors conducted a systematic comparative evaluation of five patient representation strategies under three formally specified missingness mechanisms: Missing Completely At Random (MCAR), Missing At Random (MAR), and MNAR. All methods utilized the same input cohort (352 patients from a 359-patient specialist cohort), the same normalization, and the same clustering algorithm ( $k$ -means with $k=6$ ) to isolate the effect of the representation.

The five strategies evaluated were:

Knowledge Graph (KG) + TransE: Patients are nodes; observed clinical findings (diagnoses, autoantibodies, symptoms) are typed directed edges. Crucially, absent edges carry no semantic content, making the representation valid under MNAR by construction. TransE embeddings (64 dimensions) were generated and clustered.
Tabular NaN-to-Zero: A feature matrix where missing values are encoded as zero (treating untested as negative/absent).
Tabular Median Imputation: Missing values replaced by the population median.
UMAP + NaN-to-Zero: The tabular NaN-to-zero matrix reduced via UMAP before clustering.
UMAP + Imputation: The tabular median-imputed matrix reduced via UMAP before clustering.

The study employed two experimental designs:

Layer-by-Layer Ablation: Progressive addition of information layers (Diagnosis only $\rightarrow$ Diagnosis + Autoantibodies $\rightarrow$ Diagnosis + Autoantibodies + Symptoms) on the real dataset to measure performance degradation as MNAR severity increases.
Controlled Simulation: A simulation study using an "oracle" dataset where missingness was artificially introduced under MCAR, MAR, and MNAR conditions to test robustness across mechanisms.

Key Contributions

Demonstration of Robustness: The study identifies the Knowledge Graph representation as the only method that does not collapse under any of the three missingness mechanisms. It achieved the highest performance floor (NMI $\ge$ 0.395) and the smallest performance range (0.061) across scenarios.
Identification of Pipeline Failure: The standard "impute-then-reduce" pipeline (specifically UMAP + Median Imputation) was found to be the worst-performing strategy in every scenario, reaching an NMI of 0.083 under MNAR—a fivefold gap below the KG approach.
Clinical Application: A systematic application of KG embeddings for unsupervised stratification in Allergology and Clinical Immunology on a real-world cohort, yielding six clinically interpretable clusters.
Empirical Characterization: Quantification of the MNAR structure in the dataset and a layer-by-layer ablation showing the KG's representational advantage grows as MNAR data (autoantibodies and symptoms) are added.
Semantic Layer Utility: Discussion of the patient KG as a persistent semantic layer compatible with Large Language Model (LLM)-based clinical query systems, extending utility beyond clustering.

Results

Simulation Study: Under MNAR, the KG outperformed tabular median imputation by $\Delta$ NMI = +0.121. The UMAP + Imputation pipeline collapsed completely (NMI = 0.083), confirming that manifold projection amplifies imputation bias rather than correcting it. The KG maintained stable performance (NMI $\ge$ 0.395) regardless of the mechanism.
Ablation Study: As MNAR data layers were added, the KG's advantage over the tabular NaN-to-zero baseline widened monotonically, reaching a +63% relative improvement at the symptom layer (3.6% completeness).
Cluster Validation: The six clusters identified by the KG corresponded to recognizable clinical profiles (e.g., Urticaria/Angioedema, Respiratory Allergy, Screening/Antibody-Negative, Organ-Specific Autoimmunity, Unclassified, Inflammatory Rheumatology).
External Validation: Seven independent laboratory biomarkers (not used in graph construction) showed statistically significant differences across the six clusters after Benjamini-Hochberg correction ( $q < 0.01$ ). Notable effect sizes were observed for White Blood Cell count ( $\epsilon^2 = 0.331$ ), ESR ( $\epsilon^2 = 0.218$ ), and Hemoglobin ( $\epsilon^2 = 0.148$ ).

Significance and Claims
The paper claims that when the missingness structure of clinical data cannot be verified in advance—a typical scenario in specialist practice—Knowledge Graph representations are the safer and more robust choice. The study argues that the standard impute-then-reduce pipeline is clinically unreliable under MNAR because it conflates untested data with negative findings and amplifies this error through dimensionality reduction.

The KG approach is presented not merely as a superior clustering tool but as a structural solution to the MNAR problem: by encoding only observed evidence as edges, it avoids the semantic error of imputation entirely. Furthermore, the authors highlight the dual utility of the KG: it serves as a robust input for unsupervised clustering while simultaneously functioning as a human-interpretable semantic layer for LLM-based clinical decision support, allowing for traceable, fact-grounded queries that embedding vectors or imputed matrices cannot provide.

The authors remain modest regarding limitations, noting the single-center nature of the dataset, the use of discretized laboratory values in simulations, and the retrospective nature of the study, which precludes prospective validation of the clusters as outcome predictors. They call for multi-center replication and prospective validation as necessary next steps.

More like this