Graphs are ubiquitous in statistical modeling and a broad range of machine learning applications. Examples are social networks, natural language dependency structures, latent interrelationships among tasks, and neural network topologies. Despite their versatility in representing structured data, how to fuse the information from heterogeneous and/or dynamically evolving graphs poses a grand challenge to existing machine learning theory and optimization algorithms. Furthermore, efficient graph topology optimization is another important but unsolved problem which entails searching over a combinatorially large discrete space. In this thesis, we address these open challenges in several complementary aspects:
In §1 we focus on a novel framework for fusing multiple heterogeneous graphs into a single homogeneous graph, on which learning tasks can be conveniently carried out in a principled manner. We also propose a new approach to impose analogical structures among heterogeneous nodes, which offers a theoretical unification of several representative models along with improved generalization.
In §2 we focus on graph induction problems in the context of graph-based semisupervised learning. We start with a nonparametric method that is able to recover the optimal latent label diffusion pattern over the graph, and then generalize label diffusion processes as graph convolution operations whose filter weights are induced from data residing on the non-Euclidean manifold.
In §3 we extend the scope of our modeling from static graphs to dynamic graphs. Specifically, we develop an online algorithm for multi-task learning with provable sublinear regret bound, where a latent graph of task interdependencies is dynamically inferred on-the-fly. We also look at time-series forecasting tasks, showing that the explicitly modeling of the graph dependencies among temporally evolving variables can improve the prediction accuracy.
In §4 we formulate neural architecture search as a graph topology optimization problem. We present a simple yet efficient evolutionary algorithm that automatically identifies high-performing architectures based on a novel hierarchical representation
scheme, where smaller operations are automatically discovered and reused as building blocks to form larger ones. The learned architecture achieves highly-competitive performance on ImageNet against the state-of-the-art, outperforming a large number of modern convolutional neural networks that were designed by hand.
Yiming Yang (Chair)
Karen Simonyan (DeepMind)