Playing the Lottery With Concave Regularizers for Sparse Trainable Neural Networks.

The design of sparse neural networks, i.e., of networks with a reduced number of parameters, has been attracting increasing research attention in the last few years. The use of sparse models may significantly reduce the computational and storage footprint in the inference phase. In this context, the lottery ticket hypothesis (LTH) constitutes a breakthrough result, that addresses not only the performance of the inference phase, but also of the training phase. It states that it is possible to extract effective sparse subnetworks, called winning tickets, that can be trained in isolation. The development of effective methods to play the lottery, i.e., to find winning tickets, is still an open problem. In this article, we propose a novel class of methods to play the lottery. The key point is the use of concave regularization to promote the sparsity of a relaxed binary mask, which represents the network topology. We theoretically analyze the effectiveness of the proposed method in the convex framework. Then, we propose extended numerical tests on various datasets and architectures, that show that the proposed method can improve the performance of state-of-the-art algorithms.

RAN-GNNs: Breaking the Capacity Limits of Graph Neural Networks.

Graph neural networks (GNNs) have become a staple in problems addressing learning and analysis of data defined over graphs. However, several results suggest an inherent difficulty in extracting better performance by increasing the number of layers. Recent works attribute this to a phenomenon peculiar to the extraction of node features in graph-based tasks, i.e., the need to consider multiple neighborhood sizes at the same time and adaptively tune them. In this article, we investigate the recently proposed randomly wired architectures in the context of GNNs. Instead of building deeper networks by stacking many layers, we prove that employing a randomly wired architecture can be a more effective way to increase the capacity of the network and obtain richer representations. We show that such architectures behave like an ensemble of paths, which are able to merge contributions from receptive fields of varied size. Moreover, these receptive fields can also be modulated to be wider or narrower through the trainable weights over the paths. We also provide extensive experimental evidence of the superior performance of randomly wired architectures over multiple tasks and five graph convolution definitions, using recent benchmarking frameworks that address the reliability of previous testing methodologies.

Multiclass Sparse Centroids With Application to Fast Time Series Classification.

In this article, we propose an efficient multiclass classification scheme based on sparse centroids classifiers. The proposed strategy exhibits linear complexity with respect to both the number of classes and the cardinality of the feature space. The classifier we introduce is based on binary space partitioning, performed by a decision tree where the assignation law at each node is defined via a sparse centroid classifier. We apply the presented strategy to the time series classification problem, showing by experimental evidence that it achieves performance comparable to that of state-of-the-art methods, but with a significantly lower classification time. The proposed technique can be an effective option in resource-constrained environments where the classification time and the computational cost are critical or, in scenarios, where real-time classification is necessary.

Age structure in SIRD models for the COVID-19 pandemic-A case study on Italy data and effects on mortality.

The COVID-19 pandemic is bringing disruptive effects on the healthcare systems, economy and social life of countries all over the world. Even though the elder portion of the population is the most severely affected by the COVID-19 disease, the counter-measures introduced so far by governments took into little account the age structure, with restrictions that act uniformly on the population irrespectively of age. In this paper, we introduce a SIRD model with age classes for studying the impact on the epidemic evolution of lockdown policies applied heterogeneously on the different age groups of the population. The proposed model is then applied to age-stratified COVID-19 Italian data. The simulation results suggest that control measures focused to specific age groups may bring benefits in terms of reduction of the overall mortality rate.

Sparse ℓ1- and ℓ2-Center Classifiers.

In this article, we discuss two novel sparse versions of the classical nearest-centroid classifier. The proposed sparse classifiers are based on l1 and l2 distance criteria, respectively, and perform simultaneous feature selection and classification, by detecting the features that are most relevant for the classification purpose. We formally prove that the training of the proposed sparse models, with both distance criteria, can be performed exactly (i.e., the globally optimal set of features is selected) at a linear computational cost. Especially, the proposed sparse classifiers are trained in O(mn)+O(mlogk) operations, where n is the number of samples, m is the total number of features, and k ≤ m is the number of features to be retained in the classifier. Furthermore, the complexity of testing and classifying a new sample is simply O(k) for both methods. The proposed models can be employed either as stand-alone sparse classifiers or fast feature-selection techniques for prefiltering the features to be later fed to other types of classifiers (e.g., SVMs). The experimental results show that the proposed methods are competitive in accuracy with state-of-the-art feature selection and classification techniques while having a substantially lower computational cost.

Deep Graph-Convolutional Image Denoising.

Non-local self-similarity is well-known to be an effective prior for the image denoising problem. However, little work has been done to incorporate it in convolutional neural networks, which surpass non-local model-based methods despite only exploiting local information. In this paper, we propose a novel end-to-end trainable neural network architecture employing layers based on graph convolution operations, thereby creating neurons with non-local receptive fields. The graph convolution operation generalizes the classic convolution to arbitrary graphs. In this work, the graph is dynamically computed from similarities among the hidden features of the network, so that the powerful representation learning capabilities of the network are exploited to uncover self-similar patterns. We introduce a lightweight Edge-Conditioned Convolution which addresses vanishing gradient and over-parameterization issues of this particular graph convolution. Extensive experiments show state-of-the-art performance with improved qualitative and quantitative results on both synthetic Gaussian noise and real noise.

Graph Transform Optimization with Application to Image Compression.

In this paper, we propose a new graph-based transform and illustrate its potential application to signal compression. Our approach relies on the careful design of a graph that optimizes the overall rate-distortion performance through an effective graph-based transform. We introduce a novel graph estimation algorithm, which uncovers the connectivities between the graph signal values by taking into consideration the coding of both the signal and the graph topology in rate-distortion terms. In particular, we introduce a novel coding solution for the graph by treating the edge weights as another graph signal that lies on the dual graph. Then, the cost of the graph description is introduced in the optimization problem by minimizing the sparsity of the coefficients of its graph Fourier transform (GFT) on the dual graph. In this way, we obtain a convex optimization problem whose solution defines an efficient transform coding strategy. The proposed technique is a general framework that can be applied to different types of signals, and we show two possible application fields, namely natural image coding and piecewise smooth image coding. The experimental results show that the proposed graph-based transform outperforms classical fixed transforms such as DCT for both natural and piecewise smooth images. In the case of depth map coding, the obtained results are even comparable to the state-of-the-art graph-based coding method, that are specifically designed for depth map images.

Steerable Discrete Cosine Transform.

In image compression, classical block-based separable transforms tend to be inefficient when image blocks contain arbitrarily shaped discontinuities. For this reason, transforms incorporating directional information are an appealing alternative. In this paper, we propose a new approach to this problem, namely, a discrete cosine transform (DCT) that can be steered in any chosen direction. Such transform, called steerable DCT (SDCT), allows to rotate in a flexible way pairs of basis vectors, and enables precise matching of directionality in each image block, achieving improved coding efficiency. The optimal rotation angles for SDCT can be represented as solution of a suitable rate-distortion (RD) problem. We propose iterative methods to search such solution, and we develop a fully fledged image encoder to practically compare our techniques with other competing transforms. Analytical and numerical results prove that SDCT outperforms both DCT and state-of-the-art directional transforms.