AI Paper Atlas

Research map / Learning theory and algorithms / Clustering

A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time

Ranran Shen, Pan Peng

NeurIPS 2023 · Learning theory and algorithms › Clustering · approach: Correlation clustering

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
use our dot-product spectral oracle instead of the prior random-walk l2 oracle (average error)clustering oracle · SBM p=0.03misclassification error: 0.4970 -> 0.0003Improved
use our oracle instead of prior oracle at small conductance gapclustering oracle · SBM p=0.025misclassification error: 0.6208 -> 0.0113Improved
use our oracle instead of prior oracle at p=0.035clustering oracle · SBM p=0.035misclassification error: 0.1996 -> 0Improved
use our oracle instead of prior oracle at p=0.05clustering oracle · SBM p=0.05misclassification error: 0.0168 -> 0Improved
use our oracle vs prior oracle at large gap p=0.06 and 0.07clustering oracle · SBM p=0.06, 0.07misclassification error: 0.0030 -> 0 and 0.0003 -> 0Improved
lower p to 0.02 (smaller conductance gap) for our oracleour oracle · SBM n=3000misclassification error: 0.0113 -> 0.2273Hurt
increase p from 0.025 to 0.035our oracle · SBM n=3000misclassification error: 0.0113 -> 0Improved
prior oracle run-to-run variability (min vs max over 30 runs)prior oracle · SBM p=0.04misclassification error: 0.0173 -> 0.4510Hurt
increase number of WhichCluster queries from 0 to 3200our oracle · SBM n=15000fraction of edges accessed: 0.1277 -> 0.9999Hurt
increase queries from 0 to 200our oracle · SBM n=15000fraction of edges accessed: 0.1277 -> 0.5377Mixed
increase p from 0.02 to 0.06our oracle · SBM n=3000query time (s): 0.3504 -> 0.4874Hurt
increase p from 0.02 to 0.06our oracle · SBM n=3000construct time (s): 11.6533 -> 12.5851No clear effect

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy