Resumen Técnico: Detección de Patrones de Subgrafos Cruzados entre Clientes Federados

Definición del Problema: Observabilidad Estructural y la Brecha de Equivalencia de Representación

El artículo aborda el desafío de detectar patrones complejos de subgrafos (por ejemplo, ciclos dirigidos, flujos dispersar-reunir, bicliques) dentro de grafos distribuidos entre múltiples partes (clientes) en un entorno de Aprendizaje Federado (FL). Si bien las Redes Neuronales de Grafos (GNN) son el estado del arte para tales tareas en entornos centralizados, asumen el acceso a todo el grafo. En escenarios distribuidos, cada cliente posee únicamente un subconjunto local de nodos y aristas.

Los autores identifican un problema fundamental denominado problema de observabilidad estructural. Cuando un patrón de subgrafo abarca múltiples clientes (cruzando los límites de partición), los clientes individuales poseen solo una vista truncada de la estructura. Por ejemplo, un ciclo cerrado globalmente puede aparecer como un camino abierto para un cliente local. Esto conduce a una brecha de equivalencia de representación: las representaciones de nodos calculadas por los clientes locales divergen de las que produciría un modelo centralizado porque los clientes carecen de las características y los incrustamientos de los nodos "remotos" (vecinos propiedad de otros clientes). Los enfoques estándar de FL, que dependen exclusivamente de la agregación de parámetros del modelo (por ejemplo, FedAvg), no logran cerrar esta brecha porque no pueden restaurar el contexto estructural faltante necesario para un paso de mensajes preciso.

Metodología: Marco de Intercambio de Incrustamientos por Capas

Para cerrar la brecha de equivalencia de representación sin exponer datos crudos, los autores proponen un marco de intercambio de incrustamientos por capa y por paso.

Mecanismo Central

El marco opera bajo los siguientes principios:

1. Supuesto de Subgrafo Extendido (A1): Se asume que los clientes conocen la existencia de aristas cruzadas entre clientes y las identidades de los vecinos remotos, aunque no posean las características o etiquetas crudas de los nodos remotos.
2. Supuesto de Parámetros Compartidos (A2): Todos los clientes utilizan pesos idénticos de GNN ($\Theta$) durante un paso hacia adelante. Esto puede lograrse mediante entrenamiento síncrono (Sync-SGD) o agregando parámetros en el servidor (FedAvg) antes de la inferencia.
3. Sincronización por Capas: A diferencia de trabajos anteriores que intercambian incrustamientos solo una vez por época o utilizan generación de vecinos sintéticos, este marco sincroniza representaciones de nodos intermedias en cada capa del paso hacia adelante de la GNN.
   • Después de calcular las representaciones de la capa $l$ para sus nodos propios, los clientes transmiten estas incrustaciones a otros clientes que las poseen como nodos remotos.
   • Los clientes reciben las incrustaciones de sus vecinos remotos y las utilizan para calcular la capa $l+1$.
   • Crucialmente, las características y etiquetas crudas nunca salen del cliente propietario; solo se intercambian las representaciones latentes aprendidas (incrustaciones).

Garantía Teórica

Bajo los supuestos de subgrafos extendidos y parámetros compartidos, los autores prueban una Equivalencia de Expresividad (Teorema 4.1). Demuestran que, con el intercambio por capas, la representación calculada por cualquier cliente para cualquier nodo propio es matemáticamente idéntica a la representación que una GNN centralizada calcularía sobre todo el grafo global. Esto se cumple para cualquier paso hacia adelante, ya sea durante el entrenamiento o la inferencia.

Contribuciones Clave

1. Formalización del Problema: El artículo define formalmente el "problema de observabilidad estructural" y la resultante "brecha de equivalencia de representación" en la detección de patrones de subgrafos federados.
2. Marco Novel: Introduce un protocolo de intercambio de incrustaciones por capas que restaura las capacidades de paso de mensajes centralizadas en un entorno distribuido sin compartir datos crudos.
3. Prueba Teórica: Establece que este marco recupera representaciones centralizadas exactas bajo supuestos específicos (subgrafo extendido y parámetros compartidos).
4. Aislamiento Empírico de Mecanismos: El estudio desentraña empíricamente los roles del intercambio de incrustaciones y la agregación de parámetros, mostrando que son complementarios en lugar de intercambiables.

Resultados Experimentales

Los autores evaluaron su enfoque en multigrafos dirigidos sintéticos que contenían patrones específicos (ciclos dirigidos $C_2$–$C_6$, dispersar-reunir y bicliques) particionados utilizando dos estrategias: Louvain (basada en comunidades, baja densidad cruzada entre clientes) y METIS (corte de aristas equilibrado, alta densidad cruzada entre clientes).

Hallazgos Clave:

• La Brecha Existe: El entrenamiento completamente local (sin intercambio) sufre una caída significativa en el rendimiento (el Macro PR-AUC cae de ~97% centralizado a ~70% distribuido), confirmando la brecha de equivalencia de representación.
• La Agregación de Parámetros por Sí Solas es Insuficiente: El FedAvg estándar mejora marginalmente el rendimiento sobre el entrenamiento completamente local, fallando en recuperar la información estructural perdida.
• El Intercambio de Incrustaciones Requiere Sincronización de Parámetros:
  • Añadir intercambio por capas al entrenamiento completamente local (sin parámetros sincronizados) produce ganancias mínimas, ya que las incrustaciones intercambiadas se calculan bajo modelos locales divergentes.
  • Añadir intercambio por capas a FedAvg mejora significativamente el rendimiento (recuperando ~10 puntos porcentuales), pero permanece una brecha residual debido a la deriva de parámetros dentro de una época.
  • Sync-SGD + Intercambio por Capas logra el rendimiento más alto, igualando casi el techo centralizado (94% vs 97% en Louvain), al asegurar que los parámetros estén sincronizados en cada paso.
• La Frescura Importa: El intercambio por paso propuesto supera significativamente a las líneas base de intercambio por época (obsoleto) (por ejemplo, OptimES), particularmente en escenarios de particionamiento más denso (METIS). Las incrustaciones obsoletas no logran capturar las representaciones en evolución requeridas para la detección precisa de patrones.
• Escalabilidad: Los métodos propuestos (FedAvg + LE y Sync-SGD + LE) permanecen robustos a medida que aumenta el número de clientes, mientras que los métodos completamente locales se degradan drásticamente.

Significado y Afirmaciones

El artículo afirma que su contribución principal es demostrar que la agregación de parámetros federados por sí sola no puede resolver el problema de observabilidad estructural en la detección de patrones de subgrafos. En cambio, la combinación de agregación de parámetros federados e intercambio fresco de incrustaciones por capas es necesaria para recuperar la brecha de equivalencia de representación.

Los autores enfatizan que su marco permite a los clientes calcular representaciones idénticas a las de un modelo centralizado sin violar las restricciones de privacidad respecto a características o etiquetas crudas. Señalan que, aunque la garantía teórica depende de la inferencia con lotes completos y parámetros compartidos, los resultados empíricos muestran que el enfoque es efectivo incluso con muestreo de mini-lotes, aunque permanece una pequeña brecha residual debido a la naturaleza estocástica del muestreo. El trabajo destaca que, para el aprendizaje de grafos distribuido que involucra patrones cruzados entre clientes, el momento y la frecuencia del intercambio de información (por paso vs. por época) son determinantes críticos del éxito.