Pith. sign in

REVIEW 5 major objections 6 minor 15 references

Graph Classification via Network Usable Information: From Representation Evaluation to Structure Selection

T0 review · 5 major / 6 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Simple degree centrality often beats learned graph embeddings for classification, and a clustering score can rank them before training.

desk verdict Narrow but honest extension of NetInfoF: degree centrality often wins on IMDB, and a cheap clustering NUI tracks accuracy there; the proxy claim is oversold and the evaluation is too thin. read the letter →

arxiv 2607.03587 v1 pith:SXBFMX3T submitted 2026-07-03 cs.LG

Abdullah Shaik , Anwar Said This is my paper · ORCID
classification cs.LG
keywords NetworkUsableInformationgraphclassificationcentralitydegreesparse-groupLASSOpermutation-invariantrepresentationstraining-freeevaluation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that you do not need end-to-end trained graph neural networks to get strong graph classification. NetinfoGC builds fixed, permutation-invariant graph vectors from classical centralities (degree, betweenness, closeness, PageRank, eigenvector) plus propagation-style descriptors, then scores how much task-relevant structure each vector carries by a training-free clustering procedure called Network Usable Information. On two standard social-graph benchmarks, degree centrality is repeatedly among the best single representations and often tops the propagation family. The same NUI score tracks downstream accuracy closely enough to serve as a pre-training screen, and sparse-group LASSO can keep the useful descriptors while dropping the rest. A sympathetic reader cares because the result reopens a simple, interpretable toolbox for graph labels and offers a cheap filter before expensive model training.

What carries the argument

Network Usable Information at graph level: after mean-pooling each descriptor into a fixed vector and ℓ₂-normalizing, k-means (k ≥ number of classes) produces pseudo-labels; NUI is defined as 2 minus the conditional entropy of true labels given those clusters. Sparse-group LASSO then selects which descriptor groups to keep.

What would settle it

Run the same NUI-versus-accuracy comparison on larger, more heterogeneous collections (for example molecular or Open Graph Benchmark graphs); if high-NUI descriptors systematically fail to predict or match the best classifiers there, the proxy claim fails.

Watch

Extended reading notes

Core claim

Classical graph centralities, especially degree, are highly competitive with—and on IMDB-BINARY and IMDB-MULTI often superior to—propagation-based representations for graph classification, and a training-free clustering estimate of Network Usable Information (NetinfoGC = 2 − H(Y|Ŷ)) strongly correlates with test accuracy, so NUI can act as a model-free proxy for representation utility before any supervised training.

Load-bearing premise

The claim rests on the idea that how cleanly k-means clusters of a representation line up with the true graph labels is a faithful, general measure of usable information, shown so far only on two IMDB social-network datasets.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 6 minor

Summary. The paper proposes NetinfoGC, extending Network Usable Information (NUI) from node/link tasks (NetInfoF) to graph classification. It builds permutation-invariant graph embeddings by mean-pooling a family of descriptors M that mixes NetInfoF-style propagation components with five classical centralities (degree, betweenness, closeness, PageRank, eigenvector). Representation quality is scored by a training-free NUI estimate: ℓ2-normalized embeddings are clustered with k-means (k ≥ c) and NetinfoGC = 2 − H(Y|Ŷ) measures alignment with ground-truth labels. The same concatenated features are then classified with sparse-group LASSO to select informative descriptor groups. On IMDB-BINARY and IMDB-MULTI, degree centrality often matches or beats propagation descriptors, and the authors report that NUI tracks test accuracy, arguing that NUI can screen representations before end-to-end GNN training.

Significance. If the clustering-based NUI proxy and the competitiveness of classical centralities hold beyond the two social-network benchmarks, the work would offer a practical, interpretable pre-training screen for graph representations and a reminder that simple structural statistics remain strong baselines. The sparse-group LASSO selection stage and the explicit unification of propagation and centrality descriptors are useful engineering contributions. Strengths include a clear two-stage pipeline, explicit complexity discussion, and an empirical finding (degree centrality leading on both sets) that is falsifiable and of interest to practitioners. The contribution is incremental relative to NetInfoF and standard graph kernels/centralities, and its impact hinges on broader validation and a quantified NUI–accuracy relationship.

major comments (5)
  1. §3.1–3.2 and Table 1: All quantitative claims rest on only IMDB-BINARY and IMDB-MULTI. The abstract, applications section (§2.6), and conclusion assert utility for molecular property prediction, cybersecurity, OGB-scale graphs, and pre-training screening, yet no molecular, OGB, or even other TU sets (e.g., MUTAG, PROTEINS, NCI1) appear. With N=2 datasets of the same social-network type, the central claim that centrality measures are “highly competitive” and that NUI is a general proxy is not yet supported at the scope claimed. At minimum, results on a more diverse suite (and ideally one attributed molecular set) are needed before the proxy claim can be treated as validated.
  2. Abstract and §3.2 (“strong correlation” / “NUI–performance relationship”): Table 1 lists Mean NUI and Test Accuracy for nine representations × two datasets, but no Pearson/Spearman coefficient, p-value, scatter plot, or leave-one-representation-out analysis is reported. Readers must eyeball the table. The correlation is load-bearing for the claim that NUI is an effective pre-training screening criterion; it should be quantified (with uncertainty) and, ideally, checked under a protocol where NUI is computed without using the same full labeled set that defines accuracy (e.g., NUI on a held-out split or label-free surrogate).
  3. §2.3 (NUI estimation) vs. Abstract (“training-free … without supervised learning”): NetinfoGC = 2 − H(Y|Ŷ) explicitly uses ground-truth labels Y. The procedure is free of gradient-based model training, but it is not label-free. This blurs the distinction between a model-free proxy and a label-aware clustering purity score. The manuscript should state clearly that labels are required for the NUI score, discuss how this differs from fully unsupervised representation evaluation, and address the partial circularity that any representation already separating classes will score high on both NUI and accuracy on the same labeled collection.
  4. §3.2 and Table 1: There is no comparison to standard graph classification baselines (e.g., GIN, GCN with sum/mean pooling, DiffPool, graph kernels, or even a simple degree histogram + SVM). All comparisons are internal among NetInfoF components and centralities under the same sparse-group LASSO head. Without external baselines it is hard to judge whether 70.54% / 55.08% (degree) is competitive with the literature on these sets, or whether the framework improves on end-to-end GNNs as the introduction suggests. Adding at least a few published baselines under the same splits would ground the “highly competitive” claim.
  5. §2.4 and Table 1 “All Components” rows: Concatenating all descriptors underperforms the best single descriptor on both datasets (65.74% vs 70.54% on BINARY; 41.41% vs 55.08% on MULTI). The sparse-group LASSO stage is presented as the remedy for redundancy, yet Table 1 does not report selected groups, sparsity patterns, or accuracy after LASSO-driven selection versus naive concatenation. Without those results, the exploitation half of the pipeline is not empirically demonstrated, and the motivation for group sparsity remains largely theoretical.
minor comments (6)
  1. Title page / running header: “APREPRINT- JULY7, 2026” and arXiv date “3 Jul 2026” look like future dates; confirm intended year.
  2. §2.2: Descriptors U, R, F, P, S are named but not defined in the manuscript; readers must consult Lee et al. (2024). A short self-contained definition or equation for each would improve readability.
  3. §2.3: The constant “2” in NetinfoGC = 2 − H(Y|Ŷ) is unexplained. Is it an upper bound on binary entropy, a multi-class convention, or inherited from NetInfoF? Clarify the range and units of the score.
  4. §3.1: Hyperparameters (d=32, k=32, 50 bins, λ1/λ2, number of runs) are listed but the number of independent runs and the train/val/test split protocol (e.g., 10-fold vs fixed split) are not fully specified for reproducibility.
  5. References: Zhou et al. (2020) is cited twice for different topics (smart contracts and botnets) with the same key; disambiguate. Typographic issues (e.g., “Veliˇckovi´c”, missing spaces in “GRAPHCLASSIFICATION VIANETWORKUSABLEINFORMATION”) should be cleaned.
  6. Table 1: PageRank on IMDB-BINARY has higher mean test accuracy (70.76) than Degree (70.54) but with larger std (3.50 vs 1.62); the text still calls degree “the strongest.” Soften or qualify that statement, or report a significance test.

Circularity Check

1 steps flagged · score 2.0 of 10

Mild shared-label dependence between NUI and accuracy; no derivation reduces to its inputs by construction.

  1. other [§2.3 NUI estimation; Abstract / §3.2 NUI–performance claim]
    "We define the conditional entropy: H(Y|Ŷ)=−∑ p(y,ŷ) log p(y|ŷ). The NETINFOGC score is defined as: NetinfoGC = 2−H(Y|Ŷ). ... we observe a strong correlation between estimated NUI and downstream classification accuracy, validating NUI as an effective measure of representation utility."

    NUI is computed from clustering of the embeddings using the ground-truth labels Y; test accuracy is also computed against the same Y on the same embeddings. The claimed 'validation' of NUI as a pre-training proxy therefore re-uses the label information that defines the accuracy metric, so the correlation is partly expected from shared class-separation signal rather than an independent check. It is not a full by-construction identity (different procedures; imperfect rank order in Table 1), hence only mild circularity.

full rationale

NetinfoGC is an empirical representation-evaluation framework, not a first-principles derivation of a predicted quantity. Representations (propagation descriptors plus classical centralities) are constructed independently of the downstream classifier; sparse-group LASSO is a standard regularized logistic model; and the claim that degree centrality is competitive is a table-level empirical comparison on IMDB-BINARY/MULTI, not a forced identity. The only mild circularity is that the training-free NUI score NetinfoGC = 2 − H(Y|Ŷ) already consumes the same ground-truth labels Y that define classification accuracy, so a positive NUI–accuracy correlation is partly expected whenever a representation separates classes, rather than an independent external validation of the proxy. That dependence is real but not load-bearing: k-means conditional entropy is not algebraically equal to logistic-regression accuracy (Table 1 shows imperfect rank alignment, e.g. PageRank vs degree on IMDB-BINARY), no parameter is fitted on a subset and then re-reported as a prediction, and the NetInfoF citation is to different authors (Lee et al., 2024), not a self-citation uniqueness chain. Score 2 reflects one minor shared-label loop, not a circular derivation.

Assumptions & free parameters 5 free parameters · 4 assumptions · 2 invented entities

The central empirical claim rests on a small set of modeling choices (mean readout, k-means NUI definition, sparse-group LASSO) and on the unproved premise that clustering alignment equals usable information, plus free hyperparameters that control representation dimension and regularization. No new physical entities are invented; the main invented construct is the graph-level NetinfoGC score itself.

free parameters (5)
  • embedding dimension d = 32
    Fixed at 32 for all reported runs; controls representation capacity and enters every accuracy/NUI number.
  • propagation depth k = 32
    Set to 32 for propagation-based descriptors; directly shapes the Structure/Neighborhood/Propagation features.
  • histogram bins = 50
    50 bins used in representation construction; affects discretization of continuous descriptors.
  • sparse-group LASSO λ1, λ2
    Regularization strengths that decide which descriptor groups survive; values not reported numerically but required for the selection claim.
  • k-means cluster count k (≥ c) = k ≥ number of classes
    Controls the resolution of the unsupervised clustering used to define NUI; choice affects the entropy estimate.
assumptions (4)
  • domain assumption Mean READOUT of node-level descriptors yields a permutation-invariant, size-robust graph embedding sufficient for cross-graph comparison.
    Invoked in §2.2 as the default aggregation; standard in graph pooling but not proved optimal here.
  • ad hoc to paper Conditional entropy of true labels given k-means pseudo-labels (after ℓ2 normalization) is a faithful proxy for Network Usable Information at graph level.
    Defined in §2.3 as NetinfoGC = 2 − H(Y|Ŷ); no derivation linking this quantity to mutual information or generalization error.
  • domain assumption Sparse-group LASSO on concatenated descriptors automatically retains high-NUI groups and suppresses redundant ones.
    Optimization stated in §2.4 citing Simon et al. 2013; assumed to implement NUI-guided selection without separate proof on these data.
  • domain assumption IMDB-BINARY and IMDB-MULTI are representative enough to support claims about classical vs. propagation representations and NUI–accuracy correlation.
    Sole experimental regime in §3; conclusion itself flags the limitation.
invented entities (2)
  • NetinfoGC score (graph-level NUI via clustering)
    purpose: Training-free scalar that ranks graph representations by label-aligned cluster purity.
    Defined in §2.3 as 2 − H(Y|Ŷ); no independent external validation or theoretical bound outside the paper's own accuracy correlation.
  • Unified descriptor family M = {U,R,F,P,S,Deg,Bet,Close,PR,Eig}
    purpose: Single concatenation space mixing NetInfoF propagation features with five classical centralities for graph classification.
    Introduced in §2.2; the family itself is a packaging choice rather than a new physical object, with independent evidence only via the empirical table.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph Classification via Network Usable Information: From Representation Evaluation to Structure Selection." pith.science (2026). https://pith.science/paper/SXBFMX3T

@misc{pith2026260703587,
  author       = {Pith},
  title        = {Pith review of: Graph Classification via Network Usable Information: From Representation Evaluation to Structure Selection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SXBFMX3T}},
  note         = {Machine review of arXiv:2607.03587}
}
read the original abstract

We propose NetinfoGC, a framework for graph classification that extends the Network Usable Information (NUI) paradigm to graph-level learning. Unlike conventional graph neural network approaches that rely on end-to-end training of black-box embeddings, NetinfoGC constructs a family of permutation-invariant graph representations derived from propagation-based mechanisms and classical structural descriptors, including graph centrality measures. To evaluate representation quality, we introduce a training-free NUI estimation procedure based on clustering consistency with ground-truth labels, providing a proxy for task-relevant information without supervised learning. We further exploit the same representations using sparse-group LASSO regularization, enabling automatic selection of informative structural descriptors while suppressing redundant ones. Experiments on benchmark datasets show that classical centrality measures are highly competitive with learned propagation-based representations, and in several cases yield superior performance. Moreover, we observe a strong correlation between estimated NUI and downstream classification accuracy, validating NUI as an effective measure of representation utility. Overall, NetinfoGC provides a unified and interpretable framework for evaluating and exploiting graph representations without requiring end-to-end neural training.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 6 linked inside Pith

  1. [1]

    International Conference on Learning Representations , volume=

    Netinfof framework: Measuring and exploiting network usable information , author=. International Conference on Learning Representations , volume=

  2. [2]

    arXiv preprint arXiv:1609.02907 , year=

    Semi-supervised classification with graph convolutional networks , author=. arXiv preprint arXiv:1609.02907 , year=

    arXiv

  3. [3]

    Advances in neural information processing systems , volume=

    Inductive representation learning on large graphs , author=. Advances in neural information processing systems , volume=

  4. [4]

    arXiv preprint arXiv:1710.10903 , year=

    Graph attention networks , author=. arXiv preprint arXiv:1710.10903 , year=

    arXiv

  5. [5]

    arXiv preprint arXiv:1810.00826 , year=

    How powerful are graph neural networks? , author=. arXiv preprint arXiv:1810.00826 , year=

    arXiv

  6. [6]

    arXiv preprint arXiv:2007.08663 , year=

    Tudataset: A collection of benchmark datasets for learning with graphs , author=. arXiv preprint arXiv:2007.08663 , year=

    arXiv 2007

  7. [7]

    Advances in neural information processing systems , volume=

    Open graph benchmark: Datasets for machine learning on graphs , author=. Advances in neural information processing systems , volume=

  8. [8]

    Advances in neural information processing systems , volume=

    Hierarchical graph representation learning with differentiable pooling , author=. Advances in neural information processing systems , volume=

Show all 15 references
  1. [9]

    arXiv preprint arXiv:1511.06391 , year=

    Order matters: Sequence to sequence for sets , author=. arXiv preprint arXiv:1511.06391 , year=

    arXiv

  2. [10]

    Advances in neural information processing systems , volume=

    Deep sets , author=. Advances in neural information processing systems , volume=

  3. [11]

    Journal of computational and graphical statistics , volume=

    A sparse-group lasso , author=. Journal of computational and graphical statistics , volume=. 2013 , publisher=

    2013

  4. [12]

    Journal of Computer Virology and Hacking Techniques , volume=

    A comparison of graph neural networks for malware classification , author=. Journal of Computer Virology and Hacking Techniques , volume=. 2024 , publisher=

    2024

  5. [13]

    Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence , pages=

    Smart contract vulnerability detection using graph neural networks , author=. Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence , pages=

  6. [14]

    arXiv preprint arXiv:2003.06344 , year=

    Automating botnet detection with graph neural networks , author=. arXiv preprint arXiv:2003.06344 , year=

    2003 arXiv

  7. [15]

    28th USENIX security symposium (USENIX Security 19) , pages=

    \ TESSERACT \ : Eliminating experimental bias in malware classification across space and time , author=. 28th USENIX security symposium (USENIX Security 19) , pages=

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.