PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Alberto Acedo

arXiv:2609.01633v2cs.SIcs.LGphysics.soc-phq-bio.MN

TL;DR

The paper tests whether node-wise localization can recover non-redundant structural information beyond a global spectral scalar, especially when structural epicentres are unknown. It replaces a degenerate degree-variance contribution and evaluates the resulting descriptor under domain conditions and applications.

  • Problem

    The theory predicts that the global scalar should tie sharpened spectral baselines, while node-wise attribution should help when the number of structural epicentres is unknown; testing this requires a well-behaved localization and evidence that its coordinates are not redundant.

  • Method

    Omega-N replaces the literal degree-variance contribution with a neighborhood-heterogeneity quantity, using a localization designed to avoid the original factor’s degeneracy.

  • Results

    Omega-N beats degree, the centrality battery and Guimerà-Amaral on all three protein-interaction graphs, with margins of 0.066, 0.091 and 0.049, while the margin over the battery remains between +0.032 and +0.103 across constructions.

  • Takeaways & Limitations

    Two graph-and-label statistics define a prospective applicability rule: degree structure and degree–label dependence identify settings where the descriptor is appropriate or where degree already answers the task.

  • Takeaways & Limitations

    The applicability rule was fitted on eight networks and has not been tested out of sample; approved-target status is only a proxy for druggability and label sources retain study bias.

Abstract

from arXiv · show

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.

Changes in version 2

Version 2 fixes four implementation defects, regenerates the affected analyses, and reports that the corrections improve figures without changing any verdict.

  • Corrections: Four released-code defects were fixed, including a non-convergent spectral eigensolver, incorrect connected-component handling, an outdated drug-target label, and an unmeasured applicability-table rival.The corrected eigensolver is deterministic and matches shift-invert Lanczos to seven digits.
  • Effect on conclusions: All corrections move the figures upward and none changes a verdict.The regenerated tables are in Sections 4.1 and 4.2.
  • Effect on conclusions: The two remaining air-traffic ties retain their version-1 figures and are therefore conservative.One network variant was withdrawn, and library versions are now pinned.

1. Introduction

The introduction argues that Omega-N should be evaluated as a node-wise structural descriptor rather than as another redundant global scalar, while positioning its interpretability against recursive and learned alternatives.

  • Motivation: The global index is the third adjacency-spectrum moment, whereas its node-wise triangle decomposition depends on eigenvectors and is not spectrally determined.Cospectral graphs can have different per-node triangle counts.
  • Motivation: The theory predicts that the global scalar should tie sharpened spectral baselines, while node-wise attribution should help when the number of structural epicentres is unknown.The paper tests this prediction through numerical localization, coordinate distinctness, and applicability conditions.
  • Related work: Prior work spans hand-crafted node roles, recursive feature engines, structural embeddings, graph-wavelet methods, and multiscale localizations.Omega-N is situated within these existing approaches rather than presented as the first node-wise structural descriptor.
  • Trade-off: Hand-built descriptors trade ten interpretable, training-free coordinates against learned representations that may perform better but explain less.The paper measures where this trade stops paying and reports that it stops against learned representations.
  • Additional contribution: Because spectral gap is spectral but per-node triangle counts are not, the paper constructs gap-matched graphs to separate global spectral effects from local triadic organisation.This construction addresses a stated need in whole-brain modelling without claiming the descriptor solves that application.

2. The descriptor

Omega-N localizes four structural factors into interpretable node coordinates, replaces unstable components where necessary, and evaluates whether those coordinates add information beyond degree, curvature, and centrality baselines.

  • 2.1 Definition of the descriptor: Omega-N assigns each node four base coordinates, including degree share, configuration-null triadic excess, neighbourhood dispersion, and spectral energy.The spectral-energy terms sum to λ2 = 1/M rather than M, determining the local factor’s inverse orientation.
  • 2.1 Definition of the descriptor: The ten-feature descriptor combines the base coordinates with personalized-PageRank smoothing at α ∈ {0.5, 0.9}.The construction gives 4 + 3 × 2 = 10 features per node.
  • 2.1 Definition of the descriptor: The literal degree-variance contribution is replaced because its per-node share vanishes at the mean degree, while the replacement measures neighbourhood heterogeneity without that degeneracy.The descriptor contributes three non-degree quantities; degree is retained for comparability with degree-based rivals.
  • 2.2 Conditioning failures of the direct localization: Naive localization is ill-conditioned: the degree-variance share vanishes at mean degree and the clustering share is zero on triangle-free nodes.On seven graphs, one Watts–Strogatz graph had 36 of 62 degenerate nodes, while 17 of 77 Les Misérables nodes were triangle-free.
  • 2.2 Conditioning failures of the direct localization: The exact aggregation identity uses log arithmetic-to-geometric gaps and shows that the correct aggregate is a geometric mean, not an arithmetic mean.It was numerically verified to 4e-16 on six graphs, but the descriptor later abandons the multiplicative composition and uses a feature block.
  • 2.4 Independence from discrete Ricci curvature: The triadic-excess coordinate is largely independent of Ollivier-Ricci curvature, with |ρ| ≤ 0.18 on seven of eight networks, but reaches +0.460 on sparse roman-empire.The exception shows that independence is a regime-dependent property rather than a universal one.
  • 2.5 Predictive validity of the non-degree coordinates: Omega-N beats degree, the centrality battery, and Guimerà–Amaral on all three Twitch graphs, while their union performs better still.The reported margins over the battery are 0.066, 0.091, and 0.049; the evaluation uses identical five-fold splits across feature sets.

3. Experimental design

The evaluation spans node classification, systemic-risk attribution, and drug-target prioritisation, using field-specific graphs, labels, rivals, and protocols. Shared controls standardise connected components, classifiers, and folds, while additional checks address graph construction, labels, matching, and implementation stability.

  • The descriptor is evaluated in node classification, systemic-risk attribution, and drug-target prioritisation because their graph-construction processes differ.
  • Every network uses its largest connected component, and every arm within a field uses the same classifier and folds.This avoids spectral degeneracy from disconnected components and makes feature comparisons use matched evaluation procedures.
  • Node classification: The node-classification evaluation uses eight benchmark networks, ten official heterophilous splits, and three air-traffic graphs with activity-quartile labels.Minesweeper is a declared null because its labels are independent of structure, so every arm should return chance.
  • Node classification: The node-classification rivals are a four-feature centrality battery, ReFeX at four recursion depths with 28 to 252 features, and GraphWave.GraphWave uses declared approximation settings, including degree-30 Chebyshev polynomials, two scales, a 25-point grid, and fixed subsampling on the largest graphs.
  • Systemic-risk attribution: The financial evaluation predicts forward marginal expected shortfall from correlation graphs, comparing the descriptor with past MES, system beta, and graph strength.The protocol uses partial rank correlation over 19 non-overlapping windows, a sign test, and a block bootstrap over 234 overlapping windows.
  • Drug-target prioritisation: Drug-target prioritisation uses three protein-network constructions, including two progressively thresholded STRING graphs and an independent BioPlex graph.The constructions separate curation effects from experimental-network effects; HuRI was excluded because 58.7% of nodes lack triangles.
  • Drug-target prioritisation: The drug-target label is approved-drug-target status from Open Targets, mapped to STRING and BioPlex identifiers, with replication using an independent network and label source.The comparison uses a six-feature centrality battery and a centralities-plus-Node2Vec pipeline, with AUPRC primary because positives comprise 5.5% to 9.3% of nodes.

4. Results

Omega-N outperforms the six-feature centrality battery across three protein-network constructions, remains robust to bias and cutoff controls, and matches or narrowly exceeds recursive feature engineering within its applicability domain. Its gains disappear against learned representations, while graph-and-label statistics correctly identify the excluded failure cases.

  • Drug-target prioritisation: The margin survives removal of curation across three networks, although absolute performance declines with curation.The three constructions comprise a reference network, a clean no-text-mining variant, and an independent BioPlex replicate.
  • Drug-target prioritisation: +0.0723 AUPRC on combined STRING and +0.0560 on BioPlex over the six-feature battery under degree matching.Both results were positive in all ten repetitions with Wilcoxon p = 0.00195.
  • Drug-target prioritisation: Bias controls and confidence-cutoff sweeps preserve Omega-N’s advantage over centrality baselines.Across cutoffs 400–900, the AUPRC margin remains positive from +0.085 to +0.066.
  • Drug-target prioritisation: Adding Omega-N to centralities plus Node2Vec changes nothing, and Node2Vec alone already outperforms Omega-N.Across five seeds, the mean difference is +0.0014 AUPRC, positive on three seeds and negative on two, with Wilcoxon p = 0.31.
  • Efficiency: The reported runtime advantage over original GraphWave is one to two orders of magnitude, depending on the graph.Measured examples are 0.2 s versus 4.7 s on usa-airports and 1 s versus 145 s on minesweeper; the comparison does not address scalable GraphWave.
  • Node classification and applicability domain: The applicability rule separates eight networks without error using mean degree and degree–label mutual information, excluding the two losses.The rule is mean degree at least 4 and I(k;y)/H(y) at most 0.5; within the domain, Omega-N records three wins, two ties, and one chance-level null.
  • Node classification and applicability domain: Omega-N reaches the same place as recursive feature engineering with ten interpretable coordinates instead of up to 252 features before pruning.The wins are narrow: 0.795 versus 0.770 on tolokers, 0.470 versus 0.459 on amazon-ratings, and 0.693 versus 0.684 on questions.

5. Discussion

Omega-N’s strongest evidence is conditional: it is effective on dense protein networks with weak attributes and labels not driven by connectivity, while its failures occur outside those conditions. The discussion also identifies controlled graph constructions where node-wise triadic structure can be separated from spectral gap, without claiming downstream application results.

  • 5.1 Conditions underlying the positive result: Protein networks provide the descriptor’s strongest setting because they are dense, have weak attributes, and drug-target labels are not functions of connectivity.Mean degree is 17–30, and degree is reported as a weak predictor of target status.
  • 5.1 Conditions underlying the positive result: +0.032 to +0.103 AUPRC separates Omega-N from the six-feature battery across protein-network constructions.The margin remains in this range while the centrality battery varies from 0.14 to 0.48 across constructions.
  • 5.2 Comparison with recursive feature engineering: Three narrow wins and two ties against ReFeX support ten named coordinates reaching comparable accuracy, not superiority over recursive feature engineering.ReFeX uses 28–252 features before pruning, whereas Omega-N uses ten.
  • 5.3 The two out-of-domain results: Both benchmark losses occur where degree-label dependence or insufficient triadic structure violates the descriptor’s intended conditions.brazil-airports has high degree-label information, while roman-empire has mean degree 2.9 and chain-like topology.
  • 5.4 Conditions for use: The descriptor is intended for dense co-occurrence graphs with weak attributes and targets not determined by connectivity; when learned representations are available and prediction is the sole criterion, embeddings are preferred.The paper explicitly states no claim for weighted gene co-expression analysis and identifies a confound when construction parameters jointly set density and local structure.
  • 5.5 Separating spectral gap from local structure: Matching spectral gap while varying per-node triadic structure yields a controlled construction for testing whether downstream effects arise from the gap or local organisation.In 600 pruned k-regular graphs, spectral gap explains 62% of the remaining variation in per-node triadic excess and 19% for clustering coefficient.
  • 5.5 Separating spectral gap from local structure: The paper reports this brain-network construction as a methodological test, not evidence that model fit changes at fixed spectral gap.Such a claim requires testing inside the whole-brain model with empirical data and the interference measure.
  • 5.6 Rewiring and attribution: The same gap-versus-triangles construction could separate spectral and curvature-based rewiring effects in over-squashing studies.The proposed comparison rewires graphs to a target gap through routes differing in local triadic organisation, then compares downstream accuracy.

6. Limitations

The applicability rule is promising but not yet validated out of sample, and the biological label and excluded network resource impose important scope boundaries.

  • Applicability rule: The applicability rule separates the eight evaluated networks without error but was formulated after observing the two losses and has not been tested prospectively out of sample.Its two statistics are independent of descriptor performance, but fitting two thresholds on eight networks leaves room to fit.
  • Labels and network scope: Approved-target status is only a proxy for druggability, and both label sources carry study bias despite three controls.Excluding HuRI for lacking triadic substrate is described as defensible but remains a scope decision.

Code and data availability

The reference implementation, analysis notebooks, dataset-preparation scripts, and key screening and graph-construction utilities are publicly available.

  • Availability: The repository contains the reference implementation, notebooks, dataset-preparation scripts, applicability screening function, and spectral-gap-matched graph-family notebook.Datasets come from their original sources and are not redistributed.

Declaration of LLM usage

A large language model assisted with writing, debugging, literature work, and interpretation, while every quantitative result was produced by executed code.

  • Declaration: A large language model was used interactively for writing, script debugging, literature search and summarisation, prose revision, and challenging interpretations.The authors state that executed analyses reversed several earlier conclusions.
Loading 2609.01633v2…