Spring 2013, CS760 Big Graph Mining

Korea Advanced Institute of Science and Technology
CS760 Big Graph Mining
Spring 2013 - U Kang

News and Announcements

6/13 : Poster session - prepare 8 printed slide pages.
6/11 : Final report due.
5/28 : Hadoop homework due.
5/2 : Progress report due.
3/19: Latex template for project report posted.
3/7: List of suggested projects posted.
3/6: Classroom changed to E3-1 Room 2445.

Course Information

Big graphs are everywhere: examples include the World Wide Web, social network, mobile call network, biological network, and many more. Mining big graphs helps us find userful patterns and anomalies which lead to high impact applications including fraud detection, recommendation system, cyber security, etc.
The course covers advanced algorithms for mining and managing big graphs. Topics include MapReduce/Hadoop, approximation, graph compression, power laws, community detection, graph structure analysis, triangle counting, link analysis, spectral graph analysis, tensor analysis, and anomaly detection.

Instructor: U Kang (ukang at cs.kaist.ac.kr)
- N1 605, ph (042)350-3565
- Office hours: Thursday 16:30-17:30 (also, by appointment)
Class meets: Tue, Thu 13:00~14:15, E3-1 Room 2445
URL of this web page: web.kaist.ac.kr/~ukang/courses/13S-760

Schedule

Lecture	Date		Topic	Due
1	Mar	5	Course Introduction
2		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.
3		12	Graph-2: models (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.
4		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),
5		19	Graph-4: structure analysis (Mandatory 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.
6		21	Spectral analysis-1: random walk (Optional Reading) Peter G. Doyle and J. Laurie Snell, Random walks and electric networks, July 2006
7		26	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
8		28	Spectral analysis-3: link prediction (Mandatory Reading) D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. CIKM, 2003. (Optional Reading) Lada A. Adamic and Eytan Adar. Friends and neighbors on the web. Social Networks, 25(3):211-230, 2003.
9	Apr	2	Spectral Analysis-4: triangle counting (Optional Reading) C. E. Tsourakakis, Fast Counting of Triangles in Large Real Networks: Algorithms and Laws, ICDM, 2008. C. E. Tsourakakis, U Kang, G. L. Miller, C. Faloutsos, DOULION: Counting Triangles in Massive Graphs with a Coint, KDD, 2009.	Proposal due (12:55 pm)
10		4	MapReduce-1: architecture (Mandatory Reading) Jeffrey Dean and Sanjay Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI, 2004
		9	No class
11		11	MapReduce-2: basic techniques (No Mandatory Reading)
12		16	MapReduce-3: graphs (Optional Reading) U Kang, C. E. Tsourakakis, C. Faloutsos, Pegasus: A Peta-Scale Graph Mining System - Implementation and Observations, ICDM, 2009. U Kang, H. Tong, J. Sun, C.-Y. Lin, C. Faloutsos, GBASE: A Scalable and General Graph Management System, KDD, 2011.
13		18	Guest Lecture: "Managing Skew in the Parallel Evaluation of User-Defined Operations" by Yongchul Kwon (Optional Reading) Y. Kwon, M. Balazinska, B. Howe, J. Rolia, SkewTune: Mitigating Skew in MapReduce Applications, SIGMOD, 2012. Y. Kwon, M. Balazinska, B. Howe, J. Rolia, Skew-Resistant Parallel Processing of Feature-Extracting Scientific User-Defined Functions, SoCC, 2010.
		23	Midterm week
		25	Midterm week
14		30	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
15	May	2	SVD-2: case studies (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. Korn, F., A. Labrinidis, et al. (1998). Ratio Rules: A New Paradigm for Fast, Quantifiable Data Mining. VLDB, New York, NY.	Progress report due (12:55 pm)
16		7	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.
17		9	Tensor Analysis (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 .
18		14	Data analysis on Hadoop (No Mandatory Reading)	Hadoop homework out
19		16	Approximation (Mandatory Reading) C. R. Palmer, P. B. Gibbons, C. Faloutsos. ANF: a fast and scalable tool for data mining in massive graphs, KDD 2002
		21	Project progress presentation
20		23	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
21		28	Community detection (Mandatory Reading) J. Leskovec, K. J. Lang, A. Dasgupta, M. W. Mahoney. Statistical Properties of Community Structure in Large Social and Information Networks, WWW 2008	Hadoop homework due (12:55 pm)
22		30	Anomaly detection (Optional Reading) L. Akoglu, M. McGlohon, C. Faloutsos. OddBall: Spotting Anomalies in Weighted Graphs. PAKDD, 2012. J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. Neighborhood formation and anomaly detection in bipartite graphs. ICDM, 2005.
	June	4	No class
		6	No class (holiday)
23		11	Conclusions - Review lecture	Final reports due (12:55 pm)
		13	Poster session
		18	Final exam week
		20	Final exam week

Grading

30% Homework
70% Project

Homework

Paper critique. (20%) The homework is composed of paper critiques for the 'mandatory' assigned readings. Before each class, the assigned readings will be posted to the homepage. Your task is to create an ~1 page summary for each of the readings. The summary should include the following content:
- 3 main points of the reading: what is the paper about? What is the problem that the paper wants to solve? What is the solution?
- 3 strengths of the reading: what is the main novelty that enabled the solution? What is the impact of the paper? If you were to write such a paper, how should you have thought?
- 3 future improvents of the reading: are there weaknesses of the paper? How can you extend and improve the paper?
Submit: the hard copy of the report before class.
Data analysis on Hadoop (10%)

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.

Project

Information.

Textbook

There is no textbook required.

Last modified Mar. 6, 2013, by U Kang

Korea Advanced Institute of Science and Technology CS760 Big Graph Mining Spring 2013 - U Kang