Probabilistic Inference Based Incremental Graph Index for Similarity Search on Social Networks

To findkneighbor users on social networks, the efficient approximate nearest neighbor search (ANNS) is useful. Existing graph index methods have shown attractive performance, but suffer from inaccuracy w.r.t. unindexed queries. To achieve both indexed and unindexed queries for graph-index methods, we propose an incremental graph index based method for ANNS on social networks. First, graph convolutional network based on attention mechanism is adopted to embed the social network into low-dimensional vector space, on which the graph index is constructed efficiently. To add the unindexed queries to the graph index incrementally, we propose Bayesian network (BN) learned from social interactions to represent dependency relations of unindexed queries and their neighbors, and perform probabilistic inferences in BN to infer the closest neighbors of unindexed queries. Extensive experiments show that our proposed method outperforms the state-of-the-art methods on both execution time and precision.