Web APIs have become a fundamental paradigm in the Web 4.0 era, with mashup services emerging as a transformative technology that combines multiple APIs to create comprehensive services. However, existing approaches exhibit two significant limitations: overlooking the quality and completeness of recommendation contexts of new mashup requirements, and failing to effectively extract high-quality collaborative features from multi-perspective service relationships. To address these limitations, we propose LMSR, a novelLLM-enhancedMulti-perspectiveService Feature Learning framework for Web APIRecommendation. LMSR first leverages general-purpose LLM to refine and encode the original requirement descriptions, and employs a Mixture of Service Experts (MoSE)-based context prediction model to precisely predict service information relevant to new requirements, establishing a comprehensive and high-quality recommendation context for mashup requirements. Furthermore, by integrating the predicted recommendation contexts into the LLM through fine-tuning, LMSR effectively extracts collaborative features from multi-perspective service relationships between mashup requirements and APIs, ultimately achieving precise Web API recommendation. Comprehensive experiments on real-world datasets demonstrate that LMSR significantly outperforms 11 baseline approaches across precision, recall, F1-score, and NDCG, validating its effectiveness in Web API recommendation. The codes are available athttps://scdm-shu.github.io/codes/LMSR.zip.

While Large Language Models (LLMs) show promise for Text-Attributed Graphs (TAGs) learning, their deployment is hindered by computational demands. Graph Neural Networks (GNNs) are efficient but struggle with TAGs' complex semantics. We propose LinguGKD, a novel LLM-to-GNN knowledge distillation framework that enables transferring both local semantic details and global structural information from LLMs to GNNs. First, it introduces TAG-oriented instruction tuning, enhancing LLMs with graph-specific knowledge through carefully designed prompts. Next, it develops a layer-adaptive multi-scale contrastive distillation strategy aligning LLM and GNN features at multiple granularities, from node-level to graph-level. Finally, the distilled GNNs combine the semantic richness of LLMs with the computational efficiency of traditional GNNs. Experiments demonstrate that LinguGKD outperforms existing graph distillation frameworks, the distilled simple GNNs achieve comparable or superior performance to more complex GNNs and teacher LLMs, while maintaining computational efficiency. This work bridges the gap between LLMs and GNNs, facilitating advanced graph learning in resource-constrained environments and providing a framework to leverage ongoing LLM advancements for GNN improvement.

Observation-based trajectory prediction for systems with unknown dynamics is essential in fields such as physics and biology. Most existing approaches are limited to learning within a single system with fixed dynamics patterns. However, many real-world applications require learning across systems with evolving dynamics patterns, a challenge that has been largely overlooked. To address this, we systematically investigate the problem of Continual Dynamics Learning (CDL), examining task configurations and evaluating the applicability of existing techniques, while identifying key challenges. In response, we propose the Mode-switching Graph ODE (MS-GODE) model, which integrates the strengths LG-ODE and sub-network learning with a mode-switching module, enabling efficient learning over varying dynamics. Moreover, we construct a novel benchmark of biological dynamic systems for CDL, Bio-CDL, featuring diverse systems with disparate dynamics and significantly enriching the research field of machine learning for dynamic systems. Our code available at \url{https://github.com/QueuQ/MS-GODE}.

Connected vehicles due to the high mobility and dynamic network topologies of connected vehicles require accurate QoS that includes high throughput and low latency to assess satisfactory QoE. Existing methods mainly focus on centralized QoS prediction while paying little attention to distributed mobile QoS prediction, making it challenging to protect user privacy information when invoking Web services. Moreover, even though some advanced centralized methods can be transformed into federated architectures, they often face difficulty in capturing latent feature representations of users and services and learning personalized prediction layers between them due to the heterogeneity of the QoS dataset. To address the above issues, we propose a novel framework for distributed QoS prediction, called Combining Personalized Federated Hypernetworks and Shared Residual Learning for Distributed QoS Prediction (FHR-DQP) . FHR-DQP adopts the federated averaging (FedAvg) to aggregate location-aware residual shared feature information across all clients. Additionally, a hypernetwork is leveraged to generate personalized networks for user-service QoS prediction in each client. These components are integrated as a hybrid framework that performs training using a federated approach and makes personalized QoS predictions within each client. Extensive experiments are conducted on a real-world benchmark QoS dataset called WS-DREAM, containing nearly 2,000,000 historical QoS invocation records. Compared with both centralized and federated competing baselines, the results demonstrate that FHR-DQP achieves the highest performance for distributed QoS prediction, when it provides privacy-preserving of users’ QoS invocations.

Continuous influence maximization (CIM) in social networks aims to maximize the expected influence spreading by assigning each user a continuous weight reflecting the likelihood and cost for him becoming a seed. Traditional CIM assumes a budget constrain to limit the total cost of all users. However, this assumption does not tenable in practical applications. In practice, it is not necessary to incur costs for all the users. Instead, the budget should be set only for the cost associated with the seed set. In this article, an extended CIM problem of cost distribution under budget (CDB) is defined, which aims to assign different costs to the customers according to their ability to spread influence, ensuring that the cost of each potential seed set does not exceed the budget, while the expected spreading of the product’s influence is maximized. The NP-hardness of CDB and the monotonicity and submodularity of its objective function are investigated. We formulate the CDB problem into a constrained optimization, and present a greedy descent-based algorithm for the problem. In each iteration of the greedy descent method, the influence increment of each node is calculated according to its estimated influence spreading range. The cost distribution is updated along the direction with the maximum increment. The optimal cost distribution can be obtained after several iterations. Precision of the results obtained by the proposed algorithm is analyzed. To avoid the time-consuming simulations, we design an effective algorithm for estimating the seed influence spreading range. Experiment results on real and synthetic networks show that the proposed algorithm can significantly improve the expected influence spreading.

Accurate prediction of temporal QoS is crucial for maintaining service reliability and enhancing user satisfaction in dynamic service-oriented environments. However, current methods often neglect high-order latent collaborative relationships and fail to dynamically adjust feature learning for specific user-service invocations, which are critical for precise feature extraction within each time slice. Moreover, the prevalent use of RNNs for modeling temporal feature evolution patterns is constrained by their inherent difficulty in managing long-range dependencies, thereby limiting the detection of long-term QoS trends across multiple time slices. These shortcomings dramatically degrade the performance of temporal QoS prediction. To address the two issues, we propose a novel Graph Attention Collaborative Learning (GACL) framework for temporal QoS prediction. Building on a dynamic user-service invocation graph to comprehensively model historical interactions, it designs a target-prompt graph attention network to extract deep latent features of users and services at each time slice, considering implicit target-neighboring collaborative relationships and historical QoS values. Additionally, a multi-layer Transformer encoder is introduced to uncover temporal feature evolution patterns, enhancing temporal QoS prediction. Extensive experiments on the WS-DREAM dataset demonstrate that GACL significantly outperforms state-of-the-art methods for temporal QoS prediction across multiple evaluation metrics, achieving the improvements of up to 38.80%.

Current state-of-the-art QoS prediction methods face two main limitations. Firstly, most existing QoS prediction approaches are centralized, gathering all user-service invocation QoS records for training and optimization, which causes privacy breaches. While some federated learning-based methods consider user privacy in a distributed way, they either directly upload local trained parameters or use simple encryption for global aggregation at the central server, thus failing to truly protect user privacy. Secondly, existing federated learning-based methods neglect distributed user-service topology and latent behavior-attribute correlations, compromising QoS prediction accuracy. To address these limitations, we propose a novel framework namedPrivacy-EnhancedFederated ExpandedGraphLearning (PE-FGL) for secure QoS prediction. It first conducts user-service expansion on the invocation graph with advanced privacy-preserving techniques, upgrading first-order local QoS invocations to high-order interaction relationships. Then, it extracts hybrid features from the expanded invocation graph via deep learning and graph residual learning. Finally, a two-layer secure mechanism of federated parameters aggregation is designed to enable collaborative learning among users through local parameter segmentation and global aggregation, achieving effective and secure QoS prediction. Extensive experiments on WS-DREAM demonstrate effective QoS prediction across multiple metrics while preserving privacy in user-service invocations.

Fine-tuning is the process of extending the training of pre-trained models on specific target tasks, thereby significantly enhancing their performance across various applications. However, fine-tuning often demands large memory consumption, posing a challenge for low-memory devices that some previous memory-efficient fine-tuning methods attempted to mitigate by pruning activations for gradient computation, albeit at the cost of significant computational overhead from the pruning processes during training. To address these challenges, we introduce PreBackRazor; a novel activation pruning scheme offering both computational and memory efficiency through a sparsified back-propagation strategy, which judiciously avoids unnecessary activation pruning and storage and gradient computation. Before activation pruning, our approach samples a probability of selecting a portion of parameters to freeze, utilizing a bandit method for updates to prioritize impactful gradients on convergence. During the feed-forward pass, each model layer adjusts adaptively based on parameter activation status, obviating the need for sparsification and storage of redundant activations for subsequent backpropagation. Benchmarking on fine-tuning foundation models, our approach maintains baseline accuracy across diverse tasks, yielding over 20% speedup and around 10% memory reduction. Moreover, integrating with an advanced CUDA kernel achieves up to 60% speedup without extra memory costs or accuracy loss, significantly enhancing the efficiency of fine-tuning foundation models on memory-constrained devices.

Designing a single model to address multiple tasks has been a long-standing objective in artificial intelligence. Recently, large language models have demonstrated exceptional capability in solving different tasks within the language domain. However, a unified model for various graph tasks remains underexplored, primarily due to the challenges unique to the graph learning domain. First, graph data from different areas carry distinct attributes and follow different distributions. Such discrepancy makes it hard to represent graphs in a single representation space. Second, tasks on graphs diversify into node, link, and graph tasks, requiring distinct embedding strategies. Finally, an appropriate graph prompting paradigm for in-context learning is unclear. We propose **One for All (OFA)**, the first general framework that can use a single graph model to address the above challenges. Specifically, OFA proposes text-attributed graphs to unify different graph data by describing nodes and edges with natural language and uses language models to encode the diverse and possibly cross-domain text attributes to feature vectors in the same embedding space. Furthermore, OFA introduces the concept of nodes-of-interest to standardize different tasks with a single task representation. For in-context learning on graphs, OFA introduces a novel graph prompting paradigm that appends prompting substructures to the input graph, which enables it to address varied tasks without fine-tuning. We train the OFA model using graph data from multiple domains (including citation networks, molecular graphs, knowledge graphs, etc.) simultaneously and evaluate its ability in supervised, few-shot, and zero-shot learning scenarios. OFA performs well across different tasks, making it the first general-purpose across-domains classification model on graphs.

The expressivity of Graph Neural Networks (GNNs) has been studied broadly in recent years to reveal the design principles for more powerful GNNs. Graph canonization is known as a typical approach to distinguish non-isomorphic graphs, yet rarely adopted when developing expressive GNNs. This paper proposes to maximize the expressivity of GNNs by graph canonization, then the power of such GNNs is studies from the perspective of model stability. A stable GNN will map similar graphs to close graph representations in the vectorial space, and the stability of GNNs is critical to generalize their performance to unseen graphs. We theoretically reveal the trade-off of expressivity and stability in graph-canonization-enhanced GNNs. Then we introduce a notion of universal graph canonization as the general solution to address the trade-off and characterize a widely applicable sufficient condition to solve the universal graph canonization. A comprehensive set of experiments demonstrates the effectiveness of the proposed method. In many popular graph benchmark datasets, graph canonization successfully enhances GNNs and provides highly competitive performance, indicating the capability and great potential of proposed method in general graph representation learning. In graph datasets where the sufficient condition holds, GNNs enhanced by universal graph canonization consistently outperform GNN baselines and successfully improve the SOTA performance up to $31$%, providing the optimal solution to numerous challenging real-world graph analytical tasks like gene network representation learning in bioinformatics.

Plasticity, the ability of a neural network to evolve with new data, is crucial for high-performance and sample-efficient visual reinforcement learning (VRL). Although methods like resetting and regularization can potentially mitigate plasticity loss, the influences of various components within the VRL framework on the agent's plasticity are still poorly understood. In this work, we conduct a systematic empirical exploration focusing on three primary underexplored facets and derive the following insightful conclusions: (1) data augmentation is essential in maintaining plasticity; (2) the critic's plasticity loss serves as the principal bottleneck impeding efficient training; and (3) without timely intervention to recover critic's plasticity in the early stages, its loss becomes catastrophic. These insights suggest a novel strategy to address the high replay ratio (RR) dilemma, where exacerbated plasticity loss hinders the potential improvements of sample efficiency brought by increased reuse frequency. Rather than setting a static RR for the entire training process, we propose Adaptive RR, which dynamically adjusts the RR based on the critic’s plasticity level. Extensive evaluations indicate that Adaptive RR not only avoids catastrophic plasticity loss in the early stages but also benefits from more frequent reuse in later phases, resulting in superior sample efficiency.

Large pre-trained models have enabled significant advances in machine learning and served as foundation components. Model fusion methods, such as task arithmetic, have been proven to be powerful and scalable to incorporate fine-tuned weights from different tasks into a multi-task model. However, efficiently fine-tuning large pre-trained models on multiple downstream tasks remains challenging, leading to inefficient multi-task model fusion. In this work, we propose a novel method to improve multi-task fusion for parameter-efficient fine-tuning techniques like LoRA fine-tuning. Specifically, our approach partially linearizes only the adapter modules and applies task arithmetic over the linearized adapters. This allows us to leverage the the advantages of model fusion over linearized fine-tuning, while still performing fine-tuning and inference efficiently. We demonstrate that our partial linearization technique enables a more effective fusion of multiple tasks into a single model, outperforming standard adapter tuning and task arithmetic alone. Experimental results demonstrate the capabilities of our proposed partial linearization technique to effectively construct unified multi-task models via the fusion of fine-tuned task vectors. We evaluate performance over an increasing number of tasks and find that our approach outperforms standard parameter-efficient fine-tuning techniques. The results highlight the benefits of partial linearization for scalable and efficient multi-task model fusion.

Memory replay based techniques have shown great success for continual learning with incrementally accumulated Euclidean data. Directly applying them to continually expanding networks, however, leads to the potential memory explosion problem due to the need to buffer representative nodes and their associated topological neighborhood structures. To this end, we systematically analyze the key challenges in the memory explosion problem, and present a general framework,i.e., Parameter Decoupled Graph Neural Networks (PDGNNs) with Topology-aware Embedding Memory (TEM), to tackle this issue. The proposed framework not only reduces the memory space complexity from O (ndL) to O (n)1: memory budget, d: average node degree, L: the radius of the GNN receptive field, but also fully utilizes the topological information for memory replay. Specifically, PDGNNs decouple trainable parameters from the computation ego-subnetwork viaTopology-aware Embeddings (TEs), which compress ego-subnetworks into compact vectors (i.e., TEs) to reduce the memory consumption. Based on this framework, we discover a unique pseudo-training effect in continual learning on expanding networks and this effect motivates us to develop a novel coverage maximization sampling strategy that can enhance the performance with a tight memory budget. Thorough empirical studies demonstrate that, by tackling the memory explosion problem and incorporating topological information into memory replay, PDGNNs with TEM significantly outperform state-of-the-art techniques, especially in the challenging class-incremental setting.

Cohort study is one of the most commonly used study methods in medical and public health researches, which result in longitudinal data. Conventional statistical models and machine learning methods are not capable of modeling the evolution trend of the variables in longitudinal data. In this article, we propose a Trend Analysis Neural Networks (TANN), which models the evolution trend of the variables by adaptive feature learning. TANN was tested on dataset of Kaiuan research. The task was to predict occurrence of cardiovascular events within 2 and 5 years, with three repeated medical examinations during 2008 and 2013. For 2-year prediction, The AUC of the TANN is 0.7378, which is a significant improvement than that of conventional methods, while that of TRNS, RNN, DNN, GBDT, RF, and LR are 0.7222, 0.7034, 0.7054, 0.7136, 0.7160, and 0.7024, respectively. For 5-year prediction, TANN also shows improvement. The experimental results show that the proposed TANN achieves better prediction performance on cardiovascular events prediction than conventional models. Furthermore, by analyzing the weights of TANN, we could find out important trends of the indicators, which are ignored by conventional machine learning models. The trend discovery mechanism interprets the model well. TANN is an appropriate balance between high performance and interpretability.

OBJECTIVE: An applied problem facing all areas of data science is harmonizing data sources. Joining data from multiple origins with unmapped and only partially overlapping features is a prerequisite to developing and testing robust, generalizable algorithms, especially in healthcare. This integrating is usually resolved using meta-data such as feature names, which may be unavailable or ambiguous. Our goal is to design methods that create a mapping between structured tabular datasets derived from electronic health records independent of meta-data. METHODS: We evaluate methods in the challenging case of numeric features without reliable and distinctive univariate summaries, such as nearly Gaussian and binary features. We assume that a small set of features are a priori mapped between two datasets, which share unknown identical features and possibly many unrelated features. Inter-feature relationships are the main source of identification which we expect. We compare the performance of contrastive learning methods for feature representations, novel partial auto-encoders, mutual-information graph optimizers, and simple statistical baselines on simulated data, public datasets, the MIMIC-III medical-record changeover, and perioperative records from before and after a medical-record system change. Performance was evaluated using both mapping of identical features and reconstruction accuracy of examples in the format of the other dataset. RESULTS: Contrastive learning-based methods overall performed the best, often substantially beating the literature baseline in matching and reconstruction, especially in the more challenging real data experiments. Partial auto-encoder methods showed on-par matching with contrastive methods in all synthetic and some real datasets, along with good reconstruction. However, the statistical method we created performed reasonably well in many cases, with much less dependence on hyperparameter tuning. When validating feature match output in the EHR dataset we found that some mistakes were actually a surrogate or related feature as reviewed by two subject matter experts. CONCLUSION: In simulation studies and real-world examples, we find that inter-feature relationships are effective at identifying matching or closely related features across tabular datasets when meta-data is not available. Decoder architectures are also reasonably effective at imputing features without an exact match.

Transformers, originally devised for natural language processing (NLP), have also produced significant successes in computer vision (CV). Due to their strong expression power, researchers are investigating ways to deploy transformers for reinforcement learning (RL), and transformer-based models have manifested their potential in representative RL benchmarks. In this paper, we collect and dissect recent advances concerning the transformation of RL with transformers (transformer-based RL (TRL)) to explore the development trajectory and future trends of this field. We group the existing developments into two categories: architecture enhancements and trajectory optimizations, and examine the main applications of TRL in robotic manipulation, text-based games (TBGs), navigation, and autonomous driving. Architecture enhancement methods consider how to apply the powerful transformer structure to RL problems under the traditional RL framework, facilitating more precise modeling of agents and environments compared to traditional deep RL techniques. However, these methods are still limited by the inherent defects of traditional RL algorithms, such as bootstrapping and the "deadly triad". Trajectory optimization methods treat RL problems as sequence modeling problems and train a joint state-action model over entire trajectories under the behavior cloning framework; such approaches are able to extract policies from static datasets and fully use the long-sequence modeling capabilities of transformers. Given these advancements, the limitations and challenges in TRL are reviewed and proposals regarding future research directions are discussed. We hope that this survey can provide a detailed introduction to TRL and motivate future research in this rapidly developing field.

The proliferation of homogeneous web services has necessitated the task of predicting vacant Quality of Service (QoS) for service-oriented downstream tasks. Existing approaches primarily focus on user-service invocations without considering temporal factors, limiting their applicability in QoS fluctuations over time. Moreover, some investigations are conducted to predict temporally missing QoS, which still suffers from two limitations. First, time-aware collaborative filtering (CF) approaches fail to well capture continuous temporal changes, which lowers the performance of time-aware QoS prediction. Second, they have paid less attention to the high sparsity of user-service QoS invocations across sequentially multiple time slices, which affects the calculation of temporal average QoS, thereby further reducing the accuracy of time-aware QoS prediction. To effectively mine the continuous temporal variations and solve the high sparsity of user-service QoS invocations, we propose a novel time-aware QoS prediction approach named Temporal Reinforced Collaborative Filtering (TRCF). We design temporal reinforced RBS and PCC to improve similarity evaluation that leads to better calculation of temporal average QoS and deviation migration for predicting time-aware QoS. We evaluate TRCF on a large-scale real-world temporal dataset WS-DREAM across 64 time slices and the results demonstrate its superior performance in time-aware QoS prediction, both under relatively dense and extremely sparse QoS situations.

QoS prediction plays an important role in service-oriented downstream tasks. However, most of current state-of-the-art QoS prediction approaches suffer from two limitations. First, traditional approaches typically require collection of user-service historical QoS invocations centrally in order to improve QoS prediction accuracy, which poses a threat to user data privacy. Second, although few of the recent approaches take into account data protection when predicting QoS values, they still cannot effectively capture user-service complex nonlinear invocation relationships, significantly influencing the performance of QoS prediction. To address these two issues, we propose a novel framework of data-protected QoS prediction called Federated Residual Ladder Network (FRLN), which ensures user data protection and effectiveness of predicting missing QoS values. It initially leverages our designed Residual Ladder Network (RLN) to extract latent features of users and services from both low and high dimensional spaces. Then, local QoS prediction models are collaboratively trained by personalized federated learning with the consideration of data heterogeneity. Extensive experiments have been conducted on a real-world large-scale dataset called WS-DREAM, which consists of 5825 Web services from 74 regions and 339 users from 31 regions comprising a total number of 1,974,675 user-service QoS invocations. Experimental results demonstrate the effectiveness of FRLN in multiple evaluation metrics. While the proposed FRLN framework marks a significant step forward for QoS prediction in machine learning, ongoing advancements in ML techniques and expanded datasets are essential for further enhancing its precision and applicability in real-world scenarios.

We present GNNHLS, an open-source framework to comprehensively evaluate GNN inference acceleration on FPGAs via HLS, containing a software stack for data generation and baseline deployment and FPGA implementations of 6 well-tuned GNN HLS kernels. Evaluating on 4 graph datasets with distinct topologies and scales, the results show that GNNHLS achieves up to 50.8× speedup and 423× energy reduction relative to the CPU baselines. Compared with the GPU baselines, GNNHLS achieves up to 5.16× speedup and 74.5× energy reduction.

In service recommender system, graph neural networks (GNNs) perform message passing through diffusion mechanism based on user-service relationship graph. However, existing GNN-based service recommendation models suffer from two limitations: ❨1❩ message passing is only carried out at firstorder neighbors, as higher-order may cause over-smoothing phenomenon, confining feature propagation in GNNs; and ❨2❩ due to sparse and noisy interactions, the distribution of embedding vectors is nonuniform in the latent space, resulting in unsatisfactory performance for downstream applications. To this end, we propose a fixed global graph diffusion view that is independent of the original user-service observed local view to form a multi-view learning by building contrastive learning (CL) relationship, named as Multi-View Graph Contrastive Learning (MVGCL). Specifically, it enhances the capability of message passing through constructed local and global multi-view graphs, and alleviates the sparse and noisy influences by performing intra-CL within local/global view and inter-CL between multi-view to obtain a more uniform distribution of user and service node representations. Extensive experiments are conducted on three benchmark datasets within different scales, and the results demonstrate that our proposed MVGCL can remarkably outperforms state-of-the-art competing baselines on various evaluation metrics.

This paper studies multiparty learning, aiming to learn a model using the private data of different participants. Model reuse is a promising solution for multiparty learning, assuming that a local model has been trained for each party. Considering the potential sample selection bias among different parties, some heterogeneous model reuse approaches have been developed. However, although pre-trained local classifiers are utilized in these approaches, the characteristics of the local data are not well exploited. This motivates us to estimate the density of local data and design an auxiliary model together with the local classifiers for reuse. To address the scenarios where some local models are not well pre-trained, we further design a multiparty cross-entropy loss for calibration. Upon existing works, we address a challenging problem of heterogeneous model reuse from a decision theory perspective and take advantage of recent advances in density estimation. Experimental results on both synthetic and benchmark data demonstrate the superiority of the proposed method.

Relying on large-scale training data with pixel-level labels, previous edge detection methods have achieved high performance. However, it is hard to manually label edges accurately, especially for large datasets, and thus the datasets inevitably contain noisy labels. This label-noise issue has been studied extensively for classification, while still remaining under-explored for edge detection. To address the label-noise issue for edge detection, this paper proposes to learn Pixel-level Noise Transitions to model the label-corruption process. To achieve it, we develop a novel Pixel-wise Shift Learning (PSL) module to estimate the transition from clean to noisy labels as a displacement field. Exploiting the estimated noise transitions, our model, named PNT-Edge, is able to fit the prediction to clean labels. In addition, a local edge density regularization term is devised to exploit local structure information for better transition learning. This term encourages learning large shifts for the edges with complex local structures. Experiments on SBD and Cityscapes demonstrate the effectiveness of our method in relieving the impact of label noise. Codes will be available at github.com/DREAMXFAR/PNT-Edge.

Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. Some works are inspired by $k$-WL/FWL (Folklore WL) and design the corresponding neural versions. Despite the high expressive power, there are serious limitations in this line of research. In particular, (1) $k$-WL/FWL requires at least $O(n^k)$ space complexity, which is impractical for large graphs even when $k=3$; (2) The design space of $k$-WL/FWL is rigid, with the only adjustable hyper-parameter being $k$. To tackle the first limitation, we propose an extension, $(k, t)$-FWL. We theoretically prove that even if we fix the space complexity to $O(n^k)$ (for any $k \geq 2$) in $(k, t)$-FWL, we can construct an expressiveness hierarchy up to solving the graph isomorphism problem. To tackle the second problem, we propose $k$-FWL+, which considers any equivariant set as neighbors instead of all nodes, thereby greatly expanding the design space of $k$-FWL. Combining these two modifications results in a flexible and powerful framework $(k, t)$-FWL+. We demonstrate $(k, t)$-FWL+ can implement most existing models with matching expressiveness. We then introduce an instance of $(k,t)$-FWL+ called Neighborhood$^2$-FWL (N$^2$-FWL), which is practically and theoretically sound. We prove that N$^2$-FWL is no less powerful than 3-WL, and can encode many substructures while only requiring $O(n^2)$ space. Finally, we design its neural version named **N$^2$-GNN** and evaluate its performance on various tasks. N$^2$-GNN achieves record-breaking results on ZINC-Subset (**0.059**), outperforming previous SOTA results by 10.6\%. Moreover, N$^2$-GNN achieves new SOTA results on the BREC dataset (**71.8\%**) among all existing high-expressive GNN methods.

While Graph Neural Networks (GNNs) recently became powerful tools in graph learning tasks, considerable efforts have been spent on improving GNNs' structural encoding ability. A particular line of work proposed subgraph GNNs that use subgraph information to improve GNNs' expressivity and achieved great success. However, such effectivity sacrifices the efficiency of GNNs by enumerating all possible subgraphs. In this paper, we analyze the necessity of complete subgraph enumeration and show that a model can achieve a comparable level of expressivity by considering a small subset of the subgraphs. We then formulate the identification of the optimal subset as a combinatorial optimization problem and propose Magnetic Graph Neural Network (MAG-GNN), a reinforcement learning (RL) boosted GNN, to solve the problem. Starting with a candidate subgraph set, MAG-GNN employs an RL agent to iteratively update the subgraphs to locate the most expressive set for prediction. This reduces the exponential complexity of subgraph enumeration to the constant complexity of a subgraph search algorithm while keeping good expressivity. We conduct extensive experiments on many datasets, showing that MAG-GNN achieves competitive performance to state-of-the-art methods and even outperforms many subgraph GNNs. We also demonstrate that MAG-GNN effectively reduces the running time of subgraph GNNs.

We are currently in a network era which enables us to communicate more widely and more easily via the social networks. Meanwhile, negative information, such as fake news, rumors and computer viruses, often spread in social network. In order to restrain the propagation of such negative influence, we must find its sources in the network. But in real-world applications, we usually only know the scope of the negative influence spreading, and do not know who first propagates the negative influence. However, we can identify the sources of the negative influence based on the information of some observed nodes which are negatively influenced. This is the problem of influence sources locating. To tackle this problem, we present a latent space mapping-based method for identifying the multiple influence sources in the independent cascade model. The method first detects the candidate sources of the observed nodes based on message passing in a reversed network. An algorithm is presented to calculate the activation probability between nodes according to the influence spreading pattern in the independent cascade model. To evaluate each node’s rationality as the propagation source, we use the difference between the length of the path influencing an observed node and its activation time. We define two latent spaces, namely the influence senders and receivers’ latent spaces, and map the nodes into these two latent spaces to form a model describing the influence propagation. An estimation-maximization-based algorithm is proposed to optimize the propagation model. Based on this model, we propose a latent space mapping-based algorithm to identify the influence sources. The probability for each node to be a source is calculated by its positions in the latent spaces. Finally, k nodes with the largest probabilities are selected as the sources. Empirical results demonstrate that the influence sources identified by the proposed method can influence more observed nodes at more accurate time than other methods.

With the overwhelming explosion of Web services, how to effectively predict unknown QoS has become a key issue of differentiating large-scale similar or functionally equivalent Web services. However, current state-of-the-art QoS prediction approaches based on deep learning still suffer from two deficiencies. First, they mainly focus on predicting vacant QoS in a centralized manner and scarcely take into account distributed QoS prediction, which makes difficult to protect the privacy information of users invoking Web services. Second, they have ignored the hierarchical collaborative relationship to better extract latent features of users and services, reducing the accuracy of QoS prediction. To address these two issues, we propose a novel framework calledFederatedHierarchicalClustering forDistributedQoSPrediction(FHC-DQP). It collaboratively performs distributed federated training on independent users’ QoS invocations, and then the extracted federated users’ private features are fed to clustering algorithm for partitioning them into a set of clusters. By iteratively federated hierarchical clustering, users are fine-grained partitioned together and those users within the same cluster have stronger collaborative relevance for more effectively learning the latent features of users and services leading to the performance improvement of distributed QoS prediction, where contextual-aware deep neural network is designed for personalized QoS prediction. Extensive experiments are conducted based on a public real-world benchmarking dataset called WS-DREAM with almost 2,000,000 user-service historical QoS invocations. Compared with both centralized and federated competing baselines, the results demonstrate FHC-DQP receives superior performance for distributed QoS prediction, when it provides privacy-preserving of users’ QoS invocations.

How to accurately predict vacant QoS has become a fundamental issue for service-oriented downstream tasks. However, most QoS prediction approaches based on model learning fail to discriminatively capture the latent feature representations of a user and a service, since they either leverage the shallow neural network such as MLP or take advantage of insufficient location information. Moreover, collaborative relationships of similar neighborhood have not been fully taken into account together with prediction model learning. To address these issues, we propose a novel framework for adaptive QoS prediction named Neighborhood-based Collaborative Residual Learning (NCRL). Location-aware two-tower deep residual network is designed to achieve neural QoS prediction by extracting latent features of users and services, which are fed to generate similar neighborhood for collaborative prediction based on historical QoS invocations. They are integrally combined to perform adaptive QoS prediction. Extensive experiments are conducted based on a large-scale real-world QoS dataset called WS-DREAM with almost 2,000,000 historical QoS invocations. The results indicate that NCRL can remarkably outperform state-of-the-art competing baselines.

The unsupervised anomaly detection in KPI (Key Performance Indicator) series has been an active research area due to its enormous potential for application in industry. KPI series representation, reconstruction, and forecasting have made extraordinary progress in existing work. However, long-term temporal patterns prohibit the model from learning reliable dependencies. To this end, we propose a novel approach based on VAE-TCN hybrid model. Our model uses VAE (variational automatic coder) to learn robust local features in a short window, and uses TCN (temporal convolution network) to estimate the long-term correlation in the sequence based on the features inferred by VAE module. Extensive experiments on various public benchmarks demonstrate that our method has achieved the state-of-the-art performance.

Optimization of directed acyclic graph (DAG) structures has many applications, such as neural architecture search (NAS) and probabilistic graphical model learning. Encoding DAGs into real vectors is a dominant component in most neural-network-based DAG optimization frameworks. Currently, most popular DAG encoders use an asynchronous message passing scheme which sequentially processes nodes according to the dependency between nodes in a DAG. That is, a node must not be processed until all its predecessors are processed. As a result, they are inherently not parallelizable. In this work, we propose a Parallelizable Attention-based Computation structure Encoder (PACE) that processes nodes simultaneously and encodes DAGs in parallel. We demonstrate the superiority of PACE through encoder-dependent optimization subroutines that search the optimal DAG structure based on the learned DAG embeddings. Experiments show that PACE not only improves the effectiveness over previous sequential DAG encoders with a significantly boosted training and inference speed, but also generates smooth latent (DAG encoding) spaces that are beneficial to downstream optimization subroutines.

Unsupervised anomaly detection for time series has been an active research area due to its enormous potential for wireless network management. Existing works have made extraordinary progress in time series representation, reconstruction and forecasting. However, long-term temporal patterns prohibit the model from learning reliable dependencies. To this end, we propose a novel approach based on Transformer with dilated convolution for time anomaly detection. Specifically, we provide a dilated convolution module to extract long-term dependence features. Extensive experiments on various public benchmarks demonstrate that our method has achieved the state-of-the-art performance.

The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop message passing---aggregating information from 1-hop neighbors repeatedly. However, the expressive power of 1-hop message passing is bounded by the Weisfeiler-Lehman (1-WL) test. Recently, researchers extended 1-hop message passing to $K$-hop message passing by aggregating information from $K$-hop neighbors of nodes simultaneously. However, there is no work on analyzing the expressive power of $K$-hop message passing. In this work, we theoretically characterize the expressive power of $K$-hop message passing. Specifically, we first formally differentiate two different kernels of $K$-hop message passing which are often misused in previous works. We then characterize the expressive power of $K$-hop message passing by showing that it is more powerful than 1-WL and can distinguish almost all regular graphs. Despite the higher expressive power, we show that $K$-hop message passing still cannot distinguish some simple regular graphs and its expressive power is bounded by 3-WL. To further enhance its expressive power, we introduce a KP-GNN framework, which improves $K$-hop message passing by leveraging the peripheral subgraph information in each hop. We show that KP-GNN can distinguish many distance regular graphs which could not be distinguished by previous distance encoding or 3-WL methods. Experimental results verify the expressive power and effectiveness of KP-GNN. KP-GNN achieves competitive results across all benchmark datasets.

Graph Neural Networks (GNNs) have recently been applied to graph learning tasks and achieved state-of-the-art (SOTA) results. However, many competitive methods run GNNs multiple times with subgraph extraction and customized labeling to capture information that is hard for normal GNNs to learn. Such operations are time-consuming and do not scale to large graphs. In this paper, we propose an efficient GNN framework called Geodesic GNN (GDGNN) that requires only one GNN run and injects conditional relationships between nodes into the model without labeling. This strategy effectively reduces the runtime of subgraph methods. Specifically, we view the shortest paths between two nodes as the spatial graph context of the neighborhood around them. The GNN embeddings of nodes on the shortest paths are used to generate geodesic representations. Conditioned on the geodesic representations, GDGNN can generate node, link, and graph representations that carry much richer structural information than plain GNNs. We theoretically prove that GDGNN is more powerful than plain GNNs. We present experimental results to show that GDGNN achieves highly competitive performance with SOTA GNN models on various graph learning tasks while taking significantly less time.

With the explosive growth in the number and diversity of Web services, correlative research has been investigated on Web service classification, as it fundamentally promotes advanced service-oriented applications, such as service discovery, selection, composition and recommendation. However, conventional approaches are restricted to indiscriminatingly classify Web services, which can trigger many challenges. First, they have not made full advantage of the implicit relationships among multi-dimensional information of Web services, such as the increasing number of service categories. Thus, it leads to low effectiveness of learning and representing service features, failing to ensure the overall accuracy of service classification. Second, the imbalance of service distributions has been ignored, while it is observed that service categories reveal distinct long-tail characteristics. That results in low accuracy on service classification for those categories that contain fewer Web services. To handle the challenges of more effectively learning implicit service features across the service repository, and with a particular concentration on those tail categories that contain fewer Web services, we propose a novel framework called DeepLTSC to more accurately perform the task of Web service classification under long-tail distributions. In DeepLTSC, we first present an improved label attentive convolutional deep neural network (LACNN) with service categories, which can generate deep service features to improve the overall classification performance. Then, a proposed service feature augmentation model (SFA) together with focal loss function is integrated into DeepLTSC to further optimize service features, aiming to boost the classification accuracy on tail service categories. Extensive experiments are conducted on three large-scale real-world services datasets with different long-tail distributions. The results demonstrate that DeepLTSC significantly outperforms state-of-the-art approaches for Web service classification on both overall and tail categories.

Cohort study is one of the most commonly used study methods in medical and public health researches, which result in longitudinal data. Conventional statistical models and machine learning methods are not capable of modeling the evolution trend of the variables in longitudinal data. In this paper, we propose a Trend Analysis Neural Networks (TANN), which models the evolution trend of the variables by adaptive feature learning. TANN was tested on dataset of Kaiuan research. The task was to predict occurrence of death within 5 years, with 3 repeated medical examinations from 2008 to 2013. The AUC of the TANN is 0.7888, which is a slightly improvement than that of conventional methods, while that of GBDT is 0.7824, that of random forests is 0.7822, and that of logistic regression is 0.7789. The experimental results show that the proposed TANN achieves better prediction performance on death events prediction than conventional models. Furthermore, by analyzing the weights of TANN, we could find out important trends of the indicators. The trend discovery mechanism interprets the model well. TANN is an appropriate trade-off between high performance and interpretability.

Accurate and timely prediction of the Internet traffic flow is important for network performance improvement. Few prediction methods incorporate the topology information of networks. In this paper, we present a novel Internet traffic forecasting algorithm named TTGCN, which applies the graph neural networks for traffic flow prediction on each link of a backbone network. The topology of the network was represented by a novel adjacency matrix, which models the relationship between links. The design makes TTGCN capable of capturing both the temporal and topological information of the traffic flow. TTGCN is validated on UKERNA, a dataset captured from a real backbone network. The experimental results show that the average error of the proposed TTGCN over 90 minutes is 28.249 (Mbit/s), which is a significant improvement of conventional models, while that of ARIMA and GRU and STGCN are 44.955, 40.935, and 36.152, respectively. The proposed TTGCN, by encoding both temporal and topological information in a neural representation, can achieve better prediction performance on network traffic.

Device-to-Device (D2D) communication has now become one of the most promising technologies in wireless communications of the Internet of Things (IoT). In view of the requirements on data security, response speed, signal decryption quality and storage cost of mobile devices in D2D networks, we propose chaotic deep network (CDN) to achieve secure transmission which is swifter, higher quality and lower cost. The proposed scheme consists of a prepositive nonrepetitive training procedure, a well-designed parallel encryption process, and a set of pretrained chaotic deep neural decryption networks. Benefiting from the utilization of deep learning methods, CDN achieves the swift and accurate decryption at a much lower sampling rate, which brings huge dimension reduction of both measurement matrices and ciphertext signals. Also, chaotic initial values and parameters are applied to matrix generation and network training, leading to great time reduction, storage saving and security improvement. In addition, CDN incorporates the frameworks of semitensor product (STP) and block-based image processing (BIP), which not only breaks through the dimension matching limitation of matrix multiplication by using STP but also maintains the parallelizable block-cipher mode of BIP. Proved by experiments, CDN at the sampling ratio of 25% achieves almost the same or even better peak signal to noise ratio compared to other 8 most frequently used methods at that of 50% for the same test images, and obtains better visual effects. When using a large-sized image of$2^{10}\times 2^{10}$pixels for the experiments, CDN is dozens and even hundreds of times faster than those methods, while reduces the size of measurement matrix from a 500-kB level to a 3-kB level, and the size of compressed data to be transmitted can be reduced by more than 50% as well. Besides, the total key space is approximately$10^{93}$. The adjacent pixel correlation is less than 0.01.

Software vulnerability detection in source code is a fundamental problem in cyber-security. Aiming at discovering the vulnerability automatically, this paper proposes an open source software vulnerability detection method based on attention-based bidirectional recurrent neural networks. Based on the high-level and generalizable function representations that obtained from the abstract syntax tree(AST), an attention-based bidirectional recurrent neural networks is devised to capture the sequential and important code elements in vulnerability detection from the large number of features that the deep learning model has learned. Experimental results confirm that the huge potential of the proposed new vulnerability detection method which is not only more effective than Convolutional Neural Networks(CNN) but also better than traditional Bidirectional Recurrent Neural Networks(BRNN) in reducing the false negative rate at the price of increasing the false positive rate.

Medical ontologies are widely used to represent and organize medical terminologies. Examples include ICD-9, ICD-10, UMLS etc. The ontologies are often constructed in hierarchical structures, encoding the multi-level subclass relationships among different medical concepts, allowing very fine distinctions between concepts. Medical ontologies provide a great source for incorporating domain knowledge into a healthcare prediction system, which might alleviate the data insufficiency problem and improve predictive performance with rare categories. To incorporate such domain knowledge, Gram, a recent graph attention model, represents a medical concept as a weighted sum of its ancestors' embeddings in the ontology using an attention mechanism. Although showing improved performance, Gram only considers the unordered ancestors of a concept, which does not fully leverage the hierarchy thus having limited expressibility. In this paper, we propose Hierarchical Attention Propagation (HAP), a novel medical ontology embedding model that hierarchically propagate attention across the entire ontology structure, where a medical concept adaptively learns its embedding from all other concepts in the hierarchy instead of only its ancestors. We prove that HAP learns more expressive medical concept embeddings -- from any medical concept embedding we are able to fully recover the entire ontology structure. Experimental results on two sequential procedure/diagnosis prediction tasks demonstrate HAP's better embedding quality than Gram and other baselines. Furthermore, we find that it is not always best to use the full ontology. Sometimes using only lower levels of the hierarchy outperforms using all levels.

Graphs are commonly used to represent objects, such as images and text, for pattern classification. In a dynamic world, an object may continuously evolve over time, and so does the graph extracted from the underlying object. These changes in graph structure with respect to the temporal order present a new representation of the graph, in which an object corresponds to a set of time-variant graphs. In this paper, we formulate a novel time-variant graph classification task and propose a new graph feature, called a graph-shapelet pattern, for learning and classifying time-variant graphs. Graph-shapelet patterns are compact and discriminative graph transformation subsequences. A graph-shapelet pattern can be regarded as a graphical extension of a shapelet-a class of discriminative features designed for vector-based temporal data classification. To discover graph-shapelet patterns, we propose to convert a time-variant graph sequence into time-series data and use the discovered shapelets to find graph transformation subsequences as graph-shapelet patterns. By converting each graph-shapelet pattern into a unique tokenized graph transformation sequence, we can measure the similarity between two graph-shapelet patterns and therefore classify time-variant graphs. Experiments on both synthetic and real-world data demonstrate the superior performance of the proposed algorithms.

Graph structured data are abundant in the real world. Among different graph types, directed acyclic graphs (DAGs) are of particular interest to machine learning researchers, as many machine learning models are realized as computations on DAGs, including neural networks and Bayesian networks. In this paper, we study deep generative models for DAGs, and propose a novel DAG variational autoencoder (D-VAE). To encode DAGs into the latent space, we leverage graph neural networks. We propose an asynchronous message passing scheme that allows encoding the computations on DAGs, rather than using existing simultaneous message passing schemes to encode local graph structures. We demonstrate the effectiveness of our proposed DVAE through two tasks: neural architecture search and Bayesian network structure learning. Experiments show that our model not only generates novel and valid DAGs, but also produces a smooth latent space that facilitates searching for DAGs with better performance through Bayesian optimization.

This paper formulates the problem of learning discriminative features (i.e., segments) from networked time-series data, considering the linked information among time series. For example, social network users are considered to be social sensors that continuously generate social signals represented as a time series. The discriminative segments are often referred to as shapelets in a time series. Extracting shapelets for time-series analysis has been widely studied. However, existing works on shapelet selection assume that the time series are independent and identically distributed. This assumption restricts their applications to social networked time-series analysis since a user's actions can be correlated to his/her social affiliations. In this paper, we propose a novel network regularized least squares (NetRLS) feature selection model that combines typical time-series data and user network data for analysis. Experiments on real-world Twitter, Weibo, and DBLP networked time-series data demonstrate the performance of the proposed method. NetRLS performs better than the representative baselines on four evaluation criteria, namely classification accuracy, area under the curve (AUC), F1-score, and statistical significance analysis. NetRLS also has competitive running time as the baselines.

This paper addresses the hyperlink prediction problem in hypernetworks. Different from the traditional link prediction problem where only pairwise relations are considered as links, our task here is to predict the linkage of multiple nodes, i.e., hyperlink. Each hyperlink is a set of an arbitrary number of nodes which together form a multiway relationship. Hyperlink prediction is challenging---since the cardinality of a hyperlink is variable, existing classifiers based on a fixed number of input features become infeasible. Heuristic methods, such as the common neighbors and Katz index, do not work for hyperlink prediction, since they are restricted to pairwise similarities. In this paper, we formally define the hyperlink prediction problem, and propose a new algorithm called Coordinated Matrix Minimization (CMM), which alternately performs nonnegative matrix factorization and least square matching in the vertex adjacency space of the hypernetwork, in order to infer a subset of candidate hyperlinks that are most suitable to fill the training hypernetwork. We evaluate CMM on two novel tasks: predicting recipes of Chinese food, and finding missing reactions of metabolic networks. Experimental results demonstrate the superior performance of our method over many seemingly promising baselines.

Neural networks are typically designed to deal with data in tensor forms. In this paper, we propose a novel neural network architecture accepting graphs of arbitrary structure. Given a dataset containing graphs in the form of (G,y) where G is a graph and y is its class, we aim to develop neural networks that read the graphs directly and learn a classification function. There are two main challenges: 1) how to extract useful features characterizing the rich information encoded in a graph for classification purpose, and 2) how to sequentially read a graph in a meaningful and consistent order. To address the first challenge, we design a localized graph convolution model and show its connection with two graph kernels. To address the second challenge, we design a novel SortPooling layer which sorts graph vertices in a consistent order so that traditional neural networks can be trained on the graphs. Experiments on benchmark graph classification datasets demonstrate that the proposed architecture achieves highly competitive performance with state-of-the-art graph kernels and other graph neural network methods. Moreover, the architecture allows end-to-end gradient-based training with original graphs, without the need to first transform graphs into vectors.

The Electrocardiogram (ECG) is commonly used to detect arrhythmias. Traditionally, a single ECG observation is used for diagnosis, making it difficult to detect irregular arrhythmias. Recent technology developments, however, have made it cost-effective to collect large amounts of raw ECG data over time. This promises to improve diagnosis accuracy, but the large data volume presents new challenges for cardiologists. This paper introduces ECGLens, an interactive system for arrhythmia detection and analysis using large-scale ECG data. Our system integrates an automatic heartbeat classification algorithm based on convolutional neural network, an outlier detection algorithm, and a set of rich interaction techniques. We also introduce A-glyph, a novel glyph designed to improve the readability and comparison of ECG signals. We report results from a comprehensive user study showing that A-glyph improves the efficiency in arrhythmia detection, and demonstrate the effectiveness of ECGLens in arrhythmia detection through two expert interviews.

Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a ``heuristic'' that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel $\gamma$-decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the $\gamma$-decaying theory, we propose a new method to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.

With increased use of electronic medical records (EMRs), data mining on medical data has great potential to improve the quality of hospital treatment and increase the survival rate of patients. Early readmission prediction enables early intervention, which is essential to preventing serious or life-threatening events, and act as a substantial contributor to reduce healthcare costs. Existing works on predicting readmission often focus on certain vital signs and diseases by extracting statistical features. They also fail to consider skewness of class labels in medical data and different costs of misclassification errors. In this paper, we recur to the merits of convolutional neural networks (CNN) to automatically learn features from time series of vital sign, and categorical feature embedding to effectively encode feature vectors with heterogeneous clinical features, such as demographics, hospitalization history, vital signs, and laboratory tests. Then, both learnt features via CNN and statistical features via feature embedding are fed into a multilayer perceptron (MLP) for prediction. We use a cost-sensitive formulation to train MLP during prediction to tackle the imbalance and skewness challenge. We validate the proposed approach on two real medical datasets from Barnes-Jewish Hospital, and all data is taken from historical EMR databases and reflects the kinds of data that would realistically be available at the clinical prediction system in hospitals. We find that early prediction of readmission is possible and when compared with state-of-the-art existing methods used by hospitals, our methods perform significantly better. For example, using the general hospital wards data for 30-day readmission prediction, the area under the curve (AUC) for the proposed model was 0.70, significantly higher than all the baseline methods. Based on these results, a system is being deployed in hospital settings with the proposed forecasting algorithms to support treatment.

Atrial Fibrillation (AF) is the most common chronic arrhythmia. Effective detection of the AF would avoid serious consequences like stroke. Conventional AF detection methods need heuristic or hand-craft feature extraction. In this paper, A deep neural network named multi-scale convolutional neural networks (MCNN) based AF detector is proposed. Instant heart rate sequence is extracted from ECG signal, then an end-to-end MCNN detects AF with the instant heart rate sequence as input and detection result as output. The algorithm was tested on both public and private datasets. On the public dataset, with the sensitivity achieved being 0.9822, the corresponding specificity is 0.9811, and the overall accuracy is 0.9818. The area under an ROC curve is as high as 0.9962, compared to the AUC of the best conventional method is 0.9947. Comparison shows that the MCNN based AF detector give superior accuracy than conventional methods. Test on private dataset also shows significant improvement.

In this paper, we propose a next-generation link prediction method, Weisfeiler-Lehman Neural Machine (WLNM), which learns topological features in the form of graph patterns that promote the formation of links. WLNM has unmatched advantages including higher performance than state-of-the-art methods and universal applicability over various kinds of networks. WLNM extracts an enclosing subgraph of each target link and encodes the subgraph as an adjacency matrix. The key novelty of the encoding comes from a fast hashing-based Weisfeiler-Lehman (WL) algorithm that labels the vertices according to their structural roles in the subgraph while preserving the subgraph's intrinsic directionality. After that, a neural network is trained on these adjacency matrices to learn a predictive model. Compared with traditional link prediction methods, WLNM does not assume a particular link formation mechanism (such as common neighbors), but learns this mechanism from the graph itself. We conduct comprehensive experiments to show that WLNM not only outperforms a great number of state-of-the-art link prediction methods, but also consistently performs well across networks with different characteristics.

Motivation: Metabolic network reconstructions are often incomplete. Constraint-based and pattern-based methodologies have been used for automated gap filling of these networks, each with its own strengths and weaknesses. Moreover, since validation of hypotheses made by gap filling tools require experimentation, it is challenging to benchmark performance and make improvements other than that related to speed and scalability. Results: We present BoostGAPFILL, an open source tool that leverages both constraint-based and machine learning methodologies for hypotheses generation in gap filling and metabolic model refinement. BoostGAPFILL uses metabolite patterns in the incomplete network captured using a matrix factorization formulation to constrain the set of reactions used to fill gaps in a metabolic network. We formulate a testing framework based on the available metabolic reconstructions and demonstrate the superiority of BoostGAPFILL to state-of-the-art gap filling tools. We randomly delete a number of reactions from a metabolic network and rate the different algorithms on their ability to both predict the deleted reactions from a universal set and to fill gaps. For most metabolic network reconstructions tested, BoostGAPFILL shows above 60% precision and recall, which is more than twice that of other existing tools. Availability and Implementation: MATLAB open source implementation ( https://github.com/Tolutola/BoostGAPFILL ). Contacts: [email protected] or [email protected] . Supplementary information: Supplementary data are available at Bioinformatics online.

Link prediction aims at estimating the likelihood of the existence of links between nodes. In this paper, we treat link prediction as a collaborative filtering problem, and propose an algorithm to solve this problem using matrix factorization approach. For making better predictions, this paper also explores the use of bagging technique as combination approaches for matrix factorization. We subsample the training set and added random noise to make multiple classifiers, and then combine these classifiers to be the final classifier. Results on several data sets show the efficacy of our approach. Compared with several popular proximity metrics, the accuracy of the algorithm can be increased greatly by use of bagging technique, especially measured by precision.

Convolutional neural networks (CNN) are increasingly used in many areas of computer vision. They are particularly attractive because of their ability to "absorb" great quantities of labeled data through millions of parameters. However, as model sizes increase, so do the storage and memory requirements of the classifiers, hindering many applications such as image and speech recognition on mobile phones and other devices. In this paper, we present a novel net- work architecture, Frequency-Sensitive Hashed Nets (FreshNets), which exploits inherent redundancy in both convolutional layers and fully-connected layers of a deep learning model, leading to dramatic savings in memory and storage consumption. Based on the key observation that the weights of learned convolutional filters are typically smooth and low-frequency, we first convert filter weights to the frequency domain with a discrete cosine transform (DCT) and use a low-cost hash function to randomly group frequency parameters into hash buckets. All parameters assigned the same hash bucket share a single value learned with standard back-propagation. To further reduce model size, we allocate fewer hash buckets to high-frequency components, which are generally less important. We evaluate FreshNets on eight data sets, and show that it leads to better compressed performance than several relevant baselines.

Abstract Background Flux analyses, including flux balance analysis (FBA) and 13C-metabolic flux analysis (13C-MFA), offer direct insights into cell metabolism, and have been widely used to characterize model and non-model microbial species. Nonetheless, constructing the 13C-MFA model and performing flux calculation are demanding for new learners, because they require knowledge of metabolic networks, carbon transitions, and computer programming. To facilitate and standardize the 13C-MFA modeling work, we set out to publish a user-friendly and programming-free platform (WUFlux) for flux calculations in MATLAB®. Results We constructed an open-source platform for steady-state 13C-MFA. Using GUIDE (graphical user interface design environment) in MATLAB, we built a user interface that allows users to modify models based on their own experimental conditions. WUFlux is capable of directly correcting mass spectrum data of TBDMS (N-tert-butyldimethylsilyl-N-methyltrifluoroacetamide)-derivatized proteinogenic amino acids by removing background noise. To simplify 13C-MFA of different prokaryotic species, the software provides several metabolic network templates, including those for chemoheterotrophic bacteria and mixotrophic cyanobacteria. Users can modify the network and constraints, and then analyze the microbial carbon and energy metabolisms of various carbon substrates (e.g., glucose, pyruvate/lactate, acetate, xylose, and glycerol). WUFlux also offers several ways of visualizing the flux results with respect to the constructed network. To validate our model’s applicability, we have compared and discussed the flux results obtained from WUFlux and other MFA software. We have also illustrated how model constraints of cofactor and ATP balances influence fluxome results. Conclusion Open-source software for 13C-MFA, WUFlux, with a user-friendly interface and easy-to-modify templates, is now available at http://www.13cmfa.org /or ( http://tang.eece.wustl.edu/ToolDevelopment.htm ). We will continue documenting curated models of non-model microbial species and improving WUFlux performance.

With recent adoption of wireless sensor-actuator networks (WSANs) in industrial automation, industrial wireless control systems have emerged as a frontier of cyber-physical systems. Despite their success in industrial monitoring applications, existing WSAN technologies face significant challenges in supporting control systems due to their lack of real-time performance and dynamic wireless conditions in industrial plants. This article reviews a series of recent advances in real-time WSANs for industrial control systems: 1) real-time scheduling algorithms and analyses for WSANs; 2) implementation and experimentation of industrial WSAN protocols; 3) cyber-physical codesign of wireless control systems that integrate wireless and control designs; and 4) a wireless cyber-physical simulator for codesign and evaluation of wireless control systems. This article concludes by highlighting research directions in industrial cyber-physical systems.

Algorithmic reductions are one of the corner stones of theoretical computer science. Surprisingly, to-date, they have only played a limited role in machine learning. In this paper we introduce a formal and practical reduction between two of the most widely used machine learning algorithms: from the Elastic Net (and the Lasso as a special case) to the Support Vector Machine. First, we derive the reduction and summarize it in only 11 lines of MATLAB. Then, we demonstrate its high impact potential by translating recent advances in parallelizing SVM solvers directly to the Elastic Net. The resulting algorithm is a parallel solver for the Elastic Net (and Lasso) that naturally utilizes GPU and multi-core CPUs. We evaluate it on twelve real world data sets, and show that it yields identical results as the popular (and highly optimized) glmnet implementation but is up-to two orders of magnitude faster.

Most existing submodular maximization algorithms provide theoretical guarantees with approximation bounds. However, in many cases, users may be interested in an anytime algorithm that can offer a flexible trade-off between computation time and optimality guarantees. In this paper, we propose a filtered search (FS) framework that allows the user to set an arbitrary approximation bound guarantee with a “tunable knob”, from 0 (arbitrarily bad) to 1 (globally optimal). FS naturally handles monotone and non-monotone functions as well as unconstrained problems and problems with cardinality, matroid, and knapsack constraints. Further, it can also be applied to (non-negative) non-submodular functions and still gives controllable approximation bounds based on their submodularity ratio. Finally, FS encompasses the greedy algorithm as a special case. Our framework is based on theory in A* search, but is substantially more efficient because it only requires heuristics that are critically admissible (CA) rather than admissible—a condition that gives more effective pruning and is substantially easier to implement.

As deep nets are increasingly used in applications suited for mobile devices, a fundamental dilemma becomes apparent: the trend in deep learning is to grow models to absorb ever-increasing data set sizes; however mobile devices are designed with very little memory and cannot store such large models. We present a novel network architecture, HashedNets, that exploits inherent redundancy in neural networks to achieve drastic reductions in model sizes. HashedNets uses a low-cost hash function to randomly group connection weights into hash buckets, and all connections within the same hash bucket share a single parameter value. These parameters are tuned to adjust to the HashedNets weight sharing architecture with standard backprop during training. Our hashing procedure introduces no additional memory overhead, and we demonstrate on several benchmark data sets that HashedNets shrink the storage requirements of neural networks substantially while mostly preserving generalization performance.

Additive tree models (ATMs) are widely used for data mining and machine learning. Important examples of ATMs include random forest, adaboost (with decision trees as weak learners), and gradient boosted trees, and they are often referred to as the best off-the-shelf classifiers. Though capable of attaining high accuracy, ATMs are not well interpretable in the sense that they do not provide actionable knowledge for a given instance. This greatly limits the potential of ATMs on many applications such as medical prediction and business intelligence, where practitioners need suggestions on actions that can lead to desirable outcomes with minimum costs.

Wireless sensor-actuator networks are gaining ground as the communication infrastructure for process monitoring and control. Industrial applications demand a high degree of reliability and real-time guarantees in communication. Because wireless communication is susceptible to transmission failures in industrial environments, industrial wireless standards such as WirelessHART adopt reliable graph routing to handle transmission failures through retransmissions and route diversity. While these mechanisms are critical for reliable communication, they introduce substantial challenges in analyzing the schedulability of real-time flows. This paper presents the first worst-case end-to-end delay analysis for periodic real-time flows under reliable graph routing. The proposed analysis can be used to quickly assess the schedulability of real-time flows with stringent requirements on both reliability and latency. We have evaluated our schedulability analysis against experimental results on a wireless testbed of 69 nodes as well as simulations. Both experimental results and simulations show that our delay bounds are safe and enable effective schedulability tests under reliable graph routing.

WirelessHART is a new standard specifically designed for real-time and reliable communication between sensor and actuator devices for industrial process monitoring and control applications. End-to-end communication delay analysis for WirelessHART networks is required to determine the schedulability of real-time data flows from sensors to actuators for the purpose of acceptance test or workload adjustment in response to network dynamics. In this paper, we consider a network model based on WirelessHART, and map the scheduling of real-time periodic data flows in the network to real-time multiprocessor scheduling. We then exploit the response time analysis for multiprocessor scheduling and propose a novel method for the delay analysis that establishes an upper bound of the end-to-end communication delay of each real-time flow in the network. Simulation studies based on both random topologies and real network topologies of a$74$-node physical wireless sensor network testbed demonstrate that our analysis provides safe and reasonably tight upper bounds of the end-to-end delays of real-time flows, and hence enables effective schedulability tests for WirelessHART networks.

Metric learning, the task of learning a good distance metric, is a key problem in machine learning with ample applications. This paper introduces a novel framework for nonlinear metric learning, called kernel density metric learning (KDML), which is easy to use and provides nonlinear, probability-based distance measures. KDML constructs a direct nonlinear mapping from the original input space into a feature space based on kernel density estimation. The nonlinear mapping in KDML embodies established distance measures between probability density functions, and leads to accurate classification on datasets for which existing linear metric learning methods would fail. It addresses the severe challenge to distance-based classifiers when features are from heterogeneous domains and, as a result, the Euclidean or Mahalanobis distance between original feature vectors is not meaningful. We also propose two ways to determine the kernel bandwidths, including an adaptive local scaling approach and an integrated optimization algorithm that learns the Mahalanobis matrix and kernel bandwidths together. KDML is a general framework that can be combined with any existing metric learning algorithm. As concrete examples, we combine KDML with two leading metric learning algorithms, large margin nearest neighbors (LMNN) and neighborhood component analysis (NCA). KDML can naturally handle not only numerical features, but also categorical ones, which is rarely found in previous metric learning algorithms. Extensive experimental results on various datasets show that KDML significantly improves existing metric learning algorithms in terms of classification accuracy.

During the past decade, machine learning algorithms have become commonplace in large-scale real-world industrial applications. In these settings, the computation time to train and test machine learning algorithms is a key consideration. At training-time the algorithms must scale to very large data set sizes.At testing-time, the cost of feature extraction can dominate the CPU runtime. Recently, a promising method was proposed to account for the feature extraction cost at testing time, called Cost-sensitive Tree of Classifiers (CSTC). Although the CSTC problem is NP-hard, the authors suggest an approximation through a mixed-norm relaxation across many classifiers. This relaxation is slow to train and requires involved optimization hyperparameter tuning. We propose a different relaxation using approximate submodularity, called Approximately Submodular Tree of Classifiers (ASTC). ASTC is much simpler to implement, yields equivalent results but requires no optimization hyperparameter tuning and is up to two orders of magnitude faster to train.

The largest source of energy consumption in buildings is heating, ventilation, and air conditioning (HVAC). For an HVAC system to provide comfort and minimize energy consumption, it is crucial to understand the spatiotemporal thermal dynamics, especially in large open spaces. To optimize HVAC control, it is important to establish accurate dynamic thermal models. For this purpose, we constructed a real-world test bed by instrumenting an HVAC-controller auditorium using multiple types of sensors. Based on the dataset, we develop and evaluate a novel data-driven approach to model the complex thermal dynamics in a large space through a combination of data clustering and system identification techniques. Real-world data shows that our approach achieves low estimation errors. Our modeling approach therefore provides a practical foundation for HVAC control and optimization for large open spaces.

Industry is adopting Wireless Sensor-Actuator Networks (WSANs) as the communication infrastructure for process control applications. To meet the stringent real-time performance requirements of control systems, there is a critical need for fast end-to-end delay analysis for real-time flows that can be used for online admission control. This paper presents a new end-to-end delay analysis for periodic flows whose transmissions are scheduled based on the Earliest Deadline First (EDF) policy. Our analysis comprises novel techniques to bound the communication delays caused by channel contention and transmission conflicts in a WSAN. Furthermore, we propose a technique to reduce the pessimism in admission control by iteratively tightening the delay bounds for flows with short deadlines. Experiments on a WSAN testbed and simulations demonstrate the effectiveness of our analysis for online admission control of real-time flows.

In this paper, we propose a novel supervised learning method, Fast Flux Discriminant (FFD), for large-scale nonlinear classification. Compared with other existing methods, FFD has unmatched advantages, as it attains the efficiency and interpretability of linear models as well as the accuracy of nonlinear models. It is also sparse and naturally handles mixed data types. It works by decomposing the kernel density estimation in the entire feature space into selected low-dimensional subspaces. Since there are many possible subspaces, we propose a submodular optimization framework for subspace selection. The selected subspace predictions are then transformed to new features on which a linear model can be learned. Besides, since the transformed features naturally expect non-negative weights, we only require smooth optimization even with the L1 regularization. Unlike other nonlinear models such as kernel methods, the FFD model is interpretable as it gives importance weights on the original features. Its training and testing are also much faster than traditional kernel models. We carry out extensive empirical studies on real-world datasets and show that the proposed model achieves state-of-the-art classification results with sparsity, interpretability, and exceptional scalability. Our model can be learned in minutes on datasets with millions of samples, for which most existing nonlinear methods will be prohibitively expensive in space and time.

With the advent of industrial standards such as WirelessHART, process industries are now gravitating towards wireless control systems. Due to limited bandwidth in a wireless network shared by multiple control loops, it is critical to optimize the overall control performance. In this article, we address the scheduling-control co-design problem of determining the optimal sampling rates of feedback control loops sharing a WirelessHART network. The objective is to minimize the overall control cost while ensuring that all data flows meet their end-to-end deadlines. The resulting constrained optimization based on existing delay bounds for WirelessHART networks is challenging since it is nondifferentiable, nonlinear, and not in closed-form. We propose four methods to solve this problem. First, we present a subgradient method for rate selection. Second, we propose a greedy heuristic that usually achieves low control cost while significantly reducing the execution time. Third, we propose a global constrained optimization algorithm using a simulated annealing (SA) based penalty method. We study SA method under both constant factor penalty and adaptive penalty. Finally, we formulate rate selection as a differentiable convex optimization problem that provides a quick solution through a convex optimization technique. This is based on a new delay bound that is convex and differentiable, and hence simplifies the optimization problem. We study both the gradient descent method and the interior point method to solve it. We evaluate all methods through simulations based on topologies of a 74-node wireless sensor network testbed. The subgradient method is disposed to incur the longest execution time as well as the highest control cost among all methods. Among the SA-based constant penalty method, the greedy heuristic, and the gradient descent method, the first two represent the opposite ends of the tradeoff between control cost and execution time, while the third one hits the balance between the two. We further observe that the SA based adaptive penalty method is superior to the constant penalty method, and that the interior point method is superior to the gradient method. Thus, the interior point method and the SA-based adaptive penalty method are the two most effective approaches for rate selection. While both methods are competitive against each other in terms of control cost, the interior point method is significantly faster than the penalty method. As a result, the interior point method upon convex relaxation is more suitable for online rate adaptation than the SA based adaptive penalty method due to their significant difference in run-time efficiency.

Interference between concurrent transmissions can cause severe performance degradation in wireless sensor networks (WSNs). While multiple channels available in WSN technology such as IEEE 802.15.4 can be exploited to mitigate interference, channel allocation can have a significant impact on the performance of multi-channel communication. This paper proposes a set of distributed protocols for channel allocation in WSNs with theoretical bounds. We first consider the problem of minimizing the number of channels needed to remove interference in a WSN, and propose both receiver-based and link-based distributed channel allocation protocols. Then, for WSNs with an insufficient number of channels, we formulate a fair channel allocation problem whose objective is to minimize the maximum interference (MinMax) experienced by any transmission link in the network. We prove that MinMax channel allocation is NP-hard, and propose a distributed link-based MinMax channel allocation protocol. Finally, we propose a distributed protocol for link scheduling based on MinMax channel allocation that creates a conflict-free schedule for transmissions. The proposed decentralized protocols are efficient, scalable, and adaptive to channel condition and network dynamics. Simulations based on the topologies and data traces collected from a WSN testbed of 74 TelosB motes have shown that our channel allocation protocols significantly outperform a state-of-the-art channel allocation protocol.

Web service composition (WSC) is the task of combining a chain of connected single services together to create a more complex and value-added composite service. Quality of service (QoS) has been mostly applied to represent nonfunctional properties of web services and differentiate those with the same functionality. Many research has been done on QoS-aware service composition, as it significantly affects the quality of a composite service. However, existing methods are restricted to predefined workflows, which can incur a couple of limitations, including the lack of guarantee for the optimality on overall QoS and for the completeness of finding a composite service solution. In this paper, instead of predefining a workflow model for service composition, we propose a novel planning-based approach that can automatically convert a QoS-aware composition task to a planning problem with temporal and numerical features. Furthermore, we use state-of-the-art planners, including an existing one and a self-developed one, to handle complex temporal planning problems with logical reasoning and numerical optimization. Our approach can find a composite service graph with the optimal overall QoS value while satisfying multiple global QoS constraints. We implement a prototype system and conduct extensive experiments on large web service repositories. The experimental results show that our proposed approach largely outperforms existing ones in terms of solution quality and is efficient enough for practical deployment.

Recently, a Euclidean heuristic (EH) has been proposed for A* search. EH exploits manifold learning methods to construct an embedding of the state space graph, and derives an admissible heuristic distance between two states from the Euclidean distance between their respective embedded points. EH has shown good performance and memory efficiency in comparison to other existing heuristics such as differential heuristics. However, its potential has not been fully explored. In this paper, we propose a number of techniques that can significantly improve the quality of EH. We propose a goal-oriented manifold learning scheme that optimizes the Euclidean distance to goals in the embedding while maintaining admissibility and consistency. We also propose a state heuristic enhancement technique to reduce the gap between heuristic and true distances. The enhanced heuristic is admissible but no longer consistent. We then employ a modified search algorithm, known as B' algorithm, that achieves optimality with inconsistent heuristics using consistency check and propagation. We demonstrate the effectiveness of the above techniques and report un-matched reduction in search costs across several non-trivial benchmark search problems.

This paper introduces a supervised metric learning algorithm, called kernel density metric learning (KDML), which is easy to use and provides nonlinear, probability-based distance measures. KDML constructs a direct nonlinear mapping from the original input space into a feature space based on kernel density estimation. The nonlinear mapping in KDML embodies established distance measures between probability density functions, and leads to correct classification on datasets for which linear metric learning methods would fail. It addresses the severe challenge to kNN when features are from heterogeneous domains and, as a result, the Euclidean or Mahalanobis distance between original feature vectors is not meaningful. Existing metric learning algorithms can then be applied to the KDML features. We also propose an integrated optimization algorithm that learns not only the Mahalanobis matrix but also kernel bandwidths, the only hyper-parameters in the nonlinear mapping. KDML can naturally handle not only numerical features, but also categorical ones, which is rarely found in previous metric learning algorithms. Extensive experimental results on various datasets show that KDML significantly improves existing metric learning algorithms in terms of kNN classification accuracy.

In this paper we introduce Maximum Variance Correction (MVC), which finds large-scale feasible solutions to Maximum Variance Unfolding (MVU) by post-processing embeddings from any manifold learning algorithm. It increases the scale of MVU embeddings by several orders of magnitude and is naturally parallel. This unprecedented scalability opens up new avenues of applications for manifold learning, in particular the use of MVU embeddings as effective heuristics to speed-up A* search (Rayner et al. 2011). We demonstrate that MVC embeddings lead to un-matched reductions in search time across several non-trivial A* benchmark search problems and bridge the gap between the manifold learning literature and one of its most promising high impact applications.

This paper introduces a nonlinear logistic regression model for classification. The main idea is to map the data to a feature space based on kernel density estimation. A discriminative model is then learned to optimize the feature weights as well as the bandwidth of a Nadaraya-Watson kernel density estimator. We then propose a hierarchical optimization algorithm for learning the coefficients and kernel bandwidths in an integrated way. Compared to other nonlinear models such as kernel logistic regression (KLR) and SVM, our approach is far more efficient since it solves an optimization problem with a much smaller size. Two other major advantages are that it can cope with categorical attributes in a unified fashion and naturally handle multi-class problems. Moveover, our approach inherits from logistic regression good interpretability of the model, which is important for clinical applications but not offered by KLR and SVM. Extensive results on real datasets, including a clinical prediction application currently under deployment in a major hospital, show that our approach not only achieves superior classification accuracy, but also drastically reduces the computing time as compared to other leading methods.

Streaming data programs are an important class of applications, for which queueing network models are frequently available. While the design space can be large, decomposition techniques can be effective at design space reduction. We introduce two decomposition techniques called convex decomposition and unchaining and present implications for a biosequence search application.

Plan recognition is a ubiquitous task in artificial intelligence and pervasive computing research. The multigoal recognition problem presents a major challenge in the real world of plan recognition. Users often pursue several goals in a concurrent and interleaving manner, where the pursuit of goals may spread over different parts of an activity sequence and may be pursued in parallel. Existing approaches for multigoal problems are probabilistic approaches. They all assume the existence of plan libraries, which require a lot of human efforts in predicting and formalizing plans and may be impractical in many cases. In this paper, we present a novel logic-based approach to solve the multigoal recognition problem efficiently, without the need of plan libraries, using a state-of-the-art heuristic search planner LAMA. In particular, we first propose the formulation of a multigoal recognition problem based on automated planning. Then we present a bilevel probabilistic plan recognition approach that deals with both concurrent and interleaving goals from observed activity sequences. Experimental results over several domains show that our method has great flexibility and scalability.

Complex features, such as temporal dependencies and numerical cost constraints, are hallmarks of real-world planning problems. In this article, we consider the challenging problem of cost-sensitive temporally expressive (CSTE) planning, which requires concurrency of durative actions and optimization of action costs. We first propose a scheme to translate a CSTE planning problem to a minimum cost (MinCost) satisfiability (SAT) problem and to integrate with a relaxed parallel planning semantics for handling true temporal expressiveness. Our scheme finds solution plans that optimize temporal makespan, and also minimize total action costs at the optimal makespan. We propose two approaches for solving MinCost SAT. The first is based on a transformation of a MinCost SAT problem to a weighted partial Max-SAT (WPMax-SAT), and the second, called BB-CDCL, is an integration of the branch-and-bound technique and the conflict driven clause learning (CDCL) method. We also develop a CSTE customized variable branching scheme for BB-CDCL which can significantly improve the search efficiency. Our experiments on the existing CSTE benchmark domains show that our planner compares favorably to the state-of-the-art temporally expressive planners in both efficiency and quality.

Ranking is an important problem in various applications, such as Information Retrieval (IR), natural language processing, computational biology, and social sciences. Many ranking approaches have been proposed to rank objects according to their degrees of relevance or importance. Beyond these two goals, diversity has also been recognized as a crucial criterion in ranking. Top ranked results are expected to convey as little redundant information as possible, and cover as many aspects as possible. However, existing ranking approaches either take no account of diversity, or handle it separately with some heuristics. In this paper, we introduce a novel approach, Manifold Ranking with Sink Points (MRSPs), to address diversity as well as relevance and importance in ranking. Specifically, our approach uses a manifold ranking process over the data manifold, which can naturally find the most relevant and important data objects. Meanwhile, by turning ranked objects into sink points on data manifold, we can effectively prevent redundant objects from receiving a high rank. MRSP not only shows a nice convergence property, but also has an interesting and satisfying optimization explanation. We applied MRSP on two application tasks, update summarization and query recommendation, where diversity is of great concern in ranking. Experimental results on both tasks present a strong empirical performance of MRSP as compared to existing ranking approaches.

Recent studies have shown that a significant portion of the total energy consumption of many data centers is caused by the inefficient operation of their cooling systems. Without effective thermal monitoring with accurate location information, the cooling systems often use unnecessarily low temperature set points to overcool the entire room, resulting in excessive energy consumption. Sensor network technology has recently been adopted for data-center thermal monitoring because of its nonintrusive nature for the already complex data center facilities and robustness to instantaneous CPU or disk activities. However, existing solutions place sensors in a simplistic way without considering the thermal dynamics in data centers, resulting in unnecessarily degraded hot server detection probability. In this paper, we first formulate the problems of sensor placement for hot server detection in a data center as constrained optimization problems in two different scenarios. We then propose a novel placement scheme based on computational fluid dynamics (CFD) to take various factors, such as cooling systems and server layout, as inputs to analyze the thermal conditions of the data center. Based on the CFD analysis in various server overheating scenarios, we apply data fusion and advanced optimization techniques to find a near-optimal sensor placement solution, such that the probability of detecting hot servers is significantly improved. Our empirical results in a real server room demonstrate the detection performance of our placement solution. Extensive simulation results in a large-scale data center with 32 racks also show that the proposed solution outperforms several commonly used placement solutions in terms of detection probability.

For Web service composition, choreography has recently received great attention and demonstrated a few key advantages over orchestration such as distributed control, fairness, data efficiency, and scalability. Automated design of choreography plans, especially distributed plans for multiple roles, is more complex and has not been studied before. Existing work requires manual generation assisted by model checking. In this paper, we propose a novel planning-based approach that can automatically convert a given composition task to a distributed choreography specification. Although planning has been used for orchestration, it is difficult to use planning for choreography, as it involves decentralized control, concurrent workflows, and contingency. We propose a few novel techniques, including compilation of contingencies, dependency graph analysis, and communication control, to handle these characteristics using planning. We theoretically show the correctness of this approach and empirically evaluate its practicability.

We tackle the problem of answering maximum probabilistic top-k tuple set queries. We use a sliding-window model on uncertain data streams and present an efficient algorithm for processing sliding-window queries on uncertain streams. In each sliding window, the algorithm selects the k tuples with the highest probabilities from sets of different numbers of the tuples with the highest scores. Then, the algorithm computes existential probability of the top-k tuples, and chooses the set with the highest probability as the top-k query result. We theoretically prove the correctness of the algorithm. Our experimental results show that our algorithm requires lower time and space complexity than other existing algorithms.

Streaming data applications are frequently pipelined and deployed on application-specific systems to meet performance requirements and resource constraints. Typically, there are several design parameters in the algorithms and architectures used that impact the application performance as well as resource utilization. Efficient exploration of this design space is the goal of this research. When using architecturally diverse systems to accelerate streaming applications, the design search space is often complex. The search complexity can be reduced by recognizing and exploiting convex variables to perform convex decomposition, preserving optimality even in the context of a non-convex optimization problem. This paper presents a formal treatment of convex variables and convex decomposition, including a proof that the technique preserves optimality. It also quantifies the reduction in the search space that is realized, at minimum equal to the number of distinct values of the convex variable and potentially much higher.

Wireless sensor networks are evolving from single-application platforms towards an integrated infrastructure shared by multiple applications. Given the resource constraints of sensor nodes, it is important to optimize the allocation of applications to maximize the overall Quality of Monitoring (QoM). Recent solutions to this challenging application allocation problem are centralized in nature, limiting their scalability and robustness against network failures and dynamics. This paper presents a distributed game-theoretic approach to application allocation in shared sensor networks. We first transform the optimal application allocation problem to a submodular game and then develop a decentralized algorithm that only employs localized interactions among neighboring nodes. We prove that the network can converge to a pure strategy Nash equilibrium with an approximation bound of 1=2. Simulations based on three real-world datasets demonstrate that our algorithm is competitive against a state-of-the-art centralized algorithm in terms of QoM.

Clinical study found that early detection and intervention are essential for preventing clinical deterioration in patients, for patients both in intensive care units (ICU) as well as in general wards but under real-time data sensing (RDS). In this paper, we develop an integrated data mining approach to give early deterioration warnings for patients under real-time monitoring in ICU and RDS.

With the advent of industrial standards such as Wireless Hart, process industries are now gravitating towards wireless control systems. Due to limited bandwidth in a wireless network shared by multiple control loops, it is critical to optimize the overall control performance. In this paper, we address the scheduling-control co-design problem of determining the optimal sampling rates of feedback control loops sharing a Wireless Hart network. The objective is to minimize the overall control cost while ensuring that all data flows meet their end-to-end deadlines. The resulting constrained optimization based on existing delay bounds for Wireless Hart networks is challenging since it is non-differentiable, non-linear, and not in closed-form. We propose four methods to solve this problem. First, we present a sub gradient method for rate selection. Second, we propose a greedy heuristic that usually achieves low control cost while significantly reducing the execution time. Third, we propose a global constrained optimization algorithm using a simulated annealing (SA) based penalty method. Finally, we formulate rate selection as a differentiable convex optimization problem that provides a closed-form solution through a gradient descent method. This is based on a new delay bound that is convex and differentiable, and hence simplifies the optimization problem. We evaluate all methods through simulations based on topologies of a 74-node wireless sensor network testbed. Surprisingly, the sub gradient method is disposed to incur the longest execution time as well as the highest control cost among all methods. SA and the greedy heuristic represent the opposite ends of the trade off between control cost and execution time, while the gradient descent method hits the balance between the two.

Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS+ formalism. The new scheme exploits the structural information in SAS+, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.

Shewanella oneidensis MR-1 sequentially utilizes lactate and its waste products (pyruvate and acetate) during batch culture. To decipher MR-1 metabolism, we integrated genome-scale flux balance analysis (FBA) into a multiple-substrate Monod model to perform the dynamic flux balance analysis (dFBA). The dFBA employed a static optimization approach (SOA) by dividing the batch time into small intervals (i.e., ∼400 mini-FBAs), then the Monod model provided time-dependent inflow/outflow fluxes to constrain the mini-FBAs to profile the pseudo-steady-state fluxes in each time interval. The mini-FBAs used a dual-objective function (a weighted combination of "maximizing growth rate" and "minimizing overall flux") to capture trade-offs between optimal growth and minimal enzyme usage. By fitting the experimental data, a bi-level optimization of dFBA revealed that the optimal weight in the dual-objective function was time-dependent: the objective function was constant in the early growth stage, while the functional weight of minimal enzyme usage increased significantly when lactate became scarce. The dFBA profiled biologically meaningful dynamic MR-1 metabolisms: 1. the oxidative TCA cycle fluxes increased initially and then decreased in the late growth stage; 2. fluxes in the pentose phosphate pathway and gluconeogenesis were stable in the exponential growth period; and 3. the glyoxylate shunt was up-regulated when acetate became the main carbon source for MR-1 growth.

Many embedded and scientific applications are pipelined (i.e., streaming) and deployed on application-specific systems. Typically, there are several design parameters in the algorithms and architectures used that impact the tradeoff between different metrics of application performance as well as resource utilization. Efficient automatic exploration of this design space is the goal of our research. We present a global optimization framework comprising a domain-specific variation of branch-and-bound that reduces search complexity by exploiting the topology of the application's pipelining. We exploit the topological information to discover decomposability through the canonical Jordan block form. The reduction in search complexity for four real-world streaming applications (drawn from the literature) is significant, ranging from a million-fold reduction in search space size to a reduction factor of 10 billion. All four optimization problems are thereby solvable in reasonable time.

Topical classification of user queries is critical for general-purpose web search systems. It is also a challenging task, due to the sparsity of query terms and the lack of labeled queries. On the other hand, search contexts embedded in query sessions and unlabeled queries free on the web have not been fully utilized in most query classification systems. In this work, we leverage these information to improve query classification accuracy.

Cloud computing is emerging as a prominent computing model. It provides a low-cost, highly accessible alternative to other traditional high-performance computing platforms. It also has many other benefits such as high availability, scalability, elasticity, and free of maintenance. Given these attractive features, it is very desirable if automated planning can exploit the large, affordable computational power of cloud computing. However, the latency in inter-process communication in cloud computing makes most existing parallel planning algorithms unsuitable for cloud computing. In this paper, we propose a portfolio stochastic search framework that takes advantage of and is suitable for cloud computing. We first study the running time distribution of Monte-Carlo Random Walk (MRW) search, a stochastic planning algorithm, and show that the running time distribution usually has remarkable variability. Then, we propose a portfolio search algorithm that is suitable for cloud computing, which typically has abundant computing cores but high communication latency between cores. Further, we introduce an enhanced portfolio with multiple parameter settings to improve the efficiency of the algorithm. We implement the portfolio search algorithm in both a local cloud and the Windows Azure cloud. Experimental results show that our algorithm achieves good, in many cases super linear, speedup in the cloud platforms. Moreover, our algorithm greatly reduces the running time variance of the stochastic search and improves the solution quality. We also show that our scheme is economically sensible and robust under processor failures.

WirelessHART is a new wireless sensor-actuator network standard specifically developed for process industries. A key challenge faced by WirelessHART networks is to meet the stringent real-time communication requirements imposed by process monitoring and control applications. Fixed-priority scheduling, a popular scheduling policy for real-time networks, has recently been shown to be an effective real-time transmission scheduling policy in WirelessHART networks. Priority assignment has a major impact on the schedulability of real-time flows in these networks. This paper investigates the open problem of priority assignment for periodic real-time flows in a WirelessHART network. We first propose an optimal priority assignment algorithm based on local search for any given worst case delay analysis. We then propose an efficient heuristic search algorithm for priority assignment. We also identify special cases where the heuristic search is optimal. Simulations based on random networks and the real topology of a physical sensor network test bed showed that the heuristic search algorithm achieved near optimal performance in terms of schedulability, while significantly outperforming traditional priority assignment policies for real-time systems.

Recent studies have shown that a significant portion of the total energy consumption of many data centers is caused by the inefficient operation of their cooling systems. Without effective thermal monitoring with accurate location information, the cooling systems often use unnecessarily low temperature set points to over cool the entire room, resulting in excessive energy consumption. Sensor network technology has recently been adopted for data-center thermal monitoring because of its non-intrusive nature for the already complex data center facilities and robustness to instantaneous CPU or disk activities. However, existing solutions place sensors in a simplistic way without considering the thermal dynamics in data centers, resulting in unnecessarily degraded hot server detection probability. In this paper, we first formulate the problem of sensor placement for hot server detection in a data center as a constrained optimization problem. We then propose a novel placement scheme based on Computational Fluid Dynamics (CFD) to take various factors, such as cooling systems and server layout, as inputs to analyze the thermal conditions of the data center. Based on the CFD analysis in various server overheating scenarios, we apply data fusion and advanced optimization techniques to find a near-optimal sensor placement solution, such that the probability of detecting hot servers is significantly improved. Our empirical results in a real server room demonstrate the detection performance of our placement solution. Extensive simulation results also show that the proposed solution outperforms a commonly used placement solution in terms of detection probability.

The WirelessHART standard has been specifically designed for real-time communication between sensor and actuator devices for industrial process monitoring and control. End-to-end communication delay analysis for WirelessHART networks is required for acceptance test of real-time data flows from sensors to actuators and for workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We, then, exploit the response time analysis for multiprocessor scheduling and propose a novel method for the end-to-end delay analysis of the real-time flows that are scheduled using a fixed priority scheduling policy in a WirelessHART network. Simulations based on both random topologies and real network topologies of a physical testbed demonstrate the efficacy of our end-to-end delay analysis in terms of acceptance ratio under various fixed priority scheduling policies.

Mission-critical target detection imposes stringent performance requirements for wireless sensor networks, such as high detection probabilities and low false alarm rates. Data fusion has been shown as an effective technique for improving system detection performance by enabling efficient collaboration among sensors with limited sensing capability. Due to the high cost of network deployment, it is desirable to place sensors at optimal locations to achieve maximum detection performance. However, for sensor networks employing data fusion, optimal sensor placement is a nonlinear and nonconvex optimization problem with prohibitively high computational complexity. In this paper, we present fast sensor placement algorithms based on a probabilistic data fusion model. Simulation results show that our algorithms can meet the desired detection performance with a small number of sensors while achieving up to seven-fold speedup over the optimal algorithm.

Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from the STRIPS formalism. We introduce a novel SAT encoding scheme based on the SAS+ formalism. It exploits the structural information in the SAS+ formalism, resulting in more compact SAT instances and reducing the number of clauses by up to 50 fold. Our results show that this encoding scheme improves upon the STRIPS-based encoding, in terms of both time and memory efficiency.

Recent years have witnessed the emergence of shared sensor networks as integrated infrastructure for multiple applications. It is important to allocate multiple applications in a shared sensor network, in order to maximize the overall Quality of Monitoring (QoM) subject to resource constraints (e.g., in terms of memory and network bandwidth). The resulting constrained optimization problem is a difficult and open problem since it is discrete, nonlinear, and not in closed-form. This paper makes several important contributions towards optimal multi-application allocation in shared sensor networks. (1) We formulate the optimal application allocation problem for a common class of distributed sensing applications whose QoM can be modeled as variance reduction functions. (2) We prove key theoretical properties of the optimization problem, including the monotonicity and submodularity of the variance reduction functions and the multiple knapsack structure of constraints; (3) By exploiting these properties, we propose a local search algorithm, which is efficient and has a good approximation bound, for application allocation in shared sensor networks. Simulations based on both real-world datasets and randomly generated networks demonstrate that our algorithm is competitive against simulated annealing in term of QoM, with up to three orders of magnitude reduction in execution times, making it a practical solution towards multi-application allocation in shared sensor networks.

WirelessHART is an open wireless sensor-actuator network standard for industrial process monitoring and control that requires real-time data communication between sensor and actuator devices. Salient features of a WirelessHART network include a centralized network management architecture, multi-channel TDMA transmission, redundant routes, and avoidance of spatial reuse of channels for enhanced reliability and real-time performance. This paper makes several key contributions to real-time transmission scheduling in WirelessHART networks: (1) formulation of the end-to-end real-time transmission scheduling problem based on the characteristics of WirelessHART, (2) proof of NP-hardness of the problem, (3) an optimal branch-and-bound scheduling algorithm based on a necessary condition for schedulability, and (4) an efficient and practical heuristic-based scheduling algorithm called Conflict-aware Least Laxity First (C-LLF). Extensive simulations based on both random topologies and real network topologies of a physical testbed demonstrate that C-LLF is highly effective in meeting end-to-end deadlines in WirelessHART networks, and significantly outperforms common real-time scheduling policies.

research-article Share on Preface to special issue on applications of automated planning Author: Yixin Chen Washington University in St. Louis Washington University in St. LouisView Profile Authors Info & Claims ACM Transactions on Intelligent Systems and TechnologyVolume 1Issue 2Article No.: 9pp 1–3https://doi.org/10.1145/1869397.1869398Published:03 December 2010Publication History 0citation255DownloadsMetricsTotal Citations0Total Downloads255Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Patients undergoing thoracic radiation therapy can develop radiation pneumonitis (RP), a potentially fatal inflammation of the lungs. Support vector machines (SVMs), a statistical machine learning method, have recently been used to build binary-outcome RP prediction models with promising results. In this work, we (1) introduce a feature-ranking selection step to limit complexity in ensemble SVM models (2) show that ensembles of SVMs provide a statistically significant performance improvement in the area under the cross-validated receiver operating curve and (3) apply Platt's tuning to generate probability estimates from the component SVMs in order to augment clinical relevance.

Gene prediction is one of the first and most important steps in understanding the genome of a species, and different approaches haven been proposed. In 2007, a de novo gene predictor, called CONTRAST, based on Conditional Random Fields (CRFs) is introduced, and proved to substantially outperform previous predictors. However, the oversize feature set used in the model has posed several issues, like overfitting problem and excessive computational demand. To resolve these issues, we did a thorough survey of two existing feature selection methods for CRFs, namely the gain-based and gradient-based methods, and applied the later one to CONTRAST. The results show that with the gradient-based feature selection scheme, we are able to achieve comparable or even better prediction accuracy on testing data, using only a very small fraction of the features from the candidate pool. The feature selection method also helps researchers better understand the underlying structure of the genomic sequences, further provides insights of the function and evolutionary dynamics of genomes.

Conditional random fields(CRFs) are a class of undirected graphical models which have been widely used for classifying and labeling sequence data. The training of CRFs is typically formulated as an unconstrained optimization problem that maximizes the conditional likelihood. However, maximum likelihood training is prone to overfitting. To address this issue, we propose a novel constrained nonlinear optimization formulation in which the prediction accuracy of cross-validation sets are included as constraints. Instead of requiring multiple passes of training, the constrained formulation allows the cross-validation be handled in one pass of constrained optimization.

Clustering real-time stream data is an important and challenging problem. Existing algorithms such as CluStream are based on the k -means algorithm. These clustering algorithms have difficulties finding clusters of arbitrary shapes and handling outliers. Further, they require the knowledge of k and user-specified time window. To address these issues, this article proposes D-Stream , a framework for clustering stream data using a density-based approach. Our algorithm uses an online component that maps each input data record into a grid and an offline component that computes the grid density and clusters the grids based on the density. The algorithm adopts a density decaying technique to capture the dynamic changes of a data stream and a attraction-based mechanism to accurately generate cluster boundaries. Exploiting the intricate relationships among the decay factor, attraction, data density, and cluster structure, our algorithm can efficiently and effectively generate and adjust the clusters in real time. Further, a theoretically sound technique is developed to detect and remove sporadic grids mapped by outliers in order to dramatically improve the space and time efficiency of the system. The technique makes high-speed data stream clustering feasible without degrading the clustering quality. The experimental results show that our algorithm has superior quality and efficiency, can find clusters of arbitrary shapes, and can accurately recognize the evolving behaviors of real-time data streams.

Logistic regression is an important technique for analyzing and predicting data with categorical attributes. In this paper, We consider supporting online analytical processing (OLAP) of logistic regression analysis for multi-dimensional data in a data cube where it is expensive in time and space to build logistic regression models for each cell from the raw data. We propose a novel scheme to compress the data in such a way that we can reconstruct logistic regression models to answer any OLAP query without accessing the raw data. Based on a first-order approximation to the maximum likelihood estimating equations, we develop a compression scheme that compresses each base cell into a small compressed data block with essential information to support the aggregation of logistic regression models. Aggregation formulae for deriving high-level logistic regression models from lower level component cells are given. We prove that the compression is nearly lossless in the sense that the aggregated estimator deviates from the true model by an error that is bounded and approaches to zero when the data size increases. The results show that the proposed compression and aggregation scheme can make feasible OLAP of logistic regression in a data cube. Further, it supports real-time logistic regression analysis of stream data, which can only be scanned once and cannot be permanently retained. Experimental results validate our theoretical analysis and demonstrate that our method can dramatically save time and space costs with almost no degradation of the modeling accuracy.

A major challenge for learning Bayesian networks is the complexity in searching the huge space of models and parameters. The computational cost is higher when the model topology is more flexible. In this paper, we propose the notion of dominance which can lead to strong pruning of the search space and significant reduction of learning complexity, and apply this notion to the generalized latent class (GLC) models, a class of Bayesian networks for clustering categorical data. GLC models can address the local dependence problem in latent class analysis by assuming a very general graph structure. However, The flexible topology of GLC leads to large increase of the learning complexity. We first propose the concept of dominance and related theoretical results which is general for all Bayesian networks. Based on dominance, we propose an efficient learning algorithm for GLC. A core technique to prune dominated models is regularization, which can eliminate dominated models, leading to significant pruning of the search space. Significant improvements on the modeling quality and time complexity on real datasets are reported.

Mission-critical target detection imposes stringent performance requirements for wireless sensor networks, such as high detection probabilities and low false alarm rates. Data fusion has been shown as an effective technique for improving system detection performance by enabling efficient collaboration among sensors with limited sensing capability. Due to the high cost of network deployment, it is desirable to place sensors at optimal locations to achieve maximum detection performance. However, for sensor networks employing data fusion, optimal sensor placement is a non-linear optimizationproblem with prohibitive computational complexity. In this paper, we present fast sensor placement algorithms based on a probabilistic data fusion model.Simulation results show that our algorithms can meet the desired detection performance with a small number of sensors while achieving up to 7-fold speedup over the optimal algorithm.

Existing data-stream clustering algorithms such as CluStream arebased on k-means. These clustering algorithms are incompetent tofind clusters of arbitrary shapes and cannot handle outliers. Further, they require the knowledge of k and user-specified time window. To address these issues, this paper proposes D-Stream, a framework for clustering stream data using adensity-based approach. The algorithm uses an online component which maps each input data record into a grid and an offline component which computes the grid density and clusters the grids based on the density. The algorithm adopts a density decaying technique to capture the dynamic changes of a data stream. Exploiting the intricate relationships between the decay factor, data density and cluster structure, our algorithm can efficiently and effectively generate and adjust the clusters in real time. Further, a theoretically sound technique is developed to detect and remove sporadic grids mapped to by outliers in order to dramatically improve the space and time efficiency of the system. The technique makes high-speed data stream clustering feasible without degrading the clustering quality. The experimental results show that our algorithm has superior quality and efficiency, can find clusters of arbitrary shapes, and can accurately recognize the evolving behaviors of real-time data streams.

Multiple sequence alignment is an important and difficult problem in molecular biology and bioinformatics. In this paper, we propose a partitioning approach that significantly improves the solution time and quality by utilizing the locality structure of the problem. The algorithm solves the multiple sequence alignment in three stages. First, an automated and suboptimal partitioning strategy is used to divide the set of sequences into several subsections. Then a multiple sequence alignment algorithm based on ant colony optimization is used to align the sequences of each subsection. Finally, the alignment of original sequences can be obtained by assembling the result of each subsection. The ant colony algorithm is highly optimized in order to avoid local optimal traps and converge to global optimal efficiently. Experimental results show that the algorithm can significantly reduce the running time and improve the solution quality on large-scale multiple sequence alignment benchmarks.

In this paper, we present constraint-partitioned simulated annealing (CPSA), an algorithm that extends our previous constrained simulated annealing (CSA) for constrained optimization. The algorithm is based on the theory of extended saddle points (ESPs). By decomposing the ESP condition into multiple necessary conditions, CPSA partitions a problem by its constraints into subproblems, solves each independently using CSA, and resolves those violated global constraints across the subproblems. Because each subproblem is exponentially simpler and the number of global constraints is very small, the complexity of solving the original problem is significantly reduced. We state without proof the asymptotic convergence of CPSA with probability one to a constrained global minimum in discrete space. Last, we evaluate CPSA on some continuous constrained benchmarks

In this paper, we study the partitioning of constraints in temporal planning problems formulated as mixed-integer nonlinear programming (MINLP) problems. Constraint partitioning is attractive because it leads to much easier subproblems, where each is a significant relaxation of the original problem. Moreover, each subproblem is very similar to the original problem and can be solved by any existing solver with little or no modification. Constraint partitioning, however, introduces global constraints that may be violated when subproblems are evaluated independently. To reduce the overhead in resolving such global constraints, we develop in this paper new conditions and algorithms for limiting the search space to be backtracked in each subproblem. Using a penalty formulation of a MINLP where the constraint functions of the MINLP are transformed into non-negative functions, we present a necessary and sufficient extended saddle-point condition (ESPC) for constrained local minimization. When the penalties are larger than some thresholds, our theory shows a one-to-one correspondence between a constrained local minimum of the MINLP and an extended saddle point of the penalty function. Hence, one way to find a constrained local minimum is to increase gradually the penalties of those violated constraints and to look for a local minimum of the penalty function using any existing algorithm until a solution to the constrained model is found. Next, we extend the ESPC to constraint-partitioned MINLPs and propose a partition-and-resolve strategy for resolving violated global constraints across subproblems. Using the discrete-space ASPEN and the mixed-space MIPS planners to solve subproblems, we show significant improvements on some planning benchmarks, both in terms of the quality of the plans generated and the execution times to find them.

BACKGROUND: Searching for the longest common sequence (LCS) of multiple biosequences is one of the most fundamental tasks in bioinformatics. In this paper, we present a parallel algorithm named FAST_LCS to speedup the computation for finding LCS. RESULTS: A fast parallel algorithm for LCS is presented. The algorithm first constructs a novel successor table to obtain all the identical pairs and their levels. It then obtains the LCS by tracing back from the identical character pairs at the last level. Effective pruning techniques are developed to significantly reduce the computational complexity. Experimental results on gene sequences in the tigr database show that our algorithm is optimal and much more efficient than other leading LCS algorithms. CONCLUSION: We have developed one of the fastest parallel LCS algorithms on an MPP parallel computing model. For two sequences X and Y with lengths n and m, respectively, the memory required is max{4*(n+1)+4*(m+1), L}, where L is the number of identical character pairs. The time complexity is O(L) for sequential execution, and O(|LCS(X, Y)|) for parallel execution, where |LCS(X, Y)| is the length of the LCS of X and Y. For n sequences X1, X2, ..., Xn, the time complexity is O(L) for sequential execution, and O(|LCS(X1, X2, ..., Xn)|) for parallel execution. Experimental results support our analysis by showing significant improvement of the proposed method over other leading LCS algorithms.

BACKGROUND: The problem of inferring the evolutionary history and constructing the phylogenetic tree with high performance has become one of the major problems in computational biology. RESULTS: A new phylogenetic tree construction method from a given set of objects (proteins, species, etc.) is presented. As an extension of ant colony optimization, this method proposes an adaptive phylogenetic clustering algorithm based on a digraph to find a tree structure that defines the ancestral relationships among the given objects. CONCLUSION: Our phylogenetic tree construction method is tested to compare its results with that of the genetic algorithm (GA). Experimental results show that our algorithm converges much faster and also achieves higher quality than GA.

BACKGROUND: Ant colony algorithm has emerged recently as a new meta-heuristic method, which is inspired from the behaviours of real ants for solving NP-hard problems. However, the classical ant colony algorithm also has its defects of stagnation and premature. This paper aims at remedying these problems. RESULTS: In this paper, we propose an adaptive ant colony algorithm that simulates the behaviour of biological immune system. The solutions of the problem are much more diversified than traditional ant colony algorithms. CONCLUSION: The proposed method for improving the performance of traditional ant colony algorithm takes into account the polarization of the colonies, and adaptively adjusts the distribution of the solutions obtained by the ants. This makes the solutions more diverse so as to avoid the stagnation and premature phenomena.

In this paper, we present the partitioning of mutual-exclusion (mutex) constraints in temporal planning problems and its implementation in the SGPlan4 planner. Based on the strong locality of mutex constraints observed in many benchmarks of the Fourth International Planning Competition (IPC4), we propose to partition the constraints of a planning problem into groups based on their subgoals. Constraint partitioning leads to significantly easier subproblems that are similar to the original problem and that can be efficiently solved by the same planner with some modifications to its objective function. We present a partition-and-resolve strategy that looks for locally optimal subplans in constraint-partitioned temporal planning subproblems and that resolves those inconsistent global constraints across the subproblems. We also discuss some implementation details of SGPlan4, which include the resolution of violated global constraints, techniques for handling producible resources, landmark analysis, path finding and optimization, search-space reduction, and modifications of Metric-FF when used as a basic planner in SGPlan4. Last, we show results on the sensitivity of each of these techniques in quality-time trade-offs and experimentally demonstrate that SGPlan4 is effective for solving the IPC3 and IPC4 benchmarks.

As OLAP engines are widely used to support multidimensional data analysis, it is desirable to support in data cubes advanced statistical measures, such as regression and filtering, in addition to the traditional simple measures such as count and average. Such new measures will allow users to model, smooth, and predict the trends and patterns of data. Existing algorithms for simple distributive and algebraic measures are inadequate for efficient computation of statistical measures in a multidimensional space. In this paper, we propose a fundamentally new class of measures, compressible measures, in order to support efficient computation of the statistical models. For compressible measures, we compress each cell into an auxiliary matrix with a size independent of the number of tuples. We can then compute the statistical measures for any data cell from the compressed data of the lower-level cells without accessing the raw data. Time- and space-efficient lossless aggregation formulae are derived for regression and filtering measures. Our analytical and experimental studies show that the resulting system, regression cube, substantially reduces the memory usage and the overall response time for statistical analysis of multidimensional data.

In this paper, we study strategies in incremental planning for ordering and grouping subproblems partitioned by the subgoals of a planning problem when each sub-problem is solved by a basic planner. To generate a rich set of partial orders for ordering subproblems, we propose a new ordering algorithm based on a relaxed plan built from the initial state to the goal state. The new algorithm considers both the initial and the goal states and can effectively order subgoals in such a way that greatly reduces the number of invalidations during incremental planning. We have also considered trade-offs between the granularity of the subgoal sets and the complexity of solving the overall planning problem. We show an optimal region of grain size that minimizes the total complexity of incremental planning. We propose an efficient strategy to dynamically adjust the grain size in partitioning in order to operate in this optimal region. We further evaluate a redundant-execution scheme that uses two different subgoal orders in order to improve the quality of the plans generated without greatly sacrificing run-time efficiency. Experimental results on using three basic planners (metric-FF, YAHSP, and LPG-TD-speed) show that our strategies are general for improving the time and quality of each of these planners across various benchmarks

With the advance of microarray technology, clustering analysis has become a key tool to make sense of the massive amounts of genes expression data. An artificial ants sleeping model (ASM) and an adaptive artificial ants clustering algorithm (A/sup 4/C) are presented to solve the clustering problem in data mining by simulating the behaviors of social ant colonies. In the ASM model, each datum is represented by an agent. The agents' environment is a two-dimensional grid. In A/sup 4/C, the agents can form into high-quality clusters by making simple moves according to little local information from its neighborhood and the parameters are selected and adjusted adaptively. Experimental results on clustering benchmarks show the ASM and A/sup 4/C are simpler, easier to implement, and more efficient than previous methods.

The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfigurable pipeline bus system (LARPBS) are presented. For an image with n × n pixels, the first algorithm can complete EDT in O[(log n log log n)/(log log log n)] time using n2 processors. The second algorithm can computethe EDT in O(log n log log n) time using n2/(log log n) processors.

We study the partitioning of temporal planning problems formulated as mixed-integer nonlinear programming problems, develop methods to reduce the search space of partitioned subproblems, and propose algorithms for resolving unsatisfied global constraints. The algorithms are based on the necessary and sufficient extended saddle-point condition for constrained local minimization developed in this paper. When compared with the MIPS planner in solving some PDDL2.1 planning problems, our distributed implementation of MIPS shows significant improvements in time and quality.

This paper presents a procedural framework that unifies various mechanisms to look for discrete-neighborhood saddle points in solving discrete constrained optimization problems (DCOPs). Our approach is based on the necessary and sufficient condition on local optimality in discrete space, which shows the one-to-one correspondence between the discrete-space constrained local minima of a problem and the saddle points of the corresponding Lagrangian function. To look for such saddle points, we study various mechanisms for performing ascents of the Lagrangian function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAEA, a combined constrained simulated annealing and evolutionary algorithm, performs well when using mutations and crossovers to generate trial points and accepting them based on the Metropolis probability. We apply iterative deepening to determine the optimal number of generations in CSAEA and show that its performance is robust with respect to changes in population size. To test the performance of the procedures developed, we apply them to solve some continuous and mixed-integer nonlinear programming (NLP) benchmarks and show that they obtain better results than those of existing algorithms.

We propose new dominance relations that can speed up significantly the solution process of nonlinear constrained dynamic optimization problems in discrete time and space. We first show that path dominance in dynamic programming cannot be applied when there are general constraints that span across multiple stages, and that node dominance, in the form of Euler-Lagrange conditions developed in optimal control theory in continuous space, cannot be extended to that in discrete space. This paper is the first to propose efficient dominance relations, in the form of local saddle-point conditions in each stage of a problem, for pruning states that will not lead to locally optimal paths. By utilizing these dominance relations, we develop efficient search algorithms whose complexity, despite exponential, has a much smaller base as compared to that without using the relations. Finally, we demonstrate the performance of our algorithms on some spacecraft planning and scheduling benchmarks and show significant improvements in CPU time and solution quality as compared to those obtained by the existing ASPEN planner.

The paper presents a framework that unifies various search mechanisms for solving constrained nonlinear programming (NLP) problems. These problems are characterized by functions that are not necessarily differentiable and continuous. Our proposed framework is based on the first-order necessary and sufficient condition for constrained local minimization in discrete space that shows the equivalence between discrete-neighborhood saddle points and constrained local minima. To look for discrete-neighborhood saddle points, we formulate a discrete constrained NLP in an augmented Lagrangian function and study various mechanisms for performing ascents of the augmented function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAGA, a combined constrained simulated annealing (SA) and genetic algorithm (GA), performs well. Finally, we apply iterative deepening to determine the optimal number of generations in CSAGA and show that performance is robust with respect to changes in population size.

The paper presents a problem-independent framework that unifies various mechanisms for solving discrete constrained nonlinear programming (NLP) problems whose functions are not necessarily differentiable and continuous. The framework is based on the first-order necessary and sufficient conditions in the theory of discrete constrained optimization using Lagrange multipliers. It implements the search for discrete-neighborhood saddle points (SP/sub dn/) by performing ascents in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our study on the various mechanisms shows that CSAGA, a combined constrained simulated annealing and genetic algorithm, performs well. Finally, we apply iterative deepening to determine the optimal number of generations in CSAGA.