PaperlayerView exact revision on arXiv

Source-linked AI summary

Polarity-Asymmetric Structural Calibration for Link Sign Prediction

Qiqi Gao, Wenzhuo Song, Xueyan Liu

arXiv:2609.05896v1cs.SIcs.LG

TL;DR

Structural priors in signed link prediction capture population tendencies, but can conflict with individual target-edge context, especially under polarity imbalance. PASC calibrates edge-level reliance on those priors using a conflict residual across aggregation, fusion, and optimization. On five real-world signed networks, it achieves the best Macro-F1 with competitive overall metrics.

  • Problem

    Structural priors may not match individual target-edge polarity, and severe sign imbalance makes minority or locally conflicting errors harder to detect and correct.

    Source: §I · p. 1

  • Method

    PASC compares a target-edge structural-prior score with local signed context and uses the conflict residual to calibrate signed attention, gated fusion, and regime-adaptive optimization.

    Source: §I · p. 2

  • Results

    Across five real-world signed-network datasets, PASC consistently achieves the best Macro-F1 while maintaining competitive AUC, Binary-F1, and Micro-F1.

    Source: §I · p. 2

  • Takeaways & Limitations

    Under the tested structural-shift protocols, PASC shows reduced dependence on dense-neighborhood and local-closure shortcuts.

    Source: §V · p. 10

Abstract

from arXiv · show

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.

I. INTRODUCTION

Signed structural priors capture population-level tendencies but can conflict with local evidence for individual target edges, a problem magnified by polarity imbalance. PASC calibrates each edge’s reliance on those priors using a conflict residual, and reports strong class-balanced results across five benchmarks.

I. INTRODUCTION

  • Structural-balance patterns can disagree with edge signs: for the (+, −) prior pattern, 70.8% of Wiki-RfA edges are positive, compared with 63.5% on Bitcoin-Alpha and 53.5% on Epinions.Structural priors remain useful, but their reliability varies across target edges.Source: §I · p. 1
  • Positive edges outnumber negative edges by 3.4 to 14.7 times across five datasets, making minority and locally conflicting errors less visible in global metrics such as AUC or Micro-F1.The stated challenge is estimating when to trust a structural prior for a target edge and calibrating it under local signed context.Source: §I · p. 1
  • Existing approaches extract richer structures or suppress and reweight unreliable ones, but do not directly calibrate each target edge’s reliance on priors under its local context.PASC instead treats signed-graph patterns as useful but imperfect priors and asks when each target edge should trust them.Source: §I · p. 2
  • Across five real-world signed-network datasets, PASC achieves the best Macro-F1 while maintaining competitive AUC, Binary-F1, and Micro-F1.Degree-Shift and Structural-Shortcut-Shift experiments also show reduced dependence on structural shortcuts.Source: §I · p. 2
  • For small-scale graphs PASC-S reweights edges with larger prior-context mismatch; for large-scale graphs PASC-H uses contrastive supervision on structurally matched, context-opposite edges.These variants implement the same residual-driven calibration under different graph-scale settings.Source: §I · p. 2
  • PASC defines a conflict residual from the gap between a structural-gradient-based prior score and a local signed-context cue, using it as a lightweight, training-free structural signal.The residual drives calibration across signed attention, target-edge gated fusion, and regime-adaptive optimization.Source: §I · p. 2

II. RELATED WORK

Related work spans signed graph neural networks, higher-order and subgraph methods, and graph debiasing. The included methodology overview frames PASC as target-edge calibration, and the problem definition specifies link-sign prediction on a signed graph.

A. Signed Graph Neural Networks

  • SGNN aggregation can overemphasize dominant structural patterns, making minority or structurally conflicting edges harder to model even when global ranking metrics remain high.Source: A. Signed Graph Neural Networks · p. 2

B. Subgraph and High-Order Heuristic Methods

  • Higher-order and subgraph methods add structural expressiveness, but can incur computational and scalability costs and may have too few patterns in minority-polarity or locally heterogeneous regions.Source: B. Subgraph and High-Order Heuristic… · p. 3

C. Imbalanced Learning and Debiasing on Graphs

  • Debiasing methods filter, reweight, or explain structures, but deviations from common priors may be informative minority or locally conflicting edges rather than noise.This motivates calibrating each target edge’s structural-prior reliance rather than treating deviations mainly as unreliable structures.Source: C. Imbalanced Learning and Debiasing… · p. 3

III. METHODOLOGY

  • PASC estimates a target-edge prior score, compares it with local signed context, and uses the resulting residual to guide aggregation and feature fusion.The same edge-level calibration signal is injected into node-level message passing before node representations are reassembled for target-edge prediction.Source: §III · p. 3

A. Problem Definition

  • Link sign prediction uses a signed graph with positive and negative edge sets to predict the sign between a target node pair.The implementation symmetrizes originally directed edges, so edge direction is not modeled.Source: A. Problem Definition · p. 3

B. Structural Prior Estimation and Residual-Guided Aggregation

PASC derives structural-only features and a structural-gradient-based prior score for each target edge, then compares that score with local signed context to guide message passing. The gradient represents local structural variation and acts as a proxy for less predictable prior reliability.

B. Structural Prior Estimation and Residual-Guided Aggregation

  • The conflict residual is the gap between an edge’s structural prior score and observed local signed context, and serves as an edge-level bias for positive and negative signed attention.The architecture overview shows this residual guiding aggregation, gated fusion, and regime-adaptive optimization.Source: B. Structural Prior Estimation and… · p. 3, Figure 2 · p. 4

1) Structure-Only Prior Representation:

  • PASC builds node features from the signed adjacency matrix without using target-edge labels or local context, while retaining edge signs.Source: 1) Structure-Only Prior Representation · p. 3
  • Truncated SVD supplies the top-r structural bases as the initial node features.The decomposition can use sparse solvers or randomized low-rank SVD, with preprocessing complexity described as approximately linear in observed edges.Source: 1) Structure-Only Prior Representation · p. 3
  • The structural gradient compares structure-only features aggregated over one-hop and two-hop neighborhoods; near-zero values indicate smooth neighborhoods, while large magnitudes indicate transitions such as community boundaries or bridging nodes.Source: 1) Structure-Only Prior Representation · p. 3
  • PASC uses the structural gradient as a proxy for less predictable prior reliability, concatenating the target nodes’ gradients to estimate their edge’s prior score.The score network uses structural features rather than local signed context or the target edge’s sign label.Source: 1) Structure-Only Prior Representation · p. 4

2) Residual-Guided Attention Aggregation:

PASC uses the mismatch between structural expectation and observed local signed context as an edge-level attention calibration signal. Residual-guided attention adjusts neighbor aggregation, separately for positive and negative neighborhoods.

2) Residual-Guided Attention Aggregation:

C. Target-Edge Gated Fusion

PASC uses a target-edge gate to tune how much residual-calibrated local context is added to structural representations, with the conflict residual indicating prior reliability.

C. Target-Edge Gated Fusion

  • The conflict residual measures structural-prior reliability and guides how much local context the target edge should use.PASC applies this calibration at fusion with a target-edge gate.Source: C. Target-Edge Gated Fusion · p. 5
  • A single gate value between 0 and 1 scales the context added to the structural representations of both endpoint nodes.Larger values inject more calibrated context; smaller values keep the fused representations closer to the structural prior.Source: C. Target-Edge Gated Fusion · p. 5
  • The gate takes both endpoints’ base and context representations as input, and their final node representations are concatenated for edge-level prediction.The gate is distinct from the neighbor-normalized attention weights used earlier.Source: C. Target-Edge Gated Fusion · p. 5

D. Regime-Adaptive Conflict-Residual Optimization

PASC adapts conflict-residual optimization to graph scale: it uses soft reweighting for small graphs and residual-contrastive twin supervision for large graphs.

D. Regime-Adaptive Conflict-Residual Optimization

  • PASC selects soft residual-aware reweighting for small graphs and residual-contrastive twin supervision for large graphs, using graph scale as a proxy for candidate availability.Large residuals indicate greater mismatch between the structure-derived prior and local signed context.Source: D. Regime-Adaptive Conflict-Residual… · p. 5

1) Soft Reweighting for Small-Scale Signed-Topology Regimes:

  • PASC-S keeps graph topology unchanged and emphasizes edges where disagreement indicates that the structural prior is less reliable.Its reweighting is soft and does not treat the structural prior score as a ground-truth sign.Source: 1) Soft Reweighting for Small-Scale… · p. 5
  • PASC-S weights the observation loss over training edges using binary cross-entropy on their observed labels.The reweighting coefficient grows with the magnitude of the conflict residual.Source: 1) Soft Reweighting for Small-Scale… · p. 5

2) Residual-Contrastive Twin Supervision for Large-Scale Signed-Topology Regimes:

For large-scale graphs, PASC-H matches edges with similar structural-prior scores but opposite local contexts, then uses the matched polarity for auxiliary supervision.

2) Residual-Contrastive Twin Supervision for Large-Scale Signed-Topology Regimes:

  • PASC-H finds structural twins with similar prior scores but opposite observed context, using the target edge itself as fallback when no candidate qualifies.A threshold δ limits candidate matching.Source: 2) Residual-Contrastive Twin… · p. 5
  • Within the candidate set, PASC-H selects the twin most similar in initial structural features and structural-gradient representations.The matching uses a distance function over edge-level feature concatenations.Source: 2) Residual-Contrastive Twin… · p. 6
  • PASC-H uses a conditional decoder for two auxiliary paths that share endpoint base representations but differ in context and supervised label.The twin’s observed polarity supplies the switched-context label.Source: 2) Residual-Contrastive Twin… · p. 6
  • Pairing similar prior scores with opposite contexts holds the prior estimate approximately fixed and encourages modeling polarity variation with prior–context mismatch.The paper states this is intended to improve robustness in large-scale signed graphs.Source: 2) Residual-Contrastive Twin… · p. 6
  • With sparse adjacency, truncated SVD and structural-gradient preprocessing each cost O(r|Etrain|), while residual-guided attention adds only a scalar bias per aggregation edge.PASC-H bounds candidate matching using score buckets.Source: 2) Residual-Contrastive Twin… · p. 6

IV. EXPERIMENTS

The experiments assess PASC’s benchmark performance, the behavior of its optimization variants, the contribution of its components, sensitivity to auxiliary-loss weights, and robustness under structural shift.

  • RQ1 compares PASC’s overall and class-balanced link sign prediction performance with representative methods.Source: §IV · p. 6
  • RQ2 examines how PASC-S and PASC-H behave across small- and large-scale signed-graph regimes.Source: §IV · p. 6
  • RQ3 evaluates the contributions of residual-guided aggregation, target-edge gated fusion, and regime-adaptive optimization.Source: §IV · p. 6
  • RQ4 tests PASC-H’s sensitivity to the weights of its original-context and switched-context auxiliary supervision.Source: §IV · p. 6
  • RQ5 evaluates PASC’s robustness under structural-shift protocols.Source: §IV · p. 6

A. Experimental Setup

Experiments use five imbalanced signed-network benchmarks and compare PASC with representative baselines. PASC attains the best Macro-F1 on every dataset while remaining competitive on other reported metrics.

A. Experimental Setup

  • The five benchmarks cover trust, distrust, support, and opposition relations across Bitcoin-Alpha, Bitcoin-OTC, Wiki-RfA, Slashdot, and Epinions.Their positive-to-negative edge ratios range from 3.4:1 to 14.7:1; Table II presents dataset statistics.Source: A. Experimental Setup · p. 6, Table II · p. 6
  • All datasets use polarity-stratified edge splits in an 8:1:1 train/validation/test ratio under a static transductive setting, with a fixed node set across the splits.To avoid information leakage, structure-dependent preprocessing is fitted only on the training graph; validation and test edges are held out from these steps.Source: A. Experimental Setup · pp. 6–7
  • Macro-F1 averages class-specific F1 scores equally, whereas AUC, Binary-F1, and Micro-F1 can obscure minority-polarity performance under imbalance.Source: A. Experimental Setup · p. 7

B. Overall Performance Comparison

  • PASC achieves the best Macro-F1 on all five datasets while remaining competitive on AUC, Binary-F1, and Micro-F1.On Wiki-RfA, its Macro-F1 gain over the second-best baseline is 2.54%, versus 0.47% for Micro-F1 and 0.01% for Binary-F1.Source: B. Overall Performance Comparison · p. 7

C. Variant Adaptability Analysis

PASC-S performs best on the two small Bitcoin networks, while PASC-H performs best on the three larger benchmarks. Ablations show nonzero component contributions, and PASC-H is stable across tested loss-weight settings.

C. Variant Adaptability Analysis

  • PASC-S is best on both small Bitcoin networks, while PASC-H is best on Wiki-RfA, Slashdot, and Epinions.PASC-H’s stronger supervision yields 2.75% lower Macro-F1 than PASC-S on Bitcoin-Alpha; the variants remain within 0.69% Macro-F1 on large-scale graphs.Source: C. Variant Adaptability Analysis · p. 7, Figure 3 · p. 7

D. Ablation Study

  • Removing any component causes nonzero degradation; drops reach 2.11% in Macro-F1 on small-scale Bitcoin-Alpha, while large-scale Macro-F1 drops stay below 0.7%.Auxiliary supervision has the largest Macro-F1 drops on Slashdot (0.66%) and Epinions (0.33%); Figure 4 reports AUC and Macro-F1 degradation when components are removed.Source: D. Ablation Study · p. 8, Figure 4 · p. 8

E. Hyperparameter Sensitivity Analysis

F. Structural-Shift Robustness Analysis

Under the tested degree- and structural-shortcut-shift protocols, PASC achieves strong Macro-F1 results and shows reduced dependence on dense neighborhoods and local-closure shortcuts. The conclusion describes a shared conflict residual that calibrates aggregation, fusion, and optimization.

F. Structural-Shift Robustness Analysis

V. CONCLUSION

  • PASC compares target-edge structural-prior scores with local signed-context cues; one conflict residual guides attention aggregation, gated fusion, and regime-adaptive optimization.Source: §V · p. 10
  • Future work will explore more efficient residual estimation and extend PASC to heterogeneous and dynamic signed networks.Source: §V · p. 10

Related papers

Loading 2609.05896v1…