CAT-Walk: Inductive Hypergraph Learning via Set Walks
Authors: Ali Behrouz
Farnoosh Hashemi
Sadaf Sadeghian
Margo Seltzer
Venue: NeurIPS 2023 poster (2023)
Keywords: Hypergraph Learning
Temporal Networks
Higher-order Temporal Motifs
Inductive Representation Learning
TL;DR: We propose an effective and inductive way to encode the higher-order patterns and dynamic laws of the hypergraphs via SetWalks, a new family of walks on hypergraphs, which significantly improves inductive representation learning on these networks.

Abstract: Temporal hypergraphs provide a powerful paradigm for modeling time-dependent, higher-order interactions in complex systems. Representation learning for hypergraphs is essential for extracting patterns of the higher-order interactions that are critically important in real-world problems in social network analysis, neuroscience, finance, etc. However, existing methods are typically designed only for specific tasks or static hypergraphs. We present  CAT-Walk, an inductive method that learns the underlying dynamic laws that govern the temporal and structural processes underlying a temporal hypergraph. CAT-Walk introduces a temporal, higher-order walk on hypergraphs, SetWalk, that extracts higher-order causal patterns. CAT-Walk uses a novel adaptive and permutation invariant pooling strategy, SetMixer, along with a set-based anonymization process that hides the identity of hyperedges. Finally, we present a simple yet effective neural network model to encode hyperedges. Our evaluation on 10 hypergraph benchmark datasets shows that CAT-Walk attains outstanding performance on temporal hyperedge prediction benchmarks in both inductive and transductive settings. It also shows competitive performance with state-of-the-art methods for node classification. (https://github.com/ubc-systopia/CATWalk)

CAT-WALK: Inductive Hypergraph Learning via Set Walks
Ali Behrouz
Farnoosh Hashemi
Department of Computer Science University of British Columbia alibezêcs. ubc.
Department of Computer Science University of British Columbia farshêcs ubc.ca
Sadaf Sadeghian'
Margo Seltzer
Department of Computer Science University of British Columbia sadafsdn@cs.ute uuc.iessssuuccc...
Department Computer Science University of British Columbia mseltzer wuw.rrccs.uccc.. ubc.ca
Abstract
Temporal hypergraphs provide a powerful paradigm for modeling time-dependent, higher-order interactions in complex systems. Representation learning for hy- pergraphs is essential for extracting patterns of the higher-order interactions that are critically important in real-world problems in social network analysis, neuro- science, finance, etc. However, existing methods are typically designed only for specific tasks static hypergraphs. We present WALK, inductive method that learns the underlying dynamic laws that govern the temporal and structural processes underlying temporal hypergraph. CAr- WALK introduces a temporal, higher-order walk on hypergraphs, SETWALK, that extracts higher-order causal pat- terns. CAI-WALK uses novel adaptive and permutation invariant pooling strategy, SETMIXER, along with set-based anonymization process that hides the identity of hyperedges. Finally, we present a simple yet effective neural network model encode hyperedges. Our evaluation on 10 hypergraph benchmark datasets shows that CAT-WALK attains outstanding performance on temporal hyperedge prediction benchmarks in both inductive and transductive settings. It also shows competitive performance with state-of-the-art methods for node classification. (Code)
Introduction
Temporal networks have become increasingly popular for modeling interactions among entities in dynamic systems [1-5]. While most existing work focuses on pairwise interactions between entities, many real-world complex systems exhibit natural relationships among multiple entities [6-8]. Hypergraphs provide a natural extension to graphs by allowing an edge to connect any number of vertices, making them capable of representing higher-order structures data. Representation learning on (temporal) hypergraphs has been recognized as an important machine learning problem and has become the cornerstone behind wealth of high-impact applications in computer vision [9, 10], biology [11, 12], social networks [13, 14], and neuroscience [15, 16].
Many recent attempts to design representation learning methods for hypergraphs equivalent to applying Graph Neural Networks (GNNS) to the clique-expansion (CE) hypergraph [17-21], CE is straightforward way to generalize graph algorithms hypergraphs by replacing hyperedges with (weighted) cliques [18-20) However, this decomposition of hyperedges limits expressiveness,
TThese two authors contributed equally (ordered alphahetically) and reserve the right to swap their order.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Input
Sampling
Extracted SETWALKS
1g
Law Explanation: When a mode is pairwise connected two other nodes that are sherssehves connected by three way connection, it sends form three way comeection with them.
t
I < < ta ta
Extractedd SETWALKS
Explanation:
When
(hrec-ung
connection with two other noces that are llarmacivve connected by three way connection, all rend to Jonn four-way conrection with each other.
fj < f2 fs
SET WALK can distinguish and simple walk on the CE of the hypergraph fail to differentiate between these' cassss
underlying dynamic lawa but hypergraph walk
Figure 1: The advantage of SETWALKS in walk-based hypergraph learning.
The advantage of SETWALKS in causality extraction and capturing complex dynamic laws.
Figure 2:
leading to suboptimal performance [6, 22-24] (see Theorem and Theorem 4). New methods that encode hypergraphs directly partially address this issue [11, 25-28J. However, these methods suffer from some combination of the following three limitations: they are designed for ! learning the structural properties of static hypergraphs and do not consider temporal properties, 2 the transductive setting, limiting their performance on unseen patterns and data, and & a specific downstream task (e.g., node classification [25], hyperedge prediction [26], or subgraph classification [27]) and cannot easily be extended to other downstream tasks, limiting their application.
Temporal motif-awarc and beighborhood-awar aware methods have been developed to capture complex patterns in data [29-31]. However, counting temporal motifs in large networks is time-consuming and non-parallelizable, limiting the scalability of these methods. To this end, several recent studies suggest using temporal random walks to automatically retrieve such motifs [32-36]. One possible solution to capturing underlying temporal and higher-order structure is to extend the concept of hypergraph random walk [37-43] to its temporal counterpart by letting the walker walk over time. However, existing definitions of random walks on hypergraphs offer limited expressivity and sometimes degenerate to simple walks on the CE of the hypergraph [40] (see Appendix C). There are two reasons for this: ! Random walks are composed of a sequence of pair-wise interconnected vertices, even though edges in a hypergraph connect sets of vertices. Decomposing them into sequences of simple pair wise interactions loses the semantic meaning of the hyperedges (see Theorem 4). @ A sampling probability of a walk on a hypergraph must be different from its sampling probability on the CE of the hypergraph [37-43]. However, Chitra and Raphael [40] shows that each definition of the random walk with edge-independent sampling probability of nodes is equivalent to random walks on weighted CE of the hypergraph. Existing studies on random walks on hypergraphs ignore T and focus on 2 to distinguish the walks on simple graphs and hypergraphs. However, as we show in Table 2, ① is equally important, if not more so.
For example, Figure shows the procedure of existing based machine learning methods on a temporal hypergraph. The neural networks in the model take as input only sampled walks. However, the output of the hypergraph walk [37, 38] and simple walk on the CE graph are the same. This means that the neural network cannot distinguish between pair-wise and higher-order interactions.
We present Causal Anonymous Set Walks (CAr-WALK) inductive hyperedge learning method. We introduce a hyperedge-centree random walk on hypergraphs, called SETWALK, that automatically extracts temporal, higher-order motifs. The hyperedge-centric approach enables WALKS distin- guish multi-way connections from their corresponding CEs (see Figure 1, Figure 2, and Theorem 1). We use temporal hypergraph motif's that reflect network dynamics (Figure 2) enable CAI-WALK to work well in the inductive setting. To make the model agnostic to the hyperedge identities of these motifs, we use two-step, set-based anonymization: ① Hide node identities by assigning them new positional encodings based on the number of times that they appear at a specific position in a set of sampled SETWALKS, and 2 Hide hyperedge identities by combining the positional encodings of the nodes comprising the hyperedge using novel permutation invariant pooling strategy, called SETMIXRR. We incorporate neural encoding method that samples a few SETWALKS starting from nodes of interest. It encodes and aggregates them via MLP-MIXC [44] and our new pooling strategy

---

Causality Extraction
Walks
Set-besed Anomymizaionn
Encoding
Arenyyiiationn
Hypereige
Hyper hyperddge Embeddings
Zaro poddiing
Softmax
Hyperedge Encodings
Encodinggs
Token-mber
Anonymization
Channel-mixe
Channel- mixeer
Mean-pooling
Mean-poollng
SetMixer
Figure 3: Schematic of the CAr- WALK. CAr- WALK consists of three stages: (1) Causality Extraction via Set Walks ($3.2), (2) Set-based Anonymization ($3.3), and (3) Set Walk Encoding ($3.4).
MEXMIER respectively, to predict temporal, higher-order interactions. Finally, we discuss how to extend CAI-WALK for node classification. Figure shows the schematic of the CAI-WALK.
We theoretically and experimentally discuss the effectiveness of CAr-WALK and each of its components. More specifically, we prove that SETWALKS are more expressive than existing random walk algorithms on hypergraphs. We demonstrate SETMIXER 's efficacy as permutation invariant pooling strategy for hypergraphs and prove that using it in our anonymization process makes that process more expressive than existing anonymization processes [33, 45, 46] when applied to the CE of the hypergraphs. To the best of our knowledge, we report the most extensive experiments in the hypergraph learning literature pertaining to unsupervised hyperedge prediction with 10 datasets and eight baselines. Results show that our method produces 9% and 17% average improvement in transductive and inductive settings, outperforming all state-of-the-arr baselines in the hyperedge prediction task. Also, CAr-WAi WALK achieves the best or on-par performance on dynamic node classification tasks. All proofs appear in the Appendix.
2 Related Work
Temporal graph learning is an active research area [5, 47]. A major group of methods uses GNNS to learn node encodings and Recurrent Neural Networks (RNNS) to update these encodings over time [48-55]. More sophisticated methods based on anonymous temporal random walks [33, 34], line graphs [56]. GraphMixer [57], neighborhood representation [58]. and subgraph sketching [59] are designed to capture complex structures vertex neighborhoods, Although these methods show promising results in a variety of tasks, they are fundamentally limited in that they are designed for pair-wise interaction among vertices and not the higher-order interactions in hypergraphs.
Representation learning on hypergraphs addresses this problem [17, 60]. We group work in this area into three overlapping categories:
! Clique and Star Expansion: CE-based methods replace hyperedges with (weighted) cliques and apply GNNS, sometimes with sophisticated propagation rules [21, 25], degree normalization. and nonlinear hyperedge weights [17-21, 39, 61, 62). Although these methods are simple, it is well-known that CE causes undesired losses in learning performance, specifically when relationships within an incomplete subset of hyperedge do not exist [6. 22-24]. Star expansion (SE) methods first use hypergraph star expansion and model the hypergraph represents nodes and the other represents hyperedges [25, 28, 63, 64). Next, they apply modified heterogeneous GNNs, possibly with dual attention mechanisms from nodes to hyperedges and vice versa [25, 27). Although this group does not cause as large a distortion as CF, they are neither memory nor computationally efficient.
bipartite graph, where one set of vertices
2 Message Passing: Most existing hypergraph learning methods, use message passing over hypergraphs [17-21, 25-27, 39, 61, 62, 65, 66). Recently, Chien et al. [25] and Huang and Yang [28] designed universal message-passing frameworks that include propagation rules of most previous methods (e.g., [17, 19]). The main drawback of these two frameworks is that they are limited node classification tasks and do not easily generalize to other tasks. 3 Walk- based: random walks are common approach to extracting graph information for machine learning algorithms [32-34, 67, 68]. Several walk-based hypergraph learning methods are designed for a wide array of applications [43, 69-78). However, most existing methods use simple random walks on the CE of the hypergraph (e.g.. [26, 43, 78)). More complicated random walks on hypergraphs address this limitation [40-42, 79]. Although some of these studies show that their walk's 's transition matrix
3

---

differs from the simple walk on the CE [40, 79], their extracted walks can still be the same, limiting their expressivity (see Figure I, Figure 2, and Theorem 1).
Our method differs from all prior (temporal) (hyper)graph learning methods in five ways: CAn- WALK: ① Captures temporal higher-order properties in streaming manner: In contrast to existing methods in hyperedge prediction, our method captures temporal properties in a streaming manner, avoiding the drawbacks of snapshot-based methods. ①I Works in the inductive setting by extracting underlying dynamic laws of the hypergraph, making it generalizable to unseen patterns and nodes. (II) Introduces hyperedge-centricc temporal, higher-order walk with new perspective on the walk sampling procedure. (VV Presents a new two-step anonymization process: Anonymization of higher-order patterns (i.e., SETWALKS), requires hiding the identity of both nodes and hyperedges. We present a new permutation sernutationinvvariant pooling strategy to hide hyperedges' identity according to their vertices, making the process provably more expressive than the existing anonymization processes [33, 34, 78]. V Removes self-attention and RNNs from the walk encoding procedure, avoiding their limitations. Appendices and B provide a more comprehensive discussion of related work.
3 Method: CAT-WALK Network
3.1 Preliminaries
Definition 1 (Temporal Hypergraphs). A temporal hypergraph G= = (V,E,), can be represented as a sequence of hyperedges that arrive over time, i.e., & ((e1, (e2, where V is the set of nodes, e, E 2 are hyperedges, t, is the timestamp showing when e; arrives, and X E RVW is matrix that encodes node attribute information for nodes in V. Note that we treat each hyperedge ei as the set of all vertices connected by e;-
Example 1. The input of Figure I shows an example of a temporal hypergraph. Each hyperedge is a set of nodes that are connected by higher-order connection. Each higher-order connection is specified by a color (e.g. green, blue, and gray), and also is associated with a timestamp (e.g.. tt).
Given a hypergraph 9 = (V,E,X), we represent the set of hyperedges attached to a node u before time as (u) = I'r, <1, u e). We say two hyperedges and e' are adjacent if e eee' 0 and use (e)) = ((e'r)))'' < <,, ne # 0) to represent the set of hyperedges adjacent to e before time f. Next, focus on the hyperedge prediction task: Given a subset of vertices L/ (M1...., ug). want to predict whether a hyperedge among all the u;s will appear in the next timestamp or not. In AppendixG.2 we discuss how this approach can be extended node classification.
The (hyper)graph isomorphism problem is a decision problem that decides whether a pair of (hy- per)graphs are isomorphic not. Based this concept, next, we discuss the measure we use to compare the expressive power of different methods.
Definition 2 (Expressive Power Measure). Given two methods Mj and M2, we say method Mi is more expressive than method M₂ if:
1. for any pair of (hyper)graphs (GI,92) such that G # G2 method Mj can distinguish Gi and G2 then method M2 can also distinguish them,
2. there is a pair of hypergraphs G + G2 such that Mj can distinguish them but M2 cannot.
3.2 Causality Extraction via SALWALK
The collaboration network in Figure/ 1 shows how prior work that models hypergraph walks as sequences of vertices fails to capture complex connections in hypergraphs. Consider the two walks: A + C + E and H - E + C. These two walks can be obtained either from hypergraph random walk or from simple random walk on the CE graph. Due to the symmetry of these walks with respect to (A, C, E) and (H, E, C), they cannot distinguish A and H, although the neighborhoods of these two nodes exhibit different patterns: A, B, and C have published a paper together (connected by hyperedge), but each pair of E, G. and I/ has published paper (connected by pairwise link). We address this limitation by defining a temporal walk on hypergraphs as sequence of hyperedges: Definition 3 (SETWAlK), Given a temporal hypergraph G = (V. X), SETWALK with length & on temporal hypergraph G is a randomly generated sequence of hyperedges (sets):
Sw ; (e),te,) (e2, ... - (et, te,)

---

where e; E E&, te., < <tey and the intersection of e; and e+t1 is not empry, es O C+t1 # 0. In other words, for each 1 S i S f-l: 1: 6i+1 (e,) We use Sw[i] to denote the i-th hyperedge--imee pair in the SETWALK That is, Sw[i][0] = and Sw[i][]] le:
Example 2. Figure 1 illustrates a temporal hypergraph with two sampled WETWALKS, hypergraph random walks, and simple walks. As an example, (IA, B, C).1)) - (IC, D, E, 1),13) is SETWALK that starts from hyperedge e including [A, B, C} in time 16. backtracks overtime and then samples hyperedge e' including E. F) in time 15 < 16. While this higher-order random walk with length two provides information about all [A, B, C, D, ED F), its simple hypergraph walk counterpart, i.e. A 4 C - E., provides information about only three nodes.
Next, we formally discuss the power of SETWALKS. The proof of the theorem can be found in Appendix E.I.
Theorem 1. A random SET SETWALK is equivalent to neither the hypergraph random walk, the random walk on the CE graph, nor the random walk on the SE graph. Also, for finite number of samples of each, SETWALK is more expressive than existing walks.
In Figure 1, SETWALKS capture higher-order interactions and distinguish the two nodes A and H, which are indistinguishable via hypergraph random walks and graph random walks in the CE graph. We present a more detailed discussion and comparison with previous definitions of random walks on hypergraphs in Appendix C.
Causality Extraction. We introduce sampling method allow SETWALKS to extract temporal higher-order motifs that capture causal relationships by backtracking over time and sampling adjacent hyperedges. As discussed in previous studies [33, 34], more recent connections are usually more informative than older connections. Inspired by Wang et al. [33], we use hyperparameter 2 0 to sample hyperedge with probability proportional to exp(a(t- (p)). where and Ip are the timestamps of and the previously sampled hyperedge in the SETWALK, respectively. Additionally, we want to bias sampling towards pairs of adjacent hyperedges that have a greater number of common nodes capture higher-order motifs. However, as discussed in previous studies, the importance of each node for each hyperedge can be different [25, 27, 40, 65J. Accordingly, the transferring probability from hyperedge e, its adjacent hyperedge e, depends on the importance of the nodes that they share. We address this via temporal SETWALK sampling process with eeperedge-deeendeet node weights. Given temporal hypergraph & E.) a hyperedge-dependen node-weight function I V - Ra0, and a previously sampled hyperedge (pp.tp), we sample hyperedge (e, I) with probability:
exp(a(1-1)
explele,,e))
Pl(e, ((ep=)) &
Eaernesnee exp (a(r -1p) X
(I)
Elerryaerre,, exp (p(eeeep))
where ple,e')= Eweene I(u, e) (u, representing the assigned weight to e n e'. We refer to the first and second terms as temporal bias and structural bias, respectively.
The pseudocode of our WALK sampling algorithm and its complexity analysis are in Appendix D. We also discuss this spperedge-depeneen sampling procedure and how it is provably more expressive than existing hypergraph random walks in Appendix C.
Given (potential) hyperedge eo [Mi, M2..... mss and a time In. say a SETWALK, Sw, starts from u; if u; E Sw[1][O]. We use the above procedure to generate M SETWALKS with length m starting from each i; ev. We use S(u,) to store SETWALKS that start from i;:
3.3 Set-based Anonymization of Hyperedges
In the anonymization process, we replace hyperedge identities with position encodings, capturing structural information while maintaining the inductiveness of the method. Micali and Zhu [45] studied Anonymous Walks (AWs), which replace a node's identity by the order of its appearance in each walk. The main limitation of AWs is that the position encoding of each node depends only on its specific walk, missing the dependency and correlation of different sampled walks [33]. To mitigate this drawback, Wang et al. [33] suggest replacing node identities with the hitting counts of the nodes based on a set of sampled walks. In addition to the fact that this method is designed for walks simple graphs, there are two main challenges to adopting it for SET WALKS::: ① SETWALKS
5

---

are sequence of hyperedges, so we need an encoding for the position of hyperedges. Natural attempts to replace hyperedges' identity with the hitting counts of the hyperedges based on a set of sampled SETWALKS, misses the similarity of hyperedges with many of the same nodes. @ Each hyperedge a set of vertices and natural attempts to encode its nodes' positions and aggregate them to obtain a position encoding of the hyperedge requires a permutation invariant pooling strategy. This pooling strategy also requires consideration the higher-order dependencies between obtained nodes' position encodings to take advantage of higher-order interactions (see Theorem 2). To address these challenges we present a set-based anony monnymiztton process for SETWALKS. Given a hyperedge en (u....., Mk), let Wo be any node in ey. For each node that appears at least one SETWALK in U S(u;), we assign relative, node-dependent node identity, (ww)) E 2", as follows:
R(w, (ww)) = [[Sw[Sw E S(wo), W E Sw[]][O] E (1,2...,,
(2)
For each node w further define ID(w, eo) (R(w, ((w))) Let V()) Rdxd Rd be a pooling function that gets a set of d1 -4-dimensional vectors and aggregates them to a dz-dimensional vector. Given two instances of this pooling function, () and (2(.), for each hyperedge e (W), wy-) that appears at least one SETWALK in U S(4,), we assign relative hyperedge identity
In(e, eg) = 1 (IV2 (ID(W; )
That is, for each node w; e we first aggregate its relative node-dependent identities (i.e., R(w, S(u,))) to obtain the relative hyperedge-dependdnt identity. Then we aggregate these hyperedge-dependeee identities for all nodes in Since the size of hyperedges can vary, zero-pad to fixed length. Note that this zero padding is important to capture the size of the hyperedge. The hyperedge with more zero- zero-padded dimensions has fewer nodes.
This process addresses the first challenge and encodes the position of hyperedges. Unfortunately, many simple and known pooling strategies (e.g., SUM(.), ATTN-SUM( MEAN(.), etc.) can cause missing information when applied hypergraphs. We formalize this in the following theorem:
Theorem 2. Given arbitrary positive integer k E Zt, ler (C)) be pooling function such that for any set S = (Wi....,
V(S) = Σ S(S),
(4)
where f is some function. Then the pooling function can cause missing information, meaning that it limits the expressiveness of the method to applying to the projected graph of the hypergraph.
While simple concatenation does not suffer from this undesirable property, it is not permutation invariant. To overcome these challenges, we design an all-MLP permutation invariant pooling function, SETMIXER, that not only captures higher-order dependencies of set elements but also captures dependencies across the number of times that node appears at a certain position in SETWALKS.
SETMINER. MLP-MIXI [44] is family of models based on multi-layer perceptrons, widely used in the computer vision community, that are simple, amenable to efficient implementation, and robust to over- squashing and long-term term dependencies (unlike RNNs and attention mechanisms) [44, 57]. However, the token-mixer phase of these methods is sensitive to the order of the input (see Appendix A). To address this limitation, inspired by MI.-MIXER [44), we design SETMIxER as follows: Let S (Vi...., va). where V; e Rdi be the input set and V = [Vi...., val Raddd be its matrix representation:
YP(S)= MEAN HH + (LayerNorm (H (oken) w()) W??).
(5)
where
H Hoken V + o (Softmax (LayerNorm
(6)
Here, w and ? are learnable parameters, (T.) is an activation function (we use GeLU [80] in experiments), and LayerNorm is layer normalization [81], Equation 5 is the channel mixer and Equation 6 is the token mixer. The main intuition of SETMIXeR is to use the Softmax(() function to bind token-wise information in non-parametrie manner, avoiding permutation variant operations in the token mixer. We formally prove the following theorem in Appendix E.3.
Theorem SETMIXER is permutation invariant and is a universal approximator of invariant multi-set functions. That is, SETMIEER approximate any invariant multi-se set function.

---

Based on the above theorem, SETMIXER can overcome the challenges we discussed earlier as it is permutation invariant. Also, it is a universal approximator of multi-set functions, which shows its power to learn any arbitrary function. Accordingly, in our anonymization process, we use V(.) hide hyperedge identities. Next, we guarantee that our anonymization
SETMIXER() in Equation process does not depend on hyperedges or nodes identities, which justifies the claim of inductiveness of our model:
Proposition 1. Given two (potential) hyperedges eq =u....,, ue) and eo (u/....., ub),. if there exists a bijective mapping π between node identities such that for each SETWALK like Sw U S(u) can be mapped to one SETWALK like Sw' E Ui-i S(u)) then for each hyperedge e = (Wi...., We] that appears in at least one SETWALK in U S(u), we have io(e,e)) = In(T(e), where x(e) (rtw).......((??))
Finally, we guarantee that our anonymization approach is more expressive than existing anonymization process [33, 45] when applied to the CE of the hypergraphs:
Theorem 4. The set- set-based anonymization method is more expressive than any existing anonymization strategies on the CE of the hypergraph. More precisely, there exists a pair of hypergraphs 91 (V1,&,) and G2 (V2.8) E2) with different structures (i.e., Gi * G2) that are distinguishable by our anonymization process and are not distinguishable by the CF-based methods.
3.4 WALK Encoding
Previous walk-based methods [33, 34, 78] view walk sequence of nodes. Accordingly, they plug nodes' positional encodings a RNN [82] or Transformer [83] to obtain the encoding of each walk. However, in addition to the computational cost of RNN and Transformers, they suffer from over-squashing and fail to capture long-term dependencies. To this end, we design a simple and low-cost SETWALK encoding procedure that uses two steps: ① A time encoding module distinguish different timestamps, and 2 A mixer module to summarize temporal and structural information extracted by SETWALKS.
Time Encoding, We follow previous studies [33, 84) and adopt random Fourier features [85, 86] to encode time. However, these features are periodic, so they capture only periodicity in the data. We add learnable linear term to the feature representation of the time encoding. We encode given time/ as follows:
T(r) (wit b)) cos(top))
where wr by and a 1d:-1 are learnable parameters and shows concatenation.
MIXER Module. To summarize the information in each SETWALK, sequence of hyperedges in a SETWALK as well as their corresponding encoded timestamps. Contrary to the anonymization process, where need permutation invariant procedure, here, we need permutation variant procedure since the order of hyperedges in a SETWALK is important. Given a (potential) hyperedge eq (u,...., ug), first assign ID(e, en) each hyperedge that appears least one sampled WALK starting from éu (Equation 3). Given a SETWALK, Sw (e1, (em. we let E be matrix that E, In(e, et).)T(t.)):
MLP-MIXE [44] on the
ENc(Sw) MEAN (Hocen + o (LayerNorm (Hoken)) (())) channel
w relamee)
(8)
where
Hoken
E 2r o (Wil)) token
token LayerNorm(E))
3.5
Training
In the training phase, for each hyperedge in the training set, we adopt the commonly used negative sample generation method [60] to generate a negative sample. Next, for each hyperedge in the training set such as ép (#I, .2...., Mt). including both positive and negative samples, we sample M SETWALKS with length m starting from each 4, E eg to construct S(n). Next, we anonymize cach hyperedge that appears in least one SETWALK U S(u) by Equation 3 and then use the MIXeR module to encode each Sw UL_ S(u). To encode each node u; ép. we use MEAN(.) pooling over SETWALKS in S(u). Finally, to encode en use SETMIXER to mix obtained node encodings. For
7

---

hyperedge prediction, we use 2-layer perceptron over the hyperedge encodings to make the final prediction. We discuss node classification in Appendix G.2.
4
Experiments
We evaluate the performance of our model on two important tasks: hyperedge prediction and node classification (see Appendix G.2) in both inductive and transductive settings. We then discuss the importance of our model design and the significance of each component in CAT-WALK.
4.1 Experimental Setup
Baselines. We compare our method eight previous state-of-the-art baselines on the hyperedge
prediction task. These methods can be grouped into three categories: ! Deep hypergraph learning
methods including HYPERSAGCN [26], NHP [87], and CHESHIRE [11]. 2 Shallow methods
including HPRA [88] and HPLSF [89]. 3 CE methods: CE-CAW [33], CE-EvOLVEGCN [90] and
CE-GCN [91]. Details on these models and hyperparameters used appear in Appendix F.2.
Datasets. We use 10 available benchmark datasets [6] from the existing hypergraph neural networks literature. These datasets' domains include drug networks (i.e., NDC [6]), contact networks (i.e., High School [92] and Primary School [93]), the US. Congress bills network [94, 95], email networks (i.e., Email Enron [6] and Email Eu [96]), and online social networks (i.e., Question Tags and [6]) Detailed descriptions of these datasets appear in Appendix F.I.
Evaluation Tasks. We focus on Hyperedge Prediction: In the transductive setting, we train on the temporal hyperedges with timestamps less than or equal to T Timin and test on those with timestamps greater than Turann Inspired by Wang al. [33], we consider two inductive settings. In the Strongly Inductive setting, we predict hyperedges consisting of some unseen nodes. In the Weakly Inductive setting,we we predict hyperedges with at least one seen and some unseen nodes. We first follow the procedure used in the transductive setting, and then we randomly select 10% of the nodes and remove all hyperedges that include them from the training set. We then remove all hyperedges with seen nodes from the validation and testing sets. For dynamic node classification, see Appendix G.2. For all datasets, we fix Train 0.7 T, where T is the last timestamp. To evaluate the models' performance we follow the literature and use Area Under the ROC curve (AUC) and Average Precision (AP).
4.2 Results and Discussion
Hyperedge Prediction. We report the results of CAr-WALK and baselines in Table and Appendix G. The results show that CAT-WALK achieves the best overall performance compared to the baselines in both transductive and inductive settings. In the transductive setting, not only does our method outperform baselines in all but one dataset, but it achieves near perfect results (i.e., 98.0) on the NDC and Primary School datasets. In the Weakly Inductive setting, our model achieves high scores (i.e.. > 91.5) in all but one dataset, while most baselines perform poorly as they are not designed for the inductive setting and do not generalize well to unseen nodes or patterns. In the Strongly Inductive setting, CAr-WALK still achieves high AUC (i.e., > 90.0) on most datasets and outperforms baselines on all datasets. There are three main reasons for HAL-WALK'S superior performance: I Our SETWALKS capture higher-order patterns. ② CAr- WALK incorporates temporal properties (both from WELWALKS and our time encoding module), thus learning underlying dynamic laws of the network. The other temporal methods (CE-CAW and CE-EvoLNEGCNN are CB-based methods, limiting their ability to capture higher-order patterns. ② CAr-WAIX 's set-based anonymization process that avoids using node and hyperedge identities allows generalize to unseen patterns and nodes.
Ablation Studies. We next conduct ablation studies on the High School, Primary School, and -hers-T datasets to validate the effectiveness of WAL-WSLK'S critical components. Table shows AUC results for inductive hyperedge prediction. The first row reports the performance of the complete CAr WALK implementation. Each subsequent row shows results for CAT-WALK with one module modification: row 2 replace SErWALK by edge-dependent hypergraph walk [40], row 3 removes the time encoding module, row 4 replaces SETMIXER with MEAN(.) pooling, row 5 replaces the SETMIXER with busdbased universal approximator for sets [97]. row 6 replaces the MLP-MIXER
8

---

Table 1: Performance on hyperedge prediction: Mean AUC (%) = standard deviation. Boldfaced letters shaded blue indicate the best result, while gray shaded boxes indicate results within one standard deviation the best result. N/A: the method has numerical precision or computational issues.
Methook
NDC Class
High School
Primary School
Congress Bill
Email Faron
Email Fu
Question Tags Threads
Strongly Inductive
CE-GCN
52.31 = 2.99
60.54 2.06
52.34
2.75
49.18 3.61
63.04 = 1.80
52.76 2.41
56.10 1.88
$7.91 + 1.56
CE-EvonaGGN
49.78 3.13
46,12 = 383
58.01 2.56
54.00 1.84
57.31 4.19
44,16 1.27
64.08 2.75
52.00
2.32
CE-CAW
83.73
75.38
70.81
NLIP
65.29
3,80
70.86 3.42
69.82 + 2.19
49.71 = 6.09
65.35
2.07
68.23 + 3.34
71.83 2.64
HYPrESAGCN
79.05
88.12 - 3.01
80.13 1.38
79.51
1,27
73:00 + 2.60
78.01 1.24
73.66 1.95
73.94
2.57
82.54
77.26
2.55
69.98
N/A
2.82
CAr-WArK
98.89 1.82
96.03
1.50
0.89 95.32
93.54 0.56
73:45 2.92
91.68
2.78
88.03 3.38
89.84
6.02
Indactive
Weekly Inductive
CE-GCN
$ 3.29
50.33
3.40
52.19 2.54
52.38 2:75
50.81 = 2.87
49.60 3.96
55.13 a: 2.76
57.06
3.16
CE DE-ENooNGG
55.39
57,85
1,51
51,50 4.07
55.63 + 3.41
45.66
2.10
$2.44 + 2.38
61.79 1.63
55.81
2.54
CF-CAW
77.61 1.05
83.77
82.98
79.51
80.54
73.54
17. 0.80
80.79
0.82
NHP
2.02
67,25
5.19
71.92 1.83
69.58 4.007
60.38 a 4.45
67.19
70.46 3.52
76.44 1.90
HYGEESAGCN
79.45
1.26 88.53
85.08 = 1.45
80.12 2.00
78.86 0.63
71.26 2.09
78.15 1.41
75.38
1.43
CHESHIRE
79.03
$3.55
77.31
N/A
CAr-WAL WALK
99.16 1.08
94.68
2.37
96.53 1.39
0.21 98.38
64.11 7.96
2:41 91.98
90.28 = 2.81
97.15
1.81
HPRA
0.01
94,91
00.00
89.86 = 0.06
79.48 + 0.03
78.62 = 0.00
72.51 = 0.00
83,18 + 0.00
70.49 # 0.02
HPI SF
0..1
92.14 02444-0.33 0.29
1.09 88.57
79.31 0.52
75.73 0.05
75.27 0.31
83.45 + 0.93
74.38 1.11
Transhhctie
CE-GCN
67.08-3..5 3.51
65. 2.26
63.15+ 1.32
69.30 2.27
69. .8.98- 5.38
64.36 4.17
72.56 1.72
68.55 2.26
CE-CAW
76.30 0.84
81.63 0.97
86.53 0.84
76.99 1,02
79.57 0.14
78.19 1.10
81.73 2.48
80.86 0.45
1.02
HYWEESAGEN
80.76
2.64
94,98 - 1.30
90.77 2.05
82. 84 1.61
83.39 - 0.98
79.61 2.35
84.07 + 2.50
79.62
2.04
CHESHIRE
84,91
1.05
95.11 0.94
91.62 1.18
86.81 1.24
82.27 0.86
86.38
N/A
82.75 1.99
CAR-WaK
1.38
95.30
97.91
1.46
80.45 5.30
96.74
91.63
93.51
1.27
Table 2: Ablation study on CAr- WALK.
AUC scores on inductive hyperedge prediction.
Methods
High School
Primary School
Users Threads
Congress bill
Question Tags
1
CAs- WALK
96.03 # 1.50
95,32 = 0.89
89.84 + 6.02
93.54 + 0.56
97.59 + 2.21
2
Replace SerWau by Random Walk
92.10 a 2.18
51.56 = 5.63
53.24 a: 1.73
80.27 i 0.02
67.74 a: 2.92
3.
Remove Time Encoding
95.94 0.19
86,80 : 6.33
70.58 9.32
92.56 0.49
96.91 # 1.89
Replace StrMixxx by MrAN(.)
94.58 + 1.22
95.14 + 4.36
63.59 + 5.26
91.06 + 0.24
68.62 + 1.25
5 Replace SErMIXER by Sum-based Universal Approximator Sets
94.77 0.67
90.86 0.57
60.03 1.16
91.07 0.70
89.76 0.45
7 Replace MLP-MIXE by Ryx
92.85 + 1.53
50.29 + 4.07
58. +
54.90 +
65.18 + 1.99
8 Replace MLP- MMLP-MIXUR by Transformer
55.98 0.83
86.64 3.55
60.65 1.56
89.38 1.66
56,16 + 4.03
9 Fix a D
74.06 + 14.9
58.3 + 18.62
74.41 10.69
93.31 + 0.13
62.41 + 4.34
module with RNN (see Appendix G for more experiments on the significance of using MLP-MIXER in walk encoding), row 7 replaces the MLP-MIXE module with a Transformer [83], and row 8 replaces the hyperparameter a with uniform sampling of hyperedges over all time periods. These results show that each component is critical for achieving DAT-WALK'S 's superior performance. The greatest contribution comes from SETWALK, MLP-MIXER in walk encoding, temporal hyperedge sampling, and SETMIXER pooling, respectively.
Hyperparameter Sensitivity. We analyze the effect of hyperparameters used in CAr- WALK, including temporal bias coefficient a, SETWALK length m, and sampling number M. The mean AUC performance on all inductive test hyperedges is reported in Figure 4. As expected, the left figure shows that
NIX:
High School
Primory School
100
100
30
ADC
80
AUC
50
70
20
60
60
45
50
20
2
2
10-0
10-1
10
Number of SET WALKS M
Length of SeT WALKS
Sampling time biss
Figure 4: Hyperparameter sensitivity in CALK AUC on inductive test hyperedges are reported.

---

Sampling Time (st
350
500
25
Training Time
20
400
300
10
200
5
100
10
100
160
160
[8] (x10*)
[B] (x10*)
Figure 5: Scalability evaluation: The runtime of (left) SETWALK extraction and (right) the training time of CAr- WALK over one epoch on High School (using different [E] for training).
increasing the number of sampled SETWALKS produces better performance. The main reason is that the model has more extracted structural and temporal information from the network. Also, notably, we observe that only small number of sampled SETWALKS are needed to achieve competitive performance: in the best case 1 and in the worst case 16 sampled SETWALKS per each hyperedge are needed. The middle figure reports the effect of the length of SETWALKS on performance. These results show that performance peaks at certain SETWALK lengths and the exact value varies with the dataset. That is, longer SETWALKS are required for the networks that evolve according to more complicated laws encoded in temporal higher-order motifs. The right figure shows the effect of the temporal bias coefficient a. Results suggest that has a dataset-dependent optimal interval. That is, small suggests an almost uniform sampling of interaction history, which results in poor performance when the short-term dependencies (interactions) are more important in the dataset. Also, very large might damage performance as makes the model focus on the most recent few interactions, missing long-term patterns.
Scalability Analysis. In this part. we investigate the scalability of CAr WALK. To this end, we use different versions of the High School dataset with different numbers of hyperedges from 10a to 1.6 x 10 Figure 5 (left) reports the runtimes of SETWALK sampling and Figure 5 (right) reports the runtimes of CAr- WALK for training one epoch using M = 8, m = with batch-size 64. Interestingly, our method scales linearly with the number of hyperedges, which enables it to be used on long hyperedge streams and large hypergraphs.
5 Conclusion, Limitation, and Future Work
We present CAI-WALK, inductive hypergraph representation learning that learns both higher-order patterns and the underlying dynamic laws of temporal hypergraphs. CAI-WALK uses SETWALKS, a new temporal, higher-order random walk hypergraphs that provably more expressive than existing walks on hypergraphs, to extract temporal higher-order motifs from hypergraphs. WALK then two-step, set-based anonymization process establish the correlation between the extracted motifs. We further design permutation invariant pooling strategy, SETMIXER, for aggregating nodes' positional encodings in a hyperedge obtain hyperedge level positional encodings. Consequently, the experimental results show that CAT-WALK ① produces superior performance compared to the state-of-the-ae temporal hyperedge prediction tasks, and ( competitive performance in temporal node classification tasks. These results suggest many interesting directions for future studies: Using CAr-V WALK as a positional encoder in existing anomaly detection frameworks design an inductive anomaly detection method on hypergraphs. There are. however, few limitations: Currently, CAr- WALK uses fixed-length SETWALKS, which might cause suboptimal performance. Developing procedure to learn from SetWalks of varying lengths might produce better results.
Acknowledgments and Disclosure of Funding
acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
Nous remercions le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG) de soutien.
10

---

References
[1] Serina Chang, Emma Pierson, Pang Wei Koh, Jaline Gerardin, Beth Redbird, David Grusky, and Jure Leskovec. Mobility network models of covid-19 explain inequities and inform reopening. Nature, 589(7840)822877, 2021.
[2] Michael Simpson, Farnoosh Hashemi, and Laks V. S. Lakshmanan. Misinformation mitigation under differential propagation rates and temporal penalties. Prec. VLDB Endow. 15(10): 2216-2229, jun 2022. ISSN 2150-8097. doi: 10. 10.14778/354335.354733 //doi.org/1e 10. 04778/3547855 35778//35473553547324,, 3547324.
URL https:
Martino Ciaperoni, Edoardo Galimberti, Francesco Bonchi, Ciro Cattuto, Francesco Gullo, and Alain Barrat. Relevance of temporal cores for epidemic spread in temporal networks. Scientific reports, 10(1):1-15, 2020.
[4] Farnoosh Hashemi, Ali Behrouz, and Laks V.S. Lakshmanan. Firmcore decomposition of multi- layer networks. In Proceedings the ACM Web Conference 2022, wWW '22, page 1589-1600, New York, NY. USA, 2022. Association for Computing Machinery. ISBN 978 4553390965. doi: 10.1 10.1144/348544... 455.55444..55222 122055
URL https: http:///oooooo///////// wwg//0....0.. 1145/1444440 /4854477 3512205.
[5] Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, Franco Scarselli, and Andrea Passerini. Graph neural networks for temporal graphs: State of the art, open challenges, and opportunities. arXiv preprint arXiv:2302.01011 2023.
[6] Austin 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, 2018. ISSN 0027-8424. doi: 1L10733ppas.18006683
[7] Federico Battiston, Enrico Amico, Alain Barrat, Ginestra Bianconi. Guilherme Ferraz de Arruda, Benedetta Franceschiello, lacopo lacopini. Sonia Kéfi. Vito Latora, Yamir Moreno, Micah M. Murray, Tiago P. Peixoto, Francesco Vaccarino, and Giovanni Petri. The physics of oigeer-order interactions in complex systems. Nature Physics, 17910):0933-109, Oct 2021. ISSN 1745-2481. doi: 10. 001-667001--01333
URL https::/doi. http:://doooooo/////// org/10g.//00 /0/ 1038/
[8] Yuanzhao Zhang, Maxime Lucas, and Federico Battiston. Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes. Nature Communi- cations, 14(1):1605, Mar 2023. ISSN 2041-1723, doi: 10. 10.10088/411467-033337100000 URL
https://doi.onm http://oo..og//... 1038/ /014/444477777 023 -23-4467----------99
[9] Eun-Sol Kim, Woo Young Kang, Kyoung- Woon On, Yu-Jung Heo, and Byoung- Tak Zhang. Hypergraph attention networks for multimodal learning. Proceedings of the IEEE/CVF conference computer vision and pultern recognition, pages 14581-14590 2020.
[10] Yichao Yan, Jie Qin, Jiaxin Chen, Li Liu, Fan Zhu, Ying Tai, and Ling Shao. Learning multi-granular hypergraphs for video-based person re-identification. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2899-2908, 2020.
[11] Can Chen, Chen Liao, and Yang-Yu Yu Liu. Teasing out missing reactions in genome-scale metabolic networks through hypergraph learning. Nature Communicutions, 14( 14):23377, 2023.
[12] Guobo Xie, Yinting Zhu, Zhiyi Lin, Yuping Sun, Guosheng Gu, Jianming Li, and Weiming Wang. Hbrwrlda: predicting potential Incrna-disease associations based on hypergraph bi- random walk with restart. Molecular Genetics and Genomics, 297 2022.
[13] Junliang Yu, Hongzhi Yin, Jundong Li, Qinyong Wang, Nguyen Quoe Viet Hung, and Xian- gliang Zhang. Self-supervised multi-channel hypergraph convolutional network for social recommendation. In Proceedings of the web conference 2021, pages 413-424, 2021.
[14] Dingqi Yang. Bingqing Qu, Jie Yang, and Philippe Mudre-Mauroux. Revisiting user mobility and social relationships lbsns: a hypergraph embedding approach. In The world wide web conference, pages 2147-2157, 2019.

---

[15] Junren Pan, Baiying Lei, Yanyan Shen, Yong Liu, Zhiguang Feng, and Shuqiang Wang. Characterization multimodal connectivity of brain network by hypergraph gan for alzheimer's disease analysis. In Pattern Recognition and Computer Vision: 4th Chinese Conference, PRCV 2021, Beijing, China, October 29-November 2021, Proceedings, Part 4, pages 467-478. Springer, 2021.
[16] Li Xiao, Junqi Wang. Peyman H Kassani, Yipu Zhang, Yuntong Bai, Julia Stephen, Tony W Wilson, Vince D Calhoun, and Yu-Ping Wang. Multi--ypergraph learning-based brain func- tional connectivity analysis in fmri data. IEEE transactions on medical imaging, 39(5): 1746-17588 2019.
[17] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3558-3565, 2019.
[18] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neurul Information Processing Systems, volume 19. MIT Press, 2006. URL bttps::/prroeeeings..eer neurips. ceteriss.ccpppppeeeee ippppe_fills/ppperrrteeeeeeeeeee fille/ bffeec2cc3331666Geeeee22299999 Paper.
[19] Naganand Yadati, Madhav Nimishakavi, Prateck Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. Advances in neural information processing systems, 32, 2019.
[20] Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor Pietro Perona, David Kriegman, and Serge Belongie. Beyond pairwise clustering. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 005,, volume 2, pages 838-845, IEEE, 2005,
[21] Song Bai, Feihu Zhang, and Philip HS Torr. Hypergraph convolution and hypergraph attention. Pattern Recognition, 110:107637, 2021.
[22] Matthias Hein, Simon Setzer, Leonardo Jost, and Syama Sundar Rangapuram. The total varia- tion on hypergraphs learning hypergraphs revisited. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Sys- tems, volume 26. Curran Associates, Inc., 2013. URL /ttp/t/pppp/proeeedinssseee .pff.
cc/
paper
[23] Pan Li and Olgica Milenkovic. Submodular hypergraphs: p-laplacians, Cheeger inequalities and spectral clustering. In Jennifer Dy and Andreas Krause, editors, Proceedingy of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3014-3023, PMLR, 10-15 Jul 2018. URL htlph: htttt:::////rooediggg...
mlr. .press/e//eeeee. /atiss//vv//// 1/80/1i18e.htm
[24] (Eli) Chien, Huozhi Zhou, and Pan Li. hs?: Active learning over hypergraphs with pointwise and pairwise queries. Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, volume 89 Proceedings of Machine Learning Research, pages 2466-2475. PMLR, 16-18 Apr 2019. URL https:://proceeeeeeeee
ceress/v89//e httcchhiennnn html.
[25] Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic. You are allset: A multiset function framework for hypergraph neural networks. In International Conference Learning Representations, 2022. URL https::/
[26] Ruochi Zhang, Yuesong Zou, and Jian Ma. Hyper-sagnn: self-attention based graph neural network for hypergraphs. In International Conference on Learning Representations, 2020. URL https://openreviee. net/ mett/oormmiddiieeee for
[27] Yuan Luo. SHINE: Subhypergraph inductive neural network. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances Neural Information Processing Systems, 2022. URL https://oppnrreviek net meeefoore
12

---

[28] Jing Huang and Jie Yang. Unignn: a unified framework for graph and hypergraph neural networks. Zui-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 2563-2569. International Joint Conferences on Artificial Intelligence Organization, 2021. doi: 10.24963/jjai.20211/
URL, https:
//doi. orgg 10. 24963/ //jjciiiiji/////// pttp:aaa..iaa/3.. Main Track.
[29] Ghadeer AbuOda, Gianmarco De Francisci Morales, and Ashraf Aboulnaga. Link prediction via higher-order motif features. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16-20, 2019, Springer, 2020.
Proceedings, Part I, pages
[30] Mayank Lahiri and Tanya Y Berger-Wolf, Structure prediction in temporal networks using frequent subgraphs. 2007 IEEE Symposium on computational intelligence and data mining. pages 35 42. IEEE, 2007.
[31] Mahmudur Rahman and Mohammad Al Hasan. Link prediction dynamic networks using graphlet. In Machine Leurning and Knowledge Discovery in Databuses: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part 16, pages 394 4944 Springer, 2016.
[32] Giang H Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Funyee Koh, and Sungchul Kim. Dynamic network embeddings: From random walks temporal random walks. In 2018 IEEE International Conference on Big Data (Big Data), pages 1085-1092. IEEE, 2018.
[33] Yanbang Wang. Ye Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive rep- resentation learning in temporal networks via causal anonymous walks. International Conference Learning Representations, 2021. URL httpp::/opperrrriie.tttte///ee id-KYPZ4YsCPJ.
[34] Ming Jin, Yuan-Fan Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning on continuous-timg time dynamic graphs In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL
[35] Zhining Liu, Dawei Zhou, Yada Zhu, Jinjie Gu, and Jingrui He. Towards fine-grained temporal network representation via time-reinforeed random walk. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4973-4984 2020.
[36] Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-tinn time dynamic network embeddings. In Companion proceedings of the the web conference 2018, pages 969-976, 2018.
[37] Timoteo Carletti, Federico Battiston, Giulia Cencetti, and Duccio Fanelli. Random walks on hypergraphs. Physical review E, 101(2)002308, 2020.
[38] Koby Hayashi, Sinan G Aksoy, Cheong Hee Park, and Haesun Park. Hypergraph random walks, laplacians, and clustering. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 504, 2020.
[39] Josh Payne. Deep hyperedges: a framework for transductive and inductive learning on hypergraphs, 2019.
[40] Uthsav Chitra and Benjamin Raphael. Random walks on hypergraphs with edge-dependent vertex weights. In International conference on machine learning, pages 1172-1181. PMLR, 2019.
[41] Sinan G. Aksoy, Cliff Joslyn, Carlos Ortiz Marrero, Brenda Praggastis, and Emilie Purvine. Hypernetwork science via high-order hypergraph walks. EPJ Data Science, 9()::6, Jun 2020. ISSN 2193-1127. doi: 10.1 (ttppppdd//s1188--22000-0--0 1140/epjds s116//111188811 220-00211-0.
URL https: //doi. htt////i..////////////// 100
13

---

[42] Austin R. Benson, David F. Gleich, and Lek-Heng Lim. The spacey random walk: A stochastic process for higher-order data. SIAM Review, 59(2):321-344 2017. doi: 10.1137/16M1074022.. URL. http:///ooooooo////////// 10. 11..111/166100400000
[43] Ankit Sharma, Shafiq Joty. Himanshu Kharkwal, and Jaideep Srivastava. Hyperedge2vec: Distributed representations for hyperedges, 2018. URL htttps///pperrevee..tt wttp//wwwee//fourneeeee
id=r35
[44] Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Andreas Peter Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy. MLP-mixer: An all-MLP architecture for vision. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https://openrevieet net/ for.mmid-E120OKKam.
[45] Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematies, 200:108- 122, 2016. ISSN 0166- 00tp:/000...000......000000.00.0
218X. doi: https://dbi.org/10010000. 201 5.05.035. URLhttps, /wwww/ sciencedi
[46] Ali Behrouz and Margo Seltzer. ADMIRE++: Explainable anomaly detection in the human brain via inductive learning on temporal multiplex networks. In ICML 3rd Workshop on Interpretable Machine Learning in Healthcare (IMLH), 2023. URL
[47] Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial. Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey, IEEE Access, 143- 79168, 2021.
[48] Youngjoo Seo, Michaël Defferarrd, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. International conference on neural information processing, pages 362-373. Springer, 2018.
[49] Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. T-gen: A temporal graph convolutional network for traffic prediction. IEEE Transactions Intelligent Transportation Systems, 21(9):384--388
2019.
[50] Hao Peng, Hongfei Wang, Bowen Du, Md Zakirul Alam Bhuiyan, Hongyuan Ma, Jianwei Liu, Lihong Wang, Zeyu Yang, Linfeng Du, Senzhang Wang, et al. Spatial temporal incidence dynamic graph neural networks for traffic flow forecasting. Information Sciences, 521:277-290, 2020.
[51] Xiaoyang Wang, Yao Ma. Yiqi Wang. Wei Jin, Xin Wang, Jiliang Tang, Caiyan Jia, and Jian Yu. Traffic flow prediction via spatial temporal graph neural network. In Proceedings The Web Conference 2020, pages 1082-1092, 2020.
[52] Jiaxuan You, Tianyu Du, and Jure Leskovec. Roland: Graph learning framework for dynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, page 2358-2366, New York, NY, USA, 2022. Association for Computing Machinery. ISEN 9781450393850. attps://dol: wow.lioorggiii wrw.o0g..1101 1...11146 1145 017553367783393333
doi: 10.1145/533467..3399000 URL
[53] Farnoosh Hashemi, Ali Behrouz, and Milad Rezaei Hajidehi. Cs-ign: Community search via temporal graph neural networks. In Companion Proceedings of the Web Conference 2023, WWW '23, New York, NY, USA, 2023. Association for Computing Machinery. doi: 00.1145/5538833358866 URL https: //doi. org/10. 1145/3543873, 3587654.
[54] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, page 2269-12782 New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450362016. 10. 10.1145//29250003330999 URL https://doo //doi. org 10. 1145 14453322500 .3300895
doi:
14

---

[55] Ali Behrouz and Margo Seltzer. Anomaly detection in multiplex dynamic networks: from blockchain security brain disease prediction. In NeurIPS 2022 Temporal Graph Learning Workshop, 2022. URL htt.tts://peeeeeeie...nntt wtt.:neet//ouumiiiddo000000000
[56] Sudhanshu Chanpuriya, Ryan Rossi, Sungchul Kim, Tong Yu, Jane Hoffswelll, Nedim Lipka, Shunan Guo, and Cameron N Musco. Direct embedding of temporal network edges via time- decayed line graphs. In The Fleventh International Conference on Learning Representations, net. fort//frum?/i ddQammzQQ_Tall
2023. URL
[57] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? The Eleventh International Conference on Learning Representations, 2023. URL https://openrevieet net/ /to///mmmddyyyppooyyi.
[58] Yuhong Luo and Pan Li. Neighborhood-awwee scalable temporal network representation learning. In The First Learning on Graphs Conference, 2022. URL https://openreview. net wot.:ommmm---ttteeeattt-
[59] Benjamin Paul Chamberlain, Sergey Shirobokov. Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. In The Eleventh International Conference on Learning Representations, 2023. URL htttss:/oppenrvieee wwt.vviiiiiinnforurtii id-mloqE0AozQU.
[60] Can Chen and Yang- Yu Liu. arXiv:2207.02911, 2022.
survey on hyperlink prediction.
arXiv preprint
[61] Devanshu Arya, Deepak Gupta, Stevan Rudinac, and Marcel Worring. Hyper[sage]: General- izing inductive representation learning on hypergraphs, 2021. URL https://oppereeieee net/forrum?idc=ccKKJCCTCCCC
[62] Devanshu Arya, Deepak K Gupta, Stevan Rudinac, and Marcel Worring. Adaptive neural message passing for inductive learning on hypergraphs. arXiv preprint 11X1v:2109.10683, 2021.
[63] Sameer Agarwal, Kristin Branson, and Serge Belongie. Higher order learning with graphs. In Proceedings of the 23rd international conference on Machine learning, pages 17-24, 2006.
[64] Chaoqi Yang, Ruijie Wang, Shuochao Yao, and Tarek Abdelzaher. Hypergraph learning with line expansion. arXiv preprint arXiv:2005.04880 2020.
[65] Kaize Ding, Jianling Wang, Jundong Li, Dingcheng Li, and Huan Liu. Be more with less: Hypergraph attention networks for inductive text classification. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 4927- 4936, Online, November 2020. Association for Computational Linguistics. doi: 10. 18653/11
URL https: htttt::t//ccaaaeeeee h/a.aaacanooooogo..o.ooooooooooe org/2620. www..emmll.0ee...mmmmmmmmm2mlllm waallp-main.300
[66] Boxin Du, Changhe Yuan, Robert Barton, Tal Neiman, and Hanghang Tong. Hypergraph pre-training with graph neural networks. arXiv preprint arXiv:2105.10862, 2021.
[67] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pages 855-864, 2016.
[68] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[69] Xin-Jian Xu, Chong Deng, and Li-Jie Zhang. Hyperlink prediction via local random walks and shnnenn divergence. Journal of Statistical Mechanies: Theory and Experiment, 2023(3):03342,, mar 2023. doi: 10.
URL http:///:: doi. orgg
10. 1088 1742-142220 5468/ /0//acc3l..
15

---

[70] Valerio La Gatta, Vincenzo Moscato, Mirko Pennone, Marco Postiglione, and Giancarlo Sperlí. Music recommendation via hypergraph embedding. IEEE Transactions on Neural Networks and Learning Systems, pages 1-13, 2022. doi: 10.11099TNNISS.2222.111
[71] Dingqi Yang, Bingqing Qu, Jie Yang, and Philippe
Revisiting user mobility and social relationships Ibsns: A hypergraph embedding approach. The World Wide Web Conference. WWW '19, page 2147-2157, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366748. doi: 10. 14.11449888888.3113666 URL 1145/ 000000855883333333
https://doi.orgi/
[72] Aurélien Ducournau and Alain Bretto. Random walks in directed hypergraphs and application to cemi-supervised image segmentation. Computer Vision and Image Understanding. 120: 91-102, 2014. ISSN 1077-3142. doi: https:/doi..or// 10. 10w.:.000000.ccii..1.......0
URL
http://wwwwsciiieeireeee... ottpo///caaa/e//rtto//////////10
[73] Lei Ding and Alper Yilmaz. Interactive image segmentation using probabilistic hypergraphs. Pattern Recognition, 43(5):1863-1877) 2010. ISSN 0031-3203. doi: https://doi.org/100 patcog. 2atcoog.009.11.022, URL http://wwwwwssiccceeeeeeeee wtt.:/o.mmscceeeeeeeeeeeceeieeee httm///iiccneerteeeeppiiii
50031320309904440.
[74] Sai Nageswar Satchidanand, Harini Anantbapadmanaban, and Balaraman Ravindran. Extended discriminative random walk: A hypergraph approach to multi-view multi-relational transduc- tive learning. In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAT' 15, page 3791-3799 AAAI Press, 2015. ISBN 9781577357384.
[75] Jie Huang, Chuan Chen, Fanghua Yc. Jiajing Wu, Zibin Zheng, and Guohui Ling. Hyper2vee: Biased random walk for hyper-network embedding. In Guoliang Li, Jun Yang. Joao Gama, Jug- gapong Natwichai, and Yongxin Tong, editors, Database Systems for Advanced Applications, pages 273 273-277, Cham, 2019. Springer International Publishing. ISBN 978-3-030- 18590-9.
[76] Jie Huang, Xin Liu, and Yangqiu Song. Hyper-path-bue path- representation learning for hyper- networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM '19, page 449-458, New York, NY. USA, 2019. Association for Computing Machinery. ISBN 978 978149036.763. doi: 10. 10.1145//35733843357777 URL https://doi.or: 10. 1145 /355//3353344333775533
[77] Jie Huang, Chuan Chen, Fanghua Ye. Weibo Hu, and Zibin Zheng. Nonuniform hyper-network embedding with dual mechanism. ACM Trans. Inf. Syst., 38(3), may 2020. ISSN 1046-8188. doi: 10. 145/3388924. URL attps://dot ootoorgg////// 10. 1145/338892
[78] Yunyu Liu, Jianzhu Ma and Pan Li. Neural predicting higher-order patterns in temporal networks. In Proceedings of the ACM Web Conference 2022, wwW '22, page 1340-1351, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 178149999995 doi: 10.1145/3485447.3555 447.4555577735111888 URL https::/doo http:///oooooo//////// 10. 1 101111///44444 3512181.
[79] Jiying Zhang, Fuyang Li, Xi Xiao, Tingyang Xu, Yu Rong, Junzhou Huang, and Yatao Bian. Hypergraph convolutional networks via equivalency between hypergraphs and undirected graphs, 2022. URL https::/openrrviieee net wttpe/iwwweenn.ttneeeeeeee /tt//frrmmm/dd22yyyxxff6.
[80] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus), 2020.
[81] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.066 (004:5007.0645,, 2016.
[82] David E Rumelhart, Geoffrey E Hinton, and Ronald Williams. Learning representations by back proppppppgg errors. nature, 323(6088):533 536,,336,,763 1986.
[83] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[84] da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, and kannan achan. Inductive represen- tation learning on temporal graphs. In International Conference on Learning Representations, 2020. URL https:///on htttt::///ppeeevieer met/formmiiddreeee
16

---

[85] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Self-attention with functional time representation learning. Advances in neural information processing systems, 32, 2019.
[86] Seyed Mehran Kazemi, Rishab Goel, Sepehr Eghbali, Janahan Ramanan, Jaspreet Sahota, Sanjay Thakur, Stella Wu, Cathal Smyth, Pascal Poupart, and Mareus Brubaker. Time2vec: Learning vector representation of time. arXiv preprini arXiv: urXiiv:197.0000 1907.0532,, 2019.
[87] Naganand Yadati, Vikram Nitin, Madhav Nimishakavi, Prateek Yadav, Anand Louis, and Partha Talukdar. Nhp: Neural hypergraph link prediction. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1705-1714, 2020.
[88] Tarun Kumar, K Darwin, Srinivasan Parthasarathy, and Balaraman Ravindran. Hpra: Hyper- edge prediction using resource allocation. In 12th ACM conference on web science, pages 135-143, 2020.
[89] Ye Xu, Dan Rockmore, and Adam M Kleinbaum. Hyperlink prediction in hypernetworks using latent social features. In Discovery Science: 16th International Conference, DS 2013, Singapore, October 6-9, 2013. Proceedings 16, pages 324-339. Springer, 2013.
[90] Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kaneza- shi, Tim Kaler, Tao Schardl, and Charles Leiserson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In Proceedings of the AAAI conference artificial intelligence. volume 34, pages 5363-5370, 2020.
[91] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
[92] Rossana Mastrandrea, Julie Fournet, and Alain Barrat. Contact patterns in high school: A comparison between data collected using wearable sensors, contact diaries and friendship surveys. PLOS ONE, 10(9):e0136497, 2015. doi: 10. (on1:7/forralll.oee00..3333 064977. URL
https://doi.org. 10. 1371/journal. pone. 01364977.
[93] Juliette Stehlé, Nicolas Voirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-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 primary school. PLoS ONE, 6(8)=22377, 2011. doi: 10.1371 wow.eornal..one.022333 org/10 10. 1371/journal. pone. 0023176.
URL https://doi.
[94] James H. Fowler. Connecting the congress: study of cosponsorship networks. Political Analysis, 14(04))455-445)) 2006. doi: 10. 1093/ppm/mml000.. URL https://doi. htt.:ttts///oi.org//////// org/10. p09302.
[95] James H. Fowler. Legislative cosponsorship networks in the US house and senate. Social Networks, 28(4):454-44) oct 2006. doi: 10. 10.1016/j soc.ett.cct...005.... 11.00.00......... 1.003. URL https://d// org/10 10/ 1016/j socnet. 2005. 10.003.
[96] Hao Yin, Austin R. Benson, Jure Leskovec, and David Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, 2017. doi: 10. 10.1145/30979833300888 https://doi.org: 20gg/00.1 0145/30097833 3098869.
URL
[97] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances neural information processing systems, 30, 2017.
[98] Fan RK Chung. The laplacian of a hypergraph. In "", 1993.
[99] Timoteo Carletti, Duccio Fanelli, and Renaud Lambiotte. Random walks and community detection in hypergraphs. Journal of Physics: Complexity, 2(1):015011, 2021.
[100] Linyuan and Xing Peng. High-order random walks and generalized laplacians on hyper- graphs. Internet Mathematics, 91):3-32, 2013.
17

---

[101] Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, and TH Hubert Chan. Re-revisiting learning on hypergraphs: confidence interval and subgradient method. In International Conference on Machine Learning, pages 4026-4034. PMLR, 2017.
[102] T-H Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, and Chenzi Zhang. Diffusion operator and spectral analysis for directed hypergraph laplacian. Theoretical Computer Science, 784: 46 46-64, 2019.
[103] Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. Advances in neural information processing systems, 30, 2017.
[104] Ziyu Wang, Wenhao Jiang, Yiming M Zhu, Li Yuan, Yibing Song, and Wei Liu. Dynamixer: vision mlp architecture with dynamic mixing. In International Conference on Machine Learning. pages 22691-22701. PMLR, 2022.
[105] Ali Behrouz, Parsa Delavari, and Farnoosh Hashemi. Unsupervised representation learning of brain activity via bridging voxel activity and functional connectivity, NeurIPS 2023 Al for Science Workshop, 2023. URL https://openiii /openreviee.. www.ee/.ee/oounreeeeeeeeee teee/foormnid-HSsggggFF
[106) Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
[107] Marta Gamelo, Dan Rosenbaum, Christopher Maddison, Tiago Ramalho, David Saxton, Murray Shanahan, Yee Whye Teh, Danilo Rezende, and SM Ali Eslami. Conditional neural processes. In International conference on machine learning, pages 1704-1713, PMLR, 2018.
[108] David Lopez-Paz, Robert Nishihara, Soumith Chintala, Bernhard Scholkopf, and Léon Bottou. Discovering causal signals in images. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 6979-6987, 2017.
[109] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention- based permutation-invant invariint neural networks. In International conference on machine learning, pages 3744-3753. PMLR, 2019.
[110] Jinheon Back, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In International Conference on Learning Representations, 2021. URL https://openreve
n Corom?idd=JHqqGGaat
[111] Ronald Harry Atkin. Mathematical structure human affairs. Heinemann Educational London, 1974.
[112] David Spivak. Higher-dimensional models of networks. arXiv preprint arXiv:0909.4314, 2009.
[113] 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.09068, 2019.
[114] Mustafa Hajij. Kyle Istvan, and Ghada Zamzmi. Cell complex neural networks. In TDA & Beyond, 2020. URL htttt::tt///pmeeee http://pwwwwweeeeeeeeeeo/nndddda ret.fforrmmiidd-6g1yyyyppp
[115] Celia Hacker. SkS-simplex2vec: a simplicial extension of node2vec. TDA & Beyond, 2020. URL
[116] Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial neural networks. In TDA & Beyond, 2020. URL
[117] Maosheng Yang, Elvin Isufi, and Geert Leus. Simplicial convolutional neural networks. In ICASSP 2022-2022 IEEE International Conference on Acousties, Speech and Signal Process- ing (ICASSP), pages 8847-8851, IEEE, 2022.
[118] Eric Bunch, Qian You, Glenn Fung, and Vikas Singh. Simplicial 2-complex convolutional neural networks. In TDA Beyond, 2020. URL. htt.tts///peeeeeiee...eeee net wwt.rewwwwweteooommiiii.e TLbnsKrt6J-.
18

---

[119] Christopher Wei Jin Goh, Cristian Bodnar, and Pietro Lio. Simplicial attention networks. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022. URL https://openreviert
[120] Mustafa Hajij, Karthikeyan Natesan Ramamurthy, Aldo Juzmán-Sáénzz and Ghada Za. High skip networks: A higher order generalization of skip connections. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning. 2022.
[121] Matthias Hein, Simon Setzer, Leonardo Jost, and Syama Sundar Rangapuram. The total varia- tion on hypergraphs learning on hypergraphs revisited. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Newral Information Processing Sys- tems, volume 26. Curran Associates, Inc., 2013. URL Ut..httpss//rrrccedns...nnoe .pff. httppp/e..1.lllaaaaaaaaaaa222220
cc/
[122] Sameer Agarwal, Kristin Branson, and Serge Belongie. Higher order learning with graphs. In Proceedings of the 23rd International Conference on Machine Learning, ICML '06, page 17-24, New York, NY, USA, 2006, Association for Computing Machinery. ISBN 1595933832. 1145 011198844.11188844 1143847. doi: 10. (0.1145/1 143844. 143847. URL https: //do:i:///iii wtw..o1..11//111111.11111111111.
[123] Edmund Ihler, Dorothea Wagner, and Frank Wagner. Modeling hypergraphs by graphs with the same mincut properties. Inf. Process. Letr., 17- mar 1993. ISSN 0020-0190. doi: 10. 00.1016/0020001909999911001 90115-P.
URL httLhtts://dbiiorg///1 10wp:////......000000000000 (0000009000990)
[124] Peihao Wang, Shenghao Yang. Yunyu Liu, Zhangyang Wang, and Pan Li. Equivariant hypergraph diffusion neural operators. In The Eleventh International Conference Learning Representations, 2023. URL https://opeerevieee
net forufoormiii
[125] Patrick Kidger, James Morrill, James Foster, and Terry Lyons. Neural controlled differential equations for irregular time series. Advances Neural Information Processing Systems, 33: 1196-6707. 2020.
[126] Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In Companion Pro- ceedings of the The Web Conference 2018, wWW '18 page 969-976, Republic and Canton Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. ISBN 978 4503564444. doi: 10.1145/184558.319155 URL https://doi. wtg/10.... 1145/ 3184558. 0194558.319156 3191526.
[127] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? In The Eleventh International Conference on Learning Representations, 2023. URL https://openrett ew. net/ formmm?id=ayPPoOSyLLL
19

---

Appendix
Table of Contents
A Preliminaries, Backgrounds, and Motivations
21
A.1 Anonymous Random Walks
21
A.2 Random Walk on Hypergraphs
Ilpergrahh......................
21
A.3 MLP-Mixer
22
B Additional Related Work
22
B.I Learning (Multi)Set Functions
22
B.2 Simplicial Complexes Representation Learning
23
B.3 How Does CAI-WALK Differ from Existing Works? (Contributions)
23
SET WALK and Random Walk on Hypergraphs
23
C.I Extension of SET WALKSSSS-
24
Efficient Hyperedge Sampling
25
E
Theoretical Results
26
E.1 Proof of Theorem
26
E.2 Proof of Theorem
28
E.3 Proof of Theorem 3
28
E,4 Proof Theorem
29
Proof Proposition
F
Experimental Setup Details
31
F.1
Datasets
31
F2
Basclines
32
F3 Implementation and Training Details
33
Additional Experimental Results
Results on More Datasets
34
G.2 Node Classification
................................
34
G.3 Performance in Average Precision
34
G.4 More Results on RNN v.s. MLP-MIXER in Walk Encoding
35
H Broader Impacts
36
20

---

A Preliminaries, Backgrounds, and Motivations
We begin by reviewing the preliminaries and background concepts that we refer to in the main paper. Next, we discuss the fundamental differences between our method and techniques from prior work.
A.1 Anonymous Random Walks
Micali and Zhu [45] studied Anonymous Walks (AWs), which replace a node's 's identity by the order of its appearance in each walk. Given a simple network, an AW starts from a node, performs random walks over the graph to collect sequence of nodes, W (U), (u.,,2...... H.), and then replaces the node identities by their order of appearance in each walk. That is:
(wo W) = [(4), 14:-1....4.. where K" is the smallest index such that ux- = wp-
(10)
While this method is simple anonymization process, it misses the correlation between different walks and assigns new node identities based only one single walk. The correlation between different walks is more important in temporal networks to assign new node identities, as a single walk cannot capture the frequency of a pattern over time [33]. To this end, Wang et al. [33] design set-based anonymization process that assigns new node identities based on a set of sampled walks. Given vertex иt they sample M walks with length starting from and store them in S, u. Next, for each node We that appears on at least one walk in S u. they assign a vector to each node as its hidden identity [33]:
g(wo, S []] = WWI E S.. W[i] = woll Vi m.)
(11)
where W[i] shows the i-th node in the walk W. This anonymization process not only hides the identity of vertices but it also can establish such hidden identity based on different sampled walks, capturing the correlation between several walks starting from a vertex.
Both of these anonymization processes are designed for graphs with pair-wise interactions, and there are three main challenges in adopting them for hypergraphs: I To capture higher- patterns, we use SETWALKS, which are sequence of hyperedges. Accordingly, we need an encoding for the position of hyperedges. A natural attempt to encode the position of hyperedges is to count the position of hyperedges across sampled SETWALKS, as CAW [33] does for nodes. However, this approach misses the similarity of hyperedges with many nodes in common. That is, given two hyperedges el [14, (2................. .........4. ( and e2 [u), .2..... ut 1). Although we want to encode the position of these two hyperedges, we also want these two hyperedges to have almost the same encoding as they share many vertices. Accordingly, first encode the position of vertices, and then we aggregate the position encodings of nodes that are connected by a hyperedge to compute the positional encoding of the hyperedge. ② However, since we focus on undirected hypergraphs. the order of a hyperedge's 's vertices in the aggregation process should not affect the hyperedge positional encodings. Therefore, we need permutation invariant pooling strategy. 3 While several existing studies used simple pooling functions such as MEAN(.) or SUM() [26), these pooling functions do not capture the higher-order dependencies between obtained nodes' position encodings, missing the advantage of higher-order interactions. That is, a pooling function such as MEAN(.) is a non-parametric method that sees the positional encoding of each node in hyperedge separately. Therefore, it is unable to aggregate them in a non-linear manner, which, depending on the data, can miss information. To address challenges 2 and O we design SIXMIX a permutation invariant pooling strategy that uses MLPs to learn how to aggregate positional encodings of vertices in a hyperedge to compute the hyperedge positional encoding.
suggest viewing hyperedge
set of vertices. We
A.2 Random Walk on Hypergraphs
Chung [98] presents some of the earliest research on the hypergraph Laplacian, defining the Laplacian of the k-uniform hypergraph. Following this line of work, Zhou al. [18] defined a two-step CE- based random walk- based Laplacian for general hypergraphs. Given node in the first step, we uniformly sample a hyperedge e including node u, and in the second step, we uniformly sample a node in e. Following this idea, several studies developed more sophisticated (weighted) CE-based random walks on hypergraphs [20]. However, Chitra and Raphael [40] shows that random walks on hypergraphs with inge-independent node weights are limited to capturing pair-wise interactions, making them unable to capture higher-order information. To address this limitation, they designed an edge-dependent sampling procedure of random walks hypergraphs. Carletti et al. [37] and Carletti
21

---

et al. [99] argued that to sample more informative walks from hypergraph. we must consider the degree of hyperedges in measuring the importance of vertices in the first step. Concurrently, some studies discuss the dependencies among hyperedges and define the s-th Laplacian based on simple walks on the dual hypergraphs [41, 100]. Finally, more sophisticated random walks with non-linear Laplacians have been designed [23, 101-103].
SETWALKS addresses three main drawbacks from existing methods: ① None of these methods are designed for temporal hypergraphsm so they cannot capture temporal properties of the network. Also, natural attempts to extend them to temporal hypergraphs and let the walker uniformly walk over time ignore the fact that recent hyperedges are more informative than older ones (see Table 2). To address this issue, SET WALK uses a temporal bias factor in its sampling procedure (Equation 1). ② Existing hypergraph random walks are unable to capture either higher-order interactions of vertices or higher-order dependencies of hyperedges. That is, random walks with edge-independent weights [37] are not able to capture higher-order interactions and are equivalent to simple random walks on the CE of the hypergraph [40]. The expressivity of random walks on hypergraphs with edge-dependent walks is also limited when we have limited number of sampled walks (see Theorem 1). Finally, defining a hypergraph random walk as random walk on the dual hypergraph also cannot capture the higher-order dependencies of hyperedges (see Appendix C and Appendix D). SETWALK by its nature is able to walk over hyperedges (instead of vertices) and time and can capture higher-order interactions. Also, with structural bias factor in its sampling procedure, which is based on node weights, it is more informative than a simple random walk on the dual hypergraph, capturing higher-order dependencies of hyperedges. See Appendix C for further discussion.
A.3 MLP-Mixer
MLP-MIXER [44] is family of models, based on multi-layer perceptions (MLPs), that are simple, amenable to efficient implementation, and robust to long-term dependencies (unlike RNNS, attention mechanisms, and Transformers [83]) with a wide array of applications from computer vision [104] to neuroscience [105]. The original architecture is designed for image data, where it takes image tokens as inputs. It then encodes them with a linear layer, which is equivalent to a convolutional layer over the image tokens, and updates their representations with sequence of feed-forwate layers applied to image tokens and features. Accordingly, we can divide the architecture of MLP-MIXER into two main parts: I Token Mixer: The main intuition of the token mixer is to clearly separate Channel
the cross-location operations and learn the cross-feature (cross-location) dependencies. Mixer: The intuition behind the channel mixer is clearly separate the per-location operations and provide positional invariance, a prominent feature convolutions. In both MIXER and SETMIXER we use the channel mixer as designed in MLP-MIXER Next, we discuss the token mixer and its limitation in mixing features in a permutation variant manner:
Token Mixer. Let E be the input of the MLP-MIXER, then the token mixer phase is defined as:
Hooeen E + Wx2) (W()) loken token LayerNorm (E)")"
(12)
where or.) is nonlinear activation function (usually GeLU [80]). Since it feeds the input's columns to an MLP, it mixes the cross-feature information, which results in the MLP-MIXER being sensitive to permutation. Although natural attempts to remove the token mixer or its linear layer can produce a permutation invariant method, it misses cross-feature dependencies, which are the main motivation for using the MLP-MIXER architecture. To address this issue, SET uses the Softmax(.) function over features. Using Softmax over features can be seen as cross-feature normalization, which can capture their dependencies. While Softmax..) is non-parametric method that can bind token-wiss, information, it is also permutation equivariant, and as we prove in Appendix E.3, makes the SETMIXER permutation invariant.
B
Additional Related Work
B.1 Learning (Multi)Set Functions
(Multi)set functions are pooling architectures for (multi)sets with wide array of applications in many real-world problems including few-shot image classification [106], conditional regression [107], and causality discovery [108]. Zaheer et al. [97] develop DEEPSETS, universal approach to parameterize
22

---

the (multi)set functions. Following this direction, some works design attention mechanisms to learn multiset functions [109], which also inspired Back et al. [110] to adopt attention mechanisms designed for (multi)set functions in graph representation learning. Finally, Chien et al. [25] build the connection between learning (multi)set functions with propagations on hypergraphs. To the best of our knowledge, SETMIXER is the first adaptive permutation invariant pooling strategy for hypergraphs, which views each hyperedge as a set of vertices and aggregates node encodings by considering their higher-order dependencies.
B.2 Simplicial Complexes Representation Learning
Simplicial complexes can be considered special case of hypergraphs and are defined as collection of polytopes such as triangles and tetrahedra, which are called simplices [111]. While these frameworks can be used to represent higher-order relations, simplicial complexes require the downward closure property [1 12]. That is, every substructure or face of a simplex contained in a complex K is also in K. Recently, to encode higher-order interactions, representation learning simplicial complexes has attracted much attention [6. 1 113-1 19]. The first group of methods extend node2vec [67] to simplicial complexes with random walks interactions through Hasse diagrams and simplex connections inside p-chains [113, 115]. With the recent advances in message- sasraggeppasinng-aaeeee
methods, several studies focus on designing neural networks on simplicial complexes [116-119]. Ebli et al. [116] introduced Simplicial neural networks (SNN), a generalization of spectral graph convolutio,n to simplicial complexes with higher-order Laplacian matrices. Following this direction, some works propose simplicial convolutional neural networks with different simplicial filters to exploit the relationships in upper- and wewer-neggboorhodss [117, 118). Finally, the last group of studies use an encoder-decoder architecture as well as message- paatigng to learn the representation of simplicial complexes [1 14, 120].
MAr-WALK is different from all these methods in three main aspects: I Contrary these methods, CAL-WALK is designed for temporal hypergraphs and is capable of capturing higher-order temporal properties in streaming manner, avoiding the drawbacks of snapshot-based methods. ② CAr- WALK works in the inductive setting by extracting underlying dynamic laws of the hypergraph, making generalizable to unseen patterns and nodes. 3 All these methods are designed for simplicial complexes, which are special cases of hypergraphs, while CAI-WALK is designed for general hypergraphs and does not require any assumption of the downward closure property.
B.3 How Does CAT-WALK Differ from Existing Works? (Contributions)
As we discussed in Appendix A.2, existing random walks on hypergraphs are unable to capture either ① higher-order interactions between nodes or @ higher-order dependencies of hyperedges. Moreover, all these walks are for static hypergraphs and are not able to capture temporal properties. To this end, we design WATWALK a higher-order temporal walk on hypergraphs. Naturally, WALWALK are capable of capturing higher-order patterns as a WALK defined as a sequence of hyperedges. We further design a new sampling procedure with temporal and structural biases, making SET WALKS capable of capturing higher-order dependencies of hyperedges. To take advantage of complex information provided by SETWALKS as well as training the model in an inductive manner, we design two-step anonymization process with novel pooling strategy, called SETMIXER. The anonymization process starts with encoding the position of vertices with respect to set of sampled SETWALKS and then aggregates node positional encodings via a non-linear permutation invariant pooling function, SETMIXER, to compute their corresponding hyperedge positional encodings. This two-step process lets us capture structural properties while we also care about the similarity of hyperedges. Finally, to take advantage of continuous-time dynamics in data and avoid the limitations of sequential encoding, we design a neural network for temporal walk encoding that leverages a time encoding module to encode time as well as a MIXER module to encode the structure of the walk.
C SET WALK and Random Walk on Hypergraphs
We reviewed existing random walks in Appendix A.2. Here, we discuss how these concepts are different from SETWALKS and investigate whether SETWALKS more expressive than these methods.
As we discussed in Sections 1 and 3.2, there are two main challenges for designing random walks on hypergraphs: ! Random walks are sequence of pair-wise interconnected vertices, even though
23

---

edges in hypergraph connect sets of vertices. 2 A sampling probability of a walk on hypergraph must be different from its sampling probability on the CE of the hypergraph [37-43]. To address these challenges, most existing works on random walks on hypergraphs ignore ① and focus on @ to distinguish the walks on simple graphs and hypergraphs, and ① relatively unexplored. To this end, we answer the following questions:
Q1: Can 2 alone be sufficient to take advantage of higher-order interactions? First, semanti- cally, decomposing hyperedges into sequences of simple pair-wise interactions (CE) loses the semantic meaning of the hyperedges. Consider the collaboration network in Figure 1. When de- composing the hyperedges into pair-wise interactions, both (A, B, C) and (H, G. E) have the same structure (a triangle), while the semantics of these two structures in the data are completely different. That is, (A, B, C)) have all published a paper together, while each pair of (H, G, E) separately have published paper. One might argue that although the output of hypergraph random walks and simple random walks on the CE might be the same, the sampling probability of each walk is different and with large number of samples, our model can distinguish these two structures. In Theorem I (proof in Appendix E) we theoretically show that when we have a finite number of hypergraph walk samples, M, there is hypergraph G such that with M hypergraph walks, the G and its CE are not distinguishable. Note that in reality, the bottleneck for the number of sampled walks in machine learning-base based methods is memory. Accordingly, even with tuning the number of samples for each dataset, the size of samples is bounded by a small number. This theorem shows that with a limited budget for walk sampling, @ alone is not enough to capture higher-order patterns.
Q2: Can addressing I alone be sufficient to take advantage of higher-order interactions? To answer this question, we use the extended version of the edge-to-vertex dual graph concept for hypergraphs:
Definition 4 (Dual Hypergraph). Given hypergraph G (V, the dual hypergraph of G is defined as & (V, &), where V & and hyperedge ē (e1, e2.,e,....
exl E & shows that ni e; 0.
To address D. we need to see walks on hypergraphs as a sequence of hyperedges (instead of a sequence of pair-wise connected nodes). One can interpret this as a hypergraph walk on the dual hypergraph. That is, each hypergraph walk on the dual graph is a sequence of G's hyperedges: eg. However, shown by Chitra and Raphael [40]. each walk on hypergraphs with edge-independent weights for sampling vertices is equivalent to a simple walk on the (weighted) CE graph. To this end, addressing ② alone can be equivalent to sample walks on the CE of the dual hypergraph, which misses the higher-order interdependencies of hyperedges and their intersections.
et e2
Based on the above discussion, both I and 2 are required to capture higher-order interaction between nodes as well as higher-order interdependencies of hyperedges. The definition of SETWALKS (Definition 3) with structural bias, introduced in Equation 1, satisfies both O and 2. In the next section, we discuss how a simple extension of SETWALKS can not only be more expressive than all existing walks on hypergraphs and their CEs, but its definition is universal, and all these methods are special cases of extended SETWALK.
C.1 Extension of SET WALKS
Random walks on hypergraphs are simple but less expressive methods for extracting network motifs, while SETWALKS are more complex patterns that provide more expressive motif extraction approaches. One can model the trade-off of simplicity and expressivity to connect all these concepts in a single notion of walks. To establish a connection between SET WALKS and existing walks on hypergraphs, as well as a universal random walk model on hypergraphs, we extend SETWALKS S-SETWALSS, where parameter r controls the size of hyperedges that appear in the walk:
Definition 5 (ELKK)))))), Given temporal hypergraph G = (V,E, EX),, and a threshold E Z r-SETWALK with length E on temporal hypergraph G is a randomly generated sequence of hyperedges (sets):
Sw: (e1, - (02, -... (et, lec)
where e; E &, leil S fea1 < le and the intersection of e; and ei4 is not empty, es D. eeel # O. In other words, for each S i E 1: e+t E (e)). We use Sw[i) to denote the i-th hyperedge-time pair in the SETWALK. That is, Sw[i][0] = e, and Sw[i][1] fe,
24

---

The only difference between this definition and Definition 3 is that r-SETWALK limits hyperedges in the walk hyperedges with size most The sampling process of r-SETWALKS is the same as that of SETWALK (introduced in Section 3.2 and Appendix D), while we only sample hyperedges with size most r. Now to establish the connection of r-SETWALKS and existing walks on hypergraphs, we define the extended version of the clique expansion technique:
Definition 6 (r-Projected Hypergraph). Given a hypergraph G = -V, E) and an integer r 2 2, we construct the (weighted) r-projected hypergraph of G as a hypergraph G, =V, &,), where for each &:
e [11,
........,, .,,,......,............ u4)
1. ifk r: add the En,
1: add e; = (Mn M2z. ".; ú; to Eo. every possible (i, .4, E (1, ..,,..kk)) 2. ifk 2 + r
Each of steps or 2 can be done in a weighted manner. In other words, we approximate each hyperedge with size of more than with (+) (weighted) hyperedges with size For example, when r= 2, the 2-projected graph of G is equivalent to its clique expansion, and r= oo is the hypergraph itself. Furthermore, we define the Union Projected Hyperaph (UP hypergraph) as the union of all r-projected hypergraphs, i.e., G" = (V, UP= &, Note that the UP hypergraph has the downward closure property and is equivalent the simplicial complex representation of the hypergraph G. The next proposition establishes the universality of the r-SETWALK concept.
Proposition 2. Edge-independers random walks hypergraphs [37], edge-dependent random walks on hypergraphs [40], and simple random walks on the CE of hypergraphs are all special cases of r-SETWALK, when applied the 2-projected graph, UP hypergraph, and 2-projected graph, respectively. Furthermore, all the above methods are less expressive than r-SETWALKS
The proof of this proposition is in Appendix F.5.
D Efficient Hyperedge Sampling
For sampling SETWALKS, inspired by Wang et [33], we use two steps: ! Online score computation: we ussign set of scores to each incoming hyperedge. @ Iterative sampling: we use assigned scores the previous step sample hyperedges in a SETWALK.
Algorithm Online Score Computation
Input: Given a hypergraph G = (V. E) and a [0, 1]
Output: A probability score for each vertex
I: P 0:
2: for (e.t) & with an increasing order of do
Po.[0] + exp (ar);;
4: Pa.[1] - 0, P..(22] - 0, P.,[3] - 0:
5:
for u E do
6: for (u) do
if e, is visited then
Pa.[2] <- P.,[[] + explyle,, e));
9:
Pa.[3] < Pa.[3] U (exple(e...))) e));:
10:
Pa[lI] P.,[I] expla X ());
return P:
Online Score Computation. The first part essentially works in an online manner and assigns each new incoming hyperedge a four-tuple of scores:
Pe.[0] = exp(a X f),
Pat[1]= =
Σ exp (axxx)
Per12] =
Σ exp(v(e,e')),
= [ex])=(exx(p(e,,,11 e'))
Iterative Sampling. the iterative sampling algorithm, we use pre-computed scores by Algorithm and sample hyperedge (e.t) given previously sampled hyperedge (ep. 1p). In the next proposition,
25

---

Algorithm 2 Iterative SETWALK Sampling
Input: Given a hypergraph G (V.&), E [0, 1], and previously sampled hyperedge (pp-
Output: Next sampled hyperedge (e
I: for (e.t) (ep) with an decreasing order of t do
2: Sample b ~ UNIFORM(O, 1):
3: Get Pc,10J, Po.., [r,,, Pe,,,122 and yle, ep) from the output of Algorithm 1;
4:
Normalize Fep-p.11 Ppp
5: if b P then return (e;
return (ex, Ix):
(ex. fx) is dummy empty hyperedge signaling the end of algorithm.
22
U2
U4
u4
u1
u1
:
UM(L+1)+1
(L++))
M
(L++I
M(L+1)++
g
2-Projected Hypergraph
3 3-Projoceed Hypergraph
Figure 6: The example of hypergraph G and its 2- and 3-projected hypergraphs.
we show that this sampling algorithm samples each hyperedge with the probability mentioned in Section 3.2.
Proposition 3. Algorithm sample a hyperedge (e,1) after (ep, 4p) with a probability proportional to fp) (Equation 1).
How can this sampling procedure capture higher-order patterns? As discussed in Appendix C,
SETWALKS G can be interpreted as random walk on the dual hypergraph of G. G. However, simple (or hyperedge-independeen) random walk on the dual hypergraph equivalent to the walk on the CE of the dual hypergraph [40, 41], missing the higher-order dependencies of hyperedges. Inspired by Chitra and Raphael [40], we use pegerede--depndeer weights I V & - R and sample hyperedges with a probability proportional to exp (Zweene, I(u, e e²)). where ep is the previously sampled hyperedge. the dual hypergraph و = (E,V), VV,, we assign a score f' 8 V - R to each pair of (e, 4) ('e, u) = I(u,e). e). Now, SETWALK with this sampling procedure is equivalent to the degeedeeendent hypergraph walk on the dual hypergraph of G with edge-dependent weight f(). Chitra and Raphael [40] show that an edge-dependent hypergraph random walk capture some information about higher-order interactions and is not equivalent to a simple walk on the weighted CE of the hypergraph. Accordingly, even on the dual hypergraph, SETWALK with this sampling procedure can capture higher bigher-order order dependencies of hyperedges and is not equivalent to a simple walk on the CE of the dual hypergraph G. We conclude that, unlike existing random walks on hypergraphs [37, 38, 41, 79]. SETWALK can capture both higher-order interactions of nodes, and, based on its sampling procedure, higher-order dependencies of hyperedges.
E Theoretical Results
E.1 Proof of Theorem 1
Theorem 1. A random SETWALE is equivalent neither the hypergraph random walk, the random walk on the CE graph, nor the random walk on the SE graph. Also, for a finite number of samples of each, SETWALK is more expressive than existing walks.
Proof. In this proof, we focus on the hypergraph random walk and simple random walk on the CE. The proof for the SE graph is the same and also it has been proven that the SE graph and the CE of hypergraph have close (or equal in uniform hypergraphs) Laplacian and have the same expressiveness power in the representation of hypergraphs [121-123].
First, note that each WATWALK can be approximately decomposed to a set of either hypergraph walks, simple random walks, or walk on the SE. Morcover, each of these walks can be mapped to
26

---

a corresponding SETWALK (but not a bijective mapping), by sampling hyperpedges corresponding to each consecutive pair of nodes in these walks. Accordingly, SETWALKS includes the information provided by these walks and so its expressiveness is not less than these methods. To this end, next, we discuss two examples in two different tasks for which SETWALKS are successful while other walks fail.
① In the first task, we want to see if there exists a pair of hypergraphs with different semanties that SETWALKS can distinguish, but other walks cannot. We construct such hypergraphs. Let G = (V. 8) be hypergraph with V = {4n M2..... uyy and = [(e, ())] where e [u]. u2...., Uyy and < <... < fy. Also, let A be an edge-independenn hypergraph random walk (or random walk on the CE) sampling algorithm. Chitra and Raphael [40] show that each of these walks is equivalent to random walk on the weighted CE. Assume that {()) is function that assigns weights to edges in G = (V.E") ). the weighted CE of the G. such that a hypergraph random walk on G is equivalent to walk on this weighted CE graph. Next, we construct weighted hypergraph G' (VVE') with the same set of vertices but with & Uk=1((u; 4j), 14 Ny, such that each edge et,- = (4; Uy) is associated with weight E(e,,). Clearly, sampling procedure A on G and G' are the same, while they have different semantics. For example, assume that both are collaboration networks. In G. all vertices have published single paper together, while in G', each pair of vertices have published separate paper together. The proof for the hypergraph random walk with supeedgeeddppendent weights is the same, while we construct weights of the hypergraph G' based on the sampling probability of hyperedges in the hypergraph random walk procedure.
② Next, in the second task, we investigate the expressiveness of these walks for reconstructing hyperedges. That is, we want to see that given a perfect classifier, can these walks provide enough information to detect higher-order patterns in the network. To this end, we show that for a finite number of samples of each walk, WALK is more expressive than all of these walks in detecting higher-order patterns. Let M be the maximum number of samples and L be the maximum length of walks, we show that for any M 2 2 and 2 2 there exists a pair of hypergraphs G. with higher-order interactions, and G', with pairwise interactions, such that SETWALKS can distinguish them, while they are indistinguishable by any of these walks. We construct a temporal hypergraph G = (V.E) as hypergraph with V = [ut, M2,..., MMLL+1)+1 and & ((e, 1))/ where e {ui u2..... (ML++++) and f < 12 <... < Jz. We further construct G' = (V, P') with the same set of vertices but with E Uk-Il((,,,)) uy). (I),,, Figure illustrates G and its projected graphs a given timestamp I E (41, N1.12....,,1!
SET with only one sample, Sw, can distinguish interactions in these two hypergraphs. That is, let Sw: (e, fr) + (t,1)-1) - -> (e, 11) be the sample SET from G (note that masking the time, this is the only SETWALK on G. so in any case the sampled SETWALK is Sw). Since all interactions in G' are pairwise, any sampled SETWALK on G., Sw', includes only pairwise interactions, so Sw # Sw', in any case. Accordingly, SETWALK can distinguish interactions in these two hypergraphs.
Since the output of hypergraph random walks, simple walks on the CE, and walks on the SE include only pairwise interactions, it seems that they are unable to detect higher-order patterns, so are unable to distinguish these two hypergraphs. However, one might argue that by having a large number of sampled walks and using perfect classifier, which learned the distribution of sampled random walks and can detect whether a set of sampled walks is from a higher-order interaction, we might be able to detect higher-order interactions. To this end, we next assume that we have perfect classifier C(.) that can detect whether a set of sampled hypergraph walks, simple walks on the CE, or walks on the SE are sampled from a higher-order structure or pair-wise patterns. Next, we show that hypergraph random walks cannot provide enough information about every vertex for C(. to detect whether all vertices in V shape hyperedge. To this end, assume that we sample S = (W,. W Warl walks from hypergraph G and S' = (W", Wy...., W walks from hypergraph G.. In the best case scenario, since C()) is perfect classifier, sampled walk S'. To distinguish these two hypergraphs, we need C(.) to detect sampled walks from G (i.e., S) that come from higher-order pattern. For any M sampled walks with length L from G. we observe at most MX x (L+ 1) vertices, so we have information about at most M x (L+ 1) vertices, unable to capture any information about the neighborhood of at least one vertex. Due the symmetry of vertices, without loss of generality, we can assume that this vertex is un This means that with these M sampled hypergraph random walks with length L, we are not able to provide any information about node ii at any timestamp for C(.). Therefore, even a perfect classifier C(.) cannot verify whether #j
detect that G' includes only pair-wise interactions based on
27

---

is a part of higher-ore ooder interaction or pair-wise interaction, which completes the proof. Note that the proof for the simple random walk completely the same.
Remark Note that while the first task investigates the expressiveness of these methods with respect to their sampling procedure, the second lasks discuss the limitation and difference in their outputs.
Remark 2. Note that in reality, we can have neither an unlimited number of samples nor an unlimited walk length. Also, the upper bound for the number of samples or walk length depends on the RAM of the machine on which the model is being trained. In our experiments, we observe that usually, we cannot sample more than 125 walks with batch size of 32.
E.2 Proof of Theorem 2
Before discussing the proof of Theorem we first formally define what missing information means in this context.
Definition 7 (Missing Information). We say pooling strategy like VC) misses information if there is a model M such that using Y()) on top of the M (call it M) decreases the expressive power of M. That is, M has less expressive power than M.
Theorem 2. Given arbitrary positive integer k E Zz, let V() be pooling function such that for any set S Wi.....Wall
Y(S) = S(S),
(13)
S'ES
where f is some function. Then the pooling function can cause missing information, limiting the expressiveness of the method applying to the projected (hyper)graph of the hypergraph.
Proof. The main intuition of this theorem is that a pooling function needs to capture higher-order dependencies of its input's elements and if it can be decomposed a summation of functions that capture lower-order dependencies, it misses information. We show that, in the general case for a given hypergraph G is at most as expressive as Y.() when applied to the k-projected hypergraph of & (Definition 6). Let G = (V,E) be a hypergraph with ()) for a given time r, and & = (V. be its k-projected graph, i.e., & = [(e), ..... (e(ri)) ()) where C (4), 42...., Mx+1) such that legl= Applying pooling function YP(.) on the hypergraph G is equivalent to applying V((.) to the hyperedge (V,1) &, which provides V(VV) 2 f(e;). On the other hand, applying YI(() on projected graph & mcans applying it each hyperedge e, E E. Accordingly, since for each hyperedge E & we have Y'ee; f(e)), all captured information by pooling function Y!(.) on & is the set of S = [f It is clear that V(VV)= EA+1 f(e;) is less informative than =[((e))
k E Z the pooling function Y(() when applied
V = [ui, .,...... 44-1) i) and & = ((V, ()) = ((tu),
is the summation of elements in S (in fact, VV(V) cannot capture the non-linear combinations of positional encodings of vertices, while can). Accordingly, the provided information by applying YP(.) on G cannot be more informative than applying Y(() on the G's k-projected hypergraph.
Remark 3. Note that the pooling function T(()) is defined on a (hyper)graph and gets only (hy- perjedges input.
Remark 4. Although Y(.) MEAN(.) cannot be written as Equation 13, we can simply see that the above proof works for this pooling function as well.
E.3 Proof of Theorem 3
Theorem 3. SETMIXER is permutation invariant and is a universal approximator of invariant multi-set functions. That is, SETMIXER can approximate any invariant multi set function.
Proof. Let x(S) be a given permutation of set S, we aim to show that VP(S) = ()((S)) We first recall the SETMIXER and its phases: Let = (Vi...., Val. where v, Rdi be the input set and
[V]...., vaJ" e daxd be its matrix representation:
P(V) MEAN Hooken + a (LayerNorm (Hoken)) w(")) w?l). (Channel Mixer)
28

---

where
Hoken V (Softmax ( (LayerNorm (V)*))
(Token Mixer)
Let (VV) (aa). Vmunl be permutation of the input matrix V. In the token mixer phase, None of LayerNorm, Softmax, and activation function o()) can affect the order of elements (note that Softmax is applied row-wise). Accordingly, we can see the output of the token mixer is permuted by π():
Hoken (V)) n(V) o (So Soofmax (LayerNorm (xx (v))))
=V(V) x
(Softmax (SoftmaxxLayerrNoor (LayerNorm (V)
V + or (Softmax (ooftmaaxLayyerorrrr (LayerNorm (V))
π (H V)).
(14)
Next, in the channel mixer, by using Equation 14 we have:
V()((V) =
MEAN
(HHken))) ) + o [LaeeNorr (H W(!)) wx
=
MEAN
([Hoken
+ π (or (LayerNorm (Hoke)) w(l)) W!
=
MEAN (T(Hoken))
+ π (or (LayerNorm (Hoken) w! (1 w(?))
= MEAN (IT (Heseen + W (LayerNorm (oonr w(")))
= -VV)..
(15)
In the last step, the fact that MEAN(.) is permutation invariant. Based Equation 15 can see that SETMIXER is permutation invariant.
Since the token mixer is just normalization is inevitable and cannot affect the expressive power of SETMIXER. Also, channel mixer is a 2-layer MLP, which is the universal approximator of any function. Therefore, SETMIXER is universal approximator.
E.4 Proof of Theorem 4
Theorem The set-bused anonymization method more expressive than any existing anonymization strategies the CE of the hypergraph. More precisely, there exists pair of hypergraphs Gi (V),&, and G2 (V))E)) with different structures (i.e., 9 & G2) that are distinguishable by our anonymization process and are not distinguishable by the CE-based methods.
Proof. To the best of our knowledge, there exist two anonymization processes for random walks by Wang al. [33] and Micali and Zhu [45]. Both of these methods are designed for graphs and to adapt them to hypergraphs we need to apply them to the (weighted) CE. Here, we focus on the process designed by Wang al. [33], which is more informative than the other. The proof for the Micali and Zhu [45] process is the same. Note that the goal of this theorem to investigate whether method can distinguish a hypergraph from its CE. Accordingly, this theorem does not provide any information about the expressivity of these methods in terms of the isomorphism test.
The proposed 2-step anonymization process can be seen as positional encoding for both vertices and hyperedges. Accordingly, it is expected to assign different positional encodings to vertices and hyperedges of two non-isomorphism hypergraphs. To this end, we construct the same hypergraphs as in the proof of Theorem 1. Let be the number of sampled SETWALKS with length L. We construct a temporal hypergraph
(V, E) as hypergraph with V {Mi, (2,, ... UML--++1 and & = ((e, ((), where e [N), .2..... "MLL+I>-1) and f < 12 < < ft. We further construct G (V.8') with the same set of vertices but with & = Ul_, u,), Wu.uu. As we have seen in Theorem random walks the CE of the hypergraph cannot distinguish these two hypergraphs. Since CAW [33] also uses simple random walks, cannot distinguish these two hypergraphs. Accordingly, after its anonymization process, again cannot distinguish these two hypergraphs.
The main part of the proof to show that in our method, the assigned positional encodings are different in these hypergraphs. The first step is to assign each node positional encoding, Masking
29

---

the timestamps, there is only one SETWALK in the G. Accordingly, the positional encodings of nodes in G are the same and non-zero. Given SETWALK with length L we might see most LX (dmax 1) nodes, where dmax is the maximum size of hyperedges in the hypergraph. Accordingly, with M samples on G', which dmax= 2, we can see at most M (I++ 1) vertices. Therefore, in any case, we assign zero vector to at least one vertex. This proves that the positional encodings by SET are different in these two hypergraphs, and if the assigned hidden identities to counterpart nodes are different, clearly, feeding them to the SETMIXER results in different hyperedge encodings.
Note that each SETWALK can be decomposed into a set of causal anonymous walks [33]. Accordingly, it includes the information provided by these walks, so its expressiveness is not less than the CAW method on hypergraphs, which completes the proof of the theorem.
Although the above statement completes the proof, next discuss that even given the same positional encodings for vertices in these two hypergraphs, SETMIXER can capture higher-order interactions by capturing the size of the hyperedge. Recall token mixer phase in SETMIXER:
V + o (Softmax (LayerNorm(V))) VV
akken
where V .v....., MML+D++ I' RRML++))Dddd and v # 0ixd: represents the positional encoding of in G. We assumed that the positional encoding of in G' is the same, The input of the token mixer phase on G is V as all of them are connected by a hyperedge. Then we have:
exp(v.,)
H (Hoken)i.j = Vijj o
(16)
- M(L++)+ exp(vx.))
On the other hand, when applied to hypergraph G' and (uk,, m.:) We have:
exp(v.)) HH token Di. Vi. + exp(vi;.)) + exp(vs..)) ie (k1,
cxp(v..)
(17)
Since we use zero padding, for any i 2 3, (Hokenn). O and (H (oken))) )i.j O. These zero rows, which capture the size of the hyperedge, result in different encodings for each connection.
Remark 5. the best of our knowledge, the only anonymization process that used on hypergraphs is by Liu et al. [78], which uses simple walks on the CE and is the same as Wang et al. [33]. Accordingly, it also suffers from the above limitation. Also, note that this theorem shows the limitation of these anonymization procedures when simply adopted to hypergraphs.
E.5 Proof of Proposition? 2
Proposition 2. Edge-independent random walks on hypergraphs [37], edge-dependent random walks on hypergraphs [40], and simple random walks the CE of hypergraphs are all special cases of WASK when applied to the 2-projected graph, UP graph, and 2-projected graph, respectively. Furthermore, all the above methods are less expressive than r SETWALKS.
Proof. For the first part, we discuss each walk separately:
I Simple random walks the CE of the hypergraphs: We perform 2- 2-SERWALKS the (weighted) 2-projected hypergraph with I(.) = 1. Accordingly. for every two adjacent edges in the 2-Projected graph like e and e', we have sp(e,e) 1. Therefore, it is equivalent to simple random walk on the CE (2-projected graph).
2 Edge-indepee ingeeinndeennentt random walks hypergraphs: As is shown by Chitra and Raphael [40], each edge-independent random walk on hypergraphs is equivalent to a simple random walk on the (weighted) CE of the hypergraph. Therefore, as discussed in O, these walks are special case of r- --T WALKS, when r = and applied to (weighted) 2- 2-Projected hypergraph.
3 edge-dependern random walks on hypergraphs: Let l'(e, u) be an adge-dependenns weight function used in the hypergraph random walk sampling. For each node u in the UP hypergraph, we store the set of (e, u) that is a maximal hyperedge that belongs to. Note that there might be several maximal hyperedges that u belongs to. Now, we perform 2ASETWALK sampling on the UP hypergraph with these weights and in each step, we sample each hyperedge with weight I(u, e) I' u). It is
30

---

straightforward to show that given this procedure, the sampling probability of a hyperedge is the same in both cases. Therefore, edge-dependent random walks on hypergraphs are equivalent to 2-SETWALKS when applied to the UP hypergraph.
As discussed above, all these walks are special cases of r-SETWALKS and cannot be more expressive than r-SETWALKS. Also, as discussed in Theorem I, all these walks are less expressive than SET WALKS, which are also special cases of r-SEIWALKS, when co. Accordingly, all these methods are less expressive than --SETWALKS.
F
Experimental Setup Details
F.1
Datasets
We 10 publicly available benchmark datasets, whose descriptions follows:
NDC Class [6]: The NDC Class dataset is a temporal higher-order network. in which each hyperedge corresponds to an individual drug, and the nodes contained within the hyperedges represent class labels assigned to these drugs. The timestamps. measured in days, indicate the initial market entry of each drug. Here, hyperedge prediction aims to predict future drugs.
NDC Substances [6]: The NDC Substances is a temporal higher-order network, where each hyperedge represents an NDC code associated with specific drug, while the nodes represent the constituent substances of the drug. The timestamps, measured in days, indicate the initial market entry of each drug. The hyperedge prediction task is the same NDC Classes dataset.
High School [6, 92]: The High School is temporal higher-order network dataset con- structed from interactions recorded by wearable sensors in a high school setting. The dataset captures high school contact network, where each student/teacher is represented node and each hyperedge shows Face-to-face contact among individuals. Interactions were recorded resolution of 20 seconds, capturing all interactions that occurred within the previous 20 seconds. Node labels in this data are the class of students, and we focus on the node class "PSI" in our classification tasks.
Primary School [6, 93]: The primary school dataset resembles the high school dataset, differing only in terms of the school level from which the data is collected. Node labels in this data are the class of students, and we focus on the node class "Teachers" in our classification tasks.
Congress Bill [6. 94, 95]: Each node in this dataset represents a US Congressperson. Each hyperedge is a legislative bill in both the House of Representatives and the Senate, connecting the sponsors and co-sponsors of each respective bill. The timestamps, measured in days, indicate the date when each bill was introduced.
Email Enron [6]: In this dataset nodes are email addresses at Enron and hyperedges are formed by emails, connecting the sender and recipients of each email. The timestamps have a resolution of milliseconds.
Email Eu [6, 96]: In this dataset, the nodes represent email addresses associated with European research institution. Each hyperedge consists of the sender and all recipients of the email. The timestamps in this dataset measured with resolution of I second.
Question Tags M (Math sx) [6]: This dataset consists of nodes representing tags and hyperedges representing sets of tags applied to questions on meathsstackxchangge.co timestamps in the dataset are recorded at millisecond resolution and have been normalized to start at 0.
The
Question Tags (Ask Ubuntu) [6]: In this dataset, the nodes represent tags, and the hyperedges represent sets of tags applied to questions askubuntu.com. The timestamps in the dataset are recorded with millisecond resolution and have been normalized to start at
"btps://www.cs.coomell.cc
31

---

Table 3: Dataset statisties. HeP: Hyperedge Prediction, NC: Node Classification
Dataset
NDC Class
Hlghh School
Primary School
Congress Bill
Email Ennon
Email Eu
Question Tag- M
Users Threads
NDC Substmnces
Question Tags U
IM
998
5,311
R1
236,760
192,947
271,233
PTimestampa Task
5891
5036
10,788
232.816
822.054
189,017
7,734
271.231
HcPk NC
Users-Threade [6]: In this dataset, the nodes represent users askubuntu.com and hyperedge is formed by users participating in a thread that lasts for a maximum duration of 24 hours. The timestamps in the dataset denote the time of each post, measured in milliseoonds but normalized such that the earliest post begins at O.
The statistics of these datasets can be found in Table 3.
F.2 Baselines
We compare our method to eight previous state-of-the- methods and baselines on the hyperedge prediction task:
CHESHIRE [11]: Chebyshev spectral hyperlink predictor (CHESHIRE), is a hyperedge prediction methods that initializes node embeddings by directly passing the incidence matrix through a one-layer neural network. CHESHIRE treats a hyperedge as a fully connected graph (clique) and uses a Chebyshev spectral GCN to refine the embeddings of the nodes within the hyperedge. The Chebyshev spectral GCN leverages Chebyshev polynomial expansion and spectral graph theory to learn localized spectral filters. These filters enable the extraction of local and composite features from graphs that capture complex geometric structures. The model with code provided is here.
HYPERSAGCN [26]: Self-attention-ber based graph convolutional network for hypergraphs (HyperSAGCN) utilizes a Spectral Aggregated Graph Convolutional Network (SAGCN) to refine the embeddings of nodes within each hyperedge. HyperSAGGN generates initial node embeddings by hypergraph random walks and combines node embeddings by MEAN (.) pooling to compute the embedding of hyperedge. The model with code provided is here.
NHP [87]: Neural Hyperlink Predictor (NHP), is an enhanced version of HyperSAGCN. NHP initializes node embeddings using Nede2Vec on the CE graph and then uses a novel maximum minimum-basee pooling function that enables adaptive weight learning in task-specific manner, incorporating additional prior knowledge about the nodes. The model with code provided is here.
HPL.F [89]: Hyperlink Prediction using Latent Social Features (HPLSF) is probabilistic method. It leverages the homophily property of the networks and introduces a latent feature learning approach, incorporating the use of entropy in computing hyperedge embedding. The model with code provided is here.
Using Resource Allocation (HPRA) is a hyperedge prediction method based on the resource allocation process. HPRA calculates hypergraph resource allocation (HRA) index between two nodes, taking into account direct connections and shared neighbors. The HRA index of a candidate hyperedge is determined by averaging all pairwise HRA indices between the nodes within the hyperedge. The model with code provided is here.
HPRA [88]: Hyperlink Prediction
This model is baseline that we apply CAW [33] on the CE of the hypergraph. CAW is a temporal edge prediction method that uses causal anonymous random walks to capture the dynamic laws of the network in an inductive manner. The model with code provided is here.
CE-CAW:
CE-EvoLVEGCN: This is snapshot- based temporal graph learning method that apply EVoLvEGCN [90], which uses RNNS to estimate the GCN parameters for the future snapshots, the CE of the hypergraph. The model with code provided is here.
CE-GCN: We apply Graph Convolutional Networks [91] to the CE of the hypergraph to obtain node embeddings. Next, we use MIP to predict edges. The implementation provided in the Pytorch Geometric library.
32

---

Table Hyperparameters used the grid search.
Datasets
Sampling Number M
Sampling Time Bias
SErWALK Length m
Hidden dimensions
NDC Class
4.8.
32,
128
(0.5. 20, 200) 10"
3,3,455
64. 128
High School
4. 16, 32, 64. 128
(0.5, 20, 200) 10
2. 3,3,4,5
32, 64. 128
Primary School
4. 8.8, 16, 32, 64, 128
20.5, 20, 200) 10
2,3,4,5
32, 64, 128
Congress Bill
8, 16, 64
(0.5.2.0, 20, 200) x 10
2.3.4.5
32. 64, 128
Email Earon
16, 32,
(0.5, 20, 200) 10"?
2,3,4,5
32, 64, 128
Email
16,
[0.5, 200 x 10-?
2,3,4
32, 64,
Question Tags
20.5, 200) 10"7
2.3.4
Users- I Threads
16, 32, 64
20.5, 200) 10
2.3,4
32, 64, 128
NDC Substances
16. 32, 64
(0.5, 20, 200) 10
2.3.4
32, 64, 128
Question Tags U
8, 16, 32, 64
(0.5, 20, 200)
10
2.3.4
32. 64, 128
For node classification, we use additional five state-of-the-art deep hypergraph learning methods and a CE-based baseline:
HyPERGCN [19]: This is generalization of GCNs to hypergraphs, where it uses hypergraph Laplacian to define convolution.
DEeEESSS and AuSEErRRANSORRNN [25]: These two methods are two variants of the gen- eral message passing framework, Allset, on hypergraphs, which based on the aggregation of messages from nodes to hyperedges and from hyperedges to nodes.
UNIGCNII [28]: Is an advanced variant of UNIGNN, general framework for message passing on hypergraphs.
ED-HNN [124]: Inspired by hypergraph diffusion algorithms, this method uses star expan- sions of hypergraphs with standard message passing neural networks.
CE-GCN: We apply Graph Convolutional Networks [91] to the CE of the hypergraph to ob- tain node embeddings. Next, we use MLP predict the labels of nodes. The implementation is provided in the Pytorch Geometric library. [91]
For all the baselines, we set all sensitive hyperparameters (e.g., learning rate, dropout rate, batch size, etc.) to the values given in the paper that describes the technique. Following [60], for deep learning methods, we tune their hidden dimensions via grid search to consistent with what we did for CALK. We exclude HPLSF [89] and HPRA [88] from inductive hyperedge prediction it does not apply to them.
F.3 Implementation and Training Details
In addition hyperparameters and modules (activation functions) mentioned in the main paper, here, we report the training hyperparameters of CAI-WALK: On all datasets, we use a batch size of 64 and set learning rate -4 We also use an early stopping strategy stop training the validation performance does not increase for more than 5 epochs. We use the maximum training epoch number of 30 and dropout layers with rate 0.1. Other hyperparameters used in the implementation can be found in the README file in the supplement.
Also, for tuning the model's hyperparameters, systematically tune them using grid search. The search domains of each hyperparameter are reported in Table 4. Note that, the last column in Table reports the search domain for hidden dimensions of modules in WALK, including SETMIXER, MLP-MIXER, and MLPs. Also, we tune the last layer pooling strategy with two options: SETMIXER or MEAN(.) whichever leads better performance.
We implemented our method in Python 3.7 with PyTorch and run the experiments on a Linux machine with miiiaa RTX A4000 GPU with 16GB of RAM.
33

---

Table Performance on node classification: Mean ACC (%) + standard deviation. Boldfaced letters shaded blue indicate the best result, while gray shaded boxes indicate results within one standard deviation the best result.
Methods
High School
Primary School
Average Performance
CE-GCN
76.24 2.99
79.03 3.16
77.63 + 3.07
HYPERGCN
83.91 3.05
86.17 3,40
85.04 +: 3.23
Inductive
HYPERSAGCN
84.89 + 3.80
82.13 + 3.69
83.51 # 3.75
ALI.DEEESETS
85.67 4.17
81.43 6.77
83.55 + 5.47
UNIGCNII
88.36 + 3.78
88.27 3.52
88.31 # 3.63
SLT RANSFORMER
91.19 # 2.85
90.00 + 4.35
90.59 + 3.60
ED-HNN
89.23 2.98
90.83 3.02
90.03 # 3.00
CAT-WALK
88.99 4.76
93.28 2.41
91.13 3.58
CE-GCN
78.93 + 3.11
77.46
78,20 # 3.04
HYPERGCN
84.90 + 3.59
85.23
3.06
85.07 + 3.33
Transductive
HYPERSAGCN
84.52 3.18
83.27 + 2.94
83.90 # 3.06
DEEDEESSESS
85.97 4.05
80.20 + 10.18
83.09 + 7.12
UNIGCNII
89.16 1 4.37
90.29 + 4.01
89.73 4.19
SLLSEr TR TRANSFORMER
90.75 * 3.13
89.80 + 2.55
90.27 2.84
ED-HNN
91.41 2.36
9
91.56 2.49
CAT-WALK
90.66 4.96
93.20 2.45
91.93 3.71
Additional Experimental Results
G.1
Results on More Datasets
Due to the space limit, we report the AUC results on only eight datasets in Section 4. Table 6 reports both AUC and average precision (AP) results on all 10 datasets in both inductive and transductive hyperedge prediction tasks.
G.2 Node Classífication
In the main text, focus the hyperedge prediction task. Here we describe how CAr- WALK can be used for node classification tasks.
For each node in the training set, sample max(deg(Ho), 10; hyperedges such Next, for each sampled hyperedge we sample SETWALKS with length m start- ing from each u, ep construct S(u,). Next, we anonymize each hyperedge that appears in at least one SETWALK in - S(u,) by Equation and then use the MLP-MIXER module to encode each Sw U S(u:). To encode each node E we use MEAN(.) pooling over SETWALKS in S(u,). Finally, for node classification task, we use 2-layer perceptron over the node encodings to make the final prediction.
(up, .,...., 1...
Table 5 reports the results of dynamic node classification tasks High School and Primary School datasets. CAr-WALA achieves the best or on-par performance on dynamic node classification tasks. While all baselines are specifically designed for node classification tasks, CAr WALK achieves superior results due to ( its ability to incorporate temporal properties (both from SETWALKS and our time encoding module), which helps to learn underlying dynamic laws of the network, and ② its two-step set-based anonymization process that hides node identities from the model. Accordingly, CAr- WALK can learn underlying patterns needed for the node classification task, instead of using node identities. which might cause memorizing vertices.
G.3 Performance Average Precision
In addition to the AUC, we also compare our model with baselines with respect to Average Precision (AP). Table reports both AUC and AP results on all 10 datasets in inductive and transductive hyperedge prediction tasks. As discussed in Section 4, CAT-WALK due to its ability to capture both temporal and higher-order properties of the hypergraphs, achieves superior performance and outperforms all baselines in both transductive and inductive settings with significant margin.
34

---

Table 6: Performance on hyperedge prediction: AUC and Average Precision (%) = standard deviation. Boldfaced letters shaded blue indicate the best result, while gray shaded boxes indicate results within one standard deviation of the best result. N/A: the method has computational issues.
Datioeets
NDC Closs
High School
Primury School
Congress Bill
Fimiil Finon
Metric
AUC
AP
ALIC
AP
AUC
Stoongyy Indoctive
CE-GUN
$2.51 2.59
54.33 = 2.48
00.54 + 2.06
39.9222:2
52. a 2.75
56.4
2.06
4 3.61
53.85 = 3.92
63.04
:: 1.80
57.20 = 2:27
CE-EwON-GCN
49.76+1.13
55.24 + 3.56
46.12 + 3.83
52.87 3.48
58.01
+ 2.56
58
2.41
54.00 + 1.84
50.27
1.76
57.31
4.119
54.52
3.70
CE CAW
06.25
78.58 = 1.32
83.73 1.42
82.96
1.04
90.31 1.46
82.84
1.71
2
1.28
7081
+ 1.13
12:07
= 1.52
NHP
44.53
68.18 8
66.29
+ 3,80
62.86 = 3.74
70:86
3.42
71.31 3.51
2.19
64.09
49.71
x 6.09
50.01
4.877
HARESAGGN
79.05+2448
77:24
2.05
88.12 3,01
62.72 = 2.93
80.13
1.38
2.95
+ 1.27
8
2.61
73.09
2.60
72.29
3.69
CHESHIRE
70.31
52.54
80.34
1.19
77.26 1.01
79.45
2.55
72.59
C.--War
98899
1.50
0.70
Iodiastiv
Weakly Inductive
CE-GUN
3.29
50.94 = 3.77
50.35
48.54
52.
2.54
52.38
50.83 2.68
50.1 =:
55.35
5.16
4.98
57.85
3.51
63.36 4.01
4.53
5.19 3.56
66 2.10
50.93
2.57
CA-CAW
1..0
80.00: = 1.65
53.77 + 1.41
83:41 = 1.19
$2.98 + 1.06
80.84
1.57
79.51
80.39 1.07
80.58 1.02
77.41 =: 1.28
NHP
75.17=2.002
77:23 = 3:11
07:25 x: 5.19
66.73 4.94
71.92 1.83
72.50 1.89
09:58
4,077
72.48 = 4.83
00.38 = 4.25
55.62 = 4.67
HVwaSAGCN
79.45+22.15
80.52- + 2.25
58.55 1.26
87.
- 1.49
85:08
1:45
85.84
1.60
50.12 2.00
73.48 + 2:77
78. 86 + 0.63
79.14 1:51
CHESHIRE
79.03 1.24
78.98 = 1.17
$8.40 + 1.05
86.53 1.82
$3.55
1.27
79.42
2.:42:20003
79.67 a 0.83
80.00 = 1.38
74.53 = 0.91
75.83 = 1.14
CAR-
9936 1,08
99.33
0 0.89
94.68
2,37
96.54
0.82
96.53
1.39
1.36 96.33
98.38
0.21
V8LAR
0.38
64,11 : 7.9
07.68 = 6.93
IPPRA
70.83 0:01
67.40 = 0.00
94.91 +: 0.00
89.17 = 0.00
89:86
0.06
BR.
0.02
0.03
77.16
0.03
78.62 = 0.00
76.74 = 0.00
Transkative
HPLSF
70.19210.82
77.02 = 1.42
92.14 = 0.29
92.79-0.15 0.15
58.57 1.09
N7.09
1.61
79.31
0.55
75,88
0.43
75.73 = 0:15
75.52 = (108
CF-GUN
66.83+13.7 1.74
65.83 + 3.61
62.90 + 3.00
19.76
5.78
50 14 3.87
55.50
3.46
64.42
3.11
65.19
3.34
$8.06 + 7.80
55.27
3.12
CE EvousGGN
6..5
66.51 = 3.80
65.19 + 2.26
59.23 2.19
63.15 1.32
65.18 1.89
69.30
+ 2.27
64.38 2.66
69.98 5.33
67.76 e: 5.16
CE-CAW
71.73 0 1.42
51.63 0.977
79.37
0.53
86.53 1184
87.00
1:15
76,99
1,02
77,05 = 1.14
79.57
a 0.14
78.57 : 1.15
NHP
8..39.42.81 2.81
80.72 + 2.04
76.85 + 3.08
75.37
= 3.12
80.04
3.42
80.24
3.49
80.27
2,53
77.82 = 1.91
63.17 + 3.79
K7 + 3.19
HETESSAGCN
90,76
80.50 2.75
94.98 1,30
89.73
1.21
90.77
2.05
88.64
2.09
81.12
83.39
80.54 1.66
CHESHIRE
82.34
94.20
1:23
91.62
39
CAe-WAL
95.90
97.91
Duiseets
Email Eu
Question Taps
Usen Threads
NDC Substances
Question Tags
Matric
AUC
AUC
AP
AUC
Strungy Inductive
CUN
22.7622.41
50.37 =
1.88
54.35
1.94
57.91 1.56
2.91
51.97 =
=
CE-PAONEGON
44.16 1.27
49.15
1:23
64.08 2.75
60.64
2.78
52.00
2.52
52.60
2.15
58.17
2.24
57.35
54.57
2.25
57.16 2.55
CA-CAW
72.29
73.45 = 0.68
70.14 + 1.89
70.26
= 1.77
73.12 1.06
72.64
1.18
75.87
0.77
73.19=036
74.21 + 2.04
76.53 = 2.06
NHP
25.3
64.24 1.61
08.25 5.34
004113.41
7183 2.64
71.09
2.83
70.45
3.64
2
72.52
2:99
2
HVwASAGCN
78.01+11.24
80.04
1.87
73.66 + 1.95
1.35 73.08
73.94 2:57
72.97
2:45
75.85
2.21
73.34
78.88
+ 2.69
77.53
2.78
CHESSHRE
2.79
70.10
=: 3.05
N/A
N/A
76.99 + 2.82
74.00
2:78
76.00
2.19
74,91
2.77
75.04 3.339
75.46
: 2.90
CAR-WAR
2,78
91.75
2
X800S 8 3.38
88.46
3,99
89.84 : 6,002
91.58
4.37
93.29
1.55
94.26
1.21
97.59
2.21
97.78
2.07
Inilactiv
Weakly Inductive
CE-GON
49.60 3.96
55.01 + 3.25
55.13 2.76
$1.48 = 2.66
57.06 3.16
58:37
2:86
60.92 2.81
55,93 2.00
56.85 + 2.73
57.19 2.52
CE-BNOOSGGN
2..54:2..58
61.79 1.63
59.61
1.12
55.81 2.54
50.63
1.21
2.32
CE-CAW
1.194
77.29
77.67
1.94
0.62
0.63
77.17
1.39
4.319
70.46
3.52
65
3.94
76.44 1.90
75.23 3.96
73.37
3.51
70.62 3:71
75.15
79.64
HIwASSGGEN
27.26+2..0
74.05
2.12
78.15
76.19
1.53 N1A
75.38
1,43
70.35
50.82
2.18
76.67
74.22
70.57
1.02
CUESTTRE
77.91
75.01
= 0.98
N/A
$1.27 0.85
1.41 97.55
82.96
1.31 95.65 1.82
50.68
80.78 = 1.13
77.60 + 1.57
79.68 = 1.79
CAR-WAK
2:49
92.22 : 2
90.25 x: 2
90.56 = 2,62
97.15 s 1.81
1.49
96.18
1.52
98.11 : 1.31
98.25 = 1.15
HPRA
0:000
71.08
$3.18 0.00
80 12:11:000 0.00
70.49
0.02
72.83
0.00
77.94
0.01
75.78 0.01
$1.05
81.71 0.00
Transdostive
CE-GUN
HPLSF
0..37=0.31
65:93 2.79
77.95 = 2.52
53.45 0,91
55.18 5.12
N2.29 1.06
55.84 4:53
744.88
62.78
2.69
1.11
73.81
59.71
1.45
2:25
$2.12
63.08
2.19
0.71
86.51
65.37
0.62
2.48
66.79
50.89
2.88
60.51
75.62 = 1.38
CE-EwoueGCN
64.36+4..17 4.17
66.98 = 3.72
72.56 + 1.72
69.38- = 1.51
65.55
2.26
67.86
2.61
70.09
+ 3.42
66.37
71.31
2.99
70.36 2.72
CE-CAW
78.19 1.10
77.95 = 0.98
$1.73 2.45
N3:27 = 2:34
50.86
a 0.65
NI.57 1.08
84.72
1.65
84.93 1.26
50.37 = 1.77
85.14 0.97
NHP
78.90
76.95 + 5.08
79.14 + 3.36
78.70 3.15
82.33
1.02
81.44 1:53
$1.38
1.42
82.17
1.38
78.99 4.16
80.06
4.33
IEVERSAGCN
79.61 2.35
75.99 =: 2.23
$4.07 + 2.50
84.22
2.43
79.62
2.04
79.38
= 2.55
85.07
+
=
25.18
80.99 = 3.04
CHESHIRE
56.38 1.25
S7.39
$: 1.07
N/A
$2.75
1.99
81.96 1.75
56.30
1.57
83.18 = 1.92
87.83
2.15
88.62 s 1.76
CABWWAK
96.74 1.28
97.08
1.20
91.63 1.41
92.28 1.36
93.51
1.27
94.98 0.98
90.64
0.44
91.96
0:41
96.59
06.99:44.33 4.39
97.06
3.72
G.4 More Results on RNN v.s. MLP-MIXER in Walk Encoding
Most existing methods on (temporal) random walk encoding see walk as a sequence of vertices and uses sequence encoders like RNNS or TRANSFoRMERs to encode each walk. The main drawback of these methods is that they fail directly process temporal walks with irregular gaps between timestamps. That is, sequential encoders can be seen as discrete approximations of dynamic systems; however, this discretization often fails if we have irregularly observed data [125].nper This is the main motivation of recent studies to develop methods on continuous-time temporal networks [34, 126]. Most of these methods are too complicated and sometimes fail generalize [127]. In CAF- WALK, we suggest a simple architecture to encode temporal walks by time-encoding module along with a MIXER module (see Section 3.4 for the details). In this part, we evaluate the power of our MIXER module and compare its performance when we replace it with RNNS [82]. Figure 7 reports the results on all datasets. We observe that using MIPEMIXER with the time-encoding module CAI-WALK can always outperform CAT-WALK when we replace MLP-MIxEE with RNN, and mostly this improvement is more on datasets with high variance in their timestamps. We relate this superiority to the importance of using continuous- sitiiuuuu--imeeeee encoding instead of sequential encoders.
35

---

MLP-MIXFE
100
80
AUC
60
40
NDC Class
Congress Bill
Email Enron
Emuii
Question Taga
NDC Substences
Question Tags
High School
Primury Sehovll
Usem in Threads
Figure 7: The importance using MLP-MIXER in CAr-WALK, Using RNN instead of MLP-MIXER can damage the performance in all datasets. RNNS are sequential encoders and are not able to encode continuous time in the data.
H Broader Impacts
Temporal hypergraph learning methods, such as CAr-WALK, benefit wide array of real-world applications, including but not limited to social network analysis, recommender systems, brain network analysis, drug discovery, stock price prediction, and anomaly detection (e.g. bot detection in social media or abnormal human brain activity). However, there might be some potentially negative impacts, which we list as: ! Learning underlying biased patterns in the training data, which may result in stereotyped predictions. Since CAr- WALK learns underlying dynamic laws in the training data, given biased training data, the predictions of CAr- WALK can biased. @ Also, powerful dynamic hypergraph models be used for manipulation in the abovementioned applications (e.g., stock price manipulation). Accordingly, to prevent the potential risks in sensitive tasks, e.g., decision-making from graph-structured data in health care, interpretability and explainability of machine learning models on hypergraphs is a critical area for future work.
Furthermore, this work does not perform research on human subjects part of the study and all used datasets are anonymized and publicly available.
36


Reviews:
[{"review_id": "uP5wFexDWr", "reviewer": "Reviewer_BLYu", "summary": "The paper introduces a novel way of defining random walks on hypergraph. The random walks consist in a sequence of hyperedges, where the transition probabilities take into account both the temporal closeness of the hyperedges and the importance of the nodes through which the hyperedges are connected. \nThe resulting random walk is more expressive (in the sense that transition probabilities capture more features of the hypergraph) than the Clique expansion and star expansion random graphs. These random walks are used to build an encoding of the nodes using a permutation invariant procedure. Finally these encodings are fed into a 2 layer MLP that outputs hyperedge predictions. The model compares favorably to other approaches used in the literature.", "questions": "Can you comment on the number of hyperparameters (such as $\\alpha,M,m$) used in CAT-WALK compared to those needed in other algorithms? Is there more hyperparameter tuning to do when using CAT-WALK?\n", "limitations": "The authors have addressed the limitations of their algorithm.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written. Although I’m not completely familiar with the relevant literature, the method seems novel and aims to solve a relevant problem in hypergraph link prediction. The theoretical reasons for introducing a new type of random walk on hypergraphs are compelling, and the method indeed manages to solve the expressivity problems associated to earlier random walk approaches. The experimental results are well cured and show a significant improvement in performance over previous algorithms. ", "weaknesses": "The theorems 1 and 2 are stated in an informal and imprecise way. While I understand the need not to flood the main text with mathematical details, one would have expected to find a rigorous formulation at least in the appendix. In partiuclar the definition of «expressiveness», «missing information» are not made explicit. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your review! We really appreciate it! Please see below for our response to your comments:\n\n----\n> *The theorems 1 and 2 are stated in an informal and imprecise way. While I understand the need not to flood the main text with mathematical details, one would have expected to find a rigorous formulation at least in the appendix. In partiuclar the definition of «expressiveness», «missing information» are not made explicit.*\n----\n\n**Response:**  We followed the previous studies and use the commonly used graph isomorphism test as the measure of the expressive power of methods. That is, we say model $A$ is more expressive than model $B$, if \n1.  for any pair of graphs like $(G_1, G_2)$ that $G_1 \\neq G_2$, if model $B$ can distinguish $G_1$ and $G_2$ then model $A$ can also distinguish them,\n2.  there is a pair of graphs like $(G’_1, G’_2)$ such that $A$ can distinguish them but $B$ cannot. \n\nWith respect to “missing information,” we mean missing higher-order information provided by the hypergraph representation. That is, we say an approach (or a module) misses higher-order information if its output is the same when the input is either hypergraph $G$ or its projected graph (clique expansion). \n\nThank you, yes, sure, we will explicitly and formally define both “expressiveness” and “missing information” in the paper as well as add additional explanations in the appendix. \n\n\n\n\n----\n> *Can you comment on the number of hyperparameters (such as) used in CAT-WALK compared to those needed in other algorithms? Is there more hyperparameter tuning to do when using CAT-WALK?*\n----\n\n\n\n**Response:** Thank you for asking about this! We will add more discussions about the number of hyperparameters used in CAT-Walk and other algorithms. In deep learning methods, in addition to the hidden dimensions, which are common hyperparameters in all algorithms, CAT-Walk uses **three** hyperparameters ($\\alpha$, $m$, and $M$),  HYPERSAGCN uses **five** hyperparameters (window size, walk length, the number of walks per vertex, and $p$ and $q$ to control the tendencies that encourage outward exploration in walk sampling), and NHP uses **four** hyperparameters ($\\lambda$ in the scoring function, number of GCN layers, and $p$ and $q$ to control the tendencies that encourage outward exploration in Node2Vec walk sampling). The only competitor algorithm with less number of hyperparameters is CHESHIRE with **two** hyperparameters ($K$: Chebyshev filter size, and dropout probability). Although CHESHIRE has less number of hyperparameters compared to CAT-Walk, the search space for the Chebyshev filter size is usually much larger than the search space for $m$ and $M$. Accordingly, depending on the task and dataset, either CAT-Walk or CHESHIRE might need less amount of hyperparameter tuning. We want to emphasize that CAT-Walk and CHESHIRE require a comparable amount of hyperparameter tuning while CAT-Walk achieves better AUC and Precision performance in the hyperedge prediction task.  \n\n\n\nThank you so much once again for your time and review!\n\n\n"}, {"review_id": "YNDOemBCBD", "reviewer": "Reviewer_nNT7", "summary": "The paper proposes a walk-based learning method for temporal hyperedge prediction. Several conceptional contributions are made to walks in (temporal) hypergraphs which are compared to existing techniques such as clique or star expansion to represent hypergraphs by simple (weighted) graphs. A corresponding neural architecture is proposed and shown to outperform existing methods in an extensive experimental comparison.", "questions": "* Can you make Theorem 2 more precise and address the above-mentioned concerns?\n* For some datasets, it is not clear to me how hyperedges were derived. For example, face-to-face contacts in the high school dataset naturally give rise to simple graphs. Can you explain this?\n* The considered task of \"temporal hyperedge prediction\" is very specific. Which competitors were designed for this task?", "limitations": "A detailed discussion of the prediction tasks the approach is (most) suitable for would strengthen the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The newly introduced concepts and ideas on walks in hypergraphs are nicely motivated by the shortcomings of existing methods. The authors provide illustrative examples, which are discussed in sufficient detail.\n* The paper is well-written and comprehensive. The appendix provides interesting additional results and answers most of my questions.\n* The experimental comparison is extensive and shows good results for the proposed method.", "weaknesses": "* While the conceptional contributions are nicely motivated, this is not the case to the same extent for the design choices of the neural architecture. Some arguments remain vague or are not clear to me. Theorem 2 makes a statement on set functions (or pooling) and suggests that applying a function $f$ to the individual elements (or subsets of fixed size $k$) and computing their sum \"can cause missing information.\" The statement is not precise, and the meaning of \"$f$ is some function\" is unclear. The proof in the appendix also is not helpful and essentially states that it is clear that the sum is less informative than the set itself. In light of the following papers [[Deep Sets](https://arxiv.org/abs/1703.06114), [Some Might Say All You Need Is Sum](https://arxiv.org/pdf/2302.11603.pdf)] this is not clear. \n* The approach shows great results for the task of \"temporal hyperedge prediction\", which is very specific. For the standard task of node classification, it still works well but the improvement is less significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your review! We really appreciate it! Please see below for our response to your comments:\n\n----\n>*While the conceptional contributions are nicely motivated, this is not the case to the same extent for the design choices ...*\n----\n\n**Response:** Thank you for mentioning it. Yes, sure, we will make the statement in Theorem 2 more precise in the paper. The term “$f$ is some function” is used to say function $f$ is an arbitrary function that takes sets as input. Also, the term “missing information” refers to missing the higher-order information provided by the hypergraph representation. We say an approach (or a module) misses higher-order information if its output is the same when the input is either hypergraph $G$ or its projected graph (e.g., clique expansion). We will change the writing and mathematically formulate them to make both clearer. \n\nThe main intuition of Theorem 2 is that a pooling function needs to capture higher-order\ndependencies of its input’s elements and if it can be decomposed into a summation of functions that capture only lower-order dependencies, then it misses higher-order information encoded in the data. In the proof of Theorem 2, we construct a hypergraph $G$ and show that the summarization of $G$’s projected graph, provided by this pooling function, is more informative than the provided summarization of $G$ itself by this pooling function. The term “sum is less informative than the set itself” means: Given a set $S = \\\\{a_1, …, a_k\\\\}$, we can construct any arbitrary algebraic combination of $a_1, …, a_k$, while $a_1 + a_2 + … + a_k$ is only one of them. Accordingly, given $q = a_1 + a_2 + … + a_k$, we do not have any information about the exact value of the higher-order combinations of $a_i$s, e.g., $p = a_1 a_2 + a_2 a_3 + … + a_{k - 1} a_k$. We can modify the writing of this proof to make this point clearer.\n\nPlease note that results presented in Deep Sets correspond to the models that use “suitable transformations” on top of the summation. Our Theorem 2 only holds for pooling strategies that can be written in the form of Eq. 4 (e.g., SUM Pooling). Although using a simple linear layer (suitable transformations) on top of the summation might not cause missing higher-order information, it misses the cross-node dependencies of features. Our presented SetMixer uses the Softmax$(.)$ function to bind token-wise information in a non-parametric manner. We ran new ablation studies to show the importance of SetMixer and compared it with the sum-based universal approximator for sets (please see the attached file). These results show the significance of the architecture of SetMixer.\n\n----\n> *The approach shows great results for the task of \"temporal hyperedge prediction\", which is very specific ...*\n----\n\n**Response:** As we discussed in the paper, coming up with one architecture suitable for different tasks is highly challenging and usually has not been done in the existing studies. Even in the existing studies in simple graphs, the state-of-the-art methods in each task differ significantly [1]. In hypergraph learning methods, for example, PhenomNN [2], AllSet, ED-HNN [3], and UniGNN are specifically designed for node classification tasks, and CHESHIRE, NHP, and HPRA are specifically designed for hyperedge prediction tasks.  \n\nOne of the significances of the CAT-Walk is that it performs well in both hyperedge prediction tasks (with significant improvement) and node classification tasks (with improvement but less significant).\n\n----\n> *Can you make Theorem 2 more precise and address the above-mentioned concerns?*\n----\n\n**Response:** Yes, sure, we will make the statement in Theorem 2 more precise and clearer in the paper. We will change the writing and mathematically formulate the “missing information” term to make the theorem clearer. Please also see our response to your first comment.  \n\n----\n> *For some datasets, it is not clear to me how hyperedges were derived. For example, face-to-face contacts in the high school ... Can you explain this?*\n----\n\n**Response:** The face-to-face contacts datasets (e.g., high school dataset) have recorded interactions at a resolution of 20 seconds. That is, a group of people are connected by a hyperedge if their minimum distance to each other during the past 20 seconds was less than a threshold. We also want to kindly bring to your consideration that all of the used datasets in this paper are previously released benchmark hypergraph datasets by other studies. \n\nWe will add more explanations about each of the datasets and how they have been derived to make everything clearer.  \n\n----\n>  *Which competitors were designed for this task?*\n----\n\n**Response:** All of the hypergraph learning competitors are designed for hyperedge prediction tasks. The only exception is HyperSAGCN, which can be used for both hyperedge prediction and node classification tasks. However, CAT-Walk significantly outperforms HyperSAGCN in both hyperedge prediction and node classification (please see the attached file) tasks.\n\n----\n> *A detailed discussion of the prediction tasks ...*\n----\n\n**Response:** Thank you for suggesting that. We believe that CAT-Walk is suitable for both node and hyperedge prediction tasks. Our datasets' domains vary from social, interaction, chemical, and communication networks. Due to the inductive nature of CAT-Walk, it can be applied to any network that changes based on specific dynamic laws and captures and learns these laws by sampling SetWalks. We would be happy to add a discussion in more detail about what type of domains are most suitable for CAT-Walk due to its design and architecture, as you mentioned.\n\nThank you so much once again for your time and review!\n\n----\n[1] Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020.\n\n[2] From Hypergraph Energy Functions to Hypergraph Neural Networks. ICML 2023.\n\n[3] Equivariant Hypergraph Diffusion Neural Operators. ICLR 2023."}, {"review_id": "Jepjc21KXm", "reviewer": "Reviewer_H3jP", "summary": "The paper proposes an inductive approach to temporal hypergraph learning. The method includes two main components: a hypergraph random walk called SET-WALK and a pooling strategy termed SETMIXER, for extracting higher-order causal patterns. In addition, the authors design a simple neural network for hyperedge encoding.", "questions": "Is any hypergraph random walk can replace the set-walk in the CAT-Walk network?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-organized.\n- The authors provide a new direction for the random walk on hypergraph, though the random walk seems more complicated than the CE-based random walk.\n- The paper gives many intuitions and theoretical analyses to demonstrate the superior performance of set-walk compared to existing walks.\n- The set-walk can be regarded as a generalization of node-walk on hypergraph, which seems interesting and useful.\n- The experiments in Table 1 suggest the proposed methods significantly outperform the baselines.", "weaknesses": "1. The method contains several components: including Time Encoding, SetMixer, Setwalk, and MLP-Mixer. The experiments only provide three datasets in Table 2 to evaluate each component. It would be more convincing if each component could be evaluated in all datasets and all settings in Table 1.\n\n2. Some definitions are not very easy to understand. It would be better to add some schematic for illustrating those concepts,  e.g. Def. 1 and Def. 2.\n\n3. The experiments on node classification are inadequate. There are many important baselines and benchmarks concerning node classification, such as [1][2].\n\n[1] Equivariant Hypergraph Diffusion Neural Operators\n\n[2] Hypergraph Convolutional Networks via Equivalency Between Hypergraphs and Undirected Graphs", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your review! We really appreciate it! Please see below for our response to your comments:\n\n----\n> *The method contains several components ... It would be more convincing if each component could be evaluated in all datasets and all settings in Table 1.*\n\n----\n\n**Response:** Thank you for mentioning it. Running the ablation study on all datasets and in all settings requires #ablation-cases $\\times$ #datasets $\\times$ #settings $\\times$ #run = $7 \\times 10 \\times 3 \\times 10 = 2100$ experiments. Accordingly, in our ablation study, we followed existing studies (e.g., [1, 2, 3, 4]), and reported the results on a subset of datasets. However, we would be happy to evaluate each component of CAT-Walk on all datasets. We have started running asked experiments, and in the attached file we report the results on five datasets. The new results are compatible with previous findings and show the significance of each component in the CAT-Walk design. We can definitely and would be happy to add the results for other datasets to the final version of the paper. We also want to bring to your consideration that the results of the effect of MLP-Mixer (replacing MLP-Mixer with RNN) on all datasets have been reported in Figure 7 (page 35 in the appendix). \n\n\n\n----\n> *Some definitions are not very easy to understand. It would be better to add some schematic for illustrating those concepts, e.g. Def. 1 and Def. 2.*\n----\n\n**Response:** Thank you for your suggestion. Definition 1 defines temporal hypergraphs, and Definition 2 defines SetWalks. Figures 1, 2, and 3 include examples of temporal hypergraph (Def. 1) and SetWalks (Def. 2), but due to the space constraint, we didn’t directly illustrate these two definitions by referring to these figures. We will definitely add some examples to illustrate these definitions and make them clearer. \n\n\n----\n> *The experiments on node classification are inadequate. There are many important baselines and benchmarks concerning node classification, such as [1][2].*\n----\n\n**Response:** One of the significances of the CAT-Walk design is that it performs well in both hyperedge prediction and node classification tasks.  However,  one limitation to performing extensive experiments on node classification (as we have done for hyperedge prediction) is the lack of temporal hypergraph datasets with ground truth node labels. Both of the papers you mentioned have used static hypergraph datasets. However, in the attached file, we compare our CAT-Walk with the ED-HNN paper you mentioned (unfortunately, the code for the other paper you mentioned is not publicly available). We also want to bring to your consideration that in our node classification experiments, we have **seven** state-of-the-art node classification methods, even including very recent methods, which is a comparable number of baselines with the studies that only have focused on node classification tasks. Overall, in our experiments, we have **10 + 2** datasets and **8 + 7** ( **13** unique) baselines. \n\nWe want to kindly bring to your consideration that coming up with one architecture suitable for different tasks is highly challenging and usually has not been done in the existing studies. Even in the existing studies in simple graphs, the state-of-the-art methods in each task differ significantly [5]. In hypergraph learning methods, for example, PhenomNN [6], AllSet, ED-HNN [7], and UniGNN are specifically designed for node classification tasks, and CHESHIRE, NHP, and HPRA are specifically designed for hyperedge prediction tasks. Accordingly, their experiments are also limited to a single task (either node classification or hyperedge prediction). CAT-Walk not only is suitable for both hyperedge prediction and node classification tasks, but it also outperforms baselines in both inductive and transductive settings. \n\n\n----\n> *Is any hypergraph random walk can replace the set-walk in the CAT-Walk network?*\n----\n\n**Response:** Yes, any hypergraph random walk can replace the SetWalk and can be used in the CAT-Walk framework. In our ablation study, we replace SetWalk with the state-of-the-art hypergraph random walk and show the significance of using SetWalk. \n\n\n\nThank you so much once again for your time and review!\n\n\n\n\n\n----\n\n[1] Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs. ICML 2022.\n\n[2] Inductive Representation Learning on Temporal Graphs. ICLR 2020. \n\n[3] NHP: Neural Hypergraph Link Prediction. CIKM 2020.\n\n[4] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks. ICLR 2021.\n\n[5] Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020.\n\n[6] From Hypergraph Energy Functions to Hypergraph Neural Networks. ICML 2023.\n\n[7] Equivariant Hypergraph Diffusion Neural Operators. ICLR 2023."}, {"review_id": "W6QUCTxfRr", "reviewer": "Reviewer_eydA", "summary": "The paper proposes an hyperedge learning method suitable for modelling temporal hyperedges. The approach consists of a novel hyperedge-centric random walk, a permutation-invariant pooling method and a technique for anonymizing both the identity of the nodes and  the identity of the hyperedges. \n\nDifferent than standard random walks for hypergraphs that samples sequences of nodes, the SetWalk generates sequences of hyperedges, making it strictly more powerful than clique-expantion based methods. The pooling method used to encode the hyperedges represents a variation of MLP-mixer and the authors proved empirically that it is more powerful than other pooling approaches such as mean pooling and RNNs. Finally, the anonymization startegy incorporates positional information from hyperedges, while still allowing the model to be applied in the inductive setup. The experimental setup validates the benefits of applying the CAT-Walk for hyperedge prediction. Additionally, they also validate the importance of each component in a series of ablation studies.", "questions": "Please refer to the questions mentioned in the Weaknesses section.", "limitations": "A couple of limitations are mentioned in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The proposed method contains a series of components that could be useful beyond the hyperedge prediction task presented in this paper. The idea of producing hyperedge-centric random walk is interesting and it is worth being explored in other contexts where random walk is required. Moreover the set-based pooling is a general technique that could be useful in other architectures where a set-level aggregator is needed.\n\n* The paper is very nicely presented. Even if the proposed architecture contains a  complex pipeline, containing several components, each one with its own notations, the paper is easy to follow, with a nice structure and good visualisations.\n\n* The paper introduces completely novel concepts and results presented in the experimental part clearly show the advantages of incorporating them in the method.", "weaknesses": "* SetWalk constitutes an hypergraph random walk technique  that, instead of producing sequences of nodes, it produces sequences of hyperedges. Given that, I am wondering what is the connection between the SetWalk method and a classical graph-based random walk applied on the line expansion of the hypergraph?\n\n* The paper mentions that “[the proposed method] removes self-attention and RNNs from the walk encoding procedure, avoiding their limitations.” A detailed discussion about what are these limitations and how the proposed method overcomes them is required.\n\n* The universal approximation results from [1] show that, by applying another function on top of the summation presented in Eq.4  $g(\\sum_i f(x_i))$ leads to a universal approximator for multisets. How does SetMixer pooling compare to that in terms of expressivity? What are the advantages of using SetMixer instead of this classical approach?\n\n* The paper mentions several times that a common drawbacks brought by various pooling methods is that they are losing important information. While being more expressive than some of them, it is not clear what are the limitations of SetMixer (if any). Is SetMixer universal approximator? If not, what are some examples of sets that SetMixer is not able to distinguish due to losing information.\n\n* In Eq.5, shouldn’t the multiplication with W_s^2 be a right side multiplication. The way it is defined at this moment is not a permutation invariant function (which would contradict the results in Theorem 3).\n\n* Theorem 4  states that the anonymization technique introduced in the paper is more expressive than any existing anonymization  strategies based on CE, mentioning that it can distinguish at least a pair of graphs that is not distinguished by those. However, being “more expressive than” should also imply that it does not lose any expressivity compared to CE.  However, the statement from Theorem 4 is unclear in this respect, since it is not obvious if the proposed method is able to distinguish between every pair of graphs that the previous methods are able to distinguish. This aspect should be more clearly mention in thetext.\n\n* A couple of additional ablation studies should be included in order to clearly emphasize the advantages brought by CAT-Walk. A few suggestions include:\n\n1. replacing the SetMIXER not only with RNNs but also self-attention/transformer as a more recent and powerful baseline.\n2. Replacing the pooling with the sum-based universal approximator for sets  g(sum_i f(x_i)) where f and g are 2-layers MLPs seems a fairer comparison than the basic MEAN-pooling operator.\n\n* In the ablation studies paragraph, which type of the hypergraph random walk is used for comparison? A citation or description of the method would be useful,\n\n[1] How Powerful are Graph Neural Networks? Xu et al", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your review! We really appreciate it! Please see below for our response to your comments:\n\n>*what is the connection between the SetWalk method and a classical graph-based random walk applied on the line expansion?*\n----\n**Response:** Thank you for mentioning it. We have discussed this in Appendix C. There are two main challenges for random walks on hypergraphs: \n1. Random walks are a sequence of pair-wise interconnected vertices, even though edges in a hypergraph connect sets of vertices. \n2. A sampling probability of a walk on a hypergraph must be different from its sampling probability on the CE. \n\nMost existing works ignore (1) and focus on (2) to distinguish the walks on simple graphs and hypergraphs. Either (1) or (2) alone is not sufficient to take advantage of higher-order interactions. SetWalk aims to address both. Applying simple walks on line expansion graph ignores (2). As you mentioned, applying classical random walks on the line expansion can be seen as similar to SetWalks, but there are some important differences:\n- SetWalks are temporal walks that backtrack over time. Applying classical graph-based temporal walks on line expansion only captures the dynamics of nodes (edges in the line expansion graph), missing the temporal properties of the hyperedges in the main hypergraph.\n- Line expansion is equivalent to the CE of edge-to-vertex dual hypergraph. Applying a simple walk on the line expansion misses the higher-order dependencies of hyperedges in the hypergraph.\n- One might suggest applying a simple hypergraph walk on the edge-to-vertex dual hypergraph. However, it is always equivalent to clique expansion [1]. The sampling procedure of SetWalks (Eq. 1) guarantees hyperedge-dependent walk sampling on the dual hypergraph, which is more informative than simple (hypergraph) walks on the CE [1]. (We discuss this in Appendix D)\n\nWe will add more explanations about it to make it clearer. \n\n----\n> *... A detailed discussion about what are these limitations and how the proposed method overcomes them is required.*\n----\n**Response:** Thank you for mentioning it. We have discussed this in Appendix G.5. The main drawback of these methods is that they fail to directly process temporal walks with irregular gaps between timestamps. Sequential encoders can be seen as discrete approximations of dynamic systems; however, this discretization often fails if we have irregularly observed data [2]. This motivates recent studies on continuous-time temporal graph neural networks. CAT-Walk by removing sequential encoders in the walk encoding process allows continuous-time temporal graph learning. \n\nWe will add more explanations about the importance of removing sequential encoders to make this point clearer.\n\n----\n> *How does SetMixer pooling compare to that in terms of expressivity? What are the advantages ...?*\n----\n**Response:** To have a universal approximator for sets, we need \n1. permutation-invariant property, and\n2. showing the method can approximate any function. \n\nTheorem 3 shows the permutation-invariant property of SetMixer. Since SetMixer is an all-MLP architecture and MLPs are universal approximators, it is simple to show that SetMixer is also universal approximator. \nThank you, we will add some explanations about the expressivity of SetMixer and mathematically prove it is a universal approximator.\n\nAlso, one of the main advantages of SetMixer compared to classical approaches is its ability to capture cross-node dependencies of features. SetMixer uses the Softmax(.) function to bind token-wise information while a simple MLP or classical approach misses these token-wise dependencies. We also ran new ablation studies to show the importance of SetMixer (please see the attached file).\n\n----\n> *... what are the limitations of SetMixer. Is SetMixer universal approximator? ...*\n----\n\n**Response:** As we discussed above, SetMixer is a universal approximator. However, same as any other method, it might suffer from some limitations. Sometimes the importance of each element of the set is different. While SetMixer treats all the elements the same, future work can be to extend SetMixer to the case that the importance of all elements are not the same, possibly by an attention mechanism. We can add some explanations about these limitations.\n\n----\n> *In Eq.5, shouldn’t the multiplication with W_s^2 be a right side multiplication.*\n----\n\n**Response:** Thank you for mentioning it. Yes, it was a typo and it should be a right-side multiplication. Unfortunately, we found this typo after the main submission deadline and we could only fix it in the appendix. We will fix this typo in the final version.\n\n----\n> *Theorem 4 states that the anonymization technique introduced ...*\n----\n\n**Response:** Yes, sure, we will change the statement of Theorem 4 to make it clearer. In the proof, we also show our anonymization strategy is able to distinguish between every pair of graphs that the previous methods are able to distinguish.  The main idea for this is to decompose SetWalks into simple graph-based random walks and show that SetWalk includes the information provided by these walks. We will change the writing of Theorem 4 and its proof to make it clearer.\n\n----\n> *A couple of additional ablation studies should be included ...*\n----\n**Response:** Thank you for suggesting that. We have run the asked ablation studies and reported them in the attached file. \n\n----\n>*... which type of hypergraph random walk is used?*\n----\n**Response:** Yes, sure, we will add more explanations about the used random walk in the ablation study. In this experiment, we replace SetWalks with the most powerful existing hypergraph random walk, i.e., edge-dependent hypergraph random walk [1].\n\nThank you so much once again for your time and review!\n\n[1] Random Walks on Hypergraphs with Edge-Dependent Vertex Weights. ICML 2019.\n\n[2] Neural controlled differential equations for irregular time series. NeurIPS 2020.\n"}]

Author rebuttal:
We want to thank all the reviewers for their time and comments. We are also grateful for all the constructive feedback for improving the paper. 

We have attached a file with two tables. The first table reports the results of previous ablation studies and the two newly asked ablation studies (highlighted in blue) on five datasets. The second table reports the results of a new baseline for node classification tasks. The new results are compatible with the previous results, i.e., 

1. Ablation study results show the significance of each CAT-Walk component. While both the classical universal approximator and SetWalk are universal approximators, SetWalk architecture allows binding token-wise information, which captures the cross-feature dependencies of nodes. Also, replacing MLP-Mixer with Transformers damages the performance as sequential encoders consider time as a discrete variable while CAT-Walk uses a Time Encoding module along with MLP-Mixer to encode temporal walks, considering time as a continuous variable. 

2. Not only CAT-Walk shows outstanding performance in hyperedge prediction tasks, but Table 2 also shows that CAT-Walk achieves competitive (the best or on-par) performance on node classification tasks. 


Meta-review: This paper was unanimously appreciated by the reviewers and is a nice contribution to the literature. The discussion was valuable and identified many points that were not clear from the manuscript. While these points were clarified in the discussion, the authors need to revise the paper to carry those clarifications into the manuscript.
Decision: Accept (poster)