A Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks

We introduce the \emph{temporal graphlet kernel} for classifying dissemination processes in labeled temporal graphs. Such dissemination processes can be spreading (fake) news, infectious diseases, or computer viruses in dynamic networks. The networks are modeled as labeled temporal graphs, in which the edges exist at specific points in time, and node labels change over time. The classification problem asks to discriminate dissemination processes of different origins or parameters, e.g., infectious diseases with different infection probabilities. Our new kernel represents labeled temporal graphs in the feature space of temporal graphlets, i.e., small subgraphs distinguished by their structure, time-dependent node labels, and chronological order of edges. We introduce variants of our kernel based on classes of graphlets that are efficiently countable. For the case of temporal wedges, we propose a highly efficient approximative kernel with low error in expectation. We show that our kernels are faster to compute and provide better accuracy than state-of-the-art methods.


Introduction
Dissemination processes such as spreading information or disease can be challenging to analyze and track. Recent works [21,22,28] discuss the problem of classifying dissemination processes in social and human contact networks, e.g., discriminating the spread of real news from fake news, different infectious diseases, or malicious from benign network communications. Identifying such spreading processes correctly in real-world and online social networks can have immense social impacts. For example, detecting a new viral pathogen spreading in communities can help to react early and prevent severe outbreaks [4,19]. Similarly, identifying and limiting the spread of fake news on social networks like Facebook or WeChat can help to reduce resulting social unrest [16,24,28]. These kinds of spreading processes can naturally be modeled using labeled temporal graphs. A labeled temporal graph consists of a fixed set of nodes, a label function that assigns a discrete label to each node at each point in time, and a set of timestamped edges. Figure 1 shows an example of a temporal graph and a dissemination process over time (highlighted in red). Because temporal graphs are suitable models for a wide range of real-life scenarios with dynamic relations [6], research in temporal graphs has recently gained increasing attention [2,15,21,24]. Methods for analyzing and classifying static graphs, on the other hand, have been studied for decades and are an established area of research-dominating learning methods are based on graph kernels [11] and graph neural networks [30]. A wellknown and popular static graph kernel is the graphlet kernel proposed in [23]. We introduce a temporal version, named temporal graphlet kernel, to account for the specific properties of temporal graphs. Our kernel is inspired by recent works on temporal motifs [14,15,16,24,26]. Temporal motifs are generalizations of small subgraph patterns, i.e., graphlets, that incorporate temporal properties like the chronological ordering of the edges. In contrast to previous works [21,22], our temporal graphlet kernel directly operates on the labeled temporal graphs without prior transformations into static graphs.
The authors of [22] proposed three classification tasks of dissemination on temporal networks. The first one concerns the discrimination of observations of a dissemination process and random observations. The second task aims to discriminate temporal graphs subject to two dissemination processes differing in the infection probability. Finally, the third classification task is similar to the second one, but under incomplete information, i.e., parts of the network's observations are unavailable. Our kernel achieves a high state-of-the-art classification accuracy and efficiency on all three tasks.

Contributions:
-We introduce the temporal graphlet kernel, defined as the inner product of normalized graph feature vectors counting the occurrences of labeled temporal graphlets.
-We present a highly efficient approximation variant of our temporal graphlet kernel that approximates the number of temporal wedges. -We show that our temporal graphlet kernels reach high accuracies in classifying epidemic spreading in real-world data sets. In most cases, our temporal graphlet kernels beat the state-of-the-art kernels and neural networks and are on par otherwise. The gains in accuracy are often significant. Moreover, our kernels are up to several orders of magnitude faster than the baselines.
We give an overview of the related work in Appendix A.1.

Preliminaries
A labeled, temporal graph G = (V, E, l) consists of a finite set V of nodes, a finite set E of (directed) temporal edges e = (u, v, t) with u and v in V , u = v, availability time (or time stamp) t ∈ N, and a labeling function l : V × N → Σ. The labeling function l assigns a label to each node at each time step t ∈ N. Let d(v) be the degree of vertex v, i.e., the total number of incoming and outgoing temporal edges. We denote with S(G) = (V, E) the underlying static graph of Kernels for Graphs: A kernel on a non-empty set X is a symmetric, positive semidefinite function k : X × X → R. Equivalently, a function k is a kernel if there is a feature map φ : X → H to a Hilbert space H with inner product ·, · , such that k(x, y) = φ(x), φ(y) for all x and y in X . Let G be the set of all (temporal) graphs, then a kernel k : G × G → R is a (temporal) graph kernel. Static Graphlet Kernel: Shervashidze et al. [23] introduced the graphlet kernel for static (unlabeled) graphs. It counts the occurrences of subgraph patterns of a fixed size which are called graphlets. For a graph G and k ∈ {3, 4, 5}, the static graphlet kernel counts the isomorphism types of all induced subgraphs with k nodes. The subgraphs can be disconnected. Let φ(G) σi be the number of occurrences of the isomorphism type σ i for 1 ≤ i ≤ N with N the number of different types. The feature map of the kernel is then φ SG (G) = (φ(G) σ1 , . . . , φ(G) σ N ), and the graphlet kernel is k SG (G, H) = φ SG (G), φ SG (H) for all graphs G and H in G. For small graphs representing molecules, labeled graphlets have also been considered [29]. Temporal Motifs: Our work is based on extending the commonly used definition of temporal motifs first introduced in [24].

Temporal Graphlet Kernel
We extend Definition 1 for labeled temporal graphs. Our approach is general and can be adapted for other definitions. Definition 2. In a labeled temporal graph, the label of a k-node, -edge, δ- We are interested in the classification of dissemination that spreads along temporal edges. The labels can be used to encode different dissemination patterns. Next, we define an equivalence relation on graphlets.
A temporal graphlet is edge-induced, in contrast to the static graphlet kernel, which counts the number of node-induced, possibly disconnected, subgraphs. Moreover, our equivalence relation considers the chronological order of the edges but not the actual time stamps, which would be too restrictive. Figure 2 shows an example for the equivalence relation. Note that non-equivalence can also arise from different labels in the case of labeled temporal graphs. Next, we use the equivalence relation to define graph feature vectors based on temporal graphlets.
Definition 4. For a parameter δ in N, let T be the equivalence classes of ∼. Given a temporal graph G, we defineφ T TG (G) as the vector with a component for each τ ∈ T counting the occurrences of temporal graphlets equivalent to τ in G. We denote the normalized feature vector by φ T We derive the temporal graph kernel from these feature vector.
Definition 5 (Temporal Graphlet Kernel). Given two temporal graphs G 1 and G 2 , the temporal graphlet kernel is k T

Counting Temporal Graphlets
Counting temporal graphlets is a hard problem. In general, deciding if a δ, kstar graphlet exists in a given temporal graph is NP-complete [14]. The known counting and enumeration algorithms for general temporal graphlets have exponential worst-case running times, e.g., the backtracking enumeration algorithm of Mackey et al. [16] or the general counting algorithm presented in [24]. Besides these negative results, several special cases of temporal graphlets can be computed efficiently. In the following, we discuss the counting of general temporal graphlets and the efficient counting of temporal graphlets with two or three nodes and edges, respectively, which are elementary classes of motifs for the characterization of temporal networks [26,24], as well as the underlying dissemination process.

Labeled Temporal Graphlets for Dissemination
Our goal is to classify disease or information spreading in temporal graphs. Therefore, we use a binary label alphabet Σ that encodes if a node is infected or susceptible or if a node has obtained some information or not. It is possible to use our approach for larger alphabet sizes that include, e.g., exposed or recovered labels to model complex epidemiological behaviors [3]. In the following, we discuss the counting of small graphlets with two or three nodes and edges, respectively. The motivation is that the dissemination of, e.g., viruses or (fake) news on social networks is usually a mainly local process [9,28]. Therefore, we expect small and connected graphlets to capture these processes well-we verify this hypothesis in Section 5. The authors of [24] identified 36 non-equivalent temporal unlabeled graphlets for k ∈ {2, 3} nodes and = 3 edges. More specifically, eight non-equivalent triangles and 24 stars with three edges. In the case of three vertices and two edges, the temporal graphlet is called a temporal wedge. Figure 3 shows the four non-equivalent (unlabeled) temporal wedges. If we take node labelings into account, the number of non-equivalent graphlets increases.
Lemma 1. Let G be a labeled temporal graph and L = |Σ| the size of its label alphabet. The number of distinct labels of -edge temporal graphlets is L 2 .
It follows from Lemma 1 that for Σ = {infectected, susceptible} there are a total number of 2304 pair-wise non-equivalent labeled graphlets in G with two or three nodes and three edges. Similarly, the number of non-equivalent labeled temporal wedges is 64.

Counting General Temporal Graphlets
In order to count the occurrences of general labeled graphlets, we adapt the counting algorithm introduced in [24]. Counting the occurrences of a (nonlabeled) temporal graphlet g is done in three steps: 1. Find all instances of the subgraph S(g) in S(G), where S(g) denotes the underlying static graph of the graphlet g, i.e., all temporal edges are replaced by static edges, and multi-edges are merged. 2. For each S(g), collect all temporal edges incident only to nodes in S(g) in a chronologically ordered sequence σ. 3. Count the occurrences of g in σ using dynamic programming.
The first step is done using an algorithm for enumerating subgraphs in the static graph S(G). The second step is just collecting the corresponding temporal edges. The third step uses a dynamic programming approach in which a temporal graphlet is considered as a chronologically ordered sequence of temporal edges. Therefore, the count of a graphlet of length edges can be computed using the count of the prefix of length − 1. To this end, for each possible edge sequence of lengths smaller or equal to , a counter keeps track of its occurrences. Let m be the number of static edges in S(g), then all occurrences of g in the sequence σ can be counted with a single pass over the edge sequence σ in O(m · |σ|) running time because each edge leads to maximal O(m ) counter updates when it is processed and when it leaves the time window δ. The sliding time window is used to ensure that only graphlets are counted that respect the maximal temporal distance of δ. Furthermore, after σ is processed, the counters contain all occurrences of graphlets with maximal edges in S(g).
In order to apply the counting framework for labeled temporal graphlets, we map the time-dependent node labels to edge labels.
To count the labeled graphlets, we now can apply Lemma 2 to the counting framework, where we use, for each possible labeled edge sequence σ l of lengths smaller or equal to , a counter that keeps track of the occurrences of σ l . The running time for counting labeled temporal graphlets is then in O((m·|Σ| 2 ) ·|σ l |).

Counting Two and Three Node Graphlets
The running time of the general counting algorithm described in the previous section can be improved for graphlets with two or three nodes and three edges. Efficient variants for graphlets with two or three nodes and three edges exist, namely for stars and triangles [24]. Counting the number of all labeled star graphlets over three nodes and edges is possible in O(|E| · |Σ| 2 ). We can count temporal wedges similarly. And, counting the numbers of all labeled temporal triangles has a running time in O(T ∆ + c ∆ |E| · |Σ| 2 ), where T ∆ is the running time for the enumeration of static triangles in S(G) and c ∆ the number of static triangles in S(G). We refer the reader to [24] for further details of the algorithms.

Temporal Wedge Kernel Approximation
As we will see in Section 5, the wedge-based temporal graphlet kernel shows an excellent trade-off between running time and classification accuracy. The reason is that the temporal wedges can capture dissemination patterns well, and they are easy to count. We further improve this trade-off with a highly efficient approximation algorithm. First, note that we can count the labeled wedges by iterating over all nodes and considering all incoming and outgoing edge combinations. For each pair of edges, we increase the counter of the correspondent labeled wedge. The running time for counting all labeled wedges is then in We introduce an approximation for the temporal wedge kernel based on this counting variant. The idea is to sample temporal wedges by extending techniques for wedge sampling in static graphs [22]. First, let G = (V, E, l) be a labeled temporal graph that has no vertex with two incident edges with the same time stamp (we discuss the general case later). Then w = v∈V is the total number of temporal wedges in G. We first sample a vertex with a probability of 2 /w and then a pair of to v incident edges uniformly at random, i.e., with probability 1/ d(v) 2 . The probability of the sampled temporal wedge is then 1/w, and therefore, it is a uniform sample. Algorithm 1 shows the approximation for the feature vector φ TG (G) of normalized temporal wedge counts.

Algorithm 1
Input: A temporal graph G, sample size s ∈ N Output: A feature vector φTG(G) of normalized temporal wedge counts 1: Initialize feature vector φTG(G) to a vector of zeros 2: Compute probabilities pv for all v ∈ V 3: for 1, . . . , s do 4: Sample vertex v with probability pv 5: Sample two edges {e, f } incident to v 6: Let τ be the temporal wedge defined by e and f 7: φTG(G)τ ← φTG(G)τ + 1 s 8: end for 9: return φTG(G) Theorem 2. Let G be a set of temporal graphs with label alphabet Σ. Moreover, let W be number of non-equivalent labeled temporal wedges, λ ∈ R >0 , and δ ∈ (0, 1). For s = log(2·|G|·W/δ) To support temporal graphs that have equal time stamps of edges at the same vertex, and to obtain a random uniform temporal wedge respecting a given time interval δ, we sample a vertex v with probability p v and one of the edges incident to v uniformly at random. Then we choose the second edge, f , only from the incident edges such that the difference of the availability times of e and f is in [1, δ]. To correct the introduced bias, we apply rejection sampling. Let p f be the probability of the second edge f . The probability of a temporal wedge τ respecting δ and with center v is then P τ = pv·p f d(v) . A lower bound for the probability of any temporal wedge is P min = 1/w. To obtain a uniformly sampled temporal wedge respecting the interval δ, we accept a wedge with probability Pmin Pτ , and we achieve a uniform probability of P τ · Pmin Pτ = 1/w. If the input graphs have similar distributions of the edge times and degrees, forgoing the rejection step leads to similar biases during the wedge sampling. In this case, we may waive the rejection step and still achieve high accuracy.

Experiments
We evaluate our temporal graphlet kernel and compare the effectiveness and efficiency to the baselines provided in [21,22,28]. Our research questions are: -Q1. How do our new kernels compare to the baselines in terms of accuracy? -Q2. What are the running times of our temporal graphlet kernels? -Q3. What is the solution quality and running time of our approximation? -Q4. How is the classification accuracy affected by incomplete knowledge of the dissemination process?
Data Sets: We use the temporal dissemination classification data sets introduced in [22]. The data sets contain the three different classification tasks described in the introduction based on real-world temporal graphs that model physical human interactions and social networks. Please refer to Appendix A.3 for a detailed description. Kernel Instances: We compare the following variants of our temporal graphlet kernel for k = 3 nodes and ∈ {2, 3} edges: 1) TGK -∧ counts labeled temporal wedges, 2) TGK -counts labeled temporal star graphlets, 3) TGK-all counts all labeled temporal graphlets, and 4) Approx-s is our approximation of TGK -∧ with sample size s ∈ {50, 100, 200}. Note that setting k = {2, 3}, i.e., the kernels also count graphlets on two nodes, did not improve the results. Furthermore, we use state-of-the-art approaches based on kernels and neural networks as baselines. The authors of [22] introduce three different transformations of temporal graphs to static graphs, which differ in the size of the resulting graphs and the amount of loss of temporal information. After the transformations, they apply static kernels to the static graphs for classifying the dissemination process. They use the k-step random walk and the Weisfeiler-Leman subtree kernel. This approach results in the following kernel instances: (1) RD-RW and RD-WL, which use the reduced graph representation, (2) DL-RW and DL-WL, which use the directed line graph expansion, and (3) SE-RW and SE-WL, which use the static expansion. In [21], the authors of [22] introduced graph neural networks (GNNs) based on the three graph transformations. However, Table 1: Classification accuracy in percent and standard deviation for the first and second classification tasks. For each data set, we highlight the highest accuracy in bold. OOT-Computation did not finish within the time limit.
(a) Classification accuracy for the first classification task. the evaluation in [21] showed that the kernel-based approaches outperform the GNNs in almost all instances while requiring less computation time. Tortorella and Micheli [28] introduced a dynamic echo state network called DynGESN for classification of dissemination in temporal networks. Further details and a comparison of our kernels with these neural baselines can be found in Appendix A.6.

Kernel
We implemented our kernels in C++ using GNU CC Compiler 9.3.0. The source code and data sets are available online. 4 The C++ implementation of the baseline kernels from [22] were provided by the authors and compiled with the same settings as our kernels. The experimental protocol is in Appendix A.4. Table 1a and Table 1b show the accuracies for the first and second classification tasks, respectively. Our temporal graph kernels perform better than the baselines for eight of the twelve data sets and are on par for the remaining four. For the first classification task, our kernels have the highest accuracies for Infectious, and TGK -∧ also has the highest accuracy for Mit. For the other data sets, the accuracies are similar to the best performing baselines. In the case of the second classification task, TGK -∧, TGK -, and TGK-all achieve higher accuracies the baselines for all data sets. Similarly, Appendix A.6 shows that our new kernels usually reach higher accuracies compared to the GNN baselines. In general, the accuracies of our kernels are very close to each other for most data sets, and they can all capture the discriminating information well. Q2. Table 2a shows the running times for the kernel computations for the second classification task. We observed similar results for the first task (see Appendix A.5). The impact of the time window parameter δ on the running time of the temporal graphlet kernels is limited. TGK -∧ is the fastest kernel for all data sets but the Mit data set. Here the WL-kernel based on the reduced graph representation (RG-WL) is faster. Its running time also comes close to TGK -∧ for the other data sets, but it has much worse accuracy (see Q1). The reason is that there are no multiple edges between pairs of nodes in graphs in reduced graph representation, which leads to loss of temporal information and affects the accuracy. Our TGK -is faster than the random walk kernels and the WL-kernels for Highschool and Mit. Notice that the running time of DL-RW exceeded the time limit of one hour, where our TGK -kernel only needed 102 ms. Q3. Table 1a and Table 1b show the accuracies of our approximation algorithm for sample sizes s ∈ {50, 100, 200}. With increasing sample size, the approximation error is reduced as expected. The approximation error is generally low, while the speed-up compared to TGK -∧ for low sample sizes is high. However, for s = 200, the difference in running time of the approximation and TGK -∧ is small for Tumblr and Dblp. The reason is that the exact algorithm is already very efficient due to the low average maximal degree in these data sets (see Table 4). Due to Theorem 2, our approximation is suited for large data sets. To further evaluate the performance on a larger data set, we generated a synthetic data set consisting of 100 graphs generated using the Barabási-Albert preferential attachment method [1] and randomly chosen availability times t(e) ∈ [0, 1000] for each edge e. Each of the graphs contains 5000 nodes and 49 900 edges with an average maximal degree of 390.3. The dissemination process is simulated analogously to the second classification task. Table 3 shows the running times and accuracies. The results suggest very good scalability of our approximation. The running times are only a fraction of the exact methods, and the accuracy is high. Q4. In order to evaluate how the accuracy is affected by incomplete knowledge, we applied our kernel to the third classification task, in which classification tasks one and two are modified by partly reset node labels. We compare our kernels with the best performing baselines DL-RW, DL-WL, SE-RW, and SE-WL.  For the first modified task and 50% to 80% missing data, TGK -∧ has the highest mean accuracy. Our other kernels are on par with the best performing baseline SE-RW and are significantly better than the other baselines. In the case of the second modified task, our kernels beat SE-RW, SE-WL, and DL-WL for all percentages, often with significant gaps in the accuracies, e.g., for the WLkernels. Our kernels have the highest mean accuracy for 20% and from 40% to 80%. The accuracies are on par with the baselines for the remaining percentages. In conclusion, our new temporal graphlet kernels often achieve higher mean accuracy than the kernels introduced in [22], especially in cases where large percentages of information are not available. Hence, our kernels are competitive and often better in the task of classification under missing information.

Conclusion
We introduced a temporal graphlet kernel for classifying dissemination processes on temporal graphs. Our experimental evaluation showed that our approach   beats the state-of-art baselines in most data sets and is on par for the remaining data sets. Our approximative kernel has high accuracy while running significantly faster on large data sets. The wedge-based kernel has an excellent trade-off between running time and accuracy. Finally, our kernels have high accuracy even when information about the dissemination is missing, especially when a majority of the information is unknown.

A.1 Related Work
Graph kernels have been studied extensively in the past 15 years; see [11] for an overview. Important approaches include random walk and shortest path kernels [2,5,12], as well as the Weisfeiler-Leman subtree kernel [18,27]. Further recent works focus on assignment-based approaches [10,20], spectral techniques [9], and graph decomposition [19]. Most kernels are designed for static graphs, with few exceptions considering different aspects of temporal graphs. Li et al. [13] present a family of algorithms that efficiently recomputes the random walk kernel when graphs are modified. Paaßen et al. [23] use graph kernels for predicting the next graph in a dynamically changing series of graphs. Similarly, Anil et al. [1] propose spectral graph kernels to predict the evolution of social networks. Closely related to our work are [21] and [22], which also discuss the classification of dissemination in temporal networks. To this end, the authors propose transforming the labeled temporal graphs into labeled static graphs. In [22], they compare three transformations that differ in loss of information and size of the resulting static graph. The authors combine their transformations with the random walk and the Weisfeiler-Leman subtree kernels. The kernel-based approach with the most expressive transformation achieves state-of-the-art classification accuracy but does not scale to large graphs. In [21], the transformations have been used with graph neural networks, but the overall performance was worse compared to graph kernels. Another closely related work uses dynamic echo state networks [28]. While the approach does not outperform the accuracy of the transformation-based temporal graph kernels, an advantage is its ability to process graphs in an online setting requiring less space. Furthermore, various principled extensions of graph neural networks to the temporal domain exist; see this recent survey [8] and references therein.
Ribeiro et al. [25] give an overview of motifs in static networks. General overviews of temporal graphs can be found in [6,17]. Various attempts to extend the concept of motifs to evolving graphs have been proposed [7,15]. Paranjape et al. [24] define temporal motifs as induced subgraphs on sequences of temporal edges. They introduce an algorithm for counting general temporal graphlets and efficient variants for specific small graphlets. We generalize these algorithms for counting labeled temporal graphlets. Mackey et al. [16] introduced an enumeration algorithm for temporal graphlets. Several recent works discuss the sampling of temporal motifs [14,15,26].

A.2 Omitted Proofs
Proof (Proof of Lemma 1). For each of the temporal edges (u, v, t) in the sequence of temporal edges, we consider the number of different labels for the first node u at time t and the second node v at time t + 1, leading to L 2 possible combinations. Having edges leads to L 2 possible sequences in total.
Proof (Proof of Lemma 2). We use an edge labeling function ξ and for each edge e = (u, v, t) ∈ E, we construct a new label ξ(e) by the concatenation of the time-dependent node labels l(u, t)#l(v, t + 1), where # is an additional symbol not in Σ. The edge label sequence is then l e (g) = (ξ(e 1 ), . . . , ξ(e )). Hence, there is a one-to-one mapping between l(g) and l e (g) for all labeled temporal graphlets g.
Proof (Proof of Theorem 1). If the temporal graph is given in incident list representation, i.e., each vertex has a list of incident temporal edges, and the degree d(v) can be determined in constant time. Then, computing the number of wedges and the probabilities p v is possible in O(|V |) time. Due to Lemma 1 the initialization takes O(|Σ| 2 ) time, and each operation in the for loop is possible in constant time.
Proof (Proof of Theorem 2). First, by an application of the Hoeffding bound together with the union bound, it follows that by setting for all 1 ≤ j ≤ W , and all temporal graphs G i in G. Let G 1 and G 2 in G, then The last inequality holds because the components of φ TG (·) are in [0, 1]. Finally, by setting ε = λ/W the result follows.

A.3 Data Sets
-Infectious and Highschool: Contain face-to-face contacts between visitors of the exhibition Infectious: Stay Away [8] and interactions between high school students. -Mit: A temporal graph of contacts between students [6].
-Facebook and Tumblr: The first graph is a subset of the activity of a Facebook community over three months [27]. The Tumblr graph contains quoting between Tumblr users [11]. -Dblp: A subset of the Digital Bibliography & Library Project (DBLP) database representing temporal co-author graphs. Nodes represent authors, and the time stamp of an edge is the year of a joint publication.
The authors of [22] proposed three classification tasks and provided the labeled data sets. 5 Each classification data set consists of a set of graphs belonging to two classes. Table 4 shows the statistics of the data sets. The first classification task is the discrimination of observations of a dissemination process and random labeling. The second classification task aims to discriminate temporal graphs that were subject to two different dissemination processes differing in the infection probability. The third classification task is the classification under incomplete information. The reasons for missing information about the dissemination process are manifold, e.g., non-symptomatic infections, people hiding their infection for various reasons, or spreading fake news recorded at known spreaders only.
Based on the Infectious data set and the first two classification tasks, for each graph, the labels of {10%, . . . , 80%} of randomly chosen infected nodes are set back to non-infected. This process is repeated ten times resulting in 80 data sets for each of the two classification tasks.

A.4 Experimental Protocol
We computed the normalized Gram matrices and report the classification accuracies obtained with the C-SVM implementation of LIBSVM [5], using 10fold cross-validation. The C-parameter was selected from {10 −3 , 10 −2 , . . . , 10 2 , 10 3 } by 10-fold cross-validation on the training folds. We repeated each 10-fold cross-validation ten times with different random folds and report average accuracies and standard deviations. The time window for the temporal graphlets (δ ∈ {10 i | 1 ≤ i ≤ 4}) was selected by fold-wise 10-fold cross-validation. Likewise, the number of steps of the random walk kernel (k ∈ {1, . . . , 5}) and the number of iterations of the Weisfeiler-Leman subtree kernel (h ∈ {1, . . . , 5}) were selected by fold-wise 10-fold cross-validation. All experiments ran on a computer cluster. Each experiment had an exclusive node with an Intel(R) Xeon(R) Gold 6130 CPU @ 2.10GHz and 192 GB of RAM. The time limit was one hour. Analogous to [21] and to compare the running times, we set the walk length of DL-RW to k = 2 and the number of iterations of DL-WL to h = 2.
A.5 Running Times for the First Classification Task   Table 5 shows the running times for the first classification.

A.6 Comparison to Graph Neural Networks
We present the classification results using the neural approaches presented in [21] and [28]. We compare them to our temporal graphlet kernels. The GNN model in [21] is based on the GIN architecture introduced in [29]. The final GNN layer is fed into a four-layer MLP followed by a softmax function. Alternatively, a Jumping Knowledge (JK) approach [30] to combine the outputs of all layers is used. The neural networks were trained for 200 epochs using the Adam optimizer with cross-entropy loss. For each of our three transformations introduced in [22], the following GNNs were trained on the transformed data sets: 1. RG-GIN and RG-JK for the reduced graph, 2. DL-GIN and DL-JK for the directed line graph expansion, and 3. SE-GIN and SE-JK for the static expansion.