Ranking on graph data
Ranking on graph data
复制标题
DOI：
10.1145/1143844.1143848
复制
发表时间：
2006-06
期刊：
影响因子：
--
通讯作者：
S. Agarwal
中科院分区：
文献类型：
--
作者：
S. Agarwal
在排序中，给出对象之间的顺序关系的示例，目标是从这些示例中学习一个实值排序函数，该函数可以在对象空间上推导出排序或排序。当数据被表示为图时，我们考虑学习这样一个排序函数的问题，其中顶点对应对象，边编码对象之间的相似性。基于图的正则化理论和相应的基于拉普拉斯的分类方法的最新发展，我们开发了一个用于在图数据上学习排序函数的算法框架。基于算法稳定性的概念，我们通过最近的结果为我们的算法提供了泛化保证，并给出了我们框架潜在好处的实验证据。
In ranking, one is given examples of order relationships among objects, and the goal is to learn from these examples a real-valued ranking function that induces a ranking or ordering over the object space. We consider the problem of learning such a ranking function when the data is represented as a graph, in which vertices correspond to objects and edges encode similarities between objects. Building on recent developments in regularization theory for graphs and corresponding Laplacian-based methods for classification, we develop an algorithmic framework for learning ranking functions on graph data. We provide generalization guarantees for our algorithms via recent results based on the notion of algorithmic stability, and give experimental evidence of the potential benefits of our framework.