Signed Graph Representation Learning: A Survey

In this subsection, we introduce notations and give the necessary backgrounds on the signed graph.

Notations. We denote a signed graph as $\mathcal{G}=\{\mathcal{V},\mathcal{E},s\}$, where $\mathcal{V}$ is the node sets in a signed graph $\mathcal{G}$, and $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ represents the sets of edges in graph $\mathcal{G}$ with sign $s$. $\mathcal{E}^{+}$ and $\mathcal{E}^{-}$ denote the sets of positive and negative links, respectively. It means that there is at most one signed edge between any two nodes. $\mathcal{E}$ contains $\mathcal{E}^{+}$ and $\mathcal{E}^{-}$. Similarly, we can divide the neighbors of node $v_{i}$ into positive neighbors $\mathcal{N}_{i}^{+}$ and negative neighbors $\mathcal{N}_{i}^{-}$. Also, $\mathcal{G}$ can be denoted as the adjacency matrix $A$, where $A_{ij}=1$ means there exists a positive link between $v_{i}$ and $v_{j}$, $A_{ij}=-1$ denotes a negative link between $u_{i}$ and $u_{j}$, and $A_{ij}=0$ means there is no link between $u_{i}$ and $u_{j}$. Usually, $s\in\{1,-1\}$ is the sign of the edge¹¹1The signed network can be further associated with weights. Kumar et al. (2016) and $\mathcal{E}^{+}\bigcap\mathcal{E}^{-}=\emptyset$;

Problem formulation. Given a signed graph $\mathcal{G}=\{\mathcal{V},\mathcal{E},s\}$, SGRL aims to encode the nodes $\mathcal{V}$ into low-dimensional vectors $Z\in\mathbb{R}^{d\times|\mathcal{V}|}$ as follows:

$$f(\mathcal{G})\rightarrow Z,$$

(1)

where $d$ is the embedding size ($d\ll|\mathcal{V}|$), and $f$ is the encoder function which can be Network Embedding or GNNs. The low-dimensional vectors $Z$ should be useful in downstream machine-learning tasks.

Datasets. Beyond social relationships, antagonistic relationships also exist in complex systems like diplomacy, biology, and chemistry. Examples include cooperative and hostile relations in international affairs, excitatory and inhibitory relationships among neurons in biology Tang et al. (2016b), and the side effects between chemical drugs Zitnik et al. (2018). While these complex systems also feature signed links, this paper primarily focuses on signed links in social relationships, where the entities involved are individuals. We have collected and organized datasets commonly used for modeling signed networks, as shown in Table 1. From Table 1, it can be seen that the modeling of signed networks can be categorized into three different types based on the context of the links. Thus, the scenarios of signed networks are divided into: social relationships between people, object opinions towards specific topics, and interaction feedback in human-computer interaction.

Machine learning tasks Common graph machine learning tasks, as detailed in Wu et al. (2020b), typically fall into three distinct categories: Node-level, Link-level, and Graph-level. Node-level graph machine-learning tasks usually involve applying machine learning to predict nodes’ attributes. Link-level tasks primarily focus on predicting the relationships between edges in the network²²2 In signed graphs, link prediction typically includes predicting the sign of a given link (binary classification) and predicting both the existence and the sign of a link (3-class classification).. In graph-level machine learning tasks, there are generally two main subjects of study: subgraph-level and whole-graph-level. At the subgraph level, the focus is on clustering nodes within social networks, with common tasks including Node Clustering He et al. (2022b) and Community Detection Sun et al. (2020). Whole-graph-level tasks mainly encompass Graph Classification Liu et al. (2023) and Graph RegressionLi et al. (2019). It is worth mentioning that the mainstream machine learning task of SGRL is the Link-level.

The architecture of current popular SGNN models, such as SGCN Derr et al. (2018) and SNEA Li et al. (2020) follows the spatial unsigned GNNs utilizing neural message passing among nodes to define convolutions on graphs, but adopt the following mechanism. The representation of a node $v_{i}$ at a given layer $\ell$ is defined as

$$h_{i}^{(\ell)}=[h_{i}^{pos(\ell)},h_{i}^{neg(\ell)}],$$

where $h_{i}^{pos(\ell)}$ and $h_{i}^{neg(\ell)}$ respectively denote the positive and negative representation vectors of node $v_{i}\in\mathcal{V}$ at the $\ell$th layer, and $[,]$ denotes the concatenation operation. The unsigned GNN message passing is defined as

$$\scriptsize h_{i}^{(l)}=\text{COMBINE}^{(\ell-1)}\left(h_{i}^{(\ell-1)},\text{AGGREGATE}^{(\ell-1)}(\{h_{j}:v_{j}\in\mathcal{N}_{i}\})\right),$$

(2)

where COMBINE and AGGREGATE are differentiable functions (e.g., Mean, Max). Different from GNNs, SGNNs accommodate positive and negative edges using a two-part representation, and a more involved aggregation scheme. For example, when $\ell>1$, the positive part of the representation for node $v_{i}$ could aggregate information from the positive-representation of its positive neighbors and the negative-representation of its negative neighbors.

	$\displaystyle h_{i}^{pos(\ell)}=$	$\displaystyle\text{COMBINE}^{(\ell)}\Biggl{(}h_{i}^{pos(\ell-1)},$		(3)
		$\displaystyle\text{AGGREGATE}^{(\ell)}(\left\{h_{j}^{pos(\ell-1)}:v_{j}\in\mathcal{N}_{i}^{+}\right\},\left\{h_{j}^{neg(\ell-1)}:v_{j}\in\mathcal{N}_{i}^{-}\right\})\Biggl{)}$
	$\displaystyle h_{i}^{neg(\ell)}=$	$\displaystyle\text{COMBINE}^{(\ell)}\Biggl{(}h_{i}^{neg(\ell-1)},$
		$\displaystyle\text{AGGREGATE}^{(\ell)}(\left\{h_{j}^{neg(\ell-1)}:v_{j}\in\mathcal{N}_{i}^{+}\right\},\left\{h_{j}^{pos(\ell-1)}:v_{j}\in\mathcal{N}_{i}^{-}\right\})\Biggl{)},$

After $\ell$ SGNN layers, we have the final representation $Z_{i}=\text{CONCATENATE}(h_{i}^{\ell},h_{i}^{\ell})$. In addition to CONCATENATE, we can also use MLP or ATTENTION mechanisms to fuse positive and negative representations.

In the realm of traditional social network theory, a considerable amount of research has focused on the concepts of Homophily and Heterophily. However, when negative links are introduced into social networks, many assumptions no longer hold. For example, heterophily assumptions also suggests that connected nodes are prone to have different properties or labels. However, it significantly differs from Balance theory in its inability to capture certain concepts like “an enemy of an enemy is a friend”. In this section, we introduce two important sociological theories that are more prevalent in signed graphs: Balance theory and Status theory.

Balance theory Heider (1946), a concept in social psychology, was developed by Fritz Heider in the 1940s. The theory focuses on the idea that individuals seek cognitive consistency and balance in their attitudes and relationships within social networks. According to balance theory, people strive to maintain a psychological balance in their interactions. In the context of triadic relationships, where three entities are connected by positive and negative ties, balance theory suggests that individuals tend to prefer balanced configurations. For example, if $v_{i}$ has a positive relationship with $v_{j}$ and a negative relationship with person $v_{k}$ there is an imbalance in the triad. To restore balance, $v_{i}$ might either develop a positive relationship with $v_{k}$ or a negative relationship with person $v_{j}$. Figure 2 shows all four isomorphism types of triads.

Status theory Leskovec et al. (2010) is relevant for directed networks compared to balance theory is naturally defined for undirected networks. Social status can be represented in a variety of ways, such as the rankings of nodes in social networks, and it represents the prestige of nodes. In its most basic form, Status theory suggests that $v_{i}$ has a higher status than $v_{j}$ if there is a positive link from $v_{j}$ to $v_{i}$ or a negative link from $v_{i}$ to $v_{j}$. In Figure 2, we can see the first two satisfy Status theory, while the latter two do not. This status relationship is transitive.

When comparing the two theories, Balance theory can be understood as simulating individual preferences, like liking or disliking, and primarily applies to undirected signed graph. On the other hand, Status theory is based on the assessment of individuals’ social status and is direction-dependent. Both theories can be modeled within signed directed triads (see Figure 2). Chen et al. (2018) propose to use triplets ($i$, $j$, $k$) to comparatively measure and analyze the two theories. They found that in the Slashdot and Epinions datasets, approximately 75% of the triangles satisfy both sociological theories simultaneously, and only about 1% of triangles satisfy neither.

Shallow network embedding typically refers to those methods with simple, linear non-deep learning structures. This type of method is mainly divided into two aspects: methods based on random walks (SNE Wang et al. (2017), SIGNet Islam et al. (2018), SIDE Kim et al. (2018), ROSE Javari et al. (2020)), SSNE Lu et al. (2019) and methods based on matrix factorization SPONGE Cucuringu et al. (2019). Below, we will introduce these methods separately.

SNE Wang et al. (2017) is the first research on signed network embedding, which adopts the log-bilinear model (variant of Skip-Gram model) to capture both node’s path and sign information. One issue present is that the relationship between the target node and multi-hop neighbor nodes is determined by the edge sign between multi-hop neighbors and the previous-hop neighbors. Specifically, for a target node $v$ and a path $h=[u_{1},u_{2},\cdots,u_{l},v]$, the relationship between node $v$ and $u_{1}$ is decided by $\mathcal{E}_{u_{1},u_{2}}$. If $\mathcal{E}_{u_{1},u_{2}}>0$, their relationship is positive. Conversely, it is negative.

SIGNet Islam et al. (2018). This method encodes network structural information based on the word2vec model, considering both undirected and directed graph scenarios. A major innovation of this approach lies in proposing a new negative sampling method. In signed graphs, where relationships between nodes can be positive or negative, the paper suggests that nodes with positive relationships should not be included in the negative sampler set and introduces a method based on balance theory to compute the positive and negative relationships of multi-hop neighbors. In summary, neighbors connected to the target node by an even number of negative edges are assigned to the positive relationship set, while those connected by an odd number are assigned to the negative relationship set.

SSNE Lu et al. (2019) incorporates status theory into signed network embedding. In status theory, a higher status node $v_{i}$ has a positive link to $v_{j}$, while a lower status node $v_{i}$ has a negative link to $v_{j}$. SSNE represents positive links as triplets $(v_{i},\mathcal{\ell}{+},v_{j})$, where the embedding space forces the combined embeddings of $h_{i}+h_{\mathcal{\ell}{+}}$ to be close to the embedding of $h_{j}$. Conversely, for negative links, the model encourages the embedding $h_{i}-h_{\mathcal{\ell}_{+}}$ to be close to the embedding of $h_{j}$.

SIDE Kim et al. (2018) proposed signed network embedding method builds upon truncated random walk, introducing a comprehensive likelihood formulation for signed directed connections that consistently represents both positive and negative edges. By incorporating bias factors in the likelihood function to model individual connectivity, the approach enhances the accuracy of the embedding process. Furthermore, the random walk sampling process and likelihood formulation are extended to accommodate multi-step relationships, encompassing both sign and direction. This method intricately links vector space geometry with social phenomena in networks, including homophily, preferential attachment, and balance theoretic behaviors. This association dissects the dual factors influencing link formation, establishing a robust foundation for the broad application of the method in the analysis of signed directed networks.

ROSE Javari et al. (2020). This papers attempts to address two issues. First, existing social theories fail to explain the structure in all signed graphs, meaning that not all structures conform to balance theory and status theory. Second, current signed network embedding only considers predicting the positive or negative nature of existing edges, overlooking the prediction of edge existence. To tackle these challenges, ROSE does not rely on any specific social theory for node encoding. Instead, it adopts a network transformation-based embedding approach. This involves assigning multiple roles to the same node, transforming the signed graph into an unsigned graph. Subsequently, unsigned network embedding methods can be applied to encode the graph structure.

SPONGE (Signed Positive Over Negative Generalized Eigenproblem) Cucuringu et al. (2019) is a $k$-way spectral clustering algorithm on signed networks. Inspired by constrained clustering, a new $k$-way objective of signed graph cut is designed, which seeks the global clustering assignment for each node by minimizing the trade-off between two measures of badness, i.e., the normalized weight of positive edges cross different clusters and the reciprocal of that of negative edges cross different clusters. The new objective is cast as a regularized spectral algorithm based on solving a generalized eigenproblem. The key of solving it is to derive the goal matrix, and then perform eigenvalue decomposition on the goal matrix to obtain its eigenvectors corresponding to the $k$-smallest eigenvalues. Simultaneously, it also requires that the derived embedding vectors be orthonormal for dropping the discreteness constraints. Moreover, this work also provides a detailed theoretical analysis w.r.t. the robustness of SPONGE in the Signed Stochastic Block Model framework.

Compared to shallow network embedding methods, deep models in the context of network embedding refer to those approaches that involve deep learning architectures with multiple layers in the neural network. This is currently one of the mainstream methods in SGRL.

SiNE Wang et al. (2017) is the first method which employs deep learning model to learn low-dimensional vector representations for nodes of a given signed graph. Follow the assumption of extended structural balance theory, in embedding space, users should sit closer to their “friends” (or users with positive links) than their “foes” (or users with negative links). Based on this assumption, in order to preserve the structure information of signed graph, special triplets (e.g., $(v_{i},v_{j},v_{k})$) (with one positive link $e_{ij}=1$ and one negative link $e_{ij}=-1$) are extracted, the learned similarity function should make sure $f(v_{i},v_{j})>f(v_{i},v_{k})$.

SGCN Derr et al. (2018) tackles the challenge of applying Graph Convolutional Network (GCN) Kipf and Welling (2017) to signed networks. GCN excels in unsigned networks, but struggles with the semantic and structural complexities of negative links. SGCN introduces balance theory to categorize neighbors as positive or negative based on the number of negative edges. It maintains dual representations for each node—balanced set for positive relationships and unbalanced set for negative ones. This approach, using an extended balance theory for judging multi-hop neighbors, enables SGCN to effectively model the nuanced relationships in signed graphs.

DNE-SBP Shen and Chung (2018) pioneers the application of semi-supervised Stacked Autoencoder (SAE) for embedding signature networks. This deep embedding model focuses on learning low-dimensional node vector representations while preserving structural balance in signed networks. By employing semi-supervised stacked autoencoders, DNE-SBP reconstructs the adjacency connections in the given signed network. The model prioritizes sparse negative connections by applying a higher penalty to negative links during reconstruction. To maintain structural balance, pairwise constraints are incorporated, ensuring nodes connected by positive links in the embedding space are closer than those connected by negative links. This innovative approach addresses the limitation of SDNE in capturing crucial structural balance properties in signature networks.

SNEA Li et al. (2020). Attention mechanisms allow for dealing with changeable sized input and focus on the most relevant parts of input to make decisions. Graph attention network (GAT) Velickovic et al. (2018) is the first attention-based graph learning architecture, which assign different weights to different neighbor nodes. SNEA is a GAT-based signed network embedding methods which distinguish neighbor nodes into positive and negative neighbors which follow the similar design from Derr et al. (2018). The difference lies in that the contribution of neighbor nodes to the target node is not fixed; instead, by introducing attention mechanism, the model can learn an appropriate weight for each neighbor node.

SiGAT Huang et al. (2019). SiGAT is another attention-based graph neural network applied to signed networks. Different from previously mentioned SNEA, it primarily defines different relationships by establishing various motifs. These motifs are related to triangles in the balance theory and status theory. Then, it defines an attention aggregation mechanism under different relationships, obtaining the learning of node representations in signed networks.

SDGNN Huang et al. (2021b). Building upon the concept of SiGAT, SDGNN further draws inspiration from GAE, treating the task of learning representations for signed graphs as an encoder-decoder framework. In the encoder part, SDGNN simplifies the definition of different relationships, defining only four types of signed directed relationship. Furthermore, it integrates the depiction of balance theory and status theory in signed networks into the decoder parts. SDGNN propose to recontruct the sign, direction, and trianles in loss functions.

SGCL Shu et al. (2021) is the first to employ graph contrastive representation on signed graph. Contrastive learning is an unsupervised learning paradigm which can help model capture invariant and robust representations under perturbations. Compared to the unsigned graph contrastive learning framework, SGCL has three main differences. Firstly, the data augmentation method is different, taking into consideration the existence of positive and negative edges in edge relationships. Therefore, flipping positive and negative edges is used as a means of adding perturbation. Secondly, SGCL adopts the design of encoding positive and negative edges separately. Thirdly, balance theory is employed in the design of the contrastive loss function.

SSSNET (Semi-Supervised Signed NETwork clustering) He et al. (2022b) designed a new GNN-based aggregation mechanism, Signed Mixed-Path Aggregation (SIMPA), to aggregate up-to-$h$-hop contributing neighbors, by assigning weights for different paths. Through statistical analysis of real-world signed graph datasets³³3Six public datasets are used, including Sampson, Rainfall, Fine-YNet, S&P 1500, PPI, Wiki-Rfa., nearly $20\%-50\%$ of triangles violate the social balance theory. Thus a variant of social balance theory is proposed to generate those paths, where a neutral stance is assumed on whether or not the enemy of an enemy is a friend. Specifically, the positive embedding is the weighted combination of the node representations from a “friend path” where all edges need to be positive. For a target node to be an $h$-hop enemy neighbor of the source node, exactly one edge on the “enemy path” has to be negative. Besides, a (differentiable) Probabilistic Balance Normalized Cut (PBNC)⁴⁴4Balance Normalized Cut (BNC) is a non-differentiable function with hard clustering assignment distribution Chiang et al. (2012). as a self-supervised loss is introduced to be optimized for training clustering on signed graphs, which minimizes the probability of negative edges assigned in intra-clusters and maximizes the probability of positive edges assigned in inter-clusters. PBNC with supervised classification loss (i.e., Cross Entropy and Triplet Loss) between the ground truths and the predicted labels is leveraged to optimize node embeddings and clustering simultaneously without any intermediate step.

Trustworthy models typically refer to those representation learning methods which can produce robust, explainable ethical outcomes. Research in this area is very limited, making it a crucial direction for future studies.

ASiNE Lee et al. (2020) is the first attempt that utilizes adversarial learning for signed network. Motivated by generative adversarial networks for unsigned network, ASiNE designed two pairs of generators and discriminators to generate and distinguish false positive edges and false negative edges, respectively. Two generators share an embedding space, similarly, two discriminators share another embedding space. In addition, the negative edge generator can also generate false positive edges based on the balance theory. Generators aim to generate the most indistinguishable edges, while discriminators aim to discriminate between real edges and fake edges, acting as two pairs of opponents in the following four-player minimax game. As the game progresses, the performance of both sides will gradually improve.

RSGNN Zhang et al. (2023b) is the first paper dedicated to the robustness study of the SGNN model, investigating the impact of random noise on SGNN. The paper theoretically analyzes the limitations of the current SGNN, demonstrating that the existing SGNN model fails to learn suitable representations from unbalanced triangles. Furthermore, random noise increases the number of unbalanced triangles, thereby illustrating that the decline in SGNN performance is attributed to the introduction of random noise. Then, RSGNN explore the properties of real-world signed graph to defend the negative effect of noise and propose a novel framework RSGNN which adopts a dual architecture that simultaneously denoises the graph and learns the node representations.

Compared to traditional signed social networks, researchers are increasingly focusing on more complex signed networks such as signed weighted graphs Kumar et al. (2016), signed temporal graphs Sharma et al. (2023), signed hypergraphs Chen et al. (2020) and so on. Within these domains, the fields of signed bipartite graphs modeling object opinions and signed temporal graphs modeling temporal dynamics have seen the emergence of some typical works, such as SBGNN, SBGCL, and SEMBA.

SBGNN Huang et al. (2021a) is a SGNN model designed for signed bipartite graphs. Like most GNNs message-passing scheme, SBGNNs follow a message-passing scheme. However, in SBGNN, new message functions, aggregation functions, and update functions are defined by applying balance theory. More specifically, message neighborhood propagation is divided into four categories. SBGNN captures the higher-order information through a layer-by-layer design.

SBGCL Zhang et al. (2023a) is another model that applies contrastive learning models to signed bipartite graph representation learning. Unlike SGCL, SBGCL focuses on signed bipartite graphs, attempting to address the issue of SGCL’s inability to capture potential relationships among nodes of the same type. SBGCL enhances a signed bipartite graph through an innovative two-level graph augmentation method and a multi-perspective contrastive loss is employed to unify the node presentations learned from the two perspectives.

SEMBA Sharma et al. (2023) is a signed GNN model that combine sign and dynamci in social networks. In order to addressing temporal-awareness, staleness, and sign-awareness problems, SEMBA use memory modules and balanced aggregation to learn short-term memory encoding and a long-term embedding. More specifically, memories contains both positive and negative parts, and aggregation encode positive and negative embeddings following balance theory.

With the rise of social media, social conflicts have intensified, manifesting in an increase in negative links between individuals. In this section, we provide an overview of some of the most attention-grabbing applications currently.

Social Polarization Using signed graphs to study adverse effects is a promising research topic. These adverse effects, such as polarization and echo chambers, can be harmful to the process of democratic deliberation in our societyXiao et al. (2020); Bonchi et al. (2019). For example, POLE Huang et al. (2022) is a signed networking embedding methods, adopting a measure of polarization based on the signed random-walks. POLE first design a polarization measure for signed graphs and use matrix factorization optimized polarized similarity consistency.

Stance Detection Stance detection typically categorizes stances into three types: “support,” “oppose,” and “neutral,” where in this context, “support” can be viewed as a positive relationship and “oppose” as a negative relationship⁵⁵5Neutral could be modeled as either a positive relationship or unknown.. While a substantial amount of work on stance detection is based on Natural Language Processing (NLP). However, an increasing number of studies have found that social networks significantly influence people’s opinions on specific matters Pougué-Biyong et al. (2023). SEM Pougué-Biyong et al. (2023) jointly learns user and topic embeddings in signed social graphs with distinct edge types for each topic.

Recommendation System with Negative Feedback With the success of graph neural network models in the field of recommendation systems, these systems can be viewed as user-item interaction bipartite graphs. A substantial number of researchers have employed graph representation learning to model these bipartite graphs, as seen in works like PinSAGE Ying et al. (2018) and LightGCN He et al. (2020). However, in the context of recommendation systems, the negative feedback mechanism Xie et al. (2020) also refers to users expressing dissatisfaction with recommended products, manifested through actions like poor reviews, skipping recommended content, or reporting. The optimization of recommendation systems using negative feedback has garnered attention from researchers Tang et al. (2016a). Notably, Seo et al. (2022) introduced the SiReN model, which employs a signed graph neural network approach to model recommendation systems incorporating both positive and negative feedback. By conducting qualitative and quantitative experiments on the mechanism of negative feedback, Huang et al. (2023) found that negative feedback interactions (i.e., negative edges) could enhance the performance of recommendation systems (specifically, the prediction of positive edges) to a certain extent. They proposed a new Signed GNN model named SiGRec with a new SiC loss function to model signed graphs in recommendation systems.

Social Computing In addition to the applications mentioned above, due to the relevance of its links to human sentiment, SGRL has also been applied in various social computing fields. These include education Ni et al. (2023), communication He et al. (2022a), cryptocurrency, politics, and more. This broad applicability underscores the significance of understanding and leveraging the dynamics of signed networks in diverse social scenarios.

With the rise of graph representation learning, an increasing number of tools for modeling graph representations have been introduced. Among the most representative of these are Pytorch Geometric (PyG) and Deep Graph Library (DGL). However, these approaches often view signed graph merely as a type of relation, overlooking the social attributes and real-world contexts of signed networks. PyTorch Geometric Signed Directed (PyGSD) He et al. (2023) takes data classes, data loaders, as and data splitters into consideration, and design a specific tool for SGRL.