Simple Path Structural Encoding for Graph Transformers

Graph transformers extend global self-attention to graph-structured data, achieving notable success in graph learning. Recently, random walk structural encoding (RWSE) has been found to further enhance their predictive power by encoding both structural and positional information into the edge representation. However, RWSE cannot always distinguish between edges that belong to different local graph patterns, which reduces its ability to capture the full structural complexity of graphs.This work introduces Simple Path Structural Encoding (SPSE), a novel method that utilizes simple path counts for edge encoding. We show theoretically and experimentally that SPSE overcomes the limitations of RWSE, providing a richer representation of graph structures, particularly in capturing local cyclic patterns. To make SPSE computationally tractable, we propose an efficient approximate algorithm for simple path counting.SPSE demonstrates significant performance improvements over RWSE on various benchmarks, including molecular and long-range graph datasets, achieving statistically significant gains in discriminative tasks. These results pose SPSE as a powerful edge encoding alternative for enhancing the expressivity of graph transformers.

The transformer architecture has achieved prominent performance on regularly-structured data such as images or text, owing both to global attention and positional encoding.While the former is a measure of the alignment between two tokens in a text, or two pixels in an image, the latter informs on the position of each element (text token/pixel) in the input data.Due to the absence of obvious ordering, devising general-purpose positional encodings for graph data, such as social networks, molecules, citation graphs, or electrical circuits, remains an open problem.In this work we highlight failure cases of one of the most successful positional encodings for graph transformers, based on random walks, and propose to consider instead simple paths, that is, the count and the length of all direct paths between any two points in a graph.This novel relative positional encoding overcomes several limitations of random walks, and allows the discovery of certain graph structures such as cycles, which makes it a particularly valuable tool for deep learning on molecular data.