Hypergraphs

Hypergraphs are a generalization of graphs, where the edges can connect any number of nodes (1 or more nodes). There can be directed and undirected edges in a hypergraph. In a directed edge, some of the edges are marked as the head, and the others are the tail. Hypergraphs have been used extensively in NLP for parsing or machine translation with grammars.

• Wikipedia - Hypergraphs
• Gallo et al 1990 - Directed Hypergraphs and Applications

Search ACL Anthology for Hypergraphs.

• Klein & Manning 2001 - Parsing and Hypergraphs
• Huang 2008 - Advanced Dynamic Programming in Semiring and Hypergraph Frameworks
• Li & Khudanpur 2009 - Efficient Extraction of Oracle-best Translations from Hypergraphs
• Lu & Roth 2015 - Joint Mention Extraction and Classification with Mention Hypergraphs
• Bauer & Rambow 2016 - Hyperedge Replacement and Nonprojective Dependency Structures

Neural papers that use hypergraphs.

• Wang & Lu 2018 - Neural Segmental Hypergraphs for Overlapping Mention Recognition EMNLP 2018
• Katiyar & Cardie 2018 - Nested Named Entity Recognition Revisited
• Ding et al 2020 - Be More with Less: Hypergraph Attention Networks for Inductive Text Classification EMNLP 2020
• Lin et al 2020 - Differentiable Open-Ended Commonsense Reasoning NAACL 2021
• From this paper: “Hypergraph convolutional networks (Feng et al., 2019; Yadati et al., 2019) utilize hypergraph structure rather than a general graph to represent the high-order correlation among data entirely, and hypergraph attention (Bai et al., 2019) further enhances the ability of representation learning by using an attention module.”