--- title: "Order-Dependent Event Models for Agent Interactions" authors: - "Debarun Bhattacharjya" - "Tian Gao" - "Dharmashankar Subramanian" doi: "10.24963/ijcai.2020/274" url: "https://ijcai.org/proceedings/2020/274" pdf: "https://ijcai.org/proceedings/2020/0274.pdf" venue: "Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence" year: 2020 pages: "1977-1983" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Multi-agent Learning" - "Machine Learning: Learning Graphical Models" - "Data Mining: Mining Spatial, Temporal Data" --- # Order-Dependent Event Models for Agent Interactions Debarun Bhattacharjya, Tian Gao, Dharmashankar Subramanian *Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence*, pages 1977-1983. DOI: [10.24963/ijcai.2020/274](https://doi.org/10.24963/ijcai.2020/274) ## Abstract In multivariate event data, the instantaneous rate of an event's occurrence may be sensitive to the temporal sequence in which other influencing events have occurred in the history. For example, an agent’s actions are typically driven by preceding actions taken by the agent as well as those of other relevant agents in some order. We introduce a novel statistical/causal model for capturing such an order-sensitive historical dependence, where an event’s arrival rate is determined by the order in which its underlying causal events have occurred in the recent past. We propose an algorithm to discover these causal events and learn the most influential orders using time-stamped event occurrence data. We show that the proposed model fits various event datasets involving single as well as multiple agents better than baseline models. We also illustrate potentially useful insights from our proposed model for an analyst during the discovery process through analysis on a real-world political event dataset. ## Full text ## 1 Introduction There has been an explosion of datasets in recent years involving events of various types occurring irregularly over the timeline. Many of these involve the actions of single or multiple agents, potentially along with other pertinent observations; examples include electronic health records and wearable device data, socio-political event data, financial data around trades by automated agents, and user behavior in online retail and entertainment. Such datasets enable statistical approaches for learning about agent actions/interactions [Remondino and Correndo, 2005; Grover et al., 2018]. In this paper, we treat agent actions as event occurrences and deploy machine learning techniques to capture the statistical/causal relationships between various types of events. Our model explicitly aims to capture the effect of the order in which preceding events have occurred. Specifically, an event's arrival rate is assumed to be determined by the recent historical order in which its underlying causal events ∗DISTRIBUTION STATEMENT A. Approved for public re- have occurred. Our work fits within the high-level framework of graphical event models [Didelez, 2008; Meek, 2014; Gunawardana and Meek, 2016], which are continuous-time graphical representations of marked point processes [Cox and Lewis, 1972; Aalen et al., 2008]. Although the proposed model is fairly general and widely applicable, our emphasis on order-dependence is motivated by real-world situations pertaining to agent interactions. As an illustration, consider two countries X and Y who have historically been in conflict. In politics, an escalating sequence of actions is often more likely to result in extreme actions such as declaration of war. For instance, if X first makes a negative statement about Y and then Y threatens X, it may be more likely for X to retaliate strongly and declare war on Y than if the reverse order of actions had occurred. Explicitly recognizing the order of preceding events may also be important for modeling the behavior of individual agents. For instance, the sequence of a big loss followed by a big win may induce different behaviors in a gambler compared to the reverse sequence, or for that matter compared to the situation where they only face either a big loss or a big win. Modeling and learning about the influence of causal orders from event data could provide an analyst with an enhanced understanding of the underlying process. Contributions. Our primary contributions are: (1) the formulation of a novel order-dependent event model that explicitly distinguishes the causal impact of different orders in an event dataset. As far as we are aware, this is the first model to simultaneously take a marked point process view of an event dataset and consider preceding causal event orders; (2) an efficient algorithm for learning the proposed model from an event dataset; (3) an experimental comparison with relevant baselines on event datasets involving both single and multiple agents; and (4) investigative analysis on a political event dataset extract that illustrates the benefits of explicitly identifying order-dependence during the discovery process. ## 2 Model Formulation We first introduce some basic notation and provide relevant background before describing details of our proposed model. ## 2.1 Notation &Background An event dataset (or event stream) is a sequence of timestamped events of the form D = {(li, ti)}Ni=1 , where ti is the occurrence time of the ith event, ti ∈ R+, assumed temporally ordered between start time t0 = 0 and final time tN+1 = T , and li is an event label/type belonging to an alphabet L with cardinality M = |L|. For simplicity, all equations assume a single event stream but they can be easily extended to multiple independent event streams. Example 1. The event dataset in Fig. 1(a) will be a running example to illustrate the concepts. There are N = 13 events over event label set L = {A, B, C} with cardinality M = 3 over a period of around a month (T = 30 days). A mathematically principled way to model multivariate event streams is through a marked point process. This captures the dynamics of events occurring in continuous time using conditional intensity functions, which are time-varying quantities that measure the rate at which an event label occurs. In general, the conditional intensity for event label X at time t can be written as a function of the history at that time, ht, i.e. it is denoted λx(t|ht) where ht = {(li, ti) : ti < t} represents all the preceding events at time t. Graphical event models (GEMs) [Didelez, 2008; Gunawardana and Meek, 2016] provide a framework for how various event labels are generated over time, given the historical occurrences of their parents in some underlying graph. They are graphical representations of a marked point process over event labels, analogous to how Bayesian networks are graphical representations of joint distributions over random variables [Pearl, 2014]. A GEM includes a directed graph G = (L, E), which has nodes for every event label L and directed edges E represented as ordered pairs from L × L. The conditional intensity for an arbitrary label X at any time t depends only on historical occurrences of its parent event labels, implying that λx(t|ht) = λx(t|[h(U)]t), where U are X's parents and [h(U)]t is the history restricted to labels in set U, [h(U)]t = {(li, ti) : ti < t, li ∈ U}. It is important to reiterate that a GEM is merely a highlevel framework - more information about the historical dependence of conditional intensity rates needs to be provided before the model can even be fully specified and subsequently learned. In this work we propose a specific model where the order in the history plays a critical role. ## 2.2 An Order-dependent Event Model We are interested in a model where the historical order of the occurrences of a node's parent event labels in a GEM could potentially affect the rate at which it occurs at any time. Since the same event label could occur several times in the history in an event dataset, this could lead to an infinite number of distinct historical possibilities. We therefore introduce a masking function to disregard specific instances of events that repeat, only retaining distinct event occurrences. Definition 1. A masking function φ(·) takes a sequence of event tuples as input, and returns a sub-sequence where a label is never repeated. Formally, φ(·) takes as input some temporally ordered sequence s = {(lj, tj)} and returns s′ = {(lk, tk) ∈ s : lk ̸= lm for k ̸= m}. The event label order resulting from applying this masking function is obtained from ordering the labels in s′ in time, i.e. {lk : (lk, tk) ∈ s′ , tk < tm∀k < m}. Here we only consider two cases of tuple masking function φ(·) due to their simplicity and potential applicability across domains: the 'first' and 'last' cases, depending on whether only the first or last occurrence of an event label in a sequence is retained to determine order. We imagine that a case's suitability depends on the application under consideration. Example 2 (cont.). Consider label C's occurrence in Fig. 1(a) at time t = 10. If the 'first' masking function is applied to the history at this time, the resulting historical order is B, C, A, whereas 'last' results in order B, A, C. Definition 2. An order instantiation for a set of labels Z is a permutation of a subset of Z. The order instantiation at time t in an event dataset D over a preceding time window w can be determined by applying masking function φ(·) to events restricted to labels Z occurring within [max (t - w, 0), t). Example 3 (cont.). Suppose C has parents A and B, like in Fig. 1(b). Fig. 1(a) shows the order instantiations at each of the five occurrences of event label C over its parent labels for a window of 5 days - there are two occurrences of the order A, B, two of order B and one of B, A. In this particular situation, both the 'first' and 'last' masking function cases result in identical order instantiations. We can now formalize the proposed model: Definition 3. An ordinal graphical event model (OGEM) for event label set L includes: - A graph G where there is a node for every event label. - Windows for every node in G, W = {wX : X ∈ L}. - A set of conditional intensity rate parameters Λ, one for every node and possible order instantiation with respect to the node's parents, Λ = {ΛX : X ∈ L} = {λx|o : X ∈ L, ∀o}. Here o denotes an order instantiation, which is a permutation of a subset of X's parents U - there are ∑|U| i=0 |U|! i! possible orders. Example 4 (cont.). Fig. 1(b) depicts an example OGEM over L = {A,B,C}. Note that the graph can be cyclic and even have self-loops indicating self-dependence. The conditional intensity parameters are also shown; for instance, there are 5 parameters for C - one for every order instantiation of its parents {A,B}. Parameter λC|A is the rate at which event label C occurs given that only A (among its parents) has occurred in the recent preceding window wC, whereas λC|A,B is the rate when the recent history involves an occurrence of A followed by B. While learning from data, the order is determined by the masking function φ(·). The closest model to an OGEM is the proximal GEM (PGEM) [Bhattacharjya et al., 2018], where an event label's conditional intensity rate depends only on whether or not its parents have occurred in some recent time window. We next formalize that a PGEM is unable to distinguish conditional intensity rates from different parental orders. Theorem 4. Suppose event label X with parents U is generated from order-dependent conditional intensity rates {λx|o : ∀o}, where o is an order instantiation of U. For two orders o′ and o′′ over the same subset of U s.t. λx|o′ ̸= λx|o′′ , a PGEM is unable to distinguish between these rates. Figure 1: (a) Example event stream with N = 13 events of M = 3 types of events occurring over T = 30 days. The figure also indicates the order instantiations for each occurrence of event label C, assuming that C has parents A and B and for a window wC = 5. (b) Illustrative ordinal graphical event model with 3 nodes (event labels), each with a window and a set of conditional intensity parameters. ![Image](https://ijcai.org/proceedings/2020/fulltext/274/image_000000_d9b094fa016fea3d565e7f90d932a4639ed5ef30f5e6ecb7ab56520859798a78.png) ## Algorithm 1 Ordinal Summary Statistics ``` 1: procedure SUMMARYSTATS(event label X, parents U, window wX, masking function φ(·), dataset D) 2: Active history h ← ∅ 3: N(x; o) ← 0, D(o) ← 0, ∀o 4: D(∅) += t1 - t0 ▷ Increment empty set dur. 5: for (li, ti) ∈ D do ▷ Scan all events in dataset 6: if li ∈ U then 7: Append (li, ti) to h 8: o = UpdateOrder(h,φ(·) ) 9: if li ==X then 10: N(x; o) += 1 ▷ Increment count 11: Set current time tc = ti 12: for (lj , tj ) ∈ h do ▷ Scan events in active history 13: Set inactive time t∗ = tj +wX 14: if t∗ ≥ ti+1 then 15: Break 16: else ▷ Stay until some history is active 17: D(o) += t∗ - tc ▷ Increment duration 18: Remove this event (lj, tj) from h 19: o = UpdateOrder(h,φ(·) ) 20: Set current time tc = t∗ 21: D(o) += ti+1 - tc ▷ Increment duration 22: Return counts N(x; o) and durations D(o), ∀o ``` the maximum likelihood estimates for conditional intensity parameters are ˆλx|o = N(x;o) D(o) . Thus, if the parents of a node are known, it is straightforward to compute the conditional intensity rates using the summary statistics. In Algo. 1, we outline how to scan the entire dataset to compute the required counts N(x; o) and durations D(o) for an event label X, given its parents U, window wX and a masking function φ(·). Computing counts is relatively easy if the order instantiation at the current time is known - whenever the label under consideration X is encountered, the relevant count is incremented by one (lines 9-10). Computing durations is more involved and requires maintaining an active history h. When a parent label is encountered, the corresponding event is appended to h (lines 6-7). Since the order instantiation could potentially change several times between event occurrences, the entire duration between these epochs needs to be appropriately partitioned across order instantiations. These changes are identified by scanning h and determining when a historical event becomes inactive Proof. Suppose orders o′ and o′′ are over variables K ⊆ U variables. While learning from a dataset, both orders map to the binary parental instantiation u of U where variables in K and U \ K are 1 and 0 respectively. Thus, both orders contribute to the estimate for ˆλx|u in the PGEM, which is unable to identify the true parameters λx|o′ and λx|o′′ . An OGEM is intended to explicitly capture the effect of the order of an event label's causes, unlike prior literature like PGEM that considers order-neutral event models. For instance, orders that are particularly influential in causing an event would have relatively high conditional intensity parameters. Understanding these influences could be beneficial for analysts during the process of discovery. ## 3 Learning We present an approach for learning an OGEM from an event dataset D. We treat the windows W as hyper-parameters, and focus on learning the graph G and conditional intensity parameters Λ. Like any other GEM, the OGEM graph is potentially cyclic, therefore the parents and parameters for each node/event label can be learned individually. We first show how to learn conditional intensities {λx|o : ∀o} for a node X given its parents U (in G), which relies on computing ordinal summary statistics (Algorithm 1), and then briefly summarize a heuristic graph search method to learn X's parents U. ## 3.1 Learning Parameters An OGEM is a particular kind of GEM where the conditional intensity rates are piece-wise constant over time, with rate changes occurring whenever there is a change in the order instantiation in history. The log likelihood of any particular event label X for an event dataset D can therefore be computed using summary statistics of counts and durations in D, as well as the model's conditional intensity rates: where N(x; o) refers to the number of times X is observed in the dataset and that the order instantiation o is true in the relevant preceding window wX, and D(o) is the duration over the entire time period where the condition o is true. The fact that the counts and durations depend on the window wX is hidden in the notation for the sake of simplicity. From equation (1), before the next event occurrence (loop in lines 12-20). A subroutine 'UpdateOrder' applies the masking function to the active history and returns an order whenever the active history is modified (lines 8 and 19). Example 5 (cont.). Algo. 1 was run on the event dataset in Figure 1(a) to obtain counts and durations for event label C, with parents {A, B} and wC = 5 days. The maximum likelihood estimates of intensity rates are: ˆλC|∅ = 0, ˆλC|A = 0, ˆλC|B = 0.18, ˆλC|A,B = 0.17, ˆλC|B,A = 0.33. Similar to earlier, here the numbers are identical regardless of whether the 'first' or 'last' masking function is used. In this particular example, the rate at which C happens almost doubles when B happens before A as compared to the reverse order. It may be possible for some order instantiations to never be observed in the data, resulting in counts (and therefore estimates for conditional intensities) of zero. This issue can be severe when the number of parents is large, since the number of OGEM parameters increases super-exponentially in the number of parents. As we describe in the next sub-section, our parent search approach restricts model complexity, forcing the learner to choose a small number of parents for a small dataset, making it more likely to have sufficient support in the data. For our experiments, we deal with this issue by setting the conditional intensity rate to some small default rate, denoted λ0 , whenever an order instantiation is not observed in the train set. This is treated as a model hyper-parameter. ## 3.2 Learning Parents We use a score-and-search approach to find the parents of each node and therefore the underlying graph G. A score is used to incorporate model complexity along with the log likelihood on a dataset. For instance, the Bayesian information criterion (BIC) score for an event label X with parents U is: where logLX (D) is the log likelihood for X from equation (1) computed at the maximum likelihood estimates for rates, |ΛX| is the number of free parameters (conditional intensity rates) for X in the model and γ is a penalty weight on the complexity (second) term. Unless otherwise specified, γ is set to 1. The overall score of a graph G is S(G) = ∑X SX(U; D) since the scores are decomposable. For our experiments, we use a forward and backward search procedure to iteratively find the best parental set U for each event label X. Specifically, we iteratively add one candidate event label Z to U and test if it results in a better score SX(U∪ Z) than the current best score. If so, we update U and query the next Z. After finishing adding as many nodes as beneficial for the score, we then iteratively test if removing an event label Z fromUwould improve the score, updating U if it does indeed result in a better score. Such a greedy procedure is popular for learning probabilistic graphical models in general due to its efficiency and consistency, i.e. ability to recover the true graph with asymptotic data. Theorem 5. A forward backward score-based learning algorithm for OGEM graph G and parameters Λ given hyperparameters W with summary statistics computed using Algo. 1 with either the 'first' or 'last' masking function has worst case time complexity O(M 3N), where M and N are the number of event labels and events respectively. Proof. For a single node, Algo. 1 runs in O(N) time, assuming the 'UpdateOrder' subroutine is O(1); this is possible for both the masking function cases considered. The worst case in the forward (backward) search is that all nodes will be added (removed), which is O(M 2 ). This is repeated for all M nodes to complete the entire graph and model. Theorem 6. Let G ′ be the learned graph from a forward backward score-based structure learning algorithm for OGEM graph G. Under the no detailed balance assumption [Gunawardana and Meek, 2016], with sufficient data, P(G ′ = G) → 1 as T →∞. Proof. OGEMs fall within the piece-wise constant intensity model (PCIM) class of GEMs; we refer the reader to prior work [Gunawardana and Meek, 2016]. ## 4 Experiments We demonstrate the efficacy of OGEMs using the following select datasets involving single and multiple agents. ## 4.1 Datasets ICEWS [O'Brien, 2010]. Socio-political events such as in the Integrated Crisis and Early Warning System (ICEWS) political event dataset are an important real-world example of numerous, asynchronous agent interaction events on a timeline. ICEWS involves dyadic events where a source actor performs an action on a target actor, for instance 'Police (Brazil) Assault Protester (Brazil).' Actors and actions are coded according to the Conflict and Mediation Event Observations (CAMEO) ontology, which was created for interactions among domestic and international actors [Gerner et al., 2002]. For our first experiment, we used 4 out of 5 countries from the ICEWS extract in Bhattacharjya et al. [2018], which includes events involving 5 types of actors and 5 types of actions, occurring from Jan 1, 2012 to Dec 31, 2015. (One country was omitted due to the inconsistency between event labels while splitting the data into three sets for experiments.) Mimic-II [Saeed et al., 2011]. These are patient electronic health records from Intensive Care Unit visits over 7 years. Each patient experiences a sequence of visit events, where each event involves a time stamp and diagnosis. We filter out small sequences to obtain 650 patients with 204 disease types. Diabetes [Frank and Asuncion, 2010]. Events for around 70 diabetic patients are considered: these include different types of meal ingestion, exercise and insulin dosage, along with two additional processed event labels corresponding to the increase and decrease of blood glucose measurement levels. These latter events are obtained after discretization of blood glucose measurements into three states. LinkedIn [Xu et al., 2017]. This includes employment and (when applicable) college enrollment related information of 2489 anonymous LinkedIn users. Each event stream includes a user's time-stamped records of professional experience, such as joining a new role in a company. We filter the data to popular companies and end up with 1000 users. Table 1: Log likelihood for the models on the test sets. | Dataset | PGEM | OGEM | NHP | |-----------|----------|----------|----------| | ICEWS | | | | | Argentina | -1386.05 | -1369 | -1338.65 | | Brazil | -2000.47 | -2057.45 | -1892.57 | | Colombia | -534.46 | -517.82 | -559.61 | | Mexico | -796.50 | -771.17 | -919.82 | | Mimic | -495.41 | -476.07 | - | | Diabetes | -2966.23 | -2883.62 | - | | LinkedIn | -1479.26 | -1478.38 | - | ## 4.2 Model Fit We conduct an experiment to evaluate how well the proposed model fits the afore-mentioned datasets. Experimental Setup. Each dataset is split into three sets: train (70%), dev (15%) and test (15%), only retaining event labels that are common to all three splits. Single stream datasets like ICEWS countries are split by time, e.g. if T = 1000 days, then events up to time 700 days are in train. Multiple stream datasets like LinkedIn are split by stream id, e.g. for K = 1000 users, streams for 700 of them constitute the train set. A model's performance is measured by the log likelihood on the held-out test set. During both training and testing, we disallow positive log likelihoods to minimize over fitting, capping it at zero for any node. Hyper-parameter choices for OGEM and the baselines are as follows: - OGEM: We search over a default rate hyper-parameter grid of λ0 = {0.001, 0.005, 0.01, 0.05, 0.1}. Window hyper-parameter grids are dataset specific, chosen as: - ICEWS: wX={1, 3, 7, 10, 15, 30, 60} (days) ∀X - Mimic: wX={0.1, 0.2, 0.5, 1, 1.5, 2, 5} (years) ∀X - Diabetes: wX={0.01, 0.05, 0.1, 0.5, 1, 5} (days) ∀X - LinkedIn: wX={2, 5, 7, 10, 15, 20} (years) ∀X - PGEM: The closest baseline is the proximal GEM, which allows different windows for different parents but does not distinguish between orders of causal events. We deploy the learning approach in Bhattacharjya et al. [2018], which also identifies windows using a heuristic. We use left limiting parameter ϵ = 0.001 and default rate λ0 as the only hyper-parameter with the same grid as OGEM. - NHP: Primarily just for reference, we also learn a neural Hawkes process [Mei and Eisner, 2017], a state-of-the-art neural architecture for event models. Neural networks are expected to do much better than fully parametric ones on the model fitting task due to the large number of parameters. NHP does not however learn a graphical model and is less interpretable than the other models considered, making it less useful for discovery. For NHP, the only hyperparameter is the number of epochs for training. For all models, the optimal hyper-parameter setting is chosen by training models under various settings using the train set and finding the best performing setting on the dev set. The optimal trained model is then evaluated on the test set. Results. Table 1 compares the log likelihood evaluated on test sets across models. In the OGEM column, we show the masking function case ('first'/'last') that performs better. Aside from Brazil, where PGEM performs well, OGEM exhibits superior performance. OGEM also does reasonably compared to NHP, beating it on two of the four ICEWS countries; NHP was anticipated to perform substantially better on this task. Note that NHP was not run on the multiple stream datasets because there is a peculiarity about these datasets that makes it an inappropriate baseline: they are processed to almost always have events at time t = 0, and the neural network exploits this by always artificially spiking the conditional intensity rate at the start time. As a result, we only compare OGEM with PGEM for these datasets. ## 4.3 Causal Orders Analysis The power of the OGEM is that it is able to reveal orders of causal events that are influential for a particular event of interest. Here we investigate an application of OGEMs for social unrest related events on an extract of ICEWS data from January 1, 2006 till December 31, 2010. We restrict attention to the following six actors: Police, Citizen, Government, Head of Government, Protester, Military; these are among the most frequently participating actors for these countries. Experimental Setup. We consider the social unrest event label 'Police; Fight; Citizen' and learn its OGEM parents and parameters, using event data corresponding to three Latin American countries - Argentina, Mexico and Venezuela. Other events were also studied but results for only one event are provided as an illustration due to space restrictions. For this analysis, we use the 'first' masking function φ(·), penalty weight γ = 0.1 on the complexity term, default rate λ0 = 0.001 and window wX = 30 days. Results. Selected results fromour analysis are shown in Table 2. Each column in the table ranks the orders (sequences) of event labels of the identified parents based on the model's estimated conditional intensity rates. We arbitrarily choose three orders each to display. We point the reader's attention to some observations about the ways in which the preceding order affects the rate of an interaction event in ICEWS: - In both Argentina and Mexico, missing preceding events have an impact on the rate. For instance, when the military cooperates materially with the police in Argentina, for instance to provide arms - and importantly when no other causal events occur - the rate of a police fight-related event is very high. Contrast this with the bottom order where the rate decreases, perhaps because the police's resources are consumed elsewhere. - The impact of the order of two events is prominent for Venezuela where switching the order of two parent events alters the rate substantially. Here the recent action of a citizen making a (presumably negative) statement about the government after the government makes an international statement results in a higher rate of the event of interest than if the international government statement comes later. This is an example of the finer expressiveness of OGEMs, in accordance with Theorem 4. Table 2: Ranking the causal effect of sequences for the event of interest 'Police; Fight; Citizen' by intensity rate. | Argentina | | Mexico | Venezuela | | |-----------------------------------------------------------------|------|---------------------------------------------------------------|----------------------------------------------------------------------------|------| | 1. (Military; Material Coop.; Police) | 4 | 1. (Citizen; Yield; Military) 0.5 | 1. (Govt.; Statement; Head of Govt.-Mexico) 2. (Citizen; Statement; Govt.) | 0.71 | | 1. (Citizen; Reject; Head of Govt.) 2. (Police; Fight; Govt.) | 0.5 | 1. (Citizen; Yield; Military) 0.31 2. (Citizen; Demand; Govt) | 1. (Citizen; Statement; Govt.) 2. (Govt.; Statement; Head of Govt.-Mexico) | 0.04 | | 1. (Military; Material Coop.; Police) 2. (Police; Fight; Govt.) | 0.12 | 1. (Citizen; Demand; Govt) 0.08 | 1. (Citizen; Statement; Govt.) | 0.04 | ## 5 RelatedWork Our proposed model leverages data in the form of streams of irregularly occurring time-stamped events. We briefly summarize the most relevant literature around event modeling. ## 5.1 Event Sequences Sequences of events go by various terms, including episodes [Mannila et al., 1997], narratives [Chambers and Jurafsky, 2008], storylines [Radinsky and Horvitz, 2013] and scenarios [Hashimoto et al., 2014]. (Here we have used the term 'order' or 'sequence'.) Several analytical domains have long pursued event sequence models, such as in point processes in statistics [Cox and Lewis, 1972] and frequent episode mining in data mining [Mannila et al., 1997]. Predicting from sequences without time-stamped information has also been widely studied in machine learning [Rudin et al., 2012] and in natural language processing, particularly for narrative cloze and related tasks [Radinsky and Horvitz, 2013; Granroth-Wilding and Clark, 2016]. Our work is different from this more recent literature in that: 1) we take continuous-time event streams as input, and 2) we pursue a graphical modeling approach where the sequence of only the underlying causes matters. ## 5.2 Temporal Point Processes and Graphs The framework of graphical event models (GEMs) [Didelez, 2008; Meek, 2014] captures the inter-event dependency in continuous-time event data by representing a marked point process, which models event dynamics using conditional intensity functions. The specific variants of GEMs typically differ in how they parametrize intensity functions, ex: through generalized linear models [Rajaram et al., 2005], decision trees [Gunawardana et al., 2011], forests [Weiss and Page, 2013] and proximal windows [Bhattacharjya et al., 2018]. Due to the success of deep learning in many domains, deep neural network methods have also been proposed to model event streams, such as recurrent neural network models [Xiao et al., 2017; Du et al., 2016] and neural Hawkes processes [Mei and Eisner, 2017]. A related stream of work considers probabilistic generative models for relational event models [DuBois and Smyth, 2010; Schein et al., 2015], where events have a dyadic character, i.e. they can be described in terms of a pair of actors (say, sender and receiver) that are coupled with a certain relation (say, action) like in the ICEWS dataset. Note that there are other general graphical representations that are peripherally related to our work, including discrete time models such as dynamic Bayesian networks [Dean and Kanazawa, 1989] and graphs for time series [Eichler, 1999]. Specialized graphs for multi-agent problems have also been proposed [Grover et al., 2018; Bhargava and Williams, 2019]. However, GEMs related work appears to be the most relevant graphical modeling literature; we have shown how our proposed model fits within the broader GEMs framework. ## 6 Conclusions We have introduced a novel model for capturing orderdependent causal influences in event datasets, motivated by representing the behavior of single or multiple agents using only data about their actions/interactions. This provides a data-driven and domain-agnostic alternative to traditional approaches involving hand-crafted models requiring prior domain knowledge. We presented an efficient algorithm for learning the graphical structure and parameters of an OGEM, demonstrating comparable or better model fitting performance than baselines on various benchmark datasets. An OGEM's ability to expose the order-sensitive nature of the rate of observing certain agent interactions provides a facet of analysis that would not be attained by alternate order-neutral graphical event models. This was highlighted theoretically but also experimentally, through an investigation conducted on agent interactions in the ICEWS political event dataset. We believe that analysts in professions such as business, intelligence and finance would find such an interpretable model and its order-related insights beneficial. A major limitation in the current OGEM formulation is that the number of parameters is super-exponential in the number of parents. While we have partially addressed this issue here by penalizing model complexity, this opens up possibilities for future work around more compact parameter representations. Another potential challenge is around the choice of masking function to determine historical order; in domains where events recur rapidly, the 'first' and 'last' cases may be inappropriate and possibly even subvert causal analysis with poorly chosen windows. Another line of future work would therefore be to automatically learn some of the hyperparameters, notably the windows of historical dependence. ## Acknowledgments The authors thank the anonymous reviewers for their valuable feedback. This research was developed with funding from the Defense Advanced Research Projects Agency (DARPA). The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. ## References 1. [Aalen et al., 2008] O. O. Aalen, O. Borgan, and H. K. Gjessing. Survival and Event History Analysis: A Process Point of View. Springer Science & Business Media, New York, NY, USA, 2008. 2. [Bhargava and Williams, 2019] N. Bhargava and B. Williams. Mul- tiagent disjunctive temporal networks. In Proceedings of the In- ternational Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pages 458-466, 2019. 3. [Bhattacharjya et al., 2018] D. Bhattacharjya, D. Subramanian, and T. Gao. Proximal graphical event models. In Advances in Neural Information Processing Systems (NIPS), pages 8147-8156, 2018. 4. [Chambers and Jurafsky, 2008] N. Chambers and D. Jurafsky. Un- supervised learning of narrative event chains. In Proceedings of the Annual Meeting of the Association for Computational Lin- guistics (ACL), volume 94305, pages 789-797, 2008. 5. [Cox and Lewis, 1972] D. R. Cox and P. A. W. Lewis. Multivariate point processes. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 3: Probabil- ity Theory, pages 401-448, 1972. 6. [Dean and Kanazawa, 1989] T. Dean and K. Kanazawa. A model for reasoning about persistence and causation. Computational Intelligence, 5:142-150, 1989. 7. [Didelez, 2008] V. Didelez. Graphical models for marked point processes based on local independence. Journal of the Royal Sta- tistical Society, Ser. B, 70(1):245-264, 2008. 8. [Du et al., 2016] N. Du, H. Dai, R. Trivedi, U. Upadhyay, M. Gomez-Rodriguez, and L. Song. Recurrent marked tempo- ral point processes: Embedding event history to vector. In Pro- ceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 1555-1564, 2016. 9. [DuBois and Smyth, 2010] C. DuBois and P. Smyth. Modeling re- lational events via latent classes. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 803-812, 2010. 10. [Eichler, 1999] M. Eichler. Graphical Models in Time Series Anal- ysis. PhD thesis, University of Heidelberg, Germany, 1999. 11. [Frank and Asuncion, 2010] A. Frank and A. Asuncion. UCI ma- chine learning repository, 2010. 12. [Gerner et al., 2002] D. J. Gerner, P. A. Schrodt, O. Yilmaz, and R. Abu-Jabr. Conflict and mediation event observations (CAMEO): A new event data framework for the analysis of for- eign policy interactions. International Studies Association (ISA) Annual Convention, 2002. 13. [Granroth-Wilding and Clark, 2016] M. Granroth-Wilding and S. Clark. What happens next? Event prediction using a compo- sitional neural network model. In Proceedings of the Conference on Artificial Intelligence (AAAI), pages 272-2733, 2016. 14. [Grover et al., 2018] A. Grover, M. Al-Shedivat, J. K. Gupta, Y. Burda, and H. Edwards. Learning policy representations in multiagent systems. In Proceedings of the International Confer- ence on Machine Learning (ICML), pages 1797-1806, 2018. 15. [Gunawardana and Meek, 2016] A. Gunawardana and C. Meek. Universal models of multivariate temporal point processes. In Proceedings of the International Conference on Artificial Intelli- gence and Statistics (AISTATS), pages 556-563, 2016. 16. [Gunawardana et al., 2011] A. Gunawardana, C. Meek, and P. Xu. A model for temporal dependencies in event streams. In Ad- vances in Neural Information Processing Systems (NIPS), pages 1962-1970, 2011. 17. [Hashimoto et al., 2014] C. Hashimoto, K. Torisawa, J. Kloetzer, M. Sano, I. Varga, J.-H. Oh, and Y. Kidawara. Toward future sce- nario generation: Extracting event causality exploiting semantic relation, context, and association features. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACL), pages 987-997, 2014. 18. [Mannila et al., 1997] H. Mannila, H. Toivonen, and A. I. Verkamo. Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1:259-289, 1997. 19. [Meek, 2014] C. Meek. Toward learning graphical and causal pro- cess models. In Proceedings of the Uncertainty in Artificial Intel- ligence Workshop on Causal Inference: Learning and Prediction, pages 43-48, 2014. 20. [Mei and Eisner, 2017] H. Mei and J. M. Eisner. The neural Hawkes process: A neurally self-modulating multivariate point process. In Advances in Neural Information Processing Systems (NIPS), pages 6754-6764, 2017. 21. [O'Brien, 2010] S. P. O'Brien. Crisis early warning and decision support: Contemporary approaches and thoughts on future re- search. International Studies Review, 12:87-104, 2010. 22. [Pearl, 2014] J. Pearl. Probabilistic Reasoning in Intelligent Sys- tems: Networks of Plausible Inference. Morgan Kaufmann, 2014. 23. [Radinsky and Horvitz, 2013] K. Radinsky and E. J Horvitz. Min- ing the web to predict future events. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining (WSDM), pages 255-264, 2013. 24. [Rajaram et al., 2005] S. Rajaram, T. Graepel, and R. Herbrich. Poisson-networks: A model for structured point processes. In Proceedings of the Tenth International Workshop on Artificial In- telligence and Statistics (AISTATS), pages 277-284, 2005. 25. [Remondino and Correndo, 2005] M. Remondino and G. Cor- rendo. Data mining applied to agent based simulation. In Pro- ceedings of the Nineteenth European Conference on Modelling and Simulation, pages 1-4, 2005. 26. [Rudin et al., 2012] C. Rudin, B. Letham, A. Salleb-Aouissi, E. Kogan, and Madigan D. Sequential event prediction with asso- ciation rules. In Proceedings of the Annual Conference on Learn- ing Theory (COLT), pages 615-634, 2012. 27. [Saeed et al., 2011] M. Saeed, M. Villarroel, A. T. Reisner, G. Clif- ford, L.-W. Lehman, G. Moody, T. Heldt, T. H. Kyaw, B. Moody, and R. G. Mark. Multiparameter intelligent monitoring in in- tensive care II (MIMIC-II): A public-access intensive care unit database. Critical Care Medicine, 39(5):952, 2011. 28. [Schein et al., 2015] A. Schein, J. Paisley, D. M. Blei, and H. Wal- lach. Bayesian Poisson tensor factorization for inferring multilat- eral relations from sparse dyadic event counts. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 1045-1054, 2015. 29. [Weiss and Page, 2013] J. C. Weiss and D. Page. Forest-based point process for event prediction from electronic health records. In Machine Learning and Knowledge Discovery in Databases, pages 547-562, 2013. 30. [Xiao et al., 2017] S. Xiao, J. Yan, X. Yang, H. Zha, and S. M. Chu. Modeling the intensity function of point process via recurrent neural networks. In Proceedings of the Conference on Artificial Intelligence (AAAI), volume 17, pages 1597-1603, 2017. 31. [Xu et al., 2017] H. Xu, D. Luo, and H. Zha. Learning Hawkes processes from short doubly-censored event sequences. In Pro- ceedings of the International Conference on Machine Learning (ICML), pages 3831-3840, 2017.