Advanced Data Mining (CSE 554)
Advanced Data Mining (CSE 554)
Syllabus
This course covers the analysis of relational and network-structured data — the kind of data that arises when entities interact, connect, or co-occur. Most real-world datasets (social networks, transaction logs, the Web, biological networks) are inherently relational, and classical tabular methods fail to capture the structure embedded in these relationships. From the perspective of Relational Big Data Analysis, the course examines how large-scale relational datasets can be characterised, modeled, and processed efficiently. From the perspective of Relational Data Mining, the course develops algorithmic tools for discovering patterns, communities, and predictive structure within relational data. Topics include graph models of real-world networks, community detection, influence propagation, recommendation systems, and association rule mining.
Letter Criteria
This course adopts an absolute grading policy. Final letter grades will be assigned based on the total score accumulated throughout the semester.
A+ : 95–100
A0 : 90–94
A- : 85–89
B+ : 80–84
B0 : 75–79
B- : 70–74
C+ : 65–69
C0 : 60–64
C- : 55–59
D+ : 50–54
D0 : 45–49
D- : 40–44
F : below 40
Evaluation Criteria
Paper critique : 10%
Midterm exam : 30%
Final exam : 30%
Individual Projects : 30%
Additional bonus score will be granted
T1. Networks as a Data Model: Representation and Basic Structure — Why study networks; networks as a universal language across social, information, biological, and technological domains. Graph representations (adjacency matrix, edge list, adjacency list), directed vs. undirected graphs, node degrees, bipartite and weighted graphs, and connectivity. Overview of the two central themes: network structure & evolution, and processes & dynamics.
T2. The Web as a Graph: Measuring Network Structure — The Web as a directed graph and its bowtie decomposition via strongly connected components. The three key network properties — degree distribution, path length and diameter, and clustering coefficient — applied to a large-scale case study (MSN Messenger), and what these measurements reveal about real networks.
T3. Random Graphs and the Small-World Phenomenon — The Erdős–Rényi random graph G(n,p) as a baseline null model: expected degree, degree distribution, clustering coefficient, expansion, and the emergence of a giant component and small diameter. Where G(n,p) fails to match real networks, and the Watts–Strogatz model reconciling high clustering with short path lengths by rewiring a regular lattice with a few random shortcuts.
T4. Navigable Networks: Kleinberg's Model and Decentralized Search — How individuals find short paths using only local information. Why Watts–Strogatz networks are not searchable, Kleinberg's model with geographically biased long-range links, the conditions on the exponent that make a network navigable, and algorithmic consequences (P2P search, Chord) with empirical studies of navigation.
T5. Centrality and Human Evaluation in Networks — Measuring node importance via betweenness and closeness centrality. Applying network science to human evaluation: how people rate and assess one another online, the effects of status and similarity on evaluations, and aggregating evaluations for prediction.
T6. Signed Networks: Balance, Status, and Edge Sign Prediction — Networks with positive (friend) and negative (enemy) edges. Heider's structural balance theory ("a friend of a friend is a friend"), analysis of signed triads, the competing theory of status, and supervised prediction of edge signs from local features.
T7. Decision-Based Models of Cascading Behavior — How behaviors, products, and ideas spread when adoption is a strategic decision. Granovetter's model of collective action, game-theoretic threshold models of diffusion, cascade capacity, and the coexistence and compatibility of competing behaviors.
T8. Probabilistic Contagion: Epidemic Models and Independent Cascades — Epidemic-style spreading where contagion is probabilistic rather than decision-driven. SIR and SIS models and the epidemic threshold, the Independent Cascade model, empirical exposure curves, and interactions between competing contagions.
T9. Influence Maximization: Submodularity and Greedy Approximation — Selecting a seed set of nodes to maximize the spread of influence. NP-hardness of the problem, submodularity of the influence function under the Independent Cascade model, and the greedy hill-climbing algorithm with its (1 − 1/e) approximation guarantee.
T10. Outbreak Detection: Cost-Constrained Submodular Optimization — Placing sensors to detect outbreaks (contamination, information) as quickly as possible. Formulating outbreak detection as submodular maximization under cost constraints, the CELF algorithm with lazy evaluations, data-dependent bounds on solution quality, and case studies on water distribution networks and blogs.
T11. Power Laws, Scale-Free Networks, and Network Resilience — Heavy-tailed degree distributions in real networks. Identifying and fitting power laws, estimating the degree exponent, the difference from exponential distributions, and the structural consequences of hub nodes — including network resilience under random failure versus targeted attack.
T12. Network Evolution: Preferential Attachment and Microscopic Dynamics — Generative models explaining how power laws emerge as networks grow. Continuous-time analysis of preferential ("rich-get-richer") attachment and derivation of the resulting degree distribution, followed by empirical microscopic dynamics: node arrival, edge gaps, and triad-closing strategies.
T13. Kronecker Graphs: Recursive Network Models and Estimation — Macroscopic evolution patterns (densification power law, shrinking diameters) and the Forest Fire model, leading to Kronecker graphs as a recursive generative model. How Kronecker products yield graphs matching observed properties, stochastic Kronecker graphs, and KronFit for parameter estimation on real data.
T14. Link Analysis: HITS, PageRank, and Random Walks with Restarts — Ranking nodes via random walks on graphs. Hubs and authorities (HITS), the PageRank algorithm with the random-surfer model and teleportation, handling spider traps and dead ends, power-iteration computation, and Personalized PageRank / random walks with restarts for graph proximity and recommendation. (Includes supplementary handout.)
T15. Weak Ties, Girvan-Newman, and Modularity — Granovetter's theory linking tie strength to network position: triadic closure, bridges and local bridges, neighborhood overlap, and how weak ties grant access to novel information. Community detection via the Girvan-Newman algorithm and modularity optimization, with a detour through structural holes.
T16. Spectral Clustering: Graph Cuts and Motif-Based Partitioning — Partitioning graphs using the eigenstructure of matrix representations. Graph cut criteria and conductance, the graph Laplacian and the Fiedler vector, the three stages of spectral partitioning (matrix, eigenvectors, grouping), k-way extensions, and higher-order motif-based spectral clustering.
T17. Overlapping Communities: Clique Percolation, NCP, and BigCLAM — Detecting communities when a node belongs to many social circles simultaneously. The Clique Percolation Method (k-clique communities), the Network Community Profile plot and what it reveals about large real networks, and model-based approaches (AGM, BigCLAM) allowing nodes to participate in multiple overlapping groups.
T18. Node Embeddings: node2vec and Multi-Layer Networks — Learning low-dimensional vector representations of nodes for machine-learning tasks. The node2vec random-walk embedding method, the trade-off between homophily and structural equivalence via biased walks (BFS vs. DFS), and the OhmNet extension to hierarchical multi-layer networks with applications to protein function prediction.
Related textbook & lecture
How to do research https://www.cs.ucr.edu/~eamonn/public/SDM_How_to_do_Research_Keogh.pdf
아주 쉬운 논문쓰기 https://oslab.kaist.ac.kr/wp-content/uploads/esos_files/paperwriting.pdf
학문을 직업으로 삼으려는 젊은 학자들을 위하여 http://www.ekera.org/bbs/board.php?bo_table=letter&wr_id=3407