Jianxin Wang

TCS Journal 2026 Journal Article

Better guarantees for individual fairness k-median

• Di Wu
• Qilong Feng
• Jianxin Wang

• This paper extends and refines the conference version that appeared in Proceedings of the 17th International Conference on Combinatorial Optimization and Applications by strengthening the theoretical analysis and broadening the scope of the results. • First, we include full and detailed proofs for nearly all lemmas and claims that were previously omitted ( Sections 3 - 4 ). • Second, we extend our techniques to the k -means clustering formulation and establish analogous approximation guarantees ( Section 4 ). • Specifically, we show that our dynamic programming approach yields a ( 1 + ε )-approximation algorithm for the individual fairness k -means problem with a fairness violation of at most ( 2 + ε ). The individual fairness k -median problem is a commonly encountered problem in applications involving center location. It generalizes the standard k -median problem by assigning each point a fairness radius, allowing connections only to centers within a constant factor of this radius. In this paper, we present a randomized ( 1 + ϵ ) -approximation algorithm with a ( 2 + ϵ ) -fairness violation for the individual fairness k -median problem, improving upon the previous best approximation ratio of 7. 081 + ϵ and fairness violation of 3. We propose a new dynamic programming approach to deal with the challenges caused by the individual fairness requirements, which is the crucial step in getting the improved ratio.

JBHI Journal 2026 Journal Article

BiBLDR: Bidirectional Behavior Learning for Drug Repositioning

• Renye Zhang
• Mengyun Yang
• Qichang Zhao
• Jianxin Wang

Many deep learning methods represented by graph-based approaches achieve significant progress in drug repositioning. However, these graph-based methods face a critical limitation: they often fail in cold-start scenarios because the graph structure relies heavily on known association information from both the drug and disease sides. To address this challenge, we propose a bidirectional behavior learning strategy for drug repositioning, BiBLDR, an innovative framework that reformulates drug repositioning as a behavior sequence learning task. First, we construct bidirectional behavioral sequences based on drug and disease sides. Bidirectional behavior sequences ensure sufficient information for model learning in both drug and disease cold-start scenarios, while providing more precise feature representations for association prediction tasks. Subsequently, we propose a two-stage strategy for drug repositioning. In the first stage, we construct prototype spaces to characterise the representational attributes of drugs and diseases. In the second stage, these refined prototypes and bidirectional behavior sequence data are leveraged to predict potential drug-disease associations. This design allows BiBLDR to more robustly capture hidden pharmacological relationships from bidirectional behavioral sequences, delivering significant benefits in cold-start scenarios. Extensive experiments demonstrate that our method achieves state-of-the-art performance on benchmark datasets. Meanwhile, BiBLDR demonstrates significantly superior performance compared to previous methods in cold-start scenarios.

JBHI Journal 2026 Journal Article

Customized SAM-Med3D With Multi-View Representation Fusion and Age-Grade Stratified Loss for Glioma Survival Risk Prediction

• Xinyu Li
• Hulin Kuang
• Jin Liu
• Lanlan Wang
• Pengcheng Shu
• Mengshen He
• Jianxin Wang

Survival risk prediction is crucial for personalized treatment of gliomas. Medical image foundational models can explore complex medical features, which are critical for prognosis in gliomas. We propose SAM-Risk, which uses a customized SAM-Med3D with multi-view representation fusion and clinical knowledge-based age-grade stratified loss for glioma survival risk prediction. First, to utilize potential interactions between multiple views at an early stage, we design a 3D representation generation module that transforms 1D handcrafted radiomics and clinical features into 3D representations, which are fused with multimodal MRIs through a multi-view representation fusion module. The fused representation is fed into the customized SAM-Med3D, fine-tuned using LoRA and a disparity function to extract survival risk-related features. We design a feature refinement module to explore the inter-channel relationships among the outputs of the fine-tuned SAM-Med3D. Additionally, we propose an age-grade stratified loss based on glioma prognosis standards to make the predicted risk more consistent with clinical prior knowledge. Validated on two publicly available UCSF-PDGM and BraTS2020 datasets, SAM-Risk achieves a C-index of 75. 08% and 73. 67%, respectively, outperforming several survival risk prediction methods.

EAAI Journal 2026 Journal Article

Edge-Aware Transformer with Shared Axis Feature Alignment and Adaptive Self-Attention for Glioma Grading

• Adeel Ahmed Abbasi
• Hulin Kuang
• Xinyu Li
• Jianxin Wang

Accurate glioma grading from Magnetic Resonance Imaging (MRI) is critical for early diagnosis and effective treatment planning. Existing Artificial Intelligence (AI) methods, such as Convolutional Neural Networks (CNNs) and Vision Transformers (ViTs), struggle to capture edge details, overlook volumetric spatial context, and lack sensitivity to irregular shapes. Furthermore, inadequate self-attention mechanisms cause ViTs to fail to prioritize semantically meaningful tokens. These limitations can hinder both diagnostic accuracy and generalization. To address these challenges, we propose the Edge-Aware Transformer (EA-Trans) for glioma grading. Our approach integrates four key modules. First, the Edge Sensitive Tokenization (EST) module employs edge enhancement filters using depthwise CNNs to capture edge information. Second, the Shared Axis Spatial Features Alignment (SASFA) module processes MRI volumes along the depth, height, and width axes, preserving spatial consistency and context. Third, the Volumetric Multi-Scale Wavelet Transform Convolution (VMWTC) module employs Wavelet Transform Convolutions (WT-CNNs) to extract shape-sensitive multi-scale features. Fourth, the Adaptive Self-Attention (ASA) module integrates an Interquartile Range Token Selection (IQR-TS) strategy to focus on semantically relevant tokens. Experiments on the publicly available Brain Tumor Segmentation (BraTS2020) and University of California San Francisco Preoperative Diffuse Glioma MRI (UCSF-PDGM) datasets demonstrate that the proposed model achieves accuracies of 95. 7% and 95. 2%, respectively, outperforming 12 baseline methods. Notably, the model, with only 3. 176 million parameters and 1. 970 billion floating-point operations, enhances glioma grading accuracy, supporting AI-driven neuroimaging diagnostics in medical engineering. Interpretability analysis and application to Alzheimer’s disease classification further suggest its potential applicability to other neuroimaging tasks.

EAAI Journal 2026 Journal Article

Enhance energy efficient ethernet with reinforcement learning based periodic strategy

• Kai Wang
• Wanchun Jiang
• Renfu Yao
• Jiawei Huang
• Jianxin Wang

The strategy for Energy Efficient Ethernet determines when to enter and leave the power-saving mode, thereby directly impacting both the energy savings and the incurred latency of frames. However, due to the strong dependency of the strategy performance on the network traffic, existing strategies for Energy Efficient Ethernet need either (i) appropriately static parameter configuration under certain traffic loads, or (ii) parameter adaptation mechanisms based on the traffic prediction models that assume specific traffic distribution. Consequently, existing strategies hardly maintain consistent high performance under variable traffic in reality. To address this issue, we incorporate reinforcement learning into the design of the Energy Efficient Ethernet strategy and propose the reinforcement learning based periodic strategy (RLPS). Specifically, RLPS operates periodically with a dynamically adjusted cycle length. In each cycle, RLPS first transmits all buffered frames, then enters a selected power-saving mode for the remaining duration. Rather than directly outputting power-saving mode transition decisions, RLPS learns the time length of each cycle online for effectively capturing the impacts of traffic variation. This periodic approach enables power consumption to be optimized within each cycle using learned information while also reducing the overhead of online learning. Extensive simulations driven by synthetic traffic and real traces show that RLPS outperforms existing strategies, reducing the power consumption by up to ∼ 60. 8% while maintaining consistent high performance across diverse traffic loads and distributions.

JBHI Journal 2026 Journal Article

Mamba-Based Prototypical Contrastive Learning With Augmented Feature Separation for Common and Rare Arrhythmia Classification

• Fengyi Guo
• Ying An
• Jianxin Wang

Early diagnosis of arrhythmia, a common cardiovascular condition, is crucial for improving prognosis. Electrocardiogram (ECG) is widely used as a non-invasive diagnostic tool. However, Computer-Aided Diagnosis of rare arrhythmias faces significant challenges due to the severe scarcity of samples for these rare disease classes. To tackle this, we propose a Mamba-based Prototypical Contrastive Learning framework, which can simultaneously identify both common and rare classes under the setting of generalized Few-Shot Learning (FSL). It primarily consists of: (1) the Mamba-based Spatio-Temporal Feature Fusion Network (MST), which integrates spatial features from multi-scale convolutions and temporal dynamics from bidirectional Mamba for ECG modeling; (2) the Prototypical Contrastive Learning framework with Augmented Feature Separation (PCAS), which employs a prototype augmentation strategy with an Augmented Prototype Consistency Loss to optimize prototype representations, and an Separation-Tuned Contrastive Loss to enhance intra-class compactness and inter-class distinctnessy, mitigating the risk of class collapse. Extensive experiments on publicly available datasets PTBXL and Chapman demonstrate the effectiveness of MST-PCAS, achieving superior rare-class recognition accuracies of 79. 13% and 50. 72%, respectively, for ECG arrhythmia classification.

JBHI Journal 2026 Journal Article

MRLF-DDI: A Multi-View Representation Learning Framework for Drug-Drug Interaction Event Prediction

• Jian Zhong
• Haochen Zhao
• Xiao Liang
• Qichang Zhao
• Jianxin Wang

Accurately predicting drug-drug interaction events (DDIEs) is critical for improving medication safety and guiding clinical decision-making. However, existing graph neural network (GNN)-based methods often struggle to effectively integrate multi-view features and generalize to novel or understudied drugs. To address these limitations, we propose MRLF-DDI, a multi-view representation learning framework that jointly models information from individual drug features, local interaction contexts, and global interaction patterns. MRLF-DDI introduces the use of atom-level structural features enriched with bond angle information—marking the first incorporation of this geometry-aware feature in DDIE prediction. It further employs a multi-granularity GNN and a gated knowledge transfer strategy to enhance feature learning and cold-start generalization. Extensive experiments on benchmark datasets demonstrate that MRLF-DDI achieves superior performance in both warm-start and cold-start scenarios. Case studies and visualization analyses further highlight its practical utility in identifying clinically relevant DDIEs.

TCS Journal 2026 Journal Article

Parameterized algorithms and complexity for scheduling with precedence constraints and time windows

• Feng Shi
• Na Feng
• Yicong Zhu
• Jingyi Liu
• Jianxin Wang
• Guangwei Wu

In the paper, we study several variants of the Scheduling problem with precedence constraints and time windows defined on a task set S, denoted by P∣prec, ri, di ∣γ, and present improved fixed-parameter algorithms parameterized by the maximum processing time p max and the maximum number μ of overlapping time windows, defined as μ = max t ∈ N | { i ∈ S ∣ r i ≤ t < d i } |. Firstly, we propose an algorithm for P∣prec, ri, di ∣C max with time complexity O ( ( p max + 2 ) μ p max n 3 ), where the aim is to find a feasible schedule minimizing the makespan C max, and n is the number of tasks. This significantly improves the previously best-known algorithm for P∣prec, ri, di ∣⋆ with time complexity O ( p max 2 μ · 16 μ μ · n 3 ), where ⋆ indicates that the variant has no objective function and just decides the existence of a feasible schedule. Next, for the unit processing time case P ∣ p r e c, p i = 1, r i, d i ∣ C max, we develop an algorithm with time complexity O(2 μ μmn 3), where m is the number of machines, improving the previously best-known algorithm for P ∣ p r e c, p i = 1, r i, d i ∣ ★ with time complexity O(16 μ n 4). Then, we extend the two algorithms to the typed machine setting, i. e. , P ∣ M j ( t y p e ), p r e c, r i, d i ∣ C max and P ∣ M j ( t y p e ), p r e c, p i = 1, r i, d i ∣ C max, as well as to variants with other objective functions such as the maximum flow time F max and mean weighted flow time F mean. Finally, we show that the problem P ∣ o u t t r e e, p i = 1, d i ∣ ★, where the precedence constraints are restricted to an outtree, is para-NP-hard when parameterized by the maximum vertex out-degree Δ of the outtree.

TCS Journal 2026 Journal Article

Parameterized algorithms for the spanning forest isomorphism and containment on tree

• Jingyi Liu
• Xian Chen
• Yicheng Zheng
• Jianxin Wang
• Feng Shi

The Minimum Tree Cut/Paste Distance problem is a well-known NP-hard problem in comparative genomics and phylogenetics. However, its fixed-parameter tractability (FPT) with respect to the distance remains open. Within the paper, we study a simplified variant, the Rooted Spanning Forest Isomorphism on Tree problem (RSFITP), which asks whether a rooted forest F is a spanning forest of a rooted target tree T*. This problem is NP-hard but FPT with respect to the number k of trees in F. We present several FPT algorithms for RSFITP and its generalizations. First, we improve the best-known algorithm for RSFITP, reducing the runtime from 2 O(klog k) n 3 to O ( 4 k k 2 n 2 + n 3 ), where n is the size of the input instance. Second, we introduce the Rooted Spanning Forest Containment problem, which asks whether F contains k trees forming a spanning forest of T*, and provide an FPT algorithm with runtime O(25. 6 k kn 4), further improving it to 2 3. 03 k + 120 log 2 k n O ( 1 ) when T* is binary. Third, we study a variant where trees in F can be “used” infinitely many times and solve it in runtime n 2 + o ( 1 ). Besides the above work, we extend these algorithms to the unrooted versions of these problems with similar time complexity.

AAAI Conference 2026 Conference Paper

Perspective from a Broader Context: Can Room Style Knowledge Help Visual Floorplan Localization?

• Bolei Chen
• Shengsheng Yan
• Yongzheng Cui
• Jiaxu Kang
• Ping Zhong
• Jianxin Wang

Since a building's floorplan remains consistent over time and is inherently robust to changes in visual appearance, visual Floorplan Localization (FLoc) has received increasing attention from researchers. However, as a compact and minimalist representation of the building's layout, floorplans contain many repetitive structures (e.g., hallways and corners), thus easily result in ambiguous localization. Existing methods either pin their hopes on matching 2D structural cues in floorplans or rely on 3D geometry-constrained visual pre-trainings, ignoring the richer contextual information provided by visual images. In this paper, we suggest using broader visual scene context to empower FLoc algorithms with scene layout priors to eliminate localization uncertainty. In particular, we propose an unsupervised learning technique with clustering constraints to pre-train a room discriminator on self-collected unlabeled room images. Such a discriminator can empirically extract the hidden room type of the observed image and distinguish it from other room types. By injecting the scene context information summarized by the discriminator into an FLoc algorithm, the room style knowledge is effectively exploited to guide definite visual FLoc. We conducted sufficient comparative studies on two standard visual Floc benchmarks. Our experiments show that our approach outperforms state-of-the-art methods and achieves significant improvements in robustness and accuracy.

AAAI Conference 2026 Conference Paper

Towards Ultrasound-based Reliable Disease Diagnosis Using Causal Inference

• Bolei Chen
• Jiaxu Kang
• Haonan Yang
• Ping Zhong
• Yixiong Liang
• Rui Fan
• Jianxin Wang

Aligning the decision-making process of deep learning models with that of experienced sonographers is essential for ultrasound-based reliable disease diagnosis. Although existing methods have made significant progress in this aspect, their alignments are primarily associational rather than causal, leading to pseudo-correlations between features and diagnostic results. Such a biased diagnosis blindly models the sonographer's diagnostic skills and attention to specific patterns, which we argue hardly produces an AI diagnoser that is comparable to human experts. To address this issue, we propose a causality-based diagnostic framework to align the model's diagnostic behaviors with those of experts. Specifically, by delving into both conspicuous and inconspicuous confounders within the ultrasound images, the back-door and front-door adjustment causal learning modules are proposed to promote unbiased learning by mitigating potential pseudo-correlations. In addition, we integrate causal inference into a well-designed dual-branch model with feature interaction bridges for compatibility with multimodal ultrasound inputs. To fully evaluate our method, we conduct comparative studies on different diseases and ultrasound modalities. In particular, we publish a carefully constructed multimodal ultrasound dataset for breast lesion diagnosis and segmentation. Sufficient comparative and ablation studies on this dataset emphasize that our method outperforms state-of-the-art methods.

NeurIPS Conference 2025 Conference Paper

A Single-Swap Local Search Algorithm for k-Means of Lines

• Ting Liang
• Xiaoliang Wu
• Junyu Huang
• Jianxin Wang
• Qilong Feng

Clustering is a fundamental problem that has been extensively studied over past few decades, with most research focusing on point-based clustering such as $k$-means, $k$-median, and $k$-center. However, numerous real-world applications, such as motion analysis, computer vision, and missing data analysis, require clustering over structured data, including lines, time series and affine subspaces (flats), where traditional point-based clustering algorithms often fall short. In this paper, we study the $k$-means of lines problem, where the input is a set $L$ of lines in $\mathbb{R}^d$, and the goal is to find $k$ centers $C$ in $\mathbb{R}^d$ such that the sum of squared distances from each line in $L$ to its nearest center in $C$ is minimized. The local search algorithm is a well-established strategy for point-based $k$-means clustering, known for its efficiency and provable approximation guarantees. However, extending local search algorithm to the $k$-means of lines problem is nontrivial, as the capture relation used in point-based clustering does not generalize to the line setting. This is because that the point-to-line distance function lack the triangle inequality property that supports geometric analysis in point-based clustering. Moreover, since lines extend infinitely in space, it is difficult to identify effective swap points that can significantly reduce the clustering cost. To overcome above obstacles, we introduce a *proportional capture relation* that links optimal and current centers based the assignment proportions of lines, enabling a refined analysis that bypasses the triangle inequality barrier. We also introduce a *CrossLine* structure, which provides a principled discretization of the geometric space around line pairs, and ensures coverage of high-quality swap points essential for local search, thereby enabling effective execution of the local search process. Consequently, based on the proposed components, we develop the first single-swap local search algorithm for the $k$-means of lines problem, achieving a $(500+\varepsilon)$-approximation in polynomial time for low-dimensional Euclidean space.

TCS Journal 2025 Journal Article

Approximation algorithms for facility location and k-median with differential privacy

• Lu Wang
• Qilong Feng
• Jianxin Wang

In this paper we consider the problems of facility location and k-median with differential privacy in metric space, where a local search-based framework is proposed to solve the differential privacy issues. The approximation algorithm given for the facility location problem has a multiplicative error of 4 and an additive error of O ( Δ n 2 log ⁡ n log ⁡ ( n + f max Δ − 1 ) ε − 1 ), where f max is the maximum facility-opening cost, n is the number of clients, and Δ is the maximum distance between any two input points. For the k-median problem, our local search-based framework yields an approximation algorithm with a multiplicative error of 4 + ε and an additive error of O ( Δ k 2 log 2 ⁡ n ε − 2 ).

AAAI Conference 2025 Conference Paper

C2F-TP: A Coarse-to-Fine Denoising Framework for Uncertainty-Aware Trajectory Prediction

• Zichen Wang
• Hao Miao
• Senzhang Wang
• Renzhi Wang
• Jianxin Wang
• Jian Zhang

Accurately predicting the trajectory of vehicles is critically important for ensuring safety and reliability in autonomous driving. Although considerable research efforts have been made recently, the inherent trajectory uncertainty caused by various factors including the dynamic driving intends and the diverse driving scenarios still poses significant challenges to accurate trajectory prediction. To address this issue, we propose C2F-TP, a coarse-to-fine denoising framework for uncertainty-aware vehicle trajectory prediction. C2F-TP features an innovative two-stage coarse-to-fine prediction process. Specifically, in the spatial-temporal interaction stage, we propose a spatial-temporal interaction module to capture the inter-vehicle interactions and learn a multimodal trajectory distribution, from which a certain number of noisy trajectories are sampled. Next, in the trajectory refinement stage, we design a conditional denoising model to reduce the uncertainty of the sampled trajectories through a step-wise denoising operation. Extensive experiments are conducted on two real datasets NGSIM and highD that are widely adopted in trajectory prediction. The result demonstrates the effectiveness of our proposal.

JBHI Journal 2025 Journal Article

CA 2 CL: Cluster-Aware Adversarial Contrastive Learning for Pathological Image Analysis

• Junjian Li
• Hulin Kuang
• Jin Liu
• Hailin Yue
• Jianxin Wang

Pathological diagnosis assists in saving human lives, but such models are annotation hungry and pathological images are notably expensive to annotate. Contrastive learning could be a promising solution that relies only on the unlabeled training data to generate informative representations. However, the majority of current methods in contrastive learning have the following two issues: (1) positive samples produced through random augmentation are less challenging, and (2) false negative pairs problem caused by negative sampling bias. To alleviate the above issues, we propose a novel contrastive learning method called Cluster-Aware Adversarial Contrastive Learning (CA 2 CL). Specifically, a mixed data augmentation technique is provided to learn more transferable representations by generating more discriminative sample pairs. Furthermore, to mitigate the effects of inherent false negative pairs, we adopt a cluster-aware loss to identify similarities between instances and incorporate them into the process of contrastive learning. Finally, we generate challenging contrastive data pairs by adversarial learning, and adversarially learn robust representations in the representation space without the labeled training data, which aims to maximize the similarity between the augmented sample and the related adversarial sample. Our proposed CA 2 CL is evaluated on two public datasets: NCT-CRC-HE and PCam for the fine-tuning and linear evaluation tasks and on two other public datasets: GlaS and CARG for the detection and segmentation tasks, respectively. Extensive experimental results demonstrate the superior performance improvement of our method over several Self-supervised learning (SSL) methods and ImageNet pretraining particularly in scenarios with limited data availability for all four tasks.

NeurIPS Conference 2025 Conference Paper

Fast Local Search Algorithms for Clustering with Adaptive Sampling and Bandit Strategies

• Junyu Huang
• Zhen Zhang
• Beirong Cui
• Jianxin Wang
• Qilong Feng

Local search is a powerful clustering technique that provides high-quality solutions with theoretical guarantees. With distance-based sampling strategies, local search methods can achieve constant approximations for clustering with linear running time in data size. Despite their effectiveness, existing algorithms still face scalability issues as they require scanning the entire dataset for iterative center swaps. This typically leads to an O(ndk) running time, where n is the data size, d is the dimension, k is the number of clusters. To further improve the efficiency of local search algorithms, we propose new methods based on adaptive sampling and bandit strategies. Specifically, adaptive sampling can well approximate the distance-based sampling distribution without maintaining pairwise distances between data points and the centers, enabling fast and accurate sampling in sublinear time after an $\tilde{O}(nd)$ time preprocessing step. The bandit strategy models the best swap pair selection as a bandit problem, where a grouping strategy is proposed for fast identification of the optimal swap pair. With these techniques, our proposed algorithm can achieve constant approximation in expected running time $\tilde{O}(nd + k^4)$ under mild assumptions on optimal clusters and swap pair distributions. Our approach also extends naturally to the k-median objective, achieving constant approximation in expected running time $\tilde{O}(nd + \sqrt{n}k^3)$ without distributional assumptions. Empirical results demonstrate that our algorithm achieves up to 1000× speedup over existing local search methods on datasets with 100 million points, while delivering comparable clustering quality. Compared to coreset-based approaches, it provides up to around 80× speedup and consistently yields better clustering results.

JBHI Journal 2025 Journal Article

FedComDist: Towards Effective Personalized Federated Learning for Patient Outcome Prediction Using Multi-Center Electronic Medical Records

• Abdulrahman Al-Dailami
• Hulin Kuang
• Jianxin Wang

Accurate patient outcome predictions are essential for healthcare improvement, yet utilizing diverse medical data raises privacy and security concerns. Federated learning enables collaborative model training while preserving data privacy. However, the heterogeneity of clinical features among hospitals poses a challenge, leading to suboptimal performance in conventional federated learning. In response, we propose FedComDist, a personalized federated learning approach designed to maximize the use of heterogeneous features across hospitals for patient outcome prediction. Our approach incorporates a novel method for optimizing common global and distinct local parameters. We categorize input clinical features into two main groups—common and distinct—based on their presence across all hospitals and decouple the model parameters into common and distinct accordingly. The common features are used to train common global parameters, which are aggregated and optimized on the server, making them trainable across all hospitals. Meanwhile, the distinct features are used to train local parameters and optimized using the local dataset of each hospital. Our approach is evaluated on the eICU dataset, a publicly available multi-center clinical dataset, to predict patient clinical outcomes, specifically mortality and Length of Stay (LoS). The experimental results demonstrate the effectiveness of our approach compared to various federated learning methods and provide enhanced privacy through parameter decoupling.

AAAI Conference 2025 Conference Paper

Fully-Scalable Massively Parallel Algorithm for k-center with Outliers

• Di Wu
• Qilong Feng
• Junyu Huang
• Jinhui Xu
• Ziyun Huang
• Jianxin Wang

In this paper, we consider the k-center problem with outliers (the (k, z)-center problem) in the context of Massively Parallel Computation (MPC). Existing MPC algorithms for the (k, z)-center problem typically require Ω(k) local space per machine. While this may be feasible when k is small, these algorithms become impractical for large k, where each machine may lack sufficient space for computation. This motivates the study of fully-scalable algorithms with sublinear local space. We propose the first fully-scalable MPC algorithm for the (k, z)-center problem. The main challenge is to design an MPC algorithm that operates with sublinear local space for finding the inliers close to the optimal clustering centers, and ensuring the approximation loss remains bounded. To address this issue, we propose an iterative sampling-based algorithm with sublinear local space in the data size. A key component of our approach is an outliers-removal algorithm that adjusts the sample size in each iteration to select inliers as clustering centers. However, the number of discarded inliers increases with the iteration of the outliers-removal algorithm, making it difficult to bound. To address this, we propose a self-adaptive method that can automatically adjust sample size to account for different data distributions on each machine, ensuring a lower bound on the sampling success probability. With these techniques, we present an O(log^*n)-approximation MPC algorithm for the (k, z)-center problem in constant-dimensional Euclidean space. The algorithm discards at most (1 + ε)z outliers, completing in O(log log n) computation rounds while using Θ(n^δ) local space per machine.

NeurIPS Conference 2025 Conference Paper

Graph-Theoretic Insights into Bayesian Personalized Ranking for Recommendation

• Kai Zheng
• Jianxin Wang
• Jinhui Xu

Graph self-supervised learning (GSL) is essential for processing graph-structured data, reducing the need for manual labeling. Traditionally, this paradigm has extensively utilized Bayesian Personalized Ranking (BPR) as its primary loss function. Despite its widespread application, the theoretical analysis of its node relations evaluation have remained largely unexplored. This paper employs recent advancements in latent hyperbolic geometry to deepen our understanding of node relationships from a graph-theoretical perspective. We analyze BPR’s limitations, particularly its reliance on local connectivity through 2-hop paths, which overlooks global connectivity and the broader topological structure. To address these shortcomings, we purpose a novel loss function, BPR+, designed to encompass even-hop paths and better capture global connectivity and topological nuances. This approach facilitates a more detailed measurement of user-item relationships and improves the granularity of relationship assessments. We validate BPR+ through extensive empirical testing across five real-world datasets and demonstrate its efficacy in refining graph self-supervised learning frameworks. Additionally, we explore the application of BPR+ in drug repositioning, highlighting its potential to support pharmaceutical research and development. Our findings not only illuminate the success factors of previous methodologies but also offer new theoretical insights into this learning paradigm.

JBHI Journal 2025 Journal Article

GSST: Multimodal Graph-SMILES Fusion with Soft SMILES Tokens for Molecular Property Prediction

• Jie Zhou
• Qichang Zhao
• Pengcheng Shu
• Xiang Tang
• Jianxin Wang

Accurate prediction of molecular properties is essential for drug discovery. While single modal molecular representations have shown promising results, their generalizability remains limited due to data sparsity and the inherent incompleteness of single modal characterizations. To overcome these limitations, we propose GSST, a novel multimodal pretraining framework that integrates graph-based molecular representations with SMILES sequences through learnable soft SMILES tokens. At the core of GSST is the G2S-Former module, which injects topological information from the graph-based representation into the soft SMILES tokens to enable effective cross-modal interaction while preserving modality-specific features. Extensive experiments on the MoleculeNet and MoleculeACE benchmarks demonstrate that GSST consistently outperforms state-of-the-art methods in molecular property prediction and activity cliff assessment. These results underscore the importance of effective multimodal alignment in capturing shared molecular patterns and alleviating the challenges posed by limited labeled data. GSST represents a scalable and high-throughput approach with significant potential to advance drug discovery.

JBHI Journal 2025 Journal Article

Hierarchical Graph Representation Learning With Multi-Granularity Features for Anti-Cancer Drug Response Prediction

• Wei Peng
• Jiangzhen Lin
• Wei Dai
• Ning Yu
• Jianxin Wang

Patients with the same type of cancer often respond differently to identical drug treatments due to unique genomic traits. Accurately predicting a patient's response to drug is crucial in guiding treatment decisions, alleviating patient suffering, and improving cancer prognosis. Current computational methods utilize deep learning models trained on extensive drug screening data to predict anti-cancer drug responses based on features of cell lines and drugs. However, the interaction between cell lines and drugs is a complex biological process involving interactions across various levels, from internal cellular and drug structures to the external interactions among different molecules. To address this complexity, we propose a novel Hierarchical graph representation Learning with Multi-Granularity features (HLMG) algorithm for predicting anti-cancer drug responses. The HLMG algorithm combines features at two granularities: the overall gene expression and pathway substructures of cell lines, and the overall molecular fingerprints and substructures of drugs. Subsequently, it constructs a heterogeneous graph including cell lines, drugs, known cell line-drug responses, and the associations between similar cell lines and similar drugs. Through a graph convolutional network model, the HLMG learns the final cell line and drug representations by aggregating features of their multi-level neighbor in the heterogeneous graph. The multi-level neighbors consist of the node self, directly related drugs/cell lines, and indirectly related similar drugs/cell lines. Finally, a linear correlation coefficient decoder is employed to reconstruct the cell line-drug correlation matrix to predict anti-cancer drug responses. Our model was tested on the Genomics of Drug Sensitivity in Cancer (GDSC) and the Cancer Cell Line Encyclopedia (CCLE) databases. Results indicate that HLMG outperforms other state-of-the-art methods in accurately predicting anti-cancer drug responses.

AAAI Conference 2025 Conference Paper

Improving Cancer Gene Prediction by Enhancing Common Information Between the PPI Network and Gene Functional Association

• Chao Deng
• Hongdong Li
• Jianxin Wang

Identifying cancer genes is crucial for treatment and understanding pathogenesis. Recent methods typically leverage protein-protein interaction (PPI) networks or gene functional association data from annotated gene sets. There may be some shared neighborhood structure information between these two types of gene association data. While this common information may contain more accurate gene association information, existing methods often overlook this potential. To address this gap, we introduce DISFusion, which integrates multi-omics cancer data, PPI networks, and gene functional associations to identify cancer genes. A key innovation of DISFusion is the cross-view decorrelation loss, which enhances the common information between PPI networks and gene functional associations, thereby improving prediction accuracy. Extensive experiments indicate that DISFusion outperforms state-of-the-art methods and exhibits greater generalization ability. Moreover, analysis of CPTAC pan-cancer proteomic data highlights significant associations between the 30 novel cancer genes predicted by DISFusion and multiple cancer types, underscoring its practical utility. These findings validate the effectiveness of enhancing common information and provide new insights into cancer gene identification.

JBHI Journal 2025 Journal Article

Knowledge-Driven Graph Representation Learning for Myocardial Infarction Localization

• Fengyi Guo
• Ying An
• Hulin Kuang
• Jianxin Wang

The electrocardiogram (ECG) serves as a crucial tool for myocardial infarction (MI) localization, and deep learning methods have proven effective in assisting physicians with MI localization. Traditional MI localization methods are purely data-driven, and the quality of the data significantly affects the model’s performance, particularly in the localization of rare MI. We propose a knowledge-driven graph representation learning (KD-GRL) framework which is designed to guide deep learning models in identifying key features for MI localization using prior knowledge. The MI localization knowledge graph (KG) is constructed by integrating medical knowledge about MI localization, including ECG leads and morphological manifestations, the correlations between MI localization labels, diagnostic rules, and patient demographic information. KG effectively represents the relationships among various entities, which include ECG signal entities, morphological feature entities, and demographic feature entities. The embeddings of these entities are obtained using parallel patient multi-feature extractors. Additionally, a KG aggregation method based on edge relation projection (ERP) is proposed to aggregate the relational information in the MI localization KG. Ultimately, the MI localization task is transformed into a link prediction task between patient entity and localization label entities within the KG. We conduct experiments on two public datasets, PTB and PTBXL, achieving F1-scores of 48. 90% and 46. 06%, respectively, both surpassing the comparison methods. Additionally, due to the incorporation of diagnostic knowledge, our method outperforms the comparison methods in localizing rare MIs.

TCS Journal 2025 Journal Article

Minimum sum vertex cover: Difficulty of ordering

• Jingyi Liu
• Yixin Cao
• Ling Gai
• Jianxin Wang

A minimum sum vertex cover of a graph is a vertex cover associated with a permutation of its vertices that minimizes the total cost of covering all edges. The cost of an edge is defined by the smaller index of its two endpoints in the permutation. While this vertex cover is not necessarily the smallest possible, we show that its size, denoted as k, is polynomially bounded by the size of the minimum vertex covers. We note that finding an optimal ordering is NP-hard even when the vertex set of an optimal solution is given. We propose an O ( m + 2 k k! k 3 ) -time algorithm for finding a minimum sum vertex cover, where m is the size of the input graph, toward which we also show a ( k 2 + 2 k ) -vertex kernel.

IJCAI Conference 2025 Conference Paper

Parameterized Approximation Algorithm for Doubly Constrained Fair Clustering

• Xiaoliang Wu
• Qilong Feng
• Junyu Huang
• Jianxin Wang

Fair clustering has recently received considerable attention where numerous distinct fairness notions are developed. Despite being well-justified, these fairness notions are frequently studied in isolation, leaving the need to explore how they can be combined. Building on prior work, we focus on the doubly constrained fair clustering that incorporates two widely adopted demographic representation fairness notions in clustering: group fairness and data summarization fairness. Both fairness notions extend classical clustering formulation by associating each data point with a demographic label, where group fairness requires each cluster to proportionally reflect the population-level distribution of demographic groups, and data summarization fairness ensures the chosen facilities maintaining the population-level demographic representation of each group. In this paper, we study the Fixed-Parameter Tractable (FPT) approximation algorithms for doubly constrained fair clustering under the k-median objective, referred to Df-k-Med. The previous algorithms typically enumerate different demographic groups or construct fairness coreset, parameterized by both the number of opened facilities and demographic labels. By further leveraging the local fairness information, we propose a color-agnostic structural method that obtains the parameterized result independent of the number of demographic labels while effectively handling the combination of both fairness constraints. Specifically, we design a constant factor approximation for the Df-k-Med problem with fairness violation by one, which runs in FPT(k)-time, where k is the number of opened facilities.

JBHI Journal 2025 Journal Article

Predicting Clinical Anticancer Drug Response of Patients by Using Domain Alignment and Prototypical Learning

• Wei Peng
• Chuyue Chen
• Wei Dai
• Ning Yu
• Jianxin Wang

Anticancer drug response prediction is crucial in developing personalized treatment plans for cancer patients. However, High-quality patient anticancer drug response data are scarce and cell line data and patient data have different distributions, models trained solely on cell line data perform poorly. Some existing methods predict anticancer drug response by transferring knowledge from the cell line domain to the patient domain using transfer learning. However, the robustness of these classifiers is affected by anomalies in the cell line data, and they do not utilize the knowledge in the unlabeled target domain data. To this end, we proposed a model called DAPL to predict patient responses to anticancer drugs. The model extracts domain-invariant features from cell lines and patients by constructing multiple VAEs and extracts drug features using GNNs. These features are then combined for prototypical learning to train a classifier, resulting in better predictions of patient anticancer drug response. We used the cell line datasets CCLE and GDSC as source domains and the patient datasets TCGA and PDTC as target domains and conducted experiments. The results indicate that DAPL shows excellent performance in predicting patient anticancer drug response compared to other state-of-the-art methods.

TCS Journal 2024 Journal Article

Approximation algorithms for fair k-median problem without fairness violation

• Di Wu
• Qilong Feng
• Jianxin Wang

The fair k-median problem is one of the important clustering problems. The current best approximation ratio is 4. 675 for this problem with 1-fairness violation, which was proposed by Bercea et al. [APPROX-RANDOM'2019]. To our best knowledge, there is no available approximation algorithm for this problem without any fairness violation in doubling metrics. In this paper, we consider the fair k-median problem in doubling metrics and general metrics. We provide the first QPTAS for the fair k-median problem based on the hierarchical decomposition and dynamic programming process in doubling metrics. For applying a dynamic programming process to solve this problem, the distances from portals to facilities cannot be directly enumerated since each client may not be assigned to its closest open facility. To overcome the difficulties caused by the fairness constraints, we construct an auxiliary graph and use minimum weighted perfect matching to get the cost between the portals of each block and the ones in its children. In order to satisfy the fairness constraints, we bound the fairness constraints of each open facility in the leaves of the split-tree based on the relation between the subproblem and the subproblems of its children. To obtain the assignment of the given instance and remove the fairness violation, we construct a new b-value min-cost max-flow model based on the set of open facilities. For the fair k-median problem in general metrics, we present a polynomial-time approximation algorithm with ratio O ( log ⁡ k ). Our approximation algorithm for the fair k-median problem in doubling metrics is the first result for the corresponding problem without any fairness violation in doubling metrics.

NeurIPS Conference 2024 Conference Paper

Fine Tuning Out-of-Vocabulary Item Recommendation with User Sequence Imagination

• Ruochen Liu
• Hao Chen
• Yuanchen Bei
• Qijie Shen
• Fangwei Zhong
• Senzhang Wang
• Jianxin Wang

Recommending out-of-vocabulary (OOV) items is a challenging problem since the in-vocabulary (IV) items have well-trained behavioral embeddings but the OOV items only have content features. Current OOV recommendation models often generate 'makeshift' embeddings for OOV items from content features and then jointly recommend with the `makeshift' OOV item embeddings and the behavioral IV item embeddings. However, merely using the 'makeshift' embedding will result in suboptimal recommendation performance due to the substantial gap between the content feature and the behavioral embeddings. To bridge the gap, we propose a novel User Sequence IMagination (USIM) fine-tuning framework, which first imagines the user sequences and then refines the generated OOV embeddings with the user behavioral embeddings. Specifically, we frame the user sequence imagination as a reinforcement learning problem and develop a recommendation-focused reward function to evaluate to what extent a user can help recommend the OOV items. Besides, we propose an embedding-driven transition function to model the embedding transition after imaging a user. USIM has been deployed on a prominent e-commerce platform for months, offering recommendations for millions of OOV items and billions of users. Extensive experiments demonstrate that USIM outperforms traditional generative models in OOV item recommendation performance across traditional collaborative filtering and GNN-based collaborative filtering models.

EAAI Journal 2024 Journal Article

Intelligent void identification of particle packing system of caved ore and rock

• Hao Sun
• Zongsheng Dai
• Lishan Zhao
• Lichang Wei
• Junze Jia
• Shenggui Zhou
• Jianxin Wang
• Zhen Chi

Analyzing the void structure of the packing system of caved ore and rock and establishing the causal relationship between void structure and macroscopic properties are critical research areas in the field of gravity flow. However, the current method of analyzing void structure primarily involves manual threshold segmentation, leading to low analysis efficiency and the need for improved accuracy. This study introduces a novel approach using a dataset of two-dimensional Computed Tomography (CT) slices of an irregular limestone particle packing system. The primary goal is to enhance existing algorithms by focusing on data and network aspects to address the challenges in identifying this type of image dataset. As a result, a model named Data Attention gate with Recurrent Residual convolutional neural network based on U-net (DA2RU-net) is developed and evaluated for its convergence, accuracy, and robustness. The findings indicate the following: (1) To identify voids in the packing system of caved ore and rock using CT slices, it is advisable to employ 1000 images with dimensions between 300 and 400 pixels. It is essential to ensure that both large and small voids are represented in the image dataset. (2) The DA2RU-net model demonstrates superior performance with an average Dice value of 0. 9859 for identifying large voids and 0. 9654 for identifying small voids, surpassing other iterations of the U-net model and traditional algorithms. (3) The DA2RU-net model shows robustness to variations in brightness levels.

NeurIPS Conference 2024 Conference Paper

Linear Time Approximation Algorithm for Column Subset Selection with Local Search

• Yuanbin Zou
• Ziyun Huang
• Jinhui Xu
• Jianxin Wang
• Qilong Feng

The Column Subset Selection (CSS) problem has been widely studied in dimensionality reduction and feature selection. The goal of the CSS problem is to output a submatrix S, consisting of k columns from an n×d input matrix A that minimizes the residual error ‖A-SS^\dagger A‖_F^2, where S^\dagger is the Moore-Penrose inverse matrix of S. Many previous approximation algorithms have non-linear running times in both n and d, while the existing linear-time algorithms have a relatively larger approximation ratios. Additionally, the local search algorithms in existing results for solving the CSS problem are heuristic. To achieve linear running time while maintaining better approximation using a local search strategy, we propose a local search-based approximation algorithm for the CSS problem with exactly k columns selected. A key challenge in achieving linear running time with the local search strategy is how to avoid exhaustive enumerations of candidate columns for constructing swap pairs in each local search step. To address this issue, we propose a two-step mixed sampling method that reduces the number of enumerations for swap pair construction from O(dk) to k in linear time. Although the two-step mixed sampling method reduces the search space of local search strategy, bounding the residual error after swaps is a non-trivial task. To estimate the changes in residual error after swaps, we propose a matched swap pair construction method to bound the approximation loss, ensuring a constant probability of loss reduction in each local search step. In expectation, these techniques enable us to obtain the local search algorithm for the CSS problem with theoretical guarantees, where a 53(k+1)-approximate solution can be obtained in linear running time O(ndk^4\log k). Empirical experiments show that our proposed algorithm achieves better quality and time compared to previous algorithms on both small and large datasets. Moreover, it is at least 10 times faster than state-of-the-art algorithms across all large-scale datasets.

I&C Journal 2024 Journal Article

Modification problems toward proper (Helly) circular-arc graphs

• Yixin Cao
• Hanchun Yuan
• Jianxin Wang

We present a 9 k ⋅ n O ( 1 ) -time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and Crespelle et al. [Computer Science Review 2023]. Our structural study also implies parameterized algorithms for modification problems toward proper Helly circular-arc graphs.

AAMAS Conference 2024 Conference Paper

New Algorithms for Distributed Fair k -Center Clustering: Almost Accurate as Sequential Algorithms

• Xiaoliang Wu
• Qilong Feng
• Ziyun Huang
• Jinhui Xu
• Jianxin Wang

Fair clustering problems have been paid lots of attention recently. In this paper, we study the 𝑘-Center problem under the group fairness and data summarization fairness constraints, denoted as Group Fair 𝑘-Center (GF𝑘C) and Data Summarization Fair 𝑘-Center (DSF𝑘C), respectively, in the massively parallel computational (MPC) distributed model. The previous best results for the above two problems in the MPC model are a 9-approximation with violation 7 (WWW 2022) and a (17 + 𝜖)-approximation without fairness violation (ICML 2020), respectively. In this paper, we obtain a (3 + 𝜖)approximation with violation 1 for the GF𝑘C problem in the MPC model, which is almost as accurate as the best known approximation ratio 3 with violation 1 for the sequential algorithm of the GF𝑘C problem. Moreover, for the DSF𝑘C problem in the MPC model, we obtain a (4 + 𝜖)-approximation without fairness violation, which is very close to the best known approximation ratio 3 for the sequential algorithm of the DSF𝑘C problem. Empirical experiments show that our distributed algorithms perform better than existing state-of-the-art distributed methods for the above two problems.

TCS Journal 2024 Journal Article

New algorithms for fair k-center problem with outliers and capacity constraints

• Xiaoliang Wu
• Qilong Feng
• Jinhui Xu
• Jianxin Wang

The fair k-center problem has been paid lots of attention recently. In the fair k-center problem, we are given a set X of points in a metric space and a parameter k ∈ Z +, where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k-center problem objective is minimized. In this paper, we consider the fair k-center problem with outliers and capacity constraints, denoted as the fair k-center with outliers (FkCO) problem and the capacitated fair k-center (CFkC) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give ( 1 + ϵ ) -approximations with FPT time for the FkCO and CFkC problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the FkCO problem with some reasonable assumptions.

IJCAI Conference 2024 Conference Paper

SaSDim: Self-Adaptive Noise Scaling Diffusion Model for Spatial Time Series Imputation

• Shunyang Zhang
• Senzhang Wang
• Xianzhen Tan
• Renzhi Wang
• Ruochen Liu
• Jian Zhang
• Jianxin Wang

Spatial time series imputation is of great importance to various real-world applications. As the state-of-the-art generative models, diffusion models (e. g. CSDI) have outperformed statistical and autoregressive based models in time series imputation. However, diffusion models may introduce unstable noise owing to the inherent uncertainty in sampling, leading to the generated noise deviating from the intended Gaussian distribution. Consequently, the imputed data may deviate from the real data. To this end, we propose a Self-adaptive noise Scaling Diffusion Model named SaSDim for spatial time series imputation. Specifically, we introduce a novel Probabilistic High-Order SDE Solver Module to scale the noise following the standard Gaussian distribution. The noise scaling operation helps the noise prediction module of the diffusion model to more accurately estimate the variance of noise. To effectively learn the spatial and temporal features, a Spatial guided Global Convolution Module (SgGConv) for multi-periodic temporal dependencies learning with the Fast Fourier Transformation and dynamic spatial dependencies learning with dynamic graph convolution is also proposed. Extensive experiments conducted on three real-world spatial time series datasets verify the effectiveness of SaSDim.

AAAI Conference 2024 Conference Paper

SEC: More Accurate Clustering Algorithm via Structural Entropy

• Junyu Huang
• Qilong Feng
• Jiahui Wang
• Ziyun Huang
• Jinhui Xu
• Jianxin Wang

As one of the most popular machine learning tools in the field of unsupervised learning, clustering has been widely used in various practical applications. While numerous methods have been proposed for clustering, a commonly encountered issue is that the existing clustering methods rely heavily on local neighborhood information during the optimization process, which leads to suboptimal performance on real-world datasets. Besides, most existing clustering methods use Euclidean distances or densities to measure the similarity between data points. This could constrain the effectiveness of the algorithms for handling datasets with irregular patterns. Thus, a key challenge is how to effectively capture the global structural information in clustering instances to improve the clustering quality. In this paper, we propose a new clustering algorithm, called SEC. This algorithm uses the global structural information extracted from an encoding tree to guide the clustering optimization process. Based on the relation between data points in the instance, a sparse graph of the clustering instance can be constructed. By leveraging the sparse graph constructed, we propose an iterative encoding tree method, where hierarchical abstractions of the encoding tree are iteratively extracted as new clustering features to obtain better clustering results. To avoid the influence of easily misclustered data points located on the boundaries of the clustering partitions, which we call "fringe points", we propose an iterative pre-deletion and reassignment technique such that the algorithm can delete and reassign the "fringe points" to obtain more resilient and precise clustering results. Empirical experiments on both synthetic and real-world datasets demonstrate that our proposed algorithm outperforms state-of-the-art clustering methods and achieves better clustering performances. On average, the clustering accuracy (ACC) is increased by 1.7% and the normalized mutual information (NMI) by 7.9% compared with the current state-of-the-art (SOTA) algorithm on synthetic datasets. On real-world datasets, our method outperforms other clustering methods with an average increase of 12.3% in ACC and 5.2% in NMI, respectively.

EAAI Journal 2024 Journal Article

SemNav-HRO: A target-driven semantic navigation strategy with human–robot–object ternary fusion

• Bolei Chen
• Siyi Lu
• Ping Zhong
• Yongzheng Cui
• Yixiong Liang
• Jianxin Wang

Target-Driven Semantic Navigation (TDSN) shows great potential to be applied in intelligent domestic assistants supporting humans with daily activities. Although numerous methods have been explored to achieve efficient static TDSN, socially aware TDSN in dynamic and crowded scenarios remains challenging and has not been adequately investigated. The main challenges come from the complex human–robot interaction mechanisms and the semantic relation exploitation, which requires the robot to understand the surroundings and perform foresighted behaviors. In this paper, a TDSN strategy named SemNav-HRO is proposed by considering Human–Robot–Object (HRO) ternary feature fusion. Specifically, a Deep Reinforcement Learning (DRL) based Dual-Channel Value Estimation Network (DCVEN) is first proposed by integrating multi-granularity map features and social awareness to learn crowded TDSN strategies. Meanwhile, the tricky and socially aware TDSN problem is slackened by eliminating the dependence on costly features (e. g. , pedestrian speed) and introducing a pedestrian trajectory predictor. For the learning and evaluation of crowded TDSN strategies, a novel and semantic-rich simulator with complex layouts is constructed based on realistic domestic scenes, instead of employing the previous naive simulation settings. Experimental results show that our method relatively improves the navigation success rates by 12. 8 % ∼ 25. 5 % and 14. 6 % ∼ 19. 2 % compared to the baselines on the MP3D and Gibson datasets, respectively. Furthermore, we experimentally verify the promising generalization and interpretability of our method.

JBHI Journal 2023 Journal Article

BEA-Net: Body and Edge Aware Network With Multi-Scale Short-Term Concatenation for Medical Image Segmentation

• Hulin Kuang
• Yahui Wang
• Yixiong Liang
• Jin Liu
• Jianxin Wang

Medical image segmentation is indispensable for diagnosis and prognosis of many diseases. To improve the segmentation performance, this study proposes a new 2D body and edge aware network with multi-scale short-term concatenation for medical image segmentation. Multi-scale short-term concatenation modules which concatenate successive convolution layers with different receptive fields, are proposed for capturing multi-scale representations with fewer parameters. Body generation modules with feature adjustment based on weight map computing via enlarging the receptive fields, and edge generation modules with multi-scale convolutions using Sobel kernels for edge detection, are proposed to separately learn body and edge features from convolutional features in decoders, making the proposed network be body and edge aware. Based on the body and edge modules, we design parallel body and edge decoders whose outputs are fused to achieve the final segmentation. Besides, deep supervision from the body and edge decoders is applied to ensure the effectiveness of the generated body and edge features and further improve the final segmentation. The proposed method is trained and evaluated on six public medical image segmentation datasets to show its effectiveness and generality. Experimental results show that the proposed method achieves better average Dice similarity coefficient and 95% Hausdorff distance than several benchmarks on all used datasets. Ablation studies validate the effectiveness of the proposed multi-scale representation learning modules, body and edge generation modules and deep supervision.

JBHI Journal 2023 Journal Article

Exploring Contextual Relationships for Cervical Abnormal Cell Detection

• Yixiong Liang
• Shuo Feng
• Qing Liu
• Hulin Kuang
• Jianfeng Liu
• Liyan Liao
• Yun Du
• Jianxin Wang

Cervical abnormal cell detection is a challenging task as the morphological discrepancies between abnormal and normal cells are usually subtle. To determine whether a cervical cell is normal or abnormal, cytopathologists always take surrounding cells as references to identify its abnormality. To mimic these behaviors, we propose to explore contextual relationships to boost the performance of cervical abnormal cell detection. Specifically, both contextual relationships between cells and cell-to-global images are exploited to enhance features of each region of interest (RoI) proposal. Accordingly, two modules, dubbed as RoI-relationship attention module (RRAM) and global RoI attention module (GRAM), are developed and their combination strategies are also investigated. We establish a strong baseline by using Double-Head Faster R-CNN with a feature pyramid network (FPN) and integrate our RRAM and GRAM into it to validate the effectiveness of the proposed modules. Experiments conducted on a large cervical cell detection dataset reveal that the introduction of RRAM and GRAM both achieves better average precision (AP) than the baseline methods. Moreover, when cascading RRAM and GRAM, our method outperforms the state-of-the-art (SOTA) methods. Furthermore, we show that the proposed feature-enhancing scheme can facilitate image- and smear-level classification.

TCS Journal 2023 Journal Article

Improved approximation algorithms for solving the squared metric k-facility location problem

• Zhen Zhang
• Qilong Feng
• Junyu Huang
• Jianxin Wang

The squared metric k-facility location problem is a frequently encountered generalization of the k-means problem, where a specific cost should be paid for opening each facility. The current best approximation ratio for this problem is 44. 473 + ϵ, which was obtained using a local search algorithm. We advance the state-of-the-art for the problem by devising a Lagrangian relaxation-based algorithm that achieves an improved approximation guarantee of 36. 342 + ϵ. Our improvement comes from a new deterministic rounding approach, which exploits the properties of the squared metric.

NeurIPS Conference 2023 Conference Paper

Linear Time Algorithms for k-means with Multi-Swap Local Search

• Junyu Huang
• Qilong Feng
• Ziyun Huang
• Jinhui Xu
• Jianxin Wang

The local search methods have been widely used to solve the clustering problems. In practice, local search algorithms for clustering problems mainly adapt the single-swap strategy, which enables them to handle large-scale datasets and achieve linear running time in the data size. However, compared with multi-swap local search algorithms, there is a considerable gap on the approximation ratios of the single-swap local search algorithms. Although the current multi-swap local search algorithms provide small constant approximation, the proposed algorithms tend to have large polynomial running time, which cannot be used to handle large-scale datasets. In this paper, we propose a multi-swap local search algorithm for the $k$-means problem with linear running time in the data size. Given a swap size $t$, our proposed algorithm can achieve a $(50(1+\frac{1}{t})+\epsilon)$-approximation, which improves the current best result 509 (ICML 2019) with linear running time in the data size. Our proposed method, compared with previous multi-swap local search algorithms, is the first one to achieve linear running time in the data size. To obtain a more practical algorithm for the problem with better clustering quality and running time, we propose a sampling-based method which accelerates the process of clustering cost update during swaps. Besides, a recombination mechanism is proposed to find potentially better solutions. Empirical experiments show that our proposed algorithms achieve better performances compared with branch and bound solver (NeurIPS 2022) and other existing state-of-the-art local search algorithms on both small and large datasets.

ICLR Conference 2023 Conference Paper

Optimal Activation Functions for the Random Features Regression Model

• Jianxin Wang
• José Bento 0001

The asymptotic mean squared test error and sensitivity of the Random Features Regression model (RFR) have been recently studied. We build on this work and identify in closed-form the family of Activation Functions (AFs) that minimize a combination of the test error and sensitivity of the RFR under different notions of functional parsimony. We find scenarios under which the optimal AFs are linear, saturated linear functions, or expressible in terms of Hermite polynomials. Finally, we show how using optimal AFs impacts well established properties of the RFR model, such as its double descent curve, and the dependency of its optimal regularization parameter on the observation noise level.

JAAMAS Journal 2023 Journal Article

Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability

• Yongjie Yang
• Jianxin Wang

Abstract We study the parameterized complexity of winner determination problems for three prevalent k -committee selection rules, namely the minimax approval voting (MAV), the proportional approval voting (PAV), and the Chamberlin–Courant’s approval voting (CCAV). It is known that these problems are computationally hard. Although they have been studied from the parameterized complexity point of view with respect to several natural parameters, many of them turned out to be W[1] -hard or W[2] -hard. Aiming at obtaining plentiful fixed-parameter algorithms, we revisit these problems by considering more natural single parameters, combined parameters, and structural parameters.

TIST Journal 2023 Journal Article

STExplorer: A Hierarchical Autonomous Exploration Strategy with Spatio-temporal Awareness for Aerial Robots

• Bolei Chen
• Yongzheng Cui
• Ping Zhong
• Wang Yang
• Yixiong Liang
• Jianxin Wang

The autonomous exploration task we consider requires Unmanned Aerial Vehicles (UAVs) to actively navigate through unknown environments with the goal of fully perceiving and mapping the environments. Some existing exploration strategies suffer from rough cost budgets, ambiguous Information Gain (IG), and unnecessary backtracking exploration caused by Fragmented Regions (FRs). In our work, a hierarchical spatio-temporal-aware exploration framework is proposed to alleviate these problems. At the local exploration level, the Asymmetrical Traveling Salesman Problem (ATSP) is solved by comprehensively considering exploration time, IG, and heading consistency to avoid blindly exploring. Specifically, the exploration time is reasonably budgeted by fast marching in an artificial potential field. Meanwhile, a transformer-based map occupancy predictor is designed to assist in IG calculation by imagining spatial clues out of the Field of View (FoV), facilitating the prescient exploration. We verify that our local exploration is effective in alleviating the unnecessary back-and-forth movements caused by FRs and the interference of potential obstacle occlusion on the IG calculation. At the global exploration level, the classical Next Best View Points (NBVP) are generalized to Next Best Sub-Regions (NBSR) to choose informative sub-regions for further forward-looking exploration based on a well-designed utility function. Safe flight paths and dynamically feasible trajectories are reasonably generated throughout the exploration process by fast marching and B-spline curve optimization. Comparative simulations and benchmark tests demonstrate that our proposed exploration strategy is quite competitive in terms of exploration path length, total exploration time, and exploration ratio.

NeurIPS Conference 2023 Conference Paper

V-InFoR: A Robust Graph Neural Networks Explainer for Structurally Corrupted Graphs

• Senzhang Wang
• Jun Yin
• Chaozhuo Li
• Xing Xie
• Jianxin Wang

GNN explanation method aims to identify an explanatory subgraph which contains the most informative components of the full graph. However, a major limitation of existing GNN explainers is that they are not robust to the structurally corrupted graphs, e. g. , graphs with noisy or adversarial edges. On the one hand, existing GNN explainers mostly explore explanations based on either the raw graph features or the learned latent representations, both of which can be easily corrupted. On the other hand, the corruptions in graphs are irregular in terms of the structural properties, e. g. , the size or connectivity of graphs, which makes the rigorous constraints used by previous GNN explainers unfeasible. To address these issues, we propose a robust GNN explainer called V-InfoR. Specifically, a robust graph representation extractor, which takes insights of variational inference, is proposed to infer the latent distribution of graph representations. Instead of directly using the corrupted raw features or representations of each single graph, we sample the graph representations from the inferred distribution for the downstream explanation generator, which can effectively eliminate the minor corruption. We next formulate the explanation exploration as a graph information bottleneck (GIB) optimization problem. As a more general method that does not need any rigorous structural constraints, our GIB-based method can adaptively capture both the regularity and irregularity of the severely corrupted graphs for explanation. Extensive evaluations on both synthetic and real-world datasets indicate that V-InfoR significantly improves the GNN explanation performance for the structurally corrupted graphs. Code and dataset are available at https: //anonymous. 4open. science/r/V-InfoR-EF88

TCS Journal 2022 Journal Article

A divide-and-conquer approach for reconstruction of {C≥5}-free graphs via betweenness queries

• Guozhen Rong
• Yongjie Yang
• Wenjun Li
• Jianxin Wang

We study the query complexity of reconstructing { C ≥ 5 } -free graphs with respect to the betweenness oracle. In particular, we show that hidden { C ≥ 5 } -free graphs can be reconstructed by using O ( Δ 14 ⋅ log 2 ⁡ n + Δ 9 ⋅ n log 2 ⁡ n ) betweenness queries in expectation, where Δ denotes the maximum degree of the given graph and n denotes the number of vertices. In addition, we propose two improved randomized algorithms for two subclasses of { C ≥ 5 } -free graphs, namely the distance-hereditary graphs and the chordal graphs. For the former class, our algorithm uses O ( Δ 10 ⋅ log 2 ⁡ n + Δ 5 ⋅ n log 2 ⁡ n ) betweenness queries in expectation, and for the latter class, our algorithm uses O ( Δ 2 ⋅ n log 2 ⁡ n ) betweenness queries in expectation.

AIIM Journal 2022 Journal Article

Chinese clinical named entity recognition via multi-head self-attention based BiLSTM-CRF

• Ying An
• Xianyun Xia
• Xianlai Chen
• Fang-Xiang Wu
• Jianxin Wang

Clinical named entity recognition (CNER) is a fundamental step for many clinical Natural Language Processing (NLP) systems, which aims to recognize and classify clinical entities such as diseases, symptoms, exams, body parts and treatments in clinical free texts. In recent years, with the development of deep learning technology, deep neural networks (DNNs) have been widely used in Chinese clinical named entity recognition and many other clinical NLP tasks. However, these state-of-the-art models failed to make full use of the global information and multi-level semantic features in clinical texts. We design an improved character-level representation approach which integrates the character embedding and the character-label embedding to enhance the specificity and diversity of feature representations. Then, a multi-head self-attention based Bi-directional Long Short-Term Memory Conditional Random Field (MUSA-BiLSTM-CRF) model is proposed. By introducing the multi-head self-attention and combining a medical dictionary, the model can more effectively capture the weight relationships between characters and multi-level semantic feature information, which is expected to greatly improve the performance of Chinese clinical named entity recognition. We evaluate our model on two CCKS challenge (CCKS2017 Task 2 and CCKS2018 Task 1) benchmark datasets and the experimental results show that our proposed model achieves the best performance competing with the state-of-the-art DNN based methods.

NeurIPS Conference 2022 Conference Paper

Coded Residual Transform for Generalizable Deep Metric Learning

• Shichao Kan
• Yixiong Liang
• Min Li
• Yigang Cen
• Jianxin Wang
• Zhihai He

A fundamental challenge in deep metric learning is the generalization capability of the feature embedding network model since the embedding network learned on training classes need to be evaluated on new test classes. To address this challenge, in this paper, we introduce a new method called coded residual transform (CRT) for deep metric learning to significantly improve its generalization capability. Specifically, we learn a set of diversified prototype features, project the feature map onto each prototype, and then encode its features using their projection residuals weighted by their correlation coefficients with each prototype. The proposed CRT method has the following two unique characteristics. First, it represents and encodes the feature map from a set of complimentary perspectives based on projections onto diversified prototypes. Second, unlike existing transformer-based feature representation approaches which encode the original values of features based on global correlation analysis, the proposed coded residual transform encodes the relative differences between the original features and their projected prototypes. Embedding space density and spectral decay analysis show that this multi perspective projection onto diversified prototypes and coded residual representation are able to achieve significantly improved generalization capability in metric learning. Finally, to further enhance the generalization performance, we propose to enforce the consistency on their feature similarity matrices between coded residual transforms with different sizes of projection prototypes and embedding dimensions. Our extensive experimental results and ablation studies demonstrate that the proposed CRT method outperform the state-of-the-art deep metric learning methods by large margins and improving upon the current best method by up to 4. 28% on the CUB dataset.

IJCAI Conference 2022 Conference Paper

FLS: A New Local Search Algorithm for K-means with Smaller Search Space

• Junyu Huang
• Qilong Feng
• Ziyun Huang
• Jinhui Xu
• Jianxin Wang

The k-means problem is an extensively studied unsupervised learning problem with various applications in decision making and data mining. In this paper, we propose a fast and practical local search algorithm for the k-means problem. Our method reduces the search space of swap pairs from O(nk) to O(k^2), and applies random mutations to find potentially better solutions when local search falls into poor local optimum. With the assumption of data distribution that each optimal cluster has "average" size of \Omega(n/k), which is common in many datasets and k-means benchmarks, we prove that our proposed algorithm gives a (100+\epsilon)-approximate solution in expectation. Empirical experiments show that our algorithm achieves better performance compared to existing state-of-the-art local search methods on k-means benchmarks and large datasets.

JBHI Journal 2022 Journal Article

Multimodal Disentangled Variational Autoencoder With Game Theoretic Interpretability for Glioma Grading

• Jianhong Cheng
• Min Gao
• Jin Liu
• Hailin Yue
• Hulin Kuang
• Jun Liu
• Jianxin Wang

Effective fusion of multimodal magnetic resonance imaging (MRI) is of great significance to boost the accuracy of glioma grading thanks to the complementary information provided by different imaging modalities. However, how to extract the common and distinctive information from MRI to achieve complementarity is still an open problem in information fusion research. In this study, we propose a deep neural network model termed as multimodal disentangled variational autoencoder (MMD-VAE) for glioma grading based on radiomics features extracted from preoperative multimodal MRI images. Specifically, the radiomics features are quantized and extracted from the region of interest for each modality. Then, the latent representations of variational autoencoder for these features are disentangled into common and distinctive representations to obtain the shared and complementary data among modalities. Afterwards, cross-modality reconstruction loss and common-distinctive loss are designed to ensure the effectiveness of the disentangled representations. Finally, the disentangled common and distinctive representations are fused to predict the glioma grades, and SHapley Additive exPlanations (SHAP) is adopted to quantitatively interpret and analyze the contribution of the important features to grading. Experimental results on two benchmark datasets demonstrate that the proposed MMD-VAE model achieves encouraging predictive performance (AUC: 0. 9939) on a public dataset, and good generalization performance (AUC: 0. 9611) on a cross-institutional private dataset. These quantitative results and interpretations may help radiologists understand gliomas better and make better treatment decisions for improving clinical outcomes.

TCS Journal 2021 Journal Article

A new approximation algorithm for contig-based genomic scaffold filling

• Guanlan Tan
• Qilong Feng
• Xiangzhong Meng
• Jianxin Wang

Genomic Scaffold Filling problem forms an important class of problems, and has been paid lots of attention in the literature. In this paper, we study one of the Genomic Scaffold Filling problems, called One-sided-GSF-max-BC problem. In this paper, we give a new approximation algorithm for the problem. For any given instance of the One-sided-GSF-max-BC problem, auxiliary graphs are constructed based on the given instance and the relation between maximum matching in auxiliary graphs and optimal solution is studied, which results in an approximation algorithm with ratio 2. 57.

I&C Journal 2021 Journal Article

An improved FPT algorithm for the flip distance problem

• Qilong Feng
• Shaohua Li
• Xiangzhong Meng
• Jianxin Wang

Given a set P of points in the Euclidean plane and two triangulations of P, the flip distance between these two triangulations is the minimum number of flips required to transform one triangulation into the other. The Parameterized Flip Distance problem is to decide if the flip distance between two given triangulations is equal to a given integer k. The previous best FPT algorithm runs in time O ⁎ ( k ⋅ c k ) ( c ≤ 2 × 14 11 ), where each step has fourteen possible choices, and the length of the action sequence is bounded by 11k. By analyzing the underlying properties of the flip sequence, each step of our algorithm has only five possible choices. Based on an auxiliary graph G, we prove that the length of the action sequence for our algorithm is bounded by 2 | G |. As a result, we present an FPT algorithm running in time O ⁎ ( k ⋅ 32 k ).

JBHI Journal 2021 Journal Article

Deep Matrix Factorization Improves Prediction of Human CircRNA-Disease Associations

• Chengqian Lu
• Min Zeng
• Fuhao Zhang
• Fang-Xiang Wu
• Min Li
• Jianxin Wang

In recent years, more and more evidence indicates that circular RNAs (circRNAs) with covalently closed loop play various roles in biological processes. Dysregulation and mutation of circRNAs may be implicated in diseases. Due to its stable structure and resistance to degradation, circRNAs provide great potential to be diagnostic biomarkers. Therefore, predicting circRNA-disease associations is helpful in disease diagnosis. However, there are few experimentally validated associations between circRNAs and diseases. Although several computational methods have been proposed, precisely representing underlying features and grasping the complex structures of data are still challenging. In this paper, we design a new method, called DMFCDA (Deep Matrix Factorization CircRNA-Disease Association), to infer potential circRNA-disease associations. DMFCDA takes both explicit and implicit feedback into account. Then, it uses a projection layer to automatically learn latent representations of circRNAs and diseases. With multi-layer neural networks, DMFCDA can model the non-linear associations to grasp the complex structure of data. We assess the performance of DMFCDA using leave-one cross-validation and 5-fold cross-validation on two datasets. Computational results show that DMFCDA efficiently infers circRNA-disease associations according to AUC values, the percentage of precisely retrieved associations in various top ranks, and statistical comparison. We also conduct case studies to evaluate DMFCDA. All results show that DMFCDA provides accurate predictions.

TCS Journal 2021 Journal Article

Fixed-parameter tractability for the Tree Assembly problem

• Feng Shi
• Jie You
• Zhen Zhang
• Jingyi Liu
• Jianxin Wang

Calculating the “distance” between two given objects with respect to a designated “editing” operation is a hot research area in bioinformatics, where the “distance” is always defined as the minimum number of the “editing” operations required to transform one object into the other one. One of the famous problems in the area is the Minimum Common String Partition problem, which is the simplified variant of the Minimum Tree Cut/Paste Distance problem. Within the paper, we consider another simplified variant of the Minimum Tree Cut/Paste Distance problem, named Tree Assembly problem, of which the edge-deletion operations are specified. More specifically, the Tree Assembly problem aims to transform a given forest into a given tree by edge-addition operations only. In our investigations, we present a fixed-parameter algorithm with runtime 2 O ( k log ⁡ k ) n O ( 1 ) for the Tree Assembly problem, where k is the number of trees in the given forest, and n is the number of nodes in the given tree and forest. Additionally, we give a polynomial time algorithm for a restricted variant of the problem.

TCS Journal 2021 Journal Article

Improved approximation for prize-collecting red-blue median

• Zhen Zhang
• Yutian Guo
• Junyu Huang
• Jianxin Wang
• Feng Shi

The red-blue median problem considers a set of red facilities, a set of blue facilities, and a set of clients located in some metric space. The goal is to open k r red facilities and k b blue facilities such that the sum of the distance from each client to its nearest opened facility is minimized, where k r, k b ≥ 0 are two given integers. Designing approximation algorithms for this problem remains an active area of research due to its applications in various fields. However, in many applications, the existence of noisy data poses a big challenge for the problem. In this paper, we consider the prize-collecting red-blue median problem, where the noisy data can be removed by paying a penalty cost. The current best approximation guarantee for the prize-collecting red-blue median problem is a ratio of 24, which was obtained by LP-rounding. We deal with this problem using a local search algorithm. We construct a layered structure of the swap pairs, which yields a ( 9 + ϵ ) -approximation for the prize-collecting red-blue median problem. Our techniques generalize to a more general prize-collecting τ-color median problem, where the facilities have τ different types, and give a ( 4 τ + 1 + ϵ ) -approximation for the case where τ is a constant.

TCS Journal 2021 Journal Article

On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering

• Yunlong Liu
• Jie Chen
• Jingui Huang
• Jianxin Wang

Given a graph G = ( V, E ) with a vertex ordering ≺, the fixed-order book thickness problem asks whether there is a page assignment σ such that 〈 ≺, σ 〉 is a k-page book embedding of G. This problem is NP-complete even for any fixed k greater than 3. Recently, Bhore et al. (2019, 2020) [1, 2] presented a parameterized algorithm with respect to the pathwidth κ of the vertex ordering. In this paper, we first re-analyze the running time for Bhore et al. 's algorithm, and prove a bound of 2 O ( κ 2 ) ⋅ | V | improving Bhore et al. 's bound of κ O ( κ 2 ) ⋅ | V |. Then, we show that fixed-order book thickness parameterized by the pathwidth of the vertex ordering does not admit a polynomial kernel unless NP ⊆ coNP/poly. Finally, we show that a generalized fixed-order book thickness problem, in which a budget of at most c crossings over all pages was given, admits a parameterized algorithm running in time ( c + 2 ) O ( κ 2 ) ⋅ | V |.

TCS Journal 2021 Journal Article

Reconstruction and verification of chordal graphs with a distance oracle

• Guozhen Rong
• Wenjun Li
• Yongjie Yang
• Jianxin Wang

A hidden graph is a graph whose edge set is hidden. A distance oracle of a graph G is a black-box that receives two vertices of G and outputs the distance between the two vertices. Given a hidden graph, the reconstruction problem aims to identify the edges of the hidden graph by accessing a distance oracle, and the verification problem aims to check whether the hidden graph is equal to another given graph (not hidden). If the hidden graph G is a connected chordal graph, a Las Vegas reconstruction algorithm using O ( Δ 3 2 Δ ⋅ n ( 2 Δ + log 2 ⁡ n ) log ⁡ n ) distance queries is known, where Δ is the maximum degree of G and n is the number of vertices of G. Improving upon this result, we present a reconstruction algorithm using only O ( Δ 2 n log 2 ⁡ n ) distance queries. As a byproduct, we obtain a deterministic algorithm for the verification of chordal graphs with O ( Δ 2 n log ⁡ n ) distance queries. Additionally, we derive a deterministic algorithm of reconstructing connected interval graphs using only O ( Δ n ) distance queries, and prove that reconstructing or verifying a connected interval graph needs Ω ( Δ n ) distance queries, which implies that this algorithm is the best possible in terms of the number of distance queries needed.

TCS Journal 2021 Journal Article

Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problem

• Feng Shi
• Frank Neumann
• Jianxin Wang

The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop ( 1, 2 )-Minimum Spanning Tree problem (abbr. 2H-( 1, 2 )-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-( 1, 2 )-MSTP (including the ( 1 + 1 ) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i. e. , the expected number of fitness evaluations) to obtain a 3 2 -approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the ( 1 + 1 ) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a 3 2 -approximate solution, which is better than the above mentioned ones.

TCS Journal 2020 Journal Article

An approximation algorithm for the l-pseudoforest deletion problem

• Mugang Lin
• Qilong Feng
• Bin Fu
• Jianxin Wang

An l-pseudoforest is a graph each of whose connected components is at most l edges removal being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted graph G = ( V, E ) such that the remaining graph G [ V ∖ P ] is an l-pseudoforest. The Feedback Vertex Set problem is a special case of the l-Pseudoforest Deletion problem with l = 0. In this paper, we present a polynomial time 4l-approximation algorithm for the l-Pseudoforest Deletion problem with l ≥ 1 by using the local ratio technique. When l = 1, we get a better approximation ratio 2 for the problem by further analyzing the local ratio, which matches the current best constant approximation factor for the Feedback Vertex Set problem.

TCS Journal 2020 Journal Article

An improved kernel for Max-Bisection above tight lower bound

• Qilong Feng
• Senmin Zhu
• Jianxin Wang

We study kernelizations for Max-Bisection above Tight Lower Bound, which is to decide if a given graph G = ( V, E ) admits a bisection with at least ⌈ | E | / 2 ⌉ + k crossing edges. The best known kernel for this problem has 16k vertices. Based on the Gallai–Edmonds decomposition, we divide the vertices of G into several categories and study the roles of vertices in each category for obtaining a larger number of crossing edges. By making use of the properties of maximum matchings in G, graph G is partitioned into a set of blocks, and each block in G is closely related to the number of crossing edges of a bisection of G. By analyzing the number of crossing edges in blocks, an improved kernel of 8k vertices is presented.

TCS Journal 2020 Journal Article

Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition

• Jie You
• Feng Shi
• Jianxin Wang
• Qilong Feng

Computational biology is mainly concerned with discovering an object from a given set of observations that are supposed to be good approximations of the real object. Two important steps here are to define a way to measure the distance between different objects and to calculate the distance between two given objects. The main problem is then to find an object that has the minimum total distance to the given observations. We study two NP-hard problems formulated in computational biology. The minimum tree cut/paste distance problem asks for the minimum number of cut/paste operations we need to transform a tree to another tree. The minimum common integer partition problem asks for a minimum-cardinality integer partition of a number that refines two given integer partitions of the same number. We give parameterized algorithms for both problems.

TCS Journal 2020 Journal Article

Improved approximation algorithms for two-stage flowshops scheduling problem

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

This paper considers the problem of scheduling n two-stage jobs on m two-stage flowshops so as to minimize the makespan. By studying the relationship between the problem and the classical makespan problem, we prove that if there is an α-approximation algorithm for the makespan problem, then for the general case of the problem, we can construct a 2α-approximation algorithm, and for two restricted cases which are of practical importance, we can construct an ( α + 1 / 2 ) -approximation algorithm. As a result, by employing the polynomial-time approximation scheme for the makespan problem, we get a ( 2 + ϵ ) -approximation algorithm for the general case and a ( 1. 5 + ϵ ) -approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2. 6 and 11/6 respectively.

JBHI Journal 2020 Journal Article

miRTMC: A miRNA Target Prediction Method Based on Matrix Completion Algorithm

• Hui Jiang
• Mengyun Yang
• Xiang Chen
• Min Li
• Yaohang Li
• Jianxin Wang

microRNAs (miRNAs) are small non-coding RNAs which modulate the stability of gene targets and their rates of translation into proteins at transcriptional level and post-transcriptional level. miRNA dysfunctions can lead to human diseases because of dysregulation of their targets. Correct miRNA target prediction will lead to better understanding of the mechanisms of human diseases and provide hints on curing them. In recent years, computational miRNA target prediction methods have been proposed according to the interaction rules between miRNAs and targets. However, these methods suffer from high false positive rates due to the complicated relationship between miRNAs and their targets. The rapidly growing number of experimentally validated miRNA targets enables predicting miRNA targets with high precision via accurate data analysis. Taking advantage of these known miRNA targets, a novel recommendation system model (miRTMC) for miRNA target prediction is established using a new matrix completion algorithm. In miRTMC, a heterogeneous network is constructed by integrating the miRNA similarity network, the gene similarity network, and the miRNA-gene interaction network. Our assumption is that the latent factors determining whether a gene is the target of miRNA or not are highly correlated, i. e. , the adjacency matrix of the heterogeneous network is low-rank, which is then completed by using a nuclear norm regularized linear least squares model under non-negative constraints. Alternating direction method of multipliers (ADMM) is adopted to numerically solve the matrix completion problem. Our results show that miRTMC outperforms the competing methods in terms of various evaluation metrics. Our software package is available at https://github.com/hjiangcsu/miRTMC.

JBHI Journal 2020 Journal Article

Multi-Receptive-Field CNN for Semantic Segmentation of Medical Images

• Liangliang Liu
• Fang-Xiang Wu
• Yu-Ping Wang
• Jianxin Wang

The context-based convolutional neural network (CNN) is one of the most well-known CNNs to improve the performance of semantic segmentation. It has achieved remarkable success in various medical image segmentation tasks. However, extracting rich and useful context information from complex and changeable medical images is a challenge for medical image segmentation. In this study, a novel Multi-Receptive-Field CNN (MRFNet) is proposed to tackle this challenge. MRFNet offers the optimal receptive field for each subnet in the encoder-decoder module (EDM) and generates multi-receptive-field context information at the feature map level. Moreover, MRFNet fuses these multi-feature maps by the concatenation operation. MRFNet is evaluated on 3 public medical image data sets, including SISS, 3DIRCADb, and SPES. Experimental results show that MRFNet achieves the outstanding performance on all 3 data sets, and outperforms other segmentation methods on 3DIRCADb test set without pre-training the model.

TCS Journal 2020 Journal Article

New kernels for several problems on planar graphs

• Guanlan Tan
• Qilong Feng
• Beilin Zhuo
• Neng Huang
• Jianxin Wang

In this paper, we study the kernelization of the Induced Matching problem on planar graphs, the Parameterized Planar 4-Cycle Transversal problem and the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem. For the Induced Matching problem on planar graphs, based on the Gallai-Edmonds decomposition structure, a kernel of size 26k is presented, which improves the previous best result 28k. For the Parameterized Planar 4-Cycle Transversal problem, by partitioning the vertices in a given instance into several parts and analyzing the size of each part independently, a kernel with at most 51 k − 22 vertices is obtained, which improves the previous best result 74k. Based on the kernelization process of the Parameterized Planar 4-Cycle Transversal problem, a kernel of size 51 k − 22 can also be obtained for the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem, which improves the previous best result 96k.

TCS Journal 2020 Journal Article

On scheduling multiple two-stage flowshops

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

This paper studies the problem of scheduling n two-stage jobs on m multiple two-stage flowshops, with the objective of minimizing the makespan. The problem is NP-hard even when m is a fixed constant, and becomes strongly NP-hard when m is part of the input. A 2. 6-approximation algorithm along with its analysis is presented for an arbitrary m ≥ 2. This is the first approximation algorithm for multiple flowshops when the number m of flowshops is part of the input. The fact that m is part of the input and the time complexity O ( n log ⁡ n ) of the algorithm demonstrate that the problem, which plays an important role in the current research in cloud computing and data centers, can be solved efficiently with a reasonable level of satisfaction.

JBHI Journal 2020 Journal Article

Predicting Human lncRNA-Disease Associations Based on Geometric Matrix Completion

• Chengqian Lu
• Mengyun Yang
• Min Li
• Yaohang Li
• Fang-Xiang Wu
• Jianxin Wang

Recently, increasing evidences reveal that dysregulations of long non-coding RNAs (lncRNAs) are relevant to diverse diseases. However, the number of experimentally verified lncRNA-disease associations is limited. Prioritizing potential associations is beneficial not only for disease diagnosis, but also disease treatment, more important apprehending disease mechanisms at lncRNA level. Various computational methods have been proposed, but precise prediction and full use of data's intrinsic structure are still challenging. In this work, we design a new method, denominated GMCLDA (Geometric Matrix Completion lncRNA-Disease Association), to infer underlying associations based on geometric matrix completion. Utilizing association patterns among functionally similar lncRNAs and phenotypically similar diseases, GMCLCA makes use of the intrinsic structure embedded in the association matrix. Besides, limiting the scope of the predicted values gives rise to a certain sparsity in computation and enhances the robustness of GMCLDA. GMCLDA computes disease semantic similarity according to the Disease Ontology (DO) hierarchy and lncRNA Gaussian interaction profile kernel similarity according to known interaction profiles. Then, GMCLDA measures lncRNA sequence similarity using Needleman-Wunsch algorithm. For a new lncRNA, GMCLDA prefills interaction profile on account of its K-nearest neighbors defined by sequence similarity. Finally, GMCLDA estimates the missing entries of the association matrix based on geometric matrix completion model. Compared with state-of-the-art methods, GMCLDA can provide more accurate lncRNA-disease prediction. Further case studies prove that GMCLDA is able to correctly infer possible lncRNAs for renal cancer.

TCS Journal 2019 Journal Article

An improved linear kernel for complementary maximal strip recovery: Simpler and smaller

• Wenjun Li
• Haiyan Liu
• Jianxin Wang
• Lingyun Xiang
• Yongjie Yang

We study the Complementary Maximal Strip Recovery problem (CMSR), where the given are two strings S 1 and S 2 of distinct letters, each of which appears either in the positive form or the negative form. The question is whether there are k letters whose deletion results in two matched strings. String S 1 matches string S 2 if there are partitions of S 1 and S 2 such that each component of the partitions contains at least two letters and, moreover, for each component S 1 i of the partition of S 1, there is a unique component S 2 j in the partition of S 2 which is either equal to S 1 i or can be obtained from S 1 i by firstly reversing the order of the letters and then negating the letters. The CMSR problem is known to be NP-hard and fixed-parameter tractable with respect to k. In particular, a linear kernel of size 74 k + 4 was developed based on 8 reduction rules. Very recently, by imposing 3 new reduction rules to the previous kernelization, the linear kernel has been improved to 58k. We aim to simplify the kernelization, yet obtain an improved kernel. In particular, we study 7 reduction rules which lead to a linear kernel of size 42 k + 24.

AAMAS Conference 2019 Conference Paper

Complexity of Additive Committee Selection with Outliers

• Yongjie Yang
• Jianxin Wang

We study the φf -Outliers problem, where we are given an election and are asked whether there are at most n̄ votes whose removal leads to the existence of a k-committee of a desired quality under the voting rule φf. We investigate the (parameterized) complexity ofφf -Outliers for additivek-committee selection rules, in both the general case and several special cases with respect to the incidence graphs of the given elections.

TCS Journal 2019 Journal Article

Kernels for packing and covering problems

• Jianer Chen
• Henning Fernau
• Peter Shaw
• Jianxin Wang
• Zhibiao Yang

We show how the notion of combinatorial duality, related to the well-known notion of duality from linear programming, may be used for translating kernel results obtained for packing problems into kernel results for covering problems. We exemplify this approach by having a closer look at the problems of packing a graph with vertex-disjoint trees or vertex-disjoint stars with r edges. The case r = 2 has been studied in several other papers. By establishing a general notion of a crown, we show how linear-size vertex kernels can be efficiently achieved for the mentioned problems.

TCS Journal 2019 Journal Article

On scheduling inclined jobs on multiple two-stage flowshops

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

We study scheduling on multiple two-stage flowshops in which each job has to pass through an R-operation and a T-operation. Motivated by the current research in data centers, we consider two restricted versions of the problem in which the jobs are inclined: one restricts that for each job, the R-operation consumes no less time than the T-operation, while the other assumes that the T-operation consumes no less time than the R-operation for each job. For the first case, we present an online 2-competitive algorithm and an offline 11/6-approximation algorithm. For the second case, we give an online 5/2-competitive algorithm, and prove, for the offline setting, that the problem can be reduced to the problem in the first case.

IJCAI Conference 2019 Conference Paper

Resolution and Domination: An Improved Exact MaxSAT Algorithm

• Chao Xu
• Wenjun Li
• Yongjie Yang
• Jianer Chen
• Jianxin Wang

We study the Maximum Satisfiability problem (MaxSAT). Particularly, we derive a branching algorithm of running time O*(1. 2989^m) for the MaxSAT problem, where m denotes the number of clauses in the given CNF formula. Our algorithm considerably improves the previous best result O*(1. 3248^m) by Chen and Kanj [2004] published 15 years ago. For our purpose, we derive improved branching strategies for variables of degrees 3, 4, and 5. The worst case of our branching algorithm is at variables of degree 4 which occur twice both positively and negatively in the given CNF formula. To serve the branching rules and shrink the size of the CNF formula, we also propose a variety of reduction rules which can be exhaustively applied in polynomial time and, moreover, some of them solve a bottleneck of the previous best algorithm.

TCS Journal 2019 Journal Article

Resolution and linear CNF formulas: Improved (n,3)-MaxSAT algorithms

• Chao Xu
• Jianer Chen
• Jianxin Wang

We study techniques for solving the MaxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an equivalent instance in which the CNF formula becomes a linear CNF formula. We then show how more efficient branching strategies can be applied on linear CNF formulas. As applications, we present two algorithms: one of running time O ⁎ ( 1. 194 k ) that solves the parameterized version of the problem, and the other of running time O ⁎ ( 1. 237 n ) that solves the optimization version of the problem, both significantly improving previous best upper bounds.

TCS Journal 2019 Journal Article

Scheduling two-stage jobs on multiple flowshops

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

Scheduling two-stage jobs on multiple two-stage flowshops is studied. A new formulation for configurations of the scheduling is proposed, leading directly to improvements on complexity of scheduling algorithms for the problem. Motivated by observations in practice, we present a deeper study on the structures of the problem that leads to a new approach that gives very significant improved scheduling algorithms for the problem when the costs of the two stages differ significantly.

TCS Journal 2018 Journal Article

Dealing with several parameterized problems by random methods

• Qilong Feng
• Neng Huang
• Xiong Jiang
• Jianxin Wang

In this paper, we apply random methods to deal with several parameterized problems. For the Parameterized Weighted P 3 -Packing problem, by randomly partitioning the vertices in given graph, a tripartite graph can be obtained. We prove that the Parameterized Weighted P 3 -Packing problem can be solved in polynomial time on tripartite graphs. Based on the algorithm on tripartite graphs, a randomized parameterized algorithm of running time O ⁎ ( 32 k ) is given for the Parameterized Weighted P 3 -Packing problem. For the Parameterized Weighted Load Coloring problem, by randomly partitioning the vertices in given graph into two parts and studying the structure properties of the connected components in two parts, a randomized parameterized algorithm of running time O ⁎ ( 11. 32 k ) is presented. For the Parameterized Claw-free Edge Deletion problem on Diamond-free Graphs, by combining random with branching methods, a parameterized algorithm of running time O ⁎ ( 2. 42 k ) is given.

IJCAI Conference 2018 Conference Paper

Multiwinner Voting with Restricted Admissible Sets: Complexity and Strategyproofness

• Yongjie Yang
• Jianxin Wang

Multiwinner voting aims to select a subset of candidates (the winners) from admissible sets, according to the votes cast by voters. A special class of multiwinner rules—the k-committee selection rules where the number of winners is predefined—have gained considerable attention recently. In this setting, the admissible sets are all subsets of candidates of size exactly k. In this paper, we study admissible sets with combinatorial restrictions. In particular, in our setting, we are given a graph G whose vertex set is the candidate set. Admissible sets are the subsets of candidates whose induced subgraphs belong to some special class G of graphs. We consider different graph classes G and investigate the complexity of multiwinner determination problem for prevalent voting rules in this setting. In addition, we investigate the strategyproofness of many rules for different classes of admissible sets.

TCS Journal 2018 Journal Article

Parameterized algorithms for Edge Biclique and related problems

• Qilong Feng
• Shaohua Li
• Zeyang Zhou
• Jianxin Wang

Maximum Edge Biclique and related problems have wide applications in management science, bioinformatics, etc. In this paper, we study parameterized algorithms for Parameterized Edge Biclique problem, Parameterized Edge Biclique Packing problem, Parameterized Biclique Edge Deletion problem, and Parameterized Bipartite Biclique Clustering problem. For the Parameterized Edge Biclique problem, the current best result is of running time O ⁎ ( 2 k ), and we give a parameterized algorithm of running time O ( n k 2. 5 k ⌈ k ⌉ ), where k is the parameter and n is the number of vertices in the given graph. For the Parameterized Edge Biclique Packing problem, based on randomized divide-and-conquer technique, a parameterized algorithm of running time O ⁎ ( k ⌈ k ⌉ l o g k 4 ( 2 k − 1 ) t ) ) is given, where k is the parameter and t is the number of bicliques in the solution. We study the Parameterized Biclique Edge Deletion problem on bipartite graphs and general graphs, and give parameterized algorithms of running time O ⁎ ( 2 k ) and O ⁎ ( 3 k ), respectively. For the Parameterized Bipartite Biclique Clustering problem, based on modular decomposition method, a kernel of size O ( k 2 ) and a parameterized algorithm of running time O ( 2. 42 k ( n + m ) ) are presented, where k is the parameter, n is the number of vertices, and m is the number of edges in the given graph.

AAMAS Conference 2018 Conference Paper

Parameterized Complexity of Multi-winner Determination: More Effort Towards Fixed-Parameter Tractability

• Yongjie Yang
• Jianxin Wang

We study the k-committee selection rules minimax approval, proportional approval, and Chamberlin-Courant’s approval. It is known that Winner Determination for these rules is NP-hard. Moreover, the parameterized complexity of the problem has also been studied with respect to some natural parameters. However, there are still numerous parameterizations that have not been considered. We revisit the parameterized complexity of Winner Determination for these rules by considering several important single parameters, combined parameters, and structural parameters, aiming at detecting as many fixed-parameter tractability results as possible.

TCS Journal 2018 Journal Article

Parameterized counting matching and packing: A family of hard problems that admit FPTRAS

• Yunlong Liu
• Shaokai Wang
• Jianxin Wang

In the field of parameterized counting complexity, the problems that are #W[1]-hard and admit fixed-parameter tractable randomized approximation scheme (FPTRAS) have attracted much attention in recent years. In this paper, we focus on the problems on parameterized counting matching and packing. These problems include counting set packing, counting matching, and counting subgraph packing (including both vertex-disjoint and edge-disjoint versions). We study the parameterized complexity on these problems. On the basis of some results for counting graph matchings, we show that a series of problems are #W[1]-hard. Furthermore, by extending the previous algorithm for counting 3-d matching, we obtain FPTRAS for each considered problem, respectively. Our results indicate that the problems on parameterized counting matching and packing form a large family of problems that are #W[1]-hard and admit FPTRAS.

AAMAS Conference 2017 Conference Paper

Anyone But Them: The Complexity Challenge for A Resolute Election Controller

• Yongjie Yang
• Jianxin Wang

We study the voting problems where given is an election associated with a subset J of candidates, and the question is whether we can modify the election in a way so that none of the candidates in J wins the election. The modification operations include either adding some votes/candidates or deleting some votes/candidates. These problems are natural generalizations of destructive control problems where J is a singleton and capture many practical situations. We achieve a broad range of complexity results for a number of single-winner voting systems involving voting rules which are compositions of commonly used voting correspondences, such as Borda, Maximin and Copelandα, and three tie-breaking schemes, namely the fixed-order, random candidates and random votes. In particular, we achieve polynomial-time solvability results, NP-hardness results, fixed-parameter tractability results as well as XP results. In addition, we study other tie-breaking schemes and show that the complexity of the problems may depend on tie-breaking schemes.

TCS Journal 2017 Journal Article

Dealing with 4-variables by resolution: An improved MaxSAT algorithm

• Jianer Chen
• Chao Xu
• Jianxin Wang

We study techniques for solving the Maximum Satisfiability problem (MaxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MaxSAT problem. As a result, we present an algorithm of time O ⁎ ( 1. 3248 k ) for the MaxSAT problem, improving the previous best upper bound O ⁎ ( 1. 358 k ) by Ivan Bliznets and Alexander Golovnev.

I&C Journal 2017 Journal Article

Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree

• Wenjun Li
• Yixin Cao
• Jianer Chen
• Jianxin Wang

The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an O ⁎ ( 8 k ) -time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2k vertices, and as a by-product, a deterministic algorithm running in time O ⁎ ( 4 k ). We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1. 5 for the problem.

TCS Journal 2017 Journal Article

Preface

• Jianxin Wang
• Chee K. Yap

UAI Conference 2016 Conference Paper

Towards a Theoretical Understanding of Negative Transfer in Collective Matrix Factorization

• Chao Lan
• Jianxin Wang
• Jun Huan

Collective matrix factorization (CMF) is a popular technique to improve the overall factorization quality of multiple matrices presuming they share the same latent factor. However, it suffers from performance degeneration when this assumption fails, an effect called negative transfer (n. t.). Although the effect is widely admitted, its theoretical nature remains a mystery to date. This paper presents a first theoretical understanding of n. t. in theory. Under the statistical minimax framework, we derive lower bounds for the CMF estimator and gain two insights. First, the n. t. effect can be explained as the rise of a bias term in the standard lower bound, which depends only on the structure of factor space but neither the estimator nor samples. Second, the n. t. effect can be explained as the rise of an dth -root function on the learning rate, where d is the dimension of a Grassmannian containing the subspaces spanned by latent factors. These discoveries are also supported in simulation, and suggest n. t. may be more effectively addressed via model construction other than model selection.

TCS Journal 2015 Journal Article

Edge deletion problems: Branching facilitated by modular decomposition

• Yunlong Liu
• Jianxin Wang
• Jie You
• Jianer Chen
• Yixin Cao

Edge deletion problems ask for a minimum set of edges whose deletion makes a graph have a certain property. When this property can be characterized by a finite set of forbidden induced subgraphs, the problem can be solved in fixed-parameter time by a naive bounded search tree algorithm. Sometimes deleting an edge to break an erstwhile forbidden induced subgraph might introduce new ones, which may involve the neighbors of the original forbidden induced subgraph. Therefore, in considering possible ways to break a forbidden induced subgraph one naturally takes its neighborhood into consideration. This observation easily yields more efficient branching rules, but a naive implementation will require too many tedious case analyses. Here we take advantage of modular decomposition, which allows us to focus on far simpler quotient graphs instead of the original graphs. They together yield simple improved algorithms for the edge deletion problems to chain graphs and trivially perfect graphs.

TCS Journal 2015 Journal Article

Kernelization and parameterized algorithms for covering a tree by a set of stars or paths

• Jie You
• Jianxin Wang
• Qilong Feng
• Feng Shi

Two restricted versions of the Subforest Isomorphism problem, the Covering a Tree by a Set of Stars (CTSS) and the Covering a Tree by a Set of Paths (CTSP) problems, are studied. Both problems are NP-complete. The problems are closely related to a number of well-studied problems, including the problems Subgraph Isomorphism, Tree Editing, and Graph Packing. It is shown that the problems CTSS and CTSP are fixed-parameter tractable. Thorough development of parameterized algorithms and kernelization algorithms for these problems are presented.

TCS Journal 2015 Journal Article

Parameterized complexity of control and bribery for d-approval elections

• Jianxin Wang
• Weimin Su
• Min Yang
• Jiong Guo
• Qilong Feng
• Feng Shi
• Jianer Chen

A d-Approval election consists of a set C of candidates and a set V of votes, where each vote v can be presented as a set of d candidates. For a vote v ∈ V, the d-Approval voting protocol assigns one point to each candidate in v. The candidate getting the most points from all votes wins the election. An important aspect of studying election systems is the strategic behavior such as control and bribery problems. The control by deleting votes problem decides whether for a given election ( C, V ), a specific candidate c, and an integer k, it is possible to delete at most k votes such that c wins the resulting election. In the control by adding votes setting, one has two sets V and U of votes and asks for a subset U ′ ⊆ U such that | U ′ | ≤ k and c becomes the winner in V ∪ U ′. The bribery problem has the same input as the vote deleting control problem and asks for changing at most k votes to make c win. All three problems have been shown NP-hard. We initialize the study of the parameterized complexity of these problems and present a collection of tractability and intractability results. In particular, we derive a polynomial-size problem kernel for the standard parameterization of the control by deleting votes problem, the seemingly first non-trivial problem kernel for the control problem of elections.

TCS Journal 2014 Journal Article

Algorithms for parameterized maximum agreement forest problem on multiple trees

• Feng Shi
• Jianxin Wang
• Jianer Chen
• Qilong Feng
• Jiong Guo

The Maximum Agreement Forest problem (MAF) asks for a largest common subforest of a collection of phylogenetic trees. The MAF problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we present a group of fixed-parameter tractable algorithms for the MAF problem on multiple (i. e. , two or more) binary phylogenetic trees. Our techniques work fine for the problem for both rooted trees and unrooted trees. The computational complexity of our algorithms is comparable with that of the known algorithms for two trees, and is independent of the number of phylogenetic trees for which a maximum agreement forest is constructed.

TCS Journal 2014 Journal Article

Improved parameterized algorithms for minimum link-length rectilinear spanning path problem

• Qilong Feng
• Jianxin Wang
• Chao Xu
• Jinyi Yao
• Jianer Chen

The Parameterized Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R d (d-RSP), for a given set S of n points in R d and a positive integer k, is to find a rectilinear spanning path P with at most k line-segments that cover all points in S, where all line-segments in P are axis-parallel. In this paper, we study a constrained d-RSP problem (Constrained d-RSP problem) in which each line-segment l in the spanning path must cover all the points in S that share the same line with l. By applying the branch-and-search and dynamic programming techniques, a parameterized algorithm with running time O ⁎ ( ( 1 + 1 + 4 ( d − 1 ) 2 ) k ) is given for the Constrained d-RSP problem, which significantly improves the current best result O ⁎ ( ( 0. 74 d k ) k ).

TCS Journal 2014 Journal Article

Matching and Weighted P 2 -Packing: Algorithms and Kernels

• Qilong Feng
• Jianxin Wang
• Jianer Chen

Parameterized algorithms and kernelization algorithms are presented for the weighted P 2 -Packing problem, which is a generalization of the famous Graph Matching problem. The parameterized algorithms are based on the following new techniques and observations: (1) new study on structure relationship between graph matchings in general graphs and P 2 -packings in bipartite graphs; (2) an effective graph bi-partitioning algorithm; and (3) a polynomial-time algorithm for a constrained weighted P 2 -Packing problem in bipartite graphs. The kernelization algorithms are based on the following new techniques: (1) the application of graph matching in kernelization; (2) a crown reduction structure for weighted problems. These techniques lead to randomized and deterministic parameterized algorithms that significantly improve the previous best upper bounds for the problem for both weighted and unweighted versions. For the kernelization algorithm, by using a weighted version of crown reduction, a kernel of size O ( k 2 ) is presented, where k is the given parameter of the problem.

TCS Journal 2014 Journal Article

Parameterized complexity of Max-lifetime Target Coverage in wireless sensor networks

• Weizhong Luo
• Jianxin Wang
• Jiong Guo
• Jianer Chen

Max-lifetime Target Coverage can be viewed as a family of problems where the task is to partition the sensors into groups and assign their time-slots such that the coverage lifetime is maximized while satisfying some coverage requirement. Unfortunately, these problems are NP-hard. To gain insight into the source of the complexity, we initiate a systematic parameterized complexity study of two types of Max-lifetime Target Coverage: Max–min Target Coverage and Max-individual Target Coverage. We first prove that both problems remain NP-hard even in the special cases where each target is covered by at most two sensors or each sensor can cover at most two targets. By contrast, restricting the number of targets reduces the complexity of the considered problems. In other words, they are both fixed parameter tractable (FPT) with respect to the parameter “number of targets”. Moreover, we extend our studies to the structural parameter “number k of sensors covering at least two targets”. Positively, both problems are in FPT with respect to k. Finally, we show that Max–min Target Coverage is in FPT with respect to the combined parameters “number of groups” and “number of targets covered by each group”.

TCS Journal 2013 Journal Article

Improved linear problem kernel for planar connected dominating set

• Weizhong Luo
• Jianxin Wang
• Qilong Feng
• Jiong Guo
• Jianer Chen

In this paper, we study the Planar Connected Dominating Set problem, which, given a planar graph G = ( V, E ) and a non-negative integer k, asks for a subset D ⊆ V with ∣ D ∣ ≤ k such that D forms a dominating set of G and induces a connected graph. Answering an open question posed at the 2nd Workshop on Kernelization (WorKer 2010), we provide a kernelization algorithm for this problem, leading to a problem kernel with at most 130 k vertices, improving the previously best upper bound on the kernel size. To this end, we incorporate a vertex coloring technique with data reduction rules and introduce a type distinction of regions into the region decomposition framework, which allows a refined analysis of the region size.

TCS Journal 2013 Journal Article

Parameterized complexity of Min-power multicast problems in wireless ad hoc networks

• Jianxin Wang
• Weizhong Luo
• Qilong Feng
• Jiong Guo

Power assignment in wireless ad hoc networks can be seen as a family of problems in which the task is to find in a given power requirement network a minimum power communication subnetwork that satisfies a given connectivity constraint. These problems have been extensively studied from the viewpoint of approximation, heuristic, linear programming, etc. In this paper, we add a new facet by initiating a systematic parameterized complexity study of three types of power assignment problems related to multicast: Min-power Single-source h -Multicast, Min-power Strongly Connected h -Multicast and Min-power Multi-source h -Multicast. We investigate their parameterized complexities with respect to the number of terminals and the number of senders. We show that a Min-power Single-source h -Multicast is fixed-parameter tractable with respect to the number of terminals and achieve several parameterized hardness results.

TCS Journal 2012 Journal Article

Complexity and parameterized algorithms for Cograph Editing

• Yunlong Liu
• Jianxin Wang
• Jiong Guo
• Jianer Chen

Cograph Editing is to find for a given graph G = ( V, E ) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we first show that this problem is NP-hard by a reduction from Exact 3-Cover. Subsequently, we present a parameterized algorithm based on a refined search tree technique with a running time of O ( 4. 61 2 k + | V | 4. 5 ), which improves the trivial algorithm of running time O ( 6 k + | V | 4. 5 ).

TCS Journal 2011 Journal Article

An O ∗ ( 3.5 3 3 k ) -time parameterized algorithm for the 3-set packing problem

• Jianxin Wang
• Qilong Feng
• Jianer Chen

A parameterized algorithm for the well-known NP-complete problem 3-set packing is presented. The algorithm is based on the following new approaches: (1) an efficient algorithm for problem instances in which one element is known for each of the 3-sets in a solution packing (i. e. , type-1 instances); (2) an efficient algorithm for problem instances in which at least two elements are known for each of the 3-sets in a solution packing (i. e. , type-2 instances); and (3) an effective decomposition of a general instance of 3-set packing into two instances of type-1 and type-2, respectively, whose base sets are disjoint. This technique results in an improved parameterized algorithm of running time O ∗ ( 3. 5 3 3 k ) for the 3-set packing problem, improving the previous best upper bound O ∗ ( 4. 6 1 3 k ).

TCS Journal 2011 Journal Article

Improved deterministic algorithms for weighted matching and packing problems

• Jianer Chen
• Qilong Feng
• Yang Liu
• Songjian Lu
• Jianxin Wang

Based on the method of ( n, k ) -universal sets, we present a deterministic parameterized algorithm for the weighted r d-matching problem with time complexity O ∗ ( 4 ( r − 1 ) k + o ( k ) ), improving the previous best upper bound O ∗ ( 4 r k + o ( k ) ). In particular, the algorithm applied to the unweighted 3d-matching problem results in a deterministic algorithm with time O ∗ ( 1 6 k + o ( k ) ), improving the previous best result O ∗ ( 21. 2 6 k ). For the weighted r -set packing problem, we present a deterministic parameterized algorithm with time complexity O ∗ ( 2 ( 2 r − 1 ) k + o ( k ) ), improving the previous best result O ∗ ( 2 2 r k + o ( k ) ). The algorithm, when applied to the unweighted 3-set packing problem, has running time O ∗ ( 3 2 k + o ( k ) ), improving the previous best result O ∗ ( 43. 6 2 k + o ( k ) ). Moreover, for the weighted r -set packing and weighted r d-matching problems, we give a kernel of size O ( k r ), which is the first kernelization algorithm for the problems on weighted versions.

TCS Journal 2010 Journal Article

A parameterized algorithm for the hyperplane-cover problem

• Jianxin Wang
• Wenjun Li
• Jianer Chen

We consider the problem of covering a given set of points in the Euclidean space R m by a small number k of hyperplanes of dimensions bounded by d, where d ≤ m. We present a very simple parameterized algorithm for the problem, and give thorough mathematical analysis to prove the correctness and derive the complexity of the algorithm. When the algorithm is applied on the standard hyperplane-cover problem in R d, it runs in time O ∗ ( k ( d − 1 ) k / 1. 3 k ), improving the previous best algorithm of running time O ∗ ( k d k + d ) for the problem. When the algorithm is applied on the line-cover problem in R 2, it runs in time O ∗ ( k k / 1. 3 5 k ), improving the previous best algorithm of running time O ∗ ( k 2 k / 4. 8 4 k ) for the problem.

EAAI Journal 2009 Journal Article

A parthenogenetic algorithm for single individual SNP haplotyping

• Jingli Wu
• Jianxin Wang
• Jian’er Chen

The minimum error correction (MEC) model is one of the important computational models for single individual single nucleotide polymorphism (SNP) haplotyping. Due to the NP-hardness of the model, Qian et al. presented a particle swarm optimization (PSO) algorithm to solve it, and the particle code length is equal to the number of SNP fragments. However, there are hundreds and thousands of SNP fragments in practical applications. The PSO algorithm based on this kind of long particle code cannot obtain high reconstruction rate efficiently. In this paper, a practical heuristic algorithm PGA-MEC based on parthenogenetic algorithm (PGA) is presented to solve the model. A kind of short chromosome code and an effective recombination operator are designed for the algorithm. The reconstruction rate of PGA-MEC algorithm is higher than that of PSO algorithm and the running time of PGA-MEC algorithm is shorter than that of PSO algorithm, which are proved by a number of experiments.