  Information diffusion models typically assume a discrete timeline in which an
information token spreads in the network. Since users in real-world networks
vary significantly in their intensity and periods of activity, our objective in
this work is to answer: How to determine a temporal scale that best agrees with
the observed information propagation within a network? A key limitation of
existing approaches is that they aggregate the timeline into fixed-size
windows, which may not fit all network nodes' activity periods. We propose the
notion of a heterogeneous network clock: a mapping of events to discrete
timestamps that best explains their occurrence according to a given cascade
propagation model. We focus on the widely-adopted independent cascade (IC)
model and formalize the optimal clock as the one that maximizes the likelihood
of all observed cascades. The single optimal clock (OC) problem can be solved
exactly in polynomial time. However, we prove that learning multiple optimal
clocks(kOC), corresponding to temporal patterns of groups of network nodes, is
NP-hard. We propose scalable solutions that run in almost linear time in the
total number of cascade activations and discuss approximation guarantees for
each variant. Our algorithms and their detected clocks enable improved cascade
size classification (up to 8 percent F1 lift) and improved missing cascade data
inference (0.15 better recall). We also demonstrate that the network clocks
exhibit consistency within the type of content diffusing in the network and are
robust with respect to the propagation probability parameters of the IC model.
