Abstract
Graph Neural Networks (GNNs) excel in handling graph-structured data but often underperform in link prediction tasks compared to classical methods, mainly due to the limitations of the commonly used message-passing principle. Notably, their ability to distinguish non-isomorphic graphs is limited by the 1-dimensional Weisfeiler-Lehman test (WL). Our study presents a novel method to enhance the expressivity of GNNs by embedding induced subgraphs into the eigenbasis of the graph Laplacian. We introduce a Learnable Lanczos algorithm with Linear Constraints (LLwLC), proposing two novel subgraph extraction strategies: encoding vertex-deleted subgraphs and applying Neumann eigenvalue constraints. For the former, we demonstrate the ability to distinguish graphs that are indistinguishable by 2-WL, while maintaining efficiency. The latter focuses on link representations enabling differentiation between k-regular graphs and node automorphism, a vital aspect for link prediction tasks. Our approach results in a lightweight architecture, reducing the need for extensive training datasets. Empirically, our method improves performance in challenging link prediction tasks across benchmark datasets, establishing its practical utility and supporting our theoretical findings. Notably, LLwLC achieves 20x and 10x speedups by requiring only 5% and 10% of the data from the PubMed and OGBL-Vessel datasets, while comparing to the state-of-the-art.
Introduction and Problem Statement
Most modern Graph Neural Networks (GNNs) rely on the Message Passing (MPNN) paradigm, which aggregates information from immediate neighbors. While effective, MPNNs are theoretically limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. This "glass ceiling" prevents them from distinguishing certain non-isomorphic structures, such as $k$-regular graphs where every node has the same degree.
In Link Prediction (LP), this leads to the "node automorphism problem." If two nodes have identical local structures, an MPNN assigns them identical embeddings, failing to distinguish them even if their global relationships differ. While "Subgraph GNNs" have been proposed to address this, they are often computationally expensive and require heavy preprocessing. This paper, presented at AAAI-26, introduces LLwLC (Learnable Lanczos with Linear Constraints) to solve these issues through a novel spectral approach.
Methodology: Learnable Lanczos with Linear Constraints (LLwLC)
The authors propose a spectral solution grounded in graph signal processing. Instead of using a standard eigenbasis of the graph Laplacian, they introduce a constrained eigenbasis where eigenvectors must satisfy a set of linear constraints ($C^T f = 0$). This forces the learned features to adhere to specific structural properties.
Two primary subgraph extraction policies are introduced:
- Neumann Eigenvalue Constraints: These encode boundary conditions by enforcing zero variation at the boundaries of induced subgraphs. This allows the model to "trap" spectral energy, enabling it to differentiate $k$-regular graphs and solve the node automorphism problem.
- Vertex-deleted Subgraphs: Inspired by the "reconstruction conjecture," the model encodes subgraphs formed by removing specific nodes. This allows LLwLC to distinguish graphs that even the more powerful 2-WL test cannot.
The resulting LLwLCNet architecture uses a constrained Lanczos algorithm to generate a low-rank approximation of the Laplacian and applies learnable spectral filters via MLPs on the eigenvalues. Because the basis itself is structurally "aware," the neural network can remain very lightweight.
Experimental Evaluation and Key Results
The model was evaluated on several standard link prediction benchmarks, including Planetoid datasets (Cora, Citeseer, PubMed) and Open Graph Benchmark (OGB) datasets (OGBL-Collab, OGBL-Vessel, and OGBL-PPA). LLwLC consistently outperformed or matched top-tier models like SEAL, BUDDY, and NCNC.
Key findings include:
- Massive Speedups: LLwLC achieved a 20x speedup on PubMed and a 10x speedup on OGBL-Vessel compared to the SEAL baseline.
- Extreme Data Efficiency: Due to the informative nature of the spectral basis, the model requires significantly less training data. It reached state-of-the-art performance using only 5% of training data on PubMed and 10% on OGBL-Vessel. On OGBL-PPA, it remained highly competitive using just 0.2% of the training data—25 times less than standard competitors.
Discussion and Conclusion
The success of LLwLC highlights that baking structural awareness directly into the mathematical basis of a GNN provides a powerful inductive bias. This approach allows for high expressivity without the need for massive architectures or datasets.
While highly efficient for sparse graphs, the worst-case complexity for extracting vertex-deleted subgraphs in dense graphs ($O(n^3)$) remains a challenge, though mitigated by stochastic constraint subsets. Future work may explore other linear constraints, such as edge-based constraints, and further formalize the hierarchy of expressivity for constrained spectral methods. Overall, LLwLC establishes a new, efficient frontier for expressive GNNs in link prediction tasks.
Summary updated