B Lifting maps

Lifting refers to the process of mapping a featured domain to another featured domain via a well-defined procedure. This section shows how we can lift a given domain to a CC or cell complex. Such lifting is useful as it allows CCNNs to be applied to common topological domains, including graphs and cell/simplicial complexes. This section only scratches the surface, as there remain many lifting constructions to be explored. We refer the reader to (Ferri, Bergomi, and Zu 2018) for examples of lifting graphs to simplicial complexes.

B.1 n-hop CC of a graph

Let G=(V(G),E(G)) be a graph and n2 an integer. The n-hop CC of G, denoted by CCnhop(G), is the CC whose 0-cells, 1-cells, and n-cells are the nodes of G, edges of G, and set nodes in n-hop neighborhoods of the nodes in G, respectively. It is easy to verify that CCnhop(G) is a CC of dimension n. Figure B.1(a) visualizes the 1-hop CC of a graph.

Examples of lifting domains to CCs and cell complexes. (a): The $1$-hop neighborhood of the red node can be considered as a 2-cell that we can augment to the graph. Adding such 2-cells to a graph yields a CC called the 1-hop neighborhood of the graph. (b): A path on a graph of length more than two can be considered as a 2-cell that we can augment to the graph. Adding such 2-cells to a graph yields a CC called a path-based CC of the graph. (c): A loop in a graph (i.e., a closed path with no repeating edges) can be considered as a 2-cell that we can augment to the graph. Adding such 2-cells to a graph yields a CC called a loop-based CC of the graph. (d): For every blue 2-cell of a simplicial complex, we introduce a green 3-cell obtained by considering the 1-coface of the 2-cell. Adding such 3-cells to a simplicial complex yields a CC of dimension three called the coface CC of the simplicial complex.

FIGURE B.1: Examples of lifting domains to CCs and cell complexes. (a): The 1-hop neighborhood of the red node can be considered as a 2-cell that we can augment to the graph. Adding such 2-cells to a graph yields a CC called the 1-hop neighborhood of the graph. (b): A path on a graph of length more than two can be considered as a 2-cell that we can augment to the graph. Adding such 2-cells to a graph yields a CC called a path-based CC of the graph. (c): A loop in a graph (i.e., a closed path with no repeating edges) can be considered as a 2-cell that we can augment to the graph. Adding such 2-cells to a graph yields a CC called a loop-based CC of the graph. (d): For every blue 2-cell of a simplicial complex, we introduce a green 3-cell obtained by considering the 1-coface of the 2-cell. Adding such 3-cells to a simplicial complex yields a CC of dimension three called the coface CC of the simplicial complex.

B.2 Path-based and subgraph-based CC of a graph

Let G=(V(G),E(G)) be a graph. A natural CC structure on G considers paths of G. We define a path-based CC of G, denoted by CCp(G), to be a CC consisting of 0-cells, 1-cells and 2-cells specified as follows. First, X0 and X1 in CCp(G) are the sets of nodes and edges of G, respectively. We now explain how to construct a 2-cell in CCp(G). Let P be a path in G with length larger than or equal to two (i.e., with two or more edges). An element xP in X2 induced by P is defined to be xP=vP{v}. The set X2 in CCp(G) is a non-empty collection of elements xP. It is easy to verify that CCp(G) is a CC with dim(CCp(G))=2. Note that we may replace the path P by a tree/subgraph of graph G and obtain a similar CC structure induced by the tree/subgraph of G. Figure B.1(b) shows an example of a path-based CC of a graph.

B.3 Loop-based CC of a graph

Let G=(V(G),E(G)) be a graph. We associate a CC structure with G that considers loops in G. We define a loop-based CC of G, denoted by CCloop(G), to be a CC consisting of 0-cells, 1-cells and 2-cells specified as follows. First, we set X0 and X1 in CCloop(G) to be the nodes and edges of G, respectively. We now explain how to construct a 2-cell in CCloop(G). A 2-cell in CCloop(G) is a set C={x01,,x0k}X0 such that {x0i,x0i+1}, 1ik1, and {x0k,x01} are the only edges in X1C. The set X2 in CCloop(G) is a nonempty collection of elements C. It is easy to verify that CCloop(G) is a CC with dim(CCloop(G))=2. Note that the sequence (x01,,x0k) defines a loop in G. This loop is called the loop that characterizes the 2-cell C={x01,,x0k}. Similar constructions are suggested in (Aschbacher 1996; Basak 2010; Savoy 2021; T. Mitchell Roddenberry, Schaub, and Hajij 2022). In fact, it is easy to confirm that every 2-dimensional regular cell complex can be constructed in this manner (T. Mitchell Roddenberry, Schaub, and Hajij 2022). Figure B.1(c) shows an example of a loop-based CC of a graph.

B.4 Coface CC of a simplicial complex or of a CC

Here, we describe a method to lift a simplicial complex of dimension two to a CC of dimension three. This method can be easily generalized to other dimensions. For a simplicial complex Y of dimension two, the coface CC of Y, denoted by CCSC(Y), is defined as follows. Y0, Y1, and Y2 in CCSC(Y) are the nodes, the edges, and the triangles in Y, respectively. We now explain how to construct a 3-cell in CCSC(Y). Let x2 be a 2-cell in Y. The 3-cell in CCSC(Y) associated with x2 is the union of all 0-cells in Nco,1(x2)x2. The set Y3 in CCSC(Y) is defined as the set of all 3-cells associated with all 2-cells x2 in Y. It is easy to verify that CCSC(Y) is a CC with dim(CCSC(Y))=3. A similar lifting construction can be defined to augment any CC of dimension n with (n+1)-cells in order to obtain a CC of dimension n+1.

B.5 Augmentation of CCs by higher-rank cells

The lifting methods proposed in Sections B.2, B.3, and B.4 can be described abstractly under a single general lifting construction. Specifically, the essence of all these lifting methods is to augment the underlying CC X with new cells that have a rank of dim(X)+1. Proposition B.1 formalizes the general lifting construction.

Proposition B.1 (Augmenting a CC) Let S be a nonempty set and (S,X,rk) a CC of dimension n defined on S. Consider a set Xn+1P(S) such that if xX and yXn+1 with xy, then x. Further, consider a map \hat{\mbox{rk}}\colon \mathcal{X}\cup \mathcal{X}^{n+1}\to \mathbb{Z}_{\ge 0} that satisfies \hat{\mbox{rk}}(x)= \mbox{rk}(x) for all x\in\mathcal{X} and \hat{\mbox{rk}}(x)=n+1 for all x \in \mathcal{X}^{n+1}. For \mathcal{X}^{n+1} and \hat{\mbox{rk}} satisfying such conditions, (S,\mathcal{X}\cup \mathcal{X}^{n+1},\hat{\mbox{rk}} ) is a CC of dimension n+1.

Proof. The proof follows directly from Definition 4.1.

Given a CC \mathcal{X}, we call a CC of the form (S,\mathcal{X}\cup \mathcal{X}^{n+1},\hat{\mbox{rk}} ), as constructed in Proposition B.1, a highest-rank augmented CC of \mathcal{X}. Note that Proposition B.1 provides a constructive and iterative method to build a CC of arbitrary dimension from a nonempty set S of abstract points.

References

Aschbacher, Michael. 1996. “Combinatorial Cell Complexes.” In Progress in Algebraic Combinatorics, 1–80. Mathematical Society of Japan.
Basak, Tathagata. 2010. “Combinatorial Cell Complexes and Poincaré Duality.” Geometriae Dedicata 147 (1): 357–87.
Ferri, Massimo, Dott Mattia G. Bergomi, and Lorenzo Zu. 2018. “Simplicial Complexes from Graphs Towards Graph Persistence.” arXiv Preprint arXiv:1805.10716.
Roddenberry, T. Mitchell, Michael T. Schaub, and Mustafa Hajij. 2022. “Signal Processing on Cell Complexes.” In IEEE International Conference on Acoustics, Speech and Signal Processing.
Savoy, Maxime. 2021. “Combinatorial Cell Complexes: Duality, Reconstruction and Causal Cobordisms.” PhD thesis, École Polytechnique Fédérale de Lausanne.