Expérience · Graphes

FlyWire Codex : la propagation dans les graphes du connectome, cartographiée

Cette expérience s’inscrit dans mon étude de la propagation de l’activité dans les réseaux de neurones et dans les graphes, en vue d’une IA embarquée. FlyWire Codex en fournit des cas réels : trois défis de calcul sur les graphes du connectome de la drosophile publié par le consortium FlyWire. Chaque score est recalculé par un calcul déterministe, identique d’une exécution à l’autre, et les données de graphes ont permis d’établir une carte : une visualisation de la propagation par problème, des schémas et des tableaux. Les trois résultats sont postérieurs à la clôture de leur défi et partent de solutions publiées par d’autres participants ; la provenance est donnée avec chacun.

noyau saut 1 saut 2 saut 3 saut 4 saut 5 sauts 6+ jamais atteints

1. La question : comment une activité se propage-t-elle dans un graphe ?

Dans un réseau, une activité part d’un nœud et atteint ses voisins saut après saut. Où va-t-elle, quelles zones atteint-elle, par quels chemins revient-elle ? C’est la question que j’étudie pour une IA embarquée, et le connectome en offre un terrain à échelle réelle : des graphes de plus de 130 000 neurones et de millions de connexions. FlyWire Codex y pose des problèmes de calcul chiffrés, jugés par un arbitre extérieur. Le schéma ci-dessous fixe le vocabulaire : un saut est une connexion franchie.

Trois défis de Codex sont traités ici. Chacun pose la question de la propagation sous un angle différent.

2. FlyWire et son rôle

FlyWire est un consortium scientifique qui a reconstitué et corrigé collectivement le connectome de la drosophile adulte (S. Dorkenwald et al., Nature 634, 2024), puis annoté les types de cellules (P. Schlegel et al., Nature 634, 2024). Codex est la plateforme qui met ces données à disposition et qui héberge des défis de calcul ; les organisateurs tiennent le classement de chaque défi et attribuent le titre de « Winner » à son échéance officielle.

Données et citation d’usage. Les données appartiennent au consortium FlyWire (version 783). S. Dorkenwald et al., « Neuronal wiring diagram of an adult brain », Nature 634, 2024 ; P. Schlegel et al., « Whole-brain annotation and multi-connectome cell typing of Drosophila », Nature 634, 2024. Cette page ne rediffuse aucune donnée brute du connectome (ni liste de neurones, ni liste de connexions) : les figures et les fichiers JSON sont des grandeurs dérivées (comptages, sommes, parts) calculées à partir des graphes des défis, avec les noms des 31 types de cellules annotés par le consortium.

3. Max Quasi-Cliques : les zones denses, saut après saut

La règle est publiée sur la page du défi : une ligne de k neurones portant m connexions satisfait le niveau i si m ≥ k(k−1)/2 × 1/2ⁱ. Le score additionne k_i/2ⁱ, où k_i est la taille du plus grand ensemble qui satisfait le niveau i. Le résultat vaut exactement 973135/1024. Il ne diffère du score de tête précédent que par un neurone au niveau 10 : 60 431 neurones contre 60 430.

Visualisation de la propagation

Le niveau 0 est un ensemble de 40 neurones tous reliés deux à deux. En partant d’eux, la propagation atteint 2 271 neurones au saut 1, 11 546 au saut 2, 55 755 au saut 3, 53 083 au saut 4, 9 180 au saut 5, puis 608 aux sauts 6 à 11 ; 1 698 neurones du graphe ne sont jamais atteints (distance la plus courte dans le graphe non orienté). L’ensemble de niveau 11, le plus grand, couvre 74 % des neurones du saut 1, 85 % du saut 3 et s’arrête au saut 5. La figure reprend ces comptages : chaque anneau est un saut.

JSON

4. Minimum Feedback Arc Set : un ordre, et ce qui revient en arrière

Le score est le poids total des connexions qui vont d’un neurone de rang plus bas vers un neurone de rang plus haut : 35 474 664 sur un poids total de 41 912 141 (84,6 %). Le poids restant, 6 437 477 (15,4 %), revient en arrière : ce sont les arcs de retour.

départ de l’arc (rang plus élevé) arrivée (rang plus bas) arc de retour

JSON

5. Visual Columns : la propagation dans une colonne

Une colonne rassemble au plus une cellule de chacun des 31 types. Avec l’affectation déposée, 101 587 liaisons entre cellules tombent à l’intérieur d’une colonne : de 1 type à l’autre, 572 liaisons possibles sur 930 (31 × 30) sont présentes. Une colonne retient entre 150 et 2 820 synapses (médiane 1 870).

La propagation se lit sur ces liaisons : à chaque saut, l’activité d’un type se répartit entre ses types voisins au prorata de ses synapses sortantes dans les colonnes. Départ du type L1 : saut 1 : Mi1 34 %, L5 31 %, C3 17 % ; saut 2 : L1 12 %, Mi1 10 %, L2 10 %. Départ du type R7 : saut 1 : R8 53 %, L3 24 %, Tm20 9 % ; saut 2 : Mi9 20 %, Tm20 19 %, Mi1 15 %. Au bout de quatre sauts, l’activité est déjà étalée sur la plupart des types.

JSON

6. Ce qui est vérifié, et par qui

Le classement de chaque défi est tenu par FlyWire Codex, qui annonce vérifier les envois. Le juge officiel se trouve côté organisateurs : les programmes ci-dessus reprennent la règle telle qu’elle est publiée sur la page de chaque défi.

Revérifier soi-même

Les graphes sont ceux des défis, à télécharger sur Codex. Ce programme, en bibliothèque standard seule, recalcule les trois scores à partir d’un graphe et d’un fichier de solution ; il lit les nombres comme des entiers ou des rationnels exacts, sans arrondi.

import csv
from fractions import Fraction as F

def lire(chemin, entete=True):
    with open(chemin, newline="") as f:
        r = csv.reader(f)
        if entete:
            next(r)
        return list(r)

# Max Quasi-Cliques : graphe du défi (2 colonnes, sans en-tête) et fichier de 12 lignes de neurones
def score_quasi_cliques(aretes, lignes):
    stats = []
    for l in lignes:
        s = set(l)
        k = len(s)
        m = sum(1 for a, b in aretes if a in s and b in s)
        stats.append((k, m))
    return sum(F(max([k for k, m in stats if m >= F(k * (k - 1), 2) / 2 ** i], default=0), 2 ** i)
               for i in range(12))

# MFAS : graphe pondéré (Source, Cible, Poids) et ordre (Neurone, Rang)
def score_mfas(aretes, rang):
    return sum(int(w) for a, b, w in aretes if int(rang[a]) < int(rang[b]))

# Visual Columns : liaisons (de, vers, synapses) et affectation (cellule, type, colonne)
def score_colonnes(liaisons, colonne):
    return sum(int(w) for a, b, w in liaisons if colonne.get(a) is not None and colonne.get(a) == colonne.get(b))

aretes = lire("graphe_quasi_cliques.csv", entete=False)
print(score_quasi_cliques(aretes, lire("solution_quasi_cliques.csv", entete=False)))
rang = {n: r for n, r in lire("ordre_mfas.csv")}
print(score_mfas(lire("graphe_mfas.csv"), rang))
colonne = {c: (int(k) if k.isdigit() else None) for c, t, k in lire("colonnes.csv")}
print(score_colonnes(lire("liaisons_colonnes.csv"), colonne))

Sorties attendues avec les fichiers présentés : 973135/1024, 35474664 et 1396295. Les fichiers JSON de cette page portent l'empreinte sha256 de chaque fichier lu.

7. La carte

Les données de graphes m'ont permis d'établir des cartes : pour chaque problème, une vue d'ensemble calculée une fois, avec sa date et l'empreinte des fichiers dont elle est tirée, et qui se recalcule à l'identique à partir des données du défi. C'est le même principe que la carte de mes recherches, où chaque résultat certifié et chaque impasse sont inscrits (voir La carte).

La carte du câblage dans une colonne montre, type de cellule par type de cellule, où se concentrent les synapses retenues dans les colonnes.

8. Ce que modélise ce type de question

Les trois problèmes formalisent trois manières d'interroger un réseau où une activité circule : quels groupes de neurones forment une zone dense, selon quel ordre l'activité avance et ce qui revient en arrière, quelles unités se répètent à l'identique. Ce sont des questions de graphes, posées à l'échelle réelle d'un connectome publié ; elles sont aussi celles de l'étude de la propagation pour une IA embarquée, où la même exigence s'applique : un résultat qui se recalcule à l'identique et qui se revérifie.

Mon projet d'IA au service de ma recherche

Ce défi n'est pas un but en soi : c'est un banc d'essai de ma recherche sur une IA embarquée certifiable. Mon projet d'IA, dont le fonctionnement reste confidentiel, me permet d'atteindre la tête des classements des trois défis du Codex après leur clôture, scores recalculés en arithmétique exacte. Le certificat et l'arbitre en font foi : ce n'est pas mon explication qu'il faut croire, c'est le résultat qui se revérifie. Il s'agit du meilleur résultat connu à la date indiquée, pas d'un optimum démontré.