Graph neural networks for ranking problems

Learning rankings from paired comparisons is a task widely applied in sports modelling, social network analysis, bibliometrics and recommender systems. Common approaches include generalized linear models such as the Bradley—Terry model, or eigenvector-based methods such as the PageRank algorithm. A sports tournament, citation exchange or series of paired comparisons may be represented as a directed, weighted graph, where each node represents an entity (team, player) to be compared and a directed edge between two nodes represents a favourable comparison (a win) of one over the other. In most methods, the ranking is based on ordering a vector of latent real-valued scores inferred from the data.

Graph neural networks, or GNNs, are an extension of neural networks to graph data by embedding the node, edge and graph-wide attributes in an appropriate vector representations that can be fed into standard neural network models. To exploit the dependence between nodes, edges and global attributes (rather than treating them as independent features), message-passing neural networks employ various methods of ‘pooling’ to associate node, edge and global attributes to each other during the learning process. Recently, GNNs have been extended to the task of recovering rankings from paired comparison data: e.g. GNNRank (He et al, 2022).

References

• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks https://arxiv.org/abs/2202.00211
• Graph Neural Networks for Ranking Web Pages http://dx.doi.org/10.1109/WI.2005.67
• A Gentle Introduction to Graph Neural Networks https://distill.pub/2021/gnn-intro/