OpenRaiser/Intern-Atlas huggingface dataset:
ByteComp: Revisiting Gradient Compression in Distributed Training
Venue: arXiv cs.LG 2022
Year: 2022

Gradient compression (GC) is a promising approach to addressing the communication bottleneck in distributed deep learning (DDL). However, it is challenging to find the optimal compression strategy for applying GC to DDL because of the intricate interactions among tensors. To fully unleash the benefits of GC, two questions must be addressed: 1) How to express all compression strategies and the corresponding interactions among tensors of any DDL training job? 2) How to quickly select a near-optimal compression strategy? In this paper, we propose ByteComp to answer these questions. It first designs a decision tree abstraction to express all the compression strategies and develops empirical models to timeline tensor computation, communication, and compression to enable ByteComp to derive the intricate interactions among tensors. It then designs a compression decision algorithm that analyzes tensor interactions to eliminate and prioritize strategies and optimally offloads compression to CPUs. Experimental evaluations show that ByteComp can improve the training throughput over the start-of-the-art compression-enabled system by up to 77% for representative DDL training jobs. Moreover, the computational time needed to select the compression strategy is measured in milliseconds, and the selected strategy is only a few percent from optimal.
Overcoming Congestion in Distributed Coloring
Venue: arXiv cs.DC 2022
Year: 2022

We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm for $(\operatorname{degree}+1)$-list-coloring (D1LC), this allows us to solve D1LC in $O(\log^5 \log n)$ CONGEST rounds, and in only $O(\log^* n)$ rounds when the graph has minimum degree $Ω(\log^7 n)$, w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in $O(1)$ CONGEST rounds, w.h.p.
Core-set Selection Using Metrics-based Explanations (CSUME) for multiclass ECG
Venue: arXiv cs.LG 2022
Year: 2022

The adoption of deep learning-based healthcare decision support systems such as the detection of irregular cardiac rhythm is hindered by challenges such as lack of access to quality data and the high costs associated with the collection and annotation of data. The collection and processing of large volumes of healthcare data is a continuous process. The performance of data-hungry Deep Learning models (DL) is highly dependent on the quantity and quality of the data. While the need for data quantity has been established through research adequately, we show how a selection of good quality data improves deep learning model performance. In this work, we take Electrocardiogram (ECG) data as a case study and propose a model performance improvement methodology for algorithm developers, that selects the most informative data samples from incoming streams of multi-class ECG data. Our Core-Set selection methodology uses metrics-based explanations to select the most informative ECG data samples. This also provides an understanding (for algorithm developers) as to why a sample was selected as more informative over others for the improvement of deep learning model performance. Our experimental results show a 9.67% and 8.69% precision and recall improvement with a significant training data volume reduction of 50%. Additionally, our proposed methodology asserts the quality and annotation of ECG samples from incoming data streams. It allows automatic detection of individual data samples that do not contribute to model learning thus minimizing possible negative effects on model performance. We further discuss the potential generalizability of our approach by experimenting with a different dataset and deep learning architecture.
Asymmetric Local Information Privacy and the Watchdog Mechanism
Venue: arXiv cs.IT 2022
Year: 2022

This paper proposes a novel watchdog privatization scheme by generalizing local information privacy (LIP) to enhance data utility. To protect the sensitive features $S$ correlated with some useful data $X$, LIP restricts the lift, the ratio of the posterior belief to the prior on $S$ after and before accessing $X$. For each $x$, both maximum and minimum lift over sensitive features are measures of the privacy risk of publishing this symbol and should be restricted for the privacy-preserving purpose. Previous works enforce the same bound for both max-lift and min-lift. However, empirical observations show that the min-lift is usually much smaller than the max-lift. In this work, we generalize the LIP definition to consider the unequal values of max and min lift, i.e., considering different bounds for max-lift and min-lift. This new definition is applied to the watchdog privacy mechanism. We demonstrate that the utility is enhanced under a given privacy constraint on local differential privacy. At the same time, the resulting max-lift is lower and, therefore, tightly restricts other privacy leakages, e.g., mutual information, maximal leakage, and $α$-leakage.
Machine Learning for Microcontroller-Class Hardware: A Review
Venue: arXiv cs.LG 2022
Year: 2022

The advancements in machine learning opened a new opportunity to bring intelligence to the low-end Internet-of-Things nodes such as microcontrollers. Conventional machine learning deployment has high memory and compute footprint hindering their direct deployment on ultra resource-constrained microcontrollers. This paper highlights the unique requirements of enabling onboard machine learning for microcontroller class devices. Researchers use a specialized model development workflow for resource-limited applications to ensure the compute and latency budget is within the device limits while still maintaining the desired performance. We characterize a closed-loop widely applicable workflow of machine learning model development for microcontroller class devices and show that several classes of applications adopt a specific instance of it. We present both qualitative and numerical insights into different stages of model development by showcasing several use cases. Finally, we identify the open research challenges and unsolved questions demanding careful considerations moving forward.
ComplexGen: CAD Reconstruction by B-Rep Chain Complex Generation
Venue: arXiv cs.CV 2022
Year: 2022

We view the reconstruction of CAD models in the boundary representation (B-Rep) as the detection of geometric primitives of different orders, i.e. vertices, edges and surface patches, and the correspondence of primitives, which are holistically modeled as a chain complex, and show that by modeling such comprehensive structures more complete and regularized reconstructions can be achieved. We solve the complex generation problem in two steps. First, we propose a novel neural framework that consists of a sparse CNN encoder for input point cloud processing and a tri-path transformer decoder for generating geometric primitives and their mutual relationships with estimated probabilities. Second, given the probabilistic structure predicted by the neural network, we recover a definite B-Rep chain complex by solving a global optimization maximizing the likelihood under structural validness constraints and applying geometric refinements. Extensive tests on large scale CAD datasets demonstrate that the modeling of B-Rep chain complex structure enables more accurate detection for learning and more constrained reconstruction for optimization, leading to structurally more faithful and complete CAD B-Rep models than previous results.
Forensic Artefact Discovery and Attribution from Android Cryptocurrency Wallet Applications
Venue: arXiv cs.CR 2022
Year: 2022

Cryptocurrency has been (ab)used to purchase illicit goods and services such as drugs, weapons and child pornography (also referred to as child sexual abuse materials), and thus mobile devices (where cryptocurrency wallet applications are installed) are a potential source of evidence in a criminal investigation. Not surprisingly, there has been increased focus on the security of cryptocurrency wallets, although forensic extraction and attribution of forensic artefacts from such wallets is understudied. In this paper, we examine Bitcoin and Dogecoin. The latter is increasingly popular partly due to endorsements from celebrities and being positioned as an introductory path to cryptocurrency for newcomers. Specifically, we demonstrate how one can acquire forensic artefacts from Android Bitcoin and Dogecoin cryptocurrency wallets, such as wallet IDs, transaction IDs, timestamp information, email addresses, cookies, and OAuth tokens.
LV-Linker: Supporting Linked Exploration of Phone Usage Log Data and Screen Video Data
Venue: arXiv cs.HC 2022
Year: 2022

Prior HCI studies often analyzed smartphone app usage data for usability and user experience research purposes. App usage videos are often collected by a screen recording app in order to better analyze the app usage behaviors (e.g., app usage time, screen transition, and notification handling). However, it is difficult to analyze app usage videos along with multiple user interaction stream data. When the length of a video is long, data analysis tends to take a long time due to the volume of user interaction data. This is even more difficult for novice researchers due to a lack of data analysis experience. In this paper, we propose LV-Linker (Log and Video Linker), a visualization tool that helps researchers quickly explore the app usage log and video data by linking multiple time series log data with the video data. We conducted a preliminary user study with eight participants to evaluate the benefits of linking, by measuring task completion time, helpfulness, and subjective task workload. Our results showed that offering a linking feature significantly lowers the task completion time and task workload.
Structured references from PDF articles: assessing the tools for bibliographic reference extraction and parsing
Venue: arXiv cs.DL 2022
Year: 2022

Many solutions have been provided to extract bibliographic references from PDF papers. Machine learning, rule-based and regular expressions approaches were among the most used methods adopted in tools for addressing this task. This work aims to identify and evaluate all and only the tools which, given a full-text paper in PDF format, can recognise, extract and parse bibliographic references. We identified seven tools: Anystyle, Cermine, ExCite, Grobid, Pdfssa4met, Scholarcy and Science Parse. We compared and evaluated them against a corpus of 56 PDF articles published in 27 subject areas. Indeed, Anystyle obtained the best overall score, followed by Cermine. However, in some subject areas, other tools had better results for specific tasks.
Generalization bounds and algorithms for estimating conditional average treatment effect of dosage
Venue: arXiv cs.LG 2022
Year: 2022

We investigate the task of estimating the conditional average causal effect of treatment-dosage pairs from a combination of observational data and assumptions on the causal relationships in the underlying system. This has been a longstanding challenge for fields of study such as epidemiology or economics that require a treatment-dosage pair to make decisions but may not be able to run randomized trials to precisely quantify their effect and heterogeneity across individuals. In this paper, we extend (Shalit et al, 2017) to give new bounds on the counterfactual generalization error in the context of a continuous dosage parameter which relies on a different approach to defining counterfactuals and assignment bias adjustment. This result then guides the definition of new learning objectives that can be used to train representation learning algorithms for which we show empirically new state-of-the-art performance results across several benchmark datasets for this problem, including in comparison to doubly-robust estimation methods.
Generalized Stochastic Matching
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we generalize the recently studied Stochastic Matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the Stochastic Matching problem that has been studied was as follows: given a graph G = (V, E), each edge is included in the realized sub-graph of G mutually independently with probability p_e, and the goal is to find a degree-bounded sub-graph Q of G that has an expected maximum matching that approximates the expected maximum matching of the realized sub-graph. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of Stochastic Matching in which vertices and edges are both realized independently with some probabilities p_v, p_e, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the Stochastic Matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least $0.6568$ in unweighted graphs, and $1/2 + ε$ in weighted graphs for some constant $ε> 0$. We further improve our result for unweighted graphs to $2/3$ using edge degree constrained subgraphs (EDCS).
A note on hardness of promise hypergraph colouring
Venue: arXiv cs.DM 2022
Year: 2022

We show a slightly simpler proof the following theorem by I. Dinur, O. Regev, and C. Smyth: for all $c \geq 2$, it is NP-hard to find a $c$-colouring of a 2-coloruable 3-uniform hypergraph. We recast this result in the algebraic framework for Promise CSPs, using only a weaker version of the PCP theorem.
What are People Talking about in #BlackLivesMatter and #StopAsianHate? Exploring and Categorizing Twitter Topics Emerging in Online Social Movements through the Latent Dirichlet Allocation Model
Venue: arXiv cs.IR 2022
Year: 2022

Minority groups have been using social media to organize social movements that create profound social impacts. Black Lives Matter (BLM) and Stop Asian Hate (SAH) are two successful social movements that have spread on Twitter that promote protests and activities against racism and increase the public's awareness of other social challenges that minority groups face. However, previous studies have mostly conducted qualitative analyses of tweets or interviews with users, which may not comprehensively and validly represent all tweets. Very few studies have explored the Twitter topics within BLM and SAH dialogs in a rigorous, quantified and data-centered approach. Therefore, in this research, we adopted a mixed-methods approach to comprehensively analyze BLM and SAH Twitter topics. We implemented (1) the latent Dirichlet allocation model to understand the top high-level words and topics and (2) open-coding analysis to identify specific themes across the tweets. We collected more than one million tweets with the #blacklivesmatter and #stopasianhate hashtags and compared their topics. Our findings revealed that the tweets discussed a variety of influential topics in depth, and social justice, social movements, and emotional sentiments were common topics in both movements, though with unique subtopics for each movement. Our study contributes to the topic analysis of social movements on social media platforms in particular and the literature on the interplay of AI, ethics, and society in general.
Investigating Participation Mechanisms in EU Code Week
Venue: arXiv cs.CY 2022
Year: 2022

Digital competence (DC) is a broad set of skills, attitudes, and knowledge for confident, critical and responsible use of digital technologies in every aspect of life. DC is fundamental to all people in conducting a productive and fulfilling life in an increasingly digital world. However, prejudices, misconceptions, and lack of awareness reduce the diffusion of DC, hindering digital transformation and preventing countries and people from realising their full potential. Teaching Informatics in the curriculum is increasingly supported by the institutions but faces serious challenges, such as teacher upskilling and support, and will require several years to observe sizeable outcomes. In response, grassroots movements promoting computing literacy in an informal setting have grown, including EU Code Week, whose vision is to develop computing skills while promoting diversity and raising awareness of the importance of digital skills. Code Week participation is a form of public engagement that could be affected by socio-economic and demographic factors, as any other form of participation. The aim of the manuscript is twofold: first, to offer a detailed and comprehensive statistical description of Code Week's participation in the EU Member States in terms of penetration, retention, demographic composition, and spatial distribution in order to inform more effective awareness-raising campaigns; second, to investigate the impact of socio-economic factors on Code Week involvement. The study identifies a strong negative correlation between participation and income at different geographical scales. It also suggests underlying mechanisms driving participation that are coherent with the "psychosocial" and the "resource" views, i.e. the two most widely accepted explanations of the effect of income on public engagement.
Radial Spike and Slab Bayesian Neural Networks for Sparse Data in Ransomware Attacks
Venue: arXiv cs.CR 2022
Year: 2022

Ransomware attacks are increasing at an alarming rate, leading to large financial losses, unrecoverable encrypted data, data leakage, and privacy concerns. The prompt detection of ransomware attacks is required to minimize further damage, particularly during the encryption stage. However, the frequency and structure of the observed ransomware attack data makes this task difficult to accomplish in practice. The data corresponding to ransomware attacks represents temporal, high-dimensional sparse signals, with limited records and very imbalanced classes. While traditional deep learning models have been able to achieve state-of-the-art results in a wide variety of domains, Bayesian Neural Networks, which are a class of probabilistic models, are better suited to the issues of the ransomware data. These models combine ideas from Bayesian statistics with the rich expressive power of neural networks. In this paper, we propose the Radial Spike and Slab Bayesian Neural Network, which is a new type of Bayesian Neural network that includes a new form of the approximate posterior distribution. The model scales well to large architectures and recovers the sparse structure of target functions. We provide a theoretical justification for using this type of distribution, as well as a computationally efficient method to perform variational inference. We demonstrate the performance of our model on a real dataset of ransomware attacks and show improvement over a large number of baselines, including state-of-the-art models such as Neural ODEs (ordinary differential equations). In addition, we propose to represent low-level events as MITRE ATT\&CK tactics, techniques, and procedures (TTPs) which allows the model to better generalize to unseen ransomware attacks.
Scalable almost-linear dynamical Ising machines
Venue: arXiv cs.ET 2022
Year: 2022

The past decade has seen the emergence of Ising machines targeting hard combinatorial optimization problems by minimizing the Ising Hamiltonian with spins represented by continuous dynamical variables. However, capabilities of these machines at larger scales are yet to be fully explored. We investigate an Ising machine based on a network of almost-linearly coupled analog spins. We show that such networks leverage the computational resource similar to that of the semidefinite positive relaxation of the Ising model. We estimate the expected performance of the almost-linear machine and benchmark it on a set of {0,1}-weighted graphs. We show that the running time of the investigated machine scales polynomially (linearly with the number of edges in the connectivity graph). As an example of the physical realization of the machine, we present a CMOS-compatible implementation comprising an array of vertices efficiently storing the continuous spins on charged capacitors and communicating externally via analog current.
Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
Venue: arXiv cs.DC 2022
Year: 2022

We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutions in low-treewidth graphs. By ``efficient'' we mean that the running time has polynomial dependence on the treewidth, a linear dependence on the diameter (which is unavoidable), and only a polylogarithmic dependence on $n$, the number of nodes in the graph. We present the algorithms solving the following problems in the CONGEST model which all attain $\tilde{O(τ^{O(1)}D)}$-round complexity (where $τ$ and $D$ denote the treewidth and diameter of the graph, respectively): (1) Exact single-source shortest paths (actually, the more general problem of computing a distance labeling scheme) for weighted and directed graphs, (2) exact bipartite unweighted maximum matching, and (3) the weighted girth for both directed and undirected graphs. We derive all of our results using a single unified framework, which consists of two novel technical ingredients, The first is a fully polynomial-time distributed tree decomposition algorithm, which outputs a decomposition of width $O(τ^2\log n)$ in $\tilde{O}(τ^{O(1)}D)$ rounds (where $n$ is the number of nodes in the graph). The second ingredient, and the technical highlight of this paper, is the novel concept of a \emph{stateful walk constraint}, which naturally defines a set of feasible walks in the input graph based on their local properties (e.g., augmenting paths). Given a stateful walk constraint, the constrained version of the shortest paths problem (or distance labeling) requires the algorithm to output the shortest \emph{constrained} walk (or its distance) for a given source and sink vertices. We show that this problem can be efficiently solved in the CONGEST model by reducing it to an \emph{unconstrained} version of the problem.
Gathering despite a linear number of weakly Byzantine agents
Venue: arXiv cs.DC 2022
Year: 2022

We study the gathering problem to make multiple agents initially scattered in arbitrary networks gather at a single node. There exist $k$ agents with unique identifiers (IDs) in the network, and $f$ of them are weakly Byzantine agents, which behave arbitrarily except for falsifying their IDs. The agents behave in synchronous rounds, and each node does not have any memory like a whiteboard. In the literature, there exists a gathering algorithm that tolerates any number of Byzantine agents, while the fastest gathering algorithm requires $Ω(f^2)$ non-Byzantine agents. This paper proposes an algorithm that solves the gathering problem efficiently with $Ω(f)$ non-Byzantine agents since there is a large gap between the number of non-Byzantine agents in previous works. The proposed algorithm achieves the gathering in $O(f\cdot|Λ_{good}|\cdot X(N))$ rounds in case of $9f+8\leq k$ and simultaneous startup if $N$ is given to agents, where $|Λ_{good}|$ is the length of the largest ID among non-Byzantine agents, and $X(n)$ is the number of rounds required to explore any network composed of $n$ nodes. This algorithm is faster than the most fault-tolerant existing algorithm and requires fewer non-Byzantine agents than the fastest algorithm if $n$ is given to agents, although the guarantees on simultaneous termination and startup delay are not the same. To achieve this property, we propose a new technique to simulate a Byzantine consensus algorithm for synchronous message-passing systems on agent systems.