Social Media Research Blog

Notes from DEBSM Workshop: Inferring Privacy Information via Social Relations

Inferring Privacy Information via Social Relations
Wanhong Xu, Xi Zhou Lei Li (presenter)

The presentation started with a neat quote: "Your social activities tell who you are". Social Networking are part of everyday life and for many of us a primary way in which we keep in touch with friends and family. Privacy is a huge problem in such networks. Li provided some statistics from a recent survey of British social network users: about  62 percent are concerned about the security of their personal data. 31% of the users falsify information to protect identity. This is a huge figure and definitely shows the level of concern.

This paper was motivated with applications for social advertising (which is a 2.2B US market). One can target users based on location, age gender etc. and social advertising allows advertisers to choose their audience. The problem comes up where users do not wish to disclose too much of their information online. The proposed solution is to automatically infer such missing information.

The authors use an undisclosed dataset for this study. The assumption is users fake personal information but not their activities. It is well known in offline-social networks that gender preference exist in friendship. however in online social networks this is not true (Jure Leskovec, WWW,2008). The key question that authors of this paper ask is : "Users may fake their personal information...But what about social activities?"

The insight that this paper offers is that certain group membership gives hints of user gender information. Joining groups has a gender preference. So the way in which one can infer the gender is to use a bipartite graph of users->groups with missing gender information using relation between users and groups. One approach is to use the User*Group matrix and build a classifier. However, they found that Naive Bayes does not work very well. Many social groups in fact dont have any gender preference. This can really hurt the classifier accuracy. So one approach they propose is to choose the discriminating social groups. i.e. groups that dominated by males or females. One major disadvantage that this technique suffers from is that the membership for users that dont join any of these groups can not be predicted. Once you restrict to the set of discriminating groups, now Naive Bayes performs well.

For users that cant be predicted they propose the use of an iterative algorithm to combine discriminative social groups and results from Naive Bayes classifier. Testing is performed by removing or making some data missing and then predicting the missing gender information.

My concern here is that the authors might have been able to avoid this disadvantage if they had used SVD to map the Groups to a set of lower dimensions that way it would automatically "cluster" the groups based on whatever the discriminating factor is (in their case the gender information). Secondly, while the authors had access to "verifiable" ground truth data, in real world how do we know the influence of fake profiles on these discriminative groups?

Clustering Tags and Links Simultaneously

I have a large collection of blogs that I would like to cluster. For the blogs in my collection, I have the following information:

• Text aggregated across all the posts
• A dump of the homepage of the blog
• Tags obtained from del.icio.us or "Feeds that matter"
• And finally how the blogs link to each other (aggregated across all the posts)

If we want to cluster the blogs, one can take the following approaches:

1. Cluster the blogs using only the text (Kmeans style)
2. Cluster the blogs using only the link information (By say performing NCut)
3. First cluster all the tags (so you would group "tech", "technology", "geek" etc) and then group the blogs that are categorized in each of these clusters.
4. Using a bipartite graph of the form <Blog,tag>. This is also known as co-clustering.

The problem with using the text alone is that the data can be huge (typically in Gigs) and it is almost essential to use some dimensionality reduction techniques like PCA etc. By performing NCut over the graph alone, you land up ignoring the text or the tag information that could be quite helpful. By clustering in only the tag space and then mapping the resulting clusters to the blog graph, we miss how the blogs might be interconnected. Finally, co-clustering technique too misses the fact that the blogs might link to each other and this information can be quite useful in grouping them together.

The question I was wondering about was how to cluster the blogs while using both the link and the tag information simultaneously. I think that the tags provide a reduce dimensional representation of the text. The tag space is of a much lower dimension than the complete text of the collection and it can be efficient to cluster the blogs using tags than the complete text.

Recently, I came across a very interesting piece of work that talked about "Classification Constrained Dimensionality Reduction". The idea here is that if we have a bunch of data points for which we know the true class information, we would like to classify the remaining points such that the available class information is utilized to guide the dimensionality reduction.

The above paper applied very well to our problem. One simple way to combine the two different information is to use the matrix W' shown here. C is a k*n matrix where n is the number of blogs and k is the number of tags. While W is the adjacency matrix of size n*n. I is an identity matrix of size k*k. Typically, we can get away by using only the top 200-500 most popular tags. Now, if we perform NCut using the matrix W' instead of using W alone, we can combine/fold-in the tag information with the link information. The parameter \beta controls how much importance we would like to give to the graph versus the tag information.

For example for a blog graph consisting of ~3000 blogs, I fetched the tags from del.icio.us and the link graph from the WWE/Buzzmetrics collection. Figure on the right shows 20 clusters if we use just the link information and perform NCut and the same graph using the simultaneous clustering method. Notice, how the 20 odd clusters seem nicely block diagonalized in comparison with the results using link information alone. It would be interesting to look at how these techniques compare with that using the entire text from all the blogs. I am working on this and the intuition is: we might be able to show that using just tag and link information, we can do as good (or better) than using the entire text. Afterall tags are nothing but a place holder for the "topic" of the blog.

An even more interesting extension would be to use the original paper that presented the constrained classification using dimensionality reduction and apply the same technique to our problem, such that we can perform clustering using just a small set of labeled blog and labels (matrix C).

Notes from DEBSM Workshop: Monitoring the Evolution of Interest in Blogosphere

Monitoring the evolution of interests in the blogosphere
Iraklis Varlamis (Presenter), Vasilis Vassalos, Antonis Palaios

The authors present a simple (perhaps even obvious) hypothesis that "Interests of bloggers converge around real world events".

A prototype system was built to to analyze blogs and monitor the evolution of interests. Existing search engines monitor the term popularity of words in isolation and the related terms are not clustered in any way to identify the topics. A motivating example presented was around the football world cup season, where there might be terms like "football" "round" "final" "result" "world cup" and aggregated scores for topic would be helpful rather than having to find/view the histograms for each of these terms. Also one can not know all the terms for a given topic. In many cases, multilingual content and difference in vocabulary can further make it difficult to just monitor the term popularity. Other approaches require training a topic based on a given set of training/pre-annotated document pool. This is an expensive and a semi-supervised method can be strongly effected by the selection of the initial document pool.

The goal of their paper is to build an unsupervised approach to cluster the documents and identify the evolution of interest. However, the current algorithm presented is not incremental; but they claim some recent work on an incremental version. The current version of their algorithm uses the DBScan clustering technique. Term space is clustered at the post level and their evaluation is done using inter cluster, intra cluster similarity and the utility function. They have used the BuzzMetrics dataset, however they only focus on blogs that have a post everyday, which brings the dataset down to 2500 blogs. The posts are classified into topics and then the blogs are clustered. The categories are determined by using the Cyberfiber news groups to find the topics and training documents. This is an interesting dataset that I was not aware of.

Some questions that came up were the choice of using newswire documents to learn classifiers, and also the accuracy of the classifiers. While the original hypothesis seems obvious, it can be seen as a litmus test for the efficacy of the clustering algorithms. In particular the examples presented were using the "London Bombing" Event. Any clustering algorithm that groups the related terms must at the very least pass the litmus test to show that it works.

I think that in general there are perhaps two types of events, one concerning a very specific group of individuals  ("County elections", social events, conferences etc) where online communities emerge due to offline events. The other is around real word events like "London bombings" or "Hurricane Katrina": both of which are examples of events that cut across community boundaries and which invoke reaction from almost every part of the blogosphere and almost in unison. In such cases on might see that the original community affiliation of the bloggers dont matter and tech, politics, religion and every other community might be talking about the same issue.

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?

Measuring Similarity in Social Media?

What is similarity? Does the richness of meta-data and the range of content in social media make it harder to define similarity in the context of Social Media? Jonathan's comments reminded me of a few thoughts I had recently on similarity in Social Media. And I think Jon raises a critical point which applies to this post as well. Like relevance, how we define similarity would really be dependent on the task.

Nevertheless, the traditional view of similarity measure is in terms of document similarity measured using cosine similarity. An extension is that rather than using content similarity, some researchers model topics using techniques like LDA, thus resulting in topic similarity. While, content/topic similarity is surely still used in blog analysis there are wider set of interesting features to build on.

Tag Similarity: Folksonomies for instance offer user-generated tags. This is a helpful feature to find out if two blogs are somehow related. The tags used by the author of the post is another feature. These may or may not correspond with the tags used by their readers (or on bookmarks in del.icio.us). I find it interesting that these two may often complement each other. Authors might tag their posts with specifics (like "Hilary clinton", "immigration" etc), while the reader can simply categorize the blog under a general tag "politics".

Community Structure: The graph itself has cues that offer hints about the similarity between two blogs. Community structure is definitely of importance and blogs that structurally belong to the same cluster are often related. The slight issue is that link semantics in the Blogosphere can be different from that of the Web.

Link Semantics: Traditional view of links is that of endorsement, but in the Blogosphere, sentiments may even play a big role. Related with link semantics is also the question of relation-type. Blogrolls and linkrolls are yet another way in which two blogs can be related. Adding a blog in my blogroll might not necessarily mean that its topically related -- it could just mean a sort of vague friendship / foaf:friend type of a relation.

Additionally, a significant percentage of links created on blogs point to main stream media. One can consider this as a bipartite graph  with blogs and MSM sites as the two node types. Clustering blogs that point to similar set of MSM sources can reveal additional similarity cues. This would be more particularly distinct in political domain.

While I approach this question from the viewpoint of blogs, social network and flickr communities have still further relation-types and features. In such systems comments, group memberships, affiliations etc. can be additional indicators for similarity measures.

I believe that it is still an open question how such varied features can be utilized to measure similarity in Social Media. I am sure that there are going to be a TON of interesting discussions on some of these issues at ICWSM, which I am eagerly looking forward to.

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!