Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2023 Jul 21;18(7):e0288457.
doi: 10.1371/journal.pone.0288457. eCollection 2023.

Hypergraph partitioning using tensor eigenvalue decomposition

Deepak Maurya  1 , Balaraman Ravindran  1
Affiliations

Hypergraph partitioning using tensor eigenvalue decomposition

Deepak Maurya et al. PLoS One. .

Abstract

Hypergraphs have gained increasing attention in the machine learning community lately due to their superiority over graphs in capturing super-dyadic interactions among entities. In this work, 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. The reduction step restricts the algorithms to capturing only some weighted pairwise interactions and hence loses essential information about the original hypergraph. We overcome this issue by utilizing tensor-based representation of hypergraphs, which enables us to capture actual super-dyadic interactions. We extend the notion of minimum ratio-cut and normalized-cut from graphs to hypergraphs and show that the relaxed optimization problem can be solved using eigenvalue decomposition of the Laplacian tensor. This novel formulation also enables us to remove a hyperedge completely by using the "hyperedge score" metric proposed by us, unlike the existing reduction approaches. We propose a hypergraph partitioning algorithm inspired from spectral graph theory and also derive a tighter upper bound on the minimum positive eigenvalue of even-order hypergraph Laplacian tensor in terms of its conductance, which is utilized in the partitioning algorithm to approximate the normalized cut. The efficacy of the proposed method is demonstrated numerically on synthetic hypergraphs generated by stochastic block model. We also show improvement for the min-cut solution on 2-uniform hypergraphs (graphs) over the standard spectral partitioning algorithm.

PubMed Disclaimer

Conflict of interest statement

The authors have declared that no competing interests exist.

Figures

Fig 1
Fig 1. Hypergraph: H1.
Fig 2
Fig 2. Hypergraph: H2.
Fig 3
Fig 3. Cockroach graph.
Fig 4
Fig 4. Histogram plot for percentage improvement on ratio-cut value by the proposed method for graphs generated by the ER model for different values of p.
It shows that the proposed algorithm performs better for all the generated graphs.
Fig 5
Fig 5. Histogram plot for percentage improvement on ratio-cut value by the proposed method for graphs generated by the SBM for different values of intra-cluster probability (p) and inter-cluster probability (q).
It confirms that the proposed algorithm performs better for most of the generated graphs as there are very few cases of negative PI.
Fig 6
Fig 6. Histogram plot for percentage improvement on ratio cut value by the proposed method for hypergraphs generated by the SBM for different values of q.
It shows that the proposed algorithm performs significantly better as compared to sign-based partitioning for all generated hypergraphs.
Fig 7
Fig 7. Histogram plot for percentage improvement by the proposed method for normalized cut value on hypergraphs generated by the SBM for different values of q.
It shows that the proposed algorithm performs significantly better as compared to sign-based partitioning for all generated hypergraphs.
See this image and copyright information in PMC

References

    1. Aittokallio T, Schwikowski B. Graph-based methods for analysing networks in cell biology. Briefings in bioinformatics. 2006;7(3):243–255. doi: 10.1093/bib/bbl022 - DOI - PubMed
    1. Bhatt SN, Leighton FT. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences. 1984;28(2):300–343. doi: 10.1016/0022-0000(84)90071-0 - DOI
    1. Veksler O. Star shape prior for graph-cut image segmentation. In: European Conference on Computer Vision. Springer; 2008. p. 454–467.
    1. Gao J, Buldyrev SV, Stanley HE, Havlin S. Networks formed from interdependent networks. Nature physics. 2012;8(1):40. - PubMed
    1. Dhillon IS, Guan Y, Kulis B. Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM; 2004. p. 551–556.