OpenRaiser/Intern-Atlas huggingface dataset:
Kernelization for Treewidth-2 Vertex Deletion
Venue: arXiv cs.DS 2022
Year: 2022

The Treewidth-2 Vertex Deletion problem asks whether a set of at most $t$ vertices can be removed from a graph, such that the resulting graph has treewidth at most two. A graph has treewidth at most two if and only if it does not contain a $K_4$ minor. Hence, this problem corresponds to the NP-hard $\mathcal{F}$-Minor Cover problem with $\mathcal{F} = \{K_4\}$. For any variant of the $\mathcal{F}$-Minor Cover problem where $\mathcal{F}$ contains a planar graph, it is known that a polynomial kernel exists. I.e., a preprocessing routine that in polynomial time outputs an equivalent instance of size $t^{O(1)}$. However, this proof is non-constructive, meaning that this proof does not yield an explicit bound on the kernel size. The $\{K_4\}$-Minor Cover problem is the simplest variant of the $\mathcal{F}$-Minor Cover problem with an unknown kernel size. To develop a constructive kernelization algorithm, we present a new method to decompose graphs into near-protrusions, such that near-protrusions in this new decomposition can be reduced using elementary reduction rules. Our method extends the `approximation and tidying' framework by van Bevern et al. [Algorithmica 2012] to provide guarantees stronger than those provided by both this framework and a regular protrusion decomposition. Furthermore, we provide extensions of the elementary reduction rules used by the $\{K_4, K_{2,3}\}$-Minor Cover kernelization algorithm introduced by Donkers et al. [IPEC 2021]. Using the new decomposition method and reduction rules, we obtain a kernel consisting of $O(t^{41})$ vertices, which is the first constructive kernel. This kernel is a step towards more concrete kernelization bounds for the $\mathcal{F}$-Minor Cover problem where $\mathcal{F}$ contains a planar graph, and our decomposition provides a potential direction to achieve these new bounds.
Deep reinforcement learning guided graph neural networks for brain network analysis
Venue: arXiv cs.LG 2022
Year: 2022

Modern neuroimaging techniques, such as diffusion tensor imaging (DTI) and functional magnetic resonance imaging (fMRI), enable us to model the human brain as a brain network or connectome. Capturing brain networks' structural information and hierarchical patterns is essential for understanding brain functions and disease states. Recently, the promising network representation learning capability of graph neural networks (GNNs) has prompted many GNN-based methods for brain network analysis to be proposed. Specifically, these methods apply feature aggregation and global pooling to convert brain network instances into meaningful low-dimensional representations used for downstream brain network analysis tasks. However, existing GNN-based methods often neglect that brain networks of different subjects may require various aggregation iterations and use GNN with a fixed number of layers to learn all brain networks. Therefore, how to fully release the potential of GNNs to promote brain network analysis is still non-trivial. To solve this problem, we propose a novel brain network representation framework, namely BN-GNN, which searches for the optimal GNN architecture for each brain network. Concretely, BN-GNN employs deep reinforcement learning (DRL) to train a meta-policy to automatically determine the optimal number of feature aggregations (reflected in the number of GNN layers) required for a given brain network. Extensive experiments on eight real-world brain network datasets demonstrate that our proposed BN-GNN improves the performance of traditional GNNs on different brain network analysis tasks.
On the role of Lip Articulation in Visual Speech Perception
Venue: arXiv cs.SD 2022
Year: 2022

Generating realistic lip motion from audio to simulate speech production is critical for driving natural character animation. Previous research has shown that traditional metrics used to optimize and assess models for generating lip motion from speech are not a good indicator of subjective opinion of animation quality. Devising metrics that align with subjective opinion first requires understanding what impacts human perception of quality. In this work, we focus on the degree of articulation and run a series of experiments to study how articulation strength impacts human perception of lip motion accompanying speech. Specifically, we study how increasing under-articulated (dampened) and over-articulated (exaggerated) lip motion affects human perception of quality. We examine the impact of articulation strength on human perception when considering only lip motion, where viewers are presented with talking faces represented by landmarks, and in the context of embodied characters, where viewers are presented with photo-realistic videos. Our results show that viewers prefer over-articulated lip motion consistently more than under-articulated lip motion and that this preference generalizes across different speakers and embodiments.
Evaluation of Orientation Ambiguity and Detection Rate in April Tag and WhyCode
Venue: arXiv cs.CV 2022
Year: 2022

Fiducial systems provide a computationally cheap way for mobile robots to estimate the pose of objects, or their own pose, using just a monocular camera. However, the orientation component of the pose of fiducial markers is unreliable, which can have destructive effects in autonomous drone landing on landing pads marked with fiducial markers. This paper evaluates the April Tag and WhyCode fiducial systems in terms of orientation ambiguity and detection rate on embedded hardware. We test 2 April Tag variants - 1 default and 1 custom - and 3 Whycode variants - 1 default and 2 custom. We determine that they are suitable for autonomous drone landing applications in terms of detection rate, but may generate erroneous control signals as a result of orientation ambiguity in the pose estimates.
RoVISQ: Reduction of Video Service Quality via Adversarial Attacks on Deep Learning-based Video Compression
Venue: arXiv cs.CV 2022
Year: 2022

Video compression plays a crucial role in video streaming and classification systems by maximizing the end-user quality of experience (QoE) at a given bandwidth budget. In this paper, we conduct the first systematic study for adversarial attacks on deep learning-based video compression and downstream classification systems. Our attack framework, dubbed RoVISQ, manipulates the Rate-Distortion ($\textit{R}$-$\textit{D}$) relationship of a video compression model to achieve one or both of the following goals: (1) increasing the network bandwidth, (2) degrading the video quality for end-users. We further devise new objectives for targeted and untargeted attacks to a downstream video classification service. Finally, we design an input-invariant perturbation that universally disrupts video compression and classification systems in real time. Unlike previously proposed attacks on video classification, our adversarial perturbations are the first to withstand compression. We empirically show the resilience of RoVISQ attacks against various defenses, i.e., adversarial training, video denoising, and JPEG compression. Our extensive experimental results on various video datasets show RoVISQ attacks deteriorate peak signal-to-noise ratio by up to 5.6dB and the bit-rate by up to $\sim$ 2.4$\times$ while achieving over 90$\%$ attack success rate on a downstream classifier. Our user study further demonstrates the effect of RoVISQ attacks on users' QoE.
Coordinated Pose Control of Mobile Manipulation with an Unstable Bikebot Platform
Venue: arXiv cs.RO 2022
Year: 2022

Bikebot manipulation has advantages of the single-track robot mobility and manipulation dexterity. We present a coordinated pose control of mobile manipulation with the stationary bikebot. The challenges of the bikebot manipulation include the limited steering balance capability of the unstable bikebot and kinematic redundancy of the manipulator. We first present the steering balance model to analyze and explore the maximum steering capability to balance the stationary platform. A balancing equilibrium manifold is then proposed to describe the necessary condition to fulfill the simultaneous platform balance and posture control of the end-effector. A coordinated planning and control design is presented to determine the balance-prioritized posture control under kinematic and dynamic constraints. Extensive experiments are conducted to demonstrate the mechatronic design for autonomous plant inspection in agricultural applications. The results confirm the feasibility to use the bikebot manipulation for a plant inspection with end-effector position and orientation errors about 5 mm and 0.3 degs, respectively.
Has Your FaaS Application Been Decommissioned Yet? -- A Case Study on the Idle Timeout in Function as a Service Infrastructure
Venue: arXiv cs.DC 2022
Year: 2022

Function as a Service (FaaS) is a new cloud technology with automated resource management. Different from traditional cloud computing, each FaaS cloud function can only run a fixed period of time before being decommissioned. Furthermore, FaaS cloud providers often update their platforms (e.g., idle timeout). These changes and their associated impact are not transparent and could potentially impact the execution of the cloud functions. Hence, in this paper, we develop a methodology to characterize the cloud function idle timeout which is the duration a FaaS cloud provider keeps a cloud function instance alive without serving active traffic. Our study was conducted on three popular FaaS platforms, namely AWS Lambda, IBM and Azure Cloud Function. Moreover, we also report how long a cloud function instance can be kept alive when a user regularly polls the instance. Experimental results show that the idle timeout period has evolved from 01/2020 till 01/2022.
DiSECt: A Differentiable Simulator for Parameter Inference and Control in Robotic Cutting
Venue: arXiv cs.RO 2022
Year: 2022

Robotic cutting of soft materials is critical for applications such as food processing, household automation, and surgical manipulation. As in other areas of robotics, simulators can facilitate controller verification, policy learning, and dataset generation. Moreover, differentiable simulators can enable gradient-based optimization, which is invaluable for calibrating simulation parameters and optimizing controllers. In this work, we present DiSECt: the first differentiable simulator for cutting soft materials. The simulator augments the finite element method (FEM) with a continuous contact model based on signed distance fields (SDF), as well as a continuous damage model that inserts springs on opposite sides of the cutting plane and allows them to weaken until zero stiffness, enabling crack formation. Through various experiments, we evaluate the performance of the simulator. We first show that the simulator can be calibrated to match resultant forces and deformation fields from a state-of-the-art commercial solver and real-world cutting datasets, with generality across cutting velocities and object instances. We then show that Bayesian inference can be performed efficiently by leveraging the differentiability of the simulator, estimating posteriors over hundreds of parameters in a fraction of the time of derivative-free methods. Next, we illustrate that control parameters in the simulation can be optimized to minimize cutting forces via lateral slicing motions. Finally, we conduct experiments on a real robot arm equipped with a slicing knife to infer simulation parameters from force measurements. By optimizing the slicing motion of the knife, we show on fruit cutting scenarios that the average knife force can be reduced by more than 40% compared to a vertical cutting motion. We publish code and additional materials on our project website at https://diff-cutting-sim.github.io.
METL: a modern ETL pipeline with a dynamic mapping matrix
Venue: arXiv cs.DC 2022
Year: 2022

Modern ETL streaming pipelines extract data from various sources and forward it to multiple consumers, such as data warehouses (DW) and analytical systems that leverage machine learning (ML). However, the increasing number of systems that are connected to such pipelines requires new solutions for data integration. The canonical (or common) data model (CDM) offers such an integration. It is particular useful for integrating microservice systems into ETL pipelines. (Villaca et al 2020, Oliveira et al 2019) However, a mapping to a CDM is complex. (Lemcke et al 2012) There are three complexity problems, namely the size of the required mapping matrix, the automation of updates of the matrix in response to changes in the extraction sources and the time efficiency of the mapping. In this paper, we present a new solution for these problems. More precisely, we present a new dynamic mapping matrix (DMM), which is based on permutation matrices that are obtained by block-partitioning the full mapping matrix. We show that the DMM can be used for automated updates in response to schema changes, for parallel computation in near real-time and for highly efficient compacting. For the solution, we draw on research into matrix partitioning (Quinn 2004) and dynamic networks (Haase et al 2021). The DMM has been implemented into an app called Message ETL (METL). METL is the key part of a new ETL streaming pipeline at EOS that conducts the transformation to a CDM. The ETL pipeline is based on Kafka-streams. It extracts data from more than 80 microservices with log-based Change Data Capture (CDC) with Debezium and loads the data to a DW and an ML platform. EOS is part of the Otto-Group, the second-largest e-commerce provider in Europe.
Exploring Motion Ambiguity and Alignment for High-Quality Video Frame Interpolation
Venue: arXiv cs.CV 2022
Year: 2022

For video frame interpolation (VFI), existing deep-learning-based approaches strongly rely on the ground-truth (GT) intermediate frames, which sometimes ignore the non-unique nature of motion judging from the given adjacent frames. As a result, these methods tend to produce averaged solutions that are not clear enough. To alleviate this issue, we propose to relax the requirement of reconstructing an intermediate frame as close to the GT as possible. Towards this end, we develop a texture consistency loss (TCL) upon the assumption that the interpolated content should maintain similar structures with their counterparts in the given frames. Predictions satisfying this constraint are encouraged, though they may differ from the pre-defined GT. Without the bells and whistles, our plug-and-play TCL is capable of improving the performance of existing VFI frameworks. On the other hand, previous methods usually adopt the cost volume or correlation map to achieve more accurate image/feature warping. However, the O(N^2) ({N refers to the pixel count}) computational complexity makes it infeasible for high-resolution cases. In this work, we design a simple, efficient (O(N)) yet powerful cross-scale pyramid alignment (CSPA) module, where multi-scale information is highly exploited. Extensive experiments justify the efficiency and effectiveness of the proposed strategy.
Implicit Parameter-free Online Learning with Truncated Linear Models
Venue: arXiv cs.LG 2022
Year: 2022

Parameter-free algorithms are online learning algorithms that do not require setting learning rates. They achieve optimal regret with respect to the distance between the initial point and any competitor. Yet, parameter-free algorithms do not take into account the geometry of the losses. Recently, in the stochastic optimization literature, it has been proposed to instead use truncated linear lower bounds, which produce better performance by more closely modeling the losses. In particular, truncated linear models greatly reduce the problem of overshooting the minimum of the loss function. Unfortunately, truncated linear models cannot be used with parameter-free algorithms because the updates become very expensive to compute. In this paper, we propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor. Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties. We also conduct an empirical study demonstrating the practical utility of our algorithms.
Desirable Companion for Vertical Federated Learning: New Zeroth-Order Gradient Based Algorithm
Venue: arXiv cs.LG 2022
Year: 2022

Vertical federated learning (VFL) attracts increasing attention due to the emerging demands of multi-party collaborative modeling and concerns of privacy leakage. A complete list of metrics to evaluate VFL algorithms should include model applicability, privacy security, communication cost, and computation efficiency, where privacy security is especially important to VFL. However, to the best of our knowledge, there does not exist a VFL algorithm satisfying all these criteria very well. To address this challenging problem, in this paper, we reveal that zeroth-order optimization (ZOO) is a desirable companion for VFL. Specifically, ZOO can 1) improve the model applicability of VFL framework, 2) prevent VFL framework from privacy leakage under curious, colluding, and malicious threat models, 3) support inexpensive communication and efficient computation. Based on that, we propose a novel and practical VFL framework with black-box models, which is inseparably interconnected to the promising properties of ZOO. We believe that it takes one stride towards designing a practical VFL framework matching all the criteria. Under this framework, we raise two novel {\bf asy}nchronous ze{\bf r}oth-ord{\bf e}r algorithms for {\bf v}ertical f{\bf e}derated {\bf l}earning (AsyREVEL) with different smoothing techniques. We theoretically drive the convergence rates of AsyREVEL algorithms under nonconvex condition. More importantly, we prove the privacy security of our proposed framework under existing VFL attacks on different levels. Extensive experiments on benchmark datasets demonstrate the favorable model applicability, satisfied privacy security, inexpensive communication, efficient computation, scalability and losslessness of our framework.
Domain Adaptation Meets Zero-Shot Learning: An Annotation-Efficient Approach to Multi-Modality Medical Image Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Due to the lack of properly annotated medical data, exploring the generalization capability of the deep model is becoming a public concern. Zero-shot learning (ZSL) has emerged in recent years to equip the deep model with the ability to recognize unseen classes. However, existing studies mainly focus on natural images, which utilize linguistic models to extract auxiliary information for ZSL. It is impractical to apply the natural image ZSL solutions directly to medical images, since the medical terminology is very domain-specific, and it is not easy to acquire linguistic models for the medical terminology. In this work, we propose a new paradigm of ZSL specifically for medical images utilizing cross-modality information. We make three main contributions with the proposed paradigm. First, we extract the prior knowledge about the segmentation targets, called relation prototypes, from the prior model and then propose a cross-modality adaptation module to inherit the prototypes to the zero-shot model. Second, we propose a relation prototype awareness module to make the zero-shot model aware of information contained in the prototypes. Last but not least, we develop an inheritance attention module to recalibrate the relation prototypes to enhance the inheritance process. The proposed framework is evaluated on two public cross-modality datasets including a cardiac dataset and an abdominal dataset. Extensive experiments show that the proposed framework significantly outperforms the state of the arts.
Occlusion-Aware Self-Supervised Monocular 6D Object Pose Estimation
Venue: arXiv cs.CV 2022
Year: 2022

6D object pose estimation is a fundamental yet challenging problem in computer vision. Convolutional Neural Networks (CNNs) have recently proven to be capable of predicting reliable 6D pose estimates even under monocular settings. Nonetheless, CNNs are identified as being extremely data-driven, and acquiring adequate annotations is oftentimes very time-consuming and labor intensive. To overcome this limitation, we propose a novel monocular 6D pose estimation approach by means of self-supervised learning, removing the need for real annotations. After training our proposed network fully supervised with synthetic RGB data, we leverage current trends in noisy student training and differentiable rendering to further self-supervise the model on these unsupervised real RGB(-D) samples, seeking for a visually and geometrically optimal alignment. Moreover, employing both visible and amodal mask information, our self-supervision becomes very robust towards challenging scenarios such as occlusion. Extensive evaluations demonstrate that our proposed self-supervision outperforms all other methods relying on synthetic data or employing elaborate techniques from the domain adaptation realm. Noteworthy, our self-supervised approach consistently improves over its synthetically trained baseline and often almost closes the gap towards its fully supervised counterpart. The code and models are publicly available at https://github.com/THU-DA-6D-Pose-Group/self6dpp.git.
Deep Learning Generalization, Extrapolation, and Over-parameterization
Venue: arXiv cs.LG 2022
Year: 2022

We study the generalization of over-parameterized deep networks (for image classification) in relation to the convex hull of their training sets. Despite their great success, generalization of deep networks is considered a mystery. These models have orders of magnitude more parameters than their training samples, and they can achieve perfect accuracy on their training sets, even when training images are randomly labeled, or the contents of images are replaced with random noise. The training loss function of these models has infinite number of near zero minimizers, where only a small subset of those minimizers generalize well. Overall, it is not clear why models need to be over-parameterized, why we should use a very specific training regime to train them, and why their classifications are so susceptible to imperceivable adversarial perturbations (phenomenon known as adversarial vulnerability) \cite{papernot2016limitations,shafahi2018adversarial,tsipras2018robustness}. Some recent studies have made advances in answering these questions, however, they only consider interpolation. We show that interpolation is not adequate to understand generalization of deep networks and we should broaden our perspective.
The Online Behaviour of the Algerian Abusers in Social Media Networks
Venue: arXiv cs.SI 2022
Year: 2022

Connecting to social media networks becomes a daily task for the majority of people around the world, and the amount of shared information is growing exponentially. Thus, controlling the way in which people communicate is necessary, in order to protect them from disorientation, conflicts, aggressions, etc. In this paper, we conduct a statistical study on the cyber-bullying and the abusive content in social media (i.e. Facebook), where we try to spot the online behaviour of the abusers in the Algerian community. More specifically, we have involved 200 Facebook users from different regions among 600 to carry out this study. The aim of this investigation is to aid automatic systems of abuse detection to take decision by incorporating the online activity. Abuse detection systems require a large amount of data to perform better on such kind of texts (i.e. unstructured and informal texts), and this is due to the lack of standard orthography, where there are various Algerian dialects and languages spoken.