Certified Signed Graph Unlearning

Graph Attributed Unlearning via Propagation Suppression and Knowledge Dissipation

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.

SigFJProp: Lightweight and Scalable Signed Graph Learning via Opinion Dynamics

Learning on signed graphs poses unique challenges due to the presence of both positive and negative links, which represent complex social dynamics such as trust and conflict. While existing signed graph neural networks (SGNNs) have achieved promising results, most rely on deep, multi-hop propagation architectures that suffer from scalability issues. In this work, we revisit message passing from the perspective of opinion dynamics, and propose SigFJProp, a novel and lightweight SGNN framework inspired by the Friedkin–Johnsen model. SigFJProp models signed message propagation as a discrete-time opinion update process, whose equilibrium state admits a closed-form solution involving the signed forest matrix. To make this computation tractable on large-scale graphs, we introduce Expansion Forest Sampling, a linear-time approximation method tailored for signed networks. Our approach decouples neural representation learning from propagation dynamics, enabling efficient and interpretable learning. Experimental results on seven benchmark datasets, including one with over 750K nodes and 10M edges, demonstrate that SigFJProp achieves competitive or superior performance compared to state-of-the-art methods, while significantly reducing computational overhead. The code is available at https://github.com/SunYubo23/SigFJProp.

Subgraph Filtering for Fair Graph Neural Networks

Graph neural networks (GNNs) can exhibit unfair behavior even when sensitive attributes are excluded from node features, because graph topology and message passing propagate group-correlated signals under sensitive homophily. Existing fairness-aware GNN methods mainly constrain representations or prediction distributions at a global level, without explicitly controlling the local structural pathways through which biased information propagates during aggregation. We propose Subgraph Filtering for Fair Graph Neural Networks (SF-GNN), a lightweight and architecture-agnostic framework that mitigates structural bias at its source. SF-GNN identifies bias-prone edges by combining sensitive homophily with structural propagation amplifiers, including hub participation and triadic closure. It then incorporates stochastic edge filtering into each message-passing step to selectively downweight or remove these edges while preserving the remaining graph structure. Training further incorporates a statistical-parity regularizer with a warm-up schedule to stabilize optimization. Experiments on five benchmark datasets show that SF-GNN achieves consistent fairness improvements while maintaining competitive predictive performance, leading to a better fairness--accuracy trade-off than recent fairness-aware GNN baselines.

EdgeRefine: Privacy-Utility Balance for Graphs via Jaccard Sampling under Edge Differential Privacy

Graph Neural Networks (GNNs) have shown considerable success in learning from graph-structured data, but their use in privacy-sensitive areas remains difficult because graph structure can leak sensitive link information. To satisfy edge-level differential privacy, a common approach is to inject noise into all elements of the graph's adjacency matrix, thereby obfuscating the existence of any single edge. However, stronger privacy requires more noise, and excessive noise reduces utility, making the privacy-utility balance a major barrier to practical privacy-preserving graph learning. To address this issue, we propose EdgeRefine, a local differential privacy framework that improves this trade-off through adaptive edge refinement. EdgeRefine first estimates edge-existence probabilities using Jaccard similarity and ranks edges for noisy edge removal. To ensure the sparsity and reliability of the final graph, it uses the privacy budget $\epsilon$ to determine the ratio of true to false edges, samples them separately based on this probability ranking, and controls the total number of edges with a separate sampling rate $k$. Extensive experiments show that EdgeRefine achieves accuracy comparable to the noise-free baseline and substantially outperforms other privacy-preserving methods across datasets and GNN architectures. Under privacy budget $\epsilon = 2.5$, EdgeRefine improves node classification accuracy over state-of-the-art baselines by 17.8\% on ACM under GAT and 19.7\% on Cora under GCN. In graph classification, it achieves an average accuracy degradation of around 5\% compared to the noise-free baseline. Under graph reconstruction attacks, EdgeRefine maintains relative absolute error levels above 1 across all privacy budgets, averaging 1.962 on Cora and 1.472 on AMAP, indicating strong resilience against privacy leakage.

Nonlinear Laplacians Improve Signed-Directed Graph Learning

This work introduces a non-linear Laplacian operator specific to signed and directed networks (NLSD) and proposes an efficient spectral GNN framework (NLSD-GNN), which not only integrates signed and directional data effectively but also achieves superior performance across diverse datasets.

Structure-Aware Graph Contrastive Learning via Degree-Preserving Rewiring