There have been many efforts to estimate the political orientation of citizens and political actors. With the burst of online social media use in the last two decades, this topic has undergone major changes. Many researchers and political campaigns have attempted to measure and estimate the political orientation of online social media users. In this paper, we use a combination of metric learning algorithms and label propagation methods to estimate the political orientation of Twitter users. We argue that the metric learning algorithm dramatically increases the accuracy of our model by accentuating the effect of homophilic networks. Homophilic networks are user clusters formed due to cognitive motivational processes linked with cognitive biases. We apply our method to a sample of Twitter users in Germany's six-party political sphere. Our method obtains a significant accuracy of 62% using only 40 observations of training data for each political party.
Measuring and estimating the political orientation of normal
citizens and political actors has always been a relevant
question. The answer to this question is essential for electoral
campaigns
The first quality is related to the number and type of
inputs in the algorithm: What type of features are considered
while estimating the latent political orientation of the users?
The second quality is if the method is designed to estimate
the political orientation of a specific group of political
actors
In this work, we use a combination of metric learning
algorithms and label propagation methods to estimate the
political orientation of Twitter users. Our method has three
distinguishing features. First, the method requires a minimal
number of features as training data because it exploits the
homophilic structure of social networks
We use a combination of metric learning algorithms with label propagation methods to estimate the political orientation of Twitter users. The goal of label propagation algorithms is to estimate the labels of a large set of unlabeled observations from the small set of labeled observations.
Suppose there are l labeled observations (x1; y1); : : : ; (xl; yl) and u unlabeled observations such that l < u, and n = l + u. Consider a connected graph G = (V; E) with nodes L = f1; : : : ; lg and U = fl + 1; : : : ; l + ug corresponding, respectively, to the labeled or training observations and unlabeled or test observations. A label propagation algorithm propagates the labels for the set U , based on the distances between its observations to the observations in L. Within the label propagation algorithm, the labels of the vertices in set L would be fixed, but the labels of the set U would be estimated based on a function of their distance to set L.
Let n be the total number of Twitter users we have including l users for whom we already know their political orientation and u users for whom we want to estimate their political orientation. We use only the structure of the friends’ network to estimate the political orientations. Let F be the set of friends of all n users with size m. Therefore, we can create the binary matrix A with dimension n m, which would represent the friends of each of the n users. Before constructing graph G from matrix A, we transform matrix A by using a proper metric learning algorithm.
The reason for transforming matrix A is that we believe
there are hidden information within the network structure,
which we could use to increase the estimation accuracy. By
contrast with the rational choice theory, the human
judgment is influenced by various cognitive biases, prior
judgments, environmental features, and stimulus-feedback loops
A brief description of the steps of our method is as follows. First, we acquire matrix A, which includes the labeled observations and the unlabeled observations as rows. Second, we learn the optimized distance or metric function that guarantees higher accuracy within the labeled observations by exhausting the special structure of homophilic networks. We transform matrix A by using the learned metric to construct graph G. Finally, we apply the learning method or the label propagation algorithm.
The accuracy of each learning algorithm is a function of the
distance function or the metric used to compute the distance
between the observations. The metric learning algorithm we
use is based on the following: a precise k-nearest neighbors
classification will correctly classify a labeled observation if
its k-nearest neighbors share the same label. The algorithm
then attempts to increase the number of labeled observations
with this property by learning a linear transformation of the
input space that proceeds the final learning method. The
linear transformation of LMNN is derived by maximizing a loss
function with two terms. The first term minimizes the large
distances between observations within class, and the second
term maximizes the distances between the observation
between the classes
In general, metric learning algorithms estimate the
positive semidefinite transformation matrix M such that the
distance between two observations, xi and xj , is derived by the
Mahalanobis distance,
dM(xi; xj ) =
q
(xi
xj )T M(xi
xj )
which follows certain features. If we replace M with
the identity matrix, the resulting metric would be Euclidean
metric. LMNN learns a linear transformation matrix M,
such that the training or labeled observation satisfies the
following items
Each labeled observation should share the same label as its k- nearest neighbors. This is achieved by introducing a loss function that penalizes large distances between observations belonging to the same class,
X j i pull(L) = jjL(xi xj )jj2 where j i indicates that j is an observation that we desire to be close to i, and L is the function representing the transformation by matrix M.
The labeled observations with different labels should be significantly separated. This separation is achieved by introducing a loss function that penalizes small distances between observations belonging to different classes, push(L) =
X
X[1+jjL(xi xj )jj2 jjL(xi xl)jj2] i;j i l where the inner sum iterates over all the observations with a different class to i, and l invades the perimeter of i and j plus unit margin. In other words, the observation l satisfies jjL(xi xl)jj2 jjL(xi xj )jj2 + 1 The final loss function is a weighted combination of the two defined components, (L) = (1 ) pull(L) + push(L) Although the general loss function above is not convex, by limiting the solution space to positive semidefinite matrices, the loss function will be a convex function.
The solution to the minimization of the loss function, given the labeled subset of A, is the desirable matrix M. We transform matrix A to obtain matrix AM by
We construct graph G using the AM of size n m by using the nearest neighbor graph method. In other words, using n rows of AM, we define n vertices of G and then define edges between each vertex and its kG nearest neighbors by using the Euclidean distance function.
The goal of applying a label propagation algorithm to a
graph is to estimate the labels of unlabeled vertices by using
their connections to the few labeled vertices. This problem
is usually formulated as an iterative process within which
the labels are gradually diffused over the matrix, such that
the state of the graph would converge to a stationary state.
This iterative process might have an analytical solution that
would be more efficient than applying the algorithm
iteratively
The algorithm we use for label propagation is based on Zhu, Ghahramani, and Lafferty. Let the simple graph G = (V; E) and the set of the labeled and unlabeled vertices, L and U , be as defined. The goal is to compute the real-valued function f : V ! R on the simple graph G. f must assign the same given labels for the set L or fl(i) yi for i 2 l. To estimate the function f they defined the energy function E(f ) = 1 X wi;j (f (i) 2 i;j f (j))2 and the Gaussian field p (f ) = e E(f) Z where is an inverse temperature function and Z = Rf exp( E(f )) which normalizes over all functions constrained to the constraint fl(i) yi on the labeled vertices. Then, they demonstrate the result of the minimization f = arg min E(f )
f which is a harmonic function that satisfies the constraint fl(i) yi on the labeled vertices. The harmonic property implies that the value of f at each unlabeled vertex is the average of f at neighboring vertices. Therefore, the estimated labels would be a function of the similarity of all neighboring vertices.
The estimated f has an interpretation within the framework of random walks. The estimated f (i) for an unlabeled vertex i 2 U would be a vector of size equal to number of possible classes. The jth element of f (i) would be the probability that a particle that started at vertex i would first hit a vertex with class j. Therefore, the resulting algorithm can be used to estimate the political orientation of a user in a multidimensional latent space.
We require two sets of data for training and testing. We acquire both sets from the public Twitter API. In the first step, we obtained the list of all the members of the main and local German parliaments who are available on Twitter. This list contains 623 Twitter users from one of the six parties CDU/CSU, SPD, Gru¨ne, Linke, FDP and AfD.
From a database of German political Tweets, we obtained a list of 400,000 random Twitter users. We downloaded the list of all their friends and their last 4,000 Tweets by using the public API. We counted how many times each user retweeted the Tweets of members of each of the political parties we acquired in the first step. If a user has retweeted a minimum of five Tweets from members of party j but no retweets from other parties, we tag this user as a user with a political orientation to party j. From the 400,000 initial users, we could label 8,146 based on the mentioned heuristic.
To reduce the complexity of the computations, we reduced the sample size to 50,000 from 400,000. Thus, we created matrix A using 50,000 random users including all of the 8,146 labeled users. Matrix A has at this step 50,000 rows as users, which we want to use for our training and test set, and 7,194,153 columns as the friends. To further reduce the complexity of the computations, we removed the friends who are friends of less than 0.01% of the users. The final matrix A has the dimension 50,000 552,136.
We confirm that our test data has a minor bias in the sense that we already know our test data includes users who have engaged in some type of political activity. This assumption is because these users are randomly chosen from a database of German political Tweets. On the other side, this bias is mildly mitigated in two steps. First, matrix A is created by a list of friends of all 50,000 random users and not only the friends of the labeled 8,146 users. Thus, the feature sets are from a bigger set of observations. Second, we added some randomness by removing some columns of matrix A in the final step.
We resampled 60 users per political party out of the 8,146 labeled users of A. We learned matrix M based on the 240 users. Next, we transformed the whole matrix A using M by applying
M Using the transformed AM, we made a 10-nearest neighbors graph using a Euclidean distance function to make graph G. Finally, we applied the label propagation algorithm on G that has 50,000 vertices, out of which, the labels of 240 are introduced to the algorithm. The labels of the other 49,760 are estimated using the label propagation algorithm.
We performed the resampling and the computations 10 times to make sure the results are robust. For each trial, we applied a random forest classifier on the 240 training data as a random forest label propagation random forest label propagation AM (transformed) benchmark result. We also applied the random forest classifier and the label propagation method on A directly to improve our understanding regarding how much the LM N N metric learning method contributes to the accuracy of the results. Table 1 shows the average accuracy of the estimations on the remaining 8,146-240=7,906 labeled users with a known political orientation.
Referring to Table 1, we observe that the transformation increases the accuracy of the random forest classifier and the label propagation algorithm. We also observe that the combination of the metric learning algorithm and the label propagation method results to a much higher accuracy of estimation.
In this paper, we proposed a new method to estimate the political orientation of Twitter users. Our method has many distinguishing features: The method requires few training observations, requires few learning features, is based on a multidimensional latent space, and is easily expendable to new users even if they have zero political activity on Twitter.
Based on Table 1, the high accuracy of the model is due to the transformation of the initial matrix using the function learned by the LMNN algorithm. The cost function of the LMNN algorithm has two parts. One part pulls the observations of the same class closer to each other, and the other part pushes the observations of different classes far apart. Additionally, since the LMNN algorithm is based on optimizing a k-nearest neighbor model on the training observations, the trained matrix M transforms the observations based on their relation to other observations in their vicinity and not the whole dataset. These characteristics have crucial implications reagarding the accuracy of our estimation.
As aforementioned, the initial matrix, A, has a special structural feature because it represents a homophilic social network, which means that users with similar political identity are assumed to demonstrate similar behavior on Twitter. Therefore, we expected that users with similar political identity would follow similar politicians, similar celebrities, similar sportsmen, and so forth.
When we apply the LMNN algorithm to this
homophilic network, we accentuate the extant distinctive
features formed due to the existing cognitive biases in
selfcategorization and group formation
The matrix M learns different combinations of features that help distinguish normal Twitter users based on their political orientation. The matrix M also allows different combination of features for each class because it is based on a k-nearest neighbor algorithm that considers a bounded proximity of the users. Our model detects the political orientation of users with high accuracy, and by far outperforms other algorithms that have been applied to this task.
Due to the use of label propagation algorithm, this model can be later applied on any new user e to estimate her or his political orientation, as long as e is connected to the graph G. More generally, to predict the political orientation of user e, we must find a new set of users including e, forming a small graph g connected to the initial graph G.
This study provides valuable insights into the study of user behavior on online social networks. This study illustrates, that using mathematical algorithms that exhaust properties of social theories, we can improve the performance of models explaining human behavior. Furthermore, this study contradicts the general claim that a huge amount of data is required to make accurate predictions on social and political behavior. Finally, our method provides a novel technique to assign political partisanship, by having as input only the network of interpersonal connections.
Zhu, X.; Ghahramani, Z.; and Lafferty, J. D. 2003. Semisupervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), 912–919.