Introduction

A recent line of research has focused on how learned predictions can be used to enhance the running time of algorithms. This novel approach, often referred to as warm starting, initializes an algorithm with a machine-learned starting state to optimize efficiency on a new problem instance. This starting state can significantly improve performance over the conventional method of solving problems from scratch.

Warm starting algorithms with machine-learned predictions can be viewed through the lens of beyond-worst-case analysis. While the predominant algorithmic paradigm for decades has been to use worst-case analysis, warm starting takes into account that real-world applications repeatedly solve a problem on similar instances that share a common underlying structure. Predictions about these input instances can be used to the improve running time of future computations.

This new line of research, called algorithms with predictions or learning-augmented algorithms, leverages predictions to achieve strong guarantees-much like those achieved using worst-case analysis-for warm-started algorithms. Under this setting, the performance of the algorithm is measured as a function of the prediction quality. This ensures that the algorithm is robust to prediction inaccuracies and has performance that interpolates smoothly between ideal and worst-case guarantees with respect to predictions.

Recent proof-of-concept results have demonstrated the potential to enhance the running time of offline algorithms. The area was empirically initiated by Kraska et al. (2018). Theoretically, Dinitz et al. (2021) were the first to provide a theoretical framework for using warm-start to improve the running time of the weighted bipartite matching problem. Follow-up works include the application of learned predictions to improve the efficiency of computing flows using Ford-Fulkerson (Davies et al., 2023), shortest path computations using Bellman-Ford (Lattanzi et al., 2023), binary search (Bai & Coester, 2023), convex optimization (Sakaue & Oki, 2022) and maintaining a dynamic sorted array (Mc-Cauley et al., 2023). These results showcase the promising potential to harness predictions more broadly for algorithmic efficiency.

Data structures are one of the most fundamental algorithmic domains, forming the backbone of most computer systems and databases. Leveraging predictions to improve data structure design remains a nascent research area. Empirical investigations, initiated by Kraska et al. (2018) and follow-ups such as Ferragina et al. (2021), demonstrate the exciting potential of speeding up indexing data structures using machine learning. More recently (McCauley et al., 2023) developed the first data structure in the new theoretical framework of algorithms with predictions. They design a learned data structure to maintain a sorted array efficiently under insertions (aka online list labeling). Since then, two concurrent works (Brand et al., 2024) and (Henzinger et al., 2024) show how to leverage predictions for maintaining dynamic graphs for problems such as shortest paths, reachability, and triangle detection via predictions for the matrix-vector multiplication problem. This paper focuses specifically on developing the area of data structures for dynamic graph problems. We study the fundamental problems of maintaining an incremental topological ordering of the nodes of a directed-acyclic graph (DAG) and the related problem of incremental cycle detection. In the problem, a set of n nodes V is given and the edge set is initially empty. Over time, directed edges arrive that are added to the graph. The algorithm must maintain a topological ordering of V at all times. A topological ordering is a labeling L : V ! Z of the vertices V such that L(v) < L(u) if there is a directed path from v to u. A topological ordering exists if and only if the directed graph is acyclic. Thus, if an edge is inserted that creates a cycle, the data structure must report that a cycle has been detected, after which the algorithm ends.

The goal is to design an online algorithm that has small total update time for the m edge insertions. Offline, when all edges are available a priori, the problem can be solved in O(m) (linear time) by running Depth-First-Search (DFS). A naive approach to the incremental problem is to use DFS from scratch each time an edge arrives, giving O(m 2 ) total time. The goal is to design dynamic data structures that can perform better than this naive approach.

Topological ordering and cycle detection are foundational textbook problems on DAGs. Incremental maintenance of DAGs is ubiquitous in database and scheduling applications with dependencies between events (such as task scheduling, network routing, and causal networks). Due to their wide use, there has been substantial prior work on maintaining incremental topological ordering in the worst case (without predictions). Prior work can roughly be partitioned into the cases where the underlying graph is sparse or dense. A line of work (Bender et al., 2009;Haeupler et al., 2012;Bender et al., 2015;Bernstein & Chechi, 2018;Bhattacharya & Kulkarni, 2020) for sparse graphs led to (Bhattacharya & Kulkarni, 2020) giving a randomized algorithm with total update time e O(m 4/3 ). The e O suppresses logarithmic factors. For dense graphs, a line of work (Cohen et al., 2013;Bender et al., 2015) has total update time e O(n 2 ). These results hold for both incremental topological ordering and cycle detection. A recent breakthrough (Chen et al., 2023) uses new techniques to improve the running time of incremental cycle detection to O(m 1+o(foot_0) ); their results do not extend to topological ordering. At present there are no nontrivial lower bounds for either problem, that is, it is not known if there exists an algorithm with update time e O(m).

Despite the rich theoretical literature on the problem, there is limited empirical evidence of their success (Ajwani et al., 2008). As most practical data is non-worst-case, greedy brute-force methods do well empirically (Baswana et al., 2018). The algorithms-with-predictions framework is motivated precisely by this disconnect between high-cost worstcase methods and simple practical heuristics. The goal of designing learned algorithms in this framework is to extract beyond-worst-case performance on typical instances, while being robust to bad predictions in the worst case.

More formally, in the algorithms-with-predictions framework, an algorithm is (a) consistent if it matches the offline optimal (or outperforms the worst case) under perfect predictions, (b) robust if it is never worse than the best worst-case algorithm under adversarial predictions, and (c) smooth if it interpolates smoothly between these extremes. We call an algorithm ideal if it is consistent, robust, and smooth.

In this paper, we initiate the study of how learned predictions can be leveraged for incremental topological ordering.

We propose a coarse-grained prediction model and use it to design a new ideal data structure for the problem; see Section 1.1. Moreover, we present a practical learned DFS algorithm and our experiments show that using even mildly accurate predictions leads to significant speedups. All our results extend to incremental cycle detection. Our results complement the concurrent theoretical work by (Brand et al., 2024) on dynamic graph data structures; see Section 1.2.

Our Contributions

We first propose a prediction model for the problem and then use it to formally describe our results.

Coarse Prediction Model. For the incremental topological ordering problem, it is natural to consider predictions on the nodes which give information about their relative ordering in the final graph. Intuitively, a vertex is earlier in the ordering if it has few ancestors and many descendants. For technical reasons, instead of predicting the number of ancestor and descendant vertices, we predict the number of ancestor and descendant edges. 1 More formally, for each vertex v, let ↵(v) be the total number of ancestor edges of v after all edges arrive, and let (v) be the number of descendant edges. An edge (u, w) is an ancestor edge of v in there is a directed path from w to v. The edge (u, w) is a descendent edge of v if there is a directed path from v to u. At the beginning of time, the algorithm is given predictions e ↵(v)

and e (v) for ↵(v) and (v) for each vertex v. The error in the prediction for vertex v is

We note that our prediction model predicts a small amount of information about the input, in contrast to models that predict the entire input sequence, e.g. (Brand et al., 2024;Henzinger et al., 2024). In particular, predictions that predict the entire input are fine-grained-each possible input sequence maps to a unique perfect prediction. Our predictions are coarse-grained because there are many possible input graphs that can map to a single perfect prediction. Intuitively, the more coarse-grained the prediction, the more robust it is to small changes in the input.

Ideal Learned Ordering. We present a new learned data structure for the incremental topological ordering, called Ideal Learned Ordering. This data structure has total update time e O(min{n⌘ + m, m⌘ 1/3 , nfoot_1 }). The data structure is ideal with respect to predictions; in particular, it is: 1), its performance matches (up to logarithmic factors) the best possible running time e O(m) of an offline optimal algorithm. • Robust: For any ⌘  m, the total running time is e O(min{m 4/3 , n 2 }), and thus its performance is never worse than the best-known worst-case algorithms (Bender et al., 2015) and (Bhattacharya & Kulkarni, 2020).

• Smooth: For any intermediate error ⌘, the performance smoothly interpolates as a function of ⌘ (and n and m), between the above two extremes.

At a high level, the ideal learned ordering decomposes the vertices into subproblems based on the predictions. On each subproblem, it runs the best-known worst-case algorithm, which is warm-started with the predictions.

Learned DFS Ordering and Empirical Results. In addition to the above ideal algorithm, we present a simple practical data structure that essentially warm-starts depthfirst search using predictions. We call this the learned DFS ordering (LDFS). This data structure has total update time O(m⌘); thus each insert has running time O(⌘). We implement LDFS and our experiments show that with very little training data, the predictions deliver excellent speed-ups. In particular, we demonstrate on real time-series data that using only 5% of training data, LDFS explores over 36x fewer vertices and edges than baselines, giving a 3.1x speedup in running time. Moreover, its performance is extremely robust to prediction errors; see Figure 1b.

Related Work

Recently, (Brand et al., 2024) leverage predictions for dynamic graph data structures. They give a general result for the online matrix-vector multiplication problem where the matrix is given and a sequence of vectors arrive online. They apply this to several dynamic graph problems including cycle detection. Their data structure requires O(n ! + n P i2V min{ i , n}) total time where i is the error between when edge i arrives and when it is predicted to arrive, and n ! is the time to perform matrix multiplication. Their prediction is the entire input, that is, the online sequence of vectors. The predictions used in this work are more coarse-grained (only require a pair of numbers per vertex), and thus are robust to small perturbations to the input sequence. Moreover, their work is purely theoretical and leaves open (a) how predictions can be leveraged for maintaining topological ordering, and (b) how predictions can be empirically leveraged for dynamic graph problems. Our work addresses both and complements their findings.

Ideal Learned Ordering uses the best-known sparse algorithm (Bhattacharya & Kulkarni, 2020) and the best-known dense algorithm (Bender et al., 2015), referred to as BK and BFGT throughout. We briefly summarize them; we refer to the papers for more details.

The BFGT algorithm maintains levels `(u) for each vertex u: these are underestimates of the total number of ancestors of u in the final graph. The levels are initially set to 1. On an edge insertion (x, y), if `(x) > `(y), they greedily update levels to maintain a topological ordering. To improve the efficiency, they update y's level even if `(x)  `(y) if a better underestimate of the number of ancestors of y is available (based on its predecessors' levels). The total time for all insertions is bounded by e O(m + P v `(v)). As `(v) is at most the number of ancestors, their total running time is e O(n 2 ). In Section 4, we use predictions to ensure that BFGT is run on subproblems containing vertices with O(⌘) ancestors. Thus, the levels can only increase at most ⌘ times, which leads to the total update time e O(m + n⌘).

The BK algorithm (which is based on (Bernstein & Chechi, 2018)) also partitions the vertices into levels, but these are based on their ancestors and descendants. It is a randomized algorithm and initializes the vertex levels using sampling.

In particular, they use an internal parameter ⌧ where each vertex v 2 V is sampled with probability ⇥(log n/⌧ ). A vertex is in a level (i, j) if it has i ancestors and j descendants among the sampled nodes. They bound the number of possible ancestors and descendants of a vertex within a level using the parameter ⌧ . In Section 4, we use their algorithm as a blackbox with the exception that we set ⌧ using predictions. For the analysis, we give a tighter bound of Phase I and II of their algorithm.

Organization

Section 2 defines the model. Learned DFS Ordering is presented in Section 3; which is generalized to the Ideal Learned Ordering in Section 4. Finally, Section 5 presents experimental results. For space, many proofs and further experiments are deferred to the Appendices A and B.

Model and Definitions

Directed Graphs.

We say that a vertex v is an ancestor of vertex w if there is a path from v to w in the graph. We say w is a descendant of v if v is an ancestor of w. A vertex is an ancestor and descendant of itself. We say that an edge (u, v) is an ancestor edge of a vertex w if v is an ancestor of w. Similarly, an edge

A directed graph has a cycle if there exist vertices u and w that are mutually reachable from each other: that is, u is both an ancestor and descendant of w. A topological ordering of a directed graph exists if and only if it is acyclic.

Incremental Graph Problems. In the incremental topological ordering and cycle detection problems, initially, there are n vertices V and no edges. The m edges from the set E arrive one at a time and are inserted into the graph data structure. Let G t denote the graph after t edges have been inserted (which we also refer to as time t). We assume that after an edge is inserted, the graph continues to be acyclic.

If an edge insertion leads to a cycle, the algorithm must report the cycle and terminate. Thus G m denotes the final graph (after the last edge insertion that does not create a cycle).

The performance of the graph data structure is measured as its total running time to perform all m edge insertions.

In Sections 3 and 4, we use the terms total cost and total update time and total running time interchangeably. We use the notation e O defined as e O(f

Prediction Model. In the incremental topological ordering problem with predictions, the data structure additionally obtains a prediction for each vertex v 2 V at the beginning.

Intuitively, this prediction helps the data structure initialize the label of v to be closer to a feasible topological ordering.

For a vertex v, let ↵(v) be the total number of ancestor edges of v in the final graph G m . Analogously, let (v) be the total number of descendant edges of v in the final graph G m . The Learned-DFS Ordering in Section 3 receives a prediction e ↵(v) of ↵(v) for each vertex v. 4 The prediction error of a vertex v is

The Ideal Learned Ordering in Section 4 receives a prediction e ↵(v) of the number of ancestors ↵(v) and e (v) of the number of descendants (v) respectively, for each vertex v. The prediction error of the vertex v is

The overall error is ⌘ = max v ⌘ v throughout the paper.

Learned-DFS Ordering

In this section, we give a simple and easy-to-implement data structure that achieves O(m⌘) total update time. We refer to this algorithm as the Learned DFS Ordering (LDFS).

Algorithm Description

At all times, the algorithm maintains a level `(v) for each vertex, which is a number from 0 to m. For each vertex v, the algorithm maintains a linked list in(v) of v's parents at the same level (i.e. a linked list of all parents p of v with `(p) = `(v)). Finally, to maintain a topological ordering, the algorithm additionally maintains a (global) counter a, and for each vertex v an integer j(v) 2 {1, . . . , nm + 1}.

Initially, a = nm+1, and for each v,

{}, and j(v) = nm + 1. On insertion of an edge e = (u, v), if `(u) > `(v), set `(v) `(u) and in(v) {u}. Then, do a forward search from v to recursively update v's descendants. That is, for each child w of v, if `(v) > `(w), update `(w) and in(w) and recurse. Report a cycle if one is found; otherwise calculate a topological order T f on all vertices whose levels changed during this search.

Cycle detection. After the above update concludes, if `(u) = `(v), do a reverse DFS starting at u (i.e. a DFS where edges are followed backward) only following edges in(u) from vertices at the same level. If this search visits v, report a cycle. Otherwise, let T b be a topological order on the vertices visited during this DFS (e.g., T b can be computed by ordering vertices in the order of their DFS finish times).

Topological ordering. The ordering imposed by the level `(v) on the vertices is a pseudo-topological ordering (Bender et al., 2015). Indeed, our algorithm can be viewed as a simplification of the sparse algorithm in (Bender et al., 2015) with the addition that levels are initialized using predictions.

Bender et al. describe how to extend their ordering to a topological order by breaking ties between vertices on a level using the order in which they are traversed in the reverse DFS. We use a similar technique here. Concatenate T b and T f to create a single topological order T . If `(u) = `(v) and j(u) j(v), proceed through each vertex w 2 T in reverse order. Set j(w) = a, then a = a 1, and then set w to the previous vertex in T .

We define the label of a vertex v to be L(v) = `(v)(nm + 2) + j(v). The algorithm maintains the following invariants.

Invariant 3.1. For any edge e = (u, v) in the graph G t at time t, `(u)  `(v).

Invariant 3.2 ( (Bender et al., 2015, Theorem 2.5)). At all times, a 2 {1, . . . , nm + 1}; furthermore, a is nonincreasing over the entire run of the algorithm.

↵(a).

Analysis

The following proves that the algorithm is always correct.

Lemma 3.4. If the insertion of the last edge creates a cycle in G t , the simple learned algorithm correctly detects and reports it. Furthermore, for any edge e = (u, v) in the graph G t at time t, L(u) < L(v).

We bound the running time by bounding the cost of the forward search to update levels, and the reverse DFS within a level to detect a cycle.

We first upper bound how big the levels can get using ⌘.

Lemma 3.5. Let `0 and `m denote the initial and final level of any vertex v. Then, `m `0  2⌘.

Lemma 3.5 is sufficient to bound the cost of all level updates during the forward search.

Lemma 3.6. The total cost to update the levels of all vertices is O(m⌘).

Proof. To obtain the total cost of updating the levels, note that each time we update the level of a vertex v, the algorithm recursively updates its children, and then checks each of its parents to update in(v). This takes O( (v)) time, where (v) is the sum of the outdegree and indegree of v. Thus, using Lemma 3.5 the total cost of all level updates is

To bound the cost of the reverse DFS on a level, we bound the number of incoming edges on any level at any time.

Lemma 3.7. At any time, if a vertex v has k ancestor edges on its level then ⌘ k/2. Now we can bound the cost of the reverse DFS. The algorithm maintains incoming edges in(v) of v from vertices on its level in a linked list. Performing the reverse DFS from v thus has cost O(1 + a t (v)), where a t (v) is the number of ancestor edges of v from vertices at level `(v) at time t. By Lemma 3.7, a t (v 1 )  ⌘ and thus the reverse DFS costs O(⌘) for each insertion. Finally, combining with Lemma 3.6 and the O(n) time for initialization, we get the following result. Theorem 3.8. The Learned DFS Ordering solves the incremental topological ordering and cycle detection problem with predictions in total running time O(m⌘ + n).

Ideal Learned Ordering

In this section, we give an ideal learned data structure for the incremental topological ordering and cycle detection problem with total update time e O(m + min{n⌘, n 2 , m⌘ 1/3 }) for m edge insertions. We refer to this algorithm as Ideal Learned Ordering. The algorithm receives a prediction e ↵(v) and e (v) of the number of ancestor and descendant edges of each vertex in the final graph G m . By definition, |e

Prediction Decomposition. At a high level, the algorithm decomposes the problem instance into smaller subproblems based on each vertex's prediction, and uses the state-of-theart worst-case algorithm on each subproblem based on the instance's sparsity. Recall that BK and BFGT refer to the best-known sparse algorithm by (Bhattacharya & Kulkarni, 2020) and the best-known dense algorithm by (Bender et al., 2015); see Section 1.2. Using a tighter analysis for these algorithms under predictions, we then bound the running time of each subproblem using the prediction error.

Algorithm Description

The algorithm maintains an estimate ⌘ which is an estimate of the overall error ⌘ based on edges seen so far. It also maintains a level `(v) for each vertex, initialized using both e ↵(v) and e (v). It maintains a pseudo-topological ordering over these levels greedily. We decompose the initial set of vertices V into a sequence of subproblems based on the predictions for each vertex. When an edge e = (u, v) arrives, it is treated as an edge insertion into each subproblem that contains both u and v. The algorithm invokes the BK or BFGT algorithm to perform this insertion and to assign internal labels within each subproblem.

If an edge is inserted across subproblems that violates the ordering over the levels, the algorithm updates its estimate of ⌘ and rebuilds with an improved decomposition.

Algorithm setup. Let ⌘i be the value of ⌘ after i edges are inserted. We begin with ⌘0 = 1.

We maintain a level `(v) for each vertex v. Each `(v) consists of a pair of numbers: `(v) = (`a(v), `d(v)); we call this the ancestor level and descendant level of v respectively. The idea is that `a(v) and `d(v) are initialized using the predicted ancestors and descendants of v respectively and updated as edges are inserted.

At all times, the level `(v) has four possible values satisfying the constraints below. These are referred to as the possible levels for v.

We maintain that for any edge e = (u, v), `a(u)  `a(v) and `d(u) `d(v).

At any time, the vertex set V is decomposed into subproblems H j,k , where the indices j, k 2 {0, . . . , dm/⌘ i e + 1}.

Each subproblem H := H j,k is a subgraph of G t and represents an instance of the incremental topological ordering problem (possibly at an intermediate state with some edges already inserted). A vertex v can be part of at most four subproblems, indexed by one of its possible levels:

As each vertex is in at most four subproblems, the algorithm maintains O(n) subproblems at any point; note that "empty" subproblems are not maintained.

Initialization and Build. We first describe how to perform a BUILD on a graph G t ; BUILD is called each time the estimate ⌘ changes. At initialization, BUILD(G 0 ) adds each vertex v to the subproblems H(v). If a sequence of edge insertions e 1 , . . . , e t are such that tth insertion causes ⌘t to be updated, then BUILD(G t ) first updates H(v) for each v based on the updated value of ⌘t and adds v to H(v).

Then it calls INSERT(e i ) for i 2 {1, . . . , t} using the insert algorithm described next.

The insert algorithm uses a further subroutine BUILD-BFGT(H), which is used to "switch" a subproblem from the sparse case to the dense case. Let V H and E H be the vertices and edges currently in H. BUILD-BFGT initializes an instance of BFGT on vertices V H , and then inserts all edges in E H one by one using BFGT.

Edge Insertion. On the insertion of the tth edge e t , IN-SERT(e t ) first recursively updates the ancestor and descendant levels of v and u in G t . That is, if `a(u) > `a(v), set `a(v) = `a(u) and recurse on all out-edges of v.

and recurse on all in-edges of u. This maintains the following invariant.

Invariant 4.1. For any edge e = (u, v), `a(u)  `a(v) and `d(u) `d(v).

If for any vertex v, the updated value of `(v) is not one of the possible levels of v, the algorithm doubles ⌘ (i.e. set ⌘i = 2⌘ i 1 ) and calls BUILD on G t .

Next, we describe how the algorithm inserts e t into all subproblems H 2 H(u) \ H(v) using the BK or BFGT algorithm based on whether the subproblem is sparse or dense. Without predictions, a graph is termed sparse if m = o(n 3/2 ) and dense otherwise. To determine if a subproblem with predictions is sparse or dense, the algorithm takes error ⌘ into account. More formally, let n 0 and m 0 denote the number of vertices and edges in a subproblem H prior to the insertion of e t into H. Then:

• (Sparse) If m 0 + 1 < n 0 ⌘ 2/3 , it inserts e t to the subproblem H using BK;

• (Dense) if m 0 > n 0 ⌘ 2/3 , it inserts e t to subproblem H using BFGT;

• (Sparse to dense transition) if m 0 < n 0 ⌘ 2/3 and m 0 + 1 > n 0 ⌘ 2/3 , it calls BUILD-BFGT(H) first, then inserts e t into H using BFGT.

We refer to the label within a subproblem assigned by the BFGT or BK algorithm as an internal label of the vertex.

If after t edges are inserted (for any t) we have ⌘ > n and t⌘ 1/3 > n 2 , the algorithm ignores all predictions and reverts to using the worst-case BFGT. The algorithm creates a new instance of BFGT using the vertices in G t , and inserts all t edges into this BFGT instance one by one. All future edges are inserted into this BFGT instance.

Defining Labels. For any vertex v, let i(v) be the internal label of v in subproblem H `(v) . Let k be a positive integer larger than the internal label of any node in a graph with n vertices in either BFGT or BK (we note that both algorithms maintain only nonnegative labels). Define the label L of v as

Analysis

We analyze the correctness and running time of Ideal Learned Ordering.

Correctness. First, we show that if a cycle exists, then it is correctly reported by the algorithm.

By Invariant 4.1, if the insertion of an edge creates a cycle, all vertices in the cycle must have the same level `. The algorithm maintains the invariant that at all times H `(v) 2 H(v), so all vertices and edges in the cycle must be in some subproblem H and thus will be detected by BFGT or BK.

Lemma 4.2. For any edge e = (u, v) in G t , L(u)  L(v).

Proof.

then the lemma holds since i(u) < k. Otherwise, suppose `a(u)+m `d(u) `a(v)+m `d(v). By Invariant 4.1, `a(u)  `a(v) and m `d(u)  m `d(v); thus we must have `(u) = `(v). Thus, i(u) and i(v) are both assigned by BFGT or BK on H `(u) . By correctness of BFGT and BK, i(u) < i(v). Running Time Analysis. We give an overview of the running time analysis of Ideal Learned Ordering. Proofs are deferred to Appendix A. Lemma 4.3 bounds the number of ancestors and descendants of a vertex within the graph of any subproblem. Lemma 4.3. For any subproblem H j,k and vertex v 2 H j,k , v has at most 2(⌘ + ⌘) ancestor edges and 2(⌘ + ⌘) descendant edges in H j,k . Lemma 4.4 shows that the estimate ⌘ maintained by the algorithm is never more than 2⌘. Lemma 4.4. At all times, ⌘  2⌘ Lemma 4.5 and Lemma 4.6 bound the cost of running BFGT and BK any subproblem respectively. Lemma 4.5. Consider a subproblem H with n 0 vertices and m 0 edges that are inserted into H one by one. If each vertex in H has at most O(⌘) edge ancestors, then the total running time of running BFGT on H is e O(n 0 ⌘ + m 0 ) time. Lemma 4.6. Consider a subproblem H with n 0 nodes and m 0 edges, such that: (1) m 0 < ⌘2 n 0 / log 2 n 0 , (2) each vertex in H has at most O(⌘) edge ancestors and O(⌘) edge descendants, and (3) ⌘ = O(⌘). Then running BK on H with parameter ⌧ = n 1/3 ⌘2/3 /m 1/3 takes total time e O(m 0 ⌘ 1/3 ) in expectation.

Finally, Theorem 4.7 analyzes the total running time.

Theorem 4.7. Ideal Learned Ordering has total expected running time e O(min{m⌘ 1/3 , n⌘, n 2 }).

Experiments

This section presents experimental results for the Learned DFS Ordering (LDFS) described in Section 3. Our experiments show that using prediction significantly speeds up performance over baseline solutions on real temporal data. Moreover, only a small amount of training dataset (e.g., 5%) is sufficient to see one or two orders of magnitude of improvement. Finally, we show that LDFS is extremely robust to errors in the predictions.

Our implementation and datasets can be found at https://github.com/AidinNiaparast/ Learned-Topological-Order.

Algorithms. We compare LDFS against two natural baseline solutions that we call DFS I and DFS II. Each of the three algorithms use a greedy depth-first-search approach to maintain a topological ordering, with the difference that LDFS warm-starts its levels using predictions.

DFS I.

The first algorithm is equivalent to LDFS with zero predictions: that is, e ↵(v) = 0 for each v.

DFS II. This algorithm was presented by (Marchetti-Spaccamela et al., 1993) for incremental topological ordering and revisited by (Franciosa et al., 1997) for incremental DFS. It has total update time O(mn). (Baswana et al., 2018) perform an empirical study on incremental DFS algorithms and show that DFS II (which they call FDFS) is the stateof-the-art on DAGs. DFS II maintains exactly one vertex at each level. When an edge (u, v) is inserted, if l(v) < l(u), the algorithm performs a partial DFS to detect all the vertices w reachable from v such that l(v) < l(w) < l(u), and updates their levels to be larger than l(u).

We remark that the Ideal Learned Ordering algorithm is of theoretical interest. Our experiments focus on the practical algorithm (LDFS) and on showing the usefulness of predictions.

Datasets. We use real directed temporal networks from the SNAP Large Network Dataset Collection (Leskovec & Krevl, 2014). To obtain the final DAG G, we randomly permute the vertices and only keep the edges that go from smaller to larger positions (this ensures G is acyclic). Then, we sort the edges in increasing order of their timestamps to obtain the sequence of edge insertions. Table 1 summarizes these datasets. Note that these graphs are sparse.

Predictions. To generate the predictions for LDFS, we use a contiguous portion of the input sequence as the training set. Consider the graph that results from inserting the training set edges into an empty graph. For each node v, we define e ↵(v) to be the number of v's ancestor edges in that graph.

Experimental Setup and Results. On real datasets, we compare LDFS to DFS I and II in terms of the number of edges and vertices processed (cost) in Table 2a and in terms of runtime in Table 2b. The last 50% of the data in increasing order of the timestamps is used as the test data in all of the experiments in Table 2. The training data for LDFS is a contiguous subsequence of the data that comes right before the test data.

We include plots for the email-Eu-corefoot_4 (Paranjape et al., 2017) dataset, which contains the email communications in a large European research institution. A directed edge (u, v, t) in this dataset means that u has sent an e-mail to v at time t. Figure 1a shows how the training data size affects the runtime of LDFS. Figure 1b is a robustness experiment showing performance versus the noise added to predictions.

For testing robustness to prediction error, we add noise to the predictions. We first generate predictions as described.

Then, we calculate the standard deviation of the prediction error, which we denote by SD(predictions). Finally, we add a normal noise with mean 0 and standard deviation SD(noise) = C• SD(predictions) (for some constant C) independently to all of the predictions to obtain our noisy predictions. We repeat the experiment 10 times, each time regenerating the noisy predictions; we plot the mean and standard deviation of the resulting running time in Figure 1b. Discussion. Results in Table 2 demonstrate that, in all cases, even a very basic prediction algorithm can significantly enhance performance over the baselines. Only 5% of historical data is needed to see a significant difference between our methods's performance and the baselines; in some cases up to a factor of 36 in cost. Better predictions obtained from 50% of historical data improve performance further, up to a factor of 116. These experiments show that it is possible to learn predictions that give significant performance improvements from a small amount of training data.

Finally, Figure 1b shows that LDFS is very robust to bad predictions. For example, note that if SD(noise) 2 • SD(predictions), then ⇡ 61% of the noisy predictions have noise added to them that is at least SD(predictions)foot_5 thus, the relative value of the predictions becomes largely random for many items. Since the LDFS algorithm's performance only depends on how predictions for different nodes relate to each other (not their value), this represents a significant amount of noise, effectively nullifying the predictions of many nodes. Nonetheless, LDFS still outperforms the baselines even for this extreme stress test. Moreover, increasing the noise degrades the performance confirming that the efficiency does depend on the quality of predictions.

In Appendix B, we include additional plots for the datasets in Table 1. We also investigate the effect of edge density on performance for synthetic DAGs. These experiments further support our conclusions; in particular, even for very dense DAGs, our algorithm still outperforms the baselines, although with smaller margins.

Conclusion

This paper gave the first dynamic graph data structure that leverages predictions to maintain an incremental topological ordering. We show that the data structure is ideal: that is, it is consistent, robust, and smooth with respect to errors in prediction. Thus, predictions deliver speedups on typical instances while never performing worse than the state-ofthe-art worst case solutions. This paper is also the first empirical evaluation of using predictions on dynamic graph data structures. Our experiments show that the theory is predictive of practice: predictions deliver up to 6x speedup for LDFS compared to natural baselines.

Our results demonstrate the incredible potential for improving the theoretical and empirical efficiency of data structures using predictions. It would be interesting to explore how predictions can be leveraged for designing data structures

(a) (b)

Figure 1. Total cost (number of nodes and edges processed) of LDFS compared to the two baselines for email-Eu-core dataset, in logarithmic scale. In Figure 1a, the x-axis is the percentage of the input sequence used as training data for LDFS. The training data in this experiment is a contiguous subsequence of the data that comes right before the test data. Figure 1b shows the effect of adding noise to predictions on the cost of LDFS. In this experiment, the first 5% of the input is used as the training data and the last 95% as the test data. For different values of C, a normal noise with mean 0 and standard deviation (SD) of C•SD(predictions) is independently added to each prediction. This noise is regenerated 10 times. The x-axis is SD(noise)/SD(predictions). The blue line is the mean and the cloud around it is the SD of these experiments.

for other dynamic graph problems.

We remark that the Ideal Learned Ordering algorithm is of theoretical interest and we did not implement it. Similarly, the subroutines BK and BFGT used by the algorithm as a black box are of theoretical interest and, as far as we are aware, have not been empirically evaluated. We leave it as an open question how to engineer these algorithms to work well in practice.

A. Omitted Proofs

Proof of Lemma 3.4. By Invariant 3.1, for any cycle C in the graph, all vertices in C must at the same level. Each time we add an edge e = (u, v), if `(u) = `(v), the algorithm checks whether the addition of this edge creates a cycle within that level through a reverse depth-first search. Now, assume there is no cycle in G t ; we show that a weak topological sort is maintained. A weak topological sort is trivially maintained in G 0 , so assume inductively that the algorithm correctly maintains a weak topological sort in G t 1 . Consider an edge (u, v) 2 G t . If `(u) < `(v), then the label of u is less than the label of v since j(u), j(v)  nm + 1. If `(u) = `(v), then we split into cases based on if the label of u or v was changed during the updates after the tth edge was inserted. If neither u or v were updated, the labels continue to be a topological ordering as in G t 1 . It is not possible that v is updated but u is not: for any v visited during DFS, since `(u) = `(v), u is also visited; for any v whose label is updated, u must have a strictly larger label than any other parent of v. If u is updated and v is not, then j(u) is set to a; since a decreases each time some j(w) is set, we must have j(u) < j(v). If both u and v are updated, u must come before v in T . Again, since a decreases each time some j(w) is set, we must have j(u) < j(v).

Proof of Lemma 3.7. Let A denote the set of all ancestors of v at level `(v) at the current time. Consider the vertices in A after all edges are inserted (in G m ): since G m is acyclic, there must be at least one vertex z 2 A such that no vertex w 2 A has that w is an ancestor of z in G m .

Since z is an ancestor of v, all ancestor edges of z are ancestor edges of v. However by definition of z, an ancestor edge of any w 2 A is never an ancestor edge of z. All k ancestor edges of v on its level are ancestor edges of some w 2 A. Therefore, ↵(v) ↵(z) + k, so ↵(v) ↵(z) k.

As levels only increase `(v) e ↵(v). By Invariant 3.3, `(v)  e ↵(z); equivalently, e ↵(v) + e ↵(z) 0. Summing the above two inequalities, we get

Proof of Lemma 4.3. Let H refer to the subgraph H j,k after the last edge is inserted into it (thus, H includes edges that are inserted in the future, whereas H j,k does not). We use ↵ H (v) and H (v) to denote the number of number of ancestor and descendant edges of a vertex v in H.

Let u be an ancestor of v in H, such that no ancestor edge of v in H is an ancestor edge of u in H. Such a u always exists as H is acyclic and can be found by recursively following in-edges of v.

By definition of u, all ancestor edges of u are ancestor edges of v (in G m ); however, no ancestor edges of v in H are ancestor edges of w (in G m ). Thus, ↵(v) ↵(u) + ↵ H (v), so ↵(v) ↵(u) a H (v).

As both v and u are in H j,k we can bound the difference of their predictions using ⌘. That is, j de ↵(v)/⌘e, and therefore j e ↵(v)/⌘. Similarly, j  de ↵(u)/⌘e + 1, so j  e ↵(u)/⌘ + 2. Combining, e ↵(u)/⌘ + 2 e ↵(v)/⌘, so e ↵(u) e ↵(v) 2⌘.

Summing the two above equations, we obtain that

By the definition, ↵(v) e ↵(v)  ⌘ and e ↵(u) ↵(u)  ⌘. Substituting, a H (v)  2⌘ + 2⌘.

The analysis for the number of descendants is analogous. Let w be a descendant of v in H, such that no descendant edge of v in H is a descendant edge of w in H . By definition of w, all descendant edges of w are descendant edges of v (in G m ); however, no descendant edges of v in H are descendant edges of w (in G m ). Therefore, (v)

As both v and w are in H j,k , we have that j  b e (w)/⌘c, and therefore j  e (w)/⌘. Similarly, j b e (v)/⌘c 1, so j e (v)/⌘ 2. Combining, e (w)/⌘ e (v)/⌘ 2, so e (w) e (v) 2⌘.

Summing the two above equations, we obtain that

By the definition, (v) e (v)  ⌘ and e (w) (w)  ⌘. Substituting, H (v)  2⌘ + 2⌘. As the number of ancestor and descendant edges are nondecreasing, this upper bound (in H after all edges are inserted), is also an upper bound at all times in H j,k .

Proof of Lemma 4.4. We proceed by induction. The lemma is trivially satisfied at time 0 (since ⌘0 = 1), as well as any time where ⌘ does not change.

Consider a time when ⌘ is increased, from ⌘ to 2⌘; we show that ⌘  2⌘. When ⌘ is increased, there is some vertex v with `(v) / 2 H(v). We split into two cases based on if the ancestor level or the descendant level constraint is violated: `a(v) > de ↵(v)/⌘e+1, and `d(v) < b e (v)/⌘c 1. We begin with the first case. Without loss of generality, consider a vertex v that violates the constraint such that no ancestor of v violates the constraint. Specifically, `a(v) > de ↵(v)/⌘e + 1, whereas `(u)  de ↵(v)/⌘e + 1 for all ancestors u of v.

When inserting an edge e = (x, y), the algorithm updates the ancestor levels of all descendants of x to have the same ancestor levels as x; no other ancestor levels are updated. Thus, v has an ancestor w with e ↵(w) = `a(v).

Noting that the label of v can only increase, we must have that e ↵(w) = `(v) > de ↵(v)/⌘e+1. Thus, e ↵(w) e ↵(v) > ⌘.

Since w is an ancestor of v, ↵(w) < ↵(v), so ↵(v) ↵(w) 0. Summing the above two equations,

The analysis for the descendant constraint is identical.

Proof of Lemma 4.5. For each vertex, BFGT maintains a vertex level (that determines the internal label for our algorithm), and a vertex count. In the proof of (Bender et al., 2015, Theorem 3.6), each edge traversal in BFGT increases the vertex level or a vertex count, and the running time of BFGT is upper bounded by the number of edge traversals plus m 0 (i.e. O(1) additional time for each inserted edge, even if no edge is traversed). Thus, our goal is to bound the number of times a vertex level or vertex count increases in H.

A vertex level begins at 0 and is nondecreasing for all vertices by definition. By (Bender et al., 2015, Theorem 3.5), the level of each vertex is upper bounded by the number of (vertex) ancestors, which is in turn upper bounded by the number of edge ancestors. Since each vertex has O(⌘) vertex ancestors by Lemma 4.5, the total number of vertex level increases is e O(⌘), giving e O(n 0 ⌘) increases overall.

Next, we summarize how a vertex count changes over time, and use this to show that it increases by the maximum vertex level. Let `= e O(⌘) be the maximum vertex level of any vertex. See the proof of (Bender et al., 2015, Theorem 3.6) for more details. The data structure maintains a parameter j for each vertex v, where j is at most log 2 (current vertex count of v). The count for a vertex v begins at 0, and increases up to 3 • 2 j , after which it is reset to 0. This count must increase by at least 2 j over the same time. Thus, so far, the number of times a vertex count is incremented is at most 3`. The count may be reset to 0 one additional time (at most 3`more increases); furthermore, the count may at the end of the algorithm increase up to 3 • 2 j without being reset (another 3`more increases). Thus, a vertex count can be incremented at most 9`times.

Proof of Lemma 4.6. The cost of BK as shown in (Bhattacharya & Kulkarni, 2020)

First, we show that if all vertices in H have at most O(⌘) edge ancestors and O(⌘) edge descendants, then the running time of BK on H is

Let us begin with the first term of Equation 1. This term comes from (Bhattacharya & Kulkarni, 2020, Lemma 2.2). Specifically, there are n/⌧ sampled vertices in expectation; we maintain all ancestors and descendants of each sampled vertex. This can be done efficiently using the classic data structure presented in (Italiano, 1986).

The result as stated in (Italiano, 1986) states that the descendants of all (rather than just sampled) vertices can be maintained in O(nm) time. Our results require a slightly stronger analysis. 7 For completeness, we summarize this tighter analysis here. The bounds in (Italiano, 1986) are based on a potential function analysis, where each vertex v has (using the notation of (Italiano, 1986)) potential (|vis(x) + 3|desc(x)), where vis(x) is the number of descendant edges of x, and desc(x) is the number of descendant vertices of x. They show that their amortized cost (the cost plus the change in potential) of an edge insert is O(1), and that the potential of all nodes is nonincreasing.

We observe that if we only want to maintain the descendants of sampled vertices, we can set the potential of non-sampled nodes to 0; their amortized analysis argument still holds under this change. By Lemma 4.3 and Lemma 4.4, the potential of any node is at least 6⌘, so the total cost to maintain the descendants of each sampled vertex is O(⌘).

An essentially-identical analysis shows that the total cost to maintain all ancestors of sampled nodes is O(⌘). Since there are n/⌧ expected sampled nodes, we obtain a total expected cost of O(n⌘/⌧ ).

Now, the second term of Equation 1. In (Bhattacharya & Kulkarni, 2020, Lemma 2.3), it is shown that the total time in "phase II" is e O(n 2 /⌧ ). In short, they show that the cost for a vertex v is e O(A S (v) + D S (v)), where A S (v) and D S (v) are the number of sampled ancestor and descendant vertices of v respectively. Since a vertex is sampled with probability ⇥(log n/⌧ ), they obtain expected cost e O(n/⌧ ) per vertex. A vertex in H has only O(⌘) ancestor or descendant edges, and therefore only O(⌘) ancestor or descendant vertices, and therefore expected cost e O(log n 0 ⌘/⌧ ). Summing over all n 0 vertices of H we obtain the desired second term.

The third and fourth term of Equation 1 remain unchanged; thus the running time of BK on H is given by Equation 1.

Substituting ⌧ = n 01/3 ⌘2/3 /m 01/3 , we obtain running time m⌘ 1/3 . Note that BK samples vertices with probability ⇥(log n/⌧ ), so we need that ⌧ = ⌦(log n). This is satisfied for large n 0 due to m 0 < ⌘2 n 0 log 2 n 0 . We note that if BK was to sample vertices with a fixed probability C 1 log n 0 /⌧ , we could replace the final log n 0 term in our bound on m 0 with C 1 .

Proof of Theorem 4.7. We bound the cost of updating the levels first; then we bound the total cost of all subgraphs.

First, we consider the cost of updating levels after the ith edge is inserted. We only traverse an edge (u, v) while updating levels if the level of u is updated.

First, consider an update when ⌘ does not increase; thus each vertex has one of its possible levels after the update. Each vertex has four possible levels, so each vertex can have its levels updated once per value of ⌘; thus, each edge can only be traversed once per value of ⌘. This leads to e O(m log ⌘m ) time. Now, the other case: if ⌘ increases, the cost of the scan is at most O(m); since ⌘ increases log 2 ⌘ times, this gives an additional e O(m log ⌘m ) time.

Now, the cost of inserting all edges into their corresponding subgraphs. Let us begin with some observations about the cost of a single subgraph H i,j with n 0 vertices and (after all insertions are complete) m 0 edges, for a fixed ⌘. If m 0 < ⌘2/3 n 0 / log 2 n, then by Lemma 4.6 (note that m 0 < ⌘2/3 n 0 / log 2 n implies m 0 < ⌘2 n 0 / log 2 n 0 ), all edge insertions into H i,j cost m 0 ⌘1/3 . If m 0 ⌘2/3 n 0 / log 2 n 0 , then the first ⌘2/3 n 0 / log 2 n 0 insertions into H i,j have cost e O(⌘n 0 ) by Lemma 4.6. All remaining insertions (including reinserting the first ⌘2/3 n 0 / log 2 n 0 edges during REBUILD) have cost O(n 0 ⌘) by Lemma 4.5, for O(n 0 ⌘) total time. Overall, all edge insertions into H i,j take O(min{n 0 ⌘, m 0 ⌘1/3 }) time. Now, we sum over all subgraphs and over all values of ⌘ to achieve the final running time. Let `⌘ = log 2 ⌘; thus when ⌘ doubles `⌘ is incremented. Let n i,j,⌘ and m i,j,⌘ be respectively the number of vertices and total number of edges in H i,j under a given ⌘. Then we can bound the total time spent in all subgraphs as: Substituting, the total running time on all subgraphs is e O(min{n⌘, m⌘ 1/3 }). If at any time ⌘ > n and m⌘ 1/3 > n 2 we stop the above process and use BFGT. The cost of all edge inserts while ⌘  n is e O(n 2 ) by the above; the cost of all remaining inserts is e O(n 2 ) (Bender et al., 2015). Thus, the overall total running time is e O(min{n⌘, m⌘ 1/3 , n 2 }).

B. Additional Experiments

In this section, we present additional experiments; in particular, we explore how the performance is influenced by the edge density of the graph in synthetic DAGs. We also further describe the experimental setup and the datasets we use.

Dataset Description. Here we describe the real temporal datasets we use in our experiments.

• email-Eu-corefoot_7 (Paranjape et al., 2017): This network contains the records of the email communications between the members of a large European research institution. A directed edge (u, v, t) means that person u sent an e-mail to person v at time t.

• CollegeMsgfoot_8 (Panzarasa et al., 2009): This dataset includes records about the private messages sent on an online social network at the University of California, Irvine. A timestamped arc (u, v, t) means that user u sent a private message to user v at time t. Discussion. Figure 2 suggests that our algorithm (without perturbation) outperforms the baselines, even for very dense DAGs (note that the last point in the x-axis corresponds to p = 1, which means that the DAG is complete). However, as the edge density of the DAG increases, the gap between our algorithm and DFS II decreases. Also for high densities and high perturbations, our algorithm still performs reasonably compared to other baselines in terms of cost (which is the main focus of the paper). Another observation is that LDFS is more robust to perturbation on sparse graphs. Finally, Figures 3, 4, and 5 further support our conclusions in Section 5.