OpenRaiser/Intern-Atlas huggingface dataset:
Graph Neural Networks With Lifting-based Adaptive Graph Wavelets
Venue: arXiv cs.LG 2022
Year: 2022

Spectral-based graph neural networks (SGNNs) have been attracting increasing attention in graph representation learning. However, existing SGNNs are limited in implementing graph filters with rigid transforms (e.g., graph Fourier or predefined graph wavelet transforms) and cannot adapt to signals residing on graphs and tasks at hand. In this paper, we propose a novel class of graph neural networks that realizes graph filters with adaptive graph wavelets. Specifically, the adaptive graph wavelets are learned with neural network-parameterized lifting structures, where structure-aware attention-based lifting operations (i.e., prediction and update operations) are developed to jointly consider graph structures and node features. We propose to lift based on diffusion wavelets to alleviate the structural information loss induced by partitioning non-bipartite graphs. By design, the locality and sparsity of the resulting wavelet transform as well as the scalability of the lifting structure are guaranteed. We further derive a soft-thresholding filtering operation by learning sparse graph representations in terms of the learned wavelets, yielding a localized, efficient, and scalable wavelet-based graph filters. To ensure that the learned graph representations are invariant to node permutations, a layer is employed at the input of the networks to reorder the nodes according to their local topology information. We evaluate the proposed networks in both node-level and graph-level representation learning tasks on benchmark citation and bioinformatics graph datasets. Extensive experiments demonstrate the superiority of the proposed networks over existing SGNNs in terms of accuracy, efficiency, and scalability.
Uniform Sampling over Episode Difficulty
Venue: arXiv cs.LG 2022
Year: 2022

Episodic training is a core ingredient of few-shot learning to train models on tasks with limited labelled data. Despite its success, episodic training remains largely understudied, prompting us to ask the question: what is the best way to sample episodes? In this paper, we first propose a method to approximate episode sampling distributions based on their difficulty. Building on this method, we perform an extensive analysis and find that sampling uniformly over episode difficulty outperforms other sampling schemes, including curriculum and easy-/hard-mining. As the proposed sampling method is algorithm agnostic, we can leverage these insights to improve few-shot learning accuracies across many episodic training algorithms. We demonstrate the efficacy of our method across popular few-shot learning datasets, algorithms, network architectures, and protocols.
Spartus: A 9.4 TOp/s FPGA-based LSTM Accelerator Exploiting Spatio-Temporal Sparsity
Venue: arXiv cs.AR 2022
Year: 2022

Long Short-Term Memory (LSTM) recurrent networks are frequently used for tasks involving time-sequential data such as speech recognition. Unlike previous LSTM accelerators that either exploit spatial weight sparsity or temporal activation sparsity, this paper proposes a new accelerator called "Spartus" that exploits spatio-temporal sparsity to achieve ultra-low latency inference. Spatial sparsity is induced using a new Column-Balanced Targeted Dropout (CBTD) structured pruning method, producing structured sparse weight matrices for a balanced workload. The pruned networks running on Spartus hardware achieve weight sparsity levels of up to 96% and 94% with negligible accuracy loss on the TIMIT and the Librispeech datasets. To induce temporal sparsity in LSTM, we extend the previous DeltaGRU method to the DeltaLSTM method. Combining spatio-temporal sparsity with CBTD and DeltaLSTM saves on weight memory access and associated arithmetic operations. The Spartus architecture is scalable and supports real-time online speech recognition when implemented on small and large FPGAs. Spartus per-sample latency for a single DeltaLSTM layer of 1024 neurons averages 1 us. Exploiting spatio-temporal sparsity on our test LSTM network using the TIMIT dataset leads to 46X speedup of Spartus over its theoretical hardware performance to achieve 9.4 TOp/s effective batch-1 throughput and 1.1 TOp/s/W power efficiency.
Multi-task Federated Edge Learning (MtFEEL) in Wireless Networks
Venue: arXiv cs.IT 2022
Year: 2022

Federated Learning (FL) has evolved as a promising technique to handle distributed machine learning across edge devices. A single neural network (NN) that optimises a global objective is generally learned in most work in FL, which could be suboptimal for edge devices. Although works finding a NN personalised for edge device specific tasks exist, they lack generalisation and/or convergence guarantees. In this paper, a novel communication efficient FL algorithm for personalised learning in a wireless setting with guarantees is presented. The algorithm relies on finding a ``better`` empirical estimate of losses at each device, using a weighted average of the losses across different devices. It is devised from a Probably Approximately Correct (PAC) bound on the true loss in terms of the proposed empirical loss and is bounded by (i) the Rademacher complexity, (ii) the discrepancy, (iii) and a penalty term. Using a signed gradient feedback to find a personalised NN at each device, it is also proven to converge in a Rayleigh flat fading (in the uplink) channel, at a rate of the order max{1/SNR,1/sqrt(T)} Experimental results show that the proposed algorithm outperforms locally trained devices as well as the conventionally used FedAvg and FedSGD algorithms under practical SNR regimes.
Visual Domain Adaptation for Monocular Depth Estimation on Resource-Constrained Hardware
Venue: arXiv cs.CV 2022
Year: 2022

Real-world perception systems in many cases build on hardware with limited resources to adhere to cost and power limitations of their carrying system. Deploying deep neural networks on resource-constrained hardware became possible with model compression techniques, as well as efficient and hardware-aware architecture design. However, model adaptation is additionally required due to the diverse operation environments. In this work, we address the problem of training deep neural networks on resource-constrained hardware in the context of visual domain adaptation. We select the task of monocular depth estimation where our goal is to transform a pre-trained model to the target's domain data. While the source domain includes labels, we assume an unlabelled target domain, as it happens in real-world applications. Then, we present an adversarial learning approach that is adapted for training on the device with limited resources. Since visual domain adaptation, i.e. neural network training, has not been previously explored for resource-constrained hardware, we present the first feasibility study for image-based depth estimation. Our experiments show that visual domain adaptation is relevant only for efficient network architectures and training sets at the order of a few hundred samples. Models and code are publicly available.
Resource-Aware Adaptation of Heterogeneous Strategies for Coalition Formation
Venue: arXiv cs.MA 2022
Year: 2022

Existing approaches to coalition formation often assume that requirements associated with tasks are precisely specified by the human operator. However, prior work has demonstrated that humans, while extremely adept at solving complex problems, struggle to explicitly state their solution strategy. Further, existing approaches often ignore the fact that experts may utilize different, but equally-valid, solutions (i.e., heterogeneous strategies) to the same problem. In this work, we propose a two-part framework to address these challenges. First, we tackle the challenge of inferring implicit strategies directly from expert demonstrations of coalition formation. To this end, we model and infer such heterogeneous strategies as capability-based requirements associated with each task. Next, we propose a method capable of adaptively selecting one of the inferred strategies that best suits the target team without requiring additional training. Specifically, we formulate and solve a constrained optimization problem that simultaneously selects the most appropriate strategy given the target team's capabilities, and allocates its constituents into appropriate coalitions. We evaluate our approach against several baselines, including some that resemble existing approaches, using detailed numerical simulations, StarCraft II battles, and a multi-robot emergency-response scenario. Our results indicate that our framework consistently outperforms all baselines in terms of requirement satisfaction, resource utilization, and task success rates.
Scheduling with Communication Delay in Near-Linear Time
Venue: arXiv cs.DS 2022
Year: 2022

We consider the problem of efficiently scheduling jobs with precedence constraints on a set of identical machines in the presence of a uniform communication delay. Such precedence-constrained jobs can be modeled as a directed acyclic graph, $G = (V, E)$. In this setting, if two precedence-constrained jobs $u$ and $v$, with $v$ dependent on $u$ ($u \prec v$), are scheduled on different machines, then $v$ must start at least $ρ$ time units after $u$ completes. The scheduling objective is to minimize makespan, i.e. the total time from when the first job starts to when the last job finishes. The focus of this paper is to provide an efficient approximation algorithm with near-linear running time. We build on the algorithm of Lepere and Rapine [STACS 2002] for this problem to give an $O\left(\frac{\ln ρ}{\ln \ln ρ} \right)$-approximation algorithm that runs in $\tilde{O}(|V| + |E|)$ time.
Bird's-Eye-View Panoptic Segmentation Using Monocular Frontal View Images
Venue: arXiv cs.CV 2022
Year: 2022

Bird's-Eye-View (BEV) maps have emerged as one of the most powerful representations for scene understanding due to their ability to provide rich spatial context while being easy to interpret and process. Such maps have found use in many real-world tasks that extensively rely on accurate scene segmentation as well as object instance identification in the BEV space for their operation. However, existing segmentation algorithms only predict the semantics in the BEV space, which limits their use in applications where the notion of object instances is also critical. In this work, we present the first BEV panoptic segmentation approach for directly predicting dense panoptic segmentation maps in the BEV, given a single monocular image in the frontal view (FV). Our architecture follows the top-down paradigm and incorporates a novel dense transformer module consisting of two distinct transformers that learn to independently map vertical and flat regions in the input image from the FV to the BEV. Additionally, we derive a mathematical formulation for the sensitivity of the FV-BEV transformation which allows us to intelligently weight pixels in the BEV space to account for the varying descriptiveness across the FV image. Extensive evaluations on the KITTI-360 and nuScenes datasets demonstrate that our approach exceeds the state-of-the-art in the PQ metric by 3.61 pp and 4.93 pp respectively.
Second-Order Defeaturing Estimator of Manufacturing-Induced Porosity on Structural Elasticity
Venue: arXiv cs.CE 2022
Year: 2022

Manufactured metallic components often contain non-uniformly distributed pores of complex morphologies. Since such porosity defects have significant influence on material behaviors and affect the usage in high-performance applications, it is significant to understand the impact of porosity characteristics on the behaviors of components. In this work, a gradient-enhanced porosity defeaturing estimator, which allows for the modeling of pore geometry and spatial distribution, is proposed within a general elastostatic framework. In this approach, the first order shape sensitivity is implemented to account for the change in elastic quantity of interests with respect to variations of pore sizes and shapes, which is then supplemented by a second order shape sensitivity whose mixed partial derivative quantifies the interactions between pores in proximity. The efficacy of the proposed method comes from its posterior manner that it only relies on field solutions of reference models where pores are suppressed. In this context, meshing difficulty and solution convergence issue are avoided, which would otherwise arise in a direct finite element analysis on porous structures. The impact of porosity on structural elastic performance is approximated using a second order Taylor expansion where the topological difference between the porous and reference domains is estimated by topological sensitivity; the field variables on pore boundaries are approximated as explicit functions of design variables using exterior formulations. Numerical results show that the elastic performances of components are influenced by the existence of pores. The pore-to-pore interactions are significant when pores are close by.
Reduced-Order Multiscale Modeling of Plastic Deformations in 3D Alloys with Spatially Varying Porosity by Deflated Clustering Analysis
Venue: arXiv cs.CE 2022
Year: 2022

Aluminum alloys are increasingly utilized as lightweight materials in the automobile industry due to their superior capability in withstanding high mechanical loads. A significant challenge impeding the large-scale use of these alloys in high-performance applications is the presence of manufacturing-induced, spatially varying porosity defects. In order to understand the impacts of these defects on the macro-mechanical properties of cast alloys, multiscale simulations are often required. In this paper, we introduce a computationally efficient reduced-order multiscale framework to simulate the behavior of metallic components containing process-induced porosity under irreversible nonlinear deformations. In our approach, we start with a data compression scheme that significantly reduces the number of unknown macroscale and microscale variables by agglomerating close-by finite element nodes into a limited number of clusters. Then, we use deflation methods to project these variables into a lower-dimensional space where the material elastoplastic behaviors are approximated. Finally, we solve for the unknown variables and map them back to the original, high-dimensional space. We call our method deflated clustering analysis and by comparing it to direct numerical simulations we demonstrate that it accurately captures macroscale deformations and microscopic effective responses. To illustrate the effect of microscale pores on the macroscopic response of a cast component, we conduct multi-scale simulations with spatially varying local heterogeneities that are modeled with a microstructure characterization and reconstruction algorithm.
Mis-spoke or mis-lead: Achieving Robustness in Multi-Agent Communicative Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Recent studies in multi-agent communicative reinforcement learning (MACRL) have demonstrated that multi-agent coordination can be greatly improved by allowing communication between agents. Meanwhile, adversarial machine learning (ML) has shown that ML models are vulnerable to attacks. Despite the increasing concern about the robustness of ML algorithms, how to achieve robust communication in multi-agent reinforcement learning has been largely neglected. In this paper, we systematically explore the problem of adversarial communication in MACRL. Our main contributions are threefold. First, we propose an effective method to perform attacks in MACRL, by learning a model to generate optimal malicious messages. Second, we develop a defence method based on message reconstruction, to maintain multi-agent coordination under message attacks. Third, we formulate the adversarial communication problem as a two-player zero-sum game and propose a game-theoretical method R-MACRL to improve the worst-case defending performance. Empirical results demonstrate that many state-of-the-art MACRL methods are vulnerable to message attacks, and our method can significantly improve their robustness.
NeuralMVS: Bridging Multi-View Stereo and Novel View Synthesis
Venue: arXiv cs.CV 2022
Year: 2022

Multi-View Stereo (MVS) is a core task in 3D computer vision. With the surge of novel deep learning methods, learned MVS has surpassed the accuracy of classical approaches, but still relies on building a memory intensive dense cost volume. Novel View Synthesis (NVS) is a parallel line of research and has recently seen an increase in popularity with Neural Radiance Field (NeRF) models, which optimize a per scene radiance field. However, NeRF methods do not generalize to novel scenes and are slow to train and test. We propose to bridge the gap between these two methodologies with a novel network that can recover 3D scene geometry as a distance function, together with high-resolution color images. Our method uses only a sparse set of images as input and can generalize well to novel scenes. Additionally, we propose a coarse-to-fine sphere tracing approach in order to significantly increase speed. We show on various datasets that our method reaches comparable accuracy to per-scene optimized methods while being able to generalize and running significantly faster. We provide the source code at https://github.com/AIS-Bonn/neural_mvs
On the optimal layout of a dining room in the era of COVID-19 using mathematical optimization
Venue: arXiv cs.OH 2022
Year: 2022

We consider the problem of maximizing the number of people that a dining room can accommodate provided that the chairs belonging to different tables are socially distant. We introduce an optimization model that incorporates several characteristics of the problem, namely: the type and size of surface of the dining room, the shapes and sizes of the tables, the positions of the chairs, the sitting sense of the customers, and the possibility of adding space separators to increase the capacity. We propose a simple, yet general, set-packing formulation for the problem. We investigate the efficiency of space separators and the impact of considering the sitting sense of customers in the room capacity. We also perform an algorithmic analysis of the model, and assess its scalability to the problem size, the presence of (or lack thereof) room separators, and the consideration of the sitting sense of customers. We also propose two constructive heuristics capable of coping with large problem instances otherwise intractable for the optimization model.
Near optimal efficient decoding from pooled data
Venue: arXiv cs.IT 2022
Year: 2022

Consider $n$ items, each of which is characterised by one of $d+1$ possible features in $\{0, \ldots, d\}$. We study the inference task of learning these types by queries on subsets, or pools, of the items that only reveal a form of coarsened information on the features - in our case, the sum of all the features in the pool. This is a realistic scenario in situations where one has memory or technical constraints in the data collection process, or where the data is subject to anonymisation. Related prominent problems are the quantitative group testing problem, of which it is a generalisation, as well as the compressed sensing problem, of which it is a special case. In the present article, we are interested in the minimum number of queries needed to efficiently infer the labels, if one of the features, say $0$, is dominant in the sense that the number $k$ of non-zero features among the items is much smaller than $n$. It is known that in this case, all features can be recovered in exponential time by using no more than $O(k)$ queries. However, so far, all \textit{efficient} inference algorithms required at least $Ω(k\ln n)$ queries, and it was unknown whether this gap is artificial or of a fundamental nature. Here we show that indeed, the previous gap between the information-theoretic and computational bounds is not inherent to the problem by providing an efficient algorithm that succeeds with high probability and employs no more than $O(k)$ measurements. This also solves a long standing open question for the quantitative group testing problem.
A hydraulic model outperforms work-balance models for predicting recovery kinetics from intermittent exercise
Venue: arXiv cs.OH 2022
Year: 2022

Data Science advances in sports commonly involve "big data", i.e., large sport-related data sets. However, such big data sets are not always available, necessitating specialized models that apply to relatively few observations. One important area of sport-science research that features small data sets is the study of recovery from exercise. In this area, models are typically fitted to data collected from exhaustive exercise test protocols, which athletes can perform only a few times. Recent findings highlight that established recovery such as the so-called work-balance models are too simple to adequately fit observed trends in the data. Therefore, we investigated a hydraulic model that requires the same few data points as work-balance models to be applied, but promises to predict recovery dynamics more accurately. To compare the hydraulic model to established work-balance models, we retrospectively applied them to data compiled from published studies. In total, one hydraulic model and three work-balance models were compared on data extracted from five studies. The hydraulic model outperformed established work-balance models on all defined metrics, even those that penalize models featuring higher numbers of parameters. These results incentivize further investigation of the hydraulic model as a new alternative to established performance models of energy recovery.
Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models
Venue: arXiv cs.DS 2022
Year: 2022

Correlation Clustering is an important clustering problem with many applications. We study the reconstruction version of this problem in which one is seeking to reconstruct a latent clustering that has been corrupted by random noise and adversarial modifications. Concerning the latter, there is a standard "post-adversarial" model in the literature, in which adversarial modifications come after the noise. Here, we introduce and analyse a "pre-adversarial" model in which adversarial modifications come before the noise. Given an input coming from such a semi-adversarial generative model, the goal is to reconstruct almost perfectly and with high probability the latent clustering. We focus on the case where the hidden clusters have nearly equal size and show the following. In the pre-adversarial setting, spectral algorithms are optimal, in the sense that they reconstruct all the way to the information-theoretic threshold beyond which no reconstruction is possible. This is in contrast to the post-adversarial setting, in which their ability to restore the hidden clusters stops before the threshold, but the gap is optimally filled by SDP-based algorithms. These results highlight a heretofore unknown robustness of spectral algorithms, showing them less brittle than previously thought.