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.
Vector Approximate Message Passing is a computationally-efficient iterative algorithm for estimation in high-dimensional regression problems. Due to the presence of an ‘Onsager’ correction term in its iterates, for a wide class of N by M design matrices, namely those that are right orthogonally-invariant, the asymptotic distribution of the algorithm’s estimate of the signal at any iteration can be exactly characterized in the large system limit as M/N → δ ∈ (0,∞) via a scalar recursion referred to as state evolution. In this paper, we show that appropriate functionals of the iterates in fact concentrate around their limiting values predicted by these asymptotic distributions with rates exponentially fast in N.
We address the problem of online state and parameter estimation in the Hierarchical Gaussian Filter (HGF), which is a multi-layer dynamic model with non-conjugate couplings between upper-layer hidden states and parameters of a lower layer. These non-conjugacies necessitate the approximation of marginalization and expectation integrals, while the online inference constraint renders batch learning and Monte Carlo sampling unsuitable. Here we formulate the problem as a message passing task on a factor graph and propose an online variational message passing-based state and parameter tracking algorithm, which uses Gaussian quadrature to deal with non-conjugacies. We present improved message update rules for all non-conjugate couplings, thus allowing a plug-in inference method for alternative models with equivalent non-conjugate layer couplings. The method is validated on a recorded time series of Bitcoin prices.
Many important schemes in signal processing and communications, ranging from the BCJR algorithm to the Kalman filter, are instances of factor graph methods. This family of algorithms is based on recursive message passing-based computations carried out over graphical models, representing a factorization of the underlying statistics. In order to implement these algorithms, one must have accurate knowledge of the statistical model of the underlying signals. In this work we implement factor graph methods in a data-driven manner when the statistics are unknown. In particular, we propose using machine learning (ML) tools to learn the factor graph, instead of the overall system task, which in turn is used for inference by message passing over the learned graph. We apply the proposed approach to learn the factor graph representing a finite-memory channel, demonstrating the resulting ability to implement BCJR detection in a data-driven fashion. We demonstrate that the proposed system, referred to as BCJRNet, learns to implement the BCJR algorithm from a small training set, and that the resulting receiver exhibits improved robustness to inaccurate training compared to the conventional channel-model-based receiver operating under the same level of uncertainty. Our results indicate that by utilizing ML tools to learn factor graphs from labeled data, one can implement a broad range of model-based algorithms, which traditionally require full knowledge of the underlying statistics, in a data-driven fashion.