Graph propagation algorithms such as PageRank and its variants are widely used in modern applications such as ranking webpages, spam detection, and recommender systems. To cope with the web-scale graphs in these applications, many distributed vertex-centric systems, a.k.a. Pregel-like systems, have been proposed that can be used to parallelize the iterative graph propagation algorithms. In this work, we propose a message compression framework for Pregel-like systems, called CompreGel, which accelerates graph propagation algorithms by significantly reducing the communication cost of message passing. In a Pregel-like system, messages are streams of key-value pairs, where keys (resp. values) are the IDs of the target vertices (resp. vertex values such as PageRank values for dispersion). Our framework compresses the keys and values separately to maximize the compression power. Specifically, CompreGel employs the lossless bitmap compression for keys by utilizing an ID renumbering technique, and it employs the popular error-bounded lossy compressor SZ for values. Moreover, we theoretically analyze how to set the error bound parameter of SZ properly to bound the accumulative error of vertex values across iterations of graph propagation. Extensive experiments show that CompreGel can improve job efficiency by up to 10 × with a 200 × message compression ratio, while achieving comparable accuracy to a Pregel-like system without message compression.

Given a graph pair (G 1 , G 2 ), graph edit distance (GED) is defined as the minimum number of edit operations converting G 1 to G 2 . GED is a fundamental operation widely used in many applications, but its exact computation is NP-hard, so the approximation of GED has gained a lot of attention. Data-driven learning-based methods have been found to provide superior results compared to classical approximate algorithms, but they directly fit the coupling relationship between a pair of vertices from their vertex features. We argue that while pairwise vertex features can capture the coupling cost (discrepancy) of a pair of vertices, the vertex coupling matrix should be derived from the vertex-pair cost matrix through a more well-established method that is aware of the global context of the graph pair, such as optimal transport. In this paper, we propose an ensemble approach that integrates a supervised learning-based method and an unsupervised method, both based on optimal transport. Our learning method, GEDIOT, is based on inverse optimal transport that leverages a learnable Sinkhorn algorithm to generate the coupling matrix. Our unsupervised method, GEDGW, models GED computation as a linear combination of optimal transport and its variant, Gromov-Wasserstein discrepancy, for node and edge operations, respectively, which can be solved efficiently without needing the ground truth. Our ensemble method, GEDHOT, combines GEDIOT and GEDGW to further boost the performance. Extensive experiments demonstrate that our methods significantly outperform the existing methods in terms of the performance of GED computation, edit path generation, and model generalizability.