2. Graph representation essentials

Converting a finite element mesh into graph data is not a single transformation but a modeling decision. The same tetrahedral mesh can yield several valid graphs that differ in what a node represents, what an edge encodes, and which relationships are made explicit. Before writing any conversion code, you must fix these choices, because they determine memory footprint, the receptive field of a graph neural network (GNN), and whether the resulting dataset can be batched efficiently. This section establishes the vocabulary and the design space: nodes, edges, adjacency structures, and the graph families that appear most often in mesh-learning pipelines.

Nodes: Choosing the Graph's Atomic Unit

In a mesh, the natural candidates for graph nodes are mesh vertices, but that is only one option. Three conventions dominate practice:

• Vertex-centered graphs. Each mesh node becomes a graph node. For a linear tetrahedral mesh with N vertices and M elements, the node count equals N. Node features typically include coordinates, and optionally boundary flags, material region IDs, or solution fields such as displacement or temperature.
• Element-centered (dual) graphs. Each finite element becomes a graph node, and two elements are connected if they share a facet. This is the dual graph of the mesh. It is attractive when the target quantity is element-wise, for example per-element stress or per-cell permeability.
• Hybrid or bipartite graphs. Vertices and elements are both retained as distinct node types, with incidence edges linking each element to its vertices. This preserves full topological information and is common in higher-order GNN architectures, at the cost of roughly doubling node count.

A practical rule: if the prediction target lives on vertices (nodal displacement, surface pressure), start vertex-centered; if it lives on elements (stress tensors, cell labels), start element-centered; if you need both or need to learn incidence-aware operators, use a bipartite formulation. Record the choice explicitly in the dataset schema, because downstream code that assumes vertex-centered indexing will silently produce wrong neighborhoods otherwise.

Edges and Edge Features

Edges encode which nodes may exchange information. For a vertex-centered graph derived from a tetrahedral mesh, the standard construction connects every pair of vertices that share an element. In a linear tetrahedron, all four vertices are mutually connected, so each element contributes six undirected edges. For a hexahedral element, the eight vertices yield 28 pairwise edges if you connect all pairs, but many pipelines instead connect only the 12 element edges to keep the graph sparse and geometrically faithful.

This is a genuine design fork. The clique construction (all vertex pairs within an element) guarantees that any two vertices influencing the same element are one hop apart, which helps message passing capture element-level coupling. The skeleton construction (only true mesh edges) yields a sparser graph whose edges correspond to physical element edges, which is preferable when you want the graph to mirror the actual stiffness connectivity. Document which rule you used; the two graphs have different degree distributions and different GNN behavior.

Edge features are where mesh graphs gain much of their expressive power. Useful attributes include the edge vector in physical coordinates, its length, and for curved or anisotropic meshes the direction cosines. For element-centered dual graphs, the shared facet area and facet normal are natural edge features. A minimal but effective feature set for a vertex-centered graph is:

edge_features[e] = [dx, dy, dz, ||d||]   # d = x_j - x_i, in mesh units
node_features[v] = [x, y, z, boundary_flag, region_id]

Keep coordinates in a consistent unit system and state it. Mixing millimeters and meters across a dataset is a common and hard-to-diagnose source of poor generalization.

Adjacency: Storage Formats and Their Trade-offs

Adjacency describes the connectivity independent of features. Three representations matter in practice:

For a mesh with N = 100,000 vertices and average degree 14, a dense adjacency matrix would require 10¹⁰ entries — clearly infeasible. The edge list needs about 2.8 million directed entries (each undirected edge stored twice for message passing in both directions), and CSR stores the same information with better locality. In PyTorch Geometric, the canonical form is edge_index of shape [2, E] with both directions present, plus optional edge_attr of shape [E, F]. Always verify that the graph is symmetric when the underlying relation is undirected:

import torch
src, dst = edge_index
assert torch.equal(
    torch.sort(src * N + dst).values,
    torch.sort(dst * N + src).values
), "edge_index is not symmetric"

This assertion catches a frequent bug: building edges from element connectivity without adding the reverse direction, which silently halves the receptive field.

Graph Types Relevant to Mesh Data

Mesh-derived graphs are usually undirected and homogeneous (one node type, one edge type), but several variants appear as pipelines mature:

• k-nearest-neighbor (kNN) graphs built from vertex coordinates. Useful when the mesh is unstructured or when you want a geometry-driven graph independent of element topology. Note that a kNN graph is not the same as the mesh connectivity graph and may connect vertices across element boundaries.
• Radius graphs, connecting all vertices within a distance r. Common for point-cloud-like mesh data and for particle methods.
• Heterogeneous graphs with separate vertex and element node types and incidence edges, as in the bipartite formulation above.
• Multilevel or hierarchical graphs produced by mesh coarsening, where each level is a graph and inter-level edges encode prolongation. These support multigrid-style GNNs.
• Directed graphs for special cases such as flow networks on mesh edges, where direction carries physical meaning.

The figure below summarizes how a single tetrahedral mesh maps onto the three most common graph constructions and what each preserves.

From Construction to a Verifiable Dataset

Once the graph type is fixed, the conversion should be validated against invariants that are cheap to compute and catch most errors. For a vertex-centered graph built from a tetrahedral mesh, check the following on a small sample before scaling up:

1. Node count equals the number of mesh vertices, and node indices are a permutation of 0..N-1 with no gaps.
2. Edge count matches the expected value. For a mesh of M linear tets with no duplicate elements, the clique rule gives at most 6M undirected edges before deduplication; after deduplication the count is lower wherever elements share faces.
3. Symmetry of edge_index, as shown above.
4. No self-loops unless intentionally added; a self-loop from a degenerate element usually signals a malformed connectivity array.
5. Degree sanity: interior vertices in a well-shaped tet mesh typically have degree between 8 and 20; isolated vertices (degree 0) indicate orphan nodes that will receive no messages.

A typical failure symptom is a GNN that trains but predicts nearly constant outputs on interior nodes while fitting boundary nodes well. In a vertex-centered graph this often traces to missing reverse edges or to a clique construction that was applied per element without deduplication, inflating edge weights unevenly. Printing the degree histogram and the fraction of symmetric edges resolves the diagnosis quickly.

With these conventions settled, the mesh-to-graph conversion becomes a deterministic, testable procedure rather than an ad hoc script, and the graph type can be chosen to match the prediction target instead of being inherited by accident.