Neural-Symbolic Entangled Framework for Complex Query Answering

A great deal of previous research into KG has focused on using machine learning to reason with the embedding method. The effects have been shown in TransE TransE , TransH TransH , TransG TransG , ComplEx ComplEx , ConvE ConvE , DistMult DistMult and RotatE RotatE . These approaches aim to embed the entities and relations to a continuous vector space so that one-hop reasoning can be answered with link prediction. Different methods map the entities and relations into vector space with different distributions. Meanwhile, the rule and path-based models ptranse ; IterE ; yang2017differentiable ; sadeghian2019drum , try to use learned patterns of path or rules to do multi-hop reasoning.

However, KGE models lack the ability to handle complex logical operators like conjunction ($\wedge$), disjunction ($\vee$), and negation ($\neg$), and they are not easy to generalize to multi-hop queries. In contrast, our framework can alleviate the problem of cascading error during multi-hop reasoning and also support all of the logical operators above so that any KGE models could be used to answer the complex query.

To answer logical queries, some works GQE ; Q2B ; ConE ; Q2P ; BetaE ; FuzzQE aims to encode the complex query into a space that proposes various geometric shape to represent the entity set and support complex query reasoning. Generally, a FOL query is converted to a computation graph with a directed acyclic graph (DAG) structure with which the query representation could be iteratively computed using the logical operation in embedding space. GQE (graph-query embedding) GQE consider conjunction operator ($\wedge$) with vector representation. Q2B (query to box) Q2B replace the vector embedding with hyper-rectangles since it holds the idea that box embedding can represent sets of entities better and define the disjunctive norm form (DNF) to support the disjunction ($\vee$) operator. More recently, BetaE BetaE models the query and entities with beta distributions which could support the negation ($\neg$) operator. CQD CQD applies beam search to an embedding model. ConE ConE proposes a new geometry model that embeds entities with cones embedding. FuzzQE FuzzQE satisfies the axiomatic system of fuzzy logic to reason. Q2P (Query2Particles) Q2P encodes each query into multiple vectors. GNN-QE GNNQE concentrates on the interpretation of the variables along the query path.

Most of these methods usually design their geometric or distribution embedding to support logical operators but the effectiveness of the projection operator, which is the most basic operator, has not been discussed. Meanwhile, they only concentrate on the final answers as labels but ignore the intermediate entities during the query process which are also important for reasoning.

In our work, there are two ways to represent entities and relations. The neural part is just like the KGE or query embedding method we adopt, and rotatE RotatE is chosen in this paper which embeds entities and relations to a complex space $\mathbb{C}^{k}$. For the symbolic part, an entity and a relation are encoded as a one-hot vector and an adjacent matrix, respectively.

Specifically, given the KG $\mathcal{G}$, entity set $\mathcal{V}$ and relation set $\mathcal{R}$, an entity $e$’s embedding representation is a vector $\mathbf{v}_{e}\in\mathbb{C}^{k}$ and its symbolic representation is encoded as a one-hot vector $\mathbf{p}_{e}\in\{0,1\}^{1\times|\mathcal{V}|}$. Each relation $r$ is modeled as a vector $\mathbf{v}_{r}\in\mathbb{C}^{k}$ and the corresponding symbolic representation is an adjacent matrix $\mathbf{M}_{r}\in\left\{0,1\right\}^{|\mathcal{V}|\times|\mathcal{V}|}$ where $\mathbf{M}_{r}^{ij}=1$ if $r(e_{i},e_{j})\in\mathcal{G}$, else $\mathbf{M}_{r}^{ij}=0$.

Neural projection follows the embedding method, we use rotatE RotatE here as an example. For a projection query $(h,r,?)$, the functional mapping with relation $r$ is an element-wise rotation from $h$ to the target answer $t$:

$$\mathbf{v}_{t}=\mathbf{v}_{h}\circ\mathbf{v}_{r},\text{where}|\mathbf{v}_{r}|=1$$

(1)

and $\circ$ means Hadamard product. This step gets the predicted embedding which could be used to search for the target answers.

Symbolic projection is conducted with matrix multiplications followed $\mathtt{TensorLog}$ TensorLog :

$$\mathbf{p}_{t}=\mathbf{g}(\mathbf{p}_{h}\mathbf{M}_{r})^{\top}$$

(2)

where $\mathbf{p}_{t}$ is a multi-hot vector that represents the entities linked with $h$ via relation $r$, $\top$ means transposing the vector and $\mathbf{g}$ is a normalization function. Particularly, we consider the function as $\mathbf{g}(\mathbf{x})=\mathbf{x}/sum(\mathbf{x})$. This step gets the target entities by traversing KG.

Entangled projection tries to take advantage of these above two results. Since embedding prediction suffers from the cascading error but could obtain the answer not linked with $h$, while traversing KG could not get the answers which lack the edges to the head entity but the searched answers are convincing, ENeSy combines them in an entanglement way as illustrated in Figure 2. Specifically, the similarity between the predicted embedding $\mathbf{v}_{t}$ and all the entities are calculated first. We define the similarity function as:

$$\mathbf{S}(\mathbf{x},\mathbf{y})=\gamma-\left\|\mathbf{x}-\mathbf{y}\right\|_{1}$$

(3)

where $\gamma$ denotes the margin. The L1 norm function can be changed to any distance function. We define a new vector representation with these similarity values. After softmax function, we get a inferred vector $\mathbf{p}_{t}^{\prime}\in[0,1]^{1\times|\mathcal{V}|}$ which is generated from $\mathbf{v}_{t}$. With $\mathbf{p}_{t}^{\prime}$, a new symbolic vector $\mathbf{p}_{t}^{\prime\prime}$ is obtained by the following step:

$$\mathbf{p}_{t}^{\prime\prime}=\mathbf{g}(\mathbf{p}_{t}+\mathbf{p}_{t}^{\prime})$$

(4)

This new symbolic vector $\mathbf{p}_{t}^{\prime\prime}$ integrates the information from the embedding $\mathbf{v}_{t}$ with symbolic reasoning results $\mathbf{p}_{t}$. This procedure adds more entities, which might be the answer to the query which are not linked with $h$, to $\mathbf{p}_{t}^{\prime\prime}$. This enhancement eliminates the limitation of KG incompleteness of symbolic reasoning to some extent. Each element of $\mathbf{p}_{t}^{\prime\prime}$ could be regarded as the probability of the corresponding entity. Let’s assume the entity set with non-zero probability as $\mathcal{S}_{t}$, a aggregation function is employed to transfer the symbolic vector $\mathbf{p}_{t}^{\prime\prime}$ and the embedding of entities in $\mathcal{S}_{t}$ to a new embedding vector $\mathbf{v}_{t}^{\prime}$ with an MLP function:

$$\mathbf{v}_{t}^{\prime}=\sum_{i=1}^{|\mathcal{S}_{t}|}\mathbf{p}_{t}^{i\prime\prime}\text{MLP}(\mathbf{v}_{e_{i}})\mathbf{v}_{e_{i}},e_{i}\in\mathcal{S}_{t}$$

(5)

where $\mathbf{p}_{t}^{i\prime\prime}$ is the corresponding probability of $e_{i}$ in $\mathbf{p}_{t}$. This new embedding $\mathbf{v}_{t}^{\prime}$ aggregates the symbolic answer, Note that although we use the rotatE as the neural function, any other sufficiently expressive KG embedding model or the projection operator of any other query embedding models could be employed with our framework in theory.

With the symbolic vector $\mathbf{p}$, the logical operator intersection($\mathbf{p}_{1}\wedge\mathbf{p}_{2}$), union($\mathbf{p}_{1}\vee\mathbf{p}_{2}$) and negation ($\neg\mathbf{p}$) could be defined as follows:

$\displaystyle\mathbf{p}_{1}\wedge\mathbf{p}_{2}:\mathbf{g}(\mathbf{p}_{1}\circ\mathbf{p}_{2}),\quad\mathbf{p}_{1}\vee\mathbf{p}_{2}:\mathbf{g}(\mathbf{p}_{1}+\mathbf{p}_{2}-\mathbf{p}_{1}\circ\mathbf{p}_{2}),\quad\neg\mathbf{p}:\mathbf{g}(\frac{\alpha}{|\mathcal{V}|}-\mathbf{p})$

where $\circ$ is Hadmard product and $\alpha$ is a hyperparameter. After getting symbolic vector with these logical operators, the MLP function used in Equation (5) is employed to get an aggregated embedding.

The embedding and symbolic vector can both be used to get the final answers. For the neural part, the similarity between the embedding vector $\mathbf{v}$ and all the entities $e\in\mathcal{V}$ is computed with Equation (3), which is used to rank the candidate answers. For the symbolic part, since the vector $\mathbf{p}$ represents the probability of each entity, the answers can be directly obtained with ranked elements of $\mathbf{p}$. To make the ensemble using of the two type answers, we set $\lambda$ to get a combined result with $\mathbf{v}$ and $\mathbf{p}$ as:

$$\mathbf{a}=\lambda\mathbf{p}+\left(1-\lambda\right)\text{Softmax}(\mathop{\mathbf{Concat}}\limits_{\forall e\in\mathcal{V}}(\mathbf{S}(\mathbf{v},\mathbf{v}_{e})))$$

(6)

where $\lambda$ is the weight to balance the influence of $\mathbf{v}$ and $\mathbf{p}$ and $\mathbf{Concat}$ is a function mapping the similarity between all entities $e\in\mathcal{V}$ and $\mathbf{v}$ to a vector. The final answers can be determined with $\mathbf{g}(\mathbf{a})\in[0,1]^{1\times|\mathcal{V}|}$.

Given a query $q$ with answer entity set $\mathcal{S}_{q}$, after getting the final answer embedding $\mathbf{v}_{q}$ and symbolic vector $\mathbf{p}_{q}$, we construct two following objective loss functions:

	$\displaystyle L_{1}=-\text{log}\sigma(-\mathbf{S}(\mathbf{v}_{q},\mathbf{v}_{e}))-$	$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\text{log}\sigma(\mathbf{S}(\mathbf{v}_{q},\mathbf{v}_{e^{\prime}}))$		(7)
	$\displaystyle L_{2}=-\text{log}\sigma(\mathbf{p}_{e}\cdot\text{log}$	$\displaystyle[\mathbf{p}_{q}^{\top},\theta]_{+})$		(8)

where $e\in\mathcal{S}_{q}$ is an answer of $q$, $e^{\prime}\notin\mathcal{S}_{q}$ is a negative answer which is sampled randomly. $\sigma$ is the sigmoid function, $\cdot$ is dot-product and $[\mathbf{x},\theta]_{+}$ denotes the maximum value between each element of $\mathbf{x}$ and $\theta$, which is a threshold.

Meanwhile, the MLP function in Equation (5) needs to be pretrained individually. Since this function is employed to convert a symbolic vector to an embedding vector, and in the projection operator, we have $\mathbf{p}_{t}^{\prime}$ which is generated from $\mathbf{v}_{t}$, MLP could be used to convert $\mathbf{p}_{t}^{\prime}$ back to $\mathbf{v}_{t}$. Based on this, we also design a loss function to train this function as follows:

$$L_{3}=-\text{log}\sigma(-\mathbf{S}(\mathbf{v}_{t},\sum_{i=1}^{|\mathcal{S}_{t}^{\prime}|}\mathbf{p}_{t}^{i\prime}\text{MLP}(\mathbf{v}_{e_{i}})\mathbf{v}_{e_{i}})),e_{i}\in\mathcal{S}_{t}^{\prime}$$

(9)

where $\mathcal{S}_{t}^{\prime}$ is the corresponding entity set whose probabilities are not zero in $\mathbf{p}_{t}^{\prime}$. In the first step of the training process, the symbolic part is not included, and only the embedding of entities and relations will be trained with the link prediction task. Next, in the second step, the completed projection operator will be trained still by link prediction and the loss function is $L=L_{1}+L_{2}+L_{3}$. In theory, the model could answer complex query after the above two steps, but it could also be fine-tuned with complex query data using the loss function $L=L_{1}+L_{2}$.

Since meaningful FOL queries are usually not available in real scenes, we first report the results of models which are trained with only 1p query data, which also can be seen as link prediction task. The MRR results are shown in Table 1.

As the table shows, compared with pure embedding methods like GQE, Q2B, and BetaE, the performance of ENeSy significantly improves. Since the operators except the projection of these methods are parameterized, the ability to handle complex query is limited, but our model can be generalized to more complex query structures. Even though, the improvement on 1p query proves the advantages of generalizing other KG embedding models to solve this problem. Compared with FuzzQE, which could also be trained with link prediction, our model improves the average MRR of EPFO by about 2.6%(relatively 11.9%) on FB15K-237 and 1.6%(relatively 5.9%) on NELL-995. For the queries with negation, ENeSy provides a more absolute improvement, which is 1.5%(relatively 24.6%) and 2.1%(relatively 28.8%) on FB15K-237 and NELL-995. We believe the reason for this enhancement is that the symbolic representation can indicate the probability of each entity better.

The results of models trained with query data are also reported in Table 2. Compared with the average MRR in Table 1, the performance of most baselines improves a lot because of the labeled data of complex queries, but ENeSy still achieves the best performance on the average MRR of EPFO query and negation query. Moreover, our model could get closer results with different training settings. Specifically, the average MRR decreases by about 4.7% and 2.4% for EPFO and 5% and 4.1% for negation queries on FB15K-237 and NELL-995 respectively when trained with link prediction. For FuzzQE, the results decline about 9.9%, 7.5% for EPFO, and 22.4%, 8.8% for query with negation on FB15K-237 and NELL-995, respectively. This proves the stronger robustness of our methods. Note that though the 2p/3p results seem to be worse than FuzzQE, we can replace RotatE with the projection operator of FuzzQE, and the results should be the same in theory. All the models do not get good results on the negation query. We think it’s because, after the negation operation, most of the entities in KG will be included, which makes the reasoning hard. Maybe a better way is only considering the entities which belong to the same type as the entities before the negation operation.

To get deep insights into the neural and symbolic reasoning part of ENeSy, we investigate their impact in this section. In what follows, we first explore how symbolic affects the embedding results. We then examine the influence of embedding on symbolic. Finally, the effect of ensemble prediction is discussed. The results are based on FB15K-237, and the situation on NELL-995 is similar.