Links Are Tokens as Nodes Are: Incidence-Graph Transformers with Editable Walk Encodings for Link Prediction

Two gaps have kept the random-walk positional encoding (RWPE), now a standard input to graph transformers (GTs) on other tasks, out of the ones built for link prediction (LP). First, RWPE is defined at a vertex, and the object to be scored, an edge, has not been given one. Second, the walk probabilities around a pair of vertices depend on whether the pair has an edge in the graph, so a model either reads that edge's presence off its encodings, which fails to generalize, or recomputes them for every query, which fails to scale. We close both gaps with incidence RWPE and editable RWPE. We prove that on the incidence graph, whose vertices are the vertices and the edges of the original graph, the walk with each edge given its two orientations takes one step of the original walk every two steps, so every vertex and every edge around a query carries an RWPE of its own class, computed from powers of the original graph's operator alone: incidence RWPE. We also prove that the common-neighbor heuristics are closed-form functions of these encodings. Links are then tokens as nodes are, the query edge among them, scored by a transformer with no message passing, no topological attention mask, and no node identifiers. Editable RWPE, a rank-two correction, reads every encoding on the graph the query is scored under from encodings computed once per graph, at a cost per token quadratic in the walk length and independent of the graph's size. With fewer than five million parameters, Vephormer, our Vertex-Edge Graph Transformer, exceeds every published result on ogbl-ppa and matches or exceeds every GT on all six benchmarks. Ablations find the context tokens worth nearly a quarter of the model's score on ogbl-ppa, and a message-passing after every block largely redundant.