SignFlow Bipartite Subgraph Network For Large-Scale Graph Link Sign Prediction
Authors: Yixiao Zhou
Xiaoqing Lyu
Hongxiang Lin
Huiying Hu
Tuo Wang
Venue: NeurIPS 2025 poster ()
Keywords: Link sign prediction
Subgraph representation learning
Primary area: deep_learning
TL;DR: SBSN is a scalable framework for link sign prediction in signed bipartite graphs, combining efficient subgraph sampling, directed message passing, and node feature distillation to achieve high accuracy and fast inference with low memory cost.

Abstract: Link sign prediction in signed bipartite graphs, which are extensively utilized across diverse domains such as social networks and recommendation systems, has recently emerged as a pivotal challenge. However, significant space and time complexities associated with the scalability of bipartite graphs pose substantial challenges, particularly in large-scale environments. To address these issues, this paper introduces the SignFlow Bipartite Subgraph Network (SBSN), balancing sublinear training memory growth through a heuristic subgraph extraction method integrated with a novel message passing module, with optimal inference efficiency achieved via the node feature distillation module.

Our subgraph sampling approach reduces the graph size by focusing on neighborhoods around target links and employs an optimized directed message passing mechanism to aggregate critical structural patterns. This mechanism allows SBSN to efficiently learn rich local structural patterns essential for accurate sign prediction. Furthermore, to overcome the inefficiency of subgraph sampling-based models during inference, SBSN incorporates a node feature distillation module after the first training stage. This module distills subgraph features into node features, enabling fast inference while retaining the rich structural information of subgraphs.

Experiments reveal that SBSN shows superior performance in both medium- and large-scale datasets, efficiently managing memory and computational resources, making it a scalable solution for extensive applications.

SignFlow Bipartite Subgraph Network For Large-Scale Graph Link Sign Prediction
Yixiao Zhou
Hongxiang Lin
Wangxuan Institute of Computer Technology Peking University
Wangxuan Institute of Computer Technology Peking University
Huiying Hu
Tuo Wang
Wangxuan Institute of Computer Technology Peking University
Wangxuan Institute of Computer Technology Peking University
Xiaoqing Lyu"
Wangxuan Institute of Computer Technology,
State Key Laboratory of Multimedia Information Processing Peking University
Abstract
Link sign prediction in signed bipartite graphs, which are extensively utilized across diverse domains such social networks and recommendation systems, has recently emerged as pivotal challenge. However, significant space and time complexities associated with the scalability of bipartite graphs pose substantial challenges, particularly in large-scale environments. To address these issues, this paper introduces the SignFlow Bipartite Subgraph Network (SBSN), balancing sublinear training memory growth through a heuristic subgraph extraction method integrated with novel message passing module, with optimal inference efficiency achieved via the node feature distillation module.
Our subgraph sampling approach reduces the graph size by focusing neigh- borhoods around target links and employs an optimized directed message passing mechanism aggregate critical structural patters.. This mechanism allows SBSN to efficiently learn rich local structural patterns essential for accurate sign pre- diction. Furthermore, overcome the inefficiency of subgraph sampling-basee models during inference, SBSN incorporates a node feature distillation module after the first training stage. This module distills subgraph features into node features, enabling fast inference while retaining the rich structural information of subgraphs.
Experiments reveal that SBSN shows superior performance in both medium- and large-scale datasets, efficiently managing memory and computational resources, making it scalable solution for extensive applications. The implementation of SBSN is publicly available htthtttt////tttt com/WICTSA/SESM
"Correspondence: 1vxiaoqing@pku.ce edu. cn. sinhongrian@dstnn pku. edu. cn, hhy20244pku. edu. en, Ivxiaoging@pku.co edu.
Author
emails:
chnzyxēpku edu. en, tuovang25dstu, edu. en,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
In the digital society nowadays, the diversity of evaluations among individuals is prevalent and manifests significant complexity. This phenomenon spans various domains such social network interactions [7] personalized feedback in recommendation systems [19 20 [1], and peer review in academic research O B2]. To fully analyze such social phenomena, researchers frequently employ the signed bipartite graph model. In a signed bipartite graph, nodes are partitioned into two disjoint sets, e.g., users and commodities, are represented by edges with positive or negative signs, where positive edges signify favorable connections ratings and negative edges denote unfavorable ones. Predicting the signs of these links, known as the link sign prediction task, is a fundamental problem in signed bipartite graph research. Existing methods can generally be categorized into two types: feature-based and subgraph-based approaches.
reviewers and papers. Links between these sets
9 32 6]. link sign prediction in signed bipartite graphs remains challenging. First, feature-basse approaches commonly leverage balance theory to model node interactions. However, such methods often suffer from growth in space complexity the size of the dataset increases. Furthermore, balance theory cannot model all signed graph formation patterns [88, leading to substantial information loss. Second, subgraph-base based approaches have recently emerged, extracting and encoding subgraphs for each query during training and inference. Although this strategy offers local structural advantages, faces limitations in scalability and inference speed, which significantly restrict its applicability in large-scale scenarios.
Despite progress in the field [24 25 progress
These limitations become on e-commerce platforms and user ratings on video streaming sites, where both the number of nodes in each set and the number of edges grow to massive scales. Performing message passing and feature learning directly on the entire bipartite graph becomes infeasible, resulting in prohibitive computational costs. The scalability of current models is thus severely hindered by their high resource demands, limiting their applicability in practical, large-scale settings.
more pronounced in real-world scenarios, such as user preferences
To address these challenges, propose link sign prediction method, the SignFlow Bipartite Subgraph Network (SBSN), to accomplish the prediction task:
1. Scalable Subgraph Training: To tackle the rapid growth of space complexities with increasing dataset size, transform global node feature training into local subgraph feature training. Unlike traditional methods that sample k-hop neighbors of nodes and separately, our subgraph sampling ensures each node lies on simple path connecting u and v. greatly improving information efficiency. By leveraging the properties of bipartite graphs, our subgraph sampling strategy establishes topological structure facilitate subsequent subgraph feature learning. Such subgraph training design ensures that the space complexity of our model scales sublinearly with the size of the dataset.
2. Directed SignFlow Passing: To effectively capture the structural information of subgraphs, propose the SignFlow Aggregator within SBSN. This module aggregates all path infor- mation connecting source nodes and target nodes within the topological subgraph, enabling comprehensive structural representation. The aige-feature-basee SignFlow Aggregator further enriches the subgraph representation, surpassing node-feature- feeeeure--- methods such GCN in information richness.
3. Feature Distillation for Efficient Inference: To overcome the inference inefficiencies of subgraph- models compared to feature-based models, we introduce a node feature distillation module. This additional training step distills subgraph features into node features, allowing our model to achieve better inference efficiency. Also, node features serve broad range of downstream tasks, including node clustering and node classification.
4. Theoretical and Empirical Complexity Analysis:
We provide both theoretical and em- pirical analyses of the model's complexity, demonstrating how computational and memory costs scale with dataset size F.. Extensive experiments on medium- and large-scale datasets further validate the scalability and accuracy of our approach.

---

2 Related Works
2.1 Signed Graph Representation Learning
Signed graphs have garnered significant attention due the rapid growth of social networks 17 29
and recommender systems 19 20 [1]. Numerous tasks in signed graph analysis have been explored,
such as node classification 26], node ranking [23), link sign prediction 9 [2], community detection 22) and visualization [28] Among these tasks, link sign prediction is particularly important. Signed Graph Representation Learning (SGRL) is effective approach analyze the complex patterns in real-world signed graphs with the co-existence of positive and negative links (33) Early methods for learning representations of signed graphs were based on random walks 12 30 [3] and matrix factorization 3 [I3]. In recent years, deep learning has been applied to signed representation learning. SiNE extracts structural information from triangle motifs and designs an objective function based on balance theory[8] [8]. SGCN became the first signed graph neural network model, extending GCN[14] and using balance theory to determine positive and negative relationships between nodes in multi-hop neighborhoods. Similarly, models like SIG (NEA[16), and SDGNN[LI use proposes a contrastive learning method for robust signed graph representation learning. SGA 31 proposed novel data augmentation approach tailored for SGNNs. By introducing a new perspective on data augmentation, SGA aims to significantly enhance the training process.
graph attention networks to learn signed graph representations. SBGCL 32
However. SGRL methods typically perform message passing through GNN layers across the entire bipartite graph, which makes GPU memory management challenging. As the dataset size increases linearly, the GPU memory consumption of such models increases at least linearly. Higher precision bassaage-assiigg layers often require more memory, making the training of such models on large-scale datasets impractical due to the prohibitive GPU memory consumption. Additionally, balance theory, which is commonly used by SGRL methods, cannot model all signed graph formation patterns [88]
2.2 Subgraph Embeddings and Prediction
Subgraph- based methods have also been extensively explored for graphs. SUBGNN [ introduces subgraph neural network with a novel routing mechanism to learn disentangled subgraph repre- sentations. SELO [6] extracts enclosing subgraphs for each target pair of nodes and encodes these subgraphs into vectors through unique linear optimization (I.O)-based approach. SELO introduces likelihood matrix representation for subgraphs, which captures triad and high-order cycle patterns rather than pairwise interactions.
However, SELO does not strictly limit subgraph size during the matrix computation phase, leading to large-scale matrix operations on large datasets. Moreover, the above subgraph learning algorithms require subgraph sampling for each query during the inference phase, resulting in suboptimal inference performance compared to SGRL algorithms. Furthermore, subgraph- based methods often lack node features, as they rely on subgraph embedding for inference, which limits their ability to learn rich node representations and makes them less applicable to other node-based downstream tasks.
3 Problem Formulation of Signed Bipartite Graph Link Sign Prediction
A signed bipartite graph is defined as G (U, F+ E-), where the two sets of nodes U = {ui, u2, fioon and V U2,,,, "[v]] are disjoint, E+ C U x V and E CU x V are the positive and negative edge sets, respectively. Note that E n E and the two endpoints of any edge in E U E must come from different sets U and V. For example, in Figure [ the set U could be the set of users an e-commerce platform, and the set V could be the set of products. A posi- tive edge (u, v) E E+ represents that the user rates the product favorably, and negative
userl
productt
WHer2
product2
us4r3
product3
uxerd
productd
produrts
O
user mode
faver (positiive edge)
(u,, v.)
(u,,
(u,, My
(4,, v)
product mode
vafavor (megative edge)
(st Ma)
(us, vi)
Figure 1: Signed bipartite graph in an e-commerce scenario
3

---

edge (u, v) E E represents that u rates unfa- vorably. In this paper, we ignore the directions of the edges and treat the graph G as an undirected graph.
Given G (U, V, F+, F.),, the goal is predict the sign of edge (u, v) U V that is not in the observed set of edges E- U ET. Specifically, we aim to learn a function that, for any pair of nodes u; E U and Uj V, predicts whether the edge between them should be positive or negative. The function ff should be able to accurately determine the sign of the link based on the structural properties of the graph and the features of the nodes.
SLb
P mity
Exuh
Fash (Mg.
MEL
predicee lobal
P -M2
Ps Me
Uie Adal
Subgraph Extraction
SignFlow Aggregation
Node Feature Distillation
Figure 2: Overview the SignFllow Bipartite Subgraph Network (SBSN). SBSN comprises three modules: (1) Topological Subgraph Extractor, which identifies subgraph Gun e) for queried edge (u, v): (2) Directed SignFlow Aggregator, which performs edge-base based information propagation and weighted aggregation; and (3) Node Feature Distillation Module, which enhances inference efficiency in the second training stage.
Proposed Method
To address the challenges of high computational cost and scalability in large-scale bipartite graphs, we propose the SignFlow Bipartite Subgraph Network (SBSN), as illustrated in Figure 2 Our model comprises three main modules: topological subgraph extractor (Section 4.1 directed
SignFlow Aggregator (Section[4.2) and a node feature distillation module (Section 4.5) The first two modules are used for the primary link sign prediction training. Specifically, the topological subgraph extractor identifies the subgraph for a queried edge, while the SignFlow Aggregator performs edge- based information propagation and weighted aggregation embeddings are fused and passed through an MLP to predict the link sign based weighted binary cross-entropy loss. The third module, the Node Feature Distillation Module, is employed during the second stage of training to reduce resource consumption during inference and to obtain node features applicable to broader range of downstream tasks.
generate subgraph embeddings. These
For a queried edge (u, v), the model employs a Topological Subgraph Extractor. This extractor identifies topological subgraph Gsub (u, v) that highly relevant to the queried edge. The subgraph contains multiple paths with u and v as endpoints, facilitating subgraph structure embedding and inference.
Once the subgraph structure is obtained, directed information propagation is performed. The SignFlow Aggregator aggregates path information the edge granularity. allowing nodes in subsequent layers to aggregate features from all incoming edges. This module also derives attention values for each neighbor in the previous layer based edge features and then performs weighted aggregation.
During the training phase, we use the aggregated subgraph encoding to predict the sign of the queried edge and compute the loss function. In the inference phase, subgraphs are directly extracted for

---

prediction. Alternatiely, with additional training of the node feature distillation module, we achieve significant improvements in inference speed at the cost of minimal performance loss.
4.1 Topological Subgraph Extractor
As illustrated Figure 3 the topological subgraph extractor constructs subgraph iteratively with and the first and last layers, respectively. This ensures that the subgraph effectively captures the structural information of the bipartite graph while maintaining computational efficiency. The detailed process is described below:
4.1.1 Iterative Node Sampling for Subgraph Construction
Given a queried edge (u, v) in a bipartite graph G (U,V, E-), the goal is construct topological subgraph Gsat(u, v) with u and v as the source and target nodes. The subgraph is expanded iteratively by sampling intermediate layers of nodes from U and
Let ( {u, f} represent the initial subgraph, where u and v are the only nodes. During each iteration 6, two sets of nodes, LN C U and Lj C V, are sampled as intermediate layers. The process as follows:
1. Neighbor Node Selection: Define the neighbors of a node set L in or V as: [LL) {w B(z, w) E E,r E L}. At iteration the candidate sets for new nodes are:
(L N
where LE and L are the current intermediate layers nodes in U and V, respectively.
2. Sampling New Nodes: New nodes for the subsequent layers, L and LY+ are sampled from their respective candidate sets using one of several heuristic strategies: Random Sampling (uniform selection), High-Degret Sampling (prioritizing nodes with the highest degrees), or Low-Degree Sampling (prioritizing nodes with the lowest degrees). The sampled nodes must satisfy:
LE n 0, LV n G 0,
ensuring that no duplicate nodes are added to the subgraph.
3. Subgraph Update: Update the subgraph with the newly sampled nodes:
G+++1
Glub Lyt1 U
The process repeats until the total number of nodes in Gsuh (u, v) reaches pre-defined limit Tuuh-
Theorem 1(Optimal Number of Topological Layers). Let G be a random bipartite graph T nodes with edge probability p. Under a budget of T total nodes, the number of topological subgraph layers K that maximizes the expected number of distinct paths from the first to the last layer is
Kopt max 2. TT
+ 2.
For the full derivation of this result, see Appendix
!
4.1.2 Edge Extraction for the Topological Subgraph
After determining the node sets Gsub (u, v),, the edges the subgraph are extracted from the original bipartite graph G. The edge set Fxnb of the topological subgraph is defined as:
Inttll Graph
Query:
Include edges (x, y) in Esa if 2 E Guubuu, (u, v) and (z, E E in the origi- nal graph.
1ed Dediower
Sis
Exclude the direct edge (u,v) from Fush, even if it exists in E.
Rerative Mode Sumraiie
Figure 3: Illustration of the Topological Subgraph Extraction Process
Thus, the edge set is formally expressed as: Eup (xx v) x, E Gsub, (x, E EMi(u, }}
5

---

4.2 Directed SignFlow Passing
Before training, each node is assigned an initial feature vector sampled from normal distribution. Let z" and Z" represent the embeddings of nodes on the two sides of the bipartite graph, where Zu represents the feature of node During training, we first extract a multi-layer topological subgraph Gunnu, v) for the query edge (u, v) using the topological subgraph extractor. Suppose Gsuh (u, v) consists of layers; then, the first layer only contains node u, and the k-th layer only contains node v.
Let 7, represent the feature matrix of the nodes of i-th layer in the subgraph, and let f.j denote the edge weight matrix between the i-th and j-th layers. We use message passing (MP) function to propagate and aggregate information across layers. The initial feature of the first layer is H1 Zu.
For the i-th layer, the aggregated features H; obtained by fusing the output of the message passing operations from all preceding layers as follows:
H. & ((MP(H,, Z, (Eg.) j 1,2 ..... 13)
where & represents the feature fusion mechanism.
The message passing and feature fusion process continues iteratively until the final k-th layer. After completing message passing, the feature Hę at the k-th layer is used as the subgraph feature Pu-te for the multi-layer topological subgraph (u, r)::
Pa-v=
H
The message propagation process is referred to as SignFlow Passing in this work because it explicitly incorporates directed information flow across layers, reflecting the directionality of information transfer from node u to node v.
Let N be the number of nodes, T the subgraph node budget, d the feature dimension, L the number of message-passing layers, and the batch size. Encoding an extracted subgraph is dominated by edge- wise message passing and feature transforms; in the worst case the time cost for single subgraph encoding scales as O(L d²), and the peak GPU memory is dominated by persistent node features plus temporary working memory for batch subgraphs, which can be written O(Nd + B 2 d²); importantly, when Node Feature Distillation is used at inference the batch-dependent term related to T disappears and the active computation reduces O(B d²). Notably, the time to encode one subgraph is independent of the total number of edges E, while peak GPU memory scales sublinearly with the dataset size E because only N appears in the persistent memory component (under constant graph density, E x 22). Full derivations, constant factors and empirical measurements are provided Appendix A
4.3 SignFlow Aggregator
To address the issue of information loss due to aggregation solely based on node features, we adopt SignFlow Aggregator extract and refine edge features, enabling pre-passage of messages through edge features and reducing path information loss, thereby achieving more robust feature aggregation.
In our implementation, the message passing module aggregates features by applying the SignFlow Aggregator separately to the positive and negative edges between two layers of nodes. The results of these two computations are then combined using feature fusion function. Here, the SignFlow Aggregator is responsible for processing the edge information and node features to generate refindd edge features, while the positive and negative edges handled independently to account for their distinct contributions to the overall aggregation.
4.3.1 Node to Edge Feature Transformation
Node features from two consecutive layers are transformed into edge features. Let H and HV represent the features of the nodes in the source and target layers, respectively. For each edge connecting nodes and v, the edge feature H is computed as:
u.v
E MLP (H" (u), H (v)),
where HD (u) and (v) are the features of nodes u and v, respectively, and ML. is multi-layer perceptron.

---

4.3.2 Edge Feature Message Passing
Message passing is then performed on the edge features. For each edge (u, v), where e has set of neighbors No excluding u, the edge feature H u,v is updated using the features of edges connecting with neighbors p E N, {u}. The updated edge feature is:
Aggregate H N,V: (H P.U
IpEN, {u))).
The aggregation is performed by pooling the edge features of the set:
H
Aggregate H M,U:
Pooling (H |p N.))).
4.3.3 Edge Attention Values
The updated edge features H'B are reduced to sealar values to compute attention weights On for each edge. For each node in the target layer, the attention weights are normalized using softmax function:
exp(Score HE
1,00
Ohu,0 E NeN exp(SSore(HH)) p.1)
where Score(-) computes relevance score for the edge feature. In our model, we implement Score()) using a linear layer. These attention weights are used to perform weighted aggregation of node features from the source layer:
Agg(v)= Σ ap. H)(p).
PEN,
4.3.4 Edge Feature Integration
Finally, the aggregated node features are combined with the pooled edge features. For each node in the target layer, the pooled edge features are integrated into the final feature as follows:
H (u) Agg (v) MLLP(Pooling(( (H p." ppeNN)))
This formulation ensures that both node and edge information are deeply integrated, enhancing the representation power of the SignFlow Aggregator.
Loss Function
After performing message passing in both directions, we obtain subgraph embedding P Pa-ve and P Po-au- These are used form the fused feature as follows:
Feub (u, v) Concat(Paass Po-ta)
The fused feature is then passed through MIP reduce its dimensionality to 1, followed by sigmoid activation. The output is compared with the true label using weighted binary cross-entropy loss, where the weight is the proportion positive labels in the batch.
Lrce
(y. log(ús) (1 v1 log(1 -())
N
where N is the number of samples, is the true label, 0i is the predicted label, and is the weight for sample The weight wi determined by the proportion of positive labels in the batch.
4.5 Node Feature Distillation Module
To achieve a lightweight inference process, we propose node feature distillation module that approximates the features of subgraphs using the embeddings of nodes u and e. Specifically, the edge embedding Zu is computed as a linear transformation of the element-wise product of Z., and Z.:
7

---

Zu Linear Ze @ Zo).
where C denotes the element wise product. This operation captures interactions between individual dimensions of Zu and Z.,, enabling a meaningful representation of their combined information.
To guide Zu,o in approximating the topological subgraph features, use a distillation loss defined as the similarity between Zu. and (u, v), the feature representation of the subgraph obtained from the SignFlow module. We denote this similarity loss as Simm
Lim cos( cos( Foab (u, u)).
This module is trained after completing the primary training of the SignFlow Aggregator, focusing on further optimizing Zu to enhance inference efficiency with minimal performance loss.
For classification, Zu is passed through MLP reduce dimensionality to one, followed by sigmoid activation to produce the predicted probability of the edge sign. The output is compared with the true label using a weighted binary cross-entropy loss, denoted as Lree-
The total loss for the node feature distillation module combines the distillation loss and the binary cross-entropy loss:
Liotal = Lsim + Loce-
Upon completing the node feature distillation process, inference for queried edge v becomes significantly simpler. Instead of performing complex topological subgraph sampling and message passing, the prediction is directly obtained by computing the element-wise product of Zn and Z,, followed by MI.P This streamlined approach greatly accelerates the inference process while maintaining high prediction accuracy.
Experiments
In this section, introduce seven real-world datasets and baseline models, along with our experi- mental setup. We then present the average metrics, demonstrating the performance of our model, after which we discuss the results in memory management and conduct ablation studies and parameter studies to evaluate the scalability of our model on large-scale datasets.
5.1 Datasets
We conduct a series of experiments on four small-scale and medium-scall real-world datasets: Bonanza U.S. House(5), " and Amazon-Book and three large-scale datasets: ML-I0M², MI-32M- and Amazon-Book 500 These datasets cover the academic, social, and political domains, providing us with rich information validate the performance and applicability of our model. More details about these datasets can be found in Appendix B
5.2 Baselines and Experiment Setting
We evaluate our method, SBSN, against several baselines, including node feature-based methods, Signed GNNs, and Subgraph-basee Networks. During the inference phase, for each queried pair of nodes, SBSN extracts a subgraph and predicts the sign using the subgraph embedding, whereas the derived SBSN-node directly leverages the node features distilled by the node feature distillation module for inference. Detailed descriptions of the baseline methods and specific experimental settings can be found in Appendix
httpp://wuzt htwp://wwwwoooaa..comm com/
wiw.e/oo/iiiiii.iieeeemm html
https://jmcauleyy.. ucsd. htw.:///w.....ddddee/////t/////a v2/index...nn..e html

---

Table 1: Performance (average + standard deviation) on Medium-scale Datasets
Dataset
Metric
Node2vec
SGCN
SGCL
SGA
SEGNN
SBGCL
SELO
SBSN
SBSN-node
AUC
59.3
58.7
58.4
59.6
57.7
59.0
58.5
92.0
92.5
Bonanza
Bin-FI
98.8
89.6
98.7
93.5
96.2
97.3
98.4
98.8
0.7
99,3
6.2
Mic-FI
97.7
81.4
97.4
88.0
92.7
94.7
96.9
97.7 = 1.3
98.6
AUC
54.4
80.8
82.4
65.1
84.8
81.0
84.6
88.0
- 0.4
85.0
0.2
U.S. House
Mac-FF F1
48.7
80.8
82.4
62.1
84.7
80.7
84.6
88.0
- 0.4
85,0
Mic-FI
54.5
80.9
82.4
66.1
84.7
80.7
84.7
88.0 1 0.3
85.0
AUC
52.6
59.3
61.3
53.6
60.3
63.7
65.2
0..
73.4
Amazon-Book
Bin-FI
88.8
69.3
71.0
89.1
72.0
73.4
86.5
80.9
81.0
Mac-F1
44.4
50.4
50.2
52.5
55.2
58.7
65.2
66.6 + 0.2
66.2
Mic-FI
79.8
60.4
80.7
61.2
64.0
78.3
72.7
72.7
AUC
51.0
0.2
Bin-Fi
73.0
65.2
67.3
73.5
69.9
70.2
77.5
77.3 0.2
76.5
ML-IM
Mac-F1
36.6
61.5
66.2
48.6
65.3
67.8
73.5
74.1
73.4
Mic-FI
57.5
65.2
61.9
67.4
74.5
0.2
5.3 Performance on Link Sign Prediction
As shown in Table T our proposed model SBSN achieves the best performance in terms of the AUC metric on all datasets, outperforming the state-of-the-ar model by 28.5%. 3.2%, 9.3%, and 0.8% on the midium-scale datasets. It can be observed that model exhibits significant improvements, particularly on imbalanced datasets (Bonanza, Amazon-Book), On large-scale datasets, due to CPU time (see Appendix E GPU memory overflow, the performance of SGRL methods and SELO could not be tested. However, our model still achieved strong performance (see Appendix G
Additionally, SBSN-node directly uses the node features obtained through the node feature distillation module for link sign prediction. The results show that the performance of SBSN-node incurs only minimal loss compared to subgraph-based feature extraction. The detailed analysis of inference efficiency in Appendix highlightt the substantial improvements in inference efficiency afforded by our node distillation module.
5.4 Ablation Study and Parameter Study
In the ablation experiments, as shown in Table 2 we tested the module ablation effects the U.S. House dataset. Firstly, we removed the edge features 11 from the Directed Sign- Flow Passing Module and replaced them with the node features Z, The model experienced a significant per- formance loss due to the loss of edge feature granularity in the information aggregation process. Next, we replace the Directed SignFlow Passing Module with a GCN Mean Aggregator, which also resulted in certain degree of performance degradation.
Table Ablation Study on U.S.
House Dataset
models
AUC
Bin-Fl
Mac-FI
Mic-FI
SBSN
88.0
88.8
88.0
88.0
SBSN w/o edge
87.1
87.9
87.0
87.1
SBSN SBSN_GCN
85.6
86.5
85.6
85.7
Figure 4 a)) presents the performance of our model in terms of AUC on the ML- IL dataset with varying values of the subgraph maximum nodes limit. The results indicate positive correlation, with performance steadily improving as the limit increases. However, the marginal gains in AUC diminish the limit increases, indicating that while larger neighborhood sizes improve performance, diminishing returns occur beyond a certain point.
Additional ablation studies (see Appendix Hy demonstrated that our Topological Subgraph Extractor utilizes information more efficiently than other sampling algorithms, established that different sampling strategies offer dataset-specific advantages, and identified the comprehensive utilization of node features as a primary driver for the superior performance observed on the Bonanza dataset.
5.5 Memory Efficiency Analysis
In this section, we compare the GPU memory consumption of our model with SGRL-based methods on subsets of the ML-10M dataset of varying sizes. As shown in Figure((b) SBGNN and SBGCL

---

50
7244
SHORN SBGCL
13
SBSN (OurS)
Allocated Memory (cut)
AUE (75)
70
10
ML-1M AUK:
180100
400
Subgraph
Dataset (1/ ML-10M)
Figure 4: Parameter Experiment and GPU Memory Analysis
exhibit rapidly increasing memory consumption dataset size grows. This is because SGRL-based methods perform message passing through GNN layers across the entire bipartite graph, resulting in rapid memory growth as the dataset size increases. In contrast, SBSN demonstrates significantly more stable memory footprint across different dataset sizes. This highlights the memory efficiency of method, it processes smaller topological subgraphs rather than the entire graph during message passing. By leveraging this efficient subgraph sampling and message-passing strategy, SBSN achieves balance between memory efficiency and model performance, enabling its application large-scale bipartite graphs. The memory analysis presented in Appendix F demonstrates that, for large-scale datasets, the GPU memory consumption of our method scales linearly with the number of nodes in the dataset.
Conclusion
In this paper, we introduce SBSN to address the challenges in link sign prediction for signed bipartite graphs. Experiments on real-world datasets demonstrate that SBSN outperforms existing baselines in predictive performance while maintaining computational efficiency. Importantly, the scalability of SBSN makes it versatile solution for large-scale applications.
While our results highlight the effectiveness of subgraph embedding, future work could explore improvements in three key areas. First, developing more efficient message passing modules could further optimize computational complexity. Second, incorporating self-explainability techniques may improve model transparency. Finally, extending SBSN to dynamic signed bipartite graphs would enable sal-time prediction and adaptation to evolving network structures.
10

---

7 Acknowledgment
This work is supported by the projects of Beijing Nova Interdisciplinary Program (20240484647) and National Natural Science Foundation of China (No. 62376012), which is also research achievement of State Key Laboratory of Multimedia Information Processing and Key Laboratory of Science, Technology and Standard in Press Industry (Key Laboratory of Intelligent Press Media Technology).
References
[1] Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik. Subgraph neural networks Advances in Neural Information Processing Systems, 33:8017-8029, 2020.
[2] Francesco Bonchi, Edoardo Galimberti, Aristides Gionis, Bruno Ordozgoiti, and Giancarlo Ruffo. Discovering polarized communities in signed networks. In Proceedings of the 28th acm international conference on information and knowledge management, pages 961-970, 2019.
[3] Kai- Yang Chiang, Joyce Jiyoung Whang, and Inderjit S Dhillon. Scalable clustering of signed networks using balance normalized cut. In Proceedings of the 2 ACM international conference on Information and knowledge management, pages 615-624, 2012.
[4] Wanqiu Cui, Junping Du, Dawei Wang, Feifei Kou, and Zhe Xue. Mvgan: Multi-view graph attention network for social event detection. ACM Transactions on Intelligent Systems and Technology (TIS7), 12(3): 1-2 2021.
[5] Tyler Derr, Cassidy Johnson, Yi Chang, and Jiliang Tang. Balance in signed bipartite networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pages 1221-1230, 2019.
[6] Zhihong Fang, Shaolin Tan, and Yaonan Wang. A signed subgraph encoding approach via linear optimization for link sign prediction. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[7] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[8] Fritz Heider. Attitudes and cognitive organization. The Journal of psychology, 21(1):107-11,, 1946.
[9] Junjie Huang, Huawei Shen, Qi Cao, Shuchang Tao, and Xueqi Cheng. Signed bipartite graph neural networks. In Proceedings of the 30th ACM international conference on information & knowledge management, pages 740-749, 2021.
[10] Junjie Huang, Huawei Shen, Liang Hou, and Xueqi Cheng. Signed graph attention networks. In Artificial Neural Networks and Machine Learning-CCANN 2019: Workshop and Special Sessions: 28th International Conference on Artificial Neural Networks, Munich, Germany, September 17-19, 2019, Proceedings 28, pages 566-577 666-577.55 Springer, 2019.
[11] Junjie Huang, Huawei Shen, Liang Hou, and Xueqi Cheng, Sdgun: Learning node representation for signed directed networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 196-203, 2021.
[12] Jinhong Jung, Jaemin Yoo, and U Kang. Signed graph diffusion network. arXiv preprint arXiv:2012. 14191, 2020.
[13] Junghwan Kim, Haekyu Park, Ji-Fuu Lee, and U Kang. Side: representation learning in signed directed networks. In Proceedings of the 2018 world wide web conference, pages 509-518, 2018.
[14] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint XXXi:1609002900 2016.

---

[15] Jérôme Kunegis, Stephan Schmidt, Andreas Lommatzsch, Jürgen Lerner, Ernesto W De Luca, and Sahin Albayrak. Spectral analysis of signed graphs for clustering, prediction and visualiza- tion. In Proceedings of the 2010 SIAM international conference on data mining, pages 559-570. SIAM, 2010.
[16] Yu Li, Yuan Tian, Jiawei Zhang, and Yi Chang. Learning signed network embedding via graph attention. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 4772-4779, 2020.
[17] Wenqing Lin, Large-scale network embedding in apache spark. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 3271-3279, 2021.
[18] Haoxin Liu, Ziwei Zhang, Peng Cui, Yafeng Zhang, Qiang Cui, Jiashuo Liu, and Wenwu Zhu. Signed graph neural network with latent groups In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 1066-1075, 2021.
[19] Itzik Malkiel, Oren Barkan, Avi Caciularu, Noam Razin, Ori Katz, and Noam Koenig- stein. Recobert: A catalog language model for text-based recommendations, arXiv preprint arXiv:2009. /3292, 2020.
[20] Shumpei Okura, Yukihiro Tagami, Shingo Ono, and Akira Tajima. Embedding news recommendation for millions of users. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1933-1942, 2017.
[21] Tao Qi, Fangzhao Wu, Chuhan Wu, and Yongfeng Huang. Fum: fine-grained and fast user modeling for news recommendation. In Proceedings of the 45th international ACM SIGIR conference research and development in information retrieval, pages 1974-1978, 2022.
[22] Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303. 10993, 2023.
[23] Moshen Shahriari and Mahdi Jalili. Ranking nodes in signed social networks. Social network analysis and mining, 4:1-12, 2014.
[24] Liushuai Shi, Le Wang, Chengjiang Long, Sanping Zhou, Mo Zhou, Zhenxing Niu, and Gang Hua. Sgen: Sparse graph convolution network for pedestrian trajectory prediction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8994-9003, 2021.
[25] Lin Shu, Erxin Du, Yaomin Chang, Chuan Chen, Zibin Zheng, Xingxing Xing, and Shaofeng Shen. Sgel: Contrastive representation learning for signed graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1671-1680, 2021.
[26] Jiliang Tang, Charu Aggarwal, and Huan Liu. Node classification in signed social networks. In Proceedings of the 2016 SIAM international conference data mining, pages 54-62. SIAM, 2016.
[27] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1000220)10-485555 2017.
[28] Suhang Wang, Jiliang Tang, Charu Aggarwal, Yi Chang, and Huan Liu. Signed network embedding social media. In Pruceedings of the 2017 SIAM international conference on data mining, pages 327-335. SIAM, 2017.
[29] Zhihao Wen, Yuan Fang, and Zemin Liu. Meta-inductive node classification across graphs. In Proceedings of the 44th International ACM SIGIR Conference on Reseurch and Development in Information Retrieval, pages 1219-1228, 2021.
[30] Shuhan Yuan, Xintao Wu, and Yang Xiang. Sne: signed network embedding. In Advances in Knowledge Discovery and Data Mining: 21st Pacific-Asia Conference, PAKDD 2017, Jeju, South Korea, May 23-26, 2017, Proceedings, Part I1 21, pages 183-195. Springer, 2017.
12

---

[31] Zeyu Zhang, Lu Li, Shuyan Wan, Wang Wang, Zhiyi Wang, Zhiyuan Lu, Dong Hao, and Wanli Li. Dropedge not foolproof: effective augmentation method for signed graph neural networks. Advances in Neural Information Processing Systems, 37:1 17041-117069, 2024.
[32] Zeyu Zhang, Jiamou Liu, Kaiqi Zhao, Song Yang, Xianda Zheng, and Yifei Wang. Contrastive learning for signed bipartite graphs. In Proceedings of the 46th International ACM SIGIR Conference Research and Development in Information Retrieval, pages 1629-16333 2023.
[33] Zeyu Zhang, Peiyao Zhao, Xin Li, Jiamou Liu, Xinrui Zhang, Junjie Huang, and Xiaofeng Zhu. Signed graph representation learning; A survey, arXiv preprint arXiv 15980 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification: NA
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
The code available in the supplementary material and will be available on github.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https SttSSuabissioooiiiiiio.oooii for more details.
//nips.cc/ppp cc/public/guue httpg/iddeeeeeeebbnnnnnneeee
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We include std error of our SBSN model in the main experiment table.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wwrppccccaaaaa/a/aaaaaaa
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: See README.md in code folder.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: We use LLM only for editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurii: //tpa/rrpp...cc/ooooeeeeeee////p for what should or should not be described.
20

---

A Complexity Analysis
We provide a detailed analysis of the computational complexity of our proposed SBSN model, focusing on both space and time requirements.
A.1 GPU memory Complexity
The gpu memory requirements for SBSN consist of storage for model parameters and node features, as well as dynamic memory for intermediate variables during batch processing. The primary storage for node features amounts to N d, where N is the total number of nodes and d is the feature dimension. The architecture of our model, featuring three SignFlow Aggregator modules (each with fixed linear layers and one edge attention layer), contributes an additional (d²²) to the learnable parameter space.
During batch processing, intermediate variables are generated. For a batch of size B with subgraphs of size T. subgraph node features require B T space. The computations of the Edge Attention module, including H.,,, and pooled attention values, have an upper bound of O (- T dd) in worst- case complete graph scenario within the subgraph. Other linear layers and attention mechanisms contribute terms on the order of B B-T². d and B -d?. Consequently, the overall memory complexity for SBSN is N + O(B 7 ).). This contrasts with standard GCN approaches (often used in SGRL methods), which may require OEE) memory per message aggregation step across all E edges, a prohibitive cost for large-scale graphs because = ONN))
The memory consumption varies slightly between phases. During training, the complexity is N + O(B T d.). For inference without Node Distillation, remains similar. However, when Node Distillation is applied for inference, the memory consumption for the active computation part is significantly reduced. Since predictions for pair (u, v) primarily involve their features and simpler distilled head, the batch- Match-dependent part related to T diminishes, leading to memory footprint closer N d + O(B d²) for the relevant computations. By carefully selecting batch size and subgraph size T. SBSN can efficiently process very large graphs; our estimations suggest it can handle datasets with up to N 1.7 x 10t nodes on a single 80GB GPU under typical experimental settings with == 800. For detailed memory calculation, please refer to Appendix F
A.2 Inference Time Complexity
We analyze the time complexity on a per-query basis, highlighting the efficiency gains from Node Feature Distillation during inference.
For a single query processed without Node Distillation, the computation involves two main stages. First, the sampling stage, which constructs the topological subgraph, has worst-case time complexity of O(T2 log(N)). where the bottleneck is the induced subgraph extraction (assuming, for instance, scanning through neighbor dictionaries in dense regions for T' nodes). Second, the message passing stage within the sampled subgraph, analogous to its space requirements, has an upper bound of O d²). Thus, the total time complexity per query in this mode O(T + d²)).
In contrast, when inference is performed with Node Distillation, only the features of the queried nodes u and are processed through the distilled model head (typically few MLP layers). This dramatically reduces the time complexity per query to (d2). This level of efficiency is comparable to that of many SGRL methods during their inference phase, demonstrating a significant practical advantage of our distillation approach.
B Dataset Details
Each dataset contains different number of nodes and edges, as well as positive and negative relationships between them, with detailed statisties listed in Table During the experiments, we follow the experimental setup in [3], randomly splitting the links of each dataset into three parts: 10% for testing, 5% for validation, and the remaining 85% for training. For the large-scale dataset, we split the data into 8% for testing, 2% for validation, and 90% for training, and average the results over three runs. To ensure the stability and reliability the experimental results, We run with different main-val-test splits for 5 times to get the average scores.
21

---

Table 3: Statistics Signed Bipartite Networks
Bonanza
U.S. House
ML-IM
Amazon-Bove Book
ML-IOM
ML-32M
Amazon-Booke Book-35M
7,919
515
6,040
35,736
69,878
200,948
2,930,451
1,973
1,281
3,952
38.121
10,677
84,432
15,362,619
36,543
114,378
1,000,209
1,960,674
10,000,054
32,000,201
51,311,613
%
E
0,980
0.540
0.575
0.806
0.589
0.821
0.848
%
E
0.020
0.460
0.425
0.194
0.411
0.179
0.152
C Baselines and Experiment Setting Details
Node2vec baseline: Node2vec 7 learning www-dimensional vector representations of nodes in a network, where these vectors can capture the network structure information and neighborhood characteristics of the nodes. To predict the sign of links, fuse the embeddings of the connected nodes and utilize a logistic regression model with binary cross-entropy loss. We experimented with various fusion methods--including sum, LI, L2, and concatenation-andt explored different hyperparameters for Node2Vec, specifically setting embedding_ __mm_mimm__e to { 116, 32, 64) and walk_length to (20, 30, 40). After thorough evaluation, we determined that the optimal combination was the sum fusion method, with embedding_dine set to 64 and walk_lengde set to 40.
Signed Graph Neural Networks: SGCN [24] generalize GCN [14] and GAT [27] to signed graphs
based on message-passingg mechanisms and balance theory. SGCL 25 is the first research to employ
graph contrastive learning unipartite signed graphs. SBGNN 9 designs
message-passing
mechanism for signed bipartite graphs, which is our most competitive competitor. SBGCL (32 proposes contrastive learning method for robust signed graph representation learning. SGA proposed a novel data augmentation approach tailored for SGNNs.
Subgraph-base based Networks: SELO (6) extracts enclosing subgraphs for each target pair of nodes and encodes these subgraphs into vectors.
For fair comparison, we set all the node embedding dimensions to 32, which is the same as that in SBGNN ()) and SBGCL [32], for all embedding- we follow the recommended settings in their original papers. We run up to 12,800,000 subgraph 800 for SBSN for training and choose the model that performs the best in AUC metrics on the validation set. For our SBSN, we use PyTorch to implement it. We use the Adam optimizer with an initial learning rate of 0.002 and a weight decay of le-5. We set the maximum number of nodes in the topological subgraph to 800. Our experiments are conducted on an 100 platform. Additionally, we derived SBSN-node by utilizing the node feature distillation module.
methods. For other parameters in baselines,
samples with K = 4 and
For SGA, we employ GSGNN the backbone model. which was reported as the top-performing architecture in its original publication. Regarding the hyperparameters, specifically dde del 'dd. and Led we searched for optimal values of Cael E f0.1, 0.3) and cald (0.94, 0.98, 0.99} across different datasets. Compared the direct application of the backbone model, The data augmentation of SGA significantly enhanced model performance. Nevertheless, due the backbone model being a general graph model (i.e.. not specifically designed for bipartite structures), SGA exhibited considerable variance in performance on bipartite graph datasets.
During the GPU memory test, we monitored the peak GPU memory usage by tracking the maximum allocated memory with torch. cuda. www.mmemmmmlloooo -alooryyaloccted.
The evaluation task is link sign prediction, which is binary classification problem. We use AUC (Area Under the Curve), Binary-F1, Macro-F1, and Micro-F1 to evaluate the results. These metrics widely used in existing work 9 32].
AUC is particularly important as it measures the ability of the model to distinguish between positive and negative classes. It provides a single scalar value that summarizes the performance of the model across all classification thresholds. Thus, we use AUC as the primary evaluation metrie for assessing the link sign prediction performance of models.
22

---

D Inference Efficiency Analysis
Table 4 presents the inference time of different models on the ML-IM dataset. We tested the time consumption of performing inference on the entire ML-IM dataset for each model, where link sign prediction performed for all edges in the dataset. As seen, SBGCL achieves the fastest inference time of 0.00014 seconds, followed by SBGNN and SBSN-node, both of which require 0.0043 seconds per dataset.
In contrast, SBSN, which relies on subgraph extraction and encoding during inference, requires 2658 seconds per dataset, demonstrating its substantial computational overhead compared to node feature-based methods. SELO, due to its lack of constraints on subgraph size, results in a prohibitive inference time of 354353 seconds per dataset, making it unsuitable for practical applications.
SBSN-node, leveraging the node feature distillation module, significantly improves inference effi- ciency while retaining comparable performance to SBSN. On the ML-IM dataset, the inference speed improved by a factor of 618139x compared to SBSN. This highlights the advantage integrating the distillation module for scenarios requiring rapid inference node-based downstream tasks.
Table 4: Inference Time (s) of Different Models on the ML-1M Dataset
Metric
SBGCL SBGNN
SBSN
SELO
SBSN-node
Inference Time (s)
0.00015
0.0043
2658
354353
0.0043
E
Time Estimation
On ML-10M, our model required 27 hours for training. In contrast, SELO lacks strict constraints on subgraph size during the matrix computation phase, resulting in large-scale matrix operations. Consequently, the estimated training time for SELO is approximately 152,000 hours, which is impractical and unacceptable.
F
Analysis of GPU Memory Consumption
Table 5: GPU Memory Consumption (MiB) across Different Models and Datasets
Model
U.S. House
ML-1M
ML-10M
Amazon-Book
Amazon- Book-51M
SBSN
5404
18273
18297
18282
24959
SBGNN
951
22823
OOM
OOM
OOM
SBGCL 1178
28031
OOM
OOM
OOM
As shown in Table 5 we evaluate the GPU memory consumption of three models (SBSN, SBGNN, and SBGCL) across four datasets: U.S. House, ML-1M, ML.-0M,, Amazon-Book, and Amazon- Book-51M. All experiments were performed using an NVIDIA A100 80GB PCIe GPU, ensuring consistent computational environment.
SBSN exhibits superior scalability and efficiency compared other models. successfully operates on all four datasets with memory usage ranging from 5,404 MiB (U.S. House) to 24,959 MiB Book-51M), demonstrating
capability handle large-scale datasets while keeping memory consumption manageable. Notably. compared to the 18,273 MiB used on ML-1M, the memory usage on Amazon Brnazon-Book-Sa 1M increases by 6,686 MiB. This increment precisely corresponds to the additional memory required to store node feature tensors. Specifically, the theoretical memory cost can be computed as
(IUI + IV]) x d x Chp32 x 3 = 18,293,070 x 32 x 4 x 3 bytes 2 6,699 MiB,
where d denotes the feature dimension, C1ps2 the number of bytes per 32-bit float, and the factor accounts for the parameter, gradient, and optimizer states.
In contrast, SBGNN and SBGCL encounter out-of-memory (OOM) issues on the larger datasets (ML-10M and Amazon-Book) highlighting their limitations in scalability. Although SBGNN uses 951 MiB on the smallest dataset (U.S. House), its memory consumption rises significantly to 22823
23

---

MîB on ML-1M, suggesting poor memory efficiency as dataset size increases. Similarly, SBGCL uses 1178 MiB on U.S. House but fails execute on datasets larger than Amazon-Book.
Overall, the results highlight SBSN's robust memory management and scalability, enabling it to effectively handle large-scale datasets where competing models fail due excessive GPU memory demands.
G Performance Large Scale Datasets
Table 6: Performance (average + standard deviation) on Large-scale Datasets
Dataset
Metrie
Node2vec
SOCN SGCL
SEGNN
SBGCL
SELO
SBSN
SBdN-node
AUC
54.9
ODM
TLE 7..2
74,9
ML-10M
Bin-F1
65.6
OOM
TLE
79
78.0
Mac-F1
52.8
OOM
TLE
7.2
74.5
Mic-FI
56.3
OOM
TLE
0.
75.0
AUC
56.3
OOM
TLE 78.
77.5
Bin Fl
90.1
OOM
TIE
86.0 +.11
85.3
MI.32M
Mac-F1
45.5
TLE
0.3
70.4
Mic-Fl
82.0
OOM
TLE 78.8
77.9
AUC
57.9
OOM
TLE 73.1
72.5
Bin-FI
91.8
OOM
TLE 0.2
82.6
Amazon-Book-511
Mac-F1
45.9
OOM
TLE 64.1
63.9
H
Additional Ablation Study
Table 7: Performance (AUC) of Different SBSN Variants
Variant
Bonanza
U.S. House
Amazon-book
ML-1M
Avg. AUC
Base
92.0
88.0
74.5
74.3
82.2
T=1400, w/o connect
91.0
83.5
71.5
72.5
79.3
w/o node
69.6
87.5
74.0
73.4
76.3
T=100, low
91.1
82.7
73.1
72.4
79.3
T=100, rand
92.0
84.7
73.5
71.7
80.2
T=100, high
93.0
84.0
73.2
70.9
80.0
Below, we provide supplementary experimental table that evaluates different variants of SBSN. The experimental settings remain consistent with those described in the main text.
w/o connect:
Replacing the Topological Subgraph Extractor with independent random 2-hop neighbor sampling (resulting in T = 1400) produces performance similar to SGRL. This comparison illustrates that our sampling strategy. which focuses on extracting connected topological subgraphs (with = 800), is critical to achieving higher performance.
Traditional subgraph extraction algorithms [ sample subgraph Gsub from several layers of the neighborhood around the target nodes u and v. These methods typically perform undirected message passing over the extracted subgraph. However, these subgraphs include numerous nodes that do not appear in any simple path connecting and v within Gsub, leading to unnecessary computational overhead. In contrast, passing, effectively avoiding this issue. The subgraph embedding aggregates information only from all simple paths in Gaub that connect u and v.
method extracts topological subgraphs and performs directed message
For example, on the ML- IM dataset-thh the densest graph in our experiments- found that two-hop neighbor sampling with T 1400 produces results similar to those from our Topological Subgraph Extractor with T 150. This comparison highlights the high efficiency of our sampling algorithm.
w/o node: Removing node features and replacing them with random vectors leads to performance drop, especially on Bonanza dataset. This suggests that the high-quality global node features learned in the local subgraph training contribute significantly to the performance of SBSN. Our subgraph sampling method guarantees that every node the sampled subgraph lies on a simple path connecting the target nodes and In contrast, simple two-hop neighbor sampling for and

---

separately does not offer such guarantee, which significantly reduces the efficiency in information utilization.
Different Sampling Strategies: The experiments with fixed subgraph size (T = 100) and varying heuristic sampling strategies (low, random, high degree) indicate that the optimal strategy differ by dataset. We chose the random sampling strategy for the baseline due to its overall superior performance across datasets.
Theoretical Calculation for the Number of Topological Subgraph Layers
Let T' be the total number of nodes in the topological subgraph and p be the probability of an edge existing between any two distinct nodes (i.e., the graph density). Because the first layer only contains single node u and the last layer only contains node v, let K of mid-layers. The T nodes are divided equally into K mid-layers, so each mid-layer contains ny TT/K* nodes.
the number
To calculate the expected number of such paths, denoted by E(K*), we first consider the number of possible unique sequences of nodes, from each mid-layer. There (T/K*) choices for node from each mid-layer. Thus, there are (T/K*) distinct potential sequences of K* nodes, one from each layer.
For any single such sequence (11, ......, UK-) ) to constitute actual path, there must be K - 1 edges present: (V1, U2), (02, vz),.... (UK--1, Ug-). Assume the sampled subgraph as an Erdós- Rényi random graph G(T, p), the probability of any specific edge existing between nodes in different layers is p. and these edge existences are independent. Therefore, the probability that all K required edges for specific sequence exist is p -1.
By the linearity of expectation, the total expected number of paths E(K*) is the product of the number potential node sequences and the probability of any one such sequence forming path:
T K
E(K)
K-
To find the optimal K** that maximizes E(K*), it is often easier to maximize its natural logarithm, In In(E( E()*)), since the logarithm is monotonically increasing function.
T k-
In(E(K")) = In
K
T
= KK* In
+ (K* (K*- in)ppp)
K*
= =K'(In(T) - In(K")) + (K* 11*
Treating K as continuous variable for the purpose of optimization, we differentiate (n(E(K)))
with respect to K* and set the derivative zero:
d In(E(K))) dk= [K* In(T) K" In(K") K" In(p) In(p)]
d
dk*
-In[T) - (In(K*) K* 1
In(p) 0
K
In(TT) - In(K') - 1+ In(p)
Setting the derivative to zero to find the critical points:
In(T) In(K*) - 1 In(p) =
In(K*) II((T) + In(p)
In(K*) >I(TTp) In(e)
In(K*) = In Tp
25

---

Thus, the value of K that maximizes ((K*) when K is treated as a continuous variable is:
Tp
K
(4)
where e the base of the natural logarithm. In practice, K must be an integer, and typically K 2 2 (for a path to exist between at least two layers).
In our experiments on real-world datasets, we empirically investigated the optimal K = K + 2 Max [e] + 2, with the additional constraint that K is an even number. Under a default setting for the sampled subgraph size T 800, we calculated that the optimal K value a majority of the datasets, including Bonanza, Amazon-book, ML-10M, ML-32M, and Amazon- book-51M. Consequently, we uniformly adopted K 4 practical setting across main experiments for consistency and based on these findings. Furthermore, for dense datasets where theoretical calculations or initial observations suggested an optimal > 4 (U.S. House, ML-IM), we also experimented with K = 6. However, this increase in the number of layers did not yield an improvement final performance, which we attribute the smoothin phenomenon 22 that can affect Graph Neural Networks with deeper multi-hop message passing.
4 for
Table 8: Statistics on Signed Bipartite Networks
Bonanza
U.S. House
ML-IM
Amazon-Book
ML-I0M
ML-32M
Amazon-Book-51M.
U
7,919
515
6,040
35,736
69,878
200,948
2,930,451
V
1,973
1,281
3,952
38,121
10,677
84,432
15.362,619
36,543
114,378
1,000,209
1,960,674
10,000,054
32,000,201
51,311,613
0.002339
0.173375
0,041902
0.001439
0.0134033
1.001886
0.000001
T
800
800
800
800
800
800
800
K comi
0.69
51.02
12.33
0.42
3,94
0.56
0.00
K
4
53
14
4
4
4
26


Reviews:
[{"review_id": "KJH7f7Ji5n", "reviewer": "Reviewer_pqpu", "summary": "This paper proposes a new framework for making signed link prediction in bipartite networks. It mainly consists of subgraph extraction, message passing, and an optional subgraph representation distillation module to accomplish the task. Experiments show that the proposed method outperforms signed link prediction baselines on public datasets.", "questions": "Please see weaknesses.", "limitations": "na", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The work is targeting an important problem, with a carefully designed framework solution (despite some places that might need further discussion and/or refinement). The distillation module is an interesting and novel design.\n2. The paper is well presented and easily understandable\n2. The experiment shows significant improvement over baselines, verifying the effectiveness of the proposed method.\n\nWeaknesses:\n1. My main concern is that the proposed link prediction framework seems to ignore distance encoding/labeling which is a very important module that significantly improve GNN's ability in doing link prediction. For example, see [1] - [3]. I also noticed that the node features in this paper are initialized from normal distributions which means that they are not extremely informative in helping with prediction. In this case, adding distance encoding/labeling is even more crucial. I think it would be important to (a) discuss these works in related works and (b) incorporate some of their keys designs for signed link prediction task (or discuss why not to)\n2. The baselines seem to mainly consist of specialized GNNs for signed link prediction. Following Weakness 1, can the authors further adapt and compare with some of the related works I mentioned above for signed link prediction experiment?\n3. On Bonanza the distilled model outperforms the full model. There seems a lack of explanation for this. Can the authors provide more discussion?\n\nI would be happy to raise my scores once my concerns are addressed.\n\n\n[1] Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning\n[2] Link Prediction Based on Graph Neural Networks\n[3] Graph Neural Networks for Link Prediction with Subgraph Sketching", "was_revised": true, "final_justification": "After the discussion period, I think this paper looks fine to me to accept, with decent novelty and good experiments.", "rebuttal": "We sincerely thank you for your detailed and constructive feedback. We will now address the weaknesses and questions you raised.\n\n### **Re: Weakness 1 & 2 - The role of Distance Encoding and Baselines**\n\nThis is an excellent point. Distance encoding (DE) and structural labeling techniques, as you highlighted in the suggested papers [1-3], are indeed powerful tools for GNN-based link sign prediction, especially when initial node features are not highly informative. We appreciate your suggestions and agree that a discussion of these works is important.\n\n**1. Discussion in Related Works:**\nWe concur and will add a dedicated discussion of these structural encoding methods to our Related Works section in the revised manuscript. We will highlight their importance in providing GNNs with crucial positional information.\n\n**2. Incorporating DE and Comparison:**\nTo directly investigate the impact of DE on our framework, we conducted a new experiment based on your feedback. Instead of using randomly initialized node features, we implemented a distance encoding scheme. Specifically, we randomly sampled 32 anchor nodes from the entire graph and computed the shortest path distance from each node to these anchors, using the normalized result as a 32-dimensional initial node feature vector. We tested this on the ML-1M dataset, which showed low variance in our original experiments.\n\nThe results are as follows:\n| Model Variant (on ML-1M) | AUC | Bin-F1 | Mac-F1 | Mic-F1 |\n| :--- | :--- | :--- | :--- | :--- |\n| SBSN (Original, random features) | 74.2 | **77.2** | 74.0 | 74.4 |\n| SBSN (with Distance Encoding) | **74.4** | 77.0 | **74.1** | 74.4 |\n\nAs shown, incorporating DE as initial features provides a marginal improvement in AUC. To understand this limited impact more deeply, we conducted a more comprehensive analysis that yielded two key insights:\n\n1.  Counterintuitively, using highly informative, pre-trained node embeddings from strong baselines (SBGNN, SBGCL) or even our own SBSN-node as initial features led to a **decrease** in performance. Our analysis suggests this is due to an overfitting-induced \"shortcut.\" The pre-trained embeddings are so highly optimized for 1-hop link sign prediction that when used as initial features, our SBSN model learns to rely almost exclusively on decoding the link sign directly from the features of nodes `u` and `v`. This behavior effectively bypasses the crucial step of reasoning over the subgraph's structural information, undermining the core strength of our model.\n\n2.  We observed that the model with randomly initialized features converges more slowly than the one initialized with Distance Encoding (DE). This suggests that the randomly initialized model likely dedicates part of its training process to implicitly learning the kind of positional information that DE provides explicitly from the start.\n\nWe also found that increasing the number of anchor nodes for DE to 128 brought no further practical improvements.\nAdditionally, we experimented with treating DE as a fixed, non‑learnable encoding, combined with randomly initialized and trainable node features. This configuration likewise did not yield further gains.\n\nTherefore, while DE offers a better starting point, the final performance remains similar because the model can eventually learn the necessary structural context from the data itself.\n\nThis comprehensive analysis strongly confirms our central hypothesis: **the predictive power of SBSN stems primarily from its ability to dynamically learn from topological information, rather than relying on static, global node features.** Our **Topological Subgraph Extractor** and **Directed SignFlow Aggregator** are explicitly designed to force the model to reason about the structural patterns within the local neighborhood for each query.\n\nRegarding adapting the models you mentioned as baselines, we sincerely appreciate the suggestion. Due to the time constraints of the rebuttal period, we were unable to complete the non-trivial task of adapting these general link prediction frameworks for the specific signed bipartite graph setting. However, **we commit to including these additional baseline comparisons in the final camera-ready version of the paper.**\n\n### **Re: Weakness 3 - Distilled Model Outperforming the Full Model on Bonanza**\n\nYou correctly pointed out the curious result on the Bonanza dataset where the distilled model (SBSN-node) appeared to outperform the full model (SBSN). We suspected this might be an artifact of statistical variance given the high class imbalance in this dataset.\n\nTo verify this, we conducted a more extensive set of experiments on Bonanza, running **15 trials (3 different random seeds across 5 different train-val-test splits)** to obtain more stable and reliable results.\n\nThe updated, more robust results are as follows:\n\n| Model (on Bonanza) | AUC | Bin-F1 | Mac-F1 | Mic-F1 |\n| :--- | :--- | :--- | :--- | :--- |\n| SBSN | 90.67 ± 2.08 | **97.68 ± 1.12** | **72.69 ± 4.97** | **95.58 ± 2.06** |\n| SBSN-node| **90.73 ± 2.23** | 97.15 ± 1.41 | 70.26 ± 5.42 | 94.59 ± 2.58 |\n\nThese more rigorous results demonstrate that the performance of SBSN and SBSN-node is, in fact, **statistically indistinguishable**. The initial observation was indeed due to random variance. This confirms that our node feature distillation module effectively preserves the predictive power of the full subgraph-based model while offering a massive gain in inference efficiency. We will update the results table in the manuscript with these more stable figures and add a note clarifying this.\n\nWe are grateful for your insightful questions, which have prompted us to conduct further experiments and analysis that strengthen our paper. We believe these clarifications and new results directly address the concerns you raised. We will incorporate all these points into the revised manuscript and are confident that these changes will significantly improve its quality and clarity."}, {"review_id": "IuEqJYZZKC", "reviewer": "Reviewer_of7A", "summary": "The paper introduces the SignFlow Bipartite Subgraph Network (SBSN), a new approach for link sign prediction in signed bipartite graphs, which are prevalent in domains like e-commerce and recommendation systems. SBSN addresses scalability and efficiency challenges in large-scale graphs through three key components: a topological subgraph extractor, a directed SignFlow Aggregator, and a node feature distillation module. The method achieves efficient memory scaling and inference, and superior performance on medium and large scale datasets, including Bonanza, MovieLens, and Amazon-Book.", "questions": "1. In Section 4.1, what's the sampling schedule used for the different layers? Based on the proof of Theorem 1, it seems to be uniform across layers, but it probably makes sense to mention (although having in mind the suggested $K_opt$ this would be constant per layer and not as relevant, but I think explicitly commenting on this could be useful).\n\n2. Theorem 1 derives an optimal number of topological layers ($K_{opt} = \\max(2, \\lfloor \\frac{T \\cdot p}{e} \\rfloor) + 2$ to maximize expected paths, but the paper does not fully validate this empirically across datasets. If not too hard, would it be possible to empirically look at how different values of $K$ affect the results on some of the datasets you have in the empirical section? \n\n3. Could the authors expand on the potential failure cases and more generally limitations in section 6?  \n\n4. A known issue for some of the datasets covered (e.g. Bonanza) is that the number of positive vs negative edges might be imbalanced. Can you confirm that something like this doesn't have a negative affect on the proposed method?", "limitations": "The authors do mention some potential limitations of the approach without distillation, but a more complete discussion could be useful.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper is clear and easy to follow. The approach is also well-motivated.\n\n- The approach is novel:\n    - SBSN's topological subgraph extractor focuses on nodes along simple paths connecting target nodes, reducing computational overhead compared to traditional $k$-hop neighbour sampling.\n    - The edge-based message passing is under-exploited in the link sign prediction domain, and SBSN makes good use of this.\n    - To the best of my knowledge, the idea of having a distillation module for fast inference by approximating subgraph features with node features is new to the GRL domain (with some works doing something similar but in different sub-spheres).\n\n- The empirical evaluation is substantial, with many relevant baseline covered. Ablation studies are also presented.\n\n**Weaknesses:**\n\n- The related works section (Section 2) covers alternative approaches but does not clearly delineate SBSN’s novel contributions relative to competitive methods like SBGNN, SBGCL, or SELO. The section does give good overview of the alternative approaches, but having an explicit comparison for which components of SBSN are novel would be useful. \n\n- There is lack of explicit complexity discussion in the main body of the paper. It's slightly hard to follow unless the reader follows the Appendix and simply having $O(poly(T))$ could confuse readers.\n\n- Theorem 1 derives an optimal number of topological layers to maximize expected paths, but the paper does not fully motivate the choice for this proxy, or validate this empirically.", "was_revised": true, "final_justification": "After the discussion period, I think this paper looks stronger than before, and all my questions were answered.", "rebuttal": "We are extremely grateful for your positive evaluation and thoughtful comments. We sincerely appreciate your constructive feedback, which will undoubtedly help us further improve the quality of our manuscript.\n\nWe would like to address your specific questions and suggestions below.\n\n### **Re: Weakness 1 - Delineating Novelty in Related Works**\n\nWhile we provided an overview of existing methods, we agree that explicitly delineating SBSN's novel contributions in comparison to key competitors within Section 2 would significantly enhance clarity.\n\nIn the revised manuscript, we will add a dedicated paragraph at the end of Section 2 to explicitly contrast our approach. Specifically:\n*   **Versus SBGNN/SBGCL:** We will highlight that these methods operate on the entire graph, leading to scalability challenges that our subgraph-based approach directly solves, enabling sublinear memory growth.\n*   **Versus SELO:** We will clarify that while SELO is also subgraph-based, our **Topological Subgraph Extractor** is fundamentally different as it focuses on nodes within connecting paths, improving information efficiency. Furthermore, our **Directed SignFlow Aggregator** uses an edge-centric message-passing scheme, which is distinct from SELO's matrix-based encoding of higher-order cycle patterns.\n*   **Novelty of Distillation:** We will also re-emphasize that the **Node Feature Distillation** module is, to our knowledge, a novel contribution in this specific domain, designed to bridge the gap between the performance of subgraph models and the inference efficiency of node-feature-based models.\n\n### **Re: Weakness 2 - Complexity Discussion in Main Body**\n\nWe agree completely that a more explicit discussion of complexity in the main body is necessary for clarity. Relying solely on the appendix was a space-saving measure, but it hinders readability.\n\nIn our revision, we will move a condensed but more informative version of the complexity analysis from Appendix A into the main body (likely at the end of Section 4.2). We will replace the general `O(poly(T))` with more concrete terms, explaining that the time complexity for encoding a subgraph is dominated by the message passing stage, which is upper-bounded by `O(T^2 * d^2)`, where `T` is the subgraph node limit and `d` is the feature dimension. This will give readers a much clearer understanding of the model's computational cost without needing to consult the appendix.\n\n### **Re: Weakness 3 & Question 2 - Motivation and Empirical Validation of Theorem 1**\n\nYou have raised a very important point regarding the motivation and empirical support for Theorem 1.\n\n**1. Motivation for the Proxy:**\nOur choice to maximize the expected number of distinct paths is based on the intuition that a richer, more diverse set of information pathways between two target nodes (`u` and `v`) provides a stronger and more robust structural signal for link sign prediction. More paths mean more evidence to aggregate, reducing the risk of relying on a single, potentially noisy or misleading connection. We will add this explicit motivation to Section 4.1 just before introducing the theorem.\n\n**2. Empirical Validation of K:**\nThis is an excellent suggestion. Our theoretical derivation in Appendix G shows that the optimal `K` depends on graph density and the node budget `T`. For our default setting of `T=800`, the theory suggests `K=4` is optimal for most of our datasets. We used `K=4` as a uniform setting across our main experiments for consistency and based on these findings.\n\nTo directly address your question about empirical validation, we did experiment with different values of `K`. For instance, on the denser U.S. House dataset, while the theory might suggest a larger `K`, we found that increasing `K` to 6 (with `T=800`) did not lead to any improvement in AUC. In fact, we observed a performance drop early in the training process. We attribute this to the well-known over-smoothing phenomenon in deeper GNNs, where increasing the number of message-passing layers (hops) can make node representations overly similar, thus harming performance. This empirical finding supports our decision to use a moderately deep architecture with `K=4`, which strikes a balance between capturing sufficient path information and avoiding the pitfalls of over-smoothing. We will add this discussion to the Appendix to provide empirical context for our choice of `K`.\n\n### **Re: Question 1 - Sampling Schedule for Layers**\n\nYou are correct in your inference. Our current implementation divides the node budget `T` (minus the two endpoint nodes) as evenly as possible across the `K-2` intermediate layers. For instance, with `T=800` and `K=4`, we sample approximately `(800-2)/2 = 399` nodes for each of the two intermediate layers. We will explicitly state this uniform allocation strategy in Section 4.1 for better clarity.\n\n### **Re: Question 3 & Limitations - Failure Cases**\n\nThis is a valuable suggestion. A more thorough discussion of limitations will strengthen the paper. We will expand Section 6 to include potential failure cases:\n1.  **Extreme Sparsity:** In graphs where target nodes `u` and `v` are very distant or disconnected within a few hops, our extractor may fail to find meaningful paths. In such cases, the model's prediction would degrade, relying mostly on the randomly initialized features.\n2.  **Dominating Misleading Paths:** If the local subgraph is dominated by a few strong paths that suggest an incorrect sign (a common issue in complex social networks), our model might overfit to this misleading evidence.\n3.  **Heuristic Sampling:** Our current sampling strategies (random, high/low degree) are heuristic. A more sophisticated, learnable sampling mechanism could potentially yield better subgraphs but would also increase model complexity and training time.\n\n### **Re: Question 4 - Handling Imbalanced Datasets**\n\nYou raise a crucial point about the class imbalance present in datasets like Bonanza. We can confirm that this was a key consideration in our design. To address this, we employ a **weighted binary cross-entropy loss function**, as described in Section 4.4. The weight for each class in the loss calculation is set to be inversely proportional to its frequency within the training batch. This ensures that the model pays sufficient attention to the minority class (typically negative links) and prevents it from being biased towards simply predicting the majority class. This technique is critical to achieving the strong Mac-F1 and AUC scores reported.\n\nOnce again, we thank you for your insightful review and high rating. Your suggestions are invaluable, and we are confident that incorporating them will make our paper stronger and clearer. We will diligently work on the revisions you have proposed."}, {"review_id": "2GprKA0mfG", "reviewer": "Reviewer_jwwF", "summary": "This paper introduces SignFlow Bipartite Subgraph Network (SBSN), a novel framework for link sign prediction in large-scale signed bipartite graphs. Unlike conventional GNN approaches that rely on full-graph message passing or generic subgraph sampling, SBSN incorporates three key innovations: 1) topological subgraph extraction; 2) SignFlow aggregator, and 3) node feature distillation module. The method achieves state-of-the-art performance on seven benchmark datasets, demonstrating significant gains in both predictive accuracy and inference efficiency.", "questions": "1. Figure 3 discrepancy: In the initial graph, there is no edge between nodes v2 and u5, yet they appear connected in the sampled subgraph. Could the authors clarify where this connection comes from, especially since the subgraph is claimed to be extracted from the original bipartite graph?\n\n2. Loss composition: The total loss function is simply a sum of distillation and binary cross-entropy terms. Would model performance benefit from weighting these two losses differently? How sensitive is the method to this balance?\n\n3. Ablation on edge vs node contributions: Given that distillation involves node-level features, how can one isolate and verify that the performance gains come from edge-feature modeling (as claimed) rather than from node-feature distillation? A more detailed ablation study on this point would strengthen the paper.", "limitations": "The path-constrained subgraph extraction strategy, while efficient and structurally coherent for bipartite graphs, may not generalize well to non-bipartite or heterogeneous graph structures.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The paper effectively combines three components to improve the training and inference efficiency for large-scale signed link prediction.\n\n2. The proposed method demonstrates strong empirical performance across diverse real-world datasets.\n\n3. Theoretical analysis is provided to justify the efficiency benefits of the path-constrained subgraph extraction strategy.\n\n4. The paper is generally well-written and methodologically clear, with logical explanations and organization of the proposed components.\n\nWeaknesses\n\n1. The lack of accessible source code and the unavailability of the Bonanza dataset (which the authors highlight as particularly important) significantly impair reproducibility and independent validation.\n\n2. The main contributions are not clearly summarized in the introduction, making it harder for readers to grasp the novelty at a glance.\n\n3. Among the three techniques proposed, only the path-constrained subgraph extraction appears novel. It effectively replaces the traditional k-hop neighborhood with a more targeted strategy. However, the other components—edge-based attention and feature distillation—have been explored in previous works such as R-GCN, SELO, and SimGCL. Moreover, the subgraph extraction mechanism may be overly specialized for bipartite structures, potentially limiting the method’s generalizability to other types of graphs.\n\n\n[1] R-GCN: Modeling Relational Data with Graph Convolutional Networks\n[2] SELO: Subgraph-Enhanced Signed Link Prediction from Signed Bipartite Graphs\n[3] SimGCL: Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation", "was_revised": false, "final_justification": "", "rebuttal": "We are very grateful for your detailed review and constructive feedback. We are pleased that you found our method to be empirically strong, theoretically justified, and clearly written. Your insightful questions and comments will be invaluable in helping us refine and strengthen our paper.\n\nWe will address your specific weaknesses and questions below.\n\n### **Re: Weakness 1 - Reproducibility (Source Code and Dataset)**\n\nWe sincerely apologize for not making the link to our resources more prominent. To ensure full reproducibility and facilitate independent validation, we have made our **source code and the Bonanza dataset available in an anonymous repository**:\n\n**Link: [https://anonymous.4open.science/r/SBSN-B484](https://anonymous.4open.science/r/SBSN-B484)**\n\nWe will add this link to the main body of the paper in the final version to ensure it is easily accessible to all readers.\n\n### **Re: Weakness 2 - Summary of Contributions in Introduction**\n\nThis is an excellent suggestion for improving the paper's clarity. We agree that a concise, explicit summary of our contributions at the beginning would help readers grasp the core novelties more quickly. In our revision, we will add a bulleted list at the end of the introduction that clearly outlines our main contributions:\n1.  A novel **path-constrained subgraph extraction** strategy that improves information efficiency over traditional k-hop sampling for link prediction.\n2.  A specialized **SignFlow Aggregator** that leverages edge-based attention within subgraphs to capture directional information flow.\n3.  An efficient **node feature distillation** module that bridges the gap between subgraph models' performance and feature-based models' inference speed, a novel application of distillation for this task.\n\n### **Re: Weakness 3 - Novelty of Components and Generalizability**\n\nWe appreciate your perspective on the novelty of our components and would like to offer some clarification.\n\n*   **On Edge-based Attention and Feature Distillation:** While we agree that edge-based attention and knowledge distillation are not new concepts in the broader GNN literature, we argue that their specific formulation, application, and purpose within SBSN are novel for the task of signed link prediction.\n    *   **SignFlow Aggregator vs. R-GCN:** R-GCN uses relation-type-specific weights for message passing on a static, multi-relational graph. Our SignFlow Aggregator operates differently: it computes dynamic attention scores for *individual edges* within a temporary, query-specific subgraph. Its purpose is not to model global relation types, but to capture the contextual importance and directional flow of information along paths for a *single* link prediction task.\n    *   **Distillation vs. SimGCL:** SimGCL and related works primarily use distillation for data augmentation within a contrastive learning framework. Our module serves a fundamentally different purpose: **model compression and acceleration**. We distill the rich structural knowledge learned by the complex subgraph-based model into simple node embeddings to achieve fast inference. This is a novel application of distillation to solve the well-known efficiency problem of subgraph-based models in the inference phase.\n\n*   **On Generalizability:** You raise a fair point that our current subgraph extraction is specialized for bipartite structures. This was a deliberate design choice to excel at this important and challenging problem class. However, we believe the core principle—sampling subgraphs constrained to connecting paths—is a generalizable idea. We will acknowledge in the limitations section that adapting it to other graph types (e.g., general non-bipartite or heterogeneous graphs) is a non-trivial but promising direction for future research.\n\n### **Addressing Your Questions**\n\n**1. Figure 3 Discrepancy:**\nThank you for your keen observation and for catching this error. You are correct; the edge between v2 and u5 in the sampled subgraph is a mistake in the illustration, as it does not exist in the original graph. This is a typo, and we sincerely apologize for the confusion. We will correct this figure in the final version of the paper to accurately reflect the extraction process.\n\n**2. Loss Composition:**\nThis is a great question. We used a simple sum for the total loss function because our training strategy for the distillation module makes the model robust to the specific weighting. Specifically, the training is performed in stages: we first train the module using only the distillation loss (L_sim) to ensure the node embeddings effectively approximate the rich subgraph features. Once this alignment is achieved, we introduce the binary cross-entropy loss (L_bce) to fine-tune the model for the link sign prediction task. This staged approach ensures that the core knowledge is transferred first, making the final model performance insensitive to the `lambda` hyperparameter that would otherwise balance the two losses. We will clarify this training procedure in the paper.\n\n**3. Ablation on Edge vs. Node Contributions:**\nThis is a very insightful question. The key to isolating the contribution of edge features lies in our ablation study presented in **Table 2**.\n*   The model \"SBSN w/o edge\" demonstrates a significant performance drop compared to the full SBSN model. This result directly confirms that **edge features are crucial for the performance of the primary subgraph-based model**.\n*   The node distillation module (in SBSN-node) learns to approximate the output of the full SBSN model. Therefore, the quality of the final distilled node features is directly dependent on the richness of the information provided by the source model.\n*   Since the model without edge features is demonstrably weaker, the knowledge it could provide for distillation would also be inferior. Thus, the strong performance of SBSN-node implicitly relies on the crucial information that was captured by the edge features during the initial, more complex training stage. We will clarify this chain of reasoning in our ablation study section to make this point more explicit.\n\nOnce again, we thank you for your valuable and detailed feedback. We believe that by addressing these points—providing the code, clarifying our contributions, correcting the figure, and expanding our discussion on novelty and limitations—we can significantly improve the paper. We hope our responses have addressed your concerns."}]

Author rebuttal:

Meta-review: This paper introduces SignFlow Bipartite Subgraph Network (SBSN), a scalable and effective method for link sign prediction in large-scale signed bipartite graphs. It combines (1) path-constrained subgraph extraction, (2) a directed edge-centric message passing aggregator, and (3) a node feature distillation module for efficient inference. Several initial concerns have been well addressed in the rebuttal, and after the rebuttal, all the reviewers think this is a good paper: proposing a novel method and with sufficient empirical results.
Decision: Accept (poster)