Change-Sensitive Algorithms for Maintaining Maximal Cliques in a Dynamic Graph

Apurba Das, Michael Svendsen, Srikanta TirthapuraarXiv 2016 · OpenReview

TL;DR

This paper introduces the first "change-sensitive" algorithms for efficiently tracking maximal cliques in graphs that are constantly changing due to edge additions and deletions. These algorithms achieve near-optimal performance by directly focusing on the changes, leading to significant speedups (2-3 orders of magnitude) over previous methods.

What Problem Does This Paper Address?

Many real-world applications, from social network analysis to biological data mining, rely on identifying dense subgraphs like maximal cliques within large, evolving graphs. Traditional methods for finding maximal cliques are designed for static graphs and become highly inefficient when applied to dynamic graphs, as they often recompute everything from scratch even for minor changes. This paper addresses the critical need for algorithms that can efficiently update the set of maximal cliques as the graph evolves, without re-analyzing the entire structure.

Methods

The core innovation lies in developing "change-sensitive" algorithms. Instead of re-scanning the entire graph, these algorithms focus on the specific edges that have been added or deleted.

  • Incremental Algorithms (Edge Additions): The authors propose algorithms that, when a set of edges is added, efficiently identify only the new maximal cliques that are formed and the old maximal cliques that are no longer maximal (subsumed). They achieve this by analyzing small subgraphs localized around the newly added edges. A key technique involves reducing the problem of finding new cliques to finding maximal cliques in these localized subgraphs, while carefully avoiding redundant computations.
  • Decremental Algorithms (Edge Deletions): The decremental case (edge deletions) is cleverly reduced to the incremental case by considering the graph after deletions and then adding back the deleted edges.
  • Change-Sensitive Approach: The algorithms' runtime is directly proportional to the magnitude of the change in the set of maximal cliques, rather than the total size of the graph. This is a significant departure from previous methods.
  • Practical Implementation: They introduce FastIMCENewClq, an optimized version of their incremental algorithm that further prunes the search space, leading to better practical performance.

Datasets

The authors evaluated their algorithms on a variety of real-world dynamic graphs, including:

  • Social Networks: flickr-growth, sx-stackoverflow-a2q, youtube-u-growth
  • Collaboration Networks: dblp-coauthor
  • Knowledge Networks: wiki-talk, wikipedia-growth

They also used synthetic graphs generated using the Erdős-Rényi model with "planted" cliques to test their ability to find known structures incrementally.

Key Insights and Ideas

  • Focusing on Change is Key: The most significant insight is that efficiently maintaining maximal cliques in dynamic graphs requires a paradigm shift from static analysis to focusing solely on the changes introduced by edge updates.
  • Localized Analysis Suffices: New and subsumed cliques are often localized around the updated edges, allowing for efficient analysis of smaller subgraphs rather than the entire graph.
  • Magnitude of Change Matters: The number of maximal cliques can change dramatically (exponentially in the worst case) even with a small number of edge updates, highlighting the need for algorithms that are sensitive to this magnitude.
  • Theoretical Bounds are Tight: The paper establishes nearly tight theoretical bounds on the maximum possible change in the set of maximal cliques, providing a strong foundation for their algorithmic design.
  • Practical Performance Gains: The proposed change-sensitive algorithms, especially the optimized FastIMCENewClq, offer substantial performance improvements over existing methods, making dynamic clique maintenance feasible for larger and more active graphs.

Key Results

  • Significant Speedup: The proposed IMCE algorithms are 2-3 orders of magnitude faster than prior state-of-the-art methods on real-world dynamic graphs.
  • Change-Sensitive Performance: Experimental results demonstrate that the runtime of IMCE closely tracks the magnitude of the change in the set of maximal cliques, validating the change-sensitive design.
  • Efficient Handling of Updates: The algorithms efficiently handle both incremental (edge additions) and decremental (edge deletions) updates.
  • Memory Optimization: Using hash signatures for maximal cliques significantly reduces memory consumption compared to storing the full clique sets.
  • Practicality on Large Graphs: The algorithms successfully maintain maximal cliques on graphs with millions of vertices and edges within seconds.

Limitations and Future Work

  • Fully Dynamic Case: While the paper presents algorithms for incremental and decremental updates, the fully dynamic case (handling both additions and deletions simultaneously) is noted as not being provably change-sensitive.
  • Exact Magnitude of Change: The paper aims to provide tight bounds for the maximum possible change in maximal cliques (x(n)) but acknowledges that determining the exact value remains an open research question.
  • Other Dense Structures: The authors suggest extending their change-sensitive approach to other types of dense structures in graphs, such as quasi-cliques.
  • Further Algorithmic Improvements: The paper points to ongoing research in designing more efficient change-sensitive algorithms, particularly for enumerating subsumed cliques.

Summary updated

Abstract

We consider the maintenance of the set of all maximal cliques in a dynamic graph that is changing through the addition or deletion of edges. We present nearly tight bounds on the magnitude of change in the set of maximal cliques, as well as the first change-sensitive algorithms for clique maintenance, whose runtime is proportional to the magnitude of the change in the set of maximal cliques. We present experimental results showing these algorithms are efficient in practice and are faster than prior work by two to three orders of magnitude.
BibTeX
@misc{das2016change,
  author = {Apurba Das and Michael Svendsen and Srikanta Tirthapura},
  title = {{Change-Sensitive Algorithms for Maintaining Maximal Cliques in a Dynamic Graph}},
  year = {2016},
  eprint = {1601.06311},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1601.06311},
}
Figure