In this thesis, we propose novel solutions to similarity learning problems on collaborative networks. Similarity learning is essential for modeling and predicting the evolution of collaborative networks. In addition, similarity learning is used to perform ranking, which is the main component of recommender systems. Due to the the low cost of developing such collaborative networks, they grow very quickly, and therefore, our objective is to develop models that scale well to large networks. The similarity measures proposed in this thesis make use of the global link structure of the network and of the attributes of the nodes in a complementary way. We first define a random walk model, named Visiting Probability (VP), to measure proximity between two nodes in a graph. VP considers all the paths between two nodes collectively and thus reduces the effect of potentially unreliable individual links. Moreover, using VP and the structural characteristics of small-world networks (a frequent type of networks), we design scalable algorithms based on VP similarity. We then model the link structure of a graph within a similarity learning framework, in which the transformation of nodes to a latent space is trained using a discriminative model. When trained over VP scores, the model is able to better predict the relations in a graph in comparison to models learned directly from the network’s links. Using the VP approach, we explain how to transfer knowledge from a hypertext encyclopedia to text analysis tasks. We consider the graph of Wikipedia articles with two types of links between them: hyperlinks and content similarity ones. To transfer the knowledge learned from the Wikipedia network to text analysis tasks, we propose and test two shared representation methods. In the first one, a given text is mapped to the corresponding concepts in the network. Then, to compute similarity between two texts, VP similarity is applied to compute the distance between the two sets of nodes. The second method uses the latent space model for representation, by training a transformation from words to the latent space over VP scores. We test our proposals on several benchmark tasks: word similarity, document similarity / clustering / classification, information retrieval, and learning to rank. The results are most often competitive compared to state-of-the-art task-specific methods, thus demonstrating the generality of our proposal. These results also support the hypothesis that both types of links over Wikipedia are useful, as the improvement is higher when both are used. In many collaborative networks, different link types can be used in a complementary way. Therefore, we propose two joint similarity learning models over the nodes’ attributes, to be used for link prediction in networks with multiple link types. The first model learns a similarity metric that consists of two parts: the general part, which is shared between all link types, and the specific part, which is trained specifically for each type of link. The second model consists of two layers: the first layer, which is shared between all link types, embeds the objects of the network into a new space, and then a similarity is learned specifically for each link type in this new space. Our experiments show that the proposed joint modeling and training frameworks improve link prediction performance significantly for each link type in comparison to multiple baselines. The two-layer similarity model outperforms the first one, as expected, due to its capability of modeling negative correlations among different link types. Finally, we propose a learning to rank algorithm on network data, which uses both the attributes of the nodes and the structure of the links for learning and inference. Link structure is used in training through a neighbor-aware ranker which considers both node attributes and scores of neighbor nodes. The global link structure of the network is used in inference through an original propagation method called the Iterative Ranking Algorithm. This propagates the predicted scores in the graph on condition that they are above a given threshold. Thresholding improves performance, and makes a time-efficient implementation possible, for application to large scale graphs. The observed improvements are explained considering the structural properties of small-world networks.
EPFL2013
