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_18: We continue our study of online prediction of the labelling of a graph. We show a fundamental limitation of Laplacian-based algorithms: if the graph has a large diameter then the number of mistakes made by such algorithms may be proportional to the square root of the number of vertices, even when tackling simple problems. We overcome this drawback by means of an efficient algorithm which achieves a logarithmic mistake bound. It is based on the notion of a spine, a path graph which provides a linear embedding of the original graph. In practice, graphs may exhibit cluster structure; thus in the last part, we present a modified algorithm which achieves the "best of both worlds": it performs well locally in the presence of cluster structure, and globally on large diameter graphs.
  @cite_9: We apply classic online learning techniques similar to the perceptron algorithm to the problem of learning a function defined on a graph. The benefit of our approach includes simple algorithms and performance guarantees that we naturally interpret in terms of structural properties of the graph, such as the algebraic connectivity or the diameter of the graph. We also discuss how these methods can be modified to allow active learning on a graph. We present preliminary experiments with encouraging results.
  @cite_21: In a traditional classification problem, we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem. An active line of research in this area is concerned with classification when one has information about pairwise relationships among the objects to be classified; this issue is one of the principal motivations for the framework of Markov random fields, and it arises in areas such as image processing, biometry, and document analysis. In its most basic form, this style of analysis seeks to find a classification that optimizes a combinatorial function consisting of assignment costs---based on the individual choice of label we make for each object---and separation costs---based on the pair of choices we make for two "related" objects.We formulate a general classification problem of this type, the metric labeling problem; we show that it contains as special cases a number of standard classification frameworks, including several arising from the theory of Markov random fields. From the perspective of combinatorial optimization, our problem can be viewed as a substantial generalization of the multiway cut problem, and equivalent to a type of uncapacitated quadratic assignment problem.We provide the first nontrivial polynomial-time approximation algorithms for a general family of classification problems of this type. Our main result is an O(log k log log k)-approximation algorithm for the metric labeling problem, with respect to an arbitrary metric on a set of k labels, and an arbitrary weighted graph of relationships on a set of objects. For the special case in which the labels are endowed with the uniform metric---all distances are the same---our methods provide a 2-approximation algorithm.
  @cite_19: We study the problem of online prediction of a noisy labeling of a graph with the perceptron. We address both label noise and concept noise. Graph learning is framed as an instance of prediction on a finite set. To treat label noise we show that the hinge loss bounds derived by Gentile [1] for online perceptron learning can be transformed to relative mistake bounds with an optimal leading constant when applied to prediction on a finite set. These bounds depend crucially on the norm of the learned concept. Often the norm of a concept can vary dramatically with only small perturbations in a labeling. We analyze a simple transformation that stabilizes the norm under perturbations. We derive an upper bound that depends only on natural properties of the graph – the graph diameter and the cut size of a partitioning of the graph – which are only indirectly dependent on the size of the graph. The impossibility of such bounds for the graph geodesic nearest neighbors algorithm will be demonstrated.
  @cite_2: We study the problem of predicting online the labeling of a graph. We consider a novel setting for this problem in which, in addition to observing vertices and labels on the graph, we also observe a sequence of just vertices on a second graph. A latent labeling of the second graph selects one of K labelings to be active on the first graph. We propose a polynomial time algorithm for online prediction in this setting and derive a mistake bound for the algorithm. The bound is controlled by the geometric cut of the observed and latent labelings, as well as the resistance diameters of the graphs. When specialized to multitask prediction and online switching problems the bound gives new and sharper results under certain conditions.
  @cite_12: We study the problem of predicting the labelling of a graph. The graph is given and a trial sequence of (vertex,label) pairs is then incrementally revealed to the learner. On each trial a vertex is queried and the learner predicts a boolean label. The true label is then returned. The learner’s goal is to minimise mistaken predictions. We propose minimum p-seminorm interpolation to solve this problem. To this end we give a p-seminorm on the space of graph labellings. Thus on every trial we predict using the labelling which minimises the p-seminorm and is also consistent with the revealed (vertex, label) pairs. When p = 2 this is the harmonic energy minimisation procedure of [22], also called (Laplacian) interpolated regularisation in [1]. In the limit as p → 1 this is equivalent to predicting with a label-consistent mincut. We give mistake bounds relative to a label-consistent mincut and a resistive cover of the graph. We say an edge is cut with respect to a labelling if the connected vertices have disagreeing labels. We find that minimising the p-seminorm with p = 1 + where → 0 as the graph diameter D → ∞ gives a bound of O(Φ logD) versus a bound of O(ΦD) when p = 2 where Φ is the number of cut edges.
summary: In recent years, a number of algorithms have been proposed for different learning problems over nodes of an static graph. @cite_21 studied the classification problem for nodes of an static graph and showed the connection of their general formulation to Markov random fields. With @math the number of possible node labels, they also presented an @math -approximation algorithm for the classification problem, which is run in polynomial time. @cite_19 studied the problem of online label prediction of a graph with the perceptron. The key difference between online and dynamic settings is that online setting is used in the cases where it is computationally infeasible to solve the learning problem over the entire dataset. However, in dynamic setting the learning problem can be solved over the entite dataset and the challenge is to efficiently update the solution when the dataset changes. Some other examples of online learning for graphs include @cite_9 , @cite_18 , @cite_12 and @cite_2 .