We investigate the complexity of stable (or perturbation-resilient) instances of k-Means and k-Median clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euclidean spaces, we adopt a more general notion of stability, termed "almost stable", known from the literature as (alpha,epsilon)-perturbation resilience. Additionally, we extend our results to k-Means/k-Median with penalties, where each data point is either assigned to a cluster centre or incurs a penalty. We show that certain special cases of almost stable k-Means/k-Median (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and (1 + 1/poly(n))-stable instances of k-Means/k-Median (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH).
论文检索
输入标题、作者或关键词，从 100,903 篇学术成果中精准定位
We introduce and study the multi-agent stochastic shortest path (MSSP) problem, in which k agents strive to reach a target state, aiming to minimize the expected time to reach the target by any agent. We analyze the computational and strategy-complexity of the problem in both autonomous and coordinated settings, and we design efficient strategy-synthesis algorithms. The algorithms are experimentally evaluated on instances of increasing size against natural baselines.
Multi-view clustering aims to utilize information from multiple feature representations to uncover underlying data structures. Most existing methods emphasize learning a consensus representation by enforcing consistency across views. However, those structures that cannot be directly incorporated into the clustering space receive little attention, and are often discarded as noise in practice. In this paper, we argue that such information can be informative signals for the clustering process and should be explicitly modeled rather than suppressed or ignored. Specifically, we propose salient-residual decoupled multi-view learning for clustering, SRDMVC, introducing a novel decomposition-fusion iterative optimization, which separates the feature space into a salient space and a residual subspace effectively and fuses them using a novel attention mechanism. The residual subspace can capture the deep-level structure of view information, making positive contributions to the clustering process, under proper constraints. Without assuming stronger view alignment or complementarity, SRDMVC enhances cluster discrimination, avoids spurious consensus, and alleviates representation degradation. Extensive experiments on benchmark datasets demonstrate the superior performance of the method we propose.
Dynamic graph neural networks (DyGNNs) are widely used to model evolving interactions, but may fail under data distribution shift. Due to limited and unreliable interventions and insufficient disentanglement, the existing dynamic graph domain generalization approaches lead to suboptimal results. We formalize a message sufficiency causal view: a node representation is fully mediated by its received message multiset. Building on this perspective, we propose Latent environment Extrapolation and Message Disentanglement (LEMD), a novel robust representation learning framework for dynamic graph domain generalization. A message extrapolation mechanism under soft uncertainty constraints is proposed to obtain the diverse counterfactual message distributions. Causal information is disentangled fully from the messages to suppress shortcuts via a recoverable evolving disentanglement module. We further provide rigorous theoretical analysis and proofs to ensure the effectiveness of LEMD. Across all six datasets and two tasks, LEMD consistently improves over state-of-the-art dynamic graph generalization baselines under distribution shift, and achieves the best performance increase of 7.7% relative compared to the suboptimal baseline. The code of LEMD for reviewer is available at https://github.com/W-WuJi/LEMD.
Argumentation dynamics provides techniques for revising argumentation theories in real-world domains (e.g., an autonomous medical diagnostic agent). Within this context, enforcement in abstract argumentation has become a prominent topic. Enforcement aims to modify an argumentation framework to satisfy given acceptability conditions while minimizing change from the original framework. Motivated by the need to address both syntactic and semantic notions of change, we propose formula-based enforcement, a generic framework that strictly generalizes existing approaches, by additionally covering cases they cannot handle, including semantic change. We analyze its complexity under central argumentation semantics, obtaining results from NP-completeness to completeness for the third level of the polynomial hierarchy. For second-level complete variants, we present an exact procedure based on MaxSAT solving and counterexample-guided abstraction refinement (CEGAR), and evaluate it empirically.
Responsibility allocation---determining the extent to which agents are accountable for outcomes---is a fundamental challenge in the design and analysis of multi-agent systems. In this work, we model such systems as concurrent stochastic multi-player games and introduce a notion of retrospective (backward) counterfactual responsibility, which quantifies an agent's accountability for outcomes resulting from a given strategy profile. To allocate responsibility among agents, we utilise the Shapley value and formally show that this method satisfies key desirable properties, including fairness and consistency. Building on this foundation, we propose a formal framework that supports both verification and strategic reasoning in responsibility-aware multi-agent systems. Furthermore, by adopting Nash equilibrium as the solution concept, we demonstrate how to compute stable strategy profiles in which agents trade off responsibility against expected reward.
Optimization in industrial systems often involves calibrating from a semi-optimized state, where global exploration methods like Reinforcement Learning (RL) or Bayesian Optimization (BO) are inefficient or unsafe. We propose Causal Newton Optimization (CNO), an online algorithm that iteratively calibrates inputs under a known causal graph but unknown structural equations. CNO estimates local linear causal effects via additive interventions and employs a log-linear variance regression to robustly guide Newton-based updates. Evaluations on synthetic systems and a chemical plant simulator demonstrate that CNO achieves the best balance between objective improvement and robustness. While traditional PID control suits standard dynamical systems, CNO significantly outperforms RL and BO in complex structural causal models, providing the robust stability vital for safety-critical real-world applications.
Code-switching (CS) speech translation (ST) aims to translate speech that alternates between multiple languages into a target language text, posing significant challenges due to the complexity of semantic modeling and the scarcity of CS data. Previous studies mainly rely on the models themselves to implicitly learn semantic representations and resort to costly manual annotations. To mitigate these limitations, we propose enhancing Large Language Models (LLMs) with a Mixture-of-Experts (MoE) speech projector composed of language expert groups, where each group specializes in the semantic space of a specific language for fine-grained speech feature modeling. A language-specific loss and an intra-group load balancing loss are jointly introduced to guide efficient token routing across and within expert groups. Furthermore, we introduce a multi-stage training paradigm that utilizes readily available automatic speech recognition (ASR) and monolingual ST data, facilitating speech-text alignment and improving translation performance. To bridge the data gap for smooth domain transfer, a transition loss is employed to improve adaptation to CS scenarios. Extensive experiments on widely used datasets demonstrate the effectiveness and generality of our approach, achieving average improvements of 0.86 BLEU and 0.93 COMET over SeamlessM4T, with maximum improvements of 1.49 BLEU and 1.41 COMET across different test sets. Our code and supplementary appendices are available at https://github.com/XMUDeepLIT/CSST-SSA.
Remote Sensing Image-Text Retrieval (RSITR) aims to achieve precise retrieval between remote sensing images and textual descriptions. However, existing methods neglect the multi-dimensional cognitive attributes inherent in remote sensing data and struggle to handle them simultaneously, leading to suboptimal retrieval performance. In this paper, we propose a novel Progressive Decoupling-Aggregation-Refinement framework for RSITR (PDAR-RSITR) to comprehensively capture multi-dimensional cognitive attributes. Specifically, we adapt Multi-dimensional Cognitive Decoupling to learn features across cognitive attributes of different dimensions via multi-process clustering. Subsequently, we utilize Salient Cognitive Aggregation to select and aggregate the most salient attributes via dynamic routing. Furthermore, we propose Expert Collaborative Refinement to enhance critical cross-modal relationships via three complementary expert perspectives. Extensive experimental results demonstrate that PDAR-RSITR significantly outperforms existing state-of-the-art methods across multiple metrics.
With the rising demand for trustworthy AI in clinical practice, strong interpretability is now a critical requirement as well as accuracy. However, the modality gap for medical visual question answering is quite severe when continuous visual signals are forcibly projected into discrete text space for reasoning, and the loss of necessary diagnostic information leads to low precision and black-box opacity. To address this problem, we propose MedVCoT, which incorporates latent visual reasoning into the medical visual question answering(VQA) domain. Rather than merely integrating modules, MedVCoT utilizes the specialized expertise of MedSAM to train a large vision-language model so that it can autonomously generate consistent and continuous latent visual tokens within Visual Chain-of-Thought. This mechanism forces the model to explicitly "see" the lesion in the latent space before formulating a textual diagnosis, ensuring answers are causally rooted in verifiable visual evidence rather than statistical hallucination. We achieve this through a progressive 3-stage training procedure: medical feature alignment, visual reasoning learning by utilizing latent tokens generated, and instruction tuning for complex clinical scenarios. Extensive experiments show that MedVCoT can achieve state-of-the-art performance on multiple benchmarks, outperforming other methods by large margins. Meanwhile, it provides pixel-level segmentation masks to validate its diagnostic reasoning. Our demo is available at https://zhuqh19.github.io/MedVCoT.
Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often used for query evaluation in probabilistic databases. Due to the computational intractability of exact DNF counting, there has been a line of research into a variety of approximation algorithms. We develop a new Monte Carlo approach with an adaptive stopping rule and short-circuit formula evaluation. We prove it achieves Probably Approximately Correct (PAC) learning bounds and has asymptotically improved time and randomness complexity compared to previous methods. We also show experimentally that it out-performs prior algorithms by at least three orders of magnitude in running time and scalability.
Virtual Knowledge Graphs (VKGs) provide unified access to legacy relational data sources through a high-level ontology modeling a domain of interest. The content of the ontology elements (classes and properties) is virtually mapped to underlying data sources through declarative mappings. The standard approach to interacting with a VKG system is to use SPARQL as the query language. However, the complexity of SPARQL creates a high entry barrier for normal users. In this paper, we study the VKG-QA task, which enables users to interact with the VKGs through a natural language (NL) interface by translating their questions into SPARQL queries. One critical challenge in such translation is silent failures, where a syntactically correct SPARQL query returns empty results because it involves ontology elements that lack mappings to the underlying data. To address this, we propose NaVQA (Navigation-based VKG Question Answering), a framework leveraging Large Language Models that (1) identifies and indexes the active ontology elements based on the mapping specifications, and (2) iteratively constructs a query graph from the NL question using the active ontology elements and their relations to synthesize SPARQL. Experiments on three real-world VKGs show that NaVQA significantly mitigates silent failures and outperforms existing baselines.
The learnware paradigm aims to construct a dock system that maintains a collection of learnwares, each consisting of a well-established model coupled with a specification, thereby enabling users to directly reuse existing models to solve their tasks without training models from scratch. As a core component of the paradigm, the specification sketches the model’s properties and establishes reusability between the learnware and user tasks. Existing methods have demonstrated promising performance by designing specifications that characterize the task distributions mastered by well-established models. However, in complex real-world scenarios, task distributions often overlap, thereby weakening the uniqueness of specifications and obscuring the reusability relationships between learnwares and tasks. In this paper, we design an Explicitly Distinctive Specification (EDS) that enforces specification uniqueness, improving the discriminative capability of the learnware paradigm and avoiding ambiguity caused by overlapping task distributions. This specification method explicitly leverages distributional discrepancies between specifications to strengthen the uniqueness of the model properties sketched during the submitting stage and subsequently exploits the enhanced distributional discriminability in the deploying stage to improve learnware reusability. Extensive experiments demonstrate the effectiveness and strong performance of the proposed EDS within the learnware paradigm under complex task scenarios.
Graph pre-training and prompt tuning provide an effective route to label-efficient node classification by learning transferable backbones and adapting them with lightweight prompts. However, existing pre-train-and-prompt pipelines often generalize poorly across graphs with diverse homophily due to two fundamental limitations: (i) spectral bias, where learned representations overemphasize a single frequency band, and (ii) prompt misalignment, where spatial-domain prompts cannot explicitly modulate critical spectral components and may even disrupt frequency-aware backbones. In this paper, we propose SCA-GPPT, a spectrum-aware framework that unifies Spectrum-based Graph Pre-training and Cluster-Augmented Prompt Tuning. First, we present a systematic spectral analysis of graph prompting, revealing the inherent limitations of spatial-domain prompts in capturing attenuated high-frequency signals. Second, we explicitly learn complementary low- and high-frequency spectral filters via parameterized Chebyshev polynomials and employ band-aware contrastive learning to model diverse spectral patterns during pre-training. For downstream adaptation, we freeze the pre-trained backbone and introduce cluster-augmented prompts that directly adapt Chebyshev coefficients while enforcing global structural consistency, enabling stable few-shot transfer across varying homophily regimes. Extensive experiments on real-world benchmarks demonstrate that SCA-GPPT consistently outperforms strong baselines under both transductive and inductive settings. Our code is available at https://anonymous.4open.science/r/SCA-GPPT-17B2.
Retinal angiography provides critical vascular information, yet optical coherence tomography angiography (OCTA) acquisition remains slower and less accessible than conventional structural OCT. A key open question is: how angiographic signals can be recovered? To address the issues of artifacts and structural blurring in existing generative methods, we propose a wavelet flow matching-based model, FlowOCT. This method operates directly on OCT wavelet coefficients, learning frequency-specific velocity fields to map them to the OCTA wavelet distribution. To ensure anatomical accuracy of the vasculature, we introduce constraints such as depth-wise contrastive alignment and two-dimensional projection consistency. Given the sparse nature of vascular signals in OCTA data, a structure-focused loss function and corresponding evaluation metrics are designed. Experiment results show that FlowOCT outperforms existing methods in terms of both image quality and perceptual similarity. Downstream diagnostic tasks further validate its superior authenticity and generalization capability. Code is available at https://github.com/cnu-medilab/FlowOCT.
Deep learning has achieved remarkable success in automated electrocardiogram (ECG) diagnosis. However, the long-tailed distribution of real-world ECG data remains a critical challenge. Existing methods mainly operate at the signal feature level and fail to exploit semantic relationships among diagnostic labels, which limits their ability to effectively recognize rare categories. To address this issue, we propose a Semantics-Guided Representation Learning (SGRL) framework, designed to leverage semantic priors to guide feature learning and thereby correct feature bias under long-tailed distributions. Specifically, we propose a Label Semantic Prompt Adaptation (LSPA) strategy, which introduces ECG-calibrated learnable parameters into label prompts to generate adaptive label semantic embeddings under a semantic-consistency constraint, thereby overcoming the limitations of coarse-grained label prompts in characterizing fine-grained intra-class morphological variations. Subsequently, we propose Semantic-Guided Representation Decorrelation (SGRD) that fuses ECG embeddings with adaptive label semantics and suppresses inter-class semantic correlations to obtain discriminative class semantic anchors, thereby improving tail-class separability. Extensive experiments on multiple public datasets demonstrate the significant superiority of SGRL in long-tailed ECG classification tasks. Our code is available on https://github.com/gfywudi/SGRL.
Large visual-language models demonstrate exceptional transferability in biomedical image analysis, yet their robustness remains challenging in generalization scenarios such as few-shot learning. This limitation stems from an overly entangled prompt space, causing instability in the conditional distribution, coupled with saliency bias that drives attention to dominate key regions, thereby restricting the coverage of visual representations. Furthermore, cross-modal fusion often struggles to extract critical information signals from redundant alignments. To address these structural bottlenecks, we propose TriCLIP, a decomposition-based framework designed to reconstruct the entire information flow across prompt conditioning, visual evidence extraction, and cross-modal fusion. Prompt Distribution Regularization enhances robustness to linguistic variations by optimizing class-conditional random context perturbations for continuous prompts. Feedback-driven Counterfactual Masking constructs a feedback-driven reverse saliency view that suppresses dominant evidence to promote complementary cue learning and mitigate attention bias. Finally, Selective Regulation Fusion regulates fusion selectivity through paired reinforcement-suppression principles, amplifying information correspondence while suppressing redundant channels. Extensive experiments on diverse biomedical benchmarks indicate that the proposed TriCLIP consistently outperforms existing methods.
Optimizing survival outcomes, such as patient survival or customer retention, is a critical objective in data-driven decision-making. Off-Policy Evaluation (OPE) provides a powerful framework for assessing such decision-making policies using logged data alone, without the need for costly or risky online experiments in high-stakes applications. However, typical estimators are not designed to handle right-censored survival outcomes, as they ignore unobserved survival times beyond the censoring time, leading to systematic underestimation of the true policy performance. To address this issue, we propose a novel framework for OPE and Off-Policy Learning (OPL) tailored for survival outcomes under censoring. Specifically, we introduce IPCW-IPS and IPCW-DR, which employ the Inverse Probability of Censoring Weighting technique to explicitly deal with censoring bias. We theoretically establish that our estimators are unbiased and that IPCW-DR achieves double robustness, ensuring consistency if either the propensity score or the outcome model is correct. Furthermore, we extend this framework to constrained OPL to optimize policy value under budget constraints. We demonstrate the effectiveness of our proposed methods through simulation studies and illustrate their practical impacts using public real-world data for both evaluation and learning tasks.
Transformer models are rapidly becoming a cornerstone of modern Internet of Things (IoT) applications, yet their computational and memory demands far exceed the capabilities of a single typical ultra-low-power IoT device. We present CATS, a framework for distributed transformer inference on ultra-low-power wireless devices, enabling multiple devices to collaboratively execute models far larger than what a single device can sustain. At its core, CATS is a communication-aware distributed transformer inference scheme co-designed across transformer partitioning, wireless communication and training. It employs SomeGather, a new pruned communication primitive that selectively broadcasts activation columns to reduce communication bandwidth and RAM usage without sacrificing model accuracy. Building on SomeGather, we design a partitioning method that exploits this primitive for efficient model parallelism. To cope with unreliable wireless communication, CATS employs message-dropout during training, which mimics packet losses and yields models that are robust to message loss during inference. In real-world experiments, we show that CATS brings distributed transformer inference to ultra-low-power wireless devices for the first time, with deployments on up to 16 devices that collaboratively execute transformer models up to 14 times larger than what a single device can run.
We study multi-task reinforcement learning (RL), a setting in which an agent learns a single, universal policy capable of generalising to arbitrary, possibly unseen tasks. We consider tasks specified as linear temporal logic (LTL) formulae, which are commonly used in formal methods to specify properties of systems, and have recently been successfully adopted in RL. In this setting, we present a novel task embedding technique leveraging a new generation of semantic LTL-to-automata translations, originally developed for temporal synthesis. The resulting semantically labelled automata contain rich, structured information in each state that allow us to (i) compute the automaton efficiently on-the-fly, (ii) extract expressive task embeddings used to condition the policy, and (iii) naturally support full LTL. Experimental results in a variety of domains demonstrate that our approach achieves state-of-the-art performance and is able to scale to complex specifications where existing methods fail.