Discovering Informative Subgraphs in RDF Graphs

TitleDiscovering Informative Subgraphs in RDF Graphs
Publication TypeMiscellaneous
Year of Publication2005
AuthorsCartic Ramakrishnan, Krzysztof Kochut, William Milnor, John Miller, Matthew Perry, Amit Sheth
KeywordsSemantic Associations and Semantic RDF subgraph discovery

Discovering patterns in graphs has long been an area of interest. In most contemporary approaches to such pattern discovery either quantitative anomalies or frequency of substructure is used to measure the interestingness of a pattern. In this paper we address the issue of discovering informative sub-graphs within RDF graphs. We motivate our work with an example related to Semantic Search. 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. Relevance of the discovered subgraph therefore will depend on the amount of useful information conveyed to the user. This in turn depends on the meaning of the edges in the subgraph. We introduce heuris-tics that guide a discovery algorithm away from banal paths towards more in-formative ones. This guidance is based on weighting mechanisms (driven by edge semantics) for the edges in the RDF graph. 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.

Full Text

William H. Milnor,Cartic Ramakrishnan, Matthew Perry, Amit P. Sheth, John A. Miller, and Krzysztof J. Kochut, 'Discovering Informative Subgraphs in RDF Graphs,' CS Technical Report 05-001, UGA Department of Computer Science, 2005.
year: 2005