acceptodds
Under review as a conference paper at ICLR 2027

One Interaction, Two Consequences: Rethinking the Computational Role of Edges in Graph Learning

Abstract

Graph neural networks (GNNs) are widely used to learn from graphs, and most of their designs focus on what information a node should receive. In real graph data, however, an edge usually records an interaction, such as a paper written by a student and a professor, and the same interaction can mean different things to the two participants. Such designs use an edge only to shape the message sent to one receiving node and do not model the interaction as one fact with a consequence for each participant. Graphs that differ in homophily, heterogeneity, and directionality have been handled by separate specialized GNNs that fix the meaning of an edge in advance. We instead make the interaction itself the unit of computation and propose a simple model, Learning from Interaction Consequences (LINC). LINC forms one representation of an interaction from both participants, and the two participants use this representation through scales computed from their own embeddings. As a result, one interaction has two consequences, one for each participant. Since a consequence also carries the other participant's features, ordinary message passing is a special case of LINC. We prove that the interaction representation of an undirected edge does not depend on the order of the participants, while the two consequences can still differ. On 16 benchmarks covering homophilic, heterophilic, heterogeneous, and directed graphs, LINC uses one architecture throughout and achieves the best average rank in every group against 38 baselines. In ablation studies, the interaction representation alone carries most of what a node needs from its neighbors. Different consequences for the two participants help on most graphs, especially on directed and heterophilic graphs, where the participants often differ in role or label.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Graph Neural Networks, Graph Representation Learning, Interaction Modeling, Relational Learning, heterophily graphs, heterogeneous graphs, directed graphs

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_FyHiOpenReview ↗
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
AuthorsOpenReview ↗

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.

  • What the edge space holds. Sheaf diffusion computes the difference of the two projections, which vanishes when the endpoints agree, and the diffusion drives the representations toward agreement on every edge. LINC computes the normalized element-wise product of the two projections, which is largest when they align. Its entries sum to r\sqrt r times the cosine similarity of the two projections.
  • How it returns to the nodes. Sheaf diffusion pulls the difference back through the transposed restriction map of each endpoint, so the two endpoints receive updates of opposite sign. In LINC, both participants receive the same vector, read it through their own feature-wise scales, and add it to the other participant's features. The layer is not a Laplacian and minimizes no energy. It therefore sets no target of agreement, and one interaction can have different consequences for its two participants.
  • What is learned. Sheaf models learn a d×dd\times d restriction map per node–edge incidence (Hansen & Gebhart, 2020; Bodnar et al., 2022) or an orthogonal or conformal map per node (Bamberger et al., 2025; Ribeiro et al., 2026). The matrices of LINC are shared by the whole graph, and only a scale vector varies per node.

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.

AuthorsOpenReview ↗

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.

MethodPhotoWikiCSCham-FRomanRatingsMinesTolokersQuestionsAvg. rankAvg. rank (Macro-F1)
Polynormer-r96.3079.5940.0992.4854.4297.39OOM78.413.573.29
O(d)-NSD95.8851.3940.6572.7639.2494.3285.2267.7511.7511.63
CSNN96.3678.7342.2189.7951.2999.4885.3278.753.755.38
LINC96.4579.8042.7391.4052.4095.4786.0379.412.382.38

For the directed graphs, the second table reports accuracy and the average rank among the 9 methods of the directed group.

MethodCora-MLRoman-EmpireMGTABogbn-arxivAvg. rankAvg. rank (Macro-F1)
CSNN85.6493.0990.7768.573.503.25
LINC87.7594.6890.6471.581.501.75
AuthorsOpenReview ↗

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.

MethodTrain (undir.)Inference (undir.)Memory (undir.)Train (dir.)Inference (dir.)Memory (dir.)
Polynormer-r152.9 (8.2×)52.9 (9.6×)7,325 (5.6×)———
CSNN111.8 (6.0×)44.0 (8.0×)2,059 (1.6×)178.5 (3.6×)63.3 (4.5×)5,231 (2.9×)
LINC18.65.51,29849.613.91,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.

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

This paper proposes Learning from Interaction Consequences (LINC), a graph neural network that represents each edge as a shared interaction with a separate consequence for each endpoint. LINC forms an interaction representation through an element-wise product of normalized node projections. Each node scales the shared content using its own embedding and combines it with a direct transformation of its neighbor’s features. These consequences are aggregated through a residual update, with relation-balanced weights for heterogeneous graphs.

Critical strengths
  1. Strong performance across a broad set of graph settings.

  2. The interaction term provides measurable benefits beyond simply increasing the parameter count on some datasets.

Critical weaknesses
  1. Method. 1.1. The novelty is limited. Is it just a variant of the directional attention framework? Also, Equation (3) is a message function that depends on both the receiving node and its neighbors, which is already allowed by the general MPNN formulation. The authors need to clarify their contributions further.

  2. Experiments. 2.1. The authors write in Appendix D.2: "With the direct term in place, removing the own scales changes the main metric by at most 0.75 points and raises it slightly on 10 of the 16 graphs, by at most 0.48 points." Does it mean some parts of the design are not necessary? 2.2. After checking the author-provided code, I don't find the implementation of baseline models. It raises concerns about the fairness of the comparison.

Questions for authors

See Critical Weaknesses

9 comments
AuthorsOpenReview ↗

Response to Reviewer bVEA (1/6)

We thank the reviewer for the review, and in particular for noting the strong performance of LINC across a broad range of graph settings and the measurable benefit of the interaction term beyond the added parameters. Both strengths follow from what is new in LINC, and we are glad to state it here more directly than the submission did.

W1. What is new, and how LINC relates to directional attention and the general MPNN

What is new. LINC changes the role of an edge. In existing GNNs, an edge serves the message that one receiving node gets. It acts as a route, a weight (attention), a condition (directions, relations, the receiver's embedding), or a state (Section 2). Real graph data, however, record interactions, that is, events in which two nodes take part together, such as a purchase or a collaboration. An interaction has a consequence for each participant, and LINC models exactly this. For every edge, LINC forms one representation of the interaction from both participants (the "shared content" in the reviewer's summary). Each participant then takes its own consequence from it, through a scale computed from its own embedding. The contributions follow from this view. One model serves graphs of any homophily, heterogeneity, and directionality, which specialized GNNs have handled separately. The representation of an undirected interaction does not depend on the order of the participants, while the two consequences can differ (Theorem 1). With the same architecture on every graph, LINC has the best average rank on the main metric in every graph group of the main tables, also against the added baselines. It ranks 2.38 among 23 methods on undirected graphs, 1.25 among 16 on heterogeneous graphs, and 1.50 among 9 on directed graphs. On the second metric, LINC also ranks first on undirected and directed graphs (2.38 and 1.75), so it has the best average rank in five of the six combinations of graph group and metric. LINC also costs much less than its two strongest competitors, with the optimized implementation described in W2.2. The table below compares the three methods on the seven undirected graphs on which all of them run. The numbers in parentheses show how many times the cost of LINC each competitor needs.

MethodTraining step (ms)Inference (ms)Peak training memory (MiB)
Polynormer-r152.9 (8.2×)52.9 (9.6×)7,325 (5.6×)
CSNN111.8 (6.0×)44.0 (8.0×)2,059 (1.6×)
LINC18.65.51,298
AuthorsOpenReview ↗

Response to Reviewer bVEA (2/6)

Relation to directional attention. Attention gives the edge the role of a weight. It computes a scalar coefficient from the two endpoints, normalizes it over the receiver's neighborhood, and uses it to scale the neighbor's message, so the content is still the neighbor's features. Directional variants make the weight or the transformation depend on the edge direction. LINC computes no attention weights. Its interaction representation is a content vector formed from both participants and added to each consequence as information beyond the neighbor's features. It differs from attention in three ways. It is formed once per interaction and shared by both participants, rather than computed per direction. It is not normalized over a neighborhood, so edges do not compete. And the two consequences differ even on undirected graphs, where there is no direction to use. Table 1 includes representative attention models, namely GAT, GATv2, GATE, and EGAT, as well as GNN-FiLM, which modulates messages by the receiver. LINC is not a more expensive form of attention either. The table below gives the average rank of these models on the main metric in the extended Table 1, and their costs averaged over the eight undirected graphs, timed with the same procedure. The numbers in parentheses show how many times the cost of LINC each model needs.

MethodAvg. rankTraining step (ms)Inference (ms)Peak training memory (MiB)
GAT8.5624.3 (1.4×)7.1 (1.4×)1,415 (1.2×)
GATv217.509.8 (0.6×)4.2 (0.8×)708 (0.6×)
GATE13.2527.0 (1.5×)8.3 (1.6×)1,136 (0.9×)
EGAT14.6342.8 (2.4×)14.8 (2.8×)3,116 (2.6×)
GNN-FiLM10.7589.7 (5.1×)23.8 (4.6×)5,692 (4.7×)
LINC2.3817.75.21,221

LINC costs about as much as these models, between 0.6 and 5.1 times their cost, and its average rank is far better than that of all of them. If the reviewer has a specific directional-attention model in mind, we would be glad to compare with it directly.

Eq. (3) and the general MPNN. It is true that the general MPNN formulation allows a message function that depends on both endpoints. The introduction cites this formulation among the existing designs (Gilmer et al., 2017), and it now states that LINC is an instance of it. The formulation, however, does not say what such a function should compute. GAT and GNN-FiLM are MPNNs as well, and their contributions also lie in the message functions they propose. What Eq. (3) specifies is that the part that depends on both participants is formed once per interaction, shared by both, and read by each in its own way. This turns one interaction into two consequences, instead of one message for one receiving node. As the reviewer notes in Strength 2, this part brings gains beyond the added parameters. We also tested whether its multiplicative form matters, a question raised by Reviewer H2cH. On all 16 graphs, we replaced the normalized product with a symmetric MLP of the two participants, with the same parameter count and everything else unchanged. Counting each graph and metric separately, the interaction representation brings a clear gain in 12 cases and a clear loss in 4, meaning that the paired 95% interval excludes zero. The product stays ahead in all 12 cases with a clear gain, and the MLP is ahead in all 4 cases with a clear loss. Across the 16 graphs, the advantage of the product rises with the gain of the interaction representation. Its three largest values are on Taobao, Amazon-Ratings, and Roman-Empire, the three graphs on which the interaction representation helps most, and its most negative values are on Chameleon-F and Minesweeper, where the interaction representation hurts. A generic MLP of the two participants therefore cannot replace the multiplicative form without losing part of the gains (Table 12 in Appendix D.2).

AuthorsOpenReview ↗

Response to Reviewer bVEA (3/6)

W2.1. Are some parts of the design unnecessary?

No. Each part of LINC has its own role, and the sentence the reviewer quotes concerns only the last of the four parts below. The same decomposition answers Reviewer H2cH (W2 & Q3, W4), and we repeat it here so that this response is self-contained.

(i) The direct term is part of the design, and strong on its own. The direct-only variant computes in the same way as LINC and lacks only the shared content. At B=0B=0, a node is updated as hu′=hu+WoGELU(11+nu[D0xu+∑q∈Q(u)ωu,qGELU(Dsxv)])h_u'=h_u+W_o\mathrm{GELU}\Big(\tfrac{1}{1+n_u}\Big[D_0x_u+\sum_{q\in\mathcal Q(u)}\omega_{u,q}\mathrm{GELU}(D_{\mathrm s}x_v)\Big]\Big) with x=LN(h)x=\mathrm{LN}(h). Each participant still receives its own consequence, and the nonlinearity acts on each consequence before aggregation. Section 4.3 explains why this matters (Proposition 4, Appendix B.5). A layer that aggregates first sees a neighborhood only through the sum of its features. Its strength does not come from the other components that LINC shares with it. All variants reuse the configuration selected for LINC, including depth, width, dropout, learning rate, weight decay, normalization, residual blocks, and relation-balanced aggregation, and they are retrained from scratch on the same splits and seeds. If this direct-only variant replaced LINC, it would rank first in every graph group of the original tables and third in the extended Table 1, behind only CSNN and Polynormer-r, as the table below shows.

GroupDirect onlyBest original baselineFull LINC
Undirected, 19 baselines2.62SGFormer 5.441.88
Heterogeneous, 15 baselines2.25SlotGAT 3.501.25
Directed, 7 baselines1.25MagNet 3.501.25

Residual connections and normalization are common among the baselines of Table 1, including the enhanced classic GNNs of Platonov et al. (2023), and all baselines are tuned under the same budget. These components therefore cannot explain why the direct-only variant ranks above every original baseline. What it keeps from LINC is that each consequence is computed before aggregation. Relation-balanced aggregation is not the source either. With uniform weights, Macro-F1 changes by +0.86, +0.68, +0.87, and −1.20 points on IMDB, Freebase, Alibaba, and Taobao (Table 13 in Appendix D.2), and LINC keeps the best average rank in the heterogeneous group either way (1.50 instead of 1.25).

Reviewer_H2cHOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper introduces LINC, a graph neural network that constructs a shared representation for each edge and derives a separate message, termed a “consequence,” for each endpoint. The shared representation is a normalized Hadamard product of projected endpoint embeddings. Each endpoint receives a combination of transformed neighbor features and shared interaction content modulated by a receiver-dependent feature-wise scale. The architecture uses tied role projections for undirected graphs, separate source/target projections for directed graphs, and type-specific input mappings with relation-balanced aggregation for heterogeneous graphs. The authors establish exchange symmetry, node-permutation equivariance, and reduction to a sender-only message-passing variant. Experiments cover 16 benchmarks and report strong average rankings against a broad set of baselines.

Critical strengths
  • The proposed architecture is clear and potentially useful. The emprical results are couraging.
  • Computing one shared edge representation and reading it differently at its endpoints is an intuitive inductive bias. It is interesting to introduce a 'receiver-dependent' operator to allow endpoint specific readout without learning an unrestricted matrix for every edge.
  • The same architectural template is evaluated on homophilic, heterophilic, heterogeneous, and directed graphs. Comparisons include enhanced classic GNNs, GNN-FiLM, and several edge-aware models-not just weak conventional baselines.
Critical weaknesses
  • Distinction from general message passing is overstated.LINC's endpoint consequence can be written as a conventional receiver-conditioned messaging, followed by permutation-invariant neighborhood aggregation and a node update. Computing an intermediate edge representation once and reusing it does not place the architecture outside the general MPNN framework.

  • The evidence for endpoint-specific scaling is weaker than the narrative suggests. In Appendix D.2, Table 9 reports that with the direct term retained, removing the own scales improves the main metric on 10 of 16 graphs (checking the last two columns of the table). Table 4 also shows an almost negligible average difference between the full model and the variant without own scales. These results suggest that the direct term already gives the endpoints different messages, and receiver-specific modulation of the shared interaction is not established as a consistently beneficial ingredient of the full architecture. The positive results for own scales when the direct term is removed are informative (the forth and fifth columns) , but support a narrower claim: the scales can compensate for otherwise identical endpoint messages.

  • Closely related comparisons remain missing (e.g., SheafGNN), particularly on heterophilic benchmarks. The proposed LINC shares similarity with sheaf graph neural networks (SheafGNN), as both methods use endpoint transformations associated with a shared edge space. The substantial difference lies in how edge information becomes node updates.

  • Much of the headline performance is already achieved by the direct-only backbone, for example, Freebase: 51.97 Macro-F1 versus 52.32 for full LINC, Alibaba: 44.74 versus 44.86, ogbn-arxiv:71.69 accuracy versus 71.58, to just name a few. This raises an important attribution question: How much of the improvement comes from interaction modeling, and how much comes from hyperparameter selection such as depth, normalization, residual blocks, relation-balanced aggregation, and so on?

Questions for authors
  1. Positioning issue: Do you agree that LINC is a structured receiver-conditioned MPNN? What is the precise restriction or inductive bias that distinguishes it from a general edge encoder followed by endpoint-conditioned readouts?

  2. SheafGNN comparison. It would be good to see the evaluation of neural sheaf diffusion (mentioned in the main text) on representative heterophilic datasets under the same splits and comparable tuning budgets.

  3. How should the “two consequences” claim be interpreted given that removing own scales improves the main metric on 10 of 16 datasets when the direct term is present?

  4. Why does the direct-only backbone already recover most of the gains on Freebase and Alibaba?

  5. How does the normalized product compare with a matched-capacity concatenation-based MLP, or another symmetric pair encoder? Is the benefit specifically multiplicative?

11 comments
AuthorsOpenReview ↗

Response to Reviewer H2cH (1/8)

We thank the reviewer for the detailed review, including the column-by-column reading of Table 9. The reviewer's questions point to three results that the submission did not make explicit. The revision now states them, and we believe they make the paper stronger.

  1. Where the interaction representation helps, and that this is not a matter of tuning. On both metrics, the interaction representation improves six of the seven graphs of real user interactions (e-commerce, crowdsourcing, Q&A, and social follows), five of them clearly, that is, with a paired 95% interval that excludes zero. It improves only five of the other nine, three of them clearly. Wherever it clearly improves the main metric, it does so at every interaction dimension from 8 to 256 (W4, Q4).
  2. The multiplicative form carries these gains. A symmetric MLP pair encoder of the same size falls behind wherever the interaction representation clearly helps (Q5).
  3. The interaction representation keeps LINC ahead of the strongest related methods. After we added Polynormer and CSNN, the direct-only variant falls behind both, while the full LINC stays first (W4).

We answer each point below and group related weaknesses and questions.

W1 & Q1. Relation to general message passing

Do you agree that LINC is a structured receiver-conditioned MPNN? What is the precise restriction or inductive bias …?

Yes. LINC is an MPNN in the sense of Gilmer et al. (2017). Each consequence is a receiver-conditioned message, followed by permutation-invariant aggregation and a node update, and the submission does not place LINC outside this framework. When the paper says that ordinary message passing is a special case of LINC, it means the common form in which each message depends only on the sender's features, GELU(Dxv)\mathrm{GELU}(Dx_v). This is the sender-only variant in the reviewer's summary, and LINC reduces to it exactly at B=0B=0 (Proposition 2). The distinction drawn in the introduction is therefore a distinction within the framework. It concerns how LINC organizes its message function, compared with the message functions in common use. The submission did not define ordinary message passing where the term first appears. The revision now defines it there and adds that LINC is an instance of the general MPNN.

Compared with a general edge encoder E(xu,xv)E(x_u,x_v) followed by endpoint-conditioned readouts R(xu,xv,E)R(x_u,x_v,E), LINC imposes three restrictions.

  1. One shared interaction representation. cq=Bzqc_q=Bz_q is computed once per interaction and is the same vector for both participants. For an unordered interaction, it does not depend on the order of the endpoints (Theorem 1). zqz_q is the element-wise product of two normalized projections and has no pair-specific parameters beyond these projections. Q5 below shows that this specific form matters.
  2. A feature-wise readout that depends on the node alone. A participant reads cqc_q only through γu=1+Cxu/d\gamma_u=1+Cx_u/\sqrt d. This vector is computed once per node, reused in all of the node's interactions, and close to 1 at initialization. No matrix is generated per edge, so each node reads the shared content in its own way at the cost of one product per node.
  3. Additive combination with a sender-only term. As a result, B=0B=0 recovers ordinary message passing exactly, and C=0C=0 makes the two interaction terms equal. Each departure from message passing sits in a term that can be removed on its own, so the ablations in Section 5.3 can attribute each effect. The inductive bias is that both participants jointly decide what an interaction is, so it has one answer, while each participant decides how much to take from it. In practice, the pair computation costs O(mrd)O(mrd) per layer. The same layer serves undirected, directed (with separate source and target projections), and heterogeneous graphs without changes. Whether these restrictions pay off is an empirical question. With this single layer, LINC has the best average rank on the main metric in every graph group of the main tables, also after the new baselines are added. It ranks 2.38 among 23 methods on homophilic and heterophilic graphs, 1.25 among 16 on heterogeneous graphs, and 1.50 among 9 on directed graphs. W4 isolates what the interaction representation contributes, and Q5 shows that its multiplicative form matters.
AuthorsOpenReview ↗

Response to Reviewer H2cH (2/8)

W2 & Q3. The own scales and the "two consequences" claim

The numbers the reviewer reads from Table 9 are correct, and Section 5.3 reports the same. With the direct term in place, the two participants already receive different messages, and removing the own scales changes the average result little. As we understand it, the reviewer concludes that the receiver-specific reading only compensates for identical endpoint messages. Since the full model avoids such messages through the direct term, this reading would not be an established part of the architecture. This interpretation of our results comes from how we presented the ablation. Section 5.3 introduced the comparison without the direct term as a test of the own scales ("the own scales should matter on heterophilic and directed graphs"), which invites readers to judge the claim by the full model with and without them. The revision states which comparison tests the claim and reports separately what the own scales add in the full model. On the evidence itself, we see it differently, for three reasons.

1. The direct term is part of each consequence, not an alternative to it. A consequence is the whole message of Eq. (3), mu∣q=GELU(Dsxv+γu⊙cq)m_{u\mid q}=\mathrm{GELU}(D_{\mathrm s}x_v+\gamma_u\odot c_q) (Section 4.2, Figure 1). What a participant receives from an interaction combines the other participant's features with its own reading of the shared content. In the full model, the two consequences are therefore designed to differ through both parts. The claim that different consequences help must be tested against the only variant in which they are identical, namely the one without the direct term and the own scales (Theorem 1). The table below shows that the claim holds in every configuration (✓ = kept, as in Table 4).

Direct termInteraction rep.Own scalesTwo consequencesGraphs better than row 1 (main, second)
–✓–identical (Theorem 1)reference
–✓✓differ through the own scales12/16, 11/16
✓✓–differ through the direct term16/16, 15/16
✓✓✓ (LINC)differ through both15/16, 15/16

The last two rows differ on a single graph, Taobao, whose standard deviation is about three points.

2. Removing the direct term isolates the reading rather than creating a deficiency to be patched. Without the direct term, the shared content is the only carrier of neighbor information, so the value of reading it from each participant's side can be measured on its own. The own scales then improve 12 of the 16 graphs. These include all four directed graphs, where the two participants have different roles by construction, and five of the six heterophilic graphs, where they often have different labels. With the direct term present, part of the same information also reaches each participant through the other participant's features, so the average gain from the own scales shrinks. Two routes to the same property overlap, but this does not make the property unimportant.

AuthorsOpenReview ↗

Response to Reviewer H2cH (3/8)

3. Where the two participants play different roles, the own scales help even with the direct term present. 7 of our 16 graphs record real user interactions on online platforms, namely Amazon co-purchases (Amazon-Photo, Amazon-Ratings), user–item clicks and purchases (Alibaba, Taobao), crowdsourcing (Tolokers), a Q&A community (Questions), and social follows (MGTAB). The other nine are Wikipedia pages and text (WikiCS, Chameleon-F, and the two Roman-Empire graphs), citations (Cora-ML, ogbn-arxiv), a knowledge base (Freebase), a movie database (IMDB), and a synthetic grid (Minesweeper). With the direct term present, the own scales raise the main metric on four of the seven real user-interaction graphs and the second metric on five, compared with one and three of the other nine. On the real user-interaction graphs, they add 0.14 and 0.28 points on average, with the largest gains on the e-commerce graphs. On these platforms, the two participants of an interaction often play different roles, such as a buyer and a product, an asker and an answerer, or a follower and a followee. Graphs of this kind are common in real applications, and the receiver-specific reading is designed for them. On the document and knowledge graphs, an edge is closer to a symmetric association, which the direct term already distinguishes, and the own scales change the results by at most half a point in either direction. The table below gives LINC minus the variant without the own scales (✓ ✓ – in Table 4), in points. Tables 9 and 10 in Appendix D.2 list all variants, grouped by data source.

Real user-interaction graphMainSecondOther graphMainSecond
Amazon-Photo+0.17+0.09WikiCS−0.12−0.01
Amazon-Ratings+0.41+0.52Chameleon-F−0.29−0.44
Alibaba+0.75+1.18Roman-Empire−0.01+0.01
Taobao−0.38+0.35Minesweeper−0.05−0.28
Tolokers+0.15−0.08IMDB−0.04−0.05
Questions0.00+0.07Freebase−0.13−0.44
MGTAB−0.15−0.15Cora-ML−0.04−0.09
Roman-Empire (directed)+0.19+0.23
ogbn-arxiv−0.48+0.10
Mean+0.14+0.28Mean−0.11−0.11

In short (Q3). The claim says that one interaction gives its two participants different consequences in two ways, through the other participant's features and through each participant's own reading of the shared content. LINC always uses the first way. The second adds most where the participants play different roles. The core of the inductive bias, a shared interaction representation formed by both participants, is consistently useful beyond the direct term (W4) and depends on its multiplicative form (Q5).

Why the own scales stay in the default architecture. First, they improve the results where the two participants play different roles, even with the direct term present, as shown above, and such graphs are common in real applications. Second, they are the only part through which a participant reads the shared content in its own way. Attributes of the interaction itself (edge attributes), such as the amount or time of a transaction, would therefore be read differently by the two participants through the own scales. We list this as future work. Third, they cost little. Where a graph does not need receiver-specific reading, training can drive CC to zero and recover the variant without them. The scale is also computed once per node and reused in all of the node's interactions, with no per-edge parameters.

Revision. Section 5.3 now states that a consequence combines the direct term with the participant's reading of the shared content. It names the variant with identical consequences as the comparison that tests the claim, and it reports separately what the own scales add in the full model and on which graphs.

Comments on the paper

4 comments
AuthorsOpenReview ↗

General Response to All Reviewers (1/2)

We thank the three reviewers for their careful and constructive reviews. All three note that LINC uses one architecture for homophilic, heterophilic, heterogeneous, and directed graphs and performs strongly on all of them. Their questions concern three topics, namely how the contribution is positioned, where the gains come from, and how LINC compares with closely related methods. The revision also states several results more clearly than the submission did. We answer each reviewer in a separate response, and the revised PDF marks all changes in blue.

1. Positioning. LINC is a message-passing network in the sense of Gilmer et al. (2017). What is new is how its message function is organized. The interaction representation is computed once per interaction and shared by both participants, and each participant reads it through its own feature-wise scale. The introduction now says this explicitly. It also defines ordinary message passing, which the paper calls a special case of LINC, as message passing in which each message depends only on the sender's features. LINC reduces to it at B=0B=0.

2. Where the gains come from. The ablation in Appendix D.2 (Tables 9 to 12) traces the results to the parts of LINC in four steps.

(i) The direct-only variant is already strong. As Section 4.3 motivates, LINC computes a separate consequence for each participant and applies the nonlinearity to each consequence before aggregation. It still does so without the interaction representation (B=0B=0). If this direct-only variant replaced LINC in the original tables, it would already rank first in every graph group (undirected, heterogeneous, and directed).

(ii) The interaction representation adds to the direct-only variant, above all on real user-interaction data. With the interaction representation added, LINC improves over the direct-only variant on 11 of the 16 graphs in each metric. On both metrics, it improves six of the seven graphs that record user behavior on online platforms, five of them clearly, that is, with a paired 95% interval that excludes zero. It improves only five of the other nine, three of them clearly. On seven of the eight graphs with a clear gain, the gain is larger in Macro-F1 than in the other metric of the graph (accuracy, ROC-AUC, or Micro-F1), so it also reaches the smaller classes. The multiplicative form matters as well. Following Reviewer H2cH, we replaced the normalized product with a symmetric MLP of the same size. Counting each graph and metric separately, the product stays ahead in all 12 cases where the interaction representation clearly helps (Table 12).

(iii) These gains come from the data, not from tuning. Wherever the interaction representation clearly improves the main metric, it does so at every interaction dimension from 8 to 256. After we added Polynormer and CSNN, the direct-only variant falls behind both, while the full LINC stays first.

(iv) The own scales make the two consequences differ where the participants play different roles. The two consequences of an interaction are identical only when both the direct term and the own scales are removed (Theorem 1). Every variant in which they differ beats this variant on 12 to 16 of the 16 graphs. With the direct term present, the own scales raise the main metric on four of the seven real user-interaction graphs and the second metric on five, compared with one and three of the other nine. The own scales are also the only part through which each participant reads the shared content in its own way. They would therefore let the two participants read attributes of the interaction, such as the amount or time of a transaction, differently.

3. New baselines. We added three baselines and ran them with the same splits, evaluation code, and tuning rules as the other baselines. They are O(d)-NSD, which two reviewers named, CSNN (ICLR 2026), the most recent sheaf-family model, and Polynormer in its stronger ReLU variant, Polynormer-r. LINC keeps the best average rank in every graph group, with 2.38 among 23 methods on undirected graphs, 1.25 among 16 on heterogeneous graphs, and 1.50 among 9 on directed graphs.

AuthorsOpenReview ↗

General Response to All Reviewers (2/2)

4. Reproducible comparisons. We collected the code and detailed results of every baseline on every dataset in the supplementary material, so that reviewers and readers can inspect and rerun any comparison. The package contains the official implementation of each baseline, the hyperparameter-search code and commands, the fixed configuration of every table cell, and the logs and results of every run. Re-running all 278 numeric cells of the main tables from this package reproduces the reported values closely, with a median difference of 0.02 points. The largest difference is 2.26 points, for CensNet on WikiCS, and it is far below the run-to-run variation of this baseline, which exceeds ten points.

5. One tuning budget for all methods, LINC included. Every method is selected on validation within the same budget of at most 128 configurations, and the depth of LINC is capped at six layers. LINC can do better outside this budget. Our hyperparameter analysis (Section 5.4) includes a setting with a higher test score than the selected configuration on 15 of the 16 graphs. On Minesweeper, for example, LINC reaches 98.96 ROC-AUC with 32 layers, against 95.47 in Table 1. We nevertheless report these settings only in Section 5.4 and keep every number in the main tables within the common budget. The comparison therefore does not favor LINC, and its margins in the main tables are conservative.

6. Faster implementation. We also optimized the implementation of LINC without changing the model or its equations, and its classification performance stayed essentially the same. We then re-timed every method, including both implementations of LINC, with one procedure on an A100 with exclusive access (Section 5.4, and Tables 14 and 15 in Appendix D.4). Under this procedure, and compared with our original implementation, which produced the results of the submitted version, a training step of LINC is now 1.8 to 6.7 times faster on all 16 graphs, and its peak training memory is 15% to 75% lower. Its average training-time rank improves from 18.00 to 8.38 among 23 methods on undirected graphs, from 9.50 to 5.50 among 16 on heterogeneous graphs, and from 7.25 to 3.75 among 9 on directed graphs. On four graphs, only MLP or LightDiC trains faster. LINC now also costs much less than its two strongest competitors. The table below compares the three methods on the seven undirected graphs on which all of them run. The numbers in parentheses show how many times the cost of LINC each competitor needs.

MethodTraining step (ms)Inference (ms)Peak training memory (MiB)
Polynormer-r152.9 (8.2×)52.9 (9.6×)7,325 (5.6×)
CSNN111.8 (6.0×)44.0 (8.0×)2,059 (1.6×)
LINC18.65.51,298

On Tolokers, Polynormer-r runs out of 40 GB of memory, while LINC needs 0.7 GB.

AuthorsOpenReview ↗

Update: clarifications in Section 4

We have uploaded a revised PDF that adds brief explanations of the design choices in Sections 4.1 to 4.3 (pages 4 to 6), namely the scaling in Eqs. (1) and (2), why both terms in Eq. (3) share one GELU, and why Eq. (4) averages the consequences. We have marked all changes from this round in red and kept the first-round revisions in blue.

AuthorsOpenReview ↗

Summary of the discussion

Dear Area Chair,

We briefly summarize the strengths the reviewers noted, how we addressed their questions, and where the discussion ended.

Reviewer H2cH (rating raised from 2 to 3, soundness from 2 to 3). In the review, the reviewer found the architecture clear and the idea of computing one shared edge representation and reading it differently at its endpoints an intuitive inductive bias. The reviewer also found the comparison strong, with enhanced classic GNNs and edge-aware models rather than weak baselines. On the positioning of LINC, we clarified that it lies within the general MPNN framework and stated its precise inductive bias in the introduction. On the own scales, we explained that the two-consequences claim must be tested against the variant with identical consequences, and we restructured Section 5.3 to report what the own scales add and why we keep them. On sheaf neural networks, we added O(d)-NSD and CSNN under the same protocol and compared the mechanisms in Appendix A.3. On the attribution of the gains, we added a paired ablation on all 16 graphs, a parameter-matched MLP encoder, and a sweep over the interaction dimension. The reviewer found that these largely addressed the concerns and that the core idea is compelling.

Reviewer FyHi (positive rating of 3 maintained). In the review, the reviewer found the paper well written, the idea intuitive and well motivated, and the evaluation broad. The reviewer also saw the general applicability to many kinds of graphs as a key advantage, found LINC practical at the scale of ogbn-arxiv and Freebase, and considered LINC novel and different from sheaf neural networks. On sheaf neural networks, we added a detailed comparison in Appendix A.3. On the missing baselines, we added Polynormer-r, O(d)-NSD, and CSNN under the same protocol. On the computational cost, we made the implementation faster and timed all methods with one procedure. On the rationale behind the activation functions, scaling, and aggregation, raised in a second round, we explained each choice and stated it next to the equations in Section 4. The reviewer found LINC effective against recently published methods in both performance and computational efficiency, and the clarifications a significant improvement for readers.

Reviewer bVEA (rating of 2 maintained). In the review, the reviewer noted the strong performance of LINC across a broad range of graph settings and the benefit of the interaction term beyond the added parameters. On novelty, we explained what is new in LINC and how it differs from directional attention and the general MPNN formulation. On whether every part of the design is needed, we showed the role of each part with a four-step decomposition. On the baseline implementations, we provided the code, configurations, and logs of all baselines in the supplementary material. The reviewer found that these address the concerns about the comparisons and that the distinction from attention is clearer. The remaining points concern the degree of novelty and the own scales. Since the novelty concern does not name a specific prior method, our final reply restates how LINC differs from the closest families discussed, together with the evidence that its multiplicative form carries the gains. The same reply explains the role of the own scales, consistent with Section 5.3.

Overall, the revision states the motivation of each design choice next to its equation (Section 4) and organizes the ablation around the questions a reader would ask (Section 5.3). It also explains why the main tables stay within a common tuning budget (Section 5.4) and adds four new tables to Appendix D. With all baselines in place, the full LINC keeps the best average rank in every graph group, at a fraction of the cost of the strongest competitors.

We thank you and the reviewers for the constructive discussion.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.