Finding reliable subgraphs from large probabilistic graphs

Reliable subgraphs can be used, for example, to find and rank nontrivial links between given vertices, to concisely visualize large graphs, or to reduce the size of input for computationally demanding graph algorithms. We propose two new heuristics for solving the most reliable subgraph extraction problem on large, undirected probabilistic graphs. Such a problem is specified by a probabilistic graph G subject to random edge failures, a set of terminal vertices, and an integer K. The objective is to remove K edges from G such that the probability of connecting the terminals in the remaining subgraph is maximized. We provide some technical details and a rough analysis of the proposed algorithms. The practical performance of the methods is evaluated on real probabilistic graphs from the biological domain. The results indicate that the methods scale much better to large input graphs, both computationally and in terms of the quality of the result.     

改进动态因果图与模糊推理融合故障诊断方法

在复杂的控制系统发生故障时,运维系统能保证对其进行快速、可靠的故障诊断尤为重要。针对复杂控制系统中控制信号多、信号关联性强、故障状态多、部件故障模式多的情况,提出一种改进动态因果图与模糊推理融合的故障诊断方法,利用改进动态因果图逻辑表达能力强,能因果互推的特点,构建多重（正向、反向、混合）模糊规则,有效克服了模糊逻辑推理中只能由因溯果而不能由果溯因的难题,同时,将动态因果图的动态特性引入到模糊规则的动态更新中,增强了模糊推理的实时性。最后,以某型装甲设备垂直力矩电机控制过程的故障诊断为应用背景,在自行研制的故障诊断平台中嵌入此法进行故障诊断测试,测试结果分析表明,此法能有效提高诊断效率,具有更高的准确性、先进性、适用性。     

基于故障关联的多故障概率诊断方法

故障软件诊断的必要性在于真实世界中的软件几乎都会包含一个以上的故障。与单故障不同,多个故障的传播及其关联导致软件诊断更复杂,不确定性更高,概率推理因而被用于适应多故障程序的特殊性。提出了一种新的基于变形概率图FCG及其推理的软件诊断方法。相比于BARINEL方法和经典的贝叶斯网,FCG的特别之处在于采用了无向图上候选故障及其关联关系的贝叶斯推理和Noisy-or推理,而候选故障及其关联可以从程序语句间的控制依赖关系和数据依赖关系中创建。从西门子套件到更大的space,grep程序的实验,无论是在处理单故障还是处理多故障的情况下,实验结果都证明了FCG的有效性,其诊断效果比LOUPE,Ochiai,Tarantula甚至BARINEL方法都准确。     

基于事理知识图谱的舆情推演方法

一直以来舆情态势发展的多元性、复杂性使其难以有效管控,一些负面舆情会激化矛盾,给社会安定带来不利影响.提出了一种基于事理知识图谱的舆情事件推演方法,通过神经网络挖掘事件因果逻辑,连接因果事件构成事理知识图谱.向量化事件节点以融合归并相似节点降低图谱冗余,增强图谱泛化性.根据事理知识图谱反映的发展逻辑对目标舆情事件的演化趋势进行预测.以自然灾害舆情事件为例,实验结果表明提出的方法能够有效预测舆情事件发展方向,可以为舆情监管提供一定支持.     

Symbol recognition in electrical diagrams using probabilistic graph matching

In this paper a method is proposed to recognize symbols in electrical diagrams based on probabilistic matching. The skeletons of the symbols are represented by graphs. After finding the pose of the graph (orientation, translation, scale) by a bounded search for a minimum error transformation, the observed graph is matched to the class models and the likelihood of the match is calculated. Results are given for computer-generated symbols and hand drawn symbols with and without a template. Error rates range from <1% to 8%.     

Minimal functional routes in directed graphs with dependent edges

Graphs are mathematical structures used to model a set of objects and the relations between them. One of the basic concepts of graph theory, the path, has wide real‐world applications. In classic graph models, edges ending at a node are assumed to be independent. However, many real graphs/networks can only be correctly described by considering a dependency among nodes or edges. Paths in such graphs may not be functional if the conditional dependency is ignored. In this study, we investigate the routing problem in directed graphs with dependent edges represented by general graph models as alternatives to hypergraphs. We define a minimal functional route (MFR) as a minimal set of nodes and edges that can independently perform information transfer between two given nodes, and formulate the determination of MFRs as a graph search problem. A depth‐first‐search (DFS) top‐down algorithm, an iterative integer linear programming (ILP) bottom‐up algorithm, and a subgraph‐growing bottom‐up algorithm are devised subsequently to solve this problem. Numerical experiments verify the effectiveness of the algorithms. The defined MFR problem and the proposed algorithms are expected to find many practical applications.     

State agnostic planning graphs: deterministic,non-deterministic,and probabilistic planning

Planning graphs have been shown to be a rich source of heuristic information for many kinds of planners. In many cases, planners must compute a planning graph for each element of a set of states, and the naive technique enumerates the graphs individually. This is equivalent to solving a multiple-source shortest path problem by iterating a single-source algorithm over each source.We introduce a data-structure, the state agnostic planning graph, that directly solves the multiple-source problem for the relaxation introduced by planning graphs. The technique can also be characterized as exploiting the overlap present in sets of planning graphs. For the purpose of exposition, we first present the technique in deterministic (classical) planning to capture a set of planning graphs used in forward chaining search. A more prominent application of this technique is in conformant and conditional planning (i.e., search in belief state space), where each search node utilizes a set of planning graphs; an optimization to exploit state overlap between belief states collapses the set of sets of planning graphs to a single set. We describe another extension in conformant probabilistic planning that reuses planning graph samples of probabilistic action outcomes across search nodes to otherwise curb the inherent prediction cost associated with handling probabilistic actions. Finally, we show how to extract a state agnostic relaxed plan that implicitly solves the relaxed planning problem in each of the planning graphs represented by the state agnostic planning graph and reduces each heuristic evaluation to counting the relevant actions in the state agnostic relaxed plan. Our experimental evaluation (using many existing International Planning Competition problems from classical and non-deterministic conformant tracks) quantifies each of these performance boosts, and demonstrates that heuristic belief state space progression planning using our technique is competitive with the state of the art.     

Maximal matching polytope in trees

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

Intelligent backtracking in deduction systems by means of extended unification graphs

A method for unification as the basis for intelligent backtracking in deduction systems is described. This method is based on the unification graphs introduced by Cox. In this paper, unification graphs are used in an extended form such that they represent all the information which can be gained from the unification constraints, i.e., the expression to be unified, their subterms which, as a consequence, are to be unified, the number of deduction steps which cause the unification of two terms, and the term-subterm relation as far as necessary. If a unification conflict occurs from this information, the deduction steps which have led to these conflicts can be determined and reset. This is done by searching for loop-free paths or loops with certain properties in the extended unification graph, according to the type of unification conflict. Algorithms for the handling of the unification graph and for the extraction information from it are described and proved as correct.     

大规模网络中攻击图的节点概率计算方法

针对基于攻击图的概率计算中节点之间的相关性导致的概率错误计算问题,通过将攻击图与通用安全脆弱点评估系统结合,提出攻击图各节点概率的精确计算方法和近似计算方法,在保证各节点概率精度的同时,较快地计算攻击图中各节点的概率值,有效地解决了节点之间的相关性所导致的概率错误计算问题。通过真实实验和模拟实验验证了所提方法的合理性和有效性,与相关的研究成果相比,可以适应于更复杂的攻击图,具有很好的扩展性。     

On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias

Causal discovery becomes especially challenging when the possibility of latent confounding and/or selection bias is not assumed away. For this task, ancestral graph models are particularly useful in that they can represent the presence of latent confounding and selection effect, without explicitly invoking unobserved variables. Based on the machinery of ancestral graphs, there is a provably sound causal discovery algorithm, known as the FCI algorithm, that allows the possibility of latent confounders and selection bias. However, the orientation rules used in the algorithm are not complete. In this paper, we provide additional orientation rules, augmented by which the FCI algorithm is shown to be complete, in the sense that it can, under standard assumptions, discover all aspects of the causal structure that are uniquely determined by facts of probabilistic dependence and independence. The result is useful for developing any causal discovery and reasoning system based on ancestral graph models.     

基于抽象事理图谱的因果简答题求解方法

如何利用人工智能技术回答标准测试题目是一项具有挑战性的任务,吸引了人工智能领域的广泛研究。该文聚焦在高中地理的因果简答题求解任务,求解因果简答题需要进行知识集成和多跳因果推理,最终生成一段长文本作为答案。为此,该文定义了抽象事理图谱(AEG)来表示因果等关系,并利用预训练语言模型从语料中自动抽取一个面向高中地理因果简答题的抽象事理图谱,实现了多源知识集成。基于抽象事理图谱,该文利用图神经网络技术来融合结构化和非结构化知识,实现了多跳因果推理。该文在包含真实的高中地理因果简答题的数据集GeoCEQA上开展实验,结果表明,无论是ROUGE、BLEU指标还是人工评价的得分,该文提出的方法都取得了最佳结果,在ROUGE指标上,相比最优基线方法提升0.8%～1.4%;在BLEU指标上,相比最优基线方法提升0.4%;在人工评价得分上,相比最优基线方法提升4.2%。     

Ensemble-based clustering of large probabilistic graphs using neighborhood and distance metric learning

Graphs are commonly used to express the communication of various data. Faced with uncertain data, we have probabilistic graphs. As a fundamental problem of such graphs, clustering has many applications in analyzing uncertain data. In this paper, we propose a novel method based on ensemble clustering for large probabilistic graphs. To generate ensemble clusters, we develop a set of probable possible worlds of the initial probabilistic graph. Then, we present a probabilistic co-association matrix as a consensus function to integrate base clustering results. It relies on co-occurrences of node pairs based on the probability of the corresponding common cluster graphs. Also, we apply two improvements in the steps before and after of ensembles generation. In the before step, we append neighborhood information based on node features to the initial graph to achieve a more accurate estimation of the probability between the nodes. In the after step, we use supervised metric learning-based Mahalanobis distance to automatically learn a metric from ensemble clusters. It aims to gain crucial features of the base clustering results. We evaluate our work using five real-world datasets and three clustering evaluation metrics, namely the Dunn index, Davies–Bouldin index, and Silhouette coefficient. The results show the impressive performance of clustering large probabilistic graphs.

     

Sequential Monte Carlo in reachability heuristics for probabilistic planning

Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking.In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions.     

Supervised classification using probabilistic decision graphs

A new model for supervised classification based on probabilistic decision graphs is introduced. A probabilistic decision graph (PDG) is a graphical model that efficiently captures certain context specific independencies that are not easily represented by other graphical models traditionally used for classification, such as the Naïve Bayes (NB) or Classification Trees (CT). This means that the PDG model can capture some distributions using fewer parameters than classical models. Two approaches for constructing a PDG for classification are proposed. The first is to directly construct the model from a dataset of labelled data, while the second is to transform a previously obtained Bayesian classifier into a PDG model that can then be refined. These two approaches are compared with a wide range of classical approaches to the supervised classification problem on a number of both real world databases and artificially generated data.     

Inexact graph matching by means of estimation of distribution algorithms

Estimation of distribution algorithms (EDAs) are a quite recent topic in optimization techniques. They combine two technical disciplines of soft computing methodologies: probabilistic reasoning and evolutionary computing. Several algorithms and approaches have already been proposed by different authors, but up to now there are very few papers showing their potential and comparing them to other evolutionary computational methods and algorithms such as genetic algorithms (GAs). This paper focuses on the problem of inexact graph matching which is NP-hard and requires techniques to find an approximate acceptable solution. This problem arises when a nonbijective correspondence is searched between two graphs. A typical instance of this problem corresponds to the case where graphs are used for structural pattern recognition in images. EDA algorithms are well suited for this type of problems.

This paper proposes to use EDA algorithms as a new approach for inexact graph matching. Also, two adaptations of the EDA approach to problems with constraints are described as two techniques to control the generation of individuals, and the performance of EDAs for inexact graph matching is compared with the one of GAs.     

计算机视觉中图匹配研究进展: 从二图匹配迈向多图匹配

图匹配试图求解二图或多图之间节点的对应关系.在图像图形领域,图匹配是一个历久弥新的基础性问题.从优化的角度来看,图匹配问题是一个组合优化问题,且在一般情形下具有非确定性多项式复杂程度(non-deter-ministic polynomial, NP)难度的性质.在过去数十年间,出现了大量求解二图匹配的近似算法,并在各个领域得到了较为广泛的应用.然而,受限于优化问题本身的理论困难和实际应用中数据质量的种种限制,各二图匹配算法在匹配精度上的性能日益趋近饱和.相比之下,由于引入了更多信息且往往更符合实际问题的设定,多图的协同匹配则逐渐成为了一个新兴且重要的研究方向.本文首先介绍了经典的二图匹配方法,随后着重介绍近年来多图匹配方法的最新进展和相关工作.最后,本文讨论了图匹配未来的发展.