# Analyzing Wikipedia Membership Dataset and Predicting Unconnected Nodes in
the Signed Networks

Zhihao Wu
Taoran Li
Ray Roman
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>University of
California  Los Angeles

###### Abstract

In the age of digital interaction, person-to-person relationships existing on
social media may be different from the very same interactions that exist
offline. Examining potential or spurious relationships between members in a
social network is a fertile area of research for computer scientists—here we
examine how relationships can be predicted between two unconnected people in a
social network by using area under Precison-Recall curve and ROC. Modeling the
social network as a signed graph, we compare Triadic model,Latent Information
model and Sentiment model and use them to predict peer to peer interactions,
first using a plain signed network, and second using a signed network with
comments as context. We see that our models are much better than random model
and could complement each other in different cases.

###### keywords:

Social Networks; Signed Networks; Link Predication; Probabilistic Soft Logic;
Balance theory; Setimental Analysis

<ccs2012> <concept>
<concept_id>10003033.10003106.10003114.10011730</concept_id>
<concept_desc>Networks Online social networks</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003120.10003130.10003134.10003293</concept_id>
<concept_desc>Human-centered computing Social network analysis</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>

[500]Networks Online social networks [300]Human-centered computing Social
network analysis

##  1 Introduction

As engineering teams include more and more interactive features on social
media, it sculpts the detailed interpersonal interactions between two people
in cyberspace. Several social networks such as Facebook, Wikipedia, or Stack
Overflow allow users to tacitly review, critique, or applaud their peers with
the use of “Likes", “Upvotes", “Recommendations", or some other buzzword.
Interacting with others can be interpreted as binary, such as a “like" or
“dislike"; they can be on some sort of scale, like an Amazon product rating
from one to ten stars; or it can include extensive comments. The nature of
these links can be considered positive (“Great contribution!") or negative
(“This comment appears to be irrelevant."). Evaluations such as these form the
cornerstone of signed networks, where user–user interactions can be quantified
in one of these ways. Deviating from the weighted directed graph paradigm,
relationships are now represented in a multidimensional fashion [11].

Predicting the interactions between any two users in a social network need not
remain a task rooted firmly in graph theory; the rich information contained in
these interactions—namely the comments—provide interesting exercises in
natural language processing nlp and sentiment analysis. Various papers address
the task of deducing a signed network based on the comments or reviews
imparted from person to person [4]. However, how well do these evaluations
perform when looking at less complicated models? We tested the rigor and
performance of natural language processing in predicting pairwise user
interactions. Fitting the nlp methodology to the triadic and latent
information models, we performed the comparison using the Wikipedia RfA data
set, which is a signed network decorated with user–user evaluations. We have
discovered that the natural language processing model performs the best, while
the other two models performed decently well.

##  2 Problem Statement

Performing detailed user–user predictions using comments and natural language
processing in parallel with the topology of signed networks has already been
accomplished with great results [12]. But can comparable results be achieved
with simpler models, especially for an information rich network such as those
centered around Wikipedia? The forthcoming goal, then, is to predict the peer-
to-peer interactions in an information network using three probabilistic soft
logic models, one of which is a natural language processing (nlp) framework,
while the other two (known as triadic and latent information) are rooted more
firmly in sociological theory. These three models are then compared to see if
contextual information (i.e., comments) enriches the predictions, or if
adequate approximations can be made without them.

To embark on this journey, the Wikipedia RfA (requests for adminship) data set
is used. This network is vast—approximately ten thousand nodes and 160
thousand edges. Not only does this network have signed edges, but it also has
comment embeddings between one user and another, summarizing person $A$’s
opinion of $B$’s request for adminship. The same methodology with the same
dataset derivatives are used to perform a comprehensive comparison.

##  3 Related Work

###  3.1 Pairwise Interactions in Sociology

Uncovering the who-trusts-whom backbone within a social network can uncover
mountains of information normally invisible. Predicting pairwise
relationships, positive or negative, are essential features of a network, and
the ability to predict them may have great impact on marketing techniques or
targeted advertising. This task double-dips in both computer science research
as well as sociological theory. As a primer, one may consider the latter.
Ultimately, these theories take care to formulate a triangular relationship
between members in a social network, yet using them as ground truths may prove
to be quite inflexible, especially when considering other opinion-based
features in parallel. Thankfully, there are many flavors of person-to-person
relationship predicting that relaxes these rigid constraints and provides a
usable approximation. Unfortunately, performing these computations may be
rather non-trivial.

###  3.2 Modeling Interactions with Probabilistic Soft Logic

One method for approximating trust between person $A$ and person $B$ yields
data not in a binary fashion, but rather on a spectrum from zero to one.
Researchers have tackled these interesting network problems by using
probabilistic soft logic (psl) aimed at modeling the trust within a social
network [7]. Probabilistic soft logic scaffolds hard-truths with an assigned
weight such as follows:

$\textsc{trusts}(A,B)\wedge\textsc{trusts}(B,C)\overset{0.75}{\Rightarrow}\textsc{trusts}(A,C)\,,$

where these key weights soften the hard logic prevalent in sociological
theory. With probabilistic soft logic, one can determine how “truthy"
something may be by its _distance to satisfaction_ , or plainly put, how close
the program’s prediction is from the actual truth [7]. If one were to consider
a set of ground truths $g\in G$, each truth $t_{g}$ with a weight $w_{g}$,
then the probability distribution over this prediction is

$Pr(x;w)=\exp\left(-\sum_{g\in G}w_{g}(1-t_{g}(x))\right)\,.$

For this kind of problem, reaching the global optimum is a challenge that may
not be solved in reasonable time, especially for extremely large networks.
Therefore, a cogent solution must satisfy some sort of constraint. Some
approaches have implemented a logistic regression methodology to measure the
“goodness" of machine learning predictions compared to using sociological
heuristics, while others have recast the objective function in a form more
pointed towards satisfying those same sociological constraints [9, 12].

###  3.3 Triadic Model: Analyzing and Predicting Edges

One obvious way to predict the edges between two peers is by a “fill in the
blank" sort of approach, by yielding a prediction that purely satisfies
sociological theories. Two of which are popular choices for the triadic model.
Familiar maxims like “the friend of my friend is also my friend" and “the
enemy of my enemy is my friend" take the main stage of balance theory. For
better or for worse, these truisms are framed in the context of
trustworthiness between peers. In other words, completing a triadic closure
with this theory mandates that if Amy trusts Brad, and Brad trusts Candice,
then Amy must also trust Candice.

Status theory ensures positive links are directed from subordinate to
superior, and vice versa [10, 3]. This theory maintains that if Amy is in
charge of Brad (a negative link), and Brad is in charge of Candice, then Amy
has a negative link towards Candice. However, the status theory cannot make a
prediction when considering two members of equal social status. If Brad is in
charge of Amy and Candice, then what is the relationship between the two
subordinates? Clearly this approach has limitations when attempting to satisfy
these aphorisms, and this is precisely where probabilistic soft logic can
shine. Previous work tries to evaluate the accuracy of these two social
theories in static and evolving social networks [10]. In brief, these theories
can correctly characterize, for example, mutual friendship triads, but may
underrepresent triads in balance theory. For dynamic graphs, however, balance
theory may not hold as strongly, and consequently status theory may be the key
to scoring accurate predictions.

###  3.4 Uncovering Discreet Assumptions in Social Networks

Oftentimes, there is a nuance in the very fingerprint of social networks that
may not normally be available at a cursory glance. These subtleties may be
considered _latent information_ : they are subtle, but unknown, parameters of
the system that provide deeper, more structured clues about the network at
hand. Discovery, then, rests on the nodes themselves rather than the edges.
For instance, one user may have a latent characterization as “strongly
trusting of others", while another user may be considered “moderately
trustworthy"—all while these tokens of information must be learned. However,
learning these latent variables, just like learning the trust between two
people, is a nontrivial task as well, since this hidden information must be
learned and updated several times over the entire network.

Researchers have tried to streamline the process of learning latent variables
by using what are known as hinge-loss Markov random fields, thus allowing the
network to be more scalable. Hinge-loss Markov random fields are probabilistic
models where the set of features is denoted by hinge-loss functions [6] Using
a hinge-loss Markov random field framework, however, and these attributes
become quite apparent, and significant performance boosts can be obtained when
using the paired-dual learning algorithm for learning these hidden attributes
[6].

###  3.5 Exploiting Natural Language Processing

One may draw comparisons between the relaxed Boolean logic previously
mentioned and another flavor of link prediction: sentiment analysis. In
natural language processing (nlp), strides have been made to project emotions
and persuasions from textspace to a more program-friendly format. The realm of
sentiment analysis is a great viewpoint for modeling interpersonal
relationships; researchers have even contextualized nlp with the same
sociological theories introduced above [12]. By leveraging this framework,
accomplishing the goal of guessing person-to-person relationships focuses less
on discovering, for example, the identity of the social network users in
question, but rather on its predictive capabilities.

But the role of nlp in solving these problems does not start where
sociological theories end; care must be taken to ensure that the previously
mentioned enshrining principles are followed [12]. However, as we have seen
before, these predictions may conflict with the sociological theories
previously outlined; this problem was solved by predicting edge weights not as
binary, but on a spectrum [12]. In other words, the inferred sign is actually
$x_{e}\in[0,1]$—the same flavor of probabilistic soft logic introduced
above—and thus the problem is cast as a hinge-loss Markov random field, which
makes it a good approximation for an np-hard problem. While much related work
is fixated on determining trust rather than friendship links, this model can
be extended for a signed network by mapping the transformation as $x_{e}=1$
indicating a positive interaction and $x_{e}=0$ indicating a negative
interaction [7, 8, 12]. Furthermore, this sign prediction problem has been
tackled in myriad forms, with some users leveraging the nature of the network
itself to make predictions, while others make use of the learning algorithms
and hefty dataset sizes [9, 5].

The methodology introduced in West et al. is a thorough one from which this
experiment can derive [12]. Modeling the social network as a signed graph
$G=(V,E,x)$ with $\left|V\right|$ vertices, $\left|E\right|$ edges of sign
$x\in\\{0,1\\}$, the following can be seen. First, the authors restrict their
attention to undirected graphs. They emphasize that this restriction can be
lifted, and parallel analyses can be performed on social networks where
user–user interactions are implicitly directed (such as following someone on
Twitter). The authors focus primarily on triangles in the graph as this
topographical feature is a natural extension of the aforementioned
sociological theories. A triangle is denoted as
$\\{e_{1},e_{2},e_{3}\\}\subseteq E$, three edges that form a cycle, with
signs $x_{t}=(x_{e_{1}},x_{e_{2}},x_{e_{3}})\in\\{0,1\\}^{3}$, and $T$ is the
set of all triangles in the graph.

Germane to this nlp problem, the objective function measures the so-called
triangular polarity of a triadic closure and characterizes it as a good
approximation (i.e., close enough to the sociological theories outlined
previously) or otherwise. It takes the form

$x^{*}={x\in\\{0,1\\}^{\left|E\right|}}\sum_{e\in E}c(x_{e},p_{e})+\sum_{t\in
T}d(x_{t})\,,$ (1)

where the first term describes the penalty of having each edge $x_{e}$ deviate
from its prediction $p_{e}$, while the second term quantifies the discordance
the triangle exhibits when viewed from the perspective of status or balance
theory. More specifically, the edge cost function $c$ is as follows:

$c(x_{e},p_{e})=\lambda_{1}(1-p_{e})x_{e}+\lambda_{0}p_{e}(1-x_{e})\,.$

The two parameters $\lambda_{1},\lambda_{0}$ are learned by the model using
hinge-loss Markov random fields via maximum-likelihood estimation.

##  4 Model

In this section, we present the three models, which are PSL model - Triadic,
PSL model - Latent Information and Sentiment model. We have already introduced
the PSL, a very powerful system for probabilistic modeling using first-order
logic syntax. The key point of PSL is to find the correct rules to describe
relational dependencies. For example, in the social trust network, if Mike
strongly trusts Alice, and Alice strongly trusts Jack, then we can define a
rule implying that Mike will likely trust Jack.

Later, we consider the latent information provided by the dataset. If someone
obtains the most upvotes from others, it implies that this person will more
likely be upvoted from his or her peers. If somebody downvotes most of his or
her peers, then it could be more possible that this person is not very active
or optimistic; more likely, he or she would downvote to other candidates. We
also consider the context of each pairwise link: We think this textual
information could provide more sufficient evidence to illustrate the
relationships between users. Therefore, we provide third model: the Sentiment
model.

###  4.1 PSL model - Triadic

Inspired by the social science balance theory, we encode the tendency for
upvoting and downvoting in our dataset using the rules listed in Figure 1. We
can see sixteen different possible rules are listed. The meaning behind these
rules are very intuitive: for example, if Mike strongly upvotes Alice, and
Alice strongly upvotes Jack, then it is more likely that Mike also strongly
upvotes Jack. And if Mike strongly upvotes Alice, but Alice strongly downvotes
Jack, we could infer that Mike will most likely downvote Jack because he and
Alice may have the same preference.

Figure 1: Rules for PSL model - Triadic. The rules are inspired from social
science balance theory.

After defining these rules, we must now assign predicted value to the unknown
atoms we obtain as a set of distances from satisfaction. An example of an atom
is Upvote(A,B). What is the best method to assign these values to obtain the
best prediction performance? One may approach this question from a different
perspective, seeing that this is another flavor of the combinatorial
optimization problem. Particular to this model, however, is that all the link
predictions are formed together, instead of one by one.

$P_{r}(X|w)=\frac{1}{C}\exp\left(-\sum_{r\in R}w_{r}(d_{r}(X))^{p}\right)\,.$

In this formula, $P_{r}$ is the probability density distribution over
assignment $X$, and $R$ is the set of rules we have defined before. $r$ is
rule’s weight—in the PSL model, each rule may differentially influence the
prediction. $d_{r}(X)$ is the rule’s distance to satisfaction between $X$ and
true values. $p$ is the distance exponent, which could be linear or quadratic.
If it is quadratic, then the variation of prediction is more smooth. Finally,
$C$ is a constant.

Notice that in our problem, the predicted value is 0 or 1, which is lends
itself to binary semantics. Here, we consider a continuous relaxation of the
binary problem and find an exact nonbinary solution whose edge signs are
continuous on the interval $[0,1]$. So as stated previously, we can cast our
problem as a hinge-loss Markov random field (HL-MRF). This is inspired by [1],
where a HL-MRF was used to predict edge signs based on balance theory. An HL-
MRF is an MRF with continuous variables and with potentials that can be
expressed as sums of hinge loss terms of linear functions of variables. HL-
MRFs have the advantage that their objective function is convex so that exact
inference is efficient.[2]

With this perspective, we can see that this problem is a maximum a posteriori
probability (MAP) estimate problem. We train this model using various learning
algorithm: inference method, maximum likelihood estimation (MLE), maximum
pseudo-likelihood estimation (MPLE), and mixed method (MM) to train and test
the dataset according to our model.

###  4.2 PSL model - Latent Information

The another inspiration from social science is the personality. The previous
work in signed networks focused mainly on links, whether that may be pairwise
trust or friendship. However, most of work ignored the properties that lay
within the nodes. In a trust network, for example, we can infer someone is
trustworthy according to his or her profile. More specifically, we consider
additional predicates Active and Favorable in our dataset, modeling whether a
member is active or favorable in (for this particular case) the Wikipedia
network. Important to note is that these predicates are _not_ part of the
dataset, which is why this model boasts the name “latent" information. The
intuition behind this elusive characterization is that a highly active person
will more upvote other candidates, while a highly favorable candidate will
receive more upvotes from his or her peers.

While the addition of more features could potentially make the analysis more
complicated, the node property could also strengthen our prediction. On
Facebook, for instance, Mike and Alice are foes, and Alice and Jack are
friends. Mike and Alice have the different political leanings: Mike leans
Democrat, and Alice Republican. At the same time, Jack has Republican
leanings. In this situation, we can make prediction that Mike and Jack may
bump heads more often in the political sphere than if they shared the same
political leaning. According to balance theory this prediction may be
apparent, but including this extra information provides a higher degree of
confidence when making the prediction.

Figure 2: Rules for PSL model - Latent Information. The rules are inspired
from social science.

However, we need to rewrite the PSL Triadic model to accommodate these
results. Notice that, in the previous model, we have already converted the
discrete link value 0 or 1 into a continuous [0,1]. Little modification needs
to be done there. On the other hand, there are several proposed methods to
solve the continuous latent variable model. We take the probabilistic
principal component analysis (PPCA) approach for this case.

Instead of using naive PCA and MLE-PCA, we use Expectation–Maximization for
PCA. The naive PCA and MLE-PCA have heavy computational taxes for high
dimensional data and large (and potentially incomplete) datasets. We rewrite
the previous model formula in the PSL - triadic model.

$\log P_{r}(X,Z|w)=\sum_{n}[\log P_{r}(X_{n}|Z_{n})+\log P_{r}(Z_{n})]$

Here, $Z$ represents the latent variables. In the E step of the E–M algorithm,
we compute the expectation of complete log likelihood with respect to the
posterior probability of latent variables $z$ using current parameters, from
which one can derive $E[z_{n}]$ and $E[z_{n}z_{n}^{T}]$ from posterior
probability $p(z|x)$. In the M step of the E–M algorithm, we maximize with
respect to parameter $W$ and hyperparameters in the model. This is an
iterative solution, at each step updating parameters given current
expectations, and expectations given current parameters.

Although the properties that are examined include Active and Favorable, the
nodes need not restrict themselves to two hidden properties. In fact, the node
of this signed network could have myriad other properties. Selecting the best
ones, then, depend on the nature of the problem being solved, so while the
political position or level of education or some other parameter may be
hidden, those are not as important in this problem as favorability and
activity. Obviously, considering all latent information could stifle the
training process, and the computational time would be much larger with more
features to train. Our experiment in the next section also supports this
intuition.

###  4.3 Sentiment model

Real signed networks may also include many other tokens of information
attached to the edges between two users, such as comments. These comments from
user $A$ to user $B$ represent the directed attitue and behavior, and thus it
is highly related to the edge sign. We continue with a sentiment model to
extract the hidden sentiment information from the comments embedded in the
edges and use the this treasure trove of information to make the prediction.

The sentiment model is a binary classifier which could predict whether a sign
is positive or negative given the nature of the text. Here, we use logistic
regression as the binary classifier and build feature extraction to convert a
comment into a input vector for the logistic regression. First, we use bag-of-
words model to extract a set of words as tokens from the text. Then, we
calculate the frequency of each token in the comments and convert the comments
into a token frequency vector. After that, we use term frequency–inverse
document frequency(TF-IDF) model to evaluate how important a word is to a
document. Based on TF-IDF model, we could convert the token frequency vector
into a weighted vector and use the weighted vector as the input of logistic
regression.

The TF-IDF model considers term frequency and inverse document frequency
together. Term frequency $tf(t,d)$ have many a particular weighting scheme.
Here, we use the raw frequency, which is the number of times that term $t$
occurs in the document. The inverse document frequency $idf(t,D)$ states
whether the term is common or rare across all documents. The equation is as
follows:

$idf(t,D)=\log(\frac{N}{|{t\in D:t\in d}|})\,,$

where $N$ is total number of documents in the corpus $N=|D|$.

Then, the tf-idf is calculated as:

$\textsc{tf-idf}(t,d,D)=tf(t,d)\cdot idf(t,D)$

Logistic regression is a common binary logistic model used to estimate the
probability of a binary response based on one or more predictor variables.
Logistic regression requires a sigmoid function to predict the probability
that a given item belongs to the class 1 versus the probability that it
belongs to the class 0. The function is

$P(y=1|x)=h_{\theta}(x)=\frac{1}{1+\exp(-\theta^{T}x)}\,,$

and

$P(y=0|x)=1-P(y=1|x)=1-h_{\theta}(x)\,.$

Our goal is to find appropriate $\theta$ so that the probability $P(y=1|x)$ is
large for all $x$ that belongs to class 1 and small for all $x$ that belongs
to class 0. One method of approach is by using a threshold to determine to
which class the given $x$ should belong. To evaluate the prediction, logistic
regression uses a cost function to evaluate the effective prediction and then
it could update $\theta$ to minimize the cost function. The cost function is
as follows :

$J(\theta)=-\sum_{i}(y^{(i)}\log(h_{\theta}(x^{(i)}))+(1-y^{(i)})\log(1-h_{\theta}(x^{(i)})))\,.$

After training the logistic regression classifier with cost function, we
obtain the sentiment model and then use the model to predict the sign of
edges.

##  5 Evalution

###  5.1 Dataset description

The dataset we use is the Wikipedia Requests for Adminship (wiki-RfA). This
large dataset was collected by Stanford SNAP Lab and is available at
http://snap.stanford.edu/data/wiki-RfA.html. For a Wikipedia editor to become
an administrator, a request for adminship (RfA) must be submitted. Any
Wikipedia member may cast a supporting, neutral, or opposing vote. Taking all
of the users into consideration, this generates a directed, signed network in
which nodes represent Wikipedia members and edges represent votes. Particular
to this dataset are comments embedded in the edges. A positive comment example
would be "a good contributor" or "I’ve no concern, will make an excellent
addition to the admin corps". The comments contains strong sentimental
information and thus can be used as evidence to infer the edge sign. The
format of the dataset is as follows:

Table 1: wiki-RfA Data Format Key | Value
---|---
SRC | Guettarda
TGT | Lord Roem
VOT | 1
RES | 1
YEA | 2013
DAT | 19:53, 25 January 2013
TXT | clueful, and unlikely to break Wikipedia.

The information we need is SRC, TGT, VOT, TXT.SRC is the user name of source,
TGT is user name of target, VOT is the source’s vote on the target, and TXT is
the comment written by the source. The dataset contains 10,835 nodes and
159,388 edges in total. To build the model using this dataset, we must
preprocess the dataset as needed.

First, we eliminate all ambiguous signs, leaving only positive votes and
negative votes to get a purely signed network. To get a map function from user
name to a unique ID, we use a getMap function to map their name into a unique
ID. Then, we filter some users from the dataset, sampling 500 or 1000 nodes
from the whole network to accelerate the computation. (Given the sheer size of
this dataset, sampling helps reduce the runtime drastically.) Second, the
dataset contains a sign imbalance problem. Our dataset contains a large number
of positive votes and a small number of negative votes; in reality, we are
more interested in the negative votes since they reveal rich emotional and
sentiment information that contravenes any sort of optimism normally found in
votes. To make the problem more interesting, we filter part of the positive
signs and keep all the negative signs to make sure that there is a steady
balance of both. After preprocessing, the dataset could be used as the input
of the data pipeline.

###  5.2 Evalution metrics

####  5.2.1 Evidence ratio

In our dataset, we only know part of the edge signs of the whole network. To
train and test our models, we must partition the data into some for training
and some for testing. All the training data is considered as observed data,
which implies they don’t need to be inferred. The evidence ratio is the ratio
of the size of training data to the size of test data. We hope to get better
prediction as we increase the size of the training dataset.

####  5.2.2 Metrics

In information retrieval, precision is a measure of result relevancy, while
recall is a measure of how many truly relevant results are returned. Precision
($P$) is defined as the number of true positives ($T_{p}$) over the number of
true positives plus the number of false positives ($F_{p}$):

$P=\frac{T_{p}}{T_{p}+F_{p}}\,.$

It is a measure of the fraction of true positives over all positively-
predicted items.

Recall ($R$) is defined as the number of true positives ($T_{p}$) over the
number of true positives plus the number of false negatives ($F_{n}$):

$R=\frac{T_{p}}{T_{p}+F_{n}}\,.$

Although precision and recall could be used as metrics, by themselves they are
too weak to appropriately measure the classifier. Instead, we introduce the
Receiver Operating Characteristic (ROC) curve and use area under the curve
(AUC) as our final metric. The ROC curve, is a graphical plot that illustrates
the performance of a binary classifier system as its discrimination threshold
is varied. It uses the true positive rate as the $y$-axis and the false
positive rate as the $x$-axis. We denote the area under the ROC curve as
$\text{AUC}/\text{ROC}$. Importantly, $\text{AUC}/\text{ROC}$ may ignore the
prediction quality of negative edges if they are rare; to remedy this, we
introduce the area under the Precision–Recall curve as another metric, we
denote it as $\text{AUC}/\text{negPR}$.

###  5.3 Model implementation

####  5.3.1 PSL Model implementation

Probabilistic soft logic (PSL) is a machine learning framework for development
probabilistic models. In PSL, we could define our model using a straightfoward
logical syntax and solve them with fast convex optimization. PSL is a logic
programming language, so we use the logic to express the statistical
relational learning problem. It contains three concepts: Predicate, Atom and
Rule. We build our triadic model and latent information model based on
different logic rules. The predicate is used to represent a certain
relationship or property like $\textsc{Friends}(A,B)$. An atom is used to
represent random variable like $\textsc{Friends}(\text{Steve},\text{Jay})$.
Finally, a rule is used to capture the dependency or constraint like

$3.0:\textsc{Friends}(A,B)\quad\&\quad\textsc{Friends}(B,C)\rightarrow\textsc{Friends}(A,C)\,.$

The value prefix represents the weight this rule holds, and this value could
be tuned from a learning progress.

In the training process, we define $N$ as the number of folds. $N$ has two
meanings in our training process. First it denotes the number of partitions we
split the data. For each time, we use $N-1$ folds as the training set and use
the remaining one fold as the test set. $N$ may also represent the number of
times cross validation is used. We train and predict for $N$ folds and in each
fold, we will choose a different fold as test set and the remaining folds as
training set. So a larger $N$ means not only our evidence ratio is larger but
also our cross validation will take more time. Because of limited time for our
project, we only choose the value $N$ as 3, 6 and 9. The reason of using $N$
folds like that is because we want to make use of our known edges, so we put
each known sign either into training set or test set.

####  5.3.2 Sentiment model implementation

We used the Python scikit-learn library to build a data pipeline and add
logistic regression classifier into the pipeline. scikit-learn already
provides a feature_extraction library. We use CountVectorizer to convert the
input text into token frequency vector and then the tf_vectorizer to convert
the token frequency vector into a weighted vector. Next, we split the input
dataset into training set and test set using cross_validation. We trained a
logistic regression classifier and used it to predict the test set. After
obtaining the probability, we called roc_auc_score, average_precision_score,
two functions from sklearn.metrics, and then we obtained the prediction
results like $\text{AUC}/\text{ROC}$ and $\text{AUC}/\text{negPR}$.

##  6 Results

In this section, we demonstrate the prediction quality of different models and
compare their performance in different cases.

Figure 3: Prediction accuracy($\text{AUC}/\text{posPR}$) from the Triadic
model trained with different estimation methods on small dataset.

As we can see in Figure 3, $\text{AUC}/\text{posPR}$ could achieve better
score as the evidence ratio increases. The PSL model provides three methods of
estimation to evaluate the score when we train the PSL model. We find that the
Maximum Likelihood Estimation (MLE) function could tune the best parameters
for our model in most cases, so we use MLE as our estimation when we train our
models.

Figure 4: Prediction accuracy from Triadic model under different AUC metrics
on small dataset

In Figure 4, we use several metrics to measure prediction accuracy. As you can
see, $\text{AUC}/\text{negPR}$ shows the worst results. In fact,
$\text{AUC}/\text{negPR}$ is a better indicator that can show the prediction
quality of negative signs if the proportion of negative sign is too small. So
we mainly focus on this metric, and our Triadic model could achieve 0.4 score:
better than the score of a random guess model.

Figure 5: Prediction accuracy from Triadic model under different AUC metrics
on sampled dataset

In Figure 5, to improve the $\text{AUC}/\text{negPR}$, we sampled the data to
add more negative signs and thus minimize the sign imbalance problem. After
using sampling method, the $\text{AUC}/\text{negPR}$ score reached to 0.5:
better than the previous result.

Figure 6: Prediction accuracy($\text{AUC}/\text{negPR}$) from the sentiment
model on small dataset and large dataset

In Figure 6, we show the prediction quality of the Sentiment model. As can be
seen, the Sentiment model itself is much better as it requires relatively less
data to get better results.

Table 2: Prediction accuracy from the Latent Information model under different AUC metrics on small datase Latent Information | MLE | MPLE
---|---|---
$\text{AUC}/\text{posPR}$ | 0.833/1.533 | 0.869/1.828
$\text{AUC}/\text{negPR}$ | 0.183/2.203 | 0.294/1.548
$\text{AUC}/\text{ROC}$ | 0.501/2.951 | 0.605/3.971

In Table 2, we show the results of Latent Information model. This model did
not give us any reliably good results. It appears adding latent information to
our Triadic model doesn’t improve the predictions, much to our consternation.
We consider two reasons that may cause the problem: First, the wiki-RfA data
set does not contain strong latent in formation in users’ voting, so the
latent model just does not work as well as it could have. Second, our training
data set is not large enough. Because the Latent Information model needs more
relationship information for each pair of users, each user (ideally) should
keep a minimum number of neighbors to hold enough latent information that can
be learned. While this could have been ameliorated with better sampling, the
primary concern was minimizing training time cost, and as such we were unable
to provide a large enough training set for our model.

##  7 Conclusions

In this paper, we proposed three models to solve the sign prediction problem
in signed network. First, we present the Tradic model, which inspired by the
balance theory from social science. In this model, we created the sixteen
different rules according to the structural theory and define two atoms like
upvote and downvote. Second, we considered the personality in the signed
network as latent information. Therefore we add two additional predicates
Active and Favorable and ten new different rules about these two predicates.
Third, because the dataset we analyzed has textual context in the form of
comments from other votees, we utilized this information and built sentiment
model to make predication.

We also compared the performance of Triadic model, Latent Information model
and Sentiment model, and we have shown that they are much better than a
random-guess model. We find that Sentiment model give us better results though
it requires some additional contextual data. We also find that Triadic model
could make use of the network information and provides us some useful
prediction. These two model may even complement each other in different cases.
Although our Latent Information model did not work very well, we believe the
model does capture hidden information and could be useful in other cases.

In future work, we may look for a better way to combine the sentiment model
into PSL model, which means that we can define several new rules that relies
on the implied comment information in the signed networks. The intuition is
that by computing the similarity of two Wikipedia member according to their
communication content, it adds similarity into PSL model and make the
predictions.

##  8 Acknowledgments

First, We thank Professor Sun for facilitating our research. Professor Sun
gave us lots of valuable suggestions and helped us find an interesting and
challenging topic. Also, we should thank to Stanford Network Analysis Project
(SNAP), which provides many useful data set. Finally, we also want to thank
PSL programmers who are kind to answer our naive questions at Google Groups.

## References

  * [1] S. Bach, B. Huang, B. London, and L. Getoor.  Hinge-loss markov random fields: Convex inference for structured prediction.  arXiv preprint arXiv:1309.6813, 2013.
  * [2] M. Brocheler, L. Mihalkova, and L. Getoor.  Probabilistic similarity logic.  arXiv preprint arXiv:1203.3469, 2012.
  * [3] L. Cosmides and J. Tooby.  Cognitive adaptations for social exchange.  The adapted mind, pages 163–228, 1992.
  * [4] V. K. Elangovan and J. Eisenstein.  Unsupervised induction of signed social networks from content and structure.  CoRR, abs/1411.4351, 2014.
  * [5] R. Guha, R. Kumar, P. Raghavan, and A. Tomkins.  Propagation of trust and distrust.  In Proceedings of the 13th International Conference on World Wide Web, WWW ’04, pages 403–412, New York, NY, USA, 2004. ACM.
  * [6] B. Huang and L. Getoor.  Paired-dual learning for fast training of latent variable hinge-loss mrfs.  2015\.
  * [7] B. Huang, A. Kimmig, L. Getoor, and J. Golbeck.  Probabilistic soft logic for trust analysis in social networks.  In International Workshop on Statistical Relational Artificial Intelligence (StaRAI 2012), 2012.
  * [8] B. Huang, A. Kimmig, L. Getoor, and J. Golbeck.  A flexible framework for probabilistic models of social trust.  In The 2013 International Conference on Social Computing, Behavioral-Cultural Modeling, & Prediction (SBP 2013), 2013.
  * [9] J. Leskovec, D. Huttenlocher, and J. Kleinberg.  Predicting positive and negative links in online social networks.  In Proceedings of the 19th international conference on World wide web, pages 641–650. ACM, 2010.
  * [10] J. Leskovec, D. Huttenlocher, and J. Kleinberg.  Signed networks in social media.  In Proceedings of the SIGCHI conference on human factors in computing systems, pages 1361–1370. ACM, 2010.
  * [11] C. Wang.  Case studies of signed networks.  2014\.
  * [12] R. West, H. S. Paskov, J. Leskovec, and C. Potts.  Exploiting social network structure for person-to-person sentiment analysis.  CoRR, abs/1409.2450, 2014.


$\left|f^{\prime}(r)\right|\leq\frac{1}{2}\mathbb{E}\left[\left\langle\left\|d\zeta\left(\pi(m_{\alpha\wedge\widetilde{\alpha}})\right)-d\zeta\left(\pi^{\prime}(m_{\alpha\wedge\widetilde{\alpha}})\right)\right\|\right\rangle_{r}\right]+\|x-x^{\prime}\|.$

The weights of the Ruelle probability cascade have the property [37, Thm. 4.4]
that

$\displaystyle\mathbb{E}\left[\left\langle\left\|d\zeta\left(\pi(m_{\alpha\wedge\widetilde{\alpha}})\right)-d\zeta\left(\pi^{\prime}(m_{\alpha\wedge\widetilde{\alpha}})\right)\right\|\right\rangle_{r}\right]=\sum_{\alpha,\tilde{\alpha}}\mathbb{E}\left[\mu^{\pi,\pi^{\prime}}_{\alpha}\mu^{\pi,\pi^{\prime}}_{\tilde{\alpha}}\right]\left\|d\zeta\left(\pi(m_{\alpha\wedge\widetilde{\alpha}})\right)-d\zeta\left(\pi^{\prime}(m_{\alpha\wedge\widetilde{\alpha}})\right)\right\|$
$\displaystyle=\sum_{j=0}^{r+1}\left\|d\zeta\left(\pi(m_{j})\right)-d\zeta\left(\pi^{\prime}(m_{j})\right)\right\|\sum_{\alpha\wedge\widetilde{\alpha}=j}\mathbb{E}\left[\mu^{\pi,\pi^{\prime}}_{\alpha}\mu^{\pi,\pi^{\prime}}_{\tilde{\alpha}}\right]=\int_{0}^{1}\left\|d\zeta\left(\pi(m)\right)-d\zeta\left(\pi^{\prime}(m)\right)\right\|dm$
$\displaystyle\leq
L_{\zeta}\int_{0}^{1}\left\|\pi(m)-\pi^{\prime}(m)\right\|_{2}dm,$

where the last step is by (1.12). This completes the proof of (1.22).

∎

###  B.2 Convexity, bounds and differentiability

###### Proof of Proposition 1.6.

1\. The convexity of $x\mapsto\mathcal{P}(\pi,x)$ is immediate from that of
$X_{0}(\pi,x)$ and the representation (1.21). So is the boundedness of
$\int_{0}^{1}\theta(\pi(m))dm$ from Lemma 1.3.

The lower bound on $X_{0}(\pi,x)$ for any $\pi\in\Pi$ follows from an
application of Jensen’s inequality to (1.21), which yields

$X_{0}(\pi,x)\geq\mathbb{E}\left[\sum_{\alpha\in\mathbb{N}^{r}}\mu^{\pi}_{\alpha}\int\langle\xi,z_{\alpha}\rangle+\langle\xi,\left(x-\tfrac{1}{2}d\zeta(\pi(1)\right)\xi\rangle\nu_{1}(d\xi)\right]\geq-\int\langle\xi,\left(x_{-}+\tfrac{1}{2}d\zeta(\pi(1)\right)\xi\rangle\
\nu_{1}(d\xi).$

The scalar product is estimated either by
$\langle\xi,x_{-}\xi\rangle\leq\|x_{-}\|$, or, using its integral
representation and the boundedness of the paths, by
$\langle\xi,x_{-}\xi\rangle\leq\int_{0}^{1}\int_{0}^{1}|\widehat{x}_{-}(s,t)|dsdt$.
The operator norm bound $\|d\zeta(\pi(1))\|\leq N_{\zeta}$ is from Lemma 1.2.

The upper bound on $X_{0}(\pi,x)$ is also by Jensen’s inequality, which using
the fact that the exponential contains a martingale, yields

$X_{0}(\pi,x)\leq\ln\int\exp\left(\langle\xi,x\xi\rangle\right)\nu_{1}(d\xi)\leq\ln\int\exp\left(\langle\xi,x_{+}\xi\rangle\right)\nu_{1}(d\xi).$
(B.2)

The above bounds on the scalar product yield the claim concerning
$X_{0}(\pi,x)$.

An explicit computation starting from (1.21) yields for any
$x,y\in\mathcal{S}_{2}$

$\frac{d}{d\lambda}\mathcal{P}(\pi,x+\lambda
y)\Big{|}_{\lambda=0}=\mathbb{E}\left[\left\langle\langle
r_{1}(\xi,\xi),y\rangle\right\rangle_{x}\right],$

where $\langle(\cdot)\rangle_{x}$ abbreviates the average corresponding to
$\sum_{\alpha\in\mathbb{N}^{r}}\mu^{\pi}_{\alpha}\int\exp\left(\langle\xi,z_{\alpha}\rangle+\langle\xi,\left(x-\tfrac{1}{2}d\zeta(\pi(1)\right)\xi\rangle\right)\nu_{1}(d\xi)$.
For an estimate, we use $\|r_{1}(\xi,\xi)\|_{2}=1$. Differentiating again then
yields

$\frac{d^{2}}{d\lambda^{2}}\mathcal{P}(\pi,x+\lambda
y)\Big{|}_{\lambda=0}=\mathbb{E}\left[\left\langle\langle
r_{1}(\xi,\xi),y\rangle^{2}\right\rangle_{x}-\left\langle\langle\langle
r_{1}(\xi,\xi),y\rangle\right\rangle_{x}^{2}\right],$ (B.3)

from which the bound immediately follows.

2\. The first inequality is (B.2) combined with the fact that
$\inf_{\pi\in\Pi}\int_{0}^{1}\theta(\pi(m))dm=0$. The next inequality results
from 1. and the trivial estimate of the supremum by
$\inf_{\pi\in\Pi}\mathcal{P}(\pi,0)-\frac{1}{2}\zeta^{*}(0)=\inf_{\pi\in\Pi}\mathcal{P}(\pi,0)\geq-
N_{\zeta}/2$ by 1. The third inequality is a simple consequence of the first.
The last inequality used the fact that by the Fenchel-Young inequality for
conjugate pairs [5, Prop. 13.13] for any $\xi\in L^{2}$ with corresponding
rank-one operator $|\xi\rangle\langle\xi|\in\mathcal{D}$:

$\langle\xi,x\xi\rangle\leq\frac{1}{2}\zeta^{*}(2x)+\frac{1}{2}\zeta(|\xi\rangle\langle\xi|)\leq\frac{1}{2}\zeta^{*}(2x)+\frac{1}{2}\widehat{\zeta}(1),$

where the last step is by Lemma 1.2. ∎

Acknowledgments This work was supported by the DFG under EXC-2111–390814868,
and to a minor extend also under DFG–TRR 352–Project-ID 470903074. SW would
like to thank Silvio Franz for helpful discussions.

## References

  * [1] A. Adhikari and C. Brennecke.  Free energy of the quantum Sherrington–Kirkpatrick spin-glass model with transverse field.  Journal of Mathematical Physics, 61:083302, 2020.
  * [2] M. Aizenman, J. L. Lebowitz, and D. Ruelle.  Some rigorous results on the Sherrington-Kirkpatrick spin glass model.  Commun. Math. Phys., 112(1):3–20, 1987.
  * [3] C. L. Baldwin and B. Swingle.  Quenched vs annealed: Glassiness from SK to SYK.  Physical Review X, 10(3):031026, 2020.
  * [4] E. Bates and Y. Sohn.  Parisi formula for balanced Potts glass.  arXive:2310.06745, 2023.
  * [5] H. H. Bauschke and P. L. Combettes.  Convex analysis and monotone operator theory.  Springer, 2017.
  * [6] R. Bhatia.  Matrix analysis.  Springer New York, 1997.
  * [7] A. Bovier.  Statistical Mechanics of Disordered Systems: A Mathematical Perspective.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2006.
  * [8] C. Brislawn.  Kernels of trace class operators.  Proc. Amer. Math. Soc., 104:1181–1190, 1988.
  * [9] B. K. Chakrabarti, A. Dutta, and P. Sen.  Quantum Ising phases and transitions in transverse Ising models.  Springer, 1996.
  * [10] B. K. Chakrabarti, H. Leschke, P. Ray, T. Shirai, and S. S. Tanaka.  Quantum annealing and computation: challenges and perspectives.  Phil. Trans. R. Soc. A, 381:20210419, 2023.
  * [11] L. Chayes, N. Crawford, D. Ioffe, and A. Levit.  The phase diagram of the quantum Curie-Weiss model.  Journal of Statistical Physics, 133(1):131–149, 2008.
  * [12] H.-B. Chen.  On the self-overlap in vector spin glasses.  arXiv:2311.08980, 2023.
  * [13] H.-B. Chen.  Self-overlap correction simplifies the Parisi formula for vector spins.  arXiv:2306.1025, 2023.
  * [14] H.-B. Chen and J. Xia.  Hamilton–Jacobi equations from mean-field spin glasses.  arXiv:2201.12732, 2022.
  * [15] P. Contucci.  Perspectives on Spin Glasses.  Cambridge UP, 2012.
  * [16] N. Crawford.  Thermodynamics and universality for mean field quantum spin glasses.  Communications in Mathematical Physics, 274(3):821–839, 2007.
  * [17] D. Elderfield and D. Sherrington.  The curious case of the Potts spin glass.  Journal of Physics C: Solid State Physics, 16(15):L497, 1983.
  * [18] L. Erdős and D. Schröder.  Phase transition in the density of states of quantum spin glasses.  Mathematical Physics, Analysis and Geometry, 17(3):441–464, 2014\.
  * [19] Ya. V. Fedorov and E. F. Shender.  Quantum spin glasses in the Ising model with a transverse field.  JETP Lett., 43:681 –684, 1986.
  * [20] G. Genovese and A. Barra.  A mechanical approach to mean field spin models.  J. Math. Phys., 50:053303, 2009.
  * [21] A. Georges, O. Parcollet, and S. Sachdev.  Mean field theory of a quantum Heisenberg spin glass.  Physical Review Letters, 85(4):840–843, 07 2000.
  * [22] Y. Y. Goldschmidt.  Solvable model of the quantum spin glass in a transverse field.  Physical Review B, 41(7):4858–4861, 1990.
  * [23] F. Guerra.  Broken replica symmetry bounds in the mean field spin glass model.  Communications in Mathematical Physics, 233(1):1–12, 2003.
  * [24] F. Hiai.  Monotonicity for entrywise functions of matrices.  Linear Algebra and its Applications, 431(8):1125–1146, 2009.
  * [25] I. A. Ibraginov and Y. A. Rozanov.  Gaussian random processes.  Springer New York, 1978.
  * [26] C. Itoi, H. Ishimori, K. Sato, and Y. Sakamoto.  Universality of replica-symmetry breaking in the transverse field Sherrington–Kirkpatrick model.  Journal of Statistical Physics, 190(3):65, 2023.
  * [27] H. Leschke, C. Manai, R. Ruder, and S. Warzel.  Existence of replica-symmetry breaking in quantum glasses.  Physical Review Letters, 127(20):207204, 2021.
  * [28] H. Leschke, S. Rothlauf, R. Ruder, and W. Spitzer.  The free energy of a quantum Sherrington–Kirkpatrick spin-glass model for weak disorder.  Journal of Statistical Physics, 182(3):55, 2021.
  * [29] C. Manai and S. Warzel.  Phase diagram of the quantum random energy model.  Journal of Statistical Physics, 180(1):654–664, 2020.
  * [30] C. Manai and S. Warzel.  The de Almeida–Thouless line in hierarchical quantum spin glasses.  Journal of Statistical Physics, 186(1):14, 2021.
  * [31] C. Manai and S. Warzel.  Generalized random energy models in a transversal magnetic field: Free energy and phase diagrams.  Probability and Mathematical Physics, 3:215—245, 2022.
  * [32] C. Manai and S. Warzel.  Spectral analysis of the quantum random energy model.  Communications in Mathematical Physics, 402(2):1259–1306, 2023\.
  * [33] M. Mezard and A. Montanari.  Information, physics, and computation.  Oxford UP, 2009.
  * [34] M Mezard, G Parisi, and M Virasoro.  Spin Glass Theory and Beyond.  World Scientific Lecture Notes in Physics. World Scientific, 1986.
  * [35] S. Morita, Y. Ozeki, and H.H. Nishimori.  Gauge theory for quantum spin glasses.  Journal of the Physical Society of Japan, 75(1):014001, 2005.
  * [36] J.-C. Mourrat.  Hamilton–Jacobi equations for mean-field disordered systems.  Annales Henri Lebesgue, 4:453–484, 2021.
  * [37] D. Panchenko.  The Sherrington-Kirkpatrick model.  Springer New York, NY, 2013.
  * [38] D. Panchenko.  Free energy in the mixed p-spin models with vector spins.  Ann. Probab., 46:865–896, 2018.
  * [39] D. Panchenko.  Free energy in the Potts spin glass.  Ann. Probab., 46:829–864, 2018.
  * [40] G. Parisi.  Infinite number of order parameters for spin-glasses.  Physical Review Letters, 43(23):1754–1756, 1979.
  * [41] G. Parisi.  A sequence of approximated solutions to the S-K model for spin glasses.  Journal of Physics A: Mathematical and General, 13(4):L115, 1980\.
  * [42] D. Ruelle.  A mathematical reformulation of Derrida’s REM and GREM.  Commun. Math. Phys., 108:225–239, 1987.
  * [43] D. Sherrington and S. Kirkpatrick.  Solvable model of a spin-glass.  Phys. Rev. Lett., 35:1792–1796, 1975.
  * [44] H.-J. Sommers.  Theory of a Heisenberg spin glass.  Journal of Magnetism and Magnetic Materials, 22(3):267–270, 1981\.
  * [45] S. Suzuki, Inoue J.-i., and B. K. Chakrabarti.  Quantum Ising Phases and Transitions in Transverse Ising Models.  Lecture Notes in Physics 862. Springer, 2013.
  * [46] M. Talagrand.  The Parisi formula.  Annals of Mathematics, 163:221–263, 2006.
  * [47] M. Talagrand.  Mean Field Models for Spin Glasses I. Springer, 2011.
  * [48] M. Talagrand.  Mean Field Models for Spin Glasses II. Springer, 2011.
  * [49] S. Tanaka, R. Tamura, and B. K. Chakrabarti.  Quantum spin glasses , annealing and computation.  Cambridge UP, 2017.
  * [50] K. D. Usadel and B. Schmitz.  Quantum fluctuations in an Ising spin glass with transverse field.  Solid State Communications, 64(6):975–977, 1987.
  * [51] J. Weidmann.  Integraloperatoren der Spurklasse.  Math. Ann., 163:340–345, 1966.
  * [52] T. Yamamoto and H. Ishii.  A perturbation expansion for the Sherrington-Kirkpatrick model with a transverse field.  Journal of Physics C: Solid State Physics, 20(35):6053, 1987.
  * [53] A. P. Young.  Stability of the quantum Sherrington-Kirkpatrick spin glass model.  Physical Review E, 96(3):032112–, 2017.

Chokri Manai and Simone Warzel
Departments of Mathematics & Physics, and MCQST
Technische Universität München