Budgeted Interactive Property Graph Repair with GNN

Property graphs are powerful data models, yet they often suffer from inconsistencies caused by violations of integrity constraints. Existing repair strategies are either fully automated—struggling with ambiguous cases that require domain expertise—or human-driven, which lack scalability and overlook budget and user heterogeneity. In this work, we propose a novel approach to property graph repair that integrates automatic inference with user expertise. We introduce a Graph Neural Network (GNN)-based difficulty estimator that jointly captures topological and semantic aspects of violations, enabling the system to distinguish between cases suitable for automatic repair and those requiring human input. Building on this, we design a budgeted, difficulty- and user-aware assignment algorithm that allocates violations to users based on their expertise and capacity while maximizing expected repair quality under resource constraints. We prove the NP-hardness of the problem and provide a Lagrangian relaxation. Extensive experiments demonstrate that our approach significantly improves repair accuracy compared to baselines and substantially reduces the number of involved users compared to both other interactive approaches.