Select-and-Evaluate: A Learning Framework for Large-Scale Knowledge Graph Search

F A Rezaur Rahman Chowdhury, Chao Ma, Md Rakibul Islam, Mohammad Hossein Namaki, Mohammad Omar Faruk, Janardhan Rao Doppa
Proceedings of the Ninth Asian Conference on Machine Learning, PMLR 77:129-144, 2017.

Abstract

Querying graph structured data is a fundamental operation that enables important applications including knowledge graph search, social network analysis, and cyber-network security. However, the growing size of real-world data graphs poses severe challenges for graph search to meet the response-time requirements of the applications. To address these scalability challenges, we develop a learning framework for graph search called \bf Sele\bf ct-and-Ev\bf aluat\bf e (SCALE). The key insight is to select a small part of the data graph that is sufficient to answer a given query in order to satisfy the specified constraints on time or accuracy. We formulate the problem of generating the candidate subgraph as a computational search process and induce search control knowledge from training queries using imitation learning. First, we define a search space over candidate selection plans, and identify target selection plans corresponding to the training queries by performing an expensive search. Subsequently, we learn greedy search control knowledge to imitate the search behavior of the target selection plans. Our experiments on large-scale knowledge graphs including DBpedia, YAGO, and Freebase show that using the learned selection plans, we can significantly improve the computational-efficiency of graph search to achieve high accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v77-chowdhury17a, title = {Select-and-Evaluate: A Learning Framework for Large-Scale Knowledge Graph Search}, author = {Chowdhury, F A Rezaur Rahman and Ma, Chao and Islam, Md Rakibul and Namaki, Mohammad Hossein and Faruk, Mohammad Omar and Doppa, Janardhan Rao}, booktitle = {Proceedings of the Ninth Asian Conference on Machine Learning}, pages = {129--144}, year = {2017}, editor = {Zhang, Min-Ling and Noh, Yung-Kyun}, volume = {77}, series = {Proceedings of Machine Learning Research}, address = {Yonsei University, Seoul, Republic of Korea}, month = {15--17 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v77/chowdhury17a/chowdhury17a.pdf}, url = {https://proceedings.mlr.press/v77/chowdhury17a.html}, abstract = {Querying graph structured data is a fundamental operation that enables important applications including knowledge graph search, social network analysis, and cyber-network security. However, the growing size of real-world data graphs poses severe challenges for graph search to meet the response-time requirements of the applications. To address these scalability challenges, we develop a learning framework for graph search called \bf Sele\bf ct-and-Ev\bf aluat\bf e (SCALE). The key insight is to select a small part of the data graph that is sufficient to answer a given query in order to satisfy the specified constraints on time or accuracy. We formulate the problem of generating the candidate subgraph as a computational search process and induce search control knowledge from training queries using imitation learning. First, we define a search space over candidate selection plans, and identify target selection plans corresponding to the training queries by performing an expensive search. Subsequently, we learn greedy search control knowledge to imitate the search behavior of the target selection plans. Our experiments on large-scale knowledge graphs including DBpedia, YAGO, and Freebase show that using the learned selection plans, we can significantly improve the computational-efficiency of graph search to achieve high accuracy.} }
Endnote
%0 Conference Paper %T Select-and-Evaluate: A Learning Framework for Large-Scale Knowledge Graph Search %A F A Rezaur Rahman Chowdhury %A Chao Ma %A Md Rakibul Islam %A Mohammad Hossein Namaki %A Mohammad Omar Faruk %A Janardhan Rao Doppa %B Proceedings of the Ninth Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Min-Ling Zhang %E Yung-Kyun Noh %F pmlr-v77-chowdhury17a %I PMLR %P 129--144 %U https://proceedings.mlr.press/v77/chowdhury17a.html %V 77 %X Querying graph structured data is a fundamental operation that enables important applications including knowledge graph search, social network analysis, and cyber-network security. However, the growing size of real-world data graphs poses severe challenges for graph search to meet the response-time requirements of the applications. To address these scalability challenges, we develop a learning framework for graph search called \bf Sele\bf ct-and-Ev\bf aluat\bf e (SCALE). The key insight is to select a small part of the data graph that is sufficient to answer a given query in order to satisfy the specified constraints on time or accuracy. We formulate the problem of generating the candidate subgraph as a computational search process and induce search control knowledge from training queries using imitation learning. First, we define a search space over candidate selection plans, and identify target selection plans corresponding to the training queries by performing an expensive search. Subsequently, we learn greedy search control knowledge to imitate the search behavior of the target selection plans. Our experiments on large-scale knowledge graphs including DBpedia, YAGO, and Freebase show that using the learned selection plans, we can significantly improve the computational-efficiency of graph search to achieve high accuracy.
APA
Chowdhury, F.A.R.R., Ma, C., Islam, M.R., Namaki, M.H., Faruk, M.O. & Doppa, J.R.. (2017). Select-and-Evaluate: A Learning Framework for Large-Scale Knowledge Graph Search. Proceedings of the Ninth Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 77:129-144 Available from https://proceedings.mlr.press/v77/chowdhury17a.html.

Related Material