Similar Elements and Metric Labeling on Complete Graphs
We consider a problem that involves finding similar elements in a collection of sets. The problem is motivated by applications in machine learning and pattern recognition. We formulate the similar elements problem as an optimization and give an efficient approximation algorithm that finds a solution within a factor of 2 of the optimal. The similar elements problem is a special case of the metric labeling problem and we also give an efficient 2-approximation algorithm for the metric labeling problem on complete graphs.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine LearningSimilar Papers 제목 키워드 기반
A Methodological Framework for Measuring Spatial Labeling Similarity
Spatial labeling assigns labels to specific spatial locations to characterize their spatial properties and relationships, with broad applications in scientific research and practice. Measuring the similarity between two …
Metric Learning on Temporal Graphs via Few-Shot Examples
Graph metric learning methods aim to learn the distance metric over graphs such that similar graphs are closer and dissimilar graphs are farther apart. This is of critical importance in many graph classification applicat…
Drug DiscoveryGraph ClassificationMetric LearningRepresentation LearningOnline Graph Dictionary Learning
Dictionary learning is a key tool for representation learning, that explains the data as linear combination of few basic elements. Yet, this analysis is not amenable in the context of graph learning, as graphs usually be…
Dictionary LearningGraph ClassificationGraph LearningRepresentation LearningDistance Metric Learning using Graph Convolutional Networks: Application to Functional Brain Networks
Evaluating similarity between graphs is of major importance in several computer vision and pattern recognition problems, where graph representations are often used to model objects or interactions between elements. The c…
Graph SimilarityMetric LearningA Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy
Performing inference in graphs is a common task within several machine learning problems, e.g., image segmentation, community detection, among others. For a given undirected connected graph, we tackle the statistical pro…
Combinatorial OptimizationCommunity DetectionImage SegmentationSemantic Segmentation