1 Introduction↩︎

Ubiquity of large graphs in today’s world prompts a quest to compress such data; that is, for a given graph \(G=(V,E)\) where \(E \subseteq V^2\), construct a minimal bit sequence \(s\) that encodes \(E\) losslessly. Beyond minimizing the lenght of sequence \(s\), practical requirements include fast compression and decompression and efficient query support (e.g., what are all the successors of \(v \in V\)) with a low working memory footprint [1]. Designing such representations is central to graph algorithms and succinct data structures.

The dominant practical approach to lossless graph compression is WebGraph [2], [3] that relies on the observation that successors of \(v\) are often similar to each other, so they are likely to have similar indices (in some natural enumeration of \(V\)). Instead of writing every successor of \(v\) as a full index, we only encode gaps between them using a variable-length encoding. However, WebGraph’s effectiveness depends on the ordering of \(V\). Consequently, it is typically preceded by computationally expensive reordering algorithms, such as Layered Label Propagation (LLP) [4] or recursive graph bisection (BP) [5].

WebGraph exploits locality from vertex ordering, but does not take into account the latent geometric structure that has proved useful for describing many real-world networks. According to geometric network-generation models, two nodes \(v\) and \(w\) are likely to be connected if they are in a close neighborhood in a given metric space. However, the knowledge of the locations of the nodes in the given (often latent) metric space is needed. A geometric embedding of a graph \(G\) to a metric space \(\mathbb{X}\) is a mapping \(m: V \rightarrow\mathbb{X}\). This way we can operationalize the probability of the connection between two nodes \(v\) and \(w\) as a function of the distance between \(m(v)\) and \(m(w)\). The embedding needs to be good, typically, we are interested in embeddings maximizing likelihood, which measures how good the embedding is at predicting edges between nodes. An embedder is an algorithm which finds a good embedding \(m: V \rightarrow\mathbb{X}\).

Hyperbolic geometry was found to be a promising choice in visualization and modeling of real-world graphs characterized by similar properties, such as power-law scaling behavior [6]. In Random Hyperbolic Graph model (RHG) [7], the metric space \(\mathbb{X}\) is a disk of radius \(R\) in the hyperbolic plane \(\mathbb{H}^2\). Every node gets two polar coordinates, \(r\) (radial) and \(\phi\) (angular). The angular coordinate \(\phi\) corresponds to similarity (nodes with close \(\phi\) are considered similar) and the radial coordinate \(r\) proxies popularity (nodes with small \(r\) are considered popular and thus connect to more other nodes, even if they are less similar). For more than a decade, hyperbolic embedders (finding good embeddings \(m: V \rightarrow\mathbb{H}^2\)) have been a vivid research area not only in network theory but algorithmic and machine learning communities as well [8].

In this paper, we propose a new approach to lossless compression of graphs, based on hyperbolic embeddings. Our contributions are as follows:

• First practical lossless graph compression algorithm based on hyperbolic embeddings, running in time \(O(n B_bB_d+m\log n)\), where \(B_b\) and \(B_d\) are compression parameters. We use entropy coding to encode connection in roughly as many bits as the negative binary logarithm of the likelihood. This, together with a succinct description of the mapping \(m\) itself, yields a graph compression method.

• Embedding-based vertex ordering can be used as a graph reordering method. CLOVE is especially promising due to its speed and the \(\phi\) sequence naturally ordering vertices. Our experiments show that this reordering improves WebGraph’s performance as well.

• Experimental verification using fast embedders: BFKL [9], LPCS [10], HMCS [11], and CLOVE [12]. Our method outperforms WebGraph-based appoaches by up to 42% on real-world graphs. The choice of the embedder significantly impacts compression quality.

2 Prerequisites↩︎

In this paper, we work with embeddings of graphs into the hyperbolic plane \(\mathbb{H}^2\). For more information on this geometry, see, e.g., the book [13]; we also recommend game HyperRogue [14] to gain intuitions.

Let \(G = (V, E)\), where \(E \subseteq V^2\), be a graph. We denote \(n=|V|\), \(m=|E|\). Each \(v \in V\) is mapped to a point \(m(v) \in \mathbb{H}^2\) with polar coordinates \(r(v)\) and \(\phi(v)\). Figure 1 illustrates an example embedded graph. The hyperbolic distance between two points \((r_1,\phi_1)\) and \((r_2,\phi_2)\), where \(\phi_1-\phi_2=\phi\) is given by the following formula:

\[\begin{align} d &=& {\rm acosh}\;(\sinh(r_1)\sinh(r_2)\cos\phi + \cosh(r_1)\cosh(r_2)) \\ &=& {\rm acosh}\;(\cosh(r_1-r_2) + (1-\cos(\phi))\sinh(r_1)\sinh(r_2)) \label{precisedist} \end{align}\tag{1}\]

According to the RHG model [7], the expected probability of two nodes \((v,w)\) being connected is \(p(v,w)=p(\delta(v,w)) = (1 + \exp((\delta(v, w)-R))/2T))^{-1}\), where \(R\) is the radius of the disk, and \(T\) (called temperature) is a parameter of the model controlling how well the latent geometry reflects connections. We measure the quality of a hyperbolic embedding with likelihood \(L\), which is the product of \(p(v,w)\) for all pairs of nodes \((v,w) \in E\), and \(1-p(v,w)\) for all pairs of nodes \((v,w) \notin E\). While the parameters \(R\) and \(T\) have specific meanings in the RHG model, for compression purposes, we simply pick the values of \(R\) and \(T\) which yield the maximum likelihood.

2.1 Entropy coding↩︎

We can use a compression method similar to arithmetic encoding [15] to create a compression method based on a good quality hyperbolic embedding \(m\). We start with the interval \([a,b] = [0,1]\). To compress an information about an event \(A\) that happens with probability \(p\), we compute \(m = a + (b-a)p\), and then replace the interval with \([a,b]\) with \([a,m]\) if \(A\) happened, or with \([m,b]\) if not. We repeat this procedure for every event we are interested in; to compress the edge information in a hyperbolic embedding, we simply repeat it for every pair \((u,v)\). The compressed string of bits is the binary representation of some simplest number in the final interval \([a,b]\). It is easy to see that the length of the final interval equals \(L\), and therefore, the length of the compressed string is \(O(1)-\log_2 L\). Thus, we can obtain a short representation of the connection structure.

We also need to represent the embedding itself. How to do so best may depend on the embedding; in general, distances in hyperbolic geometry are extremely sensitive to small differences in coordinates [16]–[18], so we may require a large number of bits to represent their coordinates.

2.2 Quick access to successor lists↩︎

While the entropy coding method described above gives a compression as good as the information-theoretic limit, we also need to care about practical issues. We want the compression and decompression to be quick (e.g., linear in the length of the output). In graph compression, we also usually not only want to be able to recover the information about the whole graph, but also to get a list of successors of a given node \(v\). Perfect arithmetic coding is impractical due to using arbitrary precision real numbers, on which computations are slow.

These issues can be solved by using an implementation in which we represent only next \(Q\) bits which are not yet decided (and thus not yet sent to the output stream), i.e., these bits differ in the numbers \(a\) and \(b\). We can use a small value of \(Q\) (e.g., \(Q=20\)) and obtain very fast compression close to perfect. Now, for every node \(u\), we encode every potential edge \(u \rightarrow v\) in sequence. Before we do so, we record the current offset in the compressed stream, as well as the current bits of \(a\) and \(b\). This information lets us answer the successor list queries by moving to the recorded position in the compressed stream and interval, and reading the edges for all \(u\). We can also use separate runs of entropy coding to encode every \(u\) – this yields shorter offset lists and a possibility of parallel computation, at the cost of \(n\) extra bits.

2.3 Undirected, directed, and bipartite graphs↩︎

In research on graph compression graphs are assumed to be directed, contrary to most works on hyperbolic embeddings, on undirected graphs. Ongoing research aims to fill this gap. In [19], for bipartite graphs, assume \(V = V_1 \cup V_2\), and all edges go from \(V_1\) to \(V_2\). Since we only consider pair of nodes \((v,w)\) in which \(v \in V_1\) and \(w \in V_2\) as possible edges, we take only them into account in the formula for likelihood. In [20] directed graphs are embedded by splitting every node that has both in-edges and out-edges into two (in-node and out-node).

However, for compression purposes we need fast embedders, and those known to us assume undirected graphs. In our method we run a fast hyperbolic embedder on the undirected graph \((V,E')\) such that \(\{u,v\}\in E'\) if and only if \((u,v) \in E\) or \((v,u) \in E\). To correctly take directed or bipartite graphs into account, we then introduce changes based on the ideas from [19], [20].

Many graphs we benchmark our algorithm on are in fact undirected (\((u,v) \in E\) iff \((v,u) \in E\)), or have high reciprocity. Theoretically we could use this information to greatly reduce the length of the compressed string. We do not do so, because this is not usually done in WebGraph-based graph compression algorithms, and also doing so prevents answering successor list queries efficiently.

3 Fast compression algorithm↩︎

The method described so far is slow. We need to separately encode each of \(n^2\) edges, and thus, the compression algorithm runs in time \(O(n^2)\) and can obtain the list of successors of \(v \in V\) in time \(O(n)\). In this section, we describe a more efficient method, called HyperFast¹. Instead of computing the exact distances for every pair of nodes, we approximate without significantly worsening the likelihood.

We assume that the nodes are already ordered by the angular coordinate \(\phi\). To simplify the compression, we assume that \(i\)-th node has \(\phi_i = 2\pi i/n\) – this is true in a CLOVE embedding [12] and hopefully will not worsen the likelihood too much otherwise.

The method is based on approximations. We split the set of radial distances \(A_r = \{r_v: v \in V\}\) into \(B_r\) intervals, that we will call radial buckets. In our basic implementation, we split the interval between the \(\min(A_r)\) and \(\max(A_r)\) into \(B_r\) equal intervals; let \(\mathbb{B}_r\) be the set of all radial buckets. For every \(v \in V\), let \(b_v\) be the radial bucket that \(r_v\) belongs to. For every bucket \(b \in \mathbb{B}_r\), let \(S_b\) be the set of nodes that fall into radial bucket \(b\) (geometrically, an annulus), and \(\hbar{r_b}\) be the average of all \(r_v\) for all \(v \in S_b\). We replace every \(r_v\) with \(\hbar{r_{b_v}}\), thus compressing the annulus \(S_b\) into a circle (Figure 2); thus, we lose some precision of radial distances, but hopefully that should not matter much for the quality of edge prediction. We send the following data to the compressed stream: the \(\hbar{r_b}\) for every radial bucket \(b\), and \(b_v\) for every node \(v \in V\). We use arithmetic encoding for sending \(b_v\), since the distribution of nodes into radial buckets is not uniform (in typical hyperbolic embeddings significantly more nodes fall into buckets with greater indices). This way, we have compressed all the information about radial distances into \(B_r\) floating-point numbers and \(O(n \log(B_r))\) bits. In Figure 2, the radial buckets are \([1,2)\), \([2,3)\) and \([3,4)\).

Now, let \(A_d = \{d(u,v): (u,v) \in E\}\) be the set of distances between vertices connected with edges. We split the set of possible distances into \(B_d\) intervals, that we will call distance buckets. In our basic implementation, we again split the interval between \(\min(A_d)\) and \(\max(A_d)\) into \(B_d-1\) equal buckets, and another bucket for distances above \(\max(A_d)\) (that can be achieved for nodes not connected with edges). Distances below \(\min(A_d)\) can be considered a part of the first instance bucket. Let \(\mathbb{B}_d\) be the set of all distance buckets. The idea of this bucketing is that we will no longer care about the exact distance \(d(u,v)\), but what bucket \(c \in \mathbb{B}_d\) it belongs to. The compressor sends the information about the buckets obtained (\(B_d\) threshold distances, which are floating point numbers). In Figure 2, distance buckets are \([0,1)\), \([1, 2)\), \([2,3)\), \([3, 4)\) and \([4, \infty)\). Red circles show which nodes fall into which distance bucket with respect to the red node.

For every \(u \in V\), every radial bucket \(b \in \mathbb{B}\), and every distance bucket \(c\), the set of nodes \(v\) which are in bucket \(b\) and such that \(d(u,v) \in c\) has a very simple structure. It is an intersection of the circle \(S_b\) and the annulus \(X_{u,c}\) of all points \(v\) whose distance from \(u\) is in the distance bucket \(c\) (Figure 2). Since \(V\) was ordered by the angular coordinate, so is the circle \(S_b\), and thus we can find the two arcs of \(S_b\) which intersect the annulus \(X_{u,c}\) using binary search. It is also possible to remove the logarithmic factor by using the two-pointer caterpillar method. To do so, we need to compute \(S_b \cap X_{u,c}\) for all the source vertices \(u\) in the given radial bucket in their angular order.

By performing the construction above for every \(u \in E\), radial bucket \(b \in \mathbb{B}_r\) and distance bucket \(c \in \mathbb{B}_d\), we can compute \(m'_c\), the number of pairs \((u,v) \in V \times V\) such that \(d(u,v) \in c\). This computation can be done using only the information we have sent/received so far, in time \(O(nB_bB_d \log n)\), or \(O(nB_bB_d)\) using the two-pointer caterpillar method.

Knowing the graph, we can also, for every distance bucket \(c \in \mathbb{B}_d\), compute \(m_c\), the number of actual edges \((u,v) \in E\) such that \(d(u,v) \in c\). We send this information to the compressed stream. Since \(0 \leq m_c \leq m'_c \leq n^2\), this requires \(O(B_d \log n)\) bits.

Now, for every distance bucket \(c\), we need to send the information about specifically which of these \(m'_c\) elements correspond to edges. Denote \(p_c = \frac{m_c}{m'_c}\). For simplicity, we perform the compression here assuming that, for each \(c\) and for each of \(m'_c\) edge pairs, they are connected with an edge independently with probability \(p_c\). We can thus encode the information about the connections using \(\sum_{c \in \mathbb{B}_d} m_c H(p_c)\) bits, where \(H(p)\) is the entropy \(-p \log(p) +-(1-p) \log(1-p)\). If the radial and distance buckets are small enough, this value should be close to \(-\log L\) (in fact, it could be smaller, since the actual probability \(p(d)\) need not actually be a logistic function of \(d\)).

We again do this separately for every \(u \in V\), radial bucket \(b \in \mathbb{B}\), and distance bucket \(c\). Recall that \(S_b \cap X_{u,c}\) is a union of two arcs; we also handle these two arcs separately. Let \(S_b \cap X_{u,c} = \{v_1, \ldots, v_j\}\), and let \(I\) be the set of indices which correspond to \(v \in S_b\) such that \((u,v) \in E\). Observe that when \(p\) is very small (as it is for all buckets which contain mostly non-edges), there are very long gaps between the elements of \(I\). We send the information about the following random event: is I empty? Since we know the probability of this event according to our independence model, \((1-p)^j\), we can use the entropy coding method detailed in Subsection 2.1 to encode this information nearly optimally. In case if the event happened (the intersection was empty), there is nothing to do anymore. Otherwise, we use binary search to pinpoint the specific index \(\min(I)\). The invariant of binary search is \(\min(I) \in \{l, \ldots, r\}\), initially \(l=1\) and \(r=j\); we pick \(s = (l+r)/2\), and consider the event \(\min(I) \leq s\). We can compute the probability of this event using our independence assumption, and thus, we can use the entropy conding method to encode this information. Depending on whether the event holds or not, we obtain smaller and smaller intervals, until we pinpoint \(\min(I)\). Taking \(K=n\), the compression/decompression algorithm, for a given u, needs \(O(\deg u \log(n) + B_d B_r)\) queries to entropy coding, and has the same time complexity. Here, \(\deg u\) is the outdegree of \(u\).

3.0.0.1 Adjustments.

The basic HyperFast algorithm outlined above can be modified, e.g., by optimizing radial and distance buckets, using directed degree-based radial distances, triangle-based edge prediction, and local search. These approaches are described in detail in Section 7.

4 Experimental setup↩︎

To evaluate our idea for practical uses, we analyze the results of the compression methods on real-world and simulated graphs. For each graph \(G=(V,E)\) we compute the bits per link for:

• the trivial representation of \(G\): each one of \(n(n-1)\) potential edges is independently encoded using arithmetic encoding, under assumption that the probability of an edge occuring is \(\frac{m}{n(n-1)}\). This is a natural choice for the baseline.

• the WebGraph representation of \(G\), ordering by the nodes’ order of appearance in the input file (“input order”);

• the WebGraph representation of \(G\), ordering by the recursive graph bisection method (BP) [5]. We use two variants of selecting the original bisection: random (BP) or based on the input order (BPN);

• the WebGraph representation of \(G\), ordering by the layered label propagation (LLP) [4];

• the WebGraph representation of \(G\), ordering by the \(\phi\) order from a given hyperbolic embedder;

• the HyperFast representation of \(G\), based on a hyperbolic embedder, for two sets of hyperparameters: \(B_d=B_r=8\) and \(B_d=B_r=16\);

We use the following hyperbolic embedders: CLOVE [12], BFKL [9], HMCS [11], and LPCS [10].

The complete list of real-world graphs we use can be found in Section 8. Our set of real-world graphs contains popular benchmarks used in the studies on both hyperbolic embedders and the state-of-the-art graph compression methods. To generalize our findings, we also work with the simulated graphs from the following generative graph models. In each case, we generate graphs of approximate size \(n=10000\) and \(n=50000\), and an approximate average degree of 10.

• er: Erdös-Renyi model [21]. Every pair of vertices is connected with the same probability.

• ab: Albert-Barabasi model [22]. Graphs with power law degree distribution (\(\gamma=3\)).

• cl: Chung-Lu model [23], [24]. Graphs with the given expected degree distribution. We use the power law degree distribution (\(\gamma=2.5\)).

• gs: a simple geometric model. Nodes are randomly set on a sphere and connected if the distance is shorter than the threshold.

• rh: RHG model. We use the implementation from [9]. This implementation does not allow setting the average degree directly, but we still keep average degree close to 10.

• np: nPSO model [25]. This model is similar to RHG, but the angular coordinate is not uniform, to allow creating graphs with requested number and relative size of communities. We create graphs with 8 communities, with their relative sizes chosen randomly.

According to Network Theory, many real-world networks possess similar characteristics, especially the power-law degree distributions (with \(\gamma\) values within (2,3)). A common hypothesis is that the nodes connect based on their similarity. If we assume that such a similarity can be modeled with geometry, i.e., the distance between the nodes proxies the probability of their connection, we get the foundation assumption of the geometric generative graph models; in our setup those are gs, rh, and np models. Those models are shown to produce networks that resemble real-world ones both in the degree distribution and connectivity. On the contrary, ab and cl models are non-geometric alternatives to produce networks with power-law degree distribution. Eventually, er model is a popular benchmark in Network Theory in which nodes do not connect based on their similarity. For the reproduciblity purposes, in the case of rh models, we follow the setups from comparative studies on hyperbolic embedders [8]. RHG model creates ultra-small world networks [26] (the average distance grows slower than any polynomial of the logarithm of the size of the network: heterogeneous networks with presence of the hubs).

Our preliminary analysis (Section 7) shows that the following adjustments to the basic HyperFast algorithm yield good results on real-world graphs, in terms of the the compression-to-time tradeoff: optimizing radial and distance buckets, using directed degree-based radial distances, and triangle-based edge prediction. In the next two sections these adjustments are applied.

5 Analysis of real-world graphs↩︎

5.0.0.1 Randomness in embedders

Most embedders are randomized, so we repeated a portion of the experiments with different seeds. For each real-world network, we ran 10 iterations per randomized algorithm (excluding slower embedders on the largest graphs). Our result suggest that randomness does not threaten the validity of our approach. Coefficients of variations across all embedder-based approaches are very low (in most cases they do not exceed one percent), suggesting high homogeneity of the results (see Section 9).

5.0.0.2 Overall quality assessment

We ranked methods by their average BPL across 10 iterations for each graph, with lower BPL yielding higher ranks. Figure 3 depicts the aggregate results, while Section 9 contains plots and tables.

Our analysis suggests that HyperFast with HMCS or CLOVE (especially with \(B_d=B_r=16\)) generally outperforms non-embedder approaches, achieving higher (better) ranks more frequently (Fig. 3). Surprisingly, methods utilizing BFKL or LPCS usually do not perform well. This is slightly unfortunate, as those embedders are among the fastest ones. HMCS appears promising here as it compromises compression quality with the computation time. The current state-of-the-art compression method (WebGraph with LLP) turns out to be a mediocre choice when it comes to the quality of the compression. It usually underperforms CLOVE or HMCS approaches, but it is usually better than the approaches based on BFKL or LPCS.

5.0.0.3 Maximum performance

Mean BPL offers a baseline expection for each method. However, one may be also interested in the best (optimistic) scenarios. To this end, we provide additional analyses on the best (minimal) BPL achieved per graph (where applicable). The rankings remain practically unchanged whether based on means or the best-case values (weighted Cohen’s kappa 0.99, indicating nearly perfect agreement).

Based on Table ¿tbl:stat95max95perf?, we notice that the embedder-based methods yield substantial improvements over trivial compression. In optimistic scenarios, improvements range from about 60% to as much as 80% in the extreme cases, though WebGraph with BFKL or LPCS occasionally shows marginal declines. Against current SOTA (LLP), CLOVE or HMCS in HyperFast with \(B_d=B_r=16\) achieves up to about 42% improvement in optimistic scenarios, as in ias graph. However, we observed a small decline compared to LLP+WebGraph on hepph (5%) and astroph (8%), and a significant decline on uk-2002 (66%).

5.0.0.4 Time comparison

Table [timecomp] shows the runtime breakdown for each method. The time to compress the graph using LLP is the sum of LLP+WG columns; for HMCS+WG, the sum of HMCS+WG columns; for HMCS+HyperFast with 16 buckets, the sum of HMCS, segmentation, and compression time columns. For decompression, LLP and HMCS columns do not matter, and the compression time is replaced by the decompression time.

6 Analysis of the artificial networks↩︎

For a robust statistical inference on our method’s properties, we performed simulation-based evaluation using 2,800 geometric, non-geometric, and random networks.

6.0.0.1 Ranks

The ranks’ distribution in Figure reffig:simulated is similar to the one reported for the real-world graphs. Consistent with our findings on real-world networks, our method performs better on larger networks. HyperFast with HMCS outperforms competing methods across all hyperparameters’ configurations. HyperFast with CLOVE performs slightly worse than the HMCS variants. An interesting case is the BFKL embedder: it achieves reasonable gains relative to other methods on most graphs but underperforms significantly on spherical geometry-generated graphs. The current SOTA (LLP+WebGraph) is again a mediocre choice in terms of BPL-based compression quality.

6.0.0.2 Does usage of embedders yield significant improvement?

To adress this question we performed paired Wilcoxon tests with the Bonferroni correction for the number of comparisons. See Section 10 for the full results. Our results suggest that the differences between the results obtained from HyperFast and the WebGraph based methods are significantly higher than zero on most graph types, especially those resembling real-world networks. The only exceptions occured with LPCS (\(B_d=B_r=8\)) when compared against WebGraph with CLOVE or HMCS (HyperFast performed significantly worse here). This result is not worrying though given prior observations that LPCS may underperform relative to HMCS or CLOVE on real-world networks. Notably, our proposition beats SOTA (LLP+WebGraph) in every scenario.

Comparisons among WebGraph-based methods are less clear-cut. CLOVE usually significantly improves the results. HMCS does not significantly improve performance on non-geometric graphs but consistently outperforms LLP+WebGraph. AS with real-world networks analysis, BFKL or LPCS usage may not be reasonable. However, we want to stress, that in the ultra-small-world regime (that covers most of the real-world graphs), BFKL yields significantly better results than the WebGraph-based methods (only insignificant difference with WebGraph+LLP).

6.0.0.3 HyperFast vs WebGraph

Based on the plots in Figure 5, we notice that excluding BFKL, HyperFast allows us to gain improvement over SOTA up to even over 50 percent. Especially, HMCS and CLOVE density curves peak about 40%. Similarly to the insights from the real-world graph analysis, LPCS or BFKL usage is not recommended.

6.0.0.4 Factors explaining improvement

To identify factors driving differences between results from HyperFast against the SOTA, we introduce four regression models setups:

• setup: the basic model controling for the type of the embedder (base: BFKL), the number of nodes, and edges of the graph, whether we used h16 as the value for the hyperparameters for HyperFast, and the name of the model (base: er model).

• network-based: variables computable without the model knowledge. Excludes model name; instead introduces network characterisics: gcc, and acc controling for global and average clustering coefficient; md – mean distance; dc – average degree; ecomms – the number of communities found by Levene algorithm, ci – average community intimacy, div – KL divergence measuring community size heterogeneity relative to equal sizes;

• model-based: similar to setup, but replaces model name with model-specific variables: beta \(= 1/(\gamma -1)\), model temperature (with interaction for models including it), and linearity. Linearity measures how well a single-dimensional geometry describes the connections in the network; this is 0 for non-geometric models, and otherwise, the inverse of the Hausdorff dimension of the geometric space (1 for np and rh models, \(\frac{1}{2}\) for gs since a single dimension only partially explains the two-dimensional spherical space).

• only hyperbolic: same as network-based, but only on hyperbolic models (rh and np). Includes CScore of the embedding (higher values indicate better angular covariate preservation).

Due to severe multicolinearity of variables (e.g., temperature is correlated with clustering coefficient, graph diameter is highly correlated with the mean distance,...) it is not reasonable to put all of them in a single regression. As a part of the variability is related to the factors influencing LLP+WebGraph performance that we do not control for, for the further understanding, we also performed those regressions against trivial compression as the baseline, getting stylized facts about expected performance of our method.

Based on the data in Table 1, we notice that the network type significantly affects HyperFast performance. Embedder choice significantly impacts the outcomes: HMCS yielding on average results better by about 11 percent points than the results from BFKL. If model information is unavailable, the network characteristics serve as effective proxies. Performance correlates with clustering coefficients and the community structure of the graph. Embedder that successfully retrieve angular coordinates (a proxy for similarity space) achieve better results versus SOTA. Overall, the usage of HyperFast improves the compression results against trivial. The models explain a significant share of variability when explaining the comparison against trivial method; \(R^2\) values for SOTA comparisons are reasonably high, given sample sizes.

7 Adjustments of HyperFast↩︎

In this section we provide the details of various adjustments that could be applied to HyperFast to hopefully improve its compression quality and time.

7.0.0.1 Step 1: optimize distance buckets.

In Section 3 we have proposed to split the interval of possible node distances into intervals of equal length. While this method works quite well in practice, unequal lengths may provide better results with less buckets. Therefore, we propose the following improvements. We first compute the values of \(m_c\) and \(m'_c\) for \(2B_d\) small buckets. When these values are known, we combine these small buckets into \(B_d/2\) larger buckets in an optimal way. It is possible to determine the size of the compressed stream for a given set of large buckets using entropy formulas, and find the optimal partition using a Dynamic Programming algorithm running in negligible time \(O(B_d^3)\). This doubles the running time of computing \(m'_c\) while halving the running time of the actual compression part. Since the actual compression part tends to take more time, this actually improves the total running time while hopefully improving the compression.

7.0.0.2 Step 2: directed degree-based radial distances.

CLOVE, LPCS an HMCS sort all the vertices by decreasing degree, and a vertex of index \(i\) in this order gets radial distance \(2\beta\log(i)+2(1-\beta)\log(N)\). This formula is based on the PSO model [6]. The value \(\beta\) is taken to be \(\frac{1}{\gamma-1}\), where \(\gamma\) is the estimated power-law exponent \(\gamma\) of the vertex distribution. If the graph follows the power law degree distribution exactly, we obtain that the radial distance of a vertex of degree \(d\) is close to \(2\log(N) - 2\log(d)\).

Real-world graphs may not exactly follow the power law distribution, especially for the low-degree vertices, which are the majority. Therefore it makes sense to directly use radial distance \(2\log(N) - 2\log(d)\) instead of the one provided by the embedder. This is especially useful for directed graphs, in which we can split every node into two (in-node and out-node) and set their radial distances respectively based on the in-degree and out-degree, in particular, nodes of in-degree or out-degree 0 having radial distance of infinity and thus essentially not being considered as possible sources or targets. Thus, we essentially follow the ideas outlined in Subection 2.3. One difference is that the angular position for matching in- and out-nodes is always the same, which makes sense for compression purposes, as otherwise we would need to compress the information about correlations between the two orders.

7.0.0.3 Step 3: optimize radial buckets.

In Step 1 we have optimized distance buckets, so we can also think about optimizing radial buckets. While the method we used for distance buckets does not work here, we can use a simpler, approximate one. Assume that we compress the graph based only on the information of the degree of the source node. If there are \(q\) nodes of degree \(d\), entropy coding their outgoing edges would take us \(qN_{\rm{out}} H(\frac{d}{N_{\rm{out}}})\) bits, where \(N_{\rm{out}}\) is the number of nodes of out-degree greater than 0. Essentially, we get a separate radial bucket for every possible degree; we then use a Dynamic Programming method similar to the one from Step 1 to combine them into \(B_r\) optimal distance buckets.

7.0.0.4 Step 4: triangle-based edge prediction.

So far, we have been estimating the probability of nodes \(u\) and \(v\) being connected solely on their bucketed distance \(|uv|\). However, note that the HyperFast algorithm can actually freely access the bucketed distances of both nodes \(u\) and \(v\) from the center. Therefore, instead of computing the values of \(m_c\) and \(m'_c\) for every distance bucket \(c\), we compute values \(m_{c,b,b'}\) and \(m'_{c,b,b'}\) for every distance bucket \(c\) and for every radial bucket of both in-node and out-node. Probabilities \(\frac{m_{c,b,b'}}{m'_{c,b,b'}}\) may let us improve the quality of entropy coding over using simply \(\frac{m_c}{m'_c}\), especially if hyperbolic geometry is not that suitable for modelling the given network. This comes at the cost of having to include a bigger table in the compressed stream, however, this is negligible for larger graphs.

7.0.0.5 Step 5: local search.

Yet another possible idea is to, for every node, try to move it into a different radial buckets rather than the one computed from its degree, see if it would improve the compression ratio, and actually move it if it does. (This is similar to the local search from [16].)

To test these five ideas, we have run preliminary experiments on real-world graphs. In Table 2, for each embedder, each real-world graph, and each number \(i\) from 0 to 5, we present the ratio of the HyperFast compressed file to the file compressed using LLP+WebGraph when performing steps from 1 to \(i\). We also present the running time of HyperFast.

All steps 1-4 substantially improve the compression for some graphs, while not substantially worsening the compression for others, and not worsening the running time. Step 5 substantially improves the compression for only one graph (uk-2002) while greatly worsening the running time, so we have decided not to use it.

8 Networks↩︎

Table 3 lists the real-world networks we used as benchmarks.

Table 3 gives the list of networks we benchmark on. In all cases, we have removed self-loops (if they exist), restricted to only the giant component (it the network was not connected), and replaced undirected edges with pairs of directed edges (if the graph was undirected). The restriction to the giant component was performed because the BFKL embedder assumes the graph to be connected. In most cases, these changes do not significantly affect the compression, since self-loops are rare and almost all edges are in the giant component. The only counterexample was the comedy graph; we include both the connected and unconnected (comedy-full) version of the graph, and for the experiments using the BFKL embedder on comedy-full, we add random extra edges to make the graph connected. Note that while [5] lists [28] as the source of their graphs, the graph sizes do not match; we were unable to explain this discrepancy.

9 Coefficients of variation and performance tables↩︎

Table 4 show the coefficients of variation obtained in 10 runs of tested compression methods on real-world graphs. We were unable to compute the results for CLOVE on large graphs due to the high time complexity (CLOVE runs over a week on the Patents network).

Tables 5 and 6 show the compression quality obtained by the tested compression methods. Darker background means better result.

In Figures 6 and 7 the compression quality is presented as a graph.

In Figures 8 and 9 we compare the percentage gains in the compression ratio versus the time required for our embedders.

10 Statistical inference↩︎

Figures [fig:longlongsa] and [fig:longlongwg] show whether our compression methods give a significant advantage over earlier methods, for various classes of artificial networks.

11 Implementation details↩︎

Our benchmarking tool is based on the comparison framework from [8].

We use the C++ reimplementation of LPCS and HMCS from [8]. In the case of HMCS, we use 5 levels of subcommunities. Since BP [5] has no official implementation, we use our own reimplementation in C++. We use the Rust implementation of WebGraph and LLP [3], [4].

Since we are focused on high compression rather than random access, for WebGraph, we use the hyperparameters used on the WebGraph website for high compression (window size 16, reference limit 2147483647). Likewise, we do not use the methods to allow quick random access to HyperFast compressed data, outlined in Subsection 2.2.

The code-and-data attachment to this paper is available under the anonymized link https://figshare.com/s/1b04cb24f395b8459790.

12 Conclusions and future work↩︎

We have shown that the HyperFast compression method, combined with a fast hyperbolic embedder such as HMCS, yields up to 42% improvement in the compression ratio compared to LLP+WebGraph. We conclude with some directions for further research.

• The CLOVE embedder often yields great compression, but our experiments show it is slower on large graphs than we expected. For compression applications it might be worthwhile to find out the cause for the slowdown and suggest a compromise solution.

• HyperFast assumes that the nodes are uniformly distributed along the circle. It is possible that a non-uniform distribution could yield better compression for some graphs.

• All the methods discussed in this paper use a one-dimensional model of the similarity space. The structure of some graphs is better explained by higher-dimensional models; there is some research in higher-dimensional hyperbolic embedders [34]–[37]. However, it appears that such higher-dimensional embeddings require more bits to transfer the embedding itself [8] and the algorithmic techniques used by fast embedders, WebGraph and HyperFast do not easily carry over to higher dimensions (all the higher-dimensional embedders we know are slow). These issues might limit the applicability in compression.

References↩︎