Document Type
Article
Publication Date
12-1-2005
Abstract
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.
Repository Citation
Ramakrishnan, C.,
Milnor, W.,
Perry, M.,
& Sheth, A. P.
(2005). Discovering Informative Connection Subgraphs in Multi-Relational Graphs. ACM SIGKDD Explorations Newsletter, 7 (2), 56-63.
https://corescholar.libraries.wright.edu/knoesis/67
DOI
10.1145/1117454.1117462
Included in
Bioinformatics Commons, Communication Technology and New Media Commons, Databases and Information Systems Commons, OS and Networks Commons, Science and Technology Studies Commons
Comments
© {Owner/Author | ACM} 2005. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM SIGKDD Explorations Newsletter, http://dx.doi.org/10.1145/1117454.1117462.