iLunch Talk (Oct 23):  Fundamental Limits of Graph Convolutional Networks of Moderate Depth 

What: Fundamental Limits of Graph Convolutional Networks of Moderate Depth 

When: Friday October 23, 12 noon – 1:00 pm

Where: Zoom Meeting ID: 894 9387 1010  Password: 119468

Who: Abram Manger
Affiliation: Assistant Professor in the Department of Computer Science at the University at Albany, SUNY.

Abstract: Graph convolutional networks (GCNs) are a widely used method for graph representation learning.

To elucidate the capabilities and limitations of GCNs, we investigate their power, as a function of their number of layers, to distinguish between different random graph models (corresponding to different class-conditional distributions in a classification problem) on the basis of the embeddings of their sample graphs. In particular, the graph models that we consider arise from graphons, which are the most general possible parameterizations of infinite exchangeable graph models and which are the central objects of study in the theory of dense graph limits. We give a precise characterization of the set of pairs of graphons that are indistinguishable by a GCN with nonlinear activation functions coming from a certain broad class of its depth is at least logarithmic in the size of the sample graph. The characterization is in terms of a degree profile closeness property. Outside the class, a very simple GCN architecture suffices for distinguishability. We then exhibit a concrete, infinite class of graphons arising from stochastic block models that are well-separated in terms of cut distance and are indistinguishable by a GCN. These results theoretically match empirical observations of several prior works on GCNs. To prove our results, we exploit a connection to random walks on graphs.

Bio: Abram Magner is an assistant professor in the Department of Computer Science at the University at Albany, SUNY. Prior to that, he held postdoctoral fellowships in the Department of EECS at the University of Michigan and in the Coordinated Science Lab at the University of Illinois at Urbana-Champaign. His

interests are in theoretical machine learning, probabilistic inference problems on graphs and other random structures, and information theory.

Host: School of Computing and Information Science, University of Maine

For questions: