Published April 2, 2019
| Submitted
Report
Open
Learning Mixed Membership Community Models in Social Tagging Networks through Tensor Methods
- Creators
- Anandkumar, Anima
- Sedghi, Hanie
Abstract
Community detection in graphs has been extensively studied both in theory and in applications. However, detecting communities in hypergraphs is more challenging. In this paper, we propose a tensor decomposition approach for guaranteed learning of communities in a special class of hypergraphs modeling social tagging systems or folksonomies. A folksonomy is a tripartite 3-uniform hypergraph consisting of (user, tag, resource) hyperedges. We posit a probabilistic mixed membership community model, and prove that the tensor method consistently learns the communities under efficient sample complexity and separation requirements.
Additional Information
A. Anandkumar is supported in part by Microsoft Faculty Fellowship, NSF Career award CCF-1254106, NSF Award CCF-1219234, and ARO YIP Award W911NF-13-1-0084. H. Sedghi is supported by ONR Award N00014-14-1-0665. The authors thank Majid Janzamin for detailed discussion on rank test analysis. The authors thank Rong Ge and Yash Deshpande for extensive initial discussions during the visit of AA to Microsoft Research New England in Summer 2013 regarding the pairwise mixed membership models without the Dirichlet assumption. The authors also acknowledge detailed discussions with Kamalika Chaudhuri regarding analysis of spectral clustering.Attached Files
Submitted - 1503.04567.pdf
Files
1503.04567.pdf
Files
(479.8 kB)
Name | Size | Download all |
---|---|---|
md5:c0a7ac387cfc7a26130a629886d3c28f
|
479.8 kB | Preview Download |
Additional details
- Eprint ID
- 94347
- Resolver ID
- CaltechAUTHORS:20190401-162928669
- Microsoft Faculty Fellowship
- CCF-1254106
- NSF
- CCF-1219234
- NSF
- W911NF-13-1-0084
- Army Research Office (ARO)
- N00014-14-1-0665
- Office of Naval Research (ONR)
- Created
-
2019-04-02Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field