Introduction to Graphs

Learning Objectives

By the end of this section, you will be able to:

1. Define graphs mathematically as structures G = (V, E) with nodes, edges, and their properties
2. Distinguish between graph types including directed, undirected, weighted, bipartite, and acyclic graphs
3. Represent graphs computationally using adjacency matrices, adjacency lists, and edge lists
4. Calculate key graph properties such as degree, density, and path length
5. Identify graph-structured data in real-world applications from social networks to molecules
6. Understand why graphs matter for ML and the limitations of traditional neural networks on graph data

Why This Matters: Graphs are everywhere—from social networks and molecules to knowledge bases and road networks. Unlike images (grids) or text (sequences), graph data has irregular structure that traditional neural networks cannot handle. Understanding graph fundamentals is the foundation for Graph Neural Networks (GNNs), which have revolutionized applications in drug discovery, recommendation systems, fraud detection, and more.

Why Graphs? The Big Picture

Consider the data structures you've encountered in deep learning so far:

These architectures exploit the regular structure of their input data:

• CNNs leverage the 2D grid structure of images with local receptive fields and weight sharing
• RNNs/Transformers process sequences by modeling temporal or positional dependencies
• MLPs treat input as a fixed-length feature vector with no inherent structure

But what about data with irregular structure? Consider:

• A social network where people have varying numbers of friends
• A molecule with atoms connected in arbitrary configurations
• A 3D mesh representing a surface with variable connectivity
• A knowledge graph linking entities through different relationship types

What is a Graph?

At its core, a graph is a mathematical structure that models pairwise relationships between objects. The objects are called nodes (or vertices), and the relationships are called edges (or links).

Intuitive Examples

The beauty of graph representation is its universality: once data is represented as a graph, we can apply the same algorithms and neural architectures regardless of the original domain.

Formal Mathematical Definition

A graph is defined as an ordered pair:

where:

• $V$ is a set of vertices (nodes): $V = \{v_1, v_2, \ldots, v_n\}$
• $E$ is a set of edges: $E \subseteq V \times V$

We typically denote:

• $|V| = n$ as the number of nodes
• $|E| = e$ (or $m$) as the number of edges

Node and Edge Attributes

In practical applications, nodes and edges often carry additional information:

For example, in a molecular graph:

• Node features $\mathbf{x}_v$ might encode atom type, charge, and hybridization
• Edge features $\mathbf{e}_{uv}$ might encode bond type (single, double, triple) and bond length

The Neighborhood Function

One of the most important concepts in graph neural networks is the neighborhood:

This is the set of all nodes directly connected to $v$. The degree of a node is the size of its neighborhood:

Interactive: Graph Explorer

Explore the fundamental structure of graphs with this interactive visualization. You can add nodes, connect them with edges, and observe how graph properties change in real-time.

Types of Graphs

Graphs come in many varieties, each suited to different types of relationships. The choice of graph type significantly impacts how we design algorithms and neural networks.

Directed vs. Undirected Graphs

The most fundamental distinction is whether edges have direction:

In undirected graphs, if Alice is connected to Bob, then Bob is also connected to Alice. The edge $(A, B)$ is the same as $(B, A)$.

In directed graphs (digraphs), edges have a direction. Alice following Bob on Twitter does not mean Bob follows Alice.

Weighted Graphs

When edges carry numerical values, we have a weighted graph:

Weights can represent distances, costs, similarities, or interaction strengths. For instance:

• Road network: Edge weight = travel time or distance
• Social network: Edge weight = interaction frequency
• Protein network: Edge weight = interaction confidence score

Special Graph Types

Graph Representations in Code

To work with graphs computationally, we need efficient data structures. The choice of representation affects both memory usage and algorithm efficiency.

Adjacency Matrix

The adjacency matrix $\mathbf{A} \in \{0, 1\}^{n \times n}$ encodes edges as matrix entries:

Properties of the adjacency matrix:

• Undirected graphs: $\mathbf{A}$ is symmetric ($\mathbf{A} = \mathbf{A}^T$)
• Self-loops: Diagonal entries $A_{ii}$ indicate self-connections
• Degree: Row sum gives degree: $\text{deg}(i) = \sum_j A_{ij}$
• Paths: $(\mathbf{A}^k)_{ij}$ counts paths of length $k$ from $i$ to $j$

1import torch
2import numpy as np
3
4def create_adjacency_matrix(edges: list, num_nodes: int) -> torch.Tensor:
5    """
6    Create an adjacency matrix from an edge list.
7
8    Args:
9        edges: List of (source, target) tuples
10        num_nodes: Total number of nodes
11
12    Returns:
13        Adjacency matrix of shape (num_nodes, num_nodes)
14    """
15    # Initialize with zeros
16    A = torch.zeros(num_nodes, num_nodes)
17
18    for src, tgt in edges:
19        A[src, tgt] = 1
20        A[tgt, src] = 1  # For undirected graph
21
22    return A
23
24
25# Example: Simple triangle graph (A-B-C-A)
26edges = [(0, 1), (1, 2), (2, 0)]
27num_nodes = 3
28
29A = create_adjacency_matrix(edges, num_nodes)
30print("Adjacency Matrix:")
31print(A)
32# tensor([[0., 1., 1.],
33#         [1., 0., 1.],
34#         [1., 1., 0.]])
35
36# Calculate degree of each node
37degrees = A.sum(dim=1)
38print(f"\nDegrees: {degrees}")  # tensor([2., 2., 2.])
39
40# Count paths of length 2
41A2 = A @ A
42print(f"\nPaths of length 2 (A²):")
43print(A2)
44# A²[i,j] = number of 2-hop paths from i to j

Adjacency List

For sparse graphs, an adjacency list is more memory-efficient:

1from collections import defaultdict
2from typing import Dict, List, Set
3
4class Graph:
5    """
6    Graph representation using adjacency lists.
7    Efficient for sparse graphs where |E| << |V|².
8    """
9
10    def __init__(self, directed: bool = False):
11        self.adj_list: Dict[int, Set[int]] = defaultdict(set)
12        self.directed = directed
13        self.num_edges = 0
14
15    def add_edge(self, u: int, v: int):
16        """Add an edge between nodes u and v."""
17        self.adj_list[u].add(v)
18        if not self.directed:
19            self.adj_list[v].add(u)
20        self.num_edges += 1
21
22    def neighbors(self, v: int) -> Set[int]:
23        """Return the neighborhood N(v) of node v."""
24        return self.adj_list[v]
25
26    def degree(self, v: int) -> int:
27        """Return the degree of node v."""
28        return len(self.adj_list[v])
29
30    def has_edge(self, u: int, v: int) -> bool:
31        """Check if edge (u, v) exists. O(1) average with set."""
32        return v in self.adj_list[u]
33
34    @property
35    def num_nodes(self) -> int:
36        return len(self.adj_list)
37
38
39# Example usage
40g = Graph(directed=False)
41
42# Add edges
43for edge in [(0, 1), (1, 2), (2, 0), (2, 3)]:
44    g.add_edge(*edge)
45
46print(f"Number of nodes: {g.num_nodes}")
47print(f"Number of edges: {g.num_edges}")
48print(f"Neighbors of node 2: {g.neighbors(2)}")  # {0, 1, 3}
49print(f"Degree of node 2: {g.degree(2)}")  # 3
50print(f"Edge (1, 2) exists: {g.has_edge(1, 2)}")  # True

Edge List (COO Format)

The edge list format stores edges as pairs of indices. This is the standard format in PyTorch Geometric:

1import torch
2
3def create_edge_index(edges: list) -> torch.Tensor:
4    """
5    Create edge_index tensor in COO format.
6    This is the standard format used in PyTorch Geometric.
7
8    Args:
9        edges: List of (source, target) tuples
10
11    Returns:
12        edge_index: Tensor of shape (2, num_edges)
13                   Row 0: source nodes
14                   Row 1: target nodes
15    """
16    sources = [e[0] for e in edges]
17    targets = [e[1] for e in edges]
18
19    edge_index = torch.tensor([sources, targets], dtype=torch.long)
20    return edge_index
21
22
23# Example
24edges = [(0, 1), (1, 2), (2, 0), (0, 3)]
25edge_index = create_edge_index(edges)
26
27print("Edge index (COO format):")
28print(edge_index)
29# tensor([[0, 1, 2, 0],
30#         [1, 2, 0, 3]])
31
32# For undirected graphs, include reverse edges
33def to_undirected(edge_index: torch.Tensor) -> torch.Tensor:
34    """Convert to undirected by adding reverse edges."""
35    row, col = edge_index
36    edge_index_undirected = torch.stack([
37        torch.cat([row, col]),
38        torch.cat([col, row])
39    ], dim=0)
40    return edge_index_undirected
41
42edge_index_undirected = to_undirected(edge_index)
43print("\nUndirected edge index:")
44print(edge_index_undirected)
45# tensor([[0, 1, 2, 0, 1, 2, 0, 3],
46#         [1, 2, 0, 3, 0, 1, 3, 0]])

Key Graph Properties

Understanding graph properties is essential for both algorithm design and understanding GNN behavior.

Degree Distribution

The degree distribution $P(k)$ gives the probability that a randomly selected node has degree $k$:

Many real-world graphs follow a power-law degree distribution:

This means most nodes have few connections, but a few "hub" nodes have many. Such graphs are called scale-free.

Graph Density

Density measures how connected a graph is relative to its maximum possible edges:

Paths and Connectivity

A path from node $u$ to $v$ is a sequence of edges connecting them:

Key path-related concepts:

The Degree Matrix and Graph Laplacian

Two matrices are fundamental to spectral graph theory and many GNN architectures:

The degree matrix $\mathbf{D}$ is diagonal with degrees on the diagonal:

The graph Laplacian captures the difference between a node and its neighbors:

The normalized Laplacian (used in many GNNs):

Real-World Graph Data

Graph-structured data appears across virtually every domain. Understanding these applications motivates why we need specialized neural network architectures.

Common Patterns in Real-World Graphs

Despite their diversity, most real-world graphs share common structural properties:

1. Power-law degree distribution: A few hub nodes have many connections; most nodes have few
2. Small-world property: Short average path lengths despite sparse connections ("six degrees of separation")
3. Community structure: Nodes cluster into densely connected groups with sparse inter-group connections
4. Homophily: Connected nodes tend to be similar (birds of a feather flock together)
5. Heterophily: In some graphs, connected nodes are dissimilar (buyers and sellers)

Why Graphs in Machine Learning?

Now that we understand graph structure, why can't we just use standard neural networks on graph data?

The Challenge of Irregular Structure

Traditional neural networks assume fixed input structure:

• MLPs: Fixed-length feature vector
• CNNs: Fixed grid (224×224 pixels)
• RNNs: Sequential ordering

Graphs violate all these assumptions:

The Permutation Invariance Requirement

A fundamental property required for any graph learning model is permutation invariance (for graph-level tasks) or permutation equivariance (for node-level tasks):

where $\mathbf{P}$ is any permutation matrix. This means the output should not depend on how we arbitrarily numbered the nodes.

What Graph Neural Networks Provide

Graph Neural Networks (GNNs) address these challenges through:

1. Local aggregation: Each node aggregates information from its neighbors, handling variable neighborhoods
2. Permutation equivariance: Operations are defined on edges and neighborhoods, not absolute positions
3. Weight sharing: The same transformation is applied at every node, enabling arbitrary graph sizes
4. Hierarchical representations: Stacking layers captures increasingly distant information

In the next sections, we'll see how these principles lead to specific GNN architectures like GCN, GraphSAGE, and GAT.

Summary

This section introduced the fundamental concepts of graphs as a data structure for machine learning. Here are the key takeaways:

Core Concepts

Key Equations

1. Graph definition: $G = (V, E)$
2. Neighborhood: $\mathcal{N}(v) = \{u : (u, v) \in E\}$
3. Degree: $\text{deg}(v) = \sum_j A_{vj}$
4. Density: $\rho = \frac{2|E|}{n(n-1)}$
5. Laplacian: $\mathbf{L} = \mathbf{D} - \mathbf{A}$

Looking Forward

In the next section, we'll explore why we need specialized neural networks for graphs—understanding the limitations of traditional architectures and the key ideas that enable graph neural networks.

Knowledge Check

Test your understanding of graph fundamentals with this quiz:

Exercises

Conceptual Questions

1. Explain why social networks typically exhibit a power-law degree distribution. What real-world phenomenon does this reflect?
2. Given a bipartite graph representing users and movies (edges = watched), what would edges in the user-user projection graph represent?
3. Why is the graph Laplacian positive semi-definite? What does this imply about its eigenvalues?
4. A tree with $n$ nodes has $n-1$ edges. Use this to explain why adding any edge to a tree creates exactly one cycle.

Mathematical Exercises

1. Handshaking Lemma: Prove that $\sum_{v \in V} \text{deg}(v) = 2|E|$ for any undirected graph.
2. Adjacency Matrix Powers: Show that $(\mathbf{A}^2)_{ij}$ equals the number of common neighbors between nodes $i$ and $j$.
3. Bipartite Characterization: Prove that a graph is bipartite if and only if it contains no odd-length cycles.
4. Laplacian Properties: For the graph Laplacian $\mathbf{L}$, show that $\mathbf{L}\mathbf{1} = \mathbf{0}$ where $\mathbf{1}$ is the all-ones vector.

Coding Exercises

1. Graph Class Implementation: Implement a Python class that supports both adjacency matrix and adjacency list representations, with methods to convert between them.
2. Degree Distribution: Load a real-world graph dataset (e.g., Karate Club from PyTorch Geometric) and plot its degree distribution. Does it follow a power law?
3. BFS Implementation: Implement breadth-first search to compute shortest paths from a source node to all other nodes.
4. Connected Components: Implement an algorithm to find all connected components in an undirected graph.

Now that you understand graph fundamentals, you're ready to explore why we need Graph Neural Networks—understanding the unique challenges graphs pose for traditional neural networks and the key principles that enable learning on graph-structured data.