Combinatorial Complexes: Bridging the Gap Between Cell Complexes and Hypergraphs

Research Explorer (The University of Manchester)

Abstract

Graph-based signal processing techniques have become essential for handling data in non-Euclidean spaces. However, there is a growing awareness that these graph models might need to be expanded into `higher-order' domains to effectively represent the complex relations found in high-dimensional data. Such higher-order domains are typically modeled either as hypergraphs, or as simplicial, cubical or other cell complexes. In this context, cell complexes are often seen as a subclass of hypergraphs with additional algebraic structure that can be exploited, e.g., to develop a spectral theory. In this article, we promote an alternative perspective. We argue that hypergraphs and cell complexes emphasize \emph{different} types of relations, which may have different utility depending on the application context. Whereas hypergraphs are effective in modeling set-type, multi-body relations between entities, cell complexes provide an effective means to model hierarchical, interior-to-boundary type relations. We discuss the relative advantages of these two choices and elaborate on the previously introduced concept of a combinatorial complex that enables co-existing set-type and hierarchical relations. Finally, we provide a brief numerical experiment to demonstrate that this modelling flexibility can be advantageous in learning tasks.

Authors 6

1. Mustafa Hajij

   University of San Francisco

   Affiliation as printed

   University of San Francisco San Francisco , USA

   University of San Francisco San Francisco, USA

2. Ghada Zamzmi

   University of South Florida

   Affiliation as printed

   University of South Florida Florida , USA

   University of South Florida Florida, USA

3. Theodore Papamarkou

   University of Manchester

   Affiliation as printed

   The University of Manchester Manchester , UK

   The University of Manchester Manchester, UK

4. Aldo Guzmán-Sáenz

   IBM (United States)

   Affiliation as printed

   IBM Corporation New York, USA

5. Tolga Birdal

   Imperial College London

   Affiliation as printed

   Imperial College London London , UK

   Imperial College London London, UK

6. Michael T. Schaub corresponding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Aachen , Germany

   RWTH Aachen University Aachen, Germany