Phase 01 - Lesson 21

Teoria dos Grafos para Aprendizado de Máquina

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Grafos são a estrutura de dados dos relacionamentos. Se seus dados tem conexões, você precisa de teoria dos grafos.

Tipo: Build Linguagem: Python Pré-requisitos: Fase 1, Lições 01-03 (álgebra linear, matrizes) Tempo: ~90 minutos

Objetivos de Aprendizagem

• Construir uma classe de grafo com representações em matriz/lista de adjacência e implementar travessias BFS e DFS
• Calcular o Laplaciano do grafo e usar seus autovalores para detectar componentes conexas e agrupar nos
• Implementar uma rodada de passagem de mensagens no estilo GNN como uma multiplicação por matriz de adjacência normalizada
• Aplicar agrupamento espectral para particionar um grafo usando o vetor de Fiedler

O Problema

Redes sociais, moléculas, bases de conhecimento, redes de citação, mapas de estradas -- todos são grafos. O ML tradicional trata os dados como tabelas planas. Cada linha e independente. Cada característica e uma coluna. Mas quando a estrutura das conexões importa, as tabelas falham.

Considere uma rede social. Você quer prever qual produto um usuário vai comprar. O histórico de compras dele importa. Mas o histórico de compras dos amigos dele importa mais. As conexões carregam sinal.

Ou considere uma molécula. Você quer prever se ela se liga a uma proteína. Os átomos importam, mas o que realmente importa e como os átomos estão ligados uns aos outros. A estrutura e o dado.

Redes Neurais de Grafos (GNNs) são a área de crescimento mais rápido em deep learning. Elas impulsionam a descoberta de fármacos, a recomendação social, a detecção de fraude e o raciocínio sobre grafos de conhecimento. Toda GNN se baseia na mesma fundação: teoria dos grafos básica.

Você precisa de quatro coisas:

1. Uma forma de representar grafos como matrizes (para que você possa multiplica-los)
2. Algoritmos de travessia para explorar a estrutura do grafo
3. O Laplaciano -- a matriz mais importante na teoria espectral de grafos
4. Passagem de mensagens -- a operação que faz as GNNs funcionarem

O Conceito

Grafos: Nos e Arestas

Um grafo G = (V, E) consiste em vértices (nos) V e arestas E. Cada aresta conecta dois nos.

Direcionado vs não direcionado. Em um grafo não direcionado, a aresta (u, v) significa que u conecta a v E v conecta a u. Em um grafo direcionado (digrafo), a aresta (u, v) significa que u aponta para v, mas não necessariamente o contrario.

Ponderado vs não ponderado. Em um grafo não ponderado, as arestas existem ou não. Em um grafo ponderado, cada aresta tem um peso numérico -- uma distância, um custo, uma força.

A Matriz de Adjacência

A matriz de adjacência A e a representação central. Para um grafo com n nos:

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

Para grafos não direcionados, A e simétrica: A[i][j] = A[j][i]. Para grafos ponderados, A[i][j] = peso da aresta (i, j).

Exemplo -- um triângulo:

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

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

A matriz de adjacência e a entrada de toda GNN. Operações matriciais sobre A correspondem a operações sobre o grafo.

Grau

O grau de um no e o número de arestas conectadas a ele. Para grafos direcionados, você tem grau de entrada (arestas chegando) e grau de saída (arestas saindo).

A matriz de grau D e diagonal:

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

Para o exemplo do triângulo: D = diag(2, 2, 2) porque cada no conecta a outros dois.

O grau lhe diz sobre a importancia do no. Grau alto = no hub. A distribuição de graus de uma rede revela sua estrutura. Redes sociais seguem leis de potência (poucos hubs, muitos nos folha). Grafos aleatórios tem graus com distribuição de Poisson.

BFS e DFS

Os dois algoritmos fundamentais de travessia de grafos. Você precisa de ambos.

Busca em Largura (BFS): Explore todos os vizinhos primeiro, depois os vizinhos dos vizinhos. Usa uma fila (FIFO).

BFS 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)

A BFS encontra caminhos mais curtos em grafos não ponderados. A distância do início até qualquer no e igual ao nível da BFS no qual aquele no e descoberto pela primeira vez. E por isso que a BFS e usada para distâncias em número de saltos (hop-count) em redes sociais.

Busca em Profundidade (DFS): Va o mais fundo possível antes de retroceder. Usa uma pilha (LIFO) ou recursão.

DFS 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)

A DFS e útil para:

• Encontrar componentes conexas (rode DFS a partir de nos não visitados)
• Detecção de ciclos (arestas de retorno na arvore DFS)
• Ordenação topológica (ordem reversa de finalização da DFS)

O Laplaciano do Grafo

L = D - A. A matriz mais importante na teoria espectral de grafos.

Para o triângulo:

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]]

O Laplaciano tem propriedades notáveis:

1. L e positiva semidefinida. Todos os autovalores são >= 0.

2. O número de autovalores zero e igual ao número de componentes conexas. Um grafo conexo tem exatamente um autovalor zero. Um grafo com 3 componentes desconexas tem três autovalores zero.

3. O menor autovalor não nulo (valor de Fiedler) mede a conectividade. Um valor de Fiedler grande significa que o grafo e bem conectado. Um valor de Fiedler pequeno significa que o grafo tem um ponto fraco -- um gargalo.

4. O autovetor do valor de Fiedler (vetor de Fiedler) revela a melhor divisão. Nos com valores positivos vão para um grupo, nos com valores negativos vão para o outro. Isso e o agrupamento espectral.

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

Propriedades Espectrais

Os autovalores da matriz de adjacência e do Laplaciano revelam propriedades estruturais sem nenhuma travessia.

O agrupamento espectral funciona assim:

1. Calcule o Laplaciano L
2. Encontre os k menores autovetores de L (pule o primeiro, que e todo composto de uns para grafos conexos)
3. Use esses autovetores como novas coordenadas para cada no
4. Rode k-means sobre essas coordenadas

Por que isso funciona? Os autovetores de L codificam as funções "mais suaves" sobre o grafo. Nos que são bem conectados recebem valores de autovetor similares. Nos separados por um gargalo recebem valores diferentes. Os autovetores separam naturalmente os agrupamentos.

Conexão com passeio aleatório. O Laplaciano normalizado se relaciona com passeios aleatórios sobre o grafo. A distribuição estacionária de um passeio aleatório e proporcional ao grau do no. O tempo de mistura (quão rápido o passeio converge) depende do gap espectral.

Passagem de Mensagens

A operação central das Redes Neurais de Grafos. Cada no coleta mensagens de seus vizinhos, agrega-as e atualiza seu próprio estado.

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

Na forma mais simples, AGGREGATE = média, e UPDATE = transformação linear + ativação:

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

Isso e multiplicação de matrizes disfarçada. Se H e a matriz de todas as características dos nos e A e a matriz de adjacência:

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

onde A_norm e a matriz de adjacência normalizada (cada linha soma 1).

Uma rodada de passagem de mensagens permite que cada no "veja" seus vizinhos imediatos. Duas rodadas permitem que ele veja os vizinhos dos vizinhos. K rodadas dão a cada no informação de sua vizinhança de K saltos.

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

Conceitos e Aplicações em ML

Build It

Passo 1: Classe de grafo do 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()

A lista de adjacência (self.adj) armazena vizinhos de forma eficiente. A conversão para matriz de adjacência usa numpy porque todas as operações espectrais precisam dele.

Passo 2: BFS e 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

A BFS usa um deque (fila de duas pontas) para popleft em O(1). A DFS usa uma lista como pilha. Ambas visitam cada no exatamente uma vez -- tempo O(V + E).

Passo 3: Componentes conexas e autovalores do Laplaciano

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

eigvalsh e para matrizes simétricas -- o Laplaciano e sempre simétrico para grafos não direcionados. Ele retorna autovalores em ordem crescente. Conte os zeros para encontrar o número de componentes conexas.

Passo 4: Agrupamento espectral

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

Para k=2, o sinal do vetor de Fiedler divide o grafo em dois agrupamentos. Para k>2, você rodaria k-means sobre os primeiros k autovetores (excluindo o autovetor trivial composto de uns).

Passo 5: Passagem de mensagens

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

Esta e uma rodada de passagem de mensagens de GNN. As novas características de cada no são a média ponderada das características de seus vizinhos, transformada pela matriz de pesos. Empilhe várias rodadas para propagar informação mais longe.

Use It

Com networkx e numpy, as mesmas operações são de uma linha:

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

O networkx lida com grafos de qualquer tamanho com backends C otimizados. Use-o em produção. Use sua implementação do zero para entender o que ele faz.

Análise espectral com 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}")

O vetor de Fiedler faz o trabalho pesado. Entradas positivas em um agrupamento, negativas no outro. Nenhuma otimização iterativa necessária -- apenas uma autodecomposição.

Ship It

Esta lição produz:

• outputs/skill-graph-analysis.md -- uma referência de skill para analisar dados estruturados em grafo

Conexões

As GNNs merecem menção especial. A operação de convolução de grafo na GCN (Kipf & Welling, 2017) usa a matriz de adjacência com laços próprios (self-loops) adicionados, A_hat = A + I:

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

onde A_hat = A + I (adjacência mais laços próprios) e D_hat e a matriz de grau de A_hat. Os laços próprios garantem que cada no inclua suas próprias características durante a agregação. Isso e exatamente passagem de mensagens com normalização simétrica. D_hat^(-1/2) * A_hat * D_hat^(-1/2) e a matriz de adjacência normalizada. O Laplaciano aparece porque essa normalização esta relacionada a L_sym = I - D^(-1/2) * A * D^(-1/2). Entender o Laplaciano significa entender por que as GCNs funcionam.

Exercícios

1. Implemente o PageRank do zero. Comece com pontuacoes uniformes. A cada passo: score(v) = (1-d)/n + d * sum(score(u)/out_degree(u)) para todo u que aponta para v. Use d=0.85. Rode até convergir (mudanca < 1e-6). Teste em um pequeno grafo da web.

2. Encontre comunidades usando agrupamento espectral. Crie um grafo com dois agrupamentos claramente separados (por exemplo, dois cliques conectados por uma única aresta). Rode o agrupamento espectral e verifique se ele encontra a divisão correta. O que acontece a medida que você adiciona mais arestas entre agrupamentos?

3. Implemente o algoritmo de Dijkstra para caminhos mais curtos em grafos ponderados. Compare os resultados com a BFS no mesmo grafo com pesos uniformes.

4. Construa uma rede de passagem de mensagens de 2 camadas. Aplique passagem de mensagens duas vezes com matrizes de pesos diferentes. Mostre que após 2 rodadas, cada no tem informação de sua vizinhança de 2 saltos.

5. Análise um grafo do mundo real. Use o grafo do Karate Club (34 nos, 78 arestas). Calcule a distribuição de graus, os autovalores do Laplaciano e o agrupamento espectral. Compare o resultado do agrupamento espectral com a divisão real conhecida (ground truth).

Termos-Chave

Leitura Adicional

• Kipf & Welling (2017) -- "Semi-Supervised Classification with Graph Convolutional Networks." O artigo que lancou as GNNs modernas. Mostra que as convoluções espectrais de grafos se simplificam para passagem de mensagens.
• Spielman (2012) -- notas de aula "Spectral Graph Theory". A introdução definitiva a Laplacianos, gaps espectrais e particionamento de grafos.
• Hamilton (2020) -- "Graph Representation Learning." Livro cobrindo GNNs desde os fundamentos até as aplicações.
• Bronstein et al. (2021) -- "Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges." O artigo do framework unificador.
• Velickovic et al. (2018) -- "Graph Attention Networks." Estende a passagem de mensagens com mecanismos de atenção.