Una alternativa escalable y efectiva a los Graph Transformers

Las Redes Neuronales de Grafos (GNNs) han demostrado un rendimiento impresionante en el aprendizaje de representación de grafos, pero enfrentan desafíos para capturar dependencias de largo alcance debido a su poder expresivo limitado. Para abordar esto, se introdujeron los Graph Transformers (GTs), que utilizan el mecanismo de autoatención para modelar eficazmente las relaciones pares de nodos. A pesar de sus ventajas, los GTs sufren de complejidad cuadrática respecto al número de nodos en el grafo, dificultando su aplicabilidad a grafos grandes. En este trabajo, presentamos el Operador Contextual Mejorado con Grafos (GECO), una alternativa escalable y efectiva a los GTs que aprovecha la propagación en vecindario y convoluciones globales para capturar eficazmente dependencias locales y globales en tiempo cuasilineal. Nuestro estudio en conjuntos de datos sintéticos revela que GECO alcanza una aceleración de 169 veces en un grafo con 2 millones de nodos respecto a la atención optimizada. Evaluaciones adicionales en una gama diversa de benchmarks muestran que GECO escala a grafos grandes donde los GTs tradicionales suelen enfrentar limitaciones de memoria y tiempo. Notablemente, GECO logra consistentemente una calidad comparable o superior en comparación con las líneas base, mejorando el SOTA hasta en un 4.5%, y ofreciendo una solución escalable y efectiva para el aprendizaje de grafos a gran escala.