首页 > 其他分享 >Graph Condensation for Graph Neural Networks

Graph Condensation for Graph Neural Networks

时间:2023-12-24 15:58:17浏览次数:34  
标签:mathbb Condensation mathbf Graph text mathcal theta GNN Networks

目录

Jin W., Zhao L., Zhang S., Liu Y., Tang J. and Shah N. Graph condensation for graph neural networks. ICLR, 2022.

图上做压缩的工作.

符号说明

  • \(\mathbf{A} \in \mathbb{R}^{N \times N}\), 邻接矩阵;
  • \(\mathbf{X} \in \mathbb{R}^{N \times d}\), 结点特征;
  • \(\mathbf{Y} \in \{0, \ldots, C - 1\}^N\), labels;
  • \(\mathcal{T} = \{\mathbf{A}, \mathbf{X}, \mathbf{Y}\}\), a graph dataset;

Motivation

  • 我们知道, 在不通过 graph sampling 等方法的时候, 在一个规模很大的图上 (\(N\) 很大) 进行训练是很吃资源的, 所以, 本文希望能够对图数据进行压缩, 即构造一个

    \[\mathcal{S} = \{\mathbf{A}', \mathbf{X}', \mathbf{Y}'\}, \quad \mathbf{A}' \in \mathbb{R}^{N' \times N'}, \mathbf{X}' \in \mathbb{R}^{N' \times D}, \mathbf{Y}' \in \{0, 1, \ldots, C-1\}^{N'} \]

    的小数据集 (\(N' \ll N\)), 希望通过 \(\mathcal{S}\) 训练得到的模型和通过 \(\mathcal{T}\) 训练得到的模型性能上是接近的.

  • 严格来说, 我们希望求解如下的一个 bi-level 的问题:

    \[\min_{\mathcal{S}} \mathcal{L}(\text{GNN}_{\theta_{\mathcal{S}}} (\mathbf{A}, \mathbf{X}), \mathbf{Y}), \quad \text{s.t.} \: \theta_{\mathcal{S}} = \text{argmin}_{\theta} \mathcal{L}(\text{GNN}_{\theta}(\mathbf{A}', \mathbf{X}'), \mathbf{Y}'). \]

  • 为了防止对某个初始化参数 over-fitting, 可以进而求解如下的问题:

    \[\min_{\mathcal{S}} \mathbb{E}_{\theta_0 \sim P_{\theta_0}} [\mathcal{L}(\text{GNN}_{\theta_{\mathcal{S}}} (\mathbf{A}, \mathbf{X}), \mathbf{Y})], \quad \text{s.t.} \: \theta_{\mathcal{S}} = \text{argmin}_{\theta} \mathcal{L}(\text{GNN}_{\theta}(\mathbf{A}', \mathbf{X}'), \mathbf{Y}'). \]

GCOND

  • 当然了, 直接取求解 bi-level 问题是困难的, 本文采取 Gradient Matching 来解决这一问题.

  • 假设在第 \(t\) 步, 我们有:

    \[\theta_{t+1}^{\mathcal{S}} \leftarrow \theta_t^{\mathcal{S}} - \eta \nabla_{\theta} \mathcal{L}( \text{GNN}_{\theta_t^{\mathcal{S}}}(\mathbf{A}', \mathbf{X}'), \mathbf{Y}'), \\ \theta_{t+1}^{\mathcal{T}} \leftarrow \theta_t^{\mathcal{T}} - \eta \nabla_{\theta} \mathcal{L}( \text{GNN}_{\theta_t^{\mathcal{T}}}(\mathbf{A}', \mathbf{X}'), \mathbf{Y}'). \]

  • Gradient matching 希望:

    \[ \min_{\mathcal{S}} \mathbb{E}_{\theta_0 \sim P_{\theta_0}}[ \sum_{t=0}^{T-1} D(\theta_t^{\mathcal{S}}, \theta_{t}^{\mathcal{T}})]. \]

  • 这么做的原因是, 倘若在 \(\mathcal{S}\) 上训练的参数的更新过程和在 \(\mathcal{T}\) 上的差不多, 那么很自然最后的模型也会差不多.

  • 我们可以进一步将上面的的目标转换为:

    \[\min_{\mathcal{S}} \mathbb{E}_{\theta_0 \sim P_{\theta_0}}\Bigg[ \sum_{t=0}^{T-1} D( \nabla_{\theta} \mathcal{L}( \text{GNN}_{\theta_t}( \mathbf{A}', \mathbf{X}' ), \mathbf{Y}' ), \nabla_{\theta} \mathcal{L}( \text{GNN}_{\theta_t}( \mathbf{A}, \mathbf{X} ), \mathbf{Y} ) ) \Bigg]. \]

    其中 \(D\) 为每一层的距离, 对于每一列有

    \[ dis(\mathbf{G}^{\mathcal{S}}, \mathbf{G}^{\mathcal{T}}) = \sum_{i=1}^{d_2}\bigg( 1 - \frac{ \mathbf{G}_i^{\mathcal{S}} \cdot \mathbf{G}_i^{\mathcal{T}} }{ \|\mathbf{G}_i^{\mathcal{S}}\| \| \mathbf{G}_i^{\mathcal{T}} \| } \bigg). \]

  • 剩下的问题是, \(\mathcal{S}\) 如何量化, 一种直接的策略是把 \(\mathbf{A}', \mathbf{X}', \mathbf{Y}'\) 设定为参数去学习. 但是这么做 1. 计算量大; 2. 训练难度也大 (个人感觉是灵活度太高了).

  • 所以, 作者首先固定 \(\mathbf{Y}'\), 让其和 \(\mathbf{Y}\) 保持同样的分布.

  • 接着, 作者令 \(\mathbf{X}'\) 自由学习, 并令

    \[ \mathbf{A}_{ij}' = \text{Sigmoid}\bigg( \frac{ \text{MLP}_{\Phi}([\mathbf{x}_i'; \mathbf{x}_j']) +\text{MLP}_{\Phi}([\mathbf{x}_j'; \mathbf{x}_i']) }{2} \bigg), \]

    容易发现 \(\mathbf{A}_{ij}'\) 是对称的.

代码

[official]

标签:mathbb,Condensation,mathbf,Graph,text,mathcal,theta,GNN,Networks
From: https://www.cnblogs.com/MTandHJ/p/17924450.html

相关文章

  • 将perf跟funcgraph-retval结合起来使用
    作者[email protected]概述下面是之前写的使用funcgraph-retval的文章:https://www.cnblogs.com/pengdonglin137/p/17126952.htmlhttps://www.cnblogs.com/pengdonglin137/p/17723412.html上面的文章里,都是直接通过命令行配置ftrace来使用的,过程稍微有些繁琐,linux提供......
  • Flink源码解析(九)——ExecutionGraph生成过程解析
    一、ExecutionGraph介绍介绍ExecutionGraph是调度Flink作业执行的核心数据结构,包含了作业中所有并行执行的Task信息、Task之间的关联关系、数据流转关系。相比于StreamGraph、JobGraph,ExecutionGraph加入了并行度的概念,成为真正可调度的图结构。下图是一个ExecutionGraph的简单示......
  • Codeforces 1900E Transitive Graph
    考虑题目的限制条件:存在$a\tob,b\toc$的边,就会有$a\toc$的边。考虑$p_{1\simk}$,满足这$k$个点按顺序组成了一个环且无重点。那么$p_1\top_2,p_2\top_3$,就有$p_1\top_3$,又有$p_3\top_4$,所以有$p_1\top_4$。以此类推,会发现$\foralli,j\in[1,k],i\not......
  • [Qt5] QGraphics图形视图框架概述(Item、Scene和View)
    作者:丶布布文章预览:......
  • 论文阅读-Self-supervised and Interpretable Data Cleaning with Sequence Generativ
    1.GARF简介代码地址:https://github.com/PJinfeng/Garf-master基于SeqGAN提出了一种自监督、数据驱动的数据清洗框架——GARF。GARF的数据清洗分为两个步骤:规则生成(RulegenerationwithSeqGAN):利用SeqGAN学习数据中的关系(datarelationship)。然后利用SeqGAN中......
  • [ARC105E] Keep Graph Disconnected
    NOIP模拟赛原题,赛时还是没切。正解奇偶性。考虑最终不能走的时候是什么情况,当且仅当图中只剩下两个联通块了。设其中一个联通块的点数为\(k\),那么另一个的点数为\(n-k\)。所以两人一共的操作次数为\(sum=\frac{n\times(n-1)}{2}-m-k\times(n-k)\)。显然如果\(sum......
  • LightGCL Simple Yet Effective Graph Contrastive Learning For Recommendation论文
    Abstract目前的图对比学习方法都存在一些问题,它们要么对用户-项目交互图执行随机增强,要么依赖于基于启发式的增强技术(例如用户聚类)来生成对比视图。这些方法都不能很好的保留内在的语义结构,而且很容易受到噪声扰动的影响。所以我们提出了一个图对比学习范式LightGCL来减轻基于CL......
  • BIgdataAIML-IBM-A neural networks deep dive - An introduction to neural networks
    https://developer.ibm.com/articles/cc-cognitive-neural-networks-deep-dive/ByM.TimJones,PublishedJuly23,2017Neuralnetworkshavebeenaroundformorethan70years,buttheintroductionofdeeplearninghasraisedthebarinimagerecognitionand......
  • Local Relation Networks for Image Recognition: LRNet
    LocalRelationNetworksforImageRecognition*Authors:[[HanHu]],[[ZhengZhang]],[[ZhendaXie]],[[StephenLin]]DOI:10.1109/ICCV.2019.00356@inproceedings{Hu2019,doi={10.1109/iccv.2019.00356},url={https://doi.org/10.1109/iccv.2019.00356......
  • Squeeze-and-Excitation Networks:SENet,早期cv中粗糙的注意力
    Squeeze-and-ExcitationNetworks*Authors:[[JieHu]],[[LiShen]],[[SamuelAlbanie]],[[GangSun]],[[EnhuaWu]]Locallibrary初读印象comment::(SENet)以前的工作都是在提高CNN的空间编码能力。这篇论文提出了“Squeeze-and-Excitation”块,研究通道之间的关系。......