PhD Defense: Hassan Abdallah

Semantic Web knowledge graphs have become central to many applications in artificial intelligence, semantic search, and data integration. Their collaborative and participatory nature, illustrated by Wikidata, DBpedia and YAGO, gives them remarkable scale and coverage, while raising essential questions about their structural dynamics and their usefulness for analysis tasks. While many works have focused on ontological modeling and reasoning, little attention has been paid to how facts evolve and self-organize in the factual layer of these graphs. This thesis fills this gap by modeling the dynamic behavior of relationships in graphs, by discovering specific ranking indicators, and by evaluating the robustness of the rankings obtained in the face of perturbations.

Our investigation is guided by four research questions. First, we examine whether distributed editing processes in large collaborative graphs lead to stable global structures (RQ1). Second, we seek to model the process of knowledge accumulation (RQ2). On this basis, we address the automatic discovery of relevant and interpretable ranking indicators, adapted to specific domains and use cases (RQ3). Finally, we evaluate the resilience of these rankings in the face of structural errors and vandalism (RQ4).

To answer these questions, we introduce KRELM (Knowledge Relationship Model), a generative model that considers each relationship in a graph as a bipartite graph governed by an asymmetric attachment process: subjects receive new facts uniformly, while popular objects attract preferentially. It explains the recurring emergence of stable distributions, exponential degrees for subjects, and power law for objects, observed in real graphs. We provide theoretical theorems on these convergence behaviors and empirically validate KRELM on four collaborative graphs and eight historical snapshots of Wikidata. Our results show that the observed structural regularities are not fortuitous, but rooted in reproducible generative mechanisms.

On this basis, we propose RIPM (Ranking Indicator Pattern Miner), an algorithm for the automatic extraction of ranking indicators. RIPM identifies, filters and prioritizes relation-class pairs according to their statistical inequality (measured by the Gini coefficient) and their coverage (proportion of entities concerned). We derive an efficient approximation of the Gini coefficient, allowing RIPM to operate within the constraints of public SPARQL endpoints. An experimental evaluation, including a user study with 19 participants, confirms the usefulness, diversity and interpretability of the discovered indicators.

Finally, we examine the robustness of rankings in the face of structural perturbations via a probabilistic model of ranking stability. We formalize scenarios of global and local perturbations and quantify the probability that an entity ranking changes under these perturbations. By relying on the growth dynamics of KRELM, we establish theoretical thresholds of tolerable perturbations and empirically validate these results on several knowledge graphs.

Overall, this thesis presents a framework linking the dynamic structure of knowledge graphs to their analysis, particularly the extraction of ranking indicators and the study of their robustness. By combining the contributions of complex networks and statistical modeling, it advances the theoretical understanding and practical exploitation of large-scale collaborative knowledge graphs.