Publication

Sublinear Algorithms for Spectral Graph Clustering

Related publications (92)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The Speed Submission to DIHARD II: Contributions & Lessons Learned

Sébastien Marcel, Nicholas Evans

This paper describes the speaker diarization systems developed for the Second DIHARD Speech Diarization Challenge (DIHARD II) by the Speed team. Besides describing the system, which considerably outperformed the challenge baselines, we also focus on the le ...

Idiap2019

Robust and Efficient Data Clustering with Signal Processing on Graphs

Lionel Jérémie Martin

Data is pervasive in today's world and has actually been for quite some time. With the increasing volume of data to process, there is a need for faster and at least as accurate techniques than what we already have. In particular, the last decade recorded t ...

EPFL2018

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Novel Algorithms For Clustering

James Peter Newling

Clustering is a method for discovering structure in data, widely used across many scientific disciplines. The two main clustering problems this dissertation considers are K-means and K-medoids. These are NP-hard problems in the number of samples and cluste ...

EPFL2018

Algorithms For Clustering Problems

Ashkan Norouzi Fard

Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in ...

EPFL2018

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Jian Li, Lingxiao Huang

We study the problem of constructing epsilon-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An epsilon-coreset is a weighted subset S subset of X with weight function w : S -> R->= 0, such that for any k-subset C is an element of ...

IEEE COMPUTER SOC2018

Fast Approximate Spectral Clustering for Dynamic Networks

Pierre Vandergheynst, Lionel Jérémie Martin, Andreas Loukas

Spectral clustering is a widely studied problem, yet its complexity is prohibitive for dynamic graphs of even modest size. We claim that it is possible to get information from past cluster assignments to expedite computation. Our approach builds on a recen ...

2018

Decentralized clustering for node-variant graph filtering with graph diffusion LMS

Ali H. Sayed, Roula Nassif

In this work, we consider the problem of estimating the coefficients of linear shift-invariant FIR graph filters. We assume hybrid node-varying graph filters where the network is decomposed into clusters of nodes and, within each cluster, all nodes have th ...

IEEE2018

New Multi-Keyword Ciphertext Search Method for Sensor Network Cloud Platforms

Jiyong Zhang, Yue Wang, Hongyu Yang

This paper proposed a multi-keyword ciphertext search, based on an improved-quality hierarchical clustering (MCS-IQHC) method. MCS-IQHC is a novel technique, which is tailored to work with encrypted data. It has improved search accuracy and can self-adapt ...

MDPI2018

Graph-based Methods for Visualization and Clustering

Johann Paratte

The amount of data that we produce and consume is larger than it has been at any point in the history of mankind, and it keeps growing exponentially. All this information, gathered in overwhelming volumes, often comes with two problematic characteristics: ...

EPFL2017