Beyond Node-Centric Modeling: Sketching Signed Networks with Simplicial Complexes

Q1: Notation table

A1: The notation table is as follows

Q2: essential structural information

A2: To assess whether our edge embedding method preserves essential structural information, we perform a distributional similarity analysis between the embeddings before and after sketching. Specifically, 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. Results are summarized below:

These 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.

Q3: error bound ... empirical study

A3: 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)$.

The 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.

Q1: multiple configurations of a triangle ... statistics on different configurations of triangles

A1: 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.

As 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.

Q2: dynamic signed networks

A2: 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.

For 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.

For 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.

Q1: extend to higher-order simplicial complexes

A1: 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.

Q2: any modifications ... to make it inductive?... It seems like none would be required, but I wanted to make sure

A2: 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}$.

Q3: How ... more expressive

A3: 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.

Q4: more adavenced decoder?

A4: 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.

Bitcoin-alpha

Slashdot

Q5: applied to non-signed link prediction?

A5: 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.

Q6: computational performance change .... edge density increases

A6: 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.

Q7: distance metric in LSH

A7: 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.

Q1: Notation & terminology

A1: 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$.

Q2: dimensionality of embedding

A2: After each iteration and aggregation, the embedding dimension is 300.

Q3: seed

A3: 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.

Q4: larger dataset in OGB

A4: 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.

The results demonstrate the scalability of our method.

OGB Results

Thank you for the suggestion. We select ogbl-biokg from the OGB benchmark to provide a large-scale, real-world graph scenario. Since our task is formulated as edge classification, we report Accuracy, which directly measures the correctness of edge classfication. The ogbl-biokg leaderboard focuses on knowledge graph completion, which involves predicting missing entities in triplets (either (entity, relation, ?) or (?, relation, entity)) in terms of MRR; by contrast, our method predicts edge signs/labels by generating edge representations, which does not generate tail predictions for query triples as required by the task definition. Therefore, these two tasks are fundamentally different in nature, making our approach unsuitable for knowledge graph completion. Regarding the runtime discrepancy, the previously reported 6683.48s corresponds to the time required for generating the edge embeddings, while the 9876.68s includes both embedding and downstream classification.

Comparison with Simplicial Baselines

We have carefully reviewed the TopoBench framework and the corresponding paper [1]. As stated in Section 5.1 of the TopoBench paper,

"Four types of tasks are considered: node classification (seven datasets), node regression (seven datasets), graph classification (seven datasets), and graph regression (one dataset)."

None of them includes edge classification tasks. Moreover, after inspecting the available codebase, we confirm that it does not provide implementations for edge embedding or edge-level tasks, which are central to our setting. As a result, we are currently unable to run these methods for a fair comparison on our task.

[1]Telyatnikov L, Bernardez G, Montagna M, et al. Topobench: A framework for benchmarking topological deep learning[J]. arXiv preprint arXiv:2406.06642, 2024.