Algorithmic Inductive Biases for Graph Representation Learning

Abstract:

Deep learning has witnessed phenomenal growth in the last decade. An important factor in the success of deep learning is the ability to encode structure in the neural network that can provide useful inductive bias in learning. Inductive bias makes the learning algorithm favour certain solutions over others, and this helps in generalization if the bias is well-aligned with the end task. However, introducing useful structures in the neural network can often be non-trivial and may need significant domain knowledge.

One way of introducing structure in the neural network is by mimicking the steps of an algorithm in the computational process. Algorithms usually contain simple update steps which are iteratively repeated, and this can help in capturing inherent structure of the data as well as in sharing parameters. In this thesis, we propose to use the knowledge of well-known algorithms to provide the inductive bias needed for effective learning. We focus on representation learning on relational data for which Graph Neural Networks (GNNs) have emerged as a framework of choice. For this, we take two different views of representations learnt by GNNs and propose Algorithmic Inductive Biases which can help from both the perspectives.

In the first part of the thesis, we take the view that GNN message passing is analogous to inference in Probabilistic Graphical Models (PGMs). However, GNN models often rely on localized first order approximations of spectral graph convolutions and do not explicitly model higher-order relational information among variable nodes. On the contrary, PGMs provide a principled way of incorporating such higher-order relational information but are limited by inefficient approximate inference algorithms. We derive an efficient approximate sum-product loopy belief propagation inference algorithm for higher-order PGMs and then embed the message passing updates into the neural network to provide the inductive bias of the inference algorithm in end-to-end learning. This gives us a computationally feasible GNN model flexible enough to accommodate domain knowledge that can improve the representations learnt. We empirically demonstrate its usefulness in multiple node and graph prediction tasks.

In the second part of the thesis, we aim to improve the representational capacity of GNNs which are known to be limited in their expressive power by the 1-WL color-refinement test for graph isomorphism. We propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques which operate on the paradigm of Individualization and Refinement (IR), a method to artificially introduce asymmetry and further refine the coloring when 1-WL stops. Isomorphism solvers generate a search-tree of colorings (i.e. embeddings) whose leaves uniquely identify the graph. However, the tree grows exponentially large and needs hand-crafted pruning techniques which are not desirable from a learning perspective.

We provide two ways of handling the exponential growth of the search-tree. In the first method, we propose a heuristic technique on the lines of beam search to limit the size of the search-tree. We prove that such a method will maintain the property of permutation-invariance and is more expressive for a class of graphs strictly larger than the ones distinguishable by GNNs. In the second method, we take a probabilistic view and approximate the search tree of colorings by sampling multiple paths from root to leaves of the search tree. To learn more discriminative representations, we guide the sampling process with particle filter updates, a principled approach for sequential state estimation. Both our deterministic and probabilistic algorithms are end-to-end differentiable, can be applied with any GNN as backbone and learn richer graph representations with only linear increase in runtimes. Experimental evaluation shows that our approaches consistently outperform leading GNN models on both synthetic benchmarks for isomorphism detection as well as real-world datasets.