Most of real-world graphs are dynamic , i.e., they change over time. However, while the regression problem has been studied for static graphs, it has not been investigated for dynamic graphs, yet. In the current paper, first we present the notion of update-efficient matrix embedding that defines the conditions sufficient for a matrix embedding to be used for the dynamic graph regression problem, efficiently. We also show that some of the standard matrix embeddings, e.g., the (weighted) adjacency matrix, satisfy these conditions. Then, we prove that given an @math update-efficient matrix embedding, after an update operation in the graph, the optimal solution of the graph regression problem for the revised graph can be computed in @math time. In particular, using the (weighted) adjacency matrix as the matrix embedding of @math , it takes @math time to update the optimal solution, where @math is the number of nodes of the revised graph. To the best of our knowledge, this is the first result on updating the solution of the graph regression problem, in a time considerably less than the time of computing the solution from the scratch. Finally, we study a generalization of the dynamic graph regression problem and show that it can be solved in @math space.
More recent algorithms are mostly methods for learning embeddings (representations) for nodes or subgraphs of a graph @cite_7 , @cite_14 , @cite_1 , even though learning embeddings for a graph dates back to several decades ago. For example, @cite_10 presented vector embeddings for nodes of a graph such that the inner product of the vector embeddings of any two nodes @math and @math is negative iff @math and @math are connected by an edge; and it is @math otherwise. They also studied the least embedding size @math , necessary for satisfying such a property.
@cite_10 @cite_14 @cite_1 @cite_7
2095567216 2406128552 2962756421
We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. We show that every weighted connected graph @math contains as a subgraph a spanning tree into which the edges of @math can be embedded with average stretch @math . Moreover, we show that this tree can be constructed in time @math in general, and in time @math if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique. Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from @math to @math , and to @math when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees. We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any @math , given cost and demand graphs with edge weights @math respectively, we can find a set @math with @math at most @math times the optimal non-uniform sparsest cut value, in time @math provided @math . Here @math is the @math 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; @math (resp. @math ) is the weight of edges crossing the @math cut in cost (resp. demand) graph and @math is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the @math 'th smallest eigenvalue of the normalized Laplacian playing the role of @math in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting @math -embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut. We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and @math -out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node @math in the solution is at most @math , where @math is the degree upper bound on @math . For undirected graphs and element-connectivity requirements with maximum connectivity requirement @math , our algorithm computes a solution that is a @math -approximation on the cost, and the degree of each node @math in the solution is at most @math . These ratios improve the previous @math -approximation on the cost and @math -approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k... We study undirected networks with edge costs that satisfy the triangle inequality. Let @math denote the number of nodes. We present an @math -approximation algorithm for a generalization of the metric-cost subset @math -node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each @math , there exists a @math -node connected graph whose cost is within a factor of @math of the cost of any simple @math -edge connected graph. Based on our @math -approximation algorithm, we present an @math -approximation algorithm for the metric-cost node-connectivity survivable network design problem, where @math denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704-720] recently proved, assuming NP @math DTIME( @math ), a hardness-of-approximation lower bound of @math for the subset @math -node-connectivity problem, where @math denotes a small positive number. A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with @math , a straight-line embedding on a grid of size @math can be computed deterministically in @math time with @math processors. If randomization is used, the complexity is improved to @math expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict. In the subgraph-freeness problem, we are given a constant-size graph @math , and wish to determine whether the network contains @math as a subgraph or not. The relaxation of the problem only requires us to distinguish graphs that are @math -free from graphs that are @math -far from @math -free, meaning an @math -fraction of their edges must be removed to obtain an @math -free graph. Recently, Censor-Hillel et. al. and showed that in the property-testing regime it is possible to test @math -freeness for any graph @math of size 4 in constant time, @math rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs @math of size 4 cannot test @math -cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that @math -cycle-freeness, and indeed @math -freeness for many other graphs @math comprising more than 4 vertices, can be tested in constant time. We show that @math -freeness can be tested in @math rounds for any cycle @math , improving on the running time of @math of the previous algorithms for triangle-freeness and @math -freeness. In the special case of triangles, we show that triangle-freeness can be solved in @math rounds independently of @math , when @math is not too small with respect to the number of nodes and edges. We also show that @math -freeness for any constant-size tree @math can be tested in @math rounds, even without the property-testing relaxation. Building on these results, we define a general class of graphs for which we can test subgraph-freeness in @math rounds. This class includes all graphs over 5 vertices except the 5-clique, @math . For cliques @math over @math nodes, we show that @math -freeness can be tested in @math rounds, where @math is the number of edges. Indyk and Sidiropoulos (2007) proved that any orientable graph of genus @math can be probabilistically embedded into a graph of genus @math with constant distortion. Viewing a graph of genus @math as embedded on the surface of a sphere with @math handles attached, Indyk and Sidiropoulos' method gives an embedding into a distribution over planar graphs with distortion @math , by iteratively removing the handles. By removing all @math handles at once, we present a probabilistic embedding with distortion @math for both orientable and non-orientable graphs. Our result is obtained by showing that the nimum-cut graph of Erickson and Har Peled (2004) has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma of Lee and Sidiropoulos (2009). In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. For a sufficiently connected graph with @math nodes, it is shown that, using @math path measurements, we are able to recover any @math -sparse link vector (with no more than @math nonzero elements), even though the measurements have to follow the graph path constraints. We further show that the computationally efficient @math minimization can provide theoretical guarantees for inferring such @math -sparse vectors with @math path measurements from the graph. An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of an (undirected or directed) simple graph G=(V,E). There are four versions of the problem, and the approximation guarantees are as follows: minimum-size k-node connected spanning subgraph of an undirected graph 1 + [1 k], minimum-size k-node connected spanning subgraph of a directed graph 1 + [1 k], minimum-size k-edge connected spanning subgraph of an undirected graph 1+[2 (k+1)], minimum-size k-edge connected spanning subgraph of a directed graph 1 + [4 k ]. The heuristic is based on a subroutine for the degree-constrained subgraph (b-matching) problem. It is simple and deterministic and runs in time O(k|E|2). The following result on simple undirected graphs is used in the analysis: The number of edges required for augmenting a graph of minimum degree k to be k-edge connected is at most k,|V| (k+1). For undirected graphs and k=2, a (deterministic) parallel NC version of the heuristic finds a 2-node connected (or 2-edge connected) spanning subgraph whose size is within a factor of ( @math ) of minimum, where @math is a constant. This paper addresses the basic question of how well a tree can approximate distances of a metric space or a graph. Given a graph, the problem of constructing a spanning tree in a graph which strongly preserves distances in the graph is a fundamental problem in network design. We present scaling distortion embeddings where the distortion scales as a function of @math , with the guarantee that for each @math simultaneously, the distortion of a fraction @math of all pairs is bounded accordingly. Quantitatively, we prove that any finite metric space embeds into an ultrametric with scaling distortion @math . For the graph setting, we prove that any weighted graph contains a spanning tree with scaling distortion @math . These bounds are tight even for embedding into arbitrary trees. These results imply that the average distortion of the embedding is constant and that the @math distortion is @math . For probabilistic embedding into spanning trees we prove a scaling distortion of @math , which implies constant @math -distortion for every fixed @math . We propose a new method for embedding graphs while preserving directed edge information. Learning such continuous-space vector representations (or embeddings) of nodes in a graph is an important first step for using network information (from social networks, user-item graphs, knowledge bases, etc.) in many machine learning tasks. Unlike previous work, we (1) explicitly model an edge as a function of node embeddings, and we (2) propose a novel objective, the graph likelihood, which contrasts information from sampled random walks with non-existent edges. Individually, both of these contributions improve the learned representations, especially when there are memory constraints on the total size of the embeddings. When combined, our contributions enable us to significantly improve the state-of-the-art by learning more concise representations that better preserve the graph structure. We evaluate our method on a variety of link-prediction task including social networks, collaboration networks, and protein interactions, showing that our proposed method learn representations with error reductions of up to 76 and 55 , on directed and undirected graphs. In addition, we show that the representations learned by our method are quite space efficient, producing embeddings which have higher structure-preserving accuracy but are 10 times smaller. In the standard CONGEST model for distributed network computing, it is known that "global" tasks such as minimum spanning tree, diameter, and all-pairs shortest paths, consume large bandwidth, for their running-time is @math rounds in @math -node networks with constant diameter. Surprisingly, "local" tasks such as detecting the presence of a 4-cycle as a subgraph also requires @math rounds, even using randomized algorithms, and the best known upper bound for detecting the presence of a 3-cycle is @math rounds. The objective of this paper is to better understand the landscape of such subgraph detection tasks. We show that, in contrast to , which are hard to detect in the CONGEST model, there exists a deterministic algorithm for detecting the presence of a subgraph isomorphic to @math running in a number of rounds, for every tree @math . Our algorithm provides a distributed implementation of a combinatorial technique due to Erd o for sparsening the set of partial solutions kept by the nodes at each round. Our result has important consequences to , i.e., to randomized algorithms whose aim is to distinguish between graphs satisfying a property, and graphs far from satisfying that property. In particular, we get that, for every graph pattern @math composed of an edge and a tree connected in an arbitrary manner, there exists a distributed testing algorithm for @math -freeness, performing in a constant number of rounds. Although the class of graph patterns @math formed by a tree and an edge connected arbitrarily may look artificial, all previous results of the literature concerning testing @math -freeness for classical patterns such as cycles and cliques can be viewed as direct consequences of our result, while our algorithm enables testing more complex patterns. Given a planar graph G together with a planar representation P, a region preserving grid embedding of G is a planar embedding of G in the rectilinear grid that has planar representation isomorphic to P. In this paper, an algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges. This algorithm makes use of network flow techniques, and runs in time @math , where n is the number of vertices of the graph. Constrained versions of the problem are also considered, and most results are extended to k-gonal graphs, i.e., graphs whose edges are sequences of segments with slope multiple of @math degrees. Applications of the above results can be found in several areas: VLSI circuit layout, architectural design, communication by light or microwave, transportation problems, and automatic layout of graphlike diagrams. Let @math be a @math -regular triangle-free graph with @math edges. We present an algorithm which finds a cut in @math with at least @math edges in expectation, improving upon Shearer's classic result. In particular, this implies that any @math -regular triangle-free graph has a cut of at least this size, and thus, we obtain a new lower bound for the maximum number of edges in a bipartite subgraph of @math . Our algorithm is simpler than Shearer's classic algorithm and it can be interpreted as a very efficient randomised distributed (local) algorithm : each node needs to produce only one random bit, and the algorithm runs in one round. The randomised algorithm itself was discovered using computational techniques . We show that for any fixed @math , there exists a weighted neighbourhood graph @math such that there is a one-to-one correspondence between heavy cuts of @math and randomised local algorithms that find large cuts in any @math -regular input graph. This turns out to be a useful tool for analysing the existence of cuts in @math -regular graphs: we can compute the optimal cut of @math to attain a lower bound on the maximum cut size of any @math -regular triangle-free graph. Node embedding techniques have gained prominence since they produce continuous and low-dimensional features, which are effective for various tasks. Most existing approaches learn node embeddings by exploring the structure of networks and are mainly focused on static non-attributed graphs. However, many real-world applications, such as stock markets and public review websites, involve bipartite graphs with dynamic and attributed edges, called attributed interaction graphs. Different from conventional graph data, attributed interaction graphs involve two kinds of entities (e.g. investors stocks and users businesses) and edges of temporal interactions with attributes (e.g. transactions and reviews). In this paper, we study the problem of node embedding in attributed interaction graphs. Learning embeddings in interaction graphs is highly challenging due to the dynamics and heterogeneous attributes of edges. Different from conventional static graphs, in attributed interaction graphs, each edge can have totally different meanings when the interaction is at different times or associated with different attributes. We propose a deep node embedding method called IGE (Interaction Graph Embedding). IGE is composed of three neural networks: an encoding network is proposed to transform attributes into a fixed-length vector to deal with the heterogeneity of attributes; then encoded attribute vectors interact with nodes multiplicatively in two coupled prediction networks that investigate the temporal dependency by treating incident edges of a node as the analogy of a sentence in word embedding methods. The encoding network can be specifically designed for different datasets as long as it is differentiable, in which case it can be trained together with prediction networks by back-propagation. We evaluate our proposed method and various comparing methods on four real-world datasets. The experimental results prove the effectiveness of the learned embeddings by IGE on both node clustering and classification tasks. Many resource allocation problems in the cloud can be described as a basic Virtual Network Embedding Problem (VNEP): the problem of finding a mapping of a request graph (describing a workload) onto a substrate graph (describing the physical infrastructure). Applications range from mapping testbeds (from where the problem originated), over the embedding of batch-processing workloads (virtual clusters) to the embedding of service function chains. The different applications come with their own specific requirements and constraints, including node mapping constraints, routing policies, and latency constraints. While the VNEP has been studied intensively over the last years, complexity results are only known for specific models and we lack a comprehensive understanding of its hardness.This paper charts the complexity landscape of the VNEP by providing a systematic analysis of the hardness of a wide range of VNEP variants, using a unifying and rigorous proof framework. In particular, we show that the problem of finding a feasible embedding is @math -complete in general, and, hence, the VNEP cannot be approximated under any objective, unless @math holds. Importantly, we derive @math -completeness results also for finding approximate embeddings, which may violate, e.g., capacity constraints by certain factors. Lastly, we prove that our results still pertain when restricting the request graphs to planar or degree-bounded graphs. In this paper, we study the problem of subgraph matching that extracts all subgraph isomorphic embeddings of a query graph q in a large data graph G. The existing algorithms for subgraph matching follow Ullmann's backtracking approach; that is, iteratively map query vertices to data vertices by following a matching order of query vertices. It has been shown that the matching order of query vertices is a very important aspect to the efficiency of a subgraph matching algorithm. Recently, many advanced techniques, such as enforcing connectivity and merging similar vertices in query or data graphs, have been proposed to provide an effective matching order with the aim to reduce unpromising intermediate results especially the ones caused by redundant Cartesian products. In this paper, for the first time we address the issue of unpromising results by Cartesian products from "dissimilar" vertices. We propose a new framework by postponing the Cartesian products based on the structure of a query to minimize the redundant Cartesian products. Our second contribution is proposing a new path-based auxiliary data structure, with the size O(|E(G)| x |V(q)|), to generate a matching order and conduct subgraph matching, which significantly reduces the exponential size O(|V(G)||V(q)|-1) of the existing path-based auxiliary data structure, where V (G) and E (G) are the vertex and edge sets of a data graph G, respectively, and V (q) is the vertex set of a query @math . Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms by up to @math orders of magnitude. A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) Given a set X and subsets @math of @math , satisfying @math , find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by @math has a connected component containing @math .Two other problems related to this one are the following ones. (2) Given a set X and subsets @math such that @math , find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph @math induced by @math in G is connected. (3) Given a set X and subsets @math such that @math , find a graph G with vertex set X, find a graph G with vertex set X and the minimum number of edges such that for any subset I of @math , the subgraph induced by @math is co... For any integers @math and @math , we show the existence of a set of @math vectors @math such that any embedding @math satisfying @math must have @math This lower bound matches the upper bound given by the Johnson-Lindenstrauss lemma [JL84]. Furthermore, our lower bound holds for nearly the full range of @math of interest, since there is always an isometric embedding into dimension @math (either the identity map, or projection onto @math ). Previously such a lower bound was only known to hold against linear maps @math , and not for such a wide range of parameters @math [LN16]. The best previously known lower bound for general @math was @math [Wel74, Lev83, Alo03], which is suboptimal for any @math .