Teoria grafurilor pentru învățarea automată — lecție practică de AI…

Grafurile sunt structura de date a relațiilor. Dacă datele dumneavoastră conțin conexiuni, aveți nevoie de teoria grafurilor.

Tip: Construire Limbaj: Python Cerințe preliminare: Faza 1, lecțiile 01-03 (algebră liniară, matrice) Durată: ~90 de minute

Obiective de învățare

Construirea unei clase pentru grafuri, cu reprezentări prin matrice și liste de adiacență, și implementarea parcurgerilor BFS și DFS
Calcularea Laplacianei unui graf și folosirea valorilor sale proprii pentru detectarea componentelor conexe și gruparea nodurilor
Implementarea unei runde de propagare a mesajelor în stil GNN ca înmulțire cu matricea de adiacență normalizată
Aplicarea clusteringului spectral pentru partiționarea unui graf cu ajutorul vectorului Fiedler

Problema

Rețelele sociale, moleculele, bazele de cunoștințe, rețelele de citări și hărțile rutiere sunt toate grafuri. Învățarea automată tradițională tratează datele ca tabele plate. Fiecare rând este independent. Fiecare caracteristică este o coloană. Când contează însă structura conexiunilor, tabelele nu mai sunt suficiente.

Luați ca exemplu o rețea socială. Doriți să preziceți ce produs va cumpăra un utilizator. Istoricul său de cumpărături contează, dar și istoricul de cumpărături al prietenilor săi poate conta și mai mult. Conexiunile poartă semnal.

Sau luați o moleculă. Doriți să preziceți dacă se leagă de o proteină. Atomii contează, dar ceea ce contează cu adevărat este modul în care sunt legați între ei. Structura reprezintă datele.

Rețelele neuronale pe grafuri (GNN) constituie un domeniu important și în dezvoltare rapidă al învățării profunde. Ele susțin descoperirea medicamentelor, recomandările sociale, detectarea fraudelor și raționamentul pe grafuri de cunoștințe. Fiecare GNN pornește de la aceeași bază: teoria elementară a grafurilor.

Aveți nevoie de patru elemente:

O modalitate de a reprezenta grafurile ca matrice (pentru a le putea înmulți)
Algoritmi de parcurgere pentru explorarea structurii grafului
Laplaciana — matricea centrală a teoriei spectrale a grafurilor
Propagarea mesajelor — operația care face GNN-urile să funcționeze

Conceptul

Grafuri: noduri și muchii

Un graf G = (V, E) este alcătuit din vârfurile (nodurile) V și muchiile E. Fiecare muchie conectează două noduri.

Orientat și neorientat. Într-un graf neorientat, muchia (u, v) înseamnă că u este conectat la v ȘI v la u. Într-un graf orientat (digraf), muchia (u, v) înseamnă că u indică spre v, dar nu neapărat și invers.

Ponderat și neponderat. Într-un graf neponderat, muchiile fie există, fie nu. Într-un graf ponderat, fiecare muchie are o pondere numerică — o distanță, un cost sau o intensitate.

Tip de graf	Exemplu
Neorientat, neponderat	Rețea de prietenii Facebook
Orientat, neponderat	Rețea de urmărire Twitter
Neorientat, ponderat	Hartă rutieră (distanțe)
Orientat, ponderat	Legături între pagini web (scoruri PageRank)

Notă tehnică a traducerii: PageRank atribuie în mod obișnuit scoruri nodurilor (paginilor), nu muchiilor. Un graf web poate avea muchii ponderate, dar „scorurile PageRank” nu reprezintă un exemplu de ponderi ale legăturilor.

Matricea de adiacență

Matricea de adiacență A este o reprezentare fundamentală. Pentru un graf cu n noduri:

A[i][j] = 1    dacă există o muchie de la nodul i la nodul j
A[i][j] = 0    în caz contrar

Pentru grafurile neorientate, A este simetrică: A[i][j] = A[j][i]. Pentru grafurile ponderate, A[i][j] = ponderea muchiei (i, j).

Exemplu — un triunghi:

Noduri: 0, 1, 2
Muchii: (0,1), (1,2), (0,2)

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

Matricea de adiacență poate servi drept intrare pentru GNN-uri. Operațiile matriciale asupra lui A corespund unor operații asupra grafului.

Notă tehnică a traducerii: nu fiecare GNN primește o matrice de adiacență densă. Implementările pentru grafuri mari folosesc frecvent liste de muchii, matrici rare sau alte structuri echivalente, tocmai pentru a evita costul O(n^2).

Gradul

Gradul unui nod este numărul muchiilor incidente cu acesta. Pentru grafurile orientate există grad interior (muchiile care intră) și grad exterior (muchiile care ies).

Matricea gradelor D este diagonală:

D[i][i] = gradul nodului i
D[i][j] = 0    pentru i != j

În exemplul triunghiului, D = diag(2, 2, 2), deoarece fiecare nod este conectat la alte două.

Gradul oferă informații despre importanța unui nod. Grad mare = nod central. Distribuția gradelor unei rețele îi dezvăluie structura. Unele rețele sociale au distribuții cu cozi grele sau aproximativ de tip lege de putere (puține noduri centrale, multe noduri cu grad mic). În modelul aleator Erdős-Rényi, distribuția gradelor este binomială la dimensiune finită și se apropie de Poisson în regimul rar corespunzător.

Notă tehnică a traducerii: originalul generalizează excesiv. Rețelele sociale nu urmează universal legi de putere, iar „grafurile aleatoare” reprezintă o familie largă; afirmația Poisson este specifică modelului Erdős-Rényi și limitei sale rare.

BFS și DFS

Aceștia sunt cei doi algoritmi fundamentali de parcurgere a grafurilor. Aveți nevoie de amândoi.

Căutarea în lățime (BFS): explorați mai întâi toți vecinii, apoi vecinii acestora. Folosește o coadă (FIFO).

BFS pornind din nodul 0:
  Vizitați 0
  Coadă: [1, 2]        (vecinii lui 0)
  Vizitați 1
  Coadă: [2, 3]        (adăugați vecinii lui 1)
  Vizitați 2
  Coadă: [3]           (vecinii lui 2 sunt deja vizitați)
  Vizitați 3
  Coadă: []            (final)

BFS găsește drumurile cele mai scurte în grafuri neponderate. Distanța de la punctul de pornire la orice nod accesibil este egală cu nivelul BFS la care nodul este descoperit prima dată. De aceea BFS este folosit pentru distanțe exprimate în număr de salturi în rețelele sociale.

Căutarea în adâncime (DFS): avansați cât mai mult înainte de a reveni. Folosește o stivă (LIFO) sau recursivitatea.

DFS pornind din nodul 0:
  Vizitați 0
  Stivă: [1, 2]        (vecinii lui 0)
  Vizitați 2           (extrageți din stivă)
  Stivă: [1, 3]        (adăugați vecinii lui 2)
  Vizitați 3           (extrageți din stivă)
  Stivă: [1]
  Vizitați 1           (extrageți din stivă)
  Stivă: []             (final)

DFS este utilă pentru:

Găsirea componentelor conexe (rulați DFS din nodurile nevizitate)
Detectarea ciclurilor (muchii de întoarcere în arborele DFS)
Sortarea topologică (ordinea inversă a finalizării DFS)

Algoritm	Structură de date	Găsește	Caz de utilizare
BFS	Coadă	Drumuri cele mai scurte	Distanță în rețele sociale, parcurgerea grafurilor de cunoștințe
DFS	Stivă	Componente, cicluri	Conectivitate, sortare topologică

Laplaciana grafului

L = D - A, matricea centrală a teoriei spectrale a grafurilor.

Pentru triunghi:

D = [[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]]

Pentru un graf neorientat cu ponderi nenegative, Laplaciana are proprietăți remarcabile:

L este pozitiv semidefinită. Toate valorile proprii sunt >= 0.
Numărul valorilor proprii zero este egal cu numărul componentelor conexe. Un graf conex are exact o valoare proprie zero. Un graf cu 3 componente disjuncte are trei valori proprii zero.
Cea mai mică valoare proprie nenulă (valoarea Fiedler) măsoară conectivitatea algebrică. O valoare Fiedler mare indică, în sens spectral, un graf bine conectat. O valoare mică indică o zonă slabă — un blocaj.
Vectorul propriu al valorii Fiedler (vectorul Fiedler) sugerează o partiționare. Nodurile pot fi împărțite după semnul sau pragul componentelor vectorului. Aceasta este baza unei forme de clustering spectral.

Notă tehnică a traducerii: proprietățile de mai sus nu se transferă nemodificat la grafuri orientate ori la ponderi negative. De asemenea, partiționarea după semnul vectorului Fiedler rezolvă o relaxare spectrală și nu garantează „cea mai bună” tăietură pentru orice obiectiv discret.

Диаграмма к уроку «Teoria grafurilor pentru învățarea automată»

Proprietăți spectrale

Valorile proprii ale matricei de adiacență și ale Laplacianei dezvăluie proprietăți structurale fără parcurgerea explicită a grafului.

Clusteringul spectral funcționează astfel într-o formulare uzuală:

Calculați Laplaciana L
Găsiți vectorii proprii asociați celor mai mici valori proprii ale lui L
Folosiți acești vectori drept coordonate noi pentru fiecare nod
Rulați k-means pe aceste coordonate

De ce funcționează? Vectorii proprii ai lui L codifică funcțiile cele mai „netede” pe graf. Nodurile bine conectate primesc valori similare. Nodurile separate de un blocaj primesc valori diferite. Vectorii proprii separă în mod natural clusterele în relaxarea spectrală.

Notă tehnică a traducerii: alegerea vectorilor depinde de varianta clusteringului spectral și de Laplaciana folosită. Pentru un graf conex, vectorul constant asociat valorii zero este trivial; pentru grafuri neconexe există mai mulți vectori proprii cu valoarea zero, iar eliminarea automată a unui singur vector nu este suficientă.

Legătura cu mersurile aleatoare. Laplaciana normalizată este legată de mersurile aleatoare pe graf. Pentru un mers aleator simplu pe un graf neorientat, distribuția staționară este proporțională cu gradul nodului. Timpul de amestecare depinde de diferența spectrală relevantă.

Notă tehnică a traducerii: existența unei distribuții staționare proporționale cu gradul nu implică automat convergența către ea din orice stare. Pentru convergența obișnuită sunt necesare ireductibilitatea și aperiodicitatea; un graf bipartit produce periodicitate dacă mersul nu este făcut „leneș”.

Propagarea mesajelor

Aceasta este operația centrală a rețelelor neuronale pe grafuri. Fiecare nod colectează mesaje de la vecini, le agregă și își actualizează propria stare.

h_v^(k+1) = ACTUALIZARE(h_v^(k), AGREGARE({h_u^(k) : u în vecini(v)}))

În forma cea mai simplă, AGGREGATE = mean, iar UPDATE = transformare liniară + activare:

h_v^(k+1) = sigma(W * medie({h_u^(k) : u în vecini(v)}))

Aceasta este o înmulțire de matrice sub o altă formă. Dacă H este matricea tuturor caracteristicilor nodurilor, iar A este matricea de adiacență:

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

unde A_norm este matricea de adiacență normalizată (fiecare rând are suma 1).

O rundă de propagare a mesajelor permite fiecărui nod să își „vadă” vecinii imediați. Două runde îi permit să vadă vecinii vecinilor. După K runde, fiecare nod primește informații din vecinătatea sa la K salturi, în limita structurii și a agregării folosite.

Диаграмма к уроку «Teoria grafurilor pentru învățarea automată»

Concepte și aplicații în învățarea automată

Concept	Aplicație în învățarea automată
Matrice de adiacență	Reprezentarea intrării GNN
Laplaciana grafului	Clustering spectral, detectarea comunităților
BFS/DFS	Parcurgerea grafurilor de cunoștințe, găsirea drumurilor
Distribuția gradelor	Importanța nodurilor, ingineria caracteristicilor
Propagarea mesajelor	Straturi GNN (GCN, GAT, GraphSAGE)
Valorile proprii ale lui L	Detectarea comunităților, partiționarea grafului
Clustering spectral	Gruparea nesupravegheată a nodurilor
PageRank	Importanța nodurilor, căutare web

graph-degree-distribution

Construiți

Pasul 1: clasa Graph de la zero

class 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()

Lista de adiacență (self.adj) stochează eficient vecinii. Conversia la matricea de adiacență folosește NumPy, deoarece toate operațiile spectrale au nevoie de ea.

Notă tehnică a traducerii: pentru un graf ponderat, diagonala matricei gradelor folosite în Laplaciana combinatorie trebuie să conțină suma ponderilor incidente, nu numărul vecinilor. În plus, opțiunea directed=True produce în general o matrice nesimetrică, pentru care proprietățile spectrale prezentate anterior nu se aplică direct. Blocul executabil original a fost păstrat neschimbat.

Pasul 2: BFS și DFS

from 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 folosește un deque (coadă cu două capete) pentru operația popleft în O(1). DFS folosește o listă drept stivă. Ambele vizitează exact o dată fiecare nod accesibil din punctul de pornire și rulează în timp O(V + E) pentru o reprezentare prin liste de adiacență.

Notă tehnică a traducerii: într-un graf neconex, un singur apel pornit dintr-un nod nu vizitează toate nodurile grafului, ci doar componenta accesibilă din acel nod.

Pasul 3: componente conexe și valorile proprii ale Laplacianei

def 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

Notă tehnică a traducerii: Funcția connected_components este corectă pentru grafuri neorientate, dar clasa permite și directed=True. Într-un graf orientat, BFS urmărește numai muchiile ieșite; această parcurgere nu calculează nici componentele slab conexe, nici componentele tare conexe și, în funcție de ordinea nodurilor, grupurile returnate se pot suprapune. Pentru componente slab conexe trebuie ignorată orientarea muchiilor, iar pentru componente tare conexe este necesar un algoritm dedicat, precum Tarjan sau Kosaraju. Blocul executabil original a fost păstrat neschimbat.

eigvalsh este destinat matricelor simetrice — Laplaciana este simetrică pentru grafurile neorientate cu ponderi simetrice. Returnează valorile proprii în ordine crescătoare. Numărați valorile numeric apropiate de zero pentru a determina numărul componentelor conexe.

Pasul 4: clustering spectral

def 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

Pentru k=2, semnul vectorului Fiedler împarte graful în două clustere. Pentru k>2, ar trebui să rulați k-means pe o selecție corespunzătoare de vectori proprii, în funcție de varianta spectrală aleasă.

Notă tehnică a traducerii: implementarea originală returnează numai etichetele 0 și 1 și folosește doar prima coloană din features, indiferent de valoarea lui k. Prin urmare, ea implementează numai cazul binar și nu realizează clustering cu k>2. Blocul executabil a fost păstrat neschimbat.

Pasul 5: propagarea mesajelor

def 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

Aceasta este o rundă de propagare a mesajelor într-un GNN. Noile caracteristici ale fiecărui nod sunt media ponderată a caracteristicilor vecinilor săi, transformată prin matricea ponderilor. Stivuiți mai multe runde pentru a propaga informația mai departe.

Notă tehnică a traducerii: implementarea nu adaugă auto-bucle. Prin urmare, un nod nu își include propriile caracteristici în agregare, iar un nod izolat primește vectorul zero înaintea transformării liniare.

Folosiți

Cu NetworkX și NumPy, aceleași operații se scriu într-o singură linie:

import 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 oferă o interfață comodă pentru grafuri și numeroși algoritmi. Folosiți-l atunci când se potrivește scării și cerințelor aplicației; pentru performanță mai mare, poate redirecționa anumite operații către back-enduri terțe instalate separat. Folosiți implementarea dumneavoastră de la zero pentru a înțelege ce face.

Notă tehnică a traducerii: NetworkX este implicit o implementare Python pură, nu o bibliotecă bazată în general pe back-enduri C optimizate. Versiunile actuale pot apela back-enduri terțe opționale, precum nx-cugraph sau nx-parallel, dacă acestea sunt instalate și configurate.

Analiză spectrală cu NumPy

import 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}")

Vectorul Fiedler efectuează partea esențială a calculului. Componentele nenegative formează un cluster, iar cele negative pe celălalt. Pentru această relaxare spectrală nu este necesară o optimizare iterativă suplimentară — doar o descompunere în valori și vectori proprii.

Livrați

Această lecție produce:

outputs/skill-graph-analysis.md — o referință de competență pentru analiza datelor structurate ca graf

Legături

Concept	Unde apare
Matrice de adiacență	Intrare pentru GCN, GAT, GraphSAGE
Laplaciană	Clustering spectral, filtre ChebNet
BFS	Parcurgerea grafurilor de cunoștințe, interogări pentru drumul cel mai scurt
Propagarea mesajelor	Fiecare strat GNN, propagarea neuronală a mesajelor
Diferență spectrală	Conectivitatea grafului, timpul de amestecare al mersurilor aleatoare
Distribuția gradelor	Rețele cu legi de putere, ingineria caracteristicilor nodurilor
Componente conexe	Preprocesare, tratarea grafurilor neconexe
PageRank	Clasificarea importanței nodurilor, inițializarea atenției

GNN-urile merită o mențiune specială. Operația de convoluție pe graf din GCN (Kipf & Welling, 2017) folosește matricea de adiacență cu auto-bucle adăugate, A_hat = A + I:

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

unde A_hat = A + I (adiacență plus auto-bucle), iar D_hat este matricea gradelor lui A_hat. Auto-buclele fac ca fiecare nod să își includă propriile caracteristici în agregare. Aceasta este exact propagarea mesajelor cu normalizare simetrică. D_hat^(-1/2) * A_hat * D_hat^(-1/2) este matricea de adiacență normalizată. Laplaciana apare deoarece această normalizare este legată de L_sym = I - D^(-1/2) * A * D^(-1/2). Înțelegerea Laplacianei vă ajută să înțelegeți construcția GCN-urilor.

Exerciții

Implementați PageRank de la zero. Porniți cu scoruri uniforme. La fiecare pas: score(v) = (1-d)/n + d * sum(score(u)/out_degree(u)) pentru toate nodurile u care indică spre v. Folosiți d=0.85. Rulați până la convergență (modificare < 1e-6). Testați pe un graf web mic.

Notă tehnică a traducerii: formula exercițiului trebuie să precizeze tratarea nodurilor fără muchii ieșite (dangling nodes); în PageRank standard, masa lor este redistribuită conform unei distribuții alese, adesea uniform.

Găsiți comunități prin clustering spectral. Creați un graf cu două clustere clar separate (de exemplu, două clici unite printr-o singură muchie). Rulați clusteringul spectral și verificați dacă găsește partiționarea corectă. Ce se întâmplă pe măsură ce adăugați mai multe muchii între clustere?
Implementați algoritmul lui Dijkstra pentru drumurile cele mai scurte în grafuri ponderate. Comparați rezultatele cu BFS pe același graf cu ponderi uniforme.

Notă tehnică a traducerii: algoritmul Dijkstra standard presupune ponderi nenegative ale muchiilor; în prezența ponderilor negative este necesar un alt algoritm, precum Bellman-Ford.

Construiți o rețea de propagare a mesajelor cu 2 straturi. Aplicați propagarea mesajelor de două ori, cu matrice de ponderi diferite. Arătați că după 2 runde fiecare nod deține informații din vecinătatea sa la 2 salturi.
Analizați un graf real. Folosiți graful Karate Club (34 de noduri, 78 de muchii). Calculați distribuția gradelor, valorile proprii ale Laplacianei și clusteringul spectral. Comparați rezultatul cu partiționarea reală cunoscută.

Termeni-cheie

Termen	Ce spun oamenii	Ce înseamnă de fapt
Graf	„Noduri și muchii”	O structură matematică G=(V,E) care codifică relații între perechi de elemente
Matrice de adiacență	„Tabelul conexiunilor”	O matrice n x n în care A[i][j] = 1 dacă nodul i este conectat la nodul j, în cazul neponderat
Grad	„Cât de conectat este un nod”	Numărul muchiilor incidente unui nod; în grafurile orientate se disting gradul interior și cel exterior
Laplaciană	„D minus A”	L = D - A, matricea ale cărei valori proprii dezvăluie structura unui graf neorientat
Valoare Fiedler	„Conectivitatea algebrică”	A doua cea mai mică valoare proprie a lui L pentru un graf neorientat; este pozitivă exact când graful este conex
BFS	„Căutare nivel cu nivel”	Parcurgere care vizitează toți vecinii înainte de a avansa în adâncime și găsește drumuri minime în grafuri neponderate
DFS	„Mai întâi în adâncime”	Parcurgere care urmează un drum până la capăt înainte de a reveni
Propagarea mesajelor	„Nodurile comunică cu vecinii”	Fiecare nod agregă informații de la vecini; operația centrală a multor GNN-uri
Clustering spectral	„Grupare după vectori proprii”	Partiționarea unui graf folosind vectori proprii ai Laplacianei sale
Componentă conexă	„O bucată separată”	Un subgraf conex maximal, în care fiecare nod poate ajunge la oricare altul

Lecturi suplimentare

Kipf & Welling (2017) — „Semi-Supervised Classification with Graph Convolutional Networks”. Articolul care a popularizat GNN-urile moderne. Arată cum convoluțiile spectrale pe graf se simplifică la o formă de propagare a mesajelor.
Spielman (2012) — notele de curs „Spectral Graph Theory”. O introducere de referință în Laplaciene, diferențe spectrale și partiționarea grafurilor.
Hamilton (2020) — „Graph Representation Learning”. Carte care tratează GNN-urile de la fundamente până la aplicații.
Bronstein et al. (2021) — „Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges”. Articolul despre cadrul unificator.
Veličković et al. (2018) — „Graph Attention Networks”. Extinde propagarea mesajelor cu mecanisme de atenție.

Sursă: Graph Theory for Machine Learning — original

Navigare: înapoi: 01.20 — Transformata Fourier · Faza 1 — Fundamente matematice · Catalog complet · în continuare: 01.22 — Procese stocastice.