Phase 01: Math Foundations

Théorie des graphiques pour l'apprentissage automatique

Type: Build

Language:Python

Prerequisites: Phase 1, Lessons 01-03 (linear algebra, matrices)

Time: ~90 minutes

Objectifs d'apprentissage

• Construire une classe de graphes avec des représentations de matrice/liste adjacentes et mettre en œuvre des traverses BFS et DFS
• Compute le graphe Laplacien et utilise ses valeurs propres pour détecter les composants connectés et les nœuds de cluster
• Implémenter une ronde de message de style GNN passant comme une matrice d'adjacence normalisée
• Appliquer le regroupement spectrale pour partager un graphique en utilisant le vecteur Fiedler

Le problème

Les réseaux sociaux, les molécules, les bases de connaissances, les réseaux de citations, les cartes routières, tout cela sont des graphiques. La méthode ML traditionnelle traite les données comme des tables plates. Chaque ligne est indépendante. Chaque fonctionnalité est une colonne. Mais quand la structure des connexions compte, les tables échouent.

Considérez un réseau social. Vous voulez prédire quel produit un utilisateur achètera. Son historique d'achat compte. Mais l'historique d'achat de ses amis compte plus. Les connexions portent un signal.

Ou pensez à une molécule. Vous voulez prédire si elle se lie à une protéine. Les atomes sont importants, mais ce qui compte vraiment, c'est comment les atomes sont liés les uns aux autres. La structure est les données.

Les réseaux neuraux graphiques (GNN) sont le domaine de l'apprentissage profond qui connaît la croissance la plus rapide. Ils alimentent la découverte de médicaments, la recommandation sociale, la détection de fraude et le raisonnement graphique des connaissances.

Il vous faut quatre choses:

1. Une façon de représenter les graphiques comme des matrices (pour les multiplier)
2. Algorithmes de traverses pour explorer la structure du graphique
3. Le Laplacien -- la matrice la plus importante dans la théorie des graphiques spectraux
4. Passage de messages - l'opération qui fait fonctionner les GNN

Le concept

Graphiques: nœuds et bords

Un graphique G = (V, E) est constitué de sommets (nœuds) V et de bords E. Chaque bord relie deux nœuds.

Directed vs undirected.Dans un graphique non dirigé, bord (u, v) signifie que u se connecte à v et v se connecte à u. Dans un graphe dirigé (digraphe), bord (u, v) signifie que u pointe vers v, mais pas nécessairement l'inverse.

Weighted vs unweighted.Dans un graphique non pondéré, les bords existent ou non. Dans un graphique pondéré, chaque bord a un poids numérique - une distance, un coût, une force.

La matrice d'adjacence

La matrice d'adjacence A est la représentation du noyau. Pour un graphique avec n n nodes:

CopyA[i][j] = 1    if there is an edge from node i to node j
A[i][j] = 0    otherwise

Pour les graphiques non dirigés, A est symétrique: A[i][j] = A[j][i]. Pour les graphiques pondérés, A[i][j] = poids de bord (i, j).

Example -- a triangle:

CopyNodes: 0, 1, 2
Edges: (0,1), (1,2), (0,2)

A = [[0, 1, 1],
     [1, 0, 1],
     [1, 1, 0]]

La matrice d'adjacence est l'entrée de chaque GNN. Les opérations de la matrice sur A correspondent aux opérations sur le graphique.

Diplôme

Le degré d'un nœud est le nombre de bords qui y sont connectés. Pour les graphiques dirigés, vous avez des degrés in-grade (bords entrant) et out-grade (bords sortant).

La matrice de degrés D est diagonale:

CopyD[i][i] = degree of node i
D[i][j] = 0    for i != j

Pour l'exemple du triangle: D = diag(2, 2, 2) parce que chaque nœud se connecte à deux autres.

Le degré vous indique l'importance des nœuds. Le degré élevé = nœud de hub. La distribution des degrés d'un réseau révèle sa structure. Les réseaux sociaux suivent les lois de puissance (peu de nœuds, beaucoup de nœuds de feuilles). Les graphiques aléatoires ont des degrés distribués par Poisson.

BFS et DFS

Les deux algorithmes de traversage de graphes fondamentaux.

Breadth-First Search (BFS):Explorez tous les voisins d'abord, puis les voisins des voisins.

CopyBFS from node 0:
  Visit 0
  Queue: [1, 2]        (neighbors of 0)
  Visit 1
  Queue: [2, 3]        (add neighbors of 1)
  Visit 2
  Queue: [3]           (neighbors of 2 already visited)
  Visit 3
  Queue: []            (done)

Le BFS trouve les chemins les plus courts dans les graphiques non pondérés. La distance entre le début et un nœud équivaut au niveau du BFS auquel ce nœud est découvert pour la première fois. C'est pourquoi le BFS est utilisé pour les distances de compte hop dans les réseaux sociaux.

Depth-First Search (DFS):Faites le plus profond possible avant de revenir en arrière.

CopyDFS from node 0:
  Visit 0
  Stack: [1, 2]        (neighbors of 0)
  Visit 2               (pop from stack)
  Stack: [1, 3]         (add neighbors of 2)
  Visit 3               (pop from stack)
  Stack: [1]
  Visit 1               (pop from stack)
  Stack: []             (done)

Le DFS est utile pour:

• Trouver les composants connectés (exécuter DFS à partir de nœuds non visités)
• Détection du cycle (marges arrières dans l'arbre DFS)
• Sortement topologique (ordre de finition inverse du DFS)

Le graphe laplacien

L = D - A. La matrice la plus importante dans la théorie des graphiques spectraux.

Pour le triangle:

CopyD = [[2, 0, 0],    A = [[0, 1, 1],    L = [[2, -1, -1],
     [0, 2, 0],         [1, 0, 1],         [-1, 2, -1],
     [0, 0, 2]]         [1, 1, 0]]         [-1, -1,  2]]

Le Laplacien possède des propriétés remarquables:

1. L is positive semi-definite.Toutes les valeurs propres sont >= 0.

1. The number of zero eigenvalues equals the number of connected components.Un graphique connecté a exactement une valeur propre zéro. Un graphique avec 3 composants déconnectés a trois valeurs propres zéro.

1. The smallest non-zero eigenvalue (Fiedler value) measures connectivity.Une grande valeur Fiedler signifie que le graphique est bien connecté. une petite valeur Fiedler signifie que le graphique a un point faible - un goulet d'étranglement.

1. The eigenvector of the Fiedler value (Fiedler vector) reveals the best split.Les nœuds avec des valeurs positives vont dans un groupe, les nœuds avec des valeurs négatives vont dans l'autre.

graph TD
    subgraph "Graph to Matrices"
        G["Graph G"] --> A["Adjacency Matrix A"]
        G --> D["Degree Matrix D"]
        A --> L["Laplacian L = D - A"]
        D --> L
    end
    subgraph "Spectral Analysis"
        L --> E["Eigenvalues of L"]
        L --> V["Eigenvectors of L"]
        E --> C["Connected components (zeros)"]
        E --> F["Connectivity (Fiedler value)"]
        V --> S["Spectral clustering"]
    end

Propriétés spectrales

Les valeurs propres de la matrice adjacente et du Laplacien révèlent des propriétés structurelles sans aucune traversée.

Spectral clusteringfonctionne comme ceci:

1. Compute le Laplacien L
2. Trouvez les plus petits vecteurs propres de L (sautez le premier, qui est tous-un pour les graphiques connectés)
3. Utilisez ces propres vecteurs comme nouvelles coordonnées pour chaque nœud
4. Exécutez des k-média sur ces coordonnées

Pourquoi cela fonctionne-t-il ? Les propres vecteurs de L codent les fonctions " les plus lisses " du graphique. Les nœuds bien connectés obtiennent des valeurs propres similaires. Les nœuds séparés par un goulet d'étranglement obtiennent des valeurs différentes. Les propres vecteurs séparent naturellement des grappes.

Random walk connection.Le Laplacien normalisé se rapporte à des promenades aléatoires sur le graphique. La répartition stationnaire d'une marche aléatoire est proportionnelle au degré de nœud. Le temps de mélange (la rapidité avec laquelle la marche converge) dépend de l'écart spectrique.

Le message est passé

Le fonctionnement principal des réseaux neuraux graphiques. Chaque nœud collecte des messages de ses voisins, les agrégera et met à jour son propre état.

Copyh_v^(k+1) = UPDATE(h_v^(k), AGGREGATE({h_u^(k) : u in neighbors(v)}))

Dans la forme la plus simple, AGGREGATE = moyenne et UPDATE = transformation linéaire + activation:

Copyh_v^(k+1) = sigma(W * mean({h_u^(k) : u in neighbors(v)}))

C'est la multiplication de matrice déguisée. Si H est la matrice de toutes les caractéristiques du nœud et A est la matrice d'adjacence:

CopyH^(k+1) = sigma(A_norm * H^(k) * W)

où A_norm est la matrice d'adjacentité normalisée (chaque ligne s'élève à 1).

Une ronde de message de passage permet à chaque nœud de "voir" ses voisins immédiats. Deux rondes lui permettent de voir les voisins des voisins.

graph LR
    subgraph "Round 0"
        A0["Node A: [1,0]"]
        B0["Node B: [0,1]"]
        C0["Node C: [1,1]"]
    end
    subgraph "Round 1 (aggregate neighbors)"
        A1["Node A: avg(B,C) = [0.5, 1.0]"]
        B1["Node B: avg(A,C) = [1.0, 0.5]"]
        C1["Node C: avg(A,B) = [0.5, 0.5]"]
    end
    A0 --> A1
    B0 --> A1
    C0 --> A1
    A0 --> B1
    C0 --> B1
    A0 --> C1
    B0 --> C1

Concepts et applications de l'équipement

Faites-le

Étape 1: Classement de graphique à partir de zéro

pythonCopyclass Graph:
    def __init__(self, n_nodes, directed=False):
        self.n = n_nodes
        self.directed = directed
        self.adj = {i: {} for i in range(n_nodes)}

    def add_edge(self, u, v, weight=1.0):
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight

    def neighbors(self, node):
        return list(self.adj[node].keys())

    def degree(self, node):
        return len(self.adj[node])

    def adjacency_matrix(self):
        import numpy as np
        A = np.zeros((self.n, self.n))
        for u in range(self.n):
            for v, w in self.adj[u].items():
                A[u][v] = w
        return A

    def degree_matrix(self):
        import numpy as np
        D = np.zeros((self.n, self.n))
        for i in range(self.n):
            D[i][i] = self.degree(i)
        return D

    def laplacian(self):
        return self.degree_matrix() - self.adjacency_matrix()

La liste des adjacents (self.adjLa conversion de matrice d'adjacence utilise numpy parce que toutes les opérations spectrales en ont besoin.

Étape 2: BFS et DFS

pythonCopyfrom collections import deque

def bfs(graph, start):
    visited = set()
    order = []
    distances = {}
    queue = deque([(start, 0)])
    visited.add(start)
    while queue:
        node, dist = queue.popleft()
        order.append(node)
        distances[node] = dist
        for neighbor in graph.neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return order, distances


def dfs(graph, start):
    visited = set()
    order = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph.neighbors(node)):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

BFS utilise une déque (coupe double) pour O(1) pop-left. DFS utilise une liste comme une pile. Les deux visiter chaque nœud exactement une fois - O(V + E) temps.

Étape 3: Les composants connectés et les valeurs propres laplaciennes

pythonCopydef connected_components(graph):
    visited = set()
    components = []
    for node in range(graph.n):
        if node not in visited:
            order, _ = bfs(graph, node)
            visited.update(order)
            components.append(order)
    return components


def laplacian_eigenvalues(graph):
    import numpy as np
    L = graph.laplacian()
    eigenvalues = np.linalg.eigvalsh(L)
    return eigenvalues

eigvalshest pour les matrices symétriques -- le Laplacien est toujours symétrique pour les graphiques non dirigés. Il renvoie les valeurs propres dans l'ordre ascendant.

Étape 4: Clusterage spectrique

pythonCopydef spectral_clustering(graph, k=2):
    import numpy as np
    L = graph.laplacian()
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    features = eigenvectors[:, 1:k+1]

    labels = np.zeros(graph.n, dtype=int)
    for i in range(graph.n):
        if features[i, 0] >= 0:
            labels[i] = 0
        else:
            labels[i] = 1
    return labels

Pour k=2, le signe du vecteur Fiedler divise le graphique en deux graphes. Pour k>2, vous exécutez des moyens k sur les premiers vecteurs propres k (à l'exclusion du vecteur propre trivial tous-un).

Étape 5: Transmission du message

pythonCopydef message_passing(graph, features, weight_matrix):
    import numpy as np
    A = graph.adjacency_matrix()
    row_sums = A.sum(axis=1, keepdims=True)
    row_sums[row_sums == 0] = 1
    A_norm = A / row_sums
    aggregated = A_norm @ features
    output = aggregated @ weight_matrix
    return output

Il s'agit d'une série de messages GNN. Les nouvelles caractéristiques de chaque nœud sont la moyenne pondérée des caractéristiques de ses voisins, transformée par la matrice de poids.

Utilisez-le

Avec networkx et numpy, les mêmes opérations sont unliners:

pythonCopyimport networkx as nx
import numpy as np

G = nx.karate_club_graph()

A = nx.adjacency_matrix(G).toarray()
L = nx.laplacian_matrix(G).toarray()

eigenvalues = np.linalg.eigvalsh(L.astype(float))
print(f"Smallest eigenvalues: {eigenvalues[:5]}")
print(f"Connected components: {nx.number_connected_components(G)}")

communities = nx.community.greedy_modularity_communities(G)
print(f"Communities found: {len(communities)}")

pr = nx.pagerank(G)
top_nodes = sorted(pr.items(), key=lambda x: x[1], reverse=True)[:5]
print(f"Top 5 PageRank nodes: {top_nodes}")

networkx traite des graphiques de toutes tailles avec des backends C optimisés. Utilisez-le dans la production. Utilisez votre mise en œuvre à partir de zéro pour comprendre ce qu'il fait.

analyse spectrale de la nudité

pythonCopyimport numpy as np

A = np.array([
    [0, 1, 1, 0, 0],
    [1, 0, 1, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0]
])

D = np.diag(A.sum(axis=1))
L = D - A

eigenvalues, eigenvectors = np.linalg.eigh(L)
print(f"Eigenvalues: {np.round(eigenvalues, 4)}")
print(f"Fiedler value: {eigenvalues[1]:.4f}")
print(f"Fiedler vector: {np.round(eigenvectors[:, 1], 4)}")

fiedler = eigenvectors[:, 1]
group_a = np.where(fiedler >= 0)[0]
group_b = np.where(fiedler < 0)[0]
print(f"Cluster A: {group_a}")
print(f"Cluster B: {group_b}")

Le vecteur Fiedler fait le gros du travail. Les entrées positives dans un groupe, négatives dans l'autre. Aucune optimisation itérative n'est nécessaire - juste une propre composition.

La faire partir

Cette leçon donne:

• outputs/skill-graph-analysis.md-- une référence de compétence pour l'analyse des données structurées par graphique

Les liens

Les GNN méritent une mention spéciale. L'opération de convolutions de graphes dans GCN (Kipf & Welling, 2017) utilise la matrice d'adjacence avec des boucles auto-ajoutées, A_hat = A + I:

textCopyH^(l+1) = sigma(D_hat^(-1/2) * A_hat * D_hat^(-1/2) * H^(l) * W^(l))

où A_hat = A + I (adjacence plus auto-loops) et D_hat est la matrice de degrés de A_hat. Les boucles autonomes assurent que chaque nœud inclut ses propres caractéristiques lors de l'agrégation. C'est exactement le message qui passe avec une normalisation symétrique. D_hat^(-1/2) A_hat D_hat^(-1/2) est la matrice d'adjacence normalisée. Le Laplacien apparaît parce que cette normalisation est liée à L_sym = I - D^(-1/2) A D^(-1/2). Comprendre le Laplacien signifie comprendre pourquoi les GCN fonctionnent.

Exercices

1. Implement PageRank from scratch.Commencez par des scores uniformes. À chaque étape: score(v) = (1-d) /n + d * somme(score(u) /out_degree(u)) pour tous les u pointant vers v. Utilisez d=0,85.

1. Find communities using spectral clustering.Créer un graphique avec deux grappes clairement séparées (par exemple, deux cliques reliés par un seul bord). Exécuter le regroupement spectrale et vérifier qu'il trouve la bonne fraction. Que se passe-t-il lorsque vous ajoutez plus de bordes croisées?

1. Implement Dijkstra's algorithmPour les traces les plus courtes dans les graphiques pondérés, comparez les résultats avec BFS sur le même graphique avec des poids uniformes.

1. Build a 2-layer message passing network.Appliquez un message qui passe deux fois avec des matrices de poids différentes. Montrez qu'après 2 tours, chaque nœud a des informations de son voisinage de 2 tours.

1. Analyze a real-world graph.Utilisez le graphique du Karate Club (34 nœuds, 78 bords). Comptez la répartition des degrés, les valeurs propres de Laplace et le regroupement spectrique. Comparer le résultat du regroupement spectrique avec la fraction de vérité de la terre connue.

Les termes clés

Pour en savoir plus

• Kipf & Welling (2017)-- "Classification semi-surveillée avec des réseaux convolutifs graphiques". Le document qui a lancé les GNN modernes.
• Spielman (2012)-- notes de conférence sur la théorie des graphes spectraux. L'introduction définitive aux Laplaciens, aux lacunes spectrales et à la partition des graphes.
• Hamilton (2020)-- "L'apprentissage de la représentation graphique". Livre couvrant les GNN des fondamentaux aux applications.
• Bronstein et al. (2021)-- "L'apprentissage géométrique en profondeur: réseaux, groupes, graphiques, géodésiques et gauges". Le document de cadre unificateur.
• Veličković et al. (2018)-- "Graph Attention Networks". Élargit le message passé avec des mécanismes d'attention.

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.