Determining and Handling Missing Data for Graph Machine Learning
Authors
Hansen, Alexander Højgaard ; Pedersen, Freja Herreborg
Term
4. term
Education
Publication year
2024
Submitted on
2024-05-27
Abstract
Graphs capture complex relationships, but missing nodes, edges, and attributes challenge graph machine learning. This thesis investigates how to determine and handle missing data in graphs. We address three questions: (i) how to simulate and identify missingness mechanisms (MCAR, MAR, NMAR) in graphs, (ii) how different mechanisms and missing rates affect downstream tasks, and (iii) whether link prediction can serve as imputation for missing edges. We introduce a simulator for graph missingness and evaluate its impact on a patient graph from MIMIC-IV for sepsis prediction with a GNN. We also study mechanism identification on a Wikidata subgraph using node2vec embeddings with DBSCAN/HDBSCAN clustering and a GCN-based classifier, and we explore clustering of negative embeddings. Empirically, a GraphSAGE sepsis model was largely insensitive to both mechanism and rate even at high missingness, suggesting robustness. Link-prediction imputation did not improve performance under MCAR or MAR and degraded it under NMAR, which may serve as a signal of NMAR. Clustering with node2vec could flag MCAR as noise, while results for MAR and NMAR were inconclusive. A GCN classifier could also detect MCAR but underperformed compared to clustering; clustering of negative embeddings showed structure without firm conclusions. Together, the simulator and detection methods provide practitioners with tools to analyze robustness and gain insight into patterns of missingness in graph data.
Grafer kan modellere komplekse relationer, men manglende noder, kanter og attributter udfordrer grafbaseret maskinlæring. Denne afhandling undersøger, hvordan man bestemmer og håndterer manglende data i grafer. Vi adresserer tre spørgsmål: (i) hvordan man kan simulere og identificere mekanismer for manglende data (MCAR, MAR, NMAR) i grafer, (ii) hvordan forskellige mekanismer og manglerater påvirker efterfølgende opgaver, og (iii) om link-prediktion kan fungere som imputation af manglende kanter. Vi introducerer en simulator for manglendehed i grafer og evaluerer effekten på en patientgraf fra MIMIC-IV for sepsis-prediktion med en GNN. Vi undersøger desuden mekanismebestemmelse på en Wikidata-undergraf via node2vec-indlejringer og klyngedannelse med DBSCAN/HDBSCAN samt en GCN-baseret klassifikator, og vi afprøver klyngning af negative indlejringer. Empirisk var en GraphSAGE-model til sepsis i høj grad upåvirket af både mekanisme og rate selv ved høj manglendehed, hvilket tyder på robusthed. Imputation via link-prediktion forbedrede ikke resultaterne ved MCAR eller MAR og forværrede dem ved NMAR, hvilket kan tjene som et signal om NMAR. Klyngning med node2vec kunne identificere MCAR som støj, mens resultaterne for MAR og NMAR var uklare. En GCN-klassifikator kunne også detektere MCAR, men klarede sig dårligere end klyngningsstrategien; klyngning af negative indlejringer viste struktur uden faste konklusioner. Tilsammen giver simulatoren og metoderne praktikere værktøjer til at analysere robusthed og få indsigt i mønstre af manglendehed i grafdata.
[This apstract has been generated with the help of AI directly from the project full text]