Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction

Título: Embeddings Espectrais Vazam a Topologia do Grafo: Teoria, Benchmark e Reconstrução Adaptativa

1. O Problema

O artigo aborda uma lacuna crítica entre os benchmarks ideais de aprendizado em grafos e a realidade das aplicações modernas, como o Aprendizado Federado em Grafos (FGL) e sistemas sensíveis à privacidade.

• A Falácia dos Benchmarks Atuais: A maioria dos benchmarks (como OGB) assume que o algoritmo tem acesso centralizado e completo ao grafo inteiro. Na prática, os dados são fragmentados, distribuídos entre clientes e frequentemente protegidos por filtros de privacidade que ocultam a estrutura global.
• O Canal de Vazamento: Em vez de compartilhar dados brutos (matriz de adjacência), os sistemas frequentemente compartilham embeddings espectrais (vetores próprios truncados) ou resumos estruturais. O artigo demonstra que esses embeddings, mesmo sendo parciais e ruidosos, contêm informações suficientes para que um adversário passivo (que apenas observa os dados compartilhados) reconstrua a topologia global do grafo.
• Desafios Específicos: A reconstrução é dificultada por:
  1. Truncamento Espectral: Apenas os $k$ menores autovalores são compartilhados ($k \ll n$).
  2. Ruído: Adição de ruído gaussiano para privacidade.
  3. Ambiguidade: Os vetores próprios são definidos apenas até uma transformação ortogonal (sinal/permutação/rotação), exigindo alinhamento geométrico complexo.

2. Metodologia e Contribuições Principais

Os autores propõem um framework unificado composto por três pilares:

A. LoGraB (Local Graph Benchmark)

Um novo benchmark projetado para operacionalizar o cenário de grafos fragmentados e medir a robustez de modelos e a eficácia de ataques de reconstrução.

• Estratégias de Decomposição: O grafo global é dividido em "patches" (fragmentos) locais usando três estratégias:
  1. Patches centrados em nós (d-hop): Vizinhos dentro de um raio $d$.
  2. Particionamento baseado em clusters: Simula silos de dados naturais com sobreposição controlada.
  3. Patches aleatórios: Simula coleta de dados caótica.
• Parâmetros Controláveis: O benchmark permite variar sistematicamente:
  • $d$: Raio de vizinhança (localidade).
  • $k$: Número de vetores próprios retidos (qualidade espectral).
  • $\sigma$: Nível de ruído gaussiano.
  • $p$: Taxa de cobertura (fração de nós observados).
• Tarefas e Métricas:
  1. Reconstrução de Grafo: Recuperar a topologia global a partir de patches. Introduz a métrica Island Cohesion (Coesão da Ilha) para avaliar se as componentes reconstruídas mantêm a integridade estrutural interna, não apenas a precisão de arestas isoladas.
  2. Classificação de Nós Localizada: Aprender representações úteis apenas com a visão local.
  3. Predição de Links Inter-fragmento: Prever conexões entre nós que nunca estiveram no mesmo patch.

B. AFR (Adaptive Fidelity-driven Reconstruction)

Um algoritmo inovador para reconstruir grafos a partir de fragmentos espectrais ruidosos e heterogêneos. Diferente de métodos anteriores que assumem qualidade uniforme, o AFR adapta-se à confiabilidade de cada patch.

• Pipeline de Três Estágios:
  1. Reconstrução Local e Pontuação de Fidelidade:
     • Reconstrói a matriz de adjacência local usando o Kernel de Calor (Heat Kernel) e limiarização.
     • Calcula um Score de Fidelidade ($s_v$) combinando:
       • Razão Gap-Truncamento ($\rho_v$): Medida de estabilidade espectral baseada no gap entre autovalores.
       • Entropia Estrutural ($E_v$): Medida de singularidade da estrutura do patch (evita patches simétricos que dificultam o alinhamento).
  2. Montagem Adaptativa de Ilhas:
     • Prioriza a montagem de patches de alta fidelidade.
     • Usa RANSAC-Procrustes para alinhar patches sobrepostos, sendo robusto a outliers e correspondências errôneas.
     • Critério de costura adaptativo: patches de baixa fidelidade exigem sobreposições maiores para serem costurados.
  3. Refinamento Global:
     • Bundle Adjustment: Otimização global para corrigir erros de alinhamento acumulados.
     • Inferência de Links Inter-ilha: Usa um mecanismo de "votação cruzada" baseado na co-ocorrência de nós nos patches originais para inferir arestas entre ilhas desconectadas.

C. Análise Teórica

• Proposição de Vazamento Espectral (Spectral Leakage Proposition): Prova teórica (heurística bayesiana) de que, sob uma condição de "gap espectral", a recuperação do grafo em tempo polinomial é possível se o número de vetores próprios compartilhados ($k$) superar um certo limiar $k^*$.
• Garantias Locais do AFR: O artigo fornece garantias formais (teoremas e lemas) para os componentes do AFR, incluindo limites de perturbação espectral (Davis-Kahan), recuperação exata de arestas via Kernel de Calor e limites de erro de alinhamento.

3. Resultados Experimentais

Os experimentos foram realizados em 9 conjuntos de dados (redes de citação, sociais, biológicas, moleculares e visão computacional) com 486 cenários de fragmentação.

• Reconstrução de Grafos (Task 1):
  • O AFR superou consistentemente as baselines (incluindo Eigen-sync, GAE, VGAE, PointNetLK) em 7 de 9 conjuntos de dados, alcançando o melhor F1 na maioria dos cenários.
  • Em grandes grafos (ex: ogbn-arXiv), o AFR manteve uma vantagem de mais de 10 pontos de F1 sobre a baseline mais próxima.
  • O AFR demonstrou maior resiliência ao ruído; quando o ruído aumentou, a performance do AFR degradou-se menos do que a dos métodos baseados em alinhamento rígido ou modelos generativos.
• Classificação de Nós (Task 2):
  • A estrutura do patch local (raio $d$ e cobertura $p$) foi o fator mais determinante para o desempenho. Aumentar o raio de 1-hop para 2-hop melhorou drasticamente a precisão, independentemente da arquitetura GNN.
  • Modelos baseados em Transformers (ex: Graphormer) performaram excepcionalmente bem em grafos densos, mas modelos mais simples (ex: GraphSAGE) foram mais robustos em cenários de fragmentação extrema.
• Resiliência à Privacidade (DP):
  • Sob privacidade diferencial (DP) baseada em embeddings ($\epsilon, \delta$), o AFR manteve 75% de sua performance (F1) em $\epsilon = 2$, enquanto outras baselines caíram para cerca de 60%.
  • O estudo revela uma tensão: para degradar significativamente o ataque de reconstrução (AFR), é necessário sacrificar drasticamente a utilidade do modelo (acurácia de classificação), especialmente em $\epsilon \le 2$.

4. Significado e Conclusão

• Alerta de Segurança: O trabalho demonstra que embeddings espectrais, frequentemente usados em aprendizado federado para preservar privacidade, não são seguros por si só. Eles vazam informações topológicas suficientes para reconstruir a estrutura do grafo, mesmo na presença de ruído e truncamento.
• Novo Paradigma de Avaliação: O LoGraB estabelece um novo padrão para avaliar algoritmos de grafos em cenários realistas de dados fragmentados, expondo fraquezas de arquiteturas que funcionam bem apenas em dados centralizados.
• Solução Robusta: O AFR prova que a reconstrução de grafos é viável e robusta quando se leva em conta a heterogeneidade da qualidade dos dados, utilizando uma abordagem adaptativa que prioriza a fidelidade dos fragmentos.
• Implicações Futuras: O artigo sugere que defesas de privacidade futuras devem ir além da adição simples de ruído aos embeddings, focando em transformar as propriedades geométricas dos dados compartilhados para quebrar a viabilidade de alinhamento e reconstrução.

Em resumo, o artigo fornece tanto a prova teórica quanto a evidência empírica de que a topologia de grafos é vulnerável a vazamentos via embeddings espectrais, oferecendo ao mesmo tempo um benchmark rigoroso e um algoritmo de ataque (e defesa) sofisticado para estudar esse fenômeno.