27 citations · 112 across the 30 of their papers we have counts for
34 papers
Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
Artur Back de Luca, Kimon Fountoulakis
As state-of-the-art neural networks are deployed on reasoning and algorithmic tasks, exactness guarantees become increasingly important. However, high average-case accuracy can sti…
Complexity of Classical Acceleration for -Regularized PageRank
Kimon Fountoulakis, David Martínez-Rubio
We study the degree-weighted work required to compute -regularized PageRank using the standard accelerated proximal-gradient method (FISTA). For non-accelerated methods (IS…
Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
Muhammad Fetrat Qharabagh, Artur Back de Luca, George Giapitzakis +1
Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact l…
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani +1
Semiautomata form a rich class of sequence-processing algorithms with applications in natural language processing, robotics, computational biology, and data mining. We establish th…
Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Artur Back de Luca, George Giapitzakis, Kimon Fountoulakis
Neural networks are known for their ability to approximate smooth functions, yet they fail to generalize perfectly to unseen inputs when trained on discrete operations. Such operat…
LVLM-COUNT: Enhancing the Counting Ability of Large Vision-Language Models
Muhammad Fetrat Qharabagh, Mohammadreza Ghofrani, Kimon Fountoulakis
Counting is a fundamental operation for various real-world visual tasks, requiring both object recognition and robust counting capabilities. Despite their advanced visual perceptio…
Positional Attention: Expressivity and Learnability of Algorithmic Computation
Artur Back de Luca, George Giapitzakis, Shenghao Yang +2
There is a growing interest in the ability of neural networks to execute algorithmic tasks (e.g., arithmetic, summary statistics, and sorting). The goal of this work is to better u…
Analysis of Corrected Graph Convolutions
Robert Wang, Aseem Baranwal, Kimon Fountoulakis
Machine learning for node classification on graphs is a prominent area driven by applications such as recommendation systems. State-of-the-art models often use multiple graph convo…
Simulation of Graph Algorithms with Looped Transformers
Artur Back de Luca, Kimon Fountoulakis
The execution of graph algorithms using neural networks has recently attracted significant interest due to promising empirical progress. This motivates further understanding of how…
Local Graph Clustering with Noisy Labels
Artur Back de Luca, Kimon Fountoulakis, Shenghao Yang
The growing interest in machine learning problems over graphs with additional node information such as texts, images, or labels has popularized methods that require the costly oper…
Optimality of Message-Passing Architectures for Sparse Graphs
Aseem Baranwal, Kimon Fountoulakis, Aukosh Jagannath
We study the node classification problem on feature-decorated graphs in the sparse setting, i.e., when the expected degree of a node is in the number of nodes, in the fixed-…
Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical Guarantees
Shenghao Yang, Kimon Fountoulakis
Local graph clustering methods aim to detect small clusters in very large graphs without the need to process the whole graph. They are fundamental and scalable tools for a wide ran…
On Classification Thresholds for Graph Attention with Edge Features
Kimon Fountoulakis, Dake He, Silvio Lattanzi +3
The recent years we have seen the rise of graph neural networks for prediction tasks on graphs. One of the dominant architectures is graph attention due to its ability to make pred…
Effects of Graph Convolutions in Multi-layer Networks
Aseem Baranwal, Kimon Fountoulakis, Aukosh Jagannath
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 rigo…
Graph Attention Retrospective
Kimon Fountoulakis, Amit Levi, Shenghao Yang +2
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 models…
Local Hyper-Flow Diffusion
Kimon Fountoulakis, Pan Li, Shenghao Yang
Recently, hypergraphs have attracted a lot of attention due to their ability to capture complex relations among entities. The insurgence of hypergraphs has resulted in data of incr…
Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization
Aseem Baranwal, Kimon Fountoulakis, Aukosh Jagannath
Recently there has been increased interest in semi-supervised classification in the presence of graphical information. A new class of learning models has emerged that relies, at it…
Targeted Pandemic Containment Through Identifying Local Contact Network Bottlenecks
Shenghao Yang, Priyabrata Senapati, Di Wang +2
Decision-making about pandemic mitigation often relies upon simulation modelling. Models of disease transmission through networks of contacts--between individuals or between popula…
-Norm Flow Diffusion for Local Graph Clustering
Kimon Fountoulakis, Di Wang, Shenghao Yang
Local graph clustering and the closely related seed set expansion problem are primitives on graphs that are central to a wide range of analytic and learning tasks such as local clu…
Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
K. Fountoulakis, M. Liu, D. F. Gleich +1
Clustering points in a vector space or nodes in a graph is a ubiquitous primitive in statistical data analysis, and it is commonly used for exploratory data analysis. In practice,…
Statistical guarantees for local graph clustering
Wooseok Ha, Kimon Fountoulakis, Michael W. Mahoney
Local graph clustering methods aim to find small clusters in very large graphs. These methods take as input a graph and a seed node, and they return as output a good cluster in a r…
Parallel and Communication Avoiding Least Angle Regression
S. Das, J. Demmel, K. Fountoulakis +3
We are interested in parallelizing the Least Angle Regression (LARS) algorithm for fitting linear regression models to high-dimensional data. We consider two parallel and communica…
A Short Introduction to Local Graph Clustering Methods and Software
Kimon Fountoulakis, David F. Gleich, Michael W. Mahoney
Graph clustering has many important applications in computing, but due to the increasing sizes of graphs, even traditionally fast clustering methods can be computationally expensiv…
Avoiding Synchronization in First-Order Methods for Sparse Convex Optimization
Aditya Devarakonda, Kimon Fountoulakis, James Demmel +1
Parallel computing has played an important role in speeding up convex optimization methods for big data analytics and large-scale machine learning (ML). However, the scalability of…