Plain Transformers are Surprisingly Powerful Link Predictors

Link prediction is a core challenge in graph machine learning, demanding models that capture rich and complex topological dependencies. While Graph Neural Networks (GNNs) are the standard solution, state-of-the-art pipelines often rely on explicit structural heuristics or memory-intensive node embeddings—approaches that struggle to generalize or scale to massive graphs. Emerging Graph Transformers (GTs) offer a potential alternative but often incur significant overhead due to complex structural encodings, hindering their applications to large-scale link prediction. We challenge these sophisticated paradigms with PENCIL, an encoder-only plain Transformer that replaces hand-crafted priors with attention over sampled local subgraphs, retaining the scalability and hardware efficiency of standard Transformers. Through experimental and theoretical analysis, we show that PENCIL extracts richer structural signals than GNNs, implicitly generalizing a broad class of heuristics and subgraph-based expressivity. Empirically, PENCIL outperforms heuristic-informed GNNs and is far more parameter-efficient than ID-embedding–based alternatives, while remaining competitive across diverse benchmarks—even without node features. Our results challenge the prevailing reliance on complex engineering techniques, demonstrating that simple design choices are potentially sufficient to achieve the same capabilities. Our code is publicly available at https://github.com/quang-truong/pencil.

Many real-world systems need to predict which pairs of entities are likely to be connected, but many graph-learning methods often rely on hand-designed graph heuristics, node ID embeddings, or expensive preprocessing that can be hard to scale. This paper asks whether a much simpler model can solve the same problem. We introduce PENCIL, a standard Transformer-based model that processes sampled subgraphs revolving around each candidate pair. Unlike many prior methods, PENCIL does not require handcrafted link features, costly graph encodings, or large node-embedding tables. We show theoretically that PENCIL can implicitly recover broad classes of graph patterns used by traditional link-prediction methods. Experiments show that this simple approach performs strongly across several benchmarks, often using fewer parameters and training faster than specialized graph models. These results suggest that plain, hardware-friendly Transformers can be a practical alternative for large-scale link prediction.