OpenRaiser/Intern-Atlas huggingface dataset:
LSQT: Low-Stretch Quasi-Trees for Bundling and Layout
Venue: arXiv cs.HC 2020
Year: 2020

We introduce low-stretch trees to the visualization community with LSQT, our novel technique that uses quasi-trees for both layout and edge bundling. Our method offers strong computational speed and complexity guarantees by leveraging the convenient properties of low-stretch trees, which accurately reflect the topological structure of arbitrary graphs with superior fidelity compared to arbitrary spanning trees. Low-stretch quasi-trees also have provable sparseness guarantees, providing algorithmic support for aggressive de-cluttering of hairball graphs. LSQT does not rely on previously computed vertex positions and computes bundles based on topological structure before any geometric layout occurs. Edge bundles are computed efficiently and stored in an explicit data structure that supports sophisticated visual encoding and interaction techniques, including dynamic layout adjustment and interactive bundle querying. Our unoptimized implementation handles graphs of over 100,000 edges in eight seconds, providing substantially higher performance than previous approaches.
Optimal Bounds on the Price of Fairness for Indivisible Goods
Venue: arXiv cs.GT 2020
Year: 2020

In the allocation of resources to a set of agents, how do fairness guarantees impact the social welfare? A quantitative measure of this impact is the price of fairness, which measures the worst-case loss of social welfare due to fairness constraints. While initially studied for divisible goods, recent work on the price of fairness also studies the setting of indivisible goods. In this paper, we resolve the price of two well-studied fairness notions for the allocation of indivisible goods: envy-freeness up to one good (EF1), and approximate maximin share (MMS). For both EF1 and 1/2-MMS guarantees, we show, via different techniques, that the price of fairness is $O(\sqrt{n})$, where $n$ is the number of agents. From previous work, it follows that our bounds are tight. Our bounds are obtained via efficient algorithms. For 1/2-MMS, our bound holds for additive valuations, whereas for EF1, our bound holds for the more general class of subadditive valuations. This resolves an open problem posed by Bei et al. (2019).
Screen Tracking for Clinical Translation of Live Ultrasound Image Analysis Methods
Venue: arXiv cs.CV 2020
Year: 2020

Ultrasound (US) imaging is one of the most commonly used non-invasive imaging techniques. However, US image acquisition requires simultaneous guidance of the transducer and interpretation of images, which is a highly challenging task that requires years of training. Despite many recent developments in intra-examination US image analysis, the results are not easy to translate to a clinical setting. We propose a generic framework to extract the US images and superimpose the results of an analysis task, without any need for physical connection or alteration to the US system. The proposed method captures the US image by tracking the screen with a camera fixed at the sonographer's view point and reformats the captured image to the right aspect ratio, in 87.66 +- 3.73ms on average. It is hypothesized that this would enable to input such retrieved image into an image processing pipeline to extract information that can help improve the examination. This information could eventually be projected back to the sonographer's field of view in real time using, for example, an augmented reality (AR) headset.
Robotized Ultrasound Imaging of the Peripheral Arteries -- a Phantom Study
Venue: arXiv cs.RO 2020
Year: 2020

The first choice in diagnostic imaging for patients suffering from peripheral arterial disease is 2D ultrasound (US). However, for a proper imaging process, a skilled and experienced sonographer is required. Additionally, it is a highly user-dependent operation. A robotized US system that autonomously scans the peripheral arteries has the potential to overcome these limitations. In this work, we extend a previously proposed system by a hierarchical image analysis pipeline based on convolutional neural networks in order to control the robot. The system was evaluated by checking its feasibility to keep the vessel lumen of a leg phantom within the US image while scanning along the artery. In 100 % of the images acquired during the scan process the whole vessel lumen was visible. While defining an insensitivity margin of 2.74 mm, the mean absolute distance between vessel center and the horizontal image center line was 2.47 mm and 3.90 mm for an easy and complex scenario, respectively. In conclusion, this system presents the basis for fully automatized peripheral artery imaging in humans using a radiation-free approach.
Generating Functions for Probabilistic Programs
Venue: arXiv cs.LO 2020
Year: 2020

This paper investigates the usage of generating functions (GFs) encoding measures over the program variables for reasoning about discrete probabilistic programs. To that end, we define a denotational GF-transformer semantics for probabilistic while-programs, and show that it instantiates Kozen's seminal distribution transformer semantics. We then study the effective usage of GFs for program analysis. We show that finitely expressible GFs enable checking super-invariants by means of computer algebra tools, and that they can be used to determine termination probabilities. The paper concludes by characterizing a class of -- possibly infinite-state -- programs whose semantics is a rational GF encoding a discrete phase-type distribution.
Perfectly Sampling $k\geq (8/3 +o(1))Δ$-Colorings in Graphs
Venue: arXiv cs.DS 2020
Year: 2020

We present a randomized algorithm which takes as input an undirected graph $G$ on $n$ vertices with maximum degree $Δ$, and a number of colors $k \geq (8/3 + o_Δ(1))Δ$, and returns -- in expected time $\tilde{O}(nΔ^{2}\log{k})$ -- a proper $k$-coloring of $G$ distributed perfectly uniformly on the set of all proper $k$-colorings of $G$. Notably, our sampler breaks the barrier at $k = 3Δ$ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also sketch how to modify our methods to relax the restriction on $k$ to $k \geq (8/3 - ε_0)Δ$ for an absolute constant $ε_0 > 0$. As in the work of Bhandari and Chakraborty, and the pioneering work of Huber [STOC 1998], our sampler is based on Coupling from the Past [Propp&Wilson, Random Struct. Algorithms, 1995] and the bounding chain method [Huber, STOC 1998; Häggström&Nelander, Scand. J. Statist., 1999]. Our innovations include a novel bounding chain routine inspired by Jerrum's analysis of the Glauber dynamics [Random Struct. Algorithms, 1995], as well as a preconditioning routine for bounding chains which uses the algorithmic Lovász Local Lemma [Moser&Tardos, J.ACM, 2010].
DeepHAZMAT: Hazardous Materials Sign Detection and Segmentation with Restricted Computational Resources
Venue: arXiv cs.CV 2020
Year: 2020

One of the most challenging and non-trivial tasks in robot-based rescue operations is the Hazardous Materials or HAZMATs sign detection in the operation field, to prevent further unexpected disasters. Each Hazmat sign has a specific meaning that the rescue robot should detect and interpret it to take a safe action, accordingly. Accurate Hazmat detection and real-time processing are the two most important factors in such robotics applications. Furthermore, we also have to cope with some secondary challenges such as image distortion and restricted CPU and computational resources which are embedded in a rescue robot. In this paper, we propose a CNN-Based pipeline called DeepHAZMAT for detecting and segmenting Hazmats in four steps; 1) optimising the number of input images that are fed into the CNN network, 2) using the YOLOv3-tiny structure to collect the required visual information from the hazardous areas, 3) Hazmat sign segmentation and separation from the background using GrabCut technique, and 4) post-processing the result with morphological operators and convex hull algorithm. In spite of the utilisation of a very limited memory and CPU resources, the experimental results show the proposed method has successfully maintained a better performance in terms of detection-speed and detection-accuracy, compared with the state-of-the-art methods.
Targeted Intervention in Random Graphs
Venue: arXiv cs.SI 2020
Year: 2020

We consider a setting where individuals interact in a network, each choosing actions which optimize utility as a function of neighbors' actions. A central authority aiming to maximize social welfare at equilibrium can intervene by paying some cost to shift individual incentives, and the optimal intervention can be computed using the spectral decomposition of the graph, yet this is infeasible in practice if the adjacency matrix is unknown. In this paper, we study the question of designing intervention strategies for graphs where the adjacency matrix is unknown and is drawn from some distribution. For several commonly studied random graph models, we show that there is a single intervention, proportional to the first eigenvector of the expected adjacency matrix, which is near-optimal for almost all generated graphs when the budget is sufficiently large. We also provide several efficient sampling-based approaches for approximately recovering the first eigenvector when we do not know the distribution. On the whole, our analysis compares three categories of interventions: those which use no data about the network, those which use some data (such as distributional knowledge or queries to the graph), and those which are fully optimal. We evaluate these intervention strategies on synthetic and real-world network data, and our results suggest that analysis of random graph models can be useful for determining when certain heuristics may perform well in practice.
SoK: The Faults in our ASRs: An Overview of Attacks against Automatic Speech Recognition and Speaker Identification Systems
Venue: arXiv cs.CR 2020
Year: 2020

Speech and speaker recognition systems are employed in a variety of applications, from personal assistants to telephony surveillance and biometric authentication. The wide deployment of these systems has been made possible by the improved accuracy in neural networks. Like other systems based on neural networks, recent research has demonstrated that speech and speaker recognition systems are vulnerable to attacks using manipulated inputs. However, as we demonstrate in this paper, the end-to-end architecture of speech and speaker systems and the nature of their inputs make attacks and defenses against them substantially different than those in the image space. We demonstrate this first by systematizing existing research in this space and providing a taxonomy through which the community can evaluate future work. We then demonstrate experimentally that attacks against these models almost universally fail to transfer. In so doing, we argue that substantial additional work is required to provide adequate mitigations in this space.
Robin: A Web Security Tool
Venue: arXiv cs.CR 2020
Year: 2020

Thanks to the advance of technology, all kinds of applications are becoming more complete and capable of performing complex tasks that save much of our time. But to perform these tasks, applications require that some personal information are shared, for example credit card, bank accounts, email addresses, etc. All these data must be transferred securely between the final user and the institution application. Nonetheless, several applications might contain residual flaws that may be explored by criminals in order to steal users data. Hence, to help information security professionals and developers to perform penetration tests (pentests) on web applications, this paper presents Robin: A Web Security Tool. The tool is also applied to a real case study in which a very dangerous vulnerability was found. This vulnerability is also described in this paper.
Orthogonal Sparse Superposition Codes for Ultra-Reliable Low-Latency Communications
Venue: arXiv cs.IT 2020
Year: 2020

This paper presents a new class of sparse superposition codes for low-rates and short-packet communications over the additive white Gaussian noise channel. The new code is orthogonal sparse superposition (OSS) code. A codeword of OSS codes is represented as a superposition of sparse sub-codewords whose support sets are mutually non-overlapping. To construct such codewords in a computationally efficient manner, a successive encoding method is presented. Harnessing the orthogonal property among sub-codewords, a simple yet near-optimal decoding method is proposed, which performs element-wise maximum a posterior decoding with successive support set cancellation. This decoder is super-fast by a linear decoding complexity in block lengths, far less than the commercially used channel decoders for modern channel codes. The upper bounds for the block error rates (BLERs) are analytically derived for few-layered OSS codes as a function of block lengths and code rates. It turns out that a single-layered OSS code achieves the ultimate Shannon limit in the power-limited regime, even with the linear complexity decoder. Via simulations, the proposed OSS codes are shown to perform better than commercially used coded modulation techniques for low-rate and short-latency communication scenarios.
Recommender Systems for the Internet of Things: A Survey
Venue: arXiv cs.IR 2020
Year: 2020

Recommendation represents a vital stage in developing and promoting the benefits of the Internet of Things (IoT). Traditional recommender systems fail to exploit ever-growing, dynamic, and heterogeneous IoT data. This paper presents a comprehensive review of the state-of-the-art recommender systems, as well as related techniques and application in the vibrant field of IoT. We discuss several limitations of applying recommendation systems to IoT and propose a reference framework for comparing existing studies to guide future research and practices.
Vehicle Trajectory Prediction by Transfer Learning of Semi-Supervised Models
Venue: arXiv cs.CV 2020
Year: 2020

In this work we show that semi-supervised models for vehicle trajectory prediction significantly improve performance over supervised models on state-of-the-art real-world benchmarks. Moving from supervised to semi-supervised models allows scaling-up by using unlabeled data, increasing the number of images in pre-training from Millions to a Billion. We perform ablation studies comparing transfer learning of semi-supervised and supervised models while keeping all other factors equal. Within semi-supervised models we compare contrastive learning with teacher-student methods as well as networks predicting a small number of trajectories with networks predicting probabilities over a large trajectory set. Our results using both low-level and mid-level representations of the driving environment demonstrate the applicability of semi-supervised methods for real-world vehicle trajectory prediction.
2D Qubit Placement of Quantum Circuits using LONGPATH
Venue: arXiv cs.ET 2020
Year: 2020

In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.
DeepMSRF: A novel Deep Multimodal Speaker Recognition framework with Feature selection
Venue: arXiv cs.CV 2020
Year: 2020

For recognizing speakers in video streams, significant research studies have been made to obtain a rich machine learning model by extracting high-level speaker's features such as facial expression, emotion, and gender. However, generating such a model is not feasible by using only single modality feature extractors that exploit either audio signals or image frames, extracted from video streams. In this paper, we address this problem from a different perspective and propose an unprecedented multimodality data fusion framework called DeepMSRF, Deep Multimodal Speaker Recognition with Feature selection. We execute DeepMSRF by feeding features of the two modalities, namely speakers' audios and face images. DeepMSRF uses a two-stream VGGNET to train on both modalities to reach a comprehensive model capable of accurately recognizing the speaker's identity. We apply DeepMSRF on a subset of VoxCeleb2 dataset with its metadata merged with VGGFace2 dataset. The goal of DeepMSRF is to identify the gender of the speaker first, and further to recognize his or her name for any given video stream. The experimental results illustrate that DeepMSRF outperforms single modality speaker recognition methods with at least 3 percent accuracy.
Network Flow Methods for the Minimum Covariates Imbalance Problem
Venue: arXiv cs.DS 2020
Year: 2020

The problem of balancing covariates arises in observational studies where one is given a group of control samples and another group, disjoint from the control group, of treatment samples. Each sample, in either group, has several observed nominal covariates. The values, or categories, of each covariate partition the treatment and control samples to a number of subsets referred to as \textit{levels} where the samples at every level share the same covariate value. We address here a problem of selecting a subset of the control group so as to balance, to the best extent possible, the sizes of the levels between the treatment group and the selected subset of control group, the min-imbalance problem. It is proved here that the min-imbalance problem, on two covariates, is solved efficiently with network flow techniques. We present an integer programming formulation of the problem where the constraint matrix is totally unimodular, implying that the linear programming relaxation to the problem has all basic solutions, and in particular the optimal solution, integral. This integer programming formulation is linked to a minimum cost network flow problem which is solvable in $O(n\cdot (n' + n\log n))$ steps, for $n$ the size of the treatment group and $n'$ the size of the control group. A more efficient algorithm is further devised based on an alternative, maximum flow, formulation of the two-covariate min-imbalance problem, that runs in $O(n'^{3/2}\log^2n)$ steps.
Additively Homomorphical Encryption based Deep Neural Network for Asymmetrically Collaborative Machine Learning
Venue: arXiv cs.LG 2020
Year: 2020

The financial sector presents many opportunities to apply various machine learning techniques. Centralized machine learning creates a constraint which limits further applications in finance sectors. Data privacy is a fundamental challenge for a variety of finance and insurance applications that account on learning a model across different sections. In this paper, we define a new practical scheme of collaborative machine learning that one party owns data, but another party owns labels only, and term this \textbf{Asymmetrically Collaborative Machine Learning}. For this scheme, we propose a novel privacy-preserving architecture where two parties can collaboratively train a deep learning model efficiently while preserving the privacy of each party's data. More specifically, we decompose the forward propagation and backpropagation of the neural network into four different steps and propose a novel protocol to handle information leakage in these steps. Our extensive experiments on different datasets demonstrate not only stable training without accuracy loss, but also more than 100 times speedup compared with the state-of-the-art system.
Speculative Leakage in ARM Cortex-A53
Venue: arXiv cs.CR 2020
Year: 2020

The recent Spectre attacks have demonstrated that modern microarchitectural optimizations can make software insecure. These attacks use features like pipelining, out-of-order and speculation to extract information about the memory contents of a process via side-channels. In this paper we demonstrate that Cortex-A53 is affected by speculative leakage even if the microarchitecture does not support out-of-order execution. We named this new class of vulnerabilities SiSCloak.
Attentive Graph Neural Networks for Few-Shot Learning
Venue: arXiv cs.LG 2020
Year: 2020

Graph Neural Networks (GNN) has demonstrated the superior performance in many challenging applications, including the few-shot learning tasks. Despite its powerful capacity to learn and generalize the model from few samples, GNN usually suffers from severe over-fitting and over-smoothing as the model becomes deep, which limit the scalability. In this work, we propose a novel Attentive GNN to tackle these challenges, by incorporating a triple-attention mechanism, i.e. node self-attention, neighborhood attention, and layer memory attention. We explain why the proposed attentive modules can improve GNN for few-shot learning with theoretical analysis and illustrations. Extensive experiments show that the proposed Attentive GNN model achieves the promising results, comparing to the state-of-the-art GNN- and CNN-based methods for few-shot learning tasks, over the mini-ImageNet and tiered-ImageNet benchmarks, under ConvNet-4 and ResNet-based backbone with both inductive and transductive settings. The codes will be made publicly available.
Visual Tracking by TridentAlign and Context Embedding
Venue: arXiv cs.CV 2020
Year: 2020

Recent advances in Siamese network-based visual tracking methods have enabled high performance on numerous tracking benchmarks. However, extensive scale variations of the target object and distractor objects with similar categories have consistently posed challenges in visual tracking. To address these persisting issues, we propose novel TridentAlign and context embedding modules for Siamese network-based visual tracking methods. The TridentAlign module facilitates adaptability to extensive scale variations and large deformations of the target, where it pools the feature representation of the target object into multiple spatial dimensions to form a feature pyramid, which is then utilized in the region proposal stage. Meanwhile, context embedding module aims to discriminate the target from distractor objects by accounting for the global context information among objects. The context embedding module extracts and embeds the global context information of a given frame into a local feature representation such that the information can be utilized in the final classification stage. Experimental results obtained on multiple benchmark datasets show that the performance of the proposed tracker is comparable to that of state-of-the-art trackers, while the proposed tracker runs at real-time speed.