# State-of-the-Art Graph Compression (2025)

## Introduction

Graphs are ubiquitous data structures for representing entities (nodes) and their relationships (edges) in domains ranging from social networks and knowledge bases to biological networks and neural network architectures. As graphs grow in scale (often millions or billions of nodes/edges), **graph compression** has become essential to reduce storage, speed up processing, and enable efficient querying[\[1\]](https://wachiyem-74351.medium.com/graph-compression-part-a-introduction-4f228fb26633#:~:text=Compression%20of%20large%20graphs%20has,2%2C%205)[\[2\]](https://wachiyem-74351.medium.com/graph-compression-part-a-introduction-4f228fb26633#:~:text=Whereas%20there%20exists%20an%20enormous,5). In particular, **knowledge graphs** (which store factual triples or semantic networks) and **neural network architectures** (which can be viewed as computational graphs of layers/operations) pose significant challenges due to their size and complexity. Modern compression techniques target these challenges by either *losslessly* encoding the full graph information in fewer bits or *lossily* simplifying the graph while preserving important properties. This guide surveys state-of-the-art (SOTA) methods (circa December 2025\) for compressing graphs and even *nested graphs* (graphs of graphs), covering both classical algorithmic approaches and recent machine learning-based methods.

We first clarify the distinction between lossless and lossy compression, then detail leading techniques in each category. We highlight methods applicable to **nested or hierarchical graph structures** (“graph-of-graphs”), and discuss specific considerations for compressing knowledge graphs and neural network graphs. Throughout, we include recent academic advances (2023–2025), popular benchmarks/datasets for evaluation, and links to open-source implementations or tools.

## Lossless vs. Lossy Graph Compression

Graph compression methods are broadly categorized as **lossless** or **lossy**, depending on whether they preserve all original information:

* **Lossless compression:** The compressed graph can be decoded to *exactly* the original graph with no information loss. All vertices, edges, and labels are retained. The goal is typically to minimize storage (bits used) while supporting efficient access or queries on the compressed representation. Lossless methods often exploit structural redundancies (like repeated patterns or heavy-tailed degree distributions) to encode graphs more compactly[\[3\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=space%2C%20exploiting%20the%20inner%20redundancies,89%20bits%20per%20link)[\[4\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=representations%20that%20are%20easier%20to,). For example, a web graph with billions of links can be encoded in a few bits per edge without losing any links[\[5\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=centred%20around%20referentiation%20and%20intervalisation,89%20bits%20per%20link).

* **Lossy compression:** The compressed graph is an *approximation* or summary of the original – some details are sacrificed for a smaller or simpler representation. Lossy techniques (often called *graph summarization* or simplification) may merge nodes or edges, drop less important connections, or embed the graph into a lower-dimensional space[\[4\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=representations%20that%20are%20easier%20to,). The aim is to preserve essential structural properties (connectivity, distances, community structure, etc.) or task-specific information while drastically reducing graph size. For instance, merging nodes into **super-nodes** and edges into **super-edges** yields a summary graph that retains high-level connectivity patterns[\[4\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=representations%20that%20are%20easier%20to,). Lossy compression is useful when exact recovery is not needed – e.g. for visualization, analytics, or as input to machine learning models – and can greatly accelerate algorithms (by working on a smaller graph) at the cost of some accuracy.

In practice, lossless and lossy methods are complementary. Lossless compression is preferred for *data storage, transmission,* and *exact query processing*, whereas lossy compression (graph summarization) is used for *insight extraction, faster computations,* or *as a preprocessing for learning tasks*. Next, we delve into each category.

## Lossless Graph Compression Techniques

### Classical Lossless Techniques (Algorithmic)

Classical approaches rely on algorithmic and data-structural techniques to reduce graph storage without dropping information. Key methods include:

* **Web Graph Compression (referentiation & gap encoding):** A seminal example is the *WebGraph* framework by Boldi and Vigna, which achieves extremely high compression on web-scale graphs by exploiting their link patterns[\[3\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=space%2C%20exploiting%20the%20inner%20redundancies,89%20bits%20per%20link). WebGraph uses techniques like **reference encoding** (encoding adjacency lists by referencing similar lists of nearby nodes) and **gap encoding** (storing sorted neighbor IDs as differences). With these methods, the WebGraph library compressed a 1-billion edge web crawl (“WebBase” graph with 118M nodes) into as little as \~3.1 *bits per edge*[\[3\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=space%2C%20exploiting%20the%20inner%20redundancies,89%20bits%20per%20link) – a remarkable reduction. Such compression leverages properties of web graphs (power-law degree distributions and locality in link structure). The *WebGraph* Java library (package it.unimi.dsi.webgraph) provides an implementation, including support for accessing neighbors without full decompression[\[6\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=techniques%20that%20delay%20the%20decompression,graph%2C%20so%20to%20experiment%20with). This approach is lossless and has influenced many later compressors.

* **Adjacency List Coding and Bitmaps:** Many lossless schemes compress the adjacency list or matrix representation of graphs. For example, **bitset representations** with entropy coding can compress dense adjacency matrices effectively. The *k\<sup\>2\</sup\>-tree* is a specialized data structure that recursively splits an adjacency matrix into quadrants, storing it as a compact bit tree – very effective for sparse graphs and used in RDF stores and social network compression[\[7\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=succinct%20data%20structures,triple%20pattern%20access%20that%20is)[\[8\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=preserving%20the%20query%20capabilities,pattern%20access%20that%20is%20equal). Another line of work uses **succinct data structures** (like Elias-Fano encodings for sorted lists) to store graphs in compressed form while supporting fast rank/select operations for queries. For instance, the HDT (*Header-Dictionary-Triples*) format in semantic web compresses RDF knowledge graphs by dictionary-encoding all strings and using bitmaps for relationships[\[7\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=succinct%20data%20structures,triple%20pattern%20access%20that%20is). HDT can compress huge graphs (e.g. the entire Wikidata knowledge graph, tens of billions of triples) into a 300 GB file – comparable to gzip compression – while still allowing triple-pattern lookup via indexed structures[\[8\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=preserving%20the%20query%20capabilities,pattern%20access%20that%20is%20equal). Tools like the [HDT library](https://github.com/rdfhdt/hdt-cpp) provide implementations for RDF graph compression and querying.

* **Grammar-Based Compression:** An emerging approach is to compress graphs by deriving a **graph grammar** that generates the graph. One popular technique uses the RePair algorithm (originally for string compression) generalized to graphs. In 2023, Adler *et al.* introduced **Incidence-Triplet RePair (ITR)**, a grammar-based compressor for labeled graphs (including RDF). ITR finds common substructures (like frequently co-occurring edge patterns) and replaces them with grammar non-terminals. The result is a compact grammar that can regenerate the original graph. A key benefit is that ITR supports efficient queries (e.g. neighbor and triple queries) directly on the compressed grammar. It outperforms earlier RePair-based graph compressors on query speed while achieving comparable compression ratios. Grammar-based methods shine when a graph has many repeated subgraphs (motifs): instead of storing each occurrence, the motif is stored once and reused, which conceptually treats repeated subgraphs as “macro-nodes” – a theme useful for graph-of-graphs compression.

* **Frequent Substructure Mining (Cliques, Stars, etc.):** Earlier research compressed graphs by identifying specific structures that can be compactly represented. A notable example is the work of Buehrer and Chellapilla (2008), who mined frequent **bipartite cliques** in web graphs to compress them. A clique (complete subgraph) can be stored by listing its vertices once, instead of listing all edges. By finding large bipartite cliques (which are common in web adjacency matrices), they achieved high compression rates. However, one drawback was that using such compressed representations directly in algorithms (e.g. computing shortest paths) was not straightforward – additional decoding or algorithm adaptation was needed. Similarly, Fan *et al.* converted common patterns like **stars** (a node with many identical neighbors), **cliques**, and **paths** into single “super-nodes” to shrink graph size for speeding up queries. This yielded significant size reduction and faster distance queries, but reconstructing exact paths for all node pairs could incur overhead. These pattern-based approaches are lossless as they fully encode the graph (just in a factored form), and they paved the way for modern motif-based compressors.

* **Handling Overlaps and Redundancy:** A current frontier (2024–2025) in lossless compression is dealing with *overlapping* structures. Many methods compress cliques or communities, but real graphs have overlapping communities which might get encoded multiple times. Pitois *et al.* (2025) address this by detecting overlapping parts of dense subgraphs (like quasi-cliques) so that these overlaps are not redundantly encoded[\[9\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=Several%20graph%20compression%20approaches%20rely,several%20graph%20datasets%2C%20and%20our). By “digging deep” into structure overlaps and encoding shared parts once, their algorithms achieved better compression than prior motif-based methods[\[10\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=the%20set%20of%20their%20vertices,several%20graph%20datasets%2C%20and%20our). This kind of optimization is crucial for compressing *nested graphs*, where subgraphs share components.

**Implementation and Tools:** In addition to the WebGraph and HDT libraries mentioned, many academic prototypes and open-source tools exist. For example, the ITR approach (Adler et al.) is available as a tool for compressing and querying RDF graphs. Another GitHub project, *GraphCompression* (Danielathome19, 2023), provides a suite of new lossy and lossless techniques for external-memory graph representation (indicating growing practical interest). For general graph data structures, libraries like [NetworkX](https://networkx.org/) or [SNAP](http://snap.stanford.edu) are not compression tools per se, but they sometimes integrate with compressed graph formats for efficiency. It’s worth noting that many lossless methods are domain-specific (optimized for web graphs, social networks, etc.)[\[11\]](https://arxiv.org/html/2502.02477v1#:~:text=preserve%20the%20path%20information%2C%20it,these%20techniques%20achieve%20high%20compression); thus, tools are often tailored to certain graph types.

### Machine Learning-Based Lossless Compression

Purely ML-based *lossless* compression of graphs is less common, since ensuring *exact* reconstruction usually requires algorithmic precision. However, ML can assist by *reordering* or *predicting* graph structures to improve classical compression. For example, learning a better ordering of nodes (to maximize locality or similarity in adjacency lists) can boost compression ratio – an approach explored in some recent works. There are also information-theoretic ML methods: Vippathalla *et al.* (2025) theoretically characterize graph compression limits using entropy analysis and consider *learning-based encoding* in special cases (like when a correlated graph is known at the decoder as side information). While largely theoretical, this indicates a trend of combining ML with coding theory for graphs.

Another avenue is **learned entropy coding** for graphs: analogous to learned image compression, a neural network could be trained to assign short codes to common graph patterns. For instance, an autoregressive graph model (like a GraphRNN) can serve as a predictor and then an entropy coder compresses the prediction residuals. As of 2025, such approaches are still experimental but could become SOTA as seen in other domains (an example is a 2024 ICLR work on learned entropy coding achieving efficient lossless compression, albeit demonstrated on sequences/images).

In summary, most *practical* lossless graph compression solutions today are still based on clever algorithms and data structures, possibly enhanced by minor ML components. But the boundary between lossless and lossy can blur if we allow tiny errors for big gains; that’s where modern lossy methods come in.

## Lossy Graph Compression Techniques (Graph Summarization)

### Classical Approaches to Graph Summarization

Classical lossy methods focus on *simplifying* the graph structure while preserving key properties. This often goes by names like **graph summarization**, **reduction**, **simplification**, or **sparsification**[\[12\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=i,16%5D.)[\[13\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,preserving%20condensed%20graphs.). Major techniques include:

* **Aggregation (Coarsening) into Super-Nodes:** This is a core approach where groups of similar or connected nodes are merged into one, and corresponding edges are merged into “super-edges.” The result is a smaller *summary graph* that abstractly represents the original. This process, also called **graph coarsening**, is widely used in multi-level graph algorithms and was originally developed to accelerate computations like graph partitioning. The goal is to preserve structures like community connections or spectral properties. For example, merging nodes that share many neighbors can preserve overall network connectivity. Coarsening can be repeated hierarchically, producing a *graph-of-graphs* (each level is a compressed version of the previous) – a natural handling of nested graphs. Classical coarsening methods (like heavy-edge matching or minimum cut coarsening from the 2000s) were heuristic; newer ones preserve graph spectra more rigorously[\[14\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,). The coarsening ratio (fraction of nodes merged) can be tuned for a trade-off between summary size and fidelity[\[14\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,). Coarsening is lossless w.r.t certain global properties (e.g. the smaller graph can be designed to have a similar Laplacian spectrum as the original[\[14\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,)), but individual node identity is lost (hence it’s lossy overall).

* **Graph Sparsification (Edge Suppression):** Sparsification techniques remove a subset of edges (and sometimes nodes) to yield a sparser graph that approximately preserves characteristics like cuts or distances. A classic example is *spectral sparsification* (Spielman & Srivastava, \~2010), which samples edges to preserve the graph Laplacian spectrum within bounds. The result is a sparse graph in which distances or random-walk properties closely resemble the original. Other sparsification approaches include **backbone extraction**, which prunes statistically insignificant edges (e.g., in a weighted graph, keep only edges that represent strong connections or high information flow). The idea of a *network backbone* is to retain short-range or strong interactions and drop long-range or weak ones. For instance, in a transportation network, one might keep highways (backbone) and drop small roads for a high-level view. Sparsification is widely used for visualization (reducing clutter) and speeding up algorithms, since many graph algorithms run much faster on sparse graphs. It is lossy, but if done carefully (e.g. via sampling or optimization), it preserves important metrics like centrality or connectivity with high fidelity[\[13\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,preserving%20condensed%20graphs.).

* **Pattern Mining and Replacement:** Some summarization methods identify common *motifs* or subgraphs in the graph and replace them with single nodes or a compact description. A prominent example is the VoG (Vector of Graphs) approach (Koutra et al. 2015), which uses the Minimum Description Length (MDL) principle to find structures like cliques, stars, chains, etc., that best compress the graph when described as motifs[\[15\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=sparsification%20,preserving%20condensed%20graphs.). The algorithm essentially says “this graph can be described by these *patterns* plus a few error edges.” By storing just the pattern identities and their occurrences, one obtains an interpretable summary. For instance, if a graph contains many triangles (triadic closures), a motif-based summary might note “X triangle structures exist” instead of listing all those edges. Recent research (as cited above with Pitois et al. 2025\) is extending this by handling overlapping patterns to avoid double-counting edges[\[9\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=Several%20graph%20compression%20approaches%20rely,several%20graph%20datasets%2C%20and%20our). Pattern-based summarization is very useful for understanding network structure (e.g., “network is composed of these building blocks”) and can achieve high compression when clear motifs exist. However, it may sacrifice arbitrary details that don’t fit the chosen motifs.

* **Influence/Reachability-based Summaries:** In contexts like social networks or information networks, one might compress the graph by preserving *influence paths* or reachability rather than exact structure. An **influence-based compression** might choose a subset of nodes as “influencers” and only keep edges that show how information spreads from them[\[16\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=...%20Bit,14%5D.). The summary thus retains the reachability or connectivity information relevant to diffusion processes. This can be formalized as an optimization problem: maximize coverage of connectivity with as few edges as possible[\[16\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=...%20Bit,14%5D.). Similarly, **transitive reduction** in directed acyclic graphs (keeping only critical edges that preserve reachability) is a form of lossily compressing reachability information. These methods typically target specific query types (e.g., reachability queries can be answered from the compressed graph but maybe not arbitrary queries).

* **Simplification by Node Removal:** In some cases, removing low-importance nodes (and incident edges) can simplify the graph. For example, in a power-law degree network, one might remove many low-degree peripheral nodes to focus on the “core” structure. There is research on identifying the **core** of graphs (see, e.g., k-core decomposition or recent surveys on *cores of higher-order graphs*[\[17\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=In%20this%20survey%2C%20we%20explore,the%20simplification%20of%20higher%20graphs)). Removing nodes is obviously lossy, but if those nodes contribute little to properties of interest (like overall connectivity or centrality distribution), the impact may be small. A 2025 study by Hu *et al.* introduced an information-theoretic pruning that iteratively removes edges with the least impact on mutual information of the network, yielding a simplified network that *preserves semantic connectivity* very well[\[18\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=understanding%20community%20organization%2C%20information%20flow%2C,Extensive%20experiments%20on%20social%20and). Such pruning essentially removes “noise” edges and nodes, producing an interpretable backbone of the graph[\[18\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=understanding%20community%20organization%2C%20information%20flow%2C,Extensive%20experiments%20on%20social%20and).

**Output of Classical Summaries:** The result of these techniques is often a **meta-graph** or summary graph that is much smaller. Importantly, there is often a mapping from the summary graph back to the original: e.g., super-nodes map to sets of original nodes. This mapping can be leveraged to answer queries approximately on the original graph by operating on the summary (for example, an approximate shortest path distance between two original nodes can be answered by distance in the summary graph that contains them). Many classical summarization methods ensure that certain queries (like neighbor queries or degree queries) can be answered exactly or within error bounds from the summary[\[12\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=i,16%5D.). The summary thus acts like a compressed index.

### Machine Learning-Based Graph Compression (Summarization & Embedding)

With the rise of graph neural networks (GNNs) and other deep learning models, a new class of graph compression techniques has emerged. These methods *learn* how to compress a graph, often by optimizing a objective that measures information loss. Key ML-based approaches include:

* **Graph Embeddings:** One of the earliest and most widespread ML techniques for graphs is to embed nodes (or entire graphs) into a lower-dimensional vector space. In knowledge graphs, for example, **embedding models** like *TransE* (Bordes et al., 2013\) compress multi-relational knowledge into dense vectors. Each entity and relation is mapped to a vector such that the knowledge graph’s triples can be approximately reconstructed (e.g., TransE embeds relations as translations in vector space). These embeddings are a lossy compression of the knowledge graph: the continuous vectors take far less space than the symbolic triples, and while you cannot recover the exact graph from them, they preserve enough information to answer queries like link prediction. Similarly, for homogeneous graphs, *node embedding* methods (DeepWalk, Node2Vec, etc.) compress the graph’s adjacency structure into node feature vectors by learning from random walks. There are also *graph-level embedding* approaches (Graph2Vec, etc.) that produce a single vector representing an entire graph (useful for graph classification tasks). In all these cases, a potentially huge graph is compressed into a matrix of embeddings. Downstream tasks can then be run on these vectors instead of the original graph, which is a major speedup. However, this is a lossy representation – it’s task-specific and doesn’t preserve arbitrary graph queries. The quality of compression is measured by downstream performance (e.g., an embedding that retains 95% of accuracy in a task is considered good). Embeddings effectively trade exact graph structure for compactness and computational convenience.

* **Graph Autoencoders and Variational Autoencoders:** These are neural networks designed explicitly to compress and reconstruct graph data. A **Graph Autoencoder (GAE)** uses a GNN (like a Graph Convolutional Network) as an encoder to produce latent embeddings for nodes (or for the whole graph), and a decoder (often a simple inner product or another network) that tries to reconstruct the adjacency matrix or features from those embeddings. For example, Kipf & Welling’s GAE/VGAE (2016) encodes each node into a low-D vector such that the inner product of two vectors predicts whether an edge exists between the corresponding nodes. By training this end-to-end on the graph, the encoder learns a compressed representation (the set of node vectors) that retains as much information as needed to reconstruct edges. This is fundamentally a compression: the latent size (number of nodes × embedding dimension) is much smaller than the full adjacency matrix, especially for large sparse graphs. Variational graph autoencoders (VGAE) further impose a probability distribution on the latent space to allow sampling. These methods have been used for link prediction, anomaly detection, and graph generation. They are lossy (reconstruction isn’t perfect, and some information like exact graph topology might be lost if capacity is limited), but they achieve a *learned* compression optimized for preserving the most important structures for reconstruction. Many **open-source implementations** exist (e.g., in [PyTorch Geometric](https://pytorch-geometric.readthedocs.io/) or [DGL](https://www.dgl.ai)), and researchers often release their GAE training code for specific datasets.

* **Differentiable Graph Pooling (Hierarchical Compression):** In graph deep learning, **graph pooling** layers aim to reduce the graph size as part of a learned model. Notably, Ying *et al.* (2018) introduced **DiffPool**, a neural module that learns to assign nodes to clusters (super-nodes) in a way that preserves graph structure in the next coarsened layer. Essentially, DiffPool produces a compressed adjacency matrix for the next layer by *learning* a cluster assignment matrix. Stacking multiple such layers yields a hierarchy of coarser graphs – exactly a learned *graph-of-graphs* compression. The pooling is trained together with a task (e.g., graph classification) so that it retains information relevant to that task. Many variants followed: e.g., SAGPool, TopKPool, each using different criteria (like node feature importance) to drop or merge nodes. These approaches mirror classical coarsening but are data-driven. The result is a much smaller graph (or eventually just a single node embedding) after a few pooling steps. While these methods are often used internally in GNNs, one can view them as producing a *nested compressed representation* (like a binary tree of merged nodes). If one is interested in an actual summary graph, the cluster assignments from DiffPool can be used to form an explicit summary (with super-nodes representing clusters). The **Graph Summarization with GNNs Survey (Shabani et al., 2024\)** covers numerous such methods, including graph convolution-based and attention-based models for summarization. It also notes a new line of research using **graph reinforcement learning** to iteratively improve summaries.

* **Reinforcement Learning for Graph Compression:** Instead of hand-crafting a heuristic to drop edges or nodes, researchers have applied RL to let an agent learn an optimal compression strategy. A recent example (2025) is **Cutter**, a dual-agent reinforcement framework that learns to remove edges while preserving graph *robustness* (connectivity and critical structures). The agents are rewarded for maintaining certain graph properties (like small shortest path changes) while minimizing size. Over many episodes, the RL agents “learn to compress” by trial and error, eventually discovering policies that outperform greedy pruning. Another work uses RL to learn which nodes to merge for the best summary quality. These methods are promising for scenarios where you can define a clear reward (e.g., preserve all pairs connectivity, or preserve classification accuracy when using the summary) but the search space of possible compressions is huge – RL can navigate this space. Early results show RL-based compression can yield very compact graphs that still perform well on tasks (like node classification) compared to baselines. The downside is that training these agents can be computationally expensive.

* **Graph Condensation for GNN Training:** A very recent trend (2022–2025) is **graph condensation**, which aims to create a significantly smaller synthetic graph that can replace the original for the purpose of training a GNN. It’s analogous to dataset distillation in images. The idea is to *learn* a tiny graph (with far fewer nodes) such that a GNN trained on this tiny graph will generalize almost as well as if it were trained on the full graph. Several methods (GCond, SFGC, etc.) optimize a small set of representative nodes and weighted edges. Impressively, some works report “lossless” performance in that the GNN’s accuracy on certain tasks is almost the same using the condensed graph vs. the full graph. For example, a condensed graph of only a few hundred nodes might replace a graph of tens of thousands for node classification, saving enormous training time. This is a highly task-driven compression: it preserves only the information relevant for a specific task and specific GNN architecture. A 2023 tutorial categorizes graph condensation methods into several families and benchmarks them. While not a general-purpose compression (you wouldn’t use condensed graphs for querying), this direction is crucial for scaling graph machine learning. It’s another case of *graph-of-graphs*: essentially the condensed graph is a mini-version that stands in for the original.

**Benchmarks and Evaluation for Lossy Methods:** Because lossy compression is task-dependent, evaluation uses a variety of benchmarks:

* *Graph summary quality* can be measured by how well certain properties (degree distribution, clustering coefficient, spectra) are preserved. Datasets like social networks (e.g., Twitter, Facebook, DBLP collaboration network) and web graphs are used to test how summaries preserve properties or query answers[\[19\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=...%20However%2C%20visualizing%20large,)[\[13\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,preserving%20condensed%20graphs.). For example, a summary might be tested on answering approximate distance queries on a road network, or counting triangles in a social network.

* *Graph classification benchmarks* (e.g., MUTAG, PROTEINS, or the more recent ogbg-mol\* datasets from the Open Graph Benchmark) are used to evaluate pooling methods: a pooling-based GNN is run on these and its accuracy is compared to baseline, to see if the pooling (compression) lost important info.

* *Knowledge graph completion tasks* (like link prediction on FB15k-237, WN18RR) can serve to evaluate knowledge graph embeddings: the smaller the embedding (compression) that still achieves high MRR or Hits@10, the better the compression method.

* For graph condensation, recent works introduced **GC-Bench**, a benchmark suite for graph condensation comparing methods on multiple datasets and GNN models. It measures the test accuracy of a GNN trained on the condensed graph vs. on the original graph (a near-equal accuracy means the condensation was very effective).

In summary, machine learning has greatly expanded the toolkit for lossy graph compression, enabling *adaptive, task-specific compression*. These approaches often produce not just a smaller graph, but also **learning-based codes** (embeddings) or **models** that implicitly contain the graph information (e.g., a trained GNN can be seen as a compression of the training graph into its weights). Next, we discuss how these techniques apply to special cases of **nested graphs, knowledge graphs, and neural network graphs**.

## Compressing Nested and Hierarchical Graphs

“Nested graphs” or “graphs of graphs” refer to scenarios where one graph’s nodes may themselves represent subgraphs, or multiple graphs are interconnected at a higher level. Compressing such structures requires handling multiple layers of connectivity. Several methods outlined above naturally address this:

* **Hierarchical Compression:** Graph coarsening and multi-level summarization inherently produce a hierarchy of graphs – e.g., *level 0* is the original graph, *level 1* is a coarsened summary, *level 2* is a summary of the summary, and so on. This hierarchy is effectively a *tree of graphs*, where each node in the tree is a graph that summarizes a part of the graph below. Such multi-level compressions are common in large-scale graph processing (METIS partitioning is a classic example that creates a chain of coarser graphs). The entire multi-level structure can be seen as a compressed representation too. A 2024 method, **HiCompress** (Hierarchical Compression via Large Language Models), explicitly aligns with this idea for *text-rich graphs*: it compresses local neighborhoods into summaries (using an LLM to summarize textual node content) and then compresses the summary graph further, aligning the language model’s understanding with the graph’s structure. This shows a practical use-case of nested compression: first compress node attributes and small subgraphs, then compress the connections among subgraphs.

* **Graph Grammars and Motifs:** Grammar-based compression (like the RePair method and its gRePair variant for RDF[\[20\]](https://pmc.ncbi.nlm.nih.gov/articles/PMC9003471/#:~:text=gRDF%3A%20An%20Efficient%20Compressor%20with,based%20graph%20compression)) naturally handles graphs of graphs. A grammar rule can be interpreted as a subgraph (right-hand side) being represented by a single non-terminal node (left-hand side) in a higher-level graph. If a subgraph appears multiple times disjointly in the original, the grammar sees those as multiple expansions of the same rule. In effect, the grammar is a *two-level representation*: a top-level graph of non-terminals and a set of definitions for each non-terminal (subgraph). This concept can be extended to more levels (a grammar can have non-terminals defined in terms of other non-terminals). Thus, grammar compression iteratively captures nested structure. For example, suppose you have a social network where each **community** is internally a clique and communities are connected in a line. A grammar could compress each clique into a symbol (losslessly, by a rule), and then compress the line of communities. You get a compressed representation with two layers: the high-level chain of communities, and the low-level clique structures. If communities themselves had substructures, more layers could be added. So grammar compression is a powerful way to handle nested or self-repeating graph structures. The recently cited *gRDF* approach uses grammar compression on RDF graphs, which often contain repetitive substructures (like similar ontology branches)[\[20\]](https://pmc.ncbi.nlm.nih.gov/articles/PMC9003471/#:~:text=gRDF%3A%20An%20Efficient%20Compressor%20with,based%20graph%20compression).

* **Multiple Graphs and Hypergraphs:** Sometimes “graph-of-graphs” means you have many graphs and a higher network connecting them (e.g., each graph could be a molecule, and there’s a network indicating interactions between molecules). Compressing such a dataset might involve compressing each graph *and* the inter-graph links. If many graphs share common patterns, one could form a “dictionary” of subgraphs that appear across graphs (similar to motif mining) and store each graph as a sequence of references to those subgraphs. This is analogous to how one might compress a book by a dictionary of common phrases. While not much literature directly addresses this scenario, it’s feasible to extend existing methods: e.g., a **graph database** compression could find subgraphs common to many graphs and only store one copy (plus pointers). This is beneficial in chemical databases, for instance, where certain functional groups (sub-molecules) recur in many compounds.

* **Hypergraph and Multi-layer Graph Compression:** Nested graphs can also refer to multi-layer networks (each layer is a graph on the same nodes, with different edge types, common in social or biological networks). Compressing multi-layer graphs might compress each layer individually (like compress each relation in a knowledge graph separately) and then compress correlations between layers. A grammar-based approach like ITR can handle labeled edges (each edge type akin to a layer) by treating the type as part of the adjacency pattern. Also, a recent line of work looks at finding **cores of higher-order graphs** (hypergraphs, simplicial complexes) which can be seen as extending graph compression to more complex “graph-of-graphs” structures[\[17\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=In%20this%20survey%2C%20we%20explore,the%20simplification%20of%20higher%20graphs). The core is a minimalist representation retaining topological information[\[17\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=In%20this%20survey%2C%20we%20explore,the%20simplification%20of%20higher%20graphs). These theoretical developments ensure that even nested structures (like a graph where edges themselves are graphs, as in a simplicial complex) can be simplified meaningfully.

* **Knowledge Graphs as Graph-of-Graphs:** A knowledge graph can be viewed as a collection of subgraphs (each centered on an entity or a concept). Techniques like *entity summarization* or *knowledge graph summarization* treat each entity’s local neighborhood as a unit to compress. For example, an entity with many similar relationships might be summarized by grouping those relationships. One could compress a knowledge graph by clustering entities that share relational patterns and representing the cluster with a prototype subgraph. In effect, each cluster forms a condensed subgraph in the summary. This approach was explored in some ontology summarization tools and for index compression in triplestores. The **ConceptNet** commonsense graph (with nodes as natural language phrases) is huge and very heterogeneous; Hwang et al. (EMNLP 2023\) demonstrated that by *learning* which parts of a ConceptNet subgraph are relevant and pruning the rest (a differentiable compression), they could vastly reduce the subgraph size while *improving* the quality of results when that subgraph is used in reasoning. Essentially, they treat the original subgraph (knowledge around certain concepts) as a graph to be compressed (via an attention-based GNN) into a smaller subgraph that’s still rich in relevant info. This is a nested scenario: the knowledge graph provides a subgraph, which is then compressed for a particular context.

In summary, nested graphs are handled by **multi-level compression**. Most of the advanced methods inherently produce or rely on multiple layers of abstraction (just as one might compress an image by first segmenting regions and then encoding each region). The challenge is to ensure that the compression at each level preserves the ability to reconstruct or infer properties of the level below. When successful, the payoff is huge: you might compress a complex system of graphs into a very compact multi-resolution representation.

## Compression of Knowledge Graphs

Knowledge graphs (KGs) – such as DBpedia, Wikidata, Freebase, or domain-specific ontologies – are large graphs with labeled edges (relations) and often textual attributes. Compressing KGs is vital for storage (these can have billions of triples) and for speeding up query engines or downstream ML models.

**Lossless Compression for KGs:** A lot of focus has been on **RDF graph compression**, since RDF is a common format for KGs. We already mentioned HDT, which is a standard for binary RDF serialization that compresses by using dictionaries for all unique nodes and relations, then storing the triple structure in compressed bitmaps[\[7\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=succinct%20data%20structures,triple%20pattern%20access%20that%20is). HDT and similar techniques (like *RDF succinct triple stores*) achieve impressive compression (often \>10x smaller than naive CSV or N-Triples) while still allowing basic triple pattern queries without full decompression[\[8\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=preserving%20the%20query%20capabilities,pattern%20access%20that%20is%20equal). For example, the entire Wikidata (which is an extremely large KG) can be encoded in HDT such that triple lookups (subject-predicate-object queries) can be answered in memory from the compressed form at speeds comparable to a traditional database[\[8\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=preserving%20the%20query%20capabilities,pattern%20access%20that%20is%20equal). This is a big deal for deploying KGs on limited hardware or making them downloadable. The grammar-based ITR method (2024) specifically targets RDF as well, using RePair to compress repetitive structures like ontology hierarchies. Another approach, *gRDF* (2023), applies graph grammar (gRePair) to RDF and reports it as one of the most efficient methods for compressing RDF data[\[20\]](https://pmc.ncbi.nlm.nih.gov/articles/PMC9003471/#:~:text=gRDF%3A%20An%20Efficient%20Compressor%20with,based%20graph%20compression).

Beyond specialized stores, **relational database techniques** (like columnar storage, dictionary encoding, and clustering) are also used in KG engines to compress data. Many triplestores will sort and partition triples in ways that compress well (e.g., group by subject, so you can compress consecutive triples with the same subject by storing the subject once). Some even use **offset encoding** for numeric identifiers or **prefix encoding** for IRIs (since IRIs often share long common prefixes).

**Lossy Summarization of KGs:** Knowledge graphs often contain redundant or less relevant information depending on the task. Summarizing a knowledge graph can mean either *schema summarization* (summarizing the ontology or schema of the KG) or *instance summarization* (summarizing instances/entities and their relationships). A schema-level summary might compress an ontology by merging similar classes or roles, giving a high-level view (useful in large ontologies where you might have dozens of classes that are variants of a concept – summarizing could collapse them). Instance-level summarization might cluster entities that have similar connection patterns. For example, consider a KG of academic papers: one might compress it by grouping papers that have the same authors and venue into one representative node (losing the individual identity but preserving the fact “this set of papers share properties”).

One popular approach in KGs is to compute an **“entity summary”**: a small subgraph of facts that best represent the entity. If you need to display or reason with a KG in a constrained way, you might compress each entity’s neighborhood to the top-k most important relations. This is used in some applications to make KGs more tractable for humans or for certain algorithms. It’s lossy because many facts are omitted, but ideally the important ones (like key attributes) are kept.

**Knowledge Graph Embeddings:** As discussed, KG embedding models compress a KG into a set of vectors. This can be seen as *compressing the knowledge content* into continuous space. Notably, knowledge graph completion tasks (predicting missing links) have been tackled by increasingly compact models. For instance, DistMult, ComplEx, RotatE, etc., all embed KGs in fairly low dimensions (often 100-1000 dimensions per entity) and can achieve good accuracy on link prediction. The entire set of embeddings for a large KG like Freebase may occupy far less memory than the adjacency list of the KG. For example, 1 million entities with 100-dim floats is \~400 MB, which is smaller than storing all triples if each entity has many. These models are lossy (they won’t recall a random infrequent fact accurately), but they *generalize* the graph’s information, which can be considered a form of compression \+ inference. A recent trend is **compressing the embeddings themselves** – e.g., using binary or low-precision embeddings, or factorizing the embedding table – effectively compressing the *compressed representation*. There are 2023 works on quantizing KG embeddings to reduce memory while maintaining link-prediction performance, showing how multi-stage compression is possible (graph → embedding → quantized embedding).

**Neuro-Symbolic Approaches:** An exciting development at the intersection of KG and ML is using neural networks to compress and prune KGs for specific tasks. The EMNLP 2023 paper by Hwang et al. we mentioned is a prime example. In that work, a commonsense KG (ConceptNet) is too large and noisy to directly feed to a language model for generating explanations. They introduce a **differentiable graph compression** step: essentially a GNN (a relational graph convolutional network, R-GCN) with an attention mechanism learns to score nodes/edges for relevance, and only the top-scoring subgraph is retained. This subgraph is thus a lossy compression of the original KG subgraph, focused on a particular query or context. They found that using these compressed subgraphs actually led to *better* results in generating explanations, because the noise was reduced. This highlights that compression can improve downstream quality by discarding distracting information. The authors have released their code for KG compression as well, which could be useful for others looking to compress KGs in NLP pipelines.

**Benchmark datasets for KG compression:** In storage/query contexts, benchmarks include datasets like Wikidata, DBpedia, YAGO, and synthetic ones (LUBM benchmark for university ontology, for example) to measure compression ratio and query speed. For embedding-based, standard link prediction sets (FB15k-237, WN18RR, ConceptNet subsets, etc.) are used to evaluate how well a compressed representation (like low-dim or quantized embeddings) retains predictive power. There are also *knowledge graph summarization* benchmarks in some research, where the task might be to produce a summary that covers a high percentage of facts or that can answer a set of queries with some tolerance.

In practice, knowledge graph compression often combines approaches: e.g., use HDT or similar to store it efficiently, and use embedding or pruning techniques to compress it for ML usage. Many tools integrate these: for example, the Blazegraph engine (for RDF data) can use dictionary encoding and block compression under the hood, and libraries like DGL-KGE can train embeddings and then quantize them for deployment.

## Compression of Neural Network Architectures

Neural network models (especially deep neural networks) are often represented as graphs: nodes (layers or neurons) and edges (connections or data flow). Compressing neural networks has been a huge research area, motivated by deploying models on limited hardware (mobile/edge devices) and speeding up inference. Here we focus on compressing the *architecture and weights* of neural networks, interpreting it through the graph lens.

**Network Pruning (Sparsification):** Pruning removes unnecessary weights or even entire neurons/filters from a neural network graph. It’s analogous to graph sparsification – the dense connectivity is made sparse. Pruning can be unstructured (remove individual weights, making the weight matrices sparse) or structured (remove entire channels, filters, or layers, effectively removing nodes or subgraphs from the architecture). Remarkably, modern pruning methods can eliminate **90% or more** of the weights of a network like ResNet-50 on ImageNet while maintaining very high accuracy[\[21\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=pruned_model%20%3D%20pruner). For example, after fine-tuning, a ResNet-50 with *90% of connections removed* can still achieve around 74-75% top-1 accuracy on ImageNet, compared to \~76% for the original – a negligible drop[\[21\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=pruned_model%20%3D%20pruner). This means the pruned network (only 10% of the original graph’s edges) is almost as good, effectively a highly compressed version of the original network graph. Pruning reduces model size and computational cost. Many techniques (magnitude pruning, lottery ticket hypothesis iterative pruning, sparsity-inducing regularization, etc.) exist. Some 2023 innovations include **movement pruning** (which considers weight trajectory during training) and **graph sparsity learning** (treating the network as a graph and learning which connections to keep via GNN-based criteria). Pruned models are often evaluated on benchmarks like ImageNet (for CV models) or GLUE (for NLP transformers) to ensure they retain accuracy. Open-source tools like [TensorFlow Model Optimization](https://www.tensorflow.org/model_optimization) and [PyTorch’s pruning API](https://pytorch.org/tutorials/intermediate/pruning_tutorial.html) provide implementations to apply these methods.

* *Nested Graph view:* If we consider a large neural network (like a Transformer with dozens of layers) as a graph, pruning can create “graph-of-graphs” structure by completely removing some sub-networks. For instance, pruning entire attention heads in a Transformer effectively treats each head as a subgraph and deletes some of them. Some research treats this as searching for a smaller subgraph within the big graph that can do the job – and RL or NAS (see below) can be used to find that subgraph.

**Quantization:** Quantization compresses a network by reducing the precision of weights and/or activations, effectively packing more information into fewer bits. It doesn’t remove graph components, but it compresses the data associated with edges/nodes (the weight values). A common practice is 8-bit quantization (down from 32-bit floating point), which gives 4× size reduction with usually minimal impact on accuracy. As of 2025, **4-bit and even 2-bit quantization** are being actively explored, especially for Transformer models, with advanced techniques to minimize accuracy loss. For example, the QLoRA method (2023) allowed fine-tuning large language models in 4-bit precision with performance almost equal to full precision. In the context of neural network graphs, quantization can be seen as compressing the “edge weights” of the graph. Even **binary neural networks** (1-bit weights) have been demonstrated on smaller models, achieving decent performance with massive compression (32× smaller weights)[\[22\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=With%20training%20time%20compression%20we,model%20size%20reduction%20over%20baseline)[\[23\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=palettized_model%20%3D%20palettizer). Quantization is often combined with pruning: one might prune 80% of weights and then quantize the remaining 20% to 8-bit, for a compounded compression. The Apple CoreML example above shows that a 1-bit per weight (with some clever palettization) ResNet-50 can still reach \>71% accuracy on ImageNet[\[23\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=palettized_model%20%3D%20palettizer) – over 15× size reduction for about 5 points drop in accuracy[\[23\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=palettized_model%20%3D%20palettizer). That’s a huge win for deployment on devices. Tools like NVIDIA’s TensorRT, Qualcomm’s AI Engine, and open libraries (ONNX Runtime, etc.) have built-in support for quantized models and can even do the quantization automatically with calibration data.

**Knowledge Distillation:** This is a “learning-based” compression where a large model (teacher) guides the training of a smaller model (student) to approximate the teacher’s function. The student model often has a compressed architecture (fewer layers or hidden units – effectively a smaller graph). Distillation has been extremely successful, especially in NLP. **DistilBERT** (Sanh et al. 2019\) compresses BERT-base (110M parameters) to a model with 40% fewer parameters (66M) while retaining *97% of BERT’s performance* on GLUE benchmarks[\[24\]](https://blog.tensorflow.org/2020/05/how-hugging-face-achieved-2x-performance-boost-question-answering.html#:~:text=How%20Hugging%20Face%20achieved%20a,of%20BERT%27s%20performance). It does this by training the smaller student to match the larger model’s outputs (logits or hidden states) on a large corpus, thus transferring knowledge. The result is a model that is much faster and lighter but nearly as good – a clear example of lossy compression (some nuances of the teacher are lost, but not many, as the metrics show[\[24\]](https://blog.tensorflow.org/2020/05/how-hugging-face-achieved-2x-performance-boost-question-answering.html#:~:text=How%20Hugging%20Face%20achieved%20a,of%20BERT%27s%20performance)). Distillation can also be applied to compress *ensemble* models into one, or compress a model into a different architecture. It’s widely used: e.g., compressing a big Transformer into a small one, or a ResNet into a MobileNet for mobile deployment. In graph terms, we start with a graph (teacher network), end with a smaller graph (student network) that has similar functionality. It’s somewhat akin to summarizing a graph’s function rather than its exact structure. Many official implementations exist (Hugging Face provides DistilBERT, DistilGPT-2, etc., and libraries like TensorFlow Lite and OpenVINO often rely on the idea of distillation to get efficient models).

**Neural Architecture Search (NAS) & Efficient Architectures:** NAS is about automatically finding network architectures that are optimized for a given task and perhaps hardware constraints. While not compression of a given model per se, NAS often discovers architectures that are *significantly smaller* (fewer nodes/edges in the graph) than brute-force designs while achieving equal performance. For example, EfficientNet (2019) was found via NAS and achieves better accuracy than much larger models by carefully balancing network depth, width, and resolution. One could view NAS as creating a *compressed architecture* that has no redundant parts. Recently, NAS has been combined with pruning in *one-shot NAS* or *lottery ticket NAS*, where an overcomplete super-network is trained and then a subnetwork (winning ticket) is selected. This again is treating the network as a graph and selecting an optimal subgraph to keep. In 2023-2025, there’s also interest in **Neural Architecture Compression** – taking a given trained network and searching for a smaller architecture that can reproduce it (some approaches use Meta-Learning or evolutionary algorithms for this). This is a bit like distillation but at structure level.

**Graph-of-Graphs view:** Modern deep learning systems are often **modular graphs** (e.g., a network with multiple branches, or a pipeline of multiple networks). Compressing such systems might involve compressing each component and also the connections between them. For instance, in a multi-modal model (one subgraph processes text, another processes images, then they combine), one could compress each modality’s model and also perhaps simplify the fusion mechanism. The *nested* aspect can also be seen in hyper-networks or compound networks (networks that generate other networks). Compressing those might involve first compressing the generated network without disturbing the generator, etc., but this is quite advanced and specific.

**Benchmarks for model compression:** These are straightforward – the standard benchmarks in vision (ImageNet, COCO, etc.), NLP (GLUE, SQuAD, etc.), speech (LibriSpeech), are used to ensure compressed models still perform well. There have also been **model compression challenges** (e.g., the MLPerf Tiny benchmarks, or competitions to compress models like BERT for on-device use). Performance metrics include accuracy drop, compression ratio (parameter count or memory size reduction), and inference speedup.

**Tools and Libraries:** The community has many tools for neural network compression. A few examples:  
\- **TensorRT** (NVIDIA) and **OpenVINO** (Intel) can take trained models and perform quantization and half-precision conversion, as well as some pruning.  
\- **TorchScript and ONNX** frameworks often incorporate optimizations that reduce model size (like constant folding and eliminating redundant nodes – a simple form of lossless compression at graph representation level).  
\- **Neural Magic’s DeepSparse** is a library specifically optimized to deploy sparsified (pruned) models efficiently on CPUs, taking advantage of high sparsity.  
\- **Hugging Face Transformers** provides many pre-pruned or distilled versions of popular models (e.g., distilbert-base-uncased as a ready-to-use smaller BERT).  
\- **AutoML tools** (like Google’s AutoAugment or Facebook’s NAS toolkits) can be used to search for smaller architectures.  
\- **Academic libraries**: Tencent's NCNN and Alibaba's MNN are example deployment frameworks heavily using quantization/pruning for mobile.

In practice, compressing neural network graphs is often an interplay of the above techniques: e.g., one might prune a network to 50% sparsity, quantize it to int8, and then distill its knowledge into a slightly smaller network to recover any lost accuracy. The end result could be, for instance, a model 1/10th the size and 5× faster with only 1% accuracy loss – an invaluable improvement for real-world applications.

## Benchmarks and Datasets for Graph Compression

Throughout this guide, we’ve touched on various benchmarks. Here we summarize some prominent ones used to evaluate graph compression methods:

* **Web Graph datasets:** These are commonly used for lossless compression tests. Examples include the *WebBase 2001* graph (118M pages, 1 billion links) used by Boldi & Vigna[\[5\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=centred%20around%20referentiation%20and%20intervalisation,89%20bits%20per%20link), the *UK-2002* and *UK-2007* web graphs (18M and 105M pages respectively) from the LAW (Laboratory for Web Algorithmics) repository, and the *ClueWeb12* or *Common Crawl* web graphs. Compression algorithms report bits per edge on these. For instance, WebGraph’s 3.08 bits/link on WebBase is a baseline[\[5\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=centred%20around%20referentiation%20and%20intervalisation,89%20bits%20per%20link); newer methods aim to meet or beat that. The *Facebook social graph* (one snapshot had \~60M nodes, \~1.5B edges) and *Twitter graph* (41M users, 1.2B follows) have also been used for compression evaluations.

* **Social and information networks:** SNAP and KONECT repositories provide many real graphs (e.g., *Pokec* social network, *LiveJournal* blog network, *DBLP* citation network, *Enron* email network). These often serve as testbeds for summarization and sparsification methods. For example, a summarization method might report how much it can reduce the LiveJournal graph (4M nodes, 34M edges) while preserving community structure, etc. An influence-based compression might be tried on the *Instagram follower graph* or *epi-genetic networks* where influence spread is key.

* **Knowledge Graphs:** Standard KGs for testing include *DBpedia* (hundreds of millions of triples), *Wikidata* (billions of triples), and smaller benchmarks like *BSBM* (Berlin SPARQL Benchmark) for synthetic data. The *LOD Laundromat* collection was often used to test HDT – it contains thousands of RDF datasets; HDT compressed the entire LOD cloud (billions of triples) into something like 500GB[\[25\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=Wiki%02data%20KG%20to%20an%20HDT,lot%5B9) which is remarkable. For ML tasks, subsets like *FB15k-237* (15k entities, 237 relations, 310k triples) and *WN18RR* (WordNet subset) are used for link prediction performance with compressed embeddings. The *ATOMIC* and *ConceptNet* KGs are used in NLP tasks – Hwang et al. (2023) use ConceptNet subgraphs and measure diversity/quality of text generation when those subgraphs are compressed. So their “benchmark” is a set of commonsense reasoning tasks (like explaining a counterfactual) where the model’s input knowledge graph is compressed and output quality is assessed.

* **Graph classification and regression benchmarks:** Datasets like *MUTAG, PROTEINS, NCI1* (small molecule graphs), *COLLAB, Reddit* (social graph datasets), and the newer *Open Graph Benchmark (OGB)* datasets (e.g., ogbg-molhiv for molecular graphs, ogbn-papers100M for a citation network) are used to benchmark GNN-based compression (pooling, graph coarsening for classification, etc.). For instance, the GNN summarization survey compares several pooling methods on PROTEINS and COLLAB to see which summary approach best preserves graph label information.

* **Large-scale graph analytics benchmarks:** There are graph processing benchmarks (Graph500, etc.) that include compressibility as a factor. For example, a system might compress a graph then run PageRank – the SuiteSparse Matrix Collection has some large graphs used to test how compression aids analytics. One specific benchmark is *Triangle counting on Twitter graph* – a lossy compression might be acceptable if it preserves triangle counts. Similarly, *shortest path queries on road networks* (e.g., the DIMACS graph dataset for USA road network) – compression schemes are tested if they can speed those up while giving exact or approximate answers.

* **Neural network compression benchmarks:** For model compression, the “benchmarks” are essentially standard ML tasks: ImageNet for image classification, COCO for object detection (with models like YOLO being compressed), GLUE for NLU tasks (with BERT or other transformers compressed), and MLPerf Tiny for tinyML scenarios. For example, one might demonstrate a pruning method by pruning ResNet-50 on ImageNet and reporting the top-1 accuracy drop[\[21\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=pruned_model%20%3D%20pruner). Or show a quantization method by quantizing BERT on SQuAD Q\&A and reporting the F1 score drop. In 2024, there was a lot of focus on compressing LLMs like *GPT-3 family* or *OPT* models – e.g., quantizing a 13B parameter model to 4-bit and evaluating perplexity on WikiText, or distilling chat models and evaluating on benchmarks like TruthfulQA. While these are ML benchmarks, they serve to measure the efficacy of compression.

In summary, evaluation of graph compression is multi-faceted: we care about compression ratio (bits per edge or % size reduction), *fidelity metrics* (how much error is introduced in queries or tasks), and *performance metrics* (speedup in query or training/inference time). A truly SOTA method should excel in all – e.g., drastically reduce size, while minimally affecting accuracy or query results, and ideally enabling faster processing due to the smaller size.

## Tools, Libraries, and Implementation Resources

To conclude, we list some **resources and tools** for those interested in applying graph compression or exploring these methods:

* **WebGraph** – Java library by Boldi & Vigna for compressing web-scale graphs and performing basic graph algorithms on the compressed form. Official site: [WebGraph Framework](http://webgraph.di.unimi.it/). It includes utilities to download some already-compressed web graphs and to compress your own using their techniques (referentiation, etc.)[\[6\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=techniques%20that%20delay%20the%20decompression,graph%2C%20so%20to%20experiment%20with).

* **RDF HDT** – Open-source tools for HDT format ([hdt-cpp](https://github.com/rdfhdt/hdt-cpp) in C++ and [HDT-Java](https://github.com/rdfhdt/hdt-java)). These allow converting RDF dumps to HDT, querying them with SPARQL triple patterns, and even updating HDT files. The HDT format is standardized and used in the Linked Data community for publishing compressed KGs[\[7\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=succinct%20data%20structures,triple%20pattern%20access%20that%20is).

* **Graph Grammar Compression (RePair variants)** – The authors of ITR (2024) might release code (the arXiv didn’t have a link at time of writing, but check the authors’ pages). Separately, an earlier tool by Maneth et al. (2018) for grammar-based graph compression might be available in research repositories (sometimes called *GraphRePair* or similar).

* **Graph Summarization Libraries:** There isn’t a de-facto “summarization library”, but many papers provide code. For example, the VoG motif compression code was released by the authors (Koutra et al.). The 2024 survey lists open-source tools – these include implementations of DiffPool, GraphSAGE (which can be used for embedding), and perhaps specific summarization methods like *SNAP Summarization*. Tools like NetworkX have some simplification functions (e.g., k-core, line graph, etc., which can be used to make a graph simpler). The *graphtool* library in C++/Python has efficient algorithms for k-core, motif finding, which help in manual compression.

* **Machine Learning Frameworks:** For ML-based approaches, **PyTorch Geometric (PyG)** and **Deep Graph Library (DGL)** are invaluable – they let you prototype GNNs (like autoencoders or DiffPool) with ease. PyG has examples for VGAE and for GraphPooling. There’s also a library called **PyGCoarsen** (from a 2020 paper on spectral coarsening) that can produce coarsened graphs in a differentiable way.

* **RL environments for graph compression:** Open Graph Gym (2022) is a framework for applying reinforcement learning on graph problems – one could adapt it for compression tasks like selecting edges to remove. Some authors of RL-based compression might share their environment setup (e.g., Cutter’s authors may share code on GitHub – it’s worth searching the arXiv title plus “GitHub”).

* **Neural Network Compression Tools:**

* *TensorFlow Model Optimization Toolkit* and *PyTorch FX Graph Mode Quantization* – both allow you to compress models via pruning and quantization with just a few lines of code. For example, PyTorch’s torch.nn.utils.prune module provides iterative pruning methods.

* *ONNX Runtime with Quantization* – you can take a model in ONNX format and apply post-training quantization easily. This is great for deploying models compressed without needing to retrain.

* *Neural Magic’s SparseML* – a library that integrates into training scripts to perform magnitude pruning and quantization-aware training, yielding highly sparse models that run efficiently on CPUs.

* *Hugging Face* – provides a library called *Transformer Distillation* (part of their Transformers lib, with examples like how DistilBERT was trained). They also host many compressed models on their model hub (search for “pruned” or “distilled”).

* *Academic Code* – e.g., the official implementation of DistilBERT is on GitHub (by Victor Sanh), many NAS algorithms have open-source (e.g., Facebook’s once-for-all NAS for EfficientNet is on GitHub). For quantization, the QLoRA code (Tim Dettmers et al. 2023\) is available, demonstrating 4-bit finetuning for LLMs.

* **Datasets and Benchmark Repos:** To experiment, one can fetch large graph datasets from:

* [SNAP](https://snap.stanford.edu/data) – many network datasets (social, web, collaboration, etc.).

* [KONECT](http://konect.cc) – large network datasets with a focus on open data.

* [OGB](https://ogb.stanford.edu) – standardized graph ML datasets (including a massive papers citation graph and protein networks).

* [WikiData Dumps](https://dumps.wikimedia.org/wikidatawiki/entities/) – for raw KG data (which you can try to compress with HDT or others).

* [SuiteSparse Matrix Collection](https://sparse.tamu.edu) – although for matrices, many are graph adjacency matrices useful for compression testing (includes web and social graphs in matrix form).

Finally, staying up-to-date: Graph compression is a lively field. The annual conferences like KDD, WSDM, VLDB, NeurIPS, ICLR often have latest papers on graph neural networks and compression. Workshops on Graph Representation Learning also cover new summarization techniques. As of 2025, one trend is combining large language models with graph compression (as seen by text-rich graph compression using LLMs, and using GPT-style models to assist in graph tasks). Another is the push for *theoretical limits* of graph compression, which might eventually guide practical tools (e.g., how compressible is a random graph with certain properties?). All told, the toolbox for graph and “graph-of-graphs” compression is richer than ever – spanning from information theory to deep learning – enabling us to manage today’s massive networks and knowledge graphs more efficiently than thought possible just a decade ago.

**Sources:** The information above synthesizes recent literature and tools, including academic papers[\[3\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=space%2C%20exploiting%20the%20inner%20redundancies,89%20bits%20per%20link)[\[4\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=representations%20that%20are%20easier%20to,), surveys[\[13\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,preserving%20condensed%20graphs.), and empirical results from 2023–2025. Notable references have been cited inline for further reading on specific methods and their evaluations.

---

[\[1\]](https://wachiyem-74351.medium.com/graph-compression-part-a-introduction-4f228fb26633#:~:text=Compression%20of%20large%20graphs%20has,2%2C%205) [\[2\]](https://wachiyem-74351.medium.com/graph-compression-part-a-introduction-4f228fb26633#:~:text=Whereas%20there%20exists%20an%20enormous,5) Graph Compression: — Part A: Introduction | by Martin Wafula | Medium

[https://wachiyem-74351.medium.com/graph-compression-part-a-introduction-4f228fb26633](https://wachiyem-74351.medium.com/graph-compression-part-a-introduction-4f228fb26633)

[\[3\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=space%2C%20exploiting%20the%20inner%20redundancies,89%20bits%20per%20link) [\[5\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=centred%20around%20referentiation%20and%20intervalisation,89%20bits%20per%20link) [\[6\]](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf#:~:text=techniques%20that%20delay%20the%20decompression,graph%2C%20so%20to%20experiment%20with) vigna.di.unimi.it

[https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf](https://vigna.di.unimi.it/ftp/papers/WebGraphI.pdf)

[\[4\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=representations%20that%20are%20easier%20to,) [\[9\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=Several%20graph%20compression%20approaches%20rely,several%20graph%20datasets%2C%20and%20our) [\[10\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=the%20set%20of%20their%20vertices,several%20graph%20datasets%2C%20and%20our) [\[12\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=i,16%5D.) [\[13\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,preserving%20condensed%20graphs.) [\[14\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=,) [\[15\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=sparsification%20,preserving%20condensed%20graphs.) [\[16\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=...%20Bit,14%5D.) [\[17\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=In%20this%20survey%2C%20we%20explore,the%20simplification%20of%20higher%20graphs) [\[18\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=understanding%20community%20organization%2C%20information%20flow%2C,Extensive%20experiments%20on%20social%20and) [\[19\]](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey#:~:text=...%20However%2C%20visualizing%20large,) Graph Summarization Methods and Applications: A Survey | Request PDF

[https://www.researchgate.net/publication/326028431\_Graph\_Summarization\_Methods\_and\_Applications\_A\_Survey](https://www.researchgate.net/publication/326028431_Graph_Summarization_Methods_and_Applications_A_Survey)

[\[7\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=succinct%20data%20structures,triple%20pattern%20access%20that%20is) [\[8\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=preserving%20the%20query%20capabilities,pattern%20access%20that%20is%20equal) [\[25\]](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf#:~:text=Wiki%02data%20KG%20to%20an%20HDT,lot%5B9) 2024.eswc-conferences.org

[https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf](https://2024.eswc-conferences.org/wp-content/uploads/2024/04/146640460.pdf)

[\[11\]](https://arxiv.org/html/2502.02477v1#:~:text=preserve%20the%20path%20information%2C%20it,these%20techniques%20achieve%20high%20compression) A Clique Partitioning-Based Algorithm for Graph Compression

[https://arxiv.org/html/2502.02477v1](https://arxiv.org/html/2502.02477v1)

[\[20\]](https://pmc.ncbi.nlm.nih.gov/articles/PMC9003471/#:~:text=gRDF%3A%20An%20Efficient%20Compressor%20with,based%20graph%20compression) gRDF: An Efficient Compressor with Reduced Structural Regularities ...

[https://pmc.ncbi.nlm.nih.gov/articles/PMC9003471/](https://pmc.ncbi.nlm.nih.gov/articles/PMC9003471/)

[\[21\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=pruned_model%20%3D%20pruner) [\[22\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=With%20training%20time%20compression%20we,model%20size%20reduction%20over%20baseline) [\[23\]](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html#:~:text=palettized_model%20%3D%20palettizer) Optimizing ResNet50 Model — Guide to Core ML Tools

[https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html](https://apple.github.io/coremltools/docs-guides/source/opt-resnet.html)

[\[24\]](https://blog.tensorflow.org/2020/05/how-hugging-face-achieved-2x-performance-boost-question-answering.html#:~:text=How%20Hugging%20Face%20achieved%20a,of%20BERT%27s%20performance) How Hugging Face achieved a 2x performance boost for ...

[https://blog.tensorflow.org/2020/05/how-hugging-face-achieved-2x-performance-boost-question-answering.html](https://blog.tensorflow.org/2020/05/how-hugging-face-achieved-2x-performance-boost-question-answering.html)