Multimodal Entity Alignment (MMEA) aims to identify equivalent entities across different data modalities, enabling structural data integration that in turn improves the performance of various large language model applications. To lift the requirement of labeled seed pairs that are difficult to obtain, recent methods shifted to an unsupervised paradigm using pseudo-alignment seeds. However, unsupervised entity alignment in multimodal settings remains underexplored, mainly because the incorporation of multimodal information often results in imbalanced coverage of pseudo-seeds within the knowledge graph. To overcome this, we propose PSQE (Pseudo-Seed Quality Enhancement) to improve the precision and graph coverage balance of pseudo seeds via multimodal information and clustering-resampling. Theoretical analysis reveals the impact of pseudo seeds on existing contrastive learning-based MMEA models. In particular, pseudo seeds can influence the attraction and the repulsion terms in contrastive learning at once, whereas imbalanced graph coverage causes models to prioritize high-density regions, thereby weakening their learning capability for entities in sparse regions. Experimental results validate our theoretical findings and show that PSQE as a plug-and-play module can improve the performance of baselines by considerable margins.

Cross-modal retrieval (CMR) has advanced considerably by mapping image and text features into a shared embedding space; however, these approaches still face two persistent challenges: (1) semantic sparsity, where discriminative cues are confined to localized regions, making it difficult to identify implicit visual evidence; and (2) ranking uncertainty under semantic ambiguity, where models struggle to maintain the correct retrieval order when candidates share similar contexts. To address these issues, we propose the Dual-Branch Multi-Granularity Network (DBMG) with Structured Contrastive Ranking, which enriches visual semantics by leveraging a multimodal large language model to generate auxiliary descriptions, aligns sparse cues through a dual-branch architecture capturing both global and local interactions, and enforces ranking consistency via a three-stage contrastive objective that progressively optimizes category clustering, instance alignment, and margin-based ranking. Extensive experiments on four standard CMR benchmarks demonstrate that DBMG outperforms 12 strong baselines, achieving an average 15.91% improvement in mAP, establishing a new state-of-the-art. The code is available at https://github.com/DMiC-Lab-HFUT/DBMG.

As a crucial aspect of data mining, high average utility sequential pattern mining (SPM) aims to discover low frequency and high average utility patterns (subsequences) in sequence data. Most existing high average utility SPM methods overlook the repetitive occurrences of patterns in each sequence, resulting in some important patterns being ignored. To address this issue, we focus on the problem of mining high average utility nonoverlapping patterns (HUPs) from sequential database, and propose an HUP-Miner algorithm. To reduce the need for repeated scanning of the original database, we use a position dictionary to record the occurrence information of each item. To reduce the number of candidate patterns generated, we adopt a pattern join strategy and explore four pruning strategies. To efficiently calculate the average utility of a pattern, we propose an SPC algorithm that utilizes the occurrence positions of sub-patterns. When compared with 12 competitive algorithms, the experimental results on 14 databases show that HUP-Miner gives superior results. Furthermore, we use information gain as the utility for each item, and find that the HUPs discovered in this way can generate better performance via a clustering analysis. All of the algorithms and databases used here are available from https://github.com/wuc567/Pattern-Mining/tree/master/HUP-Miner .

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

Database parameter automatic tuning is one of the challenging and difficult tasks that database administrators (DBAs) frequently encounter in artificial intelligence (AI) enabled database (DB) systems. Preferentially optimizing key parameters emerges as a critical point in addressing this issue, and it can help identify important parameters by exploring the interactions between parameters. Aiming to overcome the disadvantages of existing methods, we propose a collaborative multi-agents model called CMA+DB to automatically tune DB parameters in an effective and efficient fashion. CMA+DB integrates three components including SAPM (Single-Agent Pre-trained Model), MATM (Multi-Agent Joint Training Model), and PJTM (Probability-based Joint Training Model). SAPM applies the deep deterministic policy gradient to explore the impact of one single agent on DB performance, MATM uses multi-agent deep deterministic policy gradients to find agents that collaboratively work to improve DB performance, and PJTM can enhance parameter tuning by important agents based on a probabilistic selection factor. In the CMA+DB model, each agent is responsible for tuning a portion of the parameters, and multiple agents collaborate to recommend the optimal parameter configuration. This hybrid model can expand the number of tunable parameters in order to perform parameter tuning from the aspects of functions and parameter levels (i.e., global, DB, and session level). Experimental results reveal that CMA+DB obtains the fastest convergence performance (when reaching the largest throughput) of 14.83% faster than the state-of-the-art (SOTA) algorithms in the TPC-C benchmark on average. Essentially, after the phase of SAPM model training, CMA+DB outperforms the performance of the SOTA models in throughput. Furthermore, DB performance of CMA+DB can be improved by 1.758% through the phases of MATM and PJTM model training.

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.

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

Knowledge Graphs (KGs) often suffer from link incompleteness, limiting their performance in downstream tasks. Knowledge graph completion (KGC) has emerged to complete the missing links between entities, so to integrate new knowledge into existing KGs. Unfortunately, traditional KGC models mainly focus on static KGs with a fixed set of entities and relations, thereby struggling in generalization to dynamic KGs with possible entity drift. In this paper, we propose a Link Completion model for dynamic KGs with Entity Drift (LCED) to solve the issue. Unlike traditional link completion models, LCED can generate accurate embeddings for drifted entities, without imposing any assumption on their time or rule characteristic. The drifted entities are incorporated into the KG where their links to existing entities are predicted in an incremental fashion, without retraining the entire KG for computational efficiency. Extensive experiments conducted on benchmark datasets demonstrate the effectiveness of our proposed LCED in link completion for dynamic KGs by outperforming its state-of-the-art competitors. Code and datasets are available at https://github.com/field658/LCED.

Knowledge Graph Query Embedding (KGQE) aims to embed First-Order Logic (FOL) queries in a low-dimensional KG space for complex reasoning over incomplete KGs. To enhance the generalization of KGQE models, recent studies integrate various external information (such as entity types and relation context) to better capture the logical semantics of FOL queries. The whole process is commonly referred to as Query Pattern Learning (QPL). However, current QPL methods typically suffer from the pattern-entity alignment bias problem, leading to the learned defective query patterns limiting KGQE models' performance. To address this problem, we propose an effective Query Instruction Parsing Plugin (QIPP) that leverages the context awareness of Pre-trained Language Models (PLMs) to capture latent query patterns from code-like query instructions. Unlike the external information introduced by previous QPL methods, we first propose code-like instructions to express FOL queries in an alternative format. This format utilizes textual variables and nested tuples to convey the logical semantics within FOL queries, serving as raw materials for a PLM-based instruction encoder to obtain complete query patterns. Building on this, we design a query-guided instruction decoder to adapt query patterns to KGQE models. To further enhance QIPP's effectiveness across various KGQE models, we propose a query pattern injection mechanism based on compressed optimization boundaries and an adaptive normalization component, allowing KGQE models to utilize query patterns more efficiently. Extensive experiments demonstrate that our plug-and-play method improves the performance of eight basic KGQE models and outperforms two state-of-the-art QPL methods.

Data are exploding in many fields and may exist in the streaming mode. When the generation speed of massive streaming data far exceeds the processing speed of a single node and the generated data need to be processed in real time, traditional centralized learning models are challenging in meeting the efficiency requirements. Therefore, online distributed learning models emerge. As time progresses, features may continuously emerge from various sources in a distributed and heterogeneous fashion. Therefore, we study the problem of online distributed heterogeneous streaming feature selection and propose a novel framework to address it, named DHSFS. The framework comprises two main components: sub-node streaming feature selection and global information synchronization. The sub-node component uses a dynamic strategy to select strong features, discard irrelevant ones, and cache weakly relevant features. In the global information synchronization stage, each sub-node synchronizes statistics information with the master node to adjust the global thresholds dynamically. Finally, the features selected by each sub-node are summarized and output. Experiments on 16 datasets show that the DHSFS framework has both high prediction accuracy and high efficiency of online stream feature selection.

Sequential pattern mining (SPM) with gap constraints (or repetitive SPM or tandem repeat discovery in bioinformatics) can find frequent repetitive subsequences satisfying gap constraints, which are called positive sequential patterns with gap constraints (PSPGs). However, classical SPM with gap constraints cannot find the frequent missing items in the PSPGs. To tackle this issue, this article explores negative sequential patterns with gap constraints (NSPGs). We propose an efficient NSPG-Miner algorithm that can mine both frequent PSPGs and NSPGs simultaneously. To effectively reduce candidate patterns, we propose a pattern join strategy with negative patterns which can generate both positive and negative candidate patterns at the same time. To calculate the support (frequency of occurrence) of a pattern in each sequence, we explore a NegPair algorithm that employs a key-value pair array structure to deal with the gap constraints and the negative items simultaneously and can avoid redundant rescanning of the original sequence, thus improving the efficiency of the algorithm. To report the performance of NSPG-Miner, 11 competitive algorithms and 11 datasets are employed. The experimental results not only validate the effectiveness of the strategies adopted by NSPG-Miner but also verify that NSPG-Miner can discover more valuable information than the state-of-the-art algorithms. Algorithms and datasets can be downloaded from https://github.com/wuc567/Pattern-Mining/tree/master/NSPG-Miner .

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

Cold-start recommendation is a well-known problem in practical application scenarios. Generating reliable recommendations can be challenging when interactions are typically sparse. To mitigate the cold-start problem, some methods incorporate auxiliary information about users and items, and others adopt meta-learning to improve recommendation accuracy. However, these approaches overlook the fact that items are interdependent and likely to be related or similar. Moreover, user preference distributions in the meta-training and meta-testing phases are different in the cold-start scenario. To address these problems, we present a novel strategy called Causal Meta-learning with Multi-view Graphs (CausalMMG). Specifically, we first construct multi-view item-item graphs to explore the correlations and similarities between items from multiple perspectives. A multi-view item representer is then used to learn item representations, exploiting graph convolution neural networks to capture the structure of these different item–item graphs. We then resort to the structural causal models of causal inference and further develop a causality-enhanced bi-level adaptive meta-learner to eliminate bias caused by the different distributions of user preferences. Moreover, the meta-learner learns the user preferences for items in different orders through hierarchical and task-level adaptations. Finally, we evaluate CausalMMG on several real-world datasets, demonstrating its effectiveness in various scenarios. The results show that the proposed CausalMMG is significantly superior to competitive baseline methods for cold-start recommendation on all datasets, highlighting the importance of incorporating the multiple relationships between items and modeling different user preference distributions in recommender systems.

Knowledge Graphs (KGs) often suffer from incompleteness and this issue motivates the task of Knowledge Graph Completion (KGC). Traditional KGC models mainly concentrate on static KGs with a fixed set of entities and relations, or dynamic KGs with temporal characteristics, faltering in their generalization to constantly evolving KGs with possible irregular entity drift. Thus, in this paper, we propose a novel link prediction model based on the embedding representation to handle the incompleteness of KGs with entity drift, termed as DCEL. Unlike traditional link prediction, DCEL could generate precise embeddings for drifted entity without imposing any regular temporal characteristic. The drifted entity is added into the KG with its links to the existing entity predicted in an incremental fashion with no requirement to retrain the whole KG for computational efficiency. In terms of DCEL model, it fully takes advantages of unstructured textual description, and is composed of four modules, namely MRC (Machine Reading Comprehension), RCAA (Relation Constraint Attentive Aggregator), RSA (Relation Specific Alignment) and RCEO (Relation Constraint Embedding Optimization). Specifically, the MRC module is first employed to extract short texts from long and redundant descriptions. Then, RCAA is used to aggregate the embeddings of textual description of drifted entity and the pre-trained word embeddings learned from corpus to a single text-based entity embedding while shielding the impact of noise and irrelevant information. After that, RSA is applied to align the text-based entity embedding to graph-based space to obtain the corresponding graph-based entity embedding, and then the learned embeddings are fed into the gate structure to be optimized based on the RCEO to improve the accuracy of representation learning. Finally, the graph-based model TransE is used to perform link prediction for drifted entity. Extensive experiments conducted on benchmark datasets in terms of evaluation protocols of MRR and Hits@ \(k\) reveal the superiority of DCEL model compared to its SOTAs.

Feature selection is an essential pre-process component in data mining that aims to select the most relevant features from the target dataset. Datasets are always dynamic in real-world applications, and features may exist in stream mode. Then, online streaming feature selection methods are proposed, which deal with streaming features arriving continuously in real-time. However, most existing algorithms prioritize high accuracy and low time-consumption but overlook the stability of the selected features. Stable feature selection results are crucial for users in practice. For instance, in the medical field, unstable feature selection results can make it challenging for experts to identify the main causative factors of a disease. Motivated by this, this article proposes a new online stable streaming feature selection method via feature aggregation named OSSFS. Specifically, inspired by the cohesive MeanShift approach, OSSFS applies an incremental aggregation strategy to partition the streaming features into multiple hyperellipsoids. Then, we incrementally update and merge these hyperellipsoids with new streaming features. Finally, we select representative features from each hyperellipsoid as the final selected feature subset. Extensive experiments are conducted on several real-world datasets to compare our new method with state-of-the-art competing algorithms in cases of stability and predictive accuracy. Experimental results indicate that OSSFS achieves optimal stability without losing prediction accuracy.

Online learning, where feature spaces can change over time, offers a flexible learning paradigm that has attracted considerable attention. However, it still faces three significant challenges. First, the heterogeneity of real-world data streams with mixed feature types presents challenges for traditional parametric modeling. Second, data stream distributions can shift over time, causing an abrupt and substantial decline in model performance. Additionally, the time and cost constraints make it infeasible to label every data instance in a supervised setting. To overcome these challenges, we propose a new algorithm Online Learning from Mix-typed, Drifted, and Incomplete Streaming Features (OL-MDISF), which aims to relax restrictions on both feature types, data distribution, and supervision information. Our approach involves utilizing copula models to create a comprehensive latent space, employing an adaptive sliding window for detecting drift points to ensure model stability, and establishing label proximity information based on geometric structural relationships. To demonstrate the model’s efficiency and effectiveness, we provide theoretical analysis and comprehensive experimental results.

Density peaks clustering (DPC) is one of the density-based clustering algorithms and has been widely studied and applied in recent years because of its unique parameter, non-iteration and good robustness. However, it cannot effectively identify the cluster centers, and time and space complexities are too high. To this end, this paper proposes a fast density peaks clustering algorithm based on approximatek-nearest neighbors (FDPAN). Firstly, it uses Balanced K-means based Hierarchical K-means (BKHK) method to partition the data and quickly find the approximatek-nearest neighbors (AKNN), improving the algorithm’s efficiency on large-scale high-dimensional data. Meanwhile, three-way clustering is used to improve the neighbor search of the boundary points of the partition. Then, the local density and relative distance of DPC are recalculated by AKNN. Finally, according to the similar density chain, the connected high-density points are labeled while searching for the cluster center, and the remaining points are assigned to the clusters where their nearest higher-density points are located. Theoretical analysis and experiments on synthetic and real datasets show that FDPAN can obtain higher clustering results and shorten the operation time on large-scale high-dimensional data compared with DPC and its variants.

As the representative density-based clustering algorithm, density peaks clustering (DPC) has wide recognition, and many improved algorithms and applications have been extended from it. However, the DPC involving privacy protection has not been deeply studied. In addition, there is still room for improvement in the selection of centers and allocation methods of DPC. To address these issues, vertical federated density peaks clustering under nonlinear mapping (VFDPC) is proposed to address privacy protection issues in vertically partitioned data. Firstly, a hybrid encryption privacy protection mechanism is proposed to protect the merging process of distance matrices generated by client data. Secondly, according to the merged distance matrix, a more effective cluster merging under nonlinear mapping is proposed to ameliorate the process of DPC. Results on man-made, real, and multi-view data fully prove the improvement of VFDPC on clustering accuracy.

Outlier detection is essential for data compliance, fraud prevention, and strategic decision-making. Finding outliers relies on study of feature space to find anomalous instances. As the feature dimension increases, it will inevitably complicate the process and hinder the models from finding genuine outliers. In this paper, we investigate an ever-more challenging task, online outlier detection (OOD) problem, where data points to be examined for outlier detection are characterized by two dynamic changes: (1) increasing volume instead of a static set; and (2) evolving feature space instead of a known set. Such instance and feature space dynamics impedes traditional OD techniques reliant on geometric data structure for distinguishing outliers. To aid, we propose a new approach coinedOnline Outlier Detection in Open Feature Spaces, which circumvents this limitation by learning a latent hypersphere representation, respectively positioning regular and anomalous data points inside and outside its boundary. The crux of our approach tailors a reconstruction loss, allowing each data point to be represented as anadditionof its pertinent feature embeddings. Each of these embeddings is updated non-intrusively, championing both efficient and incremental learning of the latent hypersphere. Extensive experiments on twelve benchmark datasets underscore the robustness and superior performance of our method against seven leading counterparts. Code is released inhttps://github.com/X1aoLian/OODOFS.git.

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

Contrastive Learning (CL)-based recommender systems have gained prominence in the context of Heterogeneous Graph (HG) due to their capacity to enhance the consistency of representations across different views. However, existing frameworks often neglect the fact that user-item interactions within HG are governed by diverse latent intents (e.g., brand preferences or demographic characteristics of item audiences), which are pivotal in capturing fine-grained relations. The exploration of these underlying intents, particularly through the lens of meta-paths in HGs, presents us with two principal challenges: i) How to integrate CL with intents; ii) How to mitigate noise from meta-path-driven intents. To address these challenges, we propose an innovative framework termedIntent-guided Heterogeneous Graph Contrastive Learning(IHGCL), which designed to enhance CL-based recommendation by capturing the intents contained within meta-paths. Specifically, the IHGCL framework includes: i) a meta-path-based Dual Contrastive Learning (DCL) approach to effectively integrate intents into the recommendation, constructing intent-intent contrast and intent-interaction contrast; ii) a Bottlenecked AutoEncoder (BAE) that combines mask propagation with the information bottleneck principle to significantly reduce noise perturbations introduced by meta-paths. Empirical evaluations conducted across six distinct datasets demonstrate the superior performance of our IHGCL framework relative to conventional baseline methods.

Knowledge graph embedding is efficient method for reasoning over known facts and inferring missing links. Existing methods are mainly triplet-based or graph-based. Triplet-based approaches learn the embedding of missing entities by a single triple only. They ignore the fact that the knowledge graph is essentially a graph structure. Graph-based methods consider graph structure information but ignore the contextual information of nodes in the knowledge graph, making them unable to discern valuable entity (relation) information. In response to the above limitations, we propose a general graph transformer framework for knowledge graph embedding (TGformer). It is the first to use a graph transformer to build knowledge embeddings with triplet-level and graph-level structural features in the static and temporal knowledge graph. Specifically, a context-level subgraph is constructed for each predicted triplet, which models the relation between triplets with the same entity. Afterward, we design a knowledge graph transformer network (KGTN) to fully explore multi-structural features in knowledge graphs, including triplet-level and graph-level, boosting the model to understand entities (relations) in different contexts. Finally, semantic matching is adopted to select the entity with the highest score. Experimental results on several public knowledge graph datasets show that our method can achieve state-of-the-art performance in link prediction.

Most clustering algorithms require setting one or more parameters, which rely on prior knowledge or are constantly adjusted based on external indicators. To address the issues of requiring external index guidance, blindness, and time-consuming parameter setting for clustering algorithms on complex data, we propose a novel Parameter-Adaptive Border Peeling clustering algorithm (PABP). The PABP algorithm initially employs the maximum number of neighbors identified through natural neighbor search to automatically ascertain the number of local neighborhoods. At the same time, the Gaussian kernel bandwidth can be adaptively obtained in density measurement, which can highlight high-density areas. Secondly, the number of peels is adaptively determined by the coefficient of variation of density during the iterative border peeling process. Lastly, labels are assigned to core points based on graph connections, while the clustering of border points is accomplished via label propagation. PABP does not require users to adjust parameters based on prior knowledge or external indicators throughout the entire process. In the experiment, PABP was compared with seven other advanced clustering algorithms on 13 synthetic datasets, 10 UCI datasets, and Olivetti Face and MNIST datasets. The results indicate that the clustering performance of PABP is superior to the compared algorithms.

In recommender systems, heterogeneous graph neural networks (HGNNs) have demonstrated remarkable efficacy due to their capacity to harness rich auxiliary information within heterogeneous information networks (HINs). However, existing HGNN-based recommendation faces severe noise cascading challenge. The presence of substantial data noise can adversely affect robustness of recommender, as the graph structures are susceptible to noise and even unnoticed malicious perturbations. Moreover, these noises can propagate and accumulate through connected nodes, potentially exerting a profound impact on target nodes within the graph structure. To tackle the noise challenges, we present a Bottlenecked Heterogeneous Graph Contrastive Learning (BHGCL), aiming to enhance the robustness of recommendation systems. BHGCL can first effectively separate fine-grained latent factors from complex self-supervision signals with a disentangled-based encoder, leveraging diverse semantic information across various meta-paths. Then, by employing the information bottleneck (IB) principle, BHGCL adaptively learns to reduce noise in augmented graphs. IB can capture the minimum sufficient information from the data features, which significantly improves system performance in environments with noisy data. Experimental findings from multiple real-world datasets reveal that our approach surpasses the latest advanced recommendation systems, verifying its effectiveness and robustness. To reproduce our work, we have open-sourced our code at https://github.com/DuellingSword/BHGCL .

Heterogeneous graph neural networks (HGNN) have exhibited significant performance gains by modeling the information propagation process in graph-structured data for recommender systems. However, existing HGNN-based Recommendation still face two challenges: (1) They overlook the rich semantics brought by the combination of different meta-paths, making it difficult to capture the importance of various meta-paths; (2) when HGNN use meta-paths to capture high-order information, they are susceptible to noise data, as noise from connected nodes can create cumulative effects on a target node in the graph. To tackle these issues, we propose a new model called the Denoising Heterogeneous Graph Pre-training Framework (DHGPF) to enhance recommendation tasks. This framework has two stages: pre-training and training. In the pre-training stage, we assign learnable weights to different meta-paths and use a simplified multi-layer graph convolution network to automatically aggregate semantic information from different meta-path combinations. This approach can capture the importance of these paths. The training stage focuses on reducing noise using gating mechanism and denoising structure learning methods. These methods accomplish the denoising process through information filtering. Our model was evaluated on three real-world datasets, demonstrating that DHGPF outperforms other state-of-the-art recommendation methods. We have further organized the source code of the article at https://github.com/wangyu0627/DHGPF .

Methods based on graph neural networks for solving combinatorial optimization (CO) problems have exhibited promising results in tackling a range of NP-hard problems, eliminating the necessity for reliance on manually created domain knowledge. Existing models including reinforcement learning (RL) framework assume that combinatorial instances in the training set contribute equally during training. Nevertheless, there is considerable variation in the quality of training instances, and the performance of models may suffer from the inclusion of low-quality training instances. This paper expands the current scope of neural solvers for CO problems through the incorporation of curriculum learning (CL). To alleviate the adverse impact of low-quality training instances, we propose CL4CO which utilizes CL strategy, a selective training method, to train models based on the rank of instances' quality in neural Combinatorial Optimization framework. Also, we introduce several candidate topology-aware metrics based on heterophily ratio and evaluation of clustering for the training scheduler. Furthermore, it is noteworthy to emphasize that it has potential to enhance the generalization capacity of RL-based baselines and we give a experimental validation. This enhancement plugin from the fact that CL empowers the acquired RL-based solver to effectively leverage commonly shared features within the same class of CO. Empirically, we conduct a case study on MaxCut, a classical discrete Oil-vector CO, to verify our findings and our results demonstrate that CL4CO is efficient and superiority with good generalization ability.

Deep graph clustering (DGC) has been a promising method for clustering graph data in recent years. However, existing research primarily focuses on optimizing clustering outcomes by improving the quality of embedded representations, resulting in slow-speed complex models. Additionally, these methods do not consider changes in node similarity and corresponding adjustments in the original structure during the iterative optimization process after updating node embeddings, which easily falls into the representation collapse issue. We introduce an Efficient Graph Auto-Encoder (EGAE) and a dynamic graph weight updating strategy to address these issues, forming the basis for our proposed Fast DGC (FastDGC) network. Specifically, we significantly reduce feature dimensions using a linear transformation that preserves the original node similarity. We then employ a single-layer graph convolutional filtering approximation to replace multiple layers of graph convolutional neural network, reducing computational complexity and parameter count. During iteration, we calculate the similarity between nodes using the linearly transformed features and periodically update the original graph structure to reduce edges with low similarity, thereby enhancing the learning of discriminative and cohesive representations. Theoretical analysis confirms that EGAE has lower computational complexity. Extensive experiments on standard datasets demonstrate that our proposed method improves clustering performance and achieves a speedup of 2–3 orders of magnitude compared to state-of-the-art methods, showcasing outstanding performance. The code for our model is available at https://github.com/Marigoldwu/FastDGC . Furthermore, we have organized a portion of the DGC code into a unified framework, available at https://github.com/Marigoldwu/A-Unified-Framework-for-Deep-Attribute-Graph-Clustering .

Recommendation systems have become an indispensable part of daily life. Social recommendation systems, which utilize social relationships and past behaviors to infer users’ preferences, have gained popularity in recent years. Exploring the inherent characteristics implied by higher-order relationships offers a new approach to social recommendation. However, it is challenging due to sparse social networks, influence heterogeneity, and noisy feedback. In this article, we propose a Heterogeneous Meta-path Graph Learning model for Higher-order Social Recommendation (HEAL). Within HEAL, we introduce a heterogeneous graph in social recommendation and utilize a meta-path-guided random walk to generate higher-order relationships. By encoding higher-order structures and semantics along different meta-graphs, HEAL can mitigate the limitation of data sparsity. Moreover, HEAL exploits aspect-aware and semantic-aware attentions to adaptively propagate and aggregate useful features from different meta-neighbors and higher-order relations. These attention-based aggregation layers allow HEAL to suppress the heterogeneity of social influences. Furthermore, HEAL adopts contrastive learning as a supplemental task to the recommendation task by maximizing the consistency between the self-discriminating objectives. This auxiliary task enables the model to learn more differentiated representations, further reducing its sensitivity to noisy feedback. We evaluate the performance of HEAL through extensive experiments on public datasets. The results demonstrate that leveraging higher-order relations can enhance the quality of social recommendations by better capturing the complexity and diversity of users’ preferences and interactions.

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

Conversational recommender systems (CRS) have garnered significant attention in academia and industry because of their ability to capture user preferences via system questions and user responses. Typically, in a CRS, reinforcement learning (RL) is utilized to determine the optimal timing for requesting attribute information or suggesting items. However, existing methods consider user-preferred attributes independently and ignore that attributes may be of different importance to the same user, in the attribute and item selection phases, which limits the accuracy and interpretability of CRS. Inspired by this, we propose deep conversational path reasoning (DeepCPR), which involves constructing a reasoning path on a graph with a series of user-favored attributes. It utilizes the attention mechanism to thoroughly examine the connections between these attributes and provide improved explanations for which attributes to inquire about or which items to recommend. In DeepCPR, two deep-learning-based modules are proposed to realize attribute and item selection. In the first module, the sequence of attributes confirmed by the user in conversation is encoded with a gated graph neural network to obtain the user’s long-term preference using a self-attention mechanism for the selection of candidate attributes. In the second module, a self-attention approach with more appropriate strategies is developed to dynamically select candidate items. In addition, to achieve fine-grained user preference modeling, a recurrent neural network is employed to aggregate the sequence of attributes that interact with the users. Numerous experimental evaluations conducted on four real CRS datasets show that the proposed method significantly outperforms existing advanced methods in terms of conversational recommendations.

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

The explosion of data volume has gradually transformed big data processing from the static batch mode to the online streaming model. Streaming data can be divided into instance streams (feature space remains fixed while instances increase over time), feature streams (instance space is fixed while features arrive over time), or both. Generally, online streaming data learning has two main challenges: infinite length and concept changing. Recently, feature stream learning has received much attention. However, existing feature stream learning methods focus on feature selection or classification but ignore the concept changing over time. To the best of our knowledge, this is the first work that studies concept evolution detection over feature streams. Specifically, we first give the formal definition of concept evolution over feature streams, which include three different types: concept emerging, concept drift, and concept forgetting. Then, we design a novel framework to detect the concept evolution over feature streams that consists of a sliding window, an improved density peak-based clustering algorithm, and a weighted bipartite graph-based concept detecting method. Extensive experiments have been conducted on several synthetic and high-dimensional datasets to indicate our new method’s ability to cluster and detect concept evolution over feature streams.

Sequential pattern mining (SPM) is an important branch of knowledge discovery that aims to mine frequent sub-sequences (patterns) in a sequential database. Various SPM methods have been investigated, and most of them are classical SPM methods, since these methods only consider whether or not a given pattern occurs within a sequence. Classical SPM can only find the common features of sequences, but it ignores the number of occurrences of the pattern in each sequence, i.e., the degree of interest of specific users. To solve this problem, this paper addresses the issue of repetitive nonoverlapping sequential pattern (RNP) mining and proposes the RNP-Miner algorithm. To reduce the number of candidate patterns, RNP-Miner adopts an itemset pattern join strategy. To improve the efficiency of support calculation, RNP-Miner utilizes the candidate support calculation algorithm based on the position dictionary. To validate the performance of RNP-Miner, 10 competitive algorithms and 20 sequence databases were selected. The experimental results verify that RNP-Miner outperforms the other algorithms, and using RNPs can achieve a better clustering performance than raw data and classical frequent patterns. All the algorithms were developed using the PyCharm environment and can be downloaded fromhttps://github.com/wuc567/Pattern-Mining/tree/master/RNP-Miner.

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.

Order-preserving pattern (OPP) mining is a type of sequential pattern mining method in which a group of ranks of time series is used to represent an OPP. This approach can discover frequent trends in time series. Existing OPP mining algorithms consider data points at different time to be equally important; however, newer data usually have a more significant impact, while older data have a weaker impact. We therefore introduce the forgetting mechanism into OPP mining to reduce the importance of older data. This paper explores the mining of OPPs with forgetting mechanism (OPF) and proposes an algorithm called OPF-Miner that can discover frequent OPFs. OPF-Miner performs two tasks, candidate pattern generation and support calculation. In candidate pattern generation, OPF-Miner employs a maximal support priority strategy and a group pattern fusion strategy to avoid redundant pattern fusions. For support calculation, we propose an algorithm called support calculation with forgetting mechanism, which uses prefix and suffix pattern pruning strategies to avoid redundant support calculations. The experiments are conducted on nine datasets and 12 alternative algorithms. The results verify that OPF-Miner is superior to other competitive algorithms. More importantly, OPF-Miner yields good clustering performance for time series, since the forgetting mechanism is employed.

Large language models (LLMs), such as ChatGPT and GPT4, are making new waves in the field of natural language processing and artificial intelligence, due to their emergent ability and generalizability. However, LLMs are black-box models, which often fall short of capturing and accessing factual knowledge. In contrast, Knowledge Graphs (KGs), Wikipedia and Huapu for example, are structured knowledge models that explicitly store rich factual knowledge. KGs can enhance LLMs by providing external knowledge for inference and interpretability. Meanwhile, KGs are difficult to construct and evolve by nature, which challenges the existing methods in KGs to generate new facts and represent unseen knowledge. Therefore, it is complementary to unify LLMs and KGs together and simultaneously leverage their advantages. In this article, we present a forward-looking roadmap for the unification of LLMs and KGs. Our roadmap consists of three general frameworks, namely,1) KG-enhanced LLMs,which incorporate KGs during the pre-training and inference phases of LLMs, or for the purpose of enhancing understanding of the knowledge learned by LLMs;2) LLM-augmented KGs,that leverage LLMs for different KG tasks such as embedding, completion, construction, graph-to-text generation, and question answering; and3) Synergized LLMs + KGs, in which LLMs and KGs play equal roles and work in a mutually beneficial way to enhance both LLMs and KGs for bidirectional reasoning driven by both data and knowledge. We review and summarize existing efforts within these three frameworks in our roadmap and pinpoint their future research directions.

Recent advances in multi-kernel-based methods for outlier detection have positioned them as an attractive way to detect instances that are markedly different from the remaining data in a dataset. Currently, most outlier detection approaches based on multi-kernel learning are simply a convex combination of various kernels with handcrafted weights, meaning that these weights may not be suitable. Meanwhile, this combination of weights does not sufficiently consider the intrinsic correlations of instances when fusing different kernels. Thus, a key challenge is how to adaptively learn an appropriate combination of weights for capturing a new feature space in which outliers can be better detected than the original space. Simultaneously, it is still a burning issue to get the optimal combination of weights due to considerable computational cost and memory usage when the feature or instance size is large. In this paper, we propose a novel method forefficientadaptivemulti-kernel foroutlierdetection (EAMOD), which automatically learns the optimal weight for each training instance under different kernels using a non-negative function. In addition, we design a safe screening rule (SSR) for EAMOD to improve its training efficiency without any loss of accuracy. To the best of our knowledge, it is the first attempt to develop SSR for multi-kernel-based outlier detection methods. Extensive experiments show that EAMOD is effective and efficient.

Recently, order-preserving pattern (OPP) mining, a new sequential pattern mining method, has been proposed to mine frequent relative orders in a time series. Although frequent relative orders can be used as features to classify a time series, the mined patterns do not reflect the differences between two classes of time series well. To effectively discover the differences between time series, this paper addresses the top-kcontrast OPP (COPP) mining and proposes a COPP-Miner algorithm to discover the top-kcontrast patterns as features for time series classification, avoiding the problem of improper parameter setting. COPP-Miner is composed of three parts: extreme point extraction to reduce the length of the original time series, forward mining, and reverse mining to discover COPPs. Forward mining contains three steps: group pattern fusion strategy to generate candidate patterns, the support rate calculation method to efficiently calculate the support of a pattern, and two pruning strategies to further prune candidate patterns. Reverse mining uses one pruning strategy to prune candidate patterns and consists of applying the same process as forward mining. Experimental results validate the efficiency of the proposed algorithm and show that top-kCOPPs can be used as features to obtain a better classification performance.

Recently, ChatGPT, a representative large language model (LLM), has gained considerable attention. Due to their powerful emergent abilities, recent LLMs are considered as a possible alternative to structured knowledge bases like knowledge graphs (KGs). However, while LLMs are proficient at learning probabilistic language patterns and engaging in conversations with humans, they, like previous smaller pre-trained language models (PLMs), still have difficulty in recalling facts while generating knowledge-grounded contents. To overcome these limitations, researchers have proposed enhancing data-driven PLMs with knowledge-based KGs to incorporate explicit factual knowledge into PLMs, thus improving their performance in generating texts requiring factual knowledge and providing more informed responses to user queries. This paper reviews the studies on enhancing PLMs with KGs, detailing existing knowledge graph enhanced pre-trained language models (KGPLMs) as well as their applications. Inspired by existing studies on KGPLM, this paper proposes enhancing LLMs with KGs by developing knowledge graph-enhanced large language models (KGLLMs). KGLLM provides a solution to enhance LLMs’ factual reasoning ability, opening up new avenues for LLM research.

Online learning is critical for handling complex data streams in Big Data-related applications. This study explores a new online learning problem where both the features and labels are incomplete. Such incompleteness poses a critical challenge in determining the latent relationship between incomplete features and labels. Unfortunately, existing online learning methods only consider a few cases of incomplete feature spaces, such as trapezoidal, evolvable, and capricious data streams, limiting their applicability to this problem. To bridge this gap, this study proposes a novel algorithm ofOnlineLearning for Data Streams withIncompleteFeatures andLabels (OLIFL). OLIFL imposes no constraints on changing patterns of feature space and does not require all instances to be labeled with two-fold ideas. First, OLIFL explores the informativeness of individual features to update the classifier by dynamically maintaining global feature space and updating the informativeness matrix. Second, it estimates the label confidence of unlabeled instances to control their negative effects by limiting the error upper bound. Extensive experiments on benchmark datasets are conducted in five scenarios: three incomplete feature (trapezoidal, evolvable, and capricious) spaces, and two incomplete labels (only missing labels and missing both features and labels). In addition, we explore the sensitivity of the model to parameters, and its usability and response efficiency in handling concept drifts. The results show that OLIFL significantly outperforms its rivals. Moreover, we use OLIFL to classify a movie review task as real application verification.

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.

In the short text, the extremely short length, feature sparsity, and high ambiguity pose huge challenges to classification tasks. Recently, as an effective method for tuning Pre-trained Language Models for specific downstream tasks, prompt-learning has attracted a vast amount of attention and research. The main intuition behind the prompt-learning is to insert the template into the input and convert the tasks into equivalent cloze-style tasks. However, most prompt-learning methods only consider the class name and monotonous strategy for knowledge incorporating in cloze-style prediction, which will inevitably incur omissions and bias in short text classification tasks. In this paper, we propose a short text classification method with prompt-learning. Specifically, the top$M$concepts related to the entity in the short text are retrieved from the open Knowledge Graph like Probase, these concepts are first selected by the distance with class labels, which takes both the short text itself and the class name into consideration during expanding label word space. Then, we conducted four additional strategies for the integration of the expanded concepts, and the union of these concepts are adopted finally in the verbalizer of prompt-learning. Experimental results show that the obvious improvement is obtained compared with other state-of-the-art methods on five well-known datasets.

Unsupervised domain adaptation aims to facilitate learning tasks in unlabeled target domain with knowledge in the related source domain, which has achieved awesome performance with the pre-trained language models (PLMs). Recently, inspired by GPT, the prompt-tuning model has been widely explored in stimulating rich knowledge in PLMs for language understanding. However, existing prompt-tuning methods still directly applied the model that was learned in the source domain into the target domain to minimize the discrepancy between different domains, e.g., the prompts or the template are trained separately to learn embeddings for transferring to the target domain, which is actually the intuition of end-to-end deep-based approach. In this paper, we propose an Iterative Soft Prompt-Tuning method (ItSPT) for better unsupervised domain adaptation. On the one hand, the prompt-tuning model learned in the source domain is converted into an iterative model to find the true label information in the target domain, the domain adaptation method is then regarded as a few-shot learning task. On the other hand, instead of hand-crafted templates, ItSPT adopts soft prompts for both considering the automatic template generation and classification performance. Experiments on both English and Chinese datasets demonstrate that our method surpasses the performance of SOTA methods.

Relation reasoning inKnowledgeGraphCompletion (KGC) aims at predicting missing relations between entities. Recently, effective KGC methods have usually focused on exploring the path pattern between entities, such as reward-based path walking and path context mining, to complete target relations. However, these methods typically suffer from two challenges: 1) They have difficulty in handling the individual representation limitation of candidate paths when there are no paths that directly represent latent relations between entities; 2) They overlook the biases of path context induction, which leads to unreasonable information interfering with the model's reasoning. To manage these challenges, aGeometric-ContextualMutualInfomax (GCMI) path aggregator is proposed for relation reasoning. First, we design an attentive path aggregator with a shared Transformer encoder to capture the contexts from several candidate paths parallelly and integrate these contexts to sufficiently represent the latent relations of each entity pair for reasoning. Then, the GCMI modules are proposed to constrain the local and global biases of path context induction in the Transformer encoder and the path aggregator, respectively, by a straightforward geometric rule. Extensive experiments on 32 real-world relation reasoning tasks demonstrate that our method significantly outperforms 8 state-of-the-art baselines in terms of AP and AUC.

Adverse drug-drug interaction (ADDI) is a significant life-threatening issue for public health. The current methods for ADDI prediction usually work in a "nondiscriminatory" manner by treating each feature without discrimination and equally employing all features into ADDI modeling. Driven by this issue, we propose a Dependence Guided Discriminative Feature Selection (DGDFS) model for ADDI prediction, in which molecular structure and side effect are adopted with the incorporation of l2,0-norm equality constraints to select discriminative molecular substructures and side effects and three dependence based terms among molecular structure, side effect, and ADDIs to guide feature selection. Extensive experiments demonstrate the superior performance of DGDFS compared with fourteen state-of-the-art ADDI prediction and feature selection models.

Computing generates intelligence. With this statement we do not mean computing’s capabilities of manipulating numbers, shapes, symbols, and even logics. What we mean is the ingenious design of computing structures which serve as the basis of intelligence generation during program running. In this panel discussion, we consider how to obtain such capabilities through some computing paradigms as examples, including principal computing, logic computing, discriminative computing, and generative computing. The panelists express their thoughts about the inherent advantages and disadvantages of each of these paradigms, in terms of their adaptivity, interpretability, generality and specificity, and dives into detailed discussions about Large Language Models (LLMs), a mainstream generative paradigm which leverages the strengths of large pre-trained models and downstream prompt tuning to deliver combined intelligence, superior to most existing frameworks in natural language processing. The panel outlines potential challenges of the generative paradigm, with a strong focus on LLMs, and emphasizes that future directions of such models will need to address (1) tackling bias, discrimination, and transparency challenges; (2) delivering logical answers with high specificity; (3) enabling personalized, lightweight, and rapid updating mechanisms; (4) assessing accreditation, tracing, and misusages; and (5) ensuring sustainable LLMs.

Point-of-Interest (POI) recommendation, pivotal for guiding users to their next interested locale, grapples with the persistent challenge of data sparsity. Whereas knowledge graphs (KGs) have emerged as a favored tool to mitigate the issue, existing KG-based methods tend to overlook two crucial elements: the intention steering users’ location choices and the high-order topological structure within the KG. In this paper, we craft an Intention-aware Knowledge Graph (IKG) that harmonizes users’ visit histories, movement trajectories, and location categories to model user intentions. Building upon IKG, our novel Intention-aware Knowledge Graph Network (IKGN) delves deeper into the POI recommendation by weighing and propagating node embeddings through an attention mechanism, capturing the unique locational intent of each user. A sequential model like GRU is then employed to ensure a comprehensive representation of users’ short- and long-term location preferences. An empirical study on two real-world datasets validates the effectiveness of our proposed IKGN, with it markedly outshining seven benchmark rival models in both Recall and NDCG metrics. The code of IKGN is available at https://github.com/Jungle123456/IKGN.

Temporal link prediction (TLP) is among the most important graph learning tasks, capable of predicting dynamic, time-varying links within networks. The key problem of TLP is how to explore potential link-evolving tendency from the increasing number of links over time. There exist three major challenges toward solving this problem: temporal nonlinear sparsity, weak serial correlation, and discontinuous structural dynamics. In this article, we propose a novel transfer learning model, called DNformer, to predict temporal link sequence in dynamic networks. The structural dynamic evolution is sequenced into consecutive links one by one over time to inhibit temporal nonlinear sparsity. The self-attention of the model is used to capture the serial correlation between the input and output link sequences. Moreover, our structural encoding is designed to obtain changing structures from the consecutive links and to learn the mapping between link sequences. This structural encoding consists of two parts: the node clustering encoding of each link and the link similarity encoding between links. These encodings enable the model to perceive the importance and correlation of links. Furthermore, we introduce a measurement of structural similarity in the loss function for the structural differences of link sequences. The experimental results demonstrate that our model outperforms other state-of-the-art TLP methods such as Transformer, TGAT, and EvolveGCN. It achieves the three highest AUC and four highest precision scores in five different representative dynamic networks problems.

With the personal partial rankings from agents over a subset of alternatives, the goal of preference completion is to infer the agent’s personalized preference over all alternatives including those the agent has not yet handled from uncertain preference of third parties. By combining the partial rankings of the target agent and the partial rankings from third parties to settle some disagreement with three-way preference completion, which includes a general strategy, an optimal strategy, and a pessimistic strategy, it forms the weighted preference graph. Technically, to settle the disagreement and obtain the completed preference of the target agent in the weighted preference graph, maximum likelihood estimation (MLE) under Mallows is proposed and validated theoretically by removing edges with the minimum weight in the weighted preference graph. However, it is not easy to locate the edges with the minimum weight efficiently in a big graph. Hence, an optimal MLE algorithm and three greedy MLE algorithms are proposed to process the MLE. Furthermore, these proposed algorithms are experimentally validated and compared with each other by both the synthetic dataset and the Flixter dataset.

Graph pattern matching (GPM) is widely used in social network analysis, such as expert finding, social group query, and social position detection. Technically, GPM is to find matched subgraphs that meet the requirements of pattern graphs in big social networks. In the application of expert community location, the nodes in the pattern graph and data graph represent expert entities, and the edges represent previous cooperations between them. However, the existing GPM methods focus on shortening the matching time and without considering the preference of the decision maker (DM), which makes it difficult for the DM to find ideal teams from numerous matches to complete the assigned task. In this article, as for the process of graph pattern matching and rematching, with a preferred expert set, i.e., the DM hopes that one or more experts in this set will appear in matched subgraphs, we propose a Dual Simulation-based Edge Sequencing-oriented Semi-Supervised GPM method (DsEs-ssGPM). In addition, considering a preferred expert set and a dispreferred expert set together, the DM hopes that experts in the dispreferred expert set will not appear in final matches, so we have the DsEs-ssGPM+ method. Technically, these DsEs-ssGPM methods conduct the matching process from the preferred expert set during dual simulation-based edge sequencing, and based on the edge sequence, these edges are searched recursively. Especially, as for the rematching process, when the preferred and/or the dispreferred expert sets change continuously, to process the GPM again is unnecessary and it is possible to revise the previous matched results partially with DsEs-ssGPM methods. Experiments on four large datasets demonstrate the effectiveness, efficiency and stability of our proposed DsEs-ssGPM methods, and the necessity of introducing an edge sequencing mechanism.

Negative sequential pattern mining (SPM) is an important SPM research topic. Unlike positive SPM, negative SPM can discover events that should have occurred but have not occurred, and it can be used for financial risk management and fraud detection. However, existing methods generally ignore the repetitions of the pattern and do not consider gap constraints, which can lead to mining results containing a large number of patterns that users are not interested in. To solve this problem, this article discovers frequent one-off negative sequential patterns (ONPs). This problem has the following two characteristics. First, the support is calculated under the one-off condition, which means that any character in the sequence can only be used once at most. Second, the gap constraint can be given by the user. To efficiently mine patterns, this article proposes the ONP-Miner algorithm, which employs depth-first and backtracking strategies to calculate the support. Therefore, ONP-Miner can effectively avoid creating redundant nodes and parent-child relationships. Moreover, to effectively reduce the number of candidate patterns, ONP-Miner uses pattern join and pruning strategies to generate and further prune the candidate patterns, respectively. Experimental results show that ONP-Miner not only improves the mining efficiency but also has better mining performance than the state-of-the-art algorithms. More importantly, ONP mining can find more interesting patterns in traffic volume data to predict future traffic.

Crowdsourcing truth inference aims to assign a correct answer to each task from candidate answers that are provided by crowdsourced workers. A common approach is to generate workers’ reliabilities to represent the quality of answers. Although crowdsourced triples can be converted into various crowdsourced relationships, the available related methods are not effective in capturing these relationships to alleviate the harm to inference that is caused by conflicting answers. In this research, we propose aReliability-drivenMulti-viewGraphEmbedding framework forTruthinference (TiReMGE), which explores multiple crowdsourced relationships by organically integrating worker reliabilities into a graph space that is constructed from crowdsourced triples. Specifically, to create an interactive environment, we propose a reliability-driven initialization criterion for initializing vectors of tasks and workers as interactive carriers of reliabilities. From the perspective of multiple crowdsourced relationships, a multi-view graph embedding framework is proposed for reliability information interaction on a task-worker graph, which encodes latent crowdsourced relationships into vectors of workers and tasks for reliability update and truth inference. A heritable reliability updating method based on the Lagrange multiplier method is proposed to obtain reliabilities that match the quality of workers for interaction by a novel constraint law. Our ultimate goal is to minimize the Euclidean distance between the encoded task vector and the answer that is provided by a worker with high reliability. Extensive experimental results on nine real-world datasets demonstrate that TiReMGE significantly outperforms the nine state-of-the-art baselines.

Truth inference can help solve some difficult problems of data integration in crowdsourcing. Crowdsourced workers are not experts and their labeling ability varies greatly; therefore, in practical applications, it is difficult to determine whether the labels collected from a crowdsourcing platform are correct. This article proposes a novel algorithm called truth inference based on label confidence clustering (TILCC) to improve the quality of integrated labels for the single-choice classification problem in crowdsourcing labeling tasks. We obtain the label confidence via worker reliability, which is calculated from multiple noise labels using a truth discovery method, and then we generate the clustering features and use the K-means algorithm to cluster all the tasks into K different clusters. Each cluster corresponds to a specific class, and the tasks in the cluster are assigned a label. Compared with the performances of six state-of-the-art methods, MV, ZenCrowd, PM, CATD, GLAD, and GTIC, on 12 randomly selected real-world datasets, the performance of our algorithm showed many advantages: no need to set complex parameters, faster running speed, and significantly higher accuracy.

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.

Multi-label data streams such as Web texts and images have been popular on the Web. These data present the characteristics of multiple label, high dimensionality, high volume, high velocity and especial concept drift etc. Thus, multi-label data stream classification is a very challenging and significant task especially in the handling of high-dimensional data with concept drifts. However, this challenge has received little attention from the research community. Therefore, we propose the max-relevance and min-redundancy based algorithm adaptation approach for the efficient and effective classification on multi-label data streams with high-dimensional attributes and concept drifts .11.Source codes and data sets are available at below. https://github.com/peipeilihfut/MLStreamClassificationIn order to reduce the impact from the high-dimensional data with noisy attributes, we first refine the minimal-redundancy-maximal-relevance criterion based on mutual information to select qualified features in multi-label data streams. Secondly, we propose the data distribution based concept drifting detection approach to distinguish concept drifts hidden in data streams. Finally, we build an incremental ensemble classification model for efficiently classifying multi-label data streams. Extensive studies show that our approach can get optimal subsets of features while maintaining a good performance in the multi-label classification, as compared to several state-of-the-art multi-label feature selection algorithms using two efficient multi-label classification methods as base classifiers. Meanwhile, our approach is superior to three well-known multi-label data stream classification approaches in the effectiveness and efficiency.

The aim of sequential pattern mining (SPM) is to discover potentially useful information from a given sequence. Although various SPM methods have been investigated, most of these focus on mining all of the patterns. However, users sometimes want to mine patterns with the same specific prefix pattern, called co-occurrence pattern. Since sequential rule mining can make better use of the results of SPM, and obtain better recommendation performance, this paper addresses the issue of maximal co-occurrence nonoverlapping sequential rule (MCoR) mining and proposes the MCoR-Miner algorithm. To improve the efficiency of support calculation, MCoR-Miner employs depth-first search and backtracking strategies equipped with an indexing mechanism to avoid the use of sequential searching. To obviate useless support calculations for some sequences, MCoR-Miner adopts a filtering strategy to prune the sequences without the prefix pattern. To reduce the number of candidate patterns, MCoR-Miner applies the frequent item and binomial enumeration tree strategies. To avoid searching for the maximal rules through brute force, MCoR-Miner uses a screening strategy. To validate the performance of MCoR-Miner, eleven competitive algorithms were conducted on eight sequences. Our experimental results showed that MCoR-Miner outperformed other competitive algorithms, and yielded better recommendation performance than frequent co-occurrence pattern mining. All algorithms and datasets can be downloaded fromhttps://github.com/wuc567/Pattern-Mining/tree/master/MCoR-Miner.

Hierarchical classification learning, which organizes data categories into a hierarchical structure, is an effective approach for large-scale classification tasks. The high dimensionality of data feature space, represented in hierarchical class structures, is one of the main research challenges. In addition, the class hierarchy often introduces imbalanced class distributions and causes overfitting. In this paper, we propose a feature selection method based on label distribution learning to address the above challenges. The crux is to alleviate the class imbalance problem and learn a discriminative feature subset for hierarchical classification process. Due to correlation between different class categories in the hierarchical tree structure, sibling categories can provide additional supervisory information for each learning sub tasks, which, in turn, alleviates the problem of under-sampling of minority categories. Therefore, we transform hierarchical labels to a hierarchical label distribution to represent this correlation. After that, a discriminative feature subset is selected recursively, by the common features and label-specific feature constraints, to ensure that downstream classification tasks can achieve the best performance. Experiments and comparisons, using seven well-established feature selection algorithms on six real data sets with different degrees of imbalance, demonstrate the superiority of the proposed method.

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

Genealogical knowledge graphs depict the relationships of family networks and the development of family histories. They can help researchers to analyze and understand genealogical data, search for genealogical descendant paths, and explore the origins of a family more easily. However, the heterogenous, autonomous, complex, and evolving natures of genealogical data bring challenges to the development of contemporary genealogical knowledge graph models. Applying existing methods to genealogical data may be improper because general knowledge graph models lack in-depth domain knowledge. In this paper, we propose a genealogical knowledge graph model named Huapu-KG that combines HAO intelligence (human intelligence + artificial intelligence + organizational intelligence) to implement the construction and applications of genealogical knowledge graphs. Furthermore, challenges in constructing genealogical knowledge graphs are demonstrated, and experiments conducted on real-world genealogical datasets verify the feasibility and effectiveness of our proposed model.

Discovering frequent trends in time series is a critical task in data mining. Recently, order-preserving matching was proposed to find all occurrences of a pattern in a time series, where the pattern is a relative order (regarded as a trend) and an occurrence is a sub-time series whose relative order coincides with the pattern. Inspired by the order-preserving matching, the existing order-preserving pattern (OPP) mining algorithm employs order-preserving matching to calculate the support, which leads to low efficiency. To address this deficiency, this paper proposes an algorithm called efficient frequent OPP miner (EFO-Miner) to find all frequent OPPs. EFO-Miner is composed of four parts: a pattern fusion strategy to generate candidate patterns, a matching process for the results of sub-patterns to calculate the support of super-patterns, a screening strategy to dynamically reduce the size of prefix and suffix arrays, and a pruning strategy to further dynamically prune candidate patterns. Moreover, this paper explores the order-preserving rule (OPR) mining and proposes an algorithm called OPR-Miner to discover strong rules from all frequent OPPs using EFO-Miner. Experimental results verify that OPR-Miner gives better performance than other competitive algorithms. More importantly, clustering and classification experiments further validate that OPR-Miner achieves good performance.

Crowdsourcing platforms collect massive dirty claims that are provided by sources for crowdsourced objects, which prompts truth inference to be proposed for crowdsourcing data denoising. Although current graph-based truth-inference methods achieve remarkable success by capturing complex crowdsourcing relationships, they typically suffer from two challenges: 1) They fail to obtain complete crowdsourcing relationships because of the structural limitations of crowdsourcing relationship graphs; 2) Their vector initialization methods for objects and sources are disturbed by claim noise, which limits them from obtaining correct object and source semantics. To cope with these challenges, we propose a novelTruth-Inference method viaReliabilityAggregation (TIRA) on an object-source graph. Specifically, we propose a hierarchical graph auto-encoder to adapt to a reasonable object-source graph, which enables TIRA to capture complete crowdsourcing relationships from multiple perspectives. To better guide TIRA, we design a vector initialization method based on source reliabilities to map the denoised claims to a representation space of objects and sources. Finally, TIRA aggregates the reliability information on an object-source graph to generate object embeddings for truth inference. We conducted extensive experiments on 12 real-world datasets. The experimental results demonstrate that our method significantly outperforms 12 state-of-the-art baselines in terms of the$accuracy$and$weighted\_{F}1$.

Multimodal sentiment analysis (MSA) is a very challenging task due to its complex and complementary interactions between multiple modalities, which can be widely applied into areas of product marketing, public opinion monitoring, and so on. However, previous works directly utilized the features extracted from multimodal data, in which the noise reduction within and among multiple modalities has been largely ignored before multimodal fusion. This paper proposes a multi-level attention map network (MAMN) to filter noise before multimodal fusion and capture the consistent and heterogeneous correlations among multi-granularity features for multimodal sentiment analysis. Architecturally, MAMN is comprised of three modules: multi-granularity feature extraction module, multi-level attention map generation module, and attention map fusion module. The first module is designed to sufficiently extract multi-granularity features from multimodal data. The second module is constructed to filter noise and enhance the representation ability for multi-granularity features before multimodal fusion. And the third module is built to extensibly mine the interactions among multi-level attention maps by the proposed extensible co-attention fusion method. Extensive experimental results on three public datasets show the proposed model is significantly superior to the state-of-the-art methods, and demonstrate its effectiveness on two tasks of document-based and aspect-based MSA tasks.

Multi-label streaming feature selection has attracted extensive attention in diverse big data applications. However, most existing works focused on the scenarios where labels are independent, while ignoring the real scenarios that they may be interdependent and correlated with each other. This paper aims to fill this gap by developing a novel online multi-label streaming feature selection scheme by taking into account the existence of label correlation, known as (OMSFSLC). In our design, we first calculate the correlation degree between labels to obtain the label weight. Then, we integrate the mutual information and the label weight to evaluate the correlation between features and labels. In particular, it consists of three stages: 1) online significance analysis, which can determine the significant features via the correlation degree between the newly arriving features and labels; 2) online relevance analysis, which can obtain relevant features via the mutual information; and 3) online redundancy analysis, which can filter the redundant features for removal via pairwise comparison. We implement our solution and conduct extensive experiments on benchmark datasets for performance evaluations. The experimental results exhibit that OMSFSLCsignificantly outperforms the state-of-the-art methods in terms of effectiveness and efficiency.

Learning with streaming data has attracted extensive research interest in recent years. Existing online learning approaches have specific assumptions regarding data streams, such as requiring fixed or varying feature spaces with explicit patterns and balanced class distributions. While the data streams generated in many real scenarios commonly have arbitrarily incomplete feature spaces and dynamic imbalanced class distributions, making existing approaches be unsuitable for real applications. To address this issue, this paper proposes a novelOnlineLearning fromIncomplete andImbalancedDataStreams (OLI$^{2}$DS) algorithm. OLI$^{2}$DS has a two-fold main idea: 1) it follows the empirical risk minimization principle to identify the most informative features of incomplete feature spaces, and 2) it develops a dynamic cost strategy to handle imbalanced class distributions in real-time by transforming F-measure optimization into a weighted surrogate loss minimization. To evaluate OLI$^{2}$DS, we compare it with state-of-the-art related algorithms in three kinds of experiments. First, we adopt 14 real datasets to simulate three scenarios of incomplete feature spaces, i.e., trapezoidal, feature evolvable, and capricious data streams. Second, based on a benchmark online analyzer, we generate 13 datasets to simulate incomplete data streams with different imbalance ratios. Third, we analyze concept drift in two simulated scenes, i.e., online learning and data stream mining, and verify the adaption of OLI$^{2}$DS on repeated concept drifts and variable imbalance ratios. The results demonstrate that OLI$^{2}$DS achieves a significantly better performance than its rivals. Besides, a real-world case study on movie review classification is conducted to elaborate on our OLI$^{2}$DS algorithm's effectiveness. Code is released athttps://github.com/youdianlong/OLI2DS.

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

Investment promotion refers to the process by which the government uses disposable resources to attract investors to the region for production and business activities. The existing basic mode of attracting investment is to collect information about enterprises and entrepreneurs through manual methods, determine the target enterprise from the list of enterprises, and then attract investment through visits, negotiations, and other methods. As contacting and visiting companies one by one requires huge amounts of manpower and time, the choice of target companies is critical for attracting investments. However, to the best of our knowledge, no study has conducted research from the perspective of knowledge-graph-based recommendation. In this study, we define the problem of target company recommendation in the process of investment promotion, and analyze the characteristics of the problem and the challenges it faces based on the background of the actual problem. Then, a two-tier model for solving this problem is provided from the perspective of knowledge graph reasoning. Aiming at the problem that the knowledge graph will frequently change, the model is designed based on the idea of combining the advantages of global and local link prediction. The experimental results on real-world data demonstrate the effectiveness of the proposed model.

In the era of big data, fragmented knowledge, multisource heterogeneity, and different representation forms of the same entities in various data sources have posed considerable challenges to entity fusion. How to effectively integrate multisource knowledge for the same entities has provoked vast amounts of attention and research from multiple disciplines. Most existing methods for entity fusion can be categorized into two classes: one is to establish an association between the same entities, and the other is to delete duplicate entities after knowledge fusion and create a new fusion entity. However, in these two classes of methods, the former does not achieve true knowledge fusion and semantic interoperability, while the latter may cause irreversible loss of original information. In this paper, we propose a novel entity fusion scheme: Hypernode. Hypernode fuses the same entity in different data sources into a new entity while retaining the original data. We verify the effectiveness of Hypernode on multiple models of link prediction experiments. Several practical application cases illustrate the applicability of Hypernode in data traceability, open domain knowledge fusion, and multi-modal knowledge graph fusion.

In multi-label learning, label correlations commonly exist in the data. Such correlation not only provides useful information, but also imposes significant challenges for multi-label learning. Recently, label-specific feature embedding has been proposed to explore label-specific features from the training data, and uses feature highly customized to the multi-label set for learning. While such feature embedding methods have demonstrated good performance, the creation of the feature embedding space is only based on a single label, without considering label correlations in the data. In this article, we propose to combine multiple label-specific feature spaces, using label correlation, for multi-label learning. The proposed algorithm, mu lti- l abel-specific f eature space e nsemble (MULFE), takes consideration label-specific features, label correlation, and weighted ensemble principle to form a learning framework. By conducting clustering analysis on each label’s negative and positive instances, MULFE first creates features customized to each label. After that, MULFE utilizes the label correlation to optimize the margin distribution of the base classifiers which are induced by the related label-specific feature spaces. By combining multiple label-specific features, label correlation based weighting, and ensemble learning, MULFE achieves maximum margin multi-label classification goal through the underlying optimization framework. Empirical studies on 10 public data sets manifest the effectiveness of MULFE.

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.

Traditional social group analysis mostly uses interaction models, event models, or other social network analysis methods to identify and distinguish groups. This type of method can divide social participants into different groups based on their geographic location, social relationships, and/or related events. However, in some applications, it is necessary to make more specific restrictions on the members and the interactions between members of the group. Generally, Graph Pattern Matching (GPM) technique is used to solve this problem. However, the existing GPM methods rarely consider the rich contextual information of nodes and edges to measure the credibility between members. In this article, first, a social group query problem that needs to consider the trust between members of the group is proposed. Then, to solve this problem, a multi-fuzzy-constrained strong simulation matching model is proposed based on multi-constrained simulation, and a Strong Simulation GPM algorithm (NTSS) based on the exploration of pattern Node Topological ordered sequence is proposed. Aiming at the inefficiency of the NTSS algorithm when pattern graph with multiple nodes with zero in-degree and the problem of repeated calculation of matching edges shared by multiple matching subgraphs, two optimization strategies are proposed. Finally, we conduct verification experiments on the effectiveness and efficiency of the NTSS algorithm and the algorithms with the optimization strategies on four social network datasets in real applications. Experimental results show that the NTSS algorithm is significantly better than the existing multi-constrained GPM algorithm, and the NTSS_Inv_EdgC algorithm, which combines two optimization strategies, greatly improves the efficiency of the NTSS algorithm.

As a novel deep learning model, gcForest has been widely used in various applications. However, current multi-grained scanning of gcForest produces many redundant feature vectors, and this increases the time cost of the model. To screen out redundant feature vectors, we introduce a hashing screening mechanism for multi-grained scanning and propose a model called HW-Forest which adopts two strategies: hashing screening and window screening. HW-Forest employs perceptual hashing algorithm to calculate the similarity between feature vectors in hashing screening strategy, which is used to remove the redundant feature vectors produced by multi-grained scanning and can significantly decrease the time cost and memory consumption. Furthermore, we adopt a self-adaptive instance screening strategy called window screening to improve the performance of our approach, which can achieve higher accuracy without hyperparameter tuning on different datasets. Our experimental results show that HW-Forest has higher accuracy than other models, and the time cost is also reduced.

Nonoverlapping sequential pattern mining is an important type of sequential pattern mining (SPM) with gap constraints, which not only can reveal interesting patterns to users but also can effectively reduce the search space using the Apriori (anti-monotonicity) property. However, the existing algorithms do not focus on attributes of interest to users, meaning that existing methods may discover many frequent patterns that are redundant. To solve this problem, this article proposes a task called nonoverlapping three-way sequential pattern (NTP) mining, where attributes are categorized according to three levels of interest: strong, medium, and weak interest. NTP mining can effectively avoid mining redundant patterns since the NTPs are composed of strong and medium interest items. Moreover, NTPs can avoid serious deviations (the occurrence is significantly different from its pattern) since gap constraints cannot match with strong interest patterns. To mine NTPs, an effective algorithm is put forward, called NTP-Miner, which applies two main steps: support (frequency occurrence) calculation and candidate pattern generation. To calculate the support of an NTP, depth-first and backtracking strategies are adopted, which do not require creating a whole Nettree structure, meaning that many redundant nodes and parent–child relationships do not need to be created. Hence, time and space efficiency is improved. To generate candidate patterns while reducing their number, NTP-Miner employs a pattern join strategy and only mines patterns of strong and medium interest. Experimental results on stock market and protein datasets show that NTP-Miner not only is more efficient than other competitive approaches but can also help users find more valuable patterns. More importantly, NTP mining has achieved better performance than other competitive methods in clustering tasks. Algorithms and data are available at: https://github.com/wuc567/Pattern-Mining/tree/master/NTP-Miner .

Feature selection is one of the core concepts in machine learning, which hugely impacts the model’s performance. For some real-world applications, features may exist in a stream mode that arrives one by one over time, while we cannot know the exact number of features before learning. Online streaming feature selection aims at selecting optimal stream features at each timestamp on the fly. Without the global information of the entire feature space, most of the existing methods select stream features in terms of individual feature information or the comparison of features in pairs. This article proposes a new online scalable streaming feature selection framework from the dynamic decision perspective that is scalable on running time and selected features by dynamic threshold adjustment. Regarding the philosophy of “Thinking-in-Threes”, we classify each new arrival feature as selecting, discarding, or delaying, aiming at minimizing the overall decision risks. With the dynamic updating of global statistical information, we add the selecting features into the candidate feature subset, ignore the discarding features, cache the delaying features into the undetermined feature subset, and wait for more information. Meanwhile, we perform the redundancy analysis for the candidate features and uncertainty analysis for the undetermined features. Extensive experiments on eleven real-world datasets demonstrate the efficiency and scalability of our new framework compared with state-of-the-art algorithms.

Analyzing short texts infers discriminative and coherent latent topics that is a critical and fundamental task since many real-world applications require semantic understanding of short texts. Traditional long text topic modeling algorithms (e.g., PLSA and LDA) based on word co-occurrences cannot solve this problem very well since only very limited word co-occurrence information is available in short texts. Therefore, short text topic modeling has already attracted much attention from the machine learning research community in recent years, which aims at overcoming the problem of sparseness in short texts. In this survey, we conduct a comprehensive review of various short text topic modeling techniques proposed in the literature. We present three categories of methods based on Dirichlet multinomial mixture, global word co-occurrences, and self-aggregation, with example of representative approaches in each category and analysis of their performance on various tasks. We develop the first comprehensive open-source library, called STTM, for use in Java that integrates all surveyed algorithms within a unified interface, benchmark datasets, to facilitate the expansion of new methods in this research field. Finally, we evaluate these state-of-the-art methods on many real-world datasets and compare their performance against one another and versus long text topic modeling algorithm.

Machine learning can provide deep insights into data, allowing machines to make high-quality predictions and having been widely used in real-world applications, such as text mining, visual classification, and recommender systems. However, most sophisticated machine learning approaches suffer from huge time costs when operating on large-scale data. This issue calls for the need of Large-scale Machine Learning (LML), which aims to learn patterns from big data with comparable performance efficiently. In this paper, we offer a systematic survey on existing LML methods to provide a blueprint for the future developments of this area. We first divide these LML methods according to the ways of improving the scalability: 1) model simplification on computational complexities, 2) optimization approximation on computational efficiency, and 3) computation parallelism on computational capabilities. Then we categorize the methods in each perspective according to their targeted scenarios and introduce representative methods in line with intrinsic strategies. Lastly, we analyze their limitations and discuss potential directions as well as open issues that are promising to address in the future.

How to accurately predict unknown quality-of-service (QoS) data based on observed ones is a hot yet thorny issue in Web service-related applications. Recently, a latent factor (LF) model has shown its efficiency in addressing this issue owing to its high accuracy and scalability. An LF model can be improved by identifying user and service neighborhoods based on user and service geographical information. However, such information can be difficult to acquire in most applications with the considerations of information security, identity privacy, and commercial interests in a real system. Besides, the existing LF model-based QoS predictors mostly ignore the reliability of given QoS data where noises commonly exist to cause accuracy loss. To address the above issues, this paper proposes a data-characteristic-aware latent factor (DCALF) model to implement highly accurate QoS predictions, where ‘data-characteristic-aware’ indicates that it can appropriately implement QoS prediction according to the characteristics of given QoS data. Its main idea is two-fold: a) it detects the neighborhoods and noises of users and services based on the dense LFs extracted from the original sparse QoS data, b) it incorporates a density peaks-based clustering method into its modeling process for achieving the simultaneous detections of both neighborhoods and noises of QoS data. With such designs, it precisely represents the given QoS data in spite of their sparsity, thereby achieving highly accurate predictions for unknown ones. Experimental results on two QoS datasets generated by real-world Web services demonstrate that the proposed DCALF model outperforms state-of-the-art QoS predictors, making it highly competitive in addressing the issue of Web service selection and recommendation.

Adverse drug-drug interaction (ADDI) is referred to as a situation where the unpleasant or adverse effects caused by the co-administration of two drugs, which becomes a significant problem for public health. With the increasing availability of healthcare data, many methods are proposed for ADDI prediction. However, these methods usually work in a “nondiscriminatory” manner, i.e., they treat each feature without discrimination and equally incorporate all features into the predictive models. In practice, only a few features are essentially discriminative and relevant to ADDIs. In this paper, we propose a Dependence Guided Discriminative Feature Selection (DGDFS) model for ADDI prediction. In DGDFS, two drug attributes, molecular structure and side effect are adopted to model the adverse interaction among drugs and$l_{2,0}$-norm equality constraints are introduced to select discriminative molecular substructures and side effects for ADDI prediction. Besides, three dependence guided terms, i.e., the dependence between molecular structure and ADDI, the dependence between side effect and ADDI, and the dependence between molecular structure and side effect, are designed to guide feature selection. An iterative algorithm based on the alternating direction method of multipliers is developed for optimization. Experimental results indicate the effectiveness of DGDFS compared with fourteen baselines and its three variants.

Many real-world applications have to face the problem of diversity in data formats and semantics. Currently, how to deal with heterogeneous data effectively is still a big challenge. With the rise of knowledge graphs, more and more applications are built upon graph-like data models, which benefit from flexible schemas and convenient support for relationship queries. We propose a graph-based unifying system for heterogeneous data unification, which helps to (1) transform data in many other formats into graphs, or conversely, from graph to other formats, (2) integrate graph data based on HAO intelligence, which achieves schema integration and entity consolidation, and (3) explore data at different levels via querying the integrated graphs. In this paper, we introduce the overall system architecture, explain in detail the implementation, and display the usage in two practical scenarios.

This paper presents a HAO-Interaction question answering system, which exploits knowledge based question answering (KBQA) technology to quickly obtain an answer path for the input question, and then a creative text generation mechanism to acquire the final answer text. The system also provides visibility of the answer path on the user interface in order to facilitate user understanding. Different from other KBQA systems, HAO-Interaction supports users to incorporate an organizational graph database while accessing all system functionalities. In addition, the answer generation solution implemented in the system does not require any training data. HAO-Interaction keeps low response latency while ensuring a high user satisfaction. The effectiveness of HAO-Interaction has been verified by analyzing thousands of user reviews collected by the system.

Lifelong machine learning (LML) has driven the development of extensive web applications, enabling the learning systems deployed on web servers to deal with a sequence of tasks in an incremental fashion. Such systems can retain knowledge from learned tasks in a knowledge base and seamlessly apply it to improve the future learning. Unfortunately, most existing LML methods require labels in every task, whereas providing persistent human labeling for all future tasks is costly, onerous, error-prone, and hence impractical. Motivated by this situation, we propose a new paradigm named unsupervised lifelong learning with curricula (ULLC), where only one task needs to be labeled for initialization and the system then performs lifelong learning for subsequent tasks in an unsupervised fashion. A main challenge of realizing this paradigm lies in the occurrence of negative knowledge transfer, where partial old knowledge becomes detrimental for learning a given task yet cannot be filtered out by the learner without the help of labels. To overcome this challenge, we draw insights from the learning behaviors of humans. Specifically, when faced with a difficult task that cannot be well tackled by our current knowledge, we usually postpone it and work on some easier tasks first, which allows us to grow our knowledge. Thereafter, once we go back to the postponed task, we are more likely to tackle it well as we are more knowledgeable now. The key idea of ULLC is similar – at any time, a pool of candidate tasks are organized in a curriculum by their distances to the knowledge base. The learner then starts from the closer tasks, accumulates knowledge from learning them, and moves to learn the faraway tasks with a gradually augmented knowledge base. The viability and effectiveness of our proposal are substantiated through extensive empirical studies on both synthetic and real datasets.

Graph edge partitioning, which is essential for the efficiency of distributed graph computation systems, divides a graph into several balanced partitions within a given size to minimize the number of vertices to be cut. Existing graph partitioning models can be classified into two categories: offline and streaming graph partitioning models. The former requires global graph information during the partitioning, which is expensive in terms of time and memory for large-scale graphs. The latter creates partitions based solely on the received graph information. However, the streaming model may result in a lower partitioning quality compared with the offline model. Therefore, this study introduces a Local Graph Edge Partitioning model, which considers only the local information (i.e., a portion of a graph instead of the entire graph) during the partitioning. Considering only the local graph information is meaningful because acquiring complete information for large-scale graphs is expensive. Based on the Local Graph Edge Partitioning model, two local graph edge partitioning algorithms—Two-stage Local Partitioning and Adaptive Local Partitioning—are given. Experimental results obtained on 14 real-world graphs demonstrate that the proposed algorithms outperform rival algorithms in most tested cases. Furthermore, the proposed algorithms are proven to significantly improve the efficiency of the real graph computation system GraphX.

Bike-sharing systems are becoming popular and generate a large volume of trajectory data. In a bike-sharing system, users can borrow and return bikes at different stations. In particular, a bike-sharing system will be affected by weather, the time period, and other dynamic factors, which challenges the scheduling of shared bikes. In this article, a new shared-bike demand forecasting model based on dynamic convolutional neural networks, called SDF , is proposed to predict the demand of shared bikes. SDF chooses the most relevant weather features from real weather data by using the Pearson correlation coefficient and transforms them into a two-dimensional dynamic feature matrix, taking into account the states of stations from historical data. The feature information in the matrix is extracted, learned, and trained with a newly proposed dynamic convolutional neural network to predict the demand of shared bikes in a dynamical and intelligent fashion. The phase of parameter update is optimized from three aspects: the loss function, optimization algorithm, and learning rate. Then, an accurate shared-bike demand forecasting model is designed based on the basic idea of minimizing the loss value. By comparing with classical machine learning models, the weight sharing strategy employed by SDF reduces the complexity of the network. It allows a high prediction accuracy to be achieved within a relatively short period of time. Extensive experiments are conducted on real-world bike-sharing datasets to evaluate SDF. The results show that SDF significantly outperforms classical machine learning models in prediction accuracy and efficiency.

Detecting self-organized coalitions from functional networks is one of the most important ways to uncover functional mechanisms in the brain. Determining these raises well-known technical challenges in terms of scale imbalance, outliers and hard-examples. In this article, we propose a novel self-adaptive skeleton approach to detect coalitions through an approximation method based on probabilistic mixture models. The nodes in the networks are characterized in terms of robust k -order complete subgraphs ( k -clique ) as essential substructures. The k -clique enumeration algorithm quickly enumerates all k -cliques in a parallel manner for a given network. Then, the cliques, from max -clique down to min -clique, of each order k , are hierarchically embedded into a probabilistic mixture model. They are self-adapted to the corresponding structure density of coalitions in the brain functional networks through different order k . All the cliques are merged and evolved into robust skeletons to sustain each unbalanced coalition by eliminating outliers and separating overlaps. We call this the k -CLIque Merging Evolution (CLIME) algorithm. The experimental results illustrate that the proposed approaches are robust to density variation and coalition mixture and can enable the effective detection of coalitions from real brain functional networks. There exist potential cognitive functional relations between the regions of interest in the coalitions revealed by our methods, which suggests the approach can be usefully applied in neuroscientific studies.

Deep learning seeks to achieve excellent performance for representation learning in image datasets. However, supervised deep learning models such as convolutional neural networks require a large number of labeled image data, which is intractable in applications, while unsupervised deep learning models like stacked denoising auto-encoder cannot employ label information. Meanwhile, the redundancy of image data incurs performance degradation on representation learning for aforementioned models. To address these problems, we propose a semi-supervised deep learning framework called stacked convolutional sparse auto-encoder, which can learn robust and sparse representations from image data with fewer labeled data records. More specifically, the framework is constructed by stacking layers. In each layer, higher layer feature representations are generated by features of lower layers in a convolutional way with kernels learned by a sparse auto-encoder. Meanwhile, to solve the data redundance problem, the algorithm of Reconstruction Independent Component Analysis is designed to train on patches for sphering the input data. The label information is encoded using a Softmax Regression model for semi-supervised learning. With this framework, higher level representations are learned by layers mapping from image data. It can boost the performance of the base subsequent classifiers such as support vector machines. Extensive experiments demonstrate the superior classification performance of our framework compared to several state-of-the-art representation learning methods.

Most recent approaches for Text Simplification (TS) have drawn on insights from machine translation to learn simplification rewrites from the monolingual parallel corpus of complex and simple sentences, yet their effectiveness strongly relies on large amounts of parallel sentences. However, there has been a serious problem haunting TS for decades, that is, the availability of parallel TS corpora is scarce or not fit for the learning task. In this paper, we will focus on one especially useful and challenging problem of unsupervised TS without a single parallel sentence. To the best of our knowledge, we present the first unsupervised text simplification system based on phrase-based machine translation system, which leverages a careful initialization of phrase tables and language models. On the widely used WikiLarge and WikiSmall benchmarks, our system respectively obtains 39.08 and 25.12 SARI points, even outperforms some supervised baselines.

When acquiring labels from crowdsourcing platforms, a task may be designed to include multiple labels and the values of each label may belong to a set of various distinct options, which is the so-called multi-class multi-label annotation. To improve the quality of labels, requesters usually let one task be independently completed by a group of heterogeneous crowdsourced workers. Then, the true values of the multiple labels of each task are inferred from these repeated noisy labels. In this paper, we propose two novel probabilistic models MCMLI and MCMLD to address the multi-class multi-label inference problem in crowdsourcing. MCMLI assumes that the labels of each task are mutually independent and MCMLD utilizes a mixture of multiple independently multinoulli distributions to capture the correlation among the labels. Both models can jointly infer multiple true labels of each instance as well as estimate the reliability of crowdsourced workers modeled by a set of confusion matrices with an expectation-maximization algorithm. Experiments with three typical crowdsourcing scenarios and a real-world dataset show that our proposed models significantly outperform existing competitive alternatives. When the labels are strongly correlated, MCMLD substantially outperforms MCMLI. Furthermore, our models can be easily simplified to the one-coin models, which show more advantageous when errors are uniformly distributed, or labels are sparse.

Predictive modeling of networked data finds many real-world applications, such as fraud detection in social networks, drug discovery in biomedical networks, paper topic classification in citation networks, and so forth. Although the advanced machine learning approaches can help build reasonably accurate predictive models, their applicability is immensely hindered by the data labeling tasks, which are onerous, time-consuming, and error-prone. In this paper, we propose a novel active learning paradigm for networked data, named topology-and-content-aware (TACA) active learning, aiming to minimize the number of labels while achieving a desirable level of model accuracy. Overall, TACA advances existing works from two aspects: (1) TACA makes no assumption on the network property, whereas most existing works only perform effectively on a locally consistent network in which linked nodes are expected to share the same labels and (2) TACA generates queries without relying on model performance, thereby enjoying robust predictive results even when noises exist in the queried labels. Both theoretical and empirical evidences are presented, substantiating the effectiveness of and optimism our approach.

Mining vertex-wise interactions in graphs helps reveal useful information in real-world applications, such as bioinformatics networks BioGRID and DrugBank and academic networks DBLP and Arxiv. A main challenge in developing a general learning method for this setting is that each vertex may be associated with features from heterogeneous feature spaces, representing very disparate information. Moreover, features could be raw and low-level, leading to sparse representations. Some solutions in this area treat all feature spaces as equally important and concatenate features from heterogeneous feature spaces into a single feature vector. Others harmonize different feature spaces by respecting their relative significance in mining vertex-wise interactions but requiring construct specialized harmonizing function and/or handcrafting expressive features, both of which entail expert knowledge. Motivated by this observation, we propose a new learning paradigm named Deep Matrix Tri-Factorization (DM3F), which draws insights from deep models: (i) DM3F replaces the linear combination with a neural architecture that can learn an arbitrary harmonizing function from data; and (ii) DM3F allows raw feature inputs and automatically extracts high-level feature representations via a layer-by-layer learning mechanism. These two characteristics of DM3F make it accessible for users without expert knowledge. DM3F includes two orthogonal and complementary models, allowing an ensemble mechanism to optimize its performance during both training and predicting. A theoretical analysis of DM3F reveals that it possesses several desirable properties, including that it strictly generalizes matrix factorization models. We demonstrate the performance of DM3F on two real-world datasets.

Missing value (MV) imputation is a critical preprocessing means for data mining. Nevertheless, existing MV imputation methods are mostly designed for batch processing, and thus are not applicable to streaming data, especially those with poor quality. In this article, we propose a framework, called Real-time and Error-tolerant Missing vAlue ImputatioN (REMAIN), to impute MVs in poor-quality streaming data. Instead of imputing MVs based on all the observed data, REMAIN first initializes the MV imputation model based on a-RANSAC which is capable of detecting and rejecting anomalies in an efficient manner, and then incrementally updates the model parameters upon the arrival of new data to support real-time MV imputation. As the correlations among attributes of the data may change over time in unforseenable ways, we devise a deterioration detection mechanism to capture the deterioration of the imputation model to further improve the imputation accuracy. Finally, we conduct an extensive evaluation on the proposed algorithms using real-world and synthetic datasets. Experimental results demonstrate that REMAIN achieves significantly higher imputation accuracy over existing solutions. Meanwhile, REMAIN improves up to one order of magnitude in time cost compared with existing approaches.

Online streaming feature selection has received extensive attention in the past few years. Existing approaches have a common assumption that the feature space of the fixed data instances increases dynamically without any missing entry. This assumption, however, does not always hold in many real-world applications. For example, in a credit evaluation system, we cannot collect the complete dynamic features for each person and/or enterprise. Motivated by this observation, this paper aims at conducting online feature selection from capricious streaming features, where features flow in one by one with some random missing entries while the number of data instances remains fixed. To do so, we propose a general framework named GF-CSF. The main idea of GF-CSF is to adopt latent factor analysis to preprocess capricious streaming features for completing their missing entries before conducting feature selection. Both theoretical and experimental analyses indicate that GF-CSF can efficiently improve any existing model of online streaming features selection to achieve online capricious streaming features selection.

Automatic knowledge graph construction seeks to build a knowledge graph from unstructured text in a specific domain or cross multiple domains, without human intervention. IEEE ICDM 2019 and ICBK 2019 invited teams from both degree-granting institutions and industrial labs to compete in the 2019 Knowledge Graph Contest by automatically constructing knowledge graphs in at least two different domains. This article reports the outcomes of the Contest. The participants were expected to build a model to extract knowledge represented as triplets from text data and develop a web application to visualize the triplets. Awards were given to five teams. Their models and key techniques used to construct knowledge graphs are summarized.

We propose a generalized optimization framework for detecting anomalous patterns (subgraphs that are interesting or unexpected) in interdependent networks, such as multi-layer networks, temporal networks, networks of networks, and many others. We frame the problem as a non-convex optimization that has a general nonlinear score function and a set of block-structured and non-convex constraints. We develop an effective, efficient, and parallelizable projection-based algorithm, namely Graph Block-structured Gradient Projection (GBGP), to solve the problem. It is proved that our algorithm 1) runs in nearly-linear time on the network size, and 2) enjoys a theoretical approximation guarantee. Moreover, we demonstrate how our framework can be applied to two very practical applications, and we conduct comprehensive experiments to show the effectiveness and efficiency of our proposed algorithm.

Along with the fast development of network applications, network research has attracted more and more attention, where one of the most important research directions is networked multi-label classification. Based on it, unknown labels of nodes can be inferred by known labels of nodes in the neighborhood. As both the scale and complexity of networks are increasing, the problems of previously neglected system overhead are turning more and more seriously. In this article, a novel multi-objective optimization-based networked multi-label seed node selection algorithm (named as MOSS) is proposed to improve both the prediction accuracy for unknown labels of nodes from labels of seed nodes during classification and the system overhead for mining the labels of seed nodes with third parties before classification. Compared with other algorithms on several real networked data sets, MOSS algorithm not only greatly reduces the system overhead before classification but also improves the prediction accuracy during classification.

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

More and more user comments like Tweets are available, which often contain user concerns. In order to meet the demands of users, a good summary generating from multiple documents should consider reader interests as reflected in reader comments. In this article, we focus on how to generate a summary from multi-document documents by considering reader comments, named as reader-aware multi-document summarization (RA-MDS). We present an innovative topic-based method for RA-MDA, which exploits latent topics to obtain the most salient and lessen redundancy summary from multiple documents. Since finding latent topics for RA-MDS is a crucial step, we also present a Heterogeneous-length Text Topic Modeling (HTTM) to extract topics from the corpus that includes both news reports and user comments, denoted as heterogeneous-length texts. In this case, the latent topics extract by HTTM cover not only important aspects of the event, but also aspects that attract reader interests. Comparisons on summary benchmark datasets also confirm that the proposed RA-MDS method is effective in improving the quality of extracted summaries. In addition, experimental results demonstrate that the proposed topic modeling method outperforms existing topic modeling algorithms.

Based on the performance of entire social networks, anomaly analysis for evolving social networks generally ignores the otherness of the evolutionary behaviors of different nodes, such that it is difficult to precisely identify the anomalous evolutionary behaviors of nodes ( AEBN ). Assuming that a node's evolutionary behavior that generates and removes edges normally follows stable evolutionary mechanisms, this study focuses on detecting and assessing AEBN, whose evolutionary mechanisms deviate from their past mechanisms, and proposes a link prediction detection ( LPD ) method and a matrix perturbation assessment ( MPA ) method. LPD describes a node's evolutionary behavior by fitting its evolutionary mechanism, and designs indexes for edge generation and removal to evaluate the extent to which the evolutionary mechanism of a node's evolutionary behavior can be fitted by a link prediction algorithm. Furthermore, it detects AEBN by quantifying the differences among behavior vectors that characterize the node's evolutionary behaviors in different periods. In addition, MPA considers AEBN as a perturbation of the social network structure, and quantifies the effect of AEBN on the social network structure based on matrix perturbation analysis. Extensive experiments on eight disparate real-world networks demonstrate that analyzing AEBN from the perspective of evolutionary mechanisms is important and beneficial.

After entering the big data era, a new term of `big knowledge' has been coined to deal with challenges in mining a mass of knowledge from big data. While researchers used to explore the basic characteristics of big data, we have not seen any studies on the general and essential properties of big knowledge. To fill this gap, this paper studies the concepts of big knowledge, big-knowledge system, and big-knowledge engineering. Ten massiveness characteristics for big knowledge and big-knowledge systems, including massive concepts, connectedness, clean data resources, cases, confidence, capabilities, cumulativeness, concerns, consistency, and completeness, are defined and explored. Based on these characteristics, a comprehensive investigation is conducted on some large-scale knowledge engineering projects, including the Fifth Comprehensive Traffic Survey in Shanghai, the China's Xia-Shang-Zhou Chronology Project, the Troy and Trojan War Project, and the International Human Genome Project, as well as the online free encyclopedia Wikipedia. We also investigate the recent research efforts on knowledge graphs, where they are analyzed to determine which ones can be considered as big knowledge and big-knowledge systems. Further, a definition of big-knowledge engineering and its life cycle paradigm is presented. All of these projects are accordingly checked to determine whether they belong to big-knowledge engineering projects. Finally, the perspectives of big knowledge research are discussed.

With the crowdsourcing of small tasks becoming easier, it is possible to obtain non-expert/imperfect labels at low cost. With low-cost imperfect labeling, it is straightforward to collect multiple labels for the same data items. This paper proposes strategies of utilizing these multiple labels for supervised learning, based on two basic ideas: majority voting and pairing. We show several interesting results based on our experiments. (i) The strategies based on the majority voting idea work well under the situation where the certainty level is high. (ii) On the contrary, the pairing strategies are more preferable under the situation where the certainty level is low. (iii) Among the majority voting strategies, soft majority voting can reduce the bias and roughness, and perform better than majority voting. (iv) Pairing can completely avoid the bias by having both sides (potentially correct and incorrect/noisy information) considered. Beta estimation is applied to reduce the impact of the noise in pairing. Our experimental results show that pairing with Beta estimation always performs well under different certainty levels. (v) All strategies investigated are labeling quality agnostic strategies for real-world applications, and some of them perform better than or at least very close to the gnostic strategies.

To address the data sparsity problem in short text understanding, various alternative topic models leveraging word embeddings as background knowledge have been developed recently. However, existing models combine auxiliary information and topic modeling in a straightforward way without considering human reading habits. In contrast, extensive studies have proven that it is full of potential in textual analysis by taking into account human attention. Therefore, we propose a novel model, Attentional Segmentation based Topic Model (ASTM), to integrate both word embeddings as supplementary information and an attention mechanism that segments short text documents into fragments of adjacent words receiving similar attention. Each segment is assigned to a topic and each document can have multiple topics. We evaluate the performance of our model on three real-world short text datasets. The experimental results demonstrate that our model outperforms the state-of-the-art in terms of both topic coherence and text classification.

We define Big Wisdom with a HAO/BIBLE framework, which integrates human intelligence (HI), artificial intelligence (AI) and organizational/business intelligence (0/BI) with Bigdata analytics in large environments, for industrial intelligence in organizational activities. Big Wisdom starts with Bigdata, discovers Big Knowledge, and facilitates human and machine synergism for complex problem solving. When the HAO/BIBLE framework is applied to a regular (non-Bigdata) environment, it becomes the well-known PEAS agent structure, and when the knowledge graph in HAO/BIBLE relies on domain expertise (rather than Big Knowledge), HAO/BIBLE serves as an expert system.

Current efforts on multi-label learning generally assume that the given labels of training instances are noise-free. However, obtaining noise-free labels is quite difficult and often impractical, and the presence of noisy labels may compromise the performance of multi-label learning. Partial multi-label learning (PML) addresses the scenario in which each instance is annotated with a set of candidate labels, of which only a subset corresponds to the ground-truth. The PML problem is more challenging than partial-label learning, since the latter assumes that only one label is valid and may ignore the correlation among candidate labels. To tackle the PML challenge, we introduce a feature induced PML approach called fPML, which simultaneously estimates noisy labels and trains multi-label classifiers. In particular, fPML simultaneously factorizes the observed instance-label association matrix and the instance-feature matrix into low-rank matrices to achieve coherent low-rank matrices from the label and the feature spaces, and a low-rank label correlation matrix as well. The low-rank approximation of the instance-label association matrix is leveraged to estimate the association confidence. To predict the labels of unlabeled instances, fPML learns a matrix that maps the instances to labels based on the estimated association confidence. An empirical study on public multi-label datasets with injected noisy labels, and on archived proteomic datasets, shows that fPML can more accurately identify noisy labels than related solutions, and consequently can achieve better performance on predicting labels of instances than competitive methods.

We study the problem of active learning for multi-class classification on large-scale datasets. In this setting, the existing active learning approaches built upon uncertainty measures are ineffective for discovering unknown regions, and those based on expected error reduction are inefficient owing to their huge time costs. To overcome the above issues, this paper proposes a novel query selection criterion called approximated error reduction (AER). In AER, the error reduction of each candidate is estimated based on an expected impact over all datapoints and an approximated ratio between the error reduction and the impact over its nearby datapoints. In particular, we utilize hierarchical anchor graphs to construct the candidate set as well as the nearby datapoint sets of these candidates. The benefit of this strategy is that it enables a hierarchical expansion of candidates with the increase of labels, and allows us to further accelerate the AER estimation. We finally introduce AER into an efficient semi-supervised classifier for scalable active learning. Experiments on publicly available datasets with the sizes varying from thousands to millions demonstrate the effectiveness of our approach.

When acquiring labels from crowdsourcing platforms, a task may be designed to include multiple labels and the values of each label may belong to a set of various distinct options, which is the so-called multi-class multi-label annotation. To improve the quality of labels, one task is independently completed by a group of heterogeneous crowdsourced workers. Then, the true values of the multiple labels of each task are inferred from these repeated noisy labels. In this paper, we propose a novel probabilistic method, which includes a multi-class multi-label dependency (MCMLD) model, to address this problem. The proposed method assumes that the label-correlation exists in both unknown true labels and noisy crowdsourced labels. Thus, it introduces a mixture of multiple independently multinoulli distributions to capture the correlation among the labels. Finally, the unknown true values of the multiple labels of each task, together with a set of confusion matrices modeling the reliability of the workers, can be jointly inferred through an EM algorithm. Experiments with three simulated typical crowdsourcing scenarios and a real-world dataset consistently show that our proposed MCMLD method significantly outperforms several competitive alternatives. Furthermore, if the labels are strongly correlated, the advantage of MCMLD will be more remarkable.

A huge amount of texts available on the World Wide Web presents an unprecedented opportunity for information extraction (IE). One important assumption in IE is that frequent extractions are more likely to be correct. Sparse IE is hence a challenging task because no matter how big a corpus is, there are extractions supported by only a small amount of evidence in the corpus. However, there is limited research on sparse IE, especially in the assessment of the validity of sparse IEs. Motivated by this, we introduce a lightweight, explicit semantic approach for assessing sparse IE. 1 We first use a large semantic network consisting of millions of concepts, entities, and attributes to explicitly model the context of any semantic relationship. Second, we learn from three semantic contexts using different base classifiers to select an optimal classification model for assessing sparse extractions. Finally, experiments show that as compared with several state-of-the-art approaches, our approach can significantly improve the F -score in the assessment of sparse extractions while maintaining the efficiency.

No abstract available.

Community discovery plays an essential role in the analysis of the structural features of complex networks. Since online networks grow increasingly large and complex over time, the methods traditionally used for community discovery cannot efficiently handle large-scale network data. This introduces the important problem of how to effectively and efficiently discover large communities from complex networks. In this study, we propose a fast parallel community discovery model called picaso (a parallel community discovery algorithm based on approximate optimization), which integrates two new techniques: (1) Mountain model, which works by utilizing graph theory to approximate the selection of nodes needed for merging, and (2) Landslide algorithm, which is used to update the modularity increment based on the approximated optimization. In addition, the GraphX distribution computing framework is employed in order to achieve parallel community detection over complex networks. In the proposed model, clustering on modularity is used to initialize the Mountain model as well as to compute the weight of each edge in the networks. The relationships among the communities are then simplified by applying the Landslide algorithm, which allows us to obtain the community structures of the complex networks. Extensive experiments were conducted on real and synthetic complex network datasets, and the results demonstrate that the proposed algorithm can outperform the state of the art methods, in effectiveness and efficiency, when working to solve the problem of community detection. Moreover, we demonstratively prove that overall time performance approximates to four times faster than similar approaches. Effectively our results suggest a new paradigm for large-scale community discovery of complex networks.

Multi-instance learning (MIL) is a useful tool for tackling labeling ambiguity in learning because it allows a bag of instances to share one label. Bag mapping transforms a bag into a single instance in a new space via instance selection and has drawn significant attention recently. To date, most existing work is based on the original space, using all instances inside each bag for bag mapping, and the selected instances are not directly tied to an MIL objective. As a result, it is difficult to guarantee the distinguishing capacity of the selected instances in the new bag mapping space. In this paper, we propose a discriminative mapping approach for multi-instance learning (MILDM) that aims to identify the best instances to directly distinguish bags in the new mapping space. Accordingly, each instance bag can be mapped using the selected instances to a new feature space, and hence any generic learning algorithm, such as an instance-based learning algorithm, can be used to derive learning models for multi-instance classification. Experiments and comparisons on eight different types of real-world learning tasks (including 14 data sets) demonstrate that MILDM outperforms the state-of-the-art bag mapping multi-instance learning approaches. Results also confirm that MILDM achieves balanced performance between runtime efficiency and classification effectiveness.

The contents generated from different data sources are usually non-uniform, such as long texts produced by news websites and short texts produced by social media. Uncovering topics over large-scale non-uniform texts becomes an important task for analyzing network data. However, the existing methods may fail to recognize the difference between long texts and short texts. To address this problem, we propose a novel topic modeling method for non-uniform text topic modeling referred to as self-adaptive sliding window based topic model (SSWTM). Specifically, in all kinds of texts, relevant words have a closer distance to each other than irrelevant words. Based on this assumption, SSWTM extracts relevant words by using a selfadaptive sliding window and models on the whole corpus. The self-adaptive sliding window can filter noisy information and change the size of a window according to different text contents. Experimental results on short texts from Twitter and long texts from Chinese news articles demonstrate that our method can discover more coherent topics for non-uniform texts compared with state-of-the-art methods.

With the rapid development of big data analytics, mobile computing, Internet of Things, cloud computing, and social networking, cyberspace has expanded to a cross-fused and ubiquitous space made up of human beings, things, and information. Internet applications have evolved from Web 1.0 to Web 2.0 and Web 3.0, and web information has seen an explosive growth, which is strongly promoting the advent of a global era of big data. In this ubiquitous cyberspace, traditional search engines can no longer fully satisfy the evolving needs of various types of users. Therefore, search engines must make completely innovative, revolutionary changes for the next generation of search, which is referred to as “big search”. This paper first studies the development needs of big search. Then, big search is defined, and the 5S properties (Sourcing, Sensing, Synthesizing, Solution, and Security) of big search, which are different from those of traditional search engines, are elaborated. Also, the paper provides a system architecture for big search, explores the key technologies that support the 5S properties, and describes potential application fields of big search technology. Finally, the research opportunities of big search are discussed.

Social networking services have been prevalent at many online communities such as Twitter.com and Weibo.com, where millions of users keep interacting with each other every day. One interesting and important problem in the social networking services is to rank users based on their vitality in a timely fashion. An accurate ranking list of user vitality could benefit many parties in social network services such as the ads providers and site operators. Although it is very promising to obtain a vitality-based ranking list of users, there are many technical challenges due to the large scale and dynamics of social networking data. In this paper, we propose a unique perspective to achieve this goal, which is quantifying user vitality by analyzing the dynamic interactions among users on social networks. Examples of social network include but are not limited to social networks in microblog sites and academical collaboration networks. Intuitively, if a user has many interactions with his friends within a time period and most of his friends do not have many interactions with their friends simultaneously, it is very likely that this user has high vitality. Based on this idea, we develop quantitative measurements for user vitality and propose our first algorithm for ranking users based vitality. Also, we further consider the mutual influence between users while computing the vitality measurements and propose the second ranking algorithm, which computes user vitality in an iterative way. Other than user vitality ranking, we also introduce a vitality prediction problem, which is also of great importance for many applications in social networking services. Along this line, we develop a customized prediction model to solve the vitality prediction problem. To evaluate the performance of our algorithms, we collect two dynamic social network data sets. The experimental results with both data sets clearly demonstrate the advantage of our ranking and prediction methods.

Several models have been proposed to cope with the rapidly increasing size of data, such as Anchor Graph Regularization (AGR). The AGR approach significantly accelerates graph-based learning by exploring a set of anchors. However, when a dataset becomes much larger, AGR still faces a big graph which brings dramatically increasing computational costs. To overcome this issue, we propose a novel Hierarchical Anchor Graph Regularization (HAGR) approach by exploring multiple-layer anchors with a pyramid-style structure. In HAGR, the labels of datapoints are inferred from the coarsest anchors layer by layer in a coarse-to-fine manner. The label smoothness regularization is performed on all datapoints, and we demonstrate that the optimization process only involves a small-size reduced Laplacian matrix. We also introduce a fast approach to construct our hierarchical anchor graph based on an approximate nearest neighbor search technique. Experiments on million-scale datasets demonstrate the effectiveness and efficiency of the proposed HAGR approach over existing methods. Results show that the HAGR approach is even able to achieve a good performance within 3 minutes in an 8-million-example classification task.

Graph classification is an important tool for analyzing data with structure dependency, where subgraphs are often used as features for learning. In reality, the dimension of the subgraphs crucially depends on the threshold setting of the frequency support parameter, and the number may become extremely large. As a result, subgraphs may be incrementally discovered to form a feature stream and require the underlying graph classifier to effectively discover representative subgraph features from the subgraph feature stream. In this paper, we propose a primal-dual incremental subgraph feature selection algorithm (ISF) based on a max-margin graph classifier. The ISF algorithm constructs a sequence of solutions that are both primal and dual feasible. Each primal-dual pair shrinks the dual gap and renders a better solution for the optimal subgraph feature set. To avoid bias of ISF algorithm on short-pattern subgraph features, we present a new incremental subgraph join feature selection algorithm (ISJF) by forcing graph classifiers to join short-pattern subgraphs and generate long-pattern subgraph features. We evaluate the performance of the proposed models on both synthetic networks and real-world social network data sets. Experimental results demonstrate the effectiveness of the proposed methods.

Short text stream classification is a challengingand significant task due to the characteristics of short length, weak signal, high velocity and especially topic drifting in short text stream. However, this challenge has received little attention from the research community. Motivated by this, we propose a new feature extension approach for short text stream classification using a large scale, general purpose semantic network obtained from a web corpus. Our approach is built on an incremental ensemble classification model. First, in terms of the open semantic network, we introduce more semantic contexts in short texts to make up of the data sparsity. Meanwhile, we disambiguate terms by their semantics to reduce the noise impact. Second, to effectively track hidden topic drifts, we propose a concept cluster based topic drifting detection method. Finally, extensive experiments demonstratethat our approach can detect topic drifts effectively compared to several well-known concept drifting detection methods in data streams. Meanwhile, our approach can perform best in the classification of text data streams compared to several stateof-the-art short text classification approaches.

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

A representative skylinecontains$k$skyline points that can represent its corresponding full skyline. The existing measuring criteria of$k$representative skylines are specifically designed for static data, and they cannot effectively handle streaming data. In this paper, we focus on the problem of calculating the$k$representative skyline over data streams. First, we propose a new criterion to choose$k$skyline points as the$k$representative skyline for data stream environments, termed the$k$largest dominance skyline ($k$-LDS), which is representative to the entire data set and is highly stable over the streaming data. Second, we propose an efficient exact algorithm, called Prefix-based Algorithm (PBA), to solve the$k$-LDS problem in a 2-dimensional space. The time complexity of PBA is only$\mathcal {O}((M-k)\times k)$where$M$is the size of the full skyline set. Third, the$k$-LDS problem for a$d$-dimensional ($d\ge 3$) space turns out to be very complex. Therefore, a greedy algorithm is designed to answer$k$-LDS queries. To further accelerate the calculation, we propose a$\epsilon$-greedy algorithm which can achieve an approximate factor of$\frac{1}{(1+\epsilon)}(1-\frac{1}{\sqrt{e}})$. Experimental results on both synthetic and real-world data show that our$k$-LDS significantly outperforms its competitors in data stream environments. Furthermore, we demonstrate that the proposed$\epsilon$-greedy algorithm can solve$k$-LDS efficiently and with a competitive accuracy.

Binary Relevance is a well-known framework for multi-label classification, which considers each class label as a binary classification problem. Many existing multi-label algorithms are constructed within this framework, and utilize identical data representation in the discrimination of all the class labels. In multi-label classification, however, each class label might be determined by some specific characteristics of its own. In this paper, we seek to learn label-specific data representation for each class label, which is composed of label-specific features. Our proposed method LLSF can not only be utilized for multi-label classification directly, but also be applied as a feature selection method for multi-label learning and a general strategy to improve multi-label classification algorithms comprising a number of binary classifiers. Inspired by the research works on modeling high-order label correlations, we further extend LLSF to learn class-Dependent Labels in a sparse stackingway, denoted as LLSF-DL. It incorporates both second-order- and high-order label correlations. A comparative study with the state-of-the-art approaches manifests the effectiveness and efficiency of our proposed methods.

Many graph-based semi-supervised learning methods for large datasets have been proposed to cope with the rapidly increasing size of data, such as Anchor Graph Regularization (AGR). This model builds a regularization framework by exploring the underlying structure of the whole dataset with both datapoints and anchors. Nevertheless, AGR still has limitations in its two components: (1) in anchor graph construction, the estimation of the local weights between each datapoint and its neighboring anchors could be biased and relatively slow; and (2) in anchor graph regularization, the adjacency matrix that estimates the relationship between datapoints, is not sufficiently effective. In this paper, we develop an Efficient Anchor Graph Regularization (EAGR) by tackling these issues. First, we propose a fast local anchor embedding method, which reformulates the optimization of local weights and obtains an analytical solution. We show that this method better reconstructs datapoints with anchors and speeds up the optimizing process. Second, we propose a new adjacency matrix among anchors by considering the commonly linked datapoints, which leads to a more effective normalized graph Laplacian over anchors. We show that, with the novel local weight estimation and normalized graph Laplacian, EAGR is able to achieve better classification accuracy with much less computational costs. Experimental results on several publicly available datasets demonstrate the effectiveness of our approach.

In Big Data applications, massive datasets with huge numbers of observations are frequently encountered. To deal with such massive datasets, a divide-and-conquer scheme (e.g., MapReduce) is often used for the analysis of Big Data. With such a strategy, a large dataset (e.g., a centralized real database or a virtual database with distributed data sources) is first divided into smaller manageable segments; the final output is then aggregated from the individual outputs of the segments. Despite its popularity in practice, it remains largely unknown whether such a distributive strategy provides valid theoretical inferences to the original data. In this paper, we address this fundamental issue for the distributed kernel regression (DKR) problem, where the algorithmic feasibility is measured by the generalization performance of the resulting estimator. To justify DKR, a uniform convergence rate is needed for bounding the generalization error over the individual outputs, which brings new and challenging issues in the Big Data setup. Using a sample dependent kernel dictionary, we show that, with proper data segmentation, DKR leads to an estimator that is generalization consistent to the unknown regression function. This result theoretically justifies DKR and sheds light on more advanced distributive algorithms for processing Big Data. The promising performance of the method is supported by both simulation and real data examples.

Due to low quality of crowdsourced labelers, the integrated label of each example is usually inferred from its multiple noisy labels provided by different labelers. This paper proposes a novel algorithm, Ground Truth Inference using Clustering (GTIC), to improve the quality of integrated labels for multi-class labeling. For a K labeling case, GTIC utilizes the multiple noisy label sets of examples to generate features. Then, it uses a K-Means algorithm to cluster all examples into K different groups, each of which is mapped to a specific class. Examples in the same cluster are assigned a corresponding class label. We compare GTIC with four existing multi-class ground truth inference algorithms, majority voting (MV), Dawid & Skene's (DS), ZenCrowd (ZC) and Spectral DS (SDS), on one synthetic and eight real-world datasets. Experimental results show that the performance of GTIC is significantly superior to the others in terms of both accuracy and M-AUC. Besides, the running time of GTIC is about twenty times faster than EM-based complicated inference algorithms.

In this paper, we study a new problem of continuous learning from doubly-streaming data where both data volume and feature space increase over time. We refer to the doubly-streaming data as trapezoidal data streams and the corresponding learning problem as online learning from trapezoidal data streams. The problem is challenging because both data volume and data dimension increase over time, and existing online learning[1],[2], online feature selection[3], and streaming feature selection algorithms[4],[5]are inapplicable. We propose a new Online Learning with Streaming Features algorithm (OL$_{SF}$for short) and its two variants, which combine online learning[1],[2]and streaming feature selection[4],[5]to enable learning from trapezoidal data streams with infinite training instances and features. When a new training instance carrying new features arrives, a classifier updates the existing features by following the passive-aggressive update rule[2]and updates the new features by following the structural risk minimization principle. Feature sparsity is then introduced by using the projected truncation technique. We derive performance bounds of the OL$_{SF}$algorithm and its variants. We also conduct experiments on real-world data sets to show the performance of the proposed algorithms.

This paper proposes a novel framework that introduces noise correction techniques to further improve label quality after ground truth inference in crowdsourcing. In the framework, an adaptive voting noise correction algorithm (AVNC) is proposed to identify and correct the most likely noises with the help of estimated qualities of labelers provided by the ground truth inference. The experimental results on two real-world datasets show that (1) the framework can improve label quality regardless of inference algorithms, especially under the circumstance that each example has a few noisy labels; and (2) since the algorithm AVNC considers both the number of and the probability of potential noises, it outperforms a baseline noise correction algorithm.

Binary relevance (BR) is a well-known framework for multi-label classification. It decomposes multi-label classification into binary (one-vs-rest) classification subproblems, one for each label. The BR approach is a simple and straightforward way for multi-label classification, but it still has several drawbacks. First, it does not consider label correlations. Second, each binary classifier may suffer from the issue of class-imbalance. Third, it can become computationally unaffordable for data sets with many labels. Several remedies have been proposed to solve these problems by exploiting label correlations between labels and performing label space dimension reduction. Meanwhile, inconsistency, another potential drawback of BR, is often ignored by researchers when they construct multi-label classification models. Inconsistency refers to the phenomenon that if an example belongs to more than one class label, then during the binary training stage, it can be considered as both positive and negative example simultaneously. This will mislead binary classifiers to learn suboptimal decision boundaries. In this paper, we seek to solve this problem by learning label specific features for each label. We assume that each label is only associated with a subset of features from the original feature set, and any two strongly correlated class labels can share more features with each other than two uncorrelated or weakly correlated ones. The proposed method can be applied as a feature selection method for multi-label learning and a general strategy to improve multi-label classification algorithms comprising a number of binary classifiers. Comparison with the state-of-the-art approaches manifests competitive performance of our proposed method.

We study a new problem of learning from doubly-streaming data where both data volume and feature space increase over time. We refer to the problem as mining trapezoidal data streams. The problem is challenging because both data volume and feature space are increasing, to which existing online learning, online feature selection and streaming feature selection algorithms are inapplicable. We propose a new Sparse Trapezoidal Streaming Data mining algorithm (STSD) and its two variants which combine online learning and online feature selection to enable learning trapezoidal data streams with infinite training instances and features. Specifically, when new training instances carrying new features arrive, the classifier updates the existing features by following the passive-aggressive update rule used in online learning and updates the new features with the structural risk minimization principle. Feature sparsity is also introduced using the projected truncation techniques. Extensive experiments on the demonstrated UCI data sets show the performance of the proposed algorithms.

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

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

The key task in developing graph-based learning algorithms is constructing an informative graph to express the contextual information of a data manifold. Since traditional graph construction methods are sensitive to noise and less datum-adaptive to changes in density, a new method called$\ell^1$-graph was proposed recently. A graph construction needs to have two important properties: sparsity and locality. The$\ell^1$-graph has a strong sparsity property, but a weak locality property. Thus, we propose a new method of constructing an informative graph using auto-grouped sparse regularization based on the$\ell^1$-graph, which is called as Group Sparse graph (GS-graph). We also show how to efficiently construct a GS-graph in reproducing kernel Hilbert space with the kernel trick. The new methods, the GS-graph and its kernelized version (KGS-graph), have the same noise-insensitive property as that of$\ell^1$-graph and also can successively preserve the properties of sparsity and locality simultaneously. Furthermore, we integrate the proposed graph with several graph-based learning algorithms to demonstrate the effectiveness of our method. The empirical studies on benchmarks show that the proposed methods outperform the$\ell^1$-graph and other traditional graph construction methods in various learning tasks.

Measuring semantic similarity between two terms is essential for a variety of text analytics and understanding applications. Currently, there are two main approaches for this task, namely the knowledge based and the corpus based approaches. However, existing approaches are more suitable for semantic similarity between words rather than the more general multi-word expressions (MWEs), and they do not scale very well. Contrary to these existing techniques, we propose an efficient and effective approach for semantic similarity using a large scale semantic network. This semantic network is automatically acquired from billions of web documents. It consists of millions of concepts, which explicitly model the context of semantic relationships. In this paper, we first show how to map two terms into the concept space, and compare their similarity there. Then, we introduce a clustering approach to orthogonalize the concept space in order to improve the accuracy of the similarity measure. Finally, we conduct extensive studies to demonstrate that our approach can accurately compute the semantic similarity between terms of MWEs and with ambiguity, and significantly outperforms 12 competing methods under Pearson Correlation Coefficient. Meanwhile, our approach is much more efficient than all competing algorithms, and can be used to compute semantic similarity in a large scale.

An open question in ensemble-based active learning is how to choose one classifier type, or appropriate combinations of multiple classifier types, to construct ensembles for a given task. While existing approaches typically choose one classifier type, this paper presents a method that trains and adapts multiple instances of multiple classifier types toward an appropriate ensemble during active learning. The method is termed adaptive heterogeneous ensembles (henceforth referred to as AHE). Experimental evaluations show that AHE constructs heterogeneous ensembles that outperform homogeneous ensembles composed of any one of the classifier types, as well as bagging, boosting and the random subspace method with random sampling. We also show in this paper that the advantage of AHE over other methods is increased if (1) the overall size of the ensemble also adapts during learning; and (2) the target data set is composed of more than two class labels. Through analysis we show that the AHE outperforms other methods because it automatically discovers complementary classifiers: for each data instance in the data set, instances of the classifier type best suited for that data point vote together, while instances of the other, inappropriate classifier types disagree, thereby producing a correct overall majority vote.

Visual classification has attracted considerable research interests in the past decades. In this paper, a novel ℓ1-hypergraph model for visual classification is proposed. Hypergraph learning, as a natural extension of graph model, has been widely used in many machine learning tasks. In previous work, hypergraph is usually constructed by attribute-based or neighborhood-based methods. That is, a hyperedge is generated by connecting a set of samples sharing a same feature attribute or in a neighborhood. However, these methods are unable to explore feature space globally or sensitive to noises. To address these problems, we propose a novel hypergraph construction approach that leverages sparse representation to generate hyperedges and learns the relationship among hyperedges and their vertices. First, for each sample, a hyperedge is generated by regarding it as the centroid and linking it as well as its nearest neighbors. Then, the sparse representation method is applied to represent the centroid vertex by other vertices within the same hyperedge. The vertices with zero coefficients are removed from the hyperedge. Finally, the representation coefficients are used to define the incidence relation between the hyperedge and the vertices. In our approach, we also optimize the hyperedge weights to modulate the effects of different hyperedges. We leverage the prior knowledge on the hyperedges so that the hyperedges sharing more vertices can have closer weights, where a graph Laplacian is used to regularize the optimization of the weights. Our approach is named ℓ1-hypergraph since the ℓ1sparse representation is employed in the hypergraph construction process. The method is evaluated on various visual classification tasks, and it demonstrates promising performance.

Online selection of dynamic features has attracted intensive interest in recent years. However, existing online feature selection methods evaluate features individually and ignore the underlying structure of a feature stream. For instance, in image analysis, features are generated in groups which represent color, texture, and other visual information. Simply breaking the group structure in feature selection may degrade performance. Motivated by this observation, we formulate the problem as an online group feature selection. The problem assumes that features are generated individually but there are group structures in the feature stream. To the best of our knowledge, this is the first time that the correlation among streaming features has been considered in the online feature selection process. To solve this problem, we develop a novel online group feature selection method named OGFS. Our proposed approach consists of two stages: online intra-group selection and online inter-group selection. In the intra-group selection, we design a criterion based on spectral analysis to select discriminative features in each group. In the inter-group selection, we utilize a linear regression model to select an optimal subset. This two-stage procedure continues until there are no more features arriving or some predefined stopping conditions are met. Finally, we apply our method to multiple tasks including image classification and face verification. Extensive empirical studies performed on real-world and benchmark data sets demonstrate that our method outperforms other state-of-the-art online feature selection methods.

Software companies spend over 45 percent of cost in dealing with software bugs. An inevitable step of fixing bugs is bug triage, which aims to correctly assign a developer to a new bug. To decrease the time cost in manual work, text classification techniques are applied to conduct automatic bug triage. In this paper, we address the problem of data reduction for bug triage, i.e., how to reduce the scale and improve the quality of bug data. We combine instance selection with feature selection to simultaneously reduce data scale on the bug dimension and the word dimension. To determine the order of applying instance selection and feature selection, we extract attributes from historical bug data sets and build a predictive model for a new bug data set. We empirically investigate the performance of data reduction on totally 600,000 bug reports of two large open source projects, namely Eclipse and Mozilla. The results show that our data reduction can effectively reduce the data scale and improve the accuracy of bug triage. Ourwork provides an approach to leveraging techniques on data processing to form reduced and high-quality bug data in software development and maintenance.

It can be easy to collect multiple noisy labels for the same object via Internet-based crowdsourcing systems. Labelers may have bias when labeling, due to lacking expertise, dedication, and personal preference. These cause Imbalanced Multiple Noisy Labeling. In most cases, we have no information about the labeling qualities of labelers and the underlying class distributions. It is important to design agnostic solutions to utilize these noisy labels for supervised learning. We first investigate how imbalanced multiple noisy labeling affects the class distributions of training sets and the performance of classification. Then, an agnostic algorithm Positive LAbel frequency Threshold (PLAT) is proposed to deal with the imbalanced labeling issue. Simulations on eight UCI data sets with different underlying class distributions show that PLAT not only effectively deals with the imbalanced multiple noisy labeling problems that off-the-shelf agnostic methods cannot cope with, but also performs nearly the same as majority voting under the circumstances without imbalance. We also apply PLAT to eight real-world data sets with imbalanced labels collected from Amazon Mechanical Turk, and the experimental results show that PLAT is efficient and better than other ground truth inference algorithms.

Finding good keyphrases for a document is beneficial for many applications, such as text summarization, browsing, and indexing. In this paper, we propose a sequential pattern mining based document-specific keyphrase extraction method. Our key innovation is to use wildcards (or gap constraints) to help extract sequential patterns, where the flexible wildcard constraints within a pattern can capture semantic relationships between words. To achieve this goal, we regard each single document as a sequential dataset, and propose an efficient algorithm to mine sequential patterns with wildcard and one-off conditions that allows important keyphrases to be captured during the mining process. For each extracted keyphrase candidate, we use some statistical pattern features to characterize it. A supervised learning classifier is trained to identify keyphrases from a test document. Comparisons on keyphrase benchmark datasets confirm that our document-specific keyphrase extraction method is effective in improving the quality of extracted keyphrases.

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

Big Data concern large-volume, complex, growing data sets with multiple, autonomous sources. With the fast development of networking, data storage, and the data collection capacity, Big Data are now rapidly expanding in all science and engineering domains, including physical, biological and biomedical sciences. This paper presents a HACE theorem that characterizes the features of the Big Data revolution, and proposes a Big Data processing model, from the data mining perspective. This data-driven model involves demand-driven aggregation of information sources, mining and analysis, user interest modeling, and security and privacy considerations. We analyze the challenging issues in the data-driven model and also in the Big Data revolution.

In some real world applications, like information retrieval and data classification, we often are confronted with the situation that the same semantic concept can be expressed using different views with similar information. Thus, how to obtain a certain Semantically Consistent Patterns (SCP) for cross-view data, which embeds the complementary information from different views, is of great importance for those applications. However, the heterogeneity among cross-view representations brings a significant challenge on mining the SCP. In this paper, we propose a general framework to discover the SCP for cross-view data. Specifically, aiming at building a feature-isomorphic space among different views, a novel Isomorphic Relevant Redundant Transformation (IRRT) is first proposed. The IRRT linearly maps multiple heterogeneous low-level feature spaces to a high-dimensional redundant feature-isomorphic one, which we name as mid-level space. Thus, much more complementary information from different views can be captured. Furthermore, to mine the semantic consistency among the isomorphic representations in the mid-level space, we propose a new Correlation-based Joint Feature Learning (CJFL) model to extract a unique high-level semantic subspace shared across the feature-isomorphic data. Consequently, the SCP for cross-view data can be obtained. Comprehensive experiments on three data sets demonstrate the advantages of our framework in classification and retrieval.

Digital recruitment is increasingly becoming a popular avenue for identifying human subjects for various studies. The process starts with an online ad that describes the task and explains expectations. As social media has exploded in popularity, efforts are being made to use social media to recruit for new career opportunities. Particularly, LinkedIn and Twitter have enabled an emerging trend for matching individuals with possible opportunities based on their interests. This makes finding more relevant jobs easier for both employees and employers. There are, however, many unanswered questions about how best to do that.

Internet-based crowdsourcing systems can be viewed as a kind of loosely coupled social networks. With these systems, it is easy to collect multiple noisy labels for the same object when conducting annotation for supervised learning. Because non-expert labelers lack expertise and dedication, and have strong personal preference, they may have bias when labeling. These cause Imbalanced Multiple Noisy Labeling. In this paper, we propose an agnostic algorithm Positive LAbel frequency Threshold (PLAT) to deal with imbalanced labeling. Because of the dynamics of social networks, in most cases no information about the qualities of labelers and underlying class distributions can be acquired. PLAT does not require prior knowledge of the labeling qualities of labelers, the underlying class distributions, and the level of labeling imbalance. Simulations on eight real-world datasets with different underlying class distributions demonstrate that PLAT not only effectively deals with the imbalanced multiple noisy labeling that off-the-shelf agnostic methods cannot cope with, but also performs nearly the same as majority voting under the circumstances that labelers have no bias.

One important assumption of information extraction is that extractions occurring more frequently are more likely to be correct. Sparse information extraction is challenging because no matter how big a corpus is, there are extractions supported by only a small amount of evidence in the corpus. A pioneering work known as REALM learns HMMs to model the context of a semantic relationship for assessing the extractions. This is quite costly and the semantics revealed for the context are not explicit. In this work, we introduce a lightweight, explicit semantic approach for sparse information extraction. We use a large semantic network consisting of millions of concepts, entities, and attributes to explicitly model the context of semantic relationships. Experiments show that our approach improves the F-score of extraction by at least 11.2% over state-of-the-art, HMM based approaches while maintaining more efficiency.

Computing semantic similarity between two terms is essential for a variety of text analytics and understanding applications. However, existing approaches are more suitable for semantic similarity between words rather than the more general multi-word expressions (MWEs), and they do not scale very well. Therefore, we propose a lightweight and effective approach for semantic similarity using a large scale semantic network automatically acquired from billions of web documents. Given two terms, we map them into the concept space, and compare their similarity there. Furthermore, we introduce a clustering approach to orthogonalize the concept space in order to improve the accuracy of the similarity measure. Extensive studies demonstrate that our approach can accurately compute the semantic similarity between terms with MWEs and ambiguity, and significantly outperforms 12 competing methods.

In addition to the news content, most web news pages also contain navigation panels, advertisements, related news links etc. These non-news items not only exist outside the news region, but are also present in the news content region. Effectively extracting the news content and filtering the noise have important effects on the follow-up activities of content management and analysis. Our extensive case studies have indicated that there exists potential relevance between web content layouts and their tag paths. Based on this observation, we design two tag path features to measure the importance of nodes: Text to tag Path Ratio (TPR) and Extended Text to tag Path Ratio (ETPR), and describe the calculation process of TPR by traversing the parsing tree of a web news page. In this paper, we present Content Extraction via Path Ratios (CEPR) - a fast, accurate and general on-line method for distinguishing news content from non-news content by the TPR/ETPR histogram effectively. In order to improve the ability of CEPR in extracting short texts, we propose a Gaussian smoothing method weighted by a tag path edit distance. This approach can enhance the importance of internal-link nodes but ignore noise nodes existing in news content. Experimental results on the CleanEval datasets and web news pages randomly selected from well-known websites show that CEPR can extract across multi-resources, multi-styles, and multi-languages. The average F and average score with CEPR is 8.69% and 14.25% higher than CETR, which demonstrates better web news extraction performance than most existing methods.

Group feature selection makes use of structural information among features to discover a meaningful subset of features. Existing group feature selection algorithms only deal with pre-given candidate feature sets and they are incapable of handling streaming features. On the other hand, feature selection algorithms targeted for streaming features can only perform at the individual feature level without considering intrinsic group structures of the features. In this paper, we perform group feature selection with streaming features. We propose to perform feature selection at the group and individual feature levels simultaneously in a manner of a feature stream rather than a pre-given candidate feature set. In our approach, the group structures are fully utilized to reduce the cost of evaluating streaming features. We have extensively evaluated the proposed method. Experimental results have demonstrated that our proposed algorithms statistically outperform state-of-the-art methods of feature selection in terms of classification accuracy.

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

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

This paper takes manifold learning and regression simultaneously into account to perform unsupervised spectral feature selection. We first extract the bases of the data, and then represent the data sparsely using the extracted bases by proposing a novel joint graph sparse coding model, JGSC for short. We design a new algorithm TOSC to compute the resulting objective function of JGSC, and then theoretically prove that the proposed objective function converges to its global optimum via the proposed TOSC algorithm. We repeat the extraction and the TOSC calculation until the value of the objective function of JGSC satisfies pre-defined conditions. Eventually the derived new representation of the data may only have a few non-zero rows, and we delete the zero rows (a.k.a. zero-valued features) to conduct feature selection on the new representation of the data. Our empirical studies demonstrate that the proposed method outperforms several state-of-the-art algorithms on real datasets in term of the kNN classification performance.

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

The emergence of social tagging and crowdsourcing systems provides a unique platform where multiple weak labelers can form a crowd to fulfill a labeling task. Yet crowd labelers are often noisy, inaccurate, and have limited labeling knowledge, and worst of all, they act independently without seeking complementary knowledge from each other to improve labeling performance. In this paper, we propose a Self-Taught Active Learning (STAL) paradigm, where imperfect labelers are able to learn complementary knowledge from one another to expand their knowledge sets and benefit the underlying active learner. We employ a probabilistic model to characterize the knowledge of each labeler through which a weak labeler can learn complementary knowledge from a stronger peer. As a result, the self-taught active learning process eventually helps achieve high classification accuracy with minimized labeling costs and labeling errors.

In stock markets, an emerging challenge for surveillance is that a group of hidden manipulators collaborate with each other to manipulate the price movement of securities. Recently, the coupled hidden Markov model (CHMM)-based coupled behavior analysis (CBA) has been proposed to consider the coupling relationships in the above group-based behaviors for manipulation detection. From the modeling perspective, however, this requires overall aggregation of the behavioral data to cater for the CHMM modeling, which does not differentiate the coupling relationships presented in different forms within the aggregated behaviors and degrade the capability for further anomaly detection. Thus, this paper suggests a general CBA framework for detecting group-based market manipulation by capturing more comprehensive couplings and proposes two variant implementations, which are hybrid coupling (HC)-based and hierarchical grouping (HG)-based respectively. The proposed framework consists of three stages. The first stage, qualitative analysis, generates possible qualitative coupling relationships between behaviors with or without domain knowledge. In the second stage, quantitative representation of coupled behaviors is learned via proper methods. For the third stage, anomaly detection algorithms are proposed to cater for different application scenarios. Experimental results on data from a major Asian stock market show that the proposed framework outperforms the CHMM-based analysis in terms of detecting abnormal collaborative market manipulations. Additionally, the two different implementations are compared with their effectiveness for different application scenarios.

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

How to accurately extract the content of Web news is a popular and significant issue in Web Intelligence. Many Web news sites have similar structures and layout styles, and there are potential correlations between Web content layouts and tag path patterns. Compared with other extraction features, such as HTML tags, literal words and visual features, a tag path pattern not only addresses content segments well, but also has an advantage in the generalization. However, can we accurately extract Web news using only tag path patterns? Motivated by this problem, we propose a PPWIE extraction model. We design an extraction algorithm WEtr using self-defined tag path patterns, and then define a special tag path pattern called the distinguishing tag path pattern. In addition, to tackle the NPC-hard problem in path pattern mining, we propose a polynomial-time (ln|n|+1)-approximation algorithm MPM, in which n indicates the scale of positive samples. Our experiments show that our integration method WEtr+MPM in PPWIE can achieve better performance with more than 98% of precision, recall and the F-score on real world datasets.

Tracking recurring concept drifts is a significant issue for machine learning and data mining that frequently appears in real-world stream classification problems. It is a challenge for many streaming classification algorithms to learn recurring concepts in a data stream environment with unlabeled data, and this challenge has received little attention from the research community. Motivated by this challenge, this article focuses on the problem of recurring contexts in streaming environments with limited labeled data. We propose a semi-supervised classification algorithm for data streams with REcurring concept Drifts and Limited LAbeled data, called REDLLA, in which a decision tree is adopted as the classification model. When growing a tree, a clustering algorithm based on k -means is installed to produce concept clusters and unlabeled data are labeled in the method of majority-class at leaves. In view of deviations between history and new concept clusters, potential concept drifts are distinguished and recurring concepts are maintained. Extensive studies on both synthetic and real-world data confirm the advantages of our REDLLA algorithm over three state-of-the-art online classification algorithms of CVFDT, DWCDS, and CDRDT and several known online semi-supervised algorithms, even in the case with more than 90% unlabeled data.

One of the challenges in data mining is the dimensionality of data, which is often very high and prevalent in many domains, such as text categorization and bio-informatics. The high-dimensionality of data may bring many adverse situations to traditional learning algorithms. To cope with this issue, feature selection has been put forward. Currently, many efforts have been attempted in this field and lots of feature selection algorithms have been developed. In this paper we propose a new selection method to pick discriminative features by using information measurement. The main characteristic of our selection method is that the selection procedure works like feature clustering in a hierarchically agglomerative way, where each feature is considered as a cluster and the between-cluster and within-cluster distances are measured by mutual information and the coefficient of relevancy respectively. Consequently, the final aggregated cluster is the selection result, which has the minimal redundancy among its members and the maximal relevancy with the class labels. The simulation experiments on seven datasets show that the proposed method outperforms other popular feature selection algorithms in classification performance.

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

Counting craters in remotely sensed images is the only tool that provides relative dating of remote planetary surfaces. Surveying craters requires counting a large amount of small subkilometer craters, which calls for highly efficient automatic crater detection. In this article, we present an integrated framework on autodetection of subkilometer craters with boosting and transfer learning. The framework contains three key components. First, we utilize mathematical morphology to efficiently identify crater candidates , the regions of an image that can potentially contain craters. Only those regions occupying relatively small portions of the original image are the subjects of further processing. Second, we extract and select image texture features, in combination with supervised boosting ensemble learning algorithms, to accurately classify crater candidates into craters and noncraters. Third, we integrate transfer learning into boosting, to enhance detection performance in the regions where surface morphology differs from what is characterized by the training set. Our framework is evaluated on a large test image of 37,500 × 56,250 m 2 on Mars, which exhibits a heavily cratered Martian terrain characterized by nonuniform surface morphology. Empirical studies demonstrate that the proposed crater detection framework can achieve an F1 score above 0.85, a significant improvement over the other crater detection algorithms.

Detecting changes in stock prices is a well known problem in finance with important implications for monitoring and business intelligence. Forewarning of changes in stock price, can be made by the early detection of changes in the distributions of stock order numbers. In this paper, we address the change detection problem for streams of stock order numbers and propose a novel incremental detection algorithm. Our algorithm gains high accuracy and low delay by employing a natural Poisson distribution assumption about the nature of stock order streams. We establish that our algorithm is highly scalable and has linear complexity. We also experimentally demonstrate its effectiveness for detecting change points, via experiments using both synthetic and real-world datasets.

Summary form only given. Since its first meeting in 2001, the IEEE International Conference on Data Mining (ICDM) has established itself as the world's premier research conference in data mining. With sponsorship from the IEEE Computer Society, ICDM has taken a number of initiatives to promote data mining research over the past 10 years. By promoting novel, high quality research findings, and innovative solutions to challenging data mining problems, the conference seeks to continuously advance the state-ofthe-art in data mining. ICDM has identified many influential research topics in data mining.

Multiple instance learning (MIL) is a generalization of supervised learning which attempts to learn useful information from bags of instances. In MIL, the true labels of the instances in positive bags are not always available for training. This leads to a critical challenge, namely, handling the ambiguity of instance labels in positive bags. To address this issue, this paper proposes a novel MIL method named SMILE (Similarity-based Multiple Instance LEarning). It introduces a similarity weight to each instance in positive bag, which represents the instance similarity towards the positive and negative classes. The instances in positive bags, together with their similarity weights, are thereafter incorporated into the learning phase to build an extended SVM-based predictive classifier. Experiments on three real-world datasets consisting of 12 subsets show that SMILE achieves markedly better classification accuracy than state-of-the-art MIL methods.

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

Support vector machines (SVMs) are invaluable tools for many practical applications in artificial intelligence, e.g., classification and event recognition. However, popular SVM solvers are not sufficiently efficient for applications with a great deal of samples as well as a large number of features. In this paper, thus, we present NESVM, a fast gradient SVM solver that can optimize various SVM models, e.g., classical SVM, linear programming SVM and least square SVM. Compared against SVM-Perf (whose convergence rate in solving the dual SVM is upper bounded by O(1/√k) where k is the number of iterations) and Pegasos (online SVM that converges at rate O(1/k) for the primal SVM), NESVM achieves the optimal convergence rate at O(1/k2) and a linear time complexity. In particular, NESVM smoothes the nondifferentiable hinge loss and ℓ1-norm in the primal SVM. Then the optimal gradient method without any line search is adopted to solve the optimization. In each iteration round, the current gradient and historical gradients are combined to determine the descent direction, while the Lipschitz constant determines the step size. Only two matrix-vector multiplications are required in each iteration round. Therefore, NESVM is more efficient than existing SVM solvers. In addition, NESVM is available for both linear and nonlinear kernels. We also propose "homotopy NESVM" to accelerate NESVM by dynamically decreasing the smooth parameter and using the continuation method. Our experiments on census income categorization, indoor/outdoor scene classification event recognition and scene recognition suggest the efficiency and the effectiveness of NESVM. The MATLAB code of NESVM will be available on our website for further assessment.

An ensemble is a set of learned models that make decisions collectively. Although an ensemble is usually more accurate than a single learner, existing ensemble methods often tend to construct unnecessarily large ensembles, which increases the memory consumption and computational cost. Ensemble pruning tackles this problem by selecting a subset of ensemble members to form subensembles that are subject to less resource consumption and response time with accuracy that is similar to or better than the original ensemble. In this paper, we analyze the accuracy/diversity trade-off and prove that classifiers that are more accurate and make more predictions in the minority group are more important for subensemble construction. Based on the gained insights, a heuristic metric that considers both accuracy and diversity is proposed to explicitly evaluate each individual classifier's contribution to the whole ensemble. By incorporating ensemble members in decreasing order of their contributions, subensembles are formed such that users can select the top $p$ percent of ensemble members, depending on their resource availability and tolerable waiting time, for predictions. Experimental results on 26 UCI data sets show that subensembles formed by the proposed EPIC (Ensemble Pruning via Individual Contribution ordering) algorithm outperform the original ensemble and a state-of-the-art ensemble pruning method, Orientation Ordering (OO).

Many approaches to active learning involve periodically training one classifier and choosing data points with the lowest confidence. An alternative approach is to periodically choose data instances that maximize disagreement among the label predictions across an ensemble of classifiers. Many classifiers with different underlying structures could fit this framework, but some ensembles are more suitable for some data sets than others. The question then arises as to how to find the most suitable ensemble for a given data set. In this work we introduce a method that begins with a heterogeneous ensemble composed of multiple instances of different classifier types, which we call adaptive informative sampling (AIS). The algorithm periodically adds data points to the training set, adapts the ratio of classifier types in the heterogeneous ensemble in favor of the better classifier type, and optimizes the classifiers in the ensemble using stochastic methods. Experimental results show that the proposed method performs consistently better than homogeneous ensembles. Comparison with random sampling and uncertainty sampling shows that the algorithm effectively draws informative data points for training.

One common approach to active learning is to iteratively train a single classifier by choosing data points based on its uncertainty, but it is nontrivial to design uncertainty measures unbiased by the choice of classifier. Query by committee suggests that given an ensemble of diverse but accurate classifiers, the most informative data points are those that cause maximal disagreement among the predictions of the ensemble members. However the method for finding ensembles appropriate to a given data set remains an open question. In this paper, the random subspace method is combined with active learning to create multiple instances of different classifier types, and an algorithm is introduced that adapts the ratio of different classifier types in the ensemble towards better overall accuracy. Here we show that the proposed algorithm outperforms C4.5 with uncertainty sampling, Naive Bayes with uncertainty sampling, bagging, boosting and the random subspace method with random sampling. To the best of our knowledge, our work is the first to adapt the ratio of classifiers in a heterogeneous ensemble for active learning.

In this paper, we formulate a new research problem of learning from vaguely labeled one-class data streams, where the main objective is to allow users to label instance groups, instead of single instances, as positive samples for learning. The batch-labeling, however, raises serious issues because labeled groups may contain non-positive samples, and users may change their labeling interests at any time. To solve this problem, we propose a Vague One-Class Learning (VOCL) framework which employs a double weighting approach, at both instance and classifier levels, to build an ensembling framework for learning. At instance level, both local and global filterings are considered for instance weight adjustment. Two solutions are proposed to take instance weight values into the classifier training process. At classifier level, a weight value is assigned to each classifier of the ensemble to ensure that learning can quickly adapt to users' interests. Experimental results on synthetic and real-world data streams demonstrate that the proposed VOCL framework significantly outperforms other methods for vaguely labeled one-class data streams.

In this paper, we identify a new research problem on cleansing noisy data streams which contain incorrectly labeled training examples. The objective is to accurately identify and remove mislabeled data, such that the prediction models built from the cleansed streams can be more accurate than the ones trained from the raw noisy streams. For this purpose, we first use bias-variance decomposition to derive a maximum variance margin (MVM) principle for stream data cleansing. Following this principle, we further propose a local and global filtering (LgF) framework to combine the strength of local noise filtering (within one single data chunk) and global noise filtering (across a number of adjacent data chunks) to identify erroneous data. Experimental results on six data streams (including two real-world data streams) demonstrate that LgF significantly outperforms simple methods in identifying noisy examples.

Dr. Yixin Chen, Washington University in St. Louis, USA, Professor Juergen Dix, Clausthal University of Technology, Germany, Professor Sergio Greco, University of Calabria, Italy, Dr. Eamonn Keogh, University of California-Riverside, USA, Professor Jianzhong Li, Harbin Institute of Technology, China, Professor Qing Li, City University of Hong Kong, China, Professor Yannis Papakonstantinou, University of California-San Diego, USA, Professor V.S. Subrahmanian, University of Maryland, College Park, USA, and Professor Zhi-Hua Zhou, Nanjing University, China.

With this last issue of 2008, the IEEE Transactions on Knowledge and Data Engineering (TKDE) has completed its 20 years of publication, and the Editor-in-Chief (EiC) has completed the second term of his TKDE EiC position. It has been four years since he assumed this position in January 2005. Thanks to the hard work and outstanding efforts of our Associate Editors, reviewers, authors, and support staff from the IEEE Computer Society Publications Office, TKDE has further strengthened its "premier" status over the past four years in the field of knowledge and data engineering, including data mining, database systems, and knowledge engineering. Our paper submission rate has continued to increase, and is now far higher than any other journal in data mining, database systems, and knowledge engineering. The journal impact factor exceeded 2.0 in 2006 for the first time, and ranks #3 in all IEEE Computer Society transactions in the most recent 2007 journal impact factors. The EiC would like to take this opportunity to review some of the major activities that have taken place over the past four years, some of which are based on the changes reported in his previous editorials.

Relational patterns across multiple databases can reveal special pattern relationships hidden inside data collections. Existing research in data mining has made significant efforts in discovering different types of patterns from single or multiple databases, but how to find patterns that have a higher support in database A than in database B with a given support threshold a is still an open problem. We propose in this paper DRAMA, a systematic framework for discovering relational patterns across multiple databases. More specifically, given a series of data collections, we try to discover patterns from different databases with patterns' relationships satisfying the user specified constraints. Our method seeks to build a hybrid frequent pattern tree (HFP-tree) from multiple databases, and mine patterns from the HFP-tree by integrating users' constraints into the pattern mining process.

Subspace selection is a powerful tool in data mining. An important subspace method is the Fisher-Rao linear discriminant analysis (LDA), which has been successfully applied in many fields such as biometrics, bioinformatics, and multimedia retrieval. However, LDA has a critical drawback: the projection to a subspace tends to merge those classes that are close together in the original feature space. If the separated classes are sampled from Gaussian distributions, all with identical covariance matrices, then LDA maximizes the mean value of the Kullback-Leibler (KL) divergences between the different classes. We generalize this point of view to obtain a framework for choosing a subspace by 1) generalizing the KL divergence to the Bregman divergence and 2) generalizing the arithmetic mean to a general mean. The framework is named the general averaged divergence analysis (GADA). Under this GADA framework, a geometric mean divergence analysis (GMDA) method based on the geometric mean is studied. A large number of experiments based on synthetic data show that our method significantly outperforms LDA and several representative LDA extensions.

This paper presents an active learning approach to the problem of systematic noise inference and noise elimination, specifically the inference of Associated Corruption (AC) rules. AC rules are defined to simulate a common noise formation process in real-world data, in which the occurrence of an error on one attribute is dependent on several other attribute values. Our approach consists of two algorithms, Associative Corruption Forward (ACF) and Associative Corruption Backward (ACB). Algorithm ACF is proposed for noise inference, and ACB is designed for noise elimination. The experimental results show that the ACF algorithm can infer the noise formation correctly, and ACB indeed enhances the data quality for supervised learning.

Provides instructions and guidelines to prospective authors who wish to submit manuscripts.

Empirical studies on supervised learning have shown that ensembling methods lead to a model superior to the one built from a single learner under many circumstances especially when learning from imperfect, such as biased or noise infected, information sources. In this paper, we provide a novel corrective classification (C2) design, which incorporates error detection, data cleansing and Bootstrap sampling to construct base learners that constitute the classifier ensemble. The essential goal is to reduce noise impacts and eventually enhance the learners built from noise corrupted data. We further analyze the importance of both the accuracy and diversity of base learners in ensembling, in order to shed some light on the mechanism under which C2 works. Experimental comparisons will demonstrate that C2 is not only superior to the learner built from the original noisy sources, but also more reliable than bagging or the aggressive classifier ensemble (ACE), which are two degenerate components/variants of C2.

A bridging rule in this paper has its antecedent and action from different conceptual clusters. We first design two algorithms for mining bridging rules between clusters in a database, and then propose two non-linear metrics for measuring the interestingness of bridging rules. Bridging rules can be distinct from association rules (or frequent itemsets). This is because (1) bridging rules can be generated by infrequent itemsets that are pruned in association rule mining; and (2) bridging rules are measured by the importance that includes the distance between two conceptual clusters, whereas frequent itemsets are measured by only the support.

Recent research in machine learning, data mining, and related areas has produced a wide variety of algorithms for cost-sensitive (CS) classification, where instead of maximizing the classification accuracy, minimizing the misclassification cost becomes the objective. These methods often assume that their input is quality data without conflict or erroneous values, or the noise impact is trivial, which is seldom the case in real-world environments. In this paper, we propose a Cost-guided Iterative Classification Filter (CICF) to identify noise for effective CS learning. Instead of putting equal weights on handling noise in all classes in existing efforts, CICF puts more emphasis on expensive classes, which makes it attractive in dealing with data sets with a large cost-ratio. Experimental results and comparative studies indicate that the existence of noise may seriously corrupt the performance of the underlying CS learners and by adopting the proposed CICF algorithm, we can significantly reduce the misclassification cost of a CS classifier in noisy environments.

In this paper, we deal with mining sequential patterns in multiple data streams. Building on a state-of-the-art sequential pattern mining algorithm PrefixSpan for mining transaction databases, we propose MILE, an efficient algorithm to facilitate the mining process. MILE recursively utilizes the knowledge of existing patterns to avoid redundant data scanning, and can therefore effectively speed up the new patterns' discovery process. Another unique feature of MILE is that it can incorporate some prior knowledge of the data distribution in data streams into the mining process to further improve the performance. Extensive empirical results show that MILE is significantly faster than PrefixSpan. As MILE consumes more memory than PrefixSpan, we also present a solution to balance the memory usage and time efficiency in memory constrained environments.

This paper aims to take general tensors as inputs for supervised learning. A supervised tensor learning (STL) framework is established for convex optimization based learning techniques such as support vector machines (SVM) and minimax probability machines (MPM). Within the STL framework, many conventional learning machines can be generalized to take n/sup th/-order tensors as inputs. We also study the applications of tensors to learning machine design and feature extraction by linear discriminant analysis (LDA). Our method for tensor based feature extraction is named the tenor rank-one discriminant analysis (TR1DA). These generalized algorithms have several advantages: 1) reduce the curse of dimension problem in machine learning and data mining; 2) avoid the failure to converge; and 3) achieve better separation between the different categories of samples. As an example, we generalize MPM to its STL version, which is named the tensor MPM (TMPM). TMPM learns a series of tensor projections iteratively. It is then evaluated against the original MPM. Our experiments on a binary classification problem show that TMPM significantly outperforms the original MPM.

Mining data streams is important in both science and commerce. Two major challenges are (1) the data may grow without limit so that it is difficult to retain a long history; and (2) the underlying concept of the data may change over time. Different from common practice that keeps recent raw data, this paper uses a measure of conceptual equivalence to organize the data history into a history of concepts. Along the journey of concept change, it identifies new concepts as well as re-appearing ones, and learns transition patterns among concepts to help prediction. Different from conventional methodology that passively waits until the concept changes, this paper incorporates proactive and reactive predictions. In a proactive mode, it anticipates what the new concept will be if a future concept change takes place, and prepares prediction strategies in advance. If the anticipation turns out to be correct, a proper prediction model can be launched instantly upon the concept change. If not, it promptly resorts to a reactive mode: adapting a prediction model to the new data. A system RePro is proposed to implement these new ideas. Experiments compare the system with representative existing prediction methods on various benchmark data sets that represent diversified scenarios of concept change. Empirical evidence demonstrates that the proposed methodology is an effective and efficient solution to prediction for data streams.

Real-world data is noisy and can often suffer from corruptions or incomplete values that may impact the models created from the data. To build accurate predictive models, data acquisition is usually adopted to prepare the data and complete missing values. However, due to the significant cost of doing so and the inherent correlations in the data set, acquiring correct information for all instances is prohibitive and unnecessary. An interesting and important problem that arises here is to select what kinds of instances to complete so the model built from the processed data can receive the "maximum" performance improvement. This problem is complicated by the reality that the costs associated with the attributes are different, and fixing the missing values of some attributes is inherently more expensive than others. Therefore, the problem becomes that given a fixed budget, what kinds of instances should be selected for preparation, so that the learner built from the processed data set can maximize its performance? In this paper, we propose a solution for this problem, and the essential idea is to combine attribute costs and the relevance of each attribute to the target concept, so that the data acquisition can pay more attention to those attributes that are cheap in price but informative for classification. To this end, we will first introduce a unique economical factor (EF) that seamlessly integrates the cost and the importance (in terms of classification) of each attribute. Then, we will propose a cost-constrained data acquisition model, where active learning, missing value prediction, and impact-sensitive instance ranking are combined for effective data acquisition. Experimental results and comparative studies from real-world data sets demonstrate the effectiveness of our method.

Advances in the media and entertainment industries, including streaming audio and digital TV, present new challenges for managing and accessing large audio-visual collections. Current content management systems support retrieval using low-level features, such as motion, color, and texture. However, low-level features often have little meaning for naive users, who much prefer to identify content using high-level semantics or concepts. This creates a gap between systems and their users that must be bridged for these systems to be used effectively. To this end, in this paper, we first present a knowledge-based video indexing and content management framework for domain specific videos (using basketball video as an example). We will provide a solution to explore video knowledge by mining associations from video data. The explicit definitions and evaluation measures (e.g., temporal support and confidence) for video associations are proposed by integrating the distinct feature of video data. Our approach uses video processing techniques to find visual and audio cues (e.g., court field, camera motion activities, and applause), introduces multilevel sequential association mining to explore associations among the audio and visual cues, classifies the associations by assigning each of them with a class label, and uses their appearances in the video to construct video indices. Our experimental results demonstrate the performance of the proposed approach.

Research in machine learning, data mining and related areas has produced a wide variety of algorithms for cost-sensitive (CS) classification, where instead of maximizing the classification accuracy, minimizing the misclassification cost becomes the objective. However, these methods assume that training sets do not contain significant noise, which is rarely the case in real-world environments. In this paper, we systematically study the impacts of class noise on CS learning, and propose a cost-guided class noise handling algorithm to identify noise for effective CS learning. We call it cost-guided iterative classification filter (CICF), because it seamlessly integrates costs and an existing classification filter (C. Brodley and M. Friedl, 1999) for noise identification. Instead of putting equal weights to handle noise in all classes in existing efforts, CICF puts more emphasis on expensive classes, which makes it especially successful in dealing with datasets with a large cost-ratio. Experimental results and comparative studies from real-world datasets indicate that the existence of noise may seriously corrupt the performance of CS classifiers, and by adopting the proposed CICF algorithm, we can significantly reduce the misclassification cost of a CS classifier in noisy environments.

Mining from data streams has become an important and challenging task for many real-world applications such as credit card fraud protection and sensor networking. One popular solution is to separate stream data into chunks, learn a base classifier from each chunk, and then integrate all base classifiers for effective classification. In this paper, we propose a dynamic classifier selection (DCS) mechanism to integrate base classifiers for effective mining from data streams. The proposed algorithm dynamically selects a single "best" classifier to classify each test instance at run time. Our scheme uses statistical information from attribute values, and uses each attribute to partition the evaluation set into disjoint subsets, followed by a procedure that evaluates the classification accuracy of each base classifier on these subsets. Given a test instance, its attribute values determine the subsets that the similar instances in the evaluation set have constructed, and the classifier with the highest classification accuracy on those subsets is selected to classify the test instance. Experimental results and comparative studies demonstrate the efficiency and efficacy of our method. Such a DCS scheme appears to be promising in mining data streams with dramatic concept drifting or with a significant amount of noise, where the base classifiers are likely conflictive or have low confidence.

Summary form only given, as follows. The complete presentation was not made available for publication as part of the conference proceedings. Data mining is a fast-growing area. The first Knowledge Discovery in Databases Workshop was held in August 1989, in conjunction with the 1989 International Joint Conference on Artificial Intelligence, and this workshop series became the International Conference on Knowledge Discovery and Data Mining (KDD) in 1995. In 2003, there were a total of 15 data mining conferences. These 15 conferences do not include various artificial intelligence (AI), statistics and database conferences (and their workshops) that also solicited and accepted data mining related papers, such as IJCAI, ICML, ICTAI, COMPSTAT, AI & Statistics, SIGMOD, VLDB, ICDE, and CIKM. Among various data mining conferences, KDD and ICDM (the IEEE International Conference on Data Mining) are arguably (or unarguably) the two premier ones in the field. ICDM was established in 2000, sponsored by the IEEE Computer Society, and had its first annual meeting in 2001. This talk will review the topics of interest from ICDM from an AI perspective, and analyze common topics in data mining and AI, including key AI ideas that have been used in both data mining and machine learning. We will also discuss two current research projects on (1) user-centered agents for biological information exploration on the Web, and (2) dynamic classifier selection in dealing with streaming data. Both projects apply data mining techniques for intelligent analysis of large volumes of data.

This paper presents an efficient method for mining both positive and negative association rules in databases. The method extends traditional associations to include association rules of forms A ⇒ ¬ B , ¬ A ⇒ B , and ¬ A ⇒ ¬ B , which indicate negative associations between itemsets. With a pruning strategy and an interestingness measure, our method scales to large databases. The method has been evaluated using both synthetic and real-world databases, and our experimental results demonstrate its effectiveness and efficiency.

Many large organizations have multiple data sources, such as different branches of an interstate company. While putting all data together from different sources might amass a huge database for centralized processing, mining association rules at different data sources and forwarding the rules (rather than the original raw data) to the centralized company headquarter provides a feasible way to deal with multiple data source problems. In the meanwhile, the association rules at each data source may be required for that data source in the first instance, so association analysis at each data source is also important and useful. However, the forwarded rules from different data sources may be too many for the centralized company headquarter to use. This paper presents a weighting model for synthesizing high-frequency association rules from different data sources. There are two reasons to focus on high-frequency rules. First, a centralized company headquarter is interested in high-frequency rules because they are supported by most of its branches for corporate profitability. Second, high-frequency rules have larger chances to become valid rules in the union of all data sources. In order to extract high-frequency rules efficiently, a procedure of rule selection is also constructed to enhance the weighting model by coping with low-frequency rules. Experimental results show that our proposed weighting model is efficient and effective.

Mining frequent patterns with an FP-tree avoids costly candidate generation and repeatedly occurrence frequency checking against the support threshold. It therefore achieves better performance and efficiency than Apriori-like algorithms. However the database still needs to be scanned twice to get the FP-tree. This can be very time-consuming when new data are added to an existing database because two scans may be needed for not only the new data but also the existing data. This paper presents a new data structure P-tree, Pattern Tree, and a new technique, which can get the P-tree through only one scan of the database and can obtain the corresponding FP-tree with a specified support threshold. Updating a P-tree with new data needs one scan of the new data only, and the existing data do not need to be re-scanned.

Mining frequent patterns in transaction databases has been a popular subject in data mining research. Common activities include finding patterns in database transactions, times-series, and exceptions. The Apriori algorithm is a widely accepted method of generating frequent patterns. The algorithm can require many scans of the database and can seriously tax resources. New methods of finding association rules, such as the Frequent Pattern Tree (FP-Tree) have improved performance, but still have problems when new data becomes available and require two scans of the database.This paper proposes a new method, which requires only one scan of the database and supports update of patterns when new data becomes available. We design a new structure called Pattern Repository (PR), which stores all of the relevant information in a highly compact form and allows direct derivation of the FP-Tree and association rules quickly with a minimum of resources. In addition, it supports run-time generation of association rules by considering only those patterns that meet on-line data requirements.

In most data mining applications where induction is used as the primary tool for knowledge extraction from real world databases, it is difficult to precisely identify a complete set of relevant attributes. The paper introduces a novel rule induction algorithm called Rule Induction Two In One (RITIO), which eliminates attributes in the order of decreasing irrelevancy. Like ID3-like decision tree construction algorithms, RITIO makes use of the entropy measure as a means of constraining the hypothesis search space; but, unlike IDS-like algorithms, the hypotheses language is the rule structure and RITIO generates rules without constructing decision trees. The final concept description produced by RITIO is shown to be largely based on only the most relevant attributes. Experimental results confirm that, even on noisy, industrial databases, RITIO achieves high levels of predictive accuracy.

This article presents a heuristic, attribute-based, noise-tolerant data mining program, HCV (Version 2.0), based on the newly-developed extension matrix approach. By dividing the positive examples (PE) of a specific class in a given example set into intersecting groups and adopting a set of strategies to find a heuristic conjunctive formula in each group which covers all the group's positive examples and none of the negative examples (NE), the HCV induction algorithm adopted in the HCV (Version 2.0) software finds a description formula in the form of variable-valued logic for PE against NE in low-order polynomial time at induction time. In addition to the HCV induction algorithm, this article also outlines some of the techniques for noise handling and discretization of numerical domains developed and implemented in the HCV (Version 2.0) software, and provides a performance comparison of HCV (Version 2.0) with other data mining algorithms ID3, C4.5, C4.5rules, and NewID in noisy and continuous domains. The empirical comparison shows that the rules generated by HCV (Version 2.0) are more compact than the decision trees or rules produced by ID3-like algorithms, and HCV's predicative accuracy is competitive with ID3-like algorithms. © 1998 John Wiley & Sons, Inc.