Resumo Técnico: Recomendações Eficientes via Coarsening de Grafos e Propagação de Rótulos

Declaração do Problema

Sistemas de recomendação baseados em grafos são amplamente utilizados em aplicações industriais, como telecomunicações, para modelar interações complexas entre usuários e itens ou entre usuários. No entanto, à medida que esses conjuntos de dados escalam para milhões ou bilhões de nós e arestas, eles enfrentam desafios significativos de escalabilidade e eficiência. As GNNs (Redes Neurais de Grafos) padrão, embora poderosas, frequentemente exigem recursos computacionais pesados, sofrem com over-smoothing (suavização excessiva) e têm dificuldade com dependências de longo alcance em grafos massivos. Por outro lado, alternativas leves como o Algoritmo de Propagação de Rótulos (LPA) são computacionalmente eficientes, mas tornam-se proibitivamente lentas quando aplicadas diretamente a grafos industriais de escala total devido à necessidade de iterar sobre cada aresta. Além disso, o downsampling de grafos ingênuo muitas vezes destrói estruturas de comunidades críticas e isola hubs, degradando a qualidade da recomendação. O desafio central é equilibrar a qualidade preditiva com o custo computacional, especificamente em domínios onde as recomendações devem ser adaptadas a grupos implícitos de usuários (ex: famílias) em vez de apenas indivíduos.

Metodologia

Os autores propõem um framework de difusão de dois estágios flexível que integra o coarsening de grafos orientado pelo negócio com a propagação de rótulos de múltiplos passos. O framework opera em um grafo de usuários não direcionado $G=(V, E, Y)$ e procede através de três fases distintas:

1. Coarsening de Grafo (Agregação Orientada pelo Negócio)

Em vez de usar algoritmos genéricos de detecção de comunidades, o método agrega usuários em "super nós" (comunidades) baseando-se em heurísticas de domínio específicas relevantes para o setor de telecomunicações. Os usuários são fundidos se satisfizerem condições como:

• Frequência de Interação: Alta duração ou frequência de chamadas.
• Sobrenome: Nomes de família compartilhados.
• Cuidado (Caring): Um usuário entra em contato frequentemente com o suporte para tratar de outro.
• Saldo (Balance): Dependências financeiras (ex: recarga de saldo de outro usuário).
• Redundância: Múltiplas linhas associadas a um único usuário.

Este processo cria um grafo refinado $G'$ onde os super nós representam famílias ou domicílios implícitos. Uma nova matriz de rótulos $Y'$ é construída agregando as ofertas aceitas por todos os usuários dentro de uma comunidade.

2. Propagação Inter-Comunidade

Um primeiro passo de propagação é realizado no grafo refinado $G'$ para gerar previsões de granularidade grossa. O framework suporta dois algoritmos para este estágio:

• Algoritmo de Propagação de Rótulos (LPA): Atualiza iterativamente os rótulos dos super nós com base na dominância de vizinhança.
• Rede Neural de Grafos (GNN): Especificamente, uma arquitetura GraphSAGE é aplicada a uma representação de grafo heterogêneo contendo nós de "Comunidade" e nós de "Item". Isso modela interações ao nível da comunidade para prever arestas comunidade-item.

3. Propagação Intra-Comunidade

Para restaurar a personalização de granularidade fina, um segundo passo de propagação é executado em paralelo dentro de cada subgrafo original de nível de usuário.

• Um nó representante $r_c$ é criado para cada comunidade, contendo a informação de rótulo agregada do passo inter-comunidade.
• Este nó é conectado a todos os usuários individuais na comunidade, formando um subgrafo aumentado $G_{c, aug}$.
• O LPA é aplicado a cada subgrafo para refinar as previsões grossas em recomendações de usuários individuais.

Principais Contribuições

O artigo formaliza e valida as seguintes contribuições:

1. Coarsening Orientado pelo Negócio: Uma técnica que utiliza regras de negócio específicas para descobrir estruturas familiares implícitas, preservando relações essenciais enquanto reduz o tamanho do grafo em mais de 70%.
2. Esquema de Propagação de Dois Passos: Uma arquitetura eficiente combinando difusão de grafo grosseiro (para escalabilidade) com refinamento de granularidade fina (para precisão), garantindo baixa latência e alta precisão.
3. Validação Empírica: Uma avaliação abrangente contra o LPA de grafo total e métodos de coarsening alternativos (Louvain, Unique label-based), demonstrando melhorias significativas em escalabilidade e qualidade de recomendação.

Resultados Experimentais

O framework foi avaliado em um conjunto de dados de telecomunicações real da TIM (Itália) contendo mais de 13 milhões de usuários e 561 ofertas promocionais únicas.

• Efetividade (RQ1):
  • Usando LPA em ambos os estágios, o método proposto alcançou uma melhoria de 24% no NDCG@5 sobre o baseline de LPA de grafo total.
  • A incorporação de uma GNN leve no primeiro estágio aumentou ainda mais o NDCG@5 em mais de 50% em comparação com a versão apenas com LPA e 35% sobre uma GNN treinada em um grafo refinado via Louvain.
  • O baseline de GNN de grafo total resultou em um erro de Out-of-Memory (OOM), destacando a necessidade de coarsening para GNNs nesta escala.
• Integridade Estrutural (RQ2):
  • O coarsening orientado pelo negócio preservou propriedades topológicas (distribuição de grau, coeficientes de agrupamento) melhor do que a estratégia "Unique" (que criou comunidades excessivamente apertadas) e ofereceu um melhor equilíbrio que o método Louvain em relação à densidade e esparsidade de arestas.
• Eficiência e Escalabilidade (RQ3):
  • O passo de coarsening levou apenas 34 segundos devido às heurísticas pré-computáveis.
  • O baseline de LPA de grafo total levou mais de 17 minutos, enquanto o método proposto completou o processo de LPA de dois estágios em 9 minutos.
  • A abordagem potencializada por GNN levou aproximadamente 13 minutos para a propagação, mas permaneceu viável, enquanto a GNN de grafo total era inviável.
  • O segundo passo de propagação (intra-comunidade) é altamente paralelizável e opera em subgrafos pequenos, permitindo tempos de inferência de sub-segundo para recomendações de usuários individuais.
• Ablação (RQ4):
  • O desempenho melhorou com um aumento no número de camadas de propagação ($L$), atingindo o pico em $L=5$ com um fator de amortecimento $\alpha=0.5$. Diferente de outros métodos, o framework proposto mostrou clara sensibilidade a esses hiperparâmetros, indicando que a propagação profunda dentro da estrutura refinada gera ganhos significativos.

Significância e Alegações

O artigo afirma que o coarsening de grafos é indispensável para aplicar GNNs a grafos industriais de grande escala, pois evita falhas de memória e reduz o overhead computacional. O framework proposto demonstra que uma abordagem orientada pelo negócio para o coarsening é superior a algoritmos genéricos (como Louvain) para tarefas de recomendação envolvendo estruturas sociais implícitas (ex: famílias).

Os autores enfatizam que sua abordagem entrega um equilíbrio ideal entre escalabilidade, latência e qualidade de recomendação. Especificamente:

• O pipeline apenas com LPA é imediatamente implantável em ambientes de produção de baixa latência.
• A opção potencializada por GNN é adequada para cenários onde o maior desempenho preditivo justifica o custo adicional de treinamento.
• O método é particularmente eficaz para ofertas orientadas à família, onde recomendar o mesmo item para vários membros de um domicílio é redundante; o passo de coarsening aborda isso naturalmente ao agregar a intenção do usuário no nível da comunidade antes do refinamento.

O trabalho conclui que esta abordagem baseada em coarsening é praticamente aplicável a campanhas de marketing do mundo real, onde manter recomendações de alta qualidade enquanto se gerencia mudanças frequentes nas interações dos usuários é crítico.