text: 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.
  @cite_10: Abstract Let G be a simple graph with vertices 1, 2, …, n . We consider representations of G by nonzero vectors x 1 ,x 2 ,…,x n ϵ R d such that for i ≠ j the inner product x i · x j is negative or zero according as vertex i is adjacent to or not adjacent to vertex j . The least dimension d necessary for such representations is studied as a function of G and of various restrictions placed upon the coordinates of the vectors and the values of the inner products. In particular, for some d such that d n 2 , there always exists a representation in which all coordinates are from −1,1 and all negative inner products have the same value. Various types of vector representations of graphs are related to Hadamard matrices, families of sets with prescribed intersections, and other combinatorial problems.
  @cite_14: 
  @cite_1: Numerous important problems can be framed as learning from graph data. We propose a framework for learning convolutional neural networks for arbitrary graphs. These graphs may be undirected, directed, and with both discrete and continuous node and edge attributes. Analogous to image-based convolutional networks that operate on locally connected regions of the input, we present a general approach to extracting locally connected regions from graphs. Using established benchmark data sets, we demonstrate that the learned feature representations are competitive with state of the art graph kernels and that their computation is highly efficient.
  @cite_7: Prediction tasks over nodes and edges in networks require careful effort in engineering features used by learning algorithms. Recent research in the broader field of representation learning has led to significant progress in automating prediction by learning the features themselves. However, present feature learning approaches are not expressive enough to capture the diversity of connectivity patterns observed in networks. Here we propose node2vec, an algorithmic framework for learning continuous feature representations for nodes in networks. In node2vec, we learn a mapping of nodes to a low-dimensional space of features that maximizes the likelihood of preserving network neighborhoods of nodes. We define a flexible notion of a node's network neighborhood and design a biased random walk procedure, which efficiently explores diverse neighborhoods. Our algorithm generalizes prior work which is based on rigid notions of network neighborhoods, and we argue that the added flexibility in exploring neighborhoods is the key to learning richer representations. We demonstrate the efficacy of node2vec over existing state-of-the-art techniques on multi-label classification and link prediction in several real-world networks from diverse domains. Taken together, our work represents a new way for efficiently learning state-of-the-art task-independent representations in complex networks.
summary: 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.