Prof. Dr. Emmanuel Müller

Course description

Graphs have been lately rediscovered as a highly versatile model for many practical scenarios such as social analysis, biology, transport systems, and smart cities. A graph is an abstract representation of a network in terms of nodes and relationships between them (edges) and can be used to model behaviours of individuals or objects interacting one another.

Due to the large interest in graphs many methods have been proposed to retrieve relevant information from them and to extract non trivial patterns with methods that bridges data mining, machine learning and graph theory. As a parallel with traditional data (text or tabular) graph mining studies ways to extract patterns, infer behaviours, retrieve rules, querying, predict links, finding communities and many other things.

The course is intended to provide an introduction to the broad and rising topic of graph mining, with a focus on challenges, algorithmic solutions and new problems.

The course will be organized as follows:

  • Background concepts:
    • probability theory/statistics
    • basic linear algebra
    • basic graph concepts (morphisms, degrees, representations, ...)
  • Database methods:
    • Graph querying: exact and approximate - Reachability queries
    • Frequent subgraph mining and graph indexing
  • Unsupervised methods:
    • Community and anomaly detection
    • Graph summarization
  • Supervised methods:
    • Predictions: node classification and link prediction
    • Recommender systems

In addition, through a practical project the student will be able to exploit graph techniques on real world graph data to understand the practical applicability and the drawbacks of the algorithms studied during the course.


  • [February 10] 16.00 - 18.00, Knowledge Discovery and Data Mining open day
  • New and exciting theses from the Knowledge Discovery and Data Mining group
  • [Feb 26,27,28] Oral exam, 9.30 - 15.00
  • [Oct 26] The project requirements have been published. Mind the important dates, the report template can be found in this page  tiny.cc/GMREP
  • [Oct 21] Welcome to the graph mining course! Please enroll in the course as usual and send an email to me to notify the enrollment and add you into the mailing-list. If you want to subscribe to the mailing list manually, please visit the page: https://lists.hpi.uni-potsdam.de/listinfo/graphmining-ws1718

Expected Course Schedule

18.10Introduction to graph miningslides fundamentals
25.10Graph mining frameworks - Project Assignmentslides fundamentals
01.11Basic concepts - Graphs and linear algebra

linear algebra

08.11Node similarity and classification [first part] slides supervised
15.11Node similarity and classification [second part]slidespagerank supervised
22.11Link predictionslides supervised
29.11Non overlapping communities [first part]slides unsupervised
06.12Non overlapping communities [second part]slides unsupervised
13.12Overlapping communitiesslides unsupervised
20.12Graph models and embeddingsslides unsupervised
27.12Christmas break   
03.01Christmas break   
10.01Graph queriesslides database
17.01Frequent subgraph miningslides database
24.01Graph indexingslides database
31.01Student project presentation [first part]   
07.02Student project presentation [second part]   


The course marks will be distributed among an oral exam at the end and practical project with the following scheme. 

  • 30% Practical project and results presentation
  • 70% Oral exam

The oral exam is solely based on the material presented during the course EXCLUDING any extra material but it might involve initial questions about the project.


During the course there will be assigned a small project, for which a report and an in-class presentation will be required. 

More details to come. 

Course Material

For this course there is no official book. All the material, including slides, references, and videos, will be posted in the official page or in the intranet. However, the following, incomplete, list, can be used as complementary material: 

  • Aggarwal, C.C. and Wang, H. eds., 2010.Managing and mining graph data (Vol. 40). New York: Springer.
  • Chakrabarti, D. and Faloutsos, C., 2012. Graph mining: laws, tools, and case studies. Synthesis Lectures on Data Mining and Knowledge Discovery7(1), pp.1-207.
  • Easley, D. and Kleinberg, J., 2010. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press.
  • Rehman, S.U., Khan, A.U. and Fong, S., 2012, August. Graph mining: A survey of graph mining techniques. In Digital Information Management (ICDIM), 2012 Seventh International Conference on (pp. 88-92). IEEE.

Additional material

Linear algebra

Node classification

Link prediction

Community detection