Home / Curated / Algorithms / Power iteration clustering

Power iteration clustering

Algorithms AIMech:PowerIterationClustering DRAFT

Aliases: PIC (power iteration clustering)

A clustering algorithm that uses an early-stopped power iteration of a normalized similarity matrix to embed observations and then applies k-means to their embedding coordinates.

Identity Notes & Concept Scope This is the Lin and Cohen ICML 2010 algorithm. Its qualified PIC alias is distinct from path integral clustering: it truncates a matrix iteration to form coordinates instead of merging clusters by resolvent descriptors. It is not a generic eigensolver or a claim that converging to the dominant eigenvector finds clusters. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 218 preceding native IDs/names/aliases. Word-delimited fixed-string searches of both full checkouts, including ignored and hidden files, returned 15 lines each in existing discovery/review context. Five neighboring native records and five exact AIO nodes with scoped synonyms and outgoing edges were inspected.

Claims & Grounded Evidence

2 Claims

Mechanism #method

For a symmetric nonnegative similarity matrix A with zero diagonal and positive row sums, form D_ii=sum_j A_ij and W=D^−1 A. Starting with a nonnegative nonzero vector v, iterate v_next=Wv/||Wv||_1. Use an intermediate vector before convergence to the constant dominant right eigenvector. Following Algorithm 1 and the released pic.m, monitor d_next=abs(v_next−v) componentwise and stop when max_i abs(d_next_i−d_i) is sufficiently small, subject to an iteration cap. Apply k-means to the scalar coordinates v_i for the requested k clusters. Degree-proportional initialization is described, and multiple random initial vectors may supply several embedding coordinates. Section 2.4 prose instead writes signed differences; the absolute-change convention here is explicitly the pseudocode/implementation convention.

supports Source: Power Iteration Clustering · Locator: Sections 2.1–2.4, PDF pp. 1–4; Algorithm 1 and experimental stopping threshold on p. 4
supports Source: Author MATLAB code accompanying Power Iteration Clustering · Locator: icml2010/pic.m complete function; x_clusterembed_icml2010.m baseconv, maxit and pic case; readme.txt attribution

Limitation #stopping-convention

The stopping convention follows the paper pseudocode and released code, which use componentwise absolute first changes. The surrounding prose uses signed first changes. The released driver also uses a tolerance 100 times the paper’s stated experimental tolerance. These source differences are preserved rather than silently reconciled.

supports Source: Power Iteration Clustering · Locator: Section 2.4 and Algorithm 1, PDF pp. 3–4; p. 4 experimental threshold
supports Source: Author MATLAB code accompanying Power Iteration Clustering · Locator: pic.m and x_clusterembed_icml2010.m, complete files inspected

⚠️ Curated Limitations & Negative Results

The stopping test is a heuristic for a useful intermediate embedding, not a certificate of cluster recovery. A regular graph with degree-proportional initialization starts at a constant vector and can yield no separating coordinates.
Positive row sums are required for the stated row-stochastic normalization. Disconnected graphs, negative eigenmodes and collisions in a one-dimensional embedding limit a blanket spectral or convergence interpretation.
The paper reports experimental tolerance 1e−5/n. The released experiment driver sets baseconv=0.001 and uses baseconv/n, with maxit=5000. These are different settings, not an asserted benchmark reproduction or proof that either setting is wrong.
Choice of similarity, initialization, stopping rule and k-means solution affects the partition. No code was executed, and no runtime, accuracy or global-optimum claim is made.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	Power iteration clustering supplies a procedure for grouping unlabeled observations. The AIO target denotes a clustering task; this algorithm-to-task association does not assert equivalence or subclass membership.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Power Iteration Clustering Frank Lin, William W. Cohen	primary paper full_text	ID: https://icml.cc/Conferences/2010/papers/387.pdf sha256:92619e1e526d…
`author-code`	Author MATLAB code accompanying Power Iteration Clustering Frank Lin	official documentation documentation	ID: https://www.cs.cmu.edu/~frank/code/icml2010-code.zip sha256:95b4275d8ecf…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-11T09:32:03Z

Updated: 2026-10-11T09:35:31Z

Source File: data/curated/PowerIterationClustering.yaml