What Is a Graph? Nodes, Edges, Features, and Labels
Published:
Graphs Are Everywhere
Most structured data is relational — entities connected by relationships:
- Social networks: users (nodes) connected by friendships (edges)
- Molecules: atoms (nodes) connected by bonds (edges)
- Citation networks: papers (nodes) connected by citations (edges)
- Road networks: intersections (nodes) connected by roads (edges)
- Knowledge graphs: entities (nodes) connected by relations (typed edges)
Standard deep learning assumes inputs are grids (images), sequences (text), or fixed-size vectors. Graphs have variable size, irregular structure, and no canonical ordering — making them fundamentally different.
Graph Anatomy
A graph \(G = (V, E)\) consists of:
- \(V\) — a set of nodes (also called vertices), with \(N = \lvert V \rvert\) the number of nodes.
- \(E \subseteq V \times V\) — a set of edges. An edge \((u, v) \in E\) records a relationship between nodes \(u\) and \(v\).
Node Features
Nodes are rarely bare identifiers. Each node \(v \in V\) carries a feature vector \(x_v \in \mathbb{R}^{d}\). Stacking these row-wise gives the node feature matrix:
Examples:
- In a citation network: \(x_v\) = bag-of-words representation of the paper
- In a molecule: \(x_v\) = atom type, charge, hybridisation state
- In a social network: \(x_v\) = age, location, activity features
Edge Features
Edges can also carry features \(e_{uv} \in \mathbb{R}^{k}\), stacked into an edge feature matrix \(X_E \in \mathbb{R}^{M \times k}\):
- In a molecule: bond type (single/double/aromatic), bond length
- In a knowledge graph: relation type (one-hot)
- In a road network: distance, speed limit, traffic volume
Labels
What you want to predict determines the task level:
| Task level | Label | Example |
|---|---|---|
| Node | \(y_v\) per node | Paper topic (node classification) |
| Edge | \(y_{uv}\) per edge | Will users \(u\) and \(v\) become friends? (link prediction) |
| Graph | \(y_G\) per graph | Is this molecule toxic? (graph classification) |
Concrete Example: A Molecule as a Graph
Consider water (H₂O), using the feature template (atomic number, valence electrons, electronegativity × 10):
- Nodes: O (oxygen, node 0), H (hydrogen, node 1), H (hydrogen, node 2)
- Node features: \(x_0 = [8,\, 6,\, 34]\) for oxygen, and \(x_1 = x_2 = [1,\, 1,\, 22]\) for the two hydrogens
- Edges: \((0,1)\) and \((0,2)\) — two O–H bonds
- Edge features: \(e_{01} = e_{02} = [1,\, 0.96]\) (bond order 1, bond length 0.96 Å)
- Graph label: \(y_G = 1\) (polar molecule, for a binary classification task)
This small example shows every component: node features capturing chemistry, edge features capturing bond properties, and a graph-level label for the prediction task.
The Adjacency Matrix
A graph’s structure is encoded in an adjacency matrix \(A \in \{0,1\}^{N \times N}\):
For an undirected graph \(A\) is symmetric, i.e. \(A = A^{\top}\). For a weighted graph, \(A_{uv}\) holds the weight of edge \((u,v)\) instead of a 0/1 indicator.
The adjacency matrix is rarely stored explicitly for large graphs (too sparse) — instead, edge lists or sparse formats are used.
Neighbourhood
The neighbourhood of node \(v\) is the set of nodes directly connected to it:
The degree of node \(v\) is \(\deg(v) = \lvert \mathcal{N}(v) \rvert\) — the number of neighbours. Degree is one of the most fundamental structural properties of a node.
What GNNs Learn
A GNN takes as input:
- The graph structure (adjacency matrix or edge list)
- Node features \(X\)
- (Optionally) edge features
And produces as output:
- Node embeddings \(h_v \in \mathbb{R}^{d'}\) for each node (used for node classification)
- Edge embeddings \(h_{uv}\) for each edge (used for link prediction)
- Graph embedding \(h_G \in \mathbb{R}^{d'}\) (used for graph classification)
The core operation: each node aggregates information from its neighbours, combines it with its own features, and updates its representation — iterating this over multiple rounds.
Summary
| Concept | Notation | Example |
|---|---|---|
| Node set | \(V\), with \(N = \lvert V \rvert\) | Papers, atoms, users |
| Edge set | \(E\), with \(M = \lvert E \rvert\) | Citations, bonds, friendships |
| Node features | \(X \in \mathbb{R}^{N \times d}\) | Bag-of-words, atom type |
| Edge features | \(X_E \in \mathbb{R}^{M \times k}\) | Bond type, relation type |
| Adjacency matrix | \(A \in \{0,1\}^{N \times N}\) | Who is connected to whom |
| Neighbourhood | \(\mathcal{N}(v)\) | Direct neighbours of \(v\) |
| Node label | \(y_v\) | Paper topic |
| Graph label | \(y_G\) | Molecule toxicity |
Graphs are the natural language of relational data. GNNs are the deep learning architectures that speak it.
References
- Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer. — Standard reference for graph theory fundamentals.
- Hamilton, W. L. (2020). Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning.
- Bronstein, M. M., Bruna, J., Cohen, T., & Veličković, P. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv preprint.