Discovering informative connection subgraphs in multi-relational graphs
Discovering informative connection subgraphs in multi-relational graphs
复制标题
DOI：
10.1145/1117454.1117462
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
Cartic Ramakrishnan;William Milnor;Matthew Perry;A. Sheth
中科院分区：
文献类型：
--
作者：
Cartic Ramakrishnan;William Milnor;Matthew Perry;A. Sheth
长期以来，发现图形中的模式一直是人们感兴趣的领域。在这种模式发现的大多数方法中，要么使用定量异常、子结构频率或最大流量来衡量模式的兴趣度。在这篇文章中，我们引入了启发式算法，引导一个子图发现算法从普通的路径转向更“信息”的路径。给出一个RDF图，用户可能会提出这样的问题：“实体X与实体Y之间最相关的方式是什么？”它的响应是一个连接X和Y的子图。我们使用我们的启发式算法来发现RDF图中的信息子图。我们的启发式算法基于从RDF模式建议的边语义派生的加权机制。我们给出了关于路径排名度量生成的子图的质量的分析。然后，我们总结关于我们的加权方案和启发式方法产生更高质量的子图的直觉。
Discovering patterns in graphs has long been an area of interest. In most approaches to such pattern discovery either quantitative anomalies, frequency of substructure or maximum flow is used to measure the interestingness of a pattern. In this paper we introduce heuristics that guide a subgraph discovery algorithm away from banal paths towards more "informative" ones. Given an RDF graph a user might pose a question of the form: "What are the most relevant ways in which entity X is related to entity Y?" the response to which is a subgraph connecting X to Y. We use our heuristics to discover informative subgraphs within RDF graphs. Our heuristics are based on weighting mechanisms derived from edge semantics suggested by the RDF schema. We present an analysis of the quality of the subgraphs generated with respect to path ranking metrics. We then conclude presenting intuitions about which of our weighting schemes and heuristics produce higher quality subgraphs.