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.