OpenRaiser/Intern-Atlas huggingface dataset:
Space Optimal Vertex Cover in Dynamic Streams
Venue: arXiv cs.DS 2022
Year: 2022

We optimally resolve the space complexity for the problem of finding an $α$-approximate minimum vertex cover ($α$MVC) in dynamic graph streams. We give a randomised algorithm for $α$MVC which uses $O(n^2/α^2)$ bits of space matching Dark and Konrad's lower bound [CCC 2020] up to constant factors. By computing a random greedy matching, we identify `easy' instances of the problem which can trivially be solved by returning the entire vertex set. The remaining `hard' instances, then have sparse induced subgraphs which we exploit to get our space savings and solve $α$MVC. Achieving this type of optimality result is crucial for providing a complete understanding of a problem, and it has been gaining interest within the dynamic graph streaming community. For connectivity, Nelson and Yu [SODA 2019] improved the lower bound showing that $Ω(n \log^3 n)$ bits of space is necessary while Ahn, Guha, and McGregor [SODA 2012] have shown that $O(n \log^3 n)$ bits is sufficient. For finding an $α$-approximate maximum matching, the upper bound was improved by Assadi and Shah [ITCS 2022] showing that $O(n^2/α^3)$ bits is sufficient while Dark and Konrad [CCC 2020] have shown that $Ω(n^2/α^3)$ bits is necessary. The space complexity, however, remains unresolved for many other dynamic graph streaming problems where further improvements can still be made. \end{abstract}
Class-Level Logit Perturbation
Venue: arXiv cs.LG 2022
Year: 2022

Features, logits, and labels are the three primary data when a sample passes through a deep neural network. Feature perturbation and label perturbation receive increasing attention in recent years. They have been proven to be useful in various deep learning approaches. For example, (adversarial) feature perturbation can improve the robustness or even generalization capability of learned models. However, limited studies have explicitly explored for the perturbation of logit vectors. This work discusses several existing methods related to class-level logit perturbation. A unified viewpoint between positive/negative data augmentation and loss variations incurred by logit perturbation is established. A theoretical analysis is provided to illuminate why class-level logit perturbation is useful. Accordingly, new methodologies are proposed to explicitly learn to perturb logits for both single-label and multi-label classification tasks. Extensive experiments on benchmark image classification data sets and their long-tail versions indicated the competitive performance of our learning method. As it only perturbs on logit, it can be used as a plug-in to fuse with any existing classification algorithms. All the codes are available at https://github.com/limengyang1992/lpl.
Switchable Self-attention Module
Venue: arXiv cs.CV 2022
Year: 2022

Attention mechanism has gained great success in vision recognition. Many works are devoted to improving the effectiveness of attention mechanism, which finely design the structure of the attention operator. These works need lots of experiments to pick out the optimal settings when scenarios change, which consumes a lot of time and computational resources. In addition, a neural network often contains many network layers, and most studies often use the same attention module to enhance different network layers, which hinders the further improvement of the performance of the self-attention mechanism. To address the above problems, we propose a self-attention module SEM. Based on the input information of the attention module and alternative attention operators, SEM can automatically decide to select and integrate attention operators to compute attention maps. The effectiveness of SEM is demonstrated by extensive experiments on widely used benchmark datasets and popular self-attention networks.
InTEn-LOAM: Intensity and Temporal Enhanced LiDAR Odometry and Mapping
Venue: arXiv cs.RO 2022
Year: 2022

Traditional LiDAR odometry (LO) systems mainly leverage geometric information obtained from the traversed surroundings to register laser scans and estimate LiDAR ego-motion, while it may be unreliable in dynamic or unstructured environments. This paper proposes InTEn-LOAM, a low-drift and robust LiDAR odometry and mapping method that fully exploits implicit information of laser sweeps (i.e., geometric, intensity, and temporal characteristics). Scanned points are projected to cylindrical images, which facilitate the efficient and adaptive extraction of various types of features, i.e., ground, beam, facade, and reflector. We propose a novel intensity-based points registration algorithm and incorporate it into the LiDAR odometry, enabling the LO system to jointly estimate the LiDAR ego-motion using both geometric and intensity feature points. To eliminate the interference of dynamic objects, we propose a temporal-based dynamic object removal approach to filter them out before map update. Moreover, the local map is organized and downsampled using a temporal-related voxel grid filter to maintain the similarity between the current scan and the static local map. Extensive experiments are conducted on both simulated and real-world datasets. The results show that the proposed method achieves similar or better accuracy w.r.t the state-of-the-arts in normal driving scenarios and outperforms geometric-based LO in unstructured environments.
Generalization Bounds for Deep Transfer Learning Using Majority Predictor Accuracy
Venue: arXiv cs.LG 2022
Year: 2022

We analyze new generalization bounds for deep learning models trained by transfer learning from a source to a target task. Our bounds utilize a quantity called the majority predictor accuracy, which can be computed efficiently from data. We show that our theory is useful in practice since it implies that the majority predictor accuracy can be used as a transferability measure, a fact that is also validated by our experiments.
MetaGlyph: Automatic Generation of Metaphoric Glyph-based Visualization
Venue: arXiv cs.HC 2022
Year: 2022

Glyph-based visualization achieves an impressive graphic design when associated with comprehensive visual metaphors, which help audiences effectively grasp the conveyed information through revealing data semantics. However, creating such metaphoric glyph-based visualization (MGV) is not an easy task, as it requires not only a deep understanding of data but also professional design skills. This paper proposes MetaGlyph, an automatic system for generating MGVs from a spreadsheet. To develop MetaGlyph, we first conduct a qualitative analysis to understand the design of current MGVs from the perspectives of metaphor embodiment and glyph design. Based on the results, we introduce a novel framework for generating MGVs by metaphoric image selection and an MGV construction. Specifically, MetaGlyph automatically selects metaphors with corresponding images from online resources based on the input data semantics. We then integrate a Monte Carlo tree search algorithm that explores the design of an MGV by associating visual elements with data dimensions given the data importance, semantic relevance, and glyph non-overlap. The system also provides editing feedback that allows users to customize the MGVs according to their design preferences. We demonstrate the use of MetaGlyph through a set of examples, one usage scenario, and validate its effectiveness through a series of expert interviews.
A Survey on Mobile Edge Computing for Video Streaming: Opportunities and Challenges
Venue: arXiv cs.MM 2022
Year: 2022

5G communication brings substantial improvements in the quality of service provided to various applications by achieving higher throughput and lower latency. However, interactive multimedia applications (e.g., ultra high definition video conferencing, 3D and multiview video streaming, crowd-sourced video streaming, cloud gaming, virtual and augmented reality) are becoming more ambitious with high volume and low latency video streams putting strict demands on the already congested networks. Mobile Edge Computing (MEC) is an emerging paradigm that extends cloud computing capabilities to the edge of the network i.e., at the base station level. To meet the latency requirements and avoid the end-to-end communication with remote cloud data centers, MEC allows to store and process video content (e.g., caching, transcoding, pre-processing) at the base stations. Both video on demand and live video streaming can utilize MEC to improve existing services and develop novel use cases, such as video analytics, and targeted advertisements. MEC is expected to reshape the future of video streaming by providing ultra-reliable and low latency streaming (e.g., in augmented reality, virtual reality, and autonomous vehicles), pervasive computing (e.g., in real-time video analytics), and blockchain-enabled architecture for secure live streaming. This paper presents a comprehensive survey of recent developments in MEC-enabled video streaming bringing unprecedented improvement to enable novel use cases. A detailed review of the state-of-the-art is presented covering novel caching schemes, optimal computation offloading, cooperative caching and offloading and the use of artificial intelligence (i.e., machine learning, deep learning, and reinforcement learning) in MEC-assisted video streaming services.
Test-Time Adaptation with Principal Component Analysis
Venue: arXiv cs.LG 2022
Year: 2022

Machine Learning models are prone to fail when test data are different from training data, a situation often encountered in real applications known as distribution shift. While still valid, the training-time knowledge becomes less effective, requiring a test-time adaptation to maintain high performance. Following approaches that assume batch-norm layer and use their statistics for adaptation, we propose a Test-Time Adaptation with Principal Component Analysis (TTAwPCA), which presumes a fitted PCA and adapts at test time a spectral filter based on the singular values of the PCA for robustness to corruptions. TTAwPCA combines three components: the output of a given layer is decomposed using a Principal Component Analysis (PCA), filtered by a penalization of its singular values, and reconstructed with the PCA inverse transform. This generic enhancement adds fewer parameters than current methods. Experiments on CIFAR-10-C and CIFAR- 100-C demonstrate the effectiveness and limits of our method using a unique filter of 2000 parameters.
Computer vision system to count crustacean larvae
Venue: arXiv cs.CV 2022
Year: 2022

Fish products account for about 16 percent of the human diet worldwide, as of 2017. The counting action is a significant component in growing and producing these products. Growers must count the fish accurately, to do so technological solutions are needed. Two computer vision systems to automatically count crustacean larvae grown in industrial ponds were developed. The first system included an iPhone 11 camera with 3024X4032 resolution which acquired images from an industrial pond in indoor conditions. Two experiments were performed with this system, the first one included 200 images acquired in one day on growth stages 9,10 with an iPhone 11 camera on specific illumination condition. In the second experiment, a larvae industrial pond was photographed for 11 days with two devices an iPhone 11 and a SONY DSCHX90V cameras. With the first device (iPhone 11) two illumination conditions were tested. In each condition, 110 images were acquired. That system resulted in an accuracy of 88.4 percent image detection. The second system included a DSLR Nikon D510 camera with a 2000X2000 resolution with which seven experiments were performed outside the industrial pond. Images were acquired on day 1 of larvae growing stage resulting in the acquisition of a total of 700 images. That system resulted in an accuracy of 86 percent for a density of 50. An algorithm that automatically counts the number of larvae was developed for both cases based on the YOLOv5 CNN model. In addition, in this study, a larvae growth function was developed. Daily, several larvae were taken manually from the industrial pond and analyzed under a microscope. Once the growth stage was determined, images of the larva were acquired. Each larva's length was measured manually from the images. The most suitable model was the Gompertz model with a goodness of fit index of R squared of 0.983.
Skin Lesion Recognition with Class-Hierarchy Regularized Hyperbolic Embeddings
Venue: arXiv cs.CV 2022
Year: 2022

In practice, many medical datasets have an underlying taxonomy defined over the disease label space. However, existing classification algorithms for medical diagnoses often assume semantically independent labels. In this study, we aim to leverage class hierarchy with deep learning algorithms for more accurate and reliable skin lesion recognition. We propose a hyperbolic network to learn image embeddings and class prototypes jointly. The hyperbola provably provides a space for modeling hierarchical relations better than Euclidean geometry. Meanwhile, we restrict the distribution of hyperbolic prototypes with a distance matrix that is encoded from the class hierarchy. Accordingly, the learned prototypes preserve the semantic class relations in the embedding space and we can predict the label of an image by assigning its feature to the nearest hyperbolic class prototype. We use an in-house skin lesion dataset which consists of around 230k dermoscopic images on 65 skin diseases to verify our method. Extensive experiments provide evidence that our model can achieve higher accuracy with less severe classification errors than models without considering class relations.
A probabilistic virtual process chain to quantify process-induced uncertainties in Sheet Molding Compounds
Venue: arXiv cs.CE 2022
Year: 2022

The manufacturing process of Sheet Molding Compound (SMC) influences the properties of a component in a non-deterministic fashion. To predict this influence on the mechanical performance, we develop a virtual process chain acting as a digital twin for SMC specimens from compounding to failure. More specifically, we inform a structural simulation with individual fields for orientation and volume fraction computed from a direct bundle simulation of the manufacturing process. The structural simulation employs an interpolated direct deep material network to upscale a tailored SMC damage model. We evaluate hundreds of virtual specimens and conduct a probabilistic analysis of the mechanical performance. We estimate the contribution to uncertainty originating from the process-induced inherent random microstructure and from varying initial SMC stack configurations. Our predicted results are in good agreement with experimental tensile tests and thermogravimetric analysis.
A Meta-level Analysis of Online Anomaly Detectors
Venue: arXiv cs.LG 2022
Year: 2022

Real-time detection of anomalies in streaming data is receiving increasing attention as it allows us to raise alerts, predict faults, and detect intrusions or threats across industries. Yet, little attention has been given to compare the effectiveness and efficiency of anomaly detectors for streaming data (i.e., of online algorithms). In this paper, we present a qualitative, synthetic overview of major online detectors from different algorithmic families (i.e., distance, density, tree or projection-based) and highlight their main ideas for constructing, updating and testing detection models. Then, we provide a thorough analysis of the results of a quantitative experimental evaluation of online detection algorithms along with their offline counterparts. The behavior of the detectors is correlated with the characteristics of different datasets (i.e., meta-features), thereby providing a meta-level analysis of their performance. Our study addresses several missing insights from the literature such as (a) how reliable are detectors against a random classifier and what dataset characteristics make them perform randomly; (b) to what extent online detectors approximate the performance of offline counterparts; (c) which sketch strategy and update primitives of detectors are best to detect anomalies visible only within a feature subspace of a dataset; (d) what are the tradeoffs between the effectiveness and the efficiency of detectors belonging to different algorithmic families; (e) which specific characteristics of datasets yield an online algorithm to outperform all others.
TDB: Breaking All Hop-Constrained Cycles in Billion-Scale Directed Graphs
Venue: arXiv cs.DB 2022
Year: 2022

The Feedback vertex set with the minimum size is one of Karp's 21 NP-complete problems targeted at breaking all the cycles in a graph. This problem is applicable to a broad variety of domains, including E-commerce networks, database systems, and program analysis. In reality, users are frequently most concerned with the hop-constrained cycles (i.e., cycles with a limited number of hops). For instance, in the E-commerce networks, the fraud detection team would discard cycles with a high number of hops since they are less relevant and grow exponentially in size. Thus, it is quite reasonable to investigate the feedback vertex set problem in the context of hop-constrained cycles, namely hop-constrained cycle cover problem. It is concerned with determining a set of vertices that covers all hop-constrained cycles in a given directed graph. A common method to solve this is to use a bottom-up algorithm, where it iteratively selects cover vertices into the result set. Based on this paradigm, the existing works mainly focus on the vertices orders and several heuristic strategies. In this paper, a totally opposite cover process topdown is proposed and bounds are presented on it. Surprisingly, both theoretical time complexity and practical performance are improved.
Traffic Prediction and Fast Uplink for Hidden Markov IoT Models
Venue: arXiv cs.NI 2022
Year: 2022

In this work, we present a novel traffic prediction and fast uplink framework for IoT networks controlled by binary Markovian events. First, we apply the forward algorithm with hidden Markov models (HMM) in order to schedule the available resources to the devices with maximum likelihood activation probabilities via fast uplink grant. In addition, we evaluate the regret metric as the number of wasted transmission slots to evaluate the performance of the prediction. Next, we formulate a fairness optimization problem to minimize the age of information while keeping the regret as minimum as possible. Finally, we propose an iterative algorithm to estimate the model hyperparameters (activation probabilities) in a real-time application and apply an online-learning version of the proposed traffic prediction scheme. Simulation results show that the proposed algorithms outperform baseline models such as time division multiple access (TDMA) and grant-free (GF) random-access in terms of regret, the efficiency of system usage, and age of information.
A Distributed Acoustic Sensor System for Intelligent Transportation using Deep Learning
Venue: arXiv cs.LG 2022
Year: 2022

Intelligent transport systems (ITS) are pivotal in the development of sustainable and green urban living. ITS is data-driven and enabled by the profusion of sensors ranging from pneumatic tubes to smart cameras. This work explores a novel data source based on optical fibre-based distributed acoustic sensors (DAS) for traffic analysis. Detecting the type of vehicle and estimating the occupancy of vehicles are prime concerns in ITS. The first is motivated by the need for tracking, controlling, and forecasting traffic flow. The second targets the regulation of high occupancy vehicle lanes in an attempt to reduce emissions and congestion. These tasks are often conducted by individuals inspecting vehicles or through the use of emerging computer vision technologies. The former is not scale-able nor efficient whereas the latter is intrusive to passengers' privacy. To this end, we propose a deep learning technique to analyse DAS signals to address this challenge through continuous sensing and without exposing personal information. We propose a deep learning method for processing DAS signals and achieve 92% vehicle classification accuracy and 92-97% in occupancy detection based on DAS data collected under controlled conditions.
Distributed SDN-based Load-balanced Routing for Low Earth Orbit Satellite Constellation Networks
Venue: arXiv cs.NI 2022
Year: 2022

With the current trend towards low Earth orbit mega-constellations with inter-satellite links, efficient routing in such highly dynamic space-borne networks is becoming increasingly important. Due to the distinct network topology, specifically tailored solutions are required. Firstly, the relative movement of the constellation causes frequent handover events between the satellites and the terminals on ground. Furthermore, unevenly distributed traffic demands lead to geographical hot spots. The physical size of the network also implies significant propagation delays. Therefore, monitoring the dynamic topology changes and link loads on a network-wide basis for routing purposes is typically impractical with massive signaling overhead. To address these issues, we propose a distributed load-balanced routing scheme based on Software Defined Networking. The approach divides the large-scale network into sub-sections, called clusters. In order to minimize signaling overhead, packets are forwarded between these clusters according to geographical heuristics. Within each cluster active Quality of Service-aware load-balancing is applied. The responsible on-board network controller forwards routing instructions based on the network state information in its cluster. We also analyze specific design choices for the clusters and the interfaces between them. The protocol has been implemented in a system-level simulator and compared to a source-routed benchmark solution.
Exploiting Semantic Communication for Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2022
Year: 2022

A novel semantics-empowered two-user uplink non-orthogonal multiple access (NOMA) framework is proposed for resource efficiency enhancement. More particularly, a secondary far user (F-user) employs the semantic communication (SemCom) while a primary near user (N-user) employs the conventional bit-based communication (BitCom). The fundamental performance limit, namely semantic-versus-bit (SvB) rate region, of the proposed semantics-empowered NOMA framework is characterized. The equivalent SvB rate region achieved by the conventional BitCom-based NOMA is provided as the baseline scheme. It unveils that, compared to BitCom, SemCom can significantly improve the F-user's performance when its permitted transmit power is strictly capped, but may perform worse when its permitted transmit power is high. Guided by this result, the proposed semantics-empowered NOMA framework is investigated over fading channels. An opportunistic SemCom and BitCom scheme is proposed, which enables the secondary F-user to participate in NOMA via the most suitable communication method at each fading state, thus striking a good tradeoff between its own achieved performance and the interference imposed to the primary N-user. Two scenarios are considered for employing the opportunistic scheme, namely on-off resource management and continuous resource management. For each scenario, the optimal communication policy over fading channels is derived for maximizing the ergodic semantic rate achieved at the secondary F-user, subject to the minimum ergodic bit rate constraint of the primary N-user. Numerical results show that the proposed opportunistic scheme in both scenarios can achieve higher communication performance for NOMA than the baseline schemes merely employing SemCom or BitCom.