Learning From Simplicial Data Based on Random Walks and 1D Convolutions
Authors: Florian Frantzen
Michael T Schaub
Venue: ICLR 2024 poster (2024)
Keywords: simplicial complex
simplicial neural network
random walks
Primary area: learning on graphs and other geometries & topologies

Abstract: Triggered by limitations of graph-based deep learning methods in terms of computational expressivity and model flexibility, recent years have seen a surge of interest in computational models that operate on higher-order topological domains such as hypergraphs and simplicial complexes. While the increased expressivity of these models can indeed lead to a better classification performance and a more faithful representation of the underlying system, the computational cost of these higher-order models can increase dramatically. To this end, we here explore a simplicial complex neural network learning architecture based on random walks and fast 1D convolutions (SCRaWl), in which we can adjust the increase in computational cost by varying the length and number of random walks considered while accounting for higher-order relationships. Importantly, due to the random walk-based design, the expressivity of the proposed architecture is provably incomparable to that of existing message-passing simplicial neural networks. We empirically evaluate SCRaWl on real-world datasets and show that it outperforms other simplicial neural networks.

Published as a conference paper at ICLR 2024
LEARNING FROM SIMPLICIAL DATA BASED ON RANDOM WALKS AND 1D CONVOLUTIONS
Florian Frantzen
Michael T. Schaub
Department of Computer Science RWTH Aachen University, Germany
Department of Computer Science RWTH Aachen University, Germany schaubê cs rwth-aachen.....mmm de
florian, frantzen www.--achhnn.c..
ABSTRACT
Triggered by limitations of graph-based deep learning methods in terms of compu- tational expressivity and model flexibility, recent years have seen a surge of interest in computational models that operate on higher-order topological domains such as hypergraphs and simplicial complexes. While the increased expressivity of these models can indeed lead to a better classification performance and a more faithful representation of the underlying system, the computational cost of these higher- order models can increase dramatically. To this end, we here explore simplicial complex neural network learning architecture based random walks and fast ID convolutions (SCRaWI), in which we can adjust the increase in computational cost by varying the length and number of random walks considered while accounting for higher-order relationships. Importantly, due to the random walk-based design, the expressivity of the proposed architecture is provably incomparable to that of existing message- passsingg simplicial neural networks. We empirically evaluate SCRaWl on real-world datasets and show that it outperforms other simplicial neural networks.
INTRODUCTION
In recent years, there has been strong interest in extending graph-based learning methods, in partic- ular graph neural networks, to higher-order domains such hypergraphs and simplicial complexes. These higher-order abstractions offer a more comprehensive representation of relationships among entities than traditional graph-baser approaches, which are based on pairwise interactions. Accord- ingly, it has been shown that we can achieve performance gains in various learning and prediction tasks for complex systems by employing such higher-order models (Benson et al.) [0188] Schaub) et al. 2021; Battiston & Petri 2022). For instance, in the context of graph classification, it is well known that standard gressage-passingg graph neural networks with anonymous inputs are limited in their expressiveness by the one- dimensiinii Weisfeiler- Leman graph isomorphism test (Morris et al., 2019; Xu et al. 2019] Morris et al. 2023) and thus cannot distinguish certain non-isomorphic graphs. concrete example that such graph neural networks cannot differentiate between cycle of length 6 vs. two non-connected triangles. In contrast, higher-order extensions of graph-neural networks have greater expressiveness and naturally enable us to distinguish such graphs.
However, due to the combinatorial increase in the possible interactions, there is a significant cost in terms of increased memory and compute time associated with the use of higher-order representations. To alleviate these issues, here we take inspiration from random walk-based graph neural networks on graphs TTöshooff et al. 2023) and explore the use of a random walk-basee learning architecture for simplicial complexes. The advantages of this strategy are particularly apparent for simplicial complexes and related architectures. First, by choosing the number of random walks sampled, we can effectively trade off the computational demands with the expressivity of our architecture. Second, as we can compute fast ID convolutions on the generated random walk trajectories via fast Fourier transforms, this saves us from computing far more expensive convolutional filters simplicial complexes. Interestingly, it was shown in (Tönshoff et al. 2023) that there exist graphs that cannot be distinguished by the classical Weisfeiler-Lenme random walk-based learning strategy, and vice versa that certain graphs cannot be distinguished that distinguishable by the 1-WL. test. This incomparability message-passe passing schemes extends to
(WL) test, that can be distinguished using such

---

Published as a conference paper at ICLR 2024
sample walks
Vertices
current states
112624634
Edges
640
1134
950
Triangles
Va
V4
[=-[...]
Random Walks
F3 [..
Simplicial Complex
Featuune Mutricus
updatee states
CNN
convolations
Figure 1: Sketch of SCRaWI illustrating the individual steps of the model. We sample collection of random walks on the simplicial complex and transform them into walk feature matrices. These are then processed by a ID convolutional network and pooled into updated simplex states.
the case of simplicial complexes, and result, learning architecture has an expressivity that is not comparable to message-passee passing-basse -baiing--beedddd- schemes such as (Bodnar et al. 2021b
Contribution We contribute SCRaWI, a novel neural network architecture for simplicial complexes that utilizes random walks on higher-order simplices to incorporate higher-order relations between entities into the neural network. This leads to an architecture different from existing simplicial neural networks. We prove that SCRaWI's expressiveness is incomparable to that of mnessage-passing simplicial networks and show that model outperforms existing approaches real-world datasets.
Related work Compared corresponding graph learning problems, learning from data supported on simplicial complexes has so far received far less attention. [Eli et al.) (2020) presented a basic convolutional neural network (SNN) for simplicial complexes, which was later extended by Yang et al. (2022a) to incorporate information flows between different orders of simplices (SCNN). Roddenberry al. (222)) proposed a convolutional architecture for trajectory predictions that rooted in tools from algebraic topology and derived three desirable properties for simplicial neural architectures: permutation equivariance, orientation equivariance, and simplicial awareness.
Bodnar et al. (2021b) proposed message-passing paseeepppsnnggg simplicial network (MPSN), which adapts the proven message-passing concept from graph neural networks simplicial complexes using messages to adjacent, upper-adjacent, and lower-adjacent simplices. They later extended this line of work to the domain cell complexes (Bodnar et al., 2021a). Similarly, Goh et al. (022)) and Giusti et al. (2022) independently adapted the well-known attention mechanism from graph attention networks and constructed the simplicial attention networks SAT and SAN, respectively. Apart from this line of research focused extending graph models to simplicial complexes, Keros et al. (2022) proposed a graph convolutional model for learning functions parametrized by the k-homological features of simplicial complexes.
Random walks on simplicial complexes have been considered in (Schaub et al. 2020 Alev & Lau 2020, Parzanchevski Rosenthal] 2017 Mukherjee Steenbergen 2016). Billings et al. (2019) and Hacker (2020) proposed two similar random walk-based representation approaches (simplex2vec and k-simplex22ed learn embeddings from co-appearing simplices in the walks, with the idea that co-appearing simplices should have similar embeddings while other simplices should be further apart in the embedding space. Yang et al. (2022b) extended this work with sc2vec, which takes more connections into account and therefore yields more effective embeddings. These unsupervised representation learning methods compute embeddings for simplices or simplicial complexes, which then be used for downstream tasks such as classification, while SCRaWI is supervised learning method that trained end-to-aee -ondd.
For graphs, several neural networks based on random walks have been proposed. Nikolentzos & Vazirgiannis (2020) proposed RWNN, a model that integrates a random walk-based kernel into a GNN architecture. Jin et al. 2022) and Eliasof et al. (2022) proposed two architectures that aggregate node features along random walks to leamn information based on walk distances. Our work here extends the approach by Tönshoff al. (202)). which proposed random walk-hased graph neural network
2

---

Published as a conference paper at ICLR 2024
architecture that enriches the random walks with local structural information and processes the resulting feature matrices with a ID convolutional neural network. Zhou et al. (202)) connect some of these concepts and extend ideas behind RWNN to simplicial complexes. In contrast to SCRaWI, they use walk probabilities to enrich the node and edge features for following message-passing steps, while we make use of explicit random walks as the main building block of our architecture.
Another popular abstraction tool for higher-order data is hypergraphs, for which several learning architectures have been proposed. In a similar vein to simplicial neural networks, graph neural networks have been abstracted to hypergraphs, e.g., convolutional networks (Yadati el al. 2019). attention networks (Chen et al. 2020). and peessage-passingg networks (Heydari & Livi, 2022] Chien et al., (022). Very recently, Behrouz et al. (2023) presented walk-based hypergraph neural network that uses temporal walks to extract higher-order causal patterns. Compared to their approach, SCRaWi can capture more structural properties as part of the feature matrices resulting from the random walks.
Outline The remainder of this manuscript is structured as follows. Section 2 gives an overview of the mathematical concepts of simplicial complexes and random walks on them. In Section 3 we present our proposed architecture SCRaWI in detail. Section analyzes the expressiveness of SCRaWI compared to MPSN and Section 3 evaluates SCRaWl empirically variety of datasets.
2 BACKGROUND
Here, we present an elementary overview of concepts used to process signals defined on simplicial complexes. For more details, see (Bredon 1993, Hatcher 2002) for background in algebraic topology and (Schaub et al. 2021 Roddenberry et al. 2022) for topological signal processing.
We use [ri] to denote the set of integers from 0 to n - 1. Vectors are denoted by boldface lowercase letters v, matrices and tensors by capital letters F. For ease of notation, we index rows and columns from O. F,,- and F- denote the i-th row and j-th column, respectively, of a matrix F. O, and 1, denote n-dimensional all-zero and all-one vector, respectively.
An abstract simplicial complex (SC) (Bredon 1993 Hatcher 2002) X consists of finite set of points V. and set of non-empty subsets of V that closed under taking non-trivial subsets. A k-simplex Sh E X is a subset V with + 1 points and if S E X, then for all non-empty S C Sh. Sk-1 E X. We denote the set of k-simplices in X by X₁ and their cardinality by n, X Furthermore, for l > 0 the faces ((8*) {( X 8k-1 c S*) } of S* are the subsets of S with cardinality k. We set 8(S*) 0 for k If 1 a face of Sh S is called a coface of 1k-1. We denote the set of cofaces of S by C(S*).
We respectively denote the of lower and upper adjacent simplices of S by:
(S*) = {5* E X B(S*) n 3(S*)) * (}: n N*** (5*h E X ((s*))e((S))) + 0}-
(2)
Note that SCs can be understood as an extension of graphs: Xo is the set of vertices, X, is the set of edges, X₂ is the set of filled-in triangles (not all 3-cliques have to be filled-in triangles), and so on.
Simplices are equipped with features f& X2 + dRde For flexibility, we allow the feature spaces to be different for each simplex order, as is common in real-works data sets. If no features are supported on a simplex order, we set dç =
3 METHOD
At its core, SCRaWl extracts information from data supported on a simplicial complex by sampling random walks on the underlying complex. These walks are then transformed into feature matrices, which are used to update the states of the simplices in the subsequent steps. More precisely, SCRaWI consists of three steps, as are illustrated in Figure First, we sample random walks on simplicial complexes, as described in Section 3.I] Second, as discussed in Section we transform these walks into feature matrices that encode the random walks, the simplex states that appear them, and the local adjacencies between simplices along the walk. Finally, we process these feature matrices with a simple convolutional neural network update the hidden states of the simplices (see Section 3.3)
3

---

Published as a conference paper at ICLR 2024
3.1 RANDOM WALKS ON SIMPLICIAL COMPLEXES
A walk of length & on the k-simplices of a simplicial complex X is a sequence of k-simplices (vo.-..,, u)) E X such that o; and 12+1 1 share common face coface e, for all i E [e]. i.e.,
M441 (w:)) (mz). Note that different from the case of graph e; is not uniquely defined given by and U4-1, since Ui+1 can be reached by either a common face or a common coface. We keep track of the connection used reach the next neighbor and define W (vo, Eo; U1, Ei...., 2r- UE-1).
While there are many possible sampling schemes for random walks on SCs, for simplicity, we only consider two elementary sampling methods: (a) uniform connection sampling, and (b) uniform neighbor sampling. For both sampling strategies, we obtain a random walk on the k-simplices of X as follows: First, sample a random starting k-simplex Up (Xxx) and then sample the subsequent simplices in a walk as described in the following subsections. Using this strategy we sample m random walks on the simplicial complex, which can be chosen at runtime and can vary between training and prediction. In the case = [XX,, , opt to start random walk from each simplex, i.e. we do not sample ti uniformly at random but choose every simplex once as vo. Note that by choosing smaller
reduce the computational cost we incur for learning and processing the data.
Uniform Connection Sampling Starting from simplex uy we iteratively sample a face or coface ei ~ (3(x)) U ((x)) and neighbor
(u(((e)) if E 3(e,)
0++1
(3((e))
if E ((e))
of vn that is connected es via e, uniformly at random. This way, a neighbor with more connections to the current simplex is more likely to be sampled.
Uniform Neighbor Sampling Starting from simplex vo we iteratively sample neighboring simplex 0:4 ~ (NN (v:) U (v:)) and suitable connection
e ~ u1 uu(((6 (B(c:) ((1++1) u (C(1)) n ((e++a)))
uniformly at random. This way, higher-order simplices do not have a disproportionate influence on the walk due to their many low-order connections.
3.2 WALK FEATURE MATRICES
Based on the sampled collection of random walks [E]) from the previous step and local window size s, we transform each walk W, into feature matrix Fw, The feature matrix consists of 6 sub-matrices: (a) one matrix for the features of the current simplex. (b) one matrix for the features of the face used to traverse to the current simplex, (c) one matrix for the features of the coface used to traverse to the current simplex, and (d) the last three matrices encode local structural information about the simplicial complex seen during the walk.
More formally, given a walk W, of length & on k-simplices, embedding functions f X - TRde for E (k- 1, k + 1}. and local window size >> O, we define the walk feature matrix Fw, as
F Fw, W. Fwv, W, Fw, Iw AW,
Alr,,s] Rexidetdd +de +36-2).
(5)
The first sub-matrix Fw, E Rexdx records the features of the k-simplices appearing on the walk W: (FW),, = f(v)) for i [4].
(6)
The second and third sub- matrictssces Fty, and Fly, record the features of the faces and cofaces. respectively, that have been used in the random walk to get from the last simplex to the current one:
((e)-)), if > O and |ei-1| < k. otherwise.
FW5),- = Odx 17
[(())));
if > 0 and /e-1/ > k otherwise.
(FW))
(8)
Oddat1
4

---

Published as a conference paper at ICLR 2024
Lower Con.
Upper Con.
Idemiit
Wo
Feature
Face
Coface
Cwg
(
0
0000
000
1/
0000
C0.1
1/4
fo
0000
C0,2
1/
fo (3)
Fi (
0000
010
1/
0000
100
CU,3
1/4
[o(
(P6.6))))
0010
101
Fw::
Cw
0000
000
000
(M2154)
C1,1
(M2.014)
(eg.24)
fi (eg.01)
Fa(
0
0000
0000
000
000
000
000
(uger4)
C1,2
94
0
0000
100
000
(14,*6)
C1,3
2/1
172
Fwy: (ere0s (0g.04
Cw2
f1(05,04)
0000
0000
000
000
(og Mai 622
1/2
Walk Feature Matrices
Convolutions
Pooling
Information flow in SCRaWI modules for simplex orders 0, and 2. Using the walks shown in Figure we compute the feature matrices Fo, F1, and F2 based on simplex features f and window size of 4. The feature matrices convolved with ID CNN while keeping track of the central simplex within the window (values to the left of the convolution matrices). Convolved matrices are pooled into simplices grouped by the central simplices.
Figure 2:
Note that whenever a face or coface feature is present, the entries of the other matrix are zero. Further, assume that d_1 d 0 and hence Fiv; and Ft W, empty for walks O-simplices and maximum order simplices, respectively, where kimax is the maximum order in the SC.
The remaining three sub-matrices Iw,- E {0, 1] Exx Ahr, E {0, 11 fx(-1)) and AWr E {0, 1] ex(s-1) record structural information the form of local identity and local adjacency features:
1, if 2 i and v, = 4y
(I (Twj.o).
(9)
0, otherwise.
(A
1,
if > 1' and uy (v:).)
(10)
0,
otherwise.
1,
if > 1' and Uy Nt:
(A (5,))
(11)
lo, otherwise.
In other words, I w keeps track of whether the current simplex has been visited before within the local window while Awr,s and AW,,, keep track of whether the current simplex is lower upper adjacent to a previously visited simplex within the local window s, respectively.
Figure 2 (left) shows an example of the walk feature matrices for the walks on the vertices. the edges, and the triangles shown in Figure [ Note particular the last three sub-matrices for each walk: For Wn, vertex is visited twice, once in the third and once in the fifth step, thus we have the same walk, we go from vn via the edges (11,22) and (u2, 24) to 14, which
(I Wwo.4)s,2
also directly connected with e1. Thus we have (A Ww 1. Similarly, for W,, we go from (v2, 24) over two steps to (D4, vo), which share a common vertex e4 Thus we have (A 1.
3.3 SCRAWL MODULE
SCRaWI module on layer t operating on order k-simplices takes as input the random walks on k-simplices and the current hidden states H H and H H
k+1 of the previous layer 1. These
5

---

Published as a conference paper at ICLR 2024
SCRaWI Layer
Outpu
H
SCRaWi Medhlee
2
SCRaWI Module
H
ML.
M/2
H1
SCRaWI
H
SCRaWI
H
ML.P
H
SCRsWi
Modale
H
SCRaWI Module
H
MLP
Figure 3: Architecture of SCRaWI model operating on simplex orders 0, 1, and 2 with L SCRaWl layers and an user-defined output layer. We reuse the same collection of random walks fee) in each SCRaWI module for performance reasons.
matrices are then used lieu the simplex, face, and coface features in the walk feature matrices, respectively. The module first computes the feature matrices Fw, for each walk Wj as described in the previous subsection and stacks them into a tensor g.
We process the walk features F by 1D convolutional network CNN (without padding) performed over the walk steps to obtain the convolved matrix C " x(I-s)xd where is the number of walks on k-simplices. The CNNs can be configured flexibly depending on the task.
For each row of the convolved matrix C+ we separately keep track of the simplex in the center row of the convolution window, as is illustrated in Figure 2 with the indices next to the convolution matrices. For each k-simplex, pool all entries of C that correspond to that simplex using mean or sum pooling. This operation results in a vector pt (v) for each h-simplex v, which is then fed into a trainable multilayer perceptron Update to obtain the updated hidden state (v).
The process of SCRaWI module is illustrated in Figure 2 of k-simplices depends on the hidden state of upper and lower adjacent simplices, and hence, over multiple layers, information is propagated through different simplex orders.
As be seen, the new hidden state
3.4 COMPLETE SCRAWI. ARCHITECTURE
Based the aforementioned building blocks, we assemble the SCRaWI model, illustrated in Figure 3
Given a range of simplex orders [K] and the number of layers L as hyperparameters, the model consists of L SCRaWI layers, each consisting of K SCRaWI modules, one for each simplex order. Within one layer, SCRaWI modules run in parallel for each simplex order k E [K]. We add skip connections for each module. Information flows between different simplex orders in between each layer in the form of the hidden states of faces and cofaces appearing in the random walks.
At the end of the last layer, we obtain hidden states H for each simplex order k E [K]. These can then be processed by user-defined output layers, e.g., by adding multilayer perceptrons that transform the hidden states into classification or regression output, to obtain the final output of the model.
3.5 PERFORMANCE CONSIDERATIONS
Most of the computational complexity of SCRaWI is due to the sampling of random walks. Hence, we only sample the random walks once in each epoch and reuse this collection in all layers, i.e., each module transforms them into module-sper module--pecificc feature matrices with different feature values (first three sub-matrices) but reuses the same random walks for that. This also depicted in Figure 3 with the same collection Jmmm of random walks passed to each layer. We further describe how to sample the random walks more efficiently using boundary maps.
The structure of a simplicial complex can be encoded by boundary maps Bt, which record the incidence relations between (I: - 1) -immplless and k-simplices (Hatcher 2002). Rows and columns of B, are indexed by (A: 1)-simplices and by k-simplices, respectively. The entry (i.j) is set to 1 or 0 depending on whether the i-th (k: si-simplex is incident to the j-th k-simplex. Thus, the

---

Published as a conference paper at ICLR 2024
Simplicial Complexes
Paper
Authors
Citatonn
B
Graphs
GNN
MPSN
20
D
A,
35
45
B.
10
CRaWi
SCRaW]
C,
15
B.
A
10
C
Expressiveness relations of SCRaWI to other neural network models. SCRaWI and MPSN are strict extensions of their graph counterparts CRaWI and message- passing GNNs, respectively, and their expres- sive power is incomparable.
Figure 4:
Figure 5: Example of citation simplicial complex. Each vertex represents an author and connections (edges and triangle) indicate co- authorship. The value of the connection is the total number citations of the papers the au- thors have written together.
matrix B1 is the unsigned vertex-to-edge incidence matrix, and Bg is the edge-to-triangle incidence matrix. For ease of notation, we define B,- B Further define S hstack( ( BB+11).
For uniform connection sampling on the simiplise we can efficiently sample the next connection, j from Sk, as the connections for the i-th k-simplex are precisely those with value one in (Bx)_, and (Bk+1) ),- If the sampled index j S 7 the walk transitions over the face j. otherwise over the coface j - 7 The next walk simplex can then be sampled uniformly from S
For uniform neighbor sampling, compute A B Bx + B BB and A sign(Aa). The neighbor of the i-th k-simplex can be sampled uniformly at random from (As)
EXPRESSIVE POWER
It is known that the expressive power message-passing GNNs with anonymous inputs is limited by the WL graph isomorphism test (Morris et al. [2019] Xu et al. [019 Morris et al. (2023) and thus such GNNs cannot distinguish between non-isomorphic graphs that cannot be separated by color refinement. In (Bodnar et al. [20216] Definition 5) a simplicial version of the WL test (SWL) was introduced and it was shown that the expressiveness of gressage-passingg simplicial networks (MPSN) is limited by this test. The following theorem asserts that for SCRaWI this analysis does not apply.
Theorem 1. The expressiveness of SCRaWI is incomparable to the expressiveness of an MPSN, i.e., there are simplicial complexes that can be distinguished by SCRaWl but not by MPSN and vice versa.
Proof. Note that when applied to 1-simplicial complexes and considering vertex colorings, SWL is equivalent WL and by extension, the expressiveness MPSNs corresponds to the expressiveness of GNNs (Bodnar et al. 2021b). Note also that SCRaWI is equivalent to CRaWI when applied to 1-simplicial complexes. T'hus the theorem follows from Tönshoff al. 2023 Theorem 1).
The expressiveness inclusions of the various architectures are shown Figure 4 This implies that
the expressiveness of SCRaWI is incomparable to the WL test and its simplicial counterpart.
5 EXPERIMENTAL RESULTS
We evaluate SCRaWI on variety of datasets and compare it to other simplicial neural networks" Following the training procedure Dwivedi et al. (2023), we use the Adam optimizer with an initial learning rate 10-3 The learning rate decays with factor of 0.5 if the validation loss does not improve for 10 epochs. Training is stopped once the learning rate drops below 10-6, For full list of hyperparameters and more detailed description of the training setup, see Appendix
5.1 SEMANTIC SCHOLAR CO-AUTHORSHIP NETWORK
Following Ebli et al. 2020), we use SCRaWI to impute missing citation counts for a subset of the Semantic Scholar co-authorship network. Vertices represent distinct authors, and paper with k: +
Source code and datasets availahle httph:t/pp/ptt.... wwth htttchhaachen..dd//e http:///......iicaaccaacaaaaattt sscrawl
7

---

Published as a conference paper at ICLR 2024
Validation Accuracy
Validation Accuracy
0.8
Percentage Missing
0.6
0.1
0.8
SCNN
0.2
0.4
SAN
0.3
0.2
0.4
0.6
MPSN
0.5
SCRaWI
100
200
300
400
0.1
0.2
0.3
0.4
0.5
Epoch
Percentage Missing
Figure 6: Imputation accuracies on the Semantic Scholar dataset with different percentages of missing citations. We report the mean and standard deviation over 10 runs. Left: Training progress of SCRaWI. Right: Accuracies of SCRaWI, SIN (MPSN), SAN, and SCNN for each simplex order as more and more data is missing. Increasingly lighter lines indicate higher simplex orders.
authors implies a k-simplex connecting these authors in the network (see Figure 5) The value on a k-simplex is the sum of citations of the papers written together by the respective ie + 1 authors (including papers with more than these authors). Citation values are randomly deleted at a rate of 10%, 20%, 30%, 40%, and 50% and replaced by the median of the remaining known citations.
We report the imputation accuracies of SCRaWI in Figure (left) and compare them with k- simplex2vec (Hacker) 2020). SNN (Ebli al. 2020), SCNN (Yang al. 2022a), SAT (Goh ctt al. 2022), SAN (Giusti et al. 2022), and the MPSN architecture presented in (Bodnar et al. 2021b). For readability, omitted the results for s-simplex2vee, SNN, and SAT in Figure 6 (right). Full results are available in Table iin the appendix. Following the previous work, a citation value is correctly imputed if the prediction is within =5% the true value. We repeat each experiment 10 times and report the mean and standard deviation for missing rates of 10%, 20%, 30%, 40,, and 50%. The left plot shows the overall accuracies of our model the different missing rates while the right plot compares the accuracies of the different models on individual simplex orders.
We see that SCRaWI reaches accuracies of 95% to 99% for all missing rates after about 175 epochs. Across all experiments, we consistently see drop in accuracy around epoch 30 to 50, which is then overcome. We forced a minimum of 100 epochs to avoid early stoppings within this drop. We also see that SCRaWI is on par with MPSN and outperforms all other models for most missing rates and simplex orders. Especially for missing rates above 10%, the improvement substantial. addition, imputation accuracies are more consistent across different simplex orders for SCRaWI, whereas, for the other models, the accuracy declines faster for smaller simplices than for higher-order simplices.
5.2 SOCIAL CONTACT NETWORKS
In a second set of experiments, we perform vertex classification on the primary-school and high- school social contact datasets (Stehlé et al. 2011 Chodrow et al., 2021). The datasets constructed based on students' interactions recorded by wearable sensors. Vertices represent students, and a simplex corresponds to a group of students that were in proximity to each other given time. Vertices are labeled with the classroom to which the student belongs, resulting in a total of 12 classes for the primary school dataset and 10 classes for the high school dataset.
We use a cross cross-entropy loss to train the network on the dataset with 40% of the vertex classes missing and report the validation accuracy of the imputed classes in Figure For the primary school dataset, SCRaWI reaches an average accuracy of 0.927 + 0.026 after about 160 epochs, and for the high school dataset a perfect accuracy of 1.0 0.0 after about 150 epochs.
We compare this result with the performance of MPSN on the same datasets (middle). Although MPSN generally converges faster our experiment, it only achieves an average accuracy of 0.727 + 0.033 and 0.943 + 0.033 for the primary and high school dataset, respectively, and is thus outperformed by SCRaWI, especially on the primary school dataset. Comparisons with SCNN,
cspecalysy
"The SNN paper used threshold of +00% which was later changed to +5%.
8

---

Published as a conference paper at ICLR 2024
SCRawl
MPSN
CRaWI
Validation Accuracy
0.8
0.6
0.4
pcimary-school
0.2
high-school
50
100
150
0
20
60
80
100
0
50
100
150
200
Epoch
Epoch
Epoch
Figure 7: Vertex classification accuracies of SCRaWi W1, MPSN, and CRaWI on the social contact datasets. We report the mean and standard deviation of the validation accuracies over runs.
k-simplex2vec and some hypergraph models can be found in Table 2 in the appendix. The other simplicial approaches did not perform well on the datasets, with SCNN reaching an average accuracy of 0.166 + 0.056 for the primary school dataset and 0.228 + 0.075 for the high school dataset. k-simplex2vec reached an average accuracy of 0.398 0.011 and 0.308 + 0.019 for the primary and high school dataset, respectively. The hypergraph approaches performed consistently 0.9 accuracy on the high school dataset, 10 percent below our result. For the primary school dataset, CAt- Aalk marginally outperformed SCRaWI with average accuracy of 0.932 + 0.025.
most around
Importance of Higher-Order Interactions We repeated the same experiment using the graph- based CRaWI architecture on the underlying graph skeleton of the datasets, i.e., the graph only records pairwise proximities between students but does not record whether interactions between more than two people occurred. Keeping all other parameters the same, we found that CRaWI performance is clearly worse than SCRaWl on both datasets (see Figure 7. This highlights the importance of higher-order interactions in the dataset and the ability of SCRa WI to capture them.
CONCLUSION
We proposed a simplicial neural network architecture SCRaWI based on random walks and ID convolutions. The architecture builds the idea of (Tönshoff et al. 2023) use sampled random walks for graph learning tasks. We demonstrated that these ideas can be extended to work on simplicial complexes if carefully adjust the notion of random walks. We showed that the resulting architecture outperforms existing simplicial neural network architectures on a co-authorship network.
Other Complexes While we focused on simplicial complexes this work, the architecture can naturally be applied to other types of complexes such as (regular) cell complexes without any changes. Informally, a cell complex is a collection of cells, where each cell's s boundary is also in the complex. Starting with points O-cells, 1-cells as lines with their two endpoints their boundary, k-cell defined such that its boundary consists 2-cell with boundary consisting of a set of lines. This highlights the difference to simplicial complex, as a 2-simplex must form a triangle, while a 2-cell may be any polygon.
collection of (I: - 1)-cells. A polygon for instance is
Future Work The empirical results demonstrate the potential of the proposed architecture. However, there are several avenues for future work worth exploring. First, we plan to investigate the performance of SCRaWl in broader set of applications. Simplicial complexes have gained a lot of interest for edge flow problems, and it remains to be seen how well SCRaWl performs on these tasks. While we have paid special attention to the computational complexity in our implementation, due to the many simplices and hence walk feature matrices in a simplicial complex compared to graph, expect that using SCRaWI WI with one random walk per simplex will not scale sufficiently. Approximation guarantees for different sampling schemes thus an interesting direction for future work.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We acknowledge funding by the Ministry of Culture and Science (MKW) of the German State of North Rhine- Westphalia ("NRW Rtickkhhpprogrmmn)) and the European Union (ERC, HIGH- HOPeS, 101039827). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency, Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp- 1198-1211, 2020. (01/300015/333773333333333
Federico Battiston and Giovanni Petri. Higher-Order Systems. Springer International Publishing, 2022. /0////00077770--000000000
Ali Behrouz, Farnoosh Hashemi, Sadaf Sadeghian, and Margo Seltzer. CAT-Walk: Inductive Hyper- graph Learning via Set Walks. In Thirty Conference Neural Information Processing Systems, 2023.
CFCrr// d=
Austin R Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, 115 (48):E1 1221-E112222111 2018. 1700.10077/paa..1800000
Jacob Charles Wright Billings, Mirko Hu, Giulia Lerda, Alexey N Medvedev, Francesco Mottes, Adrian Onicas, Andrea Santoro, and Giovanni Petri. Simplex2vec embeddings for community detection in simplicial complexes. arXiv preprint arXiv:1906.09000 2019.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Liò, Guido F Montufar, and Michael Bronstein. Weisfeiler and Lehman Go Cellular: CW Networks. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Curran Associates, Inc., 2021a
Processing Systems, volume 34, pp. 2625-2640.
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lió, and Michacl Bronstein. Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1037-1037. PMLR, 18-24 Jul 2021b. URL
mlr htt.://......esss/33////aaaaaa
html
Glen E. Bredon. Topology and Geometry. Graduate texts in mathematics. Springer-Verlag. New York, 1993.
Chaofan Chen, Zelei Cheng, Zuotian Li, and Manyi Wang. Hypergraph Attention Networks. In 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 1560-1565, 2020. 10010:110///nssCmm00055...0..000
Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovie. You are AllSet: A Multiset Func- tion Framework for Hypergraph Neural Networks. In International Conference Learning Representations, 2022. htt::ttts://////tt httptttpps//ppeereiiewe (ttpearrwweeeeeeeeeeorroreeneaae http://rruumii..ippppttt1yyyy
Philip S Chodrow, Nate Veldt, and Austin R Benson. Generative hypergraph clustering: From blockmodels to modularity. Science Advances, 2021. doi T0..126/sciadv.abh
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. Journal of Machine Learning Research, 24(43):1 2023. URL http:// jmlr org/ pwwpps/ppppppeeee/ 0567 .html
Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial Neural Networks. In TDA & Beyond, 2020.
10

---

Published as a conference paper at ICLR 2024
Moshe Eliasof, Eldad Haber, and Eran Treister. pathGCN: Learning General Graph Spatial Operators from Paths. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 Proceedings of Machine Learning Research, pp. 5891. PMLR, 17-23 Jul 2022. URL URI.https:: ptttpps:/prroeed.. ngs. ml www../ressllll.................. 62/ 1ttp was.l//fe/llllaaaalea html
Lorenzo Giusti, Claudio Battiloro, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa. Simplicial Attention Neural Networks. arXiv preprint arXiv:2203.074433 2022.
Christopher Wei Jin Goh, Cristian Bodnar, and Pietro Lio. Simplicial Attention Networks, In ICLR 2022 Workshop on Geometrical and Topological Representation Learning. 2022.
Celia Hacker. k-simple22ve:: simplicial extension of node2vec. In TDA & Beyond, 2020.
Mustafa Hajij. Mathilde Papillon, Florian Frantzen, Jens Agerberg, Ibrahem AlJabea, Ruben Ballester, Claudio Battiloro, Guillermo Bernárdez, Tolga Birdal, Aiden Brent, Peter Chin, Sergio Escalera, Odin Hoff Gardaa, Gurusankar Gopalakrishnan, Devendra Govil, Josef Hoppe, Maneel Reddy Karri, Jude Khouja, Manuel Lecha, Neal Livesay. Jan Meißner, Soham Mukherjee, Alexander Nikitin, Theodore Papamarkou, Jaro Pr'ilepok, Karthikeyan Natesan Ramamurthy, Paul Rosen, Aldo Guzm an-S' aenz, Alessandro Salatiello. Shreyas N. Samaga, Michael Schaub, Luca Scofano, Indro Spinelli, Lev Telyatnikov, Quang Truong, Robin Walters, Maosheng Yang. Olga Zaghen, Ghada Zamzmi, Ali Zia, and Nina Miolane. Topox: A suite of python packages for machine learning topological domains, 2024.
Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002.
Sajjad Heydari and Lorenzo Livi. Message Passing Neural Networks for Hypergraphs. Elias Pimenidis, Plamen Angelov, Chrisina Jayne, Antonios Papaleonidas, and Mehmet Aydin (eds.), Artificial Neural Networks and Machine Learning ICANN 2022, pp. 583-592, Cham, 2022. Springer Nature Switzerland. ISBN 978-3-031-15931-2
Di Jin, Rui Wang, Meng Ge, Dongxiao He, Xiang Li, Wei Lin, and Weixiong Zhang. RAW-GNN: RAndom Walk Aggregation based Graph Neural Network. In Luc De Raedt and Luc De Raedt (eds.), Proceedings of the s1 International Joint Conference on Artificial Intelligence, IJCAI 2022, ICAI International Joint Conference on Artificial Intelligence, pp. 2108-2101111111 International Joint Conferences on Artificial Intelligence, 2022.
Alexandros Keros, Vidit Nanda, and Kartic Subr. Dist2Cycle: Simplicial Neural Network for Homology Localization. Proceedings of the AAAI Conference Artificial Intelligence, 36(7); 7133-7142, Jun. 2022. doi;10.1609/ wwt.////aa............. 206677
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019. doi 1609//aaiaaa v33101 333001330316660
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story far, 2023.
Sayan Mukherjee and John Steenbergen. Random walks on simplicial complexes and harmonics. I0. 10.00//sa.2224
Random Structures & Algorithms, 49(2))379-405, 2016.
Giannis Nikolentzos and Michalis Vazirgiannis. Random Walk Graph Neural Networks. In
H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 16211-16222. Curran Associates, Inc., 2020.
Ori Parzanchevski and Ron Rosenthal. Simplicial complexes: spectrum, homology and random 501rriimmm,,0022225222200 20(2):25--21,, 2017. doi 10.1000//sa.20657
walks. Random Structures & Algorithms,

---

Published as a conference paper at ICLR 2024
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, Hegh-Performance Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, F. Fox, and R. Garnett (eds.), ). Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
T. Mitchell Roddenberry, Nicholas Glaze, and Santiago Segarra. Principled Simplicial Neural Networks for Trajectory Prediction. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9020-9029. PMLR, 18-24 Jul 2021. URL https: htttpp::/proceedingg
mlr. www.ppess.vlll. wttsss/vv3///ee https///111///ddeeeeerelll./ htm
T. Mitchell Roddenherry, Michael T. Schaub, and Mustafa Hajij. Signal Processing on Cell Complexes. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8852-8856, 2022. 0TA..0.0090AAASSP9992222..0.0..0
Michael T. Schaub, Austin R Benson, Paul Horn. Gabor Lippner, and Ali Jadbabaie. Random Walks on Simplicial Complexes and the Normalized Hodge I-Laplacian. SIAM Review, 62(2):353-391, 2020. 11/.1113///M0200000
Michael T. Schaub, Yu Zhu, lean-Baptiste Seby, T. Mitchell Roddenberry, and Santiago Segarra. Signal processing on higher-order networks: Livin' on the edge... and beyond. Signal Processing, 187:108149, 2021. ISSN 0165-1684. doi wti.1016/.siipro22221.100
Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Fran-François Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne Régis, Bruno Lina, and Philippe Vanhems. High-Resolution Measurements of Face-to-Face Contact Patterns in a Primary School. PLoS ONE, 6(8):22377, 2011. Toojool 00133003
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference on Learning Representations, 2019. URL. https
//openreieww net. wtw.e//oooommdd/eeee.t.. A55kmm
Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Maosheng Yang, Elvin Isufi, and Geert Leus. Simplicial Convolutional Neural Networks. In ICASSP 2022 2022 IEEE International Conference Acousticss Speech and Signal Processing (ICASSP), pp.
IEEE, 2022a. 00I1001100ICAASSP222200000000000
Ruochen Yang, Frederic Sala, and Paul Bogdan. Efficient Representation Learning for Higher- Order Data With Simplicial Complexes. In Bastian Rieck and Razvan Pascanu (eds.), Proceedings of the First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, pp. 13:1-13:21. PMLR, 09-12 12 Dec 2022b. URL https: httts:://proceedingg.. mlx...mr..... presss
v198/yang22a.nct .hml
Cai Zhou, Xiyuan Wang, and Muhan Zhang. Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. [itppp////pggeeeer.....ee////rds
12

---

Published as a conference paper at ICLR 2024
Table 1: Imputation accuracies on the Semantic Scholar dataset with varying percentages of missing citations. We report the mean and standard deviation of the validation accuracies over 10 runs. We compare SCRaWl the simplicial neural networks SNN, SCNN, SAT, SAN, and MPSN as well as to the representation learning al algorithm 2-semplex2vec.
Validation Size
Simplex Order
Method
RO 352
11 1474
2g 3285
2g 5019
114 5630
1ig 4547
4-simple22vac
0.02 + 9.014
0.07 + 0.013
0.40 + 0.040
U.78 + 0.021
0.96 + 0.007
0.33
SNN
0.91 +: 0.003
0.91 1: 0.002
0.90 1: 0.004
0.91 4: 0.004
0.90 1: 0.916
0.90
+: 0.008
SCNN
0.91 1: 0.004
0.91 1: 0.002
0.91 1: 0.002
0.92 1: 0.001
0.92 1: 0.002
0.92 1: 0.002
10%6
SAT
0.18 + 0.000
0.31 + 0,000
0.28 + 0.001
0.34 + 0.001
+ 0.001
+ 0.001
SAN
0.91 0.004
0.95
0.019
0.95 0.019
0.97 0.016
0.98 0.009
0.007
SIN (MPSN)
0.99 1: 0.004
0.99 1 0.003
0.99 1 0.002
0.97 1: 0,008
0.97 1 0.004
0.97 1: 0.003
SCRaW1
0.99 + 0.085
1.00 + 0.009
0.98 + 0.020
0.93 + 0.138
0.90 + 0.202
0.97 + 0.020
0.03 # 0.023
0.08 + 0.013
0.46 + 0.014
0.81 + 0.021
0.95 + 0.009
0.92 : 0.079
SNN
0.81 + 0.006
0.82 + 0.003
0.82 + 0.005
0.83 + 0.004
0.82 + 0.012
0.83 + 0.007
SCNN
0.007
0.003
0.003
0.002
+ 0.002
0.002
20%
SAT
0.18 + 0.000
0.20 + 0.000
0.29 + 0.001
0.35 + 0.001
0.50 + 0.001
0.58 + O. 001
SAN
0.82 1: 0.006
0.91 1: 0.024
0.82 1 0.008
0.96 1 0.004
0.96 1 0.013
0.97 1: O. 009
SIN (MPSN)
0.99 +: 0.005
0.99 4: 0.002
0.99 + 0.004
0.99 + 0.008
0.98 + 0.006
O. 0.99 004
SCRaWI
+
0.008
0.013
k-simplex2vee
0.01 + 0.008
0.07 + 0.003
0.41 + 0.019
0.79 + 0.020
0.95 + 0.006
0.92 O. D88
SNN
0.72 + 9.005
D.73 0.004
D.73 0.QU5
0.73 + 0.002
U.75 + 0.002
0.75 + D63
SCNN
0.72 1: 0.005
0.73 1: 0,004
0.74 1: 0,003
0.75 1: 0,002
0.76 1: 0.002
0.77 1: 0.002
30%5
SAT
0.19 + 0,000
D.33 + 0.001
0.25 + 0.001
0.33 + 0.000
0.47 + 0.001
0.53 + 0.
SAN
0.75 + 0.021
+ 0.021
+ 0.008
+ 0,004
+ 0,005
+ 0.005
(MPSN)
0.99 0.004
0,99 0.002
0,98 0.004
0,98 0,009
0.99 0.001
0,98 0.001
SCRaWI
0.98 + 0.015
0.99 + 0.004
0.99 + 0.003
0.98 + 0.016
0.98 + 0.012
O. 0.98 + 0.010
2-simplex2vae
0.01 + 0.003
0.08 + 0.007
0.46 + 0.024
0.77 + 0.016
0.92 + 0.008
0. 0.00 + O. 085
SNN
0.63 + 0.007
0.64 + 0.003
0.65 + 0.003
0.66 + 0.004
0.67 + 0.009
0.67 + O. DO8
SCNN
0.63 4: 0.006
0.64 1: 0.003
0.65 + 0.002
0,66 + 0.002
0.67 1: 0. 0.003
0. 69 1: 0. 002
40%
SAT
0.000
0.000
0.000
0.001
+
SAN
0.87 1: 0.019
0.85 1: 0.028
0.82 1 0.008
0.91 1 0.009
0.93 1 0.011
0. 9.95
1: O. 016
SIN (MPSN)
0.98 : 0.002
0.99 1 0.001
0.98 + 0.003
0.98 + 0.007
0.98 + 0.002
O. 98 + 008
SCRaW1
0.98 + 0.009
0.98 + 0.009
0.97 1 0.021
0.97 + 0.028
0.97 + 0.012
0.98 0.013
2vve
0.07 + 0.015
0.07 + 0.008
0.36 + 0.016
0.80 + 0.022
0.91 + 0.007
0.95 + 0.003
SNN
0.54 + 0.007
0.50 + 0.0UG
0.56 + 0.003
+ 0.003
+ 0.004
+ D.0
SCNN
0.54 9.006
0.55 0,004
0.56 0,003
0.58 0,003
0.59 0,003
0.002
SAT
0.19 + 0.000
0.30 + 0.001
0.22 + 0.000
0.32 + 0.001
0.43 + 0.000
0.48 + 0.001
SAN
0.61 + 0.019
0.79 + 0.043
0.82 + 0,008
0.88 + 0.015
0.92 + 0.007
0.94 + U.D11
SIN (MPSN)
0.94
0,004
0.97 + 0.006
0.97 0.008
0.002
0.004
0.009
SCRaWi
0.95
+ 0.029
0.98 + 0.009
0.96 + 0.009
0.98 + 0.032
0.97 + 0.014
0.90 + 0.035
SNN and SCNN have been repurted by Ving 2022
SAT and SAN have been reported Glusti al X00
A TRAINING DETAILS AND RESULTS
For all experiments, we use the Adam optimizer with an initial learning rate of 10 The learning rate is reduced by factor of 0.5 if the validation loss does not improve for 10 epochs. Training is stopped once the learning rate drops below 10-6
The walk length E is the primary hyperparameter that determines the receptive field of the model. As the citation counts in the Semantic Scholar dataset can be imputed well with only local information, we choose walk length of 5 for this dataset. On other datasets, the model is trained with walk length of 50. The walk length can be increased independently in prediction, but we did not make use of this option in our experiments.
For the Semantic Scholar dataset, we ran SCRaWI modules on simplex orders k E (o....... 5), i.e., simplices of order 6 appear only as static coface features in the random walks and simplices of order 7 do not influence the model. Using uniform connection sampling, we computed m = Σn n2 random walks, i.e., one random walk for each simplex of order k E (O.....5), 5). While SCRaWI modules can be configured individually for each simplex order and each layer, we found that the same configuration for all modules works well for this dataset: Each module is configured with a local window size of s = 4, a kernel size of deem = 8, a hidden feature size of d = 32, and mean pooling operation. Complete results for the semantic scholar experiments are given in Table [
For the social contact datasets, we use 4 layers and run SCRaWI modules simplex orders k E {O..... 3). We compute one random walk for each simplex. Each SCRaWI module is again configured identically with local window size of s = 8, a kernel size of dyem 8, hidden feature size of d = 128, and a mean pooling operation. The final vertex embeddings are fed into a 2-layer MI. with ReLU activation. Complete results for the social contact experiments are given in Table
13

---

Published as a conference paper at ICLR 2024
Table 2: Vertex classification accuracies on the social contact datasets.
Dataset
primary-school
high-school
Rg
242
327
71
8317
5818
Dataset
712
5139
2370
Details
71
381
238
Target Classes
12
10
Random Baseline
0.107
0,135
k-simplex2ven 2vec"
0.398 + 0.011
0.308 + 0.019
SCNN
0.166 0.056
+ 0.228 0.075
Simplicial Methods
SIN (MPSN)
0.727 0.043
= 0.033
CRaWI
0.415 = 0.030
0.823 = 0.042
SCRa WI
0.927 = 0.026
1.000 0.000
HyperGCN
0.852 0.031
0.849 + 0.036
Hypergraph
AllSeTTransformer
0.898 + 0.026
0.908 = 0.031
Methods
CAt-Walk
0.932 0.025
0.907 = 0.050
For vertex classification, k-simplex2vec is oblivious to any higher-order connection beyond edges.
Results on hypergraphs have been reported by Behrouz et al. 2023
Table 3:
List of hyperparameters and training setup used for each experiment.
Parameter
Semantic Scholar
Social Contacts
Walk Length l
5
50
Sampling Method
uniform connection
uniform connection
Number of Layers
3
4
Max. Simplex Order K
5
Local Window Size s
4
8
Kernel Size dRem
8
8
Hidden Feature Size d
32
32
Pooling
mean
mean
Total number of
171k
132k
Trainable Parameters
Optimizer
Adam; LR = 10
LR Scheduler Stopping Criterion
Reduce on plateau: factor 0.5: patience 10
LR 10
A full list of hyperparameters used for each experiment is given in Table 3 The model has been implemented using PyTorch (Paszke al. 2019) and TopoX (Hajij et al. 2024). We adapted the code from Tönshoff et al. 2023) to implement SCRaWI.
We used Bodnar al. 222th) reference implementation for MPSN and conducted the experiments using the author's s default parameters with 4 layers, 128 hidden features, ReLU nonlinearities, and sum aggregations. Experiments for SCNN were conducted using the implementation provided by TopoX with 3 layers, 64 hidden features, and ReLU nonlinearities. We used our own implementation of k-simplex2veec
B ABLATION STUDY
In this ablation study, we investigate the influence different hyperparameters and other aspects on the performance of SCRaWI. For all experiments, the training setup and hyperparameters not under
14

---

Published as a conference paper at ICLR 2024
Validation Accuracy
0.93
0.98
0.5
0:45
primary-school
high-school
2
8
20
40
Baseline
Upper
Lower
Local Window Size
Walk Length &
Figure 8: adjacency on the performance of SCRaWI. Middle: Influence of the local window size s. Right: Influence of the walk length We report the mean and standard deviation of the validation accuracies over 5 runs.
Ablation study on the social contact datasets. Left: Influence of upper and lower
investigation are set to the same values as in the main experiments. Figure & shows the results of the ablation study on the social contact datasets.
Lower vs. Upper Adjacency During random walk, the next simplex can either be reached by traversing over face or a coface of the current simplex. We are interested the impact of either form of adjacency, i.e., we compare the performance of SCRaWI when using only lower adjacency or only upper adjacency. For simplices that don't have a face or don't have a coface, respectively, the random walk stays at the current simplex. We make the exception that for node-level walks, upper adjacency over edges is always allowed, as otherwise, no meaningful walks would be possible.
For the primary school dataset, performance 0.889 + 0.063 than only using lower adjacency with 0.454 + 0.099. this case, only using upper adjacency is thus only marginally below the baseline performance of 0.927 + 0.026. On the easier-to- to-learn high school dataset, the difference between using only upper or lower adjacency is smaller with 0.994 0.009 0.975 + 0.009, compared the baseline with 1.0 + 0.0.
that only using upper adjacency yields significantly better
These results support our claim that - at least for these datasets higher-order interactions give additional insight into the structure of the dataset and methods that capture these (higher-order) structures can perform better.
Influence of Local Window Size 8 The local window s is a parameter that influences which structural features of the input simplicial complex are visible to the model. We thus expect that larger windows improve the prediction performance while also increasing the computational complexity.
We validate this hypothesis by training SCRaWI on the social contact datasets with different local window sizes 8 E {l,...., 8J. As expected, we see that the prediction performance SCRaWI improves with larger windows: For the primary school dataset, the performance increases almost monotonically from 0.571 + 0.079 with s = to 0.927 + 0.026 with s = For the easier-to-leam high school dataset the performance is only marginally worse with 0.977 + 0.006 for vs. 1.0 0.0 for 8.
Influence of Walk Length Similar the local window size s, we expect that larger walk lengths l positively influence the prediction performance of SCRaWI, as longer walks ensure that important structural features of the simplicial complex are captured and processed by the model.
To that end, we trained SCRaWI on the social contact datasets with different walk lengths & e (5. (.....,0).. The prediction performance again improved almost monotonically with increasing walk lengths for both datasets, with the high school dataset reaching accuracies above 0.98 for 2 25 already. For the primary school dataset, the performance reached its best accuracy of 0.927 + 0.026 only for & 50.
note that the choice of walk length and window size s has a considerable impact on computational cost of the model and its value should be chosen carefully to balance predictive performance and computational complexity.
15


Reviews:
[{"review_id": "AOixfP3lBq", "reviewer": "Reviewer_6GSS", "summary": "This paper proposes a new learning method on simplicial complexes based on random walks and 1-D convolution encodings.", "questions": "See Weaknesses.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea of using random walks to tackle the high complexity of learning on simplicial complexes is a natural idea. The overall design also looks reasonable to me.\n2. Experiments show that the proposed method outperforms some of the most recent methods.", "weaknesses": "1. Compared to this work, a recent work [1] seems to provide more principled insights into exactly the same topic. Can the authors discuss more of its edge over this work?\n\n2. The experiments are conducted on a relatively limited number of datasets. I would hope to see more datasets from diverse domains being used.\n\n[1] Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes, NeurIPS 2023", "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": "uaXHP5F7kc", "reviewer": "Reviewer_WBPx", "summary": "The paper proposes a method called SCRAWL which explores simplicial complexes-based learning representations for graph datasets using random walks and 1D convolution on simplices. This work is built on top of the recent work CRAWL which uses random walks and 1D conv directly on graphs. The authors performed two tasks vertex classification and missing citation counts on two benchmark datasets.", "questions": "Why are walks computed on the fly or they are just sampled on the fly? Can’t we precompute the walks which is just one time processing before training?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well presented and motivated. \n2. Additional information from simplices seems to improve embeddings. The results are interesting. \n3. An ablation study is provided to show the robustness and compare it against existing works. \n4. The expressivity is equivalent to CRAWL. So, the theorem by CRAWL holds for this too.", "weaknesses": "1. The major concern I could see is memory and computation as it contains the matrices for k levels of simplices. And, each walk consists of six matrices. \n2. It is not clear how long the walk is and how many walks are computed for each of the k-simplices. Assuming m is for the collection of all walks from all k-simplices. \n3. Why are walks passed in every layer? Is it not enough to use it only at the input? \n4. How are the output from k-simplices combined for the final output? I could see three different outputs in Fig. 3. \n5. Fig 6. results are on par with MPSN. Justification of why it works differently on two different kinds of datasets would be much appreciated. Results are improved significantly for social networks although it.", "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": "PaVadeR7qQ", "reviewer": "Reviewer_Wmrd", "summary": "The paper presents SCRaWI, a neural network model to encode simplicial complexes based on higher-order random walks on simplices. SCRaWI samples several higher-order random walks followed by fast 1D convolutions to learn the structural properties of the Simplicial Data.", "questions": "Please see the Weaknesses. In summary, my suggestions are here: Please add \n\n1. more discussions about existing methods [1, 2]. Also please discuss [3] and its differences with your method.\n2. more datasets, different experimental settings, and hypergraph learning-based baselines. \n3. ablation studies to show the contribution of each component. \n4. scalability and efficiency evaluation.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow. Also, it is well-organized with enough illustrative figures. The proposed method is simple, yet potentially powerful, which makes it feasible for large and real-world cases. More, specifically, the model design allows choosing the number of sampled random walks as a hyperparameter, which provides a trade-off between computational cost and the expressivity of the model. Also, using fast Fourier transforms to perform convolutions on sampled walks is an interesting idea, which potentially can improve efficiency and training time.", "weaknesses": "The paper has missed some important related studies or detailed discussions about them. As an example, there are several random walk-based methods [1, 2] in a simple graph, which uses a similar idea. While they have been briefly mentioned, there are some important questions about them that are not discussed in the paper. Is there any connection between SCRaWl and these methods? Or is SCRaWl the extended version of these studies to higher-order data? A very similar study on higher-order graphs is CATWALK [3], which is a hypergraph learning method that similarly uses higher-order random walks to learn higher-order patterns. I think, given the fact that hypergraphs can be seen as a general case of simplicial complexes, their walk sampling is exactly the same as this work, which limits the novelty of this paper's idea and its model design.\n\nThe proposed method is simple, which is a desirable property **if** the effectiveness of the method is theoretically or experimentally shown. That is, the novelty of the model architecture is limited, so it is expected that extensive experimental or theoretical results will support the method's performance. However, in the paper, the experimental study is very limited, e.g.:\n\n1. There are only three datasets from two different domains. Please note that co-authorship networks and social networks usually have similar properties so it would be much better if the authors could provide more datasets with different domains, specifically in drug-drug or chemical networks (NDC, and/or NDC Substances), and communication networks (Email Enron). \n \n2. There is a lack of ablation study on the method architecture. Accordingly, it is not clear what is the contribution of each component of SCRaWl. How using a simple random walk instead of a higher-order random walk can affect the performance? How does each of the six features contribute to the performance of SCRaWl?\n\n3. The main motivations and claims in the paper are not supported by experiments. For example, when the main motivation is to address the inefficiency of the existing methods, I think it is needed to see how SCRaWl performs compared to existing methods in terms of time and how proposed components are improving the efficiency. \n\n4. Hypergraphs are another paradigm to represent higher-order interactions. There is a lack of comparison with state-of-the-art hypergraph learning methods [3, 4, 5]. \n\n\n\nIn addition to the above points, as discussed in the \"Introduction\" section, there is a trade-off between computational cost and the power of SCRaWl. It would be great if you could show this trade-off in the experiments as well. \n\n  \n  $$ $$\n\n\n[1] Random walk graph neural networks. NeurIPS 2020.\n\n[2] Walking out of the Weisfeiler Leman hierarchy: Graph learning beyond message passing. TMLR 2023. \n\n[3] CAT-Walk: Inductive Hypergraph Learning via Set Walks. NeurIPS 2023.\n\n[4] Teasing out missing reactions in genome-scale metabolic networks through hypergraph learning. Nature Communications 2023.\n\n[5] You are allset: A multiset function framework for hypergraph neural networks. ICLR 2022.\n\n\n\n$ $\n\n$ $\n\n\n--- \n--- \n``Post Rebuttal``\n--- \n--- \n--- \n\nI thank the authors for their response. \n\nMy concerns remain unaddressed in the rebuttal phase. Specifically,\n\n* There is a lack of discussion with very similar works (e.g., [2]). As mentioned in my initial review, the existing discussion, which briefly mentioned that ``here we take inspiration from random walk-based graph neural networks on graphs (Tönshoff et al., 2023)`` is not enough. To my understanding, the idea of using 1D Convolutions is previously discussed in [2], and the only remaining contribution in this paper is to design higher-order random walks on simplicial data. The proposed walk also is similar to the walk that is previously discussed in [3]. The only difference is that the random walk in [3] is temporal, which can be simply adjusted and so be restricted to a single timestamp. The authors claim that [3] has been published after the submission deadline, while as far as I understood [3] has been available from Jun 2023 (almost 3-4 months before the deadline). \n\n* I understand that the novelty is subjective and coming up with a model that combines existing studies but provides new insights is significant. However, I couldn’t find enough experimental evaluations to support the paper, and my request to perform experiments on more datasets remains unaddressed. More specifically, **(1)** The current experimental evaluation is limited to only three datasets (two of which come from the same domain). There are several benchmark datasets that are publicly available and are suitable for the experimental settings used in this paper. **The authors didn’t respond to this comment.**  **(2)** There is a lack of comparison with some important baselines (e.g., [3, 5]). The authors reported the results provided in [3], but it is not clear to me that the experimental setting used in [3] is the same as this paper. Is the hyperparameter tunning procedure for all the methods the same? Is the preprocessing step on the datasets the same? I think reporting the results from another work is unfair due to different experimental setups, data splitting, etc.  **(3)** The provided results in the appendix show the sensitivity of the method to hyperparameters. The authors' response did not address the concern about the lack of an ablation study. Specifically, my two questions in the initial review remain unaddressed: (i) How can using a simple random walk instead of a higher-order random walk affect performance? (ii) How does each of the features contribute to the performance of SCRaWl? (iii) What is the contribution of 1D Convolutions? What would happen if we use a simple linear layer?\n\n* As I mentioned in the initial review, the main motivations and claims in the paper are not supported by experiments. **The authors didn’t respond to this comment.** More specifically, when the main motivation is to address the inefficiency of the existing methods, I think it is necessary to see how SCRaWl performs compared to existing methods in terms of time and how proposed components are improving efficiency. \n\n\n--- \n$$ $$\n\n**After the rebuttal phase and also discussion with other reviewers, I raised my score to 5.**\n\n$$ $$", "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": "72Ffj20HA4", "reviewer": "Reviewer_vWSA", "summary": "This paper presents a novel algorithm for learning on simplicial\ncomplexes, i.e. generalisations of graphs. As opposed to relying on the\nmessage passing paradigm, the paper uses random walks (or rather,\n*sampled* random walks) to featurise the input data, subsequently\nemploying 1D convolutions as a type of local update mechanism.\nExperiments on several data sets demonstrate the efficacy of the method.", "questions": "1. How are the random walk parameters (length / number of walks)\n   affecting performance? Could you show predictive performance as\n   a function of these parameters (or, even better, provide theoretical\n   guarantees)?\n\n2. Would the proposed method also extend to *hypergraphs* or other\n   combinatorial complexes? This seems to be the case, given that merely\n   a notion of a random walk is required.\n\n3. Given the performance considerations, are there any practical\n   limitations in terms of data set size that could be given? This might\n   be useful to assess the suitability for certain data sets in advance.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is exceptionally well written and describes highly-original\nresearch. Given the recent interest in extending graph learning to\nhigher-order structures, the work is also timely and highly-relevant.\n\nMoreover, I appreciate that this paper presents alternatives to the\nprevailing message passing paradigm. As amply demonstrated in the\nmanuscript, this leads to a different class of expressivity, thus\nopening the door to further explorations.\n\nThe current write-up is sufficiently detailed to be reproducible, and\nall concepts are explained sufficiently well. This paper was truly\na pleasure to read and review.", "weaknesses": "Only minor weaknesses cropped up, which can be easily addressed in\na revision (please also see my questions below).\n\n- The impact of parameter choices could be studied more carefully.\n\n- A discussion on the utility of a simplicial perspective might enrich\n  the paper. As it stands now, the experiments deal with simplicial\n  data. The scope of the paper could be improved substantially if the\n  simplicial perspective was shown to be *crucial* for good performance.\n  I want to stress that I consider this to be a minor weakness since the\n  paper as such already makes a strong contribution under the assumption\n  that simplicial complexes are the 'right' thing to model the data.\n  Showing this empirically would just be a cherry on top of this cake.\n\n  (the experiment on social contact networks is a good start for this,\n  but I would appreciate a more in-depth discussion **if possible**)\n\n- Unless I am mistaken, the proper verb form should be 'convolved' as\n  a opposed to 'convoluted' (in Figure 2).\n\n- As a minor style issue: please use `\\citep` and `\\citet` (when using\n  `natbib`) consistently. The former is meant for parenthetical\n  citations, the latter for in-text citations.\n\n- There are some inconsistencies (mostly capitalisation / venues) in the\n  references.\n\n- When it comes to explaining expressivity in the context of WL,\n  a [recent survey](https://arxiv.org/abs/2112.09992) might be useful as\n  an additional reference. (The related work covered at the moment is\n  sufficient; this is just a suggestion. The review form unfortunately\n  lacks a field for 'additional comments')", "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 (poster)