Saito, S; Herbster, M; (2023) Multi-class Graph Clustering via Approximated Effective p-Resistance. In: Proceedings of the 40 th International Conference on Machine Learning. (pp. pp. 29697-29733). PMLR 202: Honolulu, Hawaii, USA.

Preview

PDF saito23a.pdf - Published Version Download (1MB) | Preview

Abstract

This paper develops an approximation to the (effective) p-resistance and applies it to multi-class clustering. Spectral methods based on the graph Laplacian and its generalization to the graph p-Laplacian have been a backbone of non-euclidean clustering techniques. The advantage of the p-Laplacian is that the parameter p induces a controllable bias on cluster structure. The drawback of p-Laplacian eigenvector based methods is that the third and higher eigenvectors are difficult to compute. Thus, instead, we are motivated to use the p-resistance induced by the p-Laplacian for clustering. For p-resistance, small p biases towards clusters with high internal connectivity while large p biases towards clusters of small “extent,” that is a preference for smaller shortest-path distances between vertices in the cluster. However, the p-resistance is expensive to compute. We overcome this by developing an approximation to the p-resistance. We prove upper and lower bounds on this approximation and observe that it is exact when the graph is a tree. We also provide theoretical justification for the use of p-resistance for clustering. Finally, we provide experiments comparing our approximated p-resistance clustering to other p-Laplacian based methods.

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item