Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI ๐Ÿ‘จ๐Ÿปโ€๐Ÿ’ป๐Ÿค–

What Is a Graph? Nodes, Edges, Features, and Labels

4 minute read

Published:

TL;DR: A graph G = (V, E) has nodes (entities) and edges (relationships). Nodes carry feature vectors X; edges can carry feature vectors E. Labels Y can be at the node level, edge level, or graph level. GNNs learn to map (G, X) โ†’ Y.

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).V= N is the number of nodes.
  • E โŠ† V ร— V โ€” a set of edges. Each edge (u, v) โˆˆ E indicates a relationship between nodes u and v.
G = (V, E)    |V| = N    |E| = M

Node Features

Nodes are rarely bare identifiers. Each node v โˆˆ V has a feature vector x_v โˆˆ โ„^d. Stacked into a matrix:

X โˆˆ โ„^{N ร— d} where X[v] = x_v

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} โˆˆ โ„^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 levelLabelExample
Nodey_v per nodePaper topic (node classification)
Edgey_{uv} per edgeWill users u and v become friends? (link prediction)
Graphy_G per graphIs this molecule toxic? (graph classification)

The Adjacency Matrix

A graphโ€™s structure is encoded in an adjacency matrix A โˆˆ {0,1}^{Nร—N}:

A[u,v] = 1 if (u,v) โˆˆ E, else 0

For an undirected graph, A is symmetric. For a weighted graph, A[u,v] = weight of edge (u,v).

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:

N(v) = { u โˆˆ V : (u,v) โˆˆ E }
The degree of node v isN(v)โ€” 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 โˆˆ โ„^dโ€™ for each node (used for node classification)
  • Edge embeddings h_{uv} for each edge (used for link prediction)
  • Graph embedding h_G โˆˆ โ„^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.

Key difference from grids and sequences: In a sequence, every position has exactly 2 neighbours (left and right). In an image, every pixel has exactly 8. In a graph, nodes can have 0 to thousands of neighbours, and there is no canonical ordering of those neighbours. This irregularity is the central challenge that GNN architectures must handle.

Summary

ConceptNotationExampleย ย 
Node setV,V=NPapers, atoms, users
Edge setE,E=MCitations, bonds, friendships
Node featuresX โˆˆ โ„^{Nร—d}Bag-of-words, atom typeย ย 
Edge featuresE โˆˆ โ„^{Mร—k}Bond type, relation typeย ย 
Adjacency matrixA โˆˆ {0,1}^{Nร—N}Who is connected to whomย ย 
Node labely_vPaper topicย ย 
Graph labely_GMolecule toxicityย ย 

Graphs are the natural language of relational data. GNNs are the deep learning architectures that speak it.

References

You May Also Enjoy

Open Problems and Future Directions in Sheaf Neural Networks

5 minute read

Published:

Sheaf Neural Networks are a young field with many open research problems. This post surveys the most important unsolved questions: scalability to million-node graphs, stochastic sheaves for uncertainty quantification, sheaf autoencoders for generative models, connections to persistent homology, and unification with other topological deep learning frameworks.

Sheaf GNNs for Molecular Property Prediction

7 minute read

Published:

Molecular graphs are naturally heterophilic โ€” atoms of different types bonded together โ€” and have rich geometric structure (bond angles, torsion angles). Sheaf GNNs can encode this structure via restriction maps that represent the relational geometry between bonded atoms. This post explores how sheaf theory applies to molecular property prediction.

Sheaf GNNs for Heterophilic Node Classification: Benchmarks and Results

6 minute read

Published:

A systematic comparison of sheaf GNNs against baselines on standard heterophilic node classification benchmarks. Which datasets benefit most from sheaf structure? How does stalk dimension d affect performance? When do sheaves win โ€” and when donโ€™t they?

Sheaves Meet Attention: Transformer-Inspired Sheaf Models

6 minute read

Published:

Graph Transformers use global attention to capture long-range dependencies that local message passing misses. Sheaf Transformers combine sheaf-based local aggregation (with learnable relational geometry) with global attention (for long-range dependencies). This post surveys the design space of sheaf-augmented attention models.