Mixed Membership Graph Clustering via Systematic Edge Query

Abstract

This work considers clustering nodes of a largely incomplete graph. Under the problem setting, only a small amount of queries about the edges can be made, but the entire graph is not observable. This problem finds applications in large-scale data clustering using limited annotations, community detection under restricted survey resources, and graph topology inference under hidden/removed node interactions. Prior works tackled this problem from various perspectives, e.g., convex programming-based low-rank matrix completion and active query-based clique finding. Nonetheless, many existing methods are designed for estimating the single-cluster membership of the nodes, but nodes may often have mixed (i.e., multi-cluster) membership in practice. Some query and computational paradigms, e.g., the random query patterns and nuclear norm-based optimization advocated in the convex approaches, may give rise to scalability and implementation challenges. This work aims at learning mixed membership of nodes using queried edges. The proposed method is developed together with a systematic query principle that can be controlled and adjusted by the system designers to accommodate implementation challenges -- e.g., to avoid querying edges that are physically hard to acquire. Our framework also features a lightweight and scalable algorithm with membership learning guarantees. Real-data experiments on crowdclustering and community detection are used to showcase the effectiveness of our method.

References in corpus (21)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Mixed membership stochastic blockmodels
• Consistency of spectral clustering in stochastic block models
• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
• Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• Clustering Partially Observed Graphs via Convex Optimization
• On Identifiability of Nonnegative Matrix Factorization
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• A Tensor Approach to Learning Mixed Membership Community Models
• Finding Dense Clusters via "Low Rank + Sparse" Decomposition
• Clustering with Noisy Queries
• Blind identification of stochastic block models from dynamical observations
• Clustering Via Crowdsourcing
• Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability
• Crowdsourcing via Pairwise Co-occurrences: Identifiability and Algorithms
• Consistent Estimation of Mixed Memberships with Successive Projections
• Clustering from Sparse Pairwise Measurements

Cited by in corpus (1)

• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach