This is an old revision of the document!
Nils Kriege
| Room: | 237 |
| Phone: | +49 231 755-7737 |
| Fax: | +49 231 755 7740 |
| E-Mail: | nils.kriege tu-dortmund.de |
Research Interests
- Combinatorial Optimization, Graph Algorithms
- Data Mining, Machine Learning with Graphs
- Information Visualization, Visual Analytics
- Applications in Cheminformatics
Teaching (in German)
Lehrveranstaltung
- Sommersemester 2018
- Seminar Algorithm Engineering
- Wintersemester 2017/18
- Sommersemester 2017
- Seminar Algorithm Engineering
- Wintersemester 2016/17
- Fachprojekt Algorithm Engineering for Graph Data Mining
- Proseminar Algorithms Unplugged
- Sommersemester 2016
- Proseminar Klassische Probleme der Graphentheorie
- Seminar Graph Data Mining
- Seminar Algorithm Engineering
- Wintersemester 2015/16
- Übung zu Einführung in die Programmierung
- Sommersemester 2015
- Seminar Algorithm Engineering
- Wintersemester 2014/15
- Übung zu Mathematik für Informatiker 1
- Seminar Algorithm Engineering
- Sommersemester 2014
- Wintersemester 2013/14
- Seminar Algorithm Engineering
- Sommersemester 2013
- Seminar Algorithm Engineering
- Wintersemester 2012/13
- Seminar Algorithm Engineering
- Sommersemester 2012
- Seminar Algorithm Engineering mit Schwerpunkt Graph Data Mining
- Sommersemester 2011
- PG 552: Drug Hunting - Navigation und visuelle Analyse im pharmakologischen Strukturraum
- Fachprojekt Algorithm Engineering
- Wintersemester 2010/11
- PG 552: Drug Hunting - Navigation und visuelle Analyse im pharmakologischen Strukturraum
- Seminar Algorithm Engineering
- Sommersemester 2010
- Seminar Graphenalgorithmen
Betreute studentische Arbeiten
- Mohamad Reza Nirumand Alankesh: Extending SplineCNN by Structural Graph Features for Cheminformatics, Bachelorarbeit, 2018.
- Robert Gehde: Erweiterung von Pharmakophor-basierten Fingerprints mittels Randomisierung, Bachelorarbeit, 2018.
- Lutz Oettershagen: On the Crossing Number of Almost Bishellable Drawings of Complete Graphs, Masterarbeit, 2017.
- Christine Dahn: Entwicklung eines Max-Cut-Algorithmus für fast-planare Graphen, Masterarbeit, 2017
- Franka Bause: Approximation der Editierdistanz für Graphen in linearer Zeit, Bachelorarbeit, 2017
- Martin Rentz: Approximative Algorithmen für das Assignment-Problem mit Hilfe von hierarchischem Clustering, Bachelorarbeit, 2017
- Jonas Ellert: Matchings in bipartiten Graphen im Semi-Streaming Modell, Bachelorarbeit, 2016
- Christopher Osthues: Experimenteller Vergleich von Labeling-Verfahren für Graphkerne, Bachelorarbeit, 2016
- David Schoen: Dynamische Layoutverfahren für semantische Molekülwolken, Diplomarbeit, 2015
- Markus Kloß: An output sensitive algorithm for enumerating all maximal common subgraphs, Studienarbeit, 2014
- Andre Droschinsky: Effiziente Enumerationsalgorithmen für Common Subtree Probleme, Diplomarbeit, 2014
- Florian Kurpicz: Efficient algorithms for the maximum common subgraph problem in partial 2-trees, Masterarbeit 2014
- Fabian Weißberg: Verfeinerung bitvektorbasierter Filterverfahren zur Substruktursuche in Molekülgraphdatenbanken, Bachelorarbeit, 2013
- Henning Garus: Interactive Visualization of Molecular Scaffold Networks, Diplomarbeit, 2012
- Patrick Baron: Integration ausgewählter Analyseverfahren für Affiliation-Netzwerke in Cytoscape, Bachelorarbeit, 2012
- Till Schäfer: Beschleunigung hierarchischer Clusterverfahren für allgemeine metrische Distanzmaße, Diplomarbeit, 2012
- Marianna D'Addario: Entwurf von Oligonukleotid-Bibliotheken für die DNA-Nanotechnologie, Diplomarbeit (Kooperation mit Prof. Rahmann und Prof. Niemeyer, Chemie), 2011
Projects
- Scaffold Hunter – A tool for the analysis and exploration of chemical space
- Google Summer of Code 2014: Mentoring project Molecule Cloud
- Google Summer of Code 2013: Mentoring project Tree Maps
- Benchmark Data Sets for Graph Kernels – A collection of graph data sets with class labels for benchmarking purposes
- Resource efficient analysis of graphs – Collaborative Research Center Providing Information by Resource-Constrained Data Analysis (SFB 876)
- Graph-Based Methods for Rational Drug Design – DFG Priority Programme Algorithms for Big Data (SPP 1736)
- Planarization Approaches in Automatic Graph Drawing – DFG Priority Programme Algorithm Engineering (SPP 1307)
Publications
Preprints
- Protein Complex Similarity based on Weisfeiler-Lehman labeling
Bianca K. Stöcker, Till Schäfer, Petra Mutzel, Johannes Köster, Nils Kriege, Sven Rahmann
PeerJ Preprints, vol. 6, e26612v1, 2018.
- A Unifying View of Explicit and Implicit Feature Maps for Structured Data: Systematic Studies of Graph Kernels
Nils M. Kriege, Marion Neumann, Christopher Morris, Kristian Kersting, Petra Mutzel,arXiv:1703.00676.
- A general purpose algorithm for counting simple cycles and simple paths of any length
Pierre-Louis Giscard, Nils Kriege, Richard C. Wilson,arXiv:1612.05531.
- A note on block-and-bridge preserving maximum common subgraph algorithms for outerplanar graphs
Nils M. Kriege, Andre Droschinsky, Petra Mutzel,arXiv:1805.10754.
Journal Articles
- On Maximum Common Subgraph Problems in Series-Parallel Graphs (Preprint arXiv:1708.02772)
Nils Kriege, Florian Kurpicz, Petra Mutzel
European Journal on Combinatorics (EJC), vol. 68, 79-95, 2018.
- Scaffold Hunter: A comprehensive visual analytics framework for drug discovery
Till Schäfer, Nils Kriege, Lina Humbeck, Karsten Klein, Oliver Koch, Petra Mutzel
Journal of Cheminformatics, 9:28, 2017.
- Practical SAHN Clustering for Very Large Data Sets and Expensive Distance Metrics
Nils Kriege, Petra Mutzel, Till Schäfer
Journal of Graph Algorithms and Applications (JGAA), vol. 18, no. 4, 577-602, 2014.
- Visual Analysis of Biological Activity Data with Scaffold Hunter
Karsten Klein, Oliver Koch, Nils Kriege, Petra Mutzel, Till Schäfer
Molecular Informatics, WILEY-VCH Verlag, 32, 964-975, 2013.
Refereed Conference Proceedings
- Largest Weight Common Subtree Embeddings with Distance Penalties (Preprint arXiv:1805.00821)
Andre Droschinsky, Nils M. Kriege, Petra Mutzel
International Symposium on Mathematical Foundations of Computer Science (MFCS) 2018, accepted.
- A Property Testing Framework for the Theoretical Expressivity of Graph Kernels
Nils M. Kriege, Christopher Morris, Anja Rey, Christian Sohler
International Joint Conference on Artificial Intelligence and European Conference on Artificial Intelligence (IJCAI-ECAI) 2018, 2348-2354.
- A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs (Preprint arXiv:1803.10983)
Christine Dahn, Nils M. Kriege, Petra Mutzel
International Workshop on Combinatorial Algorithms (IWOCA) 2018, accepted.
- Recognizing Cuneiform Signs Using Graph Based Methods (Preprint arXiv:1802.05908)
Nils M. Kriege, Matthias Fey, Denis Fisseler, Petra Mutzel, Frank Weichert
International Workshop on Cost-Sensitive Learning (COST), SIAM International Conference on Data Mining (SDM) 2018, accepted.
- Recent Advances in Kernel-Based Graph Classification
Nils M. Kriege, Christopher Morris
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) 2017, 388-392.
- Finding Largest Common Substructures of Molecules in Quadratic Time (Preprint arXiv:1610.08739)
Andre Droschinsky, Nils Kriege, Petra Mutzel
43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-FOCS) 2017, 309-321.
- Faster Kernels for Graphs with Continuous Attributes via Hashing (Preprint arXiv:1610.00064, Source code)
Christopher Morris, Nils M. Kriege, Kristian Kersting, Petra Mutzel
IEEE International Conference on Data Mining (ICDM) 2016, 1095-1100.
- On Valid Optimal Assignment Kernels and Applications to Graph Classification (Preprint arXiv:1606.01141, Source code)
Nils M. Kriege, Pierre-Louis Giscard, Richard C. Wilson
Advances in Neural Information Processing Systems (NIPS) 2016, 1615-1623.
- Faster Algorithms for the Maximum Common Subtree Isomorphism Problem (Preprint arXiv:1602.07210)
Andre Droschinsky, Nils M. Kriege, Petra Mutzel
International Symposium on Mathematical Foundations of Computer Science (MFCS) 2016, 33:1-33:14.
- Explicit versus Implicit Graph Feature Maps: A Computational Phase Transition for Walk Kernels
Nils Kriege, Marion Neumann, Kristian Kersting, Petra Mutzel
International Conference on Data Mining (ICDM) 2014, 881-886.
- Enumeration of Maximum Common Subtree Isomorphisms with Polynomial-Delay
Andre Droschinsky, Bernhard Heinemann, Nils Kriege, Petra Mutzel
International Symposium on Algorithms and Computation (ISAAC) 2014, 81-93.
- On Maximum Common Subgraph Problems in Series-Parallel Graphs
Nils Kriege, Florian Kurpicz, Petra Mutzel
International Workshop on Combinatorial Algorithms (IWOCA) 2014, 200-212.
- Finding Maximum Common Biconnected Subgraphs in Series-Parallel Graphs
Nils Kriege, Petra Mutzel
International Symposium on Mathematical Foundations of Computer Science (MFCS) 2014, 505-516.
- The Landscape Metaphor for Visualization of Molecular Similarities
Martin Gronemann, Michael Jünger, Nils Kriege, Petra Mutzel
in: Battiato, S.; Coquillart, S.; Laramee, R. S.; Kerren, A. & Braz, J. (Eds.), Computer Vision, Imaging and Computer Graphics. Theory and Application; Communications in Computer and Information Science, 2014, 458, 85-100.
- SAHN Clustering in Arbitrary Metric Spaces Using Heuristic Nearest Neighbor Search
Nils Kriege, Petra Mutzel, Till Schäfer
International Workshop on Algorithms and Computation (WALCOM) 2014, 90-101.
- Scaffold Hunter: Facilitating Drug Discovery by Visual Analysis of Chemical Space
Karsten Klein, Nils Kriege, Petra Mutzel
in: G. Csurka, M. Kraus, R. Laramee, P. Richard, J. Braz (Eds.), Computer Vision, Imaging and Computer Graphics. Theory and Application; Communications in Computer and Information Science, 2013, 359, 176-192.
- MolMap - Visualizing Molecule Libraries as Topographic Maps
Martin Gronemann, Michael Jünger, Nils Kriege, Petra Mutzel
International Conference on Information Visualization Theory and Applications (IVAPP) 2013, 537-541, Best Paper Award.
- Designing q-Unique DNA Sequences with Integer Linear Programs and Euler Tours in De Bruijn Graphs
Marianna D'Addario, Nils Kriege, Sven Rahmann
German Conference on Bioinformatics (GCB) 2012, Jena, Germany, 82-92.
- Subgraph Matching Kernels for Attributed Graphs (arXiv.org, Source code)
Nils Kriege, Petra Mutzel
International Conference on Machine Learning (ICML) 2012.
- Scaffold Hunter - Visual Analysis of Chemical Compound Databases
Karsten Klein, Nils Kriege, Petra Mutzel
International Conference on Information Visualization Theory and Applications (IVAPP) 2012, 626-635, Best Paper Award.
- CT-Index: Fingerprint-based Graph Indexing Combining Cycles and Trees (Software)
Karsten Klein, Nils Kriege, Petra Mutzel
in: Proceedings of the 27th International Conference on Data Engineering (ICDE) 2011, Hannover, Germany, 1115-1126.
Posters
- Evaluation and Application of a Graph-based Method for Rational Drug Design
Lina Humbeck, Andre Droschinsky, Till Schäfer, Nils Kriege, Petra Mutzel, Oliver Koch
German Conference on Chemoinformatics, 2017.
- Chemogenomics analysis of small molecule bioactivity data: Privileged scaffolds and conserved structural elements in proteins
Lina Humbeck, Till Schäfer, Nils Kriege, Petra Mutzel, Oliver Koch
International Conference on Chemical Structures / German Conference on Chemoinformatics, Noordwijkerhout, The Netherlands, 2014.
- Scaffold Hunter: Visual Analysis of Biological Activity Data
Karsten Klein, Oliver Koch, Nils Kriege, Petra Mutzel, Till Schäfer
German Conference on Chemoinformatics, Fulda, Germany, 2013
Journal of Cheminformatics 2014, 6(Suppl 1):P33.
- Algorithm Engineering für Probleme aus der Chemieinformatik
Nils M. Kriege
Informatik Ruhr: Doktorandenkolleg, Valbert, Germany, 2011.
- Scaffold Hunter - Interactive Exploration of Chemical Space
Karsten Klein, Nils Kriege, Petra Mutzel, Herbert Waldmann, Stefan Wetzel
in: D. Eppstein, E. Gansner (Eds.), 17th Symposium on Graph Drawing 2009, Chicago
Lecture Notes in Computer Science 5849, 2010, 426-427.
Technical Reports
- SAHN Clustering in Arbitrary Metric Spaces Using Heuristic Nearest Neighbor Search
Nils Kriege, Petra Mutzel, Till Schäfer
in: Algorithm Engineering Reports, TR13-1-003, Fakultät für Informatik, TU Dortmund, 2013.
Theses
- Comparing Graphs: Algorithms & Applications (Erratum)
Nils Morten Kriege
PhD Thesis, TU Dortmund, 2015.
- Erweiterte Substruktursuche in Moleküldatenbanken und ihre Integration in Scaffold Hunter
Nils Kriege
in: Algorithm Engineering Reports, TR10-1-001, Fakultät für Informatik, TU Dortmund, 2010.
Diploma Thesis, TU Dortmund, December 2009.
Tutorials & Invited Talks
Tutorials
- Using Scaffold Hunter for the Visual Analysis of Chemical Datasets
Nils Kriege, Till Schäfer, Hands-on Workshops, OpenTox Euro 2013, Mainz, Best Software Award
Invited Talks
- Visual Analysis of Chemical Space with Scaffold Hunter
Nils Kriege, OpenTox Euro 2013, Mainz
- Engineering Graph Algorithms for Cheminformatics
Martin Gronemann, Michael Jünger, Nils Kriege, Petra Mutzel
SPP Algorithm Engineering Annual Meeting 2012, Frankfurt (Main)