Social Media Research Blog

Laplacian Eigenmaps

In the previous posts I talked about some of the papers I have read recently on spectral clustering and graph based methods. I wanted thought I would provide one more example that would try and explain the use of graph Laplacian. The basic idea is that the graph lies on a 'manifold' which, to completely simplify it, would mean that the graph lies in some multidimensional space.

For example, here is a random dataset that was generated using three Gaussian distributions. In order to obtain a graph from these points, an RBF kernel was used. The corresponding graph Laplacian is then computed from this kernel. When we project the data onto the vectors corresponding to the second and third smallest non-zero eigenvalues , we can see that the three Gaussian distributions are clearly distinguishable. This type of projection is known as Laplacian eigenmap. For more details please refer paper by Niyogi et al.

As  an example of how this applies to the community detection / Semi-Supervised graph learning problem, here is a graph of the political books dataset. The corresponding  projection is shown below. While most of the conservative and liberal books can be identified some neutral books are a bit ambiguous making them harder to classify correctly.Typically, in case of spectral clustering we would only need to consider the second smallest eigenvector of the graph laplacian. It is also known as the "Fiedler" Vector and is used in graph partitioning.

Please note that this series of blog post on spectral methods is my attempt to share my understanding of the papers I have read recently. I am happy to receive further references and clarifications of the points discussed here.

Labeling Blogs using Graph Regularization

Recently I learned about semi-supervised learning over graphs. Using a small number of labeled nodes, the task is to find the appropriate nodes that belong to the same class as the labeled, training data. This problem is typical in Web spam detection where some hosts are identified as spammers (possibly manually) and the goal is to automatically tag the rest of the hosts as either spammers/non-spammers.

A similar task can be formulated for learning the labels in blog graphs. For popular blogs, it is not hard to find good quality labels using either Bloglines or del.icio.us. Often these labels are most reliable for popular blogs that have been tagged by many readers. Now in order to find out the other blogs that share the same label, a method recently suggested is Graph Regularization. (And for an overview on label propagation methods here is a nice tutorial).

Graph regularization uses the spectral properties of the graph to find a function that satisfies the following two constraints:

• Smoothness Constraint
• Fitting Constraint

According to the smoothness constraint, nodes that are close to each other in the graph would have the same label. On the other hand the fitting constraint ensures that the final label assignments do not deviate too much from the training data. Thus imposing a penalty for misclassification of training examples. The two constraints can be formulated in terms of the graph Laplacian. For details refer Zhou et al.

As an example, for a small blog graph, I obtained the del.icio.us tags corresponding to each blog. Empirically, I find that del.icio.us tags provide very good description of the blog. Once the tags are obtained (I used the JSON API), I use just 10 blogs tagged as "sports" and use the above regularization method to find other blogs that might be similar. The final scores (see figure, right) after regularization correspond to the community structure (found using Ncut, left) as shown in the figure below.

Here is the list of some blogs that were categorized under the label "sports", starting with the training set of 10 blogs.

In my opinion, two things stand out... one the Ncut algorithm itself may be improved if it was to be using additional tag information. Secondly, label propagation for blogs is slightly more complicated than just the original binary classification (spam/not spam) problem. One could have a few hundreds different labels that might need to be propagated, moreover -- the labels themselves may be quite related ("tech","technology","Programming", etc). Adding the constraint that labels should be propagated, subject to some known distribution makes optimizing the above cost function slightly more complicated. Furthermore, a blog may be equally relevant to two very different labels -- "politics" and "sports".

Any thoughts? Other techniques that might be useful? Ideas on how inter-related, multiple labels, can be propagated over a graph?

Random Walks and Spectral Clustering

Interestingly, Random Walks and Spectral Clustering are quite closely related. As I dig into the literature, I find this body of work quite fascinating. I had read earlier about this connection between random walks and spectral clustering,  however I found a neat paper by Dr. Marina Meila that provides a very clear explanation. 

As an example, consider a small dataset of political books. Using Ncut (on the left) there are 3 communities that were identified. Now if we were to perform a random walk on this graph the probability of transitioning from node i to node j would be given by

Pij = Aij /sum(A(:,j));

In other words P = inv(D)*A; where A is the adjacency matrix for the graph and D is a diagonal matrix with degrees of each node. Thus P is a stochastic matrix, with all its rows summing up to 1. The result of which is shown in the graph on the right. Ofcourse, for very large graph the main difficulty is really the computation of the inverse, which can be quite expensive. And that is exactly where the NCut formulation of the problem comes in handy, since it does not involve the inverse. Normalized cut is  performed by using the second smallest eigenvector of the graph Laplacian (L = D - A), to partition the nodes of the graph. The interesting thing is that the eigenvectors of L and P are the same and if \lambda is the eigenvalue of L the corresponding eigenvalue for P is (1 -\lambda). For more details refer Dr. Marina Meila's paper. Quite interesting!

Spectral Graph Partitioning

Spectral Clustering is a really simple and effective technique for graph partitioning and it can be easily used  for community detection tasks. Although running spectral clustering tools or writing a basic algorithm is only a few lines of code, sometimes the intuition of how it works is not quite obvious. I don't claim to be no expert either, but I have been exploring how it can be applied to problems in Social Media graph analysis and am quite excited about this technique.

A graph can be expressed in terms of a similarity matrix. Spectral analysis of graphs deals with the study of properties of the eigenvalues and eigenvectors of the adjacency/similarity matrix of a graph (often expressed in terms of a Laplacian matrix). A simple version of the graph Laplacian is L = D -A, where D is a diagonal matrix containing the degrees of each node and A is the adjacency matrix. One way to think about this is in terms of Fourier Analysis. A periodic function can be represented in terms of sine and cosines such that the sum of cosine and sines can smoothly explain the function. Similarly using the graph Laplacian, what we are trying to achieve is a smooth approximation of the function f(x) over the entire graph. Such an approximation can be achieved by minimizing an objective f'Lf.  

Another interesting explanation is the one offered by matrix perturbation theory. Imagine that the nodes of the graph were golf balls tied together by strings (which stand for edges). Now if the entire graph was laid out on a in space and a small perturbation was introduced by hitting a single ball, how would the rest of the balls in this network move? Balls that are connected  via multiple paths and those that are closer to the original ball that was perturbed would fluctuate more than the rest. Similarly, what f'Lf does is find a smooth function f, over the entire graph such that it would approximate these perturbations over the graph.

Here is a nice Matlab based tutorial and for computing Normalized Cut, Shi and Malik's implementation is very handy. For example, shown below is a sparsity plot of a graph of 6000 blogs. By running the Ncut algorithm, with about 100 partitions the community structure in it become clearer.
While spectral methods for graph analysis have their origins in image processing, they are finding a number of significant applications in Social Media analysis. They seem particularly attractive because of their relative ease of implementation and excellent results. For a perspective on this topic specifically from a community detection point of view, a good paper to read is by Dr. Mark Newman. Since blog social media data is so different from images, several new extensions have been suggested to incorporate different characteristics of such networks. Some recent trends are: evolutionary spectral clustering (temporal behavior), graph regularizations (semi-supervised learning/classification on graph data) among many others.

 

My Twitter Visualization Featured in Technology Review

A few months back, I had been analyzing Twitter's social network. This meme was recently picked up for a photo essay in March/April issue of the Technology Review Magazine. You can read an online version here. It also has a number of really cool visualizations from other researchers who have been studying the "social graph". For this visualization, I had used the Large Graph Layout (LGL) tool to visualize the social network on Twitter. Following is a graph constructed using contacts from about 25K users.

One of the challenges in laying out large graphs and social networks is that it is often hard to interpret what these graphs signify. To get a better understanding of the information in such networks, we inevitably need to look into the underlying community structures. My paper titled "Why We Twitter: Understanding Microblogging Usage and Communities" tried to answer these questions.

On Approximating the Community Structure of the Long Tail

Social Networks and Web graphs exhibit certain typical properties. The classic work by Barabási–Albert showed how nodes in such network link preferentially -- popular nodes often gain disproportionately larger share of the links. This is also known in other fields as the 80/20 rule or simply the "rich get richer phenomenon".  Another early work by Steve Borgatti studied social networks and found that they exhibit a core-periphery property. A small set of (popular) nodes form the core and the rest comprise of the peripheral nodes. To the best of my knowledge, community detection algorithms have often worked independent of the underlying network properties.

I have been exploring an idea that can utilize the core-periphery structure of social networks to approximately compute the communities in the graph. The intuition behind this method is really quite simple. The basic idea boils down to the following:

"The core of the social network typically defines the communities present in it. By looking at the link structure of the core and identifying how the rest of the network connects to the core we can efficiently compute communities in large graphs."

This idea can be easily explained by considering the following network of email communication (obtained from Dr. Mark Newman's site). The original adjacency matrix was permuted to order the nodes based on  their degree. Thus the core is represented by submatrix A which is quite dense. The submatrix B, here corresponds to how the rest of the network links to its core. The submatrix C is a very sparse matrix that consists of links between nodes in the long tail. From a mathematical point of view this is quite sparse and can be ignored, without much degradation of the clustering/community detection results. Thus it leads to saving a significant amount of computation and storage. By utilizing just the core of the social network (matrix A) and how other nodes link to the core (matrix B) we can approximate the overall community structure of the entire graph, much more efficiently.

The rest boils down the to the mathematical formulation of the above idea. You can read more about it in my poster paper that was recently accepted to ICWSM. (Available for download on 02/16/08)