Representation Learning with Weighted Inner Product for Universal Approximation of General Similarities

1 Introduction

Representation learning of graphs, also known as graph embedding, computes vector representations of nodes in graphstructured data. The learned representations called feature vectors are widely-used in a range of applications, e.g., community detection or link prediction on social networks [Perozzi et al., 2014; Tang et al., 2015; Hamilton et al., 2017]. Words in a text corpus also constitute a co-occurrence graph, and the learned feature vectors of words are successfully applied in many natural language processing tasks [Mikolov et al., 2013; Pennington et al., 2014; Goldberg, 2016].

The feature vector is a model parameter or computed from the node's attributes called data vector. Many of state-ofthe-art graph embedding methods train feature vectors in a low dimensional Euclidean space so that their inner product expresses the similarities representing the strengths of association among nodes. We call this common framework as inner product similarity (IPS) in this paper. IPS equipped with a sufficiently large neural network is highly expressive and it has been proved to approximate arbitrary Positive Definite (PD) similarities [Okuno et al., 2018], e.g., cosine similarity. However, IPS cannot express non-PD similarities.

To express some non-PD similarities, similarity functions based on specific kernels other than inner product have also been considered. For instance, Nickel et al. [2017] applied Poincar´e distance to learn a hierarchical structure of words in hyperbolic space. Whereas practitioners are required to specify a latent similarity model for representation learning on a given data, finding the best model is not a simple problem, leading to a tedious trial and error process. To address the issue, we need a highly expressive similarity model.

Recently, a simple similarity model named shifted inner product similarity (SIPS) has been proposed by introducing bias terms in IPS model [Okuno et al., 2019]. SIPS can approximate arbitrary conditionally PD (CPD) similarities, which includes any PD similarities and some interesting similarities, e.g., negative Poincar´e distance [Nickel and Kiela, 2017] and negative Wasserstein distance [Kolouri et al., 2016]. However, the approximation capability of SIPS is still limited to CPD similarities.

To further improve the approximation capability, inner product difference similarity (IPDS) has also been proposed by taking the difference between two IPS models [Okuno et al., 2019, See Supplement E]. Any general similarities including indefinite kernels can be expressed as the difference between two PD similarities [Ong et al., 2004], thus they can be approximated by IPDS arbitrarily well. However, only the concept of IPDS has been shown in the literature [Okuno et al., 2019] without any experiments.

In this paper, we first examine IPDS on a range of applications to investigate its effectiveness and weakness. There are, in fact, several practical concerns in IPDS such as a specification of dimensionalities of the two IPS models. Then, in order to remedy the weakness of IPDS, we propose a new model named weighted inner product similarity (WIPS). The core idea of WIPS is to incorporate element-wise weights to IPS so that it generalizes all the above-explained similarity models. WIPS reduces to IPS when all the weights are +1, and it also reduces to IPDS when they are +1 or -1. The weight values are optimized continuously by allowing positive and negative values, and thus WIPS is free from model selection, except for the choice of dimensionality. Through our extensive experiments, we verify the efficacy of WIPS in real-world applications.

The main contributions of this work are: (i) A new model WIPS is proposed for a universal approximation of general similarities without model selection (see Figure 1). (ii) Experiments of WIPS, as well as IPDS, are conducted for showing their high approximation capabilities and effectiveness on a range of applications. (iii) Our code is publicly available 1 .

2 RelatedWorks

In this section, we overview some existing methods concerned with similarity learning.

Metric learning is a kind of similarity learning where similarity between two data vectors xi, xj is captured by some metric function d(xi, xj) [Bellet et al., 2013; Kulis, 2013]. A vast amount of previous works focused on linear metric learning, where Mahalanobis distance dM(xi, xj) = √(xi -xj)⊤M(xi -xj) is trained with respect to positive-semidefinite (PSD) matrix M. Finding such a PSD matrix M in this context is interpreted as finding a linear projection L that transforms each data vector by L⊤x [Goldberger et al., 2005], since the PSD matrix M can be decomposed as M = LL⊤. Therefore, it can also be seen as learning linear embedding so that similar feature vectors get closer. It is extended to learning non-linear transformation by replacing L with neural networks, which has been known as Siamese architecture [Bromley et al., 1994]. When it comes to just capturing the similarities, especially with bilinear form of x⊤i Mxj, M no longer needs to be PSD [Chechik et al., 2009]; these non-metric learning methods are closely related to our non-PD similarities, but they do not learn embedding representations of data vectors.

Kernel methods represent similarity between two data vectors by a positive-definite (PD) kernel. Although the similarity can be shown as the inner product associated with Reproducing Kernel Hilbert Space (RKHS), explicit embedding representations of data vectors are avoided via the kernel trick. Kernel methods have been extended to conditionally PD (CPD) kernels [Sch¨olkopf, 2001] for representing negative distances, and also to general kernels including indefinite kernels [Ong et al., 2004; Oglic and Gaertner, 2018] for representing a variety of non-PD kernels in real-world situations [Schleif and Tino, 2015]. The general kernels are theoretically expressed as inner products associated with Reproducing Kernel Kr˘ein Space (RKKS), but such representations in infinite dimensions are avoided in practice.

Graph embedding can be interpreted as learning representations of nodes that preserve similarities between nodes defined from their links or neighbourhood structure. The feature vector of a node is computed from its data vector using linear transformation [Yan et al., 2007] or non-linear transformation [Wang et al., 2016], whereas feature vectors are treated as model parameters when data vectors are not observed [Tang et al., 2015]. Word embedding with Skip-gram model [Mikolov et al., 2013] in natural language processing can also be interpreted as graph embedding without data vectors. They are often 2-view graphs, where vector representations of words and those of contexts are parameterized separately. Some graph embedding methods implement such 2-view settings [Tang et al., 2015], and its generalization to a multi-view setting is straightforward [Okuno et al., 2018]. Interestingly, most of these graph embedding models employ the inner product for computing similarity, thus they can be covered by our argument, although we work only on a 1-view case for simplicity. Note that graph convolution networks [Hamilton et al., 2017] compute the feature vector of a node from the data vectors of its neighbour nodes, so they cannot be covered by our simple setting. However, these methods also use the inner product for computing similarity, hence, they may be improved by using our similarity models.

1 https://github.com/kdrl/WIPS

3 Representation Learning for Graph Embedding

Let us consider an undirected graph consisting of n(∈ N) nodes {vi}ni=1 with a weighted adjacency matrix (wij) ∈ Rn×n ≥0 . The symmetric weight wij = wji ≥ 0 is called link weight, that represents the observed strength of association between a node pair (vi, vj) for all 1 ≤ i < j ≤ n. We may also consider a data vector xi ∈ X at vi, that takes a value in a set X ⊂ Rp (p ∈ N). The data vector represents attributes or side-information of the node. If we do not have any such attributes, we use 1-hot vector instead, i.e., xi is ndimensional vector whose i-th entry is 1 and 0 otherwise, for i = 1, . . . , n. Our data consists of {wij}ni,j=1 and {xi}ni=1 .

Following the setting of graph embedding described in [Okuno et al., 2018; Okuno et al., 2019], we consider a feature vector yi ∈ Y at vi, that takes a value in a set Y ⊂ RK for some dimensionality K ∈ N. Feature vectors are computed by a continuous transformation f : X → Y as

For two data vectors x, x′ ∈ X, the strength of association between x and x′ is modeled by a similarity function

where g : Y 2 → R is a symmetric continuous function, e.g., the inner product g(y, y′ ) = 〈y, y′ 〉 = ∑Kk=1 yky′k . We employ a simple random graph model by specifying the conditional expectation of wij given xi and xj as

where ν : R → R is a non-linear function; e.g., ν(x) = σ(x) := (1 + exp(-x))-1 is a sigmoid function when wij ∈ {0, 1} follows Bernoulli distribution, or ν(x) = exp(x) when wij ∈ {0, 1, . . .} follows Poisson distribution.

For learning distributed representations of nodes from the observed data, we consider a parametric model fθ : X → Y with unknown parameter vector θ ∈ Θ. Typically, fθ is a non-linear transformation implemented as a vector valued neural network (NN), or a linear transformation. The similarity function h is now modelled as

where gλ(y, y′ ) has also a parameter vector λ in general. This architecture for similarity learning is called Siamese network [Bromley et al., 1994]. The parameter θ ∈ Θ as well as λ may be estimated by maximizing the log-likelihood function. For the case of Bernoulli distribution (i.e., the binary wij), the objective function is

which is optimized efficiently by mini-batch SGD with negative sampling [Okuno et al., 2018]. Once the optimal parameters ˆ θ and ˆλ are obtained, we compute feature vectors as yi = fˆ θ (xi), i = 1, . . . , n. For inductive tasks with newly observed data vectors xi (i = n + 1, n + 2, . . .), we also compute feature vectors by yi = fˆ θ (xi) unless xi are 1hot vectors, and then we can compute the similarity function gˆλ(yi, yj) for any pair of feature vectors.

4 Existing SimilarityModels and Their Approximation Capabilities

The quality of representation learning relies on the model (1) of similarity function. Although arbitrary similarity functions can be expressed if gλ is a large neural network with many units, our gλ are confined to simple extensions of inner product in this paper. All the models reviewed in this section are very simple and they do not have the parameter λ. You will see very subtle extensions to the ordinary inner product greatly enhance the approximation capability.

4.1 Inner Product Similarity (IPS)

Many of conventional representation learning methods use IPS as its similarity model. IPS is defined by

where 〈y, y′ 〉 = ∑Kk=1 yky′k represents the inner product in Euclidean space RK . Note that, hIPS(x, x′ ; θ) reduces to Mahalanobis inner product x⊤LθL⊤θ x′ [Kung, 2014], by specifying fθ(x) as a linear-transformation L⊤θ x with a matrix Lθ ∈ Rp×K parameterized by θ ∈ Θ.

For describing the approximation capability of IPS, we need the following definition. The similarity function h is also said as a kernel function in our mathematical argument.

Definition 1 (Positive definite kernel). A symmetric function h : X 2 → R is said to be positive-definite (PD) if ∑ni=1 ∑nj=1 cicjh(xi, xj) ≥ 0 for any {xi}ni=1 ⊂ X and {ci}ni=1 ⊂ R. This definition of PD includes positive semidefinite. Note that h is called negative definite when -h is positive definite.

For instance, h(x, x′ ) = g(f(x), f(x′ )) is PD when g(y, y′ ) = 〈y, y′ 〉 (IPS), and g(y, y′ ) = 〈y, y′ 〉/‖y‖2‖y′ ‖2 (cosine similarity).

IPS using a sufficiently large NN has been proved to approximate arbitrary PD similarities [Okuno et al., 2018, Theorem 3.2], in the sense that, for any PD-similarity h∗, hIPS(x, x′ ; ˆ θ) equipped with a NN converges to h∗(x, x′ ) as the number of units in the NN and the dimension K increase. The theorem is proved by combining the universal approximation theorem of NN [Funahashi, 1989; Cybenko, 1989; Yarotsky, 2017; Telgarsky, 2017], and the Mercer's theorem [Minh et al., 2006]. Therefore, IPS, despite its simplicity, covers a very large class of similarities. However, IPS cannot approximate non-PD similarities [Okuno et al., 2019], such as negative Poincar´e distance [Nickel and Kiela, 2017] or negative-squared distance h(x, x′ ) = -‖f (x) - f (x′ )‖22 .

4.2 Shifted Inner Product Similarity (SIPS)

For enhancing the IPS's approximation capability, Okuno et al. [2019] has proposed shifted inner product similarity (SIPS) defined by

where ˜ fθ : X → RK-1 and uθ : X → R are continuous functions parameterized by θ. Thus fθ(x) = (˜ y, z) := ( ˜ fθ(x), uθ(x)) ∈ RK represents the feature vector for x. By introducing the bias terms uθ(x) + uθ(x′ ), SIPS extends the approximation capability of IPS.

For describing the approximation capability of SIPS, we need the following definition.

Definition 2 (Conditionally positive definite kernel). A symmetric function h : X 2 → R is said to be conditionally PD (CPD) if ∑ni=1 ∑nj=1 cicjh(xi, xj) ≥ 0 for any {xi}ni=1 ⊂ X and {ci}ni=1 ⊂ R satisfying ∑ni=1 ci = 0.

CPD includes many examples, such as any of PD similarities, negative squared distance, negative Poincar´e distance used in Poincar´e embedding [Nickel and Kiela, 2017] and some cases of negative Wasserstein distance [Xu et al., 2018].

SIPS using a sufficiently large NN has been proved to approximate arbitrary CPD similarities [Okuno et al., 2018, Theorem 4.1]. Therefore, SIPS covers even larger class of similarities than IPS does. However, there still remain nonCPD similarities [Okuno et al., 2018, Supplement E.3] such as negative Jeffrey's divergence and Epanechnikov kernel.

4.3 Inner Product Difference Similarity (IPDS)

For further enhancing the SIPS's approximation capability, Okuno et al. [2019] has also proposed inner-product difference similarity (IPDS). By taking the difference between two IPSs, we define IPDS by

where f + θ : X → RK-q and f - θ : X → Rq (0 ≤ q ≤ K) are continuous functions parameterized by θ ∈ Θ. Thus fθ(x) = (y+, y-) := (f + θ (x), f - θ (x)) ∈ RK represents the feature vector for x. SIPS with K dimensions is expressed as IPDS with K + 2 dimensions by specifying f +(x) = ( ˜ fθ(x), uθ(x), 1) ∈ RK+1 and f -(x) = uθ(x) - 1 ∈ R. Therefore, the class of similarity functions of IPDS includes that of SIPS. Also note that IPDS with q = 1 and a constraint hIPDS(x, x; θ) = -1 gives the bilinear form in the hyperbolic space, which is used as another representation for Poincar´e embedding [Nickel and Kiela, 2018; Leimeister and Wilson, 2018]. For vectors yi = (y+ i , yi ), the bilinear-form 〈y+ i , y+ j 〉 - 〈yi , yj 〉 is known as an inner product associated with a pseudo-Euclidean space [Greub, 1975], which is also said to be an indefinite inner product space, and such inner products have been used in applications such as pattern recognition [Goldfarb, 1984].

For describing the approximation capability of IPDS, we need the following definition.

Definition 3 (Indefinite kernel). A symmetric function h : X 2 → R is said to be indefinite if neither of h nor -h is positive definite. We only consider h which satisfies the condition

so that h can be decomposed as h = h1 - h2 with two PD kernels h1 and h2 [Ong et al., 2004, Proposition 7].

We call h is general similarity function when h is positive definite, negative definite, or indefinite.

IPDS using a sufficiently large NN (with many units, large K - q and q) has been proved to approximate arbitrary general similarities [Okuno et al., 2018, Theorem E.1], thus IPDS should cover an ultimately large class of similarities.

4.4 Practical Issues of IPDS

Although IPDS can universally approximate any general similarities with its high approximation capability, only the theory of IPDS without any experiments nor applications has been presented in previous research [Okuno et al., 2019]. There are several practical concerns when IPDS is implemented. The optimization of fθ for IPDS can be harder than IPS or SIPS without proper regularization, because the expression of IPDS is redundant; for arbitrary f 0 θ , replacing f ± θ (x) with (f ± θ (x), f 0 θ (x)), respectively, results in exactly the same similarity model but with redundant dimensions. Choice of the two dimensionalities, i.e., K - q and q, should be important. This leads to our development of new similarity model presented in the next section.

5 Proposed SimilarityModel

We have seen several similarity models which can be used as a model of (1) for the representation learning in graph embedding. In particular, IPDS has been mathematically proved to approximate any general similarities, but the choice of the two dimensionalities can be a practical difficulty. In order to improve the optimization of IPDS, we propose a new similarity model by modifying IPDS slightly. Our new model has a tunable parameter vector λ in gλ, whereas all the models reviewed in the previous section do not have the parameter λ. Everything is simple and looks trivial, yet it works very well in practice.

5.1 Weighted Inner Product Similarity (WIPS)

We first introduce the inner product with tunable weights.

Definition 4 (Weighted inner product). For two vectors y = (y1, y2, . . . , yK), y′ = (y′1 , y′2 , . . . , y′K ) ∈ RK , weighted inner product (WIP) equipped with the weight vector λ = (λ1, λ2, . . . , λK) ∈ RK is defined as

The weights {λk}Kk=1 may take both positive and negative values in our setting; thus, WIP is an indefinite inner product [B¨ottcher and Lancaster, 1996].

WIP reduces to the ordinary inner product 〈y, y′ 〉 when λ = 1K := (1, 1, . . . , 1) ∈ RK . WIP also reduces to the indefinite inner product 〈y+ i , y+ j 〉 - 〈yi , yj 〉 when λ = (1, . . . , 1, -1, . . . , -1) = (1K-q, -1q) ∈ RK .

For alleviating the problem to choose an appropriate value of q in IPDS, we specify WIP gλ(y, y′ ) = 〈y, y′ 〉λ in the model (1). We then propose weighted inner product similarity (WIPS) defined by

where fθ : Rp → RK is a non-linear transformation parameterized by θ ∈ Θ, and λ ∈ RK is also a parameter vector to be estimated. The parameter vectors θ and λ are jointly optimized in the objective function (2). WIPS obviously includes IPS, SIPS, and IPDS as special cases by specifying λ and fθ (Table 1). WIPS inherits the universal approximation capability of general similarities from IPDS, but WIPS does not extend IPDS for a larger class of similarity functions; WIPS is expressed as IPDS by redefining fθ so that k-th element is rescaled by √λk for λk > 0 and √-λk for λk < 0. However, the discrete optimization of 0 ≤ q ≤ K in IPDS is mitigated by the continuous optimization of λ ∈ RK in WIPS.

5.2 InterpretingWIPS as aMatrix Decomposition

Let h∗ be a general similarity function that is not limited to PD or CPD similarities. WIPS can be interpreted as the eigendecomposition of the similarity matrix H∗ whose (i, j)-th entry is h∗(xi, xj). Since H∗ is a symmetric real-valued matrix, it can be expressed as

where U = (u1, . . . , un) ∈ Rn×n is the orthogonal matrix of unit eigen-vectors and and Λ = diag(λ1, . . . , λn) is the diagonal matrix of real eigenvalues λk ∈ R. There will be negative λk's when h∗ is a non-PD similarity. Let us reorder the eigenvalues so that |λ1| ≥ |λ2| ≥ · · · ≥ |λn|, and take the first K eigen-vectors as UK = (u1, . . . , uK) ∈ Rn×K and also K eigenvalues as ΛK = diag(λ) with λ = (λ1, . . . , λK). Now the similarity matrix is approximated as

We may define feature vectors yi ∈ RK for xi, i = 1, . . . , n as U ⊤ K = (y1, . . . , yn). This results in

for all 1 ≤ i < j ≤ n, and the accuracy improves in (3) as K approaches n.

The representation learning with WIPS can be interpreted as a relaxed version of the matrix decomposition without any constraints such as the orthogonality of vectors. Instead, we substitute yi = fθ(xi) in (3) and optimize the parameter vectors θ and λ with an efficient algorithm such as SGD. The above interpretation gives an insight into how WIPS deals with general similarities; allowing negative λk in WIPS is essential for non-PD similarities.

6 Experiments

6.1 Preliminary

Datasets. We use the following networks and a text corpus.

• WebKB Hypertext Network 2 has 877 nodes and 1,480 links. Each node represents a hypertext. A link between nodes represents their hyperlink ignoring the direction. Each node has a data vector of 1,703 dimensional bagof-words. Each node also has semantic class label which is one of {Student, Faculty, Staff, Course, Project}, and university label which is one of {Cornell, Texas, Washington, Wisconsin}.
• DBLP Co-authorship Network [Prado et al., 2013] has 41,328 nodes and 210,320 links. Each node represents an author. A link between nodes represents any collaborations. Each node has a 33 dimensional data vector that represents the number of publications in each of 29 conferences and journals, and 4 microscopic topological properties describing the neighborhood of the node.
• WordNet Taxonomy Tree [Nickel and Kiela, 2017] has 37,623 nodes and 312,885 links. Each node represents a word. A link between nodes represents a hyponymyhypernymy relation. Each node has a 300 dimensional data vector prepared from Google's pre-trained word embeddings 3 .
• Text9 Wikipedia Corpus 4 consists of English Wikipedia articles containing about 123M tokens.

Similarity models. We compare WIPS with baseline similarity models IPS, SIPS and IPDS [Okuno et al., 2018; Okuno et al., 2019] in addition to the negative Poincar´e distance [Nickel and Kiela, 2017]. Because most feature vectors obtained by Poincar´e distance are close to the rim of Poincar´e ball, we also consider a natural representation in hyperbolic space by transformation yi → 2yi/(1 - ||y||22 ) for downstream tasks (denoted as Hyperbolic in Results). We focus only on comparing the similarity models, because some experiments [Okuno et al., 2018] showed that even the simplest IPS model with neural networks can outperform many existing feature learning methods, such as DeepWalk [Perozzi et al., 2014] or GraphSAGE [Hamilton et al., 2017].

2 https://linqs.soe.ucsc.edu/data

3 https://code.google.com/archive/p/word2vec

4 Extension of Text8 corpus, http://mattmahoney.net/dc/textdata

NN architecture. For computing feature vectors, we use a 2-hidden layer fully-connected neural network fθ : Rp → RK where each hidden layer consists of 2,000 hidden units with ReLU activation function.

Model training. The neural network models are trained by an Adam optimizer with negative sampling approach [Mikolov et al., 2013; Tang et al., 2015] whose batch size is 64 and the number of negative sample is 5. The initial learning rate is grid searched over {2e-4, 1e-3}. The dimensionality ratio q/K of IPDS is grid searched over {0.01, 0.25, 0.5, 0.75, 0.99}. Instead, λ in WIPS is initialized randomly from the uniform distribution of range (0, 1/K).

Implementations. To make fair "apples-to-apples" comparisons, all similarity models are implemented with PyTorch framework upon the SIPS library 5 . We also made C implementation upon the word2vec program 6 . All our implementations are publicly available at GitHub 7 .

6.2 Evaluation Tasks

To assess both the approximation ability of the proposed similarity model as well as the effectiveness of the learned feature vectors, we conduct the following tasks.

Reconstruction (Task 1). Most settings are the same as those in Okuno et al. [2019]. To evaluate approximation capacity, we embed all nodes and predict all links, i.e., reconstruct the graph structure from the learned feature vectors. The maximum number of iterations for training is set to 100K. ROC-AUC of reconstruction error is evaluated at every 5K iterations and the best score is reported for each model.

Link prediction (Task 2). To evaluate generalization error, we randomly split the nodes into train (64%), validation (16%) and test (20%) sets with their associated links. Models are trained on the sub-graph of train set and evaluated occasionally on validation set in iterations; the best evaluated model is selected. The maximum number of iterations and validation interval are 5K/100 for Hypertext Network, and they are 40K/2K for Co-authorship Network and Taxonomy Tree. Then, the trained models are evaluated by predicting links from unseen nodes of test set and ROC-AUC of the prediction error is computed. This is repeated for 10 times and the average score is reported for each model.

Hypertext classification (Task 3). To see the effectiveness of learned feature vectors, we conduct hypertext classification with inductive setting. First, feature vectors of all nodes are computed by the models trained for Hypertext Network in Task 2, where K is also optimized from {10, 50, 100}. Then, a logistic regression classifier is trained on the feature vectors of train set for predicting class labels. The classification accuracy is measured on test set. This is repeated for 10 times and the average score is reported for each model.

5 https://github.com/kdrl/SIPS

6 https://github.com/tmikolov/word2vec

7 https://github.com/kdrl/WIPS

Word similarity (Task 4). The similarity models are applied to Skip-gram model [Mikolov et al., 2013] to learn word embeddings. To see the quality of the learned word embeddings from Text9 corpus, word-to-word similarity scores induced by the word embeddings are compared with four human annotated similarity scores: SimLex-999 [Hill et al., 2015], YP-130 [Yang and Powers, 2005], WS-Sim and WS-Rel [Agirre et al., 2009]. The quality is evaluated by Spearman's rank correlation. The models are trained with the SGD optimizer used in Mikolov et al. [2013]. We set the number of negative samples to 5 and the number of epochs to 5. The initial learning rate is searched over {0.01, 0.025}. As additional baselines, we use the original Skip-gram (SG) [Mikolov et al., 2013] and Hyperbolic Skipgram (HSG) [Leimeister and Wilson, 2018]. Since SG uses twice as many parameters, we also compare SG with K/2 dimensional word vectors for fair comparisons. To compute similarities with SG, both inner product and cosine similarity (denoted as SG and SG∗ ) are examined. Each model is trained 3 times and the average score is reported.

6.3 Results

Looking at the reconstruction error in Table 2, the approximation capabilities of IPDS and WIPS are very high, followed by SIPS, Poincar´e and IPS as expected from the theory. This tendency is also seen in the visualization of Fig. 2. Looking at the link prediction error in Table 2, the difference of models is less clear for generalization performance, but IPDS and WIPS still outperform the others. Table 3 shows the effectiveness of the feature vectors, where IPDS and WIPS have again the best or almost the best scores. As expected, the hyperbolic representation is much better than Poincar´e ball model (Note: this does not apply to Table 2, because these two representations are in fact the same similarity model). Table 4 shows the quality of word embeddings. The new similarity models SIPS, IPDS and WIPS work well with similar performance to SG∗ (with twice the number of parameters), whereas IPS works poorly for most cases.

As expected, we can see that IPDS and WIPS are very similar in all the results. Although IPDS and WIPS have the same level of approximation capability, WIPS is much easier to train. For example, the total training time for WIPS was much shorter than IPDS in the experiments. In Task 1 with Hypertext network and K = 100, IPDS took about 110 min to achieve 95.12 AUC with the five searching points for tuning the dimensionality ratio. But, WIPS only took about 20 min and achieved 95.12. While WIPS stably optimizes the dimensionality ratio of the two IPS models, IPDS is sensitive to the value of dimensionality ratio. For instance, in Task 2 with Hypertext network and K = 100, we observed that AUC performance of IPDS varies from the worst 64.31 to the best 82.58; WIPS was 82.93.

One of the main reason to use expressive similarity model is to skip the model selection phase, which is often very timeconsuming. However, if the training of the model is difficult, the benefit has no meaning and the practitioner needs to take much time and effort. Through the experiments, we can see that WIPS is useful in that it is not only as expressive as IPDS but also easy to train which is very important in practice.

7 Conclusion

We proposed a new similarity model WIPS by introducing tunable element-wise weights in inner product. Allowing positive and negative weight values, it has been shown theoretically and experimentally that WIPS has the same approximation capability as IPDS, which has been proved to universally approximate general similarities. As future work, we may use WIPS as a building block of larger neural networks, or extend WIPS to tensor such as ∑Kk=1 wkyky′k y′′ k to represent relations of three (or more) feature vectors y, y′ , y′′ . This kind of consideration is obviously not new, but our work gives theoretical and practical insight to neural network architecture.

Acknowledgements

We would like to thank anonymous reviewers for their helpful advice. This work was partially supported by JSPS KAKENHI grant 16H02789 to HS, 17J03623 to AO and 18J15053 to KF.