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
Experiments 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.
This 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.