1 图谱简介
图论与组合是一门历史悠久而在近四十年又获得蓬勃发展的应用数学学科，是处理离散问题的强有力的工具，是整个离散数学的一个重要组成部分。图论与组合包含着十分丰富的内容，按其所研究的问题的侧重点不同，可以分为图论、计数理论、组合矩阵论、最优化理论、组合设计等几个方面。近五十年来，随着计算机科学、信息科学和系统科学的发展，图论组合及其应用的研究越来越引起人们的关注。无论从其理论价值和实际应用的广度和深度来看，图论与组合正处于一个具有强大生命力的迅速发展的新时期。
一．图的矩阵
在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻接矩阵，拉普拉斯矩阵，规范拉普拉斯矩阵等，这些矩阵与图都有着自然的联系，代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来，这里所指的矩阵的代数性质，主要指矩阵的特征值。图谱理论主要研究图的邻接矩阵、拉普拉斯矩阵和规范拉普拉斯矩阵的特征值及其特征向量，是当前代数图论、组合矩阵论和代数组合论共同关注的一个重要研究课题，极大地丰富和促进了图论和组合学的研究内容。
假设),(EVG是一个无向无环的图（简单图或多重图），其中nvvvV,,,21，meeeE,,,21。 2 定义1 G的邻接矩阵是一个nn的矩阵nnijaGA)()(，其中ija是连接顶点iv与jv的边的条数。
图的邻接矩阵的特征值，是代数图论的一个基本研究课题，已经形成相当成熟的理论。图谱的第一篇论文发表于1957 年，其结果是.
定理1 令G是n个结点的简单连通图，则
1)(1cos2nGn，
左边的等号成立，当且仅当G是一路；右边的等号成立，当且仅当G是一个完全图。
在国内该方面的研究直到1979年才出现了第一篇论文，该论文由李乔和冯克勤合写并发表在1979年的《应用数学学报》上。
代表人物: C. D. Cvetkovic.
GSPBOX_-Atoolboxforsignalprocessingongraphs_
GSPBOX:A toolbox for signal processing on graphs
Nathanael Perraudin,Johan Paratte,David Shuman,Lionel Martin Vassilis Kalofolias,Pierre Vandergheynst and David K.Hammond
March 16,2016
Abstract
This document introduces the Graph Signal Processing Toolbox (GSPBox)a framework that can be used to tackle graph related problems with a signal processing approach.It explains the structure andthe organization of this software.It also contains a general description of the important modules.
1Toolbox organization
In this document,we brie?y describe the different modules available in the toolbox.For each of them,the main functions are brie?y described.This chapter should help making the connection between thetheoretical concepts introduced in [7,9,6]and the technical documentation provided with the toolbox.We highly recommend to read this document and the tutorial before using the toolbox.Thedocumentation,the tutorials and other resources are available on-line 1.
KernelsandRegularizationonGraphs
AlexanderJ.Smola1andRisiKondor2
1MachineLearningGroup,RSISEAustralianNationalUniversityCanberra,ACT0200,AustraliaAlex.Smola@.au2DepartmentofComputerScienceColumbiaUniversity1214AmsterdamAvenue,M.C.0401NewYork,NY10027,USArisi@
Abstract.Weintroduceafamilyofkernelsongraphsbasedonthenotionofregularizationoperators.ThisgeneralizesinanaturalwaythenotionofregularizationandGreensfunctions,ascommonlyusedforrealvaluedfunctions,tographs.Itturnsoutthatdiffusionkernelscanbefoundasaspecialcaseofourreasoning.Weshowthattheclassofpositive,monotonicallydecreasingfunctionsontheunitintervalleadstokernelsandcorrespondingregularizationoperators.
1Introduction
Therehasrecentlybeenasurgeofinterestinlearningalgorithmsthatoperateon
inputspacesXotherthanRn,specifically,discreteinputspaces,suchasstrings,
GCN总结
⼀、GCN简介
GNN模型主要研究图节点的表⽰（Graph Embedding），图边结构预测任务和图的分类问题，后两个任务也是基于Graph Embedding展开的。⽬前论⽂重点研究⽹络的可扩展性、动态性、加深⽹络。
谱卷积有理论⽀持，但有时候会受到拉普拉斯算⼦的限制；⽽空间域卷积更加灵活，主要困难在于选择定量邻域上，没有统⼀理论。未来⽅向：
加深⽹络: 研究表明随着⽹络层数增加，模型性能急剧下降感受野:节点的感受野是指⼀组节点，包括中⼼节点和其近邻节点，有些节点可能只有⼀个近邻，⽽有些节点却有数千个近邻可扩展性:⼤部分图神经⽹络并不能很好地扩展到⼤型图上。动态性和异质性:⼤多数当前的图神经⽹络都处理静态同质图。⼀⽅⾯，假设图架构是固定的。另⼀⽅⾯，假设图的节点和边来⾃同⼀个来源。GCN模型具备深度学习的三种性质：层级结构（特征⼀层⼀层抽取，⼀层⽐⼀层更抽象，更⾼级）⾮线性变换 （增加模型的表达能⼒）端对端训练（不需要再去定义任何规则，只需要给图的节点⼀个标记，让模型⾃⼰学习，融合特征信息和结构信息。）GCN的四个特征：
GCN 是对卷积神经⽹络在 graph domain 上的⾃然推⼴它能同时对节点特征信息与结构信息进⾏端对端学习，是⽬前对图数据学习任务的最佳选择。图卷积适⽤性极⼴，适⽤于任意拓扑结构的节点与图。在节点分类与边预测等任务上，在公开数据集上效果要远远优于其他⽅法。
通过谱图卷积的局部⼀阶近似，来确定卷积⽹络结构，通过图结构数据中部分有标签的节点数据对卷积神经⽹络结构模型训练，使⽹络模型对其余⽆标签的数据进⾏进⼀步分类。
⼆、spectral domain
1.离散卷积是什么，在CNN中发挥什么作⽤？
离散卷积本质：加权求和CNN中的卷积本质上就是利⽤⼀个共享参数的过滤器（kernel），**通过计算中⼼像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取**，当然加权系数就是卷积核的权重系数。
