Link Prediction in Signed Graph

Link Prediction in Signed Graph

Social Network is represented by graphs, with nodes representing entities and edges representing relationship between those entities. However, when a network has like/dislike, respect/disrespect relationship such representation is not adequate. Such network can be modeled using Signed graphs. E.g. Websites where user reviews like YouTube(user and videos are entities,  positive and negative reviews as links).

Although many notion of Unsigned network can be used for Signed network, when edge weights are allowed to be negative. But Signed Networks have one basic property "Social Balance" associated with it that is not present in the Unsigned network.

The Social Balance is used as an important property  for prediction of link in Signed Networks. This property tend to conform that some local patterns, in turn induces global characteristics.

Categories of Signed Networks:

• Homogeneous Signed Networks:- All the entities in the network are of same type. It is represented as a graph with adjacency matrix A,

We can say A, as part of an underlying Complete signed network ( contains relationship between each pair of element) A 

• Heterogeneous Signed Network:- Here more than one entities exists, relationship between entities (whether same or different) can be positive or negative. E.g. YouTube, the two kinds of entities are user and videos.

Social Balance:  

The Social Balance theory says that relationship between entities tend to be balanced. A triad is balanced if contains even number of negative edges.
We can generalize this theory to general l-cycle, an l-cycle is balanced if it contains an even number of negative edges.

A Complete Network is balanced if all triads in it are balanced. However, as most network are not complete, so a network is said to be balanced when it is possible to assign signs to all missing entries, such that the resulting complete network is balanced.

Balance Theory from Cartwrigth and Haray: 

A network is balanced iff either (i) all edges are positive, or (ii) we can divide nodes into two clusters (or groups),such that all edges within clusters are positive and all edges between clusters are negative

Sign Prediction Problem:

We need to identify the relationship between a pair of entities i and j based on partial observation of entire network of relationship. As stated earlier local pattern induces global characteristics, so exploiting this property.

Local Method for Sign Prediction: 

A natural approach for designing sign prediction algorithms proceeds by reasoning locally in terms of unbalanced triangles, which motivates the following measure of imbalance:

where SC(A,3) represents sets of triangle in the network. Note: If network is balanced then, 

In general, we can use SC(A,l) : to represent all cycles of length l. So the equation modifies to:

where l >=3 and beta(i) 's are weighing the relative contribution of unbalanced cycles of different length.
However enumerating simple cycles in graph is NP-Hard. To get around this, we change the definition:

Prediction of link: 

For a given graph A and query(i,j), we construct two graph

These are obtained by setting +1 and -1 for the edges in the graph respectively, then sign is simply:

Other methods for link prediction for signed graph includes:

• Katz's Measure

• Convex Relaxation

REFERENCES:

• Kai-Yang Chiang, Cho-Jui Hsieh, Nagarajan Natrajan, Indrijet S. Dhillon. "The Journal of Machine Learning Research" Pages 1177 Volume 15 Issue 1, January 2014