Efficient video generation models are increasingly vital for multimedia synthetic content generation. Leveraging the Transformer architecture and the diffusion process, video DiT models have emerged as a dominant approach for high-quality video generation. However, their multi-step iterative denoising process incurs high computational cost and inference latency, which limits their practical deployment in large-scale and interactive multimedia applications. Caching, a widely adopted optimization method in DiT models, leverages the redundancy in the diffusion process to skip computations in different granularities (e.g., step, cfg, block). Nevertheless, existing caching methods are limited to single-granularity strategies, struggling to balance generation quality and inference speed in a flexible manner. In this work, we propose MixCache, a training-free caching-based framework for efficient video DiT inference. MixCache first distinguishes the interference and boundary between different caching strategies, and then introduces a context-aware cache triggering strategy to determine when caching should be enabled, along with an adaptive hybrid cache decision strategy for dynamically selecting the optimal caching granularity. Extensive experiments on diverse models demonstrate that MixCache can significantly accelerate video generation (e.g., 1.94× speedup on Wan 14B, 1.97× speedup on HunyuanVideo) while delivering both superior generation quality and inference efficiency compared to baseline methods.

Trajectory similarity computation is critical to various spatial data-related applications. To date, many deep learning-based approaches have been proposed to approximate trajectory similarity. However, most of previous models focus on trajectories in Euclidean space, neglecting the information of road networks, which is an important prerequisite in many applications, such as traffic analytics, social recommendation. In this paper, we study the trajectory similarity learning over road networks. Different from previous task, trajectories over road networks contain richer and more complex information, e.g., the geographical and structure information of road networks. To this end, we propose SPGMT, a graph modeling based approach that leverages abundant structure and position information inherent in road networks for trajectory similarity learning. Particularly, our graph model learns informative node representations by simultaneously incorporating structure information of nodes from a local perspective and position information from a global perspective. This road network oriented module is the first proposal to learn from a broad context of graph topology. Afterwards, SPGMT designs a self-attention network and employs an LSTM to learn the sequential information from trajectories. We conduct experiments on real-life datasets to demonstrate the superiority of SPGMT in terms of effectiveness. Besides, additional study shows the flexibility and robustness of SPGMT.

The$k$-truss is a popular cohesive subgraph model for graph analysis, which requires each edge in the subgraph to be contained in at least$k-2$triangles, each consists three pairwisely connected edges. In this paper, we study the$k$-truss breaking problem (TBP) that aims to find the smallest set of edges whose removal makes the graph free of$k$-truss. The problem has been formulated in the literature with applications in community deception, critical connection identification, etc. However, existing solutions cannot scale to large graphs. We observe that chosen edges in a high-quality solution usually have high triangle support, while most share triangles with a significant number of easy-breaking edges (i.e., low-support edges). Motivated by these, we propose the Easy-Breaking Heuristic (EBH) that prioritizes the candidate edges based on their impact on easy-breaking edges. We also design several optimizations to further enhance the performance of EBH. Additionally, we extend our framework to efficiently handle the$k$-truss minimization problem (TMP), which aims to identify a set of at most$b$edges whose removal minimizes the size of the remaining k-truss. Extensive experiments demonstrate that our proposed algorithm outperforms state-of-the-art approaches by up to three orders of magnitude in efficiency when solving TBP, while maintaining comparable effectiveness. Additionally, our proposed algorithm achieves up to four orders of magnitude improvement in efficiency for TMP, along with generally better effectiveness.

Graphs have been widely used to represent the relationships of entities in real-world applications [1], [2]. k-truss model is a typical cohesive subgraph model and has received considerable attention due to its unique cohesive properties on degree and bounded diameter [3], [4].

The requirement for appropriate ways to measure the similarity between data objects is a common but vital task in various domains, such as data mining, machine learning and so on. Driven by abundant real-world applications, many well-known similarity (distance) metrics are proposed to measure the pairwise similarity of data pairs, e.g., graph edit distance for graphs and dynamic time warping for time series. However, many similarity metrics suffer from the high time complexity. More specifically, most of the well-known similarity metrics often need quadratic time or even much more time to compute the ground truth similarity and some of them are proven to be NP-hard. With the development of deep learning techniques, there is an emerging research trend on the learning for similarity computation on various data types in the field of database (DB) and data mining, which is quite different with the metric learning studies in the machine learning (ML) literature. Specifically, the studies in the ML focus on the learning for semantic similarity in specific tasks, which is implicitly indicated by the training data, on the data in the feature space. While the studies in the DB literature usually consider the learning for well-defined similarity metrics (e.g., graph edit distance) on the data objects (e.g., graphs), such that it can benefit the similarity computation on data in terms of multiple aspects, such as computation time, metric quality and search heuristic, and the learned representation of data can also be naturally fed to downstream tasks. This survey paper provides a comprehensive review of similarity computation learning on several data types, including set, sequence and graph. Moreover, we first classify the learning-based approaches in terms of their learning target into three categories, i.e., similarity learning, cost matrix learning and search heuristic learning. Then we detail some representative approaches for each category on every data type, and analyze some key features that are utilized by these approaches. Finally, we discuss some challenges and future directions towards the learning for similarity learning on these data types.

A path in a graph is a walk from one vertex to the other via edges. Many tasks for graph analytics may produce numerous paths, which record critical intermediate information or results. On the platform of Alibaba Cloud, a transaction (e.g., user purchase and money transfer) usually involves network communication via multiple servers. The server communication history is recorded as a path, where each vertex is an IP address. It is of significance to record such paths in Alibaba Cloud for daily maintenance tasks, such as anomaly server detection and network routing optimization. Motivated by the considerable data scale of IP paths, this paper proposes a compression method Overlap-Free Frequent Subpath (OFFS) to reduce the overall size. Meanwhile, the compressed paths should allow retrievals of any individual path, which is required by applications in our scenarios. We build a lookup table to match a series of frequent common subpaths to supernodes. Each path is shortened by replacing subpaths with corresponding supernodes in the table. We adopt a bottom-up framework to construct the lookup table in given iterations. Several optimizations are proposed to improve the compression ratio and speed. We conduct extensive experiments to show our effectiveness and efficiency based on several real datasets from Alibaba Cloud.

As a result of decades of studies, a broad spectrum of graph algorithms have been developed for graph analytics, including clustering, centrality, traversal, matching, mining, etc. However, the majority of recent graph processing frameworks only focus on a handful of fix-point graph algorithms such as breadth-first search, PageRank, shortest path, etc. It leaves the distributed computation of a large variety of graph algorithms suffering from low efficiency, limited expressiveness, or high implementation complexity with existing frameworks.In this paper, we propose Flash, a framework for programming distributed graph processing algorithms, which achieves good expressiveness, productivity and efficiency at the same time. Thanks to its high-level interface, Flash allows users to implement complex distributed graph algorithms with high performance with only a few lines of code. We have implemented 72 graph algorithms for 49 different problems in Flash. In further evaluations, we found that Flash beats other state-of-the-art graph processing frameworks with the speedups of up to 2 orders of magnitudes while takes up to 92% less lines of code.

$k$-truss model is a typical cohesive subgraph model and has been received considerable attention recently. However, the$k$-truss model only considers the direct common neighbors of an edge, which restricts its ability to reveal fine-grained structure information of the graph. Motivated by this, in this paper, we propose a new model named$(k, \tau)$-truss that considers the higher-order neighborhood ($\tau$hop) information of an edge. Based on the$(k, \tau)$-truss model, we study the higher-order truss decomposition problem which computes the$(k, \tau)$-trusses for all possible$k$values regarding a given$\tau$. Higher-order truss decomposition can be used in the applications such as community detection and search, hierarchical structure analysis, and graph visualization. To address this problem, we first propose a bottom-up decomposition paradigm in the increasing order of$k$values to compute the corresponding$(k, \tau)$-truss. Based on the bottom-up decomposition paradigm, we further devise three optimization strategies to reduce the unnecessary computation. We evaluate our proposed algorithms on real datasets and synthetic datasets, the experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms.

Abstract Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fundamental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the difficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objective of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simultaneously. In this paper, we divide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem, we can restrict the search in a very small part of the original bipartite graph. We prove that a logarithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. Furthermore, we study the diversified top-kbiclique search problem which aims to findkmaximal bicliques that cover the most edges in total. The basic idea is to repeatedly find the maximum biclique in the bipartite graph and remove it from the bipartite graphktimes. We design an efficient algorithm that considers to share the computation cost among thekresults, based on the idea of deriving the same subproblems of different results. We further propose two optimizations to accelerate the computation by pruning the search space with size constraint and refining the candidates in a lazy manner. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1.3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improvement on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.

GraphScope is a system and a set of language extensions that enable a new programming interface for large-scale distributed graph computing. It generalizes previous graph processing frameworks (e.g. , Pregel, GraphX) and distributed graph databases ( e.g ., Janus-Graph, Neptune) in two important ways: by exposing a unified programming interface to a wide variety of graph computations such as graph traversal, pattern matching, iterative algorithms and graph neural networks within a high-level programming language; and by supporting the seamless integration of a highly optimized graph engine in a general purpose data-parallel computing system. A GraphScope program is a sequential program composed of declarative data-parallel operators, and can be written using standard Python development tools. The system automatically handles the parallelization and distributed execution of programs on a cluster of machines. It outperforms current state-of-the-art systems by enabling a separate optimization (or family of optimizations) for each graph operation in one carefully designed coherent framework. We describe the design and implementation of GraphScope and evaluate system performance using several real-world applications.

Cardinality estimation (CardEst) plays a significant role in generating high-quality query plans for a query optimizer in DBMS. In the last decade, an increasing number of advanced CardEst methods (especially ML-based) have been proposed with outstanding estimation accuracy and inference latency. However, there exists no study that systematically evaluates the quality of these methods and answer the fundamental problem: to what extent can these methods improve the performance of query optimizer in real-world settings, which is the ultimate goal of a CardEst method. In this paper, we comprehensively and systematically compare the effectiveness of CardEst methods in a real DBMS. We establish a new benchmark for CardEst, which contains a new complex real-world dataset STATS and a diverse query workload STATS-CEB. We integrate multiple most representative CardEst methods into an open-source DBMS PostgreSQL, and comprehensively evaluate their true effectiveness in improving query plan quality, and other important aspects affecting their applicability. We obtain a number of key findings under different data and query settings. Furthermore, we find that the widely used estimation accuracy metric (Q-Error) cannot distinguish the importance of different sub-plan queries during query optimization and thus cannot truly reflect the generated query plan quality. Therefore, we propose a new metric P-Error to evaluate the performance of CardEst methods, which overcomes the limitation of Q-Error and is able to reflect the overall end-to-end performance of CardEst methods. It could serve as a better optimization objective for future CardEst methods.

Due to diverse graph data and algorithms, programming and orchestration of complex computation pipelines have become the major challenges to making use of graph applications for Web-scale data analysis. GraphScope aims to provide a one-stop and efficient solution for a wide range of graph computations at scale. It extends previous systems by offering a unified and high-level programming interface and allowing the seamless integration of specialized graph engines in a general data-parallel computing environment. As we will show in this demo, GraphScope enables developers to write sequential graph programs in Python and provides automatic parallel execution on a cluster. This further allows GraphScope to seamlessly integrate with existing data processing systems in PyData ecosystem. To validate GraphScope's efficiency, we will compare a complex, multi-staged processing pipeline for a real-life fraud detection task with a manually assembled implementation comprising multiple systems. GraphScope achieves a 2.86× speedup on a trillion-scale graph in real production at Alibaba.

Query optimizers rely on accurate cardinality estimation (CardEst) to produce good execution plans. The core problem of CardEst is how to model the rich joint distribution of attributes in an accurate and compact manner. Despite decades of research, existing methods either over-simplify the models only using independent factorization which leads to inaccurate estimates, or over-complicate them by lossless conditional factorization without any independent assumption which results in slow probability computation. In this paper, we propose FLAT, a CardEst method that is simultaneously fast in probability computation, lightweight in model size and accurate in estimation quality. The key idea of FLAT is a novel unsupervised graphical model, called FSPN. It utilizes both independent and conditional factorization to adaptively model different levels of attributes correlations, and thus combines their advantages. FLAT supports efficient online probability computation in near linear time on the underlying FSPN model, provides effective offline model construction and enables incremental model updates. It can estimate cardinality for both single table queries and multi-table join queries. Extensive experimental study demonstrates the superiority of FLAT over existing CardEst methods: FLAT achieves 1--5 orders of magnitude better accuracy, 1--3 orders of magnitude faster probability computation speed and 1--2 orders of magnitude lower storage cost. We also integrate FLAT into Postgres to perform an end-to-end test. It improves the query execution time by 12.9% on the well-known IMDB benchmark workload, which is very close to the optimal result 14.2% using the true cardinality.

Maximum biclique search, which finds the biclique with the maximum number of edges in a bipartite graph, is a fundamental problem with a wide spectrum of applications in different domains, such as E-Commerce, social analysis, web services, and bioinformatics. Unfortunately, due to the difficulty of the problem in graph theory, no practical solution has been proposed to solve the issue in large-scale real-world datasets. Existing techniques for maximum clique search on a general graph cannot be applied because the search objective of maximum biclique search is two-dimensional, i.e., we have to consider the size of both parts of the biclique simultaneously. In this paper, we divide the problem into several subproblems each of which is specified using two parameters. These subproblems are derived in a progressive manner, and in each subproblem we can restrict the search in a very small part of the original bipartite graph. We prove that a logarithmic number of subproblems is enough to guarantee the algorithm correctness. To minimize the computational cost, we show how to reduce significantly the bipartite graph size for each subproblem while preserving the maximum biclique satisfying certain constraints by exploring the properties of one-hop and two-hop neighbors for each vertex. We use several real datasets from various application domains, one of which contains over 300 million vertices and 1.3 billion edges, to demonstrate the high efficiency and scalability of our proposed solution. It is reported that 50% improvement on recall can be achieved after applying our method in Alibaba Group to identify the fraudulent transactions in their e-commerce networks. This further demonstrates the usefulness of our techniques in practice.

Recently there emerge many distributed algorithms that aim at solving subgraph matching at scale. Existing algorithm-level comparisons failed to provide a systematic view of distributed subgraph matching mainly due to the intertwining of strategy and optimization. In this paper, we identify four strategies and three general-purpose optimizations from representative state-of-the-art algorithms. We implement the four strategies with the optimizations based on the common Timely dataflow system for systematic strategy-level comparison. Our implementation covers all representative algorithms. We conduct extensive experiments for both unlabelled matching and labelled matching to analyze the performance of distributed subgraph matching under various settings, which is finally summarized as a practical guide.

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.