Fast best-effort search on graphs with multiple attributes

Senjuti Basu Roy, Tina Eliassi-Rad, Spiros Papadimitriou

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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-worldapplications. 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 than50 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.

Original languageEnglish (US)
Article number6877688
Pages (from-to)755-768
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number3
StatePublished - Mar 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


  • Graph search
  • Top-k algorithms
  • Weighted attribute graph


Dive into the research topics of 'Fast best-effort search on graphs with multiple attributes'. Together they form a unique fingerprint.

Cite this