A Deep Dive Into Understanding TheRandom Walk-Based Temporal Graph Learning Article Swipe
Nishil Talati
,
Di Jin
,
Haojie Ye
,
Ajay Brahmakshatriya
,
Ganesh Dasika
,
Saman Amarasinghe
,
Trevor Mudge
,
Danai Koutra
,
Ronald Dreslinski
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.5281/zenodo.5555384
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.5281/zenodo.5555384
Machine learning on graph data has gained significant interest because of its applicability to various domains ranging from product recommendations to drug discovery. While there is a rapid growth in the algorithmic community, the com-puter architecture community has so far focused on a subset of graph learning algorithms including Graph Convolution Network(GCN), and a few others. In this paper, we study another, more scalable, graph learning algorithm based on random walks, which operates on dynamic input graphs and has attracted less attention in the architecture community compared to GCN. We propose high-performance CPU and GPU implementations of two key graph learning tasks, that cover a broad class of applications, using random walks on continuous-time dynamic graphs: link prediction and node classification. We show that the resulting workload exhibits distinct characteristics, measured in terms of irregularity, core and memory utilization, and cache hit rates, compared to graph traversals, deep learning, and GCN. We further conduct an in-depth performance analysis focused on both algorithm and hardware to guide future software optimization and architecture exploration. The algorithm-focused study presents a rich trade-off space between algorithmic performance and runtime complexity to identify optimization opportunities. We find an optimal hyperparameter setting that strikes balance in this trade-off space. Using this setting, we also perform a detailed microarchitectural characterization to analyze hardware behavior of these applications and uncover execution bottlenecks, which include high cache misses and dependency-related stalls. The outcome of our study includes recommendations for further performance optimization, and open-source implementations for future investigation.
Related Topics
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://zenodo.org/record/5555384
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W3212503094
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3212503094Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.5281/zenodo.5555384Digital Object Identifier
- Title
-
A Deep Dive Into Understanding TheRandom Walk-Based Temporal Graph LearningWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-11-07Full publication date if available
- Authors
-
Nishil Talati, Di Jin, Haojie Ye, Ajay Brahmakshatriya, Ganesh Dasika, Saman Amarasinghe, Trevor Mudge, Danai Koutra, Ronald DreslinskiList of authors in order
- Landing page
-
https://zenodo.org/record/5555384Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://zenodo.org/record/5555384Direct OA link when available
- Concepts
-
Computer science, Artificial intelligence, Graph, Deep learning, Theoretical computer scienceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W3212503094 |
|---|---|
| doi | https://doi.org/10.5281/zenodo.5555384 |
| ids.doi | https://doi.org/10.5281/zenodo.5555384 |
| ids.mag | 3212503094 |
| ids.openalex | https://openalex.org/W3212503094 |
| fwci | 0.0 |
| type | article |
| title | A Deep Dive Into Understanding TheRandom Walk-Based Temporal Graph Learning |
| 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.9042999744415283 |
| 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 |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.5460063815116882 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C154945302 |
| concepts[1].level | 1 |
| concepts[1].score | 0.49388986825942993 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[1].display_name | Artificial intelligence |
| concepts[2].id | https://openalex.org/C132525143 |
| concepts[2].level | 2 |
| concepts[2].score | 0.46213310956954956 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[2].display_name | Graph |
| concepts[3].id | https://openalex.org/C108583219 |
| concepts[3].level | 2 |
| concepts[3].score | 0.43753716349601746 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q197536 |
| concepts[3].display_name | Deep learning |
| concepts[4].id | https://openalex.org/C80444323 |
| concepts[4].level | 1 |
| concepts[4].score | 0.12295439839363098 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[4].display_name | Theoretical computer science |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.5460063815116882 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[1].score | 0.49388986825942993 |
| keywords[1].display_name | Artificial intelligence |
| keywords[2].id | https://openalex.org/keywords/graph |
| keywords[2].score | 0.46213310956954956 |
| keywords[2].display_name | Graph |
| keywords[3].id | https://openalex.org/keywords/deep-learning |
| keywords[3].score | 0.43753716349601746 |
| keywords[3].display_name | Deep learning |
| keywords[4].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[4].score | 0.12295439839363098 |
| keywords[4].display_name | Theoretical computer science |
| language | en |
| locations[0].id | pmh:oai:zenodo.org:5555384 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400562 |
| 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 | Zenodo (CERN European Organization for Nuclear Research) |
| locations[0].source.host_organization | https://openalex.org/I67311998 |
| locations[0].source.host_organization_name | European Organization for Nuclear Research |
| locations[0].source.host_organization_lineage | https://openalex.org/I67311998 |
| locations[0].license | other-oa |
| locations[0].pdf_url | |
| locations[0].version | submittedVersion |
| locations[0].raw_type | info:eu-repo/semantics/conferencePaper |
| locations[0].license_id | https://openalex.org/licenses/other-oa |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://zenodo.org/record/5555384 |
| locations[1].id | doi:10.5281/zenodo.5555384 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400562 |
| 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 | Zenodo (CERN European Organization for Nuclear Research) |
| locations[1].source.host_organization | https://openalex.org/I67311998 |
| locations[1].source.host_organization_name | European Organization for Nuclear Research |
| locations[1].source.host_organization_lineage | https://openalex.org/I67311998 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.5281/zenodo.5555384 |
| indexed_in | datacite |
| authorships[0].author.id | https://openalex.org/A5063661349 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-2457-4119 |
| authorships[0].author.display_name | Nishil Talati |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Nishil Talati |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5012455357 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-7445-9936 |
| authorships[1].author.display_name | Di Jin |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Di Jin |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5028799837 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-5360-5159 |
| authorships[2].author.display_name | Haojie Ye |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Haojie Ye |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5046807118 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-5295-4186 |
| authorships[3].author.display_name | Ajay Brahmakshatriya |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Ajay Brahmakshatriya |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5004292742 |
| authorships[4].author.orcid | |
| authorships[4].author.display_name | Ganesh Dasika |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Ganesh Dasika |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5046791216 |
| authorships[5].author.orcid | https://orcid.org/0000-0002-7231-7643 |
| authorships[5].author.display_name | Saman Amarasinghe |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Saman Amarasinghe |
| authorships[5].is_corresponding | False |
| authorships[6].author.id | https://openalex.org/A5037541525 |
| authorships[6].author.orcid | https://orcid.org/0000-0001-7845-2187 |
| authorships[6].author.display_name | Trevor Mudge |
| authorships[6].author_position | middle |
| authorships[6].raw_author_name | Trevor Mudge |
| authorships[6].is_corresponding | False |
| authorships[7].author.id | https://openalex.org/A5015996266 |
| authorships[7].author.orcid | https://orcid.org/0000-0002-3206-8179 |
| authorships[7].author.display_name | Danai Koutra |
| authorships[7].author_position | middle |
| authorships[7].raw_author_name | Danai Koutra |
| authorships[7].is_corresponding | False |
| authorships[8].author.id | https://openalex.org/A5014250626 |
| authorships[8].author.orcid | |
| authorships[8].author.display_name | Ronald Dreslinski |
| authorships[8].author_position | last |
| authorships[8].raw_author_name | Ronald Dreslinski |
| authorships[8].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://zenodo.org/record/5555384 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | A Deep Dive Into Understanding TheRandom Walk-Based Temporal Graph Learning |
| 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.9042999744415283 |
| 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 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:zenodo.org:5555384 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400562 |
| 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 | Zenodo (CERN European Organization for Nuclear Research) |
| best_oa_location.source.host_organization | https://openalex.org/I67311998 |
| best_oa_location.source.host_organization_name | European Organization for Nuclear Research |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I67311998 |
| best_oa_location.license | other-oa |
| best_oa_location.pdf_url | |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | info:eu-repo/semantics/conferencePaper |
| best_oa_location.license_id | https://openalex.org/licenses/other-oa |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://zenodo.org/record/5555384 |
| primary_location.id | pmh:oai:zenodo.org:5555384 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400562 |
| 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 | Zenodo (CERN European Organization for Nuclear Research) |
| primary_location.source.host_organization | https://openalex.org/I67311998 |
| primary_location.source.host_organization_name | European Organization for Nuclear Research |
| primary_location.source.host_organization_lineage | https://openalex.org/I67311998 |
| primary_location.license | other-oa |
| primary_location.pdf_url | |
| primary_location.version | submittedVersion |
| primary_location.raw_type | info:eu-repo/semantics/conferencePaper |
| primary_location.license_id | https://openalex.org/licenses/other-oa |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://zenodo.org/record/5555384 |
| publication_date | 2021-11-07 |
| publication_year | 2021 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 26, 42, 53, 104, 176, 209 |
| abstract_inverted_index.In | 56 |
| abstract_inverted_index.We | 89, 121, 151, 190 |
| abstract_inverted_index.an | 154, 192 |
| abstract_inverted_index.in | 29, 82, 131, 199 |
| abstract_inverted_index.is | 25 |
| abstract_inverted_index.of | 10, 44, 96, 107, 133, 217, 234 |
| abstract_inverted_index.on | 2, 41, 68, 73, 112, 159 |
| abstract_inverted_index.so | 38 |
| abstract_inverted_index.to | 13, 20, 87, 144, 164, 186, 213 |
| abstract_inverted_index.we | 59, 206 |
| abstract_inverted_index.CPU | 92 |
| abstract_inverted_index.GPU | 94 |
| abstract_inverted_index.The | 172, 232 |
| abstract_inverted_index.and | 52, 77, 93, 118, 136, 139, 149, 162, 169, 183, 220, 229, 243 |
| abstract_inverted_index.far | 39 |
| abstract_inverted_index.few | 54 |
| abstract_inverted_index.for | 239, 246 |
| abstract_inverted_index.has | 5, 37, 78 |
| abstract_inverted_index.hit | 141 |
| abstract_inverted_index.its | 11 |
| abstract_inverted_index.key | 98 |
| abstract_inverted_index.our | 235 |
| abstract_inverted_index.the | 30, 33, 83, 124 |
| abstract_inverted_index.two | 97 |
| abstract_inverted_index.GCN. | 88, 150 |
| abstract_inverted_index.also | 207 |
| abstract_inverted_index.both | 160 |
| abstract_inverted_index.core | 135 |
| abstract_inverted_index.data | 4 |
| abstract_inverted_index.deep | 147 |
| abstract_inverted_index.drug | 21 |
| abstract_inverted_index.find | 191 |
| abstract_inverted_index.from | 17 |
| abstract_inverted_index.high | 226 |
| abstract_inverted_index.less | 80 |
| abstract_inverted_index.link | 116 |
| abstract_inverted_index.more | 62 |
| abstract_inverted_index.node | 119 |
| abstract_inverted_index.rich | 177 |
| abstract_inverted_index.show | 122 |
| abstract_inverted_index.that | 102, 123, 196 |
| abstract_inverted_index.this | 57, 200, 204 |
| abstract_inverted_index.Graph | 49 |
| abstract_inverted_index.Using | 203 |
| abstract_inverted_index.While | 23 |
| abstract_inverted_index.based | 67 |
| abstract_inverted_index.broad | 105 |
| abstract_inverted_index.cache | 140, 227 |
| abstract_inverted_index.class | 106 |
| abstract_inverted_index.cover | 103 |
| abstract_inverted_index.graph | 3, 45, 64, 99, 145 |
| abstract_inverted_index.guide | 165 |
| abstract_inverted_index.input | 75 |
| abstract_inverted_index.rapid | 27 |
| abstract_inverted_index.space | 179 |
| abstract_inverted_index.study | 60, 174, 236 |
| abstract_inverted_index.terms | 132 |
| abstract_inverted_index.there | 24 |
| abstract_inverted_index.these | 218 |
| abstract_inverted_index.using | 109 |
| abstract_inverted_index.walks | 111 |
| abstract_inverted_index.which | 71, 224 |
| abstract_inverted_index.future | 166, 247 |
| abstract_inverted_index.gained | 6 |
| abstract_inverted_index.graphs | 76 |
| abstract_inverted_index.growth | 28 |
| abstract_inverted_index.memory | 137 |
| abstract_inverted_index.misses | 228 |
| abstract_inverted_index.paper, | 58 |
| abstract_inverted_index.random | 69, 110 |
| abstract_inverted_index.rates, | 142 |
| abstract_inverted_index.space. | 202 |
| abstract_inverted_index.subset | 43 |
| abstract_inverted_index.tasks, | 101 |
| abstract_inverted_index.walks, | 70 |
| abstract_inverted_index.Machine | 0 |
| abstract_inverted_index.analyze | 214 |
| abstract_inverted_index.balance | 198 |
| abstract_inverted_index.because | 9 |
| abstract_inverted_index.between | 180 |
| abstract_inverted_index.conduct | 153 |
| abstract_inverted_index.domains | 15 |
| abstract_inverted_index.dynamic | 74, 114 |
| abstract_inverted_index.focused | 40, 158 |
| abstract_inverted_index.further | 152, 240 |
| abstract_inverted_index.graphs: | 115 |
| abstract_inverted_index.include | 225 |
| abstract_inverted_index.optimal | 193 |
| abstract_inverted_index.others. | 55 |
| abstract_inverted_index.outcome | 233 |
| abstract_inverted_index.perform | 208 |
| abstract_inverted_index.product | 18 |
| abstract_inverted_index.propose | 90 |
| abstract_inverted_index.ranging | 16 |
| abstract_inverted_index.runtime | 184 |
| abstract_inverted_index.setting | 195 |
| abstract_inverted_index.stalls. | 231 |
| abstract_inverted_index.strikes | 197 |
| abstract_inverted_index.uncover | 221 |
| abstract_inverted_index.various | 14 |
| abstract_inverted_index.analysis | 157 |
| abstract_inverted_index.another, | 61 |
| abstract_inverted_index.behavior | 216 |
| abstract_inverted_index.compared | 86, 143 |
| abstract_inverted_index.detailed | 210 |
| abstract_inverted_index.distinct | 128 |
| abstract_inverted_index.exhibits | 127 |
| abstract_inverted_index.hardware | 163, 215 |
| abstract_inverted_index.identify | 187 |
| abstract_inverted_index.in-depth | 155 |
| abstract_inverted_index.includes | 237 |
| abstract_inverted_index.interest | 8 |
| abstract_inverted_index.learning | 1, 46, 65, 100 |
| abstract_inverted_index.measured | 130 |
| abstract_inverted_index.operates | 72 |
| abstract_inverted_index.presents | 175 |
| abstract_inverted_index.setting, | 205 |
| abstract_inverted_index.software | 167 |
| abstract_inverted_index.workload | 126 |
| abstract_inverted_index.algorithm | 66, 161 |
| abstract_inverted_index.attention | 81 |
| abstract_inverted_index.attracted | 79 |
| abstract_inverted_index.com-puter | 34 |
| abstract_inverted_index.community | 36, 85 |
| abstract_inverted_index.execution | 222 |
| abstract_inverted_index.including | 48 |
| abstract_inverted_index.learning, | 148 |
| abstract_inverted_index.resulting | 125 |
| abstract_inverted_index.scalable, | 63 |
| abstract_inverted_index.trade-off | 178, 201 |
| abstract_inverted_index.algorithms | 47 |
| abstract_inverted_index.community, | 32 |
| abstract_inverted_index.complexity | 185 |
| abstract_inverted_index.discovery. | 22 |
| abstract_inverted_index.prediction | 117 |
| abstract_inverted_index.Convolution | 50 |
| abstract_inverted_index.algorithmic | 31, 181 |
| abstract_inverted_index.open-source | 244 |
| abstract_inverted_index.performance | 156, 182, 241 |
| abstract_inverted_index.significant | 7 |
| abstract_inverted_index.traversals, | 146 |
| abstract_inverted_index.applications | 219 |
| abstract_inverted_index.architecture | 35, 84, 170 |
| abstract_inverted_index.bottlenecks, | 223 |
| abstract_inverted_index.exploration. | 171 |
| abstract_inverted_index.optimization | 168, 188 |
| abstract_inverted_index.utilization, | 138 |
| abstract_inverted_index.Network(GCN), | 51 |
| abstract_inverted_index.applicability | 12 |
| abstract_inverted_index.applications, | 108 |
| abstract_inverted_index.irregularity, | 134 |
| abstract_inverted_index.optimization, | 242 |
| abstract_inverted_index.hyperparameter | 194 |
| abstract_inverted_index.investigation. | 248 |
| abstract_inverted_index.opportunities. | 189 |
| abstract_inverted_index.classification. | 120 |
| abstract_inverted_index.continuous-time | 113 |
| abstract_inverted_index.implementations | 95, 245 |
| abstract_inverted_index.recommendations | 19, 238 |
| abstract_inverted_index.characteristics, | 129 |
| abstract_inverted_index.characterization | 212 |
| abstract_inverted_index.high-performance | 91 |
| abstract_inverted_index.algorithm-focused | 173 |
| abstract_inverted_index.dependency-related | 230 |
| abstract_inverted_index.microarchitectural | 211 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 9 |
| citation_normalized_percentile.value | 0.16495545 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |