Combinatorial Complexes: Bridging the Gap Between Cell Complexes and Hypergraphs

2018 52nd Asilomar Conference on Signals, Systems, and Computers, pp. 799–803

Abstract

Graph-based signal processing techniques have be-come essential for handling data in non-Euclidean spaces. How-ever, 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 different types of relations, which may have different utility depending on the application con-text. 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. AIdo Guzman-Saenz

   IBM (United States)

   Affiliation as printed

   IBM Corporation,New York,USA

   IBM Corporation, New York, USA

5. ToIga Birdal

   Imperial College London

   Affiliation as printed

   Imperial College London,London,UK

   Imperial College London, London, UK

6. Michael T. Schaub Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Aachen,Germany

   RWTH Aachen University, Aachen, Germany