{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:41:49Z","timestamp":1773895309453,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["652976"],"award-info":[{"award-number":["652976"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Alibaba Innovative Research Program"},{"name":"Royal Society Wolfson Research Merit Award","award":["WRM\/R1\/180014"],"award-info":[{"award-number":["WRM\/R1\/180014"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,9]]},"DOI":"10.1145\/3448016.3452796","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T17:22:30Z","timestamp":1624036950000},"page":"459-471","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Incrementalizing Graph Algorithms"],"prefix":"10.1145","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"University of Edinburgh & Shenzhen Institute of Computing Sciences, Edinburgh, United Kingdom"}]},{"given":"Chao","family":"Tian","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Ruiqi","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}]},{"given":"Qiang","family":"Yin","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]}],"member":"320","published-online":{"date-parts":[[2021,6,18]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"2007. Orkut. http:\/\/konect.uni-koblenz.de\/networks\/orkut-links.  2007. Orkut. http:\/\/konect.uni-koblenz.de\/networks\/orkut-links."},{"key":"e_1_3_2_2_2_1","unstructured":"2012. Friendster. https:\/\/snap.stanford.edu\/data\/com-Friendster.html.  2012. Friendster. https:\/\/snap.stanford.edu\/data\/com-Friendster.html."},{"key":"e_1_3_2_2_3_1","unstructured":"2012. LiveJournal. http:\/\/snap.stanford.edu\/data\/com-LiveJournal.html.  2012. LiveJournal. http:\/\/snap.stanford.edu\/data\/com-LiveJournal.html."},{"key":"e_1_3_2_2_4_1","unstructured":"2012. Twitter-2010. http:\/\/law.di.unimi.it\/webdata\/twitter-2010\/.  2012. Twitter-2010. http:\/\/law.di.unimi.it\/webdata\/twitter-2010\/."},{"key":"e_1_3_2_2_5_1","unstructured":"2012. Wiki-de. http:\/\/konect.uni-koblenz.de\/networks\/link-dynamic-dewiki.  2012. Wiki-de. http:\/\/konect.uni-koblenz.de\/networks\/link-dynamic-dewiki."},{"key":"e_1_3_2_2_6_1","unstructured":"2014. DBpedia. http:\/\/wiki.dbpedia.org\/Downloads2014.  2014. DBpedia. http:\/\/wiki.dbpedia.org\/Downloads2014."},{"key":"e_1_3_2_2_7_1","unstructured":"2020. https:\/\/github.com\/yogesh1q2w\/Dynamic-Graph-Algorithms.  2020. https:\/\/github.com\/yogesh1q2w\/Dynamic-Graph-Algorithms."},{"key":"e_1_3_2_2_8_1","unstructured":"2020. GRAPE. https:\/\/github.com\/alibaba\/libgrape-lite.git.  2020. GRAPE. https:\/\/github.com\/alibaba\/libgrape-lite.git."},{"key":"e_1_3_2_2_9_1","volume-title":"Foundations of Databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul , Richard Hull , and Victor Vianu . 1995. Foundations of Databases . Addison-Wesley . Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Lars Backstrom Dan Huttenlocher Jon Kleinberg and Xiangyang Lan. 2006. Group formation in large social networks: Membership growth and evolution. In SIGKDD.  Lars Backstrom Dan Huttenlocher Jon Kleinberg and Xiangyang Lan. 2006. Group formation in large social networks: Membership growth and evolution. In SIGKDD.","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_3_2_2_12_1","volume-title":"Gutin","author":"Bang-Jensen J\u00f8rgen","year":"2009","unstructured":"J\u00f8rgen Bang-Jensen and Gregory Z . Gutin . 2009 . Digraphs - Theory, Algorithms and Applications , Second Edition .Springer. J\u00f8rgen Bang-Jensen and Gregory Z. Gutin. 2009. Digraphs - Theory, Algorithms and Applications, Second Edition .Springer."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi Marco Rosa Massimo Santini and Sebastiano Vigna. 2011. Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks. In WWW.  Paolo Boldi Marco Rosa Massimo Santini and Sebastiano Vigna. 2011. Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks. In WWW.","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In WWW.  Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In WWW.","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Yufei Cai Paolo G. Giarrusso Tillmann Rendel and Klaus Ostermann. 2014. A theory of changes for higher-order languages: Incrementalizing (\u0142ambda)-calculi by static differentiation. In PLDI.  Yufei Cai Paolo G. Giarrusso Tillmann Rendel and Klaus Ostermann. 2014. A theory of changes for higher-order languages: Incrementalizing (\u0142ambda)-calculi by static differentiation. In PLDI.","DOI":"10.1145\/2594291.2594304"},{"key":"e_1_3_2_2_16_1","unstructured":"Zhuhua Cai Dionysios Logothetis and Georgos Siganos. 2012. Facilitating real-time graph mining. In CloudDB.  Zhuhua Cai Dionysios Logothetis and Georgos Siganos. 2012. Facilitating real-time graph mining. In CloudDB."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.198"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Camil Demetrescu David Eppstein Zvi Galil and Giuseppe F Italiano. 2010. Dynamic graph algorithms. In Algorithms and theory of computation handbook.  Camil Demetrescu David Eppstein Zvi Galil and Giuseppe F Italiano. 2010. Dynamic graph algorithms. In Algorithms and theory of computation handbook.","DOI":"10.1201\/9781584888239-c9"},{"key":"e_1_3_2_2_19_1","volume-title":"IPDPS Workshop.","author":"Ediger David","unstructured":"David Ediger , Karl Jiang , E. Jason Riedy , and David A. Bader . 2010. Massive streaming data analytics: A case study with clustering coefficients . In IPDPS Workshop. David Ediger, Karl Jiang, E. Jason Riedy, and David A. Bader. 2010. Massive streaming data analytics: A case study with clustering coefficients. In IPDPS Workshop."},{"key":"e_1_3_2_2_20_1","unstructured":"Wenfei Fan Chunming Hu and Chao Tian. 2017. Incremental Graph Computations: Doable and Undoable. In SIGMOD.  Wenfei Fan Chunming Hu and Chao Tian. 2017. Incremental Graph Computations: Doable and Undoable. In SIGMOD."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389142"},{"key":"e_1_3_2_2_22_1","unstructured":"Wenfei Fan Xueli Liu Ping Lu and Chao Tian. 2018a. Catching Numeric Inconsistencies in Graphs. In SIGMOD.  Wenfei Fan Xueli Liu Ping Lu and Chao Tian. 2018a. Catching Numeric Inconsistencies in Graphs. In SIGMOD."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3282488"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_2_26_1","unstructured":"M. R. Henzinger T. Henzinger and P. Kopke. 1995. Computing Simulations on Finite and Infinite Graphs. In FOCS.  M. R. Henzinger T. Henzinger and P. Kopke. 1995. Computing Simulations on Finite and Infinite Graphs. In FOCS."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1049\/ip-vis:19952115"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT: the Koblenz network collection. In WWW.  J\u00e9r\u00f4me Kunegis. 2013. KONECT: the Koblenz network collection. In WWW.","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026547031739"},{"key":"e_1_3_2_2_33_1","unstructured":"Andreas Loukas and Pierre Vandergheynst. 2018. Spectrally Approximating Large Graphs with Smaller Graphs. In ICML.  Andreas Loukas and Pierre Vandergheynst. 2018. Spectrally Approximating Large Graphs with Smaller Graphs. In ICML."},{"key":"e_1_3_2_2_34_1","volume-title":"Zhu","author":"Luo Xusheng","year":"2020","unstructured":"Xusheng Luo , Luxin Liu , Yonghua Yang , Le Bo , Yuanpeng Cao , Jinghang Wu , Qiang Li , Keping Yang , and Kenny Q . Zhu . 2020 . AliCoCo: Alibaba E-commerce Cognitive Concept Net. In SIGMOD. Xusheng Luo, Luxin Liu, Yonghua Yang, Le Bo, Yuanpeng Cao, Jinghang Wu, Qiang Li, Keping Yang, and Kenny Q. Zhu. 2020. AliCoCo: Alibaba E-commerce Cognitive Concept Net. In SIGMOD."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Mugilan Mariappan and Keval Vora. 2019. GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs. In EuroSys.  Mugilan Mariappan and Keval Vora. 2019. GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs. In EuroSys.","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_3_2_2_36_1","volume-title":"Rebecca Isaacs, and Michael Isard.","author":"McSherry Frank","year":"2013","unstructured":"Frank McSherry , Derek Gordon Murray , Rebecca Isaacs, and Michael Isard. 2013 . Differential Dataflow. In CIDR. Frank McSherry, Derek Gordon Murray, Rebecca Isaacs, and Michael Isard. 2013. Differential Dataflow. In CIDR."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Alan Mislove Massimiliano Marcon Krishna P. Gummadi Peter Druschel and Bobby Bhattacharjee. 2007. Measurement and Analysis of Online Social Networks. In IMC.  Alan Mislove Massimiliano Marcon Krishna P. Gummadi Peter Druschel and Bobby Bhattacharjee. 2007. Measurement and Analysis of Online Social Networks. In IMC.","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_3_2_2_39_1","first-page":"1","article-title":"a","volume":"158","author":"Ramalingam G.","year":"1996","unstructured":"G. Ramalingam and Thomas Reps . 1996 a . On the Computational Complexity of Dynamic Graph Problems. Theor. Comput. Sci. , Vol. 158 , 1 -- 2 (1996). G. Ramalingam and Thomas Reps. 1996 a. On the Computational Complexity of Dynamic Graph Problems. Theor. Comput. Sci., Vol. 158, 1--2 (1996).","journal-title":"On the Computational Complexity of Dynamic Graph Problems. Theor. Comput. Sci."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0046"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Thomas Schank and Dorothea Wagner. 2005. Finding Counting and Listing All Triangles in Large Graphs an Experimental Study. In WEA.  Thomas Schank and Dorothea Wagner. 2005. Finding Counting and Listing All Triangles in Large Graphs an Experimental Study. In WEA.","DOI":"10.1007\/11427186_54"},{"key":"e_1_3_2_2_42_1","unstructured":"Siddharth Suri and Sergei Vassilvitskii. 2011. Counting triangles and the curse of the last reducer. In WWW.  Siddharth Suri and Sergei Vassilvitskii. 2011. Counting triangles and the curse of the last reducer. In WWW."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358755"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"crossref","unstructured":"Keval Vora Rajiv Gupta and Guoqing (Harry) Xu. 2017. KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations. In ASPLOS.  Keval Vora Rajiv Gupta and Guoqing (Harry) Xu. 2017. KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations. In ASPLOS.","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Qiange Wang Yanfeng Zhang Hao Wang Liang Geng Rubao Lee Xiaodong Zhang and Ge Yu. 2020. Automating Incremental and Asynchronous Evaluation for Recursive Aggregate Data Processing. In SIGMOD.  Qiange Wang Yanfeng Zhang Hao Wang Liang Geng Rubao Lee Xiaodong Zhang and Ge Yu. 2020. Automating Incremental and Asynchronous Evaluation for Recursive Aggregate Data Processing. In SIGMOD.","DOI":"10.1145\/3318464.3389712"},{"key":"e_1_3_2_2_47_1","volume-title":"Nature","volume":"393","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz . 1998 . Collective dynamics of 'small-world' networks . Nature , Vol. 393 , 6684 (1998), 440--442. Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of 'small-world' networks. Nature, Vol. 393, 6684 (1998), 440--442."},{"key":"e_1_3_2_2_48_1","volume-title":"Prasanna","author":"Wickramaarachchi Charith","year":"2015","unstructured":"Charith Wickramaarachchi , Charalampos Chelmis , and Viktor K . Prasanna . 2015 . Empowering Fast Incremental Computation over Large Scale Dynamic Graphs. In IPDPS. Charith Wickramaarachchi, Charalampos Chelmis, and Viktor K. Prasanna. 2015. Empowering Fast Incremental Computation over Large Scale Dynamic Graphs. In IPDPS."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140438"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364329"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_2_52_1","unstructured":"Timothy A. K. Zakian Ludovic A. R. Capelli and Zhenjiang Hu. 2019. Incrementalization of Vertex-Centric Programs. In IPDPS.  Timothy A. K. Zakian Ludovic A. R. Capelli and Zhenjiang Hu. 2019. Incrementalization of Vertex-Centric Programs. In IPDPS."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"crossref","unstructured":"Li Zheng Zhenpeng Li Jian Li Zhao Li and Jun Gao. 2019. AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN. In IJCAI.  Li Zheng Zhenpeng Li Jian Li Zhao Li and Jun Gao. 2019. AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN. In IJCAI.","DOI":"10.24963\/ijcai.2019\/614"},{"key":"e_1_3_2_2_54_1","first-page":"2094","article-title":"AliGraph","volume":"12","author":"Zhu Rong","year":"2019","unstructured":"Rong Zhu , Kun Zhao , Hongxia Yang , Wei Lin , Chang Zhou , Baole Ai , Yong Li , and Jingren Zhou . 2019 . AliGraph : A Comprehensive Graph Neural Network Platform. PVLDB , Vol. 12 , 12 (2019), 2094 -- 2105 . Rong Zhu, Kun Zhao, Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. 2019. AliGraph: A Comprehensive Graph Neural Network Platform. PVLDB, Vol. 12, 12 (2019), 2094--2105.","journal-title":"A Comprehensive Graph Neural Network Platform. PVLDB"}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2021 International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452796","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448016.3452796","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:05Z","timestamp":1750195685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448016.3452796"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":53,"alternative-id":["10.1145\/3448016.3452796","10.1145\/3448016"],"URL":"https:\/\/doi.org\/10.1145\/3448016.3452796","relation":{},"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"2021-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}