OpenRaiser/Intern-Atlas huggingface dataset:
Angular separability of data clusters or network communities in geometrical space and its relevance to hyperbolic embedding
Venue: arXiv cs.LG 2019
Year: 2019

Analysis of 'big data' characterized by high-dimensionality such as word vectors and complex networks requires often their representation in a geometrical space by embedding. Recent developments in machine learning and network geometry have pointed out the hyperbolic space as a useful framework for the representation of this data derived by real complex physical systems. In the hyperbolic space, the radial coordinate of the nodes characterizes their hierarchy, whereas the angular distance between them represents their similarity. Several studies have highlighted the relationship between the angular coordinates of the nodes embedded in the hyperbolic space and the community metadata available. However, such analyses have been often limited to a visual or qualitative assessment. Here, we introduce the angular separation index (ASI), to quantitatively evaluate the separation of node network communities or data clusters over the angular coordinates of a geometrical space. ASI is particularly useful in the hyperbolic space - where it is extensively tested along this study - but can be used in general for any assessment of angular separation regardless of the adopted geometry. ASI is proposed together with an exact test statistic based on a uniformly random null model to assess the statistical significance of the separation. We show that ASI allows to discover two significant phenomena in network geometry. The first is that the increase of temperature in 2D hyperbolic network generative models, not only reduces the network clustering but also induces a 'dimensionality jump' of the network to dimensions higher than two. The second is that ASI can be successfully applied to detect the intrinsic dimensionality of network structures that grow in a hidden geometrical space.
Forensic Analysis of Third Party Location Applications in Android and iOS
Venue: arXiv cs.CR 2019
Year: 2019

Location sharing applications are becoming increasingly common. These applications allow users to share their own locations and view contacts' current locations on a map. Location applications are commonly used by friends and family members to view Global Positioning System (GPS) location of an individual, but valuable forensic evidence may exist in this data when stored locally on smartphones. This paper aims to discover forensic artifacts from two popular third-party location sharing applications on iOS and Android devices. Industry standard mobile forensic suites are utilized to discover if any locally stored data could be used to assist investigations reliant on knowing the past location of a suspect. Security issues raised regarding the artifacts found during our analysis is also discussed.
Programming with Timespans in Interactive Visualizations
Venue: arXiv cs.HC 2019
Year: 2019

Modern interactive visualizations are akin to distributed systems, where user interactions, background data processing, remote requests, and streaming data read and modify the interface at the same time. This concurrency is crucial to provide an interactive user experience---forbidding it can cripple responsiveness. However, it is notoriously challenging to program distributed systems, and concurrency can easily lead to ambiguous or confusing interface behaviors. In this paper, we present DIEL, a declarative programming model to help developers reason about and reconcile concurrency-related issues. Using DIEL, developers no longer need to procedurally describe how the interface should update based on different input events, but rather declaratively specify what the state of the interface should be as queries over event history. We show that resolving conflicts from concurrent processes in real-world interactive visualizations can be done in a few lines of DIEL code.
Millemeter-Wave Fixed Wireless Access Using IEEE 802.11ay
Venue: arXiv cs.NI 2019
Year: 2019

IEEE 802.11ay defines new PHY and MAC specifications that enable 100 Gbps communications in the 60 GHz millimeter-wave (mmWave) band. Among the various use cases supported by IEEE 802.11ay, fixed wireless access, a cost-efficient high-performance alternative and/or complement to conventional fixed access, differentiates itself due to its unique requirements and characteristics. In this article, our goal is to identify and describe key elements incorporated into IEEE 802.11ay, including scheduling, beamforming, and link maintenance, that efficiently support fixed wireless access. IEEE 802.11ay is thus a viable and strong candidate to form the basis of future generations of standards-compliant (i.e., non-proprietary) mmWave fixed wireless access networks.
DRAT-based Bit-Vector Proofs in CVC4
Venue: arXiv cs.LO 2019
Year: 2019

Many state-of-the-art Satisfiability Modulo Theories (SMT) solvers for the theory of fixed-size bit-vectors employ an approach called bit-blasting, where a given formula is translated into a Boolean satisfiability (SAT) problem and delegated to a SAT solver. Consequently, producing bit-vector proofs in an SMT solver requires incorporating SAT proofs into its proof infrastructure. In this paper, we describe three approaches for integrating DRAT proofs generated by an off-the-shelf SAT solver into the proof infrastructure of the SMT solver CVC4 and explore their strengths and weaknesses. We implemented all three approaches using cryptominisat as the SAT back-end for its bit-blasting engine and evaluated performance in terms of proof-production and proof-checking.
Helion: Enabling a Natural Perspective of Home Automation
Venue: arXiv cs.CR 2019
Year: 2019

Security researchers have recently discovered significant security and safety issues related to home automation and developed approaches to address them. Such approaches often face design and evaluation challenges which arise from their restricted perspective of home automation that is bounded by the IoT apps they analyze. The challenges of past work can be overcome by relying on a deeper understanding of realistic home automation usage. More specifically, the availability of natural home automation scenarios, i.e., sequences of home automation events that may realistically occur in an end-user's home, could help security researchers design better security/safety systems. This paper presents Helion, a framework for building a natural perspective of home automation. Helion identifies the regularities in user-driven home automation, i.e., from user-driven routines that are increasingly being created by users through intuitive platform UIs. Our intuition for designing Helion is that smart home event sequences created by users exhibit an inherent set of semantic patterns, or naturalness that can be modeled and used to generate valid and useful scenarios. To evaluate our approach, we first empirically demonstrate that this naturalness hypothesis holds, with a corpus of 30,518 home automation events, constructed from 273 routines collected from 40 users. We then demonstrate that the scenarios generated by Helion are reasonable and valid from an end-user perspective, through an evaluation with 16 external evaluators. We further show the usefulness of Helion's scenarios by generating 17 home security/safety policies with significantly less effort than existing approaches. We conclude by discussing key takeaways and future research challenges enabled by Helion's natural perspective of home automation.
Approximate Inference in Structured Instances with Noisy Categorical Observations
Venue: arXiv cs.LG 2019
Year: 2019

We study the problem of recovering the latent ground truth labeling of a structured instance with categorical random variables in the presence of noisy observations. We present a new approximate algorithm for graphs with categorical variables that achieves low Hamming error in the presence of noisy vertex and edge observations. Our main result shows a logarithmic dependency of the Hamming error to the number of categories of the random variables. Our approach draws connections to correlation clustering with a fixed number of clusters. Our results generalize the works of Globerson et al. (2015) and Foster et al. (2018), who study the hardness of structured prediction under binary labels, to the case of categorical labels.
Causal Inference Under Interference And Network Uncertainty
Venue: arXiv cs.LG 2019
Year: 2019

Classical causal and statistical inference methods typically assume the observed data consists of independent realizations. However, in many applications this assumption is inappropriate due to a network of dependences between units in the data. Methods for estimating causal effects have been developed in the setting where the structure of dependence between units is known exactly, but in practice there is often substantial uncertainty about the precise network structure. This is true, for example, in trial data drawn from vulnerable communities where social ties are difficult to query directly. In this paper we combine techniques from the structure learning and interference literatures in causal inference, proposing a general method for estimating causal effects under data dependence when the structure of this dependence is not known a priori. We demonstrate the utility of our method on synthetic datasets which exhibit network dependence.
Evaluating Local Geometric Feature Representations for 3D Rigid Data Matching
Venue: arXiv cs.CV 2019
Year: 2019

Local geometric descriptors remain an essential component for 3D rigid data matching and fusion. The devise of a rotational invariant local geometric descriptor usually consists of two steps: local reference frame (LRF) construction and feature representation. Existing evaluation efforts have mainly been paid on the LRF or the overall descriptor, yet the quantitative comparison of feature representations remains unexplored. This paper fills this gap by comprehensively evaluating nine state-of-the-art local geometric feature representations. Our evaluation is on the ground that ground-truth LRFs are leveraged such that the ranking of tested feature representations are more convincing as opposed to existing studies. The experiments are deployed on six standard datasets with various application scenarios (shape retrieval, point cloud registration, and object recognition) and data modalities (LiDAR, Kinect, and Space Time) as well as perturbations including Gaussian noise, shot noise, data decimation, clutter, occlusion, and limited overlap. The evaluated terms cover the major concerns for a feature representation, e.g., distinctiveness, robustness, compactness, and efficiency. The outcomes present interesting findings that may shed new light on this community and provide complementary perspectives to existing evaluations on the topic of local geometric feature description. A summary of evaluated methods regarding their peculiarities is also presented to guide real-world applications and new descriptor crafting.
Collaboration of AI Agents via Cooperative Multi-Agent Deep Reinforcement Learning
Venue: arXiv cs.MA 2019
Year: 2019

There are many AI tasks involving multiple interacting agents where agents should learn to cooperate and collaborate to effectively perform the task. Here we develop and evaluate various multi-agent protocols to train agents to collaborate with teammates in grid soccer. We train and evaluate our multi-agent methods against a team operating with a smart hand-coded policy. As a baseline, we train agents concurrently and independently, with no communication. Our collaborative protocols were parameter sharing, coordinated learning with communication, and counterfactual policy gradients. Against the hand-coded team, the team trained with parameter sharing and the team trained with coordinated learning performed the best, scoring on 89.5% and 94.5% of episodes respectively when playing against the hand-coded team. Against the parameter sharing team, with adversarial training the coordinated learning team scored on 75% of the episodes, indicating it is the most adaptable of our methods. The insights gained from our work can be applied to other domains where multi-agent collaboration could be beneficial.
Secure Mobile Technologies for Proactive Critical Infrastructure Situational Awareness
Venue: arXiv cs.CR 2019
Year: 2019

Trustworthy operation of our national critical infrastructures, such as the electricity grid, against adversarial parties and accidental failures requires constant and secure monitoring capabilities. In this paper, Eyephone is presented to leverage secure smartphone sensing and data acquisition capabilities and enable pervasive sensing of the national critical infrastructures. The reported information by the smartphone users will notify the control center operators about particular accidental or malicious remote critical infrastructure incidents. The reporting will be proactive regarding potentially upcoming failures given the system's current risky situation, e.g., a tree close to fall on a power grid transmission line. The information will include various modalities such as images, video, audio, time and location. Eyephone will use system-wide information flow analysis and policy enforcement to prevent user privacy violations during the incident reportings. A working proof-of-concept prototype of Eyephone is implemented. Our results show that Eyephone allows secure and effective use of smartphones for real-time situational awareness of our national critical infrastructures.
Are SonarQube Rules Inducing Bugs?
Venue: arXiv cs.SE 2019
Year: 2019

Background. The popularity of tools for analyzing Technical Debt, and particularly the popularity of SonarQube, is increasing rapidly. SonarQube proposes a set of coding rules, which represent something wrong in the code that will soon be reflected in a fault or will increase maintenance effort. However, our local companies were not confident in the usefulness of the rules proposed by SonarQube and contracted us to investigate the fault-proneness of these rules. Objective. In this work we aim at understanding which SonarQube rules are actually fault-prone and to understand which machine learning models can be adopted to accurately identify fault-prone rules. Method. We designed and conducted an empirical study on 21 well-known mature open-source projects. We applied the SZZ algorithm to label the fault-inducing commits. We analyzed the fault-proneness by comparing the classification power of seven machine learning models. Result. Among the 202 rules defined for Java by SonarQube, only 25 can be considered to have relatively low fault-proneness. Moreover, violations considered as "bugs" by SonarQube were generally not fault-prone and, consequently, the fault-prediction power of the model proposed by SonarQube is extremely low. Conclusion. The rules applied by SonarQube for calculating technical debt should be thoroughly investigated and their harmfulness needs to be further confirmed. Therefore, companies should carefully consider which rules they really need to apply, especially if their goal is to reduce fault-proneness.
The Semantics of Rank Polymorphism
Venue: arXiv cs.PL 2019
Year: 2019

Iverson's APL and its descendants (such as J, K and FISh) are examples of the family of "rank-polymorphic" programming languages. The principal control mechanism of such languages is the general lifting of functions that operate on arrays of rank (or dimension) $r$ to operate on arrays of any higher rank $r' > r$. We present a core, functional language, Remora, that captures this mechanism, and develop both a formal, dynamic semantics for the language, and an accompanying static, rank-polymorphic type system for the language. Critically, the static semantics captures the shape-based lifting mechanism of the language. We establish the usual progress and preservation properties for the type system, showing that it is sound, which means that "array shape" errors cannot occur at run time in a well-typed program. Our type system uses dependent types, including an existential type abstraction which permits programs to operate on arrays whose shape or rank is computed dynamically; however, it is restricted enough to permit static type checking. The rank-polymorphic computational paradigm is unusual in that the types of arguments affect the dynamic execution of the program -- they are what drive the rank-polymorphic distribution of a function across arrays of higher rank. To highlight this property, we additionally present a dynamic semantics for a partially erased variant of the fully-typed language and show that a computation performed with a fully-typed term stays in lock step with the computation performed with its partially erased term. The residual types thus precisely characterise the type information that is needed by the dynamic semantics, a property useful for the (eventual) construction of efficient compilers for rank-polymorphic languages.
Geodesic Centroidal Voronoi Tessellations: Theories, Algorithms and Applications
Venue: arXiv cs.GR 2019
Year: 2019

Nowadays, big data of digital media (including images, videos and 3D graphical models) are frequently modeled as low-dimensional manifold meshes embedded in a high-dimensional feature space. In this paper, we summarized our recent work on geodesic centroidal Voronoi tessellations(GCVTs), which are intrinsic geometric structures on manifold meshes. We show that GCVT can find a widely range of interesting applications in computer vision and graphics, due to the efficiency of search, location and indexing inherent in these intrinsic geometric structures. Then we present the challenging issues of how to build the combinatorial structures of GCVTs and establish their time and space complexities, including both theoretical and algorithmic results.
Polar Codes with Memory
Venue: arXiv cs.IT 2019
Year: 2019

Polar codes with memory (PCM) are proposed in this paper: a pair of consecutive code blocks containing a controlled number of mutual information bits. The shared mutual information bits of the succeeded block can help the failed block to recover. The underlying polar codes can employ any decoding scheme such as the successive cancellation (SC) decoding (PCM-SC), the belief propagation (BP) decoding (PCM-BP), and the successive cancellation list (SCL) decoding (PCM-SCL). The analysis shows that the packet error rate (PER) of PCM decreases to the order of PER squared while maintaining the same complexity as the underlying polar codes. Simulation results indicate that for PCM-SC, the PER is comparable to (less than 0.3 dB) the stand-alone SCL decoding with two lists for the block length $N=256$. The PER of PCM-SCL with $L$ lists can match that of the stand-alone SCL decoding with $2L$ lists. Two hardware decoders for PCM are also implemented: the in-serial (IS) decoder and the low-latency interleaved (LLI) decoder. For $N=256$, synthesis results show that in the worst case, the latency of the PCM LLI decoder is only $16.1\%$ of the adaptive SCL decoder with $L=2$, while the throughput is improved by 13 times compared to it.
Learning to Link
Venue: arXiv cs.LG 2019
Year: 2019

Clustering is an important part of many modern data analysis pipelines, including network analysis and data retrieval. There are many different clustering algorithms developed by various communities, and it is often not clear which algorithm will give the best performance on a specific clustering task. Similarly, we often have multiple ways to measure distances between data points, and the best clustering performance might require a non-trivial combination of those metrics. In this work, we study data-driven algorithm selection and metric learning for clustering problems, where the goal is to simultaneously learn the best algorithm and metric for a specific application. The family of clustering algorithms we consider is parameterized linkage based procedures that includes single and complete linkage. The family of distance functions we learn over are convex combinations of base distance functions. We design efficient learning algorithms which receive samples from an application-specific distribution over clustering instances and simultaneously learn both a near-optimal distance and clustering algorithm from these classes. We also carry out a comprehensive empirical evaluation of our techniques showing that they can lead to significantly improved clustering performance.
A Formal Approach for Efficient Navigation Management of Hybrid Electric Vehicles on Long Trips
Venue: arXiv cs.LO 2019
Year: 2019

Plug-in Hybrid Electric Vehicles (PHEVs) are gaining popularity due to their economic efficiency as well as their contribution to green management. PHEVs allow the driver to use electric power exclusively for driving and then switch to gasoline as needed. The more gasoline a vehicle uses, the higher cost is required for the trip. However, a PHEV cannot last for a long period on stored electricity without being recharged. Thus, it needs frequent recharging compared to traditional gasoline-powered vehicles. Moreover, the battery recharging time is usually long, which leads to longer delays on a trip. Therefore, it is necessary to provide a flexible navigation management scheme along with an efficient recharging schedule, which allows the driver to choose an optimal route based on the fuel-cost and time-to-destination constraints. In this paper, we present a formal model to solve this PHEV navigation management problem. The model is solved to provide a driver with a comprehensive routing plan including the potential recharging and refueling points that satisfy the given requirements, particularly the maximum fuel cost and the maximum trip time. In addition, we propose a price-based navigation control technique to achieve better load balance for the traffic system. Evaluation results show that the proposed formal models can be solved efficiently even with large road networks.
Spatio-thermal depth correction of RGB-D sensors based on Gaussian Processes in real-time
Venue: arXiv cs.CV 2019
Year: 2019

Commodity RGB-D sensors capture color images along with dense pixel-wise depth information in real-time. Typical RGB-D sensors are provided with a factory calibration and exhibit erratic depth readings due to coarse calibration values, ageing and thermal influence effects. This limits their applicability in computer vision and robotics. We propose a novel method to accurately calibrate depth considering spatial and thermal influences jointly. Our work is based on Gaussian Process Regression in a four dimensional Cartesian and thermal domain. We propose to leverage modern GPUs for dense depth map correction in real-time. For reproducibility we make our dataset and source code publicly available.
Learning to Approximate Directional Fields Defined over 2D Planes
Venue: arXiv cs.CV 2019
Year: 2019

Reconstruction of directional fields is a need in many geometry processing tasks, such as image tracing, extraction of 3D geometric features, and finding principal surface directions. A common approach to the construction of directional fields from data relies on complex optimization procedures, which are usually poorly formalizable, require a considerable computational effort, and do not transfer across applications. In this work, we propose a deep learning-based approach and study the expressive power and generalization ability.