Chapter 2 Motivation
Combinatorial complex neural networks (CCNNs), as presented in this work, generalize graph neural networks (GNNs) and their higher-order analogues via topological constructions. In this section, we provide the motivation for the use of topological constructions in machine learning, and specifically in deep learning from three angles. First, data modeling: how topological abstraction can help us to reason and compute with various data types supported on topological spaces. Second, utility: how accounting for topology improves performance. Third, unification: how topology can be used to synthesize and abstract disparate concepts.
2.1 Modeling and learning from data on topological spaces
In the context of machine learning, the domain on which the data is supported is typically a (linear) vector space. This underlying vector space facilitates many computations and is often implicitly assumed. However, as has been recognized within geometric deep learning, it is often essential to consider data supported on different domains. Indeed, explicitly considering and modeling the domain on which the data is supported can be crucial for various reasons.
First, different domains can have distinct characteristics and properties that require different types of deep learning models to effectively process and analyze the data. For example, a graph domain may require a graph convolutional network (Kipf and Welling 2016) to account for the non-Euclidean structure, while a point cloud domain may require a PointNet-like architecture (Qi et al. 2017; Zaheer et al. 2017) to handle unordered sets of points.
Second, the specific data within each domain can vary widely in terms of size, complexity and noise. By understanding specific data properties within a given domain, researchers can develop models that are tailored to those particular properties. For example, a model designed for point clouds with high levels of noise may incorporate techniques such as outlier removal or local feature aggregation.
Third, accurately distinguishing between domain and data is important for developing models that generalize well to new, unseen data. By identifying the underlying structure of the domain, researchers can develop models that are robust to variations in the data while still being able to capture relevant geometric features. To summarize, by considering both the domain and data together, researchers can develop models that are better suited to handle the specific challenges and complexities of different geometric learning tasks.
Different perspectives on data: domains and relations. When referring to topological data or topological data analysis in the literature, there are different views on what the actual data consists of and what it is supposed to model. Here, we follow (Bick et al. 2021) and distinguish between different types of data and goals of our learning procedures, even though the distinction between these different types of data can sometimes be more blurry than what is presented here.
Relational data. Relational data describes the relations between different entities or objects. This fundamental concept can manifest in various ways, such as connections between users in social networks, where friend relationships or follower-ship serve as examples of such relations. Traditionally, these relations are understood through graphs, with vertices and edges representing entities and their pairwise connections, respectively. Stated differently, the edges within the graph are considered to be units of measurement; i.e., every piece of relational data involves two vertices.
However, many real-world phenomena naturally involve complex, multi-party interactions, where more than two entities interact with each other in intricate ways. For instance, groups of individuals within a society, sets of co-authors, and genes or proteins that interact with each other are all examples of such higher-order relations. Such dependencies, which go beyond pairwise interactions, can be modeled by higher-order relations and aptly abstracted as hypergraphs, cell complexes, or CCs. Clearly, topological ideas can play an important role for understanding this data, and crucially enable us to move from graphs modeling pairwise relations to richer representations.
Data as an instance of a domain. A related conceptualization of what our observed data is supposed to represent is adopted in TDA. Namely, all of observed data is supposed to correspond to a noisy instance of a topological object itself; i.e., we aim to learn the `topological shape’ of the data. Note that in this context, we typically do not directly observe relational data, but instead we construct relations from observed data, which we then use to classify the observed dataset. Persistent homology performed on point cloud data is a mainstream example for this viewpoint.
Data supported on a topological domain. Topological ideas also play an important role when considering data that is defined on top of a domain such as a graph. This could be particular dynamics, such as epidemic spreading, or it could be any type of other data or signals supported on the vertices (cases of edge-signals on a graph are not considered often, though exceptions exist (Schaub and Segarra 2018; Schaub et al. 2021)). In the language of graph signal processing, a variety of functions or signals can be defined on a graph domain, and these are said to be supported by the domain. Crucially, the graph itself can be arbitrarily complex but is typically considered to be fixed; the observed data is not relational, but supported on the vertices of a graph.
Moving beyond graphs, more general topological constructions, such as CCs, can support data not just on vertices and edges, but also on other `higher-order’ entities, as demonstrated in Figure 2.1(a-b). For example, vector fields defined on meshes in computer graphics are often data supported on edges and faces, and can be conveniently modeled as data supported on a higher-order domain (Goes, Desbrun, and Tong 2016). Similarly, class-labeled data can be provided on the edges and faces of a given mesh; see Figure 2.1(c) for an example. To process such data it is again relevant to take into account the structure of the underlying topological domain.
.]. (c): Class-labeled topological data might naturally be supported on higher-order relations. For instance, mesh segmentation labels for 2-faces are depicted by different colors (blue, green, turquoise, pink, brown) to represent different parts (head, neck, body, legs, tail) of the horse.](figures/two_tori_horse.png)
FIGURE 2.1: Data might be supported naturally on higher-order relations. (a): An edge-based vector field. (b): A face-based vector field. Both vector fields in (a) and (b) are defined on a cell complex torus2. (c): Class-labeled topological data might naturally be supported on higher-order relations. For instance, mesh segmentation labels for 2-faces are depicted by different colors (blue, green, turquoise, pink, brown) to represent different parts (head, neck, body, legs, tail) of the horse.
Modeling and processing data beyond graphs: illustrative examples. Graphs are well-suited for modeling systems that exhibit pairwise interactions. For instance, particle-based fluid simulations can be effectively represented using graphs as shown in Figure 2.2(a), with message passing used to update the physical state of fluid molecules. In this approach, each molecule is represented as a vertex containing its physical state, and the edges connecting them are utilized to calculate their interactions (Sanchez-Gonzalez et al. 2020; Shlomi, Battaglia, and Vlimant 2020).
![Examples of processing data supported on graphs or on higher-order networks. (a): Graphs can be used to model particle interactions in fluid dynamics. Vertices represent particles, whereas particle-to-particle interactions are modeled via message passing among vertices [@sanchez2020learning; @shlomi2020graph]. (b): When modeling springs and self-collision, it is natural to work with edges rather than vertices. This is because the behavior of the cloth is determined by the tension and compression forces acting along the edges, and not only by the position of individual particles. To model the interactions among multiple edges, polygonal faces can be used to represent the local geometry of the cloth. The polygonal faces provide a way to compute higher-order message passing among the edges.](figures/cloth.png)
FIGURE 2.2: Examples of processing data supported on graphs or on higher-order networks. (a): Graphs can be used to model particle interactions in fluid dynamics. Vertices represent particles, whereas particle-to-particle interactions are modeled via message passing among vertices (Sanchez-Gonzalez et al. 2020; Shlomi, Battaglia, and Vlimant 2020). (b): When modeling springs and self-collision, it is natural to work with edges rather than vertices. This is because the behavior of the cloth is determined by the tension and compression forces acting along the edges, and not only by the position of individual particles. To model the interactions among multiple edges, polygonal faces can be used to represent the local geometry of the cloth. The polygonal faces provide a way to compute higher-order message passing among the edges.
Graphs may not be adequate for modeling more complex systems such as cloth simulation, where state variables are associated with relations like edges or triangular faces rather than vertices. In such cases, higher-order message passing is required to compute and update physical states, as depicted in Figure 2.2(b). A similar challenge arises in natural language processing, where language exhibits multiple layers of syntax, semantics and context. Although GNNs may capture basic syntactic and semantic relations between words, more complex relations such as negation, irony or sarcasm may be difficult to represent (Girault, Narayanan, and Ortega 2017). Including higher-order and hierarchical relations can provide a better model for these relations, and can enable a more nuanced and accurate understanding of language.
2.2 The utility of topology
In addition to providing a versatile framework for modeling complex systems, TDL models have broad utility: they can induce meaningful inductive biases for learning, facilitate efficient message propagation over longer ranges in the underlying domain, enhance the expressive power of existing graph-based models, and have the potential to unveil crucial characteristics of deep networks themselves, as described next.
Building hierarchical representations of data. While leveraging higher-order information is important for learning representations, it is also crucial to preserve the complex higher-order relations between entities for achieving powerful and versatile representations. For instance, humans can form abstractions and analogies by building relations among relations hierarchically. However, graph-based models, which are commonly used for building relational reasoning among various entities (Adam Santoro et al. 2017; S.-X. Zhang et al. 2020; Yunpeng Chen et al. 2019; Schlichtkrull et al. 2018), are limited in their ability to build higher-order relations among these entities.
The need for hierarchical relational reasoning (C. Xu et al. 2022) demands methods that can capture deeper abstract relations among relations, beyond modeling relations between raw entities. Higher-order network models provide a promising solution for addressing the challenge of higher-order relational reasoning, as depicted in Figure 2.3.
![An illustration of representing hierarchical data via higher-order networks. Black arrows indicate graph augmentation by higher-order relations, whereas orange arrows indicate coarsened graph extraction. (a): A graph encodes binary relations (pink edges) among abstract entities (yellow vertices). (b): Higher-order relations, represented by blue cells, can be thought as relations among vertices or edges of the original graph. (c): Extraction of a coarsened version of the original graph. In the coarsened graph, vertices represent the higher-order relations (blue cells) of the original graph, and edges represent the intersections of these blue cells. (d-e): The same process repeats to obtain a more coarsened version of the original graph. The entire process corresponds to hierarchical higher-order relations, that is relations among relations, which extract meaning and content (including the `shape of data'), a common task in topological data analysis [@carlsson2009topology; @dey22].](figures/hs.png)
FIGURE 2.3: An illustration of representing hierarchical data via higher-order networks. Black arrows indicate graph augmentation by higher-order relations, whereas orange arrows indicate coarsened graph extraction. (a): A graph encodes binary relations (pink edges) among abstract entities (yellow vertices). (b): Higher-order relations, represented by blue cells, can be thought as relations among vertices or edges of the original graph. (c): Extraction of a coarsened version of the original graph. In the coarsened graph, vertices represent the higher-order relations (blue cells) of the original graph, and edges represent the intersections of these blue cells. (d-e): The same process repeats to obtain a more coarsened version of the original graph. The entire process corresponds to hierarchical higher-order relations, that is relations among relations, which extract meaning and content (including the `shape of data’), a common task in topological data analysis (G. Carlsson 2009; Dey and Wang 2022a).
Improving performance through inductive bias. A topological deep learning model can be leveraged to enhance the predictive performance on graph-based learning tasks by providing a well-defined procedure to lift a graph to a given higher-order network. The incorporation of multi-vertex relations via this approach can be viewed as an inductive bias, and is utilized to improve predictive performance. Inductive bias allows a learning algorithm to prioritize one solution over another, based on factors beyond the observed data (T. M. Mitchell 1980). Figure 2.4 illustrates two forms of augmentation on graphs using higher-order cells.
![The graph in the middle can be augmented with higher-order relations to improve a learning task. In (a), cells have been added to the missing faces; a similar inductive bias has been considered in [@bodnar2021weisfeiler] to improve classification on molecular data. In (b), one-hop neighborhoods have been added to some of the vertices in the graph; [@feng2019hypergraph] use such an inductive bias, based on lifting a graph to its corresponding one-hop neighborhood hypergraph, to improve performance on vertex-based tasks.](figures/inductive_bias.png)
FIGURE 2.4: The graph in the middle can be augmented with higher-order relations to improve a learning task. In (a), cells have been added to the missing faces; a similar inductive bias has been considered in (Bodnar et al. 2021) to improve classification on molecular data. In (b), one-hop neighborhoods have been added to some of the vertices in the graph; (Feng et al. 2019) use such an inductive bias, based on lifting a graph to its corresponding one-hop neighborhood hypergraph, to improve performance on vertex-based tasks.
Construction of efficient graph-based message passing over long-range. The hierarchical structure of TDL networks facilitates the construction of long-range interactions in an efficient manner. By leveraging such structures, signals defined on the vertices of a domain can propagate efficiently distant dependencies among vertices connected by long edge paths. Figure 2.5 illustrates the process of lifting a signal defined on graph vertices by augmenting the graph with additional topological relations and unpooling the signal back to the vertices. (Hajij, Ramamurthy, et al. 2022) employ such pooling and unpooling operations to construct models capable of capturing distant dependencies, leading to more effective and adaptive learning of both the local and global structure of the underlying domain. For related work on graph-based pooling, we refer the reader to (Su, Hu, and Li 2021; Itoh, Kubo, and Ikeda 2022).
![Illustration of message-passing among binary or higher-order cells. (a): Using a graph-based message-passing scheme, some information that starts at vertex $x$ needs to travel a long distance, that is a long edge path, before reaching vertex $y$. (b): Using a higher-order cell structure, indicated by the the blue cell, the signal can be lifted from the vertices to a higher-order cell and thus propagates back and forth between vertices $x$ and $y$ in fewer steps. This shortcut allows to share information efficiently, in fewer computational steps, among all vertices that belong to the blue cell [@hajij2022high].](figures/factors_thru.png)
FIGURE 2.5: Illustration of message-passing among binary or higher-order cells. (a): Using a graph-based message-passing scheme, some information that starts at vertex \(x\) needs to travel a long distance, that is a long edge path, before reaching vertex \(y\). (b): Using a higher-order cell structure, indicated by the the blue cell, the signal can be lifted from the vertices to a higher-order cell and thus propagates back and forth between vertices \(x\) and \(y\) in fewer steps. This shortcut allows to share information efficiently, in fewer computational steps, among all vertices that belong to the blue cell (Hajij, Ramamurthy, et al. 2022).
Improved expressive power. TDL can capture intricate and subtle dependencies that elude traditional graph-based models. By allowing richer higher-order interactions, higher-order networks can have improved expressive power and lead to superior performance in numerous tasks (Morris et al. 2019; Bodnar et al. 2021).
2.3 A unifying perspective on deep learning and structured computations
Topology provides a framework to generalize numerous discrete domains that are typically encountered in scientific computations. Examples of these domains include graphs, simplicial complexes, and cell complexes; see Figure 2.6. Computational models supported on such domains can be seen as a generalization of various deep learning architectures; i.e., can provide a unifying framework to compare and design TDL architectures. Further, understanding the connections between different types of TDL via a unifying theory can provide valuable insights into the underlying structure and behavior of complex systems, where higher-order relations naturally occur (Hansen and Ghrist 2019; Hajij, Istvan, and Zamzmi 2020; Bick et al. 2021; Majhi, Perc, and Ghosh 2022).
FIGURE 2.6: This work introduces combinatorial complexes, which are higher-order networks that generalize most discrete domains typically encountered in scientific computing, including (a) sequences and images, (b) graphs, (c) 3D shapes and simplicial complexes, (d) cubical and cellular complexes, (e) discrete manifolds, and (f) hypergraphs.
Understanding why deep networks work. A remarkable aspect of contemporary deep neural networks is their capacity to generalize very well to unseen data, even though they have an enormous number of parameters. This contradicts our previous understanding of statistical learning theory, prompting researchers to seek novel approaches in comprehending the underlying workings of deep neural networks (Neyshabur et al. 2019). Recent studies have revealed that the topology of graphs induced by deep neural networks or their corresponding training trajectories, modeled as Markov chains, exhibit strong correlations with generalization performance (Birdal et al. 2021; Dupuis, Deligiannidis, and Şimşekli 2023). An open question is how far such correlations between topological structure, computational function and generalization properties can be found in learning architectures supported on higher-order domains. We believe that by studying these questions using our novel topological constructs, such as CCs and CCNNs, we can gain deeper insights not only into TDL but also into deep learning more generally.