nips nips2004 nips2004-165 nips2004-165-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dengyong Zhou, Thomas Hofmann, Bernhard Schölkopf
Abstract: Given a directed graph in which some of the nodes are labeled, we investigate the question of how to exploit the link structure of the graph to infer the labels of the remaining unlabeled nodes. To that extent we propose a regularization framework for functions defined over nodes of a directed graph that forces the classification function to change slowly on densely linked subgraphs. A powerful, yet computationally simple classification algorithm is derived within the proposed framework. The experimental evaluation on real-world Web classification problems demonstrates encouraging results that validate our approach. 1
[1] M. Belkin, I. Matveeva, and P. Niyogi. Regularization and regression on large graphs. In COLT, 2004.
[2] S. Brin and L. Page. The anatomy of a large scale hypertextual web search engine. In Proc. 7th Intl. WWW Conf., 1998.
[3] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the Web. In Proc. 9th Intl. WWW Conf., 2000.
[4] S. Chakrabarti, B. Dom, and P. Indyk. Enhanced hypertext categorization using hyperlinks. In Proc. ACM SIGMOD Conf., 1998.
[5] F. Chung. Spectral Graph Theory. Number 92 in Regional Conference Series in Mathematics. American Mathematical Society, 1997.
[6] M. Craven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam, and S. Slattery. Learning to extract symbolic knowledge from the World Wide Web. In Proc. 15th National Conf. on Artificial Intelligence, 1998.
[7] J. Dean and M. Henzinger. Finding related Web pages in the World Wide Web. In Proc. 8th Intl. WWW Conf., 1999.
[8] C. Ding, X. He, P. Husbands, H. Zha, and H. D. Simon. PageRank, HITS and a unified framework for link analysis. In Proc. 25th ACM SIGIR Conf., 2001.
[9] G. Flake, S. Lawrence, C. L. Giles, and F. Coetzee. Self-organization and identification of Web communities. IEEE Computer, 35(3):66–71, 2002.
[10] C. Lee Giles, K. Bollacker, and S. Lawrence. CiteSeer: An automatic citation indexing system. In Proc. 3rd ACM Conf. on Digital Libraries, 1998.
[11] T. Joachims, N. Cristianini, and J. Shawe-Taylor. Composite kernels for hypertext categorisation. In ICML, 2001.
[12] T. Joachims. Transductive learning via spectral graph partitioning. In ICML, 2003.
[13] J. Kleinberg. Authoritative sources in a hyperlinked environment. 46(5):604–632, 1999. Journal of the ACM,
[14] R. Lempel and S. Moran. SALSA: the stochastic approach for link-structure analysis. ACM Transactions on Information Systems, 19(2):131–160, 2001.
[15] A. Smola and R. Kondor. Kernels and regularization on graphs. In Learning Theory and Kernel Machines. Springer-Verlag, Berlin-Heidelberg, 2003.
[16] V. N. Vapnik. Statistical learning theory. Wiley, NY, 1998. ¨
[17] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Sch olkopf. Learning with local and global consistency. In NIPS, 2003.
[18] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In ICML, 2003. A Proof of Proposition 1 Expand the right site of Equ. (4): ΩA (f ) = f (u)f (v) f 2 (u) − p(u) p(u)p(v) ch ([u, v]) u,v h = f 2 (u) − p(u) ch ([u, v]) u v h ch ([u, v]) u,v h f (u)f (v) . p(u)p(v) (15) By substituting Equ. (3), the first term in the above equality can be rewritten as u v = u h w([h, u])w([h, v]) q(h) h w([h, u]) 2 f (u) = p(u) f 2 (u) p(u) f 2 (u). (16) u In addition, the second term in Equ. (15) can be transformed into u,v h = w([h, u])w([h, v]) f (u)f (v) q(h) p(u)p(v) w([h, u]) w([h, v]) f (v). q(h)p(u) q(h)p(v) f (u) u,v h (17) Substituting Equ. (16) and (17) into (15), we have f 2 (u) − ΩA (f ) = u This completes the proof. f (u) u,v h w([h, u]) w([h, v]) f (v). q(h)p(u) q(h)p(v) (18)