Classification over bipartite graphs through projection

Abstract: Many real-world large datasets correspond to bipartite graph datasets, think for example of users rating movies or people visiting locations. Although some work exists in analysis and collaborative filtering over such bigraphs, no general methodology has been proposed yet to perform node classification. In this paper, we propose a three-stage classification framework: first, a weighting of the top nodes is defined. Secondly, the bigraph is projected into a unipartite (homogenous) graph among the bottom nodes, where the weights of the edges are a function of the weights of the top nodes in the bigraph. Finally, relational learners are applied to the resulting weighted unigraph. In a large-scale experimental setup, we propose and asses a range of weighting schemes, aggregation functions and relational learners. The beta distribution turns out to be the best weighting scheme due to its flexibility, but the tuning procedure scales badly to large datasets. For those, the inverse degree performs best. The optimal aggregation function is simply summing the weights of the shared nodes, while the network only link-based classifier is the optimal relational learner. A comparison to applying statistical learning methods (SVM) on the adjacency matrix of the bigraph shows the superiority of our approach.

Publication: Available soon, preliminary results here.