Overview
A family tree branches, a ring road loops, and a railway line stretches between two ends. Each can be drawn as a graph, but a coordinate system that represents one with short, faithful distances may distort another. This study builds a Transformer that learns the geometry of its graph representations alongside the task it has to solve.
Key Findings
Give a network room for two different shapes
A neighborhood of a graph can branch like a tree, while another part can loop back on itself. Flat distances have to represent both. The authors give a Transformer the option of using several geometries at once. Each attention head operates with its own curvature. Negative curvature makes room for branching structure, positive curvature changes how closed shapes can fit, and zero curvature recovers the flat limit. All curvatures start at zero in the experiments, so a head can move away from flat space during training.
Compare two vectors where they share a reference point
In curved space, a direction lives in the tangent space at a point. To compare query and key , the method transports each direction from its corresponding value point to the origin. There the inner product gives the attention score in Equation 6:
The values are then combined by a curvature-aware weighted average. The rest of the network, including projections, nonlinearities and transitions between layers with different curvatures, also uses the geometry. Equations 5–8
Let every node and edge speak without building every pair
Following TokenGT, the architecture turns nodes and edges into individual tokens. Global attention can then connect distant graph elements. With nodes and edges, directly computing all pair scores costs . Because the comparisons take place at one origin, the authors can use a kernel feature map to factor the approximate score calculation. The resulting attention step scales linearly with token count for fixed feature dimensions. The reported experiments use this approximation. Equation 11
The appendix compares runtime and peak memory during inference on the four graphs used for reconstruction. FPS-T’s peak memory is close to TokenGT’s in those measured runs. Graph size and hardware still determine whether multiple curvatures fit a particular application. Appendix A.3
Reconstruction and classification tell different stories
On the Web-Edu hyperlink graph, reconstruction reaches 99.00 mean average precision for FPS-T and 89.56 for TokenGT in the main comparison. The paper also shows a one-head Web-Edu run in which curvature becomes more negative over training, and a dimension study where four-dimensional FPS-T beats 16-dimensional TokenGT. The largest reconstruction difference appears on the graph with the most negative estimated average curvature among the four networks tested. Here reconstruction measures how well the model arranges an observed network, which is the map underlying its training data. Learning future links would require withholding edges or later snapshots from that process.
Node classification asks whether the representation predicts a class, rather than whether it preserves an edge. Selected F1 results below are reported with 95% confidence intervals over ten random initializations. TokenGT is the closest architecture comparison because it uses the same tokenization with flat geometry. The Transformer configurations also tune preprocessing. Table 1
| Model | Texas | Actor | Citeseer |
|---|---|---|---|
| GAT | 59.46 ± 1.12 | 27.43 ± 0.23 | 71.70 ± 0.28 |
| TokenGT | 88.65 ± 2.06 | 36.59 ± 0.89 | 71.23 ± 0.51 |
| FPS-T | 89.19 ± 2.37 | 39.61 ± 0.54 | 70.03 ± 0.71 |
Actor favors FPS-T in this comparison, while Citeseer favors TokenGT. The reconstruction and classification tests help locate where the extra geometry pays off and where a flat model remains competitive.
Questions & Answers
The opening answers are simulated author responses based on the paper.
Q: Does a negatively curved head prove that the graph is a tree?
A: The curvature is a parameter learned for the task. It indicates which geometry the model uses for that component. Different underlying structures can lead to a similar choice.
Q: Why use several heads with different curvatures?
A: A graph can contain branch-like regions, cycles, and local links at the same time. A product of geometries lets the model allocate different parts of its representation to different patterns.
Q: How can we tell whether curvature made the improvement?
A: The most informative comparisons hold the graph input, positional features, head count, and training budget fixed. Change only the curvature configuration. That separates the effect of learning geometry from other features of the graph Transformer. The reported results vary across datasets, which makes it useful to measure which graph motifs actually benefit.
Future Ideas
Route network link suggestions by structural motif
Build a link-suggestion tool for maintainers of software dependency graphs. Preserve edge direction when labeling candidate links by measured motifs, including branching and short cycles. Compare learned-curvature and flat models at matched budgets on future links withheld by date. Report precision for each motif alongside runtime. Keep the geometry-aware option only where it gives maintainers more correct suggestions at the same review volume.
Add frozen mixed-curvature heads and keep the positional construction and training steps identical across comparisons. Measure branching, cycles, and edge direction before training so the motif analysis cannot be selected to match favorable results.
Sources
Original abstract
Real-world graphs naturally exhibit hierarchical or cyclical structures that are unfit for the typical Euclidean space. While there exist graph neural networks that leverage hyperbolic or spherical spaces to learn representations that embed such structures more accurately, these methods are confined under the message-passing paradigm, making the models vulnerable against side-effects such as oversmoothing and oversquashing. More recent work have proposed global attention-based graph Transformers that can easily model long-range interactions, but their extensions to- wards non-Euclidean geometry are yet unexplored. To bridge this gap, we propose Fully Product-Stereographic Transformer, a generalization of Transformers towards operating entirely on the product of constant curvature spaces. When combined with tokenized graph Transformers, our model can learn the curvature appropriate for the input graph in an end-to-end fashion, without the need of additional tuning on different curvature initializations. We also provide a kernelized approach to non-Euclidean attention, which enables our model to run in time and memory cost linear to the number of nodes and edges while respecting the underlying geome- try. Experiments on graph reconstruction and node classification demonstrate the benefits of generalizing Transformers to the non-Euclidean domain.