NDLI: Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

Please wait, while we are loading the content...

Can Almost Everybody be Almost Happy?

Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry

Local Algorithms for Block Models with Side Information

Strategic Classification

Obfuscating Conjunctions under Entropic Ring LWE

Timeability of Extensive-Form Games

Rational Proofs with Multiple Provers

Coordination Complexity: Small Information Coordinating Large Populations

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

How To Bootstrap Anonymous Communication

Information Complexity Density and Simulation of Protocols

Mechanisms With Costly Knowledge

On Hardness of Approximating the Parameterized Clique Problem

Distribution Design

A PAC Approach to Application-Specific Algorithm Selection

Secure Multiparty Computation with General Interaction Patterns

Auction Revenue in the General Spiteful-Utility Model

Lower Bounds: From Circuits to QBF Proof Systems

On a Natural Dynamics for Linear Programming

On Sketching Quadratic Forms

Time-Lock Puzzles from Randomized Encodings

Satisfiability on Mixed Instances

On the Computational Complexity of Optimal Simple Mechanisms

The Complexity of DNF of Parities

Sampling Correctors

An Axiomatic Approach to Community Detection

Fully Succinct Garbled RAM

How to Incentivize Data-Driven Collaboration Among Competing Parties

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

On the Space Complexity of Linear Programming with Preprocessing

Energy-Efficient Algorithms

Is There an Oblivious RAM Lower Bound?

On the Computational Complexity of Limit Cycles in Dynamical Systems

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions

On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

Cryptography for Parallel RAM from Indistinguishability Obfuscation

From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology

The Space "Just Above" BQP

Simultaneous Private Learning of Multiple Concepts

Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

Content Provider	ACM Digital Library
Author	Awasthi, Pranjal Sinop, Ali Kemal Krishnaswamy, Ravishankar Charikar, Moses
Abstract	We introduce and study a new notion of graph partitioning, intimately connected to spectral clustering and k-means clustering. Formally, given a graph G on n vertices, we ask to find a graph H that is the union of k cliques on n vertices, such that $L_{G}$ > λ $L_{H}$ where λ is maximized. Here $L_{G}$ and $L_{H}$ are the (normalized) Laplacians of the graphs G and H respectively. Informally, our graph partitioning objective asks for the optimal spectral simplification of a given graph as a disjoint union of k cliques. We justify this objective function in several ways. First and foremost, we show that a commonly used spectral clustering algorithm implicitly optimizes this objective function, up to a factor of O(k). Using this connection, we immediately get an O(k)-approximation algorithm to our new objective function by simply using the spectral clustering algorithm on G. Next, we demonstrate another application of our objective function: we use it as a means to proving that simple spectral clustering algorithms can solve some well-studied graph partitioning problems (such as partitioning into expanders). Additionally, we also show that (a relaxation of) this optimization problem naturally arises as the dual problem to the question of finding the worst-case integrality gap instance for the classical k-means SDP. Finally, owing to these close connection between some classical clustering techniques (such as k-means and spectral clustering), we argue that a more complete understanding of this optimization problem could lead to new algorithmic insights and techniques for the area of graph partitioning.
Starting Page	301
Ending Page	310
Page Count	10
File Format	PDF
ISBN	9781450340571
DOI	10.1145/2840728.2840751
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Graph partitioning K-means Clustering
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Kernel k-means: spectral clustering and normalized cuts

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

A unified view of kernel k-means, spectral clustering and graph cuts (2004)

Color image segmentation using mean shift and improved spectral clustering

Farthest centroids divisive clustering ∗ (2008).

The Global Kernel $k$-Means Algorithm for Clustering in Feature Space

Farthest centroids divisive clustering (2008)

Graph Embedding Method based on Space Syntax and Improved K-Means Clustering (2014)

Weighted spectral clustering for water distribution network partitioning

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

Similar Documents

Kernel k-means: spectral clustering and normalized cuts

Partitioning Well-Clustered Graphs: Spectral Clustering Works!

A unified view of kernel k-means, spectral clustering and graph cuts (2004)

Color image segmentation using mean shift and improved spectral clustering

Farthest centroids divisive clustering ∗ (2008).

The Global Kernel $k$-Means Algorithm for Clustering in Feature Space

Farthest centroids divisive clustering (2008)

Graph Embedding Method based on Space Syntax and Improved K-Means Clustering (2014)

Weighted spectral clustering for water distribution network partitioning

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means