Hypergraph Clustering Based on PageRank

• URL: http://arxiv.org/abs/2006.08302v1
• Date: Mon, 15 Jun 2020 11:50:18 GMT
• Title: Hypergraph Clustering Based on PageRank
• Authors: Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, Yuichi Yoshida
• Abstract summary: A hypergraph is a useful object to model ternary or higher-order relations among entities. We develop two clustering algorithms based on personalized PageRank on hypergraphs.
• Score: 28.304311692306428
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A hypergraph is a useful combinatorial object to model ternary or higher-order relations among entities. Clustering hypergraphs is a fundamental task in network analysis. In this study, we develop two clustering algorithms based on personalized PageRank on hypergraphs. The first one is local in the sense that its goal is to find a tightly connected vertex set with a bounded volume including a specified vertex. The second one is global in the sense that its goal is to find a tightly connected vertex set. For both algorithms, we discuss theoretical guarantees on the conductance of the output vertex set. Also, we experimentally demonstrate that our clustering algorithms outperform existing methods in terms of both the solution quality and running time. To the best of our knowledge, ours are the first practical algorithms for hypergraphs with theoretical guarantees on the conductance of the output set.

Related papers

• Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
  This work focuses on graph local clustering, which has broad applications beyond graphs because of the internal connectivities within various modalities. We extend the non-approximating Andersen-Chung-Lang ("ACL") algorithm beyond discrete graphs and generalize its quadratic optimality to a wider range of graphs. We theoretically prove that, under two mild conditions, both algorithms can identify a quadratically optimal local cluster in terms of conductance with at least 1/2 probability.
  arXiv  Detail & Related papers  (2024-12-04T03:56:14Z)
• Hyperedge Modeling in Hypergraph Neural Networks by using Densest Overlapping Subgraphs [0.0]
  One of the most important problems in graph clustering is to find densest overlapping subgraphs (DOS) In this paper, we propose a solution to the DOS problem via Agglomerativedyion (DOSAGE) algorithm as a novel approach to enhance the process of generating the densest overlapping subgraphs. Experiments on standard benchmarks show that the DOSAGE algorithm significantly outperforms the HGNNs and six other methods on the node classification task.
  arXiv  Detail & Related papers  (2024-09-16T14:56:10Z)
• A classification model based on a population of hypergraphs [0.0]
  This paper introduces a novel hypergraph classification algorithm. Hypergraphs explore multi-way interactions of any order. The algorithm is evaluated on two datasets.
  arXiv  Detail & Related papers  (2024-05-23T21:21:59Z)
• 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)
• A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource [87.7460720701592]
  This paper introduces formulaic definition, evaluation, and development in this field. The taxonomy of deep graph clustering methods is presented based on four different criteria, including graph type, network architecture, learning paradigm, and clustering method. The applications of deep graph clustering methods in six domains, including computer vision, natural language processing, recommendation systems, social network analyses, bioinformatics, and medical science, are presented.
  arXiv  Detail & Related papers  (2022-11-23T11:31:11Z)
• Higher-order Clustering and Pooling for Graph Neural Networks [77.47617360812023]
  Graph Neural Networks achieve state-of-the-art performance on a plethora of graph classification tasks. HoscPool is a clustering-based graph pooling operator that captures higher-order information hierarchically. We evaluate HoscPool on graph classification tasks and its clustering component on graphs with ground-truth community structure.
  arXiv  Detail & Related papers  (2022-09-02T09:17:10Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
  We propose an efficient spectral hypergraph coarsening scheme (HyperSF) for preserving the original spectral (structural) properties of hypergraphs. Our results show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering.
  arXiv  Detail & Related papers  (2021-08-17T22:20:23Z)
• Learning Spatial Context with Graph Neural Network for Multi-Person Pose Grouping [71.59494156155309]
  Bottom-up approaches for image-based multi-person pose estimation consist of two stages: keypoint detection and grouping. In this work, we formulate the grouping task as a graph partitioning problem, where we learn the affinity matrix with a Graph Neural Network (GNN) The learned geometry-based affinity is further fused with appearance-based affinity to achieve robust keypoint association.
  arXiv  Detail & Related papers  (2021-04-06T09:21:14Z)
• 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)
• 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.