Search

Quantum-chemical fragmentation methods offer an efficient approach for the treatment of large proteins, in particular if local target quantities such as protein--ligand interaction energies, enzymatic reaction energies, or spectroscopic properties of embedded chromophores are sought. However, the accuracy that is achievable for such local target quantities intricately depends on how the protein is partitioned into smaller fragments. While the commonly employed na\"ive approach of using fragments with a fixed size is widely used, it can result in large and unpredictable errors when varying the fragment size. Here, we present a systematic partitioning scheme that aims at minimizing the fragmentation error of a local target quantity for a given maximum fragment size. To this end, we construct a weighted graph representation of the protein, in which the amino acids constitute the nodes. These nodes are connected by edges weighted with an estimate for the fragmentation error that is expected when cutting this edge. This allows us to employ graph partitioning algorithms provided by computer science to determine near-optimal partitions of the protein. We apply this scheme to a test set of six proteins representing various prototypical applications of quantum-chemical fragmentation methods using a simplified molecular fractionation with conjugate caps (MFCC) approach with hydrogen caps. We show that our graph-based scheme consistently improves upon the na\"ive approach.

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. 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. Reproducibility : Our code and data are available at Reference [1].

The status of a vertex $v$ in a connected graph is the sum of the distances from $v$ to all other vertices. The status sequence of a connected graph is the list of the statuses of all the vertices of the graph. In this paper we investigate the status sequences of trees. Particularly, we show that it is NP-complete to decide whether there exists a tree that has a given sequence of integers as its status sequence. We also present some results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we provide a partial answer to a conjecture of Shang and Lin from 2011, showing that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.

The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on approximate solutions uses, in increasing strength and expense: eigenvalue, semidefinite programming, SDP, and doubly nonnegative, DNN, bounding techniques. In this paper, we derive strengthened SDP and DNN relaxations, and we propose a scalable algorithmic approach for efficiently evaluating, theoretically verifiable, both upper and lower bounds. Our stronger relaxations are based on a new gangster set, and we demonstrate how facial reduction, FR, fits in well to allow for regularized relaxations. Moreover, the FR appears to be perfectly well suited for a natural splitting of variables, and thus for the application of splitting methods. Here, we adopt the strictly contractive Peaceman-Rachford splitting method, sPRSM. Further, we bring useful redundant constraints back into the subproblems, and show empirically that this accelerates sPRSM.In addition, we employ new strategies for obtaining lower bounds and upper bounds of the optimal value of MC from approximate iterates of the sPRSM thus aiding in early termination of the algorithm. We compare our approach with others in the literature on random datasets and vertex separator problems. This illustrates the efficiency and robustness of our proposed method.

In this paper we develop modeling techniques for a social partitioning problem. Different social interaction regulations are imposed during pandemics to prevent the spread of diseases. We suggest partitioning a set of company employees as an effective way to curb the spread, and use integer programming techniques to model it. The goal of the model is to maximize the number of direct interactions between employees who are essential for company’s work subject to the constraint that all employees should be partitioned into components of no more than a certain size implied by the regulations. Then we further develop the basic model to take into account different restrictions and provisions. We also give heuristics for solving the problem. Our computational results include sensitivity analysis on some of the models and analysis of the heuristic performance.

We present an implementation and scaling analysis of a GPU-accelerated kernel for HemeLB, a high-performance Lattice Boltzmann code for sparse complex geometries. We describe the structure of the GPU implementation and we study the scalability of HemeLB on a GPU cluster under normal operating conditions and with real-world application cases. We investigate the effect of CUDA block size and GPU over-subscription on the single-GPU performance, and we present a strong-scaling analysis of multi-GPU parallel simulations using two different hardware models (P100 and V100) and a variety of large cerebral aneurysm geometries. We find that HemeLB-GPU achieves single-GPU speedups of $50\times$ (P100) and $100\times$ (V100) compared to a single CPU core, with good scalability up to 32 GPUs. We also discuss strategies to improve both the kernel performance as well as the scalability of HemeLB-GPU to a larger number of GPUs. The GPU implementation supports the LBGK collision kernel, boundary conditions for walls and inlets/outlets, and several lattice types (D3Q15, D3Q19, D3Q27), and it integrates seamlessly with the existing infrastructure in HemeLB for graph partitioning and parallelization via MPI. It is expected that the GPU implementation will enable users of the HemeLB code to make better utilization of heterogeneous high-performance computing systems for large-scale lattice Boltzmann simulations.

Disk I/O is the major performance bottleneck of existing out-of-core graph processing systems. We found that the total I/O amount can be reduced by loading more vertices into memory every time. Although task partitioning of a graph processing system is traditionally considered equivalent to the graph partition problem, this assumption is untrue for many Machine Learning and Data Mining (MLDM) problems: instead of a single value, a vector of data elements is defined as the property for each vertex/edge. By dividing each vertex into multiple sub-vertices, more vertices can be loaded into memory every time, leading to less amount of disk I/O. To explore this new opportunity, we propose a category of 3-D partitioning algorithm that considers the hidden dimension to partition the property vector. The 3-D partitioning algorithm provides a new tradeoff to reduce communication costs, which is adaptive to both distributed and out-of-core scenarios. Based on it, we build a distributed graph processing system Cube and an out-of-core system SingleCube . Since network traffic is significantly reduced, Cube outperforms state-of-the-art graph-parallel system PowerLyra by up to $4.7\times$ 4 . 7 × . By largely reducing the disk I/O amount, the performance of SingleCube is significantly better than state-of-the-art out-of-core system GridGraph (up to $4.5\times$ 4 . 5 × ).

In order to improve the efficiency of fault diagnosis, a novel granular computing algorithm is developed to reduce computational cost. It is realized by extracting and partitioning on the complete graphs, and in the process of graph generation, the dimensionless similarity method is proposed to overcome the influence of attributes with different dimensions. So, the algorithm is named graph partition based on dimensionless similarity (GPDS). Moreover, similarity threshold determination method based on frequency distribution histogram is proposed to reduce the dependency on the experiences of experts. Finally, different characteristic data are applied to verify the theories. The experimental results indicate that the compressed training samples can maintain the classification accuracy. Furthermore, the elapsed time can be obviously reduced. Therefore, the GPDS method can be used in fault diagnosis properly.

In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex graph G=(V,E), and a collection M={(s1,t1),…,(sk,tk)} of pairs of its vertices, called source-destination, or demand pairs. The goal is to route as many of the demand pairs as possible, where to route a pair we need to select a path connecting it, so that all selected paths are disjoint in their vertices. The best current algorithm for NDP achieves an O(√n)-approximation, while, until recently, the best negative result was a factor Ω(log1/2−єn)-hardness of approximation, for any constant є, unless NP ⊆ ZPTIME(npoly logn). In a recent work, the authors have shown an improved 2Ω(√logn)-hardness of approximation for NDP, unless NP⊆ DTIME(nO(logn)), even if the underlying graph is a subgraph of a grid graph, and all source vertices lie on the boundary of the grid. Unfortunately, this result does not extend to grid graphs. The approximability of the NDP problem on grid graphs has remained a tantalizing open question, with the best current upper bound of O(n1/4), and the best current lower bound of APX-hardness. In a recent work, the authors showed a 2O(√logn)-approximation algorithm for NDP in grid graphs, if all source vertices lie on the boundary of the grid – a result that can be seen as suggesting that a sub-polynomial approximation may be achievable for NDP in grids. In this paper we show that this is unlikely to be the case, and come close to resolving the approximability of NDP in general, and of NDP in grids in particular. Our main result is that NDP is 2Ω(log1−є n)-hard to approximate for any constant є, assuming that NP⊈RTIME(npoly logn), and that it is nΩ (1/(loglogn)2)-hard to approximate, assuming that for some constant δ>0, NP ⊈RTIME(2nδ). These results hold even for grid graphs and wall graphs, and extend to the closely related Edge-Disjoint Paths problem, even in wall graphs. Our hardness proof performs a reduction from the 3COL(5) problem to NDP, using a new graph partitioning problem as a proxy. Unlike the more standard approach of employing Karp reductions to prove hardness of approximation, our proof is a Cook-type reduction, where, given an input instance of 3COL(5), we produce a large number of instances of NDP, and apply an approximation algorithm for NDP to each of them. The construction of each new instance of NDP crucially depends on the solutions to the previous instances that were found by the approximation algorithm.

Intra-camera supervision (ICS) for person re-identification (Re-ID) assumes that identity labels are independently annotated within each camera view and no inter-camera identity association is labeled. It is a new setting proposed recently to reduce the burden of annotation while expect to maintain desirable Re-ID performance. However, the lack of inter-camera labels makes the ICS Re-ID problem much more challenging than the fully supervised counterpart. By investigating the characteristics of ICS, this article proposes a graph-induced contrastive learning (GCL) approach to address this issue. More specifically, we first formulate the cross-camera ID association task as a graph partitioning problem subjected to ICS-specific constraints and design a greedy agglomeration algorithm to solve it. Then, we propose a graph-induced contrastive loss that unifies both intra- and inter-camera learning into a contrastive learning framework to learn a Re-ID model. The cross-camera ID association step and the Re-ID model contrastive learning step are alternatively iterated, by which we progressively obtain a highly discriminative Re-ID model. Extensive experiments on three large-scale datasets show that our approach outperforms all previous ICS works. Especially, it gains 15.7% Rank-1 and 14.3% mAP improvements on the challenging MSMT17 dataset. Moreover, our approach performs even comparable to state-of-the-art fully supervised methods on all of the three datasets.

Network security defenses evolve, responding to real-time attack incidents, modifying the underlying topology, or reallocating defense systems across the network. The present work emphasizes reducing the time to compute new optimal reallocations of defense systems, responding to emerging real-time remote attacks. The proposed heuristic method utilizes parallel processing by slicing the underlying graphical model representing the network topology, solving in parallel multiple mixed-integer programming problems corresponding to the created subgraphs, and producing an estimate of the optimal defense. The parallelized method to compute a new defense enables producing a response, in real-time, before remote attackers compromise a target machine in the network. Our prototype tool to compute a new defense, the high-performance security analyzer, has a speedup of at least 20 over solving the original problem using a serial algorithm, and with an insignificant difference between the performance of the (computed in parallel) approximately optimal defense and the (serially computed) optimal defense. A major conclusion is that further speedups will come from parallel integer programming algorithms rather than from graph partitioning.

As dynamic graph data have been actively used, incremental graph partition schemes have been studied to efficiently store and manage large graphs. In this paper, we propose a vertex-cut based novel incremental graph partitioning scheme that supports load balancing in a distributed environment. The proposed scheme chooses the load of each node that considers its storage utilization and throughput as the partitioning criterion. The proposed scheme defines hot data that means a particular vertex frequently searched among graphs requested by queries. We manage and utilize hot data for graph partitioning. Finally, we perform vertex-cut based dynamic graph partitioning by using a vertex replication index, the load each node, and hot data to distribute the load evenly in a distributed environment. In order to verify the superiority of the proposed partitioning scheme, we compare it with the existing partitioning schemes through a variety of performance evaluations.

The article considers one of the most important combinatorial optimization problems — the problem of graph partitioning. It belongs to the class of NP-complex optimization problems. The article presents the partitioning problem statement. Due to the complexity of this task, the article proposes a new search strategy based on a combined approach. The combined approach is to divide the decision-making process into two levels. At the first level, the bee optimization method is used to quickly obtain subdomains with a high value of the objective function, and at the second level, an evolutionary algorithm is used to improve obtained solutions. To implement this approach, the authors developed a combined algorithm that can obtain sets of quasi-optimal solutions in polynomial time and avoid looping in local regions at the same time. A software module is developed and algorithms for partitioning graphs into parts are implemented. A computational experiment has been carried out when dividing into 8 parts of test circuits (benchmarks) by IBM. An analysis of experimental studies showed that the developed combined algorithm is on average 5 % higher than the partition results obtained by well-known hMetis, PGAComplex algorithms with comparable solution time, which indicates the effectiveness of the proposed approach. The time complexity of the developed combined algorithm is approximately O (n2).

We establish a strict asymptotic inequality between a class of graph partition problems on the sparse End\H{o]s-Renyi and random regular graph ensembles with the same average degree. Along the way, we establish a variational representation for the ground state energy for generalized mixed $p$-spin glasses and derive strict comparison inequalities for such models as the alphabet changes.

We introduce XtraPuLP , a distributed-memory graph partitioner designed to process irregular trillion-edge graphs. XtraPuLP is based on the scalable label propagation community detection technique, which has been demonstrated in various prior works as a viable means to produce high quality partitions of skewed and small-world graphs with minimal computation time. Our XtraPuLP implementation can also be generalized to compute partitions with an arbitrary number of constraints, and it can compute partitions with balanced communication load across all parts. On a collection of large sparse graphs, we show that XtraPuLP partitioning is considerably faster than state-of-the-art partitioning methods, while also demonstrating that XtraPuLP can produce partitions of real-world graphs with billion+ vertices and over a hundred billion edges in minutes. Additionally, we demonstrate XtraPuLP on a variety of applications, including large-scale graph analytics and sparse matrix-vector multiplication.

Efficient graph partitioning is vital for high-performance graph-parallel systems. Traditional graph partitioning methods attempt to both minimize communication cost and guarantee load balancing in computation. However, the skewed degree distribution of natural graphs makes it difficult to simultaneously achieve the two objectives. This article proposes topology refactorization (TR), a topology-aware method allowing graph-parallel systems to separately handle the two objectives: refactorization is mainly focused on reducing communication cost, and partitioning is mainly targeted for balancing the load. TR transforms a skewed graph into a more communication-efficient topology through fusion and fission , where the fusion operation organizes a set of neighboring low-degree vertices into a super-vertex, and the fission operation splits a high-degree vertex into a set of sibling sub-vertices. Based on TR, we design an efficient graph-parallel system (TopoX) which pipelines refactorization with partitioning to both reduce communication cost and balance computation load. Prototype evaluation shows that TopoX outperforms PowerLyra by up to 78.5% (from 37.2%) on real-world graphs and is faster than most other graph-parallel systems, while only introducing small overhead and memory consumption.

Cluster ensemble techniques aim to combine the outputs of multiple clustering algorithms to obtain a single consensus partitioning. The current paper reports about the development of a cluster ensemble based technique combining the concepts of multiobjective optimization and deep-learning models for gene clustering where some additional protein-protein interaction information are utilized for generating the consensus partitioning. The proposed ensemble based framework works in four phases: (i) filtering out the irrelevant genes from the microarray dataset: only the statistically significant genes are considered for further data analysis; (ii) generation of diverse base partitionings: a multi-objective optimization-based clustering technique is proposed which simultaneously optimizes three different cluster quality measures and generates a set of partitioning solutions on the Pareto optimal front; (iii) generation of a consensus partitioning: mentha scores, calculated by accessing a highly enriched protein-protein interaction archive named mentha , of different clustering solutions are considered for generating a weighted incidence matrix; (iv) finally, two approaches are used to generate a consensus partitioning from the obtained incidence matrix. The first approach is based on a traditional machine learning method, and another approach exploits the graph partitioning algorithm and two deep neural models to generate the final clustering. To validate the efficacy of the proposed ensemble framework, it is applied on five gene expression datasets. We present a comparative analysis of the proposed technique over different clustering algorithms in terms of biological homogeneity index (BHI) and biological stability index (BSI). The traditional approach attains an average 3 and 2 percent improvements over the best non-dominated solution with respect to BHI and BSI, respectively, whereas deep learning models illustrate an average 6.8 and 1.5 percent improvements over the proposed traditional approach with respect to BHI and BSI, respectively. Subsequently, Welch's t-test is executed to prove that the results obtained by the proposed methods are statistically significant. Availability of data and materials: https://github.com/sduttap16/DeepEnsm .

This paper investigates subchannel allocation based on clustered interference alignment in dense small cell networks when all small cell user equipments (SUEs) have differentiated requirements for data streams. By imposing the condition that each cluster has a size not exceeding the maximum value achieved when each SUE needs only one data stream, we maximize the number of SUEs with guaranteed requirements for data streams, which is NP-hard. Hence, we propose a two-phase efficient solution with much lower complexity and reduced feedback overhead. First, similarity clustering is performed by graph partition, and then, subchannel allocation is done through a coloring algorithm. Numerical results show that the proposed solution offers a performance better than the related schemes and close to the approximate optimal solution.

As a key smart transportation service, public vehicle systems are intended to improve traffic efficiency and vehicle occupancy ratios, and to reduce the number of vehicles on roads, by inducing travelers to share rides with others. Despite the clear logic behind this service, achieving a viable model for matching multiple riders to vehicles with low latency and high satisfaction remains an open issue. In this paper, we propose an Edge Computing based Public Vehicle (ECPV) system to improve traffic efficiency and vehicle occupancy ratios by scheduling ridesharing among travelers and reduce the delay of decision making by leveraging edge computing. Particularly, by introducing a metric of traveler satisfaction jointly considering travel time, distance, and costs (i.e., charge), we formalize public vehicle scheduling problem as an optimization problem with maximizing traveler satisfaction as objective to reduce travel time and improve traffic efficiency. Further, as achieving globally optimal matching of rides and travelers is time consuming, to reduce the delay of decision making (i.e., response to ride-traveler pairs matching) and improve real time ridesharing service and traveler satisfaction, an edge computing based ride request transmission mechanism and a tree based heuristic matching mechanism are proposed to effectively exchange ride requests and select appropriate vehicles for mostof ride requests on edge devices. Also, our ECPV system considers driverless cars as public vehicles to remove the subjective influence of drivers and improve the efficiency of vehicle scheduling, and introduces a graph partition based depot placement mechanism to determine vehicleparking locations and balance vehicle distribution across system. Through extensive performance evaluations, our experimental results show that our proposed ECPV system can effectively match ride requests to public vehicles, reduce travel times and distances for all trips, reducecharges to travelers, and improve vehicle occupancy.

Superconducting Single Flux Quantum (SFQ) logic with switching delay of 1ps and switching energy of 10 −19 J is a potential emerging candidate for replacing Complementary Metal Oxide Semiconductor (CMOS) to achieve very high speed and ultra energy efficiency. Conventional SFQ circuits need Full Path Balancing (FPB), which tends to require insertion of many path balancing buffers (D-Flip-Flops). FPB method increases total power consumption as well as total area of the chip. This article presents a novel scheme for realization of superconducting SFQ circuits by introducing a new depth-bounded graph partitioning algorithm in combination with a dual clocking method (slow and fast clock pulses) that minimizes the aforesaid path balancing overheads. Experimental results show that the proposed solution reduces total number of path balancing buffers and total static power consumption by an average of 2.68× and 60%, respectively, when compared to the best of other methods for realizing SFQ circuits. However, our scheme degrades the peak throughput; therefore, it is especially valuable when the actual throughput of the SFQ circuit is much lower than the peak theoretical throughput. This is typically the case due to high-level data dependencies of the application that feeds data into an SFQ circuit.

In this work, a multi-constraint graph partitioning problem is introduced. The input is an undirected graph with costs on the edges and multiple weights on the nodes. The problem calls for a partition of the node set into a fixed number of clusters, such that each cluster satisfies a collection of node weight constraints, and the total cost of the edges whose end nodes are in the same cluster is minimized. It arises as a sub-problem of an integrated vehicle and pollster problem from a real-world application. Two integer programming formulations are provided, and several families of valid inequalities associated with the respective polyhedra are proved. An exact algorithm based on Branch & Bound and cutting planes is proposed, and it is tested on real-world instances.

In the real world, the duality of high-dimensional data is widespread. The coclustering method has been widely used because they can exploit the co-occurring structure between samples and features. In fact, most of the existing coclustering methods cluster the graphs in the original data matrix. However, these methods fail to output an affinity graph with an explicit cluster structure and still call for the postprocessing step to obtain the final clustering results. In addition, these methods are difficult to find a good projection direction to complete the clustering task on high-dimensional data. In this article, we modify the flexible manifold embedding theory and embed it into the bipartite spectral graph partition. Then, we propose a new method called structured optimal graph-based clustering with flexible embedding (SOGFE). The SOGFE method can learn an affinity graph with an optimal and explicit clustering structure and does not require any postprocessing step. Additionally, the SOGFE method can learn a suitable projection direction to map high-dimensional data to a low-dimensional subspace. We perform extensive experiments on two synthetic data sets and seven benchmark data sets. The experimental results verify the superiority, robustness, and good projection direction selection ability of our proposed method.

Social Big Data is generated by interactions of connected users on social network. Sharing of opinions and contents amongst users, reviews of users for products, result in social Big Data. If any user intends to select products such as movies, books, etc., from e-commerce sites or view any topic or opinion on social networking sites, there are a lot of options and these options result in information overload. Social recommendation systems assist users to make better selection as per their likings. Recent research works have improved recommendation systems by using matrix factorization, social regularization or social trust inference. Furthermore, these improved systems are able to alleviate cold start and sparsity, but not efficient for scalability. The main focus of this article is to improve scalability in terms of locality and throughput and provides better recommendations to users with large-scale data in less response time. In this article, the social big graph is partitioned and distributed on different nodes based on Pregel and Giraph. In the proposed approach ScaleRec, partitioning is based on direct as well as indirect trust between users and comparison with state-of-the-art approaches proves that statistically better partitioning quality is achieved using proposed approach. In ScaleRec, hyperedge and transitive closure are used to enhance social trust amongst users. Experiment analysis on standard datasets such as Epinions and LiveJournal proves that better locality and recommendation accuracy is achieved by using ScaleRec.

There is the significant interest nowadays in developing the frameworks for parallelizing the processing of large graphs such as social networks, web graphs, etc. The work has been proposed to parallelize the graph processing on clusters (distributed memory), multicore machines (shared memory) and GPU devices. Most existing research on GPU-based graph processing employs the vertex-centric processing model and the Compressed Sparse Row (CSR) form to store and process a graph. However, they suffer from irregular memory access and load imbalance in GPU, which hampers the full exploitation of GPU performance. In this paper, we present WolfGraph, a GPU-based graph processing framework that addresses the above problems. WolfGraph adopts the edge-centric processing, which iterates over the edges rather than vertices. The data structure and graph partition in WolfGraph are carefully crafted so as to minimize the graph pre-processing and allow the coalesced memory access. WolfGraph fully utilizes the GPU power by processing all edges in parallel. We also develop a new method, called Concatenated Edge List (CEL), to process a graph that is bigger than the global memory of GPU. WolfGraph allows the users to define their own graph-processing methods and plug them into the WolfGraph framework. Our experiments show that WolfGraph achieves 7-8x speedup over GraphChi and X-Stream when processing large graphs, and it also offers 65% performance improvement over the existing GPU-based, vertex-centric graph processing frameworks, such as Gunrock.

Bug triaging is the process of prioritizing bugs based on their severity, frequency, and risk in order to be assigned to appropriate developers for validation and resolution. This article introduces a graph-based feature augmentation approach for enhancing bug triaging systems using machine learning. A new feature augmentation approach that utilizes graph partitioning based on neighborhood overlap is proposed. Neighborhood overlap is a quite effective approach for discovering relationships in social graphs. Terms of bug summaries are represented as nodes in a graph, which is then partitioned into clusters of terms. Terms in strong clusters are augmented to the original feature vectors of bug summaries based on the similarity between the terms in each cluster and a bug summary. We employed other techniques such as term frequency, term correlation, and topic modeling to identify latent terms and augment them to the original feature vectors of bug summaries. Consequently, we utilized frequency, correlation, and neighborhood overlap techniques to create another feature augmentation approach that enriches the feature vectors of bug summaries to use them for bug triaging. The new modified vectors are used to classify bug reports into different priorities. Bug Triage in this context is to correctly recognize the priority of new bugs. Several classification algorithms are tested using the proposed methods. Experimental results on a data set with Eclipse bug reports extracted from the Bugzilla tracking system have shown that our approach outperformed the existing bug triaging systems including modern techniques that utilize deep learning.

People of all ages enjoy solving geometric puzzles. However, finding suitable puzzles, e.g., puzzles with a moderate level of difficulty or puzzles with intellectually stimulating shapes can be difficult. In addition, designing innovative and appealing puzzles requires demanding effort and, typically, involves many trial and error processes. In this paper, we introduce a computational approach for designing geometric puzzles. Existing approaches employ bottom-up, constructive algorithms to generate puzzle pieces; therefore, intervening in the piece generation procedure is difficult. Differing from existing approaches that generate puzzles automatically or semi-automatically, we propose a top-down, partitioning-based approach, that enables us to control and edit piece shapes. With a subtle modification, the proposed algorithm can be easily extended to both 3D polycube and 2D polyomino puzzle design. To generate a variety of piece shapes, the proposed approach involves a capacity-constrained graph partitioning algorithm combined with polyomino tiling. We demonstrate the versatility of the proposed approach through various example designs, including fabricated puzzles, created using the proposed method.

With increasingly complex neural network architectures and heterogeneous device characteristics, finding a reasonable graph partitioning and device placement strategy is challenging. There have been prior attempts at learned approaches for solving device placement, these approaches are computationally expensive, unable to handle large graphs consisting over 50000 nodes, and do not generalize well to unseen graphs. To address all these limitations, we propose an efficient single-shot, generalized deep RL method (SGDP) based on a scalable sequential attention mechanism over a graph neural network that is transferable to new graphs. On a diverse set of representative deep learning models, our method on average achieves 20% improvement over human placement and 18% improvement over the prior art with 15× faster convergence. We are the first to demonstrate super human performance on 8-layer recurrent neural network language model and 8-layer GNMT consisting of over 50000 nodes, on 8-GPUs. We provide rationales and sensitivity study on model architecture selections.

Since p-spectral clustering has good performance in many practical problems, it has attracted great attention. The Cheeger cut criterion is used in p-spectral clustering to do graph partition. However, due to the improper affinity measure and outliers, the original p-spectral clustering algorithm is not effective in dealing with manifold data. To solve this problem, we propose a manifold p-spectral clustering (M-pSC) using path-based affinity measure. First, we design a path-based affinity function to describe the complex structures of manifold data. This affinity function obeys the clustering assumption that the data pairs within the manifold structure share high affinities, and the data pairs between different manifold structures share low affinities. This will help us construct a good affinity matrix, which carry more category information of the points. Then we propose a M-pSC algorithm using the path-based affinity function. In the Cheeger cut criterion, the p-Laplacian matrix are constructed based on the manifold affinity function, and the final clustering results are obtained by using the eigenvectors of graph p-Laplacian. At last, the proposed algorithm is tested on several public data sets and the experiments show that our algorithm is adaptive to different manifold data. Compared with other popular clustering algorithms, our algorithm has good clustering quality and robustness.

Matrix Factorization (MF) based on Stochastic Gradient Descent (SGD) is a powerful machine learning technique to derive hidden features of objects from observations. In this article, we design a highly parallel architecture based on Field-Programmable Gate Array (FPGA) to accelerate the training process of the SGD-based MF algorithm. We identify the challenges for the acceleration and propose novel algorithmic optimizations to overcome them. By transforming the SGD-based MF algorithm into a bipartite graph processing problem, we propose a 3-level hierarchical partitioning scheme that enables conflict-minimizing scheduling and processing of edges to achieve significant speedup. First, we develop a fast heuristic graph partitioning approach to partition the bipartite graph into induced subgraphs; this enables to efficiently use the on-chip memory resources of FPGA for data reuse and completely hide the data communication between FPGA and external memory. Second, we partition all the edges of each subgraph into non-overlapping matchings to extract the maximum parallelism. Third, we propose a batching algorithm to schedule the execution of the edges inside each matching to reduce the memory access conflicts to the on-chip RAMs of FPGA. Compared with non-optimized FPGA-based baseline designs, the proposed optimizations result in up to 60× data dependency reduction, 4.2× bank conflict reduction, and 15.4× speedup. We evaluate the performance of our design using a state-of-the-art FPGA device. Experimental results show that our FPGA accelerator sustains a high computing throughput of up to 217 billion floating-point operations per second (GFLOPS) for training very large real-life sparse matrices. Compared with highly-optimized GPU-based accelerators, our FPGA accelerator achieves up to 12.7× speedup. Based on our optimization methodology, we also implement a software-based design on a multi-core platform, which demonstrates 1.3× speedup compared with the state-of-the-art multi-core implementation.

Traffic forecasting approaches are critical to developing adaptive strategies for mobility. Traffic patterns have complex spatial and temporal dependencies that make accurate forecasting on large highway networks a challenging task. Recently, diffusion convolutional recurrent neural networks (DCRNNs) have achieved state-of-the-art results in traffic forecasting by capturing the spatiotemporal dynamics of the traffic. Despite the promising results, however, applying DCRNNs for large highway networks still remains elusive because of computational and memory bottlenecks. This paper presents an approach for implementing a DCRNN for a large highway network that overcomes these limitations. This approach uses a graph-partitioning method to decompose a large highway network into smaller networks and trains them independently. The efficacy of the graph-partitioning-based DCRNN approach to model the traffic on a large California highway network with 11,160 sensor locations is demonstrated. An overlapping-nodes approach for the graph-partitioning-based DCRNN is developed to include sensor locations from partitions that are geographically close to a given partition. Furthermore, it is demonstrated that the DCRNN model can be used to forecast the speed and flow simultaneously and that the forecasted values preserve fundamental traffic flow dynamics. This approach to developing DCRNN models that represent large highway networks can be a potential core capability in advanced highway traffic monitoring systems, where a trained DCRNN model forecasting traffic at all sensor locations can be used to adjust traffic management strategies proactively based on anticipated future conditions.

Directed graphs are widely used to model data flow and execution dependencies in streaming applications. This enables the utilization of graph partitioning algorithms for the problem of parallelizing execution on multiprocessor architectures under hardware resource constraints. However due to program memory restrictions in embedded multiprocessor systems, applications need to be divided into parts without cyclic dependencies. We found that this can be done by a subsequent second graph partitioning step with an additional acyclicity constraint. We have four main contributions. First, we show that this more constrained version of the graph partitioning problem is NP-complete and present linear time heuristics. We then integrate them into an existing multi-level graph partitioning framework to better handle large graphs. This achieves a 9% reduction of the edge cut compared to the previous single-level algorithm. Based on this, we engineer an evolutionary algorithm to further reduce the cut, achieving a 30% reduction on average compared to the state of the art. Finally, we integrate the partitioning heuristics into a graph compiler for an embedded multiprocessor architecture and show that this can reduce the amount of communication for a real-world imaging application and thereby accelerate it by an average of 11%. It is shown that the compiler can emit optimized code for vastly different hardware platforms using the heuristics. In addition, we demonstrate how a custom fitness function for the evolutionary algorithm can be used to optimize other objectives like load balancing if the communication volume is not predominantly important on a given hardware platform.

We give a distributed algorithm in the CONGEST model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et al. (Proceedings of the 30th International Symposium on Distributed Computing, pp. 43–56, 2016), who recently initiated the study of property testing in the distributed setting, our algorithm gives the following guarantee: For a graph $$G = (V,E)$$ and a distance parameter $$\epsilon $$ , if G is planar, then every node outputs accept, and if G is $$\epsilon $$ -far from being planar (i.e., more than $$\epsilon \cdot |E|$$ edges need to be removed in order to make G planar), then with probability $$1-1/\mathrm{poly}(n)$$ at least one node outputs reject. The algorithm runs in $$O(\log |V|\cdot \mathrm{poly}(1/\epsilon ))$$ rounds, and we show that this result is tight in terms of the dependence on |V|. Our algorithm combines several techniques of graph partitioning and local verification of planar embeddings. Furthermore, we show how a main subroutine in our algorithm can be applied to derive additional results for property testing of cycle-freeness and bipartiteness, as well as the construction of spanners, in minor-free (unweighted) graphs.

Considering the scarcity of water resources, it is necessary to identify the leakage in Water Distribution Networks (WDNs). In this paper, a step-by-step method of WDN decomposition has been introd...

Graphs are used to store relationships on a variety of topics, such as road map data and social media connections. Processing this data allows one to uncover insights from its structure. However, while analyzing graphs with traditional processors, the graph connectivity can result in irregular memory access patterns and thus poor data locality that can result in low performance. Processing-in-Memory (PIM) is an attractive alternative for graph processing, as it can reduce data movement by bringing the computation closer to the data itself. While PIM-based techniques have been shown to improve graph processing performance, there is still room for improvement, as critical bottlenecks exist when connecting multiple PIM-based accelerators into larger clusters. Although a number of recent proposals have aimed to reduce inter-accelerator data movement, their techniques have generally overlooked the potential to optimize how the graph’s connectivity can lead to a more efficient hardware mapping. In fact, many real-world graphs have a small percentage of high-degree nodes that connect widely to a large number of other nodes. By clustering these nodes into communities, one can more efficiently map them to hardware, minimizing expensive inter-accelerator communication, a key performance bottleneck in these accelerators. To capitalize on this observation, we propose PIM-GraphSCC, the first PIM-based graph processor that exploits a graph’s connectivity to significantly reduce communication over critical resources: the inter-accelerator links. By partitioning graphs into communities, PIM-GraphSCC provides a community-aware graph partitioning scheme that reduces inter-accelerator data movement by up to 93 percent compared to modern graph processing schemes.

During the last years, graph-based representations are experiencing a growing usage in visual recognition and retrieval due to their ability to capture both structural and appearance-based information. Thus, they provide a greater representational power than classical statistical frameworks. However, graph-based representations leads to high computational complexities usually dealt by graph embeddings or approximated matching techniques. Despite their representational power, they are very sensitive to noise and small variations of the input image. With the aim to cope with the time complexity and the variability present in the generated graphs, in this paper we propose to construct a novel hierarchical graph representation. Graph clustering techniques adapted from social media analysis have been used in order to contract a graph at different abstraction levels while keeping information about the topology. Abstract nodes attributes summarise information about the contracted graph partition. For the proposed representations, a coarse-to-fine matching technique is defined. Hence, small graphs are used as a filtering before more accurate matching methods are applied. This approach has been validated in real scenarios such as classification of colour images or retrieval of handwritten words (i.e. word spotting).

Dynamic Topic Modeling (DTM) is the ultimate solution for extracting topics from short texts generated in Online Social Networks (OSNs) like Twitter. It requires to be scalable and to be able to account for sparsity and dynamicity of short texts. Current solutions combine probabilistic mixture models like Dirichlet Multinomial or Pitman-Yor Process with approximate inference approaches like Gibbs Sampling and Stochastic Variational Inference to, respectively, account for dynamicity and scalability of DTM. However, these methods basically rely on weak probabilistic language models, which do not account for sparsity in short texts. In addition, their inference is based on iterative optimizations, which have scalability issues when it comes to DTM. We present GDTM, a single-pass graph-based DTM algorithm, to solve the problem. GDTM combines a context-rich and incremental feature representation method with graph partitioning to address scalability and dynamicity and uses a rich language model to account for sparsity. We run multiple experiments over a large-scale Twitter dataset to analyze the accuracy and scalability of GDTM and compare the results with four state-of-the-art models. In result, GDTM outperforms the best model by $$11\%$$ 11 % on accuracy and performs by an order of magnitude faster while creating four times better topic quality over standard evaluation metrics.

Automated cell segmentation and tracking enables the quantification of static and dynamic cell characteristics and is significant for disease diagnosis, treatment, drug development, and other biomedical applications. This paper introduces a method for fully automated cell tracking, lineage construction, and quantification. Cell detection is performed in the joint spatio-temporal domain by a motion diffusion-based Partial Differential Equation (PDE) combined with energy minimizing active contours. In the tracking stage, we adopt a variational joint local-global optical flow technique to determine the motion vector field. We utilize the predicted cell motion jointly with spatial cell features to define a maximum likelihood criterion to find inter-frame cell correspondences assuming Markov dependency. We formulate cell tracking and cell event detection as a graph partitioning problem. We propose a solution obtained by minimization of a global cost function defined over the set of all cell tracks. We construct a cell lineage tree that represents the cell tracks and cell events. Finally, we compute morphological, motility, and diffusivity measures and validate cell tracking against manually generated reference standards. The automated tracking method applied to reference segmentation maps produces an average tracking accuracy score ( $TRA$ T R A ) of 99 percent, and the fully automated segmentation and tracking system produces an average $TRA$ T R A of 89 percent.

A dynamic ridesharing system is a platform that connects drivers who use their personal vehicles to travel with riders who are in need of transportation, on a short notice. Since each driver/rider may have several potential matches, to achieve a high performance level, the ridesharing operator needs to make the matching decisions based on a global view of the system that includes all active riders and drivers. Consequently, the ride-matching problem that needs to be solved can become computationally expensive, especially when the system is operating over a large region, or when it faces high demand levels during certain hours of the day. This paper develops a graph partitioning methodology based on the bipartite graph that arises in the one-to-one ride-matching problem. The proposed method decomposes the original graph into multiple sub-graphs with the goal of reducing the overall computational complexity of the problem as well as providing high quality solutions. We further show that this methodology can be extended to more complex ride-matching problems in a dynamic ride-sharing system. Using numerical experiments, we showcase the advantages of the new partitioning method for different forms of ride-matching problems. Moreover, a sensitivity analysis is conducted to show the impact of different parameters on the quality of our solution.

Given an undirected graph G = ( V , E ) with vertex set V and edge set E , the minimum conductance graph partitioning problem is to partition V into two subsets s = ( A , A ) such that its quotient cut is minimized. This problem arises in a number of significant real-world applications; however, it is known to be NP-hard and thus computationally challenging. We present in this work a hybrid evolutionary algorithm for finding low conductance of large graphs. To ensure a high search efficiency and efficacy, the algorithm relies on the general memetic search framework and integrates specialized search components (e.g., fast local optimization with a progressive neighborhood and quality-and-diversity based pool management). Computational experiments on a set of 60 large-scale real-world benchmark instances in the literature with up to 23 million vertices lead to the following main findings. First, the algorithm competes very favorably with the state-of-the-art methods and is able to find efficiently solutions of low conductance for the tested instances. Second, the dedicated search components are essential to ensure the high performance of the algorithm. Third, the algorithm can further ameliorate the solutions obtained by the well-known max-flow quotient-cut improvement algorithm. Finally, we illustrate an application of using the algorithm to detect meaningful community structures in complex networks.

In this paper, we present Prometheus, a graph partitioning based algorithm that creates multiple variable decompositions efficiently for learning Sum-Product Network structures across both continuous and discrete domains. Prometheus proceeds by creating multiple candidate decompositions that are represented compactly with an acyclic directed graph in which common parts of different decompositions are shared. It eliminates the correlation threshold hyperparameter often used in other structure learning techniques, allowing Prometheus to learn structures that are robust in low data regimes. Prometheus outperforms other structure learning techniques in 30 discrete and continuous domains. We also extend Prometheus to exploit sparsity in correlations between features in order to obtain an efficient sub-quadratic algorithm (w.r.t. the number of features) that scales better to high dimensional datasets.

We consider an extended version of the classical Max-$$k$$ k -Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved.

Pressure Driven Analysis (PDA) method provides the ability to simulate Water Distribution Networks (WDNs) more realistically. Most of the PDA-based models use either the Newton–Raphson method or th...

This paper studies incremental graph partitioning. Given a (vertex-cut or edge-cut) partition C(G) of a graph G and updates ΔG to G, it is to compute changes ΔO to C(G), yielding a partition of the updated graph such that (a) the new partition is load-balanced, (b) its cut size is minimum, and (c) the changes ΔO are also minimum. We show that this tri-criteria optimization problem is NP-complete, even when ΔG has a constant size. Worse yet, it is unbounded, i.e., there exists no algorithm that computes such ΔO with a cost that is determined only by the changes ΔG and ΔO. We approach this by proposing to incrementalize widely-used graph partitioners A into heuristically-bounded incremental algorithms A Δ . Given graph G, updates ΔG to G and a partition A(G) of G by A, AΔ computes changes ΔO to A(G) such that (1) applying ΔO to A(G) produces a new partition of the updated graph although it may not be exactly the one derived by A, (2) it retains the same bounds on balance and cut sizes as A, and (3) ΔO is decided by ΔG alone. We show that we can deduce A Δ from both vertex-cut and edge-cut partitioners A, retaining their bounds. Using real-life and synthetic data, we verify the efficiency and partition quality of our incremental partitioners.

Cloud computing has emerged as a promising computational infrastructure for cost-efficient workflow execution by provisioning on-demand resources in a pay-as-you-go manner. While scientific workflows require accessing community-wide resources, they usually need to be performed in collaborative cloud environments composed of multiple datacenters. Although such environments facilitate scientific collaboration, the movements of input and intermediate datasets across geographically distributed datacenters may cause intolerable latency that would hinder efficient execution of large-scale data-intensive scientific workflows. To address the problem, in this article we propose a novel multi-level K-cut graph partitioning algorithm to minimize the volume of data transfer across datacenters while satisfying load balancing and fixed data constraints. The algorithm first contracts the fixed input datasets in the same datacenter and their consuming tasks, and coarsens the contracted graph to a predefined scale in a level-by-level manner. Then, a K-cut algorithm is used to partition the resulted graph into K parts such that the cut size is minimized. After that, the partitioned graph is projected back to the original workflow graph, during which the load balancing constraint is maintained. We evaluate our algorithm using three real-world workflow applications and the results demonstrate that the proposed algorithm outperforms other state-of-the-art algorithms.

This letter addresses the challenge of solving large-scale Mixed Integer Linear Programs (MILPs). A resolution scheme is proposed for the class of MILPs with a hidden constraint-coupled multi-agent structure. In particular, we focus on the problem of disclosing such a structure to then apply a computationally efficient decentralized optimization algorithm recently proposed in the literature. The multi-agent reformulation problem consists in manipulating the matrix defining the linear constraints of the MILP so as to put it in a singly-bordered block-angular form, where the blocks define local constraints and decision variables of the agents, whereas the border defines the coupling constraints. We translate the matrix reformulation problem into a hyper-graph partitioning problem and introduce a novel algorithm which accounts for the specific requirements on the singly-bordered block-angular form to best take advantage of the decentralized optimization approach. Numerical results show the effectiveness of the proposed hyper-graph partitioning algorithm.

Computing path queries such as the shortest path in public transport networks is challenging because the path costs between nodes change over time. A reachability query from a node at a given start time on such a network retrieves all points of interest (POIs) that are reachable within a given cost budget. Reachability queries are essential building blocks in many applications, for example, group recommendations, ranking spatial queries, or geomarketing. We propose an efficient solution for reachability queries in public transport networks. Currently, there are two options to solve reachability queries. (1) Execute a modified version of Dijkstra’s algorithm that supports time-dependent edge traversal costs; this solution is slow since it must expand edge by edge and does not use an index. (2) Issue a separate path query for each single POI, i.e., a single reachability query requires answering many path queries. None of these solutions scales to large networks with many POIs. We propose a novel and lightweight reachability index. The key idea is to partition the network into cells. Then, in contrast to other approaches, we expand the network cell by cell. Empirical evaluations on synthetic and real-world networks confirm the efficiency and the effectiveness of our index-based reachability query solution.