PaperlayerView exact revision on arXiv

Source-linked AI summary

Incremental Lossless Graph Summarization

Jihoon Ko, Yunbum Kook, Kijung Shin

arXiv:2006.09935v1cs.DBcs.SI

TL;DR

Large graphs evolve through edge insertions and deletions, creating a need for compact lossless summaries that can be updated without rerunning static batch algorithms. MoSSo incrementally moves nodes among supernodes using several rapid selection mechanisms. It achieves near-constant-time updates, scales to hundreds of millions of edges with sub-linear memory, and retains compression rates comparable to batch methods.

  • Problem

    Large dynamic graphs require compact representations, but existing lossless summarization methods are designed for static graphs and inefficient under updates.

  • Method

    MoSSo incrementally updates a lossless summary after each edge change by moving nodes among supernodes using Corrective Escape, Fast Random, and Careful Selection.

  • Results

    Near-constant-time updates, sub-linear memory, and comparable compression rates make MoSSo fast, scalable, and effective across dynamic graph streams.

  • Takeaways & Limitations

    MoSSo enables online lossless summarization of fully dynamic graphs without maintaining the original graph in memory.

  • Takeaways & Limitations

    MoSSo assumes a sound graph stream in which additions refer to absent edges and deletions refer to present edges.

Abstract

from arXiv · show

Given a fully dynamic graph, represented as a stream of edge insertions and deletions, how can we obtain and incrementally update a lossless summary of its current snapshot? As large-scale graphs are prevalent, concisely representing them is inevitable for efficient storage and analysis. Lossless graph summarization is an effective graph-compression technique with many desirable properties. It aims to compactly represent the input graph as (a) a summary graph consisting of supernodes (i.e., sets of nodes) and superedges (i.e., edges between supernodes), which provide a rough description, and (b) edge corrections which fix errors induced by the rough description. While a number of batch algorithms, suited for static graphs, have been developed for rapid and compact graph summarization, they are highly inefficient in terms of time and space for dynamic graphs, which are common in practice. In this work, we propose MoSSo, the first incremental algorithm for lossless summarization of fully dynamic graphs. In response to each change in the input graph, MoSSo updates the output representation by repeatedly moving nodes among supernodes. MoSSo decides nodes to be moved and their destinations carefully but rapidly based on several novel ideas. Through extensive experiments on 10 real graphs, we show MoSSo is (a) Fast and 'any time': processing each change in near-constant time (less than 0.1 millisecond), up to 7 orders of magnitude faster than running state-of-the-art batch methods, (b) Scalable: summarizing graphs with hundreds of millions of edges, requiring sub-linear memory during the process, and (c) Effective: achieving comparable compression ratios even to state-of-the-art batch methods.

1 INTRODUCTION

Large evolving graphs motivate compact representations, but existing lossless summarization methods target static graphs and must be rerun after changes. MoSSo provides the first incremental approach, updating summaries rapidly while preserving competitive compression and scalability.

  • Background: Lossless graph summarization represents a graph with supernodes, superedges, and edge corrections that recover the original edges.The representation is compact and supports rapid neighborhood queries.
  • Motivation: Existing lossless summarization algorithms are static batch methods that must be rerun from scratch after dynamic changes.This makes them inefficient for fully dynamic graph streams.
  • Contribution: MoSSo is the first incremental algorithm for lossless summarization of fully dynamic graphs, updating summaries by moving nodes among supernodes.Corrective Escape, Fast Random, and Careful Selection guide node movement and destination selection.
  • Results: MoSSo summarizes graphs with up to 0.3 billion edges using sub-linear memory while maintaining compression rates comparable to state-of-the-art batch algorithms.The evaluation compares MoSSo with batch and streaming baselines on 10 real-world graphs.
  • Results: 0.1 millisecond per change and up to 10 million times faster than state-of-the-art batch algorithms characterize MoSSo's fast, any-time updates.The comparison is reported for processing changes in dynamic graphs.

2 NOTATIONS AND PROBLEM SETUP

The paper defines incremental lossless summarization for fully dynamic edge streams and seeks concise representations after each change. The formulation uses summary graphs and corrections, with approximate streaming solutions motivated by changing optima and the cost of recomputation.

  • 2.1 Notations and Concepts: A summary graph partitions nodes into supernodes and connects pairs of supernodes with superedges, while edge corrections recover the original graph.The summary graph first induces a rough graph by connecting all node pairs across neighboring supernodes.
  • 2.1 Notations and Concepts: A fully dynamic graph stream is a sequence of edge additions and deletions that defines the graph at each time step.The stream may introduce new nodes through edge additions and is assumed sound.
  • 2.2 Problem Formulation: Incremental lossless graph summarization updates the summary graph and corrections after each stream change instead of recomputing them from scratch.The objective is to obtain a concise representation at the next time step.
  • 2.2 Problem Formulation: The formulation minimizes the output representation size, counting summary-graph and edge-correction components while disregarding the comparatively small number of supernodes.This objective follows the Minimum Description Length principle and was previously used for static summarization.
  • 2.2 Problem Formulation: Because the optimal summary can change at any time among almost infinitely many possibilities, the paper studies approximate streaming solutions rather than guaranteed optima.Even static lossless summarization has been addressed only with heuristics without guarantees.

3 PROPOSED METHOD

MoSSo incrementally updates lossless graph summaries by moving nodes among supernodes after each edge insertion or deletion, using randomized escape, careful candidate selection, and fast neighborhood sampling. These mechanisms support near-constant update time, sub-linear memory, and compression rates comparable to batch methods.

  • 3.4 MoSSo-Simple: Simple Proposed Method: Corrective Escape probabilistically separates a tested node into a singleton supernode, helping reorganize supernodes and improve compression over time.The escape mechanism injects flexibility so the summary can move toward different potentially better configurations.
  • 3.5 MoSSo: Full-Fledged Proposed Method: MoSSo uses coarse clustering and getRandomNeighbor to achieve near-constant processing time per graph change while preserving strong compression rates.The full-fledged method replaces full neighborhood retrievals with unbiased sampling and carefully selects candidate nodes.
  • 3.5 MoSSo: Full-Fledged Proposed Method: getRandomNeighbor uses unbiased sampling without retrieving an entire neighborhood, addressing the scalability threat posed by growing average degree.Its average time is O(c · (1 + |C−(u)|/deд(u))) per node, and under preferential attachment its average complexity is O(c).
  • 3.6.1 Soundness of getRandomNeighbor (Alg. 2).: MoSSo’s sampling soundness is established through uniform-sampling theorems, including an MCMC construction with proposal probability 1/k and acceptance probability min(1, |Sj|/|Si|).These results provide the theoretical basis for getRandomNeighbor, a core building block of the incremental algorithm.
  • 3.6.4 Space Complexity of MoSSo (Alg. 1).: MoSSo requires O(|V| + |P| + |C+| + |C−|) space, so the entire input graph need not remain in memory during incremental summarization.The space bound is sub-linear relative to explicitly maintaining the full graph representation in the incremental process.

4 EXPERIMENTS

MoSSo is evaluated on speed, compression ratio, and scalability using real-world insertion-only and fully dynamic graph streams. It substantially outperforms batch and streaming competitors while maintaining compact summaries and near-constant update time.

  • Experimental Settings: Experiments used ten real-world graphs and generated both insertion-only and fully dynamic streams, including randomly positioned deletions with probability 0.1.Edges were treated as undirected, with self-loops and multiple edges removed.
  • Evaluation Measures: Compression ratio was defined as (|P| + |C+| + |C−|)/|E|, and runtime and ratio results were generally averaged over three trials.For streaming methods, runtime was normalized per change; batch methods were evaluated at several stream-progress points.
  • Q1. Speed: MoSSo processed each change up to 7 orders of magnitude faster than the fastest batch algorithm and 2 orders faster than streaming baselines.The speed gap widened on larger datasets, where baseline methods sometimes ran out of time.
  • Q2. Compression Ratio: MoSSo achieved the best compression ratios among streaming algorithms and ratios comparable to those of the best batch algorithms.MoSSo also consistently outperformed MoSSo-Simple in compression ratio.
  • Q3. Scalability: MoSSo’s accumulated runtime grew near-linearly with processed changes, implying near-constant time per change.The scalability evaluation used the Web-EU-05 dataset and excluded time spent waiting for input changes.

5 RELATED WORKS

Prior dynamic-graph summarization work largely targets lossy summaries or batch processing, whereas MoSSo addresses incremental lossless summarization of the current graph snapshot. Its compactness is competitive with batch methods while remaining suitable for continuously updated streams.

  • Summarization of dynamic graphs: Existing dynamic-graph summarization methods have focused largely on lossy summaries for query efficiency, influence analysis, or temporal-pattern discovery.Several incremental methods summarize the current snapshot as a graph sketch, while other methods summarize the history of graph growth.
  • Summarization of dynamic graphs: MoSSo is presented as the first incremental algorithm for lossless summarization of fully dynamic graphs.Unlike static-graph batch algorithms, it updates the summary as edge insertions and deletions arrive.
  • Summarization of dynamic graphs: MoSSo achieved compression ratios comparable to the best batch algorithms, which were rerun repeatedly during stream processing.This comparison highlights compactness under incremental updates rather than only after one final batch run.

6 CONCLUSIONS

MoSSo is a fast and effective incremental algorithm for lossless summarization of fully dynamic graphs. It combines rapid updates, scalability to very large streams, and compression rates comparable to state-of-the-art batch methods.

  • 6 CONCLUSIONS: MoSSo updates lossless summaries of fully dynamic graphs up to 7 orders of magnitude faster per change than the fastest batch algorithm.Its update time remains constant as the input graph grows.
  • 6 CONCLUSIONS: MoSSo summarizes fully dynamic graphs with up to 0.3 billion edges without maintaining the original graph in memory.The paper supports this scalability claim theoretically through Theorem 4.
  • 6 CONCLUSIONS: MoSSo achieves compression rates comparable to state-of-the-art batch algorithms.The method is based on Corrective Escape, Fast Random, and Careful Selection.

A.1 Effects of Parameters (Fig. 6)

The parameter study examines how escape probability and neighborhood-sample count affect MoSSo’s runtime and compression ratio. More samples improve compression gradually but increase runtime, while higher escape probability slightly reduces runtime and worsens compression.

  • Effects of Parameters: Compression ratio was minimized near escape probability e = 0.1, while increasing e reduced runtime only slightly and increased the ratio.The analysis used the Skitter dataset.
  • Effects of Parameters: Increasing the number of samples c gradually decreased compression ratio but increased runtime proportionally to c.Thus, larger sample counts trade additional computation for more compact representations.

A.2 Effects of Graph Properties (Fig. 7(a))

MoSSo compresses better on synthetic graphs when nodes have more similar connectivity, as controlled by a higher copying probability.

  • A.2 Effects of Graph Properties (Fig. 7(a)): Higher copying probability β, which creates more nodes with similar connectivity, led to better compression rates.The experiment used synthetic graphs with |V| = |E| = 10,000,000 and varied β.

A.3 Additional Scalability Tests (Figs. 7(b)-7(c))

MoSSo’s accumulated runtime remained near-linear on both tested datasets, whereas MoSSo-Simple scaled super-linearly.

  • A.3 Additional Scalability Tests (Figs. 7(b)-7(c)): MoSSo’s accumulated runtime was near-linear on both Web-EU-05 and Skitter.The result is reported in Figs. 7(b)-7(c).
  • A.3 Additional Scalability Tests (Figs. 7(b)-7(c)): MoSSo-Simple’s accumulated runtime was super-linear, proportional to |E|^1.42.

B APPENDIX: PROOFS

The appendix establishes correctness, runtime, and space properties for MoSSo’s sampling and incremental maintenance procedures.

  • B APPENDIX: PROOFS: The sampling scheme draws a supernode and then a node within it, with acceptance ensuring asymptotic convergence to the target distribution π.The proof describes two consecutive sampling stages and states that the acceptance rule guarantees convergence.
  • B APPENDIX: PROOFS: Neighborhood retrieval examines neighboring supernodes and correction sets, yielding time O(deg(u) + 2|C−(u)|) for node u.
  • B APPENDIX: PROOFS: Under optimal encoding, |C−| ≤ |E|, so the average-case neighborhood-retrieval complexity is bounded by 3 · deg.The bound follows from |P| + |C+| + |C−| ≤ |E| and the stated inequality for correction edges.
  • B APPENDIX: PROOFS: The incremental algorithm maintains the current summary and corrections in O(|V| + |P| + |C+| + |C−|) space.This includes coarse cluster memberships and counts of edges between supernode pairs.

C APPENDIX: DETAILS OF MOSSO-MCMC

MoSSo-MCMC proposes destination supernodes using connectivity information and accepts moves with a Metropolis-Hastings probability designed to preserve the target distribution.

  • C APPENDIX: DETAILS OF MOSSO-MCMC: MoSSo-MCMC adapts proposal and acceptance distributions for Stochastic Block Modeling [23].The algorithmic details are given through its proposal and acceptance rules.
  • C APPENDIX: DETAILS OF MOSSO-MCMC: For a testing node y and random neighbor x, proposal probabilities emphasize supernodes densely connected to Sx while ε ensures every supernode remains selectable.The proposal distribution is defined over candidate supernodes Sz.
  • C APPENDIX: DETAILS OF MOSSO-MCMC: A proposed move of y into Sz is accepted using a Metropolis-Hastings probability, with β controlling how readily moves that increase φ are accepted.The reverse proposal probability is computed after y has moved from Sy to Sz.
  • C APPENDIX: DETAILS OF MOSSO-MCMC: Figure 8 illustrates that Eq. (4) most often selects a candidate from the supernode containing one of the testing node’s relevant neighbors.Superedge thickness represents the number of edges between supernodes.
Loading 2006.09935v1…