Learning from labeled and unlabeled data on a directed graph

ABSTRACT

We propose a general framework for learning from labeled and unlabeled data on a directed graph in which the structure of the graph including the directionality of the edges is considered. The time complexity of the algorithm derived from this framework is nearly linear due to recently developed numerical techniques. In the absence of labeled instances, this framework can be utilized as a spectral clustering method for directed graphs, which generalizes the spectral clustering approach for undirected graphs. We have applied our framework to real-world web classification problems and obtained encouraging results.

REFERENCES

• 1: Chung, F. (1997). Spectral graph theory. No. 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI.
• 2: Chung, F. (to appear). Laplacian and the Cheeger inequality for directed graphs. Annals of Combinatorics.
• 3: Lisa Getoor , Nir Friedman , Daphne Koller , Benjamin Taskar, Learning probabilistic models of link structure, The Journal of Machine Learning Research, 3, 3/1/2003
• 4: Monika R. Henzinger, Hyperlink Analysis for the Web, IEEE Internet Computing, v.5 n.1, p.45-50, January 2001 [doi>10.1109/4236.895141]
• 5: Henzinger, M. (2003). Algorithmic challenges in web search engines. Internet Mathematics, 1, 115--123.
• 6: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 7: Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The PageRank citation ranking: bring order to the web (Technical Report). Stanford University.
• 8: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 9: Daniel A. Spielman , Shang-Hua Teng, Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m1.31), Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.416, October 11-14, 2003
• 10: Tikhonov, A., & Arscnin, V. (1977). Solutions of ill-posed problems. W. H. Winston, Washington, DC.
• 11: Vapnik, V. (1998). Statistical learning theory. Wiley, NY.
• 12: Wahba, G. (1990). Spline models for observational data. No. 59 in CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, Philadelphia.
• 13: Zhou, D., Bousquet, O., Lal. T., Weston, J., & Schöölkopf, B. (2004). Learning with local and global consistency. Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA.
• 14: Zhou, D., Schölkopf, B., & Hofmann, T. (2005). Semi-supervised learning on directed graphs. Advances in Neural Information Processing Systems 17. MIT Press, Cambridge, MA.