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.


extfieldsofstudy:
Computer Science
Medicine

text:
Open Long-Tailed Recognition in a Dynamic World

Real world data often exhibits a long-tailed and open-ended (with unseen classes) distribution. A practical recognition system must balance between majority (head) and minority (tail) classes, generalize across the distribution, and acknowledge novelty upon the instances of unseen classes (open classes). We define Open Long-Tailed Recognition++ (OLTR++) as learning from such naturally distributed data and optimizing for the classification accuracy over a balanced test set which includes both known and open classes. OLTR++ handles imbalanced classification, few-shot learning, open-set recognition, and active learning in one integrated algorithm, whereas existing classification approaches often focus only on one or two aspects and deliver poorly over the entire spectrum. The key challenges are: 1) how to share visual knowledge between head and tail classes, 2) how to reduce confusion between tail and open classes, and 3) how to actively explore open classes with learned knowledge. Our algorithm, OLTR++, maps images to a feature space such that visual concepts can relate to each other through a memory association mechanism and a learned metric (dynamic meta-embedding) that both respects the closed world classification of seen classes and acknowledges the novelty of open classes. Additionally, we propose an active learning scheme based on visual memory, which learns to recognize open classes in a data-efficient manner for future expansions. On three large-scale open long-tailed datasets we curated from ImageNet (object-centric), Places (scene-centric), and MS1M (face-centric) data, as well as three standard benchmarks (CIFAR-10-LT, CIFAR-100-LT, and iNaturalist-18), our approach, as a unified framework, consistently demonstrates competitive performance. Notably, our approach also shows strong potential for the active exploration of open classes and the fairness analysis of minority groups.

INTRODUCTION
O UR visual world is inherently long-tailed and open-ended [1], [2], with a few common visual categories (i.e., head classes) and many more relatively rare categories (i.e., tail classes). At the same time, new visual concepts constantly emerge as we navigate in an open world (i.e., open classes).
Although natural data distributions contain head, tail, and open classes, existing classification approaches focus mostly on either the head [3], [4] or the tail [5], [6], and often in a closed setting [7], [8] (Fig. 2). We thus formally study Open Long-Tailed Recognition++ (OLTR++) arising from natural data settings. A practical system should be able to work for a few head and many tail categories, to generalize the concept of a single category from only a few known instances, as well as to acknowledge and explore novelty upon an instance of an unseen or open category. We define OLTR++ as learning from long-tail and open-end distributed data and evaluating the classification accuracy over a balanced test set which includes head, tail, and open classes in a continuous spectrum (Fig. 1).
The key challenges for OLTR++ are tail recognition robustness and open-set sensitivity. As the number of training instances drops from thousands in the head class to a few in the tail class, we should prevent the performance from dropping drastically.
Meanwhile, for open classes, the recognition performance relies on the sensitivity to distinguish unknown samples from known classes, as well as to select informative samples for data-efficient active exploration and future model updates.

Dynamic World
Imbalanced Classification

Head Classes Tail Classes Open Classes
Open Set Recognition + Active Learning In our algorithm (OLTR++), there is a learned metric that respects both the closed-world classification and acknowledge the novelty of the open world. This metric maps images to an embedding space (dynamic meta-embedding), where visual concepts can relate to each other to improve both the tail recognition robustness and open-set sensitivity.
Specifically, our dynamic meta-embedding is a combination of two components: direct feature and induced feature. 1) Direct feature is a standard embedding that gets updated from the training data by stochastic gradient descent over the classification loss. It is usually less generalized in tail classes, compared to head classes, because of the lack of sufficient supervision. 2) Memory feature, instead, is an induced feature through a visual memory association mechanism, inspired by meta-learning methods [5], arXiv:2208.08349v1 [cs.CV] 17 Aug 2022 Fig. 2: Comparison between our proposed OLTR++ and related existing tasks. Our task, in a more realistic setting, is a combination of the three existing tasks (imbalanced classification, few-shot learning, and open-set recognition) in addition to active exploration, which constitutes a dynamic learning loop that can facilitate robust deployment of vision systems. [9], [10], that augments the direct feature of each image for better distinguishability. The association is learned to retrieve a summary of memory activations from the direct features of each input and then combined with the original direct features to be the metaembeddings. This memory feature augmentation is particularly effective on tail classes for the lack of supervision to provide generalized features . We address open-class sensitivity by dynamically calibrating the meta-embedding with respect to the visual memory. In other words, the embedding is scaled inversely by its distance to the nearest class centroid (i.e., class memory): the farther away it is from the memory, the more likely it is an open set instance. The distance between the embedding and the nearest centroid is then transformed into "sample informativeness" using an energybased model [11], which is further employed to select informative samples for active learning.
We also adopt modulated attention [12] to encourage the head and tail classes to use different sets of spatial features. As our meta-embedding relates head and tail classes, our modulated attention maintains discrimination between them.
We make the following major contributions. 1) We formally define the OLTR++ task, which learns from long-tail and openend distributed data and optimizes for the overall accuracy over a balanced test set. It provides a comprehensive and unbiased evaluation of visual recognition algorithms in practical settings. 2) We propose an integrated OLTR++ algorithm with dynamic meta-embedding. It handles tail recognition robustness by relating visual concepts among head and tail embeddings, and it handles open-class sensitivity by dynamically calibrating the embedding with respect to the visual memory. 3) We further incorporate an energy-based model into our dynamic meta-embedding for dataefficient active learning (with only sparse human annotations), which is well suited for the constantly-changing visual world. 4) We curated three large OLTR++ datasets according to a longtailed distribution from existing representative datasets: objectcentric ImageNet [3], scene-centric Places [13], and face-centric MS1M datasets [14]. We also set up benchmarks for proper OLTR performance evaluation. 5) Our extensive experimentation on these OLTR++ datasets (as well as standardized benchmarks such as CIFAR-LT 100/10 and iNaturalist-18 [15]) demonstrates that our method consistently outperforms the state-of-the-art methods.
The aim of this work is to advocate a new learning paradigm that can perceive and update in a dynamic world, i.e. simultaneously recognizing real-world long-tailed data while actively exploring novel data with human in the loop. It is a crucial step towards embodied intelligence as well as the robust deployment of vision systems. Besides exhibiting competitive performance on long-tailed recognition, our approach also demonstrates compelling results on open class detection and active exploration with a unified framework centered around visual memory.
Our code, datasets, and models are publicly available at https:// liuziwei7.github.io/projects/LongTail.html. Our work fills the void in practical benchmarks for imbalanced classification, few-shot learning, open-set recognition, and active learning, enabling future research that is directly transferable to real-world applications.

RELATED WORKS
While OLTR++ has not been defined in the previous literature, there are four closely related tasks which are often studied in isolation: imbalanced classification, few-shot learning, openset recognition, and active learning. Fig. 2 summarizes their connections and key differences. Imbalanced & Long-Tailed Recognition. Imbalanced classification is an extensively studied area [24], [25], [26], [27], [28], [29], [30], [31], [32]. While classical methods include under-sampling head classes, over-sampling tail classes, and data instance reweighting, some recent methods apply metric learning [33], [34], hard negative mining [17], [35], and meta learning [7], [36]. For example, lifted structure loss [34] introduces margins between many training instances. The range loss [37] enforces data in the same class to be close and those in different classes to be far apart. Focal loss [17] induces an online version of hard negative mining. And metaModelNet [7] learns a meta regression net from head classes and uses it to construct the classifier for tail classes.
As a step forward from imbalanced classification, longtailed recognition (where the training datasets are more imbalanced) [18], [19], [20], [21], [38], [39], [40], [41], [42] Method Formulation Venue CIFAR-10 CIFAR-100 ImageNet-LT Places-LT  has attracted extensive research interests recently. In Table 1, we provide a systematic overview of representative long-tailed recognition works (including those published after ours). In our approach, we have a dynamic meta-embedding that combines the strengths of both metric learning and meta learning. On the one hand, our direct feature is updated to ensure centroids of different classes are separated from each other; On the other hand, our memory feature is generated on-the-fly in a meta learning fashion to effectively transfer knowledge from head classes to tail classes. Few-Shot Learning. Few-shot learning is often addressed by meta-learning techniques [43], [44], [45], [46], [47], [48]. For example, matching Network [5] learns a transferable feature matching metric to go beyond given classes. And Prototypical Network [49] maintains a set of separable class templates. Additionally, feature hallucination [50] and augmentation [51] have also shown effectiveness. Since these methods focus on fast learning from novel and unseen classes, they often suffer a "catastrophic forgetting" for training classes . Few-shot learning without forgetting [52] and incremental few-shot learning [53] attempt to remedy this issue by leveraging the duality between features and classifiers' weights [54], [55]. However, these methods rely on balanced training sets, while OLTR++ learns from naturally long-tailed training sets instead.
Our approach is closely related to meta learning with associative memory [5], [9], [10], [56], [57], [58]. Compared to prior arts, our memory feature has two advantages: 1) it transfers knowledge to both head and tail classes adaptively via a learned concept selector; 2) it is fully integrated into the network without episodic training, thus suitable for large-scale applications. Open-Set Recognition. Open-set recognition [59], [60], or outof-distribution detection [61], [62], [63], aims to re-calibrate the sample confidence in the presence of open classes. One of the representative techniques is OpenMax [60], which fits a Weibull distribution to model logits. However, when there are both open and tail classes, distribution-fitting based methods often confuse the two because of the less generalized features of tail classes. Instead of calibrating the output logits, our OLTR++ approach incorporates a confidence estimation mechanism into feature learning and dynamically re-scale the meta-embedding w.r.t. the learned visual memory, such that samples from known classes are expected to be closer to the memory compared to novel samples. Open-World Recognition. Open-world recognition [64], [65], [66] is a closely related field whose goal is to distinguish "unknown unknown classes" from "known known classes". [64] also considers a dynamic setting where unknown classes are continuously added and detected, and examines the influence of unknown classes on the accuracy of known classes. [66] further incrementally learns the new classes. Once they are detected as unknown and an oracle provides labels for the objects of interest among all the unknowns. Here we advocate this dynamic-world endeavor: instead of just detecting the unknown classes, we aim to recognize the semantic label of the unknown classes. Zero-Shot Learning. Zero-shot learning (ZSL) [67], [68], [69] is also a promising direction for recognizing novel classes. ZSL aims to learn the association between base and novel class features with the aid of certain shared semantic knowledge (e.g. attributes, word2vec), which is not directly applicable here. In comparison, our active exploration is more focused on the annotation-efficiency of recognizing novel classes, i.e. using less human annotations to achieve acceptable accuracies on novel classes. Active Learning. Active learning aims to explore unlabeled data with an oracle annotator that provides ground truth labels to a few selected samples. The central issue here is the exploration efficiency, i.e. obtaining higher performance with less oracle queries. The representative works can be roughly categorized into two realms: generation-based methods [70], [71] and selectionbased methods [72], [73].
However, existing active learning methods mainly work in closed-world setting, where they focus on selecting informative samples for the known categories to improve the performance. Here we study a realistic yet more challenging problem, selecting informative samples from a mixture of known and unknown categories so as to recognize both of them, which we coined as "active exploration". Their key differences are listed in Table 2. Our active exploration considers both informativeness and openness during sample selection. Incremental Learning. Incremental learning aims to continually learn new tasks (e.g. novel classes) without catastrophic forgetting. Extensive research has been performed from different perspectives: neural architectures [74], [75], replay/rehearsal mechanisms [76], [77], parameter regularization [78], [79] and learning techniques [80], [81]. Here our dynamic learning loop   aims to achieve continual recognition of novel classes in a dataefficient manner.
Fairness Learning/Analysis. The open long-tailed recognition proposed in our work also has an intrinsic relationship to fairness analysis [82], [83], [84], [85], [86]. Their key differences are listed in Table 3. On the problem setting side, both open longtail recognition and fairness analysis aim to tackle the imbalance existed in real-world data. Open long-tailed recognition focuses on the longtail-ness in both known and unknown categories while fairness analysis deals with the bias in sensitive attributes such as male/female and white/black. On the methodology side, both open long-tailed recognition and fairness analysis aim to learn transferable representations. Open long-tailed recognition optimizes for the overall accuracy of all categories while fairness analysis optimizes for several attribute-wise criteria. The preliminary results in Table 6 demonstrates that our proposed dynamic meta-embedding is also a promising solution to fairness analysis.

OUR OLTR++ MODEL
We propose to map an image to a feature space such that visual concepts can relate to each other based on a learned metric that respects the closed-world classification while acknowledging the novelty of the open and dynamic world. Our model has three major modules (Fig. 3): dynamic meta-embedding, modulated attention, and active exploration. The first relates and transfers knowledge between head and tail classes, and the last two maintain discrimination between them with human-in-the-loop.

Intuitive Explanation of Our Approach
In this section, we give an intuitive explanation of our approach that tackles the problem open long-tailed recognition. From the Firstly, in our approach, we obtain a visual memory by aggregating the knowledge from both head and tail classes. Then the visual concepts stored in the memory are infused back as associated "fast feature" to enhance the original "slow feature". In other words, we use induced knowledge (i.e. "fast feature") to assist the direct observation (i.e. "slow feature"). We further learn a concept selector to control the amount and type of infused "fast feature". Since head classes already have abundant direct observation, only a small amount of "fast feature" is needed. On the contrary, tail classes suffer from scarce observation, the associated visual concepts in "fast feature" are more beneficial to tail classes than to head classes. Finally, we calibrate the confidence of open classes by calculating their reachabilities (i.e. feature space distances) to the obtained visual memory (i.e., class centroids). All together, we provide a comprehensive treatment to the full spectrum of head, tail and open classes, improving the performance on all categories.

Dynamic Meta-Embedding
Dynamic meta-embedding is a combination of a direct image feature and an associated memory feature, where the feature norm indicates the familiarity to known classes.
Consider a convolutional neural network (CNN) with a softmax output layer for classification. The second-to-the-last The discriminative centroids constitute our visual memory, which are obtained with two iterative steps, neighborhood sampling and affinity propagation.
layer is the feature and the last layer is the linear classifier (cf. φ(·) in Fig. 3). The feature and the classifier are jointly trained in an end-to-end fashion. Let v direct denote the direct feature extracted from an input image. The final classification accuracy largely depends on the quality of this direct feature. While a feed-forward CNN classifier works well with big training data [3], [87], it lacks sufficient supervised updates from small data in tail classes. We propose to enrich direct feature v direct with visual concepts in a memory module through a memory feature v memory , which is derived from a memory bank that captures visual concepts of each training classes. This mechanism is similar to the memory components in meta learning [46], [58]. We denote the resulting feature meta embedding v meta . Learning Visual Memory M . To construct the memory bank, we follow [88], [89] on class structure analysis and adopt discriminative centroids as the basic building block. Let M denote the visual memory of all the training data, where K is the number of training classes. Compared to alternatives [49], [90], this memory is appealing for our OLTR++ task: it is almost effortlessly and jointly learned alongside the direct features {v direct n }, and it considers both intra-class compactness and interclass discriminativeness.
More concretely, as illustrated in Fig. 5, we compute class centroids in two steps. 1) Neighborhood Sampling: We sample both intra-class and inter-class examples to compose a mini-batch during training. These examples are grouped by their class labels and the centroid c i of each group is updated by the direct feature of this mini-batch, which can be formulated as: where 1(·) is the indicator function, and B is the batch size.
2) Affinity Propagation: We alternatively update the direct feature v direct and the centroids to minimize the distance between each direct feature and the corresponding class centroids and maximize the distance to other centroids. Note that the "repelling edges" in Fig. 5 are calculated through a large margin loss L LM as described in Eqn. 13.
At the end of the training, we obtain a visual memory module M containing important visual concepts within the dataset.
Composing Memory Feature v memory . For an input image, v memory enhances its direct feature when training data are limited (as in the tail class). The memory feature relates class centroids in the memory to transfer knowledge to tail classes: where o ∈ R K is the coefficients hallucinated from the direct feature. We use a lightweight neural network to obtain the coefficients from the direct feature, o = T hal (v direct ).
Obtaining Dynamic Meta-Embedding. v meta combines the direct feature and the memory feature, and is fed to the classifier for the final class prediction (Fig. 6): where ⊗ denotes element-wise multiplication and e is a concept selector. γ > 0 is a seemingly redundant scalar for the closedworld classification tasks. However, in the OLTR++ setting, it serves an important role in differentiating the examples of the training classes from those of the open-set. γ measures the reachability [91] of an input's direct feature v direct to the memory M -the minimum distance between the direct feature and the discriminative centroids: When γ is small, the input likely belongs to a training class from which the centroids are derived, and a large reachability weight 1/γ is assigned to the resulting meta-embedding v meta . Otherwise, the embedding is scaled down to an almost all-zero vector at the extreme, which is useful to encode open classes.  Fig. 7: Modulated attention is spatial attention applied on selfattention maps ("attention on attention"). It encourages different classes to use different contexts, which helps maintain the discrimination between head and tail classes.
As the direct feature is often good enough for the data-rich head classes, whereas the memory feature is more important for the data-poor tail classes. We design a concept selector, e, to adaptively select them in a soft manner. We learn a lightweight network T sel (·) with a tanh(·) activation function on v direct :

Modulated Attention
Since discriminative cues of head and tail classes tend to distribute at different locations in the image, we find it beneficial to enhance direct feature, v direct , with spatial attention to separate head and tail classes. Specifically, we propose modulated attention to encourage samples of different classes to use different contexts. Firstly, we compute a self-attention map SA(f ) from the input feature map by self-correlation [12]. It is used as contextual information and added back (through skip connections) to the original feature map. The modulated attention M A(f ) is then designed as conditional spatial attention applied to the selfattention map: M A(f )⊗SA(f ), which allows examples to select different spatial contexts (Fig. 7). The final attention feature map becomes: where f is a feature map in CNN, SA(·) is the self-attention operation, and M A(·) is a conditional attention function [92] with a softmax normalization.
Sec. 4.1 shows empirically that our attention design achieves superior performance than the common practice of applying spatial attention to the input feature map. This modulated attention ( Fig. 7 (b)) could be plugged into any feature layer of a CNN. Here, we modify the last feature map only.

Active Exploration of Open Classes
In the dynamic world, the model should not halt after training. We assume a continuous training, inference, annotation, and model update loop as our model actively explores the visual world Compute the ratio between the first two nearest distances: Compute the free energy function of v direct : E n ← −T act · log K i e Uopen·U inf o /Tact . Select high-energy samples for further human annotations. Update the classifier φ(·) using newly added data. end for over time. Every time our model encounters certain sample of open classes, our model will determine whether this sample is informative enough for further human annotation. After obtaining these human annotations in an efficient manner, our model will be continually updated according to the newly added data.
The active exploration step has three major components: 1) active sample selection based on two different types of uncertainty, 2) human-in-the-loop annotation, and 3) model update using active data annotations, all three of which constitute a dynamic recognition loop. The detailed algorithmic pipeline of our active exploration is listed in Alg. 1.

Two Types of Uncertainty in Active Exploration
Unlike the standard active learning setting that work in closedworld setting, there actually exist two types of uncertainty here in active exploration: uncertainty in openness and uncertainty in informativeness. Existing active learning algorithms are not directly applicable here since their uncertainty estimation mechanism only considers the informativeness among known classes, which is not suitable for modeling the openness between known classes and unknown classes.
In the following, we elaborate the modeling the two types of uncertainty in the context of active exploration: 1) Uncertainty in Openness: We measure the openness U open of a new sample using the distance between its embedding and the nearest centroid, which can be formulated as: where v direct is the direct feature of the new sample and c i is the centroid of the i-th class. 2) Uncertainty in Informativeness: Intuitively, the most informative samples would be those that lie on the decision boundaries between different classes. We first sort the distances between the embedding of the new sample to all existing class centroids in ascending order: d sorted n . Then the informativeness of a new sample is defined as the ratio between the first two nearest distances: These two types of uncertainty regarding new sample and class centroids are further illustrated in Fig. 8.

Active Sample Selection
At each time step when new data are encountered, the selection of samples for active annotations is based on the combination of both openness and informativeness uncertainty estimation using the energy-based model [11]. Similar to [63], we can express the free energy function E(·) of new sample v direct as follows: where T act is the temperature for controlling the trade-off between precision and recall in active selection.

Human-in-the-Loop Annotation
After selecting these "open" yet "informative" samples, we obtain the semantic labels of these samples by querying human annotators. In the real-world applications [93], [94], it can be executed through online crowdsourcing platform with quality control. Since different human annotators have different preferences for naming unknown categories, it is crucial to maintain consistency between different samples of the same unknown category.

Model Update
Assume that we have an existing classifier φ t (·) at time step t with weight vectors {w i } K i=1 for K known classes. And during time step t to time step t + 1, we will encounter Z unknown classes. Then at time step t + 1, our new classifier φ t+1 (·) will be a concatenation of both known class weights and unknown class weights: Both weights will be updated by the obtained active human annotations.
Note that model update is not our main contribution; there are several feasible instantiations. Since we adopt cosine classifer described in Sec. 3.5, the weight of classifier and the embedding of sample can be transformed interchangeably [52], [55]. Though more sophisticated methods (e.g. learning another network to generate the classifier weights for unknown classes) can be applied, here the classifier weights for unknown classes are simply hallucinated through a weighted average of the meta-embeddings from the actively selected samples for that class, where the weight is determined by E(v direct ). This classifier hallucination approach is extremely suitable for off-the-shelf deployment.

Dynamic Recognition Loop
To accommodate for the dynamic nature of the visual world, this procedure of active sample selection, human-in-the-loop annotation, and model update repeats each time new batch of open data are encountered. Our framework maximizes learning and recognition efficiency by taking the best from both humans and machines within a synergistic collaboration, taking care of both the long-tailed and open-ended distribution existing in the natural world.
In our implementation, the feature extractor is fixed for fast adaptation, while the visual memory is updated to accommodate for the continual stream of unknown classes during the dynamic learning loop. We have further clarified in the revised paper.

Learning
Cosine Classifier. We adopt the cosine classifier [52], [55] to produce the final classification results. Specifically, we normalize the meta-embeddings {v meta n }, where n stands for the n-th input as well as the weight vectors The normalization strategy for the meta-embedding is a nonlinear squashing function [95] which ensures that vectors of small magnitude are shrunk to almost zeros while vectors of big magnitude are normalized to the length slightly below 1. This function helps amplify the effect of the reachability γ (cf. Eq. (3)).
Loss Function. Since all our modules are differentiable, our model can be trained end-to-end by alternatively updating the centroids {c i } K i=1 and the dynamic meta-embedding v meta n . The final loss function L is a combination of the cross-entropy classification loss L CE and the large-margin loss between the embeddings and the centroids L LM : where λ is set to 0.1 in our experiments via observing the accuracy curve on validation set. Specifically, L CE is the cross-entropy loss between dynamic meta-embedding v meta n and the ground truth category label y n : where φ(·) is the cosine classifier described in Eqn. 6 in the main paper. Next we introduce the large margin loss L LM between the embedding v meta n and the centroids {c i } K i=1 : where m is the margin and we set it as 5.0 in our experiments. With this formulation, we minimize the distance between each embedding and the centroid of its group and meanwhile maximize the distance between the embedding and the centroids it does not belong to.

Datasets.
We curated three open long-tailed benchmarks, ImageNet-LT (object-centric), Places-LT (scene-centric), and MS1M-LT (face-centric), respectively.   ArcFace dataset [14], [97], we sampled images for each identity with a probability proportional to the image numbers of each identity. It has 887.5K images and 74.5K identities, with a long-tailed distribution. To inspect the generalization ability of our approach, the performance is evaluated on the MegaFace benchmark [98], which has no identity overlap with MS1M-ArcFace. Network Architectures. Following [50], [51], [52], we employed a ResNet-10 [16] trained from scratch as our backbone network for ImageNet-LT. To make a fair comparison with [7], the pre-trained ResNet-152 [16] was used as the backbone network for Places-LT. For MS1M-LT, we used the popular pre-trained ResNet-50 [16] as the backbone network. To compare with the recent works, we also adopted the two-headed ResNet-50 backbone following [23]. Evaluation Metrics. The evaluation is on the performance of each method under both the closed-set (test set contains no unknown classes) and open-set (test set contains unknown classes) settings. Under each setting, besides the overall top-1 classification accuracy [52] over all classes, we also calculated the accuracy of three disjoint subsets: many-shot classes (classes each with over training 100 samples), medium-shot classes (classes each with 20∼100 training samples) and few-shot classes (classes under 20 training samples). For the open-set setting, the F-measure was also reported for a balanced treatment of precision and recall following [60]. For determining open classes, the sof tmax probability threshold was initially set as 0.1, while a more detailed analysis is provided in Sec. 4.6. Comparison Methods. We chose for comparison state-of-theart methods from different fields dealing with the open longtailed data, including: (1) metric learning: Lifted Loss [34], (2) hard negative mining: Focal Loss [17], (3) feature regularization: Range Loss [37], (4) few-shot learning: FSLwF [52], (5) longtailed modeling: MetaModelNet [7], and (6) open-set detection: Open Max [60]. We applied these methods on the same backbone networks as ours for a fair comparison. We also enabled them with class-aware mini-batch sampling [100] for effective learning. Since Model Regression [101] and MetaModelNet [7] are the most related to our work, we recorded our results along with the numbers reported in the original papers. We also included the recent advances (e.g. CB Focal [18], LDAM [20], Decoupling [21], BBN [22], and RIDE [23]) in long-tailed recognition for a comprehensive evaluation.

Ablation Study
Effectiveness of the Dynamic Meta-Embedding. From Fig. 9 (b), we observe that the combination of the memory feature and concept selector led to large improvements on all three shots, because the obtained memory feature transferred useful visual concepts among classes. Another observation is that the confidence calibrator is the most effective on few-shot classes. And the reachability estimation inside the confidence calibrator helped distinguish tail classes from open classes. Effectiveness of the Modulated Attention. We observe from Fig. 9 (a) that, compared to medium-shot classes, the modulated attention contributed more to the discrimination between manyshot and few-shot classes in the experiments. Fig. 9 (c) further validates that the modulated attention is more effective than directly applying spatial attention on feature maps. It implies that adaptive contexts selection is easier to learn than the conventional feature selection. Effectiveness of the Reachability Calibration. To further demonstrate the merit of reachability calibration for open-world setting, we conducted additional experiments following the standard settings in [62], [96] (CIFAR100 + TinyImageNet(resized)). Our approach shows favorable performance over standard open-set methods [62], [96], as listed in Table 5.

OLTR++ Benchmarking Results
In this section, we extensively evaluate the performance of various representative methods on our OLTR++ benchmarks. ImageNet-LT.   both Lifted Loss [34] and Focal Loss [17] greatly boosted the performance of few-shot classes by enforcing feature regularization. However, they also sacrificed the performance on manyshot classes since there are no built-in mechanism of adaptively handling samples of different shots. Secondly, OpenMax [60] improved the results under the open-set setting. However, the accuracy degraded when it was evaluated with F-measure, which considers both precision and recall in open-set. This proves that when the open classes are compounded with the tail classes, it becomes challenging to perform the distribution fitting that [60] requires. Lastly, although the few-shot learning without forgetting approach [52] retained the many-shot class accuracy, it had difficulty dealing with the imbalanced base classes which are lacked in the current few-shot paradigm. Overall, as demonstrated in Fig. 10, our approach provides a comprehensive treatment to all the many/medium/few-shot classes as well as the open classes with substantial improvements on all aspects. Table 4 (b). With a much stronger baseline (i.e. ImageNet pre-trained ResNet-152), our approach still consistently outperformed other alternatives under both the closedset and open-set settings. The advantage is even more profound under F-measure.

MS1M-LT.
We trained on the MS1M-LT dataset and report results on the MegaFace identification track, which is a standard benchmark in the face recognition field. Since the face identities in the training set and the test set are disjoint, we adopted an indirect way to partition the testing set into subsets of different shots. We approximated the pseudo shots of each test sample by counting the number of training samples that are similar to it by at least a threshold (feature similarity greater than 0.7). Apart from many-shot, few-shot, one-shot subsets, we also obtained a zeroshot subset, for which we could not find any sufficiently similar samples in the training set. It can be observed that our approach has the most advantage on one-shot identities (3.0% gains) and zero-shot identities (1.8% gains) as shown in Table 6.

SUN-LT.
To directly compare with [101] and [7], we also tested out method on the SUN-LT benchmark they provided. The final results are listed in Table 8. Instead of learning a series of classifier transformations, our approach transfered visual knowledge among features and achieved an 1.4% improvement over the prior best.    Note that our approach also incured much less computational cost since MetaModelNet [7] requires a recursive training procedure.

Performance on Fairness Analysis
Results. On the sensitive attribute performance on MS1M-LT, the last six columns in Table 6 show that our approach achieved across-board improvements on both gender sub-groups and ethnicity sub-groups, which has an encouraging implication for effective fairness learning.
Indications. The goal of evaluating the performance on different gender sub-groups and ethnicity sub-groups here is to draw connection between long-tailed recognition and the larger community of bias and fairness in artificial intelligence, which could possibly motivate more future research at the intersection of these two.
To provide a comprehensive comparison on this interdisciplinary sub-field, we further implement and include two representative methods in fairness learning (i.e. fair feature [83] and latent debiasing [99]) into the evaluation.   [72], core-set-based method CoreSet [102] and adversariallearning-based method VAAL [73]. As shown in Fig. 12 (a), our OLTR++ validates its advantage over different percentages of selected open samples for active annotation and demonstrates dynamic-world learning efficiency. Analysis. To further understand the active exploration ability of OLTR++, we visualized the samples of selected and not selected images by our active exploration approach in Fig. 12 (b). We can observe that OLTR++ tends to select canonical images with representative parts and appearance for unseen classes.
Sorted Class ID w.r.t Occurrences Number of Images Per Class Absolute F1 Score Gains

Effectiveness of Dynamic Recognition Loop
Setting. The experiments were performed in a similar setting to active exploration, except that the open/exploration set was divided into two subsets to mimic the two stages in incremental/continual learning scenario. Specifically, both Stage 1 and To mimic the real-world applications, the accuracies of "known/unknown" is calculated by classifying test samples to a combination of known and unknown labels. Results. We compared our results with several representative methods in incremental/continual learning, including Learning without Forgetting (LwF) [80], and Adversarial Continual Learning (ACL) [81]. LwF [80] is a seminal work in the field of incremental learning, which serves as a strong and musthave baseline by employing a soft multi-task learning paradigm. ACL [81] is a recent adversarial-learning-based method of stateof-the-art performance without using external data or models. It is also equipped with open-sourced code and evaluation scripts for fair comparisons. As listed in Table 9, our OLTR++ maintains the learning and recognition effectiveness during the dynamic loop.

Influence of Tailness and Openness
Influence of Dataset Longtail-ness. The longtail-ness of the dataset (e.g. the degree of imbalance of the class distribution) can have a negative impact on the model performance. For faster investigating, the weights of the backbone network were frozen during training. From Fig. 11 (a), we observe that as the dataset became more imbalanced (i.e. power value α decreases), our approach only underwent a moderate performance drop. In other words, dynamic meta-embedding enables effective knowledge transfer among data-abundant and data-scarce classes.  Fig. 13: Examples of the top-3 infused visual concepts from memory feature. Except for the bottom right failure case (marked in red), all the other three input images were misclassified by the plain model and correctly classified by our model. For example, to classify the top left image which belongs to a tail class 'cock', our approach learned to transfer visual concepts that represents "bird head", "round shape" and "dotted texture" respectively.     [27].
Influence of Open-Set Probabilistic Threshold. The performance change w.r.t. the open-set probability threshold is demonstrated in Fig. 11 (b). Compared to the plain model [16] and range loss [37], the performance of our approach changed steadily as the open-set threshold rose. The reachability estimator in our framework helped calibrate the sample confidence, thus enhanced robustness to open classes. Influence of the Number of Open Classes. Finally we investigate performance change w.r.t. the number of open classes. Fig. 11 (c) indicates that our approach demonstrates great robustness to the contamination of open classes.

Further Analysis
In this section, we visualize and interpret memory feature in our framework, as well as present the relation of OLTR++ to fairness analysis and typical failure cases. Infused Memory Feature. In Fig. 13, we inspect the visual concepts that memory feature has infused by visualizing its top activating neurons. Specifically, for each input image, we extracted its top-3 transferred neurons in memory feature. And each neuron is visualized by a collection of highest activated patches [103] over the whole training set. For example, to classify the top left image which belongs to a tail class 'cock', our approach learned to transfer visual concepts that represents "bird head", "round shape" and "dotted texture" respectively. After feature infusion, the dynamic meta-embedding became more informative and discriminative.
We visualize the "memory feature" in Places-LT similarly to ImageNet-LT. Examples of the infused visual concepts from "memory feature" in Places-LT are presented in Fig. 14. We observe that "memory feature" indeed encodes discriminative visual traits for the underlying scene.
Following [27], we visualize the "memory feature" in MS1M-LT by contrasting the least activated average image and the most activated average image of the top firing neuron. From Fig. 15, we observe that "memory feature" in MS1M-LT infused several identity-related attributes (e.g. "high cheekbones", "dark skin color" and "narrow eyes") for precise recognition.
Unsupervised Attribute Discovery. We also quantitatively evaluate the "memory feature" in MS1M-LT by performing unsupervised attribute discovery experiment. The performance is reported on the CelebA dataset [27] via linear probing, as listed in Table 10. Our approach outperforms randomly initialized and ImageNet pretrained features on both top-1 and top-5 average accuracy.
Failure Cases. Since our approach encourages the feature infusion among classes, it slightly sacrifices the fine-grained discrimination for the promotion of under-representative classes. One typical failure case of our approach is the confusion between manyshot and medium-shot classes. For example, the bottom right image in Fig. 13 was misclassified into 'airplane' because some cross-category traits like "nose shape" and "eye shape" were infused. Feature disentanglement [104] and strong contrastive learning [105] are potential alleviations to this trade-off issue.

Input Image
Input Image Input Image Top-1 Transferred Neuron from Memory Feature  Fig. 15: Examples of the infused visual concepts from "memory feature" in MS1M-LT.

CONCLUSIONS
We introduce the OLTR++ task that learns from natural long-tail open-end distributed data and optimizes the overall accuracy over a balanced test set. We propose an integrated OLTR++ algorithm, dynamic meta-embedding, in order to share visual knowledge between head and tail classes and to reduce confusion between tail and open classes. We validated our method on three curated largescale OLTR++ benchmarks (ImageNet-LT, Places-LT and MS1M-LT) as well as active exploration. Our work can enable future researches that are directly transferable to real-world applications.