(For a full list see below or go to Google Scholar

Graph Convolutional Networks (GCNs) are one of the most popular architectures that are used to solve classification problems accompanied by graphical information. We present a rigorous theoretical understanding of the effects of graph convolutions in multi-layer networks. We study these effects through the node classification problem of a non-linearly separable Gaussian mixture model coupled with a stochastic block model. First, we show that a single graph convolution expands the regime of the distance between the means where multi-layer networks can classify the data by a factor of at least 1/(E[deg])^(1/4), where E[deg] denotes the expected degree of a node. Second, we show that with a slightly stronger graph density, two graph convolutions improve this factor to at least 1/n^(1/4), where n is the number of nodes in the graph. Finally, we provide both theoretical and empirical insights into the performance of graph convolutions placed in different combinations among the layers of a neural network, concluding that the performance is mutually similar for all combinations of the placement. We present extensive experiments on both synthetic and real-world data that illustrate our results.

*A. Baranwal, K. Fountoulakis, A. Jagannath*

** **

Graph-based learning is a rapidly growing sub-field of machine learning with applications in social networks, citation networks, and bioinformatics. One of the most popular type of models is graph attention networks. These models were introduced to allow a node to aggregate information from the features of neighbor nodes in a non-uniform way in contrast to simple graph convolution which does not distinguish the neighbors of a node. In this paper, we study theoretically this expected behaviour of graph attention networks. We prove multiple results on the performance of the graph attention mechanism for the problem of node classification for a contextual stochastic block model. Here the features of the nodes are obtained from a mixture of Gaussians and the edges from a stochastic block model where the features and the edges are coupled in a natural way. First, we show that in an “easy” regime, where the distance between the means of the Gaussians is large enough, graph attention maintains the weights of intra-class edges and significantly reduces the weights of the inter-class edges. As a corollary, we show that this implies perfect node classification independent of the weights of inter-class edges. However, a classical argument shows that in the “easy” regime, the graph is not needed at all to classify the data with high probability. In the “hard” regime, we show that every attention mechanism fails to distinguish intra-class from inter-class edges. We evaluate our theoretical results on synthetic and real-world data.

*K. Fountoulakis, A. Levi, S. Yang, A. Baranwal, A. Jagannath*

** **

Best paper award at the GroundedML workshop at ICLR 2022.

Effects of Graph Convolutions in Deep Networks

*A. Baranwal, K. Fountoulakis, A. Jagannath *

arXiv:2204.09297

(Preprint)
(Code)

Graph Attention Retrospective

*K. Fountoulakis, A. Levi, S. Yang, A. Baranwal, A. Jagannath *

arXiv:2202.13060

(Preprint)
(Code)
(Video)

Local Hyper-flow Diffusion

*K. Fountoulakis, P. Li, S. Yang *

Conference on Neural Information Processing Systems (NeurIPS) 2021

(Preprint)
(Code)
(Video)

Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization

*A. Baranwal, K. Fountoulakis, A. Jagannath *

International Conference on Machine Learning (ICML) 2021

(Preprint)
(Code)
(Video, time 1:03:34)

Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks

*S. Yang, P. Senapati, D. Wang, C. T. Bauch, K. Fountoulakis *

PLOS Computational Biology

(Preprint)
(Code)

p-Norm Flow Diffusion for Local Graph Clustering

*K. Fountoulakis, D. Wang, S. Yang *

International Conference on Machine Learning (ICML) 2020

(Preprint)
(Code)
(Video)

Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance

*K. Fountoulakis, M. Liu, D. F. Gleich, M. W. Mahoney *

arXiv:2004.09608 (Accepted at SIAM Review)

(Code)

Statistical Guarantees for Local Graph Clustering (Long version at JMLR)

*W. Ha, K. Fountoulakis, M. W. Mahoney *

Journal of Machine Learning Research

(Preprint)

Statistical Guarantees for Local Graph Clustering

*W. Ha, K. Fountoulakis, M. W. Mahoney *

International Conference on Artificial Intelligence and Statistics (AISTATS) 2020

(Preprint)

Parallel and Communication Avoiding Least Angle Regression

*S. Das, J. Demmel, K. Fountoulakis, L. Grigori, M. W. Mahoney, S. Yang *

SIAM Journal on Scientific Computing

(Preprint)

Locality And Structure Aware Graph Node Embedding

*E. Faerman, F. Borutta, K. Fountoulakis, M. W. Mahoney *

International Conference on Web Intelligence 2018 (Best student paper award)

(Preprint)

A Flexible Coordinate Descent Method

*K. Fountoulakis, R. Tappenden *

Computational Optimization and Applications

(Preprint)

Avoiding Synchronization in First-Order Methods for Sparse Convex Optimization

*A. Devarakonda, K. Fountoulakis, J. Demmel, M. Mahoney *

International Parallel and Distributed Processing Symposium (IPDPS) 2018

(Preprint)
(Video)

Variational Perspective on Local Graph Clustering

*K. Fountoulakis, F. Roosta-Khorasani, J. Shun, X. Cheng, M. Mahoney *

Mathematical Programming

(Preprint)
(Video)

Capacity Releasing Diffusion for Speed and Locality

*D. Wang, K. Fountoulakis, M. Henzinger, M. Mahoney, S. Rao *

International Conference on Machine Learning (ICML) 2017

(Preprint)
(Video)

Avoiding communication in primal and dual block coordinate descent methods

*A. Devarakonda, K. Fountoulakis, J. Demmel, M. Mahoney *

SIAM Journal on Scientific Computing (SISC)

(Preprint)
(Video)

A Randomized Rounding Algorithm for Sparse PCA

*K. Fountoulakis, A. Kundu, E. M. Kontopoulou, P. Drineas *

ACM Transactions on Knowledge Discovery from Data

(Preprint)

An Optimization Approach to Locally-Biased Graph Algorithms

*K. Fountoulakis, D. Gleich, M. Mahoney *

Proceedings of the IEEE

(Preprint)
(Video)

Performance of First- and Second-Order Methods for L1-Regularized Least Squares Problems

*K. Fountoulakis, J. Gondzio *

Computational Optimization and Applications

(Preprint)
(Code)

A Second-Order Method for Strongly-Convex L1-Regularization Problems

*K. Fountoulakis, J. Gondzio *

Mathematical Programming

(Preprint)

Parallel Local Graph Clustering

*J. Shun, F. Roosta-Khorasani, K. Fountoulakis, M. Mahoney *

Proceedings of the VLDB Endowment (VLDB) 2016

(Preprint)

A Preconditioner for a Primal-dual Newton Conjugate Gradients Method for Compressed Sensing Problems

*I. Dassios, K. Fountoulakis, J. Gondzio *

SIAM Journal on Scientific Computing (SISC)

(Preprint)
(Code)

Matrix-free interior point method for compressed sensing problems

*K. Fountoulakis, J. Gondzio, P. Zhlobich *

Mathematical Programming Computation

(Preprint)
(Code)

Higher-Order Methods for Large-Scale Optimization

*K. Fountoulakis *

Kimon Fountoulakis’ PhD Thesis