Clustering is a long-standing research problem and a fundamental tool in AI and data analysis. The traditional k-center problem, known as a fundamental theoretical challenge in clustering, has a best possible approximation ratio of 2, and any improvement to a ratio of 2 - ε would imply P = NP. In this work, we study the constrained k-center clustering problem, where instance-level cannot-link (CL) and must-link (ML) constraints are incorporated as background knowledge. Although general CL constraints significantly increase the hardness of approximation, previous work has shown that disjoint CL sets permit constant-factor approximations. However, whether local search can achieve such a guarantee in this setting remains an open question. To this end, we propose a novel local search framework based on a transformation to a dominating matching set problem, achieving the best possible approximation ratio of 2. The experimental results on both real-world and synthetic datasets demonstrate that our algorithm outperforms baselines in solution quality.

Clustering is a fundamental tool that has garnered significant interest across a wide range of applications including text analysis. To improve clustering accuracy, many researchers have proposed incorporating background knowledge, typically in the form of must‑link and cannot‑link constraints, to guide the clustering process. With the recent advent of large language models (LLMs), there is growing interest in improving clustering quality through LLM-based automatic constraint generation. In this paper, we propose a novel constraint‑generation approach that reduces resource consumption by generating constraint sets rather than using traditional pairwise constraints. This improves both query efficiency and constraint accuracy compared to state‑of‑the‑art methods. We further introduce a constrained clustering algorithm tailored to the characteristics of LLM-generated constraints. Our method incorporates a confidence threshold and a penalty mechanism to address potentially inaccurate constraints. We evaluate our approach on five text datasets, considering both the cost of constraint generation and overall clustering performance. The results show that our method achieves clustering accuracy comparable to the state-of-the-art algorithms while reducing the number of LLM queries by more than 20 times.

Lightweight Internet of Things (IoT) devices—microcontroller-class nodes with less than 512KB RAM, sub-100MHz clocks, and low-power radios (BLE, Zigbee, LoRa, NB-IoT)—are now widely deployed in settings where traditional security stacks are infeasible. This survey examines how Artificial Intelligence (AI) can harden such constrained platforms against device-, network-, and application-layer threats, including spoofing, routing manipulation, DDoS, malware, and Advanced Persistent Threats (APTs). We (i) formalize alightweight envelopethat bounds feasible defenses in terms of RAM, CPU, bandwidth, and energy; (ii) consolidate protocol-side risks across BLE, Zigbee, and LoRaWAN; and (iii) review deployable AI techniques through adeployment-firstlens that separates training (edge, cloud, federated learning) from on-device inference. Distinct from prior surveys, we provide resource-annotated comparisons that report accuracyalongsidemodel size, peak RAM, latency, and estimated energy per inference, showing how pruning, post-training quantization, distillation, and feature narrowing shift feasibility on MCU targets. Covered methods include compact classifiers (linear models, trees, SVM), quantized TinyCNN/TinyRNN and graph-based intrusion detection, reinforcement learning for adaptive rate limiting and channel selection, and privacy-preserving federated learning with update compression. We conclude with a pragmatic agenda—energy-adaptive inference, LPWAN-aware scheduling and federated learning, robustness to poisoning and evasion, and reproducible benchmarks that couple accuracy with size/latency/energy on real hardware—aimed at making AI-based security practical at scale for lightweight IoT deployments.

Large Vision-Language Models (LVLMs) have demonstrated impressive capabilities in tasks requiring multimodal understanding. However, recent studies indicate that LVLMs are more vulnerable than LLMs to unsafe inputs and prone to generating harmful content. Existing defense strategies primarily include fine-tuning, input sanitization, and output intervention. Although these approaches provide a certain level of protection, they tend to be resource-intensive and struggle to effectively counter sophisticated attack techniques. To tackle such issues, we propose One-head Defense (Oh Defense), a novel yet simple approach utilizing LVLMs' internal safety capabilities. Through systematic analysis of the attention mechanisms, we discover that LVLMs' safety capabilities are concentrated within specific attention heads that respond differently to safe or unsafe inputs. Further exploration reveals that a single critical attention head can effectively serve as a safety guard, providing a strong discriminative signal that amplifies the model's inherent safety capabilities. Hence, the Oh Defense requires no additional training or external modules, making it computationally efficient while effectively reactivating suppressed safety mechanisms. Extensive experiments across diverse LVLM architectures and unsafe datasets validate our approach, i.e., the Oh Defense achieves near-perfect defense success rates (> 98\%) for unsafe inputs while maintaining low false positive rates (< 5\%) for safe content. The source code is available at https://github.com/AIASLab/Oh-Defense.

Differential privacy (DP) is the de facto privacy standard against privacy leakage attacks, including many recently discovered ones against large language models (LLMs). However, we discovered that LLMs could reconstruct the altered/removed privacy from given DP-sanitized prompts. We propose two attacks (black-box and white-box) based on the accessibility to LLMs and show that LLMs could connect the pair of DPsanitized text and the corresponding private training data of LLMs by giving sample text pairs as instructions (in the blackbox attacks) or fine-tuning data (in the white-box attacks). To illustrate our findings, we conduct comprehensive experiments on modern LLMs (e.g., LLaMA-2, LLaMA-3, ChatGPT-3.5, ChatGPT-4, ChatGPT-4o, Claude-3, Claude-3.5, OPT, GPT-Neo, GPT-J, Gemma-2, and Pythia) using commonly used datasets (such as WikiMIA, Pile-CC, and Pile-Wiki) against both wordlevel and sentence-level DP. The experimental results show promising recovery rates, e.g., the black-box attacks against the word-level DP over WikiMIA dataset gave 72.18% on LLaMA2 (70B), 82.39% on LLaMA-3 (70B), 75.35% on Gemma-2, 91.2% on ChatGPT-4o, and 94.01% on Claude-3.5 (Sonnet). More urgently, this study indicates that these well-known LLMs have emerged as a new security risk for existing DP text sanitization approaches in the current environment.

Two parties wish to collaborate on their datasets. However, before they reveal their datasets to each other, the parties want to have the guarantee that the collaboration would be fruitful. We look at this problem from the point of view of machine learning, where one party is promised an improvement on its prediction model by incorporating data from the other party. The parties would only wish to collaborate further if the updated model shows an improvement in accuracy. Before this is ascertained, the two parties would not want to disclose their models and datasets. In this work, we construct an interactive protocol for this problem based on the fully homomorphic encryption scheme over the Torus (TFHE) and label differential privacy, where the underlying machine learning model is a neural network. Label differential privacy is used to ensure that computations are not done entirely in the encrypted domain, which is a significant bottleneck for neural network training according to the current state-of-the-art FHE implementations. We formally prove the security of our scheme assuming honest-but-curious parties, but where one party may not have any expertise in labelling its initial dataset. Experiments show that we can obtain the output, i.e., the accuracy of the updated model, with time many orders of magnitude faster than a protocol using entirely FHE operations.

Deep models excel in analyzing image data. However, recent studies on Black-Box Model Inversion (MI) Attacks against image models have revealed the potential to recover concealed (via specific masks) private training images using publicly available images from the same domain as the training data. This study introduces PriDM, a novel diffusion model-based MI attack, illustrating the increased vulnerability of image models. PriDM leverages range-null space decomposition to extract essential range-space information and incorporates it into the diffusion model's sampling process. This enables the recovery of private information from arbitrarily masked images relying solely on images only aligned with the same machine-learning tasks as the target model. To demonstrate PriDM's effectiveness, we conducted experiments with various adversary background knowledge, including different public dataset domains and image masks. Results show PriDM produces recovered images of significantly higher quality, approximately twice as good as existing methods. Moreover, in scenarios involving complex backgrounds, PriDM outperforms the state-of-the-art by approximately 70%. In specific background knowledge scenarios, such as compressed and blurred images, our method achieves an almost 100% success rate. Additionally, PriDM performs well with real-world background knowledge including individuals wearing masks and randomly masked face images, which are not considered by existing works.

The widespread adoption of 5 G networks and mobile devices has led to a surge in the generation of private data, creating massive data streams. Securing and continuously releasing histogram data over sliding windows in these streams has become a critical issue, as it enables understanding recent collective phenomena in data streams while preserving individual privacy. Existing state-of-the-art methods require buffering all data from each sliding window to reconstruct accurate histograms, which is unnecessary and significantly hampers efficiency. This paper proposes an online streaming sampling publication framework with differential privacy, named thePublishingApproach withSliding window estimation-count sketch(PAS), which constructs an approximate histogram without buffering each sliding window and subsequently generates publishable histograms. Specifically, we introduce a novel memory-efficient sketch structure called theSliding WindowEstimation-CountSketch(SES), which facilitates rapid retrieval of counts within sliding window intervals while providing guaranteed data protection. The output of this sketch structure approximates true counts while theoretically incorporating differentially private noise, thus ensuring$(\epsilon , \delta )$-differential privacy. Moreover, to improve the speed of histogram generation and reduce processing time in PAS, we propose an adaptive histogram generation algorithm based on SES. Extensive experiments are conducted to demonstrate the effectiveness of the proposed methods in comparison with other publication methods.

Many practical applications impose a new challenge of utilizing instance-level background knowledge (e.g., subsets of similar or dissimilar data points) within their input data to improve clustering results. In this work, we build on the widely adopted k-center clustering, modeling its input instance-level background knowledge as must-link (ML) and cannot-link (CL) constraint sets, and formulate the constrained k-center problem. Given the long-standing challenge of developing efficient algorithms for constrained clustering problems, we first derive an efficient approximation algorithm for constrained k-center at the best possible approximation ratio of 2 with linear programming (LP)-rounding technology. Recognizing the limitations of LP-rounding algorithms including high runtime complexity and challenges in parallelization, we subsequently develop a greedy algorithm that does not rely on the LP and can be efficiently parallelized. This algorithm also achieves the same approximation ratio 2 but with lower runtime complexity. Lastly, we empirically evaluate our approximation algorithm against baselines on various real datasets, validating our theoretical findings and demonstrating significant advantages of our algorithm in terms of clustering cost, quality, and runtime complexity.

Center-based clustering has attracted significant research interest from both theory and practice. In many practical applications, input data often contain background knowledge that can be used to improve clustering results. In this work, we build on widely adopted k-center clustering and model its input background knowledge as must-link (ML) and cannot-link (CL) constraint sets. However, most clustering problems including k-center are inherently NP-hard, while the more complex constrained variants are known to suffer severer approximation and computation barriers that significantly limit their applicability. By employing a suite of techniques including reverse dominating sets, linear programming (LP) integral polyhedron, and LP duality, we arrive at the first efficient approximation algorithm for constrained k-center with the best possible ratio of 2. We also construct competitive baseline algorithms and empirically evaluate our approximation algorithm against them on a variety of real datasets. The results validate our theoretical findings and demonstrate the great advantages of our algorithm in terms of clustering cost, clustering quality, and running time.

Deploying Machine Learning as a Service gives rise to model plagiarism, leading to copyright infringement. Ownership testing techniques are designed to identify model fingerprints for verifying plagiarism. However, previous works often rely on overfitting or robustness features as fingerprints, lacking theoretical guarantees and exhibiting under-performance on generalized models. In this paper, we propose a novel ownership testing method called VeriDIP, whichverifies aDNN model'sintellectualproperty. VeriDIP makes two major contributions. (1) It utilizes membership inference attacks to estimate the lower bound of privacy leakage, which reflects the fingerprint of a given model. The privacy leakage fingerprints highlight the unique patterns through which the models memorize sensitive training datasets. (2) We introduce a novel approach using less private samples to enhance the performance of ownership testing. Extensive experimental results confirm that VeriDIP is effective and efficient in validating the ownership of deep learning models trained on both image and tabular datasets. VeriDIP achieves comparable performance to state-of-the-art methods on image datasets while significantly reducing computation and communication costs. Enhanced VeriDIP demonstrates superior verification performance on generalized deep learning models, particularly on table-trained models. Additionally, VeriDIP exhibits similar effectiveness on utility-preserving differentially private models compared to non-differentially private baselines.

Differential privacy (DP) has been applied in deep learning for preserving privacy of the underlying training sets. Existing DP practice falls into three categories—objective perturbation (injecting DP noise into the objective function), gradient perturbation (injecting DP noise into the process of gradient descent) and output perturbation (injecting DP noise into the trained neural networks, scaled by the global sensitivity of the trained model parameters). They suffer from three main problems. First, conditions on objective functions limit objective perturbation in general deep learning tasks. Second, gradient perturbation does not achieve a satisfactory privacy-utility trade-off due to over-injected noise in each epoch. Third, high utility of the output perturbation method is not guaranteed because of the loose upper bound on the global sensitivity of the trained model parameters as the noise scale parameter. To address these problems, we analyse a tighter upper bound on the global sensitivity of the model parameters. Under a black-box setting, based on this global sensitivity, to control the overall noise injection, we propose a novel output perturbation framework by injecting DP noise into a randomly sampled neuron (via the exponential mechanism) at the output layer of a baseline non-private neural network trained with a convexified loss function. We empirically compare the privacy-utility trade-off, measured by accuracy loss to baseline non-private models and the privacy leakage against black-box membership inference (MI) attacks, between our framework and the open-source differentially private stochastic gradient descent (DP-SGD) approaches on six commonly used real-world datasets. The experimental evaluations show that, when the baseline models have observable privacy leakage under MI attacks, our framework achieves a better privacy-utility trade-off than existing DP-SGD implementations, given an overall privacy budget$\epsilon \leq 1$for a large number of queries.

Paths in a given network represent the occurrence sequences of nodes in many real world applications, such as disease transmission chains, object trajectories and data access sequences. In this paper, we address the problem of publishing edge-privacy preserved path information for a single path such that legitimate users with the full knowledge of the network can reconstruct the path with the published information, but not adversaries, even if they have the maximum background knowledge of all the vertices and all edges but one (on the path) of the network. Existing studies on edge privacy against inference attacks focus on publishing either differential privacy (DP) noise injected graph statistics or DP edge perturbed graph topology to achieve edge differential privacy preservation. However, none of them provides an assurance on both edge privacy and data utility. To effectively protect edge privacy and maintain data utility, we propose a novel scheme of DP augmentation instead of DP perturbation as did in existing work, that publishes a simple-topology graph containing an augmented path with fake edges and vertices applying differential privacy to protect the actual path, such that only the legitimate users are able to reconstruct the actual path with high probability. We theoretically analyse the performance of our algorithm in terms of output quality on differential privacy and utility, and execution efficiency. We also conduct extensive experimental evaluations on a high-performance cluster system to validate our analytical results.

Generative Adversarial Networks (GAN)-synthesized table publishing lets people privately learn insights without access to the private table. However, existing studies on Membership Inference (MI) Attacks show promising results on disclosing membership of training datasets of GAN-synthesized tables. Different from those works focusing on discovering membership of a given data point, in this paper, we propose a novel Membership Collision Attack against GANs (TableGAN-MCA), which allows an adversary given only synthetic entries randomly sampled from a black-box generator to recover partial GAN training data. Namely, a GAN-synthesized table immune to state-of-the-art MI attacks is vulnerable to the TableGAN-MCA. The success of TableGAN-MCA is boosted by an observation that GAN-synthesized tables potentially collide with the training data of the generator.

Smart meter data is collected and shared with different stakeholders involved in a smart grid ecosystem. The fine-grained energy data is extremely useful for grid operations and maintenance, monitoring and for market segmentation purposes. However, sharing and releasing fine-grained energy data induces explicit violations of private information of consumers (Molina-Markham et al., 2010). Service providers do then share and release aggregated statistics to preserve the privacy of consumers with data aggregation aiming at reducing the risks of individual consumption traces being revealed. In this paper, we show that an adversary can reconstruct individual traces of energy data by exploiting consistency (similar consumption patterns over time) and distinctiveness (one household’s energy consumption pattern is significantly different from that of others) properties of individual consumption load patterns. We propose an unsupervised attack framework to recover hourly energy consumption ti me-series of individual users without any prior knowledge. We pose the problem of assigning aggregated energy consumption meter readings to individuals as an assignment problem and solve it by the Hungarian algorithm (Xu et al., 2017; Kuhn, 1955). Using two real-world datasets, our empirical evaluations show that an adversary is capable of recovering over 70% of households’ energy consumption patterns with over 90% accuracy.

Iterative clustering around representative points is an effective technique for clustering and helps us learn insights behind data to support various important applications. Unfortunately, it also provides security holes which may allow adversaries to infer the privacy of individuals with some background knowledge. To protect individual privacy against such inference attacks, preserving differential privacy for iterative clustering algorithms has been extensively studied. Existing differentially private clustering algorithms adopt the same framework to compute differentially private centroids iteratively by running Lloyd's k-means algorithm to obtain the actual centroids, then perturbing them with a differential privacy mechanism. These algorithms suffer from the problem of no convergence guarantee, i.e., they provide no guarantee of termination at a solution of Lloyd's algorithm within a bounded number of iterations. This problem severely impacts their clustering quality and execution efficiency. To address this problem, this article follows the same centroid updating pattern as existing work in interactive settings; however we propose a novel framework for injecting differential privacy into the actual centroids. Specifically, to ensure convergence, we maintain the perturbed centroids of the previous iterationt-1 to compute a convergence zone for each cluster in the current iterationt, where we inject differential privacy noise. To achieve a satisfactory convergence rate, we further control the orientation of centroid movement in each cluster using two strategies: one takes the orientation of centroid movement from iterationt-1 to iterationt(past knowledge); the other uses the additional information of the orientation from iterationt+1 (future knowledge). We prove that, in the expected case, our algorithm (in both strategies) converges to a solution of Lloyd's algorithm in at most twice as many iterations as Lloyd's algorithm. Furthermore, when using both past and future knowledge, we prove that our algorithm converges to the same solution as Lloyd's algorithm (for the same initial centroids) with high probability, at the cost of a slower convergence speed compared to using only past knowledge due to duplicated operations in each iteration required for computing the future knowledge. We perform experimental evaluations on seven widely used real-world datasets. The experimental results show that our algorithm outperforms the state-of-the-art methods for interactive differentially private clustering with a guaranteed convergence and better clustering quality whilst meeting the same differential privacy requirements.

Along with the increased convenience of our daily life thanks to the proliferation of location-based service (LBS), such as finding restaurants and booking taxi, concerns on privacy disclosure risks in sharing our locations with LBS have also increased and become a major bottleneck that obstacles the widespread of adoption of LBS [1]. To preserve privacy in LBS, k-anonymity was applied to conceal people's sensitive information against re-identification attacks [2]. Unfortunately, the k-anonymity technique relies on predefined background knowledge of an adversary. Once the adversary has different auxiliary information, we cannot guarantee any privacy preservation against such an adversary. To address the privacy leakage problem of the naive k-anonymity, a combination of k-anonymity and location's query frequency algorithm, the Caching-aware Dummy Selection Algorithm (CaDSA), were proposed [3]. CaDSA anonymises locations in a given area by grouping them with similar query frequency during a fixed time period, say one day. However, considering in the real-life situation location's query frequency often varies in different time slots even in a single day, privacy will clearly lose if we roughly group locations according to a fixed time period as CaDSA. Consequently, in this paper, we propose a Temporal Caching-aware Dummy Location Selection Algorithm (T-CaDLSA) that considers the differences among location's query frequencies over different time slots within a given time period (day). Both mathematical and experimental evaluations show that to achieve the same data utility, our method outperforms the existing work in privacy guarantee.

Distributed data aggregation via summation (counting) helped us to learn the insights behind the raw data. However, such computing suffered from a high privacy risk of malicious collusion attacks. That is, the colluding adversaries infer a victim's privacy from the gaps between the aggregation outputs and their source data. Among the solutions against such collusion attacks, Distributed Differential Privacy (DDP) shows a significant effect of privacy preservation. Specifically, a DDP scheme guarantees the global differential privacy (the presence or absence of any data curator barely impacts the aggregation outputs) by ensuring local differential privacy at the end of each data curator. To guarantee an overall privacy performance of a distributed data aggregation system against malicious collusion attacks, part of the existing work on such DDP scheme aim to provide an estimated lower bound of privacy budget for the global differential privacy. However, there are two main problems: low data utility from using a large global function sensitivity; unknown privacy guarantee when the aggregation sensitivity of the whole system is less than the sum of the data curator's aggregation sensitivity. To address these problems while ensuring distributed differential privacy, we provide a new lower bound of privacy budget, which works with an unconditional aggregation sensitivity of the whole distributed system. Moreover, we study the performance of our privacy bound in different scenarios of data updates. Both theoretical and experimental evaluations show that our privacy bound offers better global privacy performance than the existing work.

The neighbourhood-based Collaborative Filtering is a widely used method in recommender systems. However, the risks of revealing customers' privacy during the process of filtering have attracted noticeable public concern recently. Specifically, kNN attack discloses the target user's sensitive information by creating k fake nearest neighbours by non-sensitive information. Among the current solutions against kNN attack, the probabilistic methods showed a powerful privacy preserving effect. However, the existing probabilistic methods neither guarantee enough prediction accuracy due to the global randomness, nor provide assured security enforcement against kNN attack. To overcome the problems of current probabilistic methods, we propose a novel approach, Probabilistic Partitioned Neighbour Selection, to ensure a required security guarantee while achieving the optimal prediction accuracy against kNN attack. In this paper, we define the sum of k neighbours' similarity as the accuracy metric α, the number of user partitions, across which we select the k neighbours, as the security metric β. Differing from the present methods that globally selected neighbours, our method selects neighbours from each group with exponential differential privacy to decrease the magnitude of noise. Theoretical and experimental analysis show that to achieve the same security guarantee against kNN attack, our approach ensures the optimal prediction accuracy.