Search

A team of identical and oblivious ant-like agents - a(ge)nts - leaving pheromone traces, are programmed to jointly patrol an area modeled as a graph. They perform this task using simple local interactions, while also achieving the important byproduct of partitioning the graph into roughly equal-sized disjoint sub-graphs. Each a(ge)nt begins to operate at an arbitrary initial location, and throughout its work does not acquire any information on either the shape or size of the graph, or the number or whereabouts of other a(ge)nts. Graph partitioning occurs spontaneously, as each of the a(ge)nts patrols and expands its own pheromone-marked sub-graph, or region. This graph partitioning algorithm is inspired by molecules hitting the borders of air filled elastic balloons: an a(ge)nt that hits a border edge from the interior of its region more frequently than an external a(ge)nt hits the same edge from an adjacent vertex in the neighboring region, may conquer that adjacent vertex, expanding its region at the expense of the neighbor. Since the rule of patrolling a region ensures that each vertex is visited with a frequency inversely proportional to the size of the region, in terms of vertex count, a smaller region will effectively exert higher "pressure" at its borders, and conquer adjacent vertices from a larger region, thereby increasing the smaller region and shrinking the larger. The algorithm, therefore, tends to equalize the sizes of the regions patrolled, resembling a set of perfectly elastic physical balloons, confined to a closed volume and filled with an equal amount of air. The pheromone based local interactions of agents eventually cause the system to evolve into a partition that is close to balanced rather quickly, and if the graph and the number of a(ge)nts remain unchanged, it is guaranteed that the system settles into a stable and balanced partition. [ABSTRACT FROM AUTHOR]

We prove that there exists an absolute constant C>0$$ C>0 $$ such that, for any positive integer k$$ k $$, every graph G$$ G $$ with minimum degree at least Ck$$ Ck $$ admits a vertex‐partition V(G)=S∪T$$ V(G)=S\cup T $$, where both G[S]$$ G\left[S\right] $$ and G[T]$$ G\left[T\right] $$ have minimum degree at least k$$ k $$, and every vertex in S$$ S $$ has at least k$$ k $$ neighbors in T$$ T $$. This confirms a question posted by Kühn and Osthus (J. Comb. Theory Ser. B. 88 (2003), 29–43.) and is tight up to a constant factor. Our proof combines probabilistic methods with structural arguments based on Ore's theorem on f$$ f $$‐factors of bipartite graphs. [ABSTRACT FROM AUTHOR]

In recent years, graph similarity algorithms have been extensively developed based on neural networks. However, with an increase in the node count in graphs, these models either suffer from a reduced representation ability or face a significant increase in the computational cost. To address this issue, a graph similarity algorithm based on graph partitioning and attention mechanisms was proposed in this study. Our method first divided each input graph into the subgraphs to directly extract the local structural features. The residual graph convolution and multihead self-attention mechanisms were employed to generate node embeddings for each subgraph, extract the feature information from the nodes, and regenerate the subgraph embeddings using varying attention weights. Initially, rough cosine similarity calculations were performed on all subgraph pairs from the two sets of subgraphs, with highly similar pairs selected for precise similarity computation. These results were then integrated into the similarity score for the input graph. The experimental results indicated that the proposed learning algorithm outperformed the traditional algorithms and similar computing models in terms of graph similarity computation performance. [ABSTRACT FROM AUTHOR]

Partition problems in graphs are extremely important in applications, as shown in the Data Science and Machine Learning literature. One approach is spectral partitioning based on a Fiedler vector, i.e., an eigenvector corresponding to the second smallest eigenvalue a (G) of the Laplacian matrix L G of the graph G. This problem corresponds to the minimization of a quadratic form associated with L G , under certain constraints involving the ℓ 2 -norm. We introduce and investigate a similar problem, but using the ℓ 1 -norm to measure distances. This leads to a new parameter b (G) as the optimal value. We show that a well-known cut problem arises in this approach, namely the sparsest cut problem. We prove connectivity results and different bounds on this new parameter, relate to Fiedler theory and show explicit expressions for b (G) for trees. We also comment on an ℓ ∞ -norm version of the problem. [ABSTRACT FROM AUTHOR]

In the United States, regions (such as states or counties) are frequently divided into districts for the purpose of electing representatives. How the districts are drawn can have a profound effect on who is elected, and drawing the districts to give an advantage to a certain group is known as gerrymandering. It can be surprisingly difficult to detect when gerrymandering is occurring, but one algorithmic method is to compare a current districting plan to a large number of randomly sampled plans to see whether it is an outlier. Recombination Markov chains are often used to do this random sampling: randomly choose two districts, consider their union, and split this union up in a new way. This approach works well in practice and has been widely used, including in litigation, but the theory behind it remains underdeveloped. For example, it is not known if recombination Markov chains are irreducible, that is, if recombination moves suffice to move from any districting plan to any other. Irreducibility of recombination Markov chains can be formulated as a graph problem: for a planar graph G , is the space of all partitions of G into k connected subgraphs (k districts) connected by recombination moves? While the answer is yes when districts can be as small as one vertex, this is not realistic in real-world settings where districts must have approximately balanced populations. Here we fix district sizes to be k 1 ± 1 vertices, k 2 ± 1 vertices, ... for fixed k 1 , k 2 , ... , a more realistic setting. We prove for arbitrarily large triangular regions in the triangular lattice, when there are three simply connected districts, recombination Markov chains are irreducible. This is the first proof of irreducibility under tight district size constraints for recombination Markov chains beyond small or trivial examples. The triangular lattice is the most natural setting in which to first consider such a question, as graphs representing states/regions are frequently triangulated. The proof uses a sweep-line argument, and there is hope it will generalize to more districts, triangulations satisfying mild additional conditions, and other redistricting Markov chains. [ABSTRACT FROM AUTHOR]

Given two integers ℓ and p as well as ℓ graph classes H1, . . ., Hℓ, the problems GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ) ask, given graph G as input, whether V (G), V (G), E(G) respectively can be partitioned into ℓ sets S1, . . ., Sℓ such that, for each i between 1 and ℓ, G[Si] ∈ Hi, G[Si] ∈ Hi, (V (G), Si) ∈ Hi respectively. Moreover in GraphPart(H1, . . ., Hℓ, p), we request that the number of edges with endpoints in different sets of the partition is bounded by p. We show that if there exist dynamic programming treedecomposition-based algorithms for recognizing the graph classes Hi, for each i, then we can constructively create a dynamic programming tree-decomposition-based algorithms for GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ). We apply this approach to known problems. For well-studied problems, like VERTEX COVER and GRAPH q-COLORING, we obtain running times that are comparable to those of the best known problemspecific algorithms. For an exotic problem from bioinformatics, called DISPLAYGRAPH, this approach improves the known algorithm parameterized by treewidth. [ABSTRACT FROM AUTHOR]

Polarimetric synthetic aperture radar (PolSAR) image classification is a critical application of remote sensing image interpretation. Most of the early algorithms that use hand-crafted features to divide the image into various scattering categories have a general classification performance. The convolutional neural networks (CNNs) show superior performance in image processing with powerful nonlinear representation capabilities. However, they also require a large amount of labeled training data, which limit the practical use of CNNs in PolSAR image classification scene where labeled data are rare and expensive. To address the previous issue, this article proposes a deep similarity clustering model with compound regularization for unsupervised PolSAR image classification. The proposed model combines an unsupervised feature extraction pipeline with Wishart distance metric and a deep clustering pipeline with feature similarity metric. The regularization combines two ingredients to preserve both the sharpness of edges and the semantic continuity of the image contents. The first is the differential constraint based on pixel-level features, and the second is the graph partition constraint based on superpixel-level features. Experiments prove the effectiveness of the proposed method on both spaceborne (RadarSat2) and airborne (E-SAR/UAVSAR) PolSAR images. The visual results and quantitative scores show that our method outperforms the traditional unsupervised methods and deep-learning-based unsupervised methods with a large margin.

Szemerédi’s Regularity Lemma (SRL) is a crucial tool in the analysis of large graphs, having made significant contributions in the proof of some sensational results in mathematics. Traditional methods for studying proteins in Protein–Protein Interaction (PPI) networks typically only extract the first-order or second-order neighbor information of proteins, ignoring the potential third-order or higher-order neighbor information between proteins, which may hide certain relationships between proteins. To explore more in-depth insights for PPI networks, we take into account the fourth-order neighbor information of proteins and reconstruct the network in this paper, naming it the weighted dense PPI network. We then partition it using SRL, which primarily utilizes the structural information and corresponds to a unique partition of the original network. Bioinformatics analyses such as those for pathway enrichment analysis and multiple sequence alignment show that our method can classify interacting protein pairs, grouping proteins with functional association, disease association, and sequence similarity together. Overall, this paper has three essential contributions: (1) we present a new model to overcome the astronomically large demand of vertices in applying SRL, and achieve protein classification; (2) we reconstruct a weighted dense PPI network which can make SRL work and mine potential interactions more efficiently; and (3) proteins in the same class partitioned by our method not only have sequence similarity, but also have functional associations. [ABSTRACT FROM AUTHOR]

In this paper, we design a new branch-and-bound algorithm to solve a variant of graph partition problem called two-level graph partition problem, which is arisen in mobile wireless communications. We first exploit the two-level structure of the problem, and propose a new semidefinite relaxation for the problem. Some valid constraints are derived to enhance the tightness of the semidefinite relaxation. Furthermore, we analyze the symmetric structure of the two-level graph partition problem, and propose an effective branch pruning rule to handle the symmetry. Based on the proposed semidefinite relaxation and the symmetry handing technique, a branch-and-bound algorithm is proposed. Our numerical results show that the proposed algorithm outperforms the existing linear integer programming based algorithm on two-level graph partition problems with high density. [ABSTRACT FROM AUTHOR]

Community detection is a vital task in many fields, such as social networks and financial analysis, to name a few. The Louvain method, the main workhorse of community detection, is a popular heuristic method. To apply it to large-scale graph networks, researchers have proposed several parallel Louvain methods (PLMs), which suffer from two challenges: the latency in the information synchronization, and the community swap. To tackle these two challenges, we propose an isolate sets based parallel Louvain method (IPLM) and a fusion IPLM with the hashtables based Louvain method (FIPLM), which are based on a novel graph partition algorithm. Our graph partition algorithm divides the graph network into subgraphs called isolate sets, in which the vertices are relatively decoupled from others. We first describe the concepts and properties of the isolate set. Second we propose an algorithm to divide the graph network into isolate sets, which enjoys the same computation complexity as the breadth-first search. Third, we propose IPLM, which can efficiently calculate and update vertices information in parallel without latency or community swap. Finally, we achieve further acceleration by FIPLM, which maintains a high quality of community detection with a faster speedup than IPLM. Our two methods are for shared-memory architecture, and we implement our methods on an 8-core PC; the experiments show that IPLM achieves a maximum speedup of 4.62x and outputs higher modularity (maximum 4.76%) than the serial Louvain method on 14 of 18 datasets. Moreover, FIPLM achieves a maximum speedup of 7.26x. [ABSTRACT FROM AUTHOR]

The graph isomorphism, as a key task in graph data analysis, is of great significance for the understanding, feature extraction, and pattern recognition of graph data. The best performance of traditional methods is the quasi-polynomial time complexity, which is infeasible for huge graphs. This paper aims to propose a lightweight graph network to resolve the problem of isomorphism in huge graphs. We propose a partitioning algorithm with linear time complexity based on isomorphic necessary condition to handle network graphs that cannot be fully computed by a single computer. We use anti-weight convolution analysis and skip connections to obtain a more stable representation with fewer layers and parameters. We implement simulations on personal computer (PC) with graphs consisting of hundred millions of edges, demonstrating the identification performance ( $ \gt\!\!98\%$ ) and time efficiency.

Graph partitioning is an effective way to improve the performance of parallel computing. However, the research of graph partitioning is driven by the demand of practical applications. In this paper, we propose a streaming graph partitioning algorithm based on heterogeneous-aware for distributed heterogeneous computing environment. It not only considers the difference of network bandwidth and the compute ability of computer nodes, but also considers the shared resources competition between cores in a high-speed network. Taking breadth first search, single source shortest path and PageRank algorithms as examples, compared with the streaming algorithms without considering the heterogeneous environment, the efficiency of graph computing is improved on average by 38%, 45.7% and 61.8% respectively. Meanwhile, in view of the low efficiency of streaming graph partitioning based on adjacent vertex structure, we design a cache management mechanism based on adjacent edge structure for streaming graph partitioning, which effectively improves the partitioning efficiency. The experimental results show that our method is suitable for graph vertex assignment in distributed heterogeneous cluster environment. [ABSTRACT FROM AUTHOR]

Copyright of Control Theory & Applications / Kongzhi Lilun Yu Yinyong is the property of Editorial Department of Control Theory & Applications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Graph partitioning is crucial to parallel computations on large graphs. The choice of partitioning strategies has strong impact on the performance of graph algorithms. For an algorithm of our interest, what partitioning strategy fits it the best and improves its parallel execution? Is it possible to provide a uniform partition to a batch of algorithms that run on the same graph simultaneously, and speed up each and every of them? This paper aims to answer these questions. We propose an application-driven hybrid partitioning strategy that, given a graph algorithm A , learns a cost model for A as polynomial regression. We develop partitioners that, given the learned cost model, refine an edge-cut or vertex-cut partition to a hybrid partition and reduce the parallel cost of A . Moreover, we extend the cost-driven strategy to support multiple algorithms at the same time and reduce the parallel cost of each of them. Using real-life and synthetic graphs, we experimentally verify that our partitioning strategy improves the performance of a variety of graph algorithms, up to 22.5 × . [ABSTRACT FROM AUTHOR]

Global color consistency correction for multiview images in three-dimensional (3-D) reconstruction is an important problem. The color differences between the images will affect the result of dense matching, thereby reducing the geometric accuracy of the mesh model. Moreover, it will also affect the result of texture mapping, causing color differences in the textured model. The color correction method based on global optimization is mainly used to solve this problem. And existing methods usually use sparse matching points as the color correspondences, but the correction results are not accurate enough as a result of the sparsity of the points. Besides, their efficiency of solving large-scale images globally is low. This article proposes a novel color correction method to eliminate the color differences between large-scale multiview images effectively. The core idea of our method is to group images by graph partition algorithm, and then perform intragroup correction and intergroup correction in sequence. First, for each pair of images, we calculate the reliable matching regions around the sparse points as the color correspondences according to the local homography principle. Compared with sparse matching points, our strategy can achieve more accurate color correction results. Next, for large-scale images, we partition them into many groups. For each group of images, the correction parameters are solved to eliminate the color differences of the images included in the group. Finally, we eliminate the color differences between groups by intergroup correction to achieve overall color consistency. Experimental results on typical datasets demonstrate that the proposed method is better than the current representative methods. The proposed method shows better color consistency in the extreme cases, and also exhibits higher computational efficiency on large-scale image sets.

Dynamics always exist in complex systems. Graphs (complex networks) are a mathematical form for describing a complex system abstractly. Dynamics can be learned efficiently from the structure and dynamics state of a graph. Learning the dynamics in graphs plays an important role in predicting and controlling complex systems. Most of the methods for learning dynamics in graphs run slowly in large graphs. The complexity of the large graph's structure and its nonlinear dynamics aggravate this problem. To overcome these difficulties, we propose a general framework with two novel methods in this paper, the Dynamics-METIS (D-METIS) and the Partitioned Graph Neural Dynamics Learner (PGNDL). The general framework combines D-METIS and PGNDL to perform tasks for large graphs. D-METIS is a new algorithm that can partition a large graph into multiple subgraphs. D-METIS innovatively considers the dynamic changes in the graph. PGNDL is a new parallel model that consists of ordinary differential equation systems and graph neural networks (GNNs). It can quickly learn the dynamics of subgraphs in parallel. In this framework, D-METIS provides PGNDL with partitioned subgraphs, and PGNDL can solve the tasks of interpolation and extrapolation prediction. We exhibit the universality and superiority of our framework on four kinds of graphs with three kinds of dynamics through an experiment. [ABSTRACT FROM AUTHOR]

Given a vertex-weighted connected graph G = (V , E , w (·)) , the maximally balanced connected graphk-partition (k-BGP) seeks to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected and the weights of these k parts are as balanced as possible. When the concrete objective is to maximize the minimum (to minimize the maximum, respectively) weight of the k parts, the problem is denoted as max–mink-BGP (min–maxk-BGP, respectively), and has received much study since about four decades ago. On general graphs, max–mink-BGP is strongly NP-hard for every fixed k ≥ 2 , and remains NP-hard even for the vertex uniformly weighted case; when k is part of the input, the problem is denoted as max–min BGP, and cannot be approximated within 6/5 unless P = NP. In this paper, we study the tripartition problems from approximation algorithms perspective and present a 3/2-approximation for min–max 3-BGP and a 5/3-approximation for max–min 3-BGP, respectively. These are the first non-trivial approximation algorithms for 3-BGP, to our best knowledge. [ABSTRACT FROM AUTHOR]

Introduction: Despite huge investments in new technology and transportation infrastructure, terrible accidents still remain a reality of traffic. Methods: Severe traffic accidents were analyzed from four prevailing modes of today's transportations: sea, air, railway, and road. Main root causes of all four accidents were defined with implementation of the approach, based on Flanagan's critical incident technique. In accordance with Molan's Availability Humanization model (AH model), possible preventive or humanization interventions were defined with the focus on technology, environment, organization, and human factors. Results: According to our analyses, there are significant similarities between accidents. Root causes of accidents, human behavioral patterns, and possible humanization measures were presented with rooted graphs. It is possible to create a generalized model graph, which is similar to rooted graphs, for identification of possible humanization measures, intended to prevent similar accidents in the future. Majority of proposed humanization interventions are focused on organization. Organizational interventions are effective in assurance of adequate and safe behavior. Conclusions: Formalization of root cause analysis with rooted graphs in a model offers possibility for implementation of presented methods in analysis of particular events. Implementation of proposed humanization measures in a particular analyzed situation is the basis for creation of safety culture.

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.

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.

The goal of this article provides the common formula for Minimal Domination Cardinality for all Hamiltonian Path or Hamiltonian Circuit. It is explained the way of structures and characteristics of General Hamiltonian Path or Hamiltonian Circuit. It invents the result that all the Hamiltonian Circuit from the given graph should be Cycle Graph. These derived formulae are common for all graphs those have Hamiltonian path or Hamiltonian Circuit. This formula is used to find Maximal Dominating Cardinality in a simple manner. Even though complicated graph also which has Hamiltonian Circuit is evaluating the Cardinality of Maximal Dominating Set is very easy way. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V , E) , we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k ≥ 4 , no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k ≥ 3 . Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems. [ABSTRACT FROM AUTHOR]

In recent years, great efforts have been made to analyze biological systems to understand the long-run behaviors. As a well-established formalism for modelling real-life biological systems, Boolean networks (BNs) allow their representation and analysis using formal reasoning and tools. Most biological systems are robust—they can withstand the loss of links and cope with external environmental perturbations. Hence, the BNs used to model such systems are necessarily large and dense, and yet modular. However, existing analysis methods only work well on networks of moderate size. Thus, there is a great need for efficient methods that can handle large-scale BNs and for doing so it is inevitable to exploit both the structural and dynamic properties of the networks. In this paper, we propose a method towards the optimal decomposition of BNs to balance the relation between the structure and dynamics of a network. We show that our method can greatly improve the existing decomposition-based attractor detection by analyzing a number of large real-life biological networks. [ABSTRACT FROM AUTHOR]

With the advances in computing resources, the processing of huge amount of data becomes possible. However, the human ability to identify patterns from such data has not scaled accordingly. Consequently, efficient computational approaches for condensing and simplifying data are becoming essential for uncovering actionable insights, especially the big social networks. Many large datasets analyzed today are represented with the help of graphs. In many real-world applications, summarizing large graphs is beneficial to achieve a number of advantages, including 1) significant speedup for graph algorithms, 2) graph storage space reduction, 3) faster network transmission, 4) improved data privacy, 5) more effective graph visualization, etc. All these benefits can be obtained from the summarized graph, if it is summarized accurately. The quality of the summary graph is mostly measured using the Reconstruction Error (RE). In the existing literature, RE is a very challenging task. Most of the approaches investigated so far ending up with high value of RE. Hence, the summarized graph does not express the original graph completely due to the high value of the RE. Therefore, in this work we have examined how can we summarize a big graph structure into a compact summary by reducing its RE and ensuring its usefulness. For this task, we have proposed a novel graph summarization approach, called g-Sum, to calculate the graph structure summaries while minimizing RE and compare to the existing work in the domain. The functionality of the g-Sum is decomposed into three different, but interlinked phases; (1)- graph dataset pre-processing; (2)- graph partitioning; and (3)- graph summarization. We have performed an extensive series of experiments on different real-world social graph dataset, including Ego-Facebook, Enron Email and Web-Stanford graph datasets. The computed results show the effectiveness of the g-Sum and also compared with the state-of-the-art graph summarization approaches, S2L and GraSS. [ABSTRACT FROM AUTHOR]

Emerging Graph Neural Networks (GNNs) have made significant progress in processing graph-structured data, yet existing GNN frameworks face scalability issues when training large-scale graph data using multiple GPUs. Frequent feature data transfers between CPUs and GPUs are a major bottleneck, and current caching schemes have not fully considered the characteristics of multi-GPU environments, leading to inefficient feature extraction. To address these challenges, we propose BGS, an auxiliary framework designed to accelerate GNN training from a data perspective in multi-GPU environments. Firstly, we introduce a novel training set partition algorithm, assigning independent training subsets to each GPU to enhance the spatial locality of node access, thus optimizing the efficiency of the feature caching strategy. Secondly, considering that GPUs can communicate at high speeds via NVLink connections, we designed a feature caching placement strategy suitable for multi-GPU environments. This strategy aims to improve the overall hit rate by setting reasonable redundant caches on each GPU. Evaluations on two representative GNN models, GCN and GraphSAGE, show that BGS significantly improves the hit rate of feature caching strategies in multi-GPU environments and substantially reduces the time overhead of data loading, achieving a performance improvement of 1.5 to 6.2 times compared to the baseline. [ABSTRACT FROM AUTHOR]

Graph is an important model to describe various networks, and its scale becomes larger and larger with the development of communication and information technology. The analysis of large-scale graphs requires distributed graph processing systems, and graph partition is the basis of these systems. The existing graph partitioning algorithms are almost proposed for homogeneous clusters, which don't consider the differences among computing nodes in heterogeneous clusters. This paper proposes GAP, a Genetic Algorithm based graph Partitioning algorithm to solve this problem. GAP aims to reduce the total processing time on a heterogeneous cluster by partitioning graphs according to the computing powers of computing nodes. GAP balanced partition the graph initially, and then utilizes genetic algorithm to transfer vertices to reduce cut edges. GAP can balance the processing time of computing nodes, and reduce the communication time among computing nodes. The experiments performed on a heterogeneous cluster demonstrate the outperformance of GAP than Hash.

As granular data about elections and voters become available, redistricting simulation methods are playing an increasingly important role when legislatures adopt redistricting plans and courts determine their legality. These simulation methods are designed to yield a representative sample of all redistricting plans that satisfy statutory guidelines and requirements such as contiguity, population parity, and compactness. A proposed redistricting plan can be considered gerrymandered if it constitutes an outlier relative to this sample according to partisan fairness metrics. Despite their growing use, an insufficient effort has been made to empirically validate the accuracy of the simulation methods. We apply a recently developed computational method that can efficiently enumerate all possible redistricting plans and yield an independent sample from this population. We show that this algorithm scales to a state with a couple of hundred geographical units. Finally, we empirically examine how existing simulation methods perform on realistic validation datasets.

Abstract scRNA-seq profiles each represent a highly partial sample of mRNA molecules from a unique cell that can never be resampled, and robust analysis must separate the sampling effect from biological variance. We describe a methodology for partitioning scRNA-seq datasets into metacells: disjoint and homogenous groups of profiles that could have been resampled from the same cell. Unlike clustering analysis, our algorithm specializes at obtaining granular as opposed to maximal groups. We show how to use metacells as building blocks for complex quantitative transcriptional maps while avoiding data smoothing. Our algorithms are implemented in the MetaCell R/C++ software package.

Dynamics always exist in complex systems. Graphs (complex networks) are a mathematical form for describing a complex system abstractly. Dynamics can be learned efficiently from the structure and dynamics state of a graph. Learning the dynamics in graphs plays an important role in predicting and controlling complex systems. Most of the methods for learning dynamics in graphs run slowly in large graphs. The complexity of the large graph’s structure and its nonlinear dynamics aggravate this problem. To overcome these difficulties, we propose a general framework with two novel methods in this paper, the Dynamics-METIS (D-METIS) and the Partitioned Graph Neural Dynamics Learner (PGNDL). The general framework combines D-METIS and PGNDL to perform tasks for large graphs. D-METIS is a new algorithm that can partition a large graph into multiple subgraphs. D-METIS innovatively considers the dynamic changes in the graph. PGNDL is a new parallel model that consists of ordinary differential equation systems and graph neural networks (GNNs). It can quickly learn the dynamics of subgraphs in parallel. In this framework, D-METIS provides PGNDL with partitioned subgraphs, and PGNDL can solve the tasks of interpolation and extrapolation prediction. We exhibit the universality and superiority of our framework on four kinds of graphs with three kinds of dynamics through an experiment.

The input to a PPNC instance is integers n and p , and a non-negative real weighting of the edges of the clique K n on the vertex set {1,..., n }. We are asked to find a set of p disjoint cycles spanning {1,..., n } and subject to this such that the sum of the weights of the edges is minimized. We provide an efficient approximation algorithm for the metric version of this problem which has an approximation ratio of 4 if p ≤ n/5 and an approximation ratio of 51 for larger p. For p > n/5, our algorithm uses a subroutine which approximately solves the Mod 3 T -join With Slack problem. The input to an instance of Mod k T -join with Slack consists of integers n and B , a non-negative weighting of the edges of the clique K n , and a label l(v) from {0,1,..., k - 1} on each vertex of K n. We are asked to find the minimum weight spanning forest F from amongst those satisfying ∑ T∈F ((∑ v∈V(T) l(v)) mod k) ≤ B. If k = 2 and B = 0 this is the well-studied T -join problem which can be solved exactly in polynomial time. [ABSTRACT FROM AUTHOR]