Resumo Técnico: Detecção de Padrões de Subgrafos Federados entre Clientes

Definição do Problema: Observabilidade Estrutural e a Lacuna de Equivalência de Representação

O artigo aborda o desafio de detectar padrões complexos de subgrafos (por exemplo, ciclos direcionados, fluxos de dispersão-agrupamento, bicliques) dentro de grafos distribuídos entre múltiplas partes (clientes) em um cenário de Aprendizado Federado (FL). Embora as Redes Neurais de Grafos (GNNs) sejam o estado da arte para tais tarefas em ambientes centralizados, elas assumem o acesso ao grafo inteiro. Em cenários distribuídos, cada cliente possui apenas um subconjunto local de nós e arestas.

Os autores identificam uma questão fundamental denominada problema de observabilidade estrutural. Quando um padrão de subgrafo abrange múltiplos clientes (cruzando limites de partição), os clientes individuais possuem apenas uma visão truncada da estrutura. Por exemplo, um ciclo globalmente fechado pode aparecer como um caminho aberto para um cliente local. Isso leva a uma lacuna de equivalência de representação: as representações de nós computadas por clientes locais divergem daquelas que um modelo centralizado produziria, porque os clientes carecem dos recursos e embeddings de nós "remotos" (vizinhos pertencentes a outros clientes). Abordagens FL padrão, que dependem exclusivamente da agregação de parâmetros do modelo (por exemplo, FedAvg), falham em fechar essa lacuna porque não conseguem restaurar o contexto estrutural ausente necessário para a passagem de mensagens precisa.

Metodologia: Framework de Troca de Embeddings por Camada

Para superar a lacuna de equivalência de representação sem expor dados brutos, os autores propõem um framework de troca de embeddings por passo e por camada.

Mecanismo Central

O framework opera sob os seguintes princípios:

1. Hipótese de Subgrafo Estendido (A1): Assume-se que os clientes conhecem a existência de arestas entre clientes e as identidades dos vizinhos remotos, embora não possuam os recursos ou rótulos brutos dos nós remotos.
2. Hipótese de Parâmetros Compartilhados (A2): Todos os clientes utilizam pesos idênticos de GNN ($\Theta$) durante uma passagem forward. Isso pode ser alcançado via treinamento síncrono (Sync-SGD) ou pela agregação de parâmetros no servidor (FedAvg) antes da inferência.
3. Sincronização por Camada: Diferentemente de trabalhos anteriores que trocam embeddings apenas uma vez por época ou usam geração de vizinhos sintéticos, este framework sincroniza representações de nós intermediárias em cada camada da passagem forward da GNN.
   • Após computar as representações da camada $l$ para seus nós próprios, os clientes transmitem esses embeddings para outros clientes que os possuem como nós remotos.
   • Os clientes recebem os embeddings de seus vizinhos remotos e os utilizam para computar a camada $l+1$.
   • Crucialmente, recursos e rótulos brutos nunca deixam o cliente proprietário; apenas as representações latentes aprendidas (embeddings) são trocadas.

Garantia Teórica

Sob as hipóteses de subgrafos estendidos e parâmetros compartilhados, os autores provam uma Equivalência de Expressividade (Teorema 4.1). Eles demonstram que, com a troca por camada, a representação computada por qualquer cliente para qualquer nó próprio é matematicamente idêntica à representação que uma GNN centralizada computaria sobre o grafo global completo. Isso vale para qualquer passagem forward, seja durante o treinamento ou a inferência.

Contribuições Principais

1. Formalização do Problema: O artigo define formalmente o "problema de observabilidade estrutural" e a resultante "lacuna de equivalência de representação" na detecção federada de padrões de subgrafos.
2. Framework Inovador: Introduz um protocolo de troca de embeddings por camada que restaura capacidades de passagem de mensagens centralizadas em um ambiente distribuído sem compartilhar dados brutos.
3. Prova Teórica: Estabelece que este framework recupera representações centralizadas exatas sob hipóteses específicas (subgrafo estendido e parâmetros compartilhados).
4. Isolamento Empírico de Mecanismos: O estudo desentrelaça empiricamente os papéis da troca de embeddings e da agregação de parâmetros, mostrando que são complementares e não intercambiáveis.

Resultados Experimentais

Os autores avaliaram sua abordagem em multigrafos direcionados sintéticos contendo padrões específicos (ciclos direcionados $C_2$–$C_6$, dispersão-agrupamento e bicliques) particionados usando duas estratégias: Louvain (baseada em comunidades, baixa densidade entre clientes) e METIS (corte de arestas balanceado, alta densidade entre clientes).

Principais Descobertas:

• A Lacuna Existe: O treinamento totalmente local (sem troca) sofre uma queda significativa de desempenho (o Macro PR-AUC cai de ~97% centralizado para ~70% distribuído), confirmando a lacuna de equivalência de representação.
• A Agregação de Parâmetros Sozinha é Insuficiente: O FedAvg padrão melhora marginalmente o desempenho sobre o treinamento totalmente local, falhando em recuperar a informação estrutural perdida.
• A Troca de Embeddings Requer Sincronização de Parâmetros:
  • Adicionar troca por camada ao treinamento totalmente local (sem parâmetros sincronizados) produz ganhos mínimos, pois os embeddings trocados são computados sob modelos locais divergentes.
  • Adicionar troca por camada ao FedAvg melhora significativamente o desempenho (recuperando ~10 pontos percentuais), mas uma lacuna residual permanece devido ao desvio de parâmetros dentro de uma época.
  • Sync-SGD + Troca por Camada alcança o desempenho mais alto, quase igualando o teto centralizado (94% vs 97% no Louvain), ao garantir que os parâmetros sejam sincronizados a cada passo.
• Atualidade Importa: A troca por passo proposta supera significativamente as bases de troca por época (desatualizada) (por exemplo, OptimES), particularmente em cenários de particionamento mais denso (METIS). Embeddings desatualizados falham em capturar as representações em evolução necessárias para a detecção precisa de padrões.
• Escalabilidade: Os métodos propostos (FedAvg + LE e Sync-SGD + LE) permanecem robustos conforme o número de clientes aumenta, enquanto os métodos totalmente locais degradam-se drasticamente.

Significado e Alegações

O artigo alega que sua contribuição primária é demonstrar que apenas a agregação federada de parâmetros não pode resolver o problema de observabilidade estrutural na detecção de padrões de subgrafos. Em vez disso, a combinação de agregação federada de parâmetros e troca de embeddings fresca e por camada é necessária para recuperar a lacuna de equivalência de representação.

Os autores enfatizam que seu framework permite que os clientes computem representações idênticas a um modelo centralizado sem violar restrições de privacidade relacionadas a recursos ou rótulos brutos. Eles notam que, embora a garantia teórica dependa de inferência com lote completo e parâmetros compartilhados, os resultados empíricos mostram que a abordagem é eficaz mesmo com amostragem de mini-lotes, embora uma pequena lacuna residual permaneça devido à natureza estocástica da amostragem. O trabalho destaca que, para aprendizado de grafos distribuído envolvendo padrões entre clientes, o timing e a frequência da troca de informações (por passo vs. por época) são determinantes críticos do sucesso.