Multi-class Graph Clustering via Approximated Effective p-Resistance
Jul 24, 2023
Sprecher:innen
Shota Saito
Sprecher:in · 0 Follower:innen
Mark Herbster
Sprecher:in · 0 Follower:innen
Über
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.…
Gefällt euch das Format? Vertraut auf SlidesLive, um euer nächstes Event festzuhalten!
Professionelle Aufzeichnung und Livestreaming – weltweit.
Freigeben
Empfohlene Videos
Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind
Interactive Learning in the Era of Large Models
Später ansehen
Reachability-Aware Laplacian Representation in Reinforcement Learning
Später ansehen
Kaixin Wang, …
Communication-Constrained Bandits under Additive Gaussian Noise
Später ansehen
Special Properties of Gradient Descent with Large Learning Rates
Später ansehen
Extending Kernel PCA through Dualization: Sparsity, Robustness and Fast Algorithms
Später ansehen
F. Tonin, …
Leveraging Proxy of Training Data for Test-Time Adaptation
Später ansehen
Juwon Kang, …