Structure Balance and Gradient Matching-Based Signed Graph Condensation
Authors: Rong Li, Long Xu, Songbai Liu, Junkai Ji, Lingjie Li, Qiuzhen Lin, Lijia Ma
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on six datasets demonstrate that SGSGC achieves excellent performance. On Epinions, 94% test accuracy of training on the original signed graph, while reducing their graph size by 99.95% 99.99%, and there exist 2.24% 6.26% accuracy improvements for link sign prediction compared to the state-of-the-arts. |
| Researcher Affiliation | Academia | 1College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, China 2College of Big Data and Internet, Shenzhen Technology University, Shenzhen, China EMAIL |
| Pseudocode | Yes | Algorithm 1: SGSGC for Signed Graph Condensation Input: Training signed graph data G = (A, X) Output: Condensed signed graph data S = (A , X ) 1: Initialize θ0 Pθ0. 2: Let k = 0. 3: while k K 1 do 4: Compute A = GENψ(X ) 5: Compute Lgm Eq. (5) 6: Compute Lsm Eq. (12) 7: Compute Lfs Eq. (13) 8: Compute Ltotal Eq. (14) 9: if t%(τ1 + τ2) < τ1 then 10: Update X k+1 Eq. (15) 11: else 12: Update ψk+1 Eq. (16) 13: end if 14: Sparsify A according to Eq. (4) 15: l = 0. 16: while l τθ do 17: Update θl+1 Eq. (17). 18: end while 19: Sparsify A according to Eq. (4) 20: end while |
| Open Source Code | Yes | Code https://github.com/Bao Fit/SGSGC |
| Open Datasets | Yes | We conducted experiments on five real-world network datasets from diverse domains, including collaboration, business, and social interactions, to validate the effectiveness of the proposed SGSGC, namely Bitcoin-alpha (Kumar et al. 2018), Wiki (Leskovec, Huttenlocher, and Kleinberg 2010a), Wiki-rfa (West et al. 2014), Slashdot (Leskovec, Huttenlocher, and Kleinberg 2010b), and Epinions (Leskovec, Huttenlocher, and Kleinberg 2010b). |
| Dataset Splits | Yes | To create training and testing sets, we randomly split the positive and negative edges of each dataset in an 8:2 ratio. |
| Hardware Specification | No | No specific hardware details such as GPU models, CPU types, or memory specifications are mentioned in the paper. |
| Software Dependencies | No | The paper mentions several algorithms and model architectures (e.g., SGCN, MLP, Kaiming initialization, SGD) but does not provide specific software dependency versions (e.g., Python 3.x, PyTorch 1.x, TensorFlow 2.x, CUDA 11.x). |
| Experiment Setup | Yes | Hyper-parameter setting. For all datasets, the dimensionality of node attribute features in the original graph is fixed at 64. During the condensation process, for all graph condensation methods, the outer loop T is set to 600, and K is set to 20. The update steps τ1 and τ2 are set to 20 and 30, respectively. Moreover, in the GNN training steps, τθ is set to 15 on the GNN. For GDC, we use a two-layer MLP with hidden units fixed at 32 to obtain node embeddings. For other graph condensation methods, a two-layer MLP is used to construct GENψ. Specifically, for the small dataset Bitcoin-alpha, the hidden units are set to 128, while for the other datasets, the hidden units are set to 256. We consistently use a two-layer SGCN (Derr, Ma, and Tang 2018) to obtain node embeddings, with hidden units fixed at 32. The task of predicting the sign is treated as a binary classification problem, employing a single-layer MLP to output the probability of a positive sign. The learning rates µ1, µ2, and µ3 are set to 0.0001, 0.0001, and 0.01, respectively. During testing, we use a unified SWGCN framework with a training epoch of 600 and a learning rate of 0.01 to ensure fairness in evaluation. |