Representing Graphs: Adjacency Lists and Matrices

Efficiently storing a graph's structure in computer memory is fundamental for applying powerful graph algorithms to machine learning problems. A graph $G$ is defined by a set of vertices (or nodes) $V$ and a set of edges $E$, where each edge connects a pair of vertices. The chosen representation for $V$ and $E$ can significantly impact the efficiency of graph algorithms in terms of both memory usage and computation time.

Let's consider a simple example graph to illustrate the common representation methods. Imagine a small social network:

An undirected graph representing connections between five individuals (A, B, C, D, E).

We'll explore two primary ways to represent this graph (and graphs in general): Adjacency Matrices and Adjacency Lists.

Adjacency Matrix

An adjacency matrix represents a graph as a square matrix, typically denoted as $M$. If the graph has $|V| = n$ vertices, the matrix will be of size $n \times n$. The vertices are usually mapped to integers from $0$ to $n-1$.

For an unweighted graph, the entry $M[i][j]$ is:

• 1 if there is an edge connecting vertex $i$ and vertex $j$.
• 0 otherwise.

For a weighted graph, the entry $M[i][j]$ is:

• The weight of the edge between vertex $i$ and vertex $j$ if an edge exists.
• 0 or $\infty$ (or some other indicator of non-connection) if there is no direct edge. Using 0 works if edge weights are non-zero.

For an undirected graph, the adjacency matrix is symmetric ($M[i][j] = M[j][i]$), because an edge between $i$ and $j$ is the same as an edge between $j$ and $i$. For a directed graph (where edges have a direction, e.g., $i \rightarrow j$), the matrix is not necessarily symmetric. An entry $M[i][j]=1$ means there's an edge from $i$ to $j$.

Example: Adjacency Matrix for the Social Network Graph

Let's map A=0, B=1, C=2, D=3, E=4. Since it's undirected and unweighted:

   A B C D E
   (0 1 2 3 4)
A(0)[0 1 1 0 1]
B(1)[1 0 0 0 1]
C(2)[1 0 0 1 1]
D(3)[0 0 1 0 1]
E(4)[1 1 1 1 0]

In Python, this could be represented using a NumPy array:

import numpy as np

# Adjacency Matrix for the example graph
adj_matrix = np.array([
  # A B C D E
    [0,1,1,0,1], # A
    [1,0,0,0,1], # B
    [1,0,0,1,1], # C
    [0,0,1,0,1], # D
    [1,1,1,1,0]  # E
])

# Check if there's an edge between C (index 2) and D (index 3)
print(f"Edge between C and D? {adj_matrix[2, 3] == 1}")

# Check if there's an edge between A (index 0) and D (index 3)
print(f"Edge between A and D? {adj_matrix[0, 3] == 1}")

Performance Characteristics:

"* Space Complexity: Requires $O(V^2)$ space, regardless of the number of edges. This can be very inefficient for sparse graphs (graphs with relatively few edges compared to the maximum possible, $V^2$). Many graphs, like social networks or web graphs, are sparse."

• Time Complexity:
  • Checking if an edge exists between vertex $i$ and $j$: $O(1)$ (just access $M[i][j]$).
  • Finding all neighbors of a vertex $i$: $O(V)$ (need to iterate through the entire row $M[i]$).
  • Adding or removing an edge: $O(1)$.
  • Adding a vertex: Requires resizing the matrix, which is typically $O(V^2)$.

Adjacency List

An adjacency list represents a graph as a collection of lists (or similar dynamic arrays/sets). There is one list for each vertex in the graph. For a vertex $u$, the list associated with $u$ contains all the vertices $v$ such that there is an edge connecting $u$ and $v$.

• For an unweighted graph, the list for vertex $u$ simply contains the indices or identifiers of its neighbors.
• For a weighted graph, the list typically stores pairs (or tuples) for each neighbor $v$: (v, weight), representing the neighbor and the weight of the edge connecting $u$ to $v$.
• For a directed graph, the list for vertex $u$ contains only the vertices $v$ such that there is an edge from $u$ to $v$.

Example: Adjacency List for the Social Network Graph

Using dictionaries in Python where keys are vertices and values are lists of neighbors:

adj_list = {
    'A': ['B', 'C', 'E'],
    'B': ['A', 'E'],
    'C': ['A', 'D', 'E'],
    'D': ['C', 'E'],
    'E': ['A', 'B', 'C', 'D']
}

# If using integer indices (0-4):
adj_list_indexed = {
    0: [1, 2, 4], # Neighbors of A (0)
    1: [0, 4],    # Neighbors of B (1)
    2: [0, 3, 4], # Neighbors of C (2)
    3: [2, 4],    # Neighbors of D (3)
    4: [0, 1, 2, 3]  # Neighbors of E (4)
}

# Find neighbors of C
print(f"Neighbors of C: {adj_list['C']}")

# Check if there's an edge between C and D
print(f"Edge between C and D? {'D' in adj_list['C']}")

Performance Characteristics:

• Space Complexity: Requires $O(V + E)$ space. For an undirected graph, each edge $(u, v)$ appears twice (once in $u$'s list, once in $v$'s list), so it's proportional to $V$ plus $2E$. For a directed graph, each edge appears once. This is very memory-efficient for sparse graphs, where $E$ is much smaller than $V^2$.
• Time Complexity:
  • Checking if an edge exists between vertex $u$ and $v$: $O(\text{degree}(u))$, where $\text{degree}(u)$ is the number of neighbors of $u$. We need to scan $u$'s list to see if $v$ is present. Using a set instead of a list for neighbors can improve this to $O(1)$ on average.
  • Finding all neighbors of a vertex $u$: $O(\text{degree}(u))$ (just traverse the list for $u$). This is efficient for sparse graphs.
  • Adding an edge $(u, v)$: $O(1)$ on average (assuming list append is amortized constant time).
  • Adding a vertex: $O(1)$ on average.

Comparison and Trade-offs

The choice between an adjacency matrix and an adjacency list depends heavily on the properties of the graph and the operations you need to perform frequently.

Feature	Adjacency Matrix	Adjacency List	When to Prefer
Space	$O(V^2)$	$O(V+E)$	List: Sparse graphs ($E \ll V^2$)
			Matrix: Dense graphs ($E \approx V^2$)
Check Edge(u,v)	$O(1)$	$O(\text{degree}(u))$ / $O(1)^{*}$	Matrix: Frequent edge checks
List Neighbors(u)	$O(V)$	$O(\text{degree}(u))$	List: Frequent neighbor iteration
Add Edge	$O(1)$	$O(1)$ (average)	(Similar)
Remove Edge	$O(1)$	$O(\text{degree}(u))$ / $O(1)^{*}$	Matrix: Frequent edge removal
Add Vertex	$O(V^2)$ (resize)	$O(1)$ (average)	List: Dynamic graph size

*Using sets for neighbor storage makes check/remove $O(1)$ average time complexity for adjacency lists.

"In machine learning contexts, graphs representing phenomena (social networks, user-item interactions, molecular structures) are often large and sparse. Therefore, adjacency lists are generally the preferred representation due to their significant space savings and efficient neighbor iteration, which is fundamental to many graph algorithms like BFS and DFS discussed next. Adjacency matrices might be considered for smaller, denser graphs or when extremely fast edge existence checks are the absolute priority."

Understanding these representations is the first step towards implementing and analyzing the performance of graph algorithms important for tasks like building recommendation systems, analyzing network structures, and enabling graph neural networks.