Neural Networks for Learning Graph Embedding and Graph Matching

Time	2020 — 2024
Funding	Swiss National Science Foundation
Researchers	Francesco Leonardi, Kalvin Dobler, Kaspar Riesen

Abstract: The proposed project is concerned with graph-based pattern recognition. Research in this area can be roughly divided into three time periods, viz. the eras of graph matching, graph kernels, and graph neural networks. The overall objective of the present project is to develop and research robust methods which combine the best ideas and methods that emerged from these three eras. This way, we aim to introduce novel graph-based methods that significantly exceed the current state of the art, both in terms of speed and accuracy. Due to their power and flexibility, graphs indeed play a pivotal role in many disciplines in science and industry and the research of efficient and accurate graph-based methods has become a crucial challenge. Therefore, both the relevance and potential impacts of the proposed project can be considered very high. We envisage three relatively independent lines of research that will be investigated by two PhD students and one postdoctoral researcher.

Line of Research 1: We will employ existing graph embedding frameworks, more specifically the resulting vector space embedding, as ground truth for designing, developing, and training of novel graph neural networks. The aim is to learn graph embeddings that minimize the difference of the learned and the ground truth embed- ding. Major benefit of this procedure is that the embedding of unseen graphs can be accomplishment incomparably faster than with the original techniques.

Line of Research 2: We will learn graph matchings using graph neural networks. To this end, we plan to omit the global pooling layer and directly infer node map- pings based on the learned node embeddings. Initial ideas include exploring clustering and/or assignment algorithms that can be applied to the learned node embeddings. The advantage of this method is that it derives explicit mappings of the substructures of the underlying graphs (which is both valuable and often necessary in applications).

Line of Research 3: We plan to explore new (interdisciplinary) applications for graph-based pattern recognition. In particular, we seek to address data challenges where graphs are not currently used, even though they would be the natural approach for formal pattern representation. We believe that this will enable us to define break- through and pioneering algorithms in various scientific fields.

Along the three lines of research, several open research questions need to be answered to push forward the frontier of current knowledge. These questions range from technical issues (e.g., Which architectures are best suited for the target tasks?), over conceptual issues (e.g., Which novel applications are suitable for graph-based methods?), to empirical issues (e.g., To what extent do the proposed methods improve and accelerate the current state of the art in graph-based pattern recognition?).