图学习新突破：一个统一框架连接空域和频域

AIxiv专栏是呆板之心宣布学术、技巧内容的栏目。从前数年，呆板之心AIxiv专栏接受报道了2000多篇内容，笼罩寰球各年夜高校与企业的顶级试验室，无效增进了学术交换与传布。假如你有优良的任务想要分享，欢送投稿或许接洽报道。投稿邮箱：[email protected]；[email protected]陈枳扦博士：现任密西西比州破年夜学盘算机系助理教学，专一于图呆板进修及利用范畴，在谱域视角与不断定性研讨方面出力颇深。其研讨结果见诸于 AAAI、IJCAI、ACM、ICDM、EMNLP、Computing Surveys、Nature Communication 等。他的科研任务承蒙美国国度迷信基金会（NSF）及美国农业部（USDA）多个名目的赞助，且荣获丰田研讨院出色奉献奖与 ACM SIGPSATIAL 2020 最佳论文奖。张磊博士：于 2024 年结业于弗吉尼亚理工后，以助理教学身份加盟北伊利诺伊年夜学。他的研讨兴致普遍笼罩呆板进修跟数据发掘范围，尤其聚焦于图神经收集、图构造进修、双层优化、神经架构搜寻以及交际收集发掘等方面。在 AAAI、ICDM 等顶级集会上宣布多篇论文，并于 2023 年冬季斩获弗吉尼亚理工年夜学的 Cunningham Fellowship。赵亮博士：身为埃默里年夜学盘算机系副教学，他的研讨范畴高出数据发掘、人工智能等多学科，在图进修范畴结果斐然。在 KDD、NeurIPS、AAAI、IJCAI、WWW 等浩繁顶级集会及期刊上宣布超百篇论文，屡获殊荣，如 NSF CAREER 奖、Meta Research 奖、Amazon Research 奖等，还荣获 ICDM 2022 最佳论文奖、ACM SIGPSATIAL 2022 最佳论文奖以及 WWW 2023 最佳论文提名等。图数据进修在从前多少年中获得了明显的停顿，图神经收集（GNN）在此进程中起到了中心感化。但是，差别的 GNN 方式在观点跟实现上的差别，对懂得跟利用图进修算法形成了挑衅。针对这一成绩，来自密西西比州破年夜学，北伊利诺伊年夜学跟埃默里年夜学的学者经由过程一系列教程对此成绩开展了探讨，这些教程展现在 CVPR 2024、CIKM 2024、SIAM Math and Data Science 2024，以及宣布在 Computing Surveys 的一篇论文: 《Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networks》。论文地点：https://dl.acm.org/doi/10.1145/3627816成绩：同一框架的冲破意思安在？只管图神经收集曾经在多个范畴展现出了出色的机能，从化学分子辨认到交际收集剖析，从交通收集到输电收集，再到年夜脑收集。GNN 也在差别的场景下，用差别的实践跟机制来计划新的图神经收集，比方 Heat diffusion, page rank, random walk, attention model, ARMA, low-pass filtering。固然展示了 GNN 跟良多差别实践东西的衔接性，但这也加剧了 GNN 范畴的决裂。这些方式由于急于差别实践，无奈停止实践上直接的比拟。Part 1: 图进修实践框架的近况现在，图神经收集（GNN）涵盖了多种模子跟层的范例，但总体能够分为空域（spatial）图模子跟频域（spectral）图模子。针对这些模子，不少研讨者实验提出通用框架，以便在统一框架下对差别模子停止剖析跟比拟。但是，这些框架重要会合于空域图模子。值得留神的是，有一类研讨从同一的动身点 —— 即模子的表白才能（Expressive Power）—— 对空域跟频域图模子停止了剖析。只管如斯，空域跟频域图模子在表白才能的界说上存在差别，其剖析论断跟计划倡议既有共通之处，也各有差别，同时两者均存在必定的范围性。Part 2: 图卷积图卷积能够经由过程谱图实践（Spectral Graph Theory）中的图傅里叶变更（Graph Fourier Transform）跟卷积定理（Convolution Theorem）来懂得。图傅破叶变更：图的构造经由过程图拉普拉斯矩阵（Graph Laplacian）来表现。拉普拉斯矩阵 L 能够停止特点值剖析： ]article_adlist-->。经由过程这种变更，研讨者能够在频域中处置跟剖析图旌旗灯号。。其逆变更为转换到频域：，此中 U 是特点向量矩阵，∧ 是特点值的对角矩阵。图傅里叶变更就是将图旌旗灯号卷积定理：在传统旌旗灯号处置中，时域的卷积等价于频域的逐点相乘。对图旌旗灯号，同样建立：设两个图旌旗灯号 X（输入特点）跟 g（滤波器），它们的图卷积界说为：，它是特点值 ∧ 的函数：。 ]article_adlist-->，此中 θ 是可练习的参数向量。卷积操纵能够写为：。此中，⊙ 表现频域的逐点相乘，g 表现频域滤波器。这标明图卷积能够经由过程频域操纵实现。为了在图神经收集中实现卷积，滤波器 g 被参数化为图卷积收集（GCN）在频域跟空域的说明：在频域图模子中，GCN 应用的是 ]article_adlist-->。这种操纵实质上是一种牢固的卷积操纵，不可进修参数。因为归一化之后的拉普拉斯矩阵的特点值范畴为 0 到 2 之间，2-θ 的滤波器现实上是一个低通滤波器：缩小低频腻滑旌旗灯号，削弱高频旌旗灯号。在空域图模子中， GCN 的操纵能够懂得为对每个节点的街坊节点的特点值停止乞降，而后取均匀值。这是一种基于街坊特点聚合的方法。GCN 的频域跟空域视角是等价的，但各有着重。频域说明更倾向实践上的旌旗灯号处置实质，而空域说明更切近工程实现跟直不雅懂得。对研讨者而言，这两种视角是相反相成的，联合应用能够更片面地舆解跟改良 GCN。的一阶近似，此中Part 3: 新的同一框架：衔接空域跟频域教程中提出的框架基于一个中心假设：空间域跟频谱域的图表现进修能够经由过程一个独特的数学言语停止描写。研讨职员引入了一种新的图嵌入方式，该方式联合了图的空间衔接性跟节点特点，可能愈加精准地捕获跟表现图数据的庞杂性。其余范畴里频域跟空域的研讨在已存在的研讨里，这种空域跟频域彼此衔接视角并不少见。研讨者用两个例子来阐明：（1）谱聚类：从谱域的视角看谱聚类是应用谱剖析 (spectral decomposition) 或则说特点剖析（eigen-decomposition），而后应用剖析成果中特点值洪亮的低频旌旗灯号来作为新的表白，而后应用较为简略疾速的 Kmeans 失掉聚类成果。而别的一个新的实现，SpectralNet，计划了一个特殊 loss，应用神经收集来失掉多少乎一样的成果。单神经收集是一种以下降 loss 为导向的迭代算法，以是能够视为一种近似谱聚类的算法。（2）别的一个例子是有名的 Word2Vec 算法。以 Skip-gram 为例，每个单词都要类似于它的高低文的情况里其余单词。以是 Word2Vec 是一个迭代算法。在厥后的研讨中，Levy 提出了一些剖析，发明应用 Word2Vec 的成果里的矩阵，可能多少乎完全的复原单词的共现矩阵（PPMI）。也就是说 Word2Vec 能够看作是矩阵剖析算法的一种近似算法。在这两个例子中，研讨者发明这种比拟中，有相似于该研讨提出的谱域跟空域方式差别。即，一种方式着重矩阵剖析，而别的一种着重于迭代近似。Part 4: 将来偏向瞻望这项研讨开拓了图构造进修范畴的新偏向，将来的研讨能够基于此框架进一步摸索：盘算效力：怎样进一步优化同一框架以处置年夜范围图数据，在谱论表白下，图的信息量仍然宏大，对盘算依然是一个挑衅。同一的谱论：现在谱论重要利用于静态图构造，并且是简略图（即无向，边只衔接两个节点）。而后图论中依然有大批的差别范例的图，缺乏谱论的表白，比方有向图，超图，或则静态图。利用扩大：将同一框架利用到更多现实成绩中，如生物信息学跟社会收集剖析，怎样说明谱论视角下实在利用的法则，是一个值得摸索的范畴。© THE END 转载请接洽本大众号取得受权投稿或追求报道：[email protected] ]article_adlist--> 　　申明：新浪网独家稿件，未经受权制止转载。 -->