{"ID":2850182,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.23646","arxiv_id":"2510.23646","title":"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}=\\mathbf{1}!\\left[\\sum{t=1}^{k} A^t\u003e0\\right]-\\mathbf{1}!\\left[\\sum_{t=1}^{k-1} A^t\u003e0\\right]$ (shortest-path distance exactly $k$). Guarantees. (i) Permutation invariance: $d_{\\mathrm{HGM}}(π(G),π(H))=d_{\\mathrm{HGM}}(G,H)$ for all vertex relabelings $π$; (ii) the tensor Hamming distance $d_{\\mathrm{HGM}}(G,H):=|,\\mathcal{B}G-\\mathcal{B}H,|{1}=\\sum{i,j,k}\\mathbf{1}!\\big[(\\mathcal{B}G){ijk}\\neq(\\mathcal{B}H){ijk}\\big]$ 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.","short_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...","url_abs":"https://arxiv.org/abs/2510.23646","url_pdf":"https://arxiv.org/pdf/2510.23646v1","authors":"[\"R. Scott Johnson\"]","published":"2025-10-25T00:51:11Z","proceeding":"cs.SI","tasks":"[\"cs.SI\"]","methods":"[]","has_code":false}