Frameworks for Measuring Graph Similarity

• Applicant: Gaurav Rattan, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: from 2018 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 411032549

• Final Report Year: 2022

Final Report Abstract

The design and analysis of graph learning algorithms is currently one of the most important areas of CS research. The insights from several fields of theoretical CS have been central to the progress in this field, in particular, the fields of graph theory, logic, complexity and optimization. The main goals of this project were to (a) identify and establish the role of homomorphism/subgraph numbers as an important graph parameter towards building a theory of graph similarity, and (b) utilize these insights to develop novel learning algorithms for graph-structured data. The important results of this project are the following: 1) We developed novel connections between homomorphism counting and spectra of graph matrices. This paves way for a simultaneous understanding of convolutional and spectral methods in graph learning. 2) We developed the general framework of Homomorphism Tensors, thus unifying several disparate results on homomorphism numbers and graph similarity. 3) We designed novel graph learning algorithms, which operate in a manner so as to count certain restricted kind of homomorphisms, thus achieving better scalability compared to standard algorithms. 4) We developed the framework of Ordered Subgraph Aggregation, which unified several adhoc results on how to use subgraph information for better learning on graphs.

Publications

• The Complexity of Homomorphism Indistinguishability. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2019, August 26-30, 2019, Aachen, Germany. LIPIcs, 138, 54:1–54:13.
  Jan Böker, Yijia Chen, Martin Grohe & Gaurav Rattan
  
• Weisfeiler and Leman go Sparse: Towards Scalable Higher-Order Graph Embeddings. Annual Conference on Neural Information Processing Systems (NeurIPS) 2020, December 6-12, 2020
  Christopher Morris, Petra Mutzel & Gaurav Rattan
  
• Weisfeiler and Leman go Sparse: Towards Scalable Higher-Order Graph Embeddings. Graph Representation Learning and Beyond (GRL+), ICML 2020.
  Christopher Morris, Petra Mutzel & Gaurav Rattan
  
• Homomorphism Tensors and Linear Equations. Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP) 2022, July 4-8, Paris, France. 70:1–70:20, LIPIcs
  Martin Grohe, Gaurav Rattan & Tim Seppelt
  
• Ordered Subgraph Aggregation Networks. Advances in Neural Information Processing Systems (NeurIPS), 2022.
  Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert & Christopher Morris
  
• Recent Advances in Homomorphism Indistinguishability. Structure Meets Power, ICALP 2022.
  Gaurav Rattan & Tim Seppelt
  
• SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks. Geometrical and Topological Representation Learning (GT-RL), ICLR 2022.
  Christopher Morris, Gaurav Rattan, Sandra Kiefer & Siamak Ravanbaksh
  
• SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks. Proceedings of the 39th International Conference on Machine Learning (ICML) 2022, July 17–23, Baltimore, USA. PMLR 162:16017-16042.
  Christopher Morris, Gaurav Rattan, Sandra Kiefer & Siamak Ravanbaksh