SaNN: Simple Yet Powerful Simplicial-aware Neural Networks
Authors: Sravanthi Gurugubelli
Sundeep Prabhakar Chepuri
Venue: ICLR 2024 spotlight (2024)
Keywords: Graph Neural Networks
Higher-order Representation Learning
Simplicial Complexes
Simplicial Neural Networks
Weisfeiler-Lehman Isomorphism Test
Primary area: learning on graphs and other geometries & topologies

Abstract: Simplicial neural networks (SNNs) are deep models for higher-order graph representation learning. SNNs learn low-dimensional embeddings of simplices in a simplicial complex by aggregating features of their respective upper, lower, boundary, and coboundary adjacent simplices. The aggregation in SNNs is carried out during training. Since the number of simplices of various orders in a simplicial complex is significantly large, the memory and training-time requirement in SNNs is enormous. In this work, we propose a scalable simplicial-aware neural network (SaNN) model with a constant run-time and memory requirements independent of the size of the simplicial complex and the density of interactions in it. SaNN is based on pre-aggregated simplicial-aware features as inputs to a neural network, so it has a strong simplicial-structural inductive bias. We provide theoretical conditions under which SaNN is provably more powerful than the Weisfeiler-Lehman (WL) graph isomorphism test and as powerful as the simplicial Weisfeiler-Lehman (SWL) test. We also show that SaNN is permutation and orientation equivariant and satisfies simplicial-awareness of the highest order in a simplicial complex. We demonstrate via numerical experiments that despite being computationally economical, the proposed model achieves state-of-the-art performance in predicting trajectories,  simplicial closures, and classifying graphs.

Published as a conference paper at ICLR 2024
SANN: SIMPLE YET POWERFUL SIMPLICIAL-AWARE NEURAL NETWORKS
Sravanthi Gurugubelli & Sundeep Prabhakar Chepuri Indian Institute of Science, Bangalore, Karnataka, India (sravanthig spchepuri @ weleeiis...... asc.ac.
ABSTRACT
Simplicial neural networks (SNNs) are deep models for higher-order graph rep- resentation learning. SNNs learn low-dimensional embeddings of simplices in a simplicial complex by aggregating features of their respective upper, lower, boundary, and coboundary adjacent simplices. The aggregation in SNNs is car- ried out during training. Since the number of simplices of various orders in a simplicial complex is significantly large, the memory and training-tine require- ment in SNNs is enormous. In this work, we propose scalable dimplicialawann neural network (SaNN) model with constant run-time and memory requirements independent of the size of the simplicial complex and the density of interactions in it. SaNN is based on pre-aggregated simplicial-aware features as inputs to a neural network, so it has a strong simplicial-structun inductive bias. We pro- vide theoretical conditions under which SaNN is provably more powerful than the Weisfeiler-Lehman (WL) graph isomorphism test and as powerful as the sim- plicial Weisfeiler- Weisfeiler-Lehmmnn (SWL) test. We also show that SaNN is permutation and orientation equivariant and satisfies sinplicial-awareness of the highest order in a simplicial complex. We demonstrate via numerical experiments that despite being computationally economical, the proposed model achieves state-of-the-arr performance in predicting trajectories, simplicial closures, and classifying graphs.
INTRODUCTION
Graph Neural Network (GNN) models are extensively used for analyzing graph-structured data by embedding nodes as points in Euclidean space through neighborhood feature aggregation (Hamilton
et al. 2017; Leskovec & Jegelka 2019 Velickovic et al. 2017 [Rosii et al. 2020 Chen et al.] (020)) The expressive power of a GNN model is often benchmarked against the Weisteiler-Lehman (WL)
isomorphism test (Lehman & Weisteiler 1968) and GNN architectures as powerful (in terms of ex- pressiveness) as the WL test can be designed (Leskovec & Jegelka 2019) by appropriately choosing the aggregation functions. However, inherent limitation of any graph-based neural model lies in its ability to encode only pairwise interactions between entities. In many weal-world scenarios, interactions transcend pairwise relationships, for instance, group-based interactions seen in bio- chemistry (e.g., reaction between reagents), social networks (e.g.. interactions between friends), and trade networks (e.g., interaction between buyers, suppliers, and intermediaries), to name a few. Such supra-pairwise interactions can be effectively captured using simplicial complexes, higher-order generalization of graphs.
A simplicial complex consists of simplices of various orders, including O-simplices (or nodes), I-simplices (or edges), 2-simplices (or triangles), and more generally, k-simplices (or simplices of order k). Higher-order simplices may also be oriented, ensuring a consistent node arrange- ment within each simplex, facilitating tasks like determining information flow directions along the simplices. In simplicial complexes, k-simplices have four types of adjacent simplices: boundary- adjacent ((k - simppieee,, co-boundary-adjacen. ((A + -)smimplices) upper-adjacent, and lower- adjacent (k-simplices). Similar to how GNNs create meaningful embeddings of nodes via sequential neighborhood aggregation, simplicial neural networks (SNNs) generate embeddings for all the k- simplices within simplicial complex. Unlike GNNs that aggregate attributes only from adjacent nodes, SNNs leverage information from upper, lower, boundary, and co-boundary adjacent simplices of k-simplex, enabling them to capture higher-order interactions and generate more expressive

---

Published as a conference paper at ICLR 2024
embeddings compared to GNNs (Bodnar et al. 2021). While the expressive power of GNNs is eval- uated through the WL test, [Bdnar et al. (2021 introduces a theoretical characterization framework for SNNs, namely. the simplicial Weisteiler- Lehman (SWL) test, which is provably more powerful than the WL. test. Further, it is shown that under some conditions on the aggregation functions, SNNS are strictly more powerful than the WL test and are powerful as the SWL test (Bodnar iet al., [021]. Certain SNN models, such as Boddar et al. (202I) and Roddenberry et al. (2021). also showcase properties like simplicial awareness permutation equivariance and orientation equivariance
An important limitation of current SNN models (Ebli et al., 2020 Bunch et al.. 2020 Bodnar al,
2021 Roddenberry et al. [021]] Yang et al. (022b), is the necessity of sequential feature aggregation during training, and this incurs significant memory and training time requirements.
this paper, we propose simplicial-awer awwre neural networks (SaNN), a simpler model with strong simplicial inductive bias and constant training time and memory requirement (independent of the number of interacting simplicies) by augmenting pre-aggregated features as inputs to a neural model, such as multi-layer perceptron (MLP).
Contributions: The main contributions and results are summarized as follows:
We devise a recursive aggregating method with no learnable parameters to compute fea- tures of simplices that are aware of their different hops of neighborhood. The proposed precomputation of features results in a training time that is almost constant for simplicial complexes of any size and order.
We then prescribe conditions on the aggregating functions involved in generating the simplicial-aware features in SaNN to ensure that the embeddings generated by SaNN are provably expressive as those generated by the message passing simplicial network SN). We theoretically prove that SaNN, although a simpler model, is strictly more pow- erful than the WL test and powerful as MPSN, equivalently, the SWL test (Bodnar ct al. 2021).
We also theoretically show that SaNN permutation equivariant, orientation equivariant, and satisfies simplicial awareness of the highest order in simplicial complex while being computationally efficient.
We demonstrate the efficacy of SaNN for three applications: trajectory prediction, simplicial closure (i.e., higher-order link) prediction, and graph classification. We observe that for all the three appli- cations, SaNN outperforms non-deep baselines while being competitive with existing SNN models with a much smaller run-time. Specifically, for simplicial closure prediction, on large datasets with about million simplices of various orders, existing SNN models out of memory.
We next discuss a few works that are related to the proposed work.
Related Works: While exisiting SNN models (Bodnar et al. 2021 Ebli al. 2020 Roddenberry et al. 2021 Bunch et al. 2020) differ in how the features of neighborhood simplices are aggregated and how the aggregated features from different types of neighborhoods are combined, Yang et al. (022b) addresses scalability issues in higher-order traph-based neural networks. Unlike existing SNN models, it relaxes the fundamental definition of simplicial complexes, namely, the inclusion principle (subsets of simplices are simplices in the simplcial complex), to reduce runtime complex- ity. For tasks like predicting simplicial closure, the inclusion principle cannot be ignored [Benson et al. (2018). For instance, in predicting whether simplex is likely to form between three authors who have not all collaborated before, Benson et al. (018) demonstrates that the frequency of collab- oration between any two authors in the group positively affects the closure of the triangle. Moreover, Yang et al. (2022b) assumes all simplices in a complex are unoriented, rendering unsuitable for tasks dependent relative orientation, such trajectory prediction (Roddenberry al. 2021).
awareness caapliceallwwaaenesss plicial complex.
'Simplicial-
ensures the dependence of embeddings on the simplices of orders within a sim-
PPermutation equivariance means that the embeddings of simplices remain unaltered reordered, important attribute for modeling complex structures like graphs and simplicial complexes. 'Orientation equivariance implies that changing the relative orientations of certain simplices will only lead to the output embeddings of those simplices heing the sign-inverted versions of the embeddings prior to the orientation change.
the simplices
2

---

Published as a conference paper at ICLR 2024
The proposed work is inspired by graph- baseed neural network models that attempt to simplify GNN models to improve their scalability, traph-augmenter multi-layer perceptrons (GAMLPs) CChen
et al. 2020), simple and parallel graph isomorphism network (SPIN) (Doshi & Chepuri 2022
scalable inception graph neural networks (SIGN) (Rossi et al.] 2020 and simple graph convo- lutional networks (SGCNs) (Wu et al. 2019) are some examples of scalable and efficient GNN models. GAMLPs, SPIN, and SIGN are related to SaNN in that they compute the node features as preprocessing step before the training procedure. However, they are limited to generating node embeddings by accounting only the pairwise relations. Furthermore, the notion of a a neighborhood in SaNN differs from that in GAMLPs, SPIN, or SIGN. A direct extension of the precomputation step in GAMLPs, SPIN, or SIGN to simplicial complexes would be to precompute the features of simplices using the integer powers of the so-called Hodge Laplacian matrix (the generalization of the graph Laplacian for simplicial complexes and an aggregation operator used in Ebli et al. (2020); Bunch et al. (220). However, it does not account for information in the boundary and co-boundary adjacent simplices, which as we prove in this work, is required to propose powerful as the SWL test. Specificalll, we theoretically prove that for a specific choice of functions involved in generating embeddings, SaNN is strictly more powerful than the existing GNN models. In other words, SaNN implicitly, is strictly more powerful than GAMLPs, SPIN, or SIGN. This also implies that even the node embeddings (i.e., embeddings of 0-simplices) from SaNN are more expressive than the 1-WL test or, equivalently. GNNs. Using the node embeddings alone, SaNN dis- tinguishes a broader class of graphs than those that are distinguishable by GNNs. In summary, our proposed SNN model, denoted by SaNN. is significantly faster than existing SNN models while pre- serving the definition of simplicial complexes and the expressive power of the current SNN models.
efficient model that is as
BACKGROUND
In this section, we mathematically describe simplicial complexes and SNNs.
Simplicial Complex: Let V = fvo, Ui,...,,y, uN} be the node set of cardinality N + 1. A simplicial complex IC is collection of non-empty subsets of V with the inclusion property that if a is an ele- ment of KC, then every subset of an element of K.. A k-dimensional element o = {vo, ,i,... vs of IC with cardinality ++1 is called a k-simplex. Each simplex has orientation defined by stan- dardized vertex order, typically ascending or descending, establishing a standard node arrangement within each simplex. The number of k-simplices in K. is denoted by Ng. A simplicial complex
is said to have an order of K if the cardinality of its largest simplex is K + 1. Such a simplicial complex is also referred as K K-simplicial complex.
A k-simplex dg has four kinds of adjacent simplices, namely, boundary adjacent, co-boundary ad- jacent, upper adjacent, and lower adjacent simplices. The incidence relationship between (k [--]] 1)- simplices and k-simplices along with their relative orientations can be represented by the oriented incidence matrix B. E is a boundary simplex of the jth k-simplex. The non-zero entries of an oriented incidence matrix B, can be either +1 or 11, reflecting the relative orientations of the ith (k- )--simplex and the jth k-simpeex. For unoriented simplices, we use unoriented incidence matrices in which the (i. jthh entry is 1 if the ith (k 1i-miple is boundary simplex of the jthh k-simplex, and O otherwise. The upper and lower adjacencies of k-simplices can be defined using the upper and lower Laplacian matrices A = B E N and Ag.c = BBBB define the matrices Ax,B B -RNN++INN and As.c Bu RNN--INNe for convenience. The (-hop upper, lower, boundary, and co-boundary neighbors of simplex os are denoted by 244) (ax), (( (ax), (ax), and ((*) (ax), respectively. For example, (())) for a O-simplex og simply means (upper adjacent) neighborhood of the node ao-
xNN, The (i,j)th entry of B₃ is non-zero if the ith (k: --ismiplexx
BB E R N respectively. We will also
Simplicial Neural Networks: Let us denote the attributes of k-simplices by Xx E NoXDs and the Da-dimensional feature of a k- k-simplex d as [x(ox). The sign of feature X [a is determined based on the reference orientation of ok. For unoriented features, there is no need for a reference orientation of simplices. such cases, we consider unoriented incidence matrices. SNNs take the simplicial complex structure and the data matrices X, for = O...., K as input, and update the embeddings of the simplices by aggregating embeddings of their adjacent simplices. A generic way of expressing the update rule of the embeddings of k-simplices by the existing SNN models in the 1th layer is given by
H(( o ( (Ar.HH( ((O A. A w. An H. wit H ke1 w
())
3

---

Published as a conference paper at ICLR 2024
where Φ is non-linear function (e.g., ReLU or sigmoid), 1 is a combining function (e.g., summa- tion concatenation) that combines information from the different neighborhoods, and H Xx. The matrix Ar.s lets the model include the self-embeddings of simplices while updating their respective embeddings. Specifically,, the matrix A is taken the identity matrix I if self- embeddings are to be accounted for, and is otherwise set to an all-zero matrix O. The matrices (W's. W w w w are learnable weight matrices of the Ith layer. model with L such layers in cascade sequentially learns embeddings of k-simplices using information from their I--hop neighborhood.
Different choices of the functions, and t/, along with aggregating matrices result in various SNN models, namely, MPSN [Bodnar et al. (2021), SCoNE Roddenberry et al. (202T), SCNN Yang et al.) (2022a), S2CNN Bunch al. (2020), and SNN Ebli al. (2020). More details about the specific choice of the functions in each of the SNN models is provided in Appendix A
3 THE PROPOSED MODEL
The key idea behind the proposed model is to precompute simplicial structure features by aggregating initial features of simplices of different orders from different neighborhood hops. The aggregated features are then transformed using nonlinear functions to obtain embeddings for sim- plices of different orders. The generic embeddings can be used to obtain task-specific embeddings for the desired application. The proposed generic SaNN model for each of the k-simplices has the following two main components.
Precomputing Simplicial-aware Features: Let us collect the feature vectors in the (-hop upper neighborhood of a k-simplex 0% in the multise x x { Vr Eul Similarly, define the following multisets x[
[xx(r) vre (o))) x
{ (x_, Vr (o))) and [fcc = (r) V+ (ox) We sequentially pre-compute simplicial-aware features from different neighborhood depths follows. We update the feature vector of k-simplex σk by aggregating t-hop information of Tk. us- ing the following partial updates that are dependent on 1)-hop aware features as
Kile [xxl = (hau(x(t>((aaa (ox)). Vid [ (x,c(
Y [ollon) = (x (1-1() [ox]), [o = Sr. (x((
(2)
fu.c
where skn x [ow] + Px, for n E (,, B, C} are the neighbor- hood aggregation functions that aggregate features the l-orderr upper, k-oodeer lower, (A or-de boundary, and (k + 1)-order co-boundary adjacent simplices, respectively, of any s-mimplex. The final aggregated t-hop aware emhedding of k-simplex is computed by combining the partial updates obtained from the (t 1h- aware embeddings
fa.e
Figure 1: Simplicial aware neighburhond ag- gregation involves iterative aggregation (no learnable parameters) from the upper. lower, boundary, and co-boundary simplices simplices.
x (x)]
(Y/2)
(t) [ox) Y(lc(ow) (.Bloo) xfdloul)
(3)
for t =0=00 0, ..... .T with X = X as the initial features, where á is function that combines aggregated features from the four types of neighhorhoods and T' denotes the depth of neighhorhood information considered by SaNN (which is analogous the number of layers in SNNs). For any k-simplex dı K, the aggregated feature vectors x [ox) be efficiently precomputed for all it and t outside the training process as no learnable parameters involved, but they have strong simplicial-structun inductive bias. The aggregation scheme in an SaNN model is illustrated in Fig.
Learning from Simplicial-aware Features: We use Iearnalle nonlincar transformation functions, 96 (-), to transform the precomputed features into embeddings that are suitable for the task at hand as
x
CA
H
gh
Figure Feature Sabil compute the matrix embodding H; of k-simplices from the precomputed features. Here, use plate notation, with the bottom of the plate denoting the presence K I such blocks for 0, K.
blocks
for t: = 1......... K and 0, 1, 2, T. We finally combine the embeddings k-simplices from different hops of neighborhood as
H O ( s(") (())
(5)
AA multiset is a collection of elements that accommodates duplicate elements while accounting for the multiplicities of each element.
4

---

Published as a conference paper at ICLR 2024
where O₃ is function that combines information from different hops for k-simplices. The transformation of precomputed features and the combination of features from different depths in an SaNN model summarized in Fig. 2 We denote the final embedding of a k-simplex ds E K generated by SaNN using the information
from O, ...... Thop neighborhood as [ou] =; [o]]
Computational Complexity: SaNN model incurs significantly lower time complexity than the existing SNN models as we are precomputing the aggregated features from different hops while allowing the features to have cmpplicial-strutture Specifically, the existing T-layer SNN models have an over- all time complexity of about O(T((2N) De + N D + N&NN++ D + (3NN, D + NeDi + N₂ 1))),, while SaNN model (an example architecture tion (4.1) capturing information from o,..., Thhop neighborhood of k-simplices has a significantly smaller time complexity of (T + +N D2-1 + Ng. compared to the existing SNN models. More details the contribution of different compo- nents of SNNs and Sa ities are provided in Appendix B In Fig. [] we show a comparison of the average run-time measurements of SaNN and MP SN on an ex- ample dataset. We observe that the average run-time of the proposed model for forward pass is almost constant for simplicial complexes of any size and increases only slightly with simplices of higher orders, whereas the run-time of MPS5 increases drastically when simplices of higher orders are considered.
1137
Pargeo weggigh Vies
vesit (iouear
inductive bias.
(he
prowided in Sec-
SABY (Teolleored
So the www.kailll...oo. compht
their respective computational complex-
Figure 3: Average run time of SANN and MP lover experiments
epochs) email-Baron dataset (Benson et al., 2018), with triangles and hexahedrons as highest order simplices.
In what follows, we theoretically characterize the expressive power of SaNN.
THEORETICAL CHARACTERIZATION OF SANN
Given the computational advantage of the SaNN model, now analyze its expressive power, Specifically, we characterize the discriminative power of SaNN with respect to the WL. and SWL tests (Please refer Appendix for more details about the SWL test). The following theorem states the conditions under which the SaNN model is more powerful than the test.
Theorem 4.1. SaNN is strictly more powerful than the WL test in distinguishing non-isomorphic graphs with complex-clique lifting all the functions involved in generating the node embeddings, namely, fo2e()), fo.c(.), ((-), (.,.""" ( and Ou(-) for T are injective.
Although MP SN is provably more powerful than the WL test, it has the same form of the sequential approach of aggregating transformed features as is the case with the WL test. The proposed model. however, does not have the same form as the WL test since it is based on pre- ve-aaggrggtiin fcatures from different hops. Hence, the proof of comparing the expressive powers of SaNN and the WL test is not trivial. The proof of Thcorem 44. provided in Appendix [D] To prove the above theorem, we first prove that SaNN atleast as powerful as the WL test by showing that if the node embeddings of two nodes generated by SaNN are equal, then the WL node coloring for the two nodes are equal. We then give an example where SaNN, using the higher-order information, distinguishes two graphs that the WL test cannot, to show that SaNN is more powerful than the WI. test. Thus for appropriately chosen functions in Equations
and SaNN is provably more powerful than the WL
test.
The theorem implies that any arbitrary extension of GAMLPs (Chen et al., 2020), SPIN Doohii & Chep-] uni 2002).. or SIGN (Rossi et al. 2020) to higher-order simplices does not result in the node-embeddings. from SaNN having superior expressive power GNNs. In one possible extension, we could replace the integer powers of adjacency matrices in these graph models with those of the Hodge Laplacian matrices. These matrices generalize the graph Laplacian to simplicial complexes and are defined as the sum of upper and lower Lapla- cians. However, even with this modification, the expressive power of these extended models does not surpass that of GNNs. The theorem states that the node embeddings from the proposed model, under the conditions given in Theorem 4.1 are more expressive than those from the WL test (or equivalently, any of the existing GNN models and scalable versions). Consider- ing graph with no higher-order interactions, the node embed- dings (0- (0-simplices) from SaNN have better expressive power than scalable GNNs because SaNN incorporates information from its co- couuduryyry adjacent simplices (edges) while learning the embedding for node, which inturn carry information from their co-boundary adjacent simplices (triangles), and on.
Figure 4: A pair of non isomorphic graphs (a) and (b) distinguishable by SaNN but not by the WL. test. The histograms of colors assigned by of embeddings assigned by Salll for the first three it- crations displayed alongside the two graphs. Here, nodes assigned numerical lahels nient referencing. While the histogram of colors assigned by the WL test both graphs remains the same. the fig- ure demonstrates that SaNN generates différent embed- dings.
and those
conve.
5

---

Published as a conference paper at ICLR 2024
An illustration visualize the expressive power of SaNN in comparision to the WL test is provided in Fig. We present one instance of pair of clique-lifted graphs for which the WL test assigns the same representations and, therefore, fails to identify the two graphs as being non-isomorphic while SaNN assigns different repre- sentations to the two graphs and distinguishes them. To assign a representation for the graph as a whole, we follow the usual procedure of constructing the histogram of representations of the nodes. The histogram of colors assigned by the WL test and the histogram of embeddings assigned by SaNN for the first three itera- tions are shown next to the two graphs. The histogram of colors assigned by the WL. test to both graphs is the same. However, as shown in the figure, SaNN generates different embeddings to the two graphs (more details in Section 4.
In the next theorem, we provide the conditions on the functions such that SaNN is as powerful as the SWI. test.
Theorem 4.2. SaNN is as powerfid as the SWL test in distinguishing
-on-isomorphic simpli- cial complexes if the functions involved in generating the embeddings of the simplices, namely, fu.u(-), (+), ft.l.)) ft,,(-),, (()),
and @x(-) for = o....,I' and ks = O...., K. where T is the depth of the neighborhood information considered by SaNN in generating embeddings of simplices of each of the K + 1 orders, are injective.
(.)).
We prove Theorem 4.2 in Appendix To prove the above theorem, we propose simpler yet equally expressive alternative representation of the SWL update. Using the alternative update rule, we first prove that SaNN at most as powerful as the SWL test by showing that if the colors assigned by SWL are the same for two simplices, then SaNN also generates the same embeddings for the two simplices. We then prove that SaNN is at least as powerful as the SWL test by showing that if the embeddings generated by SaNN are the same for two simplices, then SWL also generates the same colors for the simplices.
The theorem states that the embeddings simplices from the proposed computationally efficient method, under the conditions given in Theorem [4.] are as expressive as those from BBonnrr et al. (2021). which is proved to be as powerful as the SWL test. While the SWL test and Bodnar et al. (2021) are both based on the sequential approach of aggregating transformed features, the pre-age aggregated features are transformed only during training in the proposed method. Despite avoiding the non-linear transformation of features in every iteration of feature aggregation, we prove that SaNN as powerful as the SWI. test.
To conclude, it is sufficient to limit the choice of aggnegator and transformation functions to those recommended by Theorems 4. and 4.2 design an SaNN model that is guaranteed to be more powerful than the WL test and powerful the SWL test, respectively. In what follows. discuss few such choices of the aggregator and transformation functions.
4.1 AN EXAMPLE SANN ARCHITECTURE
In this section, we discuss example functions that fulfill the conditions outlined in Theorem 4 and demonstrate that SaNN is as powerful as the SWL test. The SWL test [ef. Appendix CJ distinguishes non-isomorphic simplicial complexes based on structure, assuming uniform initial features (colors) across all simplices. To establish equivalence with the SWL test, we consider simplicial complexes with uniform scalar feature a on all simplices, without attributing any orientation to the features or the simplices. However, it worth noting that SaNN can also process oriented features in practice, and in such cases, we work with oriented simplicial complexes (or incidence matrices) as defined in Section 2.
Precomputing Simplicial-aware Features: Consider simplicial complexes with the same scalar feature as initial feature on all the simplices. For such scenario, one choice of the aggregation functions fa.u((), f+) fx. and ft,c(.) that preserves injectivity is the summation function. The summation of embeddings of upper, lower. boundary, and coboundary adjacent simplices can be computed efficiently using the (sparse) aggregation matrices defined in Section Specifically, we compute the partial updates in (2) for aggregation based on summation recursively
(6) Another common choice for neighborhood aggregation in GNNs and SNNs is degree-based weighted sum- mation. To implement degree-based weighted summation of neighboring embeddings. we use the follow- ing normalized incidence matrices: BLU = D 1/2 Ax 1/2
( E = A
(1-1) Y (x,
(()) kB AL-LIX((
(L-1), Y F.C ALtICX ((-1) k+1
BA, = "D,,"AA, -1/2 B -12 k-1,A- and BE.C- = D A, K+1,K. Here, D E BNNANN is a diagonal matrix
Di 1, whose (i, i)th entry is the number of k-simplices that are upper and lower adjacent neighbors of the ith k- simplex. DA,A-1 E I NxN, XNx is diagonal matrix whose (i, i)th entry is the number of k 1-simplices that are houndary adjacent neighbors of the ith k-simplex, and Da.++1 = R Ne N2 is a diagonal matrix whose (i, t)th entry is the number of l + 1-simplices that are co-boundary adjacent neighbors of the äth A-simplex.
-1/22
Using normalized incidence matrices aggregate features has the advantage of bringing all the features the same scale, thus providing numerical stability. However, plc, consider the two simplicial complexes in Fig. 5 with a as initial feature on simplices of all orders.
not always injective. For exam-

---

Published as a conference paper at ICLR 2024
Although the triangles, denoted by on and 02, in the simplicial com- plexes, have different number of lower adjacent triangles in their 1-hop neighborhood, the two triangles will be assigned the same lower neighbor- hood aggregated partial embodding by the degree-basee weighted summa- tion aggregator, which, in this case, is The summation aggregator, on the other hand, will assign two different lower adjacent neighborhood aggre- gated partial embeddings, specifically. 3a and 2a, to two triangles with different neighborhoods. In Appendix [F] we give generalized case where the degree- degree-based weighted sum aggregator is not injective, i.e. where the proposed architecture assigns the same partial updates to k-simplices in simplicial complexes with different structures.
Figure 5: simplicial complexes which SaltN assigns the same partial em- beddings of 2-simplices after aggregation from the lower adjacent neighhorhood the degree-based weighted summation ag- gregator is used.
We get the final updated t-hop aware feature vector of a k-simplex a, denoted by x(" E RN (() D = 2D 1) + ((r-)) + ((t-1) k+1 b concatenating the partial updates in as
where
= xL y
i.e., use an injective concatenation read-out function (other commonly used sum, mean, max read-out functions are not injective). Next, we discuss some properties of the proposed aggregation method. Property 1. The devised aggregation scheme is permutation and orientation equivariant.
We prove the equivariance the aggregation method Appendix G We first prove the permutation (orienta- tion) equivariance for one-hop aggregation, i.e., we show that if the ordering (orientations) the input features to SaNN are altered by some permutation operator P, (O, respectively), then the ordering (orientations) of the 1 t-hop aggregated features are changed by the same operator P, (O, respectively). We then prove, by induction, the permutation (orientation) equivariance of the proposed aggregation for any hop. The equivariance prop- erties of the proposed aggregation method aids the construction of permutation and orientation equivariant SaNN as we see in the next subsection.
Note that the proposed precomputation method is very different from that in GAMLPs, SPIN, or SIGN, The precomputation step in GAMLPs, Ms,s, SPIN, SIGN involves taking integer powers of graph adjacency or Lapla- cian matrices aggregate information from different hops of neighborhood. However, such a straightforward precomputation step for simplicial complexes will not result in model that captures information from different types and hops of neighborhood while being (i) as powerful as the SWL test (ii) permutation equivariant, and (iii) orientation equivariant.
MLPs for Transforming Precomputed Features: Once the features are aggregated by preserving injectivity and ensuring equivariance properties. the next step is transform the aggregated simplicial-aware features more task-aware features using non-linear learnable functions. According to Theorem 4.2 the learnable functions should be injective in order for SaNN to be as powerful as the SWL test. Given the universal approx- imation ability and injectivity of multi-layer pereeptrons (MLPs), we model the transformation functions (t) for t = O,..., T and k = o,... K using MLPs. Single-layer perceptrons, however, are not injective.
For O₂ in (5) we use concatenation read-out function combine embeddings of simplices of any order k: and get the combined embeddings H,
H S
(8)
Concatenating the embeddings results in an injective combination of embeddings simplices of different orders. Typically, to avoid over smoothing, we use embeddings from only or 3-hop neighhorhood, thus concatenation does not result in very large dimensional embeddings.
4.2 PROPERTIES OF SANN
We next prove that SaNN, with the aggregation and transformation functions satisfying the requirements in Theorem 4.2 (as in the example architecture in the Subsection 4.1), possesses all the equivariance properties namely.,Rdddenberr
that some of the existing SNNs, namely, (Roddenberry el. (202 and Bodnar al. (2021, possess. SaNN with the summation based neighborhood aggregation, feature transtormation using MLPs, and using concatenation O2 has the following properties.
Permutation equivariance: As discussed in Property [ the proposed aggregation scheme is permutation equivariant. With the transformation functions MI.s and the functions that combine embeddings from different hops as concatenation, SaNN is composition of permutation equivariant functions and hence is permutation equivariant.
Orientation equivariance: Using orientation equivariance of the proposed aggregation method [cf. Property [ and the fact that an MI.P is orientation equivariant if the activation functions in the MI. are odd, prove that Sa is orientation equivariant if all the activation functions involved in the network odd in Appendix G

---

Published as a conference paper at ICLR 2024
Simpliciil-awarrenes::: Since the embeddings of SaNN depend the boundary matrices of all orders, i.e., Bx for I,..., K, of a K K-sipplicial complex, SaNN is said satisfy simplicial-awe -awareesss of order K for a K K-simplicial complex.
EMPIRICAL EVIDENCE
In this section, we empirically evaluate SaNN in terms of its ability to perform the following three tasks: trajectory prediction, simplicial closure prediction, and graph classification e
5.1 DOWNSTREAM TASKS
The details of the three tasks are discussed next.
Trajectory prediction involves predicting the next node in sequence formed by a series of nodes connected by edges, with oriented flows the edges. As the features are oriented, we use oriented incidence matrices for aggregation. We evaluate the trajectory prediction ability of SaNN on four datasets, namely, Ocean (Roddenberry et al., [.2T]. Synthetic (Roddenberry et al.] [022], Planar (Cordonnier & Louuas 2018), and Mesh (Cordonnicr & Loukas 2018). We compare the trajectory prediction accuracy of SaNN with state-of-the-art SNN variants, namely, SCoNe (Roddenberry et al. (021) and SCNN (Ebli et al.] 2020). and a non-deep projection based method, denoted by Projection, which projects the input edge
Trajectory Prediction:
Teatures onto the Hodge Laplacian kernel (Schaub et al. 2020)
The goal of simplicial closure prediction to predict the closure of open simplices in time series of simplicial complex data. We perform this task on the email-Eus cmail Email-Ennee and cont act set-hight gh-school datasets, as referenced in |Benson et al. (2018). Our methodology involves a temporal split of the data for these datasets, using the initial 80% of the data to train the encoder. The remaining 20% of the data is aside for inference. Given the highly skewed nature of the dataset, we employ the relative area under the precision-recal curve (AUC-PR) as the evaluation metric for model performance.
Simplicial-closure Prediction:
Graph Classificatton: Graph classification refers to classifying (clique-liftee) graphs as belonging to one of two or more possible known classes. For all graph classification experiments, we consider the initial features on simplices as the cumulative count of their lower and upper adjacent simplices. As these unoriented, we unoriented incidence matrices for aggregation. We compare the graph classification accuracy of SaNN with MPSN (Bodnar et al. [202]] and state-of-the-art GNN variants, DGCNN (Phan et al. 2018), G GIN (Leskovec & Jegelka, (2019), and Grap GraphSage (Hamilton et al.) (017)) on benchmark datasets for binary as well as multi- class graph classification tasks from chemical and social domains. Specifically, we evaluate on the following TUDatasets (Morris al. 2020): Proteins, NCI1, IMDB-B, -B, IMDB-M, Reddit-B and Reddit-M.
5.2 RESULTS AND DISCUSSION
Performance: We report the performance SaNN for trajectory prediction, simplicial closure prediction and graph classification in Tables I @ seconds) within brackets. We experimentally observe that SaNN is almost as effective as the existing SNN models, which successively update the features of simplices every layer, while being several times faster.
and 3 respectively. We also provide the per epoch run-time values (in
Insights: For trajectory prediction, SaNN is observed to outperform the projection-based method and has competitive performance as the existing SNN models on all the datasets. The good performance of SaNN also signifies its effective use of the orientations of flows for trajectory prediction. We apply the existing SNN models and SaNN for simplicial closure prediction. The deep models are observed to perform exceptionally better than logistic regression. Of the three deep models, namely, MPSN, SCNN, and SaNN, MPSN observed to have the best performance on some of the smaller datasets, namely, high school, and primary- school datasets. However, on datasets with a large number of simplices, due to the dependence of each layer the existing SNN models on, approximately, the square of the number of simplices, the existing SNN variants quickly run out of memory. SaNN, the other hand, performs competitively with the existing SNN models while being many times faster. The computational savings of SaNN are the most evident for this application the
Details about the experimental setup, datascts, attributes, hyperparameters, evaluation metrics, training, validation, and test splits for the three tasks are provided in Appendix H
Table 1: Trajectory prediction accuracies on various datascts. The first and sccond best performances are highlighted in red and blue. respectively. The values within parentheses are the average per epoch run-time values (in seconds). The first terms in the runtime values of SabN correspond to the precomputation times the second temss to the epoch training times. Run-time values of non-deep baseline are indicated by The best run values highlighted bold.
DATASET
SYNTHETIC
PLANAR
MESH
PROJECTION
27.15 4: 0.0
$2.0 A: 0.0
100.0 = 0.0
30,9 1: 0.0
30.0 :: 0.6
$5.4 1.1
97.0 1.9
98.5 1.9
SCoNe RODDENBERKY ET AL. 2021 2021
(0.4)
(3.2)
(30.2)
(18.9)
28.5 0.6
50.5
97.6 + 2.0
98.1 2.0
SCNN
YANG
2022A
(1.9)
(4.2)
(36.3)
(29.8)
35.0 2: 0.7
$4.9 1: 1.1
97.3 =: 1.9
98.3 :: 2.0
BANN
(0.01. 0.1)
(0.06, 2.5)
(1.22, 26.8)
(0.39.
8

---

Published as a conference paper at ICLR 2024
Table 2: Relative AUC-PR PR values for simplicial cleoure prediction. The first and the second hest performances are highlligtted in red and blue, respectively. The values within parentbeses are the average per opoch run-time values (in seconds). The first terms the runtime values saNN correspond to the precompuration times and the second terms to per epoch training times. The hest nun-rime values are highlighted in bold. Out-of-mamary results are indicated by
DATASET
ENRON
HIGH-SCHOOG ScHOOL
PRIMARY-SCROOL
NDC-CLASSES
MATH-SX
RARDOM DASELINE (RB)
0.0537
0,0112
0.0105
0.2190
0.0202
LEG. Rec./Rs /RB
0.55 :: 0.0
0.59 =: 0.0
1,79 4: 0.0
2.32 4 0.3
0.65 :: 0.0
MPBN
BODNAR ET AL.
2021
14.51 0.1
(255)
30.83 0.0
(413)
20.19 1: (3499)
33,05 0.0
SCNN
YANG BY ML.
2022A VRD
14.17 4: 0.0
(17)
20.53 4: 0.0
(401)
(1891)
15.45 = 0.0
30.22
32.89 0.0
2.79 + 0.0 (0.26, 13)
6.88 0.0
SANNVRB
(0.01, 3)
(0.05, 112)
(0.76, 916)
(2889)
Table 3: Graph classificationn accuracies on various datasets. The first and the second best performances are highlighted in red and blue. within parentheses are the average per epech run-time values (in seconds). The first terms the runtime values
respectively. The values SP and SaNN correspead to the precomputation times and the second terms to the per epoch training times. The best time values are highlighted in bold.
DATASET
PROTEINS
NCII
IMDB-B
REDDIT-B
REDDIT-M
MPSN
BODNAR ET AL..
2021
76.5 + 3.4
(33)
8288 = 2.2
(292)
75.6 3.2
(46)
92.2 = 1.0
(242)
57.3 1.6
(1119)
72.9
76.4 # 1.7
69.2
87.8
49.2 1.2
DICKNN
PHAN RT AI..
2018
(21)
(218)
(19)
(231)
(353)
GIN
LESKOVEC JEGELKA
2019
73.3
(19)
80.0 =: 1,4
(171)
89.9 7.22
(17)
(190)
56,1 1: 1.7
(241)
GRAB #SAGB
HAMILTON AL.
2017
73.0
(17)
76.0 =:0:: 1.8
(167)
68.8 4.5
(15)
(188)
50.0 + 1.3
(219)
SPIN
DOSHt & CHEPURI 2022
75.6
(..6,0.3)
74.0= 1.7
(4)
71.1 5.0
(0.3.
88.4
(59.
53.8 + 1.4
(4, 88)
77.6
2.2
72.7
2.1
91.7
SANN
(3.6.
(8,
(4,8)
(6,45)
(34, 104)
datasets have several thousands of simplices [ef. Table/ojin Appendix [H] SaNN is observed to have competitive performance as MPSN also for graph classification. Though MPSN has a slightly better performance in terms of the means of the accuracies, in most of the results, the accuracies have significant statistical overlap, i.e., the standard deviations are too high compared to the difference in their means. Hence, comparisons between the best, second best, and others are insignificant. Furthermore, as for the other applications mentioned above, SaNN has the advantage of being almost independent of the number of simplices in the simplicial complexes.
To give additional insights into which aspects of SaNN contribute the most to its competi- tive performance, we perform ablation studies. We study the effect of features from different depths and observe that the proposed SaNN model that combines features from different depths outperforms ablated SaNN models that use specific neighborhood depths, indicating that although geghe-hhpp-aware features implicitly contain lower-hop information, explicitly combining the information from all the hops has an empirical advantage. This agrees with the thcoretical results since the model presented in Scction[] unlike the ablated Sa NN mod- cls, is provably as expressive as MPSN, suggesting that its embeddings are equally expressive and capable of achieving similar performance in downstream tasks as MPSN. We also observed that local neighborhood infor- mation is crucial for all tasks, while higher-hop information seems less relevant. We also studied the effect of features of different orders and observed that combining the transformed features from simplices different orders results in a much better performance than using only nodes, edges, triangles, or tetrahedrons. Specifi- cally, for simplicial closure prediction, we observe that the constituent edges of open triangles carry the most crucial information about whether simplex will be formed. This agrees with the observation made in [Benson] jet al. (2018). which states that the tie strengths of the edges an open triangle positively impact its simplicial closure probability. In graph classification, using only higher-order simplices such as triangles and tetrahedrons leads to poor results, possibly due to the small graph sizes with very few higher-order simplices. These limited higher-order simplices fail to capture the graph structures and distinguish between them. More details from the ablation studies are provided in Appendix[]
Additional Insights:
6 CONCLUSIONS
We have presented a class of simple simplicial neural network models, referred to as simplicial-aware neural networks (SaNN), which are based on the precomputation of simplicial features prior to the training process. We theoretically analyzed the expressive power of SaNN models and provided thcoretical conditions under which they discriminate all the simplicial complexes that the SWL test can do. We also provided the conditions under which the class of SaNN models are more powerful than the WL test. We relate the discriminative power of the SaNN models to that of the SWL test by expressing the output of SaNN models as an injective function of the colors assigned by the WL and the SWL tests. We have prescribed viable functions in the SaNN model that result in simplified yet powerful model that is as expressive as the SWL test. We have demonstrated via experiments that SaNN performs on par with the existing SNN models for trajectory prediction, simplicial clo- sure prediction, and graph classification applications on various benchmark datasets. We thereby show through numerical experiments that SaNN models are computationally inexpensive and well-capture the structure of the simplicial complexes.

---

Published as a conference paper at ICLR 2024
7 ACKNOLEDGEMENTS
This research was partially supported by a Qualcomm Innovation Fellowship and by Kotak IISe AI-ML Centre (KIAC).
REFERENCES
A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaic, and J. Kleinberg. Simplicial closure and higher-order link prediction. IEEE Transactions Neural Networks and Learning systems, (3(44))EE112--33 2018.
Bodnar, Frasca, Y. Wang, N. Otter, F. Montufar, Lio, M. Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In Lauren Cowles (ed.), Proceedings of the 38th International Conference on Machine Learning (ICMI. 202/), pp. 1026-1037, Virtual, 2021, Cambridge University Press.
E. Bunch, Q. You, G. Fung, and V. Singh. Simplicial 2-complex convolutional neural nets. arXiv preprint 2012. 06010, 2020.
Chen, Z. Chen, and J. Bruna. On graph neural networks versus graph-augmented ML.Ps. arXiv preprint 2010.15116, 2020.
J. B. Cordonnier and A. Loukas. Extrapolating paths with graph neural networks. arXiv preprint 1903.07518, 2018.
S Doshi and S.P Chepuri. Graph neural networks with parallel neighborhood aggregations for graph classifica- tion. IEEE Transactions on Signal Processing. 70:E11221-33 2022.
Ebli, M. Defferrard, G. Spreemann. Simplicial neural networks. arXiv preprint 2010.03633, 2020.
Errica, M. Podda, Bacciu, and A. Micheli. A fair comparison of graph neural networks for graph clas- sification. In Proceedings of the 8th International Conference on Learning Representations (ICLR), Addis Ababa, Ethiopia, 2020.
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning large graphs. In L. Guyon, U. V. Luxburg. Bengio, Wallach, Fergus, Vishwanathan, and Garnett (eds.), Proceedings of 30th Advances Neural Information Processing Systems (NIPS 2017), CA, USA, 2017. Neural Information Processing Systems Foundation, Inc. (NcurIPS).
A. A. Lehman and B. Weisfeiler. A reduction of graph to canonical form and an algebra arising during this reduction. Nauchno-Tecae Technicheskaya Informatiiya, 2(9): 6, 1968.
K. X. Leskovec and S. Jegelka. How powerful graph neural networks. In Proceedings of the 7th Interna- tional Conference on Learning Representations (ICLR 2019), New Orleans, LA, USA, 2019.
C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. TUDatasct: collection of benchmark datasets for learning with graphs. arXiv preprint 2007,08663, 2020.
A. V. Phan, M. Le Nguyen, Y. L. Nguyen, and L. T. Bui. DGCNN: A convolutional neural network over large-scale labeled graphs. Neural Networks, 108:533 43, 2018.
M. Roddenherry, N. Glaze, and S. Segarra. Principled simplicial neural networks for trajectory prediction. In Lauren Cowles (ed.), Proceedings of the 38th International Conference on Machine Learning (ICML 2021), pp. 9020-9029, Virtual, 2021. Cambridge University Press.
E. Rossi, F. Frasca, B. Chamberlain, D. Eynard, M. Bronstein, and F. Monti. SIGN: Scalable inception graph neural networks. arXiv preprint 0004./1199. 2020.
M. Т. Schaub, A. R. Benson. P. Hor, G. Lippner, and A. Jadbabaie. Random walks simplicial complexes and the normalized hodge l-laplacian. SIAM Review, 62(2):353-91, 2020.
Velickovie, G. Cucurull, A. Casanova, A. Romero, Lio, and Y.Bengio. Graph attention networks. Statistics, 1050(20), 2017.
F. Wu. A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning (ICMI), pp. 6861-6871, California, 2019. PMI.R.
10

---

Published as a conference paper at ICLR 2024
M. Yang. E. Isufi, and G. Leus. Simplicial convolutional neural networks. In Proceedings of the 47th In- ternttional Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8847-8888888 1851, Singapore, 2022a.
R Yang. F Sala, and P Bogdan. Efficient representation learning for higher-order data with simplicial com- plexes. In Learning on Graphs Conference, pp. 13-1, 2022b.
A SIMPLICIAL NEURAL NETWORKS
We introduced the geric model for SNNs in Section 2 Here, we present specific details of the aggregation and transformation functions in equation ( applied in various SNN models. In MPSN, the first term correspond- ing to self-emheddings ignored (i.c., A 0), and the next two terms in [ that aggregate information from the neighboring simplices of the same dimension (here, k) are merged as A H w!!) where A is the sum of the upper and the lower Laplacian matrices B B2 + B Bk+1 or some normalized version of it. MP SN, AR-1 and A441 are B and Bx, respectively. The models SNN (Ebli al. 2020), SCoNE (Rod- denberry et al. (202I). and SCNN (Yang et al.) 2022a) aggregate information from neighboring simplices of the same order, considering only the upper and the lower adjacent simplices (Ax-1 = O and Ax+1 0). SNN ignores self-embeddings, while SCONE, and SCNN consider seff-embeddings to update the embeddings. In SNN, the aggregation and transformation of aggregated features are performed together for upper and lower adjacent simplices as ( (( where A is B, B, + B B However, in SCONE and SCNN, the embeddings aggregated from upper and lower adjacent simplices are transformed separately using two different weight matrices (1(4. and w!(..) respectively, decoupling the information from the types of adjacen- cies. Additionally, SCNN also uses powers of Ax,c and A to aggregate information while SCONE does not. The model SCoNE, on the other hand, is specialized for the task of trajectory prediction and focuses on simplicial awareness, and permutation and orientation equivariance. The combining function & in all the three models MPSN, SNN, and SCoNE is summation. However, in 92CNN (Bunch al. 2020). the combining func- tion concatenation. The model proposed in S2CNN focuses on processing data specifically over 2-simplicial complexes and the aggregations in this model are performed using normalized adjacency matrices defined in (Schaub et al. 2020). It should be noted that in all these SNN models, feature aggregation is performed
sequentially during training, i.c., the embedding matrix in the (L + 1)th layer, denoted by H H((+1, is computed
by aggregating the product of the embedding matrices in the /th layer, namely, H H and H 4 and the
(())
associated learnable matrices in (I]. This increases the training time significantly [cf.. Fig. 33. All baseline
methods, including MP SN, SCNN, SCoNe, and S2CNN, exhibit simplicial awareness as they utilize the powers of lower-adjacent matrices, upper-adjacent matrices, or Hodge Laplacian matrices, none of which approach zero. However, except for MPSN, SN, these baselines do not match the SWL test in terms of expressivity, as they do not account for feature aggregation from boundary and coboundary simplices, which is considered by the SWL test. Furthermore, since the baselines other than MPSN do not consider aggregation from coboundary simplices, the node embeddings from these models cannot be shown be more expressive than those from the WL test. We summarize the properties of SaNN and the existing SNN models as follows:
Aggregations Precomputed
More expressive than WL As expressiie as SWI. Simplicial awareness
SaNN MB SN
Sequential
ScoNa SCNN
Sequential
Sequential
B COMPARISON OF COMPUTATIONAL COMPLEXITIE, OF SNNS AND SANN
Since we use MLPs to learn from simplicial-aware features, the computational complexity of the proposed SaNN is of the order of computational complexity of MLPs and constant with respect to the number of sim- plices.
The time complexity of aggregating the neighboring attributes of l--implices during the training of gen- eral SNN model as in [1] with T layers is about OTT(2N3 D3 + N&NNe-DD-L + NeN++1De+1) for simplicial complex with N₂ k-simplices with each k-simplex having Dz-ddimensional attributes. The time complexity involved in transforming the aggregated features is about (T D + N₂ N + N₂ ()+)). Here. for simplicity, we assume De-dimensional features in all the hidden layers corresponding to generat- ing embeddings of k-simplices. Therefore, the overall time complexity of the existing SNN models is about ((N NeNN-1 Dz-1 NNNNNe Dx41) (3N, DJ + + .)).. which dominated by the first term containing 2N Da, N₂. Ng-1 DE-1, and N₂ N&+1 Da+ 1, corresponding to feature aggregation in every layer.
11

---

Published as a conference paper at ICLR 2024
The proposed SaNN model performs neighborhood aggregations beforehand, and therefore, its computa- tional complexity during training is only due the transformation of pre-computed features. Specifically, an SaNN model capturing information from O,..., Thop neighborhood k-simplices has a time complexity of (TT(3,,, D + N₂ N.D + Nı D)+1)), which is negligibly small when compared to the computational complexity of the existing SNN models. This is also reflected in the run-time measurements in Fig.
C THE SWL TEST
The simplicial Weisfeiler-Lehmen (SWL.) test is an iterative algorithm that assigns colors to all the simplices in a simplicial complex by updating the colors of simplices through neighborhood feature aggregation. The details of the algorithm are as follows. Consider two K K-simplicial comlexes 1c and K22. Let the colors assigned by the SWI. algorithm in
iteration a simplex ett) (f + 1)th iteration the SWL algorithm, each simplex in the two simplicial complexes is assigned a tuple containing the old compressed lahel of the simplex cp and the following multisets
( = ( TE (EB()))))
c (() (c,") TEE cc
( [(c ( r EE and & (a, (0) ((e.) ) E (a) and ó (a,T),
namely. the multisets containing the compressed labels of the boundary adjacent, co-boundary adjacent, lower adjacent, and upper adjacent neighbors of the simplex, respectively, in the tth iteration. A new color is then generated by passing the tuple e!')
(t)) (t)) (o), cl (o), oZ (a), ( ( (o) through HASH function as
(+ HASH (
(10)
Any two simplices with the same tuple 25 will get the same updated color. The algorithm terminated the histogram of partitions of simplices partitioned by colors diverges between the two simplicial complexes, and that case, the simplicial complexes not isomorphic. is shown [4] that MP SN is strictly more powerful than the WL test and is as powerful the SWL test if the neighborhood aggregator functions injective.
D PROOF OF THEOREM
Throughout the preafs, we use Sur to represent S [o] and h to represent ( whenever the order is clear from the context, for notational convenience.
Lemma D.I. For graph G (V,E), the update of WL coloring of node V iteration T be represented by the following equation
(T) ==) (1 : {:0) (0)
V (1)) (w))
(11)
where o(.) is injective function and (10) (u) denotes the set upper adjacent t-hop neighbors of node u.
Proof. We show, by induction, that the update of the WL coloring of node E V at iteration I is given by (T]. The base case, i.c. when t = 0. trivially holds as the WL coloring of node u is (0) Let us assume that the update of WI. coloring at the (f - 11)th iteration can be represented by the following equation
(t-1)
Φ ( { VT (u), (t-" (w))
for injective function do. By definition, the update of WL. coloring (Lehman Weisfeiler 1968 of node E is given by
= HASH (cl-)) fo " vj Vje
(12)
where HASH is an injective function. Using the induction hypothesis,
12 can be written
(1) HASH (0o (0) { Vr (2 (w)...,
" (w)))).
{ 0o (c f40) ( VT (). ... u --- vi (w))
(13)
12

---

Published as a conference paper at ICLR 2024
As HASH and injective functions, can express
13
2 + (cl.)) (ct)) Yr (o).... .ul uu (w))
44 vre ()........ P()) (weu
a ( (0t) vr (10) (0) an p(0)) {
for vre v (0)) (1).., ..0)
= {<( (c))) (1))) Vre (t0) (o), ao (11))
(14)
for some function Φb Since @ is composition injective multiset functions, it is injective. By induction, the update of WL coloring of node at the I I'th iteration is given by
Lemma D.2. SaNN is atleast as powerful as the WL test distinguishing non-isomorphic graphs when using a clique-come complex lifting if all the functions involved in generating the node embeddings. namely, (o,(())o.c)))))) (.).. 1 (). and On(.) for L O....,T. are injective.
Proof. Let Kn and K2 be two K K-simplicial complexes. Let the embeddings assigned by SaNN to the nodes (0-simplices) u E Kr and E K2 be denoted by h. and h, and the WL coloring at the two nodes be denoted by Cu and Co. We show that for all simplicial complexes K1 and K2 and for all the nodes E K and K2, h. hy implies c, ce- This proves that the WL isomorphism test fails assign different embeddings to different nodes wherever SaNN fails. other words, SaNN is atleast as powerful as the WL test in distinguishing non con-isomorphic graphs.
Let us denote the T- hop neighborhood information capturing node embedding of node w generated using SaNN for graph with clique-complex lifting by
h Oo
(0)
(T)
(15)
where sw = =66 (o (foze (x((1) (x fo.c (xfc(wi)) for E to.....t...
We now prove that the WL coloring of two nodes u E Ki and E K2 is the same whenever SaNN assigns same embeddings to the nodes. With the assumption that Oo To os fou and fo.c, Vt E to,..., ,,, are injective, (T) can be written
(1)
h (2) -o (26") ) (o (Fom (xox(((22 ....,,9"'
TT (+ (Fow (Zidlwi) forc (xiT2lw)) (wl((w) ())d( {44) Vr 20 (w)) xx(2
= (c {:4%, VT f E (w) x(1) []].........
(16)
where Ou is a composition of injective functions and therefore is an injective function itself. Here, the second equality follows because of the assumption that the WL coloring of nodes is initialized with the input features the nodes (00) Xo[w]. If the node embeddings of the nodes and are equal, i..., if h h.)) (
{ 1 W E (TTT (w) } x [w)) for u and w v, equal since Oo is an injective function. From Lemma D.I notice that the tuples (o er V+ (2(() (w),... (T( (w:) }} for = u and us = v, respectively, are the arguments that the WL HASH function takes as input to compute the colors of the nodes u and at iteration T', By the equality of these tuples, we obtain e!T) = (T)
10) V FTEu(M (( (w) } x(() [x]. g
the tuple of inputs, i.c.. Cw L
The above lemma shows that through its node level embeddings. SaNN distinguishes all the simplicial com- plexes that the WL test can distinguish through its colors. We have, however, ignored the information from higher-order embeddings that S SaNN incorporates through co-boundary adjacencies. These embeddings can add more information and help differentiate graphs better. Since it is proved that SaNN is atlcast as powerful as the WL test in distinguishing non -on-isomopp graphs, it now sufficient to show an example of pair of graphs for which the WL test fails to distinguish but the higher-order information the graphs. Fig. shows an example of such a pair of graphs. The histogram of colors assigned by the WL lest and the histogram of embeddings assigned by SaNN at the first three iterations are shown next to the two graphs. The histogram of colors assigned by the WL test to both the graphs are the same. However, SaNN with T 3, i.e., with 2-hop neighborhood aggregation, generates different embeddings to the two graphs. This because for the graph in Fig. (a)). SaNN incorporates the information from four triangles in the 2-hop co-boundary of the orange nodes, while in Fig. b), there is only one triangle in the 2-hop neighbood of the orange nodes, e proved that SaNN is atleast as powerful as the WL test and have now shown an example where the WI. test fails to distinguish a pair of graphs that SaNN correctly distinguishes being two different graphs. This proves that SaNN more powerful than the WT. test in distinguishing non-isomorphic graphs.
SaNN enables
differentiate
13

---

Published as a conference paper at ICLR 2024
E PROOF OF THEOREM 4.2
To prove Theorem 4.2, we first present simpler alternative update the SWL coloring (Bodnar al. 2021 without sacrificing the expressive power of the SWL test (more details about the test are in Appendix C
Lemma E.1. For simplicial complex K., the update of SWL coloring of a simplex a E K at iteration can be represented by the following equation
es es A4 fef-.vse (o) 40 (. v. (ej., (s V
(17)
for some injective function db.
Proof. Let us denote the iterative coloring algorithm whose update expression in the tth update is 17 by SWL-1p. We prove the equivalence in expressive powers of SWL-t and the SWL test (Bodnar et al. 202 by proving that SWL--1 is as expressive as MPSN, which is proved have the same expressive power as the SWL test presented in Bodnar et al. (2021).
The expression for the embeddings of simplex a obtained using t-layers of SN given by
(t+1) U (zl² mg (a), ml (o),m² (o),
(o), ml (o))
2
(18)
where
my (a) = AGGres(e) (ms (x!) (x(),2(0)) (o) (((o)=AA)) AGG (mc (x(")x()))
(0)
m2 10 (a) AGGrE (mc ( (-) =(/h)) m/f ((((()) (o) AGGrEm(,) (mu (2 (0) (0))) ())))
Here, Zouy denotes the embedding of the simplex that is jointly coboundary adjacent and j. The functions ma, me, me and a with one of their boundary adjacent, coboundary adjacent, lower jacent and the common houndary adjacent, and upper adjacent and the common cohoundary adjacent sim- plices, respectively. These combined embeddings from all the simplices in the boundary adjacent, cobound- ary adjacent, lower adjacent, and upper adjacent neighborhood of are aggregated using the functions AGG,eB()) AGG.reBo).AGGGrreee AGGrec(o))
and and Zunj
denotes that of the simplex that is jointly boundary adjacent my combine the self-embedding
AGG+eL(o) and AGGrsu(o). respectively. The function U outputs the final embedding of a by taking into account the previous color of the simplex, and the aggregated embeddings ((+1) (a), me mg
(t41) (a), m (t+1) (a), and my (1+1)(())
(o).
is proved in Bodnar et al. (202I) that MP SN with injective aggregators and combining functions as powerful as the SWL test. It is further shown in Bodnar et al. (2021) that the following simplified version of the model, obtained by dropping off few adjacencies, is equally expressive:
2
(1+1)
(1) mg
(1) (o).my m (1)(()))))
my
(20)
Taking all the aggregators and combining functions in (18) and 19) to be injective, we can compactly represent the output of MPSN at the (th layer
(1+1) = (20) {<e 26
VAG)) th vj (()) E Vj (())))
(21)
where A(a) (B(o), C(a), L(o), and is injective function. Here, we used the fact that the composition of injective functions is injective. Similarly, we can express the equally expressive but simplified version of MP
MPSN SN given in (20) as
(t) VJE V A(O)) Enl Vj E(())) (++1) = 3 ((()) 2
(22)
where A(r) ((()), and ă is injective function. Using these representations of the two alternative definitions of the MP SN model, we now prove that SWL-1 and MPSN have equal expressiveness.
To prove that SWL- and MN are equally expressive, we first prove that MPSN SN fails to distinguish two simplices, SWL-1 also fails to distinguish the two simplices. We then prove that if SWL-1 fails to distinguish two simplices, MPSN also fails to distinguish the two simplices to prove the equivalence in their expressiveness.
Consider two k-simplices and in two simplicial complexes K2 and K2, Let denote the color assigned by SWL-v to a k-simplex a at L = Tih iteration by (P)) and the embedding obtained using / = T T-layers of MP SN by (T) We now prove that if 2 = z(" base case, i.c., for t = 0, since initial embeddings for both SWL-16 and MPSN are the initial features the simplices.
(T) then (T) = (T) by induction. This trivially holds for the
14

---

Published as a conference paper at ICLR 2024
Assume that if 2b =t? then cg cg This, from 21 means that the tuple of inputs to MPSN for obtaining the embeddings a and T, denoted by
(t) La
Vj e A(a)D. vA(a) Eu Vj [(a) (=lh) Vj E((a))) {Ee))
is equal for a = a and since 8 is injective function. By the induction hypothesis, we get
1 { (e Vj e A(o) A &e Vj E L(o) &e.... Vj E(())))
and a = т. Since subset these two tuples, namely, ( (te)" Vj A(a) v.Aaa) }} for (a, go as input to SWL-1, we see that SWL-U takes the same set of inputs for updating the colors of a and r and therefore, outputs the same colors do (t+1) and ((++1)
equal for a
By induction, if 2.. (m) = t then (2) = =c, (2)
To complete the proof, we now prove that if SWL-1 fails to distinguish two simplices, MFSN will also fail to distinguish the two simplices, i.c., if c = (T) then x!²) = x! We prove this, again, by induction. The base case, which says that if ce = (0) then 20 = (0) trivially holds. Assume that if c c. then w (0) holds. of ( we have that the tuple of inputs to SWL-0 to compute 2 and ( are equal Vj E A(a)), v-A(a) }}
[ef. 17 1. By the induction hypothesis, this implies that [za [z]])
is equal for and = T. To prove that 2 (t+1) zi ((+1), we observe from 22 that we should prove that the inputs Vj E A(a)}, V YA(a)) } Aelly viEu(a)B) for
equal. Since have already proved that (z) { (2))) VJE v((o) for a = a and a = r are equal, the only
and
unknown equivalence is that of the multisets fz Vj E u(a) J for a and a T.
To prove that 2 = (*+1) it is, therefore, sufficient to show that the multisets {z.by: Vj E U(a) B. for a and a = r are equal. The colors in these multisets correspond to the coboundary adjacent simplices of a and r, which are also jointly coboundary adjacent to their upper adjacent simplices. Since we have already proved that the multisets of colors of coboundary adjacent simplices of a and T are equal, we need to only show that the multiplicity of the color of each coboundary simplex from the two multiscts is the same.
For a l-simplex a, the color corresponding each coboundary simplex of appears exactly k ++ times in (z(") Yj E {.a).. For example, for 1-simplex (edge), the color of each coboundary 2-simplex (triangle) included in update through { auy: Vj E [(a)] every time its corresponding upper adjacent edges are included. Since the number of upper adjacent edges sharing a particular triangle with a is 2, the color of the particular triangle will be included twice. This is true for any coboundary adjacent triangle. Generalizing this to k-simplices, k-simplices and are included in {x Vj E U(a)) } is l + for a and
know that the number of times cach of the coboundary adjacent simplices of the two
This proves the and = T. Therefore, the inputs MP equivalence of the two multisets a Vj E U((a) for ((+1) and zt (1+1) will be the same. By induction are the same [ef. (,2) and hence the outputs, denoted by zi c
(1) = c (T) implies 2z (T) =x?")
( then ( 2T) This proves that SWL.-t is as expressive as MP SN and hence, will serve as a simpler alternative to the SWL test.
We proved that (T) (T), then (TT) (T), and ( =d
Lemma E.2. For a simplicial complex K. the update of SWL coloring of simplex a E KC at iteration T can be represented by the following equation
m = + (000 lll (0) V
A (0) v. v J.
(23)
where A0 (B)) (o) c ( for some injective function ó.
Proof. We show that the update of the SWL- coloring, cquivalently, the SWL coloring, a simplex e KC iteration T is given by the equation in Lemma by induction. The base case, i.e., when = 0, trivially holds as the SWL coloring of simplex o is (0) Let us assume that the update of SWL coloring at the (t - 1)th iteration can be represented by the following equation
h-" =- (0 (1)) {ll (0)
(0, Vr (o)
V vi= fii...... 1.....t-11. -1])
(24)
15

---

Published as a conference paper at ICLR 2024
for some injective function c. Using the induction hypothesis, 17 be expanded by substituting 24 Substituting (24) in the sccond term of (17 results
{ 0 D. (o) {ot ( 111 vre (o)) (m) vin l.....,-- 1}) vje
It can be simplified further by using some injective function o as
{ "0 Ae ( (f
v ( { +.) v e (B(4 V } vi= 1......-11
By substituting
(B)) A with ((+ (o). we obtain
{ { (1 Vje Vjje (f
B Bd (o) } {{ Vre .i Lii=.....t-1f
We repreat the procedure for the other terms in 17 to obtain the following expression for cg
e HASH (0 00) Hll .ee..VEEAA ( (. vi= Vi=l...... 1......-11]
{ (L V A" ((<VreA4()))
( VT E vd vi 1, 1..,t-.. -1))
(25)
Since d and é are injective, we futher simplify the expression for (t)
c = (0) {{E
c Vr E ( v vi= 1......))
(26)
for some function (.), which a composition of injective functions and hence is injective. By induction, the update of the SWL coloring of simplex at the I'th iteration is given by the equation in Lemma E.2
Lemma E.3. SaNN is at most as powerful as the SWL test in distinguishing non-isomorphic simplicial com- plexes.
Proof. Let 11 and K2 be two K-simplicial complexes. Let the embeddings assigned by SaNN to the simplices E K1 and K2 he denoted by h, and h, and the SWL coloring the two simplices be denoted by co and K2,, Go = Cr implics h = h,- With this, prove that
Cr. We show that for all the simplices a E K1 and SaNN fails to assign different embeddings to different nodes wherever SWI. isomorphism test fails. other words, SaNN is at most as powerful as the SWL test in distinguishing non-isomorphic simplicial complexes.
From Lomma F.2 the update of SWL coloring of k-simplex a in an K-simplicial complex K., at iteration T can be represented by the following equation
(T) = (c {ll 4o) A v vi= vi==I...,TTT] .T...
(27)
where (6-) is some injective function.
The embedding of a k-simplex a E K. generated using Sa NN capturing information from T-hop neighhorhond,
denoted by h (?) is given by
h 0x (s ....,,??)) -s
(28)
where
56 =09) ( (Fau (xhielo) frLC (z (Zhecol) fk.s (x(() (x FR.C (x(() (z)t)clo)))
for i TT.
We now prove that by capturing information from T-hop neighborhood for simplices of each order, SANN assigns same embeddings two k-simplices σ E K, and 022 E I2 the SWL coloring of the simplices is the same at the Tth iteration. Let us assume that the SWL coloring of two simplices, σi and 02 after T iterations are equal, i.c., of cos This, from Lemma E.2 implics that the tuple of inputs,
Ull 49 Vr E (o) v. }. vi 1, 1.::....,))
for 02 and 02 equal. However, these are the input arguments to generate the SaNN embeddings of simplices and using 28
Therefore, obtain h!T) h
16

---

Published as a conference paper at ICLR 2024
As we have already shown that SaNN at most powerful the SWL test in Lemma E.3 it now sufficient show that SANN least as powerful the SWL test under the condition that the functions involved in generating the embeddings are injective, to show that it is as powerful as SWL. We therefore show that if the functions fa.u( (.) (t) (,,(())) o()). ( and Ox(+) for & E O,..., T' and E O.....A are injective, ) has implies 6or = do2
When the functions involved in generating the embeddings are injective, we can simplify the embeddings of a simplex a of order ls as follows
h
Ox (0h (0(' (o (Fuu (Zlulol) , fu.c (xl.clot) fu.s (x (x fa.e (x (xituclo))) Vt rr......,,
= A (f (xxuul)) X.. (o.ccoo)% (21.0)) 2. X J. V1 yeEo....,.7
A (ffe Vre e A (o)) V VtEO......)
(29)
for some injective function A(-).
Let us now assume h = h This implies that the tuples of inputs
(f cr, Vr E (0) v. }. Vt Vt.e....,,
for a = σ1 and o = d2 are equal. Since these are the input arguments to compute the SWL coloring updates of the simplices σ₁ and 02 at the Tth iteration, we obtain (7) caz
F REMARK ON INJECTIVITY OF DEGREE-BASED WEIGHTED SUMMATION
Here, we give generalized case where the degree- based weighted sum aggregator is not injective. That is, we provide a case where the proposed architecture assigns the same partial updates to s-mimllicss in simplicial complexes with different structures.
Remark 1. Suppose all the k-simplices in a simplicial complex have the same mumber of upper (respec- rively, lower, boundary, and co ---ounddrr) adjacent neighbors, then refer to this structure as upper (re- spectively, lower, boundary, and co-boundary) k--reulaar simplicial complex. Consider two upper (respectively, lower, boundary, and co-boundary) k--regllar K K-simplicial complexes K2 and K2. Let TKK,44 (respectively,
(k)) (kk) B. and ek for i == 1, denote the number of upper (respectively, lower, boundary, and co- boundary) udjacent simplices of all the k-simplices in Kr. Assume that for the two simplicial complexes, the (k)
nKK,e, e.K.e.K
(M) (k) # "K2a (respectively, T. "K2.c. input features of all the k-simplices are the same. When "Kia (k)
(R)
18 # 1x22.B and C * n)g.c).. ). the structures of the two simplicial complexes are different. However, the partial embeddings of k-simplices obtained by upper (respectively, lower, boundary, and co-boundary) neighborhood aggregation using normalized incidence matrices defined above for the two non con-isomorppic sim- plicial complexes will be the same.
Let consider illustrative example to better understand the above remark. The two simplicial complexes (2) 2. The simplicial complex in Fig. (a) has tetrahedron, each face of which is triangle with three lower adjacent triangles. All the other triangles Fig. (a) also have three lower adjacent triangles. All the triangles Fig. (b)) have two lower adjacent triangles. Assume that the features over the 2-simplices are all a. Despite having different structures, the partial embeddings of all the 2 2-simplices aggregated from their lower adjacent neighbors in the two non-isomorphic simplicial complexes are if degree-based weighted summation aggregator is used.
in Fig. are lower 2-regular simplicial complexes with _x 3 and Tigg,e
For the case in Remark given the injectivity of d. the proposed architecture assigns the same histogram of k-simplicial embeddings to the two simplicial complexes the two simplicial complexes are simultaneously upper regular, lower regular, boundary regular, and co- bouudad regular. Even if the two simplicial complexes do not have the regular structure along one kind of neighborhood, i.c., upper, lower, boundary, or co-boundary, the proposed architecture will be able to distinguish the two structures based on that kind of neighborhood. For example, consider the lower 2-regular simplicial complexes in Fig. 5 Any of the triangles, say 71, in the tetrahedron will be assigned the same partial embedding as any of the other triangles in Fig.5 say σi, and as any of the triangles in Fig. (b)),, say d2 after aggregation from lower adjacent simplices. However, the partial embedding computed by aggregating information from the upper adjacent triangles helps SaNN assign a differ- ent partial embedding the triangles in the tetrahedron, thereby assigning different final embeddings to 71 and da (or 0z). spite of assigning the same lower adjacent neighborhood aggregated partial embeddings. SaNN will, therefore, be able to distinguish the two simplicial complexes with the degree-based weighted summation aggregator using the histogram of embeddings of only the 2-simplices. The cases where the simplicial com- plexes are regular along all kinds of neighborhonds for simplices of all orders are very rare and -aseee-hhsed weighted summation is, therefore, almost always injective.
17

---

Published as a conference paper at ICLR 2024
G PROOFS OF PROPERTIES OF SANN
Here, we prove the properties of SaNN presented in Section 4.2
G.1 PERMUTATION EQUIVARIANCE
Consider K K-simplical complex K. Let define set of permutation matrices p (Po..... Pk) act- ing on the input feature matrices X = {X, E xx 1K and the boundary matrices B {Bu E The permuted input features are represented by PX .PoX.....,PPy PxXx) (PoB, ...... Px-1
R 1xMx jk=-- 1
permuted boundary matrices are represented by PBP" that if the input features to SaNN are permuted using P. SaNN produces an output that is permuted by the same permutation P. Mathematically. if the embedding matrices of k-simplices combined from different hops of neighborhood output by SaNN are denoted by SaNN(X, B) = (H₃ E RNxx 1/ jk=o. we show that SPN, PBP") (S,NN(X, B) = PH (Pa PxHR).
BPk). We now prove
The aggregated feature matrix of k-dimensional simplex output by the tth branch of SaNN corre sponding to t-hop neighborhood aggregation is given by
Proof.
x (1)
( (1-1) Ax. AL-L8X (1-1) 1
(1-),
(30)
where E (I,...,T) E "O....,,K' }. and the operators are as defined in Section of the manuscript. first prove that if the input features to SaNN are permuted using P, then the 1-hop aggregated features are permuted by the same P. We then prove, by induction, that if the input features to SaNN are permuted using P. then the aggregated features of any depth are permuted by the same P.
For the base case, when t the aggregated feature matrix output by 1-hop neighbourhood aggregation when the input is (PX, PBP" T is the following
x = (P, P (P,Xx), (PA P BaP.), (PxX.),
(P.B.PT-) (Pa-
(Pa- -
(P. (P.Ba.IPHH)) (PetiXet))
P& Xx P PBB B, P. PrBatIX
Ps B X. B B.X., B, BetiXet1]
(31)
for = O...., K. Second equality achieved using fact that P&P I, E O....,K. K. This shows that when inputs R N&Nxx DD 3 = also permuted by the same set of permutation matrices.
are permuted by set of matrices P. 1-hop aggregated features (x()
Let
that when the inputs X and B permuted by the set of matrices P, the (t 1 aggregated also permuted by the PaX((-); Using the induction hypothesis, the aggregated feature matrix output by t-hop neighbourhood aggregation when input (PX, PBP") the following
features (X(-1) Ne K Jizo
of permutation matrices, i.e., {((-))
x [Pa P 6+1
P
B c+1 P! (X (X((-)),
Pa (x(-"),
(P.B.P
(P, (x("))
= [
P
P
B
P
( )) P.P (P:x
(P.B.PT
T
(P.
(Prn
P.
x (-11)
P.
P.
P,B
P. ()
b+l
P.
B
B
"
B.x
-P.X(0)
(32)
18

---

Published as a conference paper at ICLR 2024
where the second equality follows from the induction hypothesis. This proves that the neighborhood aggrega- tion SaNN permutation equivariant.
Recall that choose the transformation functtios (-) to be MLPs and the functions that combine beddings different hops, i.e.. (+(-). ) to be concatenation. Both of these operations preserve permutation equivariance and since SaNN is a composition of the permutation equivariant neighborhood aggregation, MLPs and concatenation, it is permutation equivariant.
G.2 ORIENTATION EQUIVARIANCE
Consider a K K-simplical complex K. The change orientation simplex refers to an orientation rever- sal of a simplex with respect to the neighboring simplices. This can be represented by multiplying the fea- ture vector on the simplex, and the rows and columns corresponding to the simplex in the boundary ma- trices with -1. To define the change orientations, fine set of matrices
in the case of permutation equivariance, let de- (Ou,-. ...., Ox) acting on the input feature matrices and the boundary matri- ces. The matrices Oz, vk O...., K are diagonal matrices with (i, i)th entry equal to -1 if the orien- tation of the ith simplex of dimension & is reversed or is equal to 1 otherwise. The input features with change in orientation represented by OX (O.Xo,.... Og and the boundary matrices modi- fied due the orientation changes represented by OBO" (O,BiO), ....., Ox Ox-IBO)) Mathe- matically, show that SaNN(OX, OBO") OsaNN(X, B) = OH (O, OxHx) where SaNN(X, B) (Ha E Ne D are the combined embedding matrices of i-simplices from different depths output by SaNN.
Proof. The aggregated feature matrix of k-dimensional simplex output by the tth branch of SaNN sponding to t-hop neighborhood aggregation given by (30). We first prove that if orientations the input features to Sa NN are modified using O then the orientations of the 1-hop aggregated features are changed hy the same O We then prove, by induction, that if the orientations of the input features are changed using O, then the orientations of the aggregated features of any depth permuted by the same O.
For the base case, when the aggregated feature matrix output by 1-hop neighbourhood aggregation when the input (OX, OBO") ) the following
x = [O,, 0c (O.)))
(OxX.),
O (0--0 (0
BB O. I.
O2 B B B
x
(33)
for k: 0,..., K. Second equality achieved using the fact that O²O,T I O,..., when the inputs X and B changed to OX and OBO", the orientations of the 1-hop aggregated features x(" E I N K are also altered by the same set of matrices.
K....,,. K. This shows that
Let us assume that when the inputs are OX and OBOT. the (L - 1)-hop aggregated features (x( (t-) xNNxD,, 1K are also altered hy the same set of matrices, i.c., X O (l-1) x(-1), Using the induc-
tion hypothesis, the aggregated feature matrix output by t-hop neighhourhood aggregation when the input
19

---

Published as a conference paper at ICLR 2024
(OX,OBO") is the following
_ = OO. Oz 0..
(x,") (x!-)),,
= (1 (x(-))
(0,x,
(O. 0 (0-0) (0, (0+
= O, B (1-1) O.B xx 1
(t-1))
Og B B
X _-" B. B, X B
(34)
where the second equality follows from the induction hypothesis. This proves that the neighborhood aggrega- tion in SaNN is orientation equivariant.
Recall that we choose the transformation functions (-) to be MLPs and the functions that combine em- beddings from different hops, i.e.. (x(-), to be concatenation. Without loss of generality, assume that the feature transformation functions are two-layered MLPs. The final output embedding matrices of k-dimensional simplices Hę can be written as
H
(0)
77.0
(0)
X
R,O
Wf.))
M6.1
(T)
11.00
(T)
X
K.0
1k,1
(0)
O
(())
k.0
w
Oxx
w!!)
(35)
for some learnable weight matrices (-()) k.z and activation functions The Vk O..... K, 0, Ti== 1.
The linear transformation part of MLP is clearly orientation equivariant. The non-linear activation part an MLP is orientation equivariant only it is odd. Specifically, if an activation function 17 is odd, then (OA) = Oy)(A) for all matrices A of appropriate dimension, and any diagonal matrix O with diagonal entries as 1 or -1. Therefore, H& simplifies to
H
M1..1
O 11.00
((()) 8.0
( w
Mh.1
((TE
(T)
X ( w w
Ox
1k,1
1k.0
(0)
(0)
4.0
(0)
(T)
X (
O
Nh.1
M1.o
(0)
X
w-
k.D
w:
(T)
X
(T
w
Og
(36)
This proves orientation equivariance of SaNN.
H EXPERIMENTAL SETUP AND DATASETS
The experimental setup for the three tasks considered discussed here. For fair computational comparison, the same predictive models, hyperparameters, namely depth (T), order (K), and hidden dimensions, were utilized for all the baseline SNN models.
H.1 TRAJECTORY PREDICTION
For each dataset in trajectory prediction experiments, assign to each trajectory attribute of dimension the the number of edges in the entire simplicial complex corresponding that dataset. The ith entry of the trajectory attribute vector
the ith edge not a part of trajectory, and has an orientation same as that of the trajectory, and is -1 if it part of the trajectory but has an opposite orientation relative to that of the trajectory. We then aggregate the features of upper and lower neighborhood edges from different hops as discussed in Section V in the manuscript using normalized incidence matrices. We perform 80% 20% split of the data for training and testing purposes. We 5-fold valsdaaaio for
is part of the trajectory
20

---

Published as a conference paper at ICLR 2024
evaluating the performance of each of the deep models considered including SANN. The model is trained three times on data corresponding to each of the 5 folds to eliminate any weight initialization biases.
To use the edge embeddings learnt using SaNN to perform trajectory prediction, we map the embeddings from the vector space of edge embeddings to the vector space of node embeddings by multiplying them by the incidence matrix B E N xNo, We consider the node embeddings of only those nodes that have a possibility of being the next in the trajectory, which are the neighboring nodes of the last node in a trajectory. For a trajectory f, which ends at node we masking function extract the embeddings corresponding to the neighboring nodes of the node We do this for node embeddings from different depths and combine them using an injective readout function, specifically. concatenation. We then give the combined node embeddings as input to a decoder MLP which maps the node embeddings to a vector space of dimension same as the maximum number of neighboring nodes of the last node in any trajectory in the dataset. The last layer of the decoder is softmax activation function, the output of which for trajectory is vector containing the probabilities with which the neighboring nodes the trajectory's 's node become the successor node of that trajectory. For all the datasets, we train SaNN in a supervised manner using the cross-entropy loss function. We implement early stopping while training, i.c., terminate the training process if there is no significant gain in the validation accuracy after certain number of training epochs. It is established that ensuring that the models are orientation equivariant enhances their trajectory prediction performance (Raddenberry al. 202T). We, therefore, use tanh activation function in all the layers of SaNN and all the other existing SNN variants [c.f. Section
Details of the datasets used in trajectory prediction experiments, namely, the number of nodes, edges, and triangles, in the simplicial complexes, number of trajectories in the datasets and the average length of the traeectories, are summarized in Table
Table 4: Trajectory prediction dataset details.
DATASET
NODES
EDGES
TRIANGLES
PATHS
AvG. PATH LENGTH
OCEAN
133
320
186
160
5.73
SYNTHETIC
400
1001
649
800
8,20
PLANAR
500
2857
5842
3306
2.96
MESH
400
1482
1444
3311
3.18
The hyperparameters associated with trajectory prediction experiments, namely, batch size, number of branches, given by (T + 1), used in the computation of features of edges from different hops, hidden di- mensions of edge representations the MLP for transforming edge features (denoted by T) and the decoder MLP (denoted by D), learning rate, La regularization parameters, are summarized Table[3]
Table 5: Hyperparameters of SaNN set for trajectory prediction experiments.
BRANCHES (T' (1+1)
HIDDEN DIMENSIONS
LEARNING RATE
1/2 REGULARIZATION
DATASET
BATCH SIZE
T2(320,320,320,33
OCEAN
32
3
10-3
10-4
13(133.133.133.6
T:(1001, 1001,, 1001,
SYNTHETIC
3
D::4400,400, 400, 13)
10
10-4
T:(2857, 2877,8857,288. 2857, 2857)
PLANAR
3
10-5
10-4
D=(500,500, 500,5
T:(1 1482, 1482)
MESH
16
3
10-5
10-4
D: 2P.4004400.400.
H.2 SIMPLICIAL CLOSURE PREDICTION
The list all the open triangles in the simplicial complex formed 80% time instances in datasets and the corresponding labels of whether they get closed by the time the entire simplicial complex is formed will form the data. We perform 60% 20% 20% split of the data for training. validation, and testing. For all simplicial closure prediction experiments, we consider the initial features simplices as the sum of the features aggregated from their upper and lower adjacent simplices.
21

---

Published as a conference paper at ICLR 2024
To perform simplicial closure prediction for triangles, we concatenate the embeddings of the constituent nodes and edges in the open triangles the training set learnt using SaNN. The concatenated embeddings are given as input to a decoder MLP with a sigmoid activation function in the last layer, the output of which is the probability of the open triangles forming a simplex. For all the datasets, we train SaNN in supervised manner using the binary cross-entropy loss function. We implement early stopping while training. Since the datasets heavily skewed with many negative examples (open triangles that never get closed) than positive examples (open triangles that get closed), we perform oversampling of the positive examples in each training batch and use a weight for positive examples in the binary cross- eros-- loss function.
Details of the datasets used in simplicial closure prediction experiments, namely, the number of nodes, edges, and triangles, in the simplicial complexes, and the number of open triangles in the training data, are summarized in Table f
Table 6: Simplicial closure prediction dataset details.
DATASET
O-SIMPLICES
1-SIMPLICES
2-SIMPLICES
OPEN TRIANGLES
EMAIL-ENRON
142
1655
6095
2574
CONTACT-HICH SEATT-IGG--SCCHOEE SCHOOL
327
5818
2370
25056
CONTACT- PRIMARY-SCHOOL
242
8317
5139
80446
WDC-CLASSER TAGS-MATH-SS
1161
6222
31477
7439
1629
91685
249548
1960269
The hyperparameters associated with simplicial closure prediction experiments. namely, batch size, number of branches (T + 1) used in the computation of features of cach of the K = 2 different dimensional simplices, namely, nodes and edges, hidden dimensions of node and edge representations in the MI. for transforming edge features (denoted by T) and the decoder MLP (denoted by D), learning rate, T.2 regularization parameters, and the weight assigned to positive examples the cross-entropy loss function, are summarized Table 7
Table 7: Hyperparameters of SaNN set for simplicial closure prediction experiments.
BRANCHES
HIDDEN DIMENSIONS
LEARNING RATE
WEIGHT POSITIVE EXAMPLES
BATCH
(K (T 1))
REGULARIZATION
EMAIL-ENRON
32
2
(((6.644644
D:(6-111)
10
10-3
CONTACT-HIGH-SCHOO
32
2
T:(32.32)
D:(64,1)
10
10-6
3
T:(32.32.32.32)
CONPACT--MIMARY-SCHII
2x3
D:(64,64,64,1|
10"*
T:(32.32.32)
NDC-CLASSES
32
2x3
D:[64.64.1)
10
10
TAGS-MATH-SX
32
2
D:(61.64164411
(:(32,32)
10
10-3
H.3 GRAPH CLASSIFICATION
We lift the graphs in all the graph classification datasets to simplicial complexes by considering 3-cliques as 2-simplices. For all the graph classification experiments, we input node attributes as suggested by Erricca al. 22000 and input attributes of higher-order simplices all-one vectors of the same dimension the respective node attributes. 10-fold cross-validation. Within data corresponding to each fold, we holdout 10% for validation and use the rest for training. The model is trained three times on data corresponding to cach of the 10 folds to climinate any weight initialization biases. Details of the datasets used in graph classification experiments, namely, the number of graphs in the dataset, the average number nodes, edges, and triangles in the graphs, and the dimension of the initial attributes of simplices, are summarized in Table g To perform graph classification using the embeddings learnt using SaNN, we combine embeddings of the constituent simplices of all orders in the clique-lifted graphs. Since the number of k-simplices in training example (a clique-lifte graph) is large for 0, 1,..., K. concatenating embeddings of all the k-simplices in training example will result in very nigh-dimensional embeddings. Therefore, we propose to use summation as the readout function at k-simplices level. We. finally, use concatenation as the global-level readout function. Specifically, we take a summation of all the node embeddings. edge embeddings, and triangle embeddings in a graph and concatenate the node- level, edge-level, and triangle-level embeddings of the simplicial complex get one global representation for the simplicial complex. We prove that using summation the k-simplices level readout function along with
use the predefined data splits that are used in EErica al. (2200) for performing
22

---

Published as a conference paper at ICLR 2024
concatenation the global level readout function preserves injectivity in Appendix The global embeddings of graphs are given input to decoder MLP with cither sigmoid activation function or softmax activation function as the final layer depending on whether the dataset has two or more classes. For the datasets, we train SaNN in supervised manner using the cnosopy loss function, which takes the output of the decoder and the true graph labels as the input. We implement early stopping while training.
Table 8: Graph classification dataset details.
DATASET
GRAPHS
CLASSES
AVG. NODES
AVG. EGDES
AVG. TRIANGLES
INPUT FEAT, DIM.
PROTEINS
1113
2
39.06
72.82
27.40
3
NCT1
4110
2
29.87
32.3
0.05
37
IMDB-B
1000
2
19.77
96.53
391.99
IMDB-M
1500
3
13,00
65.94
305,9
REDDIT-B B
2000
2
429.63
497.75
24.83
REDDIT-M
5000
5
508.52
594.87
21.77
The hyperparameters used in graph classification experiments, namely, batch size, number of branches, given by (T' 1). used in the computation of the features of each of the K = 3 different dimensional simplices, namely, nodes, edges, and triangles, hidden dimensions of edge representations in the MLP for transforming edge features (denoted by T) and the decoder MLP (denoted by D), learning rate, L2 regularization parameters, are summarized in Table
Table 9: Hyperparameters of SaNN set for graph classification experiments.
BRANCHES
HIDDEN DIMENSIONS
LEARNING RATE
T
DATASET
BATCH SIZE
(K x (T + 1))
(64,64,64)
PROTEINS
64
x
(64.64,64.1)
10-3
10-4
[64.64.64)
NCII
64
3 x 2
(64.64.64.1)
10
10
(32.32.32)
IMDB-B
64
3
10-3
10
(32.32.32.1}
{16,16.16}
IMDB-M M
64
3
10
10
{16.16.3)
(32,32,32)
REDDIT-B 64
3
10
10 10
(32.32.1)
(64,64.64)
REDDIT-M 64
3x2
x 10
10
(64.64.5)
I SUMMATION AS L-SIMPLICES-LEVEL READOUT FUNCTION AND CONCATENATION AS GLOBAL READOUT FUNCTIONS ARE INJECTIVE
Let denote the multiset of the aggregated features branch the k-simplices in training example (here. clique-lifter graph) Tr by A4")) x VT |T.) From Lemma in Leskovec Jegelka (2019) there exists functions 9k (-), Vt. O..... T,
, so that E.EA(") 9k (a) are unique for each multiset A computed
from the training set. Since concatenation is injective, this implies that there exist functions gx
(4) (.), VL
O, o..... T,, such that the combined embeddings of k k-simplices in the training example from different hops
T
e
Σ A
9k
Σ (1)
9k
Σ
T Ok
(a)
REA(
AE
(37)
unique. Given the universal approximation ability of MI.Ps and our choice of using ML.P% as the transforma- tion functions, the injectivity of NN preserved.
23

---

Published as a conference paper at ICLR 2024
Table 10: Trajectory prediction accuracies of ablation experiments study the effect of features from different depths. The first and the second best performances are highlighted in red and blue, respectively. The values within parentheses are the average per epoch run-time values (in seconds). The best run-time values are highlighted in bold.
Dataset
Ocean
Synthetic
Planar
Mesh
34.0 + 0.6
50.3 + 1.2
96.9 + 1.9
98.1 + 1.9
SaNN
(1- (1-hop)
(0.1)
(2.0)
(17.6)
(4.1)
34.0
53.8 +
96.8 + 1.8
95.5 + 2.0
SaNN (2 (2-hop)
(0.1)
(2.1)
(17.9)
(4.9)
33,5 + 0.7
51.3 + 1.2
95.5 2.0
94.3 1: 2.0
SaNN (3 (3-hop)
(0.1)
(2.1)
(19.2)
(4.9)
35.0 0.7
54.9
97.0 1.9
98.3 + 2.0
SaNN
(T-2)
(0.1)
(2.5)
(23.8)
(8.1)
34.1 + 0.7 (0.1)
53.9 111
97.3 + 1.9 (26.8)
98.3 + 2.1
SaNN
(T=3)
(2.5)
(8.1)
Notice that concatenating the readouts from different branches of k-simplices is the same as concatenating the embeddings from different branches first to get embeddings the k-simplices and then computing readout:
ek
Σ
9h
(a),
Σ
(1)
Σ
(P) 9h
(a) (a)
MEAA
(0)
"EA
AEA (T)
Σ
[T].
Σ ( [r].... Σ
ST
[T]
TETA
TET
TETA
Σ
S
(0)
[r].
(1)
[r]
(38)
EE
J ABLATION STUDY
We perform ablation experiments study the effect features from the different components of the SaNN model. Specifically, we perform the following two experiments: (i) we study the effect precomputed features aggregated from different depths of neighborhood, i.c., the effect of features for different f, and (ii) we study the effect of features of simplices of different orders, ie., the effect of features for different k, for the tasks described in Section[S]
Table 11: Relative AUC-PR values of ablation experiments study the effect of features from different depths for simplicial closure prediction. The first and the second best performances are highlighted in red and blue, respectively. The values within parentheses are the average per epoch run-time values (in seconds). The best run-time values are highlighted in bold.
DATASET
ENRON
HIGH- SCHOOL
PRIMARY-SCHOOL
NDC-CLASSES
MATH Sx
15.18 0.1
29.86 + 0.0
30.19 0.0
1.82 + 0.1
6.33 + 0.0
(1-HOP) /R3
(2)
(28)
(133)
(7)
(18396)
14,88 0.1
29.93 0.0
33.18 +: 0.0
2,53 0.1
5.83 1: 0.0
(2 /RB
(2)
(96)
(138)
(8)
(32612)
14.78 - 0.0
26.61 0.1
30.66 4: 0.0 (594)
0.95 195:100 0.1
4,99 0.1
SANN
(3-HOP) /R3
(2)
(107)
(9)
(45716)
15. 15 0.0
30.22 + 0.0
32.89 0.0
2.79 0.0
6.88 0.0
SANN (1- /RB
(3)
(112)
(916)
(13)
(52883)
15.45 +
26.63 0.0
32,28 0.0
1.75 0.0
5.65 0.1
SANN
/BB
(3)
(203)
(932)
(22)
(78323)
24

---

Published as a conference paper at ICLR 2024
Table 12: Graph classification accuracies of ablation experiments to study the effect of features from different depths. The first and the second best performances are highlighted in red and blue, respectively. The values within parentheses are the average per epoch run-time values (in seconds). The best run-time values are highlighted in bold.
DATASET
PROTEINS
NCI1
IMDB-B
REDDIT-B
REDDIT-M M
75.0 2.2
73.0 = 2.0
70.3 + 2.1
91.8 + 2.7
53.0 + 1.6
SANN (1-ROP)
(0.3)
(55)
(7)
(39)
(102)
74.9 2.1 2.1
74.1 + 2.2
70.2 + 2.0
90.3 +.3+ 2.7
52.4 + 1.5
SANN (2-ROP)
(0.3)
(57)
(8)
(40)
(103)
77.6 2.2
74.9 + 2.2
72.7 = 2.1
91.7 2.7
54.1 + 1.6
SANN (T=2)
(0.4)
(58)
(8)
(45)
(104)
Table 13: Relative AUC-PR values of ablation experiments study the effect of features of sim- plices of different orders for simplicial-closure prediction. The first and the second best perfor- mances are highlighted in red and blue, respectively. The values within parentheses are the average per epoch run-time values (in seconds).
DATASET
ENRON
HIGH-SCHOOL
PRIMARY-SCHOOL
NDC-CLASSES
MATH-SX
11.14 + 0.0
16.61 = 0.0
4.19 0.0
2.62 + 0.0
4.96 + 0.0
SANN (0- SIMELIEIEE
(2)
(85)
(718)
(12)
(33618)
13,03 + 0.0
27.11 T: 0.0
30,28 + 0.0
2.52 1 0.1
6.18 1: 0.0
SANN (1-SIMELICES)
(2)
(84)
(719)
(10)
(42422)
15.45 = 0.0 (3)
30.22 + 0.0
32.89 = 0.0
2.79 - 0.0
6.88 = 0.0
SANN (K=1)/RB
(112)
(916)
(13)
(52883)
J.1 EFFECT OF FEATURES FROM DIFFERENT DEPTHS
We study the influence that the features aggregated from the 1-hop neighborhood, 2-hop neighborhood, and 3-hop neighborhood have the prediction accuracies for trajectory classification and AUC-PR values for simplicial closure prediction. Since the graphs graph classification datasets are very small, lation experiments for graph classification to the features aggregated from the 1-hop and 2-hop neighborhoods. We also study the effect of combining the features from different depths as proposed in the paper lef. Fig. 2 relative to using features aggregated from specific depth of neighborhood. The results of ablation experiments for trajectory prediction, simplicial closure prediction, and graph classification and [2] respectively. Experiments involving features only from depth t are denoted by SaNN (t-hop) and those involving features aggregated from O,.... . t-hop neighborhood are denoted by SaNN (I=t).
restrict the ab-
reported in Tables T0
We observe that the proposed model (SaNN (I=2 (or 3))) as given in Section 3 which considers the combination of features from different depths, achieves hetter performance than using features from a specific neighborhood depth (SaNN (t-hop), for = 1, 2,3) 3) for all the three tasks. Since the model proposed in Section denoted by Sa NN (TT2 (or 3) (and not (SaNN (t- (t-hop),
= 1, 2, 3)), what is proved to be as powerful as MP SN, we expect its embeddings to be as expressive as those from MP SN, and therefore, perform downstream tasks on par with SN.
We observe that 1 hhhop information is usually the most informative, implying that local information is crucial for all three tasks. The 3-hop information seems not so relevant for these tasks. For the cases when the combination information from different depths is considered, SaNN (T-2) is seen to perform better than SaNN (T-3) possibly due to the inclusion of the irrelevant non-local features in the form of 3-hop features. This implies that if an even faster implementation is desired at the cost of a slight degradation of performance, SaNN (1 hoo) be used since achieves comparable performance time. However, for graph classification, we observe that since the graph sizes are small, the run-time difference between 3 BANN (t-hop), for t 1, 2, and SaNN (T=2) is not prominent. Therefore, it is always better to perform graph classification using SaNN (T=2) than SaNN (t-hop), for f = 1,2.
SaNN (T=2 (or 3) in an even smaller run-
J.2 EFFECT OF FEATURES OF SIMPLICES OF DIFFERENT ORDERS
We study the influence that simplices of different orders have on the AUC-PR values for simplicial closure prediction and classification accuracies for graph classification. Since we focus on the simplicial closure of open triangles, the ablation experiments involve features of only 0-simplices and 1-simplices. In the ablation experiments for graph classification, we consider features of and simplices. Since features on only
25

---

Published as a conference paper at ICLR 2024
Table 14: Graph classification accuracies of ablation experiments study the effect of features of simplices of different orders. The first and the second best performances are highlighted in red and blue, respectively. The absence of simplices of a particular order dataset is indicated by in the corresponding column.
DATASET
PROTEINS
NC11
IMDB-B
REDDIT-B B
REDDIT-M
76.0 + 2.3
73.5 + 2.2
71.2 + 2.1
88.6 2.6
53.6 1.5
SANN (0- (0-SIMPLICES)
(0.2)
(32)
(7)
(41)
(91)
59.3 + 2.3
66.2 + 2.3
70.6 2.2
88.7 2.6
38.1 + 1.6
SANN (1 (1-STMPLTCES)
(0.2)
(35)
(8)
(42)
(84)
73.4 2.1
70.8 2.1
75.8 2.8
43.0 + 1.6
SANN (2- (2-IMMLLIESS)
(0.3)
(8)
(37)
(89)
60.0 1 2.3
59.1 2.3
SANN (M-SIMPLCEES)
(0.3)
(8)
76,2 + 2.2
74.9 + 2.2
72.7 - 2.1
91.7 + 2.7
54.1 + 1.6
SANN (K=2)
(0.3)
(58)
(8)
(45)
(104)
77.6 2.2
68.2 2.1 (9)
SANN (R-3)
(0.4)
I-simplices considered for trajectory prediction, not perform such ablation experiment for the trajectory prediction application. The results ablation experiments simplicial closure prediction and graph classification are reported in Tables 13 and 14 respectively. Experiments involving features corresponding to
only k-simplices are denoted by SaNN (k (k-simplices) and those involving features of o, k-simplices are denoted by SaNN (K=k).
is evident from Tables 13 and 14]that that combining the transformed features from simplices different orders results a much better performance than using only nodes, edges, triangles, or tetrahedrons to the tasks. Specifically, for simplicial closure prediction, we observe that the constituent edges of open triangles carry the most crucial information about whether simplex will be formed. This agrees with the observation made in Benssn et al. (2018), which states that the tie strengths of the edges in open triangle positively impact its simplicial closure probability. More specifically, how often constituent pairs of nodes an open triangle appeared together in a simplex is observed to affect how probable the three nodes are to form a simplex. This explains the superior performance of SaNN (1-s mp ces) ces) as it captures the interactions of the edges with the other higher-order simplices. Since SaNN (0- s iimpiicess misses capturing this information, its performance is relatively poor. For graph classification, simplices higher orders like triangles and tetrahedrons yields poor results. This is possibly because of the fact that the graphs are very small and as a result, contain very few simplices of higher orders. The very few simplices present in the graphs not sufficient to capture the structure of the graphs and distinguish them. Furthermore, observe that combination of embeddings of simplices of different orders always results in a better performance than that obtained using simplices of only one order. The result that SaNN (K=2 (or 3) performs better than SaNN (0-s sesssmmpicee agrees with the theory, where we prove that SaNN (K=2 (or 3)) is more powerful than the WL test.
observe that classification performed using
26


Reviews:
[{"review_id": "6iCqDrP0HV", "reviewer": "Reviewer_jAzK", "summary": "The paper describes an efficient, and effective approach for learning representations for simplices in a simplicial complex. The central idea is that of using injective functions for aggregating simplicial features, as it ensures that the embeddings are unique. The simplicial features are aggregated over upper, lower, boundary and co-boundary adjacencies. The paper provides precise definitions and theorems and statements on the properties of the networks. The proofs are summarized in the main body and provided in full detail in the appendices. The method is further experimentally validated and shows that the proposed model (SaNN) is both efficients (significantly faster than any of the other baselines) and effective (performance within the uncertainty intervals on accurcies, or above the baselines).", "questions": "Could you respond to the above concern, and additionally address the following questions/comments?\n\n2. On several occasions the notion of \"non-deep baselines\" is used. What is meant by this. Could you clarify what non-deep means here, which methods are these?\n\n3. In section 2 when presenting the symbols it is mentioned that $k=1,2,\\dots,N+1$. Does $k$ always run up all the way to $N+1$?\n\n4. In section 4. The sentence that starts with \"The theorem implies that any arbitrary ...\" is extremely long and hard to comprehend. I suggest to split it 2 or 3 sentence to improve readability.\n\n5. Just above property 1 it is mentioned \"other commonly used sum, mean, or max read-out functions are not injective\" I am not fully sure I understand it correctly. The paragraph above explains that sum aggregation is the best injective aggregator, in contrast to mean aggregation. I think the statement that I just quoted is about aggregating over the different $\\mathbf{Y}$'s? Perhaps this can be clarified.\n\n6. In the tables: since colors red and blue are used you might as well color the text in the caption as well. I.e. \"The {\\color{red}first} and {\\color{blue}second} best performances ...\"\n\n7. The insights section says \"The deep models are observed to perform exceptionally better than logistic regression\", where do I see this? Logistic regression taking what as input? Could this be clarified.\n\nThank you for considering my comments and questions.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. I am impressed by the clarity of presentation in the paper. I find talking and reading about simplicial complex often a messy business given all the types of simplices and adjacencies, and the abstract notion in the first place. It is clear that the authors though well about how to present the math. This includes proper use of figures.\n2. The goal of the paper itself -efficiency whilst not compromising on expressivity- is relevant and important, and it is great to see the authors succeeding in reaching this goal.\n3. I appreciate the summary of the proofs after the formal statements.\n4. Next to a sound theoretical exposition, the experiments are thorough as well and include many ablation studies that are used to distill insightful take home messages.", "weaknesses": "I only have 1 important concern:\n\n1. Although the main principles are clear, I am still confused about the actual architecture/predictive models. In the end we have equation 8, but it describes a representation for each of the $N$ sets of $k$-simplices, each consisting of the $N_k$ simplices. It is unclear how to distill a global prediction out of all these representations, as would be needed for e.g. the classification tasks. Details on how the architectural design for each of the benchmarks is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i5Pj9In9p1", "reviewer": "Reviewer_7LnN", "summary": "The authors propose a class of simple simplicial neural network models, referred to as simplicial-aware neural\nnetworks (SaNNs), which leverage precomputation of simplicial features. The authors theoretically demonstrate that under certain conditions, SaNNs are better discriminators of non-isomorphic graphs than the WL and SWL test. Empirically, SaNNs are shown to perform competitively against other SNNs and GNNs on tasks such as trajectory prediction, simplicial closure prediction, and several graph classification tasks over various datasets.", "questions": "1. Is assuming the learnable transformation functions $g_k^{(t)}\\cdot)$ are injective too strong? Although the MLPs will be injective, appealing to the Universal Approximation Theorem to declare that $g_k$ can be injectively-approximated is probably not practical. \n\n2. I may have missed this but are pre-computation times explicitly indicated in the results?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The theoretical results are intriguing. Indeed, a competitor to the WL and SWL tests would be a valuable contribution to the graph ML community. \n\n2. A wide variety of benchmarks over several tasks and datasets are conducted to demonstrate the efficacy and efficiency of SaNNs. \n\n3. SaNNs inherit several valuable invariance properties of other SNNs including permutation invariance, orientation invariance, and simplicial-awareness. \n\n4. Compared to MPSNs, consideration of higher-order simplices does not blow up computation complexity.", "weaknesses": "1. It is unclear for a research with limited expertise in this rather niche area to conclude the strength of the conditions prescribed in Theorems 4.1 and 4.2. (See questions.) \n\n2. There do not appear to be any results describing the pre-computation time which should be included in any run-time comparisons which I imagine should scale near-exponentially with graph size and order of simplices considered. \n\n3. SaNNs are often not outright the winner in terms of prediction accuracies for the tasks displayed in Tables 1 and 3. For example, in Table 1, the SaNN is outcompeted by Projection and Scone on 3/4 of the datasets and the run-time savings of SaNN are not significant enough to justify usage of the SaNN. In Table 3, SaNN is not the leader in 4/5 of the datasets and it is not even the fastest. On the other hand, the time savings against MPSN are quite significant, but since many practitioners of graph learning expect training to take significant amounts of time, accuracy is the topmost priority, so there wouldn't be a strong enough justification to go with a SaNN.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tkcYyLyiYm", "reviewer": "Reviewer_LALK", "summary": "The authors present a Simplicial Graph Neural Network, which considers higher-order structures in the input graphs. In comparison to previous work, the features from k-simplices are precomputed without trainable parameters and only then fed into a GNN. This leads to lower runtime during training since features can be reused in each epoch, which is validated by the authors theoretically and empirically.\n\nThe authors prove that their method is more powerful than the WL test and as powerful as the Simplicial WL (SWL) test, when it comes to distinguishing non-isomorphic subgraphs. Further, they prove permutation equivariance, orientation equivariance, and simplicial-awareness.\n\nThe method is evaluated on trajectory prediction, simplicial closure prediction, and graph classification, where it is on par/slightly outperforms previous works with better training runtimes.", "questions": "- I wonder how the method compares to previous methods in inference runtime, when feature precomputation needs to be included.\n\n-----------\nI thank the authors for proving the precomputation times explicitly and for replying to other concerns I have - this is certainly helpful to evaluate the differences to previous work.\n\nIn general, I am still on the fence and still doubt the significance of the contribution. However, I acknowledge that other reviewers find value in it and, thus, slightly raise my score. I am not opposing this paper to be accepted, as I think it is a thorough and well executed work.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The goal of the work, achieving better scalability of expressive networks by using non-parametric simplicial encoders makes sense.\n- The authors thoroughly analyze their method theoretically and provide proofs for all relevant properties.\n- The presented method seems to find a good trade-off between expressiveness, runtime and empirical quality.\n- There is theoretical value in the non-parametric encoder for simplices that keeps equivariant properties and simplicial-awareness\n- The paper is mostly well written", "weaknesses": "- Runtime and asymptotic comparisons in this work are done by excluding the precomputation of features. I think this is misleading, since in practice, the precomputation is certainly part of the computation, especially during inference. Thus, the presented gains seem to be only valid during training, when the features need to be computed only once for many iterations of training. \n- At the same time, the method only performs on par with previous work, with small gains on some datasets.\n- The method requires many hyper parameter choices like hops, T, k, which seem to have different optimal settings on different datasets. The result quality differs substantially depending on the configuration.\n- I am skeptical regarding the practical relevance of the presented method due to above reasons.\n\n- The method lacks conceptual novelty. The main idea of precomputing features by non-learnable functions has been seen in other areas, e.g. non-parametric GNNs. The general structure of the work follows a long line of work about GNN expressiveness (higher order and WL-level) without presenting many novel insights.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4sGhXacqSF", "reviewer": "Reviewer_4crX", "summary": "This paper considers the design of neural networks for simplicial complexes, which are more general combinatorial structures than graphs, but less general than hypergraphs. The authors propose to use multihop aggregation schemes to build an architecture that is more expressive than the simplicial Weisfeiler-Lehman isomorphism test, while satisfying useful invariance, equivariance, and expressivity properties. They also demonstrate the efficientcy of their proposed method, and its performance for a few different tasks in simplicial data processing.", "questions": "My most important concern is summarized in point 1 -- in particular, the ambiguities around orientation equivariance and the use of oriented operators built from the incidence matrices are what cause me to suggest this paper be rejected. If the authors are to focus on either of the two points in order to change my mind on this paper, it should be the first one.\n\n1. There are some details missing regarding the type of data being handled. In particular, the incidence matrices are not defined in a way sufficient for the discussion following in the paper. Normally, the incidence matrices have values of +-1 depending on a chosen reference orientation (usually given by some ordering of the nodes). Coupled to this, the signs of the features on the simplices are determined relative to the same reference orientation -- this gives meaning to the notion of orientation equivariance. Without discussing these things, orientation equivariance is not a meaningful concept within the context of the paper. \n\na. This calls into question the validity of the example in Section 4.1. You say that all simplices are given a feature value given by some scalar $a$ -- yet, the matrices acting on these feature vectors/matrices have an orientation associated to them. It seems as if you are using an *oriented operator* to act on *unoriented features*. Property 1 in this example is thus difficult to claim, as the property of orientation equivariance is one describing the action of *oriented operators* acting on *oriented features*, and how the choice of orientation to begin with is irrelevant to the computation. \n\nb. Furthermore, this problem yields a comparison for isomorphism testing incorrect, as the erroneous imposition of differently-oriented features relative to the chosen orientations could be used by SaNN to yield a \"false negative,\" i.e., saying that two isomorphic complexes are different. \n\nc. A more minor comment in this direction comes from the **Insights** section of Section 5.1. It is not correct to say that \"the superior performance of SaNN also proves the orientation equivariance of SaNN experimentally.\" Orientation equivariance is a simple mathematical property, and does not guarantee good performance, nor are all performant architectures on a given dataset orientation equivariant. These properties are possibly linked, but the claim that one proves the other in some way is not justified. \n\nd. Moreover, based on my reading of the appendix, many of their experimental setups for tasks other than trajectory prediction use \"unoriented data\" by simply assigning scalar values to high-order simplices, which is again incompatible with the use of oriented operators. Perhaps something in the implementation of SaNN in these examples does not use oriented operators such as the incidence matrices, but this is not clear to me. \n\nPlease either justify, clarify, or revise the paper's discussion regarding orientation equivariance.\n\n2. Related to the above point, the claims in Section 4.2 seem reasonable at first glance, but are not explained well enough. Permutation equivariance is easily seen to hold, so is not much of a concern. Orientation equivariance is subject to the problems noted above, so more clarification on the type of simplicial features and relevant operators needs to be made. That is not to say that the result proved in the appendix is wrong, but it needs to be clarified in order to be understood in a way that acts on oriented features. Simplicial awareness is more subtle than the other two, based on the definition from (Roddenberry et. al., 2021). For instance, some of the existing convolutional-type SNNs in the literature fail to satisfy simplicial awareness if they are implemented without nonlinear activation functions, due to the fact that the square of the (co)boundary operator is the zero operator. Perhaps it is the case that the assumptions of Theorem 4.2 are sufficient to exclude such methods, but a clearer connection is needed. It would be very helpful for the authors to briefly survey some of the methods they compare to, and clarify whether Theorems 4.1 and 4.2 apply or don't apply to them.\n\n---\n\nThank you for addressing my questions -- I have raised my suggested score.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. For the most part, this paper is well-written, and is easy to digest for someone who is familiar with graph neural networks. I don't think the intended audience of this paper includes someone not familiar with GNNs, but this is fine in my opinion.\n\n2. The proposed method is demonstrated to be quite efficient in comparison to existing ones, with similar performance as well.", "weaknesses": "1. Certain definitions regarding the types of operators and features are not laid out clearly enough, which leads to ambiguity in the paper on a technical level. As noted in the list of questions and suggestions, the claimed properties of the proposed models are not clearly true, possibly due to this misunderstanding.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)