Source-linked AI summary
SDGNN: Learning Node Representation for Signed Directed Networks
Junjie Huang, Huawei Shen, Liang Hou, Xueqi Cheng
TL;DR
Most GNNs are designed for unsigned networks, leaving signed directed networks less studied and difficult to model. The paper introduces SDGNN, which uses sociological theories and reconstructs signs, directions, and triangles. Across five real-world signed networks, the authors report that SDGNN performs better than state-of-the-art baselines.
Problem
Most GNNs are designed for unsigned networks, while signed directed networks pose challenges in modeling negative links and direction.
Source: Introduction · p. 1Method
SDGNN uses layer-by-layer aggregation over signed directed relations and trains by reconstructing link signs, directions, and triangles.
Source: Introduction · p. 2Results
On five real-world signed networks, SDGNN performs better than other state-of-the-art baselines.
Source: Conclusion · p. 7Takeaways & Limitations
The authors conclude that sociologically guided SDGNN is effective for learning representations of signed networks.
Source: Conclusion · p. 7
Abstract
from arXiv · showhide
Network embedding is aimed at mapping nodes in a network into low-dimensional vector representations. Graph Neural Networks (GNNs) have received widespread attention and lead to state-of-the-art performance in learning node representations. However, most GNNs only work in unsigned networks, where only positive links exist. It is not trivial to transfer these models to signed directed networks, which are widely observed in the real world yet less studied. In this paper, we first review two fundamental sociological theories (i.e., status theory and balance theory) and conduct empirical studies on real-world datasets to analyze the social mechanism in signed directed networks. Guided by related sociological theories, we propose a novel Signed Directed Graph Neural Networks model named SDGNN to learn node embeddings for signed directed networks. The proposed model simultaneously reconstructs link signs, link directions, and signed directed triangles. We validate our model's effectiveness on five real-world datasets, which are commonly used as the benchmark for signed network embedding. Experiments demonstrate the proposed model outperforms existing models, including feature-based methods, network embedding methods, and several GNN methods.
Introduction
The introduction motivates learning representations for signed directed networks because existing GNN approaches do not account for direction. SDGNN combines sociological theory with relation-specific aggregation and training objectives that reconstruct signs, directions, and triangles.
Introduction
- Online interactions include positive relations and negative links representing hostility, distrust, hate, disagreement, or disapproval.The paper connects these interactions to social psychology theories of signed networks.Source: Introduction · p. 1
- GNNs aggregate neighborhood information for node embeddings, but Graph Auto-Encoder is designed for unsigned networks and cannot be applied directly to signed networks.Source: Introduction · p. 1
- Signed-network GNNs discussed here model balance but omit direction, an important feature of signed directed graphs.The paper identifies this gap as motivation for SDGNN.Source: Introduction · p. 1
- SDGNN aggregates and propagates node information across four signed directed relations, then reconstructs signs, directions, and triangles.Its loss functions are guided by sociological theories.Source: Introduction · p. 2
- The paper empirically analyzes balance and status theories on five real-world datasets and evaluates SDGNN on link sign prediction across five signed social networks.Link sign prediction is described as the main downstream task for evaluating signed-network embeddings.Source: Introduction · pp. 1–2
Related Work
Prior signed-network embedding methods use sociological theories with machine-learning techniques, while GNNs learn representations through neighborhood aggregation. The reviewed GNN approaches leave challenges in modeling signed directed networks, including direction, signs, and computationally costly motifs.
Signed Network Embedding
- Signed-network embedding methods use sociological theories in their objectives and optimize lookup embeddings with techniques such as sampling and random walks.Examples include methods for directed signed networks that draw on balance theory or balance and status theory.Source: Signed Network Embedding · p. 2
Graph Neural Networks
- GNNs encode nodes as low-dimensional vectors and decode graph structure, using deep-learning methods that differ from matrix factorization and random walks.Source: Graph Neural Networks · p. 2
- Most GNNs target unsigned networks; SGCN handles undirected signed graphs, while SiGAT models directed signed graphs using 38 motifs and predicts signs alone.The passage notes that SiGAT's motif set is expensive for large graphs and its objectives ignore directions and triangles.Source: Graph Neural Networks · p. 2
Problem Definition
The paper represents a signed directed network as a graph with nodes and signed, directed edges. Its objective is to map each node to a low-dimensional vector representation.
Problem Definition
- A signed directed network is G = (V, E, s), where V is the node set and E contains directed positive and negative links.The edge sets E+ and E− are disjoint.Source: Problem Definition · p. 2
- The adjacency matrix uses 1 for a positive link from ui to uj, −1 for a negative link, and 0 when no link exists.Source: Problem Definition · p. 2
- The representation objective maps each node u to a low-dimensional vector zu in Rd using a learned transformation function.The representation matrix Z contains d-dimensional vectors for the network's |V| nodes.Source: Problem Definition · p. 2
Sociological Theory
The section introduces balance and status theories as frameworks for signed directed networks and examines their consistency across five real-world datasets. Its reported findings suggest that the theories often agree and may complement one another in representation learning.
Sociological Theory
- The section introduces balance and status theories and compares them across five real-world datasets.Source: Sociological Theory · p. 3
Balance Theory
- Balance theory treats triads with an even number of negative edges as balanced and predicts balanced triads will be more prevalent.Its examples include triads with three positive signs or one positive sign.Source: Balance Theory · p. 3
Status Theory
- Status theory interprets positive directed links as assigning higher status to the recipient and negative links as assigning lower status.The theory also imposes a transitive status order across triads.Source: Status Theory · p. 3
Comparison of Balance Theory and Status Theory
- Balance theory focuses on undirected signed relations, whereas status theory uses directed relations; their predictions can sometimes agree.Source: Comparison of Balance Theory and… · p. 3
- About 70% of triads are consistent with both theories, while only a tiny fraction satisfies neither; the authors suggest their complementarity may aid representation learning.The paper characterizes the neither-consistent triads as possible noise.Source: Comparison of Balance Theory and… · p. 3, Table 1 · p. 3
Proposed Method
SDGNN adapts GNN aggregation to signed directed networks by separating four relation types, then trains embeddings to reconstruct signs, directions, and triangles.
Signed Directed GNNs
- Four signed directed relations define distinct neighborhoods, whose information is aggregated and encoded by mean or attention aggregators and an MLP.The model uses layer-by-layer aggregation to cover direction and triangle topology across multiple layers.Source: Signed Directed GNNs · pp. 3–4, Figure 2 · p. 4
Loss Function
- Sign prediction uses edge binary cross-entropy, while direction loss fits status-score differences to edge-derived targets, with status scores mapped from embeddings by a sigmoid.The status relationship threshold is γ = 0.5 in this paper.Source: Loss Function · p. 4
- Triangle loss scores theory-based triangles from edge-sign probabilities and applies edge binary cross-entropy weighted by triangle-edge counts; total loss adds sign and direction terms.The triangle set is based on balance and status theories.Source: Loss Function · p. 4
Experiments
Experiments evaluate SDGNN on five signed social networks for link-sign prediction and report stronger benchmark performance than prior baselines, followed by parameter and component analyses.
Experimental Settings
- Across five datasets, methods use 80/20 edge splits repeated five times, with 20-dimensional embeddings except FeExtra and logistic-regression edge classifiers.Source: Baselines · p. 5, Datasets · p. 5
Experiment Results
- SDGNN outperforms all baseline methods on most reported metrics for link-sign prediction across five datasets.Table 3 reports Micro-F1, Binary-F1, Macro-F1, and AUC.Source: Table 3 · p. 6, Experiment Results · p. 6
- Unsigned embeddings improve over random embeddings, with Node2vec strongest among them, indicating that structural information matters.Source: Experiment Results · p. 6
- Signed embedding methods significantly exceed unsigned methods; SIGNet trails BESIDE without status theory, while SiGAT beats direction-omitting SGCN.The authors attribute signed-method results to modeling sociological theories.Source: Experiment Results · p. 6
Parameter Analysis and Ablation Study
- Table 4 reports that attention outperforms mean aggregation, while additional layers capture higher-order information.Source: Table 4 · p. 7, Ablation Study · p. 7
- Sign-only reconstruction performs poorly; adding direction and triangle objectives improves results.The authors conclude that both directions and triangles should be included in the training objectives.Source: Table 5 · p. 7, Ablation Study · p. 7
- On Bitcoin-Alpha, SDGNN converges quickly and stays stable; performance rises then falls with dimension, while d=5 approaches BESIDE.The authors suggest excessive parameters may make embedding training difficult.Source: Parameter Analysis and Ablation Study · p. 6, Parameter Analysis · p. 7
Conclusion
The paper introduces SDGNN for signed directed network representations, guided by balance and status theories, and reports better performance than state-of-the-art baselines on five real-world signed networks.
Conclusion
- SDGNN combines sociological theory-guided message aggregation with losses that reconstruct signs, directions, and triangles.Its multi-layer design can capture higher-order structure.Source: Conclusion · p. 7
- Across five real-world signed networks, SDGNN performs better than other state-of-the-art baselines.Source: Conclusion · p. 7
- The paper analyzes hyperparameters and ablates its aggregator and loss-function designs.Source: Conclusion · p. 7
- Future work will generalize the method to heterogeneous networks to incorporate more complex semantic information.Source: Conclusion · p. 7
Comparison of Different Model Architectures
The comparison is framed around how the proposed layer-by-layer signed-relation GNN differs from selected methods across aggregation, depth, and reconstruction objectives.
Comparison of Different Model Architectures
- The proposed model is a layer-by-layer signed-relation GNN with social-theory-guided loss functions.Source: Comparison of Different Model… · p. 9
- The comparison identifies aggregator choice and layer-by-layer processing as architectural dimensions.Source: Comparison of Different Model… · p. 9
- The listed loss dimensions are sign, direction, and triangle reconstruction.Source: Comparison of Different Model… · p. 9
Algorithm Detail
Algorithm 1 takes a signed directed graph and returns node representations by iteratively aggregating neighborhood information through the configured GNN layers.
Algorithm Detail
- The algorithm takes a signed directed graph, encoder aggregators, GNN layer count, and epoch count, and returns node representations.Source: Algorithm Detail · p. 9
- It initializes node embeddings and neural-network parameters, then iterates over epochs, mini-batch node sets, neighborhoods, and layers.Source: Algorithm Detail · p. 9
- The algorithm returns the encoded node representations after backpropagation updates the parameters.Source: Algorithm Detail · p. 9
- With L = 2, the model captures triangle structure, while the number of computed neighbors increases exponentially with depth.The paper notes this neighbor growth is consistent with GraphSAGE.Source: Algorithm Detail · p. 9
Experiment Detail
The section specifies dataset preprocessing, gives a complexity expression for SDGNN, and reports that nonzero direction and triangle loss weights perform better.
Experiment Detail
- For duplicate links in wikirfa, preprocessing keeps the last edge-list record and converts string node IDs to numeric IDs across embedding methods.Source: Experiment Detail · p. 9
Complexity Analysis
- With learnable ID embeddings and L-layer aggregators, the stated total SDGNN complexity is O(|V|*d+10*d*d), with an additional O(2*d) for attention.The initial embeddings contribute O(|V|*d); the passage gives O(5*d*d) for W and O(2*5*d*d) for the two-layer MLP.Source: Complexity Analysis · p. 9
Various Values of λ1 and λ2
- Nonzero λ1 and λ2 values show better performance, and the sign-reconstruction weight is not set to zero.The cited table reports various values of λ1 and λ2; its caption identifies the table but supplies no cell values.Source: Various Values of λ1 and λ2 · p. 9, Table 7 · p. 9