Techniken zum Messen von Ähnlichkeiten zwischen Graphen

• Antragsteller: Gaurav Rattan, Ph.D.
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 411032549

• Erstellungsjahr: 2022

Zusammenfassung der Projektergebnisse

Das Design und die Analyse von Graphen-Lernalgorithmen ist derzeit einer der wichtigsten Bereiche der CS-Forschung. Die Erkenntnisse aus mehreren Bereichen der theoretischen Informatik waren für den Fortschritt auf diesem Gebiet von zentraler Bedeutung, insbesondere aus den Bereichen Graphentheorie, Logik, Komplexität und Optimierung. Die Hauptziele dieses Projekts bestanden darin, (a) die Rolle von Homomorphismus/Untergraphenzahlen als wichtigen Graphenparameter beim Aufbau einer Theorie der Graphenähnlichkeit zu identifizieren und zu etablieren und (b) diese Erkenntnisse zu nutzen, um neuartige Lernalgorithmen für graphenstrukturierte Graphen zu entwickeln Daten. Das Projekt war in der Tat an beiden Fronten erfolgreich. Die wichtigsten Ergebnisse dieses Projekts sind die folgenden: 1) Wir haben neue Verbindungen zwischen dem Zählen von Homomorphismen und den Spektren von Graphen entwickelt und damit den Weg für ein gleichzeitiges Verständnis von Faltungs- und Spektralmethoden beim Graphenlernen geebnet. 2) Wir haben den allgemeinen Rahmen von Homomorphismus-Tensoren entwickelt und damit mehrere unterschiedliche Ergebnisse zu Homomorphismuszahlen und Graphenähnlichkeit vereint. 3) Wir haben neuartige Graph-Lernalgorithmen entwickelt, die so arbeiten, dass sie bestimmte eingeschränkte Arten von Homomorphismen zählen und somit eine bessere Skalierbarkeit im Vergleich zu Standardalgorithmen erreichen. 4) Wir haben das Framework der Ordered Subgraph Aggregation entwickelt, das mehrere Ad-hoc-Ergebnisse zur Verwendung von Subgraph-Informationen für ein besseres Lernen in Graphen vereinheitlichte.

Projektbezogene Publikationen (Auswahl)

• 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