HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering

• URL: http://arxiv.org/abs/2108.07901v1
• Date: Tue, 17 Aug 2021 22:20:23 GMT
• Title: HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
• Authors: Ali Aghdaei, Zhiqiang Zhao, Zhuo Feng
• Abstract summary: 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.
• Score: 9.438207505148947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hypergraphs allow modeling problems with multi-way high-order relationships. However, the computational cost of most existing hypergraph-based algorithms can be heavily dependent upon the input hypergraph sizes. To address the ever-increasing computational challenges, graph coarsening can be potentially applied for preprocessing a given hypergraph by aggressively aggregating its vertices (nodes). However, state-of-the-art hypergraph partitioning (clustering) methods that incorporate heuristic graph coarsening techniques are not optimized for preserving the structural (global) properties of hypergraphs. In this work, we propose an efficient spectral hypergraph coarsening scheme (HyperSF) for well preserving the original spectral (structural) properties of hypergraphs. Our approach leverages a recent strongly-local max-flow-based clustering algorithm for detecting the sets of hypergraph vertices that minimize ratio cut. To further improve the algorithm efficiency, we propose a divide-and-conquer scheme by leveraging spectral clustering of the bipartite graphs corresponding to the original hypergraphs. Our experimental results for a variety of hypergraphs extracted from real-world VLSI design benchmarks show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering as well as runtime efficiency when compared with existing state-of-the-art algorithms.

Related papers

• SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning [4.110108749051657]
  We introduce a multilevel spectral framework, SHyPar, for large-scale hypergraphs by leveraging hyperedge effective resistances and flow-based community detection techniques. A key component of SHyPar is a flow-based local clustering scheme for hypergraph coarsening, which incorporates a max-flow-based algorithm to produce nodes with substantially improved conductance.
  arXiv  Detail & Related papers  (2024-10-09T03:29:47Z)
• 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)
• Hypergraph Isomorphism Computation [20.21325386855039]
  We propose a general hypergraph Weisfieler-Lehman kernel framework and implement two instances, which are Hypergraph Weisfeiler-Lehamn Subtree Kernel and Hypergraph Weisfeiler-Lehamn Hyperedge Kernel. Results on hypergraph classification datasets show significant improvements compared to other typical kernel-based methods.
  arXiv  Detail & Related papers  (2023-07-26T09:39:40Z)
• 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)
• Tensorized Hypergraph Neural Networks [69.65385474777031]
  We propose a novel adjacency-tensor-based textbfTensorized textbfHypergraph textbfNeural textbfNetwork (THNN) THNN is faithful hypergraph modeling framework through high-order outer product feature passing message. Results from experiments on two widely used hypergraph datasets for 3-D visual object classification show the model's promising performance.
  arXiv  Detail & Related papers  (2023-06-05T03:26:06Z)
• 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)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs. In this paper, we show that the proposed framework can achieve state-of-the-art performance. Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-03-31T10:46:47Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Hypergraph Partitioning using Tensor Eigenvalue Decomposition [19.01626581411011]
  We propose a novel approach for the partitioning of k-uniform hypergraphs. Most of the existing methods work by reducing the hypergraph to a graph followed by applying standard graph partitioning algorithms. We overcome this issue by utilizing the tensor-based representation of hypergraphs.
  arXiv  Detail & Related papers  (2020-11-16T01:55:43Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

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.