OpenRaiser/Intern-Atlas huggingface dataset:
Hardness of Ruling Out Short Proofs of Kolmogorov Randomness
Venue: arXiv cs.CC 2023
Year: 2023

A meta-complexity assumption, Feasible Chaitin Incompleteness (FCI), asserts the hardness of ruling out length $t$ proofs that string $x$ is Kolmogorov random (e.g. $x{\in}R$), by analogy to Chaitin's result that proving $x{\in}R$ is typically impossible. By assertion, efficiently ruling out short proofs requires, impossibly, ruling out any proof. FCI has strong implications: (i) randomly chosen $x$ typically yields tautologies hard with high probability for any given proof system, densely witnessing its nonoptimality; (ii) average-case impossibility of proving $x{\in}R$ implies average-case hardness of proving tautologies and Feige's hypothesis; and (iii) a natural language is $\textbf{NP}$-intermediate -- the sparse complement of "$x{\in}R$ lacks a length $t$ proof" (where $R$'s complement is sparse) -- and has $\textbf{P/poly}$ circuits despite not being in $\textbf{P}$. FCI and its variants powerfully assert: (i) noncomputability facts translate to hardness conjectures; (ii) numerous open complexity questions have the expected answers (e.g. non-collapse of $\textbf{PH}$), so one overarching conjecture subsumes many questions; and (iii) an implicit mapping between certain unprovable and hard-to-prove sentences is an isomorphism. Further research could relate FCI to other open questions and hardness hypotheses; consider whether $R$ frustrates conditional program logic, implying FCI; and consider whether an extended isomorphism maps any true unprovable sentence to hard-to-prove sentences.
Consensus in the Unknown-Participation Message-Adversary Model
Venue: arXiv cs.DC 2023
Year: 2023

We propose a new distributed-computing model, inspired by permissionless distributed systems such as Bitcoin and Ethereum, that allows studying permissionless consensus in a mathematically regular setting. Like in the sleepy model of Pass and Shi, we consider a synchronous, round-by-round message-passing system in which the set of online processors changes each round. Unlike the sleepy model, the set of processors may be infinite. Moreover, processors never fail; instead, an adversary can temporarily or permanently impersonate some processors. Finally, processors have access to a strong form of message-authentication that authenticates not only the sender of a message but also the round in which the message was sent. Assuming that, each round, the adversary impersonates less than 1/2 of the online processors, we present two consensus algorithms. The first ensures deterministic safety and constant latency in expectation, assuming a probabilistic leader-election oracle. The second ensures deterministic safety and deterministic liveness assuming irrevocable impersonation and eventually-stabilizing participation. The model is unrealistic in full generality. However, if we assume finitely many processes and that the set of faulty processes remains constant, the model coincides with a practically-motivated model: the static version of the sleepy model.
A Network Science perspective of Graph Convolutional Networks: A survey
Venue: arXiv cs.SI 2023
Year: 2023

The mining and exploitation of graph structural information have been the focal points in the study of complex networks. Traditional structural measures in Network Science focus on the analysis and modelling of complex networks from the perspective of network structure, such as the centrality measures, the clustering coefficient, and motifs and graphlets, and they have become basic tools for studying and understanding graphs. In comparison, graph neural networks, especially graph convolutional networks (GCNs), are particularly effective at integrating node features into graph structures via neighbourhood aggregation and message passing, and have been shown to significantly improve the performances in a variety of learning tasks. These two classes of methods are, however, typically treated separately with limited references to each other. In this work, aiming to establish relationships between them, we provide a network science perspective of GCNs. Our novel taxonomy classifies GCNs from three structural information angles, i.e., the layer-wise message aggregation scope, the message content, and the overall learning scope. Moreover, as a prerequisite for reviewing GCNs via a network science perspective, we also summarise traditional structural measures and propose a new taxonomy for them. Finally and most importantly, we draw connections between traditional structural approaches and graph convolutional networks, and discuss potential directions for future research.
Understanding Difficulty-based Sample Weighting with a Universal Difficulty Measure
Venue: arXiv cs.LG 2023
Year: 2023

Sample weighting is widely used in deep learning. A large number of weighting methods essentially utilize the learning difficulty of training samples to calculate their weights. In this study, this scheme is called difficulty-based weighting. Two important issues arise when explaining this scheme. First, a unified difficulty measure that can be theoretically guaranteed for training samples does not exist. The learning difficulties of the samples are determined by multiple factors including noise level, imbalance degree, margin, and uncertainty. Nevertheless, existing measures only consider a single factor or in part, but not in their entirety. Second, a comprehensive theoretical explanation is lacking with respect to demonstrating why difficulty-based weighting schemes are effective in deep learning. In this study, we theoretically prove that the generalization error of a sample can be used as a universal difficulty measure. Furthermore, we provide formal theoretical justifications on the role of difficulty-based weighting for deep learning, consequently revealing its positive influences on both the optimization dynamics and generalization performance of deep models, which is instructive to existing weighting schemes.
Color-NeuraCrypt: Privacy-Preserving Color-Image Classification Using Extended Random Neural Networks
Venue: arXiv cs.CR 2023
Year: 2023

In recent years, with the development of cloud computing platforms, privacy-preserving methods for deep learning have become an urgent problem. NeuraCrypt is a private random neural network for privacy-preserving that allows data owners to encrypt the medical data before the data uploading, and data owners can train and then test their models in a cloud server with the encrypted data directly. However, we point out that the performance of NeuraCrypt is heavily degraded when using color images. In this paper, we propose a Color-NeuraCrypt to solve this problem. Experiment results show that our proposed Color-NeuraCrypt can achieve a better classification accuracy than the original one and other privacy-preserving methods.
Pylon: Semantic Table Union Search in Data Lakes
Venue: arXiv cs.DB 2023
Year: 2023

The large size and fast growth of data repositories, such as data lakes, has spurred the need for data discovery to help analysts find related data. The problem has become challenging as (i) a user typically does not know what datasets exist in an enormous data repository; and (ii) there is usually a lack of a unified data model to capture the interrelationships between heterogeneous datasets from disparate sources. In this work, we address one important class of discovery needs: finding union-able tables. The task is to find tables in a data lake that can be unioned with a given query table. The challenge is to recognize union-able columns even if they are represented differently. In this paper, we propose a data-driven learning approach: specifically, an unsupervised representation learning and embedding retrieval task. Our key idea is to exploit self-supervised contrastive learning to learn an embedding model that takes into account the indexing/search data structure and produces embeddings close by for columns with semantically similar values while pushing apart columns with semantically dissimilar values. We then find union-able tables based on similarities between their constituent columns in embedding space. On a real-world data lake, we demonstrate that our best-performing model achieves significant improvements in precision ($16\% \uparrow$), recall ($17\% \uparrow $), and query response time (7x faster) compared to the state-of-the-art.
Is Facebook regionally a small world network?
Venue: arXiv cs.SI 2023
Year: 2023

The analysis of social networks, can lead to important discoveries concerning society and trends. Can in fact imply the discovery of several new aspects of social behavior, as well as understanding the interest behind certain topics. Facebook, is now used worldwide, by approximately 3 billions of users, and has become one of the main sources of information. For analyzing facebook data, not only worldwide scales are important, but it is crucial to interpret local data behavior. In this paper we address and analyse Facebook at a regional dimensionality of Facebook, and evaluate the properties of regional Facebook as a small world network. To do this, we propose a novel approach a novel experimental setup, to simulate worldwide known Milgram six degrees of separation experiment. The novel repeated sampling random procedure proposed to reproduce the Milgram experiment showed promising and interesting results, allowing to evaluate the regional Facebook scale.
A Dataset of Kurdish (Sorani) Named Entities -- An Amendment to Kurdish-BLARK Named Entities
Venue: arXiv cs.CL 2023
Year: 2023

Named Entity Recognition (NER) is one of the essential applications of Natural Language Processing (NLP). It is also an instrument that plays a significant role in many other NLP applications, such as Machine Translation (MT), Information Retrieval (IR), and Part of Speech Tagging (POST). Kurdish is an under-resourced language from the NLP perspective. Particularly, in all the categories, the lack of NER resources hinders other aspects of Kurdish processing. In this work, we present a data set that covers several categories of NEs in Kurdish (Sorani). The dataset is a significant amendment to a previously developed dataset in the Kurdish BLARK (Basic Language Resource Kit). It covers 11 categories and 33261 entries in total. The dataset is publicly available for non-commercial use under CC BY-NC-SA 4.0 license at https://kurdishblark.github.io/.
Fairly Private: Investigating The Fairness of Visual Privacy Preservation Algorithms
Venue: arXiv cs.CV 2023
Year: 2023

As the privacy risks posed by camera surveillance and facial recognition have grown, so has the research into privacy preservation algorithms. Among these, visual privacy preservation algorithms attempt to impart bodily privacy to subjects in visuals by obfuscating privacy-sensitive areas. While disparate performances of facial recognition systems across phenotypes are the subject of much study, its counterpart, privacy preservation, is not commonly analysed from a fairness perspective. In this paper, the fairness of commonly used visual privacy preservation algorithms is investigated through the performances of facial recognition models on obfuscated images. Experiments on the PubFig dataset clearly show that the privacy protection provided is unequal across groups.
MotorFactory: A Blender Add-on for Large Dataset Generation of Small Electric Motors
Venue: arXiv cs.RO 2023
Year: 2023

To enable automatic disassembly of different product types with uncertain conditions and degrees of wear in remanufacturing, agile production systems that can adapt dynamically to changing requirements are needed. Machine learning algorithms can be employed due to their generalization capabilities of learning from various types and variants of products. However, in reality, datasets with a diversity of samples that can be used to train models are difficult to obtain in the initial period. This may cause bad performances when the system tries to adapt to new unseen input data in the future. In order to generate large datasets for different learning purposes, in our project, we present a Blender add-on named MotorFactory to generate customized mesh models of various motor instances. MotorFactory allows to create mesh models which, complemented with additional add-ons, can be further used to create synthetic RGB images, depth images, normal images, segmentation ground truth masks, and 3D point cloud datasets with point-wise semantic labels. The created synthetic datasets may be used for various tasks including motor type classification, object detection for decentralized material transfer tasks, part segmentation for disassembly and handling tasks, or even reinforcement learning-based robotics control or view-planning.
Persistence-Based Discretization for Learning Discrete Event Systems from Time Series
Venue: arXiv cs.AI 2023
Year: 2023

To get a good understanding of a dynamical system, it is convenient to have an interpretable and versatile model of it. Timed discrete event systems are a kind of model that respond to these requirements. However, such models can be inferred from timestamped event sequences but not directly from numerical data. To solve this problem, a discretization step must be done to identify events or symbols in the time series. Persist is a discretization method that intends to create persisting symbols by using a score called persistence score. This allows to mitigate the risk of undesirable symbol changes that would lead to a too complex model. After the study of the persistence score, we point out that it tends to favor excessive cases making it miss interesting persisting symbols. To correct this behavior, we replace the metric used in the persistence score, the Kullback-Leibler divergence, with the Wasserstein distance. Experiments show that the improved persistence score enhances Persist's ability to capture the information of the original time series and that it makes it better suited for discrete event systems learning.
Study of JavaScript Static Analysis Tools for Vulnerability Detection in Node.js Packages
Venue: arXiv cs.CR 2023
Year: 2023

With the emergence of the Node.js ecosystem, JavaScript has become a widely-used programming language for implementing server-side web applications. In this paper, we present the first empirical study of static code analysis tools for detecting vulnerabilities in Node.js code. To conduct a comprehensive tool evaluation, we created the largest known curated dataset of Node.js code vulnerabilities. We characterized and annotated a set of 957 vulnerabilities by analyzing information contained in npm advisory reports. We tested nine different tools and found that many important vulnerabilities appearing in the OWASP Top-10 are not detected by any tool. The three best performing tools combined only detect up to 57.6% of all vulnerabilities in the dataset, but at a very low precision of 0.11%. Our curated dataset offers a new benchmark to help characterize existing Node.js code vulnerabilities and foster the development of better vulnerability detection tools for Node.js code.
Explaining $\mathcal{ELH}$ Concept Descriptions through Counterfactual Reasoning
Venue: arXiv cs.AI 2023
Year: 2023

Knowledge bases are widely used for information management, enabling high-impact applications such as web search, question answering, and natural language processing. They also serve as the backbone for automatic decision systems, e.g., for medical diagnostics and credit scoring. As stakeholders affected by these decisions would like to understand their situation and verify how fair the decisions are, a number of explanation approaches have been proposed. An intrinsically transparent way to do classification is by using concepts in description logics. However, these concepts can become long and difficult to fathom for non-experts, even when verbalized. One solution is to employ counterfactuals to answer the question, ``How must feature values be changed to obtain a different classification?'' By focusing on the minimal feature changes, the explanations are short, human-friendly, and provide a clear path of action regarding the change in prediction. While previous work investigated counterfactuals for tabular data, in this paper, we transfer the notion of counterfactuals to knowledge bases and the description logic $\mathcal{ELH}$. Our approach starts by generating counterfactual candidates from concepts, followed by selecting the candidates requiring the fewest feature changes as counterfactuals. When multiple counterfactuals exist, we rank them based on the likeliness of their feature combinations. We evaluate our method by conducting a user survey to determine which counterfactual candidates participants prefer for explanation.
HEP-BNN: A Framework for Finding Low-Latency Execution Configurations of BNNs on Heterogeneous Multiprocessor Platforms
Venue: arXiv cs.DC 2023
Year: 2023

Binarized Neural Networks (BNNs) significantly reduce the computation and memory demands with binarized weights and activations compared to full-precision NNs. Executing a layer in a BNN on different devices of a heterogeneous multiprocessor platform consisting of CPU and GPU can affect the inference performance, i.e., accuracy and latency. Usually, a heterogeneous HW platform consisting of a CPU and a GPU is available to execute the BNN workloads. However, to use the heterogeneous HW effectively, it is necessary to find an efficient strategy for BNN workload mapping. In this work, we propose a framework that generates efficient BNN layer-to-device mappings (i.e. suitable parallel configuration for each layer of the model) for execution platforms comprised of CPU and CUDA-capable GPU. We evaluate our proposed framework with two BNN architectures using two well-known datasets, Fashion-MNIST and CIFAR-10, on three hardware platforms with different characteristics. The results show that compared to running a fully-parallelized GPU implementation, our framework generates an efficient configuration up to 2x, 2.6x and 11.8x faster on our tested hardware respectively.
Toward Theoretical Guidance for Two Common Questions in Practical Cross-Validation based Hyperparameter Selection
Venue: arXiv cs.LG 2023
Year: 2023

We show, to our knowledge, the first theoretical treatments of two common questions in cross-validation based hyperparameter selection: (1) After selecting the best hyperparameter using a held-out set, we train the final model using {\em all} of the training data -- since this may or may not improve future generalization error, should one do this? (2) During optimization such as via SGD (stochastic gradient descent), we must set the optimization tolerance $ρ$ -- since it trades off predictive accuracy with computation cost, how should one set it? Toward these problems, we introduce the {\em hold-in risk} (the error due to not using the whole training data), and the {\em model class mis-specification risk} (the error due to having chosen the wrong model class) in a theoretical view which is simple, general, and suggests heuristics that can be used when faced with a dataset instance. In proof-of-concept studies in synthetic data where theoretical quantities can be controlled, we show that these heuristics can, respectively, (1) always perform at least as well as always performing retraining or never performing retraining, (2) either improve performance or reduce computational overhead by $2\times$ with no loss in predictive performance.
Is AI Art Another Industrial Revolution in the Making?
Venue: arXiv cs.AI 2023
Year: 2023

A major shift from skilled to unskilled workers was one of the many changes caused by the Industrial Revolution, when the switch to machines contributed to decline in the social and economic status of artisans, whose skills were dismembered into discrete actions by factory-line workers. We consider what may be an analogous computing technology: the recent introduction of AI-generated art software. AI art generators such as Dall-E and Midjourney can create fully rendered images based solely on a user's prompt, just at the click of a button. Some artists fear if the cheaper price and conveyor-belt speed that comes with AI-produced images is seen as an improvement to the current system, it may permanently change the way society values/views art and artists. In this article, we consider the implications that AI art generation introduces through a post-industrial revolution historical lens. We then reflect on the analogous issues that appear to arise as a result of the AI art revolution, and we conclude that the problems raised mirror those of industrialization, giving a vital glimpse into what may lie ahead.
Mephisto: A Framework for Portable, Reproducible, and Iterative Crowdsourcing
Venue: arXiv cs.AI 2023
Year: 2023

We introduce Mephisto, a framework to make crowdsourcing for research more reproducible, transparent, and collaborative. Mephisto provides abstractions that cover a broad set of task designs and data collection workflows, and provides a simple user experience to make best-practices easy defaults. In this whitepaper we discuss the current state of data collection and annotation in ML research, establish the motivation for building a shared framework to enable researchers to create and open-source data collection and annotation tools as part of their publication, and outline a set of suggested requirements for a system to facilitate these goals. We then step through our resolution in Mephisto, explaining the abstractions we use, our design decisions around the user experience, and share implementation details and where they align with the original motivations. We also discuss current limitations, as well as future work towards continuing to deliver on the framework's initial goals. Mephisto is available as an open source project, and its documentation can be found at www.mephisto.ai.
Signed Directed Graph Contrastive Learning with Laplacian Augmentation
Venue: arXiv cs.LG 2023
Year: 2023

Graph contrastive learning has become a powerful technique for several graph mining tasks. It learns discriminative representation from different perspectives of augmented graphs. Ubiquitous in our daily life, singed-directed graphs are the most complex and tricky to analyze among various graph types. That is why singed-directed graph contrastive learning has not been studied much yet, while there are many contrastive studies for unsigned and undirected. Thus, this paper proposes a novel signed-directed graph contrastive learning, SDGCL. It makes two different structurally perturbed graph views and gets node representations via magnetic Laplacian perturbation. We use a node-level contrastive loss to maximize the mutual information between the two graph views. The model is jointly learned with contrastive and supervised objectives. The graph encoder of SDGCL does not depend on social theories or predefined assumptions. Therefore it does not require finding triads or selecting neighbors to aggregate. It leverages only the edge signs and directions via magnetic Laplacian. To the best of our knowledge, it is the first to introduce magnetic Laplacian perturbation and signed spectral graph contrastive learning. The superiority of the proposed model is demonstrated through exhaustive experiments on four real-world datasets. SDGCL shows better performance than other state-of-the-art on four evaluation metrics.