Resumo Técnico: EdgeRefine

Declaração do Problema

As Redes Neurais de Grafos (GNNs) alcançaram um sucesso significativo no aprendizado a partir de dados estruturados em grafos; no entanto, sua implementação em domínios sensíveis à privacidade é dificultada pelo risco de vazamento de informações de links sensíveis. Embora a Privacidade Diferencial (DP) ofereça um framework rigoroso para proteger os dados, os métodos existentes de DP ao nível de aresta lutam para equilibrar garantias de privacidade com utilidade de dados. As abordagens atuais enfrentam três limitações primárias:

1. Incapacidade de Identificar Arestas Confiáveis: Métodos existentes frequentemente falham em distinguir arestas de alta confiança de ruído na matriz de adjacência perturbada, levando a um desempenho pobre em tarefas downstream.
2. Estratégias de Denoising Ineficazes: O denoising baseado em probabilidade muitas vezes carece de estratégias robustas para filtrar arestas ruidosas. Erros de estimativa combinados com amostragem aleatória resultam em estruturas de grafos instáveis e desempenho de classificação degradado.
3. Distorção Estrutural: A injeção de ruído frequentemente destrói a esparsidade do grafo, uma propriedade crítica de redes do mundo real. Isso leva a grafos mais densos que reduzem a eficiência computacional e distorcem o significado estrutural necessário para a passagem de mensagens de GNN.

O desafio central é desenvolver um framework que forneça privacidade diferencial estrita ao nível de aresta, mantendo a esparsidade e a integridade estrutural necessárias para o treinamento eficaz de GNNs.

Metodologia: EdgeRefine

O EdgeRefine é um framework de privacidade diferencial local (LDP) projetado para realizar o denoising de matrizes de adjacência de grafos através de um pipeline cliente-servidor. Ele emprega um processo de dois estágios para refinar o grafo ruidoso em uma estrutura adequada para tarefas downstream.

1. Perturbação no Lado do Cliente

O cliente, detendo o grafo original com a matriz de adjacência $A$, aplica Randomização de Arestas para satisfazer a $\epsilon$-privacidade de aresta.

• Mecanismo: O cliente utiliza um mecanismo de resposta aleatória na parte superior da matriz de adjacência.
• Parâmetros: Com base no orçamento de privacidade $\epsilon$, o cliente calcula as probabilidades de inversão: $p = e^\epsilon / (1 + e^\epsilon)$ para manter arestas verdadeiras e $q = 1 / (1 + e^\epsilon)$ para inverter não-arestas.
• Saída: Uma matriz de adjacência simétrica e ruidosa $\tilde{A}$ é gerada e transmitida ao servidor.

2. Denoising no Lado do Servidor

O servidor recebe $\tilde{A}$ e realiza um processo de refinamento de dois estágios para reconstruir um grafo denoisado $\hat{A}$.

Estágio 1: Estimativa de Probabilidade via Similaridade de Jaccard e Binning de Histograma

Para estimar a probabilidade de existência de arestas apesar do ruído:

• Similaridade de Jaccard: O servidor computa o coeficiente de similaridade de Jaccard para todos os pares de nós $(i, j)$ com base em seus conjuntos de vizinhança no grafo ruidoso: $J(i, j) = |N(i) \cap N(j)| / |N(i) \cup N(j)|$. Esta normalização ajuda a suprimir o impacto de perturbações aleatórias.
• Binning Baseado em Quantis: Os valores de similaridade computados são particionados em $B$ bins usando os quantis da distribuição empírica. Esta abordagem não paramétrica se adapta a diversas topologias de grafos sem necessidade de limiares manuais.
• Calibração de Probabilidade: Dentro de cada bin, a probabilidade de existência de uma aresta é estimada como a razão entre arestas observadas e o número total de pares naquele bin. Isso gera uma matriz de probabilidade calibrada $L$.

Estágio 2: Amostragem Ótima Determinística

Para converter a matriz de probabilidade em uma estrutura de grafo determinística enquanto controla a esparsidade:

• Contagem de Arestas Alvo: O servidor define um número alvo de arestas $K = \lfloor k \times E \rfloor$, onde $E$ é a contagem original de arestas e $k$ é uma taxa de amostragem global.
• Particionamento de Candidatos: As arestas são divididas em dois conjuntos baseados na matriz ruidosa $\tilde{A}$:
  • $E_{real}$: Arestas observadas ($\tilde{A}_{ij}=1$).
  • $E_{fake}$: Não-arestas ($\tilde{A}_{ij}=0$).
• Estratégia de Seleção: Usando a razão teórica de arestas verdadeiras $\rho = e^\epsilon / (1 + e^\epsilon)$ derivada do orçamento de privacidade, o servidor seleciona:
  • As top $\lfloor \rho K \rfloor$ arestas de $E_{real}$ (ordenadas por probabilidade $L_{ij}$).
  • As top $K - \lfloor \rho K \rfloor$ arestas de $E_{fake}$ (ordenadas por probabilidade $L_{ij}$).
• Saída: A união das arestas selecionadas forma a matriz de adjacência simétrica final $\hat{A}$. Esta abordagem determinística elimina a variância de amostragem e garante resultados reproduzíveis.

Principais Contribuições

1. Framework EdgeRefine: Um novo framework que equilibra privacidade e utilidade através do refinamento determinístico de arestas, abordando o trade-off no aprendizado de grafos.
2. Estimativa Baseada em Jaccard: Um método para estimar probabilidades de existência de arestas usando similaridade de Jaccard combinada com binning de histograma, que calibra precisamente as probabilidades a partir de dados ruidosos.
3. Amostragem Controlada por Taxa: Uma abordagem de amostragem determinística que controla precisamente a razão entre arestas verdadeiras e falsas e a esparsidade geral do grafo, eliminando a variância de seleção.
4. Validação Teórica e Empírica: Análise rigorosa confirmando a eficiência computacional e a conformidade estrita de privacidade, juntamente com experimentos extensos demonstrando desempenho superior sobre os baselines de estado da arte.

Resultados Experimentais

Experimentos foram conduzidos em quatro datasets do mundo real (ACM, DBLP, AMAP, Cora) utilizando três arquiteturas de GNN (GAT, GCN, GIN) através de vários orçamentos de privacidade ($\epsilon \in [0.5, 3.5]$).

• Melhoria de Acurácia: O EdgeRefine alcança acurácia comparável aos baselines sem ruído e supera significativamente os métodos existentes de preservação de privacidade.
  • Sob $\epsilon=2.5$, o EdgeRefine melhorou a acurácia de classificação de nós em 17,8% no ACM (GAT) e 19,7% no Cora (GCN) em comparação com o baseline Blink de estado da arte.
  • Na classificação de grafos (MUTAG), alcançou uma degradação de acurácia média de apenas ~5% em relação ao baseline sem ruído.
• Estabilidade: O EdgeRefine demonstra excepcional estabilidade com variância ($\sigma^2$) e coeficiente de variação (CV) significativamente menores em comparação com os competidores. Por exemplo, no ACM e DBLP, a variância foi tão baixa quanto $0.0001$.
• Esparsidade e Eficiência: O método mantém estruturas de grafos ultra-esparsas (densidade $10^{-6}$ a $10^{-5}$), que são 2 a 5 ordens de magnitude mais esparsas que outros métodos. Isso resulta em tempos de treinamento de 3 a 4 ordens de magnitude mais rápidos do que métodos como o LDPGen.
• Resiliência à Privacidade: Sob ataques de reconstrução de grafo, o EdgeRefine mantém um Erro Absoluto Relativo (RAE) consistentemente acima de 1 (média de 1.962 no Cora), indicando forte resistência à inferência de arestas.
• Índice de Equilíbrio Privacidade-Utilidade (PUBI): O EdgeRefine alcançou o maior PUBI médio (0.9386) em todas as combinações, superando o Blink-hybrid (0.7101) e o Blink-hard (0.6902), demonstrando sua capacidade de manter a utilidade conforme os requisitos de privacidade relaxam.

Significância

O artigo postula que o EdgeRefine aborda a barreira fundamental do equilíbrio privacidade-utilidade no aprendizado de grafos. Ao repensar o processo de denoising através do refinamento adaptativo de arestas, o framework permite a implementação prática de GNNs em cenários sensíveis à privacidade sem sacrificar a integridade estrutural necessária para a passagem de mensagens eficaz. Os autores afirmam que o EdgeRefine fornece uma solução robusta que é computacionalmente eficiente, teoricamente sólida e empiricamente superior aos métodos atuais de estado da arte, tornando-o um candidato viável para análise de grafos preservando a privacidade no mundo real.