Teoria dos Grafos

Por que a teoria dos grafos importa em IA

A teoria dos grafos (graph theory) estuda grafos (graphs): objetos matemáticos para representar entidades (entities) e relações (relationships). Em IA (AI) e aprendizado de máquina (machine learning), grafos aparecem em toda parte:

• Redes (networks): redes sociais, redes de citações, redes de comunicação, anéis de fraude, redes de interação biológica.
• Grafos de conhecimento (knowledge graphs): fatos estruturados como (Paris, é-capital-de, França) usados para busca, recomendação e raciocínio.
• Passagem de mensagens (message passing): o padrão central de computação por trás de muitos algoritmos de inferência probabilística (probabilistic inference) (por exemplo, propagação de crenças (belief propagation)) e das modernas Redes Neurais de Grafos (Graph Neural Networks), em que informações são trocadas iterativamente ao longo das arestas.

Grafos fornecem uma linguagem para estrutura: eles descrevem quais partes de um problema podem influenciar diretamente umas às outras e viabilizam algoritmos que exploram esparsidade (sparsity) e localidade (locality).

Definições centrais e notação

Um grafo é tipicamente escrito como:

[ G = (V, E) ]

• (V): conjunto de vértices (vertices) (ou nós (nodes))
• (E): conjunto de arestas (edges) conectando vértices

Grafos direcionados vs. não direcionados

• Grafo não direcionado (undirected graph): arestas não têm orientação, ( {u,v} \in E ). Útil para relações simétricas como “está conectado a”.
• Grafo direcionado (directed graph) (dígrafo (digraph)): arestas têm direção, ( (u,v) \in E ). Útil para relações assimétricas como “segue”, “cita” ou “depende de”.

Grafos ponderados

Arestas podem carregar pesos (w(u,v)), como distância, custo, capacidade ou força de interação. A escolha do peso importa: muitos algoritmos assumem pesos não negativos (por exemplo, o caminho mínimo de Dijkstra).

Classes especiais comuns de grafos

• Árvore (tree): grafo não direcionado, conexo e acíclico. Árvores modelam hierarquias e permitem programação dinâmica eficiente.
• DAG (grafo acíclico direcionado (directed acyclic graph)): grafo direcionado sem ciclos direcionados. DAGs aparecem em grafos de computação, grafos causais e redes bayesianas.
• Grafo bipartido (bipartite graph): nós são divididos em dois conjuntos (U) e (W), e as arestas só vão de um conjunto ao outro. Usado em recomendação (usuários–itens) e problemas de emparelhamento.
• Multigrafo (multigraph): podem existir múltiplas arestas entre um par de nós (comum em transporte/logística).
• Grafo heterogêneo (heterogeneous graph): múltiplos tipos de nós e/ou arestas (típico em grafos de conhecimento).

Estrutura de grafos: graus, caminhos, conectividade

Grau

• Não direcionado: o grau do nó (v) é ( \deg(v) ), o número de arestas incidentes.
• Direcionado: grau de entrada (in-degree) ( \deg^-(v) ), grau de saída (out-degree) ( \deg^+(v) ).

Graus resumem conectividade local e frequentemente são usados como atributos (features) de base em aprendizado de máquina em grafos (graph ML).

Caminhadas, caminhos, ciclos

• Caminhada (walk): sequência de nós em que nós consecutivos compartilham uma aresta (nós/arestas podem se repetir).
• Caminho (path): caminhada sem nós repetidos (em definições simples).
• Ciclo (cycle): caminho que começa e termina no mesmo nó.

Ciclos importam em inferência: a passagem de mensagens é exata em árvores, mas se torna aproximada em grafos com ciclos.

Componentes conexas e alcançabilidade

• Um grafo não direcionado é conexo (connected) se existe um caminho entre todo par de nós.
• Em grafos direcionados, falamos em componentes fortemente conexas (strongly connected components, SCCs): todo nó é alcançável a partir de qualquer outro seguindo as direções.

Alcançabilidade sustenta análise de dependências, influência causal e planejamento.

Representando grafos na computação

Sistemas de IA precisam de estruturas de dados concretas e representações algébricas lineares.

Lista de adjacência (adjacency list) (esparsa, escalável)

Para cada nó, armazene seus vizinhos. Essa é a representação padrão para grandes grafos esparsos (comuns em redes reais e grafos de conhecimento).

Matriz de adjacência (adjacency matrix)

Uma matriz (n \times n) (A) onde:

• Não direcionado: (A_{ij} = 1) se a aresta (i!!-!!j) existe
• Ponderado: (A_{ij} = w(i,j))
• Direcionado: (A_{ij}) representa a aresta (i \to j)

Matrizes de adjacência conectam teoria dos grafos à Álgebra Linear (Linear Algebra): muitas operações em grafos podem ser escritas como operações de matriz (útil para GPUs), mas matrizes densas são grandes demais para grafos grandes.

Matriz de incidência (incidence matrix)

Uma matriz (n \times m) descrevendo quais nós tocam quais arestas, útil em formulações de fluxo e algumas construções espectrais.

Algoritmos fundamentais e por que a IA se importa

Algoritmos de grafos frequentemente viram sub-rotinas dentro de pipelines de aprendizado de máquina (engenharia de atributos (feature engineering), restrições (constraints), raciocínio (reasoning) e avaliação (evaluation)).

Percorrimento (traversal): BFS e DFS

• BFS (busca em largura (breadth-first search)): explora por distância em grafos não ponderados; encontra o comprimento do caminho mínimo em contagem de arestas.
• DFS (busca em profundidade (depth-first search)): explora em profundidade; útil para detecção de ciclos e ordenação topológica.

Casos de uso:

• Extração de vizinhança para treinar subgrafos (comum em minilotes (minibatching) de GNN).
• Verificações de conectividade em limpeza de dados e detecção de anomalias.

Caminhos mínimos (shortest paths)

• Algoritmo de Dijkstra (Dijkstra’s algorithm): caminhos mínimos com pesos de aresta não negativos.
• Bellman–Ford: lida com pesos negativos (mais lento).
• Floyd–Warshall: caminhos mínimos entre todos os pares para grafos densos e pequenos.

Casos de uso:

• Planejamento de rotas e robótica.
• Computar distâncias em grafos como atributos (por exemplo, proximidade em um grafo de conhecimento).
• Métricas de avaliação para taxonomias hierárquicas (distância entre conceitos).

Árvore geradora mínima (minimum spanning tree, MST)

Dado um grafo não direcionado ponderado, encontre um conjunto de arestas de custo mínimo que conecte todos os nós (Kruskal/Prim).

Casos de uso:

• Construir “espinhas dorsais” de redes.
• Aproximações de clustering (single-linkage se relaciona a MST).
• Heurísticas eficientes de aprendizado de estrutura.

Ordenação topológica (topological sorting) (DAGs)

Ordena nós de modo que arestas apontem para frente. Crucial para:

• Agendamento de computações em pipelines de aprendizado de máquina.
• Raciocínio sobre grafos de dependência.
• Algumas formas de modelagem causal (quando representadas como DAGs).

Fluxo e corte (flow and cut)

• Fluxo máximo / corte mínimo (max flow / min cut): encontra o fluxo máximo viável através de uma rede com capacidades; equivalente ao corte mínimo separando fonte e sorvedouro.

Casos de uso:

• Segmentação de imagens (cortes em grafos (graph cuts)).
• Alocação de recursos e emparelhamento.
• Restrições de robustez e influência em redes.

Teoria espectral dos grafos (spectral graph theory): álgebra linear encontra estrutura

Métodos espectrais analisam grafos por meio de autovalores/autovetores de matrizes como o Laplaciano do grafo (graph Laplacian):

• Matriz de grau (D): diagonal com (D_{ii} = \deg(i))
• Laplaciano não normalizado: (L = D - A)
• Laplaciano normalizado: (L_{\text{sym}} = I - D^{-1/2} A D^{-1/2})

Isso se conecta diretamente à Álgebra Linear e a objetivos de otimização.

Por que o Laplaciano importa

• Suavidade em grafos (smoothness on graphs): para um sinal (x \in \mathbb{R}^n) sobre nós, [ x^\top L x = \frac{1}{2} \sum_{(i,j)\in E} A_{ij} (x_i - x_j)^2 ] Isso penaliza nós vizinhos terem valores muito diferentes — uma suposição por trás de muitos métodos semissupervisionados (semi-supervised) e de regularização (regularization).

• Agrupamento espectral (spectral clustering): autovetores de (L) produzem incorporações onde um clustering simples (por exemplo, k-means) separa comunidades. Essa é uma ideia clássica de “grafo-como-geometria”.

Caminhadas aleatórias (random walks) e PageRank

Uma caminhada aleatória se move de um nó para um vizinho com probabilidade proporcional ao peso da aresta. Isso é expresso naturalmente com cadeias de Markov (Markov chains), conectando-se a Probabilidade e Estatística (Probability & Statistics).

• PageRank é essencialmente uma caminhada aleatória com reinícios; ele ranqueia nós pela probabilidade estacionária de visita.
• Em IA, caminhadas aleatórias são usadas para:
  • Ranqueamento de nós e estimativa de influência
  • Amostrar vizinhanças para treinamento escalável
  • Definir medidas de proximidade usadas por métodos de incorporação

Modelos de grafos aleatórios (random graph models) (aproximações úteis)

Redes reais têm padrões — graus com cauda pesada, comunidades, pequenos diâmetros — que suposições i.i.d. (independentes e identicamente distribuídas (independent and identically distributed, IID)) simples não capturam.

Modelos comuns:

• Erdős–Rényi (ER): arestas aparecem independentemente com probabilidade (p). Bom modelo nulo; ajuste ruim para muitos grafos sociais.
• Barabási–Albert (ligação preferencial (preferential attachment)): produz distribuições de grau com cauda pesada (hubs).
• Watts–Strogatz: captura comportamento de “mundo pequeno” (alta clusterização, caminhos curtos).

Esses modelos ajudam a raciocinar sobre escalabilidade, robustez e comportamento esperado de algoritmos em redes.

Grafos de conhecimento: grafos como significado estruturado

Um grafo de conhecimento (knowledge graph, KG) representa fatos como arestas (frequentemente tipadas e direcionadas). Uma forma comum é por triplas:

[ (\text{entidade de cabeça}, \text{relação}, \text{entidade de cauda}) ]

Exemplo:

• (Marie Curie, ganhou, Prêmio Nobel)
• (Prêmio Nobel, categoria, Física)

Grafos de conhecimento geralmente são heterogêneos: muitos tipos de relação, às vezes múltiplos tipos de nó.

O que fazer com grafos de conhecimento

• Resolução de entidades (entity resolution): decidir se dois nós se referem à mesma entidade do mundo real.
• Predição de links (link prediction): prever arestas ausentes (por exemplo, “quais medicamentos tratam quais doenças?”).
• Raciocínio (reasoning): inferir novos fatos a partir dos existentes (regras lógicas, caminhos, restrições).
• Recuperação e QA (retrieval and QA): consulta estruturada mais re-ranqueamento com aprendizado de máquina.

Incorporações de grafos de conhecimento (knowledge graph embeddings)

Métodos de incorporação de grafo de conhecimento mapeiam entidades/relações para vetores para pontuação eficiente. Por exemplo, TransE pontua uma tripla por:

[ \text{score}(h,r,t) = -\lVert \mathbf{e}_h + \mathbf{e}_r - \mathbf{e}_t \rVert ]

Isso conecta estrutura de grafos com aprendizado de representações (representation learning) (ver Redes Neurais (Neural Networks)) e otimização (ver Otimização (Optimization)).

Passagem de mensagens: o padrão computacional unificador

“Passagem de mensagens” significa atualizar o estado de um nó usando informação de seus vizinhos. Essa ideia aparece tanto em inferência probabilística quanto em aprendizado profundo.

Passagem de mensagens em modelos gráficos probabilísticos (probabilistic graphical models)

Em modelos com estrutura de árvore, propagação de crenças (belief propagation) computa marginais exatas enviando mensagens ao longo das arestas. Em grafos com ciclos, isso vira propagação de crenças com ciclos (loopy belief propagation) (aproximada, mas frequentemente útil).

Isso se conecta a:

• Estrutura de independência condicional (conditional independence) (o grafo codifica a fatoração)
• Inferência e incerteza (ver Probabilidade e Estatística)
• Alternativas de amostragem como Monte Carlo via Cadeias de Markov (Markov Chain Monte Carlo, MCMC) quando a inferência exata é difícil

Passagem de mensagens em Redes Neurais de Grafos (GNNs)

Uma camada comum de GNN se parece com:

[ \mathbf{h}_v^{(k+1)} = \sigma\Big( W^{(k)} \cdot \text{AGG}_{;u \in \mathcal{N}(v)} \phi(\mathbf{h}_v^{(k)}, \mathbf{h}u^{(k)}, \mathbf{e}{uv}) \Big) ]

• (\mathbf{h}_v^{(k)}): incorporação do nó (v) na camada (k)
• (\mathcal{N}(v)): vizinhos de (v)
• (\text{AGG}): agregação (soma/média/máximo/atenção (attention))
• (\phi): função de mensagem (frequentemente linear + não linearidade)
• (\sigma): função de ativação

Ideia-chave: após (K) camadas, um nó integrou informações de sua vizinhança a (K) saltos (hops).

Considerações práticas:

• Super-suavização (over-smoothing): muitas camadas podem tornar incorporações de nós indistinguíveis.
• Supercompressão (over-squashing): informação demais comprimida através de cortes estreitos no grafo.
• Heterofilia (heterophily): vizinhos podem ter rótulos diferentes (comum em alguns grafos reais), desafiando suposições de “suavidade”.

O treinamento de GNNs usa Retropropagação (Backpropagation) sobre essas computações de passagem de mensagens.

Exemplos práticos

Exemplo 1: Análise simples de rede com NetworkX (Python)

import networkx as nx

# Undirected social network
G = nx.Graph()
G.add_edges_from([
    ("Alice", "Bob"),
    ("Bob", "Chen"),
    ("Alice", "Dina"),
    ("Dina", "Chen"),
    ("Chen", "Eli"),
])

# Shortest path (fewest hops)
print(nx.shortest_path(G, "Alice", "Eli"))  # ['Alice', 'Bob', 'Chen', 'Eli']

# Centrality: who is most "between" others?
bet = nx.betweenness_centrality(G)
print(sorted(bet.items(), key=lambda x: -x[1]))

Como isso se mapeia para tarefas de IA:

• caminhos mínimos aproximam “distância de relacionamento” em um grafo de conhecimento
• atributos de centralidade podem ajudar em detecção de anomalias ou recomendação

Exemplo 2: Um passo de passagem de mensagens (pseudocódigo conceitual)

for each node v:
    messages = []
    for u in neighbors(v):
        messages.append( MLP(concat(h_v, h_u, e_uv)) )
    h_v = LayerNorm( h_v + sum(messages) )

Isso é o núcleo de muitas arquiteturas de GNN: agregação local + atualização.

Exemplo 3: Predição de links em grafo de conhecimento (alto nível)

Dadas triplas observadas (E), treine incorporações para que triplas verdadeiras tenham pontuação maior do que triplas corrompidas:

• Positiva: (Paris, capital_de, França)
• Negativa (cauda corrompida): (Paris, capital_de, Alemanha)

A perda (loss) frequentemente é baseada em margem (margin-based) ou logística (logistic) com amostragem negativa (negative sampling) — conceitualmente semelhante ao treinamento de word2vec, mas direcionada por arestas do grafo.

Grafos como restrições e grafos de computação em sistemas de aprendizado de máquina

Grafos não são apenas “dados”; eles também representam computação e restrições:

• Frameworks de aprendizado profundo constroem grafos de computação (computation graphs) para diferenciação automática (automatic differentiation) (ver Cálculo (Calculus)).
• Predição estruturada (structured prediction) usa grafos para codificar restrições de compatibilidade (por exemplo, campos aleatórios condicionais (Conditional Random Fields, CRFs) em PLN (NLP) e visão computacional).
• Modelagem causal (causal modeling) frequentemente assume uma estrutura de DAG para relações de causa → efeito.

A teoria dos grafos fornece uma base compartilhada para essas perspectivas.

Escalando para grafos do mundo real

Grafos de IA no mundo real podem ter milhões a bilhões de arestas. A engenharia prática depende de:

• Esparsidade: armazenar arestas de forma compacta, fazer streaming de vizinhanças.
• Amostragem: amostragem de vizinhos, amostragem de subgrafos, caminhadas aleatórias (conecta-se a Métodos de Monte Carlo (Monte Carlo Methods)).
• Particionamento: distribuir grafos entre máquinas; reduzir comunicação.
• Aproximação: esboço (sketching), vizinhos mais próximos aproximados (approximate nearest neighbors) em incorporações aprendidas, inferência aproximada.

A complexidade algorítmica frequentemente domina: um método “elegante” que exige matrizes densas pode ser inviável em escala.

Escolhas comuns de modelagem e armadilhas

• Semântica das arestas (edge semantics): “conectado” pode significar amizade, co-visualização, influência causal ou similaridade — algoritmos podem assumir propriedades (simetria, transitividade) que não valem.
• Direcionalidade (directionality): impor um modelo não direcionado a um processo direcionado (citações, follows) pode apagar estrutura importante.
• Dinâmica temporal (temporal dynamics): muitos grafos evoluem; instantâneos estáticos podem enganar (grafos temporais exigem mecanismos adicionais).
• Vazamento na avaliação (evaluation leakage): em predição de links, divisões aleatórias de arestas podem vazar informação por meio de nós compartilhados; divisões mais cuidadosas (baseadas em tempo, indutivas (inductive)) podem ser necessárias.

Como isso se conecta ao restante do Guia de Matemática (Math Primer)

• Matrizes de grafos e métodos espectrais dependem fortemente de Álgebra Linear.
• Caminhadas aleatórias, PageRank e modelos gráficos conectam-se a Probabilidade e Estatística.
• Muitos objetivos (cortes, incorporações, regularizadores) são resolvidos via Otimização.
• Inferência em grafos se relaciona a amostragem e incerteza via Métodos de Monte Carlo e Monte Carlo via Cadeias de Markov (MCMC).
• Tomada de decisão baseada em grafos (por exemplo, maximização de influência ou intervenções em redes) pode ser formulada com utilidades e perdas de Teoria Bayesiana da Decisão (Bayesian Decision Theory).

Resumo

A teoria dos grafos fornece a linguagem central para representar estrutura relacional em IA: de redes e grafos de conhecimento às computações de passagem de mensagens que alimentam inferência probabilística e redes neurais de grafos. Os mesmos conceitos fundamentais — caminhos, conectividade, fluxos, Laplacianos, caminhadas aleatórias — reaparecem em diferentes aplicações, oferecendo ferramentas mentais reutilizáveis tanto para entendimento teórico quanto para projeto prático de sistemas.

---