What is the difference between a directed and an undirected graph?

In an undirected graph, every edge is bidirectional — if A is connected to B, then B is also connected to A. The adjacency matrix is symmetric. In a directed graph (digraph), edges have a direction: A can point to B without B pointing back to A. Social media 'follows' are directed; Facebook 'friendships' are undirected. GNNs handle both, but the message passing logic differs slightly for each.

Why do GNNs use sparse matrix representations instead of dense adjacency matrices?

Real-world graphs are extremely sparse. A web graph with 1 billion nodes where each node has an average of 10 links has 10 billion edges but a potential 10^18 adjacency matrix entries. Storing a dense matrix is physically impossible. Sparse formats (COO, CSR) only store the (row, col) coordinates of non-zero entries, reducing memory from O(N²) to O(E), which is the only practical approach for large-scale graphs.

What is a node feature vector and why does it matter?

A node feature vector is the numeric representation of a node's attributes. For a user node, it might encode posting frequency, account age, and follower count. For an atom node, it encodes atomic number and formal charge. GNNs learn to transform these feature vectors using information from the graph's connectivity. Without feature vectors, the GNN would have no signal to work with — it would only see the structure, not the content.

🚀 LEVEL UP TO SENIOR:Unlock 500+ Advanced Practical Challenges & Exercises.

🎓 COURSERA PARTNER:Earn professional Google, Meta, and IBM certificates to supercharge your resume.

Tutorials

HTML MASTER CLASS /// LEARN TAGS /// BUILD STRUCTURE /// SEMANTIC WEB /// HTML MASTER CLASS /// LEARN TAGS ///

⚡ Total XP: 0|💻 artificialintelligence XP: 0

Graphs and Network Data in AI & Artificial Intelligence

Master the foundational data structures of graph deep learning. Explore nodes, edges, adjacency matrices, and node feature vectors. Understand why CNNs and RNNs fundamentally cannot handle graph data, and see how GNNs solve the core problem of permutation invariance on irregular topology.

LOADING ENGINE...

Skill Matrix

UNLOCK NODES BY LEARNING NEW TAGS.

Graph Hub

Structural logic.

Quick Quiz //

Why can't a standard CNN be applied directly to graph data?

The real world is not a spreadsheet. It is a web of relationships — proteins binding to proteins, users following users, transactions flowing between accounts. Before you can build a GNN, you need to understand the data structure it operates on: the graph.

1How Computers See a Network

A graph G is defined by a set of nodes V and a set of edges E. Every node represents an entity — a user, an atom, a word — and every edge represents a relationship between two entities. For a computer to process this, we need a numeric representation. The standard choice is the Adjacency Matrix (A), a square N×N matrix where A[i][j] = 1 if an edge exists between node i and node j, and 0 otherwise.

This works well conceptually, but it does not scale. A social network with 1 million users requires a matrix with 1 trillion entries, the vast majority of which are zeros because most people are not directly connected to most other people. This is the Sparsity Problem. In practice, GNN libraries like PyTorch Geometric store graphs as Edge Lists — a flat list of (source, destination) pairs — which only stores the connections that actually exist. This reduces memory from O(N²) to O(E), where E is the number of edges.

—

// Dense Matrix: O(N²) memory
const adjMatrix = [
  [0,1,0,1], // Node A → B,D
  [1,0,1,0], // Node B → A,C
  [0,1,0,1], // Node C → B,D
  [1,0,1,0], // Node D → A,C
];
// 1M nodes → 1 TRILLION entries ❌

// Sparse Edge List: O(E) memory
const edgeIndex = [
  [0,1],[0,3], // A's edges
  [1,2],[2,3], // B,C edges
];
// 4 edges → 4 entries ✓

localhost:3000

localhost:3000/graph-memory

Memory Cost (N = 1M nodes)

Dense Matrix: ~4 TB RAM ❌

Edge List (10M edges): ~80 MB RAM ✓

Memory saved: 99.998%

2Why Standard Neural Networks Fail on Graphs

CNNs work because images are Euclidean: every pixel has exactly 8 neighbors, always arranged in the same spatial order. This regularity lets a convolutional filter slide across the grid in a predictable way. Graphs break this assumption entirely. A node might have 1 neighbor or 10,000 neighbors, and those neighbors have no inherent ordering. If you fed a node's neighbors into an MLP, the model would produce a different output depending on the arbitrary order you chose — which is meaningless and incorrect.

GNNs solve this with Permutation Invariant operations. Instead of processing neighbors in a fixed order, GNNs aggregate neighbor features using functions like Sum, Mean, or Max that produce the same result regardless of the input order. Alongside the structural connectivity, every node carries a Feature Vector — a numeric representation of its attributes (e.g., a user's age and activity count, or an atom's atomic number). These feature vectors are the signals that the GNN learns to transform through message passing.

—

// ❌ MLP: Permutation-VARIANT
function mlpFail(neighbors) {
  return mlp(neighbors.flat());
  // [B,C,D] → output_A
  // [D,C,B] → output_B ≠ output_A ❌
}

// ✓ GNN: Permutation-INVARIANT sum
function gnnAggregate(neighbors, dim) {
  return neighbors.reduce(
    (acc, h_j) =>
      acc.map((v, i) => v + h_j[i]),
    new Array(dim).fill(0)
  );
  // [B,C,D] OR [D,C,B] → same result ✓
}

localhost:3000

localhost:3000/permutation-test

Permutation Invariance Test

MLP([B,C,D]): [0.82, 0.11] ❌
MLP([D,C,B]): [0.43, 0.57] ❌

SUM([B,C,D]): [1.5, 2.1] ✓
SUM([D,C,B]): [1.5, 2.1] ✓