In this paper we investigate the problem of recommending Twitter hashtags for users with known GPS location, learning online from the stream of geo-tagged tweets. Our method learns the relevance of regions in a geographical hierarchy, combined with the local popularity of the hashtag. Unlike in typical collaborative ltering settings, trends and geolocation turns out to be more important than personalized user preferences. We evaluate in a time-aware setting, where evaluation is cumbersome by traditional measures, since we have di erent top recommendations at di erent times. We describe a time-aware framework based on individual item discounted gain.
We investigate the problem of recommending Twitter
hashtags for users, based on the temporal geolocation
information of both the users and the hashtags. Our aim is to
recommend new hashtags, i.e. hashtags that the user has not
used before. The recommendations are obtained by
learning online from the stream of geo-tagged tweets. In our task
the novel element is that neither users nor items (hashtags)
are bound to one single location. Hashtags may in fact
relate to certain locations as well as be popular worldwide.
Earlier results on recommendation in location-based social
networks surveyed in e.g. [
Since hashtag usage is highly volatile, the problem calls for
an online method. Whenever a user sends a geotagged tweet
with a hashtag he or she has not used earlier, we consider the
event as a trigger for recommendation. We measure the
accuracy of our methods in the online evaluation framework of
[
We nd that location and timing are the key factors with
little contribution from personalized user interest. The
locality of Twitter hashtag adoption in both spatial and
temporal sense is observed among others by Kamath et al. [
We use a four-month collection of 400 million geotagged
Twitter messages detailed in [
Some content may have obvious connection to certain
locations but others can have more widespread interest on
di erent levels such as language, continent, or even
worldwide. Dealing with this, our models rely on the hierarchy of
regions from a global or continent-wide level down to a
village or city district to attribute the momentary popularity
of a hashtag to levels of locations. This hierarchical property
of locations is surveyed also in [
We use two models to recommend hashtags at a given time and location, one based on the estimated probability of the hashtag appearance based on its recency, and another based on its temporal popularity. In both cases, our new method learns the importance of each node in the GADM tree. The nal prediction arises as the weighted combination of the hashtag probabilities along the path of the GADM tree from the leaf location of the user up to the root.
As baseline method, we use online matrix factorization
[
Most of previous publications on geographic recommender
systems work with check-in data, where each of the items has
a prede ned static location. For brevity, we do not survey
these here. Hashtag recommendations are addressed in two
recent papers: Chen et al. [
Spatial statistics of hashtag adoption are analyzed by
Kamath et al. [
No other results use external data to de ne the hierarchy
of locations for recommendation tasks. Similar to our result,
in [
We use the online recommendation framework described
in [
The data is implicit: the events imply only that the user is interested in a hashtag. In most of our models, we need negative instances as well for training. We use all hashtag usages as positive training instances and generate negative training instances by selecting negRate random hashtags uniformly at the time when a user rst used a hashtag. We tested the negRate parameter between 1 and 300.
We use the quality metric of [
Dobos et al. [
Most of the hashtags in the database are quite rare, thus we use only the hashtags that appear more than 5 times. This way we exclude about 90% of the hashtags, but most of the hashtag timeline remains. We also exclude the hashtags that appear in the rst month of the collection to recommend newly spreading hashtags for the users. The properties of the nal cleansed dataset are summarized in Table 1.
We collected all 214,230 nodes from the GADM database, from which 190,315 are leaves. The depth of the tree is 6, and includes 5 levels from the GADM tree plus continentcountry relations. The hashtag time series data covered 30,450 leaves from the tree. 4. 4.1
In our recommendation model we use the location ` at time t of the user. Here ` notes the leaf of the tree that is closest to the current GPS location of the user. First, we get the path in the tree from the root node to location `, Path(`). Next, for a given hashtag, assume we have a recommendation method that yields scores s(h; n; t) for nodes n along Path(`). We will give two such methods in the next subsections. In order to aggregate the individual recommendation at each GADM tree node, we propose the formula r^(u; h; `; t) =
wn s(h; n; t);
X n2Path(`) where wn values are node speci c weights. The weights wn are independent of the hashtags and characterize the area n only. We learn the weights by online gradient descent by optimizing for RMSE. If we consider all positive instances and generate negative ones as described in Section 2, we will have su ciently many implicit data to update the weights online as we read the sequence of events.
In our experiments we also investigate models where we set all wn values constant, i.e. we do not learn the weights, but simply sum all s(h; n; t) values along Path(`). 4.2
Given a prede ned time discretization that we test between a minute and a day, for each location in the tree, we compute the number of occurrences of the hashtag in the time interval at the given location. As it follows power-law distribution, we use the logarithm of the temporal popularity values as node scores: s(h; n; t) = log(pop(h; n; t)), where pop(h; n; t) denotes the number of occurrences of hashtag h in node n in the time interval ending at time t. 4.3
Our next method estimates the chance of the appearance
of a hashtag by considering its most recent usage. The
advantage of this method is that it is more sensitive to changes
in trends. While it may more aggressively over t to single
events, overall it performs similar to and combines very well
with the popularity based method. In Fig. 1, we investigate
the distribution of the time elapsed between the same
hashtag appearing in tweets. This inter-event time distribution
follows power law, in accordance with several earlier
observations [
We apply stochastic gradient descent factorization for the
user-hashtag matrix as in [
In our graphs we show the average cumulative DCG for the rst three weeks, by when all of our methods reach stable performance. Here the cumulative average corresponds to cumulative time average. We set k = 100 to compare our methods in detail. All methods show a slight performance degradation, which is due to the fact that the number of possible hashtags to recommend increase in time. 5.1
We used the online version of stochastic gradient descent
(SGD) matrix factorization algorithm of [
As we show next, our tree based methods and their baseline variants to exploit geographical information resulted in better performance in our experiments.
0.4
The temporal popularity based method using the GADM tree of Section 4.2 achieved best results by setting the time frame around 2 hours. In the recency based model of Section 4.3, the parameter t had relatively little e ect, we set t = 12h. We compared the popularity and recency based methods separately in Figs. 2 and 3, resp., by using di erent levels of the GADM tree and turning recency and node weight learning on and o .
In the gures, \world" denotes the methods that use global values only and do not take user geolocation into account, while \leaves" and \countries" use the corresponding level of the tree. Note that country level popularity and recency performed very well while leaves worked only with recency not popularity. Note that using countries but no temporal information at all performs the poorest.
Best performance is obtained when using the whole tree for recommendation by adding all recency values along the path corresponding to the current user location in the tree, marginally improving the country based results. However, by applying the gradient method to learn node speci c weights as in Section 4.1, we could achieve signi cantly better results for recency but not for popularity. By using the recency based tree learning algorithm, we were able to focus on the active and representative part of the tree. We achieved our best results with lRate=0.0001 and negRate=4. 5.3
In our nal experiments we compared and combined our
strongest methods. In Figure 4 we plotted the average
cumulative DCG@100 as the function of time for our best
models. Surprisingly, the tree based methods strongly
outperform online matrix factorization, while the best popularity
based model overtook the best recency based method a little
bit in the long run. Next, we considered the strongest one,
the tree based popularity without node weight learning, to
improve it by combining it with the best factor model and
recency recommender. We used the SGD based double layer
combination method introduced in [
0 0.4 000.38 1 0.24 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 factor pop recency
popularity popularity + recency popularity + recency + factor 2 learned node weights. We could further improve our results by including the factor model in our recommendation. In Table 2 we collected the overall performance of our best methods and their combinations.
We gave online, location based learning methods for Twitter hashtag recommendation. Since hashtags are not directly bound to a location, may be geographically spread, and vary in popularity at di erent times, we designed methods that 0.206 0.355 0.359 0.374 (4.1% ) 0.381 (6.1% ) exploit the time and location context. Surprisingly, user personalization has little contribution to recommendation quality, hence our best methods apply in the user cold start setting as well. 7.