pwc-archive/papers-with-abstracts huggingface dataset:
Genome Sequence Reconstruction Using Gated Graph Convolutional Network
Authors: Lovro Vrček, Robert Vaser, Thomas Laurent, Mile Sikic, Xavier Bresson
Date: 2021-09-29 00:00:00

A quest to determine the human DNA sequence from telomere to telomere started three decades ago and was finally finished in 2021. This accomplishment was a result of a tremendous effort of numerous experts with an abundance of data, various tools, and often included manual inspection during genome reconstruction. Therefore, such method could hardly be used as a general approach to assembling genomes, especially when the assembly speed is important. Motivated by this achievement and aspiring to make it more accessible, we investigate a previously untaken path of applying geometric deep learning to the central part of the genome assembly---untangling a large assembly graph from which a genomic sequence needs to be reconstructed. A graph convolutional network is trained on a dataset generated from human genomic data to reconstruct the genome by finding a path through the assembly graph. We show that our model can compute scores from the lengths of the overlaps between the sequences and the graph topology which, when traversed with a greedy search algorithm, outperforms the greedy search over the overlap lengths only. Moreover, our method reconstructs the correct path through the graph in the fraction of time required for the state-of-the-art de novo assemblers. This favourable result paves the way for the development of powerful graph machine learning algorithms that can solve the de novo genome assembly problem much quicker and possibly more accurately than human handcrafted techniques.
Match Prediction Using Learned History Embeddings
Authors: Maxwell Goldstein, Leon Bottou, Rob Fergus
Date: 2021-09-29 00:00:00
Tasks: Prediction

Contemporary ranking systems that are based on win/loss history, such as Elo  or TrueSkill  represent each player using a scalar estimate of ability (plus variance, in the latter case). While easily interpretable, this approach has a number of shortcomings: (i) latent attributes of a player cannot be represented, and (ii) it cannot seamlessly incorporate contextual information (e.g. home-field advantage). In this work, we propose a simple Transformer-based approach for pairwise competitions that recursively operates on game histories, rather than modeling players directly. By characterizing each player entirely by its history, rather than an underlying scalar skill estimate, it is able to make accurate predictions even for new players with limited history. Additionally, it is able to model both transitive and non-transitive relations and can leverage contextual information. When restricted to the same information as Elo and Glicko, our approach significantly outperforms them on predicting the outcome of real-world Chess, Baseball and Ice Hockey games. %Further gains can be achieved when game meta-data is added.
Mistill: Distilling Distributed Network Protocols from Examples
Authors: Patrick Krämer, Johannes Zerwas, Andreas Blenk
Date: 2021-09-29 00:00:00

New applications and use-cases in data center networks require the design of Traffic Engineering (TE) algorithms that account for application-specific traffic patterns. TE makes forwarding decisions from the global state of the network. Thus, new TE algorithms require the design and implementation of effective information exchange and efficient algorithms to compute forwarding decisions. This is a challenging and labor and time-intensive process. To automate and simplify this process, we propose MISTILL. MISTILL distills the forwarding behavior of TE policies from exemplary forwarding decisions into a Neural Network. MISTILL learns which network devices must exchange state with each other, how to process local state to send it over the network, and how to map the exchanged state into forwarding decisions. We show the ability of MISTILL to learn distributed protocols with three examples and verify their performance in simulations. We show that the learned protocols closely implement the desired policies.
SGTR: Generating Scene Graph by Learning Compositional Triplets with Transformer
Authors: Rongjie Li, Songyang Zhang, Xuming He
Date: 2021-09-29 00:00:00
Tasks: Graph Generation, Scene Graph Generation, Triplet

In this work, we propose an end-to-end framework for the scene graph generation. Motivated by the recently introduced DETR, our method, termed SGTR, generating scene graphs by learning compositional queries with Transformers. We develop a decoding-and-assembling paradigm for the end-to-end scene graph generation. Based on a shared backbone, the overall structure first consists of two parallel branches: entity detector and triplet constructor, followed by a newly designed assembling mechanism. Specifically, each triplet is constructed by a set of the compositional queries in the triplet constructor. The predicate queries and entity queries are learned simultaneously with explicit information exchange. In the training phase, the grouping mechanism is learned by matching the decoded triplets with the outcome of the entity detector. Extensive experimental results show that SGTR can achieve state-of-the-art performance, surpassing most of the existing approaches. Moreover, the sparse queries significantly improving the efficiency of scene graph generation. We hope our SGTR can serve as a strong baseline for the Transformer-based scene graph generation.
ES-Based Jacobian Enables Faster Bilevel Optimization
Authors: Daouda Sow, Kaiyi Ji, Yingbin Liang
Date: 2021-09-29 00:00:00
Tasks: Bilevel Optimization, Meta-Learning

Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. However, due to the nested structure of BO, existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations, which can be very costly in practice, especially with large neural network models. In this work, we propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO, and hence fully eliminates all second-order computations. We call our algorithm as ESJ (which stands for the ES-based Jacobian method) and further extend it to the stochastic setting as ESJ-S. Theoretically, we characterize the convergence guarantee and computational complexity for our algorithms. Experimentally, we demonstrate the superiority of our proposed algorithms compared to the state of the art methods on various bilevel problems. Particularly, in our experiment in the  few-shot meta-learning problem, we meta-learn the twelve millions parameters of a ResNet-12 network over the miniImageNet dataset, which evidently demonstrates the scalability of our ES-based bilevel approach and its feasibility in the large-scale setting.
Bit-aware Randomized Response for Local Differential Privacy in Federated Learning
Authors: Phung Lai, Hai Phan, Li Xiong, Khang Phuc Tran, My Thai, Tong Sun, Franck Dernoncourt, Jiuxiang Gu, Nikolaos Barmpalios, Rajiv Jain
Date: 2021-09-29 00:00:00
Tasks: Federated Learning, image-classification, Image Classification

In this paper, we develop BitRand, a bit-aware randomized response algorithm, to preserve local differential privacy (LDP) in federated learning (FL). We encode embedded features extracted from clients' local data into binary encoding bits, in which different bits have different impacts on the embedded features. Based upon that, we randomize all the bits to preserve LDP with three key advantages: (1) Bit-aware: Bits with a more substantial influence on the model utility have smaller randomization probabilities, and vice-versa, under the same privacy protection; (2) Dimension-elastic: Increasing the dimensions of embedded features, gradients, model outcomes, and training rounds marginally affect the randomization probabilities of binary encoding bits under the same privacy protection; and (3) LDP protection is achieved for both embedded features and labels with tight privacy loss and expected error bounds ensuring high model utility. Extensive theoretical and experimental results show that our BitRand significantly outperforms various baseline approaches in text and image classification.
Reconstructing Word Embeddings via Scattered $k$-Sub-Embedding
Authors: Soonyong Hwang, Byung-Ro Moon
Date: 2021-09-29 00:00:00
Tasks: Diversity, Word Embeddings

The performance of modern neural language models relies heavily on the diversity of the vocabularies. Unfortunately, the language models tend to cover more vocabularies, the embedding parameters in the language models such as multilingual models used to occupy more than a half of their entire learning parameters. To solve this problem, we aim to devise a novel embedding structure to lighten the network without considerably performance degradation. To reconstruct $N$ embedding vectors, we initialize $k$ bundles of $M (\ll N)$ $k$-sub-embeddings to apply Cartesian product. Furthermore, we assign $k$-sub-embedding using the contextual relationship between tokens from pretrained language models. We adjust our $k$-sub-embedding structure to masked language models to evaluate proposed structure on downstream tasks. Our experimental results show that over 99.9$\%+$ compressed sub-embeddings for the language models performed comparably with the original embedding structure on GLUE and XNLI benchmarks.
Refining Multimodal Representations using a modality-centric self-supervised module
Authors: Sethuraman Sankaran, David Yang, Ser-Nam Lim
Date: 2021-09-29 00:00:00
Tasks: Few-Shot Learning

Tasks that rely on multi-modal information typically include a fusion module that combines information from different modalities. In this work, we develop a self-supervised module, called REFINER, that refines multimodal representations using a decoding/defusing module applied downstream of the fused embedding. REFINER imposes a modality-centric responsibility condition, ensuring that both unimodal and fused representations are strongly encoded in the latent fusion space. Our approach provides both stronger generalization and reduced over-fitting. REFINER is only applied during training time keeping the inference time intact. The modular nature of REFINER lends itself to be combined with different fusion architectures easily. We demonstrate the power of REFINER on three datasets over powerful baseline fusion modules, and further show that they give a significant performance boost in few shot learning tasks.
A composable autoencoder-based algorithm for accelerating numerical simulations
Authors: Rishikesh Ranade, Derek Christopher Hill, Haiyang He, Amir Maleki, Norman Chang, Jay Pathak
Date: 2021-09-29 00:00:00

Numerical simulations for engineering applications solve partial differential equations (PDE) to model various physical processes. Traditional PDE solvers are very accurate but computationally costly. On the other hand, Machine Learning (ML) methods offer a significant computational speedup but face challenges with accuracy and generalization to different PDE conditions, such as geometry, boundary conditions, initial conditions and PDE source terms. In this work, we propose a novel ML-based approach, CoAE-MLSim, which is an unsupervised, lower-dimensional, local method, that is motivated from key ideas used in commercial PDE solvers. This allows our approach to learn better with relatively fewer samples of PDE solutions. The proposed ML-approach is compared against commercial solvers for better benchmarks as well as latest ML-approaches for solving PDEs. It is tested for a variety of complex engineering cases to demonstrate its computational speed, accuracy, scalability, and generalization across different PDE conditions. The results show that our approach captures physics accurately across all metrics of comparison (including measures such as results on section cuts and lines).
On the Effect of Input Perturbations for Graph Neural Networks
Authors: Behrooz Tahmasebi, Stefanie Jegelka
Date: 2021-09-29 00:00:00
Tasks: Graph Neural Network

The expressive power of a message passing graph neural network (MPGNN) depends on its architecture and the input node attributes. In this work, we study how this interplay is affected by input perturbations. First, perturbations of node attributes may act as noise and hinder predictive power. But, perturbations can also aid expressiveness, by making nodes more identifiable. Recent works show that unique node IDs are necessary to represent certain functions with MPGNNs. Our results relate properties of the noise, smoothness of the model and the geometry of the input graphs and task. In particular, we take the perspective of lower bounding smoothness for achieving discrimination: how much output variation is needed for exploiting random node IDs, or for retaining discriminability? Our theoretical results imply constraints on the model for exploiting random node IDs, and, conversely, insights into the tolerance of a given model class for retaining discrimination with perturbations of node attributes.
Coherence-based Label Propagation over Time Series for Accelerated Active Learning
Authors: Yooju Shin, Susik Yoon, Sundong Kim, Hwanjun Song, Jae-Gil Lee, Byung Suk Lee
Date: 2021-09-29 00:00:00
Proceeding: ICLR 2022 4
Tasks: Active Learning, Time Series, Time Series Analysis

Time-series data are ubiquitous these days, but lack of the labels in time-series data is regarded as a hurdle for its broad applicability. Meanwhile, active learning has been successfully adopted to reduce the labeling efforts in various tasks. Thus, this paper addresses an important issue, time-series active learning. Inspired by the temporal coherence in time-series data, where consecutive data points tend to have the same label, our label propagation framework, called TCLP, automatically assigns a queried label to the data points within an accurately estimated time-series segment, thereby significantly boosting the impact of an individual query. Compared with traditional time-series active learning, TCLP is shown to improve the classification accuracy by up to 5.9 times when only 0.4% of data points in the entire time series are queried for their labels.
FLOAT: FAST LEARNABLE ONCE-FOR-ALL ADVERSARIAL TRAINING FOR TUNABLE TRADE-OFF BETWEEN ACCURACY AND ROBUSTNESS
Authors: Souvik Kundu, Peter Anthony Beerel, Sairam Sundaresan
Date: 2021-09-29 00:00:00
Tasks: All, image-classification, Image Classification

Training a model that can be robust against adversarially-perturbed images with-out compromising accuracy on clean-images has proven to be challenging. Recent research has tried to resolve this issue by incorporating an additional layer after each  batch-normalization  layer  in  a  network,  that  implements  feature-wise  linear modulation (FiLM). These extra layers enable in-situ calibration of a trained model, allowing the user to configure the desired priority between robustness and clean-image performance after deployment.  However, these extra layers significantly increase training time, parameter count, and add latency which can prove costly  for  time  or  memory  constrained  applications.   In  this  paper,  we  present Fast Learnable Once-for-all Adversarial Training (FLOAT) which transforms the weight tensors without using extra layers, thereby incurring no significant increase in parameter count, training time, or network latency compared to a standard adversarial training. In particular, we add configurable scaled noise to the weight tensors that enables a ‘continuous’ trade-off between clean and adversarial performance.  Additionally, we extend FLOAT to slimmable neural networks to enable a three-way in-situ trade-off between robustness, accuracy, and complexity.  Extensive experiments show that FLOAT can yield state-of-the-art performance improving both clean and perturbed image classification by up to ∼6.5% and ∼14.5%,  respectively,  while  requiring  up  to 1.47x fewer  parameters with similar hyperparameter settings compared to FiLM-based alternatives.
Scalable Hierarchical Embeddings of Complex Networks
Authors: Nikolaos Nakis, Abdulkadir Celikkanat, Sune Lehmann, Morten Mørup
Date: 2021-09-29 00:00:00
Tasks: Clustering, Graph Embedding, Graph Representation Learning, Link Prediction, Network Embedding, Node Clustering, Representation Learning

Graph representation learning has become important in order to understand and predict intrinsic structures in complex networks. A variety of embedding methods has in recent years been developed including the Latent Distance Modeling (LDM) approach. A major challenge is scaling network embedding approaches to very large networks and a drawback of LDM is the computational cost invoked evaluating the full likelihood having O(N^2) complexity, making such analysis of large networks infeasible. We propose a novel multiscale hierarchical estimate of the full likelihood of LDMs providing high details where the likelihood approximation is most important while scaling in complexity at O(NlogN). The approach relies on a clustering procedure approximating the Euclidean norm of every node pair according to the multiscale hierarchical structure imposed. We demonstrate the accuracy of our approximation and for the first time embed very large networks in the order of a million nodes using LDM and contrast the predictive performance to prominent scalable graph embedding approaches. We find that our approach significantly outperforms these existing scalable approaches in the ability to perform link prediction, node clustering, and classification utilizing a surprisingly low embedding dimensionality of two to three dimensions whereas the extracted hierarchical structure facilitates network visualization and interpretation. The developed scalable hierarchical embedding approach enables accurate low dimensional representations of very large networks providing detailed visualizations that can further our understanding of their properties and structure.
Measuring CLEVRness: Black-box Testing of Visual Reasoning Models
Authors: Spyridon Mouselinos, Henryk Michalewski, Mateusz Malinowski
Date: 2021-09-29 00:00:00
Proceeding: ICLR 2022 4
Tasks: Benchmarking, Diagnostic, Question Answering, Visual Question Answering, Visual Question Answering (VQA), Visual Reasoning

How to measure the reasoning capabilities of intelligence systems? Visual question answering provides a convenient framework for testing the model's abilities by interrogating the model through questions about the scene. However, despite the score of various visual QA datasets and architectures, which sometimes yield even a super-human performance, the question of whether those architectures can do reasoning remains open.
To answer such a question, we extend the visual question answering framework and propose the following behavioral test in the form of a two-player game. We consider black-box neural models of CLEVR. Those models are trained on a diagnostic dataset benchmarking reasoning. Next, we train an adversarial player that re-configures the scene to fool the CLEVR model. We show that CLEVR models, which otherwise may perform at a human level, can easily be fooled by our agent. Our results question one more time whether data-driven approaches can do reasoning without exploiting numerous biases that are often present in those datasets. Finally, we also propose a controlled experiment measuring the efficiency of such models to learn and perform reasoning.
Learning by Directional Gradient Descent
Authors: David Silver, Anirudh Goyal, Ivo Danihelka, Matteo Hessel, Hado van Hasselt
Date: 2021-09-29 00:00:00
Proceeding: ICLR 2022 4

How should state be constructed from a sequence of observations, so as to best achieve some objective? Most deep learning methods update the parameters of the state representation by gradient descent. However, no prior method for computing the gradient is fully satisfactory, for example consuming too much memory, introducing too much variance, or adding too much bias. In this work, we propose a new learning algorithm that addresses these limitations. The basic idea is to update the parameters of the representation by using the directional derivative along a candidate direction, a quantity that may be computed online with the same computational cost as the representation itself. We consider several different choices of candidate direction, including random selection and approximations to the true gradient, and investigate their performance on several synthetic tasks.
FedNAS: Federated Deep Learning via Neural Architecture Search
Authors: Chaoyang He, Erum Mushtaq, Jie Ding, Salman Avestimehr
Date: 2021-09-29 00:00:00
Tasks: Deep Learning, Federated Learning, Meta-Learning, Neural Architecture Search

Federated Learning (FL) is an effective learning framework used when data cannotbe centralized due to privacy, communication costs, and regulatory restrictions.While there have been many algorithmic advances in FL, significantly less effort hasbeen made on model development, and most works in FL employ predefined modelarchitectures discovered in the centralized environment. However, these predefinedarchitectures may not be the optimal choice for the FL setting since the user datadistribution at FL users is often non-identical and independent distribution (non-IID). This well-known challenge in FL has often been studied at the optimizationlayer.  Instead, we advocate for a different (and complementary) approach.  Wepropose Federated Neural Architecture Search (FedNAS) for automating the modeldesign process in FL. More specifically, FedNAS enables scattered workers tosearch for a better architecture in a collaborative fashion to achieve higher accuracy. Beyond automating and improving FL model design, FedNAS also provides anew paradigm for personalized FL via customizing not only the model weightsbut also the neural architecture of each user. As such, we also compare FedNASwith representative personalized FL methods, including perFedAvg (based on meta-learning), Ditto (bi-level optimization), and local fine-tuning. Our experiments ona non-IID dataset show that the architecture searched by FedNAS can outperformthe manually predefined architecture as well as existing personalized FL methods.To facilitate further research and real-world deployment, we also build a realisticdistributed training system for FedNAS, which will be publicly available andmaintained regularly.