A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
Dec 10, 2023
Speakers
Ranran Shen
Speaker · 0 followers
About
We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain k latent clusters, each characterized by a large inner conductance (at least φ) and a small outer conductance (at most ε). Our aim is to preprocess the graph to enable clustering membership queries, with the key requirement that both preprocessing and query answering should be performed in sublinear time, and the resulting partition should be consistent with a k-partition that is close to the ground-truth clustering. Previous oracles have relied on either a poly(k)log n gap between inner and outer conductances or exponential (in k/ε) preprocessing time. Our algorithm relaxes these assumptions, albeit at the cost of a slightly higher misclassification ratio. We also show that our clustering oracle is robust against a few random edge deletions. To validate our theoretical bounds, we conducted experiments on synthetic networks.We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain k latent clusters, each characterized by a large inner conductance (at least φ) and a small outer conductance (at most ε). Our aim is to preprocess the graph to enable clustering membership queries, with the key requirement that both preprocessing and query answering should be performed in sublinear time, and the resulting partition should be consiste…
Organizer
NeurIPS 2023
Account · 648 followers
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
A Bounded Ability Estimation for Computerized Adaptive Testing
Watch later
Yan Zhuang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
On the Identifiability of Sparse ICA without Assuming Non-Gaussianity
Watch later
Ignavier Ng, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Toolformer: Language Models Can Teach Themselves to Use Tools
Watch later
Timo Schick, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Pre-trained Diffusion is All We Need - A Journey Beyond Training Distribution
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
When Can We Track Significant Preference Shifts in Dueling Bandits?
Watch later
Joe Suk, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
RL-based Stateful Neural Adaptive Sampling and Denoising for Real-Time Path Tracing
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%