COINs: Model-based Accelerated Inference for Knowledge Graphs

Thank you for your comments, we agree on the relevance of the proposed new experiments and also believe they will improve our work. Due to the limited page count, we could only showcase the most important results in the main text and deferred many helpful additional results to the appendix for the submission. Nevertheless, we have managed to generate new figures and have uploaded a new draft. We provide more details about these and answers to your questions below, but to summarise, new result discussion is available in appendix sections C1 and C2, while Figures 4, 5, and 6 are new or updated.

1. "More datasets should be evaluated, especially bigger ones like WikiKG90M-LSC."

• We agree on the relevance of experiments with larger datasets. We selected the three we use as the most classical ones for the field, and ones with the most available results from previous work to compare with as baselines. In fact, the WikiKG90M-LSC dataset does not have a publicly available test set with ground truth yet, as it was used for a recent competition. Nevertheless, we have started COINs-RotatE runs with larger knowledge graphs such as ogbl-biokg, but due to the greater number of edges, we require more time to achieve convergence. We would have no problem releasing these results when they are ready.

2. "Trade-off between error, speedup and number clusters should be investigated. Static min-cut algorithms (outside the end-to-end training) could be compared. What's the relationship between cut size, speedup and performance?"

• Thank you for the interesting analysis suggestion, we have managed to perform these experiments and obtain results. The full discussion is available in appendix sections C1 and C2, however here we summarize. We implemented the METIS min-cut algorithm (used for partitioning by DistDGL (Zheng et al. 2020)) as well as random uniform community assignment (used for partitioning by Pytorch-BigGraph (Lerer et al. 2019)), as alternatives to Leiden. We analyzed the cut sizes produced by all 3 (large range of resolution values for Leiden) in Figure 4. We then end-to-end trained and evaluated COINs-RotatE with all 3 community methods (a couple of resolution values for Leiden in ascending order) and plotted the relative error-scalability trade-off in Figure 6. The results can be summarized as follows: although the METIS and random communities might yield higher speed-ups, there are a lot of Leiden community assignments resulting in similar performance, and equally significant speed-ups but with significantly fewer parameters.

3. "Minimum cut literature studies the problem of reducing the number of inter-cluster relations. tf-GNN is another scalable GNN framework which uses sampling for large datasets."

• Thank you for your helpful suggestions. We have added a comment on tf-GNN in our introduction and corrected the error w.r.t min-cut literature (mention of the min-cut problem and reference to the METIS algorithm added in Section 2.3.3 Edge locality, which as mentioned above, we now consider METIS as an alternative method for obtaining the community partition and for which we obtained some initial experiment results).

4. "For dense graphs, the cut will be really poor. FB15K is the densest graph you considered. How dense is it per relation type? Is the cut quality poor here? Does that explain some of the results?"

• If we assume that there can be only one relation between two entities, FB15k-237 has 0.2934% percent of all possible edges present. This number is significant only when compared to the densities of WN18RR and NELL-995, which are 0.0111% and 0.0054% respectively, so at least 25 times denser than both. Thus yes, unfortunately, it was the hardest to obtain good community splits for FB15k-237 (max modularity achieved lower than 0.5, while could easily obtain 0.75-0.8 for the other two) and yes, the bad community split was the reason for the very bad results of TransE and DistMult on Freebase and we give a bit more details on this via Table 5 in the appendix too.

Thank you for your comments and support for our work. We have answered the few questions you had below.

1. "The theoretical justifications are mostly limited to the running times, and don't seem to go into details about why the prediction estimates obtained are also better."

• We chose to focus our theoretical analysis on the scalability effects, as we deemed these to be our main contribution, but we would be for sure very interested for future work to provide generalization guarantees. This task was deemed out of our research scope and we predict it would be very difficult: one would have to at least merge the representation theory results for all of the knowledge graph algorithms we considered, with our algorithm formulation and integration of communities into the representation. One can have nevertheless some crude intuition: using the principle of locality for prediction simply makes the task a bit easier (given good communities), as both the number of possible answers and non-answers to a query greatly fall in comparison when predicting over the whole graph.

2. "The data sets for the experiments are somewhat less well-known: so from the paper itself it's a bit hard to compare this approach with other embeddings (although there literature there is huge)."

• In fact, the datasets that we have chosen for evaluation are specifically the most standard for knowledge graph reasoning in an academic setting. The Freebase and Wordnet graphs appear in all of the original papers for TransE, DistMult, ComplEx and RotatE in some form (only Bordes et al. in 2013 used for TransE the versions with "inverse relation test leakage"), while NELL-995 is more common in GNN-based knowledge graph reasoning research (e.g. KBGAT). We reference all of these works.

3. "As someone unfamiliar with knowledge graphs (my backgrounds are more in optimization / numerical methods), a direct comparison of the overall objectives optimized in the Leiden algorithm and this algorithm would be quite helpful: right now I'm only able to piece together the overall objective function from the pseudocodes."

• We apologize for the confusion. To clarify, we do not replace the Leiden algorithm for community detection, in fact, we utilize it without modification (as a blackbox implementation) to obtain communities as a graph preprocessing step. The Leiden objective is the Constant-Potts-Model version of modularity and its optimization simply aims to yield better community partitions. On the other hand, given a community partition, COINs modifies the contrastive learning process of a given embedding algorithm by integrating the embedding of those communities into its objective.

We are grateful for your detailed comments and have implemented your suggestions for the text. The answers to your questions are below.

1. "First, The proposition doesn't prove the author's remark. For proposition 1 (equation 2), proving the lower bound on runtime didn't prove that your algorithm is better. I may show a lower bound of zero, and it says nothing."

• We do not wish to claim that the proven lower bound is sufficient evidence for superiority. We do not base our further analyses on it. It was presented as simply the limit of what can be possible with COINs. It is very important that we could achieve it and thus the lower-bound is tight. As a result, we do not need to worry about a vacuous lower-bound of 0.

2. "The current upper bound is simply trivial, and I see it's possible to make your lower bound an upper bound (just substitute the values)."

• Yes, we agree that the proof of the bounds is less rigorous than desirable. Thus, we amended this error the following way: we now show first with Proposition 3 that an extreme value of the evaluation cost is only achieved if the community sizes and/or evaluation edge counts per community are uniformly distributed. Then, we show with Proposition 4 that the value of $K$ is what decides whether the extreme point is a maximum or minimum.

3. "For proposition 2, equation 3 simply moves the left-hand side to the right-hand side. You need to specify the scenario and quantify the "expected time to a correct answer" in your proposition. Also, I need clarification on why the derivation is related to Prop 1 (with a missing constant 2). It should be simply "Our method is better when ratio A is better than ratio B" in the derivation.""

• Thank you for the helpful suggestion, we have both simplified and clarified better the reasoning behind Proposition 2.

4. "Second, you cannot control the cluster size of the community detection algorithm. Tuning the resolution parameter changes the number of clusters, but the size of each cluster depends on the graph structure and cannot be easily homogenized. There might be communities of a few nodes, and there might be a community consisting of 1/4 of the nodes. So, the analysis is actually "acceleration at the best case." The result is okay from a practical perspective, and showing good acceleration results is good enough."

• Yes we agree on the validity of your claim and counterexample. But to clarify, Proposition 1 holds for any disjoint partition $c$ and does not assume that Leiden community detection was used to obtain it. One can easily assign the groups arbitrarily focusing only on their size. E.g., with $c$=np.random.choice($K$, size=$|V|$) just like what Lerer et al. in 2019 employ for PyTorch-BigGraph, one achieves pretty uniformly sized communities with low enough variance in the sizes. The idea is that due to this lack of correlation in such an assignment, the community prediction step for us would be extremely difficult.

5. "Finally, the experiments don't support your claims in the introduction. All the 3 traditional datasets the authors tried can be run within hours or minutes on a single desktop. The experiments did show acceleration (in terms of vector evaluations), but the result doesn't support scalability compared to the scales in experiments from DistDGL or SMORE."

• We chose those datasets as most, if not all, previous work has produced baselines for us to compare with. More importantly, we do not claim to replace DistDGL or SMORE in all application settings. The key gaps in the research that we address is the requirement of multiple machines for lossless scalable prediction, as well as the lack of scalability improvements for knowledge graph model inference and not simply faster training data sampling and model optimization. If one has at their disposal compute for parallelization and has to guarantee no deviation from the baseline prediction power, the other frameworks are viable. As a side note, we utilize SMORE's improved training query and answer sampling too, while also noting the potential in parallelizing the intra-community embedding of nodes for future work.