OpenRaiser/Intern-Atlas huggingface dataset:
Text Generation from Knowledge Graphs with Graph Transformers
Venue: arXiv cs.CL 2022
Year: 2022

Generating texts which express complex ideas spanning multiple sentences requires a structured representation of their content (document plan), but these representations are prohibitively expensive to manually produce. In this work, we address the problem of generating coherent multi-sentence texts from the output of an information extraction system, and in particular a knowledge graph. Graphical knowledge representations are ubiquitous in computing, but pose a significant challenge for text generation techniques due to their non-hierarchical nature, collapsing of long-distance dependencies, and structural variety. We introduce a novel graph transforming encoder which can leverage the relational structure of such knowledge graphs without imposing linearization or hierarchical constraints. Incorporated into an encoder-decoder setup, we provide an end-to-end trainable system for graph-to-text generation that we apply to the domain of scientific text. Automatic and human evaluations show that our technique produces more informative texts which exhibit better document structure than competitive encoder-decoder methods.
Towards a complete perspective on labeled tree indexing: new size bounds, efficient constructions, and beyond
Venue: arXiv cs.DS 2022
Year: 2022

A labeled tree (or a trie) is a natural generalization of a string, which can also be seen as a compact representation of a set of strings. This paper considers the labeled tree indexing problem, and provides a number of new results on space bound analysis, and on algorithms for efficient construction and pattern matching queries. Kosaraju [FOCS 1989] was the first to consider the labeled tree indexing problem, and he proposed the suffix tree for a backward trie, where the strings in the trie are read in the leaf-to-root direction. In contrast to a backward trie, we call a usual trie as a forward trie. Despite a few follow-up works after Kosaraju's paper, indexing forward/backward tries is not well understood yet. In this paper, we show a full perspective on the sizes of indexing structures such as suffix trees, DAWGs, CDAWGs, suffix arrays, affix trees, affix arrays for forward and backward tries. Some of them take $O(n)$ space in the size $n$ of the input trie, while the others can occupy $O(n^2)$ space in the worst case. In particular, we show that the size of the DAWG for a forward trie with $n$ nodes is $Ω(σn)$, where $σ$ is the number of distinct characters in the trie. This becomes $Ω(n^2)$ for an alphabet of size $σ= Θ(n)$. Still, we show that there is a compact $O(n)$-space implicit representation of the DAWG for a forward trie, whose space requirement is independent of the alphabet size. This compact representation allows for simulating each DAWG edge traversal in $O(\log σ)$ time, and can be constructed in $O(n)$ time and space over any integer alphabet of size $O(n)$. In addition, this readily extends to the first indexing structure that permits bidirectional pattern searches over a trie within linear space in the input trie size.
Frequent Itemset Mining using QUBO
Venue: arXiv cs.DB 2022
Year: 2022

In this paper we propose a R-step approximation to solve frequent itemset mining on quantum hardware like quantum annealing or QAOA. The idea is to search for the set of items where the minimal 2-item frequency is maximal. This can be represented as a maximum clique problem.
Communication and Code Dependency Effects on Software Code Quality: An Empirical Analysis of Herbsleb Hypothesis
Venue: arXiv cs.SE 2022
Year: 2022

Prior literature has suggested that in many projects 80\% or more of the contributions are made by a small called group of around 20% of the development team. Most prior studies deprecate a reliance on such a small inner group of "heroes", arguing that it causes bottlenecks in development and communication. Despite this, such projects are very common in open source projects. So what exactly is the impact of "heroes" in code quality? Herbsleb argues that if code is strongly connected yet their developers are not, then that code will be buggy. To test the Hersleb hypothesis, we develop and apply two metrics of (a) "social-ness'"and (b) "hero-ness" that measure (a) how much one developer comments on the issues of another; and (b) how much one developer changes another developer's code (and "heroes" are those that change the most code, all around the system). In a result endorsing the Hersleb hypothesis, in over 1000 open source projects, we find that "social-ness" is a statistically stronger indicate for code quality (number of bugs) than "hero-ness". Hence we say that debates over the merits of "hero-ness" is subtly misguided. Our results suggest that the real benefits of these so-called "heroes" is not so much the code they generate but the pattern of communication required when the interaction between a large community of programmers passes through a small group of centralized developers. To say that another way, to build better code, build better communication flows between core developers and the rest. In order to allow other researchers to confirm/improve/refute our results, all our scripts and data are available, on-line at https://github.com/Anonymous633671/A-Comparison-on-Communication-and-Code-Dependency-Effects-on-Software-Code-Quality.
Stability of cyber-physical systems of numerical methods for stochastic differential equations: integrating the cyber and the physical of stochastic systems
Venue: arXiv cs.SY 2022
Year: 2022

This paper presents the cyber-physical system (CPS) of a numerical method (the widely-used Euler- Maruyama method) and establishes a foundational theory of the CPSs of numerical methods for stochastic differential equations (SDEs), which transforms the way we understand the relationship between the numerical method and the underlying dynamical system. Unlike in the literature where they are treated as separate systems linked by inequalities, the CPS is a seamless integration of the SDE and the numerical method and we construct a new and general class of stochastic impulsive differential equations (SiDEs) that can serve as a canonic form of the CPSs of numerical methods. By the CPS approach, we show the equivalence and intrinsic relationship between the stability of the SDE and the stability of the numerical method using the Lyapunov stability theory we develop for our class of SiDEs. Applying our established theory, we present the CPS Lyapunov inequality that is the necessary and sufficient condition for meansquare stability of the CPS of the Euler-Maruyama method for linear SDEs. The proposed CPS and theory initiate the study of systems numerics and provoke many open and interesting problems for future work.
Location Management in LTE Networks using Multi-Objective Particle Swarm Optimization
Venue: arXiv cs.NI 2022
Year: 2022

Long-term evolution (LTE) and LTE-advance (LTE-A) are widely used efficient network technologies serving billions of users, since they are featured with high spectrum efficiency, less latency, and higher bandwidth. Despite remarkable advantages offered by these technologies, signaling overhead remains a major issue in accessing the network. In particular, the load of signaling is mainly attributed to location management. This paper proposes an efficient approach for minimizing the total signaling overhead of location management in LTE networks using multi-objective particle swarm optimization (MOPSO). Tracking area update (TAU) and paging are considered to be the main elements of the signaling overhead of optimal location management in LTE. In addition, the total inter-list handover contributes significantly to the total signaling overhead. However, the total signaling cost of TAU and paging is adversely related to the total inter-list handover. Two cost functions should be minimized, the first is the total signaling cost of TAU and paging and the second is the total signaling overhead. The trade-off between these two objectives can be circumvented by MOPSO, which alleviates the total signaling overhead. A set of non-dominated solutions on the Pareto-optimal front is defined and the best compromise solution. The proposed algorithm results feasible compromise solution, minimizing the signaling overhead and the consumption of the power battery of a user. The efficacy and the robustness of the proposed algorithm have been proven using large scale environment problem illustrative example. The location management in LTE networks using MOPSO best compromise solution has been compared to a mixed integer non-linear programming (MINLP) algorithm. Location management mobility management entity MME pooling clustering SON Distributed Centralized pooling scheme fuzzy implementation setup LP-CPLEX
Free Component Analysis: Theory, Algorithms & Applications
Venue: arXiv cs.LG 2022
Year: 2022

We describe a method for unmixing mixtures of freely independent random variables in a manner analogous to the independent component analysis (ICA) based method for unmixing independent random variables from their additive mixtures. Random matrices play the role of free random variables in this context so the method we develop, which we call Free component analysis (FCA), unmixes matrices from additive mixtures of matrices. Thus, while the mixing model is standard, the novelty and difference in unmixing performance comes from the introduction of a new statistical criteria, derived from free probability theory, that quantify freeness analogous to how kurtosis and entropy quantify independence. We describe the theory, the various algorithms, and compare FCA to vanilla ICA which does not account for spatial or temporal structure. We highlight why the statistical criteria make FCA also vanilla despite its matricial underpinnings and show that FCA performs comparably to, and sometimes better than, (vanilla) ICA in every application, such as image and speech unmixing, where ICA has been known to succeed. Our computational experiments suggest that not-so-random matrices, such as images and short time fourier transform matrix of waveforms are (closer to being) freer "in the wild" than we might have theoretically expected.
Differentially Private Learning with Adaptive Clipping
Venue: arXiv cs.LG 2022
Year: 2022

Existing approaches for training neural networks with user-level differential privacy (e.g., DP Federated Averaging) in federated learning (FL) settings involve bounding the contribution of each user's model update by clipping it to some constant value. However there is no good a priori setting of the clipping norm across tasks and learning settings: the update norm distribution depends on the model architecture and loss, the amount of data on each device, the client learning rate, and possibly various other parameters. We propose a method wherein instead of a fixed clipping norm, one clips to a value at a specified quantile of the update norm distribution, where the value at the quantile is itself estimated online, with differential privacy. The method tracks the quantile closely, uses a negligible amount of privacy budget, is compatible with other federated learning technologies such as compression and secure aggregation, and has a straightforward joint DP analysis with DP-FedAvg. Experiments demonstrate that adaptive clipping to the median update norm works well across a range of realistic federated learning tasks, sometimes outperforming even the best fixed clip chosen in hindsight, and without the need to tune any clipping hyperparameter.
Stochastic Inverse Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

The goal of the inverse reinforcement learning (IRL) problem is to recover the reward functions from expert demonstrations. However, the IRL problem like any ill-posed inverse problem suffers the congenital defect that the policy may be optimal for many reward functions, and expert demonstrations may be optimal for many policies. In this work, we generalize the IRL problem to a well-posed expectation optimization problem stochastic inverse reinforcement learning (SIRL) to recover the probability distribution over reward functions. We adopt the Monte Carlo expectation-maximization (MCEM) method to estimate the parameter of the probability distribution as the first solution to the SIRL problem. The solution is succinct, robust, and transferable for a learning task and can generate alternative solutions to the IRL problem. Through our formulation, it is possible to observe the intrinsic property of the IRL problem from a global viewpoint, and our approach achieves a considerable performance on the objectworld.
Fast Flow Reconstruction via Robust Invertible nxn Convolution
Venue: arXiv cs.CV 2022
Year: 2022

Flow-based generative models have recently become one of the most efficient approaches to model data generation. Indeed, they are constructed with a sequence of invertible and tractable transformations. Glow first introduced a simple type of generative flow using an invertible $1 \times 1$ convolution. However, the $1 \times 1$ convolution suffers from limited flexibility compared to the standard convolutions. In this paper, we propose a novel invertible $n \times n$ convolution approach that overcomes the limitations of the invertible $1 \times 1$ convolution. In addition, our proposed network is not only tractable and invertible but also uses fewer parameters than standard convolutions. The experiments on CIFAR-10, ImageNet and Celeb-HQ datasets, have shown that our invertible $n \times n$ convolution helps to improve the performance of generative models significantly.
Learning with Succinct Common Representation Based on Wyner's Common Information
Venue: arXiv cs.LG 2022
Year: 2022

A new bimodal generative model is proposed for generating conditional and joint samples, accompanied with a training method with learning a succinct bottleneck representation. The proposed model, dubbed as the variational Wyner model, is designed based on two classical problems in network information theory -- distributed simulation and channel synthesis -- in which Wyner's common information arises as the fundamental limit on the succinctness of the common representation. The model is trained by minimizing the symmetric Kullback--Leibler divergence between variational and model distributions with regularization terms for common information, reconstruction consistency, and latent space matching terms, which is carried out via an adversarial density ratio estimation technique. The utility of the proposed approach is demonstrated through experiments for joint and conditional generation with synthetic and real-world datasets, as well as a challenging zero-shot image retrieval task.
Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path Based Formulation
Venue: arXiv cs.DS 2022
Year: 2022

The problem of online matching with stochastic rewards is a generalization of the online bipartite matching problem where each edge has a probability of success. When a match is made it succeeds with the probability of the corresponding edge. Introducing this model, Mehta and Panigrahi (FOCS 2012) focused on the special case of identical edge probabilities. Comparing against a deterministic offline LP, they showed that the Ranking algorithm of Karp et al. (STOC 1990) is 0.534 competitive and proposed a new online algorithm with an improved guarantee of $0.567$ for vanishingly small probabilities. For the case of vanishingly small but heterogeneous probabilities Mehta et al. (SODA 2015), gave a 0.534 competitive algorithm against the same LP benchmark. For the more general vertex-weighted version of the problem, to the best of our knowledge, no results being $1/2$ were previously known even for identical probabilities. We focus on the vertex-weighted version and give two improvements. First, we show that a natural generalization of the Perturbed-Greedy algorithm of Aggarwal et al. (SODA 2011), is $(1-1/e)$ competitive when probabilities decompose as a product of two factors, one corresponding to each vertex of the edge. This is the best achievable guarantee as it includes the case of identical probabilities and in particular, the classical online bipartite matching problem. Second, we give a deterministic $0.596$ competitive algorithm for the previously well studied case of fully heterogeneous but vanishingly small edge probabilities. A key contribution of our approach is the use of novel path-based analysis. This allows us to compare against the natural benchmarks of adaptive offline algorithms that know the sequence of arrivals and the edge probabilities in advance, but not the outcomes of potential matches.
Learning to Balance: Bayesian Meta-Learning for Imbalanced and Out-of-distribution Tasks
Venue: arXiv cs.LG 2022
Year: 2022

While tasks could come with varying the number of instances and classes in realistic settings, the existing meta-learning approaches for few-shot classification assume that the number of instances per task and class is fixed. Due to such restriction, they learn to equally utilize the meta-knowledge across all the tasks, even when the number of instances per task and class largely varies. Moreover, they do not consider distributional difference in unseen tasks, on which the meta-knowledge may have less usefulness depending on the task relatedness. To overcome these limitations, we propose a novel meta-learning model that adaptively balances the effect of the meta-learning and task-specific learning within each task. Through the learning of the balancing variables, we can decide whether to obtain a solution by relying on the meta-knowledge or task-specific learning. We formulate this objective into a Bayesian inference framework and tackle it using variational inference. We validate our Bayesian Task-Adaptive Meta-Learning (Bayesian TAML) on multiple realistic task- and class-imbalanced datasets, on which it significantly outperforms existing meta-learning approaches. Further ablation study confirms the effectiveness of each balancing component and the Bayesian learning framework.
A large-scale, in-depth analysis of developers' personalities in the Apache ecosystem
Venue: arXiv cs.SE 2022
Year: 2022

Context: Large-scale distributed projects are typically the results of collective efforts performed by multiple developers with heterogeneous personalities. Objective: We aim to find evidence that personalities can explain developers' behavior in large scale-distributed projects. For example, the propensity to trust others - a critical factor for the success of global software engineering - has been found to influence positively the result of code reviews in distributed projects. Method: In this paper, we perform a quantitative analysis of ecosystem-level data from the code commits and email messages contributed by the developers working on the Apache Software Foundation (ASF) projects, as representative of large scale-distributed projects. Results: We find that there are three common types of personality profiles among Apache developers, characterized in particular by their level of Agreeableness and Neuroticism. We also confirm that developers' personality is stable over time. Moreover, personality traits do not vary with their role, membership, and extent of contribution to the projects. We also find evidence that more open developers are more likely to make contributors to Apache projects. Conclusion: Overall, our findings reinforce the need for future studies on human factors in software engineering to use psychometric tools to control for differences in developers' personalities.
The Strength of Structural Diversity in Online Social Networks
Venue: arXiv cs.SI 2022
Year: 2022

Understanding the way individuals are interconnected in social networks is of prime significance to predict their collective outcomes. Leveraging a large-scale dataset from a knowledge-sharing website, this paper presents an exploratory investigation of the way to depict structural diversity in directed networks and how it can be utilized to predict one's online social reputation. To capture the structural diversity of an individual, we first consider the number of weakly and strongly connected components in one's contact neighborhood and further take the coexposure network of social neighbors into consideration. We show empirical evidence that the structural diversity of an individual is able to provide valuable insights to predict personal online social reputation, and the inclusion of a coexposure network provides an additional ingredient to achieve that goal. After synthetically controlling several possible confounding factors through matching experiments, structural diversity still plays a nonnegligible role in the prediction of personal online social reputation. Our work constitutes one of the first attempts to empirically study structural diversity in directed networks and has practical implications for a range of domains, such as social influence and collective intelligence studies.
Running Time Analysis of the (1+1)-EA for Robust Linear Optimization
Venue: arXiv cs.CC 2022
Year: 2022

Evolutionary algorithms (EAs) have found many successful real-world applications, where the optimization problems are often subject to a wide range of uncertainties. To understand the practical behaviors of EAs theoretically, there are a series of efforts devoted to analyzing the running time of EAs for optimization under uncertainties. Existing studies mainly focus on noisy and dynamic optimization, while another common type of uncertain optimization, i.e., robust optimization, has been rarely touched. In this paper, we analyze the expected running time of the (1+1)-EA solving robust linear optimization problems (i.e., linear problems under robust scenarios) with a cardinality constraint $k$. Two common robust scenarios, i.e., deletion-robust and worst-case, are considered. Particularly, we derive tight ranges of the robust parameter $d$ or budget $k$ allowing the (1+1)-EA to find an optimal solution in polynomial running time, which disclose the potential of EAs for robust optimization.
Linear Complexity of A Family of Binary $pq^2$-periodic Sequences From Euler Quotients
Venue: arXiv cs.IT 2022
Year: 2022

We first introduce a family of binary $pq^2$-periodic sequences based on the Euler quotients modulo $pq$, where $p$ and $q$ are two distinct odd primes and $p$ divides $q-1$. The minimal polynomials and linear complexities are determined for the proposed sequences provided that $2^{q-1} \not\equiv 1 \mod{q^2}.$ The results show that the proposed sequences have high linear complexities.
Faster FPT Algorithm for 5-Path Vertex Cover
Venue: arXiv cs.DS 2022
Year: 2022

The problem of $d$-Path Vertex Cover, $d$-PVC lies in determining a subset $F$ of vertices of a given graph $G=(V,E)$ such that $G \setminus F$ does not contain a path on $d$ vertices. The paths we aim to cover need not to be induced. It is known that the $d$-PVC problem is NP-complete for any $d \ge 2$. When parameterized by the size of the solution $k$, 5-PVC has direct trivial algorithm with $\mathcal{O}(5^kn^{\mathcal{O}(1)})$ running time and, since $d$-PVC is a special case of $d$-Hitting Set, an algorithm running in $\mathcal{O}(4.0755^kn^{\mathcal{O}(1)})$ time is known. In this paper we present an iterative compression algorithm that solves the 5-PVC problem in $\mathcal{O}(4^kn^{\mathcal{O}(1)})$ time.