Fast Best-Effort Search on Graphs with Multiple Attributes

S. Basu Roy, T. Eliassi-Rad, S. Papadimitriou
Proceedings of the 32nd IEEE ICDE
TKDE Poster Track, Helsinki, Finland, May 2016
March 1, 2015

Abstract

We address the  problem of search on graphs with multiple nodal attributes. We call such  graphs weighted attribute graphs (WAGs). Nodes of a WAG exhibit multiple  attributes with varying, non-negative weights. WAGs are ubiquitous in  real-world applications. For example, in a co-authorship WAG, each author is  a node; each attribute corresponds to a particular topic (e.g., databases,  data mining, and machine learning); and the amount of expertise in a  particular topic is represented by a non-negative weight on that attribute. A  typical search in this setting specifies both connectivity between nodes and  constraints on weights of nodal attributes. For example, a user's search may  be: find three coauthors (i.e., a triangle) where each author's expertise is  greater than 50 percent in at least one topic area (i.e., attribute). We  propose a ranking function which unifies ranking between the graph structure  and attribute weights of nodes. We prove that the problem of retrieving the  optimal answer for graph search on WAGs is NP-complete. Moreover, we propose  a fast and effective top-k graph search algorithm for WAGs. In an extensive  experimental study with multiple real-world graphs, our proposed algorithm  exhibits significant speed-up over competing approaches. On average, our  proposed method is more than 7χ faster in query processing than the best  competitor.

Related publications