Fast and Accurate Spreading Process Temporal Scale Estimation
Authors: Abram Magner
Carolyn S Kaminski
Petko Bogdanov
Venue: Accepted by TMLR ()

Abstract: Spreading processes on graphs arise in a host of application domains, from the study of online social networks to viral marketing to epidemiology. Various discrete-time probabilistic models for spreading processes have been proposed. These are used for downstream statistical estimation and prediction problems, often involving messages or other information that is transmitted along with infections caused by the process. These models generally model cascade behavior at a small time scale but are insufficiently flexible to model cascades that exhibit intermittent behavior governed by multiple scales.  We argue that the presence of such time scales that are unaccounted for by a cascade model can result in degradation of performance of models on downstream statistical and time-sensitive optimization tasks.  To address these issues, we formulate a model that incorporates multiple temporal scales of cascade behavior.  This model is parameterized by a \emph{clock}, which encodes the times at which sessions of cascade activity start.  These sessions are themselves governed by a small-scale cascade model, such as the discretized independent cascade (IC) model.  Estimation of the multiscale cascade model parameters leads to the problem of \emph{clock estimation} in terms of a natural distortion measure that we formulate.  Our framework is inspired by the optimization problem posed by DiTursi et al, 2017, which can be seen as providing one possible estimator (a maximum-proxy-likelihood estimator) for the parameters of our generative model. We give a clock estimation algorithm, which we call FastClock, that runs in linear time in the size of its input and is provably statistically accurate for a broad range of model parameters when cascades are generated from any spreading process model with well-concentrated session infection set sizes and when the underlying graph is at least in the semi-sparse regime.  We exemplify our algorithm for the case where the small-scale model is the discretized independent cascade process and extend substantially to processes whose infection set sizes satisfy a general martingale difference property. We further evaluate the performance of FastClock empirically in comparison to the state of the art estimator from DiTursi et al, 2017.  We find that in a broad parameter range on synthetic networks and on a real network, our algorithm substantially outperforms that algorithm in terms of both running time and accuracy.  In all cases, our algorithm's running time is asymptotically lower than that of the baseline.


Published in Transactions on Machine Learning Research (11/2022)
Fast and Accurate Spreading Process Temporal Scale Esti- mation
Abram Magner
amagnerGalbany.edi edu
University at Albany, SUNY
Carolyn Kaminski
ckaminskiilallanny.cco edu
University at Albany, SUNY
Petko Bogdanov
phoydanov@albangg.om edu
University at Albony, SUNY
Reviewed on OpenReview: https: // openreview. net/ forum? id= K4SWTEdUSP
Abstract
Spreading processes on graphs arise in a host of application domains, from the study of on- line social networks to viral marketing to epidemiology. Various discrete-time probabilistic models for spreading processes have been proposed. These are used for downstream statisti- cal estimation and prediction problems, often involving messages or other information that transmitted along with infections caused by the process. These models generally model cascade behavior small time scale but are insufficiently flexible to model cascades that exhibit intermittent behavior governed by multiple scales. We argue that the presence of such time scales that are unaccounted for by a cascade model can result in degradation of performance of models on downstream statistical and Lime-sensilive optimization lasks. To address these issues, we formulate a model that incorporates multiple temporal scales of cascade behavior. This model parameterized by clock, which encodes the times at which sessions of cascade activity start. These sessions themselves governed by small- scale cascade model, such the discretized independent. cascade (IC) model. Estimation of the multiscale cascade model parameters leads to the problem of clock estimation in terms of natural distortion measure that we formulate. Our framework is inspired by the optimization problem posed by DiTursi et al, 2017, which can be seen as providing one possible estimator (a maximum-proos likelihood estimator) for the parameters of our generative model. We give a clock estimation algorithum, which we call FastClock, that runs in linear time the size of its input and is provably statistically accurate for a broad range of model parameters when cascades well-concentrateed session infection set sizes and when the underlying graph is at least in the semi-sparse regime. We exemplify our algorithm for the case where the small-scale model is the discretized independent cascade process and extend substantially to processes whose infoction sot sizes satisfy a general martingale difference property. We further evaluate the performance of Clst empirically in comparison to the state of the art estimator from DiTursi al, 2017. We find that in broad parameter range on synthetic networks and on real network, our algorithm substantially outperforms that algorithm in terms of both running time and accuracy. In all cases, algorithm's 's running time is asymptotically lower than that of the baseline.
generated from any spreading process model with
1 Introduction
There are a variety of well-established and simple probabilistic generative models for graphs and and in- fectious processes that these graphs. In this work specifically focus models for spreading

---

Published in Transactions on Machine Learning Research (11/2022)
processes networks such the diffusion of innovation (Montanari & Saberi 2010), information (Bakshy et al. 2012) and misinformation (Shin et al. 2018) in social networks. In such models, every node al a given time has a state, and the model stipulates the conditional probabilities of nodes being in given states at future times, given their states at the current time.
Typically, these models only focus on a single, uniform time scale, thus ignoring global synchronizing events that occur in reality (such as periodic daily/weeki, business schedules governing the actions of network agents). In this work, address modeling and estimation of parameters in the common scenario where spreading process activity occurs intermittently, according to global synchronizing schedule, in Exam- 1
Example 1 (A scenario leading to intermittent spreading process activity). Consider cascade (of, soy, hashlag) among users of online social nelwork. These users may interact with the network only during certain times of day, owing to their work schedules. For instance, the bulk of interactions may occur in the morning, during one's lunch break, during one's afternoon tea, and after work. Infections are likely to proceed only during these periods of activity, during which they spread stochastically according to a more granulor temporal process. See Example 2 for a refinement of this scenario, using the terminology of our model.
The scenario just presented involves two time scales:
1. A larger time scale, consisting of sequence of sessions during which local spreading process activity occurs.
2. A smaller time scale during each session, consisting of local spreading process activity as captured by a typical model.
It is important to take these multiple scales into account in model building and subsequent parameter estimation, for a variely of reasons:
Failing to take the larger time scale into account (i.e., assuming that the process is entirely governed by the smaller time scale) leads erroncous parameter estimates for the smaller time scale model.
Even when the smaller time scale model parameters are known, failure to account for the larger time scale leads to error in downstream statistical inference and optimization tasks, such as cascade doubling time prediction (Cheng et al. 2014 and message model parameter estimation.
3. An estimate of the larger time scale or parameters of a model generating it can themselves be used as fcatures in machine learning problems involving cascades, such as cascade classification (c.g., where class labels are "misinformation" or "true information").
We discuss few motivations in more detail in Section Furthermore, in general, given cascade data in a large network, the form of the intermittencies in the large time scale are not obvious and may vary depending on the community from which the cascades originated since different communities and cascades consisting of different types of information (e.g., long-form essays versus infographics versus videos versus single-panel web comics) may operate according to different schedules. It is thus important to learn these intermittencics from observations, as we do in the present work.
Given these motivations, the present paper concerned with
the formulation of a generative model for network cascades that is parametrized by an arbitrary large time scale (which itself may contain events on multiple scales), with the smaller time scale generated by some given standard model;
the formulation of the estimation problem for the parameters of the large time scale from cascade observations;
2

---

Published in Transactions on Machine Learning Research (11/2022)
algorithmic techniques for provably accurate and computationally efficient solution of the above estimation problem.
Our work is inspired by the works of DiTursi el al. 2017 and DiTursi el al. 2019 which took the following approach: they formulated problem of clock recovery, in which a "ground-truth" cascade is generated by the independent cascade model of Kempe et al. (000)) then perturbed by a "clock transformation", parametrized by a clock (a sequence of observation timestep endpoints) to yield an observed cascade. The task that they formulated an optimization one: from the observed cascade, recover the clock with maximum likelihood. Among other contributions, they formulated a dynamic programming algorithm that provably achieves this maximum likelihood, but with a large asymptotic rumning time (see the discussion in Section [.3 Concretely, their dynamic programming algorithm can be seen as implementing one possible estimator for the clock parameter of our generative model, in the case where the cascade, viewed on the large time scale, is distributed according to the independent cascade model of Kempe et al. (2003). We are the first to empirically study the accuracy of their estimator, in terms of distance to the ground truth parameters, and, thus, it is not a priori clear what types of graphs are most favorable for its performance.
In the present work, we take a more statistical approach: rephrase the clock estimation problem via generative model that produces cascades with multiple temporal scales. In this model, clocks become the parameters of the larger temporal scale, and the task is to estimate the unknown clock (the parameter) from the data that the model produces. We make this estimation task rigorous by introducing a notion of distortion between clocks, which measures the accuracy of an estimated clock. The clocks in our work are the same type of object as those in the prior work (but interpreted differently).
Our reformulation valuable for both performance and philosophical reasons: 1. In the prior work, is unclear what physical mechanism is being modeled by the clock transformation which operates on an already generated cascade, while, in contrast, in our work, clocks are a natural product of global intermittent influences on individual node behavior.
In the prior work, the "ground-truth" cascade uses a notion of timesteps that do not map to physical times, while in our work, the observed cascade operates in discretization of real, physical time.
3. Prior work does not attempt, even empirically, to quantify the distance between the ground-trun -trth clock (the one that actually generated the data) and the estimated one maximizing the likelihood of the estimated clock, rather than ensuring accuracy, is treated as the end goal. In contrast, in our work give rigorous estimation formulation, which allows us to quantify the accuracy of the maximum likelihood estimator versus alternatives (such as the estimator that we introduce). As detailed throughout this paper, our resulting estimator substantially outperforms the previous work's dynamic programming- based maximum likelihood estimator in terms of running time and, on all of our synthotic data and in a broad range of parameters on real networks, in terms of accuracy. Across the entire parameter range on real nelworks, the average accuracy of our estimator is quite low (consistently less than 0.07).
1.1 High-level problem formulation
We next state our problem at a slightly more technical level (we give all formal formulations in Section 2 To do so, we first introduce preliminaries spreading process modcls.
spreading process models. Several well-studied information diffusion models on graph G assume a discrete timcline in which at every time step nodes of G' participate in the diffusion process (i.e., become "infected") based on influence from network neighbors who became infected in past time steps. Here, a timeline is simply an ordered sequence of indices: 0, 0,1...... The output of a spreading process model after timestop N is an infection sequence of disjoint vertex subsets S.. St, SN, where S, is the set of vertices of G that became infected during timestep t. For example, according to the independent cascade model infected nodes have one chance to infect their neighbors, while in the linear threshold model nodes
Preliminaries:
3

---

Published in Transactions on Machine Learning Research (11/2022)
get infected when a critical fraction of their neighbors have been infected in any prior time steps (Kempe let al. 2003). In addition to the discrete time models above, there also exist continuous-time counterparts. For the purposes of computation, the latter are generally discretized by a standard recipe: given resolution model over a time interval [0, one defines the ixdttiretization of the cascade to be the infection sequence S = (Sy, S1...,, STr/81), where S, consists of the set of vertices infected during the time interval jo. In the discussion that follows, we will thus state our formulation in the discrete- time case, with the understanding that this is without loss of generality.
8 > 0 and a cascade sampled from a contimuous-tim
Formulation of our two-scale model. To capture our motivating scenario, we will define a new two- scale cascade model, where the smaller scale is given by an arbitrary fixed spreading process model Mo with the property that, at any given time t, a vertex may only transmit infection if it is in the set of active nodes A, at that time.
The generative process that we will define is parametrized by a sequence of time points to, (1,-,,, giving the larger time scale. Intuitively, tj is the time at which the jth session starts. The activity within the jth session (comprising the smaller scale of the model) is dictated by Mo as follows: for any time L E [l ())); the distribution of new vertex infection events is given by Mo conditioned on the active set remaining fixed to its value at time ij. In other words, vertices may become infected in the time interval (z+1,, but the active set is not updated until time 4++1. This assumption is justified whenever nodes' "attention spans" have a finite gramularity, in the sense that newly infected vertices do not become infectious immediately. This is aligned with the intuition of daily activity periods from Example [ and more broadly justified in spreading processes on social networks. We give more specific scenario in Example 2 to illustrate this. In the appendix, Section
G we explain the behavior of our estimator when this assumption does not strictly
hold.
Example (Scenarios illustrating our active set intermittent update assumption). Here, we give more delailed ezamples of scenarios in which spreading process aclivily salisfies our assumplion regarding inter- mittent updating of the active set.
Consider social network such as Facebook, where nodes are people and edges are friendships. We consider cascades in which a person is said to be infecled when they post a particular piece of content. Note that infection of a person is detectable immediately, and can thus be recorded in a dataset. A person is active (f.e., infectious) when other people see what that person has posted. We assume, furthermore, that people have, in any given session (defieed below), limiled reserve of allention, and will thus be focused on posts that occurred prior to the current session.
Now, a session starts when some break in the day happens and ends when the break stops. At the start of a cascade, some initially active vertices (0ese(0) are seen by users in the first session. A subset Speso of these users, during that same session, repost, becoming infected. Neighbors of newly infected vertices do not see these reposts during this session, because of the aforementioned limitations of attention. Thus, the elements of (1eas()) are infected, but they are not active until the next session (which may occur several hours after the current one), at the beginniing of which the attention reserves of their neighbors have been replenished.
An alternative mechanism that could produce the some effect as the allention reserve is a platform playing an active role in displaying posts non-chromologically resulting in delays in the display of post.
We note that in the above ezample, different types of content may plausibly spread according to different clocks. For instance, long videos may be shared only after work hours, while technical essays may be shared during work. Comedic webcomics may be shared throughout the day. Thus, it is of interest to estimate the clocks of different cascades from data, rather than assuming some hard-coded clocks.
Formulation of our estimation problem. Having formulated our two-scale model, we next formu- late the central estimation question that we study in this work: given a sample infection sequence (S.ta (0), (1), (I), Sare (N)) from the two-scale model parametrizod by the larger time scale for t,.,,, the natural question to ask is to what extent to.... ..., ty can be estimated. For many models, this is reducible to a more fundamental problem, which is the central one that we tackle in this work: estimate the assignment of
4

---

Published in Transactions on Machine Learning Research (11/2022)
Timestep g00
A - (5,
S
A. [0. 18.4
Figure An example network and cascade Sobs with corresponding observed infection sequence Sobs = (16). 0.. (0)), encoding that was infected in timestep O, 2 in timestep 1, 5 in timestep 4, and timestep 5. Suppose that this cascade was generated according to our two-scalc model with clock A1 = (10, 0j. [1, 4/, [5. 5]), so that there (16), (2,5), (0)) An esti- mator of the clock, given Soha, might output a different clock: say, A2 ((0, 2/, [3, [3,4], 4), [5, 5]), yiclding an cstimated session-level infection sequence of S (f6, 2), (5), {0}) In Definition 4 we will define distance between clocks, under which Ai and A2 have nonzero distance, because Ag entails that vertices 6 and were both infected in the first session.
are timestops and sessions. Then the (unobscrved) sessiou-level infection sequence s
verlex infection events to the indices sessions during which they occurred. We call this the clock estimation problem. We elucidate this estimation problem by the example Figure T
1.2 Motivating applications
We next discuss several motivating applications for our generative model and for the clock recovery problem. In the listed applications, we explain how failing to account for multiple time scales results in degraded statistical accuracy or optimization performance on downstream tasks. We note that all of these applications involve a nontrivial statistical or optimization task even when the parameters of the small-scale cascade model are known.
Parameter estimation for information models running on top of cascade processes:
one class of applications, one wants make inferences about some extra piece of information (a mossage, sentiment, opinion, etc.) that is spread along with an infection, according to a parametric statistical model (which we will call, for this discussion, information model), and the information associated with given node is statistically dependent on the corresponding information associated with the nodes that infected it.
As a concrete example, consider model of the spread of sentiment (an information model) that runs on cascades generated by our two-scale model parametrized by some nontrivial clock, with the smaller scale generated by the discretized independent cascade model. In particular, the seed nodes v E So of the cascade are endowed with sentiments X, uniformly distributed in [0, 1]. When a node w becomes infected, say, by an unknown subset ((w) of active neighbors of w, the sentiment of is given as follows:
X = 0,0 02)
Σ X #ET(W)
(1)
[(w]]
Here, 01 is bias parameter [0, that represents some base sentiment, and 0g 1] is social influence parameter that governs how much each node w tends to adopt the average sentiment of its infectors. The goal in such a model is to estimate 0,, 02 from observation of a cascade as well as measured sentiments X
Note that even when the parameters of the smaller-scale spreading process model are known, it is of interest to estimate the parameters of the information model from sample cascades. Furthermore, in such applications. clock estimation the main subject of this paper is an essential preprocessing step in order to reduce the complexity of parameter estimation by determining the set of vertices that could have infocted a given vertex w (i.c., the set of active neighbors of w). This set is not observable, owing lack of knowledge of the clock. Furthermore, failure to consider multiple time scales introduces error into the log likelihood function of the information model parameters since
5

---

Published in Transactions on Machine Learning Research (11/2022)
the correct set of active neighbors is unknown. Ultimately, this results in erroncous parameter estimation.
Time-critical tasks: In certain applications, the goal is to optimize some objective function defined on the state of the process, subject to a time deadline that is given as input. For instance, in time-critical influence maximization (Chen et al. 2012b). the problem is to choose seed nodes to optimize the expected number of infections occurring by given limestep.
For a given seed set, the expected number of vertices infected by the deadline may change dramat- ically depending whether not large time scale is incorporated into the model. Intuitively, this is because delays introduced by a large time scale may make the infection of particularly well-connected vertex less likely. Thus, taking into account multiple time scales is essential for the success of model-based time-critical optimization tasks. This is exacerbated even further in cases where different subsets of nodes operate according to different large time scales.
3. Cascade doubling time prediction: The cascade doubling time prediction problem posed in Cheng et al. (2014). A cascade is observed up to a certain time t, and the goal is to produce an accurate estimate of the time at which the number of infected nodes doubles from the number at time t. This problem was introduced as a prototypical prediction problem for cascades. In Example 3 in Appendix C we spell out the details of concrete example in which failure to account for a large time scale results in avoidable inaccuracy in doubling time prediction.
1.3
Prior work
The general topic of analysis of cascades has received large amount of attention, both from theoretical and empirical perspectives. There are many cascade models, with features depending on application domains. For example, the independent cascade (IC) and linear threshold (LTT) models were popularized in Kempe et al. 2003) for the application of influence mazimization. This problem continues to be studied, even in settings where cascade model parameters are known (eee et al. 2016 Abbe et al. 2017). Variations on the influence maximization problem that have time-critical components and, thus, require accurate modeling of multiple time scales in the sense that we study here, have also been studied (Chen et al. 2012a Ali et al., 2019). These models are also used outside the context of influence maxinization, e.g., in modeling the spread of memes on social networks (Adamic et al. 2016).
Statistical prediction tasks involving cascades have also been posed. For instance, the cascade doubling time prediction task was considered Cheng et al. (2014). Other works propose models in which a piece of information, such as a message, an opinion, or a viral genome, is transmitted along with the infection of node (Eletreby et al.] 2020; De al.) 2016 Park al.) (020)). For such statistical problems, statistical inferences about the transmitted information can be disrupted by inaccurate estimation of the set of infoctious vertices at a given time, further motivating generative modeling and estimation that takes into account multiple time scales.
The estimation mothod that we propose and study here, FastClock, bears a resemblance to mothods in the online pounge-poinl delection literature (Veeravalli & Banerjee 2014). Broadly speaking, the goal of that problem to sequentially observe independent and identically distributed random variables X1, X2,.. and to detect, with as few samples as possible, an index after which the distribution of the variables changes. One procedure for this, called CuSum, evaluates for each index j statistic Y, Yj,)) and maintains a sum Z, = E Y. changepoint is declared once Z₁ exccods a certain threshold. In this paper, we define similar rule for detecting session endpoints. In the context of change-point detection, CuSum has been analyzed in both the iid and more general hidden Markov setting (Fuh) 2003). However, our analysis is necessarily substantially different from that of CuSum, which rests on stringent assumptions (e.g., that the X, are sampled from an ergodic Markov chain).
In DiTursi et al. (2017) (see also followup work in DiTursi et al. 2019)). ) the authors formulated a version of the problem of clock recovery from cascade data generated according to an adversarially chosen clock as a problem of maximization of a function of the clock that serves as a proxy (in particular, an upper bound) for the log likehood of the observed cascades. They proposed solution to this problem via.
6

---

Published in Transactions on Machine Learning Research (11/2022)
dynamic programming algorithm. While the dynamic programming algorithm is exact solution to their formulation of the problem, it has a running time of @(n"), where is the total number of vertices in the graph on which the observed cascade runs, This is prohibitively expensive for graphs of moderate to large size. Furthermore, their formulation of the problem makes no comparison of the estimated clock with the ground truth one, and thus there are no theoretical guarantees or empirical evaluations of the accuracy of their estimator (which we call the mazimum likelihood prozy (MLP) estimator) as an approximation the ground truth clock. In contrast, the present work gives a rigorous formulation of the problem as one of statistical estimation of the ground truth clock from observed cascades. We compare proposed algorithm and estimator with the MLP estimator in this framework in terms of both accuracy and running time.
1.4 Our contributions
Our contributions in this work are as follows:
Novel problem formulation. We formulate two-scale generative model for cascades, where the larger time scale is parametrized by an arbitrary clock (which may itself be generated by model with arbitrarily many time scales). We formalize the problem of clock estimation from observed cascades with respect to a natural distortion measure. This distortion measure allows us to quantify the proximity of estimated clocks to the ground truth in a principled manner.
Provably accurate and computationally efficient solutions. We propose a lincar-time algorithm with provable approximation guaranlees for the clock estimation problem. In particular, the distortion between the true clock and our estimate tends to 0 at polynomial rate with respect to the average degree of the graph.
Generality. We first prove our results in the context of Erdös-Rényi graphs in the semi-sparse regime and the independent cascade model. The proofs for this setting contain almost all necessary ingredients for extension of guarantees to a much more general setting: the results also hold when the cardinalities of infection sets St satisfy martingale difference property and the graph is sampled from a sufficiently dense sparse graphon model. We provide the remaining ingredients in Section 3.5 and culminate with more general theorem.
Confirmation of results in simulation on synthetic and real graphs. We bolster our theoretical results via experiments on both real and synthetic graphs and synthetic cascades. We find that the FastClock estimator empirically outperforms the dynamic programming- based estimator from DiTursi et al. 2017 in terms of accuracy and on all of our synthetic graphs and in a broad range of cascade model parameters on a real graph, and substantially in terms of running time on all of our synthetic graphs and for all investigated model parameters real graph. We give our simulation results in Section 3.4 and Appendix D
2 Problem formulation and notation
Our goal this section is to formulate our generative model and the problem of clock eslimalion. We give examples of all definitions in Appendix C
We fix a graph G on the vertex set [n] {1, (1., n), and we define the timeline of length N, for any number N E N, to be the set [[N]] (0, 1, 1.....,yy N). The first ingredient of our framework is cascade model. We will be concerned in the present work with compartmental models, wherein each node may be susceptible (uninfected), active (i.e., infected and able to transmit the infection to its neighbors). or infected (but unable to transmit its infection). We collect the different possible compartments into a set Ω = {S, A, 77 Nodes may carry additional information from an arbitrary set Ω At any given time t, a node E [n] is some state (v, () E Ω D. We call a network state any element of (Ω x 12)
Preliminary definitions:
Definition (Cascade model, observation model). A (discrele-lime) cascade model C is conditional distribution Pel- IX), where X (Ω x D2'" is a network state.
For the bulk of the paper, we will be concerned with the following model of observations of cascades: for sequence of network states (No, X1,.., XN), observe corresponding sequence, called an infection
7

---

Published in Transactions on Machine Learning Research (11/2022)
where Sobe(j) consists of the set of vertices at time j that move into either compartment. A or T according to X5- Note that we do not observe which vertices are active or any of the side information. Any cascade model thus induces probability distribution on infection sequences.
sequence: (0), Sobs
(obs
To begin to define our two-scale generative model, we next define clock, which encodes the timesteps belonging to each session. This will be a parameter of our model.
Definition 2 (Clock). A clock C' with N + sessions on the timeline [[N'']] is partition of [[N'] into N + closed subintervals (i.e., contiguous integer subsets) Co...,, We call the jth such subinterual, for j = 0
to N, the jth session interval.
Given an observed infection sequence Sabs = (Saba (ot,...) a clock C induces an infection sequence Ssess = (Sees (0), Seees (1), ..., S.esa (N)) where Seess (i) = UREC, (kk We call this the infection sequence induced by C' on Sobs
For algorithmic purposes, we note that a clock may be encoded as a sequence of non- negatiee integers giving its right interval endpoints.
Main definition of the generative model: We now define our main generative model. We fix a cascade model Co. which will govern the dynamics of the process during each session. This the small-scale model. In general, it may depend on the length of the session.
Definition (Two-scale generative model for cascades). The twv--caale generative model M(C, To. M(C) is parametrized by clock C, an initial network state Zo E (S) 12')", and a reumber of sessions T. IIs outpul is sequence X1; XI..., of network states, inducing an observed infection sequence Sobee())
For j = 1,..,,, T, at the beginning of the jth session, the network state is given by Z5-1- At each timestep t in the jth session, a nelwork slate is sampled from Co, condilioned on the current nelwork state. Any verler that is newly activated according to Co is set to infected in Xt and active in Zy. For convenience, we also define the infection sequence Seees = seees Secse (
where Ssese(j) consists of the set of vertices infected during session j (so Seess is just the infection sequence induced by C on Sobs). We call Ssess the session-level infection sequence.
Intuitively, this model, vertices infected during a given session only become active in the next session. This is justified in scenarios where nodes are not immediately infectious when they become infected. In this case, sessions may be seen as periods during which current set of active vertices causes infections.
Measuring distortion between clocks: To formulate the problem of estimating the clock of our model, given an infection sequence produced by it, we need means of measuring distortion between clocks. This is our next goal.
An infection sequence S naturally induces a partial order on the set of vertices: namely, for two vertices a, b, a < if and only a e S,,b E Sj for some i < j. Similarly, a clock C applied to an infection sequence Sobe: in the sense of Definition [ induces a partial order. This partial order the one induced by the infection sequence S that C induces on S.
We will consider two clocks Co, O2 to be equivalent with respect to given observed infection sequence Sabe if they induce the same partial order. The reason for this is that two equivalent clocks separate vertices in the same way into a sequence of sessions. We will sometimes abuse terminology and use "clock" to mean "clock equivalence class".
We next define distortion function on clock equivalence classes. This will allow us to measure how far given estimated clock from the ground truth. Note that given an observed infection sequence Sober a clock cannot reverse the order of any pair of events, that the standard Kendall 7 distance between partial orders is not appropriate here.
Definition 4 (Distortion function on clock pairs). Consider two clocks Co. C1 with respect to an observed infection sequence Sohs- We define Disco (i, to be the indicator that the clocks Co and Ci order vertices
8

---

Published in Transactions on Machine Learning Research (11/2022)
and j differently (i.e., that the partial order vertices induced by Cs orders and j and the partial order induced by C1-b does not, for b equal to either 0 or 1). IJ the clocks in question are clear from contexl, we may drop the subscript.
We define the following distortion measure on clock pairs:
dsar, (Co, C1)
Disco.o. (i.5).
(2)
Main problem statement: We finally come to the general problem that we would like to solve:
Definition 5 (Clock estimation). Fix a graph G, a small-scale cascade model Co, and a clock C. An infection sequence Sahs ~ M(C) is generated on G. Our gool is to produce on estimator Ö = C(Sons) of so as to minimize Elds... (C,C)) This is called the clock estimation problem.
The above definition implicitly assumes knowledge of the parameters of the small-scale cascade model. Estimation of these parameters has been studied extensively in the literature and need not necessarily come from cascade observations. We discuss this in the appendix, in Section E Furthermore, knowledge of the initial conditions of the cascade is necessary order achieve an expected estimation error that tends to 0 in general. We thus assume that the initial netw state is given to us. Under mild additional assumptions the model (e.g,, that Ssess (0) consists of ((1) vertices chosen uniformly at random, and that the graph is sparse, so that Seess (0) is an independent set with high probability), the initial set Seess can be inferred
with high probability. We discuss how to do this at length in the appendix, in Section
Specific: small-scale cascade model: Having defined our multiscale generative model, we specify an example small-scale cascade model for our problem. Our approach generalizes beyond this one, as we will explain in Section 3.5
We define the discretized independent cascade. (IC) process.
Definition 6 (Discretized independent cascade process). We fix a graph G, on initial infection set So of vertices in G (given by elements of [n] {1,..., n.), ) a number of timesteps K (giving the length of the session) and probubility porameters Pn. and Pe: both in [0, Here, Pn denotes the probobility of transmission of an infection across an edge, and Pe denotes the probability of infection from an external source. Additionally, we fir a probability distribulion D on N (for simplicily, we will choose the geometric distribulion with mean 1).
When node v becomes active, for every one of its susceptible neighbors w, it draws an independent Bernoulli(p.) random variable. If it is 1, v starts limer by drawing a sample X from D, then defin- ing Te.w to the minimum of X and the number of timesteps remaining in the session. The verter v then becomes inactive (moves to the I state). After Tu timesteps, w becomes active.
In porallel, in given limestep, each susceplible verler becomes aclive with probabilily P'c 11 1 (1 pc) 1/K independent of anything else. This models infection by external circumstances, with probability Pe. over the entire session.
We denote by S₁ the set of nodes that become active in timestep j. The process terminates either after K steps or after all nodes are infected.
There is natural connection between the discretized IC model and the IC model defined in Kempe et al.) (203) via two-scale model: when the small-scale model is the discretized 1C model, the sequence Seess = (Sress (0), (1), Ssess(T) of sets of vertices infected in the sessions of our model is distributed according to the model in Kempe et al. (2003). In that model, there a seed set of vertices Sp that are active at time 0. In each timestep (our sessions), the vertices that were infected in the previous timestep become active, and the vertices that were active the previous timestep become inactive but infocted. Each active vertex chooses to infect each of its neighbors independently with probability Pn. Furthermore, each uninfected vertex becomes infected with probability Pe-
9

---

Published in Transactions on Machine Learning Research (11/2022)
3 Main results: Algorithm, approximation and running time guarantees, generality
In this section, we present our proposed algorithm (Algorithm 1 for clock estimation, which we call FastClock. We give full proofs of all theorems in Appendix B
FastClock takes as input a graph G, an observed infection sequence Sobs = (Sobe Soba and the parameters of the cascade model, including the initial infection set S0eas(0) (see our discussion of this assumption in the previous section), but not including session lengths. The output of the algorithm is an estimated clock č, which takes the form of a sequence of interval right endpoints lg. f1:-.. fN E [[N]], for some N and is an estimate of the ground truth clock C' specified by lu....,NN.
Our algorithm proceeds by iteratively computing the estimate Ey. In the (j + 1)tst iteration, to compute (s+1, it chooses the size of the next interval of the clock so as to match as closely as possible the expected number of newly infected nodes in the next session. We prove that the resulting clock estimate is very close, in terms of ds.... (.,-) to the ground truth clock, using concentration inequalities.
The correctness of Fast Clock is based on the following intuition: if we manage to correctly estimate lo.... 4 then we can estimate the conditional expected number of vertices infected in the (j + 1)-st session of the process (i.e., [s + 1]]-- We can show a conditional concentration result for |Ssess (j + 1)] around its expectation. Thus, we output as our next clock interval endpoint fy+1 the smallest integer 2 Ey for which the number of vertices in S does not exceed its conditional expectation, corrected by a small quantity. This quantity is determined by the concentration properties of the random variable [Seess + 1)] conditioned on the state of the process given by (0),,..,sob((())) We choose the threshold to be such that, under this conditioning, the number of verticos infected in the next session is slightly less than it with probability tending exponentially to 1. Our approximation analysis illustrates that the approximation quality depends on the graph structure and the model parameters.
The significance of the approximation and running time results (Theorems and 2 below for the independent cascade model) is that the clock parameter of our multiscale cascade model can be quickly estimated with provably high accuracy using relatively simple expected value calculations. The generality of our results (well beyond the IC model) is discussed in Section 3.5 As long as the expected number of nodes infected in the next session can be calculated efficiently, the FastClock algorithm can be adapted to a wide variety of cascade models.
3.1 The FastClock algorithm
Before we define our algorithm we introduce some necessary notation. For a session-level infection sequence 3 and a session index t E ($), define (5) to be the a-field generated by the event that the first f session- level infection sets of the cascade process are given by Su, Si.... Sy That is, the event in question is that Ssess (0) Sa ..., (1) S. We also define (5( to be mx(5)= = E[[S
1)1 (S)) For vertex U, we denote by (N(() the set of neighbors of in G. The algorithm is given in Algorithm
After an initialization, the main loop in FastClock (Steps 5-11) iteratively determines the last infection event in the next session of the process (whose endpoint timestep we are trying to estimate), by estimating the expected number of nodes be to be infected in that session (Step 6). The key step in this procedure is the computation of Pe; which we discuss next.
Computing (S() in the discrctized IC model. Let us be more precise in specifying how to compute (e(5)= = E[][Senss (l + 1)| (5()) when the small-scale model is the discretized independent cascade model (see Definition G). A node can be infected in one of two ways: through external factors (governed by pe) via transmission from vertex in S, through an edge. In the latter case, the node must lie in the frontier set (5()), defined as follows: (5) is the set (((5)=N(b)) \ U/ S;; i.e., it is the set of neighbors of S, that we believe to be uninfected at the beginning of cascade session L. See Example 5 in the appendix for an illustration of the definition of frontier sets.
For set of vertices W S [n] and a vertex V E [n], let degw (v) denote the number of edges incident on v that are also incident vertices in W. We can use linearity of expectation to derive closed-form formula
10

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm 1: FastClock
Data: Graph G, small-scale cascade model parameters 8, observed infection sequence
Sobs = (Sobe S (NV)
Result: An estimated clock C.
// An initially empty list for the estimated clock. This will eventually contain sequence of est emated endpoints of clock intervals.
Set Ö = ():
/1 t: index of the
estimated clock interval, i.e., t is index in Ssess the session-level infection sequence.
// lota: the index in Sobs of the beginming of the next estimated clock interval 1ug (k)) = (0));
Sct t == 1, = min
/1 5: the estimated infection sequence approximating the session-level sequence S. Set Su = Soto Append tots to Ō: while lohs + N
// Compute the expected number Me infected nodes in single session of the cascade process, starting from the state of the process estimated so far.
Set 1r: = Seesss + 1)I 05 St)]
Set
t2 tobs + max A
[Sabo S 44 (1 + p4 1/3)
(3)
foba
Append tobs to C:
Set S, U forr infobot11 Sobi
10
Set t = +
11
Set Labs l'sbni
12
end
return Ō;
for (5)::
(+()= = Pe n n [S(
Σ J-0
|9;1
Σ (p. + (1-pa)(1 pr. degs, (t)))
(4)
(EF:(S)
A similar expression can be derived for the more general case where transmission probabilities across edges may differ from each other. The calculation of the summation - 1S,1 can be performed efficiently by keeping track of its value in the t-th iteration of the loop of the algorithm. In the t-th iteration, the value of the summation is updated by adding [Š.] to the running total. Note also that this estimation will be the only difference in our algorithm when applied to alternative cascade models such as the linear threshold model.
3.2 Approximation guarantee for FastClock
Our first theorem gives approximation guarantee for FastClock in the case where the small-scale model is the discretized IC model. It is subject to an assumption about the parameters of the graph model from which G is sampled and about the parameters of the small-scale cascade model, which we state next. is, however, important to note that FastClock itself does not assume anything about the graph. Furthermore, we generalize our guarantees beyond these assumptions in Section 3.5 Theorem
Assumption 1 (Assumptions on random graph model parameters). We assume that G G(n. p) (i.e., that G is sampled from the Frdös-Rényí Réngi model), where p salisfies the following relation with the ground truth
11

---

Published in Transactions on Machine Learning Research (11/2022)
number of sessions T + 1: p d(n -ÎT). and p C'log/nn, for some C > 1. We substanlially relox our modeling assumptions in Section 3.5
The former condition p may be viewed as constraint on T. It is natural in light of the fact that, together with our ussumplions on and Pe. below, il implies that the cascade does not flood the gruph, in the sense of infecting a ((1)-fraction of nodes. Many cascades in practice do not flood the graph in this sense. The lower bounding condition on p implies that the graph connected with high probability. In terms of density, this covers graphs in the semi-sparse regime, wherein the number of edges grows superlinearly with the number of vertices. This is common in real networks with communitiess. We erhibit in Section H several real networks with average degrees that are well within the bounds of our assumption.
Regarding the small-scale cascade process, we assume that it is the discretized IC model from Definition b with the following constroints on the parameters: we assume that Po is some fixed positive constant and that Pe = =lp). Our results also hold if pn. is different for every edge e (so that pn. = =Pa(e)) provided that there are two positive constants 0 < Co. C1 such that for every edge e, Pa(e) E (co.
The assumption that Pv. constant with respect to is natural in the sense that, for many infectious processes, the probability of transmission from node to another should not depend on the number of nodes. The assumption on Pe, the probabilily of infection from exlernal source, is reasonable when the cascude is overuhelmingly driven by network effects, rother than external sources.
Theorem 1 (Main FastClock approximation thcorem). Suppose that Assumption probabilily al least 1 - -8(pp)
holds. We have, with
(C, = 111p))
(5)
where recall that Sahs is the observed infection sequence generated by the two-scale cascade model parametrized by the ground truth clock C, Seess is the session-level infection sequence, and Ó is the es- timate of C that is output by FastClock.
The proof of Theorem 1 uses an auxiliary result (Theorem in the appendix, which we call the FlskClock utility theorem) stating that with high probability, for every the intersection of the session-level infection sequence clement (1) with the estimated infection sequence element S; is asymptotically equivalent in cardinality to (i) itself. We prove this by induction on the session index i, which requires a careful design of the inductive hepothesis. Given the utility theorem, the upper bound on the distortion ds..., (C, follows by summing over all possible pairs (sese(i), (j) infection sequence elements Sseses the session-level infection sequence, then summing over all vertex pairs Saess v Seces (j) This inner sum is approximated using the utility theorem.
3.3 Running time analysis
We have a strong guarantee the running time of FastClock in the independent cascade case. The run- ning time of Fast is asymplotically much smaller than that of the dynamic programming estimator from DiTursi et al. (2017).
Theorem 2 (Running time of FastClock). The FlstClock algorithm for the case where the small-scale cascade model is the discretized independent cascade model runs in time O(N + m), where m is the number of edges in the inpul graph.
3.4 Empirical results on synthetic graphs
In this section, we present empirical results on synthetic graphs and cascades. Our goal is to confirm the theoretical guarantees of FastClock and compare it to the dynamic programeming (DP) algorithm optimizing a proxy the maximum likelihood for observed cascades proposed by DiTursi et al. (017 Our comparative analysis focuses on (i) distance of the estimated clock from the ground truth clock (see Definition 4 and (ii) empirical running time of both techniques. More extensive empirical results on synthetic and real graphs are included in the appendix, Section
12

---

Published in Transactions on Machine Learning Research (11/2022)
FastClock
FastClock
DP
DP
FastClack
distencee
0.3
101
Festtlock
221
DP
0.2
0.1
0.0
3000
3000
5020
10000
0.01 0.05 0.1
0.15
0.25
0.3
number of podes
2000
1368
0.03
011
0.35
0.25
0.5
number of redes
pm
(a)
(b)
(c)
(d)
Comparison the distance and runtime estimated clocks by FastClock and baseline DP from DiTursi et al. 2017) on Erdös Rényi graphs (default parameters for all experiments: pa. = 0.1, Pe = 10-7, 3000, p = n 1/3 ssretcc
Figure 2:
unless varying the specific experiment). (b): Varying graph size. (c), Varying infection probability pa.
We generate synthetic graphs using the Erdös Rényi model (experiments using stochastic block models are included in Section D). We then generate synthotic cascades on each graph using the independent cascade (IC) model. Since both algorithms under consideration are invariant to infection timers in the small-scale model, we determine the set of vertices infected in each session according to IC model of Kempe et al. (2003). then assign each infected vertex a uniformly random infection time within its session, which we fix have length (some integer which we call the stretch factor of our cascade). As in our theorems, we denote by Seess the session-level infection sequence and by Sobs the observed process infection sequence. These implicitly specify a ground-truth clock C. We note that while all of our experiments involve sessions with uniform length, our theoretical contributions are more general. We then employ both FastClock and the maximum likelihood proxy algorithm to estimate the ground truth clock from Sobe. We draw 50 samples for each setting and report average and standard deviation for both running time and quality of estimations for each setting.
Experiments on Erdös Rényi graphs. We report subset of the results of our experiment on Erdös- Rényi graphs in Figure 2 With increasing graph size FastClock'ss distance from the ground truth clock diminishes (as expected based on Theorem [ while that of DP increases (Fig, 2(a] Note that DP optimizes proxy to the cascade likelihood and in our experiments tend to associate too many early timesteps with early sessions, which for large graph sizes results in incorrect recovery of the ground truth clock. Similarly, CastClock's s estimate quality is better than that DP for varying on Pa. (Fig, 2(c].. graph density (Fig. 4(e) in the appendix) and stretch factor for the cascades (Fig. A(g) in the appendix), with distance from ground truth close to 0 for regimes aligned with the key assumptions we make for our main results (Assumption or,
more generally, [ In addition to superior accuracy, Clock's rumning time scales linearly with the graph size and is orders of magnitude smaller than that of DP for sufficiently large instances (Figs. 2(b) 2
3.5 Generality of FastClock
We have shown that FastClock achieves small expected distortion on the clock recovery problem when the small-scale model as in Definition 0 However, the algorithm works substantially more generally -all that is needed is concentration of the number of vertices infected in each session, given previous session, around its conditional expectation, along with concentration of the frontier size in each session. In particular, the model-dependent parts of the proof of Theorem lic entirely in the proof of Theorem 4 and the associated auxiliary lemmas.
Below, we formulate sufficient conditions on our model to guarantee these properties. Our discussion culmi-
nates Assumption 2 which is used as the main hypothesis in Theorem
Concentration of the number of vertices infected in each session A sufficient condition for the required concentration property hold is martingale difference property: for any session index t, we may write [Ssess(t) sum of indicators of vertex infection events: letting X(v, t) denote the indicator
13

---

Published in Transactions on Machine Learning Research (11/2022)
that V Ssese(t), we have |Seess (t) X(,,t) We define Z(S t, v) follows: we first order the vertices in F(Ssess: 1) arbitrarily and denote them by u1 (P(S.ea.))) Then we define ((Ssess [[]Sseea(t)) or 1S X ((1,))))
Then (Z t, t.j)] }=
(S)ost))) the Doob martingale with respect to the natural filtration on the vertex j=1
infection events in the frontier up to vertex uj. By the Azuma-Hocffding incquality, the desired concentration property holds whenever
(SSanse t, - Z(S t.j 1- - 1) ((),
(6)
for all 4,4, with probability 1, where the O() is uniform in all parameters and 0 < const. 1/2. Intuitively, this means that knowledge of whether not given susceptible vertex becomes infected in session t does not substantially alter our best guess of the total number of vertices infected in that session. This encompasses our IC-based model but is substantially more general, since it allows for, e.g. weak dependence among infection events.
Concentration of the frontier size Concentration the frontier size at each step is assured when G is drawn from any random graph model coming from a sparse graphon (Borgs et al., 2017]] W with density parameter Pn. within the range of p specified by Assumption [ and with all entries bounded away from 0. More preciscly, all that is needed is concentration of the frontier size, conditioned on the latent positions of all nodes. This concentration follows immediately from Chernoff bound.
To make this rigorous, we first explain the sparse graphon framework. This is encapsulated in Definitions 7 and g below.
Definition 7 (Graphon). A graphon is a symmetric, Lebesgue-measurabbe function W 10 [0, Definition (Sparse random graph model associated with a graphon). The sparse random graph model G.W, with sparsily parameter Pn (a function of n whose codomain is [0, (0) associated with the graphon W the following distribution on graphs with vertices 21, n.: first, n numbers X1,..., Xn are sampled uniformly at random from [0, 1]. Conditioned on these, edge erists between vertices i, independently of anyyhhng else with probubilily Pa. ((X,, Xz).
We can now formulate the more general assumptions under which we can prove an accuracy guarantee for FastClock.
Assumption 2 (General assumptions on the random graph model and the small-scale model). We assume that the graph G sampled from a sparse graphon G(W.Pa) where Pn satisfies the same properties that p does in Assumplion 7. Furthermore, we assume that. there exist two constants po.Pr E (0,1) such that Po S (xz,)) S P1 for all x, [0, 1]. We denote po Pn-
We assume that the small-scale cascade model Co satisfies the following conditions:
a) The martingale difference condition described in 6
b) At any timestep and for any vertex in the current frontier, the conditional probability that v becomes infected during timestep t depends only on the set of its active neighbors.
c) There erists a universal constant Co > such that any timestep, the probubility of infection of any frontier verter is bounded below by cu.
Then our generalized accuracy guarantee for FastClock is given in the following theorem. Theorem (PastClock accuracy guarantee, generalized). Suppose that Assumption 2 holds. We have, with probability at least 1 - (((pp.))
ds... =(
We note that Theorem is a consequence of Theorem To show that this the case, it suffices to check
that Assumption 2 follows from Assumption T Since G is sampled from an Frdös- Rényi model with edge
14

---

Published in Transactions on Machine Learning Research (11/2022)
probability p PoPn, it is equivalently sample from sparse graphon model W satisfying W W(z, y) Po for all n E [o. 1,, and with Pn as sparsity parameter. Regarding the assumptions about the small-scale model, assumptions (b) and (c) hold for the 1C model trivially: specifically, the constant co is simply the minimum transmission probability for any edge. Assumption (a), the martingale difference condition, is also checked simply: in the IC model, the terms of the sum E, X(v, () defining /Seesa (1)) are independent, and so it may be checked that [Z(S 1, - ((Seess; L,j - 1)I (X(u,, 2) - (I)(",, (S S 1, where the last step is because X (v3j t) is an indicator function. This martingale difference bound is substantially less than the required one. This completes the proof that Assumption 2 follows from Assumption 1
4 Conclusions and future work
We have formulated a generative model and statistical estimation framework for network spreading processes whose activity periods (which we called seasions) are intermittent. The model is parametrized by a clock, which encodes the large-scale behavior of the process. We showed that this clock can be estimated with high accuracy and low computational cost, subject to certain natural constraints underlying graph and on the small-scale cascade model: in essence, these must be such that the graph is an expander with appropriate parameters; that, conditioned on an estimated current state of the process at any time, the expected number of vertices infected in the next session is immune to small errors in the estimated state; and that the number of vertices infected in the next session is well-concentrated around its conditional expected value. We empirically showed that the Fast.lock algorithm is superior accuracy and running time to the current state of the art dynamic programming algorithm. Furthermore, unlike this baseline, FastClock comes with theoretical accuracy guarantces. Our results hold for broad class of small-scale cascade models, provided that they satisfy certain martingale difference property. Furthermore, the class of random graph models for which our guarantees hold is similarly broad.
the structure of the
We intend to pursue further work on this problem: most pressingly, our empirical results and intuition derived from our theorems indicate that FastClock may not perform accurately when the graph contains very sparse cuts (so that it is not an expander graph, and cannot have been generated by a sparse graphon model with the assumed parameter ranges, except with very small probability). Our empirical evidence is consistent with the conjecture that the degradation of performance on real networks in comparison to the DP algorithm is result of sparse cuts. In such graphs, we envision that FastClock can be used within communities as a subroutinc of a more complicated algorithm. Further work is needed to determine whether accuracy and computational efficiency can be achieved for such graphs. Additionally, our model can be extended to the case where different subsets of nodes behave according to distinct clocks. It is important to clarify the nnormatiiontheorette limits of clock estimation and related hypothesis testing questions in this scenario.
5 Acknowledgements
This research is funded by an academic grant from the National Geospatial-Intelligenn Agency (Award No. # HM00776-0-1-0011, Project Title: Optimizing the Temporal Resolution in Dynamic Graph Mining). Approved for public release, NGA-U--202--02239. The work was also supported in part by the NSF Smart and Connected Communities (SC&C) CMMT grant 1831547 and by NSF CCF grant number #2212327.
References
Emmanuel Abbe, Sanjeev Kulkarni, and Eun Jee Loe. Nonbacktracking bounds on the influence in independent cascade models. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Newral Information Processing Systems, vol- ume 30. Curran Associates, Inc., 2017. URL httpps://proceedingg. wwt.wips..ppppprrr/ee/e. .dd.
Lada A. Adamic, Thomas M. Lento, Eytan Adar, and Pauline C. Ng. Information evolution in social networks. In Proceedings of the Nirth ACM International Conference on Web Search and Data Mining,
15

---

Published in Transactions on Machine Learning Research (11/2022)
WSDM '16, pp. 473 482, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450337168. doi: 10. 111145/283576622335827 URL https::/doi..rrr wttp//...../.... 1145/2835776 2835827
Junaid Ali, Mahmoudreza Babaei, Abhijnan Chakraborty, Baharan Mirzasoleiman, Krishna P. Gummadi, and Adish Singla. On the fairness of time-critical influence maximization social networks, 2019.
Eytan Bakshy, Itamar Rosenn, Cameron Marlow, and Lada Adamic. The role of social networks in infor- mation diffusion. In Proceedings of the 21st international conference on World Wide Web, pp. 519-528, 2012.
Petko Bogdlanov, Michael Busch, Jeff Moehlis, Ambuj K. Singh, and Boleslaw K. Szymanski. The social media genome: Modeling individual topic-specific behavior in social media. 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), pp. 236-242, 2013.
Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Nina Holden. Sparse exchangeable graphs and their limits via graphon processes. J. Mach. Learn. Res., 10:2101-221:77 2017. URL. http://jmlr.org jrgg
Wei Chen, Wei Lu, and Ning Zhang. Time-critical influence maximization in social networks with time- delayed diffusion process. In Proceedings of the Twenty-Sirth Sirth AAAI Conference on Artificial Intelligence, AA pp. 392-598. AAAI Press, 2012a.
Wei Chen, Wei Lu, and Ning Zhang. Time-critical influence maxinization in social networks with time- delayed diffusion process. In Proceedings of the Twenty-Sisth AAAT Conference on Artificial Intelligence, 12 pp. 592 598. AAAI Press, 2012b.
Justin Cheng, Lada Adamic, P. Alex Dow, Jon Michael Kleinberg, and Jure Leskovee. Can cascades be predicted? In Proceedings of the 23rd International Conference on World Wide Web, WWW '14, pp. 925-936, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327442. doi: 00.1445/256488.25677777 2567997. URL https::/doi.org:: /tt../////...11//555556/5660 2567997
Abir De, Isabel Valera, Niloy Ganguly, Sourangshu Bhattacharya, and Manuel Gomez-Rodriquez, Learning and forecasting opinion dynamics social networks. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS'16, pp. 397 405, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Daniel J DiTursi, Gregorios A Katsios, and Petko Bogdanov. Network clocks: Detecting the temporal scale of information diffusion. In 2017 IEEE International Conference on Dala Minsnn (ICDM), pp. 841 846. IEEE, 2017.
Daniel J DiTursi, Carolyn S Kaminski, and Petko Bogdanov. Optimal timelines for network processes. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 1024-1029. IEEE, 2019.
Rashad Elctroby, Yong Zhuang, Kathleen Carley, Osman Yagan, and H. Vincent Poor. The effects of evolutionary adaptations on spreading processes in complex worksrks Proceedings of the National Academy of Sciences, 117:201918529, 03 2020. doi:
Cheng-Der Fuh. SPRT and CUSUM hidden Markov models. The Annals of Statistics, 31(3):942 977, 2003. doi: 1012214/a0/005556222
URL htttps://@o1.org//1 201144//0/10055000
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Dala Mining, KDD '03, pp. 137-146, New York, NY, USA, 2003. Association for Computing Machinery. ISBN URL httpps://dot / 1145/956750.956888
1581137370. doi:
Eun Jee Loe, Sudeep Kamath, Emmanuel Abbe, and Sanjeev R. Kulkarni. Spectral bounds for independent cascade model with sensitive edges. In 2016 Annual Conference on Information Science and Systems (CTSS), pp. 649 653, 2016. doi: /O.S100//ISS..2016.77000
16

---

Published in Transactions on Machine Learning Research (11/2022)
Andrea Montanari and Amin Saberi. The spread of innovations in social networks. Proceedings of the National Academy of Sciences, 107(47):20196- 20201, 2010.
Sang Park, Benjamin Bolker, David Champredon, David Earn, Michael Li, Joshua Weitz, Bryan Grenfell, and Jonathan Dushoff. Reconeiling early-outbreak estimates of the basic reproductive number and its uncertainty: framework and applications to the novel coronavirus (sars-cov-2) outbreak. Journal of The Royal Society Interface, 17:20200144, 07 2020. doi: 10. 10.109//rsif.20200 2020.04..
Jieun Shin, Lian Jian, Kevin Driscoll, and François Bar. The diffusion of misinformation on social media: Temporal pattern, message, and source. Computers Human Behavior, 83:278-285 2018.
Venugopal V. Veeravalli and Taposh Banerjee. Chapter 6 quickest change detection. In Abdelhak M. Zoubir, Mats Viberg, Rama Chellappa, and Sergios Theodoridis (eds.), Academic Press Library in Signal Processing: Volume 3, volume 3 of Academic Press Library in Signal Processing, pp. 209 255. Elsevier, 2.000000000 URL https: / www.sccieneeirrcc...
2014. doi: http:///oo..arr///0000//1/777222
A Glossary of notation
Here we collect the notation that is used the main body of the paper and the proofs in the appendix.
N(S):: Neighborhood of the S of vertices a given graph.
2. Ssess = (Ssess (0). Szess (t),s((),..., (sess - A session-level infection sequence with T + 1 sessions. Each Ssess is subset of vertices, and Ssess (1) n (j) = 0 for + j. We denote by SSeesa the number sessions of Szess: T+ + 1.
3. Sabs (Sots (0), Sars Sobo (N)) The observed infection sequence, generated by our multi- scale cascade model.
The ground-truth clock in our estimation problem.
5. Ò The clock estimated by our algorithm.
5 The estimate of the session-level infection sequence Syess induced by our estimate Ô the clock applied to the observed infection sequence Sobe
7. (S),,, for infection sequence S and timestep index E |S| The a- a-field generated by the event that the first t session-level infection sets of the process are given by Su.... St.
(S(),, for an infoction sequence and timestep index E |S| El|S (t 1) (,)). This the expected number of vertices infected in the + 1st session, given the ression-level infection sequence up and including timestep f.
9. N The index of the last observed infection set. That is, Saasll = N
10. T The index of the last session-level infection set. That is, |Sanal T + 1.
11. n The size of the graph.
12. Pa The probability in the IC model of transmission across an edge in a single timestep.
13. Pe -The probability of infection of vertex in single timestep by a non-network souree.
14. R(S, -For an infection sequence and an index i, define the ith running sum be
R(S, U Sg.
(8)
17

---

Published in Transactions on Machine Learning Research (11/2022)
15. F((S) i) For an infection sequence S and index i E {0, 1, (....,,.11.... [8]}, define the ith frontier set to be
IFSS, 1) -V(.)) R(S,i).
(9)
The ith frontier with respect to is the set of neighbors of vertices infected in session i that have not infected by the end of session
16. i) The candidate frontier set at the end of session in infection sequence S. That is, this is
CF(S,))= = [m] R(S,i).
(10)
Note that F(S, S CF(S
17. (CF(S,S,1,)) The common candidate frontier:
Cc.(s,,,i.,) -F(.
(11)
B
Proofs
In this section, give full proofs of all results.
B.1 Proof of Theorem
To prove the main FastClock approximation theorem, we start by characterizing the growth of p (Seess) and (i)) function of n and i. Note that this is result about the independent cascade process, not the FastClock algorithm.
Lemma 1 (Growth of (u(Sena)) and (Seesa())) We have that, with probabilily at least. 1 Ep for all T,
pa (Sess)))) O((p))+1),
(12)
where the (() uniform in i. Furthermore, with probability least emp, we have
Seeee (1)) =((mp)')
(13)
for every i.
Proof. We prove this by induction on i and use the formula.
4 throughout.
Base case (i = 0): In the base case, non-negative and at most n. By our assumption, we have that pe = of o(p.), ), implying that the first term is o(np). Thus, it remains for us to show that the second sum is ((pp). The dominant contribution comes
to verify that (o(SSess) = (np)) The first term of [4p is
from the second term each term of the sum:
Σ
(Pe + (1 Pc)(1 - (1 - pv,)) deg (o) = 00( Σ
1-
(1 - Pr))
deg )r)d S0e8s (0))))
(14)
(EFo(S
vEFo(Sucao)
Σ
(1 Pm do
(15)
vERo(S....)
In the final expression above, the remaining sum is lower bounded by 0 and upper bounded by ((Fa(S for some constant C < 1, since each term is between 0 and C. Thus, we have shown that, with probability exactly 1,
Ho (S +((Fo((seee)) o(np).
(16)
18

---

Published in Transactions on Machine Learning Research (11/2022)
Since FSeSs)))) is the set of uninfected neighbors of all vertices in (O)s and, by assumption, [Seess (0) (1); we have that with probability at least - e-
(Fo(Se = (np)).
(17)
Thus, we have
Ho(Seeas) = ((pp)
(18)
with probability 2 np, Conditioning on this event (which is only event dealing with the graph struc- ture), we have that Seeee (1)l ~ (inomial(@(rp) Pr). and Chernoff bound gives that with probability e-((pp), [Seess (1) = (np), as desired. This completes the proof of the base case.
Induction (i > 0, and we verify the inductive hypothesis for i): We assume that (s(Ssess) = ((mp))+)) and [ + 1 = ((mp)==1) for j = 0, 0,,,..., 1. We must verify that holds for j = i, with probability at least 1 -- As in the base case, the first term of (4) is ((pe)) & np & (np)*+1, Ii is, therefore, negligible with probability 1. The second term again provides the dominant contribution and is easily seen to be ((IE,( just in the base case. Thus, it remains to show that [F, (F
1----((pp)) (((p)), which implies the desired result for (u The inductive ((mp)*=)) with probability at least e hypothesis implies that [Seess()) (i)) (((p)'), and the number of uninfected vertices is Ej=o Seass (j)l
n - ((mp))++1) Since s T - 1, this is asymptotically equivalent to n.
Now, conditioned on the first i elements of Ssess; the ith frontier (Sees))))) ~ Binomial (1 - (l(()))) 1
(1 - (-p))Smaa((i))) Thus, with probability al least 1 - e -{(())))) we have
[Saaa))))) O(n (1 (1 p) (8)))
(19)
Now,
1 1 (1 - (1-p)]smmn(()) = =1- 11-(1 (1 (p)(p))
(20)
Since p = o(1), we have
1 1 (1 - (xppp) ~ ptt
(21)
Now, using the fact that the fact that p o(n ríI), we have
p I' n' o(n +++++)))
(22)
from our assumption on the growth of p. Thus, in particular,
t o(1)
(23)
This implies that
1-e 1-e-r'thn 11- -1-11== n1"" = n't o(1))
(24)
Thus, with probability at least 1 1- -e-nD(()))))
F; (
(25)
which implies that
(r 0((np)++1).
(26)
By concentration of (Seeso (i)), we then have that with probability at least 1 - e- ((HraS)
SSess (i) = e((np)
(27)
desired.
19

---

Published in Transactions on Machine Learning Research (11/2022)
Completing the proof Let G2 be the event that the inductive hypothesis holds for index i = 0, T..,T --1. Then we have
Pr[N = Pr[Go]
II Pr[G, 0
Gjl
II i=0
(1 - (((()))))
- - -
(28)
This completes the proof.
]
Next, we state and prove utility theorem (Theorem below). To state it, need some notation: estimated clock Ö induces an estimate S of the ground truth session-level infection sequence Saess. In particular, $ is the unique infection sequence such that distorting $ according to Ó yields Sobe as an observed infection sequence.
Theorem (Main FastClock analysis utility theorem). We have that with probability 1 - e- for every S-T-1
SSess (1) n S seess (0) (1 O((p))-1/1).
(29)
We will prove this theorem by induction on i. The inductive hypothesis needed is subtle, as na ive hypothesis is too weak. To formulate it and to prove our result, we need some notation: for an infection sequence W, we define the ith running sum to be
R(W, U W,
W -=
(30)
We define the frontier and running sum discrepancy between two session-level infection sequences S, follows:
AF(S,S,,,) = F.(S) A ( AR(S, S,i,j) = i(S,)) A R(Š,)),
(31)
(32)
where A denotes the symmetric difference between two sets.
We define the condidate frontier at index in infection sequence S to be
CF(S,)) = [n] R(S
(33)
This is the set vertices that are not yet infected after index i.
We define the common condidate frontier to be
=
(34)
With this notation in hand, we define the following inductive hypotheses:
Hypothesis 1. There is small discrepancy between the running sums of the true and estimated clocks:
[| 1) - 12(3, < (n,
(35)
where we set, with foresight, [i i) = M1- Hypothesis 2. There is small discrepancy between Szees (i) and S.:
o1 (Seea)) 2/33
Ssess (1) Syl
f2(
(36)
(Seess())
where we set, with foresight, (2 D p4 (S for some large enough constant. D.
20

---

Published in Transactions on Machine Learning Research (11/2022)
We will use these to prove Theorem The base case and inductive steps are proven in Propositions and below. First, we start by proving an upper bound (Theorem 5 on the following difference:
(Se(S))))) (s(
(37)
In essence, the upper bound says that at any given clock time step, the expected number of nodes infected in the next timestep is almost the same according to both the true and estimated clock. This will later be used to verify the two inductive hypotheses stated above.
Theorem 5 (Upper bound on 37 ). Granted the inductive hypotheses explained above, we have that
(S ss(S))= S p/45-((seee)) )2/5 (4 (c(Sses));
(38)
with probabilily 2 2 2
Proof. To upper bound
37 we apply the triangle inequality to to get
| (Seee))) - p:(5) $ Pe
(F - [S)
(39)
+ Pe
Σ
|5
seess())
(40)
i=0
1=0
Σ
((i,Seeerr
Σ
S(i,
(41)
(S
vEF.(S)
where Q(i, Szess 0) = Pe + (1 p=)(1 (1 pn) (dogssesa(t))
We will upper bound cach of the three terms
39
40
and
41 separately.
Upper bounding (39 by O (SSsess)))
We first note that
|I
[S) s [F S,i,
(42)
So it is enough to upper bound the frontier discrepancy set cardinality. In order to do this, we decompose it as follows:
AF 8, i,,,
+ (AR 3,1,0) (14.)cccc. CCF(S 8,1, (43)
This decomposition holds for the following reason: let be vertex in the frontier discrepancy set S i,) Suppose, further, that v is not in the common candidate frontier for (t),, (so it does not contribute to the second term on the right-hand side of (43) We will show that it must be a member of A AR(SSees:
i), which will complete the proof of the claimed decomposition. Then v must be a member of at least one R(S.eas, i), R(S,i) i) (i.e., it must already be infected in at least one of these). If it were a member of both, then it would not be a member of either froutier, so could not be a member of the frontier discrepancy set. Thus, is only member of one of R(S sess: i) or R(Š,)). i). This implies that A AR(S.ess: i).. This directly implies the claimed decomposition 43
We now compute the expected value of each term of the right- hand side of 43 where the expectation is taken with respect to the graph G. After upper bounding the expectations, standard concentration inequalities will complete our claimed bound on the size the frontier discrepancy set.
In the first term, the size of the intersection of the frontier discrepancy with the running sum discrepancy is simply the number of vertices in the running sum discrepancy set that have least one edge to some vertex in Seess (t) (here we assume, without loss of generality, that |R(Secas: 2)l < (R(S,))) Using linearity of expectation, the expected number of such vertices is
El AF 3,1,8) AR(S 3,i,0) =
(1- (1 - ()(s
(44)
21

---

Published in Transactions on Machine Learning Research (11/2022)
Here (1 (1-(1) (1 () is the probability that, for fixed vertex w AR(Ssese:S, there is at least
one edge between and some vertex in (i).
We compute the expected value of the second term of 43 as follows.
We claim that
AR(S i, CCF(C 3,1,t) C CCF(C sess, 5,i, n (N(AR(S Snsss 3,i,)) \ (((Sees()))
(45)
To show this, let v E AF(Seess: i,) n CCF(S i.) The fact that is in the frontier discrepancy set means that it has an edge to exactly one of Ssess (1), This implies that it has an edge to the running sum discrepancy set. Recalling that we assumed wlog that |R(Ssess, i) S [(S, we must have that AR(S S, i, n (isss() 0, and so we must also have that there are no edges from to (t)ss()). This completes the proof of the claimed set inclusion. This implies that
B| (R i,) (CC)))CCF(Sss.. (, 1, & Bl|cCF(Ssess, 5,ú, n (N(AR(WARSS.) sesss, 3,1,0) \ (N (1))
(46)
As above, the expectation is taken with respect to the random graph G.
For a single vertex in the common candidate fronticr, the probability that it lies in the fronticr discrepancy set is thus most
- (1 - (1-(1p)) 3.400) (1 p))
(47)
Thus, using linearity of expectation, the expected size of the second term in 43 is upper bounded by
SF 3,i,i) n CCF 3,i, of (Seeae))
(48)
S &ICCF(S sess, S, i,), (1 - (1 1-p))
-1--p)/1(sssss AR(S ) (1 p) (8(1
(49)
Combining 44 and 49h and defining q = 1 p, have the following expression for the expected size of
the frontier discrepancy set:
E ARSS seas: i,1,
(50)
= A RiSSeess. i,i,i) i)l (1 ((Saaa(8)))
(51)
+ |CCF(S.ess) i) (1 (1- & . (sanalt))
(52)
We would like this to be (S (;((sess))) Note that E[[F; | oz (S(ess)) can be expressed as follows:
E E( (S(SSe)))] = (IAR(S S,1,0)
(53)
+ CCFF(S ( --
(54)
The intuition behind 50 being (( (s((sess))) is as follows: the AR term is exactly the same in 53 However, this term is negligible compared to the common candidate frontier term in both expected
values. The second term, 52 can be asymptotically simplificd as follows: we have
1 q A A(Sen (, 3,1.0] = 1 - (1- (1-p) ()pp)a R(Sana
(55)
1 - (1-p)
(56)
p- JAR(S 3,2,31
(57)
AR( S, i,
= pl Ssena(())
(58)
Sunso (i)
AR(S seaxs 8,i,1)
(1 - g ((Socoo(i)))
(59)
SSess
Here, we have used the following facts:
22

---

Published in Transactions on Machine Learning Research (11/2022)
For the first asymptotic equivalence, we used the fact that p) s,,, o(1). More precisely, we have from the inductive hypothesis that
AR(S = o(u4-1(Sesss) o (n66).
(60)
so we have
pl plAR(Sses: Sess,
o(n ( -7001110000000//771))
(61)
which is polynomially decaying in n.
For the second asymptotic equivalence, we used the fact that plSsess (f) = o(1). More precisely, this comes from the fact that
aes (1) O(p(np))) n(p
(62)
Now, we use the fact that o(n AT))
g = o(n r+. (1+1)=1),
(63)
from assumption on the growth of p. Now, need to show that the exponent is sufficiently negative and bounded away from O.
T (1+1) -T 1. (1+1)+ T+1 We have used the fact that S 1. Now, the constraints that we imposed on imply that = oflog n), so
-T T+1 S
-1
(64)
T+1
T+1
Jogn 2+1 o(1),
(65)
as desired, since the exponent tends -0 as n - 00.
Let us be more precise about what we proved far. We have
|
AR
EIJAF(S (Sans, , 8,1,0) (Senn)))) ~ (1 (( ICCF 3,1,0)
CCF
SSess (i)
(66)
Meanwhile,
AR
(S [S:(See))]] (1 ((Suaol11)) |CCF1
1+
(67)
|CFF
We have that
B[ARF os (Secss) E| (S
JAR pe3
|A
Seeas (9)
See.e [T]
(68)
AR
cC.
This can be simplified follows:
|| | (S.ess)) E|F, (Secoe))
AR CC.
+
[R [S
(Sneaa (+))
|AR
(1+
|CC.F [3]
q Senaa (1))
[3]
(69)
AR
CCF
+ AR
CCF
This can be upper bounded as follows, by distributing in the numerator and upper bounding | by AR |CCF in the numerator of the resulting first term:
AR (1
18 (sccsa())
ICCF
AR | (Sa)ea
$
(70)
|CCFF
AR
Seess (1)((CCCFF + |AR)
23

---

Published in Transactions on Machine Learning Research (11/2022)
We can further upper bound by noticing that |CCFF| + |AR| 2 |CCFF1 so
E F ( (Senn))
11+ Al
(71)
| og (S(Sees))
Sesss
Now, by our inductive hypothesis, we know that |AR]; = 0(115 1 )0.00) and by concentration, we know that (t)es(() = (Spss1(Seess). Thus, we have
E| E F1 0i]
Øi]
AR
S1+
-1+ + o144 1(ss- O(1)
(72)
Seesa (i)
Thus,
BIJAF(S seess, S,1,0) (r(Ssess) O (S(asss))
(73)
Now, remember that our goal is to show that AF 3, i, = ((EE(()))))) with high probability, conditioned on (SSess)) This follows from the expectation bound above and the fact that the size of the frontier in both clocks is binomially distributed, so that standard concentration bounds apply. This results in the following:
Pe AF, (pP.
(74)
with conditional probability at least - -(((p))))
Upper bounding (40) by (ppol[(Ssess, i)))=
To upper bound 440, we note that
Ssess (i)l = [[(Seess i)bb Σ
(75)
j=0
and an analogous identity holds with S place of Ssess Moreover,
[[SSeeer i) - R(S,)) = [AR(S S,2,0)
(76)
Thus, we have
40 = Pe AR(S.essi 3,1, S pefi (n,
(77)
where the inequality is by the inductive hypothesis. We want this to be o(p. R(S i))), which means that want IAR(S S, i, i) o([R(S i))). This follows from the inductive hypothesis, In particular, know that RR(Sess seas. 1)l > (Sccs(()) since (1) R(S i). Furthermore, have by the inductive hypothesis that |RR(S SSeess S, i,) = o(pt=1(Ssess) 0..66) S([Seeea (t) Thus, have
Pe AR(SSesss: 3,,,)) o(pe R(SeReSSSs i)[),
(78)
with (conditional) probability 1, as desired.
Upper bounding 41 by EVER((S....) Q(i, Seess: v)pp (Saass (i)): To upper bound (41 we apply the triangle inequality and extend both sums to in (: UF; This results in the following upper bound:
41 K
Σ
Q(i, S Seas, v) Q(i,
(79)
(SB.
To proceed, we will upper bound the number of nonzero terms in 79 Each nonzero term can be upper bounded by 1, since Q(i, Ssess, v), Qi,, Š, v) are both probabilities. We will show that the number of nonzero terms is most (SFF.(SSs.........
(Seess)) pppppppppppppppp 11-11 (Saess (i)) with high probability.
2/3
24

---

Published in Transactions on Machine Learning Research (11/2022)
We write
Qii, S Sunss r) (i,,
(80)
= Pe + (1 - pp - (1 -
(I-Pn) Pn) (ededddssellii (())eesscnn(v())) - De - (1 pe)(1 (1 - Pn degs, (v))
(81)
- -1-P))((1 Pm)) deRs (0) (1 - (nn) ( (0300sss000))())
(82)
Thus, a term in the sum 79 is nonzero if and only if (1.) (v) o degs, (v). This happens if and only if o has at least one edge to some vertex in S,eSsese(() (i). Thus, our task reduces to figuring out how many vertices there are that connect to some element of sesSs The expected number of such vertices is
(1 (
(83)
This is an upper bound on the contribution of 41 We thus have
(Fess))))) (S) (1 -1 (1.AAS.m((0)))
41
(84)
Next, we show that 39 In particular,
= ( To do this, we apply the results from upper bounding
(S UR:(()) (F: n (F) + (S 5,i,
(85)
S (5 + (S
(S Scrss ((F()))
(86)
Next, we show that 1 ( pp- 2/3 (Seess We can write
(1.,48mmm (1 (1.1pp))Ssssaaa (SAASten( (1)
(87)
provided that p. S.sSs (i)l o(1). Now from the inductive hypothesis, 18,45 (i)) O(IS sess (1)12/3).
and from Lemma 1 we know that [Seess (i)) O(rp)'). Then we have that
q (iaAaaaa (i) < - e ((p(pp))
(88)
In order for this second term to be 1 o(1), it is sufficient to have that
pl = o(1).
(89)
This happens if and only if
p²+1 = =(( + p o(n TH.).
(90)
This is guaranteed by our assumption that p o(n T+z Thus,
ql (: (1) < 01p(mp)2188
pp (Ss)s
2/3
(91)
We have shown that Next, we show that EvEr.(S...)) Qi,, Ssexu, w) = (2FFF We have
41
(See(() 2/3
(S (i)).
(92)
Q Seess, u) 2 - (1 - Pr.) degs (o)
(93)
Since the sum is over u E F, (S(ess))) this implies that degs degs,..s( (1) (v) 2 1. So
Qii,Seess v) 2 1 (1 pm) P. = 0(1).
(94)
25

---

Published in Transactions on Machine Learning Research (11/2022)
Thus,
Σ
Seess 1) 2 (Fi(Ssea)) Pn (
(95)
(S
Thus, we have shown that
41
const
Σ
Q(i, (1 11-11.45s000000) = const
Q(i, Ssese, r)pp ( (Sees))
(96)
(S
(E
with conditional probability at least - ----(((xx))),
Completing the proof We combine 966
74
and 78 to complete the proof.
So we have that the difference between (4 Sess) and (5( negligible in relation to (S Now, the next two propositions give the base case and inductive step of the proof of Theorem 4
Proposition (Base case of the proof of Theorem We have that, with probability 1, | S, 0)) O, and |5.4So] 0.
Proof. This follows directly from the assumed initial conditions.
Proposition 2 (Inductive step of the proof of Theorem Assume that the inductive hypotheses 35 and 36 hold for i. Then we have the following:
AS (i 1)1 S IAR +o(1) AR(S S,i,i) + o(1) (S )2/3) (See(S (97)
Equivalently,
18t+1 0 St (Ssees) 1 Saese
(98)
Furthermore,
|AR+1l S |ARd < 1( o(Hi(Sseae)
(99)
In other words, both inductive hypotheses Hypothesis and Hypothesis are salisfied for + 1. This holds with probability at least 1 - (((p((S)e))))
Proof. To prove this, we first need a few essential inequalities.
By definition of the algorithm,
S S (((((1
(100)
with probability 1.
We will also need to prove an upper bound on |St+1| - SSeess + 1)}. In particular, we will show that with probability least e (Q(a,(()e..))
|4all < SSeees (i+ + 1)) (1+ ((pi(Seea))
(101)
We show this as follows. From Theorem
mx($) (S )1 + (Se
26

---

Published in Transactions on Machine Learning Research (11/2022)
with probability - --Mla((Sraa)) This implies, via 1100 that
18++1| (e(Ssess) (1 (S )²/3) (1 ((u((Seess
By concentration of [Sseso + 1)1, with probability at least --M(ii(Saan)) this is upper bounded as follows:
S441 $ Seeee (i (++ (1(ee((((((
)) + pp4-1 ) ((pe(Seess) 111)).
Now, we can see from 63 that this is equal to the desired upper bound. We have thus shown 101
Now, with the preliminary inequalities proven, we proceed prove the proposition. We split into two cases:
Ssesa (i + 1) begins before S (in other words, |R(Ssese: a) < |R(S,)) i)D.
In this case, will show (i) that Seca 1) must end before Si+1 (i.c., that | i 1) S |R(S, + 1)1) with high probability, (īi) that
AR (Spe(S
(102)
and (iii) that
1541 (i+ / + o(1) = (S(es(Seess) (0))
(103)
To show that (i) is true, we note that because Syess 1) begins before S/+1, Sunss + 1) consists of an initial segment (ota + 1). (jz) with total cardinality |ARil, ending in a session endpoint (specifically, the one corresponding to R(Š,1)), followed by a segment Sobs (J2 + I), (ja) of total cardinality sS 1)1 - |AR again ending in session endpoint. This is true by definition of AR, The second segment begins at the same point as S (that is, R(S, i)
U Sobs(i)), and we know that it has cardinality
(S + 1)] - | S [S + 1)) S (1(Seee)) + (s(Ssese) 1/24constt
S (1()(11+ - (u(() 1133)
(104)
by concentration of [Ssess (i+ The last inequality follows from the fact that ) = (S)) Thus, the second segment of Ssesa (i + 1) must be contained in S by (100), by definition of the FastClock algorithm, as desired.
This has the following implication: we can express
AR as
AR = 13:+1l - (ISeeas + 1)1 (R,)) S (S + |ARg).
(105)
We have used 101 Since, by the inductive hypothesis, we have AR; 1o14i1((S.n) ) 0.66) ((ur(Sansa) (66,, and since (S + co, this implies that
| = ((u4(Seess))
(106)
Thus, we have established (ii). We next show (iii). We have
1 + 1)1 |AR + AR
(107)
and by the proof of (ii) we upper bound |R to get
S ( 1) 2 AR, + o(1) ol1, ((ces())
(108)
This completes the proof of (iii).
27

---

Published in Transactions on Machine Learning Research (11/2022)
Or (t begins after at the same time as S4+1 (in other words, [R(S t) 2 (R(S, In this case, will show (i) that
| = (Steas)))) 66
(109)
and (ii) that
1 (i 1)1 2 + +(1 (SeeeS 66))
(110)
To prove (i), we start by showing the following identity:
1S+11| AR, SSeass 1)1 + AR.-11444
(111)
where
I+1 {-1
Ssess + 1) stops before S441
(112)
otherwise
The identity [11 is consequence of the following derivation, which relies on the definitions of all involved terms.
ARd + ISeae (i 1)1 + |AR441 14+1
SA + sesa 1)1+ + seas Σ
Σ
Sseas
Σ
[sal
li41
k=
i+1
i+1
i+1
S Sees
Σ
Σ A=0
Sees (A:)
- Σ
|5
k=
k=0
k=0
15
Rearranging 111
to solve for | we have that
A = |15141l - AR, - Seees (i + 1)11 S ||5 - Seess (1 1)1l + |R
= =11$t41| - Seess (i + 1) + 1 2233
3 (Ss 1/3) + olu )1/3) = olu (SessS()s )00)
Here, we have used the triangle incquality and the inductive hypothesis Hypothesis I on |AR,). followed by the inequality (101). This completes the proof of (i). Furthermore, this implies, by the same logic as in the previous case
108 that
15.14S (i 1)1 AR, + o(1) = o(Ju(Sseen 60)
(113)
which verifies the inductive hypothesis Hypothesis 2 on 18.414 + 1)1-
The inductive hypotheses Hypotheses and 2 follow directly from the above.
We can now prove the utility theorem, Theorem
Proof of Theorem 4 Let B, denote the bad event that either inductive hypothesis fails to hold at step i. We
will lower bound Pr Pr[ T-1 -B.. By the chain rule, we have
T-1
T-1
f-1
Pr
- B.j = Pr By
Pr[
- B
0
BB,]-
(114)
1=0
j=0
28

---

Published in Transactions on Machine Learning Research (11/2022)
From Proposition
Proposition and Lemma
this is lower bounded by
T-1
T-1 Σ e
II [1 (-(n))"11) = exp Σ log e (1-e-D(p))!!))
D(m))
-1++
exp
i=
1 e (((p))
Now, the event that none of the bad events hold implies the claim, which completes the proof.
With Theorem in hand, we prove the main result, Theorem
Proof of Theorem Let recall the definition of dsa. (C, We have
1 Σ Di
(s,,((C,
(115)
What need is upper bound on this quantity in terms of the term [(n) (mp)-1/3 in Theorem To this end, partition the sum according to vertex membership in clock intervals as follows:
m de)ssm ds
(c, (c.s
Σ Σ
Disc
(1.5)
Σ
Σ
E
Disc,oli..).
(116)
k=liicjEs
k= k= 1iit-
In the first sum, and j are not ordered by C, because they lie in the same set in S. We consider the corresponding set in S. From the theorem, at least (1Cm ((111)()((m))) ((m)) vertex pairs from Sk. are correctly placed together in S. Furthermore, at least
Sa, 1.1-.111 (1-
Σ (1 (())(s)
(117)
pairs of vertices with one vertex in Sk, are correctly placed in different intervals. So the number of correctly gelered/unorderes vertex pairs is at least
Is|
Sk, 2. (1 f(n()))?
IS] Σ
Sk || (1lk:/(11([110 f(r)))² ~ n1 (0) (1-11111 - f(n)))
+
(118)
2
+1
Since f(n) = o11,, this is asymptotically equal to (2) (1-11ff0) (1-2(())).
This completes the proof.
B.2 Proof of Theorem
We analyze the worst-case running time of FastClock as follows: initialization takes O(1) time. The dominant contribution to the running time the while loop. Since tobs is initially and increases by at least in each iteration, the total number of iterations vertex and odge is only processed, constant number of times, in O(1) of these loop iterations, so that the running time is at most. O(N + m), as claimed.
most N. The remaining analysis involves showing that each
In particular, the calculation of μe in every step involves summation over all edges from currently active vertices to their uninfected ncighbors, along with calculation involving the current number of uninfected vertices (which we can keep track of using O(1) calculations per iteration of the loop). A vertex is only active in a single iteration of the loop. Thus, each of these edges only processed once in this step. The calculation of y' entails calculating sum over elements of Sabe that are only processed once in all of the iterations of the loop. The calculation all of the [Sots (t) can be done as preprocessing step via an iteration over all n vertices of G. Finally, the caleulation of F entails union over the same set of elements of Sots in the
29

---

Published in Transactions on Machine Learning Research (11/2022)
caleulation of the maximum, followed by traversal of all edges incident elements of S442 whose other ends connect to uninfected vertices. These operations involve processing the vertices in S.+1 (which happens only in a single iteration of the loop, and, thus, with the preprocessing step of calculating the [)),, only a constant number of times in the entire algorithm). The edges leading to elements of F142 from elements of 1/+1 are Traversed al most twice in the loop: once in the building of Fi41 and once the next ileration in the calculation of pt.
This implics that each vertex and edge is only processed O(1) times in the entire algorithm. This leads to the claimed running time of O(N + + m), which completes the proof.
B.3 Proof of Theorem
3
To generalize the proof of Theorem we need to generalize the following auxiliary results:
1. Concentration of (Seess This follows from the martingale difference property, immediately. Con- ranion is then used in the inductive proof Proposition 2 as well as in Lemma which we generalize to Lemma
2. Lemma on the growth of ps (Sess) and Seeess (i))- This follows simply from the graphon assumption and from concentration of (Seee((i). The resulting generalization is as follows.
Lemma (Growth of (S and (i))) We have that, with probability least 1- e -((pp.), for all i S ST
(Seeee)) = ((((mpopn)(*)))... "((ppp))"""")),0(00))")))))"))"
(119)
where the Q, O are uniform in i. Furthermore, with probability at least e- -2((pp)) we have
S (1) = (((mpppp))))
(120)
for every i.
Proof. The structure of the proof is exactly as in that of Lemma Namely, we prove this by induction on i. The base case follows from the graphon density assumption, along with the assumed lower bound (the assumption ] on the probability of infection of cach frontier vertex to establish the bounds on (SSess))) The bounds on [1ses<(1] then follow from the assumption a) The inductive step follows in exactly the same way.
3. Theorem upper bounding the difference (Sesssss)) 14: (5)
Theorem (Generalized upper bound on (Si(Sanss) (,(5)))- Granted the inductive hypotheses Hypothesis and we have the following upper bound:
(pi(Seess) (5( S PLP 2/3 3/Ssu(S
(121)
with probability 2 1 1 -(px((Sec..))
Proof. The contribution of in the general case is exactly as before, since Pe plays the same role. We thus ignore it in the following analysis. Recalling that (S.ess))) is an expected value, we can decompose it by linearity of expectation as follows:
(s(Sec)))=
Σ
Pr(X(u,t)= (
(122)
(EF(S
We may upper bound un (Seee)) (5( as follows:
(S:(S - (x(5)) 5
Σ
Pr| = a (r(X(e, = ||
()B
(123)
30

---

Published in Transactions on Machine Learning Research (11/2022)
upper bound the sum in (23) by its number of nonzero terms. By Assumption 2 any term in this sum is nonzero only if the vertex has at least one active neighbor in se4S The remainder of the proof, in which we upper bound the number of such vertices, is exactly the same as in the proof of Theorem 5 with the exception that q is replaced by the interval [1 PiPn. PoPa]-
Exactly in the proof of Theorem
With these ingredients, the statement of Proposition remains the same. Its proof changes slightly: we use Theorem 0 in place of Theorem 5 and in place of we use PiPa-
Propositions and Lemma allow us to prove a generalization of the utility theorem Theorem which is as follows.
Theorem (Generalization of the FastClock utility theorem). We have that with probability -Q(app) for every i < T 1,
(isss( n S = (t)e ((pmm)
(124)
Proof. The proof steps are exactly the same, except that we apply the lower bounds given in Lemma rather than Lemma
Finally, Theorem generalizes to Theorem 3 whose proof remains intact, except that we use the generalized version of the utility theorem in place Theorem This concludes the proof Theorem 3
C Examples
Example 3 (Failure to account for multiple time scales affects downstream statistical inference). Here we describe a simple example that demonstrates that failure to account for multiple time scales in a cascade can negalively impact the accuracy of downstream statistical inference. As this is only an enample, we opl for simplicity of analysis and, thus,, leave certain details the reader. These may be filled in by standard concentration arguments.
Specificully, we focus on the problem of cascade doubling time prediction, studied in Cheng et al. (2014). The problem is stated as follows: given cascade observations up to to/including time E R in which m vertices are infected, the lask is to predicl an interval [a, b) such that, with probability at least - 5, for some faed parameter 0, the time of the 2m-th infection event lies in [a,
Consider small-scale cascade model M given by the discretized independent cascade model as detailed in Desinilion 0 on graph G with verlices, with edge transmission parameler pv. 1, probability of infection from ezternal source Pe = 0, and transmission timer distributed according to geometric distribution with success parameter X. Consider a cascade generated by our two-scale model with small-scale model M and clock C = ([0, 1], [k; 2k - 1), [2k, 3k 11, [3k, 4k - -1,,,.), , for some fixed k E N. Assume that G is a complete binary tree and that the infection starts at the rool node. Finally, assume that we have observed the cascade up to and including the midpoint of session j: t = (j + 1/2)k.
We first calculate the typical number of vertices infected up and including time t. The number of vertices infected by the beginning of session j is given by E/= = 24 11, by the geometric sum formula. This holds with probability 1. The reumber of vertices infected by time t is then 2i -1- -.10-220 ---222 , for some specific, computable constant C > O. Thus, easily, the namber of infected vertices approzimately doubles by time t k.
Nert, we consider what our estimate of the doubling time would be if we were to incorrectly assume that the cascade is generated by model M (that is, if we were to ignore the eristence of the larger time scale). To do this, we need to introduce some nolation:
(t) the number of vertices with j uninfected children at the end of timestep t.
Y() the number of uninfected children of infected parents at the end of timestep We call such nodes "open slols".
31

---

Published in Transactions on Machine Learning Research (11/2022)
Z(t) the number of vertices infected in timestep t.
(1) the total number of vertices infected by the end of timestep t.
For any t' > t, we have that Z(t') is approximately X Y(t' 1), and (t')) is exactly Y(t' - 1) + Z(t'), becouse each new infection removes on open stot (the newly infected verlex) and creates two new open slots (the children of the newly infected vertex). Thus, we have that Z(t') Rs A(Y - 2) + Z(t' - 1)), so that
Z(t') R AY -) A(Y - 2) -
(125)
= A(Y(t) + =(t ((+ +... Z(t' - 1))
(126)
=X((()) +)(++))++-.++ 7(1' - 2)) AZ((1' 1)
(127)
= =(1+A)Z(( -1) (1+ Z(t + 1).
(128)
Next, note that (t) can be related to Wt):: since each new infection increases the number of open slots by 1, we must have that (t) = W(t) + 1. So we have 7(t)) (1 +
+ 1). Then
8'
1-4-1
w(C)-W(1)
Σ
Z(i) X(W((++ +1 (1+ -x(W() +
- Σ 1)
-
iH+1
i=++
1=0
= =X((()+)) (1+ (W(1+ +1)
((1 ( 2)
Then, in order for t' to be the doubling time for t, we must have that ((1 X)C-+ 1. It is then easily seen that the required t' is constant with respect to k, that we substontially underestimate the doubling time when k is large. Thus, faulure to accounl for the larger lime scale in this selling leads to subslantial and, in this setting, avoidable inaccuracy.
More realistic empirical experiments in DiTursi et al, (2017; 2019 confirm that accounting for multiple timescales con, in practioul sellings, improvv performance on doubling time prediction and several other downstream statistical tasks.
Example (Infection sequences and clocks). Consider a graph G with n = 10 vertices. A cascade may produce an observed infection sequence Sobe = ({7), (4), (1.3). {5), (2), (8), ft [10), {6, 9}), indicating that verler is infected al. lime 0, 4 al time L = 1, and at time 2, etc. If the cascade was generaled according to our multiscale model with session end points at = 1, 4,8, then this would induce the following session infection sequence: Ssess (f4, 7}, (1,3.5), (2), (6, 6,,,8,9100 10)). The clock that induced this session infection sequence is given by the session end points. As a partition into subintervals, it is encoded by ((0, 1), [2, 3), [4, (5,
Example 5 (Frontier sets of an infection sequence). Consider the graph depicted in Figure where sets of vertices are arranged from left to right according to the exomple infection sequence Seess = ({1), {3. 5). (2, 4).(6)), {6]). The frontier sets corresponding to Saese on this graph are
Fo(Ssess) = (3,4,5, 5, 5)
(129)
(S {2, 4, 7].
(130)
(2 {6, 7}.
(131)
F Fs(Seess) 0.
(132)
D Empirical results on synthetic and real graphs
In this section, we give our complete set of empirical results, continuing the material Section 3.4
Experiments on Erdös Erdös-Rényi graphs. We first experiment with Erdös Rényi to confirm the theoretical behavior of our estimator and compare its running time and quality to the DP baseline. We report the results
32

---

Published in Transactions on Machine Learning Research (11/2022)
The network for the frontier example, Example Distinct shaded regions from left to right denote distinct infection sets from the sequence Ssess in the exammple.
Figure 3:
FastClock
FastCloock
DP
DP
3:5
TeakClock
disaance
101
02
Purkimss (eccands)
02
201
0.1
0.0
1000
3000
5000
10000
0001
0.05 0.1
0.15 02
0:25 5.03
number of nodes
30:00 number of nodes
20090
6.1
0.35
0.25
05
pn
(a)
(c)
(d)
0.8
FastCloock
FastClock
0.5
0.20
Fastslock
Fasttlock
detence
0.3
327
DP
0.
tumbim-e 201
0.05
0.1
0.0
20
0.00
density (olpha)
stretch
donstty talpha)
stretch
(e)
(f)
(h)
Figure 4: Comparison the distance and runtime estimated clocks by FastClock and baseline from DiTursi et al. 2017 on Erdös-Rényi Rényi graphs (default parameters for experiments: p== 0.1, Pe 10-7, n 3000, p = n 1-1/ stretch unless varying the specific experiment). (b). Varying graph size. (c),(d): Varying infection probability Pr. (f). Varying graph donsity p = n 1/aa, (g): Varying stretch.
1/3
in Figure 4
With increasing graph size FastClock's distance from the ground truth clock diminishes (as expected based on Theorem []. while that of DP increases (Fig, [[a]]. Note that DP optimizes a proxy the cascade likelihood and in experiments tend to associate too many early timesteps with early sessions, which for large graph sizes results in incorrect recovery of the ground truth clock. Similarly, FastClock'ss
estimate quality is belter than that of DP for varying Pn. (Fig. [[c]] graph density (Fig. [(e]] and stretch factor for the cascades (Fig. ((g)), with distance from ground truth close to 0 for regimes aligned with the key assumptions we make for our main results (Assumption [ or, more generally, 2 In addition to superior
accuracy, FastClock's running time scales linearly with the graph size and is orders magnitude smaller
than that of DP for sufficiently large instances (Figs. 4(b)
4(h)
Experiments on Stochastic Block Model (SBM) graphs. We would also like understand the behavior of our estimator graphs with communities where the cascade may community boundaries. To this end, we experiment with SBM graphs varying the inter-block connectivity and virality (pa) of the cascades and report results in Fig. 5 As the cross-block connectivity increases and approaches that within blocks (i.e. the graph structure approaches that of an ER graph) FastClock's quality improves and is significantly better than that of DP (Fig. 5(a)). When, however, the transmission probability Pa high, coupled with sparse inter-block connectivity, FastClock's estimation quality deteriorates beyond that of DP (Fig. 5(c).. This behavior is due to the relatively large variance of l4 when the cascade crosses a sparse
33

---

Published in Transactions on Machine Learning Research (11/2022)
0.5
FastClock
0.5
0.4
DP
0.5
6/4
HastClock
0.3
0.1
numine
0.1
tent
0.0
0.0
-0.1
0.01
0.05
0.1
0.15
02
0.01 0.65 0.1
0:15
0.25
0.3
connectivity
0.01
0.55
155
6.2
0.02
0.2
connectivtyy
p0
(a)
(b)
(c)
(d)
baseline from DiTursi of sizes n/ v/ and a/ VR, Ps. 1007, stretch 1 2). (b): Varying inter-block connectivity (p.. = 0.1) where a setting 0.2 makes the graph equivalent to an Erdös Rényi graph with p = 0.2. (c),(d): Varying infection probability Pr. (inter-block connectivity is set to 0.01).
Figure 5: Comparison the distance and runtime
estimated clocks by FastClock
ct 2017) on Stochastic Block Model graphs (default perameters: 5000, two
in the graph with high probability. This challenging scenario opens an important research direction we plan to explore in future work.
D.1 Empirical results on a real graph
Here we evaluate the performance of FastClock and the DP algorithm from DiTursi et al. (2017) via synthetic cascades on a real network. The graph in question, harvested by Bogdanov et al. (013)). is a Twitter subnetwork consisting of 3000 nodes, with edges representing follower-folowwee relationships. The network was constructed by breadth-first search starting from set of seed nodes consisting of the authors of that work and their labmates. We generated cascades on this network with single random initially infected node and varied Pa from 0.01 to 0.15. We plotted the accuracy and rumning time (Figure G of the two algorithms versus Pa: averaged over 50 trials. For all values of Pr: the running time of FastClock is substantially smaller than that of the DP algorithm. Regarding accuracy, for smaller Pn, FastClock's average distance is smaller than or equal to that of DP. The accuracy FastClock decays past approximately Pv. = 0.15 but remains below an average distance of 0.07. We note that these larger values for Pn. may not be practically relevant. E.g., in Kempe et al. (2003), values of ps, between 0.01 and 0.1 (and, in general, varying inversely in proportion to the degrees of nodes) considered relevant.
E Discussion of knowledge of small-scale cascade model parameters
Our algorithm relics knowledge of the parameters of the small-scale cascade model. Here we discuss this aspect further. Our main messages are as follows:
Joint estimation of small-scale model parameters and the clock from a sample cascade is, without any assumptions, information -hteatttiiiteoreiiillllll impossible. This is be expected: the small-scale model parameters determine the local temporal dynamics of the process, and large-scale effects can distort these local dynamics.
This makes the issue subtle and motivates work that is beyond the scope of the present paper.
In many use cases, small-scale model parameters may be estimated from data beyond sample cas- cades. We give an example setting where this is plausible. In other settings, with certain assump- tions, joint estimation from sample cascade is possible. The main message here is that estimation of small-scale model parameters is of interest, but full exploration of practical mothods is beyond the scope of this paper. It. is appropriate and plausible to regard these cascade parameters as being given to us.
3. We show that our algorithm is robust to random model parameter uncertainty.
34

---

Published in Transactions on Machine Learning Research (11/2022)
DP
0.30
0.25
FastClock
0.20
runtimes (seconds)
diaaroa
0.15
10a
0.10
0.05
109
10
-0.05
0.01
0.05
0..1
0.15
0.01
0.05
0.1
0.15
Pn
pn
Figure 50 Synthetic cascades generated on real-world Twitter graph of about 3000 nodes. a and b) distance and runtime over Pn- DP exhibits higher accuracy at higher Ps and FastClock does better at lower Pu. FastClock is much faster than DP, but loses small amount of accuracy.
E.1 Estimation of transmission probabilities from non-cascade data
In situations, cascade model parameters (i.c., transmission probabilitics for individual edges) de- termined by observable pairwise node features and, hence, do not require cascade observations and ground truth clock information for estimation. In other words, in these scenarios, it is plausible and appropriate to think of the cascade model parameters as being already determined and available to us when we observe sample cascades and estimate clocks.
More concretely, nodes & may be endowed with feature vectors fo E Rdd for some dimension d, and the single-timestep transmission probability across an edge (v,w) w) may be stipulated to depend deterninistically on fo and fu. a way to be determined. Le., the transmission probability is stipulated to be of the form Fo)f::w), where Fo(:.)) is a known function depending on a paramoter 0, which This can be estimated in certain settings by experiment: for a sufficiently large number of pairs (v,w) of individuals (not necessarily coming from graph), the experimenter infects vertex and exposes to If the experimenter can reliably determine whether or not becomes infected, then this provides an estimate of the probability of transmission (o.fe fw), and could be used to estimate O.
be estimated.
E.2 Robustness to cascade model parameter uncertainty
We can extend our theoretical guarantees for FastClock to the case where the small-scale cascade model parameters are not known exactly, but where instead each edge transmission probability is an independent sample from a fixed unknown distribution with known expected value and support bounded away from 0 and That is, fix an arbitrary distribution D supported on [A, B), where < S B < 1, with known expected value Pu. We stress that we do not know A B. For cach ordered pair of vertices (u, w) such that {v, w) is edge in the graph, pvo ((v, w)) D.
The FastClock algorithm's guarantees remain the same. This is because the crucial property which it relies is concentration of cach (i)) around its expected value, conditioned on o;-1(S.ess). This conditional expectation is ( in the setting where D assigns probability 1 to some fixed Pa (or all of the pm((e) are deterministic). When D a nontrivial distribution, the analysis slightly more complicated: we must show that (i) remains concentrated around its conditional expected value (call it [Seesa but this number is no longer exactly equal (SSSee))). Under our assumptions on the random graph model, [Seese(i)] (i) is asymptotically close to (S((Ss whenever (S 1)] co. This is the when > 1. Thus, the only
35

---

Published in Transactions on Machine Learning Research (11/2022)
trouble comes when i and the seed set Szess (0) has small cardinality (1(1) with respect to n). In this case, with high probability, every vertex in (o(Ssess) has exactly one neighbor in Ssess (0) (unless the graph is extremely dense). For each vertex e E Fo (S ; let e(v) denote this unique edge from e to Saeso (0). Then [1ee is asymptotically equivalent to (S(See))) provided that
Σ
(1 -1- Pn(e())))
E (1-Pa).
(133)
(E
(EFo(S
This is trivially the case because
= Ps. and because the pe(e())), for different v, are independent.
Thus, algorithm's accuracy and running time guarantees are robust to random uncertainty in model parameters.
F Estimation of Seess (0)
Here describe how (0)) might be estimated under various assumptions.
In some application scenarios, we are free to choose cascade seeds: e.g,, in influence maximization. In this case, the problem is trivial.
Alternatively, if we assume that the seeds are uniformly randomly chosen, then with high probability they form an independent set (if the graph is sparse enough). We can estimate (eess to be S - Sobs()) where k- = max
Užz (oss())is an independent set in G}. This yields the correct result with high probability Pe is small enough (which we assume in our theorems).
Without any assumptions, any algorithm must be given Seess (0), because, e.g., impossible distinguish between a cascade C with T sessions versus sessions of cascade whose seed set is the final state of C.
G Behavior of FastClock under deviations from the modeling assumption
Here we consider deviations from one of the modeling assumptions and their consequences for FastClock. Specifically, consider what happens when, within any given session, small set of vertices that become infected also can immediately begin the process of infecting subset of their neighbors.
To examine this scenario, we consider relaxation of our model, wherein, in each session j, subset of at most kj vertices may be "non-compliant,, in the sense that they become active immediately. Let us call the non-compliant set for session j NC,. In this case, the total number of vertices in the infection trees of these vertices is at most ΣvENc, deg(v), which is, with high probability, at most O(kmp)). Provided that ky & (np),, this does not affect the performance guarantee FastClock.
In an extreme scenario where all vertices are non-compliant, we can modify the FastClock algorithm as follows: starting at the beginning of each session, we keep a running total of the conditional expected number of vertices infected since the start of the session. Simultaneously, we keep a running total of the number of vertices actually infected since the scssion start. At the first time point at which these two numbers differ by more than certain threshold, we declare the previous timestep to be the end of the current session. The threshold is chosen in the same manner in the original Flsc algorithm, to provide certain probability of error guarantec.
H Real network statistics
Table D lists the structural statistics for large online social networks often used in empirical network science research. Such networks are well within the expected density ranges employ in our theoretical analysis, namely their average degree is in the order (and typically higher) than a natural logarithm of the number of nodes.
36

---

Published in Transactions on Machine Learning Research (11/2022)
Name
Description
Type
Nodes
Edges
AVG degree
In(N)
ego- Facebook
Social circles from Facebook (anonymized)
Undirected
4,039
88,234
22
3go-Gplus
Social circles from Google+
Directed
107,614
13,673, 453
127
12
egu- Twitter
Social circles from Twitter
Directed
81,306
1,768, 149 149
22
suc- Epinions1
who-trusts-whon network Epinions.com
Directed
75,879
508,837
soc- LiveJournall
LiveJournal online social network
Directed
4,847,571
68, 28,993,777 773
800- Pokec
Pokec online social network
Directed
1, 1,632,803
30,622,564
19
14
soc- Soc-Slashdot0811
Slashdot social network from November 2008
Directed
77,360
905,468
12
11
Slashdot0922
Slashdot social network from February 2009
Directed
82,168
948,464
12
11
wiki- Vote
Wikipedia who-votes-on whom network
Directed
7,115
103,689
Table 1:
Statistics of some of the real-world social and information network datasets from SNAP
httpp:
// //snap.co stanford.edu/datte
37


Reviews:
[{"review_id": "xsLRzcZ4fO", "reviewer": "Reviewer_9pKo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n(1) Overall the paper is very well written. The theorems are clearly presented and the authors have done an excellent job of providing well-structured and well-explained proofs. \n(2) For settings where the model applies, the proposed algorithm is efficient and effective. \n(3) There is substantial value in the characterization of the statistical accuracy of the estimation. The results are nicely extended to sparse graphon models and relatively flexible within-session cascade models.  \n\nWeaknesses\nI have one significant concern with the paper that would lead me to recommend substantial modifications prior to publication. My main concern is that the session-level model appears to be somewhat contrived. While a model-based approach can have significant advantages in terms of enabling the derivation of principled algorithms and theoretical characterization of performance, it is important to avoid specification of a model that is neither representative of real-world data nor simple enough to provide insights into general network behaviour. I detail this concern below in the requested changes.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies spreading processes on graphs and formulates a model that incorporates multiple temporal scales of cascade behavior. The goal is to allow the models to capture both small time scale cascade behaviour but also intermittent longer time-scale behaviour. The model introduces a “clock” parameter that encodes when sessions of cascade activity start. The sessions are governed by a small-scale cascade model. Parameter estimation for the model leads to the task of clock estimation. \nThe paper makes the following contributions:\n(1) The paper formulates a distortion measure and then proposes an estimation algorithm that has linear complexity with respect to the size of the input. \n(2) Theoretical results are provided to demonstrate that the proposed algorithm is statistically accurate provided reasonable conditions are satisfied by the spreading process and the graph. The initial theoretical results in the paper focus on the special case where the incorporated model is a discretized independent cascade process and the graph is Erdös-Rényi, with constraints on the edge probability and its relationship to the number of sessions. Subsequently, a considerably more general result is provided, with the conditions being extended to sparse graphon models for the graph and to cascade processes that satisfy a martingale difference property.\n(3)  Experimental results (in an appendix) demonstrate that the proposed method outperforms the state-of-the-art competitor which is based on dynamic programming, at least for synthetic settings where the cascade behaviour and graphs adhere to the modelling assumptions.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "(1)\tJustification and utility of the proposed model\nThe presented model corresponds to few models previously presented in the literature and, in this paper, it is not justified or supported by any data where this form of cascade behaviour is observed. If the model is exactly the same as the single clock model in DiTursi et al. (2017), then I would very strongly recommend that the authors acknowledge this in the introduction. Buried in Appendix C is the statement “More realistic empirical experiments in DiTursi et al. (2017; 2019)…”, but the submitted paper does not state explicitly that the models are the same, and I do not think this would be obvious to a reader without a careful reading of DiTursi et al. DiTursi et al. is not even cited in the introduction. The phrasing in the related work regarding the DiTursi et al. paper is cryptic: “the authors formulated a version of the problem of clock recovery from cascade data”. The contribution of this paper is not undermined by acknowledging that the model formulation appeared in an earlier work; in my view it is the formulation of the estimation task and identification of a suitable distortion metric that are the key foundational advances of this work. \n\nThe paper makes attempts to justify and motivate the assumptions, but the arguments are not particularly convincing. Many of the arguments are unsupported by sufficient citation to related literature (e.g., the introduction, which includes a section on “Motivating applications”, cites only two supporting papers, and it is not clear that these provide direct support for a session model).  In particular:\n\n(a)\tSome of the motivating examples involve synchronized activity sessions, but at the same time, these need to be somewhat unpredictable, requiring to be learned from the data. Otherwise, we could simply say that a morning session lasts from 8am until 12pm and forego any estimation. In a real-world setting, it’s challenging to envisage settings where both of these conditions arise. Perhaps the authors can provide a more practical example, going beyond a simple appeal to a social network setting.  \n\n(b)\tThe requirement that a user becomes infected in one session but then only becomes active in the next session also seems very restrictive. The paper argues that this is “justified in scenarios where nodes are not immediately infectious when they become infected”. It’s challenging to see a setting where all infected users would be delayed for just the right amount of time to stay uninfectious for the current session, but then all be ready to infect in the following session. I think a clearer, detailed and concrete example would help me understand the applicability of the model. Data that shows evidence of session-based cascades of this kind would be even more compelling.\n\n(c)\tBeyond providing examples in support of the adopted model, it would be very helpful if there could be some further discussion of the applicability of the proposed model and algorithm if some of the modelling assumptions are not fully met. For example, if a small fraction of users do become infectious immediately, would this lead to the algorithm and model failing completely, or would it introduce small errors. This would provide a better sense of whether the model can be applied in a practical setting even if it is just a reasonable approximation to the observed behaviour.  Appendix E does an excellent job of this for the small-scale model, but a similar type of discussion regarding the large-scale (session) model would be a very welcome addition. \n\n(d)\tIn the appendix, the paper provides examples of networks that display density characteristics similar to those of the graph models used to establish the theoretical results in the paper, but there is no attempt to perform simulations of cascades on those networks. This is an opportunity to explore performance when there is a departure from the assumptions used to derive the theoretical results. While I appreciate that this is a paper that is focused on theoretical developments, and I am not requesting that the authors conduct extensive simulations, this lack of investigation of the proposed cascade model on real-world networks raises further questions in the mind of a reader. Even if the session-based cascade model itself is assumed reasonable, does the approach work reasonably well if the cascade occurs over a real-world network? \n\nMore minor issues:\n\n(2)\tThe abstract claims that “our algorithm substantially outperforms the dynamic programming algorithm in terms of both running time and accuracy” and the paper states that “We empirically showed that the FastClock algorithm is superior in accuracy and running time to the current state of the art dynamic programming algorithm”. Could the authors clarify whether the synthetic data generation process completely matches the modelling assumptions of both approaches? This question could be resolved by a clear statement in the introduction that the core models in the DiTursi et al. (2017) paper and the submitted paper are the same (or different in a clearly explained way).  If the models are different, then does the data generation process unfairly favour the proposed method?\n\n(3)\tIs it possible to avoid referring to (61) in the proof of Lemma 1? Since (61) is inside a different proof, it’s challenging to know what assumptions are in place without careful checking, since they could even be introduced in the proof. It seems that (60) and (61) are simple (and brief), so I think it would be fine to repeat them. \n\n(4)\tThroughout the proof of Theorem 5, there is a running assumption (without loss of generality) that $|R(S,i)|\\leq |R\\tilde{S},i|$. This is \nintroduced in parentheses only during the upper-bounding of (38), but is then used repeatedly later. It would be helpful to introduce this assumption earlier and explain that it will be employed throughout the proof. Related to this, I found the discussion concerning $\\tilde{S}_i – S_i$ after (80) challenging to follow. It wasn’t obvious to me why we couldn’t also consider edges to $S_i - \\tilde{S}_i$ for (80) to be non-zero. This may just be my confusion, and it may be obvious to the authors, but it probably would be beneficial to add a sentence to explain why this is the case. If it is derived as a result of focusing on a specific case (w.l.o.g.), then it should definitely be statement explaining this. \n\nMinor points\nFigures 2 and 3 could be improved significantly by adjusting the width of the bars to improve visibility and make comparison between the two algorithms easier. \nAbove (37): will later be used verify -> will later be used to verify \nThus, it v is only -> Thus, v is only \nAbove (76): This is follows from -> This follows from\n", "broader_impact_concerns": "In my view there are no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3fZ42p1ImK", "reviewer": "Reviewer_Q2i7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Proposed FastClock algorithm run time scales linearly with the number of sessions and the number of edges in the graph when the discretized independent cascade (IC) model is used as the small-scale cascade model.\n- The FastClock algorithm can be used with any small-scale cascade model, not just the discretized IC model, and will be efficient as long as the small-scale model allows expected number of infected nodes to be calculated efficiently.\n- The authors provide sufficient conditions for the small-scale model and random graph model in order for their guarantees to generalize beyond the discretized IC model on an Erdős-Rényi graph.\n- The paper is very well written. The authors have motivated their problem formulation in an intuitive manner and provided very readable summaries of their assumptions and key theoretical results.\n\nWeaknesses:\n- The authors assume that the parameters of the small-scale cascade model are known. The authors specify good reasons why they make this assumption in Appendix E. For example, it may not be possible to both estimate the small-scale model parameters and the clock from a cascade because they interact with each other in the generative model, which then makes it impossible to evaluate the clock estimation error. However, I argue that it could still be possible to evaluate accuracy on some sort of downstream task, such as the cascade doubling time prediction that the authors have mentioned.\n- All empirical results are buried in Appendix D. This is highly disappointing given that the authors claim the empirical results as one of their contributions. This can be fixed without too much effort though--see my requested changes.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of estimating time scales in spreading processes on networks, such as cascades of information diffusion. Such cascades are often modeled at short time scales assuming that nodes are always in a position to infect other nodes. This assumption is unrealistic for many settings, e.g. people checking social media in \"sessions\" while they are not actively at work. The authors instead propose a model parameterized by a *clock* that activates the cascade model and determines which nodes are active and able to infect others.\n\nThe main contributions I observe are as follows:\n- They propose a fast (linear-time) algorithm called FastClock to estimate the clock given the node infection times.\n- They provide approximation guarantees for the FastClock algorithm, showing that the clock estimation error decreases to 0 at a polynomial rate as a function of the average degree of the network.\n- The FastClock algorithm is both faster and more accurate than a prior approach from DiTursi et al. (2017) on simulation experiments. This contribution is unfortunately buried in the appendices currently.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I have only one major change to request: Move some of the empirical results currently in Appendix D into the main paper. For example, Figure 2(a)-(d) would be sufficient to provide the reader with at least some empirical evidence of the claimed improvement in runtime and accuracy compared to DiTursi et al. (2017). The bulk of the empirical results can stay in the appendix. If more room is needed in the main paper, I suggest moving some of Section 3.4 describing the more general theoretical results into the appendices.\n\nMinor issues:\n- Consider switching to a log scale or finding some other way to present the comparison between FastClock and DP in Figure 2. The blue bars for FastClock are not visible in many of the plots.\n- Definition 3: number sessions -> number *of* sessions\n- Definition 6: node v become active -> node v *becomes* active\n", "broader_impact_concerns": "No broader impact statement is present, and I do not think one is necessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EFcBGT6owV", "reviewer": "Reviewer_JRZX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- the proposed model is quite general, and should allow for different cascade process.\n- the proposed algorithm is simple but computationally efficient. Unless I am wrong, it is even somewhat \"online\", never going back on the chosen times, which is the golden standard in this kind of methods. However, it raises the question whether the results could be even more refined by going offline, and sacrificing a little bit of computational efficiency for performance results.\n- the theoretical analysis is useful and non-trivial, with what seems to be a quite general framework\n- the paper is generally clearly written\n\nWeaknesses/questions:\n- Some clarification could be brought about the model itself, maybe with additional remarks and/or examples.\n\nSome parts of the model seem very permissive: eg, disregarding the theoretical analysis, the cascade model can actually be anything (def 1), not restricting the spreading to neighbors of activated nodes ? (maybe this should be written, it is a bit contradictory to what if written just above def 1). On the other hand, some parts of the model seem on the contrary a bit constrained: if I understand correctly, the clock \"ticks\" each time one or more nodes become \"activated\" ? Or, conversely, \\emph{all} newly infected nodes become activated at the next ticking of clock. It feels that some if this could be relaxed: more than three node states could be easily incorporated (since the cascade model is anything), a more general process could be introduced to describe what happens when the clock ticks, etc.\n\nThe IC example is not really helpful to understand the flexibility of the proposed model, as the \"clock\" does not seem to play an important role. In fact, it is a bit unclear how the proposed model can faithfully modelize the example given by the authors of different activity period during the day (fast vs slow), unless the clock if very constrained and almost deterministic, which seems contrary to the basis of the computations in FastClock which lie of the the computation of an expectation. It would be greatly helpful to describe a model like this, and what the computation look like in this case.\n\nMore pictural illustrations of various spreading processes could be very helpful.\n\n- the clock estimation problem seems to bear many ressemblance to multiple change-point detection, where the goal is to identify multiple time points where the distribution of a time series changes, which is not mentioned by the authors. It would be good to comment on the link between the two literatures and their algorithms. Especially, the distinction between online/offline algorithms is crucial in the change-point literature. FastClock may bear ressemblance with existing algorithms for online change-point detection.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce a novel model for spreading processes on graphs, along with a fast algorithm to estimate key parameters of this model. The cornerstone of of their model is the introduction of two timescales, regulated by a \\emph{clock}. Roughly speaking, the clock groups several time steps together, and \"activates\" newly infected nodes during the next group, which in principle allows them to start spreading along the edges of the graph. Given an observed sequence of infected nodes, the goal of the proposed algorithm is to estimate the underlying clock, or, in other words, group time steps together such that each group correspond to new unobserved \"activation\".\n\nOn the theoretical side, they show that their algorithm (FastClock) approaches the true clock under some martingale assumption for the spreading process and semi-sparse graphon model for the graph structure. They give an example, the Independant Cascade (IC) process.\n\nOn the practical side, the authors show that FastClock is more efficient than another dynamic programming approach and exhibit good results on synthetic Erdo-Renyi and SBM graphs and IC process.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- Some notation are slightly poorly chosen, most of all the letter $S$ for both the small-scale (with a hat) and large-scale steps. With only tilde and hat, it is easy to get lost between what is observed, estimated, inferred, ground-truth, at which time-scale, etc.\n\n- the \"frontier\" set is absolutely crucial in the analysis and would deserve a more detailed introduction and description, maybe with an illustration ? Currently, there is also a mistake in it's definition (index $j$ not used), and the notation changes in later pages, $\\mathbb{F}_t$ vs $\\mathbb{F}(\\cdot, t)$\n\n- a suggestion, I think it would be clearer (and avoid repetition of proof) to first state and prove the main theorem 3, then apply it to the IC process by describing how the hypotheses are satisfied in this case (if they are?).", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all share the view that the paper makes a worthy technical contribution through the introduction of a new model, an algorithm for 'clock estimation' of cascade processes and its analysis. The reviewers also note that their initial comments have been adequately addressed by the authors, and feel that the paper is worthy of publication in its current state, hence my decision.
Decision: Accept (poster)