Random walk models of graphs and the open problem of invariance in networks
Abstract
The best-understood statistical models of graphs and networks are models based on exchangeable graphs. These are tractable by the standards of random graph models, but inherently (and provably) misspecified for sparse network data — a graph generated from such a model would bear no resemblance to most networks arising in applications. Developing non-exchangeable models is much more difficult, both mathematically and in terms of inference. I will review the exchangeable case, present a particular type of non-exchangeable model that is statistically tractable, and discuss the more general problem of invariance in networks — roughly, what is the sparse counterpart to an exchangeable graph? — which remains unsolved.
Background
Dr. Orbanz is an Assistant Professor in the Department of Statistics at Columbia University. Before going to New York, he was a Research Fellow in the Machine Learning Group of Zoubin Ghahramani at the University of Cambridge, and previously a graduate student of Joachim M. Buhmann at ETH Zurich.
Research Interests
His main research interest are the statistics of discrete objects and structures: permutations, graphs, partitions, binary sequences. Most of his recent work concerns representation problems and latent variable algorithms in Bayesian nonparametrics. More generally, he is interested in all mathematical aspects of machine learning and artificial intelligence.