Multiplex graphs represent diverse real-world interactions among entities, where multiple relationship types coexist within the same set of entities. These graphs introduce privacy risks, as data collectors can exploit cross-layer dependencies to infer hidden and sensitive connections. In this work, we propose aC2P-Mframework that identifies and protects critical connections while preserving the structural information in multiplex graphs. Unlike conventional methods for single-layer graphs that perturb all edges uniformly,C2P-Mselectively protects critical connections, maintaining the analytical usability of the graph. To achieve this, we introduce the multiplex$p$-cohesion model, which incorporates new score functions that account for both intra-layer and inter-layer dependencies, enabling precise identification of critical connections for each vertex. For privacy protection, our method protects the identified critical connections, leveraging an adaptive Randomized Response (RR) mechanism to ensure$\varepsilon$-Local Differential Privacy (LDP). We formally prove thatC2P-Msatisfies$\varepsilon$-LDP. Extensive experiments on eight real-world multiplex graph datasets demonstrate thatC2P-Msignificantly outperforms baseline privacy-preserving methods, achieving a better privacy-utility trade-off.

k-truss is a widely studied cohesive sub graph model that has gained significant attention over the past decades. Truss decomposition, a fundamental task in graph analysis, aims to compute the largest k for which an edge belongs to a k-truss. However, directly performing truss decomposition on sensitive graphs risks exposing the private information of user connections in real-world applications. Edge local differential privacy (edge LDP) is extensively used to protect the privacy of edges in graph analysis. This paper, for the first time, addresses the problem of truss decomposition under edge LDP. A naive approach allows each vertex to perturb its neighbor list locally and generate a noisy graph for truss decomposition. However, it often produces excessive truss number estimations, since the noisy graph is generally much denser and fails to preserve the input graph structure. To obtain more accurate estimates, we propose the Local algorithm that leverages the local information during the truss decomposition process. Furthermore, to avoid adding substantial noise to truss numbers to satisfy edge LDP, we introduce the Global algorithm that optimizes the noise scale of support numbers, enhancing the accuracy of truss decom-position results. We further propose the Global * algorithm that eliminates the need for vertices to download noisy edges by utilizing noisy degrees to adjust support numbers during truss decomposition, achieving high accuracy with significantly lower communication costs. Extensive experiments on 9 real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.

This paper focuses on Zero-Trust Foundation Models (ZTFMs), a novel paradigm that embeds zero-trust security principles into the lifecycle of foundation models (FMs) for Internet of Things (IoT) systems. By integrating core tenets, such as least privilege access, continuous verification, data confidentiality, and behavioral analytics into the design, training, and deployment of FMs, ZTFMs can enable secure, privacy-preserving AI across distributed, heterogeneous, and potentially adversarial IoT environments. We present the first structured synthesis of ZTFMs, identifying their potential to transform conventional trust-based IoT architectures into resilient, self-defending ecosystems. Moreover, we propose a comprehensive technical framework, incorporating federated learning (FL), blockchain-based identity management, micro-segmentation, and trusted execution environments (TEEs) to support decentralized, verifiable intelligence at the network edge. In addition, we investigate emerging security threats unique to ZTFM-enabled systems and evaluate countermeasures, such as anomaly detection, adversarial training, and secure aggregation. Through this analysis, we highlight key open research challenges in terms of scalability, secure orchestration, interpretable threat attribution, and dynamic trust calibration. This survey lays a foundational roadmap for secure, intelligent, and trustworthy IoT infrastructures powered by FMs.

Many real-world interconnections among entities can be characterized as graphs. Collecting local graph information with balanced privacy and data utility has garnered notable interest recently. This paper delves into the problem of identifying and protecting critical information of entity connections for individual participants in a graph based on cohesive subgraph searches. This problem has not been addressed in the literature. To address the problem, we propose to extract the critical connections of a queried vertex using a fortress-like cohesive subgraph model known as$p$-cohesion. A user's connections within a fortress are obfuscated when being released, to protect critical information about the user. Novel merit and penalty score functions are designed to measure each participant's critical connections in the minimal$p$-cohesion., facilitating effective identification of the connections. We further propose to preserve the privacy of a vertex enquired by only protecting its critical connections when responding to queries raised by data collectors. We prove that, under the decentralized differential privacy (DDP) mechanism, one's response satisfies$(\varepsilon , \delta )$-DDP when its critical connections are protected while the rest remains unperturbed. The effectiveness of our proposed method is demonstrated through extensive experiments on real-life graph datasets.

In social networks, the leave of critical users may significantly break network engagement, i.e., lead a large number of other users to drop out. A popular model to measure social network engagement is k-core, the maximal subgraph in which every vertex has at least k neighbors. To identify critical users, we propose the collapsed k-core problem: given a graph G, a positive integer k and a budget b, we aim to find b vertices in G such that the deletion of the b vertices leads to the smallest k-core. We prove the problem is NP-hard and in approximate. An efficient algorithm is proposed, which significantly reduces the number of candidate vertices. We also study the user leave towards the model of k-truss which further considers tie strength by conducting additional computation w.r.t. k-core. We prove the corresponding collapsed k-truss problem is also NP-hard and in approximate. An efficient algorithm is proposed to solve the problem. The advantages and disadvantages of the two proposed models are experimentally compared. Comprehensive experiments on nine real-life social networks demonstrate the effectiveness and efficiency of our proposed methods.

As one of the most representative cohesive subgraph models,k-core model has recently received significant attention in the literature. In this paper, we investigate the problem of the minimumk-core search: given a graphG, an integerkand a set of query verticesQ= {q}, we aim to find the smallestk-core subgraph containing every query vertexqϵQ.It has been shown that this problem is NP-hard with a huge search space, and it is very challenging to find the optimal solution. There are several heuristic algorithms for this problem, but they rely on simple scoring functions and there is no guarantee as to the size of the resulting subgraph, compared with the optimal solution. Our empirical study also indicates that the size of their resulting subgraphs may be large in practice. In this paper, we develop an effective and efficient progressive algorithm, namelyPSA, to provide a good trade-off between the quality of the result and the search time. Novel lower and upper bound techniques for the minimumk-core search are designed. Our extensive experiments on 12 real-life graphs demonstrate the effectiveness and efficiency of the new techniques.