pwc-archive/papers-with-abstracts huggingface dataset:
On the Stability of Graph Convolutional Neural Networks under Edge Rewiring
Authors: Henry Kenlay, Dorina Thanou, Xiaowen Dong
Date: 2020-10-26 00:00:00
Proceeding: ICLR Workshop GTRL 2021 5

Graph neural networks are experiencing a surge of popularity within the machine learning community due to their ability to adapt to non-Euclidean domains and instil inductive biases. Despite this, their stability, i.e., their robustness to small perturbations in the input, is not yet well understood. Although there exists some results showing the stability of graph neural networks, most take the form of an upper bound on the magnitude of change due to a perturbation in the graph topology. However, the change in the graph topology captured in existing bounds tend not to be expressed in terms of structural properties, limiting our understanding of the model robustness properties. In this work, we develop an interpretable upper bound elucidating that graph neural networks are stable to rewiring between high degree nodes. This bound and further research in bounds of similar type provide further understanding of the stability properties of graph neural networks.
Real-Time Edge Classification: Optimal Offloading under Token Bucket Constraints
Authors: Ayan Chakrabarti, Roch Guérin, Chenyang Lu, Jiangnan Liu
Date: 2020-10-26 00:00:00
Tasks: Classification, Edge Classification, Edge-computing, General Classification, image-classification, Image Classification

To deploy machine learning-based algorithms for real-time applications with strict latency constraints, we consider an edge-computing setting where a subset of inputs are offloaded to the edge for processing by an accurate but resource-intensive model, and the rest are processed only by a less-accurate model on the device itself. Both models have computational costs that match available compute resources, and process inputs with low-latency. But offloading incurs network delays, and to manage these delays to meet application deadlines, we use a token bucket to constrain the average rate and burst length of transmissions from the device. We introduce a Markov Decision Process-based framework to make offload decisions under these constraints, based on the local model's confidence and the token bucket state, with the goal of minimizing a specified error measure for the application. Beyond isolated decisions for individual devices, we also propose approaches to allow multiple devices connected to the same access switch to share their bursting allocation. We evaluate and analyze the policies derived using our framework on the standard ImageNet image classification benchmark.
Personalised Meta-path Generation for Heterogeneous GNNs
Authors: Zhiqiang Zhong, Cheng-Te Li, Jun Pang
Date: 2020-10-26 00:00:00
Tasks: Deep Reinforcement Learning, Graph Representation Learning, Node Classification, Reinforcement Learning (RL), Representation Learning

Recently, increasing attention has been paid to heterogeneous graph representation learning (HGRL), which aims to embed rich structural and semantic information in heterogeneous information networks (HINs) into low-dimensional node representations. To date, most HGRL models rely on hand-crafted meta-paths. However, the dependency on manually-defined meta-paths requires domain knowledge, which is difficult to obtain for complex HINs. More importantly, the pre-defined or generated meta-paths of all existing HGRL methods attached to each node type or node pair cannot be personalised to each individual node. To fully unleash the power of HGRL, we present a novel framework, Personalised Meta-path based Heterogeneous Graph Neural Networks (PM-HGNN), to jointly generate meta-paths that are personalised for each individual node in a HIN and learn node representations for the target downstream task like node classification. Precisely, PM-HGNN treats the meta-path generation as a Markov Decision Process and utilises a policy network to adaptively generate a meta-path for each individual node and simultaneously learn effective node representations. The policy network is trained with deep reinforcement learning by exploiting the performance improvement on a downstream task. We further propose an extension, PM-HGNN++, to better encode relational structure and accelerate the training during the meta-path generation. Experimental results reveal that both PM-HGNN and PM-HGNN++ can significantly and consistently outperform 16 competing baselines and state-of-the-art methods in various settings of node classification. Qualitative analysis also shows that PM-HGNN++ can identify meaningful meta-paths overlooked by human knowledge.
Random Geometric Graphs on Euclidean Balls
Authors: Ernesto Araya Valdivia
Date: 2020-10-26 00:00:00

We consider a latent space model for random graphs where a node $i$ is associated to a random latent point $X_i$ on the Euclidean unit ball. The probability that an edge exists between two nodes is determined by a ``link'' function, which corresponds to a dot product kernel. For a given class $\F$ of spherically symmetric distributions for $X_i$, we consider two estimation problems: latent norm recovery and latent Gram matrix estimation. We construct an estimator for the latent norms based on the degree of the nodes of an observed graph in the case of the model where the edge probability is given by $f(\langle X_i,X_j\rangle)=\mathbbm{1}_{\langle X_i,X_j\rangle\geq \tau}$, where $0<\tau<1$. We introduce an estimator for the Gram matrix based on the eigenvectors of observed graph and we establish Frobenius type guarantee for the error, provided that the link function is sufficiently regular in the Sobolev sense and that a spectral-gap-type condition holds. We prove that for certain link functions, the model considered here generates graphs with degree distribution that have tails with a power-law-type distribution, which can be seen as an advantage of the model presented here with respect to the classic Random Geometric Graph model on the Euclidean sphere. We illustrate our results with numerical experiments.
Dyslexia detection from EEG signals using SSA component correlation and Convolutional Neural Networks
Authors: Andrés Ortiz, Francisco J. Martinez-Murcia, Marco A. Formoso, Juan Luis Luque, Auxiliadora Sánchez
Date: 2020-10-26 00:00:00
Tasks: EEG, Electroencephalogram (EEG)

Objective dyslexia diagnosis is not a straighforward task since it is traditionally performed by means of the intepretation of different behavioural tests. Moreover, these tests are only applicable to readers. This way, early diagnosis requires the use of specific tasks not only related to reading. Thus, the use of Electroencephalography (EEG) constitutes an alternative for an objective and early diagnosis that can be used with pre-readers. In this way, the extraction of relevant features in EEG signals results crucial for classification. However, the identification of the most relevant features is not straighforward, and predefined statistics in the time or frequency domain are not always discriminant enough. On the other hand, classical processing of EEG signals based on extracting EEG bands frequency descriptors, usually make some assumptions on the raw signals that could cause indormation loosing. In this work we propose an alternative for analysis in the frequency domain based on Singluar Spectrum Analysis (SSA) to split the raw signal into components representing different oscillatory modes. Moreover, correlation matrices obtained for each component among EEG channels are classfied using a Convolutional Neural network.
Tight last-iterate convergence rates for no-regret learning in multi-player games
Authors: Noah Golowich, Sarath Pattathil, Constantinos Daskalakis
Date: 2020-10-26 00:00:00
Proceeding: NeurIPS 2020 12

We study the question of obtaining last-iterate convergence rates for no-regret learning algorithms in multi-player games. We show that the optimistic gradient (OG) algorithm with a constant step-size, which is no-regret, achieves a last-iterate rate of $O(1/\sqrt{T})$ with respect to the gap function in smooth monotone games. This result addresses a question of Mertikopoulos & Zhou (2018), who asked whether extra-gradient approaches (such as OG) can be applied to achieve improved guarantees in the multi-agent learning setting. The proof of our upper bound uses a new technique centered around an adaptive choice of potential function at each iteration. We also show that the $O(1/\sqrt{T})$ rate is tight for all $p$-SCLI algorithms, which includes OG as a special case. As a byproduct of our lower bound analysis we additionally present a proof of a conjecture of Arjevani et al. (2015) which is more direct than previous approaches.
Optimal Client Sampling for Federated Learning
Authors: Wenlin Chen, Samuel Horvath, Peter Richtarik
Date: 2020-10-26 00:00:00
Proceeding: NeurIPS 2021 12
Tasks: Federated Learning

It is well understood that client-master communication can be a primary bottleneck in Federated Learning. In this work, we address this issue with a novel client subsampling scheme, where we restrict the number of clients allowed to communicate their updates back to the master node. In each communication round, all participating clients compute their updates, but only the ones with "important" updates communicate back to the master. We show that importance can be measured using only the norm of the update and give a formula for optimal client participation. This formula minimizes the distance between the full update, where all clients participate, and our limited update, where the number of participating clients is restricted. In addition, we provide a simple algorithm that approximates the optimal formula for client participation, which only requires secure aggregation and thus does not compromise client privacy. We show both theoretically and empirically that for Distributed SGD (DSGD) and Federated Averaging (FedAvg), the performance of our approach can be close to full participation and superior to the baseline where participating clients are sampled uniformly. Moreover, our approach is orthogonal to and compatible with existing methods for reducing communication overhead, such as local methods and communication compression methods.
ST-GREED: Space-Time Generalized Entropic Differences for Frame Rate Dependent Video Quality Prediction
Authors: Pavan C. Madhusudana, Neil Birkbeck, Yilin Wang, Balu Adsumilli, Alan C. Bovik
Date: 2020-10-26 00:00:00
Tasks: Video Quality Assessment, Visual Question Answering (VQA)

We consider the problem of conducting frame rate dependent video quality assessment (VQA) on videos of diverse frame rates, including high frame rate (HFR) videos. More generally, we study how perceptual quality is affected by frame rate, and how frame rate and compression combine to affect perceived quality. We devise an objective VQA model called Space-Time GeneRalized Entropic Difference (GREED) which analyzes the statistics of spatial and temporal band-pass video coefficients. A generalized Gaussian distribution (GGD) is used to model band-pass responses, while entropy variations between reference and distorted videos under the GGD model are used to capture video quality variations arising from frame rate changes. The entropic differences are calculated across multiple temporal and spatial subbands, and merged using a learned regressor. We show through extensive experiments that GREED achieves state-of-the-art performance on the LIVE-YT-HFR Database when compared with existing VQA models. The features used in GREED are highly generalizable and obtain competitive performance even on standard, non-HFR VQA databases. The implementation of GREED has been made available online: https://github.com/pavancm/GREED
Track-Assignment Detailed Routing Using Attention-based Policy Model With Supervision
Authors: Haiguang Liao, Qingyi Dong, Weiyi Qi, Elias Fallon, Levent Burak Kara
Date: 2020-10-26 00:00:00
Tasks: Reinforcement Learning (RL)

Detailed routing is one of the most critical steps in analog circuit design. Complete routing has become increasingly more challenging in advanced node analog circuits, making advances in efficient automatic routers ever more necessary. In this work, we propose a machine learning driven method for solving the track-assignment detailed routing problem for advanced node analog circuits. Our approach adopts an attention-based reinforcement learning (RL) policy model. Our main insight and advancement over this RL model is the use of supervision as a way to leverage solutions generated by a conventional genetic algorithm (GA). For this, our approach minimizes the Kullback-Leibler divergence loss between the output from the RL policy model and a solution distribution obtained from the genetic solver. The key advantage of this approach is that the router can learn a policy in an offline setting with supervision, while improving the run-time performance nearly 100x over the genetic solver. Moreover, the quality of the solutions our approach produces matches well with those generated by GA. We show that especially for complex problems, our supervised RL method provides good quality solution similar to conventional attention-based RL without comprising run time performance. The ability to learn from example designs and train the router to get similar solutions with orders of magnitude run-time improvement can impact the design flow dramatically, potentially enabling increased design exploration and routability-driven placement.
Distributed Multi-Target Tracking in Camera Networks
Authors: Sara Casao, Abel Naya, Ana C. Murillo, Eduardo Montijano
Date: 2020-10-26 00:00:00
Tasks: Decision Making, Management

Most recent works on multi-target tracking with multiple cameras focus on centralized systems. In contrast, this paper presents a multi-target tracking approach implemented in a distributed camera network. The advantages of distributed systems lie in lighter communication management, greater robustness to failures and local decision making. On the other hand, data association and information fusion are more challenging than in a centralized setup, mostly due to the lack of global and complete information. The proposed algorithm boosts the benefits of the Distributed-Consensus Kalman Filter with the support of a re-identification network and a distributed tracker manager module to facilitate consistent information. These techniques complement each other and facilitate the cross-camera data association in a simple and effective manner. We evaluate the whole system with known public data sets under different conditions demonstrating the advantages of combining all the modules. In addition, we compare our algorithm to some existing centralized tracking methods, outperforming their behavior in terms of accuracy and bandwidth usage.
A Survey of Embedding Space Alignment Methods for Language and Knowledge Graphs
Authors: Alexander Kalinowski, Yuan An
Date: 2020-10-26 00:00:00
Tasks: Graph Embedding, Knowledge Graph Embedding, Knowledge Graphs, Sentence, Survey

Neural embedding approaches have become a staple in the fields of computer vision, natural language processing, and more recently, graph analytics. Given the pervasive nature of these algorithms, the natural question becomes how to exploit the embedding spaces to map, or align, embeddings of different data sources. To this end, we survey the current research landscape on word, sentence and knowledge graph embedding algorithms. We provide a classification of the relevant alignment techniques and discuss benchmark datasets used in this field of research. By gathering these diverse approaches into a singular survey, we hope to further motivate research into alignment of embedding spaces of varied data types and sources.
Infrared spectra of neutral polycyclic aromatic hydrocarbons by machine learning
Authors: Gaétan Laurens, Malalatiana Rabary, Julien Lam, Daniel Peláez, Abdul-Rahman Allouche
Date: 2020-10-26 00:00:00
Tasks: BIG-bench Machine Learning

The Interest in polycyclic aromatic hydrocarbons (PAHs) spans numerous fields and infrared spectroscopy is usually the method of choice to disentangle their molecular structure. In order to compute vibrational frequencies, numerous theoretical studies employ either quantum calculation methods, or empirical potentials, but it remains difficult to combine the accuracy of the first approach with the computational cost of the second. In this work, we employed Machine Learning techniques to develop a potential energy surface and a dipole mapping based on an artificial neural network (ANN) architecture. Altogether, while trained on only 11 small PAH molecules, the obtained ANNs are able to retrieve the infrared spectra of those small molecules, but more importantly of 8 large PAHs different from the training set, thus demonstrating the transferability of our approach.
How angry are your customers? Sentiment analysis of support tickets that escalate
Authors: Colin Werner, Lloyd Montgomery, Sanja Dodos, Gabriel Tapuc, Diksha Sharma, Daniela Damian
Date: 2020-10-26 00:00:00
Tasks: Sentiment Analysis

Software support ticket escalations can be an extremely costly burden for software organizations all over the world. Consequently, there exists an interest in researching how to better enable support analysts to handle such escalations. In order to do so, we need to develop tools to reliably predict if, and when, a support ticket becomes a candidate for escalation. This paper explores the use of sentiment analysis tools on customer-support analyst conversations to find indicators of when a particular support ticket may be escalated. The results of this research indicate a considerable difference in the sentiment between escalated support tickets and non-escalated support tickets. Thus, this preliminary research provides us with the necessary information to further investigate how we can reliably predict support ticket escalations, and subsequently to provide insight to support analysts to better enable them to handle support tickets that may be escalated.
Forethought and Hindsight in Credit Assignment
Authors: Veronica Chelu, Doina Precup, Hado van Hasselt
Date: 2020-10-26 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Reinforcement Learning (RL)

We address the problem of credit assignment in reinforcement learning and explore fundamental questions regarding the way in which an agent can best use additional computation to propagate new information, by planning with internal models of the world to improve its predictions. Particularly, we work to understand the gains and peculiarities of planning employed as forethought via forward models or as hindsight operating with backward models. We establish the relative merits, limitations and complementary properties of both planning mechanisms in carefully constructed scenarios. Further, we investigate the best use of models in planning, primarily focusing on the selection of states in which predictions should be (re)-evaluated. Lastly, we discuss the issue of model estimation and highlight a spectrum of methods that stretch from explicit environment-dynamics predictors to more abstract planner-aware models.
Data Segmentation via t-SNE, DBSCAN, and Random Forest
Authors: Timothy DeLise
Date: 2020-10-26 00:00:00

This research proposes a data segmentation algorithm which combines t-SNE, DBSCAN, and Random Forest classifier to form an end-to-end pipeline that separates data into natural clusters and produces a characteristic profile of each cluster based on the most important features. Out-of-sample cluster labels can be inferred, and the technique generalizes well on real data sets. We describe the algorithm and provide case studies using the Iris and MNIST data sets, as well as real social media site data from Instagram. This is a proof of concept and sets the stage for further in-depth theoretical analysis.
Deep Low-rank plus Sparse Network for Dynamic MR Imaging
Authors: Wenqi Huang, Ziwen Ke, Zhuo-Xu Cui, Jing Cheng, Zhilang Qiu, Sen Jia, Leslie Ying, Yanjie Zhu, Dong Liang
Date: 2020-10-26 00:00:00
Tasks: compressed sensing, MRI Reconstruction

In dynamic magnetic resonance (MR) imaging, low-rank plus sparse (L+S) decomposition, or robust principal component analysis (PCA), has achieved stunning performance. However, the selection of the parameters of L+S is empirical, and the acceleration rate is limited, which are common failings of iterative compressed sensing MR imaging (CS-MRI) reconstruction methods. Many deep learning approaches have been proposed to address these issues, but few of them use a low-rank prior. In this paper, a model-based low-rank plus sparse network, dubbed L+S-Net, is proposed for dynamic MR reconstruction. In particular, we use an alternating linearized minimization method to solve the optimization problem with low-rank and sparse regularization. Learned soft singular value thresholding is introduced to ensure the clear separation of the L component and S component. Then, the iterative steps are unrolled into a network in which the regularization parameters are learnable. We prove that the proposed L+S-Net achieves global convergence under two standard assumptions. Experiments on retrospective and prospective cardiac cine datasets show that the proposed model outperforms state-of-the-art CS and existing deep learning methods and has great potential for extremely high acceleration factors (up to 24x).
Face Frontalization Based on Robustly Fitting a Deformable Shape Model to 3D Landmarks
Authors: Zhiqi Kang, Mostafa Sadeghi, Radu Horaud
Date: 2020-10-26 00:00:00
Tasks: Face Alignment, Face Model, Face Recognition, Robust Face Alignment

Face frontalization consists of synthesizing a frontally-viewed face from an arbitrarily-viewed one. The main contribution of this paper is a robust face alignment method that enables pixel-to-pixel warping. The method simultaneously estimates the rigid transformation (scale, rotation, and translation) and the non-rigid deformation between two 3D point sets: a set of 3D landmarks extracted from an arbitrary-viewed face, and a set of 3D landmarks parameterized by a frontally-viewed deformable face model. An important merit of the proposed method is its ability to deal both with noise (small perturbations) and with outliers (large errors). We propose to model inliers and outliers with the generalized Student's t-probability distribution function, a heavy-tailed distribution that is immune to non-Gaussian errors in the data. We describe in detail the associated expectation-maximization (EM) algorithm that alternates between the estimation of (i) the rigid parameters, (ii) the deformation parameters, and (iii) the Student-t distribution parameters. We also propose to use the zero-mean normalized cross-correlation, between a frontalized face and the corresponding ground-truth frontally-viewed face, to evaluate the performance of frontalization. To this end, we use a dataset that contains pairs of profile-viewed and frontally-viewed faces. This evaluation, based on direct image-to-image comparison, stands in contrast with indirect evaluation, based on analyzing the effect of frontalization on face recognition.