calibrax.metrics.functional.graph

Graph distance metrics for comparing graph structures and computing within-graph distances. Between-graph metrics (spectral distance, approximate graph edit distance) compare two adjacency matrices. Within-graph metrics (resistance distance, shortest path distance) operate on a single graph.

Graph distance metrics -- pure JAX linear algebra on adjacency matrices.

Covers four graph distance categories from the Erlangen Program perspective:

Between-graph distances (compare two graphs): - spectral_distance: Laplacian eigenvalue spectrum comparison - graph_edit_distance_approx: Spectral relaxation of NP-hard GED

Within-graph distances (distance matrix for a single graph): - resistance_distance: Effective electrical resistance between nodes - shortest_path_distance: Floyd-Warshall all-pairs shortest paths

All metrics operate on adjacency matrices (square arrays) or graph Laplacians. No external graph libraries required -- pure JAX.

Registered with domain="graph".

spectral_distance(adj_a: Any, adj_b: Any, *, num_eigenvalues: int | None = None) -> Any

Distance between two graphs based on Laplacian eigenvalue spectra.

Computes ||lambda(L_G) - lambda(L_H)||_2 where L = D - A is the graph Laplacian. Invariant to node permutation (graph isomorphism invariant). Complexity: O(n^3) for eigendecomposition.

Parameters:

Name	Type	Description	Default
adj_a	Any	Adjacency matrix of first graph, shape (n, n).	required
adj_b	Any	Adjacency matrix of second graph, shape (m, m).	required
num_eigenvalues	int | None	Number of smallest eigenvalues to compare. If None, uses all eigenvalues.	None

Returns:

Type	Description
Any	L2 norm of the eigenvalue spectrum difference. Lower is better.
Any	0.0 for identical graphs.

Examples:

>>> import jax.numpy as jnp
>>> adj = jnp.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype=jnp.float32)
>>> spectral_distance(adj, adj)
0.0

resistance_distance(adjacency_matrix: Any) -> jnp.ndarray

Resistance distance matrix for a graph.

The resistance distance between nodes i and j is the effective resistance in the electrical network where each edge is a unit resistor: Omega_{ij} = L^+_{ii} + L^+_{jj} - 2*L^+_{ij} where L^+ is the Moore-Penrose pseudoinverse of the graph Laplacian.

A true metric on graph vertices satisfying all metric space axioms. Captures more topological information than shortest path -- nodes connected by many paths have lower resistance distance.

Complexity: O(n^3) for pseudoinverse computation.

Parameters:

Name	Type	Description	Default
adjacency_matrix	Any	Square adjacency matrix, shape (n, n).	required

Returns:

Type	Description
ndarray	Resistance distance matrix, shape (n, n). Symmetric with zero diagonal.

Examples:

>>> import jax.numpy as jnp
>>> adj = jnp.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype=jnp.float32)
>>> omega = resistance_distance(adj)
>>> float(omega[0, 2])  # Path graph: endpoints are 2 apart
2.0

shortest_path_distance(adjacency_matrix: Any, *, weighted: bool = False) -> jnp.ndarray

All-pairs shortest path distances via Floyd-Warshall.

JIT-compatible via jax.lax.fori_loop with fixed trip count. NOT differentiable because jnp.minimum has zero gradients almost everywhere.

Complexity: O(n^3). Suitable for small graphs (n < 1000).

Parameters:

Name	Type	Description	Default
adjacency_matrix	Any	Square adjacency matrix, shape (n, n). Positive values indicate edges. Zero means no edge.	required
weighted	bool	If True, uses edge weights. If False, treats all nonzero entries as unit edges.	False

Returns:

Type	Description
ndarray	Shortest path distance matrix, shape (n, n). Unreachable
ndarray	pairs have value jnp.inf.

Examples:

>>> import jax.numpy as jnp
>>> adj = jnp.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype=jnp.float32)
>>> dist = shortest_path_distance(adj)
>>> float(dist[0, 2])
2.0

graph_edit_distance_approx(adj_a: Any, adj_b: Any) -> Any

Approximate graph edit distance via spectral relaxation.

The exact GED is NP-hard. This spectral approximation computes: (1) eigendecompositions of both adjacency matrices, (2) squared eigenvalue difference, and (3) 2-hop structural difference via Frobenius norm.

Provides a lower bound on true GED in polynomial time. NOT a true metric (approximation may violate triangle inequality).

Complexity: O(n^3) for eigendecomposition.

Parameters:

Name	Type	Description	Default
adj_a	Any	Adjacency matrix of first graph, shape (n, n).	required
adj_b	Any	Adjacency matrix of second graph, shape (n, n).	required

Returns:

Type	Description
Any	Approximate graph edit distance. Lower is better.
Any	0.0 for identical graphs.

Examples:

>>> import jax.numpy as jnp
>>> adj = jnp.array([[0, 1, 0], [1, 0, 1], [0, 1, 0]], dtype=jnp.float32)
>>> graph_edit_distance_approx(adj, adj)
0.0