Published on Sep 03, 2023
In this project, we look into the problem of learning a relevance order over a set of objects linked together by a graph, an example being, the hyperlink graph on the web. Previous approaches to the problem of learning relevance order have largely disregarded the fact that the objects are connected by a graph.
The objects were represented as independent samples from some vector-space and the the ordering problem was posed as a classification/regression problem over these samples. We observe that objects are not really independent samples, i.e., the rank score of an object is not determined only by itself but by rank scores of other linked objects.
It is proposed an approach to enhance PageRank like link-based ranking algorithms, that takes as input, data capturing user's notion of relevance order over the nodes of an underlying graph and automatically assigns edge weights to the links of the graph, so that the concerned ranking algorithm (PageRank here), using this weighted graph, now orders the graph objects in accordance with user's relevance notion. Earlier approaches in learning relevance via edge weight tuning are largely sub-optimal and inefficient.
We use the principle of Maximum Entropy to search for an optimal assignment of edge weights. We provide preliminary experimental results on synthetic data to demonstrate the effectiveness of our approach. We end with a discussion on how our approach can be further adapted to learning type-specific edge weights for relevance ranking over graphs containing nodes and edges of heterogeneous types.
