acceptodds
Withdrawn from ICLR 2027

FloydNet: Pivotal Attention for Relation Composition

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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 Pivotal Attention (PA), which maintain ordered pair states and update a target relation by attending over candidates formed from and for every pivot . 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 k framework extends this operation to ordered -tuples, with Self-Attention and PA as its and cases at the attention-operation level. Under atomic tuple initialization and invariant readout, we show that 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph, Reasoning, GNN, Transformer

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_yDMeOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper introduces FloydNet and Pivotal Attention, which extend the self-attention mechanism to second-order pair-state attention and further generalize it to higher orders.

Experiments on several expressiveness tests validate its structural discrimination capabilities. Further experiments on various graph-level, node-level, and link-level tasks show decent results.

Critical strengths
  1. The proposed method is sound and conceptually simple.
  2. Diverse empirical validation across multiple tasks.
Critical weaknesses
  1. Though already acknowledged by the authors, the O(∣V∣k+1)O(|\mathcal{V}|^{k+1}) complexity of kk-order attention and the O(∣V∣k)O(|\mathcal{V}|^k) number of states remain significant limitations that could restrict the proposed method to small-scale graphs.
  2. [Presentation] This paper is difficult to follow. For example, the term "relation" is used ambiguously. It is not until Sec. 2.2 that the authors define relations as "ordered node pairs", while terms like "target pair relation", "pair-relation", and "applied relational prediction" remain confusing. Meanwhile, i,j,ki,j,k are used without clear definitions, and kk is also used to denote the attention order.
  3. [Presentation] Figure 2 is potentially misleading. Figure 2A seems to imply that relation states are updated only for specific node pairs or (k)-order tuples. However, my understanding is that the states are updated for every node pair in the second-order case. Please also see the question below.
  4. [Presentation] It seems the authors never introduce these baselines, such as Subgraph GNN and Local 2-GNN.
  5. The paper seems to have a formatting issue, as it appears to use last year's template.
Questions for authors
  1. Is the target relation RijR_{ij} updated for every node pair (i,j)(i,j)? If so, can the proposed method also be applied to non-graph data, such as sequential data?
  2. How is the proposed method applied to node-level tasks, given that the states are defined for node pairs (i,j)(i,j)?
Reviewer_AjbPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes FloydNet, a method inspired by the Floyd–Warshall algorithm. Instead of learning node embeddings through attention between pairs of nodes, the method maintains embeddings for ordered pairs of nodes and updates them by attending over relation compositions through intermediate pivot nodes. The framework is also extended to higher-order tuples. The authors evaluate the model across a broad range of benchmarks, including substructure counting and neural algorithmic reasoning.

Critical strengths
  1. The paper is well-written and easy to follow. The visualizations and pseudocode are particularly helpful in explaining the proposed method.

  2. The experiments cover a broad range of tasks, and although I am not familiar with all the state-of-the-art models in these areas, the reported results appear quite strong compared to the baselines used.

  3. The implementation details and the introduced fused kernel, which avoids materializing cubic attention tensors in memory, are useful contributions. The efficiency improvements are also supported by experimental measurements (Appendix B.3).

Critical weaknesses
  1. The idea of higher-order attention and message passing is well-established in the field, including higher-order GNNs (Morris et al., 2019), higher-order Graph Transformers (Müller et al., 2024), and triangle-based attention mechanisms in models such as AlphaFold (Jumper et al., 2021). The paper discusses some of these approaches (Section 4.2, Appendix B.6), but does not sufficiently explain what limitations of previous higher-order methods are addressed by the proposed mechanism. The strong results could potentially be attributed to a well-engineered implementation, increased model capacity, or more extensive training and hyperparameter optimization. The paper provides limited insight into why the proposed mechanism enables these improvements and why existing approaches could not achieve similar results. More importantly, the experiments do not sufficiently isolate the contribution of Pivotal Attention from previously explored higher-order mechanisms through controlled ablation studies. This is my main concern, and I am willing to change my score if I get a convincing answer on this.

  2. The theoretical results are somewhat expected given the construction of the model and only establish an upper bound on its expressive power (Appendix D). While the result is valid, it does not establish whether the proposed architecture matches the expressive power of k-FWL in general or offers any theoretical advantage over existing higher-order methods.

  3. The proposed method is computationally expensive, requiring cubic computation for pairwise attention and substantial resources for some experiments (Sections 2.4 and 3.3; Appendix A.1). This cost could be justified by sufficiently strong performance gains, but more controlled comparisons are needed to determine whether the improvements arise from the proposed higher-order relation composition mechanism rather than increased model capacity, training data, or computational budget.

Questions for authors
  1. What is the key limitation of existing higher-order GNNs and triangular-attention architectures that Pivotal Attention addresses? Could the authors provide a more direct comparison with methods such as Edge Transformer under matched model sizes and training settings?

  2. Can the authors provide ablations that isolate the contribution of the proposed pivot-based relation composition? For example, how does the model perform when Pivotal Attention is replaced with standard attention over pair embeddings or alternative higher-order aggregation mechanisms, while keeping the model capacity fixed?

  3. The appendix shows that performance improves substantially with additional training data and model depth. How much of the improvement over existing methods can be attributed to the proposed architecture rather than increased training data, parameter count, or computational budget? Have the authors considered compute-matched comparisons?

Reviewer_8EQ9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes FloydNet, a model that keeps a hidden state for every ordered pair of nodes and updates it with a new attention operation called Pivotal Attention (PA). To update the pair (i, k), each node j acts as a pivot and contributes a candidate built from (i, j) and (j, k), and these candidates are weighted by attention with (i, k) as the query. The design is inspired by Floyd–Warshall. The authors then generalize the operation to ordered k-tuples (k-FloydNet) and show that, under their assumptions on initialization and readout, k-FloydNet is at most as expressive as k-FWL. Experiments cover counting tasks, BREC, CLRS-30, metric and non-metric TSP, and LRGB.

Critical strengths
  1. I like the core idea. When (i, k) is updated, the key and the value of each pivot candidate are built from both (i, j) and (j, k) (Eqs. (2)–(3)), so the composition of two relations through an intermediate node happens explicitly inside the attention. This seems well suited to path-like problems (e.g. shortest paths), where a model with only node states has to encode the same information implicitly.

  2. The TSP experiment is a good test of generalization to larger graphs. The model is trained on N ≤ 100, and on held-out non-metric instances with 100 < N ≤ 200 it finds the optimal tour 99.8% of the time with 10 samples (99.4% for 180 ≤ N ≤ 200; Sec. 3.3, Fig. 4a). Learned solvers often degrade quickly outside the training sizes, so I find this encouraging.

Critical weaknesses
  1. It is not clear how much of the gain comes from the particular attention rule. As Sec. 4.2 notes, Edge Transformer (ET) also updates pair states through an intermediate node. ET does appear in Table 4, but, as far as I can tell, with numbers copied from Müller et al. (2024), so model size and training are not matched. A matched comparison is needed to show that building key and value from both incident relations is what helps.

  2. Table 4 only gives category averages and does not say whether the baselines were re-run or copied, or which hint setting each model uses, FloydNet included. This matters, as the paper finds that removing hints helps on most tasks. Table 5 has no parameter counts; LRGB models are usually compared at around 500k parameters, while the TSP models in Fig. 4(e) have tens of millions, so I cannot tell whether a jump like 0.6143 vs. 0.3587 MRR on PCQM-Contact comes from the architecture or from model size.

  3. Fig. 4(a) compares FloydNet (10 samples) with Linkern, but the main text does not say how Linkern was run (time limit, runs/kicks) or what FloydNet’s runtime is. Linkern finds the optimum on only 16.1% of instances with 180 ≤ N ≤ 200, which makes me wonder what budget it had. Without an equal-runtime comparison, the size of the advantage is hard to judge.

Questions for authors
  1. How does FloydNet compare with ET at matched depth, pair-state width, data and training budget? Ideally this would isolate the effect of the joint key/value construction.

  2. For Table 4, were the baseline results re-run or taken from the original papers, and were they trained with or without hints? Which setting do the FloydNet numbers correspond to? How many parameters do the FloydNet models in Table 5 have?

  3. How was Linkern configured for Fig. 4(a) (number of runs, time limit), and how do the two methods compare at the same wall-clock budget?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.