Directed, Undirected, Weighted, and Heterogeneous Graphs
Published:
Undirected Graphs
In an undirected graph, edges have no direction — \((u,v) \in E\) implies \((v,u) \in E\). The adjacency matrix is symmetric: \(A = A^{\top}\).
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 are ordered pairs. An edge \((u,v) \in E\) points from \(u\) to \(v\) and does not imply \((v,u) \in E\), so the adjacency matrix is generally asymmetric: \(A \neq A^{\top}\), with \(A_{uv} = 1\) recording the edge \(u \to v\).
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 carries a scalar weight \(w_{uv} \in \mathbb{R}\), and the adjacency matrix stores that weight rather than a 0/1 indicator: \(A_{uv} = w_{uv}\) when \((u,v) \in E\), and \(0\) otherwise.
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 partitions the node set into two disjoint parts, \(V = U \sqcup W\), with every edge joining a node in \(U\) to a node in \(W\) — never two nodes within the same part. Equivalently, a graph is bipartite exactly when it contains no odd-length cycle.
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.
Multigraphs
A multigraph allows more than one edge between the same ordered pair of nodes (parallel edges), and often self-loops \((v,v)\) as well. The edge set is therefore a multiset rather than a subset of \(V \times V\), and a single 0/1 adjacency matrix can no longer represent the graph — you either store integer edge counts in \(A\) or keep an explicit edge list.
Real examples: flight networks (several distinct flights between the same two airports), transaction networks (repeated payments between the same two accounts), road networks with parallel carriageways.
GNN implication: parallel edges each send their own message, so a node can receive several distinct messages from the same neighbour. Frameworks that index messages by edge (rather than by neighbour) handle this without modification.
Careful: a multigraph is about how many edges may join a pair of nodes; a multi-relational graph, next, is about what type those edges are. The two are independent, and a graph can be both.
Multi-relational Graphs
A multi-relational graph attaches a type \(r \in \mathcal{R}\) to every edge, so edges are triples \((u, r, v)\). The same pair of nodes may be connected by edges of several different types, and there is one adjacency matrix \(A_r\) per relation.
Real examples: knowledge graphs such as Freebase and Wikidata, where entity pairs are connected by typed relations (born_in, works_at, married_to); social networks with typed interactions (friend, colleague, family). TransE and DistMult are embedding models for such graphs, not graph types themselves.
GNN implication: R-GCN and similar architectures learn a separate weight matrix per relation type, aggregating typed messages separately before combining them.
Heterogeneous Graphs
A heterogeneous graph comes with a type map on both nodes and edges: \(\tau : V \to \mathcal{T}_V\) and \(\phi : E \to \mathcal{T}_E\), where \(\lvert \mathcal{T}_V \rvert > 1\). A multi-relational graph is the special case with many edge types but a single node type; a heterogeneous graph relaxes the node side too.
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.
Hypergraphs
A hypergraph \(H = (V, \mathcal{E})\) generalises graphs by letting each hyperedge be an arbitrary subset of nodes, \(e \subseteq V\), rather than a pair. An ordinary graph is the special case where every hyperedge has \(\lvert e \rvert = 2\). Structure is stored as an incidence matrix \(B \in \{0,1\}^{N \times \lvert \mathcal{E} \rvert}\) with \(B_{ve} = 1\) when \(v \in e\).
Real examples: group memberships (a paper with five authors is one hyperedge over all five), co-purchase baskets, multi-agent interactions.
GNN implication: hypergraph neural networks typically expand each hyperedge into a bipartite node–hyperedge incidence structure and propagate node → hyperedge → node, so a message reaches all co-members of a group in one round rather than only pairwise partners.
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 type | Key property | Example | GNN challenge |
|---|---|---|---|
| Undirected | \(A = A^{\top}\) | Molecules, friendships | Symmetric aggregation |
| Directed | \(A \neq A^{\top}\) | Citations, follows | Direction-aware aggregation |
| Weighted | \(A_{uv} = w_{uv}\) | Roads, correlations | Weight-modulated messages |
| Bipartite | \(V = U \sqcup W\), edges only across | User-item, author-paper | Alternating propagation |
| Multigraph | Parallel edges, self-loops allowed | Flights, transactions | Per-edge (not per-neighbour) messages |
| Multi-relational | Typed edges \((u, r, v)\) | Knowledge graphs | Type-specific weights |
| Heterogeneous | Multiple node and edge types | Academic networks | Type-aware architectures |
| Hypergraph | Hyperedge is any subset of \(V\) | Group memberships | Hyperedge aggregation |
| Dynamic | Graph changes over time | Communication networks | Temporal modelling |
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
- Bronstein, M. M., Bruna, J., Cohen, T., & Veličković, P. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv preprint.
- Hamilton, W. L. (2020). Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning.