More Web Proxy on the site http://driver.im/

research-article

Accurate and scalable nearest neighbors in large networks based on effective importance

Authors:

Petko Bogdanov,

Ambuj SinghAuthors Info & Claims

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

Pages 1009 - 1018

https://doi.org/10.1145/2505515.2505522

Published: 27 October 2013 Publication History

Abstract

Nearest neighbor proximity search in large graphs is an important analysis primitive with a variety of applications in graph data from different domains. We propose a novel proximity measure for weighted graphs called Effective Importance which incorporates multiple paths between nodes and captures the inherent structural clusters within a network. We develop effective bounds on the EI value using a modified small subnetwork around a query node, enabling scalable exact nearest neighbor (NN) search at query time. Our NN search does not require heavy offline analysis or holistic knowledge of the graph, making our method suitable for very large dynamically changing networks or composite network overlays.

We employ our NN search algorithm on social, information and biological networks and demonstrate the effectiveness and scalability of the approach. For million-node networks, our method retrieves the exact top 20 neighbors using less than $0.2%$ of the network edges in a fraction of a second on a conventional desktop machine. We also evaluate the effectiveness of our proximity measure and NN search for three applications, namely (i) finding good local clusters, (ii) network sparsification and (iii) prediction of node attributes in information networks. The EI measure and NN search method outperform recent counterparts from the literature in all applications.

References

[1]

Biogrid: General repository for interaction datasets. http://www.thebiogrid.org/, 2006.

[2]

K. J. Ahn, S. Guha, and A. McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st symposium on Principles of Database Systems, pages 5--14. ACM, 2012.

Digital Library

[3]

R. Andersen and F. Chung. Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm. Theory and Applications of Models of Computation, 4484/2007:1--12, 2007.

Digital Library

[4]

R. Andersen, F. Chung, and K. Lang. Local Graph Partitioning using PageRank Vectors. FOCS, pages 475--486, 2006.

Digital Library

[5]

N. T. K. Anh, V. M. Thanh, and N. V. Linh. Efficient label propagation for classification on information networks. In Proceedings of the Third Symposium on Information and Communication Technology, SoICT '12, pages 41--46, New York, NY, USA, 2012. ACM.

Digital Library

[6]

A.-L. Barabasi. Linked: the new science of networks. Perseus Publishing, 2002.

Digital Library

[7]

P. Berkhin. Bookmark-coloring algorithm for personalized pagerank computing. Internet Math, 3:2006.

[8]

A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In Proceedings of the International Conference on Machine Learning (ICML), 2006.

Digital Library

[9]

B. Bollobas. Modern Graph Theory. Springer, July 1998.

[10]

Y.-Y. Chen, Q. Gan, and T. Suel. Local methods for estimating pagerank values. In CIKM, pages 381--389. ACM, 2004.

Digital Library

[11]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990.

Digital Library

[12]

J. V. Davis and I. S. Dhillon. Estimating the global pagerank of web communities. In SIGKDD, pages 116--125. ACM, 2006.

Digital Library

[13]

C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. KDD, 2004.

Digital Library

[14]

D. Fogaras and B. Racz. Towards scaling fully personalized pagerank. In WAW, pages 105--117, 2004.

[15]

T. H. Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. TKDE, 15:2003, 2003.

Digital Library

[16]

S. Hossain, P. Butler, A. P. Boedihardjo, and N. Ramakrishnan. Storytelling in entity networks to support intelligence analysts. In Proceedings of SIGKDD, 2012.

Digital Library

[17]

H. Hu, D. L. Lee, and J. Xu. Fast Nearest Neighbor Search on Road Networks. In EDBT, pages 186--203, 2006.

Digital Library

[18]

G. Jeh and J. Widom. Simrank: a measure of structural-context similarity. In SIGKDD, pages 538--543. ACM, 2002.

Digital Library

[19]

G. Jeh and J. Widom. Scaling personalized web search. WWW, 2003.

Digital Library

[20]

G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1):359--392, 1998.

Digital Library

[21]

Y. Koren, S. C. North, and C. Volinsky. Measuring and extracting proximity in networks. KDD, 06, 2006.

Digital Library

[22]

R. Kumar, A. Tomkins, and E. Vee. Connectivity structure of bipartite graphs via the knc-plot. In Proceedings of WSDM, 2008.

Digital Library

[23]

L. Lovász. Random Walks on Graphs: A Survey. Combinatorics, Paul Erdos is Eighty, 2:1--46, 1993.

[24]

L. Lovasz and M. Simonovits. The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. In SFCS, 1990.

Digital Library

[25]

K. L. McGary, I. Lee, and E. M. Marcotte. Broad network-based predictability of Saccharomyces cerevisiae gene loss-of-function phenotypes. Genome biology, 8(12):R258, 2007.

[26]

A. Mislove, H. S. Koppula, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Growth of the flickr social network. In WOSN, 2008.

Digital Library

[27]

E. Nabieva, K. Jim, A. Agarwal, B. Chazelle, and M. Singh. Whole proteome prediction of protein function via graph-theoretic analysis of interaction maps. Bioinformatics, 21(1):302--310, 2005.

Digital Library

[28]

F. Nie, S. Xiang, Y. Liu, and C. Zhang. A general graph-based semi supervised learning with novel class discovery. Neural Computing and Applications, 19(4):549--555, 2010.

Digital Library

[29]

H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In SIGMOD, 2008.

Digital Library

[30]

P. Sarkar and A. W. Moore. A tractable approach to finding closest truncated-commute-time neighbors in large graphs. In UAI, 2007.

[31]

P. Sarkar, A. W. Moore, and A. Prakash. Fast incremental proximity search in large graphs. In ICML, New York, New York, USA, 2008.

Digital Library

[32]

V. Satuluri, S. Parthasarathy, and Y. Ruan. Local graph sparsification for scalable clustering. In Proceedings of the 2011 international conference on Management of data, pages 721--732. ACM, 2011.

Digital Library

[33]

H. Tong, C. Faloutsos, and Y. Koren. Fast direction-aware proximity for graph mining. SIGKDD, 2007.

Digital Library

[34]

H. Tong, H. Qu, and H. Jamjoom. Measuring Proximity on Graphs with Side Information. ICDM, 2008.

Digital Library

[35]

H. Tong, H. Qu, H. Jamjoom, and C. Faloutsos. iPoG: Fast Interactive Proximity Querying on Graphs. CIKM, pages 1673--1676, 2009.

Digital Library

[36]

Y. Wu and L. Raschid. Approxrank: Estimating rank for a subgraph. ICDE, pages 54--65, 2009.

Digital Library

Cited By

Berloco CDe Francisci Morales GFrassineti DGreco GKumarasinghe HLamieri MMassaro EMiola AYang S(2021)Predicting corporate credit risk: Network contagion via trade creditPLOS ONE10.1371/journal.pone.025011516:4(e0250115)Online publication date: 29-Apr-2021
https://doi.org/10.1371/journal.pone.0250115
Coşkun MGrama AKoyutürk M(2018)Indexed fast network proximity queryingProceedings of the VLDB Endowment10.14778/3204028.320402911:8(840-852)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.14778/3204028.3204029
Shankaralingappa DDe Fransicsi Morales GGionis AMukhopadhyay SZhai CBertino ECrestani FMostafa JTang JSi LZhou XChang YLi YSondhi P(2016)Extracting Skill Endorsements from Personal Communication DataProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983884(1961-1964)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2983323.2983884
Show More Cited By

Index Terms

Accurate and scalable nearest neighbors in large networks based on effective importance
1. Information systems
  1. Information retrieval

Recommendations

Nearest Neighbors by Neighborhood Counting

Finding nearest neighbors is a general idea that underlies many artificial intelligence tasks, including machine learning, data mining, natural language understanding, and information retrieval. This idea is explicitly used in the k-nearest neighbors ...
Fast and Accurate Handwritten Character Recognition Using Approximate Nearest Neighbours Search on Large Databases
Proceedings of the Joint IAPR International Workshops on Advances in Pattern Recognition

In this work, fast approximate nearest neighbours search algorithms are shown to provide high accuracies, similar to those of exact nearest neighbour search, at a fraction of the computational cost in an OCR task. Recent studies [26,15] have shown the ...
Large Scale Nearest Neighbors Search Based on Neighborhood Graph
CBD '13: Proceedings of the 2013 International Conference on Advanced Cloud and Big Data

Large scale approximate k-nearest neighbors search is an important and very useful technique for many multimedia retrieval applications. Most of existing search algorithms used the centralized indexing approaches and thus cannot meet the needs to search ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

October 2013

2612 pages

ISBN:9781450322638

DOI:10.1145/2505515

General Chairs:
Qi He
LinkedIn, USA
,
Arun Iyengar
IBM T.J. Watson Research Center, USA
,
Program Chairs:
Wolfgang Nejdl
L3S Research Center, Germany
,
Jian Pei
Simon Fraser University, Canada
,
Rajeev Rastogi
Amazon, India

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM'13

Sponsor:

CIKM'13: 22nd ACM International Conference on Information and Knowledge Management

October 27 - November 1, 2013

California, San Francisco, USA

Acceptance Rates

CIKM '13 Paper Acceptance Rate 143 of 848 submissions, 17%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
265
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Berloco CDe Francisci Morales GFrassineti DGreco GKumarasinghe HLamieri MMassaro EMiola AYang S(2021)Predicting corporate credit risk: Network contagion via trade creditPLOS ONE10.1371/journal.pone.025011516:4(e0250115)Online publication date: 29-Apr-2021
https://doi.org/10.1371/journal.pone.0250115
Coşkun MGrama AKoyutürk M(2018)Indexed fast network proximity queryingProceedings of the VLDB Endowment10.14778/3204028.320402911:8(840-852)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.14778/3204028.3204029
Shankaralingappa DDe Fransicsi Morales GGionis AMukhopadhyay SZhai CBertino ECrestani FMostafa JTang JSi LZhou XChang YLi YSondhi P(2016)Extracting Skill Endorsements from Personal Communication DataProceedings of the 25th ACM International on Conference on Information and Knowledge Management10.1145/2983323.2983884(1961-1964)Online publication date: 24-Oct-2016
https://dl.acm.org/doi/10.1145/2983323.2983884
Coskun MGrama AKoyuturk MKrishnapuram BShah MSmola AAggarwal CShen DRastogi R(2016)Efficient Processing of Network Proximity Queries via Chebyshev AccelerationProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining10.1145/2939672.2939828(1515-1524)Online publication date: 13-Aug-2016
https://dl.acm.org/doi/10.1145/2939672.2939828
Li LYao YTang JFan WTong HKrishnapuram BShah MSmola AAggarwal CShen DRastogi R(2016)QUINTProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining10.1145/2939672.2939768(985-994)Online publication date: 13-Aug-2016
https://dl.acm.org/doi/10.1145/2939672.2939768
Jung JShin KSael LKang U(2016)Random Walk with Restart on Large Graphs Using Block EliminationACM Transactions on Database Systems10.1145/290173641:2(1-43)Online publication date: 11-May-2016
https://dl.acm.org/doi/10.1145/2901736
Wu YJin RZhang X(2016)Efficient and Exact Local Search for Random Walk Based Top-K Proximity Query in Large GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.251557928:5(1160-1174)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TKDE.2016.2515579
Zhang XChen ZZhong WBoedihardjo ALu C(2016)Storytelling in heterogeneous Twitter entity network based on hierarchical cluster routing2016 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2016.7840760(1522-1531)Online publication date: Dec-2016
https://doi.org/10.1109/BigData.2016.7840760
Yin JGao L(2016)Asynchronous Distributed Incremental Computation on Evolving GraphsMachine Learning and Knowledge Discovery in Databases10.1007/978-3-319-46227-1_45(722-738)Online publication date: 4-Sep-2016
https://doi.org/10.1007/978-3-319-46227-1_45
Shin KJung JLee SKang USellis TDavidson SIves Z(2015)BEARProceedings of the 2015 ACM SIGMOD International Conference on Management of Data10.1145/2723372.2723716(1571-1585)Online publication date: 27-May-2015
https://dl.acm.org/doi/10.1145/2723372.2723716
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents