Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graph sampling”

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 OSTI2017

Graph Sampling for Visual Analytics

Effectively visualizing large graphs and capturing the statistical properties are two challenging tasks. To aid in these two tasks, many sampling approaches for graph simplification have been proposed, falling into three categories: node sampling, edge sampling, and traversal-based sampling. It is still unknown which approach is the best. We evaluate commonly used graph sampling methods through a combined visual and statistical comparison of graphs sampled at various rates. We conduct our evaluation on three graph models: random graphs, small-world graphs, and scale-free graphs. Initial results indicate that the effectiveness of a sampling method is dependent on the graph model, the size of the graph, and the desired statistical property. This benchmark study can be used as a guideline in choosing the appropriate method for a particular graph sampling task, and the results presented can be incorporated into graph visualization and analysis tools.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Application-Specific Graph Sampling for Frequent Subgraph Mining and Community Detection

Graph mining is an important data analysis methodology, but struggles as the input graph size increases. The scalability and usability challenges posed by such large graphs make it imperative to sample the input graph and reduce its size. The critical challenge in sampling is to identify the appropriate algorithm to insure the resulting analysis does not suffer heavily from the data reduction. Predicting the expected performance degradation for a given graph and sampling algorithm is also useful. In this paper, we present different sampling approaches for graph mining applications such as Frequent Subgrpah Mining (FSM), and Community Detection (CD). We explore graph metrics such as PageRank, Triangles, and Diversity to sample a graph and conclude that for heterogeneous graphs Triangles and Diversity perform better than degree based metrics. We also present two new sampling variations for targeted graph mining applications. We present empirical results to show that knowledge of the target application, along with input graph properties can be used to select the best sampling algorithm. We also conclude that performance degradation is an abrupt, rather than gradual phenomena, as the sample size decreases. We present the empirical results to show that the performance degradation follows a logistic function.

Purohit, Sumit↗
DOE OSTI2020

C-SAW: a framework for graph sampling and random walk on GPUs

Many applications require to learn, mine, analyze and visualize large-scale graphs. These graphs are often too large to be addressed efficiently using conventional graph processing technologies. Fortunately, recent research efforts find out graph sampling and random walk, which significantly reduce the size of original graphs, can benefit the tasks of learning, mining, analyzing and visualizing large graphs by capturing the desirable graph properties. This paper introduces C-SAW, the first framework that accelerates Sampling and Random Walk framework on GPUs. Particularly, C-SAW makes three contributions: First, our framework provides a generic API which allows users to implement a wide range of sampling and random walk algorithms with ease. Second, offloading this framework on GPU, we introduce warp-centric parallel selection, and two novel optimizations for collision migration. Third, towards supporting graphs that exceed the GPU memory capacity, we introduce efficient data transfer optimizations for out-of-memory and multi-GPU sampling, such as workload-aware scheduling and batched multi-instance sampling. Taken together, our framework constantly outperforms the state of the art projects in addition to the capability of supporting a wide range of sampling and random walk algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Impact-Driven Sampling Strategies for Hybrid Attack Graphs

Cyber-Physical Systems (CPSs) have a large input space, with discrete and continuous elements across multiple layers. Hybrid Attack Graph (HAG) provide a flexible and efficient approach to generate attack sequences for a CPS. Analysis and testing of large-scale HAGs are prohibitively costly. We propose a dimension reduction via property-preserving multi-layer graph sampling algorithms. Existing property-preserving graph sampling approaches generate a representative subgraph of an original large-sized graph while preserving the key properties, such as node and edge distribution, clustering coefficients, and betweenness. On the other hand, we propose impact-driven sampling strategies to transform the input data to a lower-dimensional representation while retaining key properties of the data.

Subasi, Omer↗
DOE OSTI2024

AGS-GNN: Attribute-guided Sampling for Graph Neural Networks

We propose AGS-GNN, a novel attribute-guided sampling algorithm for Graph Neural Networks (GNNs) that exploits node features and connectivity structure of a graph while simultaneously adapting for both homophily and heterophily in graphs. (In homophilic graphs vertices of the same class are more likely to be connected, and vertices of different classes tend to be linked in heterophilic graphs.) While GNNs have been successfully applied to homophilic graphs, their application to heterophilic graphs remains challenging. The best-performing GNNs for heterophilic graphs do not fit the sampling paradigm, suffer high computational costs, and are not inductive. We employ samplers based on feature-similarity and feature-diversity to select subsets of neighbors for a node, and adaptively capture information from homophilic and heterophilic neighborhoods using dual channels. Currently, AGS-GNN is the only algorithm that we know of that explicitly controls homophily in the sampled subgraph through similar and diverse neighborhood samples. For diverse neighborhood sampling, we employ submodularity, which was not used in this context prior to our work. The sampling distribution is pre-computed and highly parallel, achieving the desired scalability. Using an extensive dataset consisting of 35 small (<=100K nodes) and large (>100K nodes) homophilic and heterophilic graphs, we demonstrate the superiority of AGS-GNN compare to the current approaches in the literature. AGS-GNN achieves comparable test accuracy to the best-performing heterophilic GNNs, even outperforming methods using the entire graph for node classification. AGS-GNN also converges faster compared to methods that sample neighborhoods randomly, and can be incorporated into existing GNN models that employ node or graph sampling.

artificial intelligence↗
DOE OSTI2022

Classical Simulation of Boson Sampling Based on Graph Structure

Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms’ complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms’ complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2021

Efficient Sampling of Complex Interdependent and Multiplex Networks

Efficient sampling of interdependent and multiplex infrastructure networks is critical for effectively applying failure and recovery algorithms in real-world settings, as well as to generate property-preserving reduced-order graph-based ensembles that address topological uncertainties. In this paper, we first explore the performance, i.e. the success in preserving graph properties, of graph sampling algorithms for interdependent and multiplex networks with synthetic and real-world graphs. We simulate sampling algorithms under different parameter settings. These settings include probabilistic graph generators, coupling patterns, and various performance metrics. Our results show that while Random Node and Random Walk sampling algorithms perform best for interdependent networks, Random Edge and Forest Fire sampling algorithms perform best for multiplex networks. Second, we propose and implement a novel similarity-based sampling algorithm for multiplex networks that samples only log(N) number of layers of an N-layer multiplex network while yielding computational savings with performance guarantees. Experimental results show that similarity sampling outperforms complete sampling of all layers while decreasing performance costs from a linear scale to a logarithmic one. Our results also indicate that similarity-based sampling outperforms complete sampling and random selection in nearly all scenarios when tested with real-world data.

Subasi, Omer↗
NASA NTRS2001

Effect of Air and Vacuum Storage on the Degradation of X-Ray-Exposed Aluminized-Teflon Investigated

Metalized Teflon FEP (fluorinated ethylene propylene, DuPont), a common thermal control material, has been found to degrade in the low-Earth-orbit space environment. The aluminized-FEP (Al-FEP) exterior layer on the Hubble Space Telescope has become extremely embrittled, with extensive cracking occurring on all sides of the telescope. This embrittlement has been primarily attributed to radiation exposure (x-rays from solar flares, electron/proton radiation, and possibly near-ultraviolet radiation) combined with thermal cycling. Limited samples of FEP tested after long-term exposure to low Earth orbit on the Hubble Space Telescope and on the Long Duration Exposure Facility indicated that there might be continued degradation in tensile properties over time. An investigation was conducted at the NASA Glenn Research Center to evaluate the effect of air and vacuum storage on the mechanical properties of x-ray-exposed FEP. Aluminized-FEP (5-mil-thick) tensile samples were x-ray exposed with 15.3-kV copper xrays for 2 hr, reducing the percent elongation to failure by approximately 50 percent in comparison to that for pristine Al-FEP. X-ray-exposed samples were stored in air or under vacuum for various time periods to see the effect of storage on tensile properties. Tensile results indicated that samples stored in air had larger decreases in tensile properties than samples stored under vacuum had, as seen in the graph. Samples stored under vacuum (for up to 400 hr) showed no further decrease in tensile properties over time, whereas samples stored in air (for up to 900 hr) appeared to show decreases in tensile properties over time. X-ray-exposed samples stored in air developed a hazy appearance in the exposed area, as seen in the photographs. When the source of the haziness was evaluated using scanning electron microscopy and atomic force microscopy, it was found to reside at the Al/FEP interface as witnessed by an increased surface roughness of the aluminized side of the material and a dramatic decrease in the adhesion between the Al and FEP. Optical properties of air-stored irradiated samples showed an increase in the diffuse reflectance, which is consistent with observed roughening that was characterized by AFM. These findings indicate that air exposure helps degrade x-ray-irradiated FEP. These results indicate that proper sample handling and storage is necessary with space-retrieved materials and with those exposed to ground-based irradiation simulation exposures.

deGroh, Kim K.↗
DOE OSTI2024

Addressing GPU memory limitations for Graph Neural Networks in High-Energy Physics applications

Introduction Reconstructing low-level particle tracks in neutrino physics can address some of the most fundamental questions about the universe. However, processing petabytes of raw data using deep learning techniques poses a challenging problem in the field of High Energy Physics (HEP). In the Exa.TrkX Project, an illustrative HEP application, preprocessed simulation data is fed into a state-of-art Graph Neural Network (GNN) model, accelerated by GPUs. However, limited GPU memory often leads to Out-of-Memory (OOM) exceptions during training, due to the large size of models and datasets. This problem is exacerbated when deploying models on High-Performance Computing (HPC) systems designed for large-scale applications. Methods We observe a high workload imbalance issue during GNN model training caused by the irregular sizes of input graph samples in HEP datasets, contributing to OOM exceptions. We aim to scale GNNs on HPC systems, by prioritizing workload balance in graph inputs while maintaining model accuracy. Our paper introduces diverse balancing strategies aimed at decreasing the maximum GPU memory footprint and avoiding the OOM exception, across various datasets. Results Our experiments showcase memory reduction of up to 32.14% compared to the baseline. We also demonstrate the proposed strategies can avoid OOM in application. Additionally, we create a distributed multi-GPU implementation using these samplers to demonstrate the scalability of these techniques on the HEP dataset. Discussion By assessing the performance of these strategies as data loading samplers across multiple datasets, we can gauge their effectiveness in both single-GPU and distributed environments. Our experiments, conducted on datasets of varying sizes and across multiple GPUs, broaden the applicability of our work to various GNN applications that handle input datasets with irregular graph sizes.

Lee, Claire Songhyun↗
NASA NTRS1972

U-Th-Pb and Rb-Sr measurements on some Apollo 14 lunar samples.

The concentrations of selected elements and elemental ratios in some Apollo 14 samples are presented in a table. Another table shows the isotopic composition of lead and strontium in some Apollo 14 samples. Graphs are provided with lead isotope ratio plots and a strontium evolution diagram. Rb-Sr ages are discussed together with isochron age methods of U-Th-Pb, a primary Pb-Pb isochron, a secondary Pb-Pb isochron, U-Pb concordia age relations, and U-Th-Pb concordia relations. Breccias and some soil samples as well as a basalt sample give evidence of significant enrichment of lead relative to uranium and thorium billions of years ago at the Fra Mauro site.

Tatsumoto, M.↗
DOE OSTI2026

Community detection robustness of graph neural networks

Graph neural networks (GNNs) are increasingly widely used for community detection in attributed networks. They combine structural topology with node attributes through message passing and pooling. However, their robustness or lack thereof with respect to different perturbations and targeted attacks in conjunction with community detection tasks is not well understood. To shed light on latent mechanisms behind GNN sensitivity on community detection tasks, we conduct a systematic computational evaluation of six widely adopted GNN architectures graph convolutional network, graph attention network, graph sample and aggregate (GraphSAGE), differentiable pooling (DiffPool), minimum cut pooling (MinCUT), and deep modularity networks (DMoN). The analysis covers three perturbation categories: node attribute manipulations, edge topology distortions, and adversarial attacks. We use element-centric similarity as the evaluation metric on synthetic benchmarks and real-world citation networks. Our findings indicate that supervised GNNs tend to achieve higher baseline accuracy, while unsupervised methods, particularly DMoN, maintain stronger resilience under targeted and adversarial perturbations. Furthermore, robustness appears to be strongly influenced by community strength, with well-defined communities reducing performance loss. Across all models, node attribute perturbations associated with targeted edge deletions and shifts in attribute distributions tend to cause the largest degradation in community recovery. These findings highlight important trade-offs between accuracy and robustness in GNN-based community detection and offer insights into selecting architectures resilient to noise and adversarial attacks.

Goel, Jaidev [Virginia Polytechnic Inst. and State↗
NASA NTRS1974

Noise generated by quiet engine fans. 2: Fan A

A significant effort within the NASA Quiet Engine Program has been devoted to acoustical evaluation at the Lewis Research Center noise test facility of a family of full-scale fans. This report, documents the noise results obtained with fan A - a 1.5-pressure-ratio, 1160-ft/sec-tip-speed fan. The fan is described and some aerodynamic operating data are given. Far-field noise around the fan was measured for a variety of configurations pertaining to acoustical treatment and over a range of operating conditions. Complete results of 1/3-octave band analysis of the data are presented in tabular form. Included also are power spectra and sideline perceived noise levels. Some representative 1/3-octave band data are presented graphically, and sample graphs of continuous narrow-band spectra are also provided.

Montegani, F. J.↗
NASA NTRS1976

Noise generated by quiet engine fans. 3: Fan C

A family of fans designed with low noise features was acoustically evaluated, and noise results are documented for a 1.6-pressure-ratio, 472-m/sec (155-ft/sec) tip speed fan. The fan is described and some aerodynamic operating data are given. Far field noise around the fan was measured over a range of operating conditions for a variety of configurations having different arrangements of sound absorbing material in the flow ducts. Complete results of 1.3 octave band analysis of the data are presented in tabular form. Included also are acoustic power spectra and sideline perceived noise levels. Representative 1/3 octave band data are presented graphically, and sample graphs of continuous narrow band spectra are also provided.

Montegan, F. J.↗
NASA NTRS1987

Comets

Observations of comets obtained with the IUE satellite since its launch in 1978 are reviewed. The status of UV observation of comets prior to IUE is discussed, and particular attention is given to low-resolution UV spectroscopy of cometary comae, the detection of new species in the UV emission, high-dispersion spectroscopy, spatial mapping of the emissions, abundance determinations, and short-term variability. Diagrams, graphs, sample spectra, and tables of numerical data are provided.

Festou, M. C.↗
NASA NTRS1987

Mass loss from cool stars

The properties of cool stellar winds are discussed, summarizing the results of observations obtained with the IUE satellite since its launch in 1978. The advantages of the UV spectral region for studying mass loss in cool stars are outlined; the evidence for mass outflow in objects spanning the cool half of the H-R diagram is reviewed; techniques and results of mass-loss-rate computations based on UV data are examined; detailed studies of single stars and binaries are described; the primary achievements of the IUE are listed; and a number of outstanding problems are briefly considered. Diagrams, graphs, sample spectra, and tables of numerical data are included. The mass-loss rates and wind velocities for Zeta Aur and VV Cep binaries are found to have ranges of about (6-1000) x 10 to the -9th solar mass/yr and 10-160 km/s, respectively.

Dupree, A. K.↗
NASA NTRS1988

High speed photography, videography, and photonics V; Proceedings of the Meeting, San Diego, CA, Aug. 17-19, 1987

Recent advances in high-speed optical and electrooptic devices are discussed in reviews and reports. Topics examined include data quantification and related technologies, high-speed photographic applications and instruments, flash and cine radiography, and novel ultrafast methods. Also considered are optical streak technology, high-speed videographic and photographic equipment, and X-ray streak cameras. Extensive diagrams, drawings, graphs, sample images, and tables of numerical data are provided.

Johnson, Howard C.↗