gen Graph<N, E> {
has nodes: Vec<N>
has edges: Vec<Tuple<u64, u64, E>>
has adjacency: SparseMatrix<f64>
has node_count: u64 = nodes.length
has edge_count: u64 = edges.length
rule valid_edges {
forall edge in this.edges.
edge.0 < this.nodes.length && edge.1 < this.nodes.length
}
rule no_self_loops {
forall edge in this.edges.
edge.0 != edge.1
}
law undirected_symmetry {
forall (i, j, e) in this.edges.
(j, i, e) in this.edges
}
fun neighbors(node_idx: u64) -> Vec<u64> {
return this.edges
.filter(|edge| edge.0 == node_idx)
.map(|edge| edge.1)
}
fun degree(node_idx: u64) -> u64 {
return this.neighbors(node_idx).length
}
fun has_edge(src: u64, dst: u64) -> bool {
return this.edges.any(|edge| edge.0 == src && edge.1 == dst)
}
fun get_node(idx: u64) -> N {
return this.nodes[idx]
}
fun get_edge_data(src: u64, dst: u64) -> Option<E> {
return this.edges
.find(|edge| edge.0 == src && edge.1 == dst)
.map(|edge| edge.2)
}
// Apply permutation to node ordering (S_n group action)
// For permutation π: new_graph = π · graph
// - Node features are reordered: new_nodes[π(i)] = old_nodes[i]
// - Edge indices are remapped: (a, b) -> (π(a), π(b))
fun permute_nodes(perm: PermutationGroup<node_count>) -> Graph<N, E> {
// Reorder nodes: position π(i) gets the feature from position i
let new_nodes = (0..this.node_count).map(|i| {
let source_idx = perm.inverse_at(i)
this.nodes[source_idx]
}).collect()
// Remap edge indices through the permutation
let new_edges = this.edges.map(|edge| {
let new_src = perm.perm[edge.0]
let new_dst = perm.perm[edge.1]
(new_src, new_dst, edge.2)
}).collect()
// Rebuild adjacency matrix with permuted indices
let new_adjacency = this.build_adjacency(new_edges)
return Graph {
nodes: new_nodes,
edges: new_edges,
adjacency: new_adjacency,
node_count: this.node_count,
edge_count: this.edge_count
}
}
// Build adjacency matrix from edge list
fun build_adjacency(edges: Vec<Tuple<u64, u64, E>>) -> SparseMatrix<f64> {
let adj = SparseMatrix::zeros(this.node_count, this.node_count)
for edge in edges {
adj.set(edge.0, edge.1, 1.0)
}
return adj
}
// Check if two graphs have same structure
fun same_structure(other: Graph<N, E>) -> bool {
return this.node_count == other.node_count && this.edge_count == other.edge_count
}
}
docs {
Graph<N, E> models a graph domain where N is the node feature type and
E is the edge feature type. This is a fundamental structure for Geometric
Deep Learning architectures operating on relational data.
This gen represents the Graph domain in the GDL three-pillar ontology,
enabling permutation-equivariant neural network architectures like
Graph Neural Networks (GNNs) and Message Passing Neural Networks (MPNNs).
Properties:
- nodes: List of node features of type N (e.g., atom embeddings)
- edges: List of (source, target, edge_data) tuples
- adjacency: Sparse adjacency matrix for efficient graph operations
- node_count: Number of nodes (derived)
- edge_count: Number of edges (derived)
Edge Validity Constraint:
The valid_edges rule ensures all edge indices are within bounds,
preventing invalid node references. This is critical for memory safety
and guarantees well-formed graph structure.
No Self-Loops Constraint:
The no_self_loops rule prevents edges from a node to itself,
which is standard for many graph learning tasks. This can be relaxed
for domains where self-loops are meaningful.
Undirected Symmetry Law:
The undirected_symmetry law declares that for every edge (i, j, e),
the reverse edge (j, i, e) must also exist. This law encodes the
mathematical property of undirected graphs and enables symmetric
message passing in GNN architectures.
Inherent Symmetry:
Graph domains have inherent Permutation Group S_n symmetry.
Any reordering of node indices that preserves edge connectivity
represents the same graph. Architectures must be permutation-equivariant
to respect this structure.
Permutation Group Action (permute_nodes):
The permute_nodes(perm) method implements the S_n group action on graphs.
For a permutation π and graph G = (V, E):
- Node reordering: new_nodes[π(i)] = old_nodes[i]
- Edge remapping: (a, b, e) → (π(a), π(b), e)
This action satisfies the group action axioms:
- Identity: permute_nodes(identity) = this
- Compatibility: permute_nodes(π₁ ∘ π₂) = permute_nodes(π₁).permute_nodes(π₂)
The permute_nodes method enables verification of the equivariance law
for GNN architectures: f(π · G) = π · f(G)
Common Use Cases:
- Molecular graphs: Graph<AtomFeatures, BondFeatures>
- Social networks: Graph<UserEmbedding, RelationType>
- Knowledge graphs: Graph<EntityEmbedding, RelationEmbedding>
- Citation networks: Graph<PaperEmbedding, CitationType>
Related Genes:
- HeteroGraph<N, E>: Heterogeneous graphs with multiple node/edge types
- DirectedGraph<N, E>: Directed graphs without symmetry law
- TemporalGraph<N, E, T>: Graphs with temporal edge attributes
GDL Blueprint Reference:
Domain type in the three-pillar ontology: Domain (Omega) -> Graph
Inherent symmetry group: Permutation Group S_n
}