Towards Better Benchmark Datasets for Inductive Knowledge Graph Completion

We appreciate your help in improving our paper through you comments and questions. We respond to them below.

In particular, there is a lack of discussion and evaluation of datasets in real-world inductive settings.

Is it possible to evaluate some cases of new drugs, new patients, and cold start recommendations? I want to know whether phenomena like the correlation between PPR and SPD exist in these applications.

We appreciate the comment and would like to clarify a few details.

(1) We agree that there should be a focus on real-world KGs. In fact, the KGs used in our study span a number of different domains. This includes:

• General/Encyclopedic: This includes FB15k-237, CoDEx, and DBPedia100k.
• Drug Discovery: HetioNet
• Lexical/Linguistic: WN18RR

Our findings are consistent across each. We are thus confident that our analysis should apply to KGs from different domains.

(2) Our findings aren't related to the domain of the KG but due to how inductive datasets are constructed. In our study we find that regardless of the original KG, the older strategy for conducting inductive KG splits leads to this shortcut in the inference graph. This is because the shortcut is only related to the topology of the inference graph. This is why the PPR performance always increases significantly from transductive to inductive KGs.

Additionally, this is not something that is a concern in real-world datasets, as we don't explicitly sample a train and inference graph from a larger KG. In real-world situations, we are not given the train and inference KGs a priori. Rather, we simply seek to learn on one KG and transfer that knowledge to another. However, as shown in our paper, the older dataset strategy constructs datasets that exhibit unique patterns not found in other real-world KGs. It therefore doesn't reflect actual inductive KGC as we would not expect for the inference graph to have such properties.

We show in Section 4 that our proposed dataset construction strategy can indeed create inductive datasets that aren't unnecessarily modified and thus correspond to real-world KGs.

I think the main purpose of recreating the inductive dataset is to match it with its transductive counterparts. In my mind, the transductive datasets also have unrealistic problems.

Thank you for your comment. We agree that we want to sample the train and inference graphs such that their graph properties are similar to the transductive dataset. However we are unsure what kind of "unrealistic problems" you're referring to for transductive KGs. We believe that the existing transductive KGs are a good gauge of real-world KGC performance. This is due to two reasons:

1. These datasets often reflect real-world KGs. For example FB15k-237 is a subset of FreeBase, a prominent KG [1].
2. We don't observe the PPR shortcut on most transductive KGs.

If you would further expound on your thoughts, we would be glad to try to answer them.

[1] Bollacker, Kurt, et al. "Freebase: a collaboratively created graph database for structuring human knowledge." Proceedings of the 2008 ACM SIGMOD international conference on Management of data. 2008.

Another commonly used inductive dataset NELL is not studied in this paper.

We omit NELL-995 from our study due to quality concerns raised by [1]. We include a note of this in our original paper (see lines 804-806 in the revised version). Specifically, [1] shows that many of the triples used in the dataset are either too generic or meaningless. For example, [1] includes examples of two triples present in NELL-995 which are trivially wrong. We show them below:

• "(politician:jobs, worksfor, county:god)"
• "(person:buddha001, parentofperson, person:jesus)"

For more context, NELL-995 is derived from the Never Ending Language Learner (NELL) KG [2]. NELL automatically extracts facts from the internet. Each fact is further assigned a confidence regarding its truthfulness. E.g., a 90% implies the fact has a 90% chance of it being true. [3] used a version of NELL to construct NELL-995. However, they don't take into account the fact confidence when extracting facts for NELL-995. As such, it is likely that many facts are unlikely to be true. This is likely the cause for the observations made by [1].

Due to these observations, we don't think NELL-995 is an accurate reflection of real-world KGs, as many of its facts may be false.

[1] Safavi, Tara, and Danai Koutra. "CoDEx: A Comprehensive Knowledge Graph Completion Benchmark." EMNLP. 2020.
[2] Tom Mitchell, et al. 2018. "Never-ending learning". CACM, 2018.
[3] Xiong, et al. "DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning." EMNLP, 2017.

Dear Reviewer JoYY,

Thank you for taking the time to review our paper!

As the discussion deadline is rapidly approaching, we are eager to hear your response on our rebuttal as soon as possible. We hope that all aspects of our response addresses your concerns and await additional questions.

Regards,

Authors

Thank you for taking the time to review our paper. We reply to your questions below.

The applied graph partitioning strategy is straightforward and the research challenge in this paper is not significant.

We politely disagree with the reviewer as to the significance of our paper. Specifically, while we agree that the graph partitioning strategy is simple, we would like to note that it isn't the main contribution of our paper. Rather, our contribution is in the discovery, diagnosis, and correction of this shortcut. Furthermore, we argue that creating better and more realistic benchmark datasets is extremely important in fostering better understanding of real-world performance of different methods. We summarize our main contributions can be summarized as:

1. Discovering the widespread prevalence of the shortcut on inductive KGC datasets: We are the first to discover that this shortcut exists for inductive KGC datasets. This is important, as we show that it afflicts essentially all such datasets and results in an inflated test performance.
2. Understanding the root cause of this shortcut: We further seek to understand what causes this shortcut. We find that it is due to how previous datasets are constructed. This analysis is shown by (a) analyzing existing datasets (Sections 3.1-3.2) (b) generating our own datasets (Section 3.2 observation 3). These analyses empirically show that difference in SPD distribution between positives and negatives leads to this shortcut. Furthermore, it is very difficult to mitigate this shortcut using the original construction strategy as it often leads to either the train or inference graph being very small.
3. Introducing new datasets that mitigate the shortcut: Now that we understand the cause, we are thus able to introduce a simple but effective new method for creating datasets that is borne from first principles. We show in Section 4 that our method can dramatically reduce the prevalence of this shortcut. By removing the shortcut, the new datasets better reflect real-world applications of KGC and thus allow a better reflection of model performance than the older datasets.

Lastly, we'd like to note that the primary track/area of our paper is the datasets+benchmarks track. Therefore, the focus of our work isn't to introduce new model methodologies, but to create better and more realistic benchmark datasets. This is vital, because if we seek to truly understand the performance of different models and how they generalize to real-world applications, we must have effective and realistic benchmark datasets that reflect those situations.

In my opinion, the shortcut proposed in this paper is mainly caused by the negative-sampled evaluation

Recent studies, including RED-GNN and NBFNet, already employ the full evaluation (finding the positive entity from the entire entity set)

have the authors compared the performance differences between the two evaluation settings on new benchmarks?

We agree with the reviewer, and in fact, we actually do use the full evaluation setting and evaluate against all possible negative entities. This setting is used for all the results throughout our paper. As such, the negative sampling strategy cannot be the cause of this shortcut.

We choose to evaluate against all negative entities as we believe it reflects a more realistic scenario. In real-world situations we would in fact have to test against all entities, as we don't know which entity is correct ahead of time. Furthermore, some previous papers only use 50 random negatives for better efficiency, which while understandable, is not realistic in real-world settings where we don't have this ability.

We have revised our paper to more clearly state which evaluation setting we are using. We revised our paper on line 955 (highlighted red) to include that. Specifically we include:

We follow previous work Galkin et al. (2023); Zhang & Yao (2022); Lee et al.(2023) and evaluate against all possible negative entities.

We apologize for any confusion on the evaluation strategy.

why not improve the negative sampling strategy directly? For example, select entities having a much shorter distance from the query entity as negative samples. It could be independent of the graph structure

As noted in the previous comment, we evaluate against all possible negative entities. As such, there is no sampling to be done, as all entities regardless of their distance are included in the ranking.

Dear Reviewer mSV8,

Thank you for taking the time to review our paper!

As the discussion deadline is rapidly approaching, we are eager to hear your response on our rebuttal as soon as possible. We hope that all aspects of our response addresses your concerns and await additional questions.

Regards,

Authors

We appreciate your help in improving our paper through you comments and questions. We respond to them below.

Some part of the paper requires a better and more detailed explanation, e.g., the description related to page rank

Thank you for your feedback, we strive to make our paper as readable as possible.

We've included a more detailed description of pagerank and how it's used in our experiments in Appendix C. For clarity, we've also included the new portion below.

For a graph $G=(V, E)$, PageRank Page et al. (1999) calculates an importance score for each node. The importance score for a node $v$ is determined by computing the probability of a random walk of any length ending in that node. The rationale is that the nodes that are most likely to be visited, are most important to the underlying graph topology. The pagerank score for all nodes, $\text{pr} \in \mathbb{R}^{\lvert V \rvert}$, can be computed by (1) randomly being the walk at any node with equal probability, (2) continuously applying random walks until we reach a stationary distribution, and (3) randomly teleporting back to the starting node with probability $\alpha$. Higher values of $\alpha$ help discourage the importance of longer walks. This can be computed from the following recurrence relation:

$

	\text{pr}^{(t+1)} = (1 - \alpha) W  \text{pr}^{(t)} + \alpha \text{pr}^{(0)},      \text{(2)}

$

where $W$ is the random walk matrix $D^{-1} A$ and $\text{pr}^{(0)} = \mathbf{1} / \lvert V \rvert$. The pagerank score is equivalent to $t=\infty$.  

Personalized PageRank (PPR) Page et al. (1999) generalizes this formulation by allowing us to customize which nodes we begin the random walk at, i.e., $\text{pr}^{(0)}$. For example, we may only be interested in the PageRank score relative to a single node $s$. As such, the PageRank scores are personalized to the node $s$. We denote this quantity as $\text{pr}\_{s}$. This can be computed in the same manner as Eq. (2) by further modifying the initial probability vector $\text{pr}^{(0)}$ to the relevant starting nodes:

$ \nonumber \text{pr}^{(0)} = \begin{cases} 1 & \text{when i = s } \\ 0 & \text{else} \ \end{cases}

$

where $i$ denotes entry $i$ in the vector. Note that PPR is not restricted to only one seed node, but can be personalized to a set of nodes $S$. PPR can be equivalently expressed as the weighted sum of random walks beginning from $s$:

$

	\text{pr}\_{s} = \alpha \sum\_{k=0}^{\infty} (1-\alpha)^k W^k \text{pr}^{(0)}.  \text{(3)}

$

In practice, directly computing the recurrence relation Eq. (2) or (3) is prohibitively expensive. Multiple approximation approaches have been proposed to more effectively compute the PPR score such as Andersen et al. (2006), which we employ in our paper.

In our experiments, we calculate the PPR of KGs, which further include a relation. However, we completely ignore any relational information when computing the PPR scores. This is done by: (1) Removing all edge types and (2) Assigning an edge weight of 1 to all edges. We further remove any directional information from the edges, thus transforming the graph to an undirected graph. The PPR is then computed on this new undirected graph. We set $\alpha=0.15$ in all our experiments. However, despite these modifications, we show in Section 3 that PPR can still achieve strong performance during testing. This is due to a shortcut introduced during the dataset creation that allows for PPR to discriminate between positive and negative facts.

Please let us know if there is any other part of the paper that you think is unclear and requires additional explanation.

Dear Reviewer wYLD,

Thank you for taking the time to review our paper!

As the discussion deadline is rapidly approaching, we are eager to hear your response on our rebuttal as soon as possible. We hope that all aspects of our response addresses your concerns and await additional questions.

Regards,

Authors

Analysis of Other (E, R) Inductive Datasets two new (E, R) datasets (PediaTypes and WikiTopics)

We include the analysis for both sets of datasets. As before, the performance is Hits@10 and for predicting the correct node (h, r, ?). For each dataset we measure:

• Performance of ISDEA+ on 50 negatives. The performance is taken from the paper. This is Table 1b for PediaTypes and Table 7b for WikiTopics (we use the best here). For WikiTopics, the ISDEA+ performance isn't reported for three datasets.
• Performance of PPR on 50 negatives
• % Difference in performance (50 negatives). Note that a negative value means PPR performs better
• Performance of PPR when evaluating on all negatives . This allows us to compare our paper's results.
• The $\Delta$ SPD of each dataset.

The results are in the two tables below, where we group the PediaTypes and WikiTopics datasets separately. We also include the mean of each column as the final row.

We make several observations:

1. The difference in performance (50 negatives) between ISDEA+ and PPR is very small across all datasets. Across the 8 PediaTypes datasets, ISDEA+ only performs 0.4% better on average. For WikiTopics, this number is 14.2%. This is in fact lower than what we found in our paper for an inductive dataset, where neural methods performed 29% better than PPR.
2. The $\Delta$ SPD of these datasets is high. It is on average 2.2 and 2.7 for PediaTypes and WikiTopics, respectively. This is higher than that of the transductive datasets used in our paper (1.2 on average) and more in line with inductive datasets (4.7 across all and 2.1 when WN is excluded as it features very high values).
3. The PPR performance on all negatives is very high. On average, it is 32.5% and 38.3% on PediaTypes and WikiTopics, respectively. This is similar to the inductive datasets used in our study, where the average PPR performance is 35.6%.

These results show that these datasets suffer from the same shortcut found in our paper. This is as expected, as the PediaTypes datasets are constructed using the traditional method subgraph-based described in our paper. Also, WikiTopics uses the Forest Fire [1] sampling method, which generally favors locality, and thus will have the same downsides as the subgraph-based method.

We have revised our paper to include these results. See Appendix I.

PediaTypes Results:

WikiTopics Results:

[1] Leskovec, Jure, Jon Kleinberg, and Christos Faloutsos. "Graph evolution: Densification and shrinking diameters." TKDD, 2007.

It seems that the results of ULTRA [2] on the new inductive datasets are placed in Figure 6, separate from the main (E, R) results shown in Table 4. Could you clarify why these results are presented separately?

We apologize for the confusion.

As the reviewer noted, ULTRA is presented separately due to the fact that ULTRA is zero-shot while the other methods in Table 4 are not. This allows us to properly delineate between the type of methods. To make this clearer, we revised the paper to include this note, specifically we included in red on lines 520-522.

Since the setting of ULTRA differs from that of the other methods (i.e., 0-shot), we display it separately from the other methods in Tables 3 and 4.

Thank you for taking the time to review our paper. We reply to your questions below.

Evaluation of Other (E, R) Inductive Methods (ISDEA+ and DEq-InGram)

We appreciate the reviewer bringing these methods to our attention.

We used the official implementation of both methods. The results of each are over 5 random seeds. We'd like to clarify that in their paper, they only evaluate against 50 randomly selected negative entities. However, this diverges from the setting used in our paper and others (see ULTRA, InGram, RED-GNN) where we evaluate against all possible entities. To properly compare against the result in our paper, we evaluate against all negative samples.

(1) DEq-InGram: We provide the results of DEq-InGram in the tables below for both (E) and (E, R) datasets broken down by inference graph. Furthermore, we include the rank of the method in parentheses, such that 1 means it is the best method. The full results are included in the revised paper in Tables 3 and 4.

We observe that (1) It performs strongly in the (E, R) task (2) It improves upon standard InGram on each dataset. These results suggest that DEq-InGram can greatly improve the performance of InGram and achieve competitive performance on (E, R) datasets.

(2) ISDEA+: Curiously, when running ISDEA+ we found that when evaluating against all possible entities, we struggle to achieve performance marginally better than 0. This applies both to our datasets and those used in the original ISDEA+ paper. We provide more analysis of this issue below.

We first illustrate this problem on both the WN18RR (E) and FB15k-237 (E, R) datasets. Like detailed in their paper, we tune the learning rate from {1e-2, 1e-3, 1e-4}. They further mention tuning the weight decay from {5e-4, 0}, however we didn't find this in their code and thus omitted it. We further tuned the number of negatives per positive samples in training from {2, 16, 32}. In their paper they only train for 10 epochs, however we increase this to 200 epochs as the performance after 10 was nearly always 0.

The results are shown below for Hits@10 when evaluating using all negatives and 50 random. We find that while the performance is very low when using all negatives, it is quite high when using 50.

To ascertain if this is just a problem with our datasets, we further check the performance on the WikiTopics and PediaTypes datasets. We choose EN2FR-15K-V2 and wikidata_artv2 as representative datasets. For both datasets, we use the exact training settings provided by the authors (note that wikidata_artv2 is trained under the meta learning setting). However, we observe the same issue as before, where the performance against all negative entities is extremely low.

Due to these issues, we believe that there is a bug in their code, causing the performance against all negative entities to be artificially low. Note that we are using their code, and have not modified the code for evaluation at all. We have reached out to the authors with our findings and are waiting for a response. We will update you if we are able to fix this issue.

ISDEA+ Performance on New Datasets:

ISDEA+ Performance on WikiTopics & PediaTypes:

Including discussions of all (E, R) capable methods, i.e. InGram (DEq-InGram), ULTRA, ISDEA+, in Section 2 (around lines 134-139)

We included a discussion of ISDEA+ and DEq-InGram in our revised paper. See lines 136-140 in red. For convenience, we also include the added component below:

Gao et al. (2023) introduces the concept of “double permutation- equivariant representations” as a way to model KGs that are equivariant to permutations of both the entities and relations. They theoretically show that capturing this property is essential for proper generalization across KGs. To this point these introduce a new method ISDEA/ISDEA+ that can satisfy this property. They further introduce a variant of InGRAM Lee et al. (2023), DEq-InGram, that endows it with the ability to compute double equivariant representations.

Thank you very much!

Please let us know if you have any other questions. We'll be happy to answer them.