Hypergraph Learning with Hyperedge Expansion
Abstract
We propose a new formulation called hyperedge expansion (HE) for hypergraph learning. The HE expansion transforms the hypergraph into a directed graph on the hyperedge level. Compared to the existing works (e.g. star expansion or normalized hypergraph cut), the learning results with HE expansion would be less sensitive to the vertex distribution among clusters, especially in the case that cluster sizes are unbalanced. Because of the special structure of the auxiliary directed graph, the linear eigenvalue problem of the Laplacian can be transformed into a quadratic eigenvalue problem, which has some special properties suitable for semi-supervised learning and clustering problems. We show in the experiments that the new algorithms based on the HE expansion achieves statistically significant gains in classification performance and good scalability for the co-occurrence data.
Cite
Text
Pu and Faltings. "Hypergraph Learning with Hyperedge Expansion." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012. doi:10.1007/978-3-642-33460-3_32Markdown
[Pu and Faltings. "Hypergraph Learning with Hyperedge Expansion." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2012.](https://mlanthology.org/ecmlpkdd/2012/pu2012ecmlpkdd-hypergraph/) doi:10.1007/978-3-642-33460-3_32BibTeX
@inproceedings{pu2012ecmlpkdd-hypergraph,
title = {{Hypergraph Learning with Hyperedge Expansion}},
author = {Pu, Li and Faltings, Boi},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2012},
pages = {410-425},
doi = {10.1007/978-3-642-33460-3_32},
url = {https://mlanthology.org/ecmlpkdd/2012/pu2012ecmlpkdd-hypergraph/}
}