Methods › General › Clustering › Large-scale spectral clustering

Large-scale spectral clustering

4 papers tagged archive 2025-07-28

Introduced by Divide-and-conquer based Large-Scale Spectral Clustering

archive 2025-07-28 Description, source and code snippet are the archive's method entry.

Spectral Clustering

Spectral clustering aims to partition the data points into k clusters using the spectrum of the graph Laplacians Given a dataset X with N data points, spectral clustering algorithm first constructs similarity matrix W, where wᵢⱼ indicates the similarity between data points xᵢ and xⱼ via a similarity measure metric.

Let L=D-W, where L is called graph Laplacian and D is a diagonal matrix with dᵢᵢ = ∑ⱼ₌₁ⁿ wᵢⱼ. The objective function of spectral clustering can be formulated based on the graph Laplacian as follow: max_U tr(Uᵀ L U), s.t. Uᵀ U=I, where tr(·) denotes the trace norm of a matrix. The rows of matrix U are the low dimensional embedding of the original data points. Generally, spectral clustering computes U as the bottom k eigenvectors of L, and finally applies k-means on U to obtain the clustering results.

Large-scale Spectral Clustering

To capture the relationship between all data points in X, an N×N similarity matrix is needed to be constructed in conventional spectral clustering, which costs O(N²d) time and O(N²) memory and is not feasible for large-scale clustering tasks. Instead of a full similarity matrix, many accelerated spectral clustering methods are using a similarity sub-matrix to represent each data points by the cross-similarity between data points and a set of representative data points (i.e., landmarks) via some similarity measures, as B = Φ(X,R), where R = {r₁,r₂,…, rₚ } (p ≪N) is a set of landmarks with the same dimension to X, Φ(·) indicate a similarity measure metric, and B∈ℝ^(N×p) is the similarity sub-matrix to represent the X ∈ℝ^(N×d) with respect to the R∈ℝ^(p×d).

For large-scale spectral clustering using such similarity matrix, a symmetric similarity matrix W can be designed as W=[[ 0 B ;; Bᵀ 0 ]]. The size of matrix W is (N+p)×(N+p). Taking the advantage of the bipartite structure, some fast eigen-decomposition methods can then be used to obtain the spectral embedding. Finally, k-means is conducted on the embedding to obtain clustering results.

The clustering result is directly related to the quality of B that consists of the similarities between data points and landmarks. Thus, the performance of landmark selection is crucial to the clustering result.

PaperSource

In Syntology name not resolved (unknown_name). The lookup matched no method, paper or venue by this name; that asserts nothing about whether code exists.

Near matches the lookup lists, each a different name: Large-Scale-OR; large-scale dataset; large-scale dataset; Two large-scale datasets; LARGE-SCALE EM BENCHMARK; large-scale binary dataset; Multi-kernel spectral clustering; Higher-Order Spectral Clustering.

Syntology's have check for this name (free, it answers coverage only), read 2026-10-05; ask it again live. A level is the served verification level of that one answer; nothing here is summed across methods.

Papers archive 2025-07-28

archive papers tagged: 4 · with a code link: 1 · where Syntology ran a sample: 0 (0 with a run with no instrument failure, 0 where every run was a failure of Syntology's instrument) Syntology

Show: all tagged papersonly where code ran: none of the 4 tagged papers has a Syntology run on record

Page 1 of 1: papers 1 to 4 of 4, newest first by the archive's date (ties by slug), in archive order.

Repository counts are the archive's code-links table. A Syntology line states what Syntology ran from that paper's harvested code, as “N ran (of which C constructed an object rather than computing a result; K with no instrument failure: H honoured, V violated, P with no contract checked; I where Syntology's instrument failed) · U unverified”; the instrument figure counts failures of Syntology's instrument, not of the code. It is per sample and not a correctness claim. When the archive marks a repository official for the paper, the line starts with that repository's state (the archive's flag, not a verdict on who wrote the code; “community repositories only” when every sample that ran came from a community repository, “official: no sample here; runs from other or unrecorded repositories” when some came from a repository the paper names or has in its text, or from none recorded); hover it for the repositories the samples that ran came from.

Tasks archive 2025-07-28

4 tasks the archive attaches to papers tagged with this method, by distinct papers. A task without a page in the catalog is plain text.

TaskPapers
Clustering4
Image/Document Clustering2
Semantic Segmentation2
Incremental Learning1

Usage over time archive 2025-07-28

Papers per year tagged with Large-scale spectral clustering: 2018 to 2022, peak 1 1 0 2018: 1 paper 2018 2019: 1 paper 2019 2020: 0 papers 2020 2021: 1 paper 2021 2022: 1 paper 2022
Papers per year the archive tags with this method, by the paper's archive date (4 dated). Bars are counts, not a trend claim.

Components: the archive holds no method-to-method composition, so PwC's Components table cannot be rebuilt; the Papers list carries no Results column for the same reason (the archive does not join its leaderboard rows to method tags).

Categories archive 2025-07-28

Clustering

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections