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.
Introduction
Graph clustering (GC) is essential for understanding complex systems, from social networks to biological interactions. However, in the era of Big Data, two major hurdles persist: incompleteness and mixed membership. Real-world graphs are often too large to observe fully (a network with a billion nodes has $\approx 10^{18}$ potential edges), and nodes frequently belong to multiple communities simultaneously—for instance, a researcher might belong to both the "Machine Learning" and "Statistics" communities.
Existing solutions often rely on computationally expensive convex programming, such as nuclear norm minimization, which lacks scalability for massive datasets. Furthermore, many query-based methods assume a "single membership" model, failing to account for overlapping community ties. This paper introduces BeQuec (Block Edge Query-based graph clustering), a lightweight and scalable algorithm designed to recover mixed memberships from systematically queried edge blocks with strong theoretical guarantees.
Methodology
Edge Query Principle (EQP)
Instead of relying on purely random edge sampling, which can be difficult to implement in field surveys or crowdsourcing, BeQuec utilizes a "Systematic Edge Query Principle." This approach involves querying specific blocks of the adjacency matrix to ensure identifiability of the underlying community structure.
This systematic approach is more controllable; for instance, in a social network survey, it is easier to query interactions within specific departments (blocks) than to pick random pairs across an entire institution. The authors argue that if these overlapping blocks satisfy specific rank conditions, the local geometry can be mathematically "glued" into a global map of the network.
The BeQuec Algorithm
The BeQuec framework consists of three primary stages:
- Range Space Estimation: The algorithm performs Singular Value Decomposition (SVD) on small, queried blocks of the graph.
- PairStitch: A novel recursive procedure that "stitches" these local subspaces together to reconstruct the global range space of the node membership matrix.
- Membership Extraction: Once the global range space is identified, a "Successive Projection Algorithm" (SPA)—a greedy Gram-Schmidt procedure—is used to extract the mixed-membership vectors for every node.
Unlike previous methods involving $O(N^2)$ optimization variables, BeQuec relies on SVD and least squares, making it significantly more memory-efficient and scalable for large-scale graphs.
Experimental Evaluation
The authors evaluated BeQuec across synthetic data, crowdclustering tasks (dog breed identification), and large-scale co-authorship networks from the Digital Bibliography & Library Project (DBLP) and the Microsoft Academic Graph (MAG).
Key Results
- Efficiency: In the dog breed crowdclustering task, BeQuec was approximately 1500 times faster than standard convex optimization benchmarks while maintaining comparable accuracy (99.22% vs 99.78%).
- Robustness: BeQuec demonstrated high resilience to human error. When Amazon Mechanical Turk (AMT) annotator error rates were increased to 20%, BeQuec's performance remained stable compared to baselines like GeoNMF.
- Scalability: On the MAG2 dataset (~20,000 nodes), BeQuec achieved high accuracy using only 5.82% of total possible edges.
- Mixed Membership Recovery: In synthetic tests with high community overlap, BeQuec significantly outperformed existing methods like CD-MVSI and CD-BNMF, proving its effectiveness in identifying "non-pure" nodes.
Conclusion
BeQuec offers a scalable and theoretically grounded alternative for mixed membership graph clustering by leveraging systematic block queries and subspace stitching. While current logic requires queried block sizes to be at least the number of clusters ($K$), future work may explore third-order graph statistics (tensors) to further reduce query requirements and handle even sparser data regimes.
Summary updated