The most persistent soft-clique in a set of sampled graphs

When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques. We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations. Copyright 2012 by the author(s)/owner(s).

Distributed flow algorithms for scalable similarity visualization

We describe simple yet scalable and distributed algorithms for solving the maximum flow problem and its minimum cost flow variant, motivated by problems of interest in objects similarity visualization. We formulate the fundamental problem as a convex-concave saddle point problem. We then show that this problem can be efficiently solved by a first order method or by exploiting faster quasi-Newton steps. Our proposed approach costs at most O(|ε|) per iteration for a graph with |ε| edges. Further, the number of required iterations can be shown to be independent of number of edges for the first order approximation method. We present experimental results in two applications: mosaic generation and color similarity based image layouting. © 2010 IEEE.

Decentralised minimum-time consensus

We consider the discrete-time dynamics of a network of agents that exchange information according to a nearest-neighbour protocol under which all agents are guaranteed to reach consensus asymptotically. We present a fully decentralised algorithm that allows any agent to compute the final consensus value of the whole network in finite time using the minimum number of successive values of its own state history. We show that the minimum number of steps is related to a Jordan block decomposition of the network dynamics, and present an algorithm to compute the final consensus value in the minimum number of steps by checking a rank condition of a Hankel matrix of local observations. Furthermore, we prove that the minimum number of steps is related to graph theoretical notions that can be directly computed from the Laplacian matrix of the graph and from the minimum external equitable partition. © 2013 Elsevier Ltd. All rights reserved.

Low-rank optimization on the cone of positive semidefinite matrices

We propose an algorithm for solving optimization problems defined on a subset of the cone of symmetric positive semidefinite matrices. This algorithm relies on the factorization X = Y Y T , where the number of columns of Y fixes an upper bound on the rank of the positive semidefinite matrix X. It is thus very effective for solving problems that have a low-rank solution. The factorization X = Y Y T leads to a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second-order optimization method with guaranteed quadratic convergence. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. In contrast to existing methods, the proposed algorithm converges monotonically to the sought solution. Its numerical efficiency is evaluated on two applications: the maximal cut of a graph and the problem of sparse principal component analysis. © 2010 Society for Industrial and Applied Mathematics.

Consensus on homogeneous manifolds

The present paper considers distributed consensus algorithms for agents evolving on a connected compact homogeneous (CCH) manifold. The agents track no external reference and communicate their relative state according to an interconnection graph. The paper first formalizes the consensus problem for synchronization (i.e. maximizing the consensus) and balancing (i.e. minimizing the consensus); it thereby introduces the induced arithmetic mean, an easily computable mean position on CCH manifolds. Then it proposes and analyzes various consensus algorithms on manifolds: natural gradient algorithms which reach local consensus equilibria; an adaptation using auxiliary variables for almost-global synchronization or balancing; and a stochastic gossip setting for global synchronization. It closes by investigating the dependence of synchronization properties on the attraction function between interacting agents on the circle. The theory is also illustrated on SO(n) and on the Grassmann manifolds. ©2009 IEEE.

Synchronization in networks of identical linear systems

The paper investigates the synchronization of a network of identical linear state-space models under a possibly time-varying and directed interconnection structure. The main result is the construction of a dynamic output feedback coupling that achieves synchronization if the decoupled systems have no exponentially unstable mode and if the communication graph is uniformly connected. The result can be interpreted as a generalization of classical consensus algorithms. Stronger conditions are shown to be sufficient-but to some extent, also necessary-to ensure synchronization with the diffusive static output coupling often considered in the literature. © 2009 Elsevier Ltd. All rights reserved.

Consensus optimization on manifolds

The present paper considers distributed consensus algorithms that involve N agents evolving on a connected compact homogeneous manifold. The agents track no external reference and communicate their relative state according to a communication graph. The consensus problem is formulated in terms of the extrema of a cost function. This leads to efficient gradient algorithms to synchronize (i.e., maximizing the consensus) or balance (i.e., minimizing the consensus) the agents; a convenient adaptation of the gradient algorithms is used when the communication graph is directed and time-varying. The cost function is linked to a specific centroid definition on manifolds, introduced here as the induced arithmetic mean, that is easily computable in closed form and may be of independent interest for a number of manifolds. The special orthogonal group SO (n) and the Grassmann manifold Grass (p, n) are treated as original examples. A link is also drawn with the many existing results on the circle. © 2009 Society for Industrial and Applied Mathematics.

Synchronization in networks of identical linear systems

The paper investigates the synchronization of a network of identical linear time-invariant state-space models under a possibly time-varying and directed interconnection structure. The main result is the construction of a dynamic output feedback coupling that achieves synchronization if the decoupled systems have no exponentially unstable mode and if the communication graph is uniformly connected. Stronger conditions are shown to be sufficient - but to some extent, also necessary - to ensure synchronization with the diffusive static output coupling often considered in the literature. © 2008 IEEE.

Stabilization of planar collective motion with limited communication

This paper proposes a design methodology to stabilize relative equilibria in a model of identical, steered particles moving in the plane at unit speed. Relative equilibria either correspond to parallel motion of all particles with fixed relative spacing or to circular motion of all particles around the same circle. Particles exchange relative information according to a communication graph that can be undirected or directed and time-invariant or time-varying. The emphasis of this paper is to show how previous results assuming all-to-all communication can be extended to a general communication framework. © 2008 IEEE.

Collective motion of self-propelled particles: Stabilizing symmetric formations on closed curves

We provide feedback control laws to stabilize formations of multiple, unit speed particles on smooth, convex, and closed curves with definite curvature. As in previous work we exploit an analogy with coupled phase oscillators to provide controls which isolate symmetric particle formations that are invariant to rigid translation of all the particles. In this work, we do not require all particles to be able to communicate; rather we assume that inter-particle communication is limited and can be modeled by a fixed, connected, and undirected graph. Because of their unique spectral properties, the Laplacian matrices of circulant graphs play a key role. The methodology is demonstrated using a superellipse, which is a type of curve that includes circles, ellipses, and rounded rectangles. These results can be used in applications involving multiple autonomous vehicles that travel at constant speed around fixed beacons. ©2006 IEEE.

What is the weakest topology in which feedback stability is robust?

Mathematical theorems in control theory are only of interest in so far as their assumptions relate to practical situations. The space of systems with transfer functions in ℋ∞, for example, has many advantages mathematically, but includes large classes of non-physical systems, and one must be careful in drawing inferences from results in that setting. Similarly, the graph topology has long been known to be the weakest, or coarsest, topology in which (1) feedback stability is a robust property (i.e. preserved in small neighbourhoods) and (2) the map from open-to-closed-loop transfer functions is continuous. However, it is not known whether continuity is a necessary part of this statement, or only required for the existing proofs. It is entirely possible that the answer depends on the underlying classes of systems used. The class of systems we concern ourselves with here is the set of systems that can be approximated, in the graph topology, by real rational transfer function matrices. That is, lumped parameter models, or those distributed systems for which it makes sense to use finite element methods. This is precisely the set of systems that have continuous frequency responses in the extended complex plane. For this class, we show that there is indeed a weaker topology; in which feedback stability is robust but for which the maps from open-to-closed-loop transfer functions are not necessarily continuous. © 2013 Copyright Taylor and Francis Group, LLC.

A reversible infinite HMM using normalised random measures

Copyright 2014 by the author(s). We present a nonparametric prior over reversible Markov chains. We use completely random measures, specifically gamma processes, to construct a countably infinite graph with weighted edges. By enforcing symmetry to make the edges undirected we define a prior over random walks on graphs that results in a reversible Markov chain. The resulting prior over infinite transition matrices is closely related to the hierarchical Dirichlet process but enforces reversibility. A reinforcement scheme has recently been proposed with similar properties, but the de Finetti measure is not well characterised. We take the alternative approach of explicitly constructing the mixing measure, which allows more straightforward and efficient inference at the cost of no longer having a closed form predictive distribution. We use our process to construct a reversible infinite HMM which we apply to two real datasets, one from epigenomics and one ion channel recording.

Dense active appearance models using a bounded diameter minimum spanning tree

We present a method for producing dense Active Appearance Models (AAMs), suitable for video-realistic synthesis. To this end we estimate a joint alignment of all training images using a set of pairwise registrations and ensure that these pairwise registrations are only calculated between similar images. This is achieved by defining a graph on the image set whose edge weights correspond to registration errors and computing a bounded diameter minimum spanning tree (BDMST). Dense optical flow is used to compute pairwise registration and we introduce a flow refinement method to align small scale texture. Once registration between training images has been established we propose a method to add vertices to the AAM in a way that minimises error between the observed flow fields and a flow field interpolated between the AAM mesh points. We demonstrate a significant improvement in model compactness using the proposed method and show it dealing with cases that are problematic for current state-of-the-art approaches.

Classification using log Gaussian Cox processes

McCullagh and Yang (2006) suggest a family of classification algorithms based on Cox processes. We further investigate the log Gaussian variant which has a number of appealing properties. Conditioned on the covariates, the distribution over labels is given by a type of conditional Markov random field. In the supervised case, computation of the predictive probability of a single test point scales linearly with the number of training points and the multiclass generalization is straightforward. We show new links between the supervised method and classical nonparametric methods. We give a detailed analysis of the pairwise graph representable Markov random field, which we use to extend the model to semi-supervised learning problems, and propose an inference method based on graph min-cuts. We give the first experimental analysis on supervised and semi-supervised datasets and show good empirical performance.

Viruses' complete genomes classification based on geometrical learning

In this paper, we proposed a method of classification for viruses' complete genomes based on graph geometrical theory in order to viruses classification. Firstly, a model of triangular geometrical graph was put forward, and then constructed feature-space-samples-graphs for classes of viruses' complete genomes in feature space after feature extraction and normalization. Finally, we studied an algorithm for classification of viruses' complete genomes based on feature-space-samples-graphs. Compared with the BLAST algorithm, experiments prove its efficiency.