Portal Attention for Learning Graph Algorithms at Scale

Many graph computations share one skeleton. Shortest paths, reachability, widest-bandwidth routes and probabilistic logic queries all combine values along a path and then pick or pool the result across alternative paths. The algebra that captures this is a semiring: a pair of operations, one that combines values along a path (such as "+" for path lengths) and one that aggregates across paths (such as "min"). Swapping the semiring changes which problem is solved, while the computation graph stays the same. Neural networks can provably express these computations. In practice, gradient descent rarely finds the right weights, and the networks that could find them cost quadratic time or need depth proportional to the graph's diameter.

This note proposes portal attention. It is a hierarchical attention layer whose tree is a recursive split of the graph along small separators, the sets of vertices whose removal disconnects the graph. Each cluster is summarized by its separator vertices (its "portals") together with the semiring distances among them, rather than by a pooled average vector. Cross-cluster attention is then a small dense semiring matrix product through the portals. This is exactly how Gaussian-elimination-style algorithms compute all-pairs path closures on graphs with small separators. The central bet is that matching attention's structure to this elimination order does two things. It makes exact algorithmic behavior expressible in $O(\log N)$ layers at near-linear cost on graphs of bounded treewidth, where treewidth measures how tree-like a graph is. It also makes that behavior learnable, because gradient paths shrink from diameter length to logarithmic length.

Core Claim

Existing hierarchical attention summarizes a cluster by a pooled vector. Hierarchical Self-Attention ties sibling weights toward external subtrees under softmax. HDSE attends from nodes to METIS or Louvain super-nodes. HLM-G pools each node into a single token before global attention.

We claim that pooled summaries are the wrong interface for path algebra. The information a cluster must pass outward for min-plus closure is its $s \times s$ boundary distance matrix. That matrix can have tropical rank $s$, meaning it cannot be factored into fewer than $s$ min-plus components, so a fixed-width average cannot reproduce it. We conjecture, and will try to prove, that a pooled hierarchy with summary width below the separator size cannot represent exact cross-cluster distances, whereas a portal hierarchy with hard min can. The concrete recursion is:

$$D_{uv} = \min_{p \in P} \big( D_{up} + D_{pv} \big),$$

Here $D_{uv}$ is the semiring distance between tokens $u$ and $v$ in different child clusters, and $P$ is the set of portal tokens separating them.

This gives a possible explanation for the "shallow hierarchy saturation" that HDSE reports beyond one level of coarsening. We treat that explanation as a hypothesis to test, not an established fact.

Where This Sits Relative to Prior Work

Three papers motivate the gap. A Tropical View of Graph Neural Networks shows that sum-aggregating graph networks approach min-plus operations as a smoothing scale goes to zero. It proves that such networks can express Bellman-Ford, and states explicitly that existence does not imply gradient descent will find those weights. The CLRS Algorithmic Reasoning Benchmark supplies the empirical failure: message-passing networks drop from 96.63% validation F1 at $n=16$ to 44.99% at $n=64$. Backward Oversmoothing supplies a mechanism: in deep message-passing networks, backpropagated gradients converge to a constant vector and freeze earlier layers. Bellman-Ford-style networks need depth close to the graph diameter, so they sit exactly in this regime. Portal attention replaces diameter-length depth with separator-tree depth.

The closest single paper is Tropical Attention. It replaces softmax with max-plus attention and a Hilbert projective metric, and reaches 97.00% on Convex Hull when trained at length 8 and tested at length 1024. It remains fully pairwise, and hence quadratic, and is evaluated on sequences rather than sparse graphs. We reuse its lesson that tropical scoring avoids softmax blur. Our contribution lies elsewhere: the sparse, separator-shaped routing structure and the claim that this structure is what makes tropical attention both scalable and trainable.

The algebraic logic programming line supplies method. Semirings for probabilistic and neuro-symbolic logic programming shows that one compiled circuit serves many tasks when the semiring is swapped. The Gradient of Algebraic Model Counting shows how to backpropagate through such circuits with memory proportional to nodes rather than edges. Our separator tree is itself a compiled circuit for path closure, analogous to the tree decompositions that knowledge compilers exploit. We therefore borrow both the semiring-swap evaluation and the memory-efficient backward pass.

An Algebraic View of the Expressivity of Recurrent Language Models constrains the design. It shows that floating-point non-associativity changes what a model can compute. Min and max are exactly associative in floating point, so reassociating a tropical closure through a hierarchy is exact. Reassociating a real-valued sum-product closure is not. This is a concrete reason to prefer hard or annealed tropical aggregation over softmax inside the hierarchy.

Finally, the GraphBLAS work (Mathematical Foundations of the GraphBLAS) and Hector show that semiring graph operations run efficiently as templated matrix kernels. Portal attention turns the irregular sparse problem into many small dense $s \times s$ semiring products, which is the shape GPUs handle well.

Research Program

We will build a portal-attention layer on a nested-dissection tree computed once per input graph with METIS. The topology is an input, so the tree is not learned; we flag this openly.

Leaves hold small blocks of vertices with full local attention. Each internal node owns its separator tokens. The model runs an upward pass that computes each cluster's portal-to-portal closure, followed by a downward pass that routes values from portals to interior vertices. Both passes use semiring matrix products whose "add" is a log-sum-exp with a learned temperature, annealed toward hard min. Edge and node "weights" come from a learned encoder, so the network must learn what to aggregate, not just how.

The cost is $O(N s^2)$ per tree level for maximum portal size $s$. This is near-linear for trees and bounded-treewidth graphs. For planar or expander graphs, top-level separators grow, and we cap the portal budget. Beyond that cap the layer is approximate; we will say so and measure the damage.

The theory track has two parts. First, a rank lower bound separating portal summaries from pooled summaries. Second, a bound showing the gradient path length is the tree depth rather than the diameter. The empirical track measures exact-algorithm recovery, generalization to larger graphs, and per-layer gradient norms, using the diagnostic from Keriven's paper.

Baselines

The naive reference point is a standard message-passing network (MPNN) trained on the same tasks. On CLRS it reports 44.99% out-of-distribution F1 at $n=64$ CLRS. The Pointer Graph Network reports 50.84% in the same paper.

The strongest algorithmic competitor is Tropical Attention Tropical Attention run on graph inputs with full pairwise attention. It will be evaluated wherever quadratic memory fits and reported as out-of-memory beyond that. Its reported figure is 97.00% on length-OOD Convex Hull. That is not a graph task, and no reported graph-algorithm result for it was found on Lacuna.

The strongest scalable hierarchical competitor is GraphGPS with High-level HDSE HDSE. On Peptides-func, HDSE reports a 6.21% relative Average Precision gain over GraphGPS. The absolute anchor there is SAN's 0.6439 test AP versus GCN's 0.5930, both from Long Range Graph Benchmark.

We also include a recurrent min-plus network with Maslov-style smoothing, iterated to the graph diameter. This is the realizable network from A Tropical View of Graph Neural Networks, trained rather than constructed.

All methods get the same training graphs and parameter budget within 10%. Each gets an equal hyperparameter search of fixed trial count and five seeds, on the same GPU memory ceiling.

Two ablations isolate the key ingredient. The first keeps the identical separator tree but replaces portal summaries with pooled cluster vectors of equal token count. The second keeps portals but uses softmax instead of annealed tropical aggregation.

Beating the field means two things. On synthetic and SALSA-CLRS path tasks at 10 to 100 times the training size, graph-level exact accuracy must exceed every baseline by a margin larger than the seed spread. On Peptides-func, AP must at least match GraphGPS+HDSE at equal or lower memory.

Why not just…?

Why not just precompute shortest-path or hierarchy distances as positional encodings, as HDSE does? When the graph weights are given, this hands the model the answer. In our latent-weight tasks, the weights are a learned function of node features and are supervised only through final outputs, so nothing can be precomputed. On real benchmarks this remains a genuine threat. The Peptides-func comparison against GraphGPS+HDSE will settle whether portal routing adds anything beyond good encodings.

Why not just run Tropical Attention or a deep min-plus network with enough compute? On graphs small enough for quadratic memory, this may match us. If it does, portal attention's value shrinks to efficiency, and we will report that plainly. The deep recurrent version must be iterated to the diameter, which is the regime where Backward Oversmoothing predicts frozen layers. Our per-layer gradient-norm measurements and seed-level success rates test whether that prediction holds for tropical aggregation, which the paper's analysis does not cover.

Why not just call GraphBLAS Bellman-Ford on the graph? When the weights are observed, one should. The proposal targets settings where the relevant weights or facts come from a neural encoder, as in neuro-symbolic logic programming. There, the solver would have to sit inside training, and portal attention is that solver made differentiable at near-linear cost.

Why not just add more levels to existing pooled hierarchies? This is exactly our first ablation. HDSE's own reported saturation beyond one level is weak evidence that deeper pooling does not help.

Proposed Experiments

The first experiment is a synthetic suite. It covers single-source shortest path in the tropical semiring, reachability in the Boolean semiring, and widest path in the bottleneck semiring. Graph families span trees, grids, random geometric graphs and Erdős-Rényi graphs, so separator size varies in a controlled way. We train at $n \le 64$ and test up to the 32,000-node scale that SALSA-CLRS makes feasible. That benchmark reports graph-level accuracy "often drops to zero" at scale, with no per-algorithm numbers found on Lacuna, so our baselines supply the reference numbers. We report node-level and graph-level exact accuracy against the separator size of each family. The prediction is graceful degradation as separator size exceeds the portal budget, not collapse.

The second experiment is the graph subset of CLRS-30 (BFS, Bellman-Ford, Dijkstra, Floyd-Warshall, connected components) at the standard $n=64$ OOD split.

The third is a semiring-swap test in the spirit of algebraic model counting. We train the edge encoder under the tropical semiring, then evaluate the frozen model under Boolean and bottleneck semirings with no retraining. Transfer should be near-perfect if the model has learned the algorithm rather than a task-specific shortcut.

The fourth applies the method to Peptides-func and PCQM-Contact from the Long Range Graph Benchmark to test transfer beyond synthetic algorithms.

The fifth measures wall-clock time and memory against $N$, comparing blocked GPU semiring kernels with a PyTorch reference and with quadratic Tropical Attention.

The decisive checks come from these experiments. The idea is supported if three things hold: portal summaries beat pooled summaries at matched tree and token budget on large-graph accuracy; gradient norms in early layers stay non-vanishing where the diameter-depth min-plus network's collapse; and semiring-swapped evaluation succeeds. If pooled summaries match portals, the rank argument is irrelevant in practice. If the deep min-plus network trains equally well, the learnability claim fails and only the efficiency claim survives.