With the widespread use of Graph Neural Networks (GNNs) for representation learning from network data, the fairness of GNN models has raised great attention lately. Fair GNNs aim to ensure that node representations can be accurately classified, but not easily associated with a specific group. Existing advanced approaches essentially enhance the generalisation of node representation in combination with data augmentation strategy and do not directly impose constraints on the fairness of GNNs. In this work, we identify that a fundamental reason for the unfairness of GNNs is the phenomenon of social homophily , i.e., users in the same group are more inclined to congregate. The message-passing mechanism of GNNs can cause users in the same group to have similar representations due to social homophily, leading model predictions to establish spurious correlations with sensitive attributes. Inspired by this reason, we propose a method called Equity-Aware GNN (EAGNN) towards fair graph representation learning. Specifically, to ensure that model predictions are independent of sensitive attributes while maintaining prediction performance, we introduce constraints for fair representation learning based on three principles: sufficiency, independence and separation. We theoretically demonstrate that our EAGNN method can effectively achieve group fairness. Extensive experiments on three datasets with varying levels of social homophily illustrate that our EAGNN method achieves the state-of-the-art performance across two fairness metrics and offers competitive effectiveness.

Partial Multi-Label Learning (PML) is an emerging weakly supervised learning framework, where each instance contains a candidate label set with only some labels being ground-truth labels. Many existing PML methods recover the information of the ground-truth label set through k-Nearest Neighbor (kNN) disambiguation. However, this popular strategy might be suboptimal, as it makes disambiguation for a given instance based solely on its neighbors' features and class labels, i.e., the local structural information in the feature space, thereby missing the opportunity to explicitly and sufficiently leverage the global structural information in the feature space to facilitate disambiguation. In this paper, we propose a novel algorithm called PRAG, i.e., PaRtiAl multi-label learning by exploiting Global information, which incorporates the global factor obtained from the features of all the training instances into the kNN disambiguation process. Specifically, we learn for each instance a global factor vector, which captures the global affinity between an instance and each label across the feature space. This global factor vector is continuously updated through iterative propagation, with each iteration computing the global factor vector based on the similarity between the instance's features and a dynamically constructed label prototype for each label. The label prototype is formed by aggregating the features of all training instances weighted by their current estimated confidence for that label. Crucially, the global factor vector serves as a weighting mechanism during aggregation of the neighbor labels in the kNN disambiguation step. It effectively injects global structural information into the local disambiguation process, providing a more robust estimation of label confidence by mitigating the limitations of relying solely on potentially noisy local neighbors. Based on the estimated label confidence, PRAG then exploits label correlations to classify instances. We conducted extensive experiments on various real and synthetic datasets, and the results show the superiority of PRAG compared to the state-of-the-art methods.

Recommender systems are crucial for providing personalised experiences, but their effectiveness is often undermined by confounding bias, particularly in the presence of latent confounders. Existing debiasing methods typically address only one type of latent confounding bias, often ignoring the complex interactions caused by latent confounders, such as those between items and user feedback, and between item exposure and user feedback. To tackle these challenges, we propose a novel Deep Instrumental Variables (IV) approach for debiased representation learning in Recommendation Systems, referred to as DIVERS. Specifically, DIVERS leverages user feature embeddings as IVs to mitigate the confounding bias between items and user feedback caused by latent confounders, and combines the debiased item embeddings with an item exposure vector to generate a reconstructed item exposure vector. Moreover, DIVERS employs an identifiable Variational Auto-Encoder (iVAE) to infer identifiable representations by utilising information from both the original and reconstructed item exposure vectors, effectively addressing the confounding bias introduced by latent confounders between item exposure and user feedback. Additionally, we provide theoretical analyses to demonstrate the soundness of using IV and the identifiability of the representation learned by DIVERS. Extensive experiments on both synthetic and real-world datasets confirm that DIVERS outperforms state-of-the-art models in reducing bias and providing reliable recommendations. Our source code is available at: https://github.com/djf-web/DIVERS.

Off-policy evaluation (OPE) is a crucial problem in reinforcement learning (RL), where the goal is to estimate the long-term cumulative reward of a target policy using historical data generated by a potentially different behaviour policy. In many real-world applications, such as precision medicine and recommendation systems, unobserved confounders may influence the action, reward, and state transition dynamics, which leads to biased estimates if not properly addressed. While existing methods for handling unobserved confounders in OPE focus on single-action settings, they are less effective in multi-action scenarios commonly found in practical applications, where an agent can take multiple actions simultaneously. In this paper, we propose a novel auxiliary variable-aided method for OPE in multi-action settings with unobserved confounders. Our approach overcomes the limitations of traditional auxiliary variable methods for multi-action scenarios by requiring only a single auxiliary variable, relaxing the need for as many auxiliary variables as the actions. Through theoretical analysis, we prove that our method provides an unbiased estimation of the target policy value. Empirical evaluations demonstrate that our estimator achieves better performance compared to existing baseline methods, highlighting its effectiveness and reliability in addressing unobserved confounders in multi-action OPE settings.

Abstract Within the realm of causal inference, a pivotal task involves causal effect estimation from observational data when there exist confounding variables. The K-Nearest Neighbour Matching (K-NNM) method is widely applied to handle confounding bias, but its general application sets a uniform K value for all samples, which can lead to suboptimal results in practice. To overcome this limitation, this paper introduces a novel method for causal effect estimation called Dynamic K-Nearest Neighbour Matching (DK-NNM). The DK-NNM method employs a data-driven learning strategy to determine the optimal value of K for each sample. In practice, DK-NNM reconstructs a sparse coefficient matrix for all samples using sparse learning, while simultaneously learning a graph matrix to preserve local information and sample similarity. This approach helps identify the most suitable K-value for each sample. Additionally, DK-NNM utilizes joint propensity and prognostic scores to effectively mitigate confounding bias arising from high-dimensional covariates during the K-NNM process. Experiments performed on various synthetic, semi-synthetic, and real-world datasets conclusively demonstrate that DK-NNM surpasses baseline models in estimating causal effects from observational data and provides significant improvements over traditional methods.

The rapid development of Large Language Models (LLMs) creates new opportunities for recommender systems, especially by exploiting the side information (e.g., descriptions and analyses of items) generated by these models. However, aligning this side information with collaborative information from historical interactions poses significant challenges. The inherent biases within LLMs can skew recommendations, resulting in distorted and potentially unfair user experiences. On the other hand, propensity bias causes side information to be aligned in such a way that it often tends to represent all inputs in a low-dimensional subspace, leading to a phenomenon known as dimensional collapse, which severely restricts the recommender system’s ability to capture user preferences and behaviors. To address these issues, we introduce a novel framework named Counterfactual LLM Recommendation (CLLMR). Specifically, we propose a spectrum-based side information encoder that implicitly embeds structural information from historical interactions into the side information representation, thereby circumventing the risk of dimension collapse. Furthermore, our CLLMR approach explores the causal relationships inherent in LLM-based recommender systems. By leveraging counterfactual inference, we counteract the biases introduced by LLMs. Extensive experiments demonstrate that our CLLMR approach consistently enhances the performance of various recommender models.

In the pursuit of intersectional group fairness in machine learning models, significant attention has been directed towards fair representation learning methods. These methods aim to mitigate bias in training data by encoding data effectively while removing sensitive attribute information. However, existing fair representation learning methods often assume that decoupling sensitive attribute information from the latent representation will automatically lead to fairness on any downstream tasks learnt on the non-sensitive subspace of the latent representation. Nonetheless, biases can persist even when using representations devoid of sensitive attribute information. This is due to the learning algorithm's influence during downstream task training. In this paper, we propose a method dubbed FairReg which integrates fairness regularization with fair representation learning. This unified approach creates a more comprehensive and robust framework for ensuring intersectional group fairness in machine learning models. Empirical evaluations conducted on two real-world depression prediction datasets demonstrate the effectiveness of our method in improving intersectional group fairness compared to existing approaches.

Recommender systems rely on observational data to predict user ratings for unseen items. Since the observational data is typically missing not at random (MNAR), they contain biases, predominantly selection bias, thus models trained on such data are inherently biased. If a shadow variable, which is a variable used instead of user's latent variables that influence both the treatment and the outcome, can be identified, it is possible to build unbiased models for recommender systems. To overcome the challenge of manually identifying valid shadow variables in the data, we propose a Shadow Variable Catcher (SVC), a model designed to learn the latent representation of shadow variables from observational data. By using the learned representation of shadow variables by SVC, we develop the Shadow Debiased Recommender (SDR) method to build an unbiased collaborative filtering model for addressing selection bias in recommender systems. Comprehensive experiments on both synthetic and real-world datasets, have verified the performance of SDR and demonstrated its effectiveness and robustness, and offer new insights into the mitigation of bias in recommender systems.

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.

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.

As an emerging weakly supervised learning framework, partial label learning aims to induce a multi-class classifier from ambiguous supervision information where each training example is associated with a set of candidate labels, among which only one is the true label. Traditional feature selection methods, either for single label and multiple label problems, are not applicable to partial label learning as the ambiguous information contained in the label space obfuscates the importance of features and misleads the selection process. This makes the selection of a proper feature subset from partial label examples particularly challenging, and therefore has rarely been investigated. In this paper, we propose a novel feature selection algorithm for partial label learning, named PLFS, which considers not only the relationships between features and labels, but also exploits the relationships between instances to select the most informative and important features to enhance the performance of partial label learning. PLFS constructs an adaptive weighted graph to exploit the similarity information among instances, differentiate the label space and weight the feature space, which leads to the selection of a proper feature subset. Extensive experiments over a broad range of benchmark data sets clearly validate the effectiveness of our proposed feature selection approach.

Researchers have developed various visualization techniques, such as attribution maps, to understand which parts of an input contribute most to a model’s decision. However, existing methods often produce disparate results and may lack human-perceptual interpretability. In this work, we propose Relevance-IBA, a novel approach that combines the strengths of Information Bottleneck Attribution (IBA) and Layer-wise Relevance Propagation’s (LRP) method to estimate more accurate and human-perceptually interpretable attribution maps. Our method accentuates the contours and subtle details of the identified object, making the model’s decisions more intuitively understandable. Additionally, we introduce a segmentation-oriented evaluation technique, which assesses the capacity of interpretability methods by emphasizing the most important pixels within an object’s boundaries. We benchmark Relevance-IBA against various methodologies, including DeepLIFT, Integrated Gradients, Guided-BP, Guided-GradCAM, IBA, and InputIBA. Our results indicate that Relevance-IBA not only boosts attribution accuracy but also prioritizes human-perceptual clarity, making it a valuable tool for interpreting complex model behaviors.

In causal inference, it is a fundamental task to estimate the causal effect from observational data. However, latent confounders pose major challenges in causal inference in observational data, for example, confounding bias and M-bias. Recent data-driven causal effect estimators tackle the confounding bias problem via balanced representation learning, but assume no M-bias in the system, thus they fail to handle the M-bias. In this paper, we identify a challenging and unsolved problem caused by a variable that leads to confounding bias and M-bias simultaneously. To address this problem with co-occurring M-bias and confounding bias, we propose a novel Disentangled Latent Representation learning framework for learning latent representations from proxy variables for unbiased Causal effect Estimation (DLRCE) from observational data. Specifically, DLRCE learns three sets of latent representations from the measured proxy variables to adjust for the confounding bias and M-bias. Extensive experiments on both synthetic and three real-world datasets demonstrate that DLRCE significantly outperforms the state-of-the-art estimators in the case of the presence of both confounding bias and M-bias.

In Disability Employment Services (DES), an emerging problem is to make job survival analysis stable in unseen environments without prior knowledge of these environments. Existing survival analysis methods cannot adequately solve this problem since they assume that distribution of unseen data is similar to that observed during training. However, this assumption can be violated in practice where unanticipated events such as COVID19 and inflation can change the work and life patterns of people with disability. Models trained before the COVID19 pandemic may make unreliable job survival predictions in COVID19 or inflation situations. It is also costly and time consuming to frequently re-train and deploy the models. This paper proposes a stable survival analysis method for the DES sector without requiring prior knowledge of deployment environments. Latent representations are learned to capture non-linear relationships between relevant features and job survival time. Two reweighting stages are developed to remove censoring and conditional spurious correlations between irrelevant features and the survival outcome. The case study of Australian workers with disability shows that our method can make stable risk predictions. It can also help workers with disability determine the most effective skills for improvement to increase their job survival time. Further evaluations with public datasets show the promising stable performance of our method in other applications.

Multi-label learning deals with the problem where an instance is associated with multiple labels simultaneously. Multi-label data is often of high dimensionality and has many noisy, irrelevant, and redundant features. As an important machine learning task, multi-label feature selection has received considerable attention in recent years due to its promising performance in dealing with high-dimensional multi-label data. Existing multi-label feature selection methods typically select the global features which are shared by all instances in a dataset. However, these multi-label feature selection methods may be suboptimal since they do not consider the specific characteristics of instances. In this paper, we propose a novel algorithm that integrates Global and Local Feature Selection (GLFS) to exploit both the global features and a subset of discriminative features shared only locally by a subgroup of instances in a multi-label dataset. Specifically, GLFS employs linear regression and ℓ 2,1 -norm on the regression parameters to achieve simultaneous global and local feature selection. Moreover, the proposed algorithm has an effective mechanism for utilizing label correlations to improve the feature selection. Experiments on real-world multi-label datasets show the superiority of GLFS over the state-of-the-art multi-label feature selection methods.

In multi-label learning, each instance is associated with multiple labels simultaneously. Multi-label data often have noisy, irrelevant, and redundant features of high dimensionality. Multi-label feature selection has received considerable attention as an effective means for dealing with high-dimensional multi-label data. Many multi-label feature selection methods exploit label correlations to help select features. However, finding label correlations and selecting features in existing multi-label feature selection methods are often two separate processes, the existence of noises and outliers in training data makes the label correlations exploited from label space less reliable. Therefore, the learned label correlations may mislead the feature selection process and result in the selection of less informative features. This article proposes a novel algorithm named ROAD, i.e., multi-label featuRe selectiOn via ADaptive label correlation estimation. ROAD jointly performs adaptive label correlation exploration and feature selection with alternating optimization to obtain reliable estimation of label correlations, which can more effectively reveal the intrinsic manifold structure among labels and lead to the selection of a more proper feature subset. Comprehensive experiments on several frequently used datasets validate the superiority of ROAD against the state-of-the-art multi-label feature selection algorithms.

Causal effect estimation from observational data is a challenging problem, especially with high dimensional data and in the presence of unobserved variables. The available data-driven methods for tackling the problem either provide an estimation of the bounds of a causal effect (i.e., nonunique estimation) or have low efficiency. The major hurdle for achieving high efficiency while trying to obtain unique and unbiased causal effect estimation is how to find a proper adjustment set for confounding control in a fast way, given the huge covariate space and considering unobserved variables. In this paper, we approach the problem as a local search task for finding valid adjustment sets in data. We establish the theorems to support the local search for adjustment sets, and we show that unique and unbiased estimation can be achieved from observational data even when there exist unobserved variables. We then propose a data-driven algorithm that is fast and consistent under mild assumptions. We also make use of a frequent pattern mining method to further speed up the search of minimal adjustment sets for causal effect estimation. Experiments conducted on extensive synthetic and real-world datasets demonstrate that the proposed algorithm outperforms the state-of-the-art criteria/estimators in both accuracy and time-efficiency.

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.

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.

The ultimate goal in adversarial defense is to build a universally robust defense against all types of attacks, but ongoing arms race between adversarial attacks and defenses show the difficulty in building a deterministic defense to work towards the goal. Leveraging the idea of a mixture model, in this paper, we introduce a new Randomized Adversarial Defense method (RAD) to increase the robustness against adversarial examples. RAD is designed as a simple, yet effective random mixture of a global model and one or more local models. The mixture is able to create a random decision boundary for a test instance, making it harder for an adversarial example to succeed, and thus increasing the robustness of the defense. The global model is adversarially trained to provide the baseline robustness. The local models are aimed to supplement the global model and thus the decision boundary of a local model is expected to be adjacent to the decision boundary of the global model. These models then together form a random mixture to create a randomized (non-deterministic) decision boundary for each test instance at the end. Such a randomization scheme reduces the adversarial risk since the adversary has to approximate the best attack despite of the given complete knowledge of the parameters of the individual classifiers. By proposing the notion of having a global and local models with different focuses in the mixture and the way of creating a local model which has minimum dependency on the base (global) model, RAD provides a simpler and more flexible, yet effective approach building a randomized defense, compared with the existing randomization based methods. Experimental results show that our simple randomization approach outperforms the most robust deterministic defense method and performs competitively upon the existing randomized defense method against strong adaptive attacks on CIFAR10 and CIFAR100.

In Disability Employment Service (DES), DES providers are confronted with "what-if" questions to assist workers with disability in deciding which skill should be improved to increase their job retention time. For instance, what would happen to the job retention time of a worker with disability if he improved his computer skill to an advanced level? This requires counterfactual inference to estimate the counterfactuals of the survival outcome, i.e., job retention time, under different skill improvement scenarios. While exiting survival analysis techniques are not designed for counterfactual problems, current counterfactual prediction methods are assumed to work with non-survival outcomes. In this paper, we propose the Counterfactual Survival Network (CSN), a representation learning based method for counterfactual survival prediction, where both confounding and censoring biases are removed based on latent representations. Since ground truth counterfactuals are unavailable, we develop a sample specific estimator to estimate counterfactuals for training samples. These estimated counterfactual outcomes are used as pseudo ground truth to train the counterfactual prediction model. We demonstrate the benefits of our method in decision support tasks with the case study of Australian workers and three public datasets. Results show that CSN can help Australian workers with disability increase their job retention time. Our method also shows its promising performance in other applications.

In Disability Employment Services (DES), an emerging problem is recommending to disabled workers the right skill to upgrade and the right upgrade level to achieve a maximum increase in their job retention time. This problem involves causal reasoning to estimate the individual causal effect (ICE) on the survival outcome, i.e., job retention time, to determine the most effective intervention for a worker. Existing methods are not suitable to solve our problem. They are mostly developed for non-causal or non-survival challenges, while methods for causal survival analysis are under-explored. This paper proposes a representation learning method for recommending personalized interventions that can generate a maximum increase in job retention time for workers with disability. In our method, observed covariates are disentangled into latent variables based on which confounding and censoring biases are eliminated, and the ICE prediction model is built. Since true ICE values are not directly measurable in observational data, a reverse engineering technique is developed to estimate ICE for training samples. These estimated ICE values are then used as the pseudo ground truth to train the prediction model. Experiments with a case study of Australian workers with disability show that by adopting personalized interventions recommended by our method, disabled workers can increase their job retention time by up to 2.8 months. Additional evaluations with public datasets also show the technical strengths of our method in other applications.

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.

Despite their high accuracy, deep neural networks (DNNs) are vulnerable to adversarial examples. Currently, adversarial training is the mainstream defense approach against adversarial examples. However, given the unknown nature of adversarial attacks in real life, this approach has fundamental limitations in practical use, as it is impossible to obtain sufficient adversarial examples for the training. In this paper, we propose RanTrain, a simple training approach which employs a background class with random noise images to augment the original DNN model and training data, without requiring any adversarial examples. Experiments have shown that RanTrain works effectively with different datasets and various DNN structures, and it significantly increases the robustness of DNNs to adversarial examples.

As a basic and effective tool for explanation, prediction and decision making, causal relationships have been utilized in almost all disciplines. Traditionally, causal relationships are identified by making use of interventions or randomized controlled experiments. However, conducting such experiments is often expensive or even impossible due to cost or ethical concerns. Therefore, there has been an increasing interest in discovering causal relationships based on observational data, and in the past few decades, significant contributions have been made to this field by computer scientists.

In Disability Employment Services (DES), a growing problem is recommending to disabled job seekers which skill should be upgraded and the best level for upgrading this skill to increase their employment potential most. This problem involves counterfactual reasoning to infer causal effect of factors on employment status to recommend the most effective intervention. Related methods cannot solve our problem adequately since they are developed for non-counterfactual challenges, for binary causal factors, or for randomized trials. In this paper, we present a causality-based method to tackle the problem. The method includes two stages where causal factors of employment status are first detected from data. We then combine a counterfactual reasoning framework with a machine learning approach to build an interpretable model for generating personalized recommendations. Experiments on both synthetic datasets and a real case study from a DES provider show consistent promising performance of improving employability of disabled job seekers. Results from the case study disclose effective factors and their best levels for intervention to increase employability. The most effective intervention varies among job seekers. Our model can separate job seekers by degree of employability increase. This is helpful for DES providers to allocate resources for employment assistance. Moreover, causal interpretability makes our recommendations actionable in DES business practice.

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.

In the disability employment service, an emerging challenge is to recommend the skills whose improvement will increase the employment perspective most. The process of a skill being improved is called an intervention and different skills are called factors. The problem involves recommendation for outcome improvement, which requires estimating the improvement in the employment perspective, i.e., the outcome, driven by interventions on recommended factors. Currently, most recommendation systems deployed for the employment service rely on traditional recommendation models where the desired outcome instead of the degree of outcome improvement is the main goal for optimization. In this paper, we present a causality-based approach for recommending factors for intervention to achieve the largest improvement in the employment potential of disabled job seekers. It involves inferring the causal effect of interventions on the employment outcome to make recommendations for individuals. The causal interpretation of our model can justify given recommendations. We conduct a case study with our industry partner in the disability employment service. Results show that the recommended interventions could improve the employability of disabled job seekers. Experiments are also carried out with datasets in other domains to demonstrate the promise of our approach in different applications.

Text documents are often mapped to vectors of binary values where 1 indicates the presence of a word and 0 indicates the absence. The vectors are then used to train predictive models. In tree-based ensemble models, predictions from some decision trees may be made purely from absent words. This type of predictions should be trusted less as absent words can be interpreted in multiple ways. In this work, we propose to improve the comprehensibility and accuracy of ensemble models by distinguishing word presence and absence. The presented method weights predictions based on word presence. Experimental results on 35 real text datasets indicate that our method outperforms state-of-the-art ensemble methods on various text classification tasks.

The Random Forest (RF) classifiers are suitable for dealing with the high dimensional noisy data in text classification. An RF model comprises a set of decision trees each of which is trained using random subsets of features. Given an instance, the prediction by the RF is obtained via majority voting of the predictions of all the trees in the forest. However, different test instances would have different values for the features used in the trees and the trees should contribute differently to the predictions. This diverse contribution of the trees is not considered in traditional RFs. Many approaches have been proposed to model the diverse contributions by selecting a subset of trees for each instance. This paper is among these approaches. It proposes a Semantics Aware Random Forest (SARF) classifier. SARF extracts the features used by trees to generate the predictions and selects a subset of the predictions for which the features are relevant to the predicted classes. We evaluated SARF's classification performance on $30$ real-world text datasets and assessed its competitiveness with state-of-the-art ensemble selection methods. The results demonstrate the superior performance of the proposed approach in textual information retrieval and initiate a new direction of research to utilise interpretability of classifiers.

Story timeline summarization is widely used by analysts, law enforcement agencies, and policymakers for content presentation, story-telling, and other data-driven decision-making applications. Recent advancements in web technologies have rendered social media sites such as Twitter and Facebook as a viable platform for discovering evolving stories and trending events for story timeline summarization. However, a timeline summarization structure that models complex evolving stories by tracking event evolution to identify different themes of a story and generate a coherent structure that is easy for users to understand is yet to be explored. In this paper, we propose StoryGraph, a novel graph timeline summarization structure that is capable of identifying the different themes of a story. By using high penalty metrics that leverage user network communities, temporal proximity, and the semantic context of the events, we construct coherent paths and generate structural timeline summaries to tell the story of how events evolve over time. We performed experiments on real-world datasets to show the prowess of StoryGraph. StoryGraph outperforms existing models and produces accurate timeline summarizations. As a key finding, we discover that user network communities increase coherence leading to the generation of consistent summary structures.

Entity resolution (ER) is the problem of accurately identifying multiple, differing, and possibly contradicting representations of unique real-world entities in data. It is a challenging and fundamental task in data cleansing and data integration. In this work, we propose graph differential dependencies (GDDs) as an extension of the recently developed graph entity dependencies (which are formal constraints for graph data) to enable approximate matching of values. Furthermore, we investigate a special discovery of GDDs for ER by designing an algorithm for generating a non-redundant set of GDDs in labelled data. Then, we develop an effective ER technique, Certus, that employs the learned GDDs for improving the accuracy of ER results. We perform extensive empirical evaluation of our proposals on five real-world ER benchmark datasets and a proprietary database to test their effectiveness and efficiency. The results from the experiments show the discovery algorithm and Certus are efficient; and more importantly, GDDs significantly improve the precision of ER without considerable trade-off of recall.

Introduction to the Special Section on Advances in Causal Discovery and InferenceIdentification of cause and effect is the ultimate goal for most scientific and social discoveries.Controlled experiments are an effective approach to such discoveries, but they are expensive and sometimes infeasible to conduct.With the advent of big data availability in many areas, finding causal relationships using automated procedures is increasingly possible.With its focus on this challenge, causal discovery and inference is now a fast growing area in machine learning.Graphical causal models, the potential outcome model, and structural equation models are the three major modelling approaches to representation of causal relations and identification of causal effects.They have achieved many successes in various applications.More importantly, the principles and insights of causal inference help to solve several challenging machine-learning problems, such as model explainability, transfer learning, domain adaptation, and lifelong learning [1].However, causal discovery and inference faces many challenges in theory and practice.They need strong assumptions, some of which are not verifiable in data.There is a lack of ground truth data for real-world evaluation of causal discovery and inference methods.Some of the algorithms whose results have asymptotic theoretical guarantees are not scalable to large and/or highdimensional data.More research is still needed to solve fundamental problems in causal discovery and inference, such as structure learning, false discovery control, assessment of causal discoveries, hidden variables, and nonlinear and/or heterogeneous causal relationships.More real-world applications of causal discovery and inference are also vital.Many workshops and symposia have been organized to meet the increasing research interests and demands in causal discovery and inference.Some associate editors of this special issue have organized four KDD Causal Discovery workshops, from 2016 to 2019.More than 10 other workshops and symposia have been organized in the same period, such as NeurIPS Workshop From "What If?" To "What Next?": Causal Inference and Machine Learning for Intelligent Decision Making in 2017; NeurIPS Workshop Machine Learning and Causal Inference for Improved Decision Making in 2019; UAI Workshop Causation: Foundation to Application, 2016; UAI Workshop Causality: Learning, Inference, and Decision-Making, 2017; and UAI Workshop on Causal Inference, 2018.We edit this special issue to showcase the research achievements in the past few years since the previous special issue on the same topic in 2016 was published in this journal.This special issue collects seven articles that fall into two groups: fundamental problems and applications.The five articles in the first group study the fundamental problems in causal discovery and inference and present novel solutions for false discovery control in structure learning, causal relationship detection in simulation models, causal structure search in the presence of latent confounders, the shortest causal path discovery by local search, and conditional independence test for causal structure learning.Discovering causal relationships from observational data is a fundamental problem.Little research work has studied the strategies for controlling false discovery rates in causal structure learning.The article "Estimating and controlling the false discovery rate of the PC algorithm using edge-specific p-values," by E. Strobl, P. Spirtes, and S. Visweswaran, presents an extension

Outliers are objects that are significantly different from the others in the same dataset. They often contain insightful information for understanding the data and the data generation process. Traditional outlier detection methods can generally be divided into two categories: model-based and proximity-based approaches. A new type of model-based approach has recently been proposed to use the Bayesian network (BN) framework to discover more meaningful outliers with better interpretability. They yield very good detection result when anomalousness is mainly due to the violation of the dependency among variables. However, when anomalousness is caused by reasons other than dependency violation, BN-based methods produce very poor performance. To address this problem, we propose an ensemble outlier detection method that combines BN-based and proximity-based techniques to achieve more stable outlier detection results in different scenarios. To our best knowledge, the proposed method is the first to bring together the two major categories of outlier detection techniques. Comprehensive experiments have been done on both synthetic and real world datasets, and the results show that our method outperforms the baseline methods in most cases.

With more and more decisions being made by learnt algorithms from data, algorithmic discriminations have become a risk for civil rights. The detection of discrimination is a process of counterfactual reasoning. This paper proposes a general detection framework by combining a data mining method with a well established counterfactual reasoning framework, potential outcome model. The potential outcome model supports operational definitions of global and local discriminations and discriminations by combined factors, while a data mining method makes the detection efficient. The proposed method, instantiated by association rule mining with potential outcome model based causal effect estimation, is evaluated with four real world data sets and is compared with a Bayesian network (BN) based detection method. It is able to detect not only global discriminations that are detected by the BN based method, but also local and combined discriminations that the BN based method cannot find. The proposed method is efficient, and scales well with the data set size and the number of attributes.

Uncovering causal relationships in data is a major objective of data analytics. Currently, there is a need for scalable and automated methods for causal relationship exploration in data. Classification methods are fast and they could be practical substitutes for finding causal signals in data. However, classification methods are not designed for causal discovery and a classification method may find false causal signals and miss the true ones. In this paper, we develop a causal decision tree (CDT) where nodes have causal interpretations. Our method follows a well-established causal inference framework and makes use of a classic statistical test to establish the causal relationship between a predictor variable and the outcome variable. At the same time, by taking the advantages of normal decision trees, a CDT provides a compact graphical representation of the causal relationships, and the construction of a CDT is fast as a result of the divide and conquer strategy employed, making CDTs practical for representing and finding causal signals in large data sets. Experiment results demonstrate that CDTs can identify meaningful causal relationships and the CDT algorithm is scalable.

Randomised controlled trials (RCTs) are the most effective approach to causal discovery, but in many circumstances it is impossible to conduct RCTs. Therefore, observational studies based on passively observed data are widely accepted as an alternative to RCTs. However, in observational studies, prior knowledge is required to generate the hypotheses about the cause-effect relationships to be tested, and hence they can only be applied to problems with available domain knowledge and a handful of variables. In practice, many datasets are of high dimensionality, which leaves observational studies out of the opportunities for causal discovery from such a wealth of data sources. In another direction, many efficient data mining methods have been developed to identify associations among variables in large datasets. The problem is that causal relationships imply associations, but the reverse is not always true. However, we can see the synergy between the two paradigms here. Specifically, association rule mining can be used to deal with the high-dimensionality problem, whereas observational studies can be utilised to eliminate noncausal associations. In this article, we propose the concept of causal rules (CRs) and develop an algorithm for mining CRs in large datasets. We use the idea of retrospective cohort studies to detect CRs based on the results of association rule mining. Experiments with both synthetic and real-world datasets have demonstrated the effectiveness and efficiency of CR mining. In comparison with the commonly used causal discovery methods, the proposed approach generally is faster and has better or competitive performance in finding correct or sensible causes. It is also capable of finding a cause consisting of multiple variables—a feature that other causal discovery methods do not possess.

editorial Free Access Share on Preface to the ACM TIST Special Issue on Causal Discovery and Inference Authors: Kun Zhang Max-Planck Institute for Intelligent Systems, Germany Max-Planck Institute for Intelligent Systems, GermanyView Profile , Jiuyong Li University of South Australia, Australia University of South Australia, AustraliaView Profile , Elias Bareinboim University of California, Los Angeles, CA University of California, Los Angeles, CAView Profile , Bernhard Schölkopf Max-Planck Institute for Intelligent Systems, Germany Max-Planck Institute for Intelligent Systems, GermanyView Profile , Judea Pearl University of California, Los Angeles, CA University of California, Los Angeles, CAView Profile Authors Info & Claims ACM Transactions on Intelligent Systems and TechnologyVolume 7Issue 2January 2016 Article No.: 17pp 1–3https://doi.org/10.1145/2840720Published:09 January 2016Publication History 4citation265DownloadsMetricsTotal Citations4Total Downloads265Last 12 Months26Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The study of urban networks reveals that the accessibility of important city objects for the vehicle traffic and pedestrians is significantly correlated to the popularity, micro-criminality, micro-economic vitality, and social liveability of the city, and is always the chief factor in regulating the growth and expansion of the city. The accessibility between different components of an urban structure are frequently measured along the streets and routes considered as edges of a planar graph, while the traffic ultimate destination points and street junctions are treated as vertices. For estimation of the accessibility of destination vertex$j$from vertex$i$through urban networks, in particular, the random walks are used to calculate the expected distance a random walker starting from$i$makes before$j$is visited (known asaccess time). The state-of-the-art of access time computation is costly in large planar graphs since it involves matrix operation over entire graph. The time complexity is$O(n^{2.376})$where$n$is the number of vertices in the planar graph. To enable efficient access time query answering in large planar graphs, this work proposes the first access time oracle which is based on the proposed access time decomposition and reconstruction scheme. The oracle is a hierarchical data structure with deliberate design on the relationships between different hierarchical levels. The storage requirement of the proposed oracle is$O(n^{\frac{4}{3}}\log \log n)$and the access time query response time is$O(n^{\frac{2}{3}})$. The extensive tests on a number of large real-world road networks (with up to about 2 million vertices) have verified the superiority of the proposed oracle.

Discovering causal relationships in large databases of observational data is challenging. The pioneering work in this area was rooted in the theory of Bayesian network (BN) learning, which however, is a NP-complete problem. Hence several constraint-based algorithms have been developed to efficiently discover causations in large databases. These methods usually use the idea of BN learning, directly or indirectly, and are focused on causal relationships with single cause variables. In this paper, we propose an approach to mine causal rules in large databases of binary variables. Our method expands the scope of causality discovery to causal relationships with multiple cause variables, and we utilise partial association tests to exclude noncausal associations, to ensure the high reliability of discovered causal rules. Furthermore an efficient algorithm is designed for the tests in large databases. We assess the method with a set of real-world diagnostic data. The results show that our method can effectively discover interesting causal rules in large databases.

Functional and inclusion dependency discovery is important to knowledge discovery, database semantics analysis, database design, and data quality assessment. Motivated by the importance of dependency discovery, this paper reviews the methods for functional dependency, conditional functional dependency, approximate functional dependency, and inclusion dependency discovery in relational databases and a method for discovering XML functional dependencies.

Data anonymization has become a major technique in privacy preserving data publishing. Many methods have been proposed to anonymize one dataset and a series of datasets of a data owner. However, no method has been proposed for the anonymization of data of multiple independent data publications. A data owner publishes a dataset, which contains overlapping population with other datasets published by other independent data owners. In this paper we analyze the privacy risk in the such scenario and vulnerability of partitioned based anonymization methods. We show that no partitioned based anonymization methods can protect privacy in arbitrary data distributions, and identify a case that the privacy can be protected in the scenario. We propose a new generalization principle ε-cloning to protect privacy for multiple independent data publications. We also develop an effective algorithm to achieve the ε-cloning. We experimentally show that the proposed algorithm anonymizes data to satisfy the privacy requirement and preserves good data utility.

Ordinal regression has wide applications in many domains where the human evaluation plays a major role. Most current ordinal regression methods are based on Support Vector Machines (SVM) and suffer from the problems of ignoring the global information of the data and the high computational complexity. Linear Discriminant Analysis (LDA) and its kernel version, Kernel Discriminant Analysis (KDA), take into consideration the global information of the data together with the distribution of the classes for classification, but they have not been utilized for ordinal regression yet. In this paper, we propose a novel regression method by extending the Kernel Discriminant Learning using a rank constraint. The proposed algorithm is very efficient since the computational complexity is significantly lower than other ordinal regression methods. We demonstrate experimentally that the proposed method is capable of preserving the rank of data classes in a projected data space. In comparison to other benchmark ordinal regression methods, the proposed method is competitive in accuracy.

Most existing works of data anonymisation target at the optimization of the anonymisation metrics to balance the data utility and privacy, whereas they ignore the effects of a requester's trust level and application purposes during the data anonymisation. Our aim of this paper is to propose a much finer level anonymisation scheme with regard to the data requester's trust value and specific application purpose. We prioritize the attributes for anonymisation based on how important and critical they are related to the specified application purposes and propose a trust evaluation strategy to quantify the data requester's reliability, and further build the projection between the trust value and the degree of data anonymiztion, which intends to determine to what extent the data should be anonymized. The decomposition algorithm is developed to find the desired anonymous solution, which guarantees the uniqueness and correctness.

Previous works about privacy preserving serial data publishing on dynamic databases have relied on unrealistic assumptions of the nature of dynamic databases. In many applications, some sensitive values changes freely while others never change. For example, in medical applications, the disease attribute changes with time when patients recover from one disease and develop another disease. However, patients do not recover from some diseases such as HIV. We call such diseases permanent sensitive values. To the best of our knowledge, none of the existing solutions handle these realistic issues. We propose a novel anonymization approach called HD-composition to solve the above problems. Extensive experiments with real data confirm our theoretical results.

Individual privacy will be at risk if a published data set is not properly deidentified. k-anonymity is a major technique to de-identify a data set. Among a number of k-anonymization schemes, local recoding methods are promising for minimizing the distortion of a k-anonymity view. This paper addresses two major issues in local recoding k-anonymization in attribute hierarchical taxonomies. First, we define a proper distance metric to achieve local recoding generalization with small distortion. Second, we propose a means to control the inconsistency of attribute domains in a generalized view by local recoding. We show experimentally that our proposed local recoding method based on the proposed distance metric produces higher quality k-anonymity tables in three quality measures than a global recoding anonymization method, Incognito, and a multidimensional recoding anonymization method, Multi. The proposed inconsistency handling method is able to balance distortion and consistency of a generalized view.

Individual privacy will be at risk if a published data set is not properly de-identified. k -anonymity is a major technique to de-identify a data set. A more general view of k -anonymity is clustering with a constraint of the minimum number of objects in every cluster. Most existing approaches to achieving k -anonymity by clustering are for numerical (or ordinal) attributes. In this paper, we study achieving k -anonymity by clustering in attribute hierarchical structures. We define generalisation distances between tuples to characterise distortions by generalisations and discuss the properties of the distances. We conclude that the generalisation distance is a metric distance. We propose an efficient clustering-based algorithm for k -anonymisation. We experimentally show that the proposed method is more scalable and causes significantly less distortions than an optimal global recoding k -anonymity method. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)-anonymity problem is NP-hard. We first presentan optimal global-recoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general case.

In machine learning and data mining, heuristic and association rules are two dominant schemes for rule discovery. Heuristic rule discovery usually produces a small set of accurate rules, but fails to find many globally optimal rules. Association rule discovery generates all rules satisfying some constraints, but yields too many rules and is infeasible when the minimum support is small. Here, we present a unified framework for the discovery of a family of optimal rule sets and characterize the relationships with other rule-discovery schemes such as nonredundant association rule discovery. We theoretically and empirically show that optimal rule discovery is significantly more efficient than association rule discovery independent of data structure and implementation. Optimal rule discovery is an efficient alternative to association rule discovery, especially when the minimum support is low.

This paper studies a problem of robust rule-based classification, i.e., making predictions in the presence of missing values in data. This study differs from other missing value handling research in that it does not handle missing values but builds a rule-based classification model to tolerate missing values. Based on a commonly used rule-based classification model, we characterize the robustness of a hierarchy of rule sets as k-optimal rule sets with the decreasing size corresponding to the decreasing robustness. We build classifiers based on k-optimal rule sets and show experimentally that they are more robust than some benchmark rule-based classifiers, such as C4.5rules and CBA. We also show that the proposed approach is better than two well-known missing value handling methods for missing values in test data.

In this paper, we discuss a problem of finding risk patterns in medical data. We define risk patterns by a statistical metric, relative risk, which has been widely used in epidemiological research. We characterise the problem of mining risk patterns as an optimal rule discovery problem. We study an anti-monotone property for mining optimal risk pattern sets and present an algorithm to make use of the property in risk pattern discovery. The method has been applied to a real world data set to find patterns associated with an allergic event for ACE inhibitors. The algorithm has generated some useful results for medical researchers.

An association rule generation algorithm usually generates too many rules including a lot of uninteresting ones. Many interestingness criteria are proposed to prune those uninteresting rules. However, they work in post-pruning process and hence do not improve the rule generation efficiency. We discuss properties of informative rule set and conclude that the informative rule set includes all interesting rules measured by many commonly used interestingness criteria, and that rules excluded by the informative rule set are forwardly prunable, i.e. they can be removed in the rule generation process instead of post pruning. Based on these properties, we propose a direct interesting rule generation algorithm, DIG, to directly generate interesting rules defined by any of 12 interestingness criteria. We further show experimentally that DIG is faster and uses less memory than Apriori.

We study the problem of computing classification rule sets from relational databases so that accurate predictions can be made on test data with missing attribute values. Traditional classifiers perform badly when test data are not as complete as the training data because they tailor a training database too much. We introduce the concept of one rule set being more robust than another, that is, able to make more accurate predictions on test data with missing attribute values. We show that the optimal class association rule set is as robust as the complete class association rule set. We then introduce the k-optimal rule set, which provides predictions exactly the same as the optimal class association rule set on test data with up to k missing attribute values. This leads to a hierarchy of k-optimal rule sets in which decreasing size corresponds to decreasing robustness, and they all more robust than a traditional classification rule set. We introduce two methods to find k-optimal rule sets, i.e. an optimal association rule mining approach and a heuristic approximate approach. We show experimentally that a k-optimal rule set generated by the optimal association rule mining approach performs better than that by the heuristic approximate approach and both rule sets perform significantly better than a typical classification rule set (C4.5Rules) on incomplete test data.

Mining transaction databases for association rules usually generates a large number of rules, most of which are unnecessary when used for subsequent prediction. In this paper we define a rule set for a given transaction database that is much smaller than the association rule set but makes the same predictions as the association rule set by the confidence priority. We call this subset the informative rule set. The informative rule set is not constrained to particular target items; and it is smaller than the non-redundant association rule set. We present an algorithm to directly generate the informative rule set, i.e., without generating all frequent itemsets first, and that accesses the database less often than other unconstrained direct methods. We show experimentally that the informative rule set is much smaller than both the association rule set and the non-redundant association rule set, and that it can be generated more efficiently.