Combinatorial Methods for Graph Pooling

Downsampling produces coarsened, multi-resolution representations of data and it is used, for example, to produce lossy compression and visualization of large images, reduce computational costs, and boost deep neural representation learning. Unfortunately, due to their lack of a regular structure, there is still no consensus on how downsampling should apply to graphs and linked data. Indeed reductions in graph data are still needed for the goals described above, but reduction mechanisms do not have the same focus on preserving topological structures and properties, while allowing for resolution-tuning, as is the case in regular data downsampling. In this thesis, we take a step in this direction, introducing three different interpretations of downsampling for graph data. In the first one, we define a graph coarsening mechanism which is a graph-structured counterpart of controllable equispaced coarsening mechanisms in regular data. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs. In the second one, we define a graph coarsening mechanism that instead preserves the connectivity of the input graph by performing a series of edge contractions that can be efficiently computed adapting a well-known parallel algorithm from literature. In the third and last one, we introduce a coarsening technique, which borrows from classical results in graph theory, that instead contracts highly dense communities in the graph, that is non-parametric and generalizes well to graphs of different nature and connectivity patterns. We leverage these concepts to define three graph pooling mechanisms that we empirically assess in graph classification tasks, showing that they compare favorably against other pooling methods in literature.