Introduction to spectral graph theory:
Chapter I of Chung: Spectral graph theory. 1997 (we will provide a copy)
and: B.Mohar: The Laplacian Spectrum of Graphs. In: Graph theory, combinatorics, and applications. Vol. 2, p. 871-898. Wiley, 1991. link
Graph Cuts for clustering: J. Shi and J. Malik: Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22 (8), p. 888-905, 2000. link
Graph Cuts for semi-supervised learning: T. Joachims, Transductive Learning via Spectral Graph Partitioning, Proceedings of the International Conference on Machine Learning (ICML), 2003. link
Random walk applications:
Random walk interpretation of spectral clustering: M. Meila and J. Shi: A random walks view of spectral segmentation. AISTATS 2001. link
Label Propagation: Xiaojin Zhu, Zoubin Ghahramani. Learning from Labeled and Unlabeled Data with Label Propagation. CMU CALD tech report CMU-CALD-02-107, 2002. link
Commute time distance: Fouss F., Pirotte A., Renders J.-M & Saerens M. (2004),
"A novel way of computing dissimilarities between nodes of a graph, with application to collaborative filtering and subspace projection of the graph nodes. Technical Report, 2005. link
Regularization/smoothness approaches:
M. Belkin, I. Matveeva, P. Niyogi: Regularization and Semi-supervised Learning on Large Graphs. COLT 2004. link
Dimension reduction and manifold learning:
Laplacian Eigenmaps: M. Belkin and P. Niyogi: Laplacian Eigenmaps for dimensionality reduction and data representation. Neural Computation, June 2003; 15 (6):1373-1396. link
Locally linear embedding: Lawrence K. Saul & Sam T. Roweis: Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds. Journal of Machine Learning Research, v4, pp. 119-155, 2003. link
Isomap: J. B. Tenenbaum, V. De Silva and J. C. Langford: A global geometric framework for nonlinear dimensionality reduction. Science 290 (5500), 2319-2323. 2002. Background reading on MDS: reference to come. link
Hub/Authority approach:
J. Kleinberg: Authoritative sources in a hyperlinked environment. Journal of the ACM 46 (5), pp. 604-632, 1999. link
Semi-supervised learning using the hub/authority approach: Zhou, Schölkopf, Hofmann: Semi-supervised learning on directed graphs. NIPS 2004. link
Commute distance on labeled graphs: Zhou, Huang, Schölkopf: Learning from labeled and unlabeled data on a directed graph. ICML 2005. link
Page Rank: Larry Page, Sergey Brin, R. Motwani, T. Winograd: The PageRank Citation Ranking: Bringing Order to the Web. Stanford University Technical Report, 1998. link
and Amy N. Langville and Carl D. Meyer. Deeper Inside PageRank. Internet Mathematics, Vol. 1(3):335-380, 2005. link
Protein Ranking algorithm similar to page rank: Jason Weston, Andre Elisseeff, Dengyong Zhou, Christina Leslie and William Stafford Noble: Protein ranking: From local to global structure in the protein similarity network. Proceedings of the National Academy of Science. 101(17):6559-6563, 2004. link
Faloutsos, Faloutsos, Faloutsos: On power law relationships of the internte topology. In SIGCOMM 1999. link
Graphs over time. Densification Laws, Shrinking Diameters and Possible Explanations. Leskovec, Kleinberg, Faloutsos. KDD 2005. link
Newman: The structure and function of complex networks. SIAM review, 45:167-256. 2003. link Pages 1- 29 only.Background on kernel algorithms: Reference to come.
Kernels between vertices of a graph:
R. I. Kondor and J. Lafferty (2002). Diffusion Kernels on Graphs and Other Discrete Input Spaces. ICML 2002. link
Book chapter on the same topic: R. Kondor and J.-P. Vert: Diffusion Kernels. in "Kernel Methods in Computational Biology" ed. B. Scholkopf, K. Tsuda and J.-P. Vert. The MIT Press, 2004. link
Kernels between different graphs:
H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In T. Faucett and N. Mishra, editors, Proceedings of the 20th International Conference on Machine Learning, pages 321-328, Menlo Park, CA, AAAI Press, 2003. link
Their book chapter on the same topic: H. Kashima, K. Tsuda, and A. Inokuchi. Kernels for graphs. In B. Schoelkopf, K. Tsuda, and J.P. Vert, editors, Kernel Methods in Computational Biology, pages 155-170. MIT Press, 2004. link
Predicting the graph structure:
Jean-Philippe Vert, Y. Yamanishi: Supervised Graph Inference. NIPS 17, 2004. link
T. Kato, K. Tsuda, and K. Asai: Selective Integration of Multiple Biological Data
for Supervised Network Inference. Bioinformatics 21(10):2488-2495, 2005. The paper is not freely available, we will provide a copy.
Introduction to Bayesian networks. Reference to come.
Introduction to hidden markov models. A chapter of Pierre Baldi: Bioinformatics. The machine learning approach.
or: Rabiner, L. R., A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, vol. 77, no. 2, Feb. 1989, pgs 257 - 285. link
or: Anders Meng: An introduction to Markov and Hidden Markov Models. Unpublished notes. link