We continue the study of the learnability of quantum measurement classes in the setting where the learner is given access only to prepared quantum states, aiming for necessary and sufficient conditions for PAC learnability, along with corresponding sample complexity bounds. In the quantum setting, in contrast with the classical probabilistically observed case, sampled states are perturbed when a quantum measurement is applied, according to the Born rule, so that distinct samples in the training data cannot be arbitrarily reused. We first probe the results from previous works on this setting. We show that the empirical risk defined in previous works and matching the definition in the classical theory can fail to satisfy the uniform convergence property enjoyed in the classical learning setting for classes that we can show to be PAC learnable. Moreover, we show that VC dimension generalization upper bounds in previous work are in many cases infinite, even for measurement classes defined on a finite-dimensional Hilbert space. We then show that, nonetheless, every measurement class defined on a finite-dimensional Hilbert space is PAC learnable via a modification of the ERM rule.

The sparse dictionary coding framework represents signals as a linear combination of a few predefined dictionary atoms. It has been employed for images, time series, graph signals and recently for 2-way (or 2D) spatio-temporal data employing jointly temporal and spatial dictionaries. Large and over-complete dictionaries enable high-quality models, but also pose scalability challenges which are exacerbated in multi-dictionary settings. Hence, an important problem that we address in this paper is: How to scale multi-dictionary coding for large dictionaries and datasets?We propose a multi-dictionary atom selection technique for low-rank sparse coding named LRMDS. To enable scalability to large dictionaries and datasets, it progressively selects groups of row-column atom pairs based on their alignment with the data and performs convex relaxation coding via the corresponding sub-dictionaries. We demonstrate both theoretically and experimentally that when the data has a low-rank encoding with a sparse subset of the atoms, LRMDS is able to select them with strong guarantees under mild assumptions. Furthermore, we demonstrate the scalability and quality of LRMDS in both synthetic and real-world datasets and for a range of coding dictionaries. It achieves 3 times to 10 times speed-up compared to baselines, while obtaining up to two orders of magnitude improvement in representation quality on some of the real world datasets given a fixed target number of atoms.

Symmetry detection has been shown to improve various machine learning tasks. In the context of continuous symmetry detection, current state of the art experiments are limited to the detection of affine transformations. Under the manifold assumption, we outline a framework for discovering continuous symmetry in data beyond the affine transformation group. We also provide a similar framework for discovering discrete symmetry. We experimentally compare our method to an existing method known as LieGAN and show that our method is competitive at detecting affine symmetries for large sample sizes and superior than LieGAN for small sample sizes. We also show our method is able to detect continuous symmetries beyond the affine group and is generally more computationally efficient than LieGAN.

MOTIVATION: Understanding the mechanisms and structural mappings between molecules and pathway classes are critical for design of reaction predictors for synthesizing new molecules. This article studies the problem of prediction of classes of metabolic pathways (series of chemical reactions occurring within a cell) in which a given biochemical compound participates. We apply a hybrid machine learning approach consisting of graph convolutional networks used to extract molecular shape features as input to a random forest classifier. In contrast to previously applied machine learning methods for this problem, our framework automatically extracts relevant shape features directly from input SMILES representations, which are atom-bond specifications of chemical structures composing the molecules. RESULTS: Our method is capable of correctly predicting the respective metabolic pathway class of 95.16% of tested compounds, whereas competing methods only achieve an accuracy of 84.92% or less. Furthermore, our framework extends to the task of classification of compounds having mixed membership in multiple pathway classes. Our prediction accuracy for this multi-label task is 95.62%. We analyze the relative importance of various global physicochemical features to the pathway class prediction problem and show that simple linear/logistic regression models can predict the values of these global features from the shape features extracted using our framework. AVAILABILITY AND IMPLEMENTATION: https://github.com/baranwa2/MetabolicPathwayPrediction.

We formulate a quantum analogue of the fundamental classical PAC learning problem. As on a quantum computer, we model data to be encoded by modifying specific attributes - spin axis of an electron, plane of polarization of a photon - of sub-atomic particles. Any interaction, including reading off, extracting or learning from such data is via quantum measurements, thus leading us to a problem of PAC learning Quantum Measurement Classes. We propose and analyze the sample complexity of a new ERM algorithm that respects quantum non-commutativity. Our study entails that we define the VC dimension of Positive Operator Valued Measure(ments) (POVMs) concept classes. Our sample complexity bounds involve optimizing over partitions of jointly measurable classes. Finally, we identify universally consistent sequences of POVM classes. Technical components of this work include computations involving tensor products, trace and uniform convergence bounds.

We consider infection/spreading process models on a graph in which infected nodes are associated with real-valued messages that evolve as they spread, according to a parametric probabilistic message spreading model. Estimation of the parameters of such models from an observed sample infection trajectory and associated messages presents computational and statistical challenges as a result of the fact that the set of neighbors that infected a given node is unobserved. This leads to a log likelihood function with exponentially many terms as a function of the number of infected neighbors of each node. We show that the log likelihood can be approximated using a local central limit theorem with provable accuracy and computational efficiency. We then show that under a well-posedness condition on the model, the maximum of the approximating function is close to the maximum of the true log likelihood, so that likelihood maximization can be approximately performed by maximizing the Gaussian approximation of the log likelihood.

BACKGROUND: Development of new methods for analysis of protein-protein interactions (PPIs) at molecular and nanometer scales gives insights into intracellular signaling pathways and will improve understanding of protein functions, as well as other nanoscale structures of biological and abiological origins. Recent advances in computational tools, particularly the ones involving modern deep learning algorithms, have been shown to complement experimental approaches for describing and rationalizing PPIs. However, most of the existing works on PPI predictions use protein-sequence information, and thus have difficulties in accounting for the three-dimensional organization of the protein chains. RESULTS: In this study, we address this problem and describe a PPI analysis based on a graph attention network, named Struct2Graph, for identifying PPIs directly from the structural data of folded protein globules. Our method is capable of predicting the PPI with an accuracy of 98.89% on the balanced set consisting of an equal number of positive and negative pairs. On the unbalanced set with the ratio of 1:10 between positive and negative pairs, Struct2Graph achieves a fivefold cross validation average accuracy of 99.42%. Moreover, Struct2Graph can potentially identify residues that likely contribute to the formation of the protein-protein complex. The identification of important residues is tested for two different interaction types: (a) Proteins with multiple ligands competing for the same binding area, (b) Dynamic protein-protein adhesion interaction. Struct2Graph identifies interacting residues with 30% sensitivity, 89% specificity, and 87% accuracy. CONCLUSIONS: In this manuscript, we address the problem of prediction of PPIs using a first of its kind, 3D-structure-based graph attention network (code available at https://github.com/baranwa2/Struct2Graph ). Furthermore, the novel mutual attention mechanism provides insights into likely interaction sites through its unsupervised knowledge selection process. This study demonstrates that a relatively low-dimensional feature embedding learned from graph structures of individual proteins outperforms other modern machine learning classifiers based on global protein features. In addition, through the analysis of single amino acid variations, the attention mechanism shows preference for disease-causing residue variations over benign polymorphisms, demonstrating that it is not limited to interface residues.

Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate their capabilities and limitations for graph classification, we investigate their power to generate well-separated embedding vectors for graphs sampled from different random graph models, which correspond to different class-conditional distributions in a classification problem. It has been recognized that metric properties of learned representations are important for reduction of complexity of classifiers trained on them. Additionally, we show that inability to generate well-separated embedding vectors for two different graph models implies information-theoretic indistinguishability of these models based on noise-perturbed embedding vectors of sample graphs. We consider graph models arising from graphons, which parametrize all infinite exchangeable graph models. We precisely characterize, in terms of degree profile closeness, the set of graphon pairs that are indistinguishable (in metric and information-theoretic senses) by a GCN with depth at least logarithmic in sample graph size. Outside this set, a very simple architecture suffices for distinguishability. We then exhibit a concrete, infinite set of graphon pairs that are well-separated in cut distance and are indistinguishable by a GCN. These results theoretically match empirical observations of several prior works. Finally, we give empirical results on synthetic and real graph classification datasets, giving some indication that degree profile closeness gives rise to indistinguishability of graph distributions in real datasets, even beyond our theoretical framework.

Graph convolutional networks are a popular representation learning method for graphs, wherein an input graph is mapped to a d-dimensional embedding vector, yielding a latent representation. We continue the project of theoretically elucidating the roles of various aspects of GCN architectures by studying the power and limitations of GCNs in distinguishing random graph models based on embedding vectors of sample graphs. In the present work, we show how the embedding dimension affects the set of pairs of models that can be distinguished from one another. We also consider the application of GCNs to multi-hypothesis testing and use channel capacity results to show a lower bound on how the embedding dimension must scale with respect to the number of hypotheses and the signal-to-noise ratio in order to guarantee a probability of error tending to 0.

Numerous networks in the real world change over time, in the sense that nodes and edges enter and leave the networks. Various dynamic random graph models have been proposed to explain the macroscopic properties of these systems and to provide a foundation for statistical inferences and predictions. It is of interest to have a rigorous way to determine how well these models match observed networks. We thus ask the following goodness of fit question: given a sequence of observations/snapshots of a growing random graph, along with a candidate model $M$, can we determine whether the snapshots came from $M$ or from some arbitrary alternative model that is well-separated from $M$ in some natural metric? We formulate this problem precisely and boil it down to goodness of fit testing for graph-valued, infinite-state Markov processes and exhibit and analyze a universal test based on non-stationary sampling for a natural class of models.

Graph convolutional networks (GCNs) are a widely used method for graph representation learning. To elucidate the capabilities and limitations of GCNs, we investigate their power, as a function of their number of layers, to distinguish between different random graph models (corresponding to different class-conditional distributions in a classification problem) on the basis of the embeddings of their sample graphs. In particular, the graph models that we consider arise from graphons, which are the most general possible parameterizations of infinite exchangeable graph models and which are the central objects of study in the theory of dense graph limits. We give a precise characterization of the set of pairs of graphons that are indistinguishable by a GCN with nonlinear activation functions coming from a certain broad class if its depth is at least logarithmic in the size of the sample graph. This characterization is in terms of a degree profile closeness property. Outside this class, a very simple GCN architecture suffices for distinguishability. We then exhibit a concrete, infinite class of graphons arising from stochastic block models that are well-separated in terms of cut distance and are indistinguishable by a GCN. These results theoretically match empirical observations of several prior works on GCNs. To prove our results, we exploit a connection to random walks on graphs.

Abstract We continue building up the information theory of non-sequential data structures such as trees, sets, and graphs. In this paper, we consider dynamic graphs generated by a full duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We ask how many bits are needed to describe the labeled and unlabeled versions of such graphs. We first estimate entropies of both versions and then present asymptotically optimal compression algorithms up to two bits. Interestingly, for the full duplication model the labeled version needs $$\Theta (n)$$ Θ(n) bits while its unlabeled version (structure) can be described by $$\Theta (\log n)$$ Θ(logn) bits due to significant amount of symmetry (i.e. large average size of the automorphism group of sample graphs).

MOTIVATION: Understanding the mechanisms and structural mappings between molecules and pathway classes are critical for design of reaction predictors for synthesizing new molecules. This article studies the problem of prediction of classes of metabolic pathways (series of chemical reactions occurring within a cell) in which a given biochemical compound participates. We apply a hybrid machine learning approach consisting of graph convolutional networks used to extract molecular shape features as input to a random forest classifier. In contrast to previously applied machine learning methods for this problem, our framework automatically extracts relevant shape features directly from input SMILES representations, which are atom-bond specifications of chemical structures composing the molecules. RESULTS: Our method is capable of correctly predicting the respective metabolic pathway class of 95.16% of tested compounds, whereas competing methods only achieve an accuracy of 84.92% or less. Furthermore, our framework extends to the task of classification of compounds having mixed membership in multiple pathway classes. Our prediction accuracy for this multi-label task is 97.61%. We analyze the relative importance of various global physicochemical features to the pathway class prediction problem and show that simple linear/logistic regression models can predict the values of these global features from the shape features extracted using our framework. AVAILABILITY AND IMPLEMENTATION: https://github.com/baranwa2/MetabolicPathwayPrediction. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We study structural properties of preferential attachment graphs (with parameter m ≥ 1 giving the number of attachment choices that each new vertex makes) which intervene in two complementary algorithmic/statistical/information-theoretic problems involving the information shared between a random graph's labels and its structure: in structural compression, we seek to compactly describe a graph's structure by a bit string, throwing away its label information; in node arrival order recovery, we seek to recover node labels, given only a graph structure. In particular, we study the typical size of the automorphism group, as well as some shape parameters (such as the number of linear extensions and height) of the directed version of the graph, which in turn allows us to estimate the typical number of admissible labeled representatives of a given graph structure. Our result on the automorphism group positively settles a conjecture to the effect that, provided that m ≥ 3, preferential attachment graphs are asymmetric with high probability, and completes the characterization of the number of symmetries for a broad range of parameters of the model (i.e., for all fixed m). These results allow us to give an algorithmically efficient, asymptotically optimal algorithm for compression of unlabeled preferential attachment graphs. To show the optimality of our scheme, we also derive new, precise estimates of the Shannon entropy of both the unlabeled and labeled version of the model. Our results also imply inapproximability results for the problem of node arrival order recovery.

We continue developing the information theory of structured data. In this article, we study models generating d -ary trees ( d ≥ 2) and trees with unrestricted degree. We first compute the entropy which gives us the fundamental lower bound on compression of such trees. Then we present efficient compression algorithms based on arithmetic encoding that achieve the entropy within a constant number of bits. A naïve implementation of these algorithms has a prohibitive time complexity of O ( n d ) elementary arithmetic operations (each corresponding to a number f ( n , d ) of bit operations), but our efficient algorithms run in O ( n 2 ) of these operations, where n is the number of nodes. It turns out that extending source coding (i.e., compression) from sequences to advanced data structures such as degree-unconstrained trees is mathematically quite challenging and leads to recurrences that find ample applications in the information theory of general structures (e.g., to analyze the information content of degree-unconstrained non-plane trees).

Inferring the node arrival sequence from a snapshot of a dynamic network is an important problem, with applications ranging from identifying sources of contagion to flow of capital in financial transaction networks. Variants of this problem have received significant recent research attention, including results on infeasibility of solution for prior formulations. We present a new formulation of the problem that admits probabilistic solutions for broad classes of dynamic network models. Instantiating our framework for a preferential attachment model, we present effectively computable and practically tight bounds on the tradeoff curve between optimal achievable precision and density/recall. We also present efficient algorithms for partial recovery of node arrival orders and derive theoretical and empirical performance bounds on the precision and density/recall of our methods in comparison to the best possible. We validate our methods through experiments on both synthetic and real networks to show that their performance is robust to model changes, and that they yield excellent results in practice. We also demonstrate their utility in the context of a novel application in analysis of the human brain connectome to draw new insights into the functional and structural organization and evolution of the human brain.

Compression schemes for advanced data structures have become a central modern challenge. Information theory has traditionally dealt with conventional data such as text, images, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [8]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version (where order of subtrees doesn't matter). Furthermore, we assume that each name is generated by a known memoryless source (horizontal independence), but a symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name (vertical Markovian dependency). Such a model is closely connected to models of phylogenetic trees. While in general the problem of multimodal compression and associated analysis can be extremely complicated, we find that in this natural setting, both the entropy analysis and optimal compression are analytically tractable. We evaluate the entropy for both types of trees. For the plane case, with or without vertex names, we find that a simple two-stage compression scheme is both efficient and optimal. We then present efficient and optimal compression algorithms for the more complicated non-plane case.

We continue developing the information theory of advanced data structures. In our previous work, we introduced structural entropy of unlabeled graphs and designed lossless compression algorithms for binary trees (with structure-correlated vertex names). In this paper, we consider d-ary trees (d ≥ 2) and trees with unrestricted degree for which we compute the entropy (the first step to design optimal compression algorithms). It turns out that extending from binary trees to general trees is mathematically quite challenging and leads to new recurrences that find ample applications in the information theory of structures.

Many networks in the real world are dynamic in nature: nodes enter, exit, and make and break connections with one another as time passes. Several random graph models of these networks are such that nodes have well-defined arrival times. It is natural to ask if, for a given random graph model, we can recover the arrival order of nodes, given information about the structure of the graph. In this work, we give a rigorous formulation of the problem in a statistical learning framework and tie its feasibility, for a broad class of models, to several sets of permutations associated with the symmetries of the random graph model and graphs generated by it. Moreover, we show how the same quantities are fundamental to the study of the information content of graph structures. We then apply our general results to the special cases of the Erdoos-Renyi and preferential attachment models to derive strong inapproximability results.

We rigorously study a channel that maps sequences from a finite alphabet to self-avoiding walks in the two-dimensional grid, inspired by a model of protein folding from statistical physics and studied empirically by biophysicists. This channel, which we call the Boltzmann sequence-structure channel, is characterized by a Boltzmann/Gibbs distribution with a free parameter corresponding to temperature. In our previous work, we verified empirically that the channel capacity appears to have a phase transition for small temperature and decays to zero for high temperature. In this paper, we make some progress toward theoretically explaining these phenomena. We first estimate the conditional entropy between the input sequence and the output fold, giving an upper bound which exhibits a phase transition with respect to temperature. Next, we formulate a class of parameter settings under which the dependence between walk energies is governed by their number of shared contacts. In this setting, we derive a lower bound on the conditional entropy. This lower bound allows us to conclude that the mutual information tends to zero in a nontrivial regime of high temperature, giving some support to the empirical fact regarding capacity. Finally, we construct an example setting of the parameters of the model for which the conditional entropy is exactly calculable and which does not exhibit a phase transition.

We rigorously study a channel that maps binary sequences to self-avoiding walks in the two-dimensional grid, inspired by a model of protein statistics. This channel, which we also call the Boltzmann sequence-structure channel, is characterized by a Boltzmann/Gibbs distribution with a free parameter corresponding to temperature. In our previous work, we verified experimentally that the channel capacity has a phase transition for small temperature and decays to zero for high temperature. In this paper, we make some progress towards explaining these phenomena. We first upper bound the conditional entropy between the input sequence and the output which exhibits a phase transition with respect to temperature. Then we derive a lower bound on the conditional entropy for some specific set of parameters. This lower bound allows us to conclude that the mutual information tends to zero for high temperature.

Compression schemes for advanced data structures have become the challenge of today. Information theory has traditionally dealt with conventional data such as text, image, or video. In contrast, most data available today is multi-type and context dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [1]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version. Furthermore, we assume that each symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name. We first evaluate the entropy for both types of trees. Then we propose for known sources two compression schemes COMPRESSPTREE for plane trees with correlated names, and COMPRESSNPTREE for non-plane trees. We show that these schemes achieve the lower bound within two bits.