LASE: Learned Adjacency Spectral Embeddings
This work addresses the challenge of efficiently and accurately computing spectral embeddings for graph representation learning, offering a novel approach that integrates into supervised pipelines, though it is incremental in combining existing GNN modules.
The authors tackled the problem of learning nodal Adjacency Spectral Embeddings (ASE) from graph inputs by designing a neural architecture that unrolls gradient descent iterations into a graph neural network, resulting in Learned ASE (LASE) embeddings that are interpretable, parameter-efficient, and robust to missing edges. The method outperforms optimized eigendecomposition routines and achieves competitive performance in supervised link prediction and node classification tasks, surpassing GNNs with precomputed spectral encodings.
We put forth a principled design of a neural architecture to learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs. By bringing to bear the gradient descent (GD) method and leveraging the principle of algorithm unrolling, we truncate and re-interpret each GD iteration as a layer in a graph neural network (GNN) that is trained to approximate the ASE. Accordingly, we call the resulting embeddings and our parametric model Learned ASE (LASE), which is interpretable, parameter efficient, robust to inputs with unobserved edges, and offers controllable complexity during inference. LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules, which is intuitively pleasing since GCN-based local aggregations alone are insufficient to express the sought graph eigenvectors. We propose several refinements to the unrolled LASE architecture (such as sparse attention in the GAT module and decoupled layerwise parameters) that offer favorable approximation error versus computation tradeoffs; even outperforming heavily-optimized eigendecomposition routines from scientific computing libraries. Because LASE is a differentiable function with respect to its parameters as well as its graph input, we can seamlessly integrate it as a trainable module within a larger (semi-)supervised graph representation learning pipeline. The resulting end-to-end system effectively learns ``discriminative ASEs'' that exhibit competitive performance in supervised link prediction and node classification tasks, outperforming a GNN even when the latter is endowed with open loop, meaning task-agnostic, precomputed spectral positional encodings.