Machine Learning in Network Science

Week	Date	Topic	Material	Assignments/Project
1	January 24	○ Introduction to network science and machine learning on graphs ○ Basic network properties; the random graph and small-world models	Lecture 1A Lecture 1B
2	January 31	○ Power-law degree distribution and the Preferential Attachment model ○ Centrality criteria and link analysis algorithms ○ Practical session	Lecture 2A Lecture 2B
3	February 21	○ Link prediction and graph similarity ○ Graph similarity ○ Practical session (preparation for the Kaggle challenge)	Lecture 3A Lecture 3B	Data challenge out
4	February 28	○ Representation learning on graphs; node embedding models ○ Practical session	Lecture 4	Project proposal due on February 28
5	March 7	○ Graph neural networks ○ Practical session	Lecture 5
6	March 14	○ Graph clustering and community detection ○ Practical session	Lecture 6
7	March 21	○ Cascading behavior in networks; Influence maximization ○ Practical session	Lecture 7	Data challenge due on March 21
8	March 28	Project presentations		Project final report due on March 28 Poster session

[January 24] Lecture 1: Introduction; basic network properties; generative models

Part A: Introduction to network science and machine learning on graphs

Introduction to graph mining, network analysis, and machine learning on graphs; administrivia, course structure and overview of the topics that will be covered in the course.

Reading:

• Networks, crowds, and markets (Chapter 1 and 13)
• The structure and function of complex networks (Sections I and II)
• Network science (Chapter 1)

Part B: Basic network properties; the random graph and small-world models

Presentation of basic concepts in graph theory, linear algebra and spectral graph theory that will be used throughout the course. Basic network properties: degree distribution, clustering coefficient and shortest path length. The Erdos-Renyi random graph model and its basic properties. Comparison to the properties of real networks. The small-world phenomenon and the small-world model.

Reading:

• Networks, crowds, and markets (Chapter 2 and 20)
• Social media mining (Chapters 2 and 5)
• Notes in linear algebra, probability, and proof techniques, by Jessica Su and the SNAP team (Stanford University)
• Network science (Chapter 3)

Additional:

• Networks: An Introduction (Chapters 6, 8 and 9)
• SVD and Low Rank Matrix Approximations, lecture notes by Tim Roughgarden and Gregory Valiant (Stanford University)
• Lectures on Spectral Graph Theory, by Fan Chung (Chapter 2: Eigenvalues and the Laplacian of a graph)
• J. Leskovec and E. Horvitz. Planetary-Scale Views on a Large Instant-Messaging Network. In WWW, 2008
• Lecture 3, Lecture 4 and Lecture 5 from CSE 258 (background knowledge in data mining and machine learning)
• Random graphs, lecture notes by Aaron Clauset (CU Boulder)
• Diameter on d-regular random graphs, lecture notes by Yaron Singer (Harvard University)
• Networks: An Introduction (Chapter 12)
• P. Erdos and A. Renyi. On Random Graphs I. Publicationes Mathematicae (6) 290-297, 1959
• P. Erdos and A. Renyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960
• D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature 393:440-42, 1998
• P. S. Dodds, R. Muhamad, D. J. Watts. An Experimental Study of Search in Global Social Networks. Science 301, 2003
• D. J. Watts, P. S. Dodds, M. E. J. Newman. Identity and Search in Social Networks. Science, 296, 1302-1305, 2002
• M. E. J. Newman. Models of the Small World: A Review., J. Stat. Physics 2000
• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. ACM Symposium on Theory of Computing, 2000
• L. Backstrom, P. Boldi, M. Rosa, J. Ugander, and S. Vigna. Four Degrees of Separation. ACM Web Science Conference. 2012
• J. Ugander, B. Karrer, L. Backstrom, and C. Marlow. The Anatomy of the Facebook Social Graph. arXiv, 2012

[January 31] Lecture 2: The Preferential Attachment model; centrality criteria

Part A: Power-law degree distribution and the Preferential Attachment model

Power-law degree distribution in real networks. The Preferential Attachment model. Consequences of skewed degree distribution in the robustness of real networks.

Reading:

• Network science (Chapter 4, 5)
• Graph Mining: Laws, Tools, and Case Studies (Chapter 9)
• R. Albert, H Jeong, and A.-L. Barabasi. Error and attack tolerance of complex networks. Nature 406, 378-382, 2000

Additional:

• A. Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009
• Networks, crowds, and markets (Chapter 18)
• Graph Mining: Laws, Tools, and Case Studies (Chapter 2 and 9)
• Bela Bollobas, Oliver Riordan, Joel Spencer and Gabor Tusnady. The degree sequence of a scale-free random graph process. Journal Random Structures and Algorithms 18(3), 2001
• M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics 1(2), pp. 226-251, 2004
• M. Faloutsos, P. Faloutsos, C. Faloutsos. On Power-Law Relationships of the Internet Topology. In SIGCOMM, 1999.
• R. Albert, H Jeong, and A.-L. Barabasi. The diameter of the world wide web. Nature 401, 130-131, 1999
• A.L Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286, 1999
• J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM TKDD, 2007
• J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani. Kronecker Graphs: An approach to modeling networks. Journal of Machine Learning Research (JMLR) 11:985-1042, 2010

Part B: Centrality criteria and link analysis algorithms

Centrality criteria in graphs (degree, closeness, betweenness, eigenvector, Katz). Link analysis ranking algorithms (HITS and PageRank).

Reading:

• Social media mining (Chapters 2 and 5)
• Networks, crowds, and markets (Chapter 1)
• S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. In Proc. of the 7th International World Wide Web Conference (WWW), 1998
• J. Kleinberg. Authoritative sources in a hyperlinked environment. In Proc. of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998

Additional:

• Networks: An Introduction (Chapter 7, Sections 7.1 - 7.7)
• F. Bonchi, G. De Francisci Morales, and M. Riondato. Centrality Measures on Big Graphs: Exact, Approximated, and Distributed Algorithms. Tutorial at WWW, 2016.
• U Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25(2), 163-177, 2001
• T. H. Haveliwala. Topic-Sensitive PageRank. In Proc 11th International World Wide Web Conference, 2002
• G. Jeh and J. Widom. Scaling Personalized Web Search. In Proc. roceedings of the 12th international conference on World Wide Web (WWW), 2003
• A. Borodin, J. S. Rosenthal, G. O. Roberts, and P. Tsaparas. Finding Authorities and Hubs From Link Structures on the World Wide Web. In Proc. 10th International World Wide Web Conference, 2001
• P. Berkhin. A Survey on PageRank Computing. Internet Mathematics 2(1), pages 73-120, 2005

[February 21] Lecture 3: Link prediction and graph similarity

Part A: Link prediction

The link prediction task. Node similarity measures. Unsupervised vs. supervised link prediction in networks.

Reading:

• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. In CIKM, 2003
• R. Lichtenwalter, J.T. Lussier, and N.V. Chawla. New perspectives and methods in link prediction. In KDD, 2010
• L. Backstrom, J. Leskovec. Supervised Random Walks: Predicting and Recommending Links in Social Networks. In WSDM, 2011

Additional:

• G. Jeh and J. Widom. SimRank: A Measure of Structural-Context Similarity. In KDD, 2002
• P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, and R.Zadeh. WTF: The Who to Follow Service at Twitter. In WWW, 2013
• A. Clauset, C. Moore, M.E.J. Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 2008
• L.A. Adami and E. Adar. Friends and neighbors on the Web. Social Networks 25, 211-230, 2003
• L. Lua and T. Zhoua. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications 390(6), 1150-1170, 2011

Part B: Graph similarity

Graph similarity. Graph kernels.

Reading:

• D. Koutra, N. Shah, J. Vogelstein, B. Gallagher, and C. Faloutsos. DeltaCon: A Principled Massive-Graph Similarity Function with Attribution. ACM TKDD, 2015
• S.V.N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, Karsten M. Borgwardt. Graph Kernels. JMLR, 2010

Additional:

• P. Papadimitriou, A. Dasdan and H. Garcia-Molina. Web Graph Similarity for Anomaly Detection. Journal of Internet Services and Applications 1(1), pp. 19-30, 2010
• S. Soundarajan, T. Eliassi-Rad, and B. Gallagher. A Guide to Selecting a Network Similarity Method. In SDM, 2014
• K. M. Borgwardt and H. Kriegel. Shortest-path kernels on graphs. In ICDM, 2005
• N. Shervashidze, T. Petri, K. Mehlhorn, K. M. Borgwardt, and S. Vishwanathan. Efficient Graphlet Kernels for Large Graph Comparison. In AISTATS, 2009
• T. Gartner, P. Flach, and S. Wrobel. On Graph Kernels: Hardness Results and Efficient Alternatives. Learning Theory and Kernel Machines, 2003
• X. Gao, B. Xiao, D. Tao, and X. Li. A survey of graph edit distance. Pattern Analysis and Applications 13(1), 113-129, 2010
• R.C. Wilson and P. Zhu. A Study of Graph Spectra for Comparing Graphs and Trees. Journal of Pattern Recognition 41(9), 2833-2841, 2008

[February 28] Lecture 4: Representation learning on graphs

Methods for learning node embeddings on graphs (LINE, DeepWalk and node2vec).

Reading:

• J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. LINE: Large-scale information network embedding. In WWW, 2015
• B. Perozzi, R. Al-Rfou, and S. Skiena. DeepWalk: Online Learning of Social Representations. In KDD, 2014
• A. Grover and J. Leskovec. node2vec: Scalable Feature Learning for Networks. In KDD, 2016

Additional:

• J. B. Tenenbaum, V. De Silva, and J. C. Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290:5500, pp. 2319-2323, 2000
• S. T. Roweis and L. K. Saul. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 290:5500, pp. 2323-2326, 2000
• M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS, 2001
• T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. arXiv, 2013
• T. Mikolov, I. Sutskever, K. Chen, G.S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In NIPS, 2013
• S. Cao, W. Lu, and Q. Xu. GraRep: Learning Graph Representations with global structural information. In CIKM, 2015
• S. Cao, W. Lu, and Q. Xu. Deep Neural Networks for Learning Graph Representations. In AAAI, 2016
• W. L. Hamilton, R. Ying, and J. Leskovec. Representation Learning on Graphs: Methods and Applications. IEEE Data Engineering Bulletin, 2017
• P. Goyal and E. Ferrara. Graph Embedding Techniques, Applications, and Performance: A Survey. arXiv, 2017
• A. Narayanan, M. Chandramohan, L. Chen, Y. Liu, and S. Saminathan. subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs. In KDD (MLG Workshop), 2016
• M. Niepert, M. Ahmed, and K. Kutzkov. Learning Convolutional Neural Networks for Graphs. In ICML, 2016

[March 7] Lecture 5: Graph neural networks

GNN models. Message aggregation strategies. Graph Convolutional Networks. GraphSAGE. Graph Attention Networks. Unsupervised and supervised training. Predictions (node-level, edge-level, graph-level) with GNNs.

Reading:

• Graph Representation Learning (Chapters 5 and 6)

Additional:

• T. Kipf and M. Welling. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR, 2017
• W.L. Hamilton, R. Ying, and J. Leskovec. Inductive Representation Learning on Large Graphs. In NIPS, 2017
• P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph Attention Networks. In ICLR, 2018

[March 14] Lecture 6: Graph clustering and community detection

Community detection in networks. Girvan-Newman algorithm. Modularity and modularity optimization (greedy, spectral, Louvain method). Spectral clustering. Community evaluation criteria. Community detection in directed networks. Overlapping community detection. Community structure of large scale networks.

Reading:

• M. Girvan and M.E.J. Newman. Community structure in social and biological networks. PNAS 99, 2002
• M.E.J. Newman. Modularity and community structure in networks. PNAS, 2006
• U. von Luxburg. Tutorial on spectral clustering. Statistics and Computing 17(4), 2007
• Networks: An Introduction (Sections 11.5, 11.6)
• G. Palla, I. Derenyi, I. Farkas, T. Vicsek. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814-818, 2005
• J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics, 2009

Additional:

• J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.L. Barabasi. Structure and tie strengths in mobile communication networks. PNAS, 2007
• M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004
• A. Clauset, M.E.J. Newman, C. Moore. Finding community structure in very large networks. Phys. Rev. E 70, 066111, 2004
• V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008
• S. Fortunato. Community detection in graphs. Physics Reports, 2010
• Social media mining (Chapters 6)
• U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On Modularity Clustering. IEEE TKDE 20(2), 2008
• S. Fortunato and S. Barthelemy. Resolution limit in community detection. Proc. Natl. Acad. Sci., 2007
• L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. In Proc. KDD, 2006
• J. Yang and J. Leskovec. Defining and Evaluating Network Communities based on Ground-Truth. In ICDM, 2012
• S. Fortunato. Community detection in graphs. Physics Reports, 2010
• Social media mining (Chapters 6)
• J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis And Machine Intelligence, vol. 22, no. 8, 2000
• A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm . In NIPS, 2001
• F. D. Malliaros and M. Vazirgiannis. Clustering and Community Detection in Directed Networks: A Survey. Physics Reports, 533(4): 95-142, 2013

[March 21] Lecture 7: Cascading behavior in networks and influence maximization

Part A: Cascading behavior in networks

Cascading behavior. Models of virus and information probagation.

Reading:

• Networks, crowds, and markets (Chapter 21)
• J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, and M. Hurst. Cascading Behavior in Large Blog Graphs. In SDM, 2007

Additional:

• Networks: An Introduction (Chapter 17: 17.1 - 17.4)
• Network science (Chapter 10)
• D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec, and C. Faloutsos. Epidemic thresholds in real networks. ACM Trans. Inf. Syst. Secur. 10(4): 1:1-1:26, 2008
• B.A. Prakash, D. Chakrabarti, N.C. Valler, M. Faloutsos, and C. Faloutsos. Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and Information Systems 33 (3), 2012
• M. Goetz, J. Leskovec, M. Mcglohon, and C. Faloutsos. Modeling blog dynamics. In ICWSM, 2009
• E. Adar and L. Adamic. Tracking information epidemics in blogspace. In Web Intelligence, 2005
• J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural Diversity in Social Contagion. PNAS 109 (16), 2012
• A. Goyal, F. Bonchi, and L.V.S. Lakshmanan. Learning influence probabilities in social networks. In WSDM, 2010

Part B: Influence maximization

Influence maximization in social networks. The Greedy algorithm. Outbreak detection in networks.

Reading:

• D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the Spread of Influence through a Social Network. In KDD, 2003
• M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. Identification of influential spreaders in complex networks. Nature Physics 6, 888-893, 2010

Additional:

• A. Goyal, W. Lu, and L. S.V. Lakshmanan. SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In ICDM, 2011
• J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective Outbreak Detection in Networks. In KDD, 2007
• W. Chen, Y. Wang, and S. Yang. Efficient Influence Maximization in Social Networks. In KDD, 2009
• W. Chen, Y. Yuan, and L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In ICDM, 2010
• A. Goyal, W. Lu, and L. V.S. Lakshmanan. CELF++: optimizing the greedy algorithm for influence maximization in social networks. In WWW, 2011
• E. Cohen, D. Delling, T. Pajor, and R.F. Werneck. Sketch-based Influence Maximization and Computation: Scaling up with Guarantees. In CIKM, 2014
• Y. Wang, G. Cong, G. Song, and K. Xie. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks. In KDD, 2010
• M. Richardson and P. Domingos. Mining the Network Value of Customers. In KDD, 2001
• M. Richardson and P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In KDD, 2002
• J. Leskovec, L. Adamic, and B. Huberman. The Dynamics of Viral Marketing. TWEB, 2007
• A. Goyal, F. Bonchi, and K. V.S. Lakshmanan. A Data-Based approach to Social Influence Maximization. In PVLDB, 2012