Aug 2026· ACM Transactions on Intelligent Systems and Technology· 0 citations· 44 references
TL;DR
This work provides theoretical guarantees for the selective blocking rule by deriving the signed-versus-blocked decision boundary, separating signed-matrix effects from nonnegative block-operator spectral arguments, and showing when adaptive blocking preserves class-dependent components.
Abstract
Graph Neural Networks (GNNs) deliver strong performance through message passing (MP), yet they can become fragile when graphs contain many heterophilic links or when edge types are predicted incorrectly. Earlier analyses suggest that signed message propagation can reduce over-smoothing when the edge misclassification rate is low. However, many such analyses condition on accurately identified edge types and blur the distinction between neighbor propagation and self-retention. This work re-examines these assumptions and shows that under high uncertainty in edge labels, message passing can reduce node distinguishability even when signed edge weights are applied. The central insight is that uncertain edges should not always be propagated: it can be preferable to adaptively block a message when the estimated edge-type error outweighs the expected gain from signed propagation. Concretely, we analyze neighbor propagation without treating self-loops as edge-type observations, use a row-normalized operator for the neighbor process, and estimate two latent reliability factors during training: the local homophily and the edge classification error rate. To avoid leakage between reliability estimation and model selection, the edge error rate is estimated from a separate calibration split or from a train-only proxy, while validation labels are reserved for hyperparameter and checkpoint selection. We provide theoretical guarantees for the selective blocking rule by deriving the signed-versus-blocked decision boundary, separating signed-matrix effects from nonnegative block-operator spectral arguments, and showing when adaptive blocking preserves class-dependent components. Experiments on homophilic, heterophilic, and large-scale graphs show that the proposed strategy consistently improves signed GNN backbones and remains competitive with strong heterophily-oriented baselines. Compared with the UAI 2025 conference version [11], this journal version adds an extension analysis, tightened derivations, a leakage-free calibration protocol, and expanded empirical results.
Subgraph Filtering for Fair Graph Neural Networks is proposed, a lightweight and architecture-agnostic framework that mitigates structural bias at its source and achieves consistent fairness improvements while maintaining competitive predictive performance, leading to a better fairness--accuracy trade-off than recent fairness-aware GNN baselines.
Haohui Lu, Ji-Yuan Tian, Fangyu Zhou et al.· 0 citations
HeAD-CP is proposed, a family of node-wise diffusion variants whose coefficients are determined by a label-free local-homophily estimate derived from the GNN softmax, which are most effective at extreme heterophily, intermediate heterophily, and moderate-to-high homophily, respectively, and all preserve the marginal coverage guarantee.
Noise Corruption is introduced, a Noise Corruption-based explanation framework, which perturbs each message through matched-norm random-direction corruption while preserving the expected squared message norm, and NICE, a Noise Corruption-based explanation framework, which learns a Stochastic Restoration Boundary under NC-induced uncertainty, balancing target-prediction restoration against compactness.
Ziluowen Luo, Jun Yin, Ruochen Liu et al.· 0 citations
Graph neural networks learn from relational structure but can be sensitive to edge-level noise. We study a hybrid graph classifier that combines a message-passing branch (Graph Isomorphism Network, GIN) with a topological branch based on extended persistence diagrams and PersLay embeddings. Training optionally uses a paper-specific hinge penalty motivated by stable persistence-diagram representations and Lipschitz regularity, which we abbreviate as “HK-inspired.” On six TUDataset benchmarks, we compare five ablations (Full, GIN+PersLay, GIN + HK, GIN only, PersLay only) and measure robustness as accuracy drop under 10% random edge removal at test time, with persistence diagrams fixed from the original graphs; we also report targeted perturbations on MUTAG and PROTEINS and runtime on all six datasets. The regularized configurations reduce relative accuracy degradation where GIN-only is sensitive, particularly on smaller molecular and protein graphs, but do not consistently maximize clean or perturbed accuracy. On large social-network benchmarks, robustness differences are small and clean accuracy is the main differentiator. Adding PersLay to GIN can improve accuracy on several datasets, while PersLay alone performs worst. Training the full model increases per-epoch cost relative to GIN-only, with most overhead during training rather than inference. Overall, the results support a conditional empirical conclusion: combining structure, topology, and stability-oriented training can improve robustness under specified structural perturbations, with dataset-dependent accuracy–stability trade-offs rather than universal guarantees.
Jelena Losic, Charles Fanning· PLOS Complex Systems· 0 citations
Graph Neural Networks (GNNs) have exhibited extraordinary performance in data mining. The success depends on the message passing mechanism, which is consistent with the homophily assumption that adjacent nodes share similar behaviors. However, the connected nodes in real-world graphs often show dissimilar behaviors, which is presented as the heterophily problem. A series of works proposed various models to solve the heterophily problem. They usually assume that the neighborhood distribution of nodes with the same class tends to be similar, while distinguishable from nodes of different classes. However, our experiments discovered that many nodes belonging to different classes share the same neighbor distribution in the mainstream datasets. The performance of GNN also degrades in these conflicting nodes. To detect the conflicting nodes and improve their prediction accuracy, we propose the Conflicting Node Discrimination GNN (CNDGNN). It firstly detects the possible conflicting nodes with the same neighbor distribution according to the selected high-quality pseudo-label. Then it estimates the class type of conflicting nodes with the same neighbor distribution through nodes' high-order neighbor distributions and original features, and the aggregation weights are learned to assign positive weights for nodes of the same class type and negative weights for nodes of different classes. The theoretical analysis proves that CNDGNN performs better than GCN in the conflicting nodes and explores the key design view when solving the conflicting node problem. The experiments demonstrate the effectiveness of our method in the mainstream datasets and verify that our method performs better in conflicting nodes.
Wenjun Wang, Xin Cao, Yawen Li et al.· Proceedings of the 32nd ACM...· 0 citations
Extensive experiments ensure that FHGE consistently outperforms state-of-the-art baselines and demonstrate the power of fuzzy-driven learning in improving graph embedding quality and establish FHGE as a promising solution for real-world link prediction tasks.
Linh Nguyen Thi My, Tham Vo· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
