Learning Higher-Order Dependencies in Malware Control-Flow Graphs With Hypergraph-Level Explanations

Malware continues to cause significant security and financial losses, creating a pressing need for accurate and scalable detection and analysis. Accordingly, static malware detection has become a widely used and scalable first line of defense.However, reliable static detection remains challenging because discriminativemalware behavior can be distributed across distant and non-adjacent regions of a program. Many malware samples exhibit staged execution workflows, so the corresponding evidence may span multiple basic blocks that are not directly connected in the control-flow graph (CFG). Conventional graph-based detectors propagate information only through local control-flow links and struggle to capture such long-range dependencies. Moreover, while graph-based detectors offer a more semantically grounded view of program behavior, few works provide actionable explanations for their predictions. To address these issues, we propose MalHGNN, a malware classification framework that elevates the CFG into a hyper control-flow graph (HCFG) for higher-order dependency modeling. MalHGNN introduces explicit higher-order shortcuts by combining semantic k-NN hyperedges with structural k-Hop hyperedges, enabling aggregation of features across distant, non-adjacent basic blocks. In addition, we develop an interpretability technique, HGNN-CAM. It provides both node-level and hyperedge-level attributions to highlight critical basic blocks and their higher-order combinations. Extensive experiments on the BIG2015 and MalwareBazaar real-world datasets validate the effectiveness of MalHGNN. MalHGNN consistently outperforms representative feature-based and graph-based malware detectors on malware family classification, demonstrating the benefits of higher-order dependency modeling. These results indicate that our approach improves malware classification performance while providing interpretable node- and hyperedge-level evidence for its predictions.