Arrow Research search

Author name cluster

Xiao Zhou

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.

39 papers
2 author rows

Possible papers

39

AAAI Conference 2026 Conference Paper

Lost in Time? A Meta-Learning Framework for Time-Shift-Tolerant Physiological Signal Transformation

  • Qian Hong
  • Cheng Bian
  • Xiao Zhou
  • Xiaoyu Li
  • Yelei Li
  • Zijing Zeng

Translating non-invasive signals such as photoplethysmography (PPG) and ballistocardiography (BCG) into clinically meaningful signals like arterial blood pressure (ABP) is vital for continuous, low-cost healthcare monitoring. However, temporal misalignment in multimodal signal transformation impairs transformation accuracy, especially in capturing critical features like ABP peaks. Conventional synchronization methods often rely on strong similarity assumptions or manual tuning, while existing Learning with Noisy Labels (LNL) approaches are ineffective under time-shifted supervision, either discarding excessive data or failing to correct label shifts. To address this challenge, we propose ShiftSyncNet, a meta-learning-based bi-level optimization framework that automatically mitigates performance degradation due to time misalignment. It comprises a transformation network (TransNet) and a time-shift correction network (SyncNet), where SyncNet learns time offsets between training pairs and applies Fourier phase shifts to align supervision signals. Experiments on one real-world industrial dataset and two public datasets show that ShiftSyncNet outperforms strong baselines by 9.4%, 6.0%, and 12.8%, respectively. The results highlight its effectiveness in correcting time shifts, improving label quality, and enhancing transformation accuracy across diverse misalignment scenarios, pointing toward a unified direction for addressing temporal inconsistencies in multimodal physiological transformation.

PDF Details DOI

AAAI Conference 2026 Conference Paper

MoHoBench: Assessing Honesty of Multimodal Large Language Models via Unanswerable Visual Questions

  • Yanxu Zhu
  • Shitong Duan
  • Xiangxu Zhang
  • Jitao Sang
  • Peng Zhang
  • Tun Lu
  • Xiao Zhou
  • Jing Yao

Recently Multimodal Large Language Models (MLLMs) have achieved considerable advancements in vision-language tasks, yet produce potentially harmful or untrustworthy content. Despite substantial work investigating the trustworthiness of language models, MMLMs' capability to act honestly, especially when faced with visually unanswerable questions, remains largely underexplored. This work presents the first systematic assessment of honesty behaviors across various MLLMs. We ground honesty in models' response behaviors to unanswerable visual questions, define four representative types of such questions, and construct MoHoBench, a large-scale MMLM honest benchmark, consisting of 12k+ visual question samples, whose quality is guaranteed by multi-stage filtering and human verification. Using MoHoBench, we benchmarked the honesty of 28 popular MMLMs and conducted a comprehensive analysis. Our findings show that: (1) most models fail to appropriately refuse to answer when necessary, and (2) MMLMs' honesty is not solely a language modeling issue, but is deeply influenced by visual information, necessitating the development of dedicated methods for multimodal honesty alignment. Therefore, we implemented initial alignment methods using supervised and preference learning to improve honesty behavior, providing a foundation for future work on trustworthy MLLMs.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Spatio-Temporal Hierarchical Causal Models

  • Xintong Li
  • Haoran Zhang
  • Xiao Zhou

The abundance of fine-grained spatio-temporal data, such as traffic sensor networks, offers vast opportunities for scientific discovery. However, inferring causal relationships from such observational data remains challenging, particularly due to unobserved confounders that are specific to units (e.g., geographical locations) yet influence outcomes over time. Most existing methods for spatio-temporal causal inference assume that all confounders are observed, an assumption that is often violated in practice. In this paper, we introduce Spatio-Temporal Hierarchical Causal Models (ST-HCMs), a novel graphical framework that extends hierarchical causal modeling to the spatio-temporal domain. At the core of our approach is the Spatio-Temporal Collapse Theorem, which shows that a complex ST-HCM converges to a simpler flat causal model as the amount of subunit data increases. This theoretical result enables a general procedure for causal identification, allowing ST-HCMs to recover causal effects even in the presence of unobserved, time-invariant unit-level confounders, a scenario where standard non-hierarchical models fail. We validate the effectiveness of our framework on both synthetic and real-world datasets, demonstrating its potential for robust causal inference in complex dynamic systems.

PDF Details DOI

I&C Journal 2025 Journal Article

Changing induced subgraph isomorphisms under extended reconfiguration rules

  • Tatsuhiro Suga
  • Akira Suzuki
  • Yuma Tamura
  • Xiao Zhou

In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other, with the steps dictated by specific reconfiguration rules. Traditionally, most studies on reconfiguration problems have focused on rules that allow changing a single element at a time. In contrast, this paper considers scenarios in which k ≥ 2 elements can be changed simultaneously. We investigate the general reconfiguration problem of isomorphisms. For the Induced Subgraph Isomorphism Reconfiguration problem, we show that the problem remains PSPACE-complete even under stringent constraints on the pattern graph when k is constant. We then give two meta-theorems applicable when k is slightly less than the number of vertices in the pattern graph. In addition, we investigate the complexity of the Independent Set Reconfiguration problem, which is a special case of the Induced Subgraph Isomorphism Reconfiguration problem.

Details DOI

NeurIPS Conference 2025 Conference Paper

Counterfactual Reasoning for Steerable Pluralistic Value Alignment of Large Language Models

  • Hanze Guo
  • Jing Yao
  • Xiao Zhou
  • Xiaoyuan Yi
  • Xing Xie

As large language models (LLMs) become increasingly integrated into applications serving users across diverse cultures, communities, and demographics, it is critical to align LLMs with pluralistic human values beyond average principles (e. g. , HHH). In psychological and social value theories such as Schwartz’s Value Theory, pluralistic values are represented by multiple value dimensions paired with various priorities. However, existing methods encounter two challenges when aligning with such fine-grained value objectives: 1) they often treat multiple values as independent and equally important, ignoring their interdependence and relative priorities (value complexity); 2) they struggle to precisely control nuanced value priorities, especially those underrepresented ones (value steerability). To handle these challenges, we propose COUPLE, a COUnterfactual reasoning framework for PLuralistic valuE alignment. It introduces a structural causal model (SCM) to feature complex interdependency and prioritization among features, as well as the causal relationship between high-level value dimensions and behaviors. Moreover, it applies counterfactual reasoning to generate outputs aligned with any desired value objectives. Benefitting from explicit causal modeling, COUPLE also provides better interpretability. We evaluate COUPLE on two datasets with different value systems and demonstrate that COUPLE advances other baselines across diverse types of value objectives. Our code is available at https: //github. com/microsoft/COUPLE.

PDF Details

AIJ Journal 2025 Journal Article

CureGraph: Contrastive multi-modal graph representation learning for urban living circle health profiling and prediction

  • Jinlin Li
  • Xiao Zhou

The early detection and prediction of health status decline among the elderly at the neighborhood level are of great significance for urban planning and public health policymaking. While existing studies affirm the connection between living environments and health outcomes, most rely on single data modalities or simplistic feature concatenation of multi-modal information, limiting their ability to comprehensively profile the health-oriented urban environments. To fill this gap, we propose CureGraph, a contrastive multi-modal representation learning framework for urban health prediction that employs graph-based techniques to infer the prevalence of common chronic diseases among the elderly within the urban living circles of each neighborhood. CureGraph leverages rich multi-modal information, including photos and textual reviews of residential areas and their surrounding points of interest, to generate urban neighborhood embeddings. By integrating pre-trained visual and textual encoders with graph modeling techniques, CureGraph captures cross-modal spatial dependencies, offering a comprehensive understanding of urban environments tailored to elderly health considerations. Extensive experiments on real-world datasets demonstrate that CureGraph improves the best baseline by $28\%$ on average in terms of $R^2$ across elderly disease risk prediction tasks. Moreover, the model enables the identification of stage-wise chronic disease progression and supports comparative public health analysis across neighborhoods, offering actionable insights for sustainable urban development and enhanced quality of life. The code is publicly available at https: //github. com/jinlin2021/CureGraph.

Details DOI

IJCAI Conference 2025 Conference Paper

CureGraph: Contrastive Multi-Modal Graph Representation Learning for Urban Living Circle Health Profiling and Prediction (Abstract Reprint)

  • Jinlin Li
  • Xiao Zhou

The early detection and prediction of health status decline among the elderly at the neighborhood level are of great significance for urban planning and public health policymaking. While existing studies affirm the connection between living environments and health outcomes, most rely on single data modalities or simplistic feature concatenation of multi-modal information, limiting their ability to comprehensively profile the health-oriented urban environments. To fill this gap, we propose CureGraph, a contrastive multi-modal representation learning framework for urban health prediction that employs graph-based techniques to infer the prevalence of common chronic diseases among the elderly within the urban living circles of each neighborhood. CureGraph leverages rich multi-modal information, including photos and textual reviews of residential areas and their surrounding points of interest, to generate urban neighborhood embeddings. By integrating pre-trained visual and textual encoders with graph modeling techniques, CureGraph captures cross-modal spatial dependencies, offering a comprehensive understanding of urban environments tailored to elderly health considerations. Extensive experiments on real-world datasets demonstrate that CureGraph improves the best baseline by 28% on average in terms of across elderly disease risk prediction tasks. Moreover, the model enables the identification of stage-wise chronic disease progression and supports comparative public health analysis across neighborhoods, offering actionable insights for sustainable urban development and enhanced quality of life. The code is publicly available at https: //github. com/jinlin2021/CureGraph.

PDF Details DOI

YNIMG Journal 2025 Journal Article

Effects of aerobic running vs. reading rest after fear extinction on recall: Decreased prefrontal cortex activity to distinguish threat and safety cues

  • Xiao Zhou
  • Juan Kou
  • E Mei
  • Yi Lei

Recall of extinction memory, pivotal in the treatment of anxiety-related psychiatric disorders, involves the retrieval of learned safety associations to reduce conditioned fear responses. This study examines the differential impacts of two non-pharmacological interventions, aerobic running and reading rest, both common in daily life, on fear extinction recall by measuring neural activity and self-reported risk expectation levels. Participants (n = 64) were randomly assigned to either a running group or a reading group, and underwent a three-day differential fear conditioning task. Neural activity was assessed using functional magnetic resonance imaging (fMRI), focusing particularly on the prefrontal cortex involved in fear regulation and memory processing. Findings indicate that participants in the running group showed significantly reduced dorsomedial prefrontal cortex (dmPFC) activation during fear recall while discriminating threat and safe cues, along with greater reductions in differential expectation scores (CS+ vs. CS-) from acquisition to recall phase compared to the reading rest group. These results suggest that aerobic running may facilitate fear extinction more effectively than reading rest by modulating dmPFC function. This study explores the neural mechanisms that underpin the effects of exercise on fear memory and proposes a potential method for enhancing exposure-based therapy, potentially through targeted physical activity interventions.

Details DOI

NeurIPS Conference 2025 Conference Paper

Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgery

  • Shiji Zhou
  • Tianbai Yu
  • Zhi Zhang
  • Heng Chang
  • Xiao Zhou
  • Dong Wu
  • Han Zhao

Machine unlearning (MU) aims to efficiently remove sensitive or harmful memory from a pre-trained model. The key challenge is to balance the potential tradeoff between unlearning efficacy and utility preservation, which involves forgetting undesirable information as defined while maintaining the model's original performance. One potential way to tackle this problem is to use multi-objective optimization to jointly optimize both the unlearning and utility preservation objectives. However, existing multi-objective methods only guarantee finding a Pareto-optimal solution without fine-grained control, which causes under-optimization of the unlearning objective. To this end, we first model MU as a constrained optimization problem, that is, optimizing the unlearning objective under the constraint of a bounded increase for utility loss. We then show that solving this optimization problem is equivalent to unilateral gradient surgery on the unlearning objective. To resolve the additional computational cost brought by gradient surgery, we propose an implicit gradient surgery method, which approximates the solution to the aforementioned constrained optimization problem via only one backpropagation, thereby achieving efficient utility-preserving MU. Theoretically, we provide a tight convergence analysis of the algorithm. Empirically, our extensive experiments show that the proposed algorithm achieves better tradeoff results than existing baselines. Codes are available at https: //github. com/anseryuer/EUPMU-Efficient-Utility-Preserving-Machine-Unlearning.

PDF Details

AAAI Conference 2025 Conference Paper

FAP-CD: Fairness-Driven Age-Friendly Community Planning via Conditional Diffusion Generation

  • Jinlin Li
  • Xintong Li
  • Xiao Zhou

As global populations age rapidly, incorporating age-specific considerations into urban planning has become essential to addressing the urgent demand for age-friendly built environments and ensuring sustainable urban development. However, current practices often overlook these considerations, resulting in inadequate and unevenly distributed elderly services in cities. There is a pressing need for equitable and optimized urban renewal strategies to support effective age-friendly planning. To address this challenge, we propose a novel framework, Fairness-driven Age-friendly community Planning via Conditional Diffusion generation (FAP-CD). FAP-CD leverages a conditioned graph denoising diffusion probabilistic model to learn the joint probability distribution of aging facilities and their spatial relationships at a fine-grained regional level. Our framework generates optimized facility distributions by iteratively refining noisy graphs, conditioned on the needs of the elderly during the diffusion process. Key innovations include a demand-fairness pre-training module that integrates community demand features and facility characteristics using an attention mechanism and min-max optimization, ensuring equitable service distribution across regions. Additionally, a discrete graph structure captures walkable accessibility within regional road networks, guiding model sampling. To enhance information integration, we design a graph denoising network with an attribute augmentation module and a hybrid graph message aggregation module, combining local and global node and edge information. Empirical results across multiple metrics demonstrate the effectiveness of FAP-CD in balancing age-friendly needs with regional equity, achieving an average improvement of 41% over competitive baseline models.

PDF Details DOI

AAAI Conference 2025 Conference Paper

MotifGPL: Motif-Enhanced Graph Prototype Learning for Deciphering Urban Social Segregation

  • Tengfei He
  • Xiao Zhou

Social segregation in cities, spanning racial, residential, and income dimensions, is becoming increasingly diverse and severe. As urban spaces and social dynamics grow more complex, residents experience varying levels of segregation, which, if left unaddressed, could exacerbate crime rates, fuel social tensions, and lead to other societal challenges. Effectively addressing these issues requires a comprehensive analysis of the underlying structures of urban spaces and resident interactions. While previous studies have primarily focused on surface-level indicators of segregation, they often fail to explore the complexity of urban structure and mobility dynamics, leaving gaps in understanding modern segregation patterns. To fill this gap, we propose the Motif-Enhanced Graph Prototype Learning (MotifGPL) framework, offering a novel approach to studying urban segregation. The framework consists of three key modules: prototype-based graph structure extraction, motif distribution discovery, and urban graph reconstruction. Specifically, we use prototype-based learning to extract key urban graph prototypes from both spatial and origin-destination graphs, incorporating attributes such as points of interest, street images, and flow indices. The motif distribution discovery module enhances interpretability by matching each prototype to similar motifs, which represent simplified graph structures that reflect local patterns. These motifs are then used to guide the reconstruction of urban graphs, enabling a more detailed exploration of spatial structures and mobility patterns. By identifying critical motifs influencing urban segregation, MotifGPL offers insights to guide the design of urban environments that can help reduce segregation. Experimental results demonstrate that MotifGPL effectively uncovers these key motifs and provides actionable insights for mitigating segregation.

PDF Details DOI

EAAI Journal 2025 Journal Article

Multi-modality complementary learning network with cross-modality interaction and adaptive fusion for face forgery detection

  • Chunyin Shi
  • Chengyou Wang
  • Xiao Zhou
  • Zhiliang Qin

With the advancement of face forgery technology, many forged faces threaten information security. Although existing face forgery detection methods obtain better detection performance on intra-dataset evaluation, the generalization of cross-dataset detection and the robustness against image post-processing operations still need to be improved. To address these issues, we propose a multi-modality complementary learning network with cross-modality interaction and adaptive fusion for face forgery detection. Specifically, a two-branch architecture is designed to extract spatial and frequency features. To realize the interaction and communication of spatial and frequency information, the cross-modality interaction module is designed to explore the inter-modality correlation by applying across self-attention. Subsequently, a multi-scale feature enhancement module is introduced in the spatial branch to enhance the texture and semantic information of spatial features, improving the robustness of tackling image post-processing operations. In addition, to exploit the complementary relationship between the spatial and frequency features, an adaptive fusion module is designed to establish forged feature dependencies by leveraging spatial self-attention, while learning discriminative feature representations by fusing spatial and frequency features in an adaptive weighted manner. Extensive experimental results on four public datasets demonstrate that the proposed method outperforms other state-of-the-art methods for intra-dataset, cross-dataset, and perturbed dataset evaluations.

Details DOI

TCS Journal 2025 Journal Article

On the complexity of list H -packing for sparse graph classes

  • Tatsuya Gima
  • Tesshu Hanaka
  • Yasuaki Kobayashi
  • Yota Otachi
  • Tomohito Shirai
  • Akira Suzuki
  • Yuma Tamura
  • Xiao Zhou

The problem of packing as many subgraphs isomorphic to some H ∈ H as possible into a graph, where H is a collection of graphs, has been well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for H that contains at least three vertices and at least three edges, respectively. In this paper, we consider “list variants” of these problems: Given a graph G, an integer k, and a collection L H of subgraphs of G isomorphic to some H ∈ H, the goal is to compute k subgraphs in L H that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.

Details DOI

TCS Journal 2025 Journal Article

Parameterized complexity of weighted target set selection

  • Takahiro Suzuki
  • Kei Kimura
  • Akira Suzuki
  • Yuma Tamura
  • Xiao Zhou

Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset A 0 of G is a target set if eventually all vertices in G are activated by initially activating vertices of A 0. The Target Set Selection problem (TSS) involves finding a smallest target set of G. This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem (WTSS), from the perspective of parameterized complexity. Let k be the solution size and let ℓ be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by k + ℓ, and W[2]-hard for cographs when parameterized by k. We next prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k. On the other hand, we show that WTSS can be solved in O ( n log ⁡ n ) time for complete graphs with n vertices. Additionally, we design FPT algorithms for WTSS when parameterized by nd + ℓ, tw + ℓ, ce, and vc, where nd, tw, ce, and vc are the neighborhood diversity, the treewidth, the cluster editing number, and the vertex cover number of the input graph, respectively.

Details DOI

NeurIPS Conference 2025 Conference Paper

Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens

  • Xixian Yong
  • Xiao Zhou
  • Yingying Zhang
  • Jinlin Li
  • Yefeng Zheng
  • Xian Wu

The recent rise of Large Reasoning Models (LRMs) has significantly improved multi-step reasoning performance, but often at the cost of generating excessively long reasoning chains. This paper revisits the efficiency of such reasoning processes through an information-theoretic lens, revealing a fundamental trade-off between reasoning length and semantic efficiency. We propose two metrics—InfoBias and InfoGain—to quantify divergence from ideal reasoning paths and stepwise information contribution, respectively. Empirical analyses show that longer reasoning chains tend to exhibit higher information bias and diminishing information gain, especially for incorrect answers. Motivated by these findings, we introduce an entropy-based Adaptive Think strategy that dynamically halts reasoning once confidence is sufficiently high, improving efficiency while maintaining competitive accuracy. Compared to the Vanilla Think approach (default mode), our strategy yields a 1. 10% improvement in average accuracy and a 50. 80% reduction in token usage on QwQ-32B across six benchmark tasks spanning diverse reasoning types and difficulty levels, demonstrating superior efficiency and reasoning performance. These results underscore the promise of entropy-based methods for enhancing both accuracy and cost-effiiciency in large language model deployment.

PDF Details

AAAI Conference 2025 Conference Paper

Universal Features Guided Zero-Shot Category-Level Object Pose Estimation

  • Wentian Qu
  • Chenyu Meng
  • Heng Li
  • Jian Cheng
  • Cuixia Ma
  • Hongan Wang
  • Xiao Zhou
  • Xiaoming Deng

Object pose estimation, crucial in computer vision and robotics applications, faces challenges with the diversity of unseen categories. We propose a zero-shot method to achieve category-level 6-DOF object pose estimation, which exploits both 2D and 3D universal features of input RGB-D image to establish semantic similarity-based correspondences and can be extended to unseen categories without additional model fine-tuning. Our method begins with combining efficient 2D universal features to find sparse correspondences between intra-category objects and gets initial coarse pose. To handle the correspondence degradation of 2D universal features if the pose deviates much from the target pose, we use an iterative strategy to optimize the pose. Subsequently, to resolve pose ambiguities due to shape differences between intra-category objects, the coarse pose is refined by optimizing with dense alignment constraint of 3D universal features. Our method outperforms previous methods on the REAL275 and Wild6D benchmarks for unseen categories.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Unlearning Concepts in Diffusion Model via Concept Domain Correction and Concept Preserving Gradient

  • Yongliang Wu
  • Shiji Zhou
  • Mingzhuo Yang
  • Lianzhe Wang
  • Heng Chang
  • Wenbo Zhu
  • Xinting Hu
  • Xiao Zhou

Text-to-image diffusion models have achieved remarkable success in generating photorealistic images. However, the inclusion of sensitive information during pre-training poses significant risks. Machine Unlearning (MU) offers a promising solution to eliminate sensitive concepts from these models. Despite its potential, existing MU methods face two main challenges: 1) limited generalization, where concept erasure is effective only within the unlearned set, failing to prevent sensitive concept generation from out-of-set prompts; and 2) utility degradation, where removing target concepts significantly impacts the model's overall performance. To address these issues, we propose a novel concept domain correction framework named \textbf{DoCo} (\textbf{Do}main \textbf{Co}rrection). By aligning the output domains of sensitive and anchor concepts through adversarial training, our approach ensures comprehensive unlearning of target concepts. Additionally, we introduce a concept-preserving gradient surgery technique that mitigates conflicting gradient components, thereby preserving the model's utility while unlearning specific concepts. Extensive experiments across various instances, styles, and offensive concepts demonstrate the effectiveness of our method in unlearning targeted concepts with minimal impact on related concepts, outperforming previous approaches even for out-of-distribution prompts.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Ada-Retrieval: An Adaptive Multi-Round Retrieval Paradigm for Sequential Recommendations

  • Lei Li
  • Jianxun Lian
  • Xiao Zhou
  • Xing Xie

Retrieval models aim at selecting a small set of item candidates which match the preference of a given user. They play a vital role in large-scale recommender systems since subsequent models such as rankers highly depend on the quality of item candidates. However, most existing retrieval models employ a single-round inference paradigm, which may not adequately capture the dynamic nature of user preferences and stuck in one area in the item space. In this paper, we propose Ada-Retrieval, an adaptive multi-round retrieval paradigm for recommender systems that iteratively refines user representations to better capture potential candidates in the full item space. Ada-Retrieval comprises two key modules: the item representation adapter and the user representation adapter, designed to inject context information into items' and users' representations. The framework maintains a model-agnostic design, allowing seamless integration with various backbone models such as RNNs or Transformers. We perform experiments on three widely used public datasets, incorporating five powerful sequential recommenders as backbone models. Our results demonstrate that Ada-Retrieval significantly enhances the performance of various base models, with consistent improvements observed across different datasets. Our code and data are publicly available at: https://github.com/ll0ruc/Ada-Retrieval.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Causally Aware Generative Adversarial Networks for Light Pollution Control

  • Yuyao Zhang
  • Ke Guo
  • Xiao Zhou

Artificial light plays an integral role in modern cities, significantly enhancing human productivity and the efficiency of civilization. However, excessive illumination can lead to light pollution, posing non-negligible threats to economic burdens, ecosystems, and human health. Despite its critical importance, the exploration of its causes remains relatively limited within the field of artificial intelligence, leaving an incomplete understanding of the factors contributing to light pollution and sustainable illumination planning distant. To address this gap, we introduce a novel framework named Causally Aware Generative Adversarial Networks (CAGAN). This innovative approach aims to uncover the fundamental drivers of light pollution within cities and offer intelligent solutions for optimal illumination resource allocation in the context of sustainable urban development. We commence by examining light pollution across 33,593 residential areas in seven global metropolises. Our findings reveal substantial influences on light pollution levels from various building types, notably grasslands, commercial centers and residential buildings as significant contributors. These discovered causal relationships are seamlessly integrated into the generative modeling framework, guiding the process of generating light pollution maps for diverse residential areas. Extensive experiments showcase CAGAN’s potential to inform and guide the implementation of effective strategies to mitigate light pollution. Our code and data are publicly available at https://github.com/zhangyuuao/Light_Pollution_CAGAN.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

CGAP: Urban Region Representation Learning with Coarsened Graph Attention Pooling

  • Zhuo Xu
  • Xiao Zhou

The explosion of massive urban data recently has provided us with a valuable opportunity to gain deeper insights into urban regions and the daily lives of residents. Urban region representation learning emerges as a crucial realm for fulfilling this task. Among deep learning approaches, graph neural networks (GNNs) have shown promise, given that city elements can be naturally represented as nodes with various connections between them as edges. However, many existing GNN approaches encounter challenges such as over-smoothing and limitations in capturing information from nodes in other regions, resulting in the loss of crucial urban information and a decline in region representation performance. To address these challenges, we leverage urban graph structure information and introduce a hierarchical graph pooling process called Coarsened Graph Attention Pooling (CGAP). CGAP features local attention units to create coarsened intermediate graphs and global features. Additionally, by incorporating urban region graphs and global features into a global attention layer, we harness relational information to enhance representation effectiveness. Furthermore, CGAP integrates region attributes such as Points of Interest (POIs) and inter-regional contexts like human mobility, enabling the exploitation of multi-modal urban data for more comprehensive representation learning. Experiments on three downstream tasks related to the UN Sustainable Development Goals validate the effectiveness of region representations learned by our approach. Experimental results and analyses demonstrate that CGAP excels in various socioeconomic prediction tasks compared to competitive baselines.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

MuseCL: Predicting Urban Socioeconomic Indicators via Multi-Semantic Contrastive Learning

  • Xixian Yong
  • Xiao Zhou

Predicting socioeconomic indicators within urban regions is crucial for fostering inclusivity, resilience, and sustainability in cities and human settlements. While pioneering studies have attempted to leverage multi-modal data for socioeconomic prediction, jointly exploring their underlying semantics remains a significant challenge. To address the gap, this paper introduces a Multi-Semantic Contrastive Learning (MuseCL) framework for fine-grained urban region profiling and socioeconomic prediction. Within this framework, we initiate the process by constructing contrastive sample pairs for street view and remote sensing images, capitalizing on the similarities in human mobility and Point of Interest (POI) distribution to derive semantic features from the visual modality. Additionally, we extract semantic insights from POI texts embedded within these regions, employing a pre-trained text encoder. To merge the acquired visual and textual features, we devise an innovative cross-modality-based attentional fusion module, which leverages a contrastive mechanism for integration. Experimental results across multiple cities and indicators consistently highlight the superiority of MuseCL, demonstrating an average improvement of 10% in R2 compared to various competitive baseline models. The code of this work is publicly available at https: //github. com/XixianYong/MuseCL.

PDF Details DOI

IROS Conference 2024 Conference Paper

Reward-Driven Automated Curriculum Learning for Interaction-Aware Self-Driving at Unsignalized Intersections

  • Zengqi Peng
  • Xiao Zhou
  • Lei Zheng 0007
  • Yubin Wang
  • Jun Ma 0008

In this work, we present a reward-driven automated curriculum reinforcement learning approach for interaction-aware self-driving at unsignalized intersections, taking into account the uncertainties associated with surrounding vehicles (SVs). These uncertainties encompass the uncertainty of SVs’ driving intention and also the quantity of SVs. To deal with this problem, the curriculum set is specifically designed to accommodate a progressively increasing number of SVs. By implementing an automated curriculum selection mechanism, the importance weights are rationally allocated across various curricula, thereby facilitating improved sample efficiency and training outcomes. Furthermore, the reward function is meticulously designed to guide the agent towards effective policy exploration. Thus the proposed framework could proactively address the above uncertainties at unsignalized intersections by employing the automated curriculum learning technique that progressively increases task difficulty, and this ensures safe self-driving through effective interaction with SVs. Comparative experiments are conducted in Highway_Env, and the results indicate that our approach achieves the highest task success rate, attains strong robustness to initialization parameters of the curriculum selection module, and exhibits superior adaptability to diverse situational configurations at unsignalized intersections. Furthermore, the effectiveness of the proposed method is validated using the high-fidelity CARLA simulator.

Details

AAAI Conference 2024 Conference Paper

Tail-STEAK: Improve Friend Recommendation for Tail Users via Self-Training Enhanced Knowledge Distillation

  • Yijun Ma
  • Chaozhuo Li
  • Xiao Zhou

Graph neural networks (GNNs) are commonly employed in collaborative friend recommendation systems. Nevertheless, recent studies reveal a notable performance gap, particularly for users with limited connections, commonly known as tail users, in contrast to their counterparts with abundant connections (head users). Uniformly treating head and tail users poses two challenges for tail user preference learning: (C1) Label Sparsity, as tail users typically possess limited labels; and (C2) Neighborhood Sparsity, where tail users exhibit sparse observable friendships, leading to distinct preference distributions and performance degradation compared to head users. In response to these challenges, we introduce Tail-STEAK, an innovative framework that combines self-training with enhanced knowledge distillation for tail user representation learning. To address(C1), we present Tail-STEAK-base, a two-stage self-training framework. In the first stage, only head users and their accurate connections are utilized for training, while pseudo links are generated for tail users in the second stage. To tackle (C2), we propose two data augmentation-based self-knowledge distillation pretext tasks. These tasks are seamlessly integrated into different stages of Tail-STEAK-base, culminating in the comprehensive Tail-STEAK framework. Extensive experiments, conducted on state-of-the-art GNN-based friend recommendation models, substantiate the efficacy of Tail-STEAK in significantly improving tail user performance. Our code and data are publicly available at https://github.com/antman9914/Tail-STEAK.

PDF Details DOI

ICLR Conference 2023 Conference Paper

A Holistic View of Label Noise Transition Matrix in Deep Learning and Beyond

  • Yong Lin
  • Renjie Pi
  • Weizhong Zhang
  • Xiaobo Xia
  • Jiahui Gao
  • Xiao Zhou
  • Tongliang Liu
  • Bo Han 0003

In this paper, we explore learning statistically consistent classifiers under label noise by estimating the noise transition matrix T. We first provide a holistic view of existing T-estimation methods including those with or without anchor point assumptions. We unified them into the Minimum Geometric Envelope Operator (MGEO) framework, which tries to find the smallest T (in terms of a certain metric) that elicits a convex hull to enclose the posteriors of all the training data. Although MGEO methods show appealing theoretical properties and empirical results, we find them prone to failing when the noisy posterior estimation is imperfect, which is inevitable in practice. Specifically, we show that MGEO methods are in-consistent even with infinite samples if the noisy posterior is not estimated accurately. In view of this, we make the first effort to address this issue by proposing a novel T-estimation framework via the lens of bilevel optimization, and term it RObust Bilevel OpTimzation (ROBOT). ROBOT paves a new road beyond MGEO framework, which enjoys strong theoretical properties: identifibility, consistency and finite-sample generalization guarantees. Notably, ROBOT neither requires the perfect posterior estimation nor assumes the existence of anchor points. We further theoretically demonstrate that ROBOT is more robust in the case where MGEO methods fail. Experimentally, our framework also shows superior performance across multiple benchmarks.

Details

TMLR Journal 2023 Journal Article

Black-Box Prompt Learning for Pre-trained Language Models

  • Shizhe Diao
  • Zhichao Huang
  • Ruijia Xu
  • Xuechun Li
  • LIN Yong
  • Xiao Zhou
  • Tong Zhang

The increasing scale of general-purpose Pre-trained Language Models (\textbf{PLMs}) necessitates the study of more efficient adaptation across different downstream tasks. In this paper, we establish a Black-box Discrete Prompt Learning (\textbf{BDPL}) to resonate with pragmatic interactions between the cloud infrastructure and edge devices. Particularly, instead of fine-tuning the model in the cloud, we adapt PLMs by prompt learning, which efficiently optimizes only a few parameters of the discrete prompts. Moreover, we consider the scenario that we do not have access to the parameters and gradients of the pre-trained models, except for its outputs given inputs. This black-box setting secures the cloud infrastructure from potential attack and misuse to cause a single-point failure, which is preferable to the white-box counterpart by current infrastructures. Under this black-box constraint, we apply a variance-reduced policy gradient algorithm to estimate the gradients of parameters in the categorical distribution of each discrete prompt. In light of our method, the user devices can efficiently tune their tasks by querying the PLMs bounded by a range of API calls. Our experiments on RoBERTa and GPT-3 demonstrate that the proposed algorithm achieves significant improvement on eight benchmarks in a cloud-device collaboration manner. Finally, we conduct in-depth case studies to comprehensively analyze our method in terms of various data sizes, prompt lengths, training budgets, optimization objectives, prompt transferability, and explanations of the learned prompts.

PDF Details

ICML Conference 2022 Conference Paper

Model Agnostic Sample Reweighting for Out-of-Distribution Learning

  • Xiao Zhou
  • Yong Lin
  • Renjie Pi
  • Weizhong Zhang
  • Renzhe Xu
  • Peng Cui 0001
  • Tong Zhang 0001

Distributionally robust optimization (DRO) and invariant risk minimization (IRM) are two popular methods proposed to improve out-of-distribution (OOD) generalization performance of machine learning models. While effective for small models, it has been observed that these methods can be vulnerable to overfitting with large overparameterized models. This work proposes a principled method, Model Agnostic samPLe rEweighting (MAPLE), to effectively address OOD problem, especially in overparameterized scenarios. Our key idea is to find an effective reweighting of the training samples so that the standard empirical risk minimization training of a large model on the weighted training data leads to superior OOD generalization performance. The overfitting issue is addressed by considering a bilevel formulation to search for the sample reweighting, in which the generalization complexity depends on the search space of sample weights instead of the model size. We present theoretical analysis in linear case to prove the insensitivity of MAPLE to model size, and empirically verify its superiority in surpassing state-of-the-art methods by a large margin.

Details

ICML Conference 2022 Conference Paper

Probabilistic Bilevel Coreset Selection

  • Xiao Zhou
  • Renjie Pi
  • Weizhong Zhang
  • Yong Lin
  • Zonghao Chen
  • Tong Zhang 0001

The goal of coreset selection in supervised learning is to produce a weighted subset of data, so that training only on the subset achieves similar performance as training on the entire dataset. Existing methods achieved promising results in resource-constrained scenarios such as continual learning and streaming. However, most of the existing algorithms are limited to traditional machine learning models. A few algorithms that can handle large models adopt greedy search approaches due to the difficulty in solving the discrete subset selection problem, which is computationally costly when coreset becomes larger and often produces suboptimal results. In this work, for the first time we propose a continuous probabilistic bilevel formulation of coreset selection by learning a probablistic weight for each training sample. The overall objective is posed as a bilevel optimization problem, where 1) the inner loop samples coresets and train the model to convergence and 2) the outer loop updates the sample probability progressively according to the model’s performance. Importantly, we develop an efficient solver to the bilevel optimization problem via unbiased policy gradient without trouble of implicit differentiation. We theoretically prove the convergence of this training procedure and demonstrate the superiority of our algorithm against various coreset selection methods in various tasks, especially in more challenging label-noise and class-imbalance scenarios.

Details

IROS Conference 2022 Conference Paper

PUTN: A Plane-fitting based Uneven Terrain Navigation Framework

  • Zhuozhu Jian
  • Zihong Lu
  • Xiao Zhou
  • Bin Lan
  • Anxing Xiao
  • Xueqian Wang 0001
  • Bin Liang 0001

Autonomous navigation of ground robots has been widely used in indoor structured 2D environments, but there are still many challenges in outdoor 3D unstructured environments, especially in rough, uneven terrains. This paper proposed a plane-fitting based uneven terrain navigation framework (PUTN) to solve this problem. The implementation of PUTN is divided into three steps. First, based on Rapidly-exploring Random Trees (RRT), an improved sample-based algorithm called Plane Fitting RRT*(PF- RRT*) is proposed to obtain a sparse trajectory. Each sampling point corresponds to a custom traversability index and a fitted plane on the point cloud. These planes are connected in series to form a traversable “strip”. Second, Gaussian Process Regression is used to generate traversability of the dense trajectory interpolated from the sparse trajectory, and the sampling tree is used as the training set. Finally, local planning is performed using nonlinear model predictive control (NMPC). By adding the traversability index and uncertainty to the cost function, and adding obstacles generated by the real-time point cloud to the constraint function, a safe motion planning algorithm with smooth speed and strong robustness is available. Experiments in real scenarios are conducted to verify the effectiveness of the method. The source code is released for the reference of the community 1 1 Source code: https://github.com/jianzhuozhuTHU/putn. .

Details

ICML Conference 2022 Conference Paper

Sparse Invariant Risk Minimization

  • Xiao Zhou
  • Yong Lin
  • Weizhong Zhang
  • Tong Zhang 0001

Invariant Risk Minimization (IRM) is an emerging invariant feature extracting technique to help generalization with distributional shift. However, we find that there exists a basic and intractable contradiction between the model trainability and generalization ability in IRM. On one hand, recent studies on deep learning theory indicate the importance of large-sized or even overparameterized neural networks to make the model easy to train. On the other hand, unlike empirical risk minimization that can be benefited from overparameterization, our empirical and theoretical analyses show that the generalization ability of IRM is much easier to be demolished by overfitting caused by overparameterization. In this paper, we propose a simple yet effective paradigm named Sparse Invariant Risk Minimization (SparseIRM) to address this contradiction. Our key idea is to employ a global sparsity constraint as a defense to prevent spurious features from leaking in during the whole IRM process. Compared with sparisfy-after-training prototype by prior work which can discard invariant features, the global sparsity constraint limits the budget for feature selection and enforces SparseIRM to select the invariant features. We illustrate the benefit of SparseIRM through a theoretical analysis on a simple linear case. Empirically we demonstrate the power of SparseIRM through various datasets and models and surpass state-of-the-art methods with a gap up to 29%.

Details

TCS Journal 2021 Journal Article

Approximability of the independent feedback vertex set problem for bipartite graphs

  • Yuma Tamura
  • Takehiro Ito
  • Xiao Zhou

Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G, if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed ε > 0, unless P = NP, there exists no polynomial-time n 1 − ε -approximation algorithm even for bipartite planar graphs. We then give an α ( Δ − 1 ) / 2 -approximation algorithm for bipartite graphs G of maximum degree Δ, which runs in t ( α, G ) + O ( Δ n ) time, under the assumption that there is an α-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t ( α, G ) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three.

Details DOI

NeurIPS Conference 2021 Conference Paper

Efficient Neural Network Training via Forward and Backward Propagation Sparsification

  • Xiao Zhou
  • Weizhong Zhang
  • Zonghao Chen
  • Shizhe Diao
  • Tong Zhang

Sparse training is a natural idea to accelerate the training speed of deep neural networks and save the memory usage, especially since large modern neural networks are significantly over-parameterized. However, most of the existing methods cannot achieve this goal in practice because the chain rule based gradient (w. r. t. structure parameters) estimators adopted by previous methods require dense computation at least in the backward propagation step. This paper solves this problem by proposing an efficient sparse training method with completely sparse forward and backward passes. We first formulate the training process as a continuous minimization problem under global sparsity constraint. We then separate the optimization process into two steps, corresponding to weight update and structure parameter update. For the former step, we use the conventional chain rule, which can be sparse via exploiting the sparse structure. For the latter step, instead of using the chain rule based gradient estimators as in existing methods, we propose a variance reduced policy gradient estimator, which only requires two forward passes without backward propagation, thus achieving completely sparse training. We prove that the variance of our gradient estimator is bounded. Extensive experimental results on real-world datasets demonstrate that compared to previous methods, our algorithm is much more effective in accelerating the training process, up to an order of magnitude faster.

PDF Details

IJCAI Conference 2019 Conference Paper

Collaborative Metric Learning with Memory Network for Multi-Relational Recommender Systems

  • Xiao Zhou
  • Danyang Liu
  • Jianxun Lian
  • Xing Xie

The success of recommender systems in modern online platforms is inseparable from the accurate capture of users' personal tastes. In everyday life, large amounts of user feedback data are created along with user-item online interactions in a variety of ways, such as browsing, purchasing, and sharing. These multiple types of user feedback provide us with tremendous opportunities to detect individuals' fine-grained preferences. Different from most existing recommender systems that rely on a single type of feedback, we advocate incorporating multiple types of user-item interactions for better recommendations. Based on the observation that the underlying spectrum of user preferences is reflected in various types of interactions with items and can be uncovered by latent relational learning in metric space, we propose a unified neural learning framework, named Multi-Relational Memory Network (MRMN). It can not only model fine-grained user-item relations but also enable us to discriminate between feedback types in terms of the strength and diversity of user preferences. Extensive experiments show that the proposed MRMN model outperforms competitive state-of-the-art algorithms in a wide range of scenarios, including e-commerce, local services, and job recommendations.

PDF Details

TCS Journal 2018 Journal Article

Parameterized complexity of the list coloring reconfiguration problem with graph parameters

  • Tatsuhiko Hatanaka
  • Takehiro Ito
  • Xiao Zhou

Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACE-complete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries of these two results, we show that the problem for cographs and the shortest variant for split graphs are fixed-parameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is W [ 1 ] -hard when parameterized only by the size of a minimum vertex cover of an input graph.

Details DOI

IJCAI Conference 2018 Conference Paper

Predicting the Spatio-Temporal Evolution of Chronic Diseases in Population with Human Mobility Data

  • Yingzi Wang
  • Xiao Zhou
  • Anastasios Noulas
  • Cecilia Mascolo
  • Xing Xie
  • Enhong Chen

Chronic diseases like cancer and diabetes are major threats to human life. Understanding the distribution and progression of chronic diseases of a population is important in assisting the allocation of medical resources as well as the design of policies in preemptive healthcare. Traditional methods to obtain large scale indicators on population health, e. g. , surveys and statistical analysis, can be costly and time-consuming and often lead to a coarse spatio-temporal picture. In this paper, we leverage a dataset describing the human mobility patterns of citizens in a large metropolitan area. By viewing local human lifestyles we predict the evolution rate of several chronic diseases at the level of a city neighborhood. We apply the combination of a collaborative topic modeling (CTM) and a Gaussian mixture method (GMM) to tackle the data sparsity challenge and achieve robust predictions on health conditions simultaneously. Our method enables the analysis and prediction of disease rate evolution at fine spatio-temporal scales and demonstrates the potential of incorporating datasets from mobile web sources to improve population health monitoring. Evaluations using real-world check-in and chronic disease morbidity datasets in the city of London show that the proposed CTM+GMM model outperforms various baseline methods.

PDF Details

TCS Journal 2014 Journal Article

Bandwidth consecutive multicolorings of graphs

  • Kazuhide Nishikawa
  • Takao Nishizeki
  • Xiao Zhou

Let G be a simple graph in which each vertex v has a positive integer weight b(v) and each edge (v, w) has a nonnegative integer weight b(v, w). A bandwidth consecutive multicoloring of G assigns each vertex v a specified number b(v) of consecutive positive integers so that, for each edge (v, w), all integers assigned to vertex v differ from all integers assigned to vertex w by more than b(v, w). The maximum integer assigned to a vertex is called the span of the coloring. In the paper, we first investigate fundamental properties of such a coloring. We then obtain a pseudo polynomial-time exact algorithm and a fully polynomial-time approximation scheme for the problem of finding such a coloring of a given series-parallel graph with the minimum span. We finally extend the results to the case where a given graph G is a partial k-tree, that is, G has a bounded tree-width.

Details DOI

TCS Journal 2014 Journal Article

Generalized rainbow connectivity of graphs

  • Kei Uchizawa
  • Takanori Aoki
  • Takehiro Ito
  • Xiao Zhou

Let C = { c 1, c 2, …, c k } be a set of k colors, and let ℓ → = ( ℓ 1, ℓ 2, …, ℓ k ) be a k-tuple of nonnegative integers ℓ 1, ℓ 2, …, ℓ k. For a graph G = ( V, E ), let f: E → C be an edge-coloring of G in which two adjacent edges may have the same color. Then, the graph G edge-colored by f is ℓ → -rainbow connected if every two vertices of G have a path P connecting them such that the number of edges on P that are colored with c j is at most ℓ j for each index j ∈ { 1, 2, …, k }. Given a k-tuple ℓ → and an edge-colored graph, we study the problem of determining whether the edge-colored graph is ℓ → -rainbow connected. In this paper, we first study the computational complexity of the problem with regard to certain graph classes: the problem is NP-complete even for cacti, while is solvable in polynomial time for trees. We then give an FPT algorithm for general graphs when parameterized by both k and ℓ max = max ⁡ { ℓ j | 1 ⩽ j ⩽ k }.

Details DOI

TCS Journal 2014 Journal Article

Reconfiguration of list L ( 2, 1 ) -labelings in a graph

  • Takehiro Ito
  • Kazuto Kawamura
  • Hirotaka Ono
  • Xiao Zhou

For an integer k ≥ 0, suppose that each vertex v of a graph G has a set C ( v ) ⊆ { 0, 1, …, k } of labels, called a list of v. A list L ( 2, 1 ) -labeling of G is an assignment of a label in C ( v ) to each vertex v of G such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L ( 2, 1 ) -labeling of a graph into another list L ( 2, 1 ) -labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L ( 2, 1 ) -labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k ≥ 6. In contrast, we then show that the problem can be solved in linear time for general graphs if k ≤ 4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L ( 2, 1 ) -labelings of a tree can be transformed into each other.

Details DOI

TCS Journal 2013 Journal Article

Energy and fan-in of logic circuits computing symmetric Boolean functions

  • Akira Suzuki
  • Kei Uchizawa
  • Xiao Zhou

In this paper, we consider a logic circuit (i. e. , a combinatorial circuit consisting of gates, each of which computes a Boolean function) C computing a symmetric Boolean function f, and investigate a relationship between two complexity measures, energy e and fan-in l of C, where the energy e is the maximum number of gates outputting “1” over all inputs to C, and the fan-in l is the maximum number of inputs of every gate in C. We first prove that any symmetric Boolean function f of n variables can be computed by a logic circuit of energy e = O ( n / l ) and fan-in l, and then provide an almost tight lower bound e ≥ ⌈ ( n − m f ) / l ⌉ where m f is the maximum numbers of consecutive “0”s or “1”s in the value vector of f. Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function.

Details DOI

TCS Journal 2000 Journal Article

Algorithms for generalized vertex-rankings of partial k-trees

  • Md.Abul Kashem
  • Xiao Zhou
  • Takao Nishizeki

A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. A c-vertex-ranking is optimal if the number of labels used is as small as possible. We present sequential and parallel algorithms to find an optimal c-vertex-ranking of a partial k-tree, that is, a graph of treewidth bounded by a fixed integer k. The sequential algorithm takes polynomial-time for any positive integer c. The parallel algorithm takes O(log n) parallel time using a polynomial number of processors on the common CRCW PRAM, where n is the number of vertices in G.

Details DOI
v2026.09.13