Resumen Técnico: AutoGrable

Planteamiento del Problema

El aprendizaje en grafos, particularmente mediante Redes Neuronales de Grafos de Paso de Mensajes (MPNNs), presupone la existencia de una estructura de grafo. Sin embargo, los formatos de datos dominantes en el aprendizaje automático aplicado —tablas únicas y bases de datos relacionales vinculadas por claves foráneas— no poseen inherentemente una representación de grafo. Aplicar GNNs a tales datos requiere una fase de construcción donde se debe decidir qué entidades se convierten en nodos, cuáles se conectan y a través de qué relaciones.

Los enfoques actuales para este problema son limitados:

1. Aprender un grafo: Inferir una adyacencia suave a partir de las características junto con el modelo. Esto asume que la estructura implica proximidad geométrica, lo cual las tablas no proporcionan (su relación nativa es el valor categórico compartido).
2. Construir un grafo: Fijar un esqueleto de esquema o puntuar atributos basándose en la precisión de un modelo entrenado. Esto es circular (requiere una ejecución de entrenamiento por cada candidato), computacionalmente costoso y no explica por qué una construcción específica ayuda al aprendiz.

El artículo aborda la pregunta fundamental: Cuando un grafo no es dado, ¿qué constituye un "buen" grafo para una tabla y cómo puede construirse sin entrenar un modelo?

Metodología

Fundamento Teórico: 1-WL y Alineación de Particiones

Los autores fundamentan su enfoque en los límites del poder expresivo de las MPNNs, que están acotadas por la prueba de Weisfeiler–Leman de una dimensión (1-WL o refinamiento de color). Para una GNN, un grafo construido a partir de una tabla efectivamente clasifica las filas de la tabla en clases de color 1-WL. El modelo no puede distinguir entre filas asignadas al mismo color.

Por lo tanto, una construcción de grafo es "buena" para una tarea si la partición inducida de las filas se alinea con las etiquetas de la tarea:

• Las filas con etiquetas diferentes deben caer en clases de color distintas.
• Las filas con la misma etiqueta no deben dividirse innecesariamente (evitando la sobrefragmentación).

Este criterio de alineación puede evaluarse antes de cualquier entrenamiento del modelo.

El Puntaje de Alineación ($J$)

Para operacionalizar este criterio, el artículo propone un puntaje de entrenamiento libre $J$ para un subconjunto candidato de atributos $S$. El puntaje equilibra dos factores contrapuestos:

1. Ganancia Predictiva (Alineación): Medida por la pérdida de validación de un "predictor de bloque" simple ($\hat{h}_S$) que es constante en las celdas definidas por $S$. Este predictor utiliza la distribución de etiquetas empírica de las filas de entrenamiento dentro de cada celda.
2. Penalización por Fragmentación ($\Omega$): Una medida de qué tan escasamente están pobladas las celdas. Se define como $\frac{1}{n_{tr}} \sum \sqrt{N_{S,u}}$, donde $N_{S,u}$ es el número de filas en una celda. La alta fragmentación (muchas celdas pequeñas) aumenta el error de estimación y el riesgo de memorización.

El puntaje se formula como:
$$J(\pi_S) = \widehat{\text{Risk}}_{\text{val}}(\hat{h}_S) + \lambda \Omega(T_{tr}, \pi_S)$$
donde $\lambda \geq 0$ controla la compensación. Minimizar $J$ selecciona la partición que mejor se alinea con las etiquetas manteniendo un soporte suficiente para la generalización. El análisis teórico muestra que $\Omega$ acota el error de estimación en un límite de generalización para clasificadores constantes por celda.

Algoritmo: AUTOGRABLE

Los autores introducen AUTOGRABLE, un algoritmo que busca el subconjunto de atributos óptimo $S^*$ para minimizar $J$.

• Estrategia de Búsqueda: Dado que encontrar el minimizador exacto es NP-completo (reducible al problema de Cobertura de Pruebas o Test Cover), AUTOGRABLE emplea una búsqueda local codiciosa (Selección de Columnas Estructurales, SCS).
• Direcciones: Soporta búsqueda hacia adelante (partiendo de un conjunto vacío) y búsqueda hacia atrás (partiendo del conjunto completo).
• Codificación: Soporta dos firmas para la puntuación:
  • Codificación de valor: Puntajes basados en valores específicos rastreando la etiqueta.
  • Codificación de frecuencia: Puntajes basados en el patrón de multiplicidad (qué tan raro o compartido es un valor), independiente de la identidad del valor específico.
• Extensión Relacional: Para esquemas de múltiples tablas, el algoritmo materializa una tabla aplanada mediante uniones a la izquierda (left joins) a lo largo de rutas de claves foráneas (colapsando duplicados y ponderando filas) antes de aplicar la lógica de selección. Las columnas seleccionadas se expanden luego en un grafo de incidencia (un grafo bipartito de filas y nodos de valores).

Contribuciones Clave

1. La Alineación como Criterio: El artículo establece que, para aprendices limitados por 1-WL, la construcción de un grafo es equivalente al diseño de una partición de filas. Una construcción es buena si esta partición se alinea con las etiquetas, una propiedad que puede verificarse sin entrenar una GNN.
2. Puntaje Libre de Entrenamiento: Un nuevo puntaje $J$ que evalúa grafos candidatos basándose únicamente en la partición de filas inducida y un predictor de bloque simple, penalizando la fragmentación. Esto evita la circularidad y el costo de entrenar un modelo para cada candidato.
3. AUTOGRABLE: Un algoritmo codicioso y práctico que selecciona el subconjunto de columnas óptimo para construir un grafo de incidencia. Se aplica tanto a tablas únicas como a esquemas de claves foráneas y puede declinar explícitamente la construcción de un grafo (devolviendo un grafo trivial) si ninguna construcción mejora el puntaje.

Resultados Experimentales

Los autores evalúan AUTOGRABLE en tres preguntas de investigación:

1. Recuperación de la Verdad de Terreno (Tareas Controladas): En tareas sintéticas usando el conjunto de datos Adult donde las etiquetas se generan a partir de subconjuntos de columnas específicas, AUTOGRABLE recupera con éxito las columnas generadoras.

   • La codificación de valor sobresale en tareas locales de fila (conjunción de valor único).
   • La codificación de frecuencia sobresale en tareas sensibles a la extensión (conteo, duplicados) donde la estructura de la repetición de valores importa más que la identidad del valor en sí.
   • El parámetro de regularización $\lambda$ filtra eficazmente las columnas irrelevantes, logrando altas tasas de recuperación "Exacta".

2. Correlación con el Desempeño en Avalidad (Downstream): En benchmarks relacionales del mundo real (RelBench), el puntaje $J$ actúa como un filtro necesario. Aunque no es un clasificador perfecto, los puntajes bajos de $J$ son necesarios para un alto AUC en avalidad. El puntaje logra descartar una gran fracción de grafos candidatos (por ejemplo, el 80% en driver-top3) mientras retiene los de mejor desempeño.

3. Comparación con Baselines: Bajo un predictor GraphSAGE fijo, AUTOGRABLE supera a:

   • Trivial ($\gamma_{triv}$): Sin aristas (MLP sobre características).
   • Incidencia Completa ($\gamma_{inc}$): Usando todas las columnas (a menudo conduce a la sobrefragmentación).
   • Basado en Esquema (REG): Usando el esqueleto original de claves foráneas.
   • Selección Aleatoria: Seleccionando columnas uniformemente al azar.
   • Con Conocimiento de Tarea (auGraph): Un método que puntúa atributos usando GNNs entrenadas.

Crucialmente, en tareas donde la estructura es perjudicial (por ejemplo, study-outcome en RelBench o tareas i.i.d. de TabArena), AUTOGRABLE es el único método que declina correctamente la construcción de un grafo, devolviendo el grafo trivial y evitando la degradación del desempeño causada por la fragmentación innecesaria.

Significancia y Reivindicaciones

El artículo afirma cambiar el paradigma de la construcción de tabla-a-grafo de "dependiente del entrenamiento" a "primero la estructura". Al aprovechar el límite 1-WL, los autores argumentan que el valor de una construcción de grafo no reside en su complejidad bruta, sino en cómo agrupa las filas.

La significancia de AUTOGRABLE es triple:

1. Eficiencia: Busca en el espacio de grafos candidatos sin entrenar una sola GNN, haciendo que el proceso de búsqueda sea económico y escalable.
2. Interpretabilidad: Proporciona una explicación no circular y fundamentada de por qué un grafo ayuda (alineación de las particiones de filas con las etiquetas).
3. Adaptabilidad: Es el primer método capaz de reconocer cuándo ninguna construcción de grafo es beneficiosa, evitando la degradación del desempeño que ocurre al forzar estructuras de grafos donde los predictores locales de fila son suficientes.

Los autores concluyen que, para aprendices limitados por 1-WL, la construcción es diseño de particiones, y que "más fino no es necesariamente mejor". La construcción óptima es aquella que expone la estructura justa para distinguir tipos de filas relevantes para la etiqueta sin sacrificar el soporte estadístico necesario para la generalización.