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 163 records · Page 9
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Facial Named Entity Recognition by Attention-Based Graph Convolutional Neural Network

In the realm of facial recognition and analysis, the ability to accurately cluster large datasets of facial images stands as a cornerstone for various applications, ranging from security surveillance to user biometric identification. This project evolves a novel approach to facial data clustering by embedding facial images into a high-dimensional vector space using an advanced embedding model trained on separate data and assumes a graph-like structure on the high-dimensional vectors. We find our method works significantly better than common shallow methods.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Symbol alphabets from plabic graphs III: n = 9

Symbol alphabets of n-particle amplitudes in N = 4 super-Yang-Mills theory are known to contain certain cluster variables of G(4, n) as well as certain algebraic functions of cluster variables. In this paper we solve the C Z = 0 matrix equations associated to several cells of the totally non-negative Grassmannian, combining methods of arXiv:2012.15812 for rational letters and arXiv:2007.00646 for algebraic letters. We identify sets of parameterizations of the top cell of G + (5, 9) for which the solutions produce all of (and only) the cluster variable letters of the 2-loop nine-particle NMHV amplitude, and identify plabic graphs from which all of its algebraic letters originate.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2018

Symmetry and Topology Code of the Cluster Self-Assembly of Intermetallic Compounds A{sub 2}{sup [16]}B{sub 4}{sup [12]} of the Friauf Families Mg{sub 2}Cu{sub 4} and Mg{sub 2}Zn{sub 4}

A geometrical and topological analysis of intermetallic compounds A{sub 2}{sup [16]}B{sub 4}{sup [12]} of the Friauf families Mg{sub 2}Cu{sub 4} (formed in 273 binary and 775 ternary systems) and Mg{sub 2}Zn{sub 4} (formed in 67 binary and 121 ternary systems) has been performed. Basic 3D nets are determined in the form of a graph, whose sites correspond to the centers of tetrahedral cluster precursors В{sub 4}: Cu-type net with a coordination number (CN) of 12 for Mg{sub 2}Cu{sub 4} and a BN-type net with a CN of 8 for Mg{sub 2}Zn{sub 4}. The symmetry and topology code is determined for the crystal structure self-assembly in the following form: primary chain S{sub 3}{sup 1} → microlayer S{sub 3}{sup 2} → microframework S{sub 3}{sup 3}. An identical mechanism of primary chain S{sub 3}{sup 1} self-assembly from B{sub 4} clusters with participation of large template atoms A{sup [16]} for both families and a mechanism of S{sub 3}{sup 2} microlayer self-assembly from parallel S{sub 3}{sup 1} chains in Mg{sub 2}Cu{sub 4} (basic 2D net 4{sup 4}) and shifted chains in Mg{sub 2}Zn{sub 4} (basic 2D net 3{sup 6}) have been determined for the first time. The constant chemical composition of intermetallic compounds A{sub 2}{sup [16]}B{sub 4}{sup [12]} is related to the functional difference between the B atoms forming 3D frameworks and template atoms А. The numbers of chemically different В{sub 4} clusters for the Mg{sub 2}Cu{sub 4} and Mg{sub 2}Zn{sub 4} families are found to be 25 and 19, respectively.

36 MATERIALS SCIENCE↗
DOE OSTI2016

Designing networks: A mixed-integer linear optimization approach

Designing networks with specified collective properties is useful in a variety of application areas, enabling the study of how given properties affect the behavior of network models, the downscaling of empirical networks to workable sizes, and the analysis of network temporal evolution. Despite the importance of the task, there currently exists a gap in our ability to systematically generate networks that adhere to theoretical guarantees for the given property specifications. In this work, we propose the use of Mixed-Integer Linear Optimization modeling and solution methodologies to address this Network Generation Problem. We present useful modeling techniques and apply them to mathematically express and constrain a broad class of network properties in the context of an optimization formulation. We derive complete formulations for the generation of networks that attain specified levels of connectivity, spread, assortativity and robustness, and we illustrate these via a number of computational case studies.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2013

FEASTPACK v. 1.0

The software implements the generative graph algorithm described in the following reference: T. G. Kolda, A. Pinar, T. Plantenga and C. Seshadhri. A Scalable Generative Graph Model with Community Structure, arXiv:1302.6636, March 2013, http:l/arxiv.org/abs/1302.6636. The software also implements the clustering coefficient algorithms described in C. Seshadhri, A. Pinar and T. G. Kolda. Triadic Measures on Graphs: The Power of Wedge Sampling, in Proc. 2013 SIAM International Conference on Data Mining {SDM), May 2013.

None, SeshadhriComandur↗
DOE OSTI2020

ConnectIt: a framework for static and incremental parallel graph connectivity algorithms

Connected components is a fundamental kernel in graph applications. The fastest existing multicore algorithms for solving graph connectivity are based on some form of edge sampling and/or linking and compressing trees. However, many combinations of these design choices have been left unexplored. In this paper, we design the ConnectIt framework, which provides different sampling strategies as well as various tree linking and compression schemes. ConnectIt enables us to obtain several hundred new variants of connectivity algorithms, most of which extend to computing spanning forest. In addition to static graphs, we also extend ConnectIt to support mixes of insertions and connectivity queries in the concurrent setting. We present an experimental evaluation of ConnectIt on a 72-core machine, which we believe is the most comprehensive evaluation of parallel connectivity algorithms to date. Compared to a collection of state-of-the-art static multicore algorithms, we obtain an average speedup of 12.4x (2.36x average speedup over the fastest existing implementation for each graph). Using ConnectIt, we are able to compute connectivity on the largest publicly-available graph (with over 3.5 billion vertices and 128 billion edges) in under 10 seconds using a 72-core machine, providing a 3.1x speedup over the fastest existing connectivity result for this graph, in any computational setting. For our incremental algorithms, we show that our algorithms can ingest graph updates at up to several billion edges per second. To guide the user in selecting the best variants in ConnectIt for different situations, we provide a detailed analysis of the different strategies. Finally, we show how the techniques in ConnectIt can be used to speed up two important graph applications: approximate minimum spanning forest and SCAN clustering.

Computer Science↗
DOE OSTI2024

Decode the Workload: Training Deep Learning Models for Efficient Compute Cluster Representation

Monitoring the status of a high throughput computing cluster running computationally intensive production jobs is a crucial yet challenging system administration task due to the complexity of such systems. To this end, we train autoencoders using the Linux kernel CPU metrics of the cluster. Additionally, we explore assisting these models with graph neural networks to share information across threads within a compute node. The models are compared in terms of their ability to: 1) Produce a compressed latent representation that captures the salient features of the input, 2) Detect anomalous activity, and 3) Make distinction between different kinds of jobs run at Jefferson Lab. The goal is to have a robust encoder whose compressed embeddings are used for several downstream tasks. We extend this study further by deploying these models in a human-in-the-loop production-based setting for the anomaly detection task and discuss the associated implementation aspects such as continual learning and the criterion to generate alarms. This study represents a first step in the endeavor towards building self-supervised large-scale foundation models for computing centers.

Mohammed, Ahmed↗
NASA NTRS1991

The three-point correlation function for Abell clusters - Observations and simulations

Results are reported of a 3D study tracing the three-point correlation function of Abell clusters and of a comparison of this with the biased cold dark matter (CDM) simulations of Park (1990). For the observations, the maximum likelihood fits are Z11 = 0.85 and Q111 = 0.1, in excellent agreement with the result of the 2D study of Toth et al. (1989). For Park's simulation, maximum likelihood fits of Q11 = 0.9 and Q111 = 0.0 are found, which is in excellent agreement with the observational result. It is concluded that the standard biased CDM gravitational instability model reproduces the observed form of the three-point correlation functions for Abell clusters remarkably well. The number of triples as a function of the sides of triangles for Abell clusters, and the number of triples as a function of the sides of triangles for clusters in Park's simulation are illustrated on graphs.

Gott, J. R., III↗
DOE OSTI2013

FEASTPACK v. 1.0

The software implements the generative graph algorithm described in the following reference: T. G. Kolda, A. Pinar, T. Plantenga and C. Seshadhri. A Scalable Generative Graph Model with Community Structure, arXiv:1302.6636, March 2013, http:l/arxiv.org/abs/1302.6636. The software also implements the clustering coefficient algorithms described in C. Seshadhri, A. Pinar and T. G. Kolda. Triadic Measures on Graphs: The Power of Wedge Sampling, in Proc. 2013 SIAM International Conference on Data Mining {SDM), May 2013.

Source record↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques For Space Network Scalability

Routing in the space internet must face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this paper we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. We propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol (DTCP). In addition, we explore the underlying networking mechanisms such as multicast, neighbor discovery, and software defined networking that may be used to enable DTCP.

Delay Tolerant Networking↗
NASA NTRS2003

Scale-free Graphs for General Aviation Flight Schedules

In the late 1990s a number of researchers noticed that networks in biology, sociology, and telecommunications exhibited similar characteristics unlike standard random networks. In particular, they found that the cummulative degree distributions of these graphs followed a power law rather than a binomial distribution and that their clustering coefficients tended to a nonzero constant as the number of nodes, n, became large rather than O(1/n). Moreover, these networks shared an important property with traditional random graphs as n becomes large the average shortest path length scales with log n. This latter property has been coined the small-world property. When taken together these three properties small-world, power law, and constant clustering coefficient describe what are now most commonly referred to as scale-free networks. Since 1997 at least six books and over 400 articles have been written about scale-free networks. In this manuscript an overview of the salient characteristics of scale-free networks. Computational experience will be provided for two mechanisms that grow (dynamic) scale-free graphs. Additional computational experience will be given for constructing (static) scale-free graphs via a tabu search optimization approach. Finally, a discussion of potential applications to general aviation networks is given.

Alexandov, Natalia M.↗
DOE OSTI2020

Performance and usability enhancements for continuous subgraph matching queries on graph-structured data

A query graph, which includes vertices and edges, represents a query on graph-structured data. The query graph is decomposed into query subgraphs. A network analysis tool performs continuous subgraph matching queries to facilitate analysis of computer network traffic, social media events, or other streams of data represented as a dynamic data graph (graph-structured data). This can help identify emerging trends in the data. Some features of the network analysis tool enhance performance by effectively utilizing distributed computing resources (including processing cores and memory at different nodes of a cluster) to speed up the process of updating the dynamic data graph and detecting matches of query subgraphs. Features of a query graph building tool enhance usability by providing intuitive ways to specify query graphs and their subgraphs. Features of a results visualization tool enhance usability by providing an intuitive way to present the results of continuous subgraph matching queries.

Choudhury, Sutanay↗
DOE OSTI2015

A Visual Analytics Paradigm Enabling Trillion-Edge Graph Exploration

We present a visual analytics paradigm and a system prototype for exploring web-scale graphs. A web-scale graph is described as a graph with ~one trillion edges and ~50 billion vertices. While there is an aggressive R&D effort in processing and exploring web-scale graphs among internet vendors such as Facebook and Google, visualizing a graph of that scale still remains an underexplored R&D area. The paper describes a nontraditional peek-and-filter strategy that facilitates the exploration of a graph database of unprecedented size for visualization and analytics. We demonstrate that our system prototype can 1) preprocess a graph with ~25 billion edges in less than two hours and 2) support database query and visualization on the processed graph database afterward. Based on our computational performance results, we argue that we most likely will achieve the one trillion edge mark (a computational performance improvement of 40 times) for graph visual analytics in the near future.

graph visualization↗
DOE OSTI2021

ARENA: Asynchronous Reconfigurable Accelerator Ring to Enable Data-Centric Parallel Computing

The next generation HPC and data centers are likely to be reconfigurable and data-centric due to the trend of hardware specialization and the emergence of data-driven applications. In this work, we propose ARENA – an asynchronous reconfigurable accelerator ring architecture as a potential scenario on how the future HPC and data centers will be like. Despite using the coarse-grained reconfigurable arrays (CGRAs) as the substrate platform, our key contribution is not only the CGRA-cluster design itself, but also the ensemble of a new architecture and programming model that enables asynchronous tasking across a cluster of reconfigurable nodes, so as to bring specialized computation to the data rather than the reverse. We presume distributed data storage without asserting any prior knowledge on the data distribution. Hardware specialization occurs at runtime when a task finds the majority of data it requires are available at the present node. In other words, we dynamically generate specialized CGRA accelerators where the data reside. The asynchronous tasking for bringing computation to data is achieved by circulating the task token, which describes the dataflow graphs to be executed for a task, among the CGRA cluster connected by a fast ring network. Evaluations on a set of HPC and data-driven applications across different domains show that ARENA can provide better parallel scalability with reduced data movement (53.9 percent). Compared with contemporary compute-centric parallel models, ARENA can bring on average 4.37× speedup. The synthesized CGRAs and their task-dispatchers only occupy 2.93mm 2 chip area under 45nm process technology and can run at 800MHz with on average 759.8mW power consumption. ARENA also supports the concurrent execution of multi-applications, offering ideal architectural support for future high-performance parallel computing and data analytics systems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Sachdev-Ye-Kitaev model on a noisy quantum computer

Here we study the SYK model -- an important toy model for quantum gravity on IBM's superconducting qubit quantum computers. By using a graph-coloring algorithm to minimize the number of commuting clusters of terms in the qubitized Hamiltonian, we find the gate complexity of the time evolution using the first-order product formula for N Majorana fermions is $\mathscr{O}$(N 5 J 2 t 2 /ε) where J is the dimensionful coupling parameter, t is the evolution time, and ε is the desired precision. With this improved resource requirement, we perform the time evolution for N=6,8 with maximum two-qubit circuit depth of 343. We perform different error mitigation schemes on the noisy hardware results and find good agreement with the exact diagonalization results on classical computers and noiseless simulators. In particular, we compute return probability after time t and out-of-time order correlators (OTOC) which is a standard observable of quantifying the chaotic nature of quantum systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Graph identification of proteins in tomograms ( GRIP‐Tomo )

Abstract In this study, we present a method of pattern mining based on network theory that enables the identification of protein structures or complexes from synthetic volume densities, without the knowledge of predefined templates or human biases for refinement. We hypothesized that the topological connectivity of protein structures is invariant, and they are distinctive for the purpose of protein identification from distorted data presented in volume densities. Three‐dimensional densities of a protein or a complex from simulated tomographic volumes were transformed into mathematical graphs as observables. We systematically introduced data distortion or defects such as missing fullness of data, the tumbling effect, and the missing wedge effect into the simulated volumes, and varied the distance cutoffs in pixels to capture the varying connectivity between the density cluster centroids in the presence of defects. A similarity score between the graphs from the simulated volumes and the graphs transformed from the physical protein structures in point data was calculated by comparing their network theory order parameters including node degrees, betweenness centrality, and graph densities. By capturing the essential topological features defining the heterogeneous morphologies of a network, we were able to accurately identify proteins and homo‐multimeric complexes from 10 topologically distinctive samples without realistic noise added. Our approach empowers future developments of tomogram processing by providing pattern mining with interpretability, to enable the classification of single‐domain protein native topologies as well as distinct single‐domain proteins from multimeric complexes within noisy volumes.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2025

Uncovering Structure–Conductivity Relationships in Anion Exchange Membranes (AEMs) Using Interpretable Machine Learning

Anion exchange membranes (AEMs) play a vital role in the performance of water electrolyzers and fuel cells, yet their discovery and optimization remain challenging due to the complexity of structure–property relationships. In this study, we introduce a machine learning framework that leverages conditional graph neural networks (cGNNs) and descriptor-based models and a hybrid graph neural network (HGARE) to predict and interpret ionic conductivity. The descriptor-based pipeline employs principal component analysis (PCA), ablation, and SHAP analysis to identify factors governing anion conductivity, revealing electronic, topological, and compositional descriptors as key contributors. Beyond prediction, dimensionality reduction and clustering are performed by employing t-SNE and KMeans as well as SOM, which reveal distinct membranes clusters, some of which were enriched with high anion conductivity. Among graph-based approaches, the graph convolutional (GCN) achieved strong predictive performance, while the Hybrid Graph Autoencoder-Regressor Ensemble (HGARE) achieved the highest accuracy. Additionally, atom-level saliency maps from GCN provide spatial explanations for conductive behavior, revealing the importance of polarizable and flexible regions. This work contributes to the accelerated and data-driven design of high-performance AEMs.

Naghshnejad, Pegah [Department of Chemical Enginee↗