Effcient Multi-Criteria Important Node Identifcation via Ego-Network Approximation

Graphs are fundamental tools for modeling complex relationships across a wide range of domains, where identifying the most influential or structurally important nodes, known as key actors, is a central problem. Single centrality metrics often fail to capture universally influential nodes, highlighting the necessity for multi-criteria approaches. In this paper, we propose an effcient and effective approximation scheme that identifes key actors by aggregating multiple centrality measures through an ego-network-based graph-convolutional network (GCN). We introduce two novel heuristics: (i) size-aware ego-network retrieval, which constrains computational overhead by limiting ego-network sizes, and (ii) selective feature computation, which reduces runtime by computing detailed local features only for structurally signifcant nodes. Extensive experimental validation on both synthetic and real-world datasets demonstrates that our approximation achieves substantial computational savings, while closely matching the accuracy and ranking quality of baseline methods. Last but not least, robustness analyses underscore the practical utility of the identifed key nodes, showcasing their effectiveness in network dismantling and disruption scenarios.