OpenRaiser/Intern-Atlas huggingface dataset:
Cross-Domain Graph Anomaly Detection via Anomaly-aware Contrastive Alignment
Venue: arXiv cs.LG 2022
Year: 2022

Cross-domain graph anomaly detection (CD-GAD) describes the problem of detecting anomalous nodes in an unlabelled target graph using auxiliary, related source graphs with labelled anomalous and normal nodes. Although it presents a promising approach to address the notoriously high false positive issue in anomaly detection, little work has been done in this line of research. There are numerous domain adaptation methods in the literature, but it is difficult to adapt them for GAD due to the unknown distributions of the anomalies and the complex node relations embedded in graph data. To this end, we introduce a novel domain adaptation approach, namely Anomaly-aware Contrastive alignmenT (ACT), for GAD. ACT is designed to jointly optimise: (i) unsupervised contrastive learning of normal representations of nodes in the target graph, and (ii) anomaly-aware one-class alignment that aligns these contrastive node representations and the representations of labelled normal nodes in the source graph, while enforcing significant deviation of the representations of the normal nodes from the labelled anomalous nodes in the source graph. In doing so, ACT effectively transfers anomaly-informed knowledge from the source graph to learn the complex node relations of the normal class for GAD on the target graph without any specification of the anomaly distributions. Extensive experiments on eight CD-GAD settings demonstrate that our approach ACT achieves substantially improved detection performance over 10 state-of-the-art GAD methods. Code is available at https://github.com/QZ-WANG/ACT.
Computing the optimal BWT of very large string collections
Venue: arXiv cs.DS 2022
Year: 2022

It is known that the exact form of the Burrows-Wheeler-Transform (BWT) of a string collection depends, in most implementations, on the input order of the strings in the collection. Reordering strings of an input collection affects the number of equal-letter runs $r$, arguably the most important parameter of BWT-based data structures, such as the FM-index or the $r$-index. Bentley, Gibney, and Thankachan [ESA 2020] introduced a linear-time algorithm for computing the permutation of the input collection which yields the minimum number of runs of the resulting BWT. In this paper, we present the first tool that guarantees a Burrows-Wheeler-Transform with minimum number of runs (optBWT), by combining i) an algorithm that builds the BWT from a string collection (either SAIS-based [Cenzato et al., SPIRE 2021] or BCR [Bauer et al., CPM 2011]); ii) the SAP array data structure introduced in [Cox et al., Bioinformatics, 2012]; and iii) the algorithm by Bentley et al. We present results both on real-life and simulated data, showing that the improvement achieved in terms of $r$ with respect to the input order is significant and the overhead created by the computation of the optimal BWT negligible, making our tool competitive with other tools for BWT-computation in terms of running time and space usage. In particular, on real data the optBWT obtains up to 31 times fewer runs with only a $1.39\times$ slowdown. Source code is available at https://github.com/davidecenzato/optimalBWT.git.
Denoising after Entropy-based Debiasing A Robust Training Method for Dataset Bias with Noisy Labels
Venue: arXiv cs.LG 2022
Year: 2022

Improperly constructed datasets can result in inaccurate inferences. For instance, models trained on biased datasets perform poorly in terms of generalization (i.e., dataset bias). Recent debiasing techniques have successfully achieved generalization performance by underestimating easy-to-learn samples (i.e., bias-aligned samples) and highlighting difficult-to-learn samples (i.e., bias-conflicting samples). However, these techniques may fail owing to noisy labels, because the trained model recognizes noisy labels as difficult-to-learn and thus highlights them. In this study, we find that earlier approaches that used the provided labels to quantify difficulty could be affected by the small proportion of noisy labels. Furthermore, we find that running denoising algorithms before debiasing is ineffective because denoising algorithms reduce the impact of difficult-to-learn samples, including valuable bias-conflicting samples. Therefore, we propose an approach called denoising after entropy-based debiasing, i.e., DENEB, which has three main stages. (1) The prejudice model is trained by emphasizing (bias-aligned, clean) samples, which are selected using a Gaussian Mixture Model. (2) Using the per-sample entropy from the output of the prejudice model, the sampling probability of each sample that is proportional to the entropy is computed. (3) The final model is trained using existing denoising algorithms with the mini-batches constructed by following the computed sampling probability. Compared to existing debiasing and denoising algorithms, our method achieves better debiasing performance on multiple benchmarks.
Coevolutionary Framework for Generalized Multimodal Multi-objective Optimization
Venue: arXiv cs.NE 2022
Year: 2022

Most multimodal multi-objective evolutionary algorithms (MMEAs) aim to find all global Pareto optimal sets (PSs) for a multimodal multi-objective optimization problem (MMOP). However, in real-world problems, decision makers (DMs) may be also interested in local PSs. Also, searching for both global and local PSs is more general in view of dealing with MMOPs, which can be seen as a generalized MMOP. In addition, the state-of-the-art MMEAs exhibit poor convergence on high-dimension MMOPs. To address the above two issues, in this study, a novel coevolutionary framework termed CoMMEA for multimodal multi-objective optimization is proposed to better obtain both global and local PSs, and simultaneously, to improve the convergence performance in dealing with high-dimension MMOPs. Specifically, the CoMMEA introduces two archives to the search process, and coevolves them simultaneously through effective knowledge transfer. The convergence archive assists the CoMMEA to quickly approaching the Pareto optimal front (PF). The knowledge of the converged solutions is then transferred to the diversity archive which utilizes the local convergence indicator and the $ε$-dominance-based method to obtain global and local PSs effectively. Experimental results show that CoMMEA is competitive compared to seven state-of-the-art MMEAs on fifty-four complex MMOPs.
ViTAL: Vision-Based Terrain-Aware Locomotion for Legged Robots
Venue: arXiv cs.RO 2022
Year: 2022

This work is on vision-based planning strategies for legged robots that separate locomotion planning into foothold selection and pose adaptation. Current pose adaptation strategies optimize the robot's body pose relative to given footholds. If these footholds are not reached, the robot may end up in a state with no reachable safe footholds. Therefore, we present a Vision-Based Terrain-Aware Locomotion (ViTAL) strategy that consists of novel pose adaptation and foothold selection algorithms. ViTAL introduces a different paradigm in pose adaptation that does not optimize the body pose relative to given footholds, but the body pose that maximizes the chances of the legs in reaching safe footholds. ViTAL plans footholds and poses based on skills that characterize the robot's capabilities and its terrain-awareness. We use the 90 kg HyQ and 140 kg HyQReal quadruped robots to validate ViTAL, and show that they are able to climb various obstacles including stairs, gaps, and rough terrains at different speeds and gaits. We compare ViTAL with a baseline strategy that selects the robot pose based on given selected footholds, and show that ViTAL outperforms the baseline.
Wigner Distribution Deconvolution Adaptation for Live Ptychography Reconstruction
Venue: arXiv cs.IT 2022
Year: 2022

We propose a modification of Wigner Distribution Deconvolution (WDD) to support live processing ptychography. Live processing allows to reconstruct and display the specimen transfer function gradually while diffraction patterns are acquired. For this purpose we reformulate WDD and apply a dimensionality reduction technique that reduces memory consumption and increases processing speed. We show numerically that this approach maintains the reconstruction quality of specimen transfer functions as well as reduces computational complexity during acquisition processes. Although we only present the reconstruction for Scanning Transmission Electron Microscopy (STEM) datasets, in general, the live processing algorithm we present in this paper can be applied to real-time ptychographic reconstruction for different fields of application.
On Solution Functions of Optimization: Universal Approximation and Covering Number Bounds
Venue: arXiv cs.LG 2022
Year: 2022

We study the expressibility and learnability of convex optimization solution functions and their multi-layer architectural extension. The main results are: \emph{(1)} the class of solution functions of linear programming (LP) and quadratic programming (QP) is a universal approximant for the $C^k$ smooth model class or some restricted Sobolev space, and we characterize the rate-distortion, \emph{(2)} the approximation power is investigated through a viewpoint of regression error, where information about the target function is provided in terms of data observations, \emph{(3)} compositionality in the form of a deep architecture with optimization as a layer is shown to reconstruct some basic functions used in numerical analysis without error, which implies that \emph{(4)} a substantial reduction in rate-distortion can be achieved with a universal network architecture, and \emph{(5)} we discuss the statistical bounds of empirical covering numbers for LP/QP, as well as a generic optimization problem (possibly nonconvex) by exploiting tame geometry. Our results provide the \emph{first rigorous analysis of the approximation and learning-theoretic properties of solution functions} with implications for algorithmic design and performance guarantees.
Requirements Development for IoT Systems with UCM4IoT
Venue: arXiv cs.SE 2022
Year: 2022

The engineering of IoT (Internet of Things) systems brings about various challenges due to the inherent complexities associated with such adaptive systems. Addressing the adaptive nature of IoT systems in the early stages of the development life cycle is essential for developing a complete and precise system specification. In this paper, we propose a use case-based modelling language, UCM4IoT, to support requirements elicitation and specification of IoT systems. UCM4IoT takes into account the heterogeneity of IoT systems and provides domain-specific language constructs to model the different facets of IoT systems. The language also incorporates the notion of exceptional situations and adaptive system behaviour. Our language is supported with a textual modelling environment to assist modellers in writing use cases. The environment supports syntax-directed editing, validation of use case models, and requirements analysis. The proposed language and tool is demonstrated and evaluated with two case studies: smart store system and smart fire alarm system.
Re-evaluating sample efficiency in de novo molecule generation
Venue: arXiv cs.CE 2022
Year: 2022

De novo molecule generation can suffer from data inefficiency; requiring large amounts of training data or many sampled data points to conduct objective optimization. The latter is a particular disadvantage when combining deep generative models with computationally expensive molecule scoring functions (a.k.a. oracles) commonly used in computer-aided drug design. Recent works have therefore focused on methods to improve sample efficiency in the context of de novo molecule drug design, or to benchmark it. In this work, we discuss and adapt a recent sample efficiency benchmark to better reflect realistic goals also with respect to the quality of chemistry generated, which must always be considered in the context of small-molecule drug design; we then re-evaluate all benchmarked generative models. We find that accounting for molecular weight and LogP with respect to the training data, and the diversity of chemistry proposed, re-orders the ranking of generative models. In addition, we benchmark a recently proposed method to improve sample efficiency (Augmented Hill-Climb) and found it ranked top when considering both the sample efficiency and chemistry of molecules generated. Continual improvements in sample efficiency and chemical desirability enable more routine integration of computationally expensive scoring functions on a more realistic timescale.
Measuring Competency of Machine Learning Systems and Enforcing Reliability
Venue: arXiv cs.LG 2022
Year: 2022

We explore the impact of environmental conditions on the competency of machine learning agents and how real-time competency assessments improve the reliability of ML agents. We learn a representation of conditions which impact the strategies and performance of the ML agent enabling determination of actions the agent can make to maintain operator expectations in the case of a convolutional neural network that leverages visual imagery to aid in the obstacle avoidance task of a simulated self-driving vehicle.
Unauthorized Drone Detection: Experiments and Prototypes
Venue: arXiv cs.CV 2022
Year: 2022

The increase in the number of unmanned aerial vehicles a.k.a. drones pose several threats to public privacy, critical infrastructure and cyber security. Hence, detecting unauthorized drones is a significant problem which received attention in the last few years. In this paper, we present our experimental work on three drone detection methods (i.e., acoustic detection, radio frequency (RF) detection, and visual detection) to evaluate their efficacy in both indoor and outdoor environments. Owing to the limitations of these schemes, we present a novel encryption-based drone detection scheme that uses a two-stage verification of the drone's received signal strength indicator (RSSI) and the encryption key generated from the drone's position coordinates to reliably detect an unauthorized drone in the presence of authorized drones.
Optimal list decoding from noisy entropy inequality
Venue: arXiv cs.IT 2022
Year: 2022

A noisy entropy inequality for boolean functions by Samorodnitsky is applied to binary codes. It is shown that a binary code that achieves capacity on the binary erasure channel admits optimal list size for list decoding on some binary symmetric channels (in a regime where this optimal list size is exponentially large).
Compound Tokens: Channel Fusion for Vision-Language Representation Learning
Venue: arXiv cs.CV 2022
Year: 2022

We present an effective method for fusing visual-and-language representations for several question answering tasks including visual question answering and visual entailment. In contrast to prior works that concatenate unimodal representations or use only cross-attention, we compose multimodal representations via channel fusion. By fusing on the channels, the model is able to more effectively align the tokens compared to standard methods. These multimodal representations, which we call compound tokens are generated with cross-attention transformer layers. First, vision tokens are used as queries to retrieve compatible text tokens through cross-attention. We then chain the vision tokens and the queried text tokens along the channel dimension. We call the resulting representations compound tokens. A second group of compound tokens are generated using an analogous process where the text tokens serve as queries to the cross-attention layer. We concatenate all the compound tokens for further processing with multimodal encoder. We demonstrate the effectiveness of compound tokens using an encoder-decoder vision-language model trained end-to-end in the open-vocabulary setting. Compound Tokens achieve highly competitive performance across a range of question answering tasks including GQA, VQA2.0, and SNLI-VE.
Prediction of Scene Plausibility
Venue: arXiv cs.CV 2022
Year: 2022

Understanding the 3D world from 2D images involves more than detection and segmentation of the objects within the scene. It also includes the interpretation of the structure and arrangement of the scene elements. Such understanding is often rooted in recognizing the physical world and its limitations, and in prior knowledge as to how similar typical scenes are arranged. In this research we pose a new challenge for neural network (or other) scene understanding algorithms - can they distinguish between plausible and implausible scenes? Plausibility can be defined both in terms of physical properties and in terms of functional and typical arrangements. Hence, we define plausibility as the probability of encountering a given scene in the real physical world. We build a dataset of synthetic images containing both plausible and implausible scenes, and test the success of various vision models in the task of recognizing and understanding plausibility.
Multi-resolution Monocular Depth Map Fusion by Self-supervised Gradient-based Composition
Venue: arXiv cs.CV 2022
Year: 2022

Monocular depth estimation is a challenging problem on which deep neural networks have demonstrated great potential. However, depth maps predicted by existing deep models usually lack fine-grained details due to the convolution operations and the down-samplings in networks. We find that increasing input resolution is helpful to preserve more local details while the estimation at low resolution is more accurate globally. Therefore, we propose a novel depth map fusion module to combine the advantages of estimations with multi-resolution inputs. Instead of merging the low- and high-resolution estimations equally, we adopt the core idea of Poisson fusion, trying to implant the gradient domain of high-resolution depth into the low-resolution depth. While classic Poisson fusion requires a fusion mask as supervision, we propose a self-supervised framework based on guided image filtering. We demonstrate that this gradient-based composition performs much better at noisy immunity, compared with the state-of-the-art depth map fusion method. Our lightweight depth fusion is one-shot and runs in real-time, making our method 80X faster than a state-of-the-art depth fusion method. Quantitative evaluations demonstrate that the proposed method can be integrated into many fully convolutional monocular depth estimation backbones with a significant performance boost, leading to state-of-the-art results of detail enhancement on depth maps.
Exploring the Limits of Differentially Private Deep Learning with Group-wise Clipping
Venue: arXiv cs.LG 2022
Year: 2022

Differentially private deep learning has recently witnessed advances in computational efficiency and privacy-utility trade-off. We explore whether further improvements along the two axes are possible and provide affirmative answers leveraging two instantiations of \emph{group-wise clipping}. To reduce the compute time overhead of private learning, we show that \emph{per-layer clipping}, where the gradient of each neural network layer is clipped separately, allows clipping to be performed in conjunction with backpropagation in differentially private optimization. This results in private learning that is as memory-efficient and almost as fast per training update as non-private learning for many workflows of interest. While per-layer clipping with constant thresholds tends to underperform standard flat clipping, per-layer clipping with adaptive thresholds matches or outperforms flat clipping under given training epoch constraints, hence attaining similar or better task performance within less wall time. To explore the limits of scaling (pretrained) models in differentially private deep learning, we privately fine-tune the 175 billion-parameter GPT-3. We bypass scaling challenges associated with clipping gradients that are distributed across multiple devices with \emph{per-device clipping} that clips the gradient of each model piece separately on its host device. Privately fine-tuning GPT-3 with per-device clipping achieves a task performance at $ε=1$ better than what is attainable by non-privately fine-tuning the largest GPT-2 on a summarization task.
Node and Edge Centrality based Failures in Multi-layer Complex Networks
Venue: arXiv cs.SI 2022
Year: 2022

Multi-layer complex networks (MLCN) appears in various domains, such as, transportation, supply chains, etc. Failures in MLCN can lead to major disruptions in systems. Several research have focussed on different kinds of failures, such as, cascades, their reasons and ways to avoid them. This paper considers failures in a specific type of MLCN where the lower layer provides services to the higher layer without cross layer interaction, typical of a computer network. A three layer MLCN is constructed with the same set of nodes where each layer has different characteristics, the bottom most layer is Erdos-Renyi (ER) random graph with shortest path hop count among the nodes as gaussian, the middle layer is ER graph with higher number of edges from the previous, and the top most layer is scale free graph with even higher number of edges. Both edge and node failures are considered. Failures happen with decreasing order of centralities of edges and nodes in static batch mode and when the centralities change dynamically with progressive failures. Emergent pattern of three key parameters, namely, average shortest path length (ASPL), total shortest path count (TSPC) and total number of edges (TNE) for all the three layers after node or edge failures are studied. Extensive simulations show that all but one parameters show definite degrading patterns. Surprising, ASPL for the middle layer starts showing a chaotic behavior beyond a certain point for all types of failures.
High-Speed Resource Allocation Algorithm Using a Coherent Ising Machine for NOMA Systems
Venue: arXiv cs.IT 2022
Year: 2022

Non-orthogonal multiple access (NOMA) technique is important for achieving a high data rate in next-generation wireless communications. A key challenge to fully utilizing the effectiveness of the NOMA technique is the optimization of the resource allocation (RA), e.g., channel and power. However, this RA optimization problem is NP-hard, and obtaining a good approximation of a solution with a low computational complexity algorithm is not easy. To overcome this problem, we propose the coherent Ising machine (CIM) based optimization method for channel allocation in NOMA systems. The CIM is an Ising system that can deliver fair approximate solutions to combinatorial optimization problems at high speed (millisecond order) by operating optimization algorithms based on mutually connected photonic neural networks. The performance of our proposed method was evaluated using a simulation model of the CIM. We compared the performance of our proposed method to simulated annealing, a conventional-NOMA pairing scheme, deep Q learning based scheme, and an exhaustive search scheme. Simulation results indicate that our proposed method is superior in terms of speed and the attained optimal solutions.