Bayesian Network (BN) has been widely employed for many applications like medical diagnosis due to its ability to deal with probabilistic inferences. Real-world inference tasks in BN cannot be robustly processed by classic search-based inference algorithms, since the conditional probabilities w.r.t. given arbitrary evidence values may be missing (i.e., not included) in the conditional probability tables (CPTs). Most of the existing methods, relying on imputation models, density estimation models or deep neural networks, cannot accurately learn these missing probabilities. To this end, we incorporate the idea of learning and search for robust probabilistic inferences in BN. Firstly, we decompose the probabilistic inference task into missing and existing probability factors, ensuring the consistency of their probability spaces. Secondly, we define the Wasserstein distance between missing and existing probability factors, and incorporate the idea of generative adversarial network to obtain missing probability factors with the minimal Wasserstein distance. Finally, we give the algorithm for robust probabilistic inferences with arbitrary evidence values, which could also be used to deal with the probabilistic inferences with arbitrary query values. Extensive experiments on synthetic and real-world datasets are conducted to demonstrate the superiority of our proposed method.

Bayesian network (BN) structure learning on the discrete observations is crucial for representing uncertainty in data. However, existing single-structure learning methods are commonly trapped in local optimum or yielding structures that may lead to poorly calibrated predictions. Although posterior approximation methods can quantify the epistemic uncertainty over the learned BN structures, they cannot reliably identify the optimal BN structures. To tackle these issues, we propose a GFlowNet with Gradient-based Optimization (GFlowOpt) for the BN structure learning method. Initially, we employ Bayesian Information Criterion (BIC) scores as the rewards of BN structures, and adopt a contrastive learning-based training technique on GFlowNet to efficiently generate much better DAG representations. Subsequently, we train a proxy model on the continuous DAG representations by adopting the gradient-ascent-based optimization method to search more high proxy-scoring discrete candidate DAGs. Finally, we adopt Hill Climbing (HC) on these candidate DAGs to search high-scoring DAGs as the ultimate BN structures. Extensive experiments conducted on benchmark datasets demonstrate that the superiority of our proposed method compared with other state-of-the-art methods.

As the critical task in query optimization, cardinality estimation is fulfilled by learning the joint probability distribution of table attributes in most of the existing data-driven methods. However, these methods still suffer the efficiency bottleneck, since the exponential combinations of table joins lead to massive probability inferences. To address this issue, we propose the Bayesian Probability Forest (BPF) framework to reduce the calculation of probability inferences. By integrating mutual information and query frequency, we first propose a novel metric to learn the graphical structure of BPF, ensuring that the distance between high-frequency attributes and root node could be minimized. Then, we propose an efficient method for cardinality estimation in BPF. Specifically, the decomposition of cardinality estimation task is proposed to reduce the number of probability inferences, and elimination strategies are given to avoid the redundant calculations w.r.t. low-frequency attributes. Empirical investigations on real-world datasets demonstrate the superiority of our method over other cutting-edge competitors. Our codes are publicly available at https://github.com/CardEstGroup/bpf-ce.git.

As a fundamental task in the graph machine learning paradigm, link prediction aims to predict missing links in a graph. Recently, Graph Neural Networks (GNNs) have demonstrated significant superiority in learning graph representations and become the mainstream solution for link prediction tasks. However, existing GNN-based methods may exhibit suboptimal performance due to their inability to effectively distinguish automorphic nodes with identical structures. To address this issue, we propose a hierarchical structure-enhanced graph representation framework for link prediction based on structural information theory. Specifically, we first design an efficient algorithm to construct an encoding tree from the input graph by minimizing its structural entropy. The encoding tree is a multi-level hierarchical abstraction of the graph, providing an effective way to organize both global (higher levels) and local (lower levels) structural information for each node. Then, we enhance node embeddings with the hierarchical structural encoding, capturing nuanced structural patterns for distinguishing automorphic nodes. Finally, we train GNN models at different levels of the encoding tree to generate powerful link representations for prediction. Extensive experiments on several real-world datasets demonstrate the effectiveness and scalability of our proposed method. Our code is available at https://github.com/Bayunmaoyu/HSELP.

Multivariate time series forecasting remains a critical yet challenging task across various real-world applications, due to the complex inter-series and intra-series dependencies. While time series decomposition has emerged as a powerful paradigm for capturing intricate temporal patterns, many existing methods fail to fully exploit the predictive potential of the trend component, often relying on fixed decomposition strategies that may retain unpredictable or noisy elements. To address these limitations, we propose a complexity-aware trend extraction method that adaptively controls the complexity of the extracted trend, yielding a more predictable and robust trend component, thereby significantly improving forecasting accuracy. To better model inter-series dependencies and reduce noise interference in variable interactions, we introduce an information-theoretic constraint by leveraging mutual information to regulate the flow of information across variables. Furthermore, our framework strategically incorporates future trend characteristics into the forecasting process through a cross-attention mechanism that queries informative historical patterns, enabling more accurate predictions. Extensive experiments conducted on several real-world datasets demonstrate the effectiveness and superiority of our proposed method compared with other state-of-the-art methods. Our code is available at https://github.com/unarytree/MTSF.

The task of finding associative entities in knowledge graph (KG) is to provide a ranking list of entities according to their association degrees. However, many entities are not only linked in KG but also associated in terms of user behaviors, which facilitates finding associative entities accurately. This manuscript incorporates KG with user-generated data to propose the Association Entity Graph Model (AEGM) to evaluate the association degrees. They first propose the joint weighting function to evaluate the entity associations and prove its submodularity theoretically as well as the greedy algorithm to select the candidates efficiently. They define the entity association information to score the entity association and give the hill climbing search based algorithm for AEGM construction. Following, they embed AEGM to calculate the association degrees and obtain the associative entities efficiently. Extensive experiments on three datasets show that the proposed method can achieve a better performance than some state-of-the-art competitors in accurately finding associative entities.

Bayesian network (BN) is a directed acyclic graph (DAG) representing the dependence relations among random variables with conditional probability tables (CPTs). The efficiency and accuracy of multiple probabilistic inferences in BN could not be guaranteed by most of the existing approximate inference methods. To address this issue, we propose the methods of Transformer based BN embedding (TBNE) and TBNE based probabilistic inferences. Specifically, we first adopt mutual information to measure the weight of parent-child node pairs and transform BN into multiple bidirectional weighted graphs (BWGs), while preserving the DAG and CPTs. Then, we redesign the Transformer model by incorporating the node importance and shortest path encodings, and extend the self-attention module of Transformer to generate node embeddings of BWGs. Following, we cast the probabilistic inference as the decoding information maximization of the path in BN from the perspective of information theory. Finally, we give an efficient algorithm for multiple probabilistic inferences by calculating embedding similarities between evidence and query nodes in BN. Experimental results show that our inference method is more efficient than the state-of-the-art competitors by several orders of magnitude while maintaining almost the same results.

Abstract Knowledge graph (KG) has become the vital resource for various applications like question answering and recommendation system. However, several relations in KG only have few observed triples, which makes it necessary to develop the method for few-shot relation prediction. In this paper, we propose the Convolutional Neural Network with Self-Attention Relation Prediction (CARP) model to predict new facts with few observed triples. First, to learn the relation property features, we build a feature encoder by using the convolutional neural network with self-attention from the few observed triples rather than background knowledge. Then, by incorporating the learned features, we give an embedding network to learn the representation of incomplete triples. Finally, we give the loss function and training algorithm of our CARP model. Experimental results on three real-world datasets show that our proposed method improves Hits@10 by 48% on average over the state-of-the-art competitors.

Spectral clustering is one of the most popular modern clustering algorithms. It is easy to implement, can be solved efficiently, and very often outperforms other traditional clustering algorithms such as k-means. However, pectral clustering would be insufficient when dealing with most datasets which have complex statistical properties and quires the user to specify the number of clusters (called k). To address these two problems, in this paper, we propose an approach to extending spectral clustering with deep embedding and estimation of the number of clusters. Specifically, we first generate the deep embedding via learning a deep autoencoder, which transforms the raw data into the lower dimensional representations that suitable for clustering. We then provide an effective method to estimate the number of clusters by learning a softmax autoencoder from the deep embedding. We finally extend spectral clustering with the learned embedding and the estimated number. An extensive experimental study on several image and text datasets illustrates the effectiveness and efficiency of our approach.

A network with n nodes contains O(n2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach.

A network with $n$ nodes contains O(n2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Furthermore, even though link prediction is closely related to missing value estimation problems, such as collaborative filtering, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity over very large networks. Due to this computational complexity, most known link prediction methods are designed for evaluating the link propensity over a specified subset of links, rather than for performing a global search over the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this paper, we propose an ensemble enabled approach to scaling up link prediction, which is able to decompose traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with the use of latent factor models, which can be effectively implemented over networks of modest size. Furthermore, the ensemble enabled approach has several advantages in terms of performance. We show the advantage of using ensemble-based latent factor models with experiments on very large networks. Experimental results demonstrate the effectiveness and scalability of our approach.

This paper proposes a natural extension of conditional functional dependencies (CFDs [1]) and conditional inclusion dependencies (CINDs [2]), denoted by CFDps and CINDps, respectively, by specifying patterns of data values with 6 ≠,, and ≥ predicates. As data quality rules, CFDps and CINDps are able to capture errors that commonly arise in practice but cannot be detected by CFDs and CINDs. We establish two sets of results for central technical problems associated with CFDps and CINDps. (a) One concerns the satisfiability and implication problems for CFDps and CINDps, taken separately or together. These are important for, e.g. deciding whether data quality rules are dirty themselves, and for removing redundant rules. We show that despite the increased expressive power, the static analyses of CFDps and CINDps retain the same complexity as their CFDs and CINDs counterparts. (b) The other concerns validation of CFDps and CINDps. We show that given a set X of CFDps and CINDps on a database D, a set of SQL queries can be automatically generated that, when evaluated against D, return all tuples in D that violate some dependencies in Σ. We also experimentally verified the efficiency and effectiveness of our SQL based error detection techniques, using real-life data. This provides commercial DBMS with an immediate capability to detect errors based on CFDps and CINDps.