GegenNet: Spectral Convolutional Neural Networks for Link Sign Prediction in Signed Bipartite Graphs

Hewen Wang, Renchi Yang, Xiaokui Xiao

Abstract

Given a signed bipartite graph (SBG) G with two disjoint node sets U and V, the goal of link sign prediction is to predict the signs of potential links connecting U and V based on known positive and negative edges in G. The majority of existing solutions towards link sign prediction mainly focus on unipartite signed graphs, which are sub-optimal due to the neglect of node heterogeneity and unique bipartite characteristics of SBGs. To this end, recent studies adapt graph neural networks to SBGs by introducing message-passing schemes for both inter-partition (UxV) and intra-partition (UxU or VxV) node pairs. However, the fundamental spectral convolutional operators were originally designed for positive links in unsigned graphs, and thus, are not optimal for inferring missing positive or negative links from known ones in SBGs. Motivated by this, this paper proposes GegenNet, a novel and effective spectral convolutional neural network model for link sign prediction in SBGs. In particular, GegenNet achieves enhanced model capacity and high predictive accuracy through three main technical contributions: (i) fast and theoretically grounded spectral decomposition techniques for node feature initialization; (ii) a new spectral graph filter based on the Gegenbauer polynomial basis; and (iii) multi-layer sign-aware spectral convolutional networks alternating Gegenbauer polynomial filters with positive and negative edges. Our extensive empirical studies reveal that GegenNet can achieve significantly superior performance (up to a gain of 4.28% in AUC and 11.69% in F1) in link sign prediction compared to 11 strong competitors over 6 benchmark SBG datasets.

Introduction

Signed Bipartite Graphs (SBGs) represent relationships between two distinct sets of entities—such as users and items—where interactions can be positive (likes, trust) or negative (dislikes, distrust). Predicting these "signs" is crucial for recommendation systems and sentiment analysis. However, a major gap exists in current solutions: most existing Graph Neural Networks (GNNs) are designed for unipartite unsigned graphs. When adapted for SBGs, these models typically rely on standard message-passing (monomial bases) that act as simple low-pass filters, failing to capture the complex spectral signals inherent in signed relationships.

The Challenge of Spectral Filtering in SBGs

The authors identify that link signs in SBGs are often encoded in high-frequency spectral signals that standard GNNs ignore. Furthermore, standard GNNs use monomial bases ($x, x^2, x^3...$), which are not orthogonal and can lead to numerical instability or "over-smoothing." Positive links in SBGs require a filter that can handle complex, non-monotonic relationships in the spectral domain—an "ideal" curve that standard models cannot fit.

The GegenNet Architecture

GegenNet introduces three primary technical innovations to address these limitations:

1. Gegenbauer Polynomial Filters

GegenNet recasts link sign prediction as a spectral curve-fitting problem. By utilizing the Gegenbauer polynomial basis, the model can approximate complex spectral signals much more accurately than standard filters like those in GCN or APPNP. The orthogonality of Gegenbauer polynomials provides a more robust and expressive mathematical foundation for the filter, allowing it to capture both low- and high-frequency information.

Comparison of spectral filters: GegenNet (Gegenbauer) vs. baselines against the 'Ideal' curve across different datasets and spectral components.

2. Spectral Feature Initialization

Instead of starting with random noise, GegenNet initializes node features using a sophisticated spectral decomposition. It combines eigenvectors from the graph Laplacian (capturing inter-partition relations) with top singular vectors from the bi-adjacency matrix (capturing intra-partition similarities), effectively addressing node heterogeneity.

3. Sign-aware Architecture

The model stacks multiple layers that process positive and negative edge information separately and alternately. This allows the network to learn the nuanced interplay between "friends" and "enemies" across the bipartite partitions.

Experimental Results

The model was evaluated on six diverse real-world SBG datasets, including Amazon, Senate, and the highly sparse Bonanza dataset. GegenNet consistently yielded the highest AUC and F1-scores across all datasets, outperforming 11 strong competitors. Notably, on the sparse and imbalanced Bonanza dataset, GegenNet showed a massive improvement over baselines, demonstrating its robustness to data sparsity and its ability to extract global structural information.

Conclusion

GegenNet demonstrates that the choice of spectral basis is critical for link sign prediction in signed bipartite graphs. By moving beyond simple low-pass filters to expressive Gegenbauer polynomial filters, the model achieves state-of-the-art performance. Future work includes extending the model to dynamic bipartite networks where relationships evolve over time.

Summary updated

Abstract

Given a signed bipartite graph (SBG) G with two disjoint node sets U and V, the goal of link sign prediction is to predict the signs of potential links connecting U and V based on known positive and negative edges in G. The majority of existing solutions towards link sign prediction mainly focus on unipartite signed graphs, which are sub-optimal due to the neglect of node heterogeneity and unique bipartite characteristics of SBGs. To this end, recent studies adapt graph neural networks to SBGs by introducing message-passing schemes for both inter-partition (UxV) and intra-partition (UxU or VxV) node pairs. However, the fundamental spectral convolutional operators were originally designed for positive links in unsigned graphs, and thus, are not optimal for inferring missing positive or negative links from known ones in SBGs. Motivated by this, this paper proposes GegenNet, a novel and effective spectral convolutional neural network model for link sign prediction in SBGs. In particular, GegenNet achieves enhanced model capacity and high predictive accuracy through three main technical contributions: (i) fast and theoretically grounded spectral decomposition techniques for node feature initialization; (ii) a new spectral graph filter based on the Gegenbauer polynomial basis; and (iii) multi-layer sign-aware spectral convolutional networks alternating Gegenbauer polynomial filters with positive and negative edges. Our extensive empirical studies reveal that GegenNet can achieve significantly superior performance (up to a gain of 4.28% in AUC and 11.69% in F1) in link sign prediction compared to 11 strong competitors over 6 benchmark SBG datasets.
BibTeX
@inproceedings{wang2025gegennet,
  author = {Hewen Wang and Renchi Yang and Xiaokui Xiao},
  title = {{GegenNet: Spectral Convolutional Neural Networks for Link Sign Prediction in Signed Bipartite Graphs}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2025},
  doi = {10.1145/3746252.3761129},
}
Figure