0405图论深度学习方法

OptimizationonGraphsPartII:TechnicalModelsClassicalSolutiontoGraphMatchingProblemedge-edgesimilaritynode-nodesimilarityNP-hardGMProblem:ClassicalGMPipeline:SIFTfeatureextractorcomputenode,edgesimilarityclassicalalgorithmapproximatesolutionmatchingresultFixedmethod,e.g.GaussianKernelFunction(limitedrepresentationcapabilityofSIFT)(limitedcapacityduetofixedsimilarity)(limitedperformanceofclassicalalgorithm)LearningGMbyGraphEmbeddingModelICCV19/TPAMI20ClassicalGMPipeline:SIFTfeatureextractorcomputenode,edgesimilarityclassicalalgorithmapproximatesolutionmatchingresultDeepGraphEmbeddingGMPipeline:CNNfeatureextractorintra-+cross-graphGNNembeddingSinkhornalgorithmmatchingresultlearnnodesimilarity(differentiableend-to-endlearning)[1]CombinatorialLearningofRobustDeepGraphMatching:anEmbeddingbasedApproach,TPAMI

2020[2]LearningCombinatorialEmbeddingNetworksforDeepGraphMatching,ICCV2019

LearningGMbyGraphEmbeddingModelICCV19/TPAMI20Intra-graphNodeEmbedding:GraphConvolutionalNetworkCross-graphNodeEmbedding:Calculatesimilarity→ Computecross-graphweightsbySinkhornAdvantagesofgraphembedding:Includesgraphstructureinformation,comparedwithnodematchingReducescomplexity（NP-hard→O(N3)solvable）,comparedwithgraphmatchingTheupdatestepiteratesoverallnodesTheupdatestepiteratesoverallnodesSinkhorn:differentiable,exactlinearassignmentalgorithmHowtoinvoke:pipinstallpygmtools

(alreadysupportnumpy,pytorch,paddle,jittor;willsupport tensorflow,mindspore)>>>import

torch>>>import

pygmtools

as

pygm>>>pygm.BACKEND

=

'pytorch’

>>>np.random.seed(0)#2-dimensional(non-batched)input

>>>s_2d

=

torch.from_numpy(np.random.rand(5,5))>>>s_2d

tensor([[0.5488,0.7152,0.6028,0.5449,0.4237],

[0.6459,0.4376,0.8918,0.9637,0.3834],

[0.7917,0.5289,0.5680,0.9256,0.0710],

[0.0871,0.0202,0.8326,0.7782,0.8700],

[0.9786,0.7992,0.4615,0.7805,0.1183]])

>>>x

=

pygm.sinkhorn(s_2d)>>>x

tensor([[0.1888,0.2499,0.1920,0.1603,0.2089],

[0.1895,0.1724,0.2335,0.2219,0.1827],

[0.2371,0.2043,0.1827,0.2311,0.1447],

[0.1173,0.1230,0.2382,0.1996,0.3219],

[0.2673,0.2504,0.1536,0.1869,0.1418]])

>>>print('row_sum:',x.sum(1),'col_sum:',x.sum(0))row_sum:tensor([1.0000,1.0000,1.0000,1.0000,1.0000])col_sum:tensor([1.0000,1.0000,1.0000,1.0000,1.0000])

LearningGMbyGraphEmbeddingModelICCV19/TPAMI20PermutationLoss:Thematchingproblemcanbeconsideredas abinaryclassificationproblemforeachelement

Comparedwiththeregressionbasedoffsetlossusedinthepast,thepermutationlossbetter

portraysthecombina-torialoptimizationnatureofgraphmatchingLearningGMbyGraphEmbeddingModelICCV19/TPAMI20ModelCNNGMFormulationLossFuncMatchingAccGMNVGG16ClassicalGM（Zanfiretal.CVPR2018）OffsLoss55.3GMN-PLVGG16ClassicalGM（Zanfiretal.CVPR2018）PermLoss57.9PIA-GM-OLVGG16Intra-graphGNNOffsLoss61.6PIA-GMVGG16Intra-graphGNNPermLoss63.0PCA-GMVGG16Intra-+Cross-graphGNNPermLoss63.8MatchingresultsonPascalVOC:PermutationLoss>OffsetLoss，Intra-+Cross-graphGNN>Intra-graphGNN>ClassicalGMThemodelhasthecapabilitytotransferacrosscategories:LearningGMbyGraphEmbeddingModelICCV19/TPAMI20GMisequivalenttonodeclassificationonanassociationgraph:AssociationGraphGraphMatchingProblemNode1matchesnodea 1a=1onassociationgraphTherefore,GMsolvers==nodeclassifieronassociationgraphNaturally,GNNthatexcelinnodeclassificationcanserveasgraphmatchingsolvers!LearningGMSolversTPAMI2021IntroduceSplineConv(Feyetal.CVPR18)toencodegeometricinformation

atfeaturelevelDevisekernelfunctionsassociatedwithCNNCNNExtractor(Optional)LearningSolverGCNadoptedfornodeclassificationonassociationgraph(i.e.solvingGM)ConsidermatchingconstraintsinGNNOutputmatchingresultPascalVOCDatasetMatchingAccPreviousSOTA(Rolineketal.ECCV20)79.0NGMv2(ours)80.1LearningGMSolversTPAMI2021ComputeleadingNeigenvectors(N=3)ExtendtoMulti-graphMatching👉AdoptpermutationsynchronizationtechniquePachauriyetal.,Solvingthemulti-waymatchingproblembypermutationsynchronization,inNIPS2013

ExtendtoHyperGraphMatching👇NeuralGraphMatching(NGM)GMNeuralHyperGraphMatching(NHGM)HGM1/2orderfeatureshigh-orderfeaturesassociationgraphassociationhypergraphupdatefeaturesalongedgesupdatefeaturesalonghyperedgesmatchingacc80.1matchingacc80.7MGMTestDatasetMatchingAccNGMv2(2GM)97.5NHGMv2(HGM)97.8NMGMv2(MGM)98.2LearningGMSolversTPAMI2021

GNNNodeClassifierDoubleStochasticIterationSolu-tionQuadraticAssignmentProblem(QAP)

TestDataset:https://www.opt.math.tugraz.at/qaplib/AssocGraphConstructionComparedwithSOTASinkhorn-basealgorithmSIAMJ.ImagingSci.2019AnnealingAlgorithmECCV10LearningAlgorithmCVPR18BestPaperHonorableMentionsComparedwithGurobiProposedLearningAlgorithmTPAMI21GPUComputingCPUComputing1631xacceleration!431xacceleration!Intel(R)Xeon(R)W-3175XCPU@3.10GHzNVIDIARTX8000RunningTime(logscale)Dataset:NeuralGraphMatchingNetwork:LearningLawler’s

Quadratic

AssignmentProblemwithExtensionstoHypergraphandMulti-graphmatching,TPAMI

2021LossFunc(lowerisbetter)LearningGMSolversTPAMI2021SolvingCombinatorialOptimizationoverGraphsbyaGeneralBi-levelMLFrameworkNeurIPS2021ABi-levelFrameworkforLearningtoSolveCombinatorialOptimizationoverGraphs,NeurIPS

2021DecisionVariableObjectiveFunctionConstraintsActionSequenceRewardActionFeasibleDomainForCOproblemsovergraphs,currentformulationisExistingpapersusereinforcementlearningmodeling:HoweverLargerscale，longeractionsequence

Sparsereward,hardtoconvergeAssumeadequatemodelcapacitytolearn

NP-hardproblem，hardtodevisemodelAddingcuttingplanesforintegerprogrammingResorttotheclassicidea:ModifyingtheoriginalproblemtoaidproblemsolvingThispaper:ModifyinggraphstructureAddedgesGitHubrepoQRcodeUpper-level:AdoptareinforcementlearningagenttoadaptivelymodifythegraphsLower-level:OptimizedecisionvariablesbyheuristicsProposeaBi-levelOptimizationFormulation:Bi-levelFramework:Whentheupper-levelRLmodifiesgraphstructure,thelower-levelheuristicisinvokedUpper-levelOptim