{"ID":2823097,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.01207","arxiv_id":"2601.01207","title":"Sparse Bayesian Message Passing under Structural Uncertainty","abstract":"Semi-supervised learning on real-world graphs is frequently challenged by heterophily, where the observed graph is unreliable or label-disassortative. Many existing graph neural networks either rely on a fixed adjacency structure or attempt to handle structural noise through regularization. In this work, we explicitly capture structural uncertainty by modeling a posterior distribution over signed adjacency matrices, allowing each edge to be positive, negative, or absent. We propose a sparse signed message passing network that is naturally robust to edge noise and heterophily, which can be interpreted from a Bayesian perspective. By combining (i) posterior marginalization over signed graph structures with (ii) sparse signed message aggregation, our approach offers a principled way to handle both edge noise and heterophily. Experimental results demonstrate that our method outperforms strong baseline models on heterophilic benchmarks under both synthetic and real-world structural noise.","short_abstract":"Semi-supervised learning on real-world graphs is frequently challenged by heterophily, where the observed graph is unreliable or label-disassortative. Many existing graph neural networks either rely on a fixed adjacency structure or attempt to handle structural noise through regularization. In this work, we explicitly...","url_abs":"https://arxiv.org/abs/2601.01207","url_pdf":"https://arxiv.org/pdf/2601.01207v1","authors":"[\"Yoonhyuk Choi\",\"Jiho Choi\",\"Chanran Kim\",\"Yumin Lee\",\"Hawon Shin\",\"Yeowon Jeon\",\"Minjeong Kim\",\"Jiwoo Kang\"]","published":"2026-01-03T15:16:12Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"stat.ML\"]","methods":"[\"Graph Neural Network\"]","has_code":false}