Course contentsShow
← Machine Learning and Deep Learning
Lesson 2485 of 3,53854. Graph Neural NetworksFree lesson

Graph Representations: Adjacency List and Edge List

Store graphs as adjacency lists or edge lists; compare storage efficiency and access patterns with matrices.

Graph Representations: Adjacency List and Edge List

You'll learn two memory-efficient ways to store graphs and when to use them instead of adjacency matrices.

Beyond Matrices: List-Based Representations

While adjacency matrices offer fast lookups, they waste space for sparse graphs (graphs with few edges relative to possible connections). Two list-based alternatives trade some lookup speed for dramatic memory savings.

Adjacency List

An adjacency list stores each node with a list of its neighbors:

Node 0: [1, 3]
Node 1: [0, 2]
Node 2: [1, 3]
Node 3: [0, 2]

Think of it like a contact list on your phone—you only record people you actually know, not every person on Earth with "no connection" entries.

Storage: O(V + E) space, where V = nodes, E = edges
Access: Finding all neighbors of node i is O(1), but checking if edge (i,j) exists takes O(degree(i))

Edge List

An edge list is simply a list of all edges as pairs:

[(0, 1), (0, 3), (1, 2), (2, 3)]

This is the most compact representation—just the connections, nothing else.

Storage: O(E) space
Access: Finding neighbors requires scanning the entire list O(E)

Comparing the Three

  • Adjacency matrix: Fast lookups, heavy memory (O(V²))—best for dense graphs
  • Adjacency list: Balanced—best for most real-world sparse graphs and when you frequently traverse neighbors
  • Edge list: Minimal storage—best when you just need to iterate all edges once (e.g., loading data)

Most Graph Neural Network libraries (like PyTorch Geometric) use edge lists internally for efficiency, converting to other forms only when needed.

Key Takeaway: Adjacency lists and edge lists save massive memory on sparse graphs; choose adjacency lists for neighbor traversal or edge lists for pure storage and batch processing.