acceptodds
Under review as a conference paper at ICLR 2027

Do Structural Modifications Isolate Compositional Reasoning in Knowledge Graph Completion?

Abstract

Knowledge graph completion models are often credited with compositional reasoning: answering a query by chaining relations along a path. A natural test is a structural modification: the training graph is rewired so that its two-hop paths are destroyed, and a drop in accuracy would be read as evidence that the model used those paths. In this paper, we ask whether this modification isolates composition and find that it does not. The rewiring does remove two-hop rules, as a symbolic rule miner confirms, but it also rewrites up to a quarter of all training triples. To separate the two changes, we build a control graph that is rewired by the same amount but keeps the amount of two-hop structure unchanged. For two path-based models on two benchmarks, including the ULTRA foundation model, this control alone reproduces about three quarters of the drop in MRR. In a grid on CoDEx-S at a fixed edit budget and below the modification's closure loss, the drop follows symmetric and reciprocal triples more closely than two-hop structure. Models with no mechanism for following paths lose more than half as much accuracy as ULTRA under the same rewiring. What remains depends on choices the test leaves open: its size changes with the evaluation metric, and its sign can flip with how the modified graphs are built. A drop under this modification therefore cannot, on its own, show that a model composes. We propose that such studies report a control rewired by the same amount, results on queries with no two-hop path, how the modified graphs were built, and more than one metric. We release our constructions and controls.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
knowledge graph completion, compositional reasoning, evaluation methodology, graph rewiring, matched controls, graph neural networks

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_4ohBOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates whether knowledge graph completion (KGC) models rely on compositional reasoning, primarily in the form of two-hop relational paths. The authors intervene on the training graphs by modifying KG triples, and control the extent of these structural changes using edit distance and two-hop closure. They then evaluate how the performance of KGC models changes under different graph modifications across models and datasets. Based on these experiments, the authors conclude that structural modifications of the graph do not provide a clean way to determine whether a model actually relies on compositional reasoning.

Critical strengths

The paper studies an interesting question, that is, how much two-hop relation paths contribute to the performance of KGC models. The topic is relevant to understanding what structural information these models actually exploit during reasoning.

Critical weaknesses
  • The main conclusion is that the proposed graph intervention cannot cleanly determine whether KGC models rely on compositional reasoning. However, this type of triple modification is not a widely adopted evaluation protocol in existing work. Thus, despite the extensive analyses, the paper mainly shows that this particular intervention fails to isolate compositional reasoning, which limits its significance.
  • Some experimental controls also need stronger justification. In Section 4, models such as DistMult, ComplEx, and CompGCN are used as controls because they do not perform query-conditioned path traversal. However, this does not mean they cannot capture multi-hop relational structure. For example, DistMult uses f(h,r,t)=eh⊤diag⁡(er)etf(h,r,t)=\mathbf{e}_h^\top \operatorname{diag}(\mathbf{e}_r)\mathbf{e}_t as the training objective, while the entity embeddings are jointly optimized over all observed triples in the training graph. As a result, two-hop structures such as (h,r1,t1)(h,r_1,t_1) and (t1,r2,t2)(t_1,r_2,t_2) can still indirectly shape the representations of hh, t1t_1, and t2t_2, even without an explicit path traversal. Thus, performance degradation under rewiring only shows that explicit path traversal is unnecessary for the drop, not that the drop is unrelated to compositional structure.
Questions for authors

Could the authors clarify whether this type of graph rewiring intervention has actually been used in prior KGC work to support claims about compositional reasoning?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 4ohB

We thank the reviewer for the review and for finding the question of what two-hop paths contribute an interesting and relevant one. We agree that this exact protocol is not in wide use, and we agree fully with your point about the controls; the paper is revised around both. We start with your question, because it bears on the first weakness.

Could the authors clarify whether this type of graph rewiring intervention has actually been used in prior KGC work to support claims about compositional reasoning?

We read the question as asking whether the problem we study is real, not only whether our exact rewiring has been used, and answer both.

  • Our exact design, no. To our knowledge, closure-reducing swaps checked against an edit-matched control have not been used to support such a claim; we audit the design before it is adopted (Appendix A).
  • The inference behind it, yes, for claims about paths and message passing. Change the graph, then read the score change as evidence of what the change removed. Li et al. (2023) replace the message-passing graph with a random one and conclude that message passing is not the key part. Shomer et al. (2025) rebuild inductive splits to curb a Personalized PageRank shortcut and report lower scores for most methods. Path explanations of KGC models are scored by removing the explained edges and measuring the change (Chang et al., 2024).

Of the 11 studies in Table 6 that draw conclusions about multi-hop or path structure from a modification or ablation, only Li et al. hold the amount of change fixed, and only by edge count.

[...] this type of triple modification is not a widely adopted evaluation protocol in existing work. Thus [...] the paper mainly shows that this particular intervention fails to isolate compositional reasoning, which limits its significance.

The study matters beyond this one test because the inference behind it is in use, as listed above. For models whose rules cannot be read off, such as ULTRA, a behavioral test of this kind is one of the few probes available. Our checks (the path-evidence audit, edge selection at fixed summaries, and scorers whose computation is known) apply to any structural modification described by aggregate statistics; our results cover our swaps and Li et al.'s experiment.

To show this on a published experiment, we ran Li et al.'s setup with their code and supervision (Table 5, Appendix K). Their finding reproduces that retrained CompGCN reaches MRR 0.357 with the original graph and 0.354 with the random one (theirs: 0.355 and 0.353). Yet a CompGCN trained on the original graph loses 0.0522 MRR when given the random graph at test time. Retraining shows what training can reach, not which evidence a trained model uses, so a matched MRR after retraining does not show that a trained model ignores its graph.

[...] models such as DistMult, ComplEx, and CompGCN are used as controls because they do not perform query-conditioned path traversal. However, this does not mean they cannot capture multi-hop relational structure. [...]

We agree. Embeddings trained on all training triples can encode multi-hop structure without explicit traversal, so a drop of these models shared with ULTRA shows only that traversal is unnecessary for it. We no longer use them as evidence about composition (Section 8; Appendix K for CompGCN).

In their place:

  1. Frozen rule scorers (Section 7). AnyBURL rules are mined once on the original graph and never relearnt. The two-hop scorer uses only two-hop paths, so, apart from filtering, its whole drop comes from two-hop evidence. Yet the edit-matched control reproduces 46.0% [40.4, 51.2] (CoDEx-S) and 52.1% [50.3, 53.9] (FB15k-237) of it. A high reproduced fraction is therefore what a scorer that composes by design also shows, not evidence against composition.
  2. A path-evidence audit (Section 6, Table 1). The edit-matched control keeps closure within 1% of the original but keeps only 86.9% and 72.6% of the labeled two-hop paths are behind test answers.
  3. A synthetic graph where the evidence is known (Section 7, Appendix J). On the 300 queries whose only evidence is a two-hop path, which closes a training triple for only 27 of them, a scorer that only composes scores 0.134 MRR lower on closure-neutral than on closure-reduced [0.080, 0.190]. On queries with both a path and a one-hop shortcut, targeted deletions show that frozen ULTRA's MRR depends mainly on the shortcut.

In short, a drop under this rewiring, even with an edit-matched control, does not isolate compositional reasoning, and Section 8 gives the checks that a study using such a modification should report.

Thank you for your review.

AuthorsOpenReview ↗

Follow-up: short summary of our answers.

Dear Reviewer 4ohB,

Thank you again for your review. As the discussion closes on 18 November, here is a short summary of our answers to your main concerns. The revised PDF and supplement are uploaded; blue text marks the passages that answer review points.

  • Your question. To our knowledge, our exact design has not been used to support such a claim; the inference behind it has, for claims about paths and message passing (Li et al., 2023; Shomer et al., 2025; deletion tests for path explanations). Appendix A (Table 6) documents prior use.
  • Significance. We test that inference on a published experiment: Li et al.'s random-graph result reproduces after retraining, yet a model trained on the original graph loses 0.0522 MRR when given the random graph at test time (Table 5, Appendix K). Retraining shows what training can reach, not which evidence a trained model uses.
  • Controls. We agree with your point: DistMult, ComplEx and CompGCN are no longer treated as non-compositional controls or used as evidence about composition. Frozen rule scorers, a path-evidence audit and a synthetic graph where the evidence is known take their place (Sections 6 and 7).

For anything not listed here, please see our response above. We would be grateful to know whether these answer your concerns, and we are glad to address anything that remains.

Best regards, the authors

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

This paper examines whether performance drops following structural modifications of knowledge graphs provide evidence of compositional reasoning in knowledge graph completion models. It argues that rewiring intended to destroy two-hop structure also changes training facts and other structural properties, confounding the interpretation. Its main contribution is an edit-matched control that approximately preserves aggregate two-hop closure while matching the amount of rewiring in the structure-destroying condition. Across experiments with ULTRA and other models, this control reproduces a substantial portion of the observed performance drop. Additional analyses examine models without query-conditioned path traversal, queries stratified by two-hop support, multiple ranking metrics, and alternative construction rules. The results show that the contrasts depend on these choices, motivating a reporting checklist and the conclusion that structural perturbation alone does not establish compositional reasoning.

Critical strengths

S1. The paper identifies a consequential gap between performance changes and mechanistic claims. Destroying two-hop structure also changes training facts and other graph properties, so a performance drop cannot by itself establish reliance on compositional reasoning. The edit-matched control makes this concern concrete: substantial performance degradation remains even when aggregate closure is approximately preserved. This is a useful methodological contribution, and the authors appropriately distinguish insufficient evidence for composition from evidence that composition is absent.

S2. The empirical analysis examines several complementary explanations for the observed effects. Beyond aggregate accuracy, the paper considers models without query-conditioned path traversal, queries with no initial two-hop support, multiple ranking metrics, and alternative graph-construction rules. These checks reveal that the magnitude and even direction of a contrast can depend on the evaluation and construction choices. This breadth strengthens the case for more careful reporting and provides practical controls for future studies of graph-based reasoning.

Critical weaknesses

W1. The practical significance of the targeted evaluation protocol is insufficiently established. The paper states that none of the twelve surveyed studies uses the specific preserve–break test it critiques. Although showing that such a test can confound structural disruption with the amount of rewiring is useful, it remains unclear which existing claims about compositional reasoning this finding materially challenges. The published intervention examined in Appendix E does not resolve this concern, because the authors change both the message-passing graph and supervision, whereas the original study changes only the former. This limits the demonstrated impact of the audit and weakens the case for its significance beyond a caution about a prospective evaluation design.

W2. The unrecovered construction procedure undermines the interpretation of the headline results. The main preserve, break, and random arms are single constructions whose original builder and acceptance rules could not be recovered. Releasing these graphs permits verification of their scores, but does not establish whether their behavior is representative of a reproducible construction procedure. This is particularly consequential because the paper itself shows that changing the construction rule can substantially alter or reverse the matched-control contrast. Consequently, the headline reproduced shares remain conditional on particular graphs of uncertain provenance, and the reported construction intervals omit variation on the released break side. This substantially limits the robustness and generalizability of the central quantitative findings.

Questions for authors

Appendix B.1 reports that the incremental closure counter used by the matched and ladder builders can incorrectly remove an entity-level connection when another relation between the same entities remains. Although exact recounting establishes the final graphs’ structural properties, it does not establish whether correcting the counter would change the selected graphs or the resulting model performance. Have the main matched-control experiments been repeated with a corrected builder? If so, do the reproduced shares and matched-control contrasts remain consistent with the reported findings? If not, which central conclusions can be supported independently of the affected constructions? This concerns the validity of the current experimental evidence rather than an extension to future work.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 3E6K (1/2)

We thank the reviewer for the careful review, and for noting that the paper separates insufficient evidence for composition from evidence of its absence, which is exactly our claim. In short: the original builder is recovered, the main intervals now cover five runs of it, and the matched controls repeated with an exact counter give the same conclusions (your question, Part 2). Section numbers refer to the revised PDF.

W1. [...] it remains unclear which existing claims about compositional reasoning this finding materially challenges.

To our knowledge no published claim of compositional reasoning rests on this exact test, and the paper now says so (Appendix A). What our findings bear on is the inference it shares with tests in use for claims about paths and message passing: deletion tests that score path explanations of KGC models, Shomer et al.'s inductive splits rebuilt to curb a Personalized PageRank shortcut, and Li et al.'s random message-passing graph all read a score change as evidence of what an edit removed. We test that inference on our swaps and on Li et al.'s experiment; for the other two we offer the checks, not results. Of the 11 studies in Table 6 that draw such conclusions, only Li et al. hold the amount of change fixed, and only by edge count. (The submitted table's twelfth study, Gregucci et al., 2026, splits test queries and neither modifies nor ablates anything, so it is no longer listed.)

The published intervention examined in Appendix E does not resolve this concern, because the authors change both the message-passing graph and supervision, whereas the original study changes only the former.

You are right. We now run Li et al.'s experiment with their code and their supervision (Table 5, Appendix K). Their finding reproduces: retrained CompGCN reaches MRR 0.357 with the original graph and 0.354 with the random one (theirs: 0.355 and 0.353). Yet a CompGCN trained on the original graph loses 0.0522 when given the random graph at test time. So "a random graph does as well" holds for a retrained model, not for a fixed one: retraining shows what training can reach, not which evidence a trained model uses. Section 3 now keeps the three settings apart (frozen; retrained with original supervision, Li et al.'s design; retrained on the modified graph).

W2. [...] The main preserve, break, and random arms are single constructions whose original builder and acceptance rules could not be recovered. [...] the reported construction intervals omit variation on the released break side.

The builder of preserve, break and random (now closure-neutral, closure-reduced and closure-unconstrained) has been recovered. Rerun with its recorded seed, it reproduces the submitted graphs byte for byte on CoDEx-S, FB15k-237, WN18RR and NELL-995; its rules are now in Section 4 and Appendix B. We ran it five times per benchmark, each run with five edit-matched builds, so the intervals in Table 2 now include break-side variation (Appendix F); the edge-selection and query-level intervals use run 1 only (Table 3, Figure 2). The revised supplement contains the recovered builder, the scripts that build every graph variant, and the scripts that regenerate the paper's numbers and tables (see its README).

We also strengthened the pipeline: every builder now rejects any swap that would recreate a validation or test triple. All current variants are built with this check, giving 50 distinct, validated graphs per benchmark, none containing a held-out triple (Appendix B; Appendix D compares them with the earlier variants; see Part 2).

With the current variants the edit-matched control reproduces 70.3% [67.2, 73.9] of the contrast on CoDEx-S and 81.3% [78.1, 84.8] on FB15k-237. Per run it reproduces 69.0–72.7% and 78.6–83.7%, and the control scores above closure-reduced in every run (Table 11).

(Continued in Part 2/2.)

AuthorsOpenReview ↗

Response to Reviewer 3E6K (2/2)

This is particularly consequential because the paper itself shows that changing the construction rule can substantially alter or reverse the matched-control contrast.

We are thankful for this comment, and rerunning the sweep confirms it. The sweep covers two families of acceptance criteria (Appendix B.5, Table 7); we report the edit-matched minus closure-reduced MRR difference (κ in the paper). Relaxing our criterion so that closure-reduced also keeps some closure-neutral swaps (with a probability λ) leaves this difference positive in every run but shrinks it on CoDEx-S from +0.0458 (24.5% of triples replaced) to +0.0083 (45.1%). The submitted version's strict criterion on its own gives +0.0074 [+0.0013, +0.0136] (11.0%); relaxed in the same way, the difference falls to −0.0075 [−0.0131, −0.0022] at λ = 0.6 (30.6%), below zero in every run, and its interval includes zero in between. So at a similar edit share, the two families' differences of opposite sign (−0.0075 at 30.6% against +0.0224 at 35.7%). Sections 5 and 8 now state that the sign of this difference depends on the acceptance criterion, and the reproduced fraction is reported as descriptive only, not as a share of the model's reasoning.

Have the main matched-control experiments been repeated with a corrected builder? If so, do the reproduced shares and matched-control contrasts remain consistent with the reported findings? If not, which central conclusions can be supported independently of the affected constructions?

Yes. We repeated the five matched builds of the submitted version with an exact closure counter and changed nothing else: same seeds, acceptance and stopping rules, preserve and break graphs, checkpoint and filter (Appendix C, Table 8). The first two rows of the table answer your question directly; the last two show the change described below.

Reproduced fraction, MRRCoDEx-SFB15k-237
Submitted variants, earlier counter76.0%78.7%
Submitted variants, exact counter (Table 8)75.3%77.8%
Five runs before the held-out check (Table 9)74.2%81.5%
Five current runs (Table 2)70.3%81.3%
  • "Reproduced fraction" is the submitted version's "reproduced share".
  • Final closure loss stays within the 1% tolerance.
  • At Hits@1 and Hits@10 the fraction moves by at most 1.4 points (CoDEx-S Hits@10: 46.6% to 45.2%; Table 8).

The exact counter changes which swaps are kept, but not the conclusions. Every edit-matched build of the current variants uses it, and every variant's closure is counted exactly, so no central result depends on the earlier counter.

Two results did change when every variant was built with the held-out check (the paper's "held-out rejection"; Appendix D, Table 9). The earlier variants contained 25–110 test triples each on CoDEx-S (317–791 on FB15k-237); without them the reproduced fraction moves as the last two rows of the table show. And ULTRA's edge-selection difference on CoDEx-S, −0.0187 on the earlier variants, is −0.0013 [−0.0081, +0.0062] now, so we no longer make that claim.

Limits we state (Section 8). Two benchmarks, one frozen checkpoint, and CompGCN only for the original-supervision setting.

Thank you once again for the precise questions and your time.

Reviewer_YxggOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper aims to defuse an argument for compositional reasoning in ML models trained for knowledge graph completion (in other words, the paper does not aim to argue for or against compositional reasoning; instead, it aims to criticise an argument for compositional reasoning, without arguing against compositional reasoning). Compositional reasoning refers to models learning that certain "chains" of facts between two graph node/entities "a" and "b" are predictive of a specific link from "a" to "b". The (existing) argument for it is that if model accuracy decreases when such "chains" are disrupted, then this is strong evidence for compositional reasoning. The paper instead shows that there might be confounding factors responsible for the decrease in model accuracy in such experiments. The experiments show that it is possible to reproduce (most of) this loss in accuracy without disrupting the chains.

Critical strengths

Novelty. The paper does seem to carry out a relatively novel study. The alternative structural modifications described in this paper appear to be novel as far as I am aware.

Technical quality (of experiment design) The experimental design uses a wide variety of datasets and models, generally showing a similar and consistent effect across them.

Critical weaknesses

Clarity. The paper is written in a way that is unfortunately unclear and difficult to understand. Many important details are missing or provided much later. For example, the Introduction does not make clear what it means to remove all 2-hops of a graph, or what is the "confound" and "control" alternatives that are proposed. Moreover, it is often hard to understand what the text refers to e.g. "We bring these concerns to interventions on the training graph, where the second pathway can be measured directly." (what concerns? what is the second pathway? What does it mean to measure it?) Finally, the paper often uses rather awkward phrasing, which compounds the previous problems e.g. "Our claim is that this evidence cannot tell whether these models compose, not that they do not." Overall, the paper is hard to follow, so it becomes difficult to identify its main exact claims, their significance, and the evidence for those claims.

Significance. There is no clear motivation for the paper's approach. Neither the Introduction nor the Related Work section (nor the Discussion or Conclusion) explain why the question of whether models reason compositionally matter. The discussion of Related Work is particularly unhelpful as it focuses mostly on concrete methodological differences, without explaining their significance. Moreover, the paper attacks an argument supporting compositional reasoning, but the argument it attacks is quite weak. There are, in fact, much stronger arguments supporting compositional reasoning. For example, the systems Neural-LP and DRUM have been formally proved to use compositional reasoning, since compositional rules can be extracted from them with formal guarantees of correspondence. In other words, we have mathematical proof that some models do use composition to successfully solve the link prediction problem in knowledge graphs. Therefore, even if the paper successfully takes down the argument based on structural modifications, stronger arguments for compositionality remain. (Also, the paper seems to focus only on 2-hop chains, but most literature focuses on k-hop chains).

Technical quality. The description of the modifications to the graphs is lacking in detail. For example, to explain how the "preserve" variants of the dataset is generated, the paper only says that "preserve is rewired to keep two-hop support" - I believe most readers will be unable to understand how exactly the dataset is constructed from this short explanation. Another problem is that the experimental evaluation uses graphs such as FB15k237, NELL995, and WN18RR, which have been studied actively over the past few years and found to have a number of issues, so much so that current state-of-the-art work in Knowledge Graph completion does not place much weight in strong conclusions drawn from these benchmarks. This is not acknowledged in the paper, and the paper does not include any such studies in the review of Related Work.

Questions for authors
  1. Clearly and concisely, what are the main contributions of the paper?
  2. What is the main significance of the results?
  3. What does it mean to remove the 2-hops of a graph? Why focus on 2-hops only?
  4. How exactly do you construct the "control" alternatives of the provided graphs?
  5. Why do you believe that the results obtained on these specific datasets generalise?
5 comments
AuthorsOpenReview ↗

Response to Reviewer Yxgg (1/2)

We thank the reviewer for the careful review, and for noting that the study and its structural modifications are novel and that the effect is consistent across datasets and models. Your summary states our aim exactly: to examine an argument for composition, not to argue against composition. Below we quote each concern and answer it, with the section of the revised PDF where each change is.

Clarity. [...] the Introduction does not make clear what it means to remove all 2-hops of a graph, or what is the "confound" and "control" alternatives that are proposed.

We agree, and we have rewritten the Introduction around this. Before any result, it now explains:

  • The test. The training graph is rewired with swaps (a,r,b),(c,r,d) → (a,r,d),(c,r,b), which keep every per-relation degree. A triple is "closed" if a two-hop path joins its head to its tail. "Closure-reduced" rewiring (formerly "break") keeps only swaps that lower a local count of closed two-paths (a two-hop path plus an edge joining its ends) through the swapped edges, which lowers the number of closed triples. It does not remove all two-hop paths (see Q3).
  • The confound. Closure-reduced also replaces about twice as many triples as the closure-neutral variant it is compared with (24.5% vs 12.9% on CoDEx-S).
  • The control. "Edit-matched" replaces as many triples as closure-reduced while keeping closure within 1% of the original.

Figure 1 shows the core problem on a small graph.

"We bring these concerns to interventions on the training graph, where the second pathway can be measured directly." [...] "Our claim is that this evidence cannot tell whether these models compose, not that they do not."

We have removed both sentences. Every term is defined before use: the test, closure, the control and the contrast in Section 1, the other quantities in Section 3. Each variant is named for what its construction constrains (the former preserve, break, random and matched are now closure-neutral, closure-reduced, closure-unconstrained and edit-matched).

Significance. [...] Neither the Introduction nor the Related Work section [...] explain why the question of whether models reason compositionally matter.

We agree. The Introduction and Conclusion now say why: composition is the design rationale of path-based models and the premise of their path-based explanations, so a test that cannot detect it can mislead both. Related Work now says how rule extraction and removal tests bear on our question, not only how their methods differ, and now covers the benchmark audits.

[...] the systems Neural-LP and DRUM have been formally proved to use compositional reasoning [...] even if the paper successfully takes down the argument based on structural modifications, stronger arguments for compositionality remain.

We agree, and we no longer frame the paper as asking whether models compose. Rule extraction with formal guarantees settles composition where rules can be read off a model. For path-based neural models such as ULTRA they cannot, and a behavioral test is one of the few probes available. The inference we examine, reading a score change as evidence of what an edit removed, is also used beyond our exact test: in deletion tests for path explanations of KGC models and in Li et al.'s random message-passing graph, which we rerun (Table 5). Our checks apply to those uses; our results cover our swaps and Li et al.'s graph, and neither bears on rule-extraction models.

(Also, the paper seems to focus only on 2-hop chains, but most literature focuses on k-hop chains).

The test targets two-hop closure, so two hops is where its claim has to be checked. We also audit labeled three-hop paths and use frozen rule sets with three-atom rules (Sections 6–7). Graphs that keep two-hop closure still change three-hop evidence, which carries the point beyond two hops.

(Continued in Part 2/2.)

AuthorsOpenReview ↗

Response to Reviewer Yxgg (2/2)

Technical quality. The description of the modifications to the graphs is lacking in detail. [...] "preserve is rewired to keep two-hop support"

We agree. Section 4 and Appendix B now give, for each variant, which swaps are proposed, which are kept and when the builder stops. The supplement contains the scripts that build every graph variant. Q4 below summarises the rules.

[...] the experimental evaluation uses graphs such as FB15k237, NELL995, and WN18RR, which have been studied actively over the past few years and found to have a number of issues [...] This is not acknowledged in the paper

You are right. NELL-995 and WN18RR are no longer relied on. The evaluation is therefore narrower than the one you saw, and Section 8 says so; in all eight rows of Table 2 the control still reproduces 46–81% of the difference. We use CoDEx-S, built to avoid inverse-relation leakage, and FB15k-237, whose skewed and fixed-set relations (Safavi & Koutra, 2020) are now stated in Section 8. Related Work now covers these audits (Akrami et al., 2020; Shomer et al., 2025).

Q1. Main contributions.

  1. A natural test of composition, reading a score drop after a graph edit as evidence of what the edit removed, has a hidden confound: the edit that reduces two-hop closure also replaces about twice as many triples.
  2. A control that matches the number of edits but keeps closure reproduces most of ULTRA's difference between closure-neutral and closure-reduced (70% and 81%).
  3. Even this control is not enough. Graphs that agree on every summary we control still differ in the paths a model can use, and rule scorers that compose by design also get high fractions, so a high fraction does not indicate non-compositional reasoning. Retraining can also hide a model's dependence on its graph (Li et al., Table 5).
  4. We release validated builders and checks.

Q2. Main significance. This test cannot answer the question it is built for: a score drop supports composition only if the test also controls the path evidence, which aggregate summaries do not. Section 8 gives the checks to report instead.

Q3. What does it mean to remove the 2-hops of a graph? The test does not remove all two-hop paths. Closure-reduced stops once its running count has fallen by 30%, which leaves 66.9% (CoDEx-S) and 73.4% (FB15k-237) of the closed triples, with every per-relation degree unchanged. On why two hops, see the k-hop answer in Part 1.

Q4. How are the control alternatives constructed? Closure-neutral keeps a swap only if the local count (Part 1) is unchanged; closure-unconstrained keeps every legal swap; both stop after as many kept swaps as closure-reduced. Edit-matched keeps a swap only if closure stays within 1% of the original (or moves back toward it), recounts closure exactly every 200 kept swaps, and stops once it has replaced as many triples as closure-reduced.

Q5. Why do the results generalise? Our main claim is negative: this test cannot tell whether a model composes. Showing that an inference fails needs one valid case, not every dataset, and our counterexample is logical: equal edit counts, closure and degrees do not guarantee the evidence a rule uses; how often they diverge on a given benchmark is empirical. The percentages are empirical, and we claim them only for these benchmarks, this checkpoint and these builders (Section 8). Frequency artifacts are also held fixed in our comparisons: every contrast is between variants of the same graph, and swaps keep every relation's head and tail counts, so FB15k-237's frequency skew is identical in every variant.

We hope these answers and the revised Introduction make the paper easier to follow. Does Section 1, with Figure 1, now make the test and the control clear? If any part is still unclear, please tell us and we will answer before the discussion closes. If there is a benchmark you consider more reliable, please name it: a build takes minutes at CoDEx-S size and hours at FB15k-237 size, and we will report what can be finished in the time left. Thank you again for your careful reading.

AuthorsOpenReview ↗

Follow-up: short summary of our answers

Dear Reviewer Yxgg,

Thank you again for your review. As the discussion closes on 18 November, here is a short summary of our answers to your main concerns. The revised PDF and supplement are uploaded; blue text marks the passages that answer review points.

  • Clarity. The Introduction now explains the test, the confound and the control before any result, with a worked example showing that two rewirings with the same edit count, per-relation degrees and closure can keep or destroy the evidence a fixed two-hop rule uses (Section 1, Figure 1). Every term is defined before use (Sections 1 and 3).
  • Significance. We no longer frame the paper as asking whether models compose; we examine an inference in use for claims about paths and message passing, including Li et al.'s random-graph experiment, which we rerun (Table 5).
  • Technical quality. Section 4 and Appendix B give every construction rule; NELL-995 and WN18RR are no longer relied on, and FB15k-237's known issues are stated (Section 8).

For anything not listed here, please see our two-part response above. We would be grateful to know whether these answer your concerns, and we are glad to address anything that remains.

Best regards, the authors

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of the revision (general response to all reviewers)

We thank the three reviewers for their time and careful reading. They found the study and its modifications novel and the effect consistent across datasets and models (Yxgg); the gap between a score change and a claim about mechanism consequential, with the edit-matched control making it concrete (3E6K); and the question of what two-hop paths contribute interesting (4ohB). The main concerns were clarity (Yxgg, 4ohB), significance (all three), reproducibility of the constructions (3E6K) and the choice of controls (4ohB). We have uploaded a revised PDF and supplement. In the PDF, blue text marks the passages that answer specific review points; other edits, including the revised abstract, are not coloured. The list below gives where each change is, and point-by-point answers are posted under each review.

Clarity (Yxgg, 4ohB)

  • The Introduction now states the test, the confound and the control before any result, with a worked example on a small graph (Figure 1).
  • Every term is defined before use (Sections 1 and 3). Each variant is named for what its construction constrains: the former preserve, break, random, matched and clean are now closure-neutral, closure-reduced, closure-unconstrained, edit-matched and original.

Significance (Yxgg, 3E6K, 4ohB)

  • Prior use is documented (Appendix A, Table 6). To our knowledge, our exact design has not been used to support a claim of composition, but the inference behind it is in use for claims about paths and message passing: change the graph, then read the score change as evidence of what the change removed (Li et al., 2023; Shomer et al., 2025; deletion tests for path explanations of KGC models). We test that inference on our swaps and on Li et al.'s experiment; for the other uses we offer the checks, not results.
  • We reran Li et al.'s random-graph experiment with their code and supervision (Table 5, Appendix K). With the random graph, retrained CompGCN nearly matches its MRR on the original graph (0.354 vs 0.357), as Li et al. found, yet a model trained on the original graph loses 0.0522 MRR when given the random graph at test time.
  • The Introduction and Conclusion say why composition matters. Related Work says how rule extraction (Neural LP, DRUM) and removal tests bear on our question, and now covers the benchmark audits.

Reproducibility of the constructions (3E6K)

  • The original builder is recovered; with its recorded seed it reproduces the submitted graphs byte for byte. Its rules are in Section 4 and Appendix B.
  • Five runs per benchmark, each with five edit-matched builds, so the intervals in Table 2 include variation across builder runs (Appendix F).
  • Every edit-matched build uses an exact closure counter. Repeating the submitted matched builds with it changes the reproduced fraction by less than one point on both benchmarks (Appendix C).
  • Every builder rejects swaps that would recreate a validation or test triple: 50 validated graphs per benchmark (Appendix B). Appendix D reports what this changed.

Controls and evidence (4ohB, Yxgg)

  • DistMult, ComplEx and CompGCN are no longer used as evidence about composition (Section 8; Appendix K for CompGCN). In their place: frozen rule scorers that compose by design (Section 7), a path-evidence audit (Section 6) and a synthetic graph where the evidence is known (Section 7, Appendix J).
  • NELL-995 and WN18RR are no longer relied on; CoDEx-S and FB15k-237 remain, and FB15k-237's known issues are stated (Section 8).

Main result (Section 5, Table 2). With the current variants, the edit-matched control still reproduces most of frozen ULTRA's difference between closure-neutral and closure-reduced rewiring: 70.3% on CoDEx-S and 81.3% on FB15k-237. Frozen rule scorers that compose by design reproduce 46–70% of their own differences (Section 7), so a high fraction does not indicate non-compositional reasoning.

What the paper now claims. A drop under this modification, even with an edit-matched control, does not isolate compositional reasoning: graphs that agree on edit count, closure and degrees still differ in the paths a model can use. Section 8 lists the checks a study using such a modification should report.

We thank the reviewers again and welcome any further questions.

AuthorsOpenReview ↗

Summary of the second revision

We thank the reviewers for the discussion. We have uploaded a second revision of the paper and the supplement. It contains the changes described in our replies.

New experiment in the paper. The targeted-deletion test is now in Section 7 (a summary paragraph and Table L1) and in Appendix L (design, controls and results; Tables L2–L5). For each test query we delete the triples that form its two-hop paths to the answer and compare with deleting as many other triples of the same entity. For all seven models on both benchmarks, the path deletion lowers MRR more than its control. Since our replies we have extended the test: every model is now tested on both benchmarks; a scorer that uses only paths loses nearly all its MRR, while two scorers that ignore paths show no drop; and the result for ULTRA holds under three stricter controls. As the paper states, this shows sensitivity to these triples; it does not identify the computation inside a model.

Clarity. We simplified the wording of the abstract, the Introduction and Sections 3–8. The main concepts are introduced with their motivation and an example, and findings are stated in words before their numbers.

Rule extraction. The Introduction and Related Work now state that rule extraction may be possible for path-based models, that to our knowledge none with formal guarantees has been published for NBFNet or ULTRA in their standard form, and that extraction and behavioral tests are complementary.

Unchanged. The earlier results and conclusions stand, and Tables 1–17 keep their numbers, so the pointers in our earlier replies still apply.

Finding the changes. In the PDF, blue still marks the passages of the first revision that answer specific review points, and orange marks the passages added or rewritten in this one; smaller wording edits are not coloured. The supplement now also contains the deletion scripts, the two dated notes (each written before the runs it describes) and the result file.

Thank you again for your time.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.