How Expressive are Knowledge Graph Foundation Models?
Authors: Xingyue Huang
Pablo Barcelo
Michael M. Bronstein
Ismail Ilkan Ceylan
Mikhail Galkin
Juan L Reutter
Miguel Romero Orth
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Networks
Link Prediction
Expressivity Study
Graph Foundation Models
Primary area: deep_learning->graph_neural_networks
TL;DR: We conduct a rigorous expressiveness study on knowledge graph foundation models and propose a general framework that provably increases their expressive power.

Abstract: Knowledge Graph Foundation Models (KGFMs) are at the frontier for deep learning on knowledge graphs (KGs), as they can generalize to completely novel knowledge graphs with different relational vocabularies. Despite their empirical success, our theoretical understanding of KGFMs remains very limited. In this paper, we conduct a rigorous study of the expressive power of KGFMs. Specifically, we show that the expressive power of KGFMs directly depends on the *motifs* that are used to learn the relation representations. We then observe that the most typical motifs used in the existing literature are *binary*, as the representations are learned based on how pairs of relations interact, which limits the model's expressiveness. As part of our study, we design more expressive KGFMs using richer motifs, which necessitate learning relation representations based on, e.g., how triples of relations interact with each other. Finally, we empirically validate our theoretical findings, showing that the use of richer motifs results in better performance on a wide range of datasets drawn from different domains.

How Expressive are Knowledge Graph Foundation Models?
Xingyue Huang" Pablo Barceló 234 Michael M. Bronstein 15 ismail Îlkan Ceylan Mikhail Galkin
Juan L Reutter 234
Miguel Romero Orth
Abstract
HSRC
Finance
Knowledge Graph Foundation Models (KGFMs) are at the frontier for deep learning on knowl- edge graphs (KGs), as they can generalize to com- pletely novel knowledge graphs with different re- lational vocabularies. Despite their empirical suc- cess, our theoretical understanding of KGFMs remains very limited. In this paper, conduct rigorous study of the expressive power of KGFMs. Specifically, we show that the expressive power of KGFMs directly depends on the motifs that are used to learn the relation representations. We then observe that the most typical motifs used the existing literature are binary, as the representa- tions are learned based on how pairs of relations interact, which limits the model's expressiveness. As part of our study, we design more expressive KGFMs using richer motifs, which necessitate learning relation representations based on, e.g., how triples of relations interact with each other. Finally, we empirically validate our theoretical findings, showing that the use of richer motifs results in better performance on a wide range of datasets drawn from different domains.
Science
research
provide
Bloomberg
Oxford
Girain
MicronTech
Conductors
Poduac
supply
TokyoElectron
Gtest
Figure 1. Training is over relations provide and research, and testing is over structurally similar relations supply and produce.
which can be transferred to novel relations based on their "structurally similarities" to the observed relations.
Example 1.1. Consider the two KGs from Figure I which use disjoint sets of relations. Suppose that the model is trained on Grain and the goal is to predict the missing link produce(Intel.. SemiConductors) in GLest- Ideally, the model will predict the link by learning relation invariants that map produce + research and supply + provide, as the structural role of these relations are similar in the respective graphs, even if the relations themselves differ.
1. Introduction
A
Knowledge Graph Foundation Models (KGFMs) gained significant attention (Galkin et al., 2024; Mao et al., 2024) for their success in link prediction tasks involving unseen entities and relations on knowledge graphs (KGs). These models aim to generalize across different KGs by effec- tively learning relation invariants: properties of relations that are transferable across KGs of different relational vo- cabularies (Gao al., 2023). KGFMs learn representations of relations by relying on their structural roles in the KG,
The dominant approach (Geng al., 2023; Lee et al., 2023; Galkin et al., 2024) for computing relation in- variants is by learning relational embeddings over graph of relations. In this graph, each node repre- sents a relation type from the original KG and each edge represents a connection between two relations. One prominent choice of these connections is to identify whether two relations in the orig- inal KG match a set of shared patterns known as gruph motifs: small, recurring subgraphs that capture essential relational structures within the KG. Figure depicts a simple motif: a path of length two, connecting three entities via two relations (i.e., a binary
Unniversity of Oxford Universidad Católica de Chile 'IMFD *CENIA 'AITHYRA 'Google, Correspondence to: Xingyue Huang <University of Oxford>.
Figure 2. A simple motif a path of length two.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

How Expressive are Knowledge Graph Foundation Models?
motif). For instance, the relations provide and research connected via the entity Oxford in Figure 1, and hence match this motif with the map + provide, B + research.
2. Related work
Transductive and inductive (on node) link prediction. Link prediction on KGs has been extensively studied in the literature. Early approaches like TransE (Bordes et al., 2013), RotatE (Sun et al., 2019), and BoxE (Ab- boud et al., 2020) focus on the transductive setting, where the learned entity embeddings are fixed, and thus inap- plicable to unseen entities at test time. Multi-relational GNNs such as RGCN (Schlichtkrull et al., 2018) and CompGCN (Vashishth et al., 2020) remain transductive as they store entity and relation embeddings as parameters. To overcome this limitation, Teru et al. (2020) introduce GralL, which enables inductive link prediction via the labeling trick. NBFNet (Zhu et al., 2021), Net (Zhu et al., 2023), RED-GNN (Zhang & Yao, 2022), and AdaProp (Zhang et al., 2023), provide improvements by leveraging condi- tional message-passingg which is provably more expres- sive (Huang et al., 2023). These models, once trained, can only be applied KGs with the same relational vocabulary, limiting their applicability to graphs with unseen relations.
We saliently argue that existing models limit themselves to binary motifs, which restricts their ability to capture com- plex interactions involving more relations. We investigate the expressive power of these models, specifically, how the choice of motif's impacts the model's ability to capture relation invariants and help distinguish between different relational structures. Prior works have extensively studied relational passsigg neural networks on KGs (Bar- celó et al., 2022; Huang et al., 2023), but these results do not apply to KGFMs, which is the focus of our work.
Approach. We introduce MOTif-Induced Framework for KGFMs (MOTIF) based on learning relation invariants from arbitrary (not necessarily binary) graph motifs. MOTIF first constructs a relational hypergraph, where each node corre- sponds to a relation in the original KG, and each hyperedge represents a match of relations to a motif in the original KG. Then, it performs message passing over the relational hyper- graph to generate relation representations, which are used in message passing over the original KG to enable link predic- tion over novel relations. Importantly, MOTIF is general framework that strictly subsumes existing KGFMs such as ULTRA (Galkin et al., 2024) and INGRAM (Lee et al., 2023) as detailed in Section 5, and provides a principled approach for enhancing the expressive power of other KGFMs such as TRIX (Zhang et al., 2024) and RMPI (Geng et al., 2023).
Inductive (on node and relation) link prediction. INGRAM (Lee et al., 2023) was one of the first approaches to study inductive link prediction over both new nodes and unseen relations by constructing a weighted relation graph to learn new relation representations. Galkin et al. (2024) extended this idea with the UL.TRA architecture, which con- structs multi-relational graph of fundamental relations and leverages conditional message passing to enhance perfor- mance. ULTRA was among the first KGFMs to inspire an entire field of research (Mao et al., 2024). Concur- rently, RMPI (Geng et al., 2023) explored generating multi- relational graphs through local subgraph extraction while also incorporating ontological schema. Gao et al. (2023) introduced the concept of double equivariant GNNs, which establish invariants on nodes and relations by leveraging subgraph GNNs in the proposed ISDEA framework to en- force double equivariance precisely. MTDEA (Zhou et al., 2023a) expands this framework with an adaptation proce- dure for multi-task generalization. Further, TRIX (Zhang et al., 2024) expands on ULTRA with recursive updates of relation and entity embeddings, and is the first work com- pare expressivity among KGFMs. Finally, KG-ICL (Cui et al., 2024) introduced a new KGFM utilizing in-context learning with a unified tokenizer for entities and relations.
Contributions. Our contributions can be summarized as follows:
We introduce MOTIF as a general framework capa- ble of integrating arbitrary graph motifs into KGFMs, subsuming existing KGFMs such as ULTRA and INGRAM.
To the best of our knowledge, we provide the first rigorous analysis the expressive power of KGFMs. Our study explains the capabilities and limitations of existing KGFMs in capturing relational invariants.
We identify a sufficient condition under which a newly introduced motif enhances the expressiveness of a KGFM within the framework of MOTIF. Using this theoretical recipe, we derive a new KGFM that is prov- ably more expressive than ULTRA.
Link prediction on relational hypergraphs. Relational hypergraphs are a generalization of KGs used to represent higher-arity relational data. Work link prediction in re- lational hypergraphs first focused on shallow embeddings (Wen et al., 2016; Liu et al., 2020; Fatemi et al., 2020), and later G-MPNN (Yadati, 2020) and RD-MPNNs (Zhou et al., 2023b) advanced by incorporating message passing. Re- cently, Huang et al. (2024) conducted an in-depth expressiv-
Empirically, we conduct extensive analysis on 54 KGs from diverse domains and validate our theoretical results through synthetic and real-world experiments.
All proofs of the technical results can be found in the ap- pendix of the paper, along with the additional experiments.
2

---

How Expressive are Knowledge Graph Foundation Models?
ity study on these models and proposed HCNets, extending conditional message-passingg relational hypergraphs and achieving strong results on inductive link prediction.
4. MOTIF: A general framework for KGFMs
We present MOTIF, a very general framework for KGFMs. Given a KG G = (V, E, R). MOTIF computes an encoding for each potential link g(u, v) in G following three steps:
3. Preliminaries
Knowledge graphs. A knowledge graph (KG) is a tuple E, R),, R), where V is a set of nodes, R is the set of relation types and E [ V x R x V is set of labeled edges, or facts. We write r(u, u) to denote labeled edge, or fact, where r E R and triple r(u, v) in V x Rx x V that may or may not be a fact in G. The neighborhood of node U E V relative to a relation r E is (v) == {u] r(u, v) E E).
1. LIFT: Use a set F of motif's to compute a relational hypergraph LIFT=(G) = (Varr, ELeT, BUFT),, using a procedure called LIFT.
2. RELATION ENCODER: Apply a relation encoder on the hypergraph LIFT=(G) to obtain relation representations.
E V. A (potential) link in G is
3. ENTITY ENCODER: Use the relation representations from Step and apply an entity encoder on the KG G to obtain final link encodings.
Relational hypergraphs. A relational hypergraph is tuple G EV,E, R), where V is a set of nodes, R is a set of relation types, and E set of hyperedges (or facts) of the form e = ru11,.... (xx) E E where r E R is relation type, ",,..., up E V are nodes, and k = ar(r) is the arity of the relation r. We write p(e) as the relation type r E R of the hyperedge E E, and e(i) to refer to the node in the i-th arity position of the hyperedge e.
The overall process is illustrated in Figure 3 and we now detail each of the steps.
4.1. LIFT
A graph motif is a pair P = (GM,F), where GM = (VM, EM, Ras) is a connected KG and F is tuple defining an order on the relation set Ras. Specifically, k-ary motif is a motif with motif graph containing exactly k relation types, i.e., [Ryl = k. When k 2, we call it binary motif. The information extracted by motifs is defined via homomorphism.
Homomorphisms. A (node-relation) homomorphism from KG G= (V, E, R) to KG G" = (V', E", R') is pair of mappings h = (I, Ø). where π : V + V and d : R + Rt, such that for every fact r(u, v) in G, the fact (r)( π (v)) belongs to G¹. The image ((G) of h is the knowledge graph ((V),,(E), d(R)), where h(E) contains the fact (T((), (()) for each r(u, in G.
Definition 4.1. Let G be a KG and p= (GM,F) F) be a motif with F == (ri...., Tn). The evaluation Eval G) of P over G is the set of tuples (ø(1)). (o(r)..... ..l))....,,..,,) ((rn)) for each homomorphism h = (I. Φ) from GM to G.
Isomorphism, relation invariants, link invariants. An isomorphism from KG G (V, to KG G² = (V',E" is a pair of bijections (I,, o), where x: :: V and Ø: R - R', such that every fact r(u, is in G if and only the fact (T))( π x())) is in G¹. Two graphs are isomorphic if there an isomorphism be- tween them. For k > 1, k-ary relation invariant is a function & associating to each KG G (V. E, R) a func- tion E(G) with domain Re such that for every isomorphic KGs G and G", every isomorphism (x, Φ), and every tuple F E R² of relations in G, we have (F) = (O(F). A link invariant is a function w assigning to each KG V
The LIFT operation. Given a KG G = (V, E, R) and set of motifs F, the operation LIF constructs a relational hypergraph (VLaer ELPTT RITT) as follows:
The node set is VLnT R. where each node corresponds to relation type from the original KG.
The relation set is RLIFT = F, where each motif P E F is treated as a distinct relation type in the relational hypergraph.
G GV, F, R) a function (G)) with domain V x such that for every isomorphic KGs G and G¹, every iso- morphism (z, Ø). and every link q(u, v) in G, we have (G) v)) = (T)))) (()))(())))))))) (t))).
The hyperedge set ELUT is defined as
[P(r....., rn) PE rn) E Eval(P, G))
where Eval(P, G) denotes the set of all k-tuples of rela- tions in G that match the motif P.
For instance, unary relation invariant & evaluated on Gurann and Grest in Figure may satisfy E(Gmin) ) (research) = E(Gres)(produce if the two relations play analogous struc- tural roles. Similarly, a link invariant w may assign equal values to resfarch(Oxford, Finance) in Guran and produce (Intel, SemiConductors) in Gres under structure- preserving mapping.
4.2. Relation encoder
A relation encoder is a tuple (F, EncLIF)) where F is a set of motifs and EnCLIPT computes relation represen- tations for the set R = VLIFT of nodes of LIFT>(G) =
3

---

How Expressive are Knowledge Graph Foundation Models?
Knowledge Graph G
1. LIFT G with motif set F
2. RELATION ENCODER over LGF
3. ENTITY ENCODER over G
f1
r4
V
u
u
13
P::
r2
T3
33
P2 P
?
T4
Figure 3.
Overall framework of MOTIF(F) over the motif set F: Given query rn (u, v), (OTIF(F) first applies the LIFT, operation to generate the relational hypergraph (VLIT, FLIT. RUFF) over the set motifs F. Then a relation encoder applied to generate relation representation (indicated by color) conditioned on query 71, followed by entity encoder that conducts conditional message passing.
(VLJrT; ELET, BLAT). Given that our aim is encode links of the form q(u, v), the encoding computed by EnCLIFT for relation r E R is conditioned on the relation g E R. These encodings are determined by a sequence of features (4) E Rd((), for 0 S LLS T, defined iteratively follows:
B
Qx
h2r:
(a: 5)
12h:
(a, (3)
αx /
12r:
(ax, (3)
a B
h (0) (g,r) r1y
h h (++1) CP1 (P r/g. (M)),
h2h:
(a:, B)
where I, UP,, AGG1 are differentiable initialization, up- date, and aggregation functions, respectively, and:
Figure 4. The 4 motifs used by ULTRA are shown here. h2r repre- sents "head-to-tail", with the others following similarly. Note that h21 and 12h are isomorphic but with different relation ordering.
M = p(e) (((h)))))) (F, E (e))))
where INIT2, UP2, AGG2, and MSG are differentiable initial- ization, update, aggregation and message functions, respec- tively, v is an arbitrary node in V, and:
I (e, E ELUT(())
In this setting, MSGp(e) is motif-specific mes- sage function and we further define (r = (), e(i) = e E ELJET, 1 S ar(p(()) as the set of edge-position pairs of a node r, and (e)) as the po- sitional neighborhood of a hyperedge e with respect to a position i: (e) = {(e(j).5) j # i, j S ar(()))))
N (M pf/pg
(9) wou..g EnCLIFT, (r)) w E ENG()), RB-
We use EnckG... [u] to denote the encoding of v. condi- tioned on relation q and source node u, which corresponds to h (L) E Rd((1) (L being the number of layers). Fi- nally, a unary decoder Dec : Rd(() + [0, 1] is applied on EnckG. [b] to obtain the probability score for the exis- tence of the potential link g(u, r).
We use EnCLIFT.q[r] to denote the final relation encoding of relation r in G when conditioned on g, that is, the last layer vector (T) Rd((T) r/g
Remark 1. Observe that the relation encoder computes binary relation invariants provided INIT; is an invariant.
Observe that the entity encoder computes link Remark 2.
invariants provided INIT. is an invariant.
4.3. Entity encoder
5. KGFMs captured by MOTIF
MOTIF uses an entity encoder to compute a link-level representation of a KG, regardless of its relation vocab- ulary. This works as follows. MOTIF is defined as a tuple (Encka, (F, EnCLur))), where (F, EncL,F)) is relation en- coder and Enckg is an entity encoder that computes node representations over KGs of the form G = (V, E, RR), con- ditioned on a node ue E V and the relation q, according to the following iterative scheme:
We revisit the ULTRA architecture (Galkin et al., 2024) (See details in Appendix F). The four fundamental relations used in ULTRA can be interpreted as the graph motifs illustrated in Figure 4. Hence, any ULTRA architecture can be repre- sented as MOTIF architecture, with EnCL.FT and EnCkG being specific variants of NBFNets (Zhu et al., 2021).
MOTIF can also represent a slight variant of the INGRAM ar- chitecture (Lee et al., 2023) when we replace the constructed weighted relation graph with KG. Here the construction of
b/o.g INIT2(U, v.g),
(E+1) h boloa
= UP2 (1 AGG2 (N)),
4

---

How Expressive are Knowledge Graph Foundation Models?
LIFT uses a graph motif set F == (((22h1111)1 with Enclir and Encka being variants of GATv2 (Brody et al., 2022), and replace the random initialization in INIT, by an invari- ant function. Note that the definition of MOTIF allows for unconditional message passing (Huang et al., 2023) when both 1 and INIT2 are agnostic to the query q.
for any set F of graph motifs:
(FU
Returning Figure 4, it easy to see that the motifs h2t and 12h are isomorphic. Hence, F= {h2t, 12h, h2h, f2t has the same separation power as {h21, k2h, 121} or {12h, h2h, 121). But although these sets of motifs have the same separation power, this does not imply that the ULTRA architecture can drop either h2t or 12h. Indeed, while the set of links dis- tinguished by any instance in MOTIF(F) is the same as those in MOTIF ((h2r, h2h, 121)) or MOTIF (122h h2h, (21)), the ULTRA framework is strict subset of MOTIF(F), so we cannot directly transfer these results to UI.TRA frame- work. From a practical standpoint, the difference lies in the support for inverse relations: ULTRA bases its relation encoding on NBFNets (Zhu et al., 2021), while MOTIF uses HCNets (Huang et al., 2024), which supports inverse rela- tions by design (see Appendices A and F).
We also note that, while other KGFMs like RMPI (Geng et al., 2023) and TRIX! (Zhang et al., 2024) do not techni- cally fall under the framework of MOTIF, these models do rely on LIFT operation to construct a graph of relations based on a predefined set of motifs, followed by relation and entity encoders. In particular, RMPI constructs an alterna- tive relation graph inspired by the line graph, incorporating the motifs used in UL.TA A along with two additional motifs, PARA and LOOP. In turn, TRIX considers the same set of motifs as ULTRA but employs alternating updates entity and relation representations.
6. Expressive power
6.1. When a new motif leads to more links separated?
MOTIF computes encodings for links in KGs. In this sec- tion, we aim to understand which links MOTIF can separate and whether equipping MOTIF with more graph motifs in- creases its separation power. Hence, our focus is the potential power obtained when using particular set F of motifs. To that extent, we define (OTIF(F) as the set of all MOTIF instances that use a relation encoder built over F, that is, the set of all MOTIF instances of the form (Enoxa, (F, E))L
As a tool to assert when adding a new motif P increases the number of links that can be separated using a set of graph motifs F, we provide necessary condition for the refinement of sets of motifs F and F.. We need some terminology. A homomorphism h = (æ,, Φ) from a KG G (V, E, R) to a KG G' = E', is relation- preserving if R s R' and o(R) = R. Further, a graph is a
core if every relation-preservin homomorphism h from Il Hl is onto, that is, h(1l) H1. It is possible to show the following:
Definition 6.1. Let FF and F' be sets of graph motifs. Then F refines F', denoted F 3 F', if for every KG G and poten- tial links g(u, v). q((n','') over G, whenever every MOTIF instance in MOTIF(F) encodes q(u, u) and q' (ul, v') in the same way, then every MOTIF instance in MOTIF(F") also encodes qu, v) and q'(u', e²) in the same way. Furthermore, F and F are said to have the same separation power if both F F' and F 1 F hold. We denote this as F ~ F.
Proposition 6.3. For every KG G, up to isomorphism, there is unique KG H such that:
HI is a relation-preserving core, and
there are relation-preserving homomorphisms, from G H and from H to G.
Definition 6.1 captures the idea of the potential to separate,
The KG H is called the relation peattion-rreevvinng core of G.
or distinguish, pairs of links in a KG using different sets of graph motifs. Specifically, whenever F 3 F', we know that using F will not result in architectures that can separate links that cannot be separated by any MOTIF instance in ()T On the other hand, F ~ F', then we know that F and F can be used interchangeably without altering the potential for separating links in our architectures.
Our condition is laid terms of a specific notion of homo- morphism that we call core-onto homomorphisms. Formally, homomorphism h (T,, Φ) from G to G' is core-onto if the KG h(G) is isomorphic to the of G'. If such a homomorphism exists, we write G -000 G'. Let us also say that a motif is trivial if its relation-preserving core is isomorphic to the graph with a single fact r(u, v). We are now ready to state the main result of this section. Theorem 6.4. Let F,F' be two sets of motifs, and assume that F F'. Then, for every non-trivial motif P' E F there is a motif P E F such that P -0 P'.
core
We start by observing a simple fact: isomorphic graph mo- tifs do not make a difference in terms of separation power.
Proposition 6.2. Let P = (GM, and P' (G'M,') F') be two graph motifs such that G is isomorphic to GaM-- Then,
See Appendix B for detailed comparison of the expressive powers of TRIX and MOTIF.
To prove this result, we define a coloring scheme analo- gous to the WL-test for relational hypergraphs presented in
5

---

How Expressive are Knowledge Graph Foundation Models?
Huang et al. (2024), which simulates the relation encoding defined by EnCLIFT- We then combine this scheme with techniques from Huang et al. (2023) to produce a coloring for each link in the KG, effectively simulating the encoding provided by Encka (See Appendix C). We show that this scheme is as powerful as MOTIF in its ability to distinguish links over KGs. With this tool in hand, we prove the con- verse of Theorem 6.4: we show how to construct KG G and links qu, v). (u', e²)) such that every MOTIF instance in MOTIF(F) encodes them in the same way, but there is MOTIF instance in MOTIF(F') that encodes them differ- ently, whenever F' contains a motif that cannot be covered with a core-onto homomorphism from any motif in F.
3
ffh: (a,3,7) 7)
(3,,),7) fft:
8
7
ksh: (a,8977)
/3
hftt (a,
Figure 6. The 3-path motifs (FFgth)) ff stands for tail-forwand head, and the rest follows.
r3?
6.2. Consequences for the design of MOTIF models
Consider MOTIF models in MOTIF(F). Theorem 6.4 im- plies that if P & F cannot be covered via a core-onto homomorphism from any motif already in F, then incorpo- rating P into the set of graph motifs used by the architecture should lead more expressive encodings. This has conse- quences for the design of MOTIF architectures.
T3
122
T1
Fa
02
k-path motif. Take a motif representing a path of length l:
Figure 7. ULTRA cannot distinguish between r3(u, 01) and ra whereas MOTIF( can.
Ti (M,, u2), ra (ug, ua).... ................................ T 1.+1)-
For n 2 1. let wh denote the set of motifs formed from changing the orientation of any number of edges rj in the path of length k. with k < n, up to isomorphism. The- orem 6.4 tells us that Fpaih A Fraath whenever n < m, since there is no core-onto homomorphism from any motif with & S edges to a motif with m edges. Hence, every bigger path motif adds power for more expressive encod- ings. Further, the set of motifs used in ULTRA (Figure 4) is F= (12r, 12h, h2h, /2r), which, by Proposition 6.2, has the same separation power as F. (h21, h2h, 121). We can leverage this observation to prove:
edges (shown in Figure 6) to the set of four motifs used in ULTRA enhances its expressive power. As an example task shown in Figure 7, we show that ULTRA with its motifs generates complete relation graph and fails to distinguish between Ti and r2. In contrast, MOTIF(JTal)) constructs hyperedge (r2, T1) but not (F1, T3, T2). thereby differ- entiating between F1 and r2 and solving the task. (See Appendix for detailed proof.)
Furthermore, the core idea of augmenting existing KGFMs via more expressive motifs provably enhance their expres- sivity fits seamlessly in the large bodies of KGFMs in the literature, such as INGRAM (Lee et al., 2023), RMPI (Geng et al., 2023), and TRIX (Zhang et al., 2024), providing an orthogonal avenue for boosting their expressive power.
Theorem 6.5. ULTRA has the same expressive power as MOTIF(JE
k-star motif. As another example, consider the k--sarr motif:
6.3. Comparison with existing link prediction models
TI (11 u), (12, u)...., (kku " u).
3
Existing inductive link prediction models, such as C-MPNNs and R-MPNNs (Huang et al., 2023), can be viewed as special instances of MOTIF with an empty mo- tif set and INIT; being a one-hot encoding of relations. However, this configuration breaks relation invariance on relational hypergraphs. Somewhat counter-intuitee nounterintuiitveely. note that an instance of MOTIF that preserves relation in- variance is inherently less expressive than its corresponding entity encoder EnckG, which acts as a node invariant (but not a relation invariant). This implics, for example, that NBFNet (Zhu et al., 2021) is strictly more expressive than
Figure 5 shows an example of 4- star motif. Once again, the set F of motifs containing all k-stars with S n gives us a hierarchy in terms of separation power, where have that F A Fstur whenever < m. Hence, every wider star motif adds power for more expres- sive encodings.
(a, 6)
Figure 5. The 4-star motif.
A more expressive KGFM. We also present new ways to improve the ULTRA architecture, Adding any motif with
6

---

How Expressive are Knowledge Graph Foundation Models?
ULTRA when measured only over graphs with the same re- lations types. This increased expressive power comes at the cost of limited generalization to unseen relations.
P2
Pa
P1
7. Experimental analysis
P2
72
n1
We evaluate MOTIF over a broad range of knowledge graphs to answer the following questions:
q
73
Q1. Does MOTIF equipped with more expressive graph motifs exhibit a stronger performance?
Figure 8, A example of a KG in one of the synthetic datasets ConnectHub(2). Relations in P are in red and N are blue.
Q2. Does ULTRA have the same expressive power as M)
Table 1. Accuracy for ConnectHub(k) datasets with ULTRA and MOTIF with different m-sttar MOTIF FF for varying k.
Q3. How does a more refined relation invariant help link prediction tasks?
=?
2
3
4
5
ULTRA
0.50
0.50
0.50
0.50
0.50
Q4. What is the trade-off' between expressiveness and scal- ability for MOTIF? (See Appendices H and I.)
Extar
0.50
0.50
0.50
0.50
0.50
F Patar
1.00
0.50
0.50
0.50
0.50
F
1.00
0.50
0.50
0.50
In the experiments, we consider a basic architecture which replaces the relation encoder EncLur by HCNet (Huang et al., 2024) and the entity encoder EncKG by slight mod- ification of NBFNet (Zhu et al., 2021) (see Appendix E).
MOTIF
F
1.00
0.50
0.50
F
1.00
0.50
F
1.00
7.1. Synthetic experiments: ConnectHub
between relations in P and N, failing the task. Empirically, we find that MOTIF(FE with m S and ULTRA only reach 50% accuracy, no better than a random guess, aligning with our theoretical studies.
We construct synthetic datasets ConnectHub(k) to validate MOTIF'S endaceedd expressiveness with richer motifs (Q1).
Task & Setup. The dataset ConnectHub(k) consists of multiple synthetic KGs, where each KG the relations are partitioned into a positive class P. a negative class N, both of size k + 1, and query relation q. Each KG contains (Ista) hub with positive relations, and for each possible subset of relations of P and N of size k, the KG contains a positive and negative k-star community, respectively. An example of such KG is shown in Figure 8 with k = 2. We consider the following classification task: predict whether there exists a link of relation q from the hub center to positive communities but NOT to negative communities. The key to solving this task is successfully differentiating between relations from positive and negative classes. We consider ULTRA and MOTIF(FMaar for varying m, and show the empirical results on these datasets in Table 1. (Further details in Appendix L.)
MOTIF with expressive motifs. We claim that MOTIF(FRM) m with m > k can detect the presence of the positive hub, precisely due to the additional (A: + 1)-star motifs. This allows the model to construct a hyperedge in (G) across all relations in P, while no such hyper- edge exists for N, thus distinguishing P from N. Empiri- cally, MOTIF Fittr) with = k k+1 1 reaches 100% accuracy on ConnectHub(k)) (k), validating our theoretical results.
7.2. Pretraining and fine-tuning experiments
Datasets & Evaluations. For pretraining and fine-tuning experiments, we follow the protocol of Galkin et al. (2024) and pretrain on FB FB15k237 (Toutanova & Chen, 2015), WNISRR (Dettmers et al., 2018), and CoDEx Medium (Safavi & Koutra, 2020). We then apply zero- shot inference and fine-tuned inference over 51 KGs across three settings: inductive on nodes and relations (Inductive e, r), inductive on nodes (Inductive e), and Transduc- tive. The detailed information of datasets, model archi- tectures, implementations. and the experiments are presented in Appendix M. Following convention (Zhu et al., 2021), on each knowledge graph and for each triplet r(u, v),, we augment the correspond-
ULTRA & MOTIF with inexpressive motifs. We claim both ULTRA and MOTIF(J5tr with m S k cannot solve the task on ConnectHub(k). Since the only difference be- tween P and N is the presence of the (k: + 1)-star hub of relations in P. these models cannot detect this higher-order motif. Thus, LIFT>(() will contain two disjoint isomor- phic hypergraphs: one with positive relations and the other with negative relations. This results in indistinguishabiliyy
used in
7

---

How Expressive are Knowledge Graph Foundation Models?
ing inverse r u) where r- is a fresh relation follow filtered ranking pro- tocol (Bordes et al., 2013) and report Mean Reciprocal Rank (MRR), and Hits@ 10 for each dataset. We report both head and tails prediction results for each triplet on all datasets except three from Lv et al. (2020), where only tails prediction results are reported. The code is available at
(v,
(Q1). Our findings on domain-specific benchmarks fur- ther validate the benefits of increased expressiveness. On Metafam (Zhou et al., 2023a), dataset designed to chal- lenge models with conflicting and compositional relational patterns, MOTIF achieves a 45% improvement in MRR over ULTRA in the zero-shot setting. This underscores the model's ability to capture non-trivial relational invari- ants when higher-order motif's are available. Similarly, on WIKITOPICS-MIT (Zhou al., 2023a), where multiple KGs from diverse topics are combined to form a multi-task setting, MOTIF consistently outperforms baselines. Averaged across 8 datasets, MOTIF(J3 improves MRR from 0.331 to 0.358 and Hits @ 10 from 0.442 to 0,481; gains are even more pronounced on certain subsets (e.g.. a 58% relative improvement on MTI-tax). These results confirm that expressiveness improvements translate into practical gains when the structure of the data aligns with the capabili- ties of the underlying motifs.
symbol. For evaluation,
Setup. To evaluate the impact of graph motifs, we construct four variants of MOTIF models with different F: 3-path (F ) 2-path (2 ) {/2t} only, and no motifs (0), de- fined in Section 6. We present the average zero-shot and fine-tuned results of MOTIF over 51 KGs in Table 2. along with the corresponding results for ULTRA taken from Galkin et al. (2024). The detailed per-dataset results of pretrained, zero-shot, and finetuned inference are shown in Tables 7 to 10, respectively. Note that in the zero-shot inference setting, Inductive e, Inductive e, and Transductive are in principle indifferent, as all models encounter unseen rela- tions in the inference graph.
7.3. End-to-end experiments
Results. First of all, note that MOTIF(J) outperforms (OTIF(22 over all 51 datasets on average in zero-shot inference. In the case of fine-tuned inference, a simi- lar trend is present: (JTiF(J consistently outper- forms (oTIF(F1 It is also worth noting that both MOTIF(FM Frath) and (OTIF(FE achieve further perfor- mance improvements after fine-tuning on the training set compared to zero-shot inference. These findings demon- strate that the additionally introduced motifs help the model to learn richer relation invariants (Q1), which are then lever- aged for better predictions on new KGs with unseen nodes and relations. This observation is true on both zero-shot and fine-tuned inference.
We also conduct end-to-end experiments where for each dataset, we train a MOTIF( on the training set from scratch and evaluate its corresponding validation and test sets. We present the average results over all 54 KGs in Table 3 (Full results in Table 11 and Table 12). We continue to see improved performance of MOTIF(F3 over ULTRA due to the additional motifs, allowing models to capture a richer set of information over relations (Q1).
Degradation of relation learning (Q3). As a case study, we focus on the end-to-end experiments with WN-v2 (Teru et al., 2020), an inductive (on node) dataset with only 20 relations after inverse augmentation. The MRR for ULTRA is 0.296, severely lower than that of (OTIF (0.684). To investigate, we plot the cosine similarity² among the computed relation embeddings when queried relations are ro = derivationally related form and r2 hypernym in Figure 9. ULTRA produces highly similar relation represen- tations, whereas MOTIF with richer motifs generates distin- guishing relation representations, aiding the entity encoder in link prediction.
Secondly, recall that MOTIF( and ULTRA have the same expressive power as shown in Theorem 6.5. This theoretical finding is supported in our empirical study, as we see that ULTTR performs similarly with MOTIF (Fgah)) in these experiments (Q2).
Lastly, when it comes to comparing MoTiF(FRelly and MOTIF( ( we observe gradual decrease in all metrics on all datasets as the motifs are removed. This aligns with Theorem 6.4: adding 3-paths on top of 2-paths yields more expressive power on MOTIF since there is no core-onto ho- momorphism from any 2-path to 3-path motifs. Similarly, adding h2h or t2f on top of h2t also yields more expressive power there is no homomorphism from h2t to h2h or f2t. In the extreme case, we observe that removing all of the motifs in MOTIF(0) prevents the model from learning any non-trivial relation invariants, thus exhibiting a complete failure in generalization to unseen KGs.
Nevertheless, we notice that such degradation does not ap- pear in the pretraining experiments, suggesting that either enriching relation learning with diverse motifs or training over multiple KGs could help avoid such degradation.
8. Conclusions
We introduced MOTIF, a general framework that extends existing KGFMs via incorporating arbitrary motifs. In the context of this framework, we studied the expressive power
"The block structure is due to the concatenation of augmented inverse relations.
Results on datasets with complex relational patterns
8

---

How Expressive are Knowledge Graph Foundation Models?
Table Average zero-shot and fine-tuned link prediction MRR and Hits@ 10 over KGs.
Inductive e,
Inductive e
Transductive
Total Avg
Pretrained
Model
Motif (F)
(23 graphs)
(18 graphs)
(10 graphs)
(51 graphs)
(3 graphs)
MRR
H@10 10
MRR
H@ 10
MRR
H@10
||
MRR
H@10
MRR
H@ 10
sero-shot Inference
ULTRA
0.345
0.513
0.431
0.566
0.339
0.494
0.374
0.529
0.349
0.525
0.436
0.577
0.343
0.496
0.378
0.537
MOTIF
0.337
0.509
0.431
0.570
0.335
0.492
0.370
0.527
(h2(}
0.330
0.503
0.422
0.559
0.325
0.482
0.361
0.518
0
0.074
0.121
0.107
0.169
0.054
0.101
0.082
0.134
Finetuned Inference
ULTRA MOTIF
0.397
0,556
0.442
0.582
0.384
0,543
0,410
0.563
0,407
0.568
J
0.401
0.558
0.455
0.594
0.394
0.549
0.419
0.569
0.415
0.565
Table 3. Average end-to-end MRR and Hits@ 10 results over 54 KGs.
of both time and memory (please see the discussion in Ap- pendices H and I). A promising avenue for future work is to enhance MOTIF'S computational efficiency, thus enabling scalability to real-world large-scale graphs.
Total Avg (54 graphs)
Model
MRR
H@
ULTRA
0.394 0.409
0.552
A Acknowledgment
0.561
Bronstein is supported by EPSRC Turing Al World-Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub on Mathematical Foundations of Intelligence: An "Er- langen Programme" for AI No. EP/Y028872/1. Reutter funded by Fondecyt grant 1221799. Barceló and Reutter are funded by ANII-MMillnniim Science Initiative Program CodeICN17002. Barceló and Romero funded by the Na- tional Center for Artificial Intelligence CENIA FB210017, BasalANID.
MOTIF
ULTRA
Impact Statement
This paper presents work aimed advancing the field of Ma- chine Learning. Our methods have potential applications in recommendation systems and knowledge graph completion, among others. While these applications can have significant societal impacts, including improving information retrieval and personalization, as well as potential risks such as bias amplification and misinformation propagation, we do not identify any specific, immediate concerns requiring special attention in this work.
Figure 9. Cosine similarities between generated relations embed- dings when queried relation q and 72 in test of WN-v2.
of KGFMs and identified sufficient conditions under which adding new motifs improves MOTIFS ability to compute finer relation invariants. We thoroughly discussed the im- plications our results on existing KGFMs. The theoret- ical findings are empirically validated on diverse set of datasets.
References
Abboud, R., Ceylan, i. i., Lukasiewicz, T., and Salvatori. T. Boxe: A box embedding model for knowledge base completion. In NewrlPS, 2020.
Our work provides key insights and concrete recipes for designing more expressive KGFMs. However, the typical trade-off' between expressive power and computational com- plexity clearly also applies to our study. While using richer motifs provably increases MOTIF'S expressive power, this may come at the cost of computational efficiency terms
Ba, L., Kiros, J. R., and Hinton, G. Layer normalization. In arXiv, 2016.
Barceló, P., Galkin, M., Morris, C., and Romero, M. Weis-

---

How Expressive are Knowledge Graph Foundation Models?
feiler and leman go relational. In LoG, 2022.
Lee, J., Chung, C., and Whang, J. J. Ingram: Inductive knowledge graph embedding via relation graphs. In ICML, 2023.
Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. In NIPS, 2013.
Liu, S., Grau, B., Horrocks, I,, and Kostylev, E. Indigo: Gnn-based inductive knowledge graph completion using pair-wise encoding. In NeurlPS, 2021.
Brody, S., Alon, U., and Yahav, E. How attentive are graph attention networks? ICLR, 2022.
Liu, Y., Yao, Q. and Li, Y. Generalizing tensor decompo- sition for n-ary relational knowledge bases. In WWW, 2020.
Cui, Y., Sun, Z., and Hu, W. A prompt-hased knowledge graph foundation model for universal in-context reason- ing. In NeurIPS, 2024.
Lv, X., Xu Han, L. H., Li, J., Liu, Z., Zhang, W., Zhang, Y., Kong, H., and Wu, S. Dynamic anticipation and com- pletion for multi-hop reasoning over sparse knowledge graph. In EMNLP, 2020.
Dettmers, T., Pasquale, M., Pontus, S., and Riedel, S. Con- volutional 2D knowledge graph embeddings. In AAAI, 2018.
Fatemi, B., Taslakian, P., Vazquez, D., and Poole, D. Knowl- edge hypergraphs: Prediction beyond binary relations. In IJCAI, 2020.
Mahdisoltani, F., Biega, J. A., and Suchanek, F. M. Yago3: A knowledge base from multilingual wikipedias. In CIDR, 2015.
Fey, M. and Lenssen, J. E. Fast graph representation learning with Py Torch Geometric. ICLR Workshop on Repre- sentation Learning on Graphs and Manifolds, 2019.
Mao, H., Chen, Z., Tang, W., Zhao, J., Ma, Y., Zhao, T., Shah, N., Galkin, M., and Tang, J. Position: Graph foundation models are already here. In ICML, 2024.
Galárraga, L. A., Teflioudi, C., Hose, K., and Suchanek, F. AMIE: Association rule mining under incomplete evidence in ontological knowledge bases. In WWW, 2013.
Safavi, and Koutra, D. CoDEx: A Comprehensive Knowl- edge Graph Completion Benchmark. In EMNLP, 2020.
Schlichtkrull, M. S., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In ESWC, 2018.
Galkin, M., Denis, E., Wu, J., and Hamilton, W. L. Node- piece: Compositional and parameter-efficient representa- tions of large knowledge graphs. In ICLR, 2022.
Sun, Z., Deng, Z.-H., Nie, J.-Y., and Tang. Rotate: Knowl- edge graph embedding by relational rotation in complex space. In ICIR,, 2019.
Galkin, M., Yuan, X., Mostafa, H., Tang, J., and Zhu, Z. To- wards foundation models for knowledge graph reasoning. In ICLR, 2024.
Teru, K. K., Denis, E. G., and Hamilton, W. L. Inductive relation prediction by subgraph reasoning. In ICMI., 2020.
Gao, J., Zhou, Y., Zhou, and Ribeiro, B. Double equiv- ariance for inductive link prediction for both new nodes and new relation types. In arXiv, 2023.
Toutanova, K. and Chen, D. Observed versus latent features for knowledge base and text inference. In Workshop on Continuous Vector Space Models and their Composition- ality, 2015.
Geng, Y., Chen, J., Pan, J. 7., Chen, M., Jiang, S., Zhang, W., and Chen, H. Relational message passing for fully inductive knowledge graph completion. In ICDE, 2023.
Grohe, M. The logic of graph neural networks. In LICS, 2021.
Vashishth, S., Sanyal, S., Nitin, V., and Talukdar, P. Composition-bues based multi nulti-relationa graph convolutional networks. In ICLR, 2020.
Himmelstein, D. S., Lizee, A., Hessler, C., Brueggeman,
L., Chen, S. L., Hadley, D., Green, A., Khankhanian, P., and Baranzini, S. E. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. Elife, 2017.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit. J., Jones, L., Gomez, A. N., Kaiser, L. u. and Polosukhin, I. Atten- tion is all you need. In NIPS, 2017.
Huang, X., Orth, M. R., Ceylan, i. i., and Barceló, P. A theory of link prediction via relational weisfeiler-leman on knowledge graphs. In NeurIPS, 2023.
Wen, J., Li, J., Mao, Y., Chen, S., and Zhang, R. On the representation and embedding of knowledge bases beyond binary relations. In IJCAI, 2016.
Huang, X., Orth, M. R., Barceló, P., Bronstein, M. M., and ismail ilkan Ceylan. Link prediction with relational hypergraphs. In arXiv, 2024.
Xiong, W., Hoang, T., and Wang, W. Y. Deeppath: A reinforcement learning method for knowledge graph rea- soning. In EMNLP, 2017.
10

---

How Expressive are Knowledge Graph Foundation Models?
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful graph neural networks? In ICLR, 2019.
Yadati, N. Neural message passing for multi-rclational ordered and recursive hypergraphs. In NeurlPS, 2020.
Zhang, M., Li, P., Xia, Y., Wang, K., and Jin, L.. Labeling trick: A theory of using graph neural networks for multi- node representation learning. NeurIPS, 2021.
Zhang, Y. and Yao, Q. Knowledge graph reasoning with relational digraph. In WebConf, 2022.
Zhang. Y., Zhou, Z., Yao, Q. Chu, X., and Han, B. Adaprop: Learning adaptive propagation for graph neural network based knowledge graph reasoning. In KDD, 2023.
Zhang, Y., Bevilacqua, B., Galkin, M., and Ribeiro, B. TRIX: more expressive model for zero-shot domain transfer in knowledge graphs. In LoG, 2024.
Zhou, J., Bevilacqua, B., and Ribeiro, B. multi-task perspective for link prediction with new relation types and nodes. In NeurlPS GLFrontiers, 2023a.
Zhou, X., Hui, B., Zeira, I. Wu, H., and Tian, L. Dy- namic relation learning for link prediction in knowledge hypergraphs. In Appl Intell, 2023b.
Zhu, Z., Zhang, Z., Xhonneux, L.-P., and Tang, J. Neural bellman-fort networks: A general graph neural network framework for link prediction. In NeurlPS, 2021.
Zhu, Z.,, Yuan, X., Galkin, M., Xhonneux, S., Zhang, M., Gazeau, M., and Tang. J. A A scalable path-based reasoning approach for knowledge graphs. In NeurIPS, 2023.

---

How Expressive are Knowledge Graph Foundation Models?
A. C-MPNNs and HC-MPNNS
In this section, we follow Huang et al. (2023) and Huang et al. (2024) to define conditional message passing neural networks (C-MPNNs) and hypergraph conditional message passing neural networks (HC-MPNNs). We then follow Huang et al. (2024) to define hypergraph conditional networks (HCNets) as an architecture from HC-MPNNs. We also present their corresponding relational Weisfeiler Leman test to study their expressive power rigorously. For ease of presentation, we omit the discussion regarding history functions and readout functions from Huang et al. (2023). Also, some notations are adapted to simplify the exposition.
A.1. Model definitions
C-MPNNs. Let G = (V, E, R) be KG. A conditional message passing neural network (C-MPNN) iteratively computes node representations, relative to a fixed query R and fixed source node V, as follows:
h (0)
c/lu,g INIT(U, v, g)
h (E+1) UP (1/ AGG l MSG, (h "ln.g" zn)l ) (((U))E)))))
where INIT, UP, AGG, and MSG, are differentiable initialization, update, aggregation, and relation-specific message functions, respectively.
We denote by hig V x V + dRd(() the function h ( (u, v) == h ufa.yy and denote 2n to be a learnable vector representing the query q E R. We can then interpret a C-MPNN as computing representations of pair of nodes. Given a fixed number of layers I, 2 0, C-MPNN computes the final pair representations as hyg (T) In order to decode the likelihood of the fact q(u, 2) for some q E R, we consider unary decoder Dec : Rd(()) + R. We additionally require INIT(U, U, q) to satisfy the property target node distinguishabilliy: for all q E R and e + u E V. it holds that INIT(U, u, 9) * (u, v, q).
HC-MPNNs. Given relational hypergraph H (V, F., R) and a query q = (q, ū, = quu1,' 1,,1, Ue+1 .. Um.)
for & 2 0, an HC-MPNN computes sequence of feature maps (0) as follows: b/q
h (0)
INIT(U, 4), :/q
(E+1) h 1/g
= UP ( (h EMSG (1(h 5) (w,j) E
E(v)B)).
where INIT, UP, AGG, and MSG are differentiable initialization, update, aggregation, and relation-specific message functions, respectively. An HC-MPNN has fixed number of layers L 2 and the final conditional node representations are given by h (L) We denote by ( V - d()) the function h (v) = (ig
vlg"
HCNets. HCNets can be seen as an architecture of HC-MPNN frameworks by choosing appropriate initialization,
aggregation, and message functions. Let = (V, F, R) be a relational hypergraph. For a query = (4, ú, () = q(u1,"' ... U1-1, ? 14411 ), an HCNet computes the following representations for all 2
h (0)
Σ 1 D=u (p: + zy);
b/a
h (E+1) oig
of (w1))
(2)
Σ
Ojys (a (h
( "Glla (1 a a("))))))))))) +b()).
splera
(c.))
where sp(e).g is a learnable message function which is often diagonal matrix, o is an activation function, ( is learnable weight matrix, (2) as learnalle bias term per layer, Z, is the learnable query vector for E R, and L is the indicator function that returns if condition is true, and otherwise. a is learnable scalar and p, to refer to the sinusoidal positional encoding (Vaswani al., 2017) at position i.
A.2. Relational WL tests
To characterize these models' expressive power, Huang et al. (2023) and Huang et al. (2024) proposed the corresponding relational Weisfeiler-Leman algorithms to capture these models exactly.
12

---

How Expressive are Knowledge Graph Foundation Models?
Relational assymetric local 2-WL test (rawlz). Following Huang al. (2023), define the relational asymmetric local 2-WL test (rawlz) follows: Let G (V, F, R) be KG and 7 V V D an initial pairwise node coloring. We say ' satisfies target node distinguishabiiltty if ru(u, u) o mu,, v) for all u + E V. Then, for each f 2 0, we update the coloring
as:
(e+1) (e (0) (u, v) 7,, v), rawl2
rawll2 2 (u, v) = (rau( (u, u), { (rawwl) (u, w), | E NN RB),
where HASII injectively maps the above pair to a fresh unique color. It is shown in Theorem 5.1, Huang et al. (2023) that rawly") is relational WL test that characterizes the expressive power of C-MPNNs, i.e., for all C-MPNN, given any knowledge graph G, 8 2 0, we have rawl!) refines the é layer of this C-MPNN. In addition, given any knowledge graph G, there exists C-MPNN has equivalent expressive power of rawl? for all l 0. (G) (G))
For any knowledge graph G, we will sometimes write rawl
as shorthand of rawlz(G*)) i.c. rawlz applied on augmented knowledge graph G+. Formally speaking, let G = (V, E, R) be knowledge graph. Following Huang et al. (2023), we define its augmented knowledge graph to be G+ = (V, ,,,,E,,), Rtt,, where R+ is the disjoint union of R and R = fr r E R), and E+ = EUU E where E- [rr (r, (v,u) (((, E F, u u)-
Hypergraph relational local 1-WL test (hrwl)). Similarly, following Huang et al. (2024), we define the hypergraph relational local 1-WL test (hrwl1) as follows: Let = (V, E, R) be a relational hypergraph and V + D an initial node coloring. Then, for each l 2 0, we update the coloring as:
hrwl (0) (v) = =(v), (E+1) (fw](f+)) (v) HASH (hrwl((()), (v). (1))(((()) (w) ()) (w, E hrwl
where the function HASH is an injective mapping that maps the above pair to a unique color that has not been used in the previous iteration. When we restrict hrwl, to initial colorings e that respect a given query q == (q, ú)
q(u,,-.. Me-1, "e+1."" ,uk), we say that the coloring e satisfies generalized target node distinguishabiiliy with respect to q if:
clu) c(v) Vu E u. u and cuu)) # c(u,) Vug, uy ü, u4 + uj.
Then, Theorem 5.1, Huang et al. (2024) shows that hrwl2 with initial coloring e satisfying generalized target node distinguishability characterizes the expressive power of HC-MPNNS.
Hypergraph relational local 2-WL test (howl2). Following Huang et al. (2024), if we further restrict the test and apply only on knowledge graphs where all the edges have arity 2 and additionally only with tail prediction, we can instead assign pair-wise coloring
V x V + D satisfying larget node distinguishabiliy, i.e. Vu * c, 7(u, u) * r7(u, v). Then, we define a relational hypergraph conditioned local 2-WL test, denoted as howly. howl2 iteratively updates binary coloring 17 as follow for all é f20 0:
hewl = 1/(u,,) v)
howl, (E+1) (u, v) = HASH (howll)) (u, v). if (((howl) (o..)))) I (c, E E(r)B)
B. Differences between TRIX and MOTIF
TRIX (Zhang et al., 2024) is one of the first works to study its expressivity of KGFMs by comparing it to ULTRA (Galkin et al., 2024). However, our proposed framework MOTIF is inherently incomparable from TRIX in terms of theoretical expressivity.
TRIX enhances expressivity by introducing model capable of implicitly counting the number of homomorphism matches in a knowledge graph. This capability allows TRIX to distinguish between relation pairs based on their frequency of occurrence within specific structural patterns. For instance, consider a knowledge graph with edges
F. = (rr (wi, v1), r2(11, wr) ra(u2, U2), ra(u2, w2), rs (us, Vz), ra (V3, W3)}-
13

---

How Expressive are Knowledge Graph Foundation Models?
Here, the pair (r3, r4) appears twice in 2-hop paths, while (r1, appears only once. TRIX can distinguish between these pairs due to its ability count such occurrences.
In contrast, MOTIF focuses on the existence of specific higher-order motifs within the knowledge graph, rather than their frequeney. This design enables MOTIF to capture complex relational structures that may not be distinguishable through frequency counts alone. For example, consider a knowledge graph with edges
= (1i((1,, (2 22), T1 (I3, 21), (2(23, (1), (11. y2), (y Va). (3 y2), ra(3s, 81)
In this case, the pairs (f1,72) and (ra: r4) may be indistinguishable under TRIX due to isomorphic relation graphs under head-to-head and tail-to-tail mappings. However, MOTIF can distinguish between these pairs by identifying specific motifs, such the PARA motif with edges {a(æ, v), ((x, y)). which maps only to (21,
Therefore, while TRIX excels at distinguishing relation pairs based on frequency counts of specific patterns, MOTIF provides a complementary approach by focusing on the structural existence of complex motifs. This fundamental difference renders the two frameworks incomparable in terms of expressivity, as each can capture relational distinctions that the other cannot. However, note that incorporating higher-order motifs into TRIX could similarly boost its expressivity, highlighting our framework as a complementary way for improving KGFMs.
C. A WL test for MOTIF
We start by introducing a two-stage WL test that matches the separating power of MOTIF(F), for a set of motifs F. Using this equivalence, we show Proposition 6.2 and Theorem 6.4, in sections D.1 and D.3, respectively. Characterizing the separating power of (OTIF(F) via a suitable test, allows us to reason about simpler coloring schemes, which, in turn, makes the proofs more manageable. Also, the equivalence between (JTIF(F) and our two-stage WL test may be of independent interest.
We assume given KG G (V, R, R). Our test assigns one color each link q(u, v), for q R and u, V (recall that links not necessarily facts in G). In the first stage, we color the nodes of (G) (VLIFT, ELITT, RLIFT), that is, the set Vuer = R. When coloring a relation r E R, we always condition on another relation E R. We denote by hcwl the color assigned to r. conditioned on 9. on iteration 2 We assume a predefined number of iterations T 2 O, which will be a parameter of our test. In the second stage, we color the nodes of the KG G, conditioned on a relation g E R and a source node u E V. This determines the final color ( (
(t) F (g, r)
u)) for the link q(u, v). Crucially, the second stage
relies on the first stage in that it uses the colors howl (g. internally. Roughly speaking, the first-stage coloring follows the coloring strategy of hrwl, applied to LIFT (G), while the second-stage coloring follows the strategy of rawlg, after incorporating the relation encodings obtained in the first stage. (see Section for the definition of hrwl, and rawl2).
Formally, the first-stage colors h (4)
are defined via the following rules:
howl (g,r) = 1,=q 1 howl (++ ( (q.r) = HASH (howl (q, E ([(howl((q..s)))))) (q,)), (s, E ((e)). I (e, E ELLr(r)B)
Recall that
(r ((e,1) | e(()) E ELFT, 1 I ar(pe))))
is the set of position
pairs of a node r, and and. (e(()) is the positional neighborhood of a hyperedge e with respect to a
(e) (((() 1 i (
1,=g takes value 1 if r = q. and otherwise. The function HASH is a fixed injective function taking values in the natural numbers.
The second-stage colors col where T T2000 0 is a parameter, are defined via the following rules:
coll (0) ( v)) = I hc (2) (4.44)
col (o(ttt) HASH (aAs(col//))) (col) v)), ( w)), howl ((. | w E (N((), RR).
14

---

How Expressive are Knowledge Graph Foundation Models?
We start by showing that our coloring scheme upper bounds the separation power of any model in MOTIF(F). For simplicity, assume that any model in (OTIF(F) has the form (Enckg, (F, EnCL.F))), where
1. the initialization function INIT) used by the relational encoder EnCLEF is defined INITi (g. 11 r 1 and
2. the initialization function INIT2 used by the entity encoder is defined as (NIT2(U, v. y= h (T)
9999
This is common choice, and in particular, is the choice we take in our basic architecture for the experiments (see Section E).
Proposition C.1. Let G (V, R) be KG and EEnOGG (F, EnCLIF)) be MOTIF(F) instance, where EnCLIFT and EncKG involve T 2 0 and L 2 0 layers, respectively, Then for every pair of links g(u, v) and d'(u', v'), we have that
col 6 v)) = col =
EnokG.u.g/e
EnckG, . l/o'
Proof. We show first the following claim: (f) for every quadruple of relations 9, of E R. we have that
hf (q,r) howl ( (g',
EnCLIFT, EnCLIPT [r']]
Recall that pt is determined by the sequence of vectors h sip
and that EnCLIPT, [s] = h alp"
Take quadruple q, r, R. We prove by induction that for every 0 t $ T, we have that
howll (q, hcwl 30 (d'r')
(1) h (e) r/y r'1g"
For the base case, take 0. Assume that howl ( (q, o' = # and o' * r'. In either case, we obtain (0) For the inductive case, suppose that
howl (0)
r') By the definition of howl either q r and
1/g r 1d 1 = 1d h "1"""
howl (1) (q.r) = howl (d',
h (1) h "1 Nr/g
and assume that (o 1 (g',r'). By the definition of howlyr, it follows that
hewl (g. = howl (3 (g',r") ((((hwl) (q (s,5) E (eee)))) | (c, E (r
([(howl)) (g's & (').)) (8. (N)),, (e, E Fluer(r))
We can apply the inductive hypothesis to the first equation and obtain that h (1) = h " The second equation together with the inductive hypothesis implies that
{ (1 (9) () (8.5) e(((e)) (e, (rm
() ((e))) I (e, E EL
!
As consequence, we have that
M (1(h (t) 1 (s.5) E (c)))) (e, E ELur(r)}
I (MsG (((h () (s' (()))) (e, E (u M
where MSGp(e) is the motif-specific message function used in the (t + 1)-th layer. It follows that
h (++1) UPi (h AGO, (M)) UP, (h / ' AGG, (M')) h h//0
(++1)
r/q
15

---

How Expressive are Knowledge Graph Foundation Models?
required. (UP1 and AGG1 are the update and aggregate functions in the (L + 1 layer.)
Take pair of links ((u,, v) and q'',,, v'). Now are ready to show
col 2 (q(u, v)) yol (d
EnCkG.u. [u] EnCkG, [w/]
Recall that pn is determined by the sequence of vectors h (2) ula.p
and that EnCkG.,,plu) = h (L)
"/2.p"
We show by induction that for every 0 5 é < L, it holds that
col Fr(((u,)) (d
(1)
(1)
In the base case é = 0. Suppose col col (a v)) - (g' (d'( (d'(u, v'),, i... Lo=u howl (g, = lw=w * ho d'). Note that without loss of generality, howly (T) F (a', ()) # O. We then have two cases:
assume that HASH never takes the value 0, and hence howl (T) f (q.9) * 0 and
1. v # u and 2 * u'. We obtain h (0) (0) r/lu.g o' as required.
2. u, v/ = u' and howl (g. (g..))
h (g', ('). By the claim (f), we have that h (7) h (7)
We conclude that
d'lo"
h (0) h (0)
=/uug '' as desired.
For the inductive step, suppose that
Dolu.q
Assume that col col
(E+1) (a(u, )
col ((+1) (g' w')). It follows that
col (6)
F,7 , (alu, v)) (d
(coll w:), (c, E (o) E RD & (col (u', howl ( w wEN(())) Ry.
Using the inductive hypothesis and claim (f), we obtain that
h oluug = h v'''''
(8)
{ (h (9) w
( w E NN()) RD = ( (1
w h
(42)) w w N, RB.
follows that
= (M h w Encr.er,glrl) | EN.(w)), RB = (h w/ EnCL.FT. | EN,(('), RR = N'.
We conclude that
(f+1) e|u,g
= UP2 " AGG2(N)) = up (h vil .f AGG2(N")) = h "pp"
as required. (UP2 and AGG2 are the update and aggregate functions the (E + 1)-th layer.)
We now show that MOTIF(F) can be powerful as test, regarding separating links. Proposition C.2. Let G = (V, F., R) a KG, and let T. 2 be natural numbers. Then there exists an instance (Enckg, (F, Enouur)) of MJTIF(F) such that for every pair of links g(u, v) and g' v'), we have that
(ol u)) (d = EnckG.
EnCkG, of [v'].
16

---

How Expressive are Knowledge Graph Foundation Models?
Proof. It suffices to choose (EnckG, (F, EnCLIF)) such that the functions up(", AGG and MSG (t) pie) defining EnCLIFT, and
the functions UP2 AGG2 (i) and MSG(1) defining Enckg. are injective. Indeed, suppose this condition holds. We prove first by induction that for every r, r' E R and 0 S t T.
(t) r/o = h = howl (q,r) = howlly (d'
For t = 0, the result follows by our assumption on INIT1. Suppose that h (1+1) = h "'po" As up(") is injective, we have that h, (t) ll and AGG!") (M) AGG (M'). A From the former and by induction, we obtain howl (q.r) r) = howl (a', r').
r/g
From the later, as AGO!" is injective, we obtain M MM.. Using the fact that MSO (f) is injective, we conclude that p(e)
{i(h " 5) (s.j) (e)) (e, BLm(r) V (0 (8.5) E (e)) (e, E ELm((r))
By induction, we have
(s. E eN((e)) I (e, E E B- ([(howl 5) (s,5) E (c)) (e, E (L = 0 (( (d. s),5)
This implies that h (g. r) = howl
(++
(t-l) " r') required. Now we prove by induction that for every pair of links
q(u, v) and (w(w,, r'), and 0 s f S I., it holds that
h 1/ h (4)
col (0) col)))(((,,))) = (d'("',
Note that this implies that
( (r = (d (d' col
Enckg, a.go]] = EnCKG, on. [v]].
The implication holds for by the assumption on INIT2 and the fact that (T)
h (T)
hf (q.9)
g/e
"''4"
h (g', (d',4') Assume that h h = h (8+1) "/' As UP2 is injective, we have that (1)
h ou and (
2GG (2) (N'). From the former and by induction, we obtain fo v)) = ( (u', v²)). From the later, since (2)
AGO2 is injective, we have N = N As (S is injective, we obtain that
(h h r/q) w ENG(U), RD- (h or (T)) w N, RB.
w/u.q
By induction, we have
I (coll)) (all, v)), hewl (2) (g. r)) w (EN RD =
howl (l.,)) w EN..))) Rj.
This implies that col
(e+1) y. (g(u, v)) = coll (d r²)) as desired.
p(e)* up(") AGO!") (Sa For instance up and Up) can be vector (f) (t) can be chosen using Lemma from Xu et al. (2019) (see also Lemma VIII.5 from Grohe (2021)). Another alternative is to choose up(") Aca(") (s
is easy to find injective funtions (") AGO (1) MsG concatenation, and A
(t)
(s p(e)* AGO!
p(e) according to Theorem 4.1 in Huang et al.
(2024), and (0) AGG (f) (S according to Theorem 5.1 in Huang et al. (2023).
As direct corollary of Propositions C. and C.2, we obtain:
Corollary C.3. Let F and F' be two set of motifs. Then F 3 F' if and only ffr every KG G EV,E, and link q(u, v). (ul, d'), whenever col (L) ( u)) = ( (g'd', (u', u')) for every T, L 2 0, then (q(u, v)) = (g (ul, for every T, I. 0.
17

---

How Expressive are Knowledge Graph Foundation Models?
D. Missing proofs in the paper
D.I. Proof of Proposition 6.2
Let P = (GM,F) and p = F') be two graph motifs such that G is isomorphic to GMM- Then, for any set F of graph motifs:
(FU ~ (FU(P)) (FU(PPP').
Proof. We only show that (FU (FU P))), the part that (FU (F (P'))) is analogous.
For readability, let write F FU and F2 FU FU, Further, E1 and Eg correspond to the edges of LIFT,, (G) and LIFT,, (G), respectively.
We make use of Corollary C.3, and show that for every KG G = (V, E, R), every pair of links q(u, v), o' (u', v²) and every T, L 2 0,
col coll LL) Ar u)) = col
( 2o (a('l, + Soll u)) =col (
By definition of the second stage colors, all we need to show is that for every s' R.
howl Cool (g. 8) = (d 8') = howl (g, howl (2) (')
Once again, we only need to show one direction, the other one is analogous. We prove the (=) direction by induction on < 1 < T. The base case is immediate because the inizialization does not depend on Fi or F2. Assume then this condition holds for all f T. On step let q, s and q', be pairs satisfying the left hand side. According to the coloring step, hc
F22 (q, s) and the multiset of the colors of all neighbours of q in any tuple in any relation in F1. For F2, the color is the same except we include
5g sq corresponds to the hash of pair given by the previous color howl
N ({(howl)) (0) Fg (g. x).5) I (x, E (i(')) (P). (2)))
where (s) is the set of pairs (e, where i edge in Egg and e(i) s. Hence, since this is the only term that differs from the coloring according to F1, to prove the right hand side, it suffices to show that the above multiset is the same as
{l (howll
(2) F2 (d', (1)))),))) a'))")) (x',5") E (P'))
I (P', 1' E E2('
Now, because of isomorphism, there a bijection / that maps each index position i of r to a position f(i) of f", in such a way that a pair (P, i) is in (s) if and only if (P", f(i) is in Es)s. Further, for every fact P(ri...., rr) in LIFTA, (G), there is a fact P(rí..... :7hh such that r; (1). Hence, for every pair (x, E (P'(P'), (P',k) E2(s), there is pair (x,p) in N (P)) (-10) E Ei. By induction, since howl (1) howl (t-1) must then correspond to the color of some node (g', in (P), (P. E Es(s). Once again, by isomorphism, find the pair (x', E (P'(P)), (P', k) Eg(s'), where by induction the color of (g', x²) by howl now corresponds to that of (g, at). This proves bijection between all elements in the multiset, from which we directly obtain that howl F2 (q, s) = howl (t)
Fi (q, howl
(1) 3. (d', s'), the color of (q, by
Fg (d),
D.2. Proof of Proposition 6.3
For every KG G, up to isomorphism, there is a unique KG H such that:
is a celation-preservee core, and
there are relation-preserving homomorphisms from G to H from H to G.
Proof. Let us assume there are two such cores Hi and H2. Since there are relation- preservvig homomorphisms from G to H, from G to H2, from H, to G and from H2 to G, componing these homomorphisms establishes there are relation- preserving homomorphisms ff from H₁ to H2 and g from H2 to H1; note that the composition of two celation-presertie homomorphisms is also peation-preserving homomorphism.
18

---

How Expressive are Knowledge Graph Foundation Models?
But now I g is relation-preserving homomorphism from H₃ H2 and g o s' is a homomorhpsim from H2 to H2. This means that f o 9 and go f are onto. Moreover, since they are endomorphisms, they must be automorphism. Hence, f and g are both onto, which means that H1 and H2 are isomorphic.
D.3. Proof of Theorem 6.4
Let F,F be two sets of motifs, and assume that F 3 F. Then, for every non-trivial motif P' E F¹ there is motif P E F such that P -0 P
Proof. We prove the converse of this statement: assume that there is a non-trivial motif P E F' that does not satisfy the conditions of the Theorem, that is, that there is no motif P E F such that P 4000 P'. We show how to construct a KG G and pair of links q(u, v) and q' ('',,, v²) such that coll.: v)) = c (el'(((('''))) o')) for every T, L 2 0, but
col (a v)) + col co (q v²)), for some T, L 2 0. This, by Corollary C.3, suffices for the proof.
Let us write P'= (Grr, P'). We split the proofs into two cases, depending on whether there exists motif P' in F such that there is no homomorphism from any motif P in F to P".
Case 1. Assume that F' contains a motff P' such that there is no node-relation homomorphism from any motif P in F to P'. Notice that this implies that all motifs in F cannot be mapped to the trivial motif with just the fact Y 2), as otherwise, we would have motifs in F that can be mapped to any edge in P", resulting in a node-relation homomorphism to motif pl.
Let y be an arbitrary relation in p' and a fresh relation. Construct G by taking Gp plus two triples y. (a. and s(c, d), with a, b, c, d fresh nodes. We claim that coly> (G, y(a, b)) F coly (G, s(c, d)) but coly (G, y(a, b)) col (G, d)c which is what we were looking for.
By our assumptions it follows that LGF is graph without relations, as there are no homomorphisms from any motif in F to G. Therefore, we have that hcwl, (v) = hc) over LIFTy(()): in both cases the hewl coloring involves a single node with the same color, not connected to any other node, so we stop after just one iteration. In turn, this entails that (yla(y(a, b)) = (sle d)), as once again nodes a, b and c, are not connected to any other part in G.
On the other hand, LIFT (G) contains at least one tuple with distinct elements in the relation Rp corresponding motif P", consisting of F': this comes from the identity homomorphism from P' to Gpr. But since P' is non aoivirivial, there cannot be a relation- preserving homomorphism h from P' to the graph formed just by fact s(u, u). as this would entail that the relation preserving core of P' is indeed s(u, v). and hence p' would be trivial which we assumed otherwise. Then, there cannot be a tuple of different relations that includes s in relation Rp in (FFTT((G) This entails that the color howl, (v) and hcwl, (s) over LIFT (G) are already different after the first step. Hence, col (y(a, 6)) * coly (s(c, d)) as promised. Case 2. Next assume that there is motif Pr in F' such that there are no core-onto homomorphisms from any motif P in F to P (but there may be regular node-relation homomorphisms).
Let then H contain all different motifs (up to isomorphism) h(P) = (M(F) such that P E F and h is a homomorphism from P to the relation preserving core of P' By our assumptions, none of these homomorphisms is core-onto. Define two functions fi and f2 that map each relation name from a motif in H to a fresh relation, and that are the identity on nodes. Further, construct a graph G1 as follows: for every motif h(P) in H, replace every node in (i(())) by a fresh node and add it to G1. Construct graph G2 in the same fashion except we use fa(h(P)). Finally, extend fa to be the identity on all other relations in (P") (recall that P' = (F', Gpr) not in any motif in H, that (P') is well-defined motif and its corresponding graph (Pr) is well defined graph.
Our graph G corresponds to the union of G1, G2 and (Pt). Clearly, G, and G2 are isomorphic, let g be one such isomorphism. By construction, we also have that LIF))((1) is isomorphic to (G2)) and LIFT is isomorphic to LIFFTr((G2)
For an arbitrary motif H and fact y(2, =) of this motif, consider facts fi (v) b) and (2(v) g(b) in G and G2, respectively, that result from processing triple y(æ, 2) in this motif according to our construction (here all of a, b, g(b) are fresh nodes). As in Case 1, we show that these triples are separated by col' but not by coly.
*Slightly abusing the notation, we use h(Gr) to denote the motif in which every fact b(a, c) is replaced by (MB((( ((c).
19

---

How Expressive are Knowledge Graph Foundation Models?
First, note that (G) (G)) U LiFT)) as (1) 11 and G2 are not connected, and (2) any homomorphism h from motif P F to G1 (Pr) has a corresponding homomorphism he from P to G1 such that h(P) and h" (P) are isomorphic, and therefore any tuple in the relation Rp in LIFT=(G, U G ((P))) is also in the relation Rp of Li)T>(G)).
The fact that LIFT=(G)= = LIFTx(Gr) U (G2), that LIFT=((1) and LIFT= are isomorphic and that they are not connected establishes that howl, (1 = (22())(((((())))))) for any relation name X in G. Then, again since both connected components in LGF are isomorphic, and our game is invariant to isomorphisms (assuming the same coloring of relations), it must be the case that col (f))(f()))), b)) = (fl=(ff(Y) g()))
Let us now look at y (G). Notice first that any tuple t in Ry in LIFT (G2) has corresponding tuple fz oT in LIFT> (G.). In other words, f2 fT² is a bijection from LIFT (G2) to LIFT (G, U ((())) whose inverse is fi o S2- This is because these tuples arise from homonorphisms that start from P' and end in some motif in H, and both G1 and G2 have the same copy of this motif.
To finish we claim that there one tuple t in relation Rp in graph LIFT U GR(P)) such that fi o f2 (t) is not in relation Rp in graph LIFT,(G22) This means that for any element r in & the cardinality of edges in Rp where r participates strictly higher than the cardinality of edges where fi o f2 - (r) participate, which implies that (s) A
howl hor (r) (f1 o f2" (s)) for any relation name that belongs to t because the color in step (1) is already different. As in Case 1 above, this can be used to show that coly (fi (a) 6)) + co (fa()))
The tuple corresponds to (r'). This tuple exists in relation Rp in LIFT (G1 (Pn) because fiis a homomorphism from P' to (((P') We show that LIFT (G) does not contain any tuple consisting of all different nodes from f2("") in relation Ry", which suffices for claim. Note that this implies that all relation variables from P' are in the preimage of f2 (i.e., are part of motif in H), otherwise the claim is obvious as the size of F' is bigger than the range of f2.
Suppose for the sake of contradiction that such a tuple fF') is in Rp. By construction, any tuple from elements in f2(F') must come from LIFT (G2). Hence, tuple f2("") is added to LIFT>((G) due to a homomorphism h from P' to motif h(P) in H (for a motif P in F and a homomorphism h from P to the core of P'), and since the tuple contains all elements in f2("",, this homomorphism h is relation preeeion....rriing.. By composition of homomorphisms this also entails celation-preserving homomorphism from the (relation prattion-prerrving) core of P' to h(P).
Further, since h is a homomorphism from P to the caatioon-reserving core of P", the identity is a homomorphism from M(P) to said core of P', and since h(P) contains all relations in fa(F'), this homomorphism is also celation-presevvv This is contradiction because we have found that h(P)) is the relation preserving core P and therefore is a core-onto homomorphism from P to p'.
D.4. Proof of Theorem 6.5
ULTRA has the same expressive power as MOTIF(I5
Proof. By Proposition 6.2, we show that MOTIF((h2t, h2h, t2tt) and MOTIF((t2h, h2h, t2t}) has the same expressive power as MOTIF MoT1F((h2t, r2h, h2h, 12f)). We also note that (12h, h2h, r2t} and (h2t, h2h, 12t) are the same as F Thus, it is enough to show that ULTRA, in its general form, has the same separating power than MOTIF(F), where F= {h2t, t2h, h2h, f2t).
Recall that the separating power of MOTIF(F) can be characterized by the coloring scheme coly defined in Section C. Following the same strategy as in Propositions C. and C.2, is straightforward to show that the separating power of ULTRA matches the following test.
Let G = (V, E, R) be a KG. The first-stage colors rcol ultra are defined via the following rules:
rcol (0) ultra (g.r) = 1 r=g 1
rcol((t)) (q.r) = HASH (rool (1) Ccral (q, r). of (rcol Mire (q. ('),r)),))))))) (Lu))) | r' E NN (r), E BL
1,=g takes value 1 if r = q. and 0 otherwise. The function HASH is a fixed injective function taking values in the natural numbers.
20

---

How Expressive are Knowledge Graph Foundation Models?
The second-stage colors ecol!t) (2) u where T 2 is a parameter, are defined via the following rules:
(T) ecol u (1(u, u)) = 1=== * ultra (g, q)
ecol ultra, (q(u, u)) HASH ecol (t)
ultra, ultra (q u)), { (ecol (f) u (q(u,, w)), rcol ultra (q.r)) I EN(o),, Ri).
We aim to show that for every links ((u,, v). q (u', e') and T, L 2 have
ecol (L) ultra. T (q(u, v)) = ecol ( 7 (d' e')) +
(
Since the definition of the second-stage colorings ecoluitra, and colæ, are identical, it suffices to show that for every q, r, o, r' E R. and every 0 s t T, it holds that
rcol()) ultra (g,r) rcol (1) ultra
(') = hewl (q,r) h (4': r').
This propositions follows from the following observations. The update rule of (t) ultra coincides with the one of rawl!
(defined in Section A) applied to LIF On the other hand, the update rule howl coincides with the one of howl
(defined in Section A) applied to (G). It follows from Theorem H.4 in Huang et al. (2024) that rawl;" (4) is equivalent to howl?" ( Here rawl; (t) corresponds to the test rawlz (1) applied to the augmented graph G+, which extends each fact r(u, v) in G' with its inverse fact r- (v, u) (see definition in Section A). The key observation is that over LIFT=(G), the test rawly (t) and rawl;"" (4) are also equivalent. This is because of the structure of F = {h2t, 12h, h2h, 12t), as observed in Appendix F: The relation 1:2h is symmetric, and hence 12h (g,r) E LG) = h2h(g, r) LIFT=(G)++ Similarly for t2t. On the other hand, h22(ggr) LIFTx(G) + +2h(r,g) LIFT=(G). Hence, h2t (q.r) E LIFT=(G)+
12h r) E LG)+ Similarly for t2h. Therefore, adding inverses over LIFT>(() is superfluous, and rawly" (f) and rawl are equivalent. We conclude that rawlz (1) and howl," are equivalent, and then rcol(!) as required.
(t)
ultra and howl are equivalent,
E. MOTIF architecture
In this section, we will introduce the architecture of MOTIF used in the experimental sections. We adopt HCNets (Huang et al., 2024) as the relation encoder for the relational hypergraphs, and following ULTRA (Galkin et al., 2024), we adopt a slight modification of NBFNet (Zhu et al., 2021) as the entity encoder.
Model architectures. Specifically, for the relation encoder, we have that for S < T.
h (0)
r/g 1 r= 1d
(t+1) r/g
(W(O)
h co
Σ
20)
o (O)H ple)
(a (n "0 (1-a("))p;) b(o))
(um))
For entity encoder, we follow ULTRA (Galkin et al., 2024) and adopt the same variation of NBFNet (Zhu et al., 2021), which computes the pairwise representation follows for 0 < f < L:
h (0)
(T)
c/u.q 1e=u
*
7/g
h (6+1) u.q
(()
h (0)
ΣΣN
h (0) wlu.q
(LP(0(((()) + +b(0).
(ERmENN.(1)
where is ReLU activation, W and are learnable weight matrix and bias term per layer, 1d is all-one vector of d dimension, and 1 is the indicator function that returns 1 if condition C' is true, and 0 otherwise. We denote scalar multiplication, and @ element-wise multiplication of vectors. In the relation encoder, note to be a learnable scalar and p; to be a learnable positional encoding at i-th position. Finally. we decode the probability of a query g(u, v) by passing through representation (f.) through Multi-Layer Perceptron (MLP). o/u.q
21

---

How Expressive are Knowledge Graph Foundation Models?
F. ULTRA
In this section, we follow Galkin et al. (2024) and define ULTRA, KGFM that computes invariants on nodes and relations on knowledge graphs.
Model architectures. Given knowledge graph G (V, E, R, c) and query quu,?, ULTRA first constructs knowledge graph LIFTx(G) (VLur, ELITT RLIF)) with each node representing a relation and 4 fundamental relations in RLIFT
defined as follow:
tail-to-head (t2h) edges, 12h(r1, r2) ELIFT +
3u, w, V,niu, ()) Ag(e,,))
head-to-head (h2h) edges, h2h(r1,72) ELIFT
Eu, w
head-to-tail (h2t) edges, h2t((1, ELIT
Bu, u, (,r((e,)) Ar(
tail-to-tail (12r) edges, (2((11, r2) E ELITT <
Eu, w w (,ri(,,)) A (2(
Then, ULTRA applies a relation encoder to generate representation hegg via a variant of NBFNet (Zhu et al., 2021) that initialize with all-one vector 1st on the queried relations E VLrT. For S t S T, the relation encoder iteratively computes h (4) as follow:
hrlg 1 rmg 1d
(0)
h (++1) a ( 1
Σ Σ
h c 2 + +b(1))
rlg
E r'ENRum (r)
where Sraer learnable vectors for each of the fundamental relations, a is ReLU activations, and similar previous notation, || stands for concatenations, and (+() and (+t) are learnable weight matrices and bias vectors for each 0 S t T,
correspondingly.
Finally, after the relational embedding (T) is obtained given the query q(u, ?), ULTRA proceeds to computes the final o/g
pairwise embedding for ll L:
(0)
1 v=u h (T)
u/ou.
h (4+1)
(w())
(U)
ΣΣX
Σ
h h0 "eliag
(h +b()).
o/u.q
vll.g
WER
Frameworks. We follow the notation of MOTIF and write ULTRA its most general form. Later, will also use ULTRA to refer to this general form when the context is clear. For the relational encoder, have the following form:
h 1/g INITI (4,r)
h (++1) UP: (h 7/ AGG1 ( MSG (1 E (T,, TLIT E BLIFT r/g
r/p
INIT), UP1, AGG1, and MSG, are differentiable initialization, update, aggregation, and fundamenaal-reaaioossseeiiii message functions. respectively. Similarly for the entity encoder, we have this format:
h(0) v/u.q
INIT2(U, v,
(e+1)
(P
(0) 8 u.g. AGG2 MMss( w|u.g" ((P (i RB))),
where INIT2, UP2, AGG2, and MSG are differentiable initialization, update, aggregation and message functions, respectively.
Characteristic of fundamental relation. We also identify a few characteristics of the fundamental relationship from ULTRA when constructing the relation graphs:
1. Self-loop. 42h and t2r always exist for all relation, i.c., Vr E R, h2h(r,)) (2t(r, r). This will induce two self- for all relation.
22

---

How Expressive are Knowledge Graph Foundation Models?
2. Symmetric. Relation h2h and 121 are symmetric: If h2)()1,12) E ELUT then must have h2) E ELIFT as they satisfy the same assumption for homomorphism. The same applied for 12t.
3. Inverse. Relation h2t and 12h are always inverse relation to each other, i.c., if h2r(11,72) E E then we must have r2)( m1) E ELIFT, as they satisfy the same assumption, and vice versa.
As standard practice, current link prediction models augment the knowledge graph via inverse relations. However, adding inverse relations implies lot of symmetrical edges in the constructed relation graphs. First, note that for every r(u, E. we have r-1 (c, u) E E= Thus, by default, we have that (2h(r, r1), h2t(r, 1,22 (rr() 22)( BLIT.
Then we consider what happened in the constructed relation graphs:
12h relations. Assume (2)( E ELAET, i.e. v, w E V, ri (u, w), r2(u, w) E E, then 12((11, 12 r2), h2n(ri . E FLIFT
h2h relation. Assume h2h(r1,72) E Eurr iu, v, w E V, (,, r2 w) E E, then
h2((r1, (h(r 21 , E ELer
h2t relation. Assume h2t((1,,2) ELIT, i., u, V, u), (2(w, v) E, then
h2h(r1, r ( 12(r r2), 2h(r1 .r E ELer
f2t relation. Assume r21(r1.72) E ELIT, i.e.3uu, v, E V, ri (u, r2w u) E E, then 22)(1,,7")), h22r(r r2), 42h(r") ,rz") ELFT
G. Sparse matrix multiplication for relational hypergraph construction
To compute the adjacency matrix for the relational hypergraph, we hereby define the implementation details of lift operation LIFT. We follow a similar strategy from Galkin al. (2024) and compute the four motifs of Ul.ra, 12t,,2h,/21hh2h, via sparse matrix multiplication. We then proceed to show higher-order motif computation presented in MOTIF instances the experiments.
G.1. 2-path motifs (J:Path)
Given knowledge graph G -V,,E, with n [V] nodes and m == [R]] relations, we represent the (multi-relational) adjacency matrix A Raxmxn in sparse format. We can then gather the adjacency matrix by scatter max over the first node dimension and the last node dimension, obtaining two (sparse) matrices E, E RR and E, E mm representing any incoming edges of any relation from any nodes and outgoing edges of any relation from any nodes, respectively. Note that since the adjacency matrix is binary, i.c., all of the coordinates are either 0 or 1, taking scatter max is equivalent to taking logical OR operation. Note that these binary interactions are actually all possible 2-path motifs.
For motif computing interactions between relations are then equivalent to one sparse matrix multiplication (spmm) operation between adjacencies:
Ayzh spmm [,T, Ex) E mm
Az2 spmm EET E.) pmxm
A spmm (ET E.) pmxm
A,zh spmm E En) E mmxm
Note that we only take the existence of any edges, thus, the respective edge index is extracted from all non-zero values. Finally, we concatenate all the considered relations types as the final adjacency matrix of LIFT>(() through LIFT operation.
23

---

How Expressive are Knowledge Graph Foundation Models?
fh:: (a,3, 8,7) 7)
B 7
fft:
(a, 7)
Ct
hsh: (a, 1,,
/
hftt (a,8,7)
Figure 10. The 3-path motifs used by MOTIF(F3 are shown here.
G.2. 3-path motifs (Fgath)
Note that it also possible to compute higher-order k-path (FE motifs via similar strategy, i.e., via iteratively carrying out spmm over the adjacency matrix A As an example, we first define the motifss considered in the experiment of MOTIF with all the 3- 3-path motifs, namely, fff..ft.hffh.lfff shown in Figure 10.
hail-horward (ffh) edges, ffi(1,, F2, r3) E ELIT è 3u, e. VVri(u,) A (2((0, w) rz(w,x)
tail-flrward-tail (ift) edges,
(2,1,,2,773) E ELOT + 3u, w, E V,ri(u, Ar((u, w) Ara(z, w)
head-forward-heirr (lih)) edges, hff(r1, 72, r3) E ELOT = u, V.r (2 A (2) Viri(e,))
fal (lif) edges, hit(ri, r2, r3) ELAT + 3u, w, (, Ar2(u, Ar3(w,
To compute these efficiently via spmm, we follow a similar strategy of generating the multi-relational adjacency matrix A E Raxmx" and E₁. E Raxm and E, E R=x" Then, with the same strategy, the computation of these interactions among three relations is equivalent to one sparse matrix of size mmxxm
Anh spmm
ET A, Ex) Rmxmx
Ag spmm
E A, E,) E R
Age spmm
EET A, E,) E mmxmxm
Ayh spmm
Ef A, EA) RmXmxm
The final adjacency matrix of LGF can be generated analogously by concatenating all the considered relations types. Note that it is also possible to construct even higher-order Path-based motif's other types of motifs with spmm alternative efficient computation methods. We leave this as future work.
H. Scalability analysis
Scalability is generally a concern for KGFMs since they carry out inductive (on node and relation) link prediction between a given pair nodes, which relies heavily on the structural properties of these nodes as well as the relations (due the lack of node and relation features). While incorporating more expressive motifs enhances the model's predictive power, it also introduces additional computational costs in terms of time and space complexity. This trade-off between expressiveness and scalability is critical in practical applications and warrants careful consideration. Specifically, we aim to answer the question: What is the trade-off between expressiveness and scalability for MOTIF? (Q4).
To explore this trade-off, we conducted a scalability analysis, as reported in Table 4. All experiments were performed on the FB 15k-237 dataset using a batch size of on single NVIDIA H100 GPU. We report the number of parameters, the
24

---

How Expressive are Knowledge Graph Foundation Models?
Table Scalability analysis of link prediction using motifs applying F515k-237: number of edges in constructed relational hypergraphs,
number of parameters used, training time per batch, inference time per batch, and GPU memory taken on single H100. (batch size 64)
Model
Motif (F)
#Parameter
#Edges in LG)
Training Time(s)
Inference Time(s)
GPU Memory(GB)
ULTRA
168,705
108,240
1.19
0.066
12.87
181,185
4,288,092
3.66
2.613
17.85
MOTIF
179,649
81,180
1.80
0.100
13.14
{h21)
178,881
27,060
1.56
0.087
13.10
0
178.497
0
1.48
0.065
12.88
number of edges in the constructed relational hypergraphs, training time per batch, inference time per batch, and GPU memory usage.
H.1. Impact of motifs on scalability
The number of parameters in the models remains relatively stable as richer motifs are introduced, as the additional learnable parameters grow linearly with [t] (the number of relations) and d (embedding dimension) due to the inclusion of additional fundamental relation embeddings. However, the difference between MOTIF and ULTRA is notable: MOTIF includes additional positional encodings in the HCNet to capture edge directionality, leading to slightly more parameters.
The key scalability challenge arises from the rapid increase in the number of edges in the constructed relational hypergraphs LIFT=(G) as more complex motifs are introduced. For example: binary edges scale with O(IV RJ), while higher-order motifs such as F introduce edges that scale with ( (R). This results in an exponential increase as consider higher order motifs such as k-path or k-star in the number of induced hyper-edges, leading to significantly higher computational and memory requirements.
In terms of training and inference time, higher-order motifs (e.g., FF dramatically increase both training and inference times. For instance, training time per batch for FTu is 3.66 seconds compared to 1.80 seconds for the Fruth motif. Additionally, GPU memory consumption also increases with more complex motifs, While Foath consumes 17.85 GB, the simpler motifs such as Fraah and [h2r} use approximately 13 GB.
H.2. Optimizing scalability with Triton kernels
To mitigate the scalability bottlenecks, we have included custom implementation via Triton kernel to account for the message passing process on both knowledge graphs and relational hypergraphs, which on average halved the training times and dramatically reduced the space usage of the algorithm (5 times reduction on average). The idea is to not materialize all the messages explicitly as in PyTorch Geometric (Fey & Lenssen, 2019), but directly write the neighboring features into the corresponding memory addresses. Compared with materializing all hyperedge messages which takes O(k (E) where k is the maximum arity, computing with Triton kernel only is O(VV) in memory. This will enable fast and scalable message passing both knowledge graph and relational hypergraphs in MOTIF, As result, we observe that all of the instance of MOTIF can be run on 20GB GPU. We have shown our implementation in the provided codebase.
While adding oigher-order motifs significantly enhances performance, it also introduces scalability challenges, particularly in terms memory and computational requirements. Our Triton kernel implementation alleviates some of these issues, but further research is needed explore more efficient ways to scale models for extremely large knowledge graphs and relational hypergraphs.
I. Computational complexity
In this section, we present the theoretical computational complexity of the model variants considered in the experiments (Q4). Given knowledge graph G = (V, E, R, c), we have that [V], EE, |R] represents the size of vertices, edges, and relation types, respectively. d is the hidden dimension of the model, and is the number of layers the model. m denotes the maximum arity of the hyperedges, and in the experiment, it's either 3.
25

---

How Expressive are Knowledge Graph Foundation Models?
I.1. Generating relational hypergraph
2-path (JF The complexity of generating the relation graph for ULTRA completely determined via initial scatter max over the node dimension, which has time complexity of ( followed by sparse- sparse-matrix multiplication over E or E and Eg or E., The time complexity of this operation is (mnzz x nnz(Y)) where nnz is function finding the number of non-zero element in sparse matrix X E (E,, E Y E EE, B. Note that if we do not use spmm, this time complexity will blow up to ((P). Thus, the total complexity for constructing the relation graph in ULTRA will become [[ + [R)).
3-path (F Similarly, for the construction of the relational hypergraph in MOTIF, i.e., all the 3-path and the 2-path, we need another spmm to additionally account for the forward adjucency matrix A. The time complexity of this operation under sparse matrix multiplication is then O (nnz(()) x nnz( x nnz( X E {E) " }. Y E { E,, E.). Without spmm, this time complexity will become O( 2 [R|2 + [ which dominates the construction of E,, E, together with all the 2-Path motifs and thus also serve as the total complexity.
Additionally, it's important to note that the relational hypergraph can be generated preprocessing step during inference. During training, we typically exclude the positive triplets currently being used for training from the training knowledge graph to prevent overfitting. This exclusion often leads to changes in the relational hypergraph structure, requiring us to rebuild the relational hypergraph for each batch. Therefore, the complexity of constructing these relational hypergraphs needs to be considered.
m-Star (Par), In the synthetic experiments, we consider m-Star motifs for variety of m. ranging from 8. It is computationally more expensive generate m-Star since there does not exist an spmm computation for fast computation. To compute m-Star, we need to go through each node v and check the combination (deg())) and check the existence individually to fill up the table. Thus, the complexity will be ( (())). which is exponential to the number of relations R and thus
hard to implement in the relation-rich real-world datasets. As a result, we exclude the motifs of m-Star in real-world experiments.
1.2. C-MPNNs and HC-MPNNs
We take the complexity analysis results from Huang et al. (2023) and Huang et al. (2024), shown in Table In this table, we report both the complexity of single forward pass as well the amortized complexity of query q(u, v).
I.3. ULTRA and MOTIF
The complexity of ULTRA thus the combination of relation graph generation with 2-path motifs, applying C-MPNN on the constructed relation graph LIFTx(G), and then another C-MPNN on knowledge graphs. (Note that NBFNet an instance of C-MPNN, shown in Huang et al. (2023)). Thus, given a ULTRA model with T layers on relation encoders and L layers on its entity encoder, the overall complexity of forward pass is going to be
O(VV]) + [R]) + 2 [R|d)) - L([E)d+ + IV(d))
as the number of edges in the constructed relation graph is bounded by O( ((1()), and the number of nodes in the relation graph is O())). The complexity of MOTIF equipped with 3-path with T layers on relation encoders and L layers on its entity encoder can be derived in a similar manner:
O1V + [V]] + L(IR [R] + [R]
L(
However, note that due to spmm, the construction of the relation (hyper)graph is very efficient in practical scenarios. Additionally, we note that the amortized complexity of a query of ULTRA is
o [BI(IV] + [R]) + T(RRRd d + Rl
E d V
L
+
df)
V
and that for MOTIF equipped with 3-path is
( + T(RR + [
L
Eld
+ dPi).
[V]
[V
26

---

Adding node features. Incorporating node features, such text embeddings, is relatively simple and can be done by simply concatenating the node feature vector, 25,, with the current representation, h., produce h [h [x.]] Since the initialization of MOTIFS only requires satisfying target node distinguishability, concatenating the node features will How Expressive are Knowledge Graph Foundation Models?
Table 5. Asymptotic runtime complexities for relation and entity encoder.
Model
Complexity of forward pass
Amortized complexity of a query
C-MPNNS
( + [V]d2)
O
Eld d)))
[V] OLL
HC-MPNNs
[|
m Eld M
+ d²))
J. On adding node and relation features
In general, the task of link prediction on knowledge graphs does not consider any node features. Thus, on the surface, it seems that MOTIF does not take the node features into account, and so do many models (Teru et al., 2020) that utilize the labeling tricks (Zhang et al., 2021) and conditional message passing (Zhu et al., 2021; 2023; Galkin et al., 2024; Huang et al., 2023; 2024).
preserve this property. As a result, all theoretical results remain applicable to MOTIF when node features are included. It's also important to note that this concatenation method has already been successfully employed in knowledge graphs with node features, as demonstrated in Zhang et al. (2021): Galkin et al. (2024).
Adding relation features. The same principal can apply since MOTIF explicitly computes the (conditioned) relation representations. Specifically, given any feature vector of relations I, such as text embeddings, we can consider the augmented relation embedding h, = [|,,] in place of the original computed relation embeddings h,. We leave how adding relation features could potentially boost the zero-shot and fine-tuned performance of KGFMs an important future work.
K. Proof of the counter-example in Section 6.2
We present counter-example of link prediction in Figure showing that ULTRA cannot distinguish between links ra ru, 01) and ra 02) whereas MOTIF(F5")) can correctly distinguish. We first define the knowledge graph of interest G = (V, E, R, c) where
V = 01,
(1)
(ri,7,,ra)
(2)
E (1( r2, (((,))
We first show that ULTRA cannot distinguish between ru(u, 01) and rs(u, 02). First we note that the LIFT operation defines on motifs of ULTRA, ie.. (h21, 12h, h2h, 121), will generates an complete relation graph LIFTx(G)) for G. Formally speaking, it holds that VP E F,Vr, E R, P(r, r') E ELATT
Now, it is enough to show that ULTRA will assign the same coloring to (u, v1) and (u, 02). We first claim that h, (2) -h (2)
rrlrs hryrr
for all T' 0. The base case holds since h. (0)
h (0)
1d. For inductive case, assume (1) h rilrs then holds
Filrs r2/ra
///rs
27

---

How Expressive are Knowledge Graph Foundation Models?
that
h (
W(0)
(0) Prlrs
Σ
h (1)
rls 2 2 )
+b(1)
Plant E Run
Eu (r1)
o (w())
Σ
Σ
h (t)
x ) + +b(())
Frira
Furr Run r'ER
a (w())
(0)
Σ
Σ
+ Zrrer ) + +b(1))
r'
Flar Rusr r'ER
o (w(1))
h 122 ||
Σ
Σ
(t)
3 knoor) ) + +b(1)
Flrr Rum
E'E (12)
(++1) pales
ft
Now it is straightforward to see that the representation of (u, v1) and (u, 02) will be identical since the entity encoder of ULTRA cannot distinguish between relation T1 and 72, thus viewing node dj and u2 isomorphic each other when conditioned on u.
However, we notice that ()TlF(33 can distinguish between and r2 by computing h hirs o h ralrs" since the generated relational hypergraph will contain an hyperedges lift(12, r3, r1) by noting the homomorphism on path ++ r2 - x ra y ri 01 but it does not contain hff(r1, r3, r2).
L. Details in synthetic experiments
Dataset construction. Given 2 S k < 7, and for each knowledge graph G; = (Vi, F.,, R₂) in ConnectHub(k)) we generate and partition the relations into two classes and a query relation R, P, (g) where P. = {pr. ,PI), and N; = - (m 3 for some I k: Then, we construct each component as follows:
A hub H, where we have the center node u, and for all relation p E Pt, there exists distinct e E V2 such that the edge p(u, u) exists. Note that the center node u will have a degree larger than k: by construction.
Multiple positive communities with relations P. where for each subset of relations P, S P. satisfying |P| < k, we have a center node æ and there will exists distinct nodes "", P.
such that p, (U,, x) exists for all 1 S < [P,]-
Multiple negative communities with relations N, where for each subset of relations Ñ, C N, satisfying [N,] < k, we have center node and there will exists distinct nodes y1, M1 such that ny (1); x) exists for all 1 S j < NN].
Finally, the graph G, is disjoint union of all these components. The detailed dataset statisties reported in Table 6.
Experiment details. We use ULTRA with sum aggregation on both relational and entity levels, and similarly in all variants of MOTIF(HM*)). The message function on the entity level is chosen to be elemental-wise summation to avoid loss of information from relation types during the first message passing step. We use layers for both ULTRA and all variants of MOTIF m each with 32 dimension on both relation and entity model, and the Adam optimizer is used with a learning rate of 0.001, trained for 500 epochs in all experiments.
M. Further experimental details
Datasets. In this section, we report the details of all experiments reported in the body of this paper. For pertaining experiments, we train the MOTIF instance on three transductive knowledge graph completion datasets, following Galkin et al. (2024): FB15k237 (Toutanova & Chen, 2015), WNI8RR (Dettmers et al., 2018), and CoDEx Medium (Safavi & Koutra, 2020). We then carry out zero-shot and fine-tuning experiments on the following datasets, categorized into three groups:
Inductive e, r. Inductive link prediction on both new nodes and new relations. Including 13 datasets in INGRAM (Lee et al., 2023): FB-25, FB-50, FB-75, FB-100, WK-25, WK-50, WK-75, WK-100, NL-0,, NL.-25, NL-50, NL-75, NL-;
28

---

How Expressive are Knowledge Graph Foundation Models?
Table 6. Dataset construction parameters for ConnectHub.
ConnectHub(k)
#Training/Testing graphs
# "Training/Testing triplets
# Relations
=
7/3
360/210
[3,13]
=
7/3
1642/1078
[4,14]
4/2
824/1058
[5,11]
1/1
112/224
[6,8]
1/1
238/476
[7,9]
and 10 datasets in MTDEA (Zhou et al., 2023a): MTI tax, MTI health, MT2 org, MT2 sci, MT3 art, MT3 infra, MT4 sci, MT4 health, Metafram, FBNELL.
Inductive e. Inductive link prediction nodes only. Including 12 datasets from GralL (Teru et al., 2020): WN-v1, WN-v2, WN-v3, WN-v4, FB-v1, FB-v2, FB-v3, FB-v4, NL.vv1, NL-v2, NL-v3, NL-v4; 4 datasets from INDIGO (Liu et al., 2021): HM 1k, HM 3k, HM 5k, HM Indigo; and 2 datasets from Nodepiece (Galkin et al., 2022): ILPC Small, ILPC Large.
Transductive link prediction Large (Safavi & Koutra, 2020), NELL-995 (Xiong et al., 2017), YAGO 310 (Mahdisoltani al., 2015), WDsinger, NELL23K, FB15K237(10), FB FB15k237(20), FB FB15K237(50) (Lv et al., 2020), and Hetionet (Himmelstein et al., 2017).
Transductive.
nodes and seen relations. Including CoDEx Small, CoDEx
Full tables of zero-shot performance of MJT are presented in Table and Table 8, and full tables of fine-tune performance MOTIF(J3")) averaged runs are presented in Table 9, Table 10. We also carry out end-to-end experiments on all considered datasets, with full tables averaging 3 runs presented in Table 11 and Table 12. We report the statisties of these datasets in Table 13, Table 14, and Table 15, respectively. We finally report the detail hyperparameters used in Table 16, and the epoch used for fine-tuning and end-to-end training in Table 17. Note that we do not include all 13 datasets shown in Galkin et al. (2024) due to the size of constructed relational hypergraphs when equipped with 3-path motifs.
Training. Following convention, on each knowledge graph and for each triplet r(u, v), we augment the corresponding inverse triplet r-1(u (u, u) where r- is a fresh relation symbol. All trained MOTIF and its variants aim to minimize the negative log-likelihood of both positive and negative facts. In line with the partial completeness assumption (Galárraga et al., 2013), we generate negative samples by randomly corrupting either the head or the tail entity. The conditional probability of a fact q(u, v) is parameterized as (P(v u,, ④) = (h
where denotes the sigmoid function and f is two-layer (Ba et al., 2016) and short-cut connection after each aggregation and before applying ReLU on both encoders and dropout rate of 0.2 on relation encoders only. We discard the edges that directly connect query node pairs to prevent overfitting. The best checkpoint for each model instance is selected based on its performance on the validation set.
MLP. We adopted mayer-normalizate
Inspired by Sun et al. (2019), we employ self-adversarial negative sampling, drawing negative triples from the following distribution, with serving as the adversarial temperature:
C(v (, = - logg(p u,
wi, log(1 p(v v4, g))
Here, A represents the number of negative samples for each positive sample, and (u/, q, uf) is the i-th negative sample. Finally, is the weight for the i-th negative sample, defined as
llog(1 - plo! u// (4.9))
Wia := Softmax
29

---

How Expressive are Knowledge Graph Foundation Models?
Table 7. Detailed zero-shot inductive link prediction MRR and hits@ 10 for ULTRA and (J3
ULTRA
MOTIF
Dataset
MRR
H@ 10
MRR
H@ 10
FB-100
0.449
0.642
0.428
0.628
FB-75
0.403
0.604
0.399
0.614
FB-50
0.338
0.543
0.338
0.546
FB-25
0.388
0.640
0.384
0.640
WK-100
0.164
0.286
0.164
0.282
WK-75
0.365
0.537
0.366
0.540
WK-50
0.166
0.324
0.163
0.314
WK-25
0.316
0.532
0.311
0.493
NL-1100
0.471
0.651
0.438
0.647
NL-75
0.368
0.547
0.314
0.512
NL-50
0.407
0.570
0.373
0.532
Inductive e,
NL-25
0.395
0.569
0.348
0.498
NL-0
0.342
0.523
0.324
0.497
MTI tax
0.224
0.305
0.325
0.448
MT1 health 0.298
0.374
0.326
0.398
MT2 org 0.095
0.159
0.092
0.154
MT2 sci
0.258
0.354
0.286
0.435
MT3 art
0.259
0.402
0.269
0.414
MT3 infra
0.619
0.755
0.658
0.786
MT4 sci
0.274
0.449
0.283
0.451
MT4 health 0.624
0.737
0.627
0.762
Metafam 0.238
0.644
0.344
0.829
FBNELL
0.485
0.652
0.468
0.664
WN-v1 0.648
0.768
0.682
0.778
WN-v2
0.663
0.765
0.663
0.771
WN-v3
0.376
0,476
0.420
0.538
WN-v4
0.611
0.705
0.640
0.718
FB-vI
0.498
0.656
0.503
0.692
FB-v2
0.512
0.700
0.511
0.716
FB-v3
0.491
0.654
0.500
0.692
FB-v4
0.486
0.677
0.487
0.677
NL-v1
0.785
0.913
0.674
0.871
Inductive e
NL-v2
0.526
0.707
0.564
0.769
NL-v3
0.515
0.702
0.533
0.724
NL-v4
0.479
0.712
0.503
0,711
ILPC Small
0.302
0.443
0.295
0.444
ILPC Large
0.290
0.424
0.285
0.415
HM lk 0.059
0.092
0.063
0.097
HM 3k 0.037
0.077
0.055
0.084
HM 5k
0.034
0.071
0,050
0.073
HM Indigo
0.440
0.648
0.426
0.637
30

---

How Expressive are Knowledge Graph Foundation Models?
Table 8. Detailed zero-shot transductive link prediction MRR and hits 10 for ULTRA and MOTIF(JT
ULTRA
MOTIF
Dataset
MRR
H@ 10
MRR
H@ 10
WN18RR
0.480
0.614
0.507
0.609
Pretrained
FB15k237
0.368
0.564
0.336
0.532
CoDEx Medium
0.372
0.525
0.357
0.509
CoDEx Small
0.472
0.667
0.474
0.670
CoDEx Large
0.338
0.469
0.339
0.469
NELL-995
0.406
0.543
0.491
0.623
YAGO 310
0.451
0.615
0.441
0.607
WDsinger
0.382
0.498
0.397
0.514
Transductive
NELL23K
0.239
0.408
0.220
0.384
FB FB15k237(10)
0.248
0.398
0.236
0.384
FB (2))
0.272
0,436
0.259
0.422
FB 15k237(55))
0.324
0.526
0.312
0,508
Hetionet
0,257
0.379
0.256
0.383
31

---

How Expressive are Knowledge Graph Foundation Models?
Table 9, Detailed finetuned inductive link prediction MRR and hits 10 for ULTRA and MOTIF (33
ULTRA
MOTIF
Dataset
MRR
@@ 10
MRR
H@ 10
FB-100
0.444
0.643 + 004
0.439 4.001
0.642
FB-75
0.400 003
0.598 004
0.399 =
0.607
FB-50
0.334 ..002
0.538
0.340 1.002
0.544 :1.02220002
FB-25
0.383
0.635
0.388
0.635
WK-100
0.168
0.286
0.173
0.284
WK-75
0.380
0.530
0.371 .00
0.535
WK-50
0.140
0,280 012
0.160 .00
0,304 002
WK-25
0.321 + 003
0.535 + +0007
0.317 4.005
0,505 004
NL.1100
0.458
0.684
0.464 2001
0. 0.6822tmmm 001
NL-75
0.374
0.570 .00
0.360 #001
0.548 004
NL-50
0.418 005
0.595
0.414 1114.0000
0.573
Inductive 6,
NL-25
0.407
0.596
0.390 #.00
0.580
NL-0
0.329 010
0.551
0.328 201
0.556 007
MTI tax
0.330 046
0,459 056
0.416 2
0.522 005
MT1 health
0,380 0002
0.467 006
0.385 200
0.473 003
MT2 org
0. 0.104.1.00
0.170 001
0.106
0.170 L1.03
MT2
0.31 #1010
0.451 .042
0.326 #2002
0.520
MT3
0.306 003
0.473
0.315 2.13
0.469
MT3 infra
0.657 008
0.807
0.683 +
0.827 =
MT4 sci
0.303 007
0.478
0.309
0.483
MT4 health
0.704
0.785
0.703 #0001
0.787 #.002
Metafam
0.997 = 003
1.000 OoG
1.000 2.000
1.000 000
FBNELL
0.481 00.004
0.661 1111
0.481 1.004
0.664 1.66441.008
WN-v1
0.685 1: 003
0.793
0.703 1.03
0.806
WN-v2
0.679 002
0.779
0.680 =.00
0.781
WN-v3
0,41 1 008
0,546 006
0.466
0.590 :1 002
WN-v4
1:144t.0 003
0.720 .011
0.659 #:000
0.733 +: 0004
FB-vl
0.509 002
0.670 004
0.530 2.00
0.702 001
FB-v2
0.524
0.7 1.710:10
0.557 1.004
0.744
FB-v3
0.504 001
0.663
0.519 #.001
D.68441
FB-v4
0.496
0.684
0.508
0.695
NL-v1
0.757
0.878
0.7 +
0.873++
Inductive
NL-v2
0.575 s: 004
0.761 007
0.566 1.660000
0.765 003
NL-v3
0.563 004
0.755 006
0.580 1000
0.764 001
NL-v4
0.469 :200
0.733 0011
0.507 1.062
0.740 c0.00
ILPC Small
0.303
0.453 .002
0.302 +0001
0.449 -t.001
ILPC Large
0.308 002
0.431
0.307
0.432
HM lk
0.042.t.02
0.100
0.067
0.107
HM 3k
0.030. 002
0.090
0.054
0.103
HM 5k
0.025 +001
0.068
0.049 +00000
0.091 001
HM Indigo
0.432 001
0.639 002
0.426 (001
0.635 001
32

---

How Expressive are Knowledge Graph Foundation Models?
Table 10. Detailed finetuned transductive link prediction MRR and hits 10 for ULTRA and MOTIF (F
ULTRA
MOTIF
Dataset
MRR
H@ 10
MRR
H@ 10
WN18RR
0.480
0.614_1m IM0
0.529
0.628
Pretrained
FB15k237
0.368
0.564 9.564_.000 000
0.357:1.00
0.550
CoDEx Medium
0.372
0.525
0000
0.361 ::001
0.517
CoDEx Small
4.490.000
0.686
=.003
0.490 4.900..00r
0.680
CoDEx Large
0.343 000
0.478
DM12
0.355 c 002
0.489
NELL-995
+.509+.013
0.660
DX1
0.5144tu0 000
0.655 #2000
YAGO 310
0.557 000
0.710
0003
0.603 010
0.735 1::
WDsinger
0.417 1:002
0.526
.002
0.423 11.001
0.532 1:.00
Transductive
NELL23K
0.268
0.450
0.256
0.44 +:001
FB FB15k237(110
0.254.:001
0.411
001
0.254
0.41 1 1:00
FB15k223 (2k)
0.274:2.01
0.445
0012
0.273
0.4444
FB 15k237(50)
0.325::.00
0.528
0002
0.323
0.523::000
Hetionet
0.399
0.538
-003 0014
0.446 0002
0.575 #0004
33

---

How Expressive are Knowledge Graph Foundation Models?
Table 11. Detailed end-to-ent inductive link prediction MRR and hits 10 for ULTRA and 33
ULTRA
MOTIF
Dataset
MRR
H@ 10
MRR
H@ 10
FB-100
0.425 + 004
0.628
0.418 #..02
0.614#.001
FB-75
0.385 001
0.592
0.389
= 2000
0.592
FB-50
0.323 005
0.523
0.334
0.5322:001
FB-25
0.365 4
0.612
0.376
0.621
WK-100
0.159
0.269
0.163 #.016
0.273
WK-75
0.365 +: 006
0.501 +:00=
0.354
0.504 012
WK-50
0.149 000
0.290
0.150 20000
0.297 022
WK-25
0.305 4.008
0,486 .066
0.299 #.004
0.489 + 4.011
NL-100
0.410
0.648 ooe
0.458
0.663
NL-75
0.364 6066
0.562
0.363
0.568 010
NL-50
0.416 001
0.597
0.408
0.591 008
Inductive
NL-25
0.405
0.612
0.387
0.601
NL-0
0.323 020
0.520 ozx
0.329 2.001
0.555 004
MTI tax
0.392 040
0.517
0.431 :0044
0.52 005
MT1 health
0.378 004
0.466+.00 on6
0.378
0.473 004
MT2 org
0.100
O. 16166.1.001
0.100 10000
0.168 0011
MT2 sci
0.323 002
0.524
0.358 2013
0.535
MT3 art
0.302
0.459
0.313
0.470 006
MT3 infra
0.67 + 005
0.815
0.687
0.823
MT4 sci
0.290 00.033
0.457:000
0.290
0.457
MT4 health
0.684
0.77 +
0.701 #.001
0.781 :t001
Metafam
0.989 =: 010
1.000-2.00
0.885
1.000
FBNELL
:.489:.012
0.678 1778::00 006
1.469..022
0.634
WN-v1
0.668 007
0.788 oos
0.679
0.792.
WN-v2
0.296 074
0.597
0.684
0.795
WN-v3
0.332
0.5
0,428
0.562:t.013
WN-v4
0.622 01088
0.709 0.08
0.635 #:031
0.720 -::00::000 010
FB-vl
0.506 004
0.672 004
0.524
0.689
FB-v2
0.524
0.723
0,537 2.002
0.737 .000
FB-v3
0.502 002
0.670 o0
0.509
0.679 001
FB-v4
0.487 4.
0,678
0.494
0.685
NL-v1
0.67 1 = 011
0.799 036
0.777 2007
0.866
Inductive
NL-v2
0.526
0.745
0.561 :2.008
0.775 010
NL-v3
0.563 011
0.758 ons
0.565 0099
0.752 009
NL-v4
0.463 1.63:.0030
0.703 -:000.0000
0.512
0.737 ::
ILPC Small
0.296 2296-t.00
0.445 0044
0.291 =::001
0.438 0022
ILPC Large
0.290 006
0.417+001
0.284
0.417 002
HM lk
0.029
0.072
0.017
0.040 .002
HM 3k
0.027
0.075 000
0.030
0.089
HM 5k
0.027 +003
0.065 +00
0,028
#0.00
0.079 +7799.00)
HM Indigo
0.399 001
0.614+.om
0.369
0.587 006
34

---

How Expressive are Knowledge Graph Foundation Models?
Table 12. Detailed end-to-end transductive link prediction MRR and hits@ 10 for ULTRA and (
ULTRA
MOTIF
Dataset
MRR
H@ 10
MRR
H@ 10
WNI8RR
0.489
0.620=mm
0.531 10001
0.636
FB FB15K237
0.352
0,546 IM12
0.327 0011
0.520
CoDEx Medium
0.367:1.0
0.521 001
0.364 068
0.5 0.518
CoDEx Small
0.488
0.679
0011
0.490 :0:00
0.678
CoDEx Large
0.332
0.473
0.332
0.467
NELL-995
0.509
0.646
0.510
0.655 +5009
Transductive
YAGO 310
0.567
0.710
0.583
0.724
WDsinger
0.413
0,525 =0001
0.42 1:053
0.530::.05
NELL23K
0.261 +
0.445 =002 0012
0.263 a: 003
0.447 :0000
(1))
0,248 #:001
0.398 -001
0.255 10001
0.411 +:0001
FB15k237(20)
0.272
0,436
14436.000 0012
0.27 001
0.442
FB FB15K237(50)
0.320
0.523 0033
0.3 6
0.51
Hetionet
0.424
0.553
0.419
0.548 +.001
Table 13. Dataset statistics for inductive-e, r link prediction datasets. Triples are the number of edges given training, validation, test graphs, respectively, whereas Valid and Test denote triples to be predicted in validation and test graphs
Training Graph
Validation Graph
Test Graph
Dataset
Entities
Rels
Triples
Entities
Rels
Triples
Valid
Entities
Rels
Triples
Test
FB-25
5190
163
91571
4097
216
17147
S716
4097
216
17147
5716
3879
FB
4659
134
62809
2792
186
9316
3106
2792
186
9316
3106
FB- 100
4659
134
62809
2624
77
6987
2329
2624
77
6987
2329
WK 25
12659
41873
3228
3391
1130
3238
74
3391
1131
WK-50
12022
72
82481
9328
93
9672
3224
9328
93
9672
3225
WK-75
6853
11:4
WK-100
9784
67
49875
12136
37
13487
4496
12136
37
13487
4496
NL-
NL-25
4396
106
17578
2146
120
2230
743
2146
120
2230
744
NL.50
4396
17578
2335
119
2576
859
2335
119
2576
859
NT-75
2607
1058
1578
1818
606
1578
1818
607
NL-100
1258
55
7832
1709
53
2378
793
L700
53
2378
793
Metafam
184
FBNELL
4636
100
10275
4636
100
10275
1055
4752
183
10685
597
Wiki MTI tax
10000
17178
10000
17178
1908
10000
16526
1834
Wiki MTI health
10000
14371
10000
14371
1596
10000
7
14110
1566
Wiki MT2
10000
23233
10000
23233
2581
10000
11
21976
2441
Wiki MT2 sci
10000
16
16471
10000
16
16471
1830
10000
16
14852
1650
MTT3
Wiki MT3 infra
10000
24
21990
10000
24
21990
2443
10000
27
21646
2405
Wiki MT4 sci
10000
12576
10000
12576
1397
10000
12516
1388
Wiki MI4 health
10000
21
15539
10000
21
15539
1725
10200
20
15337
1703
35

---

Task How Expressive are Knowledge Graph Foundation Models?
Table 14. Dataset statistics for inductive-e link prediction datasets. Triples the number of edges given training, validation, graphs, respectively, whereas Valid and Test denote triples to be predicted in the validation and test graphs.
Training Graph
Validation Graph
Test Graph
Dataset
Rels
Entities
Triples
Entities
Triples
Valid
Entities
Triples
Test
FB-vI
180
1594
4245
1594
4245
489
1093
1993
411
FB-v2
200
2608
9739
2608
9739
1166
1660
4145
947
FB-v3
215
3668
17986
3668
17986
2194
2501
7406
1731
FB-v4
219
27203
4707
27203
3352
3051
11714
2840
WN-vi
9
2746
5410
2746
5410
630
922
1618
373
WN-v2
10
6954
15262
6954
15262
1838
2757
4011
852
WN-v3
11
12078
25901
12078
25901
3097
5084
6327
1143
WN-v4
3861
7940
7084
12334
2823
NL-vI
3103
4687
3103
4687
225
833
NL-v2
88
2564
8219
2564
8219
922
2086
4586
935
NL-v3
142
4647
16393
4647
16393
1851
3566
8048
1620
NL-v4
76
2092
7546
2092
7546
876
2795
7073
1447
ILPC Small
10230
78616
20960
6653
20960
2902
ILPC Large
65
46626
202446
29246
77044
10179
29246
77044
10184
HM 1k
11
36237
93364
36311
93364
1771
9899
18638
476
HM 3k
11
32118
71097
32250
71097
1201
19218
38285
1349
HM
28601
57601
28744
57601
23792
48425
2124
HM Indigo
229
12721
121601
12797
121601
14121
14775
250195
14904
Table 15. Dataset statistics for transductive link prediction datasets. Task denotes the prediction task: h/t predicting both heads and tails, and / is predicting only tails.
Dataset
Entities
Rels
Train
Valid
Test
FB15k237
14541
237
272115
17535
20466
h/t
WN18RR
40943
11
86835
3034
3134
h
CoDEx Small
2034
42
32888
1827
1828
h/t
CoDEx Medium
17050
51
185584
10310
10311
h/t
CoDEx Large
77951
551193
30622
30622
h/t
NELL995
74536
200
149678
543
2818
h/t
YAGO310
123182
1079040
5000
5000
WDsinger
10282
135
16142
2163
2203
NELL23K
22925
200
25445
4961
4952
1
FB FB15K237(10)
11512
237
27211
15624
18150
FB15K237(20)
13166
237
54423
16963
19776
FB15K237(50)
14149
237
136057
17449
20324
Hetionet
45158
2025177
112510
112510
h//
36

---

How Expressive are Knowledge Graph Foundation Models?
Table 16. MOTIF hyper--ppaaaae prpee-parameters for pretraining, line-tuning, and training from end to end.
Hyperparameter
MOTIF
# Layers T
6
Enc
Hidden dimension Dropout
64
0.2
# Layers L Hidden dimension Dec
6
64
EnC2
2-layer MLP
Dropout
0
Optimizer
AdamW
Learning rate
0.0005
Training steps
40,000
Pre-training
Adversarial temperature
1
Negatives
512
Batch size
32
Training graph mixture
FB15k237, WNISRR, CoDEx Medium
Optimizer
AdamW
Learning rate
0.0005
Fine-tuning
Adversarial temperature
# Negatives Batch size
256
16
Optimizer
AdamW
Learning rate
0.0005
End-to-End
Adversarial temperature Negatives Batch size
1
256
16
37

---

How Expressive are Knowledge Graph Foundation Models?
Table 17. Hyperparameters for fine-tuning MOTIF and from end end. Full represents whole epoch with batches being used.
Finetune
End-to-End
Datasets
Epoch
Batch per Epoch
Epoch
Batch per Epoch
FB 25-100
3
full
10
full
WK 25-100
3
full
10
full
NL 0-100
3
full
10
full
MT1-MT4
3
full
10
full
Metafam, FBNELL
full
10
FB v1-v4
full
10
full
WN v1-x4
full
10
full
NL v1-v4
3
full
10
full
ILCC Small
3
full
10
full
ILPC Large
1000
10
1000
HM 1k-5k, Indigo
100
10
1000
FB15k237
full
10
2000
WNI8RR
full
10
2000
CoDEx Small
4000
10
4000
CoDEx Medium
4000
10
8000
CoDEx Large
2000
10
4000
NELL-995
full
10
2000
YAGO310
2000
10
4000
WDsinger
3
full
10
2000
NELL23K
3
full
10
4000
FB15K237(10)
full
10
2000
FB15k237(20)
full
10
2000
FB15k237(50)
1000
10
2000
Hetionet
4000
10
2000
38


Reviews:
[{"review_id": "hsMKZSemNS", "reviewer": "Reviewer_EEM2", "summary": "The authors in this paper introduce MOTIF, a framework for enhancing expressiveness of KGFMs. The authors have conducted a rigorous, theoretical study on the expressive power of KGFMs that have been designed to generalize to unseen KGs with different relational vocabs, making them highly useful for inductive link prediction. They argue that previous methods rely mostly on binary motifs, limiting their generalization capability and in order to address this, they propose MOTIF which allows for higher-order relational motifs that enable richer relation-interactions.Yes, the authors rigorously support their claim that the choice of motifs determines the expressive power of KGFMs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for considering ours a \"strong contribution\".\n\n>*“**Methods.** Yes, but how much overhead does MOTIF introduce? Are these human-readable? Do MOTIFs scale to large-scale KGs without affecting the performance?”*\n\n>*“Q1: How much overhead does MOTIF introduce?”*\n\nThis question is **Q4** in our experimental section. A detailed comparison with theoretical computational complexity and practical scalability is shown in **App. H** and **App. G**. \n\nWhile introducing higher-order motifs will rapidly increase the number of constructed hyperedges in relational hypergraphs, the MOTIF instances considered in experiments remain feasible to scale effectively to large-scale KGs with improved performance, thanks to our custom implementation of message-passing with Triton kernels that largely reduce the computation overheads.\n\n> *“Q3: Are motifs interpretable by humans?”*\n\nIf this refers to interpretability, motifs correspond directly to small and well-defined subgraph patterns, such as paths or stars, which describe specific patterns appearing among relations to help capture the semantic meaning of relations. E.g., a \"h2h\" motif aims to identify whether the heads of two relations semantically share the same node type. \n\n> “**Theoretical Claims.** Yes, however, what is the lower bound on the computational costs? Also, the denser the KGs are, the more chances are that there would be noise. So how does the framework adapt to this?...”\n\nWe have provided a detailed analysis of the computational complexity in **App. H**. To alleviate noisy KGs, the framework can be easily adapted by adding regularization known for GNNs, such as edge dropout. In fact, we have conducted preliminary experiments using edge dropout, and MOTIF maintains stable performance, though the gains from these robustness techniques were marginal.\n\n\n>*“**Experimental Designs.** Yes. 1. Which motif type contributes the most? 2. Was there an ablation study conducted? 3. Can smaller graph modifications affect the performance? 4. How should a reader comprehend the upper bound of the motif complexity? At what upper bound does the performance start to degrade?”*\n\n>*“Q2: What is the computational cost of using denser, richer motifs?”*\n\n>*“Q4: Is there an upper bound to adding motifs that start to deteriorate the performance?”*\n\nThank you for these questions. We address each below:\n\n- *“1. Which motif type contributes the most? 2. Was there an ablation study conducted?”*\n\nWe have performed an ablation study that systematically removed motifs, transitioning from the full set of 3-path motifs to simpler sets (2-path motifs, single motif \"h2t\", and no motifs), as shown in **Table 2** of the main paper. We observe that even with a single motif (\"h2t\"), the model retains some predictive ability, as essential structural information necessary for relation representation is still captured. However, richer motifs consistently provide the strongest performance improvements due to enhanced expressivity. We are happy to include additional experiments over other binary motifs “h2h” and “t2t” in the updated manuscripts.\n\n- *“3. Can smaller graph modifications affect the performance?”*\n\nWe are not entirely sure what the reviewer refers to as our method does not modify the graph structure. Nevertheless, to validate  whether perturbation of the KG will affect the performance, we have experimented by randomly dropping half of the edges each time during training. We observed that this did not lead to noticeable performance degradation.  \n\n- *“4. How should a reader comprehend the upper bound of the motif complexity? Q2: What is the computational cost of using denser, richer motifs?”*\n\nRegarding motif complexity, computing and storing higher-order motifs incur additional complexity, which scales with respect to the number of relations. For instance, to compute k-path motifs, we would need a computation complexity of $O(|V||R|^{k-1}(|V|+|R|))$ without using sparse matrix multiplications. We include our detailed explanation again in **App. H**.\n\n- *“Q4: Is there an upper bound to adding motifs that start to deteriorate the performance?”*\n\nTheoretically, adding motifs that can not be mapped via a core-onto homomorphism to an existing one will provably be more expressive. Empirically, whether such additions lead to performance improvements or deterioration depends significantly on the dataset and specific task characteristics.  Intuitively, introducing an excessive number of motifs could reduce the signal-to-noise ratio in the constructed relation hypergraphs, potentially deteriorating the model's performance. \n\n>*“**Other Strengths And Weaknesses.** … I would like to understand the flexibility of incorporating the framework into existing KGs.”*\n\nOur framework is flexible and has been tested on 54 KGs from various domains and task settings, as shown in the experimental section. \n\n>*“**Other Comments.** ...minor typos ...”*\n\nWe will modify this in the updated manuscripts.", "claims_and_evidence": "Yes, the authors rigorously support their claim that the choice of motifs determines the expressive power of KGFMs.", "methods_and_evaluation_criteria": "Yes, but how much overhead does MOTIF introduce? Are these human-readable? Do MOTIFs scale to large-scale KGs without affecting the performance?", "theoretical_claims": "Yes, however, what is the lower bound on the computational costs? Also, the denser the KGs are, the more chances are that there would be noise. So how does the framework adapt to this? The argument assumes that more expressive models lead to better generalization.", "experimental_designs_or_analyses": "Yes. \n1.\tWhich motif type contributes the most? \n2.\tWas there an ablation study conducted?\n3.\tCan smaller graph modifications affect the performance?\n4.\tHow should a reader comprehend the upper bound of the motif complexity? At what upper bound does the performance start to degrade?", "relation_to_broader_scientific_literature": "The authors extend prior work KGFMs by introducing MOTIF, a framework that generalizes these models using higher-order relational motifs to improve inductive link prediction and relation generalization.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "The authors in this paper present a strong argument based on theoretical and empirical insights. This can be a strong contribution to the KGFM domain. I would like to understand the flexibility of incorporating the framework into existing KGs.", "other_comments_or_suggestions": "There are some minor typos that would need to be revised to improve readability, such as, “because this tuples”, “Fist we note”.", "questions_for_authors": "Q1: How much overhead does MOTIF introduce?\n\nQ2: What is the computational cost of using denser, richer motifs?\n\nQ3: Are motifs interpretable by humans?\n\nQ4: Is there an upper bound to adding motifs that start to deteriorate the performance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Qg3Izw8R2p", "reviewer": "Reviewer_C2GP", "summary": "This paper presents a modified design for existing KGFMs, incorporating arbitrary motifs rather than being limited to binary motifs, as in previous approaches. This enhancement increases expressive power. Synthetic and real-world experiments validate the proposed improvements.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *“**Methods**: ...The problem formulation is overly general, ... ”*\n\nThe reason our problem formulation is deliberately general is that our primary motivation is to rigorously analyze and broadly improve the expressive power of existing KGFMs, including widely used models like ULTRA. Our theoretical framework (MOTIF) thus intentionally generalizes beyond specific architectures. \n\n> *“**Experimental Designs**: …It would be beneficial for the authors to provide similar examples using real-world data ….”*\n> *“W4. The experimental results on real-world data are not very convincing....”* \n\nTo provide more concrete insight into why higher-order motifs are necessary, we specifically analyzed scenarios where higher-order motifs excel in downstream tasks. Empirically, we have conducted Synthetic Experiments in **Table 1** to pinpoint the exact place where binary motifs are not enough, proven by the failure of ULTRA on all constructed datasets. For real-world experiments, we found that MOTIF, equipped with higher-order motifs, significantly outperforms binary motifs on datasets containing relatively few relations, such as WordNet-based datasets, which contain only around 10 relations. This can be reflected in the average performance from WN v1-WN v4 here from zero-shot and end-to-end results:\n\n|Setting|Model|MRR|H@10|\n|-|-|-|-|\n|Zero-shot|ULTRA|0.575|0.679|\n|Zero-shot|MOTIF|**0.601**|**0.701**|\n|End-to-End|ULTRA|0.480|0.656|\n|End-to-End|MOTIF|**0.607**|**0.717**|\n\nIn **Sec. 7.3**, we conduct a detailed investigation showing that these cases revealed that binary motifs (as used by ULTRA) often construct relation graphs with structurally very similar nodes, thereby failing to distinguish different relations adequately, as shown in **Fig. 8**. In contrast, higher-order motifs frequently break such node invariances, leading to more discriminative and informative relation representations. We will discuss these and demonstrate the necessity of higher-order motifs using real-world examples.\n\n>*“**Theoretical Claims**: I did not thoroughly verify the proofs, as the theoretical claims are not critical to this paper...\"*\n\nWe would like to respectfully emphasize that one of the primary motivations and key contributions of this work is precisely to **establish a rigorous and systematic theoretical framework to analyze and understand the expressive power of existing KGFMs**, such as ULTRA. We believe these theoretical results significantly deepen our fundamental understanding of why certain KGFM variants outperform others in practice, and thus we respectively suggest that they should not be overlooked. \n\n---\n**Strengths and Weaknesses:**\n\n\n>*“W1. The definition of relational hypergraphs is problematic… W2. … more intuitive explanations of link/relation invariants are needed. W3. More generally, the writing could be improved for better clarity,...”*\n\nWe thank the reviewer for carefully pointing out these areas for improvement. We agree that the clarity and precision of our definitions, explanations, and examples can be improved for better presentation. We will explicitly clarify the definitions of relational hypergraphs (W1), provide clearer and more intuitive explanations for link/relation invariants (W2), and enhance overall readability with additional illustrative examples (W3).\n\n>“W4. “The experimental results on real-world data are not very convincing....” \n\n Please see  our detailed response on experimental design and analysis.\n\n---\n**Other comments:**\n\n>*“S1. In line 56, it would be helpful to provide a clearer explanation of the term \"binary motifs,\" as it appears to be a key concept.”*\n\nWe will clarify this in the revised manuscript by explicitly defining a binary motif as a motif $P = (G_M, \\bar{r})$ with a motif graph $G_M = (V_M, E_M, R_M)$ containing exactly two relation types ($|R_M|=2$). \n\n>*“S2. More generally, how are different entities and relations matched across various KGs? ...”*\n\nOur framework inherently matches similar relations across different KGs by constructing similar relational hypergraphs based on their structural roles. Specifically, relations with structurally similar contexts in different KGs will yield similar embeddings thanks to conditional MPNN since they can effectively capture the induced similar hypergraph neighborhoods without manual matching of entities and relations IDs. The same principle applies to entities: entities embedded in structurally similar local neighborhoods involving similar relations will naturally obtain similar embeddings across KGs. \n\n**Fig. 1** in our manuscript already illustrates how structurally similar relations across different KGs (e.g., provide ↔ supply, research ↔ produce) receive similar embeddings due to similar relational contexts. We will further expand this figure with additional explanatory details in the revised manuscript to ground this key concept.\n\n>*“S3. A minor suggestion: In lines 111–113...”*\n\nWe will modify these in the updated manuscripts.", "claims_and_evidence": "Yes. However, some unclear definitions may impact the comprehension of these claims to some extent, as outlined in the 'Other Weaknesses' section later.", "methods_and_evaluation_criteria": "Somehow, yes. The problem formulation is overly general, and the motivation behind the proposed modification does not sufficiently justify its necessity. Specifically, more explanations or concrete examples are needed to illustrate the limitations of binary motifs, particularly in the context of downstream tasks.", "theoretical_claims": "I did not thoroughly verify the proofs, as the theoretical claims are not critical to this paper. My primary concerns lie in the motivations.\"", "experimental_designs_or_analyses": "Yes, especially since I find the synthetic experiments interesting, as they effectively demonstrate the modification's inferior performance. It would be beneficial for the authors to provide similar examples using real-world data to better justify the necessity of this modification.", "relation_to_broader_scientific_literature": "KGFMs are inherently closely connected to scientific literature. The proposed modification can be viewed as an enhancement that improves analogical reasoning across different scenarios by incorporating more complex structural patterns in KGs.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "## Weaknesses:\n1. The definition of relational hypergraphs is problematic. For instance, R and V are ambiguously defined. It would be helpful to explicitly specify the domain and range of all functions involved.\n2. The sentence between lines 139 and 142 is unclear. Additionally, more intuitive explanations of link/relation invariants are needed.\n3. More generally, the writing could be improved for better clarity, particularly in explaining the method (e.g., through additional examples). Furthermore, the paper should provide deeper insights into the intuition behind the modification and the necessity of implementing it.\n4. The experimental results on real-world data are not very convincing. It would be beneficial to better demonstrate the necessity of the proposed approach.", "other_comments_or_suggestions": "1. In line 56, it would be helpful to provide a clearer explanation of the term \"binary motifs,\" as it appears to be a key concept.\n2. More generally, how are different entities and relations matched across various KGs? Additionally, it would strengthen the paper if the authors could provide support or evidence for the effectiveness of \"structural similarities\" (line 47) to better ground KGFM in the introduction.\n3. A minor suggestion: In lines 111–113, it may be clearer to use distinct notations for factual links and potential links.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NggEnciVsJ", "reviewer": "Reviewer_UN87", "summary": "The manuscript introduces a Knowledge Graph Foundation Model (KGFM) termed MOTIF, which extends ULTRA’s relation graph into a relational hypergraph using manually defined motifs to incorporate additional information for computing a relation’s conditional representation. The authors theoretically establish a condition under which a motif enhances the model’s expressivity and demonstrate that both larger path motifs and broader star motifs improve the expressiveness of the encodings, though this finding is somewhat trivial. Experimental results indicate that the proposed MOTIF outperforms ULTRA in terms of both expressivity and overall performance on real-world datasets. However, the manuscript does not provide a direct comparison with TRIX, an existing KGFM that also addresses expressive power, raising questions about the significance of its contributions.\n\n## Update after Rebuttal\nThis reviewer appreciates the authors' detailed responses. However, some concerns remain regarding the proposed method's heuristic nature, practicality and scalability.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We note that  TRIX is a **contemporaneous work** first published on 16 Nov 2024, i.e. **within 4 months** of ICML submission. We nevertheless provide answers to each of the raised concerns.\n\n---\n**Claims And Evidence**\n1. TRIX [1] is the first to provide an expressivity analysis and we will acknowledge this. However, none of our results can be derived from the TRIX paper. While [1] analyzes the expressivity of TRIX in relation to existing models, it does not provide a general tool for studying expressive power and therefore offers limited insight for evaluating future KGFMs. In contrast, the motivation of our work is to provide a more general framework (MOTIF), which captures existing KGFMs (e.g. ULTRA) and their extensions with higher-order motifs. Our theoretical results advance the understanding of KGFMs beyond known architectures. \n\n2. These graph models serve distinct purposes and generalize KGs to higher-arity data. While MOTIF uses relational hypergraphs, designing KGFM architectures using n-ary or hyper-relational KG is an interesting avenue for the future. \n\n3. (Q2) To clarify, the variant of InGram we discussed assumes that both initializations are node invariants, as stated in **Remark 1** and **Remark 2**. Thus, the theoretical results we present only apply under these conditions and do not apply to InGram using random initialization because this initialization breaks node invariance.  We will emphasize this to avoid confusion. \n\n4. The confusion stems from the ambiguous use of \"ULTRA\", which refers both to a framework and a specific architecture. To clarify: ULTRA as a **framework** is a subset of MOTIF—every instance it defines is also a MOTIF instance. ULTRA as an **architecture** (evaluated empirically) is one such instance. We’ll revise the manuscript to make this distinction explicit.\n\n---\n**Methods**\n1. (Q3) Current KGFMs typically use small motifs (e.g., short paths or stars), making manual verification straightforward.  The motif-selection process via core-onto homomorphisms can also be automated as shown in modern database engines: EmptyHeaded [Aberger et al., TODS 2017] used generation of small motifs followed by automated homomorphism checks.\n\n2. We performed an ablation study (Table 2) showing that richer motifs -- from 3-paths down to none -- consistently worsen expressivity and performance. As noted in **App. F**, we only focus on path motifs for real-world datasets due to their efficient construction via sparse matrix multiplication. While our framework can generalize to arbitrary motifs using precomputation of SQL queries and database engines, we leave empirical exploration to future work due to practical constraints. \n\n---\n**Experimental Designs**\n1. We follow prior work (ULTRA) by pretraining on the same three datasets and setup to ensure fair comparison. \n\n- There is no test leakage: all relation graphs in the train set and zero-shot inference set are different, as well as the original graph structures. While some datasets are derived from others, this only affects models with entity/relation-specific embeddings, which ULTRA and MOTIF do not use. Moreover, extracting subsets alters neighborhood structures enough to become significantly different from their larger transductive counterparts.\n  \n - Nevertheless, we did pretraining solely on YAGO310 and evaluated averaged zero-shot performance over all inductive datasets for ULTRA and MOTIF(3-path), to re-confirm the consistent performance improvement:\n\n  | | MRR|H@10|\n|-|-|-|\n|ULTRA|0.350|0.522|\n|MOTIF|**0.358**|**0.530**|\n\n2. (Q1) Our main experimental goal is to validate that richer motifs enhance expressivity within the MOTIF framework (**Q1, Sec. 6**), rather than chasing SOTA results. We use ULTRA for comparison since it is a MOTIF instance with binary motifs, making it ideal for testing our theoretical claims.\nMOTIF and TRIX differ fundamentally in expressiveness: each can distinguish relation pairs the other cannot, rendering them incomparable: \n- TRIX can implicitly count homomorphism matches, whereas MOTIF only checks for existence. E.g., in a KG with E = {r₁(u₁,v₁), r₂(v₁,w₁), r₃(u₂,v₂), r₄(v₂,w₂), r₃(u₃,v₃), r₄(v₃,w₃)}, TRIX distinguishes (r₁, r₂) from (r₃, r₄) based on their frequency, while MOTIF cannot.\n- MOTIF supports arbitrary motifs, such as the PARA with edges {α(x,y), β(x,y)} from RMPI paper, enabling finer structural distinctions. In a KG with E = {r₁(x₁,x₂), r₂(x₁,x₂), r₁(x₃,x₄), r₂(x₃,x₄), r₃(y₁,y₂), r₄(y₁,y₄), r₃(y₃,y₂), r₄(y₃,y₄)}, TRIX cannot distinguish (r₁, r₂) from (r₃, r₄) due to isomorphic relation graphs under h2h/t2t, while MOTIF can distinguish them via PARA, which maps only to (r₁, r₂).\n\nIncorporating higher-order motifs into TRIX could similarly boost its expressivity, highlighting our framework as a **complementary** way for improving KGFMs.\n\n---\n**Weaknesses**\n\nWe will refine our notation to ensure clarity and distinctness among these different concepts in the revised paper.", "claims_and_evidence": "Some claims in the manuscript are unclear and lack sufficient supporting evidence:\n1. The authors reference [1], yet they assert that their work provides the first rigorous analysis of the expressive power of Knowledge Graph Foundation Models (KGFMs). However, [1] already investigates the expressive power of KGFMs and demonstrates that the proposed model, TRIX, is more expressive than ULTRA in distinguishing triplets. While the authors acknowledge [1], they overlook the contribution of [1] on the expressive power of KGFMs.\n2. The authors claim that “relational hypergraphs are a generalization of KGs used to represent higher-arity relational data”. However, existing literature predominantly employs n-ary relational graphs or hyper-relational knowledge graphs for this purpose.\n3. Theoretical results presented in the manuscript do not hold for some instances of MOTIF. The authors claim that MOTIF can represent a variant of InGram when the weighted relation graph is replaced. However, InGram requires that INIT_1 and INIT_2 be set to random initialization for all entities and relations. Given that all links are already differentiated through distinct representations of entities and relations, incorporating a motif that cannot be covered via a core-onto homomorphism from any motif already in $\\mathcal{F}$ cannot contribute additional expressiveness to the encodings. This indicates that the configuration of MOTIF used to produce theoretical results does not appropriately generalize to InGram.\n4. Certain statements in the manuscript are unclear. For example, the authors claim that “while the set of links distinguished by *any instance* in MOTIF($\\mathcal{F}$) is the same as those in MOTIF({h2t, h2h, t2t}) or MOTIF({t2h, h2h, t2t}), the ULTRA architecture is a strict subset of MOTIF($\\mathcal{F}$), so we cannot directly transfer these results to ULTRA.” in lines 250-255. This implies that ULTRA is a strict subset of MOTIF($\\mathcal{F}$) but not an instance of it, which is contradictory. How can model A be a subset of B while simultaneously not being an instance of B?\n\n[1] TRIX: A More Expressive Model for Zero-shot Domain Transfer in Knowledge Graphs, LoG 2024.", "methods_and_evaluation_criteria": "The proposed method has the following drawbacks:\n1. The proposed method is heuristic. Although the authors establish a condition for motifs that enhances expressive power, verifying whether this condition holds for a given motif requires manually comparing existing motifs with candidate motifs. This limits the practicality and scalability of the approach, particularly when applying it to improve the expressive power.\n2. The list of possible motifs is limited. The authors define and utilize only two types of motifs: path motifs and star motifs. Furthermore, only path motifs are employed in experiments on real-world datasets. A more comprehensive analysis should include ablation studies on the selection of motifs and provide additional examples of possible motif types to better assess their impact.", "theoretical_claims": "I have checked the logical flow of the proof.", "experimental_designs_or_analyses": "Yes, I have examined the soundness and validity of the experimental designs and have the following concerns:\n1. There is a potential issue related to test leakage. The authors pretrain MOTIF on FB15K-237, WN18RR, and CoDEX Medium. However, it is unclear whether there is any test leakage in the inductive datasets derived from these pretrained datasets, particularly those based on FB15K-237 (e.g., FB-v1\\~v4, FB-25\\~100) and WN18RR(e.g., WN-v1\\~v4). The authors should clarify whether any overlap exists between the training and test sets to ensure the validity of the evaluation. Additionally, the proposed method should be re-evaluated in a setting that explicitly prevents test leakage.\n2. A direct comparison with TRIX is necessary, as TRIX outperforms MOTIF in zero-shot setting and achieves comparable performance when fine-tuned. For example, on the inductive $e,r$ setting with 23 graphs, TRIX achieves an MRR of 0.368 in the zero-shot scenario, surpassing MOTIF’s MRR of 0.349. When fine-tuned, both models achieve an MRR of 0.401. These results suggest that TRIX is at least as competitive as MOTIF, raising questions about the significance of the proposed model’s contributions from a practical perspective.", "relation_to_broader_scientific_literature": "The paper builds upon prior work on Knowledge Graph Foundation Models (KGFMs), particularly ULTRA, by proposing an extension that aims to enhance expressiveness. ULTRA itself was introduced as a relation graph-based approach for predicting missing links in arbitrary knowledge graphs.\n\nThe paper aligns with prior work, such as TRIX, which has already explored the expressive power of KGFMs, demonstrating that models like ULTRA have inherent limitations in distinguishing triplets. The authors claim to extend ULTRA’s expressiveness by leveraging relational hypergraphs, but given prior work [1], the novelty of this contribution requires careful consideration.\nAdditionally, its reliance on motifs raises questions about scalability and practicality concerns that need to be further investigated.\n\n[1] TRIX: A More Expressive Model for Zero-shot Domain Transfer in Knowledge Graphs, LoG 2024.", "essential_references_not_discussed": "Although the authors have cited [1], a paper that discusses the expressive power of KGFMs, they do not provide a direct comparison with it. Given that [1] explicitly analyzes the expressive power of KGFMs and demonstrates its superiority over ULTRA in distinguishing triplets, the manuscript should clearly compare its approach with [1], particularly in terms of expressive power. Without this comparison, it is difficult to assess whether the proposed method provides a significant theoretical or practical advancement over existing work. \n\n[1] TRIX: A More Expressive Model for Zero-shot Domain Transfer in Knowledge Graphs, LoG 2024.", "other_strengths_and_weaknesses": "Strength\n\nThe proposed relational hypergraph is a reasonable extension of relation graphs, allowing for the capture of more complex relationships between relations. \n\nWeaknesses\n1. Please refer to the concerns and recommendations discussed in ‘Claims and Evidence’, ‘Methods and Evaluation Criteria’, and ‘Essential References Not Discussed’ for further elaboration on weaknesses regarding the manuscript's clarity, theoretical claims, and comparative analysis.\n2. Different concepts are notated in the same way. For instance, the authors use a character followed by parentheses (e.g., a()) to represent functions, (hyper)edges, and indicators, which could cause confusion for readers.", "other_comments_or_suggestions": "Typos\n1. Section 4, lines 151-152: \"We present MOTIF, as a general framework for KGFMs\" -> \"We present MOTIF, a general framework for KGFMs\".\n2. Section 4.1., lines 127-128: \"and G=(V,E,R) a KG\" -> \"and G=(V,E,R) be a KG\".", "questions_for_authors": "1. Please provide a direct comparison with TRIX in terms of expressive power and performance.\n2. The current description of the theoretical claims is confusing, as it suggests that the theoretical results apply to all instances of MOTIF, while the theoretical findings presented in Section 6.1 do not hold for some instances of MOTIF. Please clarify it.\n3. Can the procedure for adding motifs be automated? If so, how might this be achieved?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper delves into the expressiveness of Knowledge Graph Foundation Models (KGFMs) and proposes a novel framework called MOTIF to enhance their expressive power by utilizing richer motifs beyond binary interactions.
The authors rigorously establish the theoretical underpinnings of their proposed framework and empirically validate their claims through extensive experimentation, demonstrating the framework's effectiveness in capturing complex relational structures and its superiority over existing models like ULTRA. 

The idea to introduce higher order motifs to improve the expressiveness of KGFMs makes sense to me.  I have similar concerns about the additional computing cost as Reviewer EEM2, which has been addressed by the authors in the response.

The authors addresses potential concerns in the rebuttals regarding the comparison with concurrent work, TRIX, clarifying that while TRIX is a relevant and contemporaneous work, it is not mandatory to directly compare with it given the ICML policy on concurrent work.

The authors also addressed the reviewers' concerns by providing detailed responses and revisions to the manuscript, addressing issues such as the framework's scalability, the practicality of the proposed method, and the necessity for more intuitive explanations and examples.
Decision: Accept (poster)