Timezone: »
People belong to multiple communities, words belong to multiple topics, and books cover multiple genres; overlapping clusters are commonplace. Many existing overlapping clustering methods model each person (or word, or book) as a non-negative weighted combination of "exemplars" who belong solely to one community, with some small noise. Geometrically, each person is a point on a cone whose corners are these exemplars. This basic form encompasses the widely used Mixed Membership Stochastic Blockmodel of networks and its degree-corrected variants, as well as topic models such as LDA. We show that a simple one-class SVM yields provably consistent parameter inference for all such models, and scales to large datasets. Experimental results on several simulated and real datasets show our algorithm (called SVM-cone) is both accurate and scalable.
Author Information
Xueyu Mao (University of Texas at Austin)
Purnamrita Sarkar (UT Austin)
Deepayan Chakrabarti (UT Austin)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: Overlapping Clustering Models, and One (class) SVM to Bind Them All »
Thu. Dec 6th 03:45 -- 05:45 PM Room Room 517 AB #114
More from the Same Authors
-
2021 Spotlight: Bootstrapping the Error of Oja's Algorithm »
Robert Lunde · Purnamrita Sarkar · Rachel Ward -
2021 Poster: Bootstrapping the Error of Oja's Algorithm »
Robert Lunde · Purnamrita Sarkar · Rachel Ward -
2018 Poster: Mean Field for the Stochastic Blockmodel: Optimization Landscape and Convergence Issues »
Soumendu Sundar Mukherjee · Purnamrita Sarkar · Y. X. Rachel Wang · Bowei Yan -
2017 : Posters »
Reihaneh Rabbany · Tianxi Li · Jacob Carroll · Yin Cheng Ng · Xueyu Mao · Alexandre Hollocou · Jeric Briones · James Atwood · John Santerre · Natalie Klein · Pranamesh Chakraborty · Zahra Razaee · Chandan Singh · Arun Suggala · Beilun Wang · Andrew R. Lawrence · Aditya Grover · FARSHAD HARIRCHI · radhika arava · Qing Zhou · Takatomi Kubo · Josue Orellana · Govinda Kamath · Vivek Kumar Bagaria -
2017 : Estimating Mixed Memberships with Sharp Eigenvector Deviations »
Xueyu Mao -
2017 Poster: Convergence of Gradient EM on Multi-component Mixture of Gaussians »
Bowei Yan · Mingzhang Yin · Purnamrita Sarkar -
2017 Poster: On clustering network-valued data »
Soumendu Sundar Mukherjee · Purnamrita Sarkar · Lizhen Lin -
2016 Poster: On Robustness of Kernel Clustering »
Bowei Yan · Purnamrita Sarkar -
2015 Poster: The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels »
Purnamrita Sarkar · Deepayan Chakrabarti · peter j bickel