Learning Discrete Structures for Graph Neural Networks
Learning Discrete Structures for Graph Neural Networks
Luca Franceschi, Mathias, Niepert, Massimiliano Pontil, Xiao He
Intro
Graph经常会missing、corrupted，甚至有时候会得不到。
尽管graph structure在某些领域是能够得到的，但是在一些其他情况下它也需要推断或者构造。一个可能的解决方案是基于某种data points之间的similarity measure构造一个kNN graph。这个方案的一个限制是其有效性取决于k和feature space上的similarity function（这也是更重要的一个原因）。在任意情况下，graph creating和parameter learning是相互独立的，并且需要heuristics & trial & error。相应的，可以用很简单的kernel matrix来隐含地为example similarity建模，代价是引入一个dense dependency structure。（？）
这篇paper考虑另外一个方向来学习discrete and sparse dependencies，且同时训练graph convolution neural network的参数。GCN本来是通过和neighborhood passing & aggregating information来学习node representation。我们提出了对graph使用generative probabilistic model，其sample同时用于training和prediction。Edge通过random variable进行建模，且parameters被当作是bilevel learning framework中的hyper-parameters。我们迭代的sample structure的同时minimize inner objective（training error），且通过minimize outer objective（validation error）来optimize edge distribution parameters。
这是第一个方法 在semi-supervised classification问题上 同时学习一个graph和GNN参数。同时，相对独立的一个点，我们使用gradient-based hyperparameter optimization来当作discrete hyperparameters（？）。我们同时也证明了产生的graph generative model的edge probability很有意义。
Background
Graph Theory Basics
$$L = D - A$$是Laplacian matrix
Graph Neural Networks
这里专门考虑semi-supervised learning 上的graph convolutional networks。有两个input：首先是一个feature matrix $$X \in \mathcal{X}_N \subset \mathbb{R}^{N \times n}$$，每一行表示一个node feature，$$n$$是node feature dimension；其次是一个graph $$G = (V, E)$$ with adjacency matrix $$A \in \mathcal{H}_N$$。给定一个class label set $$\mathcal{Y}$$和一个labeling function $$y: V \to \mathcal{Y}$$ 将subset of nodes映射到true class label。而目标是为了学习一个函数
$$ f_w : \mathcal{X}_N \times \mathcal{H}_N \to \mathcal{Y}^N
$$
通过最小化某个regularized empirical loss
$$ L(w, A) = \sum{v \in V{Train}} \ell (f_w(X, A)_v, y_v) + \Omega(w)
$$
注意：这里每一个node有一个label。
一个例子。Kipf提出了两层layer的GCN，是
$$ L(w, A) = \text{Softmax} (\hat A \text{ReLU}(\hat A X W_1) W_2)
$$
其中$$\hat A$$是normalized adjacency matrix，$$\hat A = \tilde D^{-1/2} (A+I) \tilde D^{-1/2}$$, with diagonal $$\tilde D{ii} = 1 + \sum_j A{ij}$$
Bilevel Programming in Machine Learning
Bilevel programming，双层决策，是一个优化问题，是一个objective function中的set of variables也被限制为是另外一个优化问题的最优解。
Formally,有两个目标函数$$F$$和$$L$$，分别对应outer和inner objective，和两套variables $$\theta \in \mathbb{R}^m, w \in \mathbb{R}^{d}$$，分别对应outer和inner variables。那么bi-level program就是
$$ \min{\theta, w\theta} F(w\theta, \theta), s.t. w\theta \in \arg\min_w L(w, \theta)
$$
（问题：这个与EM的区别是什么？）
Bi-level在很多情况下都有体现，比如hyper-parameter optimization，adversarial，multi-task，和meta-learning。
解决这个问题的难点在于它的解决方案通常不是closed-form。一个标准的方法会将$$L$$的minimization替换为重复、迭代的optimization dynamics $$\Phi$$，比如SGD。让$$w{\theta, T}$$表示$$T$$个iteration之后的inner variable；也就是说 $$w{\theta, T} = \Phi(w{\theta, T-1}, \theta) = \Phi(\Phi(w{\theta, T-2}, \theta), \theta)$$ 以此类推。
如果$$\theta, w$$都是实数，objective函数和dynamics都是smooth，我们就可以计算$$F$$关于$$\theta$$的gradient，通过hypergradient $$\nabla_\theta F$$表示
$$ \partialw F(w{\theta, T}, \theta) \nabla\theta w{\theta, T} + \partial\theta F(w{\theta, T}, \theta)
$$
其中$$\partial$$表示partial derivative，而$$\nabla$$表示gradient （对于scalar function）或者total derivative。（？）
Learning Discrete Graph Structures
主要解决的问题是图的结构完全没有、部分没有、或者有noisy的情况。这里我们就学习data points之间离散稀疏的依赖关系，同时学习GCN的参数。我们将这个打包成bilevel programing问题：inner是GCN模型，而outer variable是generative probabilistic model的参数。
如图1所示，先更新GCN模型（用gradient，更新$$\tau$$次），再更新model structure（用hypergradient）。
Jointly Learning the Structure and Parameters
假设true adjacency matrix $$A$$是missing或者不完整。我们想找一个模型能够最小化generalization error。我们假设存在一个集合，validation set，我们能够估计它的generalization error。因此我们提出找到一个$$A \subset \mathcal{H}_N$$能够最小化函数：
$$ F(wA, A) = \sum{v \in V{Val}} \ell(f{w_a} (X, A)_v, y_v)
$$
$$w_A$$是$$L$$唯一的minimizer。然后就可以考虑Eq(1)和Eq(5)作为inner和outer objective，其中outer是为了找到optimal discrete graph structure，而inner是GCN的参数。
这里的bi-level programming同时包含了continuous和discrete value，使得调用hyper-gradient进行SGD比较困难。一个可行的解决方案是使用continuous relaxation，另外一个方法是在图上调用probability distribution。这里使用后者。
我们维护一个针对graph structure的generative model，然后将其重新用bi－level programming的方式表述，根据discrete graph上的continuous parameter（因为转换为了distribution）。更具体地说，这里将每一条边都符合Bernoulli分布。所有的边就是互相独立的Bournelli parameters with $$\theta \in \bar{\mathcal{H}}_N$$，然后我们就可以sample graph，通过$$\bar{\mathcal{H}}_N$$