Networks with Negative Edges

When I started my PhD program at the Technische Universität in Berlin, my first task was to research rating prediction methods.  Rating prediction is a huge topic:  In 2006, Netflix started the Netflix Prize, in which participants could win a million dollars by predicting whether a given person likes or dislikes a given movie.  To make these predictions possible, Netflix published the ratings of 480,000 persons for 17,000 movies.  Ratings on Netflix are on a scale from 1 to 5.  1 would mean a user dislikes a movie and 5 means the user likes it.  Then, given a list of (user, movie) pairs, ratings had to be predicted and submitted to Netflix.  The submitted predictions were then compared to actual withheld ratings, and the first team to improve by 10% the prediction accuracy (measured in a least-squares sense) of Netflix’s own recommender then won the million dollars.

To predict ratings, there are many approaches, but as a new PhD student I came up with the following idea: First of all, interpret ratings as positive if they are over the mean rating and as negative otherwise.  Then, interpret the set of all ratings as a graph with positive and negative edges in which users and movies are nodes and the edges are the ratings.  Then, given a (user, movie) pair, predict a rating by looking at paths between the user and the rating. A good rating prediction function of this form must fulfill three conditions:

1. When there a more paths between the user and the movie, return a higher rating (because the movie was then rated by people who rated more movies in common with the given user)
2. When paths between the user and the item are longer, then the rating should be lower. For instance a path of length 3 in this graph denotes that the user has rated a movie which has been rated by a user who has rated the given movie.  A path of length 5 however implies a longer and thus weaker relationship.
3. On any given path between the user and the item, when there are an odd number of negative ratings, the predicted rating should be negative.  Otherwise it should be positive.

Negative Resistances

What kind of function of two nodes of a graph would fulfill these conditions?  Let’s just look at the first two conditions:  If the paths between the two given nodes are longer, return lower values, and if there are many paths, return higher values.  This should remind everyone of something most of us learned in high school:  electrical resistances!  Let me explain:  Combining resistances one after the other (‘”in series”) will give a higher resistance; joining resistances one in parallel to the other (“in parallel”) will give a lower value.

This is the inverse of what we want, so instead of looking at resistances, we just look at their inverses, which are called conductances (and are measures in Siemens, or “Mho”, i.e. inverted Ohm).  This construction leads to the so-called resistance distance, which some people also call the electric metric.  The resistance distance between two nodes of a network is defined as the equivalent electrical resistance of the full network when measured between the two given nodes.

Now, the resistance distance implements our first two requirements.  But what about the third?  Since electrical resistances can only be positive, we cannot simply apply it to networks with negative edges.  Or can we?  Let’s try.  Let a = +1 and b = −1 be the conductances of two edges that we want to combine.  When combined in parallel, conductances add up, and the result is a + b = (+1) + (−1) = 0.  This makes sense:  If I like and don’t like a movie at once, then a prediction would be zero, i.e. that I’m neutral to it.  When put in series, it is resistance values that add up, and therefore we get the conductance 1/(1/a + 1/b) = 1/0.  Does an infinite conductance value make sense here?  No, because the expected conductance, according to our three conditions should be negative (because there is an odd number of negative edges), and it’s absolute value should be less than 1 (because the path has length 2).  So, just using negative values for conductances does not work.  Instead, we can use the following idea:

An edge with negative weight −w is interpreted as a resistance of (1/w) in series with a “inverting amplifier”, denoted as (−) in the graphic.  By an inverting amplifier, I mean an electrical component whose two ends always have opposite electrical potential.  An inverting amplifier has to be earthed (because otherwise it would not “know” what voltage counts as zero to invert around).  However, disregarding the actual implementation of an inverting amplifier, we get the effect we want:  In our previous example a edge of +1 in series with an edge of (−1) gives a conductance of +1 followed by a conductance of +1 followed by an inverted amplifier.  By simplifying the two conductance (which are in series), we arrive at a conductance of 1/2 in series with an inverting amplifier, giving an edge of −1/2, exactly what we needed!

The Graph Laplacian

At this point you should be asking:  How can the resistance distance between two nodes of a network be computed, anyway?  The answer is to use a matrix called the graph Laplacian, denoted L. Let n be the number of nodes in the network.  L is an n×n matrix with L_ij = −w when the edge (i, j) has weight w,  L_ii = Σ_j w(i,j) and L_ij = 0 otherwise. The resistance distance between nodes i and j is then given by

d(i, j) = (L⁺)_ii + (L⁺)_jj − (L⁺)_ij − (L⁺)_ji.

Here, L⁺ is the Moore–Penrose pseudoinverse of L.

The question is now how to compute the resistance distance when negative edges are allowed.  The answer is to used a modified version of the Laplacian, in which the diagonal elements are defined as L_ii = Σ_j |w(i,j)|.  To see why this is the case would require to check of the proof of the expression for the unsigned resistance distance above, and extend it to negative edges.  This is done in reference [2] below, but since it’s long and boring we will look at something more fun in which the Laplacian also arises:  graph drawing.

Graph Drawing

Given a graph, we want to draw it.  In other words, we want to find coordinates for each nodes, such that when we draw the edges, the pictures looks pretty.  There are many ways to interpret the word “pretty” which lead to all kinds of graph drawings.  Here we’ll take a very simple definition:  A graph drawing is pretty when each nodes is drawn near to it’s neighbors.  In other words, we need to find node-vectors x and y such that for each node i, the point (x(i), y(i)) is near to the neighbors of i.  The nearest point to a given set of points is given by the center of gravity of these point.  We then get the following two equations for each node i:

[ Σ_i~j x(j) w(i,j) ] / Σ_i~j w(i,j) = x(i)

and

[ Σ_i~j y(j) w(i,j) ] / Σ_i~j w(i,j) = y(i).

Note that we are taking sums over all neighbors of i, and that the center of gravity is nothing more that the mean, which can be taken for x and y separately. At this point, it will be easier to use matrix notation.  The weights w(i, j) will be aggregated into a matrix A defined as A(i, j) = w(i, j) when nodes i and j are connected and A(i, j) = 0 otherwise.  We will also use the diagonal matrix D in which D_ii is the sum of edge weights connected to i.

The two expressions above can now be written as:

D¯¹ A x = x

D¯¹ A y = y

At this point, an obvious solution is to place each node at the same place on the drawing.  Then every node is near to its neighbors, but the drawing is obviously not what we want!  Therefore, the equations must be modified.  One method of doing that is to change to note that the first equation is equivalent to

A x = D x

giving

(D − A) x = 0.

The matrix D − A is however exactly the Laplacian L defined above.  Thus, we are looking for eigenvectors of L with eigenvalue 0.  Now, L always has an eigenvalue of zero. However, its corresponding eigenvector is trivial, i.e. all its component are the same.  Therefore, we look at the eigenvector of L with smallest but nonzero eigenvalue.  Since it is known that L has only nonnegative eigenvalues, the second eigenvalue is what we need.  By the way, this smallest eigenvalue of L is called the algebraic connectivity of the network, and denotes how connected the network is. The corresponding eigenvector is known as the “Fiedler vector” and can be used for graph drawing.  Since we need to eigenvectors that are different, we can therefore take the eigenvectors of L with smallest nonzero eigenvalue to draw graphs.  The result looks like this:

In this example, the graph is the cube graph, and the drawing actually looks like a cube!  Note that we only used the adjacency information to draw the graph– not the fact that is depicts a cube as a three-dimensional object.

Antipodal Proximity

So if the network contains negative edges, how would we draw it?  We try to place points near to their positive neighbors, so let’s try to put them far away from their negative neighbors.  One way to do that is to use what one could call antipodal proximity:

Here, i is connected by a positive edge to j_1 and j_2 and by a negative edge to j_3.  Therefore, we draw i near to j_1, j_2 and to the opposite position of j_3.  (Just as the inverting amplifier has to be connected to earth, which has an electric potential of zero, we need to specify where the origin is located on the plane.)  When we now compute the mean of each node’s neighbors taking into account antipodal, we get the equation

A x = D x

just as before, but with D defined using the sum of absolute edge weights.  This gives the signed Laplacian L = D − A that we introduced to compute the signed resistance distance. Let’s apply this new method of drawing signed networks to an actual network with positive and negative edges: The relationships among the tribal groups of the Eastern Central Highlands of New Guinea! The tribal groups of the Eastern Central Highlands of New Guinea can be friendly (“rova”) or antagonistic (“hina”) to each other. The result is a network with positive and negative edges, which we can draw using eigenvectors of the signed Laplacian:

In this graph drawing, positive edges (friendships) are shown as continuous green lines and negative edges (enmity) as dashed red lines. The embedding of the Laplacian clearly put groups of friendly tribes together, and groups of antagonistic tribes apart.

Conclusion

To conclude:  The graph Laplacian can be used for networks with negative edges, as long as it’s defined by summing over absolute edge weights for the diagonal elements.  For completeness, I’ll mention that the signed Laplacian has only nonnegative eigenvalues just like the unsigned Laplacian.  However, its smallest eigenvalue is now always zero. In fact, it is larger than zero when all connected components of the network contain cycles with an odd number negative edges.  Also, the matrix D − A defined without using absolute values seems to be used in knot theory, see the reference [19] in [1].

References

This is my paper describing all this stuff:

[1] Kunegis, Jérôme; Schmidt, Stephan; Lommatzsch, Andreas; Lerner, Jürgen (2010): Spectral Analysis of Signed Graphs for Clustering, Prediction and Visualization. In: Proc. SIAM Int. Conf. on Data Mining. pp. 559–570.

Here’s my reference about the signed resistance distance:

[2] Kunegis, Jérôme; Schmidt, Stephan; Bauckhage, Christian; Mehlitz, Martin; Albayrak, Sahin (2008): Modeling Collaborative Similarity with the Signed Resistance Distance Kernel. In: Proc. European Conf. on Artificial Intelligence. pp. 261–265.

The relationships among the tribal groups of the Eastern Central Highlands of New Guinea are described in the following paper.  I have no idea how that data applies to the current situation of these tribes.

[3] Read, Kenneth E. (1954): Cultures of the Central Highlands, New Guinea. Southwestern Journal of Anthropology 10:1-43.

The actual data is available here.

All this is also covered by Chapter 5 in my PhD thesis:

[4] Kunegis, Jérôme (2011):  On the Spectral Evolution of Large Networks. PhD Thesis, University of Koblenz-Landau.

For another dataset of a larger social network with negative edges, see the Slashdot Zoo.

You may also be interested in:

• 9 Reasons to Have an “Enemy” and “Dislike” Feature on Facebook