Fall 2020, M2177.003000 Advanced Data Mining

Seoul National University
M2177.003000 Advanced Data Mining
Fall 2020 - U Kang

News and Announcements

Sep. 2: The class starts.

Course Information

Data mining attracted much interests as an essential tool for big data analysis. Especially, designing and implementing advanced data mining algorithms and analysis platforms play crucial roles in extracting executable knowledges from big data. This course covers advanced data mining techniques, algorithms, and core platforms for big data analysis. This course also covers the techniques to effectively analyze very large data and high-speed data.

A very important aspect of this course is the course project. Students will pick an interesting data mining project, and do data mining researches on the topic. At the end of the course, students will learn how to do interesting researches in data mining, and how to write good papers.

Instructor: U Kang (ukang at snu.ac.kr)
- 301-502
- Office hours: Monday 14:30-15:30 (also, by appointment)
TA:
- Minyong Cho (chominyong@gmail.com), 301-5th floor, office hours: Monday 16:00-17:00
Class meets: Mon, Wed 17:00~18:15, 301-203
URL of this web page: http://datalab.snu.ac.kr/~ukang/courses/20F-ADM

Schedule

Date		Topic	Due
Sep.	2	Course introduction
	7	Graph-1: basics and diameter (Optional Reading) J. Leskovec, J. Kleinberg, C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. ACM SIGKDD, 2005.
	9	Graph-2: models for graphs (Mandatory Reading) A.L Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286, 1999. (Optional Reading) R. Albert, H. Jeong, A.L. Barabasi, Error and attack tolerance of complex networks . U Kang, Mary McGlohon, Leman Akoglu, and Christos Faloutsos, Patterns on the Connected Components of Terabyte-Scale Graphs, IEEE International Conference on Data Mining (ICDM) 2010, Sydney, Australia.	Hw1
	14	Graph-3: power law (Mandatory Reading) M. Faloutsos, P. Faloutsos, C. Faloutsos. On Power-Law Relationships of the Internet Topology. SIGCOMM, 1999. (Optional Reading) Mark E.J. Newman: Power laws, Pareto distributions and Zipf's law, Contemporary Physics 46, 323-351 (2005),	Hw2
	16	Graph-4: structure analysis (Optional Reading) U Kang, Charalampos E. Tsourakakis, Ana Paula Appel, Christos Faloutsos, and Jure Leskovec, Radius Plots for Mining Tera-byte Scale Graphs: Algorithms, Patterns, and Observations, SIAM International Conference on Data Mining (SDM) 2010, Columbus, Ohio, USA.
	21	Spectral analysis-1: random walk (Optional Reading) Peter G. Doyle and J. Laurie Snell, Random walks and electric networks, July 2006
	23, 28	Spectral analysis-2: link analysis (Mandatory Reading) J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. (Optional Reading) S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. WWW, 1998	Hw3
	30	Spectral analysis-3: random walk with restart (Optional Reading) Minji Yoon, Jinhong Jung, and U Kang. TPA: Fast, Scalable, and Accurate Method for Approximate Random Walk with Restart on Billion Scale Graphs, ICDE 2018
Oct.	5	Spectral analysis-4: link prediction (Optional Reading) D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. CIKM, 2003. Lada A. Adamic and Eytan Adar. Friends and neighbors on the web. Social Networks, 25(3):211-230, 2003.
	7	Spectral analysis-5: triangle counting (Mandatory Reading) C. E. Tsourakakis, Fast Counting of Triangles in Large Real Networks: Algorithms and Laws, ICDM, 2008. (Optional Reading) C. E. Tsourakakis, U Kang, G. L. Miller, C. Faloutsos, DOULION: Counting Triangles in Massive Graphs with a Coint, KDD, 2009.	Hw4
	12	MapReduce-1: architecture (Mandatory Reading) Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI, 2004	Hw5
	14	MapReduce-2: data mining algorithms (Optional Reading) S. Papadimitriou, J. Sun, DisCo: Distributed Co-clustering with Map-Reduce, ICDM, 2008.
	19	SVD-1: basic definition (Optional Reading) S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, R. Harshman. Indexing by Latenet Semantic Analysis. Jounral of the American Society for Information Science, 1990
	21	Midterm
	26	Guest lecture 1
	28	SVD-2: case studies (Mandatory Reading) Korn, F., A. Labrinidis, et al. (1998). Ratio Rules: A New Paradigm for Fast, Quantifiable Data Mining. VLDB, New York, NY. (Optional Reading) Korn, F., H. V. Jagadish, et al. (May 13-15, 1997). Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences. ACM SIGMOD, Tucson, AZ.	Hw6
Nov.	2	SVD-3: properties (Optional Reading) Chen, C. M. and N. Roussopoulos (May 1994). Adaptive Selectivity Estimation Using Query Feedback. Proc. of the ACM-SIGMOD , Minneapolis, MN.
	4	Tensor analysis 1 (Mandatory Reading) T. G. Kolda, B. W. Bader and J. P. Kenny. Higher-Order Web Link Analysis Using Multilinear Algebra. In: ICDM 2005, Pages 242-249, November 2005 (Optional Reading) Tamara G. Kolda, Brett W. Bader, Tensor Decompositions and Applications, SIAM Review, Vol. 51, No.3 pp. 455-500, 2009. Jimeng Sun, Spiros Papadimitriou, Philip Yu. Window-based Tensor Analysis on High-dimensional and Multi-aspect Streams, Proc. of the Int. Conf. on Data Mining (ICDM), Hong Kong, China, Dec 2006 .	Hw7
	9	Tensor analysis 2 (Optional Reading) U Kang, Evangelos Papalexakis, Abhay Harpale, and Christos Faloutsos, GigaTensor: Scaling Tensor Analysis Up By 100 Times - Algorithms and Discoveries, KDD 2012
	11	Recommendation 1 (Mandatory Reading) Yehuda Koren, Robert M. Bell, Chris Volinsky, Matrix Factorization Techniques for Recommender Systems. Computer 42(8): 30-37 (2009)	Hw8
	16	Recommendation 2 (Mandatory Reading) Bonhun Koo, Hyunsik Jeon, and U Kang, Accurate News Recommendation Coalescing Personal and Global Temporal Preferences, PAKDD 2020	Hw9
	18	Time series analysis (Optional Reading) Yeh, Chin-Chia Michael, et al. Matrix profile I: all pairs similarity joins for time series: a unifying view that includes motifs, discords and shapelets, ICDM 2016
	23	Approximation (Optional Reading) C. R. Palmer, P. B. Gibbons, C. Faloutsos. ANF: a fast and scalable tool for data mining in massive graphs, KDD 2002
	25	Graph compression (Mandatory Reading) U Kang, C. Faloutsos. Beyond `Caveman Communities': Hubs and Spokes for Graph Compression and Mining, ICDM 2011 (Optional Reading) F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi, and P. Raghavan, "On compressing social networks," in KDD, 2009	Hw10
	30	Community detection (Optional Reading) J. Leskovec, K. J. Lang, A. Dasgupta, M. W. Mahoney. Statistical Properties of Community Structure in Large Social and Information Networks, WWW 2008
Dec.	2	Anomaly detection (Mandatory Reading) L. Akoglu, M. McGlohon, C. Faloutsos. OddBall: Spotting Anomalies in Weighted Graphs. PAKDD, 2012. (Optional Reading) J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. Neighborhood formation and anomaly detection in bipartite graphs. ICDM, 2005.	Hw11
	7	How to do great research
	9	Final exam week
	14	Final exam week

Grading

10% Attendance
30% Homework
30% Midterm
30% Final

Late policy - for all deliverables:

No delay penalties, for medical etc emergencies (bring doctor's note).
Each person has 4 'slip days' total, for the whole semester. 10% per day of delay, after that.

Textbook

There is no textbook required.

Prerequisite

Undergraduate level algorithm, statistics and linear algebra.

Last modified Aug. 25, 2020, by U Kang

Seoul National University M2177.003000 Advanced Data Mining Fall 2020 - U Kang