Xiafei Qiu
Abstract
As graph data is prevalent for an increasing number of Internet applications, continuously monitoring structural patterns in dynamic graphs in order to generate real-time alerts and trigger prompt actions becomes critical for many applications. In this paper, we present a new system GraphS to efficiently detect constrained cycles in a dynamic graph, which is changing constantly, and return the satisfying cycles in real-time. A hot point based index is built and efficiently maintained for each query so as to greatly speed-up query time and achieve high system throughput. The GraphS system is developed at Alibaba to actively monitor various online fraudulent activities based on cycle detection. For a dynamic graph with hundreds of millions of edges and vertices, the system is capable to cope with a peak rate of tens of thousands of edge updates per second and find all the cycles with predefined constraints with a 99.9% latency of 20 milliseconds.
- T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In the proceeding of ACM SIGMOD conference, pages 349--360, 2013. Google Scholar
Digital Library
- T. Akiba, Y. Yano, and N. Mizuno. Hierarchical and dynamic k-path covers. In the proceeding of the ACM International Conference on Information and Knowledge Management (CIKM), pages 1543--1552, 2016. Google ScholarDigital Library
- Apache Flink. http://flink.apache.org/.Google Scholar
- Apache Storm. http://storm.apache.org/.Google Scholar
- A. Bernstein and S. Chechik. Incremental topological sort and cycle detection in expected total time. In SODA, pages 21--34, 2018. Google ScholarDigital Library
- J. Cheng, S. Huang, H. Wu, and A. W. Fu. Tf-label: a topological-folding labeling scheme for reachability querying in a large graph. In the proceeding of ACM SIGMOD conference, pages 193--204, 2013. Google ScholarDigital Library
- J. Cheng, Z. Shang, H. Cheng, H. Wang, and J. X. Yu. K-reach: Who is in your small world. PVLDB, 5(11):1292--1303, 2012. Google ScholarDigital Library
- S. Choudhury, L. B. Holder, G. C. Jr., K. Agarwal, and J. Feo. A selectivity based approach to continuous pattern detection in streaming graphs. In the proceeding of the International Conference on Extending Database Technology (EDBT), pages 157--168, 2015.Google Scholar
- W. Fan, J. Li, J. Luo, Z. Tan, X. Wang, and Y. Wu. Incremental graph pattern matching. In the proceeding of ACM SIGMOD conference, pages 925--936, 2011. Google ScholarDigital Library
- B. Gallagher. Matching structure and semantics: A survey on graph-based pattern matching. 6, 01 2006.Google Scholar
- J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica. Graphx: Graph processing in a distributed dataflow framework. In the proceeding of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 599--613, 2014. Google ScholarDigital Library
- M. Jiang, A. W. Fu, R. C. Wong, and Y. Xu. Hop doubling label indexing for point-to-point distance querying on scale-free networks. PVLDB, 7(12):1203--1214, 2014. Google ScholarDigital Library
- R. Jin and G. Wang. Simple, fast, and scalable reachability oracle. PVLDB, 6(14):1978--1989, 2013. Google ScholarDigital Library
- C. Kankanamge, S. Sahu, A. Mhedbhi, J. Chen, and S. Salihoglu. Graphflow: An active graph database. In the proceeding of ACM SIGMOD conference, pages 1695--1698, 2017. Google ScholarDigital Library
- A. A. Khan and H. Singh. Petri net approach to enumerate all simple paths in a graph. Electronics Letters, 16(8):291--292, 1980.Google ScholarCross Ref
- S. R. Kosaraju and G. F. Sullivan. Detecting cycles in dynamic graphs in polynomial time (preliminary version). In STOC, pages 398--406, 1988. Google ScholarDigital Library
- G. Malewicz, M. H. Austern, A. J. C. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In the proceeding of ACM SIGMOD conference, pages 135--146, 2010. Google ScholarDigital Library
- S. RAI and A. KUMAR. On path enumeration. International Journal of Electronics, 60(3):421--425, 1986.Google ScholarCross Ref
- B. Roberts and D. P. Kroese. Estimating the number of s-t paths in a graph. J. Graph Algorithms Appl., 11(1):195--214, 2007.Google ScholarCross Ref
- F. Rubin. Enumerating all simple paths in a graph. IEEE Transactions on Circuits and Systems, 25(8):641--642, 1978.Google ScholarCross Ref
- S. Seufert, A. Anand, S. J. Bedathur, and G. Weikum. FERRARI: flexible and efficient reachability range assignment for graph indexing. In the proceeding of the IEEE International Conference on Data Engineering (ICDE), pages 1009--1020, 2013. Google ScholarDigital Library
- O. Shmueli. Dynamic cycle detection. Inf. Process. Lett., 17(4):185--188, 1983.Google ScholarCross Ref
- C. Sommer. Shortest-path queries in static networks. ACM Comput. Surv., 46(4):45:1--45:31, 2014. Google ScholarDigital Library
- The Rust Programming Language. https://www.rust-lang.org/.Google Scholar
- H. Wei, J. X. Yu, C. Lu, and R. Jin. Reachability querying: An independent permutation labeling approach. PVLDB, 7(12):1191--1202, 2014. Google ScholarDigital Library
- H. Yildirim, V. Chaoji, and M. J. Zaki. GRAIL: scalable reachability index for large graphs. PVLDB, 3(1):276--284, 2010. Google ScholarDigital Library
- J. X. Yu and J. Cheng. Graph reachability queries: A survey. In Managing and Mining Graph Data, pages 181--215. 2010.Google ScholarCross Ref
- J. Zhou, S. Zhou, J. X. Yu, H. Wei, Z. Chen, and X. Tang. DAG reduction: Fast answering reachability queries. In the proceeding of ACM SIGMOD conference, pages 375--390, 2017. Google ScholarDigital Library
- A. D. Zhu, W. Lin, S. Wang, and X. Xiao. Reachability queries on large dynamic graphs: a total order approach. In the proceeding of ACM SIGMOD conference, pages 1323--1334, 2014. Google ScholarDigital Library
Index Terms
- Real-time constrained cycle detection in large dynamic graphs
Recommendations
Cycle transversals in perfect graphs and cographs
A cycle transversal (or feedback vertex set) of a graph G is a subset T@__ __V(G) such that T@__ __V(C)<>0@__ __ for every cycle C of G. This work considers the problem of finding special cycle transversals in perfect graphs and cographs. We prove that ...
Vertex arboricity of toroidal graphs with a forbidden cycle
The vertex arboricity a(G) of a graph G is the minimum k such that V(G) can be partitioned into k sets where each set induces a forest. For a planar graph G, it is known that a(G)@?3. In two recent papers, it was proved that planar graphs without k-...
Cycle extension in edge-colored complete graphs
Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily ...
Comments