Scholarly Works, Computer Science

Permanent URI for this collection

https://hdl.handle.net/10919/24290

Research articles, presentations, and other scholarship

Browse

Now showing 1 - 20 of 885

ZoneTrace: Zone Monitoring Tool for F2FS on ZNS SSDs
Chen, Ping-Xiang; Seo, Dongjoo; Sung, Changhoon; Park, Jongheum; Lee, Minchul; Li, Huaicheng; Bjorling, Matias; Dutt, Nikil (ACM, 2024-09-01)
We present ZoneTrace, a runtime monitoring tool for the Flash-friendly File System (F2FS) on Zoned Names- pace (ZNS) Solid-state Drives (SSDs). ZNS SSD organizes its storage into zones of sequential write access. Due to ZNS SSD's sequential write nature, F2FS is a log-structured file system that has recently been adopted to support ZNS SSDs. To present the space management with the zone concept between F2FS and the underlying ZNS SSD, we developed ZoneTrace, a tool that enables users to visualize and analyze the space management of F2FS on ZNS SSDs. ZoneTrace utilizes the extended Berkeley Packet Filter (eBPF) to trace the updated segment bitmap in F2FS and visualize each zone space usage accordingly. Furthermore, ZoneTrace is able to analyze on file fragmentation in F2FS and provides users with informative fragmentation histogram to serve as an indicator of file fragmentation. Using ZoneTrace's visualization, we are able to identify the current F2FS space management scheme's inability to fully optimize space for streaming data recording in autonomous systems, which leads to serious file fragmentation on ZNS SSDs. Our evaluations show that ZoneTrace is lightweight and assists users in getting useful insights for effortless monitoring on F2FS with ZNS SSD with both synthetic and realistic workloads. We believe ZoneTrace can help users analyze F2FS with ease and open up space management research topics with F2FS on ZNS SSDs.
Implicit Solvent with Explicit Ions Generalized Born Model in Molecular Dynamics: Application to DNA
Kolesnikov, Egor S.; Xiong, Yeyue; Onufriev, Alexey V. (American Chemical Society, 2024-09-16)
The ion atmosphere surrounding highly charged biomolecules, such as nucleic acids, is crucial for their dynamics, structure, and interactions. Here, we develop an approach for the explicit treatment of ions within an implicit solvent framework suitable for atomistic simulations of biomolecules. The proposed implicit solvent/explicit ions model, GBION, is based on a modified generalized Born (GB) model; it includes separate, modified GB terms for solute-ion and ion-ion interactions. The model is implemented in the AMBER package (version 24), and its performance is thoroughly investigated in atomistic molecular dynamics (MD) simulations of double-stranded DNA on a microsecond time scale. The aggregate characteristics of monovalent (Na+ and K+) and trivalent (Cobalt Hexammine, CoHex(3+)) counterion distributions around double-stranded DNA predicted by the model are in reasonable agreement with the experiment (where available), all-atom explicit water MD simulations, and the expectation from the Manning condensation theory. The radial distributions of monovalent cations around DNA are reasonably close to the ones obtained using the explicit water model: expressed in units of energy, the maximum deviations of local ion concentrations from the explicit solvent reference are within 1 k(B)T, comparable to the corresponding deviations expected between different established explicit water models. The proposed GBION model is able to simulate DNA fragments in a large volume of solvent with explicit ions with little additional computational overhead compared with the fully implicit GB treatment of ions. Ions simulated using the developed model explore conformational space at least 2 orders of magnitude faster than in the explicit solvent. These advantages allowed us to observe and explore an unexpected "stacking" mode of DNA condensation in the presence of trivalent counterions (CoHex(3+)) that was revealed by recent experiments.
The Interaction Fidelity Model: A Taxonomy to Communicate the Different Aspects of Fidelity in Virtual Reality
Bonfert, Michael; Muender, Thomas; McMahan, Ryan P.; Steinicke, Frank; Bowman, Doug; Malaka, Rainer; Doering, Tanja (Taylor & Francis, 2025-06-18)
Fidelity describes how closely a replication resembles the original. It can be helpful to analyze how faithful interactions in virtual reality (VR) are to a reference interaction. In prior research, fidelity has been restricted to the simulation of reality-also called realism. Our definition includes other reference interactions, such as superpowers or fiction. Interaction fidelity is a multilayered concept. Unfortunately, different aspects of fidelity have either not been distinguished in scientific discourse or referred to with inconsistent terminology. Therefore, we present the Interaction Fidelity Model (IntFi Model). Based on the human-computer interaction loop, it systematically covers all stages of VR interactions. The conceptual model establishes a clear structure and precise definitions of eight distinct components. As a communication tool, it helps teams to understand and discuss fidelity in VR. It was reviewed through workshops with fourteen VR experts. We provide guidelines, diverse examples, and educational material to apply the IntFi Model universally to any VR experience and propose foundational research opportunities.
Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling
Cetinkaya, Ibrahim; Büyüktahtakın, İ. Esra; Shojaee, Parshin; Reddy, Chandan K. (2025-10-14)
Our study contributes to the scheduling and combinatorial optimization literature with new heuristics discovered by leveraging the power of Large Language Models (LLMs). We focus on the single-machine total tardiness (SMTT) problem, which aims to minimize total tardiness by sequencing n jobs on a single processor without preemption, given processing times and due dates. We develop and benchmark two novel LLM-discovered heuristics, the EDD Challenger (EDDC) and MDD Challenger (MDDC), inspired by the well-known Earliest Due Date (EDD) and Modified Due Date (MDD) rules. In contrast to prior studies that employed simpler rule-based heuristics, we evaluate our LLM-discovered algorithms using rigorous criteria, including optimality gaps and solution time derived from a mixed-integer programming (MIP) formulation of SMTT. We compare their performance against state-of-the-art heuristics and exact methods across various job sizes (20, 100, 200, and 500 jobs). For instances with more than 100 jobs, exact methods such as MIP and dynamic programming become computationally intractable. Up to 500 jobs, EDDC improves upon the classic EDD rule and another widely used algorithm in the literature. MDDC consistently outperforms traditional heuristics and remains competitive with exact approaches, particularly on larger and more complex instances. This study shows that human–LLM collaboration can produce scalable, high-performing heuristics for NP-hard constrained combinatorial optimization, even under limited resources when effectively configured.
lociPARSE: A Locality-aware Invariant Point Attention Model for Scoring RNA 3D Structures
Tarafder, Sumit; Bhattacharya, Debswapna (American Chemical Society, 2024-11-11)
A scoring function that can reliably assess the accuracy of a 3D RNA structural model in the absence of experimental structure is not only important for model evaluation and selection but also useful for scoring-guided conformational sampling. However, high-fidelity RNA scoring has proven to be difficult using conventional knowledge-based statistical potentials and currently available machine learning-based approaches. Here, we present lociPARSE, a locality-aware invariant point attention architecture for scoring RNA 3D structures. Unlike existing machine learning methods that estimate superposition-based root-mean-square deviation (RMSD), lociPARSE estimates Local Distance Difference Test (lDDT) scores capturing the accuracy of each nucleotide and its surrounding local atomic environment in a superposition-free manner, before aggregating information to predict global structural accuracy. Tested on multiple datasets including CASP15, lociPARSE significantly outperforms existing statistical potentials (rsRNASP, cgRNASP, DFIRE-RNA, and RASP) and machine learning methods (ARES and RNA3DCNN) across complementary assessment metrics. lociPARSE is freely available at https://github.com/Bhattacharya-Lab/lociPARSE.
Optimal Dielectric Boundary for Binding Free Energy Estimates in the Implicit Solvent
Forouzesh, Negin; Ghafouri, Fatemeh; Tolokh, Igor S.; Onufriev, Alexey V. (American Chemical Society, 2024-12-10)
Accuracy of binding free energy calculations utilizing implicit solvent models is critically affected by parameters of the underlying dielectric boundary, specifically, the atomic and water probe radii. Here, a multidimensional optimization pipeline is used to find optimal atomic radii, specifically for binding calculations in the implicit solvent. To reduce overfitting, the optimization target includes separate, weighted contributions from both binding and hydration free energies. The resulting five-parameter radii set, OPT_BIND5D, is evaluated against experiment for binding free energies of 20 host-guest (H-G) systems, unrelated to the types of structures used in the training. The resulting accuracy for this H-G test set (root mean square error of 2.03 kcal/mol, mean signed error of -0.13 kcal/mol, mean absolute error of 1.68 kcal/mol, and Pearson's correlation of r = 0.79 with the experimental values) is on par with what can be expected from the fixed charge explicit solvent models. Best agreement with the experiment is achieved when the implicit salt concentration is set equal or close to the experimental conditions.
Graphical security modelling for Autonomous Vehicles: A novel approach to threat analysis and defence evaluation
Nguyen, Nhung H.; Ge, Mengmeng; Cho, Jin-Hee; Moore, Terrence J.; Yoon, Seunghyun; Lim, Hyuk; Nelson, Frederica; Bai, Guangdong; Kim, Dan Dongseong (Elsevier Advanced Technology, 2025-03-01)
Autonomous Vehicles (AVs) integrate numerous control units, network components, and protocols to operate effectively and interact with their surroundings, such as pedestrians and other vehicles. While these technologies enhance vehicle capabilities and enrich the driving experience, they also introduce new attack surfaces, making AVs vulnerable to cyber-attacks. Such cyber-attacks can lead to severe consequences, including traffic disruption and even threats to human life. Security modelling is crucial to safeguarding AVs as it enables the simulation and analysis of an AV's security before any potential attacks. However, the existing research on AV security modelling methods for analysing security risks and evaluating the effectiveness of security measures remains limited. In this work, we introduce a novel graphical security model and metrics to assess the security of AV systems. The proposed model utilizes initial network information to build attack graphs and attack trees at different layers of network depth. From this, various metrics are automatically calculated to analyse the security and safety of the AV network. The proposed model is designed to identify potential attack paths, analyse security and safety with precise metrics, and evaluate various defence strategies. We demonstrate the effectiveness of our framework by applying it to two AV networks and distinct AV attack scenarios, showcasing its capability to enhance the security of AVs.
A machine learning framework to predict PPCP removal through various wastewater and water reuse treatment trains
Choi, Joung Min; Manthapuri, Vineeth; Keenum, Ishi; Brown, Connor L.; Xia, Kang; Chen, Chaoqi; Vikesland, Peter J.; Blair, Matthew F.; Bott, Charles; Pruden, Amy; Zhang, Liqing (Royal Society Chemistry, 2025-01-30)
The persistence of pharmaceuticals and personal care products (PPCPs) through wastewater treatment and resulting contamination of aquatic environments and drinking water is a pervasive concern, necessitating means of identifying effective treatment strategies for PPCP removal. In this study, we employed machine learning (ML) models to classify 149 PPCPs based on their chemical properties and predict their removal via wastewater and water reuse treatment trains. We evaluated two distinct clustering approaches: C1 (clustering based on the most efficient individual treatment process) and C2 (clustering based on the removal pattern of PPCPs across treatments). For this, we grouped PPCPs based on their relative abundances by comparing peak areas measured via non-target profiling using ultra-performance liquid chromatography-tandem mass spectrometry through two field-scale treatment trains. The resulting clusters were then classified using Abraham descriptors and log Kow as input to the three ML models: support vector machines (SVM), logistic regression, and random forest (RF). SVM achieved the highest accuracy, 79.1%, in predicting PPCP removal. Notably, a 58-75% overlap was observed between the ML clusters of PPCPs and the Abraham descriptor and log Kow clusters of PPCPs, indicating the potential of using Abraham descriptors and log Kow to predict the fate of PPCPs through various treatment trains. Given the myriad of PPCPs of concern, this approach can supplement information gathered from experimental testing to help optimize the design of wastewater and water reuse treatment trains for PPCP removal.
Top-Down Stochastic Block Partitioning: Turning Graph Clustering Upside Down
Wanye, Frank; Gleyzer, Vitaliy; Kao, Edward; Feng, Wu-chun (ACM, 2025-07-20)
Stochastic block partitioning (SBP) is a statistical inference-based algorithm for clustering vertices within a graph. It has been shown to be statistically robust and highly accurate even on graphs with a complex structure, but its poor scalability limits its usability to smaller-sized graphs. In this manuscript we argue that one reason for its poor scalability is the agglomerative, or bottom-up, nature of SBP’s algorithmic design; the agglomerative computations cause high memory usage and create a large search space that slows down statistical inference, particularly in the algorithm’s initial iterations. To address this bottleneck, we propose Top-Down SBP, a novel algorithm that replaces the agglomerative (bottom-up) block merges in SBP with a block-splitting operation. This enables the algorithm to start with all vertices in one cluster and subdivide them over time into smaller clusters. We show that Top-Down SBP is up to 7.7× faster than Bottom-Up SBP without sacrificing accuracy and can process larger graphs than Bottom-Up SBP on the same hardware due to an up to 4.1× decrease in memory usage. Additionally, we adapt existing methods for accelerating Bottom- Up SBP to the Top-Down approach, leading to up to 13.2× speedup over accelerated Bottom-Up SBP and up to 403× speedup over sequential Bottom-Up SBP on 64 compute nodes. Thus, Top-Down SBP represents substantial improvements to the scalability of SBP, enabling the analysis of larger datasets on the same hardware.
Can Large Language Models Predict Parallel Code Performance?
Bolet, Gregory; Georgakoudis, Giorgis; Menon, Harshitha; Parasyris, Konstantinos; Hasabnis, Niranjan; Estes, Hayden; Cameron, Kirk; Oren, Gal (ACM, 2025-07-20)
Accurate determination of the performance of parallel GPU code typically requires execution-time profiling on target hardware – an increasingly prohibitive step due to limited access to high-end GPUs. This paper explores whether Large Language Models (LLMs) can offer an alternative approach for GPU performance prediction without relying on hardware.We frame the problem as a roofline classification task: given the source code of a GPU kernel and the hardware specifications of a target GPU, can an LLM predict whether the GPU kernel is compute-bound or bandwidth-bound? For this study, we build a balanced dataset of 340 GPU kernels, obtained from HeCBench benchmark and written in CUDA and OpenMP, along with their ground-truth labels obtained via empirical GPU profiling. We evaluate LLMs across four scenarios: (1) with access to profiling data of the kernel source, (2) zero-shot with source code only, (3) few-shot with code and label pairs, and (4) finetuned on a small custom dataset. Our results show that state-of-theart LLMs have a strong understanding of the Roofline model, achieving 100% classification accuracy when provided with explicit profiling data. We also find that reasoning-capable LLMs significantly outperform standard LLMs in zero- and few-shot settings, achieving up to 64% classification accuracy of GPU source codes, without any profiling information. Lastly, we find that model accuracy does not benefit meaningfully from few-shot prompting compared to zero-shot, and that LLM fine-tuning will require much more data than what we currently have available. This work is among the first to use LLMs for source-level roofline performance prediction via classification, and illustrates their potential to guide optimization efforts when runtime profiling is infeasible. Our findings suggest that with better datasets and prompt strategies, LLMs could become practical tools for HPC performance analysis and performance portability. Code and datasets are publicly available at https: //github.com/Scientific-Computing-Lab/ParallelCodeEstimation.
Pairwise BPF Programs Should Be Optimized Together
Craun, Milo; Williams, Dan (ACM, 2025-09-08)
BPF programs are extensively used for tracing and observability in production systems where performance overheads matter. Many individual BPF programs do not incur serious performance degrading overhead on their own, but increasingly more than a single BPF program is used to understand production system performance. BPF deployments have begun to look more like distributed applications; however, this is a mismatch with the underlying Linux kernel, potentially leading to high overhead cost. In particular, we identify that many BPF programs follow a pattern based on pairwise program deployment where entry and exit probes will be attached to measure a single quantity. We find that the pairwise BPF program pattern results in unnecessary overheads. We identify three optimizations—BPF program inlining, context aware optimization, and intermediate state internalization—that apply to pairwise BPF programs. We show that applying these optimizations to an example pairwise BPF program can reduce overhead on random read throughput from 28.13% to 8.98% and on random write throughput from 26.97% to 8.60%. We then examine some key design questions that arise when seeking to integrate optimizations with the existing BPF system.
SchedBPF - Scheduling BPF programs
Shekar, Kavya; Williams, Dan (ACM, 2025-09-08)
The Linux BPF framework enables the execution of verified custom bytecode in the critical path of various Linux kernel routines, allowing for efficient in-kernel extensions. The safety properties and low execution overhead of BPF programs have led to advancements in kernel extension use-cases that can be broadly categorized into tracing, custom kernel policies, and application acceleration. However, BPF is fundamentally event-driven and lacks native support for periodic or continuous tasks such as background tracing, metric aggregation, or kernel housekeeping. Existing approaches such as kernel modules with kthreads, userspace daemons, or BPF timers fail to satisfy all the essential requirements for periodic kernel extensions such as fine-grained CPU control, kernel safety, and minimal overhead. To address this gap, we propose SchedBPF — a conceptual framework that enables periodic execution of BPF programs on kernel threads. SchedBPF program executions are sandboxed and preemptible, as governed by the existing BPF verifier and JIT engine. They also adopt time-slice semantics, cgroup-style CPU quotas, and nice-level priority control, similar to kernel threads. SchedBPF aims to enable low-overhead, periodic execution of safe BPF code with fine-grained CPU resource management.
BPFflow - Preventing information leaks from eBPF
Dimobi, Chinecherem; Tiwari, Rahul; Ji, Zhengjie; Williams, Dan (ACM, 2025-09-08)
eBPF has seen major industry adoption by enterprises to enhance observability, tracing, and monitoring by hooking at different points in the kernel. However, since the kernel is a critical resource, eBPF can also pose as a threat if misused, potentially leading to privilege escalation, information leaks and more. While effective to some extent, existing mitigation strategies like interface filtering are coarse-grained and often over-restrictive. We propose BPFflow, a flexible framework for the system administrator to define policies that specify sensitive data sources, trusted sinks and permitted flows between them. These policies are enforced by an Information Flow Control (IFC) system within the eBPF verifier to track the propagation of sensitive data to prevent unauthorized leakage to userspace or any other untrusted sinks without any runtime overhead.
Adaptive and Efficient Dynamic Memory Management for Hardware Enclaves
Dhanraj, Vijay; Chawla, Harpreet; Manila, Daniel; Schneider, Eric; Fu, Erica; Porter, Donald; Tsai, Chia-Che; Vij, Mona (ACM, 2025-09-08)
The second version of Intel® Software Guard Extensions (Intel SGX), or SGX2, adds dynamic management of enclave memory and threads. The first version required the address space and thread counts to be fixed before execution. The Enclave Dynamic Memory Management (EDMM) feature of SGX2 has the potential to lower launch times and overall execution time. Despite reducing the enclave loading time by 28–93%, straightforward EDMM adoption strategies actually slow execution time down by as much as 58%. Using the Gramine library OS as a representative enclave runtime environment, this paper shows how to recover EDMM performance. The paper explains how implementing mutual distrust between the OS and enclave increases the cost of modifying page mappings. The paper then describes a series of optimizations and, using application benchmarks, shows that these optimizations effectively eliminate the overheads of EDMM while retaining EDMM’s performance and flexibility gains.
Teaching K-8 Students Computer Science Using Digital Storybooks
Deverin, Thomas; Hamouda, Sally (ACM, 2025-08-03)
This study introduces CodeKids, a novel web-based platform to teach computer science to elementary and middle school-aged students using interactive digital storybooks. Several books on the CodeKids website were created to target common misconceptions young students form when learning foundational computer science concepts, including variables, conditionals, and loops. The primary objectives of this research are to evaluate student engagement and perceptions of the storybook format and determine if the books help prevent common computer science misconceptions for K-8 students.
Designing Answer-Aware LLM Hints to Scaffold Deeper Learning in K-12 Programming Education
Bhaskar, Sahana; Hamouda, Sally (ACM, 2025-08-03)
Many K–12 students struggle with programming concepts. While LLMs offer scalable, timely support, overly direct answers can reduce reasoning and engagement [8], prompting the question: How can LLMs support learning without encouraging overreliance? In our study with 105 students, 31.4% showed misconceptions about variable assignment and data types, and in another survey, only 20% correctly solved conditional problems. This highlights the need for scaffolding to address conceptual gaps in K–12 programming. To address these gaps, we designed an answer-aware hint generation system using LLMs to support learning without reducing cognitive demand.We developed the system for CodeKids—an opensource, curriculum-aligned platform built with Virginia Tech and local public schools. It helps students practice grade-level programming through interactive activities, using LLM-generated hints to guide thinking without revealing answers [1, 11]. Based on Vygotsky’s Zone of Proximal Development [12], our approach balances support and autonomy through structured prompting that preserves productive struggle.
Teaching and Learning AI in K-12 Informatics Education
Barendsen, Erik; Lonati, Violetta; Quille, Keith; Altin, Rukiye; Divitini, Monica; Hooshangi, Sara; Karnalim, Oscar; Kiesler, Natalie; Melton, Madison; Suero Montero, Calkin; Morpurgo, Anna (ACM, 2024-12)
With the diffuse and very rapidly evolving presence of Artificial Intelligence (AI) in so many aspects of our everyday life, the question of at what age and how to start preparing citizens for the AI revolution has become urgent. Moreover, AI in general, and the recent and easy availability for everyone of generative AI in particular, are raising pressing issues regarding education in terms of both opportunities and challenges. This working group research is an international and collective effort to reach deep but scalable insights into current trends, developments, and perspectives regarding AI in K-12 education. The focus is on AI as content matter as opposed to AI as enabler of digital technology for teaching and learning. This work complements earlier reviews of scientific literature on AI in education by sketching the bigger picture by putting progress in scientific research in the context of developments in educational practice. Drawing on a scoping literature review, interviews with educators, AI experts, and policymakers, and an analysis of institutional documents, we provide an overview of the current trends and gaps. The analyses revealed several gaps and opportunities. First, maintaining a conceptual distinction between teaching with AI, with AI as enabler of digital tools for education, and teaching about AI, with AI as content matter, is crucial. Second, in spite of the abundance of interventions and tools in literature and documents, there is a lack of fundamental pedagogical knowledge about the underlying mechanisms informing teaching and learning of AI. Third, research and design efforts are required to find a proper balance between technical and socio-ethical aspects of AI in curricula. Fourth, there is a need for research-informed initiatives to support K-12 teachers’ preparation and continuous professional development on teaching and learning of AI. These findings give rise to the formulation of four grand challenges as inspiration for future research and policy developments
Evaluating Capabilities and Perspectives of Generative AI Tools in Smart Contract Development
Khalid, Shawal; Brown, Chris (ACM, 2025-08)
Smart contracts, self-executing agreements on the blockchain, have emerged as a transformative force in blockchain technology, automating agreements and enabling decentralized applications. However, the stakes are extraordinarily high—manual coding errors in smart contracts have repeatedly led to financial losses. Notable incidents, such as the DAO hack that resulted in a loss of approximately $50 million [36] and the Parity wallet vulnerability that froze approximately $280 million in assets [45], underscore the immense economic risks involved. To support manual development tasks, recent advancements in artificial intelligence (AI) powered by large language models (LLMs) have transformed how software is developed and maintained by automating various software engineering tasks. This research explores the capabilities of generative AI tools for efficient and secure smart contract development. The methodology involves two phases: 1) we distribute a mixed methods survey for blockchain and smart contract developers (𝑛 = 114) to investigate their perspectives towards utilizing LLMs; and 2) we evaluate the effectiveness of generative AI tools, such as ChatGPT, Google Gemini, and ChainGPT, for smart contract development. This evaluation is based on comparing the LLM-generated smart contract code with human-written code, using a diverse dataset of smart contracts gathered from GitHub. Static analysis tools and unit testing are employed to validate the accuracy, correctness, efficiency, and security of the generated code. Our findings highlight the potential of these tools to accelerate smart contract development processes, while also emphasizing the need for human oversight, contributing to the advancement of blockchain technology and its applications.
EVINET: Evidential Reasoning Network for Resilient Graph Learning in the Open and Noisy Environments
Guan, Weijie; Wang, Haohui; Kang, Jian; Liu, Lihui; Zhou, Dawei (ACM, 2025-08-03)
Graph learning has been crucial to many real-world tasks, but they are often studied with a closed-world assumption, with all possible labels of data known a priori. To enable effective graph learning in an open and noisy environment, it is critical to inform the model users when the model makes a wrong prediction to in-distribution data of a known class, i.e., misclassification detection or when the model encounters out-of-distribution from novel classes, i.e., out-ofdistribution detection. This paper introduces Evidential Reasoning Network (EviNet), a framework that addresses these two challenges by integrating Beta embedding within a subjective logic framework. EviNet includes two key modules: Dissonance Reasoning for misclassification detection and Vacuity Reasoning for outof- distribution detection. Extensive experiments demonstrate that EviNet outperforms state-of-the-art methods across multiple metrics in the tasks of in-distribution classification, misclassification detection, and out-of-distribution detection. EviNet demonstrates the necessity of uncertainty estimation and logical reasoning for misclassification detection and out-of-distribution detection and paves the way for open-world graph learning. Our code and data are available at https://github.com/SSSKJ/EviNET.
Network Interdiction Goes Neural
Zhang, Lei; Chen, Zhiqian; Lu, Chang-Tien; Zhao, Liang (ACM, 2025-08-03)
Network interdiction problems, arising in critical applications from military strategy to disease control, involve a complex attackerdefender dynamic: one player optimizes a network-based objective, while the other strategically modifies the network to impede that objective. The inherent bi-level optimization and combinatorial nature of these problems pose a significant computational challenge, often rendering traditional exact solvers impractical and hindering the development of effective heuristics. While Graph Neural Networks (GNNs) have demonstrated promise in solving singlelevel combinatorial optimization problems on graphs, their direct application to bi-level interdiction problems remains limited. In this paper, we bridge this gap by introducing a novel approach that leverages the power of GNNs to learn Mixed-Integer Linear Programming (MILP) formulations of network interdiction problems. By representing the problem in this structured mathematical form, we empower a multipartite GNN with the representational capacity to effectively capture the complex interplay between the two players. This approach aligns the neural network with the underlying mathematical structure of interdiction problems, leading to improved performance. Through extensive experiments on two network interdiction tasks, we demonstrate the superiority of our proposed method over both baseline GNN models and traditional exact solvers, showcasing its potential for real-world applications.

Browse

Recent Submissions