Zhao Zhang

EAAI Journal 2026 Journal Article

An enhanced you only look once model for multi-class apple detection in natural orchard environments

• Xiaohang Liu
• Zhao Zhang
• Jiangfan Yu
• Wanjia Hua
• Xu Li
• Han Li
• Man Zhang
• Chayan Kumer Saha

Multi-class apple detection can improve automatic apple-picking robots' efficiency. Existing studies classified apples into four occlusion types but struggled with clustered fruits and could not balance precision, speed, and model size. A robust Apple State You Only Look Once version 8 medium (AS-YOLOv8m) model was thus proposed for detecting apples into 11 classes according to the apples’ occlusion and clustering conditions. Core innovations included: (i) A cross-stage partial bottleneck module with the deformable convolution was designed to enhance feature extraction and geometric transformation modeling capabilities; (ii) the space-to-depth convolution module was embedded in the backbone network to improve small target detection; (iii) the large-target detection head was removed to lighten the model size; and (iv) the wise intersection over union box loss function was used to balance the loss of high- and low-quality anchor boxes. The model was trained (5, 845 images), validated (1, 948 images), and tested (1, 950 images) using 9, 743 apple images, which were augmented from 1, 149 original captures collected from commercial orchards under diverse lighting conditions. Results showed that AS-YOLOv8m achieved a higher mean average precision of 95. 8% in 11 classes than that of 95. 4% in 4 classes, which also outperformed other comparison models (<95. 1%) and prior research results (<91. 3%). The detection speed was 76. 9 frames per second, and the model size was 36. 2 megabytes. With its real-time capability, small model size, and high detection precision, the AS-YOLOv8m model stands as a promising multi-class apple detection method for the further improvement of robot picking effect and efficiency.

TCS Journal 2026 Journal Article

Approximation algorithm for fair stochastic maximum coverage problem

• Mingchao Zhou
• Zhao Zhang

We propose the fair stochastic maximum coverage (FSMC) problem. Given an element set U and a collection of sets S partitioned into ℓ disjoint groups S 1, ⋯, S ℓ, each set S has a cost c S. For a set of demand scenarios Ω, each occurring with probability p ω, let r e, ω ∈ {0, 1} indicate whether element e is demanded in scenario ω. The objective is to choose a subcollection F ⊆ S maximizing the expected number of demanded elements covered, subject to a global budget ∑ S ∈ F c S ≤ B and fairness constraints L i ≤ ∑ S ∈ F ∩ S i c S ≤ B i for each group. FSMC strictly generalizes the maximum group set cover (MGSC) problem by incorporating both stochasticity and lower-bound fairness constraints. Under two mild assumptions, we design a deterministic 1 2 ( 1 − ( 1 − 1 f ) f ) -approximation algorithm running in O ( T + n ) time, where f is the maximum frequency of any element, T is the LP-solving time, and n = | S |. Relaxing one assumption yields a bi-criteria algorithm with the same ratio and total budget at most 2 B. For the cardinality version (FCSMC), our algorithm achieves an unconditional ( 1 − ( 1 − 1 f ) f ) -approximation. When L i ≡ 0, FSMC reduces to the stochastic MGSC problem, where we obtain approximation ratio 1 2 ( 1 − ( 1 − 1 f ) f ) > 0. 316 under the relaxed assumption, and 1 3 ( 1 − ( 1 − 1 f ) f ) > 0. 2107 without assumptions, improving the previous best-known polynomial-time approximation ratio of 0. 2.

AAAI Conference 2026 Conference Paper

Multi-Aspect Cross-modal Quantization for Generative Recommendation

• Fuwei Zhang
• Xiaoyu Liu
• Dongbo Xi
• Jishen Yin
• Huan Chen
• Peng Yan
• Fuzhen Zhuang
• Zhao Zhang

Generative Recommendation (GR) has emerged as a new paradigm in recommender systems. This approach relies on quantized representations to discretize item features, modeling users’ historical interactions as sequences of discrete tokens. Based on these tokenized sequences, GR predicts the next item by employing next-token prediction methods. The challenges of GR lie in constructing high-quality semantic identifiers (IDs) that are hierarchically organized, minimally conflicting, and conducive to effective generative model training. However, current approaches remain limited in their ability to harness multimodal information and to capture the deep and intricate interactions among diverse modalities, both of which are essential for learning high-quality semantic IDs and for effectively training GR models. To address this, we propose Multi-Aspect Cross-modal quantization for generative Recommendation (MACRec), which introduces multimodal information and incorporates it into both semantic ID learning and generative model training from different aspects. Specifically, we first introduce cross-modal quantization during the ID learning process, which effectively reduces conflict rates and thus improves codebook usability through the complementary integration of multimodal information. In addition, to further enhance the generative ability of our GR model, we incorporate multi-aspect cross-modal alignments, including the implicit and explicit alignments. Finally, we conduct extensive experiments on three well-known recommendation datasets to demonstrate the effectiveness of our proposed method.

TCS Journal 2026 Journal Article

Partial interval multicover: Approximation and complexity

• Peng Li
• Xiangzhi Tu
• Zhao Zhang
• Yixin Cao

We study a variant of set cover on the real line, where elements are points, sets are intervals, and each point has an integer demand; a point is fully covered when it is contained in at least its demand many chosen intervals. The objective is to select the fewest intervals that fully cover at least a specified number of points. We present the first polynomial-time approximation scheme (PTAS) for the unweighted version of this problem and show that a natural weighted generalization is NP-complete.

TCS Journal 2025 Journal Article

A 1/2-approximation algorithm for maximum interval multi-cover

• Yuxuan Xu
• Yingli Ran
• Zhao Zhang

Given a set of points P on a line, a collection of intervals I along the line, and a positive integer K ≤ | I |, each point p ∈ P is associated with a covering requirement q p, the goal of the maximum interval multi-cover (MaxIMC) problem is to find a sub-collection of intervals I ′ ⊆ I with | I ′ | ≤ K to maximize the number of fully-covered points, where a point p is fully-covered by I ′ if it belongs to at least q p intervals of I ′. In this paper, we present a 1 2 -approximation algorithm for the MaxIMC problem.

ICML Conference 2025 Conference Paper

Decomposition of Graphic Design with Unified Multimodal Model

• Hui Nie 0001
• Zhao Zhang
• Yutao Cheng
• Maoke Yang
• Gonglei Shi
• Qingsong Xie
• Jie Shao
• Xinglong Wu

We propose Layer Decomposition of Graphic Designs (LDGD), a novel vision task that converts composite graphic design (e. g. , posters) into structured representations comprising ordered RGB-A layers and metadata. By transforming visual content into structured data, LDGD facilitates precise image editing and offers significant advantages for digital content creation, management, and reuse. This task presents two core challenges: (1) predicting the attribute information (metadata) of each layer, and (2) recovering the occluded regions within overlapping layers to enable high-fidelity image reconstruction. To address this, we present the Decompose Layer Model (DeaM), a large unified multimodal model that integrates a conjoined visual encoder, a language model, and a condition-aware RGB-A decoder. DeaM adopts a two-stage processing pipeline: first generates layer-specific metadata containing information such as spatial coordinates and quantized encodings, and then reconstructs pixel-accurate layer images using a condition-aware RGB-A decoder. Beyond full decomposition, the model supports interactive decomposition via textual or point-based prompts. Extensive experiments demonstrate the effectiveness of the proposed method. The code is accessed at https: //github. com/witnessai/DeaM.

IROS Conference 2025 Conference Paper

DPSN: Dual Prior Knowledge Induced Tactile paving and Obstacle Joint Segmentation Network

• Youqi Song
• Wenqi Li
• Zhao Zhang
• Yu Wu
• Zilong Jin
• Changbo Wang
• Gaoqi He

Accurate semantic segmentation of both tactile paving and the obstacle is crucial for the safe mobility of visually impaired individuals. However, existing methods face two major challenges: (i) discontinuous segmentation fragments; (ii) Inaccurate obstacle recognition. To address challenge (i), we propose incorporating appearance priors of complete tactile pavings to prevent the model from directly learning irregular ground truth masks. To tackle challenge (ii), we propose introducing cross-modal semantic priors to complement the semantic information of obstacles. We implemented these strategies in proposed Dual Prior knowledge induced tactile paving and obstacle joint Segmentation Network (DPSN). Based on bilateral network architecture, DPSN merges obstacle category masks into tactile paving categories, constructing a complete tactile paving mask. Utilizing the complete mask, DPSN transfer appearance prior knowledge to detail features from boundary and structural perspectives. Concurrently, DPSN leverages the CLIP Text Encoder to guide visual feature decoding by attention mechanisms, transferring rich cross-modal semantic prior knowledge to the visual feature maps. Furthermore, we propose the TPO-Dataset, the first dataset for joint tactile paving and obstacle segmentation acquired from actual scenes. Experiments demonstrate that DPSN achieves state-of-the-art results on the TPO-Dataset, with relative gains of 27. 16% in obstacle IoU and 30. 53% in accuracy metrics compared to baseline methods. Notably, DPSN achieves real-time performance at 88. 25 FPS on the maximum scale of 2048×512 resolution.

AAAI Conference 2025 Conference Paper

FakeDiffer: Distributional Disparity Learning on Differentiated Reconstruction for Face Forgery Detection

• Bo Wang
• Zhao Zhang
• Suiyi Zhao
• Xianming Ye
• Haijun Zhang
• Meng Wang

Existing face forgery detection methods achieve promising performance when training and testing forgery data are from identical manipulation types, while they fail to generalize well to unseen samples. In this paper, we experimentally investigate and find that the poor generalization of the methods mainly arises from their overfitting on the known fake patterns. Excessively focused on seen fakes, those detectors fail to effectively learn image-intrinsic information and the distributional disparity between real and fake images. Then, to address this issue, we redefine fake learning as real-fake distributional disparity learning. We propose a novel deepfake detection framework learning distributional disparity based on the differentiated reconstruction on real and fake images for improved generalization. Specifically, distributional disparity learning on differentiated reconstruction of the real and fake images, enforces the model to learn image-invariant intrinsic representations. The reconstruction on real and fake images forces the decoders to learn the distribution of real and fake images, respectively. Moreover, to avoid the influence from the specificalization of the known fake patterns, we further propose the information interaction learning on the encoded intrinsic information and the pixel disparity between the input image and its reconstruction to distinguish face forgeries that are even unknown. Extensive experiments on large-scale benchmark datasets demonstrated the effectiveness of addressing the overfitting issue of the classification network, and verified the superior performance of our method.

AAAI Conference 2025 Conference Paper

FashionTailor: Controllable Clothing Editing for Human Images with Appearance Preserving

• Jie Hou
• Jianghong Ma
• Xiangyu Mu
• Haijun Zhang
• Zhao Zhang

The garment structure serves as a crucial medium for expressing the designer's creative vision and showcasing the distinctive character of clothing items. Effective editing of garment structure in fashion images allows for an advanced preview of the design, accelerating the process of garment customization to meet individualized requirements. Although large-scale diffusion models have demonstrated impressive image generation and editing capabilities, no efforts have been made to exploit their potential in part-level editing of images. Unlike previous research, we define a clothing structure editing (CSE) task aimed at accurately editing the local structure of human-centered clothing images through simple instruction-based prompts while maintaining the consistency of clothing appearance. Specifically, this paper develops a new controllable triple-flow framework for structure editing named FashionTailor. An additional network called ClothingNet is proposed to extract the clothing details to address the rigid constraints of the original garment structure. Then, we propose a semantic-refined module to extract the semantic understanding of the source image and adaptively focus on the part to be edited. We also design a cross-blend attention mechanism to integrate fine-grained clothing features to guarantee precise alignment between appearance and target structure features. In addition, a garment structure dataset called StructureFashion has been collated, wherein each item of clothing is represented by multiple photos with diverse structure characteristics, containing over six million pairs. Finally, our method supports editing the structure of multiple parts on a garment simultaneously. Extensive experiments validate the effectiveness of our method for editing part-level human images in StructureFashion dataset and real-scenarios.

IJCAI Conference 2025 Conference Paper

FCKT: Fine-Grained Cross-Task Knowledge Transfer with Semantic Contrastive Learning for Targeted Sentiment Analysis

• Wei Chen
• Zhao Zhang
• Meng Yuan
• Kepeng Xu
• Fuzhen Zhuang

In this paper, we address the task of targeted sentiment analysis, which involves two sub-tasks, i. e. , identifying specific aspects from reviews and determining their corresponding senti-ments. Aspect extraction forms the foundation for sentiment prediction, highlighting the critical dependency between these two tasks for effective cross-task knowledge transfer. While most existing studies adopt a multi-task learning paradigm to align task-specific features in the latent space, they predominantly rely on coarse-grained knowledge transfer. Such approaches lack fine-grained control over aspect-sentiment relationships, often assuming uniform sentiment polarity within related aspects. This oversimplification neglects contextual cues that differentiate sentiments, leading to negative transfer. To overcome these limitations, we propose FCKT, a fine-grained cross-task knowledge transfer framework tailored for TSA. By explicitly incorporating aspect-level information into sentiment prediction, our framework achieves fine-grained knowledge transfer, effectively mitigating negative transfer and enhancing task performance. Extensive experiments on three real-world datasets, including comparisons with various baselines and large language models (LLMs), demonstrate the effectiveness of FCKT. The source code is available on https: //github. com/cwei01/FCKT.

AAAI Conference 2025 Conference Paper

Graphic Design with Large Multimodal Model

• Yutao Cheng
• Zhao Zhang
• Maoke Yang
• Hui Nie
• Chunyuan Li
• Xinglong Wu
• Jie Shao

In the field of graphic design, automating the integration of design elements into a cohesive multi-layered artwork not only boosts productivity but also paves the way for the democratization of graphic design. One existing practice is Graphic Layout Generation (GLG), which aims to layout sequential design elements. It has been constrained by the necessity for a predefined correct sequence of layers, thus limiting creative potential and increasing user workload. In this paper, we present Hierarchical Layout Generation (HLG) as a more flexible and pragmatic setup, which creates graphic composition from any-ordered sets of design elements. To tackle the HLG task, we introduce Graphist, the first layout generation model based on large multimodal models. Graphist efficiently reframes the HLG as a sequence generation problem, utilizing RGB-A images as input, outputs a JSON draft protocol, indicating the coordinates, size, and order of each element. We develop multiple evaluation metrics for HLG. Graphist outperforms prior arts and establishes a strong baseline for this field.

AAAI Conference 2025 Conference Paper

Mixed-Curvature Multi-Modal Knowledge Graph Completion

• Yuxiao Gao
• Fuwei Zhang
• Zhao Zhang
• Xiaoshuang Min
• Fuzhen Zhuang

Multi-modal Knowledge Graph Completion (KGC), which aims to enrich knowledge graph embeddings by incorporating images and text as supplementary information alongside triplets, is an significant task in learning KGs. Existing multi-modal KGC methods mainly focus on modalitylevel fusion, neglecting the importance of modeling the complex structures, such as hierarchical and circular patterns. To address this, we propose a Mixed-Curvature multi-modal Knowledge Graph Completion method (MCKGC) that embeds the information into three single-curvature spaces, including hyperbolic space, hyperspherical space, and Euclidean space, and incorporates multi-modal information into a mixed space. Specifically, MCKGC consists of Modality Information Mixed-Curvature Module (MIMCM) and Progressive Fusion Module (PFM). To improve the expressive ability for different modalities, MIMCM introduces multi-modal information into three single-curvature spaces for interaction. Then, to extract useful information from different modalities and capture the complex structure from the geometric information, PFM implements a progressive fusion strategy by utilizing modality-level and space-level gates to adaptively incorporate the information from different spaces. Extensive experiments on three widely used benchmarks demonstrate the effectiveness of our method.

NeurIPS Conference 2025 Conference Paper

Rethinking Out-of-Distribution Detection and Generalization with Collective Behavior Dynamics

• Zhenbin Wang
• Lei Zhang
• Wei Huang
• Zhao Zhang
• Zizhou Wang

Out-of-distribution (OOD) problems commonly occur when models process data with a distribution significantly deviates from the in-distribution (InD) training data. In this paper, we hypothesize that a $\textit{field}$ or $\textit{potential}$ more essential than features exists, and features are not the ultimate essence of the data but rather manifestations of them during training. we investigate OOD problems from the perspective of collective behavior dynamics. With this in mind, we first treat the output of the feature extractor as charged particles and investigate their collective behavior dynamics within a self-consistent electric field. Then, to characterize the relationship between OOD problems and dynamical equations, we introduce the $\textit{basin of attraction}$ and prove that its boundary can be represented as the zero level set of a differentiable function of the potential, $\textit{i. e. }$, the spatial integral of field. We further demonstrate that: $\textit{i)}$ InD and OOD inputs can be effectively separated based on whether they are steady state solutions for specific field conditions, enabling robust OOD detection and outperforming prior methods over three benchmarks. $\textit{ii)}$ the generalization capability correlates positively with the basin of attraction. By analyzing the dynamics of perturbations, we propose that the potential is well-characterized by a Fourier-domain form of the Poisson equation. Evaluated on six benchmark datasets, our method rivals the SoTA approaches for OOD generalization and can be seamlessly integrated with them to deliver additional gains.

NeurIPS Conference 2025 Conference Paper

Seeing is Believing? Mitigating OCR Hallucinations in Multimodal Large Language Models

• zhentao he
• Can Zhang
• Ziheng Wu
• Zhenghao Chen
• Yufei Zhan
• Yifan Li
• Zhao Zhang
• Xian Wang

Recent advancements in multimodal large language models (MLLMs) have enhanced document understanding by integrating textual and visual information. However, existing models exhibit incompleteness within their paradigm in real-world scenarios, particularly under visual degradation (e. g. , blur, occlusion, low contrast). In such conditions, the current response paradigm often fails to adequately perceive visual degradation and ambiguity, leading to overreliance on linguistic priors or misaligned visual-textual reasoning. This difficulty in recognizing uncertainty frequently results in the generation of hallucinatory content, especially when a precise answer is not feasible. To better demonstrate and analyze this phenomenon and problem, we propose KIE-HVQA, the first benchmark dedicated to evaluating OCR hallucination in degraded document understanding. This dataset includes test samples spanning identity cards, invoices, and prescriptions, with simulated real-world degradations and pixel-level annotations for OCR reliability. This setup allows for evaluating models' capacity, under degraded input, to distinguish reliable visual information and answer accordingly, thereby highlighting the challenge of avoiding hallucination on uncertain data. To achieve vision-faithful reasoning and thereby avoid the aforementioned issues, we further introduce a Group Relative Policy Optimization (GRPO)-based framework featuring a novel reward mechanism. By incorporating a self-awareness of visual uncertainty and an analysis method that initiates refusal to answer to increase task difficulty within our supervised fine-tuning and reinforcement learning framework, we successfully mitigated hallucinations in ambiguous regions. Experiments on Qwen2. 5-VL demonstrate that our 7B-parameter model achieves a ~28% absolute improvement in hallucination-free accuracy over GPT-4o on KIE-HVQA and there is no significant performance drop in standard tasks, highlighting both effectiveness and robustness. This work advances the development of reliable MLLMs for real-world document analysis by addressing critical challenges in visual-linguistic alignment under degradation.

ICLR Conference 2025 Conference Paper

SLoPe: Double-Pruned Sparse Plus Lazy Low-Rank Adapter Pretraining of LLMs

• Mohammad Mozaffari
• Amir Yazdanbakhsh
• Zhao Zhang
• Maryam Mehri Dehnavi

We propose SLoPe, a Double-Pruned **S**parse Plus **L**azy L**o**w-rank Adapter **P**r**e**training method for LLMs that improves the accuracy of sparse LLMs while accelerating their pretraining and inference and reducing their memory footprint. Sparse pretraining of LLMs reduces the accuracy of the model, to overcome this, prior work uses dense models during fine-tuning. SLoPe improves the accuracy of sparsely pretrained models by adding low-rank adapters in the final 1% iterations of pretraining without adding significant overheads to the model pretraining and inference. In addition, SLoPe uses a double-pruned backward pass formulation that prunes the transposed weight matrix using N:M sparsity structures to enable an accelerated sparse backward pass. SLoPe accelerates the training and inference of models with billions of parameters up to 1.25× and 1.54× respectively (OPT-33B and OPT-66B) while reducing their memory usage by up to 0.63× and 0.61× for training and inference respectively.

AAAI Conference 2025 Conference Paper

Smoothness Really Matters: A Simple Yet Effective Approach for Unsupervised Graph Domain Adaptation

• Wei Chen
• Guo Ye
• Yakun Wang
• Zhao Zhang
• Libang Zhang
• Daixin Wang
• Zhiqiang Zhang
• Fuzhen Zhuang

Unsupervised Graph Domain Adaptation (UGDA) seeks to bridge distribution shifts between domains by transferring knowledge from labeled source graphs to given unlabeled target graphs. Existing UGDA methods primarily focus on aligning features in the latent space learned by graph neural networks (GNNs) across domains, often overlooking structural shifts, resulting in limited effectiveness when addressing structurally complex transfer scenarios. Given the sensitivity of GNNs to local structural features, even slight discrepancies between source and target graphs could lead to significant shifts in node embeddings, thereby reducing the effectiveness of knowledge transfer. To address this issue, we introduce a novel approach for UGDA called Target-Domain Structural Smoothing (TDSS). TDSS is a simple and effective method designed to perform structural smoothing directly on the target graph, thereby mitigating structural distribution shifts and ensuring the consistency of node representations. Specifically, by integrating smoothing techniques with neighbor- hood sampling, TDSS maintains the structural coherence of the target graph while mitigating the risk of over-smoothing. Our theoretical analysis shows that TDSS effectively reduces target risk by improving model smoothness. Empirical results on three real-world datasets demonstrate that TDSS outperforms recent state-of-the-art baselines, achieving significant improvements across six transfer scenarios.

AAAI Conference 2025 Conference Paper

Thinking in Granularity: Dynamic Quantization for Image Super-Resolution by Intriguing Multi-Granularity Clues

• Mingshen Wang
• Zhao Zhang
• Feng Li
• Ke Xu
• Kang Miao
• Meng Wang

Dynamic quantization has attracted rising attention in image super-resolution (SR) as it expands the potential of heavy SR models onto mobile devices while preserving competitive performance. Most current methods explore layer-to-bit configuration upon varying local regions, adaptively allocating the bit to each layer and patch. Despite the benefits, they still fall short in the tradeoff of SR accuracy and quantization efficiency. Apart from this, adapting the quantization level for each layer individually can disturb the original inter-layer relationships, thus diminishing the representation capability of quantized models. In this work, we propose Granular-DQ, which takes advantage of multi-granularity clues and local patch statistics, achieving a distinctive patch-wise and layer-invariant dynamic quantization paradigm. Specifically, Granular-DQ initiates by developing a granularity-bit controller to apprehend the coarse-to-fine granular representations of local patches, matching their proportional contribution to the entire image to determine the proper bit-width allocation. On this premise, we investigate the interrelationships between bit-width and information density within high-bit patches, establishing a soft gate that enables further fine-grained dynamic bit adaption. Extensive experiments validate the superiority of Granular-DQ in the trade-off between efficiency and accuracy over recent state-of-the-art methods on various SR models.

EAAI Journal 2024 Journal Article

An approach to ship target detection based on combined optimization model of dehazing and detection

• Tao Liu
• Zhao Zhang
• Zhengling Lei
• Yuchi Huo
• Shuo Wang
• Jiansen Zhao
• Jinfeng Zhang
• Xin Jin

The design of a ship detection model that can be adapted to both foggy and clear images faces significant challenges. Existing methods are either not accurate enough, or have a high amount of model parameters, making them difficult to deploy to lightweight front-ends. To address these issues, a lightweight deep learning model based on combined optimization of dehazing and detection is proposed, focusing on self-adaptive ship detection. Firstly, a self-adaptive image dehazing module is designed and placed ahead of the detection network, including a dehazing parameter predictor and an improved dehazing method. Subsequently, a lightweight-improved object detection deep learning model integrated with the dehazing module is devised to detect the ship in the foggy image. Experimental results demonstrate the effectiveness of this approach in enabling efficient and accurate ship detection under foggy conditions. Through the joint optimization of the dehazing module and the detection module, it can be seen from the experiments that our Dehazing + Detection model has the highest detection accuracy and performs well in terms of detection speed, parameter amount, and weight file size. The detection accuracy has reached 97. 1%, which is better than that of the other three dehazing + detection models.

AAAI Conference 2024 Conference Paper

Dense Projection for Anomaly Detection

• Dazhi Fu
• Zhao Zhang
• Jicong Fan

This work presents a novel method called dense projection for unsupervised anomaly detection (DPAD). The main idea is maximizing the local density of (normal) training data and then determining whether a test data is anomalous or not by evaluating its density. Specifically, DPAD uses a deep neural network to learn locally dense representations of normal data. Since density estimation is computationally expensive, we minimize the local distances of the representations in an iteratively reweighting manner, where the weights are updated adaptively and the parameters are regularized to avoid model collapse (all representations collapse to a single point). Compared with many state-of-the-art methods of anomaly detection, our DPAD does not rely on any assumption about the distribution or spatial structure of the normal data and representations. Moreover, we provide theoretical guarantees for the effectiveness of DPAD. The experiments show that our method DPAD is effective not only in traditional one-class classification problems but also in scenarios with complex normal data composed of multiple classes.

YNIMG Journal 2024 Journal Article

Evolving brain network dynamics in early childhood: Insights from modular graph metrics

• Zeyu Song
• Zhenqi Jiang
• Zhao Zhang
• Yifei Wang
• Yu Chen
• Xiaoying Tang
• Hanjun Li

Modular dynamic graph theory metrics effectively capture the patterns of dynamic information interaction during human brain development. While existing research has employed modular algorithms to examine the overall impact of dynamic changes in community structure throughout development, there is a notable gap in understanding the cross-community dynamic changes within different functional networks during early childhood and their potential contributions to the efficiency of brain information transmission. This study seeks to address this gap by tracing the trajectories of cross-community structural changes within early childhood functional networks and modeling their contributions to information transmission efficiency. We analyzed 194 functional imaging scans from 83 children aged 2 to 8 years, who participated in passive viewing functional magnetic resonance imaging sessions. Utilizing sliding windows and modular algorithms, we evaluated three spatiotemporal metrics-temporal flexibility, spatiotemporal diversity, and within-community spatiotemporal diversity-and four centrality metrics: within-community degree centrality, eigenvector centrality, between-community degree centrality, and between-community eigenvector centrality. Mixed-effects linear models revealed significant age-related increases in the temporal flexibility of the default mode network (DMN), executive control network (ECN), and salience network (SN), indicating frequent adjustments in community structure within these networks during early childhood. Additionally, the spatiotemporal diversity of the SN also displayed significant age-related increases, highlighting its broad pattern of cross-community dynamic interactions. Conversely, within-community spatiotemporal diversity in the language network exhibited significant age-related decreases, reflecting the network's gradual functional specialization. Furthermore, our findings indicated significant age-related increases in between-community degree centrality across the DMN, ECN, SN, language network, and dorsal attention network, while between-community eigenvector centrality also increased significantly for the DMN, ECN, and SN. However, within-community eigenvector centrality remained stable across all functional networks during early childhood. These results suggest that while centrality of cross-community interactions in early childhood functional networks increases, centrality within communities remains stable. Finally, mediation analysis was conducted to explore the relationships between age, brain dynamic graph metrics, and both global and local efficiency based on community structure. The results indicated that the dynamic graph metrics of the SN primarily mediated the relationship between age and the decrease in global efficiency, while those of the DMN, language network, ECN, dorsal attention network, and SN primarily mediated the relationship between age and the increase in local efficiency. This pattern suggests a developmental trajectory in early childhood from global information integration to local information segregation, with the SN playing a pivotal role in this transformation. This study provides novel insights into the mechanisms by which early childhood brain functional development impacts information transmission efficiency through cross-community adjustments in functional networks.

EAAI Journal 2024 Journal Article

Federated continual representation learning for evolutionary distributed intrusion detection in Industrial Internet of Things

• Zhao Zhang
• Yong Zhang
• Hao Li
• Shenbo Liu
• Wei Chen
• Zhigang Zhang
• Lijun Tang

As a promising paradigm, Federated Learning (FL)-based distributed intrusion detection offers potent protection for the network security of Industrial Internet of Things (IIoT) systems. Nonetheless, the practical deployment of IIoT systems occurs in a highly-complex and dynamic distributed environment. The ever-growing and dynamically-evolving cyber attacks will render the FL-based intrusion detection model inefficient, since FL cannot gracefully learn from the dynamic traffic data streams to identify new attacks. To address this issue, we propose the evolutionary distributed intrusion detection system based on federated continual representation learning, designed to continually capture effective feature representations of emerging attacks from dynamic traffic data streams. Specifically, we develop the supervised contrastive loss and the global information-aware regularization loss to alleviate the catastrophic forgetting on the previously observed attacks and mitigate the data heterogeneity across clients. Besides, we propose the prototype variance-based memory update strategy to ensure the effective memory replay data. Extensive experimental results demonstrate our proposed method outperforms the state-of-the-art methods by 13. 3%–31. 5% in terms of average accuracy on a real energy intrusion detection dataset.

NeurIPS Conference 2024 Conference Paper

GraphMorph: Tubular Structure Extraction by Morphing Predicted Graphs

• Zhao Zhang
• Ziwei Zhao
• Dong Wang
• Liwei Wang

Accurately restoring topology is both challenging and crucial in tubular structure extraction tasks, such as blood vessel segmentation and road network extraction. Diverging from traditional approaches based on pixel-level classification, our proposed method, named GraphMorph, focuses on branch-level features of tubular structures to achieve more topologically accurate predictions. GraphMorph comprises two main components: a Graph Decoder and a Morph Module. Utilizing multi-scale features extracted from an image patch by the segmentation network, the Graph Decoder facilitates the learning of branch-level features and generates a graph that accurately represents the tubular structure in this patch. The Morph Module processes two primary inputs: the graph and the centerline probability map, provided by the Graph Decoder and the segmentation network, respectively. Employing a novel SkeletonDijkstra algorithm, the Morph Module produces a centerline mask that aligns with the predicted graph. Furthermore, we observe that employing centerline masks predicted by GraphMorph significantly reduces false positives in the segmentation task, which is achieved by a simple yet effective post-processing strategy. The efficacy of our method in the centerline extraction and segmentation tasks has been substantiated through experimental evaluations across various datasets. Source code will be released soon.

EAAI Journal 2024 Journal Article

IPNet: Polarization-based Camouflaged Object Detection via dual-flow network

• Xin Wang
• Jiajia Ding
• Zhao Zhang
• Junfeng Xu
• Jun Gao

Camouflaged Object Detection (COD) is a critical task in a variety of domains, such as medicine and military applications. The main challenge in COD is accurately detecting and extracting the concealed object from the complex background. The similarity between the camouflaged objects and their background significantly reduces the accuracy of object extraction. Polarization information can provide valuable insights into the characteristics of objects with different material properties and surface roughness. It reflects the difference in polarization information between the object and the background, which increases the contrast between the two and improves the object detection accuracy even under complex scenes. In this paper, we propose IPNet, an efficient cross-modal fusion network that utilizes both RGB intensity and linear polarization cues to generate scene representation with high contrast. Our novel network architecture dynamically fuses RGB intensity and polarization cues using an efficient cross-modal fusion module, leveraging cross-level contextual information to achieve robust detection. For training and evaluating the proposed network, we construct a polarization-based PCOD_1200 dataset that contains 89 subclasses and 1200 samples. A comprehensive set of experiments demonstrates the effectiveness of IPNet to fuse polarization and RGB intensity information and shows that our approach outperforms state-of-the-art methods.

AAAI Conference 2024 Conference Paper

Modeling Adaptive Inter-Task Feature Interactions via Sentiment-Aware Contrastive Learning for Joint Aspect-Sentiment Prediction

• Wei Chen
• Yuxuan Liu
• Zhao Zhang
• Fuzhen Zhuang
• Jiang Zhong

Aspect prediction (AP) and sentiment prediction (SP) are representative applications in fine-grained sentiment anal- ysis. They can be considered as sequential tasks, where AP identifies mentioned aspects in a sentence, and SP infers fine-grained sentiments for these aspects. Recent models perform the aspect-sentiment prediction in a joint man-ner, but heavily rely on the feature interactions of aspect and sentiment. One drawback is that they ignore correlation strength varies between aspect features and sentiment fea- tures across different sentences, and employ a fixed feature interaction strategy may limit effective knowledge transfer across tasks. To tackle this issue, in this paper, we propose an Adaptive Inter-task Feature Interaction framework, AIFI, for joint aspect-sentiment prediction. Specifically, we introduce a novel contrast-based alignment method based on contrastive learning. Our approach considers the AP-specific and SP-specific representations of a given sentence as a positive pair, while representation of another random sentence serves as a negative example. Moreover, we propose an inter-task feature correlation network to predict the contrast strength, which is determined by the temperature coefficient in the InfoNCE loss. This dynamic correlation adjustment enhances model’s ability to capture proper feature interactions more efficiently. Experimental results on three datasets validate the effectiveness of our approach.

IJCAI Conference 2024 Conference Paper

OSIC: A New One-Stage Image Captioner Coined

• Bo Wang
• Zhao Zhang
• Mingbo Zhao
• Xiaojie Jin
• Mingliang Xu
• Meng Wang

Mainstream image captioning models are usually two-stage captioners, i. e. , encoding the region features by a pre-trained detector and then feeding them into a language model to generate the captions. However, such a two-stage procedure will lead to a task-based information gap that decreases the performance, because the region features in the detection task are suboptimal representations and cannot provide all the necessary information for subsequent captions generation. Besides, the region features are usually represented from the last layer of the detectors that lose the local details of images. In this paper, we propose a novel One-Stage Image Captioner (OSIC) with dynamic multi-sight learning, which directly transforms the images into descriptive sentences in one stage for eliminating the information gap. Specifically, to obtain rich features, multi-level features are captured by Swin Transformer, and then fed into a novel dynamic multi-sight embedding module to exploit both the global structure and local texture of input images. To enhance the global modeling capacity of the visual encoder, we propose a new dual-dimensional refining to non-locally model the features interaction. As a result, OSIC can directly obtain rich semantic information to improve the captioner. Extensive comparisons on the benchmark MS-COCO, Flickr8K and Flickr30K datasets verified the superior performance of our method.

TCS Journal 2024 Journal Article

Selfish bin packing with punishment

• Ling Gai
• Weiwei Zhang
• Zhao Zhang

In this paper we study the problem of selfish bin packing with punishment. Different from the selfish bin packing problem proposed by Bilò in 2006, where the items are astute to minimize their shared proportional cost in a bin, we consider the case that items are into the utility defined as the load of bin it is packed in and, a unilateral moving may incur punishment. We define and consider several kinds of punishment, which can be roughly classified into two types: the punishment according to the behavior and the punishment based on the result. For both types we present the tight bound for Price of Anarchy (PoA) under the objective of minimizing the number of bins used. The results proved show that punishment does not always work, a punishment based on the result can be viewed as a delicate designed threat in advance which could perform much better, with an approximate 1. 48 upper bound comparing to the optimal solution.

AAAI Conference 2024 Conference Paper

Stereo Vision Conversion from Planar Videos Based on Temporal Multiplane Images

• Shanding Diao
• Yuan Chen
• Yang Zhao
• Wei Jia
• Zhao Zhang
• Ronggang Wang

With the rapid development of 3D movie and light-field displays, there is a growing demand for stereo videos. However, generating high-quality stereo videos from planar videos remains a challenging task. Traditional depth-image-based rendering techniques struggle to effectively handle the problem of occlusion exposure, which occurs when the occluded contents become visible in other views. Recently, the single-view multiplane images (MPI) representation has shown promising performance for planar video stereoscopy. However, the MPI still lacks real details that are occluded in the current frame, resulting in blurry artifacts in occlusion exposure regions. In fact, planar videos can leverage complementary information from adjacent frames to predict a more complete scene representation for the current frame. Therefore, this paper extends the MPI from still frames to the temporal domain, introducing the temporal MPI (TMPI). By extracting complementary information from adjacent frames based on optical flow guidance, obscured regions in the current frame can be effectively repaired. Additionally, a new module called masked optical flow warping (MOFW) is introduced to improve the propagation of pixels along optical flow trajectories. Experimental results demonstrate that the proposed method can generate high-quality stereoscopic or light-field videos from a single view and reproduce better occluded details than other state-of-the-art (SOTA) methods. https://github.com/Dio3ding/TMPI

NeurIPS Conference 2023 Conference Paper

Described Object Detection: Liberating Object Detection with Flexible Expressions

• Chi Xie
• Zhao Zhang
• Yixuan Wu
• Feng Zhu
• Rui Zhao
• Shuang Liang

Detecting objects based on language information is a popular task that includes Open-Vocabulary object Detection (OVD) and Referring Expression Comprehension (REC). In this paper, we advance them to a more practical setting called *Described Object Detection* (DOD) by expanding category names to flexible language expressions for OVD and overcoming the limitation of REC only grounding the pre-existing object. We establish the research foundation for DOD by constructing a *Description Detection Dataset* ($D^3$). This dataset features flexible language expressions, whether short category names or long descriptions, and annotating all described objects on all images without omission. By evaluating previous SOTA methods on $D^3$, we find some troublemakers that fail current REC, OVD, and bi-functional methods. REC methods struggle with confidence scores, rejecting negative instances, and multi-target scenarios, while OVD methods face constraints with long and complex descriptions. Recent bi-functional methods also do not work well on DOD due to their separated training procedures and inference strategies for REC and OVD tasks. Building upon the aforementioned findings, we propose a baseline that largely improves REC methods by reconstructing the training data and introducing a binary classification sub-task, outperforming existing methods. Data and code are available at https: //github. com/shikras/d-cube and related works are tracked in https: //github. com/Charles-Xie/awesome-described-object-detection.

YNIMG Journal 2023 Journal Article

Differential responses in the mirror neuron system during imitation of individual emotional facial expressions and association with autistic traits

• Weihua Zhao
• Qi Liu
• Xiaolu Zhang
• Xinwei Song
• Zhao Zhang
• Peng Qing
• Xiaolong Liu
• Siyu Zhu

The mirror neuron system (MNS), including the inferior frontal gyrus (IFG), inferior parietal lobule (IPL) and superior temporal sulcus (STS) plays an important role in action representation and imitation and may be dysfunctional in autism spectrum disorder (ASD). However, it's not clear how these three regions respond and interact during the imitation of different basic facial expressions and whether the pattern of responses is influenced by autistic traits. Thus, we conducted a natural facial expression (happiness, angry, sadness and fear) imitation task in 100 healthy male subjects where expression intensity was measured using facial emotion recognition software (FaceReader) and MNS responses were recorded using functional near-infrared spectroscopy (fNIRS). Autistic traits were measured using the Autism Spectrum Quotient questionnaire. Results showed that imitation of happy expressions produced the highest expression intensity but a small deactivation in MNS responses, suggesting a lower processing requirement compared to other expressions. A cosine similarity analysis indicated a distinct pattern of MNS responses during imitation of each facial expression with functional intra-hemispheric connectivity between the left IPL and left STS being significantly higher during happy compared to other expressions, while inter-hemispheric connectivity between the left and right IPL differed between imitation of fearful and sad expressions. Furthermore, functional connectivity changes during imitation of each different expression could reliably predict autistic trait scores. Overall, the results provide evidence for distinct patterns of functional connectivity changes between MNS regions during imitation of different emotions which are also associated with autistic traits.

TMLR Journal 2023 Journal Article

Euclidean-Norm-Induced Schatten-p Quasi-Norm Regularization for Low-Rank Tensor Completion and Tensor Robust Principal Component Analysis

• Jicong Fan
• Lijun Ding
• Chengrun Yang
• Zhao Zhang
• Madeleine Udell

The nuclear norm and Schatten-$p$ quasi-norm are popular rank proxies in low-rank matrix recovery. However, computing the nuclear norm or Schatten-$p$ quasi-norm of a tensor is hard in both theory and practice, hindering their application to low-rank tensor completion (LRTC) and tensor robust principal component analysis (TRPCA). In this paper, we propose a new class of tensor rank regularizers based on the Euclidean norms of the CP component vectors of a tensor and show that these regularizers are monotonic transformations of tensor Schatten-$p$ quasi-norm. This connection enables us to minimize the Schatten-$p$ quasi-norm in LRTC and TRPCA implicitly via the component vectors. The method scales to big tensors and provides an arbitrarily sharper rank proxy for low-rank tensor recovery compared to the nuclear norm. On the other hand, we study the generalization abilities of LRTC with the Schatten-$p$ quasi-norm regularizer and LRTC with the proposed regularizers. The theorems show that a relatively sharper regularizer leads to a tighter error bound, which is consistent with our numerical results. Particularly, we prove that for LRTC with Schatten-$p$ quasi-norm regularizer on $d$-order tensors, $p=1/d$ is always better than any $p>1/d$ in terms of the generalization ability. We also provide a recovery error bound to verify the usefulness of small $p$ in the Schatten-$p$ quasi-norm for TRPCA. Numerical results on synthetic data and real data demonstrate the effectiveness of the regularization methods and theorems.

NeurIPS Conference 2023 Conference Paper

Graph Convolutional Kernel Machine versus Graph Convolutional Networks

• Zhihao Wu
• Zhao Zhang
• Jicong Fan

Graph convolutional networks (GCN) with one or two hidden layers have been widely used in handling graph data that are prevalent in various disciplines. Many studies showed that the gain of making GCNs deeper is tiny or even negative. This implies that the complexity of graph data is often limited and shallow models are often sufficient to extract expressive features for various tasks such as node classification. Therefore, in this work, we present a framework called graph convolutional kernel machine (GCKM) for graph-based machine learning. GCKMs are built upon kernel functions integrated with graph convolution. An example is the graph convolutional kernel support vector machine (GCKSVM) for node classification, for which we analyze the generalization error bound and discuss the impact of the graph structure. Compared to GCNs, GCKMs require much less effort in architecture design, hyperparameter tuning, and optimization. More importantly, GCKMs are guaranteed to obtain globally optimal solutions and have strong generalization ability and high interpretability. GCKMs are composable, can be extended to large-scale data, and are applicable to various tasks (e. g. , node or graph classification, clustering, feature extraction, dimensionality reduction). The numerical results on benchmark datasets show that, besides the aforementioned advantages, GCKMs have at least competitive accuracy compared to GCNs.

NeurIPS Conference 2023 Conference Paper

MKOR: Momentum-Enabled Kronecker-Factor-Based Optimizer Using Rank-1 Updates

• Mohammad Mozaffari
• Sikan Li
• Zhao Zhang
• Maryam Mehri Dehnavi

This work proposes a Momentum-Enabled Kronecker-Factor-Based Optimizer Using Rank-1 updates, called MKOR, that improves the training time and convergence properties of deep neural networks (DNNs). Second-order techniques, while enjoying higher convergence rates vs first-order counterparts, have cubic complexity with respect to either the model size and/or the training batch size. Hence they exhibit poor scalability and performance in transformer models, e. g. large language models (LLMs), because the batch sizes in these models scale by the attention mechanism sequence length, leading to large model size and batch sizes. MKOR's complexity is quadratic with respect to the model size, alleviating the computation bottlenecks in second-order methods. Because of their high computation complexity, state-of-the-art implementations of second-order methods can only afford to update the second order information infrequently, and thus do not fully exploit the promise of better convergence from these updates. By reducing the communication complexity of the second-order updates as well as achieving a linear communication complexity, MKOR increases the frequency of second order updates. We also propose a hybrid version of MKOR (called MKOR-H) that mid-training falls backs to a first order optimizer if the second order updates no longer accelerate convergence. Our experiments show that MKOR outperforms state -of-the-art first order methods, e. g. the LAMB optimizer, and best implementations of second-order methods, i. e. KAISA/KFAC, up to 2. 57x and 1. 85x respectively on BERT-Large-Uncased on 64 GPUs.

NeurIPS Conference 2022 Conference Paper

A Simple Approach to Automated Spectral Clustering

• Jicong Fan
• Yiheng Tu
• Zhao Zhang
• Mingbo Zhao
• Haijun Zhang

The performance of spectral clustering heavily relies on the quality of affinity matrix. A variety of affinity-matrix-construction (AMC) methods have been proposed but they have hyperparameters to determine beforehand, which requires strong experience and leads to difficulty in real applications, especially when the inter-cluster similarity is high and/or the dataset is large. In addition, we often need to choose different AMC methods for different datasets, which still depends on experience. To solve these two challenging problems, in this paper, we present a simple yet effective method for automated spectral clustering. First, we propose to find the most reliable affinity matrix via grid search or Bayesian optimization among a set of candidates given by different AMC methods with different hyperparameters, where the reliability is quantified by the \textit{relative-eigen-gap} of graph Laplacian introduced in this paper. Second, we propose a fast and accurate AMC method based on least squares representation and thresholding and prove its effectiveness theoretically. Finally, we provide a large-scale extension for the automated spectral clustering method, of which the time complexity is linear with the number of data points. Extensive experiments of natural image clustering show that our method is more versatile, accurate, and efficient than baseline methods.

TCS Journal 2022 Journal Article

Approximation algorithm for prize-collecting sweep cover with base stations

• Wei Liang
• Zhao Zhang

In a sweep cover problem, positions of interest (PoIs) are required to be visited periodically by mobile sensors. In this paper, we propose a new sweep cover problem: the prize-collecting sweep cover problem (PCSC), in which penalty is incurred by those PoIs which are not sweep-covered, and the goal is to minimize the covering cost plus the penalty. Assuming that every mobile sensor has to be linked to some base station, and the number of base stations is upper bounded by a constant, we present a 5-LMP (Lagrangian Multiplier Preserving) algorithm. As a step stone, we propose the prize-collecting forest with k components problem (PCF k ), which might be interesting in its own sense, and presented a 2-LMP for rooted PCF k.

AAAI Conference 2022 Conference Paper

Mind the Gap: Cross-Lingual Information Retrieval with Hierarchical Knowledge Enhancement

• Fuwei Zhang
• Zhao Zhang
• Xiang Ao
• Dehong Gao
• Fuzhen Zhuang
• Yi Wei
• Qing He

Cross-Lingual Information Retrieval (CLIR) aims to rank the documents written in a language different from the user’s query. The intrinsic gap between different languages is an essential challenge for CLIR. In this paper, we introduce the multilingual knowledge graph (KG) to the CLIR task due to the sufficient information of entities in multiple languages. It is regarded as a “silver bullet” to simultaneously perform explicit alignment between queries and documents and also broaden the representations of queries. And we propose a model named CLIR with hierarchical knowledge enhancement (HIKE) for our task. The proposed model encodes the textual information in queries, documents and the KG with multilingual BERT, and incorporates the KG information in the query-document matching process with a hierarchical information fusion mechanism. Particularly, HIKE first integrates the entities and their neighborhood in KG into query representations with a knowledge-level fusion, then combines the knowledge from both source and target languages to further mitigate the linguistic gap with a language-level fusion. Finally, experimental results demonstrate that HIKE achieves substantial improvements over state-ofthe-art competitors.

TCS Journal 2022 Journal Article

Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph

• Weizhi Hong
• Yingli Ran
• Zhao Zhang

In a minimum general partial dominating set problem (MinGPDS), given a graph G = ( V, E ), a profit function p: V → R + and a threshold K, the goal is to find a minimum subset of vertices D ⊆ V such that the total profit of those vertices dominated by D is at least K (a vertex is dominated by D if it is either in D or has at least one neighbor in D). In a maximum general budgeted dominating set problem (MaxGBDS), given a budget B, the goal is to find a vertex set D with at most B vertices such that the total profit of those vertices dominated by D is as large as possible. We present the first parallel algorithms for MinGPDS and MaxGBDS in unit disk graphs. They both run in O ( log ⁡ n ) rounds on O ( n ) machines, and achieve constant approximation ratios.

IJCAI Conference 2022 Conference Paper

Positive-Unlabeled Learning with Adversarial Data Augmentation for Knowledge Graph Completion

• Zhenwei Tang
• Shichao Pei
• Zhao Zhang
• Yongchun Zhu
• Fuzhen Zhuang
• Robert Hoehndorf
• Xiangliang Zhang

Most real-world knowledge graphs (KG) are far from complete and comprehensive. This problem has motivated efforts in predicting the most plausible missing facts to complete a given KG, i. e. , knowledge graph completion (KGC). However, existing KGC methods suffer from two main issues, 1) the false negative issue, i. e. , the sampled negative training instances may include potential true facts; and 2) the data sparsity issue, i. e. , true facts account for only a tiny part of all possible facts. To this end, we propose positive-unlabeled learning with adversarial data augmentation (PUDA) for KGC. In particular, PUDA tailors positive-unlabeled risk estimator for the KGC task to deal with the false negative issue. Furthermore, to address the data sparsity issue, PUDA achieves a data augmentation strategy by unifying adversarial training and positive-unlabeled learning under the positive-unlabeled minimax game. Extensive experimental results on real-world benchmark datasets demonstrate the effectiveness and compatibility of our proposed method.

TCS Journal 2021 Journal Article

Approximation algorithms for the dynamic k-level facility location problems

• Limin Wang
• Zhao Zhang
• Chenchen Wu
• Dachuan Xu
• Xiaoyan Zhang

In this paper, we first consider a dynamic k-level facility location problem, which is a generalization of the k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for this problem which finds a constant factor approximate solution. Then, we investigative the dynamic k-level facility location problem with submodular penalties and outliers, which extend the existing problem on two fronts, namely from static to dynamic and from without penalties (outliers) to penalties (outliers) allowed. Based on primal-dual technique and the triangle inequality property, we also give two constant factor approximation algorithms for the dynamic problem with submodular penalties and outliers, respectively.

TCS Journal 2021 Journal Article

Minimum power partial multi-cover on a line

• Wei Liang
• Menghong Li
• Zhao Zhang
• Xiaohui Huang

This paper studies the minimum power partial multi-cover problem on a line (MinPowPMC-Line), the goal of which is to find an assignment of powers to sensors such that at least a required number of points are covered up to their covering requirements. We first present an LP method to show that the minimum power multi-cover problem on a line (without partial covering requirement) is solvable in polynomial time. But this method no longer works when facing partial covering requirement. We turn to dynamic programming method to find an optimal solution for MinPowPMC-Line in time O ( n 4 m 1 + 2 ( c r m a x ) ), where n, m are the number of points and the number of sensors, respectively, and c r m a x denotes the maximum covering requirement of elements. So, this problem is polynomial-time solvable when c r max is upper bounded by a constant.

AAAI Conference 2021 Conference Paper

Partial-Label and Structure-constrained Deep Coupled Factorization Network

• Yan Zhang
• Zhao Zhang
• Yang Wang
• Zheng Zhang
• Li Zhang
• Shuicheng Yan
• Meng Wang

In this paper, we technically propose an enriched prior guided framework, called Dual-constrained Deep Semi-Supervised Coupled Factorization Network (DS2 CF-Net), for discovering hierarchical coupled data representation. To extract hidden deep features, DS2 CF-Net is formulated as a partial-label and geometrical structure-constrained framework. Specifically, DS2 CF-Net designs a deep factorization architecture using multilayers of linear transformations, which can coupled update both the basis vectors and new representations in each layer. To enable learned deep representations and coefficients to be discriminative, we also consider enriching the supervised prior by joint deep coefficients-based label prediction and then incorporate the enriched prior information as additional label and structure constraints. The label constraint can enable the intra-class samples to have same coordinate in feature space, and the structure constraint forces the coefficients in each layer to be block-diagonal so that the enriched prior using the self-expressive label propagation are more accurate. Our network also integrates the adaptive dualgraph learning to retain the local structures of both data and feature manifolds in each layer. Extensive experiments on image datasets demonstrate the effectiveness of DS2 CF-Net for representation learning and clustering.

AAAI Conference 2021 Conference Paper

Unified Tensor Framework for Incomplete Multi-view Clustering and Missing-view Inferring

• Jie Wen
• Zheng Zhang
• Zhao Zhang
• Lei Zhu
• Lunke Fei
• Bob Zhang
• Yong Xu

In this paper, we propose a novel method, referred to as incomplete multi-view tensor spectral clustering with missingview inferring (IMVTSC-MVI) to address the challenging multi-view clustering problem with missing views. Different from the existing methods which commonly focus on exploring the certain information of the available views while ignoring both of the hidden information of the missing views and the intra-view information of data, IMVTSC-MVI seeks to recover the missing views and explore the full information of such recovered views and available views for data clustering. In particular, IMVTSC-MVI incorporates the feature space based missing-view inferring and manifold space based similarity graph learning into a unified framework. In such a way, IMVTSC-MVI allows these two learning tasks to facilitate each other and can well explore the hidden information of the missing views. Moreover, IMVTSC-MVI introduces the low-rank tensor constraint to capture the high-order correlations of multiple views. Experimental results on several datasets demonstrate the effectiveness of IMVTSC-MVI for incomplete multi-view clustering.

TCS Journal 2020 Journal Article

A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem

• Yishuo Shi
• Yingli Ran
• Zhao Zhang
• Ding-Zhu Du

This paper presents a bicriteria approximation algorithm for the minimum submodular cost partial set multi-cover problem (SCPSMC), the goal of which is to find a minimum cost sub-collection of sets to fully cover q percentage of total profit of all elements, where the cost on sub-collections is a submodular function, and an element e with covering requirement r e is fully covered if it belongs to at least r e picked sets. Assuming that the maximum covering requirement r max = max e ∈ E ⁡ r e is a constant and the cost function is nonnegative and submodular, we give a deterministic ( b / q ε, ( 1 − ε ) ) -bicriteria algorithm for SCPSMC, the output of which fully covers at least ( 1 − ε ) q -percentage of the total profit and the performance ratio is b / q ε, where b = max e ⁡ ( f e r e ) and f e is the number of sets containing element e.

TCS Journal 2020 Journal Article

A game theoretic approach for minimal connected dominating set

• Xiuyang Chen
• Zhao Zhang

Connected dominating set (CDS) is a subset of vertices in a graph which dominates all vertices and induces a connected subgraph. This paper proposes a game theoretic approach to find a CDS, and proves that starting from a non-trivial initial state, every non-trivial Nash equilibrium is a minimal CDS and reaching a non-trivial Nash equilibrium needs O ( n ) rounds in the worst case.

TCS Journal 2020 Journal Article

Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs

• Pengcheng Liu
• Zhao Zhang
• Xiaohui Huang

In this paper, we study the minimum (connected) k-bounded-degree node deletion problem (Min(C)kBDND). For a connected graph G, a constant k and a weight function w: V → R +, a vertex set C ⊆ V ( G ) is a kBDND-set if the maximum degree of graph G − C is at most k. If furthermore, the subgraph of G induced by C is connected, then C is a CkBDND-set. The goal of MinWkBDND (resp. MinWCkBDND) is to find a kBDND-set (resp. CkBDND-set) with the minimum weight. In this paper, we focus on their cardinality versions with w ( v ) ≡ 1, v ∈ V, which are denoted as MinkBDND and MinCkBDND. This paper presents a ( 1 + ε ) and a 3. 76-approximation algorithm for MinkBDND and MinCkBDND on unit disk graphs, respectively, where 0 < ε < 1 is an arbitrary constant.

TCS Journal 2020 Journal Article

Approximation algorithm for minimum weight connected-k-subgraph cover

• Pengcheng Liu
• Zhao Zhang
• Xiaohui Huang

For a given graph G, the minimum weight connected-k-subgraph cover problem (MinWCkSC) is to find a minimum weight vertex subset C of G such that each connected subgraph of G on k vertices contains at least one vertex of C. Previously, Zhang et al. [37] presented a ( k − 1 ) -approximation algorithm for MinWCkSC under the assumption that the girth of G, which is the length of a shortest cycle of G, is at least k. In this paper, we improve this result by showing that ( k − 1 ) -approximation can be achieved when the girth requirement is relaxed from k to 2 k / 3.

IJCAI Conference 2020 Conference Paper

Deep Latent Low-Rank Fusion Network for Progressive Subspace Discovery

• Zhao Zhang
• Jiahuan Ren
• Zheng Zhang
• Guangcan Liu

Low-rank representation is powerful for recover-ing and clustering the subspace structures, but it cannot obtain deep hierarchical information due to the single-layer mode. In this paper, we present a new and effective strategy to extend the sin-gle-layer latent low-rank models into multi-ple-layers, and propose a new and progressive Deep Latent Low-Rank Fusion Network (DLRF-Net) to uncover deep features and struc-tures embedded in input data. The basic idea of DLRF-Net is to refine features progressively from the previous layers by fusing the subspaces in each layer, which can potentially obtain accurate fea-tures and subspaces for representation. To learn deep information, DLRF-Net inputs shallow fea-tures of the last layers into subsequent layers. Then, it recovers the deeper features and hierar-chical information by congregating the projective subspaces and clustering subspaces respectively in each layer. Thus, one can learn hierarchical sub-spaces, remove noise and discover the underlying clean subspaces. Note that most existing latent low-rank coding models can be extended to multi-layers using DLRF-Net. Extensive results show that our network can deliver enhanced perfor-mance over other related frameworks.

AAAI Conference 2020 Conference Paper

Relational Graph Neural Network with Hierarchical Attention for Knowledge Graph Completion

• Zhao Zhang
• Fuzhen Zhuang
• Hengshu Zhu
• Zhiping Shi
• Hui Xiong
• Qing He

The rapid proliferation of knowledge graphs (KGs) has changed the paradigm for various AI-related applications. Despite their large sizes, modern KGs are far from complete and comprehensive. This has motivated the research in knowledge graph completion (KGC), which aims to infer missing values in incomplete knowledge triples. However, most existing KGC models treat the triples in KGs independently without leveraging the inherent and valuable information from the local neighborhood surrounding an entity. To this end, we propose a Relational Graph neural network with Hierarchical ATtention (RGHAT) for the KGC task. The proposed model is equipped with a two-level attention mechanism: (i) the first level is the relation-level attention, which is inspired by the intuition that different relations have different weights for indicating an entity; (ii) the second level is the entity-level attention, which enables our model to highlight the importance of different neighboring entities under the same relation. The hierarchical attention mechanism makes our model more effective to utilize the neighborhood information of an entity. Finally, we extensively validate the superiority of RGHAT against various state-of-the-art baselines.

IJCAI Conference 2020 Conference Paper

Unsupervised Vehicle Re-identification with Progressive Adaptation

• Jinjia Peng
• Yang Wang
• Huibing Wang
• Zhao Zhang
• Xianping Fu
• Meng Wang

Vehicle re-identification (reID) aims at identifying vehicles across different non-overlapping cameras views. The existing methods heavily relied on well-labeled datasets for ideal performance, which inevitably causes fateful drop due to the severe domain bias between the training domain and the real-world scenes; worse still, these approaches required full annotations, which is labor-consuming. To tackle these challenges, we propose a novel Progressive Adaptation Learning method for vehicle reID, named PAL, which infers from the abundant data without annotations. For PAL, a data adaptation module is employed for source domain, which generates the images with similar data distribution to unlabeled target domain as “pseudo target samples”. These pseudo samples are combined with the unlabeled samples that are selected by a dynamic sampling strategy to make training faster. We further proposed a weighted label smoothing (WLS) loss, which considers the similarity between samples with different clusters to balance the confidence of pseudo labels. Comprehensive experimental results validate the advantages of PAL on both VehicleID and VeRi-776 dataset.

IJCAI Conference 2019 Conference Paper

Scalable Block-Diagonal Locality-Constrained Projective Dictionary Learning

• Zhao Zhang
• Weiming Jiang
• Zheng Zhang
• Sheng Li
• Guangcan Liu
• Jie Qin

We propose a novel structured discriminative block- diagonal dictionary learning method, referred to as scalable Locality-Constrained Projective Dictionary Learning (LC-PDL), for efficient representation and classification. To improve the scalability by saving both training and testing time, our LC-PDL aims at learning a structured discriminative dictionary and a block-diagonal representation without using costly l0/l1-norm. Besides, it avoids extra time-consuming sparse reconstruction process with the well-trained dictionary for new sample as many existing models. More importantly, LC-PDL avoids using the com- plementary data matrix to learn the sub-dictionary over each class. To enhance the performance, we incorporate a locality constraint of atoms into the DL procedures to keep local information and obtain the codes of samples over each class separately. A block-diagonal discriminative approximation term is also derived to learn a discriminative projection to bridge data with their codes by extracting the special block-diagonal features from data, which can ensure the approximate coefficients to associate with its label information clearly. Then, a robust multiclass classifier is trained over extracted block-diagonal codes for accurate label predictions. Experimental results verify the effectiveness of our algorithm.

IJCAI Conference 2017 Conference Paper

Integrating Answer Set Programming with Semantic Dictionaries for Robot Task Planning

• Dongcai Lu
• Yi Zhou
• Feng Wu
• Zhao Zhang
• Xiaoping Chen

In this paper, we propose a novel integrated task planning system for service robot in domestic domains. Given open-ended high-level user instructions in natural language, robots need to generate a plan, i. e. , a sequence of low-level executable actions, to complete the required tasks. To address this, we exploit the knowledge on semantic roles of common verbs defined in semantic dictionaries such as FrameNet and integrate it with Answer Set Programming --- a task planning framework with both representation language and solvers. In the experiments, we evaluated our approach using common benchmarks on service tasks and showed that it can successfully handle much more tasks than the state-of-the-art solution. Notably, we deployed the proposed planning system on our service robot for the annual RoboCup@Home competitions and achieved very encouraging results.

TCS Journal 2016 Journal Article

Algorithm for constraint partial inverse matroid problem with weight increase forbidden

• Shuangshuang Li
• Zhao Zhang
• Hong-Jian Lai

In a partial inverse matroid problem, given a matroid M = ( S, I ), a real valued weight function w on S, and an independent set I 0 ∈ I, the goal is to modify the weight w as small as possible to a new weight w ¯ such that there exists a w ¯ -maximum base containing I 0. In this paper, we study a constraint version of the partial inverse matroid problem in which the weight can only be decreased. A polynomial time algorithm is presented under l ∞ -norm.

TCS Journal 2016 Journal Article

Approximation algorithm for the balanced 2-connected k-partition problem

• Di Wu
• Zhao Zhang
• Weili Wu

For two positive integers m, k and a connected graph G = ( V, E ) with a nonnegative vertex weight function w, the balanced m-connected k-partition problem, denoted as BC m P k, is to find a partition of V into k disjoint nonempty vertex subsets ( V 1, V 2, …, V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m-connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G, k ), that is, β m ⁎ ( G, k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) }, where the maximum is taken over all m-connected k-partition of G. In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2, a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k, where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2k-connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v. In the case that every vertex has weight at most W / k, we prove a lower bound β 2 ⁎ ( G, k ) ≥ W / ( 2 k − 1 ) for 2k-connected interval graph G. (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2k-connected interval graphs.

TCS Journal 2015 Journal Article

A PTAS for the minimum weight connected vertex cover P 3 problem on unit disk graphs

• Limin Wang
• Xiaoyan Zhang
• Zhao Zhang
• Hajo Broersma

Let G = ( V, E ) be a weighted graph, i. e. , with a vertex weight function w: V → R +. We study the problem of determining a minimum weight connected subgraph of G that has at least one vertex in common with all paths of length two in G. It is known that this problem is NP-hard for general graphs. We first show that it remains NP-hard when restricted to unit disk graphs. Our main contribution is a polynomial time approximation scheme for this problem if we assume that the problem is c-local and the unit disk graphs have minimum degree of at least two.

TIST Journal 2015 Journal Article

A Sparse Projection and Low-Rank Recovery Framework for Handwriting Representation and Salient Stroke Feature Extraction

• Zhao Zhang
• Cheng-Lin Liu
• Ming-Bo Zhao

In this article, we consider the problem of simultaneous low-rank recovery and sparse projection. More specifically, a new Robust Principal Component Analysis (RPCA)-based framework called Sparse Projection and Low-Rank Recovery (SPLRR) is proposed for handwriting representation and salient stroke feature extraction. In addition to achieving a low-rank component encoding principal features and identify errors or missing values from a given data matrix as RPCA, SPLRR also learns a similarity-preserving sparse projection for extracting salient stroke features and embedding new inputs for classification. These properties make SPLRR applicable for handwriting recognition and stroke correction and enable online computation. A cosine-similarity-style regularization term is incorporated into the SPLRR formulation for encoding the similarities of local handwriting features. The sparse projection and low-rank recovery are calculated from a convex minimization problem that can be efficiently solved in polynomial time. Besides, the supervised extension of SPLRR is also elaborated. The effectiveness of our SPLRR is examined by extensive handwritten digital repairing, stroke correction, and recognition based on benchmark problems. Compared with other related techniques, SPLRR delivers strong generalization capability and state-of-the-art performance for handwriting representation and recognition.

TCS Journal 2015 Journal Article

Preface

• Zhao Zhang
• Lidong Wu
• Ding-Zhu Du

TAAS Journal 2014 Journal Article

A Host-Based Approach for Unknown Fast-Spreading Worm Detection and Containment

• Songqing Chen
• Lei Liu
• Xinyuan Wang
• Xinwen Zhang
• Zhao Zhang

The fast-spreading worm, which immediately propagates itself after a successful infection, is becoming one of the most serious threats to today’s networked information systems. In this article, we present WormTerminator, a host-based solution for fast Internet worm detection and containment with the assistance of virtual machine techniques based on the fast-worm defining characteristic. In WormTerminator, a virtual machine cloning the host OS runs in parallel to the host OS. Thus, the virtual machine has the same set of vulnerabilities as the host. Any outgoing traffic from the host is diverted through the virtual machine. If the outgoing traffic from the host is for fast worm propagation, the virtual machine should be infected and will exhibit worm propagation pattern very quickly because a fast-spreading worm will start to propagate as soon as it successfully infects a host. To prove the concept, we have implemented a prototype of WormTerminator and have examined its effectiveness against the real Internet worm Linux/Slapper. Our empirical results confirm that WormTerminator is able to completely contain worm propagation in real-time without blocking any non-worm traffic. The major performance cost of WormTerminator is a one-time delay to the start of each outgoing normal connection for worm detection. To reduce the performance overhead, caching is utilized, through which WormTerminator will delay no more than 6% normal outgoing traffic for such detection on average.

TCS Journal 2014 Journal Article

Approximation algorithm for the minimum weight connected k -subgraph cover problem

• Yaping Zhang
• Yishuo Shi
• Zhao Zhang

A subset F of vertices is called a connected k-subgraph cover ( VCC k ) if every connected subgraph on k vertices contains at least one vertex from F. The minimum weight connected k-subgraph cover problem ( MWVCC k ) has its background in the field of security and supervisory control. It is a generalization of the minimum weight vertex cover problem, and is related with the minimum weight k-path cover problem ( MWVCP k ) which requires that every path on k vertices has at least one vertex from F. A k-approximation algorithm can be easily obtained by LP rounding method. Assuming that the girth of the graph is at least k, we reduce the approximation ratio to k − 1, which is tight for our algorithm.

TCS Journal 2013 Journal Article

Optimally restricted edge connected elementary Harary graphs

• Qinghai Liu
• Xiaohui Huang
• Zhao Zhang

An edge subset F of a connected graph G = ( V, E ) is a k -restricted edge cut if G − F is disconnected, and every component of G − F has at least k vertices. The k -restricted edge connectivity of G, denoted by λ k ( G ), is the cardinality of a minimum k -restricted edge cut. By the current studies on λ k, it can be seen that the larger λ k is, the more reliable the graph is. Hence one expects λ k to be as large as possible. A possible upper bound for λ k is ξ k defined as ξ k ( G ) = min { ω ( S ): 0̸ ≠ S ⊂ V ( G ), | S | = k and G [ S ] is connected }, where ω ( S ) is the number of edges with one end in S and the other end in V ( G ) ∖ S, and G [ S ] is the subgraph of G induced by S. A graph G is called λ k -optimal if λ k ( G ) = ξ k ( G ). A natural question is whether there exists a graph G which is λ k -optimal for any k ≤ | V ( G ) | / 2. In this paper, we show that except for two cases, the elementary Harary graph has this property.

TCS Journal 2011 Journal Article

Preface

• Ding-Zhu Du
• Yingfei Dong
• Zhao Zhang

TCS Journal 2009 Journal Article

Algorithms for connected set cover problem and fault-tolerant connected set cover problem

• Zhao Zhang
• Xiaofeng Gao
• Weili Wu

Given a set V of elements, S a family of subsets of V, and G a connected graph on vertex set S, a connected set cover (CSC) is a subfamily R of S such that every element in V is covered by at least one set of R, and the subgraph G [ R ] of G induced by R is connected. If furthermore G [ R ] is k -connected and every element in V is covered by at least m sets in R, then R is a ( k, m ) -CSC. In this paper, we present two approximation algorithms for the minimum CSC problem, and one approximation algorithm for the minimum ( 2, m ) -CSC problem. Performance ratios are analyzed. These are the first approximation algorithms for CSC problems in general graphs with guaranteed performance ratios.

TCS Journal 2009 Journal Article

Construction of strongly connected dominating sets in asymmetric multihop wireless networks

• Deying Li
• Hongwei Du
• Peng-Jun Wan
• Xiaofeng Gao
• Zhao Zhang
• Weili Wu

Consider an asymmetric wireless network represented by a digraph G = ( V, E ). A subset of vertices U is called a strongly connected dominating set (SCDS) if the subgraph induced by U is strongly connected and every vertex not in U has both an in-neighbor in U and an out-neighbor in U. SCDS plays an important role of the virtual backbone in asymmetric wireless networks. Motivated by the construction of a small virtual backbone, we study the problem Minimum SCDS, which seeks a smallest SCDS of a digraph. For any constant 0 < ρ < 1, there is no polynomial-time ρ ln n -approximation for Minimum SCDS unless N P ⊆ D T I M E ( n o ( ln n ) ), where n is the number of nodes. However, none of the polynomial-time heuristics for Minimum SCDS proposed in the literature are logarithmic approximations. In this paper, we present a polynomial-time ( 3 H ( n − 1 ) − 1 ) -approximation algorithm for Minimum SCDS, where H is the harmonic function. The approximation ratio of this algorithm is thus within a factor of 3 from the best possible approximation ratio achievable by any polynomial-time algorithm.

TCS Journal 2009 Journal Article

PTAS for connected vertex cover in unit disk graphs

• Zhao Zhang
• Xiaofeng Gao
• Weili Wu

This paper gives the first polynomial time approximation scheme for the connected vertex cover problem in unit disk graphs.

TCS Journal 2007 Journal Article

Algorithms for long paths in graphs

• Zhao Zhang
• Hao Li

We obtain a polynomial algorithm in O ( n m ) time to find a long path in any graph with n vertices and m edges. The length of the path is bounded by a parameter defined on neighborhood condition of any three independent vertices of the path. An example is given to show that this bound is better than several classic results.