Project topics and materials
Get Complete Project Material File(s) Now! »
Algorithms in the Batch Setting
Given G(Y ) = (V; E(Y )), in the batch setting we have at our disposal a train-ing set E0 of labeled edges from E(Y ). Formally, we have a training set E0 = (u1; v1); yu1;v1 ); ((u2; v2); yu2;v2 ); : : : ; ((um; vm); yum;vm , that has been drawn from E Y uniformly at random without replacement, with m = jE0j. We want to build a predictive model for the labels of the remaining edges. We present two algorithms to do so, which both compute estimates of the all parameters p and q of our generative model. They differ in the approximation guarantees they provide, and in the class of graphs to which they apply. The first algorithm runs on the graph G and estimates locally the parameters by their empirical means in the training set, which under some density assumptions are showed to concentrate around their true values. The second algorithm, on the other hand, exploits the reduced graph G00 and computes a maximum likelihood estimation of the parameters through a global label propagation approach, without making any density assumption.
Approximation to Bayes via dense sampling
Our first algorithm is an approximation to the Bayes optimal predictor y (u; v). Let us denote by trb(u) and unc(u) the trollness and the untrustworthiness of node u when both are computed on the subgraph induced by the training edges. Recall that the Bayes optimal predictor classifies an edge u ! v using the following rule: y (u; v) = sign pu+qv 1 . Our approximation thus consists in using the quantities tr(u) un(u) pu+qv following rule: b and c to estimate . This results in the 1 2 (2.3) sign 1 tr(u) + 1 un(v) ; b c 2 where 0 is the only parameter to be trained. We now give an intuition to justify this equation, and defer the technical arguments to end of the chapter, on page 37, where we will formalize what it means for a quantity to be “close” to another.
Note first that 1 trb(u) = db+out(u) is the empirical mean7 of the probability of a dbout(u) random edge outgoing from u to be positive, and is therefore “close” to 12 (pu + qu).
Approximation to Maximum Likelihood via Label Propagation
Remember we suppose that the training set E0 has been drawn uniformly at random without replacement, with m = jE0j. Then a reasonable approach to approximate y (u; v) would be to resort to a maximum likelihood estimator of the parameters fpu; qugjuV=1j based on E0. If we further assume, in order to make the computation more tractable, that the joint prior distribution (p; q) is uniform over [0; 1]2 with independent marginals,9 we show in the supplementary material on page 40 that for ‘ 2 f1; : : : ; jV jg the gradient of the log-likelihood function with respect to a given p‘ and q‘ satisfies.
Experimental Analysis
We now evaluate our EDGE SIGN PREDICTION methods on representative real-world datasets of varying density and label regularity. After presenting the data and our evaluation criterion, we proceed in two steps. First, we simulate our generative model on real networks to give them signs, then we study to which extent we can recover the parameters p and q of each node, and how predictions based on these estimation compare with the Bayes optimal. Second, we select random training sets from the actual signs. This shows that our methods compete well against existing approaches in terms of both predictive and computational performance. We are especially interested in small training set regimes, and have restricted our comparison to the batch learning scenario since all competing methods we are aware of have been developed in that setting only.
Datasets
We consider six real-world classification datasets. The first four are Directed Signed Social Networks widely used as benchmarks for this task [LHK10; SJ14; WAS16; Wan+17a]. In ADVOGATO, a trust-based social network for open source developers, a user u can certify another user v with different degrees of trust: “Observer”, “Apprentice” (both of which we consider negative), “Journeyer” and “Master” (both of which we consider positive).13 A full description of this trust metric, and its resistance to attacks, is available in the PhD thesis of the website’s creator [Lev02, Section 4]). In WIKIPEDIA, there is an edge from user u to user v if v applies for an admin position and u votes for or against that promotion. In SLASHDOT, a news sharing and commenting website, member u can tag other members v as friends or foes. Finally, in EPINION, an online shopping website, user v reviews products and, based on these reviews, another user u can display whether he considers v to be reliable or not. In addition to these four datasets, we considered two other signed social networks where the signs are inferred automatically, rather than given explicitly by the users. In WIK. EDITS [MAC11], an edge from Wikipedia user u to user v indicates whether they edited the same article in a constructive manner or Table 2.2 – Dataset properties. The 5th column gives the fraction of positive labels. The next two columns provide two different measures of label regularity, while the last two columns give the proportion of reciprocal edges, and among them the fraction with different signs.
Table of contents :
1 Introduction
1.1 Learning in graphs
1.2 Graph with several edge semantics
1.2.1 Signed graphs
1.2.2 Multilayer graphs
1.3 Predicting edge type
1.4 Outline
2 On the Troll-Trust Model for edge sign prediction in Social Networks
2.1 Notation and Preliminaries
2.2 Generative Model for Edge Labels
2.3 Algorithms in the Batch Setting
2.3.1 Approximation to Bayes via dense sampling
2.3.2 Approximation to Maximum Likelihood via Label Propagation
2.4 Related work
2.5 Experimental Analysis
2.5.1 Datasets
2.5.2 Synthetic signs
2.5.3 Real signs
2.5.4 Additional experiments
2.6 Algorithms in the Online Setting
2.7 Open questions
2.8 Summary
2.9 Additional material
2.9.1 Proofs from Section 2.3
2.9.1.1 Proof of Theorem 1
2.9.1.2 Derivation of the maximum likelihood equations
2.9.1.3 Label propagation on G00
2.9.2 Proof from Section 2.6
2.9.3 Further Experimental Results
3 Edge sign prediction in general graphs and Correlation Clustering
3.1 A bias for general graphs
3.1.1 Sign generative model and behavior
3.1.2 Directed edges requirement
3.1.3 Social balance as a learning bias
3.2 CORRELATION CLUSTERING
3.2.1 Problem setting and connection to EDGE SIGN PREDICTION .
3.2.2 State of the art
3.2.2.1 Exact methods
3.2.2.2 Hardness and approximations
3.2.2.3 Heuristics
3.2.2.4 Active and online settings
3.2.3 Beyond worst case instances
3.2.4 Variants and extensions
3.3 Low stretch trees and spanners
3.3.1 GALAXY TREE: a spanning tree designed for sign prediction .
3.3.2 Related work
3.3.3 Empirical evaluation
3.3.3.1 Graph topology
3.3.3.2 Stretch
3.3.3.3 Sign prediction
3.4 Conclusions
3.4.1 Summary
3.4.2 Future work
4 Edge clustering in node attributed graphs
4.1 Attributed graphs and problem definition
4.1.1 Setting and modelling
4.1.2 Learning problem and additional constraints
4.2 Proposed approaches
4.2.1 k-MEANS baseline and improvement
4.2.2 Convex relaxation
4.2.3 Matrix optimization
4.2.3.1 FRANK–WOLFE method
4.2.3.2 EXPLICIT low rank factorization
4.3 Synthetic experiments
4.3.1 Data generation
4.3.2 Results
4.4 Related work
4.5 Open directions
5 Conclusion
5.1 Contributions
5.2 Future work
5.2.1 Reciprocal recommendation
5.2.2 Representation learning .
