Modeling Implicit Communities using Spatio-Temporal Point Processes
from Geo-tagged Event Traces

Within general social networks, there has been much work on detecting communities as overlapping or non-overlapping clusters of users such that there is a high degree of connectedness between them. Techniques have largely considered social-network connectedness as the main driver in forming communities. Community detection techniques could adopt a top-down approach starting from the entire graph and form communities by separating them into more coherent subsets that would eventually become communities. Methods from this school include those that use graph-based methods [27] and filtering out edges based on local informations such as number of mutual friends [40]. Analogously, community discovery could proceed bottom-up by aggregating proximal nodes to form communities. Techniques within this category have explored methods such as merging proximal cliques [16] or by grouping nodes based on affinities to ’leader’ nodes [15]. Point processes[6], which are popular models for sequential and temporal data, have been recently explored for community detection in general social networks[29]. NetCodec, the method proposed therein, targets to simultaneously detect community structure and network infectivity among individuals from a trace of their activities. The key idea is to leverage multi-dimensional Hawkes process in order to model the relationship between network infectivity vis-a-vis community memberships and user popularity, in order to address the community discovery and network infectivity estimation tasks simultaneously. Our task of community detection within LBSNs is understandably more complex due to the primacy of spatial information in determining LBSN community structures. Accordingly, we leverage a spatio-temporal variant of multi-dimensional Hawkes process, in devising our solution.

With each LBSN check-in being associated with a location, the location information is central to LBSNs. There has been much research into modelling user-location correlations in various forms, which may be referred to as location adoption in general.

[14] is the closest work to our work, where authors determine the patterns from geo located posts from twitter. Our model deals with discrete locations unlike [14] which simply considers sampling of spatial locations from a continuous distribution which can not be used for modeling check-in locations. The intensity function in CoLAB seamlessly integrates temporal and spatial components of the model and jointly learns the parameters whereas in [14] location and time are modeled separately. Moreover, we use multi-dimensional Hawkes Process as intensities differs across users. The parameter estimation of multi-dimensional Hawkes Process is much harder and Monte Carlo Simulations based methods used in [14] are very slow. We introduce the use of stochastic variational inference (SVI) [2] to overcome this. [11] and [10] exploit the role of social correlations and temporal cyclical behaviors in improving upon the task of predicting the next location that a user would check-in. Location categories (e.g., restaurant, pub etc.) has also been seen to be useful for next location prediction[22]. [34] exploit geographical influence across locations in recommending POIs (points of interest) to LBSN users.

Another task that has attracted significant attention within LBSNs is that of quantifying user influence in LBSNs. [37] consider using geo-social correlation between users to estimate mutual influence. [32] leverage the observation that mutual influence is central to successful recommendation to identify a set of influential seed nodes using information cascade models. [3] adopt influence propagation models to address a slight variant, that of identifying region-specific influential users. [18] and [30] propose other kinds of models for the influence maximization task within LBSNs. ocation Promotion [42][21] and Trip Purpose Detection [13] form other les addressed tasks within the context of LBSNs. Mobility models that mine spatial patterns based on generative models [11], Gaussian distributions [4] and kernel density based estimations [20] have been particularly popular in modeling location adoption behavior within LBSNs.

Given the check-in events $E$ as defined earlier, for modeling time and spatial components w.r.t. communities, we define the Hawkes process based model as follows:

The category $c$ associated with a check-in is represented as a $|V|$-length vector and it represents one of $V$ possible categories²²2We overload the notation $c$ to also represent a scalar categorical value in the set $\{1,\ldots,V\}$ such as restaurant, entertainment etc. associated with the check-in. Also, we assume that the category depends on the underlying latent community associated with this check-in. For example, some community may be more inclined towards restaurants while another community is oriented towards sports. The category is modelled as a sample from a Multinomial (categorical) distribution,

where $\boldsymbol{\theta_{g}}$ is a $|V|$-length vector whose elements encode probability of each category and which depends on the community $g$ that the check-in belongs to. We assume a prior over $\boldsymbol{\theta_{g}}$ as a sample from Dirichlet distribution with parameters $\boldsymbol{\theta_{0}}$. We write the conditional distribution $p(c,\boldsymbol{\theta_{g}}|\boldsymbol{\theta_{0}})$ as:

$j$ runs over the $V$ categories and $p(c|\theta_{g})$ is given as $\theta_{g,c}$

We assume the latent variable $g$ (the communities) associated with the user for some check-in, is distributed as multinomial distribution parameterized by $\pi_{i}$ for a user $i$. $\pi_{ig}$ represents the probability user $i$ belongs to community $g$.

Note that, for sampling (t,x,y), the thinning algorithm proposed in [17] is modified in order to sample location coordinates from discrete “venue” set rather the continuous space. First we consider a discrete set of locations $L$ for the user based on her region. We sample $(x^{\prime},y^{\prime})$ at $n^{th}$ iteration, from a Gaussian distribution centered at the previous coordinates in the $(n-1)^{th}$ iteration: $(x_{n-1},y_{n-1})$. Once $(x^{\prime},y^{\prime})$ is sampled, the nearest coordinate in the $L$ is determined and returned as $(x_{n},y_{n})$.

The latent variables $g_{n}$’s dependent on different types of feature set i.e. space, time through $p(t_{n},\ell_{n}|i_{n},g_{n})$ and semantics through $p(c_{n}|g_{n},\theta)$. Though the prior over $g_{n}$ is conjugate to $p(c_{n}|g_{n},\theta)$, it is not with respect to $p(t_{n},\ell_{n}|i_{n},g_{n})$ and hence the posterior over $g_{n}$ cannot be computed in closed form. Moreover, $g_{n}$’s are inter-dependent i.e. at current step $g_{n}$ it is dependent on history from $g_{1}$ to $g_{n-1}$ as well as the future ones i.e. $g_{n+1}$. Thus marginalizing out over such interconnected latent variables to compute the normalization constant for the posterior is intractable. To this end we assume a variational distribution over $g_{n}$’s conditioned on the user $i_{n}$. The conditional variational distribution over $g_{n}$ is considered to be a multinomial distribution with parameters $\boldsymbol{\phi_{i_{n}}}$. The variational parameter $\boldsymbol{\phi_{i}}$ for a user $i$ represents the posterior probability distributions over the communities for the user as observed from the data.

The variational parameters can be learnt by minimizing the KL divergence between the variational posterior (10) and the exact posterior (9). However, a direct minimization of KL divergence is not possible due to the intractable posterior. Following variational inference approach [2], the variational parameters are learnt by maximizing a variational lower bound, Evidence Lower Bound (ELBO), which indirectly minimizes the KL divergence. ELBO is obtained by considering an expected value of the complete joint log likelihood w.r.t the variational distribution [2] and acts as a lower bound to the marginal likelihood or evidence (normalization constant of the posterior). Hence, ELBO is useful to learn the model parameters also in addition to the variational parameters. Using the variational distribution defined in (10) and the complete joint log likelihood (8), we obtain the ELBO as:

Here, $\mathbb{E}_{q}$ represents the expectation with respect to the variational distribution $q$ defined in (10). We learn the variational parameters and the model parameters by maximizing the ELBO. Table 2 lists the model parameters and variational parameters to be learnt using ELBO. All the terms in the ELBO except the first term can be computed in closed form.

Since the first term in (11) cannot be computed in closed form, we approximate it using the samples from the variational posterior (10) (Monte-Carlo approximation).

where $\boldsymbol{g^{(s)}}$ represent the vector of $N$ samples sampled from the joint variational distribution over all the $g_{n}$’s, i.e. $q(\boldsymbol{g^{(s)}})=\prod_{i=1}^{N}q(g_{n}^{(s)}|\phi_{i_{n}})$. This results in a stochastic variational lower bound where the stochasticity arises due to the approximation of expectation using Monte Carlo sampling [38]. We learn the model parameters $\mu$, $\eta$, $A_{ij}$, $\theta$ by maximizing the stochastic variational lower bound [26] using gradient based methods. However learning the variational parameters is problematic as the variational parameters does not appear explicitly in the stochastic term but only through the samples. For determining gradient w.r.t. $\phi$ we apply the Reinforcement trick to the stochastic term and compute the gradient as follows [9]:

We generate synthetic data using algorithm 1 (statistics in Table 4). The set of locations, #users to categories i.e. (U:V) and to the number of checkins i.e. (U:N) are kept similar to the real data collected from Brazil with $\nu$ (temporal decay parameter) is set to 0.01 [33] and $h$ is picked up from the bandwidth values learned from users’ checkins. During inference, we use true values for all the parameters, except for the influence matrix $A_{ij}$ and the user-community posterior $\phi$ which are estimated. We use $RelErr(A_{ij},\hat{A}_{ij})=\frac{1}{I^{2}}\sum_{i,j=1}^{I}\frac{|a_{ij}-\hat{a}_{ij}|}{|a_{ij}|}$ (and similarly for $\phi$), as the metric to evaluate the ability to recover the true values. Table 4 indicates that the stochastic variational inference technique offers considerably better reconstruction of the parameters, recording significant reductions in the error.

For real data, we use our crawls over Foursquare conducted between January-2015 and March-2016 and construct two collections consisting of check-ins from Saudi Arabia (SA) and United States (US), with details given in Table 4. We allocated first 80% (as per check-in timestamp) of each dataset to training and remaining for testing. Here, we also use temporal decay parameter as 0.01 [33] and $h$ is learnt for each user based on Silverman’s rule of thumb in kernel density estimation [1] and is fixed during the joint estimation.

We plot communities over SA and US data in Figure 4, where colored dots represents a check-in. In figure  4, it can be observed that; (i) Overlap between communities due to data concentration in cities. (ii) CoLAB is able to capture communities across cities.

Unfortunately, we lack the community ground truth for users, making communities assessment a non-trivial task. Thus, we use a metric a joint loss function for the intra-community properties through a mixture of (i) category loss ($\mathcal{L}_{cat}$) and (ii) location loss ($\mathcal{L}_{loc}$). Category Loss: We consider all categories associated to locations as independent marks of a point process. Hence to estimate the category affinity in a community, we consider similarity among the check-in categories using pre-trained word embeddings [24] and devise a loss function.

where $\mathbf{T}$ represents test data, $\mu_{g}$ is category mean for a community $g$ using $K_{cat}$ frequent categories, $\mathbf{v}_{E_{n}}$ is the category vector for event $E_{n}$; $\Phi(E_{n},g)$ indicates whether $E_{n}$ is assigned to community $g$, with $\mathcal{M}$ as all communities. Table 6 demonstrates CoLAB’s ability to capture category dynamics across communities. Although, it can be observed that at $K_{cat}$ = 10 Dirichlet Hawkes performs better because with most frequent categories like restaurant, coffee shop etc. DH assigns it most of the communities. Note that, DH is unable to capture communities with varied categories as seen at $K_{cat}$ = 50 and 100, that CoLAB performs better.
Location Loss:[4] show that users tend to visit nearby locations given we ignore the bias of loyalty. Hence ideally, a community of users not spatially dispersed in their checkin characteristics should be distinct from another community with checkins spanning large distances. We capture this through a distance based k-means loss ($\mathcal{L}_{loc}$) with cluster means($\mu_{l}$) for checkin coordinates for each community. In table 7 we can see CoLAB performs significantly better than other baselines because CoLAB can better capture the geographical dispersion in communities.