HAHE: Hierarchical Attention for Hyper-Relational Knowledge Graphs in Global and Local Level

HKGs comprise hyper-relational facts (H-Facts). Typically, an H-Fact can be represented as $\mathcal{H}=\{((s,r,o),\{(a_{i}:v_{i})\}^{m}_{i=1})|s,o,v_{1},...,v_{m}\in\mathcal{E},r,a_{1},...,a_{m}\in\mathcal{R}\}$, where $(s,r,o)$ represents the main triple and $\{(a_{i}:v_{i})\}^{m}_{i=1}$ represents m auxiliary attribute-value qualifiers.

The link prediction (LP) task on HKGs is to predict missing elements from H-Facts, where missing elements can be entities $\in\{s,o$ $\left.,v_{1},\ldots,v_{m}\right\}$ or relations $\in\left\{r,a_{1},\ldots,a_{m}\right\}$.

Since there are more than two entities in an H-Fact, we introduce hypergraph learning (Feng et al., 2019). A hypergraph of HKG, $\mathcal{G}_{H}=\{\mathcal{E}_{H},\mathcal{H_{H}},\mathcal{I}_{H}\}$, contains a node set $\mathcal{E}_{H}$=$\mathcal{E}$, a hyperedge set $\mathcal{H}_{H}$=$\mathcal{H}$, and a special incidence matrix $\mathcal{I}_{H}$ that records the weights of each hyperedge. $\mathcal{I}_{H}$ is a $|\mathcal{E}_{H}|\times|\mathcal{H}_{H}|$ matrix defined as follows:

		$\displaystyle h(v,e)=1,\text{ if }v\in e,$		(1)
		$\displaystyle h(v,e)=0,\text{ if }v\notin e,$

where $v\in\mathcal{E}_{H}$, $e\in\mathcal{H}_{H}$. $h$ is a fuction to represent the value in $\mathcal{I}_{H}$. For a node $v\in\mathcal{E}_{H}$, its degree is defined as $d(v)=\sum_{e\in\mathcal{H}_{H}}h(v,e)$, which represents the number of times that a node (entity) appears in different hyperedges (H-Facts) in the whole HKG.

Multi-position prediction is a new meaningful task with more practicality than the one-position link prediction task on HKGs. For HKG link prediction, in one main triple, we can predict another element for every two of them we know, i.e., we can predict ($s,r,?$), ($s,?,o$), ($?,r,o$). In one auxiliary attribute-value qualifier, if we know any of the attributes and values of one of the auxiliary attribute-value qualifiers, we can predict the other, i.e., ($a,?$), ($?,v$). Thus in practical link prediction, there are some problems have two or more prediction points for example ($s,r,?,a_{1},?,a_{2},v_{2}$) (prediction position one in the main triple and the other in the first attribute-value qualifier) or ($s,r,o,a_{1},?,a_{2},?$) (both predicted positions are in the auxiliary attribute-value qualifiers). We refer to tasks with two or more prediction positions in link prediction tasks as multi-position prediction tasks on HKGs.

HKGs $\mathcal{G}=\{\mathcal{E},\mathcal{R},\mathcal{H}\}$ consist of multiple hyper-relational facts (H-Facts) $\mathcal{H}$ with entities $\mathcal{E}$ and relations $\mathcal{R}$. Since each H-Fact represents an n-ary relation (n>2) and has rich, heterogeneous semantic information, we model HKGs in terms of global-level hypergraph-based representation and local-level sequence-based representation with hypergraph dual-attention layers and heterogeneous self-attention layers respectively. The overview of HAHE is illustrated in Figure 3. For global-level representation, we define $\mathcal{G}_{H}=\{\mathcal{E}_{H},\mathcal{H}_{H},\mathcal{I}_{H}\}$ to represent the graph structure of entities. Unlike the regular graph, the hyperedges can connect more than two entity nodes. Moreover, we use incidence matrix $\mathcal{I}_{H}$ to represent the association information of nodes and hyperedges. For local-level representation, every H-Fact has the structure of one main triple and several auxiliary attribute-value qualifiers $\mathcal{H}=\{((s,r,o),\{(a_{i}:v_{i})\}^{m}_{i=1})|s,o,v_{1},...,v_{m}\in\mathcal{E},r,a_{1},...,a_{m}\in\mathcal{R}\}$, which represents the semantic information of facts. We can fully connect entities and relations in H-Facts and represent them as heterogeneous semantic sequence structure, containing five kinds of nodes $s,r,o,a,v$ and 14 kinds of edges $s-r,s-o,r-o,s-a,s-v,r-a,r-v,o-a,o-v,a_{i}-a_{j},o_{i}-o_{j},a_{i}-o_{i},a_{i}-o_{j}$, where $i,j$ are the serial numbers of different qualifiers.

As shown in Figure 4(a), entity embedding first utilizes Hypergraph Dual-Attention Layers to learn hypergraph structural information in global level. Previous Hypergraph Attention Network methods created a transformed ordinary graph by full joining nodes within the same hyperedge and applying GAT. The hypergraph representation loses because the ordinary graph after this transformation cannot distinguish whether two nodes are within the same hyperedge or different hyperedges. We first initialize the entities as nodes with embedding as $\boldsymbol{h}_{v_{i}}\in\mathbb{R}^{d}$, where $v_{i}\in\mathcal{E}_{H}$ and $d$ is dimension of embedding, and initialize the H-Facts as hyperedges with embedding as $\boldsymbol{h}_{e_{i}}\in\mathbb{R}^{d}$, where $e_{i}\in\mathcal{H}_{H}$. Then the node and hyperedge embeddings are projected into the same space to obtain $\mathbf{W}\boldsymbol{h}_{v_{i}}$ and $\mathbf{W}\boldsymbol{h}_{e_{i}}$ ,where $\mathbf{W}\in\mathbb{R}^{d\times d}$. The attention from nodes to hyper-edges (N-to-H Attention) is performed as follows:

$$\alpha_{ij}=att\left(\mathbf{W}\boldsymbol{h}_{e_{i}},\mathbf{W}\boldsymbol{h}_{v_{j}}\right)|v_{j}\in e_{i},$$

(2)

where $\alpha_{ij}$ indicates the importance of node $v_{j}$’s features to hyperedge $e_{i}$, $att$ is N-to-H Attention function where we choose a single-layer neural network with concatenation operation. $v_{j}\in e_{i}$ means we only calculate the attention where node $v_{j}$ is in hypergraph $e_{i}$, which is indexed by hypergraph incidence matrix $\mathcal{I}_{H}$. Then, the information of nodes is aggregated to hyperedges:

$$\tilde{\boldsymbol{h}}_{e_{i}}=\sigma\left(\sum_{v_{j}\in e_{i}}\frac{\exp\left(\operatorname{LR}\left(\alpha_{ik}\right)\right)}{\sum_{v_{k}\in e_{i}}\exp\left(\operatorname{LR}\left(\alpha_{ik}\right)\right)}\mathbf{W}\boldsymbol{h}_{v_{j}}\right),$$

(3)

where $\tilde{\boldsymbol{h}}_{e_{i}}\in\mathbb{R}^{d}$ is updated hyperedge embeddings and $LR$, $\sigma$ are activation functions. After that, we use a similar way to aggregate the information of updated hyperedges back to nodes with Attention (H-to-N Attention) as follows:

$$\beta_{ij}=att\left(\mathbf{W}\boldsymbol{h}_{v_{i}},\mathbf{W}\boldsymbol{h}_{e_{j}}\right)|e_{j}\in v_{i},$$

(4)

$$\tilde{\boldsymbol{h}}_{v_{i}}=\sigma\left(\sum_{e_{j}\in v_{i}}\frac{\exp\left(\operatorname{LR}\left(\beta_{ik}\right)\right)}{\sum_{e_{k}\in{v}_{i}}\exp\left(\operatorname{LR}\left(\beta_{ik}\right)\right)}\tilde{\boldsymbol{h}}_{e_{j}}\right),$$

(5)

where $\beta_{ij}$ denotes the importance between updated hyperedge $e_{j}$ and node $v_{i}$, and $\tilde{\boldsymbol{h}}_{v_{i}}$ is the updated node embedding. This way, we update the global hypergraph entity embedding and achieve node-hyperedge-node dual-attention message passing. Though we introduce more hyperedge embeddings than ordinary GNNs, they are only used as an intermediate weight variable for hypergraph attention computation. PyG makes dual-attention easy to implement, making it scalable to large graphs as GNNs.

After hypergraph dual-attention layers, H-Facts distribute updated node embeddings to sequence embeddings with relation embeddings, and fed them into Heterogeneous Self-Attention Layers.

Each element in the sequence $\boldsymbol{x}_{i}\in\mathbb{R}^{d}$ has five roles, including $s,r,o,a,v$, and a total of 14 kinds of edge with other elements in the sequence $\boldsymbol{x}_{j}\in\mathbb{R}^{d}$. So, as shown in Figure 4(b), we design a heterogeneous self-attentive layer with both node-bias and edge-bias to learn the local semantic information of the H-Facts. The elements in the sequence pass through this attention layer and update the embedding as follows:

$$\gamma_{ij}=\frac{\left(\mathbf{W}_{role(i)}^{Q}\boldsymbol{x}_{i}+\mathbf{b}_{ij}^{Q}\right)^{\top}\left(\mathbf{W}_{role(j)}^{K}\boldsymbol{x}_{j}+\mathbf{b}_{ij}^{K}\right)}{\sqrt{d}},$$

(6)

$$\tilde{\boldsymbol{x}_{i}}=\sum_{j=1}^{n}\frac{\exp\left(\gamma_{ik}\right)}{\sum_{k=1}^{n}\exp\left(\gamma_{ik}\right)}\left(\mathbf{W}_{role(j)}^{V}\boldsymbol{x}_{j}+\mathbf{b}_{ij}^{V}\right),$$

(7)

where $\gamma_{ij}$ is the importance between one element in sequence $\boldsymbol{x}_{i}$ and another $\boldsymbol{x}_{j}$, $\mathbf{W}_{role(i)}^{Q},\mathbf{W}_{role(i)}^{K},\mathbf{W}_{role(i)}^{V}\in\mathbb{R}^{d\times d}$ are the linear weight metrics of query, key, value, and five different kinds of $\boldsymbol{x}_{i}$ pass through different weight metrics indexed by $role$ function as the node-bias, and $\mathbf{b}_{ij}^{Q},\mathbf{b}_{ij}^{K},\mathbf{b}_{ij}^{V}\in\mathbb{R}^{d}$ are designed as the edge-bias. Then the sequence embeddings are updated by learning the semantic information inside the H-Facts as $\tilde{\boldsymbol{x}_{i}}\in\mathbb{R}^{d}$.

Finally, the updated sequence embeddings are selected for the embedding at the position to be predicted $\tilde{\boldsymbol{x}}_{p}$ with MLP decoder to get the prediction distribution and obtain the link prediction results.

$$\boldsymbol{P}=softmax(\boldsymbol{MLP}(\tilde{\boldsymbol{x}}_{p})\mathbf{E}^{\top}),$$

(8)

where $\boldsymbol{MLP}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, $\mathbf{E}\in\mathbb{R}^{|\mathcal{E}|\times d}$ shares the initial element embedding matrix, $\boldsymbol{P}\in\mathbb{R}^{|\mathcal{E}|}$ is obtained after softmax operation, which denotes the similarity probability of $\tilde{\boldsymbol{x}}_{p}$ with each element in HKG for obtaining the link prediciton answers.

The model trains through the final loss, which is calculated by the similarity between the target of prediction and all entities:

$$\mathcal{L}=\sum_{t=1}^{|\mathcal{E}|}{\mathbf{y}_{t}\log\boldsymbol{P}},$$

(9)

where $\mathbf{y}_{t}$ is the $t$-th entry of the label $\mathbf{y}$.

For Multi-position Prediction, due to the fully connected attention mechanism, HAHE can accomplish the multi-position prediction task of HKG by masking two or more entities or relations at two or more positions in the same hyper-relational fact. After passing the MLP encoder, HAHE can get the prediction value $\boldsymbol{P}_{i}(i\geq 2)$ of the corresponding positions, and find the entity or relaiton with the highest similarity among all HKG elements as the prediction results respectively.

In this experiment, we evaluate our model on the link prediction task. For entity prediction, the results of our model and each variant of our model can be found in Table 2. For relation prediction, the result is shown in Appendix C. We can observe that the HAHE outperforms the other current methods on all three datasets. On JF17K, for the prediction of subject and object, HAHE reports an improvement of 0.6 (0.9%) MRR points, 1.5 (2.7%) H@1, and 3.6 (4.6%) H@10 compared with the best approach. For the prediction of all entities, HAHE reports a gain of 1.2 (1.8%) MRR, 1.5 (2.5%) H@1, and 1.7 (2.1%) H@10 compared with the next-best approach. For the other two datasets, we also have different degrees of improvement. For WD50K, the latest high-quality HKG dataset, our model has the largest improvement over the existing SOTA model GRAN, with an MRR improvement of about 10 points, which proves that this model is more suitable for hypergraph-structured knowledge graphs with hyper-relational facts beyond binary relation.

The hypergraph dual-attention mechanism, node heterogeneity, and edge heterogeneity are the three components of HAHE that are required for its operation. We evaluate seven different variants of HAHE, irrespective of whether or not each component is helpful. When evaluating each model variant with a variety of hyperparameters, the results of the optimal prediction were recorded. For different HAHE variants in Figure 5(a), it can be observed that hypergraph dual-attention, node heterogeneity, and edge heterogeneity all contribute to the accurate result of our complete model. In addition, we have outlined the specific results of three primary  HAHE variants in Table 2. Each variant lacks a necessary component that is required. Through comparison, our experiment results intuitively demonstrated the effectiveness of HAHE.

Then, we did more refined ablation analysis to explore the significance of the hypergraph dual-attention mechanism in global level and heterogeneity of nodes and edges in local level, respectively.

We statistically displayed the entity evaluation results of JF17K by the degree of entities in the HKG hypergraph structure to investigate the hypergraph dual attention mechanism. As shown in Figure 5(b), the hypergraph dual-attention mechanism improves the prediction accuracy of entities with different degree. Due to the presence of the attention mechanism, the entity feature information will help in message passing of global information by the hyper-relational facts (hyperedges). For entities with higher degree, the hypergraph dual-attention mechanism can better capture the global features of the hyperrelational facts. Entities with fewer degrees have little impact on capturing global information, but entities with more degrees compensate for this and improve their prediction accuracy.

The experimental results show that both node-bias and edge-bias with heterogeneity can better distinguish different types of entities in an H-fact and different types of relationships between them in local level. Moreover, we find that node-bias plays a more prominent role than edge-bias in the subject/object prediction tasks as shown in Figure 5(c), because the entity roles in the main triplet are more diverse than those in the qualifier. And on the element prediction task in qualifiers, edge-bias is better than node-bias as shown in Figure 5(d), because edge-bias can distinguish the relationship between corresponding attribute-value pairs $(a_{i},v_{i})$ and non-corresponding attribute-value pairs $(a_{j},v_{i})$ rather than node-bias.

JF17K, WikiPeople, and WD50K were applied to test our multi-position prediction model. As an example, in Figure 6, our model outputs the embedding for each position and calculates the joint probability distribution for each candidate answer tuple. Because the increase of predicted positions leads to more answer sets than predicted by the unit placement link, we set the evaluation threshold to keep only the higher scoring answer tuples to obtain the evaluation results.

As shown in Table 3, we evaluated 2-position prediction and 3-position prediction on three HKG datasets, respectively, and used MRR to rank the answer tuples. The test set has three categories: Ent-Ent, Ent-Rel, and Rel-Rel. Ent-Ent and Rel-Rel indicate that all predicted locations are entities or relations, and Ent-Rel indicates that entities and relations are missing jointly. In addition, whether the main triple is complete divides the sample into two categories. "av" indicates that all predicted positions are in the auxiliary qualifiers, while "sro/av" indicates that the main triple has lost a position" and others in qualifiers. "all" includes both categories. According to the results of multi-position prediction tasks, HAHE performs better on the high-quality WD50K dataset, and more positions predicted or one position in the main triple makes the prediction more difficult.