Spectral decomposition for optimal graph index prediction

Liyan Song, Yun PENG, Koon Kau CHOI, Jianliang XU, Bingsheng He

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

1 Citation (Scopus)


There is an ample body of recent research on indexing for structural graph queries. However, as verified by our experiments with a large number of random and scale-free graphs, there may be a great variation in the performances of indexes of graph queries. Unfortunately, the structures of graph indexes are often complex and ad-hoc, so deriving an accurate performance model is a daunting task. As a result, database practitioners may encounter difficulties in choosing the optimal index for their data graphs. In this paper, we address this problem by proposing a spectral decomposition method for predicting the relative performances of graph indexes. Specifically, given a graph, we compute its spectrum. We then propose a similarity function to compare the spectrums of graphs. We adopt a classification algorithm to build a model and a voting algorithm for predicting the optimal index. Our empirical studies on a large number of random and scale-free graphs, using four structurally distinguishable indexes, demonstrate that our spectral decomposition method is robust and almost always exhibits an accuracy of 70% or above.

Original languageEnglish
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 17th Pacific-Asia Conference, PAKDD 2013, Proceedings
Number of pages14
EditionPART 1
Publication statusPublished - 2013
Event17th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2013 - Gold Coast, QLD, Australia
Duration: 14 Apr 201317 Apr 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7818 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference17th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2013
CityGold Coast, QLD

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Spectral decomposition for optimal graph index prediction'. Together they form a unique fingerprint.

Cite this