GrafoLab

Laboratório dedicado à pesquisa e divulgação científica sobre grafos e Redes Neurais de Grafos (GNNs), explorando aplicações em inteligência artificial, ciência de dados e aprendizado de máquina.

posts recentes

mais visitados

  • Who To Follow: O Grafo Social do Twitter (X) e o Poder do Personalized PageRank

    Visualização conceitual do Personalized PageRank no grafo social do Twitter. Um nó central (o usuário) em azul brilhante emite 'caminhadas aleatórias' (trilhas de luz) que exploram a rede. Arcos de luz retornam ao centro, simbolizando o 'teleporte' do PPR e iluminando os nós relevantes.

    Resumo — O recurso “Quem Seguir” (Who To Follow – WTF) do Twitter/X é um dos sistemas de recomendação de maior sucesso e influência da web. Ele resolve um problema clássico: como sugerir contas relevantes em um grafo social gigantesco e dinâmico? A fundação dessa solução não é um modelo de deep learning complexo, mas sim uma aplicação elegante de um algoritmo clássico de grafos: o Personalized PageRank (PPR). Este post explica a intuição, a modelagem e a engenharia por trás dessa ideia.

    1. O Problema: Previsão de Arestas em um Grafo Dirigido

    Quando você pensa em “recomendação”, talvez imagine sistemas como o da Netflix (usuários e itens). O desafio do Twitter é diferente. O Twitter é um grafo social dirigido:

    • Nós: São as contas de usuário (você, seus amigos, empresas, celebridades).
    • Arestas Dirigidas: São as relações de “seguir”. Uma aresta u \rightarrow v significa que o usuário u segue o usuário v.

    O problema do “Quem Seguir” é, essencialmente, um problema de previsão de arestas (link prediction). O sistema precisa adivinhar: “Quais são as arestas u \rightarrow ? que o usuário u tem alta probabilidade de criar no futuro?”

    Uma abordagem ingênua, como sugerir as contas mais populares (com mais seguidores), falharia. Você não quer ver apenas celebridades e políticos; você quer encontrar pessoas relevantes para o seu círculo de interesses e conexões.

    2. A Solução: O “Navegante Aleatório Pessoal”

    A solução genial do Twitter foi adaptar o famoso algoritmo PageRank do Google. Lembre-se do PageRank clássico: ele simula um “navegante aleatório” que pula de página em página seguindo links, e a importância de uma página é a probabilidade desse navegante estar nela.

    O Twitter adaptou isso para o Personalized PageRank (PPR).

    Imagine um “navegante aleatório” que tem um “favorito”: você. O passeio dele funciona assim:

    1. Ele começa na sua conta.
    2. Ele dá um passo, seguindo aleatoriamente uma das pessoas que você segue (ex: ele “visita” a conta do Rener).
    3. Da conta do Rener, ele dá outro passo, seguindo alguém que o Rener segue (ex: ele “visita” a conta da Ana).
    4. A cada passo, ele tem uma escolha:
      • Com probabilidade \alpha (ex: 85%), ele continua “navegando” pela rede, seguindo quem seus amigos seguem.
      • Com probabilidade 1-\alpha (ex: 15%), ele se “teleporta” de volta para o ponto de partida: a sua conta.

    Após rodar essa simulação por muito tempo, as contas onde esse “navegante pessoal” passou mais tempo são, por definição, as mais relevantes e “próximas” de você. O PPR é uma medida de proximidade e importância relativa ao seu nó no grafo, não uma medida de popularidade global.

    Em termos técnicos, a equação do PageRank é sutilmente alterada. A equação clássica é:

    \displaystyle r = \alpha P^{\top} r + (1-\alpha)v

    No PageRank clássico do Google, o vetor de teleporte v era uniforme (o navegante podia reiniciar em qualquer página da web). No Personalized PageRank do Twitter, o vetor v é personalizado: ele tem 100% de sua massa concentrada no seu nó de usuário, e 0 em todos os outros.

    Traduzindo a matemática: O score de uma conta (r) é uma soma da chance dela ser “visitada” por um link (a parte \alpha P^{\top} r) e a chance dela ser o “ponto de reinício” do navegante (a parte (1-\alpha)v). Como o ponto de reinício é sempre você, os scores mais altos ficam com contas que são fáceis de alcançar (em poucos “saltos”) a partir da sua rede de conexões.

    3. Além do PPR: Refinando o Ranking

    O PPR puro é a base, mas o sistema de produção (descrito no famoso paper de 2013) é um ensemble que usa outros sinais para refinar a lista:

    • Fechamento Triádico: A ideia de que “o amigo do meu amigo é meu amigo”. O PPR captura isso muito bem. Se você segue o Rener, e o Rener segue a Ana, a Ana terá um score de PPR alto para você.
    • Reciprocidade: A pessoa sugerida já te segue? Isso é um sinal forte.
    • Popularidade Local: Quão popular é essa conta dentro do seu círculo de interesses, e não globalmente?
    • Recência e Engajamento: A conta é ativa? Você interagiu com tópicos similares aos que ela posta?

    4. O Desafio da Engenharia: Milissegundos

    Calcular o PPR exato para centenas de milhões de usuários em tempo real é computacionalmente impossível. A engenharia por trás do “Quem Seguir” é tão impressionante quanto o algoritmo.

    • Aproximação: O sistema não calcula o PPR exato. Ele usa aproximações rápidas, como simular um número finito de “caminhadas aleatórias” (Random Walks) a partir do seu nó para estimar os scores.
    • Cálculo em Subgrafo: A caminhada aleatória não roda na web inteira, mas em um “subgrafo de interesse” ao seu redor.
    • Cache Quente: Os resultados são pré-calculados e armazenados em sistemas de cache de alta velocidade, para que as sugestões possam ser entregues em milissegundos quando você acessa o site.
    • Atualizações Incrementais: Quando você segue uma nova pessoa, seu “ponto de partida” muda. O sistema detecta isso e dispara o recálculo das suas sugestões de PPR, mantendo a lista atualizada.

    5. Conclusão: A Lição do Twitter (X)

    O caso do “Who To Follow” é uma aula magistral sobre o poder dos algoritmos de grafos “clássicos”. Ele demonstra que, para muitos problemas de recomendação em redes (como link prediction), uma modelagem de grafo inteligente (nós e arestas dirigidas) combinada com o algoritmo certo (Personalized PageRank) pode ser uma solução extremamente poderosa, eficiente e escalável.

    Ele prova que nem todo problema de grafos precisa da solução mais complexa. Às vezes, a solução mais elegante já existe há décadas, esperando a engenharia correta para ser aplicada em escala planetária.

    Referências

    • Gupta, A., Goel, A., Lin, J., Sharma, A., Wang, D., & Zadeh, R. (2013). WTF: The Who to Follow Service at Twitter. Proceedings of the 22nd International Conference on World Wide Web (WWW).
    • Haveliwala, T. H. (2002). Topic-sensitive PageRank. Proceedings of the 11th International Conference on World Wide Web (WWW). (Paper seminal sobre a ideia de PageRank Personalizado).

    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

  • Meta e o Social Graph: A Infraestrutura e os Sinais que Movem o seu Feed

    Visualização conceitual da arquitetura da Meta. À esquerda, um massivo 'social graph' azul (o grafo) sustentado pela infraestrutura 'TAO'. À direita, um núcleo de 'IA' (o ranking DLRM) que é alimentado por feixes de luz vindos do grafo, representando as 'features de grafo'.

    Resumo — O Facebook (agora Meta) não apenas usa um grafo; ele é um grafo. O “Social Graph” é o ativo central que mapeia todas as conexões entre pessoas, páginas, lugares e interesses. O poder do seu feed vem da combinação de duas coisas: uma infraestrutura de grafo de escala planetária (o TAO) e sinais de rede (features de grafo) que alimentam a poderosa IA de recomendação que decide o que você vê.

    1. O “Social Graph” como Ativo Central

    Camada 1: A Intuição

    Quando você abre seu feed, a ordem das postagens não é cronológica nem aleatória. Ela é o resultado de um complexo sistema de IA que tenta prever o que é mais relevante para você. Mas como ele faz isso?

    Ele começa com um mapa. A Meta não construiu apenas um site; ela construiu o mapa digital mais detalhado dos relacionamentos humanos e interesses. Esse mapa é o Social Graph.

    Camada 2: O Conceito Técnico

    Nesse grafo:

    • Nós (Entidades): São você, seus amigos, as páginas que você curte, os grupos dos quais participa, os locais onde fez check-in, os eventos que marcou.
    • Arestas (Relações): São as conexões entre eles. Amigo de, Curtiu, Comentou, Marcou em foto, Compareceu a, Membro de.

    Cada ação que você toma na plataforma é, essencialmente, a criação ou o fortalecimento de uma aresta nesse grafo. Esse grafo com trilhões de arestas não é apenas um “banco de dados”; ele é o produto.

    2. O Desafio de Engenharia: Como Servir um Grafo Planetário?

    Camada 1: A Intuição

    Imagine o desafio de engenharia. Quando você carrega seu feed, o sistema da Meta precisa, em menos de um segundo, consultar: “Quem são os amigos de Rener? O que eles postaram? Quem curtiu esses posts? Rener é próximo de quais desses amigos?”.

    Um banco de dados relacional tradicional (como SQL) falharia miseravelmente nessa tarefa em escala. A operação de “juntar tabelas” (JOINs) para cruzar amigos, com curtidas, com comentários, para 3 bilhões de usuários em tempo real, é computacionalmente proibitiva.

    Camada 2: A Solução de Infraestrutura (TAO)

    A Meta precisou construir sua própria solução. O resultado é o TAO (The Associations and Objects), um data store distribuído globalmente e otimizado para o grafo (Bronson et al., 2013).

    O TAO não é um banco de dados de grafos para consultas analíticas complexas (como “encontre o caminho mais curto entre todos os políticos”). Em vez disso, ele é otimizado para leituras de baixa latência e alta vazão do “grafo de vizinhança”. Ele é projetado para responder perguntas como:

    • “Quais são todas as arestas (ex: curtidas, comentários) de um nó específico (ex: este post)?”
    • “Quais são todos os nós conectados a este nó (ex: todos os amigos desta pessoa)?”

    TAO é a fundação de engenharia que permite que o Social Graph exista e seja lido em tempo real, em escala planetária.

    3. A “Inteligência”: Features de Grafo que Alimentam o Ranking

    Ok, o TAO nos dá acesso rápido aos dados. Mas como a IA de ranking decide que a foto do seu primo é mais importante que o post de um grupo?

    Ela usa features (sinais) que são, em sua maioria, extraídos do grafo. O modelo de ranking de recomendação da Meta, publicamente conhecido como DLRM (Deep Learning Recommendation Model), é um modelo de deep learning que aprende a importância de diferentes sinais (Naumov et al., 2019). A genialidade está no fato de que os sinais mais poderosos que o DLRM utiliza são extraídos do grafo.

    Camada 1: A Intuição das “Pistas”

    O algoritmo de ranking funciona como um detetive, coletando “pistas” (features) para prever a probabilidade de você curtir, comentar ou compartilhar algo. Muitas das pistas mais fortes vêm do grafo:

    • Proximidade na Rede: Você e o autor do post são amigos? (Distância 1 no grafo).
    • Afinidade: Você interage muito com essa pessoa? (Peso da aresta entre vocês).
    • Prova Social: Quantos dos seus amigos também curtiram este post? (Contagem de vizinhos em comum que tocaram no nó do post).
    • Autoridade do Tópico: Este post é de uma página que é uma autoridade (alta centralidade) no tópico “Grafos”, um tópico que você segue?

    Camada 2: A Engenharia de Features

    O trabalho de engenharia de dados na Meta é extrair esses sinais do TAO e de outros sistemas em tempo real e alimentá-los como features no DLRM. O DLRM, então, aprende a ponderar a importância de cada uma dessas features para tomar a decisão final de ranking.

    Portanto, o grafo é a fonte da inteligência.

    4. Conclusão: A Lição da Meta

    A Meta é o estudo de caso definitivo de uma empresa “Graph-First”. A lição que aprendemos com ela não é sobre uma arquitetura específica, mas sobre a importância fundamental de:

    1. Modelar o Domínio como um grafo (o Social Graph).
    2. Construir a Infraestrutura para suportar esse grafo em escala (TAO).
    3. Usar a Estrutura do Grafo para gerar os sinais (features) que alimentam os modelos de IA.

    O poder da Meta não vem apenas dos seus modelos de deep learning, mas do fato de que esses modelos são alimentados pelo grafo de conexões humanas mais rico já construído.

    Referências

    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

  • Netflix e Recomendação: Resolvendo um Problema de Grafo com Fatoração Matricial

    Visualização conceitual do sistema de recomendação. Um grafo bipartido com nós de 'usuários' (azuis) e 'itens' (vermelhos) conectados por uma nuvem central de 'fatores latentes', simbolizando a Fatoração Matricial.

    Resumo — O que faz a Netflix acertar (quase) sempre o que você quer assistir? A resposta é um dos sistemas de grafos mais valiosos do mundo. Na sua essência, o problema de recomendação é um imenso grafo bipartido ligando usuários a itens, e o desafio é prever as “arestas” que faltam. A solução que definiu a indústria não foi uma GNN, mas uma técnica elegante chamada Fatoração Matricial (MF). Este post explica a intuição por trás dessa ideia, como ela funciona e por que é uma lição fundamental sobre grafos.

    1. Modelagem como Grafo: A Planilha de 1 Milhão de Dólares

    O problema que a Netflix enfrenta é direto: Como prever a nota que um usuário daria a um filme que ele ainda não viu?

    Imagine uma planilha gigante. De um lado, todas as linhas são os milhões de usuários da Netflix. Do outro, todas as colunas são os milhares de filmes e séries do catálogo. Quando você dá uma nota para um filme, você preenche uma célula. O “Netflix Prize”, lançado em 2006, foi um desafio de 1 milhão de dólares para criar um algoritmo que conseguisse preencher os bilhões de células vazias com a maior precisão possível.

    Em Teoria dos Grafos, essa “planilha” é um grafo bipartido.

    • Por que “bipartido”? Porque temos dois tipos de nós que não se conectam entre si: um conjunto de nós de Usuário (que chamaremos de U) e um conjunto de nós de Item (que chamaremos de I).
    • As notas são as arestas (ligações) que conectam um nó de usuário a um nó de item. O peso dessa aresta é a nota, r_{ui}.

    O resultado é uma matriz de interações R gigantesca e extremamente esparsa, pois a maioria dos usuários não avaliou a maioria dos itens. O problema, portanto, é um clássico link prediction (previsão de arestas, ou, no caso, do peso delas).

    2. A Solução Elegante: Fatoração Matricial (MF)

    Como prever as células vazias? A intuição da Fatoração Matricial é genial. Em vez de se preocupar com as conexões diretas (ex: “usuários que gostaram do filme A também gostaram do B”), ela assume que existe um “DNA” oculto por trás dos gostos.

    Imagine que o “gosto” de cada usuário pode ser descrito por um punhado de números (ex: 50 “fatores latentes”). Esses fatores podem representar coisas como:

    • Gosto por Ação: 9.0
    • Gosto por Comédia: 2.1
    • Gosto pelo Diretor X: 7.5 …e assim por diante. O algoritmo não sabe o que são esses fatores, ele apenas os “descobre” matematicamente. Da mesma forma, cada filme é descrito pelos mesmos 50 fatores:
    • O quanto ele é Ação: 8.8
    • O quanto ele é Comédia: 1.5
    • O quanto ele é do Diretor X: 7.2

    A nota que você daria a um filme é simplesmente a “compatibilidade” entre o seu vetor de gostos e o vetor de características do filme.

    Em termos técnicos, isso se chama Fatoração Matricial (MF). O algoritmo decompõe a matriz gigante R em duas matrizes menores:

    • P: Onde cada linha p_u é o vetor de fatores latentes do usuário u.
    • Q: Onde cada linha q_i é o vetor de fatores latentes do item i.

    A previsão da avaliação \hat{r}_{ui} que o usuário u daria ao item i é simplesmente o produto escalar de seus vetores:

    \hat{r}_{ui} = p_u^T q_i

    O modelo aprende os vetores p_u e q_i minimizando o erro nas avaliações que ele já conhece. A função de perda (objetivo) mais comum é o erro quadrático regularizado (Koren et al., 2009):

    \displaystyle \min_{p*, q*} \sum_{(u,i) \in K} (r_{ui} - p_u^T q_i)^2 + \lambda (||p_u||^2 + ||q_i||^2)

    Traduzindo a matemática: Esta equação diz ao computador: “Encontre os vetores de usuário (p_u) e de item (q_i) que, quando multiplicados (p_u^T q_i), cheguem o mais perto possível das notas reais que já conhecemos (r_{ui}). Faça isso evitando que os números dos vetores fiquem grandes demais (essa é a ‘regularização’ \lambda, que previne overfitting).”

    Na prática, podemos ver a MF como uma forma poderosa de aprender embeddings para os nós do grafo bipartido.

    3. Além da MF: O Poder dos Ensembles e do Contexto

    A solução vencedora do Netflix Prize, “BellKor’s Pragmatic Chaos”, não foi apenas um modelo de MF, mas um ensemble (mistura) de centenas de modelos.

    Mais importante ainda, como descrito por Gómez-Uribe & Hunt (2015), o sistema de produção real da Netflix evoluiu para muito além da MF estática. O sistema moderno considera contexto:

    • Temporalidade: O que você assistiu hoje? Seus gostos mudam com o tempo.
    • Contexto de Acesso: Você está na TV (provavelmente buscando filmes) ou no celular (talvez séries mais curtas)?
    • Sazonalidade: É dezembro? A chance de você querer um filme de Natal é maior.

    O sistema de produção real é um ensemble massivo que usa a MF como uma das fontes de sinal, mas a combina com dezenas de outras features e modelos para gerar a recomendação final.

    4. Por que a Fatoração Matricial Funcionou Tão Bem?

    1. Generalização e Descoberta: Ao aprender fatores latentes, o modelo generaliza. Ele descobre padrões por conta própria. Por exemplo, ele pode aprender que pessoas que gostam de ‘Star Wars’ e ‘Blade Runner’ (que compartilham fatores latentes de ‘ficção científica épica’) também tendem a gostar de ‘Duna’, mesmo que não haja uma conexão óbvia entre os usuários que assistiram esses filmes.
    2. Escalabilidade: Embora a matriz R seja imensa, as matrizes P e Q são muito menores (ex: k=50 ou k=100 fatores). Algoritmos como Stochastic Gradient Descent (SGD) ou Alternating Least Squares (ALS) conseguem otimizar esses fatores de forma eficiente.
    3. Flexibilidade: O modelo de MF pode ser facilmente estendido para incluir bias (vieses) de usuário (ex: “usuário A é mais crítico e sempre dá notas baixas”) e de item (ex: “filme B é popular e sempre recebe notas altas”).

    5. Limitações da Abordagem Clássica

    O principal desafio da MF pura é o problema do início frio (cold start):

    • Novo Usuário: Se um usuário u_{novo} chega, não temos nenhuma avaliação dele. É impossível construir seu vetor de fatores p_{u_{novo}}.
    • Novo Item: Se um filme i_{novo} é adicionado ao catálogo, ele não tem avaliações. Seu vetor q_{i_{novo}} é desconhecido.

    Nesses casos, o sistema precisa recorrer a outras heurísticas (ex: recomendar os itens mais populares, ou perguntar os gêneros favoritos do usuário).

    6. Onde Grafos “Modernos” (GNNs) Poderiam Ajudar?

    Este é o ponto-chave: a MF é uma solução fantástica para o grafo bipartido, mas ela só usa a estrutura de interação. E se quiséssemos usar os atributos dos nós?

    É aqui que as Redes Neurais de Grafos (GNNs) brilham:

    1. Resolvendo o Cold Start: Se tivéssemos atributos para os itens (gênero, atores, diretor, ano) e para os usuários (demografia, localização), uma GNN (como a GraphSAGE) poderia aprender a generalizar a partir desses atributos. Ela aprenderia uma função que gera o embedding de um filme com base nos seus metadados, resolvendo o problema do item novo.
    2. Usando Grafos Heterogêneos: Poderíamos modelar o problema de forma mais rica, não apenas com usuários e itens, but also com nós de “Ator”, “Diretor”, “Gênero”. Uma GNN poderia propagar informação por esse grafo heterogêneo.
    3. Capturando Padrões Complexos: GNNs podem capturar padrões estruturais mais complexos na vizinhança de um nó do que o produto escalar da MF, potencialmente levando a recomendações mais sofisticadas.

    Conclusão

    O sistema da Netflix é um estudo de caso fundamental sobre o poder dos grafos. Ele demonstra que, embora o problema seja de grafo (um grafo bipartido), a solução mais eficaz por muito tempo foi uma técnica de aprendizado de representação (embedding), a Fatoração Matricial.

    Ele nos ensina que “usar grafos” não significa apenas aplicar GNNs; significa entender a estrutura relacional do problema e escolher a ferramenta certa para ele — seja ela MF, PageRank ou uma GCN.

    Referências

    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

  • GraphRAG: O Poder dos Grafos para Reduzir Alucinações em LLMs

    Comparativo visual entre RAG tradicional e GraphRAG. O RAG 'puro' (esquerda) mostra blocos de texto espalhados em uma névoa (alucinação). O GraphRAG (direita) mostra um grafo organizado de entidades e relações, simbolizando clareza e redução de alucinações.

    Resumo — Você já se frustrou com um chatbot que “inventa” informações? O GraphRAG surge como uma solução poderosa. Ele estende a técnica de Retrieval-Augmented Generation (RAG) usando grafos de conhecimento para dar mais “base” às respostas dos LLMs, combatendo as temidas alucinações. A ideia é transformar seus documentos em uma rede inteligente de “coisas” conectadas, permitindo que o LLM acesse um contexto muito mais rico e confiável.

    1. O Problema: Quando o RAG “Puro” Não Basta

    Imagine que você está usando um chatbot baseado em RAG (Retrieval-Augmented Generation). Ele funciona pegando sua pergunta, buscando trechos relevantes em uma base de documentos e depois usa esses trechos para ajudar um Large Language Model (LLM) a gerar uma resposta.

    Parece ótimo, certo? E é. Mas em bases de documentos muito grandes ou complexas, surgem problemas:

    • Informação Espalhada: Um fato importante pode estar dividido em vários documentos, ou em parágrafos distantes do mesmo documento.
    • Conexões Ocultas: A relação entre “quem fez o quê”, “quando algo aconteceu” ou “por que uma regra existe” pode não ser óbvia olhando apenas para trechos isolados.
    • Ambiguidade: Um mesmo nome pode significar coisas diferentes (“Jaguar” como animal vs. carro).

    Quando isso acontece, o LLM pode receber trechos incompletos ou desconexos. O que ele faz? Ele tenta “preencher as lacunas”, e muitas vezes essa “lacuna” é preenchida com uma alucinação — uma informação convincente, mas falsa ou sem base nas evidências.

    2. A Ideia-Chave do GraphRAG: Documentos Que Conversam Entre Si

    O GraphRAG ataca esse problema organizando o conhecimento de uma forma muito mais inteligente: como um grafo.

    Pense nos seus documentos não como textos soltos, mas como um grande quebra-cabeça de informações. O GraphRAG pega cada peça desse quebra-cabeça e a transforma em uma “coisa” conectada a outras “coisas”.

    • “Coisas” (Nós): São as entidades principais: pessoas, empresas, produtos, leis, artigos, datas, locais.
    • “Conexões” (Arestas): São as relações entre essas coisas: “é autor de”, “pertence a”, “depende de”, “publicado em”, “cita”.
    • Evidências: Cada conexão ou “coisa” carrega consigo o trecho original do documento que a comprova.

    Quando você faz uma pergunta, o sistema não busca apenas por palavras-chave. Ele “navega” nessa rede de conhecimento, encontra o pedaço do grafo que é mais relevante para sua pergunta e apresenta essa rede de evidências interconectadas para o LLM.

    Em termos técnicos, o GraphRAG organiza o conhecimento como um knowledge graph:

    • Nós (Entidades): Pessoa, Empresa, Produto, Lei, API, Artigo, Versão, Lugar, Data.
    • Arestas (Relações): autor-de, pertence-a, depende-de, publicado-em, revogado-por, cita.
    • Atributos: Cada nó ou aresta pode ter atributos como: trechos de apoio do documento original, links para a fonte, data de criação/revisão, indicadores de confiança.

    Exemplo Rápido: Do Texto ao Grafo

    Imagine o seguinte trecho na sua base de conhecimento:

    “O modelo GrafoNet foi publicado na Conferência X em 2024 pelo Laboratório Y.”

    Isso pode ser transformado em um grafo com:

    • Nós: GrafoNet (Modelo), Conferência X (Evento), 2024 (Tempo), Laboratório Y (Instituição).
    • Arestas:
      • GrafoNet —(publicado-em)→ Conferência X
      • Laboratório Y —(autor-de)→ GrafoNet

    Cada nó e aresta guarda a proveniência da informação (o link ou parágrafo exato), permitindo citações precisas na resposta final.

    3. O Fluxo de um Sistema GraphRAG na Prática

    Construir um GraphRAG envolve algumas etapas:

    1. Ingestão de Documentos: Coletar todos os documentos (PDFs, wikis, relatórios, FAQs, etc.).
    2. Extração de Conhecimento: Usar algoritmos (automáticos ou manuais) para identificar as entidades (quem, o quê, onde, quando) e as relações (o que conecta essas entidades) em cada documento.
    3. Construção do Grafo: Montar o knowledge graph. Isso significa criar os nós (com IDs únicos para evitar duplicidade, ex: “Apple Inc.” é um único nó, mesmo que apareça em vários documentos) e conectar com as arestas.
    4. Indexação Híbrida: Manter dois tipos de busca:
      • Busca Tradicional: Um índice vetorial/textual para buscar por similaridade de texto (como um RAG comum).
      • Busca em Grafo: Um banco de grafos que permite navegar pelas conexões (usando linguagens como Cypher, Gremlin ou SPARQL).
    5. Consulta em Duas Etapas:a. Busca de Sementes: Primeiro, você busca “sementes” (nós ou trechos candidatos) usando a busca textual/vetorial.b. Expansão do Subgrafo: A partir dessas “sementes”, o sistema “navega” no grafo (como “vizinhos a k-hops” ou tipos específicos de relações) para encontrar todas as evidências conectadas.
    6. Ranqueamento de Evidências: Combina a similaridade textual (o quanto o trecho é parecido com a pergunta) com sinais de grafo (a “importância” ou “centralidade” do nó no subgrafo, o quão recente é a informação, a confiabilidade da fonte).
    7. Compilação do Contexto: Gera resumos curtos e citáveis para cada nó e aresta recuperada, formando um contexto rico para o LLM.
    8. Geração da Resposta: Envia o contexto compilado para o LLM com instruções claras para se basear apenas nessas evidências e citar as fontes.

    Um Modelo Simples para Ranqueamento Híbrido

    Para ranquear as evidências recuperadas, podemos combinar a similaridade de texto com a importância do grafo. Imagine que o quanto uma evidência é relevante para sua pergunta é uma mistura de:

    1. O quão parecido o texto da evidência é com sua pergunta (similaridade).
    2. O quão “central” ou “importante” essa evidência é dentro do pedaço do grafo que encontramos.

    Em termos técnicos, podemos fazer isso com uma fórmula simples. Seja \cos(q,d) a similaridade de cosseno entre a consulta q e um documento/nó d. E g(d) um score de importância do nó no grafo (ex: PageRank normalizado no subgrafo relevante). Um ranqueador híbrido simples pode ser:

    \displaystyle s(q,d) = \lambda \cos(q,d) + (1-\lambda) g(d), \quad \lambda \in [0,1].

    Esta equação calcula um score de relevância (s(q,d)) para cada evidência. \lambda é um peso que você ajusta:

    • Se \lambda for alto (próximo de 1) → prioriza a similaridade textual (mais parecido com o RAG tradicional).
    • Se \lambda for baixo (próximo de 0) → prioriza a estrutura e importância do grafo (centralidade, autoridade e coerência relacional).

    4. Onde o GraphRAG Realmente Ajuda?

    O GraphRAG é um superpoder para seu sistema de perguntas e respostas:

    • Desambiguação: Diferenciar “Jaguar (animal)” de “Jaguar (carro)” ao olhar para o tipo da entidade no grafo.
    • Perguntas Multi-Passo: Responder a perguntas complexas que exigem uma cadeia de evidências (ex: “Qual a idade do autor do artigo X, que trabalhou na empresa Y?”). O grafo permite navegar por essas conexões (X → autor → idade; autor → empresa → Y).
    • Menos Alucinação: A resposta do LLM é ancorada em nós e arestas concretas e citáveis, reduzindo a chance de invenções.
    • Relevância Temporal: Usar datas como nós ou atributos nas arestas para priorizar conteúdo mais atualizado, ou filtrar informações antigas.

    5. Boas Práticas e Pontos de Atenção

    Para implementar um GraphRAG eficaz:

    • Modelagem do Grafo:
      • Defina um esquema mínimo com tipos de nós e arestas para manter a organização e evitar a “bagunça” do grafo.
      • Normalize nomes (sinônimos, entity linking simples) para garantir que a mesma entidade tenha um único nó.
      • Use arestas direcionadas e com atributos temporais (ex: entrou-em-vigor-em, revogado-por).
    • Avaliação do Sistema:
      • Recuperação: Use métricas clássicas de IR como nDCG, MAP, e Recall@k para avaliar se as evidências corretas estão sendo encontradas.
      • Geração: Meça a fidelidade (faithfulness) da resposta (o quanto ela se baseia nas evidências) e a precisão (F1/EM) em datasets de QA.
      • Confiabilidade: Calcule a porcentagem de respostas com citações válidas e penalize citações quebradas.
    • Limitações e Custos:
      • A extração de entidades nunca é perfeita; tenha um fallback para a busca semântica tradicional.
      • A arquitetura é mais complexa e pode introduzir latência na resposta. Monitore os custos operacionais.
      • Cuidado com o viés estrutural: nós muito conectados podem dominar os resultados, exigindo ajustes no seu ranqueador.

    6. Exemplo de Prompt para Geração com o LLM

    Para instruir o LLM a usar o contexto do grafo de forma correta e combater alucinações, o prompt é crucial:

    Instruções: Responda à pergunta do usuário baseando-se exclusivamente nas evidências fornecidas no contexto. Se precisar citar, use o formato [Nó:ID | Fonte | Data] no final da frase. Se a evidência fornecida for insuficiente para responder, diga claramente: “A evidência fornecida é insuficiente para responder à pergunta.”

    Contexto (Subgrafo de Evidências):

    • [Resumo conciso da evidência do Nó A com link para fonte]
    • [Resumo conciso da evidência da Relação A->B com link para fonte]
    • …

    Pergunta: [Pergunta do usuário]

    Tabela Resumo: RAG “Puro” vs. GraphRAG

    AspectoRAG “Puro”GraphRAG
    RepresentaçãoTrechos de texto independentesEntidades e Relações (subgrafo)
    RecuperaçãoBusca textual/vetorialConsulta híbrida (vetor + grafo)
    GroundingImplícito (baseado em trechos)Explícito (nós e arestas citáveis)
    Perguntas Multi-hopLimitadoNatural (via navegação no grafo)
    Risco de AlucinaçãoMaiorMenor (evidência estruturada)
    Custo/ComplexidadeMenorMaior (requer camada de grafo)

    Referências Essenciais

    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

  • PageRank e Knowledge Graph: A Evolução da Busca do Google Através dos Grafos

    Visualização da evolução da busca. O PageRank (esquerda) é uma galáxia caótica de links azuis. O Knowledge Graph (direita) é uma rede organizada de entidades coloridas, mostrando a transição da estrutura para a semântica.

    Resumo — A web é um imenso grafo dirigido, com páginas como nós e hyperlinks como arestas. O algoritmo PageRank, pilar fundamental do Google, introduziu uma forma robusta de medir a “importância” estrutural nesse grafo. Este texto explica a intuição por trás do PageRank, sua matemática, e como essa ideia evoluiu para a busca semântica com o Knowledge Graph, que entende “coisas” em vez de apenas “strings”.

    1. A Web Como um Grafo (e Por Que Isso Importa)

    Imagine cada página na web como um vértice e cada link (hyperlink) como uma aresta direcionada de uma página para outra. Diferente de dados tabulares, a qualidade de uma página não depende apenas do seu conteúdo, mas de como ela é referenciada por outras. Em meados dos anos 1990, a web estava se tornando caótica. Os buscadores da época, que se baseavam primariamente em contagem de palavras-chave, eram fáceis de manipular.

    A ideia revolucionária de Larry Page e Sergey Brin foi: usar a estrutura do grafo da web para inferir relevância. A premissa era que um link de uma página A para uma página B é um “voto” da página A para a B.

    2. A Intuição do PageRank: Votos Ponderados

    Mas o PageRank é mais inteligente do que uma simples contagem de “votos”. Ele opera sob duas intuições principais:

    1. Nem todos os votos são iguais: Um “voto” (link) vindo de uma página muito importante (como um grande portal de notícias ou uma universidade) “pesa” muito mais do que um link vindo de uma página pessoal desconhecida.
    2. Importância é transitiva: Se uma página A recebe muitos votos de páginas importantes, a própria página A se torna importante.

    Isso cria um paradoxo: para saber o quão importante é uma página, precisamos saber a importância das páginas que linkam para ela. Mas como saber a importância delas? A solução é o “Navegante Aleatório” (Random Surfer).

    Imagine um usuário que navega na web de forma aleatória. Ele está em uma página e, a cada passo, ele tem duas escolhas:

    • Escolha A (Seguir um Link): Ele clica em um link aleatório da página atual.
    • Escolha B (Teleporte): Ele se cansa da página atual e digita um novo endereço, “teleportando-se” para qualquer outra página da web.

    O score de PageRank de uma página é simplesmente a probabilidade de encontrarmos esse navegante aleatório nela após ele navegar por muito tempo. Páginas com muitos links de entrada, especialmente de páginas já importantes, “capturam” esse navegante com mais frequência.

    Em termos técnicos, esse processo é uma Cadeia de Markov.

    • A probabilidade de o navegante seguir um link (Escolha A) é chamada de damping factor (fator de amortecimento), representado por \alpha. Um valor típico é 0{,}85.
    • A probabilidade de ele se teleportar (Escolha B) é, portanto, 1-\alpha (ou seja, 0{,}15).

    O teleporte é crucial: ele impede que o navegante fique “preso” em páginas sem saída (dangling nodes) ou em pequenos ciclos de links, garantindo que ele possa, eventualmente, chegar a qualquer página da web.

    A equação central que descreve a distribuição estacionária desse processo (ou seja, os scores finais do PageRank) é:

    \displaystyle r = \alpha P^{\top} r + (1-\alpha)v

    Traduzindo a matemática: Esta equação pode parecer intimidante, mas o que ela diz é:

    “O score de PageRank de uma página (r) é a soma de duas partes:

    1. A chance dela receber um “voto” vindo de um link de outra página (a parte \alpha P^{\top} r).
    2. A chance dela receber a visita de um “teleporte” aleatório (a parte (1-\alpha)v).”

    Onde P é a matriz que representa todos os links da web e v é o vetor de teleporte (que pode ser uniforme, dando a mesma chance para todas as páginas). Na prática, o Google não “resolve” essa equação de uma vez, mas a calcula de forma iterativa (power iteration) até que os scores parem de mudar.

    3. HITS vs. PageRank: Duas Visões de Autoridade

    Desenvolvido quase na mesma época, o algoritmo HITS (Hyperlink-Induced Topic Search) de Jon Kleinberg propôs uma visão diferente, separando as páginas em dois papéis:

    • Authorities: Páginas com conteúdo de alta qualidade sobre um tópico.
    • Hubs: Páginas que funcionam como ótimos diretórios, apontando para as melhores authorities.

    A diferença-chave é que o HITS é dependente da consulta (executado em um subgrafo específico do tópico buscado), enquanto o PageRank é global e independente da consulta. Na prática, os buscadores modernos combinam múltiplos sinais.

    4. A Evolução: Do Link ao Significado com o Knowledge Graph

    O PageRank foi genial para entender a estrutura da web, mas ele não entendia o significado do conteúdo. Para o PageRank, um link é apenas um “voto”, sem saber por que ele foi dado.

    Em 2012, o Google anunciou o Knowledge Graph, marcando uma mudança fundamental da busca por “strings” (texto) para a busca por “coisas” (entidades).

    O Knowledge Graph é uma imensa base de conhecimento estruturada como um grafo, onde:

    • Nós são Entidades: Pessoas (ex: “Leonardo da Vinci”), lugares (ex: “Paris”), obras (ex: “Mona Lisa”), conceitos.
    • Arestas são Relações: Fatos que conectam essas entidades (ex: “Leonardo da Vinci” —criador de→ “Mona Lisa”; “Mona Lisa” —localizada em→ “Paris”).

    Isso permitiu avanços cruciais:

    1. Desambiguação: Entender que quando você busca “Jaguar”, você pode estar falando do animal, do time de futebol americano ou da marca de carro. O grafo de entidades provê o contexto.
    2. Respostas Diretas: Apresentar os famosos “painéis de conhecimento” com fatos consolidados (ex: data de nascimento, altura, obras principais de um artista).
    3. Expansão de Consulta: Se você busca “Albert Einstein”, o grafo sugere entidades relacionadas como “Teoria da Relatividade” ou “Niels Bohr”.

    Enquanto o PageRank mede a importância estrutural na malha de hyperlinks, o Knowledge Graph provê a compreensão semântica das entidades. Hoje, esses dois mundos cooperam para ranquear e responder às suas perguntas.

    Tabela Resumo: Três Abordagens

    AspectoPageRankHITSKnowledge Graph
    NaturezaGlobal, indep. da consultaDependente da consultaSemântico (entidades/rel.)
    Sinal PrincipalEstrutura de linksHubs ↔ AuthoritiesFatos e relações
    VantagemEscalável, robustoCapta estrutura localDesambiguação, respostas diretas
    LimitaçãoPopularidade ≠ intençãoSensível a ruídoCuradoria, consistência

    Referências

    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

  • Bem-vindo ao GrafoLab: Desvendando o Poder dos Grafos e GNNs

    Resumo — O GrafoLab nasce para investigar, explicar e aplicar grafos e Redes Neurais de Grafos (GNNs) em problemas reais de inteligência artificial e ciência de dados. Nosso compromisso é combinar rigor científico, reprodutibilidade e uma escrita clara para aproximar teoria e prática.

    Por que se importar com Grafos?

    Grafos são estruturas matemáticas compostas por vértices (nós) e arestas (ligações). Embora a definição seja simples, seu poder descritivo é imenso. Eles são a linguagem natural para modelar relações em sistemas complexos: redes sociais, páginas na web, transações financeiras, interações entre proteínas, redes de computadores e muito mais.

    A formalização da Teoria dos Grafos remonta a 1736 com Leonhard Euler e seu famoso problema das Sete Pontes de Königsberg. Ao resolvê-lo, Euler inaugurou o que chamou de geometria situs (geometria das posições), lançando as bases para um campo que se tornaria uma ferramenta unificadora para entender a conectividade e a estrutura dos dados.

    Do PageRank às GNNs: Uma Linha do Tempo Evolutiva

    • Anos 1990–2000: Com a explosão da World Wide Web, algoritmos baseados em grafos ganharam protagonismo. O PageRank, por exemplo, modelou a web como um imenso grafo direcionado. Ao analisar as ligações entre as páginas, foi capaz de estimar a importância de cada uma, transformando para sempre os mecanismos de busca (Brin & Page, 1998).
    • A última década: As Redes Neurais de Grafos (GNNs) levaram o aprendizado profundo a um novo território: os dados não-euclidianos. Em vez de operar sobre grades rígidas como imagens ou sequências lineares de texto, as GNNs propagam e agregam informações através das arestas de um grafo. O resultado são modelos que aprendem representações informadas pela estrutura da rede (Kipf & Welling, 2016; Hamilton et al., 2017).

    Em suma, as GNNs permitem criar modelos que entendem relações, não apenas atributos isolados — uma capacidade essencial quando a estrutura é o problema.

    O que você encontrará no GrafoLab

    • Fundamentos bem explicados: Conceitos de teoria dos grafos (conectividade, caminhos, medidas de centralidade, subgrafos, cliques) com demonstrações claras e intuição geométrica.
    • GNNs sem mistério: Guias práticos sobre arquiteturas como GCN, GraphSAGE, GAT e suas variantes. Discutiremos quando usar cada uma, suas hipóteses e como avaliar sua robustez.
    • Aplicações em problemas reais: Estudos de caso em sistemas de recomendação, busca semântica, grafos de conhecimento (knowledge graphs), Graph-augmented RAG, bioinformática e, claro, detecção de fraudes. O foco será sempre em como modelar o problema, na engenharia de atributos e arestas e nas métricas de impacto.
    • Boas práticas científicas: Nosso conteúdo seguirá princípios de reprodutibilidade (código, seeds, versões de bibliotecas), com discussões transparentes sobre ameaças à validade dos resultados (data shift, leakage, etc.) e a importância de baselines fortes.
    • Perspectiva brasileira: Análises sobre os desafios e as oportunidades locais, incluindo dados, infraestrutura, conformidade (LGPD) e casos de uso no ecossistema de tecnologia do Brasil.

    Nossos Compromissos Editoriais

    1. Precisão antes do hype: Preferimos as nuances e os intervalos de confiança às proclamações exageradas.
    2. Fontes primárias: Nossas referências serão sempre artigos de conferências, journals e surveys reconhecidos pela comunidade científica.
    3. Transparência experimental: Seremos explícitos sobre seeds, versões, partições de dados e métricas utilizadas em nossos exemplos.
    4. Conteúdo vivo: O campo evolui rápido, e nossos artigos serão atualizados para refletir isso.

    Para quem é o GrafoLab?

    • Para profissionais e pesquisadores que já trabalham ou desejam trabalhar com grafos e GNNs.
    • Para estudantes que buscam uma trilha de aprendizado coerente, dos fundamentos às fronteiras do conhecimento.
    • Para tomadores de decisão que precisam entender o que é possível, seguro e mensurável ao modelar problemas como redes.

    Referências Essenciais

Descubra o poder dos grafos e da IA.

Receba insights, artigos e descobertas sobre Grafos, GNNs e Inteligência Artificial — direto na sua caixa de entrada, uma vez por semana.

Não fazemos spam! Leia nossa política de privacidade para mais informações.