Modeling and Understanding Relationship Dynamics in Knowledge Graphs with Applications in Ranking and Stability Analysis
Séminaire organisé par Hassan Abdallah (LIFAT) le 09/03/2026.
Knowledge Graphs (KGs) in the Semantic Web have become central to numerous applications in artificial intelligence, semantic search, and data integration. Their collaborative, crowdsourced nature, represented by platforms like Wikidata, DBpedia, and YAGO, offers immense scale and coverage but also raises important questions about their structural dynamics and analytic utility. While much research has focused on ontological (or schema) modeling, less attention has been devoted to understanding how facts evolve and self-organize in the factual layer of these graphs. This work addresses this gap by modeling the dynamic behavior of relationships in KGs, discovering domain-specific ranking indicators, and assessing the robustness of resulting rankings under perturbations. Our investigation is guided by four research questions. First, we explore whether the distributed editing processes in large crowdsourced KGs result in stable global structures (RQ1). Second, we seek to understand how to model the knowledge accumulation process (RQ2). Building on these insights, we address the problem of automatically discovering meaningful and interpretable ranking indicators tailored to specific domains and use cases (RQ3). Finally, we assess the resilience of such rankings in the face of structural errors and vandalism (RQ4). To tackle these questions, we first introduce KRELM, a generative Knowledge Relationship Model that treats each KG relationship as a bipartite network governed by an asymmetric attachment process: subjects receive new facts uniformly, while popular objects attract new facts preferentially. This model explains the persistent emergence of exponential and power-law degree distributions in real-world KGs. We provide theoretical results for these convergence behaviors and empirically validate KRELM across four crowdsourced KGs and eight historical Wikidata snapshots. Our results demonstrate that the structural regularities observed in KGs are not coincidental but are rooted in reproducible generative mechanisms. Building on this foundation, we propose RIPM (Ranking-Indicator Pattern Miner), a scalable algorithm for the automatic extraction of domain-specific ranking indicators. RIPM identifies, filters, and favors relationship class pairs based on their statistical inequality (measured by the Gini coefficient) and coverage (the proportion of covered entities). We derive an efficient approximation for the Gini coefficient, enabling RIPM to operate within the constraints of public SPARQL endpoints. An experimental evaluation, including a user study with 19 participants, confirms the utility, diversity, and interpretability of the indicators discovered by RIPM. Finally, we examine the robustness of rankings under structural perturbations by proposing a probabilistic model of ranking stability. We formalize and quantify the likelihood that an entity’s rank changes under perturbations. Building upon KRELM’s growth dynamics, we establish theoretical thresholds for tolerable perturbations and empirically validate these results across multiple KGs. Overall, this work presents a framework that links the dynamic structure of KGs with knowledge graph analysis, in particular, ranking indicator mining and robustness analysis. By combining insights from complex networks and statistical modeling, it advances the theoretical understanding and practical exploitation of large-scale knowledge graphs.