OpenRaiser/Intern-Atlas huggingface dataset:
An Algorithm for the Exact Treedepth Problem
Venue: arXiv cs.DM 2020
Year: 2020

We present a novel algorithm for the minimum-depth elimination tree problem, which is equivalent to the optimal treedepth decomposition problem. Our algorithm makes use of two cheaply-computed lower bound functions to prune the search tree, along with symmetry-breaking and domination rules. We present an empirical study showing that the algorithm outperforms the current state-of-the-art solver (which is based on a SAT encoding) by orders of magnitude on a range of graph classes.
Robust and Scalable Entity Alignment in Big Data
Venue: arXiv cs.SI 2020
Year: 2020

Entity alignment has always had significant uses within a multitude of diverse scientific fields. In particular, the concept of matching entities across networks has grown in significance in the world of social science as communicative networks such as social media have expanded in scale and popularity. With the advent of big data, there is a growing need to provide analysis on graphs of massive scale. However, with millions of nodes and billions of edges, the idea of alignment between a myriad of graphs of similar scale using features extracted from potentially sparse or incomplete datasets becomes daunting. In this paper we will propose a solution to the issue of large-scale alignments in the form of a multi-step pipeline. Within this pipeline we introduce scalable feature extraction for robust temporal attributes, accompanied by novel and efficient clustering algorithms in order to find groupings of similar nodes across graphs. The features and their clusters are fed into a versatile alignment stage that accurately identifies partner nodes among millions of possible matches. Our results show that the pipeline can process large data sets, achieving efficient runtimes within the memory constraints.
Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions
Venue: arXiv cs.SI 2020
Year: 2020

Algorithms to find optimal alignments among strings, or to find a parsimonious summary of a collection of strings, are well studied in a variety of contexts, addressing a wide range of interesting applications. In this paper, we consider chain letters, which contain a growing sequence of signatories added as the letter propagates. The unusual constellation of features exhibited by chain letters (one-ended growth, divergence, and mutation) make their propagation, and thus the corresponding reconstruction problem, both distinctive and rich. Here, inspired by these chain letters, we formally define the problem of computing an optimal summary of a set of diverging string sequences. From a collection of these sequences of names, with each sequence noisily corresponding to a branch of the unknown tree $T$ representing the letter's true dissemination, can we efficiently and accurately reconstruct a tree $T' \approx T$? In this paper, we give efficient exact algorithms for this summarization problem when the number of sequences is small; for larger sets of sequences, we prove hardness and provide an efficient heuristic algorithm. We evaluate this heuristic on synthetic data sets chosen to emulate real chain letters, showing that our algorithm is competitive with or better than previous approaches, and that it also comes close to finding the true trees in these synthetic datasets.
A Secure Location-based Alert System with Tunable Privacy-Performance Trade-off
Venue: arXiv cs.CR 2020
Year: 2020

Monitoring location updates from mobile users has important applications in many areas, ranging from public safety and national security to social networks and advertising. However, sensitive information can be derived from movement patterns, thus protecting the privacy of mobile users is a major concern. Users may only be willing to disclose their locations when some condition is met, for instance in proximity of a disaster area or an event of interest. Currently, such functionality can be achieved using searchable encryption. Such cryptographic primitives provide provable guarantees for privacy, and allow decryption only when the location satisfies some predicate. Nevertheless, they rely on expensive pairing-based cryptography (PBC), of which direct application to the domain of location updates leads to impractical solutions. We propose secure and efficient techniques for private processing of location updates that complement the use of PBC and lead to significant gains in performance by reducing the amount of required pairing operations. We implement two optimizations that further improve performance: materialization of results to expensive mathematical operations, and parallelization. We also propose an heuristic that brings down the computational overhead through enlarging an alert zone by a small factor (given as system parameter), therefore trading off a small and controlled amount of privacy for significant performance gains. Extensive experimental results show that the proposed techniques significantly improve performance compared to the baseline, and reduce the searchable encryption overhead to a level that is practical in a computing environment with reasonable resources, such as the cloud.
Learning Low-rank Deep Neural Networks via Singular Vector Orthogonality Regularization and Singular Value Sparsification
Venue: arXiv cs.LG 2020
Year: 2020

Modern deep neural networks (DNNs) often require high memory consumption and large computational loads. In order to deploy DNN algorithms efficiently on edge or mobile devices, a series of DNN compression algorithms have been explored, including factorization methods. Factorization methods approximate the weight matrix of a DNN layer with the multiplication of two or multiple low-rank matrices. However, it is hard to measure the ranks of DNN layers during the training process. Previous works mainly induce low-rank through implicit approximations or via costly singular value decomposition (SVD) process on every training step. The former approach usually induces a high accuracy loss while the latter has a low efficiency. In this work, we propose SVD training, the first method to explicitly achieve low-rank DNNs during training without applying SVD on every step. SVD training first decomposes each layer into the form of its full-rank SVD, then performs training directly on the decomposed weights. We add orthogonality regularization to the singular vectors, which ensure the valid form of SVD and avoid gradient vanishing/exploding. Low-rank is encouraged by applying sparsity-inducing regularizers on the singular values of each layer. Singular value pruning is applied at the end to explicitly reach a low-rank model. We empirically show that SVD training can significantly reduce the rank of DNN layers and achieve higher reduction on computation load under the same accuracy, comparing to not only previous factorization methods but also state-of-the-art filter pruning methods.
Developable B-spline surface generation from control rulings
Venue: arXiv cs.GR 2020
Year: 2020

An intuitive design method is proposed for generating developable ruled B-spline surfaces from a sequence of straight line segments indicating the surface shape. The first and last line segments are enforced to be the head and tail ruling lines of the resulting surface while the interior lines are required to approximate rulings on the resulting surface as much as possible. This manner of developable surface design is conceptually similar to the popular way of the freeform curve and surface design in the CAD community, observing that a developable ruled surface is a single parameter family of straight lines. This new design mode of the developable surface also provides more flexibility than the widely employed way of developable surface design from two boundary curves of the surface. The problem is treated by numerical optimization methods with which a particular level of distance error is allowed. We thus provide an effective tool for creating surfaces with a high degree of developability when the input control rulings do not lie in exact developable surfaces. We consider this ability as the superiority over analytical methods in that it can deal with arbitrary design inputs and find practically useful results.
Adaptation of a Lexical Organization for Social Engineering Detection and Response Generation
Venue: arXiv cs.CL 2020
Year: 2020

We present a paradigm for extensible lexicon development based on Lexical Conceptual Structure to support social engineering detection and response generation. We leverage the central notions of ask (elicitation of behaviors such as providing access to money) and framing (risk/reward implied by the ask). We demonstrate improvements in ask/framing detection through refinements to our lexical organization and show that response generation qualitatively improves as ask/framing detection performance improves. The paradigm presents a systematic and efficient approach to resource adaptation for improved task-specific performance.
Asynchronous Byzantine Approximate Consensus in Directed Networks
Venue: arXiv cs.DC 2020
Year: 2020

In this work, we study the approximate consensus problem in asynchronous message-passing networks where some nodes may become Byzantine faulty. We answer an open problem raised by Tseng and Vaidya, 2012, proposing the first algorithm of optimal resilience for directed networks. Interestingly, our results show that the tight condition on the underlying communication networks for asynchronous Byzantine approximate consensus coincides with the tight condition for synchronous Byzantine exact consensus. Our results can be viewed as a non-trivial generalization of the algorithm by Abraham et al., 2004, which applies to the special case of complete networks. The tight condition and techniques identified in the paper shed light on the fundamental properties for solving approximate consensus in asynchronous directed networks.
COVID-19 Time-series Prediction by Joint Dictionary Learning and Online NMF
Venue: arXiv cs.LG 2020
Year: 2020

Predicting the spread and containment of COVID-19 is a challenge of utmost importance that the broader scientific community is currently facing. One of the main sources of difficulty is that a very limited amount of daily COVID-19 case data is available, and with few exceptions, the majority of countries are currently in the "exponential spread stage," and thus there is scarce information available which would enable one to predict the phase transition between spread and containment. In this paper, we propose a novel approach to predicting the spread of COVID-19 based on dictionary learning and online nonnegative matrix factorization (online NMF). The key idea is to learn dictionary patterns of short evolution instances of the new daily cases in multiple countries at the same time, so that their latent correlation structures are captured in the dictionary patterns. We first learn such patterns by minibatch learning from the entire time-series and then further adapt them to the time-series by online NMF. As we progressively adapt and improve the learned dictionary patterns to the more recent observations, we also use them to make one-step predictions by the partial fitting. Lastly, by recursively applying the one-step predictions, we can extrapolate our predictions into the near future. Our prediction results can be directly attributed to the learned dictionary patterns due to their interpretability.
Community detection with node attributes in multilayer networks
Venue: arXiv cs.SI 2020
Year: 2020

Community detection in networks is commonly performed using information about interactions between nodes. Recent advances have been made to incorporate multiple types of interactions, thus generalizing standard methods to multilayer networks. Often though, one can access additional information regarding individual nodes, attributes or covariates. A relevant question is thus how to properly incorporate this extra information in such frameworks. Here we develop a method that incorporates both the topology of interactions and node attributes to extract communities in multilayer networks. We propose a principled probabilistic method that does not assume any a priori correlation structure between attributes and communities but rather infers this from data. This leads to an efficient algorithmic implementation that exploits the sparsity of the dataset and can be used to perform several inference tasks; we provide an open-source implementation of the code online. We demonstrate our method on both synthetic and real-world data and compare performance with methods that do not use any attribute information. We find that including node information helps in predicting missing links or attributes. It also leads to more interpretable community structures and allows the quantification of the impact of the node attributes given in input.
Invariant Integration in Deep Convolutional Feature Space
Venue: arXiv cs.LG 2020
Year: 2020

In this contribution, we show how to incorporate prior knowledge to a deep neural network architecture in a principled manner. We enforce feature space invariances using a novel layer based on invariant integration. This allows us to construct a complete feature space invariant to finite transformation groups. We apply our proposed layer to explicitly insert invariance properties for vision-related classification tasks, demonstrate our approach for the case of rotation invariance and report state-of-the-art performance on the Rotated-MNIST dataset. Our method is especially beneficial when training with limited data.
GraN: An Efficient Gradient-Norm Based Detector for Adversarial and Misclassified Examples
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks (DNNs) are vulnerable to adversarial examples and other data perturbations. Especially in safety critical applications of DNNs, it is therefore crucial to detect misclassified samples. The current state-of-the-art detection methods require either significantly more runtime or more parameters than the original network itself. This paper therefore proposes GraN, a time- and parameter-efficient method that is easily adaptable to any DNN. GraN is based on the layer-wise norm of the DNN's gradient regarding the loss of the current input-output combination, which can be computed via backpropagation. GraN achieves state-of-the-art performance on numerous problem set-ups.
A Revised Generative Evaluation of Visual Dialogue
Venue: arXiv cs.CV 2020
Year: 2020

Evaluating Visual Dialogue, the task of answering a sequence of questions relating to a visual input, remains an open research challenge. The current evaluation scheme of the VisDial dataset computes the ranks of ground-truth answers in predefined candidate sets, which Massiceti et al. (2018) show can be susceptible to the exploitation of dataset biases. This scheme also does little to account for the different ways of expressing the same answer--an aspect of language that has been well studied in NLP. We propose a revised evaluation scheme for the VisDial dataset leveraging metrics from the NLP literature to measure consensus between answers generated by the model and a set of relevant answers. We construct these relevant answer sets using a simple and effective semi-supervised method based on correlation, which allows us to automatically extend and scale sparse relevance annotations from humans to the entire dataset. We release these sets and code for the revised evaluation scheme as DenseVisDial, and intend them to be an improvement to the dataset in the face of its existing constraints and design choices.
A Procedure for Extracting Software Development Process Patterns
Venue: arXiv cs.SE 2020
Year: 2020

Process patterns represent well-structured and successful recurring activities of Software Development Methodologies. They are able to form a library of reusable building blocks that can be utilized in Situational Method Engineering for constructing a custom SDM or enhancing an existing one to fit specific project situation. Recently, some researchers have subjectively extracted process patterns from existing SDMs based on cumulative experience in various domains; however, how to objectively extract process patterns from SDMs by adopting a systematic procedure has remained as question. In this regard, this paper is concerned with a procedure aiming to take process patterns out of existing SDMs. An example illustrates applicability of the proposed procedure for extracting process patterns in a specific context.
Process Patterns for Service Oriented Development
Venue: arXiv cs.SE 2020
Year: 2020

Software systems development nowadays has moved towards dynamic composition of services that run on distributed infrastructures aligned with continuous changes in the system requirements. Consequently, software developers need to tailor project specific methodologies to fit their methodology requirements. Process patterns present a suitable solution by providing reusable method chunks of software development methodologies for constructing methodologies to fit specific requirements. In this paper, we propose a set of high-level service-oriented process patterns that can be used for constructing and enhancing situational service-oriented methodologies. We show how these patterns are used to construct a specific service-oriented methodology for the development of a sample system. Keywords. Service-Oriented Software Development Methodologies, Process Patterns, Process Meta-Model, Situational Method Engineering
Multi-label Stream Classification with Self-Organizing Maps
Venue: arXiv cs.LG 2020
Year: 2020

Several learning algorithms have been proposed for offline multi-label classification. However, applications in areas such as traffic monitoring, social networks, and sensors produce data continuously, the so called data streams, posing challenges to batch multi-label learning. With the lack of stationarity in the distribution of data streams, new algorithms are needed to online adapt to such changes (concept drift). Also, in realistic applications, changes occur in scenarios of infinitely delayed labels, where the true classes of the arrival instances are never available. We propose an online unsupervised incremental method based on self-organizing maps for multi-label stream classification with infinitely delayed labels. In the classification phase, we use a k-nearest neighbors strategy to compute the winning neurons in the maps, adapting to concept drift by online adjusting neuron weight vectors and dataset label cardinality. We predict labels for each instance using the Bayes rule and the outputs of each neuron, adapting the probabilities and conditional probabilities of the classes in the stream. Experiments using synthetic and real datasets show that our method is highly competitive with several ones from the literature, in both stationary and concept drift scenarios.
Improving correlation method with convolutional neural networks
Venue: arXiv cs.CV 2020
Year: 2020

We present a convolutional neural network for the classification of correlation responses obtained by correlation filters. The proposed approach can improve the accuracy of classification, as well as achieve invariance to the image classes and parameters.
Information Freshness in Cache Updating Systems
Venue: arXiv cs.IT 2020
Year: 2020

We consider a cache updating system with a source, a cache and a user. There are $n$ files. The source keeps the freshest version of the files which are updated with known rates $λ_i$. The cache downloads and keeps the freshest version of the files from the source with rates $c_i$. The user gets updates from the cache with rates $u_i$. When the user gets an update, it either gets a fresh update from the cache or the file at the cache becomes outdated by a file update at the source in which case the user gets an outdated update. We find an analytical expression for the average freshness of the files at the user. Next, we generalize our setting to the case where there are multiple caches in between the source and the user, and find the average freshness at the user. We provide an alternating maximization based method to find the update rates for the cache(s), $c_i$, and for the user, $u_i$, to maximize the freshness of the files at the user. We observe that for a given set of update rates for the user (resp. for the cache), the optimal rate allocation policy for the cache (resp. for the user) is a $threshold$ $policy$, where the optimal update rates for rapidly changing files at the source may be equal to zero. Finally, we consider a system where multiple users are connected to a single cache and find update rates for the cache and the users to maximize the total freshness over all users.
Revisiting Initialization of Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

The proper initialization of weights is crucial for the effective training and fast convergence of deep neural networks (DNNs). Prior work in this area has mostly focused on balancing the variance among weights per layer to maintain stability of (i) the input data propagated forwards through the network and (ii) the loss gradients propagated backwards, respectively. This prevalent heuristic is however agnostic of dependencies among gradients across the various layers and captures only firstorder effects. In this paper, we propose and discuss an initialization principle that is based on a rigorous estimation of the global curvature of weights across layers by approximating and controlling the norm of their Hessian matrix. The proposed approach is more systematic and recovers previous results for DNN activations such as smooth functions, dropouts, and ReLU. Our experiments on Word2Vec and the MNIST/CIFAR image classification tasks confirm that tracking the Hessian norm is a useful diagnostic tool which helps to more rigorously initialize weights
Influence of COVID-19 confinement in students performance in higher education
Venue: arXiv cs.CY 2020
Year: 2020

This study explores the effects of COVID-19 confinement in the students performance in higher education. Using a field experiment of 458 students from three different subjects in Universidad Autonoma de Madrid (Spain), we study the differences in assessments by dividing students into two groups. The first group (control) corresponds to academic years 2017/2018 and 2018/2019. The second group (experimental) corresponds to students from 2019/2020, which is the group of students that interrupted their face-to-face activities because of the confinement. The results show that there is a significant positive effect of the COVID-19 confinement on students performance. This effect is also significative in activities that did not change their format when performed after the confinement. We find that this effect is significative both in subjects that increased the number of assessment activities and subjects that did not change the workload of students. Additionally, an analysis of students learning strategies before confinement shows that students did not study in a continuous basis. Based on these results, we conclude that COVID-19 confinement changed students learning strategies to a more continuous habit, improving their efficiency. For these reasons, better scores in students assessment are expected due to COVID-19 confinement that can be explained by an improvement in their learning performance.