CS Paper Radar

Polarity-Asymmetric Structural Calibration for Link Sign Prediction

Qiqi Gao, Wenzhuo Song, Xueyan Liu

cs.SI cs.LG ·submitted 2026-09-05 05:33 UTC · v1
top venuecode/data

Abstract

Link sign prediction (LSP) aims to infer the positive or negative polarity of unobserved links in signed networks. Signed Graph Neural Networks (SGNNs) usually rely on signed-graph structural priors, including structural balance and homophily-like similarity, to guide message passing and prediction. These priors describe population-level tendencies, not guarantees for individual target edges. Their failures are especially costly under severe sign imbalance, where errors on minority and locally conflicting relations are harder to detect and correct. We propose Polarity-Asymmetric Structural Calibration (PASC), a target-edge structural-prior calibration framework for signed link prediction. PASC constructs a structure-only prior representation, estimates a target-edge structural prior score, and compares this score with a local signed-context cue to derive a conflict residual. The residual calibrates signed attention aggregation, target-edge gated fusion, and regime-adaptive optimization. Experiments on five real-world signed network datasets show that PASC consistently achieves the best Macro-F1 among representative baselines, with competitive AUC, Binary-F1, and Micro-F1. Structural-shift experiments further suggest reduced dependence on dense-neighborhood and local-closure shortcuts. Source code is available at https://github.com/iqqGGGGGGG/PASC-for-LSP.

Comment
Accepted by IEEE ICDM 2026. 10 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Stability Analysis of Signed Graphs under Structural Perturbations

cs.LG ·2026-10-21 ·Ning Zhang, Li Zhang
top venue similarity 0.66
Abstract

Signed graph learning has emerged as a powerful framework for modeling networks with both positive and negative interactions. While graph-filter-based methods have achieved promising empirical performance on signed networks, their stability under edge perturbations remains less well understood. Existing stability analyses primarily focus on unsigned graphs and do not account for sign-flip perturbations. In this paper, we study the stability of signed graph filters under edge additions, deletions, and sign flips. Our theoretical analysis reveals how signed edge perturbations and node feature correlations jointly determine the learned representation stability. Based on this analysis, we propose a theory-guided perturbation strategy that selects structurally influential signed-edge modifications. Experiments on synthetic and real signed graphs show that the proposed method consistently induces larger embedding drift, polarity change, and downstream link prediction degradation than baselines. These results highlight the importance of \textit{sign-aware} and \textit{distribution-aware} stability analysis for signed graph learning.

0.40

Signed Graph Pre-Training and Prompt Learning

cs.LG ·2026-09-22 ·Zihan Mei, Rong Pan, Yuzhou Chen, Yixuan He
published similarity 0.60
Abstract · 26 pages, 3 figures, Accepted to Learning on Graphs Conference (LoG 2026)

Signed graphs arise in trust--distrust networks, financial correlation systems, biological interaction graphs, and many other domains in which edges can be positive or negative and may also be directed. While signed graph neural networks have improved task-specific learning, graph transfer learning on signed graphs remains underdeveloped. In this paper, we introduce TopoSIGN, a pioneer topology-guided graph pre-training and prompt learning framework for signed graphs. TopoSIGN combines a structural encoder built on the magnetic signed Laplacian with a novel persistent-homology branch that summarizes signed topology through Dowker-complex persistence images. The fused embeddings are then transferred to a prompt learning function. Experimental results on synthetic and real-world datasets demonstrate the efficacy of TopoSIGN in extracting useful structural information in signed graphs, as well as the adaptability and flexibility of the proposed general framework.

0.34

HARMONIA: Interpretable Graph Learning through Mixtures of Neural Bases

cs.AI stat.MLcs.LG ·2026-09-27 ·Quan D. Bui, Nguyen Do, An Nguyen Dang, Huyen Nguyen, Nhu Duc Minh Nguyen +1 more
similarity 0.58
Abstract

Existing interpretable graph additive models still face limitations in either computational scalability or modeling flexibility. In terms of structural modeling, previous approaches either face quadratic scaling costs or sacrifice explicit source-to-target contribution decomposition. In terms of feature components, they rely either on per-feature neural networks or on single shared bases with limited feature specialization. We address both problems by introducing HARMONIA: Interpretable Graph Learning through Mixtures of Neural Bases, an interpretable-by-design framework. For feature modeling, HARMONIA introduces a Mixture of Neural Bases (MoNB), which routes features to specialized basis experts, enabling parameter sharing without sacrificing feature-specific specialization. For structural modeling, HARMONIA uses Relative Random Walk Probabilities (RRWP) to capture multi-hop and multi-path relationships, and proposes Sparse RRWP Aggregation (SRA) to compute these interactions through sparse graph propagation without quadratic pairwise complexity. HARMONIA retains a simple additive form in which predictions decompose into feature responses modulated by structural influence. Empirically, HARMONIA achieves stronger explanation recovery than existing interpretable graph baselines while maintaining competitive predictive performance and scaling to graphs with millions of nodes. These results show that interpretable graph learning can remain both faithful and scalable without sacrificing predictive effectiveness.

0.21

Learning a Prior-Data Fitted Network for Graph Foundation Models via Structural Causal Model Priors

cs.LG ·2026-10-28 ·Ziwei Zhang, Tianyin Liao, Chunyu Hu, Ge Lan, Nuo Xu +5 more
similarity 0.58
Abstract

Graph Foundation Models (GFMs) have recently emerged as a promising paradigm for learning transferable representations across different graphs and domains. However, existing GFMs face notable limitations, including limited pre-training scale or reliance on aligning with textual information in Large Language Models (LLMs). To overcome these limitations, recent studies have drawn inspiration from prior-data fitted networks (PFNs), which learn from large synthetic datasets and support multi-domain prediction backed by causal learning. However, existing graph PFNs encounter severe difficulties in modeling causal relationships within and across node and edge sets, generating diverse graph structures, and designing suitable architectures that can learn from complex synthetic datasets. To address these challenges, we propose **GSCM-PFN** (Graph SCM-based Prior-Data Fitted Network), a graph PFN pre-trained on synthetic data generated from an SCM-based prior that jointly models nodes and graph topology. Specifically, we (1) design a joint feature-edge-label structural causal model (SCM) to guide synthetic graph generation and capture causal relationships within and across node and edge sets; (2) introduce prior-guided node-edge dependency modeling to instantiate diverse graph generation strategies, and prove that our SCM-based generation prior is more expressive than existing priors; and (3) propose a feature-permutation-invariant dual-path graph network with theoretical guarantees for learning from diverse synthetic graphs. Experiments on 23 real-world benchmarks show that GSCM-PFN outperforms both conventional GFMs and PFN-based GFMs, without utilizing real-world graph data for pre-training. Code: https://anonymous.4open.science/r/GSCM-PFN-A3A3/

0.19

AtlasULP: Domain-aware Universal Link Prediction via Relation Atlas

cs.LG ·2026-11-05 ·Yujing Liu, Yixin Liu, Yu Zheng, Lianhua Chi, Alan Wee-Chung Liew +2 more
similarity 0.57
Abstract

Link prediction (LP) is a widely applied task in graph learning. Conventional LP approaches typically follow a dataset-specific paradigm, requiring independent training for each graph and incurring high computational and maintenance costs in large-scale applications. Motivated by these limitations, recent work explores Universal Link Prediction (ULP), aiming to enable training-free inference on arbitrary unseen graphs. However, existing methods primarily rely on subgraph sampling strategies to construct universal representations, which are unable to capture higher-order information due to the exponential growth of higher-order neighborhoods. As a result, they often under-perform on graphs where long-range signals are essential, such as biological networks. Moreover, their prediction models are typically domain-agnostic and lack the ability to adapt to different graph domains, leading to limited generalization. To address these challenges, we propose an Atlas-based Universal Link Prediction framework (AtlasULP), which introduces the relation atlas to capture structural associations between node pairs from both global and local perspectives, enabling a comprehensive characterization of connectivity signals across diverse graph domains. Building upon this representation, we develop a domain-guided prompting ULP model, which generates domain-aware prompt tokens from contextual structures and performs prompt-guided in-context prediction for adaptive link inference. Extensive experiments demonstrate that AtlasULP consistently outperforms state-of-the-art methods across diverse graph domains.

0.19

SUCRe: Selective Uncertainty-Aware Contrastive Representation for Graph Transfer Learning

cs.GR ·2026-09-25 ·Mingcan Wang, Junchang Xin, Zhongming Yao, Bing Tian Dai, Kaifu Long +1 more
similarity 0.56
Abstract

Graph transfer learning (GTL) provides a promising paradigm for adapting knowledge from source graphs with sufficient labels to label-scarce target graphs. However, existing approaches often assume that transferred knowledge is uniformly reliable, ignoring the different transferability of samples caused by structural and distribution shifts across graphs. This limitation leads to negative transfer and unnecessary computational overhead. In this work, we propose SUCRe, a selective uncertainty-aware contrastive representation method for GTL. The key idea is to selectively adapt and transfer graph knowledge according to its estimated reliability. Specifically, we introduce structure-aware entropy-based matching discrepancy, which jointly models feature uncertainty and structural coherence to ensure accurate feature adaptation between graphs. Moreover, we develop a domain-aware semi-hard negative sampling strategy that constructs informative contrastive sets by filtering unreliable cross-domain relationships, reducing computational redundancy while enhancing representation discrimination. Extensive experiments on graph transfer benchmarks demonstrate that SUCRe achieves competitive performance with improved efficiency.

0.10

Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction

cs.LG cs.GT ·2026-09-28 ·Chen Shao, Donald Loveland, Tobias Käfer, Danai Koutra
similarity 0.56
Abstract · 10 pages, figure 7

Graph Neural Networks (GNNs) are effective for learning node and link embeddings through permutation-equivariant aggregation. However, standard GNNs collapse automorphic nodes, i.e., those with identical structural roles (or orbits) into indistinguishable representations, leading to the node automorphism problem. This collapse limits their expressive power and degrades link prediction performance. Existing approaches to characterize GNN expressiveness rely primarily on Weisfeiler-Lehman (WL) analyses, but these methods are typically qualitative and often misaligned with empirical results. To address this gap, we begin by introducing a novel quantitative framework to assess GNN expressiveness for link prediction. We first formalize edge-level automorphism through edge orbits, which capture the set of structural role pairs for nodes that share a link. Then, we introduce the edge automorphism ratio (EAR), a scalar metric that quantifies a GNN's ability to distinguish links in a given graph. We empirically demonstrate that EAR correlates strongly with performance, validating its practical benefit. Building on this insight, we design EDGE-ORBIT EQUIVARIANT GRAPH NEURAL NETWORK (EO-GNN), a GNN architecture that addresses automorphism collapse while preserving equivariance and incurring minimal computational overhead. EO-GNN accomplishes this through two core designs combined with WL-based node hashes: (i) automorphism-aware dropouts and (ii) subgraph orbit-biased aggregation. Empirical evaluations on synthetic and real graphs show improvements of up to 42.36% and 28.44%, respectively, in predicting links in scenarios with high automorphism.

0.22

Towards One-for-All Foundation Model for Attributed Graph Clustering

cs.LG cs.AI ·2026-10-06 ·Yunhui Liu, Xudong Jin, Kang Zhang, Danshuo An, Yu Xing +3 more
code/data similarity 0.56
Abstract

Attributed graph clustering aims to discover node groups by jointly exploiting node attributes and graph topology, yet its unsupervised nature makes model selection and adaptation inherently difficult. Existing methods typically train and tune a separate model for each input graph, leading to costly and fragile pipelines that often fail to transfer across graphs with different feature spaces, structural patterns, and attribute-structure correlations. In this paper, we study a one-for-all alternative: can a single model be trained once and directly applied to diverse attributed graphs without graph-specific training, fine-tuning, or hyperparameter search? We propose OFAG, a foundation model for attributed graph clustering. Building upon Prior-data Fitted Networks, OFAG learns a reusable clustering inference strategy from synthetic attributed graphs generated under broad priors over latent clusters, node attributes, and graph structures. To handle incompatible feature spaces across graphs, OFAG adopts a dimension-agnostic signal-wise graph encoder that treats each feature channel as a graph signal and models its response to shared graph filters. The model is trained with a hyperspherical clustering objective, producing clustering-friendly node representations in a single forward pass at inference time. On ten datasets, one frozen OFAG model achieves the best mean performance and average rank across NMI, ACC, ARI, and F1, while completing all ten datasets in 12.43 minutes total---over 6* faster than the second-fastest baseline and nearly 28* faster than the second-best on clustering quality. Our code and pretrained checkpoint are available at https://github.com/Cloudy1225/OFAG, allowing practitioners to directly apply OFAG to their own attributed graph datasets without additional training or tuning.

0.57