PaperlayerView exact revision on arXiv

Source-linked AI summary

SLUGGER: Lossless Hierarchical Summarization of Massive Graphs

Kyuhan Lee, Jihoon Ko, Kijung Shin

arXiv:2112.05374v1cs.DBcs.SI

TL;DR

Massive graphs require compact lossless representations, while conventional graph summarization cannot fully exploit their hierarchical structure because supernodes are disjoint. The paper introduces hierarchical graph summarization and SLUGGER, which greedily constructs concise exact summaries with scalable acceleration. Across 16 real-world graphs, SLUGGER improves compression by up to 29.6%, scales linearly with edge count, and summarizes a graph with 0.8 billion edges in a few hours.

  • Problem

    Massive graphs make efficient lossless storage important, but conventional graph summarization cannot fully exploit pervasive hierarchical structures because its supernodes are disjoint.

  • Method

    The paper introduces hierarchical graph summarization with nested supernodes and positive and negative edges, then uses SLUGGER to greedily minimize encoding cost with sampling, approximation, and memoization.

  • Results

    Up to 29.6% more concise representations than the best competitors, linear scalability with graph size, and successful summarization of graphs with up to 0.8 billion edges.

  • Takeaways & Limitations

    Hierarchical graph summarization can produce concise exact representations while retaining graph outputs that support partial decompression and downstream graph processing.

Abstract

from arXiv · show

Given a massive graph, how can we exploit its hierarchical structure for concisely but exactly summarizing the graph? By exploiting the structure, can we achieve better compression rates than state-of-the-art graph summarization methods? The explosive proliferation of the Web has accelerated the emergence of large graphs, such as online social networks and hyperlink networks. Consequently, graph compression has become increasingly important to process such large graphs without expensive I/O over the network or to disk. Among a number of approaches, graph summarization, which in essence combines similar nodes into a supernode and describe their connectivity concisely, protrudes with several advantages. However, we note that it fails to exploit pervasive hierarchical structures of real-world graphs as its underlying representation model enforces supernodes to be disjoint. In this work, we propose the hierarchical graph summarization model, which is an expressive graph representation model that includes the previous one proposed by Navlakha et al. as a special case. The new model represents an unweighted graph using positive and negative edges between hierarchical supernodes, each of which can contain others. Then, we propose Slugger, a scalable heuristic for concisely and exactly representing a given graph under our new model. Slugger greedily merges nodes into supernodes while maintaining and exploiting their hierarchy, which is later pruned. Slugger significantly accelerates this process by sampling, approximation, and memoization. Our experiments on 16 real-world graphs show that Slugger is (a) Effective: yielding up to 29.6% more concise summary than state-of-the-art lossless summarization methods, (b) Fast: summarizing a graph with 0.8 billion edges in a few hours, and (c) Scalable: scaling linearly with the number of edges in the input graph.

I. INTRODUCTION

Massive graphs make efficient lossless storage important, but conventional graph summarization cannot fully exploit their pervasive hierarchical structure because supernodes are disjoint. SLUGGER addresses this with a hierarchical representation and scalable summarization algorithm.

  • Motivation: Massive social, hyperlink, and curation graphs make storage efficiency critical because conventional processing can incur disk or network I/O delays.Examples include networks with tens or hundreds of billions of connections or edges.
  • Existing approach: Conventional graph summarization combines similarly connected nodes into supernodes, encodes their connectivity and exceptions, and supports further compression and partial on-the-fly decompression.Its outputs remain graphs and can support algorithms without fully decompressing the representation.
  • Limitation: Because conventional supernodes must be disjoint, the model has limited expressive power for exploiting hierarchical and overlapping structures found in real-world graphs.Each node must belong to exactly one supernode, limiting hierarchical compression.
  • Contributions: The hierarchical graph summarization model allows supernodes to contain smaller supernodes and represents graphs with positive and negative edges, while including the previous model as a special case.An edge exists exactly when positive representations outnumber negative representations between the supernodes containing its endpoints.
  • Contributions: SLUGGER greedily merges nodes while maintaining and later pruning hierarchy, using sampling, approximation, and memoization to summarize graphs exactly and scale linearly with edge count.It seeks concise representations consisting of supernodes, positive edges, and negative edges.
  • Contributions: SLUGGER outperformed 4 state-of-the-art summarization methods on 16 real-world graphs, achieving up to 29.6% better compression while summarizing a graph with 0.8 billion edges within a few hours.The experiments substantiate its effectiveness, speed, and scalability.

B. Hierarchical Graph Summarization Model

The hierarchical graph summarization model allows nested supernodes connected by positive, negative, and hierarchy edges, generalizing the previous disjoint-supernode model. Lossless summarization minimizes the number of these edges, and SLUGGER heuristically searches for concise exact representations.

  • Hierarchical Graph Summarization Model: Nested supernodes let the model represent hierarchical structures that the previous disjoint-supernode model cannot exploit.Supernodes may contain smaller supernodes, forming a forest rather than a partition into disjoint groups.
  • Hierarchical Graph Summarization Model: Positive edges encode connections between all relevant subnode pairs, while negative edges encode their absence; an ordinary edge exists when positive evidence exceeds negative evidence.The model also uses directed hierarchy edges to represent containment relationships.
  • Hierarchical Graph Summarization Model: The model strictly improves representational conciseness on one constructed graph: it uses o(n1.5) edges, whereas the previous model cannot use o(n1.5).Theorem 1 formalizes this separation between the hierarchical and previous models.
  • Problem Definition: The lossless problem minimizes Cost(G) = |P +| + |P −| + |H| because encoding bits are roughly proportional to the summary's edge count.The input is represented exactly by a hierarchical summary graph, and the computational hardness of this problem remains open.
  • SLUGGER: SLUGGER greedily merges supernodes while updating hierarchy, positive, and negative edges, then accelerates search with memoization, sampling, and approximation before pruning unhelpful supernodes.It is a scalable heuristic for minimizing the encoding cost without information loss.

A. Cost Functions of SLUGGER

SLUGGER decomposes encoding cost into hierarchy and inter-supernode edge costs, then uses root-level and root-pair costs to guide merging decisions.

  • Cost decomposition: SLUGGER divides encoding cost into hierarchy cost CostH(G) and p-/n-edge cost CostP(G).CostH(G) counts hierarchy edges, while CostP(G) counts positive and negative edges.
  • Hierarchy costs: The hierarchy cost is partitioned by root nodes, using each root and its descendants to account for h-edges.The root-node set R and descendant sets SX define the relevant hierarchy components.
  • Pruning: After merging, SLUGGER prunes the hierarchical model to reduce encoding cost while retaining the represented graph.The pruning operation is the final step in the algorithm overview.
  • Edge costs: The p-/n-edge cost is partitioned by unordered root-node pairs, counting edges between their associated supernode sets.Additional root-level costs count p-edges and n-edges incident to each supernode.
  • Decision costs: SLUGGER uses root-node and root-pair costs to make merging decisions within its greedy-search procedure.The algorithm overview initializes the hierarchical model and repeatedly updates it through merging and pruning.

B. Description of SLUGGER

SLUGGER alternates candidate generation and greedy hierarchical merging, updating local encodings efficiently before pruning supernodes that do not improve succinctness.

  • Overview: SLUGGER alternates candidate generation and merging for T iterations, then prunes the resulting hierarchical graph summarization.It initializes singleton supernodes and exact edge encodings before repeatedly merging supernodes.
  • Candidate Generation Step: Candidate sets restrict merging to nearby root nodes, because pairs at distance three or larger increase encoding cost.Root nodes within distance 2 are grouped using min-hashing, with candidate sets capped at 500 nodes.
  • Merging Step: Within each candidate set, SLUGGER greedily selects root-node pairs using an encoding-cost ratio and merges pairs exceeding a decreasing threshold.The threshold starts high to prioritize larger reductions and decreases across iterations.
  • Update of encoding: When root nodes merge, SLUGGER locally updates p-edges and n-edges within the merged nodes and descendants, then updates edges to connected root nodes.The local search considers at most seven supernodes in one case and uses memoized best encodings for constant-size input configurations.
  • Pruning Step: Pruning removes supernodes whose incident hierarchy and edge encodings can be replaced while decreasing total cost without changing the represented graph.The first pruning substep removes non-leaf nodes without incident p- or n-edges and reconnects their hierarchy edges.

C. Complexity Analysis

SLUGGER has linear space complexity and O(T · |E|) time complexity under the stated |V| = O(|E|) assumption, with constant-time memoization.

  • Time complexity: SLUGGER’s overall time complexity is O(T · |E|), because candidate generation, merging, and pruning each take O(|E|) time.The algorithm repeats candidate generation and merging T times, while memoization takes O(1) time.
  • Space complexity: SLUGGER’s overall space complexity is O(|E|), matching the lower bound imposed by storing the input graph.The input graph makes the space requirement at least O(|E|), and the analysis gives the same upper bound.

IV. EXPERIMENTS

Experiments on 16 real-world graphs compare SLUGGER with state-of-the-art summarizers across compactness, speed, scalability, and implementation settings.

  • Experimental scope: The study evaluates six research questions covering compactness, speed and scalability, iteration effects, pruning, hierarchy height, and output composition.The experiments were conducted on 16 real-world graphs after removing directions, duplicate edges, and self-loops.
  • Experimental settings: Experiments ran on a 3.8 GHz AMD Ryzen 3900X desktop with 128GB memory using implementations of SLUGGER and four state-of-the-art summarization methods.SLUGGER used T = 20 unless otherwise stated, while competitor-specific parameters were fixed as reported.
  • Q1. Compactness: SLUGGER produced the most concise representations on all 16 datasets, including a 29.6% smaller representation than the best competitor on Protein.The experiments compare output representation sizes using the defined relative-size metric and average results over five trials.
  • Q2. Speed and Scalability: SLUGGER scaled linearly with input graph size in experiments using sampled UK-05 graphs.This empirical result agrees with the linear-time analysis presented for the algorithm.
  • Q2. Speed and Scalability: SLUGGER had speed comparable to SWEG, was faster on 7 of 16 datasets, and was among the only methods to summarize the approximately 0.8-billion-edge graph.Only SLUGGER and SWEG successfully summarized the largest graph; other competitors exceeded time or memory limits or failed.

D. Q3. Effects of Iterations

Increasing SLUGGER’s iteration count made representations more concise, with compression rates nearly converging after 40 iterations. Additional pruning substeps and greater allowable hierarchy height also reduced output size while increasing hierarchy depth.

  • D. Q3. Effects of Iterations: After 40 iterations, SLUGGER’s compression rates almost converged as output representations became progressively more concise.The experiment varied T from 1 to 80 across 16 datasets.
  • D. Q3. Effects of Iterations: Every pruning substep reduced representation size, maximum hierarchy-tree height, and average leaf depth, supporting the pruning design.
  • D. Q3. Effects of Iterations: SLUGGER’s hierarchy can range up to height |V| − 1, unlike competitors whose hierarchy height is at most 1.
  • D. Q3. Effects of Iterations: Allowing taller hierarchy trees increased average leaf depth while decreasing the relative output size.The height-constrained variant prevented merges that would exceed the upper bound Hb.

VII. APPENDIX: PROOFS

The appendix proves properties of the hierarchical representation by bounding the encoding costs that arise when large supernodes and their interconnections are represented. The argument derives a contradiction from assuming that the previous model can achieve an overly small representation.

  • Proof structure: The appendix establishes its claims through intermediate lemmas about supernode connectivity and encoding-cost lower bounds.The supplied proof passages include the theorem proof setup, cost decomposition, and consequences of the connectivity lemma.
  • Lemma 6: If a supernode contains at least 8k subnodes, it must have a positive edge to every supernode.The proof uses the bound on non-neighbors of each subnode and compares missing-edge and present-edge encoding costs.
  • Proof of Theorem 1: Assuming the previous model represents the graph with O(nk) edges leads to a lower-bound contradiction from many supernode pairs with complete nonzero connectivity.The proof counts at least Ω(n) suitable supernodes and derives an overall encoding cost in Ω(n^1.5).

C. Proof of Lemma 2

The complexity proof bounds SLUGGER’s candidate-generation, merging, and pruning costs by graph size, supporting linear-time processing in the number of edges.

  • Candidate generation: Candidate generation takes O(|V| + |E|) = O(|E|) time.Hashing nodes, computing shingles while scanning edges, and grouping equal shingles yield this bound.
  • Merging: The merging step computes savings over candidate sets whose size is bounded by a constant, with cost determined by incident descendant edges.Processing a candidate set D takes O(|D|^2 · Σ deg(v)) time, and |D| is constant.
  • Pruning: The worst-case pruning steps take O(|H| + |V|) = O(|E|) time, with encoding costs computed from p/n-edges and subedges.The proof contrasts the previous representation’s edge-access cost with the current representation’s p-edge cost.

F. Proof of Lemma 5

The pruning procedure operates on a hierarchical graph summary and root-node set, iteratively examining nodes and updating positive edges during pruning.

  • Pruning procedure: The pruning algorithm initializes its queue with root nodes and examines randomly selected nodes for removable or updateable connectivity.The pseudocode uses hierarchy membership and positive or negative edge tests to decide whether to modify the representation.
  • Edge updates: A pruning update replaces a positive edge with the appropriate difference between candidate connections and negative edges.The pseudocode explicitly updates P+ using D \ P− after removing the original positive edge.

B. Pseudocode for Partial Decompression

Algorithm 4 retrieves a node’s one-hop neighbors from the hierarchical summary without decompressing the entire model. Across 16 datasets, retrieval stayed below 15 microseconds and below 4 microseconds on 12 summary graphs.

  • Algorithm 4 retrieves neighbors through partial decompression rather than fully decompressing the hierarchical summary.The retrieval time was strongly correlated with the average depth of leaf nodes, although the supplied passage does not specify the direction of that correlation.
  • Retrieving a node’s neighbors took less than 15 microseconds on every hierarchical summary graph.
  • Retrieval took less than 4 microseconds on 12 of the 16 hierarchical summary graphs.

C. Graph Algorithms on a Hierarchical Summary Graph

Hierarchical summary graphs support graph algorithms by retrieving neighbors through on-the-fly partial decompression. This interface lets several standard algorithms run directly on summaries with no or minimal changes.

  • Graph access: Standard algorithms access the input graph primarily by retrieving a node’s neighbors.The passage identifies DFS and PageRank as examples whose graph access occurs at their neighbor-retrieval steps.
  • Graph algorithms: Hierarchical summaries can execute BFS, PageRank, Dijkstra’s, and triangle counting through on-the-fly partial decompression.The supplied passages describe running these four algorithms on SLUGGER and SWEG summary graphs.
  • Partial decompression: Algorithm 4 takes a hierarchical graph summarization model and a subnode v, returning v’s one-hop neighbor set N_v.
Loading 2112.05374v1…