Situation
We have a social network whose
. nodes are persons
. edge values are discrete trust ratings (in [1,4])
For example, we have nodes A and C and an edge going from A to C whose value is 1 (A trusts C at level 1). See example below (trust ratings in brackets)
Problem
Find a way to predict the value of one missing edge (NOTE: predict ONE edge at a time) on input of the social network

Proposal
1. Build an undirected graph from the social network by exchanging nodes with edges . From the previous social network, we obtain:


1st Issue : How do we represent cycles of the social network? By assigning stronger weights to the corresponding edges in the undirected graph (as shown below)?

2. Formalize the problem.
. We seek a function f: x -> R that gives a continuous rating f(x) to a social network edge x (Classification is done by mapping f(x) with the nearest discrete rating in [1,4]).
. For simplicity, we consider that the edges of the undirected graph are not weighted (but this depends on how we tackle the '1st Issue').
. The idea is that f(x) should be smooth with respect to the graph (that is, similar edges are rated similarly).
. The (un)smoothness over any edge between x and y is proportional to (f(x) - f(y))^2
. Summing over all edges of the graph, we obtain the (un)smoothness L(f) over the whole graph. We call L(f) loss.
. If the loss is small, the rating of the unlabeled node (social net edge) is close to its labelled peers.
. We should solve the optimization problem min_f L(f)
. 2nd Issue: Can we adapt any of the graph-based semi-supervised learning method to the case of one single unlabeled node?
. Note: Semi-supervised learning is interesting when the size of unlabeled data is large !