Method for supervised graph sparsification
A method for employing a supervised graph sparsification (SGS) network to use feedback from subsequent graph learning tasks to guide graph sparsification is presented. The method includes, in a training phase, generating sparsified subgraphs by edge sampling from input training graphs following a learned distribution, feeding the sparsified subgraphs to a prediction/classification component, collecting a predication/classification error, and updating parameters of the learned distribution based on a gradient derived from the predication/classification error. The method further includes, in a testing phase, generating sparsified subgraphs by edge sampling from input testing graphs following the learned distribution, feeding the sparsified subgraphs to the prediction/classification component, and outputting prediction/classification results to a visualization device.
1. A computer-implemented method executed on a processor for employing a supervised graph sparsification (SGS) network to use feedback from subsequent graph learning tasks to guide graph sparsification, the method comprising:
in a training phase:
generating sparsified subgraphs by edge sampling from input training graphs following a learned distribution;
feeding the sparsified subgraphs to a prediction/classification component;
collecting a predication/classification error; and
updating parameters of the learned distribution based on a gradient derived from the predication/classification error; and
in a testing phase:
generating sparsified subgraphs by edge sampling from input testing graphs following the learned distribution;
feeding the sparsified subgraphs to the prediction/classification component; and
outputting prediction/classification results to a visualization device:
wherein the edge sampling from the input training graphs includes:
determining edge sampling probabilities; and
sampling differentiable edges by Gumbel-Softmax: and
wherein an importance of an edge is given by:
z u,v =MLP θ ( x u , x v , e u,v ),
where z u,v is a scalar indicating an importance of edge (u, v), x u is a vector representation of u's attributes, x v is a vector representation of v's attributes, e u,v is a vector representation of edge attributes, and MLP θ ( ) is a multi-layer neural network parameterized by θ.
2. The method of claim 1 , wherein a probability that the edge (u, v) is sampled is given by:
π
u
,
v
=
exp
(
z
u
,
υ
)
∑
w
∈
N
u
exp
(
z
u
,
w
)
.
3. The method of claim 2 , wherein the differentiable edge sampling by the Gumbel-Softmax provides a sparse vector is given by:
s
v
=
exp
(
(
log
(
π
u
,
v
)
+
ε
v
)
/
τ
)
∑
w
∈
N
u
exp
(
(
log
(
π
u
,
w
)
+
ε
w
)
/
τ
)
where τ is a constant and s v is expected to be either close to 0 or 1 with Σ v∈N u s v =1.
4. The method of claim 1 , wherein the sparsified subgraphs are fed into graph neural networks (GNNs) to learn a graph representation for subsequent prediction components.
5. The method of claim 4 , wherein the sparsified subgraphs are k-neighbor subgraphs.
6. The method of claim 5 , wherein the sparsified subgraphs are sampled before applying the GNNs.
7. The method of claim 1 , wherein samples from the edge sampling from input training and testing graphs are differentiable.
8. A non-transitory computer-readable storage medium comprising a computer-readable program for employing a supervised graph sparsification (SGS) network to use feedback from subsequent graph learning tasks to guide graph sparsification, wherein the computer-readable program when executed on a computer causes the computer to perform the steps of:
in a training phase:
generating sparsified subgraphs by edge sampling from input. training graphs following a learned distribution;
feeding the sparsified subgraphs to a prediction/classification component;
collecting a predication/classification error; and
updating parameters of the learned distribution based on a gradient derived from the predication/classification error; and
in a testing phase:
generating sparsified subgraphs by edge sampling from input testing graphs following the learned distribution;
feeding the sparsified subgraphs to the prediction/classification component; and
outputting prediction/classification results to a visualization device;
wherein the edge sampling from the input training graphs includes:
determining edge sampling probabilities; and
sampling differentiable edges by Gumbel-Softmax; and
wherein an importance of an edge is given by:
z u,v =MLP θ ( x u , x v , e u,v ),
where z u,v is a scalar indicating an importance of edge (u, v), x u is a vector representation of u's attributes, x v is a vector representation of v's attributes, e u,v is a vector representation of edge attributes, and MLP θ ( ) is a multi-layer neural network parameterized by θ.
9. The non-transitory computer-readable storage medium of claim 8 , wherein a probability that the edge (u, v) is sampled is given by:
π
u
,
v
=
exp
(
z
u
,
v
)
∑
w
∈
N
u
exp
(
z
u
,
w
)
.
10. The non-transitory computer-readable storage medium of claim 9 , wherein the differentiable edge sampling by the Gumbel-Softmax provides a sparse vector is given by:
s
v
=
exp
(
(
log
(
π
u
,
v
)
+
ε
v
)
/
τ
)
∑
w
∈
N
u
exp
(
(
log
(
π
u
,
w
)
+
ε
w
)
/
τ
)
where τ is a constant and s v is expected to be either close to 0 or 1 with Σ v∈N u s v =1.
11. The non-transitory computer-readable storage medium of claim 8 , wherein the sparsified subgraphs are fed into graph neural networks (GNNs) to learn a graph representation for subsequent prediction components.
12. The non-transitory computer-readable storage medium of claim 11 , wherein the sparsified subgraphs are k-neighbor subgraphs.
13. The non-transitory computer-readable storage medium of claim 12 , wherein the sparsified subgraphs are sampled before applying the GNNs.
14. The non-transitory computer-readable storage medium of claim 8 , wherein samples from the edge sampling from input training and testing graphs are differentiable.
15. A system for employing a supervised graph sparsification (SGS) network to use feedback from subsequent graph learning tasks to guide graph sparsification, the system comprising:
a memory; and
one or more processors in communication with the memory configured to:
in a training phase:
generate sparsified subgraphs by edge sampling from input training graphs following a learned distribution;
feed the sparsified subgraphs to a prediction/classification component;
collect a predication/classification error; and
update parameters of the learned distribution based on a gradient derived from the predication/classification error; and
in a testing phase:
generate sparsified subgraphs by edge sampling from input testing graphs following the learned distribution;
feed the sparsified subgraphs to the prediction/classification component; and
output prediction/classification results to a visualization device;
wherein the edge sampling from the input training graphs includes determining edge sampling probabilities and sampling differentiable edges by Gumbel-Softmax; and
wherein an importance of an edge is given by:
z u,v =MLP θ ( x u , x v , e u,v ),
where z u,v is a scalar indicating an importance of edge (u, v), x u is a vector representation of u's attributes, x v is a vector representation of v's attributes, e u,v is a vector representation of edge attributes, and MLP θ ( ) is a multi-layer neural network parameterized by θ.