OpenRaiser/Intern-Atlas huggingface dataset:
Modeling the Block Verification Time of Zcash
Venue: arXiv cs.CR 2021
Year: 2021

An important aspect of the propagation delay in blockchain networks is the block verification time, which is also responsible for the so-called verifier's dilemma. Models for the block verification time can help to understand and improve the verification process. Moreover, modeling the verification time is necessary for blockchain network simulations. In this paper, we present JOIST, a new model for the block verification time of Zcash. We identify computationally complex operations in the verification process of Zcash, and derive our model based on characteristic transaction features. We evaluate JOIST and show that the model is consistently more accurate than existing models, which consider the block size only.
A Logical Model for joining Property Graphs
Venue: arXiv cs.LO 2021
Year: 2021

The present paper upgrades the logical model required to exploit materialized views over property graphs as intended in the seminal paper "A Join Operator for Property Graphs". Furthermore, we provide some computational complexity proofs strengthening the contribution of a forthcoming graph equi-join algorithm proposed in a recently accepted paper.
Reasoning on $\textit{DL-Lite}_{\cal R}$ with Defeasibility in ASP
Venue: arXiv cs.AI 2021
Year: 2021

Reasoning on defeasible knowledge is a topic of interest in the area of description logics, as it is related to the need of representing exceptional instances in knowledge bases. In this direction, in our previous works we presented a framework for representing (contextualized) OWL RL knowledge bases with a notion of justified exceptions on defeasible axioms: reasoning in such framework is realized by a translation into ASP programs. The resulting reasoning process for OWL RL, however, introduces a complex encoding in order to capture reasoning on the negative information needed for reasoning on exceptions. In this paper, we apply the justified exception approach to knowledge bases in $\textit{DL-Lite}_{\cal R}$, i.e., the language underlying OWL QL. We provide a definition for $\textit{DL-Lite}_{\cal R}$ knowledge bases with defeasible axioms and study their semantic and computational properties. In particular, we study the effects of exceptions over unnamed individuals. The limited form of $\textit{DL-Lite}_{\cal R}$ axioms allows us to formulate a simpler ASP encoding, where reasoning on negative information is managed by direct rules. The resulting materialization method gives rise to a complete reasoning procedure for instance checking in $\textit{DL-Lite}_{\cal R}$ with defeasible axioms. Under consideration in Theory and Practice of Logic Programming (TPLP).
Hyperspectral Remote Sensing Image Classification Based on Multi-scale Cross Graphic Convolution
Venue: arXiv cs.CV 2021
Year: 2021

The mining and utilization of features directly affect the classification performance of models used in the classification and recognition of hyperspectral remote sensing images. Traditional models usually conduct feature mining from a single perspective, with the features mined being limited and the internal relationships between them being ignored. Consequently, useful features are lost and classification results are unsatisfactory. To fully mine and utilize image features, a new multi-scale feature-mining learning algorithm (MGRNet) is proposed. The model uses principal component analysis to reduce the dimensionality of the original hyperspectral image (HSI) to retain 99.99% of its semantic information and extract dimensionality reduction features. Using a multi-scale convolution algorithm, the input dimensionality reduction features were mined to obtain shallow features, which then served as inputs into a multi-scale graph convolution algorithm to construct the internal relationships between eigenvalues at different scales. We then carried out cross fusion of multi-scale information obtained by graph convolution, before inputting the new information obtained into the residual network algorithm for deep feature mining. Finally, a flexible maximum transfer function classifier was used to predict the final features and complete the classification. Experiments on three common hyperspectral datasets showed the MGRNet algorithm proposed in this paper to be superior to traditional methods in recognition accuracy.
TOPIC: Top-k High-Utility Itemset Discovering
Venue: arXiv cs.DB 2021
Year: 2021

Utility-driven itemset mining is widely applied in many real-world scenarios. However, most algorithms do not work for itemsets with negative utilities. Several efficient algorithms for high-utility itemset (HUI) mining with negative utilities have been proposed. These algorithms can find complete HUIs with or without negative utilities. However, the major problem with these algorithms is how to select an appropriate minimum utility (minUtil) threshold. To address this issue, some efficient algorithms for extracting top-k HUIs have been proposed, where parameter k is the quantity of HUIs to be discovered. However, all of these algorithms can solve only one part of the above problem. In this paper, we present a method for TOP-k high-utility Itemset disCovering (TOPIC) with positive and negative utility values, which utilizes the advantages of the above algorithms. TOPIC adopts transaction merging and database projection techniques to reduce the database scanning cost, and utilizes minUtil threshold raising strategies. It also uses an array-based utility technique, which calculates the utility of itemsets and upper bounds in linear time. We conducted extensive experiments on several real and synthetic datasets, and the results showed that TOPIC outperforms state-of-the-art algorithm in terms of runtime, memory costs, and scalability.
Dataset Bias Mitigation Through Analysis of CNN Training Scores
Venue: arXiv cs.CV 2021
Year: 2021

Training datasets are crucial for convolutional neural network-based algorithms, which directly impact their overall performance. As such, using a well-structured dataset that has minimum level of bias is always desirable. In this paper, we proposed a novel, domain-independent approach, called score-based resampling (SBR), to locate the under-represented samples of the original training dataset based on the model prediction scores obtained with that training set. In our method, once trained, we use the same CNN model to infer on its own training samples, obtain prediction scores, and based on the distance between predicted and ground-truth, we identify samples that are far away from their ground-truth and augment them in the original training set. The temperature term of the Sigmoid function is decreased to better differentiate scores. For experimental evaluation, we selected one Kaggle dataset for gender classification. We first used a CNN-based classifier with relatively standard structure, trained on the training images, and evaluated on the provided validation samples of the original dataset. Then, we assessed it on a totally new test dataset consisting of light male, light female, dark male, and dark female groups. The obtained accuracies varied, revealing the existence of categorical bias against certain groups in the original dataset. Subsequently, we trained the model after resampling based on our proposed approach. We compared our method with a previously proposed variational autoencoder (VAE) based algorithm. The obtained results confirmed the validity of our proposed method regrading identifying under-represented samples among original dataset to decrease categorical bias of classifying certain groups. Although tested for gender classification, the proposed algorithm can be used for investigating dataset structure of any CNN-based tasks.
THUE: Discovering Top-K High Utility Episodes
Venue: arXiv cs.DB 2021
Year: 2021

Episode discovery from an event is a popular framework for data mining tasks and has many real-world applications. An episode is a partially ordered set of objects (e.g., item, node), and each object is associated with an event type. This episode can also be considered as a complex event sub-sequence. High-utility episode mining is an interesting utility-driven mining task in the real world. Traditional episode mining algorithms, by setting a threshold, usually return a huge episode that is neither intuitive nor saves time. In general, finding a suitable threshold in a pattern-mining algorithm is a trivial and time-consuming task. In this paper, we propose a novel algorithm, called Top-K High Utility Episode (THUE) mining within the complex event sequence, which redefines the previous mining task by obtaining the K highest episodes. We introduce several threshold-raising strategies and optimize the episode-weighted utilization upper bounds to speed up the mining process and effectively reduce the memory cost. Finally, the experimental results on both real-life and synthetic datasets reveal that the THUE algorithm can offer six to eight orders of magnitude running time performance improvement over the state-of-the-art algorithm and has low memory consumption.
$\ell_p$-norm Multiway Cut
Venue: arXiv cs.DS 2021
Year: 2021

We introduce and study $\ell_p$-norm-multiway-cut: the input here is an undirected graph with non-negative edge weights along with $k$ terminals and the goal is to find a partition of the vertex set into $k$ parts each containing exactly one terminal so as to minimize the $\ell_p$-norm of the cut values of the parts. This is a unified generalization of min-sum multiway cut (when $p=1$) and min-max multiway cut (when $p=\infty$), both of which are well-studied classic problems in the graph partitioning literature. We show that $\ell_p$-norm-multiway-cut is NP-hard for constant number of terminals and is NP-hard in planar graphs. On the algorithmic side, we design an $O(\log^2 n)$-approximation for all $p\ge 1$. We also show an integrality gap of $Ω(k^{1-1/p})$ for a natural convex program and an $O(k^{1-1/p-ε})$-inapproximability for any constant $ε>0$ assuming the small set expansion hypothesis.
CLIPDraw: Exploring Text-to-Drawing Synthesis through Language-Image Encoders
Venue: arXiv cs.CV 2021
Year: 2021

This work presents CLIPDraw, an algorithm that synthesizes novel drawings based on natural language input. CLIPDraw does not require any training; rather a pre-trained CLIP language-image encoder is used as a metric for maximizing similarity between the given description and a generated drawing. Crucially, CLIPDraw operates over vector strokes rather than pixel images, a constraint that biases drawings towards simpler human-recognizable shapes. Results compare between CLIPDraw and other synthesis-through-optimization methods, as well as highlight various interesting behaviors of CLIPDraw, such as satisfying ambiguous text in multiple ways, reliably producing drawings in diverse artistic styles, and scaling from simple to complex visual representations as stroke count is increased. Code for experimenting with the method is available at: https://colab.research.google.com/github/kvfrans/clipdraw/blob/main/clipdraw.ipynb
Seeking Stability by being Lazy and Shallow
Venue: arXiv cs.PL 2021
Year: 2021

Designing a language feature often requires a choice between several, similarly expressive possibilities. Given that user studies are generally impractical, we propose using stability as a way of making such decisions. Stability is a measure of whether the meaning of a program alters under small, seemingly innocuous changes in the code. Directly motivated by a need to pin down a feature in GHC/Haskell, we apply this notion of stability to analyse four approaches to the instantiation of polymorphic types, concluding that the most stable approach is lazy (instantiate a polytype only when absolutely necessary) and shallow (instantiate only top-level type variables, not variables that appear after explicit arguments).
Chaos Engineering for Enhanced Resilience of Cyber-Physical Systems
Venue: arXiv cs.CR 2021
Year: 2021

Cyber-physical systems (CPS) incorporate the complex and large-scale engineered systems behind critical infrastructure operations, such as water distribution networks, energy delivery systems, healthcare services, manufacturing systems, and transportation networks. Industrial CPS in particular need to simultaneously satisfy requirements of available, secure, safe and reliable system operation against diverse threats, in an adaptive and sustainable way. These adverse events can be of accidental or malicious nature and may include natural disasters, hardware or software faults, cyberattacks, or even infrastructure design and implementation faults. They may drastically affect the results of CPS algorithms and mechanisms, and subsequently the operations of industrial control systems (ICS) deployed in those critical infrastructures. Such a demanding combination of properties and threats calls for resilience-enhancement methodologies and techniques, working in real-time operation. However, the analysis of CPS resilience is a difficult task as it involves evaluation of various interdependent layers with heterogeneous computing equipment, physical components, network technologies, and data analytics. In this paper, we apply the principles of chaos engineering (CE) to industrial CPS, in order to demonstrate the benefits of such practices on system resilience. The systemic uncertainty of adverse events can be tamed by applying runtime CE-based analyses to CPS in production, in order to predict environment changes and thus apply mitigation measures limiting the range and severity of the event, and minimizing its blast radius.
Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
Venue: arXiv cs.DS 2021
Year: 2021

In this paper, we present Approximation Schemes for Capacitated Vehicle Routing Problem (CVRP) on several classes of graphs. In CVRP, introduced by Dantzig and Ramser (1959), we are given a graph $G=(V,E)$ with metric edges costs, a depot $r\in V$, and a vehicle of bounded capacity $Q$. The goal is to find minimum cost collection of tours for the vehicle that returns to the depot, each visiting at most $Q$ nodes, such that they cover all the nodes. This generalizes classic TSP and has been studied extensively. In the more general setting, each node $v$ has a demand $d_v$ and the total demand of each tour must be no more than $Q$. Either the demand of each node must be served by one tour (unsplittable) or can be served by multiple tour (splittable). The best known approximation algorithm for general graphs has ratio $α+2(1-ε)$ (for the unsplittable) and $α+1-ε$ (for the splittable) for some fixed $ε>\frac{1}{3000}$, where $α$ is the best approximation for TSP. Even for the case of trees, the best approximation ratio is $4/3$ by Becker (2018) and it has been an open question if there is an approximation scheme for this simple class of graphs. Das and Mathieu (2015) presented an approximation scheme with time $n^{\log^{O(1/ε)}n}$ for Euclidean plane $\mathbb{R}^2$. No other approximation scheme is known for any other class of metrics (without further restrictions on $Q$). In this paper, we make significant progress on this classic problem by presenting Quasi-Polynomial Time Approximation Schemes (QPTAS) for graphs of bounded treewidth, graphs of bounded highway dimensions, and graphs of bounded doubling dimensions. For comparison, our result implies an approximation scheme for Euclidean plane with run time $n^{O(\log^{10}n/ε^{9})}$.
Bottleneck Time Minimization for Distributed Iterative Processes: Speeding Up Gossip-Based Federated Learning on Networked Computers
Venue: arXiv cs.DC 2021
Year: 2021

We present a novel task scheduling scheme for accelerating computational applications involving distributed iterative processes that are executed on networked computing resources. Such an application consists of multiple tasks, each of which outputs data at each iteration to be processed by neighboring tasks; these dependencies between the tasks can be represented as a directed graph. We first mathematically formulate the problem as a Binary Quadratic Program (BQP), accounting for both computation and communication costs. We show that the problem is NP-hard. We then relax the problem as a Semi-Definite Program (SDP) and utilize a randomized rounding technique based on sampling from a suitably-formulated multi-variate Gaussian distribution. Furthermore, we derive the expected value of bottleneck time. Finally, we apply our proposed scheme on gossip-based federated learning as an application of iterative processes. Through numerical evaluations on the MNIST and CIFAR-10 datasets, we show that our proposed approach outperforms well-known scheduling techniques from distributed computing. In particular, for arbitrary settings, we show that it reduces bottleneck time by $91\%$ compared to HEFT and $84\%$ compared to throughput HEFT.
GuidedMix-Net: Learning to Improve Pseudo Masks Using Labeled Images as Reference
Venue: arXiv cs.CV 2021
Year: 2021

Semi-supervised learning is a challenging problem which aims to construct a model by learning from a limited number of labeled examples. Numerous methods have been proposed to tackle this problem, with most focusing on utilizing the predictions of unlabeled instances consistency alone to regularize networks. However, treating labeled and unlabeled data separately often leads to the discarding of mass prior knowledge learned from the labeled examples, and failure to mine the feature interaction between the labeled and unlabeled image pairs. In this paper, we propose a novel method for semi-supervised semantic segmentation named GuidedMix-Net, by leveraging labeled information to guide the learning of unlabeled instances. Specifically, we first introduce a feature alignment objective between labeled and unlabeled data to capture potentially similar image pairs and then generate mixed inputs from them. The proposed mutual information transfer (MITrans), based on the cluster assumption, is shown to be a powerful knowledge module for further progressive refining features of unlabeled data in the mixed data space. To take advantage of the labeled examples and guide unlabeled data learning, we further propose a mask generation module to generate high-quality pseudo masks for the unlabeled data. Along with supervised learning for labeled data, the prediction of unlabeled data is jointly learned with the generated pseudo masks from the mixed data. Extensive experiments on PASCAL VOC 2012, PASCAL-Context and Cityscapes demonstrate the effectiveness of our GuidedMix-Net, which achieves competitive segmentation accuracy and significantly improves the mIoU by +7$\%$ compared to previous state-of-the-art approaches.
Automatic Construction of Enterprise Knowledge Base
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we present an automatic knowledge base construction system from large scale enterprise documents with minimal efforts of human intervention. In the design and deployment of such a knowledge mining system for enterprise, we faced several challenges including data distributional shift, performance evaluation, compliance requirements and other practical issues. We leveraged state-of-the-art deep learning models to extract information (named entities and definitions) at per document level, then further applied classical machine learning techniques to process global statistical information to improve the knowledge base. Experimental results are reported on actual enterprise documents. This system is currently serving as part of a Microsoft 365 service.
Do Not Deceive Your Employer with a Virtual Background: A Video Conferencing Manipulation-Detection System
Venue: arXiv cs.CR 2021
Year: 2021

The last-generation video conferencing software allows users to utilize a virtual background to conceal their personal environment due to privacy concerns, especially in official meetings with other employers. On the other hand, users maybe want to fool people in the meeting by considering the virtual background to conceal where they are. In this case, developing tools to understand the virtual background utilize for fooling people in meeting plays an important role. Besides, such detectors must prove robust against different kinds of attacks since a malicious user can fool the detector by applying a set of adversarial editing steps on the video to conceal any revealing footprint. In this paper, we study the feasibility of an efficient tool to detect whether a videoconferencing user background is real. In particular, we provide the first tool which computes pixel co-occurrences matrices and uses them to search for inconsistencies among spectral and spatial bands. Our experiments confirm that cross co-occurrences matrices improve the robustness of the detector against different kinds of attacks. This work's performance is especially noteworthy with regard to color SPAM features. Moreover, the performance especially is significant with regard to robustness versus post-processing, like geometric transformations, filtering, contrast enhancement, and JPEG compression with different quality factors.
Topic-to-Essay Generation with Comprehensive Knowledge Enhancement
Venue: arXiv cs.CL 2021
Year: 2021

Generating high-quality and diverse essays with a set of topics is a challenging task in natural language generation. Since several given topics only provide limited source information, utilizing various topic-related knowledge is essential for improving essay generation performance. However, previous works cannot sufficiently use that knowledge to facilitate the generation procedure. This paper aims to improve essay generation by extracting information from both internal and external knowledge. Thus, a topic-to-essay generation model with comprehensive knowledge enhancement, named TEGKE, is proposed. For internal knowledge enhancement, both topics and related essays are fed to a teacher network as source information. Then, informative features would be obtained from the teacher network and transferred to a student network which only takes topics as input but provides comparable information compared with the teacher network. For external knowledge enhancement, a topic knowledge graph encoder is proposed. Unlike the previous works only using the nearest neighbors of topics in the commonsense base, our topic knowledge graph encoder could exploit more structural and semantic information of the commonsense knowledge graph to facilitate essay generation. Moreover, the adversarial training based on the Wasserstein distance is proposed to improve generation quality. Experimental results demonstrate that TEGKE could achieve state-of-the-art performance on both automatic and human evaluation.
Wrong Colored Vermeer: Color-Symmetric Image Distortion
Venue: arXiv cs.CV 2021
Year: 2021

Color symmetry implies that the colors of geometrical objects are assigned according to their symmetry properties. It is defined by associating the elements of the symmetry group with a color permutation. I use this concept for generative art and apply symmetry-consistent color distortions to images of paintings by Johannes Vermeer. The color permutations are realized as mappings of the HSV color space onto itself.