Advances in Knowledge Discovery and Data Mining

Due to the intricate dynamics of multivariate time series in cyber-physical system, unsupervised anomaly detection has always been a research hotspot. Common methods are mainly based on reducing reconstruction error or maximizing estimated probability for normal data, however, both of them may be sensitive to particular fluctuations in data. Meanwhile, these methods tend to model temporal dependency or spatial correlation individually, which is insufficient to detect diverse anomalies. In this paper, we propose an error-restricted framework with variance estimation, namely Spatial-Temporal Anomaly Transformer (S-TAR), which can provide a corresponding confidence for each reconstruction. First, it presents Error-Restricted Probability (ERP) loss by restricting the reconstruction error and its estimated probability skillfully, further improving the capability to distinguish outliers from normal data. Second, we adopt Spatial-Temporal Transformer with distinct attention modules to detect diverse anomalies. Extensive experiments on five real-world datasets are conducted, the results show that our method is superior to existing state-of-the-art approaches.

Anomaly detection on attributed networks is a vital task in graph data mining and has been widely applied in many real-world scenarios. Despite the promising performance, existing contrastive learning-based anomaly detection models still suffer from a limitation: the lack of fine-grained contrastive tasks tailored for different anomaly types, which hinders their capability to capture diverse anomaly patterns effectively. To address this issue, we propose a novel multi-task contrastive learning framework that jointly optimizes two well-designed contrastive tasks: context matching and link prediction. The context matching task identifies contextual anomalies by measuring the congruence of the target node with its local context. The link prediction task fully exploits self-supervised information from the network structure and identifies structural anomalies by assessing the rationality of the local structure surrounding target nodes. By integrating these two complementary tasks, our framework can more precisely identify anomalies. Extensive experiments on four benchmark datasets demonstrate that our method achieves considerable improvement compared to state-of-the-art baselines.

Video Anomaly Detection (VAD) is a significant task, which refers to taking a video clip as input and outputting class labels, e.g., normal or abnormal, at the frame level. Wang et al. proposed a method called DSTJiP, which trains the model by solving Decoupled Spatial and Temporal Jigsaw Puzzles and achieves impressive VAD performance. However, the model sometimes fails to detect abnormal human actions where abnormal motions are accompanied by normal motions. The reason is that the model learns representations of little- and non-motion parts of training examples, resulting in being insensitive to abnormal motions. To circumvent this problem, we propose to solve Spatial and Augmented Temporal Jigsaw Puzzles (SATJiP) as an extension of DSTJiP. SATJiP encourages the model to focus on motions by a novel pretext task, enabling it to detect abnormal motions accompanied by normal motions. Experiments conducted on three standard VAD benchmarks demonstrate that SATJiP outperforms the state-of-the-art methods.

In rapidly evolving industrial IT systems, the integration of sensor networks has become the cornerstone of operational workflows. These networks diligently collect data in the form of time series, where the format intertwines closely with temporal dependencies, crucial for anomaly detection models. Hence, the extraction of information in the time domain is advantageous for anomaly detection. To address this, we adopt a method of time series decomposition to delve into seasonality, trend, and residual components. Additionally, we design a novel algorithm that combines Transformer architecture with convolutional layers, focusing on subtle local dependencies within time series data. Extensive validation on three different real-world datasets highlights the robustness of our approach, demonstrating its proficiency in anomaly detection in time series materials. This underscores the advantage of combining convolutional strategies with Transformer architecture in capturing complex patterns and anomalies.

We present TOPOMA, a time-series orthogonal projection operator with moving average that can identify anomalous points for multivariate time-series, without requiring any labels nor training. Despite intensive research the problem has received, it remains challenging due to 1) scarcity of labels, 2) occurrence of non-stationarity in online streaming, and 3) trust issues posed by the black-box nature of deep learning models. We tackle these issues by avoiding training a complex model on historical data as in previous work, rather we track a moving average estimate of variable subspaces that can compute the deviation of each time step via orthogonal projection onto the subspace. Further, we propose to replace the popular yet less principled global thresholding function of anomaly scores used in previous work with an adaptive one that can bound the occurrence of anomalous events to a given small probability. Our algorithm is shown to compare favourably with deep learning methods while being transparent to interpret.

Unsupervised learning-based anomaly detection using autoencoders has gained importance since anomalies behave differently than normal data when reconstructed from a well-regularized latent space. Existing research shows that retaining valuable properties of input data in latent space helps in the better reconstruction of unseen data. Moreover, real-world sensor data is skewed and non-Gaussian in nature rendering mean-based estimators unreliable for such cases. Reconstruction-based anomaly detection methods rely on Euclidean distance as the reconstruction error which does not consider useful correlation information in the latent space. In this work, we address some of the limitations of the Euclidean distance when used as a reconstruction error to detect anomalies (especially near anomalies) that have a similar distribution as the normal data in the feature space. We propose a latent dimension regularized autoencoder that leverages a robust form of the Mahalanobis distance (MD) to measure the latent space correlation to effectively detect near as well as far anomalies. We showcase that incorporating the correlation information in the form of robust MD in the latent space is quite helpful in separating both near and far anomalies in the reconstructed space.

There have been multiple attempts to tackle the problem of identifying abnormal instances that have inconsistent behaviors in multi-view data (i.e., multi-view anomalies) but the problem still remains a challenge. In this paper, we propose an unsupervised approach with probabilistic latent variable models to detect multi-view anomalies in multi-view data. In our proposed model, we assume that views of an instance are generated from a shared latent variable that uniformly represents that instance. Since the latent variable is shared across views, an abnormal instance that exhibits inconsistencies across different views would have a lower likelihood. This is because, using a single latent variable, the model could not explain well all views that are inconsistent. Therefore, the likelihood of instances based on the proposed shared latent variable model can be used to detect multi-view anomalies. We derive a variational inference algorithm for learning the model parameters that scales well to large datasets. We compare our proposed method with several state-of-the-art methods for multi-view anomaly detection on several datasets. The results show that our method outperforms the existing methods in detecting multi-view anomalies.

In this paper, we propose QWalkVec, a quantum walk-based node embedding method. A quantum walk is a quantum version of a random walk that demonstrates a faster propagation than a random walk on a graph. We focus on the fact that the effect of the depth-first search process is dominant when a quantum walk with a superposition state is applied to graphs. Simply using a quantum walk with its superposition state leads to insufficient performance since balancing the depth-first and breadth-first search processes is essential in node classification tasks. To overcome this disadvantage, we formulate novel coin operators that determine the movement of a quantum walker to its neighboring nodes. They enable QWalkVec to integrate the depth-first search and breadth-first search processes by prioritizing node sampling. We evaluate the effectiveness of QWalkVec in node classification tasks conducted on four small-sized real datasets. As a result, we demonstrate that the performance of QWalkVec is superior to that of the existing methods on several datasets. Our code will be available at https://​github.​com/​ReiSato18/​QWalkVec.

Graph representation learning methods have significantly transformed applications in various domains. However, their success often comes at the cost of interpretability, hindering them from being adopted in critical decision-making scenarios. In conventional graph classification, the integration of domain expertise to enhance model training has been underutilized, leading to discrepancies in decision outcomes between humans and models. To address this, we introduce a novel framework involving active human verification in graph classification processes. Our approach features a human-aligned representation learning component, achieved by seamlessly integrating Graph Neural Network architectures and leveraging human domain knowledge and feedback. This framework enhances model transparency and interpretability and fosters collaborative decision-making between humans and AI systems. Extensive evaluations and user studies prove the efficiency of our framework.

Deep Neural Networks have shown vulnerability to sparse adversarial attack, which involves perturbing only a limited number of pixels. Identifying the coordinates requiring perturbation in sparse attacks poses a significant computational challenge. Existing solutions predominantly rely on heuristic methods or relax the \(\ell _{0}\)-norm to the \(\ell _{1}\)-norm. In this paper, we present an efficient algorithm for conducting sparse attacks. Our algorithm factorizes the perturbation at each pixel to the product of the perturbation coordinates and the perturbation magnitudes and then optimizes them alternately. We reformulate the \(\ell _{0}\)-norm as a stochastic binary optimization problem, assuming that each pixel’s perturbation status is associated with a stochastic binary variable. This stochastic binary variable follows a Bernoulli distribution, with a parameter value that ranges from 0 to 1, signifying the probability of pixel disturbance. To tackle this stochastic binary optimization challenge, we employ an unbiased gradient estimator known as Augment-Reinforce-Merge (ARM). Once the perturbed coordinates are determined, we optimize the perturbation magnitudes with gradient descent. Furthermore, we incorporate a binary search algorithm to eliminate redundant pixels to enhance sparsity. Comprehensive experiments demonstrate the superiority of our proposed method over several state-of-the-art sparse attack methods.

Malevolent Dialogue Response Detection has gained much attention from the NLP community recently. Existing methods have difficulties in effectively utilizing the conversational context and the malevolent information. In this work, we propose a novel framework, the Label Enhanced Multi-task learning (LEMT), which incorporates a structured representation of malevolence description information and exploits malevolence shift detection as an auxiliary task. Specifically, we introduce a hierarchical structure encoder based on prior probability knowledge to capture the semantic information of different malevolent types and integrate it with utterance information. In addition, the malevolence shift detection is modeled to improve the ability of the model to distinguish between different malevolent information. Experimental results show that our LEMT outperforms state-of-the-art methods and verifies the effectiveness of the modules.

Recently, multi-head Graph Attention Networks (GATs) have incorporated attention mechanisms to generate more enriched feature embeddings, demonstrating significant potential in Knowledge Graph Completion (KGC) tasks. However, existing GATs based KGC approaches struggle to update entities with few neighbors, making it challenging to obtain structured semantic information and overlooking complex and implicit information in distant triples. To this effect, we propose a novel model named the Two-Stage KGC model with integrated High-Order Structural Features (HOSAT), designed to enhance the learning process of GATs. Initially, we leverage the conventional GATs module to acquire embeddings encapsulating local semantic intricacies. Subsequently, we introduce a global biased random walk algorithm, strategically amalgamating graph topology, entity attributes, and relationship attributes. This algorithm aims to extract high-order structured semantic neighbor sequences from multiple perspectives and construct nuanced reasoning paths. By propagating the embedding along this path, it is ensured that with an increasing number of iterations, the aggregated information of each node becomes an almost perfect combination of local and global features. Evaluation on two public benchmark datasets using entity prediction methods demonstrates that HOSAT achieves substantial performance improvements over state-of-the-art methods.

Multi-label recognition with limited annotations has been gaining attention recently due to the costs of thorough dataset annotation. Despite significant progress, current methods for simulating partial labels utilize a strategy that uniformly omits labels, which inadequately prepares models for real-world inconsistencies and undermines their generalization performance. In this paper, we consider a more realistic partial label setting that correlates label absence with an instance’s ambiguity, and propose the novel Ambiguity-Aware Instance Weighting (AAIW) to specifically address the performance decline caused by such ambiguous instances. This strategy dynamically modulates instance weights to prioritize learning from less ambiguous instances initially, then gradually increasing the weight of complex examples without the need for predetermined sequencing of data. This adaptive weighting not only facilitates a more natural learning progression but also enhances the model’s ability to generalize from increasingly complex patterns. Experiments on standard multi-label recognition benchmarks demonstrate the advantages of our approach over state-of-the-art methods.

Node classification is a pivotal task in spam detection, community identification, and social network analysis. Compared with traditional graph learning methods, Graph Neural Networks (GNN) show superior performance in prediction tasks, but essentially rely on the characteristics of adjacent nodes. This paper proposed a novel Chaotic Neural Oscillator Feature Selection Graph Neural Network (CNO_FSGNN) model integrating Lee Oscillator which serves as a chaotic memory association to enhance the processing of transient information and transitions between distinct behavioral patterns and synchronization of relevant networks, and a Feature Selection Graph Neural Network to address the limitations. Consequently, the synthesis can improve mean classification accuracy across six homogeneous and heterogeneous datasets notably in Squirrel dataset, and can mitigate over-smoothing concerns in deep layers reducing model execution time.

Fairness is increasingly becoming an important issue in machine learning. Representation learning is a popular approach recently that aims at mitigating discrimination by generating representation on the historical data so that further predictive analysis conducted on the representation is fair. Inspired by this approach, we propose a novel structure, called GIFair, for generating a representation that can simultaneously reconcile utility with both group and individual fairness, compared with most relevant studies that only focus on group fairness. Due to the conflict of the two fairness targets, we need to trade group fairness off against individual fairness in addition to considering the utility of classifiers. To achieve an optimized trade-off performance, we include a focal loss function so that all the targets can receive more balanced attention. Experiments conducted on three real datasets show that GIFair can achieve a better utility-fairness trade-off compared with existing models.

Record linkage is the process of identifying and matching records from different datasets that refer to the same entity. This process can be framed as a pairwise binary classification problem, where a classification model predicts if a pair of records match (i.e., refer to the same entity) or not. Even though training data is paramount in model building and the subsequent predictions, there is a lack of reporting in the literature on training data details, especially the ratio of matching to non-matching examples. The absence of adequate reporting has a significant impact on both the model building and reproducibility of research studies. In this paper we demonstrate how the performance measures commonly used in record linkage (precision, recall, and \(F_1\)-measure) vary with respect to this ratio. Specifically, we show that different class imbalance ratios in training data have a substantial impact in classifier performance, with more imbalanced training data resulting in lower performance. Furthermore, we examine the impact on performance when the class ratio between the test data and the training data is changed. Our extensive experimental study allows us to offer practical advice for constructing training data, building record linkage models, measuring performance, and reporting on the training data details.

Clustering as one of the main research methods in data mining, with the generation of multi-view data, multi-view clustering has become the research hotspot at present. Many excellent multi-view clustering algorithms have been proposed to solve various practical problems. These algorithms mainly achieve multi-view feature fusion by maximizing the consistency between views. However, in practical applications, multi-view data’ initial feature is often imbalanced, resulting in poor performance of existing multi-view clustering algorithms. Additionally, imbalanced multi-view data exhibits significant differences in feature across different views, which better reflects the complementarity of multi-view data. Therefore, it is important to fully extract feature from different views of imbalanced multi-view data. This paper proposes an imbalanced multi-view clustering algorithm based on common specific feature learning, ImMC-CSFL. Two deep networks are used to extract common and specific feature on each view, the GAN network is introduced to maximize the extraction of common feature from multi-view data, and orthogonal constraints are used to maximize the extraction of specific feature from different views. Finally, the learned imbalanced multi-view feature is input for clustering. The experiment result on three different multi-view datasets UCI Digits, BDGP, and CCV showed that our proposed algorithm had better clustering performance, and the effectiveness and robustness were verified through experiment analysis of different modules.

This paper introduces the multivariate beta mixture model (MBMM), a new probabilistic model for soft clustering. MBMM adapts to diverse cluster shapes because of the flexible probability density function of the multivariate beta distribution. We introduce the properties of MBMM, describe the parameter learning procedure, and present the experimental results, showing that MBMM fits diverse cluster shapes on synthetic and real datasets. The code is released anonymously at https://​github.​com/​hhchen1105/​mbmm/​.

AutoML has witnessed effective applications in the field of supervised learning – mainly in classification tasks – where the goal is to find the best machine-learning pipeline when a ground truth is available. This is not the case for unsupervised tasks that are by nature exploratory and they are performed to unveil hidden insights. Since there is no right result, analyzing different configurations is more important than returning the best-performing one. When it comes to exploratory unsupervised tasks – such as cluster analysis – different facets of the datasets could be interesting for the data scientist; for instance, data items can be effectively grouped together in different subspaces of features. In this paper, AutoClues explores and returns a dashboard of both relevant and diverse clusterings via AutoML and diversification. AutoML ensures that the explored pipelines for cluster analysis (including pre-processing steps) compute good clusterings. Then, diversification selects, out of the explored clusterings, the ones conveying different clues to the data scientists.

Analyzing the properties of subsequences within time series can reveal hidden patterns and improve the quality of time series clustering. However, most existing methods for subsequence analysis require point-to-point alignment, which is sensitive to shifts and noise. In this paper, we propose a clustering method named CTDS that treats time series as a set of independent and identically distributed (iid) points in \(\mathbb {R}^d\) extracted by a sliding window in local regions. CTDS utilises a distributional measure called Isolation Distributional Kernel (IDK) that can capture the subtle differences between probability distributions of subsequences without alignment. It has the ability to cluster large non-stationary and complex datasets. We evaluate CTDS on UCR time series benchmark datasets and demonstrate its superior performance than other state-of-the-art clustering methods.

In this paper, we introduce a novel Distributed Markov Chain Monte Carlo (MCMC) inference method for the Bayesian Non-Parametric Latent Block Model (DisNPLBM), employing the Master/Worker architecture. Our non-parametric co-clustering algorithm divides observations and features into partitions using latent multivariate Gaussian block distributions. The workload on rows is evenly distributed among workers, who exclusively communicate with the master and not among themselves. DisNPLBM demonstrates its impact on cluster labeling accuracy and execution times through experimental results. Moreover, we present a real-use case applying our approach to co-cluster gene expression data. The code source is publicly available at https://​github.​com/​redakhoufache/​Distributed-NPLBM

Conventional fair graph clustering methods face two primary challenges: i) They prioritize balanced clusters at the expense of cluster cohesion by imposing rigid constraints, ii) Existing methods of both individual and group-level fairness in graph partitioning mostly rely on eigen decompositions and thus, generally lack interpretability. To address these issues, we propose \(iFairNMTF \), an individual Fairness Nonnegative Matrix Tri-Factorization model with contrastive fairness regularization that achieves balanced and cohesive clusters. By introducing fairness regularization, our model allows for customizable accuracy-fairness trade-offs, thereby enhancing user autonomy without compromising the interpretability provided by nonnegative matrix tri-factorization. Experimental evaluations on real and synthetic datasets demonstrate the superior flexibility of iFairNMTF in achieving fairness and clustering performance.

Given a large graph with few node labels, how can we (a) identify whether there is generalized network-effects  (GNE) or not, (b) estimate GNE to explain the interrelations among node classes, and (c) exploit GNE efficiently to improve the performance on downstream tasks? The knowledge of GNE is valuable for various tasks like node classification and targeted advertising. However, identifying GNE such as homophily, heterophily or their combination is challenging in real-world graphs due to limited availability of node labels and noisy edges. We propose NetEffect, a graph mining approach to address the above issues, enjoying the following properties: (i) Principled: a statistical test to determine the presence of GNE in a graph with few node labels; (ii) General and Explainable: a closed-form solution to estimate the specific type of GNE observed; and (iii) Accurate and Scalable: the integration of GNE for accurate and fast node classification. Applied on real-world graphs, NetEffect discovers the unexpected absence of GNE in numerous graphs, which were recognized to exhibit heterophily. Further, we show that incorporating GNE is effective on node classification. On a million-scale real-world graph, NetEffect achieves over 7\(\mathbf {\times }\) speedup (14 minutes vs. 2 hours) compared to most competitors.

Discovering relevant patterns for a particular user remains a challenging data mining task. One way to deal with this difficulty is to use interestingness measures to create a ranking. Although these measures allow evaluating patterns from various sights, they may generate different rankings and hence highlight different understandings of what a good pattern is. This paper investigates the potential of learning-to-rank techniques to learn to rank directly. We use the Choquet integral, which belongs to the family of non-linear aggregators, to learn an aggregation function from the user’s feedback. We show the interest of our approach on association rules, whose added-value is studied on UCI datasets and a case study related to the analysis of gene expression data.

Detecting anomalies in real-world multivariate time series data is challenging due to the deviation between the distributions of normal and anomalous data. Previous studies focused on capturing time and spatial features but lacked an effective criterion to measure differentiation from normal data. Our proposed method utilizes saliency detection, similar to anomaly detection, to identify the most significant region and effectively detect abnormal data. In this work, We propose a novel framework, Saliency-aware Anomaly Detection (SalAD), for detecting anomalies in multivariate time series data. SalAD comprises three main components: 1) a saliency detection module to remove redundant data, 2) an unsupervised saliency-aware forecasting model, and 3) a saliency-aware anomaly score to differentiate anomalies. We evaluate our model using the real-world Korea Aerospace Research Institute (KARI) orbital element dataset, which includes six orbital elements and unexpected disturbances from satellites, as well as conducting extensive experiments on four benchmark datasets to demonstrate its effectiveness and superiority over other baselines. The SalAD framework has been deployed on the K3A and K5 satellites.

Given a retail transactional database, the objective of high-utility pattern mining is to discover high-utility itemsets (HUIs), i.e., itemsets that satisfy a user-specified utility threshold. In retail applications, when purchasing a set of items (i.e., itemsets), consumers seek to replace or substitute items with each other to suit their individual preferences (e.g., Coke with Pepsi, tea with coffee). In practice, retailers, too, require substitutes to address operational issues like stockouts, expiration, and other supply chain constraints. The implication is that items that are interchangeably purchased, i.e., substitute goods, are critical to ensuring both user satisfaction and sustained retailer profits. In this regard, this work presents (i) an efficient model to identify HUIs containing substitute goods in place of items that require substitution, (ii) the SubstiTution-based Itemset indeX (STIX) to retrieve HUIs containing substitutes, and (iii) an experimental study to depict the benefits of the proposed approach w.r.t. a baseline method.

Low-rank decomposition that explores and eliminates the linear dependency within a tensor is often used as a structured model pruning method for deep convolutional neural networks. However, the model accuracy declines rapidly as the compression ratio increases over a threshold. We have observed that with a small amount of sparse elements, the model accuracy can be recovered significantly for the highly compressed CNN models. Based on this premise, we developed a novel method, called LPSD (Low-rank Plus Sparse Decomposition), that decomposes a CNN weight tensor into a combination of a low-rank and a sparse components, which can better maintain the accuracy for the high compression ratio. For a pretrained model, the network structure of each layer is split into two branches: one for low-rank part and one for sparse part. LPSD adapts the alternating approximation algorithm to minimize the global error and the local error alternatively. An exhausted search method with pruning is designed to search the optimal group number, ranks, and sparsity. Experimental results demonstrate that in most scenarios, LPSD achieves better accuracy compared to the state-of-the-art methods when the model is highly compressed.

Treatment effect estimation has received increasing attention recently. However, the issue of data sparsity often poses a significant challenge, limiting the feasibility of modeling. This paper aims to leverage cross-domain data to mitigate the data sparsity issue, and presents a framework called TEC. TEC incorporates a collaborative and adversarial generalization module to enhance information sharing and transferability across domains. This module encourages the learned representations of different domains to be more cohesive, thereby improving the generalizability of the models. Furthermore, we address the issue of poor performance for few-shot samples in each domain, and propose a pattern augmentation module that explicitly borrows samples from other domains and applies the self-teaching philosophy to them. Extensive experiments are conducted on both synthetic and benchmark datasets to demonstrate the superiority of the proposed framework.