Video recommendation systems heavily rely on user watch time feedback, making accurate watch time prediction a crucial task. However, this task inherently suffers from bias, as recommendation models tend to favor long-duration videos to maximize watch time. This issue, known as duration bias in the watch-time prediction context, can be explained from a causal perspective, where video duration acts as a confounder. Recent works address this bias using backdoor adjustment, isolating the direct effect of content on watch time from observational data. These methods typically discretize video duration into groups, estimate group-wise effects, and then aggregate them via a unified prediction model. However, this aggregation strategy is prone to model misspecification due to feature distribution shift across groups. In this paper, we reinterpret the problem through the lens of invariant learning and propose a novel framework: Duration-Invariant Feature Learning (DIFL). DIFL employs a kernel-based regularization that enforces representation invariance across duration groups, reducing sensitivity to group design and improving generalization. This enables more accurate modeling of the direct causal effect and making counterfactual inference. Extensive experiments on both public and real large-scale production datasets demonstrate the effectiveness of our approach, which achieves SOTA performance.

Anime, as a popular medium, has attracted hundreds of millions audience, especially the young followers. In recent years, various anime-related AI tasks like anime character classification (ACC), retrieval (ACR), tag-prediction (ACTP), question answering (ACQA), and generation (ACG) have been proposed to meet the requirements of various applications. However, there is still a lack of large-scale datasets for these tasks. Such a situation is definitely not beneficial to anime-related academic research and industrial applications. In this paper, to boost anime-related AI technical research and application development, we present Anime-2026, a new and large-scale anime character dataset, which can support various anime-related AI tasks, including ACC, ACR, ACTP, ACQA and ACG etc. Anime-2026 consists of 1.5M anime character images, 14k different characters, 16k unique semantic keyword tags, 10k question-answer pairs, and 4k manually designed text queries by crowdsourcing for the ACR and ACG tasks. Furthermore, to assess the dataset, we re-implement a number of generic and anime-specific AI baseline models, and conduct extensive experiments to evaluate these models on Anime-2026. In summary, as a general benchmark dataset, Anime-2026 provides the largest free anime character resource to support future anime-related AI research and development. We expect that Anime-2026 will promote the R&D of new and more advanced models and methods of various anime-related AI tasks. The dataset is available on https://huggingface.co/datasets/miaojiemiao/Anime-2026.

Watch time prediction (WTP) has emerged as a pivotal task in short video recommendation systems, designed to quantify user engagement through continuous interaction modeling. Predicting users' watch times on videos often encounters fundamental challenges, including wide value ranges and imbalanced data distributions, which can lead to significant estimation bias when directly applying regression techniques. Recent studies have attempted to address these issues by converting the continuous watch time estimation into an ordinal regression task. While these methods demonstrate partial effectiveness, they exhibit notable limitations: (1) The discretization process frequently relies on bucket partitioning, inherently reducing prediction flexibility and accuracy. (2) The interdependencies among different partition intervals remain underutilized, missing opportunities for effective error correction.

This article proposes a new method for causal discovery based on a novel dependence measurement criterion, namely, Multi-level Wavelet Mapping Correlation (MWMC). MWMC captures nonlinear dependencies between variables by measuring their correlations across multiple levels of wavelet mappings. From a theoretical perspective, we show that the empirical estimate of MWMC converges exponentially fast to its population quantity. Under the null hypothesis of independence, we further design a permutation-based independence testing procedure, termed the Wavelet Independence Test (WIT), built upon MWMC. We prove that WIT not only effectively controls the Type I error rate (false positives), but also guarantees that the Type II error rate (false negatives) is upper bounded by \(\mathcal{O}(n^{-1})\) , where \( n \) denotes the sample size, even with a finite number of permutations. Building on these theoretical guarantees, we derive a causal discovery method by integrating MWMC-based WIT into standard causal discovery pipelines. Extensive experiments on (conditional) independence testing and causal discovery using both synthetic and real-world datasets with varying sample sizes demonstrate that our approach consistently outperforms existing independence testing and causal discovery methods in terms of reduced Type II error rates and statistically validated performance improvements. Impact Statement —Causal discovery is a fundamental task in knowledge discovery, aiming to uncover the underlying data-generating mechanisms in order to support more accurate and interpretable predictions. Statistical independence tests and conditional independence (CI) tests have long served as core tools in this area. To improve the reliability of independence testing, we propose a novel test, WIT, which achieves lower Type II error rates in 19 out of 25 distinct experimental scenarios involving diverse data distributions, compared to 15 out of 25 for the strongest existing baseline. We further apply WIT to CI testing and causal discovery, and extensive empirical results show that it consistently improves the performance of multiple causal discovery algorithms across a range of experimental settings.

Sea surface temperature (SST) prediction is a critical task in ocean science, supporting various applications, such as weather forecasting, fisheries management, and storm tracking. While existing data-driven methods have demonstrated significant success, they often neglect to leverage the rich domain knowledge accumulated over the past decades, limiting further advancements in prediction accuracy. The recent emergence of large language models (LLMs) has highlighted the potential of integrating domain knowledge for downstream tasks. However, the application of LLMs to SST prediction remains under explored, primarily due to the challenge of integrating ocean domain knowledge and numerical data. To address this issue, we propose Ocean Knowledge Graph-enhanced LLM (OKG-LLM), a novel framework for global SST prediction. To the best of our knowledge, this work presents the first systematic effort to construct an Ocean Knowledge Graph (OKG) specifically designed to represent diverse ocean knowledge for SST prediction. We then develop a graph embedding network to learn the comprehensive semantic and structural knowledge within the OKG, capturing both the unique characteristics of individual sea regions and the complex correlations between them. Finally, we align and fuse the learned knowledge with fine-grained numerical SST data and leverage a pre-trained LLM to model SST patterns for accurate prediction. Extensive experiments on the real-world dataset demonstrate that OKG-LLM consistently outperforms state-of-the-art methods, showcasing its effectiveness, robustness, and potential to advance SST prediction. The codes are available in the online repository.

Neural radiance fields (NeRFs) have demonstrated remarkable performance in novel view synthesis. However, there is much room for restoring 3-D scenes based on NeRF from corrupted images, which are common in natural scene captures and can significantly impact the effectiveness of NeRF. This article introduces NeRF-MIR, a novel neural rendering approach specifically proposed for the restoration of masked images, demonstrating the potential of NeRF in this domain. Recognizing that randomly emitting rays to pixels in NeRF may not effectively learn intricate image textures, we propose a patch-based entropy for ray emitting (PERE) strategy to distribute emitted rays properly. This enables NeRF-MIR to fuse comprehensive information from images of different views. In addition, we introduce a progressively iterative restoration (PIRE) mechanism to restore the masked regions in a self-training process. Furthermore, we design a dynamically weighted loss function that automatically recalibrates the loss weights for masked regions. As existing datasets do not support NeRF-based masked image restoration, we construct three masked datasets to simulate corrupted scenarios. Extensive experiments on real data and constructed datasets demonstrate the superiority of NeRF-MIR over its counterparts in masked image restoration.

Logs of large-scale cloud systems record diverse system events, ranging from routine statuses to critical errors. As the fundamental step of automated log analysis, log parsing is to transform unstructured logs into structured data for easier management and analysis. However, existing syntax-based and deep learning-based parsers struggle with complex real-world logs. Recent parsers based on large language models (LLMs) achieve higher accuracy, but they typically rely on online APIs (e.g., ChatGPT), raising privacy concerns and suffering from network latency. Moreover, with the rise of artificial intelligence for IT operations (AIOps), traditional parsers that focus on syntax-level templates fail to capture the semantics of dynamic log parameters, limiting their usefulness for downstream tasks. These challenges highlight the need for semantic log parsing that goes beyond template extraction to understand parameter semantics.This paper presents SemanticLog, an effective and efficient semantic log parser powered by open-source LLMs. SemanticLog adapts the structure of LLMs to the log parsing task, leveraging their rich knowledge while safeguarding log data privacy. It first extracts informative feature representations from log data, then refines them through fine-grained semantic perception to enable accurate template and parameter extraction together with semantic category prediction. To boost scalability, SemanticLog introduces the EffiParsing tree for faster inference on large-scale logs. Extensive experiments on the LogHub-2.0 dataset show that SemanticLog significantly outperforms the state-of-the-art log parsers in terms of accuracy. Moreover, it also surpasses existing LLM-based parsers in efficiency while showcasing advanced semantic parsing capability. Notably, SemanticLog employs much smaller open-source LLMs compared to existing LLM-based parsers (mainly based on ChatGPT), while maintaining better capability of log data privacy protection.

Contemporary face recognition systems use feature templates extracted from face images to identify persons. To enhance privacy, face template protection techniques are widely employed to conceal sensitive identity and appearance information stored in the template. This paper identifies an emerging privacy attack form utilizing diffusion models that could nullify prior protection. The attack can synthesize high-quality, identity-preserving face images from templates, revealing persons' appearance. Based on studies of the diffusion model's generative capability, this paper proposes a defense by rotating templates to a noise-like distribution. This is achieved efficiently by spherically and linearly interpolating templates on their located hypersphere. This paper further proposes to group-wisely divide and drop out templates' feature dimensions, to enhance the irreversibility of rotated templates. The proposed techniques are concretized as a novel face template protection technique, SlerpFace. Extensive experiments show that SlerpFace provides satisfactory recognition accuracy and comprehensive protection against inversion and other attack forms, superior to prior arts.

Existing Protein Language Models (PLMs) often suffer from limited adaptability to multiple tasks and exhibit poor generalization across diverse biological contexts. In contrast, general-purpose Large Language Models (LLMs) lack the capability to interpret protein sequences and fall short in domain-specific knowledge, limiting their capacity for effective biosemantic reasoning. To combine the advantages of both, we propose BioBridge, a domain-adaptive continual pretraining framework for protein understanding. This framework employs Domain-Incremental Continual Pre-training (DICP) to infuse protein domain knowledge and general reasoning corpus into a LLM simultaneously, effectively mitigating catastrophic forgetting. Cross-modal alignment is achieved via a PLM-ProjectorLLM pipeline, which maps protein sequence embeddings into the semantic space of the language model. Ultimately, an end-toend optimization is adopted to uniformly support various tasks, including protein property prediction and knowledge questionanswering. Our proposed BioBridge demonstrates performance comparable to that of mainstream PLMs on multiple protein benchmarks, such as EC and BindingDB. It also achieves results on par with LLMs on general understanding tasks like MMLU and RACE. This showcases its innovative advantage of combining domain-specific adaptability with general-purpose language competency.

Cloud removal (CR) remains a challenging task in remote sensing image processing. Although diffusion models (DM) exhibit strong generative capabilities, their direct applications to CR are suboptimal, as they generate cloudless images from random noise, ignoring inherent information in cloudy inputs. To overcome this drawback, we develop a new CR model EMRDM based on mean-reverting diffusion models (MRDMs) to establish a direct diffusion process between cloudy and cloudless images. Compared to current MRDMs, EMRDM offers a modular framework with updatable modules and an elucidated design space, based on a reformulated forward process and a new ordinary differential equation (ODE)-based backward process. Leveraging our framework, we redesign key MRDM modules to boost CR performance, including restructuring the denoiser via a preconditioning technique, reorganizing the training process, and improving the sampling process by introducing deterministic and stochastic samplers. To achieve multi-temporal CR, we further develop a denoising network for simultaneously denoising sequential images. Experiments on mono-temporal and multi-temporal datasets demonstrate the superior performance of EMRDM. Our code is available at https://github.com/Ly403/EMRDM.

Identity-preserving face synthesis aims to generate synthetic face images of virtual subjects that can substitute real-world data for training face recognition models. While prior arts strive to create images with consistent identities and diverse styles, they face a trade-off between them. Identifying their limitation of treating style variation as subject-agnostic and observing that real-world persons actually have distinct, subject-specific styles, this paper introduces MorphFace, a diffusion-based face generator. The generator learns fine-grained facial styles, e.g., shape, pose and expression, from the renderings of a 3D morphable model (3DMM). It also learns identities from an off-the-shelf recognition model. To create virtual faces, the generator is conditioned on novel identities of unlabeled synthetic faces, and novel styles that are statistically sampled from a real-world prior distribution. The sampling especially accounts for both intra-subject variation and subject distinctiveness. A context blending strategy is employed to enhance the generator’s responsiveness to identity and style conditions. Extensive experiments show that MorphFace outperforms the best prior arts in face recognition efficacy*.

Multivariate Time Series Forecasting (MTSF) is a critical task in various domains, and Large Language Models (LLMs) for MTSF have recently received considerable attention. Despite significant progress in large-scale time series models, particularly in fine-tuning pre-trained LLMs for MTSF, there are still limitations with existing works. First, multivariate time series (MTS) are often handled as multiple independent univariate inputs and processed separately across different variates, which neglects the dependencies between the variates. Second, most existing approaches employ Mean Squared Error (MSE) as loss function, which evaluates error at each time point separately, ignoring long-term dependencies. To address these limitations, this paper explores inter-variate and long-term dependencies to boost MTSF performance. We propose a temporal channel adapter to capture inter-variate relationships, and introduce a post-constraint module to model correlations between consecutive time points. Extensive experiments on benchmark datasets show that our method achieves state-of-the-art performance across diverse datasets and prediction horizons.

The continuous emergence of new objects in the visual world poses a serious challenge to deep object recognition methods, which sparks the increasing study on continual or incremental learning. However, learning new tasks faces the tough catastrophic forgetting problem, i.e., dramatic performance degradation on old tasks. A good continual learning model should be robustly adapted to the upcoming tasks while effectively handling catastrophic forgetting. In this paper, we focus on the class-incremental learning (CIL) task, and propose a novel prototype-based continual learning model C-HPN that projects the visual features into a hypersphere geometric space, where continual learning is conducted. C-HPN features two-fold contributions. On the one hand, instead of using the popular cross-entropy loss, we develop an instance-prototype compact loss to obtain well-clustered hyperspherical embeddings and a prototype-prototype separability loss to boost the model’s generalization by introducing large angle distance inductive bias between prototypes in the hyperspherical space. On the other hand, prototype construction and adaptation strategies are designed for effectively adapting new classes, and an instance-prototype relationship preservation distillation mechanism is introduced to overcome catastrophic forgetting. Extensive experiments on several image datasets validate the effectiveness of the proposed method.

Temporal causal discovery aims to uncover causal relations in time series data. Current deep learning-based methods usually analyze the parameters of some components of the trained models, which is an incomplete mapping process from the model parameters to the causality and fails to investigate the other components. To address this, this paper presents an interpretable transformer-based causal discovery model termed CausalFormer, which consists of: 1) the causality-aware transformer which learns the causal representation with the multi-kernel causal convolution under the temporal priority constraint, and 2) the decomposition-based causality detector which identifies causality by interpreting the global structure of the trained transformer with the regression relevance propagation.

Face recognition (FR) stands as one of the most crucial applications in computer vision. The accuracy of FR models has significantly improved in recent years due to the availability of large-scale human face datasets. However, directly using these datasets can inevitably lead to privacy and legal problems. Generating synthetic data to train FR models is a feasible solution to circumvent these issues. While existing synthetic-based face recognition methods have made significant progress in generating identity-preserving images, they are severely plagued by context overfitting, resulting in a lack of intra-class diversity of generated images and poor face recognition performance. In this paper, we propose a framework to $\textbf{U}$nleash model $\textbf{I}$nherent capabilities to enhance intra-class diversity for synthetic face recognition, shorted as $\textbf{UIFace}$. Our framework first train a diffusion model that can perform denoising conditioned on either identity contexts or a learnable empty context. The former generates identity-preserving images but lacks variations, while the latter exploits the model's intrinsic ability to synthesize intra-class-diversified images but with random identities. Then we adopt a novel two-stage denoising strategy to fully leverage the strengths of both type of contexts, resulting in images that are diverse as well as identity-preserving. Moreover, an attention injection module is introduced to further augment the intra-class variations by utilizing attention maps from the empty context to guide the denoising process in ID-conditioned generation. Experiments show that our method significantly surpasses previous approaches with even less training data and half the size of synthetic dataset. More surprisingly, the proposed $\textbf{UIFace}$ even achieves comparable performance of FR models trained on real datasets when we increase the number of synthetic identities.

Semi-supervised federated learning (SSFL) aims to leverage the vast amount of unlabeled data distributed across clients and a limited amount of labeled data held by the central server. However, SSFL faces a tough challenge of catastrophic forgetting, caused by discrepancies between local and global data distributions in non-independent and identically distributed (non-IID) settings, and exacerbated by noisy pseudo-labels. To deal with this problem, existing methods typically focus on mitigating the adverse effects of distribution divergence and refining the pseudo-labels. Differently, in this paper we tackle this problem from a data perspective by reducing the divergence between local and global distributions. Specifically, we propose global knowledge generative replay, which generates synthetic samples to complement the missing global knowledge during local training. Additionally, we introduce forgetting-aware model aggregation, a method that adaptively re-weights local models based on their degree of knowledge forgetting, resulting in a more robust global model. We conduct extensive experiments on widely-used benchmark datasets, and experimental results show that our method achieves state-of-the-art performance across various data settings, validating its effectiveness and superiority. The code will be available at https://github.com/lhq12/SemiFed.

Real-world data often exhibits a long-tailed distribution, which fuels growing research interest in long-tailed object detection (LTOD) from both academia and industry. However, existing methods primarily focus on the head-tail imbalance issue in LTOD, neglecting the more critical issue of tail class data scarcity. This leads to overfitting on tail classes and poor performance as a whole. This paper addresses both tail class data scarcity and head-tail imbalance by proposing a Dual-Model framework named DuMo, which tackles the two challenges by two separate models, and then merges them by knowledge transfer to ensure superior performance across the entire class space. Specifically, DuMo consists of a tail class expert model (EM) and a base model (BM). EM is dedicated to detecting scarce tail classes, and enhanced by a tail class feature augmentation (TCFA) module that uses CLIP-generated semantic embeddings to diversify the tail class features. On the other hand, BM handles head-tail imbalance by employing a class-specific margin loss (CSML), which moves the decision boundary toward the underrepresented tail classes, thus reducing the suppression from head classes. Finally, a knowledge transfer (KT) module transfers expertise from EM to BM, which further enhances BM’s performance on tail classes and ensures robust detection across all classes. Extensive experiments on LVIS v1.0 and LVIS-X validate the effectiveness of the proposed method DuMo.

Offline reinforcement learning seeks to derive improved policies entirely from historical data but often struggles with over-optimistic value estimates for out-of-distribution (OOD) actions. This issue is typically mitigated via policy constraint or conservative value regularization methods. However, these approaches may impose overly constraints or biased value estimates, potentially limiting performance improvements. To balance exploitation and restriction, we propose an Imagination-Limited Q-learning (ILQ) method, which aims to maintain the optimism that OOD actions deserve within appropriate limits. Specifically, we utilize the dynamics model to imagine OOD action-values, and then clip the imagined values with the maximum behavior values. Such design maintains reasonable evaluation of OOD actions to the furthest extent, while avoiding its over-optimism. Theoretically, we prove the convergence of the proposed ILQ under tabular Markov decision processes. Particularly, we demonstrate that the error bound between estimated values and optimality values of OOD state-actions possesses the same magnitude as that of in-distribution ones, thereby indicating that the bias in value estimates is effectively mitigated. Empirically, our method achieves state-of-the-art performance on a wide range of tasks in the D4RL benchmark.

In many real-world scenarios, the goal is to identify variables whose causal mechanisms change across related datasets. For example, detecting abnormal root nodes in manufacturing, and identifying key genes that influence cancer by analyzing differences in gene regulatory mechanisms between healthy individuals and cancer patients. This can be done by recovering the causal structure for each dataset independently and then comparing them to identify differences, but the performance is often suboptimal. Typically, existing methods directly identify causal mechanism shifts based on linear additive noise models (ANMs) or by imposing restrictive assumptions on the noise distribution. In this paper, we introduce CMSI, a novel and more general algorithm based on nonlinear ANMs that identifies variables with shifting causal mechanisms under arbitrary noise distributions. Evaluated on various synthetic datasets, CMSI consistently outperforms existing baselines in terms of F1 score. Additionally, we demonstrate CMSI's applicability on gene expression datasets of ovarian cancer patients at different disease stages.

We address the identification of direct causes in time series with multiple time lags, and propose a constraint-based window causal graph discovery method. A key advantage of our method is that the number of required conditional independence (CI) tests scales quadratically with the number of sub-series. The method first uses CI tests to find the minimum trek lag between two arbitrary sub-series, followed by designing an efficient CI testing strategy to identify the direct causes between them. We show that the method is both sound and complete under some graph constraints. We compare the proposed method with typical baselines on various datasets. Experimental results show that our method outperforms all the counterparts in both accuracy and running speed.

Determining conditional independence (CI) relationships between random variables is a fundamental yet challenging task in machine learning and statistics, especially in high-dimensional settings. Existing generative model-based CI testing methods, such as those utilizing generative adversarial networks (GANs), often struggle with undesirable modeling of conditional distributions and training instability, resulting in subpar performance. To address these issues, we propose a novel CI testing method via score-based generative modeling, which achieves precise Type I error control and strong testing power. Concretely, we first employ a sliced conditional score matching scheme to accurately estimate conditional score and use Langevin dynamics conditional sampling to generate null hypothesis samples, ensuring precise Type I error control. Then, we incorporate a goodness-of-fit stage into the method to verify generated samples and enhance interpretability in practice. We theoretically establish the error bound of conditional distributions modeled by score-based generative models and prove the validity of our CI tests. Extensive experiments on both synthetic and real-world datasets show that our method significantly outperforms existing state-of-the-art methods, providing a promising way to revitalize generative model-based CI testing.

Zero-shot object detection (ZSD) aims to leverage semantic descriptions to localize and recognize objects of both seen and unseen classes. Existing ZSD works are mainly coarse-grained object detection, where the classes are visually quite different, thus are relatively easy to distinguish. However, in real life we often have to face fine-grained object detection scenarios, where the classes are too similar to be easily distinguished. For example, detecting different kinds of birds, fishes, and flowers. In this paper, we propose and solve a new problem called Fine-Grained Zero-Shot Object Detection (FG-ZSD for short), which aims to detect objects of different classes with minute differences in details under the ZSD paradigm. We develop an effective method called MSHC for the FG-ZSD task, which is based on an improved two-stage detector and employs a multi-level semantics-aware embedding alignment loss, ensuring tight coupling between the visual and semantic spaces. Considering that existing ZSD datasets are not suitable for the new FG-ZSD task, we build the first FG-ZSD benchmark dataset FGZSD-Birds, which contains 148,820 images falling into 36 orders, 140 families, 579 genera and 1432 species. Extensive experiments on FGZSD-Birds show that our method outperforms existing ZSD models.

Recently, numerous benchmarks have been constructed to evaluate various general capabilities (e.g., perception and reasoning) of Vision-Language Large Models (VLLMs). However, few studies have focused on the robustness of VLLMs when dealing with altered prompts and images. To fill this gap, this paper first constructs a real-world, high-quality, and challenging benchmark, namely RBench (i.e., Robust Bench). Specifically, RBench is human-annotated, with both prompts and images being modified to enrich the difficulty, and cross-validation to ensure data quality. Then, we propose a new method, called Robustness Booster (RBoost in short), to effectively enhance the robustness of existing VLLMs by automatically generating high-value instruction-tuning training data. Extensive experiments demonstrate the vulnerability of existing VLLMs when handling altered inputs, and the superiority of our RBoost method in improving model robustness. RBench is available at https://github.com/zhaominyiz/RBench.

Training Large Language Models (LLMs) is prohibitively expensive, creating a critical scaling gap where insights from small-scale experiments often fail to transfer to resource-intensive production systems, thereby hindering efficient innovation. To bridge this, we introduce Farseer, a novel and refined scaling law offering enhanced predictive accuracy across scales. By systematically constructing a model loss surface $L(N,D)$, Farseer achieves a significantly better fit to empirical data than prior laws (e.g., \Chinchilla's law). Our methodology yields accurate, robust, and highly generalizable predictions, demonstrating excellent extrapolation capabilities, outperforming Chinchilla's law, whose extrapolation error is 433\% higher. This allows for the reliable evaluation of competing training strategies across all $(N,D)$ settings, enabling conclusions from small-scale ablation studies to be confidently extrapolated to predict large-scale performance. Furthermore, Farseer provides new insights into optimal compute allocation, better reflecting the nuanced demands of modern LLM training. To validate our approach, we trained an extensive suite of approximately 1,000 LLMs across diverse scales and configurations, consuming roughly 3 million NVIDIA H100 GPU hours. To foster further research, we are comprehensively open-sourcing all code, data, results (https://github.com/Farseer-Scaling-Law/Farseer), all training logs (https://wandb.ai/billzid/Farseer?nw=nwuserbillzid), all models used in scaling law fitting (https://huggingface.co/Farseer-Scaling-Law).

Long-term prediction of Sea Surface Temperature (SST) is a pervasive issue in ocean science, particularly for understanding climate changes and improving marine disaster risk assessment. However, existing approaches typically focus either on short-term or long-term coarse-grained prediction, due to their limited ability to overcome noise interference and model complex spatio-temporal dependencies in long SST sequences. To overcome these limitations, we proposed a novel spatio-temporal decomposition Mamba model, termed STDMamba, for long-term fine-grained SST prediction. First, we introduce a Gaussian-weighted series decomposition module with smoothing mechanisms to decompose SST sequences into trend and fluctuation components, thereby mitigating noise interference. Then, we design a dual spatio-temporal representation learning module which utilizes Mamba2 to effectively capture the long-term spatio-temporal dependencies in the fluctuation component, and employs a Temporal Convolutional Network (TCN) to learn the spatio-temporal feature representation of the trend component. Finally, the dual representations are fused and passed through a prediction layer to generate the long-term fine-grained SST prediction results. Experiments on real-world datasets demonstrate that STDMamba significantly outperforms state-of-the-art prediction models. The code of STDMamba is available at https://github.com/ADMIS-TONGJI/STDMamba.

Few-shot object detection (FSOD) has been proposed to solve the problem of insufficient data for training, and it has drawn the attention of the remote sensing community in recent years. A mainstream type of FSOD method is to generate class prototypes based on the limited samples to help the construction of classification decision boundaries. However, these constructed prototypes may be far away from the true class centroids in the few-shot scenario. Recently, the vision-language model (VLM) has shown its powerful ability to align the visual features and text features, which leads to strong zero-shot performance on various downstream computer vision tasks when given only texts. Therefore, in this work, we propose to build class prototypes from text descriptions instead of limited visual instances by leveraging a classical pretrained VLM named CLIP. Concretely, we generate prototypes by feeding the CLIP text encoder with class names and enforcing each positive proposal feature to be close to the corresponding prototype. To accelerate the alignment process, we utilize the CLIP visual encoder as another teacher to achieve visual knowledge distillation. Moreover, we adopt prompt tuning to adapt CLIP to the remote sensing scenario. Extensive experiments on two public FSOD datasets, i.e., DIOR and NWPU VHR-10.v2, demonstrate the effectiveness of our method, which yields competitive results with that of existing approaches.

Remote sensing data are of considerable significance for monitoring global climate, detecting harmful algae bloom, and so on. However, due to sensor failures, cloud cover, and thick aerosols, the collected remote sensing data for various ocean factors, such as chlorophyll-a (Chl-a) concentration and sea surface temperature (SST), often have a high missing rate, which seriously hinders their applications. Existing data imputation models mostly ignore highly sparse spatial locations or perform badly when the data missing rate is high due to the lack of available information. Large language models (LLMs) possess powerful representation learning capabilities and can effectively capture sequential correlations even with extremely limited information, thereby presenting the promising potential for highly sparse remote sensing data imputation. Therefore, we proposed a novel LLM-based spatiotemporal model for highly sparse remote sensing data imputation, i.e., LLM4HRS. First, LLM4HRS develops an LLM-based bidirectional temporal representation learning module to learn forward and backward temporal dependencies in data sequences and fuses them together to obtain comprehensive temporal representations. Next, LLM4HRS constructs a LLM-based spatial representation learning module to learn spatial correlations with the learned temporal representation. Finally, a spatiotemporal representation fusion and data imputation module is developed to achieve data imputation. Experiments on the SST and Chl-a remote sensing datasets demonstrate that LLM4HRS significantly outperforms existing data imputation models, with its advantages becoming more pronounced as the masking rate increases. Furthermore, when extended to the remote sensing PAR data in a large region, LLM4HRS still achieves the best performance, further validating its broad applicability for remote sensing data imputation. The code of LLM4HRS is publicly available athttps://github.com/ssyuwang/LLM4HRS-master.

Accurate prediction of Sea Surface Temperature (SST) is of high importance in marine science, benefiting applications ranging from ecosystem protection to extreme weather forecasting and climate analysis. Wide-area SST usually shows diverse SST patterns in different sea areas due to the changes of temperature zones and the dynamics of ocean currents. However, existing studies on SST prediction often focus on small-area predictions and lack the consideration of diverse SST patterns. Furthermore, SST shows an annual periodicity, but the periodicity is not strictly adherent to an annual cycle. Existing SST prediction methods struggle to adapt to this non-strict periodicity. To address these two issues, we proposed the Cross-Region Graph Convolutional Network with Periodicity Shift Adaptation (RGCN-PSA) model which is equipped with the Cross-Region Graph Convolutional Network module and the Periodicity Shift Adaption module. The Cross-Region Graph Convolutional Network module enhances wide-area SST prediction by learning and incorporating diverse SST patterns. Meanwhile, the periodicity Shift Adaptation module accounts for the annual periodicity and enable the model to adapt to the possible temporal shift automatically. We conduct experiments on two real-world SST datasets, and the results demonstrate that our RGCN-PSA model obviously outperforms baseline models in terms of prediction accuracy. The code of RGCN-PSA model is available at https://github.com/ADMIS-TONGJI/RGCN-PSA/ .

With the growing diversity of data formats on social media, such as text, images, and videos, there is a growing need to analyze sentiment from multiple modalities. Multimodal sentiment detection, which aims to identify users’ sentiment by jointly modeling information from different modalities, has thus attracted increasing attention. However, most existing multimodal sentiment detection methods fuse multimodal information directly after the unimodal encoding and overlook the modality consistency of multimodal vector spaces before the fusion, which may damage the accuracy of multimodal sentiment detection. To address this issue, we propose a contrastive learning-based multimodal sentiment detection model termed EPMC which can map the representations of different modalities into a unified semantic space before fusion. EPMC operates in two stages, i.e., pre-training stage and fine-tuning stage. At the pre-training stage, we designed a cross-modal transformation module to map different modalities into a unified feature space. Meanwhile, to further capture the relationship between the cross-modal transformation vectors and the unimodal encoding vectors, we propose a multimodal consistency contrastive learning task that helps the model discern and amplify the cross-modal similarity between different modalities, thereby learning more discriminative features for sentiment detection. At the fine-tuning stage, EPMC is iteratively refined using the learned multimodal representation and guided by the cross-entropy loss. Extensive experiments conducted on three public multimodal datasets validate the effectiveness of EPMC model. The official implementation of EPMC is released at https://github.com/ADMIS-TONGJI/EPMC .

Given a specific region, crime prediction aims to predict the occurrence of various crime events within a certain period of time in future, which is of high significance for guaranteeing urban safety. In practice, crime events are usually affected by a variety of factors from different views, e.g., the attributes of the region, the correlations between different regions, and the correlations between different categories of crime events. Moreover, these correlations are dynamically changing over time, which makes it difficult to learn the regularity and patterns in crime data for achieving accurate prediction. To address this issue, we proposed a new M ulti- V iew S patial- T emporal (MVST) model for fine-grained crime prediction. MVST model first builds a static region graph to capture the similarity between regions in terms of region attributes such as census records and economy statistics, and creates a time-dependent graph to capture the dynamic correlations between regions based on human mobility data. Meanwhile, both static and dynamic graphs are created to capture the correlations between different categories of crime events. After that, those graphs created from different views are fused together with a multi-view graph fusion module to achieve crime prediction with fine-grained time granularities, e.g., 4 hours and 12 hours. According to the experiments on two real crime datasets, our MVST model obviously outperforms existing crime prediction methods. The code of MVST model is available at https://github.com/weichang811/MVST .

Inductive relation prediction, an important task for knowledge graph completion, is to predict the relations between entities that are unseen at the training stage. The latest methods use Pre-Trained Language Models (PLMs) to encode the paths between the head entity and tail entity and achieve state-of-the-art prediction performance. However, these methods cannot handle no-path scenarios well and lack the capability to learn comprehensive relation representations for distinguishing different relations. To tackle this issue, we propose a novel R elation- a ware k nowledg e r easoning model entitled Raker, which introduces an adaptive reasoning information extraction method to identify relation-aware reasoning neighbors of entities in the target triple to handle no-path scenarios and enables the PLM to better distinguish different relations via the relation-specific soft prompting. Raker is evaluated on three public datasets and achieves SOTA performance in inductive relation prediction when compared with the baseline methods. Notably, the absolute improvement of Raker is even more than 5% on the FB15k-237 dataset in the inductive setting. Moreover, Raker also demonstrates the superiority in transductive, few-shot, and unseen relation settings. The code of Raker is available at https://github.com/ADMIS-TONGJI/Raker .

With the rapid amassing of spatial-temporal (ST) ocean data, many spatial-temporal data mining (STDM) studies have been conducted to address various oceanic issues, including climate forecasting and disaster warning. Compared with typical ST data (e.g., traffic data), ST ocean data presents some unique characteristics, e.g., diverse regionality and high sparsity. These characteristics make it difficult to design and train STDM models on ST ocean data. To the best of our knowledge, a comprehensive survey of existing studies remains missing in the literature, which hinders not only computer scientists from identifying the research issues in ocean data mining but also ocean scientists to apply advanced STDM techniques. In this article, we provide a comprehensive survey of existing STDM studies for ocean science. Concretely, we first review the widely used ST ocean datasets and highlight their unique characteristics. Then, typical ST ocean data quality enhancement techniques are discussed. Next, we classify existing STDM studies for ocean science into four types of tasks, i.e., prediction, event detection, pattern mining, and anomaly detection, and elaborate the techniques for these tasks. Finally, promising research opportunities are discussed. This survey can help scientists from both computer science and ocean science better understand the fundamental concepts, key techniques, and open challenges of STDM for ocean science.

Accurate spatial-temporal (ST) traffic prediction plays an essential role in intelligent transportation systems. Existing advanced traffic prediction methods typically utilize spatial-temporal graph neural networks (STGNNs) to capture the ST correlations and achieve excellent prediction performance. However, our experimental investigation reveals that existing static and dynamic graph-based STGNNs still incur excessive noise and redundancy, and fail to discover robust and reliable ST correlations in traffic networks. Moreover, most methods cannot explain the underlying reasons behind the ST correlations. To solve these problems, we propose a novel S patial- T emporal G raph M odeling framework via A daptive contrastive learning (ST-GMA). Firstly, we design a robust augmentation learning module to generate high-level and robust data augmentations via a self-supervised task for modeling reliable correlations. Then, we develop an adaptive contrastive learning module to update correlation graphs by effectively selecting positive and negative augmentations, reducing redundant calculations, and providing insights into the correlation changes. Finally, ST-GMA integrates the generated correlation graphs with ST convolution blocks to conduct traffic prediction tasks. Experimental results on five real-world datasets demonstrate that ST-GMA not only achieves significant prediction performance compared with state-of-the-art methods but also exhibits a new perspective on the interpretability of correlation changes.

Temporal causal discovery is a crucial task aimed at uncovering the causal relations within time series data. The latest temporal causal discovery methods usually train deep learning models on prediction tasks to uncover the causality between time series. They capture causal relations by analyzing the parameters of some components of the trained models, e.g., attention weights and convolution weights. However, this is an incomplete mapping process from the model parameters to the causality and fails to investigate the other components, e.g., fully connected layers and activation functions, that are also significant for causal discovery. To facilitate the utilization of the whole deep learning models in temporal causal discovery, we proposed an interpretable transformer-based causal discovery model termed CausalFormer, which consists of the causality-aware transformer and the decomposition-based causality detector. The causality-aware transformer learns the causal representation of time series data using a prediction task with the designed multi-kernel causal convolution which aggregates each input time series along the temporal dimension under the temporal priority constraint. Then, the decomposition-based causality detector interprets the global structure of the trained causality-aware transformer with the proposed regression relevance propagation to identify potential causal relations and finally construct the causal graph. Experiments on synthetic, simulated, and real datasets demonstrate the state-of-the-art performance of CausalFormer on discovering temporal causality.

Debt collection is utilized for risk control after credit card delinquency. The existing rule-based method tends to be myopic and non-adaptive due to the delayed feedback. Reinforcement learning (RL) has an inherent advantage in dealing with such task and can learn policies end-to-end. However, employing RL here remains difficult because of different interaction processes from standard RL and the notorious problem of optimistic estimations in the offline setting. To tackle these challenges, we first propose an Alternating Q-Learning (AQL) framework to adapt debt collection processes to comparable procedures in RL. Based on AQL, we further develop an Adversarial Conservative Alternating Q-Learning (ACAQL) to address the issue of overoptimistic estimations. Specifically, adversarial conservative value regularization is proposed to balance optimism and conservatism on Q-values of out-of-distribution actions. Furthermore, ACAQL utilizes the counterfactual action stitching to mitigate the overestimation by enhancing behavior data. Finally, we evaluate ACAQL on a real-world dataset created from Bank of Shanghai. Offline experimental results show that our approach outperforms state-of-the-art methods and effectively alleviates the optimistic estimation issue. Moreover, we conduct online A/B tests on the bank, and ACAQL achieves at least a$\emph {6\%}$improvement of the debt recovery rate, which yields tangible economic benefits.

In recent years, Few-shot Object Detection (FSOD) has become an increasingly important research topic in computer vision. However, existing FSOD methods require strong annotations including category labels and bounding boxes, and their performance is heavily dependent on the quality of box annotations. However, acquiring strong annotations is both expensive and time-consuming. This inspires the study on weakly supervised FSOD (WS-FSOD in short), which realizes FSOD with only image-level annotations, i.e., category labels. In this paper, we propose a new and effective weakly supervised FSOD method named WFS-DETR. By a well-designed pretraining process, WFS-DETR first acquires general object localization and integrity judgment capabilities on large-scale pretraining data. Then, it introduces object integrity into multiple-instance learning to solve the common local optimum problem by comprehensively exploiting both semantic and visual information. Finally, with simple fine-tuning, it transfers the knowledge learned from the base classes to the novel classes, which enables accurate detection of novel objects. Benefiting from this ``pretraining-refinement'' mechanism, WSF-DETR can achieve good generalization on different datasets. Extensive experiments also show that the proposed method clearly outperforms the existing counterparts in the WS-FSOD task.

We propose a novel framework for kernel-based statistical independence tests that enable adaptatively learning parameterized kernels to maximize test power. Our framework can effectively address the pitfall inherent in the existing signal-to-noise ratio criterion by modeling the change of the null distribution during the learning process. Based on the proposed framework, we design a new class of kernels that can adaptatively focus on the significant dimensions of variables to judge independence, which makes the tests more flexible than using simple kernels that are adaptive only in length-scale, and especially suitable for high-dimensional complex data. Theoretically, we demonstrate the consistency of our independence tests, and show that the non-convex objective function used for learning fits the L-smoothing condition, thus benefiting the optimization. Experimental results on both synthetic and real data show the superiority of our method. The source code and datasets are available at \url{https://github.com/renyixin666/HSIC-LK.git}.

Single-cell RNA sequencing (scRNA-seq) enables researchers to analyze gene expression at single-cell level. One important task in scRNA-seq data analysis is unsupervised clustering, which helps identify distinct cell types, laying down the foundation for other downstream analysis tasks. In this paper, we propose a novel method called Cluster-aware IteRative Contrastive LEarning (CIRCLE in short) for scRNA-seq data clustering, which uses an iterative representation learning and clustering framework to progressively learn the clustering structure of scRNA-seq data with a cluster-aware contrastive loss. CIRCLE consists of a Transformer encoder, a clustering head, a projection head and a contrastive loss. First, CIRCLE extracts the feature vectors of the original and augmented data by the Transformer-encoder. Then, it computes the clustering centroids by K-means and employs the student’s t-distribution to assign pseudo-labels to all cells in the clustering head. The projection-head uses a Multi-Layer Perceptron (MLP) to obtain projections of the augmented data. At last, both pseudo-labels and projections are used in the contrastive loss to guide the model training. Such a process goes iteratively so that the clustering result gets better and better. Extensive experiments on 25 real-world scRNA-seq datasets show that CIRCLE outperforms the state-of-the-art (SOTA) methods in most cases. Concretely, CIRCLE surpasses the existing methods by from 14% to 280%, and from 5% to 133% on average in terms of performance metrics ARI and NMI respectively. Source code is available at https://github.com/Alunethy/CIRCLE.

The widespread adoption of face recognition has led to increasing privacy concerns, as unauthorized access to face images can expose sensitive personal information. This paper explores face image protection against viewing and recovery attacks. Inspired by image compression, we propose creating a visually uninformative face image through feature subtraction between an original face and its model-produced regeneration. Recognizable identity features within the image are encouraged by co-training a recognition model on its high-dimensional feature represen-tation. To enhance privacy, the high-dimensional represen-tation is crafted through random channel shuffling, resulting in randomized recognizable images devoid of attacker-leverageable texture details. We distill our methodologies into a novel privacy-preserving face recognition method, MinusFace. Experiments demonstrate its high recognition accuracy and effective privacy protection. Its code is avail-able at https://github.com/Tencent/TFace.

The task of multivariate time series (MTS) forecasting has attracted much attention in recent years. However, most existing methods overlook the causal relationship among different variables, which may lead to inaccurate forecasting results. In this paper, we incorporate causality into the forecasting procedure of MTS. We first use a causal discovery algorithm to obtain the causal graph of the MTS and then design a novel Causal-Temporal Attention Mechanism to encode the causal graph and the MTS into a set of feature tensors. Finally, a linear decoder is adopted to derive the forecasting results from the feature tensors. Experiment results on five real-world datasets indicate that our method outperforms the state-of-the-art models. Moreover, extra experiments are conducted to validate the effectiveness of hyperparameters and the modules in our method.

Real-world data ubiquitously exhibit long-tailed distribution, which sparks the increasing interest in long-tailed object detection (LTOD). However, existing methods neglect that a lack of diverse data in tail classes will cause underrepresented tail class features, making their efforts for balancing foreground classes tend to over-fit tail classes and be less effective. In this paper, we propose a multi-class co-attention generation network to increase data diversity of tail classes by generating augmented samples. To alleviate imbalance, we develop a distribution-aware up-sampling strategy, performing differential up-sampling for different classes and design a bi-directional regulation loss to adjust both positive and negative gradients. Moreover, we construct a new dataset LVIS-X with more rare classes based on existing LTOD benchmark dataset LVIS. Experiments on LVIS and LVIS-X demonstrate the superiority of the proposed method.

Traditional graph classification requires large amounts of labeled data, which is expensive and time-consuming to acquire, especially in some special scenarios that domain knowledge is indispensable for labeling graphs. Observing that some key subgraphs can determine the properties of graphs (e.g. the toxicity of drug molecules depend on some toxic functional groups), in this paper we explore to classify graphs using unlabeled graphs plus a small number of key subgraphs for each class, which is called weakly-supervised graph classification. To this end, we develop the WeGraph method, where the graph classifier is trained with subgraph-based self-supervised learning and divergence- minimization based fine-tuning. Moreover, we design a key subgraph extraction algorithm to iteratively extract and update the key subgraphs, which makes the training process a closed loop. We conduct extensive experiments on different types of graph datasets to evaluate the effectiveness of WeGraph. Experimental results show that WeGraph can achieve high performance even when only one key subgraph is provided for each class.

We propose a novel method to efficiently learn significant Fourier feature pairs for maximizing the power of Hilbert-Schmidt Independence Criterion~(HSIC) based independence tests. We first reinterpret HSIC in the frequency domain, which reveals its limited discriminative power due to the inability to adapt to specific frequency-domain features under the current inflexible configuration. To remedy this shortcoming, we introduce a module of learnable Fourier features, thereby developing a new criterion. We then derive a finite sample estimate of the test power by modeling the behavior of the criterion, thus formulating an optimization objective for significant Fourier feature pairs learning. We show that this optimization objective can be computed in linear time (with respect to the sample size $n$), which ensures fast independence tests. We also prove the convergence property of the optimization objective and establish the consistency of the independence tests. Extensive empirical evaluation on both synthetic and real datasets validates our method's superiority in effectiveness and efficiency, particularly in handling high-dimensional data and dealing with large-scale scenarios.

MOTIVATION: Molecular property prediction (MPP) is a fundamental but challenging task in the computer-aided drug discovery process. More and more recent works employ different graph-based models for MPP, which have achieved considerable progress in improving prediction performance. However, current models often ignore relationships between molecules, which could be also helpful for MPP. RESULTS: For this sake, in this article we propose a graph structure learning (GSL) based MPP approach, called GSL-MPP. Specifically, we first apply graph neural network (GNN) over molecular graphs to extract molecular representations. Then, with molecular fingerprints, we construct a molecule similarity graph (MSG). Following that, we conduct GSL on the MSG, i.e. molecule-level GSL, to get the final molecular embeddings, which are the results of fuzing both GNN encoded molecular representations and the relationships among molecules. That is, combining both intra-molecule and inter-molecule information. Finally, we use these molecular embeddings to perform MPP. Extensive experiments on 10 various benchmark datasets show that our method could achieve state-of-the-art performance in most cases, especially on classification tasks. Further visualization studies also demonstrate the good molecular representations of our method. AVAILABILITY AND IMPLEMENTATION: Source code is available at https://github.com/zby961104/GSL-MPP.

Causal partitioningis an effective approach for causal discovery based on the divide-and-conquer strategy. Up to now, various heuristic methods based on conditional independence (CI) tests have been proposed for causal partitioning. However, most of these methods fail to achieve satisfactory partitioning without violating$d$-separation, leading to poor inference performance. In this work, we transform causal partitioning into an alternative problem that can be more easily solved. Concretely, we first construct a superstructure$G$of the true causal graph$G_{\mathcal {T}}$by performing a set of low-order CI tests on the observed data$D$. Then, we leverage point-line duality to obtain a graph$G_\mathcal {A}$adjoint to$G$. We show that the solution ofminimizing edge-cut ratioon$G_\mathcal {A}$can lead to a valid causal partitioning withsmaller causal-cut ratioon$G$andwithout violating$d$d-separation. We design an efficient algorithm to solve this problem. Extensive experiments show that the proposed method can achieve significantly better causal partitioning without violating$d$-separation than the existing methods.

Existing multimodal sentiment analysis models focus more on fusing highly correlated image-text pairs, and thus achieves unsatisfactory performance on multimodal social media data which usually manifests weak correlations between different modalities. To address this issue, we first build a large multimodal social media sentiment analysis dataset RU-Senti which contains more than 100,000 image-text pairs with sentiment labels. Then, we proposed a topic-oriented model (TOM) which assumes that text is usually related to a certain portion of the image contents and significant variances exist in sentiment distribution across diverse topics. TOM learns the topic information from textual content and designs a topic-oriented feature alignment module to extract textual semantics correlated information from images, thus achieving the alignment between two modalities. Then, TOM utilizes a transformer encoder initialized with the parameters from a pre-trained vision-language model to fuse the multimodal features for sentiment prediction. According to the experiments over the public MVSA-Multiple dataset and our RU-Senti dataset, RU-Senti is of high suitability for studying weakly correlated multimodal sentiment analysis, and the proposed TOM model also largely outperforms the SOTA mulitimodal sentiment analysis methods and pre-trained vision-language models.

In the past decade, Artificial Intelligence (AI) driven drug design and discovery has been a hot research topic in the AI area, where an important branch is molecule generation by generative models, from GAN-based models and VAE-based models to the latest diffusion-based models. However, most existing models pursue mainly the basic properties like validity and uniqueness of the generated molecules, a few go further to explicitly optimize one single important molecular property (e.g. QED or PlogP), which makes most generated molecules little usefulness in practice. In this paper, we present a novel approach to generating molecules with desirable properties, which expands the diffusion model framework with multiple innovative designs. The novelty is two-fold. On the one hand, considering that the structures of molecules are complex and diverse, and molecular properties are usually determined by some substructures (e.g. pharmacophores), we propose to perform diffusion on two structural levels: molecules and molecular fragments respectively, with which a mixed Gaussian distribution is obtained for the reverse diffusion process. To get desirable molecular fragments, we develop a novel electronic effect based fragmentation method. On the other hand, we introduce two ways to explicitly optimize multiple molecular properties under the diffusion model framework. First, as potential drug molecules must be chemically valid, we optimize molecular validity by an energy-guidance function. Second, since potential drug molecules should be desirable in various properties, we employ a multi-objective mechanism to optimize multiple molecular properties simultaneously. Extensive experiments with two benchmark datasets QM9 and ZINC250 k show that the molecules generated by our proposed method have better validity, uniqueness, novelty, Fréchet ChemNet Distance (FCD), QED, and PlogP than those generated by current SOTA models.

The discovery of cancer biomarkers helps to advance medical diagnosis and plays an important role in biomedical applications. Most of the existing data-driven methods identify biomarkers by ranking-based strategies, which generally return a subset or superset of the actual biomarkers, while some other causal-wise feature selection methods are based on Markov Blanket (MB) learning, facing the challenges of high-dimensionality & low-sample. In this work, we propose a novel hybrid causal feature selection method (called CAFES) to support large-scale cancer biomarker discovery from real RNA-seq data. Concretely, CAFES first uses minimal-redundancy & maximal-relevance strategy for dimensionality reduction that returns a set of candidate features. CAFES then learns the causal skeleton w.r.t. those features by CI tests and further obtains an appropriate superset of the MB of the target variable. Finally, CAFES learns the causal structure of this superset by the DAG-GNN algorithm and then obtains the MB of the target variable, which can be treated as the cancer biomarkers. We conduct experiments to evaluate the proposed method on two real well-known RNA-seq datasets that covering both binary and multi-class cases. We compare our method CAFES with seven recent methods including Semi-HITON-MB, STMB, BAMB, FBED, LCS-FS, EEMB, and EAMB. The results show that CAFES can identify dozens of cancer biomarkers, and of the discovered biomarkers can be verified by existing works that they are really directly related to the corresponding disease. An advantage of CAFES is that its Recall is significantly higher than those of all the counterparts, indicating that the continuous optimization (DAG-GNN) with the returned causal skeleton after feature selection (that can be treated as a conditional independence-based constraint to the optimization problem) is effective in cancer biomarkers identification under high-dimensional and low-sample RNA-seq data.

Monitoring Chlorophyll-a (Chl-a) concentration in ocean is of considerable significance for early warning of algae disasters, marine ecological environment protection, etc. However, due to various uncontrollable factors such as cloud cover and thick aerosols, the missing rate of observed Chl-a data is quite high, which seriously hinders its applications. The existing data imputation methods are mostly applicable to Chl-a data with a low missing rate, and perform much worse when the missing rate reaches 0.7 or above. To address this issue, we proposed a self-supervised spatiotemporal imputation (S2-STI) model for highly sparse Chl-a data imputation by fusing multisource satellite data. First, to obtain comprehensive information about the missed Chl-a data, we designed a multisource sparse data fusion (MSDF) module to fuse multisource satellite data, including Chl-a data, sea surface temperature (SST) data, and photosynthetically available radiation data. MSDF constructs a spatialtemporal graph network to learn high-quality spatiotemporal representations of SST and photosynthetically active radiation (PAR) data, and fuses the learned representations with Chl-a data to enrich the information for imputation. Then, we developed a generation-based data imputation (GDI) module to model the distribution of Chl-a data based on the outputs of MSDF. Considering the high data sparsity, we designed a self-supervised training strategy to train S2-STI in the absence of ground truth. Finally, we leverage the data generated by the GDI module in the trained S2-STI model to fill in missing values in the sparse Chl-a data. Experiments on real datasets show that S2-STI achieves much better performance than the existing data imputation methods. Specifically, for the Chl-a data with a missing rate of 0.9, S2-STI improves by at least 12% in terms of masked autoencoder (MAE) error when compared with the strong baseline methods.

Accurate prediction of ocean factors (e.g., temperature and salinity) is crucial for plenty of applications, including weather forecasting, storm tracking, and ecosystem protection. Meanwhile, it is well-known that the ocean is a unified system and various ocean factors usually influence each other. For example, the changes in temperature would affect the distribution of salinity in ocean. However, the existing studies for ocean factor prediction mainly focus on designing individual models for predicting specific factors and ignore the correlations between different factors, thus having potentials to be further improved. Therefore, we propose a unified framework UniOcean to predict multiple ocean factors simultaneously, and capture the correlations between them to improve the prediction accuracy. First, considering that ocean factors are usually collected with different temporal scales, we develop the fine-grained multiscale data fusion module to integrate multiple ocean factors with different temporal scales, and effectively learn their hierarchical patterns at different levels. Then, since the correlations between ocean factors may vary across different time periods, the multifactor correlation learning module is constructed to adaptively learn the dynamic correlations between different factors. Finally, we utilize the factor-specific towers to predict multiple ocean factors simultaneously. Experimental results on five real-world remote sensing datasets demonstrate that UniOcean significantly improves the prediction accuracy by 11%–53% in terms of MSD for different ocean factors.

Multivariate Time Series Anomaly Detection (MTS-AD) is crucial for the effective management and maintenance of devices in complex systems, such as server clusters, spacecrafts, and financial systems, and so on. However, upgrade or cross-platform deployment of these devices will introduce the issue of cross-domain distribution shift, which leads to the prototypical problem of domain adaptation for MTS-AD. Compared with general domain adaptation problems, MTS-AD domain adaptation presents two peculiar challenges: (1) the dimensions of data from the source domain and the target domain are usually different, so alignment without losing any information is necessary; and (2) the association between different variates plays a vital role in the MTS-AD task, which is overlooked by traditional domain adaptation approaches. Aiming at addressing the above issues, we propose a Variate Associated Domain Adaptation Method Combined with a Graph Deviation Network (VANDA) for MTS-AD, which includes two major contributions. First, we characterize the intra-domain variate associations of the source domain by a graph deviation network (GDN), which can share parameters across domains without dimension alignment. Second, we propose a sliding similarity to measure the inter-domain variate associations and perform joint training by minimizing the optimal transport distance between source and target data for transferring variate associations across domains. VANDA achieves domain adaptation by transferring both variate associations and GDN parameters from the source domain to the target domain. We construct two pairs of MTS-AD datasets from existing MTS-AD data and combine three domain adaptation strategies with six MTS-AD backbones as the benchmark methods for experimental evaluation and comparison. Extensive experiments demonstrate the effectiveness of our approach, which outperforms the benchmark methods, and significantly improves the AD performance of the target domain by effectively utilizing the source domain knowledge.

Incremental maximal clique enumeration (IMCE), which maintains maximal cliques in dynamic graphs, is a fundamental problem in graph analysis. A maximal clique has a solid descriptive power of dense structures in graphs. Real-world graph data is often large and dynamic. Studies on IMCE face significant challenges in the efficiency of incremental batch computation and hybrid edge changes. Moreover, with growing graph sizes, new requirements occur on indexing global maximal cliques and obtaining maximal cliques under specific vertex scope constraints. This work presents a new data structure SOMEi to maintain intermediate maximal cliques during construction. SOMEi serves as a space-efficient index to retrieve scope-constrained maximal cliques on the fly. Based on SOMEi, we design a procedure-oriented IMCE algorithm to deal with hybrid edge changes within a unified algorithm framework. In particular, the algorithm is able to process a large batch of edge changes and significantly improve the average processing time of a single edge change through an efficient pruning strategy. Experimental results on real and synthetic graph data demonstrate that the proposed algorithm outperforms all the baselines and achieves good efficiency through pruning.

Recently, several methods such as private ANM, EM-PC and Priv-PC have been proposed to perform differentially private causal discovery in various scenarios including bivariate, multivariate Gaussian and categorical cases. However, there is little effort on how to conduct private nonlinear causal discovery from numerical data. This work tries to challenge this problem. To this end, we propose a method to infer nonlinear causal relations from observed numerical data by using regression-based conditional independence test (RCIT) that consists of kernel ridge regression (KRR) and Hilbert-Schmidt independence criterion (HSIC) with permutation approximation. Sensitivity analysis for RCIT is given and a private constraint-based causal discovery framework with differential privacy guarantee is developed. Extensive simulations and real-world experiments for both conditional independence test and causal discovery are conducted, which show that our method is effective in handling nonlinear numerical cases and easy to implement. The source code of our method and data are available at https://github.com/Causality-Inference/PCD.

AI-aided drug discovery (AIDD) is gaining popularity due to its potential to make the search for new pharmaceuticals faster, less expensive, and more effective. Despite its extensive use in numerous fields (e.g., ADMET prediction, virtual screening), little research has been conducted on the out-of-distribution (OOD) learning problem with noise. We present DrugOOD, a systematic OOD dataset curator and benchmark for AIDD. Particularly, we focus on the drug-target binding affinity prediction problem, which involves both macromolecule (protein target) and small-molecule (drug compound). DrugOOD offers an automated dataset curator with user-friendly customization scripts, rich domain annotations aligned with biochemistry knowledge, realistic noise level annotations, and rigorous benchmarking of SOTA OOD algorithms, as opposed to only providing fixed datasets. Since the molecular data is often modeled as irregular graphs using graph neural network (GNN) backbones, DrugOOD also serves as a valuable testbed for graph OOD learning problems. Extensive empirical studies have revealed a significant performance gap between in-distribution and out-of-distribution experiments, emphasizing the need for the development of more effective schemes that permit OOD generalization under noise for AIDD.

We propose a new criterion for measuring dependence between two real variables, namely, Multi-level Wavelet Mapping Correlation (MWMC). MWMC can capture the nonlinear dependencies between variables by measuring their correlation under different levels of wavelet mappings. We show that the empirical estimate of MWMC converges exponentially to its population quantity. To support independence test better with MWMC, we further design a permutation test based on MWMC and prove that our test can not only control the type I error rate (the rate of false positives) well but also ensure that the type II error rate (the rate of false negatives) is upper bounded by O(1/n) (n is the sample size) with finite permutations. By extensive experiments on (conditional) independence tests and causal discovery, we show that our method outperforms existing independence test methods.

High-performance molecular property prediction is one of the essential problems in many research fields. Although Deep Learning models (DLMs) have the strong potential to predict molecular property, the search space of their neural structure and hyperparameters is too huge to enumerate all possibilities, which implies that one will be difficult to get a optimal configuration solution, or even build a DLM with poor performance. To tackle the aforementioned problem, we first abstractly map various types of supervised DLMs for chemical molecular property prediction under a unified molecular DLM conceptualization. Then, we develop a self-learning molecular DLMs construction and optimization framework, called GEP-DL4Mol, based on the unified supervised molecular DLM conceptualization and Gene Expression Programming. Experiments on eight benchmark datasets including 19 property prediction tasks were conducted to evaluate the performance of the proposed method. Experimental results show that the proposed method outperforms other methods.

Graph neural networks (GNNs) are prone to catastrophic forgetting of past experience in continuous learning scenarios. In this work, we propose a novel method for class-incremental graph learning (CGL) by class prototype construction and augmentation, which can effectively overcome catastrophic forgetting and requires no storage of exemplars (i.e., data-free). Concretely, on the one hand, we construct class prototypes in the embedding space that contain rich topological information of nodes or graphs to represent past data, which are then used for future learning. On the other hand, to boost the adaptability of the model to new classes, we employ class prototype augmentation (PA) to create virtual classes by combining current prototypes. Theoretically, we show that PA can promote the model's adaptation to new data and reduce the inconsistency of old prototypes in the embedding space, therefore further mitigate catastrophic forgetting. Extensive experiments on both node and graph classification datasets show that our method significantly outperforms the existing methods in reducing catastrophic forgetting, and beats the existing methods in most cases in terms of classification accuracy.

The ubiquitous use of face recognition has sparked increasing privacy concerns, as unauthorized access to sensitive face images could compromise the information of individuals. This paper presents an in-depth study of the privacy protection of face images’ visual information and against recovery. Drawing on the perceptual disparity between humans and models, we propose to conceal visual information by pruning human-perceivable low-frequency components. For impeding recovery, we first elucidate the seeming paradox between reducing model-exploitable information and retaining high recognition accuracy. Based on recent theoretical insights and our observation on model attention, we propose a solution to the dilemma, by advocating for the training and inference of recognition models on randomly selected frequency components. We distill our findings into a novel privacy-preserving face recognition method, PartialFace. Extensive experiments demonstrate that PartialFace effectively balances privacy protection goals and recognition accuracy. Code is available at: https://github.com/Tencent/TFace.

Zero-shot object detection aims to localize and recognize objects of unseen classes. Most of existing works face two problems: the low recall of RPN in unseen classes and the confusion of unseen classes with background. In this paper, we present the first method that combines DETR and meta-learning to perform zero-shot object detection, named Meta-ZSDETR, where model training is formalized as an individual episode based meta-learning task. Different from Faster R-CNN based methods that firstly generate class-agnostic proposals, and then classify them with visual-semantic alignment module, Meta-ZSDETR directly predict class-specific boxes with class-specific queries and further filter them with the predicted accuracy from classification head. The model is optimized with meta-contrastive learning, which contains a regression head to generate the coordinates of class-specific boxes, a classification head to predict the accuracy of generated boxes, and a contrastive head that utilizes the proposed contrastive-reconstruction loss to further separate different classes in visual space. We conduct extensive experiments on two benchmark datasets MS COCO and PASCAL VOC. Experimental results show that our method outperforms the existing ZSD methods by a large margin.

Discovering causal relationships from observational data is a challenging topic in artificial intelligence. Recent works formulate causal discovery as a continuous optimization problem with a differentiable acyclic constraint. Although these methods have achieved considerable performance improvement, they have two drawbacks: 1) they require a relatively large number of training samples; and 2) their performance will substantially deteriorate when facing heterogeneous noise. To address these problems, we first propose a low-order conditional independence (CI) constraint for the continuous optimization problem, and then design a soft version of the constraint by transforming it to a regularization term in the loss function of the continuous optimization problem. We show the convergence of continuous optimization with our constraint under some mild conditions, and the consistency of causal structure learning with the CI regularization. Extensive experiments on both synthetic and real-world datasets show that with our CI constraint or regularization, existing continuous optimization methods can achieve considerable performance improvement of causal discovery, especially when sample size is small.

With the rapid growth of virtual human techniques and the popularity of 3D face modeling, multi-view face synthesis has received considerable attention in the computer vision community. Though learning-based methods have achieved photo-realistic effect, the lack of geometry guidance remains a great hurdle to their results in high fidelity of identity. To relieve it, we propose a novel network named Dual-Representation-Net (DR-Net) driven by both learning and geometry information. In addition, we utilize face parsing to lead the learning of regional attention, in this way, the two synthesizing representations can collaborate and compete dynamically under different face angles, which improves the stability of face synthesis by assimilating the benefits of both kinds of information. What is more, we want to emphasize that DR-Net can serve as a general framework for multi-view face synthesis by jointly exploiting learning and geometry information. That is, our geometry module and learning module are actually substitutable, which can be replaced by any other SOTA methods. This makes our method both flexible and scalable. Extensive experiments verify that our approach is superior to other counterparts in both synthesis quality and identity preservation. Moreover, with the geometric information, we can decouple the synthesis of face and background to obtain more robust results on in-the-wild data.

In recent years, some advances have been achieved in classification and object detection related to animation. However, these works do not take full advantage of the tags and text description content attached to the anime data when they are created, which restricts both the related methods and data to unimodality, consequently leading to unsatisfactory performance. In this paper, we propose a novel multimodal deep learning network for Anime character identification and tag prediction by exploiting multimodal data. Considering that in many realistic scenarios, text annotations accompanying anime may be missing, we introduce the concept of curriculum learning in transformers to enable inference with only one modality. Another challenge lies in that the existing dataset does not meet our demand for large-scale multimodal deep learning. To train the proposed network, we construct a new anime dataset Dan: mul that contains over 1.6M images spread across more than 14K categories, with an average of 24 tags per image. To the best of our knowledge, this is the first dataset specifically designed for multimodal anime character identification. With the trained network, we can identify the anime characters in images and generate the related tags. Experiments show that our method achieves state-of-the-art performance on Dan: mul in animation identification.

Aspect Sentiment Quad Prediction (ASQP), which aims to predict the (aspect category, aspect term, opinion term, sentiment polarity) quadruple in a sentence, is an important subtask of Aspect-based Sentiment Analysis (ABSA) and has also gained much research attention. Recently, a number of works adopt generative models to do ASQP and achieve promising performance. Nevertheless, these approaches are limited by data scarcity, due to the challenge of labeling fine-grained quadruple annotations. Even data augmentation techniques do not help much because it is difficult to maintain the quality of augmented samples. Furthermore, the proposed templates of generative models are undesirable in extracting semantic and structural information, thus cannot fully exploit the knowledge of the language models. In this paper, to boost the performance of ASQP, we propose a novel method called DAST (the abbreviation of Data Augmentation and Self-Training). Specifically, DAST first generates large amounts of unlabeled data from the original training data. Then, an iterative self-training mechanism is proposed to fully utilize the unlabeled data to train the ASQP model. In each iteration, we employ a base ASQP model and a discriminator to obtain high-quality samples with pseudo labels, and further enhance the two models with the augmented data. In our method, both the potential of data augmentation and the ASQP model are fully explored thanks to the iterative mechanism. Finally, we advance the ASQP base model via a novel tree-like template that improves the representations of the relations between different sentiment elements, and a double-check mechanism that leverages multi-task learning to detect incorrect predictions. Extensive experiments on two benchmark datasets demonstrate the superiority of our method over the existing ones.

This paper presents the first unified distractor removal method, named IDDR-NGP, which directly operates on Instant-NPG. The method is able to remove a wide range of distractors in 3D scenes, such as snowflakes, confetti, defoliation and petals, whereas existing methods usually focus on a specific type of distractors. By incorporating implicit 3D representations with 2D detectors, we demonstrate that it is possible to efficiently restore 3D scenes from multiple corrupted images. We design the learned perceptual image patch similarity~( LPIPS) loss and the multi-view compensation loss (MVCL) to jointly optimize the rendering results of IDDR-NGP, which could aggregate information from multi-view corrupted images. All of them can be trained in an end-to-end manner to synthesize high-quality 3D scenes. To support the research on distractors removal in implicit 3D representations, we build a new benchmark dataset that consists of both synthetic and real-world distractors. To validate the effectiveness and robustness of IDDR-NGP, we provide a wide range of distractors with corresponding annotated labels added to both realistic and synthetic scenesExtensive experimental results demonstrate the effectiveness and robustness of IDDR-NGP in removing multiple types of distractors. In addition, our approach achieves results comparable with the existing SOTA desnow methods and is capable of accurately removing both realistic and synthetic distractors.

Zero-shot object detection (ZSD) aims to localize and recognize unseen objects in unconstrained images by leveraging semantic descriptions. Existing ZSD methods typically suffer from two drawbacks: 1) Due to the lack of data on unseen categories during the training phase, the model inevitably has a bias towards the seen categories, i.e., it prefers to subsume objects of unseen categories to seen categories; 2) It is usually very tricky for the feature extractor trained on data of seen categories to learn discriminative features that are good enough to help the model transfer the knowledge learned from data of seen categories to unseen categories. To tackle these problems, this paper proposes a novel zero-shot detection method based on a semantics-aware DETR and a class-wise adaptive contrastive loss. Concretely, to address the first problem, we develop a novel semantics-aware attention mechanism to mitigate the bias towards seen categories and integrate it into DETR, which results in a new end-to-end zero-shot object detection approach. Furthermore, to handle the second problem, a novel class-wise adaptive contrastive loss is proposed, which considers the relevance between each pair of categories according to their semantic description in order to learn separable features for better visual-semantic alignment. Extensive experiments and ablation studies on benchmark datasets demonstrate the effectiveness and superiority of the proposed method.

Though scene text recognition (STR) from high-resolution (HR) images has achieved significant success in the past years, text recognition from low-resolution (LR) images is still a challenging task. This inspires the study on scene text image super-resolution (STISR) to generate super-resolution (SR) images based on the LR images, then STR is performed on the generated SR images, which eventually boosts the recognition performance. However, existing methods have two major drawbacks: 1) STISR models may generate imperfect SR images, which mislead the subsequent recognition. 2) As the STISR models are optimized for high recognition accuracy, the fidelity of SR images may be degraded. Consequently, neither the recognition performance of STR nor the fidelity of STISR is desirable. In this paper, a novel model called STIRER (the abbreviation of Scene Text Image REcovery and Recognition) is proposed to effectively and simultaneously recover and recognize LR scene text images under a unified framework. Concretely, STIRER consists of a feature encoder to obtain pixel features and two dedicated decoders to generate SR images and recognize texts respectively based on the encoded features and the raw LR images. We propose a progressive scene text swin transformer architecture as the encoder to enrich the representations of the pixel features for better recovery and recognition. Extensive experiments on two LR datasets show the superiority of our model to the existing methods on recognition performance, super-resolution fidelity and computational cost. The STIRER Code is available in https://github.com/zhaominyiz/STIRER.

In addition to relevance, diversity is an important yet less studied performance metric of cross-modal image retrieval systems, which is critical to user experience. Existing solutions for diversity-aware image retrieval either explicitly post-process the raw retrieval results from standard retrieval systems or try to learn multi-vector representations of images to represent their diverse semantics. However, neither of them is good enough to balance relevance and diversity. On the one hand, standard retrieval systems are usually biased to common semantics and seldom exploit diversity-aware regularization in training, which makes it difficult to promote diversity by post-processing. On the other hand, multi-vector representation methods are not guaranteed to learn robust multiple projections. As a result, irrelevant images and images of rare or unique semantics may be projected inappropriately, which degrades the relevance and diversity of the results generated by some typical algorithms like top-k. To cope with these problems, this paper presents a new method called CoLT that tries to generate much more representative and robust representations for accurately classifying images. Specifically, CoLT first extracts semantics-aware image features by enhancing the preliminary representations of an existing one-to-one cross-modal system with semantics-aware contrastive learning. Then, a transformer-based token classifier is developed to subsume all the features into their corresponding categories. Finally, a post-processing algorithm is designed to retrieve images from each category to form the final retrieval result. Extensive experiments on two real-world datasets Div400 and Div150Cred show that CoLT can effectively boost diversity, and outperforms the existing methods as a whole (with a higher F1 score).

Abstract Anomalies (or outliers) indicate a minority of data items that are quite different from the majority (inliers) of a dataset in a certain aspect. Unsupervised anomaly detection (UAD) is an important but not yet extensively studied research topic. Recent deep learning based methods exploit the reconstruction gap between inliers and outliers to discriminate them. However, it is observed that the reconstruction gap often decreases rapidly as the training process goes. And there is no reasonable way to set the training stop point. To support effective UAD, we propose a new UAD framework by introducing a Latent Feature Reconstruction (LFR) layer that can be applied to recent UAD methods. The LFR layer acts as a regularizer to constrain the latent features in a low-rank subspace from which inliers can be reconstructed well while outliers cannot. We develop two new UAD methods by implementing the proposed framework with autoencoder architecture and geometric transformation scheme. Experiments on five benchmarks show that our proposed methods can achieve state-of-the-art performance in most cases.

Molecular property prediction (MPP) is a crucial and fundamental task for AI-aided drug discovery (AIDD). Recent studies have shown great promise of applying self-supervised learning (SSL) to producing molecular representations to cope with the widely-concerned data scarcity problem in AIDD. As some specific substructures of molecules play important roles in determining molecular properties, molecular representations learned by deep learning models are expected to attach more importance to such substructures implicitly or explicitly to achieve better predictive performance. However, few SSL pre-trained models for MPP in the literature have ever focused on such substructures. To challenge this situation, this paper presents a Chemistry-Aware Fragmentation for Effective MPP (CAFE-MPP in short) under the self-supervised contrastive learning framework. First, a novel fragment-based molecular graph (FMG) is designed to represent the topological relationship between chemistry-aware substructures that constitute a molecule. Then, with well-designed hard negative pairs, a is pre-trained on fragment-level by contrastive learning to extract representations for the nodes in FMGs. Finally, a Graphormer model is leveraged to produce molecular representations for MPP based on the embeddings of fragments. Experiments on 11 benchmark datasets show that the proposed CAFE-MPP method achieves state-of-the-art performance on 7 of the 11 datasets and the second-best performance on 3 datasets, compared with six remarkable self-supervised methods. Further investigations also demonstrate that CAFE-MPP can learn to embed molecules into representations implicitly containing the information of fragments highly correlated to molecular properties, and can alleviate the over-smoothing problem of graph neural networks.

MOTIVATION: Protein complexes are groups of polypeptide chains linked by non-covalent protein-protein interactions, which play important roles in biological systems and perform numerous functions, including DNA transcription, mRNA translation, and signal transduction. In the past decade, a number of computational methods have been developed to identify protein complexes from protein interaction networks by mining dense subnetworks or subgraphs. RESULTS: In this article, different from the existing works, we propose a novel approach for this task based on generative adversarial networks, which is called PCGAN, meaning identifying Protein Complexes by GAN. With the help of some real complexes as training samples, our method can learn a model to generate new complexes from a protein interaction network. To effectively support model training and testing, we construct two more comprehensive and reliable protein interaction networks and a larger gold standard complex set by merging existing ones of the same organism (including human and yeast). Extensive comparison studies indicate that our method is superior to existing protein complex identification methods in terms of various performance metrics. Furthermore, functional enrichment analysis shows that the identified complexes are of high biological significance, which indicates that these generated protein complexes are very possibly real complexes. AVAILABILITY AND IMPLEMENTATION: https://github.com/yul-pan/PCGAN.

MOTIVATION: Predicting molecular properties is one of the fundamental problems in drug design and discovery. In recent years, self-supervised learning (SSL) has shown its promising performance in image recognition, natural language processing, and single-cell data analysis. Contrastive learning (CL) is a typical SSL method used to learn the features of data so that the trained model can more effectively distinguish the data. One important issue of CL is how to select positive samples for each training example, which will significantly impact the performance of CL. RESULTS: In this article, we propose a new method for molecular property prediction (MPP) by Contrastive Learning with Attention-guided Positive-sample Selection (CLAPS). First, we generate positive samples for each training example based on an attention-guided selection scheme. Second, we employ a Transformer encoder to extract latent feature vectors and compute the contrastive loss aiming to distinguish positive and negative sample pairs. Finally, we use the trained encoder for predicting molecular properties. Experiments on various benchmark datasets show that our approach outperforms the state-of-the-art (SOTA) methods in most cases. AVAILABILITY AND IMPLEMENTATION: The code is publicly available at https://github.com/wangjx22/CLAPS.

MOTIVATION: Contrastive learning has been widely used as pretext tasks for self-supervised pre-trained molecular representation learning models in AI-aided drug design and discovery. However, existing methods that generate molecular views by noise-adding operations for contrastive learning may face the semantic inconsistency problem, which leads to false positive pairs and consequently poor prediction performance. RESULTS: To address this problem, in this article, we first propose a semantic-invariant view generation method by properly breaking molecular graphs into fragment pairs. Then, we develop a Fragment-based Semantic-Invariant Contrastive Learning (FraSICL) model based on this view generation method for molecular property prediction. The FraSICL model consists of two branches to generate representations of views for contrastive learning, meanwhile a multi-view fusion and an auxiliary similarity loss are introduced to make better use of the information contained in different fragment-pair views. Extensive experiments on various benchmark datasets show that with the least number of pre-training samples, FraSICL can achieve state-of-the-art performance, compared with major existing counterpart models. AVAILABILITY AND IMPLEMENTATION: The code is publicly available at https://github.com/ZiqiaoZhang/FraSICL.

With the development of biomedical techniques in the past decades, causal gene identification has become one of the most promising applications in human genome-based business, which can help doctors to evaluate the risk of certain genetic diseases and provide further treatment recommendations for potential patients. When no controlled experiments can be applied, machine learning techniques like causal inference-based methods are generally used to identify causal genes. Unfortunately, most of the existing methods detect disease-related genes by ranking-based strategies or feature selection techniques, which generally return a superset of the corresponding real causal genes. There are also some causal inference-based methods that can identify a part of real causal genes from those supersets, but they are just able to return a few causal genes. This is contrary to our knowledge, as many results from controlled experiments have demonstrated that a certain disease, especially cancer, is usually related to dozens or hundreds of genes. In this work, we present an effective approach for identifying causal genes from gene expression data by using a new search strategy based on non-linear regression-based independence tests, which is able to greatly reduce the search space, and simultaneously establish the causal relationships from the candidate genes to the disease variable. Extensive experiments on real-world cancer datasets show that our method is superior to the existing causal inference-based methods in three aspects: 1) our method can identify dozens of causal genes, and 1/3 ∼ 1/2 of the discovered causal genes can be verified by existing works that they are really directly related to the corresponding disease; 2) The discovered causal genes are able to distinguish the status or disease subtype of the target patient; 3) Most of the discovered causal genes are closely relevant to the disease variable.

The generic object detection (GOD) task has been successfully tackled by recent deep neural networks, trained by an avalanche of annotated training samples from some common classes. However, it is still non-trivial to generalize these object detectors to the novel long-tailed object classes, which have only few labeled training samples. To this end, the Few-Shot Object Detection (FSOD) has been topical recently, as it mimics the humans’ ability of learning to learn and intelligently transfers the learned generic object knowledge from the common heavy-tailed to the novel long-tailed object classes. Especially, the research in this emerging field has been flourishing in recent years with various benchmarks, backbones, and methodologies proposed. To review these FSOD works, there are several insightful FSOD survey articles [ 58 , 59 , 74 , 78 ] that systematically study and compare them as the groups of fine-tuning/transfer learning and meta-learning methods. In contrast, we review the existing FSOD algorithms from a new perspective under a new taxonomy based on their contributions, i.e., data-oriented, model-oriented, and algorithm-oriented. Thus, a comprehensive survey with performance comparison is conducted on recent achievements of FSOD. Furthermore, we also analyze the technical challenges, the merits and demerits of these methods, and envision the future directions of FSOD. Specifically, we give an overview of FSOD, including the problem definition, common datasets, and evaluation protocols. The taxonomy is then proposed that groups FSOD methods into three types. Following this taxonomy, we provide a systematic review of the advances in FSOD. Finally, further discussions on performance, challenges, and future directions are presented.

Sea surface temperature (SST) is one critical parameter of global climate change, and accurate SST prediction is important to various applications, e.g., weather forecasting, fishing directions, and disaster warnings. The global ocean system is unified and complex, and the SST patterns in different oceanic regions are highly diverse and correlated. However, existing data-driven SST prediction methods mainly consider the local patterns within a certain oceanic region, e.g., El Nino region and the Black sea. It is challenging but necessary to model the global SST correlations rather than that in a specific region to enhance the prediction accuracy of SST. In this work, we proposed a new method called Hierarchical Graph Recurrent Network (HiGRN) to address the issue. First, to learn the dynamic and diverse local SST patterns of specific locations, we design an adaptive node embedding with self-learned parameters to learn various SST patterns. Then we develop a hierarchical cluster generator to aggregate the locations with similar patterns into regional clusters and utilize a graph convolution network to learn the spatial correlations among these clusters. Finally, we introduce a multi-level attention mechanism to fuse the local patterns and regional correlations, and the output is fed into a recurrent network to achieve SST predictions. Extensive experiments on two real-world datasets show that our method largely outperforms the state-of-the-art SST prediction methods. The source code is available at https://github.com/Neoyanghc/HiGRN .

Recently, many regression-based conditional independence (CI) test methods have been proposed to solve the problem of causal discovery. These methods provide alternatives to test CI of x,y given Z by first removing the information of the controlling set Z from x and y , and then testing the independence between the two residuals R x,Z and R y,Z . When the residuals are linearly uncorrelated, the independence test between them is nontrivial. With the ability to calculate inner product in high-dimensional space, kernel-based methods are usually used to achieve this goal, but they are considerably time-consuming. In this paper, we test the independence between two linear combinations under linear structural equation model. We show that the dependence between the two residuals can be captured by the difference between the similarity of R x,Z and R y,Z and that of R x,Z and R r ( R r is an independent copy of R y,Z ) in high-dimensional space. With this result, we provide a new way to test CI based on the similarity between residuals, which is called SCIT — the abbreviation of Similarity-based CI Testing. Furthermore, we develop two versions of the proposal, called Kernel-SCIT and Neural-SCIT, respectively. Kernel-SCIT calculates the similarity by using kernel functions, while Neural-SCIT approximates the upper bound of the similarity by using deep neural networks. In both algorithms, random permutation tests are performed to control Type I error rate. The proposed tests are evaluated on (conditional) independence test and causal discovery with both synthetic and real datasets. Experimental results show that Kernel-SCIT is simpler yet more efficient and effective than the typical existing kernel-based methods HSIC and KCIT in the cases of small sample size, and Neural-SCIT can significantly boost the performance of CI testing when sufficient samples are available. The source code is available at https://github.com/xyw5vplus1/SCIT .

The misinformation detection systems are increasingly important in E-commerce management, which detect misinformation on the commodity display page. Misinformation in E-commerce is usually presented as a mismatch between multi-modal information, the detection systems need to find the misinformation across the multi-model information. Furthermore, with the development of E-commerce globalization, we hope to deploy the system in the international E-commerce platform, which may face the difficulty caused by multi-lingual data. To this end, we propose aCross-lingualMulti-modalMisinformationDetection (CMMD) framework for E-commerce management. The CMMD framework includes a word alignment network that embeds information from different languages into the same feature space and a multimodal fusion structure that fuses text representations and image representations through two self-supervised tasks. With the cooperation of these two modules, the CMMD model could extract rich cross-lingual multi-modal features to achieve accurate misinformation detection. We conduct experiments on the public multi-modal dataset and further apply the proposed CMMD to the real-world E-commerce international platform. The experimental results show that the proposed framework CMMD achieves better performance on the public dataset than some benchmarks and gets satisfactory results in real-world E-commerce management.

Recently, many regression based conditional independence (CI) test methods have been proposed to solve the problem of causal discovery. These methods provide alternatives to test CI by first removing the information of the controlling set from the two target variables, and then testing the independence between the corresponding residuals Res1 and Res2. When the residuals are linearly uncorrelated, the independence test between them is nontrivial. With the ability to calculate inner product in high-dimensional space, kernel-based methods are usually used to achieve this goal, but still consume considerable time. In this paper, we investigate the independence between two linear combinations under linear non-Gaussian structural equation model. We show that the dependence between the two residuals can be captured by the difference between the similarity of (Res1, Res2) and that of (Res1, Res3) (Res3 is generated by random permutation) in high-dimensional space. With this result, we design a new method called SCIT for CI test, where permutation test is performed to control Type I error rate. The proposed method is simpler yet more efficient and effective than the existing ones. When applied to causal discovery, the proposed method outperforms the counterparts in terms of both speed and Type II error rate, especially in the case of small sample size, which is validated by our extensive experiments on various datasets.

Cross-view geo-localization is to match scene images (e.g. ground-view images) with geo-tagged aerial images, which is crucial to a wide range of applications such as autonomous driving and street view navigation. Existing methods can neither address the perspective difference well nor effectively capture the scene information. In this work, we propose a Geometric and Scene Information Fusion (GSIF) model for more accurate cross-view geo-localization. GSIF first learns the geometric information of scene images and aerial images via log-polar transformation and spatial-attention aggregation to alleviate the perspective difference. Then, it mines the scene information of scene images via Sky View Factor (SVF) extraction. Finally, both geometric information and scene information are fused for image matching, and a balanced loss function is introduced to boost the matching accuracy. Experimental results on two real datasets show that our model can significantly outperforms the existing methods.

Nested Name Entity Recognition is to identify the entities with nested relationships from sentences, which has various applications ranging from relation extraction to semantic understanding. However, existing methods have two drawbacks, i.e., 1) error propagation when identifying entities at different nesting levels and 2) unable to uncover and utilize the complex correlations between the inner and outer entities. To address these two defects, we propose a bidirectional hierarchical(BidH) model for nested name entity recognition. BidH consists of a forward module and a backward module, where the former first extracts the inner entities and then extracts the outer ones, while the latter extracts the entities in the opposite direction. Furthermore, we design an entity masked self attention mechanism to combine the two modules by fusing their predictions and hidden states layer by layer. BidH can effectively deal with error propagation and exploit the correlations between entities at different nesting levels to improve the recognition accuracy. Experiments on the GENIA dataset show that BidH outperforms the state-of-the-art nested named entity recognition models in terms of F1 score.

Text visual question answer (TextVQA) is an important task of visual text understanding, which requires to understand the text generated by text recognition module and provide correct answers to specific questions. Recent works of TextVQA have tried to combine text recognition and multi-modal learning. However, due to the lack of effective preprocessing of text recognition output, existing approaches suffer from serious contextual information missing, which leads to unsatisfactory performance. In this work, we propose a Multi-Modal Learning framework with Text Merging (MML&TM in short) for TextVQA, where we develop a text merging (TM) algorithm, which can effectively merge the word-level text obtained from the text recognition module to construct line-level and paragraph-level texts for enhancing semantic context, which is crucial to visual text understanding. The TM module can be easily incorporated into the multi-modal learning framework to generate more comprehensive answers for TextVQA. We evaluate our method on a public dataset ST-VQA. Experimental results show that our TM algorithm can obtain complete semantic information, which subsequently helps MML&TM generate better answers for TextVQA.

Outlier detection is an important data mining task, and developing effective methods to detect outliers is challenging in cases where there is insufficient labeled data. Manually labeling the data is labor-intensive and time-consuming. Because of a limited number of labeled samples, the classes are unbalanced, resulting in a class-imbalance problem. Existing methods fail to address these aforementioned issues holistically and fall short in generating quality outlier samples for effective outlier detection accuracy. In this paper, we propose a new solution that tackles these problems. We propose a. Generative Adversarial Active Learning method (DIR-GAAL), which generates Diverse, Informative, and Representative outlier samples through active learning, and employs the mini-max game between the generator and discriminator in a generative adversarial network. We conducted extensive experiments on several benchmark datasets to evaluate the performance of our method. When compared to other benchmark methods, our method consistently demon-strates better outlier detection accuracy without being negatively affected by the class-imbalance problem.

Scene text image super-resolution (STISR) has been regarded as an important pre-processing task for text recognition from low-resolution scene text images. Most recent approaches use the recognizer's feedback as clues to guide super-resolution. However, directly using recognition clue has two problems: 1) Compatibility. It is in the form of probability distribution, has an obvious modal gap with STISR - a pixel-level task; 2) Inaccuracy. it usually contains wrong information, thus will mislead the main task and degrade super-resolution performance. In this paper, we present a novel method C3-STISR that jointly exploits the recognizer's feedback, visual and linguistical information as clues to guide super-resolution. Here, visual clue is from the images of texts predicted by the recognizer, which is informative and more compatible with the STISR task; while linguistical clue is generated by a pre-trained character-level language model, which is able to correct the predicted texts. We design effective extraction and fusion mechanisms for the triple cross-modal clues to generate a comprehensive and unified guidance for super-resolution. Extensive experiments on TextZoom show that C3-STISR outperforms the SOTA methods in fidelity and recognition performance. Code is available in https://github.com/zhaominyiz/C3-STISR.

With the wide application of face recognition systems, there is rising concern that original face images could be exposed to malicious intents and consequently cause personal privacy breaches. This paper presents DuetFace, a novel privacy-preserving face recognition method that employs collaborative inference in the frequency domain. Starting from a counterintuitive discovery that face recognition can achieve surprisingly good performance with only visually indistinguishable high-frequency channels, this method designs a credible split of frequency channels by their cruciality for visualization and operates the server-side model on non-crucial channels. However, the model degrades in its attention to facial features due to the missing visual information. To compensate, the method introduces a plug-in interactive block to allow attention transfer from the client-side by producing a feature mask. The mask is further refined by deriving and overlaying a facial region of interest (ROI). Extensive experiments on multiple datasets validate the effectiveness of the proposed method in protecting face images from undesired visual inspection, reconstruction, and identification while maintaining high task availability and performance. Results show that the proposed method achieves a comparable recognition accuracy and computation cost to the unprotected ArcFace and outperforms the state-of-the-art privacy-preserving methods. The source code is available at https://github.com/Tencent/TFace/tree/master/recognition/tasks/duetface.

Few-shot object detection (FSOD) is to detect objects with a few examples. However, existing FSOD methods do not consider hierarchical fine-grained category structures of objects that exist widely in real life. For example, animals are taxonomically classified into orders, families, genera and species etc. In this paper, we propose and solve a new problem called hierarchical few-shot object detection (Hi-FSOD), which aims to detect objects with hierarchical categories in the FSOD paradigm. To this end, on the one hand, we build the first large-scale and high-quality Hi-FSOD benchmark dataset HiFSOD-Bird, which contains 176,350 wild-bird images falling to 1,432 categories. All the categories are organized into a 4-level taxonomy, consisting of 32 orders, 132 families, 572 genera and 1,432 species. On the other hand, we propose the first Hi-FSOD method HiCLPL, where a hierarchical contrastive learning approach is developed to constrain the feature space so that the feature distribution of objects is consistent with the hierarchical taxonomy and the model's generalization power is strengthened. Meanwhile, a probabilistic loss is designed to enable the child nodes to correct the classification errors of their parent nodes in the taxonomy. Extensive experiments on the benchmark dataset HiFSOD-Bird show that our method HiCLPL outperforms the existing FSOD methods.

Minyi Zhao, Lu Zhang, Yi Xu, Jiandong Ding, Jihong Guan, Shuigeng Zhou. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

There are already some text-based visual question answering (TextVQA) benchmarks for developing machine's ability to answer questions based on texts in images in recent years. However, models developed on these benchmarks cannot work effectively in many real-life scenarios (e.g. traffic monitoring, shopping ads and e-learning videos) where temporal reasoning ability is required. To this end, we propose a new task named Video Text Visual Question Answering (ViteVQA in short) that aims at answering questions by reasoning texts and visual information spatiotemporally in a given video. In particular, on the one hand, we build the first ViteVQA benchmark dataset named M4-ViteVQA --- the abbreviation of Multi-category Multi-frame Multi-resolution Multi-modal benchmark for ViteVQA, which contains 7,620 video clips of 9 categories (i.e., shopping, traveling, driving, vlog, sport, advertisement, movie, game and talking) and 3 kinds of resolutions (i.e., 720p, 1080p and 1176x664), and 25,123 question-answer pairs. On the other hand, we develop a baseline method named T5-ViteVQA for the ViteVQA task. T5-ViteVQA consists of five transformers. It first extracts optical character recognition (OCR) tokens, question features, and video representations via two OCR transformers, one language transformer and one video-language transformer, respectively. Then, a multimodal fusion transformer and an answer generation module are applied to fuse multimodal information and generate the final prediction. Extensive experiments on M4-ViteVQA demonstrate the superiority of T5-ViteVQA to the existing approaches of TextVQA and VQA tasks. The ViteVQA benchmark is available in https://github.com/bytedance/VTVQA.

Reading irregular scene text is a challenging problem in scene text recognition. Rectification is a popular measure to reduce irregularities of text in images. Existing rectification methods seek to rectify text images into a strictly regular form via free parametric transformation functions. However, they always suffer from information loss or severe deformation due to their poor constraints to the transformation functions. In our investigation, we found that CNN and attention are robust to many slight irregularities. What inspires us to propose a novel and effective rectification method that mainly rectifies the principle regularities, and leaves the slight irregularities to the CNN-LSTM-attention recognizer. Our rectification method first estimates the character densities and directions of the input image in a down-sampled map then finds a best fitting curve from a small predefined Bézier curve set, and finally rectifies the input image with a transformation function corresponding to the selected curve. Transformation functions are carefully designed so that they neither lose important visual information nor cause severe deformation. Extensive experiments on seven benchmark datasets show that our method achieves the state of the art performance in most cases, especially in curved text recognition.

Single-cell RNA sequencing (scRNA-seq) permits researchers to study the complex mechanisms of cell heterogeneity and diversity. Unsupervised clustering is of central importance for the analysis of the scRNA-seq data, as it can be used to identify putative cell types. However, due to noise impacts, high dimensionality and pervasive dropout events, clustering analysis of scRNA-seq data remains a computational challenge. Here, we propose a new deep structural clustering method for scRNA-seq data, named scDSC, which integrate the structural information into deep clustering of single cells. The proposed scDSC consists of a Zero-Inflated Negative Binomial (ZINB) model-based autoencoder, a graph neural network (GNN) module and a mutual-supervised module. To learn the data representation from the sparse and zero-inflated scRNA-seq data, we add a ZINB model to the basic autoencoder. The GNN module is introduced to capture the structural information among cells. By joining the ZINB-based autoencoder with the GNN module, the model transfers the data representation learned by autoencoder to the corresponding GNN layer. Furthermore, we adopt a mutual supervised strategy to unify these two different deep neural architectures and to guide the clustering task. Extensive experimental results on six real scRNA-seq datasets demonstrate that scDSC outperforms state-of-the-art methods in terms of clustering accuracy and scalability. Our method scDSC is implemented in Python using the Pytorch machine-learning library, and it is freely available at https://github.com/DHUDBlab/scDSC.

MOTIVATION: Accurately predicting drug-target interaction (DTI) is a crucial step to drug discovery. Recently, deep learning techniques have been widely used for DTI prediction and achieved significant performance improvement. One challenge in building deep learning models for DTI prediction is how to appropriately represent drugs and targets. Target distance map and molecular graph are low dimensional and informative representations, which however have not been jointly used in DTI prediction. Another challenge is how to effectively model the mutual impact between drugs and targets. Though attention mechanism has been used to capture the one-way impact of targets on drugs or vice versa, the mutual impact between drugs and targets has not yet been explored, which is very important in predicting their interactions. RESULTS: Therefore, in this article we propose MINN-DTI, a new model for DTI prediction. MINN-DTI combines an interacting-transformer module (called Interformer) with an improved Communicative Message Passing Neural Network (CMPNN) (called Inter-CMPNN) to better capture the two-way impact between drugs and targets, which are represented by molecular graph and distance map, respectively. The proposed method obtains better performance than the state-of-the-art methods on three benchmark datasets: DUD-E, human and BindingDB. MINN-DTI also provides good interpretability by assigning larger weights to the amino acids and atoms that contribute more to the interactions between drugs and targets. AVAILABILITY AND IMPLEMENTATION: The data and code of this study are available at https://github.com/admislf/MINN-DTI.

BACKGROUND: Essential proteins are indispensable to the development and survival of cells. The identification of essential proteins not only is helpful for the understanding of the minimal requirements for cell survival, but also has practical significance in disease diagnosis, drug design and medical treatment. With the rapidly amassing of protein-protein interaction (PPI) data, computationally identifying essential proteins from protein-protein interaction networks (PINs) becomes more and more popular. Up to now, a number of various approaches for essential protein identification based on PINs have been developed. RESULTS: In this paper, we propose a new and effective approach called iMEPP to identify essential proteins from PINs by fusing multiple types of biological data and applying the influence maximization mechanism to the PINs. Concretely, we first integrate PPI data, gene expression data and Gene Ontology to construct weighted PINs, to alleviate the impact of high false-positives in the raw PPI data. Then, we define the influence scores of nodes in PINs with both orthological data and PIN topological information. Finally, we develop an influence discount algorithm to identify essential proteins based on the influence maximization mechanism. CONCLUSIONS: We applied our method to identifying essential proteins from saccharomyces cerevisiae PIN. Experiments show that our iMEPP method outperforms the existing methods, which validates its effectiveness and advantage.

Cellular programs often exhibit strong heterogeneity and asynchrony in the timing of program execution. Single-cell RNA-seq technology has provided an unprecedented opportunity for characterizing these cellular processes by simultaneously quantifying many parameters at single-cell resolution. Robust trajectory inference is a critical step in the analysis of dynamic temporal gene expression, which can shed light on the mechanisms of normal development and diseases. Here, we present TiC2D, a novel algorithm for cell trajectory inference from single-cell RNA-seq data, which adopts a consensus clustering strategy to precisely cluster cells. To evaluate the power of TiC2D, we compare it with three state-of-the-art methods on four independent single-cell RNA-seq datasets. The results show that TiC2D can accurately infer developmental trajectories from single-cell transcriptome. Furthermore, the reconstructed trajectories enable us to identify key genes involved in cell fate determination and to obtain new insights about their roles at different developmental stages.

Clustering analysis has been widely used in analyzing single-cell RNA-sequencing (scRNA-seq) data to study various biological problems at cellular level. Although a number of scRNA-seq data clustering methods have been developed, most of them evaluate the similarity of pairwise cells while ignoring the global relationships among cells, which sometimes cannot effectively capture the latent structure of cells. In this paper, we propose a new clustering method SPARC for scRNA-seq data. The most important feature of SPARC is a novel similarity metric that uses the sparse representation coefficients of each cell in terms of the other cells to measure the relationships among cells. In addition, we develop an outlier detection method to help parameter selection in SPARC. We compare SPARC with nine existing scRNA-seq data clustering methods on twelve real datasets. Experimental results show that SPARC achieves the state of the art performance. By further analyzing the cell similarity data derived from sparse representations, we find that SPARC is much more effective in mining high quality clusters of scRNA-seq data than two traditional similarity metrics. In conclusion, this study provides a new way to effectively cluster scRNA-seq data and achieves more accurate clustering results than the state of art methods.

In random-turn games, players toss a coin to decide who moves. This paper studies the complexities of the algorithms for playing random-turn connection games perfectly on regular tessellations. Our study theoretically shows that there are algorithms playing random-turn Hex, Square and Triangle perfectly in${O(n^{9}\cdot 2.618^{n}),\ O(n^{9}\cdot 2.746^{n})}$and${O(n^{9}\cdot 3.645^{n})}$time for each move respectively, where n is the board size. We then implement the perfect-playing algorithm for random-turn Square and measure the actual running time it costs for each move. We then compute and analyze the game lengths on random-turn Square, Hex and Triangle and conjecture that the asymptotic complexity of their game lengths are the same. We finally compare the perfect-playing algorithm with the sampling algorithm by competing against each other, and the numbers of their wins and loses are reported.

Link weight prediction is an important subject in network science and machine learning. Its applications to social network analysis, network modeling, and bioinformatics are ubiquitous. Although this subject has attracted considerable attention recently, the performance and interpretability of existing prediction models have not been well balanced. This article focuses on an unsupervised mixed strategy for link weight prediction. Here, the target attribute is the link weight, which represents the correlation or strength of the interaction between a pair of nodes. The input of the model is the weighted adjacency matrix without any preprocessing, as widely adopted in the existing models. Extensive observations on a large number of networks show that the new scheme is competitive to the state-of-the-art algorithms concerning both root-mean-square error and Pearson correlation coefficient metrics. Analytic and simulation results suggest that combining the weight consistency of the network and the link weight-associated latent factors of the nodes is a very effective way to solve the link weight prediction problem.

This article addresses two important issues of causal inference in the high-dimensional situation. One is how to reduce redundant conditional independence (CI) tests, which heavily impact the efficiency and accuracy of existing constraint-based methods. Another is how to construct the true causal graph from a set of Markov equivalence classes returned by these methods. For the first issue, we design a recursive decomposition approach where the original data (a set of variables) are first decomposed into two small subsets, each of which is then recursively decomposed into two smaller subsets until none of these subsets can be decomposed further. Redundant CI tests can be reduced by inferring causalities from these subsets. The advantage of this decomposition scheme lies in two aspects: 1) it requires only low-order CI tests and 2) it does not violate d -separation. The complete causality can be reconstructed by merging all the partial results of the subsets. For the second issue, we employ regression-based CI tests to check CIs in linear non-Gaussian additive noise cases, which can identify more causal directions by [Formula: see text] (or [Formula: see text]). Consequently, causal direction learning is no longer limited by the number of returned V -structures and consistent propagation. Extensive experiments show that the proposed method can not only substantially reduce redundant CI tests but also effectively distinguish the equivalence classes.

With the rapid increase of mobile devices and online media, more and more people prefer posting/viewing videos online. Generally, these videos are presented on video streaming sites with image thumbnails and text titles. While facing huge amounts of videos, a viewer clicks through a certain video with high probability because of its eye-catching thumbnail. However, current video thumbnails are created manually, which is time-consuming and quality-unguaranteed. And static image thumbnails contain very limited information of the corresponding videos, which prevents users from successfully clicking what they really want to view. In this paper, we address a novel problem, namely GIF thumbnail generation, which aims to automatically generate GIF thumbnails for videos and consequently boost their Click-Through-Rate (CTR). Here, a GIF thumbnail is an animated GIF file consisting of multiple segments from the video, containing more information of the target video than a static image thumbnail. To support this study, we build the first GIF thumbnails benchmark dataset that consists of 1070 videos covering a total duration of 69.1 hours, and 5394 corresponding manually-annotated GIFs. To solve this problem, we propose a learning-based automatic GIF thumbnail generation model, which is called Generative Variational Dual-Encoder (GEVADEN). As not relying on any user interaction information (e.g. time-sync comments and real-time view counts), this model is applicable to newly-uploaded/rarely-viewed videos. Experiments on our built dataset show that GEVADEN significantly outperforms several baselines, including video-summarization and highlight-detection based ones. Furthermore, we develop a pilot application of the proposed model on an online video platform with 9814 videos covering 1231 hours, which shows that our model achieves a 37.5% CTR improvement over traditional image thumbnails. This further validates the effectiveness of the proposed model and the promising application prospect of GIF thumbnails.

Recently, regression based conditional independence (CI) tests have been employed to solve the problem of causal discovery. These methods provide an alternative way to test for CI by transforming CI to independence between residuals. Generally, it is nontrivial to check for independence when these residuals are linearly uncorrelated. With the ability to represent high-order moments, kernel-based methods are usually used to achieve this goal, but at a cost of considerable time. In this paper, we investigate the independence between two linear combinations under linear non-Gaussian structural equation model (SEM). We show that generally the 1-st to 4-th moments of the two linear combinations contain enough information to infer whether or not they are independent. The proposed method provides a simpler but more effective way to measure CIs, with only calculating the 1-st to 4-th moments of the input variables. When applied to causal discovery, the proposed method outperforms kernel-based methods in terms of both speed and accuracy. which is validated by extensive experiments.

Most object detection methods require huge amounts of annotated data and can detect only the categories that appear in the training set. However, in reality acquiring massive annotated training data is both expensive and time-consuming. In this paper, we propose a novel two-stage detector for accurate few-shot object detection. In the first stage, we employ a support-query mutual guidance mechanism to generate more support-relevant proposals. Concretely, on the one hand, a query-guided support weighting module is developed for aggregating different supports to generate the support feature. On the other hand, a supportguided query enhancement module is designed by dynamic kernels. In the second stage, we score and filter proposals via multi-level feature comparison between each proposal and the aggregated support feature based on a distance metric learnt by an effective hybrid loss, which makes the embedding space of distance metric more discriminative. Extensive experiments on benchmark datasets show that our method substantially outperforms the existing methods and lifts the SOTA of FSOD task to a higher level.

Weakly-supervised text classification has received much attention in recent years for it can alleviate the heavy burden of annotating massive data.Among them, keyword-driven methods are the mainstream where user-provided keywords are exploited to generate pseudolabels for unlabeled texts.However, existing methods treat keywords independently, thus ignore the correlation among them, which should be useful if properly exploited.In this paper, we propose a novel framework called ClassKG to explore keyword-keyword correlation on keyword graph by GNN.Our framework is an iterative process.In each iteration, we first construct a keyword graph, so the task of assigning pseudo labels is transformed to annotating keyword subgraphs.To improve the annotation quality, we introduce a self-supervised task to pretrain a subgraph annotator, and then finetune it.With the pseudo labels generated by the subgraph annotator, we then train a text classifier to classify the unlabeled texts.Finally, we re-extract keywords from the classified texts.Extensive experiments on both long-text and short-text datasets show that our method substantially outperforms the existing ones.

Generic object detection has achieved significant progress in recent years. However, oriented object detection in aerial images is still a challenging task due to arbitrary orientation, complex backgrounds and large scale variation. Currently, the majority of oriented object detectors are anchor-based, achieving promising performance yet suffering from complicated anchor designs and imbalance between the positive and negative anchor boxes. In this work, we propose a new anchor-free model called RBA-CenterNet for oriented object detection. Specifically, we first detect the center point of each object after extracting feature of the input image. Then, we regress the rotated box parameters in other prediction branches. Considering that using only the center point of the object may hurt the detection performance, we introduce a refinement module called rotated border alignment (RBA) to integrate the border feature into the center point feature. Our experiments show that the proposed model RBA-CenterNet can achieve comparable detection performance to state-of-the-art methods.

A number of deep learning based algorithms have been proposed to recover high-quality videos from low-quality compressed ones. Among them, some restore the missing details of each frame via exploring the spatiotemporal information of neighboring frames. However, these methods usually suffer from a narrow temporal scope, thus may miss some useful details from some frames outside the neighboring ones. In this paper, to boost artifact removal, on the one hand, we propose a Recursive Fusion (RF) module to model the temporal dependency within a long temporal range. Specifically, RF utilizes both the current reference frames and the preceding hidden state to conduct better spatiotemporal compensation. On the other hand, we design an efficient and effective Deformable Spatiotemporal Attention (DSTA) module such that the model can pay more effort on restoring the artifact-rich areas like the boundary area of a moving object. Extensive experiments show that our method outperforms the existing ones on the MFQE 2.0 dataset in terms of both fidelity and perceptual effect. Code is available at https://github.com/zhaominyiz/RFDA-PyTorch.

The scarcity of labeled data is a critical obstacle to deep learning. Semi-supervised learning (SSL) provides a promising way to leverage unlabeled data by pseudo labels. However, when the size of labeled data is very small (say a few labeled samples per class), SSL performs poorly and unstably, possibly due to the low quality of learned pseudo labels. In this paper, we propose a new SSL method called DP-SSL that adopts an innovative data programming (DP) scheme to generate probabilistic labels for unlabeled data. Different from existing DP methods that rely on human experts to provide initial labeling functions (LFs), we develop a multiple-choice learning~(MCL) based approach to automatically generate LFs from scratch in SSL style. With the noisy labels produced by the LFs, we design a label model to resolve the conflict and overlap among the noisy labels, and finally infer probabilistic labels for unlabeled samples. Extensive experiments on four standard SSL benchmarks show that DP-SSL can provide reliable labels for unlabeled data and achieve better classification performance on test sets than existing SSL methods, especially when only a small number of labeled samples are available. Concretely, for CIFAR-10 with only 40 labeled samples, DP-SSL achieves 93.82% annotation accuracy on unlabeled data and 93.46% classification accuracy on test data, which are higher than the SOTA results.

Several visual graph query interfaces (a.k.a gui) expose a set of canned patterns (i.e., small subgraph patterns) to expedite subgraph query formulation by enabling pattern-at-a-time construction. Unfortunately, manual generation of canned patterns is not only labour intensive but also may lack diversity to support efficient visual formulation of a wide range of subgraph queries. Recent efforts have taken a data-driven approach to select high-quality canned patterns for a gui automatically from the underlying graph database. However, as the underlying database evolves, these selected patterns may become stale and adversely impact efficient query formulation. In this paper, we present a novel framework called Midas for efficient and effective maintenance of the canned patterns as the database evolves. Specifically, it adopts a selective maintenance strategy that guarantees progressive gain of coverage of the patterns without sacrificing their diversity and cognitive load. Experimental study with real-world datasets and visual graph interfaces demonstrates the effectiveness of Midas compared to static guis.

MOTIVATION: Molecular property prediction is a hot topic in recent years. Existing graph-based models ignore the hierarchical structures of molecules. According to the knowledge of chemistry and pharmacy, the functional groups of molecules are closely related to its physio-chemical properties and binding affinities. So, it should be helpful to represent molecular graphs by fragments that contain functional groups for molecular property prediction. RESULTS: In this article, to boost the performance of molecule property prediction, we first propose a definition of molecule graph fragments that may be or contain functional groups, which are relevant to molecular properties, then develop a fragment-oriented multi-scale graph attention network for molecular property prediction, which is called FraGAT. Experiments on several widely used benchmarks are conducted to evaluate FraGAT. Experimental results show that FraGAT achieves state-of-the-art predictive performance in most cases. Furthermore, our case studies show that when the fragments used to represent the molecule graphs contain functional groups, the model can make better predictions. This conforms to our expectation and demonstrates the interpretability of the proposed model. AVAILABILITY AND IMPLEMENTATION: The code and data underlying this work are available in GitHub, at https://github.com/ZiqiaoZhang/FraGAT. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: The rapid development of single-cell RNA sequencing (scRNA-seq) enables the exploration of cell heterogeneity, which is usually done by scRNA-seq data clustering. The essence of scRNA-seq data clustering is to group cells by measuring the similarities among genes/transcripts of cells. And the selection of features for cell similarity evaluation is of great importance, which will significantly impact clustering effectiveness and efficiency. RESULTS: In this paper, we propose a novel method called CaFew to select genes based on cluster-aware feature weighting. By optimizing the clustering objective function, CaFew obtains a feature weight matrix, which is further used for feature selection. The genes have large weights in at least one cluster or the genes whose weights vary greatly in different clusters are selected. Experiments on 8 real scRNA-seq datasets show that CaFew can obviously improve the clustering performance of existing scRNA-seq data clustering methods. Particularly, the combination of CaFew with SC3 achieves the state-of-art performance. Furthermore, CaFew also benefits the visualization of scRNA-seq data. CONCLUSION: CaFew is an effective scRNA-seq data clustering method due to its gene selection mechanism based on cluster-aware feature weighting, and it is a useful tool for scRNA-seq data analysis.

Privacy preserving is a paramount concern in publishing datasets that contain sensitive information. Preventing privacy disclosure and providing useful information to legitimate users for data analyzing/mining are conflicting goals. Randomized response is a class of techniques that perturbs each sensitive value in a certain way, so that personal privacy is protected while the large-trend of the entire dataset is still recoverable. However, existing randomized response techniques do not allow to flexibly configure the level of privacy protection, support only a few types of aggregate queries, and cannot achieve the best answer accuracy from perturbed data. These drawbacks impair the effectiveness of those techniques. This paper proposes a general framework based on randomized response techniques, which has good flexibility and extensibility, and can improve the effectiveness of randomized response methods. Our approach is validated by extensive experiments and comparison with existing randomized response and generalization methods.

In recent years, many methods have been developed for discovering causal relationships from observed data. However, as an important kind of causes existing in many causal systems, combined causes (e.g. multi-factor causes consisting of two or more component variables that individually might not be a cause) have not received enough attention. The existing approach includes both individual and combined variables in the causal discovery process using constraint-based methods, can neither distinguish a set of Markov equivalence classes nor identify a combined cause containing one (or more) individual cause(s), therefore can output only some combined causes, instead of all combined causes. In this paper, we first subsume all possible combined causes into three types and give them formal definitions, then extend the additive noise model (ANM) to infer combined causes. We show that if a candidate variable set X w.r.t. a target Y satisfies: (1) allowing ANM for only the forward direction X→Y, and (2) no disturbance variable is contained in X, i.e., removing any component of X will weaken the causal relationship between X and Y, then X forms a combined cause. Based on this finding, we develop an efficient method to discover combined causes. Furthermore, we also conduct extensive experiments to validate the proposed method on both synthetic and real-world data sets.

Currently, video text spotting tasks usually fall into the four-staged pipeline: detecting text regions in individual images, recognizing localized text regions frame-wisely, tracking text streams and post-processing to generate final results. However, they may suffer from the huge computational cost as well as sub-optimal results due to the interferences of low-quality text and the none-trainable pipeline strategy. In this article, we propose a fast and robust end-to-end video text spotting framework named FREE by only recognizing the localized text stream one-time instead of frame-wise recognition. Specifically, FREE first employs a well-designed spatial-temporal detector that learns text locations among video frames. Then a novel text recommender is developed to select the highest-quality text from text streams for recognizing. Here, the recommender is implemented by assembling text tracking, quality scoring and recognition into a trainable module. It not only avoids the interferences from the low-quality text but also dramatically speeds up the video text spotting. FREE unites the detector and recommender into a whole framework, and helps achieve global optimization. Besides, we collect a large scale video text dataset for promoting the video text spotting community, containing 100 videos from 21 real-life scenarios. Extensive experiments on public benchmarks show our method greatly speeds up the text spotting process, and also achieves the remarkable state-of-the-art.

In the emerging business of food delivery, rider traffic accidents raise financial cost and social traffic burden. Although there has been much effort on traffic accident forecasting using temporal-spatial prediction models, none of the existing work studies the problem of detecting the takeaway rider accidents based on food delivery trajectory data. In this article, we aim to detect whether a takeaway rider meets an accident on a certain time period based on trajectories of food delivery and riders’ contextual information. The food delivery data has a heterogeneous information structure and carries contextual information such as weather and delivery history, and trajectory data are collected as a spatial-temporal sequence. In this article, we propose a TakeAway Rider Accident detection fusion network TARA-Net to jointly model these heterogeneous and spatial-temporal sequence data. We utilize the residual network to extract basic contextual information features and take advantage of a transformer encoder to capture trajectory features. These embedding features are concatenated into a pyramidal feed-forward neural network. We jointly train the above three components to combine the benefits of spatial-temporal trajectory data and sparse basic contextual data for early detecting traffic accidents. Furthermore, although traffic accidents rarely happen in food delivery, we propose a sampling mechanism to alleviate the imbalance of samples when training the model. We evaluate the model on a transportation mode classification dataset Geolife and a real-world Ele.me dataset with over 3 million riders. The experimental results show that the proposed model is superior to the state-of-the-art.

In this paper, for the first time, we study label propagation in heterogeneous graphs under heterophily assumption. Homophily label propagation (i.e., two connected nodes share similar labels) in homogeneous graph (with same types of vertices and relations) has been extensively studied before. Unfortunately, real-life networks (e.g., social networks) are heterogeneous, they contain different types of vertices (e.g., users, images, and texts) and relations (e.g., friendships and co-tagging) and allow for each node to propagate both the same and opposite copy of labels to its neighbors. We propose a IC-partite label propagation model to handle the mystifying combination of heterogeneous nodes/relations and heterophily propagation. With this model, we develop a novel label inference algorithm framework with update rules in near-linear time complexity. Since real networks change overtime, we devise an incremental approach, which supports fast updates for both new data and evidence (e.g., ground truth labels) with guaranteed efficiency. We further provide a utility function to automatically determine whether an incremental or a re-modeling approach is favored. Extensive experiments on real datasets have verified the effectiveness and efficiency of our approach, and its superiority over the state-of-the-art label propagation methods.

The mining missing links and predicting upcoming links are two important topics in the link prediction. In the past decades, a variety of algorithms have been developed, the majority of which apply similarity measures to estimate the bonding probability between nodes. And for these algorithms, it is still difficult to achieve a satisfactory tradeoff among precision, computational complexity, robustness to network types, and scalability to network size. In this article, we propose a chaotic ant colony optimized (CACO) link prediction algorithm, which integrates the chaotic perturbation model and ant colony optimization. The extensive experiments on a wide variety of unweighted and weighted networks show that the proposed algorithm CACO achieves significantly higher prediction accuracy and robustness than most of the state-of-the-art algorithms. The results demonstrate that the chaotic ant colony effectively takes advantage of the fact that most real networks possess the transmission capacity and provides a new perspective for future link prediction research.

Despite powerful representation ability, deep neural networks (DNNs) are prone to over-fitting, because of over-parametrization. Existing works have explored various regularization techniques to tackle the over-fitting problem. Some of them employed soft targets rather than one-hot labels to guide network training (e.g. label smoothing in classification tasks), which are called target-based regularization approaches in this paper. To alleviate the over-fitting problem, here we propose a new and general regularization framework that introduces an auxiliary network to dynamically incorporate guided semantic disturbance to the labels. We call it Network as Regularization (NaR in short). During training, the disturbance is constructed by a convex combination of the predictions of the target network and the auxiliary network. These two networks are initialized separately. And the auxiliary network is trained independently from the target network, while providing instance-level and class-level semantic information to the latter progressively. We conduct extensive experiments to validate the effectiveness of the proposed method. Experimental results show that NaR outperforms many state-of-the-art target-based regularization methods, and other regularization approaches (e.g. mixup) can also benefit from combining with NaR.

Scene text recognition (STR) is still a hot research topic in computer vision field due to its various applications. Existing works mainly focus on learning a general model with a huge number of synthetic text images to recognize unconstrained scene texts, and have achieved substantial progress. However, these methods are not quite applicable in many real-world scenarios where 1) high recognition accuracy is required, while 2) labeled samples are lacked. To tackle this challenging problem, this paper proposes a few-shot adversarial sequence domain adaptation (FASDA) approach to build sequence adaptation between the synthetic source domain (with many synthetic labeled samples) and a specific target domain (with only some or a few real labeled samples). This is done by simultaneously learning each character's feature representation with an attention mechanism and establishing the corresponding character-level latent subspace with adversarial learning. Our approach can maximize the character-level confusion between the source domain and the target domain, thus achieves the sequence-level adaptation with even a small number of labeled samples in the target domain. Extensive experiments on various datasets show that our method significantly outperforms the finetuning scheme, and obtains comparable performance to the state-of-the-art STR methods.

Zero-shot Object Detection (ZSD) aims to locate and classify instances of unseen categories. Existing methods focus on learning the mapping from visual space to semantic space, while the learning of discriminative representations for ZSD has not gained enough attention. In this paper, we demonstrate the necessity to learn discriminative semantic representations for ZSD, and propose a new end-to-end framework for this task. Our framework is able to learn discriminative semantic representations in an augmented space introduced for both user-defined and latent attributes, and refine the user-defined attributes with the help of unseen and external classes. The proposed method is extensively evaluated on two challenging ZSD datasets, and the experimental results show that our method significantly outperforms several existing methods.

Several commercial and academic frameworks for querying a large collection of small- or medium-sized data graphs (eg. chemical compounds) provide visual graph query interfaces (a.k.a GUI) to facilitate non-programmers to query these sources. However, construction of these visual interfaces is not data-driven. That is, it does not exploit the underlying data graphs to automatically generate the contents of various panels in a GUI. Such data-driven construction has several benefits such as facilitating efficient subgraph query formulation and portability of the interface across different application domains and sources. In this demonstration, we present a novel data-driven visual subgraph query interface construction engine called AURORA. Specifically, given a graph repository D containing a collection of small- or medium-sized data graphs, it automatically generates the GUI for D by populating various components of the interface. We demonstrate various innovative features of AURORA.

The paradigm of interleaving (i.e. blending) visual subgraph query formulation and processing by exploiting the latency offered by the GUI brings in several potential benefits such as superior system response time (SRT) and opportunities to enhance usability of graph databases. Recent efforts at implementing this paradigm are focused on subgraph isomorphism-based queries, which are often restrictive in many real-world graph applications. In this demonstration, we present a novel system called BOOMER to realize this paradigm on more generic but complex bounded 1-1 p-homomorphic(BPH) queries on large networks. Intuitively, a BPH query maps an edge of the query to bounded paths in the data graph. We demonstrate various innovative features of BOOMER, its flexibility, and its promising performance.

BACKGROUND: Protein-DNA interaction governs a large number of cellular processes, and it can be altered by a small fraction of interface residues, i.e., the so-called hot spots, which account for most of the interface binding free energy. Accurate prediction of hot spots is critical to understand the principle of protein-DNA interactions. There are already some computational methods that can accurately and efficiently predict a large number of hot residues. However, the insufficiency of experimentally validated hot-spot residues in protein-DNA complexes and the low diversity of the employed features limit the performance of existing methods. RESULTS: Here, we report a new computational method for effectively predicting hot spots in protein-DNA binding interfaces. This method, called PreHots (the abbreviation of Predicting Hotspots), adopts an ensemble stacking classifier that integrates different machine learning classifiers to generate a robust model with 19 features selected by a sequential backward feature selection algorithm. To this end, we constructed two new and reliable datasets (one benchmark for model training and one independent dataset for validation), which totally consist of 123 hot spots and 137 non-hot spots from 89 protein-DNA complexes. The data were manually collected from the literature and existing databases with a strict process of redundancy removal. Our method achieves a sensitivity of 0.813 and an AUC score of 0.868 in 10-fold cross-validation on the benchmark dataset, and a sensitivity of 0.818 and an AUC score of 0.820 on the independent test dataset. The results show that our approach outperforms the existing ones. CONCLUSIONS: PreHots, which is based on stack ensemble of boosting algorithms, can reliably predict hot spots at the protein-DNA binding interface on a large scale. Compared with the existing methods, PreHots can achieve better prediction performance. Both the webserver of PreHots and the datasets are freely available at: http://dmb.tongji.edu.cn/tools/PreHots/ .

Recovering causal relationships from observed data is crucial to a variety of applications. Due to the curse of dimensionality, general causal discovery methods such as constraint-based methods and functional model based methods are not quite effective and efficient for large and high-dimensional data sets. Thus, some causal partitioning methods have been proposed to handle this problem. However, existing causal partitioning methods rely on high-order conditional independent (CI) tests, which makes them inefficient in handling dense causal graphs. Therefore, high-dimensionality is still a big challenge to these methods. In this work, we propose a new split-and-merge strategy to enable effective and scalable causality discovery. Different from the existing methods, our method uses only low-order CI tests, can get more accurate results and is applicable to various scenarios. We provide both theoretic analysis and empirical evaluation on the proposed method. Experiments on various real-world causal graphs show that the proposed method outperforms the stat-of-the-art method in terms of accuracy, efficiency and scalability. For high-dimensional cases, our method is much faster than the counterpart by one to three orders of magnitudes.

Identifying protein complexes is helpful for understanding cellular functions and designing drugs. In the last decades, many computational methods have been proposed based on detecting dense subgraphs or subnetworks in Protein-Protein Interaction Networks (PINs). However, the high rate of false positive/negative interactions in PINs prevents from the achievement of satisfactory detection results directly from PINs, because most of such existing methods exploit mainly topological information to do network partitioning. In this paper, we propose a new approach for protein complex detection by merging topological information of PINs and functional information of proteins. We first split proteins to a number of protein groups from the perspective of protein functions by using FunCat data. Then, for each of the resulting protein groups, we calculate two protein-protein similarity matrices: one is computed by using graph embedding over a PIN, the other is by using GO terms, and combine these two matrices to get an integrated similarity matrix. Following that, we cluster the proteins in each group based on the corresponding integrated similarity matrix, and obtain a number of small protein clusters. We map these clusters of proteins onto the PIN, and get a number of connected subgraphs. After a round of merging of overlapping subgraphs, finally we get the detected complexes. We conduct empirical evaluation on four PPI datasets (Collins, Gavin, Krogan, and Wiphi) with two complex benchmarks (CYC2008 and MIPS). Experimental results show that our method performs better than the state-of-the-art methods.

Novel road-network applications often recommend a moving object (e.g., a vehicle) about interesting services or tasks on its way to a destination. A taxi-sharing system, for instance, suggests a new passenger to a taxi while it is serving another one. The traveling cost is then shared among these passengers. A fundamental query is: given two nodes s and t, and an area A on road network graph , is there a “good” route (e.g., short enough path) P from s to t that crosses A in G? In a taxi-sharing system, s and t can be a taxi's current and destined locations, and A contains all the places to which a person waiting for a taxi is willing to walk. Answering this Route and Area Matching (ROAM) Query allows the application involved to recommend appropriate services to users efficiently. In this paper, we examine efficient ROAM query algorithms. Particularly, we develop solutions for finding a ρ-route, which is an s-t path that passes A, with a length of at most (1 + ρ) times the shortest distance between s and t. The existence of a ρ-route implies that a service or task located at A can be found for a given moving object m, and that m only deviates slightly from its current route. We present comprehensive studies on index-free and index-based algorithms for answering ROAM queries. Comprehensive experiments show that our algorithm runs up to 30 times faster than baseline algorithms.

Most of the existing methods for anomaly detection use only positive data to learn the data distribution, thus they usually need a pre-defined threshold at the detection stage to determine whether a test instance is an outlier. Unfortunately, a good threshold is vital for the performance and it is really hard to find an optimal one. In this paper, we take the discriminative information implied in unlabeled data into consideration and propose a new method for anomaly detection that can learn the labels of unlabelled data directly. Our proposed method has an end-to-end architecture with one encoder and two decoders that are trained to model inliers and outliers’ data distributions in a competitive way. This architecture works in a discriminative manner without suffering from overfitting, and the training algorithm of our model is adopted from SGD, thus it is efficient and scalable even for large-scale datasets. Empirical studies on 7 datasets including KDD99, MNIST, Caltech-256, and ImageNet etc. show that our model outperforms the state-of-the-art methods.

This paper addresses two important issues in causality inference. One is how to reduce redundant conditional independence (CI) tests, which heavily impact the efficiency and accuracy of existing constraint-based methods. Another is how to construct the true causal graph from a set of Markov equivalence classes returned by these methods.For the first issue, we design a recursive decomposition approach where the original data (a set of variables) is first decomposed into three small subsets, each of which is then recursively decomposed into three smaller subsets until none of subsets can be decomposed further. Consequently, redundant CI tests can be reduced by inferring causality from these subsets. Advantage of this decomposition scheme lies in two aspects: 1) it requires only low-order CI tests, and 2) it does not violate d-separation. Thus, the complete causality can be reconstructed by merging all the partial results of the subsets.For the second issue, we employ regression-based conditional independence test to check CIs in linear non-Gaussian additive noise cases, which can identify more causal directions by x−E(x|Z)⊥z (or y−E(y|Z)⊥z). Therefore, causal direction learning is no longer limited by the number of returned Vstructures and the consistent propagation.Extensive experiments show that the proposed method can not only substantially reduce redundant CI tests but also effectively distinguish the equivalence classes, thus is superior to the state of the art constraint-based methods in causality inference.

At the early stages of the drug discovery, molecule toxicity prediction is crucial to excluding drug candidates that are likely to fail in clinical trials. In this paper, we presented a novel molecular representation method and developed a corresponding deep learning-based framework called TOP (the abbreviation of TOxicity Prediction). TOP integrated a serial special data processing methods, a bidirectional gated recurrent unit-based RNN (BiGRU) and a fully connected neural network for end-to-end molecular representation learning and chemical toxicity prediction. TOP can automatically learn a mixed molecular representation from not only SMILES contextual information that describes the molecule structure, but also physiochemical properties. Therefore, TOP can overcome the drawbacks of existing methods that use either of them, thus greatly promotes toxicity prediction. We conducted extensive experiments over 14 classic toxicity prediction tasks on three different benchmark datasets, including balanced and imbalanced ones. The results show that, with the help of the novel molecular representation method, TOP significantly outperforms not only three baseline machine learning methods, but also five state-of-the-art methods.

Most existing ensemble methods aim to train the underlying embedded models independently and simply aggregate their final outputs via averaging or weighted voting. As many prediction tasks contain uncertainty, most of these ensemble methods just reduce variance of the predictions without considering the collaborations among the ensembles. Different from these ensemble methods, multiple choice learning (MCL) methods exploit the cooperation among all the embedded models to generate multiple diverse hypotheses. In this paper, a new MCL method, called vMCL (the abbreviation of versatile Multiple Choice Learning), is developed to extend the application scenarios of MCL methods by ensembling deep neural networks. Our vMCL method keeps the advantage of existing MCL methods while overcoming their major drawback, thus achieves better performance. The novelty of our vMCL lies in three aspects: (1) a choice network is designed to learn the confidence level of each specialist which can provide the best prediction base on multiple hypotheses; (2) a hinge loss is introduced to alleviate the overconfidence issue in MCL settings; (3) Easy to be implemented and can be trained in an end-to-end manner, which is a very attractive feature for many real-world applications. Experiments on image classification and image segmentation task show that vMCL outperforms the existing state-of-the-art MCL methods.

Video compression artifact reduction aims to recover high-quality videos from low-quality compressed videos. Most existing approaches use a single neighboring frame or a pair of neighboring frames (preceding and/or following the target frame) for this task. Furthermore, as frames of high quality overall may contain low-quality patches, and high-quality patches may exist in frames of low quality overall, current methods focusing on nearby peak-quality frames (PQFs) may miss high-quality details in low-quality frames. To remedy these shortcomings, in this paper we propose a novel end-to-end deep neural network called non-local ConvLSTM (NL-ConvLSTM in short) that exploits multiple consecutive frames. An approximate non-local strategy is introduced in NL-ConvLSTM to capture global motion patterns and trace the spatiotemporal dependency in a video sequence. This approximate strategy makes the non-local module work in a fast and low space-cost way. Our method uses the preceding and following frames of the target frame to generate a residual, from which a higher quality frame is reconstructed. Experiments on two datasets show that NL-ConvLSTM outperforms the existing methods.

Although exploratory search has received significant attention recently in the context of structured data, scant attention has been paid for graph-structured data. In this paper, we present two novel index structures called VACCINE and ADVISE to efficiently support exploratory subgraph search in a visual environment (VESS). VACCINE is an offline, feature-based index that stores rich information related to frequent and infrequent subgraphs in the underlying graph database and how they can be transformed from one subgraph to another. ADVISE, on the other hand, is an adaptive, compact, on-the-fly index instantiated during iterative visual formulation/reformulation of a subgraph query for exploratory search and records relevant information to efficiently support its repeated evaluation. These indexes engender more efficient and scalable visual exploratory subgraph search framework compared to a state-of-the-art technique.

Video text spotting is still an important research topic due to its various real-applications. Previous approaches usually fall into the four-staged pipeline: text detection in individual images, frame-wisely recognizing localized text regions, tracking text streams and generating final results with complicated post-processing skills, which might suffer from the huge computational cost as well as the interferences of low-quality text. In this paper, we propose a fast and robust video text spotting framework by only recognizing the localized text one-time instead of frame-wisely recognition. Specifically, we first obtain text regions in videos with a well-designed spatial-temporal detector. Then we concentrate on developing a novel text recommender for selecting the highest-quality text from text streams and only recognizing the selected ones. Here, the recommender assembles text tracking, quality scoring and recognition into an end-to-end trainable module, which not only avoids the interferences from low-quality text but also dramatically speeds up the video text spotting process. In addition, we collect a larger scale video text dataset (LSVTD) for promoting the video text spotting community, which contains 100 text videos from 22 different real-life scenarios. Extensive experiments on two public benchmarks show that our method greatly speeds up the recognition process averagely by 71 times compared with the frame-wise manner, and also achieves the remarkable state-of-the-art.

Visual graph query interfaces (a.k.a gui ) widen the reach of graph querying frameworks across different users by enabling non-programmers to use them. Consequently, several commercial and academic frameworks for querying a large collection of small- or medium-sized data graphs (\textite.g., chemical compounds) provide such visual interfaces. Majority of these interfaces expose a fixed set ofcanned patterns (\textiti.e., small subgraph patterns) to expedite query formulation by enabling pattern-at-a-time in lieu of edge-at-a-time construction mode. Canned patterns to be displayed on a gui are typically selected manually based on domain knowledge. However, manual generation of canned patterns is labour intensive. Furthermore, these patterns may not sufficiently cover the underlying data graphs to expedite visual formulation of a wide range of subgraph queries. In this paper, we present a generic and extensible framework called Catapult to address these limitations. Catapult takes a data-driven approach toautomatically select canned patterns, thereby taking a concrete step towards the vision of data-driven construction of visual query interfaces. Specifically, it firstclusters the underlying data graphs based on their topological similarities and thensummarize each cluster to create acluster summary graph (csg ). The canned patterns within a user-specifiedpattern budget are then generated from these csg s by maximizingcoverage anddiversity, and minimizingcognitive load of the patterns. Experimental study with real-world datasets and visual graph interfaces demonstrates the superiority of Catapult compared to traditional techniques.

BACKGROUND: Super-enhancers (SEs) are clusters of transcriptional active enhancers, which dictate the expression of genes defining cell identity and play an important role in the development and progression of tumors and other diseases. Many key cancer oncogenes are driven by super-enhancers, and the mutations associated with common diseases such as Alzheimer's disease are significantly enriched with super-enhancers. Super-enhancers have shown great potential for the identification of key oncogenes and the discovery of disease-associated mutational sites. RESULTS: In this paper, we propose a new computational method called DEEPSEN for predicting super-enhancers based on convolutional neural network. The proposed method integrates 36 kinds of features. Compared with existing approaches, our method performs better and can be used for genome-wide prediction of super-enhancers. Besides, we screen important features for predicting super-enhancers. CONCLUSION: Convolutional neural network is effective in boosting the performance of super-enhancer prediction.

Privacy has received increasing concerns in publication of datasets that contain sensitive information. Preventing privacy disclosure and providing useful information to legitimate users for data mining are conflicting goals. Generalization and randomized response methods were proposed in database community to tackle this problem. However, both of them have postulated the same prior belief for all transactions, which might be wrong modeling and lead to privacy breach. Besides, generalization and randomized response methods usually require a privacy controlling parameter to control the tradeoff between privacy and data quality, which may put the data publishers in a dilemma. In this paper, a novel privacy preserving method for data publication is proposed based on conditional probability distribution and machine learning techniques, which can achieve different prior beliefs for different transactions. A basic cross sampling algorithm and a complete cross sampling algorithm are designed respectively for the settings of single sensitive attribute and multiple sensitive attributes, and an improved complete algorithm is developed by using Gibbs sampling, in order to enhance data utility when data are not sufficient. Our method can offer stronger privacy guarantee, while, as shown in the extensive experiments, retaining better data utility.

This special section consists of eight papers selected from the accepted papers of the 27th International Conference on Genome Informatics (GIW2016), which was held in Shanghai, China, October 3-5, 2016. These papers cover diverse topics, including gene clustering, protein-protein interaction network inference, essential proteins identification, glycan structure identification, lncRNA function prediction, lncRNA-disease association prediction, signal transduction network construction, and parallel algorithms.

We investigate the relationship between conditional independence (CI) x ⫫ y | Z and the independence of two residuals x −E( x | Z )⫫ y −E( y | Z ), where x and y are two random variables and Z is a set of random variables. We show that if x , y , and Z are generated by following linear structural equation models and all external influences follow joint Gaussian distribution, then x ⫫ y | Z if and only if x −E( x | Z )⫫ y −E( y | Z ). That is, the test of x ⫫ y | Z can be relaxed to a simpler unconditional independence test of x −E( x | Z )⫫ y −E( y | Z ). Furthermore, testing x −E( x | Z )⫫ y −E( y | Z ) can be simplified by testing x −E( x | Z )⫫ y or y −E( y | Z )⫫ x . On the other side, if all these external influences follow non-Gaussian distributions and the model satisfies structural faithfulness condition, then we have x ⫫ y | Z ⇔ x −E( x | Z )⫫ y −E( y | Z ). We apply the results above to the causal discovery problem, where the causal directions are generally determined by a set of V -structures and their consistent propagations, so CI test-based methods can return a set of Markov equivalence classes. We show that in the linear non-Gaussian context, in many cases x −E( x | Z )⫫ z or y −E( y | Z )⫫ z (∀ z ∈ Z and Z is a minimal d -separator) is satisfied when x −E( x | Z )⫫ y −E( y | Z ), which implies z causes x (or y ) if z directly connects to x (or y ). Therefore, we conclude that CIs have useful information for distinguishing Markov equivalence classes. In summary, comparing with the existing discretization-based and kernel-based CI testing methods, the proposed method provides a simpler way to measure CI, which needs only one unconditional independence test and two regression operations. When being applied to causal discovery, it can find more causal relationships, which is extensively validated by experiments.

Emerging on-demand transport services, such as Uber and GoGoVan, usually face the dilemma of demand supply imbalance, meaning that the spatial distributions of orders and drivers are imbalanced. Due to such imbalance, much supply resource is wasted while a considerable amount of order demand cannot be met in time. To address this dilemma, knowing the unmet demand in the near future is of high importance for service providers because they can dispatch their vehicles in advance to alleviate the impending demand supply imbalance, we develop a general framework for predicting the unmet demand in future time slots. Under this framework, we first evaluate the predictability of unmet demand in on-demand transport services and find that unmet demand is highly predictable. Then, we extract both static and dynamic urban features relevant to unmet demand from data sets in multiple domains. Finally, multiple prediction models are trained to predict unmet demand by using the extracted features. As demonstrated via experiments, the proposed framework can predict unmet demand in on-demand transport services effectively and flexibly.

We investigate the relationship between conditional independence (CI) x ⊥ y|Z and the independence of two residuals x – E(x|Z) ⊥ –E(y|Z), where x and y are two random variables, and Z is a set of random variables. We show that if x, y and Z are generated by following linear structural equation model and all external influences follow Gaussian distributions, then x ⊥ y|Z if and only if x – E(x|Z) ⊥ y – E(y|Z). That is, the test of x ⊥ y|Z can be relaxed to a simpler unconditional independence test of x – E(x|Z) ⊥ y – E(y|Z). Furthermore, if all these external influences follow non-Gaussian distributions and the model satisfies structural faithfulness condition, then we have x ⊥ y|Z ⇔ x – E(x|Z) ⊥ y – E(y|Z). We apply the results above to the causal discovery problem, where the causal directions are generally determined by a set of V-structures and their consistent propagations, so CI test-based methods can return a set of Markov equivalence classes. We show that in linear non-Gaussian context, x – E(x|Z) ⊥ y – E(y|Z) ⇒ x – E(x|Z) ⊥ z or y – E(y|Z ⊥ z (∀z ∈ Z) if Z is a minimal d-separator, which implies z causes x (or y) if z directly connects to x (or y). Therefore, we conclude that CIs have useful information for distinguishing Markov equivalence classes. In summary, compared with the existing discretization-based and kernel-based CI testing methods, the proposed method provides a simpler way to measure CI, which needs only one unconditional independence test and two regression operations. When being applied to causal discovery, it can find more causal relationships, which is experimentally validated.

We consider the scene text recognition problem under the attention-based encoder-decoder framework, which is the state of the art. The existing methods usually employ a frame-wise maximal likelihood loss to optimize the models. When we train the model, the misalignment between the ground truth strings and the attention's output sequences of probability distribution, which is caused by missing or superfluous characters, will confuse and mislead the training process, and consequently make the training costly and degrade the recognition accuracy. To handle this problem, we propose a novel method called edit probability (EP) for scene text recognition. EP tries to effectively estimate the probability of generating a string from the output sequence of probability distribution conditioned on the input image, while considering the possible occurrences of missing/superfluous characters. The advantage lies in that the training process can focus on the missing, superfluous and unrecognized characters, and thus the impact of the misalignment problem can be alleviated or even overcome. We conduct extensive experiments on standard benchmarks, including the IIIT-5K, Street View Text and ICDAR datasets. Experimental results show that the EP can substantially boost scene text recognition performance.

Recognizing text from natural images is a hot research topic in computer vision due to its various applications. Despite the enduring research of several decades on optical character recognition (OCR), recognizing texts from natural images is still a challenging task. This is because scene texts are often in irregular (e.g. curved, arbitrarily-oriented or seriously distorted) arrangements, which have not yet been well addressed in the literature. Existing methods on text recognition mainly work with regular (horizontal and frontal) texts and cannot be trivially generalized to handle irregular texts. In this paper, we develop the arbitrary orientation network (AON) to directly capture the deep features of irregular texts, which are combined into an attention-based decoder to generate character sequence. The whole network can be trained end-to-end by using only images and word-level annotations. Extensive experiments on various benchmarks, including the CUTE80, SVT-Perspective, IIIT5k, SVT and ICDAR datasets, show that the proposed AON-based method achieves the-state-of-the-art performance in irregular datasets, and is comparable to major existing methods in regular datasets.

The widespread location-aware applications produce a vast amount of spatio-textual data that contains both spatial and textual attributes. To make use of this enriched information for users to describe their preferences for travel routes, we propose a Bounded-Cost Informative Route (BCIR) query to retrieve the routes that are the most textually relevant to the user-specified query keywords subject to a travel cost constraint. BCIR query is particularly helpful for tourists and city explorers to plan their travel routes. We will show that BCIR query is an NP-hard problem. To answer BCIR query efficiently, we propose an exact solution with effective pruning techniques and an approximate solution with performance guarantee. Extensive experiments over real data sets demonstrate that the proposed solutions achieve the expected performance.

Visual graph query interfaces (a.k.a GUI) make it easy for non-expert users to query graphs. Recent research has laid out and implemented a vision of a novel subgraph query processing paradigm where the latency offered by the GUI is exploited to blend visual query construction and processing by generating and refining candidate result matches iteratively during query formulation. This paradigm brings in several potential benefits such as superior system response time (srt) and opportunities to enhance usability of graph databases. However, these early efforts focused on subgraph isomorphism-based graph queries where blending is performed by iterative edge-to-edge mapping. In this paper, we explore how this vision can be realized for more generic but complex 1-1 p-homomorphic p-hom) queries introduced by Fan et al. A 1-1 p-hom query maps an edge of the query to paths in the data graph. We present a novel framework called BOOMER for blending bounded 1-1 p-hom (bph ) queries, a variant of 1-1 p-hom where the length of the path is bounded instead of arbitrary length. Our framework is based on a novel online , adaptive indexing scheme called cap index. We present two strategies for CAP index construction, immediate and deferment-based, and show how they can be utilized to facilitate judicious interleaving of visual bph query formulation and query processing. BOOMER is also amenable to modifications to a bph query during visual formulation. Experiments on real-world datasets demonstrate both efficiency and effectiveness of Boomer for realizing the visual querying paradigm on an important type of graph query.

BACKGROUND: The default mode network (DMN) in resting state has been increasingly used in disease diagnosis since it was found in 2001. Prior work has mainly focused on extracting a single DMN with various techniques. However, by using seeding-based analysis with more than one desirable seed, we can obtain multiple DMNs, which are likely to have complementary information, and thus are more promising for disease diagnosis. In the study, we used 18 early mild cognitive impairment (EMCI) participants and 18 late mild cognitive impairment (LMCI) participants of Alzheimer's disease (AD). First, we used seeding-based analysis with four seeds to extract four DMNs for each subject. Then, we conducted fusion analysis for all different combinations of the four DMNs. Finally, we carried out nonlinear support vector machine classification based on the mixing coefficients from the fusion analysis. RESULTS: We found that (1) the four DMNs corresponding to the four different seeds indeed capture different functional regions of each subject; (2) Maps of the four DMNs in the most different joint source from fusion analysis are centered at the regions of the corresponding seeds; (3) Classification results reveal the effectiveness of using multiple seeds to extract DMNs. When using a single seed, the regions of posterior cingulate cortex (PCC) extractions of EMCI and LMCI show the largest difference. For multiple-seed cases, the regions of PCC extraction and right lateral parietal cortex (RLP) extraction provide complementary information for each other in fusion, which improves the classification accuracy. Furthermore, the regions of left lateral parietal cortex (LLP) extraction and RLP extraction also have complementary effect in fusion. In summary, AD diagnosis can be improved by exploiting complementary information of DMNs extracted with multiple seeds. CONCLUSIONS: In this study, we applied fusion analysis to the DMNs extracted by using different seeds for exploiting the complementary information hidden among the separately extracted DMNs, and the results supported our expectation that using the complementary information can improve classification accuracy.

Prediction of compound-protein interactions (CPIs) is to find new compound-protein pairs where a protein is targeted by at least a compound, which is a crucial step in new drug design. Currently, a number of machine learning based methods have been developed to predict new CPIs in the literature. However, as there is not yet any publicly available set of validated negative CPIs, most existing machine learning based approaches use the unknown interactions (not validated CPIs) selected randomly as the negative examples to train classifiers for predicting new CPIs. Obviously, this is not quite reasonable and unavoidably impacts the CPI prediction performance. In this paper, we simply take the unknown CPIs as unlabeled examples, and propose a new method called PUCPI (the abbreviation of PU learning for Compound-Protein Interaction identification) that employs biased-SVM (Support Vector Machine) to predict CPIs using only positive and unlabeled examples. PU learning is a class of learning methods that leans from positive and unlabeled (PU) samples. To the best of our knowledge, this is the first work that identifies CPIs using only positive and unlabeled examples. We first collect known CPIs as positive examples and then randomly select compound-protein pairs not in the positive set as unlabeled examples. For each CPI/compound-protein pair, we extract protein domains as protein features and compound substructures as chemical features, then take the tensor product of the corresponding compound features and protein features as the feature vector of the CPI/compound-protein pair. After that, biased-SVM is employed to train classifiers on different datasets of CPIs and compound-protein pairs. Experiments over various datasets show that our method outperforms six typical classifiers, including random forest, L1- and L2-regularized logistic regression, naive Bayes, SVM and k-nearest neighbor (kNN), and three types of existing CPI prediction models. More information can be found at http://admis.fudan.edu.cn/projects/pucpi.html.

Machine learning and artificial intelligence techniques have been applied to construct online portfolio selection strategies recently. A popular and state-of-the-art family of strategies is to explore the reversion phenomenon through online learning algorithms and statistical prediction models. Despite gaining promising results on some benchmark datasets, these strategies often adopt a single model based on a selection criterion (e.g., breakdown point) for predicting future price. However, such model selection is often unstable and may cause unnecessarily high variability in the final estimation, leading to poor prediction performance in real datasets and thus non-optimal portfolios. To overcome the drawbacks, in this article, we propose to exploit the reversion phenomenon by using combination forecasting estimators and design a novel online portfolio selection strategy, named Combination Forecasting Reversion (CFR), which outputs optimal portfolios based on the improved reversion estimator. We further present two efficient CFR implementations based on online Newton step (ONS) and online gradient descent (OGD) algorithms, respectively, and theoretically analyze their regret bounds, which guarantee that the online CFR model performs as well as the best CFR model in hindsight. We evaluate the proposed algorithms on various real markets with extensive experiments. Empirical results show that CFR can effectively overcome the drawbacks of existing reversion strategies and achieve the state-of-the-art performance.

With the proliferation of positioning technologies and GPS-enabled mobile devices, it has become very important to search for optimal paths to cover required points of interest(POIs, e.g., banks and restaurants) over road networks in many location-based services. In practice, however, traffic conditions are inherently uncertain and dynamically changing overtime, which makes it rather challenging to provide accurate results for path queries based on travelling time. Inspired by this, we considerthe practical settings of road networks and model them by uncertain road networks (URNs) on which the travelling time of each road is uncertain and captured by a set of travelling time samples. Then, we formalize the probabilistic time-constrained path (PTP) query over uncertain road networks to retrieve those paths that not only cover required POIs with constrained service time but also have the minimum travelling times in high confidence. We prove that PTPquery problem is NP-hard. In orderto answer PTPqueries efficiently, we propose an efficient PTPquery approach with effective pruning strategies regarding the time constraints on POIs and the probabilistic/rank requirements of queries. Extensive experiments on real road networks validate the efficiency and effectiveness of our PTPquery approach.

Conditional independence (CI) testing is an important tool in causal discovery. Generally, by using CI tests, a set of Markov equivalence classes w.r.t. the observed data can be estimated by checking whether each pair of variables x and y is d-separated, given a set of variables Z. Due to the curse of dimensionality, CI testing is often difficult to return a reliable result for high-dimensional Z. In this paper, we propose a regression-based CI test to relax the test of x ⊥ y|Z to simpler unconditional independence tests of x − f(Z) ⊥ y−g(Z), and x−f(Z) ⊥ Z or y−g(Z) ⊥ Z under the assumption that the data-generating procedure follows additive noise models (ANMs). When the ANM is identifiable, we prove that x − f(Z) ⊥ y − g(Z) ⇒ x ⊥ y|Z. We also show that 1) f and g can be easily estimated by regression, 2) our test is more powerful than the state-of-the-art kernel CI tests, and 3) existing causal learning algorithms can infer much more causal directions by using the proposed method.

Scene text recognition has been a hot research topic in computer vision due to its various applications. The state of the art is the attention-based encoder-decoder framework that learns the mapping between input images and output sequences in a purely data-driven way. However, we observe that existing attention-based methods perform poorly on complicated and/or low-quality images. One major reason is that existing methods cannot get accurate alignments between feature areas and targets for such images. We call this phenomenon “attention drift”. To tackle this problem, in this paper we propose the FAN (the abbreviation of Focusing Attention Network) method that employs a focusing attention mechanism to automatically draw back the drifted attention. FAN consists of two major components: an attention network (AN) that is responsible for recognizing character targets as in the existing methods, and a focusing network (FN) that is responsible for adjusting attention by evaluating whether AN pays attention properly on the target areas in the images. Furthermore, different from the existing methods, we adopt a ResNet-based network to enrich deep representations of scene text images. Extensive experiments on various benchmarks, including the IIIT5k, SVT and ICDAR datasets, show that the FAN method substantially outperforms the existing methods.

Big data clusters introduce an intermediate cache layer between the computing frameworks and the underlying distributed file systems, to enable upper-level applications or end users to efficiently access big datasets in cache and effectively share them among different computing frameworks. As caches are shared by multiple applications or end users, directly applying existing on-demand caching strategies will result in intense conflicts, when big datasets are cached as a whole. Meanwhile, big data applications usually involve massive numbers of file scans, cached-in data blocks may have little chance of being accessed before they are cached out to make way for other on-demand data blocks. Thus, it is unwise to cache data blocks long before they are actually accessed. In this paper, we propose a novel just-enough big data caching scheme for just-in-time block prefetching to improve the cache effectiveness of big data clusters. With just-in-time block prefetching, a block is cached in just before the task begins to process the block, rather than being cached in along with other blocks of the same dataset being processed. We monitor block accesses to measure the average processing time of data blocks, and then estimate the minimal number of blocks that should be kept in cache for a big dataset, so that the speed of data processing matches with that of data prefetching, and each upper-level task can obtain its input blocks from cache just in time. Our experimental results show that the proposed cache method can restrain over-requirement of cache resources in big data applications, and provides the same performance improvement as when all data blocks are cached.

Considering the drawbacks of existing reversion based on-line portfolio selection (PS) strategies, we propose a new on-line learning and reversion based strategy that is called Gaussian Weighting Reversion (GWR in short). On the one hand, to exploit the "time validity" of historical market data, which means that the more recent market data are more valuable to market prediction than the less recent market data, we use the Gaussian function to weight data in a moving window. On the other hand, for each time point we average two predictions to alleviate the impact of noise and outliers. We conduct extensive evaluation on six real market datasets and compare our strategy with nine existing methods, including the state of the art ones. Experimental results show that our method outperforms the existing methods.

BACKGROUND: Studies have shown that enhancers are significant regulatory elements to play crucial roles in gene expression regulation. Since enhancers are unrelated to the orientation and distance to their target genes, it is a challenging mission for scholars and researchers to accurately predicting distal enhancers. In the past years, with the high-throughout ChiP-seq technologies development, several computational techniques emerge to predict enhancers using epigenetic or genomic features. Nevertheless, the inconsistency of computational models across different cell-lines and the unsatisfactory prediction performance call for further research in this area. RESULTS: Here, we propose a new Deep Belief Network (DBN) based computational method for enhancer prediction, which is called EnhancerDBN. This method combines diverse features, composed of DNA sequence compositional features, DNA methylation and histone modifications. Our computational results indicate that 1) EnhancerDBN outperforms 13 existing methods in prediction, and 2) GC content and DNA methylation can serve as relevant features for enhancer prediction. CONCLUSION: Deep learning is effective in boosting the performance of enhancer prediction.

BACKGROUND: Differences in chromatin states are critical to the multiplicity of cell states. Recently genome-wide histone modification maps of diverse human developmental stages and tissues have been charted. DESCRIPTION: To facilitate the investigation of epigenetic dynamics and regulatory mechanisms in cellular differentiation processes, we developed iHMS, an integrated human histone modification database that incorporates massive histone modification maps spanning different developmental stages, lineages and tissues ( http://www.tongjidmb.com/human/index.html ). It also includes genome-wide expression data of different conditions, reference gene annotations, GC content and CpG island information. By providing an intuitive and user-friendly query interface, iHMS enables comprehensive query and comparative analysis based on gene names, genomic region locations, histone modification marks and cell types. Moreover, it offers an efficient browser that allows users to visualize and compare multiple genome-wide histone modification maps and related expression profiles across different developmental stages and tissues. CONCLUSION: iHMS is of great helpfulness to understand how global histone modification state transitions impact cellular phenotypes across different developmental stages and tissues in the human genome. This extensive catalog of histone modification states thus presents an important resource for epigenetic and developmental studies.

BACKGROUND: Predicting protein complexes from protein-protein interaction (PPI) networks has been studied for decade. Various methods have been proposed to address some challenging issues of this problem, including overlapping clusters, high false positive/negative rates of PPI data and diverse complex structures. It is well known that most current methods can detect effectively only complexes of size ≥3, which account for only about half of the total existing complexes. Recently, a method was proposed specifically for finding small complexes (size = 2 and 3) from PPI networks. However, up to now there is no effective approach that can predict both small (size ≤ 3) and large (size >3) complexes from PPI networks. RESULTS: In this paper, we propose a novel method, called CPredictor2.0, that can detect both small and large complexes under a unified framework. Concretely, we first group proteins of similar functions. Then, the Markov clustering algorithm is employed to discover clusters in each group. Finally, we merge all discovered clusters that overlap with each other to a certain degree, and the merged clusters as well as the remaining clusters constitute the set of detected complexes. Extensive experiments have shown that the new method can more effectively predict both small and large complexes, in comparison with the state-of-the-art methods. CONCLUSIONS: The proposed method, CPredictor2.0, can be applied to accurately predict both small and large protein complexes.

BACKGROUND: Long non-coding RNA (lncRNA) plays important roles in many biological and pathological processes, including transcriptional regulation and gene regulation. As lncRNA interacts with multiple proteins, predicting lncRNA-protein interactions (lncRPIs) is an important way to study the functions of lncRNA. Up to now, there have been a few works that exploit protein-protein interactions (PPIs) to help the prediction of new lncRPIs. RESULTS: In this paper, we propose to boost the prediction of lncRPIs by fusing multiple protein-protein similarity networks (PPSNs). Concretely, we first construct four PPSNs based on protein sequences, protein domains, protein GO terms and the STRING database respectively, then build a more informative PPSN by fusing these four constructed PPSNs. Finally, we predict new lncRPIs by a random walk method with the fused PPSN and known lncRPIs. Our experimental results show that the new approach outperforms the existing methods. CONCLUSION: Fusing multiple protein-protein similarity networks can effectively boost the performance of predicting lncRPIs.

Summary Modern communication networks and social networks are the main tunnels of knowledge diffusion. Knowledge diffusion in complex networks is different from the epidemic‐like information spreading, because individuals are willing to learn and spread knowledge to their friends and the learning process can hardly be achieved in a few conversations. In this paper, we investigate the important issue as what topological structure is suitable for knowledge diffusion. We propose a new knowledge diffusion model, where both learning and forgetting mechanisms are considered. In this model, individuals can play imparter and learner simultaneously. Comparing knowledge diffusion on a series of complex topologies, we observe that the individuals with a large degree can quickly learn more knowledge, who are beneficial to knowledge diffusion. Our results surprisingly reveal that the networks with high degree‐heterogeneity are likely to be suitable for knowledge diffusion. Our finding suggests that enhancing the degree heterogeneity of existing social networks may help to improve the performance of knowledge diffusion. This result is well confirmed by our extensive simulation results. Our model therefore provides a theoretical framework for understanding knowledge diffusion in complex topologies. Copyright © 2016 John Wiley & Sons, Ltd.

Recently, exploratory search has received much attention in information retrieval and database fields. This search paradigm assists users who do not have a clear search intent and are unfamiliar with the underlying data space. Specifically, query formulation evolves iteratively as the user becomes more familiar with the content. Despite its growing importance, exploratory search on graph-structured data has received little attention in the literature. We demonstrate a system called picasso to realize exploratory sub-structure search on a graph database containing a set of small or medium-sized data graphs. picasso embodies several novel features such as progressive ( i.e. , iterative) formulation of queries visually and incremental processing, multi-stream results exploration wall to visualize, explore, and analyze search results to identify possible search directions.

The widespread location-aware applications produce a vast amount of spatio-textual data that contains both spatial and textual attributes. To make use of this enriched information for users to describe their preferences for travel routes, we propose a Bounded-Cost Informative Route (BCIR) query to retrieve the routes that are the most textually relevant to the user-specified query keywords subject to a travel cost constraint. BCIR query is particularly helpful for tourists and city explorers to plan their travel routes. We will show that BCIR query is an NP-hard problem. To answer BCIR query efficiently, we propose an exact solution with effective pruning techniques and two approximate solutions with performance guarantees. Extensive experiments over real data sets demonstrate that the proposed solutions achieve the expected performance.

Various sparse regularizers have been applied to machine learning problems, among which structured sparsity has been proposed for a better adaption to structured data. In this paper, motivated by effectively classifying linked data (e.g. Web pages, tweets, articles with references, and biological network data) where a group structure exists over the whole dataset and links exist between specific samples, we propose a joint sparse representation model that combines group sparsity and graph sparsity, to select a small number of connected components from the graph of linked samples, meanwhile promoting the sparsity of edges that link samples from different groups in each connected component. Consequently, linked samples are selected from a few sparsely-connected groups. Both theoretical analysis and experimental results on four benchmark datasets show that the joint sparsity model outperforms traditional group sparsity model and graph sparsity model, as well as the latest group-graph sparsity model.

Group sparse representation (GSR) exploits group structure in data and works well on many problems. However, the group structure must be manually given in advance. In many practical scenarios such as classification, samples are grouped according to their labels. Constructing a consistent group structure in such cases is not easy. The reasons are: 1) samples may be incorrectly labeled; and 2) label assigning in big data is time-consuming and expensive. In this paper, we propose and formulate a new problem, semi-supervised group sparse representation (SS-GSR) to support group sparse representation among both labeled and unlabeled data, while learning a more robust group structure, which can be further exploited to more effectively represent other unlabeled data. We develop a model to tackle the SS-GSR problem, based on the manifold assumption in subspace segmentation that samples in the same group lie close in feature space and span the same subspace. We also propose an alternating algorithm to solve the model. Finally, we validate the model via extensive experiments.

Graph coloring is a fundamental NP-hard problem in graph theory. It has a wide range of real applications, such as Operations Research, Communication Network, Computational Biology and Compiler Optimization. Notable efforts have been spent on designing its approximation algorithms. Halldrsson proposed the algorithm (denoted as SampleIS) with the current best known approximation ratio. However, its time complexity is O(|G|3), where |G| is the number of vertices of a graph G. It is clear that SampleIS is not practical for large graphs. In this paper, we propose a practical vertex-cut based coloring technique (VColor) for coloring large graphs. First, we partition G into k connected components (CCs) of a small size s by removing a vertex-cut component (VCC). For each CC, we apply our novel coloring algorithm, based on maximal independent set enumeration. The approximation ratio and the time complexity for coloring the k CCs are log s + 1 and O(ks23s/3), respectively, whereas those of SampleIS are ks(log log ks)2/ log3 ks and O(k3s3). For the VCC, we simply apply SampleIS. To combine the colorings of the CCs and the VCC, we propose a maximum matching based algorithm. Second, in the context of a database of graphs, users may color many graphs. We propose an optimization technique, inspired by multi-query optimization, for coloring a set of graphs. We design a VP hierarchy (VPH) to represent the common subgraphs as the common CCs. Third, we propose techniques for determining the optimal values of the parameters of VColor. Our extensive experimental evaluation on real-world graphs confirms the efficiency and/or effectiveness of our proposed techniques. In particular, VColor is more than 500 times faster than SampleIS, and the number of colors used are comparable on real graphs Yeast and LS.

Many graphs in real-world applications, such as telecommunications networks, social-interaction graphs and co-authorship graphs, contain temporal information. However, existing graph mining algorithms fail to exploit these temporal information and the resulting subgraph patterns do not contain any temporal attribute. In this paper, we study the problem of mining a set of diversified temporal subgraph patterns from a temporal graph, where each subgraph is associated with the time interval that the pattern spans. This problem motivates important applications such as finding social trends in social networks, or detecting temporal hotspots in telecommunications networks. We propose a divide-and-conquer algorithm along with effective pruning techniques, and our approach runs 2 to 3 orders of magnitude faster than a baseline algorithm and obtains high-quality temporal subgraph patterns in real temporal graphs.

Mutual information (MI) is a powerful concept for correlation-centric applications. It has been used for feature selection from microarray gene expression data in many works. One of the merits of MI is that, unlike many other heuristic methods, it is based on a mature theoretic foundation. When applied to microarray data, however, it faces some challenges. First, due to the large number of features (i.e., genes) present in microarray data, the true distributions for the expression values of some genes may be distorted by noise. Second, evaluating inter-group mutual information requires estimating multi-variate distributions, which is quite difficult if not impossible. To address these problems, in this paper, we propose a new MI-based feature selection approach for microarray data. Our approach relies on two strategies: one is relevance boosting, which requires a desirable feature to show substantially additional relevance with class labeling beyond the already selected features, the other is feature interaction enhancing, which probabilistically compensates for feature interaction missing from simple aggregation-based evaluation. We justify our approach from both theoretical perspective and experimental results. We use a synthetic dataset to show the statistical significance of the proposed strategies, and real-life datasets to show the improved performance of our approach over the existing methods.

Online portfolio selection has attracted increasing attention from data mining and machine learning communities in recent years. An important theory in financial markets is mean reversion, which plays a critical role in some state-of-the-art portfolio selection strategies. Although existing mean reversion strategies have been shown to achieve good empirical performance on certain datasets, they seldom carefully deal with noise and outliers in the data, leading to suboptimal portfolios, and consequently yielding poor performance in practice. In this paper, we propose to exploit the reversion phenomenon by using robust$L_1$-median estimators, and design a novel online portfolio selection strategy named “Robust Median Reversion” (RMR), which constructs optimal portfolios based on the improved reversion estimator. We examine the performance of the proposed algorithms on various real markets with extensive experiments. Empirical results show that RMR can overcome the drawbacks of existing mean reversion algorithms and achieve significantly better results. Finally, RMR runs in linear time, and thus is suitable for large-scale real-time algorithmic trading applications.

Group sparsity has drawn much attention in machine learning. However, existing work can handle only datasets with certain group structures, where each sample has a certain membership with one or more groups. This paper investigates the learning of sparse representations from datasets with uncertain group structures, where each sample has an uncertain member-ship with all groups in terms of a probability distribution. We call this problem uncertain group sparse representation (UGSR in short), which is a generalization of the standard group sparse representation (GSR). We formulate the UGSR model and propose an efficient algorithm to solve this problem. We apply UGSR to text emotion classification and aging face recognition. Experiments show that UGSR outperforms standard sparse representation (SR) and standard GSR as well as fuzzy kNN classification.

The identification of interactions between compounds and proteins plays an important role in network pharmacology and drug discovery. However, experimentally identifying compound-protein interactions (CPIs) is generally expensive and time-consuming, computational approaches are thus introduced. Among these, machine-learning based methods have achieved a considerable success. However, due to the nonlinear and imbalanced nature of biological data, many machine learning approaches have their own limitations. Recently, deep learning techniques show advantages over many state-of-the-art machine learning methods in many applications. In this study, we aim at improving the performance of CPI prediction based on deep learning, and propose a method called DL-CPI (the abbreviation of Deep Learning for Compound-Protein Interactions prediction), which employs deep neural network (DNN) to effectively learn the representations of compound-protein pairs. Extensive experiments show that DL-CPI can learn useful features of compound-protein pairs by a layerwise abstraction, and thus achieves better prediction performance than existing methods on both balanced and imbalanced datasets.

Subgraph queries have been a fundamental query for retrieving patterns from graph data. Due to the well known NP hardness of subgraph queries, those queries may sometimes take a long time to complete. Our recent investigation on real- world datasets revealed that the performance of queries on graphs generally varies greatly. In other words, query clients may occasionally encounter “unexpectedly” long execution from a subgraph query processor. This paper aims to demonstrate a tool that alleviates the problem by monitoring subgraph query progress. Specifically, we present a novel subgraph query progress indicator called PIGEON that exploits query-time information to report to users accurate estimated query progress. In the demonstration, users may interact with PIGEON to gain insights on the query evaluation, which include the following: Users are enabled to (i) monitor query progress; (ii) analyze the causes of long query times; and (iii) abort queries that run abnormally long, which may sometimes contain human errors.

In dynamic distinct counting, we want to maintain a multi-set S of integers under insertions to answer efficiently the query: how many distinct elements are there in S? In external memory, the problem admits two standard solutions. The first one maintains $S$ in a hash structure, so that the distinct count can be incrementally updated after each insertion using O(1) expected I/Os. A query is answered for free. The second one stores S in a linked list, and thus supports an insertion in O(1/B) amortized I/Os. A query can be answered in O(N/B log_{M/B} (N/B)) I/Os by sorting, where N=|S|, B is the block size, and M is the memory size. In this paper, we show that the above two naive solutions are already optimal within a polylog factor. Specifically, for any Las Vegas structure using N^{O(1)} blocks, if its expected amortized insertion cost is o(1/log B}), then it must incur Omega(N/(B log B)) expected I/Os answering a query in the worst case, under the (realistic) condition that N is a polynomial of B. This means that the problem is repugnant to update buffering: the query cost jumps from 0 dramatically to almost linearity as soon as the insertion cost drops slightly below Omega(1).

A public transportation network can often be modeled as a timetable graph where (i) each node represents a station; and (ii) each directed edge (u,v) is associated with a timetable that records the departure (resp. arrival) time of each vehicle at station u (resp. v). Several techniques have been proposed for various types of route planning on timetable graphs, e.g., retrieving the route from a node to another with the shortest travel time. These techniques, however, either provide insufficient query efficiency or incur significant space overheads.

MOTIVATION: Genome-wide association studies (GWASs) are commonly applied on human genomic data to understand the causal gene combinations statistically connected to certain diseases. Patients involved in these GWASs could be re-identified when the studies release statistical information on a large number of single-nucleotide polymorphisms. Subsequent work, however, found that such privacy attacks are theoretically possible but unsuccessful and unconvincing in real settings. RESULTS: We derive the first practical privacy attack that can successfully identify specific individuals from limited published associations from the Wellcome Trust Case Control Consortium (WTCCC) dataset. For GWAS results computed over 25 randomly selected loci, our algorithm always pinpoints at least one patient from the WTCCC dataset. Moreover, the number of re-identified patients grows rapidly with the number of published genotypes. Finally, we discuss prevention methods to disable the attack, thus providing a solution for enhancing patient privacy. AVAILABILITY AND IMPLEMENTATION: Proofs of the theorems and additional experimental results are available in the support online documents. The attack algorithm codes are publicly available at https://sites.google.com/site/zhangzhenjie/GWAS_attack.zip. The genomic dataset used in the experiments is available at http://www.wtccc.org.uk/ on request.

MOTIVATION: Computational prediction of compound-protein interactions (CPIs) is of great importance for drug design and development, as genome-scale experimental validation of CPIs is not only time-consuming but also prohibitively expensive. With the availability of an increasing number of validated interactions, the performance of computational prediction approaches is severely impended by the lack of reliable negative CPI samples. A systematic method of screening reliable negative sample becomes critical to improving the performance of in silico prediction methods. RESULTS: This article aims at building up a set of highly credible negative samples of CPIs via an in silico screening method. As most existing computational models assume that similar compounds are likely to interact with similar target proteins and achieve remarkable performance, it is rational to identify potential negative samples based on the converse negative proposition that the proteins dissimilar to every known/predicted target of a compound are not much likely to be targeted by the compound and vice versa. We integrated various resources, including chemical structures, chemical expression profiles and side effects of compounds, amino acid sequences, protein-protein interaction network and functional annotations of proteins, into a systematic screening framework. We first tested the screened negative samples on six classical classifiers, and all these classifiers achieved remarkably higher performance on our negative samples than on randomly generated negative samples for both human and Caenorhabditis elegans. We then verified the negative samples on three existing prediction models, including bipartite local model, Gaussian kernel profile and Bayesian matrix factorization, and found that the performances of these models are also significantly improved on the screened negative samples. Moreover, we validated the screened negative samples on a drug bioactivity dataset. Finally, we derived two sets of new interactions by training an support vector machine classifier on the positive interactions annotated in DrugBank and our screened negative interactions. The screened negative samples and the predicted interactions provide the research community with a useful resource for identifying new drug targets and a helpful supplement to the current curated compound-protein databases. AVAILABILITY: Supplementary files are available at: http://admis.fudan.edu.cn/negative-cpi/.

BACKGROUND: With the rapid development of high-throughput technologies, researchers can sequence the whole metagenome of a microbial community sampled directly from the environment. The assignment of these metagenomic reads into different species or taxonomical classes is a vital step for metagenomic analysis, which is referred to as binning of metagenomic data. RESULTS: In this paper, we propose a new method TM-MCluster for binning metagenomic reads. First, we represent each metagenomic read as a set of "k-mers" with their frequencies occurring in the read. Then, we employ a probabilistic topic model -- the Latent Dirichlet Allocation (LDA) model to the reads, which generates a number of hidden "topics" such that each read can be represented by a distribution vector of the generated topics. Finally, as in the MCluster method, we apply SKWIC -- a variant of the classical K-means algorithm with automatic feature weighting mechanism to cluster these reads represented by topic distributions. CONCLUSIONS: Experiments show that the new method TM-MCluster outperforms major existing methods, including AbundanceBin, MetaCluster 3.0/5.0 and MCluster. This result indicates that the exploitation of topic modeling can effectively improve the binning performance of metagenomic reads.

Nucleosomes and the free linker DNA between them assemble the chromatin. Nucleosome positioning plays an important role in gene transcription regulation, DNA replication and repair, alternative splicing, and so on. With the rapid development of ChIP-seq, it is possible to computationally detect the positions of nucleosomes on chromosomes. However, existing methods cannot provide accurate and detailed information about the detected nucleosomes, especially for the nucleosomes with complex configurations where overlaps and noise exist. Meanwhile, they usually require some prior knowledge of nucleosomes as input, such as the size or the number of the unknown nucleosomes, which may significantly influence the detection results. In this paper, we propose a novel approach DPNuc for identifying nucleosome positions based on the Dirichlet process mixture model. In our method, Markov chain Monte Carlo (MCMC) simulations are employed to determine the mixture model with no need of prior knowledge about nucleosomes. Compared with three existing methods, our approach can provide more detailed information of the detected nucleosomes and can more reasonably reveal the real configurations of the chromosomes; especially, our approach performs better in the complex overlapping situations. By mapping the detected nucleosomes to a synthetic benchmark nucleosome map and two existing benchmark nucleosome maps, it is shown that our approach achieves a better performance in identifying nucleosome positions and gets a higher F-score. Finally, we show that our approach can more reliably detect the size distribution of nucleosomes.

Genomic science is now facing an explosive increase of data thanks to the fast development of sequencing technology. This situation poses serious challenges to genomic data storage and transferring. It is desirable to compress data to reduce storage and transferring cost, and thus to boost data distribution and utilization efficiency. Up to now, a number of algorithms / tools have been developed for compressing genomic sequences. Unlike the existing algorithms, most of which treat genomes as one-dimensional text strings and compress them based on dictionaries or probability models, this paper proposes a novel approach called CoGI (the abbreviation of Compressing Genomes as an Image) for genome compression, which transforms the genomic sequences to a two-dimensional binary image (or bitmap), then applies a rectangular partition coding algorithm to compress the binary image. CoGI can be used as either a reference-based compressor or a reference-free compressor. For the former, we develop two entropy-based algorithms to select a proper reference genome. Performance evaluation is conducted on various genomes. Experimental results show that the reference-based CoGI significantly outperforms two state-of-the-art reference-based genome compressors GReEn and RLZ-opt in both compression ratio and compression efficiency. It also achieves comparable compression ratio but two orders of magnitude higher compression efficiency in comparison with XM--one state-of-the-art reference-free genome compressor. Furthermore, our approach performs much better than Gzip--a general-purpose and widely-used compressor, in both compression speed and compression ratio. So, CoGI can serve as an effective and practical genome compressor. The source code and other related documents of CoGI are available at: http://admis.fudan.edu.cn/projects/cogi.htm.

Non-rigid shape comparison based on manifold embeddingusing Generalized Multidimensional Scaling(GMDS) has attracted much attention for its highaccuracy. However, this method requires that shape surfaceis not elastic. In other words, it is sensitive totopological transformations such as stretching and compressing.To tackle this problem, we propose a new approachthat constructs a high-dimensional space to embedthe manifolds of shapes based on sparse representation,which is able to completely withstand rigid transformationsand considerably tolerate topological transformations.Experiments on TOSCA shapes validate theproposed approach.

Protein-protein interaction (PPI) networks are crucial for organisms. Many research efforts have thus been devoted to the study on the topological properties PPI networks. However, existing studies did not always report consistent results on the topological properties of PPI networks. This situation is primarily caused by the incompleteness of current PPI datasets. To solve this problem, in this paper we revisited the topological properties of PPI networks from the perspective of PPI dataset evolution. Concretely, we used twelve PPI datasets of Arabidopsis thaliana from different BioGRID database versions, and compared the topological properties of PPI networks built from the twelve datasets. Our results show that as the dataset evolves, the PPI network becomes more and more complete, all considered topological properties seemingly converge to stable values, which possibly indicate the topological nature of the complete Arabidopsis thaliana PPI network. Such findings can not be obtained from a few datasets as used in the existing works.

Spatial-keyword queries on road networks are receiving in-creasing attention with the prominence of location-based services. There is a growing need to handle queries on road networks in distributed environments because a large net-work is typically distributed over multiple machines and it will improve query throughput. However, all the existing work on spatial keyword queries is based on a centralized setting. In this paper, we develop a distributed solution to answering spatial keyword queries on road networks. Exam-ple queries include “find locations near a supermarket and a hospital, ” and “find Chinese restaurants within 500 meters from my current location. ” We define an operation for an-swering such queries and reduce the problem of answering a query into computing a function of such operations. We pro-pose a new distributed index that enables each machine to independently evaluate the operation on its network frag-ment in a distributed setting. We theoretically prove the space optimality of the proposed index technique. We con-duct experiments with a distributed setting. Experimen-tal results demonstrate the promising performance of our method.

Query processing that preserves both the query privacy at the client and the data privacy at the server is a new research problem. It has many practical applications, especially when the queries are about the sensitive attributes of records. However, most existing studies, including those originating from data outsourcing, address the data privacy and query privacy separately. Although secure multiparty computation (SMC) is a suitable computing paradigm for this problem, it has significant computation and communication overheads, thus unable to scale up to large datasets. Fortunately, recent advances in cryptography bring us two relevant tools - conditional oblivious transfer and homomorphic encryption. In this paper, we integrate database indexing techniques with these tools in the context of private search on key-value stores. We first present an oblivious index traversal framework, in which the server cannot trace the index traversal path of a query during evaluation. The framework is generic and can support a wide range of query types with a suitable homomorphic encryption algorithm in place. Based on this framework, we devise secure protocols for classic key search queries on B+-tree and R-tree indexes. Our approach is verified by both security analysis and performance study.

This paper studies two fundamental problems both of which are defined on a set S of elements drawn from an ordered domain. In the first problem--called approximate K-partitioning--we want to divide S into K disjoint partitions P1, ..., PK such that (i) every element in Pi is smaller than all the elements in Pj for any i, j satisfying 1 ≤ i < j ≤ K, and (ii) the size of each Pi (1 ≤ i ≤ K) falls in a given range [a, b]. In the second problem--called approximate K-splitters---we want to find K - 1 elements s_1, ..., sK-1 from S, such that the size of S ∩ (s_i, s_i-1] falls in a given range [a, b] (define dummy s_0 = - ∞ and s_K = ∞). We present I/O-efficient comparison-based algorithms for solving these problems, and establish their optimality by proving matching lower bounds. Our results reveal that the two problems are separated in terms of I/O complexity when K is small, but have the same hardness when K is large.

Nucleosome positioning plays an essential role in cellular processes by modulating accessibility of DNA to proteins. Many computational models have been developed to predict genome-wide nucleosome positions from DNA sequences. Comparative analysis of predicted and experimental nucleosome positioning maps facilitates understanding the regulatory mechanisms of transcription and DNA replication. Therefore, a comprehensive evaluation of existing computational methods is important and useful for biologists to choose appropriate ones in their research. In this article, we carried out a performance comparison among eight widely used computational methods on four species including yeast, fruitfly, mouse and human. In particular, we compared these methods on different regions of each species such as gene sequences, promoters and 5'UTR exons. The experimental results show that the performances of the two latest versions of the thermodynamic model are relatively steadier than the other four methods. Moreover, these methods are workable on four species, but their performances decrease gradually from yeast to human, indicating that the fundamental mechanism of nucleosome positioning is conserved through the evolution process, but more and more factors participate in the determination of nucleosome positions, which leads to sophisticated regulation mechanisms.

With the increase of available protein-protein interaction (PPI) data, more and more efforts have been put to PPI network modeling, and a number of models of PPI networks have been proposed. Roughly speaking, good models of PPI networks should be able to accurately describe PPI mechanisms, and thus reproduce the structures of PPI networks. With such models, theoretical and/or computational biologists can efficiently explore the evolution and dynamics of PPI networks. However, a theoretical and/or computational biologist may feel confused when she/he has to choose a proper PPI model for her/his research work from a dozen of candidate models, while there is no guideline available to help her/him. To tackle this problem, in this article, we carry out a comprehensive performance comparison study on 12 existing models over PPI datasets of four species (yeast, mouse, fruit fly and nematode), by comparing the global and local statistical properties of the original PPI networks and the model-reproduced ones. To draw more convincing conclusions, we use the mean reciprocal rank to combine the ranks of a certain model on all statistical properties. Our experimental results indicate that the PS_Seed model [Solé and Pastor-Satorras (PS) model with seed] the STICKY model and the DD_Seed model (Duplication-Divergence model with seed) fit best with the test PPI datasets. By analyzing the underlying mechanisms of the models with better fitting ability, our analysis shows that the evolutionary mechanism of node duplication and link dynamics and the mechanisms with 'degree-weighted' behaviors seem to be able to describe the PPI networks better.

Geography Markup Language (GML) has become a de facto standard for encoding and exchanging geographic data. Usually, GML documents are of huge size due to its verbose structures and textual data, hence it is very costly to store and transit them. In this paper, we propose an effective pattern-based approach to compressing GML documents. First, a tree-structured pattern from the GML document under compression is extracted. Then, a tree automaton for matching the document against the extracted pattern is constructed. While doing compression, the GML document is matched against the pattern to generate a bits-stream that represents the difference between the document's structure and the extracted pattern. Meanwhile, we separate document structure from document content and group document content into different streams according to the tags. Spatial coordinate data are compressed by delta encoding. Finally, the extracted pattern, all streams and encodings are forwarded to a text compressor gzip. Extensive experiments on real GML documents show that the proposed approach outperforms the existing XML and GML compression approaches in compression ratio, while keeping an acceptable compression efficiency.

Accurate identification of cis-regulatory elements and their correlated modules is essential for analysis of transcriptional regulation, which is a challenging problem in computational biology. Unsupervised learning has the advantage of compensating for missing annotated data, and is thus promising to be effective to identify cis-regulatory elements and modules. We introduced a Conditional Random Fields model, referred to as CRFEM, to integrate sequence features and long-range dependency of genomic sequences such as epigenetic features to identify cis-regulatory elements and modules at the same time. The proposed method is able to automatically learn model parameters with no labeled data and explicitly optimize the predictive probability of cis-regulatory elements and modules. In comparison with existing methods, our method is more accurate and can be used for genome-wide studies of gene regulation.

The rapid development of high-throughput technologies enables researchers to sequence the whole metagenome of a microbial community sampled directly from the environment. The assignment of these sequence reads into different species or taxonomical classes is a crucial step for metagenomic analysis, which is referred to as binning of metagenomic data. Most traditional binning methods rely on known reference genomes for accurate assignment of the sequence reads, therefore cannot classify reads from unknown species without the help of close references. To overcome this drawback, unsupervised learning based approaches have been proposed, which need not any known species' reference genome for help. In this paper, we introduce a novel unsupervised method called MCluster for binning metagenomic sequences. This method uses N-grams to extract sequence features and utilizes automatic feature weighting to improve the performance of the basic K-means clustering algorithm. We evaluate MCluster on a variety of simulated data sets and a real data set, and compare it with three latest binning methods: AbundanceBin, MetaCluster 3.0, and MetaCluster 5.0. Experimental results show that MCluster achieves obviously better overall performance (F-measure) than AbundanceBin and MetaCluster 3.0 on long metagenomic reads (≥800 bp); while compared with MetaCluster 5.0, MCluster obtains a larger sensitivity, and a comparable yet more stable F-measure on short metagenomic reads (<300 bp). This suggests that MCluster can serve as a promising tool for effectively binning metagenomic sequences.

The eight papers in this special section were presented at the Twelfth Asia Pacific Bioinformatics Conference (APBC2014), which was held in Shanghai, China, 17-19 January, 2014. The papers cover diverse topics, including protein complex prediction, nucleosome positioning, biological data classification and clustering, sequence comparison, genome reconstruction, and enhancers etc.

With the help of the histogram of triangle area representation (TAR) and feature matching strategy, a new effective image registration approach for remote sensing is proposed in this paper. This approach is based on a robust transformation parameter estimation algorithm called the histogram of TAR sample consensus (HTSC in short). The HTSC algorithm can replace the existing random sample consensus (RANSAC) and progressive sample consensus (PROSAC) methods that have been widely used in the transformation parameter estimation step of remote-sensing image registration, for it can efficiently calculate the consensus set with a higher accuracy. This paper lays down a new way to build a robust transformation parameter estimator based on the invariance constraint for remote-sensing image registration. Analogous to the two types of well-known existing transformation parameter estimation methods RANSAC and PROSAC, HTSC can serve as a new type (or the third type if we treat RANSAC and PROSAC as the first and the second types) of such methods, as it adopts the transformation-invariance information to find the consensus.

Existing differential privacy (DP) studies mainly consider aggregation on data sets where each entry corresponds to a particular participant to be protected. In many situations, a user may pose a relational algebra query on a database with sensitive data, and desire differentially private aggregation on the result of the query. However, no existing work is able to release such aggregation when the query contains unrestricted join operations. This severely limits the applications of existing DP techniques because many data analysis tasks require unrestricted joins. One example is subgraph counting on a graph. Furthermore, existing methods for differentially private subgraph counting support only edge DP and are subject to very simple subgraphs. Until recent, whether any nontrivial graph statistics can be released with reasonable accuracy for arbitrary kind of input graphs under node DP was still an open problem.

In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI [4]. Our recent attempts at implementing this vision [4,6], show significant improvement in the system response time (SRT) for subgraph queries. However, these efforts are designed specifically for graph databases containing a large collection of small or medium-sized graphs. Consequently, its frequent fragment-based action-aware indexing schemes and query processing strategy are unsuitable for supporting subgraph queries on large networks containing thousands of nodes and edges. In this demonstration, we present a novel system called QUBLE (QUery Blender for Large nEtworks) to realize this novel paradigm on large networks. We demonstrate various innovative features of QUBLE and its promising performance.

Given two locations s and t in a road network, a distance query returns the minimum network distance from s to t, while a shortest path query computes the actual route that achieves the minimum distance. These two types of queries find important applications in practice, and a plethora of solutions have been proposed in past few decades. The existing solutions, however, are optimized for either practical or asymptotic performance, but not both. In particular, the techniques with enhanced practical efficiency are mostly heuristic-based, and they offer unattractive worst-case guarantees in terms of space and time. On the other hand, the methods that are worst-case efficient often entail prohibitive preprocessing or space overheads, which render them inapplicable for the large road networks (with millions of nodes) commonly used in modern map applications.

This paper presents new results in external memory for finding the skyline (a.k.a. maxima) of N points in d-dimensional space. The state of the art uses for fixed d ≥ 3, and O((N/B)logM/B(N/B)) I/Os for d = 2, where M and B are the sizes (in words) of memory and a disk block, respectively. We give algorithms whose running time depends on the number K of points in the skyline. Specifically, we achieve expected cost for fixed d ≥ 3, and O((N/B)logM/B(K/B)) worst-case cost for d = 2. As a side product, we solve two problems both of independent interest. The first one, the M-skyline problem, aims at reporting M arbitrary skyline points, or the entire skyline if its size is at most M. We settle this problem in O(N/B) expected time in any fixed dimensionality d. The second one, the M-pivot problem, is more fundamental: given a set S of N elements drawn from an ordered domain, it outputs M evenly scattered elements (called pivots) from S, namely, S has asymptotically the same number of elements between each pair of consecutive pivots. We give a deterministic algorithm for solving the problem in O(N/B) I/Os.

BACKGROUND: Protein function prediction is an important problem in the post-genomic era. Recent advances in experimental biology have enabled the production of vast amounts of protein-protein interaction (PPI) data. Thus, using PPI data to functionally annotate proteins has been extensively studied. However, most existing network-based approaches do not work well when annotation and interaction information is inadequate in the networks. RESULTS: In this paper, we proposed a new method that combines PPI information and protein sequence information to boost the prediction performance based on collective classification. Our method divides function prediction into two phases: First, the original PPI network is enriched by adding a number of edges that are inferred from protein sequence information. We call the added edges implicit edges, and the existing ones explicit edges correspondingly. Second, a collective classification algorithm is employed on the new network to predict protein function. CONCLUSIONS: We conducted extensive experiments on two real, publicly available PPI datasets. Compared to four existing protein function prediction approaches, our method performs better in many situations, which shows that adding implicit edges can indeed improve the prediction performance. Furthermore, the experimental results also indicate that our method is significantly better than the compared approaches in sparsely-labeled networks, and it is robust to the change of the proportion of annotated proteins.

MicroRNAs (miRNAs) have been emerged as a novel class of endogenous post-transcriptional regulators in a variety of animal and plant species. One challenge facing miRNA research is to accurately identify the target mRNAs, because of the very limited sequence complementarity between miRNAs and their target sites, and the scarcity of experimentally validated targets to guide accurate prediction. In this paper, we propose a new method called SuperMirTar that exploits supervised distance learning to predict miRNA targets. Specifically, we use the experimentally supported miRNA-mRNA pairs as training set to learn a distance metric function that minimizes the distances between miRNAs and mRNAs with validated interactions, then use the learned function to calculate the distances of test miRNAmRNA interactions, and those with smaller distances than a predefined threshold are regarded as true interactions. We carry out performance comparison between the proposed approach and seven existing methods on independent datasets, the results show that our method achieves superior performance and can effectively narrow the gap between the number of predicted miRNA targets and the number of experimentally validated ones.

This paper presents a comprehensive comparison study on the performances of major existing models over two PPI datasets, by comparing the global and local statistical properties of the original PPI networks and the model-reproduced ones. Our experimental results show that the DD model has best fitting ability while iSite model and STICKY model also fit well with the PPI datasets over most statistical properties.

Differential privacy is a robust principle for privacy preserving data analysis tasks, and has been successfully applied to a variety of applications. However, the number of queries that can be answered is limited for preventing privacy disclosure. Once the privacy budget is exhausted, all succeeding queries must be rejected. Therefore, each of the historical query answers is valuable and it is important to exploit them together to learn more about the data. We propose to integrate all available linear query answers into a consistent form that embodies our knowledge learned from the noisy answers, obtaining more accurate answers to past queries and even new queries, improving the data utility. Two distinct approaches are developed for this purpose, one via principle component analysis, and another via maximum entropy method. The second approach also generates a synthetic database, which is useful for differentially private data publishing. One important goal of our work is to ensure that the running time of our approaches does not grow with the cardinality of the universe of a data tuple, so that high-dimensional data with very large domain can still be tackled efficiently.

In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI to filter irrelevant matches and prefetch partial query results [8]. Our first attempt at implementing this vision, called GBLENDER [8], shows significant improvement in system response time (SRT) for sub graph containment queries. However, GBLENDER suffers from two key drawbacks, namely inability to handle visual sub graph similarity queries and inefficient support for visual query modification, limiting its usage in practical environment. In this paper, we propose a novel algorithm called PRAGUE (Practical visu Al Graph QUery Blender), that addresses these limitations by exploiting a novel data structure called spindle-shaped graphs (SPIG). A SPIG succinctly records various information related to the set of super graphs of a newly added edge in the visual query fragment. Specifically, PRAGUE realizes a unified visual framework to support SPIG-based processing of modification-efficient sub graph containment and similarity queries. Extensive experiments on real-world and synthetic datasets demonstrate effectiveness of PRAGUE.

BACKGROUND: Promoter prediction is an integrant step for understanding gene regulation and annotating genomes. Traditional promoter analysis is mainly based on sequence compositional features. Recently, many kinds of structural features have been employed in promoter prediction. However, considering the high-dimensionality and overfitting problems, it is unfeasible to utilize all available features for promoter prediction. Thus it is necessary to choose some appropriate features for the prediction task. RESULTS: This paper conducts an extensive comparison study on feature selection of DNA structural properties for promoter prediction. Firstly, to examine whether promoters possess some special structures, we carry out a systematical comparison among the profiles of thirteen structural features on promoter and non-promoter sequences. Secondly, we investigate the correlations between these structural features and promoter sequences. Thirdly, both filter and wrapper methods are utilized to select appropriate feature subsets from thirteen different kinds of structural features for promoter prediction, and the predictive power of the selected feature subsets is evaluated. Finally, we compare the prediction performance of the feature subsets selected in this paper with nine existing promoter prediction approaches. CONCLUSIONS: Experimental results show that the structural features are differentially correlated to promoters. Specifically, DNA-bending stiffness, DNA denaturation and energy-related features are highly correlated with promoters. The predictive power for promoter sequences differentiates greatly among different structural features. Selecting the relevant features can significantly improve the accuracy of promoter prediction.

BACKGROUND: Nucleosome distribution along chromatin dictates genomic DNA accessibility and thus profoundly influences gene expression. However, the underlying mechanism of nucleosome formation remains elusive. Here, taking a structural perspective, we systematically explored nucleosome formation potential of genomic sequences and the effect on chromatin organization and gene expression in S. cerevisiae. RESULTS: We analyzed twelve structural features related to flexibility, curvature and energy of DNA sequences. The results showed that some structural features such as DNA denaturation, DNA-bending stiffness, Stacking energy, Z-DNA, Propeller twist and free energy, were highly correlated with in vitro and in vivo nucleosome occupancy. Specifically, they can be classified into two classes, one positively and the other negatively correlated with nucleosome occupancy. These two kinds of structural features facilitated nucleosome binding in centromere regions and repressed nucleosome formation in the promoter regions of protein-coding genes to mediate transcriptional regulation. Based on these analyses, we integrated all twelve structural features in a model to predict more accurately nucleosome occupancy in vivo than the existing methods that mainly depend on sequence compositional features. Furthermore, we developed a novel approach, named DLaNe, that located nucleosomes by detecting peaks of structural profiles, and built a meta predictor to integrate information from different structural features. As a comparison, we also constructed a hidden Markov model (HMM) to locate nucleosomes based on the profiles of these structural features. The result showed that the meta DLaNe and HMM-based method performed better than the existing methods, demonstrating the power of these structural features in predicting nucleosome positions. CONCLUSIONS: Our analysis revealed that DNA structures significantly contribute to nucleosome organization and influence chromatin structure and gene expression regulation. The results indicated that our proposed methods are effective in predicting nucleosome occupancy and positions and that these structural features are highly predictive of nucleosome organization.The implementation of our DLaNe method based on structural features is available online.

Query (e.g., shortest path) on road networks has been extensively studied. Although most of the existing query processing approaches are designed for centralized environments, there is a growing need to handle queries on road networks in distributed environments due to the increasing query workload and the challenge of querying large networks. In this demonstration, we showcase a distributed system calledDISKs(DIstributedSpatialKeywordsearch) that is capable of efficiently supporting spatial group keyword search (S-GKS) on road networks. Given a group of keywordsXand a distancer, an SGKS returns locations on a road network, such that for each returned locationp, there exists a set of nodes (on the road network), which are located within a network distancerfrompand collectively containsX. We will demonstrate the innovative modules, performance and interactive user interfaces of DISKs.

Computing the shortest path between two given locations in a road network is an important problem that finds applications in various map services and commercial navigation products. The state-of-the-art solutions for the problem can be divided into two categories: spatial-coherence-based methods and vertex-importance-based approaches. The two categories of techniques, however, have not been compared systematically under the same experimental framework, as they were developed from two independent lines of research that do not refer to each other. This renders it difficult for a practitioner to decide which technique should be adopted for a specific application. Furthermore, the experimental evaluation of the existing techniques, as presented in previous work, falls short in several aspects. Some methods were tested only on small road networks with up to one hundred thousand vertices; some approaches were evaluated using distance queries (instead of shortest path queries), namely, queries that ask only for the length of the shortest path; a state-of-the-art technique was examined based on a faulty implementation that led to incorrect query results. To address the above issues, this paper presents a comprehensive comparison of the most advanced spatial-coherence-based and vertex-importance-based approaches. Using a variety of real road networks with up to twenty million vertices, we evaluated each technique in terms of its preprocessing time, space consumption, and query efficiency (for both shortest path and distance queries). Our experimental results reveal the characteristics of different techniques, based on which we provide guidelines on selecting appropriate methods for various scenarios.

MiRNA are about 22nt long small noncoding RNAs that post transcriptionally regulate gene expression in animals, plants and protozoa. Confident identification of MiRNA-Target Interactions (MTI) is vital to understand their function. Currently, several integrated programs and databases are available for animal miRNAs, the mechanisms of which are significantly different from plant miRNAs. Here we present imiRTP, an integrated MTI prediction and analysis toolkit for Arabidopsis thaliana. It features two important functions: (i) combination of several effective plant miRNA target prediction methods provides a sufficiently large MTI candidate set, and (ii) different filters allow for an efficient selection of potential targets. The modularity of imiRTP enables the prediction of high quality targets on genome-wide scale.

Due to the complexity of graph query languages, the need for visual query interfaces that can reduce the burden of query formulation is fundamental to the spreading of graph data management tools to wider community. We present a novel HCI (human-computer interaction)-aware graph query processing paradigm, where instead of processing a query graph after its construction, it interleaves visual query construction and processing to improve system response time. We demonstrate a system called GBLENDER that exploits GUI latency to prune false results and prefetch candidate data graphs by employing a novel action-aware indexing scheme and a data structure called spindle-shaped graphs (SPIG). We demonstrate various innovative features of GBLENDER and its promising performance in evaluating subgraph containment and similarity queries.

BACKGROUND: MicroRNAs (miRNAs) are ~22 nt long integral elements responsible for post-transcriptional control of gene expressions. After the identification of thousands of miRNAs, the challenge is now to explore their specific biological functions. To this end, it will be greatly helpful to construct a reasonable organization of these miRNAs according to their homologous relationships. Given an established miRNA family system (e.g. the miRBase family organization), this paper addresses the problem of automatically and accurately classifying newly found miRNAs to their corresponding families by supervised learning techniques. Concretely, we propose an effective method, miRFam, which uses only primary information of pre-miRNAs or mature miRNAs and a multiclass SVM, to automatically classify miRNA genes. RESULTS: An existing miRNA family system prepared by miRBase was downloaded online. We first employed n-grams to extract features from known precursor sequences, and then trained a multiclass SVM classifier to classify new miRNAs (i.e. their families are unknown). Comparing with miRBase's sequence alignment and manual modification, our study shows that the application of machine learning techniques to miRNA family classification is a general and more effective approach. When the testing dataset contains more than 300 families (each of which holds no less than 5 members), the classification accuracy is around 98%. Even with the entire miRBase15 (1056 families and more than 650 of them hold less than 5 samples), the accuracy surprisingly reaches 90%. CONCLUSIONS: Based on experimental results, we argue that miRFam is suitable for application as an automated method of family classification, and it is an important supplementary tool to the existing alignment-based small non-coding RNA (sncRNA) classification methods, since it only requires primary sequence information. AVAILABILITY: The source code of miRFam, written in C++, is freely and publicly available at: http://admis.fudan.edu.cn/projects/miRFam.htm.

BACKGROUND: Prediction of protein subcellular localization generally involves many complex factors, and using only one or two aspects of data information may not tell the true story. For this reason, some recent predictive models are deliberately designed to integrate multiple heterogeneous data sources for exploiting multi-aspect protein feature information. Gene ontology, hereinafter referred to as GO, uses a controlled vocabulary to depict biological molecules or gene products in terms of biological process, molecular function and cellular component. With the rapid expansion of annotated protein sequences, gene ontology has become a general protein feature that can be used to construct predictive models in computational biology. Existing models generally either concatenated the GO terms into a flat binary vector or applied majority-vote based ensemble learning for protein subcellular localization, both of which can not estimate the individual discriminative abilities of the three aspects of gene ontology. RESULTS: In this paper, we propose a Gene Ontology Based Transfer Learning Model (GO-TLM) for large-scale protein subcellular localization. The model transfers the signature-based homologous GO terms to the target proteins, and further constructs a reliable learning system to reduce the adverse affect of the potential false GO terms that are resulted from evolutionary divergence. We derive three GO kernels from the three aspects of gene ontology to measure the GO similarity of two proteins, and derive two other spectrum kernels to measure the similarity of two protein sequences. We use simple non-parametric cross validation to explicitly weigh the discriminative abilities of the five kernels, such that the time & space computational complexities are greatly reduced when compared to the complicated semi-definite programming and semi-indefinite linear programming. The five kernels are then linearly merged into one single kernel for protein subcellular localization. We evaluate GO-TLM performance against three baseline models: MultiLoc, MultiLoc-GO and Euk-mPLoc on the benchmark datasets the baseline models adopted. 5-fold cross validation experiments show that GO-TLM achieves substantial accuracy improvement against the baseline models: 80.38% against model Euk-mPLoc 67.40% with 12.98% substantial increase; 96.65% and 96.27% against model MultiLoc-GO 89.60% and 89.60%, with 7.05% and 6.67% accuracy increase on dataset MultiLoc plant and dataset MultiLoc animal, respectively; 97.14%, 95.90% and 96.85% against model MultiLoc-GO 83.70%, 90.10% and 85.70%, with accuracy increase 13.44%, 5.8% and 11.15% on dataset BaCelLoc plant, dataset BaCelLoc fungi and dataset BaCelLoc animal respectively. For BaCelLoc independent sets, GO-TLM achieves 81.25%, 80.45% and 79.46% on dataset BaCelLoc plant holdout, dataset BaCelLoc plant holdout and dataset BaCelLoc animal holdout, respectively, as compared against baseline model MultiLoc-GO 76%, 60.00% and 73.00%, with accuracy increase 5.25%, 20.45% and 6.46%, respectively. CONCLUSIONS: Since direct homology-based GO term transfer may be prone to introducing noise and outliers to the target protein, we design an explicitly weighted kernel learning system (called Gene Ontology Based Transfer Learning Model, GO-TLM) to transfer to the target protein the known knowledge about related homologous proteins, which can reduce the risk of outliers and share knowledge between homologous proteins, and thus achieve better predictive performance for protein subcellular localization. Cross validation and independent test experimental results show that the homology-based GO term transfer and explicitly weighing the GO kernels substantially improve the prediction performance.

The prediction of 3D structures of proteins from amino acid sequences is one of the most challenging problems in molecular biology. An essential task for solving this problem with coarse-grained models is to deduce effective interaction potentials. The development and evaluation of new energy functions is critical to accurately modeling the properties of biological macromolecules. Knowledge-based mean force potentials are derived from statistical analysis of proteins of known structures. Current knowledge-based potentials are almost in the form of weighted linear sum of interaction pairs. In this study, a class of novel nonlinear knowledge-based mean force potentials is presented. The potential parameters are obtained by nonlinear classifiers, instead of relative frequencies of interaction pairs against a reference state or linear classifiers. The support vector machine is used to derive the potential parameters on data sets that contain both native structures and decoy structures. Five knowledge-based mean force Boltzmann-based or linear potentials are introduced and their corresponding nonlinear potentials are implemented. They are the DIH potential (single-body residue-level Boltzmann-based potential), the DFIRE-SCM potential (two-body residue-level Boltzmann-based potential), the FS potential (two-body atom-level Boltzmann-based potential), the HR potential (two-body residue-level linear potential), and the T32S3 potential (two-body atom-level linear potential). Experiments are performed on well-established decoy sets, including the LKF data set, the CASP7 data set, and the Decoys “R”Us data set. The evaluation metrics include the energy Z score and the ability of each potential to discriminate native structures from a set of decoy structures. Experimental results show that all nonlinear potentials significantly outperform the corresponding Boltzmann-based or linear potentials, and the proposed discriminative framework is effective in developing knowledge-based mean force potentials. The nonlinear potentials can be widely used for ab initio protein structure prediction, model quality assessment, protein docking, and other challenging problems in computational biology.

In this paper, we study the problem of indexing multidimensional data in P2P networks based on distributed hash tables (DHTs). We advocate the indexing approach that superimposes a multidimensional index tree on top of a DHT - a paradigm that keeps the underlying DHT intact while being able to adapt to any DHT substrate. In this context, we identify several index design issues and propose a novel indexing scheme called multidimensional Lightweight Hash Tree (m-LIGHT). First, to preserve data locality, m-LIGHT employs a clever naming mechanism that gracefully maps a tree-based index into the DHT and contributes to high efficiency in both index maintenance and query processing. Second, to tackle the load balancing issue, m-LIGHT leverages a new data-aware splitting strategy that achieves optimal load balance under a fixed index size. We present detailed algorithms for processing complex queries over the m-LIGHT index. We also conduct an extensive performance evaluation of m-LIGHT in comparison with several state-of-the-art indexing schemes. The experimental results show that m-LIGHT substantially reduces index maintenance overhead and improves query performance in terms of both bandwidth consumption and response latency.

BACKGROUND: MicroRNAs (simply miRNAs) are derived from larger hairpin RNA precursors and play essential regular roles in both animals and plants. A number of computational methods for miRNA genes finding have been proposed in the past decade, yet the problem is far from being tackled, especially when considering the imbalance issue of known miRNAs and unidentified miRNAs, and the pre-miRNAs with multi-loops or higher minimum free energy (MFE). This paper presents a new computational approach, miRenSVM, for finding miRNA genes. Aiming at better prediction performance, an ensemble support vector machine (SVM) classifier is established to deal with the imbalance issue, and multi-loop features are included for identifying those pre-miRNAs with multi-loops. RESULTS: We collected a representative dataset, which contains 697 real miRNA precursors identified by experimental procedure and other computational methods, and 5428 pseudo ones from several datasets. Experiments showed that our miRenSVM achieved a 96.5% specificity and a 93.05% sensitivity on the dataset. Compared with the state-of-the-art approaches, miRenSVM obtained better prediction results. We also applied our method to predict 14 Homo sapiens pre-miRNAs and 13 Anopheles gambiae pre-miRNAs that first appeared in miRBase13.0, MiRenSVM got a 100% prediction rate. Furthermore, performance evaluation was conducted over 27 additional species in miRBase13.0, and 92.84% (4863/5238) animal pre-miRNAs were correctly identified by miRenSVM. CONCLUSION: MiRenSVM is an ensemble support vector machine (SVM) classification system for better detecting miRNA genes, especially those with multi-loop secondary structure.

DHT is a widely used building block for scalable P2P systems. However, as uniform hashing employed in DHTs destroys data locality, it is not a trivial task to support complex queries (e.g., range queries and k-nearest-neighbor queries) in DHT-based P2P systems. In order to support efficient processing of such complex queries, a popular solution is to build indexes on top of the DHT. Unfortunately, existing over-DHT indexing schemes suffer from either query inefficiency or high maintenance cost. In this paper, we propose LIGhtweight Hash Tree (LIGHT)—a query-efficient yet low-maintenance indexing scheme. LIGHT employs a novel naming mechanism and a tree summarization strategy for graceful distribution of its index structure. We show through analysis that it can support various complex queries with near-optimal performance. Extensive experimental results also demonstrate that, compared with state of the art over-DHT indexing schemes, LIGHT saves 50-75 percent of index maintenance cost and substantially improves query performance in terms of both response time and bandwidth consumption. In addition, LIGHT is designed over generic DHTs and hence can be easily implemented and deployed in any DHT-based P2P system.

The development and evaluation of functions for protein energetics is an important part of current research aiming at understanding protein structures and functions. Knowledgebase mean force potentials are derived from statistical analysis of interacting groups in experimentally determined protein structures. Current knowledge-based mean force potentials are based on the inverse Boltzmannpsilas law, which calculate the ratio of the observed probability with respect to the probability of the reference state. In this study, a general probability framework is presented with the aim to develop novel energy scores. A class of empirical probability functions is derived by decomposing the joint probability of backbone dihedral angles and amino acid sequences. The neighboring interactions are modeled by conditional probabilities. Such probability functions are based on the strict probability theory and some suitable suppositions for convenience of computation. Experiments are performed on several well-constructed decoy sets and the results show that the empirical probability functions presented here outperform previous statistical potentials based on dihedral angles. Such probability functions will be helpful for protein structure prediction,model quality evaluation, transcription factors identification and other challenging problems in computational biology.

In this paper, we study the problem of indexing multidimensional data in the P2P networks based on distributed hash tables (DHTs). We identify several design issues and propose a novel over-DHT indexing scheme called m- LIGHT. To preserve data locality, m-LIGHT employs a clever naming mechanism that gracefully maps the index tree into the underlying DHT so that it achieves efficient index maintenance and query processing. Moreover, m- LIGHT leverages a new data-aware index splitting strategy to achieve optimal load balance among peer nodes. We conduct an extensive performance evaluation for m-LIGHT. Compared to the state-of-the-art indexing schemes, m-LIGHT substantially saves the index maintenance overhead, achieves a more balanced load distribution, and improves the range query performance in both bandwidth consumption and response latency.

Much work has focused on mining evolving data, and most approaches learn the latest model from the latest data. The problem with these approaches is that the learned model is always of low quality. In this paper, we propose a clustering approach to find hidden concepts that control data generation. Unlike traditional clustering methods that are based on data similarity (measured by Euclidean distance, e.g.), we devise a new similarity metric for concept similarity. We propose a two step algorithm, which uses dynamic programming and hierarchical clustering to find concepts in the data.

Recent research has shown that keyword search is a friendly and potentially effective way to retrieve information of interest over relational databases. Existing work has generally focused on implementing keyword search in centralized databases. This paper addresses keyword search over distributed databases. We adopts distributed hash tables (DHTs) - a peer-to-peer inspired overlay network technology - as the infrastructure to implement keyword search over relational databases. For this end, we combine IR-based ranking techniques with a P2P-based indexing strategy, and propose an effective approach. Extensive experiments over real-world datasets show that our approach is effective and efficient.

The multidimensional similarity query, an essential query for information processing in sensor networks, has not received sufficient attention in the research community of sensor networks. In this paper, we study the multidimensional similarity query for large-scale sensor networks and propose a new algorithm called DIC (dimension reduction by Chebyshev polynomials). In DIC algorithm, the normalized Chebyshv coefficients are adopted as indexing and theoretic storage location of multidimensional data, and the multidimensional data are stored in the sensor nodes close to the theoretic location. A query bounding is estimated by using DIC algorithm, and query is executed inside a small zone. Inside the small zone, a new method of the itinerary-based query propagation and data aggregation is presented. The DIC algorithm does not require to preserve any index structure in sensor nodes, and also do not reply on any infrastructure structures distributed among the sensor nodes. We provide extensive experiments to evaluate the performance of the algorithm. The experimental results demonstrate that DIC can indeed enable efficient similarity queries.

MOTIVATION: Fold recognition is an important step in protein structure and function prediction. Traditional sequence comparison methods fail to identify reliable homologies with low sequence identity, while the taxonomic methods are effective alternatives, but their prediction accuracies are around 70%, which are still relatively low for practical usage. RESULTS: In this study, a simple and powerful method is presented for taxonomic fold recognition, which combines support vector machine (SVM) with autocross-covariance (ACC) transformation. The evolutionary information represented in the form of position-specific score matrices is converted into a series of fixed-length vectors by ACC transformation and these vectors are then input to a SVM classifier for fold recognition. The sequence-order effect can be effectively captured by this scheme. Experiments are performed on the widely used D-B dataset and the corresponding extended dataset, respectively. The proposed method, called ACCFold, gets an overall accuracy of 70.1% on the D-B dataset, which is higher than major existing taxonomic methods by 2-14%. Furthermore, the method achieves an overall accuracy of 87.6% on the extended dataset, which surpasses major existing taxonomic methods by 9-17%. Additionally, our method obtains an overall accuracy of 80.9% for 86-folds and 77.2% for 199-folds. These results demonstrate that the ACCFold method provides the state-of-the-art performance for taxonomic fold recognition. AVAILABILITY: The source code for ACC transformation is freely available at http://www.iipl.fudan.edu.cn/demo/accpkg.html.

MOTIVATION: Identification of core promoters is a key clue in understanding gene regulations. However, due to the diverse nature of promoter sequences, the accuracy of existing prediction approaches for non-CpG island (simply CGI)-related promoters is not as high as that for CGI-related promoters. This consequently leads to a low genome-wide promoter prediction accuracy. RESULTS: In this article, we first systematically analyze the similarities and differences between the two types of promoters (CGI- and non-CGI-related) from a novel structural perspective, and then devise a unified framework, called PNNP (Pattern-based Nearest Neighbor search for Promoter), to predict both CGI- and non-CGI-related promoters based on their structural features. Our comparative analysis on the structural characteristics of promoters reveals two interesting facts: (i) the structural values of CGI- and non-CGI-related promoters are quite different, but they exhibit nearly similar structural patterns; (ii) the structural patterns of promoters are obviously different from that of non-promoter sequences though the sequences have almost similar structural values. Extensive experiments demonstrate that the proposed PNNP approach is effective in capturing the structural patterns of promoters, and can significantly improve genome-wide performance of promoters prediction, especially non-CGI-related promoters prediction. AVAILABILITY: The implementation of the program PNNP is available at http://admis.tongji.edu.cn/Projects/pnnp.aspx.

BACKGROUND: Prediction of protein-protein interaction sites is one of the most challenging and intriguing problems in the field of computational biology. Although much progress has been achieved by using various machine learning methods and a variety of available features, the problem is still far from being solved. RESULTS: In this paper, an ensemble method is proposed, which combines bootstrap resampling technique, SVM-based fusion classifiers and weighted voting strategy, to overcome the imbalanced problem and effectively utilize a wide variety of features. We evaluate the ensemble classifier using a dataset extracted from 99 polypeptide chains with 10-fold cross validation, and get a AUC score of 0.86, with a sensitivity of 0.76 and a specificity of 0.78, which are better than that of the existing methods. To improve the usefulness of the proposed method, two special ensemble classifiers are designed to handle the cases of missing homologues and structural information respectively, and the performance is still encouraging. The robustness of the ensemble method is also evaluated by effectively classifying interaction sites from surface residues as well as from all residues in proteins. Moreover, we demonstrate the applicability of the proposed method to identify interaction sites from the non-structural proteins (NS) of the influenza A virus, which may be utilized as potential drug target sites. CONCLUSION: Our experimental results show that the ensemble classifiers are quite effective in predicting protein interaction sites. The Sub-EnClassifiers with resampling technique can alleviate the imbalanced problem and the combination of Sub-EnClassifiers with a wide variety of feature groups can significantly improve prediction performance.

Generalization is a well-known method for privacy preserving data publication. Despite its vast popularity, it has several drawbacks such as heavy information loss, difficulty of supporting marginal publication, and so on. To overcome these drawbacks, we develop ANGEL,1 a new anonymization technique that is as effective as generalization in privacy protection, but is able to retain significantly more information in the microdata. ANGEL is applicable to any monotonic principles (e.g., l-diversity, t-closeness, etc.), with its superiority (in correlation preservation) especially obvious when tight privacy control must be enforced. We show that ANGEL lends itself elegantly to the hard problem of marginal publication. In particular, unlike generalization that can release only restricted marginals, our technique can be easily used to publish any marginals with strong privacy guarantees.

We consider skyline computation when the underlying data set is horizontally partitioned onto geographically distant servers that are connected to the Internet. The existing solutions are not suitable for our problem, because they have at least one of the following drawbacks: (1) applicable only to distributed systems adopting vertical partitioning or restricted horizontal partitioning, (2) effective only when each server has limited computing and communication abilities, and (3) optimized only for skyline search in subspaces but inefficient in the full space. This paper proposes an algorithm, called feedback-based distributed skyline (FDS), to support arbitrary horizontal partitioning. FDS aims at minimizing the network bandwidth, measured in the number of tuples transmitted over the network. The core of FDS is a novel feedback-driven mechanism, where the coordinator iteratively transmits certain feedback to each participant. Participants can leverage such information to prune a large amount of local data, which otherwise would need to be sent to the coordinator. Extensive experimentation confirms that FDS significantly outperforms alternative approaches in both effectiveness and progressiveness.

DHT is a widely-used building block in P2P systems, and complex queries are gaining popularity in P2P applications. To support efficient query processing over DHTs, effective indexing structures are essential. Recently, a number of indexing schemes have been proposed. However, these schemes have focused on improving query efficiency, and as a trade-off, sacrificed maintenance efficiency - an important performance measure in the P2P context, where frequent data updating and high peer dynamism are typically incurred. In this paper, we propose LHT, a Low maintenance Hash Tree, for efficient data indexing over DHTs. LHT employs a novel naming function and a tree summarization strategy to gracefully distribute its index structure. It is adaptable to any DHT substrates, and is easy to be implemented and deployed. Experiments show that in comparison with the state-of-the-art indexing technique, LHT saves up to 75% (at least 50%) maintenance cost, and achieves better performance for exact-match queries and range queries.

Many applications are driven by evolving data - patterns in Web traffic, program execution traces, network event logs, etc., are often non-stationary. Building prediction models for evolving data becomes an important and challenging task. Currently, most approaches work by "chasing trends", that is, they keep learning or updating models from the evolving data, and use these impromptu models for online prediction. In many cases, this proves to be both costly and ineffective - much time is wasted on re-learning recurring concepts, yet the classifier may remain one step behind the current trend all the time. In this paper, we propose to mine high-order models in evolving data. More often than not, there are a limited number of concepts, or stable distributions, in the data stream, and concepts switch between each other constantly. We mine all such concepts offline from a historical stream, and build high quality models for each of them. At run time, combining historical concept change patterns and cues provided by an online training stream, we find the most likely current concept and use its corresponding models to classify data in an unlabeled stream. The primary advantage of the high-order model approach is its high accuracy. Experiments show that in benchmark datasets, classification error of the high-order model is only a small fraction of that of the current best approaches. Another important benefit is that, unlike state-of-the-art approaches, our approach does not require users to tune any parameters to achieve a satisfying result on streams of different characteristics.

The localization of sensor nodes is a fundamental problem in sensor networks and can be implemented using powerful and expensive beacons. Beacons, the fewer the better, can acquire their position knowledge either from GPS devices or by virtue of being manually placed. In this paper, we propose a distributed method to localization of sensor nodes using a single moving beacon, where sensor nodes compute their position estimate based on the range-free technique. Two parameters are critical to the location accuracy of sensor nodes: the radio transmission range of the beacon and how often the beacon broadcasts its position. Theoretical analysis shows that these two parameters determine the upper bound of the estimation error when the traverse route of the beacon is a straight line. We extend the position estimate when the traverse route of the beacon is randomly chosen in a real-world situation, where the radio irregularity might cause a node to miss some crucial coordinate information from the beacon. We further point out that the movement pattern of the beacon plays a pivotal role in the localization task for sensors. To minimize estimation errors, sensor nodes can carry out a variety of algorithms in accordance with the movement of the beacon. Simulation results compare variants of the distributed method in a variety of testing environments. Real experiments show that the proposed method is feasible and can estimate the location of sensor nodes accurately, given a single moving beacon.

As Geography Markup Language (GML) becomes a standard for geographic information representation on the internet, more needs to efficiently store and retrieve GML data arise. Storing and retrieving GML data in object-relational database is a proper option considering its sophisticated technology and object-oriented features. The existing storage approaches for GML are not satisfactory for they consider only data aspects while ignoring semantic constraints. In the paper, we explore the structure and semantic characteristics existed in GML, and present a method to capture and map these constraints into object-relational databases during GML storage. Comparing with the existing methods, our approach preserves not only the data and structure, but also its semantics of GML document.

The localization of the sensor node is a fundamental problem in sensor networks and can be implemented using powerful and expensive beacons. Beacons, the fewer the better, can acquire their position knowledge either from a GPS device or by virtue of being manually placed. In this paper, we propose two distributed methods to localization of sensor nodes using a single moving beacon where sensor nodes compute their position estimate based on the range-free technique. The first method uses the arrival and departure information of a walking beacon and the second method exploits the variance of the received signal strength (RSS) from the beacon. We provide the upper bound of the estimation error for these methods in an ideal environment. Critical to the location accuracy of sensor nodes are two more parameters, the radio transmission range of the beacon, and how often the beacon broadcasts its position. Simulation results show the location estimate error of sensor nodes applying the proposed two methods. The results are consistent to the theoretical analysis and the average estimate errors could be within one meter.

This demonstration presents a GML specific compressor that exploits the unique characteristics of GML documents to achieve better compression performance than the existing XML compressors. We call this compressor GPress, an abbreviation of "GML comPressor". To the best of our knowledge, GPress is the first compressor developed specifically for GML documents. Experimental results show that GPress outperforms the best existing XML compressor XMill evidently in compression ratio.

Graphs are widely used for modeling complicated data, including chemical compounds, protein interactions, XML documents, and multimedia. Information retrieval against such data can be formulated as a graph search problem, and finding an efficient solution to the problem is essential for many applications. A popular approach is to represent both graphs and queries on graphs by sequences, thus converting graph search to subsequence matching. State-of-the-art sequencing methods work at the finest granularity - each node (or edge) in the graph will appear as an element in the resulting sequence. Clearly, such methods are not semantic conscious, and the resulting sequences are not only bulky but also prone to complexities arising from graph isomorphism and other problems in searching. In this paper, we introduce a novel sequencing method to capture the semantics of the underlying graph data. We find meaningful components in graph structures and use them as the most basic units in sequencing. It not only reduces the size of resulting sequences, but also enables semantic-based searching. In this paper, we base our approach on chemical compound databases, although it can be applied to searching other complicated graphs, such as protein structures. Experiments demonstrate that our approach outperforms state-of-the-art graph search methods.

GML has become the de facto standard for electronic spatial data exchange among the applications of Web and distributed geographic information systems (GISs). As more and more geographical data is presented in GML, it is necessary to develop techniques for managing GML documents in databases. A possible solution is to store GML data into object-relational databases from which the users can retrieve the interested data. In this paper, we propose an approach to map GML schema to object-relational database schema by using GML schema graph, and algorithms for storing / querying valid GML documents into / from the relations generated by the corresponding object-relational schema. Spatial and non-spatial features embedded in GML document are stored in object-oriented relations, and the structures and constrains defined in GML schema are also well preserved. A prototype for GML documents storing and querying based on the proposed method is implemented on the basis of the Oracle/Spatial system. Preliminary experiment results shows that our method is feasible and efficient.

In this demonstration, we present a prototype system called SIPPER, which is the abbreviation for Selecting Informative Peers in Structured P2P Environment for Content-based Retrieval. SIPPER distinguishes itself from the existing P2P-IR systems by the following two features: First, to improve retrieval efficiency, SIPPER employs a novel peer selection method to direct the query to a small fraction of relevant peers in the network for searching globally relevant documents. Second, to reduce the bandwidth cost of meta data publishing, SIPPER uses a new publishing mechanism, the term-node publishing mechanism, which is different from the traditional term-document model [2].

Let R be a set of objects. An object o ∈ R is an outlier, if there exist less than k objects in R whose distances to o are at most r. The values of k, r, and the distance metric are provided by a user at the run time. The objective is to return all outliers with the smallest I/O cost.This paper considers a generic version of the problem, where no information is available for outlier computation, except for objects' mutual distances. We prove an upper bound for the memory consumption which permits the discovery of all outliers by scanning the dataset 3 times. The upper bound turns out to be extremely low in practice, e.g., less than 1% of R. Since the actual memory capacity of a realistic DBMS is typically larger, we develop a novel algorithm, which integrates our theoretical findings with carefully-designed heuristics that leverage the additional memory to improve I/O efficiency. Our technique reports all outliers by scanning the dataset at most twice (in some cases, even once), and significantly outperforms the existing solutions by a factor up to an order of magnitude.

No abstract available.

With the rapid growth of on-line information available, text classification is becoming more and more important. kNN is a widely used text classification method of high performance. However, this method is inefficient because it requires a large amount of computation for evaluating the similarity between a test document and each training document. In this paper, we propose a fast kNN text classification approach based on pruning the training corpus. By using this approach, the size of training corpus can be condensed sharply so that time-consuming on kNN searching can be cut off significantly, and consequently classification efficiency can be improved substantially while classification performance is preserved comparable to that of without pruning. Effective, algorithm for text corpus pruning is designed. Experiments over the Reuters corpus are carried out, which validate the practicability of the proposed approach. Our approach is especially suitable for on-line text classification applications.

Geography Markup Language (GML) has been adopted as de facto standard for geo-referenced information storing and exchanging, while Scalable Vector Graphics (SVG), also a W3C-recommended XML standard, is appearing as an ideal format for rendering maps. Usually, Extensible Stylesheet Language Transformations (XSLT) is used to transform GML documents toSVG documents. Considering the complexity and variety of GML documents, however, designing XSLT rules is not a easy task; even worse, such a method cannot guarantee that the generated SVG document is valid. In this paper, we present a novel method to transform GML documents to SVG documents, while guaranteeing that the result SVG documents conform to a certain DTD or Schema pre-specified by the users. With this new method, it is convenient for the users to construct transformation rules from GML to SVG guided by the pre-specified SVG DTD or schema. We propose three algorithms to implement the new method. We also build a prototype and conduct preliminary experiments, which validate the effectiveness of the new method.

This paper reports the techniques of dynamic tuning of XML storage schema in VXMLR, which is a XML management system based on RDBMS. With two different tuning strategies, VXMLR can dynamically adjust its storage schema based on the latest query records to improve its query processing efficiency. When a tuning event is triggered, VXMLR first derives from its history queries the initial mapping rules that map XML DTD to relational schemas; then by vertically partitioning the relational tables or redundantly storing the data relevant to history queries, some candidate storage schemas are generated; following that, the benefit and cost of each candidate schema is estimated; and finally a cost-driven approach is proposed to select the final storage schema from the candidate schemas under a certain space constraint. Experimental results validate the practicability and effectiveness of the proposed techniques.

This paper explores an adjacency matrix based approach for Chinese text retrieval. Using this approach, retrieval systems need only keep indexing data, rather than indexing data and original text data as traditional retrieval systems do, thus system space costs as a whole can be reduced drastically while retrieval efficiency is maintained as satisfactory. Experiments demonstrate the effectiveness and efficiency of this approach.