Graph Mining (Wintersemester 2017/2018)

Lecturer:
Course Website: https://hpi.de/en/mueller/lehre/aktuelle-vorlesung/ws-1718/graph-mining.html

General Information

• Weekly Hours: 2
• Credits: 3
• Graded: yes
• Enrolment Deadline: 27.10.2017
• Teaching Form: Lecture
• Enrolment Type: Compulsory Elective Module
• Maximum number of participants: 15

Programs, Module Groups & Modules

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.

Requirements

The course has no prerequisites, although a basic knowledge in data mining, statistics and linear algebra would be beneficial. All the basic and advanced aspects and algorithms will be covered during the course. Basic programming skills are also required for the project. 

Literature

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 Discovery, 7(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.

Examination

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.

Zurück