What is a signed graph?

A signed graph is a graph where each edge carries a positive (+1) or negative (-1) sign. Positive edges represent trust, agreement, or friendship. Negative edges represent distrust, disagreement, or enmity. Examples include review networks (like/dislike), social networks (friend/foe), and political networks (ally/opponent).

What is balance theory in signed graphs?

Balance theory states that signed triangles tend toward balance: 'the friend of my friend is my friend' (+++), 'the enemy of my enemy is my friend' (+--). Unbalanced triangles like 'the friend of my friend is my enemy' (++-) are unstable and tend to resolve. Signed GNNs leverage this structural property.

How do signed GNNs differ from standard GNNs?

Signed GNNs maintain separate representations for positive and negative neighborhoods. During message passing, a node aggregates messages from positive neighbors and negative neighbors separately, then combines them. This captures the different semantics: positive neighbors should pull embeddings closer, negative neighbors should push them apart.

What is the sign prediction task?

Sign prediction (also called link sign prediction) predicts whether a new edge will be positive or negative. Given two nodes connected by an unsigned edge, the model predicts the sign. This is useful for predicting whether a review will be positive or negative, or whether two users will agree or disagree.

How do I represent a signed graph in PyG?

Store the sign as an edge attribute. Use edge_attr with +1 for positive edges and -1 for negative edges. Alternatively, split into two edge types in HeteroData: ('user', 'trusts', 'user') and ('user', 'distrusts', 'user'). The SignedGCN model in PyG handles signed graphs natively.

Signed Graphs in GNNs: Positive and Negative Edges | Kumo.ai

A signed graph is a graph where edges carry a positive or negative sign. Positive edges (+1) represent trust, agreement, friendship, or approval. Negative edges (-1) represent distrust, disagreement, enmity, or disapproval. When a user upvotes a post, that is a positive edge. When they downvote it, that is a negative edge. Standard unsigned graphs treat all connections equally and cannot distinguish these semantics.

Signed graphs appear in review platforms (like/dislike), social networks (friend/block), political systems (ally/opponent), and trust networks (trust/ distrust). The sign of the edge fundamentally changes how information should propagate: you should agree with your friends' friends but disagree with your enemies' friends.

Balance theory

The structural foundation of signed graph analysis is balance theory, which predicts the stability of signed triangles:

Balanced (stable): +++ (all friends), +-- (enemy of my enemy is my friend)
Unbalanced (unstable): ++- (friend of my friend is my enemy), --- (all enemies)

Balanced triads are far more common in real social networks than chance would predict. Signed GNNs leverage this structural regularity to make predictions about unknown edge signs.

Signed message passing

Standard message passing aggregates all neighbors equally. Signed GNNs split aggregation into positive and negative channels:

signed_message_passing.py

import torch
from torch_geometric.nn import SignedGCN

# SignedGCN: built-in signed graph model in PyG
model = SignedGCN(
    in_channels=64,
    hidden_channels=32,
    num_layers=2,
)

# Separate positive and negative edges
pos_edge_index = edge_index[:, edge_sign == 1]
neg_edge_index = edge_index[:, edge_sign == -1]

# Train with signed graph loss
z = model(x, pos_edge_index, neg_edge_index)

# SignedGCN internally:
# 1. Aggregates positive neighbors -> h_pos
# 2. Aggregates negative neighbors -> h_neg
# 3. Combines: h_new = transform(h_self, h_pos, h_neg)
# Positive neighbors pull embeddings together
# Negative neighbors push embeddings apart

SignedGCN processes positive and negative neighborhoods separately, learning different aggregation patterns for each.

Enterprise example: trust-aware recommendations

A marketplace platform where buyers rate sellers. Ratings above 3 stars create positive edges; ratings of 1-2 stars create negative edges. The signed graph reveals trust patterns:

Sellers trusted by your trusted sellers are likely trustworthy (+ + = +)
Sellers distrusted by your distrusted sellers might be trustworthy (- - = +)
Sellers trusted by your distrusted sellers are suspect (- + = -)

A signed GNN propagates these trust signals through the network. After 2 layers, each seller's embedding reflects not just their direct ratings but the trust reputation of their raters. Sellers rated highly by other highly-trusted sellers get boosted. Sellers rated highly only by low-trust accounts get penalized.

Sign prediction

The primary task on signed graphs is sign prediction: given two connected nodes, will their edge be positive or negative? This maps to real-world questions:

Will this user like or dislike this product?
Will these two politicians ally or oppose each other?
Will this reviewer give a positive or negative rating?

Signed GNNs predict signs by learning embeddings where positively connected nodes are close in embedding space and negatively connected nodes are far apart. The sign of a new edge is predicted based on the distance between the endpoint embeddings.

Key Takeaways

1A signed graph assigns +1 or -1 to each edge, representing trust/distrust, like/dislike, or friend/foe. This is richer than unsigned graphs that treat all connections identically.
2Signed GNNs process positive and negative neighborhoods separately. Positive neighbors attract embeddings; negative neighbors repel them. This respects the semantic difference between edge types.
3Balance theory (friend of friend = friend, enemy of enemy = friend) provides structural priors that signed GNNs learn and exploit for prediction.
4Enterprise uses include trust-aware recommendations, review sentiment propagation, adversarial network detection, and political alliance prediction.
5In PyG, use SignedGCN with separate positive and negative edge indices. The model handles dual-channel aggregation and signed loss computation internally.

Signed Graphs: Positive and Negative Edges