Fast Exact CoSimRank Search on Evolving and Static Graphs

Weiren Yu, Fan Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, \DCoSim for accurate CoSimRank search over evolving graphs. Based on \DCoSim, we also propose a fast scheme, \FCoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that \DCoSim and \FCoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores $\mathbfS $, \FCoSim is based on three ideas: (i) It first finds a "spanning polytree»» T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores $\mathbfS (T)$ over the "spanning polytree»» T. (iii) On G, \DCoSim is employed to compute the changes of $\mathbfS (T)$ in response to the delta graph $(G øminus T)$. Experimental evaluations verify the superiority of \DCoSim over evolving graphs, and the fast speedup of \FCoSim on large-scale static graphs against its competitors, without any loss of accuracy.
Original languageEnglish
Title of host publicationWWW '18 Proceedings of the 2018 World Wide Web Conference
PublisherACM
Pages599-608
ISBN (Print)978-1-4503-5639-8
DOIs
Publication statusPublished - 10 Apr 2018
Eventthe 2018 World Wide Web Conference - Lyon, France
Duration: 23 Apr 201827 Apr 2018

Conference

Conferencethe 2018 World Wide Web Conference
Period23/04/1827/04/18

Fingerprint

Topology
Costs

Bibliographical note

Copyright:ACM

Cite this

Yu, W., & Wang, F. (2018). Fast Exact CoSimRank Search on Evolving and Static Graphs. In WWW '18 Proceedings of the 2018 World Wide Web Conference (pp. 599-608). ACM. https://doi.org/10.1145/3178876.3186126
Yu, Weiren ; Wang, Fan. / Fast Exact CoSimRank Search on Evolving and Static Graphs. WWW '18 Proceedings of the 2018 World Wide Web Conference. ACM, 2018. pp. 599-608
@inproceedings{c25b5730081d406988143df6b6b3ba59,
title = "Fast Exact CoSimRank Search on Evolving and Static Graphs",
abstract = "In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, \DCoSim for accurate CoSimRank search over evolving graphs. Based on \DCoSim, we also propose a fast scheme, \FCoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that \DCoSim and \FCoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores $\mathbfS $, \FCoSim is based on three ideas: (i) It first finds a {"}spanning polytree»» T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores $\mathbfS (T)$ over the {"}spanning polytree»» T. (iii) On G, \DCoSim is employed to compute the changes of $\mathbfS (T)$ in response to the delta graph $(G {\o}minus T)$. Experimental evaluations verify the superiority of \DCoSim over evolving graphs, and the fast speedup of \FCoSim on large-scale static graphs against its competitors, without any loss of accuracy.",
author = "Weiren Yu and Fan Wang",
note = "Copyright:ACM",
year = "2018",
month = "4",
day = "10",
doi = "10.1145/3178876.3186126",
language = "English",
isbn = "978-1-4503-5639-8",
pages = "599--608",
booktitle = "WWW '18 Proceedings of the 2018 World Wide Web Conference",
publisher = "ACM",
address = "United States",

}

Yu, W & Wang, F 2018, Fast Exact CoSimRank Search on Evolving and Static Graphs. in WWW '18 Proceedings of the 2018 World Wide Web Conference. ACM, pp. 599-608, the 2018 World Wide Web Conference, 23/04/18. https://doi.org/10.1145/3178876.3186126

Fast Exact CoSimRank Search on Evolving and Static Graphs. / Yu, Weiren; Wang, Fan.

WWW '18 Proceedings of the 2018 World Wide Web Conference. ACM, 2018. p. 599-608.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Fast Exact CoSimRank Search on Evolving and Static Graphs

AU - Yu, Weiren

AU - Wang, Fan

N1 - Copyright:ACM

PY - 2018/4/10

Y1 - 2018/4/10

N2 - In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, \DCoSim for accurate CoSimRank search over evolving graphs. Based on \DCoSim, we also propose a fast scheme, \FCoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that \DCoSim and \FCoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores $\mathbfS $, \FCoSim is based on three ideas: (i) It first finds a "spanning polytree»» T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores $\mathbfS (T)$ over the "spanning polytree»» T. (iii) On G, \DCoSim is employed to compute the changes of $\mathbfS (T)$ in response to the delta graph $(G øminus T)$. Experimental evaluations verify the superiority of \DCoSim over evolving graphs, and the fast speedup of \FCoSim on large-scale static graphs against its competitors, without any loss of accuracy.

AB - In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, \DCoSim for accurate CoSimRank search over evolving graphs. Based on \DCoSim, we also propose a fast scheme, \FCoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that \DCoSim and \FCoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores $\mathbfS $, \FCoSim is based on three ideas: (i) It first finds a "spanning polytree»» T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores $\mathbfS (T)$ over the "spanning polytree»» T. (iii) On G, \DCoSim is employed to compute the changes of $\mathbfS (T)$ in response to the delta graph $(G øminus T)$. Experimental evaluations verify the superiority of \DCoSim over evolving graphs, and the fast speedup of \FCoSim on large-scale static graphs against its competitors, without any loss of accuracy.

UR - https://dl.acm.org/citation.cfm?doid=3178876.3186126

U2 - 10.1145/3178876.3186126

DO - 10.1145/3178876.3186126

M3 - Conference contribution

SN - 978-1-4503-5639-8

SP - 599

EP - 608

BT - WWW '18 Proceedings of the 2018 World Wide Web Conference

PB - ACM

ER -

Yu W, Wang F. Fast Exact CoSimRank Search on Evolving and Static Graphs. In WWW '18 Proceedings of the 2018 World Wide Web Conference. ACM. 2018. p. 599-608 https://doi.org/10.1145/3178876.3186126