- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The work proposes LINC, a GNN layer that treats each edge as an interaction between two participants, instead of only as a channel for a message to one receiving node. For every edge, LINC builds one shared interaction representation from both endpoints, and each participant uses it through a scale computed from its own embedding, so the same interaction can have a different consequence for each participant. The authors show that this representation does not depend on the order of the endpoints for undirected edges, and that ordinary message passing is a special case of LINC. LINC is evaluated on a wide range of benchmarks showing remarkable results in many of them.
Critical strengths
The paper is generally well written, and the main narrative is easy to follow, also at a high level. The idea of viewing an edge as one interaction with a different consequence for each participant is intuitive and well motivated, although not entirely new (see weaknesses). The evaluation is broad, covering 16 benchmarks and 38 baselines, and I find the general applicability of the method to many different kinds of graphs (heterogeneous graphs, directed, etc.) one of its key advantages.
Although the method is clearly more computationally expensive than other, simpler, methods, its application to graphs with over a million edges, such as ogbn-arxiv (169k nodes) and Freebase (180k nodes), shows that it remains practical at this scale and suggests its potential relevance in real-world scenarios.
Critical weaknesses
The main idea reminded me of the principle behind sheaf neural networks (Hansen & Gebhart, 2020; Bodnar et al., 2022). In sheaf neural networks, each node keeps its own representation (its stalk), and learned d x d restriction maps project the two endpoints of an edge into a shared edge space. The two projections are compared there, and each endpoint then receives its own update, transformed back through its own restriction map. Although sheaf neural networks do not define an explicit interaction representation as LINC does, I feel the comparison computed in each edge space plays a similar role. To be clear, I believe LINC is still novel and differs from sheaf neural networks, but the paper would benefit from more detailed discussion of such methods.
Moreover, although the number of datasets and baselines is remarkable, I feel several relevant baselines are missing, especially some that are cited by the paper itself or are particularly notable. These include Polynormer (Deng et al., 2024), neural sheaf diffusion (Bodnar et al., 2022), bundle neural networks (Bamberger et al., 2025), and cooperative sheaf neural networks (Ribeiro et al., 2026).
References:
Bamberger, J., Barbero, F., Dong, X., & Bronstein, M. (2025). Bundle neural networks for message diffusion on graphs. International Conference on Learning Representations (ICLR).
Bodnar, C., Di Giovanni, F., Chamberlain, B. P., Lio, P., & Bronstein, M. M. (2022). Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs. Advances in Neural Information Processing Systems, 35.
Deng, C., Yue, Z., & Zhang, Z. (2024). Polynormer: Polynomial-expressive graph transformer in linear time. International Conference on Learning Representations (ICLR).
Hansen, J., & Gebhart, T. (2020). Sheaf neural networks. NeurIPS Workshop on Topological Data Analysis and Beyond.
Ribeiro, A., Tenorio, A. L., Belieni, J., Souza, A. H., & Mesquita, D. (2026). Cooperative sheaf neural networks. International Conference on Learning Representations (ICLR).
Questions for authors
Additional baselines. It would be helpful to include a comparison with Polynormer (Deng et al., 2024) and neural sheaf diffusion (Bodnar et al., 2022), which are both cited in the paper, as well as with more recent sheaf- and bundle-based models (Bamberger et al., 2025; Ribeiro et al., 2026). If running these models is not feasible, reporting the results from their papers on the datasets and splits that overlap with the ones used here would already help position LINC with the current state-of-the-art.
8 comments
Response to Reviewer FyHi (2/4)
W2 & Q. Additional baselines
From the sheaf family, we added neural sheaf diffusion in its O(d) form (Bodnar et al., 2022), which the reviewer names, and its most recent extension, CSNN (Ribeiro et al., ICLR 2026). For Polynormer, we ran both the original model and Polynormer-r, its variant with ReLU activations, which the authors report as the stronger one and use in their released code. Polynormer-r is stronger on six of the seven graphs here, so we report it. Each method was run with its official implementation under the same protocol as all other baselines. This protocol uses the same data, splits, and evaluation code, the authors' configuration when one is published for the same setting, and otherwise the authors' search space with at most 128 configurations. The implementations, configurations, and per-run logs of all baselines on all datasets are in the supplementary material, so that every comparison can be rerun.
For the undirected graphs, the first table reports accuracy on the first five graphs and ROC-AUC on the last three, as well as the average rank among the 23 methods of the undirected group.
| Method | Photo | WikiCS | Cham-F | Roman | Ratings | Mines | Tolokers | Questions | Avg. rank | Avg. rank (Macro-F1) |
|---|---|---|---|---|---|---|---|---|---|---|
| Polynormer-r | 96.30 | 79.59 | 40.09 | 92.48 | 54.42 | 97.39 | OOM | 78.41 | 3.57 | 3.29 |
| O(d)-NSD | 95.88 | 51.39 | 40.65 | 72.76 | 39.24 | 94.32 | 85.22 | 67.75 | 11.75 | 11.63 |
| CSNN | 96.36 | 78.73 | 42.21 | 89.79 | 51.29 | 99.48 | 85.32 | 78.75 | 3.75 | 5.38 |
| LINC | 96.45 | 79.80 | 42.73 | 91.40 | 52.40 | 95.47 | 86.03 | 79.41 | 2.38 | 2.38 |
For the directed graphs, the second table reports accuracy and the average rank among the 9 methods of the directed group.
| Method | Cora-ML | Roman-Empire | MGTAB | ogbn-arxiv | Avg. rank | Avg. rank (Macro-F1) |
|---|---|---|---|---|---|---|
| CSNN | 85.64 | 93.09 | 90.77 | 68.57 | 3.50 | 3.25 |
| LINC | 87.75 | 94.68 | 90.64 | 71.58 | 1.50 | 1.75 |
Response to Reviewer FyHi (3/4)
Overall. LINC keeps the best average rank in both graph groups and on both metrics. As in the submission, out-of-memory entries are not ranked, so the rank of Polynormer-r covers seven graphs. Ranking such entries last is a common alternative (e.g., Gu et al., 2025). We keep them unranked because the efficiency analysis (Section 5.4) already reports the memory cost, and counting it again in the accuracy ranking would penalize the same weakness twice. Ranking these entries last would move Polynormer-r to 5.94 and leave the rank of LINC unchanged.
Per graph. Polynormer-r is above LINC on Roman-Empire, Amazon-Ratings, and Minesweeper, by 1.08, 2.02, and 1.92 points, and LINC is higher on the other graphs. CSNN is 4.01 points above LINC on Minesweeper, and LINC is higher on the other seven undirected graphs and on three of the four directed graphs. NSD is below LINC on every graph.
Cost. LINC is also far cheaper than Polynormer-r and CSNN. The table below gives the training step and inference time in ms and the peak training memory in MiB. The values are averages over the seven undirected graphs on which all three methods run and over the four directed graphs, where Polynormer-r is not among the baselines. The numbers in parentheses show how many times the cost of LINC each competitor needs.
| Method | Train (undir.) | Inference (undir.) | Memory (undir.) | Train (dir.) | Inference (dir.) | Memory (dir.) |
|---|---|---|---|---|---|---|
| Polynormer-r | 152.9 (8.2×) | 52.9 (9.6×) | 7,325 (5.6×) | — | — | — |
| CSNN | 111.8 (6.0×) | 44.0 (8.0×) | 2,059 (1.6×) | 178.5 (3.6×) | 63.3 (4.5×) | 5,231 (2.9×) |
| LINC | 18.6 | 5.5 | 1,298 | 49.6 | 13.9 | 1,786 |
The gap does not come from our engineering optimization alone. Even before this optimization, LINC was faster than Polynormer-r on the three graphs where Polynormer-r leads (25.6, 49.0, and 22.6 ms against 184.4, 197.9, and 104.7 ms). On Tolokers, where Polynormer-r runs out of 40 GB of memory, LINC needs 2.8 GB before optimization and 0.7 GB after. All costs come from one timing procedure applied to every method.
Depth and the common tuning budget. On the three graphs where Polynormer leads, its author configurations use 10 local and 1 to 3 global attention layers. The search space of LINC caps the depth at 6 layers, and all main-table results respect this cap. LINC also improves with depth. On Minesweeper, its ROC-AUC rises to 98.02 at 16 layers and 98.96 at 32 layers (Appendix D.3), above the 97.39 of Polynormer-r. These settings lie outside the search space, so the main table is unchanged, and we mention them only to explain the gap. This is our general rule. The hyperparameter analysis in Section 5.4 includes a setting with a higher test score than the selected configuration on 15 of the 16 graphs, and we report all such settings only in that analysis. Every number in the main tables stays within the budget that applies to every method, so the comparison does not favor LINC.
Two details. With their author configurations, both versions of Polynormer exceeded 40 GB of memory on Tolokers and are marked OOM. The CSNN paper reports 92.63 on Roman-Empire. That result uses the edge list as stored in the dataset, without symmetrization (its Appendix C), so the edges remain directed. It therefore corresponds to our directed Roman-Empire, on which our run of CSNN obtains 93.09, in line with the reported value, and LINC obtains 94.68. On the undirected Roman-Empire of our Table 1, CSNN obtains 89.79 and LINC obtains 91.40. LINC is thus higher than CSNN in both settings.
Response to Reviewer FyHi (1/4)
We thank the reviewer for the positive assessment of the writing, the breadth of the evaluation, and the general applicability of LINC, and for stating clearly that LINC is related to, yet different from, sheaf neural networks. Following the reviewer's suggestions, we added the closest related methods, and LINC keeps the best average rank in every graph group with them included. We also made LINC several times faster through simple engineering changes to its implementation, such as computing graph constants once and fusing projections, while its classification performance stayed essentially the same. This addresses the computational cost the reviewer mentions.
W1. Relation to sheaf neural networks
The reviewer's description of sheaf neural networks is accurate, and the analogy holds in one respect. In both methods, the two endpoints form a quantity in a shared, edge-related space, and each endpoint derives its own update from it. The methods differ in what that quantity is, how it returns to the nodes, and what is learned. A single sentence in our related work did not do this justice. The revision therefore adds a subsection on sheaf neural networks to Appendix A (A.3) and refers to it from that sentence in Section 2.
In short, sheaf methods ask how far apart the two endpoints of an edge are and evolve the representations to reduce that gap. LINC asks what the two endpoints form together on an edge and passes it to both as information beyond the neighbor's features. The numerical comparison follows.