Search NASA⌕ Search

SEARCH · Search NASA

Results for “Graph Partitioning”

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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
DOE OSTI2018

Sparse Hardware Embedding of Spiking Neuron Systems for Community Detection

We study the applicability of spiking neural networks and neuromorphic hardware for solving general optimization problems without the use of adaptive training or learning algorithms. We leverage the dynamics of Hopfield networks and spin-glass systems to construct a fully connected spiking neural system to generate synchronous spike responses indicative of the underlying community structure in an undirected, unweighted graph. Mapping this fully connected system to current generation neuromorphic hardware is done by embedding sparse tree graphs to generate only the leading-order spiking dynamics. Here, we demonstrate that for a chosen set of benchmark graphs, the spike responses generated on a current generation neuromorphic processor can improve the stability of graph partitions and non-overlapping communities can be identified even with the loss of higher-order spiking behavior if the graphs are sufficiently dense. For sparse graphs, the loss of higher-order spiking behavior improves the stability of certain graph partitions but does not retrieve the known community memberships.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Trust: Triangle Counting Reloaded on GPUs

Triangle counting is a building block for a wide range of graph applications. Here, traditional wisdom suggests that i) hashing is not suitable for triangle counting, ii) edge-centric triangle counting beats vertex-centric design, and iii) communication-free and workload balanced graph partitioning is a grand challenge for triangle counting. On the contrary, we advocate that i) hashing can help the key operations for scalable triangle counting on Graphics Processing Units (GPUs), i.e., list intersection and graph partitioning, ii) vertex-centric option reduces both hash table construction cost and memory consumption, which is limited on GPUs. In addition, iii) we exploit graph and workload collaborative, and hash-based 2D partitioning to scale vertex-centric triangle counting over 1,000 GPUs with sustained scalability. In this work, we present TRUST, which performs triangle counting with the hash operation and vertex-centric paradigm. To the best of our knowledge, TRUST is the first work that achieves over one trillion Traversed Edges Per Second (TEPS) rate for triangle counting.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

A Fast and Scalable Genetic Algorithm-Based Approach for Planning of Microgrids in Distribution Networks

As a result of climate change, extreme weather events are occurring more frequently and with increasing impact. This trend poses a significant challenge for distribution utilities and system operators to ensure that there is uninterrupted power supply to critical loads in their networks; thus, the level of proactive preparation of the distribution system to be able to handle severe impacts of extreme weather events represents the system's resilience. One method that distribution system planners can use to prepare for future extreme events is to plan multiple microgrids which can use local generation as much as possible to supply critical loads. But partitioning an existing distribution system such that multiple feasible islands are planned and which are capable of supporting critical loads is still challenging for distribution systems - first, because of the size of the network graph partitioning problem and, second, because of the difficulty in properly formulating the desired attributes of such islands or microgrids. Therefore, this paper presents a genetic algorithm based approach that facilitates incorporating multiple objectives for grid partitioning by formulating two types of problems - node allocation and edge elimination - and it considers multiple topological and resilience-enhancing objectives. The performance of the proposed genetic algorithm-based approach is numerically evaluated on multiple test systems as well as on a real distribution feeder in Colorado, United States.

genetic algorithm↗
DOE OSTI2020

Sphynx

Sphynx is a software library for parallel graph partitioning and load balancing. It partitions a set of vertices in a graph such that the vertex parts are balanced, and the edge cut is approximately minimized. The primary use case is to partition a computational graph into smaller tasks that can be assigned to processors (cores) for efficient parallel computing. Sphynx is based on the Trilinos scientific computing toolkit so can run on both multi-CPU and multi-GPU systems. SAND2020-12183 M Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy's National Nuclear Security Administration under contract DE-NA0003525.

Boman, Erik↗
DOE OSTI2022

A differentiable approach to the maximum independent set problem using dataless neural networks

The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. Here, in this paper, we propose a different approach in that no data is required for training the neural networks that produce the solution. In this sense, what we present is not a machine learning solution, but rather one that is dependent on neural networks and where backpropagation is applied to a loss function defined by the structure of the neural network architecture as opposed to a training dataset. In particular, we reduce the popular combinatorial optimization problem of finding a maximum independent set to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest. Additionally, we propose a universal graph reduction procedure to handle large-scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental results on both real and synthetic graphs demonstrate that our proposed method performs on par or outperforms state-of-the-art learning-based methods in terms of the size of the found set without requiring any training data.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Multilevel Combinatorial Optimization across Quantum Architectures

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Furthermore, hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Spatial decomposition of structured grids for nuclear reactor simulations

Spatial decomposition methods based on graph partitioning are developed and implemented in the high fidelity neutron transport code MPACT. These graph-based spatial decomposition methods are more general than previous decomposition methods and typically provide better load balance and reduced runtimes due to their improved parallel efficiency. Correlations are drawn between simulation runtime and the balance of the partition for 2D simulations. Comparisons are made using partition balance metrics for different decomposition schemes in 2D and 3D simulations. Finally, for typical ranges of subdomains, graph-based partitioning methods offer significant reductions to runtimes. However, for highly decomposed problems, these graph-based methods may decrease convergence rates, thus reducing parallel efficiency compared to older methods.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗
DOE OSTI2020

Detecting multiple communities using quantum annealing on the D-Wave system

A very important problem in combinatorial optimization is the partitioning of a network into communities of densely connected nodes; where the connectivity between nodes inside a particular community is large compared to the connectivity between nodes belonging to different ones. This problem is known as community detection, and has become very important in various fields of science including chemistry, biology and social sciences. The problem of community detection is a twofold problem that consists of determining the number of communities and, at the same time, finding those communities. This drastically increases the solution space for heuristics to work on, compared to traditional graph partitioning problems. In many of the scientific domains in which graphs are used, there is the need to have the ability to partition a graph into communities with the “highest quality” possible since the presence of even small isolated communities can become crucial to explain a particular phenomenon. We have explored community detection using the power of quantum annealers, and in particular the D-Wave 2X and 2000Q machines. It turns out that the problem of detecting at most two communities naturally fits into the architecture of a quantum annealer with almost no need of reformulation. This paper addresses a systematic study of detecting two or more communities in a network using a quantum annealer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Bootstrap AMG for spectral clustering

Graph Laplacian is a popular tool for analyzing graphs, particularly in graph partitioning and clustering. Given a notion of similarity (via an adjacency matrix), graph clustering refers to identifying different groups such that vertices in the same group are more similar compared to vertices across different groups. Data clustering can be reformulated in terms of a graph clustering problem when the given set of data is represented as a graph, also known as similarity graph. In this context, eigenvectors of the graph Laplacian are often used to obtain a new geometric representation of the original data set that generally enhances cluster properties and improves cluster detection. Here, we apply a bootstrap algebraic multigrid (AMG) method that constructs a set of vectors associated with the graph Laplacian. These vectors, referred to as algebraically smooth ones, span a low-dimensional Euclidean space, which we use to represent the data, enabling cluster detection both in synthetic and in realistic well-clustered graphs. We show that, in the case of a good quality bootstrap AMG, the computed smooth vectors employed in the construction of the final AMG operator, which by construction is spectrally equivalent to the originally given graph Laplacian, accurately approximate the space in the lower portion of the spectrum of the preconditioned operator. Thus, our approach can be viewed as a spectral clustering technique associated with the generalized spectral problem (Laplace operator versus the final AMG operator), and hence, it can be seen as an extension of the classical spectral clustering that employs a standard eigenvalue problem.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A Fast and Scalable Genetic Algorithm-Based Approach for Planning of Microgrids in Distribution Networks: Preprint

As a result of climate change, extreme weather events are occurring more frequently and with increasing impact. This trend poses a significant challenge for distribution utilities and system operators to ensure that there is uninterrupted power supply to critical loads in their networks; thus, the level of proactive preparation of the distribution system to be able to handle severe impacts of extreme weather events represents the system's resilience. One method that distribution systems use to prepare for extreme events is to form multiple microgrids and thereby isolate themselves from the grid supply by using local generation as much as possible to supply critical loads. But partitioning an existing system into multiple feasible islands capable of supporting critical loads is still challenging for distribution systems - first, because of the size of the graph partitioning problem and, second, because of the difficulty in properly formulating the desired attributes of such islands or microgrids. Therefore, this paper presents a genetic algorithmbased approach that facilitates incorporating multiple objectives for grid partitioning by formulating two types of problems - node allocation and edge elimination - and it considers multiple topological and resilience-enhancing objectives. The performance of the proposed genetic algorithm-based approach is numerically evaluated on multiple test systems as well as on a real distribution feeder in Colorado, USA.

edge elimination↗
DOE OSTI2020

Graph Theory and IC Component Design Analysis

Graph analysis in large integrated circuit (IC) designs is an essential tool for verifying design logic and timing via dynamic timing analysis (DTA). IC designs resemble graphs with each logic gate as a vertex and the conductive connections between gates as edges. Using DTA digital statistical correlations, graph condensation, and graph partitioning, it is possible to identify high-entropy component centers and paths within an IC design. Identification of high-entropy component centers (HECC) enables focused DTA, effectively lowering the computational complexity of DTA on large integrated circuit graphs. In this paper, a devised methodology termed IC layout subgraph component center identification (CCI) is used to identify described. CCI lowers DTA computationally complexity by condensing IC graphs into reduced subgraphs in which dominant logic functions are verified.

42 ENGINEERING↗
DOE OSTI2025

Toward computing bounds for Ramsey numbers using quantum annealing

Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Outer Wall Segmentation of Abdominal Aortic Aneurysm by Variable Neighborhood Search Through Intensity and Gradient Spaces

Aortic aneurysm segmentation remains a challenge. Manual segmentation is a time-consuming process which is not practical for routine use. To address this limitation, several automated segmentation techniques for aortic aneurysm have been developed, such as edge detection-based methods, partial differential equation methods, and graph partitioning methods. However, automatic segmentation of aortic aneurysm is difficult due to high pixel similarity to adjacent tissue and a lack of color information in the medical image, preventing previous work from being applicable to difficult cases. This paper uses uses a variable neighborhood search that alternates between intensity-based and gradient-based segmentation techniques. By alternating between intensity and gradient spaces, the search can escape from local optima of each space. The experimental results demonstrate that the proposed method outperforms the other existing segmentation methods in the literature, based on measurements of dice similarity coefficient and jaccard similarity coefficient at the pixel level. In addition, it is shown to perform well for cases that are difficult to segment.

62 RADIOLOGY AND NUCLEAR MEDICINE↗
DOE OSTI2025

A distributed voltage inference framework for cyber-physical attacks detection and localization in active distribution grids

The transition to active distribution grids with real-time monitoring and control depends on the proliferation of advanced communication networks and devices. This paradigm shift towards a cyber-physical architecture also introduces new vulnerabilities for adversaries to exploit and launch sophisticated cyber-physical attacks targeting grid observability. Current research highlights the challenges in distinguishing attacks on voltage phasor or nodal injection measurements and isolating multi-source attack locations in a multiphase distribution grid. The attack detection and localization methods in literature face accuracy issues, applications across diverse attack scenarios, or scalability limits. Here, to bridge these gaps, this paper proposes a distributed Voltage Inference framework for real-time detection and localization of cyber-physical attacks, addressing scalability, adaptability, and accuracy challenges in state-of-the-art methods. The proposed methodology leverages the distributed nature of the Voltage Inference framework through a two-step process of prediction and correction, together with a tractable graph partitioning approach, providing a reliable solution to identify compromised measurement sources and facilitate isolation. Extensive testing on IEEE 13 and 123-node distribution feeders underscores the algorithm’s efficacy, enhancing the security and resilience of active distribution grids against evolving cyber threats. Additionally, Hardware-in-the-Loop (HIL) implementation validates the proposed strategy’s practical applicability in real-world scenarios.

active distribution grids↗
DOE OSTI2018

High performance Data Driven Agent-based Modeling Framework for Simulation of Commute Mode Choices in Metropolitan Area

Active transportation, human-powered transportation modes such as walking and bicycling, not only reduces the carbon footprint from the transportation sector but also promotes healthy living by offering opportunities for people to build physical activity into their daily routine. To encourage active transportation through urban planning and public campaigns, it is of significant importance to infer factors that substantially influence commuters in their transportation mode choice process. This necessitates a flexible and repeatable tool that can evaluate how a policy is perceived by individual commuters and convert their decisions into macro level understanding. This paper introduces one such effort that is specifically designed for studies of transportation mode choices in metropolitan areas. It provides results from a high-resolution data driven simulation based on high performance computing implementation of the agent-based model framework for home-to-work commute trips. The framework uses a graph-partition based technique that can leverage the interaction structure of agents within a geographic proximity and can boost the simulation execution time. Further, based on a flexible design, it can run ABM with different levels of computing resources-from multi core workstations to an HPC grid. The framework has been tested on the Titan Cray XK7 supercomputer of the Oak Ridge Leadership Computing Facility.

Park, Byung↗
DOE OSTI2018

Exploring Applications of Random Walks on Spiking Neural Algorithms

Neuromorphic computing has many promises in the future of computing due to its energy efficient and scalable implementation. Here we extend a neural algorithm that is able to solve the diffusion equation PDE by implementing random walks on neuromorphic hardware. Additionally, we introduce four random walk applications that use this spiking neural algorithm. The four applications currently implemented are: generating a random walk to replicate an image, finding a path between two nodes, finding triangles in a graph, and partitioning a graph into two sections. We then made these four applications available to be implemented on software using a graphical user interface (GUI).

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Quantum Optimization and Approximation Algorithms

Shor's groundbreaking quantum algorithm for integer factoring provides an exponential speedup over the best-known classical algorithms. In the 20 years since Shor's algorithm was conceived, only a handful of fundamental quantum algorithmic kernels, generally providing modest polynomial speedups over classical algorithms, have been invented. To better understand the potential advantage quantum resources provide over their classical counterparts, one may consider other resources than execution time of algorithms. Quantum Approximation Algorithms direct the power of quantum computing towards optimization problems where quantum resources provide higher-quality solutions instead of faster execution times. We provide a new rigorous analysis of the recent Quantum Approximate Optimization Algorithm, demonstrating that it provably outperforms the best known classical approximation algorithm for special hard cases of the fundamental Maximum Cut graph-partitioning problem. We also develop new types of classical approximation algorithms for finding near-optimal low-energy states of physical systems arising in condensed matter by extending seminal discrete optimization techniques. Our interdisciplinary work seeks to unearth new connections between discrete optimization and quantum information science.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Scalable Approaches to Selecting Key Entities in Large Networked Infrastructure Systems

This work aims at bringing advances in discrete optimization algorithms to solving practical engineering problems at scale. Often times, in many engineering design problems, there is a need to select a small set of influential or representative elements from a large ground set of entities in an optimal fashion. Submodular optimization provides for a formal way to solve such problems. Common examples with infrastructure systems involve sensor placement and identification of key entities with certain objectives. However, scaling these approaches to large infrastructure systems can be challenging because of the high computational complexity of the overall framework that include the optimization algorithms as well as high-complexity compute-oracles that provide the necessary objective function values. In this work, we explore a well-studied and widely-applicable paradigm, namely leader-selection in a multi-agent networked setting in the context of scalable methodologies. We demonstrate novel frameworks that utilize variations of accelerated submodular optimization algorithms along with linear-algebraic methods that can help accelerate the oracle computations. We further explore this combination in conjunction with graph partitioning paradigms to take advantage of the accelerated algorithms in a distributed setting. Finally we demonstrate the key findings on a practical problem in an operational setting. For this, we leverage an example road network with approximately 18k nodes and 27k edges in a traffic control application, where we seek a limited number of k=200 key intersections. This problem can be solved in a serial setting in just under 5 hours providing more than 2 orders of magnitude speed-up over methods that do not consider acceleration techniques.

Visweswara Sathanur, Arun↗