(a) 
`
`Fig.  11. 3  A n  exampl e  o f matchin g  a s 
`parameter  optimization ,  (a )  Initia l 
`parameter  se t  (displaye d  a t  lef t  a s three ­
`dimensional  surfac e  (se e Fig . 9.8 )  (b ) 
`Fitting process : iterativel y  adjus t  a  base d 
`on M   (se e text) ,  (c )  Fina l  paramete r  se t 
`yields  thi s three­dimensiona l  surface . 
`{See color  inserts.) 
`
`Ch. 11   Matching 
`
`356 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 367
`
`

`

`continuum,  an d tha t  labele d  arc s  coul d  b e replace d  b y node s  t o yiel d a  directe d 
`graph wit h labele d nodes . 
`Depending o n th e attribute s o f th e relationa l structur e an d o f th e correspon ­
`dence desired , th e definitio n  o f a  matc h  ma y b e mor e o r les s elegant . I t i s alway s 
`possible t o translat e powerfu l  representation s suc h a s labele d graph s o r «­ar y rela ­
`tions int o computationa l  representation s whic h ar e amenabl e t o forma l  treatmen t 
`(such a s undirecte d  graphs) .  However ,  whe n  grap h  algorithm s  ar e t o b e imple ­
`mented  wit h  compute r  dat a  structures ,  th e freedo m  an d powe r  o f programmin g 
`languages ofte n  tempt s th e implemente r  awa y fro m  pur e grap h theory . H e ca n re ­
`place  elegan t  (bu t occasionall y  restrictiv e  an d impractical )  graph­theoreti c  con ­
`cepts an d operation s wit h arbitraril y comple x dat a structure s an d algorithms . 
`One exampl e  i s th e "grap h  isomorphism "  problem ,  a  ver y pur e  versio n o f 
`relational  structur e  matching . I n it , al l grap h  node s an d arc s ar e unlabeled , an d 
`graphs matc h i f ther e i s a  1: 1 an d ont o correspondenc e betwee n th e arc s an d node s 
`of th e  tw o graphs . Th e  lac k o f expressiv e  powe r i n thes e graph s an d th e require ­
`ment tha t a  matc h b e "perfect "  limit s th e usefulnes s  o f thi s pur e mode l o f match ­
`ing i n th e contex t  o f nois y inpu t an d imprecis e  referenc e  structures .  I n practice , 
`graph  node s  ma y hav e  propertie s  wit h  continuou s  range s o f values , an d a n arbi ­
`trarily comple x algorith m determine s whethe r node s o r arc s match . Th e algorith m 
`may eve n acces s informatio n  outsid e th e graph s themselves , a s lon g a s i t return s 
`the answe r  "match " o r "n o match. " Generalizin g  th e graph­theoreti c notion s i n 
`this wa y ca n obscur e  issue s o f thei r  efficiency ,  power ,  an d properties ; on e mus t 
`steer a  cours e betwee n th e "elegan t an d unusable " an d th e "genera l  an d uncon ­
`trollable." Thi s  sectio n  introduce s  som e  "pure "  graph­theoreti c  algorithm s  tha t 
`form th e basi s fo r technique s i n Section s 11. 3 an d 11.4 . 
`
`11.2.1  Th e Algorithm s 
`
`The  followin g  ar e severa l  definition s  o f matchin g  betwee n  graph s  [Harar y  1969 ; 
`Berge 1976] . 
`•  Graph  isomorphism.   Give n tw o graph s  (V\,   E\)  an d (V 2,  E 2), find  a  1: 1 an d 
`onto  mappin g  (a n  isomorphism )  /   betwee n  V\   an d  V 2  suc h  tha t  fo r 
`V\, v 2 €   V\,   V 2, f(v\)   =  v 2 an d fo r eac h  edg e o f E\   connectin g  an y pai r o f 
`nodes v i an d v' i  €   V\,  ther e i s a n edg e o f E 2 connectin g f(v\)   an d 
`f(y\). 
`•  Subgraph  isomorphism.   Fin d isomorphism s betwee n a  grap h (V\ i  E\)  an d sub­
`graphs o f anothe r grap h  ( V2i  E 2). Thi s i s computationall y  harde r tha n  isomor ­
`phism becaus e on e doe s no t kno w i n advanc e whic h subset s o f V 2 ar e involve d 
`in isomorphisms . 
`"Double"subgraph  isomorphisms.   Fin d al l isomorphism s betwee n subgraphs  o f 
`a grap h  (V\ i  E\)  an d subgraphs  o f anothe r grap h  (V 2i  E 2). Thi s sound s harde r 
`than th e subgrap h isomorphis m problem , bu t i s equivalent . 
`•  A  matc h ma y no t confor m  t o stric t rule s o f correspondenc e  betwee n arc s an d 
`nodes  (som e  node s  an d arc s  ma y b e "unimportant") .  Suc h  a  matchin g  cri ­
`terion ma y wel l b e implemente d a s a  "computational "  (impure ) versio n o f on e 
`of th e pur e grap h isomorphisms . 
`
`• 
`
`Sec.  11.2   Graph­Theoretic  Algorithms 
`
`357 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 368
`
`

`

`Figure 11. 4 show s example s o f thes e kind s o f matches . 
`One algorith m  fo r  findin g  grap h  isomorphis m  [Cornei l an d Gotlie b  1970 ] i s 
`based  o n  th e  ide a  o f  separatel y  puttin g  eac h  grap h  int o  a  canonica l  form ,  fro m 
`which isomorphis m  ma y easil y b e determined .  Fo r directe d graph s  (i.e. , nonsym ­
`metric  relations )  a   backtrac k  searc h  algorith m  [Berztis s  1973 ]  work s  o n  bot h 
`graphs a t once . 
`Two  solution s  t o  th e  subgrap h  isomorphis m  proble m  appea r  i n  [Ullma n 
`1976]: Th e  first   i s a  simpl e  enumerativ e  searc h  o f  th e  tre e  o f  possibl e  matche s 
`between  nodes .  Th e  secon d  i s  mor e  interesting ;  i n  i t  a   proces s  o f  "parallel ­
`iterative" refinemen t  i s applie d a t eac h stag e o f th e search . Thi s proces s i s a  wa y o f 
`rejecting  nod e  pair s fro m  th e isomorphis m  an d  o f propagatin g  th e effect s  o f suc h 
`rejections; on e rejecte d  matc h ca n lea d t o mor e matche s bein g rejected .  Whe n  th e 
`iteration  converge s  (i.e. ,  whe n  n o  mor e  matche s  ca n  b e  rejecte d  a t  th e  curren t 
`stage), anothe r ste p i n th e tre e searc h i s performe d  (on e mor e matchin g pai r i s hy ­
`pothesized). Thi s mixin g o f parallel­iterativ e processe s wit h tre e searc h i s usefu l i n 
`a variet y o f application s  (Sectio n 11.4.4 , Chapte r 12) . 
`"Double" subgrap h isomorphis m i s easil y reduce d t o subgrap h  isomorphis m 
`via anothe r well­know n grap h problem , th e "cliqu e problem. " A  clique  of  siz e ./Vi s 
`a totall y connecte d subgrap h o f siz e TV (eac h nod e i s connecte d t o ever y othe r nod e 
`in  th e  cliqu e  b y a n arc) . Findin g  isomorphism s  betwee n  subgraph s  o f a  grap h A 
`and subgraph s o f a  grap h B  i s accomplishe d b y formin g a n association  graph  G  fro m 
`the graph s A  an d B  an d finding  clique s i n G  (fo r details , se e Sectio n  11.3.3) . Cliqu e 
`
`(b) 
`
`(c) 
`
`(d) 
`
`(e) 
`
`Isomorphism s  an d  matches . Th e grap h  (a )  ha s a n  isomorphis m  wit h 
`Fig.  11. 4 
`(b), variou s subgrap h isomorphism s wit h  (c) , an d severa l "double " subgrap h iso ­
`morphisms wit h  (d) .  Severa l partia l matche s wit h  (e )  (an d als o (b) , (c) , an d (d)) , 
`depending o n whic h missin g o r extr a node s ar e ignored . 
`
`358 
`
`Ch. 11   Matching 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 369
`
`

`

`finding  ma y b e don e wit h a  subgrap h isomorphis m algorithm ; henc e th e reduction . 
`Several  othe r  clique­findin g  algorithm s  exis t  [Amble r  e t  al .  1975 ; Knode l  1968 ; 
`BronandKerbosch  1973 ; Ostee n an d To u 1973] . 
`
`11.2.2  Complexit y 
`
`It i s o f som e practica l importanc e  t o b e awar e o f th e computationa l  complexit y o f 
`the matchin g algorithm s propose d here ; the y ma y tak e surprisin g amount s o f com ­
`puter time .  Ther e ar e man y accessibl e treatment s o f computationa l complexit y o f 
`graph­theoreti c  algorithm s  [Reingol d  e t  al .  1977 ;  Aho ,  Hopcrof t  an d  Ullma n 
`1974]. Theoretica l result s usuall y describ e worst­cas e o r averag e tim e complexity . 
`The  stat e o f  knowledg e  i n  grap h  algorithm s  i s stil l  improving ;  som e  interestin g 
`worst­cas e bound s hav e no t bee n established . 
`A "hard " combinatoria l  proble m i s on e tha t take s tim e  (i n a  usua l mode l o f 
`computation  base d  o n a  seria l computer )  proportiona l  t o a n exponentia l  functio n 
`of th e lengt h o f th e input . "Polynomial­time " solution s ar e desirabl e becaus e the y 
`do no t gro w a s fas t wit h th e siz e o f th e problem .  Th e tim e t o find  al l th e clique s o f a 
`graph i s i n th e wors t cas e inherentl y exponentia l i n th e siz e o f th e inpu t graphs , be ­
`cause th e outpu t i s a n exponentia l numbe r o f graphs . Bot h th e singl e subgrap h iso ­
`morphism proble m an d th e "cliqu e problem "  (doe s ther e exis t a  cliqu e o f siz e £? ) 
`are NP­complete;  al l know n deterministi c algorithm s ru n  (i n th e wors t case ) i n tim e 
`exponential  i n  th e  lengt h  o f  th e  descriptio n  o f th e graph s  involve d  (whic h  mus t 
`specify  th e node s an d arcs) . No t onl y this , bu t i f eithe r o f thes e problem s  (o r a  hos t 
`of othe r N P complet e problems )  coul d b e solve d deterministicall y  i n tim e polyno ­
`mial^ relate d t o th e lengt h o f th e input , i t coul d b e use d t o solv e al l th e othe r N P 
`problems i n polynomia l time . 
`Graph  isomorphism ,  bot h  directe d  an d  undirected ,  i s  a t  thi s  writin g  i n  a 
`netherworld  (alon g  wit h  man y  othe r  combinatoria l  problems) .  N o  polynomial ­
`time deterministi c  algorithm s  ar e know n  t o exist ,  bu t  th e relatio n  o f thes e prob ­
`lems t o eac h othe r i s no t a s clear­cu t a s i t i s betwee n th e NP­complet e problem . I n 
`particular, finding a  polynomial­tim e  deterministi c solutio n t o on e o f the m woul d 
`not necessaril y indicat e anythin g abou t ho w t o solv e th e othe r problem s determin ­
`istically  i n polynomia l  time . Thes e  problem s  ar e no t  mutuall y  reducible .  Certai n 
`restrictions o n  th e graphs ,  fo r  instanc e tha t the y ar e plana r  (ca n b e arrange d wit h 
`their node s i n a  plan e an d wit h n o arc s crossing) , ca n mak e grap h isomorphis m a n 
`"easy"  (polynomial­time )  problem . 
`The average­cas e complexit y i s ofte n o f mor e practica l interes t tha n th e wors t 
`case. Typically , suc h a  measur e i s impossibl e t o determin e analyticall y an d mus t b e 
`approximated  throug h  simulation .  Fo r  instance ,  on e  algorith m  t o  find   isomor ­
`phisms  o f randoml y  generate d  graph s  yield s  a n  averag e  tim e  tha t  seem s  no t  ex ­
`ponential, bu t proportiona l  t o N 3  ,  wit h /Vth e numbe r  o f node s i n th e grap h  [Ull ­
`man  1976] . Anothe r  algorith m  seem s  t o  ru n  i n  averag e tim e  proportiona l  t o  N 2 
`[Corneil an d Gotlie b 1970] . 
`All th e grap h  problem s o f thi s sectio n ar e i n NP . Tha t is , a   «o«deterministi c 
`algorithm ca n solv e the m i n polynomia l time . Ther e ar e variou s way s o f visualizin g 
`
`Sec.  77. 2  Graph­Theoretic  
`
`Algorithms 
`
`359 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 370
`
`

`

`nondeterministic  algorithms ;  on e  i s  tha t  th e  algorith m  make s  certai n  significan t 
`"good guesses " fro m a  rang e o f possibilitie s  (suc h a s correctl y guessin g whic h sub ­
`set  o f  node s fro m  grap h  B  ar e  isomorphi c  wit h grap h  A  an d  the n  onl y  havin g  t o 
`worry  abou t  th e  arcs) .  Anothe r  wa y  i s  t o  imagin e  parallel  computation ;  i n  th e 
`clique problem ,  fo r example , imagin e multipl e machine s runnin g i n parallel , eac h 
`with a  differen t  subse t  o f node s fro m  th e inpu t graph . I f an y machin e discover s a 
`totally  connecte d  subset ,  i t has , o f course , discovere d a  clique . Checkin g  whethe r 
`TV node s ar e al l pairwis e connecte d i s a t mos t a  polynomial­tim e problem , s o al l th e 
`machines wil l terminat e i n polynomia l time , eithe r wit h succes s o r not . Severa l in ­
`teresting processe s ca n b e implemente d wit h paralle l computations . Ullman' s algo ­
`rithm  use s a  refinemen t  procedur e whic h ma y ru n i n paralle l betwee n stage s o f hi s 
`tree search , an d whic h h e explain s ho w t o implemen t i n paralle l hardwar e  [Ullma n 
`1976]. 
`
`11.3  IMPLEMENTIN G GRAPH­THEORETI C  ALGORITHM S 
`
`11.3.1  Matchin g Metric s 
`
`Matching  involve s  quantifiable   similarities.   A   matc h  i s  no t  merel y  a   correspon ­
`dence, bu t a  correspondenc e tha t ha s bee n quantifie d  accordin g t o it s "goodness. " 
`This  measur e  o f goodnes s  i s th e  matching  metric.   Similarit y  measure s  fo r  correla ­
`tion  matchin g  ar e  lumpe d  togethe r  a s  on e  number .  I n  relationa l  matchin g  the y 
`must  tak e int o accoun t a  relational ,  structure d  for m  o f dat a  [Shapir o an d Haralic k 
`1979]. 
`Most  o f th e structura l  matchin g  metric s ma y  b e explaine d  wit h th e  physica l 
`analogy  o f "template s  an d  springs "  [Fischle r  an d  Elschlage r  1973] . Imagin e  tha t 
`the referenc e  dat a compris e a  structur e o n a  transparen t rubbe r sheet . Th e match ­
`ing proces s move s thi s shee t ove r th e inpu t dat a structure ,  distortin g th e shee t s o 
`as  t o  ge t  th e  bes t  match .  Th e  final   goodnes s  o f  fit   depend s  o n  th e  individua l 
`matches betwee n element s o f th e inpu t an d referenc e  data , an d o n th e amoun t o f 
`work i t take s t o distor t  th e sheet .  Th e continuou s deformatio n  proces s i s a  prett y 
`abstraction whic h mos t matchin g algorithm s d o no t implement . A  computationall y 
`more  tractabl e  for m  o f  th e  ide a  i s  t o  conside r  th e  mode l  a s a  se t  o f  rigi d  "tem ­
`plates"  connecte d  b y  "springs "  (se e  Fig .  11.5) . Th e  template s ar e connecte d  b y 
`"springs" whos e "tension " i s als o a  functio n  o f th e relation s betwee n elements . A 
`spring  functio n  ca n  b e  arbitraril y  comple x  an d  nonlinear ;  fo r  exampl e  th e  "ten ­
`sion" i n th e sprin g ca n attai n ver y hig h o r infinit e value s fo r configuration s o f tem ­
`plates whic h canno t  b e allowed .  Nonlinearit y  i s goo d  fo r  suc h constraint s  as : i n a 
`picture o f a  fac e th e tw o eye s mus t  b e essentiall y i n a  horizonta l  lin e an d mus t b e 
`within fixed  limit s o f distance .  Th e qualit y o f th e matc h i s a  functio n  o f th e good ­
`ness o f fit  o f th e template s  locall y an d  th e amoun t  o f "energy "  neede d  t o stretc h 
`the spring s t o forc e  th e  inpu t  ont o  th e referenc e  data . Cost s ma y  b e impose d  fo r 
`missing o r extr a elements . 
`The templat e  matc h  function s  an d  sprin g function s  ar e genera l  procedures , 
`thus  th e  template s  ma y  b e  mor e  genera l  tha n  pur e  iconi c  templates .  Further , 
`
`360 
`
`Ch. 11   Matching 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 371
`
`

`

`Right 
`edge 
`
`Mouth 
`
`Fig.  11. 5  A  template s an d  spring s mode l  o f a  face . 
`
`matches  ma y  b e  define d  no t  onl y  betwee n  node s  an d  othe r  nodes ,  bu t  betwee n 
`nodes an d  imag e dat a directly . Thu s th e templat e an d  spring s formalis m  i s work ­
`able fo r "cross­representational "  matching .  Th e mechanis m o f minimizin g th e to ­
`tal cos t o f th e matc h ca n tak e severa l forms ; mor e detaile d example s follo w i n Sec ­
`tion 11.4 . 
`Equation  11. 3  a   genera l  for m  o f  th e  template­and­spring s  metric .  Tem ­
`plateCost  measure s  dissimilarit y  betwee n  th e  inpu t  an d  th e  templates ,  an d 
`SpringCost  measure s th e dissimilarit y  betwee n th e matche d  inpu t elements ' rela ­
`tions an d th e referenc e  relation s betwee n th e templates . MissingCos t measure s th e 
`penalties fo r missin g elements . F(­ ) i s th e mappin g fro m  template s o f th e referenc e 
`to element s o f th e inpu t data . F  partition s th e referenc e  template s int o tw o classes , 
`those  foun d  {FoundinRefer }  an d  thos e  no t  foun d  {MissinginRefer j  i n  th e  inpu t 
`data. I f th e inpu t dat a ar e symboli c the y ma y b e similarl y partitioned . Th e genera l 
`metric i s 
`
`+ 
`
`Cost= 
`
`TemplateCost U  Fid)) 
`I  
`d  6   {FoundinRefer ) 
`SpringCos t (Fid),   Fie)) 
`L  
`id, e)   6   {FoundinRefe r  x   Foundinlnput l 
`+ 
`L  
`c  €   {MissinginRefer l  U   {Missinginlnput j 
`
`MissingCos t  (c ) 
`
`(11.3) 
`
`Equation  11. 3 ma y b e writte n a s on e su m o f generalize d SpringCost s i n whic h 
`the templat e propertie s ar e include d  (a s 1­ar y  relations) , a s ar e "springs " involv ­
`ing missin g elements . 
`
`Sec.  11.3  
`
`Implementing   Graph­Theoretic   Algorithms 
`
`361 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 372
`
`

`

`As  wit h  correlatio n  metrics ,  ther e  ar e  normalizatio n  issue s  involve d  wit h 
`structural matchin g metrics . Th e numbe r o f element s matche d  ma y affec t  th e ulti ­
`mate  magnitud e  o f  th e  metric .  Fo r  instance ,  i f spring s alway s hav e  a  finite  cost , 
`then th e mor e element s tha t ar e matched ,  th e highe r th e tota l sprin g energ y mus t 
`be;  thi s  shoul d  probabl y  no t  b e take n  t o  impl y  tha t a  matc h  o f man y  element s i s 
`worse  tha n  a  matc h  o f a  few .  Conversely ,  suppos e  tha t  relation s  whic h agre e ar e 
`given positiv e "goodness " measures , an d a  matc h i s chose n o n th e basi s o f th e to ­
`tal "goodness. " The n unles s on e i s careful ,  th e shee r numbe r o f possibl y mediocr e 
`relational matche s induce d b y matchin g man y element s ma y outweig h th e  "good ­
`ness"  o f a n  elegan t  matc h  involvin g  onl y  a  fe w  elements .  O n  th e  othe r  hand , a 
`small, elegan t  matc h  o f a  par t o f th e inpu t  structur e wit h on e particula r  referenc e 
`object  ma y  leav e  muc h  o f  th e  searc h  structur e  unexplained .  Thi s  goo d  "sub ­
`match" ma y b e les s helpfu l  tha n a  matc h tha t explain s mor e o f th e input . T o som e 
`extent  th e genera l  metri c  (Eq.11.3 )  cope s wit h  thi s b y acknowledgin g  th e  "miss ­
`ing" categor y o f elements . 
`If th e referenc e  template s actuall y contai n iconi c representation s  o f wha t th e 
`input  element s  shoul d  loo k  lik e  i n  th e  image ,  a  TemplateCos t  ca n  b e  associate d 
`with a  templat e an d a  locatio n i n th e imag e b y 
`
`TemplateCost (Template ,  Location ) 
`=  ( 1 ­   normalize d  correlatio n  metri c  betwee n 
`template  shap e an d  inpu t  imag e  a t  th e location) . 
`If th e matc h  is , fo r  instance ,  t o matc h referenc e  description s  o f a  chai r wit h 
`an inpu t dat a structure , a  typica l "spring " migh t b e tha t th e chai r sea t mus t b e sup ­
`ported b y it s legs . Thu s i f ./u s th e associatio n functio n  mappin g referenc e  element s 
`such a s LE G o r TABLETO P t o inpu t elements , 
`SpringCost! (/"(LEG) , /"(TABLETOP ) 
`
`_  J O 
`1 
`
`i f F  (LEG )  appear s t o suppor t  F  (TABLETOP) , 
`i f F  (LEG )  doe s no t appea r t o suppor t  F  (TABLETOP) . 
`
`For quantifie d  relations , on e migh t hav e 
`SpringCost2  =   numbe r  o f standar d  deviation s  fro m  th e 
`canonical  mea n  valu e fo r  thi s relation . 
`Another  versio n  o f  SpringCost 2  i s  th e  followin g  [Barro w  an d  Poppleston e 
`1971]. 
`P 
`.   o M  .   ,   =   SpringCost s o f propertie s  (unary ) an d binar y relation s 
`total numbe r o f unar y an d binar y spring s 
`Empirica l Constan t  
`Total numbe r o f referenc e element s matche d 
`The first  ter m measure s  th e averag e badnes s o f matche s betwee n  propertie s 
`(unary relations ) an d relation s betwee n regions . Th e secon d ter m i s inversel y pro ­
`portional t o th e numbe r o f region s tha t ar e matched , effectivel y  increasin g th e cos t 
`of matche s tha t explai n les s o f th e input . 
`
`/, ,  . x 
`
`, 
`
`362 
`
`Ch. 7 7  Matching 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 373
`
`

`

`11.3.2  Backtrac k  Searc h 
`
`Backtrack  searc h i s a  generi c nam e fo r  a  typ e o f potentiall y  exhaustiv e searc h  or ­
`ganized  i n  stages ;  eac h  processin g  stag e  attempt s  t o  exten d  a   partia l  solutio n 
`derived i n th e previou s stage . Shoul d th e attemp t fail , th e searc h  "backtracks " t o 
`the  mos t  recen t  partia l  solution ,  fro m  whic h  a  ne w  extensio n  i s attempted .  Th e 
`technique i s basic , amountin g t o a  depth­firs t  searc h throug h a  tre e o f partia l solu ­
`tions  (Fig .  11.6) . Backtrackin g  i s a  pervasiv e  contro l  structur e  i n artificia l  intelli ­
`
`Fig.  11. 6  Th e grap h o f  (a ) i s t o b e matche d  i n  (b ) wit h arc s al l bein g unlabele d 
`but  node s havin g propertie s indicate d  b y thei r shapes ,  (c )  i s th e tre e o f solution s 
`built b y a  backtrac k algorithm . 
`
`Implementing  Graph­Theoretic   Algorithms 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 374
`
`

`

`gence, an d throug h th e year s severa l genera l classe s o f technique s hav e evolve d t o 
`make th e basic , brute­forc e backtrac k searc h mor e  efficient . 
`Example: Graph  Isomorphisms 
`Given tw o graphs , 
`
`* ­  
`(V X,EX) 
`Y=  (Vy,   Ey), 
`without los s o f generality , le t  V x  =   V Y —   {1 , 2 , . . . ,  »} , an d le t Xb e th e  referenc e 
`graph,  Ythe   inpu t graph . Th e isomorphis m  i s give n by : I f /  €   V x,  th e correspond ­
`ing nod e unde r th e isomorphis m i s F(i)   €   V Y. 
`In th e algorithm , S  i s th e se t o f node s accounte d fo r i n  Yby  a  partia l solution . 
`Ogives th e curren t leve l o f th e searc h i n th e tre e o f partia l solutions , th e numbe r o f 
`nodes  i n  th e  curren t  partia l  solution ,  an d  th e  nod e  o f  X   whos e  matc h  i n  Y  i s 
`currently  bein g sought ,  v  i s a  nod e  o f  Y  currentl y  bein g considere d  t o exten d  th e 
`current  partia l  solution .  A s  written ,  th e  algorith m  finds   al l  isomorphisms .  I t  i s 
`easily modifie d t o qui t afte r finding  th e first. 
`
`(Vy­S) 
`
`Algorithm 11. 1  Backtrac k Searc h fo r Directe d Grap h Isomorphis m 
`Recursive Procedure   DirectedGraphlsomorphism s  (S,k) ; 
`begin 
`if  S=V Y  then   ReportAsIsomorphism(F ) 
`else 
`forallvt 
`do 
`//Match (A: , v ) 
`then 
`begin 
`F(k):=v; 
`DirectedGraphlsomorphisms  (£ €   {v},A:­rl) ; 
`end; 
`
`end, 
`
`ReportAsIsomorphism  coul d prin t o r sav e th e curren t  valu e o f F,  th e globa l 
`structure  recordin g  th e  curren t  solution .  Match(/c,v )  i s  a   procedur e  tha t  test s 
`whether  v  €   V y ca n correspon d t o k  €   V x unde r th e isomorphis m s o fa r define d b y 
`F. Le t X k  b e th e subgrap h o f A'wit h vertice s {1,2, . .  .,k).  Th e procedur e  "Match " 
`must chec k fo r  i  <  k,  whethe r  (/ ,  k)   i s a n edg e o f X k  if f  (F(i),   v )  i s a n edg e o f Y 
`and  whethe r  (k,   i)  i s a n edg e o f AT* if f (v , F(i))   i s a n edg e o f Y. 
`Improving Backtrack  Search 
`Several technique s ar e usefu l  i n improvin g th e efficienc y  o f backtrac k  searc h 
`[Bittner an d Reingol d 1975] : 
`
`364 
`
`Ch. 11   Matching 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 375
`
`

`

`1.  Branch  pruning.  Al l technique s o f thi s variet y examin e th e curren t partia l solu ­
`tion an d prun e awa y descendent s tha t ar e no t viabl e continuation s o f th e solu ­
`tion. Shoul d non e exist , backtrackin g ca n tak e plac e immediately . 
`2.  Branch   merging.   D o no t searc h  branche s  o f th e solutio n  tre e isomorphi c wit h 
`those alread y searched . 
`3.  Tree  rearrangement  and  reordering.  Give n prunin g capabilities , mor e node s ar e 
`likely t o  b e eliminate d  b y prunin g  i f ther e ar e fewe r  choice s t o mak e earl y i n 
`the searc h  (partia l solutio n  node s o f lo w degre e shoul d  b e hig h  i n th e searc h 
`tree). Similarly , searc h firs t  thos e extension s t o th e curren t solutio n  tha t hav e 
`the fewes t alternatives . 
`4.  Branch  and  bound.   I f a  cos t ma y b e assigne d t o solutions , standar d  technique s 
`such a s heuristi c searc h  an d  th e A * searc h algorith m  [Nilsso n  1980 ]  (Sectio n 
`4.4)  ma y b e employe d  t o allo w th e searc h  t o procee d  o n a  "best­first "  rathe r 
`than a  "depth­first "  basis . 
`
`For extension s o f thes e techniques , se e [Haralic k an d Elliot t 1979] . 
`
`11.3.3  Associatio n Grap h Technique s 
`
`Generalized Structure  Matching 
`A genera l relationa l structur e  "bes t  match " i s les s restricte d  tha n grap h iso ­
`morphism,  becaus e  node s  o r  arc s  ma y  b e  missin g  fro m  on e  o r  th e  othe r  graph . 
`Also, i t i s mor e genera l tha n subgrap h isomorphis m becaus e on e structur e ma y no t 
`be exactl y isomorphi c  t o a  substructur e  o f th e other .  A  mor e genera l  matc h con ­
`sists o f a  se t o f node s fro m  on e structur e an d a  se t o f node s fro m th e othe r an d a  1: 1 
`mapping betwee n the m whic h preserve s th e compatibilitie s o f propertie s an d rela ­
`tions.  I n  othe r  words ,  correspondin g  node s  (unde r  th e  nod e  mapping )  hav e 
`sufficiently  simila r  properties ,  an d  correspondin g  set s  unde r  th e  mappin g  hav e 
`compatible relations . 
`The  tw o relationa l  structure s ma y hav e a  comple x makeu p  tha t  fall s  outsid e 
`the  norma l  purvie w  o f grap h  theory .  Fo r  instance ,  the y  ma y  hav e  parameterize d 
`properties  attache d  t o  thei r  node s  an d  edges .  Th e  definitio n  o f  whethe r  a   nod e 
`matches anothe r  nod e an d whethe r  tw o suc h nod e matche s ar e mutuall y compati ­
`ble  ca n  b e determine d  b y arbitrar y  procedures ,  unlik e th e  muc h  simple r  criteri a 
`used  i n  pur e grap h  isomorphis m  o r  subgrap h  isomorphism ,  fo r  example .  Recal l 
`that th e variou s grap h an d subgrap h isomorphism s rel y heavil y  o n a  1: 1 match , a t 
`least locally , betwee n arc s an d node s o f th e structure s t o b e matched . However , th e 
`idea  o f  a   "bes t  match "  ma y  mak e  sens e  eve n  i n  th e  absenc e  o f  suc h  perfec t 
`correspondences. 
`The association  graph  define d  i n thi s sectio n i s a n auxiliar y dat a structur e pro ­
`duced fro m  tw o relationa l structure s t o b e matched . Th e beaut y o f th e associatio n 
`graph  i s  tha t  i t  is   a  simple ,  pur e  graph­theoreti c  structur e  whic h  i s amenabl e  t o 
`pure graph­theoreti c  algorithm s  suc h  a s cliqu e finding.  Thi s  i s usefu l  fo r  severa l 
`reasons. 
`
`Sec. 77. 3 
`
`Implementing   Graph­Theoretic  
`
`Algorithms 
`
`365 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 376
`
`

`

`• 
`• 
`
`I t take s relationa l structur e matchin g fro m  th e a d ho c t o th e classica l domain . 
`I t  broaden s  th e  bas e o f peopl e wh o ar e producin g  usefu l  algorithm s  fo r struc ­
`ture matching . I f th e rathe r specialize d relationa l structur e matchin g enterpris e 
`is reducibl e t o a  classica l graph­theoretica l  problem ,  the n everyon e workin g o n 
`the classica l proble m i s als o workin g indirectl y o n structur e matching . 
`•  Knowledg e abou t th e computationa l complexit y o f classica l grap h algorithm s il ­
`luminates th e difficult y  o f structur e matching . 
`
`Clique Finding  for   Generalized   Matching 
`Let a  relationa l structur e b e a  se t o f element s  V,  a  se t o f propertie s  (o r mor e 
`simply unar y predicates )  P  define d  ove r th e elements , an d a  se t o f binar y relation s 
`(or binar y predicates ) R  define d  ove r pair s o f th e elements . A n exampl e o f a  grap h 
`representation o f suc h a  structur e i s give n i n Fig . 11.7 . 
`Given  tw o structure s define d  b y  (V\,   P,  R)   an d  (V 2,  P,  R),   sa y tha t  "simi ­
`lar" an d  "compatible " actuall y  mea n  "th e  same. " The n  w e construc t  a n associa ­
`tion grap h  Ga s follow s  [Amble r e t al . 1975] . Fo r eac h  v\  i n  V\  an d  v 2 i n  V 2, con ­
`struct a  nod e o f  G labeled  (vi ,  v 2) i f  v i an d  v 2 hav e th e sam e propertie s  [p(v\)   if f 
`p (v 2)  fo r eac h p  i n Pi . Thu s th e node s o f G  denot e assignments , o r pair s o f nodes , 
`one eac h fro m  V\  an d  V 2, whic h hav e simila r properties . No w connec t  tw o node s 
`(vj,  v 2) an d  (v'i ,  v' 2) o f G  i f the y represen t compatible  assignment s accordin g t o  R, 
`that  is ,  i f th e  pair s satisf y  th e  sam e  binar y  predicate s  [r(v\,   v\)   iff  r(v 2,  v' 2)  fo r 
`each  r'mR]. 
`th e tw o relationa l structures , i s 
`A matc h betwee n  (F lf  P,  R)   an d ( V2,  P,R),  
`just a  se t o f assignment s tha t ar e al l mutuall y compatible . Th e "bes t match " coul d 
`well  b e  take n  t o  b e  th e  larges t  se t  o f  assignment s  (nod e  correspondences )  tha t 
`were al l mutuall y compatibl e unde r  th e relations . Bu t thi s i n th e associatio n grap h 
`G i s jus t  th e  larges t  totall y  connecte d  (completel y  mutuall y  compatible)—se t  o f 
`nodes. I t i s a  clique.   A  cliqu e t o whic h n o ne w node s ma y b e adde d withou t destroy ­
`ing th e cliqu e propertie s i s a  maximal  clique . I n thi s formulatio n  o f matching , large r 
`cliques ar e  take n  t o indicat e  bette r  matches ,  sinc e  the y  accoun t  fo r  mor e  nodes . 
`
`F I R .  11. 7  A   grap h  representatio n  o f a 
`relational  structure .  Element s  (nodes )  v\ 
`and  V 3 hav e  propert y  p i ,  1­ 2 an d  i> 4 hav e 
`property  p2 , an d  th e arc s betwee n  node s 
`indicate  tha t  th e  relatio n  r l  hold s 
`between  i> | an d  i> 2and  betwee n  v 2  an d 
`vh  an d  r 2 hold s  betwee n  v 3 an d  v 4  an d 
`between  v 4and  v j . 
`
`366 
`
`Ch.  11   Matching 
`
`IPR2022-00092 - LGE
`Ex. 1015 - Page 377
`
`

`

`Thus th e bes t matche s ar e determine d b y th e larges t maxima l clique s i n th e associ ­
`ation graph . Figur e 11. 8 show s a n example : Certai n subfeature s  o f th e object s hav e 
`been  selecte d  a s  "primitiv e  elements "  o f  th e  objects ,  an d  appea r  a s node s  (ele ­
`ments)  i n  th e  relationa l  structures .  T o  thes e  node s  ar e  attache d  properties ,  an d 
`between  the m  ca n  exis t  relations .  Th e choic e  o f primitives ,  properties , an d  rela ­
`tions  i s  u p  t o  th e  designe r  o f  th e  representation .  Her e  th e  primitive s  o f  th e 
`representation correspon d t o edge s an d corner s o f th e shape . 
`The  associatio n  grap h  i s  show n  i n  11.8e .  It s  node s  correspon d  t o  pair s  o f 
`nodes, on e eac h fro m  A  an d B , whos e propertie s ar e similar .  [Notic e tha t ther e i s 
`no nod e i n th e associatio n grap h fo r  (6,6')] . Th e arc s o f th e associatio n grap h indi ­
`cate  tha t  th e  endpoint s  o f  th e  ar c  represen t  compatibl e  associations .  Maxima l 
`cliques i n th e associatio n grap h  (show n a s set s o f node s wit h th e sam e shape ) indi ­
`cate set s o f consisten t  associations . Th e larges t  maxima l  cliqu e provide s th e  nod e 
`pairings o f th e "bes t  match. " 
`In  th e exampl e  construction ,  th e associatio n  grap h  i s forme d  b y associatin g 
`nodes wit h exactl y th e sam e propertie s  (actuall y unar y predicates) , an d b y allowin g 
`as  compatibl e  association s  onl y  thos e  wit h  exactl y  th e  sam e  relation s  (actuall y 
`binary predicates) . Thes e condition s ar e eas y t o state , bu t the y ma y no t b e exactl y 
`what i s needed . I n particular ,  i f th e propertie s an d relation s ma y tak e o n range s o f 
`values greate r  tha n  th e binar y  "exists "  an d  "doe s  no t exist, "  the n a  measur e o f 
`similarity  mus t  b e introduce d  t o defin e  whe n  nod e  propertie s ar e simila r  enoug h 
`for association , and~whe n relation s ar e "simila r enough~fo r  ccjnpaTibilityTArbitraril y 
`complex function s  ca n decid e whethe r propertie s an d relation s ar e similar . A s lon g 
`as th e functio n  answer s "yes " o r  "no, "  th e complexit y  o f it s computation s  i s ir ­
`relevant t o th e matchin g algorithm . 
`The followin g recursiv e clique­findin g algorith m build s u p clique s a  nod e a t a 
`time  [Amble r e t al .  1975] . Th e searc h  tre e i t generate s ha s state s tha t ar e ordere d 
`pairs  (se t  o f node s chose n  fo r  a  clique , se t  o f node s availabl e fo r  inclusio n  i n  th e 
`clique). Th e roo t o f th e tre e i s th e stat e  (0 , al l grap h nodes) , an d a t eac h branc h a 
`choice i s mad e whethe r  t o includ e o r no t t o includ e a n eligibl e nod e i n th e clique . 
`(If a  nod e i s eligibl e fo r inclusio n i n cliqu e X,  the n each  cliqu e includin g A"mus t ei ­
`ther includ e th e nod e o r exclud e it) . 
`
`Algorithm 11.2 :  Clique­Findin g  Algorith m 
`Comment Nodes  i s th e se t o f node s i n th e inpu t graph . 
`Comment 
`Cliques (X,  Y)   take s a s argument s a  cliqu e X,  an d  F , a  se t o f node s tha t include s 
`X.  I t return s al l clique s tha t includ e Jan d  ar e include d i n Y. 
`Cliques (0,Nodes ) finds  al l clique s i n th e graph . 
`CliquesiXJ)  :  = 
`// n o nod e i n  Y—X\s  connecte d t o al l element s o f X 
`then {X\ 
`else 
`CliquesUriJ  {y],V)  \J   Clique s (X,  Y­{y}) 
`wherey i s connecte d