Mixed Membership Graph Clustering via Systematic Edge Query

• URL: http://arxiv.org/abs/2011.12988v2
• Date: Mon, 12 Jul 2021 04:07:43 GMT
• Title: Mixed Membership Graph Clustering via Systematic Edge Query
• Authors: Shahana Ibrahim, Xiao Fu
• Abstract summary: 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.
• Score: 22.77704627076251
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Cluster-based Graph Collaborative Filtering [55.929052969825825]
  Graph Convolution Networks (GCNs) have succeeded in learning user and item representations for recommendation systems. Most existing GCN-based methods overlook the multiple interests of users while performing high-order graph convolution. We propose a novel GCN-based recommendation model, termed Cluster-based Graph Collaborative Filtering (ClusterGCF)
  arXiv  Detail & Related papers  (2024-04-16T07:05:16Z)
• CDIMC-net: Cognitive Deep Incomplete Multi-view Clustering Network [53.72046586512026]
  We propose a novel incomplete multi-view clustering network, called Cognitive Deep Incomplete Multi-view Clustering Network (CDIMC-net) It captures the high-level features and local structure of each view by incorporating the view-specific deep encoders and graph embedding strategy into a framework. Based on the human cognition, i.e., learning from easy to hard, it introduces a self-paced strategy to select the most confident samples for model training.
  arXiv  Detail & Related papers  (2024-03-28T15:45:03Z)
• Large Scale Constrained Clustering With Reinforcement Learning [1.3597551064547502]
  Given a network, allocating resources at clusters level, rather than at each node, enhances efficiency in resource allocation and usage. We propose an approach to solve this constrained clustering problem via reinforcement learning. In the results section, we show that our algorithm finds near optimal solutions, even for large scale instances.
  arXiv  Detail & Related papers  (2024-02-15T18:27:18Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation [65.268245109828]
  Online deep clustering refers to the joint use of a feature extraction network and a clustering model to assign cluster labels to each new data point or batch as it is processed. While faster and more versatile than offline methods, online clustering can easily reach the collapsed solution where the encoder maps all inputs to the same point and all are put into a single cluster. We propose a method that does not require data augmentation, and that, differently from existing methods, regularizes the hard assignments.
  arXiv  Detail & Related papers  (2023-03-29T08:23:26Z)
• Distributed Solution of the Inverse Rig Problem in Blendshape Facial Animation [0.0]
  Rig inversion is central in facial animation as it allows for a realistic and appealing performance of avatars. A possible approach towards a faster solution is clustering, which exploits the spacial nature of the face. In this paper, we go a step further, involving cluster coupling to get more confident estimates of the overlapping components.
  arXiv  Detail & Related papers  (2023-03-11T10:34:07Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Weighted Sparse Subspace Representation: A Unified Framework for Subspace Clustering, Constrained Clustering, and Active Learning [0.3553493344868413]
  We first propose a novel spectral-based subspace clustering algorithm that seeks to represent each point as a sparse convex combination of a few nearby points. We then extend the algorithm to constrained clustering and active learning settings. Our motivation for developing such a framework stems from the fact that typically either a small amount of labelled data is available in advance; or it is possible to label some points at a cost.
  arXiv  Detail & Related papers  (2021-06-08T13:39:43Z)
• SMLSOM: The shrinking maximum likelihood self-organizing map [0.0]
  This paper proposes a greedy algorithm that automatically selects a suitable number of clusters based on a probability distribution model framework. Compared with existing methods, our proposed method is computationally efficient and can accurately select the number of clusters.
  arXiv  Detail & Related papers  (2021-04-28T18:50:36Z)
• Overlapping community detection in networks via sparse spectral decomposition [1.0660480034605242]
  We consider the problem of estimating overlapping community memberships in a network, where each node can belong to multiple communities. Our algorithm is based on sparse principal subspace estimation with iterative thresholding. We show that a fixed point of the algorithm corresponds to correct node memberships under a version of the block model.
  arXiv  Detail & Related papers  (2020-09-20T07:31:09Z)
• Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
  We propose a fully learnable clustering framework without requiring a large number of overlapped subgraphs. Our method significantly improves clustering accuracy and thus performance of the recognition models trained on top, yet it is an order of magnitude more efficient than existing supervised methods.
  arXiv  Detail & Related papers  (2020-04-01T13:39:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.