Difference between revisions of "Konstas et al. SIGIR 2009"

From Cohen Courses
Jump to navigationJump to search
(Created page with '== Citation == Ioannis Konstas, Vassilios Stathopoulos, and Joemon M. Jose. On social networks and collaborative recommendation. In Proceedings of the 32nd international ACM SIG…')
 
 
(22 intermediate revisions by the same user not shown)
Line 9: Line 9:
 
== Summary ==
 
== Summary ==
  
−
This [[Category::paper]] proposes a method, using [[UsesMethod::Random walk with restart]], for [[AddressesProblem::Content recommendation]] in social network systems.  
+
This [[Category::paper]] applies [[UsesMethod::Random walk with restart]] as a method of [[AddressesProblem::Content recommendation|content recommendation]] in social network systems.  
  
−
As it is in the context of social network, naturally and effectively, a graph based algorithm such as [[UsesMethod::Random walk with restart]] can be considered to perform the [[AddressesProblem::Content recommendation]] task.  
+
As it is in the context of social network, naturally and effectively, a graph based algorithm such as [[UsesMethod::Random walk with restart]] can be considered to perform the [[AddressesProblem::Content recommendation|recommendation]] task.  
  
 
This [[Category::paper]] argues that the extra knowledge provided by the users' social activity, such as the social annotation and friendships inherent in the social graph established among users, items and tags, can improve the performance of a recommendation system using methods such as [[UsesMethod::Random walk with restart]].
 
This [[Category::paper]] argues that the extra knowledge provided by the users' social activity, such as the social annotation and friendships inherent in the social graph established among users, items and tags, can improve the performance of a recommendation system using methods such as [[UsesMethod::Random walk with restart]].
  
−
The argue is supported based on a series of comparison experiments between the [[UsesMethod::Random walk with restart]] model and a user-based [[Social_collaborative_filtering|collaborative filtering] method using the Pearson Correlation similarity. The results show that the graph model system benefits from the additional information embedded in social knowledge. In addition, the graph model outperforms the standard collaborative �filtering method.
+
The argument is supported based on a series of comparison experiments between the [[UsesMethod::Random walk with restart]] model and a user-based [[Social_collaborative_filtering|collaborative filtering]] method using the Pearson Correlation similarity. The results show that the graph model system benefits from the additional information embedded in social knowledge. In addition, the graph model outperforms the standard [[Social_collaborative_filtering|collaborative filtering]] method.
  
−
== Background and preparation ==
+
== The dataset ==
  
−
*Network construction
+
The source of [[UsesDataset::last.fm|dataset]] comes from last.fm - a Web 2.0 website. As introduced in the [[UsesDataset::last.fm|dataset]], there are three components serving as the vertices in the graph - users, music tracks and tags, deriving relation matrices as User-Track(UTr), User-Tag(UTg) and Track-Tag(TrTg).  
−
The dataset [[UsesDataset::WordNet]] is used to construct the network of words.Collect all words in WordNet, and add links between any two words that occurr in the same synset. The resulting graph is a graph <math>G(W,E)</math> where <math>W</math> is a set of word / part-of-speech pairs for all the words in WordNet. <math>E</math> is the set of edges connecting each pair of synonymous words.
 
  
−
*Random walk model
+
The UTr sub-matrix consists of the playcount of every track by each user, i.e. the number of times it has been listened to.
−
Starting from a word with unknown polarity <math>i</math> , it moves to a node <math>j</math> with probability <math>P_{ij}</math> after the first step. The walk continues until the surfer hits a word with a known
 
−
polarity.
 
  
−
*First-passage time
+
The UU sub-matrix consists the average user playcount. This is crucial because the UTr sub-matrix may contain very large values and thus the binary values in UU will be suppressed.
−
It is very similar to the definition of [[UsesMethod::hitting time]].
 
−
The mean first-passage (hitting) time <math>h(i|k)</math> is defined as the average number of steps a random walker, starting in state <math>i \ne k</math>, will take to enter state <math>k</math> for the first time. Considering a subset vertices of the graph, then <math>h(i|S)</math> means the average number of steps a random walker, starting in state <math>i \notin S</math>, will take to enter a stae <math>k \in S</math> for the first time.
 
  
−
Then it is proven that:
+
In the case of the UTg sub-matrix, the associated tags for each user have been collected based on popularity. An exponential decay function is applied to the values of the tags of each user in the matrix, where the most popular tag gets the average user's playcount. The same process was performed for the TrTg sub-matrix accordingly.
  
−
<math>h(i|S) = 
+
The full social graph look like:
−
\begin{cases}
 
−
0,  & i \in S \\
 
−
\sum_{j \in V}p_{ij} * h(j|S) + 1,  & otherwise
 
−
\end{cases}
 
−
</math>
 
  
−
== Algorithm description ==
+
[[File:Last.fm.graph.png]]
  
−
#Construct a word relatedness graph
+
== Experiment results and observations==
−
#Define a random walk on the graph
+
The experiment result is concluded as following table:
−
#Compute the word's [[UsesMethod::hitting time]] for both the positive and negative sets of vertices
+
[[File:Last.fm.result.png]]
−
#If the hitting time for the positive set is greater than for the negative set, than the word is classified as negative. Otherwise, it is classified as positive. The ratio between the two hitting times could be used as an indication of how positive/negative the given word is.
 
  
−
Since computing the hitting time is time consuming especially when the graph is large, a Monte Carlo based estimating algorithm is proposed as such:
+
There are several observations from the result worth noticing:
−
[[File:Word_polarity_using_random_walks.png]]
 
  
−
== Experiment result ==
+
*The addition of social network and social tagging information increases the number of relevant retrieved (num_rel_ret) tracks in the [[Random walk with restart|RWR]] method.
−
Comparing to other methods, this method is quite successful in both the settings of semi-supervised and unsupervised.
+
*There is also a notable decrease in MAP and Precision at high ranks and in parallel to num_rel_ret increase and Precision at lower ranks. This tendency accounts for the fact that with the progressive addition of social knowledge the method retrieves more tracks thus effectively increases its recall but at lower ranks (e.g P@200), causing a harm to its precision.
 +
*the [[Random walk with restart|RWR]] method with the UTrUTg graph retrieves statistically significantly more relative tracks than the RWR method with the UTrUU graph (and also has higher P@200 and P@1000) compared to the simple [[Random walk with restart|RWR]] method.
 +
The above three observation highlights the benifits of the social graph.
  
−
* In the setting of using [[UsesDataset::WordNet]] synonyms and hypernyms to construct the network and test set to the set of adjectives. It out performs the spin-model, bootstrap and short-path method.
+
*Using the same sub-matrix as the input, the [[Random walk with restart|RWR]] method always outperforms the [[Social_collaborative_filtering | CF]] method. This supports the argument that the [[Random walk with restart|RWR]] method is more effective than the [[Social_collaborative_filtering | CF]] method.
−
[[File:Hassan_%26_Radev_ACL_2010_E1.png]]
 
  
−
* It is also compared to the SO-PMI method in the setting of only 14 seeds. Though SO-PMI with a very large dataset performs slightly better than this method, this method is faster and does not need such large corpus.
+
*Using the [[Social_collaborative_filtering | CF]] method, the addition of friendships and social tagging information deteriorates the performance increasingly. This supports the argument that the memory based [[Social_collaborative_filtering | CF]] method cannot provide with adequate non-trivial mechanisms to incorporate social knowledge.
−
[[File:Hassan_%26_Radev_ACL_2010_E2.png]]
 
  
 
== Related papers ==
 
== Related papers ==
−
*[[RelatedPaper:: Takamura et al. 2005|Hiroya Takamura, Takashi Inui, and Manabu Okumura.2005. Extracting semantic orientations of words using spin model. In ACL ’05.]]
+
*[[RelatedPaper:: Bu et al. MM 2010|Music Recommendation by Unified Hypergraph: Combining Social Media Information and Music Content]]
−
*[[RelatedPaper::Turney and Littman, 2003 | Peter Turney and Michael Littman. 2003. Measuring praise and criticism: Inference of semantic orientation from association. ACM Transactions on Information Systems, 21:315–346.]]
+
Interesting article also leverages the social media information and the music content itself to recommend music.
−
*[[RelatedPaper::Kamps LREC 2004|Jaap Kamps, Maarten Marx, Robert J. Mokken, and Maarten De Rijke. 2004. Using wordnet to measure semantic orientations of adjectives. In National Institute for, pages 1115–1118.]]
+
*[[RelatedPaper:: Yildirim and Krishnamoorthy MM RecSys 2008|A random walk method for alleviating the sparsity problem in collaborative filtering]]
−
*[[RelatedPaper::Hu and Liu, 2004|Minqing Hu and Bing Liu. 2004. Mining and summarizing customer reviews. In KDD ’04]]
+
Another recommendation algorithm using random walk.
−
*[[RelatedPaper::Turney,2002|Peter D. Turney. 2002. Thumbs up or thumbs down?:semantic orientation applied to unsupervised classification of reviews. In ACL ’02]]
+
*[[RelatedPaper: Yuan et al. RecSys 2009|Augmenting collaborative recommender by fusing explicit social relationships]]
 +
Two principal methods to integrate explicit social relationships into traditional CF methods: the weighted-similarity fusion and the graph fusion.
  
 
== Study plan ==
 
== Study plan ==
−
* Article: [http://en.wikipedia.org/wiki/Random_walk Random walk]
+
* Web page: [[Random walk with restart]]
−
* Article: [http://en.wikipedia.org/wiki/Monte_Carlo_method Monto Carlo Method]
+
* Slides: [http://www.cs.cmu.edu/~wcohen/collab-filtering-tutorial.ppt Collaborative Filtering: A Tutorial]
 +
* Article: [http://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient Pearson correlation]

Latest revision as of 08:37, 2 October 2012

Citation

Ioannis Konstas, Vassilios Stathopoulos, and Joemon M. Jose. On social networks and collaborative recommendation. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’09, pages 195–202, New York, NY, USA, 2009. ACM.

Online Version

online version

Summary

This paper applies Random walk with restart as a method of content recommendation in social network systems.

As it is in the context of social network, naturally and effectively, a graph based algorithm such as Random walk with restart can be considered to perform the recommendation task.

This paper argues that the extra knowledge provided by the users' social activity, such as the social annotation and friendships inherent in the social graph established among users, items and tags, can improve the performance of a recommendation system using methods such as Random walk with restart.

The argument is supported based on a series of comparison experiments between the Random walk with restart model and a user-based collaborative filtering method using the Pearson Correlation similarity. The results show that the graph model system benefits from the additional information embedded in social knowledge. In addition, the graph model outperforms the standard collaborative filtering method.

The dataset

The source of dataset comes from last.fm - a Web 2.0 website. As introduced in the dataset, there are three components serving as the vertices in the graph - users, music tracks and tags, deriving relation matrices as User-Track(UTr), User-Tag(UTg) and Track-Tag(TrTg).

The UTr sub-matrix consists of the playcount of every track by each user, i.e. the number of times it has been listened to.

The UU sub-matrix consists the average user playcount. This is crucial because the UTr sub-matrix may contain very large values and thus the binary values in UU will be suppressed.

In the case of the UTg sub-matrix, the associated tags for each user have been collected based on popularity. An exponential decay function is applied to the values of the tags of each user in the matrix, where the most popular tag gets the average user's playcount. The same process was performed for the TrTg sub-matrix accordingly.

The full social graph look like:

Last.fm.graph.png

Experiment results and observations

The experiment result is concluded as following table: Last.fm.result.png

There are several observations from the result worth noticing:

  • The addition of social network and social tagging information increases the number of relevant retrieved (num_rel_ret) tracks in the RWR method.
  • There is also a notable decrease in MAP and Precision at high ranks and in parallel to num_rel_ret increase and Precision at lower ranks. This tendency accounts for the fact that with the progressive addition of social knowledge the method retrieves more tracks thus effectively increases its recall but at lower ranks (e.g P@200), causing a harm to its precision.
  • the RWR method with the UTrUTg graph retrieves statistically significantly more relative tracks than the RWR method with the UTrUU graph (and also has higher P@200 and P@1000) compared to the simple RWR method.

The above three observation highlights the benifits of the social graph.

  • Using the same sub-matrix as the input, the RWR method always outperforms the CF method. This supports the argument that the RWR method is more effective than the CF method.
  • Using the CF method, the addition of friendships and social tagging information deteriorates the performance increasingly. This supports the argument that the memory based CF method cannot provide with adequate non-trivial mechanisms to incorporate social knowledge.

Related papers

Interesting article also leverages the social media information and the music content itself to recommend music.

Another recommendation algorithm using random walk.

Two principal methods to integrate explicit social relationships into traditional CF methods: the weighted-similarity fusion and the graph fusion.

Study plan

Retrieved from "http://curtis.ml.cmu.edu/w/courses/index.php?title=Konstas_et_al._SIGIR_2009&oldid=13482"