Aug 2026· Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2· 0 citations· 29 references
TL;DR
This work proposes two scalable greedy algorithms based on gradient-guided edge selection that efficiently approximate marginal gains and prune the candidate edge set and achieves optimization performance comparable to exact greedy strategies while substantially reducing computational time.
Abstract
Information centrality is a powerful metric for quantifying node importance and has demonstrated practical value in a variety of real-world applications. Although existing studies have explored information centrality optimization via edge addition, they are restricted to a local setting, where candidate edges must be incident to the target node. Such restrictions fail to fully exploit the global structure of the network and often lead to suboptimal solutions under the same edge budget. In this work, we study the problem of global information centrality optimization, where candidate edges may connect any pair of currently non-adjacent nodes. This formulation significantly enlarges the search space and breaks the supermodularity property that underlies traditional greedy approaches, making the problem substantially more challenging. To address these challenges, we propose two scalable greedy algorithms based on gradient-guided edge selection. Our methods exploit geometric interpretations, dimensionality reduction techniques, and nearly-linear-time Laplacian solvers to efficiently approximate marginal gains and prune the candidate edge set. Extensive experiments on real-world networks demonstrate that our algorithms achieve optimization performance comparable to exact greedy strategies while substantially reducing computational time.
A novel heuristic community detection algorithm, termed CoDeSEG, which identifies communities by minimizing the network's two-dimensional structural entropy within a potential game framework, and introduces a structural entropy-based node overlapping heuristic for detecting overlapping communities, with a near-linear time complexity.
This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.
Finding maximum cliques in protein-protein interaction networks (PPINs) is computationally NP-hard. Large-scale PPINs typically contain dense and redundant interaction structures that exponentially increase search time. To address this computational bottleneck while preserving topological integrity, this study proposes a two-stage pruning strategy. The framework first employs K-core decomposition to filter peripheral noise, followed by a particle swarm-optimized graph attention network (GAT-PSO) that integrates four centrality metrics. This centrality-aware design explicitly captures complex structural dependencies, successfully mitigating the dense-core bias inherent in conventional statistical feature-based pruning and ensuring the retention of critical connector nodes. Evaluation across 12,535 STRING-derived PPINs demonstrated average node and edge reductions of 95.87% and 91.11%, respectively, thereby accelerating the MaxCliqueDyn (MCQD) algorithm by up to 106.73 times. Despite this extreme dimensionality reduction, the pruned networks maintained strong structural fidelity, achieving a clique-size similarity of 97.23% and a Jaccard index of 86.70%. Furthermore, functional enrichment confirmed that the retained modules align with established biological pathways. These results validate the proposed framework as a robust, scalable pre-processing solution for accelerating exact clique detection in massive PPINs.
Gilland Fausta Putra Achyar, Annisa, Heru Cahya Rustamaji et al.· Journal of Mathematics and S...· 0 citations
Heterogeneous information networks serve as one of the most important platforms in the fields of big data and artificial intelligence. Node similarity analysis is a fundamental yet crucial task. To explicitly distinguish the number of differing items and the total magnitude of interaction information between nodes of the same type under arbitrary meta-paths, while enabling flexible weighting between these two aspects, this paper proposes a similarity algorithm that formulates node similarity as a convex combination of vector norms. The proposed algorithm requires only the interaction information between typed nodes and does not depend on the type of metapath. It satisfies desirable properties including non-negativity, symmetry, self-maximum and boundedness. Experimental results on two real-world datasets demonstrate its superiority: on the Association for Computing Machinery Digital Library Dataset, the proposed algorithm achieves an average Silhouette of 0.67 on the paper-author-paper meta-path, outperforming PathSim and HeteSim by over 139%, and maintains a Calinski-Harabasz index approximately 6.6 times that of PathSim on the optimal paper-subject-paper meta-path. On the Internet Movie Database Dataset, it attains an average Silhouette of 0.77, which is 5.1 times and 3.0 times those of PathSim and HeteSim, respectively. Furthermore, the algorithm exhibits strong robustness, with minimal performance fluctuation across different meta-paths and clustering algorithms, whereas baseline methods suffer severe degradation. These results validate the efficiency and robustness of the proposed algorithm under various complex scenarios.
Wujie Hu, Wenhu Qin, Xuechun Liu et al.· IEEE International Conferenc...· 0 citations
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.
Graph machine learning provides powerful tools for understanding complex networks and learning meaningful node representations. A central challenge, however, is designing embeddings with minimal distortion of both local and global functionals, such as shortest path lengths. Prior distortion guarantees for distance-preserving embeddings are worst-case in nature, producing overly pessimistic bounds that fail to capture the structure of typical large-scale networks. To address this, we analyze shortest-path approximation via landmark-based embeddings on inhomogeneous random graphs, a general model with type-dependent edge probabilities. By retaining shortest paths to a small set of reference nodes called landmarks, landmark-based methods effectively function as virtual graph spanners, where structural heterogeneity and controlled neighborhood expansion modeled via multi-type branching processes enable significantly tighter dimension-distortion trade-offs than classical worst-case bounds. We extend these guarantees to global, component-wide averages and unify the analysis across finite-type and continuous latent spaces through a novel metric sandwiching framework, establishing universal distortion bounds for general $L^2$ kernel models, including heavy-tailed and power-law networks. Finally, we introduce a GNN-augmented variant that replaces rigid, computationally expensive exact shortest-path queries with flexible, structure-aware neural surrogates. By leveraging the inherent alignment between graph neural message-passing and the dynamic programming principles of shortest-path algorithms, our approach demonstrates that models trained on small-scale random graphs learn to extract universal distance-preserving features, achieving robust generalization to large-scale, real-world networks that match or exceed the fidelity of classical, exact landmark-based embeddings.