Social Media Research Blog

SXSW Panel on Collaborative filters

I am at SXSW this weekend and wow what a conference this has been! Met a lot of cool people and been to a bunch of happening parties! I plan to post a few updates about the conference. In the mean time here is a quick post from notes I wrote during the panel discussion on Collaborative Filters.

Anton Kast from Digg.com gave a brief history of collaborative filtering from the research literature covering tapestry (from parc) grouplens (UMN) and a few other projects mostly from 1990s and draws comparisons to current systems used in spam filters, pagerank , tagging systems and applications in facebook ads etc. The talk wasnt very technical and meant to be a quick overview for the audience that might not be familiar with the research background. Kast described recommendation as the output of collaborative filtering that is personalized for a particular user in the system. For example  amazon (people who bought this also bought..), behavioral ad targets, google news etc. I wish Kast had spent more time discussing the last slide which covered practical problems: sparsity problem in recommendation systems, early rater problem/cold start, gray sheep (small group very popular).

Erik Frey from last.fm shared some interesting stats -- 25m unique users/month. The types of relations that last.fm derives: songs-users, users-users. He also shared some insights on what were described as lean forward and lean backward mode in music recommendation systems. The lean forward mode is when a user is feeling a little experimental and would like to discover new stuff. The lean backwards mode is when the emphasis is on continuity and the desire to listen to something familiar (i.e. radio experience). The two main data sources for last.fm are : scrobbles, social info like tags. Frey suggests that tags are quite useful to explain recos

The next speaker was the cto of baynote -- a recommendation system that is provided as service using javascripts that enables clients to customize their website in real time based on user behavior. They also apply it for reordering the search results.

Finally, Jon Sanders from Netflix gave a very good talk covering the history of netflix and its evolution. Today netflix has about 2 billion ratings and gets about 2 M ratings per day. 60% of movies watched are via personalized recos -- amazing!

Following were the steps in evolution of netflix:

step 1 At first netflix was a editorially managed site and the first evolution was that of adding a rating widget.

step 2 score and sort all movies using rating alone (top k list)

step 3 movie similarity by k-nearest

step 4 interest based recos (same actor director  etc)

step 5 ask ( get users to rate genre)

step 6 ask others (top 10 lists from users)

step 7 explain why (because you enjoyed)

step 8 $1M prize

step 9 develop a unique experience and customized website for each customer

future: streaming video specific recommendations, incorporating implicit and explicit metadata, discovery focus, let people drive and not be led.

Ranking Nodes via Random Walks

A few days ago, we were discussing a research problem in the lab. It reminded me of two papers I had recently read. The problem that we were talking about involved a graph where we knew certain nodes of interest and wanted to identify and rank other nodes that might be relevant. This is a classic example of a situation where random walks can be quite effective. Following are brief summaries of two papers on this topic:

The first paper titled "Ranking on Data Manifolds" is by Dr. Dengyong Zhou. It is discusses a neat interpretation of a random walk. Following excerpt from the paper describes the basic intuition:

"We firstly define a weighted network on the data and assign an authoritative score to every query. The query points act as source nodes that continually pump their authoritative scores to the remaining points via the weighted network, and the remaining points further spread the authoritative score they received to their neighbors. This spreading process is repeated until convergence, and the points are ranked according to the amounts of authoritative score they received."

Manifold is defined by Wikipedia as:

an abstract mathematical space in which every point has a neighborhood which resembles Euclidean space, but in which the global structure may be more complicated.

(rdfs:seeAlso Wolfram page on manifold)

So basically, one can think of a graph or a social network as data that lies on a manifold. In order to learn and capture the structure of the manifold a the Laplacian Matrix is used to represent the original graph. The advantage here is that the Laplacian is capable of capturing the long range relations between the nodes and ensures overall smoothness when propagating the scores on the manifold.

As the scores are iteratively spread from the nodes of interest to the neighbors (via the graph laplacian), the algorithm converges and corresponds to the random walks in the graph. The final scores provide the overall ranking of the nodes, with respect to the initial nodes of interest. The applications of this method range from image processing to web search and recommendation.

I really like this paper for its simplicity and clarity in explaining the connection between random walks and node ranking.

The second paper I would like to mention here is "Fast Random Walks with Restart and its Applications" by Hanghang Tong et al. It is a really nice paper that talks about how random walks can be used to identify how close two nodes are in a graph. Moreover, the paper discusses some really neat mathematical tricks that can be applied for efficient, "on the fly" computation of the random walks in large graphs.  The basic intuition is to use the Sherman-Morisson Lemma to avoid directly computing the inverse of a large graph (which is prohibitive). This is actually a superb trick to use, especially when doing rank one updates. A number of applications are discussed in this paper, including image retrieval and neighborhood formation etc.

There is a more recent work by Alekh Agarwal and Soumen Chakrabarti on this topic, "Learning Random Walks to Rank Nodes in Graphs". There are many more papers and I have probably not read them all -- these are just a few of my favorites on this subject.

Learning Preferences of New Users in Recommender Systems: An Information Theoretic Approach

Liveblogging from WebKDD 08

Learning Preferences of New Users in Recommender Systems: An Information Theoretic Approach
Al M. Rashid, George Karypis, and John Riedl

[Update: This was the winner for the best paper award]

This paper is addresses the cold start problem in collaborative filtering, i.e. for new users since the system does not know of the user's preferences, the system cannot recommend items. This paper looks at a few different heuristics:

• Popularity of an item. The system picks most popular items and presents the new user with these. If the user rates these items, it constitutes the initial profile. The interesting point they note is that a good strategy is to pick popular items that have a varied rating distribution. The downside is unpopular items are harder to predict.
• Entropy: identify informative items. Downside is that entropy does not pick the right item when the ratings are few.
• Entropy0: treat missing ratings as separate rating items. However, this favors popular items more.
• HELF: combines entropy with popularity.
• ICGN: Information gain through clustered neighbors. Use ratings so far to determine what is informative next.

Evaluation was done on the MovieLens recommendation system.Overall ICGN and Entropy0 perform the best.

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.

List Crazy Diggers

[UPDATE 08/22/2008, 12:10 AM]

I wonder why diggers are just list crazy?

At the time of writing this post (yesterday), here are the 'lists' from the top 100 diggs on the digg front page -- almost 16 of them! What this means is that on every page there is at least one 'list' type of an item. (And I have noticed this trend for some time now)

1. 5 Reasons to Write Down Everything You Eat For a Week

2. 6 Worst Movie Posters Of 2008

3. 15 Fugly Faces of George W Bush: Commander in Grief [PICS]

4. 10 Movie Trailers That Were Better Than The Actual Movie

5. 10 Coolest Chuck Norris T Shirts Ever!

6. 7 Principles Of Clean And Optimized CSS Code

7. 15 Images You Won't Believe Aren't Photoshopped

8. 10 Great Webcomics You Should NOT Share With Your Kids

9. The Top 10 Rookies That Will Impact the NFL This Season

10. The 5 Most Baffling Sex Scenes in the History of Fanfiction

11. The Top Five Weirdest Olympic Events!

12. 9 Linux Myth Debunked

13. Stephen Colbert's Top 7 Drug Moments

14. The Top 7 Girl Gamer Stereotypes

15. Top 10 Songs Over 10 Minutes Long

16. The 10 Skimpiest Superheroine Costumes

Lists can be entertaining and fun. But I wonder why we see lists enjoying such high popularity in digg? From a cursory glance, the comment activity on 'lists' is comparable to any other item. So my guess was simply that the 'Top Diggers' have a greater inclination towards lists. 

[UPDATE 08/22/2008, 12:10 AM]

To understand what was going on here, I turned to the expert, Dr. Kristina Lerman, who has extensively studied the Digg Community. Following is an excerpt from her response to my question about the popularity of lists on Digg:

"......did you notice how the amount of communicated information is shrinking? First we had Twitter, that advertised 128 chars or less in a message. Rather than being an inconvenience, other services followed the trend: "videos in 5s or less", or other bite-sized chunks of information. Lists are part of that trend, but not only do they communicate information in a convenient bite-sized chunk, but they also rank them - another passion of the current age. It seems that people are really averse to expressing thoughts in long paragraphs." [Text highlighted by me]

Digg is essentially a news site, but the audience probably loves the quick, bite-size and neatly ranked information that such posts provide. Even on traditional news reports and TV shows the "top 10"   whatever-odd-ball-potpourri land up being a part of the reporting.

Here are links to some of Dr. Kristina Lerman's papers on digg and a video of her talk (@Google) on Social Information Processing.

Kristina Lerman (2007), User Participation in Social Media: Digg Study , in Proceedings of the International Workshop on Social Media Analysis (SMA07), Conference on Web Intelligence and Intelligent Agent Technology [pdf] [bibtex]

Kristina Lerman (2007), Social Networks and Social Information Filtering on Digg, in Proceedings of Int. Conf. on Weblogs and Social Media, Boulder, CO,USA (poster). Extended version available on arXiv (cs.HC/0612046)

Thanks Kristina for your sharing your thoughts on this new trend!

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]

The Cold Start Problem in Social Media

The Cold Start Problem in Social Media

Here is a classic cold start problem:

• "Social Tools" can only be social if there are enough people on it.
• And any social site is only as attractive as the number of friends you have on it.
• The social site is only useful if there are enough people contributing to it. (be it annotating images, links or adding reviews)

The question is how do you get enough users to adopt a tool and build sufficient traction around it such that it attracts more users? I dont have all the answers and perhaps entrepreneurs and folks in startups are more knowledgeable about this than I am. But this is a question I have been pondering about for some time. Most of these points might be fairly obvious, but here are a few thoughts I'd like to share:

• Above all, build something cool!
• Realize that in many systems, 1% users acting as contributors is all it takes! (see Clay Shirky's book "Here Comes Everybody" for more on this). Ensure that the reward mechanism is automatically built into the site. These 1% of all users are not the ones that are motivated by money. They use your tools because they enjoy it or it solves some real problem they have been facing. I have seen some sites trying to "pay" users to add data to "seed" their site. For example, check out some of the high paying HITS on Mechanical Turk. In my opinion, this is like throwing money out of the window. Completely bogus way to jump start your site!
• Provide APIs: One of the key factors that contributed to the success of Twitter was that they had a neat API that developers immediately adopted and had fun building cool toys. These 3rd party tools in turn make it easy for users to contribute and engage with your site, thus breaking the cold start problem. For example, even though not developed by Twitter, the plethora of third party twitter client make it easy to easily update your Tweets. 
• Try to "seed" your site with datasets curated by web crawls, APIs, external databases or using the tools yourself. For example, if you are building a site that uses geotagging, you might consider using sites like geonames.org or if your site is around movies -- use IMDB or Amazon data to seed it.
• Make sure stuff is findable and socially visible. Make it easy for your users to find the data they really care about and they will be willing to annotate. Moreover, make sure that it is easy for users to share what they annotate with their friends. The beauty of Facebook is the news feeds. People like to know what their friends are upto. On Twitter, I want to know what my friends are saying and be able to have conversations with them - without that twitter is just a chat room.
• Dont ever SPAM! Every week I have a bunch of emails coming from some random sites that a friend of mine once joined. Make sure that in your invitation email you include an option to not receive any requests from your site in the future. I am amazed when I dont see this option at all. If a user does not wish to join a network, please dont keep sending them emails requesting them to join every time one of their friends sign up! Also, I am a sucker for alpha/beta testing for any new social media/social network site. Sometimes, I try even the ones that eventually land up spamming everyone on your email/IM. As a RULE -- never spam your potential users! That is the best way to piss them off even before they join it.
• Listen and iterate rapidly. Your alpha/beta users are the most important. Listen to what they have to say. Also, if you cannot convince your friends and family to use the tool -- why would anyone else bother?

The cold start problem has been studied in computer science, particularly for recommendation systems**. A good place to start is the paper:

Methods and metrics for cold-start recommendations  Schein, r.I.; Popescul, A.; Ungar, L.H.; Pennock, D.M. [Link]

I am quite interested in knowing how startups have approached this problem in real situations and particularly, if there is any analytical data available to show what worked and what did not? I guess this might be information that few would be willing to share so openly.

** on a related note: The blog "Duke Listens" is an excellent source for more on recommendation systems. Also check out the recent post on cold start problem.

Its Getting Crowded Out Here!

Yep! Thats what my Firefox toolbar looks like these days. Bookmarklets are a convenient way to post stuff to various sites. I use it for sharing links with the ebiquity blog via del.icio.us, post something to friendfeed, check news every now and then and right now I am testing this bookmarking site called Gyzork.  A few other plugins I have installed are del.icio.us, socialbrowse and stumbleupon. I used to have a lot more but couldnt keep up with all the stuff going on in my browser on a single monitor! :-(

Perhaps its time to rethink how we use bookmarklets. Some thoughts on this:

• It would be great to have icons for bookmarklets
• I need a bookmarklet 'stack feature' -- a place where I can organize bookmarklets.
• A listing of all the bookmarklets for different categories (GTD, News, Links, Blogs, etc...) would be handy for power users.
• Maybe we even need a simple way to post a link on one place and have it pushed to other sites

Its getting crowded out here! I am wondering if there is a better way to manage this somehow?

[Thanks Anthony Vito, for some of the discussions that led to this post]

Email Interview: Nihaar Gupta, Youlicit

Nihaar Gupta, VP of Product development at Youlicit has kindly obliged to have an email interview with SocialMedia Research Blog. Following are the responses to some of the questions I had for him:

1) Please describe Youlicit to us?

Youlicit at its core is a discovery engine (http://blog.youlicit.com/?p=23). We want to connect you to the most relevant and recommended information as effortlessly as possible. As of now, we are building a technology that allows a user to find the most recommended sites (recommended by people around the web) related to a given URL. We believe that people are the best judges of content and more often than not, the information you are looking for has been found by someone before. Our goal is to aggregate that information and allow the user to access it with the click of a button.

2) Tell Us about your background, the team behind Youlicit and how started it?

Youlicit came about as a result of trying to solve our own frustrations with trying to find information on the web. With the enormous amount of user-generated content and annotations on the web, we saw a huge amount of valuable data that was inaccessible and fragmented. For the sake of brevity, the team bios & background are here http://blog.youlicit.com/?page_id=6

3) Please give us a brief overview of the technology behind Youlicit?

Youlicit aggregates user annotations of websites and other user generated content and analyzes it to create a URL-URL mapping of websites based on relevance and quality. Using this mapping we are able to deliver related and recommended sites to a user with a click of a button.

4) While using Youlicit plugin, I felt that one of the challenges is the coverage -- how do you plan to address this and build your current index?

We are constantly working on improving our coverage. There are two metrics we strive to maximize for our results, quality and relevance. In regards to quality, we’re always looking to increase our database of “quality sites” by tapping into the various kinds of user annotations (denoting quality content) that exist on the web (bookmarks, tags, votes, comments). In regards to relevance, we’re always researching novel ways to extrapolate connections between websites and map URL’s back to our database of “quality sites”.

5) How do you ranking the 'Enhanced Links' in the plugin? Do you also take into account how many users actually click through the suggested links?

Each result in the Youlicit More widget (and on Youlicit’s site) has a score based on the metrics above, quality of the site and relevance to the item being queried. We are looking into ways of scoring the results from implicit/explicit feedback that we get from users (clicks, recommends).

6) How do you ensure that the Enhanced links feature is non-intrusive?

The current version has manifested itself after a few weeks of alpha testing with a handful of bloggers. That said, we are still looking for feedback on the user interface and would love to hear opinions on how to make it more useful and less intrusive for bloggers/blog readers.

7) How would you compare the plugin to sphere's related blog posts?

While Sphere focuses related & recent blogosphere content, we, at Youlicit, are trying to provide the blog reader with more seminal information related to the blogger’s topic of conversation. For instance, if you are reading a blog entry on global warming, you are more likely to receive the most recommended articles (blogs, sites, essays) on Global warming from around the web rather than  recent blog entries on that topic.

8) What are the other features on Youlicit?

Youlicit’s primary product is a Firefox extension to access that allows a user to access our results during his/her browsing experience. We are in the process of redesigning our website and streamlining the current offering to focus on this button. Down the road we would like to be able to deliver personalized recommendations for users as well as connect users to people based on transient and long-terms interests (ideally using a person’s interests to enhance his/her social graph).

9) Would the plugin be adverting supported?

We do see advertising as a very possible source of monetization. Given the fact that we are providing contextually relevant information, the search model of advertising applies nicely. We are also exploring other possible means of monetization but as of right now the priority is to build something that people find useful.

10) What are the next things to look out for at Youlicit?

As I mentioned above, we are stripping down Youlicit to bring the focus back to its core; the Youlicit More functionality via the Firefox extension and blog widget. We expect to release a new designed website very soon. And as always, we love to hear feedback on what you think so far and how we can improve.