A New Relaxation Approach to Normalized Hypergraph Cut
Normalized graph cut (NGC) has become a popular research topic due to its wide applications in a large variety of areas like machine learning and very large scale integration (VLSI) circuit design. Most of traditional NGC methods are based on pairwise relationships (similarities). However, in real-world applications relationships among the vertices (objects) may be more complex than pairwise, which are typically represented as hyperedges in hypergraphs. Thus, normalized hypergraph cut (NHC) has attracted more and more attention. Existing NHC methods cannot achieve satisfactory performance in real applications. In this paper, we propose a novel relaxation approach, which is called relaxed NHC (RNHC), to solve the NHC problem. Our model is defined as an optimization problem on the Stiefel manifold. To solve this problem, we resort to the Cayley transformation to devise a feasible learning algorithm. Experimental results on a set of large hypergraph benchmarks for clustering and partitioning in VLSI domain show that RNHC can outperform the state-of-the-art methods.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Hypergraph $p$-Laplacian: A Differential Geometry View
The graph Laplacian plays key roles in information processing of relational data, and has analogies with the Laplacian in differential geometry. In this paper, we generalize the analogy between graph Laplacian and differ…
Un-normalized hypergraph p-Laplacian based semi-supervised learning methods
Most network-based machine learning methods assume that the labels of two adjacent samples in the network are likely to be the same. However, assuming the pairwise relationship between samples is not complete. The inform…
Hypergraph Neural Sheaf Diffusion: A Symmetric Simplicial Set Framework for Higher-Order Learning
The absence of intrinsic adjacency relations and orientation systems in hypergraphs creates fundamental challenges for constructing sheaf Laplacians of arbitrary degrees. We resolve these limitations through symmetric si…
Learning Domain-Independent Planning Heuristics with Hypergraph Networks
We present the first approach capable of learning domain-independent planning heuristics entirely from scratch. The heuristics we learn map the hypergraph representation of the delete-relaxation of the planning problem a…
Hypergraph and protein function prediction with gene expression data
Most network-based protein (or gene) function prediction methods are based on the assumption that the labels of two adjacent proteins in the network are likely to be the same. However, assuming the pairwise relationship …
PredictionProtein Function Prediction