In this article, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost ...functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider new distributed gradient-based methods where each node maintains two estimates, namely an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the gradients is pushed to the neighbors, whereas the information about the decision variable is pulled from the neighbors, hence giving the name "push-pull gradient methods." The methods utilize two different graphs for the information exchange among agents and, as such, unify the algorithms with different types of distributed architecture, including decentralized (peer to peer), centralized (master-slave), and semicentralized (leader-follower) architectures. We show that the proposed algorithms and their many variants converge linearly for strongly convex and smooth objective functions over a network (possibly with unidirectional data links) in both synchronous and asynchronous random-gossip settings. In particular, under the random-gossip setting, "push-pull" is the first class of algorithms for distributed optimization over directed graphs. Moreover, we numerically evaluate our proposed algorithms in both scenarios, and show that they outperform other existing linearly convergent schemes, especially for ill-conditioned problems and networks that are not well balanced.
This Special Issue focuses on recent progress in a new area of mathematical physics and applied analysis, namely, on nonlinear partial differential equations on metric graphs and branched networks. ...Graphs represent a system of edges connected at one or more branching points (vertices). The connection rule determines the graph topology. When the edges can be assigned a length and the wave functions on the edges are defined in metric spaces, the graph is called a metric graph.
Evolution equations on metric graphs have attracted much attention as effective tools for the modeling of particle and wave dynamics in branched structures and networks. Since branched structures and networks appear in different areas of contemporary physics with many applications in electronics, biology, material science, and nanotechnology, the development of effective modeling tools is important for the many practical problems arising in these areas.
The list of important problems includes searches for standing waves, exploring of their properties (e.g., stability and asymptotic behavior), and scattering dynamics. This Special Issue is a representative sample of the works devoted to the solutions of these and other problems.
A graph G is called C 4 -free if it does not contain the cycle C 4 as an induced subgraph. Hubenko, Solymosi and the first author proved (answering a question of Erdős) a peculiar property of C 4 ...-free graphs: C 4 -free graphs with n vertices and average degree at least cn contain a complete subgraph (clique) of size at least c ′ n (with c ′ = 0.1 c 2 ). We prove here better bounds ( c 2 n 2 + c in general and ( c - 1 / 3 ) n when c ≤ 0.733 ) from the stronger assumption that the C 4 -free graphs have minimum degree at least cn. Our main result is a theorem for regular graphs, conjectured in the paper mentioned above: 2k-regular C 4 -free graphs on 4 k + 1 vertices contain a clique of size k + 1 . This is the best possible as shown by the kth power of the cycle C 4 k + 1 .
We prove that the maximum number of triangles in a
C
5‐free graph on n vertices is at most 122(1+o(1))n3∕2, improving an estimate of Alon and Shikhelman.
Graph signal processing on directed graphs is more challenging that on undirected graph, primarily because the graph matrices, e.g., adjacency or Laplacian, associated with the latter is ...non-symmetric. The eigenvalues that represent the spectral frequencies are therefore complex in general, and the design of spectral filters for complex frequencies presents more challenges. In this work we consider the design of two-channel filter banks for directed bipartite graphs. By decomposing any graph into a series of bipartite graphs, the basic two-channel system can be applied in cascade for arbitrary graphs. The graph filters are constructed using ladder structures. The design of the kernels in the ladder structures is achieved via a least-squares formulation. Analytical formulas are derived for the design of the kernel coefficients.
The aim of this paper is to investigate the Zagreb indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concepts.
This paper extends previous results on wavelet filterbanks for data defined on graphs from the case of orthogonal transforms to more general and flexible biorthogonal transforms. As in the recent ...work, the construction proceeds in two steps: first we design "one-dimensional" two-channel filterbanks on bipartite graphs, and then extend them to "multi-dimensional" separable two-channel filterbanks for arbitrary graphs via a bipartite subgraph decomposition. We specifically design wavelet filters based on the spectral decomposition of the graph, and state sufficient conditions for the filterbanks to be perfect reconstruction and orthogonal. While our previous designs, referred to as graph-QMF filterbanks, are perfect reconstruction and orthogonal, they are not exactly k-hop localized, i.e., the computation at each node is not localized to a small k-hop neighborhood around the node. In this paper, we relax the condition of orthogonality to design a biorthogonal pair of graph-wavelets that are k-hop localized with compact spectral spread and still satisfy the perfect reconstruction conditions. The design is analogous to the standard Cohen-Daubechies-Feauveau's (CDF) construction of factorizing a maximally-flat Daubechies half-band filter. Preliminary results demonstrate that the proposed filterbanks can be useful for both standard signal processing applications as well as for signals defined on arbitrary graphs.
We say an algorithm on n × n matrices with integer entries in −M,M (or n-node graphs with edge weights from −M,M) is truly subcubic if it runs in O(n3 − δ poly(log M)) time for some δ > 0. We define ...a notion of subcubic reducibility and show that many important problems on graphs and matrices solvable in O(n3) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do: *The all-pairs shortest paths problem on weighted digraphs (APSP). *Detecting if a weighted graph has a triangle of negative total edge weight. *Listing up to n2.99 negative triangles in an edge-weighted graph. *Finding a minimum weight cycle in a graph of non-negative edge weights. *The replacement paths problem on weighted digraphs. *Finding the second shortest simple path between two nodes in a weighted digraph. *Checking whether a given matrix defines a metric. *Verifying the correctness of a matrix product over the (min, +)-semiring. *Finding a maximum subarray in a given matrix. Therefore, if APSP cannot be solved in n3−ε time for any ε > 0, then many other problems also need essentially cubic time. In fact, we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR,AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two improved BMM algorithms: a derandomization of the combinatorial BMM algorithm of Bansal and Williams (FOCS’09), and an improved quantum algorithm for BMM.
PDF
