A training-free NUI estimation procedure based on clustering consistency with ground-truth labels is introduced, providing a proxy for task-relevant information without supervised learning, and a strong correlation between estimated NUI and downstream classification accuracy is observed, validating NUI as an effective measure of representation utility.
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.
Graph classification plays a central role in many scientific disciplines. While classical kernel-based methods and graph neural networks achieve strong predictive performance, they often require substantial computational resources. Hyperdimensional Computing (HDC) has recently emerged as an efficient and noise-resilient alternative, providing lightweight models that are attractive for resource-constrained settings. Within this context, GraphHD is a representative HDC-based approach for graph classification; however, its encoding process can become costly on large graphs and its standard configuration relies on a single centrality choice (PageRank) for node-to-hypervector assignment.
In this work, we go beyond PageRank in GraphHD by systematically evaluating alternative centrality measures (degree, closeness, betweenness, Katz, and eigenvector) and by introducing two new encoding variants. GraphHD-Level preserves quantitative structural information by mapping centrality values to level-hypervectors, whereas GraphHD-Order simplifies the algorithm by eliminating edge encoding and aggregating node hypervectors directly. Experiments on six widely used benchmarks from cheminformatics and bioinformatics (MUTAG, ENZYMES, PROTEINS, DD, NCI1, and PTC\_FM) show that replacing PageRank with alternative centralities yields similar F1-scores while offering notable runtime savings, and that GraphHD-Order remains competitive with the original GraphHD baseline while providing consistent speedups in encoding time.
Community detection is essential for uncovering the functional organization of complex networks. While traditional methods often rely on edge density, motif-based approaches use higher-order structural patterns to identify communities. However, existing research frequently employs conventional motifs, such as triangles or 4-node cliques, or lacks validation against networks with ground-truth communities. This study addresses these limitations by systematically evaluating eight small motifs across both synthetic and real-world networks with known community structures. We propose a framework that transforms unweighted graphs into weighted representations by assigning weights to node pairs based on their co-occurrence frequency within specific graphlets, while also preserving information about the original edges, rather than creating a potentially sparse (hyper)network. Thus, graphlet adjacency captures the topological complexity of a node by accounting for both its direct edges and the local connectivity patterns of its neighbors; this higher-order information is vital for accurate community detection. Our results demonstrate that graphlet-based weighting significantly enhances community detection in networks. We find that no single "universal" motif optimizes performance across all real-world networks. Rather than favoring only dense, clique-based structures, our findings highlight that simpler motifs can also provide strong performance in networks. These results suggest that relying exclusively on cliques may overlook critical connectivity patterns, offering a new perspective on how higher-order structures define communities in networks.
Anastasiia Dziuba, Jure Pražnikar· Journal of Intelligence and...· 0 citations
Results show that mixed-distribution training can improve structural transfer in GNN-based centrality approximation, while identifying closeness centrality's sensitivity to topology as an open challenge.
Samra Sana, Giorgio Mantica, Saul Imbrici· 0 citations
A diffusion-enhanced inductive link prediction framework that combines Graph Diffusion Convolution (GDC), structural node descriptors, and neighborhood aggregation from GraphSAGE is proposed that achieves higher accuracy than the other models on the benchmark datasets.