mlsanityData to 7 Oct 2026

Omega-N: Interpretable Structural Node Descriptors and Their Applicability Domain

arXiv 2609.01633 ↗First posted 21 Aug 2026cs.SI cs.LG physics.soc-phcited by 0

Not on the map. Why?

Abstract (arXiv)

A composite structural index summarises a network in one number, and for a triangle-based index it is spectrally redundant: Tr(A^3) is the third moment of the adjacency spectrum. The non-redundant content sits one level down, in diag(A^3), which depends on eigenvectors and is not spectrally determined. A corollary in the theory paper predicted that the global scalar should tie sharpened spectral baselines rather than beat them, while the node-wise attribution should do better where the number of structural epicentres is unknown. We construct Omega-N by localizing each of the four factors. The direct localization is badly conditioned; two corrections from published practice fix it, a configuration-null excess per factor and a personalized-PageRank neighbourhood at several scales, giving ten interpretable features per node, with no attributes, training or embeddings. Against a recursive feature engine at five levels of recursion, Omega-N wins on three and ties on two of the six in-domain evaluations, the sixth a declared null where every arm returns chance, with ten features against its 28 to 252 before pruning. Two statistics from the graph and labels, not from performance, partition the eight benchmarks without error, and the two they exclude are the two on which it loses. The strongest application is drug-target prioritisation on protein interaction networks: +0.032 to +0.103 AUPRC over a six-feature centrality battery and +0.084 to +0.208 over the four-feature one, across three constructions, replicated on an independent AP-MS network and label source (degree-matched: +0.0723 on STRING, +0.0560 on BioPlex, p=0.00195). Adding Omega-N to centralities plus Node2Vec changes nothing. The claim is narrow and it is the point: ten named features, computed without training, match or beat hand-crafted centralities and a recursive engine, and do not touch learned representations.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 40 references that are in the map. First posted on arXiv 21 Aug 2026.

Builds on

17 of 40 references.

References · 17

  1. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  2. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  3. 2017struc2vec: Learning Node Representations from Structural Identitycited by 214
  4. 2017Learning Structural Node Embeddings Via Diffusion Waveletscited by 97
  5. 2023GADBench: Revisiting and Benchmarking Supervised Graph Anomaly Detectioncited by 57
  6. 2023Over-Squashing in Graph Neural Networks: A Comprehensive surveycited by 23
  7. 2024Graph Rewiring in GNNs to Mitigate Over-Squashing and Over-Smoothing: A Surveycited by 8
  8. 2017Multiscale mixing patterns in networkscited by 7
  9. 2019RiWalk: Fast Structural Node Embedding via Role Identificationcited by 7
  10. 2023Structural Node Embeddings with Homomorphism Countscited by 3
  11. 2022Network compression with configuration models and the minimum description lengthcited by 2
  12. 2023Proper network randomization is key to assessing social balancecited by 2
5 more
  1. 2022Digraphwave: Scalable Extraction of Structural Node Embeddings via Diffusion on Directed Graphscited by 1
  2. 2023Unsupervised Framework for Evaluating and Explaining Structural Node Embeddings of Graphscited by 1
  3. 2024RAGFormer: Learning Semantic Attributes and Topological Structure for Fraud Detectioncited by 1
  4. 2025Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metricscited by 1
  5. 2026Measuring Structure in Graph Benchmark Datasets Using Graph Invariantscited by 1

Built on by

Not cited yet.