LASE : Learned Adjacency Spectral Embeddings.

Abstract

Las redes neuronales de grafos (GNNs, por su sigla en inglés) se han convertido en un foco de interés durante los últimos años. Las mismas han sido aplicadas exitosamente en problemas de varios dominios, mostrando ser una metodología particularmente efectiva en lo que respecta al aprendizaje de representaciones de grafos (GRL). Por su parte, los Random Dot Product Graphs (RDPG) son un modelo generativo de grafos muy popular por su simplicidad, interpretabilidad y poder de expresión. El mismo postula que un grafo puede modelarse considerando que existen posiciones latentes (o embeddings) para cada nodo y especifica la probabilidad de interconexión entre estos como el producto interno entre los embeddings asociados. La tarea de estimar estos embeddings se plantea como un problema de factorización de matrices no convexo. Los Adjacency Spectral Embeddings (ASE) ofrecen una solución aproximada a este problema obtenida mediante la descomposición espectral de la matriz de adyacencia, la cual si bien goza de garantías estadísticas sólidas puede ser costosa computacionalmente. El presente trabajo se centra en el uso de GNNs para aprender embeddings similares a los de ASE. En particular, se propone una nueva arquitectura, denominada Learned Adjacency Spectral Embeddings (LASE), que utiliza la técnica de Algorithm Unrolling para modelar el descenso por gradiente (GD) aplicado a ASE. En esta arquitectura, cada iteración de GD se representa como una capa en una red neuronal, compuesta por componentes clásicos de las GNNs como las Graph Convolutional Networks(GCN) y los mecanismos de Graph Attention (GAT). Los embeddings obtenidos con LASE muestran ser de una calidad comparable o incluso superior a los obtenidos mediante otros métodos tradicionales como ser la descomposición en valores singulares (SVD). La arquitectura propuesta permite la incorporación de mecanismos de sparse attention los cuales reducen significativamente el costo computacional requerido. A su vez, se introduce una versión generalizada, Generalized LASE (GLASE), que expande su aplicación a escenarios con grafos heterofilios. Por su parte, este trabajo propone el uso de los embeddings obtenidos con LASE como Positional Encodings (PE), que pueden ser utilizados por ejemplo para alimentar modelos basados en Graph Transformers (GTs). A su vez, la incorporación de la información estructural que aportan estos embeddings, permite romper la simetría en las representaciones de los nodos, venciendo así algunas de las limitaciones que presentan las GCNs clásicas. En particular, se propone la creación de un módulo basado en LASE que pueda integrarse como parte de la arquitectura de un modelo más general destinado a tareas específicas, como ser clasificación de nodos o predicción de enlaces. Los experimentos realizados durante este trabajo consideran grafos homofilios y heterofilios, y buscan validar la efectividad y adaptabilidad de los modelos en una variedad de escenarios. En particular, se utilizan conjuntos de datos sintéticos generados mediante modelos Stochastic Block Model (SBM), así como conjuntos datos reales comúnmente utilizados en la literatura.