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]

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]

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]

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]

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 network of energy pipelines is extremely important for the proper functioning of a modern society. Even though measurement instruments and sensors are currently widely used to monitor the network's operational status in real time, it is expensive to deploy these extra devices for a large city-scale network. Numerical simulation of fluid networks offers a rather easy and effective technique to track the work performance of pipelines. Because of the computational intensiveness of the pipeline network, it is most suitable to deploy such a massive simulation program on a supercomputer with a parallel technique. The performance of this kind of parallel simulation may undoubtedly be enhanced if the pipeline network is reasonably divided into several subnetworks in which the fluid flows are resolved independently. In this paper, we concentrate on how to achieve a computationally balanced subnetwork partition scheme and propose an acceleration method for energy pipeline network simulations based on a graph partition algorithm. In our approach, each node of the network takes part in the decision of dividing the entire network by learning the weight of its neighbors. Moreover, we utilize graph-tree transformations to merge locally related components as much as possible, and together with subgraph rebalancing, the pipeline network division quality is improved considerably. Numerical simulations show that our approach is much better than others for the degree of balance, and the cut edge ratio is also lower than others when it is compared with the random, k -means, and METIS methods. • Proposal of a novel graph partitioning algorithm based on node self-learning. • A periphery-to-center graph reduction method minimizing the number of cut edges. • A technique of weighted quadratic relaxation to adjust the part balance in k -GP. • Discussion of the impact of k -GP algorithms on EPN simulation performance. [ABSTRACT FROM AUTHOR]

The rapid growth of data and parameter sizes of machine learning models makes it necessary to improve the efficiency of distributed training. It is observed that the communication cost usually is the bottleneck of distributed training systems. In this paper, we focus on the parameter server framework which is a widely deployed distributed learning framework. The frequent parameter pull, push, and synchronization among multiple machines leads to a huge communication volume. We aim to reduce the communication cost for the parameter server framework. Compressing the training model and optimizing the data and parameter allocation are two existing approaches to reducing communication costs. We jointly consider these two approaches and propose to optimize the data and parameter allocation after compression. Different from previous allocation schemes, the data sparsity property may no longer hold after compression. It brings additional opportunities and challenges for the allocation problem. We also consider the allocation problem for both linear and deep neural network (DNN) models. Fixed and dynamic partition algorithms are proposed accordingly. Experiments on real-world datasets show that our joint compression and partition scheme can efficiently reduce communication overhead for linear and DNN models. • An optimization problem that minimizes the bottleneck traffic volume for parameter server frameworks is formulated. • Model compression and partition methods are jointly considered to reduce the communication cost during the training process. • A dynamic parameter partition scheme is proposed, which adaptively updates the partition plan with access pattern changes. • Evaluation results show the proposed scheme can significantly reduce network traffics and accelerate the training process. [ABSTRACT FROM AUTHOR]