Active Search on Graphs using Sigma-Optimality

Yifei Ma, Tzu-Kuo Huang, Jeff Schneider Carnegie Mellon Univ
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:910-919, 2015.

Abstract

Many modern information access problems involve highly complex patterns that cannot be handled by traditional keyword based search. Active Search is an emerging paradigm that helps users quickly find relevant information by efficiently collecting and learning from user feedback. We consider active search on graphs, where the nodes represent the set of instances users want to search over and the edges encode pairwise similarity among the instances. Existing active search algorithms are either short of theoretical guarantees or inadequate for graph data. Motivated by recent advances in active learning on graphs, namely the Sigma-optimality selection criterion, we propose new active search algorithms suitable for graphs with theoretical guarantees and demonstrate their effectiveness on several real-world datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-ma15a, title = {Active Search on Graphs using Sigma-Optimality}, author = {Ma, Yifei and Huang, Tzu-Kuo and Univ, Jeff Schneider Carnegie Mellon}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {910--919}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/ma15a/ma15a.pdf}, url = {https://proceedings.mlr.press/r13/ma15a.html}, abstract = {Many modern information access problems involve highly complex patterns that cannot be handled by traditional keyword based search. Active Search is an emerging paradigm that helps users quickly find relevant information by efficiently collecting and learning from user feedback. We consider active search on graphs, where the nodes represent the set of instances users want to search over and the edges encode pairwise similarity among the instances. Existing active search algorithms are either short of theoretical guarantees or inadequate for graph data. Motivated by recent advances in active learning on graphs, namely the Sigma-optimality selection criterion, we propose new active search algorithms suitable for graphs with theoretical guarantees and demonstrate their effectiveness on several real-world datasets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Active Search on Graphs using Sigma-Optimality %A Yifei Ma %A Tzu-Kuo Huang %A Jeff Schneider Carnegie Mellon Univ %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-ma15a %I PMLR %P 910--919 %U https://proceedings.mlr.press/r13/ma15a.html %V R13 %X Many modern information access problems involve highly complex patterns that cannot be handled by traditional keyword based search. Active Search is an emerging paradigm that helps users quickly find relevant information by efficiently collecting and learning from user feedback. We consider active search on graphs, where the nodes represent the set of instances users want to search over and the edges encode pairwise similarity among the instances. Existing active search algorithms are either short of theoretical guarantees or inadequate for graph data. Motivated by recent advances in active learning on graphs, namely the Sigma-optimality selection criterion, we propose new active search algorithms suitable for graphs with theoretical guarantees and demonstrate their effectiveness on several real-world datasets. %Z Reissued by PMLR on 04 October 2026.
APA
Ma, Y., Huang, T. & Univ, J.S.C.M.. (2015). Active Search on Graphs using Sigma-Optimality. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:910-919 Available from https://proceedings.mlr.press/r13/ma15a.html. Reissued by PMLR on 04 October 2026.

Related Material