CISE Seed Grant Report: Overlapping Graph Partitioning for Distributed Graph Mining

This CISE Seed Grant, award in May 2018, funded doctoral student Erasmo Tani in the CS Department to work under the supervision of  CISE Faculty Affiliate  Lorenzo Orecchia (CS) and  Charalampos E. Tsourakakis  (CS, ECE) in the design of a novel class of graph clustering algorithms that can incorporate both edge cuts and vertex cut information.

The funding supported the following activities:

• Erasmo and his supervisors designed novel theoretical algorithms for approximating trade-offs of edge and vertex cuts. The theoretical design and analysis is complete and the researchers are currently working to implement the algorithms. They expect to submit separate theoretical and experimental papers during 2019.
• Theoretical work under the previous point led them to consider novel spectral algorithms for vertex separators. They are preparing a manuscript to be submitted during 2019.
• PhD Candidate (CS) Tani and Professors Orecchia and Charalampos have also prepared and submitted a grant proposal on this topic to NSF CISE core program on Algorithms Foundations.