论文标题
使用签名的图形切割来保存二进制代码的接近度
Proximity Preserving Binary Code using Signed Graph-Cut
论文作者
论文摘要
我们引入了一个二进制嵌入式框架，称为“接近保存代码”（PPC），该框架学习数据点之间的相似性和差异，以创建紧凑且具有亲和力的二进制代码。该代码可用于将快速和内存有效的近似应用于最近的邻居搜索。我们的框架是灵活的，可以在数据点之间进行不同的接近定义。与以前的方法基于未签名的图形分区提取二进制代码的方法相反，我们的系统通过结合正面和负面的图，模拟了数据中有吸引力和排斥力的力量。所提出的框架显示为归结为找到签名图的最小切割，这是已知的NP- hard的问题。我们提供有效的近似值，并通过构建位后代码来实现卓越的结果。我们表明，相对于准确性和复杂性，所提出的近似值优于常用的光谱方法。因此，这对于可以翻译成签名的图形切割的许多其他问题很有用。
We introduce a binary embedding framework, called Proximity Preserving Code (PPC), which learns similarity and dissimilarity between data points to create a compact and affinity-preserving binary code. This code can be used to apply fast and memory-efficient approximation to nearest-neighbor searches. Our framework is flexible, enabling different proximity definitions between data points. In contrast to previous methods that extract binary codes based on unsigned graph partitioning, our system models the attractive and repulsive forces in the data by incorporating positive and negative graph weights. The proposed framework is shown to boil down to finding the minimal cut of a signed graph, a problem known to be NP-hard. We offer an efficient approximation and achieve superior results by constructing the code bit after bit. We show that the proposed approximation is superior to the commonly used spectral methods with respect to both accuracy and complexity. Thus, it is useful for many other problems that can be translated into signed graph cut.
