acceptodds
Under review as a conference paper at ICLR 2027

Same Knowledge, Different Graph: Knowledge-Graph Foundation Models Are Not Schema-Invariant

Abstract

Knowledge-graph foundation models (KGFMs) are designed to be equivariant to the renaming of entities and relations, a property that supports transfer to unseen vocabularies. We ask whether they are also invariant to how the same knowledge is written down, for instance, as a direct edge, a reified event node, or a Freebase-style mediator. These encodings are not isomorphic, yet each can be made answer-preserving for a declared family of queries. We formalize such schema rewrites and evaluate KGFMs with a context-only protocol in which the background relations outside a fold are rewritten while the held-out queries and their candidates stay fixed. Under reification of the evidence, ULTRA’s mean reciprocal rank falls by 17–55% relative to the original view on six of seven benchmark graphs and its top-1 answer changes on 60–90% of queries; on CoDExSmall, DBpedia100k and WN18RR, where deleting the rewritten facts measurably hurts, re-encoding them costs 0.8–1.3 times as much as deleting them, and a Freebase-style expansion of the collapsed mediator relations of FB15k-237 costs 17%. Two further message-passing models behave similarly. We relate the failure to a receptive-field idealization of the entity encoder and to a removable query-conditioning asymmetry in ULTRA. Among remedies, a learned consistency objective does not consistently improve over augmentation. A structural normalizer with a relation-purity test, when the motifs in use are recognized, recovers near-original MRR and high top-1 agreement on every rewrite we constructed, with residual discrepancies where motifs have low support. It leaves the eight untouched graphs we tested unchanged; incomplete motif recognition remains its main open failure.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
knowledge graphs, graph foundation models, schema invariance, graph representation learning, equivariance, link prediction, robustness, structural normalization

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

This paper studies schema invariance in knowledge graph foundation models (KGFMs). It introduces SCHEMASHIFT, which evaluates answer-preserving schema rewrites using a context-only protocol. The experiments show substantial losses in filtered MRR and equivalent-view consistency (EVC). The authors compare augmentation, consistency objectives, and structural normalization. A blind structural normalizer with a relation-purity test recovers near-original MRR and high top-1 agreement when the relevant motifs are recognized.

Critical strengths

1.Clear distinction between link invariance and schema invariance. The paper identifies an important limitation: invariance to renaming does not guarantee consistent predictions under answer-preserving schema rewrites.

2.Well-controlled context-only protocol. Queries, candidates, and filtered sets remain fixed. Deletion and matched-noise reference conditions, together with experiments across datasets and backbones, strengthen the empirical diagnosis.

3.Effective structural normalization. The relation-purity test reduces false positives, while iterative normalization handles composed reification. For recognized motifs, normalization restores near-original MRR and high EVC without retraining the backbone.

Critical weaknesses

1.Limited evaluation of structural normalization across backbones. Although normalization results for ULTRA cover six KGs, results for MOTIF and TRIX are limited to CoDExSmall, and no normalization results are reported for FLOCK. Extending recovery experiments to the datasets already evaluated for schema sensitivity would provide stronger evidence for the normalizer’s effectiveness across backbones.

2.Dependence on motif recognition. The normalizer recognizes reification and path motifs. Partial recognition remains a major failure, while single-edge mediators and higher-arity encodings remain open.

3.Incomplete verification of normalization. On benchmark graphs, structural checks compare edge and relation counts rather than perform an edge-level round trip. Near-original MRR and high EVC do not establish ranking invariance or score invariance.

4.Incomplete sensitivity analysis. Figure 10 evaluates the purity threshold using structural counts rather than MRR and EVC. The support threshold is compared only at s=1s=1 and s=2s=2, and different pass limits are not evaluated. Further analysis of their effects on MRR and EVC would clarify how reliably the normalizer works under different settings.

Questions for authors

Please see the Weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer M8Cb

W1. Recovery across backbones. Table 3 (main text) and Table 25 (Appendix G.3) add MOTIF and TRIX on WN18RR and DBpedia100k, and TRIX on AristoV4, besides CoDExSmall. Top-1 agreement with the original view after normalization, reified view:

GraphULTRA s=2 / s=1MOTIF s=2 / s=1TRIX s=2 / s=1
CoDExSmall0.989 / 1.0000.938 / 1.0000.999 / 1.000
WN18RR0.999 / 0.9990.999 / 0.9991.000 / 1.000
AristoV40.941 / 0.999not run0.999 / 0.999
DBpedia100k0.993 / 1.0000.992 / 0.9980.999 / 0.999

MRR stays within 0.0013 of the original in every row. The weakest case is MOTIF on CoDExSmall at s=2 (0.908 on the shared-role view), where residual mediators at s=2 are associated with changes in 3–9% of its top-1 answers. Limits: on DBpedia100k the query sets differ by model for memory reasons (2,000–3,000 queries); MOTIF was not run on AristoV4. For FLOCK, the replicate study on CoDExSmall (Table 28) shows that after normalization at s=1, where the graph is recovered exactly, we detect no difference from resampling of the original (excess +0.006, interval −0.005 to +0.018). Partially recovered graphs were not tested with FLOCK.

W2. Dependence on motif recognition. We agree that motif coverage limits the remedy. The normalizer has two predefined motifs. Partial recognition remains its main failure (11–33% relative MRR on uniform views), single-occurrence mediators are left by s=2, and higher-arity structure is outside the library. The Wikidata experiment (Table 27) now measures this on native data: statements with qualifiers are never collapsed, coverage is 71–81% of statements, and recovery is partial (agreement 0.61). The abstract and Section 7 state the remedy as conditional.

W4. Counts do not establish exact recovery. We agree that matching counts is insufficient. We therefore compared the normalizer's output with the original edge by edge on 156 graph instances of eight graphs, as equality of directed labeled edge sets up to a relation bijection (Section 6.2, Table 3; Appendix G.2, Table 24). The normalizer never sees which nodes were introduced; only the validator does.

  • Untouched graphs: unchanged on 8 of 8 at s=2.
  • Reification views: no original entity is collapsed at s=2, but the output equals the original on only 31 of 73 instances, because mediators of keys that occur once remain (27 on DBpedia100k, 75 on AristoV4). At s=1 it is exact on 61 of 73; the 12 failures are DBpedia100k, where 17–25 original entities are removed.
  • Path-shaped views: exact on 13 of 75 with the submitted rule, because of the pooling error described to Reviewer 9veW; 33 of 75 with position-indexed purity at s=2 and 60 of 75 at s=1.
  • Composed path expansion is not recovered by any variant.

The abstract now reports the exact-recovery count (44 of 148 rewritten instances at the default threshold), and the text separates count checks, exact graph recovery and prediction recovery. Our earlier statement that no genuine node was collapsed holds for reification views only and is corrected.

W5. Sensitivity analysis. Figure 11 (Appendix G.4) reports downstream agreement over a grid fixed before scoring: s in {1, 2, 3, 5}, τ in {0, 0.5, 0.7, 0.9, 1}, and three stopping rules, on CoDExSmall, WN18RR and DBpedia100k.

  • Agreement varies by at most 0.001 for τ between 0.5 and 0.9.
  • Support alone (τ=0) fails on WN18RR (agreement 0.21–0.51) and DBpedia100k (0.67–0.94), including on the untouched graphs; τ=1 fails on shared-role views of CoDExSmall (0.32–0.43) and mixed views of DBpedia100k (0.69).
  • Larger s leaves more mediators: on CoDExSmall, agreement is 1.000 at s=1, 0.989 at s=2, and about 0.90 at s=3 and 5; on DBpedia100k, 0.999–1.000, 0.993, 0.988, and 0.985. For τ between 0.5 and 0.9, MRR differs from the original view by at most 0.0015.
  • The six-pass cap and the yield rule agree within 0.002 whenever τ ≥ 0.5.

This is a retrospective analysis of the paper's graphs. The values s=2 and τ=0.9 were chosen after those graphs had been inspected; we have not selected thresholds on disjoint graphs, and Sections 6.2 and 7 say so. WD50K is the only graph in the paper that was not inspected before the thresholds were fixed.

Dear Reviewer M8Cb,

Thanks for your time and effort in reviewing our work. Your comments are valuable to improve the quality of it. As the author-reviewer discussion period will end in about 2 days, we gently request that you read the rebuttal and check whether your concerns are addressed. Thanks again for your time and help in improving the quality of this paper.

Regards from the authors.

Reviewer_M8CbOpenReview ↗

Maintain score

Thank you for your response. I will keep my original score.

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

The manuscript studies whether knowledge-graph foundation models produce consistent predictions across answer-preserving schema rewrites. It formalizes schema invariance and introduces a context-only evaluation protocol that changes background encodings while keeping queries, candidates, and filtering sets fixed. Experiments across seven knowledge graphs show substantial prediction changes in ULTRA, MOTIF, and TRIX, with deletion and noise controls, a Freebase-style expansion, and logical-query evaluations providing additional validation. The paper also analyzes receptive-field limitations and an inversion-related conditioning asymmetry, and evaluates augmentation, consistency objectives, and structural normalization as potential remedies. Normalization largely recovers original performance when the relevant mediator motifs are recognized.

Critical strengths

S1. The context-only evaluation protocol carefully isolates the effect of re-encoding background facts while keeping queries, candidates, and filtering sets fixed. Comparisons against deletion and matched-structure noise strengthen the empirical diagnosis and show that re-encoding can be as damaging as removing the evidence.

S2. The study establishes that schema sensitivity occurs across multiple datasets and three message-passing backbones, rather than being confined to one model. The Freebase-style expansion further supports the relevance of the findings to established KG storage conventions.

Critical weaknesses

W1. The conceptual novelty beyond structural distribution shift is limited. Reification changes path lengths, node degrees, and relation-interaction patterns, all of which directly affect the computations of the evaluated message-passing models. Consequently, sensitivity to these rewrites is reasonably expected from their architectures, even when the underlying facts remain recoverable. Although the controlled evaluation establishes the magnitude of this sensitivity, the paper provides limited evidence that schema invariance reveals a fundamentally new failure mechanism beyond structural distribution shift. This limits the conceptual contribution and makes the empirical diagnosis alone insufficient to strongly support acceptance.

W2. The structural normalization remedy has limited demonstrated generality. The normalizer recognizes a predefined set of mediator motifs and collapses them into direct edges, effectively reversing the transformations used to construct the benchmark. Recovering near-original predictions after approximately restoring the original graph therefore provides limited evidence of robustness to independently occurring schema differences. The purity test helps avoid false positives on the tested graphs, but its effectiveness depends on recognizable motifs and relations concentrated on mediator-shaped nodes; incomplete recognition substantially reduces performance. Without evaluation on naturally occurring alternative encodings involving richer mediator structures, shared events, or qualifiers, the practical applicability of the proposed remedy remains insufficiently established.

Questions for authors

Q1. To clarify the interpretation of the empirical findings, what evidence distinguishes schema-specific sensitivity from the structural distribution shift induced by changes in path lengths, degrees, and relation-interaction patterns? Which reported result most directly supports an explanation beyond these architectural sensitivities?

Q2. To clarify the scope of the normalization results, does any reported experiment evaluate alternative encodings obtained independently of the paper’s rewrite procedure, rather than encodings generated using motifs explicitly covered by the normalizer? In particular, how does the Freebase-style expansion test the normalizer beyond reversing a known construction?

2 comments
AuthorsOpenReview ↗

Response to Reviewer XRMz

Q1 / W1. What distinguishes schema-specific sensitivity from structural distribution shift? Our reification experiments measure structural distribution shift under preserved facts; they do not establish a separate schema-specific mechanism. We have revised the framing accordingly. Reification changes path lengths, degrees and relation interactions together, and no reported reification result supports a mechanism beyond these. The introduction and abstract now state the contribution as a measurement of structural shift when the declared facts and the evaluation task are held fixed, with deletion of the same facts and count-matched random structure as references. The result that isolates a specific cause is global inversion: ULTRA's relation-interaction graph is preserved exactly, yet predictions change, because the relation encoder is seeded at one relation while head prediction reads another (Proposition 1); seeding it at the relation that is read restores agreement to 0.999–1.000 (Section 5.3).

Q2 / W2. Was any encoding obtained independently of the rewrite procedure? What does the Freebase-style expansion test? In the submission, none. The Freebase-style expansion uses real collapsed property pairs but is generated by our procedure, with one new mediator per fact and without the original mediator identities or qualifiers. It tests recovery of a constructed encoding, and Section 5.2 now says so.

We added a test using an externally defined encoding (Section 6.2, Appendix G.6, Table 27). WD50K is a set of Wikidata statements. We instantiate WD50K statements in Wikidata's statement-node layout, preserving their qualifier structure. WD50K does not supply statement identifiers, so we assign the node identities ourselves. We compare this encoding with the usual direct-edge projection on the same queries, with the normalizer's thresholds left at the paper's values.

  • ULTRA's MRR is 0.290 on direct edges and 0.190 on statement nodes, and the top-1 answer changes on 62% of queries. Deleting the same background statements gives 0.228, so the native encoding costs more than deletion.
  • The normalizer recovers part of the loss (MRR 0.255, top-1 agreement 0.61). It collapses 71–81% of statement nodes; statements with qualifiers (11–16%) match neither motif and are never collapsed.
  • With qualifiers removed, agreement after normalization is 0.98 (0.999 at s=1), supporting qualifier structure as a contributor to the recovery gap.

So the sensitivity is present on an external encoding, and the remedy is bounded: it repairs patterns its motif library recognizes. Limits, stated in Section 7: one external encoding, one backbone on it, and the direct view is itself a derived projection of the statements.

Dear Reviewer XRMz,

Thanks for your time and effort in reviewing our work. Your comments are valuable to improve the quality of it. As the author-reviewer discussion period will end in about 2 days, we gently request that you read the rebuttal and check whether your concerns are addressed. Thanks again for your time and help in improving the quality of this paper.

Regards from the authors.

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

The paper investigates whether knowledge graph foundation models are invariant to changes in how knowledge is written and stored, for example, replacing a direct relation with an intermediate event or mediator node. The paper also states that graph representation changes often reduce accuracy in ULTRA, MOTIF, and TRIX, although some results improve.

The authors present a method that keeps the evaluated queries, candidate entities, and filter sets static while rewriting background relations.

The paper describes a query condition asymmetry that affects ULTRA’s sensitivity to global edge inversion. Fixing this issue restores agreement with inversion. For reification, consistency training is not significantly better than augmentation, but a normaliser mostly recovers performance that understands what it is looking for.

Critical strengths
  1. The paper clearly shows how the way a graph is organised can affect the results. The authors keep the questions and possible answers the same and change only how they store the background facts. Several models then perform much worse in some cases; changing the format hurts almost as much as deleting useful facts. This shows an important limitation when using these models with graphs organised in different ways. [Sections 3.3 and 5; Tables 1–3.]

  2. The authors are transparent with the paper limits when stating that Theorem 1 does not apply to real models and that ConceptNet100k does not reproduce the published number. The authors also identify why ULTRA can give different answers to the same question when the graph’s edge directions are reversed. Their fix makes the answers almost fully consistent, with little average change in accuracy after fine-tuning. This gives researchers a concrete improvement to use. [Proposition 1]

Critical weaknesses
  1. The proposed fix does not fully match its stated guarantee. The normaliser can reject a valid pattern that the authors say it should accept. For example, a pattern that appears twice can be rejected because it shares a relation with another pattern that appears only once. The authors need to explain or correct this mismatch. It affects the guarantee behind their proposed fix, but does not overturn the main experimental findings. [Proposition 2(i); Algorithm 1]

  2. Some numbers are difficult to interpret. In ConceptNet100k, MRR increases from 0.061 to 0.154 upon reification, yet the authors offer no explanation. FLOCK is run with a reduced budget, and on Hetionet, its MRR is 0.09 (compared to the 0.246 reported in the publication). A model this noisy can look stable under rewrites simply because it is already inconsistent.

Questions for authors

Does your code calculate purity using all candidate patterns, or only those that appear often enough to pass the first check? How does it handle a pattern that relates to a rarer one, and would correcting the mismatch change any of your reported results?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 9veW

Does the code compute purity over all candidate patterns or only those that pass support? (Proposition 2) Thank you for identifying this issue. Inspection confirms that the implementation counts only candidates that pass the support threshold: the purity of a relation counts its edges at candidates whose key already meets the support threshold, before the purity test. Your counterexample holds. If a role occurs in one key with two instances and in another with one, s=2 removes the second from the count; the role has purity 2/3, and the supported key fails at τ=0.9. Proposition 2(i) and its proof now require that the role's edges are covered by support-qualified candidates, and the counterexample is stated after the proposition in Section 6.2.

Would correcting it change the reported results? The correction narrows the guarantee without changing the submitted algorithm or its reported scores. Computing purity over all candidates instead gives the same normalized graph in 284 of 312 audited settings; the 28 differences are all on DBpedia100k at s=2, where the alternative removes two additional original entities (Appendix G.1–G.2). The original reported scores remain those of the submitted implementation; results for alternative rules are labeled separately.

Additional implementation issue identified in the audit. For the path motif, the submitted code pooled the two positions of a key when counting purity, which we had not disclosed. On path-shaped views this lets original entities with one incoming and one outgoing edge pass as mediators (up to 7,192 on WN18RR). Their facts are restored and predictions do not change measurably (top-1 agreement 0.999 on WN18RR mixed views and 1.000 on the Freebase-style expansion under either rule), but the output graph is not the original. Counting the two positions separately removes the error. We report that variant as new and keep it apart from the submitted results (Section 6.2, Table 24).

ConceptNet100k improves under reification. We agree that sensitivity and accuracy loss are different things, and Section 5.1 now treats ConceptNet100k as an exception. A paired rerun on 2,400 queries (Appendix G.5, Table 26) shows:

  • MRR is 0.061 on the original graph, +0.031 after deleting the rewritten relations, +0.088 with matched random structure and +0.093 after reification. Count-matched random structure produces a similar gain. The improvement is therefore not unique to preserving the re-encoded facts; this comparison does not establish its cause.
  • The gain is confined to queries whose answer has more than 30 edges (+0.149); queries whose answer has degree 1 lose. Twelve of the 13 query relations with at least 20 queries improve.
  • Top-1 answers move toward high-degree entities: median degree 38 on the original graph and 236 after reification (true answers: 43).

These are descriptive associations. They are consistent with a shift toward popular entities that happens to score better on this graph; we did not test that explanation. Our original-view value is also lower than the published one (0.082) for a reason we have not found, although the released checkpoint gives the same 0.061 on the standard split.

FLOCK at a reduced budget may look stable because it is noisy. We agree, and tested the point directly (Section 5.4, Appendix G.8, Table 28). On CoDExSmall at FLOCK's published budget we scored every view ten times with independent sampling seeds (the original twenty times, in two groups) and compared, per query, the distribution of the top-1 answer across views with the same comparison between the two original groups.

  • We detect no difference between renaming and resampling (excess total variation +0.008, interval −0.003 to +0.019).
  • Reification is not: excess +0.106 (0.087 to 0.125), modal-answer agreement 0.595 against 0.713 between the original groups, MRR 0.501 → 0.461. The normalized deficit (NCD) of the same view is only 0.054.
  • Deletion shifts the distribution more (+0.355).

A small normalized deficit therefore coexists with a real change in FLOCK's output distribution. Section 5.4 no longer attributes the smaller deficit to the walk-based architecture. We could not run FLOCK at its published budgets on the larger graphs (128–512 walks per query) with the memory available, so full-budget validation there is still missing; Sections 5.4 and 7 say so.

Dear Reviewer 9veW,

Thanks for your time and effort in reviewing our work. Your comments are valuable to improve the quality of it. As the author-reviewer discussion period will end in about 2 days, we gently request that you read the rebuttal and check whether your concerns are addressed. Thanks again for your time and help in improving the quality of this paper.

Regards from the authors.

AuthorsOpenReview ↗

Anymore concern?

As we approach the end of the rebuttal period, we would appreciate knowing whether our responses and the updates to the manuscript have addressed your concerns. If so, we would be grateful if you could reconsider your rating in light of these changes. We remain available to address any remaining questions or concerns. Thank you in advance for your consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.