How Expressive are Knowledge Graph Foundation Models?

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.

---

Claims And Evidence

1. 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.

2. 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.

3. (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.

4. 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.

---

Methods

1. (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.

2. 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.

---

Experimental Designs

1. We follow prior work (ULTRA) by pretraining on the same three datasets and setup to ensure fair comparison.

• 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.

• 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:

2. (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. MOTIF and TRIX differ fundamentally in expressiveness: each can distinguish relation pairs the other cannot, rendering them incomparable:

• 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.
• 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₂).

Incorporating higher-order motifs into TRIX could similarly boost its expressivity, highlighting our framework as a complementary way for improving KGFMs.

---

Weaknesses

We will refine our notation to ensure clarity and distinctness among these different concepts in the revised paper.

“Methods: ...The problem formulation is overly general, ... ”

The 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.

“Experimental Designs: …It would be beneficial for the authors to provide similar examples using real-world data ….” “W4. The experimental results on real-world data are not very convincing....”

To 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:

In 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.

“Theoretical Claims: I did not thoroughly verify the proofs, as the theoretical claims are not critical to this paper..."

We 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.

---

Strengths and Weaknesses:

“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,...”

We 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).

“W4. “The experimental results on real-world data are not very convincing....”

Please see our detailed response on experimental design and analysis.

---

Other comments:

“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.”

We 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$).

“S2. More generally, how are different entities and relations matched across various KGs? ...”

Our 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.

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.

“S3. A minor suggestion: In lines 111–113...”

We will modify these in the updated manuscripts.

We thank the Reviewer for considering ours a "strong contribution".

“Methods. Yes, but how much overhead does MOTIF introduce? Are these human-readable? Do MOTIFs scale to large-scale KGs without affecting the performance?”

“Q1: How much overhead does MOTIF introduce?”

This 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.

While 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.

“Q3: Are motifs interpretable by humans?”

If 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.

“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?...”

We 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.

“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?”

“Q2: What is the computational cost of using denser, richer motifs?”

“Q4: Is there an upper bound to adding motifs that start to deteriorate the performance?”

Thank you for these questions. We address each below:

• “1. Which motif type contributes the most? 2. Was there an ablation study conducted?”

We 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.

• “3. Can smaller graph modifications affect the performance?”

We 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.

• “4. How should a reader comprehend the upper bound of the motif complexity? Q2: What is the computational cost of using denser, richer motifs?”

Regarding 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.

• “Q4: Is there an upper bound to adding motifs that start to deteriorate the performance?”

Theoretically, 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.

“Other Strengths And Weaknesses. … I would like to understand the flexibility of incorporating the framework into existing KGs.”

Our framework is flexible and has been tested on 54 KGs from various domains and task settings, as shown in the experimental section.

“Other Comments. ...minor typos ...”

We will modify this in the updated manuscripts.