Graph-based Semi-supervised Local Clustering with Few Labeled Nodes

• URL: http://arxiv.org/abs/2211.11114v2
• Date: Sun, 18 Aug 2024 04:40:32 GMT
• Title: Graph-based Semi-supervised Local Clustering with Few Labeled Nodes
• Authors: Zhaiming Shen, Ming-Jun Lai, Sheng Li,
• Abstract summary: Local clustering aims at extracting a local structure inside a graph without the necessity of knowing the entire graph structure. We propose a new semi-supervised local clustering approach using only few labeled nodes.
• Score: 6.493238575291165
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Local clustering aims at extracting a local structure inside a graph without the necessity of knowing the entire graph structure. As the local structure is usually small in size compared to the entire graph, one can think of it as a compressive sensing problem where the indices of target cluster can be thought as a sparse solution to a linear system. In this paper, we apply this idea based on two pioneering works under the same framework and propose a new semi-supervised local clustering approach using only few labeled nodes. Our approach improves the existing works by making the initial cut to be the entire graph and hence overcomes a major limitation of the existing works, which is the low quality of initial cut. Extensive experimental results on various datasets demonstrate the effectiveness of our approach.

Related papers

• TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization [2.4783546111391215]
  Density-based clustering methods by mode-seeking usually achieve clustering by using local density estimation to mine structural information. We propose a new algorithm (TANGO) to establish local dependencies by exploiting a global-view emphtypicality of points. It achieves final clustering by employing graph-cut on sub-clusters, thus avoiding the challenging selection of cluster centers.
  arXiv  Detail & Related papers  (2024-08-19T15:26:25Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering. Models estimate an initial graph beforehand to apply GCN. Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
  arXiv  Detail & Related papers  (2024-02-25T07:03:37Z)
• Local Graph Clustering with Noisy Labels [8.142265733890918]
  We propose a study of local graph clustering using noisy node labels as a proxy for additional node information. In this setting, nodes receive initial binary labels based on cluster affiliation: 1 if they belong to the target cluster and 0 otherwise. We show that reliable node labels can be obtained with just a few samples from an attributed graph.
  arXiv  Detail & Related papers  (2023-10-12T04:37:15Z)
• 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)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
  We propose a novel unsupervised graph representation model by contrasting cluster assignments, called as GRCCA. It is motivated to make good use of local and global information synthetically through combining clustering algorithms and contrastive learning. GRCCA has strong competitiveness in most tasks.
  arXiv  Detail & Related papers  (2021-12-15T07:28:58Z)
• Self-supervised Graph-level Representation Learning with Local and Global Structure [71.45196938842608]
  We propose a unified framework called Local-instance and Global-semantic Learning (GraphLoG) for self-supervised whole-graph representation learning. Besides preserving the local similarities, GraphLoG introduces the hierarchical prototypes to capture the global semantic clusters. An efficient online expectation-maximization (EM) algorithm is further developed for learning the model.
  arXiv  Detail & Related papers  (2021-06-08T05:25:38Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Incorporating User's Preference into Attributed Graph Clustering [14.082520165369885]
  We propose two quality measures for a local cluster: Graph Unimodality (GU) and Attribute Unimodality (AU) The local cluster detected by LOCLU concentrates on the region of interest, provides efficient information flow in the graph and exhibits a unimodal data distribution in the subspace of the designated attributes.
  arXiv  Detail & Related papers  (2020-03-24T19:07:22Z)
• Minimizing Localized Ratio Cut Objectives in Hypergraphs [32.80813008862995]
  We present a framework for local hypergraph clustering based on minimizing localized ratio cut objectives. Our algorithm is strongly-local, meaning that its runtime depends only on the size of the input set, and does not need to explore the entire hypergraph to find good local clusters.
  arXiv  Detail & Related papers  (2020-02-21T17:42:22Z)

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.