Introduction to Graphs and Graph-Structured Data

Introduction to Graphs and Graph-Structured Data

The study of complex systems pervades nearly every scientific discipline and industry application, from understanding the intricate web of social interactions that shape human behavior to modeling the molecular mechanisms that govern life itself. At the heart of this complexity lies a fundamental challenge: how do we represent and analyze systems where relationships between entities are as important as the entities themselves? This question leads us to one of the most versatile and powerful abstractions in computer science and mathematics—the graph.

A graph is a mathematical structure consisting of a set of vertices (also called nodes) and a set of edges (also called links or connections) that capture relationships between these vertices. While this definition may seem deceptively simple, the expressive power of graphs is remarkable. By representing entities as nodes and their interactions as edges, we can model an extraordinarily diverse range of real-world phenomena. The World Wide Web becomes a massive directed graph where web pages link to one another. Social networks transform into intricate webs of friendships, followers, and professional connections. Molecular structures reveal themselves as graphs where atoms are nodes and chemical bonds are edges. Even the human brain, with its billions of neurons and trillions of synaptic connections, can be abstractly represented as a graph of profound complexity.

The ubiquity of graph-structured data is not merely a coincidence of abstraction—it reflects an underlying truth about the nature of complex systems. In many domains, the most meaningful information resides not in isolated data points but in the patterns of connections that link them. A person's importance in a social network, for instance, cannot be determined by examining their profile alone; it emerges from their position within the broader network of relationships. Similarly, the toxicity of a molecule cannot be predicted from its individual atoms; it depends critically on how those atoms are bonded together into a specific structure. This insight—that relational structure carries essential information—forms the philosophical foundation for the entire field of graph representation learning, and particularly for the Graph Neural Networks that are the subject of this book.

Fundamental Concepts and Formal Definitions

Before proceeding further, it is essential to establish the formal mathematical foundation that will underpin our discussions throughout this book. This section provides precise definitions of key graph-theoretic concepts, ensuring that we share a common vocabulary for the more advanced topics that follow.

Basic Graph Structure

A graph $G$ is formally defined as an ordered pair $G = (V, E)$, where $V$ is a finite set of vertices (or nodes) and $E \subseteq \{\{u, v\} : u, v \in V, u \neq v\}$ is a set of edges (or links) connecting pairs of vertices. This definition corresponds to what is called a simple graph, which imposes two important restrictions: there are no self-loops (edges connecting a vertex to itself) and there is at most one edge between any pair of vertices. While these restrictions simplify mathematical analysis, many real-world applications require more complex structures, and we will relax these constraints as needed in subsequent sections.

The order of a graph refers to the number of vertices it contains, denoted as $|V|$, while the size refers to the number of edges, denoted as $|E|$. When analyzing graph complexity, the relationship between these quantities is often expressed through the graph's density, defined as:

$$\text{density}(G) = \frac{2|E|}{|V|(|V|-1)}$$

This formula yields values between 0 (a graph with no edges) and 1 (a complete graph where every possible edge exists). Dense graphs, where density approaches 1, have many connections relative to their size, while sparse graphs, where density approaches 0, have relatively few edges. This distinction becomes critically important when designing neural network architectures for graph data, as computational complexity often depends on the number of edges.

For every edge $\{u, v\} \in E$, we say that vertices $u$ and $v$ are adjacent or neighbors, and that the edge is incident on both $u$ and $v$. The neighborhood of a vertex $v$, denoted $N(v)$ or $\mathcal{N}(v)$, is the set of all vertices adjacent to $v$:

$$N(v) = \{u \in V : \{u, v\} \in E\}$$

The degree of a vertex $v$, denoted $\deg(v)$, is the number of edges incident on $v$, which equivalently equals the size of its neighborhood:

$$\deg(v) = |N(v)|$$

In directed graphs (discussed in detail below), we distinguish between in-degree, the number of edges pointing into a vertex, and out-degree, the number of edges pointing out of a vertex.

An important theorem that will recur throughout our study of graph neural networks is the Handshaking Lemma, which states that the sum of all vertex degrees in a graph equals twice the number of edges:

$$\sum_{v \in V} \deg(v) = 2|E|$$

This simple relationship has profound implications for understanding the structural properties of graphs and for designing efficient algorithms that process graph data.

Directed and Undirected Graphs

One of the most fundamental distinctions in graph theory is between undirected graphs and directed graphs (also called digraphs). In an undirected graph, edges have no inherent direction—an edge $\{u, v\}$ indicates a symmetric relationship between $u$ and $v$ where both vertices are treated equally. Friendship relationships on social media platforms are naturally modeled as undirected edges: if Alice is friends with Bob, then Bob is necessarily friends with Alice.

In a directed graph $G = (V, E)$, edges are ordered pairs rather than unordered pairs, so $E \subseteq \{(u, v) : u, v \in V, u \neq v\}$. An edge $(u, v)$ is directed from $u$ to $v$, meaning it represents an asymmetric relationship where $u$ is the source and $v$ is the target. Following on social media, the "follows" relationship on platforms like Twitter or Instagram is inherently directed: if Alice follows Bob, this does not imply that Bob follows Alice.

The asymmetry of directed graphs introduces important structural considerations. A directed path from vertex $u$ to vertex $v$ is a sequence of directed edges that can be traversed from $u$ to $v$, respecting edge directions. A strongly connected directed graph is one where every vertex is reachable from every other vertex—that is, for any pair of vertices $(u, v)$, there exists both a directed path from $u$ to $v$ and a directed path from $v$ to $u$. In contrast, a directed graph is weakly connected if the underlying undirected graph (obtained by treating all edges as undirected) is connected.

These connectivity properties have significant implications for graph neural network architectures. Message passing in GNNs relies on information flowing along edges, and the nature of this flow—whether it respects edge directions or ignores them—fundamentally shapes what the network can learn. We will explore these considerations extensively in subsequent chapters.

Weighted and Unweighted Graphs

Unweighted graphs treat all edges as equally important, using binary values to indicate the presence or absence of connections. Weighted graphs, on the other hand, assign numerical values to edges to represent the strength, capacity, cost, or any other quantitative aspect of the relationship between vertices.

Formally, a weighted graph is defined as $G = (V, E, w)$ where $w: E \rightarrow \mathbb{R}$ is a weight function that assigns a real-valued weight to each edge. The weights can represent diverse concepts depending on the application domain: the physical distance between locations in a transportation network, the communication bandwidth between computer