Publication
Many challenges of modern graph processing stem from the fact that graphs have become massive and change frequently. Numerous techniques have been developed to address those issues, with graph cut sparsification offering to replace original graphs with their succinct versions while preserving the sizes of cuts, sketching allowing to compute compressed embeddings of the graph and dynamic streaming algorithms being able to process evolving graphs on the fly, supporting both insertion and deletion of edges.
Cut sparsifiers are especially useful in cut-centric application like clustering. However, in practical scenarios considering higher-order structures, like the number of triangles crossing each cut, turn out to be exceptionally valuable for the quality of partitioning. One class of those structures, which the triangle is an example of, are motifs, which are frequently occurring subgraphs of a given graph. Regrettably, classical graph sparsification results fail to preserve such structures. In this thesis, we present a new type of graph sparsifier called a motif cut sparsifier, which can preserve the number of motifs that each cut crosses for all motifs of constant size simultaneously, while still being a regular cut sparsifier and using approximately the same amount of edges as the classic constructions. This result works when we count all subgraphs isomorphic to our motif, i.e. non-induced occurrences, as valid instances. Surprisingly, we show a there exists a strong lower bound on sparsification when only the induced occurrences of motifs are counted, which we also present.
To maximize the benefit of compactness of graph sparsifiers, we need to be able to compute them on the fly, using approximately the same amount of memory that is used to store them. Linear sketches has proven to be a powerful tool to achieve this, even in dynamic streams where edges can be both inserted and deleted. However, low-memory construction of other fundamental primitives beyond graph sparsifiers has been more difficult. One such fundamental tool, which has recently found success in the design of dynamic algorithms, is expander decomposition. At the heart of the algorithms for expander decomposition is a recursive procedure searching for sparse cuts in the graph. Due to the adaptivity of this process, it is difficult to perform it in the streaming model using existing sparsifier constructions --- this is a common issue for many streaming algorithms. We present a way to overcome this obstacle, and compute expander decompositions in dynamic streams.
In general, streaming algorithms have to rely on randomness, which makes it difficult to make them work with adaptive inputs, with classical construction typically not providing any such guarantee whatsoever. As an example, algorithms based on linear sketches were shown to be vulnerable when faced with an adaptive adversary. In our work, we show that this is also an issue for another classic sublinear data structure