Grammar-Based Graph Compression

Sebastian Maneth; Fabian Peternek

Source-linked AI summary

Grammar-Based Graph Compression

Sebastian Maneth, Fabian Peternek

arXiv:1704.05254v1Apr 18, 2017cs.DS

TL;DR

Large graphs require compact representations that do not make useful queries prohibitively expensive. The paper generalizes RePair to graph grammars and develops query algorithms over the compressed representation, reporting compression advantages and compression-ratio-proportional speed-ups for selected queries.

Problem
Large graph data creates storage and transfer demands, while query evaluation over compressed representations can otherwise become more difficult.
Method
The paper recursively replaces repeated graph digrams with nonterminal edges in a straight-line hyperedge replacement grammar.
Results
Reachability is evaluated in O(|G|) time and regular path queries in O(|G||α|) time over the grammar, enabling speed-ups proportional to compression.
Takeaways & Limitations
Grammar compression can provide smaller graph representations while supporting selected reachability and regular path queries with compression-ratio-proportional speed-ups.
Takeaways & Limitations
The compressor restricts nonterminal edges to be attachment-distinct, which can weaken compression by preventing some shared representations.

Abstract

from arXiv · show

We present a new graph compressor that works by recursively detecting repeated substructures and representing them through grammar rules. We show that for a large number of graphs the compressor obtains smaller representations than other approaches. Specific queries such as reachability between two nodes or regular path queries can be evaluated in linear time (or quadratic times, respectively), over the grammar, thus allowing speed-ups proportional to the compression ratio.

1 Introduction

The paper generalizes RePair to graph compression, evaluates the resulting compressor, and develops query algorithms over compressed graphs. Its approach targets repeated graph substructures while addressing the difficulty of efficiently selecting non-overlapping digrams.

The paper generalizes the RePair compression scheme to graphs, experimentally evaluates it, and presents query-evaluation algorithms over compressed graphs.
Graph grammar compression represents repeated edge-based digrams with nonterminal edges and corresponding grammar rules.In the illustrated example, the original graph has size 11 and the resulting grammar has size 10.
A greedy linear-time counting procedure replaces exact most-frequent digram selection, whose known graph algorithm has quadratic time complexity.Node orders are varied experimentally, and a Weisfeiler–Lehman-inspired similarity order performs best in the reported experiments.
On network graphs, RePair combined with dense substructure removal gives the best compression for all but two graphs, while on RDF graphs it consistently beats k2-trees, sometimes by several hundredfold.
Reachability over a grammar-compressed graph is evaluated in O(|G|) time, while regular path queries are evaluated in O(|G||α|) time.These algorithms target particular queries because general CMSO evaluation can be too expensive for large graphs.
The paper extends an earlier conference version with new theoretical, experimental, grammar-formalism, and regular-path-query material.

2 Related Work

Related work spans grammar-based graph compression, succinct representations for web and RDF graphs, and query evaluation over compressed input. Existing methods differ in the structures they compress and the queries they natively support.

2 Related Work: The paper positions its method as a graph generalization of RePair within context-free hyperedge replacement grammars, following earlier string and tree compression work.
2.1 Succinct Graph Representations: Web-graph compressors exploit locality and similarity, often ordering nodes so similar adjacency lists become close or mergeable.
2.1 Succinct Graph Representations: Adjacency-list methods primarily support out-neighborhood queries, whereas k2-trees compress adjacency matrices and support both in- and out-neighborhood queries.
2.2 RDF Graph Compression: RDF compression commonly separates dictionaries from triples or encodes a separate adjacency matrix for each predicate.
2.3 Queries with Compressed Input: Compressed graph representations can avoid exponential query-time blow-ups, and some connectivity and reachability problems admit polynomial-time algorithms over hierarchical representations.

3 Preliminaries

This section defines the hypergraph and straight-line HR-grammar foundations used to represent graphs, derive unique graph values, and relate graph encodings to strings and trees.

3 Preliminaries: A hypergraph consists of ranked labeled edges attached to nodes, with external nodes defining its rank and internal nodes comprising the remaining vertices.The formalism prohibits repeated nodes within an edge or within the external-node sequence, and distinguishes simple rank-two edges from general hyperedges.
3 Preliminaries: An HR grammar replaces nonterminal edges with matching-rank right-hand-side hypergraphs, while a straight-line grammar gives each nonterminal one rule and prevents cyclic dependencies.Straight-line grammars also exclude unreachable rules and define a unique right-hand side for every nonterminal.
3.1 Creating Graphs with Unique Node IDs: A canonical node-renaming and preorder derivation of the derivation tree produces one uniquely identified graph val(G) from an otherwise isomorphism-based grammar language.The prescribed renaming assigns fresh identifiers to internal nodes, while sibling ordering fixes the order of nonterminal derivations.
3.2 String- and Tree-Graphs: Strings are encoded as rank-two hypergraph paths with external endpoints, while tree nodes become ordered hyperedges whose rank records the parent and children.The string encoding has size 2|w| + 1; tree encodings range from 2|t|+2 to 3|t|+2 depending on node arity.

4 GraphRePair

GraphRePair generalizes the RePair compression scheme from strings and trees to graphs.

4 GraphRePair: GraphRePair generalizes the RePair compression scheme to graphs.

4.1 RePair Compression Scheme for Strings and Trees

This section reviews RePair as a repeated-digram replacement scheme for strings and trees, including grammar-size effects, linear-time implementation, pruning, and rank constraints.

4.1 RePair Compression Scheme for Strings and Trees: RePair repeatedly replaces all non-overlapping occurrences of the most frequent digram, producing a grammar approximation because finding the smallest grammar is NP-complete.For strings, overlapping occurrences arise only for digrams of the form aa.
4.1 RePair Compression Scheme for Strings and Trees: A string example reduces size from |w| = 9 to grammar size 7 after replacing frequent digrams.
4.1 RePair Compression Scheme for Strings and Trees: The string implementation maintains linked lists and a priority queue of active digrams to select the most frequent digram in constant time and achieve linear overall runtime.The queue uses √n frequency buckets, with the final bucket holding digrams occurring at least √n times.
4.1 RePair Compression Scheme for Strings and Trees: Pruning removes nonterminals referenced only once, reducing grammar size when possible but never increasing it.
4.1 RePair Compression Scheme for Strings and Trees: TreeRePair defines digrams as parent-child node pairs, uses parameters for dangling edges, and exposes a user-defined maxRank parameter.Rank controls the number of dangling edges and affects later algorithms, so keeping it small is desirable.

4.2 RePair on Graphs

GraphRePair represents graph digrams as pairs of incident edges, defines valid occurrences and replacements in HR grammars, and approximates maximal non-overlapping selection through node ordering.

4.2 RePair on Graphs: GraphRePair uses two edges sharing at least one node as a digram because node-neighbor replacements fail to compress basic cycles.
4.2 RePair on Graphs: A graph digram occurrence is an isomorphic two-edge subgraph whose external nodes correspond exactly to attachment nodes incident with edges outside the occurrence.Occurrences are classified as overlapping when they share nodes; a digram is active when it has at least two non-overlapping occurrences.
4.2 RePair on Graphs: Different HR-grammar representations can generate the same graph while having different sizes, such as sizes 12 and 9 for two example grammars.
4.2 RePair on Graphs: The compressor chooses digrams with the largest number of non-overlapping occurrences, but exact selection is approximated by traversing graph nodes in a chosen order.The node order strongly influences compression behavior because greedy counting can fail to find a maximal non-overlapping set.
4.2 RePair on Graphs: Replacing an occurrence removes its two edges and removal nodes, then adds a nonterminal edge attached so that expanding its rule reconstructs the original graph.

4.3 The Algorithm

gRePair repeatedly replaces frequent non-overlapping digram occurrences, approximating maximal selection when exact matching is too expensive, then prunes grammar rules. Its compression depends on traversal choices and pruning order.

4.3 The Algorithm: gRePair runs a replacement loop over digram occurrence lists, optionally reconnects components with virtual edges, and prunes afterward.The algorithm outputs a grammar whose value represents the input graph and whose size is bounded by the graph size.
4.3.1 Counting Occurrences (Step 3): O(m^4) exact selection is possible via maximum matching, but its cost motivates an order-based approximation for choosing non-overlapping occurrences.All occurrences may number O(m^2), so constructing and matching the occurrence graph is prohibitively expensive.
4.3.1 Counting Occurrences (Step 3): The node traversal order changes the selected occurrence set: a jumping order finds four occurrences in the example, whereas other traversals find three.The implementation provides four node-order choices because order strongly influences compression behavior.
4.3.2 Updating Occurrence Lists (Step 10): After replacements, affected occurrence lists are updated using label-indexed edge lists, giving O(|Σ|) selection time per update.For labeled graphs, initial occurrence construction takes O(|Σ|^2) time when |Σ| is small.
4.3.3 Pruning: Pruning removes nonterminals with nonpositive contribution, but contribution changes as rules are removed, so the removal order affects final grammar quality.Rules referenced once are removed first; remaining nonterminals are considered in bottom-up order.

4.4 Relation to Compression of Strings and Trees

The graph compressor generalizes RePair beyond strings and trees while preserving useful relationships to those formalisms. For tree-generating grammars, line-structures guide a conversion to tree-graph rules with at most a factor-two size increase.

4.4 Relation to Compression of Strings and Trees: With a left-to-right node order, gRePair reproduces the digram sequence of string RePair and therefore encodes the same string grammar.For trees, experiments report compression ratios comparable to TreeRePair within the same order of magnitude.
4.4 Relation to Compression of Strings and Trees: SL-HR grammars can share repeating disconnected subgraphs, but every grammar representing a tree or string can be converted to one whose right-hand sides are tree-like with limited overhead.The conversion addresses the greater expressive power of graph grammars while retaining the represented tree or string.
4.4 Relation to Compression of Strings and Trees: A line-structure records reachability between external nodes through internal paths and exposes the structure needed to split nonterminal edges into tree-graphs.For tree-generating grammars, each line-structure is a rooted forest, although a right-hand side may still contain cycles or multiple parents through nonterminal edges.
4.4 Relation to Compression of Strings and Trees: The conversion orders external nodes consistently, splits disconnected components, and removes internal external nodes so that every right-hand side becomes a tree-graph.The construction may add nonterminals and can increase size when an external node appears in multiple split graphs.
4.4 Relation to Compression of Strings and Trees: The resulting grammar has size at most twice the original grammar size.The factor two arises because splitting can at worst double node and edge sizes.

4.5 Important Parameters

gRePair exposes node order and maximal digram rank as major compression parameters. Node-order choices alter occurrence selection, while rank limits can determine whether structured graph families compress effectively or not at all.

4.5.1 Node Order: The compressor evaluates natural, BFS, FP, and FP0 node orders, with order choice affecting digram counting and compression behavior.Natural order uses node IDs; BFS uses breadth-first traversal; FP reaches a neighborhood-coloring fixpoint; FP0 orders by degree.
4.5.1 Node Order: FP iteratively refines node colors from degrees and sorted neighbor colors until reaching a fixpoint, whose equivalence classes correlate with compression ratio.The resulting coloring need not be a strict order, so an admissible order is chosen within tied classes.
4.5.2 Maximal Rank: A maximal rank that is too small or too large can strongly affect compression because only digrams within the rank limit are counted.Higher-rank digrams may be ignored when the limit is low, while unrestricted rank can favor structurally unhelpful replacements.
4.5.2 Maximal Rank: If the maximal rank is at least k, gRePair compresses gn,k to O(k^2 + n), but it does not compress when the rank limit is below k.The low-rank failure occurs because gn,k contains no digram of smaller rank.
4.5.2 Maximal Rank: For Tn, restricting maximal rank to 2 yields grammar size O(n), whereas unbounded rank compresses at best to 75% of the original size.The restricted setting enables subsequent string-graph compression; unrestricted rank leaves many start-graph nodes unshared.
4.5.2 Maximal Rank: For the illustrated family, pruning cannot improve the compression ratio beyond 3/4 because start-graph nodes and terminal edges remain.This differs from TreeRePair’s 50% bound because graph size counts both nodes and edges.

4.6 Implementation Details

The implementation maintains active digram occurrences with linked structures and stores graphs through label-specific k2-tree encodings. Productions use compact edge-list encodings that preserve external-node and attachment information.

4.6.1 Data Structures: Occurrences are stored in doubly linked lists for active digrams, while a priority queue ranks digrams by frequency and has length √n.Here n denotes the number of edges in the original input graph.
4.6.2 Grammar Representation: The start graph is encoded with k2-trees, using adjacency matrices for rank-2 labels and incidence matrices for higher-rank edges.Separate subgraphs are encoded for each edge label.
4.6.2 Grammar Representation: Incidence matrices record which nodes attach to each hyperedge, while stored permutations recover the ordered attachment relation.The number of distinct permutations determines the fixed-length encoding used for the permutation list.
4.6.2 Grammar Representation: Productions use variable-length δ-coded edge lists, with bits marking external nodes and terminal versus nonterminal edges.The encoding also stores attachment-node IDs, edge counts, and labels.
4.6.2 Grammar Representation: The example production encoding occupies 28 bits.This size is reported for the production associated with the example grammar.

4.7 On the Choice of Grammar Formalism

The paper chooses context-free hyperedge replacement grammars for gRePair while contrasting them with more expressive node replacement grammars and their compression trade-offs. It also examines distinctness restrictions, showing that ext-distinctness can reduce grammar size whereas att-distinctness may weaken compression.

4.7 On the Choice of Grammar Formalism: Hyperedge replacement grammars are the formalism used for gRePair, with the paper also discussing why alternative replacement methods and hypergraph restrictions matter.
4.7.1 Hyperedge vs. Node Replacement: Context-free graph grammars include hyperedge replacement (HR) and node replacement (NR) grammars.
4.7.1 Hyperedge vs. Node Replacement: NR grammars are strictly more expressive than HR grammars, including the ability to describe all complete graphs, while equivalent SL-NR grammars can simulate SL-HR grammars with similar size.
4.7.1 Hyperedge vs. Node Replacement: NR derivations use connection relations that specify which rule nodes connect to nodes in the nonterminal’s neighborhood.
4.7.1 Hyperedge vs. Node Replacement: Applying RePair to NR grammars is unresolved because connection relations make digram occurrences more specific, potentially incompatible, or rare.
4.7.1 Hyperedge vs. Node Replacement: An SL-NR grammar can generate a complete graph C_n with 2^n nodes using grammar size O(n), although the corresponding HR lower-bound claim remains unproved.
4.7.2 On the Conditions (C1) and (C2): The formalism imposes att-distinctness and ext-distinctness, requiring edge attachments and external-node strings to contain no repeated node.
4.7.2 On the Conditions (C1) and (C2): Ext-distinctness preserves the generated graph language and can strictly reduce grammar size, whereas att-distinctness may prevent smaller grammars from representing the same graph.

5 Experimental results

The experiments evaluate a Scala prototype of gRePair on network, RDF, and version graphs under different parameter and node-order settings. They identify maxRank = 4 and FP-order as generally effective choices, while emphasizing that prototype implementation and ordering affect measured compression.

5 Experimental results: The evaluation omits runtime and peak-memory comparisons because the prototype implementation could be substantially improved.
5 Experimental results: Node order changes compression results for all compared compressors, and the experiments use natural order for final start-graph encoding to maintain comparability.
5.1 Datasets: The prototype experiments use network, RDF, and version graphs, report compression in bits per edge, and compare against k2-tree, LM, and HN compressors.
5.1 Datasets: The datasets include communication, web, and co-authorship networks; DBpedia-based and other RDF graphs; and version graphs formed from repeated graph snapshots.
5.2 Influence of Parameters: The parameter study varies maximum nonterminal rank and node order while holding other parameters fixed, so individual runs may not attain the compressor’s best possible result.
5.2.1 Maximum Rank: maxRank = 4 achieves the best average compression across the tested graph classes, while higher values up to 16 perform worse.
5.2.2 Node Order: FP-order performs best on almost all selected graphs, has marginal impact on most RDF graphs, and benefits version graphs substantially.
5.2.2 Node Order: Graphs with fewer ∼=FP equivalence classes generally compress better, consistent with the presence of more repeating substructures.

5.3 Comparison with other Compressors

Across network, RDF, and version graphs, gRePair achieves substantial compression, with especially strong results for structured RDF and repeated version graphs. Its performance depends on graph structure and ordering, and dense-substructure preprocessing can improve network results.

5.3 Comparison with other Compressors: gRePair achieves average compression ratios of 68% for network graphs, 35% for RDF graphs, and 24% for version graphs.
5.3.1 Network Graphs: On network graphs, gRePair improves over plain k2-tree on all graphs except NotreDame but is often slightly worse than LM and HN.
5.3.1 Network Graphs: Combining dense substructure removal with gRePair generally improves network compression and yields the smallest bpe values for two of three CA-graphs.
5.3.2 RDF Graphs: On RDF graphs, gRePair greatly improves over k2-tree and can produce representations orders of magnitude smaller for graphs dominated by star-shaped, tree-like structures.
5.3.3 Version Graphs: For repeated identical copies of simple graphs, gRePair provides exponential compression and becomes orders of magnitude smaller than other compressors as copies increase.
5.3.3 Version Graphs: Exponential compression is not expected for most version graphs because changes between versions can prevent consistent reuse of nonterminals.
5.3.3 Version Graphs: FP-order improves compression on version graphs by similarly ordering repeated graph versions, outperforming alternative orders in the DBLP co-authorship experiment.

5.4 Results on Synthetic Graphs

Synthetic graph experiments show that compression depends strongly on graph family, maximal digram rank, and node order, with some graphs admitting exponential compression.

Overall findings: Some synthetic graphs can be compressed exponentially, while compression quality varies substantially with maximal rank and node order.The experiments evaluate grid and triangle-fractal families across graph sizes, traversal orders, and maxRank values.
Triangle fractals: For triangle fractals, maxRank = 2 gives the best compression, while FP-order remains near-optimal at maxRank = 4.Higher ranks can introduce more competing digram choices, making the result depend on node order.
Experimental setup: Table 7 reports compression ratios for triangle-fractal and grid graphs across multiple sizes, four node orders, and four maxRank settings.The reported ratio is measured relative to the paper’s graph-size definition.
Triangle fractals: Triangle-fractal compression is highly order-sensitive: FP preserves strong results, whereas BFS can miss the optimum even at maxRank = 2.The authors attribute this sensitivity to the different sets of non-overlapping digram occurrences found under each order.
Grid graphs: Grid graphs show the opposite rank behavior: unbounded rank compresses best, whereas maxRank = 2 yields almost no compression regardless of node order.For n = 12, unbounded rank gives 34% with FP and 12% with natural order, while FP0 gives close to no compression.
Grid graphs: Grid compression reflects traversal structure: natural order reaches 12% for n = 12, while BFS also performs well because both follow row-oriented patterns.For grid12 with BFS and unbounded maxRank, the rank was capped at 1500 because unrestricted computation took too long.

6 Query Evaluation

This section develops query-evaluation methods over SL-HR grammars, distinguishing neighborhood queries that require partial decompression from speed-up queries evaluated directly on the grammar. It establishes grammar-based procedures for reachability, CMSO properties, and regular path queries, including product-grammar constructions for compressing automaton runs.

6.1 Neighborhood Queries: Neighborhood queries enable graph traversal and arbitrary algorithms, but partial decompression causes slowdown relative to uncompressed representations; node neighbors are computed in O(νn) time.Here n is the represented node’s in- or out-degree, and ν denotes the grammar-representation runtime under alternative preprocessing choices.
6.1.1 Speed-Up Queries: Speed-up queries run bottom-up over the grammar: fixed CMSO properties are decidable in O(|G|η) time, with η determined by right-hand-side evaluation complexity.The derivation DAG preserves the information needed for bottom-up computation without explicitly constructing a potentially exponential derivation tree.
6.1.1 Speed-Up Queries: CMSO-definable functions evaluated with similar complexity include connected-component counts, simple-cycle and simple-path counts, and extremal degree or cycle-length measures.The specific complexity depends on the function and its right-hand-side evaluation bound.
6.2 Reachability Queries: Reachability between two nodes can be decided in O(|G|) time by computing nonterminal skeleton graphs bottom-up and testing reachability in the resulting start-graph structure.The method first represents the queried nodes, computes each nonterminal’s skeleton, and then propagates reachable external-node sets through the derivation paths.
6.3 Regular Path Queries: Regular path queries are generalized by constructing a grammar for the product of the graph transition system and the query NFA, then applying grammar-based reachability.Nodes are extended with automaton states, while renamings preserve the state component and update only node IDs.
6.3 Regular Path Queries: The product construction represents every accepting automaton run on graph paths while preserving a compressed SL-HR grammar representation.Given grammar G and NFA A, the product grammar is computable in O(|G||A|) time and has size O(|G||A|).
6.3 Regular Path Queries: O(|α||G|) time decides whether nodes u and v in val(G) satisfy regular path query α.The method constructs an NFA for α, forms the product grammar, and applies reachability from (u, qi) to (v, qf).
6.3 Regular Path Queries: For a40 and a five-state NFA accepting lengths divisible by five, the direct product has 205 states whereas the grammar product has 95 states.Replacing nonterminals with their 20-state skeleta immediately exposes an accepting run between nodes 0 and 40.
6.3 Regular Path Queries: O(|α||G|) time decides whether any node pair in val(G) satisfies regular path query α.A bottom-up analysis tracks external nodes reachable from initial states and those reaching final states, detecting an intersection or start-to-target path.
6.3 Regular Path Queries: The constructions generalize straightforwardly to hypergraphs by treating a rank-k labeled hyperedge as k−1 directed labeled edges from its first attachment node.The suggested transition-system semantics use one source node and multiple target nodes.

7 Conclusions

The paper generalizes RePair to graph compression, evaluates the resulting SL-HR grammar compressor, and develops speed-up algorithms for queries over compressed graphs.

The paper generalizes RePair to produce straight-line hyperedge replacement grammars and shows that grammar rank can heavily influence compression behavior.For strings and trees, SL-HR grammars cannot compress much better than native string or tree grammars.
The graph RePair compressor achieves the best compression on RDF graphs, sometimes by several orders of magnitude, and on version graphs, while results on network graphs are inconclusive.The compressor sometimes outperforms competing compressors on network graphs, but no consistent winner emerges there.
Finding a maximum non-overlapping digram is computationally hard for graphs, so the implementation uses a traversal-order-dependent greedy approximation.The experiments identify a node-degree-based order, similar to one used in the Weisfeiler-Lehman test, as giving the best compression results.
The paper gives speed-up algorithms for reachability and regular path queries whose gains can scale with the grammar's compression ratio.It also detects whether any node pair has a path matching a regular expression, even without specifying the pair beforehand.
Future work includes implementing the query algorithms, exploring alternative node orders and node-replacement grammars, and studying isomorphism complexity for SL-HR grammars.The authors note that node-replacement grammars can compress some graphs more strongly but have more complex and expensive rules.