Resumen Técnico: Condensación de Grafos Atribuidos a Texto mediante Selección de Texto y Coincidencia de Atributos

Declaración del Problema

Los Grafos Atribuidos a Texto (TAGs, por sus siglas en inglés) integran la topología de grafos con descripciones textuales de los nodos, permitiendo tareas potentes como la clasificación zero-shot y la clasificación de artículos mediante el entrenamiento conjunto de Redes Neuronales de Grafos (GNNs) y Modelos de Lenguaje (LMs). Sin embargo, este entrenamiento de modalidad dual es computacionalmente costoso, requiriendo una cantidad significativa de memoria y tiempo, particularmente en conjuntos de datos a gran escala.

Si bien la Condensación de Conjuntos de Datos ofrece una solución al comprimir grandes conjuntos de datos en otros más pequeños y representativos, los métodos existentes no abordan los TAGs de manera efectiva:

1. Condensación de Grafos Tradicional (ej. GCond): Estos métodos típicamente comprimen solo la modalidad de grafo, ignorando la rica información textual. Además, a menudo dependen de la supervisión de etiquetas, lo cual es incompatible con los escenarios de TAG donde las etiquetas de verdad fundamental (ground-truth) son escasas o costosas de obtener.
2. Condensación Multimodal (ej. MTT-VL): Los métodos basados en el Emparejamiento de Trayectorias de Entrenamiento (MTT) intentan comprimir tanto la imagen como el texto. Sin embargo, al aplicarse a los TAGs, enfrentan dos problemas críticos:
   • Texto Ilegible: El MTT optimiza el texto en un espacio de embeddings continuo mediante el descenso de gradiente. Esto produce vectores de embedding ilegibles que son incompatibles con los tokenizadores y los modelos de lenguaje descendentes.
   • Entrenamiento Inestable: En los TAGs, los modelos profesor suelen entrenarse mediante aprendizaje contrastivo. La pérdida en el aprendizaje contrastivo depende de todo el lote (batch), lo que genera una alta varianza en las trayectorias de entrenamiento. Esta inestabilidad impide que el modelo estudiante coincida con la trayectoria del profesor, resultando en una convergencia subóptima.

La pregunta central de investigación es: ¿Es posible diseñar un método de condensación de TAG que para escenarios sin etiquetas, genere un texto comprimido discreto y legible, y logre una convergencia estable?

Metodología: TAGSAM

Los autores proponen TAGSAM, un marco de condensación que consta de dos componentes clave: Selección de Texto de Subgrafos y Coincidencia de Similitud de Atributos.

1. Selección de Texto de Subgrafos

En lugar de optimizar embeddings continuos, TAGSAM selecciona y fusiona fragmentos de texto representativos del espacio discreto original para formar textos comprimidos concisos y legibles.

• Proceso:
  1. Muestreo de Subgrafos: Se muestrean aleatoriamente $M$ subgrafos del grafo original utilizando Búsqueda en Anchura (BFS).
  2. Fragmentación de Texto y Puntuación: Se divide el texto dentro de cada subgrafo en fragmentos (chunks). Se calcula una Puntuación Representativa (RS) para cada fragmento basada en la Información Mutua por Fragmento (CMI). La RS maximiza la cobertura de información del subgrafo mientras penaliza la redundancia.
  3. Selección y Fusión: Un algoritmo voraz (greedy) selecciona secuencialmente los top-$k$ fragmentos con el mayor RS para formar un texto comprimido $\hat{T}_i$.
• Garantía Teórica: Los autores demuestran que esta selección voraz aproxima la solución óptima dentro de un factor de $(1 - 1/e)$.

2. Coincidencia de Similitud de Atributos (ASM)

Para comprimir la estructura del grafo y las características de los nodos, TAGSAM reemplaza el enfoque inestable de MTT con la Coincidencia de Similitud de Atributos.

• Mecanismo: En lugar de alinear trayectorias completas de actualización de parámetros (que sufren de alta varianza), ASM alinea las matrices de similitud de atributos entre los modelos profesor y estudiante.
  • La matriz de similitud $S_M$ se calcula como el producto de los embeddings de grafo y los embeddings de texto para todos los pares de nodos.
  • La pérdida de coincidencia minimiza la discrepancia entre la matriz de similitud del estudiante y la del profesor, utilizando un softmax por fila antes de la Entropía Cruzada Binaria (sBCE) para asegurar gradientes más suaves.
• Justificación Teórica: Los autores demuestran que en el aprendizaje contrastivo, la similitud óptima entre atributos corresponde a su Información Mutua Puntual (PMI). A diferencia de las trayectorias completas, que son sensibles a matrices de rotación y escala arbitrarias en el espacio del codificador, la matriz de similitud es inherentemente estable e invariante a estas transformaciones.
• Eficiencia: A diferencia de MTT, que requiere entrenar múltiples modelos profesor (típicamente 15) para capturar trayectorias diversas, ASM requiere un solo modelo profesor, reduciendo significativamente el costo computacional.

Contribuciones Clave

1. Identificación del Problema: Los autores identifican que la condensación de grafos tradicional no es adecuada para los TAGs debido a su negligencia del texto y dependencia de etiquetas, mientras que los métodos multimodales existentes fallan debido a salidas de texto ilegibles e inestabilidad de entrenamiento causada por trayectorias contrastivas de alta varianza.
2. Marco Novedoso (TAGSAM):
   • Selección de Texto de Subgrafos: Un método para comprimir texto en el espacio discreto seleccionando fragmentos representativos mediante información mutua, asegurando que la salida sea legible y compatible con los tokenizadores.
   • Coincidencia de Similitud de Atributos: Una técnica de condensación robusta que alinea matrices de similitud de atributos estables en lugar de volátiles trayectorias de entrenamiento, mejorando la estabilidad de la convergencia.
3. Análisis Teórico: El artículo proporciona pruebas teóricas que muestran que la selección de texto voraz aproxima la solución óptima y que la similitud de atributos sirve como una estimación estable de la PMI, justificando la robustez de la estrategia de coincidencia.

Resultados Experimentales

Los autores evaluaron TAGSAM en cinco conjuntos de datos (Cora, Photo, Computer, Arxiv, Products) que van desde 2.7K hasta 2.4M de nodos, comparándolo contra seis líneas base de vanguardia (Random, Herding, K-Center, GCond*, MTT-TAG, MTT-KNN).

• Precisión de Clasificación: TAGSAM superó consistentemente a todas las líneas base. En promedio, mejoró la precisión en un 4.9% respecto a la mejor línea base (MTT-TAG). Notablemente, logró una precisión competitiva incluso al condensar el conjunto de datos a solo el 1% de su tamaño original.
• Predicción de Enlaces: TAGSAM logró mejoras significativas en el AUC (hasta un 4.1% sobre Random y un 2.1% sobre MTT-TAG), lo que indica una mejor retención de la información estructural.
• Generalización de Arquitectura Cruzada: Los modelos entrenados con datos condensados por TAGSAM mantuvieron una mayor precisión cuando se probaron con diferentes arquitecturas de codificador (ej. GCN, SAGE, Cheby) en comparación con las líneas base.
• Eficiencia: Aunque la condensación incurre en un costo único, TAGSAM acelera significativamente las búsquedas de hiperparámetros descendentes. Debido al requerimiento de un solo profesor, TAGSAM es más escalable que los métodos basados en MTT para grafos grandes.
• Estudios de Ablación: Los experimentos confirmaron que tanto la selección de texto de subgrafos como la coincidencia de similitud de atributos son esenciales, siendo la combinación la que produce un rendimiento superior sobre las variantes que utilizan selección aleatoria o coincidencia de trayectoria.

Significancia

El artículo afirma que TAGSAM hace factible el pre-entrenamiento eficiente en Grafos Atribuidos a Texto a gran escala. Al abordar los desafíos específicos de la compresión de texto discreto y la inestabilidad del aprendizaje contrastivo, TAGSAM permite la creación de conjuntos de datos altamente comprimidos que preservan la información conjunta necesaria para una clasificación zero-shot efectiva y otras tareas de TAG, sin depender de una costosa supervisión de etiquetas.