Report
Node Copying: A Random Graph Model for Effective Graph Sampling
| العنوان: | Node Copying: A Random Graph Model for Effective Graph Sampling |
|---|---|
| المؤلفون: | Regol, Florence, Pal, Soumyasundar, Sun, Jianing, Zhang, Yingxue, Geng, Yanhui, Coates, Mark |
| المصدر: | Signal Processing, Volume 192, March 2022, 108335 |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Statistics |
| مصطلحات موضوعية: | Statistics - Machine Learning, Computer Science - Machine Learning |
| الوصف: | There has been an increased interest in applying machine learning techniques on relational structured-data based on an observed graph. Often, this graph is not fully representative of the true relationship amongst nodes. In these settings, building a generative model conditioned on the observed graph allows to take the graph uncertainty into account. Various existing techniques either rely on restrictive assumptions, fail to preserve topological properties within the samples or are prohibitively expensive for larger graphs. In this work, we introduce the node copying model for constructing a distribution over graphs. Sampling of a random graph is carried out by replacing each node's neighbors by those of a randomly sampled similar node. The sampled graphs preserve key characteristics of the graph structure without explicitly targeting them. Additionally, sampling from this model is extremely simple and scales linearly with the nodes. We show the usefulness of the copying model in three tasks. First, in node classification, a Bayesian formulation based on node copying achieves higher accuracy in sparse data settings. Second, we employ our proposed model to mitigate the effect of adversarial attacks on the graph topology. Last, incorporation of the model in a recommendation system setting improves recall over state-of-the-art methods. |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1016/j.sigpro.2021.108335 |
| URL الوصول: | http://arxiv.org/abs/2208.02435 |
| رقم الانضمام: | edsarx.2208.02435 |
| قاعدة البيانات: | arXiv |
| ResultId |
1 |
|---|---|
| Header |
edsarx arXiv edsarx.2208.02435 1037 3 Report report 1037.14147949219 |
| PLink |
https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2208.02435&custid=s6537998&authtype=sso |
| FullText |
Array
(
[Availability] => 0
)
Array ( [0] => Array ( [Url] => http://arxiv.org/abs/2208.02435 [Name] => EDS - Arxiv [Category] => fullText [Text] => View record in Arxiv [MouseOverText] => View record in Arxiv ) ) |
| Items |
Array
(
[Name] => Title
[Label] => Title
[Group] => Ti
[Data] => Node Copying: A Random Graph Model for Effective Graph Sampling
)
Array ( [Name] => Author [Label] => Authors [Group] => Au [Data] => <searchLink fieldCode="AR" term="%22Regol%2C+Florence%22">Regol, Florence</searchLink><br /><searchLink fieldCode="AR" term="%22Pal%2C+Soumyasundar%22">Pal, Soumyasundar</searchLink><br /><searchLink fieldCode="AR" term="%22Sun%2C+Jianing%22">Sun, Jianing</searchLink><br /><searchLink fieldCode="AR" term="%22Zhang%2C+Yingxue%22">Zhang, Yingxue</searchLink><br /><searchLink fieldCode="AR" term="%22Geng%2C+Yanhui%22">Geng, Yanhui</searchLink><br /><searchLink fieldCode="AR" term="%22Coates%2C+Mark%22">Coates, Mark</searchLink> ) Array ( [Name] => TitleSource [Label] => Source [Group] => Src [Data] => Signal Processing, Volume 192, March 2022, 108335 ) Array ( [Name] => DatePubCY [Label] => Publication Year [Group] => Date [Data] => 2022 ) Array ( [Name] => Subset [Label] => Collection [Group] => HoldingsInfo [Data] => Computer Science<br />Statistics ) Array ( [Name] => Subject [Label] => Subject Terms [Group] => Su [Data] => <searchLink fieldCode="DE" term="%22Statistics+-+Machine+Learning%22">Statistics - Machine Learning</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Machine+Learning%22">Computer Science - Machine Learning</searchLink> ) Array ( [Name] => Abstract [Label] => Description [Group] => Ab [Data] => There has been an increased interest in applying machine learning techniques on relational structured-data based on an observed graph. Often, this graph is not fully representative of the true relationship amongst nodes. In these settings, building a generative model conditioned on the observed graph allows to take the graph uncertainty into account. Various existing techniques either rely on restrictive assumptions, fail to preserve topological properties within the samples or are prohibitively expensive for larger graphs. In this work, we introduce the node copying model for constructing a distribution over graphs. Sampling of a random graph is carried out by replacing each node's neighbors by those of a randomly sampled similar node. The sampled graphs preserve key characteristics of the graph structure without explicitly targeting them. Additionally, sampling from this model is extremely simple and scales linearly with the nodes. We show the usefulness of the copying model in three tasks. First, in node classification, a Bayesian formulation based on node copying achieves higher accuracy in sparse data settings. Second, we employ our proposed model to mitigate the effect of adversarial attacks on the graph topology. Last, incorporation of the model in a recommendation system setting improves recall over state-of-the-art methods. ) Array ( [Name] => TypeDocument [Label] => Document Type [Group] => TypDoc [Data] => Working Paper ) Array ( [Name] => DOI [Label] => DOI [Group] => ID [Data] => 10.1016/j.sigpro.2021.108335 ) Array ( [Name] => URL [Label] => Access URL [Group] => URL [Data] => <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2208.02435" linkWindow="_blank">http://arxiv.org/abs/2208.02435</link> ) Array ( [Name] => AN [Label] => Accession Number [Group] => ID [Data] => edsarx.2208.02435 ) |
| RecordInfo |
Array
(
[BibEntity] => Array
(
[Identifiers] => Array
(
[0] => Array
(
[Type] => doi
[Value] => 10.1016/j.sigpro.2021.108335
)
)
[Subjects] => Array
(
[0] => Array
(
[SubjectFull] => Statistics - Machine Learning
[Type] => general
)
[1] => Array
(
[SubjectFull] => Computer Science - Machine Learning
[Type] => general
)
)
[Titles] => Array
(
[0] => Array
(
[TitleFull] => Node Copying: A Random Graph Model for Effective Graph Sampling
[Type] => main
)
)
)
[BibRelationships] => Array
(
[HasContributorRelationships] => Array
(
[0] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Regol, Florence
)
)
)
[1] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Pal, Soumyasundar
)
)
)
[2] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Sun, Jianing
)
)
)
[3] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Zhang, Yingxue
)
)
)
[4] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Geng, Yanhui
)
)
)
[5] => Array
(
[PersonEntity] => Array
(
[Name] => Array
(
[NameFull] => Coates, Mark
)
)
)
)
[IsPartOfRelationships] => Array
(
[0] => Array
(
[BibEntity] => Array
(
[Dates] => Array
(
[0] => Array
(
[D] => 04
[M] => 08
[Type] => published
[Y] => 2022
)
)
)
)
)
)
)
|
| IllustrationInfo |