** This software package is developed for the following paper:
Da Kuang, Chris Ding, Haesun Park,
Symmetric Nonnegative Matrix Factorization for Graph Clustering,
The 12th SIAM International Conference on Data Mining (SDM '12), pp. 106--117.
Please cite this paper if you find this software useful.
** Symmetric NMF (SymNMF) is defined as:
min_H f(H) = ||A - HH'||_F^2 subject to H >= 0
where the input A is a n*n symmetric matrix containing pairwise similarity values,
and the output H is a n*k nonnegative matrix indicating clustering assignment.
SymNMF can be used as a framework for graph clustering. It uses the same similarity
matrix A as in spectral clustering, but imposes different constraint on H.
** All these Matlab functions are documented.
Please find the helper texts at the beginning of each M-file.
To get started, run the script test.m
** A summary of the functions in this software is listed below:
symnmf_newton.m - The core computational routine for SymNMF, accepting a similarity matrix as input
symnmf_cluster.m - A wrapper of symnmf_newton for graph clustering, accepting a data matrix as input
scale_dist3.m - Computes the affinity matrix of a dense graph with Gaussian similarity
scale_dist3_knn.m - Computes the affinity matrix of a sparse graph with Gaussian similarity
inner_product_knn.m - Computes the affinity matrix of a sparse graph with inner product similarity
dist2.m - Computes a matrix of squared Euclidean distance values
graph.data - A simple graph clustering example
test.m - A test script running on the graph.data example
** Basic usage:
To run SymNMF on a similarity matrix: H = symnmf_newton(A, k)
To run SymNMF on a data matrix for graph clustering: idx = symnmf_cluster(X, k)
Please refer to the documentation for more options.
** NOTE:
The documentation (as well as the cited paper) differentiates the term
'affinity matrix' and the term 'similarity matrix'.
An affinity matrix contains the raw edge weights in a graph, whereas
a similarity matrix is formed based on the affinity matrix and is
directly fed into symnmf_newton.
For example, 'scale_dist3', 'scale_dist3_knn', 'inner_product_knn'
routines all compute the affinity matrix; the similarity matrix in
normalized cut is a normalized version of the affinity matrix.