Discovering Informative Connection Subgraphs in Multi-Relational Graphs

TitleDiscovering Informative Connection Subgraphs in Multi-Relational Graphs
Publication TypeJournal Article
Year of Publication2005
AuthorsWilliam Milnor, Matthew Perry, Cartic Ramakrishnan, Amit Sheth
JournalSpecial Issue: Link Mining, <i>SIGKDD Exploration,</i> 7 (no. 2)
Date Published12/2005
PublisherSIGKDD Exploration
KeywordsInformative 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:
hasBookTitle: Special Issue: Link Mining