More Like this

1. Deep Bucket Elimination

   https://doi.org/10.24963/ijcai.2021/582  

   Razeghi, Yasaman; Kask, Kalev; Lu, Yadong; Baldi, Pierre; Agarwal, Sakshi; Dechter, Rina (August 2021, International Joint Conference of Artificial Intelligence {ijcai})

   null (Ed.)

   Bucket Elimination (BE) is a universal inference scheme that can solve most tasks over probabilistic and deterministic graphical models exactly.However, it often requires exponentially high levels of memory (in the induced-width) preventing its execution. In the spirit of exploiting Deep Learning for inference tasks, in this paper, we will use neural networks to approximate BE.The resulting Deep Bucket Elimination (DBE) algorithm is developed for computing the partition function.We provide a proof-of-concept empirically using instances from several different benchmarks, showing that DBE can be a more accurate approximation than current state-of-the-art approaches for approximating BE (e.g. the mini-bucket schemes), especially when problems are sufficiently hard. 

   more » « less
2. Pulse Generation Based on a Microstrip Circuit with Fourth Order Degenerate Band Edge

   Dmitry Oshmarin, Alireza Nikzamir (June 2022, arXivorg)

   A pulse generation scheme is proposed based on a structured resonance in a cavity where the non-conventional energy distribution is concentrated in its middle part. The cavity is first used as an oscillator during the energy charging step and when a switch is activated the signal is extracted from its center. The key component of the proposed scheme is the periodic microstrip waveguide with a fourth-order degenerate band edge (DBE) of its wavenumber-frequency dispersion diagram. The DBE is an exceptional point degeneracy condition that is responsible for the energy to be localized at the cavity center and that can also have the quality factor easily destroyed by a perturbation. The waveguide is designed to have a DBE frequency of 2.86 GHz and produces pulses of approximately 0.1 V peak and 1.1 ns width. 

   more » « less
3. Fast Fourier Transform Reductions for Bayesian Network Inference

   Hsiao, Vincent; Nau, Dana S.; Dechter, Rina (January 2022, AI & Statistics, PMLR)

   Camps-Valls, Gustau; Ruiz, Francisco J.; Valera, Isabel (Ed.)

   Bayesian Networks are useful for analyzing the properties of systems with large populations of interacting agents (e.g., in social modeling applications and distributed service applications). These networks typically have large functions (CPTs), making exact inference intractable. However, often these models have additive symmetry. In this paper we show how summation-based CPTs, especially in the presence of symmetry, can be computed efficiently through the usage of the Fast Fourier Transform (FFT). In particular, we propose an efficient method using the FFT for reducing the size of Conditional Probability Tables (CPTs) in Bayesian Networks with summation-based causal independence (CI). We show how to apply it directly towards the acceleration of Bucket Elimination, and we subsequently provide experimental results demonstrating the computational speedup provided by our method. 

   more » « less
4. FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Analysis

   Huang, Baihe; Li, Xiaoxiao; Song, Zhao; Yang, Xin (July 2021, Proceedings of Machine Learning Research)

   Meila, Marina; Zhang, Tong (Ed.)

   Federated Learning (FL) is an emerging learning scheme that allows different distributed clients to train deep neural networks together without data sharing. Neural networks have become popular due to their unprecedented success. To the best of our knowledge, the theoretical guarantees of FL concerning neural networks with explicit forms and multi-step updates are unexplored. Nevertheless, training analysis of neural networks in FL is non-trivial for two reasons: first, the objective loss function we are optimizing is non-smooth and non-convex, and second, we are even not updating in the gradient direction. Existing convergence results for gradient descent-based methods heavily rely on the fact that the gradient direction is used for updating. The current paper presents a new class of convergence analysis for FL, Federated Neural Tangent Kernel (FL-NTK), which corresponds to overparamterized ReLU neural networks trained by gradient descent in FL and is inspired by the analysis in Neural Tangent Kernel (NTK). Theoretically, FL-NTK converges to a global-optimal solution at a linear rate with properly tuned learning parameters. Furthermore, with proper distributional assumptions, FL-NTK can also achieve good generalization. The proposed theoretical analysis scheme can be generalized to more complex neural networks. 

   more » « less
5. SkipGNN: predicting molecular interactions with skip-graph networks

   https://doi.org/10.1038/s41598-020-77766-9  

   Huang, Kexin; Xiao, Cao; Glass, Lucas M.; Zitnik, Marinka; Sun, Jimeng (December 2020, Scientific Reports)

   null (Ed.)

   Abstract Molecular interaction networks are powerful resources for molecular discovery. They are increasingly used with machine learning methods to predict biologically meaningful interactions. While deep learning on graphs has dramatically advanced the prediction prowess, current graph neural network (GNN) methods are mainly optimized for prediction on the basis of direct similarity between interacting nodes. In biological networks, however, similarity between nodes that do not directly interact has proved incredibly useful in the last decade across a variety of interaction networks. Here, we present SkipGNN, a graph neural network approach for the prediction of molecular interactions. SkipGNN predicts molecular interactions by not only aggregating information from direct interactions but also from second-order interactions, which we call skip similarity. In contrast to existing GNNs, SkipGNN receives neural messages from two-hop neighbors as well as immediate neighbors in the interaction network and non-linearly transforms the messages to obtain useful information for prediction. To inject skip similarity into a GNN, we construct a modified version of the original network, called the skip graph. We then develop an iterative fusion scheme that optimizes a GNN using both the skip graph and the original graph. Experiments on four interaction networks, including drug–drug, drug–target, protein–protein, and gene–disease interactions, show that SkipGNN achieves superior and robust performance. Furthermore, we show that unlike popular GNNs, SkipGNN learns biologically meaningful embeddings and performs especially well on noisy, incomplete interaction networks. 

   more » « less