OpenRaiser/Intern-Atlas huggingface dataset:
Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity
Venue: arXiv cs.DS 2020
Year: 2020

The terminal backup problems (Anshelevich and Karagiozova (2011)) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga (2016) gave a $4/3$-approximation algorithm based on LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in $O(m\log (nUA)\cdot \operatorname{MF}(kn,m+k^2n))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $A$ is the maximum edge-cost, $U$ is the maximum edge-capacity, and $\operatorname{MF}(n',m')$ is the time complexity of a max-flow algorithm in a network with $n'$ nodes and $m'$ edges. The algorithm implies that the $4/3$-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, called a separately-capacitated multiflow. We show a min-max theorem which extends Lovász-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem.
Country-wide mobility changes observed using mobile phone data during COVID-19 pandemic
Venue: arXiv cs.CY 2020
Year: 2020

In March 2020, the Austrian government introduced a widespread lock-down in response to the COVID-19 pandemic. Based on subjective impressions and anecdotal evidence, Austrian public and private life came to a sudden halt. Here we assess the effect of the lock-down quantitatively for all regions in Austria and present an analysis of daily changes of human mobility throughout Austria using near-real-time anonymized mobile phone data. We describe an efficient data aggregation pipeline and analyze the mobility by quantifying mobile-phone traffic at specific point of interest (POI), analyzing individual trajectories and investigating the cluster structure of the origin-destination graph. We found a reduction of commuters at Viennese metro stations of over 80\% and the number of devices with a radius of gyration of less than 500 m almost doubled. The results of studying crowd-movement behavior highlight considerable changes in the structure of mobility networks, revealed by a higher modularity and an increase from 12 to 20 detected communities. We demonstrate the relevance of mobility data for epidemiological studies by showing a significant correlation of the outflow from the town of Ischgl (an early COVID-19 hotspot) and the reported COVID-19 cases with an 8-day time lag. This research indicates that mobile phone usage data permits the moment-by-moment quantification of mobility behavior for a whole country. We emphasize the need to improve the availability of such data in anonymized form to empower rapid response to combat COVID-19 and future pandemics.
Learn to Talk via Proactive Knowledge Transfer
Venue: arXiv cs.LG 2020
Year: 2020

Knowledge Transfer has been applied in solving a wide variety of problems. For example, knowledge can be transferred between tasks (e.g., learning to handle novel situations by leveraging prior knowledge) or between agents (e.g., learning from others without direct experience). Without loss of generality, we relate knowledge transfer to KL-divergence minimization, i.e., matching the (belief) distributions of learners and teachers. The equivalence gives us a new perspective in understanding variants of the KL-divergence by looking at how learners structure their interaction with teachers in order to acquire knowledge. In this paper, we provide an in-depth analysis of KL-divergence minimization in Forward and Backward orders, which shows that learners are reinforced via on-policy learning in Backward. In contrast, learners are supervised in Forward. Moreover, our analysis is gradient-based, so it can be generalized to arbitrary tasks and help to decide which order to minimize given the property of the task. By replacing Forward with Backward in Knowledge Distillation, we observed +0.7-1.1 BLEU gains on the WMT'17 De-En and IWSLT'15 Th-En machine translation tasks.
Robust Vision Challenge 2020 -- 1st Place Report for Panoptic Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

In this technical report, we present key details of our winning panoptic segmentation architecture EffPS_b1bs4_RVC. Our network is a lightweight version of our state-of-the-art EfficientPS architecture that consists of our proposed shared backbone with a modified EfficientNet-B5 model as the encoder, followed by the 2-way FPN to learn semantically rich multi-scale features. It consists of two task-specific heads, a modified Mask R-CNN instance head and our novel semantic segmentation head that processes features of different scales with specialized modules for coherent feature refinement. Finally, our proposed panoptic fusion module adaptively fuses logits from each of the heads to yield the panoptic segmentation output. The Robust Vision Challenge 2020 benchmarking results show that our model is ranked #1 on Microsoft COCO, VIPER and WildDash, and is ranked #2 on Cityscapes and Mapillary Vistas, thereby achieving the overall rank #1 for the panoptic segmentation task.
Predicting Helpfulness of Online Reviews
Venue: arXiv cs.CL 2020
Year: 2020

E-commerce dominates a large part of the world's economy with many websites dedicated to online selling products. The vast majority of e-commerce websites provide their customers with the ability to express their opinions about the products/services they purchase. These feedback in the form of reviews represent a rich source of information about the users' experiences and level of satisfaction, which is of great benefit to both the producer and the consumer. However, not all of these reviews are helpful/useful. The traditional way of determining the helpfulness of a review is through the feedback from human users. However, such a method does not necessarily cover all reviews. Moreover, it has many issues like bias, high cost, etc. Thus, there is a need to automate this process. This paper presents a set of machine learning (ML) models to predict the helpfulness online reviews. Mainly, three approaches are used: a supervised learning approach (using ML as well as deep learning (DL) models), a semi-supervised approach (that combines DL models with word embeddings), and pre-trained word embedding models that uses transfer learning (TL). The latter two approaches are among the unique aspects of this paper as they follow the recent trend of utilizing unlabeled text. The results show that the proposed DL approaches have superiority over the traditional existing ones. Moreover, the semi-supervised has a remarkable performance compared with the other ones.
Covariance-Based Cooperative Activity Detection for Massive Grant-Free Random Access
Venue: arXiv cs.IT 2020
Year: 2020

This paper designs a cooperative activity detection framework for massive grant-free random access in the sixth-generation (6G) cell-free wireless networks based on the covariance of the received signals at the access points (APs). In particular, multiple APs cooperatively detect the device activity by only exchanging the low-dimensional intermediate local information with their neighbors. The cooperative activity detection problem is non-smooth and the unknown variables are coupled with each other for which conventional approaches are inapplicable. Therefore, this paper proposes a covariance-based algorithm by exploiting the sparsity-promoting and similarity-promoting terms of the device state vectors among neighboring APs. An approximate splitting approach is proposed based on the proximal gradient method for solving the formulated problem. Simulation results show that the proposed algorithm is efficient for large-scale activity detection problems while requires shorter pilot sequences compared with the state-of-art algorithms in achieving the same system performance.
Congenial Differential Privacy under Mandated Disclosure
Venue: arXiv cs.CR 2020
Year: 2020

Differentially private data releases are often required to satisfy a set of external constraints that reflect the legal, ethical, and logical mandates to which the data curator is obligated. The enforcement of constraints, when treated as post-processing, adds an extra phase in the production of privatized data. It is well understood in the theory of multi-phase processing that congeniality, a form of procedural compatibility between phases, is a prerequisite for the end users to straightforwardly obtain statistically valid results. Congenial differential privacy is theoretically principled, which facilitates transparency and intelligibility of the mechanism that would otherwise be undermined by ad-hoc post-processing procedures. We advocate for the systematic integration of mandated disclosure into the design of the privacy mechanism via standard probabilistic conditioning on the invariant margins. Conditioning automatically renders congeniality because any extra post-processing phase becomes unnecessary. We provide both initial theoretical guarantees and a Markov chain algorithm for our proposal. We also discuss intriguing theoretical issues that arise in comparing congenital differential privacy and optimization-based post-processing, as well as directions for further research.
Monocular Reconstruction of Neural Face Reflectance Fields
Venue: arXiv cs.CV 2020
Year: 2020

The reflectance field of a face describes the reflectance properties responsible for complex lighting effects including diffuse, specular, inter-reflection and self shadowing. Most existing methods for estimating the face reflectance from a monocular image assume faces to be diffuse with very few approaches adding a specular component. This still leaves out important perceptual aspects of reflectance as higher-order global illumination effects and self-shadowing are not modeled. We present a new neural representation for face reflectance where we can estimate all components of the reflectance responsible for the final appearance from a single monocular image. Instead of modeling each component of the reflectance separately using parametric models, our neural representation allows us to generate a basis set of faces in a geometric deformation-invariant space, parameterized by the input light direction, viewpoint and face geometry. We learn to reconstruct this reflectance field of a face just from a monocular image, which can be used to render the face from any viewpoint in any light condition. Our method is trained on a light-stage training dataset, which captures 300 people illuminated with 150 light conditions from 8 viewpoints. We show that our method outperforms existing monocular reflectance reconstruction methods, in terms of photorealism due to better capturing of physical premitives, such as sub-surface scattering, specularities, self-shadows and other higher-order effects.
Information Constrained Optimal Transport: From Talagrand, to Marton, to Cover
Venue: arXiv cs.IT 2020
Year: 2020

The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand's celebrated transportation cost inequality. Following Marton's approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.
Extending Partial Orthogonal Drawings
Venue: arXiv cs.DM 2020
Year: 2020

We study the planar orthogonal drawing style within the framework of partial representation extension. Let $(G,H,Γ_H )$ be a partial orthogonal drawing, i.e., G is a graph, $H\subseteq G$ is a subgraph and $Γ_H$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing $Γ_G$ of $G$ that extends $Γ_H$ can be tested in linear time. If such a drawing exists, then there also is one that uses $O(|V(H)|)$ bends per edge. On the other hand, we show that it is NP-complete to find an extension that minimizes the number of bends or has a fixed number of bends per edge.
Cross-lingual Semantic Role Labeling with Model Transfer
Venue: arXiv cs.CL 2020
Year: 2020

Prior studies show that cross-lingual semantic role labeling (SRL) can be achieved by model transfer under the help of universal features. In this paper, we fill the gap of cross-lingual SRL by proposing an end-to-end SRL model that incorporates a variety of universal features and transfer methods. We study both the bilingual transfer and multi-source transfer, under gold or machine-generated syntactic inputs, pre-trained high-order abstract features, and contextualized multilingual word representations. Experimental results on the Universal Proposition Bank corpus indicate that performances of the cross-lingual SRL can vary by leveraging different cross-lingual features. In addition, whether the features are gold-standard also has an impact on performances. Precisely, we find that gold syntax features are much more crucial for cross-lingual SRL, compared with the automatically-generated ones. Moreover, universal dependency structure features are able to give the best help, and both pre-trained high-order features and contextualized word representations can further bring significant improvements.
An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings
Venue: arXiv cs.CG 2020
Year: 2020

An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.
Combinatorial diversity metrics for the analysis of policy processes
Venue: arXiv cs.AI 2020
Year: 2020

We present several completely general diversity metrics to quantify the problem-solving capacity of any public policy decision making process. This is performed by modelling the policy process using a declarative process paradigm in conjunction with constraints modelled by expressions in linear temporal logic. We introduce a class of traces, called first-passage traces, to represent the different executions of the declarative processes. Heuristics of what properties a diversity measure of such processes ought to satisfy are used to derive two different metrics for these processes in terms of the set of first-passage traces. These metrics turn out to have formulations in terms of the entropies of two different random variables on the set of traces of the processes. In addition, we introduce a measure of `goodness' whereby a trace is termed {\it good} if it satisfies some prescribed linear temporal logic expression. This allows for comparisons of policy processes with respect to the prescribed notion of `goodness'.
Transferring Inter-Class Correlation
Venue: arXiv cs.CV 2020
Year: 2020

The Teacher-Student (T-S) framework is widely utilized in the classification tasks, through which the performance of one neural network (the student) can be improved by transferring knowledge from another trained neural network (the teacher). Since the transferring knowledge is related to the network capacities and structures between the teacher and the student, how to define efficient knowledge remains an open question. To address this issue, we design a novel transferring knowledge, the Self-Attention based Inter-Class Correlation (ICC) map in the output layer, and propose our T-S framework, Inter-Class Correlation Transfer (ICCT).
FOCAL: A Forgery Localization Framework based on Video Coding Self-Consistency
Venue: arXiv cs.CV 2020
Year: 2020

Forgery operations on video contents are nowadays within the reach of anyone, thanks to the availability of powerful and user-friendly editing software. Integrity verification and authentication of videos represent a major interest in both journalism (e.g., fake news debunking) and legal environments dealing with digital evidence (e.g., a court of law). While several strategies and different forensics traces have been proposed in recent years, latest solutions aim at increasing the accuracy by combining multiple detectors and features. This paper presents a video forgery localization framework that verifies the self-consistency of coding traces between and within video frames, by fusing the information derived from a set of independent feature descriptors. The feature extraction step is carried out by means of an explainable convolutional neural network architecture, specifically designed to look for and classify coding artifacts. The overall framework was validated in two typical forgery scenarios: temporal and spatial splicing. Experimental results show an improvement to the state-of-the-art on temporal splicing localization and also promising performance in the newly tackled case of spatial splicing, on both synthetic and real-world videos.
Prediction of ICD Codes with Clinical BERT Embeddings and Text Augmentation with Label Balancing using MIMIC-III
Venue: arXiv cs.CL 2020
Year: 2020

This paper achieves state of the art results for the ICD code prediction task using the MIMIC-III dataset. This was achieved through the use of Clinical BERT (Alsentzer et al., 2019). embeddings and text augmentation and label balancing to improve F1 scores for both ICD Chapter as well as ICD disease codes. We attribute the improved performance mainly to the use of novel text augmentation to shuffle the order of sentences during training. In comparison to the Top-32 ICD code prediction (Keyang Xu, et. al.) with an F1 score of 0.76, we achieve a final F1 score of 0.75 but on a total of the top 50 ICD codes.
LMSCNet: Lightweight Multiscale 3D Semantic Completion
Venue: arXiv cs.CV 2020
Year: 2020

We introduce a new approach for multiscale 3Dsemantic scene completion from voxelized sparse 3D LiDAR scans. As opposed to the literature, we use a 2D UNet backbone with comprehensive multiscale skip connections to enhance feature flow, along with 3D segmentation heads. On the SemanticKITTI benchmark, our method performs on par on semantic completion and better on occupancy completion than all other published methods -- while being significantly lighter and faster. As such it provides a great performance/speed trade-off for mobile-robotics applications. The ablation studies demonstrate our method is robust to lower density inputs, and that it enables very high speed semantic completion at the coarsest level. Our code is available at https://github.com/cv-rits/LMSCNet.
CRAC: Checkpoint-Restart Architecture for CUDA with Streams and UVM
Venue: arXiv cs.DC 2020
Year: 2020

The share of the top 500 supercomputers with NVIDIA GPUs is now over 25% and continues to grow. While fault tolerance is a critical issue for supercomputing, there does not currently exist an efficient, scalable solution for CUDA applications on NVIDIA GPUs. CRAC (Checkpoint-Restart Architecture for CUDA) is new checkpoint-restart solution for fault tolerance that supports the full range of CUDA applications. CRAC combines: low runtime overhead (approximately 1% or less); fast checkpoint-restart; support for scalable CUDA streams (for efficient usage of all of the thousands of GPU cores); and support for the full features of Unified Virtual Memory (eliminating the programmer's burden of migrating memory between device and host). CRAC achieves its flexible architecture by segregating application code (checkpointed) and its external GPU communication via non-reentrant CUDA libraries (not checkpointed) within a single process's memory. This eliminates the high overhead of inter-process communication in earlier approaches, and has fewer limitations.
ALIGN: A System for Automating Analog Layout
Venue: arXiv cs.AR 2020
Year: 2020

ALIGN ("Analog Layout, Intelligently Generated from Netlists") is an open-source automatic layout generation flow for analog circuits. ALIGN translates an input SPICE netlist to an output GDSII layout, specific to a given technology, as specified by a set of design rules. The flow first automatically detects hierarchies in the circuit netlist and translates layout synthesis to a problem of hierarchical block assembly. At the lowest level, parameterized cells are generated using an abstraction of the design rules; these blocks are then assembled under geometric and electrical constraints to build the circuit layout. ALIGN has been applied to generate layouts for a diverse set of analog circuit families: low frequency analog blocks, wireline circuits, wireless circuits, and power delivery circuits.
Widely Reused and Shared, Infrequently Updated, and Sometimes Inherited: A Holistic View of PIN Authentication in Digital Lives and Beyond
Venue: arXiv cs.HC 2020
Year: 2020

Personal Identification Numbers (PINs) are widely used as an access control mechanism for digital assets (e.g., smartphones), financial assets (e.g., ATM cards), and physical assets (e.g., locks for garage doors or homes). Using semi-structured interviews (n=35), participants reported on PIN usage for different types of assets, including how users choose, share, inherit, and reuse PINs, as well as behaviour following the compromise of a PIN. We find that memorability is the most important criterion when choosing a PIN, more so than security or concerns of reuse. Updating or changing a PIN is very uncommon, even when a PIN is compromised. Participants reported sharing PINs for one type of asset with acquaintances but inadvertently reused them for other assets, thereby subjecting themselves to potential risks. Participants also reported using PINs originally set by previous homeowners for physical devices (e.g., alarm or keypad door entry systems). While aware of the risks of not updating PINs, this did not always deter participants from using inherited PINs, as they were often missing instructions on how to update them. %While aware of the risks of not updating PINs, participants continued using these PINs, as they were often missing instructions on how to update them.Given the expected increase in PIN-protected assets (e.g., loyalty cards, smart locks, and web apps), we provide suggestions and future research directions to better support users with multiple digital and non-digital assets and more secure human-device interaction when utilizing PINs.