Hypergraph Random Walks, Laplacians, and Clustering

• URL: http://arxiv.org/abs/2006.16377v2
• Date: Tue, 27 Oct 2020 17:32:14 GMT
• Title: Hypergraph Random Walks, Laplacians, and Clustering
• Authors: Koby Hayashi, Sinan G. Aksoy, Cheong Hee Park, and Haesun Park
• Abstract summary: We propose a flexible framework for clustering hypergraph-structured data based on recently proposed random walks. We show that the proposed methods produce higher-quality clusters and conclude by highlighting avenues for future work.
• Score: 9.488853155989615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a flexible framework for clustering hypergraph-structured data based on recently proposed random walks utilizing edge-dependent vertex weights. When incorporating edge-dependent vertex weights (EDVW), a weight is associated with each vertex-hyperedge pair, yielding a weighted incidence matrix of the hypergraph. Such weightings have been utilized in term-document representations of text data sets. We explain how random walks with EDVW serve to construct different hypergraph Laplacian matrices, and then develop a suite of clustering methods that use these incidence matrices and Laplacians for hypergraph clustering. Using several data sets from real-life applications, we compare the performance of these clustering algorithms experimentally against a variety of existing hypergraph clustering methods. We show that the proposed methods produce higher-quality clusters and conclude by highlighting avenues for future work.

Related papers

• 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)
• Hypergraph Transformer for Semi-Supervised Classification [50.92027313775934]
  We propose a novel hypergraph learning framework, HyperGraph Transformer (HyperGT) HyperGT uses a Transformer-based neural network architecture to effectively consider global correlations among all nodes and hyperedges. It achieves comprehensive hypergraph representation learning by effectively incorporating global interactions while preserving local connectivity patterns.
  arXiv  Detail & Related papers  (2023-12-18T17:50:52Z)
• 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)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  We present an expressive family of parameterized, hypergraph-regularized energy functions. We then demonstrate how minimizers of these energies effectively serve as node embeddings. We draw parallels between the proposed bilevel hypergraph optimization, and existing GNN architectures in common use.
  arXiv  Detail & Related papers  (2023-06-16T04:40:59Z)
• Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering [29.400924845055865]
  We study p-Laplacians and spectral clustering for a recently proposed hypergraph model that incorporates edge-dependent weights (EDVWs) We convert hypergraphs with EDVWs into submodular hypergraphs for which the spectral theory is better developed. Existing concepts and theorems such as p-Laplacians and Cheeger inequalities proposed under the submodular hypergraph setting can be directly extended to hypergraphs with EDVWs.
  arXiv  Detail & Related papers  (2022-08-15T22:29:00Z)
• Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
  We study spectral clustering for nonuniform hypergraphs based on the hypergraph nonbacktracking operator. We propose an alternating algorithm for inference in a hypergraph blockmodel via linearized belief-propagation.
  arXiv  Detail & Related papers  (2022-04-27T01:14:06Z)
• Representing Videos as Discriminative Sub-graphs for Action Recognition [165.54738402505194]
  We introduce a new design of sub-graphs to represent and encode theriminative patterns of each action in the videos. We present MUlti-scale Sub-Earn Ling (MUSLE) framework that novelly builds space-time graphs and clusters into compact sub-graphs on each scale.
  arXiv  Detail & Related papers  (2022-01-11T16:15:25Z)
• Learning Multi-Granular Hypergraphs for Video-Based Person Re-Identification [110.52328716130022]
  Video-based person re-identification (re-ID) is an important research topic in computer vision. We propose a novel graph-based framework, namely Multi-Granular Hypergraph (MGH) to better representational capabilities. 90.0% top-1 accuracy on MARS is achieved using MGH, outperforming the state-of-the-arts schemes.
  arXiv  Detail & Related papers  (2021-04-30T11:20:02Z)
• Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning [18.800058655626696]
  We propose a novel method to co-cluster the vertices and hyperedges of hypergraphs with edge-dependent weights (EDVWs) In our method, we leverage random walks with EDVWs to construct a hypergraph Laplacian and use its spectral properties to embed vertices and hyperedges in a common space. We then cluster these embeddings to obtain our proposed co-clustering method, of particular relevance in applications requiring the simultaneous clustering of data entities and features.
  arXiv  Detail & Related papers  (2021-02-19T21:47:39Z)
• Generative hypergraph clustering: from blockmodels to modularity [26.99290024958576]
  We propose an expressive generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. We show that hypergraph Louvain is highly scalable, including as an example an experiment on a synthetic hypergraph of one million nodes. We use our model to analyze different patterns of higher-order structure in school contact networks, U.S. congressional bill cosponsorship, U.S. congressional committees, product categories in co-purchasing behavior, and hotel locations.
  arXiv  Detail & Related papers  (2021-01-24T00:25:22Z)
• Conjoined Dirichlet Process [63.89763375457853]
  We develop a novel, non-parametric probabilistic biclustering method based on Dirichlet processes to identify biclusters with strong co-occurrence in both rows and columns. We apply our method to two different applications, text mining and gene expression analysis, and demonstrate that our method improves bicluster extraction in many settings compared to existing approaches.
  arXiv  Detail & Related papers  (2020-02-08T19:41:23Z)

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.