SL-8 (C#) : ILP Moderne et Knowledge Graphs

Navigation : Index | << SL-7 | Twin Python >>

Twin C# (dotNetRDF 3.4.1) de SL-8-KnowledgeGraphs-ILP — marathon parite .NET ⇄ Python #4956, Prong B. Compagnon cross-langage du notebook Python (rdflib) sur l’ILP moderne applique aux Knowledge Graphs.

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Construire un Knowledge Graph avec dotNetRDF (triplets RDF, namespaces, Turtle) 2. Extraire les relations d’un KG en dictionnaires de paires (subject, object) 3. Implementer une jointure relationnelle (body a 2 atomes) en C# 4. Miner des règles de Horn (approche simplifiee AMIE3) avec support / confidence 5. Distinguer standard confidence et PCA confidence (Partial Completeness Assumption) 6. Appliquer les règles decouvertes pour completer un KG incomplet 7. Visualiser le KG familial en arbre genealogique ASCII

Verdict SOTA honnete : le coeur (dotNetRDF, rule mining from-scratch, PCA confidence, completion, visualisation) est SOTA-OK (vrai moteur RDF, algorithmes reimplémentes). La section ASP/clingo du notebook Python est INTRINSIC en .NET (clingo est une librairie C/Potassco sans binding .NET natif) ; le twin implemente a la place la saturation au point fixe from-scratch, qui couvre le cas Datalog non-récursive/documente honnetement la limite (recursion + contraintes d’integrite = clingo superieur, RECOVERABLE-MACHINE via appel externe).

Correspondance Python ⇄ C

Concept Python (rdflib)	Equivalent C# (dotNetRDF)
Graph(), g.add((s,p,o))	new Graph(), g.Assert(s, p, o)
Namespace("http://.../")	g.NamespaceMap.AddNamespace("fam", new Uri(...))
URIRef(...)	g.CreateUriNode("fam:Marie")
g.triples((None, p, None))	g.GetTriplesWithPredicate(p)
set de paires (s,o)	HashSet<(string s, string o)>

---

1. Installation et imports dotNetRDF

#r "nuget: dotNetRDF, 3.4.1"
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using VDS.RDF;
using VDS.RDF.Parsing;

// Separateur decimal '.' (invariant) pour parite avec le twin Python et la prose
CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
CultureInfo.DefaultThreadCurrentUICulture = CultureInfo.InvariantCulture;

const string FAM = "http://example.org/family/";
Console.WriteLine("dotNetRDF 3.4.1 charge. Namespace FAM = " + FAM);

Installed Packages

• dotNetRDF, 3.4.1

dotNetRDF 3.4.1 charge. Namespace FAM = http://example.org/family/

---

2. Construction du Knowledge Graph familial

Nous creons un KG de 14 personnes sur 4 generations avec 4 types de relations : parentOf, grandparentOf (INCOMPLET — c’est le coeur du problème ILP), siblingOf, marriedTo. Le notebook Python explique pourquoi grandparentOf est volontairement tronque : simuler un KG reel incomplet que l’ILP doit completer.

var g = new Graph();
g.NamespaceMap.AddNamespace("fam", new Uri(FAM));
g.NamespaceMap.AddNamespace("rdf", new Uri("http://www.w3.org/1999/02/22-rdf-syntax-ns#"));

static IUriNode U(IGraph graph, string qname) => graph.CreateUriNode(qname);

string[] persons = {
    "Marie", "Pierre", "Jean", "Claire",
    "Luc", "Sophie", "Paul", "Anne",
    "Marc", "Lea", "Hugo", "Julie",
    "Thomas", "Emma"
};

foreach (var p in persons)
    g.Assert(U(g, "fam:" + p), U(g, "rdf:type"), U(g, "fam:Person"));

// parentOf(X, Y) : X est parent de Y (14 triples)
(string, string)[] parentTriples = {
    ("Marie", "Jean"), ("Marie", "Claire"),
    ("Pierre", "Jean"), ("Pierre", "Claire"),
    ("Jean", "Luc"), ("Jean", "Sophie"),
    ("Claire", "Paul"), ("Claire", "Anne"),
    ("Luc", "Marc"), ("Luc", "Lea"),
    ("Sophie", "Hugo"), ("Sophie", "Julie"),
    ("Paul", "Thomas"), ("Paul", "Emma"),
};
foreach (var (parent, child) in parentTriples)
    g.Assert(U(g, "fam:" + parent), U(g, "fam:parentOf"), U(g, "fam:" + child));

// grandparentOf : SOUS-ENSEMBLE incomplet (5 triples sur 14 vraies paires)
// Vraies paires = 14 : Marie/Pierre -> {Luc,Sophie,Paul,Anne} (8), Jean -> {Marc,Lea,Hugo,Julie} (4), Claire -> {Thomas,Emma} (2).
// On n'ajoute que 5 triples (Marie/Pierre vers Luc/Sophie/Paul partiellement).
// standard confidence = 5/14 ~ 0.36 ; PCA confidence = 5/8 = 0.625
(string, string)[] grandparentTriples = {
    ("Marie", "Luc"), ("Marie", "Sophie"), ("Marie", "Paul"),
    ("Pierre", "Luc"), ("Pierre", "Sophie"),
};
foreach (var (gp, gc) in grandparentTriples)
    g.Assert(U(g, "fam:" + gp), U(g, "fam:grandparentOf"), U(g, "fam:" + gc));

// siblingOf (12 triples, symetrique)
(string, string)[] siblingTriples = {
    ("Jean", "Claire"), ("Claire", "Jean"),
    ("Luc", "Sophie"), ("Sophie", "Luc"),
    ("Paul", "Anne"), ("Anne", "Paul"),
    ("Marc", "Lea"), ("Lea", "Marc"),
    ("Hugo", "Julie"), ("Julie", "Hugo"),
    ("Thomas", "Emma"), ("Emma", "Thomas"),
};
foreach (var (s1, s2) in siblingTriples)
    g.Assert(U(g, "fam:" + s1), U(g, "fam:siblingOf"), U(g, "fam:" + s2));

// marriedTo (2 triples, symetrique)
(string, string)[] marriedTriples = { ("Marie", "Pierre"), ("Pierre", "Marie") };
foreach (var (h, w) in marriedTriples)
    g.Assert(U(g, "fam:" + h), U(g, "fam:marriedTo"), U(g, "fam:" + w));

int Count(IGraph graph, IUriNode pred) => graph.GetTriplesWithPredicate(pred).Count();

Console.WriteLine("Knowledge Graph cree avec dotNetRDF");
int nPerson = persons.Length;
Console.WriteLine($"  Person : {nPerson}");
Console.WriteLine($"  parentOf : {Count(g, U(g, "fam:parentOf"))} triples");
Console.WriteLine($"  grandparentOf : {Count(g, U(g, "fam:grandparentOf"))} triples");
Console.WriteLine($"  siblingOf : {Count(g, U(g, "fam:siblingOf"))} triples");
Console.WriteLine($"  marriedTo : {Count(g, U(g, "fam:marriedTo"))} triples");
Console.WriteLine($"  Total triplets : {g.Triples.Count()}");

Knowledge Graph cree avec dotNetRDF
  Person : 14
  parentOf : 14 triples
  grandparentOf : 5 triples
  siblingOf : 12 triples
  marriedTo : 2 triples
  Total triplets : 47

Interpretation : Knowledge Graph familial

Le KG contient 47 triplets (14 rdf:type Person + 14 parentOf + 5 grandparentOf + 12 siblingOf + 2 marriedTo). Notons que grandparentOf est incomplet : seules 5 des 14 vraies paires grand-parent/petit-enfant sont explicitement stockees. C’est précisément ce que l’ILP va exploiter.

---

3. Extraction des relations pour le rule mining

Avant de miner des règles, on convertit le graphe RDF en dictionnaires predicate -> {(subject, object)}, le format attendu par le mineur.

static Dictionary<string, HashSet<(string s, string o)>> ExtractRelations(IGraph graph)
{
    var relations = new Dictionary<string, HashSet<(string s, string o)>>();
    foreach (var t in graph.Triples)
    {
        var predUri = ((IUriNode)t.Predicate).Uri.ToString();
        if (!predUri.StartsWith(FAM)) continue;          // ignorer rdf:type et autres namespaces
        var predName = predUri.Substring(FAM.Length);
        var subjName = ((IUriNode)t.Subject).Uri.ToString().Substring(FAM.Length);
        var objName = ((IUriNode)t.Object).Uri.ToString().Substring(FAM.Length);
        if (!relations.ContainsKey(predName))
            relations[predName] = new HashSet<(string s, string o)>();
        relations[predName].Add((subjName, objName));
    }
    return relations;
}

var relations = ExtractRelations(g);

Console.WriteLine("Relations extraites du graphe :");
foreach (var kv in relations.OrderBy(r => r.Key))
{
    Console.WriteLine($"  {kv.Key}: {kv.Value.Count} paires");
    foreach (var (s, o) in kv.Value.OrderBy(p => p.s).ThenBy(p => p.o).Take(5))
        Console.WriteLine($"    {s} -> {o}");
    if (kv.Value.Count > 5)
        Console.WriteLine($"    ... ({kv.Value.Count - 5} autres)");
    Console.WriteLine();
}

var allEntities = new HashSet<string>();
foreach (var pairs in relations.Values)
    foreach (var (s, o) in pairs) { allEntities.Add(s); allEntities.Add(o); }
Console.WriteLine($"Total entites uniques : {allEntities.Count}");
Console.WriteLine($"Total relations : {relations.Count}");

Relations extraites du graphe :
  grandparentOf: 5 paires
    Marie -> Luc
    Marie -> Paul
    Marie -> Sophie
    Pierre -> Luc
    Pierre -> Sophie

  marriedTo: 2 paires
    Marie -> Pierre
    Pierre -> Marie

  parentOf: 14 paires
    Claire -> Anne
    Claire -> Paul
    Jean -> Luc
    Jean -> Sophie
    Luc -> Lea
    ... (9 autres)

  siblingOf: 12 paires
    Anne -> Paul
    Claire -> Jean
    Emma -> Thomas
    Hugo -> Julie
    Jean -> Claire
    ... (7 autres)

Total entites uniques : 14
Total relations : 4

Interpretation : Extraction des relations

L’extraction convertit le graphe RDF en dictionnaires de paires. On retrouve parentOf (14), grandparentOf (5), siblingOf (12), marriedTo (2).

---

4. Rule Mining : jointure relationnelle et evaluation

On implemente deux briques : - ComputeBodyPairs : jointure r1(A,B) JOIN r2(B,C) -> (A,C) (on indexe r2 par sujet). - EvaluateRule : support, standard confidence, PCA confidence.

static HashSet<(string a, string c)> ComputeBodyPairs(
    HashSet<(string a, string b)> r1, HashSet<(string b, string c)> r2)
{
    // Indexer r2 par sujet pour un lookup O(1)
    var r2BySubj = new Dictionary<string, HashSet<string>>();
    foreach (var (b, c) in r2)
    {
        if (!r2BySubj.ContainsKey(b)) r2BySubj[b] = new HashSet<string>();
        r2BySubj[b].Add(c);
    }
    var result = new HashSet<(string, string)>();
    foreach (var (a, b) in r1)
        if (r2BySubj.TryGetValue(b, out var cs))
            foreach (var c in cs) result.Add((a, c));
    return result;
}

static (int support, int bodySize, double confidence, double pcaConfidence, int pcaDenom)
    EvaluateRule(HashSet<(string, string)> bodyPairs,
                 HashSet<(string, string)> headPairs,
                 HashSet<(string, string)> headRelation)
{
    // Support = |body ∩ head|
    var supportPairs = new HashSet<(string, string)>(bodyPairs.Intersect(headPairs));
    int support = supportPairs.Count;
    int bodySize = bodyPairs.Count;
    if (bodySize == 0) return (0, 0, 0.0, 0.0, 0);

    double confidence = (double)support / bodySize;

    // PCA : denominator = paires (A,C) du body ou A a au moins un head triple, OU (A,C) est dans head
    var headBySubj = new Dictionary<string, HashSet<string>>();
    foreach (var (a, c) in headRelation)
    {
        if (!headBySubj.ContainsKey(a)) headBySubj[a] = new HashSet<string>();
        headBySubj[a].Add(c);
    }
    int pcaDenom = 0;
    foreach (var (a, c) in bodyPairs)
        if (headBySubj.ContainsKey(a) || headPairs.Contains((a, c)))
            pcaDenom++;
    double pcaConfidence = pcaDenom > 0 ? (double)support / pcaDenom : 0.0;
    return (support, bodySize, Math.Round(confidence, 4), Math.Round(pcaConfidence, 4), pcaDenom);
}

// Test unitaire de la jointure
var r1 = new HashSet<(string, string)> { ("A", "B"), ("C", "D") };
var r2 = new HashSet<(string, string)> { ("B", "E"), ("D", "F") };
var joined = ComputeBodyPairs(r1, r2);
Console.WriteLine("Test de ComputeBodyPairs :");
Console.WriteLine($"  r1 = {{(A,B), (C,D)}}");
Console.WriteLine($"  r2 = {{(B,E), (D,F)}}");
Console.WriteLine($"  JOIN result = {string.Join(", ", joined.Select(p => $"({p.Item1},{p.Item2})"))}");
Console.WriteLine($"  Attendu : (A,E), (C,F)");

Test de ComputeBodyPairs :
  r1 = {(A,B), (C,D)}
  r2 = {(B,E), (D,F)}
  JOIN result = (A,E), (C,F)
  Attendu : (A,E), (C,F)

Interpretation : Jointure relationnelle

ComputeBodyPairs realise une jointure naturelle : elle apparie l’objet de r1 avec le sujet de r2. Sur le test, r1={(A,B),(C,D)} JOIN r2={(B,E),(D,F)} = {(A,E),(C,F)} : la jointure propage la variable partagee B/D. C’est l’opération fondamentale du rule mining sur KG.

---

5. Enumeration des candidats et minage de règles

On enumere systematiquement : - les règles a 2 atomes en body : r1(A,B) ^ r2(B,C) => head(A,C) - les règles a 1 atome en body : r1(A,B) => head(A,B)

en filtrant par min_support=1 et min_confidence=0.3, et en ignorant les règles triviales (r ^ r => r, r => r).

record Rule(string[] Body, string Head, int Support, int BodySize, double Confidence, double PcaConfidence);

static List<Rule> MineRules(
    Dictionary<string, HashSet<(string, string)>> relations,
    int minSupport = 1, double minConfidence = 0.3)
{
    var predNames = relations.Keys.OrderBy(x => x).ToList();
    var discovered = new List<Rule>();

    // Regles a 2 atomes : r1(A,B) ^ r2(B,C) => head(A,C)
    foreach (var r1 in predNames)
        foreach (var r2 in predNames)
        {
            var bodyPairs = ComputeBodyPairs(relations[r1], relations[r2]);
            if (bodyPairs.Count == 0) continue;
            foreach (var head in predNames)
            {
                if (head == r1 && head == r2) continue;   // skip trivial r1^r1=>r1
                var (sup, bs, conf, pca, _) = EvaluateRule(bodyPairs, relations[head], relations[head]);
                if (sup >= minSupport && conf >= minConfidence)
                    discovered.Add(new Rule(new[] { r1, r2 }, head, sup, bs, conf, pca));
            }
        }

    // Regles a 1 atome : r1(A,B) => head(A,B)
    foreach (var r1 in predNames)
        foreach (var head in predNames)
        {
            if (r1 == head) continue;                     // skip trivial r1=>r1
            var bodyPairs = relations[r1];
            if (bodyPairs.Count == 0) continue;
            var (sup, bs, conf, pca, _) = EvaluateRule(bodyPairs, relations[head], relations[head]);
            if (sup >= minSupport && conf >= minConfidence)
                discovered.Add(new Rule(new[] { r1 }, head, sup, bs, conf, pca));
        }

    // Tri par confidence (desc) puis support (desc)
    return discovered.OrderByDescending(r => r.Confidence).ThenByDescending(r => r.Support).ToList();
}

var rules = MineRules(relations);
Console.WriteLine($"Regles decouvertes : {rules.Count}");
Console.WriteLine();
Console.WriteLine($"{"Regle",-50} | {"Supp",4} | {"Body",4} | {"Conf",6} | {"PCA",6}");
Console.WriteLine(new string('-', 82));
foreach (var rule in rules)
{
    string body = rule.Body.Length == 2
        ? $"{rule.Body[0]}(A,B) ^ {rule.Body[1]}(B,C)"
        : $"{rule.Body[0]}(A,B)";
    string headAtom = rule.Body.Length == 2 ? $"{rule.Head}(A,C)" : $"{rule.Head}(A,B)";
    Console.WriteLine($"{body} => {headAtom,-22} | {rule.Support,4} | {rule.BodySize,4} | {rule.Confidence,6:F2} | {rule.PcaConfidence,6:F2}");
}

Regles decouvertes : 5

Regle                                              | Supp | Body |   Conf |    PCA
----------------------------------------------------------------------------------
parentOf(A,B) ^ siblingOf(B,C) => parentOf(A,C)          |   14 |   14 |   1.00 |   1.00
marriedTo(A,B) ^ parentOf(B,C) => parentOf(A,C)          |    4 |    4 |   1.00 |   1.00
grandparentOf(A,B) ^ siblingOf(B,C) => grandparentOf(A,C)     |    4 |    5 |   0.80 |   0.80
marriedTo(A,B) ^ grandparentOf(B,C) => grandparentOf(A,C)     |    4 |    5 |   0.80 |   0.80
parentOf(A,B) ^ parentOf(B,C) => grandparentOf(A,C)     |    5 |   14 |   0.36 |   0.62

Interpretation : Règles decouvertes

L’algorithme decouvre plusieurs règles. La plus importante est :

parentOf(A,B) ^ parentOf(B,C) => grandparentOf(A,C)

Avec support = 5, body_size = 14, standard confidence = 5/14 ~ 0.36, PCA confidence = 5/8 = 0.625.

La standard confidence est faible (0.36) : c’est l’effet de l’incompletude du KG — le body produit 14 vraies paires grand-parent/petit-enfant, mais seulement 5 sont stockees dans grandparentOf. La PCA confidence (0.625) corrige ce biais en supposant que les sujets ayant au moins un head triple ont leurs head triples complets : seules les paires body ou le sujet (A) a un head triple comptent au denominateur (8 au lieu de 14).

---

6. Des règles d’association aux règles logiques

La distinction : une règle d’association (statistique) exprime une correlation ; une règle logique (Horn) exprime une dépendance causale exploitable pour inferer. parentOf ^ parentOf => grandparentOf est logique (la grand-parente est définie par composition), pas une simple correlation.

// Analyse detaillee de la meilleure regle (grandparent)
var gpRule = rules.First(r => r.Body.Length == 2
    && r.Body[0] == "parentOf" && r.Body[1] == "parentOf" && r.Head == "grandparentOf");

Console.WriteLine("Analyse detaillee de la regle grandparent :");
Console.WriteLine(new string('=', 60));
Console.WriteLine($"  Body : parentOf(A,B) ^ parentOf(B,C)");
Console.WriteLine($"  Head : grandparentOf(A,C)");
Console.WriteLine($"  Support          = {gpRule.Support}   (paires body ET head)");
Console.WriteLine($"  Body size        = {gpRule.BodySize}  (toutes les paires (A,C) du body)");
Console.WriteLine($"  Standard conf    = {gpRule.Confidence:F4}  = {gpRule.Support}/{gpRule.BodySize}");
Console.WriteLine($"  PCA confidence   = {gpRule.PcaConfidence:F4}  (corrige l'incompletude)");
Console.WriteLine();
Console.WriteLine("Pourquoi la PCA est plus elevee : le denominateur PCA ne compte");
Console.WriteLine("que les paires body ou le sujet A a au moins un head triple (8),");
Console.WriteLine("pas toutes les paires body (14). Les 6 paires de Jean/Claire");
Console.WriteLine("(qui n'ont aucun head triple) sont exclues : on ne sait pas si");
Console.WriteLine("leur absence de grandparentOf est un vrai negatif ou un trou.");

Analyse detaillee de la regle grandparent :
============================================================
  Body : parentOf(A,B) ^ parentOf(B,C)
  Head : grandparentOf(A,C)
  Support          = 5   (paires body ET head)
  Body size        = 14  (toutes les paires (A,C) du body)
  Standard conf    = 0.3571  = 5/14
  PCA confidence   = 0.6250  (corrige l'incompletude)

Pourquoi la PCA est plus elevee : le denominateur PCA ne compte
que les paires body ou le sujet A a au moins un head triple (8),
pas toutes les paires body (14). Les 6 paires de Jean/Claire
(qui n'ont aucun head triple) sont exclues : on ne sait pas si
leur absence de grandparentOf est un vrai negatif ou un trou.

---

7. Application pratique : completer le Knowledge Graph

On utilise les règles decouvertes (qualifiees par leur PCA confidence) pour inferer de nouveaux triplets grandparentOf manquants. C’est tout l’intérêt de l’ILP : transformer un KG incomplet en KG complete.

static int ApplyRules(
    IGraph graph,
    Dictionary<string, HashSet<(string, string)>> relations,
    List<Rule> rules,
    double minPca = 0.5)
{
    int added = 0;
    foreach (var rule in rules.Where(r => r.PcaConfidence >= minPca && r.Body.Length == 2))
    {
        var bodyPairs = ComputeBodyPairs(relations[rule.Body[0]], relations[rule.Body[1]]);
        foreach (var (a, c) in bodyPairs)
        {
            var subj = U(graph, "fam:" + a);
            var obj = U(graph, "fam:" + c);
            var pred = U(graph, "fam:" + rule.Head);
            var triple = new Triple(subj, pred, obj);
            // N'ajouter que les triples absents (idempotent)
            if (!graph.ContainsTriple(triple))
            {
                graph.Assert(triple);
                added++;
            }
        }
    }
    return added;
}

int before = Count(g, U(g, "fam:grandparentOf"));
int newTriples = ApplyRules(g, relations, rules, minPca: 0.5);
int after = Count(g, U(g, "fam:grandparentOf"));

Console.WriteLine($"Completion du KG par les regles (PCA >= 0.5) :");
Console.WriteLine($"  grandparentOf AVANT : {before} triples");
Console.WriteLine($"  Nouveaux triplets   : +{newTriples}");
Console.WriteLine($"  grandparentOf APRES : {after} triples");
Console.WriteLine();
Console.WriteLine("Le KG est desormais complete : les 14 vraies paires");
Console.WriteLine("grand-parent/petit-enfant sont inferrees par la regle.");

Completion du KG par les regles (PCA >= 0.5) :
  grandparentOf AVANT : 5 triples
  Nouveaux triplets   : +9
  grandparentOf APRES : 14 triples

Le KG est desormais complete : les 14 vraies paires
grand-parent/petit-enfant sont inferrees par la regle.

---

8. Visualisation du Knowledge Graph familial

Arbre genealogique (relations parentOf) sur 4 generations.

static void PrintFamilyTree(Dictionary<string, HashSet<(string s, string o)>> rels, string root, string indent = "", HashSet<string>? visited = null)
{
    visited ??= new HashSet<string>();
    if (visited.Contains(root)) return;
    visited.Add(root);
    Console.WriteLine(indent + root);
    if (rels.TryGetValue("parentOf", out var parents))
    {
        var children = parents.Where(p => p.s == root).Select(p => p.o).OrderBy(x => x).ToList();
        foreach (var child in children)
            PrintFamilyTree(rels, child, indent + "  ", visited);
    }
}

Console.WriteLine("Arbre genealogique (relations parentOf) :");
Console.WriteLine(new string('=', 50));
// Racines : personnes qui sont parents mais ne sont enfant de personne
var allChildren = relations["parentOf"].Select(p => p.o).ToHashSet();
var roots = allEntities.Where(e => relations["parentOf"].Any(p => p.s == e) && !allChildren.Contains(e)).OrderBy(x => x);
foreach (var root in roots)
    PrintFamilyTree(relations, root);

Arbre genealogique (relations parentOf) :
==================================================
Marie
  Claire
    Anne
    Paul
      Emma
      Thomas
  Jean
    Luc
      Lea
      Marc
    Sophie
      Hugo
      Julie
Pierre
  Claire
    Anne
    Paul
      Emma
      Thomas
  Jean
    Luc
      Lea
      Marc
    Sophie
      Hugo
      Julie

---

9. Comparaison ILP classique vs Rule Mining sur KG

Dimension	ILP classique (FOIL, SL-4/SL-6)	Rule Mining (AMIE3, ce notebook)
Entrees	Exemples positifs/negatifs etiquetes	KG (faits positifs seulement)
Negatifs	Fournis explicitement	Absents (PCA pour estimer)
Type de règles	Horn générales	Règles fermees (closed rules)
Couverture	Backtracking, couverture exacte	Jointure relationnelle
Sortie	Programme logique récursif	Liste de reglesplatees

// Tableau comparatif synthetique
Console.WriteLine("ILP Classique (SL-4/SL-6 FOIL) vs Rule Mining sur KG (SL-8 AMIE3)");
Console.WriteLine(new string('=', 65));
Console.WriteLine($"{"Dimension",-25} | {"ILP classique (FOIL)",-20} | {"Rule Mining (AMIE3)",-20}");
Console.WriteLine(new string('-', 65));
var rows = new (string, string, string)[] {
    ("Entrees", "Ex. positifs + negatifs", "KG (faits positifs)"),
    ("Negatifs", "Etiquetes explicitement", "Absents (PCA)"),
    ("Recursion", "Oui (ancestorOf...)", "Non (regles fermees)"),
    ("Optimisation", "FOIL_Gain (entropie)", "Support/Confidence"),
    ("Sortie", "Programme logique", "Liste de regles"),
};
foreach (var (dim, ilp, amie) in rows)
    Console.WriteLine($"{dim,-25} | {ilp,-20} | {amie,-20}");

ILP Classique (SL-4/SL-6 FOIL) vs Rule Mining sur KG (SL-8 AMIE3)
=================================================================
Dimension                 | ILP classique (FOIL) | Rule Mining (AMIE3) 
-----------------------------------------------------------------
Entrees                   | Ex. positifs + negatifs | KG (faits positifs) 
Negatifs                  | Etiquetes explicitement | Absents (PCA)       
Recursion                 | Oui (ancestorOf...)  | Non (regles fermees)
Optimisation              | FOIL_Gain (entropie) | Support/Confidence  
Sortie                    | Programme logique    | Liste de regles     

---

10. Au-dela : Answer Set Programming (clingo) — limite honnete du twin C

Le notebook Python poursuit avec clingo (ASP solver de Potassco) pour : - la saturation au point fixe (vs notre ApplyRules en passe unique), - la recursion (ancestorOf récursif, inexprimable par nos règles fermees a 2 atomes), - les contraintes d’integrite (repair minimal d’un KG cyclique).

Verdict SOTA : clingo est une librairie C/C++ sans binding .NET natif. Une traduction litterale est INTRINSIC en .NET (pas d’equivalent SOTA installable sans appel externe a un binaire). Le twin C# implemente a la place la saturation au point fixe from-scratch ci-dessous (equivalent au cas non-récursive documente dans le notebook Python), qui couvre le cas pedagogique. La recursion + contraintes d’integrite restent l’apanage de clingo (RECOVERABLE-MACHINE via appel processus externe au binaire clingo, hors scope de ce twin).

// Saturation au point fixe : on re-applique ApplyRules jusqu'a ce qu'aucun
// nouveau triplet ne soit ajoute (equivalent clingo sans recursion).
// Sur le KG familial (regles non-recursives), 1 iteration suffit.
static int Saturate(IGraph graph, Dictionary<string, HashSet<(string,string)>> rels, List<Rule> rules, double minPca = 0.5)
{
    int total = 0, iter = 0;
    while (true)
    {
        iter++;
        // Re-extraire les relations apres chaque passe (le KG a grandi)
        var freshRels = ExtractRelations(graph);
        int added = ApplyRules(graph, freshRels, rules, minPca);
        total += added;
        Console.WriteLine($"  Iteration {iter} : +{added} triplets");
        if (added == 0) break;
        if (iter > 20) { Console.WriteLine("  (garde-fou : 20 iterations)"); break; }
    }
    return total;
}

Console.WriteLine("Saturation au point fixe (equivalent Datalog non-recursif) :");
int sat = Saturate(g, relations, rules, 0.5);
Console.WriteLine($"Total triplets inferes par saturation : {sat}");
Console.WriteLine();
Console.WriteLine("Sur ce KG, les regles sont non-recursives : 1 seule iteration");
Console.WriteLine("suffit. clingo ferait la meme chose (point fixe) MAIS saurait");
Console.WriteLine("aussi resoudre ancestorOf recursif et le repair minimal —");
Console.WriteLine("cas honnetement hors scope du twin C# (INTRINSIC sans clingo natif).");

Saturation au point fixe (equivalent Datalog non-recursif) :
  Iteration 1 : +0 triplets
Total triplets inferes par saturation : 0

Sur ce KG, les regles sont non-recursives : 1 seule iteration
suffit. clingo ferait la meme chose (point fixe) MAIS saurait
aussi resoudre ancestorOf recursif et le repair minimal —
cas honnetement hors scope du twin C# (INTRINSIC sans clingo natif).

---

Exercices

Convention (cf notebook-conventions.md C.1) : les stubs d’exercice utilisent pass-equivalents C# (// TODO etudiant, commentaire sans erreur). Le notebook s’execute de bout en bout même exercices non completes.

Exemple guide 1 : Ajouter uncleOf et rediscover sa règle

Solution demontree ci-dessous (See #2161). uncleOf(X,Y) :- parentOf(Z,Y), siblingOf(Z,X) (le frere d’un parent est l’oncle).

// Exemple guide 1 : uncleOf(X,Y) :- parentOf(Z,Y) ^ siblingOf(Z,X)
// Variante : on ajoute manuellement quelques uncleOf, puis on verifie
// si le mineur retrouve la regle parentOf(B,Y) ^ siblingOf(A,B) => uncleOf(A,Y).
// (La regle demande un schema de jointure legerement different ; on
// l'illustre ici en construisant les paires uncleOf attendues a la main.)

var uncleExpected = new HashSet<(string, string)>();
foreach (var (z, y) in relations["parentOf"])
    foreach (var (a, b) in relations["siblingOf"])
        if (b == z) uncleExpected.Add((a, y));

Console.WriteLine($"Paires uncleOf attendues (parentOf(Z,Y) ^ siblingOf(Z,X)) : {uncleExpected.Count}");
foreach (var (u, n) in uncleExpected.OrderBy(p => p.Item1).ThenBy(p => p.Item2).Take(8))
    Console.WriteLine($"  {u} est l'oncle/la tante de {n}");

Paires uncleOf attendues (parentOf(Z,Y) ^ siblingOf(Z,X)) : 10
  Anne est l'oncle/la tante de Emma
  Anne est l'oncle/la tante de Thomas
  Claire est l'oncle/la tante de Luc
  Claire est l'oncle/la tante de Sophie
  Jean est l'oncle/la tante de Anne
  Jean est l'oncle/la tante de Paul
  Luc est l'oncle/la tante de Hugo
  Luc est l'oncle/la tante de Julie

Exercice 1 (variation) : Ajouter cousinOf au KG

Construisez un petit ensemble de triples cousinOf et constatez que le mineur a 2 atomes peut retrouver cousinOf(X,Y) :- parentOf(Z,X) ^ siblingOf(Z,W) ^ parentOf(W,Y) … sauf que cette règle a 3 atomes : notre mineur (limite a 2) ne la trouve pas. Reflechissez a comment l’etendre.

// Exercice 1 : cousinOf a 3 atomes — le mineur a 2 atomes ne le trouve pas.
// TODO etudiant : ajoutez quelques triples cousinOf, puis minez et constatez
// l'absence de la regle cousinOf(X,Y) :- parentOf(Z,X) ^ siblingOf(Z,W) ^ parentOf(W,Y).
// Indice : la regle demande d'etendre MineRules aux bodies a 3 atomes
// (enumeration r1^r2^r3 => head, cout |preds|^3).
var placeholder = 0;  // TODO etudiant
Console.WriteLine("Exercice a completer : etendre MineRules aux regles a 3 atomes.");

Exercice a completer : etendre MineRules aux regles a 3 atomes.

Exemple guide 2 : Reimplementer la PCA confidence

Solution demontree (See #2161). On re-calcule la PCA de la règle grandparent et on verifie qu’elle vaut 0.625.

// Exemple guide 2 : verification manuelle de la PCA pour grandparent
var bodyGp = ComputeBodyPairs(relations["parentOf"], relations["parentOf"]);
var headGp = relations["grandparentOf"];
var (sup, bs, conf, pca, denom) = EvaluateRule(bodyGp, headGp, headGp);
Console.WriteLine($"Re-verification PCA (grandparent) :");
Console.WriteLine($"  body_pairs      = {bs}   (parentOf JOIN parentOf)");
Console.WriteLine($"  support         = {sup}   (body ∩ head)");
Console.WriteLine($"  pca_denominator = {denom} (paires body ou A a un head triple)");
Console.WriteLine($"  PCA confidence  = {sup}/{denom} = {pca:F4}");
Console.WriteLine($"  Attendu         : 5/8 = 0.625  -> {(pca == 0.625 ? "OK" : "ECHEC")}");

Re-verification PCA (grandparent) :
  body_pairs      = 14   (parentOf JOIN parentOf)
  support         = 5   (body ∩ head)
  pca_denominator = 8 (paires body ou A a un head triple)
  PCA confidence  = 5/8 = 0.6250
  Attendu         : 5/8 = 0.625  -> OK

Exercice 2 (variation) : Un mini-KG ou la PCA est trompeuse

Construisez un mini-KG ou la PCA surestime une règle fausse (la PCA suppose que les sujets a head triple sont complets, ce qui peut etre faux).

// Exercice 2 : mini-KG piegeux pour la PCA.
// TODO etudiant : construisez un KG ou un sujet a un seul head triple (donc
// compte au denominateur PCA) mais ou ce head triple est lui-meme incomplet.
// Indice : la PCA echoue quand la "completude partielle" supposee est fausse.
var ex2 = 0;  // TODO etudiant
Console.WriteLine("Exercice a completer : construire un KG piegeux pour la PCA.");

Exercice a completer : construire un KG piegeux pour la PCA.

Exercice 3 : Règles fermees vs ouvertes

AMIE n’enumere que des règles fermees (toutes les variables du body sont dans le head). Quantifiez le gain d’expressivite des règles ouvertes.

// Exercice 3 : regles fermees vs ouvertes.
// TODO etudiant : enumerer combien de regles ouvertes (avec une variable
// existentielle dans le body absente du head) deviendraient minables si
// on levait la contrainte "fermee".
var ex3 = 0;  // TODO etudiant
Console.WriteLine("Exercice a completer : regles ouvertes (variable existentielle).");

Exercice a completer : regles ouvertes (variable existentielle).

---

11. Resume

Concept	Description
Knowledge Graph	Graphe RDF de triplets (sujet, predicat, objet)
Extraction	Conversion du KG en predicate -> {(s,o)} pour le minage
Jointure relationnelle	r1(A,B) JOIN r2(B,C) -> (A,C)
Support	Nombre de paires body ET head
Standard confidence	support / body_size (penalisee par l’incompletude)
PCA confidence	support / (paires body ou le sujet a un head triple)
Completion	Appliquer les règles pour inferer de nouveaux triplets
Saturation	Re-appliquer jusqu’au point fixe (equivalent Datalog non-récursif)

Perspectives

Ce notebook a explore l’intersection ILP x Knowledge Graphs. Le twin C# couvre le coeur (dotNetRDF, rule mining from-scratch, PCA, completion, saturation). La recursion et les contraintes d’integrite (clingo) restent l’apanage d’un solveur ASP dedie — honnetement documentees comme INTRINSIC en .NET natif.

Ressources

• Galarraga et al., “AMIE: Association Rule Mining under Incomplete Evidence in Ontological Knowledge Bases” (ISWC 2013) — la PCA confidence.
• SL-8-KnowledgeGraphs-ILP — twin Python original (rdflib + clingo).
• Marathon parite .NET ⇄ Python #4956.

Co-Authored-By: Claude noreply@anthropic.com