Efficient Learning of Linear Graph Neural Networks
via Node Subsampling
Seiyun Shin, Ilan Shomorony, and Han Zhao
University of Illinois at Urbana-Champaign

Graph Neural Networks (GNNs)¨

Two-stage Training Algorithm

Powerful models for graph-structured data

Numerical Results: Run-time Comparison
DatasetFor regression tasks, lev. score sampling has a nice guarantee
C

𝑿𝑨

A
𝑿𝑩

𝑿𝑪

B

C

𝑿𝑫

C

B

𝑿𝑬

E

A
B
D
F

D

E

F 𝑿𝑭

¨

Workaround:
Step 1: Estimate leverage scores

Step 2: Use leverage score estimate for training<latexit sha1_base64="D01Nf6TIaSbI5cxzi/3aYPKCnQ0=">AAAB8HicbVBNS8NAEN3Ur1q/qh69LBbBU0lU1GPVi8cK9kPaUDababt0swm7E6GE/govHhTx6s/x5r9x2+ag1QcDj/dmmJkXJFIYdN0vp7C0vLK6VlwvbWxube+Ud/eaJk41hwaPZazbATMghYIGCpTQTjSwKJDQCkY3U7/1CNqIWN3jOAE/YgMl+oIztNJDF4UMIbua9MoVt+rOQP8SLycVkqPeK392w5inESjkkhnT8dwE/YxpFFzCpNRNDSSMj9gAOpYqFoHxs9nBE3pklZD2Y21LIZ2pPycyFhkzjgLbGTEcmkVvKv7ndVLsX/qZUEmKoPh8UT+VFGM6/Z6GQgNHObaEcS3srZQPmWYcbUYlG4K3+PJf0jypeufV07uzSu06j6NIDsghOSYeuSA1ckvqpEE4icgTeSGvjnaenTfnfd5acPKZffILzsc38leQgw==</latexit>bAÃ

<latexit sha1_base64="Zb56woiQ30x32Eyi9WF+fKfoVqo=">AAADGXicbVJba9swFFa8W+ddmm6PexEzgTFGiEN3eRl0jEIfNuggaQNxCLJ8nIhKspGOW4LwL+nr9kP2Nvbap/2N/YIprhlLugOWP76LdCyftJTC4mDwqxPcun3n7r2d++GDh48e73b3npzYojIcxryQhZmkzIIUGsYoUMKkNMBUKuE0Pfu41k/PwVhR6BGuSpgpttAiF5yhp+bd3eRCZLBk6D5MavqezrvRoD9oit4EcQsi0tbxfK/zO8kKXinQyCWzdhoPSpw5ZlBwCXWYVBZKxs/YAqYeaqbAzlzTeU17nsloXhj/aKQN+2/CMWXtSqXeqRgu7ba2Jv+nTSvM382c0GWFoPn1QXklKRZ0fQ00EwY4ypUHjBvhe6V8yQzj6C8rTDLIk5FzifVaie2KKwlJc1TuRnXtP82AhgteKMV09tIl58DraTxzjSnNXRSvTRuWw7pVU3foxd6mGv9VlVtnw7BHP/k/ywxlcgGpYVvboWkTRjmP/Yb0s7AcpGQaispu2aG0dbMKWejt1kRZT4e+eQk5Jj6/kECj+BWNhjQxYrFE/2rYOvRTEm/PxE1wMuzHb/qvv+xHB/vtvOyQZ+Q5eUFi8pYckCNyTMaEk4pckq/kW3AZfA9+BD+vrUGnzTwlGxVc/QFUsQCK</latexit>B¨

Many applications:¨ Recommender systems, social network, drug discovery etc.
Being able to train GNNs efficiently is an important task!

d=AXlinear GNN
architecture<latexit sha1_base64="95UQky/LG9OfyVI7lIXyjNzNAqg=">AAADE3icbVLbatRAGJ6NpxpPrV56MxgKIrJslnq4rEjBC4UKu20hWcpk8md36BzCzJ+WZchj9FYfxDvx1gfwNXwCZ9Mg7tYfMvn4DjN/Jn9RS+FwNPo1iG7cvHX7ztbd+N79Bw8fbe88PnKmsRym3EhjTwrmQAoNUxQo4aS2wFQh4bg4e7/Sj8/BOmH0BJc1zBSba1EJzjBQWX4hSlgw9O/a0+1kNBx1Ra+DtAcJ6evwdGfwOy8NbxRo5JI5l6WjGmeeWRRcQhvnjYOa8TM2hyxAzRS4me96buluYEpaGRsejbRj/014ppxbqiI4FcOF29RW5P+0rMHq7cwLXTcIml8dVDWSoqGrC6ClsMBRLgNg3IrQK+ULZhnHcE1xXkKVT7zPXdBq7FdcSsi7oyo/advwaRY0XHCjFNPlC5+fA2+zdOY7U1H5JF2Z1iwHba8W/iCIu+tq+ldVfpWN4136MfxTZimTcygs29gObZ+wygccNqSfhOMgJdNgGrdhh9q13Sqk0ZutibrNxqF5CRXmIT+XQJP0JU3GNLdivsDw6tg2DlOSbs7EdXA0Hqavh68+7yX7e/28bJGn5Bl5TlLyhuyTD+SQTAknhlySL+RrdBl9i75HP66s0aDPPCFrFf38A9q8/00=</latexit><latexit sha1_base64="PUOt3UzikYXrLmWx6jPnq1lkuqo=">AAADE3icbVLLatwwFNW4r9R9JGmX3YiagVLKYA/pYxkogS5aSGEmGbCHIMvXHhE9jCQnDMKfkW37Id2VbvsB/Y1+QWXHlM6kFywfzkO6lm9ec2ZsHP8aBbdu37l7b+d++ODho8e7e/tPToxqNIU5VVzpRU4McCZhbpnlsKg1EJFzOM3P33f66QVow5Sc2XUNS0EqyUpGifVUml2yAlbEukV7thfFk7gvfBMkA4jQUMdn+6PfWaFoI0BayokxaRLXdumItoxyaMOsMVATek4qSD2URIBZur7nFo89U+BSaf9Ii3v234Qjwpi1yL1TELsy21pH/k9LG1u+Wzom68aCpNcHlQ3HVuHuAnDBNFDL1x4QqpnvFdMV0YRaf01hVkCZzZzLjNdqO6x2zSHrjyrdrG39p2mQcEmVEEQWL112AbRNk6XrTXnpoqQzbViO2kHN3ZEXx5tq8lcVrsuG4Rh/9P+UaEx4BbkmW9tZPSS0cB77DfEnZihwTiSoxmzZoTZtvzKu5HZrrG7TqW+eQ2kzn6844Ch5haMpzjSrVta/erYN/ZQk2zNxE5xMJ8mbyevPB9HhwTAvO+gZeo5eoAS9RYfoAzpGc0SRQlfoC/oaXAXfgu/Bj2trMBoyT9FGBT//ABe1/2Q=</latexit>⇥<latexit sha1_base64="aMXuEvqOzCy8m2McnzR37VSViNc=">AAADDnicbVLLatwwFNW4r9R9Je2yG1EzUEoZxkP6WAZKoIsWUpiZBGwTZM31jBJJNtJ1yiD8D9m2H9Jd6ba/0N/oF1R2TOlMesHy4Z5zdK+km1dSWByPfw2CGzdv3b6zcze8d//Bw0e7e4/ntqwNhxkvZWlOcmZBCg0zFCjhpDLAVC7hOD9/1/LHF2CsKPUU1xVkii21KARn6FPzFIUCe7objUfjLuh1EPcgIn0cne4NfqeLktcKNHLJrE3icYWZYwYFl9CEaW2hYvycLSHxUDNfJXNduw0d+syCFqXxn0baZf91OKasXavcKxXDld3m2uT/uKTG4m3mhK5qBM2vChW1pFjS9ux0IQxwlGsPGDfC90r5ihnG0d9QmC6gSKfOpdZzFfYrriWkXanCTZvGH82Ahs+8VIrpxQuXXgBvkjhznSgvXBS3og3JYdOzuTv05HCTjf+yyrXeMBzSD/45maFMLiE3bGs7NL3DKOex35B+FJaDlExDWdstOVS26VYhS73dmqiaZOKbl1Bg6v1LCTSKX9JoQlMjliv0vy7bhH5K4u2ZuA7mk1H8evTq0350sN/Pyw55Sp6R5yQmb8gBeU+OyIxwckYuyRfyNbgMvgXfgx9X0mDQe56QjQh+/gHJwP0e</latexit>b
X<latexit sha1_base64="EqhH/8tDQBtvTYEB9wDg5WVBfms=">AAADK3icbVJdb9MwFHXD1whf3XjkxRBVGgiqphqMxyE0iQeQhtRulZKocpyb1prtRLazqTJ55tfsFX4ITyBe+QP8ApwsQrTjSnGO7jnHvr6+acmZNqPR95537fqNm7e2bvt37t67/6C/vXOsi0pRmNKCF2qWEg2cSZgaZjjMSgVEpBxO0tO3DX9yBkqzQk7MqoREkIVkOaPEuNS8/zgGzudsN4rPWQZLYuybWf0Jv8DxGVC7qpOn834wGo7awFdB2IEAdXE03+79jrOCVgKkoZxoHYWj0iSWKMMoh9qPKw0loadkAZGDkgjQiW3vUuOBy2Q4L5T7pMFt9l+HJULrlUidUhCz1Jtck/wfF1Umf51YJsvKgKSXB+UVx6bATWNwxhRQw1cOEKqYqxXTJVGEGtc+P84gjyfWxtpxpelWs+IQt0fldlLX7moKJJzTQggis2e2aWIdhYltRWlug7ARrUkO645N7aEjB+ts+JcVtvH6/gC/d29NFCZ8AakiG9sZ1TmUsA67DfEHpql7ZSKhqPSGHEpdtyvjhdwsjZV1NHbFc8hN7PwLDjgIn+NgjGPFFkvjfm229t2UhJszcRUcj4fhq+HLj3vBwV43L1voEXqCdlGI9tEBeoeO0BRR9BldoC/oq3fhffN+eD8vpV6v8zxEa+H9+gPUlAgf</latexit>d`i ([AX|<latexit sha1_base64="Y+vAQS8uSRaHqPVwkCbzM5iJz+E=">AAADEXicbVLdatRAFJ6NfzX+tXrpzWBYEJFls1Tby4oUvFCosNtWNkuZTE52h85MwsxJZRnyFL3VB/FOvPUJfA2fwEkaxE09kMnH9zNzJjlpKYXF8fjXILhx89btO1t3w3v3Hzx8tL3z+NgWleEw44UszGnKLEihYYYCJZyWBphKJZyk528b/eQCjBWFnuK6hIViSy1ywRl66lOCQmbg3tRn29F4NG6LXgdxByLS1dHZzuB3khW8UqCRS2btPB6XuHDMoOAS6jCpLJSMn7MlzD3UTIFduLbjmg49k9G8MP7RSFv234Rjytq1Sr1TMVzZvtaQ/9PmFeb7Cyd0WSFofnVQXkmKBW2uTzNhgKNce8C4Eb5XylfMMI7+I4VJBnkydS6xXiuxW3EtIWmPyt20rv3VDGj4zAulmM5euOQCeD2PF641pbmL4sa0YTmsOzV1h14cbqrxX1W5JhuGQ/re/1FmKJNLSA3rbYemSxjlPPYb0g/CcpCSaSgq27NDaet2FbLQ/dZEWc8nvnkJOSY+v5RAo/gljSY0MWK5Qv9q2Tr0UxL3Z+I6OJ6M4tejVx93o4Pdbl62yFPyjDwnMdkjB+QdOSIzwokil+QL+RpcBt+C78GPK2sw6DJPyEYFP/8AVhr+ZQ==</latexit>

⇥

Ã

y])

<latexit sha1_base64="aMXuEvqOzCy8m2McnzR37VSViNc=">AAADDnicbVLLatwwFNW4r9R9Je2yG1EzUEoZxkP6WAZKoIsWUpiZBGwTZM31jBJJNtJ1yiD8D9m2H9Jd6ba/0N/oF1R2TOlMesHy4Z5zdK+km1dSWByPfw2CGzdv3b6zcze8d//Bw0e7e4/ntqwNhxkvZWlOcmZBCg0zFCjhpDLAVC7hOD9/1/LHF2CsKPUU1xVkii21KARn6FPzFIUCe7objUfjLuh1EPcgIn0cne4NfqeLktcKNHLJrE3icYWZYwYFl9CEaW2hYvycLSHxUDNfJXNduw0d+syCFqXxn0baZf91OKasXavcKxXDld3m2uT/uKTG4m3mhK5qBM2vChW1pFjS9ux0IQxwlGsPGDfC90r5ihnG0d9QmC6gSKfOpdZzFfYrriWkXanCTZvGH82Ahs+8VIrpxQuXXgBvkjhznSgvXBS3og3JYdOzuTv05HCTjf+yyrXeMBzSD/45maFMLiE3bGs7NL3DKOex35B+FJaDlExDWdstOVS26VYhS73dmqiaZOKbl1Bg6v1LCTSKX9JoQlMjliv0vy7bhH5K4u2ZuA7mk1H8evTq0350sN/Pyw55Sp6R5yQmb8gBeU+OyIxwckYuyRfyNbgMvgXfgx9X0mDQe56QjQh+/gHJwP0e</latexit><latexit sha1_base64="RQlrezWie4NZ5dIqe0SNDItDbDc=">AAADCXicbVLLatwwFNW4r9R9JGmX3YiagVLKYA/pYxkogS5aSGAmGbBNkOVrj4gkG0lOGYS/INv2Q7or3fYr+hv9gsqOKR2nFywfzkO6sm9Wc6ZNGP6aeLdu37l7b+e+/+Dho8e7e/tPTnXVKApLWvFKrTKigTMJS8MMh1WtgIiMw1l28b7Tzy5BaVbJhdnUkApSSlYwSoyjTlbne0E4C/vCN0E0gAANdXy+P/md5BVtBEhDOdE6jsLapJYowyiH1k8aDTWhF6SE2EFJBOjU9p22eOqYHBeVco80uGf/TVgitN6IzDkFMWs91jryf1rcmOJdapmsGwOSXh9UNBybCnfXxjlTQA3fOECoYq5XTNdEEWrcx/GTHIpkYW2inVabYTUbDkl/VGEXbeuupkDCZ1oJQWT+0iaXQNs4Sm1vygobRJ1py3LUDmpmj5w43Vajv6qwXdb3p/ij+5NEYcJLyBQZbWfUkFDCOuw2xJ+YpsA5kVA1emSHWrf9ynglx62xuo3nrnkOhUlcvuSAg+gVDuY4UaxcG/fq2dZ3UxKNZ+ImOJ3Pojez1ycHweHBMC876Bl6jl6gCL1Fh+gDOkZLRBGgK/QFffWuvG/ed+/HtdWbDJmnaKu8n38AVqX6xg==</latexit>

X

y

b
y
<latexit sha1_base64="fdxpu/YGV/AXIa4hrxbCRVAFPa8=">AAADG3icbVJda9swFFW8j3beR5PtcS9iJjDGCHHo1j0WRmEPG3SQtAU7BFm+dkQl2UhyQxD6KX3dfsjexl73sL+xXzDFNWNJd8Hy4Z5zpKurm9WcaTMe/+oFd+7eu7+3/yB8+Ojxk4P+4OmZrhpFYUYrXqmLjGjgTMLMMMPholZARMbhPLt8v+HPr0BpVsmpWdcwF6SUrGCUGJ9a9AfpiuWwJMamV0Dt2rlFPxqPxm3g2yDuQIS6OF0Mer/TvKKNAGkoJ1on8bg2c0uUYZSDC9NGQ03oJSkh8VASAXpu29odHvpMjotK+U8a3Gb/dVgitF6LzCsFMUu9y22S/+OSxhTv5pbJujEg6c1BRcOxqfCmEThnCqjhaw8IVczXiumSKEKNb1eY5lCkU2tT7bnadKtZc0jbowo7dc5fTYGEFa2EIDJ/1fbQJfHctqKssFG8EW1JTlzHZvbEk8NtNv7LCrvxhuEQf/RvSxQmvIRMkZ3tjOocSliP/Yb4E9MUOCcSqkbvyKHWrl0Zr+Ruaax2ycQXz6EwqfeXHHAUv8bRBKeKlUvjf23WhX5K4t2ZuA3OJqP47ejN58Po+LCbl330HL1AL1GMjtAx+oBO0QxRtELX6Av6GlwH34LvwY8badDrPM/QVgQ//wDc9QKT</latexit>ỹ<latexit sha1_base64="wyRA4EYJO+Yok1MmgzzQ/L4kK8w=">AAADGXicbVLLatwwFNW4r9R9ZNIuuxE1A6WUwR6SpstACXTRQgozSWA8DLJ87RGRZCPJCYPQl2Tbfkh3pduu+hv9gsqOKZ1JL1g+3HOOdHV1s5ozbeL41yC4c/fe/Qc7D8NHj5883R3uPTvVVaMozGjFK3WeEQ2cSZgZZjic1wqIyDicZRfvW/7sEpRmlZyadQ0LQUrJCkaJ8anlcDe9BGpTw3gOdu3cchjF47gLfBskPYhQHyfLvcHvNK9oI0AayonW8ySuzcISZRjl4MK00VATekFKmHsoiQC9sF3lDo98JsdFpfwnDe6y/zosEVqvReaVgpiV3uba5P+4eWOKdwvLZN0YkPTmoKLh2FS4bQPOmQJq+NoDQhXztWK6IopQ45sVpjkU6dTaVHuuNv1q1hzS7qjCTp3zV1Mg4YpWQhCZv7ZtK908WdhOlBU2SlrRhuTY9Wxmjz052mSTv6ywrTcMR/ijf1miMOElZIpsbWdU71DCeuw3xJ+YpsA5kVA1eksOtXbdynglt0tjtZtPfPEcCpN6f8kBR8kbHE1wqli5Mv7XZV3opyTZnonb4HQyTt6ODz7vR0f7/bzsoBfoJXqFEnSIjtAHdIJmiKIGXaMv6GtwHXwLvgc/bqTBoPc8RxsR/PwDUwsBqw==</latexit><latexit sha1_base64="lfeXtGjz88N69qeIUIhSoMt9TfM=">AAADD3icbVLditQwFM7Uv7X+7eqlN8EyICLDdFh/LhdkwQuFFWZ2FtqypOlpJ0ySliRdKaEPsbf6IN6Jtz6Cr+ETmHaLOF0PJPk43/clJ8lJK860mc9/TbwbN2/dvrN31793/8HDR/sHj091WSsKK1ryUp2lRANnElaGGQ5nlQIiUg7rdPuu49cXoDQr5dI0FSSCFJLljBLjUuv4Aqht2vP9YD6b94Gvg3AAARri5Pxg8jvOSloLkIZyonUUziuTWKIMoxxaP641VIRuSQGRg5II0Int623x1GUynJfKDWlwn/3XYYnQuhGpUwpiNnrMdcn/cVFt8reJZbKqDUh6dVBec2xK3F0eZ0wBNbxxgFDFXK2Ybogi1Lgn8uMM8nhpbawdV5lhNg2HuD8qt8u2dVdTIOEzLYUgMnthuydsozCxvSjNbRB2oh3JcTuwqT125HSXDf+ywnZe35/iD+4/icKEF5AqMtrOqMGhhHXYbYg/Mk2BcyKhrPVIDpVu+5nxUo5LY1UbLVzxHHITO3/BAQfhSxwscKxYsTFu6bOt77okHPfEdXC6mIWvZ68+HQZHh0O/7KGn6Bl6jkL0Bh2h9+gErRBFW3SJvqCv3qX3zfvu/biSepPB8wTthPfzD2da/bU=</latexit>

sample O(✏ 2 log n) A:j ⇥ Xj: ’s w.p. pj

sample O(d✏ 2 log n) rows
via leverage score sampling<latexit sha1_base64="B79p2vFsHv1ApD8vuLOaY0XDCvA=">AAADHHicbVLLbhMxFHWGVxkeTcuSjcUoUqkgykS8lpVQJRYgipS0leIQeZw7E6t+jGxPIbLmV7qFD2GH2CLxG3wBznSESMqVbB/dc459bd+sFNy6weBXJ7p2/cbNW1u34zt3793f7u7sHltdGQZjpoU2pxm1ILiCseNOwGlpgMpMwEl29nrFn5yDsVyrkVuWMJW0UDznjLqQmnV33+8RKO1H/3RYE6ELrB7PusmgP2gCXwVpCxLUxtFsp/ObzDWrJCjHBLV2kg5KN/XUOM4E1DGpLJSUndECJgEqKsFOfVN8jXshM8e5NmEoh5vsvw5PpbVLmQWlpG5hN7lV8n/cpHL5q6nnqqwcKHZ5UF4J7DRevQSecwPMiWUAlBkeasVsQQ1lLrxXTOaQk5H3xAaudO3slgJIc1TuR3UdrmZAwSempaRqvu/JObB6kk59I8pyn6Qr0ZrksG7ZzB8GsrfOpn9Z6VfeOO7ht+FzqcFUFJAZurGdM63DSB9w2BC/45aBEFSBruyGPHx23cxcaLVZGi/ryTAULyB3JPgLAThJn+BkiInhxcKFpcnWceiSdLMnroLjYT990X/+4VlysN/2yxZ6iB6hPZSil+gAvUFHaIwY+owu0Bf0NbqIvkXfox+X0qjTeh6gtYh+/gEDXwFz</latexit><latexit sha1_base64="vt2A5qw2rbazDXk11Xd31PgfNpU=">AAADC3icbVLbitQwGM7U01pPu3rpTbAMyCJDO3i6XJAFLxRWnNldaMuQpn87cZO0JOnKEPoIe6sP4p1460P4Gj6BabeI0/WHph/fIfnT/lnNmTZh+GviXbt+4+atndv+nbv37j/Y3Xt4rKtGUVjSilfqNCMaOJOwNMxwOK0VEJFxOMnO3nT6yTkozSq5MJsaUkFKyQpGiXHUx3r1abUbhLOwL3wVRAMI0FBHq73J7ySvaCNAGsqJ1nEU1ia1RBlGObR+0mioCT0jJcQOSiJAp7bvtcVTx+S4qJR7pME9+2/CEqH1RmTOKYhZ67HWkf/T4sYUr1PLZN0YkPTyoKLh2FS4uzjOmQJq+MYBQhVzvWK6JopQ4z6Pn+RQJAtrE+202gyr2XBI+qMKu2hbdzUFEj7TSggi832bnANt4yi1vSkrbBB1pi3LYTuomT104nRbjf6qwnZZ35/id+5fEoUJLyFTZLSdUUNCCeuw2xC/Z5oC50RC1eiRHWrd9ivjlRy3xuo2nrvmORQmcfmSAw6iZziY40Sxcm3cq2db301JNJ6Jq+B4Potezl58eB4c7A/zsoMeoyfoKYrQK3SA3qIjtEQUlegCfUFfvQvvm/fd+3Fp9SZD5hHaKu/nH/QR+7E=</latexit>

Theorem (informal): With O nd✏

Challenge: Large-scale Graphs in GNNs

<latexit sha1_base64="YbwUPd3By90qQ9XKTbkfzmvDCcU=">AAACjXicbVFda9RAFJ3Er7pWuyr64svgIlTFJVla9UGkxQd9rOC2CzsxTCY37dD5iDOTliUd8G/6B/wJPjvZDVW3Xhg4nHPvuZczRS24dUnyI4qvXb9x89bG7cGdzbv3tob3Hxxa3RgGU6aFNrOCWhBcwdRxJ2BWG6CyEHBUnH7o9KMzMJZr9cUtasgkPVa84oy6QOXD7+SCOC5KaImk7qSo2oX3+BXuyX0/W5PPvScX+eTrBBMB3/B2+pJAbbnQ6jkmrNQOE8lV/qcdhw2X1sF5f0bOgAVhZZMPR8k4WRa+CtIejFBfB/nwFyk1ayQoxwS1dp4mtctaahxnAvyANBZqyk7pMcwDVFSCzdplUh4/C0yJK23CUw4v2b8nWiqtXcgidHY323WtI/+nzRtXvc1arurGgWKrRVUjsNO4ix2X3ABzYhEAZYaHWzE7oYYyFz5nQAwoOGdaSqrKF20XkJ+n2WXoo9T7EFS6HstVcDgZp6/Hu593Rns7fWQb6Al6irZRit6gPfQJHaApYuhntBk9ih7HW/Fu/C5+v2qNo37mIfqn4o+/AdLtyME=</latexit>kỹGraph Convolutional Networks (GCNs):
Layer-wise propagation rule: For A 2 Rn⇥nÃX w̃k22  (1 + ✏) · min ky
w

100

1.49

1.39

ogbn-arxiv

169.3K

1.2M

128

299.487.40

Synthetic data
(Gaussian)

50.0K

625.0M

500

27.28

5.77

Synthetic data
(Gaussian)

100.0K

2.5B

500

107/10 8.97

Synthetic data
(Gaussian)

150.0K

5.6B

500

247.70in time O nd2 ✏ 2 log n , with probability 1<latexit sha1_base64="SU+Y2FUh2KywzhvWu/wTpkMXokg=">AAAB+XicbVDLSsNAFL2pr1pfUZduBotQFy2J1Mey4MadFewD2lgm00k7dDIJM5NCCf0TNy4UceufuPNvnLZZaOuBC4dz7uXee/yYM6Ud59vKra1vbG7ltws7u3v7B/bhUVNFiSS0QSIeybaPFeVM0IZmmtN2LCkOfU5b/uh25rfGVCoWiUc9iakX4oFgASNYG6ln225ZPKXl7n1IB7jknk97dtGpOHOgVeJmpAgZ6j37q9uPSBJSoQnHSnVcJ9ZeiqVmhNNpoZsoGmMywgPaMVTgkCovnV8+RWdG6aMgkqaERnP190SKQ6UmoW86Q6yHatmbif95nUQHN17KRJxoKshiUZBwpCM0iwH1maRE84khmEhmbkVkiCUm2oRVMCG4yy+vkuZFxb2qXD5Ui7VqFkceTuAUSuDCNdTgDurQAAJjeIZXeLNS68V6tz4WrTkrmzmGP7A+fwCtSJJd</latexit>

9.96

Orders of maginitude less wall-clock time:¨ 40x acceleration on our scheme for ogbn-arxiv datasets

Numerical Results: Peak Memory Usage
DatasetAXwk22<latexit sha1_base64="0ySfKpCzrGuCihdrzyTYcdgZiQk=">AAACEHicbVA9SwNBEN3z2/gVtbRZDKIWhrvgVxmwsTOCUSEXw95mLlmyt3vszgnhyE+w8a/YWChia2nnv3ETU/j1YODx3gwz86JUCou+/+FNTE5Nz8zOzRcWFpeWV4qra5dWZ4ZDnWupzXXELEihoI4CJVynBlgSSbiKeidD/+oWjBVaXWA/hWbCOkrEgjN0Uqu4fRZKiHGHqvZNJYTUCqnVTb5XGYRSd6iioRGdLu62iiW/7I9A/5JgTEpkjFqr+B62Nc8SUMgls7YR+Ck2c2ZQcAmDQphZSBnvsQ40HFUsAdvMRw8N6JZT2jTWxpVCOlK/T+QssbafRK4zYdi1v72h+J/XyDA+buZCpRmC4l+L4kxS1HSYDm0LAxxl3xHGjXC3Ut5lhnF0GRZcCMHvl/+Sy0o5OCwfnO+XqvvjOObIBtkkOyQgR6RKTkmN1Aknd+SBPJFn79579F6816/WCW88s05+wHv7BGOgnCc=</latexit>

Our scheme andlev. score sampling

1.3M

¨

log n observations,full AX
4.3K

Main Result2

Wall-clock time (sec)ogbl-ddi

perform a regression task

<latexit sha1_base64="csnV1DKJRMYJwnNvKl1kQHfq63c=">AAADHXicbVLLbhMxFHWGVxleKV2ysRhFKhVUmYjXshKqxAJEkZK2Uhwij+fOxKofI9tTFFnzLd3Ch7BDbBG/wRfgTEeIpFzJ9tE959jX9s0qwa0bDn/1omvXb9y8tXU7vnP33v0H/e2Hx1bXhsGEaaHNaUYtCK5g4rgTcFoZoDITcJKdvVnxJ+dgLNdq7JYVzCQtFS84oy6k5v2dD7s5gcp+8s9GDRG6xOrJvJ8M94dt4Ksg7UCCujiab/d+k1yzWoJyTFBrp+mwcjNPjeNMQBOT2kJF2RktYRqgohLszLfVN3gQMjkutAlDOdxm/3V4Kq1dyiwoJXULu8mtkv/jprUrXs88V1XtQLHLg4paYKfx6ilwzg0wJ5YBUGZ4qBWzBTWUufBgMcmhIGPviQ1c5brZLQWQ9qjCj5smXM2Ags9MS0lVvufJObBmms58K8oKn6Qr0ZrksOnYzB8GcrDOpn9Z6VfeOB7gd+F3qcFUlJAZurGdM53DSB9w2BC/55aBEFSBru2GPHx2085caLVZGq+a6SgUL6BwJPhLAThJn+JkhInh5cKFpc02ceiSdLMnroLj0X76cv/Fx+fJwV7XL1voEXqMdlGKXqED9BYdoQliaIku0Bf0NbqIvkXfox+X0qjXeXbQWkQ//wA43wHh</latexit><latexit sha1_base64="OQy4X/nqABA57Mh6LkSd//EAlUg=">AAADHnicbVJda9swFFW8r877aLrtbS9iJjDKCHHYF33qGIU9bNBB0gbsEGTlOlEryUaSOzKh/9LX7YfsrfR1+xv7BVNcMxZ3Fywf7jlH90q6WcmZNoPBr05w4+at23e27ob37j94uN3deXSki0pRGNOCF2qSEQ2cSRgbZjhMSgVEZByOs9P3a/74DJRmhRyZVQlTQRaS5YwS41Oz7pN3M7t34nBqmACNJzN7sudm3WjQH9SBr4O4ARFq4nC20/mdzgtaCZCGcqJ1Eg9KM7VEGUY5uDCtNJSEnpIFJB5K4otNbd2+wz2fmeO8UP6TBtfZfx2WCK1XIvNKQcxSt7l18n9cUpn87dQyWVYGJL0qlFccmwKv7wLPmQJq+MoDQhXzvWK6JIpQ428sTOeQpyNrU+250jSrWXFI61K5HTnnj6ZAwhdaCEHkfNemZ0BdEk9tLcpyG8Vr0YbkwDVsZg882dtk47+ssGtvGPbwR/+8RGHCF5Ap0trOqMahhPXYb4g/MU2BcyKhqHRLDqV29cp4IdutsdIlQ988h9yk3r/ggKP4BY6GOFVssTT+V2dd6Kckbs/EdXA07Mev+68+v4z2d5t52UJP0TP0HMXoDdpHH9AhGiOKvqJz9A19D86DH8FFcHklDTqN5zHaiODnH23NAq8=</latexit><latexit sha1_base64="/0rWve6gs/qbmiU+eHtSaZGTbMc=">AAACDnicbVDJSgNBEO1xN25Rj14ag6AHw0yIyzHgxZsKRgOZGHo6NUljT/fQXSOEIV/gxV/x4kERr569+Td2loPbg4LHe1VU1YtSKSz6/qc3NT0zOze/sFhYWl5ZXSuub1xZnRkOda6lNo2IWZBCQR0FSmikBlgSSbiObk+G/vUdGCu0usR+Cq2EdZWIBWfopHZx5yyUEOMuVZ0QUiukVjf5fmUQSt2lioZGdHu41y6W/LI/Av1LggkpkQnO28WPsKN5loBCLpm1zcBPsZUzg4JLGBTCzELK+C3rQtNRxRKwrXz0zoDuOKVDY21cKaQj9ftEzhJr+0nkOhOGPfvbG4r/ec0M4+NWLlSaISg+XhRnkqKmw2xoRxjgKPuOMG6Eu5XyHjOMo0uw4EIIfr/8l1xVysFh+eCiWqpVJ3EskC2yTXZJQI5IjZySc1InnNyTR/JMXrwH78l79d7GrVPeZGaT/ID3/gUoS5uD</latexit>¨# Features

However, computing lev. scores requires the computation of AX

BA# Nodes # Edges# Nodes # Edges# Features

Wall-clock time (sec)full AX

Our scheme andlev. score samplingn ⌦(1).

<latexit sha1_base64="Zme6pfX6Dpz2MPIg93QMBql5fmk=">AAACKnicbVDLSgMxFM34rPVVdSlCsAjiosyIr2XFjUsVq0JnLJn0joYmmSHJKCXMyq8RXOmfuBO3foNrM20Xvg4Ezj3nXu7NiTPOtPH9N29sfGJyaroyU52dm19YrC0tX+g0VxRaNOWpuoqJBs4ktAwzHK4yBUTEHC7j3lHpX96B0iyV56afQSTIjWQJo8Q4qVNbO8QhkzgUxNzGsT0rrq2rDBOgsSw6tbrf8AfAf0kwInU0wkmn9hl2U5oLkIZyonU78DMTWaIMoxyKaphryAjtkRtoOyqJ2xPZwTcKvOGULk5S5Z40eKB+n7BEaN0Xsessz9W/vVL8z2vnJjmILJNZbkDS4aIk59ikuMwEd5kCanjfEUIVc7dieksUocYlVw0VSLinqRBEdrdseAe0aAeRHWaW2HpQlEEFv2P5Sy62G8FeY/d0p97cGUVWQatoHW2iAO2jJjpGJ6iFKHpAj+gZvXhP3qv35r0PW8e80cwK+gHv4wuvaqds</latexit><latexit sha1_base64="apCoPEkZwW0N2OW+VQAdFaHeRUc=">AAACFnicbZDLSsNAFIYn9VbrLerSzWARWsSSSL1shIqbLivYCzSxTKaTduhkEmYmQgl9Cje+ihsXirgVd76N0zaKtv4w8POdczhzfi9iVCrL+jQyC4tLyyvZ1dza+sbmlrm905BhLDCp45CFouUhSRjlpK6oYqQVCYICj5GmN7ga15t3REga8hs1jIgboB6nPsVIadQxj6q3ScEhjB3axRG8gI6kvQAVLr+xhs0fW+yYeatkTQTnjZ2aPEhV65gfTjfEcUC4wgxJ2batSLkJEopiRkY5J5YkQniAeqStLUcBkW4yOWsEDzTpQj8U+nEFJ/T3RIICKYeBpzsDpPpytjaG/9XasfLP3YTyKFaE4+kiP2ZQhXCcEexSQbBiQ20QFlT/FeI+EggrnWROh2DPnjxvGscl+7R0cl3OV8ppHFmwB/ZBAdjgDFRAFdRAHWBwDx7BM3gxHown49V4m7ZmjHRmF/yR8f4FccqdCA==</latexit><latexit sha1_base64="W1ajfmOvBFihxedJ4ZrNkxxwYZY=">AAACEnicbVDLSsNAFJ3UV62vqEs3g0VoQUoi9bERCm66rGIf0KRlMp22QyeTMDMRSsg3uPFX3LhQxK0rd/6NkzYLbT0wcOace7n3Hi9kVCrL+jZyK6tr6xv5zcLW9s7unrl/0JJBJDBp4oAFouMhSRjlpKmoYqQTCoJ8j5G2N7lJ/fYDEZIG/F5NQ+L6aMTpkGKktNQ3y6ew3otLVjmB17ADHcqh4yM19rz4LunF+qeoTyQcJH2zaFWsGeAysTNSBBkaffPLGQQ48glXmCEpu7YVKjdGQlHMSFJwIklChCdoRLqacqTnuPHspASeaGUAh4HQjys4U393xMiXcup7ujJdVy56qfif143U8MqNKQ8jRTieDxpGDKoApvnAARUEKzbVBGFB9a4Qj5FAWOkUCzoEe/HkZdI6q9gXlfPbarFWzeLIgyNwDErABpegBuqgAZoAg0fwDF7Bm/FkvBjvxse8NGdkPYfgD4zPHyamm+4=</latexit>

H

W

(`)

), H (0) = X 2 Rn⇥d

Implications: When d ⌧ n,¨

Storage cost:¨

Speed-up: nd2 ✏ 2 log n ⌧ n2 d¨Query complexity gains: nd✏ 2 log n ⌧ n2

<latexit sha1_base64="xE7lCfpXA6vp14vwRfr7BLevstk=">AAACCXicbVDLSsNAFJ34rPUVdelmsAhuLEmoj2XBjcsK9gFNWiaTSTt0MhNmJkIJ3brxV9y4UMStf+DOv3HaZqGtBy4czrmXe+8JU0aVdpxva2V1bX1js7RV3t7Z3du3Dw5bSmQSkyYWTMhOiBRhlJOmppqRTioJSkJG2uHoZuq3H4hUVPB7PU5JkKABpzHFSBupb0Me9TyfpIoywXv5uTfxmRhADn3GIO95Ud+uOFVnBrhM3IJUQIFG3/7yI4GzhHCNGVKq6zqpDnIkNcWMTMp+pkiK8AgNSNdQjhKignz2yQSeGiWCsZCmuIYz9fdEjhKlxkloOhOkh2rRm4r/ed1Mx9dBTnmaacLxfFGcMagFnMYCIyoJ1mxsCMKSmlshHiKJsDbhlU0I7uLLy6TlVd3L6sVdrVKvFXGUwDE4AWfABVegDm5BAzQBBo/gGbyCN+vJerHerY9564pVzByBP7A+fwAybZlW</latexit>¨

Matrix A could be large and stored in distributed manner¨

Fully observing A may be costly or infeasible<latexit sha1_base64="Rb58T0CNJAjKsZ7SEDijNGxNNk4=">AAACBnicbVDLSsNAFJ3UV62vqEsRBovgxpKU+lgW3LisYB/QpGUymbRDJzNhZiKU0JUbf8WNC0Xc+g3u/BunbRbaeuDC4Zx7ufeeIGFUacf5tgorq2vrG8XN0tb2zu6evX/QUiKVmDSxYEJ2AqQIo5w0NdWMdBJJUBww0g5GN1O//UCkooLf63FC/BgNOI0oRtpIffuYhx5JFGWC97Lz6sRjYgA59BiDvFft22Wn4swAl4mbkzLI0ejbX14ocBoTrjFDSnVdJ9F+hqSmmJFJyUsVSRAeoQHpGspRTJSfzd6YwFOjhDAS0hTXcKb+nshQrNQ4DkxnjPRQLXpT8T+vm+ro2s8oT1JNOJ4vilIGtYDTTGBIJcGajQ1BWFJzK8RDJBHWJrmSCcFdfHmZtKoV97JycVcr12t5HEVwBE7AGXDBFaiDW9AATYDBI3gGr+DNerJerHfrY95asPKZQ/AH1ucPNIuYRA==</latexit>

Numerical Results: MSE Comparison

Computational cost:O(n2 d)

4.3K

1.3M

100

1.49

1.39

ogbn-arxiv

169.3K

1.2M

128

299.487.40

Synthetic data
(Gaussian)

50.0K

625.0M

500

27.28

5.77

Synthetic data
(Gaussian)

100.0K

2.5B

500

107/10 8.97

Synthetic data
(Gaussian)

150.0K

5.6B

500

247.70<latexit sha1_base64="MF4AU185bOwvKX5+NfSGlnTAodI=">AAAB73icbVDLSgNBEOz1GeMr6tHLYBA8SNiV+DgGvHiMYB6QLGF2tjcZMju7zswKIeQnvHhQxKu/482/cZLsQRMLGoqqbrq7glRwbVz321lZXVvf2CxsFbd3dvf2SweHTZ1kimGDJSJR7YBqFFxiw3AjsJ0qpHEgsBUMb6d+6wmV5ol8MKMU/Zj2JY84o8ZK7ZB0hSDyvFcquxV3BrJMvJyUIUe9V/rqhgnLYpSGCap1x3NT44+pMpwJnBS7mcaUsiHtY8dSSWPU/nh274ScWiUkUaJsSUNm6u+JMY21HsWB7YypGehFbyr+53UyE934Yy7TzKBk80VRJohJyPR5EnKFzIiRJZQpbm8lbEAVZcZGVLQheIsvL5PmRcW7qlzeV8u1ah5HAY7hBM7Ag2uowR3UoQEMBDzDK7w5j86L8+58zFtXnHzmCP7A+fwB77ePOA==</latexit>

¨

9.96

Improvements on the memory usage:¨ In the best case, 1414x less memory requirement<latexit sha1_base64="9w35BTnIvf7dU1WJ0QOlHxAadaY=">AAAB7nicbVDLSsNAFL2pr1pfVZduBotQNyUp9bEsuHFnBfuANpbJZNIOnUzCzEQooR/hxoUibv0ed/6NkzYLbT1w4XDOvdx7jxdzprRtf1uFtfWNza3idmlnd2//oHx41FFRIgltk4hHsudhRTkTtK2Z5rQXS4pDj9OuN7nJ/O4TlYpF4kFPY+qGeCRYwAjWRureVcVj3T8flit2zZ4DrRInJxXI0RqWvwZ+RJKQCk04Vqrv2LF2Uyw1I5zOSoNE0RiTCR7RvqECh1S56fzcGTozio+CSJoSGs3V3xMpDpWahp7pDLEeq2UvE//z+okOrt2UiTjRVJDFoiDhSEco+x35TFKi+dQQTCQztyIyxhITbRIqmRCc5ZdXSadecy5rF/eNSrORx1GEEziFKjhwBU24hRa0gcAEnuEV3qzYerHerY9Fa8HKZ47hD6zPHx5Zjr4=</latexit>

The matrix multiplication AX requires¨

This can be prohibitive in big data settings

time

84%

86%

Concluding Remark

MSE

¨

MSE

¨

Two-step training algorithms:
Step 1: Estimate leverage scores

Can GNNs avoid quadratic complexity
scaling with n via sampling?
Questions:¨ How many samples need to be observed?
¨

fraction of graph observed (%)

fraction of graph observed (%)

Step 2: Use leverage score estimate for training

d=
AX

b
A
Ã
<latexit sha1_base64="95UQky/LG9OfyVI7lIXyjNzNAqg=">AAADE3icbVLbatRAGJ6NpxpPrV56MxgKIrJslnq4rEjBC4UKu20hWcpk8md36BzCzJ+WZchj9FYfxDvx1gfwNXwCZ9Mg7tYfMvn4DjN/Jn9RS+FwNPo1iG7cvHX7ztbd+N79Bw8fbe88PnKmsRym3EhjTwrmQAoNUxQo4aS2wFQh4bg4e7/Sj8/BOmH0BJc1zBSba1EJzjBQWX4hSlgw9O/a0+1kNBx1Ra+DtAcJ6evwdGfwOy8NbxRo5JI5l6WjGmeeWRRcQhvnjYOa8TM2hyxAzRS4me96buluYEpaGRsejbRj/014ppxbqiI4FcOF29RW5P+0rMHq7cwLXTcIml8dVDWSoqGrC6ClsMBRLgNg3IrQK+ULZhnHcE1xXkKVT7zPXdBq7FdcSsi7oyo/advwaRY0XHCjFNPlC5+fA2+zdOY7U1H5JF2Z1iwHba8W/iCIu+tq+ldVfpWN4136MfxTZimTcygs29gObZ+wygccNqSfhOMgJdNgGrdhh9q13Sqk0ZutibrNxqF5CRXmIT+XQJP0JU3GNLdivsDw6tg2DlOSbs7EdXA0Hqavh68+7yX7e/28bJGn5Bl5TlLyhuyTD+SQTAknhlySL+RrdBl9i75HP66s0aDPPCFrFf38A9q8/00=</latexit><latexit sha1_base64="PUOt3UzikYXrLmWx6jPnq1lkuqo=">AAADE3icbVLLatwwFNW4r9R9JGmX3YiagVLKYA/pYxkogS5aSGEmGbCHIMvXHhE9jCQnDMKfkW37Id2VbvsB/Y1+QWXHlM6kFywfzkO6lm9ec2ZsHP8aBbdu37l7b+d++ODho8e7e/tPToxqNIU5VVzpRU4McCZhbpnlsKg1EJFzOM3P33f66QVow5Sc2XUNS0EqyUpGifVUml2yAlbEukV7thfFk7gvfBMkA4jQUMdn+6PfWaFoI0BayokxaRLXdumItoxyaMOsMVATek4qSD2URIBZur7nFo89U+BSaf9Ii3v234Qjwpi1yL1TELsy21pH/k9LG1u+Wzom68aCpNcHlQ3HVuHuAnDBNFDL1x4QqpnvFdMV0YRaf01hVkCZzZzLjNdqO6x2zSHrjyrdrG39p2mQcEmVEEQWL112AbRNk6XrTXnpoqQzbViO2kHN3ZEXx5tq8lcVrsuG4Rh/9P+UaEx4BbkmW9tZPSS0cB77DfEnZihwTiSoxmzZoTZtvzKu5HZrrG7TqW+eQ2kzn6844Ch5haMpzjSrVta/erYN/ZQk2zNxE5xMJ8mbyevPB9HhwTAvO+gZeo5eoAS9RYfoAzpGc0SRQlfoC/oaXAXfgu/Bj2trMBoyT9FGBT//ABe1/2Q=</latexit>⇥<latexit sha1_base64="aMXuEvqOzCy8m2McnzR37VSViNc=">AAADDnicbVLLatwwFNW4r9R9Je2yG1EzUEoZxkP6WAZKoIsWUpiZBGwTZM31jBJJNtJ1yiD8D9m2H9Jd6ba/0N/oF1R2TOlMesHy4Z5zdK+km1dSWByPfw2CGzdv3b6zcze8d//Bw0e7e4/ntqwNhxkvZWlOcmZBCg0zFCjhpDLAVC7hOD9/1/LHF2CsKPUU1xVkii21KARn6FPzFIUCe7objUfjLuh1EPcgIn0cne4NfqeLktcKNHLJrE3icYWZYwYFl9CEaW2hYvycLSHxUDNfJXNduw0d+syCFqXxn0baZf91OKasXavcKxXDld3m2uT/uKTG4m3mhK5qBM2vChW1pFjS9ux0IQxwlGsPGDfC90r5ihnG0d9QmC6gSKfOpdZzFfYrriWkXanCTZvGH82Ahs+8VIrpxQuXXgBvkjhznSgvXBS3og3JYdOzuTv05HCTjf+yyrXeMBzSD/45maFMLiE3bGs7NL3DKOex35B+FJaDlExDWdstOVS26VYhS73dmqiaZOKbl1Bg6v1LCTSKX9JoQlMjliv0vy7bhH5K4u2ZuA7mk1H8evTq0350sN/Pyw55Sp6R5yQmb8gBeU+OyIxwckYuyRfyNbgMvgXfgx9X0mDQe56QjQh+/gHJwP0e</latexit>b
X<latexit sha1_base64="EqhH/8tDQBtvTYEB9wDg5WVBfms=">AAADK3icbVJdb9MwFHXD1whf3XjkxRBVGgiqphqMxyE0iQeQhtRulZKocpyb1prtRLazqTJ55tfsFX4ITyBe+QP8ApwsQrTjSnGO7jnHvr6+acmZNqPR95537fqNm7e2bvt37t67/6C/vXOsi0pRmNKCF2qWEg2cSZgaZjjMSgVEpBxO0tO3DX9yBkqzQk7MqoREkIVkOaPEuNS8/zgGzudsN4rPWQZLYuybWf0Jv8DxGVC7qpOn834wGo7awFdB2IEAdXE03+79jrOCVgKkoZxoHYWj0iSWKMMoh9qPKw0loadkAZGDkgjQiW3vUuOBy2Q4L5T7pMFt9l+HJULrlUidUhCz1Jtck/wfF1Umf51YJsvKgKSXB+UVx6bATWNwxhRQw1cOEKqYqxXTJVGEGtc+P84gjyfWxtpxpelWs+IQt0fldlLX7moKJJzTQggis2e2aWIdhYltRWlug7ARrUkO645N7aEjB+ts+JcVtvH6/gC/d29NFCZ8AakiG9sZ1TmUsA67DfEHpql7ZSKhqPSGHEpdtyvjhdwsjZV1NHbFc8hN7PwLDjgIn+NgjGPFFkvjfm229t2UhJszcRUcj4fhq+HLj3vBwV43L1voEXqCdlGI9tEBeoeO0BRR9BldoC/oq3fhffN+eD8vpV6v8zxEa+H9+gPUlAgf</latexit>d`i ([AX|<latexit sha1_base64="Y+vAQS8uSRaHqPVwkCbzM5iJz+E=">AAADEXicbVLdatRAFJ6NfzX+tXrpzWBYEJFls1Tby4oUvFCosNtWNkuZTE52h85MwsxJZRnyFL3VB/FOvPUJfA2fwEkaxE09kMnH9zNzJjlpKYXF8fjXILhx89btO1t3w3v3Hzx8tL3z+NgWleEw44UszGnKLEihYYYCJZyWBphKJZyk528b/eQCjBWFnuK6hIViSy1ywRl66lOCQmbg3tRn29F4NG6LXgdxByLS1dHZzuB3khW8UqCRS2btPB6XuHDMoOAS6jCpLJSMn7MlzD3UTIFduLbjmg49k9G8MP7RSFv234Rjytq1Sr1TMVzZvtaQ/9PmFeb7Cyd0WSFofnVQXkmKBW2uTzNhgKNce8C4Eb5XylfMMI7+I4VJBnkydS6xXiuxW3EtIWmPyt20rv3VDGj4zAulmM5euOQCeD2PF641pbmL4sa0YTmsOzV1h14cbqrxX1W5JhuGQ/re/1FmKJNLSA3rbYemSxjlPPYb0g/CcpCSaSgq27NDaet2FbLQ/dZEWc8nvnkJOSY+v5RAo/gljSY0MWK5Qv9q2Tr0UxL3Z+I6OJ6M4tejVx93o4Pdbl62yFPyjDwnMdkjB+QdOSIzwokil+QL+RpcBt+C78GPK2sw6DJPyEYFP/8AVhr+ZQ==</latexit>

y])

Ã

⇥
<latexit sha1_base64="aMXuEvqOzCy8m2McnzR37VSViNc=">AAADDnicbVLLatwwFNW4r9R9Je2yG1EzUEoZxkP6WAZKoIsWUpiZBGwTZM31jBJJNtJ1yiD8D9m2H9Jd6ba/0N/oF1R2TOlMesHy4Z5zdK+km1dSWByPfw2CGzdv3b6zcze8d//Bw0e7e4/ntqwNhxkvZWlOcmZBCg0zFCjhpDLAVC7hOD9/1/LHF2CsKPUU1xVkii21KARn6FPzFIUCe7objUfjLuh1EPcgIn0cne4NfqeLktcKNHLJrE3icYWZYwYFl9CEaW2hYvycLSHxUDNfJXNduw0d+syCFqXxn0baZf91OKasXavcKxXDld3m2uT/uKTG4m3mhK5qBM2vChW1pFjS9ux0IQxwlGsPGDfC90r5ihnG0d9QmC6gSKfOpdZzFfYrriWkXanCTZvGH82Ahs+8VIrpxQuXXgBvkjhznSgvXBS3og3JYdOzuTv05HCTjf+yyrXeMBzSD/45maFMLiE3bGs7NL3DKOex35B+FJaDlExDWdstOVS26VYhS73dmqiaZOKbl1Bg6v1LCTSKX9JoQlMjliv0vy7bhH5K4u2ZuA7mk1H8evTq0350sN/Pyw55Sp6R5yQmb8gBeU+OyIxwckYuyRfyNbgMvgXfgx9X0mDQe56QjQh+/gHJwP0e</latexit><latexit sha1_base64="RQlrezWie4NZ5dIqe0SNDItDbDc=">AAADCXicbVLLatwwFNW4r9R9JGmX3YiagVLKYA/pYxkogS5aSGAmGbBNkOVrj4gkG0lOGYS/INv2Q7or3fYr+hv9gsqOKR2nFywfzkO6sm9Wc6ZNGP6aeLdu37l7b+e+/+Dho8e7e/tPTnXVKApLWvFKrTKigTMJS8MMh1WtgIiMw1l28b7Tzy5BaVbJhdnUkApSSlYwSoyjTlbne0E4C/vCN0E0gAANdXy+P/md5BVtBEhDOdE6jsLapJYowyiH1k8aDTWhF6SE2EFJBOjU9p22eOqYHBeVco80uGf/TVgitN6IzDkFMWs91jryf1rcmOJdapmsGwOSXh9UNBybCnfXxjlTQA3fOECoYq5XTNdEEWrcx/GTHIpkYW2inVabYTUbDkl/VGEXbeuupkDCZ1oJQWT+0iaXQNs4Sm1vygobRJ1py3LUDmpmj5w43Vajv6qwXdb3p/ij+5NEYcJLyBQZbWfUkFDCOuw2xJ+YpsA5kVA1emSHWrf9ynglx62xuo3nrnkOhUlcvuSAg+gVDuY4UaxcG/fq2dZ3UxKNZ+ImOJ3Pojez1ycHweHBMC876Bl6jl6gCL1Fh+gDOkZLRBGgK/QFffWuvG/ed+/HtdWbDJmnaKu8n38AVqX6xg==</latexit>Xỹ<latexit sha1_base64="wyRA4EYJO+Yok1MmgzzQ/L4kK8w=">AAADGXicbVLLatwwFNW4r9R9ZNIuuxE1A6WUwR6SpstACXTRQgozSWA8DLJ87RGRZCPJCYPQl2Tbfkh3pduu+hv9gsqOKZ1JL1g+3HOOdHV1s5ozbeL41yC4c/fe/Qc7D8NHj5883R3uPTvVVaMozGjFK3WeEQ2cSZgZZjic1wqIyDicZRfvW/7sEpRmlZyadQ0LQUrJCkaJ8anlcDe9BGpTw3gOdu3cchjF47gLfBskPYhQHyfLvcHvNK9oI0AayonW8ySuzcISZRjl4MK00VATekFKmHsoiQC9sF3lDo98JsdFpfwnDe6y/zosEVqvReaVgpiV3uba5P+4eWOKdwvLZN0YkPTmoKLh2FS4bQPOmQJq+NoDQhXztWK6IopQ45sVpjkU6dTaVHuuNv1q1hzS7qjCTp3zV1Mg4YpWQhCZv7ZtK908WdhOlBU2SlrRhuTY9Wxmjz052mSTv6ywrTcMR/ijf1miMOElZIpsbWdU71DCeuw3xJ+YpsA5kVA1eksOtXbdynglt0tjtZtPfPEcCpN6f8kBR8kbHE1wqli5Mv7XZV3opyTZnonb4HQyTt6ODz7vR0f7/bzsoBfoJXqFEnSIjtAHdIJmiKIGXaMv6GtwHXwLvgc/bqTBoPc8RxsR/PwDUwsBqw==</latexit><latexit sha1_base64="lfeXtGjz88N69qeIUIhSoMt9TfM=">AAADD3icbVLditQwFM7Uv7X+7eqlN8EyICLDdFh/LhdkwQuFFWZ2FtqypOlpJ0ySliRdKaEPsbf6IN6Jtz6Cr+ETmHaLOF0PJPk43/clJ8lJK860mc9/TbwbN2/dvrN31793/8HDR/sHj091WSsKK1ryUp2lRANnElaGGQ5nlQIiUg7rdPuu49cXoDQr5dI0FSSCFJLljBLjUuv4Aqht2vP9YD6b94Gvg3AAARri5Pxg8jvOSloLkIZyonUUziuTWKIMoxxaP641VIRuSQGRg5II0Int623x1GUynJfKDWlwn/3XYYnQuhGpUwpiNnrMdcn/cVFt8reJZbKqDUh6dVBec2xK3F0eZ0wBNbxxgFDFXK2Ybogi1Lgn8uMM8nhpbawdV5lhNg2HuD8qt8u2dVdTIOEzLYUgMnthuydsozCxvSjNbRB2oh3JcTuwqT125HSXDf+ywnZe35/iD+4/icKEF5AqMtrOqMGhhHXYbYg/Mk2BcyKhrPVIDpVu+5nxUo5LY1UbLVzxHHITO3/BAQfhSxwscKxYsTFu6bOt77okHPfEdXC6mIWvZ68+HQZHh0O/7KGn6Bl6jkL0Bh2h9+gErRBFW3SJvqCv3qX3zfvu/biSepPB8wTthPfzD2da/bU=</latexit>

sample O(✏ 2 log n) A:j ⇥ Xj: ’s w.p. pj<latexit sha1_base64="B79p2vFsHv1ApD8vuLOaY0XDCvA=">AAADHHicbVLLbhMxFHWGVxkeTcuSjcUoUqkgykS8lpVQJRYgipS0leIQeZw7E6t+jGxPIbLmV7qFD2GH2CLxG3wBznSESMqVbB/dc459bd+sFNy6weBXJ7p2/cbNW1u34zt3793f7u7sHltdGQZjpoU2pxm1ILiCseNOwGlpgMpMwEl29nrFn5yDsVyrkVuWMJW0UDznjLqQmnV33+8RKO1H/3RYE6ELrB7PusmgP2gCXwVpCxLUxtFsp/ObzDWrJCjHBLV2kg5KN/XUOM4E1DGpLJSUndECJgEqKsFOfVN8jXshM8e5NmEoh5vsvw5PpbVLmQWlpG5hN7lV8n/cpHL5q6nnqqwcKHZ5UF4J7DRevQSecwPMiWUAlBkeasVsQQ1lLrxXTOaQk5H3xAaudO3slgJIc1TuR3UdrmZAwSempaRqvu/JObB6kk59I8pyn6Qr0ZrksG7ZzB8GsrfOpn9Z6VfeOO7ht+FzqcFUFJAZurGdM63DSB9w2BC/45aBEFSBruyGPHx23cxcaLVZGi/ryTAULyB3JPgLAThJn+BkiInhxcKFpcnWceiSdLMnroLjYT990X/+4VlysN/2yxZ6iB6hPZSil+gAvUFHaIwY+owu0Bf0NbqIvkXfox+X0qjTeh6gtYh+/gEDXwFz</latexit><latexit sha1_base64="OQy4X/nqABA57Mh6LkSd//EAlUg=">AAADHnicbVJda9swFFW8r877aLrtbS9iJjDKCHHYF33qGIU9bNBB0gbsEGTlOlEryUaSOzKh/9LX7YfsrfR1+xv7BVNcMxZ3Fywf7jlH90q6WcmZNoPBr05w4+at23e27ob37j94uN3deXSki0pRGNOCF2qSEQ2cSRgbZjhMSgVEZByOs9P3a/74DJRmhRyZVQlTQRaS5YwS41Oz7pN3M7t34nBqmACNJzN7sudm3WjQH9SBr4O4ARFq4nC20/mdzgtaCZCGcqJ1Eg9KM7VEGUY5uDCtNJSEnpIFJB5K4otNbd2+wz2fmeO8UP6TBtfZfx2WCK1XIvNKQcxSt7l18n9cUpn87dQyWVYGJL0qlFccmwKv7wLPmQJq+MoDQhXzvWK6JIpQ428sTOeQpyNrU+250jSrWXFI61K5HTnnj6ZAwhdaCEHkfNemZ0BdEk9tLcpyG8Vr0YbkwDVsZg882dtk47+ssGtvGPbwR/+8RGHCF5Ap0trOqMahhPXYb4g/MU2BcyKhqHRLDqV29cp4IdutsdIlQ988h9yk3r/ggKP4BY6GOFVssTT+V2dd6Kckbs/EdXA07Mev+68+v4z2d5t52UJP0TP0HMXoDdpHH9AhGiOKvqJz9A19D86DH8FFcHklDTqN5zHaiODnH23NAq8=</latexit><latexit sha1_base64="vt2A5qw2rbazDXk11Xd31PgfNpU=">AAADC3icbVLbitQwGM7U01pPu3rpTbAMyCJDO3i6XJAFLxRWnNldaMuQpn87cZO0JOnKEPoIe6sP4p1460P4Gj6BabeI0/WHph/fIfnT/lnNmTZh+GviXbt+4+atndv+nbv37j/Y3Xt4rKtGUVjSilfqNCMaOJOwNMxwOK0VEJFxOMnO3nT6yTkozSq5MJsaUkFKyQpGiXHUx3r1abUbhLOwL3wVRAMI0FBHq73J7ySvaCNAGsqJ1nEU1ia1RBlGObR+0mioCT0jJcQOSiJAp7bvtcVTx+S4qJR7pME9+2/CEqH1RmTOKYhZ67HWkf/T4sYUr1PLZN0YkPTyoKLh2FS4uzjOmQJq+MYBQhVzvWK6JopQ4z6Pn+RQJAtrE+202gyr2XBI+qMKu2hbdzUFEj7TSggi832bnANt4yi1vSkrbBB1pi3LYTuomT104nRbjf6qwnZZ35/id+5fEoUJLyFTZLSdUUNCCeuw2xC/Z5oC50RC1eiRHWrd9ivjlRy3xuo2nrvmORQmcfmSAw6iZziY40Sxcm3cq2db301JNJ6Jq+B4Potezl58eB4c7A/zsoMeoyfoKYrQK3SA3qIjtEQUlegCfUFfvQvvm/fd+3Fp9SZD5hHaKu/nH/QR+7E=</latexit>

Non-linear GCNs

What graph subsampling strategies are amenable?
fraction of graph observed (%)

fraction of graph observed (%)
Datasets: ogbl-ddi (from OGB), ego-Facebook (from SNAP), House dataset

sample O(d✏ 2 log n) rows
via leverage score sampling<latexit sha1_base64="csnV1DKJRMYJwnNvKl1kQHfq63c=">AAADHXicbVLLbhMxFHWGVxleKV2ysRhFKhVUmYjXshKqxAJEkZK2Uhwij+fOxKofI9tTFFnzLd3Ch7BDbBG/wRfgTEeIpFzJ9tE959jX9s0qwa0bDn/1omvXb9y8tXU7vnP33v0H/e2Hx1bXhsGEaaHNaUYtCK5g4rgTcFoZoDITcJKdvVnxJ+dgLNdq7JYVzCQtFS84oy6k5v2dD7s5gcp+8s9GDRG6xOrJvJ8M94dt4Ksg7UCCujiab/d+k1yzWoJyTFBrp+mwcjNPjeNMQBOT2kJF2RktYRqgohLszLfVN3gQMjkutAlDOdxm/3V4Kq1dyiwoJXULu8mtkv/jprUrXs88V1XtQLHLg4paYKfx6ilwzg0wJ5YBUGZ4qBWzBTWUufBgMcmhIGPviQ1c5brZLQWQ9qjCj5smXM2Ags9MS0lVvufJObBmms58K8oKn6Qr0ZrksOnYzB8GcrDOpn9Z6VfeOB7gd+F3qcFUlJAZurGdM53DSB9w2BC/55aBEFSBru2GPHx2085caLVZGq+a6SgUL6BwJPhLAThJn+JkhInh5cKFpc02ceiSdLMnroLj0X76cv/Fx+fJwV7XL1voEXqMdlGKXqED9BYdoQliaIku0Bf0NbqIvkXfox+X0qjXeXbQWkQ//wA43wHh</latexit>

perform a regression taskby<latexit sha1_base64="fdxpu/YGV/AXIa4hrxbCRVAFPa8=">AAADG3icbVJda9swFFW8j3beR5PtcS9iJjDGCHHo1j0WRmEPG3SQtAU7BFm+dkQl2UhyQxD6KX3dfsjexl73sL+xXzDFNWNJd8Hy4Z5zpKurm9WcaTMe/+oFd+7eu7+3/yB8+Ojxk4P+4OmZrhpFYUYrXqmLjGjgTMLMMMPholZARMbhPLt8v+HPr0BpVsmpWdcwF6SUrGCUGJ9a9AfpiuWwJMamV0Dt2rlFPxqPxm3g2yDuQIS6OF0Mer/TvKKNAGkoJ1on8bg2c0uUYZSDC9NGQ03oJSkh8VASAXpu29odHvpMjotK+U8a3Gb/dVgitF6LzCsFMUu9y22S/+OSxhTv5pbJujEg6c1BRcOxqfCmEThnCqjhaw8IVczXiumSKEKNb1eY5lCkU2tT7bnadKtZc0jbowo7dc5fTYGEFa2EIDJ/1fbQJfHctqKssFG8EW1JTlzHZvbEk8NtNv7LCrvxhuEQf/RvSxQmvIRMkZ3tjOocSliP/Yb4E9MUOCcSqkbvyKHWrl0Zr+Ruaax2ycQXz6EwqfeXHHAUv8bRBKeKlUvjf23WhX5K4t2ZuA3OJqP47ejN58Po+LCbl330HL1AL1GMjtAx+oBO0QxRtELX6Av6GlwH34LvwY8badDrPM/QVgQ//wDc9QKT</latexit><latexit sha1_base64="0ySfKpCzrGuCihdrzyTYcdgZiQk=">AAACEHicbVA9SwNBEN3z2/gVtbRZDKIWhrvgVxmwsTOCUSEXw95mLlmyt3vszgnhyE+w8a/YWChia2nnv3ETU/j1YODx3gwz86JUCou+/+FNTE5Nz8zOzRcWFpeWV4qra5dWZ4ZDnWupzXXELEihoI4CJVynBlgSSbiKeidD/+oWjBVaXWA/hWbCOkrEgjN0Uqu4fRZKiHGHqvZNJYTUCqnVTb5XGYRSd6iioRGdLu62iiW/7I9A/5JgTEpkjFqr+B62Nc8SUMgls7YR+Ck2c2ZQcAmDQphZSBnvsQ40HFUsAdvMRw8N6JZT2jTWxpVCOlK/T+QssbafRK4zYdi1v72h+J/XyDA+buZCpRmC4l+L4kxS1HSYDm0LAxxl3xHGjXC3Ut5lhnF0GRZcCMHvl/+Sy0o5OCwfnO+XqvvjOObIBtkkOyQgR6RKTkmN1Aknd+SBPJFn79579F6816/WCW88s05+wHv7BGOgnCc=</latexit><latexit sha1_base64="YbwUPd3By90qQ9XKTbkfzmvDCcU=">AAACjXicbVFda9RAFJ3Er7pWuyr64svgIlTFJVla9UGkxQd9rOC2CzsxTCY37dD5iDOTliUd8G/6B/wJPjvZDVW3Xhg4nHPvuZczRS24dUnyI4qvXb9x89bG7cGdzbv3tob3Hxxa3RgGU6aFNrOCWhBcwdRxJ2BWG6CyEHBUnH7o9KMzMJZr9cUtasgkPVa84oy6QOXD7+SCOC5KaImk7qSo2oX3+BXuyX0/W5PPvScX+eTrBBMB3/B2+pJAbbnQ6jkmrNQOE8lV/qcdhw2X1sF5f0bOgAVhZZMPR8k4WRa+CtIejFBfB/nwFyk1ayQoxwS1dp4mtctaahxnAvyANBZqyk7pMcwDVFSCzdplUh4/C0yJK23CUw4v2b8nWiqtXcgidHY323WtI/+nzRtXvc1arurGgWKrRVUjsNO4ix2X3ABzYhEAZYaHWzE7oYYyFz5nQAwoOGdaSqrKF20XkJ+n2WXoo9T7EFS6HstVcDgZp6/Hu593Rns7fWQb6Al6irZRit6gPfQJHaApYuhntBk9ih7HW/Fu/C5+v2qNo37mIfqn4o+/AdLtyME=</latexit>

Extensions:¨ Nonlinear GCNs, classification or link prediction tasks?
¨ Generalization guarantee?
¨ Adaptive alglorithms at each gradient descent step?
¨

60%

linear GNN
architecture

Budget: O nd✏ 2 log n
Run-time: O nd2 ✏ 2 log nkyError: kỹ ÃX w̃k22  (1 + ✏) · minw<latexit sha1_base64="/0rWve6gs/qbmiU+eHtSaZGTbMc=">AAACDnicbVDJSgNBEO1xN25Rj14ag6AHw0yIyzHgxZsKRgOZGHo6NUljT/fQXSOEIV/gxV/x4kERr569+Td2loPbg4LHe1VU1YtSKSz6/qc3NT0zOze/sFhYWl5ZXSuub1xZnRkOda6lNo2IWZBCQR0FSmikBlgSSbiObk+G/vUdGCu0usR+Cq2EdZWIBWfopHZx5yyUEOMuVZ0QUiukVjf5fmUQSt2lioZGdHu41y6W/LI/Av1LggkpkQnO28WPsKN5loBCLpm1zcBPsZUzg4JLGBTCzELK+C3rQtNRxRKwrXz0zoDuOKVDY21cKaQj9ftEzhJr+0nkOhOGPfvbG4r/ec0M4+NWLlSaISg+XhRnkqKmw2xoRxjgKPuOMG6Eu5XyHjOMo0uw4EIIfr/8l1xVysFh+eCiWqpVJ3EskC2yTXZJQI5IjZySc1InnNyTR/JMXrwH78l79d7GrVPeZGaT/ID3/gUoS5uD</latexit><latexit sha1_base64="D01Nf6TIaSbI5cxzi/3aYPKCnQ0=">AAAB8HicbVBNS8NAEN3Ur1q/qh69LBbBU0lU1GPVi8cK9kPaUDababt0swm7E6GE/govHhTx6s/x5r9x2+ag1QcDj/dmmJkXJFIYdN0vp7C0vLK6VlwvbWxube+Ud/eaJk41hwaPZazbATMghYIGCpTQTjSwKJDQCkY3U7/1CNqIWN3jOAE/YgMl+oIztNJDF4UMIbua9MoVt+rOQP8SLycVkqPeK392w5inESjkkhnT8dwE/YxpFFzCpNRNDSSMj9gAOpYqFoHxs9nBE3pklZD2Y21LIZ2pPycyFhkzjgLbGTEcmkVvKv7ndVLsX/qZUEmKoPh8UT+VFGM6/Z6GQgNHObaEcS3srZQPmWYcbUYlG4K3+PJf0jypeufV07uzSu06j6NIDsghOSYeuSA1ckvqpEE4icgTeSGvjnaenTfnfd5acPKZffILzsc38leQgw==</latexit><latexit sha1_base64="Zb56woiQ30x32Eyi9WF+fKfoVqo=">AAADGXicbVJba9swFFa8W+ddmm6PexEzgTFGiEN3eRl0jEIfNuggaQNxCLJ8nIhKspGOW4LwL+nr9kP2Nvbap/2N/YIprhlLugOWP76LdCyftJTC4mDwqxPcun3n7r2d++GDh48e73b3npzYojIcxryQhZmkzIIUGsYoUMKkNMBUKuE0Pfu41k/PwVhR6BGuSpgpttAiF5yhp+bd3eRCZLBk6D5MavqezrvRoD9oit4EcQsi0tbxfK/zO8kKXinQyCWzdhoPSpw5ZlBwCXWYVBZKxs/YAqYeaqbAzlzTeU17nsloXhj/aKQN+2/CMWXtSqXeqRgu7ba2Jv+nTSvM382c0GWFoPn1QXklKRZ0fQ00EwY4ypUHjBvhe6V8yQzj6C8rTDLIk5FzifVaie2KKwlJc1TuRnXtP82AhgteKMV09tIl58DraTxzjSnNXRSvTRuWw7pVU3foxd6mGv9VlVtnw7BHP/k/ywxlcgGpYVvboWkTRjmP/Yb0s7AcpGQaispu2aG0dbMKWejt1kRZT4e+eQk5Jj6/kECj+BWNhjQxYrFE/2rYOvRTEm/PxE1wMuzHb/qvv+xHB/vtvOyQZ+Q5eUFi8pYckCNyTMaEk4pckq/kW3AZfA9+BD+vrUGnzTwlGxVc/QFUsQCK</latexit>

y

MSE

¨

= (AH

(`)

MSE

¨

(`+1)

ogbl-ddi

AXwk22