Combinatorial Complexes: Bridging the Gap Between Cell Complexes and
  Hypergraphs
Mustafa Hajij Ghada Zamzmi Theodore Papamarkou Aldo Guzmán-Sáenz Tolga Birdal Michael T. Schaub
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.