Mettez les graphes au service de la data

Vous avez maintenant une boîte à outils complète : parcours, composantes, tri topologique, arbres, chemins, flots. Mais à quoi tout cela sert-il quand on travaille en data science ? À beaucoup plus de choses qu’on ne le croit. Les graphes organisent les pipelines de données, ont fait la fortune d’un moteur de recherche, alimentent les systèmes de recommandation et structurent la connaissance que consultent aujourd’hui les modèles de langage.

Ce chapitre fait le tour de ces usages, en reliant chacun aux notions des chapitres précédents. Notre fil rouge : une librairie en ligne rennaise, avec son site web, ses clients, ses livres et ses données.

Les DAG, colonne vertébrale des pipelines

Orchestrer des traitements

Chaque nuit, la librairie recalcule ses stocks, ses ventes de la veille et ses recommandations. Ces traitements dépendent les uns des autres : c’est exactement le pipeline du chapitre 4. Les orchestrateurs de workflows (Airflow, Dagster, Prefect) demandent de décrire un traitement comme un DAG (graphe orienté sans circuit) de tâches, puis ils :

• vérifient l’absence de circuit à la déclaration (un DAG avec une dépendance circulaire est refusé) ;
• lancent les tâches dans un ordre topologique, en exécutant en parallèle celles d’un même niveau ;
• en cas d’échec, relancent uniquement la tâche fautive et ses descendants (au sens du chapitre 3), sans tout recalculer.

Les outils de transformation SQL comme dbt font de même avec les tables : chaque modèle déclare les tables qu’il lit, dbt en déduit le graphe des dépendances et reconstruit les tables dans l’ordre. Ce même graphe sert à la traçabilité des données (data lineage) : si une colonne source est corrompue, les descendants de cette table dans le graphe sont exactement les tableaux de bord à invalider.

Si nett_clients échoue, l'orchestrateur ne relance qu'elle et ses descendants ; les autres résultats restent valables.

Le graphe de calcul des réseaux de neurones

Les bibliothèques d’apprentissage profond utilisent elles aussi un DAG. Quand vous écrivez perte = ((w * x + b - y) ** 2).mean() en PyTorch, la bibliothèque enregistre un graphe de calcul : chaque opération est un sommet, relié aux opérations qui produisent ses entrées. La rétropropagation du gradient parcourt ensuite ce graphe dans l’ordre topologique inverse, de la perte vers les paramètres. C’est le tri topologique du chapitre 4, au cœur de l’entraînement de tous les réseaux de neurones (voir le cours d’apprentissage automatique).

À retenir

Dès que des calculs dépendent les uns des autres, il y a un DAG caché : pipelines de données, tables dbt, graphes de calcul pour la différentiation automatique, tableurs. Le tri topologique donne l’ordre d’exécution, les niveaux donnent le parallélisme, et les descendants donnent ce qu’il faut recalculer.

PageRank : classer par les liens

L’idée : un internaute au hasard

Comment classer des pages web par importance ? L’idée de PageRank, à l’origine de Google, est qu’une page est importante si des pages importantes pointent vers elle. La définition semble circulaire, mais elle se formalise très bien avec une marche aléatoire.

Imaginez un internaute qui navigue au hasard. À chaque étape :

• avec probabilité $d$ (typiquement $d = 0{,}85$), il clique sur un des liens de la page, choisi uniformément ;
• avec probabilité $1 - d$, il se téléporte sur une page quelconque du site, choisie uniformément.

Le PageRank d’une page est la proportion du temps que cet internaute passe sur elle, à long terme :

$$PR(p) = \frac{1 - d}{n} + d \sum_{q \to p} \frac{PR(q)}{d^+(q)}$$

• $n$ est le nombre de pages ;
• la somme porte sur les pages $q$ qui ont un lien vers $p$ ;
• $d^+(q)$ est le nombre de liens sortants de $q$ (son demi-degré extérieur) : une page partage son importance entre toutes celles qu’elle cite.

Mathématiquement, c’est la distribution stationnaire d’une chaîne de Markov (voir le cours de modèles stochastiques). La téléportation joue un rôle crucial : elle rend la chaîne irréductible, même si le graphe du web n’est pas fortement connexe (chapitre 3), ce qui garantit que la distribution stationnaire existe et est unique.

Le calcul par itérations

On part d’un PageRank uniforme ($1/n$ partout) et on applique la formule en boucle jusqu’à stabilisation : c’est la méthode de la puissance (power iteration).

Partie de 0,25 partout, la méthode de la puissance oscille quelques itérations puis se stabilise ; D, que personne ne cite, tombe tout de suite à la téléportation seule.

Exemple

Le site de la librairie a quatre pages : A (accueil), B (blog), C (catalogue) et D (une page promotionnelle). Liens : A → B, A → C, B → C, C → A, D → C. Avec $d = 0{,}85$, le terme de téléportation vaut $0{,}15 / 4 = 0{,}0375$.

Première itération, en partant de $0{,}25$ partout :

• $PR(A) = 0{,}0375 + 0{,}85 \times 0{,}25 = 0{,}25$ (seul C pointe vers A, et C n’a qu’un lien) ;
• $PR(B) = 0{,}0375 + 0{,}85 \times 0{,}25 / 2 \approx 0{,}144$ (A partage entre B et C) ;
• $PR(C) = 0{,}0375 + 0{,}85 \times (0{,}125 + 0{,}25 + 0{,}25) \approx 0{,}569$ ;
• $PR(D) = 0{,}0375$ (personne ne pointe vers D).

Après convergence : $PR(C) \approx 0{,}394$, $PR(A) \approx 0{,}373$, $PR(B) \approx 0{,}196$ et $PR(D) \approx 0{,}038$. Le catalogue, cité par trois pages, arrive en tête ; l’accueil le suit de près, car il est cité par le catalogue, une page importante. La page promotionnelle, que rien ne cite, n’a que la téléportation.

Le catalogue et l'accueil se renvoient leur importance ; la page promo, que rien ne cite, garde seulement sa part de téléportation.

def pagerank(liens, d=0.85, iterations=100):
    """liens : page -> liste des pages citées. Méthode de la puissance."""
    pages = list(liens)
    n = len(pages)
    pr = {p: 1 / n for p in pages}
    for _ in range(iterations):
        pr = {p: (1 - d) / n + d * sum(pr[q] / len(liens[q]) for q in pages if p in liens[q])
              for p in pages}
    return pr

site = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "D": ["C"]}
print({p: round(v, 3) for p, v in pagerank(site).items()})
# {'A': 0.373, 'B': 0.196, 'C': 0.394, 'D': 0.038}

Attention

Une page sans lien sortant (un « cul-de-sac », dangling node) pose un problème : la somme des PageRank n’est plus conservée, car l’importance qui y arrive disparaît. Le code ci-dessus ne gère pas ce cas (il diviserait par zéro). La convention habituelle, adoptée par networkx, est de considérer qu’une telle page pointe vers toutes les pages.

Au-delà du web, PageRank et ses variantes mesurent l’influence dans un réseau social, repèrent les articles scientifiques les plus structurants dans un graphe de citations, ou détectent les comptes centraux d’un réseau de fraude. C’est l’une des mesures de centralité ; d’autres existent, comme la centralité d’intermédiarité (betweenness), qui compte combien de plus courts chemins passent par un sommet (un point de passage obligé, proche de la notion de point d’articulation du chapitre 2).

La recommandation sur un graphe biparti

Clients et livres

La librairie veut suggérer des livres à ses clients. Représentons ses ventes par un graphe biparti : d’un côté les clients, de l’autre les livres, et une arête quand un client a acheté un livre. Aucune arête ne relie deux clients ni deux livres.

Client	Livres achetés
U1	L1, L2
U2	L1, L2, L3
U3	L2, L4
U4	L3

Compter les chemins de longueur 3

Une idée simple et étonnamment efficace : recommander à un client les livres qu’on atteint depuis lui par un chemin de longueur 3, client → livre → autre client → autre livre. Autrement dit : « les clients qui ont acheté les mêmes livres que vous ont aussi acheté… ». Plus il y a de tels chemins vers un livre, plus il est recommandé.

Exemple

Pour U1 (qui a acheté L1 et L2), on cherche les chemins vers un livre qu’il n’a pas :

• U1 → L1 → U2 → L3 ;
• U1 → L2 → U2 → L3 ;
• U1 → L2 → U3 → L4.

L3 obtient un score de 2 et L4 un score de 1 : on recommande d’abord L3. U2 ressemble beaucoup à U1 (deux livres en commun), et son avis pèse donc double.

Les trois chemins U1 → livre → client → livre : deux mènent à L3 (via U2), un à L4 (via U3).

Algébriquement, si $B$ est la matrice d’adjacence clients-livres, le nombre de chemins de longueur 3 est donné par le produit $B B^\top B$ : c’est le principe du filtrage collaboratif fondé sur les voisins. Les systèmes industriels raffinent l’idée avec des marches aléatoires (quelques pas au hasard depuis le client, en comptant les livres les plus visités, à la manière d’un PageRank personnalisé), ou en apprenant des représentations vectorielles des sommets (embeddings).

Piège

Un livre très populaire (acheté par tout le monde) est atteint par une foule de chemins depuis n’importe quel client : le score brut le recommande à tous, ce qui n’apporte rien. On normalise donc les scores, par exemple en divisant par le degré des livres ou des clients intermédiaires, exactement comme PageRank divise par $d^+(q)$.

Les graphes de connaissances

Des faits sous forme de triplets

Un graphe de connaissances (knowledge graph) stocke des faits sous la forme de triplets (sujet, prédicat, objet), c’est-à-dire d’arcs étiquetés entre entités :

• (« Les Misérables », écrit_par, Victor Hugo) ;
• (Victor Hugo, né_à, Besançon) ;
• (« Les Misérables », genre, roman historique) ;
• (Besançon, situé_en, France).

Les quatre triplets forment un petit graphe orienté dont chaque arc porte un prédicat.

C’est un multigraphe orienté dont les arcs portent un type. Wikidata en contient plus d’un milliard, et les moteurs de recherche s’en servent pour afficher les encadrés d’information. La norme RDF décrit ces triplets, et le langage SPARQL permet de les interroger ; les bases orientées graphes comme Neo4j utilisent un autre langage, Cypher.

Interroger, c’est parcourir

Répondre à « quels romans ont été écrits par des auteurs nés en France ? » revient à chercher des chemins d’une forme donnée : livre → écrit_par → auteur → né_à → ville → situé_en → France. Les requêtes récursives (« toutes les sous-catégories de roman, à n’importe quelle profondeur ») sont des calculs de descendants, donc de fermeture transitive (chapitre 3). C’est aussi exactement ce que fait un programme Prolog quand il déduit des faits nouveaux à partir de règles (voir le cours de programmation logique).

Les graphes de connaissances connaissent un regain d’intérêt avec les modèles de langage : dans les approches de type GraphRAG, on extrait des entités et des relations d’un corpus de documents, on les organise en graphe, puis on fournit au modèle les sous-graphes pertinents pour répondre à une question. Le graphe apporte des faits vérifiables et des liens explicites, là où la recherche par similarité de textes les perd.

Un aperçu des méthodes modernes

Pour finir, voici quelques outils que vous croiserez en data et qui prolongent ce cours.

Question	Méthode	Lien avec le cours
Quels groupes de sommets sont très liés entre eux ?	détection de communautés (algorithme de Louvain, maximisation de la modularité)	généralise les composantes connexes
Quels sommets sont centraux ?	PageRank, centralité de degré, d’intermédiarité	degrés, plus courts chemins
Comment représenter un sommet par un vecteur ?	plongements (node2vec, marches aléatoires)	parcours, marches aléatoires
Comment apprendre sur des données en graphe ?	réseaux de neurones sur graphes (GNN) : chaque sommet agrège l’information de ses voisins	listes d’adjacence, voisinages
Comment regrouper des points proches ?	clustering hiérarchique à lien simple	arbre couvrant minimal (chapitre 5)

networkx suffit pour explorer des graphes de quelques centaines de milliers de sommets. Au-delà, on passe à des outils spécialisés (igraph, graph-tool, les bases orientées graphes, ou les bibliothèques de GNN comme PyTorch Geometric).

import networkx as nx

web = nx.DiGraph([("A", "B"), ("A", "C"), ("B", "C"), ("C", "A"), ("D", "C")])
print(nx.pagerank(web, alpha=0.85))                  # alpha joue le rôle de d

ventes = nx.Graph([("U1", "L1"), ("U1", "L2"), ("U2", "L1"), ("U2", "L2"),
                   ("U2", "L3"), ("U3", "L2"), ("U3", "L4"), ("U4", "L3")])
print(nx.is_bipartite(ventes))                       # True
perso = nx.pagerank(ventes, personalization={"U1": 1})   # PageRank personnalisé depuis U1
print(sorted((l for l in perso if l.startswith("L")), key=perso.get, reverse=True))

communautes = nx.community.louvain_communities(ventes, seed=0)   # détection de communautés

En entretien

« PageRank modélise un internaute qui suit des liens au hasard et se téléporte de temps en temps : le score d’une page est la probabilité stationnaire d’y être, calculée par itérations de puissance. La téléportation garantit la convergence même si le graphe n’est pas fortement connexe. La même idée, personnalisée depuis un utilisateur, sert à faire de la recommandation. »

En résumé

• Les DAG organisent les pipelines de données (Airflow, dbt) et les graphes de calcul des réseaux de neurones : ordre topologique pour l’exécution, niveaux pour le parallélisme, descendants pour la traçabilité.
• PageRank classe les pages par une marche aléatoire avec téléportation : $PR(p) = (1 - d)/n + d \sum_{q \to p} PR(q)/d^+(q)$, calculé par la méthode de la puissance.
• La recommandation s’appuie sur un graphe biparti utilisateurs-produits : compter les chemins de longueur 3 ou faire des marches aléatoires personnalisées, en normalisant par les degrés.
• Un graphe de connaissances stocke des triplets (sujet, prédicat, objet) ; l’interroger revient à chercher des chemins, et il sert aujourd’hui à ancrer les réponses des modèles de langage.
• Communautés, centralités, plongements et GNN prolongent les notions de ce cours à l’échelle des grands réseaux.

Exercices

Exercice · Une itération de PageRank

facile

Un site a trois pages avec les liens A → B, B → C, C → A et C → B. Avec $d = 0{,}85$ et un PageRank initial de $1/3$ partout, calculez une itération. Quelle page semble la plus importante ?

Voir la solution

Le terme de téléportation vaut $0{,}15 / 3 = 0{,}05$. C a deux liens sortants, A et B en ont un chacun.

• $PR(A) = 0{,}05 + 0{,}85 \times \tfrac{1/3}{2} \approx 0{,}05 + 0{,}142 = 0{,}192$ (seul C pointe vers A) ;
• $PR(B) = 0{,}05 + 0{,}85 \times \big(\tfrac{1}{3} + \tfrac{1/3}{2}\big) = 0{,}05 + 0{,}425 = 0{,}475$ (A et C pointent vers B) ;
• $PR(C) = 0{,}05 + 0{,}85 \times \tfrac{1}{3} \approx 0{,}333$ (seul B pointe vers C).

La somme vaut bien 1. Après une itération, B est en tête : c’est la seule page citée deux fois. (À convergence, on obtient environ 0,397 pour B, 0,388 pour C et 0,215 pour A : C remonte, car il reçoit tout le PageRank de B.)

En code

Python

liens = {"A": ["B"], "B": ["C"], "C": ["A", "B"]}
d, n = 0.85, len(liens)

def iteration(pr):
    return {p: (1 - d) / n + d * sum(pr[q] / len(liens[q]) for q in liens if p in liens[q])
            for p in liens}

pr = iteration({p: 1 / n for p in liens})
print({p: round(v, 3) for p, v in pr.items()}, round(sum(pr.values()), 3))
# {'A': 0.192, 'B': 0.475, 'C': 0.333} 1.0
for _ in range(100):                          # méthode de la puissance jusqu'à convergence
    pr = iteration(pr)
print({p: round(v, 3) for p, v in pr.items()})
# {'A': 0.215, 'B': 0.397, 'C': 0.388}

R

pages <- c("A", "B", "C")
L <- matrix(0, 3, 3, dimnames = list(pages, pages))   # L[q, p] = 1 si q cite p
L["A", "B"] <- 1; L["B", "C"] <- 1; L["C", "A"] <- 1; L["C", "B"] <- 1
P <- L / rowSums(L)                        # chaque page partage son importance entre ses liens
d <- 0.85; n <- 3

iteration <- function(pr) (1 - d) / n + d * as.vector(t(P) %*% pr)
pr <- iteration(rep(1 / n, n))
round(pr, 3); sum(pr)                      # 0.192 0.475 0.333 ; somme 1
for (k in 1:100) pr <- iteration(pr)       # méthode de la puissance jusqu'à convergence
round(pr, 3)                               # 0.215 0.397 0.388

Exercice · Recommander à un autre client

moyen

Avec le tableau des ventes de la librairie, calculez les scores de recommandation par chemins de longueur 3 pour le client U3. Que recommandez-vous ?

Voir la solution

U3 a acheté L2 et L4. Les clients qui partagent un livre avec lui : via L2, U1 et U2 ; via L4, personne d’autre. Chemins vers des livres que U3 n’a pas :

• U3 → L2 → U1 → L1 ;
• U3 → L2 → U2 → L1 ;
• U3 → L2 → U2 → L3.

Scores : L1 = 2, L3 = 1. On recommande L1 en priorité. Remarquez que tout passe par L2, le livre le plus acheté (trois clients) : c’est typiquement le cas où une normalisation par le degré de L2 serait utile pour ne pas surpondérer les livres populaires.

En code

Python

import numpy as np

clients, livres = ["U1", "U2", "U3", "U4"], ["L1", "L2", "L3", "L4"]
B = np.array([[1, 1, 0, 0],                # U1 : L1, L2
              [1, 1, 1, 0],                # U2 : L1, L2, L3
              [0, 1, 0, 1],                # U3 : L2, L4
              [0, 0, 1, 0]])               # U4 : L3

chemins = B @ B.T @ B                      # nombre de chemins client -> livre de longueur 3
u3 = clients.index("U3")
scores = {l: int(chemins[u3, j]) for j, l in enumerate(livres) if B[u3, j] == 0}
print(scores)   # {'L1': 2, 'L3': 1} : on recommande L1

R

B <- matrix(c(1, 1, 0, 0,                  # U1 : L1, L2
              1, 1, 1, 0,                  # U2 : L1, L2, L3
              0, 1, 0, 1,                  # U3 : L2, L4
              0, 0, 1, 0),                 # U4 : L3
            nrow = 4, byrow = TRUE,
            dimnames = list(paste0("U", 1:4), paste0("L", 1:4)))

chemins <- B %*% t(B) %*% B                # nombre de chemins client -> livre de longueur 3
chemins["U3", B["U3", ] == 0]              # L1 2, L3 1 : on recommande L1

Exercice · Choisir le bon outil

difficile

Pour chaque besoin de la librairie, indiquez la modélisation par un graphe et l’algorithme du cours à utiliser.

1. Le traitement de nuit a échoué à l’étape jointure : quelles tâches faut-il relancer ?
2. Livrer des colis depuis l’entrepôt vers tous les points relais en minimisant le temps de trajet vers chacun.
3. Relier les points relais par un réseau de navettes, en minimisant la longueur totale des lignes.
4. Savoir combien de colis par jour peuvent partir de l’entrepôt vers la ville, compte tenu du nombre de camions sur chaque axe.
5. Repérer, dans le graphe « tel livre cite tel livre », des groupes de livres qui se citent tous mutuellement.

Voir la solution

1. Le pipeline est un DAG ; il faut relancer jointure et tous ses descendants (un parcours depuis jointure), dans un ordre topologique : jointure, features, entrainement, evaluation, tableau_de_bord.
2. Graphe orienté valué par les temps (positifs) : Dijkstra depuis l’entrepôt, qui donne l’arborescence des plus courts chemins vers tous les points relais.
3. Graphe non orienté valué par les distances : arbre couvrant de coût minimal (Kruskal ou Prim).
4. Réseau de transport avec des capacités (colis par jour sur chaque axe) : flot maximal par Ford-Fulkerson ; la coupe minimale indique les axes à renforcer.
5. Graphe orienté des citations : composantes fortement connexes (Tarjan ou Kosaraju). Pour des groupes « très liés » sans exiger l’accessibilité mutuelle, on utiliserait plutôt une détection de communautés.

En code

Python

pipeline = {
    "ventes": ["nett_ventes"], "clients": ["nett_clients"], "calendrier": ["features"],
    "nett_ventes": ["jointure"], "nett_clients": ["jointure"],
    "jointure": ["features", "tableau_de_bord"], "features": ["entrainement"],
    "entrainement": ["evaluation"], "evaluation": ["tableau_de_bord"], "tableau_de_bord": [],
}

# Un DFS lancé depuis la tâche en échec visite exactement ses descendants ;
# ses dates de fin, lues à l'envers, donnent un ordre topologique pour les relancer.
fin, vus = [], set()
def explorer(x):
    vus.add(x)
    for y in pipeline[x]:
        if y not in vus:
            explorer(y)
    fin.append(x)                  # x est terminé : tous ses descendants le sont déjà

explorer("jointure")
print(fin[::-1])
# ['jointure', 'features', 'entrainement', 'evaluation', 'tableau_de_bord']

R

pipeline <- list(ventes = "nett_ventes", clients = "nett_clients", calendrier = "features",
                 nett_ventes = "jointure", nett_clients = "jointure",
                 jointure = c("features", "tableau_de_bord"), features = "entrainement",
                 entrainement = "evaluation", evaluation = "tableau_de_bord",
                 tableau_de_bord = character(0))

# Descendants de la tâche en échec (parcours avec une pile)
vus <- "jointure"; pile <- "jointure"
while (length(pile) > 0) {
  x <- pile[1]; pile <- pile[-1]
  nouveaux <- setdiff(pipeline[[x]], vus)
  vus <- c(vus, nouveaux); pile <- c(nouveaux, pile)
}

# Ordre topologique par Kahn, puis on ne garde que les descendants
d_moins <- table(factor(unlist(pipeline), levels = names(pipeline)))
file <- names(pipeline)[d_moins == 0]; ordre <- c()
while (length(file) > 0) {
  x <- file[1]; file <- file[-1]; ordre <- c(ordre, x)
  for (y in pipeline[[x]]) { d_moins[y] <- d_moins[y] - 1; if (d_moins[y] == 0) file <- c(file, y) }
}
ordre[ordre %in% vus]
# "jointure" "features" "entrainement" "evaluation" "tableau_de_bord"