OpenRaiser/Intern-Atlas huggingface dataset:
Boosting-GNN: Boosting Algorithm for Graph Networks on Imbalanced Node Classification
Venue: arXiv cs.LG 2022
Year: 2022

The Graph Neural Network (GNN) has been widely used for graph data representation. However, the existing researches only consider the ideal balanced dataset, and the imbalanced dataset is rarely considered. Traditional methods such as resampling, reweighting, and synthetic samples that deal with imbalanced datasets are no longer applicable in GNN. This paper proposes an ensemble model called Boosting-GNN, which uses GNNs as the base classifiers during boosting. In Boosting-GNN, higher weights are set for the training samples that are not correctly classified by the previous classifier, thus achieving higher classification accuracy and better reliability. Besides, transfer learning is used to reduce computational cost and increase fitting ability. Experimental results indicate that the proposed Boosting-GNN model achieves better performance than GCN, GraphSAGE, GAT, SGC, N-GCN, and most advanced reweighting and resampling methods on synthetic imbalanced datasets, with an average performance improvement of 4.5%
A generalized configuration model with triadic closure
Venue: arXiv cs.SI 2022
Year: 2022

In this paper we present a generalized configuration model with random triadic closure (GCTC). This model possesses five fundamental properties: large clustering coefficient, power law degree distribution, short path length, non-zero Pearson degree correlation, and existence of community structures. We analytically derive the Pearson degree correlation coefficient and the clustering coefficient of the proposed model. We select a few datasets of real-world networks. By simulation, we show that the GCTC model matches very well with the datasets in terms of Pearson degree correlations and clustering coefficients. We also test three well-known community detection algorithms on our model, the datasets and other three prevalent benchmark models. We show that the GCTC model performs equally well as the other three benchmark models. Finally, we perform influence diffusion on the GCTC model using the independent cascade model and the linear threshold model. We show that the influence spreads of the GCTC model are much closer to those of the datasets than the other benchmark models. This suggests that the GCTC model is a suitable tool to study network science problems where degree correlation or clustering plays an important role.
The Component Diagnosability of General Networks
Venue: arXiv cs.DC 2022
Year: 2022

The processor failures in a multiprocessor system have a negative impact on its distributed computing efficiency. Because of the rapid expansion of multiprocessor systems, the importance of fault diagnosis is becoming increasingly prominent. The $h$-component diagnosability of $G$, denoted by $ct_{h}(G)$, is the maximum number of nodes of the faulty set $F$ that is correctly identified in a system, and the number of components in $G-F$ is at least $h$. In this paper, we determine the $(h+1)$-component diagnosability of general networks under the PMC model and MM$^{*}$ model. As applications, the component diagnosability is explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, hierarchical hypercubes, Cayley graphs generated by transposition trees (except star graphs), and DQcube as well. Furthermore, we provide some comparison results between the component diagnosability and other fault diagnosabilities.
On learning parametric distributions from quantized samples
Venue: arXiv cs.IT 2022
Year: 2022

We consider the problem of learning parametric distributions from their quantized samples in a network. Specifically, $n$ agents or sensors observe independent samples of an unknown parametric distribution; and each of them uses $k$ bits to describe its observed sample to a central processor whose goal is to estimate the unknown distribution. First, we establish a generalization of the well-known van Trees inequality to general $L_p$-norms, with $p > 1$, in terms of Generalized Fisher information. Then, we develop minimax lower bounds on the estimation error for two losses: general $L_p$-norms and the related Wasserstein loss from optimal transport.
Density estimation on low-dimensional manifolds: an inflation-deflation approach
Venue: arXiv cs.LG 2022
Year: 2022

Normalizing Flows (NFs) are universal density estimators based on Neural Networks. However, this universality is limited: the density's support needs to be diffeomorphic to a Euclidean space. In this paper, we propose a novel method to overcome this limitation without sacrificing universality. The proposed method inflates the data manifold by adding noise in the normal space, trains an NF on this inflated manifold, and, finally, deflates the learned density. Our main result provides sufficient conditions on the manifold and the specific choice of noise under which the corresponding estimator is exact. Our method has the same computational complexity as NFs and does not require computing an inverse flow. We also show that, if the embedding dimension is much larger than the manifold dimension, noise in the normal space can be well approximated by Gaussian noise. This allows using our method for approximating arbitrary densities on unknown manifolds provided that the manifold dimension is known.
D2CFR: Minimize Counterfactual Regret with Deep Dueling Neural Network
Venue: arXiv cs.AI 2022
Year: 2022

Counterfactual Regret Minimization (CFR)} is the popular method for finding approximate Nash equilibrium in two-player zero-sum games with imperfect information. CFR solves games by travsersing the full game tree iteratively, which limits its scalability in larger games. When applying CFR to solve large-scale games in previously, large-scale games are abstracted into small-scale games firstly. Secondly, CFR is used to solve the abstract game. And finally, the solution strategy is mapped back to the original large-scale game. However, this process requires considerable expert knowledge, and the accuracy of abstraction is closely related to expert knowledge. In addition, the abstraction also loses certain information, which will eventually affect the accuracy of the solution strategy. Towards this problem, a recent method, \textit{Deep CFR} alleviates the need for abstraction and expert knowledge by applying deep neural networks directly to CFR in full games. In this paper, we introduces \textit{Neural Network Counterfactual Regret Minimization (NNCFR)}, an improved variant of \textit{Deep CFR} that has a faster convergence by constructing a dueling netwok as the value network. Moreover, an evaluation module is designed by combining the value network and Monte Carlo, which reduces the approximation error of the value network. In addition, a new loss function is designed in the procedure of training policy network in the proposed \textit{NNCFR}, which can be good to make the policy network more stable. The extensive experimental tests are conducted to show that the \textit{NNCFR} converges faster and performs more stable than \textit{Deep CFR}, and outperforms \textit{Deep CFR} with respect to exploitability and head-to-head performance on test games.
The Graph Cut Kernel for Ranked Data
Venue: arXiv cs.LG 2022
Year: 2022

Many algorithms for ranked data become computationally intractable as the number of objects grows due to the complex geometric structure induced by rankings. An additional challenge is posed by partial rankings, i.e. rankings in which the preference is only known for a subset of all objects. For these reasons, state-of-the-art methods cannot scale to real-world applications, such as recommender systems. We address this challenge by exploiting the geometric structure of ranked data and additional available information about the objects to derive a kernel for ranking based on the graph cut function. The graph cut kernel combines the efficiency of submodular optimization with the theoretical properties of kernel-based methods. The graph cut kernel combines the efficiency of submodular optimization with the theoretical properties of kernel-based methods.
Adapting Software Architectures to Machine Learning Challenges
Venue: arXiv cs.SE 2022
Year: 2022

Unique developmental and operational characteristics of ML components as well as their inherent uncertainty demand robust engineering principles are used to ensure their quality. We aim to determine how software systems can be (re-) architected to enable robust integration of ML components. Towards this goal, we conducted a mixed-methods empirical study consisting of (i) a systematic literature review to identify the challenges and their solutions in software architecture for ML, (ii) semi-structured interviews with practitioners to qualitatively complement the initial findings and (iii) a survey to quantitatively validate the challenges and their solutions. We compiled and validated twenty challenges and solutions for (re-) architecting systems with ML components. Our results indicate, for example, that traditional software architecture challenges (e.g., component coupling) also play an important role when using ML components; along with new ML specific challenges (e.g., the need for continuous retraining). Moreover, the results indicate that ML heightened decision drivers, such as privacy, play a marginal role compared to traditional decision drivers, such as scalability. Using the survey we were able to establish a link between architectural solutions and software quality attributes, which enabled us to provide twenty architectural tactics used to satisfy individual quality requirements of systems with ML components. Altogether, the results of the study can be interpreted as an empirical framework that supports the process of (re-) architecting software systems with ML components.
YOLO5Face: Why Reinventing a Face Detector
Venue: arXiv cs.CV 2022
Year: 2022

Tremendous progress has been made on face detection in recent years using convolutional neural networks. While many face detectors use designs designated for detecting faces, we treat face detection as a generic object detection task. We implement a face detector based on the YOLOv5 object detector and call it YOLO5Face. We make a few key modifications to the YOLOv5 and optimize it for face detection. These modifications include adding a five-point landmark regression head, using a stem block at the input of the backbone, using smaller-size kernels in the SPP, and adding a P6 output in the PAN block. We design detectors of different model sizes, from an extra-large model to achieve the best performance to a super small model for real-time detection on an embedded or mobile device. Experiment results on the WiderFace dataset show that on VGA images, our face detectors can achieve state-of-the-art performance in almost all the Easy, Medium, and Hard subsets, exceeding the more complex designated face detectors. The code is available at \url{https://github.com/deepcam-cn/yolov5-face}
Tight Lower Bounds for $α$-Divergences Under Moment Constraints and Relations Between Different $α$
Venue: arXiv cs.IT 2022
Year: 2022

The $α$-divergences include the well-known Kullback-Leibler divergence, Hellinger distance and $χ^2$-divergence. In this paper, we derive differential and integral relations between the $α$-divergences that are generalizations of the relation between the Kullback-Leibler divergence and the $χ^2$-divergence. We also show tight lower bounds for the $α$-divergences under given means and variances. In particular, we show a necessary and sufficient condition such that the binary divergences, which are divergences between probability measures on the same $2$-point set, always attain lower bounds. Kullback-Leibler divergence, Hellinger distance, and $χ^2$-divergence satisfy this condition.
Enhanced Doubly Robust Learning for Debiasing Post-click Conversion Rate Estimation
Venue: arXiv cs.LG 2022
Year: 2022

Post-click conversion, as a strong signal indicating the user preference, is salutary for building recommender systems. However, accurately estimating the post-click conversion rate (CVR) is challenging due to the selection bias, i.e., the observed clicked events usually happen on users' preferred items. Currently, most existing methods utilize counterfactual learning to debias recommender systems. Among them, the doubly robust (DR) estimator has achieved competitive performance by combining the error imputation based (EIB) estimator and the inverse propensity score (IPS) estimator in a doubly robust way. However, inaccurate error imputation may result in its higher variance than the IPS estimator. Worse still, existing methods typically use simple model-agnostic methods to estimate the imputation error, which are not sufficient to approximate the dynamically changing model-correlated target (i.e., the gradient direction of the prediction model). To solve these problems, we first derive the bias and variance of the DR estimator. Based on it, a more robust doubly robust (MRDR) estimator has been proposed to further reduce its variance while retaining its double robustness. Moreover, we propose a novel double learning approach for the MRDR estimator, which can convert the error imputation into the general CVR estimation. Besides, we empirically verify that the proposed learning scheme can further eliminate the high variance problem of the imputation learning. To evaluate its effectiveness, extensive experiments are conducted on a semi-synthetic dataset and two real-world datasets. The results demonstrate the superiority of the proposed approach over the state-of-the-art methods. The code is available at https://github.com/guosyjlu/MRDR-DL.
Bridging Data Center AI Systems with Edge Computing for Actionable Information Retrieval
Venue: arXiv cs.LG 2022
Year: 2022

Extremely high data rates at modern synchrotron and X-ray free-electron laser light source beamlines motivate the use of machine learning methods for data reduction, feature detection, and other purposes. Regardless of the application, the basic concept is the same: data collected in early stages of an experiment, data from past similar experiments, and/or data simulated for the upcoming experiment are used to train machine learning models that, in effect, learn specific characteristics of those data; these models are then used to process subsequent data more efficiently than would general-purpose models that lack knowledge of the specific dataset or data class. Thus, a key challenge is to be able to train models with sufficient rapidity that they can be deployed and used within useful timescales. We describe here how specialized data center AI (DCAI) systems can be used for this purpose through a geographically distributed workflow. Experiments show that although there are data movement cost and service overhead to use remote DCAI systems for DNN training, the turnaround time is still less than 1/30 of using a locally deploy-able GPU.
Reinforcement Learning for on-line Sequence Transformation
Venue: arXiv cs.LG 2022
Year: 2022

A number of problems in the processing of sound and natural language, as well as in other areas, can be reduced to simultaneously reading an input sequence and writing an output sequence of generally different length. There are well developed methods that produce the output sequence based on the entirely known input. However, efficient methods that enable such transformations on-line do not exist. In this paper we introduce an architecture that learns with reinforcement to make decisions about whether to read a token or write another token. This architecture is able to transform potentially infinite sequences on-line. In an experimental study we compare it with state-of-the-art methods for neural machine translation. While it produces slightly worse translations than Transformer, it outperforms the autoencoder with attention, even though our architecture translates texts on-line thereby solving a more difficult problem than both reference methods.
What Makes a Game High-rated? Towards Factors of Video Game Success
Venue: arXiv cs.SE 2022
Year: 2022

As the video game market grows larger, it becomes harder to stand out from the crowd. Launching a successful game involves different aspects. But what are they? In this paper, we investigate some aspects of the high-rated games from a dataset of 200 projects. The results show that the none of the aspects of this study have a strong relationship with the game's success. A further analysis on the high-rated games shows that team, technical, and game-design aspects should be the main focus of the game developers.
Towards a Rigorous Statistical Analysis of Empirical Password Datasets
Venue: arXiv cs.CR 2022
Year: 2022

A central challenge in password security is to characterize the attacker's guessing curve i.e., what is the probability that the attacker will crack a random user's password within the first $G$ guesses. A key challenge is that the guessing curve depends on the attacker's guessing strategy and the distribution of user passwords both of which are unknown to us. In this work we aim to follow Kerckhoffs' principle and analyze the performance of an optimal attacker who knows the password distribution. Let $λ_G$ denote the probability that such an attacker can crack a random user's password within $G$ guesses. We develop several statistically rigorous techniques to upper and lower bound $λ_G$ given $N$ independent samples from the unknown distribution. We show that our bounds hold with high confidence and apply our techniques to analyze eight password datasets. Our empirical analysis shows that even state-of-the-art password cracking models are often significantly less guess efficient than an attacker who can optimize its attack based on its (partial) knowledge of the password distribution. We also apply our techniques to re-examine the empirical password distribution and Zipf's Law. We find that the empirical distribution closely matches our bounds on $λ_G$ when $G$ is not too large i.e., $G \ll N$. However, for larger values of $G$ our empirical analysis rigorously demonstrates that the empirical distribution (resp. Zipf's Law) overestimates the attacker's success rate. We apply our techniques to upper/lower bound the effectiveness of password throttling mechanisms (key-stretching) which are used to reduce the number of attacker guesses $G$. Finally, if we make an additional assumption about the way users respond to password restrictions, we can use our techniques to evaluate the effectiveness of password composition policies which restrict the passwords users may select.
FoveaTer: Foveated Transformer for Image Classification
Venue: arXiv cs.CV 2022
Year: 2022

Many animals and humans process the visual field with a varying spatial resolution (foveated vision) and use peripheral processing to make eye movements and point the fovea to acquire high-resolution information about objects of interest. This architecture results in computationally efficient rapid scene exploration. Recent progress in self-attention-based Vision Transformers, an alternative to the traditionally convolution-reliant computer vision systems. However, the Transformer models do not explicitly model the foveated properties of the visual system nor the interaction between eye movements and the classification task. We propose Foveated Transformer (FoveaTer) model, which uses pooling regions and eye movements to perform object classification tasks using a Vision Transformer architecture. Using square pooling regions or biologically-inspired radial-polar pooling regions, our proposed model pools the image features from the convolution backbone and uses the pooled features as an input to transformer layers. It decides on subsequent fixation location based on the attention assigned by the Transformer to various locations from past and present fixations. It dynamically allocates more fixation/computational resources to more challenging images before making the final image category decision. Using five ablation studies, we evaluate the contribution of different components of the Foveated model. We perform a psychophysics scene categorization task and use the experimental data to find a suitable radial-polar pooling region combination. We also show that the Foveated model better explains the human decisions in a scene categorization task than a Baseline model. We demonstrate our model's robustness against PGD adversarial attacks with both types of pooling regions, where we see the Foveated model outperform the Baseline model.
M6-UFC: Unifying Multi-Modal Controls for Conditional Image Synthesis via Non-Autoregressive Generative Transformers
Venue: arXiv cs.CV 2022
Year: 2022

Conditional image synthesis aims to create an image according to some multi-modal guidance in the forms of textual descriptions, reference images, and image blocks to preserve, as well as their combinations. In this paper, instead of investigating these control signals separately, we propose a new two-stage architecture, M6-UFC, to unify any number of multi-modal controls. In M6-UFC, both the diverse control signals and the synthesized image are uniformly represented as a sequence of discrete tokens to be processed by Transformer. Different from existing two-stage autoregressive approaches such as DALL-E and VQGAN, M6-UFC adopts non-autoregressive generation (NAR) at the second stage to enhance the holistic consistency of the synthesized image, to support preserving specified image blocks, and to improve the synthesis speed. Further, we design a progressive algorithm that iteratively improves the non-autoregressively generated image, with the help of two estimators developed for evaluating the compliance with the controls and evaluating the fidelity of the synthesized image, respectively. Extensive experiments on a newly collected large-scale clothing dataset M2C-Fashion and a facial dataset Multi-Modal CelebA-HQ verify that M6-UFC can synthesize high-fidelity images that comply with flexible multi-modal controls.
REAM$\sharp$: An Enhancement Approach to Reference-based Evaluation Metrics for Open-domain Dialog Generation
Venue: arXiv cs.CL 2022
Year: 2022

The lack of reliable automatic evaluation metrics is a major impediment to the development of open-domain dialogue systems. Various reference-based metrics have been proposed to calculate a score between a predicted response and a small set of references. However, these metrics show unsatisfactory correlations with human judgments. For a reference-based metric, its reliability mainly depends on two factors: its ability to measure the similarity between the predicted response and the reference response, as well as the reliability of the given reference set. Yet, there are few discussions on the latter. Our work attempts to fill this vacancy. We first clarify an assumption on reference-based metrics that, if more high-quality references are added into the reference set, the reliability of the metric will increase. Next, we present REAM$\sharp$: an enhancement approach to Reference-based EvAluation Metrics for open-domain dialogue systems. A prediction model is designed to estimate the reliability of the given reference set. We show how its predicted results can be helpful to augment the reference set, and thus improve the reliability of the metric. Experiments validate both the effectiveness of our prediction model and that the reliability of reference-based metrics improves with the augmented reference sets.