OpenRaiser/Intern-Atlas huggingface dataset:
DGraph: A Large-Scale Financial Dataset for Graph Anomaly Detection
Venue: arXiv cs.SI 2023
Year: 2023

Graph Anomaly Detection (GAD) has recently become a hot research spot due to its practicability and theoretical value. Since GAD emphasizes the application and the rarity of anomalous samples, enriching the varieties of its datasets is fundamental work. Thus, this paper present DGraph, a real-world dynamic graph in the finance domain. DGraph overcomes many limitations of current GAD datasets. It contains about 3M nodes, 4M dynamic edges, and 1M ground-truth nodes. We provide a comprehensive observation of DGraph, revealing that anomalous nodes and normal nodes generally have different structures, neighbor distribution, and temporal dynamics. Moreover, it suggests that unlabeled nodes are also essential for detecting fraudsters. Furthermore, we conduct extensive experiments on DGraph. Observation and experiments demonstrate that DGraph is propulsive to advance GAD research and enable in-depth exploration of anomalous nodes.
Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling
Venue: arXiv cs.LG 2023
Year: 2023

Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graph-structured data. To address its scalability issue due to the recursive embedding of neighboring features, graph topology sampling has been proposed to reduce the memory and computational cost of training GCNs, and it has achieved comparable test performance to those without topology sampling in many empirical studies. To the best of our knowledge, this paper provides the first theoretical justification of graph topology sampling in training (up to) three-layer GCNs for semi-supervised node classification. We formally characterize some sufficient conditions on graph topology sampling such that GCN training leads to a diminishing generalization error. Moreover, our method tackles the nonconvex interaction of weights across layers, which is under-explored in the existing theoretical analyses of GCNs. This paper characterizes the impact of graph structures and topology sampling on the generalization performance and sample complexity explicitly, and the theoretical findings are also justified through numerical experiments.
Determination of action model equivalence and simplification of action model
Venue: arXiv cs.AI 2023
Year: 2023

In this paper, we study two problems: determining action model equivalence and minimizing the event space of an action model under certain structural relationships. The Kripke model equivalence is perfectly caught by the structural relationship called bisimulation. In this paper, we propose the generalized action emulation perfectly catching the action model equivalence. Previous structural relationships sufficient for the action model equivalence, i.e. the bisimulation, the propositional action emulation, the action emulation, and the action emulation of canonical action models, can be described by various restricted versions of the generalized action emulation. We summarize four critical properties of the atom set over preconditions, and prove that any formula set satisfying these properties can be used to restrict the generalized action emulation to determine the action model equivalence by an iteration algorithm. We also construct a new formula set with these four properties, which is generally more efficient than the atom set. The technique of the partition refinement has been used to minimize the world space of a Kripke model under the bisimulation. Applying the partition refinement to action models allows one to minimize their event spaces under the bisimulation. The propositional action emulation is weaker than bismulation but still sufficient for the action model equivalence. We prove that it is PSPACE-complete to minimize the event space of an action model under the propositional action emulation, and provide a PSPACE algorithm for it. Finally, we prove that minimize the event space under the action model equivalence is PSPACE-hard, and propose a computable method based on the canonical formulas of modal logics to solve this problem.
ErgoTac-Belt: Anticipatory Vibrotactile Feedback to Lead Centre of Pressure during Walking
Venue: arXiv cs.HC 2023
Year: 2023

Balance and gait disorders are the second leading cause of falls, which, along with consequent injuries, are reported as major public health problems all over the world. For patients who do not require mechanical support, vibrotactile feedback interfaces have proven to be a successful approach in restoring balance. Most of the existing strategies assess trunk or head tilt and velocity or plantar forces, and are limited to the analysis of stance. On the other hand, central to balance control is the need to maintain the body's centre of pressure (CoP) within feasible limits of the support polygon (SP), as in standing, or on track to a new SP, as in walking. Hence, this paper proposes an exploratory study to investigate whether vibrotactile feedback can be employed to lead human CoP during walking. The ErgoTac-Belt vibrotactile device is introduced to instruct the users about the direction to take, both in the antero-posterior and medio-lateral axes. An anticipatory strategy is adopted here, to give the users enough time to react to the stimuli. Experiments on ten healthy subjects demonstrated the promising capability of the proposed device to guide the users' CoP along a predefined reference path, with similar performance as the one achieved with visual feedback. Future developments will investigate our strategy and device in guiding the CoP of elderly or individuals with vestibular impairments, who may not be aware of or, able to figure out, a safe and ergonomic CoP path.
String Diagrams for Layered Explanations
Venue: arXiv cs.LO 2023
Year: 2023

We propose a categorical framework to reason about scientific explanations: descriptions of a phenomenon meant to translate it into simpler terms, or into a context that has been already understood. Our motivating examples come from systems biology, electrical circuit theory, and concurrency. We demonstrate how three explanatory models in these seemingly diverse areas can be all understood uniformly via a graphical calculus of layered props. Layered props allow for a compact visual presentation of the same phenomenon at different levels of precision, as well as the translation between these levels. Notably, our approach allows for partial explanations, that is, for translating just one part of a diagram while keeping the rest of the diagram untouched. Furthermore, our approach paves the way for formal reasoning about counterfactual models in systems biology.
Learning with Muscles: Benefits for Data-Efficiency and Robustness in Anthropomorphic Tasks
Venue: arXiv cs.RO 2023
Year: 2023

Humans are able to outperform robots in terms of robustness, versatility, and learning of new tasks in a wide variety of movements. We hypothesize that highly nonlinear muscle dynamics play a large role in providing inherent stability, which is favorable to learning. While recent advances have been made in applying modern learning techniques to muscle-actuated systems both in simulation as well as in robotics, so far, no detailed analysis has been performed to show the benefits of muscles when learning from scratch. Our study closes this gap and showcases the potential of muscle actuators for core robotics challenges in terms of data-efficiency, hyperparameter sensitivity, and robustness.
Dreamento: an open-source dream engineering toolbox for sleep EEG wearables
Venue: arXiv cs.HC 2023
Year: 2023

We introduce Dreamento (Dream engineering toolbox), an open-source Python package for dream engineering using sleep electroencephalography (EEG) wearables. Dreamento main functions are (1) real-time recording, monitoring, analysis, and sensory stimulation, and (2) offline post-processing of the resulting data, both in a graphical user interface (GUI). In real-time, Dreamento is capable of (1) data recording, visualization, and navigation, (2) power-spectrum analysis, (3) automatic sleep scoring, (4) sensory stimulation (visual, auditory, tactile), (5) establishing text-to-speech communication, and (6) managing annotations of automatic and manual events. The offline functions aid in post-processing the acquired data with features to reformat the wearable data and integrate it with non-wearable recorded modalities such as electromyography (EMG). While Dreamento was primarily developed for (lucid) dreaming studies, its applications can be extended to other areas of sleep research such as closed-loop auditory stimulation and targeted memory reactivation.
An Evaluation Study of 2D and 3D Teleconferencing for Remote Physical Therapy
Venue: arXiv cs.HC 2023
Year: 2023

The present research investigates the effectiveness of using a telepresence system compared to a video conferencing system and the effectiveness of using two cameras compared to one camera for remote physical therapy. We used Telegie as our telepresence system, which allowed users to see an environment captured with RGBD cameras in 3D through a VR headset. Since both telepresence and the inclusion of a second camera provide users with additional spatial information, we examined this affordance within the relevant context of remote physical therapy. Our dyadic study across different time zones paired 11 physical therapists with 76 participants who took on the role of patients for a remote session. Our quantitative questionnaire data and qualitative interviews with therapists revealed several important findings. First, after controlling for individual differences between participants, using two cameras had a marginally significant positive effect on physical therapy assessment scores from therapists. Second, the spatial ability of patients was a strong predictor of therapist assessment. And third, the video clarity of remote communication systems mattered. Based on our findings, we offer several suggestions and insights towards the future use of telepresence systems for remote communication.
Multi-label Classification with High-rank and High-order Label Correlations
Venue: arXiv cs.LG 2023
Year: 2023

Exploiting label correlations is important to multi-label classification. Previous methods capture the high-order label correlations mainly by transforming the label matrix to a latent label space with low-rank matrix factorization. However, the label matrix is generally a full-rank or approximate full-rank matrix, making the low-rank factorization inappropriate. Besides, in the latent space, the label correlations will become implicit. To this end, we propose a simple yet effective method to depict the high-order label correlations explicitly, and at the same time maintain the high-rank of the label matrix. Moreover, we estimate the label correlations and infer model parameters simultaneously via the local geometric structure of the input to achieve mutual enhancement. Comparative studies over twelve benchmark data sets validate the effectiveness of the proposed algorithm in multi-label classification. The exploited high-order label correlations are consistent with common sense empirically. Our code is publicly available at https://github.com/Chongjie-Si/HOMI.
Out-of-Distribution Detection in Time-Series Domain: A Novel Seasonal Ratio Scoring Approach
Venue: arXiv cs.LG 2023
Year: 2023

Safe deployment of time-series classifiers for real-world applications relies on the ability to detect the data which is not generated from the same distribution as training data. This task is referred to as out-of-distribution (OOD) detection. We consider the novel problem of OOD detection for the time-series domain. We discuss the unique challenges posed by time-series data and explain why prior methods from the image domain will perform poorly. Motivated by these challenges, this paper proposes a novel {\em Seasonal Ratio Scoring (SRS)} approach. SRS consists of three key algorithmic steps. First, each input is decomposed into class-wise semantic component and remainder. Second, this decomposition is employed to estimate the class-wise conditional likelihoods of the input and remainder using deep generative models. The seasonal ratio score is computed from these estimates. Third, a threshold interval is identified from the in-distribution data to detect OOD examples. Experiments on diverse real-world benchmarks demonstrate that the SRS method is well-suited for time-series OOD detection when compared to baseline methods. Open-source code for SRS method is provided at https://github.com/tahabelkhouja/SRS
FedSS: Federated Learning with Smart Selection of clients
Venue: arXiv cs.DC 2023
Year: 2023

Federated learning provides the ability to learn over heterogeneous user data in a distributed manner while preserving user privacy. However, its current client selection technique is a source of bias as it discriminates against slow clients. For starters, it selects clients that satisfy certain network and system-specific criteria, thus not selecting slow clients. Even when such clients are included in the training process, they either struggle with the training or are dropped altogether for being too slow. Our proposed idea looks to find a sweet spot between fast convergence and heterogeneity by looking at smart client selection and scheduling techniques.
Cluster Resource Management for Dynamic Workloads by Online Optimization
Venue: arXiv cs.PF 2023
Year: 2023

Over the past ten years, many different approaches have been proposed for different aspects of the problem of resources management for long running, dynamic and diverse workloads such as processing query streams or distributed deep learning. Particularly for applications consisting of containerized microservices, researchers have attempted to address problems of dynamic selection of, for example: types and quantities of virtualized services (e.g., IaaS/VMs), vertical and horizontal scaling of different microservices, assigning microservices to VMs, task scheduling, or some combination thereof. In this context, we argue that frameworks like simulated annealing are highly suitable for online navigation of trade-offs between performance (SLO) and cost, particularly when the complex workloads and cloud-service offerings vary over time. Based on a macroscopic objective that combines both performance and cost terms, annealing facilitates light-weight and coherent policies of exploration and exploitation. In this paper, we first give some background on simulated annealing and then experimentally demonstrate its usefulness for different case studies, including service selection for both a single type of workload (e.g., distributed deep learning) and a mixture of workload types (exploring a partially categorical set of options), and container sizing for microservice benchmarks. We conclude with a discussion of how the basic annealing platform can be applied to other resource-management problems, hybridized with other methods, and accommodate user-specified rules of thumb.
SparseTIR: Composable Abstractions for Sparse Compilation in Deep Learning
Venue: arXiv cs.LG 2023
Year: 2023

Sparse tensors are rapidly becoming critical components of modern deep learning workloads. However, developing high-performance sparse operators can be difficult and tedious, and existing vendor libraries cannot satisfy the escalating demands from new operators. Sparse tensor compilers simplify the development of operators, but efficient sparse compilation for deep learning remains challenging because a single sparse format cannot maximize hardware efficiency, and single-shot compilers cannot keep up with latest hardware and system advances. In this paper, we observe that the key to addressing both these challenges is to leverage composable formats and composable transformations. We propose SparseTIR, a sparse tensor compilation abstraction that offers composable formats and composable transformations for deep learning workloads. SparseTIR constructs a search space over these composable components for performance tuning. With these improvements, SparseTIR obtains consistent performance speedups vs vendor libraries on GPUs for single operators: 1.20-2.34x for GNN operators, 1.05-2.98x for sparse attention operators, and 0.56-7.45x for sparse convolution operators. SparseTIR also accelerates end-to-end GNNs by 1.08-1.52x for GraphSAGE training, and 4.20-40.18x for RGCN inference.
Dynamic Budget Throttling in Repeated Second-Price Auctions
Venue: arXiv cs.GT 2023
Year: 2023

In today's online advertising markets, a crucial requirement for an advertiser is to control her total expenditure within a time horizon under some budget. Among various budget control methods, throttling has emerged as a popular choice, managing an advertiser's total expenditure by selecting only a subset of auctions to participate in. This paper provides a theoretical panorama of a single advertiser's dynamic budget throttling process in repeated second-price auctions. We first establish a lower bound on the regret and an upper bound on the asymptotic competitive ratio for any throttling algorithm, respectively, when the advertiser's values are stochastic and adversarial. Regarding the algorithmic side, we propose the OGD-CB algorithm, which guarantees a near-optimal expected regret with stochastic values. On the other hand, when values are adversarial, we prove that this algorithm also reaches the upper bound on the asymptotic competitive ratio. We further compare throttling with pacing, another widely adopted budget control method, in repeated second-price auctions. In the stochastic case, we demonstrate that pacing is generally superior to throttling for the advertiser, supporting the well-known result that pacing is asymptotically optimal in this scenario. However, in the adversarial case, we give an exciting result indicating that throttling is also an asymptotically optimal dynamic bidding strategy. Our results bridge the gaps in theoretical research of throttling in repeated auctions and comprehensively reveal the ability of this popular budget-smoothing strategy.
Embedding Recycling for Language Models
Venue: arXiv cs.CL 2023
Year: 2023

Real-world applications of neural language models often involve running many different models over the same corpus. The high computational cost of these runs has led to interest in techniques that can reuse the contextualized embeddings produced in previous runs to speed training and inference of future ones. We refer to this approach as embedding recycling (ER). While multiple ER techniques have been proposed, their practical effectiveness is still unknown because existing evaluations consider very few models and do not adequately account for overhead costs. We perform an extensive evaluation of ER across eight different models (17 to 900 million parameters) and fourteen tasks in English. We show how a simple ER technique that caches activations from an intermediate layer of a pretrained model, and learns task-specific adapters on the later layers, is broadly effective. For the best-performing baseline in our experiments (DeBERTa-v2 XL), adding a precomputed cache results in a >90% speedup during training and 87-91% speedup for inference, with negligible impact on accuracy. Our analysis reveals important areas of future work.
Machine Learning Security in Industry: A Quantitative Survey
Venue: arXiv cs.LG 2023
Year: 2023

Despite the large body of academic work on machine learning security, little is known about the occurrence of attacks on machine learning systems in the wild. In this paper, we report on a quantitative study with 139 industrial practitioners. We analyze attack occurrence and concern and evaluate statistical hypotheses on factors influencing threat perception and exposure. Our results shed light on real-world attacks on deployed machine learning. On the organizational level, while we find no predictors for threat exposure in our sample, the amount of implement defenses depends on exposure to threats or expected likelihood to become a target. We also provide a detailed analysis of practitioners' replies on the relevance of individual machine learning attacks, unveiling complex concerns like unreliable decision making, business information leakage, and bias introduction into models. Finally, we find that on the individual level, prior knowledge about machine learning security influences threat perception. Our work paves the way for more research about adversarial machine learning in practice, but yields also insights for regulation and auditing.
Scaling Novel Object Detection with Weakly Supervised Detection Transformers
Venue: arXiv cs.CV 2023
Year: 2023

A critical object detection task is finetuning an existing model to detect novel objects, but the standard workflow requires bounding box annotations which are time-consuming and expensive to collect. Weakly supervised object detection (WSOD) offers an appealing alternative, where object detectors can be trained using image-level labels. However, the practical application of current WSOD models is limited, as they only operate at small data scales and require multiple rounds of training and refinement. To address this, we propose the Weakly Supervised Detection Transformer, which enables efficient knowledge transfer from a large-scale pretraining dataset to WSOD finetuning on hundreds of novel objects. Additionally, we leverage pretrained knowledge to improve the multiple instance learning (MIL) framework often used in WSOD methods. Our experiments show that our approach outperforms previous state-of-the-art models on large-scale novel object detection datasets, and our scaling study reveals that class quantity is more important than image quantity for WSOD pretraining. The code is available at https://github.com/tmlabonte/weakly-supervised-DETR.
The expected sum of edge lengths in planar linearizations of trees. Theory and applications
Venue: arXiv cs.CL 2023
Year: 2023

Dependency trees have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these structures, vertices are words and edges connect syntactically-dependent words. The tendency of these dependencies to be short has been demonstrated using random baselines for the sum of the lengths of the edges or its variants. A ubiquitous baseline is the expected sum in projective orderings (wherein edges do not cross and the root word of the sentence is not covered by any edge), that can be computed in time $O(n)$. Here we focus on a weaker formal constraint, namely planarity. In the theoretical domain, we present a characterization of planarity that, given a sentence, yields either the number of planar permutations or an efficient algorithm to generate uniformly random planar permutations of the words. We also show the relationship between the expected sum in planar arrangements and the expected sum in projective arrangements. In the domain of applications, we derive a $O(n)$-time algorithm to calculate the expected value of the sum of edge lengths. We also apply this research to a parallel corpus and find that the gap between actual dependency distance and the random baseline reduces as the strength of the formal constraint on dependency structures increases, suggesting that formal constraints absorb part of the dependency distance minimization effect. Our research paves the way for replicating past research on dependency distance minimization using random planar linearizations as random baseline.