Deep graph de-noise by differentiable ranking
A method for employing a differentiable ranking based graph sparsification (DRGS) network to use supervision signals from downstream tasks to guide graph sparsification is presented. The method includes, in a training phase, generating node representations by neighborhood aggregation operators, generating sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution, feeding the sparsified subgraphs to a task, generating a prediction, and collecting a prediction error to update parameters in the generating and feeding steps to minimize an error, and, in a testing phase, generating node representations by neighborhood aggregation operators related to testing data, generating sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution related to the testing data, feeding the sparsified subgraphs related to the testing data to a task, and outputting prediction results to a visualization device.
1. A computer-implemented method executed on a processor for employing a differentiable ranking based graph sparsification (DRGS) network to use supervision signals from downstream tasks to guide graph sparsification, the method comprising:
in a training phase:
generating node representations by neighborhood aggregation operators;
generating sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution;
feeding the sparsified subgraphs to a task;
generating a prediction;
collecting a prediction error to update parameters in the generating and feeding steps to minimize an error; and
in a testing phase:
generating node representations by neighborhood aggregation operators related to testing data;
generating sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution related to the testing data;
feeding the sparsified subgraphs related to the testing data to a task; and
outputting prediction results to a visualization device.
2. The method of claim 1 , wherein the generating node representations step in the training phase is generated by first-order neighborhood aggregation.
3. The method of claim 2 , wherein the first-order neighborhood aggregation is given by:
z (1) u =M w ( x u , {x v |v in N u }, {e u,v |v in N u }),
where z (1) u is a vector representation of node u after first-order neighborhood, x u is a vector representation of u's features, x v is a vector representation of neighbor v's attributes, e u,v is a vector representation of edge features, and M w( ) is a neighborhood aggregation function parameterized by w, where w is a learned parameter.
4. The method of claim 1 , wherein the generating node representations step in the training phase is generated by multi-order neighborhood aggregation.
5. The method of claim 1 , wherein the generating sparsified subgraphs by top-k neighbor sampling in the training phase is generated by an edge importance score.
6. The method of claim 5 , wherein the edge importance score is given by:
z u,v =MLP θ ( z u , z v , e u,v ),
where z u,v is a scalar indicating an importance score of edge (u, v), z u is a node representation of u, z v is a node representation of v, e u,v is a vector representation of edge features, and MLP θ( ) is a multi-layer neural network parameterized by θ, where θ is a learned parameter.
7. The method of claim 1 , wherein the generating sparsified subgraphs by top-k neighbor sampling in the training phase is generated by a soft permutation matrix given as:
P
sort
[
i
,
:
]
=
exp
(
(
(
n
+
1
-
2
i
)
g
u
,
i
-
A
g
[
i
,
:
]
U
)
/
τ
)
Σ
j
∈
N
u
exp
(
(
(
n
+
1
-
2
i
)
g
u
,
j
-
A
g
[
j
,
:
]
U
)
/
τ
)
,
where τ is a constant, A g [i, j]=|g u,i −g u,j |, and U is a column vector of all ones.
8. The method of claim 1 , wherein the collecting a prediction error step in the training phase includes computing an error measurement and backpropagation.
9. A non-transitory computer-readable storage medium comprising a computer-readable program for employing a differentiable ranking based graph sparsification (DRGS) network to use supervision signals from downstream 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 node representations by neighborhood aggregation operators;
generating sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution;
feeding the sparsified subgraphs to a task;
generating a prediction;
collecting a prediction error to update parameters in the generating and feeding steps to minimize an error; and
in a testing phase:
generating node representations by neighborhood aggregation operators related to testing data;
generating sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution related to the testing data;
feeding the sparsified subgraphs related to the testing data to a task; and
outputting prediction results to a visualization device.
10. The non-transitory computer-readable storage medium of claim 9 , wherein the generating node representations step in the training phase is generated by first-order neighborhood aggregation.
11. The non-transitory computer-readable storage medium of claim 10 , wherein the first-order neighborhood aggregation is given by:
z (1) u =M w ( x u , {x v |v in N u }, {e u,v |v in N u }),
where z (1) u is a vector representation of node u after first-order neighborhood, x u is a vector representation of u's features, x v is a vector representation of neighbor v's attributes, e u,v is a vector representation of edge features, and M w( ) is a neighborhood aggregation function parameterized by w, where w is a learned parameter.
12. The non-transitory computer-readable storage medium of claim 9 , wherein the generating node representations step in the training phase is generated by multi-order neighborhood aggregation.
13. The non-transitory computer-readable storage medium of claim 9 , wherein the generating sparsified subgraphs by top-k neighbor sampling in the training phase is generated by an edge importance score.
14. The non-transitory computer-readable storage medium of claim 13 , wherein the edge importance score is given by:
z u,v =MLP θ ( z u , z v , e u,v ),
where z u,v is a scalar indicating an importance score of edge (u, v), z u is a node representation of u, z v is a node representation of v, e u,v is a vector representation of edge features, and MLP θ( ) is a multi-layer neural network parameterized by θ, where θ is a learned parameter.
15. The non-transitory computer-readable storage medium of claim 9 , wherein the generating sparsified subgraphs by top-k neighbor sampling in the training phase is generated by a soft permutation matrix given as:
P
sort
[
i
,
:
]
=
exp
(
(
(
n
+
1
-
2
i
)
g
u
,
i
-
A
g
[
i
,
:
]
U
)
/
τ
)
Σ
j
∈
N
u
exp
(
(
(
n
+
1
-
2
i
)
g
u
,
j
-
A
g
[
j
,
:
]
U
)
/
τ
)
,
where τ is a constant, A g [i, j]=|g u,i −g u,j |, and U is a column vector of all ones.
16. The non-transitory computer-readable storage medium of claim 9 , wherein the collecting a prediction error step in the training phase includes computing an error measurement and backpropagation.
17. A system for employing a differentiable ranking based graph sparsification (DRGS) network to use supervision signals from downstream 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 node representations by neighborhood aggregation operators;
generate sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution;
feed the sparsified subgraphs to a task;
generate a prediction;
collect a prediction error to update parameters in the generating and feeding steps to minimize an error; and
in a testing phase:
generate node representations by neighborhood aggregation operators related to testing data;
generate sparsified subgraphs by top-k neighbor sampling from a learned neighborhood ranking distribution related to the testing data;
feed the sparsified subgraphs related to the testing data to a task; and
output prediction results to a visualization device.
18. The system of claim 17 , wherein the generating node representations step in the training phase is generated by first-order neighborhood aggregation.
19. The system of claim 18 , wherein the first-order neighborhood aggregation is given by:
z (1) u =M w ( x u , {x v |v in N u }, {e u,v |v in N u }),
where z (1) u is a vector representation of node u after first-order neighborhood, x u is a vector representation of u's features, x v is a vector representation of neighbor v's attributes, e u,v is a vector representation of edge features, and M w ( ) is a neighborhood aggregation function parameterized by w, where w is a learned parameter.
20. The system of claim 17 , wherein the generating node representations step in the training phase is generated by multi-order neighborhood aggregation.