OpenRaiser/Intern-Atlas huggingface dataset:
Yggdrasil: Privacy-aware Dual Deduplication in Multi Client Settings
Venue: arXiv cs.CR 2020
Year: 2020

This paper proposes Yggdrasil, a protocol for privacy-aware dual data deduplication in multi client settings. Yggdrasil is designed to reduce the cloud storage space while safeguarding the privacy of the client's outsourced data. Yggdrasil combines three innovative tools to achieve this goal. First, generalized deduplication, an emerging technique to reduce data footprint. Second, non-deterministic transformations that are described compactly and improve the degree of data compression in the Cloud (across users). Third, data preprocessing in the clients in the form of lightweight, privacy-driven transformations prior to upload. This guarantees that an honest-but-curious Cloud service trying to retrieve the client's actual data will face a high degree of uncertainty as to what the original data is. We provide a mathematical analysis of the measure of uncertainty as well as the compression potential of our protocol. Our experiments with a HDFS log data set shows that 49% overall compression can be achieved, with clients storing only 12% for privacy and the Cloud storing the rest. This is achieved while ensuring that each fragment uploaded to the Cloud would have 10^296 possible original strings from the client. Higher uncertainty is possible, with some reduction of compression potential.
Spectral Clustering using Eigenspectrum Shape Based Nystrom Sampling
Venue: arXiv cs.LG 2020
Year: 2020

Spectral clustering has shown a superior performance in analyzing the cluster structure. However, its computational complexity limits its application in analyzing large-scale data. To address this problem, many low-rank matrix approximating algorithms are proposed, including the Nystrom method - an approach with proven approximate error bounds. There are several algorithms that provide recipes to construct Nystrom approximations with variable accuracies and computing times. This paper proposes a scalable Nystrom-based clustering algorithm with a new sampling procedure, Centroid Minimum Sum of Squared Similarities (CMS3), and a heuristic on when to use it. Our heuristic depends on the eigen spectrum shape of the dataset, and yields competitive low-rank approximations in test datasets compared to the other state-of-the-art methods
Point-Location in The Arrangement of Curves
Venue: arXiv cs.CG 2020
Year: 2020

An arrangement of $n$ curves in the plane is given. The query is a point $q$ and the goal is to find the face of the arrangement that contains $q$. A data-structure for point-location, preprocesses the curves into a data structure of polynomial size in $n$, such that the queries can be answered in time polylogarithmic in $n$. We design a data structure for solving the point location problem queries in $O(\log C(n)+\log S(n))$ time using $O(T(n)+S(n)\log(S(n)))$ preprocessing time, if a polygonal subdivision of total size $S(n)$, with cell complexity at most $C(n)$ can be computed in time $T(n)$, such that the order of the parts of the curves inside each cell has a monotone order with respect to at least one segment of the boundary of the cell. We call such a partitioning a curve-monotone polygonal subdivision.
Wasserstein Routed Capsule Networks
Venue: arXiv cs.LG 2020
Year: 2020

Capsule networks offer interesting properties and provide an alternative to today's deep neural network architectures. However, recent approaches have failed to consistently achieve competitive results across different image datasets. We propose a new parameter efficient capsule architecture, that is able to tackle complex tasks by using neural networks trained with an approximate Wasserstein objective to dynamically select capsules throughout the entire architecture. This approach focuses on implementing a robust routing scheme, which can deliver improved results using little overhead. We perform several ablation studies verifying the proposed concepts and show that our network is able to substantially outperform other capsule approaches by over 1.2 % on CIFAR-10, using fewer parameters.
Deep Models and Shortwave Infrared Information to Detect Face Presentation Attacks
Venue: arXiv cs.CV 2020
Year: 2020

This paper addresses the problem of face presentation attack detection using different image modalities. In particular, the usage of short wave infrared (SWIR) imaging is considered. Face presentation attack detection is performed using recent models based on Convolutional Neural Networks using only carefully selected SWIR image differences as input. Conducted experiments show superior performance over similar models acting on either color images or on a combination of different modalities (visible, NIR, thermal and depth), as well as on a SVM-based classifier acting on SWIR image differences. Experiments have been carried on a new public and freely available database, containing a wide variety of attacks. Video sequences have been recorded thanks to several sensors resulting in 14 different streams in the visible, NIR, SWIR and thermal spectra, as well as depth data. The best proposed approach is able to almost perfectly detect all impersonation attacks while ensuring low bonafide classification errors. On the other hand, obtained results show that obfuscation attacks are more difficult to detect. We hope that the proposed database will foster research on this challenging problem. Finally, all the code and instructions to reproduce presented experiments is made available to the research community.
Characterization and Identification of Cloudified Mobile Network Performance Bottlenecks
Venue: arXiv cs.NI 2020
Year: 2020

This study is a first attempt to experimentally explore the range of performance bottlenecks that 5G mobile networks can experience. To this end, we leverage a wide range of measurements obtained with a prototype testbed that captures the key aspects of a cloudified mobile network. We investigate the relevance of the metrics and a number of approaches to accurately and efficiently identify bottlenecks across the different locations of the network and layers of the system architecture. Our findings validate the complexity of this task in the multi-layered architecture and highlight the need for novel monitoring approaches that intelligently fuse metrics across network layers and functions. In particular, we find that distributed analytics performs reasonably well both in terms of bottleneck identification accuracy and incurred computational and communication overhead.
Light Euclidean Spanners with Steiner Points
Venue: arXiv cs.CG 2020
Year: 2020

The FOCS'19 paper of Le and Solomon, culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy $(1+ε)$-spanner in $\mathbb{R}^d$ is $\tilde{O}(ε^{-d})$ for any $d = O(1)$ and any $ε= Ω(n^{-\frac{1}{d-1}})$ (where $\tilde{O}$ hides polylogarithmic factors of $\frac{1}ε$), and also shows the existence of point sets in $\mathbb{R}^d$ for which any $(1+ε)$-spanner must have lightness $Ω(ε^{-d})$. Given this tight bound on the lightness, a natural arising question is whether a better lightness bound can be achieved using Steiner points. Our first result is a construction of Steiner spanners in $\mathbb{R}^2$ with lightness $O(ε^{-1} \log Δ)$, where $Δ$ is the spread of the point set. In the regime of $Δ\ll 2^{1/ε}$, this provides an improvement over the lightness bound of Le and Solomon [FOCS 2019]; this regime of parameters is of practical interest, as point sets arising in real-life applications (e.g., for various random distributions) have polynomially bounded spread, while in spanner applications $ε$ often controls the precision, and it sometimes needs to be much smaller than $O(1/\log n)$. Moreover, for spread polynomially bounded in $1/ε$, this upper bound provides a quadratic improvement over the non-Steiner bound of Le and Solomon [FOCS 2019], We then demonstrate that such a light spanner can be constructed in $O_ε(n)$ time for polynomially bounded spread, where $O_ε$ hides a factor of $\mathrm{poly}(\frac{1}ε)$. Finally, we extend the construction to higher dimensions, proving a lightness upper bound of $\tilde{O}(ε^{-(d+1)/2} + ε^{-2}\log Δ)$ for any $3\leq d = O(1)$ and any $ε= Ω(n^{-\frac{1}{d-1}})$.
Attention based Multiple Instance Learning for Classification of Blood Cell Disorders
Venue: arXiv cs.CV 2020
Year: 2020

Red blood cells are highly deformable and present in various shapes. In blood cell disorders, only a subset of all cells is morphologically altered and relevant for the diagnosis. However, manually labeling of all cells is laborious, complicated and introduces inter-expert variability. We propose an attention based multiple instance learning method to classify blood samples of patients suffering from blood cell disorders. Cells are detected using an R-CNN architecture. With the features extracted for each cell, a multiple instance learning method classifies patient samples into one out of four blood cell disorders. The attention mechanism provides a measure of the contribution of each cell to the overall classification and significantly improves the network's classification accuracy as well as its interpretability for the medical expert.
Evaluation of Network Based IDS and Deployment of multi-sensor IDS
Venue: arXiv cs.NI 2020
Year: 2020

Cloud-based and network-based technology has witnessed an exponential rise in development. Adaptation of these latest technologies has opened flood gates for data breaches, an increase in sophistication of cyber threats, and, a multitude of new attack vectors. Numerous tools and solutions are currently available for detection of these threats. Network-based Intrusion Detection Systems is one of the most effective tools implemented to maintain confidentiality, integrity, and, availability of networks. While there are several open source tools in the offing, this paper evaluates two open-source NIDS Snort and Suricata, along with strategic placement of multi sensor IDS in a WAN environment, in combination with NIDS, for in time threat detection and protection of systems.
A report on the first virtual PLDI conference
Venue: arXiv cs.HC 2020
Year: 2020

This is a report on the PLDI 2020 conference, for which I was General Chair, which was held virtually for the first time as a result of the COVID-19 pandemic. The report contains: my personal reflections on the positive and negative aspects of the event; a description of the format of the event and associated logistical details; and data (with some analysis) on attendees' views on the conference format, the extent to which attendees engaged with the conference, attendees' views on virtual vs. physical conferences (with a focus on PLDI specifically) and the diversity of conference registrants. I hope that the report will be a useful resource for organizers of upcoming virtual conferences, and generally interesting to the Programming Languages community and beyond.
Co-Simulation of Human-Robot Collaboration: from Temporal Logic to 3D Simulation
Venue: arXiv cs.RO 2020
Year: 2020

Human-Robot Collaboration (HRC) is rapidly replacing the traditional application of robotics in the manufacturing industry. Robots and human operators no longer have to perform their tasks in segregated areas and are capable of working in close vicinity and performing hybrid tasks -- performed partially by humans and by robots. We have presented a methodology in an earlier work [16] to promote and facilitate formally modeling HRC systems, which are notoriously safety-critical. Relying on temporal logic modeling capabilities and automated model checking tools, we built a framework to formally model HRC systems and verify the physical safety of human operator against ISO 10218-2 [10] standard. In order to make our proposed formal verification framework more appealing to safety engineers, whom are usually not very fond of formal modeling and verification techniques, we decided to couple our model checking approach with a 3D simulator that demonstrates the potential hazardous situations to the safety engineers in a more transparent way. This paper reports our co-simulation approach, using Morse simulator [4] and Zot model checker [14].
Time Perception: A Review on Psychological, Computational and Robotic Models
Venue: arXiv cs.AI 2020
Year: 2020

Animals exploit time to survive in the world. Temporal information is required for higher-level cognitive abilities such as planning, decision making, communication, and effective cooperation. Since time is an inseparable part of cognition, there is a growing interest in the artificial intelligence approach to subjective time, which has a possibility of advancing the field. The current survey study aims to provide researchers with an interdisciplinary perspective on time perception. Firstly, we introduce a brief background from the psychology and neuroscience literature, covering the characteristics and models of time perception and related abilities. Secondly, we summarize the emergent computational and robotic models of time perception. A general overview to the literature reveals that a substantial amount of timing models are based on a dedicated time processing like the emergence of a clock-like mechanism from the neural network dynamics and reveal a relationship between the embodiment and time perception. We also notice that most models of timing are developed for either sensory timing (i.e. ability to assess an interval) or motor timing (i.e. ability to reproduce an interval). The number of timing models capable of retrospective timing, which is the ability to track time without paying attention, is insufficient. In this light, we discuss the possible research directions to promote interdisciplinary collaboration in the field of time perception.
A Semismooth-Newton's-Method-Based Linearization and Approximation Approach for Kernel Support Vector Machines
Venue: arXiv cs.LG 2020
Year: 2020

Support Vector Machines (SVMs) are among the most popular and the best performing classification algorithms. Various approaches have been proposed to reduce the high computation and memory cost when training and predicting based on large-scale datasets with kernel SVMs. A popular one is the linearization framework, which successfully builds a bridge between the $L_1$-loss kernel SVM and the $L_1$-loss linear SVM. For linear SVMs, very recently, a semismooth Newton's method is proposed. It is shown to be very competitive and have low computational cost. Consequently, a natural question is whether it is possible to develop a fast semismooth Newton's algorithm for kernel SVMs. Motivated by this question and the idea in linearization framework, in this paper, we focus on the $L_2$-loss kernel SVM and propose a semismooth Newton's method based linearization and approximation approach for it. The main idea of this approach is to first set up an equivalent linear SVM, then apply the Nyström method to approximate the kernel matrix, based on which a reduced linear SVM is obtained. Finally, the fast semismooth Newton's method is employed to solve the reduced linear SVM. We also provide some theoretical analyses on the approximation of the kernel matrix. The advantage of the proposed approach is that it maintains low computational cost and keeps a fast convergence rate. Results of extensive numerical experiments verify the efficiency of the proposed approach in terms of both predicting accuracy and speed.
Dog Identification using Soft Biometrics and Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

This paper addresses the problem of biometric identification of animals, specifically dogs. We apply advanced machine learning models such as deep neural network on the photographs of pets in order to determine the pet identity. In this paper, we explore the possibility of using different types of "soft" biometrics, such as breed, height, or gender, in fusion with "hard" biometrics such as photographs of the pet's face. We apply the principle of transfer learning on different Convolutional Neural Networks, in order to create a network designed specifically for breed classification. The proposed network is able to achieve an accuracy of 90.80% and 91.29% when differentiating between the two dog breeds, for two different datasets. Without the use of "soft" biometrics, the identification rate of dogs is 78.09% but by using a decision network to incorporate "soft" biometrics, the identification rate can achieve an accuracy of 84.94%.
ADER: Adaptively Distilled Exemplar Replay Towards Continual Learning for Session-based Recommendation
Venue: arXiv cs.LG 2020
Year: 2020

Session-based recommendation has received growing attention recently due to the increasing privacy concern. Despite the recent success of neural session-based recommenders, they are typically developed in an offline manner using a static dataset. However, recommendation requires continual adaptation to take into account new and obsolete items and users, and requires "continual learning" in real-life applications. In this case, the recommender is updated continually and periodically with new data that arrives in each update cycle, and the updated model needs to provide recommendations for user activities before the next model update. A major challenge for continual learning with neural models is catastrophic forgetting, in which a continually trained model forgets user preference patterns it has learned before. To deal with this challenge, we propose a method called Adaptively Distilled Exemplar Replay (ADER) by periodically replaying previous training samples (i.e., exemplars) to the current model with an adaptive distillation loss. Experiments are conducted based on the state-of-the-art SASRec model using two widely used datasets to benchmark ADER with several well-known continual learning techniques. We empirically demonstrate that ADER consistently outperforms other baselines, and it even outperforms the method using all historical data at every update cycle. This result reveals that ADER is a promising solution to mitigate the catastrophic forgetting issue towards building more realistic and scalable session-based recommenders.
Dataflow Analysis With Prophecy and History Variables
Venue: arXiv cs.PL 2020
Year: 2020

Leveraging concepts from state machine refinement proofs, we use prophecy variables, which predict information about the future program execution, to enable forward reasoning for backward dataflow analyses. Drawing prophecy and history variables (concepts from the dynamic execution of the program) from the same lattice as the static program analysis results, we require the analysis results to satisfy both the dataflow equations and the transition relations in the operational semantics of underlying programming language. This approach eliminates explicit abstraction and concretization functions and promotes a more direct connection between the analysis and program executions, with the connection taking the form of a bisimulation relation between concrete executions and an augmented operational semantics over the analysis results. We present several classical dataflow analyses with this approach (live variables, very busy expressions, defined variables, and reaching definitions) along with proofs that highlight how this approach can enable more streamlined reasoning. To the best of our knowledge, we are the first to use prophecy variables for dataflow analysis.
A comparative analysis of knowledge acquisition performance in complex networks
Venue: arXiv cs.SI 2020
Year: 2020

Discovery processes have been an important topic in the network science field. The exploration of nodes can be understood as the knowledge acquisition process taking place in the network, where nodes represent concepts and edges are the semantical relationships between concepts. While some studies have analyzed the performance of the knowledge acquisition process in particular network topologies, here we performed a systematic performance analysis in well-known dynamics and topologies. Several interesting results have been found. Overall, all learning curves displayed the same learning shape, with different speed rates. We also found ambiguities in the feature space describing the learning curves, meaning that the same knowledge acquisition curve can be generated in different combinations of network topology and dynamics. A surprising example of such patterns are the learning curves obtained from random and Waxman networks: despite the very distinct characteristics in terms of global structure, several curves from different models turned out to be similar. All in all, our results suggest that different learning strategies can lead to the same learning performance. From the network reconstruction point of view, however, this means that learning curves of observed sequences should be combined with other sequence features if one aims at inferring network topology from observed sequences.
The expressive power of kth-order invariant graph networks
Venue: arXiv cs.LG 2020
Year: 2020

The expressive power of graph neural network formalisms is commonly measured by their ability to distinguish graphs. For many formalisms, the k-dimensional Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this paper we consider the expressive power of kth-order invariant (linear) graph networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate k-WL. This means that for any two graphs that can be distinguished by k-WL, one can find a k-IGN which also distinguishes those graphs. The question remains whether k-IGNs can distinguish more graphs than k-WL. This was recently shown to be false for k=2. Here, we generalise this result to arbitrary k. In other words, we show that k-IGNs are bounded in expressive power by k-WL. This implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.
A Study on Evaluation Standard for Automatic Crack Detection Regard the Random Fractal
Venue: arXiv cs.CV 2020
Year: 2020

A reasonable evaluation standard underlies construction of effective deep learning models. However, we find in experiments that the automatic crack detectors based on deep learning are obviously underestimated by the widely used mean Average Precision (mAP) standard. This paper presents a study on the evaluation standard. It is clarified that the random fractal of crack disables the mAP standard, because the strict box matching in mAP calculation is unreasonable for the fractal feature. As a solution, a fractal-available evaluation standard named CovEval is proposed to correct the underestimation in crack detection. In CovEval, a different matching process based on the idea of covering box matching is adopted for this issue. In detail, Cover Area rate (CAr) is designed as a covering overlap, and a multi-match strategy is employed to release the one-to-one matching restriction in mAP. Extended Recall (XR), Extended Precision (XP) and Extended F-score (Fext) are defined for scoring the crack detectors. In experiments using several common frameworks for object detection, models get much higher scores in crack detection according to CovEval, which matches better with the visual performance. Moreover, based on faster R-CNN framework, we present a case study to optimize a crack detector based on CovEval standard. Recall (XR) of our best model achieves an industrial-level at 95.8, which implies that with reasonable standard for evaluation, the methods for object detection are with great potential for automatic industrial inspection.