Hamming Graph Metrics: A Multi-Scale Framework for Structural Redundancy and Uniqueness in Graphs

Abstract

Traditional graph centrality measures effectively quantify node importance but fail to capture the structural uniqueness of multi-scale connectivity patterns -- critical for understanding network resilience and function. This paper introduces Hamming Graph Metrics (HGM), a framework that represents a graph by its exact-$k$ reachability tensor $\mathcal{B}G\in {0,1}^{N\times N\times D}$ with slices $(\mathcal{B}G):,:,1=A$ and, for $k\ge 2$, $(\mathcal{B}G):,:,k=1!\left[\sum {t=1}^k{A}^t>0\right]-1!\left[{\sum }_{t=1}^{k-1}{A}^t>0\right]$ (shortest-path distance exactly $k$). Guarantees. (i) Permutation invariance: $d_{\mathrm{HGM}}(\pi (G),\pi (H))=d_{\mathrm{HGM}}(G,H)$ for all vertex relabelings $\pi$; (ii) the tensor Hamming distance $d_{\mathrm{HGM}}(G,H):=|,\mathcal{B}G-\mathcal{B}H,|1=\sum i,j,k1![(\mathcal{B}G)ijk\ne (\mathcal{B}H)ijk]$ is a true metric on labeled graphs; and (iii) Lipschitz stability to edge perturbations with explicit degree-dependent constants (see "Graph-to-Graph Comparison" $\to$ "Tensor Hamming metric"; "Stability to edge perturbations"; Appendix A). We develop: (1) per-scale spectral analysis via classical MDS on double-centered Hamming matrices $D^{(k)}$, yielding spectral coordinates and explained variances; (2) summary statistics for node-wise and graph-level structural dissimilarity; (3) graph-to-graph comparison via the metric above; and (4) analytic properties including extremal characterizations, multi-scale limits, and stability bounds.