|Title||Discovering Informative Connection Subgraphs in Multi-Relational Graphs|
|Publication Type||Journal Article|
|Year of Publication||2005|
|Authors||William Milnor, Matthew Perry, Cartic Ramakrishnan, Amit Sheth|
|Journal||Special Issue: Link Mining, <i>SIGKDD Exploration,</i> 7 (no. 2)|
|Keywords||Informative Graph Discovery, Knowledge Discovery, Pattern Discovery in RDF grpahs, RDF graph mining, RDF Graphs, semantic graph mining, semantic Web data mining, Semantic web Mining|
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.
|Full Text|| |
Cartic Ramakrishnan, William Milnor, Matthew Perry, andAmit Sheth, 'Discovering Informative Connection Subgraphs in Multi-Relational Graphs, 'Special Issue: Link Mining, SIGKDD Exploration, 7 (no. 2), December 2005, pp. 56-63.
related resource url: http://scholar.google.com/citations?view_op=view_citation&hl=en&user=2T3...