Discovering Complex Patterns in High Dimensional Data

Famous paper cited over 7000 times. On second page, ”Since the majority of analyses in spectral graph partitioning apprea to deal with paritioning the graph into exactly two parts, these methods are then typically applied recursively to find $k$ clusters (e.g. [9]). Experimentally it has been observed that using more eigenvectors and directly computing $k$ way partitioning is better (e.g. [5, 1]).

Papers referenced should be viewed to see how recursive partitioning on the second eigenvector has been done and why $k$ way partitioning is seen as a better method.

Famous paper cited over 6000 times. Explains in detail many aspects of the ”best” way to do spectral clustering… Note this paper is written after [ng2002spectral] which has stated that using more eigenvectors is better than bi-partitioning, so it does not mention a recursive version of the algorithm.

More recent paper that derives spectral clustering in different way than previous papers.

This method computes the spectral clustering on a small number of samples and then uses matrix completion to infer the clusters of the remaining points belong to.

Relatively recent paper which uses ”graph signal processing” to filter the graph down prior to running spectral clustering.

Paper cited over 6000 times. Newman points to reasons why traditional spectral clustering may fall short in discovering communities… Normalized minimum cut tends to assume two communities are roughly the same size. Modularity is (up to a multiplicative constant), the number of edgest falling within groups minus the expected number in an equivalent network with edges placed at random.

Paper cited over 7000 times. Very popular algorithm that’s actively being researched on finding communities in extremely large graphs. Non-deterministic, but ”identifying communities in a 118 million nodes network took only 152 minutes”.

Very interesting paper cited over 600 times, discussing the use of sub-sampling to measure stability in clustering.

Paper states, ”It can be combined with any clustering algorithm, but proves to be particularly useful in conjunction with hierarchical clustering algorithms.”

Provides several clustering similarity measures.

Paper should be looked at not just for the clustering similarity measures, but look at Figure 2 which outlines the algorithm to determine stability and how it relates to our graph matching problem.

This paper is cited over 200 times and questions the Ben-Hur et. al. Paper’s approach. It states that instability may be due to the fact that there are competing partitions of a certain size that has nothing to do with the sampling process. Note that if we’re using a partitioning to be fed into graph matching, we want to know that the partition is stable either way.

This paper measures stability using Adjusted Rand Index Similarity.