Social Media Research Blog

Exploring the Impact of Profile Injection Attacks in Social Tagging Systems

Live blogging from WebKDD 08:

Exploring the Impact of Profile Injection Attacks in Social Tagging Systems
Maryam Ramezani, J.J. Sandvig, Runa Bhaumik, Robin Burke, and Bamshad Mobasher

Explores how folksonomies can be used for social navigation and protect it from 'self-promotion tags'. in profile injection attacks, users create number of identities and add 'tag spam' for malicious intent. Spurl.net is an example of a social tagging system that was inundated with spam and had to shut down.With various entities (resource, tag and users) the profile injection attacks can effect each of the 'navigation contexts' like: related resources, co-occurring tags, recent items etc. The paper goes in depth into the various classes of such attacks. The paper uses del.icio.us crawls for this study that were split into three partitions: low freq, med freq, high freq.

Two main types of attacks discussed:

• attacks on popular tags
• Piggyback attack: force association of a particular resource with another resource to make it look similar.
• Overload attack: associate popular tags with a target URL.
• Focused overload attack: for a specific target users (say those, using the tag coffee) associate the target URL with those tagged as coffee

One interesting point is that piggyback attack is a problem mostly in the Low and medium freq partitions and just 3-5% of fake user profiles injected (using relatively few number of tags) can cause considerable problems in social tagging systems. The authors present various results based on number of tags, number of profiles etc.

I think as tagging systems become more main stream dealing with spam in such environments is quite important. 

Only 10 Cherry Picked? Thats not Enough!

Sixapart re-launced Blogs.com as a blog directory... yawn! (Wow! A Yawn is really contagious... via techcrunch's coverage -- the Yawn cascade initiator).

Seriously.. Sixapart? I am sure you could do a lot better than having an expensive team of editors cherry pick their favorite blogs in a handful of categories. You guys have a ton of good, high quality blogs and the interesting thing is that you can use some of the tag information to cluster these blogs into the different communities they belong to. For example blogs that talk about business are likely to use tags like marketing, advertising, finance etc. Algorithmic approaches can be effectively used to mine blog graphs to find high quality feeds.

At eBiquity, we have looked at this problem from two different approaches:

• Using readership information from Bloglines, we can cluster the blogs based on how people subscribe and categorize their feeds. Although typepad probably does not have access to subscription information it has other sources (like what tags are used by the blogger, and the number of people visiting and commenting on the blogs) to come up with a much better directory. Something on the lines of "Feeds That Matter" (see site here, bit outdated though).
• More recently, I have looked at how we can combine the graph structure and folksonomy information to identify communities in social media. This was an Idea that I first shared on this blog and subsequently submitted a paper, which I would be presenting at this year's WebKDD workshop.

The point is, I beleive that the top 10 offered by sixapart and bloglines are not really that interesting anymore. In the era of hundreds of thousands of potentially good blog (of the millions that exist), we can rely on algorithmic approaches to find (more than just 10) high quality blogs. This is also related to the "Feed Distillation Task" that TREC ran for 2007. If you are interested in feed distillation... check out CMU's submission by Elsas et al. and the follow up papers by Jon at other venues.

Another challenge is being able to find not just popular blogs but also that cool blog that probably be down there somewhere in the long tail.

Del.icio.us + Google Custom Search = Delizzy

In my April 9, 2008 blog post on "Social Tagging and Vertical Search" I had talked about exactly this idea:

For quite some time now I wanted to build a mashup using the social tagging information from del.icio.us and combine it with Google's Custom Search engine. This is a neat way to build high quality vertical search engines. (For example we could use all the URLs under the tag "astronomy" to build an astronomy vertical).

Well, it was just waiting to happen. Delizzy (via Techcrunch), is a wonderfully simple idea but it is a super cool site built using del.icio.us and Google Custom Search. It lets you do what del.ico.us has surprisingly, still not yet provided -- A full text search over your bookmarked items. I believe this could be taken a step further and built into custom search engines or verticals for different topics. Imagine searching over only highly bookmarked sites for a particular topic like "AJAX" or "Ruby on Rails" or "Artificial Intelligence".

In any case Delizzy is pretty cool. Go check it out!

Clustering Triples from Social Data

By far, the most prevalent data available in social media is tagging information. For example, in del.icio.us a user may tag a URL or in Flickr she may tag an image. One of the questions that comes up is how to then cluster social data that is rich in tags. Some techniques available ignore the user information and use only a bipartite graph consisting of tags and URLs. Another method is to represent two pieces of evidence (user-tag;tag-blog) in a tripartite graph (where nodes are of three different types: users, tags and urls). However, even this type of structure actually  misses the higher order relation between the three nodes. Note that the information available is really in triples of the type <user, tag, url>. This information is not captured by the tripartite graph model. In particular, two users may be connected via a common tag even if the actual URL they bookmarked is vastly different.

There are some techniques using Tensor Matrix Factorization that can handle such data. However, the question of how to deal with triple (or higher) information from social data is quite interesting. Moreover, being able to do so efficiently and in an online fashion would also be important. I believe that this topic may be of significant interest in the upcoming social media and data mining conferences. The implications of these techniques would be in building better recommendation systems and personalization algorithms.

[Thanks Vlad Korolev for some of the discussions related to this post]

Wordle: Create Beautiful Tag Clouds

Briefly; via Harry Chen:

Worldle is a neat tool to create pretty looking tag clouds. Enter text or your del.icio.us username.

Here is my tag cloud from del.icio.us

looks awesome, no?
Thanks Harry!

The Cost of Manual Annotation

For many machine learning tasks it can be quite difficult to get the "ground truth" data. In some cases the best way to verify the results is by a painful, laborious and mindnumbing task of labeling data manually. When Pranam and I were working on the Splog detection task, we spent a good deal of time painstakingly labeling independently if a blog from a random sample was legitimate or spam. The part that makes this task difficult is:

• Sometimes it is not clear when something is a blog is a splog
• You need to also look at the inlinks and outlinks
• Plagiarized content makes it harder to judge authenticity
• Sploggers are getting more sophisticated in the methods they are using

On an average we spent about 2-3 minutes per blog and in the end, were only able to hand label a small collection. In comparison to many other tasks this was still a relatively straightforward judgment. Consider the task of relevance ranking that NIST has to perform each year for the TREC tracks. Here the goal is for the annotators to figure out if a result is relevant for a query. The guidelines are strict and NIST has many professional annotators who are trained to perform these tasks. Even more complicated are some of the annotation that might be required in certain Natural Language Processing experiments. These can range anywhere from just verifying a parse tree or an output to actually constructing gold standards or hand crafted parse trees. Moreover, some NLP tools require tremendous amounts of linguistic resources -- be it tediously constructing an ontology, lexicon, gazetteer lists or identifying word senses. Many of these tasks require linguists or experts whose time might be quite valuable.

lets consider a simple case where the annotator was asked to label a URL with a tag. Lets also say that it takes roughly a minute to load the page, quickly glance over it, make a judgment and then type in the appropriate labels. I know from experience that this is not a minute but more like 1.5-2 minutes on an average (try it! it is a braindead boring task and if you are asked to do it continuously, you will slow down!). If say I can work 10 hours on this task without loss in quality of my annotations, it would only result in 600 URLs being tagged. UMBC pays lets say around $10/hour for on-campus jobs. That means we would spend about $100 just to label 600 URLs. Not so sure if that would be the best way I would like to spend a hundred bucks! Additionally, just one human annotator is never sufficient. You always need to answer questions like : "So, what was your inter-annotator agreement?". Well then you just blew another $200 or $300 on this task and still have just 600 URLs marked up. No wonder del.icio.us and Flickr are such amazing sources for free (yaay!), human assessed labels and annotations. It works out great if you can use these instead.

Mechanical Turk is an attempt by Amazon to make it easy for such tasks to be distributed to people who would perform them in return for small micropayments. However, it seems to me that the incentive for completing the task (or doing it well) is so minimal that there is very little enthusiasm around this product. I suspect, the only people completing these HITS are individuals in countries where the dollar still has some value. In fact, there seems to be something fishy about atleast a handful of HITS that are high paying. It looks like the system is totally getting gamed by spammers - look at this example requesting 20 backlinks to a site ($3) or creating bogus accounts ($7) and likes.

The most interesting tool for manual annotation that I have ever seen is the ESP game. It is an excellent entertaining and I must warn you totally addictive. The game works by showing you an image and asking you to label it. You are randomly paired with another player and both get a score if a word matches. This totally ingenious way of collecting annotations for images means that the annotations come absolutely free of cost!

To bring the cost of manual annotation to zero or close to it the best incentive is to provide some value to the annotator. Ofcourse some tasks are so specific or specialized that this might be truly difficult without actually paying someone to go through it. 

From a research perspective, when we build a classifier and use the UCI dataset we have a good "gold standard" and accessible body of literature that has studied the very same data. But as we are dealing with ever increasing size of datasets, access to ground truth or manually verified samples is becoming even more challenging. So is the significance of using it. What does it really mean to annotate less than 0.1% of the data (say you have a very large collection of blogs, images, graph -- whatever social media content you can imagine)?

[Image Courtesy http://www.socialfiction.org/]

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).

Social Tagging and Vertical Search

I love del.icio.us! Its a superb resource to easily share bookmarks. One neat thing about del.icio.us is that the quality of data they have is just fantastic. For most of the popular tags we can find a bunch of very high quality sites that are relevant to the tag/topic. No wonder Yahoo! has been so keen on integrating del.icio.us data into it's search. But I just wish they did more with del.icio.us.

For quite some time now I wanted to build a mashup using the social tagging information from del.icio.us and combine it with Google's Custom Search engine. This is a neat way to build high quality vertical search engines. (For example we could use all the URLs under the tag "astronomy" to build an astronomy vertical).

The closest tool I have found to what I describe here is Swicki. It is a really neat widget to build customized search engines. An awesome feature in Swicki is that I just need to list a few URLs and it learns the related URLs automatically.

Once the vertical search engines is built, Swicki lets you search for an appropriate vertical. One thing I think might be interesting is to recommend and combine related verticals. For example, for the vertical search engine "Astronomy" the related verticals could be "Physics", "Cosmology", "Thermodynamics", etc. We could go even further by combining verticals. I could run my query on a combined vertical using "Astronomy" and "Biology", to search for topics related to Astrobiology,  for example.

Another early tool was Rollyo, which allowed users to build custom search engines; I believe, it got overshadowed by Google Custom Search.

I would love to build something like this for del.icio.us. Perhaps, a mashup using del.icio.us and Yahoo API or Google Custom Search. If only, I did not have to cheat and sneak upon del.icio.us servers to crawl their data to do this! Currently, their API is limited and does not offer a simple way to get the list of highly ranked URLs for a tag. Additionally, they are pretty quick with blocking any bots. I have been gathering some data from other sites like Yahoo myWeb 2.0, Furl etc. but these are often highly spammed and frankly not as high quality as del.icio.us.