Secure multi-party computation techniques enable in-depth analysis on joint graphs that inherently encompass comprehensive topology information and extended attributes, while preserving data privacy. In the two-party setting, existing approaches suffer from inefficiencies due to redundant secure sorting or costly secure shuffling operations required for secure message passing. Some works improve efficiency by relaxing security assumptions, either through differential privacy or by introducing helper parties.

Encrypted matrix-vector multiplication is a fundamental component of a variety of applications that involve data privacy concerns. Current algorithms utilizing fully homomorphic encryption (FHE) generally use batching to enhance computational efficiency while neglecting the sparsity of the matrices, a characteristic that exists naturally in many practical situations. Alternatively, porting plaintext algorithms that skip zero elements to address sparsity may fail to utilize batching and introduce additional privacy concerns.

Pair-then-Aggregate (PtA) introduces a programming paradigm and an automated parallel execution engine for large-scale secure multi-party (MPC) computations, drawing inspiration from the widely-used yet not explicitly defined Table-Generation-and-Look-up (TGL) pattern in privacy-preserving algorithm design. PtA offers an easy-to-use API and a versatile execution engine that harnesses various levels of parallelism and adapts to different MPC deployments, algorithms, and input sizes. Evaluations on a real-world MPC platform demonstrate significant enhancements in scalability, adaptability, and ease of programming. PtA can process one billion input elements with 3-23 lines of C++ code in 5-74 seconds. It outperforms state-of-the-art implementations in 91.4 % of 35 test cases, achieving up to a$12.4 \times$speedup with much less coding effort.11Our code is provided in https://github.com/Fannxy/Pair-then-Aggregate

Graph Neural Networks (GNNs) are widely used in various applications and consist of two main operations: Propagation and Transformation. By permuting and combining these two operations, we can obtain different GNN architectures for different downstream tasks. Despite the effectiveness and popularity of GNNs, their training is time-consuming and memory-intensive, which limits their practical usage. Various methods have been proposed to tackle this issue, such as sampling and distributed training. In this work, we carefully revisit the two basic operations of GNNs and observe two types of redundancy in these operations: 1) propagation data redundancy, and 2) transformation computation redundancy. To address these problems, we propose CompressGNN, a framework that leverages hierarchical compression to accelerate GNNs by reducing data and computational redundancy. The framework comprises a propagation compression module and a transformation compression module. In the propagation compression module, we compress the graph structure to eliminate data redundancy. In the transformation compression module, we achieve computation compression by compressing similar node features at runtime. Extensive experiments demonstrate that our method achieves an average speedup of 2.32× across multiple datasets and models.

Ego-centric queries, focusing on a target vertex and its direct neighbors, are essential for various applications. Enabling such queries on graphs owned by mutually distrustful data providers without breaching privacy holds promise for more comprehensive results. In this paper, we propose GORAM, a graph-oriented data structure that enables efficient ego-centric queries on federated graphs with strong privacy guarantees. GORAM leverages secure multiparty computation (MPC) and ensures that no information about the graphs or the querying keys is exposed during the process. For practical performance, GORAM partitions the federated graph and constructs an Oblivious RAM (ORAM )-inspired index atop these partitions. This design enables each ego-centric query to process only a single partition, which can be accessed fast and securely. Utilizing GORAM, we develop a prototype querying engine on a real-world MPC framework. We then conduct a comprehensive evaluation using five commonly used queries similar to the LinkBench workload description [11] on both synthetic and real-world graphs. Our evaluation shows that all five queries can be completed in just 58.1 milliseconds to 35.7 seconds, even on graphs with up to 41.6 million vertices and 1.4 billion edges. To the best of our knowledge, this represents the first instance of processing billion-scale graphs with practical performance on MPC.

Graph databases play a pivotal role in the FinTech industry. However, existing graph benchmarks fail to capture the unique characteristics of financial datasets and workloads, rendering them inadequate for evaluating graph databases in financial scenarios. This paper presents the LDBC Financial Benchmark (FinBench) Transaction Workload, a novel benchmark that adopts a choke point-driven design methodology, emphasizing performance bottlenecks, and incorporates distinct features such as dataset skewness, edge multiplicity, temporal window filtering, recursive path filtering, read-write query patterns, and truncation on hub vertices. Key contributions include a scalable data generator that synthesizes datasets with financial-specific features, a parameter generator that leverages bucketed data statistics for runtime consistency across queries, and a scalable benchmark driver that biases query execution by time windows. Experimental evaluations on graph databases demonstrate the benchmark's capability to reveal novel choke points and provide insights into system performance in financial scenarios.

Vertical Federated Learning (VFL) is a solution increasingly used by companies with the same user group but differing features, enabling them to collaboratively train a machine learning model. VFL ensures that clients exchange intermediate results extracted by their local models, without sharing raw data. However, in practice, VFL encounters several challenges, such as computational and communication overhead, privacy leakage risk, and adversarial attack. Our study reveals that the usage of floating-point (FP) numbers is a common factor causing these issues, as they can be redundant and contain too much information. To address this, we propose a new architecture called rounding layer, which converts intermediate results to integers. Our theoretical analysis and empirical results demonstrate the benefits of the rounding layer in reducing computation and memory overhead, providing privacy protection, preserving model performance, and mitigating adversarial attacks. We hope this paper inspires further research into novel architectures to address practical issues in VFL.

Evolving graphs consisting of slices are large and constantly changing. For example, in Alipay, the graph generates hundreds of millions of new transaction records every day. Analyzing the graph within a temporary window is time-consuming due to the heavy merging of slices. Fortunately, we have discovered that most queries exhibit consistent patterns and possess monotonic properties. As a result, transitional results can be computed within slice generation for reuse. Accordingly, we develop MergeGraph enabling window-based monotonic graph analytics with reusable transitional results for pattern-consistent queries. MergeGraph has three advantages over previous works. First, it is the first system specifically tailored for window-based monotonic graph analytics with pattern-consistent queries. Second, it effectively utilizes transitional results from different slices concurrently. Third, MergeGraph boasts a high degree of expressiveness, supporting a broad spectrum of monotonic graph queries. Experimental results demonstrate that MergeGraph delivers significant performance benefits. In evaluating four typical graph applications, MergeGraph achieves an average speedup of 11.30× compared to state-of-the-art methods.

GeaFlow is a distributed dataflow system optimized for streaming graph processing, and has been widely adopted at Ant Group, serving various scenarios ranging from risk control of financial activities to analytics on social networks and knowledge graphs. It is built on top of a base with full-fledged stateful stream processing capabilities, extended with a series of graph-aware optimizations to address the space explosion and programming complexity issues of conventional join-based approaches. We propose new state backends and streaming operators that facilitate processing on dynamic graph-structured datasets, reducing space consumed by states. We develop a hybrid domain-specific language that embeds Gremlin into SQL, supporting both table and graph abstractions over streaming data. In addition to streaming workloads, GeaFlow is also extensively used for some batch processing jobs. In the largest deployments to date, GeaFlow is able to process tens of millions of events per second and manage hundreds of terabytes of states.

Out-of-core systems rely on high-performance cache sub-systems to reduce the number of I/O operations. Although the page cache in modern operating systems enables transparent access to memory and storage devices, it suffers from efficiency and scalability issues on cache misses, forcing out-of-core systems to design and implement their own cache components, which is a non-trivial task. This study proposes TriCache, a cache mechanism that enables in-memory programs to efficiently process out-of-core datasets without requiring any code rewrite. It provides a virtual memory interface on top of the conventional block interface to simultaneously achieve user transparency and sufficient out-of-core performance. A multi-level block cache design is proposed to address the challenge of per-access address translations required by a memory interface. It can exploit spatial and temporal localities in memory or storage accesses to render storage-to-memory address translation and page-level concurrency control adequately efficient for the virtual memory interface. Our evaluation shows that in-memory systems operating on top of TriCache can outperform Linux OS page cache by more than one order of magnitude, and can deliver performance comparable to or even better than that of corresponding counterparts designed specifically for out-of-core scenarios.

With the magnitude of graph-structured data continually increasing, graph processing systems that can scale-out and scale-up are needed to handle extreme-scale datasets. While existing distributed out-of-core solutions have made it possible, they suffer from limited performance due to excessive I/O and communication costs.

Evolving graphs in the real world are large-scale and constantly changing, as hundreds of thousands of updates may come every second. Monotonic algorithms such as Reachability and Shortest Path are widely used in real-time analytics to gain both static and temporal insights and can be accelerated by incremental computing. Existing streaming systems adopt the incremental computing model and achieve either low latency or high throughput, but not both. However, both high throughput and low latency are required in real scenarios such as financial fraud detection. This paper presents RisGraph, a real-time streaming system that provides low-latency analysis for each update with high throughput. RisGraph addresses the challenge with localized data access and inter-update parallelism. We propose a data structure named Indexed Adjacency Lists and use sparse arrays and Hybrid Parallel Mode to enable localized data access. To achieve inter-update parallelism, we propose a domain-specific concurrency control mechanism based on the classification of safe and unsafe updates. Experiments show that RisGraph can ingest millions of updates per second for graphs with several hundred million vertices and billions of edges, and the P999 processing time latency is within 20 milliseconds. RisGraph achieves orders-of-magnitude improvement on throughput when analyses are executed for each update without batching and performs better than existing systems with batches of up to 20 million updates.

Apache Spark is a widely deployed big data analytics framework that offers such attractive features as resiliency, load-balancing, and a rich ecosystem. However, there is still plenty of room for improvement in its performance. Although a data-parallel system in a native programming language significantly improves performance, it may require re-implementing many functionalities of Spark to become a full-featured system. It is desirable for native big data systems to just write a compute engine in native languages to ensure high efficiency, and reuse other mature features provided by Spark rather than re-implement everything. But the interaction between the JVM and the native world risks becoming a bottleneck. This paper proposes Chukonu, a native big data framework that re-uses critical big data features provided by Spark. Owing to our novel DAG-splitting approach, the potential Spark integration overhead is alleviated, and its even outperforms existing pure native big data frameworks. Chukonu splits DAG programs into run-time parts and compile-time parts: The run-time parts are delegated to Spark to offload the complexities due to feature implementations. The compile-time parts are natively compiled. We propose a series of optimization techniques to be applied to the compile-time parts, such as operator fusion, vectorization, and compaction, to significantly reduce the Spark integration overhead. The results of evaluation show that Chukonu has a speedup of up to 71.58X (geometric mean 6.09X) over Apache Spark, and up to 7.20X (geometric mean 2.30X) over pure-native frameworks on six commonly-used big data applications. By translating the physical plan produced by SparkSQL into Chukonu programs, Chukonu accelerates Spark-SQL's TPC-DS performance by 2.29X.

The specific characteristics of graph workloads make it hard to design a one-size-fits-all graph storage system. Systems that support transactional updates use data structures with poor data locality, which limits the efficiency of analytical workloads or even simple edge scans. Other systems run graph analytics workloads efficiently, but cannot properly support transactions. This paper presents LiveGraph, a graph storage system that outperforms both the best graph transactional systems and the best solutions for real-time graph analytics on fresh data. LiveGraph achieves this by ensuring that adjacency list scans, a key operation in graph workloads, are purely sequential: they never require random accesses even in presence of concurrent transactions. Such pure-sequential operations are enabled by combining a novel graph-aware data structure, the Transactional Edge Log (TEL), with a concurrency control mechanism that leverages TEL's data layout. Our evaluation shows that LiveGraph significantly outperforms state-of-the-art (graph) database solutions on both transactional and real-time analytical workloads.

Weibo is the Twitter counterpart in China that has attracted hundreds of millions of users. We crawled an almost complete Weibo user network that contains 222 million users and 27 billion links in 2013. This paper analyzes the structural properties of this network, and compares it with a Twitter user network. The topological properties we studied include the degree distributions, reciprocity, clustering coefficient, PageRank centrality, and degree assortativity. We find that Weibo users have a higher diversity index, higher Gini index, but a lower reciprocity and clustering coefficient for most of the nodes. A surprising observation is that the reciprocity of Weibo is only about a quarter of the reciprocity of the Twitter user network. We also show that Weibo adoption rate correlates with economic development positively, and Weibo network can be used to quantify the connections between provinces and regions in China. In particular, point-wise mutual information is shown to be accurate in quantifying the strength of connections.