Publications

Group highlights

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

Effects of Graph Convolutions in Deep Networks

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

arXiv:2204.09297

(Preprint) (Code)

Graph Attention Retrospective

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

arXiv:2202.13060

(Preprint) (Code) (Video)

Best paper award at the GroundedML workshop at ICLR 2022.

 

Full List

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