Graph Neural Tangent Kernel: Convergence on Large Graphs Article Swipe

PDF

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2301.10808

Graph neural networks (GNNs) achieve remarkable performance in graph machine learning tasks but can be hard to train on large-graph data, where their learning dynamics are not well understood. We investigate the training dynamics of large-graph GNNs using graph neural tangent kernels (GNTKs) and graphons. In the limit of large width, optimization of an overparametrized NN is equivalent to kernel regression on the NTK. Here, we investigate how the GNTK evolves as another independent dimension is varied: the graph size. We use graphons to define limit objects -- graphon NNs for GNNs, and graphon NTKs for GNTKs -- , and prove that, on a sequence of graphs, the GNTKs converge to the graphon NTK. We further prove that the spectrum of the GNTK, which is related to the directions of fastest learning which becomes relevant during early stopping, converges to the spectrum of the graphon NTK. This implies that in the large-graph limit, the GNTK fitted on a graph of moderate size can be used to solve the same task on the large graph, and to infer the learning dynamics of the large-graph GNN. These results are verified empirically on node regression and classification tasks.

Related Topics

Theoretical Computer Science

Geometry

Concepts

Graph Computer science Line graph Tangent Voltage graph Algorithm Combinatorics Mathematics Theoretical computer science Geometry

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2301.10808
PDF: https://arxiv.org/pdf/2301.10808
OA Status: green
Cited By: 4
Related Works: 10
OpenAlex ID: https://openalex.org/W4318347779

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4318347779

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2301.10808

Digital Object Identifier
Title: Graph Neural Tangent Kernel: Convergence on Large Graphs

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-01-25

Full publication date if available
Authors: Sanjukta Krishnagopal, Luana Ruiz

List of authors in order
Landing page: https://arxiv.org/abs/2301.10808

Publisher landing page
PDF URL: https://arxiv.org/pdf/2301.10808

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2301.10808

Direct OA link when available
Concepts: Graph, Computer science, Line graph, Tangent, Voltage graph, Algorithm, Combinatorics, Mathematics, Theoretical computer science, Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 4

Total citation count in OpenAlex
Citations by year (recent): 2024: 3, 2023: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4318347779
doi	https://doi.org/10.48550/arxiv.2301.10808
ids.doi	https://doi.org/10.48550/arxiv.2301.10808
ids.openalex	https://openalex.org/W4318347779
fwci
type	preprint
title	Graph Neural Tangent Kernel: Convergence on Large Graphs
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11273
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9990000128746033
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Advanced Graph Neural Networks
topics[1].id	https://openalex.org/T11948
topics[1].field.id	https://openalex.org/fields/25
topics[1].field.display_name	Materials Science
topics[1].score	0.9599000215530396
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2505
topics[1].subfield.display_name	Materials Chemistry
topics[1].display_name	Machine Learning in Materials Science
topics[2].id	https://openalex.org/T10241
topics[2].field.id	https://openalex.org/fields/28
topics[2].field.display_name	Neuroscience
topics[2].score	0.9239000082015991
topics[2].domain.id	https://openalex.org/domains/1
topics[2].domain.display_name	Life Sciences
topics[2].subfield.id	https://openalex.org/subfields/2805
topics[2].subfield.display_name	Cognitive Neuroscience
topics[2].display_name	Functional Brain Connectivity Studies
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C132525143
concepts[0].level	2
concepts[0].score	0.6294085383415222
concepts[0].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[0].display_name	Graph
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.5211008787155151
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C203776342
concepts[2].level	3
concepts[2].score	0.49458739161491394
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1378376
concepts[2].display_name	Line graph
concepts[3].id	https://openalex.org/C138187205
concepts[3].level	2
concepts[3].score	0.45138296484947205
concepts[3].wikidata	https://www.wikidata.org/wiki/Q131251
concepts[3].display_name	Tangent
concepts[4].id	https://openalex.org/C22149727
concepts[4].level	4
concepts[4].score	0.4156011939048767
concepts[4].wikidata	https://www.wikidata.org/wiki/Q7940747
concepts[4].display_name	Voltage graph
concepts[5].id	https://openalex.org/C11413529
concepts[5].level	1
concepts[5].score	0.3941720426082611
concepts[5].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[5].display_name	Algorithm
concepts[6].id	https://openalex.org/C114614502
concepts[6].level	1
concepts[6].score	0.3717186450958252
concepts[6].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[6].display_name	Combinatorics
concepts[7].id	https://openalex.org/C33923547
concepts[7].level	0
concepts[7].score	0.3558061718940735
concepts[7].wikidata	https://www.wikidata.org/wiki/Q395
concepts[7].display_name	Mathematics
concepts[8].id	https://openalex.org/C80444323
concepts[8].level	1
concepts[8].score	0.30809974670410156
concepts[8].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[8].display_name	Theoretical computer science
concepts[9].id	https://openalex.org/C2524010
concepts[9].level	1
concepts[9].score	0.0
concepts[9].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[9].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/graph
keywords[0].score	0.6294085383415222
keywords[0].display_name	Graph
keywords[1].id	https://openalex.org/keywords/computer-science
keywords[1].score	0.5211008787155151
keywords[1].display_name	Computer science
keywords[2].id	https://openalex.org/keywords/line-graph
keywords[2].score	0.49458739161491394
keywords[2].display_name	Line graph
keywords[3].id	https://openalex.org/keywords/tangent
keywords[3].score	0.45138296484947205
keywords[3].display_name	Tangent
keywords[4].id	https://openalex.org/keywords/voltage-graph
keywords[4].score	0.4156011939048767
keywords[4].display_name	Voltage graph
keywords[5].id	https://openalex.org/keywords/algorithm
keywords[5].score	0.3941720426082611
keywords[5].display_name	Algorithm
keywords[6].id	https://openalex.org/keywords/combinatorics
keywords[6].score	0.3717186450958252
keywords[6].display_name	Combinatorics
keywords[7].id	https://openalex.org/keywords/mathematics
keywords[7].score	0.3558061718940735
keywords[7].display_name	Mathematics
keywords[8].id	https://openalex.org/keywords/theoretical-computer-science
keywords[8].score	0.30809974670410156
keywords[8].display_name	Theoretical computer science
language	en
locations[0].id	pmh:oai:arXiv.org:2301.10808
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2301.10808
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2301.10808
locations[1].id	doi:10.48550/arxiv.2301.10808
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2301.10808
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5002601106
authorships[0].author.orcid	https://orcid.org/0000-0002-1556-404X
authorships[0].author.display_name	Sanjukta Krishnagopal
authorships[0].author_position	first
authorships[0].raw_author_name	Krishnagopal, Sanjukta
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5036583414
authorships[1].author.orcid	https://orcid.org/0000-0002-9666-1211
authorships[1].author.display_name	Luana Ruiz
authorships[1].author_position	last
authorships[1].raw_author_name	Ruiz, Luana
authorships[1].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2301.10808
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Graph Neural Tangent Kernel: Convergence on Large Graphs
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11273
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9990000128746033
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Advanced Graph Neural Networks
related_works	https://openalex.org/W2903067171, https://openalex.org/W2380035736, https://openalex.org/W1927597435, https://openalex.org/W3207232533, https://openalex.org/W1568744482, https://openalex.org/W4299307887, https://openalex.org/W2952803432, https://openalex.org/W2106452164, https://openalex.org/W2389138578, https://openalex.org/W2954009223
cited_by_count	4
counts_by_year[0].year	2024
counts_by_year[0].cited_by_count	3
counts_by_year[1].year	2023
counts_by_year[1].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2301.10808
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2301.10808
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2301.10808
primary_location.id	pmh:oai:arXiv.org:2301.10808
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2301.10808
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2301.10808
publication_date	2023-01-25
publication_year	2023
referenced_works_count	0
abstract_inverted_index.,	98
abstract_inverted_index.a	103, 157
abstract_inverted_index.--	87, 97
abstract_inverted_index.In	45
abstract_inverted_index.NN	55
abstract_inverted_index.We	29, 80, 114
abstract_inverted_index.an	53
abstract_inverted_index.as	71
abstract_inverted_index.be	14, 163
abstract_inverted_index.in	7, 149
abstract_inverted_index.is	56, 75, 124
abstract_inverted_index.of	34, 48, 52, 105, 120, 129, 142, 159, 180
abstract_inverted_index.on	18, 61, 102, 156, 170, 189
abstract_inverted_index.to	16, 58, 83, 110, 126, 139, 165, 175
abstract_inverted_index.we	65
abstract_inverted_index.NNs	89
abstract_inverted_index.and	43, 92, 99, 174, 192
abstract_inverted_index.are	25, 186
abstract_inverted_index.but	12
abstract_inverted_index.can	13, 162
abstract_inverted_index.for	90, 95
abstract_inverted_index.how	67
abstract_inverted_index.not	26
abstract_inverted_index.the	31, 46, 62, 68, 77, 107, 111, 118, 121, 127, 140, 143, 150, 153, 167, 171, 177, 181
abstract_inverted_index.use	81
abstract_inverted_index.GNN.	183
abstract_inverted_index.GNNs	36
abstract_inverted_index.GNTK	69, 154
abstract_inverted_index.NTK.	63, 113, 145
abstract_inverted_index.NTKs	94
abstract_inverted_index.This	146
abstract_inverted_index.hard	15
abstract_inverted_index.node	190
abstract_inverted_index.same	168
abstract_inverted_index.size	161
abstract_inverted_index.task	169
abstract_inverted_index.that	117, 148
abstract_inverted_index.used	164
abstract_inverted_index.well	27
abstract_inverted_index.GNNs,	91
abstract_inverted_index.GNTK,	122
abstract_inverted_index.GNTKs	96, 108
abstract_inverted_index.Graph	0
abstract_inverted_index.Here,	64
abstract_inverted_index.These	184
abstract_inverted_index.data,	20
abstract_inverted_index.early	136
abstract_inverted_index.graph	8, 38, 78, 158
abstract_inverted_index.infer	176
abstract_inverted_index.large	49, 172
abstract_inverted_index.limit	47, 85
abstract_inverted_index.prove	100, 116
abstract_inverted_index.size.	79
abstract_inverted_index.solve	166
abstract_inverted_index.tasks	11
abstract_inverted_index.that,	101
abstract_inverted_index.their	22
abstract_inverted_index.train	17
abstract_inverted_index.using	37
abstract_inverted_index.where	21
abstract_inverted_index.which	123, 132
abstract_inverted_index.(GNNs)	3
abstract_inverted_index.define	84
abstract_inverted_index.during	135
abstract_inverted_index.fitted	155
abstract_inverted_index.graph,	173
abstract_inverted_index.kernel	59
abstract_inverted_index.limit,	152
abstract_inverted_index.neural	1, 39
abstract_inverted_index.tasks.	194
abstract_inverted_index.width,	50
abstract_inverted_index.(GNTKs)	42
abstract_inverted_index.achieve	4
abstract_inverted_index.another	72
abstract_inverted_index.becomes	133
abstract_inverted_index.evolves	70
abstract_inverted_index.fastest	130
abstract_inverted_index.further	115
abstract_inverted_index.graphon	88, 93, 112, 144
abstract_inverted_index.graphs,	106
abstract_inverted_index.implies	147
abstract_inverted_index.kernels	41
abstract_inverted_index.machine	9
abstract_inverted_index.objects	86
abstract_inverted_index.related	125
abstract_inverted_index.results	185
abstract_inverted_index.tangent	40
abstract_inverted_index.varied:	76
abstract_inverted_index.converge	109
abstract_inverted_index.dynamics	24, 33, 179
abstract_inverted_index.graphons	82
abstract_inverted_index.learning	10, 23, 131, 178
abstract_inverted_index.moderate	160
abstract_inverted_index.networks	2
abstract_inverted_index.relevant	134
abstract_inverted_index.sequence	104
abstract_inverted_index.spectrum	119, 141
abstract_inverted_index.training	32
abstract_inverted_index.verified	187
abstract_inverted_index.converges	138
abstract_inverted_index.dimension	74
abstract_inverted_index.graphons.	44
abstract_inverted_index.stopping,	137
abstract_inverted_index.directions	128
abstract_inverted_index.equivalent	57
abstract_inverted_index.regression	60, 191
abstract_inverted_index.remarkable	5
abstract_inverted_index.empirically	188
abstract_inverted_index.independent	73
abstract_inverted_index.investigate	30, 66
abstract_inverted_index.large-graph	19, 35, 151, 182
abstract_inverted_index.performance	6
abstract_inverted_index.understood.	28
abstract_inverted_index.optimization	51
abstract_inverted_index.classification	193
abstract_inverted_index.overparametrized	54
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile