The principal components analysis of a graph, and its relationships to spectral clustering
(2004) Machine Learning: ECML 2004, 15th European Conference on Machine Learning
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- (en) This work presents a novel procedure for computing (1) distances between nodes of a weighted, undirected, graph, called the Euclidean Commute Time Distance (ECTD), and (2) a subspace projection of the nodes of the graph that preserves as much variance as possible, in terms of the ECTD – a PCA of the graph. It is based on a Markov-chain model of random walk through the graph. The model assigns transition probabilities to the links between nodes, so that a random walker can jump from node to node. A quantity, called the average commute time, computes the average time taken by a random walker for reaching node j when starting from node i, and coming back to node i. The square root of this quantity, the ECTD, is a distance measure between any two nodes, and can be computed from the pseudoinverse of the Laplacian matrix of the graph, which is a kernel. We finally define the PCA of a graph as the subspace projection that preserves as much variance as possible, in terms of the ECTD.
- Affiliations
Louvain School of Management Operations and Information
Citations
Saerens, M., Fouss, F., Yen, L., & Dupont, P. (2004). The principal components analysis of a graph, and its relationships to spectral clustering. Lecture Notes in Computer Science, 3201, 371-383. https://hdl.handle.net/2078.5/26066 (Original work published 2004)