Neighborhood Based Fast Graph Search in Large Networks
A. Khan, N. Li, X. Yan, Z. Guan, S. Chakraborty, and S. Tao. Conference, International Conference on Management of Data (SIGMOD/PODS 2011), Athens, Greece - June 12 - 16, 2011, page 901--912. New York, NY, USA, ACM, (2011)
Abstract
Complex social and information network search becomes important with
a variety of applications. In the core of these applications, lies
a common and critical problem: Given a labeled network and a query
graph, how to efficiently search the query graph in the target network.
The presence of noise and the incomplete knowledge about the structure
and content of the target network make it unrealistic to find an
exact match. Rather, it is more appealing to find the top-k approximate
matches.
In this paper, we propose a neighborhood-based similarity measure
that could avoid costly graph isomorphism and edit distance computation.
Under this new measure, we prove that subgraph similarity search
is NP hard, while graph similarity match is polynomial. By studying
the principles behind this measure, we found an information propagation
model that is able to convert a large network into a set of multidimensional
vectors, where sophisticated indexing and similarity search algorithms
are available. The proposed method, called Ness (Neighborhood Based
Similarity Search), is appropriate for graphs with low automorphism
and high noise, which are common in many social and information networks.
Ness is not only efficient, but also robust against structural noise
and information loss. Empirical results show that it can quickly
and accurately find high-quality matches in large networks, with
negligible cost.
%0 Conference Paper
%1 khan-2011
%A Khan, Arijit
%A Li, Nan
%A Yan, Xifeng
%A Guan, Ziyu
%A Chakraborty, Supriyo
%A Tao, Shu
%B Conference, International Conference on Management of Data (SIGMOD/PODS 2011), Athens, Greece - June 12 - 16, 2011
%C New York, NY, USA
%D 2011
%I ACM
%K 2011 graph matching selected seminar twitter winter
%P 901--912
%T Neighborhood Based Fast Graph Search in Large Networks
%X Complex social and information network search becomes important with
a variety of applications. In the core of these applications, lies
a common and critical problem: Given a labeled network and a query
graph, how to efficiently search the query graph in the target network.
The presence of noise and the incomplete knowledge about the structure
and content of the target network make it unrealistic to find an
exact match. Rather, it is more appealing to find the top-k approximate
matches.
In this paper, we propose a neighborhood-based similarity measure
that could avoid costly graph isomorphism and edit distance computation.
Under this new measure, we prove that subgraph similarity search
is NP hard, while graph similarity match is polynomial. By studying
the principles behind this measure, we found an information propagation
model that is able to convert a large network into a set of multidimensional
vectors, where sophisticated indexing and similarity search algorithms
are available. The proposed method, called Ness (Neighborhood Based
Similarity Search), is appropriate for graphs with low automorphism
and high noise, which are common in many social and information networks.
Ness is not only efficient, but also robust against structural noise
and information loss. Empirical results show that it can quickly
and accurately find high-quality matches in large networks, with
negligible cost.
@inproceedings{khan-2011,
abstract = {Complex social and information network search becomes important with
a variety of applications. In the core of these applications, lies
a common and critical problem: Given a labeled network and a query
graph, how to efficiently search the query graph in the target network.
The presence of noise and the incomplete knowledge about the structure
and content of the target network make it unrealistic to find an
exact match. Rather, it is more appealing to find the top-k approximate
matches.
In this paper, we propose a neighborhood-based similarity measure
that could avoid costly graph isomorphism and edit distance computation.
Under this new measure, we prove that subgraph similarity search
is NP hard, while graph similarity match is polynomial. By studying
the principles behind this measure, we found an information propagation
model that is able to convert a large network into a set of multidimensional
vectors, where sophisticated indexing and similarity search algorithms
are available. The proposed method, called Ness (Neighborhood Based
Similarity Search), is appropriate for graphs with low automorphism
and high noise, which are common in many social and information networks.
Ness is not only efficient, but also robust against structural noise
and information loss. Empirical results show that it can quickly
and accurately find high-quality matches in large networks, with
negligible cost.},
added-at = {2011-10-10T09:55:04.000+0200},
address = {New York, NY, USA},
author = {Khan, Arijit and Li, Nan and Yan, Xifeng and Guan, Ziyu and Chakraborty, Supriyo and Tao, Shu},
biburl = {https://www.bibsonomy.org/bibtex/2a41070c39ca410d4bd9ae996444ae99c/becker},
booktitle = {Conference, International Conference on Management of Data (SIGMOD/PODS 2011), Athens, Greece - June 12 - 16, 2011},
interhash = {8a1aa0e2b006855c14be6c6b9c45327f},
intrahash = {a41070c39ca410d4bd9ae996444ae99c},
keywords = {2011 graph matching selected seminar twitter winter},
pages = {901--912},
publisher = {ACM},
timestamp = {2011-10-26T09:08:42.000+0200},
title = {Neighborhood Based Fast Graph Search in Large Networks},
year = 2011
}