Finding Bipartite Components in Hypergraphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Hypergraphs are important objects to model ternary or higher-order relations of objects, and have a number of applications in analysing many complex datasets occurring in practice. In this work we study a new heat diffusion process in hypergraphs, and employ this process to design a polynomial-time algorithm that approximately finds bipartite components in a hypergraph. We theoretically prove the performance of our proposed algorithm, and compare it against the previous state-of-the-art through extensive experimental analysis on both synthetic and real-world datasets. We find that our new algorithm consistently and significantly outperforms the previous state-of-the-art across a wide range of hypergraphs.

Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 2022
EditorsM. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, J. Wortman Vaughan
PublisherCurran Associates Inc
Number of pages12
Publication statusPublished - 14 Dec 2021
Event35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online
Duration: 6 Dec 202114 Dec 2021

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258


Conference35th Conference on Neural Information Processing Systems, NeurIPS 2021
CityVirtual, Online


Dive into the research topics of 'Finding Bipartite Components in Hypergraphs'. Together they form a unique fingerprint.

Cite this