UC San Diego

Recently there has been an increasing number of learning problems arising in complex data domains, like graph-structured data, such as social networks and knowledge graphs. Various machine learning approaches have been developed to handle different kinds of data like PointNet for point clouds and graph neural networks for graph-structured data. At the same time, to tame the complexity in data, geometry and topology form natural platforms. In particular, computational geometry and the emerging field of topological data analysis (TDA) have been effective at capturing hidden structure and shape features from data, as well as providing efficient algorithms for them. In this thesis, we aim to integrate geometric ideas and topological concepts with machine learning pipelines to further augment their power and performance.

In the first part of the thesis, we show how topological ideas, in particular, the so-called persistent homology, can help with analyzing graph-structured data. Persistent homology provides a flexible and versatile way to summarize complex shapes (including graphs) by a simple multiscale summary. In the first line of work, we designed an effective metric learning approach for persistence-based summaries of graphs, and showed how this improved graph classification tasks. In the second line, we show how topological summaries can be used to further improve graph neural networks' performance.

In the second part, we investigate how geometric algorithmic ideas can be combined with neural networks (NNs) to tackle hard optimization problems in geometric setting. In recent years, NNs have shown promise in helping solve combinatorial optimization problems. However, such approaches often tend to be ad hoc. Instead of solving problems in a completely data-driven manner using NNs, we propose to design mixed algorithmic-NN frameworks, where NNs are used as components within an algorithmic framework. In particular, this allows us to leverage elegant algorithmic ideas for problems in geometric setting to develop learning-based frameworks solving optimization problems efficiently in practice, but also with theoretical guarantees. We demonstrate our proposed mixed algorithmic-NN frameworks over two problems: Maximum-independent set (and several other graph problems) for intersection graphs in Euclidean setting, and computing (rectilinear) Minimum Steiner Tree for points in Euclidean setting.