Introduction to Graphs: Nodes, Edges, and Direction

What is a Graph?

At its core, a graph is a mathematical structure used to model relationships between objects. In the world of data science and machine learning, this is an incredibly powerful concept. You can think of:

• Social networks, where people are the objects and their friendships are the relationships.
• Molecular structures, where atoms are the objects and chemical bonds are the relationships.
• The internet, where web pages are the objects and hyperlinks are the relationships.

In graph theory, we have formal names for these components. The objects are called vertices (or more commonly, nodes), and the relationships are called edges.

To get a dynamic and visual introduction to these ideas, the following video provides a clear and concise overview.

As the video explained, a graph $G$ is formally defined as an ordered pair $G=(V,E)$, where $V$ is the set of all vertices and $E$ is the set of all edges. Each edge in $E$ represents a connection between a pair of vertices from $V$. This simple notation, $G=(V,E)$, is the bedrock of graph theory and will appear constantly as we discuss GNNs.

For a different perspective that frames these concepts within a machine learning context, you can watch this short segment.

Directed vs. Undirected Graphs

The nature of the relationships in a network is not always the same. This leads to a fundamental classification of graphs: directed and undirected. The distinction is simple but has profound implications for how information propagates through a network—a core mechanism in GNNs.

An undirected graph models symmetric, or two-way, relationships. If an edge connects node A to node B, it is implied that the connection also goes from B to A. A classic example is a friendship on Facebook; the relationship is mutual.

A directed graph, or digraph, models asymmetric, or one-way, relationships. An edge from node A to node B does not imply an edge from B to A. Think of following someone on Twitter; you can follow them without them following you back.

The following images clearly illustrate this difference.

To solidify your understanding, the next video segments provide clear explanations and helpful analogies.

The school hierarchy example mentioned in the next video is a particularly intuitive way to understand directedness.

Formalizing the Difference

This distinction between directed and undirected graphs is also reflected in the formal notation for edges.

• In an undirected graph, an edge between vertices $u$ and $v$ is an unordered pair, typically written as a set $\{u,v\}$. The order does not matter: $\{u,v\}$ is identical to $\{v,u\}$.
• In a directed graph, an edge from vertex $u$ to vertex $v$ is an ordered pair, written as $(u,v)$. Here, the order is critical: $(u,v)$ is not the same as $(v,u)$. $(u,v)$ represents an arrow pointing from $u$ to $v$.

The following image provides a perfect summary, showing how the set of edges $E$ is written differently for undirected and directed graphs.

For a comprehensive textual reference that summarizes everything we've covered, the following article is an excellent resource.

Conclusion

In this introductory lesson, we have established the foundational vocabulary of graph theory. You can now define the core components of a graph and distinguish between its two primary forms.

Here are the key takeaways:

• A graph $G=(V,E)$ is a structure used to model relationships, consisting of a set of vertices ($V$, or nodes) and a set of edges ($E$, or links).
• Vertices represent the entities or objects in a network.
• Edges represent the connections or relationships between pairs of vertices.
• Undirected graphs model symmetric, bidirectional relationships, where an edge $\{u,v\}$ connects $u$ and $v$ mutually.
• Directed graphs (digraphs) model asymmetric, one-way relationships, where an edge $(u,v)$ represents a connection from $u$ to $v$.

This foundation is non-negotiable for understanding GNNs. The structure of a graph—particularly its directionality—dictates how information can be passed between nodes, which is the central mechanism of graph neural networks.

In our next lesson, we will build directly on this by exploring how to represent these abstract graph structures in a concrete way that a computer can process. We will dive into two essential data structures: adjacency matrices and adjacency lists.