Online Graph-Adaptive Learning with Scalability and Privacy

Yanning Shen, Geert Leus, Georgios B. Giannakis

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Graphs are widely adopted for modeling complex systems, including financial, biological, and social networks. Nodes in networks usually entail attributes, such as the age or gender of users in a social network. However, real-world networks can have very large size, and nodal attributes can be unavailable to a number of nodes, e.g., due to privacy concerns. Moreover, new nodes can emerge over time, which can necessitate real-time evaluation of their nodal attributes. In this con, this paper deals with scalable learning of nodal attributes by estimating a nodal function based on noisy observations at a subset of nodes. A multikernel-based approach is developed, which is scalable to large-size networks. Unlike most existing methods that re-solve the function estimation problem over all existing nodes whenever a new node joins the network, the novel method is capable of providing real-time evaluation of the function values on newly joining nodes without resorting to a batch solver. Interestingly, the novel scheme only relies on an encrypted version of each node's connectivity in order to learn the nodal attributes, which promotes privacy. Experiments on both synthetic and real datasets corroborate the effectiveness of the proposed methods.

Original languageEnglish (US)
Article number8666759
Pages (from-to)2471-2483
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume67
Issue number9
DOIs
StatePublished - May 1 2019

Fingerprint

Scalability
Set theory
Joining
Large scale systems
Experiments

Keywords

  • Graph signal reconstruction
  • kernel-based learning
  • learning over dynamic graphs
  • online learning

Cite this

Online Graph-Adaptive Learning with Scalability and Privacy. / Shen, Yanning; Leus, Geert; Giannakis, Georgios B.

In: IEEE Transactions on Signal Processing, Vol. 67, No. 9, 8666759, 01.05.2019, p. 2471-2483.

Research output: Contribution to journalArticle

@article{8effd8da3d794e049e4cfb0f25c2d0fc,
title = "Online Graph-Adaptive Learning with Scalability and Privacy",
abstract = "Graphs are widely adopted for modeling complex systems, including financial, biological, and social networks. Nodes in networks usually entail attributes, such as the age or gender of users in a social network. However, real-world networks can have very large size, and nodal attributes can be unavailable to a number of nodes, e.g., due to privacy concerns. Moreover, new nodes can emerge over time, which can necessitate real-time evaluation of their nodal attributes. In this con, this paper deals with scalable learning of nodal attributes by estimating a nodal function based on noisy observations at a subset of nodes. A multikernel-based approach is developed, which is scalable to large-size networks. Unlike most existing methods that re-solve the function estimation problem over all existing nodes whenever a new node joins the network, the novel method is capable of providing real-time evaluation of the function values on newly joining nodes without resorting to a batch solver. Interestingly, the novel scheme only relies on an encrypted version of each node's connectivity in order to learn the nodal attributes, which promotes privacy. Experiments on both synthetic and real datasets corroborate the effectiveness of the proposed methods.",
keywords = "Graph signal reconstruction, kernel-based learning, learning over dynamic graphs, online learning",
author = "Yanning Shen and Geert Leus and Giannakis, {Georgios B.}",
year = "2019",
month = "5",
day = "1",
doi = "10.1109/TSP.2019.2904922",
language = "English (US)",
volume = "67",
pages = "2471--2483",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

TY - JOUR

T1 - Online Graph-Adaptive Learning with Scalability and Privacy

AU - Shen, Yanning

AU - Leus, Geert

AU - Giannakis, Georgios B.

PY - 2019/5/1

Y1 - 2019/5/1

N2 - Graphs are widely adopted for modeling complex systems, including financial, biological, and social networks. Nodes in networks usually entail attributes, such as the age or gender of users in a social network. However, real-world networks can have very large size, and nodal attributes can be unavailable to a number of nodes, e.g., due to privacy concerns. Moreover, new nodes can emerge over time, which can necessitate real-time evaluation of their nodal attributes. In this con, this paper deals with scalable learning of nodal attributes by estimating a nodal function based on noisy observations at a subset of nodes. A multikernel-based approach is developed, which is scalable to large-size networks. Unlike most existing methods that re-solve the function estimation problem over all existing nodes whenever a new node joins the network, the novel method is capable of providing real-time evaluation of the function values on newly joining nodes without resorting to a batch solver. Interestingly, the novel scheme only relies on an encrypted version of each node's connectivity in order to learn the nodal attributes, which promotes privacy. Experiments on both synthetic and real datasets corroborate the effectiveness of the proposed methods.

AB - Graphs are widely adopted for modeling complex systems, including financial, biological, and social networks. Nodes in networks usually entail attributes, such as the age or gender of users in a social network. However, real-world networks can have very large size, and nodal attributes can be unavailable to a number of nodes, e.g., due to privacy concerns. Moreover, new nodes can emerge over time, which can necessitate real-time evaluation of their nodal attributes. In this con, this paper deals with scalable learning of nodal attributes by estimating a nodal function based on noisy observations at a subset of nodes. A multikernel-based approach is developed, which is scalable to large-size networks. Unlike most existing methods that re-solve the function estimation problem over all existing nodes whenever a new node joins the network, the novel method is capable of providing real-time evaluation of the function values on newly joining nodes without resorting to a batch solver. Interestingly, the novel scheme only relies on an encrypted version of each node's connectivity in order to learn the nodal attributes, which promotes privacy. Experiments on both synthetic and real datasets corroborate the effectiveness of the proposed methods.

KW - Graph signal reconstruction

KW - kernel-based learning

KW - learning over dynamic graphs

KW - online learning

UR - http://www.scopus.com/inward/record.url?scp=85064106575&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064106575&partnerID=8YFLogxK

U2 - 10.1109/TSP.2019.2904922

DO - 10.1109/TSP.2019.2904922

M3 - Article

AN - SCOPUS:85064106575

VL - 67

SP - 2471

EP - 2483

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 9

M1 - 8666759

ER -