NDLI: Clustering Based Fast Low-Rank Approximation for Large-Scale Graph

Content Provider	IEEE Xplore Digital Library
Author	Wei Chen Ming Shao Yun Fu
Copyright Year	2011
Abstract	As a fundamental data structure, graph has been widely used in machine learning, data mining, and computer vision. However, graph based analysis with respect to kernel method, spectral clustering and manifold learning can reach time complexity of $O(m^3)$, where $m$ is the data size. In particular, the problem becomes intractable when data is in large-scale. Recently, low-rank matrix approximation draws considerable attentions since it can extract essential parts that are responsible for most actions of the matrix. Nonetheless, the structure information embedded in the massive data is inevitably ignored. In this paper, we argue that vector quantization can better reveal the intrinsic structure of the large-scale data and both intra- and inter-cluster matrices should be taken advantage of to boost the accuracy of low-rank matrix approximation. Considering both inter- and intra-relationships, we can reach a better trade-off on different kinds of graphs. Extensive experiments demonstrate that the proposed framework not only keeps lower time complexity but also performs comparably with the state of the art.
Starting Page	787
Ending Page	792
File Size	434796
Page Count	6
File Format	PDF
ISBN	9781467300056
DOI	10.1109/ICDMW.2011.49
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-12-11
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	large scale Laplace equations Vector quantization Clustering algorithms Approximation algorithms clustering Complexity theory low-rank matrix approximation Approximation methods Kernel
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

Low-Rank Kernel Matrix Factorization for Large-Scale Evolutionary Clustering

Distributed Kernel Matrix Approximation and Implementation Using Message Passing Interface

Multi-level Approximate Spectral Clustering

A randomized heuristic for kernel parameter selection with large-scale multi-class data

Review on spectral methods for clustering

Fast approximated relational and kernel clustering

Fast and accurate low rank approximation of massive graphs

Fast Graph-Based Relaxed Clustering for Large Data Sets Using Minimal Enclosing Ball

A fast approximate kernel k-means clustering method for large data sets

Clustering Based Fast Low-Rank Approximation for Large-Scale Graph

Similar Documents

Low-Rank Kernel Matrix Factorization for Large-Scale Evolutionary Clustering

Distributed Kernel Matrix Approximation and Implementation Using Message Passing Interface

Multi-level Approximate Spectral Clustering

A randomized heuristic for kernel parameter selection with large-scale multi-class data

Review on spectral methods for clustering

Fast approximated relational and kernel clustering

Fast and accurate low rank approximation of massive graphs

Fast Graph-Based Relaxed Clustering for Large Data Sets Using Minimal Enclosing Ball

A fast approximate kernel k-means clustering method for large data sets

Clustering Based Fast Low-Rank Approximation for Large-Scale Graph