Proximity Preserving Binary Code using Signed Graph-Cut
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.
Code (0)
등록된 구현이 없습니다.
Tasks
graph partitioningSimilar Papers 제목 키워드 기반
Curvature Regularization to Prevent Distortion in Graph Embedding
Recent research on graph embedding has achieved success in various applications. Most graph embedding methods preserve the proximity in a graph into a manifold in an embedding space. We argue an important but neglected p…
Graph EmbeddingTwitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings
Proximity preserving and structural role-based node embeddings have become a prime workhorse of applied graph mining. Novel node embedding techniques are often tested on a restricted set of benchmark datasets. In this pa…
Graph MiningNode ClassificationDual Graph Embedding for Object-Tag LinkPrediction on the Knowledge Graph
Knowledge graphs (KGs) composed of users, objects, and tags are widely used in web applications ranging from E-commerce, social media sites to news portals. This paper concentrates on an attractive application which aims…
DecoderEntity EmbeddingsGraph EmbeddingKnowledge Graphs+3Graph Auto-Encoder Via Neighborhood Wasserstein Reconstruction
Graph neural networks (GNNs) have drawn significant research attention recently, mostly under the setting of semi-supervised learning. When task-agnostic representations are preferred or supervision is simply unavailable…
DecoderGraph MiningGraph ReconstructionAsymmetric Transitivity Preserving Graph Embedding
Graph embedding algorithms embed a graph into a vector space where the structure and the inherent properties of the graph are preserved. The existing graph embedding methods cannot preserve the asymmetric transitivity we…
Graph EmbeddingLink Prediction