Large-scale multi-agent systems face two core challenges: inefficient policy learning and the explosion of state dimensions. Existing methods often rely on manually designed task sequences to guide agents’ learning in stages, but these designs lack adaptability to agents’ learning abilities, making it difficult to ensure the rationality of task difficulty. Moreover, the representation capability of current network structures is limited, making it challenging to efficiently handle high-dimensional state information and complex interaction relationships. To address these issues, we propose a Progressive Multi-Agent Reinforcement Learning (PMARL) framework. PMARL introduces a task adapter that adaptively selects task difficulty based on agents’ learning abilities, eliminating reliance on manual experience. Additionally, a Dynamic Dimension Adaptive Network (DDAN) is designed, incorporating hypernetwork and self-attention mechanisms to achieve adaptive feature extraction of high-dimensional states and efficient representation of agent interaction relationships. Experimental results demonstrate that PMARL exhibits higher efficiency and better adaptability compared to existing methods when addressing large-scale multi-agent tasks.

Single domain generalization aims to develop a robust model trained on a source domain to generalize well on unseen target domains. Recent progress in single domain generalization has focused on expanding the scope of training data through style (e.g., backgrounds) augmentation. However, existing methods are difficult to generate data with large style shifts due to the lack of precise correlation measures between the generated and original data, and they struggle to effectively capture the consistency between the generated and original data when learning feature representations. In this article, we propose a novel Mutual Information-guided Style Augmentation (MISA) based single domain generalization method. Specifically, MISA incorporates a style diversity module, which uses the matrix-based Rényi’s \(\alpha\) -order entropy functionals to compute an approximate mutual information value between the augmented and original data, minimizing it to guide style generator learning. Moreover, MISA combines the merits of the random convolution and affine transformation to further improve the texture diversity of the augmented data. Additionally, MISA introduces a representation learning module, which minimizes the approximate mutual information value between the prediction logits of the original sample and its corresponding residual component to capture the consistency between the generated and original data for feature representation optimization. Using five real-world datasets, the extensive experiments have demonstrated the effectiveness of MISA, in comparison with state-of-the-art methods.

Cognitive diagnosis (CD) is an important task in the field of intelligent education, aiming to discover the proficiency of students on knowledge concepts with response logs. In applications, different users of the tutoring system demand for a diagnosis of knowledge concepts at different granularities. However, recent methods assume that the concepts are of the same granularity and use explicit correlations between same-granularity concepts to improve the diagnosis performance. If required for diagnosing multi-granularity concepts, these methods will face diminished performance or partial invalidation. To this end, we make the first attempt for multiple-granularity cognitive diagnosis, i.e., diagnosis on coarse- and fine-grained concepts simultaneously. Specifically, in a skillful way, the same-granularity correlations are captured and embedded into concept representations in view of concept semantics and cross-granularity correlations to model the proficiency influence between concepts implicitly. Then, the specific loss for single-granularity diagnosis and the general loss for the consistency of multi-granularity are designed to train the model jointly, achieving multiple-granularity diagnosis. Extensive experiments demonstrate that our method can achieve state-of-the-art accuracy on both coarse- and fine-grained concepts.

The explosion of data and the widespread adoption of AI techniques, especially the success of foundation models and generative AI, have transformed knowledge discovery and data mining (KDD), making them integral to real-world decision-making. For both traditional AI methods and generative AI, issues such as data noise, algorithmic bias, lack of interpretability, and privacy concerns can significantly impact the quality and reliability of extracted knowledge, thereby affecting downstream decision-making. This workshop aims to bring together researchers and practitioners from information and knowledge management, data mining, and intelligent systems to explore trustworthy KDD across diverse settings in the generative AI era. We welcome contributions on robust data preprocessing, explainable learning algorithms, bias detection and mitigation, secure and privacy-preserving mining, trustworthy knowledge graph construction, resource-efficient deployment, alignment of foundation models, and applications for social good. Special emphasis is placed on emerging challenges posed by large-scale, pre-trained models in dynamic, multi-source, and user-centric environments. By fostering dialogue between traditional KDD approaches and innovations in the foundation model era, TrustKDD seeks to advance trustworthy methodologies that align with CIKM's mission of developing reliable, scalable, and intelligent information and knowledge systems.

Entity alignment (EA) aims to find the same entities in different knowledge graphs. Existing EA methods assume the supervised aligned pairs without noise. In applications, noisy pairs lead to degradation of EA performance. To this end, a robust EA method based on knowledge distillation is proposed for noisy pairs. Firstly, the dual-teacher model with online distillation is designed, in which, noise discriminator is performed to improve the noise resistance of teacher models. Secondly, a student model is offline distilled from the dual-teacher model without using the noisy supervised pairs, further enhancing the robustness of student model. In addition, the entity structure is combined with entity representation for alignment inference to alleviate the bias of entity representation in noisy environment. Extensive experiments demonstrate the effectiveness of the proposed method.

The widespread application of pre-trained language models (PLMs) in natural language processing (NLP) has led to increasing concerns about their explainability. Selective rationalization is a self-explanatory framework that selects human-intelligible input subsets as rationales for predictions. Recent studies have shown that applying existing rationalization frameworks to PLMs will result in severe degeneration and failure problems, producing sub-optimal or meaningless rationales. Such failures severely damage trust in rationalization methods and constrain the application of rationalization techniques on PLMs. In this paper, we find that the homogeneity of tokens in the sentences produced by PLMs is the primary contributor to these problems. To address these challenges, we propose a method named Pre-trained Language Model's Rationalization (PLMR), which splits PLMs into a generator and a predictor to deal with NLP tasks while providing interpretable rationales. The generator in PLMR also alleviates homogeneity by pruning irrelevant tokens, while the predictor uses full-text information to standardize predictions. Experiments conducted on two widely used datasets across multiple PLMs demonstrate the effectiveness of the proposed method PLMR in addressing the challenge of applying selective rationalization to PLMs. Codes: https://github.com/ylb777/PLMR.

Clustering is a fundamental technique widely used for exploring the inherent data structure. Many studies indicate that an appropriate feature representation can effectively improve clustering performance. However, the existing feature representation methods are based on correlation to select or extract features, which makes it hard to deal with spurious correlations. The spurious correlations mislead the correlation-based methods to consider features that have no causal relationship as being correlative, which limits the clustering performance and feature interpretability. To tackle this issue, inspired by causal learning, we propose a new joint optimization Clustering Method with Causal Feature Embedding (CM-CaFE) , which utilizes the causality of features to learn more discriminative representation for clustering. Specifically, to eliminate spurious correlations among features, we first employ any state-of-the-art Markov blanket learning method to learn an undirected causal graph. Next, we extract the maximal fully connected causal subgraphs from the learned undirected causal graph and propose an approach to merge them to generate the causal matrix. Based on the causal matrix, we present an objective function that consists of a clustering loss term and a causal matrix fitting term to learn a causal transformation matrix. The causal transformation matrix is utilized to map the original data into a new space for clustering. Finally, we comprehensively compare the proposed method with some state-of-the-art clustering approaches on several datasets to demonstrate the effectiveness and interpretability of the proposed method.

Conditional Independence (CI) tests play an essential role in causal discovery from observational data, enabling the measurement of independence between two nodes. However, traditional CI tests ignore the imbalanced occurrence probabilities of node values, which may affect the accuracy of determining independence between nodes. To address this problem, we first introduce a new concept of the Node-imbalance phenomenon to describe the imbalance of node values in the Bayesian network data and analyze the influence of the Node-imbalance phenomenon on the traditional CI tests, then we propose a Weight-Based Conditional Independence (WCI) test to improve the accuracy of CI tests in the presence of Node-imbalance. In the experiments, we verify that WCI effectively measures the dependency between nodes in the Node-imbalance phenomenon compared with the traditional independence tests, and the state-of-the-art causal discovery algorithms reduce the number of false causal orientations through WCI.

Feature weighting aims to assign different weights to features based on their importance in machine learning tasks. In clustering tasks, the existing methods learn feature importance based on the clustering results derived from the collaborative contribution of all features, which overlooks the independent effect of each feature. In fact, there are underlying causal relationships between features and the clustering results, and the features with high causal effects are always more crucial for clustering. Therefore, we propose an enhancedFeatureWeighting method viaCausalEffect forClustering, calculating the causal effect of each feature on the clustering results for obtaining the independent contribution of each feature. Specifically, we start by identifying the causal relationships among the features and utilizing the causal relationships to generate a reasonable treatment group. Next, we compare the changes in the data distribution between the treatment and control groups to determine the causal effect of each feature. Finally, the causal effects of features are used for enhancing the clustering-driven weight learning. Moreover, we present a theory of relative order consistency in causal effect. Experimental results demonstrate that utilizing causal effect in weight learning facilitates efficient convergence and achieves superior accuracy compared to state-of-the-art clustering algorithms.

Causal feature selection has recently received increasing attention in machine learning and data mining, especially in the era of Big Data. Existing causal feature selection algorithms select unique causal features of the single class label as the optimal feature subset. However, a single class label usually has multiple classes, and it is unreasonable to select the same causal features for different classes of a single class label. To address this problem, we employ the class-specific mutual information to evaluate the causal information carried by each class of the single class label, and theoretically analyze the unique relationship between each class and the causal features. Based on this, aLabel-awareCausalFeatureSelection algorithm (LaCFS) is proposed to identifies the causal features for each class of the class label. Specifically, LaCFS uses the pairwise comparisons of class-specific mutual information and the size of class-specific mutual information values from the perspective of each class, and follows a divide-and-conquer framework to find causal features. The correctness and application condition of LaCFS are theoretically proved, and extensive experiments are conducted to demonstrate the efficiency and superiority of LaCFS compared to the state-of-the-art approaches.

As a promising strategy to achieve generalizable graph learning tasks, graph invariant learning emphasizes identifying invariant subgraphs for stable predictions on biased unknown distribution by selecting the important edges/nodes based on their contributions to the predictive tasks (i.e., subgraph predictivity). However, the existing approaches solely relying on subgraph predictivity face a challenge: the learned invariant subgraph often contains numerous spurious nodes and shows poor connectivity, undermining the generalization power of Graph Neural Networks (GNNs). To tackle this issue, we propose a summary graph-induced Invariant Learning (SIL) model that innovatively adopts a summary graph to leverage both the subgraph connectivity and predictivity for learning strong connected and accurate invariant subgraphs. Specifically, SIL first learns a summary graph containing multiple strongly connected supernodes while maintaining structure consistency with the original graph. Second, the learned summary graph is disentangled into an invariant supernode and spurious counterparts to eliminate the interference of highly predictive edges and nodes. Finally, SIL identifies a potential invariant subgraph from the invariant supernode to accomplish generalization tasks. Additionally, we provide a theoretical analysis of the summary graph learning mechanism, guaranteeing that the learned summary graph is consistent with the original graph. Experimental results validate the effectiveness of the SIL model.

Fair feature selection for classification decision tasks has recently garnered significant attention from researchers. However, existing fair feature selection algorithms fall short of providing a full explanation of the causal relationship between features and sensitive attributes, potentially impacting the accuracy of fair feature identification. To address this issue, we propose a fair causal feature selection algorithm, called FairCFS . Specifically, FairCFS constructs a localized causal graph that identifies the Markov blankets of class and sensitive variables, to block the transmission of sensitive information for selecting fair causal features. Extensive experiments on seven public real-world datasets validate that FairCFS has accuracy comparable to eight state-of-the-art feature selection algorithms while presenting more superior fairness.

Local-to-global learning approach plays an essential role in Bayesian network (BN) structure learning. Existing local-to-global learning algorithms first construct the skeleton of a DAG (directed acyclic graph) by learning the MB (Markov blanket) or PC (parents and children) of each variable in a dataset, then orient edges in the skeleton. However, existing MB or PC learning methods are often computationally expensive especially with a large-sized BN, resulting in inefficient local-to-global learning algorithms. To tackle the problem, in this article, we link feature selection with local BN structure learning and develop an efficient local-to-global learning approach using filtering feature selection. Specifically, we first analyze the rationale of the well-known Minimum-Redundancy and Maximum-Relevance (MRMR) feature selection approach for learning a PC set of a variable. Based on the analysis, we propose an efficient F2SL (feature selection-based structure learning) approach to local-to-global BN structure learning. The F2SL approach first employs the MRMR approach to learn the skeleton of a DAG, then orients edges in the skeleton. Employing independence tests or score functions for orienting edges, we instantiate the F2SL approach into two new algorithms, F2SL-c (using independence tests) and F2SL-s (using score functions). Compared to the state-of-the-art local-to-global BN learning algorithms, the experiments validated that the proposed algorithms in this article are more efficient and provide competitive structure learning quality than the compared algorithms.

Cross-lingual entity alignment (CLEA) aims to find equivalent entity pairs between knowledge graphs (KGs) in different languages. It is an important way to connect heterogeneous KGs and facilitate knowledge completion. Existing methods have found that incorporating relations into entities can effectively improve KG representation and benefit entity alignment, and these methods learn relation representation depending on entities, which cannot capture the diverse structures of relations. However, multiple relations in KG form diverse structures, such as adjacency structure and ring structure. This diversity of relation structures makes the relation representation challenging. Therefore, we propose to construct the weighted line graphs to model the diverse structures of relations and learn relation representation independently from entities. Especially, owing to the diversity of adjacency structures and ring structures, we propose to construct adjacency line graph and ring line graph, respectively, to model the structures of relations and to further improve entity representation. In addition, to alleviate the hubness problem in alignment, we introduce the optimal transport into alignment and compute the distance matrix in a different way. From a global perspective, we calculate the optimal 1-to-1 alignment bi-directionally to improve the alignment accuracy. Experimental results on two benchmark datasets show that our proposed method significantly outperforms state-of-the-art CLEA methods in both supervised and unsupervised manners.

Inferring causal structures from experimentation is a challenging task in many fields. Most causal structure learning algorithms with unknown interventions are proposed to discover causal relationships over an identical variable set. However, often due to privacy, ethical, financial, and practical concerns, the variable sets observed by multiple sources or domains are not entirely identical. While a few algorithms are proposed to handle the partially overlapping variable sets, they focus on the case of known intervention targets. Therefore, to be close to the real-world environment, we consider discovering causal relationships over overlapping variable sets under the unknown intervention setting and exploring a scenario where a problem is studied across multiple domains. Here, we propose an algorithm for discovering the causal relationships over the integrated set of variables from unknown interventions, mainly handling the entangled inconsistencies caused by the incomplete observation of variables and unknown intervention targets. Specifically, we first distinguish two types of inconsistencies and then deal with respectively them by presenting some lemmas. Finally, we construct a fusion rule to combine learned structures of multiple domains, obtaining the final structures over the integrated set of variables. Theoretical analysis and experimental results on synthetic, benchmark, and real-world datasets have verified the effectiveness of the proposed algorithm.

Causal structure learning (CSL) from observational data is a crucial objective in various machine learning applications. Recent advances in CSL have focused on local-to-global learning, which offers improved efficiency and accuracy. The local-to-global CSL algorithms first learn the local skeleton of each variable in a dataset, then construct the global skeleton by combining these local skeletons, and finally orient edges to infer causality. However, data quality issues such as noise and small samples often result in the presence of problematicasymmetric edgesduring global skeleton construction, hindering the creation of a high-quality global skeleton. To address this challenge, we propose a novel local-to-global CSL algorithm with a progressive enhancement strategy and make the following novel contributions: 1) To construct an accurate global skeleton, we design a novel strategy to iteratively correctasymmetric edgesand progressively improve the accuracy of the global skeleton. 2) Based on the learned accurate global skeleton, we design an integrated global skeleton orientation strategy to infer the correct directions of edges for obtaining an accurate and reliable causal structure. Extensive experiments demonstrate that our method achieves better performance than the existing CSL methods.

In educational data mining, knowledge tracing (KT) aims to model learning performance based on student knowledge mastery. Deep-learning-based KT models perform remarkably better than traditional KT and have attracted considerable attention. However, most of them lack interpretability, making it challenging to explain why the model performed well in the prediction. In this paper, we propose an interpretable deep KT model, referred to as fuzzy deep knowledge tracing (FDKT) via fuzzy reasoning. Specifically, we formalize continuous scores into several fuzzy scores using the fuzzification module. Then, we input the fuzzy scores into the fuzzy reasoning module (FRM). FRM is designed to deduce the current cognitive ability, based on which the future performance was predicted. FDKT greatly enhanced the intrinsic interpretability of deep-learning-based KT through the interpretation of the deduction of student cognition. Furthermore, it broadened the application of KT to continuous scores. Improved performance with regard to both the advantages of FDKT was demonstrated through comparisons with the state-of-the-art models.

Almost all existing causal feature selection methods are proposed without considering the problem of sample selection bias. However, in practice, as data-gathering process cannot be fully controlled, sample selection bias often occurs, leading to spurious correlations between features and the class variable, which seriously deteriorates the performance of those existing methods. In this article, we study the problem of causal feature selection under sample selection bias and propose a novel Progressive Causal Feature Selection (PCFS) algorithm which has three phases. First, PCFS learns the sample weights to balance the treated group and control group distributions corresponding to each feature for removing spurious correlations. Second, based on the sample weights, PCFS uses a weighted cross-entropy model to estimate the causal effect of each feature and removes some irrelevant features from the confounder set. Third, PCFS progressively repeats the first two phases to remove more irrelevant features and finally obtains a causal feature set. Using synthetic and real-world datasets, the experiments have validated the effectiveness of PCFS, in comparison with several state-of-the-art classical and causal feature selection methods.

Directed acyclic graph (DAG) learning plays a key role in causal discovery and many machine learning tasks. Learning a DAG from high-dimensional data always faces scalability problems. A local-to-global DAG learning approach can be scaled to high-dimensional data, however, existing local-to-global DAG learning algorithms employ either the AND-rule or the OR-rule for constructing a DAG skeleton. Simply using either rule, existing local-to-global methods may learn an inaccurate DAG skeleton, leading to unsatisfactory DAG learning performance. To tackle this problem, in this paper, we propose anAdaptiveDAGLearning (ADL) algorithm. The novel contribution of ADL is that it can simultaneously and adaptively use the AND-rule and the OR-rule to construct an accurate global DAG skeleton. We conduct extensive experiments on both benchmark and real-world datasets, and the experimental results show that ADL is significantly better than some existing local-to-global and global DAG learning algorithms.

Causal feature selection has received increasing attention in recent years. However, the state-of-the-art causal feature selection algorithms use the conditional independence tests, which require enumerating conditioning sets, leading to an exponential increase in computational complexity along with an increase in feature space. To address this problem, in this paper, we theoretically analyze the unique performance of causal features in mutual information, and propose a novelCausalFeatureSelection algorithm usingMutualInformation, called CFS-MI. Specifically, CFS-MI separately instantiates the pairwise comparison of mutual information in two stages to reduce computational complexity, and thus improves the efficiency on high-dimensional data. Extensive experiments on 5 benchmark Bayesian networks and 16 real-world datasets validate that CFS-MI has comparable accuracy compared to 7 state-of-the-art causal feature selection algorithms, while presenting more superior computational efficiency.

In this study, we investigate a challenging problem, namely, robust domain adaptation, where data from only a single well-labeled source domain are available in the training phase. To address this problem, assuming that the causal relationships between the features and the class variable are robust across domains, we propose a novel causal autoencoder (CAE), which integrates a deep autoencoder and a causal structure learning model to learn causal representations using data from a single source domain. Specifically, a deep autoencoder model is adopted to learn the low-dimensional representations, and a causal structure learning model is designed to separate the low-dimensional representations into two groups: causal representations and task-irrelevant representations. Using three real-world datasets, the experiments have validated the effectiveness of CAE, in comparison with eleven state-of-the-art methods.

Cross-lingual entity alignment, which is an important task in the field of graph mining, aims to find equivalent entity pairs from two knowledge graphs. Recent methods show that relation representation can be used to improve entity representation and entity alignment. However, relation representation is learned dependently on entity representation, and both representations are learned from node-centered knowledge graphs. This dependency of relation on entity results in poor relation representation and leads to limited enhancement of entity representation. Therefore, to address this challenge, we propose novel relation-aware line graph neural networks for cross-lingual entity alignment (RALG). More specifically, we first propose to learn relation representation with heterogeneous line graphs independently from entities. The constructed heterogeneous line graphs can capture the correlation of relations explicitly. Secondly, we design a new way of aggregation in the form of triples to strengthen the relevance between entities and their corresponding relations. Experiments conducted on real-world datasets show that independent learning of relation representation with line graphs can represent relations better, and our method achieves better performance than the state-of-the-art methods for entity alignment.

Learning a causal structure from observational data is crucial for data scientists. Recent advances in causal structure learning (CSL) have focused on local-to-global learning, since the local-to-global CSL can be scaled to high-dimensional data. The local-to-global CSL algorithms first learn the local skeletons, then construct the global skeleton, and finally orient edges. In practice, the performance of local-to-global CSL mainly depends on the accuracy of the global skeleton. However, in many real-world settings, owing to inevitable data quality issues (e.g. noise and small sample), existing local-to-global CSL methods often yield many asymmetric edges (e.g., given anasymmetric edge containing variables A and B, the learned skeleton of A contains B, but the learned skeleton of B does not contain A), which make it difficult to construct a high quality global skeleton. To tackle this problem, this paper proposes a Bootstrap sampling based Causal Structure Learning (BCSL) algorithm. The novel contribution of BCSL is that it proposes an integrated global skeleton learning strategy that can construct more accurate global skeletons. Specifically, this strategy first utilizes the Bootstrap method to generate multiple sub-datasets, then learns the local skeleton of variables on each asymmetric edge on those sub-datasets, and finally designs a novel scoring function to estimate the learning results on all sub-datasets for correcting the asymmetric edge. Extensive experiments on both benchmark and real datasets verify the effectiveness of the proposed method.

Abstract A large number of covariates can have a negative impact on the quality of causal effect estimation since confounding adjustment becomes unreliable when the number of covariates is large relative to the number of samples. Propensity score is a common way to deal with a large covariate set, but the accuracy of propensity score estimation (normally done by logistic regression) is also challenged by the large number of covariates. In this paper, we prove that a large covariate set can be reduced to a lower dimensional representation which captures the complete information for adjustment in causal effect estimation. The theoretical result enables effective data-driven algorithms for causal effect estimation. Supported by the result, we develop an algorithm that employs a supervised kernel dimension reduction method to learn a lower dimensional representation from the original covariate space, and then utilises nearest neighbour matching in the reduced covariate space to impute the counterfactual outcomes to avoid the large sized covariate set problem. The proposed algorithm is evaluated on two semisynthetic and three real-world datasets and the results show the effectiveness of the proposed algorithm.

Learning partial Bayesian network (BN) structure is an interesting and challenging problem. In this challenge, it is computationally expensive to use global BN structure learning algorithms, while only one part of a BN structure is interesting, local BN structure learning algorithms are not a favourable solution either due to the issue of false edge orientation. To address the problem, this article first presents a detailed analysis of the false edge orientation issue with local BN structure learning algorithms and then proposes PSL, an efficient and accurate P artial BN S tructure L earning (PSL) algorithm. Specifically, PSL divides V-structures in a Markov blanket (MB) into two types: Type-C V-structures and Type-NC V-structures, then it starts from the given node of interest and recursively finds both types of V-structures in the MB of the current node until all edges in the partial BN structure are oriented. To further improve the efficiency of PSL, the PSL-FS algorithm is designed by incorporating F eature S election (FS) into PSL. Extensive experiments with six benchmark BNs validate the efficiency and accuracy of the proposed algorithms.

Causal feature selection aims at learning the Markov blanket (MB) of a class variable for feature selection. The MB of a class variable implies the local causal structure among the class variable and its MB and all other features are probabilistically independent of the class variable conditioning on its MB, this enables causal feature selection to identify potential causal features for feature selection for building robust and physically meaningful prediction models. Missing data, ubiquitous in many real-world applications, remain an open research problem in causal feature selection due to its technical complexity. In this article, we discuss a novel multiple imputation MB (MimMB) framework for causal feature selection with missing data. MimMB integrates Data Imputation with MB Learning in a unified framework to enable the two key components to engage with each other. MB Learning enables Data Imputation in a potentially causal feature space for achieving accurate data imputation, while accurate Data Imputation helps MB Learning identify a reliable MB of the class variable in turn. Then, we further design an enhanced kNN estimator for imputing missing values and instantiate the MimMB. In our comprehensively experimental evaluation, our new approach can effectively learn the MB of a given variable in a Bayesian network and outperforms other rival algorithms using synthetic and real-world datasets.

In this article, we aim to develop a unified view of causal and non-causal feature selection methods. The unified view will fill in the gap in the research of the relation between the two types of methods. Based on the Bayesian network framework and information theory, we first show that causal and non-causal feature selection methods share the same objective. That is to find the Markov blanket of a class attribute, the theoretically optimal feature set for classification. We then examine the assumptions made by causal and non-causal feature selection methods when searching for the optimal feature set, and unify the assumptions by mapping them to the restrictions on the structure of the Bayesian network model of the studied problem. We further analyze in detail how the structural assumptions lead to the different levels of approximations employed by the methods in their search, which then result in the approximations in the feature sets found by the methods with respect to the optimal feature set. With the unified view, we can interpret the output of non-causal methods from a causal perspective and derive the error bounds of both types of methods. Finally, we present practical understanding of the relation between causal and non-causal methods using extensive experiments with synthetic data and various types of real-world data.

The discovery of Markov blanket (MB) for feature selection has attracted much attention in recent years, since the MB of the class attribute is the optimal feature subset for feature selection. However, almost all existing MB discovery algorithms focus on either improving computational efficiency or boosting learning accuracy, instead of both. In this article, we propose a novel MB discovery algorithm for balancing efficiency and accuracy, called BAlanced Markov Blanket (BAMB) discovery. To achieve this goal, given a class attribute of interest, BAMB finds candidate PC (parents and children) and spouses and removes false positives from the candidate MB set in one go. Specifically, once a feature is successfully added to the current PC set, BAMB finds the spouses with regard to this feature, then uses the updated PC and the spouse set to remove false positives from the current MB set. This makes the PC and spouses of the target as small as possible and thus achieves a trade-off between computational efficiency and learning accuracy. In the experiments, we first compare BAMB with 8 state-of-the-art MB discovery algorithms on 7 benchmark Bayesian networks, then we use 10 real-world datasets and compare BAMB with 12 feature selection algorithms, including 8 state-of-the-art MB discovery algorithms and 4 other well-established feature selection methods. On prediction accuracy, BAMB outperforms 12 feature selection algorithms compared. On computational efficiency, BAMB is close to the IAMB algorithm while it is much faster than the remaining seven MB discovery algorithms.

Feature selection is important in many big data applications. Two critical challenges closely associate with big data. First, in many big data applications, the dimensionality is extremely high, in millions, and keeps growing. Second, big data applications call for highly scalable feature selection algorithms in an online manner such that each feature can be processed in a sequential scan. We present SAOLA, a Scalable and Accurate OnLine Approach for feature selection in this paper. With a theoretical analysis on bounds of the pairwise correlations between features, SAOLA employs novel pairwise comparison techniques and maintains a parsimonious model over time in an online manner. Furthermore, to deal with upcoming features that arrive by groups, we extend the SAOLA algorithm, and then propose a new group-SAOLA algorithm for online group feature selection. The group-SAOLA algorithm can online maintain a set of feature groups that is sparse at the levels of both groups and individual features simultaneously. An empirical study using a series of benchmark real datasets shows that our two algorithms, SAOLA and group-SAOLA, are scalable on datasets of extremely high dimensionality and have superior performance over the state-of-the-art feature selection methods.

Reliable tornado forecasting with a long-lead time can greatly support emergency response and is of vital importance for the economy and society. The large number of meteorological variables in spatiotemporal domains and the complex relationships among variables remain the top difficulties for a long-lead tornado forecasting.

Many datasets from real-world applications have very high-dimensional or increasing feature space. It is a new research problem to learn and maintain a classifier to deal with very high dimensionality or streaming features. In this article, we adapt the well-known emerging-pattern--based classification models and propose a semi-streaming approach. For streaming features, it is computationally expensive or even prohibitive to mine long-emerging patterns, and it is nontrivial to integrate emerging-pattern mining with feature selection. We present an online feature selection step, which is capable of selecting and maintaining a pool of effective features from a feature stream. Then, in our offline step, separated from the online step, we periodically compute and update emerging patterns from the pool of selected features from the online step. We evaluate the effectiveness and efficiency of the proposed method using a series of benchmark datasets and a real-world case study on Mars crater detection. Our proposed method yields classification performance comparable to the state-of-art static classification methods. Most important, the proposed method is significantly faster and can efficiently handle datasets with streaming features.

Feature selection is important in many big data applications. There are at least two critical challenges. Firstly, in many applications, the dimensionality is extremely high, in millions, and keeps growing. Secondly, feature selection has to be highly scalable, preferably in an online manner such that each feature can be processed in a sequential scan. In this paper, we develop SAOLA, a Scalable and Accurate On Line Approach for feature selection. With a theoretical analysis on a low bound on the pair wise correlations between features in the currently selected feature subset, SAOLA employs novel online pair wise comparison techniques to address the two challenges and maintain a parsimonious model over time in an online manner. An empirical study using a series of benchmark real data sets shows that SAOLA is scalable on data sets of extremely high dimensionality, and has superior performance over the state-of-the-art feature selection methods.

In faithful Bayesian networks, the Markov blanket of the class attribute is a unique and minimal feature subset for optimal feature selection. However, little attention has been paid to Markov blanket feature selection in a non-faithful environment which widely exists in the real world. To tackle this issue, in this paper, we deal with non-faithful data distributions and propose the concept of representative sets instead of Markov blankets. With a standard sparse group lasso for selection of features from the representative sets, we design an effective algorithm, SRS, for Markov blanket feature Selection via Representative Sets with non-faithful data distributions. Empirical studies demonstrate that SRS outperforms the state-of-the-art Markov blanket feature selectors and other well-established feature selection methods.

The development of disastrous flood forecasting techniques able to provide warnings at a long lead-time (5-15 days) is of great importance to society. Extreme Flood is usually a consequence of a sequence of precipitation events occurring over from several days to several weeks. Though precise short-term forecasting the magnitude and extent of individual precipitation event is still beyond our reach, long-term forecasting of precipitation clusters can be attempted by identifying persistent atmospheric regimes that are conducive for the precipitation clusters. However, such forecasting will suffer from overwhelming number of relevant features and high imbalance of sample sets. In this paper, we propose an integrated data mining framework for identifying the precursors to precipitation event clusters and use this information to predict extended periods of extreme precipitation and subsequent floods. We synthesize a representative feature set that describes the atmosphere motion, and apply a streaming feature selection algorithm to online identify the precipitation precursors from the enormous feature space. A hierarchical re-sampling approach is embedded in the framework to deal with the imbalance problem. An extensive empirical study is conducted on historical precipitation and associated flood data collected in the State of Iowa. Utilizing our framework a few physically meaningful precipitation cluster precursor sets are identified from millions of features. More than 90% of extreme precipitation events are captured by the proposed prediction model using precipitation cluster precursors with a lead time of more than 5 days.

It is a nontrivial task to build an accurate emerging pattern (EP) classifier from high-dimensional data because we inevitably face two challenges 1) how to efficiently extract a minimal set of strongly predictive EPs from an explosive number of candidate patterns, and 2) how to handle the highly sensitive choice of the minimal support threshold. To address these two challenges, we bridge causal relevance and EP discriminability (the predictive ability of emerging patterns) to facilitate EP mining and propose a new framework of mining EPs from high-dimensional data. In this framework, we study the relationships between causal relevance in a causal Bayesian network and EP discriminability in EP mining, and then reduce the pattern space of EP mining to direct causes and direct effects, or the Markov blanket (MB) of the class attribute in a causal Bayesian network. The proposed framework is instantiated by two EPs-based classifiers, CE-EP and MB-EP, where CE stands for direct Causes and direct Effects, and MB for Markov Blanket. Extensive experiments on a broad range of data sets validate the effectiveness of the CE-EP and MB-EP classifiers against other well-established methods, in terms of predictive accuracy, pattern numbers, running time, and sensitivity analysis.

Building an accurate emerging pattern classifier with a high-dimensional dataset is a challenging issue. The problem becomes even more difficult if the whole feature space is unavailable before learning starts. This paper presents a new technique on mining emerging patterns using streaming feature selection. We model high feature dimensions with streaming features, that is, features arrive and are processed one at a time. As features flow in one by one, we online evaluate each coming feature to determine whether it is useful for mining predictive emerging patterns (EPs) by exploiting the relationship between feature relevance and EP discriminability (the predictive ability of an EP). We employ this relationship to guide an online EP mining process. This new approach can mine EPs from a high-dimensional dataset, even when its entire feature set is unavailable before learning. The experiments on a broad range of datasets validate the effectiveness of the proposed approach against other well-established methods, in terms of predictive accuracy, pattern numbers and running time.

Associative classifiers have received considerable attention due to their easy to understand models and promising performance. However, with a high dimensional dataset, associative classifiers inevitably face two challenges: (1) how to extract a minimal set of strong predictive rules from an explosive number of generated association rules, and (2) how to deal with the highly sensitive choice of the minimal support threshold. In order to address these two challenges, we introduce causality into associative classification, and propose a new framework of causal associative classification. In this framework, we use causal Bayesian networks to bridge irrelevant and redundant features with irrelevant and redundant rules in associative classification. Without loss of prediction power, the feature space involved with the antecedent of a classification rule is reduced to the space of the direct causes, direct effects, and direct causes of the direct effects, a.k.a. the Markov blanket, of the consequent of the rule in causal Bayesian networks. The proposed framework is instantiated via baseline classifiers using emerging patterns. Experimental results show that our framework significantly reduces the model complexity while outperforming the other state-of-the-art algorithms.

In this paper, we study a new research problem of causal discovery from streaming features. A unique characteristic of streaming features is that not all features can be available before learning begins. Feature generation and selection often have to be interleaved. Managing streaming features has been extensively studied in classification, but little attention has been paid to the problem of causal discovery from streaming features. To this end, we propose a novel algorithm to solve this challenging problem, denoted as CDFSF (Causal Discovery From Streaming Features) which consists of two phases: growing and shrinking. In the growing phase, CDFSF finds candidate parents or children for each feature seen so far, while in the shrinking phase the algorithm dynamically removes false positives from the current sets of candidate parents and children. In order to improve the efficiency of CDFSF, we present S-CDFSF, a faster version of CDFSF, using two symmetry theorems. Experimental results validate our algorithms in comparison with other state-of-art algorithms of causal discovery.