We propose $\textit{weighted inner product similarity}$ (WIPS) for neural
network-based graph embedding. In addition to the parameters of neural
networks, we optimize the weights of the inner product by allowing positive and
negative values. Despite its simplicity, WIPS can approximate arbitrary general
similarities including positive definite, conditionally positive definite, and
indefinite kernels. WIPS is free from similarity model selection, since it can
learn any similarity models such as cosine similarity, negative Poincar\'e
distance and negative Wasserstein distance. Our experiments show that the
proposed method can learn high-quality distributed representations of nodes
from real datasets, leading to an accurate approximation of similarities as
well as high performance in inductive tasks.

本文提出一种基于神经网络的图嵌入方法 —— 加权内积相似性，其能够优化相似度模型，学习任何相似度模型，且在节点表示学习和归纳任务中有高效表现。

加权内积表示学习实现通用相似度近似

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

We consider the representation power of siamese-style similarity functions
used in neural network-based graph embedding. The inner product similarity
(IPS) with feature vectors computed via neural networks is commonly used for
representing the strength of association between two nodes. However, only a
little work has been done on the representation capability of IPS. A very
recent work shed light on the nature of IPS and reveals that IPS has the
capability of approximating any positive definite (PD) similarities. However, a
simple example demonstrates the fundamental limitation of IPS to approximate
non-PD similarities. We then propose a novel model named Shifted IPS (SIPS)
that approximates any Conditionally PD (CPD) similarities arbitrary well. CPD
is a generalization of PD with many examples such as negative Poincar\'e
distance and negative Wasserstein distance, thus SIPS has a potential impact to
significantly improve the applicability of graph embedding without taking great
care in configuring the similarity function. Our numerical experiments
demonstrate the SIPS's superiority over IPS. In theory, we further extend SIPS
beyond CPD by considering the inner product in Minkowski space so that it
approximates more general similarities.

本文提出了一种名为 SIPS 的新模型，通过在 Minkowski 空间内考虑内积，SIPS 能够很好地逼近各种条件正定的相似度，从而从理论上得出 SIPS 优于 IPS 的结论。

关于神经网络图嵌入的表示能力及其拓展

On representation power of neural network-based graph embedding and  beyond

We consider the problem of designing locality sensitive hashes (LSH) for
inner product similarity, and of the power of asymmetric hashes in this
context. Shrivastava and Li argue that there is no symmetric LSH for the
problem and propose an asymmetric LSH based on different mappings for query and
database points. However, we show there does exist a simple symmetric LSH that
enjoys stronger guarantees and better empirical performance than the asymmetric
LSH they suggest. We also show a variant of the settings where asymmetry is
in-fact needed, but there a different asymmetric LSH is required.

研究局部敏感哈希的设计问题中对内积相似度问题的对称和非对称哈希的功效及提供了性能更好的对称 LSH 解决方案和非对称 LSH 的变体的需求场景。

对称和非对称 LSH 用于内积搜索

On Symmetric and Asymmetric LSHs for Inner Product Search

This paper addresses the nearest neighbor search problem under inner product
similarity and introduces a compact code-based approach. The idea is to
approximate a vector using the composition of several elements selected from a
source dictionary and to represent this vector by a short code composed of the
indices of the selected elements. The inner product between a query vector and
a database vector is efficiently estimated from the query vector and the short
code of the database vector. We show the superior performance of the proposed
group $M$-selection algorithm that selects $M$ elements from $M$ source
dictionaries for vector approximation in terms of search accuracy and
efficiency for compact codes of the same length via theoretical and empirical
analysis. Experimental results on large-scale datasets ($1M$ and $1B$ SIFT
features, $1M$ linear models and Netflix) demonstrate the superiority of the
proposed approach.

该论文提出了一种基于紧凑代码的近似向量检索算法，通过选择源字典中的若干元素来近似一个向量，并将其表示为由所选元素的索引组成的短代码，从而实现查询向量和数据库向量间的内积相似度检索。通过理论分析和实验结果表明，提出的 $M$-selection 算法在紧凑代码相同长度的情况下，在检索精度和速度方面表现出卓越的性能。