In this paper, we present a multi-order interaction neural network (MINN) for relation prediction, which can calculate the 2ndorder and 3rd-order feature interactions and automatically combine them within linear complexity. The proposed MINN contains three layers: embedding, multi-order interaction pooling (MI-Pooling), and Deep & Wide layer. In embedding layer, we convert sparse input features into dense representations to narrow the size of features. In MI-Pooling layer, the 2nd-order and 3rd-order feature interactions are calculated and combined in linear time. The results of MI-Pooling will be input into a deep neural network (DNN) for learning nonlinear feature in the last Deep & Wide layer, which will output the nal prediction value. The experiments evaluating on two well-known datasets, WN18 and FB15k, show that MINN e ciently performs better than most of the state-of-the-art sparse models in relation prediction.
In general, some relations among entities are uncertain in the semantic web due to information missing. It's meaningful and interesting to predict accurately if a particular and unknown relation exists between two entities. For example, we may want to kown whether two people are brothers.
An RDF triple in semantic web can be represented as (entity1, relation,
entity2). When given such a triple, the goal of this paper is to predict if it is valid.
This task can be considered essentially as sparse prediction when a few relations
exist among a large number of entities. There are many researches about sparse
prediction recently. Factorization Machine (FM) is a classical method by using
the 2nd-order feature interactions [
Each element of a triple is treated as a feature. We transform it into vector represent (x1; x2; x3) as the input of MINN by one-hot encoder, where xi 2 [1:::size of f eaturei]. The MINN will output the existence probability of the triple
nally. MINN contains three main modules: embedding layer, MI-pooling, Deep & Wide layer. The architecture of model is shown in Fig. 1.
R3OLQJ
Embedding layer convert the sparse one-hot vector into dense representation, which can learn the initial information and reduce computation. Formally, let an input vector be Xin = (x1; x2; x3) and embedding matrix vecem 2 R3 K , where K is the embedding size. We can get dense embedding feature xemb 2 RK : xem = Xin vecem = (xv1; xv2; xv3) (1) Predicting Relations by Multi-Order Interaction Neural Network
MI-pooling is employed for extracting the 2nd-order and 3rd-order feature interactions from embedding features rstly. The former can be calculated by formula (2).
fSO(xem) = Xn Xn xvi xvj = 21 4 The complexities of both formulas are O(n). The two interactions are combined by weighted summation to learn muti-order features. The weights can be learned by the model so that the MINN could automatically select more important information from 2nd-order and 3rd-order interactions.
Finally, we employ a linear model to obtain the output in deep & wide layer, where the deep part can learn the high-level non-linear features and the wide can learn the linear and original features. 3
We evaluate the performance of MINN on two well-known datasets, WN18 and FB15k. Since negative samples are required for training models, we need to generate negative datasets. We generate a new sample by random replacing one entity of a triple, and if the sample is not in the datasets, it is a valid negative sample. The ratio of positive and negative samples is 1:1. We randomly divide the datasets into three parts: 70% (training), 20% (validation), and 10% (test).
We compare MINN with the state-of-the-art sparse prediction models: FM [
According to the experimental results, the following conclusions can be drawn. Firstly, the FM learns only 2nd-order features interaction, which performs worst. This demonstrates that 2nd-order features interaction is not enough to express the information of input features. Secondly, the DeepFM combines FM and DNN in parallel, and the performance of DeepFM is bettter than FM but inferior to the others. This shows that high-level non-linear features are necessary and low-order features play an important role when learning the high-level nonlinear feature. Finally, comparing to NFM and InteractionNN, the MINN combines the 2nd-order and 3rd-order feature interactions for learning nonlinear feature. The better performance demonstrates that the higher-order features have improved the performance of the model. However, the 3rd-order interactions of the RDF triples are not enough, that is, there is only one 3rd-order combination xv1xv2xv3 that contains 3rd-order interaction information. We will take more auxiliary semantic information into considering to exhibit the better performance. 4
In this paper, we present a novel neural network MINN for relation prediction by reducing to sparse prediction with higher-order feature interactions to extract more semantics. Our proposed MINN provides a linear computation of 2nd-order and 3rd-order feature interactions. The linear interaction method exactly make higher-order feature interactions feasiable in relation predication. We believe that our proposal is also helpful to other sparse predication. In the future work, we will consider more datasets with more features in our experiments. 5
This work is supported by the National Key Research and Development Program of China (2017YFC0908401) and the National Natural Science Foundation of China (61972455, 61672377). Xiaowang Zhang is supported by the Peiyang Young Scholars in Tianjin University (2019XRX-0032).