Knowledge Graph (KG)-supported Graph Neural Network models are becoming crucial in recommendation systems due to their ability to mitigate the data sparsity challenge. However, these models remain suboptimal because they overlook the representation differences between the inherent user-item Bipartite Graph (BG) and the external head-relation-tail KG, leading to semantic misalignment. Moreover, they indiscriminately incorporate various types of relations from the KG, which may introduce noise information into the model, ultimately degrading recommendation performance. To address these challenges, we propose an end-to-end model named Multi-graph Fusion Cross-model Contrastive Learning (MFCCL). To uncover users' interest in items and explore the associations between items, we first construct a user-interest graph by integrating information from both the BG and KG, and an item-association graph derived from the BG. We devise a multi-graph representation learning module that incorporates rich semantics into user and item representations in parallel. Simultaneously, a classical collaborative filtering module is introduced to fully leverage user-item collaborative signals. Additionally, we design a novel free data-augmentation cross-model contrastive learning to facilitate the exchange of complementary information between different models. Empirical evaluations on three widely used benchmarks demonstrate that our MFCCL method achieved significant improvements over the baselines.

Multi-graph multi-label learning (MGML) represents each object as a bag-of-graphs with multiple labels, but demands large-scale labeled data whose acquisition is often difficult and costly. Self-supervised contrastive learning (SCL) mitigates label dependence by leveraging data augmentation to construct discriminative pretext tasks, proving effective for multi-instance learning. However, when applied to MGML, SCL faces two key challenges: (1) it distinguishes individual instances by their differences, whereas MGML requires modeling label correlations; (2) it assumes semantic invariance under augmentation, but structural perturbations in MGML alter label semantics. To tackle these challenges, we propose a self-suPervised contrastive rE-learning framework for mulTi-grAph multi-labeL classification (PETAL). Specifically, to model label correlations, we first define a unified label space to learn label prototypes and align features with them, yielding prototype-aligned representations. We then design a multi-granularity contrastive loss over these representations, which captures label dependencies by contrasting at the bag level, graph level, and bag-graph level. Moreover, to ensure semantic invariance, we develop a contrastive re-learning strategy based on prototype-aligned representations to generate augmentation-free positive samples. This guarantees consistent multi-label distributions without structural perturbations. Experiments on six datasets demonstrate that PETAL achieves an average improvement of 4.12% over state-of-the-art self-supervised and supervised baselines.

Every graph hides a tree: through tree decomposition—a foundational tool in modern graph theory with broad applications such as in computational power networks, any network can be unfolded into a hierarchy of overlapping vertex bags whose backbone is a tree. Leveraging this powerful lens, we propose Topological Decomposition for Self-supervised Learning (TopDSL), a framework that injects multi-scale signals into graph representation learning. Concretely, we: 1) decompose the input graph into tree structures with bags representing local structural contexts; 2) compute bag-level roles via closeness centrality for nodes and local edge betweenness for edges, and aggregate these scores across bags to capture context-dependent importance (e.g., local structural bridges); 3) convert the resulting importance and attribute-stability scores into a context-aware augmentation policy that adaptively perturbs nodes, edges, and features—preserving local bridges, honoring multi-community vertices, and attenuating noisy global hubs; 4) construct a new structural similarity loss for contrastive learning, which fuses traditional graph-based proximity with a novel tree-based similarity derived from node co-occurrence in decomposition bags; 5) demonstrate that our framework achieves superior performance over state-of-the-art baselines on various graph learning benchmarks.

Multi-Graph Learning (MGL) is a fundamental machine learning paradigm that represents objects as bags-of-graphs, each encoding a distinct structural property, and has broad applications in bioinformatics, chemistry, computing power networks, and software defect detection. However, the inherent scarcity of labeled data poses a significant bottleneck for supervised MGL approaches. While self-supervised contrastive learning offers a compelling solution, its direct application to MGL faces three key challenges: (1) existing graph neural networks, primarily for single-graph modeling, struggle to yield discriminative bag-level representations from bags-of-graphs; (2) conventional contrastive objectives are limited to single-level settings, failing to capture cross-hierarchical dependencies; and (3) standard data augmentation often disrupts intrinsic graph and bag structures, undermining semantic consistency. To address these issues, we propose the Hierarchical Graph-Bag-Network (HGBN), a self-supervised MGL framework that constructs hierarchical representations in the form of a graph-bag-network. HGBN employs an asymmetric hierarchical graph neural network to learn discriminative graph-level and bag-level representations, introduces cross-hierarchical contrastive objectives to align graph-level and bag-level semantics, and leverages the asymmetric network outputs to form positive and negative pairs, preserving intrinsic structural and semantic consistency. Experiments on eight benchmark multi-graph datasets demonstrate that HGBN consistently outperforms both supervised and self-supervised state-of-the-art baselines, achieving average improvements of 4.82% in accuracy and F1 score.

The relationship between long non-coding RNAs (lncRNAs) and diseases is crucial for understanding biological processes, as well as the onset, progression, prevention, and treatment of diseases. Accurate prediction of associations between lncRNAs and diseases holds significant potential, offering new insights for biological research and identifying novel therapeutic targets for clinical applications. These predictions enhance research efficiency, reduce unnecessary experimental costs, and improve diagnostic and treatment precision. However, existing methods often fail to simultaneously consider global structural information, local subgraph details, and multi-scale graph information. In this study, we design a graph neural network prediction framework based on multi-scale graph-level attention, designed to predict disease-related candidate lncRNAs, named GLALDA. It employs a dual-level attention mechanism to integrate both global structural and local subgraph information. To enhance the ability of the model to capture the graph structure, edge feature information is incorporated into the attention calculations. Furthermore, we utilize a cross-attention mechanism to deeply fuse feature representations from graphs of different scales, effectively combining local node details with global context. The resulting integrated features are then fed into a scoring network for evaluation. Experimental results on public datasets demonstrate that GLALDA achieves an AUC of 0.949 and an AUPR of 0.947, outperforming six other state-of-the-art methods. Furthermore, through in-depth case studies of three cancers, we further validate GLALDA's capability to identify potential disease-related lncRNA candidates. These findings underscore the framework's potential to advance both biological research and clinical applications.

OBJECTIVE: Accurate prediction of cancer drug responses is essential for advancing precision oncology. This work aims to improve generalization and robustness in drug response prediction by modeling complex drug-cell line interactions. METHODS: We propose HypergraphCDR, a Hypergraph Convolutional Network model with Hypergraph Contrastive Learning for cancer drug response prediction. Multiomics features of cancer cell lines are first compressed using an autoencoder. A Hypergraph is then constructed to capture high-order relationships between drugs and cancer cell lines, with Hypergraph Convolutional Networks generating drug embeddings. In parallel, cell line embeddings are generated via a neural network. Drug and cell line embeddings are jointly optimized and integrated into a regression framework using a combination of supervised regression loss and contrastive loss. RESULTS: Extensive experiments demonstrate that HypergraphCDR consistently outperforms state-of-the-art methods in terms of Pearson Correlation Coefficient (${PCC}$), Spearman Correlation Coefficient (${SCC}$), and Coefficient of Determination (${R}^{2}$). Moreover, in independent experiments involving unseen drugs and unseen cell lines, as well as tissue-specific evaluations, HypergraphCDR exhibits superior generalization performance compared with recent baselines. CONCLUSION: By explicitly modeling higher-order drug-cell line relationships, HypergraphCDR substantially enhances the accuracy and robustness of cancer drug response prediction. SIGNIFICANCE: This study provides an effective and generalizable computational framework for drug response prediction, supporting reliable drug screening and treatment strategy development in precision medicine.

LncRNAs have been confirmed by various studies to play an important role in the generation of a variety of diseases, making the accurate prediction of IncRNA-disease associations crucial for diagnosis and therapy. However, experimentally validated associations remain scarce. To address the limitations of existing computational methods regarding biological information coverage and model robustness, we developed HGANTLDA, a novel multimodal information fusion framework. We made three key contributions: 1) integrating the Nucleotide Transformer, a gene language pre-training model, to systematically encode IncRNA sequence semantic information, enhancing sequencelevel feature representation; 2) incorporating miRNA regulatory mechanisms by constructing a heterogeneous graph of IncRNA, miRNA, and disease nodes, and employing a HAN to learn representations from complex semantic paths among these nodes; 3) developing a function similarity-based negative sample selection strategy that significantly reduced pseudo-negative sample interference, effectively improving prediction stability. Extensive experimental results demonstrate that HGANTLDA achieves superior performance, with an AUC of 98.93% and an F1-score of 97.29%, representing a 2.7% improvement over the secondranked model. We have also developed an accessible online service system (http://62.234.10.79:80/) that allows users to perform predictions, customize models, and visualize IncRNA-disease association results interactively.

Recently, k-vertex connected component (k-VCC) detection has gained significant attention in graph analysis owing to its ability to capture structural cohesion. A k-VCC remains connected even after the removal of any k-1 vertices from itself. The k-VCC has broad applications across multiple domains, such as social network analysis, cybersecurity, and bioinformatics. Yet, the existing exact k-VCC detection algorithms require repeated computation of minimum vertex cuts, imposing a prohibitive computational cost for large scale graphs. In this paper, we present an approximate algorithm for k-VCC detection that leverages Monte Carlo sampling to accelerate minimum vertex cut computation with theoretical guarantee. Further, we design a distributed algorithm for mining all k-VCCs, named DkVCC. DkVCC adopts a divide-and-conquer strategy, decomposing the problem into smaller subgraph mining tasks that can be executed concurrently. Specifically, we generate tasks from individual vertices to construct initial subgraphs, and then iteratively expand and merge the subgraphs to form the final k-VCCs. Extensive experiments on 5 large real datasets demonstrates the efficiency of our proposed algorithms. For example, we achieve 4× runtime speedup on the LiveJournal dataset with 3.99M vertices and 34.7M edges in a 3-node cluster.

Graph stream summarization refers to the technique used to process graph streams-unbounded sequences of edges-by constructing compressed representations that support approximate queries on both graph topology and temporal information in computing power networks. However, existing methods struggle to achieve accurate and efficient temporal queries due to two key limitations: (1) inefficient integration of temporal information, leading to high latency in both edge processing and query execution; and (2) redundant multilayer structures that accumulate errors, significantly reducing query accuracy. In this paper, we propose GRIT, an accurate and efficient Graph stReam summarIzation for Temporal query. GRIT introduces a new structure FlatIndex, which organizes temporal information in a flattened form, playing a critical role in minimizing error accumulation and ensuring accurate temporal queries. To further enhance edge processing efficiency, we introduce a lazy update strategy, which updates only a single element in the FlatIndex upon edge insertion, significantly reducing insertion latency. Moreover, our greedy-based decomposition (GBD) algorithm decomposes the target query range into the minimal number of intervals corresponding to the FlatIndex, enabling efficient execution of temporal queries over arbitrary time ranges. Extensive experiments on five real-world datasets demonstrate that GRIT improves query accuracy by 2-3 orders of magnitude, while reducing query latency by 1-2 orders of magnitude and increasing throughput by 7-13 times compared to state-of-the-art methods.

The Hot Object Cache (HOC) admission policy is one of the core technologies in Content Delivery Network (CDN) cache management and plays a critical role in the broader Computing Power Network (CPN) environment. It primarily employs heuristic- and threshold-based methods. These methods are simple and efficient but fail both to capture latent dependencies among requested objects and to support informed admission decisions. We propose a reinforcement learning approach called LEI for multi-object CDN admission (i.e., sequences of request objects across multiple time instants, which include multiple objects requested at each instant). LEI integrates three key components: a Multi-Object Time Encoding (MO-TE) mechanism, which uses density-based representations to model multi-object temporal sequences; a Buffer Mechanism, which addresses the reward-latency issue by buffering historical decision information; and a dual-head network architecture with a two-stage training strategy, which enhances the model's admission decision-making capability and long-term stability. Experiments on four public datasets demonstrate that LEI improves the HOC request hit rate by 5-12% and the HOC byte hit rate by 5-42% compared with state-of-the-art methods. It also reduces disk cache (DC) read and write rates.

Network resilience refers to the ability of a network to maintain its functionality despite perturbations, where resilience/robustness is shown when a substantial proportion of its nodes remain engaged even under changes. Such phenomenon is common in real-world networks, such as computing power networks. Previous works demonstrate that the coreness of a user/node effectively captures the dynamics of user engagement. However, most existing works only consider changes in a single coreness value and thus fail to measure the overall network resilience. Subsequent works are either inefficient or do not consider coreness-decreased scenario. In this paper, we propose and study the collapsed follower maximization problem, aiming to maximize the number of coreness-decreased vertices by finding a group collapser (collapsing a set of vertices) with a given budget. We prove that the problem is NP-hard and W[2]-hard parameterized by the budget b. To address the problem, we first present a Greedy algorithm that iteratively finds the best collapser in each of the budget b iterations. To further optimize the Greedy algorithm, we propose GreedyOpt, which leverages the shell component structure to accelerate the computation of follower for one collapser and prune the search space. Extensive experimental results on 8 real-world datasets show that the effectiveness and efficiency of our algorithms.

Graph Neural Networks (GNNs) are the rising standard for graph tasks, yet their distributed training in servers or computing power network remains challenging. Cross-machine sampling and data loading often create bottlenecks, leading to inefficient resource utilization. In this paper, we present Hybrid2, a distributed GNN training system that combines full-graph and mini-batch training through a novel hybrid-batch training method. It also adopts hybrid feature extraction, leveraging both local caching and remote access to improve feature retrieval efficiency. The integration of these methods in Hybrid² results in a dual hybrid-gain effect. First, it reduces sampling and loading overhead by pre-aggregating neighbors for each target vertex, minimizing the layers to sample and load. Second, it accelerates data loading by dynamically identifying and locally caching the most frequently accessed vertices during training, maximizing memory efficiency. Experimental results demonstrate that Hybrid² brings substantial performance improvements across key components of distributed GNN training. Network communication overhead is reduced by up to tens of times, while both sampling and loading achieve at least several-fold speedups. These gains contribute to an overall training acceleration exceeding 20× compared to DistDGL, all with comparable GPU memory usage and no loss in accuracy. Compared to the state-of-the-art system, it achieves nearly 3× speedup while using fewer resources.

Node equivalence is common in graphs, such as computing networks, encompassing automorphic equivalence (preserving adjacency under node permutations) and attribute equivalence (nodes with identical attributes). Despite their importance for learning node representations, these equivalences are largely ignored by existing graph models. To bridge this gap, we propose a GrAph self-supervised Learning framework with Equivalence (GALE) and analyze its connections to existing techniques. Specifically, we: 1) unify automorphic and attribute equivalence into a single equivalence class; 2) enforce the equivalence principle to make representations within the same class more similar while separating those across classes; 3) introduce approximate equivalence classes with linear time complexity to address the NP-hardness of exact automorphism detection and handle node-feature variation; 4) analyze existing graph encoders, noting limitations in message passing neural networks and graph transformers regarding equivalence constraints; 5) show that graph contrastive learning are a degenerate form of equivalence constraint; and 6) demonstrate that GALE achieves superior performance over baselines.

Graphs, fundamental in modeling various research subjects such as computing networks, consist of nodes linked by edges. However, they typically function as components within larger structures in real-world scenarios, such as in protein-protein interactions where each protein is a graph in a larger network. This study delves into the Graph-of-Net (GON), a structure that extends the concept of traditional graphs by representing each node as a graph itself. It provides a multi-level perspective on the relationships between objects, encapsulating both the detailed structure of individual nodes and the broader network of dependencies. To learn node representations within the GON, we propose a position-aware neural network for Graph-of-Net which processes both intra-graph and inter-graph connections and incorporates additional data like node labels. Our model employs dual encoders and graph constructors to build and refine a constraint network, where nodes are adaptively arranged based on their positions, as determined by the network’s constraint system. Our model demonstrates significant improvements over baselines in empirical evaluations on various datasets.

Accurate encrypted malicious traffic detection is crucial for improving network service quality. Existing methods leverage the widespread application of machine learning (ML) to distinguish encrypted malicious traffic from normal traffic by learning the statistical characteristics of traffic. However, the scarcity of high-quality annotated encrypted malicious traffic data, especially malicious traffic samples, limits the performance of these supervised learning methods. Additionally, annotating network traffic is challenging as it requires domain-specific expert knowledge. Therefore, this paper proposes an encrypted malicious traffic detection framework based on the active learning method. This framework achieves high recognition rates using a limited number of samples. It employs a hybrid weighted uncertainty sampling strategy that utilizes the independence coefficient method to weight uncertainty measurements across multiple scales. This improves the reliability during the automatic instance selection process. In the experimental section, we achieved a detection accuracy exceeding 93 % using a data subset comprising only 1 % of the original dataset. Furthermore, we validated the robustness of the proposed framework through calibration rate measurements in the experiments.

To be still yet still moving. - Do Hyun Choe

Graph self-supervised learning aims to learn the intrinsic graph representations from unlabeled data, with broad applicability in areas such as computing networks. Although graph contrastive learning (GCL) has achieved remarkable progress by generating perturbed views via data augmentation and optimizing sample similarity, it performs poorly in heterophilic graph scenarios (where connected nodes are likely to belong to different classes or exhibit dissimilar features). In heterophilic graphs, existing methods typically rely on random or carefully designed augmentation strategies (e.g., edge dropping) for contrastive views. However, such graph structures exhibit intricate edge relationships, where topological perturbations may completely alter the semantics of neighborhoods. Moreover, most methods focus solely on local contrastive signals while neglecting global structural constraints. To address these limitations, inspired by graph coloring, we propose a novel Coloring learning for heterophilic graph Representation framework, CoRep, which: 1) Pioneers a coloring classifier to generate coloring labels, explicitly minimizing the discrepancy between homophilic nodes while maximizing that of heterophilic nodes. A global positive sample set is constructed using multi-hop same-color nodes to capture global semantic consistency. 2) Introduces a learnable edge evaluator to guide the coloring learning dynamically and utilizes the edges' triplet relations to enhance its robustness. 3) Leverages Gumbel-Softmax to differentially discretize color distributions, suppressing noise via a redundancy constraint and enhancing intra-class compactness. Experimental results on 14 benchmark datasets demonstrate that CoRep significantly outperforms current state-of-the-art methods.

Identifying complex interactions among millions of single nucleotide polymorphisms (SNPs) is a key challenge in Genome-Wide Association Studies (GWAS), offering crucial insights into the genetic architecture of complex diseases. Evolutionary algorithm (EA)-based methods have gained significant attention for their global search capabilities, controllable runtime, and multi-objective optimization potential. However, when applied to high-dimensional GWAS datasets, many existing EA-based methods encounter challenges such as getting trapped in local optima and facing high computational demands. To address these issues, the evolutionary multitasking (EMT) paradigm presents a promising solution, enhancing population diversity and convergence speed through collaborative, cross-task knowledge sharing. Furthermore, the multi-tasking framework and EA can be seamlessly deployed across multiple Graphics Processing Units (GPUs), leveraging their high parallelism and aggregated memory bandwidth. Therefore, we introduce a GPU-powered evolutionary auxiliary multitasking algorithm (GEAMT) for fast SNP interaction detection. GEAMT first constructs a main task along with several low-dimensional auxiliary tasks to redefine the original task. The main task explores the entire search space, while the auxiliary tasks search distinct subspaces to enhance local optimization capabilities. In each iteration, the auxiliary tasks transfer high-quality information to the main task via an information transfer mechanism. Subsequently, an auxiliary task update strategy based on feature regrouping is employed to switch the search subspaces of the auxiliary tasks. The final results are derived from the Pareto-optimal solutions of the main task. Implemented across multiple GPUs, GEAMT achieves notable scalability and efficiency. Comprehensive experiments on both synthetic and real-world datasets demonstrate that GEAMT can significantly enhance search accuracy and speed up the search process.

The subcellular localization of Long non-coding RNAs (LncRNAs) is a pivotal research area with profound implications for understanding underlying molecular mechanisms, involvement in pathological processes, and regulation of gene expression. Traditional machine learning based methods often rely on k-mer frequencies for classification, ignoring the global features of LncRNAs. More recent methods based on deep learning have utilized sequence and graph models for LncRNA classification. However, while these methods could improve their combination of LncRNA features, they still possess limitations, for example, ignoring the fact that mutations could occur in LncRNAs. Simultaneously, it employs the Shapelet model to extract local features of the most representative k-mer among different LncRNA classes. Furthermore, gShapeLnoc combines global and local feature representations for predicting the subcellular localization of LncRNAs. We have evaluated the performance of the gShapeLnoc algorithm on a real dataset, and the results demonstrate that it outperforms existing state-of-the-art methods in terms of accuracy.

Limited-supervised multi-label learning (LML) leverages weak or noisy supervision for multi-label classification model training over data with label noise, which contain missing labels and/or redundant labels. Existing studies usually solve LML problems by assuming that label noise is independent of the input features and class labels, while ignoring the fact that noisy labels may depend on the input features (instance-dependent) and the classes (label-dependent) in many real-world applications. In this paper, we propose limited-supervised Multi-label Learning with Dependency Noise (MLDN) to simultaneously identify the instance-dependent and label-dependent label noise by factorizing the noise matrix as the outputs of a mapping from the feature and label representations. Meanwhile, we regularize the problem with the manifold constraint on noise matrix to preserve local relationships and uncover the manifold structure. Theoretically, we bound noise recover error for the resulting problem. We solve the problem by using a first-order scheme based on proximal operator, and the convergence rate of it is at least sub-linear. Extensive experiments conducted on various datasets demonstrate the superiority of our proposed method.

Accurate polyp segmentation of colonoscopy images is crucial for diagnosing and treating colorectal cancer. A new type of method for this challenging task has been introduced with the emergence of large vision models like the Segment Anything Model (SAM). However, the application of SAM to medical image segmentation falls short of clinical requirements. In efforts to tailor SAM for medical imaging tasks, researchers often work on improving adapters and prompts separately, over-looking the potential for synergy between them. Furthermore, existing methods still do not overcome the influence of prompt type, quantity, and positioning on segmentation results. SAM’s dependency on professionally annotated prompts further limits its utility. To tackle these issues, we propose a fine-tuning strategy named Automatic Prompt Tuning (APT), which aims to generate prompts automatically. This approach begins with adapting SAM for polyp segmentation by incorporating lightweight adapters into the image encoder. Next, we introduce an automatic prompt generator to process features and produce relevant prompts. Finally, we ensure the mask decoder consistently delivers accurate segmentation by leveraging these automatically generated prompts. Extensive experiments on three major polyp segmentation datasets demonstrate that APT outperforms other state-of-the-art approaches, proving its effectiveness.

Bipartite graph models the relationship between two different sets of entities. Such graph data become more dynamic and are organized as stream with duplicate edges in real-word applications such as customer-product in e-commerce. A butterfly, (2,2)-biclique, is the simplest cohesive substructure and of great importance in a bipartite graph. However, it is challenging to estimate the number of butterflies in large scale and high dynamic bipartite graph stream when given a limited memory. Besides, existing works for butterfly counting assume no duplicate edges in the bipartite graph stream, which cause less accuracy in bipartite graph stream with duplicate edges. In this paper, we propose FABLE, a Fixed-size memory Approximate Butterfly counting algorithm for dupLicate Edges in bipartite graph stream. In FABLE, we compute the number of distinct edges by maintaining an ordered list of edge priorities for replacement and sampling. We provide theoretical proof of unbiasedness and derive the variance of butterfly count. Our extensive experiments on 5 real-world datasets confirm that our approach has higher accuracy compared with the baseline method under the same memory usage.

As real-world graph data continues to grow larger and larger, training large graphs in a distributed environment is becoming increasingly prevalent. However, network transmission in a distributed environment can hinder subsequent training steps, resulting in suboptimal training performance. After conducting a comprehensive analysis and experimental demonstration, we have discovered that during the training process, there exist certain data that can be computed once and reused multiple times. In addition, we also found that after a certain iterations of training, the parameter updates during each iteration had minimal effect on the parameters. Based on these findings, we have improved the original implementation and proposed a cache-enhanced distributed graph training system, NeutronCache. It utilizes cached reusable intermediate data and a dynamically adjusted stale embedding reuse strategy, reducing network overhead in distributed systems and accelerating the training process. Through experimental validation, our implementation achieved acceleration ranging from 1.4X to 16.61X on real graph datasets with almost no loss in accuracy.

Attributed Heterogeneous Information Networks (AHINs) amalgamate the advantages of attributed graphs (AGs) and heterogeneous information networks (HINs) to model intri-cate systems. Within this context, community search-aiming to identify the most probable community containing the queried ver-tex-has been extensively explored in AGs and HINs. However, existing methodologies fall short in simultaneously accommodating heterogeneous attributes and multiple meta-paths in AHINs, posing a substantial challenge in investigating community search within expansive AHINs. Recent studies highlight the efficacy of machine learning-based community search, offering enhanced flexibility and higher-quality communities in comparison to traditional structural-based methods. Yet, semi-supervised learning methods demand substantial labeled data and incur considerable memory and time costs when applied to large AHINs. To tackle these challenges, we propose a MK (Most-likely; K-sized) community search approach. This approach involves defining an MK community and leveraging Graph Neural Networks (GNNs) to amalgamate structures and attributes into a unified goodness metric. Our methodology involves training on local subgraphs sampled via guided random walks based on multiple meta-paths, circumventing the need for training on the entire graph. Moreover, attention-based GNNs adeptly learn meta-path weights to guide weighted walks in subsequent iterations. Additionally, self-training is employed to alleviate the labeling burden. We also demonstrate that pinpointing the location for the MK community is NP-hard and present a heuristic local search strategy that expedites the resolution process through rewriting. Ultimately, the convergence of iterations yields the solution. Extensive experiments conducted on four real-world datasets underscore that the MK framework significantly enhances both effectiveness and efficiency in community search within AHINs. Our code is publicly available at https://github.com/uucxuu/CSAH.

Community search is a fundamental problem in graph analysis. However, prevailing community search models predominantly focus on non-attributed or vertex-attributed graphs. Real-world graphs often bear crucial information within their edges, depicting intricate interactions among vertices. Integrating this edge-based information becomes pivotal in refining community search methodologies. In this paper, we proposed the Edge-Attributed Community Search (EACS) problem and proved that the EACS problem is NP-hard. Advanced exact and 2-approximation algorithms are proposed to address the EACS problem. Extensive experiments demonstrate the efficiency and effectiveness of our algorithms.

Multi-graph Multi-label learning (Mgml) aims to classify a set of objects of interest, such as text or images, using a bag-of-graphs representation. PreviousMgmlworks have limitations as they only learn labels at the bag level, lose structural information in learning by transferring graphs into instances, and cannot handle noisy labels. This paper presents a robustcoarseandfine-grainedNoise Multi-graph Multi-label (cfMGNML) learning framework that builds the learning model over the graphs and empowers label prediction at both thecoarse(bag) andfine-grained(graph in each bag) levels with noisy labels. To identify label noise, a label probability matrix is defined to act on the scoring function of each label, with a higher probability value indicating that the label is more likely to be the corresponding graph or bag label. The problem is regularized with the manifold constraint on the label probability matrix to preserve local relationships within the data and uncover its essential manifold structure. Meanwhile, a thresholding rank-loss objective is proposed to rank the labels for the graphs and bags and minimize the hamming loss at one step simultaneously. To tackle the non-convex optimization problem, an effective sub- gradient descent algorithm is developed. Experiments over various datasets demonstrate the proposed method achieves superior performance than the state-of-the-art algorithms.

Abstract Software quality is key to the success of software systems. Modern software systems are growing in their worth based on industry needs and becoming more complex, which inevitably increases the possibility of more defects in software systems. Software repairing is time‐consuming, especially locating the source files related to specific software defect reports. To locate defective source files more quickly and accurately, automated software defect location technology is generated and has a huge application value. The existing deep learning‐based software defect location method focuses on extracting the semantic correlation between the source file and the corresponding defect reports. However, the extensive code structure information contained in the source files is ignored. To this end, we propose a software defect location method, namely, multi‐graph learning‐based software defect location (MGSDL). By extracting the program dependency graphs for functions, each source file is converted into a graph bag containing multiple graphs (i.e., multi‐graph). Further, a multi‐graph learning method is proposed, which learns code structure information from multi‐graph to establish the semantic association between source files and software defect reports. Experiments' results on four publicly available datasets, AspectJ, Tomcat, Eclipse UI, and SWT, show that MGSDL improves on average 3.88%, 5.66%, 13.23%, 9.47%, and 3.26% over the competitive methods in five evaluation metrics, rank@10, rank@5, MRR, MAP, and AUC, respectively.

Reachability query has important applications in many fields such as social networks, semantic web, and biological information networks. How to improve the query efficiency in directed acyclic graph (DAG) has always been the main problem of reachability query research. Existing methods either can't prune unreachable pairs enough or can't perform well on both index size and query time. In this paper, we propose BL (Bridging Label), a general index framework for reachability queries in large graphs. First, we summarize the relationships between BL and existing label indices. Second, we propose a kind of specific index, named minBL, which can avoid redundant labels. Moreover, we propose TFD-minBL and CTFD-minBL, which generate minBL under the TFD-based permutation single-pass and in incremental, respectively. Finally, we conduct a large number of extensive experiments on real datasets. The experimental results show that our methods are much faster and use less storage overhead than state-of-the-art methods. The source codes of BL can be downloaded from web sitehttps://github.com/BioLab310/BL

The problem of finding the longest common subsequence (MLCS) for multiple sequences is a computationally intensive and challenging problem that has significant applications in various fields such as text comparison, pattern recognition, and gene diagnosis. Currently, the dominant point-based MLCS algorithms have become popular and extensively studied. Generally, they construct the directed acyclic graph (DAG) of matching points and convert the MLCS problem into a search for the longest paths in the DAG. Several improvements have been made, focusing on decreasing model size and reducing redundant computations. These include 1) hash methods for eliminating duplicated nodes, 2) dynamic structures for supporting smaller DAG and 3) path pruning strategy and so on. However, the algorithms are still too limited when facing large-scale MLCS problem due to 1) the dynamic structures are too time-consuming to maintain and 2) the path pruning relies heavily on the tightness of the lower and upper bound of the MLCS. These factors contribute to the large-scale MLCS problem remaining a challenge. We propose a novel algorithm for the large-scale MLCS problem, named dwMLCS. It is based on two models: one is a dynamic DAG model which is both space and time efficient. It can decrease the size of the DAG significantly. The other is a weighted DAG model with new successor strategies. With this model, we design the algorithm for finding a tighter lower bound of the MLCS. Then, the path pruning is conducted to further reduce the size of the DAG and eliminate redundant computation. Additionally, we propose an upper bound method for improving the efficiency of the path pruning strategy. The experimental results demonstrate that the effectiveness and efficiency of the models and algorithms proposed are better than state-of-the-art algorithms.

The De Bruijn graph (DBG) has been widely used in the algorithms for indexing or organizing read and reference sequences in bioinformatics. However, a DBG model that can locate each node, edge and path on sequence has not been proposed so far. Recently, DBG has been used for representing reference sequences in read mapping tasks. In this process, it is not a one-to-one correspondence between the paths of DBG and the substrings of reference sequence. This results in the false path on DBG, which means no substrings of reference producing the path. Moreover, if a candidate path of a read is true, we need to locate it and verify the candidate on sequence. To solve these problems, we proposed a DBG model, called MiniDBG, which stores the position lists of a minimal set of edges. With the position lists, MiniDBG can locate any node, edge and path efficiently. We also proposed algorithms for generating MiniDBG based on an original DBG and algorithms for locating edges or paths on sequence. We designed and ran experiments on real datasets for comparing them with BWT-based and position list-based methods. The experimental results show that MiniDBG can locate the edges and paths efficiently with lower memory costs.

Multi-instance learning (MIL) is a supervised learning where each example is a labeled bag with many instances. The typical MIL strategies are to train an instance-level feature extractor followed by aggregating instances features as bag-level representation with labeled information. However, learning such a bag-level representation highly depends on a large number of labeled datasets, which are difficult to get in real-world scenarios. In this paper, we make the first attempt to propose a robust Self-supervised Multi-Instance LEarning architecture with Structure awareness (SMILEs) that learns unsupervised bag representation. Our proposed approach is: 1) permutation invariant to the order of instances in bag; 2) structure-aware to encode the topological structures among the instances; and 3) robust against instances noise or permutation. Specifically, to yield robust MIL model without label information, we augment the multi-instance bag and train the representation encoder to maximize the correspondence between the representations of the same bag in its different augmented forms. Moreover, to capture topological structures from nearby instances in bags, our framework learns optimal graph structures for the bags and these graphs are optimized together with message passing layers and the ordered weighted averaging operator towards contrastive loss. Our main theorem characterizes the permutation invariance of the bag representation. Compared with state-of-the-art supervised MIL baselines, SMILEs achieves average improvement of 4.9%, 4.4% in classification accuracy on 5 benchmark datasets and 20 newsgroups datasets, respectively. In addition, we show that the model is robust to the input corruption.

Community search is a fundamental graph processing task that aims to find a community containing the given query node. Recent studies show that machine learning (ML)-based community search can return higher-quality communities than the classic methods such as k-core and k-truss. However, the state-of-the-art ML-based models require a large number of labeled data (i.e., nodes in ground-truth communities) for training that are difficult to obtain in real applications, and incur unaffordable memory costs or query time for large datasets. To address these issues, in this paper, we present the community search based on contrastive learning with partition, namely COCLEP, which only requires a few labels and is both memory and query efficient. In particular, given a small collection of query nodes and a few (e.g., three) corresponding ground-truth community nodes for each query, COCLEP learns a query-dependent model through the proposed graph neural network and the designed label-aware contrastive learner. The former perceives query node information, low-order neighborhood information, and high-order hypergraph structure information, the latter contrasts low-order intra-view, high-order intra-view, and low-high-order inter-view representations of the nodes. Further, we theoretically prove that COCLEP can be scalable to large datasets with the min-cut over the graph. To the best of our knowledge, this is the first attempt to adopt contrastive learning for community search task that is nontrivial. Extensive experiments on real-world datasets show that COCLEP simultaneously achieves better community effectiveness and comparably high query efficiency while using fewer labels compared with the-state-of-the-art approaches and is scalable for large datasets.

This paper presents a novel spatial query, skyline micro-cluster (SMC) query. Given a set of data points P, a query point q, a radius γ and a density parameter k, the SMC query returns the skyline micro-clusters (MCs), where MC is a set of points in P that can be covered by a circle with radius γ and the number of points in MC is at least k. In this paper, we formally define the SMC query. As the brute-force approach to solving the SMC query in massive datasets has high computation and memory costs, we propose a basic skyline micro-cluster query algorithm, BSMC, which can reduce the time complexity from O(2N) to O(N3). Furthermore, on top of BSMC, we propose an efficient skyline micro-cluster query algorithm (ESMC). In ESMC, we use the z-value index and propose a filter to remove the invalid micro-clusters, which reduces significant computation overhead. To reduce the memory overhead, we propose an incremental skyline query method. A comprehensive performance study is conducted on real datasets and the experimental results show that our proposed method, ESMC, can significantly improve the SMC query performance.

Self-supervised learning on graph aims to learn graph representations in an unsupervised manner. While graph contrastive learning (GCL - relying on graph augmentation for creating perturbation views of anchor graphs and maximizing/minimizing similarity for positive/negative pairs) is a popular self-supervised method, it faces challenges in finding label-invariant augmented graphs and determining the exact extent of similarity between sample pairs to be achieved. In this work, we propose an alternative self-supervised solution that (i) goes beyond the label invariance assumption without distinguishing between positive/negative samples, (ii) can calibrate the encoder for preserving not only the structural information inside the graph, but the matching information between different graphs, (iii) learns isometric embeddings that preserve the distance between graphs, a by-product of our objective. Motivated by optimal transport theory, this scheme relays on an observation that the optimal transport plans between node representations at the output space, which measure the matching probability between two distributions, should be consistent to the plans between the corresponding graphs at the input space. The experimental findings include: (i) The plan alignment strategy significantly outperforms the counterpart using the transport distance; (ii) The proposed model shows superior performance using only node attributes as calibration signals, without relying on edge information; (iii) Our model maintains robust results even under high perturbation rates; (iv) Extensive experiments on various benchmarks validate the effectiveness of the proposed method.

Given a graph, searching for a community containing a query vertex is a fundamental problem and has found many applications. Most existing community search models are based on non-attributed or vertex-attributed graphs. In many real-world graphs, however, the edges carry the richest information to describe the interactions between vertices; hence, it is important to take the information into account in community search. In this paper, we conduct a pioneer study on the community search on edge-attributed graphs. We proposed the Edge-Attributed Community Search (EACS) problem, which aims to extract a subgraph that contains the given query vertex while its edges have the maximum attribute similarity. We prove that the EACS problem is NP-hard and propose both exact and 2-approximation algorithms to address EACS. Our exact algorithms run up to 2320.34 times faster than the baseline solution. Our approximate algorithms further improve the efficiency by up to 2.93 times. We conducted extensive experiments to demonstrate the efficiency and effectiveness of our algorithms.

Nonoccurring behavior (NOB) studies have attracted the growing attention of scholars as a crucial part of behavioral science. As an effective method to discover both NOB and occurring behaviors (OB), negative sequential pattern (NSP) mining is successfully used in analyzing medical treatment and abnormal behavior patterns. At this time, NSP mining is still an active and challenging research domain. Most of the algorithms are inefficient in practice. Briefly, the key weaknesses of NSP mining are: 1) an inefficient positive sequential pattern (PSP) mining process, 2) a strict constraint of negative containment, and 3) the lack of an effective Negative Sequential Candidate (NSC) generation method. To address these weaknesses, we propose a highly efficient algorithm with improved techniques, named sc-NSP, to mine NSP efficiently. We first propose an improved PrefixSpan algorithm in the PSP mining process, which connects to a bitmap storage structure instead of the original structure. Second, sc-NSP loosens the frequency constraint and exploits the NSC generation method of positive and negative sequential patterns mining (PNSP) (a classic NSP mining method). Furthermore, a novel pruning strategy is designed to reduce the computational complexity of sc-NSP. Finally, sc-NSP obtains the support of NSC by using the most efficient bitwise-based calculation operation. Theoretical analyses show that sc-NSP performs particularly well on data sets with a large number of elements and items in sequence. Comparison and extensive experiments along with case studies on health data show that sc-NSP is 10 times more efficient than other state-of-the-art methods, and the number of NSPs obtained is 5 times greater than other methods.

The sequence analysis handles sequential discrete events and behaviors, which can be represented by temporal point processes (TPPs). However, TPP models only occurring events and behaviors. This article explores an efficient method for the negative sequential pattern (NSP) mining to leverage TPP in modeling both frequently occurring and nonoccurring events and behaviors. NSP mining is good at the challenging modeling of nonoccurrences of events and behaviors and their combinations with occurring events, with existing methods built on incorporating various constraints into NSP representations, e.g., simplifying NSP formulations and reducing computational costs. Such constraints restrict the flexibility of NSPs, and nonoccurring behaviors (NOBs) cannot be comprehensively exposed. This article addresses this issue by loosening some inflexible constraints in NSP mining and solves a series of consequent challenges. First, we provide a new definition of negative containment with the set theory according to the loose constraints. Second, an efficient method quickly calculates the supports of negative sequences. Our method only uses the information about the corresponding positive sequential patterns (PSPs) and avoids additional database scans. Finally, a novel and efficient algorithm, NegI-NSP, is proposed to efficiently identify highly valuable NSPs. Theoretical analyses, comparisons, and experiments on four synthetic and two real-life data sets clearly show that NegI-NSP can efficiently discover more useful NOBs.

Capturing the complex interactions of single nucleotide polymorphisms (SNPs) is considered essential for etiological analysis in genome-wide association analysis (GWAS). Evolutionary algorithms (EAs) have been extensively adopted for SNP-SNP interaction detection. Most existing EA-based methods focus on enhancing the search ability of EA itself. However, as the scale of SNP data further increases, the exponentially growing search space gradually becomes the dominant factor leading to the performance degradation of EA-based methods. To this end, a distributed evolutionary framework based on space partitioning (SP-EF) is proposed to detect SNP-SNP interactions on large-scale datasets. Distinct from the traditional population-distributed approaches, SP-EF first partitions the entire search space into several subspaces from the perspective of data. The space partitioning strategy is non-destructive since it guarantees that each feasible solution is assigned to a specific subspace. Thereafter, each subspace is explored by an EA optimizer independently and all the subspaces are optimized in parallel. Lastly, the final output is selected from the local optima in the historical search of each subspace. SP-EF can not only cope with the heavy computational burden of SNP combination evaluation but also enhance the diversity of the population to avoid local optima. Notably, SP-EF is load-balanced and scalable since it can flexibly partition the space according to the number of available computational nodes and the problem size. To show the practicability of SP-EF, we further design a discrete fireworks algorithm (DFWA) with three problem-guided operators as an EA optimizer. Experiments on artificial and real-world datasets demonstrate that our method significantly improves search speed and search accuracy.

Medical image segmentation is significant for diagnosis and prognosis. Inspired by the success of Transformer for Natural Language Processing, this paper presents DBT-UNETR, a novel double branch Transformer architecture with cross fusion for multi-scale feature representation, which enhances the model performance of 3D medical image segmentation. The DBT-UNETR consists of a single scale Transformer and a multiple scale Transformer to capture informative feature. These two branch features are cross fused and then they are combined together. Finally, these feature representations are sent to decoders via skip connection for final segmentation. Moreover, in order to further improve the model performance, an Early Fusion module is designed. Comprehensive experiments are conducted on public available dataset, Multi-Atlas Labeling Beyond The Cranial Vault (BTCV), and it demonstrates the proposed model outperforms the comparative baseline methods.

Semantic code search greatly facilitates software reuse, which enables users to find code snippets highly matching user-specified natural language queries. Due to the rich expressive power of code graphs (e.g., control-flow graph and program dependency graph), both of the two mainstream research works (i.e., multi-modal models and pre-trained models) have attempted to incorporate code graphs for code modelling. However, they still have some limitations: First, there is still much room for improvement in terms of search effectiveness. Second, they have not fully considered the unique features of code graphs.

BACKGROUND: In various fields, searching for the Longest Common Subsequences (LCS) of Multiple (i.e., three or more) sequences (MLCS) is a classic but difficult problem to solve. The primary bottleneck in this problem is that present state-of-the-art algorithms require the construction of a huge graph (called a direct acyclic graph, or DAG), which the computer usually has not enough space to handle. Because of their massive time and space consumption, present algorithms are inapplicable to issues with lengthy and large-scale sequences. RESULTS: A mini Directed Acyclic Graph (mini-DAG) model and a novel Path Elimination Algorithm are proposed to address large-scale MLCS issues efficiently. In mini-DAG, we employ the branch and bound approach to reduce paths during DAG construction, resulting in a very mini DAG (mini-DAG), which saves memory space and search time. CONCLUSION: Empirical experiments have been performed on a standard benchmark set of DNA sequences. The experimental results show that our model outperforms the leading algorithms, especially for large-scale MLCS problems.

Hundreds of thousands of single nucleotide polymorphisms (SNPs)are currently available for genome-wide association study (GWAS). Detecting disease-associated SNP-SNP interactions is considered an important way to capture the underlying genetic causes of complex diseases. In the combinatorially explosive search space, evolutionary algorithms are promising in solving this difficult problem because of their controllable time complexity. However, in existing evolutionary algorithms, some possible SNP-SNP interactions are evaluated multiple times by the fitness function. Such reevaluations not only waste computing resources but also make these algorithms easy to fall into local optima. To tackle this drawback, a progressive screening memetic algorithm (PSMA)is proposed in the paper. PSMA first represents all possible SNP-SNP interactions in a constructed graph. Then, the proposed algorithm uses the progressive screening strategy to guarantee that every possible SNP-SNP interaction can only be evaluated once by reducing the constructed graph. Furthermore, two types of local search algorithms are introduced to enhance the detecting power of PSMA. For detecting disease-associated SNP-SNP interactions, experimental results show that our proposed method outperforms other existing state-of-the-art methods in terms of accuracy and time.

Recently, the compacted de Bruijn graph (cDBG) of complete genome sequences was successfully used in read mapping due to its ability to deal with the repetitions in genomes. However, current approaches are not flexible enough to fit frequently building the graphs with different k-mer lengths. Instead of building the graph directly, how can we build the compacted de Bruijin graph of longer k-mer based on the one of short k-mer? In this article, we present StLiter, a novel algorithm to build the compacted de Bruijn graph either directly from genome sequences or indirectly based on the graph of a short k-mer. For 100 simulated human genomes, StLiter can construct the graph of k-mer length 15-18 in 2.5-3.2 hours with maximal ∼70GB memory in the case of without considering the reverese complements of the reference genomes. And it costs 4.5-5.9 hours when considering the reverse complements. In experiments, we compared StLiter with TwoPaCo, the state-of-art method for building the graph, on 4 datasets. For k-mer length 15-18, StLiter can build the graph 5-9 times faster than TwoPaCo using less maximal memory cost. For k-mer length larger than 18, given the graph of a short (k- x)-mer, such as x= 1-2, compared with TwoPaCo building the graph directly, StLiter can also build the graph more efficiently. The source codes of StLiter can be downloaded from web site https://github.com/BioLab-cz/StLiter.

Sequence alignment is an essential step in computational genomics. More accurate and efficient sequence pre-alignment methods that run before conducting expensive computation for final verification are still urgently needed. In this article, we propose a more accurate and efficient pre-alignment algorithm for sequence alignment, called DiagAF. Firstly, DiagAF uses a new lower bound of edit distance based on shift hamming masks. The new lower bound makes use of fewer shift hamming masks comparing with state-of-the-art algorithms such as SHD and MAGNET. Moreover, it takes account the information of edit distance path exchanging on shift hamming masks. Secondly, DiagAF can deal with alignments of sequence pairs with not equal length, rather than state-of-the-art methods just for equal length. Thirdly, DiagAF can align sequences with early termination for true alignments. In the experiment, we compared DiagAF with state-of-the-art methods. DiagAF can achieve a much smaller error rate than them, meanwhile use less time than them. We believe that DiagAF algorithm can further improve the performance of state-of-the-art sequence alignment softwares. The source codes of DiagAF can be downloaded from web site https://github.com/BioLab-cz/DiagAF.

Density Peaks (DP) Clustering organizes data into clusters by finding peaks in dense regions. This involves computing density ($\rho$) and distance ($\delta$) of every point. As such, though DP has been very effective in producing high quality clusters, their complexity is O($N^2$) where$N$is the number of data points. In this paper, we propose a fast distributed density peaks clustering algorithm, FDDP, based on the z-value index. In FDDP, we first employ the z-value index to map multi-dimensional data points into one dimensional space, and then range-partition the data according to the z-value to balance the load across the processing nodes. We ensure minimal overlapping range to handle computations at the boundary points. We also propose FC, an efficient algorithm that employs a forward computing strategy to calculate$\rho$linearly. Additionally, we propose another algorithm, CB, which uses a caching and efficient searching strategy to compute$\delta$. Moreover, FDDP is able to reduce the time complexity from$O(N^2)$to$O(N\cdot log(N))$. We provide a theoretical analysis of FDDP and evaluated FDDP empirically. Our experimental results show that FDDP outperforms the state-of-the-art algorithms significantly.

Density Peaks (DP) Clustering organizes data into clusters by finding peaks in dense regions. This involves computing density (ρ) and distance (δ) of every point, and the time complexity is O(N2) where N is the number of data points. In this paper, we propose a fast distributed density peaks clustering algorithm, FDDP, based on the z-value index. We also propose FC, an efficient algorithm that employs a forward computing strategy to calculate ρ linearly, and CB, which uses a caching and efficient searching strategy to compute δ. Our experimental results show that FDDP outperforms the state-of-the-art algorithms significantly.

Graphs are a powerful and versatile data structure that easily captures real life relationship. Multi-graph Multi-label learning (MGML) is a supervised learning task, which aims to learn a Multi-label classifier to label a set of objects of interest (e.g. image or text) with a bag-of-graphs representation. However, prior techniques on the MGML are developed based on transferring graphs into instances that does not fully utilize the structure information in the learning, and focus on learning the unseen labels only at the bag level. There is no existing work studying how to label the graphs within a bag that is of importance in many applications like image or text annotation. To bridge this gap, in this paper, we present a novel coarse and fine-grained Multi-graph Multi-label (cfMGML) learning framework which directly builds the learning model over the graphs and empowers the label prediction at both the coarse (aka. bag) level and fine-grained (aka. graph in each bag) level. In particular, given a set of labeled multi-graph bags, we design the scoring functions at both graph and bag levels to model the relevance between the label and data using specific graph kernels. Meanwhile, we propose a thresholding rank-loss objective function to rank the labels for the graphs and bags and minimize the hamming-loss simultaneously at one-step, which aims to address the error accumulation issue in traditional rank-loss algorithms. To tackle the non-convex optimization problem, we further develop an effective sub-gradient descent algorithm to handle high-dimensional space computation required in cfMGML. Experiments over various real-world datasets demonstrate cfMGML achieves superior performance than the state-of-arts algorithms.

Abbreviations are common in source code. Properly designed abbreviations may significantly facilitate typing, typesetting, and reading of lengthy source code. However, abbreviations, if used improperly, may also significantly reduce the readability and maintainability of source code. Although a few automated approaches have been proposed to suggest full terms for given abbreviations, to the best of our knowledge, there is no automated approaches to suggest whether abbreviations are used properly, i.e., whether they should be replaced with corresponding full terms. Notably, it is often challenging for inexperienced developers and maintainers to make such decisions. To this end, in this paper, we propose an automated approach to assisting developers and maintainers in making the decisions. The rationale of the approach is that abbreviations should not be expanded if the expansion would result in unacceptably lengthy identifiers or if developers/maintainers can easily figure out the meaning (full terms) of the abbreviations based on their domain knowledge or contexts of the abbreviations. From a corpus of programs, we leverage data mining techniques to discover common abbreviations that are frequently employed by various developers in similar contexts. The key of the data mining is to turn the problem of mining common abbreviations into the maximal clique problem that has been extensively studied. We suggest to not expand given abbreviation if it matches at least one of the discovered common abbreviations. From the same corpus, we also calculate the probability distribution for the length of different types of identifier, e.g., variable names and method names. The probability distribution specifies how likely an identifier of type T is composed of exactly n characters. Our heuristic is to not expand the abbreviation if the probability of its enclosing identifier would be reduced by the expansion. Finally, we also suggest to not expand the abbreviation if its full terms are contained in surrounding contexts of the abbreviation, i.e., tokens on the same source code line. Other abbreviations that do not receive suggestions from the proposed approach are expected to be replaced with their full terms. Our evaluation results on 1,818 abbreviations from five open-source applications suggest that the proposed approach is accurate with a high accuracy of 95%.

Social Internet of Things (SIoT) is the integration of social network (SN) and the Internet of Things (IOT). Community search in SIOT is an important problem beneficial to the resource/service discovery. In this article, we address the problem from the perspective of a dense subgraph query. Specifically, we propose a core-based static dense subgraph query and a graph kernel based dynamic dense subgraph query. The two algorithms consider the large scale and the time-varying nature of the SIoT, respectively. Unlike the existing works, the static method is inspired by the first-connection-last-expansion idea. Top-k neighbors of each query node are first found by a random walk. Then, all the query nodes and their top-k neighbors are connected as the core using Steiner tree expansion. The rank constraint random sampling is utilized to extend the core to a dense subgraph. Further, by leveraging a graph kernel index and identifying the updates that may affect the results, we conduct the dynamic query in an incremental update way instead of executing it from scratch. The experiments on synthetic and real datasets show that the proposed algorithms are both effective and efficient.

Genetic association study (GAS) is a promising tool for detecting and analyzing the cause of complex diseases. The extreme learning machine (ELM) has been successfully applied in a variety of research fields. Yet, as a black box method, it could not measure up to the task of GAS by itself, because it cannot tell us what causes the diseases, which is very crucial to the biologists. In this paper, we propose an ELM-based statistically significant pattern classification framework, which combines ELM with feature vector-based methods to solve the GAS problem efficiently and effectively. In particular: 1) a statistically significant pattern considering in terms of both family wise error rate (FWER) and false discovery rate (FDR) is proposed to control false positives in multiple hypothesis tests, which is necessary in GAS, but ignored by most of the existing methods; 2) an upper bound of the significance of a pattern is deduced to speed up FWER-constrained statistically significant pattern mining in a row enumeration way. Further, a space-effective grid index is devised to dramatically improves the efficiency of FDR-constrained pattern discovery; and 3) an ELM classifier is constructed based on the significant patterns. Comprehensive empirical studies on four real genotype datasets demonstrate much higher efficiency and effectiveness of our proposed framework with respect to the compared methods.

Community discovery is a popular way to solve the personal service recommendation problem and has recently attracted more and more attentions of the researchers. The communities are often practically overlapping with each other, thus more and more research focus on the problem of overlapping communities detection. A common drawback of the existing algorithms to this problem is the low efficiency when dealing the large scale network. In this paper, we propose a graph compression based overlapping communities discovery algorithm, which greatly enhances the power of handling large networks even using a single computer. First, a graph compression based social network model, namely agglomerative graph, is introduced, which is a lossless compression to the original network. Then, inspired by the idea of iteration based on the selected seeds, the algorithm expands the selected seeds to the communities by optimizing the proposed community fitness function iteratively. Finally, it merges the communities of high similarity with each other to get the final results. Since the network is lossless compressed, and massive redundant computations are avoided, the results can be exactly obtained in an efficient and effective way. The experiments based on both real and synthetic datasets demonstrate efficiency and effectiveness of the proposal method in detecting overlapping communities over large scale networks.

Advanced microarray technologies have enabled to simultaneously monitor the expression levels of all genes. An important problem in microarray data analysis is to discover phenotype structures. The goal is to 1) find groups of samples corresponding to different phenotypes (such as disease or normal), and 2) for each group of samples, find the representative expression pattern or signature that distinguishes this group from others. Some methods have been proposed for this issue, however, a common drawback is that the identified signatures often include a large number of genes but with low discriminative power. In this paper, we propose a $(g^\ast)$-sequence model to address this limitation, where the ordered expression values among genes are profitably utilized. Compared with the existing methods, the proposed sequence model is more robust to noise and allows to discover the signatures with more discriminative power using fewer genes. This is important for the subsequent analysis by the biologists. We prove that the problem of phenotype structure discovery is NP-complete. An efficient algorithm, FINDER, is developed, which includes three steps: 1) trivial $(g^\ast)$-sequences identifying, 2) phenotype structure discovery, and 3) refinement. Effective pruning strategies are developed to further improve the efficiency. We evaluate the performance of FINDER and the existing methods using both synthetic and real gene expression data sets. Extensive experimental results show that FINDER dramatically improves the accuracy of the phenotype structures discovered (in terms of both statistical and biological significance) and detects signatures with high discriminative power. Moreover, it is orders of magnitude faster than other alternatives.

Diagnostic genes refer to the genes closely related to a specific disease phenotype, the powers of which to distinguish between different classes are often high. Most methods to discovering the powerful diagnostic genes are either singleton discriminability-based or combination discriminability-based. However, both ignore the abundant interactions among genes, which widely exist in the real world. In this paper, we tackle the problem from a new point of view and make the following contributions: (1) we propose an EWave model, which profitably exploits the ordered expressions among genes based on the defined equivalent dimension group sequences taking into account the "noise" universal in the real data, (2) we devise a novel sequence rule, namely interesting non-redundant contrast sequence rule, which is able to capture the difference between different phenotypes in a high accuracy using as few as possible genes, (3) we present an efficient algorithm called NRMINER to find such rules. Unlike the conventional column enumeration and the more recent row enumeration, it performs a novel template-driven enumeration by making use of the special characteristic of micro array data modeled by EWave. Extensive experiments conducted on various synthetic and real datasets show that: (1) NRMINER is significantly faster than the competing algorithm by up to about one order of magnitude, (2) it provides a higher accuracy using fewer genes. Many diagnostic genes discovered by NRMINER are proved biologically related to some disease.

Spectral alignment, which studies the matching of ion peaks between the investigated spectrum and theoretical spectrum of peptide in the peptide database, is a very useful topic in computational proteomics. So far, the efficient, accurate and practical spectral alignment algorithm is still urgently needed due to its important application in the PTM unrestrictive peptide identification. In this paper, a multi-stage spectral alignment algorithm called MS-SA is proposed with the following two features: (a) it provided four different levels of alignment aims according to the alignment quality which can be specified by users, (b) it provided the capability of analyzing the detail modification types and locations for spectrum with multiple PTM sites. Therefore, MS-SA is of high practicality and can be applied to different specific applications such as being a filter in the large-scale database searching, a tool for detail modification types and locations analysis in small-scale spectral alignment and so on. A large number of experiments on real MS/MS data have been done for testing the performance of MS-SA. Also, the results of MS-SA are compared with those of same type of algorithms such as SA and SPC. The results show that MS-SA possesses strong practicality and outperforms the SA and SPC algorithms on several aspects.

Unlike pattern-based biclustering methods that focus on grouping objects in the same subset of dimensions, in this paper, we propose a novel model of coherent clustering for time-series gene expression data, i.e., time-delayed cluster (td-cluster). Under this model, objects can be coherent in different subsets of dimensions if these objects follow a certain time-delayed relationship. Such a cluster can discover the cycle time of gene expression, which is essential in revealing gene regulatory networks. This paper is the first attempt to mine time-delayed gene expression patterns from microarray data. A novel algorithm is also presented and implemented to mine all significant td-clusters. Our experimental results show following two results: 1) the td-cluster algorithm can detect a significant amount of clusters that were missed by previous models, and these clusters are potentially of high biological significance and 2) the td-cluster model and algorithm can easily be extended to 3-D gene x sample x time data sets to identify 3-D td-clusters.

Composite Web services are often long-running, loosely coupled and cross-organizational applications. They always run in a highly dynamic environment. For the applications and environment, advanced transaction support is required to ensure the quality of reliable execution. Towards composite service adaptive mechanism unavailable for lacking transaction support, this paper proposes a self-healing model for Web service reliable execution, which is an integration of flexible compensation service in selection and reselecting in execution. In order to make the composite service healing itself as quickly as possible and minimize the number of reselections, away of mining cascading scope of replacement in advance by considering full multi-relation among transaction Web services is proposed in this paper. Further more, a new comprehensive, objective QoS-driven service replacement model with compensation support is presented, and the self-healing algorithm is proposed. Experiments show that the model guarantees business process reliability.

Large-scale, rapid and accurate protein identification is the crucial basis for further protein analysis in computational proteomics. Searching protein database by use of the protein tandem mass spectra has been a standard solution for solving this problem. Though several algorithms have been proposed, more sensitive and accurate approaches are still needed. In this paper, an effective database search approach is proposed. Prior to searching sequence database, an approach based on a graph-theoretic model is proposed to infer the peptide sequence tag (PST) from the tandem mass spectra data which is the partial sequence of the peptide. Also, an index approach for the protein sequence database is proposed for speeding up the database search and filtering out the incorrect protein sequences. Then, a novel scoring method for evaluating the match between the peptide sequence tag and the protein sequence is proposed for improving the accuracy of the database search result. Finally, we develop an algorithm for solving the problem and implement it as a computer program PepCheck. All the results fore-Check are compared with those of the famous algorithms. Experimental results demonstrate that PepCheck is as accurate as or more accurate than them with the test datasets.

Clustering is a popular technique for analyzing microarray data sets, with n genes and m experimental conditions. As explored by biologists, there is a real need to identify coregulated gene clusters, which include both positive and negative regulated gene clusters. The existing pattern-based and tendency-based clustering approaches cannot directly be applied to find such coregulated gene clusters, because they are designed for finding positive regulated gene clusters. In this paper, in order to cluster coregulated genes, we propose a coding scheme that allows us to cluster two genes into the same cluster if they have the same code, where two genes that have the same code can be either positive or negative regulated. Based on the coding scheme, we propose a new algorithm for finding maximal subspace coregulated gene clusters with new pruning techniques. A maximal subspace coregulated gene cluster clusters a set of genes on a condition sequence such that the cluster is not included in any other subspace coregulated gene clusters. We conduct extensive experimental studies. Our approach can effectively and efficiently find maximal subspace coregulated gene clusters. In addition, our approach outperforms the existing approaches for finding positive regulated gene clusters.

Currently, pattern-based and tendency-based models are very popular for clustering co-regulated genes. In this paper, we propose another novel model, namely g-Cluster. The proposed model has the following advantages: (1) find positive and negative co-regulated genes in a shot, (2) get away from the restriction of magnitude transformation relationship among genes, and (3) guarantee quality of clusters and significance of regulations using a novel similarity measurement gCode and two user-specified thresholds, called wave constraint threshold and regulation threshold respectively. We also design a novel tree-based clustering algorithm, FBTD, combined with efficient pruning rules to identify all maximal g-Clusters. The extensive experiments on real and synthetic datasets show that (1) our algorithm can effectively and efficiently find an amount of co-regulated gene clusters missed by previous models, which are potentially of high biological significance, and (2) our algorithm is superior to the existing approaches