A Change-Sensitive Algorithm for Maintaining Maximal Bicliques in a Dynamic Bipartite Graph

Apurba Das, Srikanta TirthapuraarXiv 2017 · OpenReview

TL;DR

This paper introduces the first "change-sensitive" algorithms for efficiently tracking maximal bicliques in dynamic bipartite graphs. These algorithms' runtime is proportional to the actual change in bicliques, offering significant speedups over existing methods that recompute everything from scratch.

What Problem Does This Paper Address?

Bipartite graphs are fundamental for modeling relationships in various domains, like social networks or biological interactions. Often, these networks evolve over time, with edges being added or removed. A key structural pattern in bipartite graphs is the "maximal biclique" – a complete bipartite subgraph that cannot be extended. Maintaining an accurate count and list of these maximal bicliques as the graph changes is computationally challenging. Existing methods typically re-analyze the entire graph after each update, which is inefficient, especially when only a small portion of the bicliques actually change. This paper tackles the problem of efficiently enumerating only the changes in maximal bicliques, rather than recomputing the entire set.

Methods

The core contribution is a "change-sensitive" algorithm called DynamicBC. This algorithm is designed to be efficient when the number of changes in maximal bicliques is small. It breaks down the problem into two main parts:

  • NewBC (Enumerating New Maximal Bicliques): This component efficiently finds bicliques that become maximal after new edges are added. It does this by focusing on subgraphs induced by the neighborhoods of the newly added edges, leveraging a static maximal biclique enumeration algorithm (MineLMBC) on these smaller subgraphs.
  • SubBC (Enumerating Subsumed Maximal Bicliques): This part identifies bicliques that were maximal in the old graph but are no longer maximal after edge additions (i.e., they are now contained within larger bicliques). It uses a clever approach of computing maximal bicliques in the "difference" graph (bicliques from the old graph minus the new edges) and comparing their signatures (hashes) against the original set of maximal bicliques. This avoids storing all maximal bicliques in memory, which can be prohibitive.

The paper also addresses the decremental case (edge deletions) by reducing it to the incremental case (edge additions) and proposes a strategy for the fully dynamic case (both additions and deletions).

Datasets

The authors evaluated their algorithms on several real-world bipartite graph datasets:

  • actor-movie-1: Represents actors and movies they starred in.
  • dblp-author-1: Connects authors to their publications.
  • epinions-rating-init: Links users to products they rated.
  • flickr-membership-1: Shows users and the groups they belong to.

These datasets are described as having millions of nodes and edges, making them suitable for testing the scalability of the proposed algorithms.

Key Insights and Ideas

  • The "Change" is Key: The fundamental insight is that focusing on the change in maximal bicliques, rather than the entire set, is crucial for efficiency in dynamic graphs.
  • Magnitude of Change Can Be Large: The paper proves that even a single edge addition can lead to an exponential change in the number of maximal bicliques, highlighting the necessity of specialized algorithms.
  • Change-Sensitive Algorithms: The core idea is to design algorithms whose runtime is proportional to the magnitude of the change, not just the size of the graph. This is achieved by carefully focusing computation on the affected parts of the graph.
  • Signature-Based Comparison: Using hash signatures for maximal bicliques in the SubBC component is a clever memory-saving technique, avoiding the need to store potentially massive sets of bicliques.
  • Reduction to Incremental Case: The elegant reduction of the decremental problem to the incremental one simplifies the overall dynamic graph maintenance.

Key Results

  • Near-Tight Bounds: The paper establishes near-tight bounds on the magnitude of change in maximal bicliques, showing it can be as large as 1.5 times the maximum possible number of bicliques in a graph of slightly smaller size.
  • Significant Speedup: Experimental results demonstrate that DynamicBC is orders of magnitude faster than a baseline algorithm that recomputes all maximal bicliques from scratch. For instance, on the actor-movie-1 dataset, DynamicBC took about 30 milliseconds to process a batch of 100 edges, while the baseline took over 30 minutes.
  • Scalability: The algorithms were tested on large graphs (millions of nodes) and showed good performance.
  • Change-Sensitivity Verified: Experiments confirmed that the computation time of DynamicBC is roughly proportional to the size of the change in maximal bicliques.

Limitations and Future Work

  • Theoretical Bounds vs. Practical Performance: While theoretical bounds on the magnitude of change are provided, the paper acknowledges that in practice, the change can still be large, leading to longer computation times.
  • Future Work: The authors suggest two main avenues for future research:
  • Developing more efficient algorithms for enumerating changes, particularly for subsumed cliques.
  • Exploring parallelization of the algorithm for enumerating changes in maximal bicliques.

Summary updated

Abstract

We consider the maintenance of maximal bicliques from a dynamic bipartite graph that changes over time due to the addition or deletion of edges. When the set of edges in a graph changes, we are interested in knowing the change in the set of maximal bicliques (the "change"), rather than in knowing the set of maximal bicliques that remain unaffected. The challenge in an efficient algorithm is to enumerate the change without explicitly enumerating the set of all maximal bicliques. In this work, we present (1) near-tight bounds on the magnitude of change in the set of maximal bicliques of a graph, due to a change in the edge set (2) a "change-sensitive" algorithm for enumerating the change in the set of maximal bicliques, whose time complexity is proportional to the magnitude of change that actually occurred in the set of maximal bicliques in the graph. To our knowledge, these are the first algorithms for enumerating maximal bicliques in a dynamic graph, with such provable performance guarantees. Our algorithms are easy to implement, and experimental results show that their performance exceeds that of current baseline implementations by orders of magnitude.
BibTeX
@misc{das2017change,
  author = {Apurba Das and Srikanta Tirthapura},
  title = {{A Change-Sensitive Algorithm for Maintaining Maximal Bicliques in a Dynamic Bipartite Graph}},
  year = {2017},
  eprint = {1707.08272},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.08272},
}
Figure