Identifying user geolocation in online social networks is an essential task in many location-based applications. Existing methods rely on the similarity of text and network structure, however, they suffer from a lack of interpretability on the corresponding results, which is crucial for understanding model behavior. In this work, we adopt influence functions to interpret the behavior of GNN-based models by identifying the importance of training users when predicting the locations of the testing users. This methodology helps with providing meaningful explanations on prediction results. Furthermore, it also initiates an attempt to uncover the so-called black-box GNN-based models by investigating the effect of individual nodes. Identifying geographic locations of users in online social networks (OSN) has become a key Internet service for many downstream applications, including location-based targeted advertising, emergency location identification, political election campaign, local event/place recommendation, natural disaster response, and remediation, etc. (Zheng et al., 2018). As such, the problem of user geolocation (UG) has received a great deal of research attention in the past decade (Han et al., 2012; Do et al., 2017; Miura et al., 2017; Rahimi et al., 2018; Bakerman et al., 2018). Earlier efforts (Amitay et al., 2004; Wing and Baldridge, 2011; Han et al., 2012; Roller et al., 2012; Ahmed et al., 2013; Han et al., 2014; Chong and Lim, 2017) mainly focused on extracting indicative information from user-posted contents. These approaches rely on informative words that can link users to their specific locations via various natural language processing techniques such as topic modeling and other statistical models. More recently, researchers aimed at incorporating multi-aspect information, especially the user men-tion/interaction network to boost the performance of geolocation identification (Rahimi et al., 2015; Do et al., 2017; Rahimi et al., 2017, 2018; Hamouni et al., 2019). For example, (Rahimi et al., 2018; Wu et al., 2019) employ Graph Convolutional Networks (GCNs) (Kipf and Welling, 2017) or simplified GCN (Wu et al., 2019) to learn network structures for user geolocation. In addition, graph representation-based methods (Tang et al., 2015; Grover and Leskovec, 2016; Kipf and Welling, 2017; Hamilton et al., 2017; Qiu et al., 2018) have also been widely used for user geolocation (Do et al., 2017; Miura et al., 2017; Rahimi et al., 2018; Hamouni et al., 2019; Huang and Carley, 2019). However, the existing methods lack model transparency and fail to provide meaningful explanations regarding the model behavior and prediction results, which prevents them from safety-critical applications. For example, when locating an emergency for a specific region, it would be more meaningful to explain why such prediction is made, rather than simply presenting numerical ranking values. To address such limitations, we propose a general framework to explain the behavior of user geolocation models and the prediction results, by utilizing the influence function (Hampel et al., 2011; Koh and Liang, 2017) to quantify the impact of in-network users on the predicted outcome. The main assumption is that the prediction results from a trained geolocation model are typically affected by the knowledge learned from training data (i.e., all in-network users and their associated attributes). We demonstrate that the user geolocation (espe-cially) for the network-based methods, is largely dominated by the geographical locations of the 1-hop neighboring nodes. This finding, on the one hand, enables demystification of the model behavior and quantitative measuring of the influence of individual users (both 1-hop and high-order proximity nodes); and on the other hand, provides interpretation on the predicted locations for downstream applications/decision makers  which, in turn, points out a direction to further improve the model. The User geolocation problem is defined as predicting the user's home location (Zheng et al., 2018). Since each location is described by a (lon-gitude, latitude) pair, the task can be converted into a typical classification problem where the labels/categories are region ids obtained through some space-partitioning methods, such as k -d trees, that divides the surface of the earth into closed and non-overlapping regions. Each user is associated with one (and only one) region-label that she/he belongs to. We use one-hot encoding to denote each label y  R 1  c , where c is the number of regions. The user geolocation task thus becomes one of identifying the geographical locations, given the user tweet contents X and the mention network G . Graph Neural Networks (GNNs) (Bruna et al., 2014; Defferrard et al., 2016; Kipf and Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018; Ying et al., 2018; Xu et al., 2019; You et al., 2019) are powerful tools of representation learning for graph data, which has received increasing attention over the past several years (Zhou et al., 2018; Wu et al., 2020). The main idea is that, given a network G = ( V , E ) with attributes x v  X for every node v ( v  V ), a general GNN is to learn a vector representation of node v by: x ( k ) v = f  2 M (cid:16) x ( k  1) v , f  1 A (cid:0)(cid:8) x ( k  1) u (cid:12)(cid:12) u  N ( v ) (cid:9)(cid:1)(cid:17) , where  1 and  2 are trainable parameters, and N ( v ) indicates the neighboring nodes of node v . Specifi-cally, f  1 A aggregates information from neighbors, f  2 M merges the node representations from step k  1 with the computed neighborhood information. Both f  1 A and f  2 M can be arbitrary differentiable, permutation-invariant functions (e.g., neural networks) (Rahimi et al., 2018; Wu et al., 2019). Previous works (Rahimi et al., 2015; Do et al., 2017; Hamouni et al., 2019) typically leverage graph embedding methods (Grover and Leskovec, 2016; Kipf and Welling, 2017; Hamilton et al., 2017; Wu et al., 2019) for user representation learning. In spite of the superior performance, GNNs (including those used for user geolocation) (Rahimi et al., 2018; Wu et al., 2019) model the process of learning and prediction in a black-box manner and, consequently, are limited in terms of interpretability. Therefore, it is important to understand how the model learns the data and why a particular prediction is made. To demystify the geolocation models, we intend to uncover and explain the training process and prediction outcomes. There has been a growing interest to explain the model behavior and the predicted outcomes in the area of neural networks. In particular, an influence function (Cook and Weisberg, 1980; Hampel et al., 2011) is used to estimate the effect of individual training sample and interpret the results made by a specific model. While providing an elegant post-training interpretation, computationally-prohibitive cost of repeatedly retraining the model is avoided, spurring wide uses in a range of applications, including image classification (Koh and Liang, 2017), group effect (Koh et al., 2019), recommendation (Cheng et al., 2019), etc. However, whether influence functions can be applied to GNN-based models remained unclear. We take a step towards bridging this gap by tracing the geolocation results from the GNN-based models back to the important nodes in the mention network. Specifically, let z 1 , . . . , z m denote the m training samples (nodes in the mention network G ), where each z i = ( x i , y i ) is an attribute vector of i -th node and its label. Removing one sample z from the training set can change the model optimal parameters from   to   z , where   and   z is the set of optimal parameters with and without the sample z , respectively. And   z can be obtained by:   z def = arg min    (cid:80) z i (cid:54) = z (cid:96) ( z i ,  ) , where (cid:96) ( z i ,  ) is the loss of sample z i . To estimate the influence of every removed training sample z and avoid retraining the model, Koh et al. (Koh and Liang, 2017) use an influence function strategy to effi-ciently approximate this behavior. The basic idea is to compute the change of optimal parameters if z was upweighted by some small (cid:15) , which gives the new parameters:   (cid:15),z def = arg min    1 m m (cid:88) i =1 (cid:96) ( z i ,  ) + (cid:15)(cid:96) ( z,  ) , (1) where the influence of upweighting z on the parameters   is given by: I up ,  ( z ) def =   (cid:15),z (cid:15) (cid:12)(cid:12)(cid:12)(cid:12) (cid:15) =0 =  H  1   (cid:53)  (cid:96) ( z,   ) , (2) H   def = 1 m (cid:80) mi =1 (cid:53) 2  (cid:96) ( z i ,   ) is the Hessian matrix, and Eq. (2) shows that removing z is the same as upweighting it by (cid:15) =  1 m . Thus, we can linearly approximate the parameter change of removing z as   z      1 m I up ,  ( z ) without retraining the model. The influence of upweighting a training node z on the loss for a testing node z test can then be calculated according to the chain rule: I up , loss ( z, z test ) def = (cid:96) ( z test ,   (cid:15),z ) (cid:15) (cid:12)(cid:12)(cid:12)(cid:12) (cid:15) =0 = (cid:53)  (cid:96) ( z test ,   ) (cid:124)   (cid:15),z (cid:15) (cid:12)(cid:12)(cid:12)(cid:12) (cid:15) =0 =  (cid:53)  (cid:96) ( z test ,   ) (cid:124) H  1   (cid:53)  (cid:96) ( z,   ) . To speed up the computation, we use implicit Hessian-vector products (HVPs) to approximate w test def = H  1   (cid:53)  (cid:96) ( z test ,   ) , and Eq. (3) can be rewritten as I up , loss ( z, z test ) =  w test (cid:53)  (cid:96) ( z,   ) . Since the Hessian H   is positive semi-definite by assumption, we have: w test  arg min  (cid:8) 1 2  (cid:124) H     (cid:53)  (cid:96) ( z test ,   ) (cid:124)  (cid:9) , where the exact solution  can be obtained with conjugate gradients requiring only the evaluation of H    instead of explicitly computing H  1   . We refer the reader to (Koh and Liang, 2017) for more detailed explanations on this topic, where the application of influence functions in computer vision is investigated. Note that the above method does not depend on a specific GNN implementation, i.e., it can be easily adapted to any GNN models. We investigate the interpretability of two user geolocation models: (1) SGC (Wu et al., 2019), which is a simplified GCN that removes the non-linearity in each layer of GCN and has achieved state-of-the-art performance for user geolocation. (2) A simple MLP model which combines the embedding of user-posted content and the node embedding for UG prediction. Here, we use doc2vec for user content embedding. For SGC, we use the published code 1 , where the tweet content is fed into a GNN as the node attribute. For MLP, we use node2vec to generate node representations. Note that we follow the evaluation metrics used by previous works. We used two real-world Twitter datasets for evaluation: GeoText (Eisenstein et al., 2010) and Twitter-US (Roller et al., 2012). Their descriptive statistics are shown in Table 1. Dataset # Train # Val # Test # Label GeoText 5,685 1,895 1,895 129 Twitter-US 429,200 10,000 10,000 256 Table 1: Descriptive statistics of datasets. Before explaining the results, we compare the performance of SGC, MLP and GCN (Rahimi et al., 2018) 2 models as shown in Table 2. First of all, all three models can achieve similar performance results. While SGC performs slightly better, its superiority is not obvious compared to other GNN-based models and even the simple MLP model. This result implies that the improvement of UG results is limited even with the most advanced GNN-based models, at least on the two widely used benchmark datasets. Next, we turn to explain the results made by the SGC and MLP models. We omit other GCN-based models due to the limited space. Influence of n -hop neighbors. For each test node, we average the influence value of the n -hop ( n = 1 , 2 , 3 ) training neighbors in the mention network. As Figure 1 illustrates, 1-hop nodes usually have more positive influence on the test sample, while in contrast, the influence of 2-hop and 3-hop neighbors is relatively smaller. This is an intuitive interpretation of the geolocation results, but it ver-ifies the effect of network-view modeling in user geolocation (Rahimi et al., 2015; Do et al., 2017; 1 https://github.com/Tiiiger/SGC 2 We used the implementation of GCN for geolocation provided by https://github.com/afshinrahimi/geographconv 0 600 1200 1800 Index of testing nodes 0.0 0.1 0.2 A v g . Hamouni et al., 2019), i.e., the immediate neighbors can largely contribute to the user geolocation. By comparing the results between SGC and MLP, we have the following observations. First, SGC is more sensitive to training samples, e.g., the influence value of SGC (y-axis) is far smaller than MLP. This is caused by the difference of fundamental training paradigms between SGC and MLP, i.e., SGC is a GNN-based model which considers the tweet content as attributes, but MLP embeds the tweet content and nodes independently. Therefore, a small change (removing a node) in SGC may incur significant influence on testing results. This result also implies that GNN-based models are more vulnerable to adversarial attacks, which is problematic for all existing GNN-based models as observed in recent works (Zugner and Gunnemann, 2019a,b). Second, for some nodes (indexed by x-axis) the average influence of their n -hop neighbors is negative, i.e., those data points that value are below 0. An interesting phenomena is that there are more such nodes for MLP as compared to SGC. We hypothesize that these nodes are the main reason of SGC MLP 0 20 40 60 A cc @ 161 PositiveOverallNegative the inferior performance of MLP. To verify this assumption, we scrutinize the prediction results of these nodes. As shown in Figure 2(a), where the accuracy of predicting these nodes in MLP is significantly lower than in SGC, which confirms our hypothesis and gives promising explanations on the classification error, i.e., the low classification accuracy might be caused by those nodes whose n -hop influence are negative (cf. Figure 1). Influence of geographic distance. We also quantify the influence of geographic distance between training samples and testing samples. As Figure 2(b) shows, the close training data (e.g., less than 10KM) have higher impacts on locating users. However, the influence significantly drops with distance greater than 10KM. In another word, geographically far nodes (beyond a threshold) may Influence of regions. It is of interest to investigate the effect of regions on the user geolocation. The most important assumption in user geolocation is that geographically similar users should be topologically proximal. To quantify this assumption, for each region, we treat the training samples within this region as in-region nodes, and those out of it as out-region nodes. By calculating the mean influence of in-region and out-region samples for each test user, we can measure the influence of different regions. As Figure 3 shows, in-region samples (positive samples) have more significantly positive influence than out-region samples (nega-tive samples). This result not only consolidates the motivation of most multi-view user geolocation models, but also suggests an important direction for improving the geolocation performance, i.e., paying more attention to the in-region samples. In this work, we presented a framework for explaining the GNN-based models by extending the influence function to estimate the effect of samples in graph data. The experiments conducted on a specific task  user geolocation  provided intuitive explanations and enabled quantification of the influence of individual training samples. Some interesting observations include the effects of regions and the sensitivity of GNN-based models, which open potentials for further improvements that we plan to address in our future work. This work was supported by the National Natural Science of China under Grant No.61602097 and No.61472064, and NSF grant CNS 1646107.
abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain objective abstain abstain abstain abstain method abstain other other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain other abstain abstain other abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain result abstain abstain abstain abstain other abstain result abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain objective abstain abstain other