OpenRaiser/Intern-Atlas huggingface dataset:
Optimally Reliable & Cheap Payment Flows on the Lightning Network
Venue: arXiv cs.NI 2021
Year: 2021

Today, payment paths in Bitcoin's Lightning Network are found by searching for shortest paths on the fee graph. We enhance this approach in two dimensions. Firstly, we take into account the probability of a payment actually being possible due to the unknown balance distributions in the channels. Secondly, we use minimum cost flows as a proper generalization of shortest paths to multi-part payments (MPP). In particular we show that under plausible assumptions about the balance distributions we can find the most likely MPP for any given set of senders, recipients and amounts by solving for a (generalized) integer minimum cost flow with a separable and convex cost function. Polynomial time exact algorithms as well as approximations are known for this optimization problem. We present a round-based algorithm of min-cost flow computations for delivering large payment amounts over the Lightning Network. This algorithm works by updating the probability distributions with the information gained from both successful and unsuccessful paths on prior rounds. In all our experiments a single digit number of rounds sufficed to deliver payments of sizes that were close to the total local balance of the sender. Early experiments indicate that our approach increases the size of payments that can be reliably delivered by several orders of magnitude compared to the current state of the art. We observe that finding the cheapest multi-part payments is an NP-hard problem considering the current fee structure and propose dropping the base fee to make it a linear min-cost flow problem. Finally, we discuss possibilities for maximizing the probability while at the same time minimizing the fees of a flow. While this turns out to be a hard problem in general as well - even in the single path case - it appears to be surprisingly tractable in practice.
Structured Directional Pruning via Perturbation Orthogonal Projection
Venue: arXiv cs.LG 2021
Year: 2021

Structured pruning is an effective compression technique to reduce the computation of neural networks, which is usually achieved by adding perturbations to reduce network parameters at the cost of slightly increasing training loss. A more reasonable approach is to find a sparse minimizer along the flat minimum valley found by optimizers, i.e. stochastic gradient descent, which keeps the training loss constant. To achieve this goal, we propose the structured directional pruning based on orthogonal projecting the perturbations onto the flat minimum valley. We also propose a fast solver sDprun and further prove that it achieves directional pruning asymptotically after sufficient training. Experiments using VGG-Net and ResNet on CIFAR-10 and CIFAR-100 datasets show that our method obtains the state-of-the-art pruned accuracy (i.e. 93.97% on VGG16, CIFAR-10 task) without retraining. Experiments using DNN, VGG-Net and WRN28X10 on MNIST, CIFAR-10 and CIFAR-100 datasets demonstrate our method performs structured directional pruning, reaching the same minimum valley as the optimizer.
Post Triangular Rewiring Method for Shorter RRT Robot Path Planning
Venue: arXiv cs.RO 2021
Year: 2021

This paper proposed the 'Post Triangular Rewiring' method that minimizes the sacrifice of planning time and overcomes the limit of Optimality of sampling-based algorithm such as Rapidly-exploring Random Tree (RRT) algorithm. The proposed 'Post Triangular Rewiring' method creates a closer to the optimal path than RRT algorithm before application through the triangular inequality principle. The experiments were conducted to verify a performance of the proposed method. When the method proposed in this paper are applied to the RRT algorithm, the Optimality efficiency increase compared to the planning time.
Measuring scientific output of researchers by t-index and Data Envelopment Analysis
Venue: arXiv cs.DL 2021
Year: 2021

There is a growing need for ranking universities, departments, research groups, and individual scholars. Usually, the scientific community measures the scientific merits of the researchers by using a variety of indicators that take into account both the productivity of scholars and the impact of their publications. We propose the t-index, the new indicator to measure the scientific merits of the individual researchers. The proposed t-index takes into account the number of citations, number of coauthors on every published paper, and career duration. The t-index makes the possible comparison of researchers at various stages of their careers. We also use in this paper the Data Envelopment Analysis (DEA) to measure the scientific merits of the individual researchers within the observed group of researchers. We chose 15 scholars in the scientific area of transportation engineering and measured their t-index values, as well as DEA scores.
Can Evolutionary Computation Help us to Crib the Voynich Manuscript ?
Venue: arXiv cs.CL 2021
Year: 2021

Departing from the postulate that Voynich Manuscript is not a hoax but rather encodes authentic contents, our article presents an evolutionary algorithm which aims to find the most optimal mapping between voynichian glyphs and candidate phonemic values. Core component of the decoding algorithm is a process of maximization of a fitness function which aims to find most optimal set of substitution rules allowing to transcribe the part of the manuscript -- which we call the Calendar -- into lists of feminine names. This leads to sets of character subsitution rules which allow us to consistently transcribe dozens among three hundred calendar tokens into feminine names: a result far surpassing both ``popular'' as well as "state of the art" tentatives to crack the manuscript. What's more, by using name lists stemming from different languages as potential cribs, our ``adaptive'' method can also be useful in identification of the language in which the manuscript is written. As far as we can currently tell, results of our experiments indicate that the Calendar part of the manuscript contains names from baltoslavic, balkanic or hebrew language strata. Two further indications are also given: primo, highest fitness values were obtained when the crib list contains names with specific infixes at token's penultimate position as is the case, for example, for slavic \textbf{feminine diminutives} (i.e. names ending with -ka and not -a). In the most successful scenario, 240 characters contained in 35 distinct Voynichese tokens were successfully transcribed. Secundo, in case of crib stemming from Hebrew language, whole adaptation process converges to significantly better fitness values when transcribing voynichian tokens whose order of individual characters have been reversed, and when lists feminine and not masculine names are used as the crib.
Data-Driven Extract Method Recommendations: A Study at ING
Venue: arXiv cs.SE 2021
Year: 2021

The sound identification of refactoring opportunities is still an open problem in software engineering. Recent studies have shown the effectiveness of machine learning models in recommending methods that should undergo different refactoring operations. In this work, we experiment with such approaches to identify methods that should undergo an Extract Method refactoring, in the context of ING, a large financial organization. More specifically, we (i) compare the code metrics distributions, which are used as features by the models, between open-source and ING systems, (ii) measure the accuracy of different machine learning models in recommending Extract Method refactorings, (iii) compare the recommendations given by the models with the opinions of ING experts. Our results show that the feature distributions of ING systems and open-source systems are somewhat different, that machine learning models can recommend Extract Method refactorings with high accuracy, and that experts tend to agree with most of the recommendations of the model.
giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris-Rips Filtrations
Venue: arXiv cs.CG 2021
Year: 2021

We introduce giotto-ph, a high-performance, open-source software package for the computation of Vietoris-Rips barcodes. giotto-ph is based on Morozov and Nigmetov's lockfree (multicore) implementation of Ulrich Bauer's Ripser package. It also contains a re-working of the GUDHI library's implementation of Boissonnat and Pritam's Edge Collapser, which can be used as a pre-processing step to dramatically reduce overall run-times in certain scenarios. Our contribution is twofold: on the one hand, we integrate existing state-of-the-art ideas coherently in a single library and provide Python bindings to the C++ code. On the other hand, we increase parallelization opportunities and improve overall performance by adopting more efficient data structures. Our persistent homology backend establishes a new state of the art, surpassing even GPU-accelerated implementations such as Ripser++ when using as few as 5-10 CPU cores. Furthermore, our implementation of Edge Collapser has fewer software dependencies and improved run-times relative to GUDHI's original implementation.
Leveraging a Federation of Knowledge Graphs to Improve Faceted Search in Digital Libraries
Venue: arXiv cs.DL 2021
Year: 2021

Scientists always look for the most accurate and relevant answers to their queries in the literature. Traditional scholarly digital libraries list documents in search results, and therefore are unable to provide precise answers to search queries. In other words, search in digital libraries is metadata search and, if available, full-text search. We present a methodology for improving a faceted search system on structured content by leveraging a federation of scholarly knowledge graphs. We implemented the methodology on top of a scholarly knowledge graph. This search system can leverage content from third-party knowledge graphs to improve the exploration of scholarly content. A novelty of our approach is that we use dynamic facets on diverse data types, meaning that facets can change according to the user query. The user can also adjust the granularity of dynamic facets. An additional novelty is that we leverage third-party knowledge graphs to improve exploring scholarly knowledge.
Neat: Low-Complexity, Efficient On-Chip Cache Coherence
Venue: arXiv cs.AR 2021
Year: 2021

Cache coherence protocols such as MESI that use writer-initiated invalidation have high complexity and sometimes have poor performance and energy usage, especially under false sharing. Such protocols require numerous transient states, a shared directory, and support for core-to-core communication, while also suffering under false sharing. An alternative to MESI's writer-initiated invalidation is self-invalidation, which achieves lower complexity than MESI but adds high performance costs or relies on programmer annotations or specific data access patterns. This paper presents Neat, a low-complexity, efficient cache coherence protocol. Neat uses self-invalidation, thus avoiding MESI's transient states, directory, and core-to-core communication requirements. Neat uses novel mechanisms that effectively avoid many unnecessary self-invalidations. An evaluation shows that Neat is simple and has lower verification complexity than the MESI protocol. Neat not only outperforms state-of-the-art self-invalidation protocols, but its performance and energy consumption are comparable to MESI's, and it outperforms MESI under false sharing.
Behavior Constraining in Weight Space for Offline Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

In offline reinforcement learning, a policy needs to be learned from a single pre-collected dataset. Typically, policies are thus regularized during training to behave similarly to the data generating policy, by adding a penalty based on a divergence between action distributions of generating and trained policy. We propose a new algorithm, which constrains the policy directly in its weight space instead, and demonstrate its effectiveness in experiments.
Prequential MDL for Causal Structure Learning with Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Learning the structure of Bayesian networks and causal relationships from observations is a common goal in several areas of science and technology. We show that the prequential minimum description length principle (MDL) can be used to derive a practical scoring function for Bayesian networks when flexible and overparametrized neural networks are used to model the conditional probability distributions between observed variables. MDL represents an embodiment of Occam's Razor and we obtain plausible and parsimonious graph structures without relying on sparsity inducing priors or other regularizers which must be tuned. Empirically we demonstrate competitive results on synthetic and real-world data. The score often recovers the correct structure even in the presence of strongly nonlinear relationships between variables; a scenario were prior approaches struggle and usually fail. Furthermore we discuss how the the prequential score relates to recent work that infers causal structure from the speed of adaptation when the observations come from a source undergoing distributional shift.
Time Series Analysis of Computer Network Traffic in a Dedicated Link Aggregation
Venue: arXiv cs.NI 2021
Year: 2021

Fractal behavior and long-range dependence are widely observed in measurements and characterization of traffic flow in high-speed computer networks of different technologies and coverage levels. This paper presents the results obtained when applying fractal analysis techniques on a time series obtained from traffic captures coming from an application server connected to the Internet through a high-speed link. The results obtained show that traffic flow in the dedicated high-speed network link have fractal behavior when the Hurst exponent is in the range of 0.5, 1, the fractal dimension between 1, 1.5, and the correlation coefficient between -0.5, 0. Based on these results, it is ideal to characterize both the singularities of the traffic and its impulsiveness during a fractal analysis of temporal scales. Finally, based on the results of the time series analyses, the fact that the traffic flows of current computer networks exhibit fractal behavior with a long-range dependency is reaffirmed.
LATTE: LSTM Self-Attention based Anomaly Detection in Embedded Automotive Platforms
Venue: arXiv cs.LG 2021
Year: 2021

Modern vehicles can be thought of as complex distributed embedded systems that run a variety of automotive applications with real-time constraints. Recent advances in the automotive industry towards greater autonomy are driving vehicles to be increasingly connected with various external systems (e.g., roadside beacons, other vehicles), which makes emerging vehicles highly vulnerable to cyber-attacks. Additionally, the increased complexity of automotive applications and the in-vehicle networks results in poor attack visibility, which makes detecting such attacks particularly challenging in automotive systems. In this work, we present a novel anomaly detection framework called LATTE to detect cyber-attacks in Controller Area Network (CAN) based networks within automotive platforms. Our proposed LATTE framework uses a stacked Long Short Term Memory (LSTM) predictor network with novel attention mechanisms to learn the normal operating behavior at design time. Subsequently, a novel detection scheme (also trained at design time) is used to detect various cyber-attacks (as anomalies) at runtime. We evaluate our proposed LATTE framework under different automotive attack scenarios and present a detailed comparison with the best-known prior works in this area, to demonstrate the potential of our approach.
Understanding the Communist Party of China's Information Operations
Venue: arXiv cs.CR 2021
Year: 2021

The Communist Party of China is known to engage in Information Operations to influence public opinion. In this paper, we seek to understand the tactics used by the Communist Party in a recent Information Operation - the one conducted to influence the narrative around the pro-democracy movement in Hong Kong. We use a Twitter dataset containing account information and tweets for the operation. Our research shows that the Hong Kong operation was (at least) partially conducted manually by humans rather than entirely by automated bots. We also show that the Communist Party mixed in personal attacks on Chinese dissidents and messages on COVID-19 with the party's views on the protests during the operation. Finally, we conclude that the Information Operation network in the Twitter dataset was set up to amplify content generated elsewhere rather than to influence the narrative with original content.
Structured Latent Embeddings for Recognizing Unseen Classes in Unseen Domains
Venue: arXiv cs.CV 2021
Year: 2021

The need to address the scarcity of task-specific annotated data has resulted in concerted efforts in recent years for specific settings such as zero-shot learning (ZSL) and domain generalization (DG), to separately address the issues of semantic shift and domain shift, respectively. However, real-world applications often do not have constrained settings and necessitate handling unseen classes in unseen domains -- a setting called Zero-shot Domain Generalization, which presents the issues of domain and semantic shifts simultaneously. In this work, we propose a novel approach that learns domain-agnostic structured latent embeddings by projecting images from different domains as well as class-specific semantic text-based representations to a common latent space. In particular, our method jointly strives for the following objectives: (i) aligning the multimodal cues from visual and text-based semantic concepts; (ii) partitioning the common latent space according to the domain-agnostic class-level semantic concepts; and (iii) learning a domain invariance w.r.t the visual-semantic joint distribution for generalizing to unseen classes in unseen domains. Our experiments on the challenging DomainNet and DomainNet-LS benchmarks show the superiority of our approach over existing methods, with significant gains on difficult domains like quickdraw and sketch.
Locally Enhanced Self-Attention: Combining Self-Attention and Convolution as Local and Context Terms
Venue: arXiv cs.CV 2021
Year: 2021

Self-Attention has become prevalent in computer vision models. Inspired by fully connected Conditional Random Fields (CRFs), we decompose self-attention into local and context terms. They correspond to the unary and binary terms in CRF and are implemented by attention mechanisms with projection matrices. We observe that the unary terms only make small contributions to the outputs, and meanwhile standard CNNs that rely solely on the unary terms achieve great performances on a variety of tasks. Therefore, we propose Locally Enhanced Self-Attention (LESA), which enhances the unary term by incorporating it with convolutions, and utilizes a fusion module to dynamically couple the unary and binary operations. In our experiments, we replace the self-attention modules with LESA. The results on ImageNet and COCO show the superiority of LESA over convolution and self-attention baselines for the tasks of image recognition, object detection, and instance segmentation. The code is made publicly available.
Altruistic Maneuver Planning for Cooperative Autonomous Vehicles Using Multi-agent Advantage Actor-Critic
Venue: arXiv cs.RO 2021
Year: 2021

With the adoption of autonomous vehicles on our roads, we will witness a mixed-autonomy environment where autonomous and human-driven vehicles must learn to co-exist by sharing the same road infrastructure. To attain socially-desirable behaviors, autonomous vehicles must be instructed to consider the utility of other vehicles around them in their decision-making process. Particularly, we study the maneuver planning problem for autonomous vehicles and investigate how a decentralized reward structure can induce altruism in their behavior and incentivize them to account for the interest of other autonomous and human-driven vehicles. This is a challenging problem due to the ambiguity of a human driver's willingness to cooperate with an autonomous vehicle. Thus, in contrast with the existing works which rely on behavior models of human drivers, we take an end-to-end approach and let the autonomous agents to implicitly learn the decision-making process of human drivers only from experience. We introduce a multi-agent variant of the synchronous Advantage Actor-Critic (A2C) algorithm and train agents that coordinate with each other and can affect the behavior of human drivers to improve traffic flow and safety.
Stress Classification and Personalization: Getting the most out of the least
Venue: arXiv cs.LG 2021
Year: 2021

Stress detection and monitoring is an active area of research with important implications for the personal, professional, and social health of an individual. Current approaches for affective state classification use traditional machine learning algorithms with features computed from multiple sensor modalities. These methods are data-intensive and rely on hand-crafted features which impede the practical applicability of these sensor systems in daily lives. To overcome these shortcomings, we propose a novel Convolutional Neural Network (CNN) based stress detection and classification framework without any feature computation using data from only one sensor modality. Our method is competitive and outperforms current state-of-the-art techniques and achieves a classification accuracy of $92.85\%$ and an $f1$ score of $0.89$. Through our leave-one-subject-out analysis, we also show the importance of personalizing stress models.
Accenture at CheckThat! 2021: Interesting claim identification and ranking with contextually sensitive lexical training data augmentation
Venue: arXiv cs.CL 2021
Year: 2021

This paper discusses the approach used by the Accenture Team for CLEF2021 CheckThat! Lab, Task 1, to identify whether a claim made in social media would be interesting to a wide audience and should be fact-checked. Twitter training and test data were provided in English, Arabic, Spanish, Turkish, and Bulgarian. Claims were to be classified (check-worthy/not check-worthy) and ranked in priority order for the fact-checker. Our method used deep neural network transformer models with contextually sensitive lexical augmentation applied on the supplied training datasets to create additional training samples. This augmentation approach improved the performance for all languages. Overall, our architecture and data augmentation pipeline produced the best submitted system for Arabic, and performance scales according to the quantity of provided training data for English, Spanish, Turkish, and Bulgarian. This paper investigates the deep neural network architectures for each language as well as the provided data to examine why the approach worked so effectively for Arabic, and discusses additional data augmentation measures that should could be useful to this problem.
Detecting Ideal Instagram Influencer Using Social Network Analysis
Venue: arXiv cs.SI 2021
Year: 2021

Social Media is a key aspect of modern society where people share their thoughts, views, feelings and sentiments. Over the last few years, the inflation in popularity of social media has resulted in a monumental increase in data. Users use this medium to express their thoughts, feelings, and opinions on a wide variety of subjects, including politics and celebrities. Social Media has thus evolved into a lucrative platform for companies to expand their scope and improve their prospects. The paper focuses on social network analysis (SNA) for a real-world online marketing strategy. The study contributes by comparing various centrality measures to identify the most central nodes in the network and uses a linear threshold model to understand the spreading behaviour of individual users. In conclusion, the paper correlates different centrality measures and spreading behaviour to identify the most influential user in the network