Constraint-Based Structural Attention in Graph Transformers
An Inverse-Optimisation-Based Approach
C.E.M. Pelsma (TU Delft - Mechanical Engineering)
P. Mohajerin Esfahani – Mentor (TU Delft - Mechanical Engineering)
T. Ok – Mentor (TU Delft - Mechanical Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Many problems in science and engineering involve data that is naturally graph-structured: molecules, proteins, knowledge bases, and road networks. Graph Transformers have become one of the leading model families for this kind of data. Because plain self-attention treats its input as an unordered set, graph topology (edges, distances, and connectivity patterns) must be supplied to the model explicitly, either through structural encodings added to the node features or, more directly, through a learned bias added to the attention logits. In the latter case, a structural term is added to the content score, where it competes with that score on equal footing and applies the same correction at every layer, regardless of whether content attention already respects the structural prior.
We take a different starting point. Softmax attention can itself be written as the solution to an entropy-regularized optimization problem, which suggests treating structure not as another term in the objective but as a constraint on the attention itself. This thesis develops that idea into a Graph Transformer in which structural priors are imposed as per-pair inequality constraints on the attention distribution. Each correction is governed by a Lagrangian dual variable that the model carries across transformer layers, growing for pairs where content attention falls short of the structural prior and relaxing where the prior is already met.
The result is a Graph Transformer that learns structural constraints within its attention mechanism rather than treating structure as a fixed additive term. Because the dual variable reacts to how far the realized attention falls short of the structural target, the correction is active only where structure is genuinely underserved and silent elsewhere. The construction is agnostic to which pairwise graph signal serves as the constraint, and multiple signals can be combined without architectural changes. On the ZINC and LRGB Peptides molecular benchmarks, the adaptive constraint mechanism consistently improves over the matched baseline, in which the dual is held fixed at unit scale.