Search NASA⌕ Search

SEARCH · Search NASA

Results for “graph generation”

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 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Hybrid Attack Graph Generation with Graph Convolutional Deep-Q Learning

Critical infrastructures such as power grids have become increasingly complex, connected, and vulnerable to adverse scenarios, including cyber and physical attacks and faults. Effective risk mitigation for such cyber-physical energy systems (CPES), requires preemptive knowledge of likely adversarial attack scenarios. Hybrid Attack Graph (HAG) is a structured way to represent an adversarial scenario as an attack sequence using a threat model. However, the scarcity of documented attack sequences hinders analysts and CPES planners’ ability to identify credible attack scenarios for a given CPES. We propose a data-driven Graph Convolutional Deep-Q Network (GCDQ) to address this data challenge through generating HAGs. By leveraging limited real-world observations from the MITRE ATT&CK knowledge base, our GCDQ model synthesizes realistic graphs with the targeted attribute of minimum detectability via reinforcement learning. This generative model is the first step in creating a tool to substantially boost the attack sequence dataset and enhance the performance of CPS defense-related tasks by providing insights into likely attack sequences with given attributes.

deep learning, artificial intelligence↗
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 OSTI2022

Synthetic Data and Graph Generation for Modeling Adversarial Activity (Final Project Report)

The Data and Graph Generation for Modeling Adversary Activity (MAA) project developed a methodology along with scalable graph modeling and generation tools to produce realistic large-scale background activity graphs with embedded adversarial activity pathways. The technical report presents PNNL methodology, released datasets, lessons learned, and recommendations to develop graph analytic algorithms for structure-only and attributed knowledge graphs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Tackling the Challenges in Scene Graph Generation With Local-to-Global Interactions

In this work, we seek new insights into the underlying challenges of the scene graph generation (SGG) task. Quantitative and qualitative analysis of the visual genome (VG) dataset implies: 1) ambiguity: even if interobject relationship contains the same object (or predicate), they may not be visually or semantically similar; 2) asymmetry: despite the nature of the relationship that embodied the direction, it was not well addressed in previous studies; and 3) higher-order contexts: leveraging the identities of certain graph elements can help generate accurate scene graphs. Motivated by the analysis, we design a novel SGG framework, Local-to-global interaction networks (LOGINs). Locally, interactions extract the essence between three instances of subject, object, and background, while baking direction awareness into the network by explicitly constraining the input order of subject and object. Globally, interactions encode the contexts between every graph component (i.e., nodes and edges). Finally, Attract and Repel loss is utilized to fine-tune the distribution of predicate embeddings. By design, our framework enables predicting the scene graph in a bottom-up manner, leveraging the possible complementariness. To quantify how much LOGIN is aware of relational direction, a new diagnostic task called Bidirectional Relationship Classification (BRC) is also proposed. Overall, experimental results demonstrate that LOGIN can successfully distinguish relational direction than existing methods (in BRC task), while showing state-of-the-art results on the VG benchmark (in SGG task).

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1992

Software For Generating Graphs And Charts

Common Graphics Library (CGL) computer program designed to enable users to generate graphs and charts of quality sufficient for publication or optical projection. Quickly and easily generates linear, logarithmic, bar, pie, and composite charts. Features of linear charts include automatic scaling, increasing or decreasing numerical axes, and character axes. Features of pie charts include segment labels, exploded segments, and chart keys. One of general features, horizontal or vertical orientation of figures. Written in ANSI FORTRAN 77.

Hammond, Dana P.↗
DOE OSTI2024

Efficient Hybrid Attack Graph Generation for Cyber-Physical System Resilience Experimentation (Final Project Report)

HAGEN project has developed theory, algorithms, and capabilities to assist cyber physical system modelers and operators to perform system and device-level vulnerability assessment, risk assessment, impact assessment, and mitigation planning. The project generates hybrid attack graphs for Cyber-Physical System (CPS) resilience experimentation at desired scale and speed. The project will produce composite attack datasets, algorithms, and demonstrable prototypical tools, and a library of high-impact attack sequences for a given CPS of interest. This report provided overall summary of research and development performed between FY22-24.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗
DOE OSTI2022

Transactional Knowledge Graph Generation To Model Adversarial Activities

A Knowledge Graph (KG) is a formal and structured representation of facts, relationships, and semantic descriptions of a set of entities. Traditionally, KGs are used to describe metadata about entities and to provide additional context to target application results. Many real-world domains also involve temporal interactions between entities in addition to the metadata data. Modeling these attributed transactions is a critical requirement when using KGs in complex real-world applications. Modeling adversarial activities is one such application that develops methodology and tools to produce realistic large-scale background activity graphs that include embedded Weapons of Mass Destruction (WMD) activity patterns. We present a novel platform for constructing a transactional knowledge graph from a diverse set of sources. We present the core components and architecture of the framework, and a use case for generating a background knowledge graph and WMD activity template to evaluate network alignment and subgraph matching algorithms.

Purohit, Sumit↗
DOE OSTI2019

Graph Generation with a Focusing Lexicon

Reference datasets are an essential part of developing effective data exploration tools. Many reference datasets are synthetic in nature, seeding real-world properties into generation routines. Others are laboriously curated from original source materials. This is a time-consuming process that requires significant domain expertise all along the process. This paper presents a third path: deriving a network from real-world source materials using automated tools. By properly grounding the tools in a small collection of curated documents, a larger corpus be automatically processed with greater confidence. The end system leverages human knowledge (in the initial document curation), but with much less time commitment enabled by automation. Our ultimate goal is to produce reference datasets, derived from real-world data that capture aspects salient to a specific activity in the context of all of the activities in the data-set. Our reference datasets take the form of graphs.

Chandra Shekar, Mayanka↗
NASA NTRS1986

Program for Generating Graphs and Charts

Office Automation Pilot (OAP) Graphics Database system offers IBM personal computer user assistance in producing wide variety of graphs and charts and convenient data-base system, called chart base, for creating and maintaining data associated with graphs and charts. Thirteen different graphics packages available. Access graphics capabilities obtained in similar manner. User chooses creation, revision, or chartbase-maintenance options from initial menu; Enters or modifies data displayed on graphic chart. OAP graphics data-base system written in Microsoft PASCAL.

Ackerson, C. T.↗
DOE OSTI2020

A Scalable Parallel Hypergraph Generator (HyGen)

Graphs are extensively used to model real-world complex systems. An edge in a graph can model pairwise relationships. However, multiway relationships (connections between three or more vertices) are common in many complex systems such as cellular process, image segmentation, and circuit design. A graph edge cannot model multiway relationships. A hypergraph, which can connect more than two vertices, is thus a better option to model multiway relationships. A large-scale hypergraph analysis has the potential to find useful insights from a complex system and assist in knowledge discovery. Currently a limited number of hypergraphs exists that are representative of real-world datasets. Moreover, real-world hypergraph datasets are small in size and inadequate to incorporate future needs. A graph generator that can produce large-scale synthetic hypergraphs can solve the above mentioned problems. In this paper, we present a scalable parallel hypergraph generator (HyGen) based on the Message Passing Interface (MPI) standard. To generate hypergraphs, HyGen takes the following parameter values as inputs: i) number of vertices, ii) number of hyperedges, iii) number of clusters, iv) vertex distribution, v) hyperedge distribution, vi) local cluster cardinality, and vii) global cluster cardinality. We have demonstrated that HyGen can generate hypergraphs of various sizes in a scalable fashion. HyGen takes approximately four minutes to generate a hypergraph with 4.8 million vertices, 1.6 million hyperedges, and 800 clusters using 1,024 processes on a leadership class computing platform. Our strong and weak scaling experiments on supercomputers demonstrate that HyGen can quickly create large-scale hypergraphs in a parallel manner, thus providing a useful capability for hypergraph analysis.

Hasan, S M Shamimul↗
DOE OSTI2021

Fast GPU-Based Generation of Large Graph Networks From Degree Distributions

Synthetically generated, large graph networks serve as useful proxies to real-world networks for many graph-based applications. The ability to generate such networks helps overcome several limitations of real-world networks regarding their number, availability, and access. Here, we present the design, implementation, and performance study of a novel network generator that can produce very large graph networks conforming to any desired degree distribution. The generator is designed and implemented for efficient execution on modern graphics processing units (GPUs). Given an array of desired vertex degrees and number of vertices for each desired degree, our algorithm generates the edges of a random graph that satisfies the input degree distribution. Multiple runtime variants are implemented and tested: 1) a uniform static work assignment using a fixed thread launch scheme, 2) a load-balanced static work assignment also with fixed thread launch but with cost-aware task-to-thread mapping, and 3) a dynamic scheme with multiple GPU kernels asynchronously launched from the CPU. The generation is tested on a range of popular networks such as Twitter and Facebook, representing different scales and skews in degree distributions. Results show that, using our algorithm on a single modern GPU (NVIDIA Volta V100), it is possible to generate large-scale graph networks at rates exceeding 50 billion edges per second for a 69 billion-edge network. GPU profiling confirms high utilization and low branching divergence of our implementation from small to large network sizes. For networks with scattered distributions, we provide a coarsening method that further increases the GPU-based generation speed by up to a factor of 4 on tested input networks with over 45 billion edges.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Distribution System Dataset Generator for AI Applications [SWR-24-75]

This software is a simple, light-weight python package to generate pytorch compatible machine learning graph dataset representing electric power distribution system. User is able to use these graph datasets to test their graph generation artificial intelligence (AI) models, link prediction AI models, graph classification AI models and so much more. This package uses grid-data-models (https://github.com/NREL-Distribution-Suites/grid-data-models) as input data format for power distribution system. NREL-Ditto (https://github.com/NREL-Distribution-Suites/ditto) tool can be leveraged to transform popular distribution system file formats such as opendss, cyme and synergi to grid-data-models.

Duwadi, Kapil↗
DOE OSTI2023

TransformerG2G: Adaptive time-stepping for learning temporal graph embeddings using transformers

Dynamic graph embedding has emerged as a very effective technique for addressing diverse temporal graph analytic tasks (i.e., link prediction, node classification, recommender systems, anomaly detection, and graph generation) in various applications. Such temporal graphs exhibit heterogeneous transient dynamics, varying time intervals, and highly evolving node features throughout their evolution. Hence, incorporating long-range dependencies from the historical graph context plays a crucial role in accurately learning their temporal dynamics. In this paper, we develop a graph embedding model with uncertainty quantification, TransformerG2G, by exploiting the advanced transformer encoder to first learn intermediate node representations from its current state (t) and previous context (over timestamps [t–1,t–l], l is the length of context). Moreover, we employ two projection layers to generate lower-dimensional multivariate Gaussian distributions as each node's latent embedding at timestamp t. We consider diverse benchmarks with varying levels of "novelty" as measured by the TEA (Temporal Edge Appearance) plots. Here, our experiments demonstrate that the proposed TransformerG2G model outperforms conventional multi-step methods and our prior work (DynG2G) in terms of both link prediction accuracy and computational efficiency, especially for high degree of novelty. Furthermore, the learned time-dependent attention weights across multiple graph snapshots reveal the development of an automatic adaptive time stepping enabled by the transformer. Importantly, by examining the attention weights, we can uncover temporal dependencies, identify influential elements, and gain insights into the complex interactions within the graph structure. For example, we identified a strong correlation between attention weights and node degree at the various stages of the graph topology evolution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Clustering and Cliques in Preferential Attachment Random Graphs with Edge Insertion

In this paper, we investigate the global clustering coefficient (a.k.a transitivity) and clique number of graphs generated by a preferential attachment random graph model with an additional feature of allowing edge connections between existing vertices. Specifically, at each time step t, either a new vertex is added with probability f(t), or an edge is added between two existing vertices with probability 1 – f(t). We establish concentration inequalities for the global clustering and clique number of the resulting graphs under the assumption that f(t) is a regularly varying function at infinity with index of regular variation –$\gamma$, where $\gamma$ $\in$ [0, 1). Finally, we also demonstrate an inverse relation between these two statistics: the clique number is essentially the reciprocal of the global clustering coefficient.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

FeederGAN: Synthetic Feeder Generation via Deep Graph Adversarial Nets

This paper presents a novel, automated, generative adversarial networks (GAN) based synthetic feeder generation mechanism, abbreviated as FeederGAN. FeederGAN digests real feeder models represented by directed graphs via a deep learning framework powered by GAN and graph convolutional networks (GCN). Information of a distribution feeder circuit is extracted from its model input files so that the device connectivity is mapped onto the adjacency matrix and the device characteristics, such as circuit types (i.e., 3-phase, 2-phase, and 1-phase) and component attributes (e.g., length and current ratings), are mapped onto the attribute matrix. Then, Wasserstein distance is used to optimize the GAN and GCN is used to discriminate the generated graphs from the actual ones. A greedy method based on graph theory is developed to reconstruct the feeder using the generated adjacency and attribute matrices. Furthermore, our results show that the GAN generated feeders resemble the actual feeder in both topology and attributes verified by visual inspection and by empirical statistics obtained from actual distribution feeders.

42 ENGINEERING↗
DOE OSTI2024

Efficient graph representation framework for chemical molecule similarity tasks

Graph data has emerged in numerous scientific domains and machine learning techniques have been widely used for analysis and learning of diverse data for prediction and decision. Machine learning techniques can readily address complex problems by leveraging their structural information. But graphs cannot be directly used for existing machine learning algorithms unless encoded as vectors. The problem of efficient representation of graphs is a substantial challenge in graph machine learning. In this paper, we propose a novel two-stage framework for the representation of chemical molecule graphs based on the strengths of Graph Isomorphism Networks (GINs) and Siamese autoencoders. In the first stage, the GIN model is constructed and trained using the structural information of chemical molecule graphs. Node attributes, edge attributes, and edge indices are used as input data, while graph attributes are used as labels. The GIN model effectively captures the structural characteristics of graphs and can accurately predict graph attributes, i.e., molecular properties. It also generates Graph Embeddings, represented as vectors that encode the structural information of graphs. In the second stage, Graph Embedding vectors are further optimized for downstream similarity tasks while preserving the graph structural information. The Siamese autoencoder is constructed and trained, which reduces the dimensionality of the Graph Embedding vectors, while maximizing the preservation of structural information in the original high-dimensional vectors. The resulting low-dimensional Graph Embeddings can be effectively utilized for tasks such as approximate nearest neighbor search. The experimental results demonstrate the effectiveness of our proposed framework in accurately predicting graph similarity.

Ma, Jiaji↗
DOE OSTI2021

Loop amplitudes monodromy relations and color-kinematics duality

Color-kinematics duality is a remarkable conjectured property of gauge theory which, together with double copy, is at the heart of a wealth of new developments in scattering amplitudes. So far, its validity has been verified in most cases only empirically, with limited ab initio understanding beyond tree-level. In this paper we provide initial steps in a first-principle understanding of color-kinematics duality and double-copy at loop level, through a detailed analysis of the field-theory limit of the monodromy relations of string theory at one loop. In this limit, we dissect the type of Feynman graphs generated and the relations they obey. We find that graphs with contact-terms are unavoidable and are generated in the field theory limit of “bulk” contours which do not have a standard physical interpretation in string perturbation theory. We show how they are related to ambiguities in the definition of the loop momentum and that their role is precisely to cancel those ambiguities.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗