Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching
Graph matching is a challenging problem with very important applications in a wide range of fields, from image and video analysis to biological and biomedical problems. We propose a robust graph matching algorithm inspired in sparsityrelated techniques. We cast the problem, resembling group or collaborative sparsity formulations, as a non-smooth convex optimization problem that can be efficiently solved using augmented Lagrangian techniques. The method can deal with weighted or unweighted graphs, as well as multimodal data, where different graphs represent different types of data. The proposed approach is also naturally integrated with collaborative graph inference techniques, solving general network inference problems where the observed variables, possibly coming from different modalities, are not in correspondence. The algorithm is tested and compared with state-of-the-art graph matching techniques in both synthetic and real graphs. We also present results on multimodal graphs and applications to collaborative inference of brain connectivity from alignment-free functional magnetic resonance imaging (fMRI) data. The code is publicly available.
This paper examines the problem of approximate graph 
      matching (isomorphism). Given graphs G, H with p nodes, represented by 
      respective adjacency matrices A, B, Find a permutation matrix P that 
      best ``matches’’ AP and PB. The paper indicates that this is a 
      problem with a long history. The fundamental problem is combinatorial and 
      its complexity is not fully understood. This has led to various relations 
      of the problem. For example to minimize a convex matching metric under the 
      constraint that the permutation P is relaxed to a doubly stochastic matrix 
      **[reference needed at this point in the paper (line 061)]. Once 
      the resulting convex problem is solved one then finds the nearest 
      permutation matrix to the solution. The authors point out that the 
      traditional Frobenius norm matching metric ||AP-PB||_F^2, does not 
      produce a common core shared graph with a sparse set of outlier edges. 
      Hence they propose a group lasso approach in which the matching metric is 
      the sum of the Euclidean norms of the corresponding entries of AP and PB 
      (equation 2). This is motivated by the heuristic argument that the group 
      lasso will tend to set most groups of coefficients to zero with only a few 
      groups nonzero. So the metric will seek a permutation that matrices 
      many edges and will have a sparse set of edges that do not match well. 
      The only theoretical result of the paper is Lemma 1, which 
      verifies that the proposed matching metric makes sense in the very special 
      case of two isomorphic, undirected, unweighted graphs with no self loops 
      (and obviously no noise in the form of randomly added edges). The lemma 
      indicates that in this case, minimizing the metric will achieve AP=PB with 
      P doubly stochastic. The proof is very elementary. The authors 
      then propose an optimization procedure for minimizing the new matching 
      metric subject to P being doubly stochastic (problem (3)). This is based 
      on a linearized variation of ADMM drawing heavily from the work by Lin et 
      al (NIPS 2011). **[Note: possible typo line 154: ADMOM ?]. 
      Section 4, shows how the above ideas could be applied to 
      collaborative inverse covariance estimation in the spirit of the graphical 
      lasso. This leads to a non convex problem, but which is convex when either 
      of two disjoint set of variable is fixed. This gives an alternating, two 
      phase sequence of convex problems. The basic problem seems to have its 
      origins in Chiquet 2011, where it is addressed using a different method. 
      The experimental section of paper describes four experiments. The 
      first explores performance of the proposed method and algorithm on several 
      synthetic forms of graphs. The proposed method appears to have significant 
      advantages in these experiments. The second experiment involves graph 
      matching on real graphs from the connectome of C. elegans. There are two 
      graphs (chemical connections and electrical connections). Although the 
      data is real the problem solved is artificial: each graph is first 
      permuted, edge noise is added and then this graph is matched to its 
      original. Experiment three explores the proposed method’s ability 
      to match graphs with edge weights drawn from different distributions 
      (a.k.a. multimodal graph matching). This is explored using synthetic 
      datasets in the spirit of the first experiment. At low noise levels the 
      proposed method seems to have a distinct advantage over competing methods 
      – note however that in this case this means there is an (almost) exact 
      match – this is unlikely to happen in real-world datasets. The 
      fourth experiment on collaborative inference is also based on real data – 
      in this case resting state fMRI. However, the actual experiment is 
      synthetic with the data to be matched obtained by permuting the real data. 
      This is an interesting experiment. It shows that that the proposed method 
      has potential advantages over the usual application of the graphical lasso 
      – but is this surprising? The graphical lasso uses each graph separately, 
      while the proposed method allows the graphs to collaborate. This is 
      obviously a good thing and should lead to improved results. The experiment 
      confirms that this is the case. Let me note that in several places 
      the authors emphasize that the proposed method shows promising performance 
      “on real data”. For example, phrases of this type appear twice in the 
      conclusion. This is a little misleading since although the data is 
      obtained from real experiments the actual tests performed are synthetic 
      and hence are not reflective of actual alignments that would occur in 
      practice. It would be better to say: “shows promising performance using 
      real data to form synthetic alignment problems”.