# Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning

@article{Zhu2021CoclusteringVA, title={Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning}, author={Yu Zhu and Boning Li and Santiago Segarra}, journal={ArXiv}, year={2021}, volume={abs/2102.10169} }

We propose a novel method to co-cluster the vertices and hyperedges of hypergraphs with edge-dependent vertex weights (EDVWs). In this hypergraph model, the contribution of every vertex to each of its incident hyperedges is represented through an edge-dependent weight, conferring the model higher expressivity than the classical hypergraph. 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… Expand

#### 2 Citations

Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling

- Computer Science
- ArXiv
- 2021

This work proposes a matrix factorization method based on a loss function that generalizes that of the skip-gram model with negative sampling to arbitrary similarity matrices and can better preserve node pairs associated with higher similarity scores. Expand

Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond

- Computer Science, Physics
- Signal Process.
- 2021

This tutorial paper presents a didactic treatment of the emerging topic of signal processing on higher-order networks using the Hodge Laplacian matrix, a multi-relational operator that leverages the special structure of simplicial complexes and generalizes desirable properties of the LaplACian matrix in graph signal processing. Expand

#### References

SHOWING 1-10 OF 39 REFERENCES

Inhomogeneous Hypergraph Clustering with Applications

- Computer Science, Mathematics
- NIPS
- 2017

It is proved that inhomogenous partitioning produces a quadratic approximation to the optimal solution if the inhomogeneous costs satisfy submodularity constraints and offers significant performance improvements in applications such as structure learning of rankings, subspace segmentation and motif clustering. Expand

Beyond pairwise clustering

- Computer Science
- 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05)
- 2005

A two-step algorithm is proposed for solving the problem of clustering in domains where the affinity relations are not dyadic (pairwise), but rather triadic, tetradic or higher, which is an instance of the hypergraph partitioning problem. Expand

Random Walks on Hypergraphs with Edge-Dependent Vertex Weights

- Computer Science, Mathematics
- ICML
- 2019

This paper uses random walks to develop a spectral theory for hypergraphs with edge-dependent vertex weights, and derives a random walk-based hypergraph Laplacian, and bound the mixing time of random walks on such hyper graphs. Expand

Learning with Hypergraphs: Clustering, Classification, and Embedding

- Computer Science, Mathematics
- NIPS
- 2006

This paper generalizes the powerful methodology of spectral clustering which originally operates on undirected graphs to hypergraphs, and further develop algorithms for hypergraph embedding and transductive classification on the basis of the spectral hypergraph clustering approach. Expand

Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration

- Mathematics
- 2019

To date, social network analysis has been largely focused on pairwise interactions. The study of higher-order interactions, via a hypergraph network, brings in new insights. We study community… Expand

Heterogeneous Hyper-Network Embedding

- Computer Science
- 2018 IEEE International Conference on Data Mining (ICDM)
- 2018

A fully-connected and graph convolutional layers are designed to project different types of nodes into a common low-dimensional space, a tuple-wise similarity function is proposed to preserve the network structure, and a ranking based loss function is used to improve the similarity scores of hyperedges in the embedding space. Expand

Probabilistic graph and hypergraph matching

- Mathematics, Computer Science
- 2008 IEEE Conference on Computer Vision and Pattern Recognition
- 2008

This work formalizes a soft matching criterion that emerges from a probabilistic interpretation of the problem input and output, as opposed to previous methods that treat soft matching as a mere relaxation of the hard matching problem. Expand

A Provable Generalized Tensor Spectral Method for Uniform Hypergraph Partitioning

- Computer Science
- ICML
- 2015

This paper develops a unified approach for partitioning uniform hypergraphs by means of a tensor trace optimization problem involving the affinity tensor, and a number of existing higher-order methods turn out to be special cases of the proposed formulation. Expand

Co-clustering documents and words using bipartite spectral graph partitioning

- Computer Science, Mathematics
- KDD '01
- 2001

A new spectral co-clustering algorithm is used that uses the second left and right singular vectors of an appropriately scaled word-document matrix to yield good bipartitionings and it can be shown that the singular vectors solve a real relaxation to the NP-complete graph bipartitionsing problem. Expand

The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning

- Computer Science, Mathematics
- SIAM J. Sci. Comput.
- 2017

A feasible optimization algorithm to compute the Fiedler vector according to the normalized Laplacian tensor of an even-uniform hypergraph and a novel tensor-based spectral method for partitioning vertices of the hypergraph are developed. Expand