PhD Seminar • Machine Learning • Effects of Graph Convolutions on Linear Separability and Generalization

Please note: This PhD seminar will take place online.

Aseem Baranwal, PhD candidate
David R. Cheriton School of Computer Science

Supervisors: Professors Kimon Fountoulakis, Aukosh Jagannath

We study the classification of a mixture of Gaussians, where the data corresponds to the node attributes of a stochastic block model. We show that graph convolution extends the regime in which the data is linearly separable by a factor of roughly 1/D^0.5, where D is the expected degree of a node, as compared to the mixture model data on its own. Furthermore, we find that the linear classifier obtained by minimizing the cross-entropy loss after the graph convolution generalizes to out-of-distribution data where the unseen data can have different intra- and inter-class edge probabilities from the training data.

Based on the paper: Graph convolution for Semi-Supervised Classification: Separability and OoD Generalization. A. Baranwal, K. Fountoulakis, A. Jagannath. Proceedings of the 38^th International Conference on Machine Learning, Proceedings of Machine Learning Research Vol. 139684–693, 2021.

Attend this PhD seminar on Zoom.