{'fraction_non_alphanumeric': 0.041240290962889906, 'fraction_numerical': 0.008691899889039576, 'mean_word_length': 4.611553095814597, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Pooling Strategies for Simplicial Convolutional Networks

The goal of this paper is to introduce pooling strategies for simplicial convolutional neural networks. Inspired by graph pooling methods, we introduce a general formulation for a simplicial pooling layer that performs: i) local aggregation of simplicial signals; ii) principled selection of sampling sets; iii) downsampling and simplicial topology adaptation. The general layer is then customized to design four different pooling strategies (i.e., max, top-k, self-attention, and separated top-k) grounded in the theory of topological signal processing. Also, we leverage the proposed layers in a hierarchical architecture that reduce complexity while representing data at different resolutions. Numerical results on real data benchmarks (i.e., flow and graph classification) illustrate the advantage of the proposed methods with respect to the state of the art.


INTRODUCTION
In the last years, Graph Neural Networks (GNNs) [1][2][3] have shown remarkable results in learning tasks involving data defined on irregular domains (e.g., graphs), such as social networks, recommender systems, cybersecurity, natural language processing, genomics, and many more [3,4]. However, GNNs are designed to work with graphs, which consider only pairwise relationships between data. On the contrary, many real-world phenomena involve multi-way relationships as, e.g., in biological or social networks. Some recent works in topological signal processing [5,6] have shown that multi-way relationships can be described using simplicial complexes, which are specific instances of hyper-graphs with powerful algebraic representation able to model higher-order interactions among nodes. Consequently, there was also a raising interest in the development of (deep) neural network architectures able to handle data defined on topological spaces, as summarized in the sequel. Related works. Despite its recent birth, many contributions have been made to the field of simplicial deep learning. In [7], the authors introduced a basic simplicial neural network (SNN) architecture that performs convolution exploiting highorder Laplacians without independently exploiting upper and lower neighbourhoods. In [8], message passing neural networks (MPNNs) are adapted to simplicial complexes, with the aggregation and updating functions taking into account data defined on adjacent simplices, enabling message exchange even among signals of different orders. The work in [9] exploits the simplicial filters introduced in [10] to design a flexible and low-complexity simplicial convolutional networks (SCNs) with spectral interpretability. Finally, in [11,12], simplicial attentional architectures are introduced.
Motivated by the fact that, both in convolutional neural networks (CNNs) and in GNNs, the introduction of pooling layers was proved to be useful for reducing the number of model parameters while improving the learning performance, in this work we aim to endow SCNs with pooling strategies. However, while for CNNs the pooling operation relies on aggregation based on the natural local neighbourhood provided by the regular grid domain, even on simpler graph domains the definition of local patches is not straightforward. Early works tried to overcome this issue by using graph clustering algorithms such as GraClus [13] or spectral methods [14] to produce a node assignment that generalizes the notion of locality present in regular domains. The most recent trends are instead focused on differentiable learnable operators that can learn a node assignment [15], or simply keep some nodes while discarding the others [16,17]. Other works [18] discuss the class of global pooling methods that reduce the graph to a single vector, ignoring topological information. To the best of our knowledge, no previous works tackled the problem of pooling for SCNs. Contribution. The goal of this work is to introduce pooling strategies for SCNs. Taking inspiration from the select-reduceconnect (SRC) paradigm [19], we introduce a general simplicial pooling layer that comprises three steps: i) a local aggregation step responsible for providing a meaningful summary of the input signals; ii) a selection step responsible for selecting a proper subset of simplices; finally, iii) a reduction step that downsamples the input complex and the aggregated signals of step i) based on the simplices selected in step ii). By tailoring steps ii) and iii), we introduce four different simplicial pooling layers that generalize the well-known graph pooling strategies. Also, we exploit the proposed simplicial pooling layers in a jumping knowledge (JK) hierarchical architecture [20], which aggregates the intermediate embeddings produced by the simplicial pooling layers to produce the final output. Finally, we assess the performance of the proposed methods on realworld graph and trajectory classification tasks, showing favorable comparisons with respect to other techniques in terms of performance and robustness to compression.

BACKGROUND
Simplicial complex and signals. Given a finite set of vertices V, a k-simplex H k is a subset of V with cardinality k + 1. A face of H k is a subset with cardinality k and thus a k-simplex has k + 1 faces. A coface of H k is a (k + 1)-simplex that includes H k [5,21]. The lower neighbourhood N ↓ of H k is the set of simplices with which it shares a face. Similarly, the upper neighbourhood N ↑ of H k is the set of simplices with which it shares a co-face. A simplicial complex XK of order K is a collection of k-simplices H k , k = 0, . . . , K such that, for any A k-simplicial signal is defined as a mapping from the set of all k-simplices contained in the complex to the real numbers: In this paper, w.l.o.g., we will focus on complexes X2 of order up to two, thus with a set of vertices D0 = V with |V| = V , a set of edges D1 = E with |E| = E and a set of triangles Algebraic representations. The structure of a simplicial complex XK is described by the set of its incidence matrices B k , with k = 1, . . . , K. The B k 's describe which k-simplices are incident to which (k − 1)-simplices: From the incidence information, we can build the high order combinatorial Laplacian matrices [22] of order k = 0, . . . , K: The term L k,d in (3), also known as lower Laplacian, encodes the lower adjacency of k-order simplices; the second term L k,u , also known as upper Laplacian, encodes the upper adjacency of k-order simplices. Thus, for example, two edges are lower adjacent if they share a common vertex, whereas they are upper adjacent if they are faces of a common triangle. Note that the vertices of a graph can only be upper adjacent if they are incident to the same edge. This is why L0 contains only one term, and it corresponds to the usual graph Laplacian. Hodge Decomposition. High order Laplacians admit a Hodge decomposition [21], such that any k-simplicial signal z k ∈ R N k can be decomposed as: for k = 0, 1, . . . , K. The first term B T k z k−1 of (4) is called irrotational component, the second term B k+1 z k+1 solenoidal component, and the third term z k,h harmonic component. In the sequel, we will focus w.l.o.g. on edge flow signals and complexes of order 2. Therefore, we will drop the subscripts and denote z1 with z, L1 with L, L 1,d with L d , L1,u with Lu and X2 with X . Moreover, we denote the lower and upper neighborhoods of the i-th edge with N i,↓ and N i,↑ , respectively.

SIMPLICIAL CONVOLUTIONAL NETWORKS WITH POOLING LAYERS
The Hodge decomposition in (4) suggests to separately filter the components of simplicial signals. Indeed, the work in [10] introduced linear shift-invariant (LSI) filters for simplicial signals, which can be seen as a generalization of LSI graph filters that exploit both upper and lower connectivities. A simplicial convolutional neural network is made by the concatenation of several layers composed by a point-wise non-linearity applied to a bank of LSI simplicial filters plus a residual connection [9].
In this paper, we generalize the layer structure of [9] introducing a a family of pooling strategies encoded into the mapping P(·). In particular, letting X ∈ R E×G be the matrix collecting G edge signals on its columns, the layer of an SCN endowed with pooling mechanisms (SCNP) can be written as: where Y ∈ R E ×F , with E ≤ E; the filters and residual weights Dp Ju p=1 and H ∈ R G×F are learnable parameters, while the order J d and Ju of the filters, the number F of output signals, and the non-linearity σ(·) are hyperparameters to be chosen at each layer. Therefore, an SCNP of depth L is built as the stack of L layers defined as in (5); the SCN layer in [9] is recovered from (5) removing the pooling stage.

Design of simplicial pooling mapping
In this paragraph, we present a general formulation for a simplicial pooling mapping, which will then be tailored to design four different pooling strategies. Let us first denote the input to the pooling mapping in (5) as Z = Z d + Zu + Z h ∈ R E×F , and let the simplicial complex structure be encoded into X = (Lu, L d ). We also denote as Z ∈ R E ×F the output of the pooling layer in (5). Then, formally, we define a simplicial pooling layer as the mapping which takes as input a simplicial complex X and signals Z ∈ R E×F defined on it, and returns as output a sub-complex X ⊂ X and signals Z ∈ R E ×F defined on it, with E < E.
Following the pooling paradigm introduced in [19] for GNNs, we propose to model the layer in (6) as the composition of three operations: a local aggregation step, a selection step, and a reduction step. The local aggregation step is responsible for providing summary signals Z ∈ R E×F of the input signals Z ∈ R E×F leveraging the connectivity induced by the complex X . Formally, we define it as the local mapping: The mapping in (7)  The selection step is responsible for choosing a subset E ⊂ E of edges that will compose the 1-skeleton of the sub-complex X . Formally, we define it as a mapping: The cardinality of E is tuned via the pooling ratio r ∈ (0, 1] (a hyperparameter to be chosen), such that |E | = E = r · E . Finally, the reduction step is responsible for properly downsampling the input complex X and the aggregated signals Z to obtain the output sub-complex X and the output signals Z ∈ R E ×F , based on the edge set E chosen through the selection set. Formally, we define it as a mapping: We assume that the reduction mapping in (9) is given by the concurrent application of two independent operations, i.e., R = (RS, RC ), which separately downsample signal and simplicial complex structure, respectively, and are defined as: (Complex reduction) RC : (E , X ) → X .
The operations (10)-(11) compute the signals Z and the complex structure X at the output of the pooling layer, respectively. In summary, the general pooling mapping P in (6) is given by the composition of the three operations in (7)-(9), i.e., We assume that the aggregation in (7) is kept fixed (e.g., max or mean). Also, the complex reduction in (11) is computed as follows: if an edge e belongs to E but it is not in E , the lower connectivity is updated by disconnecting the nodes that are on the boundary of e, while the upper connectivity is updated by removing the triangles that have e on their boundaries.

Simplicial pooling strategies
In this paragraph, we customize the selection and signal reduction steps in (8) and (10) to design four pooling strategies. Max pooling: The first method is an extension of the Max Pooling strategy commonly used in CNNs. It selects the subset of edges E by ranking the absolute values of the sum of the aggregated signals Z of each edge. Formally, we define: where 1 is the vector of all ones, and top E (·) selects the indexes of the the E largest entries of its vector argument.
Top-k pooling: The next layer is a generalization of those proposed in [16,18] for GNNs. It selects the subset of edges E ranking a learnable weighted combination of the aggregated signals Z of each edge. Then, it computes the reduced signals as a scaled version of Z with coefficients in [0, 1] given by a normalization of the aforementioned weighted combination. Formally, we have: where p is a learnable vector, and is the Hadamard product. Self-Attention Pooling: This method is a generalization of SagPool [17]. The main difference with Top-k is that the ranking is computed over the output of a simplicial convolutional layer as in (5) without pooling and with one output signal, here briefly denoted as SCN. Formally, we have: Separated Top-k pooling: The Hodge Decomposition in (4) and the consequent structure of the SCNP layer in (5) suggest to design pooling layers based on the computation of three different aggregated signals: Z d (obtained from Z d ), Zu (obtained from Zu), and Z h (obtained from Z h ). Consequently, we will have three corresponding score vectors y d , y u , and y h , respectively. Thus, the "separated" version of the Top−k layer in (15)-(16) is given by: RS : where p u , p d , and p h are learnable vectors. Also all the previous methods can be reformulated in this "separated" version, but we leave their presentation and assessment for future works.

NUMERICAL EXPERIMENTS
In this section, we assess the performance of the proposed simplicial pooling layers and hierarchical architecture on two learning tasks: trajectory classification [8], and real-world graph [23] classification 1 . We compare the four proposed simplicial pooling layers with a random pooling strategy, and with plain SCNs having no pooling layers. Also, for graph classification, we show the results obtained using GCNs [3] equipped with the "graph counterpart" of the proposed simplicial pooling layers. All the hyper-parameters are tuned to obtain the best performance per each dataset, except for the pooling ratio, which we keep fixed at r = 0.7. We compute the intermediate and global embeddings via mean-maximum concatenation and sum, respectively. The models are trained for 150 epochs using the Adam optimizer [24] and early stopping with patience 25.
All the experiments are averaged on five random seeds. We first test the proposed simplicial pooling on two flow classification tasks, namely the synthetic flow and ocean drifter datasets, whose details can be found in [6,8]. In Table 1 (right side), we compare the accuracy obtained by all the considered methods, illustrating the gain introduced by the proposed simplicial pooling layers for both datasets. Then, to assess the accuracy-complexity tradeoff obtained by the proposed strate- gies, in Fig. 2 we show the accuracy of the classification task versus the pooling ratio for the synthetic flow dataset considering three pooling methods. As we can see from Fig. 2, the accuracy mildly decreases with the pooling ratio, especially for the Separated Top-k strategy, illustrating the very good accuracycomplexity trade-off obtained by the proposed methods. Finally, we study the performance of the proposed simplicial pooling layers on real-world graph classification tasks on the popular TUDataset [23] collection. To obtain simplicial complexes from the graphs, we follow the clique complex lifting procedure proposed in [8], while the input edge signals are computed as the average of the graph signals of the boundary nodes. Then, in Table 1 (left side), we can see how the proposed SCNPs outperform SCNs with random pooling layers or no pooling, and the GCNs counterpart architectures.

CONCLUSIONS
In this paper, we have proposed a general formulation of a pooling layer for simplicial convolutional neural networks, designed as the composition of a local aggregation mapping, a selection mapping, and a reduction mapping. The proposed methodology is then tailored to design four different simplicial pooling layers, which generalize known graph pooling strategies for simplicial neural architectures. Numerical results on real and synthetic benchmarks illustrate the favorable performance of the proposed strategies with respect to other methods available in the literature. Future extensions include more complex simplicial architectures [8], or cell complex neural networks [25][26][27].