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]

Graph similarity computation aims to predict a similarity score between one pair of graphs to facilitate downstream applications, such as finding the most similar chemical compounds similar to a query compound or Fewshot 3D Action Recognition. Recently, some graph similarity computation models based on neural networks have been proposed, which are either based on graph-level interaction or node-level comparison. However, when the number of nodes in the graph increases, it will inevitably bring about reduced representation ability or high computation cost. Motivated by this observation, we propose a graph partitioning and graph neural network-based model, called PSimGNN, to effectively resolve this issue. Specifically, each of the input graphs is partitioned into a set of subgraphs to extract the local structural features directly. Next, a novel graph neural network with an attention mechanism is designed to map each subgraph into an embedding vector. Some of these subgraph pairs are automatically selected for node-level comparison to supplement the subgraph-level embedding with fine-grained information. Finally, coarse-grained interaction information among subgraphs and fine-grained comparison information among nodes in different subgraphs are integrated to predict the final similarity score. Experimental results on graph datasets with different graph sizes demonstrate that PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks using approximate Graph Edit Distance (GED) as the graph similarity metric. [ABSTRACT FROM AUTHOR]

This paper investigates the situation awareness issue of power system with massive measured data. To address this issue, first, a graph-theory-based network partitioning algorithm is proposed to realize decentralized detection in a faster response speed, while using power flow characteristics highlights the independency of different groups. Further, a hierarchical event detection method is proposed to judge voltage change and locate event position according to spectral distribution change of established multidimensional matrix. With the proposed method, the system situation can be assessed and the knowledge of the system model is not required. In addition, the accurate result of weak event happened in system could also be obtained. The simulation results are presented to illustrate the effectiveness of the proposed detection method. [ABSTRACT FROM AUTHOR]

Social ties are formed as a result of interactions and individual preferences of the people in a social network. There are two opposite types which are interpreted as friendship vs. enmity or trust vs. distrust between people. The aforementioned social network structure can be represented by a signed graph, where people are the graph’s vertices and their interactions are graph’s edges. The edges can be positive and negative signs. To determine trustworthiness, this paper considers the problem of a signed graph partitioning with minimizing the sum of the negative edge's weight and balanced size of its clusters. An efficient algorithm to solve such a problem is proposed. The experimental results show that the proposed algorithm outperforms in terms of the execution times and the accuracy within the given bounds.

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 new results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we show that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence. [ABSTRACT FROM AUTHOR]

Proposal-free instance segmentation methods mainly generate instance-agnostic semantic segmentation labels and instance-aware features to group pixels into different object instances. However, previous methods mostly employ separate modules for these two sub-tasks and require multiple passes for inference. In addition to the lack of efficiency, previous methods also failed to perform as well as proposal-based approaches. To this end, this work proposes a single-shot proposal-free instance segmentation method that requires only one single pass for prediction. Our method is based on learning an affinity pyramid, which computes the probability that two pixels belong to the same instance in a hierarchical manner. Moreover, incorporating with the learned affinity pyramid, a novel cascaded graph partition (CGP) module is presented to fuse the two predictions and segment instances efficiently. As an additional contribution, we conduct an experiment to demonstrate the benefits of proposal-free methods in capturing detailed structures from finely annotated training examples. Our approach is evaluated on the Cityscapes and COCO datasets and achieves state-of-the-art performance. [ABSTRACT FROM AUTHOR]

When training graph embedding via neural network, high dimension feature vector and large scale graph cause data transferring from memory to GPU to be a bottleneck. Aimed to solve this problem, this paper proposed graph partition based graph representation learning. This method splitted graph nodes into blocks according to their degree. It stored several node feature matrices in buffer pool on GPU. Every epoch, it trained representation during several blocks which fitted into buffer pool to reduce the data transferred from memory to GPU. Based on block split, this method used blocked based sampling algorithm, cached block feature matrix in GPU buffer pool to reduce memory read and built hierarchical negative sampling table, which could sample nodes in const time complex. Compared to related work on several real world datasets, this method achieves competitive accuracy at downstream machine learning task and 2 ~ 7 times speedup on training process. The experiments show that graph representation learning based on partition can train model efficiently and generate accurate embedding vectors. In future work, it is worth to prove the deviation between partition based method and original method in theory. [ABSTRACT FROM AUTHOR]

Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly little theory about performance guarantees for spectral clustering. This issue is partly due to the fact that spectral clustering typically involves two steps which complicated its theoretical analysis: First, the eigenvectors of the associated graph Laplacian are used to embed the dataset, and second, k-means clustering algorithm is applied to the embedded dataset to get the labels. This paper is devoted to the theoretical foundations of spectral clustering and graph cuts. We consider a convex relaxation of graph cuts, namely ratio cuts and normalized cuts, that makes the usual two-step approach of spectral clustering obsolete and at the same time gives rise to a rigorous theoretical analysis of graph cuts and spectral clustering. We derive deterministic bounds for successful spectral clustering via a spectral proximity condition that naturally depends on the algebraic connectivity of each cluster and the inter-cluster connectivity. Moreover, we demonstrate by means of some popular examples that our bounds can achieve near optimality. Our findings are also fundamental to the theoretical understanding of kernel k-means. Numerical simulations confirm and complement our analysis. [ABSTRACT FROM AUTHOR]

A new direct reanalysis algorithm for local high-rank structural modifications, based on triangular factorization, has recently been developed. In this work, an improvement is proposed for further reduction of the workload so that the algorithm becomes more efficient and also suitable for low-rank modifications. Compared to the original algorithm, firstly, an alternative formula for updating the triangular factors is derived to avoid repetitive calculations for certain low-rank cases. Secondly, to maximize the efficiency, a combined algorithm is proposed that estimates the workloads of the original and alternative algorithms for each row individually before numerical calculations and selects the one with smaller workload. Numerical experiments show that compared with full factorization, the combined algorithm is significantly more efficient and expected to save up to 75% of execution time in our numerical examples. The new method can be easily implemented and applied to engineering problems, especially to local and step-by-step modification of structures. [ABSTRACT FROM AUTHOR]

Vision tasks, such as segmentation, grouping, recognition, and learning, have a "what-goes-with-what" component. It can be formulated as partitioning an adjacent graph into a number of subgraphs, each being a "coherent" visual pattern in the sense of optimizing a Bayesian posterior probability or minimizing an energy functional. In this paper, we generalize Swendsen-Wang (1987)- a well celebrated algorithm in statistical mechanics-for general graph partition. Our objective is to design reversible Markov chain moves in the space of all possible partitions to search for global optimum in the Bayesian framework. We start with an adjacency graph whose vertices are image elements, such as pixels, edgels, small regions, or image bases. For each edge in the graph, we compute a local discriminative probability or probability ratio for how likely the two vertices belong to an underlying visual pattern. These edge probabilities are computed in a bottom-up fasion through previous supervised learning techniques. By turning on/off the edges independently according to these edge probabilities, we obtain a partition of the graph into a number of connected subgraphs. This procedure is in fact a sample from the space of graph partitions. We use it as a proposal (hypothesis) in a probabilistic manner. Thus the algorithm picks up a connected subgraph and flips the label of all its vertices in a single reversible Markov chain jump. In comparison to the classic Gibbs sampler which flips a single vertex at a time, the proposed method achieves: 1) Fast mixing rate it can flip a large subgraph at a time and the acceptance probability can be made to be one. 2) Short burn-in period - it can walk at low temperature and does not need a long sumulated annealing procedure. Thus it is shown to be nearly 100 times faster than the Gibbs sampler and thus produce results in about 1 minute on a PC for image segmentation and curve grouping experiments. The algorithm is tested in image segmentation and curve grouping task, and it is general for many problems in vision and beyond.

Personal privacy is facing severe threats as social networks are sharing user data with advertisers, application developers, and data mining researchers. Although these data are anonymized by removing personal information, such as user identity, nickname, or address information, personal information still could not be protected effectively. In order to arouse the attention of people from academia and industry for privacy protection, we propose a random forest method to de-anonymize social networks. First, we convert the social network de-anonymization problem into a binary classification problem between node pairs. In order to partition large sparse social networks, we use the spectral partition method to partition large graphs into a number of small subgraphs. Then, we use the features of the network structure to train the random forest classifier. As a result, candidate node pairs from anonymous network and auxiliary network can be classified as matched pair by the random forest classifier. Furthermore, we improve the efficiency of our solution through parallelizing proposed method. The experiments conducted on the real data sets show that our solution's area under the curve is 19% higher than baseline methods on average. Besides that we test the robustness of the proposed algorithm by adding some noisy data, and the result demonstrates that our solution has good robustness.

We prove that every strongly 10 50 t -connected tournament contains all possible 1-factors with at most t components and this is best possible up to constant. In addition, we can ensure that each cycle in the 1-factor contains a prescribed vertex. This answers a question by Kühn, Osthus, and Townsend. Indeed, we prove more results on partitioning tournaments. We prove that a strongly Ω (k 4 t q) -connected tournament admits a vertex partition into t strongly k -connected tournaments with prescribed sizes such that each tournament contains q prescribed vertices, provided that the prescribed sizes are Ω (n). This result improves the earlier result of Kühn, Osthus, and Townsend. We also prove that for a strongly Ω (t) -connected n -vertex tournament T and given 2 t distinct vertices x 1 , ... , x t , y 1 , ... , y t of T , we can find t vertex disjoint paths P 1 , ... , P t such that each path P i connecting x i and y i has the prescribed length, provided that the prescribed lengths are Ω (n). For both results, the condition of connectivity being linear in t is best possible, and the condition of prescribed sizes being Ω (n) is also best possible. [ABSTRACT FROM AUTHOR]

The name disambiguation task is designed to solve the name ambiguity problem of documents of multiple persons who have the same name with one another. The task aims to partition all the publications belonging to multiple person with the same name and realize that each decomposed partition is composed of publications of a unique person. Many works on name disambiguation task have a common feature that clustering method is usually used in the last step. The paper presents a complementary study to these works from another point of view. Based on the idea that documents with strong association relationships are likely to belong to the same author, this paper proposes a method of discovering meta clusters by graph partition with a heuristic rule to improve these clustering-based works. Specially, different from these works, this work uses clustering ensemble method instead of clustering method in the last step. Experimental results on a real-life dataset show that the improved method has satisfactory performance compared with the clustering-based baseline method. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

Differential privacy protection model provides strict and quantitative risk representation for privacy disclosure, which greatly ensures the availability of data. However, most existing methods do not consider the semantic context, so they are vulnerable to attacks based on semantic information. Therefore, dynamic social privacy protection based on graph pattern partitioning is designed to satisfy differential privacy protection. Firstly, the structure of social network is represented as a graph model, and the original graph is classified into several sub-graphs according to the characteristics of nodes. Then, the dense area of each sub-graph is divided by quad-tree method, and the noise of differential privacy protection is added to the leaf nodes of the tree, and the graph publishing is generated by sub-graph reconstruction. Finally, the feasibility and practicability of the model are verified by statistical analysis, such as degree distribution, shortest path, and clustering coefficient. The simulation results show the validity and applicability of the privacy protection method proposed in this paper. [ABSTRACT FROM AUTHOR]

We are interested in the solution of the maximum k -balanced subgraph problem. Let G = (V , E , s) be a signed graph and k a positive scalar. A signed graph is k -balanced if V can be partitioned into at most k sets in such a way that positive edges are found only within the sets and negative edges go between sets. The maximum k -balanced subgraph problem is the problem of finding a subgraph of G that is k -balanced and maximum according to the number of vertices. This problem has applications in clustering problems appearing in collaborative v s conflicting environments. The particular case k = 2 yields the problem of finding a maximum balanced subgraph in a signed graph and its exact solution has been addressed before in the literature. In this paper, we provide a representatives formulation for the general problem and present a partial description of the associated polytope, including the introduction of strengthening families of valid inequalities. A branch-and-cut algorithm is described for finding an optimal solution to the problem. An ILS metaheuristic is implemented for providing primal bounds for this exact method and a branching rule strategy is proposed for the representatives formulation. Computational experiments, carried out over a set of random instances and on a set of instances from an application, show the effectiveness of the valid inequalities and strategies adopted in this work. [ABSTRACT FROM AUTHOR]