Learning to Select Exogenous Events for Marked Temporal Point Process
Authors: Ping Zhang
Rishabh K Iyer
Ashish V. Tendulkar
Gaurav Aggarwal
Abir De
Venue: NeurIPS 2021 Poster (2021)
Keywords: Temporal point process
time series
event selection

Abstract: Marked temporal point processes (MTPPs) have emerged as a powerful modeling
tool for a wide variety of applications which are characterized using discrete
events localized in continuous time. In this context, the events are of two types
endogenous events which occur due to the influence of the previous events and
exogenous events which occur due to the effect of the externalities. However, in
practice, the events do not come with endogenous or exogenous labels. To this
end, our goal in this paper is to identify the set of exogenous events from a set of
unlabelled events. To do so, we first formulate the parameter estimation problem
in conjunction with exogenous event set selection problem and show that this
problem is NP hard. Next, we prove that the underlying objective is a monotone
and \alpha-submodular set function, with respect to the candidate set of exogenous
events. Such a characterization subsequently allows us to use a stochastic greedy
algorithm which was originally proposed in~\cite{greedy}for submodular maximization.
However, we show that it also admits an approximation guarantee for maximizing
\alpha-submodular set function, even when the learning algorithm provides an imperfect
estimates of the trained parameters. Finally, our experiments with synthetic and
real data show that our method performs better than the existing approaches built
upon superposition of endogenous and exogenous MTPPs.

Learning to Select Exogenous Events for Marked Temporal Point Process
Ping Zhang"
Rishabh Iyer*
Ashish Tendulkart
Gaurav Aggarwal*
Abir De
UT Dallas, 'Google Inc., IIT Bombay.
{Ping 2 rishabh. iyer Hutdallasss edu, edu,
fashishvt, aaaaiiaatt..uuraaaaggaaaaaaa Jogoolg com, abirăcse iitb. in
Abstract
Marked temporal point processes (MTPPs) have emerged as a powerful modeling tool for a wide variety of applications which are characterized using discrete events localized in continuous time. In this context, the events of two types- endogenous events which occur due to the influence of the previous events and exogenous events which occur due the effect of the externalities. However, in practice, the events do not come with endogenous or exogenous labels. To this end, our goal in this paper is to identify the of exogenous events from a of unlabeled events. To do so, we first formulate the parameter estimation problem in conjunction with exogenous event set selection problem and show that this problem is NP hard. Next, we prove that the underlying objective function, with respect the candidate set of exogenous
monotone
and a-submodular events. Such a characterization subsequently allows us to use a stochastic greedy algorithm which was originally proposed in [64] for submodular maximization. However, we show that it also admits an approximation guarantee for maximizing a-submodular set function, even when the learning algorithm provides an imperfect estimates of the trained parameters. Finally, our experiments with synthetic and real data show that our method performs better than the existing approaches built upon superposition of endogenous and exogenous MTPPs.
Introduction
In recent years, marked temporal point processes (MTPPs) have shown tremendous potential in modeling the arrival process of the asynchronous events in continuous time 665 46 66
[6] 22
52 82 33
74 49 77 27 53 47]. They are extensively used a wide variety of applications, e.g., information diffusion in social networks [66 77
13 60
83
43 12 85 76),, improving human lcarning 76 74), location modeling [83,, epidemic forecasting 49 66), etc. At the outset, an MTPP event consists of two elements- its arrival time and the mark, where the latter encodes the category of the event, e.g., the topic of a blog post, the sentiment associated with a tweet, disease of individual, etc.
16
In the context of learning an MTPP, we observe two types of events- endogenous events which occur due to influence of the previously observed events and, exogenous events which are driven by the external sources or unobserved events, rather than being influenced by the previously observed events. For example, post in social media may be influenced some external news source, rather than the previous messages (26) 60 [3]; in epidemic process, an infection may be triggered by community transmission where the source is other than any previously known infections [50), etc. In such applications, the observed events appear unlabeled, i.e. they are not tagged with their sources of influence. Consequently, the existing MTPP models [21 12 78 [6) resort the superposition of exogenous and endogenous MTPPs. However, such approaches view an event being exogenous or endogenous with equal likelihood and therefore, they do not focus identifying which events more likely to be exogenous than others. Consequently, they often remain oblivious to the presence of the exogenous events, which often preclude these models from realizing their full potential. While
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

De et al. [13] tackle this problem in the particular context of opinion dynamics in social networks, their formulation focus only on the mark dynamics and, skirt the effect of exogenous events on the arrival times. As result, their framework can not be extended to generic MTPP model, where the arrival time is often a key component.
1.1 Our contributions
In order to respond to the above limitations, we make the following contributions.
Learning in conjunction with selection of exogenous events. We design TPP-SELECTS novel event selection algorithm which, for any given MTPP model, simultaneously filters the exogenous events from a stream of unlabeled events as well as train the model parameters over the remaining (endogenous) events (Section 3). More specifically, we seek to maximize the likelihood of all the events, jointly with respect to the set of exogenous events and the parameters of the associated MTPP model. Such a formulation induces a parameter estimation problem in conjunction with the combinatorial optimization problem for selecting the exogenous events.
Characterization of the objective. Subsequently, we show that our problem is NP-hard due to the involvement of the candidate exogenous events as an optimization variable. We tackle this problem using several technical innovations. First, we reformulate it as an instance of a set function maximization problem, where the objective corresponds to the value of the maximum likelihood, a function of the candidate set of exogenous events. Then, based this representation, show that this objective satisfies monotonicity and a-submodularity- a notion of approximate submodularity [25 29] for linear MTPP and wide variety of nonlinear MTPPs (Section 4. These results reveal an unexplored connection between approximate submodularity and temporal point process, that is of independent interest.
Approximation guarantee for greedy method in the face of imperfect training. Next, we show that these properties allow us an existing stochastic greedy algorithm [64]. While this algorithm is known to admit an approximation guarantee for submodular maximization, we show that also enjoys an approximation guarantee for maximizing a-submodular functions. Moreover, we show that this algorithm also admits an approximation guarantee even when the training algorithm provides an imperfect estimation of the MTPP parameters.
Finally, we perform a comprehensive evaluation of our proposal on both synthetic and real data. Our experiments with synthetically generated sequences show that TPP-SFLEEE can accurately select the exogenous events from stream of unlabeled events, even though is completely unsu- pervised. Our experiments on real datasets show that, despite training a subset (endogenous) of events, -EPEEEE outperforms several baselines as well as the corresponding model which is trained on the entire dataset in the presence of exogenous events. Our code is available in https///ghhbbbboooomooole//////s
Related work
Apart from the works on MTPPs, our work is related to robust learning, subset selection, modeling external effects in different applications, active learning, etc.
Robust learning. Robust learning focuses on training machine learning models in the presence of outliers and noisy labels 9 67
&8 58 However, exogenous events are not outlier data, they are events which follow different model, other than the central model- which, in our case, captures the endogenous event dynamics. These robust learning methods predominantly consider i.i.d. data and focus on designing models and training algorithms which would generalize well across the data including the outliers. In contrast, the events in our setup have strong temporal dependencies. Moreover, our objective is to select the exogenous events, that the model can be trained on the remaining (endogenous) events to obtain more accurate parameter estimates
Data subset selection. In recent years, there is flurry of work on data selection 81
80
79
48
2
40 51 57 7 6 36) which predominantly select smaller sized subset of data to facilitate efficient training, by optimizing submodular functions and their variants. However, TPP-SELECT aims to filter the exogenous events from a sequence of events to help the underlying MTPP model achieve better predictive performance.
Modeling external effects. Our work is also connected to the methods that model the external effect in several applications, especially, in web or online social media [19 60 that aim to model the effect of exogenous influence on the information diffusion in social media. However, they do not aim to
select the exogenous messages from stream of unlabeled messages. Iwata et al. [34] aim to learn

---

the effect of one user on the post of other users. Such model can be used to quantify the external effect. Linderman and Adams [5] aim to learn probabilistic model which captures latent influence present in data using mutually exciting processes combined with a random graph model. Furthermore infers the latent network structure from the noisy observations. Tanaka et al. [75] model dynamics of event sequence in the particular application of purchase data modeling. Specifically, it combines three factors, namely user preferences, influence from other users and media advertisements. These proposals learn their model using EM algorithm combined with Gibbs sampling method. However, they do not provide an algorithm to explicitly demarcate between endogenous and exogenous events. Very recently, Liu and Hauskrecht [47] consider semi-supervised setting of event outlier detection for MTPP. However, they assume that they have access to data without outliers, so that the underlying MTPP model can be trained this clean data. In contrast, work applies to unsupervised setting, where the training data also contains the exogenous events.
Optimization of submodular functions and their variants. Submodular functions have the ability to characterize a wide variety of set functions. Moreover, thanks to the existence of a simple greedy algorithm to maximize such functions, their use is widespread across several subset selection tasks [8 [8] 79 [88 2]. Several popular set functions, e.g., facility location, set cover, concave over modular, etc. are submodular [6 2 (35. In this context, there is recent line of works which focus on maximizing different variants of submodular functions which include a-submodular functions and 37. In particular, our work is more focused around
y-weakly submodular functions [61 54
a-submodular functions.
Subset selection in conjunction with model learning. Existing works 55 36 39 14 15 57
have also considered subset selection in conjunction with model parameter estimation. However, in the context of applications as well as formulations, these works differ from us. Killamsetty et al. (39 consider simultaneous parameter estimation on training set and subset selection using validation error in order to facilitate efficient learning without introducing significant error. On the other hand, the works in [36] 51] [7 | focus on selecting coreset- a small representative subset of the entire data- together with parameter estimation. However, they consider i.i.d data and select subset for efficient training. In contrast, we partition sequence of events into exogenous and endogenous events for improved training of point process models. Finally, the works in 14 15 consider simultaneous parameter estimation and subset selection. Similar to our work, they aim to find model parameters and a desired data subset simultancously by minimizing the underlying loss functions with respect these variables. However, they focus on human assisted machine learning, whereas our work considers exogenous event selection in the context of marked temporal point processes. Thus the problem formulation, results and proofs are significantly different from these works.
Active learning. Active learning methods [8] 28 69
24 aim to identify instances in the training data, in order to reduce the labelling cost. In contrast, our work aims to select samples which are not influenced by the previous events a sequence of dependent observations. To that end, it trains the endogenous MTPP model on the rest of the events. More specifically, active learning methods aim to find subset of instances so that the model trained over it gives accurate predictions for all the samples in the test set. In contrast, our work selects both exogenous and endogenous events and then trains two separate models (No, mg) and (p, q) so that they perform well specifically on endogenous and exogenous events respectively.
3 Problem formulation
In this section, we formulate our problem of learning an MTPP in presence of exogenous events, starting with an overview of MTPPs.
3.1 Overview of marked temporal point processes
A marked temporal point process is a stochastic process which is characterized using sequence of events H fe = (v. })}, where E R+ is the time of occurrence and y E C {c) is mark of the
event that has happened at time 17 12 65 10) The dynamics of the arrival times can equivalently be represented as a counting process (t) that counts the number of events occurred until time t. In this context we also define He as the history of events happened until and excluding time f, i.e.
H. = {er = (yi, 4e)ee E H, 4-11 < 144 < 1). We specify the dynamics of the arrival times using a conditional intensity function X(1) which in turn encapsulates the probability that an event occurs in
the infinitesimal time interval [L, + dt), described as follows 12 74 10::
A(t) = Pr (An event will occur between t and t + dt) E(dN = 1}.
(1)
3

---

where (t) E {0, 1 is the number of events arriving in the infinitesimal time- intervltevaal [t, + dt). On the other hand, we capture the behavior of marks using probability distribution, i.e.
m(c) = Pr (Mark of an event is c) = Pr (y = c),
(2)
which is often modeled multinomial distribution over the set of marks C.
3.2 Problem setup
Endogenous and exogenous events. In the context of MTPP, we observe two types of events, viz., (i) endogenous events that occur due to the influence of the previously observed events; and, (ii) exogenous events that are not influenced by the previously observed events but occur due to the influence of the externalities [2] [3] The dynamics of the endogenous events modeled using a parameterized conditional intensity function X(t) = At (He) and conditional mark distribution m(y) my Hz). The arrival time and the mark depend on the previously observed events H4, ( H4) = (LdN(L) = H,), mo H+) = Pr(y HH))
(3)
Therefore, both Ag and mg stochastic quantities. On the other hand, exogenous events captured mostly using an independent MTPP which, the intensity function or the mark distribution modeled using deterministic and mostly time invariant distributions. In our work, we model the intensity function and the mark distribution for exogenous events as Gamma and Beta noise,
(4) These distributions allows μ E (0, oo) and g E (o, 1). a. and B. are hyperparameters. We further assume that both the arrival times and the marks of the exogenous events are i.i.d. random variables. Use of superposition of MTPP models and their limitations. Suppose, at all possible, the train- ing observations Ht gathered during the windww [0. (") were already tagged with endogenous or exogenous labels. In such a case, one could first build the set of exogenous events and the endogenous events S and then, use maximum likelihood estimation to learn {a., {.) and O separately using the set of exogenous events S and the endogenous events Hr \S, respectively.
X(t) μ Gamma(ax. 8x),
m(y) = q ~ Beta( Sm,y)..
In practice, the difference between the exogenous and the endogenous events is not evident in the training data. Specifically, these events are not tagged with endogenous or exogenous labels and therefore, it is not possible to construct the set of exogenous events S, well in advance. Existing works 21
84 77 tackle this problem by maximizing the likelihood corresponding to the superposition of exogenous and endogenous MTPPs. In such case, the intensity function becomes X(t) = μ (t He) and the mark distribution incorporates the effect of exogenous events using additive offsets.
Maximizing the likelihood associated with the superposition of two MTPPs, often turns out to be suboptimal as shown in our experiments (Section 6 This is because, such an approach does not aim to find out the of exogenous events S which maximizes likelihood function. In fact, due to the absence of any informed choice about S, such a likelihood function assumes that all the partitions between exogenous and endogenous events {(S, H))} are equally likely (Appendix I. Such an assumption may not be true in general. We ameliorate this limitation by selecting partition {(S, {S) along with the model parameters, which induces the highest value of the likelihood, across all possible partitions and the hypothesis class.
3.3 Problem statement
We aim to select the exogenous events from a given stream of unlabeled events and simultaneously train these MTPP models (3) on the remaining events which endogenous in nature.
Selecting exogenous events in conjunction with parameter estimation. Given a stream of events Hy recorded in the time interval T),, we aim to pick S C H the candidate set of & exogenous events, i.e., [S] < k- and concurrently, train the parameters f on the set of the endogenous events SS. Using the intensity functions and the mark distributions defined in Eq. to solve the following regularized log- likelhhoood maximization problem:
our goal is
maximize @E0.SCHr
5,0,8, Hr))
subject to, |S| < k,
(5)
| log(>o(tz H), + log mo HH.) 1f d0(T (44) dr
with, L(0:S, Hr)
Σ A
+ +| TEEM + | [S|
(6)

---

Here, is the coefficient of the L2 regularizer, l is pre-specified integer with & < Hrr) The above problem poses subset selection task in conjunction with likelihood maximization. Parameter estimation along with subset selection has also been addressed in the context of human assisted learning 15 efficient learning 18
Next, we derive an equivalent representation of our optimization problem 6 as an instance of cardinality constrained function maximization problem.
Reformulating ( as a set function optimization problem. Given a fixed set of the exogenous events S, the optimal value of the model parameters 0* (Hr))) becomes dependent only the endogenous events Sr Thereefoe, if we define:
F(S) [(e" (HT S,
then the optimization problem 66 becomes equivalent to solving the following optimization problem.
maximize F(S), subject to, |S| -
(8)
SCHr
Hardness analysis. Given the optimal set of exogenous events S one can easily compute the optimal parameters 0* (Hr))5*) for the problem (5) in polynomial time, if the objective (6) is concave with respect to I for any fixed S. However, in general, both S and 0" (S+) can not be solved in polynomial time. We formally state this result in the following proposition (Proven in Appendix (.2).
Proposition 1 Solving the optimization problem in Eq. 5 is NP-hard.
4 Our proposed framework for maximizing F(S)
In this section, we present our framework to maximize F(S). More specifically, we first show that the set function (S) defined in Eq. (7) is monotone and a-submodular for wide variety of MTPPs. Then, present algorithm [56], which identifies the optimal set of exogenous events from set unlabeled events, for any given MTPP model. Finally, we show that such an algorithm enjoys approximation guarantee even when the learning algorithm provides an imperfect estimate of the trainable parameter O.
approximation algorithm based on scalable stochastic greedy
4.1 Characterization of F(S)
First, we show that F(S) enjoys several useful properties for a wide variet of MTPPs, which allows us leverage a stochastic greedy algorithm that offers approximation guarantee. Before formally stating those properties, we first present the formal definitions of monotonicity and a-submodularityy
Definition 2 A function F(S) is monotone non-decreasing if F(S U (e)) - -F(S) 2 - -fr all S. F(S) is a-submodular if F(S U (e)) F(S) 2 aFF(T U (e)) F(T)) for all
e TT and S STCC C. HT (28 86 20J.
Monotonicity and a-submodularity of F(S) with linear MTPPs. First, we consider a linear marked temporal point process which is built upon Hawkes process (77 (6). Here, model the intensity function Ao (H)) and the mark distribution ( He) for the endogenous events as linear combination of multiple triggering kernels (1,44) 0), i.e.,
(9) Here, is the dimension of K. and {Ox,,, Om,o 1 E [d]} is the set of trainable parameters. In general, (:..(:)))) captures differ- ent forms of dependencies. For example, in the particular case of information diffusion in social networks, Ao may correspond the rate of message of a user u with neighbors and, Ne. (1, = e (t- [4; is posted by user v) which captures the scenario the effect of an previously occurred event é; decays over time with the decay factor w. > O. In the subsequent theorems, we formally state that F(S) is monotone and submodular set function (Proven in Appendix
dt H4) 0 (t),
me (H4) logistic(y [T,,K,.,t)
where O_ (() = > Oa EegEN, (t.
Theorem (Monotonicity of linear MTPP) Assume that the endogenous events follow a linear MTPP D. Then the set function F(S) defined in Eq. T is monotone in if p 2 Pmin = (0.5/e) =mmax,> exp 2E[[oo( q))), where i and q are the intensity and the mark distribu-
tion for the exogenous events and Kmax. maxesT (t)l.
5

---

We would like to hightlight that for several linear MTPP models, such an assumption on the regular- ization parameter p is quite loose. For examples, in the previously discussed example of information diffusion with exponential kernels, if we have Kimax, = 1 and an exogenous event distribution 14, q ~ (1,ma (1,1), 1), we have Pinin < 0.1.
Theorem (a-submodularity of linear MTPP) Given that the same conditions in Theorem 3 as well as I xx (t)ttt S K < oc, Kmax, = max+sT I| (.a lz. K = mid |Ko (t)
If K, Kmax, fimin.
0, then the set function F(S) is a-submodular in S with a 2 ax,, where
log
[V
/epp peep//max. mmax..
+ Ellog(H 4)
oF Kmnxx.A + log 46mmns.2 + log
(v/ 2ppmmos.A
+ K
log 2p
Kinns m log
+ [logg( q)]
2
In the previously discussed example of linear MTPP, which has an exponential kernel having decay factor w. we have aj Ollog p/ (log p + bee"") where b is a data dependent constant. Hence, by choosing a low decay factor w, one can obtain a high value of orp.
Proof sketches of Theorem 3 and 4 We prove Theorem 3 in two steps. In the first step, show that
(() F(S) 2 mino, i 0x112 2 log(0 (t)) + exp 2 E [lg((a 2)))
: In the second
step, we show that this lower bound is greater than Ellog μ log q] +og V 2ep/ x2 Mixx which proves the theorem. To prove Theorem 4 we aim to bound [F(S U {e)) F(S))/[F((
U (e)) F(T))
To bound the numerator, we use the result of Theorem B To bound the denominator, we first
show that F(T U {e}) - F(T)= S (100(H THT (T (e)))))
log(O) (H2 V(T U (e)))
+
log[1 + exp (-y 0t (HTAATTUU minimum and maximum possible values of ||011|-
Km km (t)) These individual terms are finally bounded using
Monotonicity and a-submodularity of Nonlinear MTTPs. Next, we consider nonlinear MTPPs
that do not have any fixed parameterized form, which are trained using deep learning methods [7
87
89], Such models use sequence encoder- either recurrent neural network (17) or a transformer 87
89
to first derive an embedding h, of the history of events He, happened until time i, and then use h; to capture the generative process of the next event. Characterization of F(S) for such general
MTPP is an extremely challenging task. Therefore, we focus on a class of nonlinear MTPPs which satisfy the following conditions the intensity function and the mark distribution, i.e.,
Amine al|0| < (t He)= < Amaxe 11012, Mmin -110111 < ma H.)) < 1.
(10)
Here, Amax; Amin: mmin are constants such that: oo= (Ht)) E [Amax, Amin]] We would like to high- light that many popular MTPP processes including recurrent marked temporal process (RMTPP) 17].
self-attentive point process [87). transformer Hawkes process [89]. neural Hawkes Process [5 etc.
satisfy the above conditions. In fact, such an exponential bound is tight for the intensity function used in RMTPP [17. since its intensity function uses an exponential activation function in the last layer. In Appendix C.3 we discuss the representations of different MTPPs in the form defined in Eq. (TO). Next, show the monotonicity and submodularity of F(S) in the following theorems (Proven in Appendix C
Theorem (Monotonicity of nonlinear MTPP) Assume that the endogenous events follow nonlinear MTPP with exponentially bounded intensity function. as described in Eq. (10) with Amax < exp(-Ellogh
9))). Then the set function F(S) defined in Eq. ① is monotone in S if 2 0.25 a²/ (log [L/Amax] + E[log(H - 4)}, where a and are the intensity and the mark distri- bution for the exogenous events.
Theorem (a-submodularity of nonlinear MTPP) Given the same conditions in Theorem 5 Jand Jo 0o Dottt (lll < Amax < co, the set function F(S) is a-submodular in S with a 2 Oep, where
OF equal
log |exp (-a² Eloggu 4)/44) /Amax]
(11)
Tog( 1/ Aminn + Amax + 2 /1/m + Elog(( q)
Amax + (a + /)/
P
We would like to point out that \o bounds. Indeed, in practice, we encounter several existing models [1 89 87 that choose activation
(T) = Xo > 0 for the nonlinear MTPPs having exponential
functions, e.g., Softplus, exponential function, having nonzero intensity functions even when the

---

Theorem Assume that the training algorithum TRAIN() in Algorithm Sasiihhmmmpooei provides imperfect estimates I for parameters θ = 0. However, for the linear MTPPs described in Eq. (t H44 = 0 for
O. Therefore, the set of nonlinear MTPPs considered above does not cover the class of linear MTPPs (9) and therefore, the results and the proofs in Theorems 5 are different from Theorems Appendix characterizes other types of nonlinear MTPPs.
4.2 TPP-SELECT: Approximation algorithm for maximizing F(S)
Finally, we present TPP-SELECT, an approximation algorithm based on a stochastic greedy algorithm proposed in [56] in order to solve the optimization problem defined in
Outline of TPP-SELECT. Algorithm] T we
summarize TPP-SELECT to maximize F(S). It
Algorithm 1 Stochastic greedy algorithm (56)
a randomized iterative algorithm based on the
Require:
The set of observed events Hr, the final time T, the regularization parameter the number of exogenous events
stochastic greedy algorithm proposed in (56).
which keeps picking up one element per each of k iterations (refer to the for loop in line no. 2). In each iteration, given the current estimate of S, Algorithm p up candidate exogenous
1: S + 0
2: for i E [K] do
3: Randomly draw subset V from H
event V which maximizes F(S {v}). How- in contrast to the well known (determin-
4:
for u E V do
istic) greedy algorithm [6]] stochastic greedy algorithm computes the maximum only subset of elements sampled from the current candidate set of elements.
5:
@ t (R
6:
(() + ((0:S,
7:
0 ((Hr)(SUm) =
8:
end for
9:
V' argmax F(S u (v})
Advantage over deterministic greedy algo- rithm. The stochastic greedy algorithm is the randomized version of well known greedy al- gorithm [61]. If we put V Hr then the stochastic greedy algorithm becomes equivalent to the greedy algorithm. However, we need to train the model |V] times (due to the for loop in lines 4-8) per each iteration. As result, the deterministic greedy algorithm would have been extremely inefficient, as it needs to greedily search for the optimal event over all the possible candidate events V. Therefore, reducing the search space subset V would significantly improve the efficiency.
10: S S+SU
11: end for
12: Return S, S,0(H
Approximation guarantees. Next, provide the approximation guarantee of Algorithm [ for solving the optimization problem defined in (8.. Existing works [56] (37, provide approximation guarantees of Algorithm [ problem, a training algorithm may not provide the optimal value of model parameters 0" (Hr\S), even when the MTPP model is linear. Hence, we mostly obtaín an imperfect estimate of the model parameters 0" (H) To this end, we derive the approximation guarantee of Algorithm ] when the underlying training algorithm provides an imperfect estimate of the model parameters 0 (Hr (S).
when the exact value of F(S) is available. However, in the context of our
We would like to highlight that the following approximation guarantees apply to the cardinality constrained maximization problem of any monotone a-submodular function and therefore is of independent interest.
of the underlying model parameters, with L(0" (S; -
all S and that it runs with [V] = O [Hrl log(1/6) (cf. line number 3). Then,
[[F(S)) 2 (1- exp (-ap) app F(S") ke
(12)
where the expectation is taken over many draws V (cf. line number 3). S is the solution of the optimization problem g and app is the submodularity ratio, computed using Theorems and
The above approximation guarantee in the presence of imperfect parameter estimates is related to several existing works (20
32 72]. However, they do not focus on cardinality constrained maximization of a-submodular functions in general and not the well known stochastic greedy algorithm in particular. Note that, when we have a perfect training algorithm, ie., e = 0, Theorem reduces to similar results in [56] 37).
63
7

---

Correct prodietion for S
Inserroct presiction for S
Prodiction for Hy/SS
0
25
50
75
100
0
25
50
75
100
0
25
50
75
100
(a) iteration
(b) iteration
(c) iteration
Figure 1: Snapshots of output of Algorithm I one third, two third and final stages of executions.
The exogenous intensity μ is tuned in such way that [S] = 0.3 [Hr).- Moreover, we also set k = 0.3 Hrl- Top half (bottom half) of each figure indicates ground truth exogenous events S (endogenous events H)) Blue, green and red events indicate predicted endogenous events, correctly predicted exogenous events and wrongly predicted endogenous events. We observe that, the algorithm is able to predict the exogenous events with significant accuracy, as the number of wrongly predicted exogenous events is significantly lower than the correctly predicted exogenous events. The classification accuracy of final stage is 0.806.
Experiments with synthetic data
In this section, we create synthetic examples containing endogenous or exogenous label and evaluate TPP-SELECT from both qualitative and quantitative perspectives.
5.1 Experimental setup
Data generation. At the very outset, we generate data using linear MTPP defined in Eq. ( More specifically, we set the number of marks |C| = order to sample the endogenous events, we set d 2 and draw unidimensional parameters 0x Om, Unif 1] for E {1.2) 2). We use the triggering kernel (t, = exp(-wx(t 4)) and Km., = exp(-4i (t 44),, where WA,Wn, E Unif 1] for E [d]. For exogenous messages, we sample μ and q using the exogenous distribution 4 with ax Bx, am, 3. = 1. Finally, we use Ogata's 's thinning algorithm [62] to generate both endogenous and exogenous events.
Baselines. We compare our method against several data selection based unsupervised robust learning methods: (i) EM algorithm 770 which first assigns a constant probability which models the likelihood of an event e being exogenous and then estimates it along with model parameters 0 using expectation maximization; (ii) K-means 770 which uses K K-means clustering to cluster the events in K groups and then label the smallest size cluster as S, the exogenous event set; (iii) Principal Component Analysis (PCA) 71 which first finds a low-dimensional projection of the representation vector of the events, then sorts them in the decreasing order of the reconstruction error and finally, choose top-k events as the exogenous event set S; and, (iv) Facility- facility location function to select the set of exogenous events S. For K K-means, PCA, we directly used implementation available in Keras [8]. For Facility location, we used apricot library (68].
[]] which maximizes
5.2 Results
We qualitatively show how TPP-SELECT keeps selecting the exogenous events throughout the progression of Algorithm [] To that aim, we tune the exogenous intensity μ in such a way that |S| = 0.3 HTl and run Algorithm with A 0.3 (.rl Figure summarizes the results, which shows that: (i) the algorithm is able to predict the exogenous events with remarkable accuracy, as the number of wrong predictions is significantly lower than the correct predictions; (ii) the performance of algorithm is strikingly accurate during the initial stage, as the number of wrong predictions of exogenous events is significantly low; and, (iii) even when TPP-SELECT makes wrong predictions about e E S, there always exists some correct ground truth exogenous event around it which indicates that TPP-SELECT was almost able predict them correctly.
Select 0.806
EM
K-means
PCA 0.562
Fac-loc 0.299
0.554
0.620
Table I: Accuracy of exogenous event selection in synthetic data in the figure [ for different methods.
Next, we compare our method against the baselines. Table summarizes the results, which shows that our method outperforms the basclines.
8

---

TPP-
EM
PCA
Fac-Loc
SELECT
Club
0.32 10.02
0.18 1002
0.28 1001
0.25 10.01
Election
0.58 =0.33
0.31 10.01
00.00
0.44 +0.03
Series
0.18 10.02
0.27 10.02
0.26 10.01
0.16 10.01
Verdiet
0.33 00.04
0.27 +0001
0.18 =0.00
0.10 +0.01
BookOrder
0.96 =0.01
0.41 1.003
0.92 10.01
0.46 10.01
Table 2: Accuracy of exogenous event selection of SPP-SEET EM 770,, PCA 71 and Facility-
Location [ across all datasets, when we inject |S] 0.4|Hrl exogenous events, Numbers in bold
font (underline) indicate the best (second best) performer. We observe that in a majority of the cases, TPP-SELECT outperforms the baselines.
Experiments with real data
In this section, we provide a comprehensive evaluation of our proposal on several real world datasets, which shows that our method outperforms several data selection based robust learning methods, as well as the underlying base MTPP model which is trained over all observations including exogenous events. Appendix G contains additional experiments.
6.1 Experimental setup
Datasets. We considered five real world datasets, also summarized in Appendix F] which (i) Club, (ii) Election, (iii) Series, (iv) Verdict and (v) BookOrder. Among these datasets, the first four datasets were gathered from the works [12 84 whereas, the last dataset were gathered from 17
Baselines. We compare our method against the four data selection based unsupervised robust learning methods, presented in Section 5.1
6.2 Results
Comparison with baselines. We first compare the performance of TPP-SELECT against the base- lines in terms of the classification accuracy for exogenous event selection. To that aim, we inject 40% exogenous events and present to the event selection methods for identifying these events. Here, we consider recurrent marked temporal point process (RMTPP) 17 as our base MTPP model (Ae, me). Note that, unlike synthetic dataset, K-means is not able to predict any exogenous events correctly, We believe that this poor performance is due to the complexity of the underlying generative process in real datasets, which renders the feature distance between events to be the poor predictors of exogenous labels. Table summarizes the results of our method and the other baselines, which shows that (i) our method consistently outperforms the baselines in majority of the cases, as it aims to select the events in conjunction with the model parameters, whereas the baselines except for EM algorithm selects the events in a model-agnostic manner; (ii) except for Series and Verdict datasets, EM algorithm fares poorly across all other datasets, which believe is due the time-invariant modeling of probability of the exogenous events; and (iii) PCA is the second best winner in majority of the datasets.
Comparison with the base MTPP model. Next, investigate how well TPP-SELECT performs in comparison to the underlying base MTPP which models the event dynamics using the superposition between endogenous and exogenous MTPPs and thus, is trained the entire sequence of events including the exogenous events. Given a sequence of observed events, we split it into 80% training and 20% test sets. We use TPP-SELECT on the training set HT, where it simultaneously selects the exogenous events S and trains the model parameters (Ae, ma) on the endogenous events H Once we train the model, predict the unseen events in the test set T. To this end, we evaluate the performance on in terms of mean absolute error (MAE), ie., ! Ec=(ty)e [E[ - î] and mark prediction error (MPE), i.e.,
use Ogata's 's thinning algorithm [62) simulate future events to
1
TTT Ee=(tr)e Pr(y # 7). Here, MAE and MPE measure the errors in predicting the arrival times and the marks of the future events.
Table 3 summarizes the results, which shows that TPP- SELECE performs better than the underlying base MTPP model across all datasets. Such observations imply that model aware exogenous event filtering improves the predictive performance than learning a superposition of two models.
The datasets public and anonymized. We collect them from htts://ittub.commaraaat 1 024 detmmaarcaionnrrremaatrrraaaa and https://gttu..com.... com/musically-uttt able information or offensive content.
They are under MIT License. No dalasel contains personally identili

---

Time prediction error in terms of MAE E [t-11 1
Mark prediction ervor Priy # f)
Rase model: RMTPP
Base model: THP
Base model:
RMTPP
Rase model:
THP
TPP-SELUCT
Basc MTPP
TEP-SOLUCT
Base MTPP
TPP-SELECT
Basc MTPP
TPP-SLLECT
Basc MTPP
3.57
3.67=0.05
11,51:0,07
11.9340.88
0.59:1005
0.36:0.011
0,424001
Election
8.50
8.50-0001
30.79 0.02
30.99.10.03
0.4310.02
0.67.1..03
0.38 0.38.10.00
0.4110011
Series
1.15:0.05
1.71=007
9.12:0.17
9.99:0.20
0,5910.00
0.6910.01
0.57=0.00
0.5810.00
Verdiet
2.27:=0.00
2.27=0.00
7.88=0.01
8.11=00055
0.57::0.00
0.71+00001
0.57=0.00
0.60#0.01
BookOrder
0.07=00.00
0.07-0.00
0.09:00.00
0.11-00.01
0.45+-0.00
0.49++0.00
0.37-0.01
0,44+0.00
Table 3: Performance in terms of E[[ - E)). Le.. the mean absolute error (MAE) for time prediction (left half) and the misclassification error Pr(y + 17) for the mark prediction (right half) for TPP- SELECT and the corresponding base MTPP model which is the superposition of endogenous and exogenous MTPP models. Here, this base MTPP model is learned over the entire sequence of observed events. In all experiments, we considered 80% training and 20% test set.
3.60
0.7
0.6
MAE
3.45
MPE
0.5
0.4
3.30
0.30
0.30
0.45
0.60
0.30
0.45
0.60
|
|
Figure 2: Variation of mean absolute error E(It - 2) and mark prediction error (MPE) Pr(y # 1) against k. the maximum number of exogenous events, on Club dataset. We observe that in both the cases when is too small or high, then SPP-STLECT performs poorly. However, there exists sweet spot of where REP-SELECT shows its best performance.
Effeet of k. Finally, we investigate how k, the pre-specified number of exogenous events, impacts the performance of TPP-SELECT. Figure summarizes the results, which show that (i) TPP-SELECY performs poorly when is either too small or too large, and (ii) there exists a sweet spot of k. where TPP-SELECT shows the best peformance.
7 Conclusion
In this paper, we aim to identify the set of exogenous events from a set of unlabeled events for learning marked temporal point process. To that goal, we have developed TPP-SELECT, novel framework that selects the possible set of exogenous events from set the observed events, under any given MTPP model. More specifically, we first cast this problem as an instance of exogenous event set selection problem, in conjunction with parameter estimation problem which is NP-hard, in general. However, we show that solving such problem is equivalent to maximizing a monotone and a-submodular set function which leads us to develop built upon stochastic greedy algorithm which was originally proposed in (64] In this work, we show that it also enjoys approximation guarantee for a-submodular lar set function maxinization, even when the learning algorithm provides an imperfect estimate of the trained parameters. Our experiments show that TPP-SEL PPP-SEEECT is able to outperform wide variety of baselines based on data-selection from robust learning literature.
an approximation algorithm
Our work opens several venues of future work. For example, our method can be easily applied to identify external influence in Twitter- such situation can immediately beneficial in wide variety of applications that include viral marketing. misinformation detection, etc. However, by deploying our method as-it-is can lead privacy leakage of users. To counter this effect, one can design differentially private framework to mitigate this effect, by building upon the work by Mitrovic et al.
(59 In our work, we do not consider a multivariate point process. It would be interesting to develop exogenous event selection method for such processes. Finally, it would be valuable to extend our method an online setting, where the task to select the exogenous events in the face of an online stream of events.
10

---

Acknowledgments and Disclosure of Funding
The project was partially funded by Google Research Grant and DST Inspire Faculty Grant. This work is also supported by the National Science Foundation under Grant No. IIS-2106937. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, Google or DST.
References
[1] S. Ahmed and A. Atamtürk. Maximizing class of submodular utility functions. Mathematical programming. (28(1)149-166) 2011.
[2] R. Bairi, R. Iyer, G. Ramakrishnan, and J. Bilmes. Summarization of multi-document topic hierarchies using submodular mixtures. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguisties and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 553-563, 2015.
[3] A. Bakshi and A. Prasad. Robust linear regression: Optimal rates in polynomial time. arXiv preprint arXiv:2007.012 0..004...119,, 2020.
[4] K. Bhatia, P. Jain, P. Kamalaruban, and P. Kar. Consistent robust regression. In Advances in Neural Information Processing Systems, pages 2110-2119 2017.
[5] A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek. Guarantees for greedy maxi- mization of non-submodular functions with applications. arXiv preprint 1731::1003.02100 2017.
[6] C. Boutsidis, P. Drineas, and M. Magdon-Ismas Near-optimal coresets for least-squares regression. IEEE transactions on information theory,
2013.
[7] T. Campbell and T. Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. In International Conference on Machine Learning, pages 698-706, 2018.
[8] F. Chollet et al. Keras. https://ghhubb.co///coollltteee 2015.
[9] C.-C. Chuang, S.-F. Su, J.-T. Jeng, and C.-C. Hsiao. Robust support vector regression networks for function approximation with outliers. IEEE Transactions on Neural Networks, 13(6): 1322-1330, 2002.
[10] D. Daley, D. Vere-Jones, et al. An introduction to the theory of point processes: volume II: general theory and structure. Springer New York, 2008.
[11] A. Das and D. Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.399 2011.
[12] A. De, I. Valera, N. Ganguly, S. Bhattacharya, and M. Gomez-Rodriguez. Learning and forecasting opinion dynamics in social networks. In NIPS, 2016.
[13] A. De, S. Bhattacharya, and N. Ganguly. Demarcating endogenous and exogenous opinion diffusion process on social networks. In Proceedings of the 2018 World Wide Web Conference, pages 549-558. 2018.
[14] A. De, P. Koley, N. Ganguly, and M. Gomez-Rodriguez. Regression under human assistance. AAAI, 2020.
[15] A. De, N. Okati, A. Zarezade, and M. Gomez-Rodriguez. Classification under human assistance. AAAI, 2021.
[16] N. Du, M. Farajtabar, A. Ahmed, A. J. Smola, and L.. Song. Dirichlet-hawkes processes with applications to clustering continuous-time document streams. In KDD,, 2015.
[17] N. Du, H. Dai, R. Trivedi, Upadhyay, M. Godez-Rodriguez, and I.. Song. Recurrent marked temporal point processes: Embedding event history vector. In KDD, 2016.

---

[18] S. Durga, R. Iyer, G. Ramakrishnan, and A. De. Training data subset selection for regression with controlled generalization error. In International Conference on Machine Learning, pages 9202-9212. PMLR, 2021.
[19] S. Dutta, S. Masud, S. Chakrabarti, and T. Chakraborty. Deep exogenous and endogenous influence combination for social chatter intensity prediction. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1999-2008, 2020.
[20] M. El Halabi and S. Jegelka. Optimal approximation for unconstrained non-submodular minimization. In International Conference on Machine Learning, pages 3961-3972. PMLR, 2020.
[21] M. Farajtabar, N. Du, M. G. Rodriguez, I. Valera, H. Zha, and L. Song. Shaping social activity by incentivizing users. Advances in neural information processing systems, 27, 2014.
[22] M. Farajtabar, Yang, X. Ye, H. Xu, Trivedi, E. Khalil, Li, L. Song, and Zha. Fake news mitigation via point process based intervention. In JCML, 2017.
[23] Filzmoser and Nordhausen. Robust linear regression for high- nigh-dimensional data: An overview. Wiley Interdisciplinary Reviews: Computational Statistics, page e e1524.
[24] Y. Gal, R. Islam, and Z. Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, pages 1183-1192. PMLR, 2017.
[25] K. Gatmiry and M. Gomez-Rodriguez.. Non-submodular function maximization subject to matroid constraint, with applications. arXiv preprini UrXiv:/811.07860 2018.
[26] P. Grabowicz, N. Ganguly, and K. Gummadi. Distinguishing between topical and non-topical information diffusion mechanisms in social media. In Proceedings of the International AAAI Conference Web and Social Media, volume 10, 2016.
[27] V. Gupta, S. Bedathur, S. Bhattacharya, and A. De. Learning temporal point processes with intermittent observations. In International Conference on Artificial Intelligence and Statistics, pages 3790-3798. PMLR, 2021.
[28] A. Hashemi, M. Ghasemi, H. Vikalo, and U. Topeu. Submodular observation selection and information gathering for quadratic models. arXiv preprint 10XX:::9000009999, 2019.
[29] H. Hassani, M. Soltanolkotabi, and A. Karbasi. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pages 5841-5851 2017.
[30] A. Hassidim and Y. Singer. Submodular optimization under noise. 2017.
[31] A. Hassidim and Y. Singer. Optimization for approximate submodularity. pages 394-405. Curran Associates Inc., 2018
[32] T. Horel and Y. Singer. Maximization of approximately submodular functions. 2016.
[33] H. Huang, H. Wang, and B. Mak. Recurrent poisson process unit for speech recognition. In AAAI, 2019.
[34] T. Iwata, A. Shah, and Z. Ghahramani. Discovering latent influence in online social activities via shared cascade poisson processes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 266-274, 2013.
[35] R. K. Iyer. Submodular optimization and machine learning: Theoretical results, unifying and scalable algorithms, and applications. PhD thesis, 2015.
[36] V. Kaushal, R. Iyer, S. Kothawade, Mahadev, K. Doctor, and G. Ramakrishnan. Learning from less data: A unified data subset selection and active learning framework for computer vision. 20/9 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1289-1299 IEEE, 2019.
12

---

[37] R. Khanna, E. Elenberg, A. G. Dimakis, S. Negahban. and J. Ghosh. Scalable greedy feature selection via weak submodularity. arXiv preprint arXiv:1703.02725: 2017. 2017.
[38] K. Killamsetty, D. Sivasubramanian, B. Mirzasoleiman, G. Ramakrishnan, A. De, and R. Iyer. Grad-match: A gradient matching based data subset selection for efficient learning. arXiv preprint arXiv22033.00123 2021.
[39] K. Killamsetty, D. Subramanian, G. Ramakrishnan, and R. Iyer. Glister: A generalization based data selection framework for efficient and robust learning. In AAAI, 2021.
[40] K. Kirchhoff and J. Bilmes. Submodularity for data selection in machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 131-141 2014.
[41] P. Koley, A. Saha, S. Bhattacharya, N. Ganguly, and A. De. Demarcating endogenous and exoge- nous opinion dynamies: An experimental design approach. arXiv preprint 4rX1::2102.05954 2021.
[42] K. Konyushkova, R. Sznitman, and P. Fua. Learning active learning from data. arXiv preprint arXiv:1703.03355, 2017.
[43] S. Kumar, X. Zhang, and J. Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In KDD, 2019.
[44] B. Lehmann, D. Lehmann, and N. Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behuvior, 55(2):270-296, 2006.
[45] S. Linderman and R. Adams. Discovering latent network structure in point process data. In International Conference on Machine Learning, pages 1413-1421. PMLR, 2014.
[46] T. J. Liniger. Multivariate hawkes processes. PhD thesis, ETH Zurich, 2009.
[47] S. Liu and M. Hauskrecht. Event outlier detection in continuous time. In International Conference on Machine Learning, pages 6793-6803. PMLR, 2021.
[48] Y. Liu, R. Iyer, K. Kirchhoff, and J. Bilmes. Svitchboard ii and fisver i: High-quality limited- complexity corpora of conversational english speech. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
[49] L. Lorch, A. De, S. Bhatt, W. Trouleau, U. Upadhyay, and M. Gomez-Rodriguez. Stochastic optimal control of epidemic processes in networks. arXiv preprint 4rXiv:1810.13045. 2018.
[50] L. Lorch, W. Trouleau, S. Tsirtsis, Szanto, Schölkopf, and M. Gomez-Rodriguez. spa- tiotemporal epidemic model to quantify the effects of contact tracing, testing, and containment. arXiv preprint arXiv:2004.0764f, 2020.
[51] M. Lucic, M. Faulkner, A. Krause, and D. Feldman. Training gaussian mixture models at scale via coresets. The Journal of Machine Learning Research, 18(1):5885-590 2017.
[52] H. Mei and J. M. Eisner. The neural hawkes process: A neurally self-modulating multivariate point process. In NIPS, 2017.
[53] H. Mei, G. Qin, and Fisner. Imputing missing events continuous-time event streams. In International Conference on Machine Learning, pages 4475-4485. PMLR, 2019.
[54] M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pages
Springer, 1978.
[55] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák, and A. Krause. Lazier than lazy greedy. arXiv preprint arXiv:1409.79)) 2014.
[56] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, Vondrák, and A. Krause. Lazier than lazy greedy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015,
13

---

[57] B. Mirzasoleiman, J. Bilmes, and J. Leskovec. Coresets for data-efficien training of machine learning models. In Proc. ICML, 2020.
[58] B. Mirzasoleiman, K. Cao, and J. Leskovee. Coresets for robust training of deep neural networks against noisy labels. Advances in Neural Information Processing Systems, 33, 2020.
[59] M. Mitrovic, M. Bun, A. Krause, and A. Karbasi. Differentially private submodular maximiza- tion: Data summarization in disguise. International Conference on Machine Learning, pages 2478-2487. PMLR, 2017.
[60] S. A. Myers, C. Zhu, and J. Leskovec. Information diffusion and external influence in networks. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 2012.
[61] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 1978.
[62] Y. Ogata. On lewis' simulation method for point processes. IEEE transactions on information theory, 27(1):23-31, 1981.
[63] C. Qian, J.-C. Shi, Y. Yu, K. Tang, and Z.-H. Zhou. Subset selection under noise. pages 3560-3570, 2017.
[64] C. Qian, Y. Yu, and K. Tang. Approximation guarantees of stochastic greedy algorithms for subset selection. In IJCAI, pages 1478-1484, 2018.
[65] M.-A. Rizoiu, L. Xie, S. Sanner, M. Cebrian, Yu, and P. Van Hentenryck. Expecting to be hip: Hawkes intensity processes for social media popularity. In WWW, 2017.
[66] M.-A. Rizoiu, S. Mishra, Q. Kong, M. Carman, and L. Xie. Sir-hawkes: on the relationship between epidemic models and hawkes point processes. The Web Confernce, 2018.
[67] H. Sasaki, T. Takenouchi, Monti, and Hyvarinen. Robust contrastive learning and nonlinear ica in the presence of outliers. In Conference on Uncertainty in Artificial Intelligence, pages 659-668. PMLR, 2020.
[68] Schreiber, Bilmes, and W. S. Noble. apricot: Submodular selection for data sum- marization in python. Journal of Machine Learning Research, 21(161):1-6, 2020. URL http://mmlooggpaapprrsv21111661
[69] O. Sener and S. Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference Learning Representations, 2018.
[70] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithums. Cambridge university press, 2014.
[71] M.-L. Shyu, S.-C. Chen, K. Sarinnapakorn, and I.. Chang. novel anomaly detection scheme based on principal component classifier. Technical report, 2003.
[72] A. Singla, S. Tschiatschek, and A. Krause. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. 2016.
[73] S. Soni, S. L. Ramirez, and J. Eisenstein. Detecting social influence in event cascades by comparing discriminative rankers. In The 2019 ACM SIGKDD Workshop on Causal Discovery, pages 78-90 98-99,000 2019.
[74] B. Tabibian, U. Upadhyay, A. De, A. Zarezade, B. Schölkopf, and M. Gomez-Rodriguez. Enhancing human learning via spaced repetition optimization. PNAS, 2019.
[75] Y. Tanaka, Kurashima, Fujiwara, T. Iwata, and H. Sawada. Inferring latent triggers of purchases with consideration of social effects and media advertisements. In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, pages 543-552, 2016.
(76] U. Upadhyay, A. De, and M. Godez-Rodriguez. Deep reinforcement learning of marked temporal point processes. arXiv preprint 1805003000009300 2018.
14

---

[77] I. Valera, M. Gomez- Gomez-Rodrigee Rodriguez, and K. Gummadi. Modeling diffusion of competing products and conventions in social media. arXiv preprint arXiv:1406.0516, 2014.
[78] Y. Wang, G. Williams, E. Theodorou, and L. Song. Variational policy for guiding point processes.
In International Conference on Machine Learning, pages 3684-3693, PMLR, 2017.
[79] K. Wei, R. Iyer, and J. Bilmes. Fast multi-stage submodular maximization. In International conference on machine learning, pages 1494-1502 1502. PMLR, 2014.
[80] K. Wei, Y. Liu, K. Kirchhoff, and J. Bilmes. Unsupervised submodular subset selection for speech data. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4107-4111. I. IEEE, 2014.
[81] K. Wei, R. Iyer, and J. Bilmes. Submodularity in data subset selection and active learning, In International Conference on Machine Learning, pages 1954-1963, 2015.
[82] Xiao, Yan, S. Chu, X. Yang, and Zha. Modeling the intensity function of point process via recurrent neural networks. In AAAI, 2017.
[83] Y. Yuan, F. E. Bachl, F. Lindgren, D. L. Borchers, J. B. IIlian, S. T. Buckland, H. Rue, Gerrodette, et al. Point process models for spatio-temporal distance sampling data from large-scale survey of blue whales. The Annals of Applied Statistics, 11(4)2277-22977, 2017.
[84] A. Zarezade, A. De, U. Upadhyay, H. R. Rabiee, and M. Gomez-Rodriguez, Steering social activity: A stochastic optimal control point of view. J. Mach. Learn. Res., 18:205-1, 2017.
[85] A. Zarezade, A. De, U. Upadhyay, H. Rabiee, and M. Gomez-Rodriguez. Steering social activity: A stochastic optimal control point of view. JMLRR 2018
[86] H. Zhang and Y. Vorobeychik. Submodular optimization with routing constraints. In Proceedings of the AAAI conference artificial intelligence. volume 30, 2016.
[87] Q. Zhang, A. Lipani, O. Kirnap, and E. Yilmaz. Self-attentive hawkes processes. ICML, 2020.
[88] Zhu, W. Chen, and L. Chen. Robust linear subspace for image retrieval. In Proceedings of the 2020 12th International Conference on Machine Learning and Computing, pages 390-394, 2020.
[89] Zuo, H. Jiang, Z. Li, T. Zhao, and Zha. Transformer hawkes process. In ICMI., 2020.
15


Reviews:
[{"review_id": "lxJPd0aYGp", "reviewer": "Reviewer_mzmy", "summary": "This paper studies a particular kind of temporal point process, with a focus on trying to identify exogenous events. The problem is formulated as a set function maximization, some theoretical results about monotonicity and alpha-sub-modularity are presented, a stochastic greedy algorithm (based on [38]) is proposed, and some experiments are conducted.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper makes some good theoretical contributions to the literature; it could have been (and could yet become) a stronger paper than its current form. I am left with the sense that there are innovative ideas here, but the results do not quite match up. I am open to upgrading my score after the rebuttal period, particularly if the authors can either convince me about some of their experiment-related choices, and/or make revisions. Let me begin with my major concerns about the paper.\n\nExperiments:\n\nI was enjoying the paper and was looking forward to giving it a strong accept, until I reached the experiments section, which made me change my mind instantly. I’m baffled by the authors’ choices. The paper is essentially about identifying exogeneous events, so I don’t understand why Section 5 delves into predicting next times and next labels. If they want to target these tasks, they are not considering the appropriate baseline temporal point process models. \n\nMy conjecture is that the authors felt they needed to use real data, and since real data does not usually come with labels about exogeneous / endogenous, they decided to tackle the prediction task. In the process, they have left out relevant baselines for this task. I believe they were better off focusing on synthetic data and showing that their method is able to identify exogeneous events better than relevant baseline approaches. I am not convinced their model is better than the state-of-the-art for prediction (it probably isn’t, which is fine).\n\nI have some clarification questions about the experiments:\n\n1. What exactly are the baselines in 5.1 doing? If I understand the task correctly, it is to predict the next time/label given the history of events. So, at any event occurrence in the test set, each model predicts the next time and event label. Is that correct? Are all of the baseline models generative models, i.e. can they generate new data? And why do they need to identify the exogenous events if the task is merely prediction? I would really like to understand what the authors were thinking here. It seems this entire experiment should be done with synthetic data, where the task is to identify exogeneous vs. endogenous events.\n2. Why did the authors not compare with more recent models such as neural Hawkes, etc. for Table 2?\n\nLiterature:\n\nFor a paper with so many references, I’m surprised the authors have left out a lot of relevant literature. First, they have left out literature on outliers in temporal point processes, which is very closely related to the submission. I would be interested to hear how the authors think their work is different, and why they did not consider some of these as suitable baselines. I list a few papers below about outliers and also missing data (which I think should also be mentioned):\n\nEvent Outlier Detection in Continuous Time: \nhttp://proceedings.mlr.press/v139/liu21g/liu21g.pdf\n\nDetecting Anomalous Event Sequences with Temporal Point Processes:\nhttps://arxiv.org/abs/2106.04465\n\nImputing missing events in continuous-time event streams: \nhttp://proceedings.mlr.press/v97/mei19a/mei19a.pdf\n\nLearning Temporal Point Processes with Intermittent Observations:\nhttp://proceedings.mlr.press/v130/gupta21a.html\n\nThe authors mention multivariate point processes right at the end, but do not refer to the vast amount of literature on graphical models for temporal point processes. Some of this work is a generalization of the model considered in the paper. Here are some references:\n\nUniversal Models of Multivariate Temporal Point Processes: \nhttp://proceedings.mlr.press/v51/gunawardana16.html\n\nProximal Graphical Event Models:\nhttps://papers.nips.cc/paper/2018/file/f1ababf130ee6a25f12da7478af8f1ac-Paper.pdf\n\nAlso, I recommend citing the following paper, since it models exogenous events that affect state variables in a continuous-time Bayes net. Event-Driven Continuous Time Bayesian Networks:\nhttps://ojs.aaai.org//index.php/AAAI/article/view/5725\n\n\nOther comments/suggestions:\n\nThe term “externalities” is mentioned in the Abstract, with no explanation.\n\nThe description about the state-of-the-art in line 36 is inaccurate. Multivariate models do not consider these with “equal likelihood”. Please fix this line.\n\nI recommend title case for section headings.\n\nIt may be worthwhile explaining the distribution choices in equation (4).\n\nI found page 5 dense and hard to read. The work itself seems like a good contribution but its hard to follow. I suggest breaking it up further and adding more examples that clarify implications of some of the results. More discussion is needed here. Importantly, I think it’s very important to add more caveats about the specific MTPPs that are in scope for some of the results.\n\nEquation (11) looks wrong for both parts. Lower and upper bounds are identical on the left, and t is used instead of y on the right.\n\nIs k assumed known in algorithm 1? How is it determined in practice? Later on, it seems it has a major effect on results.\n\nCan the authors say more about the subset sizes in step 3 of Algorithm 1? I understand that any subset is equally likely to be chosen. It seems that if small subsets are chosen, the algorithm is indeed efficient but performance could be poor. Did they try experiments where they controlled the subset size?\n\nFigure 1 is not as easy to read as the authors perhaps intend. I could not spot the great results that the authors claim. I see both greener and redder as my eyes scan to the right. Perhaps a table with classification numbers would help here?\n\nThere is a mistake in lines 315-317: 7 datasets are implied here but only 5 were used.\n\nThere are several typos/grammatical errors. Here are some: line 120 (allows), 171 (variety), 184-186 (entire sentence needs editing), 332 (hyper-parameters), 335 (on in), etc.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should say much more about scope of their work; please see comments in my main review.", "review_text": "", "extra_scores": {"ethical_concerns": "I have no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dhB5hryDLS", "reviewer": "Reviewer_Ls8f", "summary": "This paper aims at identifying the set of exogenous events from a set of unlabeled events for learning marked temporal point process. This paper shows solving the exogenous event set selection problem, in conjunction with parameter estimation problem, can be achieved by maximizing a monotone and alpha-submodular set function and then proposes TPP-SELECT framework. The experiments on both synthetic and real data show the proposed method performs better than baselines.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Overall, this paper is well organized and explains the framework clearly.\n2. This paper targets at a very important and interesting problem, i.e., identifying the set of exogenous events without labels for marked temporal point processes. And it’s novel that applying submodular set function method to this problem, although it seems to be a relatively straightforward application.\n3. The theoretical analysis is quite thorough.\n\nUpdate:\nThank the authors for their comments. Most of my concerns are addressed. I will keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The current method doesn’t consider the triggering patterns among endogenous events, while there always exists a branch process among them. I wonder to know if this work can be extended to deal with such structure.\n2. In Table 1, most of the mark prediction errors are larger than 0.5. Does there exist sample imbalance in those data set? Maybe ROC or AOC is a more suitable metric? I also suggest the authors test their method on data with different ratios of exogenous events to endogenous events.\n3. There are some errors in Table 2: (1) Base MTPP achieves better results on Election data for time prediction error and on Club data for mark prediction error; (2) Base MTPP gets the same results with TPP-SELECT on BookOrder data for time prediction error. The authors should be more careful for the experimental results.\n4. From Table 2, it seems base MTPP achieves comparable results with TPP-SELECT. However, I think base MTPP is much more efficient than TPP-SELECT. I suggest the authors provide further comparisons on convergence rate and run-time.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "Q4ZyyMRj7Sv", "reviewer": "Reviewer_w3dd", "summary": "This paper presents a method for identifying hidden labels indicating whether each event has been triggered by exogenous or endogenous influence. The parameter estimation problem of temporal point processes with event selection procedures is reformulated as a set function optimization problem. To solve this problem, the authors propose an approximate algorithm. The effectiveness of the proposed model is demonstrated using synthetic and real-world datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The major contribution of this paper is to bridge between the point process estimation problem and the submodularity and to develop a feasible optimization algorithm. This is technically solid. Thus, my opinion tends to accept. But there are some questions/suggestions as follows.\n\n(1) In this paper, the exogenous events are regarded as those that are triggered by background intensities. They are defined as constants generated from probability distributions, as in Eq. (4). In a practical situation, one would like to model them as time-dependent functions such as periodic functions. Does the proposal allow such situations?\n\n(2) Another option to efficiently infer triggering labels is the use of Gibbs sampler for latent variables (i.e., labels). Such methods are used for analyzing social and advertising effects, as in [R1, R2, R3]. They can also discern the events that are triggered by background intensity. These studies might be related to those that are cited in \"Modeling external effects\" of Section 1.3. It would be great to add a discussion about the differences and advantages of the proposal against these prior works. \n\n[R1] T. Iwata, A. Shah, and Z. Ghahramani. Discovering Latent Influence in Online Social Activities via Shared Cascade Poisson Processes, KDD, 2013.\n\n[R2] Scott W. Linderman, et al., Discovering Latent Network Structure in Point Process Data, ICML, 2014.\n\n[R3] Y. Tanaka, et al., Inferring Latent Triggers of Purchases with Consideration of Social Effects and Media Advertisements, WSDM, 2016.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see comments (1) and (2) in my main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "CxIB4cjGn-C", "reviewer": "Reviewer_8RFc", "summary": "The authors propose an approach to separate exogenous and endogenous events generated by marked temporal point processes (MTPPs). In this context, an event consists of a timestamp and a mark, which is assumed to be a category or class. Many MTPPs are self-exciting or self-inhibiting so that new events are generated due to the influence of previous events--these are endogenous events. Other events are considered to be exogenous events. Given a set of events, the authors proposed approach attempts to select a subset of exogenous events using a stochastic greedy approach. Along the way, they establish some important theoretical properties regarding monotonicity and submodularity of MTPPs that allows them to derive an approximation guarantee for their algorithm. They also demonstrate reasonable empirical results on simulated and real data sets.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality: High**  \nWhile the problem of separating exogenous and endogenous events in temporal point processes (TPPs) or MTPPs is not new, the proposed approach completely changes the way we think about exogenous and endogenous events in MTPPs. The typical approach, as the authors mention, is to assume that the conditional intensity function $\\lambda(t)$ is the sum of exogenous and endogenous components, which are then treated as a single MTPP. This sum is then treated as the starting point to separate exogenous and endogenous.\n\nThe authors instead propose to think about exogenous and endogenous as separate MTPPs whose events are interleaved so that they look like they are generated from a single MTPP. They demonstrate the relationship between their approach and the usual sum approach in Appendix B.1. They exploit their new modeling approach to better classify exogenous and endogenous events.\n\nThe discussion of related work is fairly comprehensive. One missing reference is Li and Zha (2013), who use a mixture of linear Hawkes processes to classify events as being from different classes.\n\nReference:\nLi, L., & Zha, H. (2013). Dyadic event attribution in social networks with mixtures of hawkes processes. Proceedings of the 22nd ACM international conference on Conference on information & knowledge management - CIKM '13, 1667-1672. doi:10.1145/2505515.2505609\n\n**Quality: Moderate**  \nThe quality of the theoretical results is higher than the experimental results, in my opinion (although I did not carefully check proofs). Theorems 3-6 enable the authors to derive the approximation guarantee for their algorithm (Theorem 7), and as the authors note, it may be of independent interest.\n\nThe experimental results presented suggest that the proposed TPP-Select algorithm works, but does not establish superiority of TPP-Select compared to baselines at the proposed task: separating exogenous and endogenous events. The authors opt to present only qualitative simulation results while deferring quantitative results to Appendix E. I think this is a mistake. Furthermore, the authors don't compare error rates of different approaches with respect to classification of exogenous/endogenous; instead, they only evaluate prediction error rates.\n\nI would suggest 2 additional experiments:\n- On your current synthetic data, measure also classification error for TPP-Select and compare it to the EM and k-means baselines, which also attempt to identify the exogenous event set.\n- On your real data experiments, assume that all events are endogenous and then inject (interleave) some fake events generated according to your exogenous model. Then evaluate classification error with respect to these fake events.\n\n**Clarity: Moderate**  \nThe quality of the presentation is decent, with lots of minor issues as I list below. More importantly, I had to read through almost the entire paper before I understood the distinction between exogenous and endogenous that the authors are making. I would suggest showing a linear Hawkes process as an illustrative example in Section 2.2 to clearly show that $\\mu$ corresponds to the exogenous component.\n\nThe choice of experiment results to include in the main paper and supplement could also be improved. I think Figure 1 and 2 should go to the supplement while something similar to Figure 3 should go into the main paper (see discussion above for improvements to the simulation experiments).\n\nMinor issues:\n- Definition of $\\lambda(t)$ in (1) is a bit sloppy--it should be the limit of the stated quantity as $dt \\rightarrow 0$.\n- In equation (9), the subscript $\\lambda$ on $\\theta$ and $\\kappa$ should be replaced with the black dot that is being used elsewhere.\n- Line 211: MTTPs -> MTPPs\n- Line 295: missing end ) in the first exp function\n\n**Significance: High**  \nThis paper presents a novel way of thinking about TPPs. Given the large amount of research being done on TPPs recently (particularly non-linear and neural TPPs), I think this has the potential to be very impactful.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Both are discussed in the supplement. The discussion of limitations is somewhat brief and should be expanded upon. Another limitation that I noticed is that the proposed algorithm is a hard decision algorithm--unlike the EM algorithm baseline used in this paper or the variational inference approach in Li and Zha (2013), which output a probability that a given event is exogenous.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission provides useful theory and experimental support for methods to label Marked Temporal Point Processes. There was extensive engagement between the authors and reviewers, and the reviewers came away well satisfied by the extended experiments. We ask that the authors please update the paper to incorporate as much of the useful additional exposition as possible, updating the main paper where possible or including supplemental material where appropriate. 
Decision: Accept (Poster)