We study theoretical properties of embedding methods for knowledge graph completion under the "missing completely at random" assumption. We prove generalization error bounds for this setting. Even though the missing completely at random setting may seem naive, it is actually how knowledge graph embedding methods are typically benchmarked in the literature. Our results provide, to a certain extent, an explanation for why knowledge graph embedding methods work (as much as classical learning theory results provide explanations for classical learning from i.i.d. data).
Summary
This paper studied the knowledge completion problem from the viewpoint of statistical learning theory. More specifically, it formalized a knowledge graph completion problem as an estimation of the optimal embedding by assuming the canonical distribution derived from the embedding and derived the upper bound of misclassification rate of entities under the missing-completely-at-random assumption.
Decision
Although the formalization of knowledge graph completion problems is novel (to the best of my knowledge), there is much room for improvement in the organization of the paper. Therefore, I would recommend to reject the paper this time and to ask authors to revise the paper so that the paper is more accessible to researchers and engineers.
There are numerous existing works about the knowledge graph embedding problem and the knowledge graph completion problem using embeddings. However, few works have been done to justify these methods theoretically. This paper attempted to answer this question via statistical learning theorem perspectives. The theorems gave sufficient conditions in terms of the size of a knowledge graph and properties of embedding functions under which the misclassification rate goes to $0$. In this aspect, this paper gave insights into how we can give justifications to existing embedding methods.
However,  I think it is hard for those who are not familiar with this field to follow the logic of the paper, as I write in detail in the following sections. I understand some people argue that the paper organization is not essential for how a paper contributes to science and technology. However, the accessibility to the paper is vital to promote technical communications in different fields. Also, I believe it is beneficial for the paper to maximize its value. Thus, I would ask the authors to polish the paper.
Suggestions
- Introduction 
	- Please explain what knowledge graphs are in the introduction before explaining how knowledge graphs represent knowledge, or what problems of practically available knowledge graphs have.
	- I think it is a bit too casual and conversational to use wordings like "Please bare in mind" in papers.
	- I think it is helpful if the authors add a summary of theorems and its implication in the introduction to grasp the theoretical contributions the paper has made.
- Section 6, Theorem 1
	- Please describe what is the probability of $P$ and with respect to which probability distribution $\mathbb{E}$ takes the expectation.
- Section 7
	- The authors claim that Pinsker's inequality plays a central role in deriving the upper bound for the ratio of wrongly predicted triples. However, we cannot know how the authors used the inequality unless we see the proof of Theorem 3, which is available in the appendix.
	- In Theorem 3, the definition of "wrongly predicted triple" is missing. I only find a description related to it in the proof of Theorem 3 in the appendix. Could you add the definition in the main part?
- Section 8, Theorem 4
	- The statement of Theorem 4 says that $\mathbb{X}$ is a learned representation. But it is not available in the main article how we obtain it. We know that the authors used the maximum-likelihood estimator if we read the proof of the theorem. The author should clarify it in the statement of the theorem.
- Section 10
	- What does "this" mean in the title of the section?
	- In the initial reading, I could not understand the main point the authors want to address in the paragraph starting with Loss. I think authors can clarify the point by restructuring the paragraph.
Minor comments
- Section 2 and Section 6
	- The authors treated $\mathbb{X}$, which is the set of vector representations of objects and relations, as a lookup table in Section 2.2 and reinterpreted it as the subset of $\mathcal{X}^{|\mathcal{O}|+|\mathcal{R}|}$ in Section 6. I think we can simplify the description if we treat $\mathbb{X}$ as the subset of $\mathcal{X}^{\mathcal{O} \sqcup \mathcal{R}} := \{f: \mathcal{O} \sqcup \mathcal{R} \to \mathcal{X} \}$ and denote $\mathbb{X}(o)$ as $x_o$ in short hand for a representation $\mathbb{X}$ and an object $o\in \mathcal{O}$ (and similarly for $x_r$).
- Section 4
	- It would be helpful to make the correspondence explicit between each sentence and theorem later in the last paragraph. For example, "We prove a generalization bound for log-likelihood from which a bound on Kullback-Leibler divergence follows (Theorem 3)" or something like that. - Section 6, Theorem 1
	- The definitions of $\mathbb{X}_o$ and $\mathbb{X}_r$ are missing, if I do not miss something.
	- It is better to add the assumption that $\sup_{h, r, t} |\psi(x_h, x_r, x_t)|$ is finite.
- Section 12
	- "simplistic" means too simple by itself. So, "too simplistic" should be "too simple" or "simplistic".
Questions
- Section 4
	- I could not fully understand the intuition of the proof in the second paragraph. The authors think that the situation is desirable if multiple knowledge graphs are available. However, in the first approach, they concatenated the graphs into one (I interpreted the union of graphs as $\widehat{\mathcal{G}}_1 \cup \widehat{\mathcal{G}}_2 \cup \cdots \widehat{\mathcal{G}}_n$. Correct me if I am wrong). Since this operation would reduce the situation to the single-graph case, we cannot take advantage of multiple graphs.
- Section 7, Theorem 4
	- The upper bound is in terms of the estimator which maximizes the expected log-likelihood. I am wondering whether this estimator can achieve the best possible misclassification rate (i.e., $|\mathcal{F}/|\mathcal{O}^2|/|\mathcal{R}||$). I understand that it minimizes the discrepancy between the inferred distribution and the data generating distribution. But I am not sure it implies the least misclassification rate.
	- The small terms in the upper bound (i.e., first and second terms) depend on the number of objects $|\mathcal{O}|$ and not on relations $|\mathcal{R}|$. Since the role of $\mathcal{O}^2$ and $\mathcal{R}$ is symmetric mathematically (if I understand correctly), I feel it is weird that the additional terms do not necessarily go to zero when $\mathcal{R}\to \infty$. I particular, I expected that the additonal small terms depend solely on $|\mathcal{G}|=|\mathcal{O}|^2|\mathcal{R}|$.