Graph Reduction in Multirelational Networks: A Spreading-Oriented Reduction Benchmark

Resumen Técnico: Reducción de Grafos en Redes Multirelacionales (SORB)

Planteamiento del Problema
Las redes del mundo real suelen ser incompletas, ruidosas y evolucionar dinámicamente, lo que hace que su análisis directo sea computacionalmente exigente. Aunque la Maximización de la Influencia (IM, por sus siglas en inglés)—la tarea de identificar nodos semilla para maximizar la propagación de información—es ampliamente estudiada, el impacto de la reducción de grafos (dispersión y agrupación/coarsening) como paso de preprocesamiento en la precisión de la IM sigue siendo poco explorado. Los benchmarks existentes suelen centrarse en grafos de una sola relación o en la clasificación de nodos, fallando al no abordar cómo las estrategias de reducción afectan los procesos de propagación en sistemas multirelacionales complejos. Además, la interacción entre la reducción de grafos y las propiedades estructurales específicas de las redes multicapa no ha sido examinada en gran medida.

Metodología: El Benchmark de Reducción Orientado a la Propagación (SORB)
Los autores presentan SORB, un marco de trabajo de código abierto y estandarizado diseñado para evaluar sistemáticamente los modelos de IM a través de diversos entornos de tareas, integrando la reducción de grafos directamente en el flujo de evaluación.

• Arquitectura del Pipeline: El flujo de trabajo consta de tres etapas:

  1. Módulo de Reducción: Genera versiones reducidas de las redes de entrada utilizando una cuadrícula de tasas de reducción ($r \in \{0.01, \dots, 0.9\}$) y métodos.
  2. Módulo de Predicción: Ejecuta modelos de selección de semillas tanto en los grafos originales como en los reducidos.
  3. Difusión y Evaluación: Ejecuta simulaciones del Modelo de Cascada Independiente Multicapa (MICM) en las redes originales utilizando los conjuntos de semillas predichos de los grafos reducidos. Esto asegura que las métricas de rendimiento reflejen el verdadero potencial de propagación en los datos completos, aislando el efecto de la reducción en la calidad de la predicción.

• Conjuntos de Datos: El benchmark utiliza siete redes del mundo real, incluyendo grafos homogéneos (WikiCS, Amazon-CS) y redes multicapa (Freebase, IMDB, FinDKG, arxiv, timik).

• Estrategia de Aplanamiento (Flattening): Dado que la mayoría de los algoritmos de reducción operan sobre grafos homogéneos, las redes multicapa se transforman en multígrafos de una sola capa mediante un proceso de "aplanamiento". Esto agrega las relaciones entre capas en un único conjunto de aristas, preservando la agregación de actores pero introduciendo la posibilidad de duplicación de aristas. Los autores tratan esto como un compromiso pragmático para probar los algoritmos existentes, reconociéndolo como una operación estructural con costos inherentes.

• Métodos de Reducción: El estudio evalúa cinco técnicas de dispersión (Random, LocalDegree, Jaccard similarity, TSpanner, ForestFire) y dos técnicas de agrupación/coarsening (VariationNeighborhoods, AffinityGs).

• Modelos de IM: Se prueban seis modelos de selección de semillas, que van desde heurísticas de baja complejidad (Degree Centrality, Degree Discount, Neighbourhood Size) hasta modelos de aprendizaje de alta complejidad (ts-net) y extensiones multicapa (v-rnk-m).

• Métricas de Evaluación:

  • Gain@k: Mide la calidad de los conjuntos de semillas seleccionados de tamaño $k$ (un solo nodo o porcentaje de actores).
  • $AUC_{cutoff}$: Mide el acuerdo entre el ranking de influencia de la verdad de terreno (ground-truth) y el ranking predicho dentro del 80% superior de los actores.

Contribuciones Clave y Hallazgos
El estudio aborda cuatro preguntas de investigación relativas al impacto de la reducción en el rendimiento de la IM, el papel de las tasas de reducción, la consistencia entre redes y el uso de recursos computacionales.

1. Impacto en la Calidad del Conjunto de Semillas (Gain@k):

   • Dispersión (Sparsification): En redes de una sola capa (homogéneas), la dispersión preserva la calidad del conjunto de semillas en todos los tamaños examinados. El rendimiento medio se mantiene en los niveles de la línea base y la varianza suele reducirse.
   • Agrupación (Coarsening): En el subconjunto de redes donde la agrupación fue computacionalmente factible, resultó en solo un declive marginal en el Gain@k, acompañado de una mejora en la estabilidad de los resultados (menor varianza).
   • Contexto Multicapa: Las redes multicapa aplanadas exhiben una degradación sistemática del ranking independientemente de la estrategia de reducción, lo que sugiere que los métodos de reducción actuales luchan con la complejidad estructural introducida por el aplanamiento.

2. Papel de la Tasa de Reducción ($r$) vs. Estrategia:

   • No existe una relación monótona estadísticamente significativa entre la tasa de reducción nominal $r$ y la degradación del rendimiento downstream ($AUC_{cutoff}$).
   • La degradación es impulsada principalmente por la elección de la estrategia de reducción más que por el porcentaje de aristas eliminadas. Por ejemplo, ForestFire se comporta como una función escalón (manteniendo la estructura hasta un umbral), mientras que TSpanner exhibe una relación invertida con $r$ en algunos contextos.
   • La sensibilidad estructural es alta; incluso la eliminación aleatoria de aristas induce cambios de ranking estadísticamente significativos.

3. Consistencia entre Redes:

   • Las redes homogéneas muestran un comportamiento consistente y estable bajo la reducción.
   • Las redes heterogéneas (multicapa) presentan un desafío distinto. La transformación de aplanamiento introduce una sobrecarga (duplicación de aristas) que puede contrarrestar el ahorro de memoria en tasas de reducción bajas ($r \le 0.5$), particularmente para modelos basados en aprendizaje como ts-net.

4. Recursos Computacionales:

   • La dispersión genera reducciones medibles en el tiempo de inferencia y el consumo de memoria, notablemente para los modelos más pesados (v-rnk-m y ts-net).
   • Sin embargo, para grafos heterogéneos, el paso de aplanamiento puede aumentar los requisitos de memoria para ts-net en tasas de reducción bajas porque el grafo resultante de una sola capa contiene estrictamente más aristas que cualquier capa individual.

Significancia y Reivindicaciones
Los autores afirman que SORB cambia el enfoque de probar algoritmos de IM de forma aislada a cuantificar cómo la reducción de grafos altera el rendimiento predictivo bajo condiciones realistas. La principal significancia del trabajo radica en demostrar que:

• La reducción de grafos es un paso de preprocesamiento viable para la IM, particularmente la dispersión en redes homogéneas, ofreciendo ahorros de recursos con una pérdida mínima de rendimiento.
• La elección de la estrategia de reducción es más crítica que la tasa de reducción en sí misma.
• Los métodos de reducción actuales no son adecuados para redes multicapa cuando se aplican mediante un pipeline de aplanar-luego-reducir, lo que resalta una brecha en la literatura para algoritmos de reducción dedicados a redes multicapa.

El artículo concluye que, si bien la dispersión ofrece potencial para un análisis eficiente, la falta de enfoques dedicados para grafos heterogéneos sigue siendo un desafío. Los autores posicionan a SORB como una base para trabajos futuros que incorporen la condensación de grafos y métodos diseñados específicamente para estructuras de redes heterogéneas.