OpenRaiser/Intern-Atlas huggingface dataset:
VERONICA: Expressive and Precise Concurrent Information Flow Security (Extended Version with Technical Appendices)
Venue: arXiv cs.LO 2020
Year: 2020

Methods for proving that concurrent software does not leak its secrets has remained an active topic of research for at least the past four decades. Despite an impressive array of work, the present situation remains highly unsatisfactory. With contemporary compositional proof methods one is forced to choose between expressiveness (the ability to reason about a wide variety of security policies), on the one hand, and precision (the ability to reason about complex thread interactions and program behaviours), on the other. Achieving both is essential and, we argue, requires a new style of compositional reasoning. We present VERONICA, the first program logic for proving concurrent programs information flow secure that supports compositional, high-precision reasoning about a wide range of security policies and program behaviours (e.g. expressive de-classification, value-dependent classification, secret-dependent branching). Just as importantly, VERONICA embodies a new approach for engineering such logics that can be re-used elsewhere, called decoupled functional correctness (DFC). DFC leads to a simple and clean logic, even while achieving this unprecedented combination of features. We demonstrate the virtues and versatility of VERONICA by verifying a range of example programs, beyond the reach of prior methods.
A Graph-Based Approach for Active Learning in Regression
Venue: arXiv cs.LG 2020
Year: 2020

Active learning aims to reduce labeling efforts by selectively asking humans to annotate the most important data points from an unlabeled pool and is an example of human-machine interaction. Though active learning has been extensively researched for classification and ranking problems, it is relatively understudied for regression problems. Most existing active learning for regression methods use the regression function learned at each active learning iteration to select the next informative point to query. This introduces several challenges such as handling noisy labels, parameter uncertainty and overcoming initially biased training data. Instead, we propose a feature-focused approach that formulates both sequential and batch-mode active regression as a novel bipartite graph optimization problem. We conduct experiments on both noise-free and noisy settings. Our experimental results on benchmark data sets demonstrate the effectiveness of our proposed approach.
Visual Exploration of Movement Relatedness for Multi-species Ecology Analysis
Venue: arXiv cs.HC 2020
Year: 2020

Advances in GPS telemetry technology have enabled analysis of animal movement in open areas. Ecologists today are utilizing modern analytic tools to study animal behaviors from large quantity of GPS coordinates. Analytic tools with automatic event extraction functionality can be used to investigate potential interactions between animals by locating relevant segments in movement trajectories. However, such automation can easily overlook the spatial, temporal, social context as well as potential data problems. To this end, this paper explores the visual presentations that also clarify the spatial-temporal contexts, social surroudings, as well as underlying data uncertainties of multi-species animal interactions. The outcome system presents the proximity-based, time-varying relatedness between animal entities through pairwise (PW) or individual-to-group (i-G) perspectives. Focusing on the relational aspects, we employ both static depictions and animations to communicate the travelling of individuals. Our contributions are a novel visualization system that helps investigate the subtle variations of long term spatial-temporal relatedness while considering small group patterns. Our evaluation with movement ecologists shows that the system gives them quick access to valuable clues in discovering insights into multi-species movements and signs of potential interactions.
Multiple Object Tracking by Flowing and Fusing
Venue: arXiv cs.CV 2020
Year: 2020

Most of Multiple Object Tracking (MOT) approaches compute individual target features for two subtasks: estimating target-wise motions and conducting pair-wise Re-Identification (Re-ID). Because of the indefinite number of targets among video frames, both subtasks are very difficult to scale up efficiently in end-to-end Deep Neural Networks (DNNs). In this paper, we design an end-to-end DNN tracking approach, Flow-Fuse-Tracker (FFT), that addresses the above issues with two efficient techniques: target flowing and target fusing. Specifically, in target flowing, a FlowTracker DNN module learns the indefinite number of target-wise motions jointly from pixel-level optical flows. In target fusing, a FuseTracker DNN module refines and fuses targets proposed by FlowTracker and frame-wise object detection, instead of trusting either of the two inaccurate sources of target proposal. Because FlowTracker can explore complex target-wise motion patterns and FuseTracker can refine and fuse targets from FlowTracker and detectors, our approach can achieve the state-of-the-art results on several MOT benchmarks. As an online MOT approach, FFT produced the top MOTA of 46.3 on the 2DMOT15, 56.5 on the MOT16, and 56.5 on the MOT17 tracking benchmarks, surpassing all the online and offline methods in existing publications.
How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction
Venue: arXiv cs.SI 2020
Year: 2020

Hypergraphs provide a natural way of representing group relations, whose complexity motivates an extensive array of prior work to adopt some form of abstraction and simplification of higher-order interactions. However, the following question has yet to be addressed: How much abstraction of group interactions is sufficient in solving a hypergraph task, and how different such results become across datasets? This question, if properly answered, provides a useful engineering guideline on how to trade off between complexity and accuracy of solving a downstream task. To this end, we propose a method of incrementally representing group interactions using a notion of n-projected graph whose accumulation contains information on up to n-way interactions, and quantify the accuracy of solving a task as n grows for various datasets. As a downstream task, we consider hyperedge prediction, an extension of link prediction, which is a canonical task for evaluating graph models. Through experiments on 15 real-world datasets, we draw the following messages: (a) Diminishing returns: small n is enough to achieve accuracy comparable with near-perfect approximations, (b) Troubleshooter: as the task becomes more challenging, larger n brings more benefit, and (c) Irreducibility: datasets whose pairwise interactions do not tell much about higher-order interactions lose much accuracy when reduced to pairwise abstractions.
Automatic marker-free registration of tree point-cloud data based on rotating projection
Venue: arXiv cs.CV 2020
Year: 2020

Point-cloud data acquired using a terrestrial laser scanner (TLS) play an important role in digital forestry research. Multiple scans are generally used to overcome occlusion effects and obtain complete tree structural information. However, it is time-consuming and difficult to place artificial reflectors in a forest with complex terrain for marker-based registration, a process that reduces registration automation and efficiency. In this study, we propose an automatic coarse-to-fine method for the registration of point-cloud data from multiple scans of a single tree. In coarse registration, point clouds produced by each scan are projected onto a spherical surface to generate a series of two-dimensional (2D) images, which are used to estimate the initial positions of multiple scans. Corresponding feature-point pairs are then extracted from these series of 2D images. In fine registration, point-cloud data slicing and fitting methods are used to extract corresponding central stem and branch centers for use as tie points to calculate fine transformation parameters. To evaluate the accuracy of registration results, we propose a model of error evaluation via calculating the distances between center points from corresponding branches in adjacent scans. For accurate evaluation, we conducted experiments on two simulated trees and a real-world tree. Average registration errors of the proposed method were 0.26m around on simulated tree point clouds, and 0.05m around on real-world tree point cloud.
Parity (XOR) Reasoning for the Index Calculus Attack
Venue: arXiv cs.CR 2020
Year: 2020

Cryptographic problems can often be reduced to solving Boolean polynomial systems, whose equivalent logical formulas can be treated using SAT solvers. Given the algebraic nature of the problem, the use of the logical XOR operator is common in SAT-based cryptanalysis. Recent works have focused on advanced techniques for handling parity (XOR) constraints, such as the Gaussian Elimination technique. First, we propose an original XOR-reasoning SAT solver, named WDSat (Weil Descent SAT solving), dedicated to a specific cryptographic problem. Secondly, we show that in some cases Gaussian Elimination on SAT instances does not work as well as Gaussian Elimination on algebraic systems. We demonstrate how this oversight is fixed in our solver, which is adapted to read instances in algebraic normal form (ANF). Finally, we propose a novel preprocessing technique based on the Minimal Vertex Cover Problem in graph theory. This preprocessing technique is, within the framework of multivariate Boolean polynomial systems, used as a DLL branching selection rule that leads to quick linearization of the underlying algebraic system. Our benchmarks use a model obtained from cryptographic instances for which a significant speedup is achieved using the findings in this paper. We further explain how our preprocessing technique can be used as an assessment of the security of a cryptographic system.
Learning Discrete Distributions by Dequantization
Venue: arXiv cs.LG 2020
Year: 2020

Media is generally stored digitally and is therefore discrete. Many successful deep distribution models in deep learning learn a density, i.e., the distribution of a continuous random variable. Naïve optimization on discrete data leads to arbitrarily high likelihoods, and instead, it has become standard practice to add noise to datapoints. In this paper, we present a general framework for dequantization that captures existing methods as a special case. We derive two new dequantization objectives: importance-weighted (iw) dequantization and Rényi dequantization. In addition, we introduce autoregressive dequantization (ARD) for more flexible dequantization distributions. Empirically we find that iw and Rényi dequantization considerably improve performance for uniform dequantization distributions. ARD achieves a negative log-likelihood of 3.06 bits per dimension on CIFAR10, which to the best of our knowledge is state-of-the-art among distribution models that do not require autoregressive inverses for sampling.
Algorithmic Aspects of Secure Connected Domination in Graphs
Venue: arXiv cs.DM 2020
Year: 2020

Let $G = (V,E)$ be a simple, undirected and connected graph. A connected dominating set $S \subseteq V$ is a secure connected dominating set of $G$, if for each $ u \in V\setminus S$, there exists $v\in S$ such that $(u,v) \in E$ and the set $(S \setminus \{ v \}) \cup \{ u \} $ is a connected dominating set of $G$. The minimum size of a secure connected dominating set of $G$ denoted by $ γ_{sc} (G)$, is called the secure connected domination number of $G$. Given a graph $ G$ and a positive integer $ k,$ the Secure Connected Domination (SCDM) problem is to check whether $ G $ has a secure connected dominating set of size at most $ k.$ In this paper, we prove that the SCDM problem is NP-complete for doubly chordal graphs, a subclass of chordal graphs. We investigate the complexity of this problem for some subclasses of bipartite graphs namely, star convex bipartite, comb convex bipartite, chordal bipartite and chain graphs. The Minimum Secure Connected Dominating Set (MSCDS) problem is to find a secure connected dominating set of minimum size in the input graph. We propose a $ (Δ(G)+1) $ - approximation algorithm for MSCDS, where $ Δ(G) $ is the maximum degree of the input graph $ G $ and prove that MSCDS cannot be approximated within $ (1 -ε) ln(| V |)$ for any $ ε> 0 $ unless $ NP \subseteq DTIME(| V |^{O(log log | V |)})$ even for bipartite graphs. Finally, we show that the MSCDS is APX-complete for graphs with $Δ(G)=4$.
HAMLET -- A Learning Curve-Enabled Multi-Armed Bandit for Algorithm Selection
Venue: arXiv cs.LG 2020
Year: 2020

Automated algorithm selection and hyperparameter tuning facilitates the application of machine learning. Traditional multi-armed bandit strategies look to the history of observed rewards to identify the most promising arms for optimizing expected total reward in the long run. When considering limited time budgets and computational resources, this backward view of rewards is inappropriate as the bandit should look into the future for anticipating the highest final reward at the end of a specified time budget. This work addresses that insight by introducing HAMLET, which extends the bandit approach with learning curve extrapolation and computation time-awareness for selecting among a set of machine learning algorithms. Results show that the HAMLET Variants 1-3 exhibit equal or better performance than other bandit-based algorithm selection strategies in experiments with recorded hyperparameter tuning traces for the majority of considered time budgets. The best performing HAMLET Variant 3 combines learning curve extrapolation with the well-known upper confidence bound exploration bonus. That variant performs better than all non-HAMLET policies with statistical significance at the 95% level for 1,485 runs.
A Study of Fitness Landscapes for Neuroevolution
Venue: arXiv cs.NE 2020
Year: 2020

Fitness landscapes are a useful concept to study the dynamics of meta-heuristics. In the last two decades, they have been applied with success to estimate the optimization power of several types of evolutionary algorithms, including genetic algorithms and genetic programming. However, so far they have never been used to study the performance of machine learning algorithms on unseen data, and they have never been applied to neuroevolution. This paper aims at filling both these gaps, applying for the first time fitness landscapes to neuroevolution and using them to infer useful information about the predictive ability of the method. More specifically, we use a grammar-based approach to generate convolutional neural networks, and we study the dynamics of three different mutations to evolve them. To characterize fitness landscapes, we study autocorrelation and entropic measure of ruggedness. The results show that these measures are appropriate for estimating both the optimization power and the generalization ability of the considered neuroevolution configurations.
Constructing Deep Neural Networks with a Priori Knowledge of Wireless Tasks
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks (DNNs) have been employed for designing wireless systems in many aspects, say transceiver design, resource optimization, and information prediction. Existing works either use the fully-connected DNN or the DNNs with particular architectures developed in other domains. While generating labels for supervised learning and gathering training samples are time-consuming or cost-prohibitive, how to develop DNNs with wireless priors for reducing training complexity remains open. In this paper, we show that two kinds of permutation invariant properties widely existed in wireless tasks can be harnessed to reduce the number of model parameters and hence the sample and computational complexity for training. We find special architecture of DNNs whose input-output relationships satisfy the properties, called permutation invariant DNN (PINN), and augment the data with the properties. By learning the impact of the scale of a wireless system, the size of the constructed PINNs can flexibly adapt to the input data dimension. We take predictive resource allocation and interference coordination as examples to show how the PINNs can be employed for learning the optimal policy with unsupervised and supervised learning. Simulations results demonstrate a dramatic gain of the proposed PINNs in terms of reducing training complexity.
Learning to Structure Long-term Dependence for Sequential Recommendation
Venue: arXiv cs.IR 2020
Year: 2020

Sequential recommendation recommends items based on sequences of users' historical actions. The key challenge in it is how to effectively model the influence from distant actions to the action to be predicted, i.e., recognizing the long-term dependence structure; and it remains an underexplored problem. To better model the long-term dependence structure, we propose a GatedLongRec solution in this work. To account for the long-term dependence, GatedLongRec extracts distant actions of top-$k$ related categories to the user's ongoing intent with a top-$k$ gating network, and utilizes a long-term encoder to encode the transition patterns among these identified actions. As user intent is not directly observable, we take advantage of available side-information about the actions, i.e., the category of their associated items, to infer the intents. End-to-end training is performed to estimate the intent representation and predict the next action for sequential recommendation. Extensive experiments on two large datasets show that the proposed solution can recognize the structure of long-term dependence, thus greatly improving the sequential recommendation.
P4-Protect: 1+1 Path Protection for P4
Venue: arXiv cs.NI 2020
Year: 2020

1+1 protection is a method to secure traffic between two nodes against failures in between. The sending node duplicates the traffic and forwards it over two disjoint paths. The receiving node assures that only a single copy of the traffic is further forwarded to its destination. In contrast to other protection schemes, this method prevents almost any packet loss in case of failures. 1+1 protection is usually applied on the optical layer, on Ethernet, or on MPLS. In this work we propose the application of 1+1 for P4-based IP networks. We define an 1+1 protection header for that purpose. We describe the behavior of sending and receiving nodes and provide a P4-based implementation for the BMv2 software switch and the hardware switch Tofino Edgecore Wedge 100BF-32X. We illustrate how to secure traffic, e.g. individual TCP flows, on the Internet with this approach. Finally, we present performance results showing that the P4-based implementation efficiently works on the Tofino Edgecore Wedge 100BF-32X.
Proposal of a standard of Knowledge Management and Technological Innovation for Mexico
Venue: arXiv cs.OH 2020
Year: 2020

The purpose of this work is to offer a methodology that allows to construct a standard in Knowledge Management and Technological Innovation which may be used in various organizations in México to improve the operation of their resources and productivity. Based on the review of the existing literature, a model is offered including several elements to enable organizations to establish their position in relation to both concepts. The following proposal is based on a systematic effort to understand and integrate models of Knowledge Management and Innovation published in recent years as well as the results of the experiences to propose standards of Knowledge Management and Technological Innovation. In order to elaborate the proposal, factors and their associated components have been analyzed through a review of the literature in order to build and validate a standard proposal. To test the research study, a six-stage research model has been constructed. For this purpose, an in-depth exploratory research study has been carried out in a public sector organization, in an area that allows the replicability of the model. The results have been analyzed to construct and empirically validate the Mexican Standard of Knowledge Management an Technological Innovation. Finally, after the statistical analysis, results obtained from the application of the validated instrument are shown , which supports the definition of the model.
Unsupervised Sentiment Analysis for Code-mixed Data
Venue: arXiv cs.CL 2020
Year: 2020

Code-mixing is the practice of alternating between two or more languages. Mostly observed in multilingual societies, its occurrence is increasing and therefore its importance. A major part of sentiment analysis research has been monolingual, and most of them perform poorly on code-mixed text. In this work, we introduce methods that use different kinds of multilingual and cross-lingual embeddings to efficiently transfer knowledge from monolingual text to code-mixed text for sentiment analysis of code-mixed text. Our methods can handle code-mixed text through a zero-shot learning. Our methods beat state-of-the-art on English-Spanish code-mixed sentiment analysis by absolute 3\% F1-score. We are able to achieve 0.58 F1-score (without parallel corpus) and 0.62 F1-score (with parallel corpus) on the same benchmark in a zero-shot way as compared to 0.68 F1-score in supervised settings. Our code is publicly available.
Analysing Affective Behavior in the First ABAW 2020 Competition
Venue: arXiv cs.LG 2020
Year: 2020

The Affective Behavior Analysis in-the-wild (ABAW) 2020 Competition is the first Competition aiming at automatic analysis of the three main behavior tasks of valence-arousal estimation, basic expression recognition and action unit detection. It is split into three Challenges, each one addressing a respective behavior task. For the Challenges, we provide a common benchmark database, Aff-Wild2, which is a large scale in-the-wild database and the first one annotated for all these three tasks. In this paper, we describe this Competition, to be held in conjunction with the IEEE Conference on Face and Gesture Recognition, May 2020, in Buenos Aires, Argentina. We present the three Challenges, with the utilized Competition corpora. We outline the evaluation metrics, present both the baseline system and the top-3 performing teams' methodologies per Challenge and finally present their obtained results. More information regarding the Competition, the leaderboard of each Challenge and details for accessing the utilized database, are provided in the Competition site: http://ibug.doc.ic.ac.uk/resources/fg-2020-competition-affective-behavior-analysis.
Shared-Memory Parallel Maximal Clique Enumeration from Static and Dynamic Graphs
Venue: arXiv cs.DC 2020
Year: 2020

Maximal Clique Enumeration (MCE) is a fundamental graph mining problem, and is useful as a primitive in identifying dense structures in a graph. Due to the high computational cost of MCE, parallel methods are imperative for dealing with large graphs. We present shared-memory parallel algorithms for MCE, with the following properties: (1) the parallel algorithms are provably work-efficient relative to a state-of-the-art sequential algorithm (2) the algorithms have a provably small parallel depth, showing they can scale to a large number of processors, and (3) our implementations on a multicore machine show good speedup and scaling behavior with increasing number of cores, and are substantially faster than prior shared-memory parallel algorithms for MCE; for instance, on certain input graphs, while prior works either ran out of memory or did not complete in 5 hours, our implementation finished within a minute using 32 cores. We also present work-efficient parallel algorithms for maintaining the set of all maximal cliques in a dynamic graph that is changing through the addition of edges.