GrafoLab

Resumo — Hoje, ferramentas como GraphSAGE e GAT são padrão na indústria. Mas de onde elas vieram? A fundação de todo o campo de GNNs foi estabelecida em 2009, em um artigo seminal de Franco Scarselli e colegas. Eles propuseram a primeira arquitetura formal capaz de aprender em grafos arbitrários, introduzindo conceitos de “estado” e “convergência” que precederam o moderno Message Passing. Este post revisita o modelo original de Scarselli para entender as raízes matemáticas das Redes Neurais de Grafos.

---

1. O Mundo Antes das GNNs (O Problema Euclidiano)

Antes de 2009, o Deep Learning já brilhava, mas vivia em um mundo restrito: o mundo dos dados euclidianos.

• Imagens são grades fixas (pixels).
• Texto e áudio são sequências lineares.

Redes Convolucionais (CNNs) e Recorrentes (RNNs) funcionavam perfeitamente nessas estruturas rígidas. Mas o mundo real é bagunçado. Redes sociais, moléculas, transações financeiras e sistemas de recomendação não seguem uma grade; eles são grafos.

Até então, para aplicar ML em grafos, dependíamos de engenharia de features manual ou algoritmos de kernel limitados. Faltava um modelo que pudesse aprender diretamente da estrutura irregular do grafo.

2. A Ideia Central: O Modelo de Scarselli

Em 2009, Franco Scarselli e sua equipe publicaram “The Graph Neural Network Model”, propondo uma solução elegante e universal.

A ideia central não era empilhar camadas (como nas GNNs de hoje), mas sim simular um processo de difusão de informação até que o grafo atingisse um equilíbrio.

O modelo define que cada nó possui um Estado Oculto (). Esse estado não é estático; ele é atualizado iterativamente com base nas informações dos seus vizinhos, até convergir para um valor estável.

A equação fundamental proposta por Scarselli é:

Onde:

• : São as features (atributos) do próprio nó.
• : São as features das arestas conectadas a ele.
• : São os estados dos nós vizinhos.
• : É a função de transição local (uma rede neural).

3. Convergência vs. Camadas (A Grande Diferença)

Aqui reside a maior diferença entre o “pai das GNNs” e os modelos modernos.

• Scarselli (GNN Recorrente/Recursiva): O modelo roda a função repetidamente no grafo. A informação viaja dos vizinhos, para os vizinhos dos vizinhos, e assim por diante. O algoritmo continua atualizando os estados até que eles parem de mudar (atinjam um ponto fixo ou convergência). Só então a classificação é feita.
• Modernas (GCN, GraphSAGE): São baseadas em empilhamento de camadas. Se você tem 2 camadas, a informação viaja exatamente 2 saltos. Não há loop até a convergência infinita.

O modelo de Scarselli era computacionalmente caro (exigia muitas iterações para convergir e usava uma técnica complexa chamada Alman-BPTT para treinar), mas provou matematicamente que era possível aprender representações estáveis em qualquer topologia de grafo.

4. O Legado: O “Avô” do Message Passing

Embora a implementação exata de Scarselli raramente seja usada hoje (devido ao custo computacional), os conceitos que ele introduziu são a base de tudo o que usamos:

1. Independência de Topologia: O modelo funciona em qualquer grafo, não importa o tamanho ou a forma.
2. Permutação Invariante: Não importa a “ordem” em que você lê os vizinhos; o resultado é o mesmo.
3. Message Passing (Troca de Mensagens): A ideia de que “meu estado depende do estado dos meus vizinhos” é a essência do paradigma MPNN (Message Passing Neural Network) que domina a área hoje.

Podemos traçar uma linha direta de evolução:

• 2009 (Scarselli): GNN original (recursiva).
• 2015 (Gated GNN): Introduziu GRUs para melhorar a atualização dos estados.
• 2016 (GCN): Simplificou a recursão para uma convolução eficiente em camadas fixas.
• 2017 (GraphSAGE): Adicionou amostragem para escalar para grafos gigantes.

Conclusão

O paper de Scarselli (2009) é o “marco zero” das GNNs. Ele nos ensinou que grafos não precisam ser transformados ou achatados para serem processados por redes neurais; eles podem ser tratados em sua forma nativa. Entender esse modelo original nos dá a clareza de que, no fundo, toda GNN moderna é uma forma otimizada de resolver o problema que Scarselli formulou: como propagar informação através de conexões para entender quem é quem na rede.

---

Referências

• Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009). The Graph Neural Network Model. IEEE Transactions on Neural Networks.
• Wu, Z. et al. (2020). A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems.
• Bronstein, M. M. et al. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.13478.

Sobre o autor

Rener Menezes
Cofundador & CTO — FitBank

Rener Menezes é cofundador e CTO do FitBank, fintech brasileira de Banking-as-a-Service. Com mais de 25 anos de experiência projetando sistemas financeiros em larga escala, é bacharel em Sistemas de Informação e mestrando na Unifor, onde pesquisa Redes Neurais de Grafos e aprendizado por reforço para detecção de fraude. Interesses: sistemas distribuídos, infraestrutura de pagamentos e graph ML.

Links: LinkedIn · ORCID · contato@grafolab.ia.br