FloydNet: A Learning Paradigm for Global Relational Reasoning

arXiv:2601.19094v3 Announce Type: replace-cross Abstract: Learning algorithmic computation often requires explicit relational intermediate states, yet many graph processors maintain their primary states on individual entities.

We introduce \fnet and \textbf{Pivotal Attention} (PA), which maintain ordered pair states and update a target relation $(i,k)$ by attending over candidates formed from $(i,j)$ and $(j,k)$ for every pivot $j$. Motivated by the pair-and-pivot structure of Floyd--Warshall, PA learns relation composition and pivot weighting in parallel rather than executing its ordered min-plus recurrence.

The \kfnet{k} framework extends this operation to ordered $k$-tuples, with Self-Attention and PA as its $k=1$ and $k=2$ cases at the attention-operation level.

Under atomic tuple initialization and invariant readout, we show that \kfnet{k} is no more graph-discriminative than k-FWL; on BREC, each evaluated variant matches the success set of its corresponding WL reference. \fnet further achieves 96.64\% mean accuracy under the reported CLRS-30 protocol and a 99.8\% optimality rate with 10 samples on held-out non-metric TSP instances.