Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Structural vs Positional Encodings in Graphs

4 minute read

Published:

TL;DR: Positional encoding: "node v is at position (x,y) in graph space" — globally unique identifiers. Structural encoding: "node v is a hub/leaf/bridge" — role descriptors independent of global position. Two nodes can have the same structural role in different positions, or the same position with different roles. Both types of information matter for different tasks.

The Conceptual Distinction

Positional encoding (PE): assigns each node a unique identifier that reflects its global location in the graph. If the graph has a natural linear or spatial ordering (like a sequence or a molecular geometry), PEs capture that.

Analogy: your home address. It uniquely identifies your location in the city.

Structural encoding (SE): assigns each node a descriptor that reflects its local structural role, regardless of where it is globally. Hub nodes (many connections) get one encoding; leaf nodes (one connection) get another.

Analogy: your job title (engineer, manager, intern). Two engineers at different companies have the same structural role but different positions.

Examples

Same position, different structure:
Two molecules where atom A is always the central carbon, but one has 3 bonds (sp2 hybridised) and another has 4 (sp3). Their global “position” (central atom) is the same, but their structural role differs.

Same structure, different position:
In a path graph A-B-C-D-E, nodes B and D both have degree 2. Their structural roles are identical (leaf-of-interior), but they are at different global positions (2nd vs 4th from the start).

Key test: Would two nodes in two *different* graphs (or two copies of the same graph) deserve the same encoding? If yes → structural. If no → positional (position only makes sense within one fixed graph).

Classification of Common Encodings

EncodingTypeWhat two nodes with same encoding share
Laplacian eigenvectorsPositionalSimilar global position in graph space
DegreeStructuralSame number of connections
RWPE (return probabilities)StructuralSame local cycle/clique structure
Shortest-path from anchor nodesPositionalSame distance from chosen landmarks
Clustering coefficientStructuralSame fraction of triangles among neighbours
Orbit type (from automorphism)StructuralSymmetric role under graph isomorphism

When Each Matters

Use positional encodings when:

  • Node identity matters (e.g., tracking specific atoms in a molecule simulation)
  • Task depends on absolute global position (e.g., node ID in a knowledge graph)
  • Model needs to distinguish globally symmetric nodes (two equivalent atoms that have different contexts in the molecule)

Use structural encodings when:

  • The task is about structural roles (hub detection, bridge node classification)
  • You want to transfer across graphs (same structural role should mean same representation)
  • Isomorphic subgraphs should be treated identically

Use both when:

  • You want maximum expressive power (GPS uses RWPE — structural — plus LapPE — positional)
  • Different task components require different information

Equivariance Considerations

Positional encodings break node permutation equivariance — the representation of node v now depends on its global position, which changes if you relabel nodes.

Structural encodings preserve permutation equivariance up to isomorphism — relabelling nodes permutes structural encodings accordingly. This is the “right” property for structural encodings.

SignNet and similar approaches attempt to make LapPE (which is technically positional but has sign ambiguity) equivariant by handling sign symmetries correctly.

Summary

 PositionalStructural
UniquenessGlobally uniqueShared across isomorphic roles
Transferable across graphsNo (each graph has its own coordinate system)Yes (same role in different graphs)
Permutation equivariantNo (depends on labelling)Yes (up to isomorphism)
ExamplesLapPE, SPD, anchor distancesRWPE, degree, orbits
Best forTasks needing unique node IDsTasks needing role classification

The distinction is not academic — choosing the wrong type of encoding is a common source of suboptimal performance in GNN and Graph Transformer design.

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.