SEARCH · Search NASA

Results for “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 163 records · Page 9

All sources NASA NTRS DOE OSTI

DOE OSTI2022

Augmenting Graph Convolution with Distance Preserving Embedding for Improved Learning

Graph convolution incorporates topological information of a graph into learning. Message passing corresponds to traversal of a local neighborhood in classical graph algorithms. We show that incorporating additional global structures, such as shortest paths, through distance preserving embedding can improve performance. Our approach, Gavotte, significantly improves the performance of a range of popular graph neu-ral networks such as GCN, GA T,Graph SAGE, and GCNII for transductive learning. Gavotte also improves the performance of graph neural networks for full-supervised tasks, albeit to a smaller degree. As high-quality embeddings are generated by Gavotte as a by-product, we leverage clustering algorithms on these embed dings to augment the training set and introduce Gavotte+. Our results of Gavotte+ on datasets with very few labels demonstrate the advantage of augmenting graph convolution with distance preserving embedding.

Cong, Guojing↗

DOE OSTI2021

Revisit the Scalability of Deep Auto-Regressive Models for Graph Generation

As a new promising approach to graph generations, deep auto-regressive graph generation has drawn increasing attention. It however has been commonly deemed as hard to scale up to work with large graphs. In existing studies, it is perceived that the consideration of the full non-local graph dependences is indispensable for this approach to work, which entails the needs for keeping the entire graph’s info in memory and hence the perceived “inherent” scalability limitation of the approach. This paper revisits the common perception. It proposes three ways to relax the dependences and conducts a series of empirical measurements. It concludes that the perceived “inherent” scalability limitation is a misperception; with the right design and implementation, deep auto-regressive graph generation can be applied to graphs much larger than the device memory. The rectified perception removes a fundamental barrier for this approach to meet practical needs.

Yang, Shuai↗

DOE OSTI2021

Scalable Comparative Visualization of Ensembles of Call Graphs

Optimizing the performance of large-scale parallel codes is critical for efficient utilization of computing resources. Code developers often explore various execution parameters, such as hardware configurations, system software choices, and application parameters, and are interested in detecting and understanding bottlenecks in different executions. They often collect hierarchical performance profiles represented as call graphs, which combine performance metrics with their execution contexts. The crucial task of exploring multiple call graphs together is tedious and challenging because of the many structural differences in the execution contexts and significant variability in the collected performance metrics (e.g., execution runtime). In this paper, we present Ensemble CallFlow to support the exploration of ensembles of call graphs using new types of visualizations, analysis, graph operations, and features. We introduce ensemble-Sankey , a new visual design that combines the strengths of resource-flow (Sankey) and box-plot visualization techniques. Whereas the resource-flow visualization can easily and intuitively describe the graphical nature of the call graph, the box plots overlaid on the nodes of Sankey convey the performance variability within the ensemble. Our interactive visual interface provides linked views to help explore ensembles of call graphs, e.g., by facilitating the analysis of structural differences, and identifying similar or distinct call graphs. Finally, we demonstrate the effectiveness and usefulness of our design through case studies on large-scale parallel codes.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2017

When Labels Fall Short: Property Graph Simulation via Blending of Network Structure and Vertex Attributes

Property graphs can be used to represent heterogeneous networks with attributed vertices and edges. Given one property graph, simulating another graph with same or greater size with identical statistical properties with respect to the attributes and connectivity is critical for privacy preservation and benchmarking purposes. In this work we tackle the problem of capturing the statistical dependence of the edge connectivity on the vertex labels and using the same distribution to regenerate property graphs of the same or expanded size in a scalable manner. However, accurate simulation becomes a challenge when the attributes do not completely explain the network structure. We propose the Property Graph Model (PGM) approach that uses an attribute (or label) augmentation strategy to mitigate the problem and preserve the graph connectivity as measured via degree distribution, vertex label distributions and edge connectivity. Our proposed algorithm is scalable with a linear complexity in the number of edges in the target graph. We illustrate the efficacy of the PGM approach in regenerating and expanding the datasets by leveraging two distinct illustrations.

Visweswara Sathanur, Arun↗

DOE OSTI2020

Topological Analysis of The SPOKE Graph

The SPOKE graph [2, 6] is a sparse decorated semantic graph representing a collection of knowledge collected in many scientific databases from the fields of healthcare, biochemistry, chemistry, biology, et cetera. This knowledge graph is stored as a relational dataset decorated with metadata on each constituent vertex and edge. Formally, the graph is G(V, E, D), where V is a set of n vertices V := {1, ..., n} and edges of the form (i, j) ϵ E for i, j ϵ V, and table D that for any item in V υ E stores unstructured data such as vertex/edge type, nature of a relationship, et cetera. D(i) = {data involving vertex i ϵ V}, and D(i, j) = {data involving edge (i, j) ϵ E}. Here, we treat the graph as undirected in the sense that a direct relationship for (i, j) causes a (possibly opposite) reverse direct relationship for (j, i). The SPOKE graph G(V, E, D) is formed by processing a collection of relational datasets from medicine, chemistry, and biology, connecting many entities. Here, we analyze an instance from 2019, Spoke-20190707, where a graph file contains 6.16M edges and associated metadata and a vertex file contains 2.15M vertices and the associated metadata. There are 12 different types of vertex entities; all edge types used are implicit (see §2). There is other metadata in D on edges and vertices, but we just use the topology and the vertex labels in this report. SPOKE is growing as more knowledge is gained and more datasets are added. SPOKE is likely to grow 10x during the next phase of this project, and we therefore would like to consider topoligical analysis techniques that are scalable to several orders of magnitude larger than the current dataset (say >1B edges).

59 BASIC BIOLOGICAL SCIENCES↗

NASA NTRS1971

On a programming language for graph algorithms

An algorithmic language, GRAAL, is presented for describing and implementing graph algorithms of the type primarily arising in applications. The language is based on a set algebraic model of graph theory which defines the graph structure in terms of morphisms between certain set algebraic structures over the node set and arc set. GRAAL is modular in the sense that the user specifies which of these mappings are available with any graph. This allows flexibility in the selection of the storage representation for different graph structures. In line with its set theoretic foundation, the language introduces sets as a basic data type and provides for the efficient execution of all set and graph operators. At present, GRAAL is defined as an extension of ALGOL 60 (revised) and its formal description is given as a supplement to the syntactic and semantic definition of ALGOL. Several typical graph algorithms are written in GRAAL to illustrate various features of the language and to show its applicability.

Rheinboldt, W. C.↗

NASA NTRS1991

A graph theoretic approach to scene matching

The ability to match two scenes is a fundamental requirement in a variety of computer vision tasks. A graph theoretic approach to inexact scene matching is presented which is useful in dealing with problems due to imperfect image segmentation. A scene is described by a set of graphs, with nodes representing objects and arcs representing relationships between objects. Each node has a set of values representing the relations between pairs of objects, such as angle, adjacency, or distance. With this method of scene representation, the task in scene matching is to match two sets of graphs. Because of segmentation errors, variations in camera angle, illumination, and other conditions, an exact match between the sets of observed and stored graphs is usually not possible. In the developed approach, the problem is represented as an association graph, in which each node represents a possible mapping of an observed region to a stored object, and each arc represents the compatibility of two mappings. Nodes and arcs have weights indicating the merit or a region-object mapping and the degree of compatibility between two mappings. A match between the two graphs corresponds to a clique, or fully connected subgraph, in the association graph. The task is to find the clique that represents the best match. Fuzzy relaxation is used to update the node weights using the contextual information contained in the arcs and neighboring nodes. This simplifies the evaluation of cliques. A method of handling oversegmentation and undersegmentation problems is also presented. The approach is tested with a set of realistic images which exhibit many types of sementation errors.

Ranganath, Heggere S.↗

NASA NTRS1990

Partitioning sparse matrices with eigenvectors of graphs

The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorithms for computing separators. Finally, the time required to compute the Laplacian eigenvector is reported, and the accuracy with which the eigenvector must be computed to obtain good separators is considered. The spectral algorithm has the advantage that it can be implemented on a medium-size multiprocessor in a straightforward manner.

Pothen, Alex↗

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 OSTI2021

Improved Bounds for Burning Fence Graphs

Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a graph. The burning process takes place in synchronous, discrete rounds. In each round, a fire breaks out at a vertex, and the fire spreads to all vertices that are adjacent to a burning vertex. Additionally, the burning number of a graph G is the minimum number of rounds necessary for each vertex of G to burn. We consider the burning number of the \(m \times n\) Cartesian grid graphs, written \(G_{m,n}\) . For \(m = \omega (\sqrt{n})\) , the asymptotic value of the burning number of \(G_{m,n}\) was determined, but only the growth rate of the burning number was investigated in the case \(m = O(\sqrt{n})\) , which we refer to as fence graphs. We provide new explicit bounds on the burning number of fence graphs \(G_{c\sqrt{n},n}\) , where \(c > 0\) .

79 ASTRONOMY AND ASTROPHYSICS↗

DOE OSTI2025

Quantum graph learning and algorithms applied in quantum computer sciences and image classification

Graph and network theory play a fundamental role in quantum computer sciences, including quantum information and computation. Random graphs and complex network theory are pivotal in predicting novel quantum phenomena, where entangled links are represented by edges. Quantum algorithms have been developed to enhance solutions for various network problems, giving rise to quantum graph computing and quantum graph learning (QGL). Here, in this review, we explore graph theory and graph learning methods as powerful tools for quantum computers to generate efficient solutions to problems beyond the reach of classical systems. We delve into the development of quantum complex network theory and its applications in quantum computation, materials discovery, and research. We also discuss quantum machine learning (QML) methodologies for effective image classification using qubits, quantum gates, and quantum circuits. Additionally, the paper addresses the challenges of QGL and algorithms, emphasizing the steps needed to develop flexible QGL solvers. This review presents a comprehensive overview of the fields of QGL and QML, highlights recent advancements, and identifies opportunities for future research.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2016

Solving Graph Laplacian Systems Through Recursive Bisections and Two-Grid Preconditioning

We present a parallelizable direct method for computing the solution to graph Laplacian-based linear systems derived from graphs that can be hierarchically bipartitioned with small edge cuts. For a graph of size n with constant-size edge cuts, our method decomposes a graph Laplacian in time O(n log n), and then uses that decomposition to perform a linear solve in time O(n log n). We then use the developed technique to design a preconditioner for graph Laplacians that do not have this property. Finally, we augment this preconditioner with a two-grid method that accounts for much of the preconditioner's weaknesses. We present an analysis of this method, as well as a general theorem for the condition number of a general class of two-grid support graph-based preconditioners. Numerical experiments illustrate the performance of the studied methods.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2017

A Visual Evaluation Study of Graph Sampling Techniques

We evaluate a dozen prevailing graph-sampling techniques with an ultimate goal to better visualize and understand big and complex graphs that exhibit different properties and structures. The evaluation uses eight benchmark datasets with four different graph types collected from Stanford Network Analysis Platform and NetworkX to give a comprehensive comparison of various types of graphs. The study provides a practical guideline for visualizing big graphs of different sizes and structures. The paper discusses results and important observations from the study.

Big graphs↗

DOE OSTI2020

Local structure graph models with higher-order dependence

Local structure graph models (LSGMs) describe random graphs and networks as a Markov random field (MRF)—each graph edge has a specified conditional distribution dependent on explicit neighbourhoods of other graph edges. Centered parameterizations of LSGMs allow for direct control and interpretation of parameters for large- and small-scale structures (e.g., marginal means vs. dependence). Here, we extend this parameterization to account for triples of dependent edges and illustrate the importance of centered parameterizations for incorporating covariates and interpreting parameters. Using a MRF framework, common exponential random graph models are also shown to induce conditional distributions without centered parameterizations and thereby have undesirable features. This work attempts to advance graph models through conditional model specifications with modern parameterizations, covariates and higher-order dependencies.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Hybrid Quantum–Classical Graph Transformers for Efficient Sentiment Analysis

Quantum Machine Learning (QML) offers a promising paradigm that leverages quantum computing principles to develop efficient and expressive models for learning from complex and structured data. Recent advances in natural language processing (NLP) and artificial intelligence (AI) have demonstrated capabilities in understanding, generating, and reasoning over linguistic and multimodal information. In this work, we present the Quantum Graph Transformer (QGT), a hybrid quantum–classical architecture that extends graph transformer capabilities through quantum self-attention. The QGT models variable-length sentences as token graphs, where both the embedding encoding and the self-attention mechanisms are implemented using parameterized quantum circuits (PQCs), enabling efficient contextual learning with significantly fewer trainable parameters. We train QGT using both fully connected and 𝑘 -nearest-neighbor graph structures and evaluate it on five benchmark sentiment-classification datasets. Experimental results show that QGT consistently achieves higher or comparable accuracy to existing quantum NLP models and outperforms a Classical Graph Transformer (CGT) baseline with identical architecture, achieving 29.4 × fewer parameters while requiring 3–5 × fewer samples to reach comparable performance. These findings highlight the potential of graph-based quantum models as scalable and data-efficient architectures for natural language understanding.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2017

EvoGraph: On-The-Fly Efficient Mining of Evolving Graphs on GPU

With the prevalence of the World Wide Web and social networks, there has been a growing interest in high performance analytics for constantly-evolving dynamic graphs. Modern GPUs provide massive AQ1 amount of parallelism for efficient graph processing, but the challenges remain due to their lack of support for the near real-time streaming nature of dynamic graphs. Specifically, due to the current high volume and velocity of graph data combined with the complexity of user queries, traditional processing methods by first storing the updates and then repeatedly running static graph analytics on a sequence of versions or snapshots are deemed undesirable and computational infeasible on GPU. We present EvoGraph, a highly efficient and scalable GPU- based dynamic graph analytics framework.

dynamic graphs↗

DOE OSTI2018

On Edge Exchangeable Random Graphs

We study a recent model for edge exchangeable random graphs introduced by Crane and Dempsey; in particular we study asymptotic properties of the random simple graph obtained by merging multiple edges. We study a number of examples, and show that the model can produce dense, sparse and extremely sparse random graphs. One example yields a power-law degree distribution. We give some examples where the random graph is dense and converges a.s. in the sense of graph limit theory, but also an example where a.s. every graph limit is the limit of some subsequence. Another example is sparse and yields convergence to a non-integrable generalized graphon defined on (0,∞).

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2021

Multilevel Graph Partitioning for Three-Dimensional Discrete Fracture Network Flow Simulations

We present a topology-based method for mesh-partitioning in three-dimensional discrete fracture network (DFN) simulations that takes advantage of the intrinsic multi-level nature of a DFN. DFN models are used to simulate flow and transport through low-permeability fractured media in the subsurface by explicitly representing fractures as discrete entities. The governing equations for flow and transport are numerically integrated on computational meshes generated on the interconnected fracture networks. Modern high-fidelity DFN simulations require high-performance computing on multiple processors where performance and scalability depends partially on obtaining a high-quality partition of the mesh to balance work-loads and minimize communication across all processors. The discrete structure of a DFN naturally lends itself to various graph representations, which can be thought of as coarse-scale representations of the computational mesh. Using this concept, we develop two applications of the multilevel graph partitioning algorithm to partition the mesh of a DFN. In the first, we project a partition of the graph based on the DFN topology onto the mesh of the DFN and in the second, this DFN-based projection is used as the initial condition for further partitioning refinement of the mesh. We compare the performance of these methods with standard multi-level graph partitioning using graph-based metrics (cut, imbalance, partitioning time), computational-based metrics (FLOPS, iterations, solver time), and total run time. The DFN-based and the mesh-based partitioning methods are comparable in terms of the graph-based metrics, but the time required to obtain the partition is several orders of magnitude faster using the DFN-based partitions. The computation-based metrics show comparable performance between both methods so, in combination, the DFN-based partitions are several orders of magnitude faster than the mesh-based partition. Furthermore, the method which uses the DFN-partition solution as the initial condition of the mesh partition provided cut and imbalance values that were close to the mesh-based partition but in a fraction of the time. In turn, this hybrid method outperformed both of the other methods in terms of the total run time.

58 GEOSCIENCES↗