Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Directed, Undirected, Weighted, and Heterogeneous Graphs

4 minute read

Published:

TL;DR: Undirected graphs have symmetric relationships; directed graphs have asymmetric ones (A ≠ Aᵀ). Weighted graphs encode relationship strength. Heterogeneous graphs have multiple node/edge types. Each variant arises naturally in real data and requires adapted GNN designs.

Undirected Graphs

In an undirected graph, edges have no direction — (u,v) ∈ E implies (v,u) ∈ E. The adjacency matrix is symmetric: A = Aᵀ.

Real examples: molecular bonds (a bond between C and O is mutual), social friendships (Facebook), co-authorship networks.

GNN implication: each node aggregates from its neighbours symmetrically. The message from u to v is the same as from v to u.

Directed Graphs

In a directed graph (digraph), edges have a direction. Edge (u→v) ∈ E does not imply (v→u). The adjacency matrix is generally asymmetric: A ≠ Aᵀ.

Real examples: citation networks (A cites B, but B doesn’t cite A), Twitter follows, web links, dependency graphs.

GNN implication: a node can receive messages from in-neighbours (who point to it) and send messages to out-neighbours (who it points to). Many GNNs handle this by treating in-edges and out-edges separately, or by symmetrising A at the cost of losing directionality.

Weighted Graphs

In a weighted graph, each edge has a scalar (or vector) weight w_{uv} ∈ ℝ. The adjacency matrix becomes A[u,v] = w_{uv}.

Real examples: road networks (road distance), correlation networks (feature correlation), similarity graphs (cosine similarity between embeddings).

GNN implication: edge weights naturally modulate message strength. Messages from strongly-connected neighbours contribute more than messages from weakly-connected ones.

Bipartite Graphs

A bipartite graph has two disjoint node sets U and V, with edges only between U and V (never within U or within V).

Real examples: user-item graphs (recommendation), author-paper graphs (authorship), drug-protein interaction graphs.

GNN implication: message passing alternates between the two node sets. Specialised bipartite GNNs propagate information from items to users and back.

Multiplex and Multi-relational Graphs

A multi-relational graph has multiple edge types — the same pair of nodes can be connected by edges of different types.

Real examples: knowledge graphs (TransE, DistMult) where entity pairs are connected by typed relations (was_born_in, works_at, married_to); social networks with typed interactions (friend, colleague, family).

GNN implication: R-GCN and similar architectures learn separate weight matrices per relation type, aggregating typed messages separately before combining.

Heterogeneous Graphs

A heterogeneous graph has multiple node types and multiple edge types:

Node types: {Paper, Author, Venue}
Edge types: {Author→Paper: wrote, Paper→Venue: published_at, Paper→Paper: cites}

Real examples: academic networks (DBLP, OAG), biomedical knowledge graphs (drug→protein→disease), e-commerce graphs (user→item→category).

GNN implication: nodes of different types have different feature spaces and semantics. You cannot apply the same weight matrix to messages from a Paper and a Venue. Heterogeneous GNNs (HAN, HGT, RGCN) maintain type-specific transformations.

Homogeneous vs Heterogeneous: Most classical GNN papers (GCN, GAT, GIN, GraphSAGE) assume homogeneous graphs — one node type, one edge type. Real-world graphs are almost never homogeneous. Understanding the type structure of your data is the first step in choosing an appropriate GNN.

Hypergraphs

A hypergraph generalises graphs: hyperedges can connect any number of nodes (not just pairs).

Real examples: group memberships (a paper can have 5 authors — one hyperedge connecting all 5), co-purchase events, multi-agent interactions.

GNN implication: hypergraph neural networks convert hyperedges to bipartite graphs (node–hyperedge–node) and propagate through both.

Dynamic Graphs

A dynamic graph evolves over time: nodes and edges appear and disappear.

Real examples: communication networks (who emails whom at time t), social networks (friendships change), financial transaction networks.

GNN implication: snapshot-based models process sequences of graph snapshots; event-based models (Temporal Graph Networks) process continuous-time events.

Summary

Graph typeKey propertyExampleGNN challenge
UndirectedA = AᵀMolecules, friendshipsSymmetric aggregation
DirectedA ≠ AᵀCitations, followsDirection-aware aggregation
WeightedA[u,v] = wRoads, correlationsWeight-modulated messages
BipartiteTwo node setsUser-item, author-paperAlternating propagation
Multi-relationalMultiple edge typesKnowledge graphsType-specific weights
HeterogeneousMultiple node+edge typesAcademic networksType-aware architectures
HypergraphEdges connect >2 nodesGroup membershipsHyperedge aggregation
DynamicGraph changes over timeCommunication networksTemporal modeling

Recognising which graph type your data is determines which GNN variant to use. Starting with a homogeneous GNN on a heterogeneous graph is a common and costly mistake.

References

You May Also Enjoy

Open Problems and Future Directions in Sheaf Neural Networks

5 minute read

Published:

Sheaf Neural Networks are a young field with many open research problems. This post surveys the most important unsolved questions: scalability to million-node graphs, stochastic sheaves for uncertainty quantification, sheaf autoencoders for generative models, connections to persistent homology, and unification with other topological deep learning frameworks.

Sheaf GNNs for Molecular Property Prediction

7 minute read

Published:

Molecular graphs are naturally heterophilic — atoms of different types bonded together — and have rich geometric structure (bond angles, torsion angles). Sheaf GNNs can encode this structure via restriction maps that represent the relational geometry between bonded atoms. This post explores how sheaf theory applies to molecular property prediction.

Sheaf GNNs for Heterophilic Node Classification: Benchmarks and Results

6 minute read

Published:

A systematic comparison of sheaf GNNs against baselines on standard heterophilic node classification benchmarks. Which datasets benefit most from sheaf structure? How does stalk dimension d affect performance? When do sheaves win — and when don’t they?

Sheaves Meet Attention: Transformer-Inspired Sheaf Models

6 minute read

Published:

Graph Transformers use global attention to capture long-range dependencies that local message passing misses. Sheaf Transformers combine sheaf-based local aggregation (with learnable relational geometry) with global attention (for long-range dependencies). This post surveys the design space of sheaf-augmented attention models.