Learning spectral graph transformations for link prediction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning spectral graph transformations for link prediction

Full text

Pdf (693 KB)

Source

ACM International Conference Proceeding Series; Vol. 382 archive
Proceedings of the 26th Annual International Conference on Machine Learning table of contents

Montreal, Quebec, Canada

Pages 561-568

Year of Publication: 2009

ISBN:978-1-60558-516-1

Authors

Jérôme Kunegis	Technische Universität Berlin, Berlin, Germany
Andreas Lommatzsch	Technische Universität Berlin, Berlin, Germany

Sponsors

: MITACS
: NSF
Microsoft Research : Microsoft Research

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 64, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1553374.1553447 What is a DOI?

ABSTRACT

We present a unified framework for learning link prediction and edge weight prediction functions in large networks, based on the transformation of a graph's algebraic spectrum. Our approach generalizes several graph kernels and dimensionality reduction methods and provides a method to estimate their parameters efficiently. We show how the parameters of these prediction functions can be learned by reducing the problem to a one-dimensional regression problem whose runtime only depends on the method's reduced rank and that can be inspected visually. We derive variants that apply to undirected, weighted, unweighted, unipartite and bipartite graphs. We evaluate our method experimentally using examples from social networks, collaborative filtering, trust networks, citation networks, authorship graphs and hyperlink networks.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Albert, R., Jeong, H., & Barabáási, A.-L. (1999). The diameter of the World Wide Web. Nature, 401, 130.
	2	Peter Bailey , Nick Craswell , David Hawking, Engineering a multi-purpose test collection for web retrieval experiments, Information Processing and Management: an International Journal, v.39 n.6, p.853-871, November 2003 [doi>10.1016/S0306-4573(02)00084-5]
	3	Chebotarev, P., & Shamis, E. (1997). The matrix-forest theorem and measuring relations in small social groups. Automation and Remote Control, 58, 1505--1514.
	4	Francois Fouss , Alain Pirotte , Jean-Michel Renders , Marco Saerens, Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.355-369, March 2007 [doi>10.1109/TKDE.2007.46]
	5	Ken Goldberg , Theresa Roeder , Dhruv Gupta , Chris Perkins, Eigentaste: A Constant Time Collaborative Filtering Algorithm, Information Retrieval, v.4 n.2, p.133-151, July 2001 [doi>10.1023/A:1011419012209]
	6	R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
	7	Hage, P., & Harary, F. (1983). Structural models in anthropology. Cambridge University Press.
	8	Hou, Y. (2005). Bounds for the least Laplacian eigen-value of a signed graph. Acta Mathematica Sinica, 21, 955--960.
	9	Takahiko Ito , Masashi Shimbo , Taku Kudo , Yuji Matsumoto, Application of kernels to link analysis, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081941]
	10	Kandola, J., Shawe-taylor, J., & Cristianini, N. (2002). Learning semantic similarity. Advances in Neural Information Processing Systems (pp. 657--664).
	11	Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
	12	Jérôme Kunegis , Andreas Lommatzsch , Christian Bauckhage, The slashdot zoo: mining a social network with negative edges, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain [doi>10.1145/1526709.1526809]
	13	David Liben-Nowell , Jon Kleinberg, The link prediction problem for social networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956972]
	14	Newman, M. E. J. (2001). The structure of scientific collaboration networks. Proc. National Academy of Sciences, 98, 404--409.
	15	Sarwar, B., Karypis, G., Konstan, J., & Riedl, J. (2000). Application of dimensionality reduction in recommender systems--a case study. Proc. ACM WebKDD Workshop.
	16	Smola, A., & Kondor, R. (2003). Kernels and regularization on graphs. Proc. Conf. on Learning Theory and Kernel Machines (pp. 144--158).
	17	Stewart, D. (2005). Social status in an open-source community. American Sociological Review, 70, 823--842.
	18	Wax, M., & Sheinvald, J. (1997). A least-squares approach to joint diagonalization. IEEE Signal Processing Letters, 4, 52--53.
	19	Yi Wu , Edward Y. Chang, Distance-function design and fusion for sequence data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031238]