{'fraction_non_alphanumeric': 0.03949735995988319, 'fraction_numerical': 0.012624996312793133, 'mean_word_length': 3.963689604685212, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Submodularity on Hypergraphs: From Sets to Sequences

In a nutshell, submodular functions encode an intuitive notion of diminishing returns. As a result, submodularity appears in many important machine learning tasks such as feature selection and data summarization. Although there has been a large volume of work devoted to the study of submodular functions in recent years, the vast majority of this work has been focused on algorithms that output sets, not sequences. However, in many settings, the order in which we output items can be just as important as the items themselves. To extend the notion of submodularity to sequences, we use a directed graph on the items where the edges encode the additional value of selecting items in a particular order. Existing theory is limited to the case where this underlying graph is a directed acyclic graph. In this paper, we introduce two new algorithms that provably give constant factor approximations for general graphs and hypergraphs having bounded in or out degrees. Furthermore, we show the utility of our new algorithms for real-world applications in movie recommendation, online link prediction, and the design of course sequences for MOOCs.


Preliminaries and Related Work
Intuitively, submodularity describes the set of functions that exhibit diminishing returns. Mathematically, a set function f : 2 V → R is submodular if, for every two sets A ⊆ B ⊆ V and element v ∈ V \ B, we have . That is, the marginal contribution of any element v to the value of f (A) diminishes as the set A grows.
A submodular function f is said to be monotone if f (A) ≤ f (B) for every two sets A ⊆ B ⊆ V . That is, adding items to a set cannot decrease its value. A seminal result in submodularity states that if our utility function f is monotone submodular (and non-negative), then the classical greedy algorithm maximizes f subject to a cardinality constraint up to an approximation ratio of 1 − 1/e (Nemhauser et al., 1978). Since then, the study of submodular functions has been extended to a broad variety of different settings, including non-monotone submodularity (Feige et al., 2007;Buchbinder et al., 2014), adaptive submodularity (Golovin and Krause, 2011), weak submodularity (Das and Kempe, 2011), and continuous submodularity (Wolsey, 1982;Bach, 2015), just to name a few.
Despite the above, the vast majority of existing results are limited to the scenario where we wish to output sets, not sequences. Alaei and Malekian (2010) and Zhang et al. (2016) consider functions they call stringor sequence-submodular, but it is in a different context. Li and Milenkovic (2017) look at a combination of submodularity and hypergraphs, but it is specifically within the context of hypergraph clustering. In this paper, we use a directed graph on the items where the edges encode the additional value of selecting items in a particular order. The only known theoretical result for this setting is limited to the case where the underlying graph is a directed acyclic graph (Tschiatschek et al., 2017). Considering sequences instead of sets causes an exponential increase in the size of the search space, but it allows for much more expressive models.
For example, consider the problem of recommending movies to a user. A recommendation system could determine that the user might be interested in The Lord of the Rings franchise. However, if the model does not consider the order of the movies it recommends, the user may watch The Return of the King first and The Fellowship of the Ring last, which is likely to make the user totally unsatisfied with an otherwise excellent recommendation. With this example as motivation, the next section gives a more detailed description of the problem we consider.

Problem Description
Tschiatschek et al. (2017) was the first to consider this particular submodular sequence setting and we will closely follow their setup of the problem. Recall that the goal is to select a sequence of items that will maximize some given objective function. To generalize the problem description, we will refer to items as vertices from now on.
Let V = {v 1 , v 2 , . . . , v n } be the set of n vertices (items) we can pick from. A set of edges E encodes the fact that there is additional value in picking certain vertices in a certain order. More specifically, an edge e ij = (v i , v j ) encodes the fact that there is additional utility in selecting v j after v i has already been chosen. Self-loops (i.e., edges that begin and end at the same vertex) encode the fact that there is some individual utility in selecting a vertex.
In general, our input consists of a directed graph G = (V, E), a non-negative monotone submodular set function h : 2 E → R ≥0 , and a parameter k. The objective is to output a non-repeating sequence σ of k unique nodes that maximizes the objective function: We say that E(σ) is the set of edges induced by the sequence σ. It is important to note that the function h is a submodular set function over the edges, not over the vertices. Furthermore, the objective function f is neither a set function, nor is it necessarily submodular on the vertices.
For example, consider the graph in Figure 1, and let h E(σ) = |E(σ)|. That is, the value of a sequence is simply the number of edges induced by that sequence. Consider the sequence σ A = (F ) where the user has watched only The Fellowship of the Ring, the sequence σ B = (T ) where the user watched only The Two Towers, and the sequence σ C = (F, T ) where the user watched The Fellowship of the Ring and then The Two Towers: The Return of the King Figure 1: Graph for The Lord of the Rings franchise. The self-loops encode the fact that each movie has some individual value. The edges encode the fact that there is additional utility in watching the movies in the correct order. Notice that the utility of watching The Return of the King after having already seen both The Fellowship of the Ring and The Two Towers is higher than the utility of watching The Return of the King after having seen just one of the two.
This example shows that although the marginal gain of the edges is non-increasing in the context of a growing set of edges (i.e., the function h is submodular on the edges), it is clear that the function f is not submodular on the vertices. In particular, the marginal gain of The Two Towers is larger once the user has already viewed The Fellowship of the Ring.
Furthermore, just to fully clarify the concept of edges being induced by a sequence, consider the sequence σ D = (T, F ) where the user watched The Two Towers and then The Fellowship of the Ring.
Notice that although sequences σ C and σ D contain the same movies, the order of σ D means that the edge (F, T ) is not induced, and thus, the value of the sequence is lower.

Our Contributions
Throughout this paper we use the notation ∆ = min{d in , d out }, where d in = max v∈V d in (v) and d out = max v∈V d out (v). The previous work on our problem, due to Tschiatschek et al. (2017), presented an algorithm (OMegA) enjoying a (1 − e − 1 2∆ )-approximation guarantee when the underlying graph G is a directed acyclic graph (except for self-loops).
In this paper, we present two new algorithms: Sequence-Greedy and Hyper Sequence-Greedy, which also provably achieve constant factor approximations (when ∆ is constant), but their guarantees hold for general graphs and hypergraphs, respectively. Although the example given in Figure 1 is indeed a directed acyclic graph, many real-world problems require a general graph or hypergraph.
We showcase the utility of our algorithms on real world applications in movie recommendation, online link prediction, and the design of course sequences for massive open online courses (MOOCs). Furthermore, we show that even when the underlying graph is a directed acyclic graph, our general graph algorithm performs comparably well. Our experiments also demonstrate the power of being able to utilize hypergraphs and hyperedges.
Paper Organization. Our theoretical results are formally presented in Section 2, and their proofs can be found in Section 3. Details about the real-world applications we consider and the experimental results we obtain for these applications appear in Section 4.

General Graphs
In this section, we present our first algorithm, Sequence-Greedy. Sequence-Greedy is essentially the same as the classical greedy algorithm, but instead of choosing the most valuable vertex at each step, it chooses the most valuable valid edge.
More specifically, we start off with an empty sequence σ. At each step, we define E to be the set of all edges whose end point is not already in σ. We then greedily select the edge e ij ∈ E with maximum marginal gain Recall that e ij = (v i , v j ). That is, v i is the start point of e ij and v j is the endpoint. If e ij is a self-loop, then j = i and we append the single vertex v j to σ. Similarly, if j = i, but v i is already in σ, then we still only append v j . Finally, if e ij has two distinct vertices and neither of them is already in the sequence, we append v i and then v j to σ. This description is summarized in pseudo-code in Algorithm 1.
Theorem 2.1. The approximation ratio of Algorithm 1 is at least 1−e −(1− 1 k ) 2din+1 . Notice that the approximation guarantee of Algorithm 1 depends on the maximum in-degree d in . Intuitively, this is because Algorithm 1 builds σ by appending vertices to the end of the sequence. This means that each vertex we add to σ decreases the size of E by at most d in .
However, one can easily modify Algorithm 1 to build σ backwards by prepending vertices to the start of the sequence at each step. More specifically, we redefine E to be the set of all edges whose start point is not already in σ. Again we greedily select the edge e ij ∈ E that maximizes h e ij | E(σ) . Now, if e ij is a self-loop or v j is already in σ, we prepend the single vertex v i to the start of σ. Otherwise, if e ij has two distinct vertices and neither of them is already in the sequence, we prepend v j to σ first, and then prepend v i (thus, maintaining the order). This description is summarized in pseudo-code in Algorithm 2 with the main differences noted as comments.
Algorithm 2 gives the same approximation ratio as Algorithm 1, but with a dependence on d out instead of d in . Thus, if we run both the forwards and backwards version of Sequence-Greedy and take the maximum, we get an approximation ratio that depends on ∆ = min{d in , d out }. Furthermore, notice that the approximation ratio improves as k increases. Therefore, we can summarize the approximation ratio of Sequence-Greedy as follows. Theorem 2.2. As k → ∞, the approximation ratio of Sequence-Greedy approaches // vertices appended to beginning of σ 10 return σ.
This is comparable to the (1 − e − 1 2∆ )-approximation guarantee that is achieved by the existing algorithm OMegA, except that our guarantee is valid on general graphs, not just directed acyclic graphs.
In addition to this provable approximation ratio, Sequence-Greedy has the strong advantage of being computationally efficient. Both finding E and identifying the most valuable edge in E can be done in O(m) time, where m = |E|. Thus, Sequence-Greedy runs in O(km) time. This is faster than OMegA, which runs in O(m∆k 2 log k).

Extension to Hypergraphs
Extending our results to hypergraphs allows us to encode increasingly sophisticated models. For example, looking back on Figure 1, we see that the value of watching all three movies is just the sum of the pairwise additional values. However, hyperedges allow us to encode the fact that there is even further utility in watching the entire franchise in order.
From this point on, we replace the directed graph G with a directed hypergraph H = (V, E). Each edge e ∈ E of this directed hypergraph is a non-empty non-repeating sequence of vertices from V . Let V (e) be the set of vertices found in the hyperedge e. We assume that the intersection of a sequence and a set maintains the order of the sequence, which allows us to redefine E(σ) as Informally, E(σ) contains an edge e ∈ E if and only if all the vertices of e appear in σ in the proper order.
We also need to explain how the concept of in-degrees and out-degrees extends to hypergraphs. Self-loops contribute 1 to both the in-degree and the out-degree of that vertex. For all other edges e ∈ E such that v ∈ V (e), they will contribute 1 to d in (v) if v is not the first vertex of e, and 1 to d out (v) if v is not the last vertex of e. Finally, we define r as the maximum size of any edge in E. More formally, r = max e∈E |e|.
Aside from the above redefinition of E(σ), there is no need to make other changes in the definition of the objective function f . Specifically, it is still defined as f (σ) = h(E(σ)), where h : 2 E → R ≥0 is a non-negative monotone submodular function.
Our algorithm for hypergraphs, Hyper Sequence-Greedy, is an extension of the original Sequence-Greedy. Again, we start off with an empty sequence σ. This time, at each step we define E to be the set of all hyperedges e ∈ E such that σ ∩ V (e) is a prefix of e. The idea is that we can only select a hyperedge e if the vertices of e already in our sequence σ form a prefix of e, and they appear in σ in the right order.
We then select the hyperedge e * ∈ E that has the maximum marginal gain, and append the vertices of e * (that are not already in our sequence) to σ without changing their order. This description is summarized in pseudo-code in Algorithm 3.

Algorithm 3: Hyper Sequence-Greedy (Forward)
Input: Theorem 2.3. The approximation ratio of Algorithm 3 is at least 1−e −(1− r k ) rdin+1 . As with Sequence-Greedy, we can also run Hyper Sequence-Greedy backwards and take the maximum of the two results. In the backwards version, we prepend the vertices to the start of the sequence and we can only select a hyperedge e if V (e) ∩ σ is a suffix of e. Once more, this improves the approximation ratio in the sense that the dependence on d in is replaced with a dependence on ∆ = min{d in , d out }. Additionally notice that, as before, our approximation ratio improves as k increases. Thus, we can summarize the performance guarantee of Hyper Sequence-Greedy as follows. Theorem 2.4. As k → ∞, the approximation ratio of Hyper Sequence-Greedy approaches Remarks: One can observe that this hypergraph setting is a generalization of the previous directed graph setting. Specifically, Sequence-Greedy and the associated theory is a special case of Hyper Sequence-Greedy for r = 2. Furthermore, if r = 1 (i.e., our graph has only self-loops) then Hyper Sequence-Greedy is the same as the classical greedy algorithm.
We also note that while Algorithm 3 may select fewer than k vertices, the theoretical guarantees still hold. Furthermore, since we assume that h is monotone, we can safely select k vertices in practice every time. One simple heuristic for extending σ to k vertices is to only consider hyperedges with at most k − |σ| vertices.

Proof of Theorem 2.1
In this section we prove Theorem 2.1, however, before we get into the proof, let us first recall the theorem itself. Theorem 2.1. The approximation ratio of Algorithm 1 is at least 1−e −(1− 1 k ) 2din+1 . We begin the proof of the theorem by defining some additional notation. First, let be the number of iterations completed by the main loop of Algorithm 1, i.e., the number of iterations in which σ is updated. Then, for every 0 ≤ s ≤ , let σ s be the value of σ after s iterations of this loop have been performed. In other words, σ 0 is the initial value of σ when we first get to the loop, σ 1 is the value of σ at the end of the first iteration of the loop, and so on. Note that σ is the output of Algorithm 1. Additionally, we also denote by e s and E s , for every 1 ≤ s ≤ , the values assigned to the variables e ij and E, respectively, at iteration number s of the above loop. Finally, we also define as the real number of iterations performed by the above loop. Notice that = unless the algorithm exits the loop because E = ∅, in which case = + 1 and we define E = ∅.
Proof. Notice that the way σ is updated in each iteration of Algorithm 1 guarantees that e s ∈ E(σ s )\E(σ s−1 ). Moreover, since σ s−1 is a prefix of σ s , we also get E(σ s−1 ) ⊆ E(σ s ). Thus, where the inequality follows from the monotonicity of h.
Let σ * denote an arbitrary (but fixed) optimal sequence. We now need to prove a few properties of σ * .
Proof. Observe that σ * contains at most k vertices because it is feasible. This means that there can be at most d in k arcs that end in a vertex of σ * , which implies the observation since every arc of E(σ * ) must end at a vertex of σ * .
The next lemma studies the change in the value of (E(σ * ) ∩ E s ) ∪ E(σ s−1 ) as a function of s.
Proof. Recall that, for every 1 ≤ s ≤ , E s contains the arcs of E whose end point is not in σ s−1 . This definition implies that E s+1 ⊆ E s because σ s−1 is a prefix of σ s . In contrast, since σ s contains at most two vertices that do not appear in σ s−1 and each one of these vertices can be the end point of at most d in arcs, we also get |E s \ E s+1 | ≤ 2d in .
Using these observations and the submodularity of h, we can now derive the following inequality.
where the second inequality follows from the definition of e s which guarantees that it maximizes h(e s | E(σ s−1 )) among all the edges of E s .
It now remains to observe that where the first inequality follows from the monotonicity of h since the fact that σ s−1 is a prefix of σ s implies E(σ s−1 ) ⊆ E(σ s ).
We are now ready to combine all the above claims into a single lemma. Lemma 3.4. For every 1 ≤ s ≤ , the following two inequalities hold: Moreover, the first inequality holds also for s = .
Proof. Lemma 3.3 shows that, for every 1 ≤ t < , we have Adding up this inequality for 1 ≤ t < s gives us The first equality follows since the fact that σ 0 is empty implies E(σ 0 ) = ∅ and E(σ * ) ∩ E 1 = E(σ * ). Additionally, the second inequality follows from Observation 3.1, and the last inequality follows from the non-negativity of f . This proves that the first inequality of the lemma holds for every 1 ≤ s ≤ . In the rest of the proof we aim to prove the second inequality, and thus, assume 1 ≤ s ≤ .
Recall now that e s is the edge of E s maximizing h(e s | E(σ s−1 )) and that the size of E(σ * ) ∩ E s ⊆ E(σ * ) is at most d in k by Observation 3.2. Thus, by the submodularity of h, The lemma follows from this inequality since h(e s | E(σ s−1 )) lower bounds f (σ s ) − f (σ s−1 ) by Observation 3.1.
Proof. To prove the corollary, we prove by induction the stronger claim that, for every 0 ≤ s ≤ , For s = 0 this inequality is true since Assume now that the claim holds for s − 1 ≥ 0, and let us prove it for s. By Lemma 3.4, Plugging in the induction hypothesis, we get We are now ready to prove Theorem 2.1.
Proof of Theorem 2.1. First, we need to consider the case that Algorithm 1 terminates because the set E becomes empty. In this case E = ∅, which implies Using Lemma 3.4 for s = , this observation implies which proves the theorem. Thus, in the rest of the proof we may assume that Algorithm 1 terminates because σ reaches a size larger than k − 2.
Consider now the case that 2d in + 1 ≥ d in k.
In this case where the first inequality holds since σ 1 is a prefix of σ and the second inequality follows from Lemma 3.4. Thus, it remains to prove the theorem in the more interesting case of 2d in + 1 < d in k.
Observe that Plugging this inequality into Corollary 3.5 gives At this point we need a lower bound on . One can note that |σ| starts as 0, increases by at most 2 in each iteration of the loop of Algorithm 1 and ends up with a value of at least k − 1 by our assumption. Thus, the number of iterations must be at least (k − 1)/2. Plugging this observation into the previous inequality gives

Proof of Theorem 2.3
In this section we prove Theorem 2.3, however, before we get into the proof, let us first recall the theorem itself. Theorem 2.3. The approximation ratio of Algorithm 3 is at least 1−e −(1− r k ) rdin+1 . In the proof of this theorem we use the same notation that we used in Section 3.1 for analyzing Algorithm 1. One can observe that the proofs of Observation 3.1 and Observation 3.2 are unaffected by the differences between Algorithm 1 and Algorithm 3, and thus, these two observations can also be used for towards the proof of Theorem 2.3. The next lemma is analogous to Lemma 3.3. Lemma 3.6. For every 1 ≤ s < , h((E(σ * )∩E s+1 )∪E(σ s )) ≥ h((E(σ * )∩E s )∪E(σ s−1 ))−rd in ·h(e s | σ s−1 ).
Proof. Observe that the definition of E s guarantees that E s+1 ⊆ E s , for every 1 ≤ s < , because σ s−1 is a prefix of σ s . In contrast, every vertex u that appears in σ s but not in σ s−1 can be responsible for at most d in arcs of E s \ E s+1 because u can be responsible for excluding an arc from E s+1 only if u is a non-first vertex of the arc. Since σ s contains at most r vertices that do not appear in σ s−1 , this implies |E s \ E s+1 | ≤ rd in .
Using these observations and the submodularity of h, we can now derive the following inequality.
where the second inequality follows from the definition of e s which guarantees that it maximizes h(e s | E(σ s−1 )) among all the edges of E s .

It now remains to observe that
where the first inequality follows from the monotonicity of h since the fact that σ s−1 is a prefix of σ s implies E(σ s−1 ) ⊆ E(σ s ).
We are now ready to prove the following analog of Lemma 3.4. Lemma 3.7. For every 1 ≤ s ≤ , the following two inequalities hold: Moreover, the first inequality holds also for s = .
Proof. Lemma 3.6 shows that, for every 1 ≤ t < , we have

Adding up this inequality for 1 ≤ t < s gives us
The first equality follows since the fact that σ 0 is empty implies E(σ 0 ) = ∅ and E(σ * ) ∩ E 1 = E(σ * ). Additionally, the second inequality follows from Observation 3.1, and the last inequality follows from the non-negativity of f . This proves that the first inequality of the lemma holds for every 1 ≤ s ≤ . In the rest of the proof we aim to prove the second inequality, and thus, assume 1 ≤ s ≤ .
where the first inequality holds since σ 1 is a prefix of σ and the second inequality follows from Lemma 3.7. Thus, it remains to prove the theorem in the more interesting case of rd in + 1 < d in k.
Observe that Plugging this inequality into Corollary 3.8 gives At this point we need a lower bound on . One can note that |σ| starts as 0, increases by at most r in each iteration of the loop of Algorithm 3 and ends up with a value of at least k − r + 1 by our assumption. Thus, the number of iterations must be at least (k − r + 1)/r. Plugging this observation into the previous inequality gives

Movie Recommendation
In this application, we use the Movielens 1M dataset (Harper and Konstan, 2015) to recommend movies to users based on the films they have reviewed in the past. This dataset contains 1,000,209 anonymous, time-stamped ratings made by 6,040 users for 3,706 different movies. As in Tschiatschek et al. (2017), we do not want to predict a user's rating for a given movie, instead we want to predict which movies the user will review next.
One issue with this dataset is that the distribution of the number of ratings per user (shown in Figure 2a) has a very long tail, with the most prolific reviewer having reviewed 2,314 movies. In order for our data to be representative of the general population, we remove all users who have rated fewer than 20 movies or more than 50 movies. We also remove all movies with fewer than 1,000 reviews. This leaves us with 67,757 ratings made by 2,047 users for 207 different movies.
We first group and sort all the reviews by user and time-stamp, so that each user i has an associated sequence σ i of movies they have rated, where σ i j refers to the j th movie that user i has reviewed. We use a 90/10 training/testing split of the data and 10-fold cross validation.
For each user i in the test set (D test ), we use their first 8 movies as a given starting sequence S i = {σ i 1 . . . σ i 8 }. We want to use S i to select k movies that we think user i will review in the future. Therefore, for each user i, we build a hypergraph H i = (V, E i ), where V = {v 1 , . . . , v n } is the set of all movies, and E i is a set of hyperedges. Each hyperedge e s has value p s , where s is a movie sequence of length at most 3. Intuitively, p s is the conditional probability of reviewing the last movie in s given that the rest of the movies in s have already been reviewed in the proper order.
Since we use empirical frequencies in the training data to calculate these conditional probabilities, we may run into the issue of overfitting to rare sequences. To avoid this, we add a parameter d to the denominator of our calculation of each edge value. This will increase the relative value for sequences that appear more often. In this experiment, we use d = 20.  (1). We also highlight the size 3 hyperedge in green.
(c) Shows the performance of our algorithms against existing baselines for various cardinalities k.
More formally, define N s to be the number of users in the training set (D train ) that have reviewed all the movies in the sequence s in the proper order. Also define s l to be last element in s, and s to be s with s l removed. Now we can define the value of each edge e s as follows: (1) As mentioned above, the idea is that p s represents the conditional probability of reviewing s l given that all the movies in s have already been reviewed in the proper order. If user i has not reviewed all the movies in s , then we scale down the value of that edge by p s (i.e., the conditional probability of reviewing all the movies in s ).
Note that if s = ∅, then we define N s = |D train |, thus ensuring that this definition also applies for self-loops. A small subgraph of a fully trained hypergraph is shown in Figure 2b.
We use a probabilistic coverage utility function as our non-negative monotone submodular function h. Mathematically, We compare the performance of our algorithms, Sequence-Greedy and Hyper Sequence-Greedy, to the existing submodular sequence baseline (OMegA), as well as a naive baseline (Frequency), which just outputs the most popular movies that the user has not yet reviewed.
We also compare to a simple long short-term memory (LSTM) recurrent neural network (RNN). In addition to tuning parameters, we experimented with various frameworks such as training on uniform vs. variablesized sequences. In the end, we obtained the best results when we trained the neural network on the first k movies of each σ i , where the target is to predict the next k movies that the user i will review. In terms of the architecture, we use one layer of 512 LSTM nodes (with a dropout of 0.5) followed by a dense layer with a softmax activation that returns a 207 × 1 vector P , where entry P i is the probability that movie i will be reviewed. For each k, we simply return the k highest values in P . As before, we used a 90/10 training/testing split with 10-fold cross validation.
We hypothesize that, with enough data, neural networks will outperform our algorithms. However, with this comparison, we would like to show that in situations where data is relatively scarce, our algorithms are competitive with existing neural network frameworks, while also providing theoretical guarantees.
Let P i be our predicted sequence for the next k movies that user i will review, and let Q i be the next k movies that user i actually reviewed. Then, we define the accuracy of the prediction P i as follows.
In other words, τ (P i , Q i ) is the fraction of ordered pairs of the true answer Q i that appear in our prediction P i . Our experimental results in terms of this accuracy measure are summarized in Figure 2c.
These results showcase the power of using hypergraphs, as Hyper Sequence-Greedy consistently outperforms Sequence-Greedy. We also notice that Hyper Sequence-Greedy outperforms the score of the existing baseline OMegA by roughly 50%.

Online Link Prediction
In this application, we consider users who are searching through Wikipedia for some target article. Given a sequence of articles they have previously visited, we want to predict which link they will follow next. We use the Wikispeedia dataset (West et al., 2009), which consists of 51,138 completed search paths on a condensed version of Wikipedia that contains 4,604 articles and 119,882 links between them.
The setup for this problem is similar to that of section 4.1, so we will only go over the main differences. Again we will use a 90/10 training/testing split of the data with 10-fold cross validation.
For each training set D train , we build the underlying hypergraph H = (V, E). This time, V is the set of all articles, and E is a set of hyperedges e s where p s is the conditional probability of moving to article s l given that the user had just visited s in succession. Figure 3: Given a sequence of articles a Wikipedia user has visited, we want to predict the next link they will click. This bar chart shows the prediction accuracy, as well as the objective function value, of various algorithms.
For each testing set D test , we will use the last article in each completed path as the target, and the previous 3 articles as the given sequence. This means we will be able to use hyperedges of up to size 4. We employ the same probabilistic coverage function h and the same baseline comparisons as in Section 4.1. For this application, our neural network was most effective when we used a single layer of 32 LSTM nodes (with a dropout of 0.2). Our results are shown in Figure 3.
In this case, Hyper Sequence-Greedy exhibits the best performance. We see that the simple neural network implementation is outperformed by Hyper Sequence-Greedy as well as by some of the baselines. This is likely a result of the data in this experiment being more sparse. Although in this application we technically have more data than in the previous one, here we attempt to choose between 4,604 articles, rather than just 207 movies.
We also show the results that the various algorithms achieve when evaluated on our objective function f (σ) = h E(σ) . Asides from the LSTM-RNN, which doesn't consider the objective function at all, we see that the objective function values are relatively in line with the prediction accuracy. This demonstrates that the probabilistic coverage function was a good choice for the objective function.

Course Sequence Design
In this final application we want to use historical enrollment data in Massive Open Online Courses (MOOCs) to generate a sequence of courses that we think would be of interest to users. We use a publicly available dataset (Ho et al., 2014) that covers the first year of open online courses offered by edX. The dataset consists of 641,139 registrations from 476,532 unique users across 13 different online courses offered by Harvard and MIT. Amongst a plethora of other statistics, the data contains information on when each user first and last accessed each course, how many course chapters they accessed, and the grade they achieved if they were ultimately certified (i.e., fully completed) in the course.
One natural way to think about the value of a sequence of courses is in terms of prerequisites. That is, in what order should we offer courses to students in order to help them learn as much as possible. This model comes with a natural measure of success as well, which is the grade each student gets in each course. Unfortunately, out of the 476,532 unique users in this dataset only 180 were certified (and thus, received grades) in 3 or more courses. Furthermore, this dataset only contains 13 different courses (shown in Figure  4a), none of which are logical prerequisites for each other.
Instead, we can think about a sequence of courses being valuable if they will all be interesting to a user who registers for them. Similarly to the prerequisites model where the order of courses affects the user's grade, the order in which a user registers for courses should also affect their interest. In this dataset, we can measure interest by the percentage of the course that the user accessed. In particular, we say that if a user was interested in a course i if she accessed at least one-third of all the chapters for course i.
As always, we need to build the underlying hypergraph H = (V, E) for each training set. In this case, V is the set of all courses and E is a set of hyperedges of form e s , where s is a sequence of at most 3 courses and p s is the probability that a user will be interested in s l given that she previously showed interest in s in the proper order. Recall that s l is the last course in s, and s is the sequence obtained from s after deleting s l . As in section 4.1, we also use a parameter d to avoid overfitting to rare sequences. In this case we use d = 100. However, unlike Section 4.1, we are not making recommendations based on a user's history. Instead each algorithm will use the underlying hypergraph to build a single sequence σ. Since we are not starting with any given sequence, we can finally run Sequence-Greedy and Hyper Sequence-Greedy both forwards and backwards, and take the maximum of the two results.
Different users will naturally have different interests, so it is unreasonable to expect that any single sequence σ will work for all users. However, if σ is a "good" sequence, we could expect that users who start all the courses in σ in the correct order ultimately end up showing interest in those courses. Intuitively, the idea is that σ should capture a sequence of courses with some common theme and present them in the best possible order. Therefore, if a user begins all the courses in σ they likely have some interest in this common theme.