Dynamic Bayesian Ontology Languages

Many formalisms combining ontology languages with uncertainty, usually in the form of probabilities, have been studied over the years. Most of these formalisms, however, assume that the probabilistic structure of the knowledge remains static over time. We present a general approach for extending ontology languages to handle time-evolving uncertainty represented by a dynamic Bayesian network. We show how reasoning in the original language and dynamic Bayesian inferences can be exploited for effective reasoning in our framework.

Introduction
Description Logics (DLs) (Baader et al. 2007) are a wellknown family of knowledge representation formalisms that have been successfully employed for encoding the knowledge of many application domains. In DLs, knowledge is represented through a finite set of axioms, usually called an ontology or knowledge base. In essence, these axioms are atomic pieces of knowledge that provide explicit information of the domain. When mixed together in an ontology, these axioms may imply some additional knowledge that is not explicitly encoded. Reasoning is the act of making this implicit knowledge explicit through an entailment relation.
Some of the largest and best-maintained DL ontologies represent knowledge from the bio-medical domains. For instance, the NCBO Bioportal 1 contains 420 ontologies of various sizes. In the bio-medical fields it is very common to have only uncertain knowledge. The certainty that an expert has on an atomic piece of knowledge may have arisen from a statistical test, or from possibly imprecise measurements, for example. It thus becomes relevant to extend DLs to represent and reason with uncertainty.
The need for probabilistic extensions of DLs has been observed for over two decades already. To cover it, many different formalisms have been introduced (Jaeger 1994; Lukasiewicz and Straccia 2008;Lutz and Schröder 2010;Klinov and Parsia 2011). The differences in these logics range from the underlying classical DL used, to the semantics, to the assumptions made on the probabilistic component. One of the main issues that these logics need to handle is the representation of joint probabilities, in particular when the different axioms are not required to be probabilistically independent. A recent approach solves this issue by dividing the ontology into contexts, which intuitively represent axioms that must appear together. The probabilistic knowledge is expressed through a Bayesian network that encodes the joint probability distribution of these contexts. Although originally developed as an extension of the DL EL (Ceylan and Peñaloza 2014b), the framework has been extended to arbitrary ontology languages with a monotone entailment relation (Ceylan and Peñaloza 2014a).
One common feature of the probabilistic extensions of DLs existing in the literature is that they consider the probability distribution to be static. For many applications, this assumption does not hold: the probability of a person to have gray hair increases as time passes, as does the probability of a computer component to fail. To the best of our knowledge, there is so far no extension of DLs that can handle evolving probabilities effectively.
In this paper, we describe a general approach for extending ontology languages to handle evolving probabilities. By extension, our method covers all DLs, but is not limited to them. The main idea is to adapt the formalism from (Ceylan and Peñaloza 2014a) to use dynamic Bayesian networks (DBNs) (Murphy 2002) as the underlying uncertainty structure to compactly encode evolving probability distributions.
Given an arbitrary ontology language L, we define its dynamic Bayesian extension DBL. We show that reasoning in DBL can be seamlessly divided into the probabilistic computation over the DBN, and the logical component with its underlying entailment relation. In order to reduce the number of entailment checks, we compile a so-called context formula, which encodes all contexts in which a given consequence holds.
Related to our work are relational BNs (Jaeger 1997) and their extensions. In contrast to relational BNs, we provide a tight coupling between the logical formalism and the DBN, which allows us to describe evolving probabilities while keeping the intuitive representations of each individual component. Additionally, restricting the logical formalism to specific ontology languages provides an opportunity for finding effective reasoning algorithms.

Bayesian Ontology Languages
To remain as general as possible, we do not fix a specific logic, but consider an arbitrary ontology language L consisting of two infinite sets A and C of axioms and consequences, respectively, and a class O ⊆ ℘ fin (A) of finite sets of axioms, called ontologies, such that if O ∈ O, then O ∈ O for all O ⊆ O. The language L is associated to a class I of interpretations and an entailment relation |= ⊆ I×(A∪C). An interpretation I ∈ I is a model of the ontology  (Baader et al. 2007) is an ontology language of this kind; consequences in these languages are e.g. concept unsatisfiability, concept subsumption, or query entailment. However, many other ontology languages of varying expressivity and complexity properties exist. For the rest of this paper, L is an arbitrary but fixed ontology language, with axioms A, ontologies O, consequences C, and interpretations I.
As an example language we use the DL EL (Baader et al. 2005), which we briefly introduce here. Given two disjoint sets N C and N R , EL concepts are built by the grammar rule C ::= A | | C C | ∃r.C where A ∈ N C and r ∈ N R . EL axioms and consequences are expressions of the form C D, where C and D are concepts. An interpretation is a pair (∆ I , · I ) where ∆ I is a non-empty set and · I maps every A ∈ N C to A I ⊆ ∆ I and every r ∈ N R to r I ⊆ ∆ I × ∆ I . This function is extended to concepts by I := ∆ I , (C D) I := C I ∩ D I , and (∃r.C) I := {d | ∃e ∈ C I .(d, e) ∈ r I }. This interpretation entails the axiom (or consequence) C D iff C I ⊆ D I .
The Bayesian ontology language BL extends L by associating each axiom in an ontology with a context, which intuitively describes the situation in which the axiom is required to hold. The knowledge of which context applies is uncertain, and expressed through a Bayesian network (Ceylan and Peñaloza 2014a).
Briefly, a Bayesian network (Darwiche 2009) is a pair B = (G, Φ), where G = (V, E) is a finite directed acyclic graph (DAG) whose nodes represent Boolean random variables, and Φ contains, for every x ∈ V , a conditional probability distribution P B (x | π(x)) of x given its parents π(x). Every variable x ∈ V is conditionally independent of its non-descendants given its parents. Thus, the BN B defines a unique joint probability distribution (JPD) over V : Let V be a finite set of variables. A V -context is a consistent set of literals over V . A V -axiom is an expression of the form α : κ where α ∈ A is an axiom and κ is a We briefly illustrate these notions over the language BEL, an extension of the DL EL, in the following Example.  Figure 1.
This KB represents a computer failure scenario, where x stands for a critical situation, y represents the memory failing, and z the CPU failing.
The contextual semantics is defined by extending interpretations to evaluate also the variables from V . A V -interpretation is a pair I = (I, V I ) where I ∈ I and V I is a propositional interpretation over the variables V .
It is a model of the V -ontology O iff it is a model of all the V -axioms in O. It entails c ∈ C if I |= c. The intuition behind this semantics is that an axiom is evaluated to true by all models provided it is in the right context.
Given a V -ontology O, every propositional interpretation, or world, W on V defines an ontology Intuitively, a contextual ontology is a compact representation of exponentially many ontologies from L; one for each world W. The uncertainty in BL is expressed by the BN B, which is interpreted using multiple world semantics. Definition 2 (probabilistic interpretation). A probabilistic interpretation is a pair P = (I, P I ), where I is a set of V -interpretations and P I is a probability distribution over I such that P I (I) > 0 only for finitely many interpretations The probabilistic interpretation P is a model of the KB (B, O) iff it is a model of O and consistent with B.
The fundamental reasoning task in BL, probabilistic entailment, consists in finding the probability of observing a consequence c; that is, the probability of being at a context where c holds. Definition 3 (probabilistic entailment). Let c ∈ C, and K a BL KB. The probability of c w.r.t. the probabilistic interpretation P = (I, P I ) is P P (c) := (I,W)∈I,I|=c P I (I, W).
It has been shown that to compute the conditional probability of a consequence c, it suffices to test, for each world W, whether O W entails c (Ceylan and Peñaloza 2014b).
This means that reasoning in BL can be reduced to exponentially many entailment tests in the classical language L. For some logics, this exponential enumeration of worlds can be avoided (Ceylan and Peñaloza 2014c). However, this depends on the properties of the ontological language and its entailment relation, and cannot be guaranteed for arbitrary languages.
Another relevant problem is to compute the probability of a consequence given some partial information about the context. Given a context κ, the con- For simplicity, in the rest of this paper we consider only unconditional consequences. However, it should be noted that all results can be transferred to the conditional case. Example 5. Consider again the KB K 1 = (B 1 , O 1 ) from Example 1 and the consequence Comp FailComp. We are interested in finding the probability of the computer to fail, i.e. P K1 (Comp FailComp). This can be computed by enumerating all worlds W for which O W |= Comp FailComp, which yields the probability 0.238. As seen, it is possible to extend any ontological language to allow for probabilistic reasoning based on a Bayesian network. We now further extend this formalism to be able to cope with controlled updates of the probabilities over time.

Dynamic Bayesian Ontology Languages
With BL, one is able to represent and reason about the uncertainty of the current context, and the consequences that follow from it. In that setting, the joint probability distribution of the contexts, expressed by the BN, is known and fixed. In some applications, see especially (Sadilek and Kautz 2010) this probability distribution may change over time. For example, as the components of a computer age, their probability of failing increases. The new probability depends on how likely it was for the component to fail previously, and the ageing factors to which it is exposed. We now extend BL to    Figure 2. The set of nodes of the graph can be thought of as containing two disjoint copies of the random variables in V . Then, the probability distribution at time t + 1 depends on the distribution at time t. In the following we will use V t and x t for x ∈ V , to denote the variables in V at time t.
As standard in BNs, the graph structure of a TBN encodes the conditional dependencies among the nodes: every node is independent of all its non-descendants given its parents. Thus, for a TBN B, the conditional probability distribution at time t + 1 given time t is We further assume the Markov property: the probability of the future state is independent from the past, given the present state.
In addition to the TBN, a DBN contains a BN B 1 that encodes the JPD of V at the beginning of the evolution. Thus, the DBN D = (B 1 , B → ) defines, for every t ≥ 1, the unique probability distribution Intuitively, the distribution at time t is defined by unraveling the DBN starting from B 1 , using the two-slice structure of B → until t copies of V have been created. This produces a new BN B 1:t encoding the distribution over time of the different variables. Figure 3 depicts the unraveling to t = 3 of the DBN (B 1 , B → ) where B 1 and B → are the networks depicted in Figures 1 and 2, respectively. The conditional probability tables of each node given its parents (not depicted) are those of B 1 for the nodes in V 1 , and of B → for nodes in V 2 ∪ V 3 . Notice that B 1:t has t copies of each random variable in V . For a given t ≥ 1, we call B t the BN obtained from the unraveling B 1:t of the DBN to time t, and eliminating all variables not in V t . In particular, we have that P Bt (V ) = P B1:t (V t ).
The dynamic Bayesian ontology language DBL is very similar to BL, except that the probability distribution of the contexts evolves accordingly to a DBN.
In a nutshell, a DBN can be thought of as a compact representation of an infinite sequence of BNs B 1 , B 2 , . . . over V . Following this idea, a DBL KB expresses an infinite sequence of BL KBs, where the ontological component remains unchanged, and only the probability distribution of the contexts evolves over time. A timed probabilistic interpretation P simply interprets each of these BL KBs, at the corresponding point in time. To be a model of a DBL KB, P must then be a model of all the associated BL KBs.
Before describing the reasoning tasks for DBL and methods for solving them, we show how the computation of all the contexts that entail a consequence can be reduced to the enumeration of the worlds satisfying a propositional formula.

Compiling Contextual Knowledge
From Proposition 4, we see that reasoning in BL can be reduced to checking, for every world W, whether O W |= c. This reduces probabilistic reasoning to a sequence of standard entailment tests over the original language L. However, each of these entailments might be very expensive. For example, in the very expressive DL SHOIQ, deciding an entailment is already NEXPTIME-hard (Tobies 2000). Rather than repeating this reasoning step for every world, it makes sense to try to identify the relevant worlds a priori. We do this through the computation of a context formula.
Definition 8 (context formula). Let O be a V -ontology, and c ∈ C. A context formula for c w.r.t. O is a propositional formula φ such that for every interpretation W of the variables in V , it holds that O W |= c iff W |= p φ.
The idea behind this formula is that, for finding whether O W |= c, it suffices to check whether the valuation W satisfies φ. This test requires only linear time on the length of the context formula. The context formula can be seen as a generalization of the pinpointing formula (Baader and Peñaloza 2010b) and the boundary (Baader et al. 2012), defined originally for classical ontology languages. Example 9. Consider again the V -ontology O 1 from Example 1. The formula φ 1 := (x ∧ (y ∨ z)) ∨ (¬x ∧ y ∧ z) is a context formula for Comp FailComp w.r.t. O 1 . In fact, the valuation {x, ¬y, z} satisfies this formula.
Clearly, computing the context formula must be at least as hard as deciding an entailment in L: if we label every axiom in a classical L-ontology O with the same propositional variable x, then the boundary formula of c w.r.t. this {x}-ontology is x iff O |= c. On the other hand, the algorithm used for deciding the entailment relation can usually be modified to compute the context formula. Using arguments similar to those developed for axiom pinpointing (Baader and Peñaloza 2010a;Kalyanpur et al. 2007), it can be shown that for most description logics, computing the context formula is not harder, in terms of computational complexity, than standard reasoning. In particular this holds for any arbitrary ontology language whose entailment relation is EXPTIME-hard. This formula can also be compiled into a more efficient data structure like binary decision diagrams (Lee 1959). Intuitively, this means that we can compute this formula using the same amount of resources needed for only one entailment test, and then use it for verifying whether the sub-ontology defined by a world entails the consequence in an efficient way.

Reasoning in DBL
Rather than merely computing the probability of currently observing a consequence, we are interested in computing the probability of a consequence to follow after some fixed number of time steps t. Definition 10 (probabilistic entailment with time). Let K = (D, O) be a DBL KB and c ∈ C. Given a timed interpretation P and t ≥ 1, the probability of c at time t w.r.t.
We show that probabilistic entailment over a fixed time bound can be reduced to probabilistic entailment defined for BOLs by unravelling the DBN. Lemma 11. Let K = (D, O) be a DBL KB, c ∈ C, and t ≥ 1. Then the probability of c at time t w.r.t. K is given by Proof. (Sketch) A timed model P of K is a sequence of probabilistic interpretations P 1 , P 2 , . . ., where each P i is a model of the BL KB K i := (B i , O). We use this fact to show that where (1) follows from Definition 10, (2) holds by definition, and (3) follows from Proposition 4.
Lemma 11 provides a method for computing the probability of an entailment at a fixed time t. One can first generate the BN B t , and then compute the probability w.r.t. B t of all the worlds that entail c. Moreover, using a context formula we can compile away the ontology and reduce reasoning to standard inferences in BNs, only.
Theorem 12. Let K = (D, O) be a DBL KB, c ∈ C, φ a context formula for c w.r.t. O, and t ≥ 1. Then the probability of c at time t w.r.t. K is given by P K (c[t]) = P Bt (φ).
Proof. By Lemma 11 and the definition of a context formula, we have which proves the result.
This means that one can first compute a context formula for c and then do probabilistic inferences over the DBN to detect the probability of satisfying φ at time t. For this, we can exploit any existing DBN inference method. One option is to do variable elimination over the t-step unraveled DBN B 1:t , to compute B t . Assuming that t is fixed, it suffices to make 2 |V | inferences (one for each world) over B t and the same number of propositional entailment tests over the context formula. If entailment in L is already exponential, then computing the probability of c at time t is as hard as deciding entailments.
The previous argument only works assuming a fixed time point t. Since it depends heavily on computing B t (e.g., via variable elimination), it does not scale well as t increases. Other methods have been proposed for exploiting the recursive structure of the DBN. For instance, one can use the algorithm described in (Vlasselaer et al. 2014) that provides linear scalability over time. The main idea is to compile the structure into an arithmetic circuit (Darwiche 2009) and use forward and backward message passing (Murphy 2002).
While computing the probability of a consequence at a fixed point in time t is a relevant task, it is usually more important to know whether the consequence can be observed within a given time limit. In our computer example, we would be interested in finding the probability of the system failing within, say, the following twenty steps.
Abusing of the notation, we use the expression ∼ c, c ∈ C, to denote that the consequence c does not hold; i.e., I |= ∼ c iff I |= c. Thus, for example, P K (∼ c[t]) is the probability of c not holding at time t. To find the probability of observing c in the first t time steps, one can alternatively compute the probability of not observing c in any of those steps. Formally, for a timed interpretation P and t ∈ N, we define Definition 13 (time bounded probabilistic entailment). The probability of observing c in at most t steps w.r.t. the DBL KB K is P K (c[1 : t]) := inf P|=K P P (c[1 : t]).
Just as before, given a constant t ≥ 1, it is possible to compute P K (c[1 : t]) by looking at the t-step unraveling of D. More precisely, to compute P P (∼ c[1], . . . , ∼ c[t]), it suffices to look at all the valuations W of t i=1 V i such that for all i, 1 ≤ i ≤ t, it holds that O W(i) |= ∼ c. These valuations correspond to an evolution of the system where the consequence c is not observed in the first t steps. The probability of these valuations w.r.t. B 1:t then yields the probability of not observing this consequence. We thus get the following result. Theorem 14. Let K = (D, O) be a DBL KB, c ∈ C, φ a context formula for c w.r.t. O, and t ≥ 1. Then P K (c[1 : t]) = W|∃i.W(i)|=pφ P B1:t (W).
This means that the probability of observing a consequence within a fixed time-bound t can be computed by simply computing the context formula and then performing probabilistic a posteriori computations over the unraveled BN. In our running example, the probability of observing a computer failure in the next 20 steps is simply Thus, the computational complexity of reasoning is not affected by introducing the dynamic evolution of the BN, as long as the time bound is constant. Notice, however, that the number of possible valuations grows exponentially on the time bound t. Thus, for large intervals, this approach becomes unfeasible. By extending the time limit indefinitely, we can also find the probability of eventually observing the consequence c (e.g., the probability of the system ever failing). The probability of eventually observing c w.r.t. K is given by is monotonic on t and bounded by 1; hence P K (c[∞]) is well defined.
Observe that Theorem 14 cannot be used to compute the probability of eventually observing c since one cannot necessarily predict the changes in probabilities of finding worlds that entail the consequence c. Rather than considering these increasingly large BNs separately, we can exploit methods developed for probability distributions that evolve over time. This will also allow us to extract more information from DBL KBs.
It is easy to see that every TBN defines a timehomogeneous Markov chain over a finite state space. More precisely, if B is a TBN over V , then M B is the Markov chain, where every valuation W of the variables in V is a state and the transition probability distribution given the current state W is described by the BN obtained from adding W as evidence to the first slice of B. For example, the TBN B → from Figure 2 yields the conditional probability distribution given that {x, y, z} was observed at time t depicted in Figure 4. From this, we can derive the probability of observing {x, y, z} at time t + 1 given that it was observed at time t, which is P ({x, y, z} t+1 | {x, y, z} t ) = 0.252.
We extend the notions from Markov chains to TBNs in the obvious way. In particular, the TBN B is irreducible if for every two worlds V, W, the probability of eventually reaching W given V is greater than 0. It is aperiodic if for every world W there is an n W such that for all n ≥ n W , it holds that P (W n | W) > 0. A distribution P W over the worlds is stationary if W P (V | W)P W (W) = P W (V) holds for every world V. It follows immediately that if B is irreducible and aperiodic, then it has a unique stationary distribution (Harris 1956).
Given a TBN B over V , let now ∆ B be the set of all stationary distributions over the worlds of V . For a world W, define δ B (W) := min P ∈∆ B P (W) to be the smallest probability assigned by any stationary distribution of B to W. If δ B (W) > 0, then we know that, regardless of the initial distribution, in the limit we will always be able to observe the world W with a constant positive probability. In particular, this means that the probability of eventually observing W equals 1. Notice moreover that this results is independent of the initial distribution used.
We can take this idea one step forward, and consider sets of worlds. For a propositional formula φ, let In other words, δ B (φ) expresses the minimum probability of satisfying φ in any stationary distribution of B. From the arguments above, we obtain the following theorem. Theorem 15. Let K = (D, O) be a DBL KB over V with D = (B 1 , B → ), c ∈ C, and φ a context formula for c w.r.t. O. If δ B→ (φ) > 0, then P K (c[∞]) = 1.
In particular, if B → is irreducible and aperiodic, ∆ B contains only one stationary distribution, which simplifies the computation of the function δ. Unfortunately, such a simple characterization of P K (c[∞]) cannot be given when δ B→ (φ) = 0. In fact, in this case the result may depend strongly on the initial distribution. Example 16. Let V = {x}, O 2 = { A B : {x} }, and consider the TBN B → over V defined by P (x | x) = 1 and P (x | ¬x) = 0. It is easy to see that any distribution over the valuations of V is stationary. For every initial distribution So far, our reasoning services have focused on predicting the outcome at future time steps, given the current knowledge of the system. Based on our model of evolving probabilities, the distribution at any time t + 1 depends only on time t, if it is known. However, for many applications it makes sense to consider evidence that is observed throughout several time steps. For instance, in our computer failure scenario, the DBN B → ensures that, if at some point a critical situation is observed (x is true), then the probability of observing a memory or CPU failure in the next step is higher. That is, the evolution of the probability distribution is affected by the observed value of the variable x.
Suppose that we have observed over the first t time steps that no critical situation has occurred, and we want to know the probability of a computer failure. Formally, let E be a consistent set of literals over t i=1 V i . We want to compute the probability P K (c[t] | E) of observing c at time t given the evidence E. This is just a special case of bounded probabilistic entailment, where the worlds are not only restricted w.r.t. the context formula but also w.r.t. the evidence E.
The efficiency of this approach depends strongly on the time bound t, but also on the structure of the TBN B → . Recall that the complexity of reasoning in a BN depends on the tree-width of its underlying DAG (Pan et al. 1998). The unraveling of B → produces a new DAG whose tree-width might increase with each unraveling step, thus impacting the reasoning methods negatively.

Conclusions
We have introduced a general approach for extending ontology languages to handle time-evolving probabilities with the help of a DBN. Our framework can be instantiated to any language with a monotonic entailment relation including, but not limited to, all the members of the description logic family of knowledge representation formalisms.
Our approach extends on ideas originally introduced for static probabilistic reasoning. The essence of the method is to divide an ontology into different contexts, which are identified by a consistent set of propositional variables from a previously chosen finite set of variables V . The probabilistic knowledge is expressed through a probability distribution over the valuations of V which is encoded by a DBN.
Interestingly, our formalism allows for reasoning methods that exploit the properties of both, the ontological, and the probabilistic components. From the ontological point of view, we can use suplemental reasoning to produce a context formula that encodes all the possible worlds from which a wanted consequence can be derived. We can then use standard DBN methods to compute the probability of satisfying this formula.
This work represents first steps towards the development of a formalism combining well-known ontology languages with time-evolving probabilities. First of all, we have introduced only the most fundamental reasoning tasks. It is possible to think of many other problems like finding the most plausible explanation for an observed event, or computing the expected time until a consequence is derived, among many others.
Finally, the current methods developed for handling DBNs, although effective, are not adequate for our problems. To find out the probability of satisfying the context formula φ, we need compute the probability of each of the valuations that satisfy φ at different points in time. Even using methods that exploit the structure of the DBN directly, the information of the context formula is not considered. Additionally, with the most efficient methods to-date, it is unclear how to handle the evidence over time effectively. Dealing with these, and other related problems, will be the main focus of our future work.


extfieldsofstudy:
Computer Science
Physics
Mathematics

text:
Multiscale Event Detection in Social Media

Event detection has been one of the most important research topics in social media analysis. Most of the traditional approaches detect events based on fixed temporal and spatial resolutions, while in reality events of different scales usually occur simultaneously, namely, they span different intervals in time and space. In this paper, we propose a novel approach towards multiscale event detection using social media data, which takes into account different temporal and spatial scales of events in the data. Specifically, we explore the properties of the wavelet transform, which is a well-developed multiscale transform in signal processing, to enable automatic handling of the interaction between temporal and spatial scales. We then propose a novel algorithm to compute a data similarity graph at appropriate scales and detect events of different scales simultaneously by a single graph-based clustering process. Furthermore, we present spatiotemporal statistical analysis of the noisy information present in the data stream, which allows us to define a novel term-filtering procedure for the proposed event detection algorithm and helps us study its behavior using simulated noisy data. Experimental results on both synthetically generated data and real world data collected from Twitter demonstrate the meaningfulness and effectiveness of the proposed approach. Our framework further extends to numerous application domains that involve multiscale and multiresolution data analysis.

Introduction
The last decade has seen rapid development of online social networks and social media platforms, which leads to an explosion of user-generated data posted on the Internet. The huge amount of such data enables the study of many research problems, and event detection is certainly one of the most popular and important topics in this novel research area. Social media platforms present several advantages for event detection. First, due to the real-time nature of online social services, the public awareness of real world happenings could be raised in a much quicker fashion than with the traditional media. Second, due to the large amount of users posting content online, more complete pictures of the real world events with descriptions from different angles are offered with fast and large-scale coverage. These advantages have attracted a significant amount of interest from the data mining communities in event detection problems. For instance, the MediaEval Workshop has open research task dedicated to event detection (Reuter et al, 2013), and numerous event detection approaches have been proposed recently in the literature (Sayyadi et al, 2009;Becker et al, 2009;Aggarwal and Subbian, 2012).
Events in social media platforms can be loosely defined as real world happenings that occur within similar time periods and geographical locations, and that have been mentioned by the online users in the forms of images, videos or texts. Different types of events are usually of different temporal and spatial scales or resolutions 1 , meaning that they span different intervals in time and space. For example, discussions about the London 2012 Summer Olympic Games would span a temporal period of nearly one month and a spatial area of all over the world, while those regarding the 2012 concert of The Stone Roses in the Phoenix Park in Dublin may concentrate only on the date and at the location of the concert. Similarly, Fig. 1 illustrates discussions on Twitter about two events of different spatiotemporal scales in New York City. In the designs of event detection algorithms, it is thus important to take into account the different temporal and spatial scales of various kinds of events. This is challenging in the sense that: (i) Event detection approaches usually rely on classification or clustering algorithms with fixed temporal and spatial resolutions; This results in the detected events being of similar scales; (ii) It is not yet clear how multiple resolutions in time and in space interact with each other so that they can be analyzed simultaneously, even if it is relatively easier to take into account multiple resolutions in only one of these two dimensions; (iii) Data streams from social media platforms usually contain much noisy information irrelevant to the events of interest. It is thus important to understand how to attenuate the influence of the noise on detecting events of different scales. Efficient and robust multiscale event detection for solving the above challenges is exactly the objective of the present paper.
In this paper, we first introduce a baseline approach that detects events that are of similar scales and localized in both time and space, which serves as a first step towards the understanding of multiscale event detection. We then propose a novel approach towards the detection of events that are of different scales and localized either in time or in space but not necessarily in both simultaneously. To this end, we study the relationship between scales in the two dimensions and explore the properties of the wavelet transform to automatically and explicitly handle the interaction between different scales in time and space simultaneously. We propose an algorithm to compute a data similarity graph at appropriate scales, based on which we perform a graphbased clustering process to detect events of different spatiotemporal scales. Furthermore, we present spatiotemporal analysis of the distribution of noisy information in data streams, especially using notions from spatial statistics, which allows us to define a novel term-filtering procedure for the proposed multiscale event detection algorithm, and helps us study the behavior of the two approaches in this paper using simulated noisy data.
We compare the proposed multiscale event detection approach with the baseline approach on both synthetically generated data and real world data collected from Twitter. We show experimentally that the proposed approach can effectively detect events of different temporal and spatial scales. On the one hand, we believe that the modeling of the relationship and interaction between temporal and spatial scales and the detection of multiscale events provide new insights into the task of event detection with social media data. On the other hand, the proposed framework can be further generalized to other application domains that involve multiscale or multiresolution data analysis.

Spatiotemporal detection of events
In this paper, we define an "event" in social media as follows.
Definition. Events in social media are real world happenings that are reflected by data that are concentrated either in both time and space, or in at least one of the two dimensions.
Events defined as above are usually of different temporal and spatial scales, namely, they span different intervals in time and space. In addition, there exist data that do not contain any information about ongoing events. In the case of Twitter, such examples can be tweets that are like: "At work", or "It feels great to be home...". When non-informative tweets constitute a large part of the input data, the event-relevant tweets could however be buried in noise. It becomes very difficult in this case to identify the information of interest. In this paper, we focus on the Twitter data streams and consider the following objective.
Objective. Consider a Twitter data stream that contains temporal, spatial and text information. Our goal is to design event detection approaches that (i) are able to identify events that appear at multiple spatiotemporal scales, namely, events that affect or take place in different temporal and spatial intervals, and (ii) are robust against the ambiguous and noisy information present in the data.
In this paper, we cast event detection as a graph-based clustering problem, where the vertices of the graph represent the tweets, and the edges reflect their similarities. The goal is to group similar tweets into the same cluster such that they correspond to a real world event. The clustering algorithm utilizes a similarity measure between tweets that takes into account the temporal, spatial, and textual features of a tweet. Intuitively, two tweets that are generated by users that are participating in the same event should share a number of common terms and be closely located in time and/or space. In this paper, we compare two different ways of measuring similarity between tweets, the first a baseline approach based on spatiotemporal constraints and the second a novel wavelet-based scheme. Then, in order to effectively handle the noisy information, we study the spatiotemporal distribution of the noise in the Twitter data, especially using a homogeneous Poisson process as a statistical model in our analysis. This is helpful to analyze the behavior of the baseline and the proposed event detection algorithms.

Local event detection via spatiotemporal constraints
Events defined as in the previous section can have different localization behavior in time and space. When the events are localized in both dimensions, event detection can be effectively implemented by imposing spatiotemporal constraints on the data. In this section, we first describe a baseline approach for detecting events that are localized both in time and space, which serves as a first step towards the understanding of multiscale event detection presented later. We formulate a clustering problem, where we wish to group together the tweets that correspond to the same real world event. The similarity measure between different tweets is thus important. In our baseline event detection approach, we measure the similarity between every pair of tweets t i and t j as: where t(t i , t j ) and d(t i , t j ) are the temporal difference in minutes and the spatial distance in meters, respectively, between t i and t j . The thresholds T t and T d enforce the locality of the events and impose strict spatiotemporal constraints. Under such constraints, two tweets t i and t j that have a reasonably high text similarity tend to refer to the same event in real world. The function s tf-idf (t i , t j ) represents the text similarity of t i and t j in terms of the cosine angle between the vector representations of the two tweets using the term frequency-inverse document frequency (tf-idf ) weighting scheme (Manning et al, 2008). Given S 1 (t i , t j ) as the pairwise similarity between tweets, we can create an undirected and weighted graph with adjacency matrix W 1 : where the vertices represent tweets and the edges (along with the associated weights) are defined by S 1 (t i , t j ). By partitioning the vertices of the graph into disjoint clusters, each cluster is then expected to contain tweets that are likely to correspond to the same event. Furthermore, due to the constraints introduced in Eq. (1), these events are localized in both time and space. In this paper, we perform graph-based clustering using the Louvain method (Blondel et al, 2008). This is a greedy optimization method that first find small communities in a local way by maximizing the modularity function (Newman, 2006), before repeating the same procedure by considering the communities found in the previous step as vertices in a new graph, until a maximum of modularity is attained 2 . The Louvain method is suitable for our purpose of event detection because of the following advantages: (i) Unlike most of the clustering methods, it does not require prior knowledge about the number of clusters; This is important because we usually do not know the number of events a priori. (ii) Unlike the popular approach based on normalized graph cut (such as spectral clustering (von Luxburg, 2007)), it does not necessarily favor a balanced clustering; This enables the detection of small-scale clusters together with some relatively larger ones. (iii) It is also computationally very efficient when applied to large scale networks. Specifically, the complexity of the greedy implementation in Blondel et al (2008) is empirically observed to be close to O(n log n) where n is the number of the vertices in the graph.
The graph-based clustering approach described above outputs a set of clusters that correspond to events localized in both time and space. This can be illustrated by Fig. 2(a), where each cluster corresponds to a particular timespace "cube". After clustering, we apply simple post-processing steps to identify those clusters that are likely to correspond to meaningful events in real world. For example, we consider that a meaningful event should be observed by a sufficient number of users with sufficient information reflected on Twitter. Therefore, we consider a cluster as a local event if and only if the number of tweets and distinct Twitter users within the cluster are above certain thresholds (see Sect. 7 for the implementation details of these post-processing steps). The algorithm for local event detection is summarized in Algorithm 1.
Obviously, the choices for the values of thresholds T t and T d in Eq. (1) are critical in LED. Without prior information we may choose them such that they correspond to the expected temporal and spatial spans of events to be discovered. By setting T t and T d appropriately, the algorithm would then be efficient at detecting events that are of similar scales and that are sufficiently concentrated in both time and space. For events of different scales, however, setting the thresholds too low might break down some event clusters while setting them too high would generally lead to a higher amount of noisy information in other clusters 3 (as we will see in the experimental sections). In this case, one needs to implement more complex detection schemes to identify events that appear at multiple spatiotemporal scales. Hence, we introduce in the next section our novel wavelet-based method for multiscale event detection.

Algorithm 1 Local Event Detection via Locality Constraints (LED)
1: Input: T : a set of tweets with temporal, spatial, and text information Tt: temporal threshold T d : spatial threshold 2: Compute the pairwise similarities S 1 (t i , t j ) between tweets in T using Eq. (1), and the adjacency matrix W 1 using Eq. (2). 3: Apply the non-recursive Louvain method to W 1 , and retain the meaningful clusters {c i } m i=1 after post-processing steps. 4: Output: {c i } m i=1 : clusters that correspond to events that are localized in both time and space.

Multiscale event detection using wavelets
In this section, we propose a novel algorithm for multiscale event detection. Specifically, we first introduce a new model of the relationship and interaction between the temporal and spatial scales. We then propose a wavelet-based scheme for computing the pairwise multiscale similarities between tweets.

Relationship model between temporal and spatial scales
The fundamental question in designing approaches towards multiscale event detection resides in properly handling events that are of different scales and do not have simultaneous temporal and spatial localization. An illustration is shown in Fig. 2(b), where three events are represented by rectangular cuboids that span different time and space intervals. Two of them are only concentrated in one dimension but spread in the other one. In such cases, we need to compute a similarity score S 2 (t i , t j ) between pairs of tweets t i and t j that carefully considers the temporal and spatial scales of different events. We shall relax the strict constraints in both temporal and spatial dimensions as defined in Eq. (1), so that S 2 (t i , t j ) is computed at appropriate scales that actually correspond to the span of the underlying events. To this end, we propose in this paper to model the relationship and interaction between the temporal and spatial scales as follows.
Scale relationship model. When two tweets t i and t j share common terms and are close in space, we could tolerate a coarser temporal resolution in computing S 2 (t i , t j ). Vice versa, when they are close in time, we could tolerate a coarser spatial resolution.
Our scale relationship model essentially says that, for two tweets t i and t j to be considered similar, they should be similar at a fine resolution in at least one of the temporal or spatial dimensions, but not necessarily in both simutaneousy. It thus represents a tradeoff between time and space in the detection of events of different spatiotemporal scales. This matches the observation that real world events often happen within a small geographical area but could span longer time intervals (such as a protest at a certain location in a city), or they take place only within short time intervals but could spread a larger geographical area (such as a brief power outage across different areas of a city). Therefore, based on the proposed model, we can relax the strict constraints defined in Eq.
(1) in event detection. In order to do so, however, we do not compare two tweets t i and t j with large temporal or spatial distances by simply choosing higher thresholds T t and T d , since this would suffer from text ambiguity generally present in the Twitter data stream (the same word having different meanings depending on context). We do not either incorporate directly the exact temporal and spatial distances between them into the computation of the similarity metric S 2 (t i , t j ), since this might lead to domination of one scale to the other. These limitations motivate us to propose a more detailed analysis model, that is, instead of considering the temporal and spatial information of each tweet as a whole, we now analyze spatiotemporal patterns of the terms (or keywords) contained in each tweet. More specifically, to compare two tweets t i and t j , we propose to look at the similarity between the time series of the number of occurrences of the common terms shared by them (the occurrence is evaluated in terms of in how many tweets these terms appear). On the one hand, this enables us to study the interaction between the temporal and spatial scales when computing the similarity between keyword time series. On the other hand, this does not affect the clustering-based event detection framework, as similarities between tweets would eventually be computed based on similarities between time series of the common terms shared by them.
We build the time series of keywords as follows. We start with initial temporal resolution ∆t and spatial resolution ∆d. Next, for each term shared by t i and t j , we compute using the temporal resolution ∆t two time series of its number of occurrences, that are based on data corresponding to the two geographical cells to which t i and t j belong. These geographical cells are defined by discretizing the geographical area using the spatial resolution ∆d. The keyword time series are illustrated in Fig. 3.

Wavelet-based similarity computation
We now propose to use a wavelet-based method to measure similarities between time series of keywords. Similarity between time series are often measured by the correlation of their coefficients under the wavelet transform (Daubechies, 1992), which is a well-developed tool in signal processing that leads to a multiresolution representation of the signals. In this paper, we consider the discrete wavelet transform (DWT) using the Haar wavelet, since it provides a natural way to handle different temporal scales as required in our approach. Specifically, due to the properties of the Haar wavelet, the approximation coefficients of DWT at different levels naturally correspond to aggregating the time series from fine scales (starting with the initial temporal resolution) into coarse scales, each time by a factor of two. Therefore, to evaluate the similarity of the time series at a certain temporal scale, we only need to measure the correlation between a specific set of the DWT coefficients at the corresponding level (see Fig. 4 for an illustration).
Our key idea is then to evaluate the similarity between the two time series shown in Fig. 3 at a properly chosen temporal scale, which is in turn determined by the spatial distance between the two geographical cells. More specifically, we introduce a number of predefined spatial scales for the spatial distance. Then, if the spatial scale is coarse, which means that t i and t j are distant, then we require the time series to be compared at a finer temporal scale (the finest temporal scale being the initial temporal resolution); Alternatively, if the spatial scale is fine, which means that t i and t j are close, then the time series could be compared at a coarser temporal scale. Given the number of spatial scales specified by the parameter n scale , we define n scale distance ranges using logarithmical equispacing between the minimum and maximum distances between two distinct geographical cells (measured based on the center of the cells), which correspond to these spatial scales 4 . According to the scale relationship model, the temporal scale S t is then selected inversely according to the spatial scale: For instance, if we choose to have n scale = 4 spatial scales S s ∈ {1, 2, 3, 4}, 1 being the coarsest and 4 the finest, then we would have S t = 4, 3, 2, 1, respectively, that represent from the finest to the coarsest temporal scale. This in turn means that we compute the DWT at levels from 1 to 4, respectively. This procedure is illustrated in Fig. 4. We can now define a new similarity metric between two tweets t i and t j as follows: where s tf-idf (t i , t j ) is the text similarity of t i and t j defined as in Eq. (1). For each term shared by t i and t j , we can compute a similarity of the corresponding time series; s st (t i , t j ) is then defined as the maximum such similarity among all the terms shared by t i and t j . The reasons why we choose the maximum similarity are as follows. First, social media platforms that are ideal for event detection usually contain short textual data where two pieces of text, if corresponding to the same event, would share only a few but informative common terms, such as hashtags in Twitter or tags in Youtube or Flickr. Second, in Twitter specifically, although many tweets may share the same popular term, it is less often that there would be a high similarity between the two keyword time series in terms of their spatiotemporal patterns, especially at fine temporal scales, after a term-filtering procedure which we propose in the next section that removes the "noisy" terms that generally spread in time and space. We thus consider high similarity between time series as a strong indicator that t i and t j may be related to the same event. Taking the maximum instead of the average similarity helps us preserve such information and promote a higher recall metric (retrieval of positive links between tweets) that we favor. In Eq. (4), we consider the overall similarity between two tweets as a product of their text similarity (s tf-idf (t i , t j )) and the similarity of spatiotemporal patterns of the terms shared by them (s st (t i , t j )). This leads to an interesting comparison between LED and MED: Both approaches only consider the text similarity s tf-idf (t i , t j ) that is meaningful in event detection; However, while the former relies on fixed temporal and spatial constraints on t i and t j , the latter looks at similar spatiotemporal patterns of the common terms, thus offers more flexibility for events of different scales. Finally, we can use our new similarity metric to construct an undirected and weighted graph W 2 : Based on this similarity graph, we can again apply the Louvain method to detect event clusters. The complete algorithm for the proposed multiscale event detection approach is summarized in Algorithm 2.
Algorithm 2 Multiscale Event Detection using Wavelets (MED) 1: Input: T : a set of tweets with temporal, spatial, and text information ∆t: initial temporal resolution ∆d: initial spatial resolution n scale : number of spatial scales 2: For every pair of tweets t i and t j in T , extract the common terms {w i } k i=1 . 3: For each w i , compute using ∆t the time series of its number of occurrences, that are based on data corresponding to the two geographical cells (defined using ∆d) to which t i and t j belong. 4: Determine using Eq. (3) the temporal scale St using the spatial scale Ss to which the distance between the two geographical cells corresponds. 5: Apply DWT to the two time series, and compute the similarity between them as the correlation between a specific set of DWT coefficients at the level corresponding to Ss. 6: Compute sst(t i , t j ) as the maximum time series similarity among (4), and the adjacency matrix W 2 using Eq. (5). 7: Apply the non-recursive Louvain method to W 2 , and retain the meaningful clusters {c i } m i=1 after post-processing steps. 8: Output: : clusters that correspond to events of different temporal and spatial scales.
There are a number of parameters in our multiscale event detection approach. First, the initial resolution parameters ∆t and ∆d are used for constructing keyword time series; Compared to T t and T d in LED, they do not have to adapt to the "true" scales of various events, thanks to the scale relationship model and the scale adjustment afterwards using the wavelet-based scheme. In practice, we can simply choose them to be relatively small, for example, as the expected minimum temporal and spatial intervals a desired event may span (specific example choices are presented in Sect. 7). Second, the number of spatial scales n scale can be considered as a choice in the design of the algorithm. Intuitively, an n scale too small would not take full advantage of the spatiotemporal scale relationship model, while n scale being too large might lead to unnecessary increase in computational cost. The choice of this parameter is also influenced by the resolution parameters ∆t and ∆d. One the one hand, ∆d determines the number of geographical cells l d along one dimension hence the spatial variability in the data. This implicitly controls the maximum n scale such that the resulting distance scales are meaningful. On the other hand, given a certain time span of data, the temporal resolution ∆t would determine the length of keyword time series l t , which in turn determines the maximum (meaningful) level of DWT computation using a Haar wavelet and hence the maximum temporal scale. Because of the relationship in Eq. (3), the maximum spatial scale is thus determined accordingly. Based on these two observations, we therefore suggest considering min(log 2 l d , log 2 l t ) as an upper bound for n scale , where · denotes the ceiling of a number. In our experiments, we choose n scale = 4 to ensure a certain level of spatial variability while respecting this upper bound.

Spatiotemporal analysis of noise in Twitter
One challenge in designing event detection algorithms for Twitter data is that we often need to deal with a large amount of "noise" tweets that do not provide any information regarding real world events. Examples can be tweets such as "Could really use a drink" or "Nachos for lunch", or discussions between Twitter users about personal matters. We consider these tweets as noise and event detection algorithms should be able to discard them and not allow them to influence the event detection result. In the literature, several works (such as Sakaki et al (2010)) have employed keyword filtering techniques in order to tackle this problem and derived a working set of tweets that contain information relevant to the types of events they wish to detect. Since we do not focus in this paper on specific event types, but rather on events that take place in specific locations and time intervals, we analyze in this section the spatiotemporal structure of the noise, namely, the event-irrelevant tweets in the data. This analysis will allow us to define a novel term-filtering procedure, and to evaluate empirically the performance of the event detection algorithms in this paper using simulated noisy data under different space-time parameters.

Spatial distribution of noise in Twitter data
In order to get an intuition about the relevant spatial statistics models that can be useful for analyzing the spatial distribution of the noise, we focus on a set of geo-located tweets collected from a specific day (22-01-2012) in New York City. In this dataset, four of the top-ten frequent terms are: nyc contained in 335 tweets (183 of which are located in middle and lower Manhattan), love contained in 674 tweets (145 of which are located in middle and lower Manhattan), lol contained in 1080 tweets (110 of which are located in middle and lower Manhattan), and night contained in 355 tweets (97 of which are located in middle and lower Manhattan). These terms, albeit being among the most frequent ones in the daily collection of tweets, do not appear to be relevant to a specific event of interest. In Fig. 5 we illustrate the locations of the tweets (in middle and lower Manhattan) that contain these frequent terms. One can observe that the tweets have a slight, but not strong spatial concentration and appear to be almost randomly distributed within the Manhattan area. Based on these spatial plots we seek the appropriate spatial statistics tools to model these distributions.
In the spatial statistics literature (Cressie and Wikle, 2011), the lack of spatial structure is commonly assessed using the concept of Complete Spatial Randomness (CSR). CSR considers that the points on a map (locations of tweets in our context) follow a homogeneous Poisson point process. This implies that the numbers of tweets in non-overlapping areas in the map are independent and follow a Poisson distribution with some intensity parameter λ.
More precisely, if we denote the number of tweets within an area A as N (A), CSR asserts that N (A) follows a Poisson distribution with mean λ · V (A), where V (A) denotes the size of the area A. Intuitively, the CSR property asserts that points are "randomly" scattered in an area and are not concentrated in specific locations. We consider the task of assessing the levels of noise in Twitter data (with respect to the target event detection task) by testing the CSR property for tweets that contain common terms 5 . In particular, we initially select a term (say the most frequent term in a collection of tweets) and then we test whether the locations of the tweets that contain this term have the CSR property. In case a term has the CSR property (i.e., the locations of the tweets that contain this term follow a Poisson point process distribution), the edges in the twitter similarity graph that are based on these terms can be considered as noise and may result in the identification of clusters that are not related to events of interest.
5 The direct usage of the CSR tests for the whole input tweet stream would not be particularly informative since both of our algorithms construct a similarity graph between tweets where the edge weights (i.e., the similarities between tweets) are based on the terms that two tweets have in common. In this case, noise or event-irrelevant tweets would affect the construction of the graph only when two "noise" tweets have a term in common (i.e., resulting in the formation of an edge that connects event-irrelevant tweets in the tweet similarity graph).
In order to evaluate the CSR property we have employed Ripley's Kfunction (Cressie and Wikle, 2011), which is a commonly used measure for assessing the proximity of a spatial distribution to a homogeneous Poisson point process. The sample-based estimate of Ripley's K-function is defined as N (d ij < s)/n 2 for a given distance value s, where d ij denotes the Euclidean distance between two sample points i and j (two tweets in our context) in the space, N (d ij < s) counts the number of sample pairs that has a distance smaller than s, n is the total number of points, and V (A) is the size of the area A. It is known that, when a spatial Poisson process is homogeneous, the values of the K-function are approximately equal to πs 2 . Thus, the proximity of K(s) to πs 2 can be employed for evaluating how similar our data distribution is to a homogeneous Poisson process. In this paper, we use the standardized K-function: L(s) = K(s) π − s, and the proximity to a homogeneous Poisson process is measured by the proximity of the values of L(s) to 0.
We now assess the spatial distribution of the sets of tweets shown in Fig. 5 (tweets containing the terms "nyc", "love", "lol" and "night"). Specifically, we illustrate in Fig. 6 the values of their standardized K-function for different values of s (distances) up to 4km, depicted in the black lines. Moreover, we simulate (2000 times) a homogeneous Poisson process and compute the maximum and minimum values for L(s), depicted in the blue and red dashed lines, respectively. We can observe that, the values of L(s) obtained using the locations of these tweets are close to, and in several cases within the ranges of, the values of L(s) obtained from the simulated homogeneous Poisson processes. This indicates that these tweets are slightly more concentrated in space than what a homogeneous Poisson process would produce (possibly due to the differences in the concentration of twitter users in different areas in middle and lower Manhattan), but their spatial distribution is still close to a homogeneous Poisson process.
To further explain what we mean by "still close to a homogeneous Poisson process", let us consider what appears to be one of the most extreme differences between the spatial distribution of tweets and a homogeneous Poisson process in Fig. 6, which is the value L(s) = 0.19 that is achieved for a distance value s = 1km for the term "nyc". Based on the number of tweets that contain the term "nyc" on 22-01-2012 (in middle and lower Manhattan), a homogeneous Poisson process would require an intensity parameter λ = 7.93 per square kilometer to generate the same number of tweets. This would mean that on average, the number of tweets per square kilometer that contain the term "nyc" should be 7.93. In our case, the value of L(s) = 0.19 for s = 1km means that, for small distances, the actual concentration of tweets is slightly higher, with an intensity parameter λ = 11.21 per square kilometer. This shows that, even in this worst case, the spatial distribution of tweets is still not far from a homogeneous Poisson process. In order to evaluate whether our observation for the four specific terms holds for a larger tweet collection, we analyze all the geo-located tweets from the New York area for the duration between 01-11-2011 and 01-04-2013. Specifically, for each day, we have retrieved the top-ten frequent terms, and for each frequent term we have computed the sample-based estimates of L(s) for s from 0.1km to 1.2km, again focusing on the middle and lower Manhattan area. To avoid cases where the number of samples is low, we have computed the values of L(s) only when the number of tweets in middle and lower Manhattan is larger than 100. The results are presented in the boxplot of Fig. 7, which illustrates the mean, the variance and the range of the values of L(s) (around 5000 values in total, ten for each of the500 days), for different values of s. As we can see, the boxplot in Fig. 7 illustrates that the most frequent terms in our Twitter data do not have a strong spatial pattern and follow a distribution that is close to a homogeneous Poisson process, only exhibiting slightly higher tweet concentrations for small distances.

Temporal distribution of noise in Twitter data
In order to analyze the temporal pattern of the noise in Twitter data, we have assessed whether the distribution of the timestamps of event-irrelevant tweets is close to a uniform distribution. A uniform distribution of the timestamps can serve as a strong indication that these tweets are not relevant to an event that takes place in a confined time interval. In order to test this hypothesis, we have collected the timestamps of the top-ten frequent terms of each day between 01-11-2011 and 01-04-2013. We focus our analysis on a 6-hour interval between 11am and 5pm. For this time interval we tested whether the timestamps of tweets that contain a specific frequent term follow a uniform distribution, using the Chi-squared goodness of fit test. Interestingly, we could reject the null hypothesis that the timestamps are uniformly distributed at a 5% confidence level only in 27% of the cases. This result suggests that a large number of frequent terms in our data does not have a strong temporal pattern.
In summary, the spatiotemporal analysis of the distribution of the noise in Twitter data presented in this section allows us to (i) conduct synthetic experiments with simulated noisy data that help us understand the behavior of the event detection algorithms under different space-time parameters, and (ii) consider a term-filtering mechanism that removes tweets that contain the terms with low values for L(s). We will describe both aspects in more details in the next section.

Synthetic experiments
In order to better understand the behavior of the event detection algorithms LED and MED, and the potential influence of the noise in the data, we present in this section experimental results based on synthetic data. Specifically, we generate artificial documents that are considered as "tweets" posted at different time instants and diverse spatial locations. By creating some artificial "events" in this setting, we are able to evaluate quantitatively the performances of the proposed methods under different choices for the parameter values. In what follows, we first explain the experimental setup, and then present the event detection results.

Experimental setup
We work with a spatial area of 10 by 10, which are defined by bottom left and top right coordinates (0, 0) and (10, 10) respectively in a 2-D Euclidean space, and a temporal interval of (0, 32) on the real line. We then define events that span different spatial areas and temporal intervals in diverse experimental settings. First, for each event, we choose a number between 3 and 10 uniformly at random as the number of tweets related to that event. These event-relevant tweets are uniformly distributed in the spatial area and temporal interval spanned by that event. We also generate, based on the spatiotemporal analysis presented in Sect. 5, event-irrelevant tweets, namely, noise, which follows a 2-D Poisson point process in the whole spatial area and are distributed uniformly in the whole temporal interval. Next, the content of each tweet is generated as follows. We take geo-located tweets from New York collected on a random day (in this case 21-01-2012) as a reference, and choose 59 terms as event-relevant terms (referred to as signal terms) and consider all the other terms that appear in the tweets on that day as noise (referred to as noise terms). We select the number of terms in each event-relevant tweet uniformly at random between 5 and 10. In particular, in each event-relevant tweet, one term is selected uniformly at random from the 59 signal terms, and the rest are randomly chosen from the noise terms with probabilities that depend on their numbers of occurrences in the actual daily tweets. We also create event-irrelevant tweets, and the number of terms in each event-irrelevant tweet is selected uniformly at random between 3 and 10. The terms in each event-irrelevant tweet are only chosen from the noise terms. We present event detection results in the following scenarios.

Events concentrated in both time and space without noise
In a first scenario, we consider 20 events, each of which is concentrated in a 2 by 2 spatial area and a temporal interval of 2. The spatial and temporal loca-tions are chosen uniformly at random in the whole spatial area and temporal interval. We only consider event-relevant tweets, where the goal is to detect the 20 clusters that correspond to the events by clustering the tweets into different subsets. For MED, we focus on terms that appear in at least 3 tweets. We choose n scale = 4 unless its upper bound min(log 2 l d , log 2 l t ) goes below 4 due to the increase of resolution parameters. In our experiments, we take the same value for the four parameters in the two methods, namely T t and T d in LED and ∆t and ∆d in MED, and evaluate the clustering performance in terms of Normalized Mutual Information (NMI) and F-measure (Manning et al, 2008). The F-measure is computed using a choice of β = 2 meaning that it is slightly in favor of recall 6 , as we consider that it is more important to ensure that tweets related to the same event are grouped into one cluster. The results obtained by averaging 10 test runs are shown in Fig. 8. As we can see, in terms of both evaluation criteria, the performance of LED with small values of the thresholds T t and T d is not satisfactory as it is not able to capture the links between all the tweets within the same event. However, the performance increases noticeably as the temporal and spatial thresholds are chosen to be close to or larger than the "true" scales of the events (2 in this case for both time and space). When the thresholds get too large, the performance drops slightly, as the chance of grouping two different events together in one cluster increases. Compared to LED, MED achieves much better performance even when the resolution parameters ∆t and ∆d are small. The reason is that, even at very fine initial resolutions, the wavelet-based representation in MED is able to aggregate the time series appropriately such that the similarity of the time series is actually computed at a coarser scale. This suggests that MED is better at capturing the links between tweets corresponding to the same event, even with suboptimal choices for the value of the parameters. Therefore, the performance of MED is much less sensitive to parameter selection than that of LED.

Events concentrated in only one dimension without noise
We now consider events that are not necessarily concentrated in both time and space but only in one of the two dimensions. Specifically, we consider 20 events, where 10 of them are concentrated in a temporal interval of length between 1 to 2 but spread in a spatial area with a size from 8 by 8 to 16 by 16. The other 10 events are concentrated in a spatial area with a size from 1 by 1 to 2 by 2 but spread in a temporal interval of length between 8 to 16. We still consider a noise-free scenario as in the previous experiment. The clustering results are shown in Fig. 9. We see that, while MED can handle the scale changes in this scenario with a performance that remains comparable to that in the previous experiment, the performance of LED drops significantly. Specifically, due to the lack of a single temporal and spatial scale for all the events, LED only performs reasonably well when the threshold values for T t (a) (b) Fig. 8 Clustering performance in terms of (a) NMI and (b) F-measure, on events concentrated in both time and space without noise.
(a) (b) Fig. 9 Clustering performance in terms of (a) NMI and (b) F-measure, on events concentrated in only one dimension without noise.
and T d are large enough to cover the scales of all the events. This experiment highlights the advantage of MED in handling events of different scales and in the absence of simultaneous temporal and spatial localization.

Events concentrated in both time and space with noise
We now move to noisy scenarios where we also consider event-irrelevant tweets in addition to event-relevant tweets. Specifically, we generate event-irrelevant tweets that follow a 2-D Poisson point process with an intensity parameter λ = 10 within the whole spatial area of 10 by 10. This generates around 1000 noise tweets in addition to the tweets that correspond to 20 events generated as in Sect. 6.2.1. The goal is to detect the events by applying clustering to all the tweets in the dataset. To measure the clustering quality, we define the groundtruth to be a combination of 20 event clusters and noise clusters where each noise tweet is considered as a single cluster. The reason for this setting is that we wish to group tweets that correspond to the same event, and at the same time we want to ensure that the noise tweets remain as separated as possible. Based on the analysis in Sect. 5, for MED, we propose to evaluate the values of the standardized K-function L(s) for all the terms that appear in at least 3 tweets for s chosen to be 0.5, 1, 1.5 and 2, and only consider terms that have an average L(s) value no smaller than 1 as valid terms for generating keyword time series. The clustering results are shown in Fig. 10. In the noisy scenario, we see that the NMI and F-measure curves show different trends. Specifically, with small values for the threshold or resolution parameters, the number of links between tweets created by both methods is small, and most of the noise clusters remain well-separated. When the parameter values increase, noise tweets starting forming more links to event-relevant tweets as well as to themselves, which penalizes the clustering. Therefore, we see that the NMI curves show an almost monotonically decreasing trend as the parameter values increase. In contrast, the F-measure is a weighted combination of precision and recall, which penalizes both false positives and false negatives. Therefore, for both methods, we see that the F-measure curves initially increase as the parameter values increase (where the number of false negatives generally decreases), and decrease as these parameters become large (where the number of false positives increases). We now compare the performance of LED and MED in the same experiment. For NMI, we see that the performance of LED drops significantly when the thresholds exceed the "true" scales of the events, as large thresholds in LED tend to increase the number of event-relevant and noise tweets that are linked to each others. In comparison, the performance of MED is relatively more stable, which is partly due to the term-filtering procedure employed. Similarly, we see that MED outperforms LED for a large range of parameter values in terms of the F-measure. In addition, the performance of MED is again more stable in the sense that it peaks at a wider range of parameter values, while LED only performs well when the threshold values are chosen at the "true" event scales.

Events concentrated in only one dimension with noise
Finally, we show in Fig. 11 the experimental results in a noisy scenario where the events are concentrated either in time or space as defined in Sect. 6.2.2. While the NMI curves are similar to those in Fig. 10, the F-measure curves show that the performance of both methods drops significantly in this challenging scenario. Still, MED outperforms LED in terms of both peak performance and stability.

Influence of parameter settings
We now take a closer look at the parameter settings for the synthetic experiments. Especially, we investigate how the length of the temporal interval, the size of the spatial area, and the number of signal terms in each event-relevant tweet, influence the performance of both algorithms in terms of the F-measure in the scenario of Sect. 6.2.4, that is, the performance curve in Fig. 11(b)). First, given a fixed parameter for the Poisson point process and fixed spatial area of 10 by 10, the total number of noise tweets remains the same. In this case, we observe that the performance of both algorithms has improved when the temporal interval increases from 32 to 128 ( Fig. 12(a)), due to decreased noise density in the temporal dimension hence a higher signal-to-noise-ratio. Such a gain is more dramatic for LED especially at large parameter values, in which case the performance of this approach is more sensitive to the density of the noisy information.
Second, given a fixed temporal interval of 32, as the spatial area increases from 10 by 10 to 16 by 16, the total number of noise tweets increases quadratically. In this case, we see from Fig. 12(b) that the performance of both algorithms decreases mainly because of that, as the total number of noise tweets increases, generally more links are formed between noise tweets.
Finally, we have investigated the influence of the number of signal terms in each event-relevant tweet on the performance of the algorithms. Specifically, we increase the number of signal terms from 1 to 3 in each event-relevant tweet and repeat the same experiments. We have observed performance gain in Fig. 12(c) for both algorithms which matches the intuition that a higher signal-to-noise-ratio generally leads to better performance. In summary, the synthetic experiments suggest that LED is efficient at detecting events that are concentrated in both time and space, provided that these events are of similar scales and that the correct temporal and spatial thresholds are chosen in the algorithm. In comparison, although we employed a term-filtering procedure in MED in the noisy scenarios, the results on synthetic data generally suggest that MED is better than LED at detecting events of different scales and in the absence of simultaneous temporal and spatial localization. MED is also less sensitive to parameter selection and leads to more robust and stable event detection performance.

Real world experiments
We now test the performance of LED and MED in real world event detection tasks. We focus in this section on the comparison between these two event detection methods, since (i) such a comparison would highlight the difference between LED and MED in detecting real world events of various temporal and spatial scales, and (ii) to the best of our knowledge, there is no other multiscale method in the literature that is dedicated to event detection. We first describe the data and some implementation details, and then present the event detection results. Finally, we discuss about the scalability of the proposed algorithm.

Data description
We have collected geotagged public tweets in the New York area, which corresponds to a geographical bounding box with bottom left GPS coordinates pair (40.4957, -74.2557) and top right coordinates pair (40.9176, -73.6895), from November 2011 to March 2013. The streams of public tweets are retrieved using Twitter's official Streaming API with the "locations" request parameter 7 . After the initial retrieval, we filter out those tweets that have no geotags or have geotags outside the predefined bounding box. This results in 16449769 geotagged tweets in total. As a pre-processing step, we remove those tweets that contain a clear location indicator, such as the ones corresponding to Foursquare check-ins, which we do not consider as events of interest.

Implementation details
We implement both event detection algorithms LED and MED on a daily basis, that is, we aim at detecting events from each day. The tf-idf weighting scheme in the vector space model is implemented using the Text to Matrix Generator (TMG) MATLAB toolbox (Zeimpekis and Gallopoulos, 2006), where we also remove a list of stop words provided by the toolbox (with an additional one "http"), and set the minimum and maximum length of a valid term to be 3 and 30.
For LED, we use a temporal threshold of T t = 30 minutes and spatial threshold of T d ≈ 100 meters (difference of 0.001 in latitude or 0.0015 in longitude) in Eq. (1) for the detection of local event clusters. For MED, we focus on terms that appear in at least 5 tweets. We evaluate the values of the standardized K-function L(s) for all these terms with s chosen to be 0.2, 0.4, 0.6, 0.8 and 1, and only consider those that have an average L(s) value no smaller than 0.5 as valid terms for generating keyword time series. The initial temporal and spatial resolutions in MED are set to ∆t = 30 minutes and ∆d = 100 meters, and the number of spatial scales is set to n scales = 4. Once the clusters are obtained by both methods, we perform simple post-processing steps that (i) remove clusters that contain less than 3 tweets or less than 3 distinct users, so that each event would contain sufficient information from sufficient number of observes, and (ii) remove clusters in which more than 50% of the tweets comes from a single user, so that the information source is sufficiently diverse, and finally (iii) remove clusters that correspond to job advertisements and traffic alerts posted by bots. While there is no general rule for such post-processing, we found these steps practical to remove clusters that are not meaningful and correspond to noisy information.

Event detection results
We now analyze the clustering results for both LED and MED algorithms. First of all, the clusters detected by LED do correspond to meaningful real world events of interest. For example, Table 1 shows some example local clusters obtained that correspond to several protests during the Occupy Wall Street (OWS) movement 8 in New York City. To understand better the behavior of LED, we take 2011-11-17 as an example date, when many OWS protests took place. We first show in Fig. 13 all the 41 local event clusters detected on this date in middle and lower Manhattan, where different clusters are shown in different colors. Detailed information about the top 20 clusters are further shown in Table 2, where the six columns correspond to cluster id, median timestamp (GMT+0) of all the tweets in the cluster, minimal time interval (in seconds) that covers 80% of the tweets, mean latitude and longitude of the tweets, and (up to 10) top terms contained in the cluster. As we can see in Fig. 13 and in the third column of Table 2, all the clusters are highly localized in both time and space. In addition, due to the strict temporal and spatial constraints used by LED (see Eq. (1)), for the same event we get separate clusters, which correspond to different timestamps (such as clusters 2 and 5 that talk about protests at Zuccotti Park) or different locations (such as clusters 3 and 13 that talk about protests at Union Square). Ideally, we would like some of these separated clusters to be grouped together if they are related to the same real world event.
We now present the event detection results on data from the same date using MED. Table 3 Table 3, we see that MED is able to detect events that spread in much larger spatial areas or longer time intervals than LED. Specifically, we see in Fig. 14(a) and Fig. 14(b) two clusters related to OWS protests at Zuccotti Park (cluster 1), and Union Square and Foley Square (cluster 2), respectively, both of which span rather long time intervals. Moreover, although most of the tweets in the two clusters are mainly posted from locations where the protests took place, there also exist tweets in the clusters that mention the same events but have been posted at quite distant locations. In Fig. 14(c) and Fig. 14(d), we see two clusters corresponding to the Raise Cache tech event (cluster 5) and the Mastercard free lunch promotion event (cluster 9), respectively, both of which are more concentrated in time but spread in space (with a few outliers in the latter case). Although there exists certain amount of noise tweets in the detected clusters, these examples demonstrate that MED is able to detect events that concentrate only in time or space, many of which are of different scales. In comparison, LED is not able to detect such event clusters. Specifically, LED produced many separated clusters for OWS protests, two separated clusters with some missing tweets for the Raise Cache tech event, and missed completely the Mastercard promotion event due to the lack of a group of tweets that are concentrated in both time and space.
Finally, we notice that even in the results obtained by MED there sometimes exists more than one cluster about the same event, for example, in Table 3 there are two clusters detected for both the OWS protests (clusters 1 and 2) and the Katy Perry concert (clusters 3 and 4). First, the protests at Zuccotti Table 2 Detailed information about the top 20 local event clusters detected by LED on 2011-11-17. The six columns from the left to the right correspond to cluster id, median timestamp (GMT+0) of all the tweets in the cluster, minimal time interval (in seconds) that covers 80% of the tweets, mean latitude and longitude of the tweets, and (up to 10) top terms contained in the cluster. Table 3 Detailed information about the top 10 event clusters detected by MED on 2011-11-17. The six columns from the left to the right correspond to cluster id, median timestamp (GMT+0) of all the tweets in the cluster, minimal time interval (in seconds) that covers 80% of the tweets, mean latitude and longitude of the tweets, and (up to 10) top terms contained in the cluster.
Park took place from the morning to noon, while the protests at Union Square and Foley Square happened in the afternoon after 3pm. Although there indeed exist semantic links between tweets that correspond to these two events, the rather different locations and timestamps lead to separate clusters. Second, for the Katy Perry concert, the two clusters highly overlap in both time and space, and the tweets in one cluster have quite strong links to those in the other one. In this case, clusters have been separated mainly because of the strong patterns present in the texts: While in cluster 3 the concert is described mostly using a single term "katyperry", in cluster 4 we see two separate terms "katy" and "perry".

Scalability
The computational complexity of both LED and MED mainly depend on (i) the construction of a similarity graph, and (ii) the graph-based clustering process. As we mentioned before, the Louvain method used in the clustering process is empirically observed to be able to scale to large scale graphs. Therefore, we mainly discuss the computational cost of constructing similarity graphs in the two algorithms. For both LED and MED, the construction of a similarity graph can be performed efficiently because the similarities need to be computed only for pairs of tweets that have common terms. Thus, the computational complexity of the similarity graph construction, using an appropriate index structure (such as an inverted index), can be O(n × avg connectivity), where n is the total number of tweets and avg connectivity denotes, given a tweet t, the average number of tweets in the dataset with non-zero similarity with t. In our real world experiment, avg connectivity corresponds to only 2% of the total number of tweets.
In addition, avg connectivity can be further reduced by the term-filtering procedure that is employed in MED for noise-filtering. Since term-filtering is applied to the most popular (frequent) terms, this can substantially affect avg connectivity. In our experiment, for example, after the filtering procedure avg connectivity is further reduced by more than 40% compared to LED. Moreover, the filtering procedure potentially represents a tradeoff between the performance of the algorithm and its computational complexity. A more aggressive filtering can largely attenuate the influence of noisy information and at the same time reduce the computational cost. However, it might also filter out terms that are related to some relatively small-scaled events.
For MED, we need to compute the spatiotemporal similarity of time series for the valid terms (after term-filtering) shared by every pair of tweets. However, since the spatiotemporal similarity is defined between time series that come from different geographical cells, we only need to evaluate, for each valid term, the pairwise similarity between time series from different cells, instead of comparing every pair of different tweets containing that term. This keeps the number of DWT computations needed relatively low due to the small number of geographical cells.
Practically, for the daily Twitter stream with geotag in the middle and lower Manhattan area of New York City that we have considered in the experiment (∼8000 geotagged tweets with 36000 terms in total), it takes only a few seconds to finish the construction of the similarity graph in LED. For the implementation of MED, it takes roughly 5 minutes for our MATLAB code to create the similarity graph on a lab server with average computing power or 8 minutes on a mid-2009 MacBook Pro (both single core process), where the main computational cost is due to the DWT computations. While we consider this computation time reasonable given the benefits of the algorithm, we certainly hope to further improve the scalability of our algorithm in future work.

Related work
Social media data have become pervasive due to the fast development of online social networks since the last decade. This has given rise to a series of interesting research problems such as event detection based on user-generated content (Sayyadi et al, 2009;Becker et al, 2009;Aggarwal and Subbian, 2012). As an example, Chen and Roy (2009)   have proposed to detect social events using tagged photos in Flickr. A more popular platform is Twitter, which has attracted a significant amount of interest due to the rich user-generated text data that can be used for event detection (Atefeh and Khreich, 2013). Early works in the field have focused on more specific types of events, such as news (Sankaranarayanan et al, 2009) and earthquakes (Sakaki et al, 2010), while recent approaches detect various types of events (Petrovic et al, 2010;Marcus et al, 2011;Becker et al, 2011;Ozdikis et al, 2012;Li et al, 2012a;Parikh and Karlapalem, 2013;Berlingerio et al, 2013). Although the specific techniques presented in the state-of-the-art event detection approaches may vary from a technical point of view, many of them rely on the detection of certain behaviors in the Twitter stream such as the burstiness of certain keywords, which indicates the emergence of particular events. In particular, several works use wavelets, which is a well-developed tool in signal processing, for event detection based on keyword burstiness patterns (Weng and Lee, 2011;Cordeiro, 2012).
Recently, there has been an increasing amount of interest in exploring both the temporal and spatial dimensions to better capture the meaningful information and reduce noise in the data from social media platforms. In Rattenbury et al (2007), the authors have proposed to analyze for event extraction the semantics of tags associated with the Flickr photos, by taking into account multiple temporal and spatial resolutions. In Chen and Roy (2009), the authors have proposed to cluster Flickr photos based on both the temporal and the spatial distributions of the photo tags using wavelets. In Becker et al (2010), the authors have considered combining text, temporal and spatial features in order to build an appropriate tweet similarity measure. In Lappas et al (2012), the authors have proposed two approaches to detect burstiness of keywords in both temporal and spatial dimensions simultaneously. In Sugitani et al (2013), the authors have proposed a hierarchical clustering procedure for event detection in Twitter, where both temporal and spatial constraints have been imposed to measure the similarities of tweets. They have also proposed to examine co-occurrences of keywords that present specific spatiotemporal patterns. Other examples include Lee et al (2011);Li et al (2012b); Thom et al (2012); Walther and Kaisser (2013) and Zaharieva et al (2013), where the authors have proposed spatiotemporal clustering methods for anomaly and event detection in Twitter and Flickr, respectively. These approaches are certainly inspirational to the idea proposed in the present paper; However, most of them do not explicitly handle multiple spatiotemporal scales in event detection.
Finally, there are a few approaches in the literature that have studied the influence of different resolutions for temporal and spatial analysis in event detection. For example, in Cooper et al (2005) and Rattenbury et al (2007), the authors have proposed to use a scale-space analysis of the data (Witkin, 1983). The common objective in these approaches is to select the most appropriate scale for event extraction and detection. More generally, multiscale or multiresolution clustering algorithms has been of interest in the machine learning, pattern recognition, and physics (Ronhovde et al, 2011(Ronhovde et al, , 2012 communities since the last decade. The approaches that take advantage of the properties of the wavelet transform to enable a multiresolution interpretation in the clustering process, such as the works in Sheikholeslami et al (2000) and Tremblay and Borgnat (2012), are of particular interest. Although these approaches are not originally proposed for event detection in social media platforms, they have inspired us to consider wavelets in our framework. While they output multiple sets of clustering solutions at different resolutions, our approach however uses wavelets to choose the appropriate temporal and spatial resolutions for constructing a single data similarity graph.
In summary, although there exist many approaches that take into account the temporal and spatial dimensions of the social media data for event detection, they generally do not explicitly handle different scales in data analysis.
In contrast, our framework explicitly handles multiple spatiotemporal scales, which we believe is essential for building an efficient and generic event detection approach. Different scales in the temporal and spatial dimensions have been treated separately in most of the state-of-the-art analyses, but the relationship and interaction between these scales have been largely overlooked in the literature. To the best of our knowledge, our approach is the first attempt that is based on an explicit modeling of the relationship between different temporal and spatial resolutions. Finally, we present a statistical analysis of the temporal and spatial distributions of noisy information in the Twitter data, which we believe is the first of its kind. We believe our perspective contributes to the research in the field of social media analytics and provides new insights into the design of novel clustering and event detection algorithms.

Conclusion
In this paper, we have proposed a novel approach towards multiscale event detection in social media. Especially, we have shown that it is important to understand and model the relationship between the temporal and spatial scales, so that events of different scales can be separated simultaneously and in a meaningful way. Furthermore, we have presented statistical modeling and analysis about the spatiotemporal distributions of noisy information in the Twitter stream, which not only helps us define a novel term-filtering procedure for the proposed approach, but also provides new insights into the understanding of the influence of noise in the design of event detection algorithms. Future directions include (i) further investigation of the possibility of extending and generalizing the proposed scale relationship model to handle temporal and spatial scales simutaneously for multiscale event detection, (ii) more appropriate and accurate statistical models for analyzing noisy information present in social media data, and (iii) improvement on the scalability of the proposed algorithms.