Weighted Theta Functions and Embeddings with Applications to Max-Cut, Clustering and Summarization

2015-12-01 · NeurIPS 2015 12 · Fredrik D. Johansson, Ankani Chattoraj, Chiranjib Bhattacharyya, Devdatt Dubhashi

We introduce a unifying generalization of the Lovász theta function, and the associated geometric embedding, for graphs with weights on both nodes and edges. We show how it can be computed exactly by semidefinite programming, and how to approximate it using SVM computations. We show how the theta function can be interpreted as a measure of diversity in graphs and use this idea, and the graph embedding in algorithms for Max-Cut, correlation clustering and document summarization, all of which are well represented as problems on weighted graphs.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringDiversityDocument Summarization Graph Embedding

Methods 이 논문이 사용한 방법론

SVM A Support Vector Machine, or SVM, is a non-parametric supervised learning model. For non-linear classification and regression, they utilise the kernel trick to map inputs…

ANIMC: A Soft Framework for Auto-weighted Noisy and Incomplete Multi-view Clustering

2020-11-20 · Xiang Fang, Yuchong Hu, Pan Zhou, Dapeng Oliver Wu

Multi-view clustering has wide applications in many image processing scenarios. In these scenarios, original image data often contain missing instances and noises, which is ignored by most multi-view clustering methods. …

Clustering Incomplete multi-view clustering regression

Hierarchical Universal Value Function Approximators

2024-10-11 · Rushiv Arora

There have been key advancements to building universal approximators for multi-goal collections of reinforcement learning value functions -- key elements in estimating long-term returns of states in a parameterized manne…

Hierarchical Reinforcement Learning reinforcement-learning Reinforcement Learning

Sampling Matters in Deep Embedding Learning

2017-06-23 · ICCV 2017 10 · Chao-yuan Wu, R. Manmatha, Alexander J. Smola, Philipp Krähenbühl

Deep embeddings answer one simple question: How similar are two images? Learning these embeddings is the bedrock of verification, zero-shot learning, and visual search. The most prominent approaches optimize a deep convo…

Clustering Face Verification Image Retrieval Metric Learning+3

Theta-Resonance: A Single-Step Reinforcement Learning Method for Design Space Exploration

2022-11-03 · Masood S. Mortazavi, Tiancheng Qin, Ning Yan

Given an environment (e.g., a simulator) for evaluating samples in a specified design space and a set of weighted evaluation metrics -- one can use Theta-Resonance, a single-step Markov Decision Process (MDP), to train a…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning (RL)

Computationally efficient sparse clustering

2020-05-21 · Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira

We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretical analysis focuses on the model $X_i = …

Clustering