Algorithmic Aspects of Temporal Betweenness

The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph. In the analysis of many real-world graphs or networks, betweenness centrality of a vertex is used as an indicator for its relative importance in the network. In particular, it is among the most popular tools in social network analysis. In recent years, a growing number of real-world networks is modeled as temporal graphs, where we have a fixed set of vertices and there is a finite discrete set of time steps and every edge might be present only at some time steps. While shortest paths are straightforward to define in static graphs, temporal paths can be considered"optimal"with respect to many different criteria, including length, arrival time, and overall travel time (shortest, foremost, and fastest paths). This leads to different concepts of temporal betweenness centrality and we provide a systematic study of temporal betweenness variants based on various concepts of optimal temporal paths. Computing the betweenness centrality for vertices in a graph is closely related to counting the number of optimal paths between vertex pairs. We show that counting foremost and fastest paths is computationally intractable (#P-hard) and hence the computation of the corresponding temporal betweenness values is intractable as well. For shortest paths and two selected special cases of foremost paths, we devise polynomial-time algorithms for temporal betweenness computation. Moreover, we also explore the distinction between strict (ascending time labels) and non-strict (non-descending time labels) time labels in temporal paths. In our experiments with established real-world temporal networks, we demonstrate the practical effectiveness of our algorithms, compare the various betweenness concepts, and derive recommendations on their practical use.

Introduction
Graph metrics such as betweenness centrality are studied and applied in many application areas, including social and technological network analysis [19,27], wireless routing [5], machine learning [24], and neuroscience [30]. The betweenness centrality of a vertex in a graph measures how often this vertex is visited by a shortest (or optimal) path. High betweenness centrality scores are strict non-strict Shortest O(n 3 · T 2 ) O(n 3 · T 2 ) Foremost #P-hard #P-hard Fastest #P-hard #P-hard Prefix-foremost O(n · M · log M ) #P-hard Shortest foremost O(n 3 · T 2 ) O(n 3 · T 2 ) Table 1: An overview of the computational complexity of the temporal betweenness variants we consider. Here, n refers to the number of vertices, M refers to the total number of time edges, and T refers to the number of time steps.
usually associated with vertices that can be seen as more important for the network. In static graphs, betweenness centrality is a well-studied concept. It is well-known that Brandes' algorithm [2] 1 computes the betweenness centrality of all vertices of a given static graph with n vertices and m edges in O(n · m) time and O(n + m) space.
In temporal graphs, that is, graphs with fixed vertex set and edge set(s) varying over discrete time steps, the notion of betweenness centrality can be defined in a similar fashion. However, there are more options how to choose "optimal" paths. Depending on the application, a path may be optimal if it minimizes the number of edges ("shortest"), the arrival time ("foremost"), or the overall travel time ("fastest"). For any of these path types we can define and study a variant of temporal betweenness centrality. In addition, combinations of optimality criteria such as shortest foremost temporal paths can be considered. Furthermore, we will distinguish between temporal paths with strictly or non-strictly ascending time labels on the edges. We investigate algorithmic aspects of temporal betweenness variants based on, strict and non-strict, shortest, foremost and fastest paths. In addition, we also consider two subtypes of foremost paths, namely shortest foremost, and prefix-foremost paths.
Our main research question is as follows: How hard-theoretically and practically-is the computation of the different variants of temporal betweenness centrality and what does this imply for their usefulness and applicability in practice?
The various betweenness variants show remarkable differences in their computational complexity: while some of them can be computed in polynomial time, others are computationally hard. Note that computing betweenness values is closely related to counting optimal paths since, informally speaking, the betweenness value of a vertex quantifies how many optimal paths go through this vertex. We show that counting foremost and fastest temporal paths is #P-hard, implying the same hardness result for the computation of corresponding betweenness concept. Since temporal betweenness based on foremost temporal paths is arguably the best motivated variant in many application [23,28] areas and we obtain intractability, we investigate to modifications, namely shortest foremost and (strict) prefix foremost temporal paths. For temporal betweeness based on these modified versions of foremost temporal paths as well as shortest temporal paths, we obtain tractability results.
In Table 1, we give an overview of our theoretical findings. We present formal (worst-case) computational hardness proofs. In the cases where we state polynomial-time computability, we provide algorithms that compute the temporal betweenness scores of all vertices in a given temporal . . . Then v 1 and v 2 are vertices with high temporal betweenness based on temporal paths whereas v 3 has very low temporal betweenness based on temporal paths. However for e.g. foremost temporal walks, v 3 would also have a high temporal betweenness.
graph. We remark that in contrast to the static setting, temporal walks (that visit a vertex multiple times) can also be optimal for certain optimality criteria. In our definition of temporal betweenness centrality we use the number of optimal temporal paths as opposed to the number of optimal temporal walks. This is natural for static graphs because static shortest walks are always paths. In the temporal case, this is not always true-it is possible that there is a non-path temporal walk (that visits a vertex multiple times) that arrives at the same time as the foremost temporal path, so the number of foremost temporal paths and foremost temporal walks between two vertices can be different. Consider the graph shown in Figure 1. Clearly, every walk from the left half to the right passes either v 1 or v 2 and since the edges on the right are only present at exactly one time step, every walk going from left to right is a foremost walk. Intuitively, v 1 and v 2 should have very similar, high betweenness scores, whereas v 3 should be close to zero. But if we use walks instead of paths for our definitions, we get a very high number of walks alternating between v 2 and v 3 before arriving on the right side, so v 2 and v 3 would get a high centrality score. We conclude that paths are more suitable than walks for defining temporal betweenness centrality. Furthermore, we distinguish between strict and non-strict temporal paths.
We provide a thorough formal study of the computational complexity landscape of temporal betweenness centrality, altogether obtaining a fairly complete picture concerning the computation of temporal betweenness. We implemented and compared several of our algorithms (in terms of running time, distribution of the betweenness values, and vertex rankings induced by the betweenness values). From our experimental results we derive conclusions for working with temporal betweenness centrality in applications. Our freely available implementations and the experimental investigations are based on our theoretical findings and provide guidelines for future work with one of the perhaps most fundamental network analysis concepts in a temporal context.

Related work.
There is an enormous amount of work on the concept of betweenness centrality in static graphs, as already indicated by the huge citation numbers concerning Brandes path-breaking algorithm [2]. Betweenness centrality was defined in 1977 by Freeman [7]. We refrain from further discussing the static case which is already discussed in many textbooks.
The theory of temporal graphs is comparatively young [12,13,14,20] but strongly grows in many directions. We focus our discussion of related work on temporal walks, paths, and the computation of temporal betweenness centrality.
Bui-Xuan et al. [3] did an early work on algorithms that find optimal temporal paths (called "journeys" there). In particular, they presented algorithms for shortest, fastest, and foremost temporal paths. Afterwards, Wu et al. [32] provided state-of-the-art algorithms for optimal temporal paths. Based on breadth-first search which finds shortest paths in static graphs, Wu et al. showed that shortest, foremost, fastest and reverse-foremost (strict) temporal paths can be found in a similar fashion. Himmel et al. [11] and Casteigts et al. [4] expanded on the work of Wu et al. and studied a more complex variation of temporal paths and walks with constraints on the waiting time in each vertex. Himmel et al. [11] contributed efficient algorithms to find optimal temporal walks but Casteigts et al. [4] showed that finding optimal temporal paths is NP-hard in settings with upper bounds on the waiting time.
While betweenness centrality in static graphs is a well studied concept, the study of betweenness centrality in temporal graphs is rather young. Tang et al. [28] argued that temporal graphs are more suitable to represent the dynamics of social and technical networks and introduced temporal variants of centrality metrics such as closeness and betweenness centrality based on foremost temporal paths. Building on this, Tang et al. [26] used their notion of temporal closeness to analyze the containment of malware in mobile phone networks. Nicosia et al. [21] also discussed temporal variants of betweenness and closeness centralities, as well as other temporal graph metrics. They mostly give an overview on different definitions. Kim and Anderson [16] defined the temporal betweenness centrality of a vertex based on shortest paths in the so-called static expansion, a static directed graph, and give a polynomial-time algorithm for computing the temporal betweeness values. Notably, a path in the static expansion may represent a non-path temporal walk in the corresponding temporal graph. Afrasiabi Rad et al. [23] studied foremost walk temporal betweenness and observed #P-hardness, presented an exponential-time algorithm and conducted corresponding experiments.
We finish with pointing to some more references of the meanwhile already rich literature on computing (variants of) temporal betweenness centrality. Note that the several temporal graph surveys [12,13,14,18] already provide some definitions of temporal betweenness centrality. As mentioned before, most works [1,10,16,23,28] work with temporal walks, not temporal paths. Also, they usually do not make the point of distinguishing between strict and non-strict paths. To the best of our knowledge, there is no work on systematically classifying the computational complexity of temporal betweenness computation.
Organization of the paper. In Section 2 we provide the basic notation used in this paper as well as some preliminary observations. In Section 3 we prove computational hardness for some variants of temporal betweenness (see Table 1) and in Sections 4 and 5 we provide theoretical foundations and algorithms for the remaining temporal betweenness concepts. In Section 6 we present our experimental evaluation of the algorithms described in Section 5. We conclude in Section 7.

Preliminaries & Basic Observations
In this section, we introduce the most important mathematical definitions and terminology used in this paper. We further present some basic observations.

Temporal Graphs and Paths
The fundamental mathematical object we are concerned with are temporal graphs. We only consider undirected temporal graphs. However, temporal paths and walks are implicitly directed because of the ascending time labels. Hence, we need a notion for directed transitions on a temporal path or walk which indicate not only which time edge is used but also in which direction. For any time edge e = ({v, w}, t) we call (v, w, t) the transition from v to w at time step t. We call v the starting point and w the endpoint of the transition. Using this, we can now define temporal walks and temporal paths.
Definition 2.2 (Temporal Walk). A temporal walk W on a temporal graph G from vertex s to vertex z is an ordered sequence of transitions (e 1 , . . . , e k ) ∈ E k such that the endpoint of e i is the starting point of e i+1 and t(e i ) ≤ t(e i+1 ) for each i ∈ {1, . . . , k − 1}. We call a temporal walk strict if t(e i ) < t(e i+1 ) for each i ∈ {1, . . . , k − 1}.
A temporal walk may visit the same vertex more than once. In contrast to that, a temporal path visits each vertex at most once. This is analogous to the definitions for static graphs. For readability, we use the notation v t → w instead of the triple (v, w, t). Since the endpoint of a transition is equal to the starting point of the next one for any walk, we use a shortened notation omitting the doubled vertices. For instance, we denote the "middle" temporal path from s to z in Figure 2 In this example, P is a temporal path since all involved vertices are visited only once. Moreover, P is a strict temporal path because the time labels are strictly ascending.

Optimality of Temporal Paths
In static graphs, shortest paths are a central concept. In temporal graphs, there are different concepts of optimal paths. Figure 2 illustrates three of the most common optimization criteria: shortest, foremost, and fastest [3].
→ z) is foremost, and More formally, we use the following definitions: Definition 2.4. Let G = (V, E, T ) be a temporal graph. Let s, z ∈ V and let W be a temporal walk from s to z.
• W is a shortest walk if there is no walk W ′ from s to z such that W ′ contains less transitions than W .
• W is a foremost walk if there is no walk W ′ from s to z such that W ′ has an earlier arrival time than W .
• W is a fastest walk if there is no walk W ′ from s to z such that the difference between arrival and start time is smaller for W ′ than it is for W .
A temporal path is shortest, foremost, or fastest if it is a shortest, foremost, or fastest temporal walk, respectively. Note that for the optimality criteria "foremost" and "fastest" optimal temporal walks are not necessarily temporal paths. Imagine a temporal graph where all time edges incident to s have the same time label and also all time edges incident to z have the same time label. Then every walk from s to z (if exists) is foremost and fastest, since all walks leave s at the same time and arrive at z at the same time.
Together with the distinction between strict and non-strict, this gives us six different types of optimal temporal paths. In the following, we use the term "⋆-optimal" temporal path, where ⋆ denotes the type.
Next, we introduce terminology and notation for counting optimal temporal paths.
sz is the number of ⋆-optimal temporal paths from s to z.
We define σ (⋆) vv := 1. We further introduce terminology and notation for counting optimal temporal paths that visit a certain vertex or a certain vertex appearance. Definition 2.6. Let v ∈ V be any vertex and let t ∈ [T ] be a time step. Then, is the number of ⋆-optimal paths that pass through v, and is the number of ⋆-optimal paths that pass through v exactly at time step t, i.e., the paths that contain the transition u t → v for some u ∈ V .
We set σ sz /T . Note that these are corner cases where the we can get non-integer values. This technically does not fit the intuition and description that we express numbers of paths with certain properties but this is rather done to keep certain proofs simpler by avoiding to discuss these corner cases explicitely.

Temporal Betweenness Centrality
In static graphs, the betweenness centrality of a vertex measures how often this vertex is passed on shortest paths between pairs of vertices in the graph. Freeman [7] defines the betweenness centrality As we have seen above, there are different notions of optimal paths (i.e., fastest, shortest, foremost) in temporal graphs. Thus, there are several options how to define temporal betweenness centrality based on any of these notions. Moreover, we do not want to assume that there is a temporal path from any vertex to any other vertex in the graph. That is, we assume that there are vertex pairs s, z with σ sz = 0 which we want to leave out when summing over all vertex pairs. To formalize this, we use a connectivity matrix A of the temporal graph: Formally, temporal betweenness with respect to these different concepts of path optimality is defined as follows.
Definition 2.7 (Temporal Betweenness). The temporal betweenness of any vertex v ∈ V is given by: For this paper, we use a slightly different version of temporal betweenness which is defined for vertex appearances and show that the temporal betweenness as defined above can be easily computed from the modified version. This allows us to simplify some of our proofs. We drop the condition that when summing over all vertex pairs, these vertices have to be different from the vertex of which we want to know the betweenness. Formally, we definê We can observe that using the connectivity matrix A for the temporal graph, we can compute the temporal betweenness C Proof. We show the above claim as follows.

Computationally Hard Temporal Betweenness Versions
In this section, we state counting problems closely related to temporal betweenness, including the computation of temporal betweenness itself, and show that they are #P-hard. In particular, we will show that counting all temporal paths is #P-hard for both strict and non-strict paths. The same holds true for foremost and fastest temporal paths, but not for shortest temporal paths. Our hardness results are based on the following two counting problems for which Valiant [29] showed #P-completeness: 2

Paths
Input: A static graph G = (V, E), two vertices s, z ∈ V . Task: Count the number of different paths from s to z in G.

Imperfect Matchings
Input: A bipartite static graph. Task: Count the number of different matchings (of any size) in G.
We use polynomial-time counting reductions 3 from the two problems above to prove that counting problems related to temporal betweennes are #P-hard. More specifically, we show the #Phardness of the following problems: (Strict) Temporal Paths Input: A temporal graph G = (V, E, T ), two vertices s, z ∈ V . Task: Count the number of (strict) temporal paths from s to z in G.

Foremost (Strict) Paths
Input: A temporal graph G = (V, E, T ), two vertices s, z ∈ V . Task: Count the number of foremost (strict) temporal paths from s to z in G.

Fastest (Strict) Paths
Task: Count the number of fastest (strict) temporal paths from s to z in G.
Task: Compute the betweenness centrality of v in G.
As also observed by Afrasiabi Rad et al. [23], for non-strict paths the #P-hard problem Paths is contained as a special case in Temporal Paths, since any static graph can be transformed into an equivalent temporal graph with lifetime T = 1. Furthermore, each temporal path in this instance is also foremost and fastest. Hence, we have the following: The counting problem Strict Temporal Paths is #P-hard as well, but the proof is more technical since strict paths are fundamentally different from static paths, whereas non-strict paths could be regarded as a generalization of static paths, allowing for the simple argument used above. We show the #P-hardness of Strict Temporal Paths by a polynomial-time counting reduction from Imperfect Matchings.
Proof. We reduce from the #P-complete problem Imperfect Matchings [29]. Given a bipartite graph such that the number of non-empty matchings in G is equal to the number of strict temporal paths from a ′ to b ′ in G. An example for the transformation is shown in Figure 3 and it is easy to check that the transformation can be computed in polynomial time.
The temporal edge set E is constructed as follows: For each edge {a i , b j } ∈ E, we create a temporal edge ({a i , b j }, 2 · i). These edges are meant to represent the edges of the original graph and will be called forward-edges. The vertices a i ∈ A are connected to a ′ at time step 2 · i − 1. All b j ∈ B are connected to b at the last time step T . For i > 1 we connect each a i to each b j at time step 2 · i − 1; these edges are drawn dashed in orange in Figure 3 and we will refer to them as back-edges.
We justify the terms forward-edge and back-edge by showing that for any temporal path from a ′ to b ′ , every transition with an even time label goes from an a ∈ A to a b ∈ B (forward) and exactly : Given a static bipartite graph G, we construct a temporal graph G such that the number of matchings in G equals the number of strict paths from a ′ to b ′ in G. In this example, the matching the other way from a b ∈ B to an a ∈ A (back ) for every transition with an odd time label. By construction, each vertex a i ∈ A is incident to time edges with at most two time labels: 2 · i − 1 and 2 · i. Hence, any temporal path containing a transition b j 2·i → a i ends in a i since no time edge with a higher time label will be available. By an anologous argument, back-edges cannot be used forwardly because it is impossible to arrive in a i before time 2 · i − 1.
As a consequence, on any temporal path from a ′ to b ′ , every back-edge is followed by a forwardedge and every forward-edge is followed either by a back-edge or by the final edge to b ′ . Thus, for any matching M = {{a i 1 , b j 1 }, . . . , {a im , b jm }} of size m ∈ N + there is exactly one temporal path from a ′ to b ′ containing exactly the forward edges corresponding to M , and conversely, for each temporal path P from a ′ to b ′ there is exactly one matching corresponding to the forward-edges in P . Thus, the number of non-empty matchings in G equals the number of temporal paths from a ′ to b ′ in G which implies that we have a polynomial-time counting reduction.
Analogously to the case of non-strict paths, the #P-hardness of Strict temporal paths implies the #P-hardness of Strict Foremost Paths and Strict Fastest Paths. We have shown that counting strict and non-strict temporal paths is #P-hard. This allows us to prove this section's main result. Proof. We prove the #P-hardness by a polynomial-time counting reduction from (Strict) Temporal Paths. Let G = (V, E, T ) be a temporal graph with vertices a and b. Let p be the number of (strict) temporal paths from a to b. We construct a temporal graph The construction is illustrated in Figure 4 and can clearly be computed in polynomial time.
By construction, every temporal path from a ′ to b ′ is both fastest and foremost and there are exactly four (fastest/foremost) temporal paths going through v ′ , connecting the pairs (a, b), (a, b ′ ), (a ′ , b), and (a ′ , b ′ ), respectively: T + 2 Figure 4: Given a temporal graph G, we construct a temporal graph G ′ such that we can compute the number of a-b-paths in G from the betweenness of v in G ′ .
We observe that for each of these four pairs, there are p + 1 foremost (and fastest) (strict) temporal paths, and for any other pair of vertices, no temporal path goes through v at all. This allows us to compute p from the temporal betweenness centrality based on foremost (fm) or fastest (fa) temporal paths of v: This implies that we have a polynomial-time counting reduction.

Counting Temporal Paths and Temporal Dependencies
In the previous section, we have shown that computing the temporal betweenness centrality based on fastest or foremost paths is #P-hard. Now we investigate ways to extend the approach of Brandes' algorithm [2] for static graphs to variants of temporal betweenness based on types of optimal temporal paths for which the counting problem is not intractable. In this section we provide the theoretical foundations for designing efficient algorithms to compute temporal betweenness centrality.

Counting Shortest Temporal Paths
We first show how we can count shortest temporal paths efficiently. Our results from Section 3 indicate that this is not possible for the case of foremost and fastest temporal paths.
As it turns out, what we need to count is a slightly different version of shortest temporal paths, which we call t-shortest temporal paths. A temporal path P from s to z is a t-shortest temporal path if it arrives at time t and if there is no temporal path P ′ from s to z which arrives at time t and is shorter than P . We show that similarly to the static case, t-shortest temporal paths P have the property that every prefix is a t ′ -shortest temporal path, where t ′ is the time when the prefix arrives at its last vertex. Formally, we show the following.
be a t-shortest temporal path from s to z.
Proof. Assume that P = (s is not a t ′ -shortest temporal path. Then there is a shorter temporal path P ′′ = (s Lemma 4.1 allows us to formulate a recursive relation of the number of shortest temporal paths. To do this, we need to define the predecessor of a vertex appearance (v, t) on a temporal path as the vertex appearance (w, t ′ ) where the path arrived last, that is, (w, t ′ ) is predecessor of (v, t) on P if and only if P contains the transitions s (v, t) denotes the set of predecessors of (v, t) on ⋆-optimal temporal paths starting at s.
If we want to use the predecessor relation to formulate recursive function, then we need that the relation behaves acyclicly. To show this formally, we define the directed predecessor graph for ⋆-optimal temporal paths starting at some vertex s ∈ V as follows. Given a temporal graph G, the vertex set of the predecessor graph is the set of vertex appearances in G. The arc set is given by the ordered pairs of vertex appearances such that there is a ⋆-optimal temporal path starting at s that arrives in these vertex appearances in that order, that is, we add an arc from a vertex appearance (v, t) to another vertex appearance (w, t ′ ) if (v, t) ∈ P  where It is easy to observe that the predecessor graph is acyclic for all strict optimal temporal path versions, since the time stamps of the vertex appearances are strictly increasing along the arcs of the graph. In the case of t-shortest temporal paths, we show next that this also holds in the non-strict case. Proof. Proof by contradiction. Let G = (V, E, T ) be a temporal graph with source s. Let dist : V × [T ] → N be the function that returns the length of the shortest path in the predecessor graph G (n-t-sh) pre (s) from s to any vertex appearance. Note that for any vertex appearance (v, t ′ ) we have that dist(v, t ′ ) is also the length of a t ′ -shortest temporal path from s to v. Hence, for any vertex appearances (v, t ′ ) and (w, t ′′ ), if the predecessor graph contains the arc ((v, t ′ ), (w, t ′′ )), then dist(v, t ′ ) < dist(w, t ′′ ). Assume that G (n-t-sh) pre (s) contains a cycle C = ((v, t ′ ), . . . , (v, t ′ )). Then dist(v, t ′ ) < dist(v, t ′ ), a contradiction.
By an analogous argument, we get the following, which we need in the next subsection. With the help of this notation and Lemma 4.1 (and Lemma 4.4 for the non-strict case), we can formulate the following recursion for the number of t-shortest temporal paths. Corollary 4.6 (Counting of t-Shortest Temporal Paths). Let s be a source and let z be a vertex with s = z. The number of t-shortest temporal paths (t-sh) from s to z is given by:

Temporal Dependencies
Similar to Brandes [2] we introduce so-called dependencies to obtain an alternative formulation for the betweenness which we then use for the actual computation. Recall the definition of (static) betweenness centrality where σ sz is the number of all shortest paths from s to z and σ sz (v) is the fraction of these paths which pass through v. Brandes [2] calls the latter the pair-dependency of s and z on v. Brandes' central observation is that the betweenness centrality can be computed faster by first computing partial sums of the form the dependency of s on v. He showed that the dependencies obey a recursive relation which can be exploited algorithmically. Both concepts, dependencies and pair-dependencies, naturally generalize to optimal paths in temporal graphs. In some cases, we may be interested in the dependency on a vertex at a specific time instead of the whole lifetime. Hence, we introduce temporal dependencies of vertex appearances: From our definition of the modified temporal betweenness of a vertex appearance it follows that we can use the temporal dependencies to compute it.
Now we state our central result allowing us to design algorithms to compute the temporal betweenness centrality based on shortest temporal paths.
Proof. We start by rewriting the pair-dependency of a vertex appearance as the summed fractions of shortest temporal paths using a specific transition from v to some vertex w at some time step: where δ (sh) sz ((v, t), ({v, w}, t ′ )) is the fraction of shortest temporal paths from vertex s to z that use the transitions v ′ t → v t ′ → w for some v ′ . Note that for the case that z = v there is no vertex appearance (w, t ′ ) such that (v, t) ∈ P sh s (w, t ′ ), hence we need δ (sh) sv (v, t) as an additional summand. Furthermore, we have that Inserting these cases into the double sum above yields the following: The lemma statement now follows immediately.
Lemma 2.8 together with Observation 4.8 show that we can use temporal dependencies to compute temporal betweenness centrality. Lemma 4.9 shows that the temporal dependencies obey a recursive relation and Lemma 4.5 shows that it is cycle-free. This together with Corollary 4.6 allows us to design a polynomial-time algorithm to compute temporal betweenness centrality based on shortest temporal paths. Before we give the specific algorithm description and running time analysis, we describe some other temporal betweenness concepts that can be computed in a similar fashion.

Specialized Optimality Concepts
So far, our results allow us to efficiently compute the temporal betweenness for strict and non-strict shortest temporal paths. For all other of the six canonical variants we have shown computational hardness results in Section 3. In the following, we show that for some specialized optimality concepts for temporal paths, we can also efficiently compute the corresponding temporal betweenness. Specifically, we consider shortest foremost temporal paths and prefix-foremost temporal paths.
Shortest foremost temporal paths. A shortest foremost path is a foremost temporal path that is not longer than any other foremost temporal path. It may not be a shortest temporal path overall, however, as even shorter temporal paths with higher arrival times may exist. Shortest foremost temporal paths can be regarded as temporal paths that prioritize a low arrival time and use a low edge count as a tie-breaker. Definition 4.10. Let s, z ∈ V . A temporal path P from s to z is a shortest foremost temporal path if P is a foremost temporal path from s to z and for all foremost temporal paths P ′ from s to z it holds: |P | ≤ |P ′ |.
We observe that a shortest foremost temporal path is a t-shortest temporal path for the earliest possible arrival time. Hence, our findings in the previous subsection translate very easily to shortest foremost temporal paths.
Prefix foremost temporal paths. Now we consider the class of foremost temporal paths for which every prefix of the temporal path is foremost as well. That is, every vertex that is visited by such a temporal path is visited as soon as possible. These temporal paths are called prefix foremost paths.
Definition 4.11. Let s, z ∈ V . A path P = (e 1 , . . . , e k ) from s to z is a prefix foremost temporal path if P is a foremost path and every prefix P ′ = (e 1 , . . . , e k ′ ), k ′ ≤ k is a foremost temporal path as well.
Wu et al. [32] showed that there is always at least one prefix foremost path between any pair of vertices s and z unless z is not reachable from s at all. We can observe that in the straightforward reduction from Paths that yields Proposition 3.1 we also get that counting nonstrict prefix foremost temporal paths is computationally hard. The main difference between strict and non-strict prefix foremost paths foremost paths is that in the former case, the predecessor relation is acyclic, and in the latter it is not. Intuitively, this is the reason why we get hardness in the non-strict case and tractability for the strict version.
For strict prefix foremost paths, one can show that the counting problem and the computation of the corresponding betweenness are solvable in polynomial time by very similar arguments as for shortest temporal paths. The main difference is that the time stamp of a predecessor is unique, hence we can define the set of predecessors as a set of vertices as opposed to a set of vertex appearances, otherwise the arguments are analogous to the ones used in the proof of Lemma 4.9. This allows us to simplify the recursive function for the temporal dependency for prefix foremost temporal paths which also results in a faster computation.
Proof. We start by rewriting the pair-dependency of a vertex appearance as the summed fractions of prefix foremost temporal paths using a specific transition from v to some vertex w at some time step: , w}) is the fraction of prefix foremost temporal paths from vertex s to z that use the transitions v t → w for some t. Note that for the case that z = v there is no vertex w such that v ∈ P (pfm) s (w), hence we need δ (pfm) sv (v) as an additional summand. Furthermore, we have that Inserting these cases into the double sum above yields the following: The lemma statement now follows immediately.

Algorithms and Running Time Analysis
In the following we give detailed descriptions of the algorithms we use to compute the temporal betweenness variants discussed above. Brandes' algorithm [2] (for static graphs without edge weights) is based on breadth-first search. For each vertex, the Single-Source Shortest Paths problem is solved once. At the end of each iteration, the dependency of the respective s on all other vertices v is added to the betweenness score of s. Our algorithms for temporal betweenness will follow roughly the same structure. Instead of breadth-first search, the appropriate algorithm for the respective temporal path class is used as the base for the algorithm. To describe our algorithm formally, we need the notion of temporal neighborhoods. Shortest (foremost) temporal betweenness. We have shown that the temporal dependencies for shortest (foremost) paths follow a similar recursion as for static graphs.
Algorithm 1 uses a |V | × T -table to store the number of shortest temporal paths to all vertex appearances. The overall structure of the algorithm is similar to Brandes' algorithm [2]-a singlesource-all-shortest-paths traversal from each vertex to all vertex appearances is performed and the count of shortest temporal paths is stored in the aforementioned table. At the end of each iteration, we add the dependencies found for each vertex appearance to the betweenness score of the respective vertex.
In order to count shortest foremost temporal paths instead of shortest temporal paths, only the dependency accumulation needs to be changed: instead of checking whether the paths have minimal length, the algorithm checks for minimal arrival time. Proof. The correctness of Algorithm 1 follows from Lemma 2.8 together with Observation 4.8, which show that we can use temporal dependencies to compute the temporal betweenness, and from Corollary 4.6 and Lemma 4.9 (with Lemma 4.5) since our algorithm dynamically computes the values given by the recursive formulas stated in the lemmas.
It is easy to check that the running time of Algorithm 1 is upper-bounded by |V | (the outer loop in Line 1) times the total number of elements in Q (the loop from Line 10) times the maximum size of a temporal neightborhood (the loop from Line 12). Both the total number of elements in Q and the maximum size of a temporal neightborhood is in O(|V | · T ). The claimed running time follows.
The space consumption of Algorithm 1 is in O(|V | · T + |E|), since we need to store matrices of size |V | · T for the temporal path counts and the temporal dependencies.
Strict prefix foremost temporal betweenness. Algorithm 2 modifies Brandes' algorithm [2] to count strict prefix foremost temporal paths. The overall structure of the algorithm remains the same. Instead of iterating over all neighbors, however, we add add all temporal edges of a vertex into a priority queue (prioritizing early time labels). This allows us to traverse the graph in a time-respecting manner and find the prefix foremost temporal paths.
Notably, since the time labels of predecessors are unique in prefix foremost temporal paths, we do not have to consider vertex appearances in this case. Intuitively, this is the main reason why we can achieve both a faster running time a lower space consumption. Proof. The proof is essentially analogous to the correctness proof for Algorithm 1 but uses Lemma 4.13.
It is easy to check that the running time of Algorithm 2 is upper-bounded by |V | (the outer loop in Line 1) times the size of Q (the loop from Line 9) times the time necessary to dequeue (Line 10). The size of Q is in O(|E|) and the time to dequeue is in O(log |E|). Here, we assume that |V | ≤ |E|. The claimed running time follows.
The space consumption of Algorithm 2 is in O(|E|+|V |) the arrays for the temporal path counts and the temporal dependencies used in the algorithm are all of size |V |.

Experimental Evaluation
In this section, we analyze the running time of our implementations of Algorithm 1 (computing strict and non-strict shortest and shortest foremost temporal betweenness) and Algorithm 2 (computing strict prefix foremost temporal betweenness) on several real-world temporal graphs and we investigate the differences between the five different betweenness concepts our algorithms can compute.

Setup and Statistics
We implemented 4 Algorithm 1 and Algorithm 2 in C++ and carried out experiments on an Intel Xeon E5-1620 computer with four cores clocked at 3.6 GHz and with 64 GB RAM. We did not utilize the parallel-processing capabilities. The operating system was Debian GNU/Linux 6.0.
We used the following freely available data sets for temporal graphs: Physical-proximity net-

Experimental Results
We now discuss the results of our experiments. We analyzed the influence of the temporal betweenness type on the running time, the distribution of the temporal betweenness values, and the ranking of the ten vertices with the hightest temporal betweenness values.
Running time. As indicated by our theoretical running time bounds (see Table 1), Algorithm 1 (computing shortest and foremost shortest betweenness) is several orders of magnitudes slower than Algorithm 2 (computing prefix foremost betweenness). Algorithm 1 solved all instances except for "karlsruhe" and "infectious" (which where not solved within the timeout of three hours) within 45 minutes (keep in mind that Algorithm 1 computes shortest and foremost shortest temporal be- Table 2: Statistics for the data sets used in our experiments. The lifetime T of a graph is the difference between the largest and smallest time stamp on an edge in the graph. The resolution r indicates how often edges were measured. The last three columns state the running times in seconds of our implementation. A -1 indicates that the instance was not solved within three hours.  tweenness simultaneously). Algorithm 2 solved all instances except "karlsruhe" within 30 seconds. We show the specific running times in Table 2.
Impact of temporal betweenness type on the temporal betweenness distribution. In Figure 5 we exemplarily show histograms of the temporal betweenness values of the "highschool-2013" data set, the "facebook-like" data set, and the "primaryschool" data set. We can observe that the temporal betweenness centrality has a power-law-like distribution and the temporal betweenness type does not have a strong influence on the distribution in the "highschool-2013" data set and the "facebook-like" data set (which is the case in most data sets). In the "primaryschool" data set however, the distributions for non-strict shortest and strict shortest temporal betweenness are very similar but the other ones are quite different from each other.
Impact of temporal betweenness type on the vertex ranking. In Table 3 we present Kendall's tau correlation measure 6 [17] for each pair of vertex rankings induced by the different temporal betweenness versions. For the temporal betweennes variants "shortest" and "shortest foremost" we can observe that their respective non-strict and strict variants produce very similar rankings. We can further see that the betweenness variants "non-strict shortest foremost", "strict Middle: Temporal betweenness histogram of "facebook-like" data set. The y-axis is on a log-scale. Bottom: Temporal betweenness histogram of "primaryschool" data set. The temporal betweenness types from left to right are: non-strict shortest, non-strict shortest foremost, strict shortest, strict shortest foremost, strict prefix foremost. Table 4: Size of the intersection of each pair of sets containing the ten vertices with highest temporal betweenness values.
These findings are supported by the pairwise comparisons of the sets of the ten vertices with the largest temporal betweenness values, which are presented in Table 4. Notably, the "primaryschool" has quite different top ten vertex sets for all pairs of betweenness variants that do not fall into the above mentioned pairings. We can also observe that "non-strict shortest" and "strict prefix foremost" produce the most dissimilar vertex rankings and top ten sets.

Conclusion
We investigated several variants of temporal betweenness centrality based on the various optimization criteria for temporal paths. We have shown a surprising discrepancy in their computational complexity: while some variations are #P-hard, others can be computed in polynomial time. More specifically, we found that counting foremost, and thus fastest paths, is #P-hard, and in turn, the computation of the corresponding betweenness centrality scores is #P-hard as well. In contrast to that, one can count shortest and shortest foremost temporal paths in polynomial time both for strict and non-strict paths. In the case of prefix-foremost paths, however, we found a polynomialtime algorithm for the strict version, whereas the non-strict version is again #P-hard. An intuitive explanation for this behavior might be that our algorithms strongly rely on a recursive formulation for the so-called temporal dependencies, which in turn requires that the predecessor relation of optimal temporal paths is acyclic and that prefixes of optimal temporal paths are also optimal. For all optimal temporal path types for which we show computational hardness of the corresponding counting problem, one of the two mentioned requirements is not given.
As to challenges for future research, one direction is to attack the temporal betweenness centrality variants which we have shown to be computationally hard by means of approximation algorithms or the development of fixed-parameter algorithms (e.g. for some structural graph parameters of the underlying graph). Roughly in the same direction would be to undertake a closer study of the special structures of real-world networks that might be algorithmically exploitable. A line of research directly motivated by our experiments would be to explore how to decrease the memory consumption of our algorithms-the practical limitations seem to mainly come from the high space consumption, at some point leading our algorithms to do a lot of paging. Specifically, our algorithm for shortest and shortest foremost temporal betweenness stores dependency and path count values for every vertex-time step combination. This is major difference to the static algorithm of Brandes [2] which is less vulnerable in this respect.
On the experimental side, we can observe that the temporal betweenness type does not have a strong impact on the distribution of the betweenness values. When comparing the vertex rankings produced by the betweenness values we can observe that there is little difference between strict and the respective non-strict variants. Furthermore, "shortest foremost" and "prefix foremost" yield similar results, while the strict prefix foremost temporal betweenness values can be computed significantly faster.
It would also be interesting to compare our results to results obtained by static expansion based temporal betweenness algorithms (both in terms of running time and betweenness values). We also believe it would be very enlightening to compare the betweenness values of the two tractable variants of temporal betweenness based on foremost paths (shortest foremost and prefix foremost) to the betweenness values for temporal betweenness based on foremost temporal paths (which is intractable).


Run Away From your Teacher: Understanding BYOL by a Novel Self-Supervised Approach

Recently, a newly proposed self-supervised framework Bootstrap Your Own Latent (BYOL) seriously challenges the necessity of negative samples in contrastive learning frameworks. BYOL works like a charm despite the fact that it discards the negative samples completely and there is no measure to prevent collapse in its training objective. In this paper, we suggest understanding BYOL from the view of our proposed interpretable self-supervised learning framework, Run Away From your Teacher (RAFT). RAFT optimizes two objectives at the same time: (i) aligning two views of the same data to similar representations and (ii) running away from the model's Mean Teacher (MT, the exponential moving average of the history models) instead of BYOL's running towards it. The second term of RAFT explicitly prevents the representation collapse and thus makes RAFT a more conceptually reliable framework. We provide basic benchmarks of RAFT on CIFAR10 to validate the effectiveness of our method. Furthermore, we prove that BYOL is equivalent to RAFT under certain conditions, providing solid reasoning for BYOL's counter-intuitive success.

INTRODUCTION
Recently the performance gap between self-supervised learning and supervised learning has been narrowed thanks to the development of contrastive learning (Chen et al., 2020b;a;Tian et al., 2019;Chen et al., 2020b;Sohn, 2016;Zhuang et al., 2019;He et al., 2020;Oord et al., 2018;Hadsell et al., 2006). Contrastive learning distinguishes positive pairs of data from the negative. It has been shown that when the representation space is l 2 -normalized, i.e. a hypersphere, optimizing the contrastive loss is approximately equivalent to optimizing the alignment of positive pairs and the uniformity of the representation distribution at the same time (Wang & Isola, 2020). This equivalence conforms to our intuitive understanding. One can easily imagine a failed method when only either of the properties is optimized: aligning the positive pairs without uniformity constraint causes representation collapse, mapping different data all to the same meaningless point; scattering the data uniformly in the representation space without aligning similar ones yields no more meaningful representation than random.
The proposal of Bootstrap Your Own Latent (BYOL) challenges the consensus that negative samples are necessary to contrastive methods (Grill et al., 2020). BYOL trains the model (online network) to predict its Mean Teacher (MT, Tarvainen & Valpola (2017)) on two differently augmented views of the same data. There is no explicit constraint on uniformity in BYOL, while the expected collapse never happens. What's more, it reaches the SOTA performance on the downstream tasks. Although BYOL has been empirically proven to be an effective self-supervised learning approach, the mechanism that keeps it from collapse remains to be explored.
In this paper, we explain how BYOL works through another interpretable learning framework which leverages the MT in the exact opposite way. Based on a series of theoretical derivation and empirical approximation, we build a new self-supervised learning framework, Run Away From your Teacher (RAFT), which optimizes two objectives at the same time: (i) minimize the representation distance between two samples from a positive pair and (ii) maximize the representation distance between the online and its MT. The second objective of RAFT incorporates the MT in a way exactly opposite to BYOL, and it explicitly prevents the representation collapse by encouraging the online to be different from its history. Moreover, we empirically show that the second objective of RAFT is a more effective and consistent regularizer for the alignment loss, which makes RAFT more favorable than BYOL. Finally, we understand some crucial behaviors of BYOL by theoretically proving that BYOL is a special form of RAFT when certain conditions and approximation hold. This proof explains why collapse does not happen in BYOL, and also makes the performance of BYOL an approximate guarantee for RAFT.
The main body of the paper is organized in the same order of how we explore the properties of BYOL and establish RAFT based on them (refer to Appendix A for more details). In section 3, we investigate the phenomenon that BYOL fails to work when the predictor is removed. In section 4, we establish two disentangled objectives out of BYOL by upper bounding. Based on that, we propose RAFT due to its stronger regularization effect and its accordance with our knowledge. In section 5, we prove that, as a representation learning framework, BYOL is a special form of RAFT under certain achievable conditions.
In summary, our contributions are listed as follows: • We present a novel self-supervised learning framework RAFT that minimizes the alignment and maximizes the distance between the online network and its MT. The motivation of RAFT conforms to our understanding of balancing alignment and uniformity of the representation space, and thus could be easily extended and adapted to future problems.
• We equate two seemingly opposite ways of incorporating MT in contrastive methods under certain conditions. By doing so, we partially explain why BYOL doesn't collapse and provide a novel framework to understand BYOL, under which two questions need to be answered in the future: (i) on what condition is the upper bound loss of BYOL equivalent to BYOL itself? (ii) how does the predictor help optimize the representation uniformity? 2 BACKGROUND AND RELATED WORK

CONTRASTIVE LEARNING BACKGROUND
Contrastive methods relies on the assumption that two views of the same data point share the information, and thus creates a positive pair. By separating the positives and the negatives, the neural network trained by the algorithm learns to extract the most useful information from the data and performs better on the downstream tasks (Chen et al., 2020b;a;Tian et al., 2019;Chen et al., 2020b;Sohn, 2016;Zhuang et al., 2019;He et al., 2020;Oord et al., 2018). Typically, the algorithm uses the InfoNCE objective: where (x, x + ) are sampled from the positive pair distribution P pos , which is built by a series of data augmentation functions [ref]. The negative samples {x − i } K are i.i.d sampled for K times from the data distribution X ; function h(x, y) measures the similarity between two input data (x, y). Empirically for the sake of symmetry, the measurement function h(x, y) = d(f (x), f (y)) has an encoder f (·) and a similarity metric d(·, ·) evaluating how close the two representations are.
Wang & Isola (2020) puts the contrastive learning under the context of hypersphere and formally showcases that optimizing the contrastive loss is equivalent to optimizing two metrics of the encoder network when the size of negative samples K is sufficiently large: the alignment of the two augmented views of the same data and the uniformity of the representation population. We introduce the alignment objective and uniformity objective as follows.
Definition 2.1 (Alignment loss) The alignment loss L align (f, P pos ) of the function f over positivepair distribution P pos is defined as: where the positive pair (x 1 , x 2 ) are two augmented views of the same input data x ∼ X , i.e. (x 1 , x 2 ) = (t 1 (x), t 2 (x)) and t 1 ∼ T 1 , t 2 ∼ T 2 are two augmentations. For the sake of simplicity, we omit P pos and use L align (f ) in the following content. Definition 2.2 (Uniformity loss) The loss of uniformity L uniform (f ; X ) of the encoder function f over data distribution X is defined as where t > 0 is a fixed parameter and is empirically set to t = 2. To note here, the vectors in the representation space are automatically l 2 -normalized, i.e. f (x) f (x)/ f (x) 2 , as we limit the representation space to a hypersphere following Wang & Isola (2020) and Grill et al. (2020) and the representation vectors in the following context are also automatically l 2 -normalized, unless specified otherwise. Wang & Isola (2020) has empirically demonstrated that the balance of the alignment loss and the uniformity loss is necessary when learning representations through contrastive method. The rationale behind it is straightforward: L align provides the motive power that concentrates the similar data, and L uniform prevents it from mapping all the data to the same meaningless point.

BYOL: BIZARRE ALTERNATIVE OF CONTRASTIVE
A recently proposed self-supervised representation learning algorithm BYOL hugely challenges the common understanding that the alignment should be balanced by negative samples during the contrastive learning. It establishes two networks, online and target, approaching to each other during training. The online is trained to predict the target's representations and the target is the Exponential Moving Average (EMA) of the parameters of the online. The loss of BYOL at every iteration could be written as where two vectors in representation space are automatically l 2 -normalized. f θ is the online encoder network parameterized by θ and q w is the predictor network parameterized by w. x ∼ X is the input sampled from the data distribution X , and t 1 (x), t 2 (x) are two augmented views of x where t 1 ∼ T 1 , t 2 ∼ T 2 are two data augmentations. The target network f ξ is of the same architecture as f θ and is updated by EMA with τ controlling to what degree the target network preserves its history ξ ← τ ξ + (1 − τ )θ.
From the scheme of BYOL training, it seems like there is no constraint on the representation uniformity, and thus most frequently asked question about BYOL is how it prevents the representation collapse. Theoretically, we would expect that when the final convergence of the online and target is reached, L BYOL degenerates to L align and therefore causes representation collapse, while this speculation never happens in reality. The motivation of understanding why and how BYOL avoids the representation collapse is the starting point of this paper.

MEAN TEACHER
There is one type of semi-supervised learning method that BYOL constantly reminds people of, Mean Teacher (MT) (Tarvainen & Valpola, 2017;Laine & Aila, 2016). Like BYOL, MT is also of Teacher-Student (T-S) framework, where the teacher network is also the EMA of the student network. The additional consistency loss between the teacher and student is applied to the supervised signals. There has been a lot of work demonstrating the efficacy of MT (Athiwaratkun et al., 2019;Novak et al., 2018;Chaudhari et al., 2019), among which the major conclusion states that the consistency loss between the student and its MT acts as a regularizer for better generalization. The proven properties of MT might lead us to focus on how the online network's learning from MT effectively regularizes L align in BYOL. In this paper, however, our newly proposed method leverages the MT in an opposite way, which provides a novel perspective of estimating the efficacy of the MT in the self-supervised learning approaches. When taken out the predictor, the training loss quickly converges to 0 (red curve, BYOL-NP). Replacing the MLP-predictor (blue curve, BYOL-MLPP) with the linear predictor (green curve, BYOL-LP) will not cause the collapse even though I is an apparent solution for collapse. Furthermore, initializing the linear predictor with I forces the loss quickly approaching to 0 at beginning, while it recovers from the seemingly collapse after 10-20 epochs of training (orange curve, BYOL-LPI). (b) Evolution of the representation uniformity. BYOL with predictor consistently optimizes the uniformity of the representation distribution even though the uniformity is not explicitly included in the loss term. One interesting fact to note here is that the uniformity loss is optimized with a constant rate with linear predictor (green curve, BYOL-LP; orange curve, BYOL-LPI) after certain phase of training. (c) linear evaluation protocol on CIFAR10. Different structures of the predictor provide close performance on the downstream classification task.

ON-AND-OFF BYOL: FAILURE WITHOUT PREDICTOR
We start by presenting a property of BYOL: its success heavily relies on the existence of the predictor q w . The experimental setup of this paper is listed in Appendix B. The performance of BYOL original model, whose predictor q w is a two-layer MLP with batch normalization, evaluated on the linear evaluation protocol (Kolesnikov et al., 2019;Kornblith et al., 2019;Chen et al., 2020a;He et al., 2020;Grill et al., 2020) reaches 68.08 ± 0.84%. When the predictor is removed, the performance degenerates to 20.92 ± 1.29%, which is even lower than the random baseline's 42.74 ± 0.41%. We examine the speculation that the performance drop is caused by the representation collapse both visually (refer to Appendix E for the qualitative illustration on the representation collapse) and numerically. Inspired by Wang & Isola (2020), we use L uniform (f θ ; X ) to evaluate to what degree the representations are spread on the hypersphere and L align (q w • f θ ) to evaluate how the similar samples are aligned in the representation space. The results in Table 1 show that with the predictor, BYOL optimizes the uniformity of the representation distribution. On the contrary, when taken away the predictor, the alignment of two augmented views is overly optimized and the uniformity of the representation deteriorates (Figure 1), therefore we conclude the predictor is essential to the collapse prevention in BYOL.
One reasonable follow-up explanation on the efficacy of the predictor may consider its specially designed architecture or some good properties brought by the weight initialization, which makes it hard to understand the mechanism behind it. Fortunately, after replacing the current predictor, two-layer MLP with batch normalization (Ioffe & Szegedy, 2015), with different network architectures and weight initializations, we find that there is no significant change either on linear evaluation protocol or on the model behavior during training (Table 1 & Figure 1). We first replace the complex structure with linear mapping q w (·) = W (·). This replacement provides a naive solution to representation collapse: W = I, while it never converges to this apparent collapse. Surprisingly enough when we initialize W with the apparent collapse solution I, the model itself seems to have a self-recovering mechanism even though it starts off at a poor position: the loss quickly approaches to 0 and the uniformity deteriorates for 10-20 epochs and suddenly it deflects from the collapse and keeps on the right track. We conduct a theoretical proof that a randomly initialized linear predictor prevents the (more strict form of) representation collapse by creating infinite non-trivial solutions when the convergence is achieved (refer to Appendix H), while we fail to correlate the consistently optimized Table 1: Evaluation results of BYOL variants on CIFAR10 after 300 epochs of training, used as evidence supporting the proposal of RAFT. (α, β) = (1, 1) are set in BYOL and RAFT. L align (q w • f θ ) and L uniform (f θ ) are evaluated by averaging the last 10 epochs of training. We highlight the overly optimized L align and failed L uniform in this table. For the accuracy on the linear evaluation protocol, we also only highlight the ones that underperform the random baseline.
Model uniformity with the presence of the predictor, which indicates that a deeper rationale needs to be found.
There are a lot of methods and frameworks that are analogous to BYOL: self-distillation in the field of knowledge distillation (Hinton et al., 2015;Furlanello et al., 2018;Mobahi et al., 2020;Zhang & Sabuncu, 2020), Deep Q Network in reinforcement learning (Mnih et al., 2013), and Mean Teacher in semi-supervised learning (Tarvainen & Valpola, 2017). The reason why BYOL's relying on the presence of the predictor is dissatisfactory lies in the fact that when the predictor is removed, BYOL remains to be of the Teacher-Student framework but it fails to work. This inconsistent behavior yet under the same theoretical framework drives us to explore the mechanism behind BYOL, and we further argue that any theoretical analysis on understanding BYOL shall solve the question how the predictor makes BYOL work.

DISENTANGLE THE BYOL LOSS BY UPPER BOUNDING
Analyzing L BYOL is hard, since it only has one single mean squared error term and there are many factors entangled within it, e.g., two augmented views of the same data, predictor, and the EMA updating rule. Inspired by the Bias-Variance decomposition on squared loss (Geman et al., 1992), we extract the alignment loss by subtracting and adding the same term q w (f θ (t 2 (x))) and further yield the upper bound of L BYOL . Definition 4.1 (Cross-model loss) The cross-model loss L cross-model (f, g; X ) of the function f and g over the data distribution X is defined as Definition 4.2 (BYOL loss) The BYOL loss L BYOL is defined as where α, β > 0 are constants, P pos is defined in Eq. 2 and X 2 = T 2 (X ) is the distribution of the augmented data. For the sake of simplicity, we use L align (q w • f θ ) to denote L align (q w • f θ ; P pos ) in the following content. For the sake of symmetry, we use L cross- ] to compute the cross-model loss. The Mean Teacher f ξ is the EMA of the encoder f θ . In BYOL, the loss is computed by minimizing the distance between the prediction of one view x 1 and another view x 2 's representation generated by the MT. In RAFT, we optimize two objectives together: (i) minimize the representation distance between two samples from a positive pair and (ii) maximize the representation distance between the online network and its MT.
Theorem 4.1 (L BYOL is an upper bound of L BYOL ) L BYOL is an upper bound of L BYOL if we ignore the scalar multiplication. Concretely speaking, for any given constants α, β > 0, we have Proof Please refer to Appendix F.
Ideally, minimizing L BYOL would yield similar performance as minimizing L BYOL . We exemplify the legitimacy of L BYOL by setting (α, β) = (1, 1). In Table 1, the performance of BYOL and BYOL are close to each other with respect to three metrics: alignment, uniformity, and downstream linear evaluation protocol, regardless of the form of predictors. When the predictor is linear mapping, the performance differences between them are subtle. Besides, when the predictor is removed, the representation collapse also happens to BYOL . So we conclude that optimizing L BYOL is almost equivalent to L BYOL , while we leave the question that under what condition this approximate equivalence holds to the future. In spite of the performance similarity, L BYOL is of a more disentangled form than L BYOL and therefore we focus on studying the former instead of the latter.
The new objective consists of two terms: the first term L align minimizes the representation distance between samples from a positive pair and has already been shown crucial to the successful contrastive methods (Wang & Isola, 2020). Intuitively, it provides the motive power to concentrate similar data in the representation space. Based on the form of BYOL and the study on the alignment-uniformity framework, we conclude that MT is used to regularize the alignment loss. This perspective of two terms regularizing each other is crucial to our analysis and improvement of the original BYOL framework. Understanding why BYOL works without collapse is approximately equivalent to understanding how minimizing L cross-model (q w • f θ , f ξ ) effectively regularizes the alignment loss, or even actively optimizes the uniformity.

RAFT: RUN AWAY FROM YOUR TEACHER
The major difficulty of correlating L cross-model with L uniform is that their optimization intentions are not only irrelevant, but somewhat opposite. Minimizing the cross-model loss asks the network to produce close representations for certain inputs, while optimizing the uniformity loss requires it to produce varying representations. The disparity residing in the form pushes us to question the original motivation of BYOL: do we really want the online network to approach to the Mean Teacher? To test our suspicion, we minimize , and we find it works as well. This bizarre phenomenon will be explained in Section 5. Removing the predictor, we observe that although mini- In contrastive methods, the most favorable objective actively optimizes uniformity, including both BYOL and RAFT with predictor. The secondly favorable objective is the effective regularizer of alignment. RAFT remains to restrain alignment loss without predictor, while BYOL fails to do so.
fails to yield better representation than the random baseline, it prevents the overly-optimized alignment loss, i.e. it works as an effective regularizer for the alignment loss, while minimizing L cross-model (f θ , f ξ ) does not.
Based on the conclusion above and law of Occam's Razor, we propose a new self-supervised learning framework, Run Away From your Teacher (RAFT), which optimizes two learning objectives simultaneously: (i) minimize the alignment loss of two samples from a positive pair and (ii) maximize the distance between the online network and its MT (refer to Figure 2 and Algorithm 1). Definition 4.3 (RAFT loss) The RAFT loss L RAFT is defined as where α, β > 0 are constants and other components follow the Definition 4.2.
Compared to BYOL and BYOL , RAFT better conforms to our knowledge and is a conceptually non-collapsing algorithm. There has been a lot of work demonstrating that weight averaging is roughly equal to sample averaging (Tarvainen & Valpola, 2017), thus if two samples' representations are close to each other at the beginning and their initial updating directions are opposite, then RAFT consistently separates them in the representation space. All the forms of loss terms could be classified into three categories: uniformity optimizer, effective regularizer for alignment loss, and others ( Figure 3). According to our experiments, when the predictor is removed, running away from MT remains an effective regularizer for the alignment loss while BYOL's running towards MT fails to do so, thus RAFT is of more unified and consistent form. In summary, our proposed learning framework RAFT is completely based on the intention of solving the inconsistency of the predictor in BYOL, and it's better than BYOL in threefold: • Consistency. Compared to BYOL, our newly proposed method has an effective regularizer for the alignment loss regardless of the presence of predictor. • Interpretability. Mean teacher uses the technique of weight averaging and thus could be considered as an approximate ensemble of the previous versions of the model. Running away from the mean teacher intuitively encourages the diversity of the representation, which is positively correlated to the uniformity. • Disentanglement. The learning objective is decoupled into aligning two augmented views and running away from the mean teacher, and hence could be independently studied.
We will discuss the relationship between RAFT and BYOL in the next section, and we find BYOL is a special form of RAFT under certain conditions, which makes the performance of BYOL a guarantee of the effectiveness of RAFT. We provide benchmarks of alignment, uniformity, and downstream linear evaluation performance on CIFAR10 (Table 3). We discover that balancing the alignment loss and the cross-model loss is not an easy job with the predictor taken away. The imbalance between the alignment loss and the cross-model loss would lead to representation collapse or over-regularized alignment where every data is randomly projected. One interesting research direction is to study the efficacy of the predictor. The reason why it helps the two terms to achieve an equilibrium is left to be answered. In this respect, RAFT is a more effective regularizer, while the uniformity optimization holds no huge difference from BYOL -NP. (c) Evolution trace of RAFT-LP. With the linear predictor, on the contrary to RAFT-NP, the uniformity is optimized consistently during training, which implies deeper rationale of the existence of predictor.

UNDERSTANDING BYOL VIA RAFT
In Section 4.1 we derive an upper bound L BYOL of L BYOL and explicitly extract two terms L align and L cross-model . In BYOL , two terms are simultaneously minimized, while in RAFT, we minimize L align but maximize L cross-model instead. To clearly distinguish the difference between the two objectives, we rewrite them as following: where α, β > 0 are constants.
In form, L RAFT and L BYOL seem to evolve in opposite optimizing direction on the second term, but the empirical study has shown that both of them work. How can two opposite optimization goals produce similar effect? Since RAFT is a conceptually working method, we analyze the mechanism of BYOL by establishing the equivalence between the parameters of BYOL and RAFT under mild conditions. Theorem 5.1 (One-to-one correspondence between BYOL and RAFT) There is a one-to-one correspondence between parameter trajectories of BYOL and RAFT when the following three conditions hold: i. the representation space is a hypersphere; ii. the predictor is a linear transformation, i.e. q w (·) = W (·); iii. only the tangential component of the gradient on the hypersphere is preserved.
Proof We prove the theorem by construction. For the detail, please refer to Appendix G.
Remark The third condition conforms to the property of the hypersphere representation space and is easy to achieve. One can preserve only the tangential gradient by slightly modifying the loss.
For example, suppose the representation of the MT isz and the representation of the input is z which are both normalized, the cross-model loss z − z 2 2 can revised as z − λz 2 2 /λ, where λ = sg( z,z ) stands for stopping gradient of the inner product of z andz. Our experiments in Table 1 demonstrates that the condition of the tangential component of the gradient doesn't turn any of the algorithms including BYOL, BYOL and RAFT into a collapsed one.
In Theorem 1, we show that optimizing L BYOL with initial parameters (θ (0) , W (0) ) is equivalent to optimizing L RAFT with initial parameters (θ (0) , −W (0) ) when the aforementioned three conditions are satisfied. This equivalence demonstrates that the final encoder network f θ and f θ equal to each other. Therefore we conclude that, as representation learning framework, BYOL is equivalent to our newly proposed RAFT. From a geometric point of view, the optimization process is the data points moving in the representation space under the guidance of the training loss. The loss function measures the potential energy of the parameters, and the gradient with regard to the data points is the motive force. If the representation space is a hypersphere as in BYOL, then the tangential force, i.e. the tangential component of the gradient, is the only key to scattering or concentrating the data points in the representation space. By the central symmetry of the hypersphere, clockwise and counterclockwise moving directions are equivalent to some extent, for example, pushing a point by π/2 and pulling it by π/2 on the 2-dimensional sphere causes the same effect.
The equivalence between BYOL and RAFT offers us a direct way to understand some strange phenomena we observe which are also reported in the original BYOL paper. Firstly, the non-collapse of BYOL is explained, since the RAFT is an intuitively and practically working algorithm. The equivalence of BYOL and RAFT when predictor is linear helps us understand why BYOL is an effective self-supervised learning algorithm. It also explains our initial question why BYOL fails to avoid representation collapse without the predictor: removing the predictor means fixing W = I, which breaks the RAFT's designing principle of running away from the MT. Secondly, though the BYOL's optimization procedure is of the form that two models approaching to each other, there has been no report of convergence in the original paper. The established equivalence perfectly explains it. RAFT incorporates the MT in an extremely dynamic way since it continuously varies from the history models, thus there would be no convergence of the data points. So does the parameters.

CONCLUSION AND FUTURE WORK
In this paper, we address the problem of why the newly proposed self-supervised learning framework Bootstrap Your Own Latent (BYOL) works without negative samples. By decomposing, upper bounding and approximating the original loss of BYOL, we establish another interpretable selfsupervised learning method, Run Away From your Teacher. We show that RAFT contains an explicit term that prevents the representation collapse and we also empirically validate the effectiveness of RAFT. By constructing a one-to-one correspondence from RAFT to BYOL (variant of BYOL), we successfully explain the mechanism behind BYOL that makes it work and therefore implies the huge potential of our proposed RAFT. Based on the observation and the conclusion, here we have several suggestions for future work: Theoretical guarantees of RAFT. Though we have intuitively explained why running away from the MT is an effective regularizer, we don't provide theoretical guarantees why optimizing RAFT would be favorable with respect to the representation learning. In future, one can try to relate RAFT to the theory of Mutual Information (MI) maximization (Belghazi et al., 2018;Tschannen et al., 2019), as the training objective of contrastive learning InfoNCE has been proven to be a lower bound of the MI (Poole et al., 2019). One detail should be noticed when attempting to correlate RAFT with MI maximization. Even though RAFT is an effective regularizer, it fails to yield good-quality representations when the predictor is removed, thus any theoretical proof on the effectiveness of RAFT should well explain the mechanism behind this extra predictor.
On the efficacy of the predictor. It has become a popular and almost standardized method to add an extra MLP on top of the network in contrastive learning methods (Chen et al., 2020a;b;Grill et al., 2020), while most of the work adopts this method as a special trick without considering the effect this MLP brings to the algorithm. In this paper, however, we find that this extra MLP may bring some unexpected properties to the original training objective: although the representations are optimized by disparate motivations (in our paper, BYOL running towards MT and RAFT running away from MT), the encoder network is trained to be exactly the same. This observation indicates that the mechanism of the extra MLP to the network needs to be further studied.

A MAIN THREAD OF PAPER
The proposal of RAFT is based on a series of theoretical derivation and empirical approximation. Therefore the logic chain of our paper is fundamental to the legitimacy of our explanation on BYOL and the superiority of our newly proposed RAFT. Here we organize our main thread in the same order as the sections, to provide a clear view with readers.
In Section 3, • As a learning framework, BYOL does not consistently work. It heavily relies on the existence of the predictor. We want to understand why this inconsistency exists.
• The architecture of the predictor doesn't affect the collapse of BYOL, the fact that the linear predictor q w (·) = W (·) prevents collapse will be used as a crucial condition in Section 5.
In Section 4.1, • We showcase that minimizing L BYOL is close to minimizing L BYOL in terms of alignment, uniformity, and linear evaluation protocol, which indicates that understanding the behavior of optimizing BYOL's upper bound is approximately equivalent to understanding BYOL.
In Section 4.2, works as well, which has the exact opposite way of incorporating the cross-model loss to BYOL .
• Based on the observation above, we propose a new self-supervised learning approach Run Away From your Teacher, which regularizes L align (q w • f θ ) by maximizing L cross-model (q w • f θ , f ξ ). Compared with BYOL, RAFT accords more with our common understanding.
• Additional experiments show that without predictor, BYOL fails to regularize L align (f θ ), let alone optimizing uniformity. On the contrary, although not able to actively optimize uniformity either, RAFT's maximizing L cross-model (f θ , f ξ ) continues to be an effective regularizer for L align (f θ ), which makes it more favorable (Figure 3).
In Section 5, • We prove that when the predictor is linear (q w = W ) and the representation space is a hypersphere where only the tangential component of gradient is preserved during training, minimizing L cross-model (W • f θ , f ξ ) and maximizing it obtain the same encoder f θ .
• Based on the equivalence above, we conclude that BYOL is a special case of RAFT under conditions above. The equivalence established helps understanding several counterintuitive behaviors of BYOL.

B EXPERIMENTAL SETUP
Dataset Our main goal is to unravel the mystery why BYOL doesn't collapse during training and to solve the predictor-inconsistency. The most important metric is whether the algorithm collapses or not, and we don't target on developing a more powerful self-supervised learning algorithm that surpasses SOTA on large dataset. In this repsect, we limit our experiments to the scope of the CIFAR10 dataset. Each image is resized from 32 × 32 to 96 × 96. This change is the consequence of the tradeoff between the effect of the data augmentation and batch size: larger size of the image would allow more subtle and informative data augmentation scheme while it will reduce the training batch size, which has already been empirically shown is harmful to the model performance.
Model architecture In our experiments, the model is composed of three stages: an encoder f θ that adopts the ResNet18 architecture (without the classifier on top); a projector g θ that is comprised of a linear layer with output size 512, batch normalization, rectified linear units (ReLU), and a final linear layer with output size 128; a predictor q w that is comprised of the same architecture as the projector but without the batch normalization.
Training We adopt the same data augmentation scheme that is used in Chen et al. (2020a) and Grill et al. (2020) and train the BYOL on the training set for 300 epochs with batch size 128 on 3 random seeds. The objective of training is specified accordingly and the model is trained on the Adam optimizer with learning rate 3 × 10 −4 (Kingma & Ba, 2014). Unless stated otherwise, we update the target network with the EMA rate 4 × 10 −3 without the cosine smoothing trick.
Evaluation After training, we evaluate the encoder's performance on the widely adopted linear evaluation protocol: we fix the parameter of the encoder and we train another linear classifier on top of it using all the training labels for 100 epochs with learning rate 5 × 10 −4 . The final classification accuracy indicates to what degree the representations of the same class concentrate and the representations of the different class separate, and thus tells the quality of the representation.   TanRAFT-LP RAFT with Linear Predictor, preserving only the Tangential gradient Table 3: Evaluation results of RAFT on CIFAR10. α and β represents the weight of L align (q w • f θ ), and L cross-model (q w •f θ , f ξ ), i.e. L = αL align (q w •f θ )+βL cross-model (q w •f θ , f ξ ). All the quantifiable metrics are evaluated after 300 epochs of training of the training set of CIFAR10. Compared to BYOL , our proposed RAFT is better in terms of the effectiveness of regularizing the L align .

C TABLES
Model

D ALGORITHMS
Algorithm 1: RAFT: Run Away From your Teacher Inputs : X , T 1 , and T 2 set of images and distributions of transformations θ and f θ model parameters and encoder w and q w predictor parameters and predictor ξ and f ξ MT parameters and MT optimizer optimizer, updates online parameters using the loss gradient K and N total number of optimization steps and batch size {τ k } K k=1 and {η k } K k=1 target network update schedule and learning rate schedule We project the representation f θ (x) to 2-D dimension using PCA (Wold et al., 1987) and then normalize to a unit sphere. The width of the circle shows the density of the data points that are projected to that particular position. Two dots residing on each side of the blue line across the circle represents two augmented views of the same data.

F PROOF OF BYOL UPPER BOUNDING
In this section, we provide how we derive the upper bound of L BYOL . For the sake of simplicity, without loss of rigor, we use t 1 = t 1 (x) to represent the transformed input x.
By applying the Cauchy-Schwarz's inequality to Eq. 12, we yield: which stands for any λ > 0, where the positive-pair distribution P pos is modeled by the chain rule of the conditional probability: For any given pair α, β > 0, we let λ = β/α and substitute it back to Eq. 13, yielding and as an optimization objective, we have Therefore we have proven that L BYOL as optimization objective is the upper bound of L BYOL .
To note here, one can subtract and add a different term f ξ (x 1 ) to form the alignment loss on the side of MT f ξ , while it doesn't help to solve the problem since the alignment constraint on the side of MT doesn't generate gradients.

G PROOF OF ONE-TO-ONE CORRESPONDENCE BETWEEN BYOL AND RAFT
Theorem (One-to-one correspondence between BYOL and RAFT) There is a one-to-one correspondence between parameter trajectories of BYOL and RAFT when the following three conditions hold: i. the representation space is a hypersphere; ii. the predictor is a linear transformation, i.e. q w (·) = W (·); iii. only the tangential component of the gradient on the hypersphere is preserved.
Without losing generality, suppose that x 1 = t 1 (x), x 2 = t 2 (x) where x is an arbitrary input and batch size is 1, and (α, β) = (1, 1). We set BYOL and RAFT with initial parameters (θ , W ) = (θ (0) , W (0) ) and (θ, W ) = (θ (0) , −W (0) ) respectively. For convenience, we assumes the dot product "·" ignores the row layout or column layout in the chain rule of derivatives and we define the following symbols: Based on the notations defined, we rewrite the loss terms of BYOL and RAFT as follows: The two objectives are following: We claim that under the third condition, the following equations hold: where subscript denotes the tangential component of the gradient.

H NON-TRIVIAL SOLUTIONS CREATED BY PREDICTOR
Suppose inputs x 1 = t 1 (x) and x 2 = t 2 (x) is n-dimensional. And in linear model, f θ , f ξ and q w is parameterized by matrices (θ ij ) n×n , (ξ ij ) n×n and (W ij ) m×m respectively.