Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph clustering”

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.

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

At least 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

TX$^2$: Transformer eXplainability and eXploration

The Transformer eXplainability and eXploration (Martindale & Stewart, 2021), or TX 2 software package, is a library designed for artificial intelligence researchers to better understand the performance of transformer models (Vaswani et al., 2017) used for sequence classification. The tool is capable of integrating with a trained transformer model and a dataset split into training and testing populations to produce an ipywidget (Project Jupyter Contributors, 2021) dashboard with a number of visualizations to understand model performance with an emphasis on explainability and interpretability. The TX 2 package is primarily intended to integrate into a workflow centered around Jupyter Notebooks (Kluyver et al., 2016), and currently assumes the use of PyTorch (Paszke et al., 2019) and Hugging Face transformers library (Wolf et al., 2020). The dashboard includes visualization and data exploration features to aid researchers, including an interactive UMAP embedding graph (McInnes et al., 2018) to understand classification clusters, a word salience map that can be updated as researchers alter textual entries in near real time, a set of tools to understand word frequency and importance based on the clusters in the UMAP embedding graph, and a set of traditional confusion matrix analysis tools.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Randomized Cholesky Preconditioning for Graph Partitioning Applications

A graph is a mathematical representation of a network; we say it consists of a set of vertices, which are connected by edges. Graphs have numerous applications in various fields, as they can model all sorts of connections, processes, or relations. For example, graphs can model intricate transit systems or the human nervous system. However, graphs that are large or complicated become difficult to analyze. This is why there is an increased interest in the area of graph partitioning, reducing the size of the graph into multiple partitions. For example, partitions of a graph representing a social network might help identify clusters of friends or colleagues. Graph partitioning is also a widely used approach to load balancing in parallel computing. The partitioning of a graph is extremely useful to decompose the graph into smaller parts and allow for easier analysis. There are different ways to solve graph partitioning problems. For this work, we focus on a spectral partitioning method which forms a partition based upon the eigenvectors of the graph Laplacian (details presented in Acer, et. al.). This method uses the LOBPCG algorithm to compute these eigenvectors. LOBPCG can be accelerated by an operator called a preconditioner. For this internship, we evaluate a randomized Cholesky (rchol) preconditioner for its effectiveness on graph partitioning problems with LOBPCG. We compare it with two standard preconditioners: Jacobi and Incomplete Cholesky (ichol). This research was conducted from August to December 2021 in conjunction with Sandia National Laboratories.

97 MATHEMATICS AND COMPUTING↗
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 OSTI2020

TripleGraph

RDF triplestores are great tools for online graph analytic processing (i.e., graph pattern query processing), but they do not provide graph mining capabilities (e.g., PageRank, connected-component analysis, node eccentricity, etc.). The software title “TripleGraph” is a graph analysis toolkit, which uses an RDF triplestore as its backend for creating, manipulating, mining, and programming with large scale property graphs. It allows users to run various graph mining algorithms easily. User can import edgelist-formatted (homogeneous graph) or JSON-formatted graph (property graph) into the RDF triplestore using the provided tool and perform various analysis such as (1) Node/edge retrieval and manipulation, (2) Pathfinding between two given nodes, (3) Running graph mining algorithms (PageRank/Personalized PageRank, Single Source Shortest Path/Multi-Source Shortest Path, Connected Component, Node Eccentricity, Peer Pressure Clustering). It supports standard graph data format and works with a standard SPARQL endpoint like Jena Fuseki. It allows users to perform online graph analytic processing and graph mining on the same platform (a triplestore).

Sangkeun, MattLee↗
DOE OSTI2014

Efficient Extraction of High Centrality Vertices in Distributed Graphs

Betweenness centrality (BC) is an important measure for identifying high value or critical vertices in graphs, in variety of domains such as communication networks, road networks, and social graphs. However, calculating betweenness values is prohibitively expensive and, more often, domain experts are interested only in the vertices with the highest centrality values. In this paper, we first propose a partition-centric algorithm (MS-BC) to calculate BC for a large distributed graph that optimizes resource utilization and improves overall performance. Further, we extend the notion of approximate BC by pruning the graph and removing a subset of edges and vertices that contribute the least to the betweenness values of other vertices (MSL-BC), which further improves the runtime performance. We evaluate the proposed algorithms using a mix of real-world and synthetic graphs on an HPC cluster and analyze its strengths and weaknesses. The experimental results show an improvement in performance of upto 12x for large sparse graphs as compared to the state-of-the-art, and at the same time highlights the need for better partitioning methods to enable a balanced workload across partitions for unbalanced graphs such as small-world or power-law graphs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

A three-phase workflow for general and expressive representations of nondeterminism in HPC applications

Nondeterminism is an increasingly entrenched property of high-performance computing (HPC) applications and has recently been shown to seriously hamper debugging and reproducibility efforts. Additionally, tools for addressing the nondeterministic debugging problem have emerged, but they do not provide methods for systematically cataloging the nondeterminism in a given application. We propose a three-phase workflow for representing executions of nondeterministic message passing interface programs as event graphs, quantifying their structural similarity with graph kernels, and applying machine learning techniques to investigate shared properties across applications. We present an empirical study comparing two graph kernels’ suitability for this task and propose future uses of the methodology.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

SORA: Scalable Overlap-graph Reduction Algorithms for Genome Assembly using Apache Spark in the Cloud

The advent of high-throughput DNA sequencing techniques has permitted very high quality de novo assemblies of genomes, but raise an issue of requiring large amounts of computer memory to resolve the large genome graphs generated by most overlap graph de novo assemblers. To address these limitations, we present a novel algorithmic approach; Scalable Overlap-graph Reduction Algorithms (SORA). SORA adapts string graph reduction algorithms for the genome assembly using a distributed computing platform. To efficiently compute coverage for enormous paths in the graphs, SORA uses Apache Spark which is a cluster-based engine designed on top of Hadoop to handle very large datasets in the cloud. The experimental results show that SORA can process a nearly one billion edge graph in a distributed cloud cluster as well as smaller graphs on a local cluster with a short turnaround time. Moreover, our algorithms scale almost linearly with increasing numbers of virtual instances in the cloud. SORA is freely available for download at https://github.com/BioHPC/SORA/.

Paul, Alexander↗
DOE OSTI2021

Hierarchical effects facilitate spreading processes on synthetic and empirical multilayer networks

In this paper we consider the effects of corporate hierarchies on innovation spread across multilayer networks, modeled by an elaborated SIR framework. We show that the addition of management layers can significantly improve spreading processes on both random geometric graphs and empirical corporate networks. Additionally, we show that utilizing a more centralized working relationship network rather than a strict administrative network further increases overall innovation reach. In fact, this more centralized structure in conjunction with management layers is essential to both reaching a plurality of nodes and creating a stable adopted community in the long time horizon. Further, we show that the selection of seed nodes affects the final stability of the adopted community, and while the most influential nodes often produce the highest peak adoption, this is not always the case. In some circumstances, seeding nodes near but not in the highest positions in the graph produces larger peak adoption and more stable long-time adoption.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2013

Analysis of Molecular Clusters in Simulations of Lithium-Ion Battery Electrolytes

Graph theoretic tools were used to identify and classify clusters of ions and solvent molecules in molecular dynamics simulations of lithium-ion battery electrolytes. Electrolytes composed of various concentrations of LiPF6 dissolved in ethylene carbonate (EC), dimethylene carbonate (DMC), or a 1:1 EC/DMC mixture were simulated at multiple temperatures using classical molecular dynamics. Contrary to Nernst–Einstein theory but consistent with experiment, pure DMC systems had the greatest diffusivity but the lowest conductivity. This disagreement with Nernst–Einstein theory is explained by the observed clustering behavior, which found that systems with pure EC as a solvent formed ion clusters with nonzero charge, whereas systems with pure DMC as a solvent formed primarily neutral clusters.

25 ENERGY STORAGE↗
DOE OSTI2022

Deep structural clustering for single-cell RNA-seq data jointly through autoencoder and graph neural network

Abstract Single-cell RNA sequencing (scRNA-seq) permits researchers to study the complex mechanisms of cell heterogeneity and diversity. Unsupervised clustering is of central importance for the analysis of the scRNA-seq data, as it can be used to identify putative cell types. However, due to noise impacts, high dimensionality and pervasive dropout events, clustering analysis of scRNA-seq data remains a computational challenge. Here, we propose a new deep structural clustering method for scRNA-seq data, named scDSC, which integrate the structural information into deep clustering of single cells. The proposed scDSC consists of a Zero-Inflated Negative Binomial (ZINB) model-based autoencoder, a graph neural network (GNN) module and a mutual-supervised module. To learn the data representation from the sparse and zero-inflated scRNA-seq data, we add a ZINB model to the basic autoencoder. The GNN module is introduced to capture the structural information among cells. By joining the ZINB-based autoencoder with the GNN module, the model transfers the data representation learned by autoencoder to the corresponding GNN layer. Furthermore, we adopt a mutual supervised strategy to unify these two different deep neural architectures and to guide the clustering task. Extensive experimental results on six real scRNA-seq datasets demonstrate that scDSC outperforms state-of-the-art methods in terms of clustering accuracy and scalability. Our method scDSC is implemented in Python using the Pytorch machine-learning library, and it is freely available at https://github.com/DHUDBlab/scDSC.

Gan, Yanglan↗
DOE OSTI2022

A quantum processor based on coherent transport of entangled atom arrays

The ability to engineer parallel, programmable operations between desired qubits within a quantum processor is key for building scalable quantum information systems. In most state-of-the-art approaches, qubits interact locally, constrained by the connectivity associated with their fixed spatial layout. Here we demonstrate a quantum processor with dynamic, non-local connectivity, in which entangled qubits are coherently transported in a highly parallel manner across two spatial dimensions, between layers of single- and two-qubit operations. Our approach makes use of neutral atom arrays trapped and transported by optical tweezers; hyperfine states are used for robust quantum information storage, and excitation into Rydberg states is used for entanglement generation. We use this architecture to realize programmable generation of entangled graph states, such as cluster states and a seven-qubit Steane code state. Furthermore, we shuttle entangled ancilla arrays to realize a surface code state with thirteen data and six ancillary qubits and a toric code state on a torus with sixteen data and eight ancillary qubits. Finally, we use this architecture to realize a hybrid analogue–digital evolution and use it for measuring entanglement entropy in quantum simulations, experimentally observing non-monotonic entanglement dynamics associated with quantum many-body scars. Realizing a long-standing goal, these results provide a route towards scalable quantum processing and enable applications ranging from simulation to metrology.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Improved particle-flow event reconstruction with scalable neural networks for current and future particle detectors

Abstract Efficient and accurate algorithms are necessary to reconstruct particles in the highly granular detectors anticipated at the High-Luminosity Large Hadron Collider and the Future Circular Collider. We study scalable machine learning models for event reconstruction in electron-positron collisions based on a full detector simulation. Particle-flow reconstruction can be formulated as a supervised learning task using tracks and calorimeter clusters. We compare a graph neural network and kernel-based transformer and demonstrate that we can avoid quadratic operations while achieving realistic reconstruction. We show that hyperparameter tuning significantly improves the performance of the models. The best graph neural network model shows improvement in the jet transverse momentum resolution by up to 50% compared to the rule-based algorithm. The resulting model is portable across Nvidia, AMD and Habana hardware. Accurate and fast machine-learning based reconstruction can significantly improve future measurements at colliders.

Physics↗
DOE OSTI2022

DFSynthesizer: Dataflow-based Synthesis of Spiking Neural Networks to Neuromorphic Hardware

Spiking Neural Networks (SNNs) are an emerging computation model that uses event-driven activation and bio-inspired learning algorithms. SNN-based machine learning programs are typically executed on tile-based neuromorphic hardware platforms, where each tile consists of a computation unit called a crossbar, which maps neurons and synapses of the program. However, synthesizing such programs on an off-the-shelf neuromorphic hardware is challenging. This is because of the inherent resource and latency limitations of the hardware, which impact both model performance, e.g., accuracy, and hardware performance, e.g., throughput. We propose DFSynthesizer, an end-to-end framework for synthesizing SNN-based machine learning programs to neuromorphic hardware. The proposed framework works in four steps. First, it analyzes a machine learning program and generates SNN workload using representative data. Second, it partitions the SNN workload and generates clusters that fit on crossbars of the target neuromorphic hardware. Third, it exploits the rich semantics of the Synchronous Dataflow Graph (SDFG) to represent a clustered SNN program, allowing for performance analysis in terms of key hardware constraints such as number of crossbars, dimension of each crossbar, buffer space on tiles, and tile communication bandwidth. Finally, it uses a novel scheduling algorithm to execute clusters on crossbars of the hardware, guaranteeing hardware performance. We evaluate DFSynthesizer with 10 commonly used machine learning programs. Our results demonstrate that DFSynthesizer provides a much tighter performance guarantee compared to current mapping approaches.

Computer Science↗
DOE OSTI2019

Improving Performance of Multi-Area State Estimation Using Spectral Clustering

This paper investigates the problem of dividing a large power system into several areas to be solved by a state estimator which coordinates locally obtained decentralized estimates. By applying automatic partitioning to the utility system, the performance of the distributed state estimator can be improved as compared to the pre-defined utility control areas. The presented approach utilizes the spectral properties of the un-directed graph formed by assigning a vertex to every bus and an edge to every pair of buses connected by a line. The graph Laplacian matrix and associated eigenvectors and eigenvalues are used to cluster the graph vertices in such a way that each area has a large number of internal connections, but a small number of external connections. This approach is demonstrated using the IEEE 118 bus system.

Kelle, David↗
DOE OSTI2020

Track Seeding and Labelling with Embedded-space Graph Neural Networks

To address the unprecedented scale of HL-LHC data, the Exa.TrkX project is investigating a variety of machine learning approaches to particle track reconstruction. The most promising of these solutions, graph neural networks (GNN), process the event as a graph that connects track measurements (detector hits corresponding to nodes) with candidate line segments between the hits (corresponding to edges). Detector information can be associated with nodes and edges, enabling a GNN to propagate the embedded parameters around the graph and predict node-, edge- and graph-level observables. Previously, message-passing GNNs have shown success in predicting doublet likelihood, and we here report updates on the state-of-the-art architectures for this task. In addition, the Exa.TrkX project has investigated innovations in both graph construction, and embedded representations, in an effort to achieve fully learned end-to-end track finding. Hence, we present a suite of extensions to the original model, with encouraging results for hitgraph classification. In addition, we explore increased performance by constructing graphs from learned representations which contain non-linear metric structure, allowing for efficient clustering and neighborhood queries of data points. We demonstrate how this framework fits in with both traditional clustering pipelines, and GNN approaches. The embedded graphs feed into high-accuracy doublet and triplet classifiers, or can be used as an end-to-end track classifier by clustering in an embedded space. A set of post-processing methods improve performance with knowledge of the detector physics. Finally, we present numerical results on the TrackML particle tracking challenge dataset, where our framework shows favorable results in both seeding and track finding.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2015

Translating Non-Trivial Algorithms from the Circuit Model to the Measurement

We provide a set of prescriptions for implementing a circuit model algorithm as measurement based quantum computing via a large discrete cluster state constructed sequentially, from qubits implemented as single photons. We describe a large optical discrete graph state capable of searching logical 4 and 8 element lists as an example. To do so we have developed several prescriptions based on analytic evaluation of the evolution of discrete cluster states and graph state equations. We describe the cluster state as a sequence of repeated entanglement and measurement steps using a small number of single photons for each step. These prescriptions can be generalized to implement any logical circuit model operation with appropriate single photon measurements and feed forward error corrections. Such a cluster state is not guaranteed to be optimal (i.e. minimum number of photons, measurements, run time).

Smith, IV, Amos M↗
DOE OSTI2024

Unsupervised learning-enabled pulsed infrared thermographic microscopy of subsurface defects in stainless steel

Metallic structures produced with laser powder bed fusion (LPBF) additive manufacturing method (AM) frequently contain microscopic porosity defects, with typical approximate size distribution from one to 100 microns. Presence of such defects could lead to premature failure of the structure. In principle, structural integrity assessment of LPBF metals can be accomplished with nondestructive evaluation (NDE). Pulsed infrared thermography (PIT) is a non-contact, one-sided NDE method that allows for imaging of internal defects in arbitrary size and shape metallic structures using heat transfer. PIT imaging is performed using compact instrumentation consisting of a flash lamp for deposition of a heat pulse, and a fast frame infrared (IR) camera for measuring surface temperature transients. However, limitations of imaging resolution with PIT include blurring due to heat diffusion, sensitivity limit of the IR camera. We demonstrate enhancement of PIT imaging capability with unsupervised learning (UL), which enables PIT microscopy of subsurface defects in high strength corrosion resistant stainless steel 316 alloy. PIT images were processed with UL spatial–temporal separation-based clustering segmentation (STSCS) algorithm, refined by morphology image processing methods to enhance visibility of defects. The STSCS algorithm starts with wavelet decomposition to spatially de-noise thermograms, followed by UL principal component analysis (PCA), fine-tuning optimization, and neural learning-based independent component analysis (ICA) algorithms to temporally compress de-noised thermograms. The compressed thermograms were further processed with UL-based graph thresholding K-means clustering algorithm for defects segmentation. The STSCS algorithm also includes online learning feature for efficient re-training of the model with new data. For this study, metallic specimens with calibrated microscopic flat bottom hole defects, with diameters in the range from 203 to 76 µm, were produced using electro discharge machining (EDM) drilling. While the raw thermograms do not show any material defects, using STSCS algorithm to process PIT images reveals defects as small as 101 µm in diameter. To the best of our knowledge, this is the smallest reported size of a sub-surface defect in a metal imaged with PIT, which demonstrates the PIT capability of detecting defects in the size range relevant to quality control requirements of LPBF-printed high-strength metals.

36 MATERIALS SCIENCE↗