OpenRaiser/Intern-Atlas huggingface dataset:
Political Bias and Factualness in News Sharing across more than 100,000 Online Communities
Venue: arXiv cs.CY 2022
Year: 2022

As civil discourse increasingly takes place online, misinformation and the polarization of news shared in online communities have become ever more relevant concerns with real world harms across our society. Studying online news sharing at scale is challenging due to the massive volume of content which is shared by millions of users across thousands of communities. Therefore, existing research has largely focused on specific communities or specific interventions, such as bans. However, understanding the prevalence and spread of misinformation and polarization more broadly, across thousands of online communities, is critical for the development of governance strategies, interventions, and community design. Here, we conduct the largest study of news sharing on reddit to date, analyzing more than 550 million links spanning 4 years. We use non-partisan news source ratings from Media Bias/Fact Check to annotate links to news sources with their political bias and factualness. We find that, compared to left-leaning communities, right-leaning communities have 105% more variance in the political bias of their news sources, and more links to relatively-more biased sources, on average. We observe that reddit users' voting and re-sharing behaviors generally decrease the visibility of extremely biased and low factual content, which receives 20% fewer upvotes and 30% fewer exposures from crossposts than more neutral or more factual content. This suggests that reddit is more resilient to low factual content than Twitter. We show that extremely biased and low factual content is very concentrated, with 99% of such content being shared in only 0.5% of communities, giving credence to the recent strategy of community-wide bans and quarantines.
LIRA-V: Lightweight Remote Attestation for Constrained RISC-V Devices
Venue: arXiv cs.CR 2022
Year: 2022

This paper presents LIRA-V, a lightweight system for performing remote attestation between constrained devices using the RISC-V architecture. We propose using read-only memory and the RISC-V Physical Memory Protection (PMP) primitive to build a trust anchor for remote attestation and secure channel creation. Moreover, we show how LIRA-V can be used for trusted communication between two devices using mutual attestation. We present the design, implementation and evaluation of LIRA-V using an off-the-shelf RISC-V microcontroller and present performance results to demonstrate its suitability. To our knowledge, we present the first remote attestation mechanism suitable for constrained RISC-V devices, with applications to cyber-physical systems and Internet of Things (IoT) devices.
Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs
Venue: arXiv cs.LG 2022
Year: 2022

Learning Markov decision processes (MDPs) in the presence of the adversary is a challenging problem in reinforcement learning (RL). In this paper, we study RL in episodic MDPs with adversarial reward and full information feedback, where the unknown transition probability function is a linear function of a given feature mapping, and the reward function can change arbitrarily episode by episode. We propose an optimistic policy optimization algorithm POWERS and show that it can achieve $\tilde{O}(dH\sqrt{T})$ regret, where $H$ is the length of the episode, $T$ is the number of interactions with the MDP, and $d$ is the dimension of the feature mapping. Furthermore, we also prove a matching lower bound of $\tildeΩ(dH\sqrt{T})$ up to logarithmic factors. Our key technical contributions are two-fold: (1) a new value function estimator based on importance weighting; and (2) a tighter confidence set for the transition kernel. They together lead to the nearly minimax optimal regret.
Facing to Latency of Hyperledger Fabric for Blockchain-enabled IoT: Modeling and Analysis
Venue: arXiv cs.DC 2022
Year: 2022

Hyperledger Fabric (HLF), one of the most popular private blockchains, has recently received attention for blockchain-enabled Internet of Things (IoT). However, for IoT applications to handle time-sensitive data, the processing latency in HLF has emerged as a new challenge. In this article, therefore, we establish a practical HLF latency model for HLF-enabled IoT. We first discuss the structure and transaction flow of HLF-enabled IoT. After implementing real HLF, we capture the latencies that each transaction experiences and show that the total latency of HLF can be modeled as a Gamma distribution, which is validated by conducting a goodness-of-fit test (i.e., the Kolmogorov-Smirnov (KS) test). We also provide the parameter values of the modeled latency distribution for various HLF environments. Furthermore, we explore the impacts of three important HLF parameters including transaction generation rate, block size, and block-generation timeout on the HLF latency. As a result, this article provides design insights on minimizing the latency for HLF-enabled IoT.
Biometrics in the Era of COVID-19: Challenges and Opportunities
Venue: arXiv cs.CY 2022
Year: 2022

Since early 2020 the COVID-19 pandemic has had a considerable impact on many aspects of daily life. A range of different measures have been implemented worldwide to reduce the rate of new infections and to manage the pressure on national health services. A primary strategy has been to reduce gatherings and the potential for transmission through the prioritisation of remote working and education. Enhanced hand hygiene and the use of facial masks have decreased the spread of pathogens when gatherings are unavoidable. These particular measures present challenges for reliable biometric recognition, e.g. for facial-, voice- and hand-based biometrics. At the same time, new challenges create new opportunities and research directions, e.g. renewed interest in non-constrained iris or periocular recognition, touch-less fingerprint- and vein-based authentication and the use of biometric characteristics for disease detection. This article presents an overview of the research carried out to address those challenges and emerging opportunities.
Combinatorial optimization and reasoning with graph neural networks
Venue: arXiv cs.LG 2022
Year: 2022

Combinatorial optimization is a well-established area in operations research and computer science. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning, especially graph neural networks (GNNs), as a key building block for combinatorial tasks, either directly as solvers or by enhancing exact solvers. The inductive bias of GNNs effectively encodes combinatorial and relational input due to their invariance to permutations and awareness of input sparsity. This paper presents a conceptual review of recent key advancements in this emerging field, aiming at optimization and machine learning researchers.
A Taxonomy of Assets for the Development of Software-Intensive Products and Services
Venue: arXiv cs.SE 2022
Year: 2022

Context: Developing software-intensive products or services usually involves a plethora of software artefacts. Assets are artefacts intended to be used more than once and have value for organisations; examples include test cases, code, requirements, and documentation. During the development process, assets might degrade, affecting the effectiveness and efficiency of the development process. Therefore, assets are an investment that requires continuous management. Identifying assets is the first step for their effective management. However, there is a lack of awareness of what assets and types of assets are common in software-developing organisations. Most types of assets are understudied, and their state of quality and how they degrade over time have not been well-understood. Method: We perform a systematic literature review and a field study at five companies to study and identify assets to fill the gap in research. The results were analysed qualitatively and summarised in a taxonomy. Results: We create the first comprehensive, structured, yet extendable taxonomy of assets, containing 57 types of assets. Conclusions: The taxonomy serves as a foundation for identifying assets that are relevant for an organisation and enables the study of asset management and asset degradation concepts.
Parallel algorithms for power circuits and the word problem of the Baumslag group
Venue: arXiv cs.CC 2022
Year: 2022

Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and $(x,y) \mapsto x\cdot 2^y$. The same authors applied power circuits to give a polynomial-time solution to the word problem of the Baumslag group, which has a non-elementary Dehn function. In this work, we examine power circuits and the word problem of the Baumslag group under parallel complexity aspects. In particular, we establish that the word problem of the Baumslag group can be solved in NC - even though one of the essential steps is to compare two integers given by power circuits and this, in general, is shown to be P-complete. The key observation is that the depth of the occurring power circuits is logarithmic and such power circuits can be compared in NC.
Deep Decomposition Network for Image Processing: A Case Study for Visible and Infrared Image Fusion
Venue: arXiv cs.CV 2022
Year: 2022

Image decomposition is a crucial subject in the field of image processing. It can extract salient features from the source image. We propose a new image decomposition method based on convolutional neural network. This method can be applied to many image processing tasks. In this paper, we apply the image decomposition network to the image fusion task. We input infrared image and visible light image and decompose them into three high-frequency feature images and a low-frequency feature image respectively. The two sets of feature images are fused using a specific fusion strategy to obtain fusion feature images. Finally, the feature images are reconstructed to obtain the fused image. Compared with the state-of-the-art fusion methods, this method has achieved better performance in both subjective and objective evaluation.
Mobility-Aware Routing and Caching: A Federated Learning Assisted Approach
Venue: arXiv cs.IT 2022
Year: 2022

We consider a service cost minimization problem for resource-constrained small-cell networks with caching, where the challenge mainly stems from (i) the insufficient backhaul capacity and limited network bandwidth and (ii) the limited storing capacity of small-cell base stations (SBSs). Besides, the optimization problem is NP-hard since both the users' mobility patterns and content preferences are unknown. In this paper, we develop a novel mobility-aware joint routing and caching strategy to address the challenges. The designed framework divides the entire geographical area into small sections containing one SBS and several MUs. Based on the concept of one-stop-shop (OSS), we propose a federated routing and popularity learning (FRPL) approach in which the SBSs cooperatively learn the routing and preference of their respective MUs and make a caching decision. The FRPL method completes multiple tasks in one shot, thus reducing the average processing time per global aggregation of learning. By exploiting the outcomes of FRPL together with the estimated service edge of SBSs, the proposed cache placement solution greedily approximates the minimizer of the challenging service cost optimization problem. Theoretical and numerical analyses show the effectiveness of our proposed approaches.
Self-Supervised Learning of Graph Neural Networks: A Unified Review
Venue: arXiv cs.LG 2022
Year: 2022

Deep models trained in supervised mode have achieved remarkable success on a variety of tasks. When labeled samples are limited, self-supervised learning (SSL) is emerging as a new paradigm for making use of large amounts of unlabeled samples. SSL has achieved promising performance on natural language and image learning tasks. Recently, there is a trend to extend such success to graph data using graph neural networks (GNNs). In this survey, we provide a unified review of different ways of training GNNs using SSL. Specifically, we categorize SSL methods into contrastive and predictive models. In either category, we provide a unified framework for methods as well as how these methods differ in each component under the framework. Our unified treatment of SSL methods for GNNs sheds light on the similarities and differences of various methods, setting the stage for developing new methods and algorithms. We also summarize different SSL settings and the corresponding datasets used in each setting. To facilitate methodological development and empirical comparison, we develop a standardized testbed for SSL in GNNs, including implementations of common baseline methods, datasets, and evaluation metrics.
Local Calibration: Metrics and Recalibration
Venue: arXiv cs.LG 2022
Year: 2022

Probabilistic classifiers output confidence scores along with their predictions, and these confidence scores should be calibrated, i.e., they should reflect the reliability of the prediction. Confidence scores that minimize standard metrics such as the expected calibration error (ECE) accurately measure the reliability on average across the entire population. However, it is in general impossible to measure the reliability of an individual prediction. In this work, we propose the local calibration error (LCE) to span the gap between average and individual reliability. For each individual prediction, the LCE measures the average reliability of a set of similar predictions, where similarity is quantified by a kernel function on a pretrained feature space and by a binning scheme over predicted model confidences. We show theoretically that the LCE can be estimated sample-efficiently from data, and empirically find that it reveals miscalibration modes that are more fine-grained than the ECE can detect. Our key result is a novel local recalibration method LoRe, to improve confidence scores for individual predictions and decrease the LCE. Experimentally, we show that our recalibration method produces more accurate confidence scores, which improves downstream fairness and decision making on classification tasks with both image and tabular data.
Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
Venue: arXiv cs.DS 2022
Year: 2022

Given a set of well-formed terminal pairs on the external face of an undirected planar graph with unit edge weights, we give a linear-time algorithm for computing the union of non-crossing shortest paths joining each terminal pair, where well-formed means that such a set of non-crossing paths exists. This allows us to compute distances between each terminal pair, within the same time bound. We also give a novel concept of incremental shortest path subgraph of a planar graph, i.e., a partition of the planar embedding in subregions that preserve distances, that can be of interest itself.
Unifying Hidden-Variable Problems from Quantum Mechanics by Logics of Dependence and Independence
Venue: arXiv cs.LO 2022
Year: 2022

We study hidden-variable models from quantum mechanics, and their abstractions in purely probabilistic and relational frameworks, by means of logics of dependence and independence, based on team semantics. We show that common desirable properties of hidden-variable models can be defined in an elegant and concise way in dependence and independence logic. The relationship between different properties, and their simultaneous realisability can thus been formulated and a proved on a purely logical level, as problems of entailment and satisfiability of logical formulae. Connections between probabilistic and relational entailment in dependence and independence logic allow us to simplify proofs. In many cases, we can establish results on both probabilistic and relational hidden-variable models by a single proof, because one case implies the other, depending on purely syntactic criteria. We also discuss the no-go theorems by Bell and Kochen-Specker and provide a purely logical variant of the latter, introducing non-contextual choice as a team-semantical property.
Analysis of Evolutionary Diversity Optimisation for Permutation Problems
Venue: arXiv cs.NE 2022
Year: 2022

Generating diverse populations of high quality solutions has gained interest as a promising extension to the traditional optimization tasks. This work contributes to this line of research with an investigation on evolutionary diversity optimization for three of the most well-studied permutation problems, namely the Traveling Salesperson Problem (TSP), both symmetric and asymmetric variants, and Quadratic Assignment Problem (QAP). It includes an analysis of the worst-case performance of a simple mutation-only evolutionary algorithm with different mutation operators, using an established diversity measure. Theoretical results show many mutation operators for these problems guarantee convergence to maximally diverse populations of sufficiently small size within cubic to quartic expected run-time. On the other hand, the result on QAP suggests that strong mutations give poor worst-case performance, as mutation strength contributes exponentially to the expected run-time. Additionally, experiments are carried out on QAPLIB and synthetic instances in unconstrained and constrained settings, and reveal much more optimistic practical performances, while corroborating the theoretical finding regarding mutation strength. These results should serve as a baseline for future studies.
Deep Deterministic Uncertainty: A Simple Baseline
Venue: arXiv cs.LG 2022
Year: 2022

Reliable uncertainty from deterministic single-forward pass models is sought after because conventional methods of uncertainty quantification are computationally expensive. We take two complex single-forward-pass uncertainty approaches, DUQ and SNGP, and examine whether they mainly rely on a well-regularized feature space. Crucially, without using their more complex methods for estimating uncertainty, a single softmax neural net with such a feature-space, achieved via residual connections and spectral normalization, *outperforms* DUQ and SNGP's epistemic uncertainty predictions using simple Gaussian Discriminant Analysis *post-training* as a separate feature-space density estimator -- without fine-tuning on OoD data, feature ensembling, or input pre-procressing. This conceptually simple *Deep Deterministic Uncertainty (DDU)* baseline can also be used to disentangle aleatoric and epistemic uncertainty and performs as well as Deep Ensembles, the state-of-the art for uncertainty prediction, on several OoD benchmarks (CIFAR-10/100 vs SVHN/Tiny-ImageNet, ImageNet vs ImageNet-O) as well as in active learning settings across different model architectures, yet is *computationally cheaper*.
Accelerating Communication for Parallel Programming Models on GPU Systems
Venue: arXiv cs.DC 2022
Year: 2022

As an increasing number of leadership-class systems embrace GPU accelerators in the race towards exascale, efficient communication of GPU data is becoming one of the most critical components of high-performance computing. For developers of parallel programming models, implementing support for GPU-aware communication using native APIs for GPUs such as CUDA can be a daunting task as it requires considerable effort with little guarantee of performance. In this work, we demonstrate the capability of the Unified Communication X (UCX) framework to compose a GPU-aware communication layer that serves multiple parallel programming models of the Charm++ ecosystem: Charm++, Adaptive MPI (AMPI), and Charm4py. We demonstrate the performance impact of our designs with microbenchmarks adapted from the OSU benchmark suite, obtaining improvements in latency of up to 10.1x in Charm++, 11.7x in AMPI, and 17.4x in Charm4py. We also observe increases in bandwidth of up to 10.1x in Charm++, 10x in AMPI, and 10.5x in Charm4py. We show the potential impact of our designs on real-world applications by evaluating a proxy application for the Jacobi iterative method, improving the communication performance by up to 12.4x in Charm++, 12.8x in AMPI, and 19.7x in Charm4py.
Information Directed Reward Learning for Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

For many reinforcement learning (RL) applications, specifying a reward is difficult. This paper considers an RL setting where the agent obtains information about the reward only by querying an expert that can, for example, evaluate individual states or provide binary preferences over trajectories. From such expensive feedback, we aim to learn a model of the reward that allows standard RL algorithms to achieve high expected returns with as few expert queries as possible. To this end, we propose Information Directed Reward Learning (IDRL), which uses a Bayesian model of the reward and selects queries that maximize the information gain about the difference in return between plausibly optimal policies. In contrast to prior active reward learning methods designed for specific types of queries, IDRL naturally accommodates different query types. Moreover, it achieves similar or better performance with significantly fewer queries by shifting the focus from reducing the reward approximation error to improving the policy induced by the reward model. We support our findings with extensive evaluations in multiple environments and with different query types.
SAT-based Circuit Local Improvement
Venue: arXiv cs.AI 2022
Year: 2022

Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of this behavior is that the search space is enormous: the number of circuits of size $s$ is $s^{Θ(s)}$, the number of Boolean functions on $n$ variables is $2^{2^n}$. In this paper, we explore the following natural heuristic idea for decreasing the size of a given circuit: go through all its subcircuits of moderate size and check whether any of them can be improved by reducing to SAT. This may be viewed as a local search approach: we search for a smaller circuit in a ball around a given circuit. Through this approach, we prove new upper bounds on the circuit size of various symmetric functions. We also demonstrate that some upper bounds that were proved by hand decades ago, nowadays can be found automatically in a few seconds.
Contrastive Pre-training for Imbalanced Corporate Credit Ratings
Venue: arXiv cs.LG 2022
Year: 2022

Corporate credit rating reflects the level of corporate credit and plays a crucial role in modern financial risk control. But real-world credit rating data usually shows long-tail distributions, which means heavy class imbalanced problem challenging the corporate credit rating system greatly. To tackle that, inspried by the recent advances of pre-train techniques in self-supervised representation learning, we propose a novel framework named Contrastive Pre-training for Corporate Credit Rating (CP4CCR), which utilizes the self-surpervision for getting over class imbalance. Specifically, we propose to, in the first phase, exert constrastive self-superivised pre-training without label information, which want to learn a better class-agnostic initialization. During this phase, two self-supervised task are developed within CP4CCR: (i) Feature Masking (FM) and (ii) Feature Swapping(FS). In the second phase, we can train any standard corporate redit rating model initialized by the pre-trained network. Extensive experiments conducted on the Chinese public-listed corporate rating dataset, prove that CP4CCR can improve the performance of standard corporate credit rating models, especially for class with few samples.