Hasso-Plattner-Institut
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.

News

  • [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

Day Topic Material Extra Type
18.10 Introduction to graph mining slides   fundamentals
25.10 Graph mining frameworks - Project Assignment slides   fundamentals
01.11 Basic concepts - Graphs and linear algebra

linear algebra
graphs

  fundamentals
08.11 Node similarity and classification [first part]  slides   supervised
15.11 Node similarity and classification [second part]slides pagerank  supervised
22.11 Link predictionslides   supervised
29.11 Non overlapping communities [first part] slides   unsupervised
06.12 Non overlapping communities [second part] slides   unsupervised
13.12 Overlapping communities slides   unsupervised
20.12 Graph summarization and graph embeddings slides   unsupervised
27.12 Christmas break      
03.01 Christmas break      
10.01 Graph queries slides   database
17.01 Frequent subgraph mining slides   database
24.01 Graph indexing slides   database
31.01 Student project presentation [first part]      
07.02 Student project presentation [second part]      

Grading

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.

Assignments

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