# Designing weighted and multiplex networks for deep learning user geolocation
in Twitter

Federico M. Funes
Facultad de Ingeniería (UBA)
<EMAIL_ADDRESS>
&José Ignacio Alvarez-Hamelin
Facultad de Ingeniería (UBA)
INTECIN (UBA-CONICET)
<EMAIL_ADDRESS>
Mariano G. Beiró
Facultad de Ingeniería (UBA)
INTECIN (UBA-CONICET)
<EMAIL_ADDRESS>

###### Abstract

Predicting the geographical location of users of social media like Twitter has
found several applications in health surveillance, emergency monitoring,
content personalization, and social studies in general. In this work we
contribute to the research in this area by designing and evaluating new
methods based on the literature of weighted multigraphs combined with state-
of-the-art deep learning techniques. The explored methods depart from a
similar underlying structure (that of an extended mention and/or follower
network) but use different information processing strategies, e.g.,
information diffusion through transductive and inductive algorithms –RGCNs and
GraphSAGE, respectively– and node embeddings with Node2vec+.These graphs are
then combined with attention mechanisms to incorporate the users’ text view
into the models. We assess the performance of each of these methods and
compare them to baseline models in the publicly available Twitter-US dataset;
we also make a new dataset available based on a large Twitter capture in Latin
America. Finally, our work discusses the limitations and validity of the
comparisons among methods in the context of different label definitions and
metrics.

##  1 Introduction

User geolocation in social media platforms has proven a useful resource for
the development of tools for public health surveillance (e.g., monitoring of
general ailments and symptoms (Paul and Dredze,, 2011); forecasting of zika
virus incidence (McGough et al.,, 2017)) and of emergency monitoring systems
(e.g., earthquakes (Sakaki et al.,, 2010); forest fires (De Longueville et
al.,, 2009); floods (Jongman et al.,, 2015)). However, many social media such
as Twitter do not provide wide access to their users’ location information:
i.e., the location field in the Twitter user profile is unstructured and
noisy, and thus difficult to map to a real location. It has also been assessed
that only $\sim 1\%$ of the tweets are geotagged (Cheng et al.,, 2010), making
it challenging to automatically link the large flow of real-time information
available through the platform to specific places.

These limitations motivate the study of location prediction in Twitter based
on the information that is available on the platform, such as the content
published by the users, the hashtags they use, and the users they mention,
reply to, or follow. This task can be enriched by combining techniques from a
variety of areas, such as Natural Language Processing, social networks and
graph mining.

The literature on user geolocation in Twitter has developed several graph-
based and content-based deep learning models in the last years, while it also
proposed the usage of specific metrics as Acc@100, and alternative label
construction techniques as the usage of k-d trees. Many works also explored
the usage of probabilistic classifiers and information-theoretic or statistic
measures for detecting Location Indicative Words (LIW’s), and the remotion of
celebrities from the contact graphs. We make a brief historical account of
these advances in Section 5.

##  2 Data collection and preprocessing

In this work we introduce a dataset collected between January 1, 2019 and
December 10, 2019 in Argentina using the Twitter API, in the context of a
social study Reyero et al., (2021). The users’ set was defined as those
Twitter accounts who were following at least one of the candidates for the
Argentinian presidential elections during 2019, which made for a total of 900
million tweets captured, belonging to 2 million active users. For each user,
all her tweets were collected, unless she had posted more than 3,000 tweets
between two consecutive polls (around 5 days) –something which happened with
extremely low frequency– in which case her tweets were automatically capped by
the API.

From these 900 million tweets, around 1 million were precisely geolocalized by
a set of coordinates in the metadata; this statistic is consistent with
previous findings (e.g., (Cheng et al.,, 2010)). Moreover, 14 million tweets
had metadata that geolocalized them inside a bounding box and mentioned a
specific city chosen by the user when tweeting. We unified and validated the
latter by combining the information with the Geonames gazzetteer
(https://www.geonames.org/), assigning a city in Geonames and a set of precise
coordinates to each geolocated tweet. In this process, around 2 million tweets
had to be discarded.

For each user with at least one geolocated tweet, we defined her ground-truth
location as the city in which most of her geolocated tweets were placed. At
this point, we built the two labelled datasets described in Table 1. The tweet
ids composing each of these datasets are publicly available at
GitHub111https://github.com/fedefunes96/twitter-location-data.git for
hydration. Compared to previous datasets in the literature, our datasets offer
a higher average of tweets per user (around $1,000$), thus providing a large
volume of content data for training.

Our datasets Twitter-ARG-Exact and Twitter-ARG-BBox cover $95$ and $229$
cities accross $14$ and $22$ different countries respectively (with at least
$100$ users in each city), but most of the users ($76.9\%$ and $72.6\%$
respectively) lie inside Argentina.

Dataset | Users | Geolocated tweets | Total tweets
---|---|---|---
Twitter-ARG-Exact | $37,146$ | $625,180$ | $27,574,343$
Twitter-ARG-BBox | $141,209$ | $9,298,954$ | $124,192,146$
Table 1: Basic statistics for the datasets introduced in this work.

###  2.1 Profile location analysis

We analyzed the veracity of the location informed by the users in their
profile. (Cheng et al.,, 2010) had found that only $26\%$ of the users mention
a city in their profile location field. We applied a tokenizer to the location
field and tried to match the words to a city and/or country name in GeoNames.
We found a match with one or more GeoNames cities for $63\%$ of our users who
had some profile location information available. Interestingly, for those with
only one match ($40.9\%$ of the total users), it turned out that $52\%$ of
them were coincident with the ground-truth location obtained from their
georeferenced tweets. All in one, this implies that only $20\%$ of our users
have an unambiguous city in their location profile that matches their
geolocated tweets.

Figure 1 shows the distribution of distances between the profile city and the
ground-truth one extracted from the geolocated tweets, for those users whose
profile city is unambiguous. We observe that $65\%$ of these users have an
error of less than 10km between their profile location and their ground-truth
one. However, $25\%$ of the users have an error larger than $161\text{km}$,
which is the typical relaxed accuracy bound in the location prediction
literature, and thus we consider that the profile location is not accurate
enough for building ground-truth city labels.

Figure 1: Cumulative distribution of the distance between the city in the user
profile and the ground-truth city given by the majority of the user’s
geotagged tweets. These results are in agreement with (Cuevas et al.,, 2014).

###  2.2 Graphs’ construction

Exploiting the mentions contained in the users’ tweets, and the users’
following relationships extracted through the Twitter API, we built user
networks that can help predict their locations.

Frequently, users in our dataset will follow or mention users which are not
part of it. Although we could discard these connections, they might be
relevant for inferring the user’s location: e.g., if two users follow many
people in common, their probability of being geographically close is larger
than for a pair of random users.

Given the set of users in our dataset, $U$, and the extended set of users $E$
obtained by adding users mentioned by those in our dataset, we denote $n=|U|$
and $m=|E|$, and we consider the mention matrix $M\in\mathbf{R}^{n\times n}$
which represents a weighted directed graph with no loops, whose nodes are
those users in $U$. The elements $(m_{ij})$ in this matrix point out the
number of times that user $i$ mentioned user $j$ in her tweets.

Previous works in the literature obtain a collapsed mention matrix that adds
co-mentions to the mention network, by computing $(M+I)\cdot(M+I)^{T}$ (see,
e.g., Rahimi et al., (2015, 2018)).

In this work we propose an alternative solution that combines the connections
in the mention graph $M$ with mention paths that traverse users outside our
user set; this procedure gives a weighted graph as result. We define our
extended mention network as $Y=(M+M^{T})+(X_{M}\cdot X_{M}^{T}-diag(X_{M}\cdot
X_{M}^{T}))$. Here, $X_{M}\in\mathbf{1}^{n\times(m-n)}$ represents the
existence of mentions from users in $U$ to users not in $U$, and thus
corresponds to a bipartite graph. The left term in the formula represents the
symmetrized mention matrix (where each element $a_{ij}$ represents the number
of times that users $i$ and $j$ mention one another), while the right term
represents the number of users external to our dataset that both $i$ and $j$
mention. Thus, the latter extends the mention network by adding co-mentions
going through external users. Following Rahimi et al., (2015) we remove
mentions to popular users before computing our extended network.

The advantages of this extended network with respect to the previous collapsed
networks’ definitions are two-fold: firstly, it can simultaneously weight
mentions and co-mentions in the results –thus profiting of all the mention
information that we collect in tweets– and secondly, that it reduces the
complexity of the obtained network –in Rahimi et al., (2015) and Rahimi et
al., (2018), for example, $n$ nodes mentioning a central node in the
training/test set generate $n\cdot(n-1)$ edges in the collapsed network–. We
illustrate our procedure in Figure 2.

When the follower network is available –as is the case in our dataset– we also
extend it by including connections to users outside our dataset. We define our
extended follower network as $Z=F+(X_{F}\cdot X_{F}^{T}-diag(X_{F}\cdot
X_{F}^{T}))$. Here, $X_{F}\in\mathbf{1}^{n\times(m-n)}$ represents follower
relationships from users in $U$ to users not in $U$. Put into words, this
computation extends the follower network by adding co-follower relationships
to external users (i.e., counting the number of users outside our dataset that
are co-followed by a pair of users $i$ and $j$ in our dataset). We treat the
resulting network as undirected and weighted, and we also remove popular nodes
from the original data before computing $Z$.

In one of our models, RGCN-EXT, both the extended mention graph and the
extended follower graph are combined into a multiplex graph Kivelä et al.,
(2014). In this type of graph, the set of nodes is the same across all layer,
but each layer represents a different relationship type; thus, the network can
couple the information diffusion paths provided by each layer. This could be
further generalized to allow the flow of information across layers as in
general multilayer graphs, or to decompose layers into sublayers (e.g.,
dividing the mention layer into pure mentions and external comentions).

Figure 2: Construction of the extended mention graph. (a) Original mention
graph, including mentions to users not in $U$. (b) Extended mention graph for
the set of users $U$ in our dataset.

###  2.3 Labels construction

In most cases, ground-truth location labels lie on a continuous space given by
the precise latitude and longitude coordinates –e.g., in our Twitter-ARG-Exact
dataset–. In order to discretize these labels, (Roller et al.,, 2012) proposed
the usage of k-d trees Bentley, (1975). This method builds equally-sized
partitions of space which can improve the classifiers’ learning task.

The usage of k-d trees also has some pitfalls: if many users share the same
set of coordinates (i.e., due to precision limitations), it becomes hard to
obtain similarly sized fine-grained partitions; also, in the presence of very
dense metropolitan areas, they might be split into several k-d regions during
partitioning, thus confusing the classifiers, as several leaf nodes will refer
to quite similar users or locations. A discussion of this point can be found
in Han et al., (2012).

For the Twitter-ARG-BBox dataset, we discarded using k-d trees due to the
former reason. For Twitter-ARG-Exact, instead, we evaluated both methods, but
we found that the usage of k-d trees was outperformed by city labels, due to
the large number of samples in the Buenos Aires metropolitan area. In Figure 3
we show the division that a k-d tree would produce on our dataset Twitter-ARG-
Exact.

Figure 3: Division produced by a k-d tree with at least 255 users per leaf
node in our dataset Twitter-ARG-Exact.

For Twitter-US, instead we will show results for both labels types, k-d tree
nodes and city names, for the sake of comparison.

##  3 Models

We propose 3 graph-based geolocation models: (a) RGCN-EXT, a Relational Graph
Convolutional Network that combines mentions and follower relationships as
different layers of a multiplex, (b) GraphSage-EXT, an inductive learning
model based on GraphSAGE and, (c) N2V-EXT, a weighted graph embedding based on
Node2vec+. All these models incorporate tweets’ content information in some
step of their pipelines, as described in the following subsections. We also
incorporate two content-based methods for comparison: BiLSTM-TXT, based on a
bidirectional Long Short-Term Memory (Bi-LSTM), and Trans-TXT, based on a
transformer’s encoder.

###  3.1 RGCN-EXT

Relational Graph Convolutional Networks (R-GCN’s) (Schlichtkrull et al.,,
2018) constitute an extension to GCN’s in which nodes can hold several types
of relationships between them. In network theory, this concept is known as a
multiplex network.

Each neural layer in an R-GCN is computed as:

$h_{i}^{(l+1)}=\sigma\left(\sum_{r\in\mathcal{R}}\sum_{j\in\mathcal{N}_{i}^{r}}\frac{1}{c_{i,r}}W_{r}^{(l)}h_{j}^{(l)}+W_{0}^{(l)}h_{i}^{(l)}+b\right)$

where $\mathcal{R}$ represents the set of relationship types and
$\mathcal{N}_{i}^{r}$ represents the set of neighbors of node $i$ with
relationship type $j$. We use the relationships obtained from the extended,
weighted mention graph, and those of the extended, weighted follower graph
when available.

The normalization constants $c_{i,r}$ can be learned, as well as the $W^{(l)}$
matrices and the bias, $b$. The input vector $h_{i}^{(0)}$ for each node at
the input layer is a feature vector for user $i$ denoting a score for each
label. We use a ReLU activation function ($\sigma$) for the intermediate R-GCN
layers and a softmax activation at the output layer.

The input scores $h_{i}^{(0)}$ are computed by training a transformer’s
encoder over the users’ text view (as explained for the baseline models in
Subsection 3.4) and combining its predictions with those given by Location
Indicative Words (LIW’s). The list of LIW’s in each training set is built
using $\chi^{2}$ tests as proposed in Han et al., (2014).

The full procedure is illustrated in Figure 4; we implemented this model
through the StellarGraph library Data61, (2018), and we denote it as RGCN-EXT
in our results.

Figure 4: Components of the R-GCN model. On the left part of the diagram, the
transformer’s encoder classifier and Location Indicative Words (LIW’s) are
trained to output a probability for each discrete location. On the right, the
multiplex network that combines the extended mentions (black) and extended
followers (green) graphs, over which the four layers of the R-GCN are applied.
The initial feature vectors for this stage are the probability distributions
computed during the first stage.

###  3.2 GraphSAGE-EXT

GraphSAGE (Hamilton et al.,, 2017) is an inductive learning framework capable
of generating embeddings based on each node’s local neighborhood’s features.
During this process, the model learns a set of aggregator functions that can
later be used to make predictions for nodes that were not seen during
training.

We apply this model to the extended, weighted mention graph using the
MeanAggregator proposed in (Hamilton et al.,, 2017).

The aggregator at each node is computed as:

$h_{i}^{(l+1)}=\sigma\left(W^{(l)}\cdot\left(h_{i}^{(l)}\Bigg{\|}\frac{\sum_{j\in\mathcal{N}_{i}}{h_{j}^{(l)}}}{|\mathcal{N}_{i}|}\right)\right).$

The input vectors $h_{i}^{(0)}$ are computed as in the RGCN-EXT model, i.e.,
by scores obtained from training a transformer’s encoder over the users’ text
view combined with the predictions made by Location Indicative Words (LIW’s).

In our GraphSAGE-EXT model, we use a ReLU nonlinearity as the $\sigma$
activation function, with a final softmax layer. We used the StellarGraph
implementation Data61, (2018) of GraphSAGE.

###  3.3 N2V-EXT

Node2vec Grover and Leskovec, (2016) is a dimensionality reduction method that
can learn node representations from graphs such that nodes at shorter
distances in the graph tend to lie closer in the representation space; this is
achieved by using biased random walkers.

In our model N2V-EXT we apply the weighted graph variant of Node2vec,
Node2vec+ Liu et al., (2021), to our extended mention graph and extended
follower graph, using the implementation in Liu and Krishnan, (2021). We
combine the results of a logistic regression classifier for these embeddings
with those of a transformer’s encoder on the users’ text view, by applying a
logistic regression meta-classifier on the concatenation of both outputs.

###  3.4 Baseline content-based methods

We also implement two baseline models that only consider the users’ text view:
BiLSTM-TXT and Trans-TXT.

In the BiLSTM-TXT model we use GloVe Pennington et al., (2014) to extract
embeddings from the content and train a BiLSTM to predict the location
probabilities.

In the Trans-TXT model we train a transformer’s encoder Vaswani et al., (2017)
over the content. The input of this model is formed by the $d$-dimensional
GloVe embeddings of the content generated by the user; the embedding matrix is
also updated during training. A positional encoding is added to the input
embedding and the result, $H\in\mathbf{R}^{n\times d}$, enters the encoder,
which applies a multi-head attention layer and obtains a single representation
$o$ for each user:

$o=\text{MultiHead}(Q,H)=[\text{head}_{1},...,\text{head}_{h}]W^{O},$

where:

$\text{head}_{i}(Q,H)=\text{softmax}\left(\frac{QW_{i}^{Q}(HW_{i}^{K})^{T}}{\sqrt{d_{k}}}\right)HW_{i}^{V}.$

The $W^{Q}_{i}$, $W^{K}_{i}$ and $W^{V}_{i}$ projections in each head $i$ are
learnt during training, as well as the attention context $Q$ and the final
projection $W^{O}$. The output of each head is of size $d_{k}=d/h$, and we use
$h=10$ different heads for Twitter-US and $h=6$ for our dataset. The output of
the attention layer passes through a feed-forward and a softmax layer. These
results are combined with the predictions made by Location Indicative Words
(LIW’s) to train a meta-classifier.

We chose these two types of methods as they had been previously used to
achieve the highest results in the literature (see Huang and Carley, (2019)).

##  4 Results

In Table 2 we show the performance of the three proposed models (RGCN-EXT,
GraphSAGE-EXT and N2V-EXT) and the two baselines, for our introduced dataset.
We report the Acc@100, together with the mean and median errors. From these
results we observe that the addition of network information produced a
consistent improvement in performance, without any significant difference
among the three methods. In this sense, we remark that GraphSAGE-EXT keeps the
advantage of being an inductive algorithm, which makes it faster and more
generalizable with respect to the other methods.

In Tables 3 we show the results for the Twitter-US dataset, either using city
names or k-d tree nodes as labels. We differentiate between the performance
metrics obtained under different types of labels in order to make a fair
comparison. In this sense, the label choice can strongly affect the results,
as we observed for our own dataset. We compare against other methods in the
literature that either use content information, or combine it with the users’
network. We do not compare against methods using metadata (e.g., the
information in the user profile). Under tree-node labels, our results improved
the state-of-the-art ((Miura et al.,, 2017)), while for city labels we
obtained a slightly smaller accuracy as compared to Huang and Carley, (2019),
who proposed a hierarchical classifier –first predicting county, then city–
that combined a Bi-LSTM on text embeddings and a network embedding.

| Twitter-ARG-Exact |  | Twitter-ARG-BBox
---|---|---|---
Method | Acc@100 $\uparrow$ | Mean $\downarrow$ | Median $\downarrow$ |  | Acc@100 $\uparrow$ | Mean $\downarrow$ | Median $\downarrow$
Content-based |  |  |  |  |  |  |
BiLSTM-TXT | $0.750$ | $547.5$ | $5.2$ |  | $0.496$ | $989.9$ | $191.6$
Trans-TXT | $0.764$ | $522.5$ | $4.9$ |  | $0.532$ | $914.7$ | $51.6$
(Graph+content)-based |  |  |  |  |  |  |
RGCN-EXT | $0.829$ | $\mathbf{367.5}$ | $\mathbf{3.8}$ |  | $0.644$ | $\mathbf{690.6}$ | $6.4$
GraphSAGE-EXT | $0.823$ | $369.1$ | $\mathbf{3.8}$ |  | $0.578$ | $798.4$ | $23.2$
N2V-EXT | $\mathbf{0.832}$ | $371.4$ | $3.9$ |  | $\mathbf{0.653}$ | $719.2$ | $\mathbf{0}$
Table 2:  Cross-validated prediction results for the two Latin American datasets proposed here. We evaluate the results for our 3 proposed models combining network and content information, and we compare them with 2 content-based models. |  Twitter-US (city labels) |  |  Twitter-US (node labels)
---|---|---|---
Method | Acc@100 $\uparrow$ | Mean $\downarrow$ | Median $\downarrow$ |  | Acc@100 $\uparrow$ | Mean $\downarrow$ | Median $\downarrow$
Content-based |  |  |  |  |  |  |
BiLSTM-TXT | $0.508$ | $638.9$ | $150.8$ |  | $0.500$ | $603.1$ | $161.7$
Trans-TXT | $0.523$ | $653.6$ | $132.4$ |  | $0.513$ | $589.3$ | $146.7$
(Rahimi et al.,, 2017)-MLP | $-$ | $-$ | $-$ |  | $\mathbf{0.54}$ | $\mathbf{554}$ | $\mathbf{120}$
(Miura et al.,, 2017)-LR | $-$ | $-$ | $-$ |  | $0.527$ | $666.6$ | $121.1$
Huang and Carley, (2019)-HLPNN-Text | $\mathbf{0.571}$ | $\mathbf{516.6}$ | $\mathbf{89.9}$ |  | $-$ | $-$ | $-$
(Graph+content)-based |  |  |  |  |  |  |
RGCN-EXT | $0.666$ | $408.7$ | $43.3$ |  | $\mathbf{0.670}$ | $\mathbf{384.0}$ | $57.2$
GraphSAGE-EXT | $0.643$ | $432.1$ | $50.3$ |  | $0.632$ | $424.3$ | $70.2$
N2V-EXT | $0.690$ | $421.0$ | $35.3$ |  | $\mathbf{0.670}$ | $394.8$ | $57.0$
(Rahimi et al.,, 2017)-MADCEL-W-MLP | $-$ | $-$ | $-$ |  | $0.61$ | $515$ | $77$
(Miura et al.,, 2017)-MADCEL-B-LR | $-$ | $-$ | $-$ |  | $0.601$ | $582.8$ | $66.5$
(Miura et al.,, 2017)-SUB-NN-UNET | $0.615$ | $481.5$ | $65$ |  | $-$ | $-$ | $-$
(Rahimi et al.,, 2018)-MLP-TXT+NET | $-$ | $-$ | $-$ |  | $0.66$ | $420$ | $\mathbf{56}$
Huang and Carley, (2019)-HLPNN-NET | $\mathbf{0.708}$ | $\mathbf{361.5}$ | $\mathbf{31.6}$ |  | $-$ | $-$ | $-$
Table 3:  Cross-validated prediction results for the Twitter-US dataset,
either with GeoNames cities (left) or nodes of a k-d tree (right) as
prediction targets. When using node labels we consider the median of each
region as its representative location, following (Rahimi et al.,, 2015). We
evaluated the results for the 3 graph-based models and compared them against 2
proposed baseline models and others in the literature.

##  5 Related work

One of the first works in the topic of user geolocation is the one by (Cheng
et al.,, 2010), which proposes a model based on the probabilities of using
each word in different cities or states. After refining their model by
identifying Location Indicative Words (LIW’s) and smoothing the distributions,
they reached an score of $51\%$ of the users being assigned to a city closer
than 100 miles to their ground truth location. This relaxed accuracy measure
was later adopted by the literature and referred to as Acc@100 (accuracy at
less than 100 miles).

Due to the uneven geographical distribution of the population in many
countries, predicting the exact location (city, county or state) makes the
classification problem highly unbiased. (Roller et al.,, 2012) was the first
to propose using a grid based on a $k$-$d$ tree instead, in order to produce
balanced classes. They obtained an Acc@100 of 0.346 on the Twitter-US dataset
that they captured.

The selection of Location Indicative Words (LIW’s) was later improved by (Han
et al.,, 2014), by comparing different statistical-based and information
theory-based methods. The authors tested their method on the Twitter-US and
Twitter-WORLD Han et al., (2012) datasets, obtaining an Acc@100 of 0.450 and
0.270 respectively.

(Chi et al.,, 2016) built off (Han et al.,, 2014)’s work by adding city
mentions and the top 10k Twitter @mentions and #hashtags to the LIW’s. Using a
multinomial Naive Bayes model, they obtained an accuracy of 0.225, on the
W-NUT dataset. (Mahmud et al.,, 2014) used an ensemble of statistical and
heuristic classifiers, and followed a hierarchical approach to predict time
zone, state, and then city. They captured a dataset of 1.5M tweets generated
by 9.5k users in 100 cities, and obtained an accuracy of 0.58 at the city
level.

Some later works enhanced the performance by adding some type of network
information into the models, based on the location homophily principle: users
who are closer are more likely to establish connections and interact. (Rahimi
et al.,, 2015, 2017) were the first to incorporate the @mention network into
the prediction model: i.e., they built an undirected network in which two
users $(u_{1},u_{2})$ are connected if one of them mentioned the other. They
discarded mentions of highly popular users (e.g., celebrities) assuming that
they would not be predictive of the follower’s location, and they added edges
by transitivity when the intermediate nodes were not part of the training/test
set. They used a label propagation model based on Modified Adsorption (MAD,
(Talukdar and Crammer,, 2009)), reaching an Acc@100 of 0.61 for Twitter-US and
0.53 for Twitter-WORLD, using a $k$-$d$ tree-based grid.

Other network-based models like (Miura et al.,, 2017) and (Huang and Carley,,
2019) achieved an Acc@100 of 0.70 and 0.72 on Twitter-US respectively, by
using neural network architectures and combining embeddings for the content,
some metadata and the mention graph. (Rahimi et al.,, 2018) also explored the
usage of a Graph Convolutional Network (GCN, (Kipf and Welling,, 2017)) on the
mention graph, obtaining an Acc@100 of 0.62 for Twitter-US y 0.54 for Twitter-
WORLD.

Up to our knowledge, scarce works have used the follower network for location
prediction in Twitter, possibly due to the fact that this type of data is
difficult to obtain. Li et al., (2012) collected this information for $140k$
users obtaining a follower network with 2 million edges; they fitted a
probabilistic generative model obtaining an Acc@100 of $0.62$. (Rodrigues et
al.,, 2016) collected tweets from $12k$ users in Brazil, retrieving the last
200 tweets from each, and building a follower-followee graph with $125k$
edges. They obtained an accuracy of 0.652 when classifying the users into 10
Brazilian cities, using a Markov random field model that combined content and
follower relationships. Finally, we mention that (Hemamalini et al.,, 2018),
proposed an implementation for a location service based on follower
information, but did not analyze any performance metrics or datasets. A
thorough survey of the location prediction problem in Twitter can be found in
(Zheng et al.,, 2018).

##  6 Conclusions

In this work we proposed three graph-based methods for user geolocation that
can propagate users’ generated content through their extended mention and
follower networks using different mechanisms: RGCN-EXT, GraphSAGE-EXT and
N2V-EXT. In particular, the GraphSAGE-EXT model is trained under an inductive
learning setting, thus avoiding retraining when new nodes appear in a real
scenario.

We also proposed a new methodology for extending the mention graph with co-
mentions towards third-users without overloading it, and we introduced the
usage of the follower graph in some of our methods. Our results for the Latin
America dataset suggest that the extended follower network, when available,
can significantly improve the predictions as compared to the state-of-the art
baseline models; i.e., both the RGCN-EXT and N2V-EXT models obtained the best
results in this case. The inclusion of the user text view in the models was
performed through the encoder component of a transformer, this reduces the
execution time as compared to other methods using recurrent neural network
architectures.

On the other hand, in the well-known Twitter-US dataset our results improved
the state of the art when using k-d tree nodes for building labels, while for
city name levels, N2V-EXT stayed slightly below the results obtained by Huang
and Carley, (2019) (significantly improving those obtained by (Miura et al.,,
2017), though).

By using two different georeference fields in the Twitter API’s –coordinates
and bounding boxes– we measured the plausibility of training location models
using bounding boxes, which are much more available that the precise tweet
coordinates. While previous datasets in the literature are based on
coordinates, we built a version of our dataset based on bounding boxes and
reached an Acc@100 accuracy of 0.65. Also, we discussed the importance of
analysing which is the best label construction technique in each case: for our
proposed dataset, a large metropolitan area like Buenos Aires would be split
into different nodes of a k-d tree. So, despite other advantages of the latter
as the possibility of balancing class sizes, in this case it was more
convenient to use cities as levels in order to obtain a smaller error. Also
for the Twitter-US dataset, the best results were in general found at the city
resolution level.

Future lines of research beyond this work include profiting of the multi-layer
design of the R-GCN’s in order to introduce new layers (e.g., separating
mentions from comentions, or incorporating a retweet network) and modeling the
propagation of partially available features (e.g., profile information) with
techniques as the ones proposed by Rossi et al., (2021). Another interesting
extension is to take into account users who are moving, either temporally
(e.g., travelling) or due to migration or relocation. These factors could be
taken into account by using embedding or diffusion methods based on temporal
graphs.

## Acknowledgements

The authors acknowledge the financial support of a PICT 2019 grant from the
Agencia Nacional de Promoción Científica y Tecnológica (PICT 2019-01031).

## References

  * Bentley, (1975) Bentley, J. L. (1975).  Multidimensional binary search trees used for associative searching.  Communications of the ACM, 18(9):509–517.
  * Cheng et al., (2010) Cheng, Z., Caverlee, J., and Lee, K. (2010).  You are where you tweet: a content-based approach to geo-locating twitter users.  In Proceedings of the 19th ACM international conference on Information and knowledge management, pages 759–768.
  * Chi et al., (2016) Chi, L., Lim, K. H., Alam, N., and Butler, C. J. (2016).  Geolocation prediction in twitter using location indicative words and textual features.  In Proceedings of the 2nd Workshop on Noisy User-generated Text (WNUT), pages 227–234.
  * Cuevas et al., (2014) Cuevas, R., Gonzalez, R., Cuevas, A., and Guerrero, C. (2014).  Understanding the locality effect in twitter: measurement and analysis.  Personal and Ubiquitous Computing, 18(2):397–411.
  * Data61, (2018) Data61, C. (2018).  Stellargraph machine learning library.  https://github.com/stellargraph/stellargraph.
  * De Longueville et al., (2009) De Longueville, B., Smith, R. S., and Luraschi, G. (2009).  " omg, from here, i can see the flames!" a use case of mining location based social networks to acquire spatio-temporal data on forest fires.  In Proceedings of the 2009 international workshop on location based social networks, pages 73–80.
  * Grover and Leskovec, (2016) Grover, A. and Leskovec, J. (2016).  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864.
  * Hamilton et al., (2017) Hamilton, W. L., Ying, R., and Leskovec, J. (2017).  Inductive representation learning on large graphs.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025–1035.
  * Han et al., (2012) Han, B., Cook, P., and Baldwin, T. (2012).  Geolocation prediction in social media data by finding location indicative words.  In Proceedings of COLING 2012, pages 1045–1062.
  * Han et al., (2014) Han, B., Cook, P., and Baldwin, T. (2014).  Text-based twitter user geolocation prediction.  Journal of Artificial Intelligence Research, 49:451–500.
  * Hemamalini et al., (2018) Hemamalini, S., Kannan, K., and Pradeepa, S. (2018).  Location prediction of twitter user based on friends and followers.  International Journal of Pure and Applied Mathematics, 118(18):2817–2824.
  * Huang and Carley, (2019) Huang, B. and Carley, K. (2019).  A hierarchical location prediction neural network for Twitter user geolocation.  In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 4732–4742, Hong Kong, China. Association for Computational Linguistics.
  * Jongman et al., (2015) Jongman, B., Wagemaker, J., Romero, B. R., and De Perez, E. C. (2015).  Early flood detection for rapid humanitarian response: harnessing near real-time satellite and twitter signals.  ISPRS International Journal of Geo-Information, 4(4):2246–2266.
  * Kipf and Welling, (2017) Kipf, T. N. and Welling, M. (2017).  Semi-supervised classification with graph convolutional networks.  In International Conference on Learning Representations (ICLR).
  * Kivelä et al., (2014) Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., and Porter, M. A. (2014).  Multilayer networks.  Journal of complex networks, 2(3):203–271.
  * Li et al., (2012) Li, R., Wang, S., and Chang, K. C.-C. (2012).  Multiple location profiling for users and relationships from social network and content.  arXiv preprint arXiv:1208.0288.
  * Liu et al., (2021) Liu, R., Hirn, M., and Krishnan, A. (2021).  Accurately modeling biased random walks on weighted graphs using node2vec+.  arXiv preprint arXiv:2109.08031.
  * Liu and Krishnan, (2021) Liu, R. and Krishnan, A. (2021).  Pecanpy: a fast, efficient and parallelized python implementation of node2vec.  Bioinformatics, 37(19):3377–3379.
  * Mahmud et al., (2014) Mahmud, J., Nichols, J., and Drews, C. (2014).  Home location identification of twitter users.  ACM Transactions on Intelligent Systems and Technology (TIST), 5(3):1–21.
  * McGough et al., (2017) McGough, S. F., Brownstein, J. S., Hawkins, J. B., and Santillana, M. (2017).  Forecasting zika incidence in the 2016 latin america outbreak combining traditional disease surveillance with search, social media, and news report data.  PLoS neglected tropical diseases, 11(1):e0005295.
  * Miura et al., (2017) Miura, Y., Taniguchi, M., Taniguchi, T., and Ohkuma, T. (2017).  Unifying text, metadata, and user network representations with a neural network for geolocation prediction.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1260–1272.
  * Paul and Dredze, (2011) Paul, M. J. and Dredze, M. (2011).  You are what you tweet: Analyzing twitter for public health.  In Fifth international AAAI conference on weblogs and social media.
  * Pennington et al., (2014) Pennington, J., Socher, R., and Manning, C. D. (2014).  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543.
  * Rahimi et al., (2015) Rahimi, A., Cohn, T., and Baldwin, T. (2015).  Twitter user geolocation using a unified text and network prediction model.  In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 630–636, Beijing, China. Association for Computational Linguistics.
  * Rahimi et al., (2017) Rahimi, A., Cohn, T., and Baldwin, T. (2017).  A neural model for user geolocation and lexical dialectology.  In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), Vancouver, Canada. Association for Computational Linguistics.
  * Rahimi et al., (2018) Rahimi, A., Cohn, T., and Baldwin, T. (2018).  Semi-supervised user geolocation via graph convolutional networks.  In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2009–2019. Association for Computational Linguistics.
  * Reyero et al., (2021) Reyero, T. M., Beiró, M. G., Alvarez-Hamelin, J. I., Hernández, L., and Kotzinos, D. (2021).  Evolution of the political opinion landscape during electoral periods.  EPJ Data Science, 10(1):31.
  * Rodrigues et al., (2016) Rodrigues, E., Assunção, R., Pappa, G. L., Renno, D., and Meira Jr, W. (2016).  Exploring multiple evidence to infer users’ location in twitter.  Neurocomputing, 171:30–38.
  * Roller et al., (2012) Roller, S., Speriosu, M., Rallapalli, S., Wing, B., and Baldridge, J. (2012).  Supervised text-based geolocation using language models on an adaptive grid.  In Proceedings of the 2012 joint conference on empirical methods in natural language processing and computational natural language learning, pages 1500–1510.
  * Rossi et al., (2021) Rossi, E., Kenlay, H., Gorinova, M. I., Chamberlain, B. P., Dong, X., and Bronstein, M. (2021).  On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features.
  * Sakaki et al., (2010) Sakaki, T., Okazaki, M., and Matsuo, Y. (2010).  Earthquake shakes twitter users: real-time event detection by social sensors.  In Proceedings of the 19th international conference on World wide web, pages 851–860.
  * Schlichtkrull et al., (2018) Schlichtkrull, M., Kipf, T. N., Bloem, P., Van Den Berg, R., Titov, I., and Welling, M. (2018).  Modeling relational data with graph convolutional networks.  In European semantic web conference, pages 593–607. Springer.
  * Talukdar and Crammer, (2009) Talukdar, P. P. and Crammer, K. (2009).  New regularized algorithms for transductive learning.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 442–457. Springer.
  * Vaswani et al., (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017).  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008.
  * Zheng et al., (2018) Zheng, X., Han, J., and Sun, A. (2018).  A survey of location prediction on twitter.  IEEE Transactions on Knowledge and Data Engineering, 30(9):1652–1671.