Using a connected dominating set (CDS) as a virtual backbone of a wireless sensor network can effectively save energy, reduce interference, and extend network lifespan, which also has wide applications in geometric routing algorithms and network topology control. A fault-tolerant virtual backbone can be modeled as a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-connected <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>-dominating set (abbreviated as a <inline-formula> <tex-math notation="LaTeX">$(k,m)$ </tex-math></inline-formula>-CDS) in a graph. In this paper, we present an approximation algorithm for the minimum weight <inline-formula> <tex-math notation="LaTeX">$(2,m)$ </tex-math></inline-formula>-CDS problem in a general graph, which achieves approximation ratio at most <inline-formula> <tex-math notation="LaTeX">$5.164H(n-1)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$H(\gamma)=\sum _{i=1}^{\gamma }1/i$ </tex-math></inline-formula> is the <inline-formula> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula>th Harmonic number and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the number of nodes in the graph. This ratio improves previously best known ratio by a factor of at least 3.87.
Jiao Zhou, Zhipeng Cai, Xiaohui Huang et al.· IEEE Transactions on Network...· 0 citations
With the growing global emphasis on data privacy protection, particularly the enforcement of the “right to be forgotten” under the GDPR, effectively deleting private information from models has become an urgent challenge. Graph-structured data presents a particularly challenging unlearning scenario due to its non-Euclidean nature and strong relational dependencies, which are prevalent in real-world applications such as social and recommendation systems. To address this issue, graph unlearning has been introduced to eliminate the influence of deleted data on models while preserving their overall performance. The effectiveness of graph unlearning is typically evaluated by three key metrics: model performance, unlearning efficiency, and robustness against membership inference attacks, which together determine the overall quality of an unlearning method. Existing graph unlearning methods fall into exact and approximate regimes. Most studies focus on edge/node-level unlearning, and existing attempts at feature-level unlearning remain limited. Exact unlearning methods that adopt the SISA partition and retraining paradigm may inadvertently reintroduce the features intended to be unlearned during the aggregation phase, thereby leading to incomplete unlearning. Approximate methods, on the other hand, often incur excessive information loss in feature-level removal, which degrades predictive accuracy. Accordingly, we propose a graph unlearning framework specifically designed for feature-level unlearning, consisting of two main stages. In the first stage, we zero out the features of the unlearned nodes at each layer to block their propagation through the GNN, thereby reducing their influence on neighboring node representations. In the second stage, we induce misclassification of the unlearned nodes to progressively degrade model representations and learned knowledge associated with them, enabling more thorough feature-level unlearning. Experiments on multiple graph datasets and models demonstrate that our method achieves favorable overall unlearning performance in most settings, offering a balanced trade-off between accuracy, unlearning efficiency, and unlearning effectiveness.
Zhiyu Chen, Jiaquan Liang, Qi Luo et al.· Mathematics· 0 citations
