Resumo Técnico: DG-CoLearn

1. Declaração do Problema

O Aprendizado de Grafos Dinâmicos (DGL) é crítico para modelar dados em evolução em domínios como redes sociais e finanças. No entanto, as abordagens existentes enfrentam dois gargalos principais em configurações realistas de larga escala:

1. Ineficiência Computacional: Os métodos atuais, tanto centralizados quanto colaborativos, normalmente retreinam modelos sobre snapshots inteiros de grafos a cada timestamp. Isso é proibitivamente caro, dado que as atualizações em grafos dinâmicos são frequentemente esparsas e localizadas.
2. Tensão entre Privacidade e Escalabilidade na Colaboração: Embora o aprendizado colaborativo distribua a computação, os frameworks existentes lutam com arestas entre partições (cross-partition edges).
   • O Aprendizado Federado (FL) padrão frequentemente assume grafos de clientes disjuntos ou visibilidade total da conectividade entre clientes, o que não ocorre em grafos particionados dinâmicos realistas.
   • Os modelos de privacidade existentes focam em prevenir a fuga de dados para um servidor não confiável. No entanto, em muitos sistemas práticos (ex: plataformas financeiras), um coordenador central confiável mantém a topologia global, e o risco principal é a fuga estrutural cliente-para-cliente (ou seja, um cliente inferir a estrutura do subgrafo de outro cliente).
   • Os métodos atuais ou ignoram as arestas entre clientes (levando a uma passagem de mensagens incompleta) ou exigem reconstrução generativa cara/processamento de grafo completo para aproximá-las, o que não escala para atualizações dinâmicas.

O artigo formaliza um cenário denominado aprendizado de grafo colaborativo cliente-obliquo (client-oblivious), onde um servidor confiável mantém a topologia global, mas os clientes devem permanecer oblíquos à conectividade entre clientes, treinando apenas em seus subgrafos locais com informações de vizinhança incompletas.

2. Metodologia: DG-CoLearn

Os autores propõem o DG-CoLearn, um framework construído sobre o princípio unificador do processamento incremental de snapshots. Em vez de retreinar sobre snapshots completos, o sistema atualiza seletivamente apenas nós e arestas afetados por mudanças temporais, preservando representações históricas. O framework opera através de três estágios principais:

A. CoLearnPartition: Particionamento de Grafos Temporais de Dois Estágios

Para suportar o aprendizado colaborativo, o servidor emprega um algoritmo de particionamento de vértices incremental e leve.

• Atribuição Incremental: Novos nós ($\Delta V$) são atribuídos a partições existentes com base em seus vizinhanças de 1-hop e 2-hop, mantendo as atribuições históricas fixas para evitar um reparticionamento custoso.
• Objetivos de Otimização: O algoritmo otimiza conjuntamente:
  1. Minimização de Arestas Entre Clientes: Para reduzir o overhead de troca de embeddings.
  2. Balanceamento do Volume de Arestas das Partições: Para garantir cargas computacionais comparáveis.
  3. Balanceamento da Distribuição de Rótulos dos Nós: Para promover um treinamento estável.
• Estratégia: Utiliza um processo de dois estágios: um estágio primário aplicando uma restrição rígida para minimizar arestas de corte (cut edges), seguido por um estágio de refinamento secundário para balancear o volume de arestas e a diversidade de rótulos.

B. Treinamento Local Leve

Os clientes realizam o treinamento apenas no subgrafo induzido de $k$-hops ($g^k_t$) definido pelo grafo delta ($\Delta G$).

• Expansão de Subgrafo: Apenas nós dentro de $k$-hops dos nós atualizados são processados.
• Modelagem Temporal: O framework adapta a abordagem ROLAND, usando um GRU para atualizar estados de nós através de snapshots.
• Reuso de Estado: Para nós fora do subgrafo afetado, os estados ocultos históricos de $t-1$ são diretamente reutilizados, eliminando a necessidade de reprocessar regiões inalteradas. Isso reduz significativamente a computação local.

C. Troca de Conhecimento de Nós Mediada pelo Servidor

Para abordar a falta de conectividade entre clientes sem expor dados estruturais brutos, o DG-CoLearn introduz um mecanismo para reconstruir embeddings exatos de múltiplos hops.

• Base Teórica: O servidor, possuindo a matriz de adjacência global, computa os embeddings globais exatos de 1-hop e 2-hops para nós de borda usando teoremas derivados de propriedades da matriz de adjacência.
  • Correção de 1-hop: Adiciona a soma das características de 0-hop dos vizinhos entre clientes.
  • Correção de 2-hop: Adiciona embeddings de 1-hop dos vizinhos entre clientes, suas características de 0-hop e as características de 0-hop de seus vizinhos entre clientes.
• Preservação de Privacidade: Os clientes enviam apenas seus embeddings locais. O servidor computa a diferença (termos de correção) necessária para tornar os embeddings exatos e retorna apenas essas somas agregadas. Os clientes nunca veem características brutas ou identidades de vizinhos de outros clientes.
• Troca Incremental: A troca de embeddings ocorre apenas para nós no subgrafo de $k$-hops atualizado, reduzindo a complexidade de comunicação de $O(|V_t|)$ para $O(|\Delta V|)$.

3. Principais Contribuições

1. Formalização do Aprendizado Cliente-Oblíquo: O artigo define um regime de privacidade onde um coordenador confiável mantém a topologia global, mas o objetivo principal de privacidade é prevenir a inferência estrutural entre clientes, distinto dos modelos tradicionais de FL com servidor não confiável.
2. Algoritmo CoLearnPartition: Um novo algoritmo de particionamento de dois estágios adaptado para grafos dinâmicos que minimiza arestas entre clientes enquanto mantém subgrafos balanceados e diversos em rótulos, otimizando especificamente a eficiência do treinamento de GNN.
3. Esquema de Aprendizado Incremental: Uma abordagem de treinamento local leve que restringe a computação aos subgrafos afetados e reutiliza estados históricos, evitando o retreinamento de snapshot completo.
4. Troca de Embedding Consciente de Privacidade: Um mecanismo mediado pelo servidor que permite a passagem de mensagens de múltiplos hops exata entre partições sem revelar informações estruturais privadas entre clientes, provado ser insuficiente para reconstruir subgrafos privados mesmo sob colusão.

4. Resultados Experimentais

Experimentos extensos foram conduzidos em seis conjuntos de dados padrão (UCI, OTC, DBLP3/5, Reddit, AS-733) e dois benchmarks de larga escala temporais (tgbl-coin, tgbn-reddit).

• Eficiência:
  • Alcançou até 33,8× de aceleração no tempo de treinamento em comparação ao retreinamento de snapshot completo.
  • Reduziu o overhead de comunicação em 27,4× via troca incremental de embeddings.
  • Reduziu o tempo de particionamento em 51,6× em conjuntos de dados de larga escala.
• Desempenho:
  • Predição de Links: Melhorou o Mean Reciprocal Rank (MRR) em até 518% e o Mean Average Precision (MAP) em 8,27% sobre baselines centralizados.
  • Classificação de Nós: Melhorou os scores F1 em até 13,36% sobre os melhores baselines federados (ex: FedDGL).
  • Precisão Entre Clientes: Especificamente em tarefas de predição de arestas entre clientes, o DG-CoLearn melhorou o MAP em 11,7% sobre o baseline mais forte (Incremental FedGCN), demonstrando a eficácia da reconstrução exata de embeddings.
• Escalabilidade: No conjunto de dados tgbl-coin (22M de arestas), o baseline de retreinamento completo falhou em completar, enquanto o DG-CoLearn processou os dados com sucesso.

5. Significância e Alegações

O artigo argumenta que o aparente trade-off entre privacidade cliente-para-cliente e precisão preditiva no aprendizado de grafos colaborativo dinâmico não é fundamental, mas um artefato de tratar esses desafios de forma independente.

• Unindo Eficiência e Privacidade: O DG-CoLearn demonstra que, ao explorar a localidade temporal (atualizações incrementais) e a esparsidade estrutural, é possível alcançar precisão de nível centralizado mantendo estrita privacidade estrutural cliente-para-cliente e custos de computação/comunicação significativamente menores.
• Aplicabilidade Prática: O framework é projetado para cenários realistas onde um coordenador confiável existe (ex: redes financeiras), mas os clientes não podem compartilhar a topologia bruta. Ele evita os custos proibitivos do retreinamento de grafo completo e a imprecisão de suposições de grafos disjuntos.
• Robustez: Os autores alegam que seu mecanismo de troca mediado pelo servidor é provadamente insuficiente para reconstruir o subgrafo de outro cliente, mesmo se múltiplos clientes coludirem, pois os termos de correção agregados não revelam identidades de vizinhos individuais ou topologias internas.

O trabalho sugere que projetar para restrições conjuntas de eficiência e privacidade produz resultados superiores em comparação com a adaptação de métodos de aprendizado federado estáticos ou de grafos disjuntos para ambientes dinâmicos.