Beyond Node-Centric Modeling: Sketching Signed Networks with Simplicial Complexes
Authors: Wei Wu
Xuan Tan
Yan Peng
Ling Chen
FangFang Li
Chuan Luo
Venue: NeurIPS 2025 poster ()
Keywords: Signed Networks
Edge Embedding
Simplicial Complexes
Locality Sensitive Hashing
Link Sign Prediction
Primary area: general_machine_learning

Abstract: Signed networks can reflect more complex connections through positive and negative edges, and cost-effective signed network sketching can significantly benefit an important link sign prediction task in the era of big data. Existing signed network embedding algorithms mainly learn node representation in the Graph Neural Network (GNN) framework with the balance theory. However, the node-wise representation learning methods either limit the representational power because they primarily rely on node pairwise relationship in the network, or suffer from severe efficiency issues. Recent research has explored simplicial complexes to capture higher-order interactions and integrated them into GNN frameworks. Motivated by that, we propose  EdgeSketch+,  a simple and effective edge embedding algorithm beyond traditional node-centric modeling that directly represents edges as low-dimensional vectors without transitioning from node embeddings. The proposed approach maintains a good balance between accuracy and efficiency by exploiting the Locality Sensitive Hashing (LSH) technique to swiftly capture the higher-order information derived from the simplicial complex in a manner of no learning processes. Experiments show that EdgeSketch+ matches state-of-the-art accuracy while significantly reducing runtime, achieving speedups of up to $546.07\times$ compared to GNN-based methods.

Beyond Node-Centric Modeling: Sketching Signed Networks with Simplicial Complexes
Wei Wu!
Xuan Tan'
Yan Peng'
Ling Chen² Fangfang Li Chuan Luo
"chool of Computer Science and Engineering, Central South University
Australian Artificial Intelligence Institute, University of Technology Sydney
Xianggjang Laboratory
School of Software, Beihang University
william. third. wu@gmail. com
{tanxuan, pengyan, lifangfanm (agggfann)@ssuu Scsu. edu, cn ling. wwwneuts.eeeeeecooeo eu chuanluo@buaa edu.cn
Abstract
Signed networks reflect more complex connections through positive and nega- tive edges, and cost-effective signed network sketching can significantly benefit important link sign prediction task in the of big data. Existing signed net- work embedding algorithms mainly learn node representation the Graph Neural Network (GNN) framework with the balance theory. However, the node- wise representation learning methods either limit the representational power because they primarily rely node pairwise relationship in the network, suffer from severe efficiency issues. Recent research has explored simplicial complexes to capture higher-order interactions and integrated them into GNN frameworks. Moti- vated by that, we propose EdgeSketch+, simple and effective edge embedding algorithm beyond traditional node-centric modeling that directly represents edges as low-dimensional vectors without transitioning from node embeddings. The proposed approach maintains a good balance between accuracy and efficiency by exploiting the Locality Sensitive Hashing (LSH) technique to swiftly capture the higher-order information derived from the simplicial complex in a manner of no learning processes. Experiments show that EdgeSketch+ matches state-of-the- art accuracy while significantly reducing runtime, achieving speedups of up 546.07x compared to GNN-base methods
Introduction
Signed networks provide richer and more nuanced description of the connections than unsigned networks by differentiating positive and negative relationships. This enables critical applications like analyzing social cohesion through friend/enemy ties and improving recommender systems via positive/negative feedback. Consequently, significant task is link sign prediction, which aims to predict the sign of the edge in a signed network.
Current signed network embedding methods primarily node-wise representation learning in Graph Neural Networks (GNNs) (122), incorporating the balance theory (i.c., a friend of my friends my friend; enemy of my enemies my friend) [10] [T]. Although the node-wise signed network embedding approaches have achieved great success thanks to the balance theory, they either are trapped into the special circumstances of the edges such as isomorphic proximity ineur severe
*Corresponding author:
We have released the source code and the datasets in htt.peee//gghhhheooo///aaaaataap
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

pall
Figure In a signed network, orange and purple edges represent positive and negative signs, respectively. Balance theory suggests vi and enemies, while v11 and Vo6 are indistinct. Edges (V1, vo) and (V11. V66) have isomorphic proximity in node-to-node interactions but differ in a simplicial complex context.
efficiency issues from neural network training. For example, in Figure the balance theory cannot identify the edge (V11, V666 but (v1, r6) (i.e., enemies). Meanwhile, unsigned network embedding methods, including both node embedding (12H18] and edge embedding [19H23], lack mechanisms to capture signed network properties, resulting performance degradation dealing with signed networks.
Furthermore, great many graph embedding methods concentrate the node- wise interaction rela- tionship, but real-world networks are increasingly complicated, rendering node-to-node relationships incompetent delineate higher-order interaction relationships in the networks. For example, social network analysis emphasizes friend circles rather than individual pairs [24). As shown in Figure [ edges (v1, v6) and (V11, 166), which are isomorphic the node level, differ in higher-order structures
(v11, V66) lies in two triangles while (v1, v6) is in only one. Recent advancements in GNNs have incorporated simplicial complexes 35 which exhibit the powerful representation capability by capturing the complicated. higher-order substructures in the network, yet these approaches demand huge computational cost due massive parameter training.
By contrast, randomization offers high efficiency in algorithm design by avoiding laborious learning processes. A well-established framework, Locality -Senstiv-ee Hashing (LSH) [36). supported by solid theoretical foundation, embeds similar data objects into the same location in low-dimensional space with higher probability than dissimilar ones by randomized hash functions, preserving their relative distances. To our knowledge, most graph hashing methods (37-51 efficiently represent graphs nodes in reduced dimensions in non-learning fashion, though 47 51] enhance graph classification by converting node-based graphs into simplicial complex-bart ones. As this integration remains underexplored. focus on advancing signed network sketching using LSH and simplicial complexes, aiming for robust theoretical guarantees and strong experimental results.
In this paper, we seek to strike a good balance between accuracy and efficiency of sketching the signed network by leveraging the LSH technique to capture higher-order interaction relationship from the simplicial complex. We first propose novel edge structure distance measure tailored for the edge surrounding, which is represented via the convolution operation on the edge itself (i.e., 1-simplex) and all its direct neighborhoods containing the adjacent edges (i.e., 1-simplexes), nodes (i.e., 0-simplexes) and triangles (i.e., 2-simplexes) under the simplicial complex, preserving intricate structural information beyond traditional node-wise neighborhoods (See Appendix C Subsequently, our cost-effective algorithm beyond node-centric modeling, EdgeSketch+, iteratively sketches edge surroundings into low-dimensional binary vectors without learning, while maintaining low computational overhead. Additionally, by doubling the binary representation length, EdgeSketch+ enables integration with linear models, effectively addressing SVM kernel storage issues in large-scale scenarios. In summary, the main contributions of our work are as follows:
To our knowledge, this is the first work introducing simplicial complexes signed networks, significantly improving embedding efficiency and link sign prediction.
We present novel signed network sketching model called EdgeSketch+, which effectively and efficiently represents each signed edge by adopting the LSH technique to capture the oideer-order interaction relationship from the simplicial complex.
The experimental results show that our proposed EdgeSketch++ algorithm enjoys good performance comparable to the state-of-the-art competitors, while remarkably reducing computational expenses, for example, running up to 546.07x faster than the GNN-based signed network embedding methods.

---

2 Related Works
Graph Embedding with Simplicial Complex. In order to cope with the complicated interaction in the graph, the researchers have explored the use of simplicial complex in the GNN framework for applications such as trajectory prediction 34 29), visual inspection [I] and missing data imputation [33] MPSN [35] and SaNN [25] perform graph classification in the message passing mechanism with the simplicial complex, while N&F
[3 outperforms the existing message passing neural networks [4) by adopting differential k-forms on simplicial complexes to augment geometric interpretability. SGAT [26) implements node embedding by injecting simplicial complexes into heterogeneous message passing networks, and SCRaW1 1 (27] learns node representation by random walks on higher-order simplicies. Furthermore, SCN (30) and EdgeRWSE (28) extend node (i.e., O-simplex) embedding to edge (i.e., 1-simplex) embedding on message passing and random walks, respectively; the latter additionally preserves information from local/global positions of the nodes and local/giobal structures in the network based on edge-level random walks.
Signed Network Embedding. The signed networks assign the edges with a richer and more nuanced description such that the positive and negative edges are distinguished. In particular, link sign prediction is an important task unique to the signed networks and thus has attracted much attention from researchers. To our knowledge, most of the existing signed network embedding
algorithms T4 5 6
55
g are node-wise representation under the balance theory [TO] m. They
usually apply a certain GNN method (e.g.. GCN [53] GAT [22 GCL [56]. etc.) the signed networks based on the balance theory. RSGNN M aims to improve the robustness of the signed GNN methods by reducing the affect of noisy edges. Furthermore, GS GS-GNN 22. generalizing the
balance theory to the k-group theory [57] (58) describes the node relationship with all the groups as the global information and models the positive and negative edges as the local information. SGA [59] addresses graph sparsity and unbalanced triangle issues through structure- aware edge manipulation and curriculum learning. In addition, many node embedding algorithms [12T7]] are initially used for the classic downstream tasks in the traditional networks, e.g., node classification and link prediction. By contrast, only a few works [19 23] focus on the edge embedding. These methods commonly lack the mechanism of capturing the unique properties of signed networks. Whether for signed networks or traditional networks, the above network embedding algorithms mainly rely on random walks, matrix factorization and graph neural networks, which pose challenges in terms of efficiency.
Graph Hashing, Although the GNN framework has achieved great progress, it suffers from huge computational resource and memory storage due to dramatic parameter training. To this end, the researchers have resorted to the Locality Sensitive Hashing (LSH) technique, which can efficiently conduct the high-dimensional data similarity estimation by exploiting a family of random hash functions to map the similar data objects to the close and even the same data points represented as vectors, e-g., MinHash (60), SimHash (61) etc. Some graph hashing algorithms 437-42 62 50)
aim to represent each node in the network as a compact hashcode. The core idea of the methods to extract and sketch the subtrees rooted at each node the corresponding node representation. Although the methods can further derive the edge representation, they cannot preserve the complete characteristics of the edges. By contrast, others [43/47 51 represent the whole graph as low- dimensional feature vector for graph classification. Particularly, the works [47] (1] improve the performance of the above LSH-based graph classification by extracting the simplicial complex and then converting the original node- based graphs into multi dimei-ddmensional simplex- based graphs.
Unfortunately, the whole graph hashing methods are not applicable in our problem setting.
3 Preliminaries
3.1 Edge-based Signed Network Embedding
Given a signed network g = (V, U-)), where V a node set, E VVVV is a positive edge set and 8 C V x V is a negative edge set. Note that Ex - = 0 means that an edge is either positive or negative. Edge-based signed network embedding seeks to sketch each edge E 8 U as low-dimensional vector X E _R. which facilitates the link sign prediction task.
3

---

3.2 Simplicial Complex
Given a network (V.E), where V node set and & an edge set, we call it k-simplex Sk [vo, ,,,..., V2] if node subset {vo. ....... vx) V forms a clique in g. for example, O-simplex node, 1-simplex is an edge, 2-simplex is a triangle, etc. Also, given a simplex St = [vo.....vy v&] and a (k -i-simplex Sk-1 =
............ Ivo....,Vk''.. Vk+ val. St is co-boundary adjacency and Sk-1 is a boundary adjacency. Formally, the boundary operator ask oo-= St-1 oo [vo...., ..o......V.-1-... Vk++l..... VxJ. Furthermore, simplicial complex C' is a collection of different dimensional simplexes in the network. We let K be the largest dimension of any simplex in C, and Cg be the subset composed of all the k-simplexes. We encode the adjacency relationship between (k 1)-simllexes and k-simplexes as where the columns represent the corresponding coefficients of the -issimllexss the above-mentioned boundary operator of all the k-simplexes. Consequently, the Hodge Laplacian of K K-dimensional simplicial complex is defined as
Lg B
L B + B&.1 B (1,2..... --
(I)
Lx = Bx
where each row and each column of L2 denotes k-simplex, k {0, 10..,, K}. Similarly, L describes the adjacency relationship between any two k-simplexes. Note that an entry of Bx/L Lg is 0
the two corresponding simplexes are not adjacent; otherwise, is non-zero. The simplicial complex bridges geometric topology with algebraic topology, which further establishes connection between graph analysis and topology. In word, the simplicial complex assists in preserving higher-order interaction relationship in the network.
3.3 Locality Sensitive Hashing
An efficient framework for data sketching and similarity preserving backed by solid theoretical foundation is Locality-Sensitie Hashing (LSH) (36), which sketches the similar data objects as the
same hashcode with higher probability than the dissimilar ones by family of randomized hash functions.
Definition 1 (Locality Sensitive Hashing). A family H of randomized functions is called (d1, d2, Pt, P2) senssiiee if for two data objects p and q, and Vh E H:
If dist(p. q) di, then Pr(h(p) h())) pı:
* If dist(p.. q) d2, then Pr(h(p) h(g)) P2-
where d1 < d2 under a certain distance measure dist and 0 S p2 < P1 S 1.
4 Signed Network Sketching
In this section, we propose a novel signed network sketching model called EdgeSketch+ beyond node-centric modeling, which employs the simplicial complex to capture the higher-order interaction relationship in the signed network and then efficiently implements edge embedding in the LSH framework. The relevant definitions are provided in Appendix C
4.1 The EdgeSketch+ Algorithm
We outline the proposed EdgeSketch+ method in Algorithm The input consists of signed network g (V,&* U 87,, the number of dimensions for edge embedding D, the number of iterations R, and R sets of 3 D) random vectors (h (d.r) 2.DD) k=0.d=1.r=1 corresponding to 0-, 1- and 2-simplexes, respectively. The output returns each edge embedding at the Rth iteration the final edge embedding.
(h(d)))
First, Algorithm extracts all the simplexes (Line 1), and establishes the simplex-based adjacency matrices and the T-dimensional Hodge Laplacian (Lines 2-3). Subsequently. Algorithm [ proceeds in an iterative way: we represent all the extracted simplexes by the convolution operation on the simplex- based adjacency matrices and the I-dimensional Hodge Laplacian (Lines 5-7); further,

---

Algorithm The EdgeSketch+ Algorithm
Input: (V, (
1-----11.-11
Output: {Ke; 1/=1
1: Extract all 0-, 1- and 2-simplexes in
2: Build the simplex-based adjacency matrices B and B2
3: Build the I-dimensional Hodge Laplacian L1
4: for I....
5:
[NR]]
(x-r-))
NaNo 1) ] - Convn, ((MR) (r-1)) (r-1) 1)
RNo
[x]] 1fr-1)
(r-1) - ConvB (1x))
(1-1),
(1-11])
NN
IN2
7: [xe] [x!r-)
(r-1)
11 ConvI, ((x(1-1)
(1-11))
8:
for
=
1,
Ni do
9: Nej
AGG( (h (d.r) (r-1) 1
Ney Id-1 (1)
(cl.)) x "x! 1x!"" boundary adjacent on By 1.0
(hg
(ddir (r-1) |x,
x
(r-1) is co-boundary adjacent B2) (b(d X (ddr) (r-1) ((-1)) adjacent on L (2=))
10:
Nei
(g
11:
end for
aggregate (e.g., sum) each edge surrounding in the LSH framework such that the direct neighborhood information is effectively and efficiently perserved (Lines 8-11). 1). Accordingly, the resulting edge em- beddings from the last iteration. We illustrate the overall procedure of the proposed EdgeSketch+ approach in Figure 4 of Appendix B
The random vectors are produced off-line only once and shared globally. Therefore, there is no demand for high perfffreffrmmece hardware such as GPUs. As a consequence, the proposed EdgeSketch+ algorithm remarkably saves computation cost.
4.2
Theoretical Analysis
In this section, we theoretically analyze the proposed EdgeSketch+ algorithm.
4.2.1 EdgeSketch+ belongs to an LSH family
Proposition 1. Let e and be two edges, respectively, and be the size of their sketchings. Algorithm is (di, d2, 1 di
D -sensitive for some large D:
if dist(ei, e,) d1, then Pr(h(e;) h(e,)) 2 4
if dist(e;, e,) d2, then Pr(h(e;) = h(e,)) s 1 de
D
where 0 di d2 < 1.
Proof. The Hamming distance between two edge sketchings varies from to some large D in the case of D-dimensional sketches, i.e., dist e [0, DJ. Furthermore, we can convert the distance into the probability that they share the same hashcode, i.c.,
Pr(h(e;) = h(e,)) = dist(er. ej) E [].
D
4.2.2 EdgeSketch+ produces a Hash Kernel
Definition (Hash Kernel). Given any two edges, e, and e,. Algorithm generates the D- (R) dimensional edge sketching under R iterations, x (R) and xx) respectively. We define the hash kernel, KFdgeSketche, between and ej as
D = (R) en,
KEdgeSketch+(ee.ee) = k(xe, Xe,
(R)
(R) end
(3)
Theorem 1. The hash kernel matrix K E R NxN as defined in Eq. is positive definite.

---

Proof. We rewrite Eq.
3 as
1
Σ
KEdgeSketch+ (ei, ej)
[ (xxx, = [xx, 0 (xxja =
D
d=l
x (1)()), =),,.. ,), = 1), (x = 0), ... 1 = =)) (4)
VD
x (1(x),1= "...)...,000.. = 1), 1(x,1 = -). ,1x,,11 0))
VD
The value KEdgeSketch+<<;; ej) can be interpreted as the inner product two vectors, each having a dimensionality of 2D. As a result, can be expressed as K MMT, where e RN22
4.2.3 Concentration
We define the theoretical similarity between two edges, e and ej. as
1 D
EE16 on = xx
1(x
Sim(ei.e,) = -r(h(e,))= h(e,))
lim D-+t0
(5)
Then, we can show the highly-concentrated estimator Sim(e;,ej),
Theorem 2. Given two edges and ej. Algorithm Searthhm@@eeeeeee generates the corresponding D-dimensional
edge sketching xRR) and xei under iterations. Ve O, the probability of deviation between the kernel KrdgeSketchs<eiiee eÿ) and their real similarity Sim(ei.ej) is bounded by the following
inequality
Pr PrllK (ei, ez) ) Sim(e;, 2 s 2exp(-2De)).
Proof. Let ((R) be Bernouli random variable, which takes x with the probability of Sim(e;, ej). Furthermore, considering D i..d Bernoulli random variables, x|R), .x(R) ,.,x x(R)
we have X (() D E ((k) and B ] Sim(er,)) e)). Consequently, we can directly use the Hoeffding bound 63
on the mean of the variables,
Pr[ Pr[lKEndgeStenchheeeeeee Sim(e; ej)l 2 Pr([i BIX BIX" e]
S 2exp(-2
4.2.4 Time Complexity
Let v be the average degree of the network, R be the number of iterations, and D be the number of dimensions for edge embedding. We denote the number of O-simplexes, I-simplexes and 2-simplexes as No. N₁ and N2, respectively. In the real scenarios, the networks are commonly sparse, which means that O O(N,) (N2) [64 65) Consequently, takes O O and O to extract O-simplexes, 1 1-simplexes and 2-simplexes, respectively. Next, Algorithm| spends O (2N)), (3N)) and O(N)) in generating the sparse matrices, B,, B2 and L,, respectively. In the outer for loop, requires D) (Line 5), ON, (Line 6), O D) (Line 7) and (VN, (Lines 8-11). Consequently, the total time complexity ONN + R).
Additionally, we analyze the algorithm's representational power and space complexity in Appendix D.I and Appendix D.2 respectively.
4.3 Incorporation with Linear Learning Models
As in Eq. (3), the D-dimensional edge embedding derives nonlinear kernels. However, the explicit kernel computation is definitely accompanied with a precomputed Gram matrix with the size being the square of the number training instances. Fortunately, the inner product in Eq. (4) indicates that vectorized representation can be mapped into an inner product space by negation and concatenation, which remarkably speedups the training and testing processes without compromise classification accuracy by the linear learning models such as logistic regression. Consequently, this approach

---

effectively addresses the issue of SVM training for large-scale problems, particularly when the training dataset exceeds available memory capacity. Taking the edge embedding vector [1, 0, 1, 0, as an example, Eq. transforms it into a a 10-dimensional feature vector, i.c., V 1,000.0.1 where the underlined entries negate the corresponding bits in the original vector. Consequently. the concatenated vectors can be utilized by linear solvers, eliminating the need to store large-scale kernel matrices.
5 Experimental Results
In this section, conduct the extensive experiments to evaluate the performance of the proposed EdgeSketch+ method. All dataset information provided in of Appendix where "BTC-a" stands for Bitcoin-alppha "BTC-O" for Bitcoin-OTC, "Slash." " for Slashdot, and "Epin." for Epinions. For details on baselines and experimental settings, please refer to Appendix
5.1 Link Sign Prediction Results
Table 1: Link sign prediction performance results.
GSGNN
Datasets
RSGNN SDGNN
SGCL.
SiGAT
EdgeRWSF
edge2vec
EdgeSSetch+
+SGA
Rinary-FI
03475
0.9714
0.9272
03740
0.9706
0.963
0.9639
0.9704
0.9686
0.97715
0.9780
Accuracy
0.9051
0.9458
0.8729
0.9508
0.9438
0.9266
0.9340
0.9435
0.9263
0.9433
0,9581
AUC
0.8467
0.8799
0,7863
0.9101
0.8874
0.8911
0.5314
0.8579
0.6246
0.8485
0.8829
Macro Fl
0.5874
0.7294
0.71119
0.7501
0.6758
0.7373
0.4836
0.6770
0.4892
0.5874
0.7687
Runtime
332.81
779.81
315.71
2204.68
267.83
176.69
558.67
94.67
4081.36
121.23
4,03
Binary- Fl
0.933
0.9623
0.9138
039666
0.9600
0.9655
0.9467
0.9627
0.9617
0.9603
0.968T
Accuracy
0.9172
0.9315
0,8585
0.9384
0.9265
0.9209
0.8987
0.9327
0.9263
0.9315
0.9413
BTC-
AUC
0.8127
0.9004
0.8032
0.9152
0.8953
0.8987
0.5314
0.8579
0.6132
0.8127
0.8695
Macro-F1
0.6096
0.7850
0,7652
0,7782
0.7473
0.7533
0.4836
0.6770
0,4892
0.6096
0,8137
Runtime (5)
441.78
1394.25
430.51
2930.11
716.56
173.65
1744.71
125.64
4560.63
460.23
7,81
Binary-FI
0,8737
0.9072
0.8672
0.8741
0,9209
Accuracy
0,8162
0.8519
0.7982
0.7795
0.8729
Slash.
AUC
0,7942
0.8864
0.8222
0.7129
0,8914
Macro-FI
0,7665
0.7697
0.7232
0,4710
0.7995
Runtime
OCT
O0T
19.04
OOT
182.26
1326 12
OOM
652.34
O0T
0OM
140.44
Binary-Fi
0,9255
0.9579
0.9523
0.9206
0.9659
Accuracy
0,8784
0.9269
0.9188
0,8530
0.9405
Epin.
AUC
0.8240
0.9248
0.8914
0.6340
0.9217
Macro-FI
0,7955
0.8354
0.8222
0,4601
0.8658
Runtime (s)
00M
O0T 4180.38
OOT
30651.82
1220.41
OOM
1069.47
O0T
00M
273.24
DOM/OTT mean that the methods run out of memory/time.
Table I shows the experimental results. Clearly, our proposed EdgeSketch+ algorithm competes very well with all the competitors tailored for signed network embedding (i.e., RSGNN, SDGNN, SNEA, SGCL, SiGAT and GSGNN+SGA)
performs best in most cases, with an average AUC lag of only 0.0253, compared to the top-perforning baselines, which reflects that the proposed EdgeSketch++ algorithm has achieved strong precision and recall for the minority class but struggles to maintain balanced performance across all the thresholds due to the influence of the majority class; also, runs fastest all the datasets. achieving up 546.07x speedug Particularly, would like note that some GNN-based algorithms suffer from huge time or memory consumption on the two largest datascts, i.c., Slash. and Epin This reveals that the idea of integrating the simplicial complex into the LSH framework is very promising in efficiently recognizing the confusing patterns signed networks with no data distribution fitting and further benefiting the quality of edge-based signed network embedding our proposed EdgeSketch+ algorithm judges the edges more accurately with the aid of simplicial complexes. In the Appendix G. we analyze the experimental results about the edge embedding algorithms (i.e., EdgeRWSE, TER and edge2vec) and the LSH-based method (i.e., MPSketch) in more details.
TThe ratios exclude out-of-time and out-of out-of-memory scenarios. In the original paper M RSGNN ran only on the sampled Slash. and Epin.
7

---

5.2 Ablation Study
The proposed EdgeSketch+ algorithm preserves higher-order interaction relationship from the sim- plicial complex in the signed network by the LSH technique. Therefore, conduct the ablation analysis w.r.t. the simplicies (i.e., O-simplex, 1-simplex and 2-simplex) involved in the proposed EdgeSketch+ algorithm. To this end, have the following variants,
EL only utilizes the Hodge Laplacian L1 by removing the boundary adjacency matrix involving O-simplexes, Bi, and the co-boundary adjacency matrix involving 2- simplexes, B,, simultaneously;
EdgeSketch+-11 replaces L of EdgeSketch+-L. with I'I, which operates the incidence matrix in Eq. (I) Any entry of 1 is if the node is incident upon the edge; it is O, otherwise.
We adopt the same parameters for the two vari- ants for fair comparison. Table reports the experimental results in terms of /) 300 and R= EdgeSketch+-1" with no simplicies in- volved, performs worst, which indicates that the simplicial complex, as the higher-order abstrac- tion, definitely facilitates signed network sketch- ing by preserving the higher-order interaction relationship. Furthermore, we observe the wider gap between EdgeSketch+ and EdgeSketch+- L1. which implies that the O-simplexes and 2- simplexes involved in the edge surrounding are indispensable and the higher-order direct neigh- borhood information remarkably benefits the final edge embedding. Overall, the performance shows an obvious increasing trend as more sim- plicies captured, i.e., from just incidence information to the edge surrounding.
Table 2: Ablation study of EdgeSketch+ w.r.t. the simplicial complex.
EdgeSkeiche EdgeSketch+
EdgeSkesch= (orignal)
Datasets
Metries
-1'
-L,
Binary-Fi
0.9690
0.9696
0.9780
Accuracy
0.9404
0,9415
0.9581
BTC-a
Macro-F1
0.6120
0.682
0.7687
Binary-Fi
0.9556
0.9574
0.9681
Accuracy
0.9173
0.9205
0.9413
AUC
0.7594
0,7667
0.8695
Macro-FI
0.6789
0.6841
0.8137
Binary-Pi
Accuracy
0.8343
0,8351
0.8729
Slash.
AUC
0.8120
0.8133
0.8914
Macro-Fi
0.7194
0.7216
0.7995
Binary-FI
0.9456
0,9459
0.9659
Epin.
Accuracy
0.9038
0,9044
0,9405
Macro-F1
0.7664
0.7676
0.8658
5.3 Scalability
As shown in Section 4.2.4 the time and
space complexities of the proposed EdgeS- ketch+ algorithm are both polynomial w.r.t.
700000
7000
600000
6000
the number of edges, and thus we verify its scalability w.r.t. the the network property on a set of random, million-scale networks (i.e., [V] 10%) generated by the Erdos- Renyi model [66]. Figure 2 reports the results in terms of memory consumption and runtime in case of R 2 and D = 300. The embedding time of EdgeSketch+ dis- plays the slow quadratic growth, owing to V, D, D2, R < N1, and memory con- sumption is empirically linear thanks to DR & Nj. Particularly, our proposed probabilistic model produces representation for tens of millions of edges in less than 2 hours and 600GB the million-scale networks. The empirical results match theoretical complexities. Therefore, our proposed EdgeSketch+ model shows good potential in efficiently sketching large-scale signed networks.
500000
5000
Memory
400000
Runtime
300000
3000
200060
2000
100000
1000
2
5
2
Edges
Edges
Figure Scalability of EdgeSketch+ w.r.t. the number of edges.
5.4 Slyper-parameter Sensitivity
The proposed EdgeSketch+ algorithm has two parameters, i.e., the embedding dimension D and the number of iterations R. We explore how these two parameters affect link sign prediction performance

---

BTC-a
BTC-a
Slash.
Slash.
0.03
g05
530
160 199
6as
S 35 Oimenddee neiinn
0.55
Gemendiion netio
Sig
253
126
Iberation
Iberabong
Iberatoon
Rerabons
Figure 3: syper-parameter sensitivity in EdgeSketch++ in link sign prediction w.r.t. the embedding dimension D) and the number of iterations R.
in effectiveness and runtime. We exhibit the results in terms of binary-fl and end-to-end runtime on BTC-a and Slash. in Figure 3
It is evident that the accuracy performance is closely influenced by the embedding dimension D and the number of iterations R. Generally speaking, accuracy exhibits fluctuations as D and R increase observe clear convex surface on Slash. Particularly, EdgeSketch+ performs
on BTC-a: whereas best the case of the largest D = 300 and the smallest R 1. This result highlights two key insights: larger 1) captures more meaningful information and the simplicial complex, abstraction, retains sufficient information with a small R. Conversely, increasing R excessively would cause feature diffusion across simplexes, leading to the loss of local features. The end-to-end runtime demonstrates an empirical linear relationship with R, even though the classification time is considered. This implies that the embedding process theoretically linear R dominates the whole link sign prediction task, and further EdgeSketch+ generates high-quality embedding vectors that are easy to classify.
higher-order
5.5 Effectiveness of Edge Structure Distance
We define the edge structure distance based on the Hamming distance to describe the similarity between the edges of the signed networks in Appendix
Table Hamming distance Cosine distance.
EdgeSketch+
EdgeSketch+ (orignal)
Datasets
Metries
-Cosine
C In order to verify its effectiveness, compare with the common Cosine distance. Specifically, we precompute the Cosine kernel based cosine distance and then feed it into SVM.
Binary-F1
0.9742
0.9780
Accuracy
0.9505
0.9581
BTC-a
AUC
0.7329
0.8829
Macro-F1
0,6509
0.7687
Binary-F1
0.9616
0.9681
Accuracy
0.9285
0.9413
Table 3 shows the comparison results on BTC-a and BTC-O. Clearly, our proposed edge similar- ity based on the Hamming distance is superior the Cosine similarity the L.S family.
BTC-O
AUC
0.7158
0.8695
Macro-F1
0,5481
0.8137
5.6 Necessity of Edge Embedding
In order to demonstrate that the edge embedding as feature design definitely fosters the good per- formance, we directly feed the initialized edge vectors into the logistic regression classifier.
Table 4: Importance of the Edge Embedding.
Datasets
Metrics
Naive
EdgeSketch+
Binary-F1
0.9698
0.9780
Accuracy
0,9415
0.9581
Table 4 shows the comparison results on BTC- and BTC-O. In the scenario where the same classifier model is adopted, our proposed edge embedding model performs much better than the naive method based on the only initialized edge
BTC-a
AUC
0,5000
0.8829
Macro-F1
0.4830
0.7687
Binary-F1 0.9436
0.9681
Accuracy
0.8933
0.9413
BTC-O
vectors, which shows that the edge embedding effectively captures the higher-order structure information. By contrast, naive method cap- tures only the information of the edges themselves. Particularly, the AUC values of 0.5000 from the
AUC
0.5000
0.8695
Macro-F1
0.4786
0.8137

---

naive method imply that good feature design is very necessary; otherwise, the classifier performs no better than random guessing.
Conclusion
In this paper, we propose simple and very speedy signed network sketching model dubbed EdgeS- ketch+ beyond node-centric modeling, which can capture the higher-order information derived from the simplicial complex with more representational capability than the traditional node-to-node inter- active relationship. The approach adopts the L.H technique to avoid substantial parameter training, while preserving much structural information possible. Furthermore, we provide the theoretical guarantees for the accuracy and the complexity the edge representation. We conduct the extensive experiments of EdgeSketch+ and collection of state-of-the-an methods. We evaluate its performance in terms of accuracy and runtime on number of signed network datasets. The experimental results show that our proposed EdgeSketch+ method achieves the competitive accuracy performance with dramatically reduced runtime, which makes more practical in the era of big data.
Acknowledgments
This work supported by Open Project of Xiangjiang Laboratory (No.25XJ03022) National Natural Science Foundation of China (No. 62302528, 62522201, 62172449, 62202025, 72374070), Hunan Provincial Natural Science Foundation of China (2022J13021, (2020113021,02251200711 Beijing Natural Science Foundation (No. 1.241050), Young Elite Scientist Sponsorship Program by CAST (No. YESS20230566), CCF-Huawei Populus Grove Fund CCF-Huawei (No. CCF-HuuaeiPM22224005) High Performance Computing Center of Central South University, and Fundamental Research Fund Project of Beihang University.
References
[1] Z. Zhang. J. Liu, X. Zheng, Y. Wang. P. Han, Y. Wang. K. Zhao, and Z. Zhang, "RSGNN: A Model-agnostic Approach for Enhancing the Robustness of Signed Graph Neural Networks," in www, 2023, pp. 60-70.
[2] H. Liu, Z. Zhang, P. Cui, Y. Zhang, Q. Cui, J. Liu, and W. Zhu, "Signed Graph Neural Network with Latent Groups," in KDD, 2021, pp. 1066-1075.
[3] Huang, H. Shen, L. Hou, and X. Cheng, "SDGNN: Learning Node Representation for Signed 2021, pp. 196-203.
Directed Networks," in AAAI,
[4] Y. Li, Y. Tian, J. Zhang, and Y. Chang, "Learning Signed Network Embedding via Graph Attention," AAAI, no. 04, 2020, pp. 4772-4779.
[5] T. Derr, Y. Ma, and Tang, "Signed Graph Convolutional Networks," in JCDM, 2018, pp. 929-92 9344.
[6] L. Shu, E. Du, Y. Chang, C. Chen, Z. Zheng, X. Xing, and S. Shen, "SGCL: Contrastive Representation Learning for Signed Graphs," in CIKM, 2021, pp. 1671-1680.
[7] J. Huang, H. Shen, L. Hou, and X. Cheng, "Signed Graph Attention Networks," in ICANN, 2019, pp. 566-577.
[8] H. Sun, P. Tian, Y. Xiong, Y. Zhang, Y. Xiang, X. Jia, and H. Wang, "DynamiSE: Dynamic Signed Network Embedding for Link Prediction," Machine Learning, pp. 1-17, 2024.
[9] L. Li, J. Liu, X. Ji, M. Wang, and Z. Zhang, "Self-Explainable Graph Transformer Link Sign Prediction," in AAAI, 2025, pp. 12 099-
[10] D. Cartwright and F. Harary, "Structural Balance: A Generalization of Heider's Theory." Psychological Review, vol. 63, no. 5, p. 277, 1956.
[11] Heider, "Attitudes and Cognitive Organization," The Journal of Psychology, vol. 21, no. 1, pp. 107-112, 1946.
10

---

[12] B. Perozzi. R. Al-Rfou, and S. Skiena, "DeepWalk: Online Learning of Social Representations." in KDD, 2014, pp. 701-710.
[13] A. Grover and Leskovec, "node2vec: Scalable Feature Learning for Networks," in KDD, 2016, pp. 855-864.
[14] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, "LINE: Large-scale Information Network Embedding," in WWW, 2015, pp. 1067-1077.
[15] C. Huang, M. Li, F. Cao, H. Fujita, Z. Li, and X. Wu, "Are Graph Convolutional Networks with Random Weights Feasible?" IEEE Transactions Pattern Analysis and Machine Intelligence, vol. 45, no. 3, pp. 2751-2768, 2022.
[16] Y. Yan, B. Jing, L. Liu, R. Wang. J. Li, T. Abdelzaher, and H. Tong, "Reconciling Competing Sampling Strategies of Network Embedding." in NeurIPS, 2023, pp. 6844-6861.
[17] Y. Yan, Hu, Q. Zhou, L. Liu, Z. Zeng, Chen, M. Pan, Chen, M. Das, and H. Tong. "PACER: Network Embedding from Positional to Structural," in WWW, 2024, pp. 2485-2496.
[18] G. Yang M. Li, H. Feng, and X. Zhuang, "Deeper Insights into Ddeep Graph Convolutional Networks: Stability and Generalization," IEEE Transactions on Pattern Analysis and Machine Intelligence, 2025.
[19] C. Wang, C. Wang. Z. Wang, X. Ye, and P. S. Yu, "Edge2vec: Edge-based Social Network Embedding," ACM Transactions on Knowledge Discovery from Data, vol. 14, no. 4, pp. 1-24, 2020.
[20] H. Wang, Yang, K. Huang, and X. Xiao, "Efficient and Effectiive Edge-wise Graph Represen- tation Learning,"" in KDD, 2023, pp. 2326-2336.
[21] P. Bielak, T. Kajdanowicz, and N. V. Chawla, "AttrE2vec: Unsupervised Attributed Edge Representation Learning." Information Sciences, vol. 592, pp. 92-96, 2022.
[22] J. Kim, T, Kim, S. Kim, and C. D. Yoo, "Edge-labeling Graph Neural Network for few-shot Learning," in CVPR, 2019, pp. 11-20.
[23] L. Gong and Q Cheng, "Exploiting Edge Features for Graph Neural Networks," in CVPR, 2019, pp. 9219211199 9211-9219.
[24] A. C. Wilkerson, T.J. Moore, A. Swami, and H. Krim, "Simplifying The Homology of Networks via Strong Collapses," in ICASSP, 2013, pp. pp. 5258-5262.
[25] S. Gurugubelli and S. P. Chepuri, "SaNN: Simple Yet Powerful Simplicial-aware Neural Networks," in ICLR, 2024.
[26] S. H. Lee, F. Ji, and W. P. Tay, "SGAT: Simplicial Graph Attention Network," in IJCAI, 2022, pp. 3192-32000
[27] Frantzen and M. T. Schaub, "Learning from Simplicial Data ased on Random Walks and 1d Convolutions." in ICLR, 2024.
[28] C. Zhou, X. Wang, and M. Zhang, "Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes," in NeurlPS, 2023, pp. 16 172-16 206.
[29] C. Liu, D. Ruhe, F. Bijkelboom. and P. Forré, "Clifford Group Equivariant Simplicial Message Passing Networks," in ICLR, 2024.
[30] H. Wu, A. Yip, J. Long, J. Zhang, and M. K. Ng. "Simplicial Complex Neural Networks," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 46, no. 1, pp. 561-575, 2024.
[31] M. Hajij. G. Zamzmi, T. Papamarkou, V. Maroulas, and X. Cai, "Simplicial Complex Represen- tation Learning." in ICLR, 2021.
[32] K. Maggs, C. Hacker, and B. Rieck, "Simplicial Representation Learning with Neural k-Forms," in ICLR, 2024.
11

---

[33] M. Yang, E. Isufi, and G. Leus, "Simplicial Convolutional Neural Networks," in ICASSP, 2022, pp. 8847-8851.
[34] M. Roddenberry, N. Glaze, and S. Segarra, "Principled Simplicial Neural Networks for Trajectory Prediction," in ICML, 2021, pp. 9020-9029.
[35] C. Bodnar, F. Frasca, Y. Wang, N. Otter, G. F. Montufar, P. Lio, and M. Bronstein, "Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks," in ICML, 2021, pp. 1026-1037.
[36] P. Indyk and R. Motwani, "Approximate Nearest Neighbors: towards Removing the Curse of Dimensionality," in STOC, 1998, pp. 604-613.
[37] W. Wu, B. Li, L. Chen, and C. Zhang, "Efficient Attributed Network Embedding via Recursive Randomized Hashing," in IJCAI-18, 2018, pp. 2861-2867.
[38] W. Wu, B. Li, C. Luo, and W. Nejdl, SlashinggAAceleratte Graph Neural Networks for Link Prediction," in WWW, 2021, pp. 2910-2920.
[39] W. Wu, B. Li, C. Luo, W. Nejdl, and X. Tan, "MPSketch: Message Passing Networks via Randomized Hashing for Efficient Attributed Network Embedding," IEEE Transactions Cybernetics, vol. 54, no. 5, pp. 2941-2954, 2024.
[40] D. Bera, R. Pratap, B. D. Verma, B. Sen, and T. Chakraborty. "QUINT: Node Embedding using Network Hashing," IEEE Transactions on Knowledge and Data Engineering. vol. 35, no. 3, pp. 2987-3000, 2023.
[41] D. Yang, B. Qu, J. Yang, L. Wang, and P. Cudre-Mauroux, "Streaming Graph Embeddings via Incremental Neighborhood Sketching." IEEE Transactions on Knowledge and Data Engineering. vol. 35, no. 5, pp. 5296-5310, 2023.
[42] A. Celikkanat, F. D. Malliaros, and A. N. Papadopoulos, "NODESIG: Binary Node Embeddings via Random Walk Diffusion," " in ASONAM, 2022, pp. 68-75.
[43] B. Li, X. Zhu, L. Chi, and C. Zhang, "Nested Subtree Hash Kernels for Large-scale Graph Classification over Streams," in ICDM, 2012, pp. 399-408.
[44] W. Wu, B. Li, L. Chen, X. Zhu, and C. Zhang, "K-Ary Tree Hashing for Fast Graph Classifica- tion," IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 5, pp. 936-949, 2018.
[45] C. Morris, N. M. Kriege, K. Kersting, and P. Mutzel, "Faster Kernels for Graphs with Continuous Attributes via Hashing," in ICDM, 2016, pp. 1095-1100.
[46] M. Neumann, R. Garnett, C. Bauckhage, and K. Kersting, "Propagation Kernels: Efficient Graph Kernels from Propagated Information," Machine Learning, vol. 102, pp. 209-245, 2016.
[47] X. Tan, W. Wu, and C. Luo, "SCHash: Speedy Simplicial Complex Neural Networks via Randomized Hashing," in SIGIR, 2023, pp. 1609-1618.
[48] C. Aggarwal, G. He, and P. Zhao, "Edge Classification in Networks," in ICDE, 2016, pp. 1038-1049.
[49] W. Wu, Li, C. Luo, and Li, "Time- and Space-Efficiently Sketching Billion-Scale Attributed Networks," IEEE Transactions on Knowledge and Data Engineering, vol. 37, no. 2, pp. 966-978, 2025.
[50] W. Wu, S. Li, L. Chen, L. Fangfang, and C. Luo, "Skeching Very Large-scale Dynamic Attributed Networks More Practically," in wWW, 2025, pp. 5274-
[51] F. Li, H. Zhang, W. Li, and W. Wu, "Heterogeneous Graph Embedding Made More Practical," in SIGIR, 2025, pp. 688 697.
[52] Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph Attention Networks," in ICLR, 2018.
12

---

[53] T. N. Kipf and M. Welling, "Semi- Seemi-Supervieed Classification with Graph Convolutional Net- works," in ICLR, 2017.
[54] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How Powerful are Graph Neural Networks?" in ICLR, 2019.
[55] H. Liu, "LightSGCN: Powering Signed Graph Convolution Network for Link Sign Prediction with Simplified Architecture Design," in SIGIR, 2022, pp. 2680-2685.
[56] Y. You, T. Chen, Y. Sui, T. Chen, Z. Wang, and Y. Shen, "Graph Contrastive Learning with Augmentations." NeurIPS, pp. 5812-5823, 2020.
[57] M. Cucuringu. P. Davies, A. Glielmo, and H. Tyagi, "SPONGE: A Generalized Eigenproblem for Clustering Signed Networks," in AISTATS, 2019, pp. 1088-1098.
[58] R.-C. Tzeng, B. Ordozgoiti, and A. Gionis, "Discovering Conflicting Groups in Signed Net- works," NeurIPS, pp. 10974-10985, 2020.
[59] Z. Zhang, L. Li, S. Wan, W. Wang, Z. Wang. Z. Lu, D. Hao, and W. Li, "DropEdge not Foolproof: Effective Augmentation Method for Signed Graph Neural Networks," in NeurIPS, 2024, pp. 117 041-117 069.
[60] A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher, "Min-wise Independent Permutations," in STOC, 1998, pp. 327-336.
[61] M. S. Charikar, "Similarity Estimation Techniques from Rounding Algorithms," STOC, 2002. pp. 380-388.
[62] D. Yang, P. Rosso, B. Li, and P. Cudre-Mauroux, "NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching," KDD, 2019, pp. 1162-1172.
[63] W. Hoeffding, "Probability Inequalities for Sums of Bounded Random Variables," in The Collected Works of Wassily Hoeffding, 1994, pp. 409-426.
[64] J.-P. Eckmann and E. Moses, "Curvature of Co-links Uncovers Hidden Thematic Layers in the World Wide Web," Proceedings of the National Scademy of Deiences, vol. 99, no. 9, pp. 5825-5829, 2002.
[65] 7. Zhang, Cui, H. Li, X. Wang, and W. Zhu, "Billion-scale Network Embedding with Iterative Random Projection," in ICDM, 2018, pp. 787-796.
[66] P. ERDAS and A. R&wi, "On Random Graphs 1," Publicationes Mathematicae, vol. 6, no. 18, pp. 290-297, 1959.
[67] B. Weisfeiler and A. A. Lehman, "A Reduction a Graph to a Canonical Form and an Algebra Arising during this Reduction," Nauchno--echnicheekaay Informatsia, vol. 2, no. 9, pp. 12-16. 1968.
[68] N. Halko, P.-G Martinsson, and J. A. Tropp, "Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions,, SIAM Review, vol. 53, no. 2, pp. 217-288, 2011.
[69] T. Lei, W. Jin, R. Barzilay, and T. Jaakkola, "Deriving Neural Architectures from Sequence and Graph Kernels," ICML, 2017, pp. 2024-2033.
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:
The contents of the paper match the claims made in the abstract and introduc- tion.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations in separate section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not 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 to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
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:
We have provided the theories and the corresponding proofs.
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 or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We explicitly reveal all the hyperparameters and open source models necessary to reproduce our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, 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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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]
Justification:
We have provided the publicly available datasets and our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//wpps.cc/publii.... htt.//ublllluuuueee des/ Cae///eoeeSbiieeee
ssi onPolicy) d for more details.
The authors should provide instructions on 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We have provided the details of all the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Since our comparative experiments strictly follow the baseline settings, includ- ing train/test dataset splits and random seeds, the experimental results exhibit no variance.
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.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of 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 reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have described the system which the experiments conducted in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in 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 the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We review and ensure that the present work respects the NeurlPS Code of Ethics at each individual part.
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., if there is special consid- eration due to laws or regulations 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: The research does not have concerns about societal impacts because it is designed for general- purpose graph embedding.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or 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 to 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 is being used as 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 ML).
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: We use publicly available datasets and models, widely used in the research community.
Guidelines:
The answer NA means that the paper poses no 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. Licenses 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: We have obeyed all license and terms involved in the datasets and the compared methods.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI
The name of the license (e.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 package should be provided. For popular datasets, paperssitthooee thooode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 in the main paper.
According the NeurIPS Code of Bthies, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve IRB approvals.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We just adopt LLM to proofread the paper (e.g., grammar, spelling, word choice).
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standarr components.
Please refer to our LLM policy for what should or should be described.
20

---

Appendix
A
Notation Table
The notations are summarized in T
Table Notations
Notation
Description
g
Signed network where edges have positive negative signs
V
Set of nodes the signed network
&
Set of edges in the signed network
A node in the signed network
An edge in the signed network, typically I-simplex
Se
A k-simplex Embedding of simplex S
x
C B; L
A simplicial complex
Boundary adjacency matrix for i-simplices
i-dimensional Hodge Laplacian A family of randomized functions
H
Random vector
Hash kernel
B
The EdgeSketch+ Algorithm
ailepiie sletsiigg
extract
build
Conv
AGG
simpleses
matrices
OR
Duamplor sirrchepp
sgn(-)
0/1/2-simplexes
Signed Network
Signed Network Sketching
Figure 4: The overall procedure of the proposed EdgeSketch+ algorithm.
C
Definitions
Definition 3 (Edge Surrounding). The edge surrounding centers around the edge itself (i.e., 1- simplex), with its direct neighborhood from the viewpoint of the simplicial complex, including the adjacent edges (i.e., 1-simplexes), nodes (i.e., 0-simplexes) and triangles (i.e., 2-simplexes). We can represent the edge surrounding via the convolution operation on the simplex- baseee adjacency matrices B,, B2 and the 1-dimensional Hodge Laplacian L1, which effectively preserves the direct neighborhood information.
This definition extends the traditional neighborhood relationship in graph mining, which is limited to the same-level, node-centric adjacency relationship.
Definition (Edge Sketching). The edge e's sketching under iterations is a --dimensional binary
vector, (R) [x e.1 e.2 (R) which is defined in terms of the edge surrounding projected
(R)
(R)
into R sets of x D random vectors in an iterative manner. The vector element x = if the dth projection is non-negative, and 0 otherwise.
,(R)
21

---

The projection operation is actually a linear combination of three kinds of simplexes from the edge surrounding on three random vectors, which is mathematically equivalent the edge surrounding holistically projected into target random vector.
Definition 5 (Edge Structure Distance). Given any two edges, e; and éj. A the D-dimensional edge sketching under R iterations, Xe; and x respectively. We define the edge structure distance as the Hamming distance between their sketchings, i.c..
D dist(er, e₁) dist(xa) (R) xxe)) = Σ
(x (R)
ond # (R) xe,a))
(8)
d=l
where x()) (0. 1), and (state) 1, if state is true, and (staate) otherwise.
The distance represents the number of the target random vectors that lie in the same direction with exactly one of two edge surroundings.
D Theoretical Analysis
D.1 Representational Power
The work [54] has demonstrated that the WL isomorphism test [67] has the maximal representa- tional power to discriminate the substructures in the graph because the test ensures that different substructures is embedded into distinct locations in the feature space.
Motivated by the LSH framework, we can quantize the representational power of our proposed EdgeSketch+ algorithm from a probabilistic perspective. Assuming that A(r) denotes the r-th sketching process of the proposed probabilistic model, have the probabilistic expression as follows
(r) (r-1)) n: (r( (Xe,
(r) (XE)
(xx--111 (r-1)))
lim E D
1() D ex =x
(r)
d=l
where 1,2..... R. Formally, Eq. illustrates that the proposed EdgeSketch+ model could represent two substructures in the graph as the same feature vector with the probability of their theoretical similarity.
D.2 Space complexity
EdgeSketch++ requires storing the simplex-based adjacency matrices (i.e., O(2N1) for B, and O(3N2) for B2) and the Hodge Laplacian (i.e., O(FN)) for L1) well as the embedding for 0-simplexes (i.e., O)) 1-simplexes (i.e., O(N,)) and 2-simplexes (i.e., O(2)))): also, the random vectors need (D²R). Therefore, the space complexity is practically I R2
E Datasets
We implement the link sign prediction task on the following signed networks from the SNAP group 5
Bitcoin-alphe is who-truse tho-trust-whom Bitcoin-Alpha trading network, where the users give trust or distrust tags others for the sake of security.
Bitcoin-OTC is who-trust-we trumt-whom Bitcoin-On CTC trading network, where the give trust or distrust tags to others for the sake of security.
Slashdot news website that covers technology, science and culture. The users are allowed to tag each other as friends or foes.
Epinions a who-trust-whon online social network from the consumer review site. The users decide whether to trust each other.
Particularly, for Bitcoin-alpha and Bitcoin-OTC. users rate others negatively (i.e.. {-10, ......,..2...... -1)) or positively (i.e., (10.9.... 2, 1}); we consider the negative scores
/htpp://ssntt aaamapp.tamforddeeetatttaaaaaaa
22

---

Table 6: Summary of the signed network datasets.
Datasets
[V]
|8*1
|E-|
]triangles]
[v]
Bitcoin-alpha
3,783
22,650
1,536
22,153
12.79
Bitcoin-UTC
5,881
32,029
3,563
33,493
12.10
Slashdot
82,144
425,072
124,130
579,565
13.37
Epinions
131,228
717,667
123,705
4,910,076
12.76
as the negative edges and the positive scores as the positive edges. as shown in [3.. We initialize the node features with the positive in- mn-degree, the negative in-degree, the positive out-degree and the negative out-degree; then, we initialize the features of high-dimensional simplexes (i.e., edges and triangles) by taking the sum of the node features. The above datasets are summarized in Table
F Baselines and Experiment Setting
We compare the proposed EdgeSketch+ method with the following state-of-the-ard approaches in the link sign prediction task
RSGNN 1 aims to denoise the signed network in the node representation learning process
based on the balance theory.
SDGNN 3 learns node representation by aggregating messages from different signed, social relations in the signed network based the balance theory.
SNEA 4 estimates the importance coefficients of node pairs via the self-attention mecha-
nism when representing nodes in the signed network based on the balance theory.
SGCL learns node representation by applying the graph contrastive learning to signed networks based on the balance theory.
SiGAT 7 learns node representation by applying the graph attention network to signed networks based on the balance theory.
GSGNN+5GA 2 59
combines GS-GNN's [2] latent group modeling with SGA's (59 augmentation to address graph sparsity and unbalanced triangles.
EdgeRWSE [8 learns edge representation based on edge-level (i.e., 1-simplex) random walks with edge-level node position information supplemented.
TER 20 exploits the randomized singular value decomposition matrices to obtain edge representation.
68 of edge transition
edge2vec 19 utilizes deep autoencoders to capture local and global structure information of the embedded edges.
MPSketch [39 generates the node embeddings by using the LSH technique to pass messages in the MPNN framework [69]
All the compared methods have their codes provided by their respective authors, and we adopt the recommended hyperparameters in their papers for the learning methods. Also, we conduct the experiments with different values of R {1, 3, 4, 5) for MPSketch and EdgeSketch+. Finally, we set R 1 on Bitcoin-alpha and R 4 on Bitcoin-OTC for MPSketch, which runs out of memory on Slashdot and Epinions; we set R on Bitcoin-alpha and R = 1 on Bitcoin- OTC, R Slashdot and R = 1 on Epinions for EdgeSketch+. We set the embedding dimension D as 300 and the cutoff time of 24 hours. All the experiments are conducted on Linux with 2.90GHz 128 Intel Xeon Platinum 8375C CPU, 1.5T RAM and NVIDIA A10 GPU (24GB RAM). When the experiments encounter out-of-memory errors on the GPU, we would switch the computational device to the CPU. Following the previous works 2. achieve the signed network embedding and then conduct the link sign prediction task by the logistic regression classifier for the methods which are not trained in end-to-end manner. Particularly, for proposed EdgeSketch+ algorithm, we expand the embedding vectors and then feed them into the logistic regression classifier, as shown in Section
on
We do report the results from 48 55 30 since the codes publicly available.
23

---

4.3 for MPSketch, we use the Hamming distance and SVM classifier recommended in the original paper Otherwise, we employ the end-to-end training. We report the mean of binary-fl, accuracy, auc, macro-fl and end-to-end runtime in the 5-fold cross validation in Table I We provide the code the attachment.
G Analysis of Experimental Results
The proposed EdgeSketch+ model outperforms all the edge embedding algorithms (i.e., EdgeRWSE, TER and edge2vec). In spite of the simplicial complex involved, EdgeSketch+ unsurprisingly superior to EdgeRWSE, because EdgeRWSE focuses random walks simplicial complexes, with the edge patterns among the signed triangles neglected, that is to say, the neighbors that share O- simplexes is only considered; by contrast, EdgeSketch+ preserves such important information related to 2-simplexes to distinguish some difficult patterns under the balance theory. Besides, EdgeRWSE exhausts memory on Slashdot and Epinions, mainly due the memory consumption required for walking between a large number of simplexes. TER, as an efficient and effective edge embedding method recently claimed by its authors, definitely performs more efficiently than the learning-baat based competitors by randomized singular value decomposition (68). but EdgeSketch+ goes towards more efficient and effective by leveraging the advantages of the LSH technique and the simplicial complex. Also, EdgeSketch+ clearly outperforms edge2vec in terms of effectiveness and efficiency, because edge2vec essentially preserves local and global proximities from the node-level perspective by deep autoencoders. This again illustrates that the simplicial complex is able to identify more patterns.
Also, compare EdgeSketch+ against the most recent LSH-based node embedding algorithm, MPSketch, which derives edge embedding by concatenating two corresponding node embeddings. Evidently, MPSketch performs worst, and even runs out of memory on Slashdot and Epinions, because it cannot effectively capture the substructure features in the signed networks and more importantly, embeds into the nonlinear Hamming space such that the precomputed kernel matrix is too big to fit in memory, which makes it difficult to scalc. Although the two methods do not need learning, EdgeSketch+ still performs faster than MPSketch by two orders of magnitude. The main reasons are as follows: 1) MPSketch sketches a large, aggregated information pool, and even iterates more than EdgeSketch+ on Bitcoin-OTC capture sufficient information; 2) The SVM classifier training based on the Hamming kernel is time-consuming This again implies that MPSketch has the limited capabilities of capturing the patterns in the signed networks.
In addition, we would like to note that all the competitors implicitly/xxpliiityy represent the nodes or edges 32/64-bit embedding vectors, while proposed EdgeSketch+ algorithm only generates the binary vectors with nearly no sacrificing the result quality, which means that EdgeSketch+ is able to enjoy lower memory footprints than the compared methods in signed network embedding. Overall, our proposed EdgeSketch+ model achieves an excellent balance between accuracy and efficiency.
H
Limitations
This work has two main limitations. First, although EdgeSketch+ operates in an unsupervised manner without using edge signs during sketching, it relies on downstream classifiers that require labeled data. This setup may limit its applicability in domains where labeled signed edges are scarce. Second, the current approach leverages simplicial complexes constructed from triangle structures, which may miss relevant higher-order interactions not captured by 2-simplices. Extending the framework to incorporate digees-dimensional simplices could provide more comprehensive modeling, albeit the cost of increased computational complexity.
We also assess MPSketch by logistic regression, but underperforms.
24


Reviews:
[{"review_id": "EFUxp8mAf1", "reviewer": "Reviewer_Lwco", "summary": "This paper introduces EdgeSketch+, a fast and simple signed network sketching algorithm that leverages simplicial complexes and Locality Sensitive Hashing (LSH) to efficiently generate edge embeddings for signed graphs. Instead of learning node embeddings and deriving edge scores, it directly embeds edges by exploiting higher-order simplicial structures (0-, 1-, and 2-simplexes) to capture rich local geometry, while maintaining scalability through randomized hashing. Experimental results on standard signed network datasets demonstrate competitive prediction performance with up to 546× lower runtime than GNN-based baselines, with ablation studies highlighting the importance of simplicial components.", "questions": "- Clarify the notation and terminology in Algorithm 1.\n- State explicitly the dimensionality of the embedding after each iteration and after aggregation.\n- The seed is chosen and is not random. Was it fixed arbitrarily or cherry picked? How sensitive are the results to this choice? Is fixing a single seed standard practice in this line of work? Some discussion of randomness/stability would help. \n- The largest signed dataset used (Epinions) is still small by modern standards. Scalability is a known issue with such higher-order methods. Can the authors comment on whether EdgeSketch+ applies to unsigned graphs, and how it might scale and perform on much larger datasets like those in OGB?", "limitations": "Authors have addressed the limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths\nThe paper is well-written and easy to understand. EdgeSketch+ is simple yet elegant — combining higher-order simplicial structures with locality-sensitive hashing to capture rich interactions without expensive training. Its ability to use 0-, 1-, and 2-simplexes efficiently while preserving key properties is compelling, and the theoretical guarantees strengthen the contribution. The experiments are thorough and well-designed, showing competitive or better accuracy than strong baselines with much lower runtime. The ablation studies convincingly show the importance of each simplicial component and highlight the scalability and practicality of the approach.\n\n### Weaknesses\nWhile EdgeSketch+ is the first to use simplicial complexes for signed networks, the overall architecture presented has been around for a while.\n\nIn Algorithm 1, lines 5 and 6 refer to convolution operators `ConvB1` and `ConvB2`. The two arrays make it look like $L_1$ and $L_2$ are used for convolution. However, the text says they use adjacency matrices $B_1$, $B_2$. Shouldn’t these be better referred to as $ConvL_0$ and $ConvL_2$ in the context of Hodge Laplacians, for consistency? Please clarify notation and what $L_0$, $L_1$, $L_2$ actually mean in this step. Also, the dimension of embeddings after each step is not clear and would be helpful to include them to for ease of reading.\n\nSince the signed edges can be treated edge orientation in a simplicial complex, it would strengthen the empirical evidence if EdgeSketch+ is compared with simplicial representation learning methods like SaNN, SGAT, etc.", "was_revised": true, "final_justification": "The authors have adequately addressed my concerns in their rebuttal, and I am satisfied with the clarifications provided. While the contribution is somewhat incremental, the method is technically sound, efficient, and well-supported by experiments. I will maintain my positive evaluation.", "rebuttal": "*Q1: Notation & terminology*\n\nA1: The edge embedding model focuses on the adjacency relationships related to edges in the convolution operation. $B_1$ describes the boundary adjacency relationships between nodes and edges, $B_2$ describes the upper boundary adjacency relationships between triangles and edges. The Hodge Laplacian  $L_1$, computed from  $B_1$ and $B_2$ via Eq. (1), encodes the edge-to-edge adjacency relationships, while $L_0$ and $L_2$ describe the adjacency relationships of nodes and triangles, respectively. Therefore, we use $B_1$ and $B_2$ rather than $L_0$ and $L_2$.\n\n*Q2: dimensionality of embedding*\n\nA2: After each iteration and aggregation, the embedding dimension is 300.\n\n*Q3: seed*\n\nA3: In the EdgeSketch+ code, we use the current system time as the random seed. As mentioned in Appendix E, each experiment is independently repeated for 5 runs with different random seeds for each run, which complies with standard practice.\n\n*Q4: larger dataset in OGB*\n\nA4: We select ogbl-biokg from the OGB dataset, which contains 5,088,434 edges, and generate edge embeddings using  EdgeSketch+. The embedding time is as follows.\n| Dataset     |  Runtime (s) |\n|-------------|-------------|\n| ogbl-biokg  | 6683.48  |\n\nThe results demonstrate the scalability of our method."}, {"review_id": "krstmWt0J5", "reviewer": "Reviewer_uWUZ", "summary": "This paper points out the limitations of node-centric graph embedding methods for link sign prediction, and proposes to overcome the limitations by introducing higher-order interactions in the form of simplicial complexes. It proposes a learning-free method EdgeSketch+, which computes edge embeddings iteratively by performing locality-sensitive hashing on newly defined edge surroundings. Theoretical analysis is provided to characterize the key properties of EdgeSketch+. Experimental results on four public datasets validate the effectiveness of EdgeSketch+. Extensive ablation studies help to understand the characteristics and behaviors of EdgeSketch+, e.g., the scalability, and the sensitivity to the hyperparameters.", "questions": "Q1. To my understanding, triangles play special roles in link sign prediction. There are multiple possible configurations of a triangle, which present different real-world meanings and have different impacts on link sign prediction. Is it possible to relate your methods to such observations? For example, you may build a connection with the traditional theory of signed networks, provide statistics on different configurations of triangles, or provide a case study on how these triangles improve the accuracy of link prediction.\n\nQ2. Can you discuss how EdgeSketch+ can deal with dynamic signed networks? For example, how to update the simplex embeddings and which are relevant? What is the time complexity and space complexity?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nS1. This paper is clearly and concisely written. It is easy to follow and understand.\n\nS2. It is novel to explore simplicial complexes for link sign prediction. The choice of LSH achieves a good balance between accuracy and efficiency, which makes EdgeSketch+ practical for large-scale real-world datasets.\n\nS3. The theoretical analysis characterizes the key properties of EdgeSketch+, which help to understand the behavior of the algorithm.\n\nS4. The experimental design is comprehensive, and the results are significant in most cases. Specifically, the results on the two large datasets, Slash. and Epin., validate the superior performance of EdgeSketch and its computational efficiency.\n\n**Weaknesses**\n\nCurrently, I am not aware of any major weaknesses in the paper.", "was_revised": true, "final_justification": "The rebuttal from the authors has addressed my concerns. Specifically, their answer to Q1 enhances the explainability of EdgeSketch+, and the answer to Q2 precisely describes how EdgeSketch+ can be extended to dynamic signed networks.", "rebuttal": "*Q1: multiple configurations of a triangle ... statistics on different configurations of triangles*\n\nA1: Different triangle types — such as (+,+,+), (+,+,-) (+,-,-) and (-,-,-) configurations — have distinct real-world interpretations under social balance theory, and potentially different impacts on link sign prediction. To empirically explore this, we conduct an ablation study where we selectively exclude specific types of triangles. Specifically, we produce four ablation variants on  Bitcoin-OTC by removing one type of  (+,+,+), (+,+,-) (+,-,-) and (-,-,-) during simplex extraction. \n| Metric | Paper | w/o (-,-,-) | w/o (+,-,-) | w/o (+,+,-) | w/o (+,+,+) |\n| --------- | ------ | ------- | ------- | ------- | ------- |\n| Binary-F1 | 0.9681 | 0.9606  | 0.9569  | 0.9615  | 0.9512  |\n| Accuracy  | 0.9413 | 0.9361  | 0.9314  | 0.9376  | 0.9342  |\n| AUC       | 0.8695 | 0.8578  | 0.8567  | 0.8594  | 0.8564  |\n| Macro-F1  | 0.8137 | 0.8098  | 0.8006  | 0.8096  | 0.8048  |\n\nAs shown in the updated results, excluding different triangle types generally leads to noticeable performance drops, with the (+,-,-) and (+,+,+) configurations contributing more significantly to prediction quality. This observation aligns with social balance theory, where (+,+,+) and (+,-,-) are regarded as balanced configurations, indicating structurally stable and consistent relationships. The fact that removing these balanced triangles leads to larger performance degradation suggests that such structures carry stronger and more reliable predictive signals in signed networks. In contrast, unbalanced configurations (e.g., (+,+,-) and (-,-,-)) are often transient or noisy, contributing less decisively to link sign prediction. These results highlight that EdgeSketch+ effectively captures higher-order signed structures and exploits structurally meaningful patterns aligned with established social theories.\n\n\n*Q2: dynamic signed networks*\n\nA2:\n EdgeSketch+ is naturally suited for dynamic signed networks due to its non-learning and localized design. When a new edge is added or removed, only its surrounding simplicial structures—specifically, the affected 1- and 2-simplexes—need to be updated. For example, when a new edge connects two nodes, we identify newly formed triangles (2-simplexes) with shared neighbors and update the relevant boundary matrices accordingly. Embedding regeneration is then performed only for the modified edge and its neighboring simplices, using the same pre-sampled LSH projections to ensure consistency. This design avoids recomputing embeddings for the entire graph. \n\nFor a static graph, the overall time complexity is $O(N_1^2 + \\bar{v} N_1D^2R)$, where $N_1$ is the number of 1-simplices (edges), $\\bar{v}$ is the average node degree, $D$ is the embedding dimension, and $R$ is the number of hash rounds. This complexity covers the extraction of simplicial complexes, construction of boundary and Laplacian matrices (e.g., $\\mathrm{B}_1$, $\\mathrm{B}_2$, and $\\mathrm{L}_1$), and multiple-round random projections. The corresponding space complexity is $O(N_1D + D^2R)$, including storage for edge embeddings, Hodge Laplacians, and random projection vectors.\n\nFor dynamic signed networks, the incremental time complexity is $O(\\Delta ED^2R)$, where $\\Delta E$ is the number of modified edges. Due to the fixed projection mechanism, many previously computed embeddings can be cached and reused, which further improves runtime and memory efficiency. The space complexity during update remains $O(N_1D + D^2R)$, as it reuses the same embedding structure and projection vectors without duplicating storage."}, {"review_id": "Z5ZdsISK7H", "reviewer": "Reviewer_9SJs", "summary": "Graph neural networks are a popular modeling paradigm for graph structured data, and have enjoyed popularity in both research and industrial settings for exactly this purpose. One common application of GNNs is the construction of node-embeddings that can be used in downstream applications through transfer learning. While popular, this approach traditionally suffers from two different problems -- poor computational scaling and limited expressivity. This is usually done by computing embeddings, and is usually done in a self-supervised fashion. It is well known at this point that using equivariant GNNs to do this at a node-level leads to the isomorphic node problem. For signed graphs, many methods further depend on balance theory which, when violated, can lead to poor results. The authors situate their work in this area of the literature, and present EdgeSketch+. This method presents a computationally efficient technique for generating edge-embeddings, with a strong focus specifically on signed graphs. Efficiency is realized through the use of locality sensitive hashing, which is done in a way that captures higher-order simplical structures. The authors explore the theoretical aspects of their work and contribute multiple interesting bounds, and then present experiments on link sign prediction intended to justify their method.", "questions": "1. How would you extend this to higher-order simplical complexes?\n2. Are there any modifications that you'd make to the method to make it inductive? It seems like none would be required, but I wanted to make sure.\n3. How would you make the model more expressive?\n4. Would a more advanced decoder yield better results?\n5. Could this be applied to non-signed link prediction?\n6. How does computational performance change as edge density increases?\n7. How sensitive is the method to the choice of distance metric in the LSH family?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n1. The work is well motivated and addresses a significant problem in the space.\n2. The work is well written and presented. There are no significant typos, and is relatively easy to follow despite the mathematically intricate nature of the work.\n3. Figure 1 provides a fantastic intuition for the problem that sets the tone for the rest of the work\n4. 4.3, the incorporation into linear learning models is just _cool_.\n5. Runtime performance validates that this model just works and is just fast. 546x speedup is incredible.\n6. The hyperparameter sensitivity is clearly experimented and explored, and the method looks fairly robust\n7. The theoretical results are clearly outlined and succinct. In particular, the concentration bound is particularly clear.\n8. The ablation studies clearly demonstrate the importance of each component\n\n**Weaknesses**\n1. The experiments also lack standard deviations\n2. Only 4 datasets\n3. Limited to 2-simplicies without a path forward towards expanding to higher-order tasks\n4. The application is quite limited in that it's focused only on signed networks with strong triangular structures.\n5. Missing baselines, although I'm happy to give them a pass given that the code isn't publicly available.", "was_revised": true, "final_justification": "The authors provided clear answers to my questions and have further improved their work. Initially I viewed this paper as a clear accept and this is only more true with the improvements.", "rebuttal": "*Q1: extend to higher-order simplicial complexes*\n\nA1: We extract higher-order simplicial complexes from the graph, and then construct the corresponding adjacency matrices and the corresponding Hodge Laplacians  to describe the adjacency relationships between simplices.\n\n*Q2: any modifications ... to make it inductive?... It seems like none would be required, but I wanted to make sure*\n\nA2: The model does not require specific modifications. If encountering more complicated graphs that need to be extended to higher dimensions, similar to dimensions 0, 1, and 2, we will construct the corresponding boundary adjacency matrix  $\\mathrm{B}$ and compute Hodge Laplacian  $\\mathrm{L}$.\n\n*Q3: How ... more expressive*\n\nA3: To enhance the model's expressiveness, we could explore extending the dimensionality of simplices, incorporating edges into higher-order simplicial structures, or integrating additional contextual features, such as edge weights or temporal dynamics, to enrich its representational capacity. In future work, we will further explore to improve the expression ability.\n\n*Q4: more adavenced decoder?*\n\nA4: We conduct an experiment employing a Multilayer Perceptron (MLP). Although this approach is more time-consuming, the classification results are slightly better than those of logistic regression, as shown in the table below.\n\n Bitcoin-alpha\n| Metric    | Paper  | MLP | \n| --------- | ------ | ------- | \n| Binary-F1 | 0.9780 | 0.9791  | \n| Accuracy  | 0.9581 | 0.9605 |\n| AUC       | 0.8829 | 0.9175 | \n| Macro-F1  | 0.7687 | 0.8110 | \n| Runtime(s) | 4.03 | 40.10 |\n\nSlashdot\n| Metric    | Paper  | MLP | \n| --------- | ------ | ------- | \n| Binary-F1 | 0.9209 | 0.9223  | \n| Accuracy  | 0.8729 | 0.8786  |\n| AUC       | 0.8914 | 0.9223  | \n| Macro-F1  | 0.7995 | 0.8222  | \n| Runtime(s) | 140.44 | 1238.07 |\n\n*Q5: applied to non-signed link prediction?*\n\nA5: The goal of non-signed link prediction is to predict whether an edge exists between two nodes in an unsigned network. By contrast, signed link prediction aims to predict the signs of **existing** edges  in a signed network, representing a fundamentally different task. Our method for signed networks relies on existing network structures to generate edge representations, which currently has limited applicability to non-signed link prediction. In future work, we will further explore to find suitable solutions.\n\n*Q6: computational performance change .... edge density increases*\n\nA6: In Section 5.3 Scalability, we test the time consumption as edge density increases with a fixed number of nodes. The experimental results show that the time displays slow quadratic growth.\n\n*Q7: distance metric in LSH*\n\nA7: In Section 5.6, we evaluate the effects of two different distance metrics on the results. Combined with the theoretical analysis in Section 4.2, we conclude that the Hamming distance is a suitable distance metric for the LSH-based embedding method."}, {"review_id": "IItr1tnheU", "reviewer": "Reviewer_dXe3", "summary": "This paper introduces a novel and well-motivated edge-based signed network sketching method, which preserves higher-order relationship from simplicial complexes beyond the traditional node-centric modeling in the signed network. The method is elegant in its simplicity yet powerful in its expressiveness, marking a significant departure from traditional node-based embedding techniques. To my best knowledge, very few existing works have explored the use of higher-order topological structures in graphs, particularly for signed networks. The authors skillfully bridge the gap between traditional signed graph sketching and higher-order topology, demonstrating that capturing structures beyond pairwise interactions significantly enhances downstream performance, avoiding the issue from the balance theory. Furthermore, the Locality-Sensitive Hashing (LSH) framework helps to efficiently capture higher-order interactions without the computational burden of traditional GNNs. Particularly, integration with linear learning models guarantees real-world large-scale applications. Consequently, the method effectively balances performance and efficiency while maintaining strong representational capability. The work is both theoretically grounded and practically impactful, offering a scalable and versatile tool for signed network analysis.", "questions": "see the weaknesses", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and easy to follow.\n2. The idea of simplicial complexes as higher-order abstraction in signed network embedding is interesting. The method beyond the traditional node-centric scheme provides a new insight into signed network embedding. \n3. Extensive experimental results across multiple datasets and baselines highlight the effectiveness, efficiency, scalability, and domain-agnostic nature of the proposed framework.\n4. The paper provides solid theoretical analysis, including LSH-based theory, error bound, and complexity, with the performance guaranteed. Particularly, incorporation with linear models benefits large network application, avoiding the issue of SVM training, and also the experiments verify this point. \n\nWeaknesses:\n\n1. It would be better if the paper provides a notation table to clarify many symbols.\n2. The authors empirically verify the necessity of edge embedding. The authors are encouraged to further demonstrate that the method effectively preserves the essential structural information of the data.  \n3. Section 4.2.3 theoritically analyzes the error bound. Empirical study is encouraged.", "was_revised": true, "final_justification": "The authors have adequately addressed all of my concerns in their rebuttal. I am satisfied with their clarifications and maintain my positive evaluation. I recommend acceptance of the manuscript.", "rebuttal": "*Q1: Notation table*\n\nA1: The notation table is as follows\n|Notation|Description|\n|-----------------|-------------|\n|$g$|Signed network where edges have positive or negative signs|\n|$\\mathcal{V}$|Set of nodes in the signed network|\n|$\\mathcal{E}$|Set of edges in the signed network|\n|$v$|A node in the signed network|\n|$e$|An edge in the signed network, typically a 1-simplex|\n|$\\mathcal{S}_k$|A $k$-simplex|\n|$\\mathbf{x}_{\\mathcal{S}}$|Embedding of simplex $\\mathcal{S}$|\n|$\\mathcal{C}$|A simplicial complex|\n|$\\mathrm{B}_i$|Boundary adjacency matrix for $i$-simplices|\n|$\\mathrm{L}_i$|$i$-dimensional Hodge Laplacian|\n|$\\mathcal{H}$|A family of randomized functions|\n|$\\mathbf{h}$|Random vector|\n|$\\kappa$|Hash kernel|\n\n*Q2: essential structural information*\n\nA2: To assess whether our edge embedding method preserves essential structural information, we perform a distributional similarity analysis between the embeddings before and after sketching.\nSpecifically, we apply Kernel Density Estimation (KDE) to the pre- and post-sketching embeddings and compute two standard distributional divergence metrics: KL divergence and JS divergence. These metrics measure how similar two distributions are, where smaller values indicate stronger preservation of structural characteristics.\nResults are summarized below:\n| Dataset        | KL Divergence | JS Divergence |\n|----------------|---------------|---------------|\n| Bitcoin-alpha  | 0.0143        | 0.0027        |\n| Bitcoin-OTC    | 0.0062        | 0.0007        |\n| Slashdot       | 0.0003        | 0.0001        |\n| Epinions       | 0.0048        | 0.0003        |\n\nThese consistently low divergence values demonstrate that the proposed method preserves the overall distribution and structural patterns of edge features after sketching. This further supports the effectiveness of our edge embedding approach in retaining meaningful information from the original data.\n\n*Q3: error bound ... empirical study* \n\nA3: We conduct an empirical study to evaluate how well the sketch-based estimator approximates the true edge similarity under different deviation thresholds $\\epsilon$. Specifically, using the Epinions dataset as a representative benchmark for signed networks, we compute the probability that the deviation between the estimated similarity and the true similarity exceeds a given $\\epsilon$, and compare it with the theoretical upper bound $2exp⁡(−2D\\epsilon^2)$.\n| $\\epsilon$     | the probability of deviation | upper bound |\n|-------|-------------------------------|-------------|\n| 0.040  | 0.49941                       | 0.52729     |\n| 0.0425| 0.47720                       | 0.48794     |\n| 0.045  | 0.45499                       | 0.44859     |\n| 0.0475| 0.43377                       | 0.40824     |\n| 0.050  | 0.41255                       | 0.36788     |\n\nThe empirical deviation probabilities closely follow the theoretical bound. This demonstrates that the error between the estimated and true similarities remains tightly concentrated, providing empirical support for the theoretical guarantee of our estimator."}]

Author rebuttal:

Meta-review: The paper introduces EdgeSketch+, a model to learn edge embeddings in signed graphs, balancing accuracy and efficiency. The main idea of the model is to represent edges through an LSH technique, capturing higher-order information of the underlying simplicial complex. The work has several clear merits highlighted by the reviewers, including the novelty of the methodology, the good experimental results, and the theoretical support. During the discussion period, the authors provided clarifications and addressed several of the reviewers' concerns. Overall, the paper makes a solid and well-motivated contribution.
Decision: Accept (poster)