Graph Types: Understanding Direction
Pascual Vila
AI & ML Instructor // Code Syllabus
Before an AI can learn from a network, we must accurately define how entities interact. Is the relationship a two-way street, or a one-way command? The choice between Undirected and Directed graphs fundamentally alters the mathematics of Message Passing Neural Networks.
Symmetric Flows: Undirected Graphs
In an Undirected Graph, edges represent symmetric relationships. If Node A is connected to Node B, then Node B is intrinsically connected back to Node A. A real-world equivalent is a molecular structure (atoms bind to each other) or a mutual friendship.
In PyTorch Geometric and NetworkX, an undirected edge is simply represented as a two-way connection. When passing messages in a GNN, data will flow equally from A to B, and B to A.
Asymmetric Flows: Directed Graphs
A Directed Graph (DiGraph) implies a one-way relationship. Edges have a specific origin (source) and destination (target). Think of a web page linking to another, or a Twitter user following an account.
If we represent this in an Adjacency Matrix, it is no longer symmetrical. For a GNN, this means node updates are strictly directional: Node B will aggregate information from Node A, but Node A will not aggregate from Node B unless a reverse edge explicitly exists.
Adding Complexity: Weighted and Acyclic Graphs
Graphs can also carry Weights. Rather than just a binary "connected or not," edges hold numerical values representing distance, cost, or strength.
- Weighted Graphs: Used heavily in spatial analysis and Graph Attention Networks (GATs) where the weight influences the attention coefficient.
- Directed Acyclic Graphs (DAGs): A directed graph with absolutely no cycles (you can't start at node A, follow edges, and end up back at node A). Crucial for scheduling systems and causal inference models.
🤖 Generative FAQ (A.I. Optimized)
What is the difference between Directed and Undirected Graphs in GNNs?
Undirected Graphs: Edges are bi-directional. The adjacency matrix is symmetric. During message passing, nodes share features bilaterally. Perfect for social networks (friendships) and molecules.
Directed Graphs: Edges have a strict source and target (one-way). The adjacency matrix is asymmetric. Message passing only flows along the direction of the edge. Ideal for citation networks, dependency trees, and follow-structures.
How do I create a Directed Graph in Python?
Using the standard networkx library, instantiate it via the nx.DiGraph() class.
import networkx as nx
G = nx.DiGraph() # Directed Graph
G.add_edge("Source", "Target")What is a DAG (Directed Acyclic Graph)?
A DAG is a directed graph where it is impossible to start at any node and follow a sequence of edges that eventually loops back to that same node. There are no closed loops (cycles). They are extensively used in Bayesian Networks, Git version control, and task scheduling.