{"id":{"repo_id":"milano","oai_identifier":"oai:air.unimi.it:2434/155500"},"canonical_url":"https://search.dev.ndltd.org/etd/milano/oai:air.unimi.it:2434/155500","repository":{"repo_id":"milano","name":"Università degli Studi di Milano","base_url":"https://air.unimi.it/oai/request"},"display":{"title":"FAST LEARNING ON GRAPHS","abstract":"We carry out a systematic study of classification problems on networked data, presenting novel techniques with good performance both in theory and in practice. We assess the power of node classification based on class-linkage information only. In particular, we propose four new algorithms that exploit the homiphilic bias (linked entities tend to belong to the same class) in different ways. The set of the algorithms we present covers diverse practical needs: some of them operate in an active transductive setting and others in an on-line transductive setting. A third group works within an explorative protocol, in which the vertices of an unknown graph are progressively revealed to the learner in an on-line fashion. Within the mistake bound learning model, for each of our algorithms we provide a rigorous theoretical analysis, together with an interpretation of the obtained performance bounds. We also design adversarial strategies achieving matching lower bounds. In particular, we prove optimality for all input graphs and for all fixed regularity values of suitable labeling complexity measures. We also analyze the computational requirements of our methods, showing that our algorithms can to handle very large data sets. In the case of the on-line protocol, for which we exhibit an optimal algorithm with constant amortized time per prediction, we validate our theoretical results carrying out experiments on real-world datasets.","abstract_html":"We carry out a systematic study of classification problems on networked data, presenting novel techniques with good performance both in theory and in practice. We assess the power of node classification based on class-linkage information only. In particular, we propose four new algorithms that exploit the homiphilic bias (linked entities tend to belong to the same class) in different ways. The set of the algorithms we present covers diverse practical needs: some of them operate in an active transductive setting and others in an on-line transductive setting. A third group works within an explorative protocol, in which the vertices of an unknown graph are progressively revealed to the learner in an on-line fashion. Within the mistake bound learning model, for each of our algorithms we provide a rigorous theoretical analysis, together with an interpretation of the obtained performance bounds. We also design adversarial strategies achieving matching lower bounds. In particular, we prove optimality for all input graphs and for all fixed regularity values of suitable labeling complexity measures. We also analyze the computational requirements of our methods, showing that our algorithms can to handle very large data sets. In the case of the on-line protocol, for which we exhibit an optimal algorithm with constant amortized time per prediction, we validate our theoretical results carrying out experiments on real-world datasets.","abstract_has_math":false,"creators":["F. Vitale"],"institution":"Università degli Studi di Milano","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["relatore: Nicolo' Cesa-Bianchi ; correlatore: Claudio Gentile ; direttore della scuola di dottorato in informatica: Ernesto Damiani","CESA BIANCHI, NICOLO' ANTONIO"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-03-25","date_published":"2011-03-25","updated_at":"2026-07-27T20:19:17Z","subjects":["graph learning","graph prediction","graph theory","graph clustering","transductive learning","online learning","random spanning trees","random walks","node classification","effective resistance","Settore INF/01 - Informatica"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["10.13130/vitale-fabio_phd2011-03-25"],"render_values":[{"text":"10.13130/vitale-fabio_phd2011-03-25","href":"https://doi.org/10.13130/vitale-fabio_phd2011-03-25","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2434/155500","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["relatore: Nicolo' Cesa-Bianchi ; correlatore: Claudio Gentile ; direttore della scuola di dottorato in informatica: Ernesto Damiani","F. Vitale","CESA BIANCHI, NICOLO' ANTONIO"]},{"key":"dc:creator","label":"Author","values":["F. Vitale"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-03-25"]},{"key":"dc:publisher","label":"Institution","values":["Università degli Studi di Milano"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["graph learning","graph prediction","graph theory","graph clustering","transductive learning","online learning","random spanning trees","random walks","node classification","effective resistance","Settore INF/01 - Informatica"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2434/155500","10.13130/vitale-fabio_phd2011-03-25"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["We carry out a systematic study of classification problems on networked data, presenting novel techniques with good performance both in theory and in practice. We assess the power of node classification based on class-linkage information only. In particular, we propose four new algorithms that exploit the homiphilic bias (linked entities tend to belong to the same class) in different ways. The set of the algorithms we present covers diverse practical needs: some of them operate in an active transductive setting and others in an on-line transductive setting. A third group works within an explorative protocol, in which the vertices of an unknown graph are progressively revealed to the learner in an on-line fashion. Within the mistake bound learning model, for each of our algorithms we provide a rigorous theoretical analysis, together with an interpretation of the obtained performance bounds. We also design adversarial strategies achieving matching lower bounds. In particular, we prove optimality for all input graphs and for all fixed regularity values of suitable labeling complexity measures. We also analyze the computational requirements of our methods, showing that our algorithms can to handle very large data sets. In the case of the on-line protocol, for which we exhibit an optimal algorithm with constant amortized time per prediction, we validate our theoretical results carrying out experiments on real-world datasets."]},{"key":"dc:title","label":"Title","values":["FAST LEARNING ON GRAPHS"]}]}],"canonical_facts":{"dc:contributor":["relatore: Nicolo' Cesa-Bianchi ; correlatore: Claudio Gentile ; direttore della scuola di dottorato in informatica: Ernesto Damiani","F. Vitale","CESA BIANCHI, NICOLO' ANTONIO"],"dc:creator":["F. Vitale"],"dc:date":["2011-03-25"],"dc:description":["We carry out a systematic study of classification problems on networked data, presenting novel techniques with good performance both in theory and in practice. We assess the power of node classification based on class-linkage information only. In particular, we propose four new algorithms that exploit the homiphilic bias (linked entities tend to belong to the same class) in different ways. The set of the algorithms we present covers diverse practical needs: some of them operate in an active transductive setting and others in an on-line transductive setting. A third group works within an explorative protocol, in which the vertices of an unknown graph are progressively revealed to the learner in an on-line fashion. Within the mistake bound learning model, for each of our algorithms we provide a rigorous theoretical analysis, together with an interpretation of the obtained performance bounds. We also design adversarial strategies achieving matching lower bounds. In particular, we prove optimality for all input graphs and for all fixed regularity values of suitable labeling complexity measures. We also analyze the computational requirements of our methods, showing that our algorithms can to handle very large data sets. In the case of the on-line protocol, for which we exhibit an optimal algorithm with constant amortized time per prediction, we validate our theoretical results carrying out experiments on real-world datasets."],"dc:identifier":["http://hdl.handle.net/2434/155500","10.13130/vitale-fabio_phd2011-03-25"],"dc:language":["eng"],"dc:publisher":["Università degli Studi di Milano"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:subject":["graph learning","graph prediction","graph theory","graph clustering","transductive learning","online learning","random spanning trees","random walks","node classification","effective resistance","Settore INF/01 - Informatica"],"dc:title":["FAST LEARNING ON GRAPHS"],"dc:type":["info:eu-repo/semantics/doctoralThesis"]},"updated_at":"2026-07-27T20:19:17Z"}