Kimia Shayestehfard’s PhD Proposal Review

“Permutation Invariant Graph Learning”

Abstract:
Graphs are widely used in many areas such as biology, engineering, and social sciences to model sets of objects and their interactions and relationships. Tasks addressed by applying machine learning to graphs, known as graph learning, include node and graph classification, edge prediction, transfer learning, and generative modeling/distribution sampling, to name a few.
Due to high prevalence and multitude of applications of graphs across different fields, graph neural networks have been developed in the past few years. Graph neural networks have shown tremendous success at producing node embeddings that capture structural and relational information of a graph and are discriminative for downstream tasks. However, graph learning algorithms still deal with a major challenge, namely, the lack of permutation invariance: In a dataset of sampled graphs, nodes may be ordered arbitrarily, and aligning them is combinatorial and computationally expensive. Moreover, many graph distance algorithms do not satisfy metric properties, which can significantly hamper the fidelity of the downstream tasks. In this work we address the challenges posed by permutation invariance via combining fast and tractable metric graph alignment methods with graph neural networks. We propose a tractable, non-combinatorial method for solving the graph transfer learning problem by combining classification and embedding losses with a continuous, convex penalty motivated by tractable graph distances. We demonstrate that our method successfully predicts labels across graphs with almost perfect accuracy; in the same scenarios, training embeddings through standard methods leads to predictions that are no better than random. Furthermore, we propose a framework that combines fast and tractable graph alignment methods with a family of deep generative models and are thus invariant to node permutations. These models can be learned by solving convex optimization problems. Our experiments demonstrate that our models successfully learn graph distributions, outperforming competitors by at least 66% in two relevant performance scores and improve the computation time up to 20 times over existing metric graph alignment methods.

Committee:

Prof. Stratis Ioannidis (Advisor)

Prof. Dana Brooks (Advisor)

Prof. Tina Eliassi-Rad