Author name cluster

Feng Shi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers

2 author rows

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.

IJCAI Conference 2025 Conference Paper

AttentionDrag: Exploiting Latent Correlation Knowledge in Pre-trained Diffusion Models for Image Editing

Biao Yang
Muqi Huang
Yuhui Zhang
Yun Xiong
Kun Zhou
Xi Chen
Shiyang Zhou
Huishuai Bao

Traditional point-based image editing methods rely on iterative latent optimization or geometric transformations, which are either inefficient in their processing or fail to capture the semantic relationships within the image. These methods often overlook the powerful yet underutilized image editing capabilities inherent in pre-trained diffusion models. In this work, we propose a novel one-step point-based image editing method, named \textbf{AttentionDrag}, which leverages the inherent latent knowledge and feature correlations within pre-trained diffusion models for image editing tasks. This framework enables semantic consistency and high-quality manipulation without the need for extensive re-optimization or retraining. Specifically, we reutilize the latent correlations knowledge learned by the self-attention mechanism in the U-Net module during the DDIM inversion process to automatically identify and adjust relevant image regions, ensuring semantic validity and consistency. Additionally, AttentionDrag adaptively generates masks to guide the editing process, enabling precise and context-aware modifications with friendly interaction. Our results demonstrate a performance that surpasses most state-of-the-art methods with significantly faster speeds, showing a more efficient and semantically coherent solution for point-based image editing tasks. Code is released at: https: //github. com/GPlaying/AttentionDrag.

PDF Details DOI

TCS Journal 2025 Journal Article

Runtime performance of evolutionary algorithms for the chance-constrained makespan scheduling problem

Feng Shi
Daoyu Huang
Xiankun Yan
Frank Neumann

The makespan scheduling problem is an extensively studied NP-hard problem, and its simplest version is to find an allocation approach for a set of jobs with deterministic processing time to two identical machines such that the makespan is minimized. However, in real-life scenarios, the actual processing time of each job may be stochastic under the influence of external factors. Thus within this paper, we first propose a chance-constrained version of the makespan scheduling problem. Then we study the theoretical performance of RLS and (1+1) EA for three variants of the chance-constrained makespan scheduling problem. Within those variants, our theoretical analysis implies that distinct uncertainties influence the behaviors of the two algorithms. Specifically, we separately analyze the expected runtime of the two algorithms to obtain an optimal solution or almost optimal solution to the instances of the three variants. In addition, we further investigate the experimental performance of the two algorithms for the three variants.

JBHI Journal 2025 Journal Article

Unified Model for Children's Brain Image Segmentation With Co-Registration Framework Guided by Longitudinal MRI

Lin Teng
Yichu He
Zehong Cao
Rui Hua
Ye Han
Qianjin Feng
Feng Shi
Dinggang Shen

Accurate segmentation of brain structures is crucial for analyzing longitudinal changes in children's brains. However, existing methods are mostly based on models established at a single time-point due to difficulty in obtaining annotated data and dynamic variation of tissue intensity. The main problem with such approaches is that, when conducting longitudinal analysis, images from different time points are segmented by different models, leading to significant variation in estimating development trends. In this paper, we propose a novel unified model with co-registration framework to segment children's brain images covering neonates to preschoolers, which is formulated as two stages. First, to overcome the shortage of annotated data, we propose building gold-standard segmentation with co-registration framework guided by longitudinal data. Second, we construct a unified segmentation model tailored to brain images at 0-6 years old through the introduction of a convolutional network (named SE-VB-Net), which combines our previously proposed VB-Net with Squeeze-and-Excitation (SE) block. Moreover, different from existing methods that only require both T1- and T2-weighted MR images as inputs, our designed model also allows a single T1-weighted MR image as input. The proposed method is evaluated on the main dataset (320 longitudinal subjects with average 2 time-points) and two external datasets (10 cases with 6-month-old and 40 cases with 20–45 weeks, respectively). Results demonstrate that our proposed method achieves a high performance (>92%), even over a single time-point. This means that it is suitable for brain image analysis with large appearance variation, and largely broadens the application scenarios.

ICML Conference 2023 Conference Paper

Alternately Optimized Graph Neural Networks

Haoyu Han 0001
Xiaorui Liu
Haitao Mao
MohamadAli Torkamani
Feng Shi
Victor Lee
Jiliang Tang

Graph Neural Networks (GNNs) have greatly advanced the semi-supervised node classification task on graphs. The majority of existing GNNs are trained in an end-to-end manner that can be viewed as tackling a bi-level optimization problem. This process is often inefficient in computation and memory usage. In this work, we propose a new optimization framework for semi-supervised learning on graphs from a multi-view learning perspective. The proposed framework can be conveniently solved by the alternating optimization algorithms, resulting in significantly improved efficiency. Extensive experiments demonstrate that the proposed method can achieve comparable or better performance with state-of-the-art baselines while it has significantly better computation and memory efficiency.

JBHI Journal 2023 Journal Article

Brain Status Transferring Generative Adversarial Network for Decoding Individualized Atrophy in Alzheimer's Disease

Xingyu Gao
Hongrui Liu
Feng Shi
Dinggang Shen
Manhua Liu

Deep learning has been widely investigated in brain image computational analysis for diagnosing brain diseases such as Alzheimer's disease (AD). Most of the existing methods built end-to-end models to learn discriminative features by group-wise analysis. However, these methods cannot detect pathological changes in each subject, which is essential for the individualized interpretation of disease variances and precision medicine. In this article, we propose a brain status transferring generative adversarial network (BrainStatTrans-GAN) to generate corresponding healthy images of patients, which are further used to decode individualized brain atrophy. The BrainStatTrans-GAN consists of generator, discriminator, and status discriminator. First, a normative GAN is built to generate healthy brain images from normal controls. However, it cannot generate healthy images from diseased ones due to the lack of paired healthy and diseased images. To address this problem, a status discriminator with adversarial learning is designed in the training process to produce healthy brain images for patients. Then, the residual between the generated and input images can be computed to quantify pathological brain changes. Finally, a residual-based multi-level fusion network (RMFN) is built for more accurate disease diagnosis. Compared to the existing methods, our method can model individualized brain atrophy for facilitating disease diagnosis and interpretation. Experimental results on T1-weighted magnetic resonance imaging (MRI) data of 1, 739 subjects from three datasets demonstrate the effectiveness of our method.

JBHI Journal 2023 Journal Article

Individualized Assessment of Brain Aβ Deposition With fMRI Using Deep Learning

Chaolin Li
Mianxin Liu
Jing Xia
Lang Mei
Qing Yang
Feng Shi
Han Zhang
Dinggang Shen

PET-based Alzheimer's disease (AD) assessment has many limitations in large-scale screening. Non-invasive techniques such as resting-state functional magnetic resonance imaging (rs-fMRI) have been proven valuable in early AD diagnosis. This study investigated feasibility of using rs-fMRI, especially functional connectivity (FC), for individualized assessment of brain amyloid-β deposition derived from PET. We designed a graph convolutional networks (GCNs) and random forest (RF) based integrated framework for using rs-fMRI-derived multi-level FC networks to predict amyloid-β PET patterns with the OASIS-3 (N = 258) and ADNI-2 (N = 291) datasets. Our method achieved satisfactory accuracy not only in Aβ-PET grade classification (for negative, intermediate, and positive grades, with accuracy in the three-class classification as 62. 8% and 64. 3% on two datasets, respectively), but also in prediction of whole-brain region-level Aβ-PET standard uptake value ratios (SUVRs) (with the mean square errors as 0. 039 and 0. 074 for two datasets, respectively). Model interpretability examination also revealed the contributive role of the limbic network. This study demonstrated high feasibility and reproducibility of using low-cost, more accessible magnetic resonance imaging (MRI) to approximate PET-based diagnosis.

NeurIPS Conference 2023 Conference Paper

Towards Label Position Bias in Graph Neural Networks

Haoyu Han
Xiaorui Liu
Feng Shi
MohamadAli Torkamani
Charu Aggarwal
Jiliang Tang

Graph Neural Networks (GNNs) have emerged as a powerful tool for semi-supervised node classification tasks. However, recent studies have revealed various biases in GNNs stemming from both node features and graph topology. In this work, we uncover a new bias - label position bias, which indicates that the node closer to the labeled nodes tends to perform better. We introduce a new metric, the Label Proximity Score, to quantify this bias, and find that it is closely related to performance disparities. To address the label position bias, we propose a novel optimization framework for learning a label position unbiased graph structure, which can be applied to existing GNNs. Extensive experiments demonstrate that our proposed method not only outperforms backbone methods but also significantly mitigates the issue of label position bias in GNNs.

AAAI Conference 2022 Conference Paper

Learning from the Tangram to Solve Mini Visual Tasks

Yizhou Zhao
Liang Qiu
Pan Lu
Feng Shi
Tian Han
Song-Chun Zhu

Current pre-training methods in computer vision focus on natural images in the daily-life context. However, abstract diagrams such as icons and symbols are common and important in the real world. This work is inspired by Tangram, a game that requires replicating an abstract pattern from seven dissected shapes. By recording human experience in solving tangram puzzles, we present the Tangram dataset and show that a pre-trained neural model on the Tangram helps solve some mini visual tasks based on low-resolution vision. Extensive experiments demonstrate that our proposed method generates intelligent solutions for aesthetic tasks such as folding clothes and evaluating room layouts. The pre-trained feature extractor can facilitate the convergence of few-shot learning tasks on human handwriting and improve the accuracy in identifying icons by their contours. The Tangram dataset is available at https: //github. com/yizhouzhao/Tangram.

JBHI Journal 2022 Journal Article

Task-Induced Pyramid and Attention GAN for Multimodal Brain Image Imputation and Classification in Alzheimer's Disease

Xingyu Gao
Feng Shi
Dinggang Shen
Manhua Liu

With the advance of medical imaging technologies, multimodal images such as magnetic resonance images (MRI) and positron emission tomography (PET) can capture subtle structural and functional changes of brain, facilitating the diagnosis of brain diseases such as Alzheimer's disease (AD). In practice, multimodal images may be incomplete since PET is often missing due to high financial costs or availability. Most of the existing methods simply excluded subjects with missing data, which unfortunately reduced the sample size. In addition, how to extract and combine multimodal features is still challenging. To address these problems, we propose a deep learning framework to integrate a task-induced pyramid and attention generative adversarial network (TPA-GAN) with a pathwise transfer dense convolution network (PT-DCN) for imputation and classification of multimodal brain images. First, we propose a TPA-GAN to integrate pyramid convolution and attention module as well as disease classification task into GAN for generating the missing PET data with their MRI. Then, with the imputed multimodal images, we build a dense convolution network with pathwise transfer blocks to gradually learn and combine multimodal features for final disease classification. Experiments are performed on ADNI-1/2 datasets to evaluate our method, achieving superior performance in image imputation and brain disease diagnosis compared to state-of-the-art methods.

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.

YNIMG Journal 2021 Journal Article

Recycling diagnostic MRI for empowering brain morphometric research – Critical & practical assessment on learning-based image super-resolution

Gaoping Liu
Zehong Cao
Qiang Xu
Qirui Zhang
Fang Yang
Xinyu Xie
Jingru Hao
Yinghuan Shi

Preliminary studies have shown the feasibility of deep learning (DL)-based super-resolution (SR) technique for reconstructing thick-slice/gap diagnostic MR images into high-resolution isotropic data, which would be of great significance for brain research field if the vast amount of diagnostic MRI data could be successively put into brain morphometric study. However, less evidence has addressed the practicability of the strategy, because lack of a large-sample available real data for constructing DL model. In this work, we employed a large cohort (n = 2052) of peculiar data with both low through-plane resolution diagnostic and high-resolution isotropic brain MR images from identical subjects. By leveraging a series of SR approaches, including a proposed novel DL algorithm of Structure Constrained Super Resolution Network (SCSRN), the diagnostic images were transformed to high-resolution isotropic data to meet the criteria of brain research in voxel-based and surface-based morphometric analyses. We comprehensively assessed image quality and the practicability of the reconstructed data in a variety of morphometric analysis scenarios. We further compared the performance of SR approaches to the ground truth high-resolution isotropic data. The results showed (i) DL-based SR algorithms generally improve the quality of diagnostic images and render morphometric analysis more accurate, especially, with the most superior performance of the novel approach of SCSRN. (ii) Accuracies vary across brain structures and methods, and (iii) performance increases were higher for voxel than for surface based approaches. This study supports that DL-based image super-resolution potentially recycle huge amount of routine diagnostic brain MRI deposited in sleeping state, and turning them into useful data for neurometric research.

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.

JBHI Journal 2020 Journal Article

Adaptive Feature Selection Guided Deep Forest for COVID-19 Classification With Chest CT

Liang Sun
Zhanhao Mo
Fuhua Yan
Liming Xia
Fei Shan
Zhongxiang Ding
Bin Song
Wanchun Gao

Chest computed tomography (CT) becomes an effective tool to assist the diagnosis of coronavirus disease-19 (COVID-19). Due to the outbreak of COVID-19 worldwide, using the computed-aided diagnosis technique for COVID-19 classification based on CT images could largely alleviate the burden of clinicians. In this paper, we propose an A daptive F eature S election guided D eep F orest (AFS-DF) for COVID-19 classification based on chest CT images. Specifically, we first extract location-specific features from CT images. Then, in order to capture the high-level representation of these features with the relatively small-scale data, we leverage a deep forest model to learn high-level representation of the features. Moreover, we propose a feature selection method based on the trained deep forest model to reduce the redundancy of features, where the feature selection could be adaptively incorporated with the COVID-19 classification model. We evaluated our proposed AFS-DF on COVID-19 dataset with 1495 patients of COVID-19 and 1027 patients of community acquired pneumonia (CAP). The accuracy (ACC), sensitivity (SEN), specificity (SPE), AUC, precision and F1-score achieved by our method are 91. 79%, 93. 05%, 89. 95%, 96. 35%, 93. 10% and 93. 07%, respectively. Experimental results on the COVID-19 dataset suggest that the proposed AFS-DF achieves superior performance in COVID-19 vs. CAP classification, compared with 4 widely used machine learning methods.

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.

YNIMG Journal 2019 Journal Article

Computational neuroanatomy of baby brains: A review

Gang Li
Li Wang
Pew-Thian Yap
Fan Wang
Zhengwang Wu
Yu Meng
Pei Dong
Jaeil Kim

The first postnatal years are an exceptionally dynamic and critical period of structural, functional and connectivity development of the human brain. The increasing availability of non-invasive infant brain MR images provides unprecedented opportunities for accurate and reliable charting of dynamic early brain developmental trajectories in understanding normative and aberrant growth. However, infant brain MR images typically exhibit reduced tissue contrast (especially around 6 months of age), large within-tissue intensity variations, and regionally-heterogeneous, dynamic changes, in comparison with adult brain MR images. Consequently, the existing computational tools developed typically for adult brains are not suitable for infant brain MR image processing. To address these challenges, many infant-tailored computational methods have been proposed for computational neuroanatomy of infant brains. In this review paper, we provide a comprehensive review of the state-of-the-art computational methods for infant brain MRI processing and analysis, which have advanced our understanding of early postnatal brain development. We also summarize publically available infant-dedicated resources, including MRI datasets, computational tools, grand challenges, and brain atlases. Finally, we discuss the limitations in current research and suggest potential future research directions.

YNICL Journal 2019 Journal Article

Quantitative susceptibility mapping based hybrid feature extraction for diagnosis of Parkinson's disease

Bin Xiao
Naying He
Qian Wang
Zenghui Cheng
Yining Jiao
E. Mark Haacke
Fuhua Yan
Feng Shi

Parkinson's disease is the second most common neurodegenerative disease in the elderly after Alzheimer's disease. The aetiology and pathogenesis of Parkinson's disease (PD) are still unclear, but the loss of dopaminergic cells and the excessive iron deposition in the substantia nigra (SN) are associated with the pathophysiology. As an imaging technique that can quantitatively reflect the amount of iron deposition, Quantitative Susceptibility Mapping (QSM) has been shown to be a promising modality for the diagnosis of PD. In the present work, we propose a hybrid feature extraction method for PD diagnosis using QSM images. First, we extract radiomics features from the SN using QSM and employ machine learning algorithms to classify PD and normal controls (NC). This approach allows us to investigate which features are most vulnerable to the effects of the disease. Along with this approach, we propose a Convolutional Neural Network (CNN) based method which can extract different features from the QSM image to further support the diagnosis of PD. Finally, we combine these two types of features and we find that the radiomics features and CNN features are complementary to each other, which helps further improve the classification (diagnostic) performance. We conclude that: (1) radiomics features from QSM data have significant clinical value for the diagnosis of PD; (2) CNN features are also useful in the diagnosis of PD; and (3) the combination of radiomics features and CNN features can enhance the diagnostic accuracy.

IJCAI Conference 2019 Conference Paper

Rapid Performance Gain through Active Model Reuse

Feng Shi
Yu-Feng Li

Model reuse aims at reducing the need of learning resources for a newly target task. In previous model reuse studies, the target task usually receives labeled data passively, which results in a slow performance improvement. However, learning models for target tasks are often required to achieve good enough performance rapidly for practical usage. In this paper, we propose the AcMR (Active Model Reuse) method for the rapid performance improvement problem. Firstly, we construct queries through pre-trained models to facilitate the active learner when labeled examples are insufficient in the target task. Secondly, we consider that pre-trained models are able to filter out not-very-necessary queries so that AcMR can save considerable queries compared with direct active learning. Theoretical analysis verifies that AcMR requires fewer queries than direct active learning. Experimental results validate the effectiveness of AcMR.

AAAI Conference 2018 Conference Paper

Interpreting CNN Knowledge via an Explanatory Graph

Quanshi Zhang
Ruiming Cao
Feng Shi
Ying Nian Wu
Song-Chun Zhu

This paper learns a graphical model, namely an explanatory graph, which reveals the knowledge hierarchy hidden inside a pre-trained CNN. Considering that each ﬁlter1 in a convlayer of a pre-trained CNN usually represents a mixture of object parts, we propose a simple yet efﬁcient method to automatically disentangles different part patterns from each ﬁlter, and construct an explanatory graph. In the explanatory graph, each node represents a part pattern, and each edge encodes co-activation relationships and spatial relationships between patterns. More importantly, we learn the explanatory graph for a pre-trained CNN in an unsupervised manner, i. e. without a need of annotating object parts. Experiments show that each graph node consistently represents the same object part through different images. We transfer part patterns in the explanatory graph to the task of part localization, and our method signiﬁcantly outperforms other approaches.

YNIMG Journal 2016 Journal Article

Joint feature-sample selection and robust diagnosis of Parkinson's disease from MRI data

Ehsan Adeli
Feng Shi
Le An
Chong-Yaw Wee
Guorong Wu
Tao Wang
Dinggang Shen

Parkinson's disease (PD) is an overwhelming neurodegenerative disorder caused by deterioration of a neurotransmitter, known as dopamine. Lack of this chemical messenger impairs several brain regions and yields various motor and non-motor symptoms. Incidence of PD is predicted to double in the next two decades, which urges more research to focus on its early diagnosis and treatment. In this paper, we propose an approach to diagnose PD using magnetic resonance imaging (MRI) data. Specifically, we first introduce a joint feature-sample selection (JFSS) method for selecting an optimal subset of samples and features, to learn a reliable diagnosis model. The proposed JFSS model effectively discards poor samples and irrelevant features. As a result, the selected features play an important role in PD characterization, which will help identify the most relevant and critical imaging biomarkers for PD. Then, a robust classification framework is proposed to simultaneously de-noise the selected subset of features and samples, and learn a classification model. Our model can also de-noise testing samples based on the cleaned training data. Unlike many previous works that perform de-noising in an unsupervised manner, we perform supervised de-noising for both training and testing data, thus boosting the diagnostic accuracy. Experimental results on both synthetic and publicly available PD datasets show promising results. To evaluate the proposed method, we use the popular Parkinson's progression markers initiative (PPMI) database. Our results indicate that the proposed method can differentiate between PD and normal control (NC), and outperforms the competing methods by a relatively large margin. It is noteworthy to mention that our proposed framework can also be used for diagnosis of other brain disorders. To show this, we have also conducted experiments on the widely-used ADNI database. The obtained results indicate that our proposed method can identify the imaging biomarkers and diagnose the disease with favorable accuracies compared to the baseline methods.

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.

YNIMG Journal 2015 Journal Article

LINKS: Learning-based multi-source IntegratioN frameworK for Segmentation of infant brain images

Li Wang
Yaozong Gao
Feng Shi
Gang Li
John H. Gilmore
Weili Lin
Dinggang Shen

Segmentation of infant brain MR images is challenging due to insufficient image quality, severe partial volume effect, and ongoing maturation and myelination processes. In the first year of life, the image contrast between white and gray matters of the infant brain undergoes dramatic changes. In particular, the image contrast is inverted around 6–8months of age, and the white and gray matter tissues are isointense in both T1- and T2-weighted MR images and thus exhibit the extremely low tissue contrast, which poses significant challenges for automated segmentation. Most previous studies used multi-atlas label fusion strategy, which has the limitation of equally treating the different available image modalities and is often computationally expensive. To cope with these limitations, in this paper, we propose a novel learning-based multi-source integration framework for segmentation of infant brain images. Specifically, we employ the random forest technique to effectively integrate features from multi-source images together for tissue segmentation. Here, the multi-source images include initially only the multi-modality (T1, T2 and FA) images and later also the iteratively estimated and refined tissue probability maps of gray matter, white matter, and cerebrospinal fluid. Experimental results on 119 infants show that the proposed method achieves better performance than other state-of-the-art automated segmentation methods. Further validation was performed on the MICCAI grand challenge and the proposed method was ranked top among all competing methods. Moreover, to alleviate the possible anatomical errors, our method can also be combined with an anatomically-constrained multi-atlas labeling approach for further improving the segmentation accuracy.

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.

NeurIPS Conference 2015 Conference Paper

Robust Feature-Sample Linear Discriminant Analysis for Brain Disorders Diagnosis

Ehsan Adeli-Mosabbeb
Kim-Han Thung
Le An
Feng Shi
Dinggang Shen

A wide spectrum of discriminative methods is increasingly used in diverse applications for classification or regression tasks. However, many existing discriminative methods assume that the input data is nearly noise-free, which limits their applications to solve real-world problems. Particularly for disease diagnosis, the data acquired by the neuroimaging devices are always prone to different sources of noise. Robust discriminative models are somewhat scarce and only a few attempts have been made to make them robust against noise or outliers. These methods focus on detecting either the sample-outliers or feature-noises. Moreover, they usually use unsupervised de-noising procedures, or separately de-noise the training and the testing data. All these factors may induce biases in the learning process, and thus limit its performance. In this paper, we propose a classification method based on the least-squares formulation of linear discriminant analysis, which simultaneously detects the sample-outliers and feature-noises. The proposed method operates under a semi-supervised setting, in which both labeled training and unlabeled testing data are incorporated to form the intrinsic geometry of the sample space. Therefore, the violating samples or feature values are identified as sample-outliers or feature-noises, respectively. We test our algorithm on one synthetic and two brain neurodegenerative databases (particularly for Parkinson's disease and Alzheimer's disease). The results demonstrate that our method outperforms all baseline and state-of-the-art methods, in terms of both accuracy and the area under the ROC curve.

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.

YNIMG Journal 2014 Journal Article

Integration of sparse multi-modality representation and anatomical constraint for isointense infant brain MR image segmentation

Li Wang
Feng Shi
Yaozong Gao
Gang Li
John H. Gilmore
Weili Lin
Dinggang Shen

Segmentation of infant brain MR images is challenging due to poor spatial resolution, severe partial volume effect, and the ongoing maturation and myelination processes. During the first year of life, the brain image contrast between white and gray matters undergoes dramatic changes. In particular, the image contrast inverses around 6–8months of age, where the white and gray matter tissues are isointense in T1 and T2 weighted images and hence exhibit the extremely low tissue contrast, posing significant challenges for automated segmentation. In this paper, we propose a general framework that adopts sparse representation to fuse the multi-modality image information and further incorporate the anatomical constraints for brain tissue segmentation. Specifically, we first derive an initial segmentation from a library of aligned images with ground-truth segmentations by using sparse representation in a patch-based fashion for the multi-modality T1, T2 and FA images. The segmentation result is further iteratively refined by integration of the anatomical constraint. The proposed method was evaluated on 22 infant brain MR images acquired at around 6months of age by using a leave-one-out cross-validation, as well as other 10 unseen testing subjects. Our method achieved a high accuracy for the Dice ratios that measure the volume overlap between automated and manual segmentations, i. e. , 0. 889±0. 008 for white matter and 0. 870±0. 006 for gray matter.

YNIMG Journal 2014 Journal Article

Measuring the dynamic longitudinal cortex development in infants by reconstruction of temporally consistent cortical surfaces

Gang Li
Jingxin Nie
Li Wang
Feng Shi
John H. Gilmore
Weili Lin
Dinggang Shen

Quantitative measurement of the dynamic longitudinal cortex development during early postnatal stages is of great importance to understand the early cortical structural and functional development. Conventional methods usually reconstruct the cortical surfaces of longitudinal images from the same subject independently, which often generate longitudinally-inconsistent cortical surfaces and thus lead to inaccurate measurement of cortical changes, especially for vertex-wise mapping of cortical development. This paper aims to address this problem by presenting a method to reconstruct temporally-consistent cortical surfaces from longitudinal infant brain MR images, for accurate and consistent measurement of the dynamic cortex development in infants. Specifically, the longitudinal development of the inner cortical surface is first modeled by a deformable growth sheet with elasto-plasticity property to establish longitudinally smooth correspondences of the inner cortical surfaces. Then, the modeled longitudinal inner cortical surfaces are jointly deformed to locate both inner and outer cortical surfaces with a spatial–temporal deformable surface method. The method has been applied to 13 healthy infants, each with 6 serial MR scans acquired at 2weeks, 3months, 6months, 9months, 12months and 18months of age. Experimental results showed that our method with the incorporated longitudinal constraints can reconstruct the longitudinally-dynamic cortical surfaces from serial infant MR images more consistently and accurately than the previously published methods. By using our method, for the first time, we can characterize the vertex-wise longitudinal cortical thickness development trajectory at multiple time points in the first 18months of life. Specifically, we found the highly age-related and regionally-heterogeneous developmental trajectories of the cortical thickness during this period, with the cortical thickness increased most from 3 to 6months (16. 2%) and least from 9 to 12months (less than 0. 1%). Specifically, the central sulcus only underwent significant increase of cortical thickness from 6 to 9months and the occipital cortex underwent significant increase from 0 to 9months, while the frontal, temporal and parietal cortices grew continuously in this first 18months of life. The adult-like spatial patterns of cortical thickness were generally present at 18months of age. These results provided detailed insights into the dynamic trajectory of the cortical thickness development in infants.

YNIMG Journal 2014 Journal Article

Segmentation of neonatal brain MR images using patch-driven level sets

Li Wang
Feng Shi
Gang Li
Yaozong Gao
Weili Lin
John H. Gilmore
Dinggang Shen

The segmentation of neonatal brain MR image into white matter (WM), gray matter (GM), and cerebrospinal fluid (CSF), is challenging due to the low spatial resolution, severe partial volume effect, high image noise, and dynamic myelination and maturation processes. Atlas-based methods have been widely used for guiding neonatal brain segmentation. Existing brain atlases were generally constructed by equally averaging all the aligned template images from a population. However, such population-based atlases might not be representative of a testing subject in the regions with high inter-subject variability and thus often lead to a low capability in guiding segmentation in those regions. Recently, patch-based sparse representation techniques have been proposed to effectively select the most relevant elements from a large group of candidates, which can be used to generate a subject-specific representation with rich local anatomical details for guiding the segmentation. Accordingly, in this paper, we propose a novel patch-driven level set method for the segmentation of neonatal brain MR images by taking advantage of sparse representation techniques. Specifically, we first build a subject-specific atlas from a library of aligned, manually segmented images by using sparse representation in a patch-based fashion. Then, the spatial consistency in the probability maps from the subject-specific atlas is further enforced by considering the similarities of a patch with its neighboring patches. Finally, the probability maps are integrated into a coupled level set framework for more accurate segmentation. The proposed method has been extensively evaluated on 20 training subjects using leave-one-out cross validation, and also on 132 additional testing subjects. Our method achieved a high accuracy of 0. 919±0. 008 for white matter and 0. 901±0. 005 for gray matter, respectively, measured by Dice ratio for the overlap between the automated and manual segmentations in the cortical region.

YNIMG Journal 2012 Journal Article

Altered structural connectivity in neonates at genetic risk for schizophrenia: A combined study using morphological and white matter networks

Feng Shi
Pew-Thian Yap
Wei Gao
Weili Lin
John H. Gilmore
Dinggang Shen

Recently, an increasing body of evidence suggests that developmental abnormalities related to schizophrenia may occur as early as the neonatal stage. Impairments of brain gray matter and wiring problems of axonal fibers are commonly suspected to be responsible for the disconnection hypothesis in schizophrenia adults, but significantly less is known in neonates. In this study, we investigated 26 neonates who were at genetic risk for schizophrenia and 26 demographically matched healthy neonates using both morphological and white matter networks to examine possible brain connectivity abnormalities. The results showed that both populations exhibited small-world network topology. Morphological network analysis indicated that the brain structural associations of the high-risk neonates tended to have globally lower efficiency, longer connection distance, and less number of hub nodes and edges with relatively higher betweenness. Subgroup analysis showed that male neonates were significantly disease-affected, while the female neonates were not. White matter network analysis, however, showed that the fiber networks were globally unaffected, although several subcortical–cortical connections had significantly less number of fibers in high-risk neonates. This study provides new lines of evidence in support of the disconnection hypothesis, reinforcing the notion that the genetic risk of schizophrenia induces alterations in both gray matter structural associations and white matter connectivity.

YNIMG Journal 2012 Journal Article

LABEL: Pediatric brain extraction using learning-based meta-algorithm

Feng Shi
Li Wang
Yakang Dai
John H. Gilmore
Weili Lin
Dinggang Shen

Magnetic resonance imaging of pediatric brain provides valuable information for early brain development studies. Automated brain extraction is challenging due to the small brain size and dynamic change of tissue contrast in the developing brains. In this paper, we propose a novel Learning Algorithm for Brain Extraction and Labeling (LABEL) specially for the pediatric MR brain images. The idea is to perform multiple complementary brain extractions on a given testing image by using a meta-algorithm, including BET and BSE, where the parameters of each run of the meta-algorithm are effectively learned from the training data. Also, the representative subjects are selected as exemplars and used to guide brain extraction of new subjects in different age groups. We further develop a level-set based fusion method to combine multiple brain extractions together with a closed smooth surface for obtaining the final extraction. The proposed method has been extensively evaluated in subjects of three representative age groups, such as neonate (less than 2months), infant (1–2years), and child (5–18years). Experimental results show that, with 45 subjects for training (15 neonates, 15 infant, and 15 children), the proposed method can produce more accurate brain extraction results on 246 testing subjects (75 neonates, 126 infants, and 45 children), i. e. , at average Jaccard Index of 0. 953, compared to those by BET (0. 918), BSE (0. 902), ROBEX (0. 901), GCUT (0. 856), and other fusion methods such as Majority Voting (0. 919) and STAPLE (0. 941). Along with the largely-improved computational efficiency, the proposed method demonstrates its ability of automated brain extraction for pediatric MR images in a large age range.

YNIMG Journal 2011 Journal Article

Automatic segmentation of neonatal images using convex optimization and coupled level sets

Li Wang
Feng Shi
Weili Lin
John H. Gilmore
Dinggang Shen

Accurate segmentation of neonatal brain MR images remains challenging mainly due to their poor spatial resolution, inverted contrast between white matter and gray matter, and high intensity inhomogeneity. Most existing methods for neonatal brain segmentation are atlas-based and voxel-wise. Although active contour/surface models with geometric information constraint have been successfully applied to adult brain segmentation, they are not fully explored in the neonatal image segmentation. In this paper, we propose a novel neonatal image segmentation method by combining local intensity information, atlas spatial prior, and cortical thickness constraint in a single level-set framework. Besides, we also provide a robust and reliable tissue surface initialization for the proposed method by using a convex optimization technique. Thus, tissue segmentation, as well as inner and outer cortical surface reconstruction, can be obtained simultaneously. The proposed method has been tested on a large neonatal dataset, and the validation on 10 neonatal brain images (with manual segmentations) shows very promising results.

YNIMG Journal 2011 Journal Article

Brain anatomical networks in early human brain development

Yong Fan
Feng Shi
Jeffrey Keith Smith
Weili Lin
John H. Gilmore
Dinggang Shen

Recent neuroimaging studies have demonstrated that human brain networks have economic small-world topology and modular organization, enabling efficient information transfer among brain regions. However, it remains largely unknown how the small-world topology and modular organization of human brain networks emerge and develop. Using longitudinal MRI data of 28 healthy pediatric subjects, collected at their ages of 1month, 1year, and 2years, we analyzed development patterns of brain anatomical networks derived from morphological correlations of brain regional volumes. The results show that the brain network of 1-month-olds has the characteristically economic small-world topology and nonrandom modular organization. The network's cost efficiency increases with the brain development to 1year and 2years, so does the modularity, providing supportive evidence for the hypothesis that the small-world topology and the modular organization of brain networks are established during early brain development to support rapid synchronization and information transfer with minimal rewiring cost, as well as to balance between local processing and global integration of information.

YNIMG Journal 2011 Journal Article

Sex differences in grey matter atrophy patterns among AD and aMCI patients: Results from ADNI

Martha Skup
Hongtu Zhu
Yaping Wang
Kelly S. Giovanello
Ja-an Lin
Dinggang Shen
Feng Shi
Wei Gao

We used longitudinal magnetic resonance imaging (MRI) data to determine whether there are any gender differences in grey matter atrophy patterns over time in 197 individuals with probable Alzheimer's disease (AD) and 266 with amnestic mild cognitive impairment (aMCI), compared with 224 healthy controls participating in the Alzheimer's Disease Neuroimaging Initiative (ADNI). While previous research has differentiated probable AD and aMCI groups from controls in brain atrophy, it is unclear whether and how sex plays a role in patterns of change over time. Using regional volumetric maps, we fit longitudinal models to the grey matter data collected at repeated occasions, seeking differences in patterns of volume change over time by sex and diagnostic group in a voxel-wise analysis. Additionally, using a region-of-interest approach, we fit longitudinal models to the global volumetric data of predetermined brain regions to determine whether this more conventional approach is sufficient for determining sex and group differences in atrophy. Our longitudinal analyses revealed that, of the various grey matter regions investigated, males and females in the AD group and the aMCI group showed different patterns of decline over time compared to controls in the bilateral precuneus, bilateral caudate nucleus, right entorhinal gyrus, bilateral thalamus, bilateral middle temporal gyrus, left insula, and right amygdala. As one of the first investigation to model more than two time points of structural MRI data over time, our findings add insight into how AD and aMCI males and females differ from controls and from each other over time.

YNIMG Journal 2010 Journal Article

Construction of multi-region-multi-reference atlases for neonatal brain MRI segmentation

Feng Shi
Pew-Thian Yap
Yong Fan
John H. Gilmore
Weili Lin
Dinggang Shen

Neonatal brain MRI segmentation is a challenging problem due to its poor image quality. Atlas-based segmentation approaches have been widely used for guiding brain tissue segmentation. Existing brain atlases are usually constructed by equally averaging pre-segmented images in a population. However, such approaches diminish local inter-subject structural variability and thus lead to lower segmentation guidance capability. To deal with this problem, we propose a multi-region-multi-reference framework for atlas-based neonatal brain segmentation. For each region of a brain parcellation, a population of spatially normalized pre-segmented images is clustered into a number of sub-populations. Each sub-population of a region represents an independent distribution from which a regional probability atlas can be generated. A selection of these regional atlases, across different sub-regions, will in the end be adaptively combined to form an overall atlas specific to the query image. Given a query image, the determination of the appropriate set of regional atlases is achieved by comparing the query image regionally with the reference, or exemplar, of each sub-population. Upon obtaining an overall atlas, an atlas-based joint registration–segmentation strategy is employed to segment the query image. Since the proposed method generates an atlas which is significant more similar to the query image than the traditional average-shape atlas, better tissue segmentation results can be expected. This is validated by applying the proposed method on a large set of neonatal brain images available in our institute. Experimental results on a randomly selected set of 10 neonatal brain images indicate that the proposed method achieves higher tissue overlap rates and lower standard deviations (SDs) in comparison with manual segmentations, i. e. , 0. 86 (SD 0. 02) for GM, 0. 83 (SD 0. 03) for WM, and 0. 80 (SD 0. 05) for CSF. The proposed method also outperforms two other average-shape atlas-based segmentation methods.

YNIMG Journal 2010 Journal Article

Neonatal brain image segmentation in longitudinal MRI studies

Feng Shi
Yong Fan
Songyuan Tang
John H. Gilmore
Weili Lin
Dinggang Shen

In the study of early brain development, tissue segmentation of neonatal brain MR images remains challenging because of the insufficient image quality due to the properties of developing tissues. Among various brain tissue segmentation algorithms, atlas-based brain image segmentation can potentially achieve good segmentation results on neonatal brain images. However, their performances rely on both the quality of the atlas and the spatial correspondence between the atlas and the to-be-segmented image. Moreover, it is difficult to build a population atlas for neonates due to the requirement of a large set of tissue-segmented neonatal brain images. To combat these obstacles, we present a longitudinal neonatal brain image segmentation framework by taking advantage of the longitudinal data acquired at late time-point to build a subject-specific tissue probabilistic atlas. Specifically, tissue segmentation of the neonatal brain is formulated as two iterative steps of bias correction and probabilistic-atlas-based tissue segmentation, along with the longitudinal atlas reconstructed by the late time image of the same subject. The proposed method has been evaluated qualitatively through visual inspection and quantitatively by comparing with manual delineations and two population-atlas-based segmentation methods. Experimental results show that the utilization of a subject-specific probabilistic atlas can substantially improve tissue segmentation of neonatal brain images.