Multi-class Graph Clustering via Approximated Effective p-Resistance
Jul 24, 2023
Speakers
Shota Saito
Řečník · 0 sledujících
Mark Herbster
Řečník · 0 sledujících
About
This paper considers the approximation of the effective p-resistance over a graph and its application to multi-class clustering.The effective p-resistance is known to be a metric over a graph. However, it is computationally expensive to obtain the effective p-resistance, and thus it is practically difficult to use.As a solution, we provide an approximation of the effective p-resistance, which is less computationally expensive. We give a theoretical guarantee of the quality of this approximation. We then propose a multi-class clustering algorithm via approximated effective p-resistance. Furthermore, we develop a theoretical connection between effective p-resistance and semi-supervised learning that justifies using effective p-resistance to multi-class clustering.We experimentally demonstrate that our algorithm outperforms the existing spectral clustering using graph p-Laplacian as well as effective 2-resistance-based methods.This paper considers the approximation of the effective p-resistance over a graph and its application to multi-class clustering.The effective p-resistance is known to be a metric over a graph. However, it is computationally expensive to obtain the effective p-resistance, and thus it is practically difficult to use.As a solution, we provide an approximation of the effective p-resistance, which is less computationally expensive. We give a theoretical guarantee of the quality of this approximation.…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Preference Proxies: Evaluating LLMs in capturing Human Preferences in Human-AI Tasks
Zhlédnout později
Mudit Verma, …
Continual Learning in Linear Classification on Separable Data
Zhlédnout později
Itay Evron, …
Toward Large Kernel Models
Zhlédnout později
Patch-level Routing in Mixture-of-Experts is Provably Sample-efficient for Convolutional Neural Networks
Zhlédnout později
