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.
Results validate the proposed framework as a robust, scalable pre-processing solution for accelerating exact clique detection in massive PPINs and confirm that the retained modules align with established biological pathways.
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.