Article

Online learning over graphs

Authors:

Massimiliano Pontil,

Lisa WainerAuthors Info & Claims

ICML '05: Proceedings of the 22nd international conference on Machine learning

Pages 305 - 312

https://doi.org/10.1145/1102351.1102390

Published: 07 August 2005 Publication History

Abstract

We apply classic online learning techniques similar to the perceptron algorithm to the problem of learning a function defined on a graph. The benefit of our approach includes simple algorithms and performance guarantees that we naturally interpret in terms of structural properties of the graph, such as the algebraic connectivity or the diameter of the graph. We also discuss how these methods can be modified to allow active learning on a graph. We present preliminary experiments with encouraging results.

References

[1]

Bauschke, H. H., & Borwein, J. M. (1996). On projection algorithms for solving convex feasibility problems. SIAM Review, 38, 367--426.]]

Digital Library

[2]

Belkin, M., Matveeva, I., & Niyogi, P. (2004). Regularization and semi-supervised learning on large graphs. COLT 2004, Proc. (pp. 624--638). Springer.]]

[3]

Belkin, M., & Niyogi, P. (2004). Semi-supervised learning on riemannian manifolds. Machine Learning, 56, 209--239.]]

Digital Library

[4]

Campbell, C., Cristianini, N., & Smola, A. (2000). Query learning with large margin classifiers. ICML 2000, Proc. (pp. 111--118). Morgan Kaufmann.]]

Digital Library

[5]

Chung, F. R. (1997). Spectral graph theory. No. 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Society.]]

[6]

Freund, Y., & Schapire, R. E. (1999). Large margin classification using the perceptron algorithm. Machine Learning, 37, 277--296.]]

Digital Library

[7]

Gentile, C., & Warmuth, M. K. (1998). Linear hinge loss and average margin. NIPS 1998, Proc. (pp. 225--231). MIT Press.]]

Digital Library

[8]

Herbster, M. (2001). Learning additive models online with fast evaluating kernels. COLT 2001, Proc. (pp. 444--460). Springer.]]

Digital Library

[9]

Herbster, M., Pontil, M., & Wainer, L. (2005). Online learning over graphs (Working Paper). University College London.]]

[10]

Kondor, R., & Lafferty, J. (2002). Diffusion kernels on graphs and other discrete input spaces. ICML 2002, Proc. (pp. 315--322). Morgan Kaufmann.]]

Digital Library

[11]

Shalev-Shwartz, S., Crammer, K., Dekel, O., & Singer, Y. (2004). Online passive-aggressive algorithms. NIPS 16. MIT Press.]]

[12]

Smola, A., & Kondor, R. (2003). Kernels and regularization on graphs. COLT 2003, Proc. (pp. 144--158). Springer.]]

[13]

Tong, S., & Koller, D. (2000). Support vector machine active learning with applications to text classification. ICML 2000, Proc. (pp. 999--1006). Morgan Kaufmann.]]

Digital Library

[14]

Wahba, G. (1990). Splines models for observational data, vol. 59 of Regional conference series in Applied Mathematics. SIAM.]]

[15]

Warmuth, M. K., Liao, J., Rätsch, G., Mathieson, M., Putta, S., & Lemmen, C. (2003). Active learning with support vector machines in the drug discovery process. Journal of Chemical Information and Computer Sciences, 43, 667--673.]]

[16]

Zhu, X., Ghahramani, Z., & Lafferty, J. (2003a). Semi-supervised learning using gaussian fields and harmonic functions. ICML 2003, Proc. (pp. 912--919). AAAI Press.]]

[17]

Zhu, X., Lafferty, J., & Ghahramani, Z. (2003b). Combining active learning and semi-supervised learning using gaussian fields and harmonic functions. Proc. of the ICML 2003 workshop on The Continuum from Labeled to Unlabeled Data in ML and Data Mining (pp. 58--65).]]

Cited By

Peng CTang TYin QBai XLim SAggarwal C(2024)Physics-Informed Explainable Continual Learning on GraphsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.334745335:9(11761-11772)Online publication date: Sep-2024
https://doi.org/10.1109/TNNLS.2023.3347453
Zhou BSun YBabanezhad RKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Fast online node labeling for very large graphsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620207(42658-42697)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620207
Chen ZChen FZhang LJi TFu KZhao LChen FWu LAggarwal CLu C(2023)Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural NetworksACM Computing Surveys10.1145/362781656:5(1-42)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3627816
Show More Cited By

Online learning over graphs
1. Computing methodologies
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Comparability Graphs Among Cover-Incomparability Graphs
Algorithms and Discrete Applied Mathematics
Abstract
Comparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset $P = (V, \leq)$ is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are ...
Collapsible graphs and Hamiltonian connectedness of line graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics-an update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, ...
Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G-v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '05: Proceedings of the 22nd international conference on Machine learning

August 2005

1113 pages

ISBN:1595931805

DOI:10.1145/1102351

General Chair:
Saso Dzeroski
Jozef Stefan Institute, Slovenia
,
Program Chairs:
Luc De Raedt,
Stefan Wrobel

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
601
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Peng CTang TYin QBai XLim SAggarwal C(2024)Physics-Informed Explainable Continual Learning on GraphsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.334745335:9(11761-11772)Online publication date: Sep-2024
https://doi.org/10.1109/TNNLS.2023.3347453
Zhou BSun YBabanezhad RKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Fast online node labeling for very large graphsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620207(42658-42697)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620207
Chen ZChen FZhang LJi TFu KZhao LChen FWu LAggarwal CLu C(2023)Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural NetworksACM Computing Surveys10.1145/362781656:5(1-42)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3627816
Yu WMa XBailey JZhan YWu JDu BHu W(2023)Graph structure reforming framework enhanced by commute time distance for graph classificationNeural Networks10.1016/j.neunet.2023.09.044168(539-548)Online publication date: Nov-2023
https://doi.org/10.1016/j.neunet.2023.09.044
Thiessen MGärtner T(2023)Online Learning of Convex Sets on GraphsMachine Learning and Knowledge Discovery in Databases10.1007/978-3-031-26412-2_22(349-364)Online publication date: 17-Mar-2023
https://doi.org/10.1007/978-3-031-26412-2_22
Das BIsufi E(2022)Online Filtering over Expanding Graphs2022 56th Asilomar Conference on Signals, Systems, and Computers10.1109/IEEECONF56349.2022.10052045(43-47)Online publication date: 31-Oct-2022
https://doi.org/10.1109/IEEECONF56349.2022.10052045
Galke LFranke BZielke TScherp A(2021)Lifelong Learning of Graph Neural Networks for Open-World Node Classification2021 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN52387.2021.9533412(1-8)Online publication date: 18-Jul-2021
https://doi.org/10.1109/IJCNN52387.2021.9533412
Haghir Chehreghani M(2021)Sublinear update time randomized algorithms for dynamic graph regressionApplied Mathematics and Computation10.1016/j.amc.2021.126434410:COnline publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1016/j.amc.2021.126434
Herbster MPasteris STse LLarochelle HRanzato MHadsell RBalcan MLin H(2020)Online matrix completion with side informationProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497437(20402-20414)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3497437
Haghir Chehreghani M(2020)Dynamical algorithms for data mining and machine learning over dynamic graphsWIREs Data Mining and Knowledge Discovery10.1002/widm.139311:2Online publication date: 3-Nov-2020
https://doi.org/10.1002/widm.1393
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents