Vi föreslår en konvex-konkav programmeringsmetod för den märkta viktade graf matchning problem. Konvex konkav programmering formulering erhålls genom att skriva om den viktade graf matchning problem som ett minst-kvadrat problem på uppsättningen permutation matriser och koppla den till två olika optimeringsproblem: en kvadratisk konvex och en kvadratisk konkav optimering problem på uppsättningen av doubly stokastiska matriser. Den konkava avkoppling har samma globala minimum som den ursprungliga graf matchning problem, men sökandet efter dess globala minimum är också ett svårt kombinatorial problem. Vi konstruerar därför en approximation av konkav problemlösning genom att följa en lösning väg av ett konvex-konkav problem som erhålls genom linjär interpolering av konvexa och konkav formuleringar, med början från konvex avslappning. Denna metod gör det enkelt att integrera informationen på grafetikett likheter i optimeringsproblem, och därför utföra märkta viktade graf matchning. Algoritmen jämförs med några av de bäst presterande grafmatchningsmetoderna på fyra datauppsättningar: simulerade grafer, QAPLib, bilder av näthinnans kärl och handskrivna kinesiska tecken. I samtliga fall är resultaten konkurrenskraftiga med den senaste tekniken.
I den metod för att följa sökvägar som föreslås i REF skrev författaren om problemet med grafmatchning som ett ungefärligt problem med permutationsmatriser.
A Path Following Algorithm for the Graph Matching Problem
{'venue': 'IEEE Transactions on Pattern Analysis and Machine Intelligence', 'journal': 'IEEE Transactions on Pattern Analysis and Machine Intelligence', 'mag_field_of_study': ['Computer Science', 'Medicine']}