Research on the Parallel Tractability of Knowledge Graph Reasoning based on Boolean Circuits

Although neural methods have been comprehensively applied in different fields,symbolic based logic reasoning is still the main choice for numerous applications based on knowledge graphs.To enhance the efficiency of knowledge graph reasoning,researchers studied how to design parallelalgorithms for reasoning,and take advantage of high-performance architectures,like neural networks.Although parallel algorithms and architectures improve the performance of reasoning to some degree,the task of reasoning is essentially bounded by its computational complexity,i.e.,the PTiMe-Completeness or higher complexities.This means that the task of reasoning is not parallelly tractable.In this work,we investigate the parallel tractability of knowledge graph reasoning from the perspective of parallel complexity.We concentrate on knowledge graphs that are Datalog rewritable.We aim to capture the parallelly tractable classes of knowledge graphs,for which,the task of reasoning falls in the NC complexity.To this end,we employ the computational model of Boolean circuit to formalize knowledge graph reasoning and further obtain all the theoretical results.We then use the results to analyze DHL(Description Horn Logic),a fragment of description logic.We give the properties that ensure the parallel tractability of DHL reasoning.One can utilize our results to check the parallel tractability of real knowledge graphs.In addition,the Boolean circuits proposed in this paper can also be used to construct neural networks to perform knowledge graph reasoning.

(S,T)-WEAK TRACTABILITY OF MULTIVARIATE LINEAR PROBLEMS IN THE AVERAGE CASE SETTING

The purpose of this article is to investigate (s, t)-weak tractability of multivariate linear problems in the average case set ting. The considered algorithms use finitely many evaluations of arbitrary linear functionals. Generally, we obtained matching necessary and sufficient conditions for (s,t)-weak tractability in terms of the corresponding non-increasing sequence of eigenvalues. Specifically, we discussed (s, t)-weak tractability of linear tensor product problems and obtained necessary and sufficient conditions in terms of the corresponding one-dimensional problem. As an example of applications, we discussed also (s,t)-weak tractability of a multivariate approximation problem.

TRACTABILITY OF MULTIVARIATE INTEGRATION PROBLEM FOR PERIODIC CONTINUOUS FUNCTIONS

The authors study the tractability and strong tractability of a multivariate integration problem in the worst case setting for weighted 1-periodic continuous functions spaces of d coordinates with absolutely convergent Fourier series. The authors reduce the initial error by a factor ε for functions from the unit ball of the weighted periodic continuous functions spaces. Tractability is the minimal number of function samples required to solve the problem in polynomial in ε^-1 and d, and the strong tractability is the presence of only a polynomial dependence in ε^-1. This problem has been recently studied for quasi-Monte Carlo quadrature rules, quadrature rules with non-negative coefficients, and rules for which all quadrature weights are arbitrary for weighted Korobov spaces of smooth periodic functions of d variables. The authors show that the tractability and strong tractability of a multivariate integration problem in worst case setting hold for the weighted periodic continuous functions spaces with absolutely convergent Fourier series under the same assumptions as in Ref,[14] on the weights of the Korobov space for quasi-Monte Carlo rules and rules for which all quadrature weights are non-negative. The arguments are not constructive.

Automated Test Case Generation from Requirements: A Systematic Literature Review

Software testing is an important and cost intensive activity in software development.The major contribution in cost is due to test case generations.Requirement-based testing is an approach in which test cases are derivative from requirements without considering the implementation’s internal structure.Requirement-based testing includes functional and nonfunctional requirements.The objective of this study is to explore the approaches that generate test cases from requirements.A systematic literature review based on two research questions and extensive quality assessment criteria includes studies.The study identies 30 primary studies from 410 studies spanned from 2000 to 2018.The review’s nding shows that 53%of journal papers,42%of conference papers,and 5%of book chapters’address requirementsbased testing.Most of the studies use UML,activity,and use case diagrams for test case generation from requirements.One of the signicant lessons learned is that most software testing errors are traced back to errors in natural language requirements.A substantial amount of work focuses on UML diagrams for test case generations,which cannot capture all the system’s developed attributes.Furthermore,there is a lack of UML-based models that can generate test cases from natural language requirements by rening them in context.Coverage criteria indicate how efciently the testing has been performed 12.37%of studies use requirements coverage,20%of studies cover path coverage,and 17%study basic coverage.

STRONG EQUIVALENCES OF APPROXIMATION NUMBERS AND TRACTABILITY OF WEIGHTED ANISOTROPIC SOBOLEV EMBEDDINGS

In this article,we study multivariate approximation defined over weighted anisotropic Sobolev spaces which depend on two sequences a={a j}j≥1 and b={b j}j≥1 of positive numbers.We obtain strong equivalences of the approximation numbers,and necessary and sufficient conditions on a,b to achieve various notions of tractability of the weighted anisotropic Sobolev embeddings.

A new age in understanding adult hippocampal neurogenesis in Alzheimer’s disease

Several lines of evidence have established that proliferation and differentiation of neural stem cells into neurons within the sub-granular zone of the dentate gyrus,a process named adult hippocampal neurogenesis,contribute to maintaining healthy cognitive functions throughout life.The rate of adult hippocampal neurogenesis decreases with aging and a premature impairment of adult hippocampal neurogenesis has been observed both in animal models of Alzheimer’s disease and human post-mortem tissues.The causal relationship between adult hippocampal neurogenesis and the development of Alzheimer’s disease pathology has,however,not been established.This is partly due to the limitation of recapitulating the development of Alzheimer’s disease pathology in rodent models and the lack of translatable biomarkers to identify tractable targets in humans.While it is tempting to postulate that adult hippocampal neurogenesis could be leveraged to improve cognitive deficits in Alzheimer’s disease,consensual results have yet to be reached to fully explore this hypothesis.In this review,we discuss how the recent progress in identifying molecular pathways in adult hippocampal neurogenesis provides a good framework to initiate strategies for drug-based intervention in neurodegenerative diseases,especially in Alzheimer’s disease.We outline how discrepancies in pre-clinical disease models and experimental methodology have resulted in contradictory findings and propose a shift towards using more translatable approaches to model neurogenesis in Alzheimer’s disease.In particular,we review how exploring novel experimental paradigms including the use of human induced pluripotent stem cells and more complex cell culture systems,as well as standardizing protocols used to investigate evidence of neurogenesis in human tissues,could deliver deeper mechanistic insights that would kick-start innovative drug discovery efforts to promote healthy aging and cellular rejuvenation.

Remarks on the Complexity of Signed k-Domination on Graphs

This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.

The expression tractability of biological traits shaped by natural selection

Understanding how gene expression is translated to phenotype is central to modern molecular biology,and the success is contingent on the intrinsic tractability of the specific traits under examination.However, an a priori estimate of trait tractability from the perspective of gene expression is unavailable.Motivated by the concept of entropy in a thermodynamic system, we here propose such an estimate(S_T)by gauging the number(N) of expression states that underlie the same trait abnormality, with large S_T corresponding to large N. By analyzing over 200 yeast morphological traits, we show that S_T predicts the tractability of an expression-trait relationship. We further show that S_T is ultimately determined by natural selection, which builds co-regulated gene modules to minimize possible expression states.

Querying Big Data: Bridging Theory and Practice

Big data introduces challenges to query answering, from theory to practice. A number of questions arise. What queries are ＂tractable＂ on big data？ How can we make big data ＂small＂ so that it is feasible to find exact query answers？When exact answers are beyond reach in practice, what approximation theory can help us strike a balance between the quality of approximate query answers and the costs of computing such answers？ To get sensible query answers in big data,what else do we necessarily do in addition to coping with the size of the data？ This position paper aims to provide an overview of recent advances in the study of querying big data. We propose approaches to tackling these challenging issues,and identify open problems for future research.

Finding Data Tractable Description Logics for Computing a Minimum Cost Diagnosis Based on ABox Decomposition

Ontology diagnosis, a well-known approach for handling inconsistencies in a description logic （DL） based ontology, computes a diagnosis of the ontology, i.e., a minimal subset of axioms in the ontology whose removal restores consistency. However, ontology diagnosis is computationally hard, especially computing a minimum cost diagnosis （MCD） which is a diagnosis such that the sum of the removal costs attached to its axioms is minimized. This paper addresses this problem by finding data tractable DLs for computing an MCD which allow computing an MCD in time polynomial in the size of the ABox of a given ontology. ABox decomposition is used to find a sufficient and necessary condition to identify data tractable DLs for computing an MCD under the unique name assumption （UNA） among all fragments of that are at least as expressive as without inverse roles. The most expressive, data tractable DL identified is without inverse roles or qualified existential restrictions.

Probabilistic Tractable Models in Mixed Discrete-Continuou s Domains

We study the problem of the unsupervised learning of graphical models in mixed discrete-continuous domains.The problem of unsupervised learning of such models in discrete domains alone is notoriously challenging,compounded by the fact that inference is computationally demanding.The situation is generally believed to be significantly worse in discrete-continuous domains:estimating the unknown probability distribution of given samples is often limited in practice to a handful of parametric forms,and in addition to that,computing conditional queries need to carefully handle low-probability regions in safety-critical applications.In recent years,the regime of tractable learning has emerged,which attempts to learn a graphical model that permits efficient inference.Most of the results in this regime are based on arithmetic circuits,for which inference is linear in the size of the obtained circuit.In this work,we show how,with minimal modifications,such regimes can be generalized by leveraging efficient density estimation schemes based on piecewise polynomial approximations.Our framework is realized on a recent computational abstraction that permits efficient inference for a range of queries in the underlying language.Our empirical results show that our approach is effective,and allows a study of the trade-off between the granularity of the learned model and its predictive power.

Parameterized Algorithmics for Computational Social Choice:Nine Research Challenges

Computational Social Choice is an interdisciplinary research area involving Economics, Political Science,and Social Science on the one side, and Mathematics and Computer Science（including Artificial Intelligence and Multiagent Systems） on the other side. Typical computational problems studied in this field include the vulnerability of voting procedures against attacks, or preference aggregation in multi-agent systems. Parameterized Algorithmics is a subfield of Theoretical Computer Science seeking to exploit meaningful problem-specific parameters in order to identify tractable special cases of in general computationally hard problems. In this paper, we propose nine of our favorite research challenges concerning the parameterized complexity of problems appearing in this context. This work is dedicated to Jianer Chen, one of the strongest problem solvers in the history of parameterized algorithmics,on the occasion of his 60 th birthday.

An Overview of Kernelization Algorithms for Graph Modification Problems

Kernelization algorithms for graph modification problems are important ingredients in parameterized computation theory. In this paper, we survey the kernelization algorithms for four types of graph modification problems, which include vertex deletion problems, edge editing problems, edge deletion problems, and edge completion problems. For each type of problem, we outline typical examples together with recent results, analyze the main techniques, and provide some suggestions for future research in this field.