SEARCH · Engineering Papers

Results for “Computational graph”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 181 records · Page 10

All sources NASA NTRS DOE OSTI

DOE OSTI2024

Distributed Multi-GPU Community Detection on Exascale Computing Platforms

Community detection is a fundamental operation in graph mining, and by uncovering hidden structures and patterns within complex systems it helps solve fundamental problems pertaining to social networks, such as information diffusion, epidemics, and recommender systems. Scaling graph algorithms for massive networks becomes challenging on modern distributed-memory multi-GPU (Graphics Processing Unit) systems due to limitations such as irregular memory access patterns, load imbalances, higher communication-computation ratios, and cross-platform support. We present a novel algorithm HiPDPL-GPU (Distributed Parallel Louvain) to address these challenges. We conduct experiments involving different partitioning techniques to achieve an optimized performance of HiPDPL-GPU on the two largest supercomputers: Frontier and Summit. Remarkably, HiPDPL-GPU processes a graph with 4.2 billion edges in less than 3 minutes using 1024 GPUs. Qualitatively, the performance of HiPDPL-GPU is similar or better compared to other state-of-the-art CPU- and GPU-based implementations. While prior GPU implementations have predominantly employed CUDA, our first-of-its-kind implementation for community detection is cross-platform, accommodating both AMD and NVIDIA GPUs.

Sattar, Naw Safrin↗

DOE OSTI2023

Fuzzy cyber detection pattern matching

Mechanisms for identifying a pattern of computing resource activity of interest, in activity data characterizing activities of computer system elements, are provided. A temporal graph of the activity data is generated and a filter is applied to the temporal graph to generate one or more first vector representations, each characterizing nodes and edges within a moving window defined by the filter. The filter is applied to a pattern graph representing a pattern of entities and events indicative of the pattern of interest, to generate a second vector representation. The second vector representation is compared to the one or more first vector representations to identify one or more nearby vectors, and one or more corresponding subgraph instances are output to an intelligence console computing system as inexact matches of the temporal graph.

Shu, Xiaokui↗

DOE OSTI2024

Extending Power of Nature from Binary Problems to Real-Valued Graph Learning in Real World

Nature performs complex computations constantly at clearly lower cost and higher performance than digital computers. It is crucial to understand how to harness the unique computational power of nature in Machine Learning (ML). In the past decade, besides the development of Neural Networks (NNs), the community has also relentlessly explored nature-powered ML paradigms. Although most of them are still predominantly theoretical, a new practical paradigm enabled by the recent advent of CMOS-compatible room-temperature nature-based computers has emerged. By harnessing the nature's power of entropy increase, this paradigm can solve binary learning problems delivering immense speedup and energy savings compared with NNs, while maintaining comparable accuracy. Regrettably, its values to the real world are highly constrained by its binary nature. A clear pathway to its extension to real-valued problems remains elusive. This paper aims to unleash this pathway by proposing a novel end-to-end Nature-Powered Graph Learning (NP-GL) framework. Specifically, through a three-dimensional co-design, NP-GL can leverage the nature's power of entropy increase to efficiently solve real-valued graph learning problems. Experimental results across 4 real-world applications with 6 datasets demonstrate that NP-GL delivers, on average, 6970X speedup and 10^5x energy consumption reduction with comparable or even higher accuracy than Graph Neural Networks (GNNs).

artificial intelligence↗

DOE OSTI2023

Graph Metric Learning Quantifies Morphological Differences between Two Genotypes of Shoot Apical Meristem Cells in Arabidopsis

We present a method for learning “spectrally descriptive” edge weights for graphs. We generalize a previously known distance measure on graphs (Graph Diffusion Distance), thereby allowing it to be tuned to minimize an arbitrary loss function. Because all steps involved in calculating this modified GDD are differentiable, we demonstrate that it is possible for a small neural network model to learn edge weights which minimize loss. We apply this method to discriminate between graphs constructed from shoot apical meristem images of two genotypes of Arabidopsis thaliana specimens: wild-type and trm678 triple mutants with cell division phenotype. Training edge weights and kernel parameters with contrastive loss produces a learned distance metric with large margins between these graph categories. We demonstrate this by showing improved performance of a simple k-nearest-neighbors classifier on the learned distance matrix. We also demonstrate a further application of this method to biological image analysis. Once trained, we use our model to compute the distance between the biological graphs and a set of graphs output by a cell division simulator. Comparing simulated cell division graphs to biological ones allows us to identify simulation parameter regimes which characterize mutant vs. wild-type Arabidopsis cells. We find that trm678 mutant cells are characterized by increased randomness of division planes and decreased ability to avoid previous vertices between cell walls.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2023

End-to-End Pipeline for Trigger Detection on Hit and Track Graphs

There has been a surge of interest in applying deep learning in particle and nuclear physics to replace labor-intensive offline data analysis with automated online machine learning tasks. This paper details a novel AI-enabled triggering solution for physics experiments in Relativistic Heavy Ion Collider and future Electron-Ion Collider. The triggering system consists of a comprehensive end-to-end pipeline based on Graph Neural Networks that classifies trigger events versus background events, makes online decisions to retain signal data, and enables efficient data acquisition. Here, the triggering system first starts with the coordinates of pixel hits lit up by passing particles in the detector, applies three stages of event processing (hits clustering, track reconstruction, and trigger detection), and labels all processed events with the binary tag of trigger versus background events. By switching among different objective functions, we train the Graph Neural Networks in the pipeline to solve multiple tasks: the edge-level track reconstruction problem, the edge-level track adjacency matrix prediction, and the graph-level trigger detection problem. We propose a novel method to treat the events as track-graphs instead of hit-graphs. This method focuses on intertrack relations and is driven by underlying physics processing. As a result, it attains a solid performance (around 72% accuracy) for trigger detection and outperforms the baseline method using hit-graphs by 2% higher accuracy.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2024

Modern chemical graph theory

Abstract Graph theory has a long history in chemistry. Yet as the breadth and variety of chemical data is rapidly changing, so too do graph encoding methods and analyses that yield qualitative and quantitative insights. Using illustrative cases within a basic mathematical framework, we showcase modern chemical graph theory's utility in Chemists' analysis and model development toolkit. The encoding of both experimental and simulation data is discussed at various levels of granularity of information. This is followed by a discussion of the two major classes of graph theoretical analyses: identifying connectivity patterns and partitioning methods. Measures, metrics, descriptors, and topological indices are then introduced with an emphasis upon enhancing interpretability and incorporation into physical models. Challenging data cases are described that include strategies for studying time dependence. Throughout, we incorporate recent advancements in computer science and applied mathematics that are propelling chemical graph theory into new domains of chemical study. This article is categorized under: Molecular and Statistical Mechanics > Molecular Dynamics and Monte‐Carlo Methods Structure and Mechanism > Computational Materials Science Structure and Mechanism > Molecular Structures

Leite, Leonardo S. G.↗

DOE OSTI2025

Increasing the hardness of posiform planting using random QUBOs for programmable quantum annealer benchmarking

Posiform planting is a method for constructing QUBO instances with a unique planted solution that can be tailored to arbitrary connectivity graphs. In this study we investigate making posiform planted QUBOs computationally harder by fusing many smaller random Ising models, whose global minimum is computed classically, with posiform planted QUBOs. The unique ground state of the resulting QUBO is the concatenation of (exactly one of) the ground states of each smaller problem. Our method generates QUBO instances that have a unique solution, are native to the hardware graph, and have tunable computational hardness. We use our QUBOs to benchmark three D-Wave quantum annealing processors (with 563–5627 qubits), and compare them against simulated annealing and Gurobi. Surprisingly, we find that the D-Wave ground state sampling success rate is not dependent on the glued random QUBO size, and that some QUBO classes are solved at high success rates at short annealing times on the Zephyr processors.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2026

Citation network datasets for benchmarking spiking graph neural networks on experimental neuromorphic hardware

Spiking neural networks (SNNs) running on neuromorphic computers offer an energy-efficient alternative for AI tasks. Recently, spiking graph neural networks (S-GNNs) have been shown to produce encouraging results on benchmark citation network datasets such as Cora, CiteSeer, and PubMed for node classification tasks. These S-GNNs were run on SNN simulators only because they contain up to tens of thousands of neurons and up to millions of synapses, translating poorly to neuromorphic hardware. Therefore, in this paper, we create a suite of benchmark datasets from the CiteSeer dataset that can be accommodated on current neuromorphic hardware platforms. Our contribution consists of a collection of three datasets. First, we have an induced subgraph of CiteSeer, which we call MiniSeer, containing 2110 papers, 3604 binary features, and 6 topics. Second, MicroSeer is a very small dataset consisting of 84 papers, 1227 features, and 6 topics. Lastly, BiteSeer is a collection of 15 binary classification datasets. We present creation of these datasets along with accuracies, running times, and spike counts when simulated. We believe that our results in this paper will be used by the neuromorphic community to benchmark, test, and develop neuromorphic hardware and simulators.

Zhu, Kevin [George Mason University, Virginia]↗

DOE OSTI2025

A change language for ontologies and knowledge graphs

Ontologies and knowledge graphs (KGs) are general-purpose computable representations of some domain, such as human anatomy, and are frequently a crucial part of modern information systems. Most of these structures change over time, incorporating new knowledge or information that was previously missing. Managing these changes is a challenge, both in terms of communicating changes to users and providing mechanisms to make it easier for multiple stakeholders to contribute. To fill that need, we have created KGCL, the Knowledge Graph Change Language (https://github.com/INCATools/kgcl), a standard data model for describing changes to KGs and ontologies at a high level, and an accompanying human-readable Controlled Natural Language (CNL). This language serves two purposes: a curator can use it to request desired changes, and it can also be used to describe changes that have already happened, corresponding to the concepts of “apply patch” and “diff” commonly used for managing changes in text documents and computer programs. Another key feature of KGCL is that descriptions are at a high enough level to be useful and understood by a variety of stakeholders—e.g. ontology edits can be specified by commands like “add synonym ‘arm’ to ‘forelimb’” or “move ‘Parkinson disease’ under ‘neurodegenerative disease’.” We have also built a suite of tools for managing ontology changes. These include an automated agent that integrates with and monitors GitHub ontology repositories and applies any requested changes and a new component in the BioPortal ontology resource that allows users to make change requests directly from within the BioPortal user interface. Overall, the KGCL data model, its CNL, and associated tooling allow for easier management and processing of changes associated with the development of ontologies and KGs.

96 KNOWLEDGE MANAGEMENT AND PRESERVATION↗

DOE OSTI2020

Gauges, loops, and polynomials for partition functions of graphical models

Graphical models represent multivariate and generally not normalized probability distributions. Computing the normalization factor, called the partition function, is the main inference challenge relevant to multiple statistical and optimization applications. The problem is #P-hard that is of an exponential complexity with respect to the number of variables. Here, aimed at approximating the partition function, we consider multi-graph models where binary variables and multivariable factors are associated with edges and nodes, respectively, of an undirected multi-graph. We suggest a new methodology for analysis and computations that combines the Gauge function technique from Chertkov and Chernyak with the technique developed in Anari and Oveis Gharan 2017 arXiv:1702.02937; Gurvits 2011 arXiv:1106.2844; Straszak and Vishnoi 2017 55th Annual Allerton Conf. on Communication, Control, and Computing, based on the recent progress in the field of real stable polynomials. We show that the Gauge function, representing a single-out term in a finite sum expression for the partition function which achieves extremum at the so-called belief-propagation gauge, has a natural polynomial representation in terms of gauges/variables associated with edges of the multi-graph. Moreover, Gauge function can be used to recover the partition function through a sequence of transformations allowing appealing algebraic and graphical interpretations. Algebraically, one step in the sequence consists of the application of a differential operator over gauges associated with an edge. Graphically, the sequence is interpreted as a repetitive elimination/contraction of edges resulting in multi-graph models on decreasing in size (number of edges) graphs with the same partition function as in the original multi-graph model. Even though the complexity of computing factors in the sequence of the derived multi-graph models and respective Gauge functions grow exponentially with the number of eliminated edges, polynomials associated with the new factors remain bi-stable if the original factors have this property. Moreover, we show that BP estimations in the sequence do not decrease, each low-bounding the partition function.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Co-design of Advanced Architectures for Graph Analytics using Machine Learning

A graph is an excellent way of representing relationships among entities. We can use graph analytics to synthesize and analyze such relational data, and extract relevant features that are useful for various tasks such as machine learning. Considering the crucial role of graph analytics in various domains, it is important and timely to investigate the right hardware configurations that can achieve optimal performance for graph workloads on future high-performance computing systems. Design space exploration studies facilitate the selection of appropriate configurations (e.g. memory) to achieve a desired system performance. Recently, the approach of accelerating graph analytics using persistent non-volatile memory has gained a lot of attention. Traditional system simulators such as Gem5 and NVMain can be used to explore the design space of these advanced memory architectures for graph workloads. However, these simulators are slow in execution thus limiting the efficiency of design space exploration studies. To overcome this challenge, we proposed a machine learning based approach to co-design advanced memory architectures for graph workloads. We tested our approach with DRAM, non-volatile memory, and hybrid memory (DRAM+NVM) using a breadth first search benchmark algorithm. Our results showed the applicability of the proposed machine learning based approach to the co-design of the advanced memory architectures. In this paper, we provide recommendations on selecting advanced memory architectures to achieve desired performance for graph workloads. We also discuss the performances of different machine learning models that were considered in this study.

Kurte, Kuldeep↗

DOE OSTI2022

ADAM: A web platform for graph-based modeling and optimization of supply chains

Modeling and optimization are essential tasks that arise in the analysis and design of supply chains (SCs). SC models are essential for understanding emergent behavior such as transactions between participants, inherent value of products exchanged, as well as impact of externalities (e.g., policy and climate) and of constraints. Unfortunately, most users of SC models have limited expertise in mathematical optimization, and this hinders the adoption of advanced decision-making tools. Here, in this work, we present ADAM, a web platform that enables the modeling and optimization of SCs. ADAM facilitates modeling by leveraging intuitive and compact graph-based abstractions that allow the user to express dependencies between locations, products, and participants. ADAM model objects serve as repositories of experimental, technology, and socio-economic data; moreover, the graph abstractions facilitate the organization and exchange of models and provides a natural framework for education and outreach. Here, we discuss the graph abstractions and software design principles behind ADAM, its key functional features and workflows, and application examples.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Enabling Real-Time Communication in Multi-Agent Systems: A Graph Neural Network Based Approach

Global connectivity enables effective coordination in Multi-Agent Systems (MAS). Solving these connection problems under hardware constraints is an NP-hard non-Euclidean Degree Constrained Minimum Spanning Tree (DCMST) problem. Prior MAS controllers coordinate team movement for task completion and collision avoidance; some considering Line-of-Sight (LOS) maintenance but prioritizing flexibility over guarantees. Evolutionary Algorithms (EA) have been shown to find good solutions for DCMST, but their performance degrades with larger populations required to support a large MAS. We present a method based on edge graph attention networks, trained offline to reduce online computation times. Empirical comparisons with greedy polynomial-time solvers and EA show that our method leverages latent graph information to consistently find constraint-satisfying solutions in less time.

connectivity maintenance↗

DOE OSTI2023

Multiscale graph neural network autoencoders for interpretable scientific machine learning

The goal of this work is to address two limitations in autoencoder-based models: latent space interpretability and compatibility with unstructured meshes. This is accomplished here with the development of a novel graph neural network (GNN) autoencoding architecture with demonstrations on complex fluid flow applications. To address the first goal of interpretability, the GNN autoencoder achieves reduction in the number nodes in the encoding stage through an adaptive graph reduction procedure. Further, this reduction procedure essentially amounts to flowfieldconditioned node sampling and sensor identification, and produces interpretable latent graph representations tailored to the flowfield reconstruction task in the form of so-called masked fields. These masked fields allow the user to (a) visualize where in physical space a given latent graph is active, and (b) interpret the time-evolution of the latent graph connectivity in accordance with the time-evolution of unsteady flow features (e.g. recirculation zones, shear layers) in the domain. To address the goal of unstructured mesh compatibility, the autoencoding architecture utilizes a series of multi-scale message passing (MMP) layers, each of which models information exchange among node neighborhoods at various lengthscales. The MMP layer, which augments standard single-scale message passing with learnable coarsening operations, allows the decoder to more efficiently reconstruct the flowfield from the identified regions in the masked fields. Analysis of latent graphs produced by the autoencoder for various model settings are conducted using unstructured snapshot data sourced from large-eddy simulations in a backward-facing step (BFS) flow configuration with an OpenFOAM-based flow solver at high Reynolds numbers.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

IRIS-MASH: Efficient Multi-device Asynchronous Multi-Stream Heterogeneous Computing

In the rapidly evolving field of high-performance computing (HPC), effectively leveraging heterogeneous devices through asynchronous task programming is paramount. This paper presents a robust asynchronous task programming model tailored for a multi-device, multi-stream execution environment that incorporates a diverse array of heterogeneous computing units, including GPUs from various vendors and other accelerators. Current state-of-the-art task programming models provide methodologies to support asynchronous task executions, but they typically handle homogeneous devices using native programming languages, while support for heterogeneous devices is limited to frameworks like OpenCL. This gap presents significant challenges in abstracting heterogeneous devices to harness their true asynchronous capabilities effectively using their native programming languages. By implementing asynchronous task execution, our model significantly boosts the performance of tiled algorithm task graphs through overlapping data transfers with computation and enabling the simultaneous execution of multiple kernels. We integrate this approach into a heterogeneous Intelligent Runtime System (IRIS) and assess its performance using a suite of tiled algorithm benchmarks from the heterogeneous math kernels library (MatRIS) based on IRIS. Experimental results demonstrate a performance improvement ranging from 1.6 × to 2 × over IRIS without asynchronous support, and a notable 22% performance enhancement compared to established runtime systems such as StarPU and PaRSEC. This approach significantly improves computation efficiency of HPC workflows and provides a solid base for future exploration and development in the area of asynchronous task programming in heterogeneous systems.

Miniskar, Narasinga Rao [ORNL] (ORCID:000000018259↗

DOE OSTI2022

On the structure of isometrically embeddable metric spaces

Since its popularization in the 1970s, the Fiedler vector of a graph has become a standard tool for clustering of the vertices of the graph. Recently, Mendel and Noar, Dumitriu and Radcliffe, and Radcliffe and Williamson have introduced geometric generalizations of the Fiedler vector. Motivated by questions stemming from their work, we provide structural characterizations for when a finite metric space can be isometrically embedded in a Hilbert space.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Towards scaling community detection on distributed-memory heterogeneous systems

Distributed multi-GPU systems pose significant challenges and opportunities for efficient execution of parallel applications. Graph algorithms are generally characterized by irregular memory accesses, low computation to communication ratios, and load balancing problems that are especially hard to address on multi-GPU systems. Graph community detection is an important problem in the emerging domain of graph analytics with numerous applications. In this paper, we present our ongoing work on distributed-memory multi-GPU implementation for graph community detection. Our work parallelizes the widely used (albeit serial) Louvain method on distributed multi-GPU platforms. Supported by an extensive set of experiments on a multi-GPU enabled supercomputer (OLCF Summit) and a single compute node (Nvidia DGX-2®), we demonstrate competitive performance to existing distributed-memory CPU-based implementation, and up to 6.5 better results than Nvidia RAPIDS® CUGRAPH. To the best of our knowledge, this work represents the first effort for community detection on distributed multi-GPU systems. Our approach and related findings can be extended to numerous other iterative graph algorithms on multi-GPU systems.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Graph-based design of irregular metamaterials

In the field of metamaterial research, random structures offer a novel and less conventional approach compared to traditional periodic designs. Designing random metamaterials is challenging when it comes to ensuring intercon- nectivity, which is essential for manufacturability. This study introduces an innovative framework for generating random metamaterials using graph al- gorithms, ensuring connectivity and adaptability across various base shapes, including cylinders, triangles, pyramids, and cubes. By employing graph algorithms, our framework enhances the intuitiveness and efficiency of de- sign representation and manipulation, streamlining the design process. The framework generates families of designs that exhibit a wide range of prop- erty magnitudes that can be adjusted intuitively by modifying the input parameters. The rapid design process allows many designs to be generated, offering the user a multitude of solutions around the target property range. The designs can be effectively implemented in various fields and subjected to diverse analytical studies, including static, dynamic, and eigenfrequency assessments. We illustrate computational results for two key properties (stiff- ness and acoustic impedance), showcasing the method’s effectiveness through examples ranging from rod-based to cube-based designs. Here, the framework not only advances metamaterial research but also creates new opportunities for innovation in fields requiring customized material properties.

36 MATERIALS SCIENCE↗