Skip to content

axtonsun/awesome-streaming-graphs

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

14 Commits
README.md
README.md
 
 

Repository files navigation

awesome-streaming-graphs

Awesome

Must-read papers on streaming graph

Content

1. Keynote
2. Survey
3. System
4. Graph Stream Summarization
5. Exact Algorithms
 5.1 Subgraph Matching  5.2 Regular Path Query
6. Approximation Algorithms
 6.1 Triangle Count  6.2 Butterfly Count

Keynote

  1. Streaming Graph Processing and Analytics. [slides] [DEBS'20 video] [PKUMOD'20 video]

    M. Tamer Özsu.

  2. Graph Processing: A Panaromic View and Some open Problems. [slides] [VLDB'19 video] [PKUMOD'20 video]

    M. Tamer Özsu.

  3. An Introduction to Graph Analytics Platform - Very Short Version. [slides]

    M. Tamer Özsu.

Survey papers

  1. Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems. IEEE Trans. Parallel Distributed Syst. 34(6): 1860-1876 (2023) [paper]

    Maciej Besta, Marc Fischer, Vasiliki Kalavri, Michael Kapralov, Torsten Hoefler.

  2. 图数据流的模型、算法和系统[J]. 大数据, 2018, 4(4): 44-55. [paper]

    李友焕, 邹磊.

  3. Graph stream algorithms: a survey. SIGMOD Rec. 43(1): 9-20 (2014) [paper]

    Andrew McGregor.

System

  1. GraphGuard: Private Time-Constrained Pattern Detection Over Streaming Graphs in the Cloud. USENIX Security Symposium 2024 [paper] [slides] [video]

    Songlei Wang, Yifeng Zheng, Xiaohua Jia.

  2. LSGraph: A Locality-centric High-performance Streaming Graph Engine. EuroSys 2024: 33-49 [paper]

    Hao Qi, Yiyang Wu, Ligang He, Yu Zhang, Kang Luo, Minzhi Cai, Hai Jin, Zhan Zhang, Jin Zhao.

  3. ACGraph: Accelerating Streaming Graph Processing via Dependence Hierarchy. DAC 2023: 1-6 [paper]

    Zihan Jiang, Fubing Mao, Yapu Guo, Xu Liu, Haikun Liu, Xiaofei Liao, Hai Jin, Wei Zhang.

  4. GeaFlow: A Graph Extended and Accelerated Dataflow System. Proc. ACM Manag. Data 1(2): 191:1-191:27 (2023) [paper]

    Zhenxuan Pan, Tao Wu, Qingwen Zhao, Qiang Zhou, Zhiwei Peng, Jiefeng Li, Qi Zhang, Guanyu Feng, Xiaowei Zhu.

  5. GraphFly: Efficient Asynchronous Streaming Graphs Processing via Dependency-Flow. SC 2022: 45:1-45:14 [paper]

    Dan Chen, Chuangyi Gui, Yi Zhang, Hai Jin, Long Zheng, Yu Huang, Xiaofei Liao.

  6. TDGraph: a topology-driven accelerator for high-performance streaming graph processing. ISCA 2022: 116-129 [paper]

    Jin Zhao, Yun Yang, Yu Zhang, Xiaofei Liao, Lin Gu, Ligang He, Bingsheng He, Hai Jin, Haikun Liu, Xinyu Jiang, Hui Yu.

  7. GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams. SIGMOD Conference 2022: 325-339 [paper]

    David Tench, Evan West, Victor Zhang, Michael A. Bender, Abiyaz Chowdhury, J. Ahmed Dellas, Martin Farach-Colton, Tyler Seip, Kenny Zhang.

  8. Controlling Memory Footprint of Stateful Streaming Graph Processing. USENIX ATC 2021: 269-283 [paper] [sildes] [video]

    Pourya Vaziri, Keval Vora.

  9. RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s. SIGMOD Conference 2021: 513-527 [paper]

    Guanyu Feng, Zixuan Ma, Daixuan Li, Shengqi Chen, Xiaowei Zhu, Wentao Han, Wenguang Chen

  10. DZiG: sparsity-aware incremental processing of streaming graphs. EuroSys 2021: 83-98 [paper]

    Mugilan Mariappan, Joanna Che, Keval Vora.

  11. Exploiting Buffered Updates for Fast Streaming Graph Analysis. IEEE Trans. Computers 70(2): 255-269 (2021) [paper]

    Feng Sheng, Qiang Cao, Jie Yao.

  12. GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs. EuroSys 2019: 25:1-25:16 [paper]

    Mugilan Mariappan, Keval Vora.

  13. GraphOne: A Data Store for Real-time Analytics on Evolving Graphs. FAST 2019: 249-263 [paper] [slides] [video]

    Pradeep Kumar, H. Howie Huang.

  14. KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations. ASPLOS 2017: 237-251 [paper]

    Keval Vora, Rajiv Gupta, Guoqing Xu.

Graph Stream Summarization

  1. HourglassSketch: An Efficient and Scalable Framework for Graph Stream Summarization. ICDE 2025 [paper] [code]

    Jiarui Guo, Boxuan Chen, Kaicheng Yang, Tong Yang, Zirui Liu, Qiuheng Yin, Sha Wang, Yuhan Wu, Xiaolin Wang, Bin Cui, Tao Li, Xi Peng, Renhai Chen, Gong Zhang.

  2. HIGGS: HIerarchy-Guided Graph Stream Summarization. ICDE 2025 [paper]

    Xuan Zhao, Xike Xie, Christian S. Jensen.

  3. Mayfly: a Neural Data Structure for Graph Stream Summarization. ICLR 2024 [paper] [code]

    Yuan Feng, Yukun Cao, Hairu Wang, Xike Xie, S. Kevin Zhou.

  4. Auxo: A Scalable and Efficient Graph Stream Summarization Structure. Proc. VLDB Endow. 16(6): 1386-1398 (2023) [paper]

    Zhiguo Jiang, Hanhua Chen, Hai Jin.

  5. Horae: A Graph Stream Summarization Structure for Efficient Temporal Range Query. ICDE 2022: 2792-2804 [paper]

    Ming Chen, Renxiang Zhou, Hanhua Chen, Jiang Xiao, Hai Jin, Bo Li.

  6. Scube: Efficient Summarization for Skewed Graph Streams. ICDCS 2022: 100-110 [paper]

    Ming Chen, Renxiang Zhou, Hanhua Chen, Hai Jin.

  7. A parameter-free approach to lossless summarization of fully dynamic graphs. Inf. Sci. 589: 376-394 (2022) [paper]

    Ziyi Ma, Yuling Liu, ZhiBang Yang, Jianye Yang, Kenli Li.

  8. A Parameter-Free Approach for Lossless Streaming Graph Summarization. DASFAA (1) 2021: 385-393 [paper]

    Ziyi Ma, Jianye Yang, Kenli Li, Yuling Liu, Xu Zhou, Yikun Hu.

  9. DMatrix: Toward fast and accurate queries in graph stream. Comput. Networks 198: 108403 (2021) [paper] [code]

    Changsheng Hou, Bingnan Hou, Tongqing Zhou, Zhiping Cai.

  10. Graph Stream Sketch: Summarizing Graph Streams With High Speed and Accuracy. IEEE Trans. Knowl. Data Eng. 35(6): 5901-5914 (2023) [paper]

    Xiangyang Gou, Lei Zou, Chenxingyu Zhao, Tong Yang.

  11. Fast and Accurate Graph Stream Summarization. ICDE 2019: 1118-1129 [paper]

    Xiangyang Gou, Lei Zou, Chenxingyu Zhao, Tong Yang.

  12. Incremental Lossless Graph Summarization. KDD 2020: 317-327 [paper] [slides] [video]

    Jihoon Ko, Yunbum Kook, Kijung Shin.

  13. Graph Stream Summarization: From Big Bang to Big Crunch. SIGMOD Conference 2016: 1481-1496 [paper] [slides]

    Nan Tang, Qing Chen, Prasenjit Mitra.

  14. gSketch: On Query Estimation in Graph Streams. Proc. VLDB Endow. 5(3): 193-204 (2011) [paper]

    Peixiang Zhao, Charu C. Aggarwal, Min Wang.

Exact Algorithms

Subgraph Matching

  1. TC-Match: Fast Time-constrained Continuous Subgraph Matching. Proc. VLDB Endow. 17(11): 2791-2804 (2024) [paper] [code]

    Jianye Yang, Sheng Fang, Zhaoquan Gu, Ziyi Ma, Xuemin Lin, Zhihong Tian.

  2. CSM-TopK: Continuous Subgraph Matching with TopK Density Constraints. ICDE 2024: 3084-3097 [paper] [code]

    Chuchu Gao, Youhuan Li, Zhibang Yang, Xu Zhou.

  3. Efficient Multi-Query Oriented Continuous Subgraph Matching. ICDE 2024: 3230-3243 [paper]

    Ziyi Ma, Jianye Yang, Xu Zhou, Guoqing Xiao, Jianhua Wang, Liang Yang, Kenli Li, Xuemin Lin.

  4. Time-Constrained Continuous Subgraph Matching Using Temporal Information for Filtering and Backtracking. ICDE 2024: 3257-3269 [paper]

    Seunghwan Min, Jihoon Jang, Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, Wook-Shin Han.

  5. NewSP: A New Search Process for Continuous Subgraph Matching over Dynamic Graphs. ICDE 2024: 3324-3337 [paper]

    Ziming Li, Youhuan Li, Xinhuan Chen, Lei Zou, Yang Li, Xiaofeng Yang, Hongbo Jiang.

  6. Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction. Proc. ACM Manag. Data 1(1): 15:1-15:26 (2023) [paper] [code] [video]

    Rongjian Yang, Zhijie Zhang, Weiguo Zheng, Jeffrey Xu Yu.

  7. An In-Depth Study of Continuous Subgraph Matching. Proc. VLDB Endow. 15(7): 1403-1416 (2022) [paper] [code]

    Xibo Sun, Shixuan Sun, Qiong Luo, Bingsheng He.

  8. RapidFlow: An Efficient Approach to Continuous Subgraph Matching. Proc. VLDB Endow. 15(11): 2415-2427 (2022) [paper] [code]

    Shixuan Sun, Xibo Sun, Bingsheng He, Qiong Luo.

  9. RapidMatch: A Holistic Approach to Subgraph Query Processing. Proc. VLDB Endow. 14(2): 176-188 (2020) [paper] [code]

    Shixuan Sun, Xibo Sun, Yulin Che, Qiong Luo, Bingsheng He.

  10. Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming. Proc. VLDB Endow. 14(8): 1298-1310 (2021) [paper] [code]

    Seunghwan Min, Sung Gwan Park, Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, Wook-Shin Han.

  11. Space-Efficient Subgraph Search Over Streaming Graph With Timing Order Constraint. IEEE Trans. Knowl. Data Eng. 34(9): 4453-4467 (2022) [paper]

    Youhuan Li, Lei Zou, M. Tamer Özsu, Dongyan Zhao.

  12. Time Constrained Continuous Subgraph Search Over Streaming Graphs. ICDE 2019: 1082-1093 [paper] [code]

    Youhuan Li, Lei Zou, M. Tamer Özsu, Dongyan Zhao.

  13. TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data. SIGMOD Conference 2018: 411-426 [paper]

    Kyoungmin Kim, In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, Geonhwa Jeong.

  14. General dynamic Yannakakis: conjunctive queries with theta joins under updates. VLDB J. 29(2-3): 619-653 (2020) [paper]

    Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, Wolfgang Lehner.

  15. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. SIGMOD Conference 2017: 1259-1274 [paper]

    Muhammad Idris, Martín Ugarte, Stijn Vansummeren.

  16. Graphflow: An active graph database. SIGMOD Conference 2017: 1695-1698 [paper]

    Chathura Kankanamge, Siddhartha Sahu, Amine Mhedhbi, Jeremy Chen, Semih Salihoglu.

  17. A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs. EDBT 2015: 157-168 [paper] [slides]

    Sutanay Choudhury, Lawrence B. Holder, George Chin Jr., Khushbu Agarwal, John Feo.

  18. Incremental graph pattern matching. ACM Trans. Database Syst. 38(3): 18 (2013) [paper]

    Wenfei Fan, Xin Wang, Yinghui Wu.

  19. Incremental graph pattern matching. SIGMOD Conference 2011: 925-936 [paper]

    Wenfei Fan, Jianzhong Li, Jizhou Luo, Zijing Tan, Xin Wang, Yinghui Wu.

Regular Path Query

  1. MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs. Proc. ACM Manag. Data 2(1): 5:1-5:26 (2024) [paper]

    Siyuan Zhang, Zhenying He, Yinan Jing, Kai Zhang, X. Sean Wang.

  2. LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs. Proc. VLDB Endow. 17(5): 1047-1059 [paper] [code]

    Xiangyang Gou, Xinyi Ye, Lei Zou, Jeffrey Xu Yu.

  3. Evaluating complex queries on streaming graphs. ICDE 2022: 272-285 [paper] [code] [slides] [video]

    Anil Pacaci, Angela Bonifati, M. Tamer Özsu.

  4. Regular Path Query Evaluation on Streaming Graphs. SIGMOD Conference 2020: 1415-1430 [paper] [slides] [video]

    Anil Pacaci, Angela Bonifati, M. Tamer Özsu.

Approximation Algorithms

Triangle Count

  1. Fast and Accurate Triangle Counting in Graph Streams Using Predictions. ICDM 2024 [paper] [code]

    Cristian Boldrin, Fabio Vandin.

  2. Compact Estimator for Streaming Triangle Counting. IEEE Trans. Knowl. Data Eng. 36(8): 3712-3724 (2024) [paper]

    Jiqing Gu, Chao Song, Haipeng Dai, Li Lu, Ming Liu.

  3. Sliding window-based approximate triangle counting with bounded memory usage. VLDB J. 32(5): 1087-1110 (2023) [paper] [code]

    Xiangyang Gou, Lei Zou.

  4. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. SIGMOD Conference 2021: 645-657 [paper] [code]

    Xiangyang Gou, Lei Zou.

  5. Distributed Triangle Approximately Counting Algorithms in Simple Graph Stream. ACM Trans. Knowl. Discov. Data 16(4): 79:1-79:43 (2022) [paper] [code]

    Xu Yang, Chao Song, Mengdi Yu, Jiqing Gu, Ming Liu.

  6. Distributed Triangle Counting Algorithms in Simple Graph Stream. ICPADS 2019: 294-301 [paper]

    Mengdi Yu, Chao Song, Jiqing Gu, Ming Liu.

  7. CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams. ACM Trans. Knowl. Discov. Data 15(3): 38:1-38:30 (2021) [paper] [code]

    Kijung Shin, Euiwoong Lee, Jinoh Oh, Mohammad Hammoud, Christos Faloutsos.

  8. Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams. PAKDD (3) 2018: 651-663 [paper] [code]

    Kijung Shin, Mohammad Hammoud, Euiwoong Lee, Jinoh Oh, Christos Faloutsos.

  9. Fast, Accurate and Provable Triangle Counting in Fully Dynamic Graph Streams. ACM Trans. Knowl. Discov. Data 14(2): 12:1-12:39 (2020) [paper] [code]

    Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, Christos Faloutsos.

  10. Think Before You Discard: Accurate Triangle Counting in Graph Streams with Deletions. ECML/PKDD (2) 2018: 141-157 [paper] [code]

    Kijung Shin, Jisu Kim, Bryan Hooi, Christos Faloutsos.

  11. Temporal locality-aware sampling for accurate triangle counting in real graph streams. VLDB J. 29(6): 1501-1525 (2020) [paper] [code]

    Dongjin Lee, Kijung Shin, Christos Faloutsos.

  12. WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams. . ICDM 2017: 1087-1092 [paper] [code]

    Kijung Shin.

  13. REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel. ICDE 2019: 758-769 [paper]

    Pinghui Wang, Peng Jia, Yiyan Qi, Yu Sun, Jing Tao, Xiaohong Guan

  14. FURL: Fixed-memory and uncertainty reducing local triangle counting for multigraph streams. Data Min. Knowl. Discov. 33(5): 1225-1253 (2019) [paper] [Code]

    Minsoo Jung, Yongsub Lim, Sunmin Lee, U Kang.

  15. Memory-Efficient and Accurate Sampling for Counting Local Triangles in Graph Streams: From Simple to Multigraphs. ACM Trans. Knowl. Discov. Data 12(1): 4:1-4:28 (2018) [paper] [Code]

    Yongsub Lim, Minsoo Jung, U Kang.

  16. MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams. KDD 2015: 685-694 [paper] [Code]

    Yongsub Lim, U Kang.

  17. Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage. Proc. VLDB Endow. 11(2): 162-175 (2017) [paper]

    Pinghui Wang, Yiyan Qi, Yu Sun, Xiangliang Zhang, Jing Tao, Xiaohong Guan.

  18. TRIÈST: Counting Local and Global Triangles in Fully Dynamic Streams with Fixed Memory Size. ACM Trans. Knowl. Discov. Data 11(4): 43:1-43:50 (2017) [paper] [code]

    Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal.

  19. TRIÈST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size. KDD 2016: 825-834 [paper] [code]

    Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal.

Butterfly Count

  1. FABLE: Approximate Butterfly Counting in Bipartite Graph Stream with Duplicate Edges. CIKM 2024: 2158-2167 [paper]

    Guozhang Sun, Yuhai Zhao, Yuan Li.

  2. Counting Butterflies in Fully Dynamic Bipartite Graph Streams. ICDE 2024: 2917-2930 [paper]

    Serafeim Papadias, Zoi Kaoudi, Varun Pandey, Jorge-Arnulfo Quiané-Ruiz, Volker Markl.

  3. Approximately Counting Butterflies in Large Bipartite Graph Streams. IEEE Trans. Knowl. Data Eng. 34(12): 5621-5635 (2022) [paper]

    Rundong Li, Pinghui Wang, Peng Jia, Xiangliang Zhang, Junzhou Zhao, Jing Tao, Ye Yuan, Xiaohong Guan.

  4. sGrapp: Butterfly Approximation in Streaming Graphs. ACM Trans. Knowl. Discov. Data 16(4): 76:1-76:43 (2022) [paper] [code]

    Aida Sheshbolouki, M. Tamer Özsu.

  5. FLEET: Butterfly Estimation from a Bipartite Graph Stream. CIKM 2019: 1201-1210 [paper] [code]

    Seyed-Vahid Sanei-Mehri, Yu Zhang, Ahmet Erdem Sariyüce, Srikanta Tirthapura.

About

Must-read papers on streaming graph

Topics

paper-list graph-stream streaming-graph

Resources

Readme
Activity

Stars

1 star

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published