publications

2024

1. NeurIPS

   Analysis of Corrected Graph Convolutions

   R. Wang, A. Baranwal, K. Fountoulakis. Thirty-eighth Conference on Neural Information Processing Systems, 2024

   Abstract Preprint

   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 convolutions on the data, as empirical evidence suggests they can enhance performance. However, it has been shown empirically and theoretically, that too many graph convolutions can degrade performance significantly, a phenomenon known as oversmoothing. In this paper, we provide a rigorous theoretical analysis, based on the contextual stochastic block model (CSBM), of the performance of vanilla graph convolution from which we remove the principal eigenvector to avoid oversmoothing. We perform a spectral analysis for \(k\) rounds of corrected graph convolutions, and we provide results for partial and exact classification. For partial classification, we show that each round of convolution can reduce the misclassification error exponentially up to a saturation level, after which performance does not worsen. For exact classification, we show that the separability threshold can be improved exponentially up to \(O(\log n / \log(\log n))\) corrected convolutions.

2023

1. NeurIPS

   Optimality of Message-Passing Architectures for Sparse Graphs

   A. Baranwal, K. Fountoulakis, A. Jagannath. Thirty-seventh Conference on Neural Information Processing Systems, 2023

   Abstract Preprint Code Poster

   We study the node classification problem on feature-decorated graphs in the sparse setting, i.e., when the expected degree of a node is \(O(1)\) in the number of nodes, in the fixed-dimensional asymptotic regime, i.e., the dimension of the feature data is fixed while the number of nodes is large. Such graphs are typically known to be locally tree-like. We introduce a notion of Bayes optimality for node classification tasks, called asymptotic local Bayes optimality, and compute the optimal classifier according to this criterion for a fairly general statistical data model with arbitrary distributions of the node features and edge connectivity. The optimal classifier is implementable using a message-passing graph neural network architecture. We then compute the generalization error of this classifier and compare its performance against existing learning methods theoretically on a well-studied statistical model with naturally identifiable signal-to-noise ratios (SNRs) in the data. We find that the optimal message-passing architecture interpolates between a standard MLP in the regime of low graph signal and a typical convolution in the regime of high graph signal. Furthermore, we prove a corresponding non-asymptotic result.

2. JMLR

   Graph Attention Retrospective

   K. Fountoulakis, A. Levi, S. Yang, A. Baranwal, A. Jagannath. Journal of Machine Learning Research Vol. 241–52, 2023

   Abstract Preprint Code talk

   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 is graph attention networks. They were introduced to allow a node to aggregate information from 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 theoretically study the 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 node features are obtained from a mixture of Gaussians and the edges from a stochastic block model. We show that in an "easy" regime, where the distance between the means of the Gaussians is large enough, graph attention is able to distinguish inter-class from intra-class edges. Thus it maintains the weights of important edges and significantly reduces the weights of unimportant edges. Consequently, we show that this implies perfect node classification. In the "hard" regime, we show that every attention mechanism fails to distinguish intra-class from inter-class edges. In addition, we show that graph attention convolution cannot (almost) perfectly classify the nodes even if intra-class edges could be separated from inter-class edges. Beyond perfect node classification, we provide a positive result on graph attention’s robustness against structural noise in the graph. In particular, our robustness result implies that graph attention can be strictly better than both the simple graph convolution and the best linear classifier of node features. We evaluate our theoretical results on synthetic and real-world data.

3. ICLR

   Effects of Graph Convolutions in Multi-layer Networks

   A. Baranwal, K. Fountoulakis, A. Jagannath. International Conference on Learning Representations, 2023 (spotlight)

   Abstract Preprint Code Slides talk

   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/\sqrt[4]∆\), where \(∆\) 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/\sqrt[4]n\), 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 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.

4. DMTCS

   Antisquares and Critical Exponents

   A. Baranwal, J. Currie, L. Mol, P. Ochem, N. Rampersad, J. Shallit. Discrete Mathematics & Theoretical Computer Science Vol. 25:2, 2023

   Abstract Preprint

   The complement \(\bar{x}\) of a binary word \(x\) is obtained by changing each \(0\) in \(x\) to \(1\) and vice versa. An antisquare is a nonempty word of the form \(x\bar{x}\). In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is \((5+\sqrt5)/2\). We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a large number. We say a binary word is good if the only antisquares it contains are \(01\) and \(10\). We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length \(n\) and determine the repetition threshold between polynomial and exponential growth for the number of good words.

2021

1. ICML

   Graph convolution for Semi-Supervised Classification: Separability and OoD Generalization

   A. Baranwal, K. Fountoulakis, A. Jagannath. Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research Vol. 139684–693, 2021 (spotlight)

   Abstract Preprint Code Poster Slides talk

   We study the classification of a mixture of Gaussians, where the data corresponds to the node attributes of a stochastic block model. We show that graph convolution extends the regime in which the data is linearly separable by a factor of roughly \(1/\sqrt D\), where \(D\) is the expected degree of a node, as compared to the mixture model data on its own. Furthermore, we find that the linear classifier obtained by minimizing the cross-entropy loss after the graph convolution generalizes to out-of-distribution data where the unseen data can have different intra- and inter-class edge probabilities from the training data.

2. TCS

   Ostrowski-Automatic Sequences: Theory and Applications

   A. Baranwal, L. Schaeffer, J. Shallit. Theoretical Computer Science Vol. 858122-142, 2021

   Abstract Code

   We extend the notion of \(k\)-automatic sequences to Ostrowski-automatic sequences, and develop a procedure to computationally decide certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. Our primary contribution is the design and implementation of an adder recognizing addition in a generalized Ostrowski numeration system. We also provide applications of our work to several topics in combinatorics on words.

2020

1. THESIS

   Decision Algorithms for Ostrowski-Automatic Sequences

   A. Baranwal. MMath Thesis, Univeristy of Waterloo, 2020

   Abstract Slides

   We extend the notion of automatic sequences to a broader class, the Ostrowski-automatic sequences. We develop a procedure for computationally deciding certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. In Chapter 1, we begin with topics and ideas that are preliminary to this work, including a small introduction to non-standard positional numeration systems and the relationship between words and automata. In Chapter 2, we define the theoretical foundations for recognizing addition in a generalized Ostrowski numeration system and formalize the general theory that develops our decision procedure. Next, in Chapter 3, we show how to implement these ideas in practice, and provide the implementation as an integration to the automatic theorem-proving software package – Walnut. Further, we provide some applications of our work in Chapter 4. These applications span several topics in combinatorics on words, including repetitions, pattern-avoidance, critical exponents of special classes of words, properties of Lucas words, and so forth. Finally, we close with open problems on decidability and higher-order numeration systems and discuss future directions for research.

2019

1. WORDS

   Repetitions in infinite palindrome-rich words

   A. Baranwal, J. Shallit. Combinatorics on Words, Lecture Notes in Computer Science Vol. 1168293–105, 2019

   Abstract Preprint Slides

   Rich words are those containing the maximum possible number of distinct palindromes. Several characteristic properties of rich words have been studied; yet the analysis of repetitions in rich words still involves some interesting open problems. We consider lower bounds on the repetition threshold of infinite rich words over 2- and 3-letter alphabets, and construct a candidate infinite rich word over the alphabet \(\Sigma_2=\{0,1\}\) with a small critical exponent of \(2+\sqrt2/2\). This represents the first progress on an open problem of Vesti from 2017.

2. WORDS

   Critical exponent of infinite balanced words via the Pell number system

   A. Baranwal, J. Shallit. Combinatorics on Words, Lecture Notes in Computer Science Vol. 1168280–92, 2019

   Abstract Preprint

   In a recent paper of Rampersad et al., the authors conjectured that the smallest possible critical exponent of an infinite balanced word over a \(5\)-letter alphabet is \(3/2\). We prove this result, using a formulation of first-order logic, the Pell number system, and a machine computation based on finite-state automata.