Partial Recovery in the Graph Alignment Problem

References

• Abbe E (2017) Community detection and stochastic block models: Recent developments. J. Machine Learn. Res. 18(1):6446–6531.Google Scholar
• Almohamad H, Duffuaa SO (1993) A linear programming approach for the weighted graph matching problem. IEEE Trans. Pattern Anal. Machine Intelligence 15(5):522–525.Crossref, Google Scholar
• Banerjee S, Hegde N, Massoulié L (2012) The price of privacy in untrusted recommendation engines. 50th Annual Allerton Conf. Comm. Control Comput. (Allerton) (IEEE), 920–927.Google Scholar
• Barak B, Chou CN, Lei Z, Schramm T, Sheng Y (2018) (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. Preprint, submitted May 7, https://arxiv.org/abs/1805.02349.Google Scholar
• Bayati M, Gleich DF, Saberi A, Wang Y (2013) Message-passing algorithms for sparse network alignment. ACM Trans. Knowledge Discovery Data 7(1):1–31.Crossref, Google Scholar
• Bollobás B (1982) Distinguishing vertices of random graphs. North-Holland Math. Stud. 62:33–49.Crossref, Google Scholar
• Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. Internat. J. Pattern Recognition Artificial Intelligence 18(3):265–298.Crossref, Google Scholar
• Cover TM, Thomas JA (2012) Elements of Information Theory (John Wiley & Sons, United Kingdom).Google Scholar
• Cullina D, Kiyavash N (2016) Improved achievability and converse bounds for Erdös-Rényi graph matching. Performance Evaluation Rev. 44(1):63–72.Crossref, Google Scholar
• Cullina D, Kiyavash N (2017) Exact alignment recovery for correlated Erdös-Rényi graphs. Preprint, submitted November 18, https://arxiv.org/abs/1711.06783.Google Scholar
• Cullina D, Kiyavash N, Mittal P, Poor HV (2019) Partial recovery of Erdös-Rényi graph alignment via k-core alignment. Proc. ACM Measurement and Analysis of Comput. Systems 3(3):1–21.Google Scholar
• Czajka T, Pandurangan G (2008) Improved random graph isomorphism. J. Discrete Algorithms 6(1):85–92.Crossref, Google Scholar
• Dai OE, Cullina D, Kiyavash N, Grossglauser M (2018) On the performance of a canonical labeling for matching correlated Erdös-Rényi graphs. Preprint, submitted April 25, https://arxiv.org/abs/1804.09758.Google Scholar
• Ding J, Ma Z, Wu Y, Xu J (2021) Efficient random graph matching via degree profiles. Probab. Theory Related Fields 179(1):29–115.Google Scholar
• Dym N, Maron H, Lipman Y (2017) Ds++: A flexible, scalable and provably tight relaxation for matching problems. ACM Transactions on Graphics (TOG) 36(6):1–14.Google Scholar
• Elmsallati A, Clark C, Kalita J (2015) Global alignment of protein-protein interaction networks: A survey. IEEE/ACM Trans. Comput. Biol. Bioinformatics 13(4):689–705.Crossref, Google Scholar
• Fan Z, Mao C, Wu Y, Xu J (2019a) Spectral graph matching and regularized quadratic relaxations I: The Gaussian model. Preprint, submitted July 20, https://arxiv.org/abs/1907.08880.Google Scholar
• Fan Z, Mao C, Wu Y, Xu J (2019b) Spectral graph matching and regularized quadratic relaxations II: Erdös-Rényi graphs and universality. Preprint, submitted July 20, https://arxiv.org/abs/1907.08883.Google Scholar
• Feizi S, Quon G, Mendoza M, Medard M, Kellis M, Jadbabaie A(2019) Spectral alignment of graphs. IEEE Trans. Network Sci. Engrg. 7(3):1182–1197Crossref, Google Scholar
• Fishkind DE, Adali S, Patsolic HG, Meng L, Lyzinski V, Priebe CE(2012) Seeded graph matching. Preprint, submitted September 3, https://arxiv.org/abs/1209.0367.Google Scholar
• Fogel F, Jenatton R, Bach F, d’Aspremont A (2013) Convex relaxations for permutation problems. Adv. Neural Inform. Processes Systems 26:1016–1024.Google Scholar
• Ganassali L, Massoulié L (2020) From tree matching to sparse graph alignment. Conf. Learn. Theory (PMLR).Google Scholar
• Kazemi E, Hassani SH, Grossglauser M (2015a) Growing a graph matching from a handful of seeds. Proc. VLDB Endowment 8(10):1010–1021.Crossref, Google Scholar
• Kazemi E, Yartseva L, Grossglauser M (2015b) When can two unlabeled networks be aligned under partial overlap? 53rd Annual Allerton Conf. Comm. Control Comput. (IEEE), 33–42.Google Scholar
• Kezurer I, Kovalsky SZ, Basri R, Lipman Y (2015) Tight relaxation of quadratic matching. Comput. Graphics Forum 34(5):115–128.Crossref, Google Scholar
• Kuchaiev O, Milenković T, Memišević V, Hayes W, Pržulj N (2010) Topological network alignment uncovers biological function and phylogeny. J. Roy. Soc. Interface 7(50):1341–1354.Crossref, Google Scholar
• Lacoste-Julien S, Taskar B, Klein D, Jordan MI (2006) Word alignment via quadratic assignment. Proc. Main Conf. Human Language Tech. Conf. North Amer. Chapter Assoc. Comput. Linguistics (Association for Computational Linguistics), 112–119.Google Scholar
• Lyzinski V, Fishkind D, Fiori M, Vogelstein J, Priebe C, Sapiro G(2016) Graph matching: Relax at your own risk. IEEE Trans. Pattern Anal. Machine Intelligence 38(1):60–73.Crossref, Google Scholar
• MacCartney B, Galley M, Manning CD (2008) A phrase-based alignment model for natural language inference. Proc. Conf. Empirical Methods Natural Language Processing (Association for Computational Linguistics), 802–811.Google Scholar
• Malod-Dognin N, Pržulj N (2015) L-GRAAL: Lagrangian graphlet-based network aligner. Bioinformatics 31(13):2182–2189.Crossref, Google Scholar
• Mossel E, Xu J (2019) Seeded graph matching via large neighborhood statistics. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM), 1005–1014.Google Scholar
• Narayanan A, Shmatikov V (2006) How to break anonymity of the Netflix prize data set. Preprint, submitted October 18, https://arxiv.org/abs/cs/0610105.Google Scholar
• Narayanan A, Shmatikov V (2009) De-anonymizing social networks. 2009 30th IEEE Sympos. Security Privacy (IEEE), 173–187.Google Scholar
• Pedarsani P, Grossglauser M (2011) On the privacy of anonymized networks. Proc. 17th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining, 1235–1243.Google Scholar
• Pittel B, Spencer J, Wormald N (1996) Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67(1):111–151.Crossref, Google Scholar
• Read RC, Corneil DG (1977) The graph isomorphism disease. J. Graph Theory 1(4):339–363.Crossref, Google Scholar
• Rendl F, Pardalos P, Wolkowicz H (1994) The quadratic assignment problem: A survey and recent developments. Proc. DIMACS Workshop Quadratic Assignment Problems, vol. 16, 1–42.Google Scholar
• Sahni S, Gonzalez T (1976) P-complete approximation problems. J. ACM 23(3):555–565.Crossref, Google Scholar
• Santhanam NP, Wainwright MJ (2012) Information-theoretic limits of selecting binary graphical models in high dimensions. IEEE Trans. Inform. Theory 58(7):4117–4134.Crossref, Google Scholar
• Sason I, Verdú S (2016) f-divergence inequalities. IEEE Trans. Inform. Theory 62(11):5973–6006.Crossref, Google Scholar
• Scheinerman ER, Ullman DH (2011) Fractional Graph Theory: A Rational Approach to the Theory of Graphs (Courier Corporation).Google Scholar
• Schellewald C, Schnörr C (2005) Probabilistic subgraph matching based on convex relaxation. Internat. Workshop Energy Minimization Methods Comput. Vision Pattern Recognition (Springer), 171–186.Google Scholar
• Shirani F, Garg S, Erkip E (2018) Typicality matching for pairs of correlated graphs. 2018 IEEE Internat. Sympos. Inform. Theory (IEEE), 221–225.Google Scholar
• Singh R, Xu J, Berger B (2008) Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc. Natl. Acad. Sci. USA 105(35):12763–12768.Crossref, Google Scholar
• Umeyama S (1988) An eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Machine Intelligence 10(5):695–703.Crossref, Google Scholar
• Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, Fishkind DE, Vogelstein RJ, Priebe CE (2015) Fast approximate quadratic programming for graph matching. PLoS One. 10(4):e0121002.Crossref, Google Scholar
• Wright EM (1971) Graphs on unlabelled nodes with a given number of edges. Acta Math. 126:1–9.Crossref, Google Scholar
• Wu Y, Xu J, Yu SH (2022) Settling the sharp reconstruction thresholds of random graph matching. IEEE Transactions Inform. Theory 68(8):5391–5417.Google Scholar
• Yartseva L, Grossglauser M (2013) On the performance of percolation graph matching. Proc. First ACM Conf. Online Social Networks (ACM), 119–130.Google Scholar
• Zaslavskiy M, Bach F, Vert JP (2008) A path following algorithm for the graph matching problem. IEEE Trans. Pattern Anal. Machine Intelligence 31(12):2227–2242.Crossref, Google Scholar
• Zhang S, Yang J, Jin W (2010) Sapper: Subgraph indexing and approximate matching in large graphs. Proc. VLDB Endowment 3(1–2):1185–1194.Crossref, Google Scholar
• Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2(1):71–109.Crossref, Google Scholar