OpenRaiser/Intern-Atlas huggingface dataset:
Storing and Querying Large-Scale Spatio-Temporal Graphs with High-Throughput Edge Insertions
Venue: arXiv cs.DC 2020
Year: 2020

Real-world graphs often contain spatio-temporal information and evolve over time. Compared with static graphs, spatio-temporal graphs have very different characteristics, presenting more significant challenges in data volume, data velocity, and query processing. In this paper, we describe three representative applications to understand the features of spatio-temporal graphs. Based on the commonalities of the applications, we define a formal spatio-temporal graph model, where a graph consists of location vertices, object vertices, and event edges. Then we discuss a set of design goals to meet the requirements of the applications: (i) supporting up to 10 billion object vertices, 10 million location vertices, and 100 trillion edges in the graph, (ii) supporting up to 1 trillion new edges that are streamed in daily, and (iii) minimizing cross-machine communication for query processing. We propose and evaluate PAST, a framework for efficient PArtitioning and query processing of Spatio-Temporal graphs. Experimental results show that PAST successfully achieves the above goals. It improves query performance by orders of magnitude compared with state-of-the-art solutions, including JanusGraph, Greenplum, Spark and ST-Hadoop.
Enhanced Channel Estimation in Massive MIMO via Coordinated Pilot Design
Venue: arXiv cs.IT 2020
Year: 2020

Pilot contamination is a limiting factor in multicell massive multiple-input multiple-output (MIMO) systems because it can severely impair channel estimation. Prior works have suggested coordinating pilot design across cells in order to reduce the channel estimation error caused by pilot contamination. In this paper, we propose a method for coordinated pilot design using fractional programming to minimize the weighted mean squared-error (MSE) in channel estimation. In particular, we apply the recently proposed quadratic transform to the MSE expression which allows the effect of pilot contamination to be decoupled. The resulting problem reformulation enables the pilots to be optimized in closed form if they can be designed arbitrarily. When the pilots are restricted to a given set of orthogonal sequences, pilot optimization reduces to an assignment problem which can be solved by weighted bipartite matching. Furthermore, we consider the max-min fairness of data rates with orthogonal pilots and obtain an extension of the proposed method to correlated Rayleigh fading. Finally, simulations demonstrate the advantage of the proposed (orthogonal and nonorthogonal) pilot designs as compared with state-of-the-art methods in combating pilot contamination.
Machine Learning Based Analysis of Finnish World War II Photographers
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we demonstrate the benefits of using state-of-the-art machine learning methods in the analysis of historical photo archives. Specifically, we analyze prominent Finnish World War II photographers, who have captured high numbers of photographs in the publicly available Finnish Wartime Photograph Archive, which contains 160,000 photographs from Finnish Winter, Continuation, and Lapland Wars captures in 1939-1945. We were able to find some special characteristics for different photographers in terms of their typical photo content and framing (e.g., close-ups vs. overall shots, number of people). Furthermore, we managed to train a neural network that can successfully recognize the photographer from some of the photos, which shows that such photos are indeed characteristic for certain photographers. We further analyzed the similarities and differences between the photographers using the features extracted from the photographer classifier network. We make our annotations and analysis pipeline publicly available, in an effort to introduce this new research problem to the machine learning and computer vision communities and facilitate future research in historical and societal studies over the photo archives.
Attention Augmented Convolutional Networks
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional networks have been the paradigm of choice in many computer vision applications. The convolution operation however has a significant weakness in that it only operates on a local neighborhood, thus missing global information. Self-attention, on the other hand, has emerged as a recent advance to capture long range interactions, but has mostly been applied to sequence modeling and generative modeling tasks. In this paper, we consider the use of self-attention for discriminative visual tasks as an alternative to convolutions. We introduce a novel two-dimensional relative self-attention mechanism that proves competitive in replacing convolutions as a stand-alone computational primitive for image classification. We find in control experiments that the best results are obtained when combining both convolutions and self-attention. We therefore propose to augment convolutional operators with this self-attention mechanism by concatenating convolutional feature maps with a set of feature maps produced via self-attention. Extensive experiments show that Attention Augmentation leads to consistent improvements in image classification on ImageNet and object detection on COCO across many different models and scales, including ResNets and a state-of-the art mobile constrained network, while keeping the number of parameters similar. In particular, our method achieves a $1.3\%$ top-1 accuracy improvement on ImageNet classification over a ResNet50 baseline and outperforms other attention mechanisms for images such as Squeeze-and-Excitation. It also achieves an improvement of 1.4 mAP in COCO Object Detection on top of a RetinaNet baseline.
Foundations, Properties, and Security Applications of Puzzles: A Survey
Venue: arXiv cs.CR 2020
Year: 2020

Cryptographic algorithms have been used not only to create robust ciphertexts but also to generate cryptograms that, contrary to the classic goal of cryptography, are meant to be broken. These cryptograms, generally called puzzles, require the use of a certain amount of resources to be solved, hence introducing a cost that is often regarded as a time delay---though it could involve other metrics as well, such as bandwidth. These powerful features have made puzzles the core of many security protocols, acquiring increasing importance in the IT security landscape. The concept of a puzzle has subsequently been extended to other types of schemes that do not use cryptographic functions, such as CAPTCHAs, which are used to discriminate humans from machines. Overall, puzzles have experienced a renewed interest with the advent of Bitcoin, which uses a CPU-intensive puzzle as proof of work. In this paper, we provide a comprehensive study of the most important puzzle construction schemes available in the literature, categorizing them according to several attributes, such as resource type, verification type, and applications. We have redefined the term puzzle by collecting and integrating the scattered notions used in different works, to cover all the existing applications. Moreover, we provide an overview of the possible applications, identifying key requirements and different design approaches. Finally, we highlight the features and limitations of each approach, providing a useful guide for the future development of new puzzle schemes.
Multicast Communications in Tree Networks with Heterogeneous Capacity Constraints
Venue: arXiv cs.DS 2020
Year: 2020

A widely studied problem in communication networks is that of finding the maximum number of communication requests that can be scheduled concurrently, subject to node and/or link capacity constraints. In this paper, we consider the problem of finding the largest number of multicast communication requests that can be serviced simultaneously by a network of tree topology, subject to heterogeneous capacity constraints. This problem generalizes the following two problems studied in the literature: a) the problem of finding a largest induced $k$-colorable subgraph of a chordal graph, b) the maximum multi-commodity flow problem in tree networks. The problem is already known to be NP-hard and to admit a $c$-approximation ($c \approx 1.58$) in the case of homogeneous capacity constraints. We first show that the problem is much harder to approximate in the heterogeneous case. We then use a generalization of a classical algorithm to obtain an $M$-approximation where $M$ is the maximum number of leaves of the subtrees representing the multicast communications. Surprisingly, the same algorithm, though in various disguises, is used in the literature at least four times to solve related problems (though the analysis is different). The special case of the problem where instances are restricted to unicast communications in a star topology network is known to be polynomial-time solvable. We extend this result and show that the problem can be solved in polynomial time for a set of paths in a tree that share a common vertex.
Saddlepoint Approximations for Short-Packet Wireless Communications
Venue: arXiv cs.IT 2020
Year: 2020

In recent years, the derivation of nonasymptotic converse and achievability bounds on the maximum coding rate as a function of the error probability and blocklength has gained attention in the information theory literature. While these bounds are accurate for many scenarios of interest, they need to be evaluated numerically for most wireless channels of practical interest, and their evaluation is computationally demanding. This paper presents saddlepoint approximations of state-of-the-art converse and achievability bounds for noncoherent, single-antenna, Rayleigh block-fading channels. These approximations can be calculated efficiently and are shown to be accurate for SNR values as small as 0 dB and blocklengths of 168 channel uses or more.
Influences of Human Demographics, Brand Familiarity and Security Backgrounds on Homograph Recognition
Venue: arXiv cs.CR 2020
Year: 2020

Homograph attack is a way that attackers deceive victims about which website domain name they are communicating with by exploiting the fact that many characters look alike. The attack becomes serious and is raising broad attention when recently many brand domains have been attacked such as Apple Inc., Adobe Inc., Lloyds Bank, etc. We first design a survey of human demographics, brand familiarity, and security backgrounds and apply it to 2,067 participants. We build a regression model to study which factors affect participants' ability in recognizing homograph domains. We find that for different levels of visual similarity, the participants exhibit different abilities. 13.95% of participants can recognize non-homographs while 16.60% of participants can recognize homographs whose the visual similarity with the target brand domains is under 99.9%; but when the similarity increases to 99.9%, the number of participants who can recognize homographs significantly drops down to only 0.19%; and for the homographs with 100% of visual similarity, there is no way for the participants to recognize. We also find that female participants tend to recognize homographs better the male but male participants tend to able to recognize non-homographs better than females. Security knowledge is a significant factor affecting both homographs and non-homographs; surprisingly, people who have strong security knowledge tend to be able to recognize homographs but not non-homographs. Furthermore, people who work or are educated in computer science or computer engineering do not appear as a factor affecting the ability in recognizing homographs; however, interestingly, right after they are explained about the homograph attack, people who work or are educated in computer science or computer engineering are the ones who can capture the situation the most quickly.
3D Dynamic Point Cloud Inpainting via Temporal Consistency on Graphs
Venue: arXiv cs.GR 2020
Year: 2020

With the development of 3D laser scanning techniques and depth sensors, 3D dynamic point clouds have attracted increasing attention as a representation of 3D objects in motion, enabling various applications such as 3D immersive tele-presence, gaming and navigation. However, dynamic point clouds usually exhibit holes of missing data, mainly due to the fast motion, the limitation of acquisition and complicated structure. Leveraging on graph signal processing tools, we represent irregular point clouds on graphs and propose a novel inpainting method exploiting both intra-frame self-similarity and inter-frame consistency in 3D dynamic point clouds. Specifically, for each missing region in every frame of the point cloud sequence, we search for its self-similar regions in the current frame and corresponding ones in adjacent frames as references. Then we formulate dynamic point cloud inpainting as an optimization problem based on the two types of references, which is regularized by a graph-signal smoothness prior. Experimental results show the proposed approach outperforms three competing methods significantly, both in objective and subjective quality.
PHANTOM: Curating GitHub for engineered software projects using time-series clustering
Venue: arXiv cs.SE 2020
Year: 2020

Context: Within the field of Mining Software Repositories, there are numerous methods employed to filter datasets in order to avoid analysing low-quality projects. Unfortunately, the existing filtering methods have not kept up with the growth of existing data sources, such as GitHub, and researchers often rely on quick and dirty techniques to curate datasets. Objective: The objective of this study is to develop a method capable of filtering large quantities of software projects in a resource-efficient way. Method: This study follows the Design Science Research (DSR) methodology. The proposed method, PHANTOM, extracts five measures from Git logs. Each measure is transformed into a time-series, which is represented as a feature vector for clustering using the k-means algorithm. Results: Using the ground truth from a previous study, PHANTOM was shown to be able to rediscover the ground truth on the training dataset, and was able to identify "engineered" projects with up to 0.87 Precision and 0.94 Recall on the validation dataset. PHANTOM downloaded and processed the metadata of 1,786,601 GitHub repositories in 21.5 days using a single personal computer, which is over 33% faster than the previous study which used a computer cluster of 200 nodes. The possibility of applying the method outside of the open-source community was investigated by curating 100 repositories owned by two companies. Conclusions: It is possible to use an unsupervised approach to identify engineered projects. PHANTOM was shown to be competitive compared to the existing supervised approaches while reducing the hardware requirements by two orders of magnitude.
Stochastic rounding and reduced-precision fixed-point arithmetic for solving neural ordinary differential equations
Venue: arXiv cs.DS 2020
Year: 2020

Although double-precision floating-point arithmetic currently dominates high-performance computing, there is increasing interest in smaller and simpler arithmetic types. The main reasons are potential improvements in energy efficiency and memory footprint and bandwidth. However, simply switching to lower-precision types typically results in increased numerical errors. We investigate approaches to improving the accuracy of reduced-precision fixed-point arithmetic types, using examples in an important domain for numerical computation in neuroscience: the solution of Ordinary Differential Equations (ODEs). The Izhikevich neuron model is used to demonstrate that rounding has an important role in producing accurate spike timings from explicit ODE solution algorithms. In particular, fixed-point arithmetic with stochastic rounding consistently results in smaller errors compared to single precision floating-point and fixed-point arithmetic with round-to-nearest across a range of neuron behaviours and ODE solvers. A computationally much cheaper alternative is also investigated, inspired by the concept of dither that is a widely understood mechanism for providing resolution below the least significant bit (LSB) in digital signal processing. These results will have implications for the solution of ODEs in other subject areas, and should also be directly relevant to the huge range of practical problems that are represented by Partial Differential Equations (PDEs).
The game semantics of game theory
Venue: arXiv cs.GT 2020
Year: 2020

We use a reformulation of compositional game theory to reunite game theory with game semantics, by viewing an open game as the System and its choice of contexts as the Environment. Specifically, the system is jointly controlled by $n \geq 0$ noncooperative players, each independently optimising a real-valued payoff. The goal of the system is to play a Nash equilibrium, and the goal of the environment is to prevent it. The key to this is the realisation that lenses (from functional programming) form a dialectica category, which have an existing game-semantic interpretation. In the second half of this paper, we apply these ideas to build a compact closed category of `computable open games' by replacing the underlying dialectica category with a wave-style geometry of interaction category, specifically the Int-construction applied to the cartesian monoidal category of directed-complete partial orders.
META-Learning State-based Eligibility Traces for More Sample-Efficient Policy Evaluation
Venue: arXiv cs.LG 2020
Year: 2020

Temporal-Difference (TD) learning is a standard and very successful reinforcement learning approach, at the core of both algorithms that learn the value of a given policy, as well as algorithms which learn how to improve policies. TD-learning with eligibility traces provides a way to boost sample efficiency by temporal credit assignment, i.e. deciding which portion of a reward should be assigned to predecessor states that occurred at different previous times, controlled by a parameter $λ$. However, tuning this parameter can be time-consuming, and not tuning it can lead to inefficient learning. For better sample efficiency of TD-learning, we propose a meta-learning method for adjusting the eligibility trace parameter, in a state-dependent manner. The adaptation is achieved with the help of auxiliary learners that learn distributional information about the update targets online, incurring roughly the same computational complexity per step as the usual value learner. Our approach can be used both in on-policy and off-policy learning. We prove that, under some assumptions, the proposed method improves the overall quality of the update targets, by minimizing the overall target error. This method can be viewed as a plugin to assist prediction with function approximation by meta-learning feature (observation)-based $λ$ online, or even in the control case to assist policy improvement. Our empirical evaluation demonstrates significant performance improvements, as well as improved robustness of the proposed algorithm to learning rate variation.
Non-Stochastic Information Theory
Venue: arXiv cs.IT 2020
Year: 2020

In an effort to develop the foundations for a non-stochastic theory of information, the notion of $δ$-mutual information between uncertain variables is introduced as a generalization of Nair's non-stochastic information functional. Several properties of this new quantity are illustrated, and used to prove a channel coding theorem in a non-stochastic setting. Namely, it is shown that the largest $δ$-mutual information between received and transmitted codewords over $ε$-noise channels equals the $(ε, δ)$-capacity. This notion of capacity generalizes the Kolmogorov $ε$-capacity to packing sets of overlap at most $δ$, and is a variation of a previous definition proposed by one of the authors. Results are then extended to more general noise models, and to non-stochastic, memoryless, stationary channels. Finally, sufficient conditions are established for the factorization of the $δ$-mutual information and to obtain a single letter capacity expression. Compared to previous non-stochastic approaches, the presented theory admits the possibility of decoding errors as in Shannon's probabilistic setting, while retaining a worst-case, non-stochastic character.
Network traffic instability in a two-ring system with automated driving and cooperative merging
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, we characterize the effects of turning and merging maneuvers of connected and/or automated vehicles (CAVs or AVs) on network traffic instability using the macroscopic or network fundamental diagram (MFD or NFD). We revisit the two-ring system from a theoretical perspective and develop an integrated modeling framework consisting of different microscopic traffic models of human-driven vehicles (HVs), AVs, and CAVs. Results suggest that network traffic instability due to turning and merging maneuvers is an intrinsic property of road networks. When the turning probability is low, CAVs do not significantly change the NFD bifurcation, but scatter in both the simulated link fundamental diagrams (FDs) and NFDs reduces leading to higher and more stable network flows. When the turning probability is high, non-cooperative AVs worsen network traffic instability - the NFD undergoes bifurcation long before the critical density is reached. Results highlight the important impact of cooperative merging on network traffic stability when AVs are widely deployed in road networks.
Recommending research articles to consumers of online vaccination information
Venue: arXiv cs.IR 2020
Year: 2020

Online health communications often provide biased interpretations of evidence and have unreliable links to the source research. We tested the feasibility of a tool for matching webpages to their source evidence. From 207,538 eligible vaccination-related PubMed articles, we evaluated several approaches using 3,573 unique links to webpages from Altmetric. We evaluated methods for ranking the source articles for vaccine-related research described on webpages, comparing simple baseline feature representation and dimensionality reduction approaches to those augmented with canonical correlation analysis (CCA). Performance measures included the median rank of the correct source article; the percentage of webpages for which the source article was correctly ranked first (recall@1); and the percentage ranked within the top 50 candidate articles (recall@50). While augmenting baseline methods using CCA generally improved results, no CCA-based approach outperformed a baseline method, which ranked the correct source article first for over one quarter of webpages and in the top 50 for more than half. Tools to help people identify evidence-based sources for the content they access on vaccination-related webpages are potentially feasible and may support the prevention of bias and misrepresentation of research in news and social media.