1 Introduction↩︎

Graph classification is a fundamental problem in graph machine learning, where the objective is to assign labels to entire graphs based on their structural and attribute information. It arises in a wide range of applications, including molecular property prediction, program analysis, malware detection, and network security. In recent years, graph neural networks (GNNs) have become the dominant paradigm for this task due to their ability to learn expressive representations through message passing mechanisms [1]–[3]. Despite their success, the expressive power of GNNs is known to be theoretically bounded by the Weisfeiler–Lehman hierarchy [4], and their performance often depends heavily on architectural design and training stability.

A key limitation of existing GNN-based approaches is that they rely on end-to-end learning of graph embeddings, which are typically treated as black-box representations. This makes it difficult to interpret what structural information is being utilized and whether the learned representations are inherently informative for the downstream task. Furthermore, training deep graph models can be computationally expensive and sensitive to hyperparameter choices, especially on large-scale or heterogeneous graph datasets.

To mitigate these challenges, several pooling and hierarchical representation methods have been proposed, aiming to construct graph-level embeddings from node representations in a permutation-invariant manner [5]–[7]. While these approaches improve aggregation, they still inherit the limitations of learned embeddings and do not provide explicit mechanisms to evaluate representation quality prior to training.

From a data perspective, benchmark datasets such as TUDataset and Open Graph Benchmark have played a central role in evaluating graph learning methods [8], [9]. However, performance comparisons on these benchmarks often focus solely on predictive accuracy, without providing insight into the intrinsic informational content of different graph representations.

Recently, the concept of Network Usable Information (NUI) was introduced in NetInfoF [10], providing a principled framework for quantifying the amount of task-relevant information contained in learned representations for node-level and link-level tasks. However, extending this notion to graph-level classification remains challenging due to the absence of a unified representation space across graphs with varying sizes and structures.

In this work, we propose NetinfoGC, a framework that extends NUI to graph classification. Our approach constructs a family of permutation-invariant graph representations derived from both propagation-based mechanisms and classical structural descriptors. In particular, we incorporate graph centrality measures as complementary structural signals alongside the original NetInfoF components, enabling a richer characterization of graph topology.

Beyond representation construction, NetinfoGC introduces a two-stage pipeline. First, we estimate NUI using an unsupervised clustering-based procedure that measures alignment between induced structure and ground-truth labels. Second, we exploit the same representations using sparse-group LASSO regularization [11], which enables automatic selection of informative structural descriptors while suppressing redundant ones.

Graph-based learning has been widely studied in security-related applications such as malware classification [12], smart contract vulnerability detection [13], botnet detection [13], and adversarial robustness analysis [14]. These settings further motivate the need for interpretable and efficient representation evaluation mechanisms, as graph structures evolve dynamically and retraining large models may be impractical.

Contributions. Concretely, this paper makes the following contributions:

• We adapt the NUI framework from node/link-level tasks to graph classification, resolving the representation-space mismatch that arises when graphs vary in size and structure.

• We augment the propagation-based descriptors from NETINFOF with five classical centrality measures, and show empirically that these two families capture complementary structural information rather than redundant signal.

• We design a training-free, clustering-based procedure for estimating NUI at the graph level, giving a label-aware but model-free proxy for representation quality.

• Empirically, we find that degree centrality is a consistently strong - sometimes the strongest - representation across both benchmarks, and that NUI tracks downstream accuracy closely enough to serve as a pre-training screening criterion.

2 NetinfoGC for Graph Classification↩︎

This section introduces NetinfoGC, a graph classification framework that extends the Network Usable Information (NUI) paradigm of NetInfoF [10] to graph-level learning. While the underlying principles of NetInfoF remain unchanged, graph classification requires representations that operate on entire graphs rather than individual nodes or edges. This introduces the need for permutation-invariant, fixed-dimensional graph embeddings that can be compared across graphs of varying sizes and structures.

2.1 Problem Definition↩︎

Let \[\mathcal{G} = \{(G_i,y_i)\}_{i=1}^N\] denote a dataset of \(N\) attributed graphs, where each graph \[G_i = (V_i, E_i, X_i)\] consists of a node set \(V_i\), an edge set \(E_i\), and a node feature matrix \[X_i \in \mathbb{R}^{|V_i| \times f}.\] Each graph is associated with a label \[y_i \in \{1,\dots,c\},\] where \(c\) denotes the number of classes.

The objective of graph classification is to learn a function \[f : \mathcal{G} \rightarrow \{1,\dots,c\}\] that maps unseen graphs to their correct labels. Unlike node-level tasks, graph classification requires learning from heterogeneous graph instances with varying sizes, requiring invariant and fixed-dimensional representations.

NetinfoGC addresses this by first constructing graph-level representations from multiple structural descriptors, and then measuring and exploiting their Network Usable Information in a unified framework.

2.2 Graph-level Representation Learning↩︎

NetinfoGC constructs graph representations from a unified set of structural descriptors that capture complementary aspects of topology, feature propagation, and vertex importance.

2.2.0.1 Unified descriptor family.

We define a set of representation functions: \[\mathcal{M} = \{U, R, F, P, S, Deg, Bet, Close, PR, Eig\},\] where each \(m \in \mathcal{M}\) denotes either a propagation-based descriptor from NetInfoF or a classical centrality measure.

For each graph \(G_i\), each descriptor induces a node-level representation: \[Z_i^{(m)} \in \mathbb{R}^{|V_i| \times d}.\]

2.2.0.2 Graph-level aggregation.

To obtain permutation-invariant representations, we apply a READOUT function: \[h_i^{(m)} = \mathrm{READOUT}(Z_i^{(m)}) \in \mathbb{R}^{d}.\] We use mean pooling as the default READOUT operator, ensuring invariance to node ordering and robustness across graphs of varying size.

2.2.0.3 Centrality-based representations.

In addition to propagation-based descriptors, we incorporate classical centrality measures to capture structural importance from a complementary perspective.

For each node \(v \in V_i\), we compute:

\[c^{deg}(v), \quad c^{bet}(v), \quad c^{close}(v), \quad c^{pr}(v), \quad c^{eig}(v).\]

Each centrality measure produces a vector: \[\mathbf{c}_i^{(m)} \in \mathbb{R}^{|V_i|}.\]

We treat this vector as a node-level feature: \[Z_i^{(m)} = \mathbf{c}_i^{(m)},\] which is then aggregated using the same READOUT operator: \[h_i^{(m)} = \mathrm{READOUT}(Z_i^{(m)}).\]

2.2.0.4 Unified graph representation.

Each graph is represented by the set: \[\mathcal{H}_i = \{ h_i^{(m)} \mid m \in \mathcal{M} \}.\]

The final representation used for downstream tasks is constructed via concatenation: \[x_i = \big\|_{m \in \mathcal{M}} h_i^{(m)} \in \mathbb{R}^{|\mathcal{M}| \cdot d}.\]

This representation integrates propagation-based, feature-based, and centrality-based structural information into a single unified embedding space.

2.3 NetinfoGC for NUI Measurement↩︎

To estimate Network Usable Information (NUI), we evaluate whether a graph representation induces structure that is aligned with the true class labels.

We consider the dataset of graph embeddings: \[\mathcal{X} = \{x_i\}_{i=1}^N.\]

2.3.0.1 Unsupervised clustering.

We apply \(k\)-means clustering to \(\mathcal{X}\) to obtain pseudo-labels: \[\hat{y}_i = \mathrm{Cluster}(x_i),\] where \(k \geq c\). Before clustering, embeddings are \(\ell_2\)-normalized.

2.3.0.2 NUI estimation.

We define the conditional entropy: \[H(Y \mid \hat{Y}) = - \sum_{y,\hat{y}} p(y,\hat{y}) \log p(y \mid \hat{y}).\]

The NetinfoGC score is defined as: \[\mathrm{NetinfoGC} = 2^{-H(Y \mid \hat{Y})}.\]

Lower entropy indicates stronger alignment between clustering structure and ground-truth labels, implying higher usable information.

2.4 NetinfoGC for NUI Exploitation↩︎

For classification, we concatenate all graph representations: \[x_i = \big\|_{m \in \mathcal{M}} h_i^{(m)}.\]

We use a logistic regression model with sparse-group LASSO regularization. Let \(\beta^{(m)}\) denote parameters associated with descriptor \(m\). The optimization problem is: \[\min_{\beta} \mathcal{L}(\beta) + \lambda_1 \sum_{m \in \mathcal{M}} \|\beta^{(m)}\|_2 + \lambda_2 \|\beta\|_1.\]

This induces: - group-level sparsity (removal of entire descriptors), - feature-level sparsity (within descriptors).

Descriptors with low Network Usable Information are automatically suppressed, while informative ones are retained.

Prediction is performed as: \[\hat{y}_i = \arg\max_y \sigma(x_i^\top \beta).\]

2.5 Computational Complexity↩︎

Representation construction is dominated by propagation operations: \[O(k \bar{e} d),\] and READOUT: \[O(\bar{n} d).\]

Centrality computation varies: - degree: \(O(\bar{e})\) - betweenness/closeness: \(O(\bar{n}\bar{e})\) - PageRank/eigenvector: \(O(T\bar{e})\)

NUI measurement via \(k\)-means: \[O(T_k N |\mathcal{M}| d).\]

Sparse-group LASSO training scales linearly: \[O(N |\mathcal{M}| d).\]

Overall complexity remains linear in graph size for sparse graphs.

2.6 Applications↩︎

NetinfoGC applies to any domain involving graph classification, including molecular property prediction, cybersecurity, program analysis, and communication networks. A key advantage is that it enables estimation of representation quality before training complex graph models.

In cybersecurity, graphs representing program execution or network traffic can be analyzed to determine whether structural descriptors contain sufficient discriminative information. In molecular learning, it allows evaluation of whether structural or centrality-based representations are informative before training GNNs.

Overall, NetinfoGC provides a principled framework for evaluating and exploiting graph representations through Network Usable Information.

3 Numerical Evaluation↩︎

We evaluate NetinfoGC on standard graph classification benchmarks to study (i) the effectiveness of graph-level Network Usable Information (NUI) as a predictor of downstream performance, and (ii) the contribution of different structural descriptors, including both the original NetInfoF components and classical graph centrality measures.

3.1 Experimental Setup↩︎

We conduct experiments on the IMDB-BINARY and IMDB-MULTI datasets from the TU benchmark suite [8]. Each graph is converted into a set of graph-level embeddings using the READOUT-based construction described in Section 2.2. We evaluate representations derived from both the original NetInfoF components and five centrality-based descriptors: degree, betweenness, closeness, PageRank, and eigenvector centrality.

Unless otherwise specified, we use an embedding dimension of \(d=32\), 50 histogram bins, propagation depth \(k=32\) for propagation-based descriptors, learning rate \(10^{-3}\), and train all models for 500 epochs using sparse-group LASSO regularization. All results are reported as mean \(\pm\) standard deviation over multiple independent runs, including NUI score, validation accuracy, and test accuracy.

3.2 Results↩︎

Table 1 summarizes the performance of different graph representations across both datasets. Overall, we observe that structural descriptors exhibit varying degrees of usefulness, and no single representation is universally optimal across datasets.

3.2.0.1 Effectiveness of centrality-based representations.

A key observation is that classical centrality measures provide competitive and in some cases superior graph classification performance compared to propagation-based representations. In particular, degree centrality consistently achieves the strongest performance across both datasets, reaching \(70.54\%\) test accuracy on IMDB-BINARY and \(55.08\%\) on IMDB-MULTI. This is also reflected in its high NUI score, suggesting a strong alignment between the amount of usable structural information and downstream predictive performance.

Other centrality measures show dataset-dependent behavior. PageRank achieves competitive performance on IMDB-BINARY, while betweenness and closeness centralities provide moderate improvements in specific settings. In contrast, eigenvector centrality performs less consistently, particularly on IMDB-MULTI, indicating that global spectral influence alone may not sufficiently capture discriminative graph-level information.

3.2.0.2 Comparison with NetInfoF components.

Among the original NetInfoF descriptors, propagation-based and neighborhood-based representations remain competitive but are generally outperformed by the most informative centrality-based representations. This suggests that classical structural measures capture complementary information not fully encoded by propagation-based mechanisms.

3.2.0.3 Combination of representations.

We further evaluate a combined representation that aggregates all descriptors. Interestingly, this full combination does not consistently outperform the best individual descriptor. This indicates that simply increasing representation dimensionality does not guarantee improved performance, and may introduce redundancy that dilutes discriminative structure. This observation further motivates the role of NUI as a principled criterion for evaluating representation usefulness prior to model construction.

3.2.0.4 NUI–performance relationship.

Across representations, we observe a strong empirical correlation between the estimated NUI score and downstream classification accuracy. Representations with higher NUI tend to yield better predictive performance, supporting the premise that NUI provides a meaningful proxy for task-relevant information in graph representations.

3.2.0.5 Summary.

Overall, these results demonstrate that NetinfoGC not only enables effective graph classification using a diverse set of structural descriptors, but also provides a practical mechanism to evaluate the usefulness of such representations before training. The results further highlight that classical graph-theoretic measures can play a significant role in modern graph representation learning when viewed through the lens of Network Usable Information.

4 Conclusion↩︎

This work extended the NUI paradigm, originally developed for node- and link-level tasks in NETINFOF, to the graph classification setting. The main technical challenge in this extension is the lack of a shared representation space across graphs of varying size and topology; NETINFOGC addresses this by combining propagation-based descriptors with classical centrality measures under a common permutation-invariant READOUT operator.

Two findings stand out from the experiments. First, degree centrality alone was consistently among the strongest representations on both IMDB-BINARY and IMDB-MULTI, often matching or exceeding the propagation-based descriptors inherited from NETINFOF. This is a useful reminder that simple, interpretable structural statistics still carry substantial discriminative signal for graph-level tasks, even relative to learned or propagation-heavy alternatives. Second, the clustering-based NUI estimate tracked downstream test accuracy fairly closely across representations, which suggests it can serve as a cheap, label-aware screening step before committing to a specific representation or training a full model.

One counterintuitive result deserves more scrutiny than we were able to give it here: concatenating all descriptors together did not outperform the single best descriptor, and in some cases performed worse. This points to redundancy or noise introduced by naively stacking representations, and suggests that NUI-guided descriptor selection — rather than exhaustive concatenation — may be the more principled path forward, which is precisely the role the sparse-group LASSO stage is intended to play.

The current evaluation is limited to two TUDataset benchmarks, and the centrality measures we used are standard but not exhaustive. Extending NETINFOGC to larger, more heterogeneous graph collections (e.g., OGB), incorporating attributed or weighted centrality variants, and studying the theoretical relationship between NUI and generalization error are natural next steps.

References↩︎