Wasserstein diffusion on graphs with missing attributes
Authors: Zhixian Chen
Tengfei Ma
Yangqiu Song
Yang Wang
Venue:  (2021)
Keywords: Wasserstein barycenter
graph learning
diffusion
missing features
matrix completion

Abstract: Many real-world graphs are attributed graphs where nodes are associated with non-topological features. While attributes can be missing anywhere in an attributed graph, most of existing node representation learning approaches do not consider such incomplete information.
In this paper, we propose a general non-parametric framework to mitigate this problem. Starting from a decomposition of the attribute matrix, we transform node features into discrete distributions in a lower-dimensional space equipped with the Wasserstein metric. On this Wasserstein space, we propose Wasserstein graph diffusion to smooth the distributional representations of nodes with information from their local neighborhoods. This allows us to reduce the distortion caused by missing attributes and obtain integrated representations expressing information of both topology structures and attributes. We then pull the nodes back to the original space and produce corresponding point representations to facilitate various downstream tasks. To show the power of our representation method, we designed two algorithms based on it for node classification (with missing attributes) and matrix completion respectively, and demonstrate their effectiveness in experiments.

Under review as a conference paper at ICLR 2021
WASSERSTEIN DIFFUSION ON GRAPHS WITH MISSING ATTRIBUTES
Anonymous authors Paper under double-blind review
A ABSTRACT
Many real-world graphs are attributed graphs where nodes are associated with non-topological features. While attributes can be missing anywhere in attributed graph, most of existing node representation learning ap- proaches do not consider such incomplete information. Tn this paper, we propose general non-pon non-parametric framework to mitigate this problem. Start- ing from a decomposition of the attribute matrix, we transform node features into discrete distributions in lower-dimensional space equipped with the Wasserstein metric. On this Wasserstenn space, we propose Wasserstein graph diffusion to smooth the distribution representations of nodes with information from their local neighborhoods. This allows us to reduce the distortion caused by missing altribules and obtain integrated representations expressing information of both topology structure and attributes. We then pull the nodes back to the original space and produce corresponding point representations to facilitate various downstream tasks. To show the power of our representation method, we designed two algorithms basod on for node classification (with missing attributes) and matrix completion respectively, and demonstrate their effectiveness in experiments.
INTRODUCTION
Many real-world networks are attributed networks, where nodes are not only connected with other nodes, but also associated with features, e.g., social network users with profiles or keywords showing interests, Internet Web pages with content information, etc. Learning node representations underlie various downstream graph-based learning tasks and have attracted
much attention (Perozzi et al.) 2014 Grover & Leskovec, 2016 Pimentel et al. 2017 Duarte et al. 2019 A high-quality node representation is able to express node-attributed and graph-structured information and can better capture meaningful latent information.
Random walk based graph embedding approaches (Perozzi et al. 2014 Grover & Leskovec 2016) exploit graph structure information to preserve pre-specified node similarities in the embedding space and have proven successful in various applications based on plain graphs. In addition, graph neural networks, many of which base on the message passing schema (Gilmer al. 2017), aggregate information from neighborhoods and allow us to incorporate attribute and structure information effectively. However, most of the methods, which embed nodes into dower-dimensional Euelidean space, suffer from common limitations: they fail to model complex patterns or capture complicated latent information stemming from the limited representation capacity of the embedding space. There has recently been a tendency to embed nodes into more complex larget space with attempt. to increase the ability to express composite information.
prominent example Wasserstein embedding that represents nodes as probability distributions (Bojchevski & Günnemann 2018 Muzellec & Cuturi 2018 Frogner et al. 2019) equipped with Wasserstein metric. common practice is to learn mapping from original space to Wasserstein space by minimizing distortion while the objective functions are usually difficult to optimize and require expensive computations.
On the other hand, most representation learning methods highly depend the completeness of observed node attributes which are usually partially absent and even entirely inaccessible in real-life graph data. For instance, in the case of social networks like Facebook and Twitter, in

---

Under review as a conference paper at ICLR 2021
which personal information is incomplete as users not willing to provide their information for privacy concerns. Consequently, presentation learning models that require fully observed attributes may not be able to cope with these types of real-world networks.
In this paper, we propose a novel non-parametric framework to mitigate this problem. Starting from decomposition of the attribute matrix, we transform node features into discrete distributions in a lowor-dimensional space equipped with the Wasscrstein metric and implicitly implement dimension reduction which greatly reduces computational complexity.
Preserving node similarity is a common precondition for incorporating structural information into representation learning. Based this, we develop a Wasserstein graph diffusion process to effectively propagate a node distribution to its neighborhood and contain node similarity in the Wasserstein space. To some extent, this diffusion operation implicitly compensates for the loss of information by aggregating information from neighbors. Therefore, we reduce the distortion caused by missing attributes and obtain integrated node representations representing node attributes and graph structure.
In addition to produce distribution representations ions, our framework can leverage the inverse mapping to transform the node distributions back to node features (point representations). Experimentally, we show that these node features are efficient, node representations and well- suited to various downstream learning tasks. More precisely, to comprehensively investigate the representation ability, we examine our framework on node classification concerning two missing cases: partially missing and entire node attributes missing. Morcover, we adapt our framework for matrix complction to show our ability to recover absent values.
Contributions. We develop novel non-parametric framework for node representation learning to utilize incomplete node-attributed information ion. The contributions of our frame- work are: 1. embedding nodes into low-dimension discrete Wasserstein space through matrix decomposition; 2. reducing distortion caused by incomplete information and pro- ducing effective distribution representations for expressing both attributes and structure information through the Wasserstein graph diffusion process; 3. reconstructing node features which can be usod for various downstream tasks as well as for matrix completion.
2 BACKGROUND AND RELATED WORK
Graph representation learning
In this paper, we focus on learning node representations on attributed graphs. There are many effective graph embedding approaches, such as DeepWalk (Bojchevski & Günnemann 2018), node2vec (Grover & Leskovec 2016), Gen Vetor (Duarte et al. 2019), which embed nodes into a lower-dimension Euclidean space and preserve graph structure while most of them disregard node informative attributes. So far, there are little attention paid to attribute information (Yang et al. 2015 Gao & Huang 2018 Hong et | 2019). The advent of graph neural networks (Bruna et al. 2014 Kipl & Welling 201 707710 Hamilton et al.,
2017 Veličković et al., 2017 Gilmer et al. 2017 Klicpera et al. 2019a b) fill the gap to some extent, by defining graph convolutional operations in spectral domain or aggregating neighborhood information in spatial domain. Their learned node representation integrate both node attributes and graph structure information.
Due to the expressive limitation of Euclidean space, embedding into a more complex target space has been explored. There are several works to leverage distributions equipped with Wasserstein distance to model complex data since a probability is well-suited for modeling uncertainty and flexibility of complex networks. For instance, Graph2Gauss (Bojchevski & Günnemann 2018 represents node Gaussian distributions such that uncertainty and complex interactions across nodes are reflected in the embeddings. Similarly, [Muzellec & be thought of as particular case of clliptical distributions embodding. Frogner et al.) (2019) learn to compute minimum-distortion embeddings in discrete distribution space such that the underlying distances of input space are preserved approximately.
Cuturi 2018 presented framework in which point embedding
Missing attributes
2

---

Under review as a conference paper at ICLR 2021
The completeness and adequacy of attribute information is precondition for learning high-quality node embeddings an attributed graph. To represent incomplete attributes in the embeddings, fundamental method is providing plausible imputations for missing values, There is a variety of missing value imputation (MVT) techniques such as mean imputation, KNN imputation (Troyanskaya al. 2001), softimpute (Hastie al. 2015), and on.
As a consequence, the representation capacity of the generated embeddings is inherently bounded by the reconstruction ability of the imputation methods. As the number of missing attributes increases, this can lead to distortion problems as well as unstable learning. The herein proposed method is the first work to compute embeddings of graph with incomplete attributes directly.
3 WASSERSTEIN GRAPH DIFFUSION (WGD) FRAMEWORK
In this paper, we propose a non- con-parameerrc Wasserstein graph diffusson (WGD) framework graph with missing attributes to generate node representations. The WGD framework (depicted in Fig consists of three main components: 1.space transformation to embed nodes into Wasserstein space; 2. Wasserstein graph diffusion to update node distribution representations; 3. inverse transformation to pull nodes back to the original feature space.
Space of Upok
gpAce tronsfurm
Wasserstain Spane
4.
Borycrater Uysints
62
Feature Space
moypling
Roslls Vaces
metric
Support puints Supp(U))
Xasa
Figure 1: The WGD Framework involves transformations among three space: feature space, principal component space and discrete Wasserstein space. SVD is leveraged to generate initial node representations UPin principal component space which will be transformed to discrete distributions endowed with Wasserstein distance through particular reversible positive mapping. In this discrete Wasserstein space, we utilize Wasserstein barycenter to aggregate distributional information of h hop neighbors. In each WGD layer, the updated node distributions will be transformed back to the principal component space to update corresponding node representations which is also the input of next layer. The support points are shared over layers. After L times update, we pull UK back to the original feature space through inverse mapping to generate new node representations.
3.1 PRELIMINARY: WASSERSTEIN DISTANCE
Wasserstein distance is an optimal transport metric, which measures the distance traveled in transporting the mass in one distribution to match another. The p- Wasserstein distance between two distributions and v over metric space X' is defined as
1/P
W Wp(n,v) (n inf I d(., ()
(a.)))(()))) 2xxx
where I(u, v) is the the set of probabilistic couplings (n, d(æ, y) is ground metric on X. this paper, we take p = 2. The Wasserstein space is a metric space that endow probability distributions with the Wasserstein distance.
3

---

Under review as a conference paper at ICLR 2021
3.2 THE SPACE TRANSFORMATION
Space transformation is the first step of our WGD framework, which attempts to transform node features to discrete distributions endowed with the Wasserstein metric.
common assumption for matrix completion is that the matrix is low-ranked, iee. the features lie in smaller subspace, and the missing features space. Inspired by Alternating Least Square imputation method which follows this assumption and uses SVD to factorize matrix into low-ranked submatrices, we first decompose the feature matrix X E R=xm into a principal component matrix U, an singular value matrix A, and an orthogonal basis matrix V, i.c. X = UAVT. For dimensionality reduction, we only account for the first lo singular vectors of V:
be recovered from this Algorithm, a well known missing value
Uk, AR, V = SV),
(1)
here Uk E Rnxk, V&2 E Rm** and A₂ Rlxk To impute missing entries, ALS alternatively optimizes these submatries. While our method is not for matrix completion and not need to optimize Us and Ve. We aim to generate expressive node appreentaaiinss components space where UR is the initial node embedding matrix. It is worth noting that such node representations have strong semantic information: each feature dimension is basis vector from Ve. Moreover, in broad sense (allowing the existence of negative frequencies), we can express nodes as general histograms with principal components (the rows of Uk, noted as row((Uk)), acting frequencics and basis vectors (the columns of Vk, noted as col(V):) acting as bins. Therefore, to capture the ground semantic information, we transform UR from a Euclidean space to discrete distribution space. More precisely, this space transformation involves a reversible positive function (here we use the exponential function for implementation) and normalization operation:
the principal
(2) Here, UK can be seen as the discrete distributions of nodes which have common support points (Vx with the notation supp(Uk), i.e. supp(Uk) co.(V)).. Each row of Uy is a discrete distribution with the form u, = E, asjo, where ag are weigths summing to 1, and oy is a column of V&2 as well as a support point. The distance of various support points, noting that A is the square root of the eigenvalues of X TT,, i.e. we define the ground metric as follows:
Up == ((U))) = (ormalize(<xp(rooo((a))))
d(e, 0y) =|1 X(u; - uÿ) ||==|| Aud; AUju, 12= A3,1-
(3)
Here, is and 2y refer to the i-th and j-th support points which are mutual orthogonal unit vectors. In the meantime, we equip node discrete distributions Üg with Wasserstein metric:
W3 () = min tottrr(D (DDTT subject to T1 = üss T = =ūz-
(4)
720
Here D E Baxk refers to the underlying distance matrix with Dij = d(vs, Uz).
3.3 THE WASSERSTEIN CRAPH DIFFUSION PROCESS
Although we produce node distribution representations from space transformation, the information extracted from such reprosentations is limited and distorted caused by missing attributes. To reduce the distortion, we carry out the Wasserstein graph diffusion process to smooth node distributions over its local neighborhood such that valid information extracted from different node altributes can be shared, iee. informational complementarity. The Wasserstein graph diffusion can boil down to aggregation operation realized by computing Wasserstein barycenter that is exactly the updated node representations. In this way, both topology structure information and the aforementioned integrated attribute information are incorporated into node representations. Note that it is similar to the message aggregation in graph neural networks, except we do in Wasserstein space and introduce no parameters.
We denote the node distribution updale process as Barycenter Updale:
Carrycenter-upultteee. D) = arg inf (EN(()
Σ
(5)
P [Nu)
4

---

Under review as a conference paper at ICLR 2021
here M(u) = (() {u), M(u) refers to the neighbors of [Nu equals to the degree of u (with self-loop) and ú' refers to the discrete distribution of node w'. Similar to common message aggregation graph, the Wasserstein diffusion process inchuded times Barycenter Update can affect Z-hop neighbors.
Recall that the set of support points of barycenter, noted Su, contains all possible combination of the common support points supp(U?) shared by all initial node distributions:
S. = (u))
Σ
aalos E supp(Ue)).
(6)
Noting that, as the Barycenter Update process goes on, nodes will not share the same support points any more and their set of support points will be larger and larger that dramatically increase the computation. On the other hand, such a free-support problem notoriously difficult to solve. Therefore, we leverage the fixed-support Wasserstein barycenter for the update that preserves the initial support supp(Ux). Therefore, no matter how many times update node distributions, they always share the common support points. In practice, we use Iterative Bregman Projection (IBP) algorithm (Benamou et al. 2015 to obtain the fixed-support barycenter (see Algorithm The Wasserstein diffusion process is formulated as follows:
0 = (Uk): 0(+1)_ Barycenter Update(Uk)) D) with fixed supp(Uk))
(7)
Through the Wasserstein diffusion process, we obtain the updated node distributions Uk which have an effective ability represent node attributes and graph structure.
Algorithm 1 Iterative Bregman Projection for Barycenter Update
input: discrete distribution matrix Paxas distance matrix Daxd', weights vector w, e.
I: initialize: K = exp(-D/e), Vo = 1
2: for i .....M. ..M do p
3: U, KV:
4:
p: = exp(log( UU))w
5:
V x
6: end for
7:
output: PM
3.4 THE INVERSE TRANSFORMATION
We first derive an approximate inverse transformation from the prespecified mapping (2) to convert the updated distribution representations Üs to the principal component space:
U = www.-ccciii..Otttooooooooooooooo
(8)
refers to the Gram-Schmidt Orthogonalization processing used to hold the semantic structure of the principal component space. In addition, side effect, empirical results show that orthogonalizing node embeddings can efficiently alleviate over-smoothing problem.
Here
On the other hand, SVD separates the observed attribute information into two parts: one is extracted by the updated node distributions while the other maintains in the fixed support points. To generate more expressive node representation incorporating both the two parts of information, pull nodes back to the feature space:
x ÜUAAA
(9)
Note that this X not matrix completion for the original X, since the elements in X do not remain the same. Instead, it is transformation of the representation Us after our Wasserstein diffusion process, by combing with neural networks it can be then used for various downstreaming tasks, as will show in the next section.
5

---

Under review as a conference paper at ICLR 2021
4 EMPIRICAL STUDY
As explained in the previous section, our WGD framework can incorporate node attributes and graph structure to reconstruct node representations in the original space, i.e. the feature matrix. Thercfore, it is well-suited for various downstream learning tasks as well as matrix completion. In this section, adapt WGD for node classification tasks and matrix completion then evaluate the quality of reconstructed node features (representations) respectively.
4.1 NODE CLASSIFICATION ON GRAPHS WITH MISSING ATTRIBUTES
In this section, we apply our framework to node classification tasks on attributed graphs with missing features. Algorithm Sanrrihmmmummmmiieee summarizes the architecture. Each WGD layer (the outer loop) contains three main stages: space transformation, Wasserstein diffusion, and inverse transformation. The explicit formulas of space transformation and inverse transformation are given by (2) and (8). In the diffusion process, we conduct Barycenter Update 7 h times to aggregate h-hopp neighbors probability information and take the mean outputs of each layer the updated principal components matrix to avoid over smoothing. We reconstruct feature matrix (9) (acting as updated node representations) on the original space and feed them to two-layer MLP for node classification, termed WGD-MLP.
To confirm the importance of the Wasserstein diffusion process, we propose an ablation framework, called SVD-GCN in which skip the diffusion process and remain the other stages unchanged. The forward formula of + 1-th SVD-GCN layer is:
= A4 V (T with U Ak. vi SVD(X",,),
(10)
Precisely, we leverage low-rank SVD to factorize the matrix then feed the reconstructed feature matrix to two-layer GCN (Kipf & Welling 2017 Furthermore, to show that matrix decomposition is necessary, provid an additional ablation framework, termed WE-MLP. In this baseline, we directly transform node features to discrete distributions skipping the stage of matrix decomposition. The forward formula of 1 + 1-th WE-MLP layer is:
((+1) log( Seteryceeteeuuudueeeeeeeee Uuw.uuulaaeeoommmleeeesess'A"""" ()))
(11)
After that, we feed the output that is identical the updated node represcntations to two-layer MLP for node classification.
Algorithm 2 WGD adapted for node classification on graphs with missing attributes input: attribute matrix Xaxm containing initial values, k.
1: Apply k-rank SVD to X: Un, Ag, Vv SVD(X,
2: U Ux
3: for 1=1 L do
4:
space transformation: Uh (1-1))
(ormalze((xpp(Too00
5: ((0) - (-1)
6: for iori= 1 do
t(0 Barycenter_Updatt(
7:
Wasserstein diffusion:
8: end for
9: inverse transformation: u( = Gram Schmidt Ortho(col(log(( (U)(((())))
10: end for
11: U2 = mmean(Ul)) .... U(()
12: X = =UAAVV.
13: Apply MLP for node classification: Y MLP(X)
Experimental Settings. In the experiments of node classification, implicitly evaluate the ability of WGD to produce high-quality node representations utilizing incomplete attribute information. Since node attributes of common benchmarks of node classification, such as citation networks, are usually fully collected, we artificially remove some attributes at random. To thoroughly and quantitatively evaluate our representation capacity,

---

Under review as a conference paper at ICLR 2021
conducte experiments three common node classification benchmarks: Cora, Citeseer and PubMed in two settings:
a. Partially Missing Partially missing means some entities of the feature matrix are missing. Precisely, we randomly remove the values of an attribute matrix in a given proportion (from 10% to 90%).
b. Entirely Missing Entirely missing means some nodes have complete attributes while the others have feature at all. In this case, we remove some rows of the feature matrix in a given proportion (from 10% to 90%) al random.
We apply various traditional imputation approaches including zero-impute, mean-impute, soft-impute (Mazumder et al.) 2010), and KNNNimmpte (Batista et al. (0022) to complete the missing values and use a two-layer GCN to classify nodes based on imputed feature matrices. We call them ZERO-GON, MEAN-GCN, SOFT-GCN and KNN-GCN respoctively. Here, zero-impute and mean-impute means that we replace missing values with zero value or the mean of observed features respectively. Moreover, we set the performance of GCN only leveraging graph structure, i.e. with identity matrix as feature mairix, as a lower bound, named GCN_NOFEAT Moreover, in this situation we use Label Propagation (LP) Algorithm as a better low-bound. If the performance of a model is below the low-bounds, reflects that the model is unable to utilize incomplete attributes effectively.
In all the benchmark and experimental settings, we fix most of the hyperparameters of WGD- MLP: 7 WGD layers including twice Barycenter_ -pdate on each layer, two-layer MLP with 128 hidden units with 0.5 dropout. We apply rank 64 SVD on the incomplete attribute matrix in which we replace the missing values with the mean value of observed features. The settings of GCN used in all baselines and SVD-GCN are the same, i.e. 2 layers with 32 hidden units. For all models, we Adam optimizer with 0.01 learning rate and weight decay depending on different missing cases. We early stop the model training process with patience 100, select the best performing models based on validation set accuracy, and report the mean accuracy for 10 runs as the final results. For more experimental details please refer to our codes: https: https:///nonymous.o 4open. -
Experimental Results As shown in Fig 2
WGD-MLP outperforms all basclines and
nofent
zero_gen
mean_gon
knn_gcn
goft
svd_gon
wgd_m/p
Cora
Clesser
Pubmed
0.80
0.70
0.80
0.70
0.60
0.70
0.00
0.50
0.60
0.40
0.30
0.50
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
munnay nale
mizain
gen, nofeat
LP
zero_gon
nen
knn_gon
soft
svd_gon
wgd_mmp
Cora
Giesser
Pubmed
0.80
0.70
0.80
0.70
0.60
0.70
0.50
0.60
0.50
0.40
0.50
0.30
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.5
0.8
miooni hale
antraing rate
Figure 2: Average accuracy of models in entirely missing (top) and partially missing (bottom) settings.
achieves significant improvement, especially when the missing rate is over 50%. There is clear trend of decreasing of baselines in two types of missing attributes. In contrast, the flat curve of WGD-MLP reflects our remarkable robustness. On Cora and Citeseer, comparison of the lower bound provided by GCN NOFEAT with baselines confirms that imputation strategies are ineffective and even counterproductive when observed attributes are grossly
7

---

Under review as a conference paper at ICLR 2021
inadequate. By contrast, WGD always shows continuously satisfactory performance, even when 90% of attributes are unavailable. For instance, both two types of missing data, the performance of WGD consistently falls by only 10% and 5%, respectively, Pubmed datasets. It illustrates that WGD can significantly reduce informative distortion caused by missing data and learn effective latent. node representations. On the other hand, the inferior performance of SVD-GCN convincingly demonstrates the efficiency of Wasserstein diffusion. For WE-MLP, we conduct experiments on Cora and Pubmed with a fixed missing rate (0.1). Here is the results: Cora: 0.453 (entirely missing), 0.439 (partially missing); Pubmed: 0.575 (entirely missing), 0.537 (partially missing). It implics a clear benefit of matrix decomposition in the first step of WGD.
Cora and
Sensitive Analysis To show how the number of WGD layers and iterations of Wasser- stein diffuuson in each layer influence our performance of node classification, we take Cora as an example and present the results in Fig As we know, many GNN models encounter the over-smoothing issue when they go deep; however, Figure shows shows contrary results and demonstrates that our method can efficiently handle over-smoothing. This is due to two strategies: self-connection (similar to the strategy in APPNPKlippera et al. 2019a and orthogonalization which make nodes different.
Partial missing
Whole missing
Analysis
0.70
0.70
0.70
Accuracy
0.80
hw1
0.60
h-1
whole
0.50
hm3
0.50
hm3
0.50
whole, Lm2
partial,
0.40
h=5
0.40
h=5
0.40
partial, L=2
Figure 3: Sensitive analysis for the number of WGD layers and times h of Wasserstein diffusion in each layer. The results (node classification accuracy on Cora dataset) show that our mothod prevents over-smoothing.
4.2 MULTI-GRAPH MATRIX COMPLETION
An interesting aspect of the WGD framework is that they allow us to reconstruct feature matrix with the introduction of reconstruction constrains and neural networks. In this section, we test the ability of WGD to reconstruct missing values of mulli-graph matrix, or more precisely, of recommendation systems with additional information including the similarity of users and items represented as the users graph and the items graph, respectively. Algorithm B summarizes the WGD framework adapted for matrix complction tasks.
Assume that X is the incomplete feature matrix of the users graph, then X is that of the items graph. Leveraging k-rank SVD, we have Un, Av. V22 = SVD(X, k). Through the space transformation (2) we obtain @(U)), the discrete distributions of users with supp(U>)= = (Vx). In the same way, we have Vú, As, Us = SVD(X k)) and o(V)) with supp(Vs) Vi)) (U,). Typically, the update of node distributions on one graph will lead to unexpected changes in the support points of the other graph. However, this does not appear to be the case in WGD, as the predefined distance matrix (3) only depends on the fixed Ag. Therefore, supp(Uk) and supp(V)) share common distance matrix. It implics that, two Wasserstein diffusion processes formulatd by (5). can simultaneously go on. Informally, this generalized WGD framework, called the multi-graph WGD, can be thought of overlay of two original WGDs. The difference appears in the last step: in the multi multi-graph WGD, we concatenate the outputs of each layer, feed them to simple MLP and normalize columns of the learned Ug and V& to be unit vectors.
Benchmarks. We conduct experiments two popular matrix completion datascts with multi-graph: Flixster and MovieLens--1000 processod by Monti et al. (017).
Baselines. We compare our multi-graph WGD framework with some advanced matrix completion methods, including GRALS (Rao et al.) 2015). sRMGCNN (Monti et al.) 2017), GC-MC (Berg et al. 2017), F-EAE (Hartford et al. 2018), and IGMC (Zhang

---

Under review as a conference paper at ICLR 2021
Algorithm 3 mulli-graph WGD adapted for matrix completion
input: attribute matrix Xaxm containing initial values,
1: Apply k-rank SVD to X: Un, Ag, V = SVD(X,k)
2: U/ Uk. v(0) V&
3: for 1 do
((--1) Normalizo(exp(row (1)
4: space transormation:
V (1111) Normalize(exp(row Vi
5: space transormation:
U - ((-1) ((0)
+ VR (1-1)
6:
7:
for 1 h do
Wasserstein diffusion: Ú(
Barycenter_Updatell (((-1) D)
8:
V((i) Barycenter Update V (1)) D)
Wasserstein diffuusion: 10: end for
9:
inverse transformation: U( SrannSShmiid..OOrtlccllo(o""'""
12: inverse transformation: ((()) Gram Schmidt Ortho(col(log() ()(
13: end for
14: UR commatt _..,R()), Vr (V: v(())
15: Reconstruct Uk: Up = L2 Mor
16: Reconstruct Vg:: Vi = L2 (MPP
return X V
Table 1: RMSE test results on Flixster and MovieLens-10000
GRALS
sRMGCNN
GC-MC
F-EAE
IGMC
WGD-MLP
FLIXSTER
1.313
1.179
0.941
0.908
0.872
0.883
ML-100K 0.945
0.929
0,910
0.920
0.905
0.910
GRALS is graph regularization method and sRMGCNN is factorized matrix model. GC-MC directly applies GCN for link prediction on the user-item bipartite graph. F-EAE and IGMC are inductive matrix completion methods without using side information. The former leverages exchangable matrix layers while the latter focus on local subgraphs around each rating and trains GNN to map the subgraphs to ratings.
& Chen 2020
Experimental Settings and Results. We follow the experimental setup of Monti et al. (2017) and take the common metric Root Mean Square Error (RMSE) to evaluate the accuracy of matrix completion. We set rank= 10 as the same as sRMGCNN for Flixster and 1000 In addition,
use 4-layer MLP with 160 hidden units in all experiments.
We set L 5, h= = in Flixster and L = 7, h = in MovieLens-100k We train the model using Adam optimizer with 0.001 learning rate. Table [ presents the experimental results. As we can see, our WGD-MLP model outperforms most methods and achieves comparable performance as the state of art model IGMC, However, the parameter numbers in our model is much less than the GNN based model IGMC.
5 CONCLUSTON
Graphs with missing node attributes are ubiquitous in the real-world, while most node representation learning approaches have limited ability to capture such incomplete informa- tion. To mitigate this problem, we introduced matrix decomposition and Wasserstein graph diffusion for representation learning such that observed node features can be transformed into discrete distributions and diffused along the graph. We developed a general framework that can produce high-quality node representations with powerful ability to represent at- tribute and structure information and adapted the framework for two applications: node classification and matrix completion. Extensive experiments on node classification under two missing settings verified the powerful representation capacity and superior robustness our framework. Our model also proves effective to recover missing features in matrix completion.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Gustavo EAPA Batista, Maria Carolina Monard, et al. A study of k-nearest neighbour as an imputation method. His, 87(251-260):48, 2002.
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Iterative bregman projections for regularized transportation problems. pp- A1111-A1138, 2015.
Rianne den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. Computing Research Repository, 2017.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. International Conference on Learning Representations, 2018.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally connected networks graphs. In International Conference Learning Representations (ICLR2014), CBLS, April 2014, pp. http openreview, 2014.
Leandro Duarte, Jacqueline Souza Lima, Renan Maestri, Vanderlei Debastiani, and Rosane Garcia Collevatti. Genvectors: An integrative analytical tool for spatial genetics. pp. 330761, 2019.
Charlie Frogner, Farzanch Mirzazadeh, and Justin Solomon. Learning embeddings into entropic wasserstein spaces. International Conference on Learning Representations, 2019.
Hongchang Gao and Heng Huang, Deep attributed network embedding. In International Joint Conferences on Artificial Intelligence, pp. 3364-3370, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Vaannnng-Volume
Conference on Machine Learning- Volume 70, pp. 1263 1272, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Jason Hartford, Devon R Graham, Kevin Leylon-Brown, and Siamak Ravanbakhsh. Deep models of interactions across sets. International Conference on Machine Learning, 2018.
Trevor Hastie, Rahul Mazumder, Jason D Lee, and Reza Zadeh, Matrix completion and low-rank svd via fast. alternating least. squares. pp. 3367 0407, 2015.
Richang Hong. Yuan He, Le Wu, Yong Ge, and Xindong Wu. Deep attributed network embedding by preserving structure and attribute information. IEEE Transactions on Systems, Mon, and Cybernelics: Systems, 2019.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnerannn. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019a.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems, pp. 15354-13360 2019b.
Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. The Journal of Machine Learning Research, 11: 2010.
10

---

Under review as a conference paper at ICLR 2021
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. In Advances in Neural Information Processing Systems, pp. 3697-3707, 2017.
Boris Muzellec and Marco Cuturi. Generalizing point embeddings using the wasserstein space of elliptical distributions. In Advances in Neural Information Processing Systems, pp. 10237-10248, 2018.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deopwalk: Online learning of social representations. 2014.
Tiago Pimentel, Adriano Veloso, and Nivio Ziviani. Unsupervised and scalable algorithm for learning node representations. International Conference on Learning Representations, 2017.
Nikhil Rao, Hsiang-Fi Fu Yu, Pradeep K Ravikumar, and Inderjit S Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In Advances in Neural Information Processing Systems, pp. 2107-2115, 2015.
Olga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat. Brown, Trevor Hastie, Robert Tibshirani, David Botstein, and Russ B Altman. Missing value estimation methods for dna microarrays. pp. 520-50 520, 2001.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. Compuling Research Repository, 2017.
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang. Network representation learning with rich text information. In International Joint Conferences on Arlificial Intelligence, pp. 2111 2117, 2015.
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. International Conference Leorning Representations, 2020.
11


Reviews:
[{"review_id": "vVS9WlqvSeG", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a Wasserstein diffusion based method for estimating missing node labels on attributed graphs. The algorithms use linear algebraic decompositions to represent the node labels in a low dimensional space and then uses a Wasserstien Barycenter approach to implement the diffusion before lifting back to the original feature space. None of these components is novel in this setting but the combined algorithm is interesting and the provided code is helpful and demonstrates the naturalness and ease of implementation of the proposed model. \n\nThe empirical experiments are beyond sufficient given the space constraints and highlight the flexiblity of this formulation of the problem. The application to multigraph completion is particularly interesting - this is related to several other recent problems of interest around node embeddings and inference around families of graphs on common node sets that would be an interesting extension of this work. \n\nThe typesetting of text in equations should be placed in something like \\operatorname so that it isn't squashed and italicized. Also the final table needs to be reformatted, as it is difficult to parse currently. \n\nTypo second to last paragraph of page 5 low-rand -> low-rank", "extra_scores": {}, "extra_text": {}}, {"review_id": "mDOmHzBHXWR", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work studies the missing data issue in the graph-based learning tasks, including node classification and matrix completion. The idea is to perform dimension reduction of the observed features. Then, allow these features to diffuse over graphs by computing barycenter update to fill in the missing features. The prediction is performed by adding MLP over the obtained features. The paper is written well and easy to follow. However, the idea reads very heuristic with some potentially issues. The experiments read weak. \n\nFirst, regarding originality, this work seems to combine some previously well-studied techniques: Use optimal transport to complete missing data; Graph-based semi-supervised learning. For example, [1] discussed using optimal transport to fill in missing data, which is not referred in this work. [2] studied label propagation over graph via optimal transport, which is also not referred in this work. The idea in this work seems to be a combination of techniques from different previous works. It is okay to combine techniques but one needs to sufficiently demonstrate the effectiveness, which have not been well done in this work. \n\nSecond, it reads weird to use exp() followed by a softmax to obtain a discrete distribution. \"exp\" function is not properly transformed function to keep the feature information. For example, if some components in the features obtained by SVD have a few negative ones and a few large positive components. Of course, both the negative and positive features are important. However, if we adopt the method proposed in the work, the model only tends to capture those large positive components and ignores those negative components (due to the exp function). Later, the authors use l2-distance (a very component-wise well-balanced metric) to define W-distance. This yields a very imbalanced treatment on the features.\n\nThird, the experimental section is not persuasive. It is widely know that GCN does not work very well for node classification tasks. There are many other models, e.g., APPNP [3], performing  good node classification over homorphilic networks. These better baselines should be used. Moverover, for only topological information, GCN without node features is not a strong baseline. Better methods with only graph structures should be traditional methods, such as label propagation. Moveover, to demonstrate the effectiveness of this approach, experiments should also be done over heterophilic networks.                \n\n\n\n[1] Missing Data Imputation using Optimal Transport, Muzellec et al., ICML 2020\n[2] Wasserstein Propagation for Semi-Supervised Learning, Solomon et al., ICML 2014.\n[3] Prediction and propagation, 2020", "extra_scores": {}, "extra_text": {}}, {"review_id": "Oj4Y9wWN1m", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the paper, the authors proposed a framework to learn representation for graphs with node attributes that are allowed to be missed.   The learning process includes two steps: (1) node features transformation using SVD which allows representing a node as a discrete distribution with support points of orthogonal basis vectors. (2) message passing and updating the node distribution using Wasserstein barycenter, i.e. one node representation is the barycenter of its neighbors and itself.  Two downstream tasks were used to demonstrate the performance of the proposed methods:  node classification and multi-graph completion.\n\nOverall, the idea is interesting however the writing of technical ingredients is not convinced enough. There are points not clear and can be improved to get a better version of the paper.\n - For the ground metric in Eq. (3), what is the rationale for choosing as the norm (not sure which norm) of square eigenvalues?\n - The paragraph including Eq. (6) (\"Recall that the set ... notoriously difficult to solve.\") does not contribute any further information as it is not used in the rest of the paper.\n - In Eq. (9), do the inverse map of  X need to be consistent with the observed feature of that node?\n - How to handle SVD with missing nodes? It seems that if the graph is 100% missing features, i.e. the graph with no features, the method does not work as we can not perform the SVD step.\n - Is there any convergence guarantee for the prosed Wasserstein diffusion process in Eq. (7)? If there is no rigorous proof, an intuition justification is the least.\n - Some SOTA baseline methods such as GCNmf [1] or methods therein (e.g. GAIN) (if you think the paper is not peer-reviewed yet) should be compared with.\n\nThere are several typos and mistakes:\n - Page 3, \"matrixV\"=> \"matrix V\"\n - Page 4, \"sqaure root\" => \"square root\"\n - Page 4, \"In practice, We use\" => \"In practice, we use\"\n - Page 6, \"training process with patience 100,\" ?!\n - Table 1, to tight table caption\n\n[1] Taguchi, H., Liu, X., & Murata, T. (2020). Graph Convolutional Networks for Graphs Containing Missing Features. arXiv preprint arXiv:2007.04583.", "extra_scores": {}, "extra_text": {}}, {"review_id": "9xfJFtBWhtA", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary and contributions: Briefly summarize the paper and its contributions:\nThe paper considers node representation learning in the setting of incomplete node attributes. The proposed method transforms node features to a latent space endowed with the Wasserstein metric, uses the Wasserstein barycenter of nodes’ neighbors to recover missing features, and finally transforms them back to their original space using a proposed inverse mapping. The algorithm has been tested on benchmark classification tasks as well as matrix completion tasks.\n\nStrengths: \n+ The paper appears to be a novel application of ideas from both matrix completion and optimal transport. \n+ In the node classification experiments, multiple benchmark datasets were used and multiple methods to complete missing values were considered as baselines. \n\nWeaknesses: \n- While the experiments show promising results, the authors do not explain the choices  behind their method. \n- Why do the authors use SVD and define the distance between transformed features in the way they did? Is there a reason for using the exponential function in the transformation other than for inducing positiveness of probability? How does the inverse mapping come up and why does it work? \n- In the classification task experimental section, it is not clear why methods, like IGMC (used in Section 4,2) paired with an MLP, weren’t tested for the classification tasks. As for the choice of architectures, is there a reason for using 7 WGD layers versus 2 GCN layers for the baselines?\n- Because many choices are not justified or described, a number of questions are left unanswered. What is fundamentally different between a WGD layer and a GCN layer? What is the influence of the number of WGD layers? And what is changing in the representation after each WGD layer? What does the induced latent space look like? How does it relate to the complete feature information setting? Is the dimension of the latent space equal to that of the original space? Why does feature recovery using Wasserstein barycenter update trumps simple average or k-means of neighbors, what makes the metric be more adequate than Euclidean distance? \n- The authors claim that their work “is the ﬁrst work to compute embeddings of a graph with incomplete attributes directly.” but their proposed algorithm is two-stage, first matrix completion and then neural network training. The paper seems to be more relevant to data pre-processing than representation learning itself. \n- The authors conducted experiments in two settings, partially missing and entirely missing. It seems that the performance of the proposed method is exactly the same in both settings. (Figure 1) This is curious. Can the authors comment on what is happening in this case?\n- In multiple instances, the authors introduce experiments but don’t comment on them or explain the similarity or differences in performance between all of these experimental settings.\n\nClarity: \nMany terms are used without properly defining them; the equivalence of p-Wasserstein distance to eq. (4) is unclear unless readers are already familiar with optimal transport; the iterative Bregman projection and Gram-Schmidt process have not been elaborated clearly. The statement “However, most of the methods, which embed nodes into a lower-dimensional Euclidean space, suﬀer from common limitations” is in reference to GCNs which are not limited to low-dimensional spaces. So it’s not clear what the authors meant by this.\n\nRelationship to prior work: \nThe state-of-the-art alternatives have not been well-addressed and compared with. A lot of work has been done with graph convolutional networks and in this literature, the issue of missing attributes is very common. There is no mention of matrix completion methods in related works, these methods were used in Section 4.2, without explaining how they are different from the proposed method, or why this set of methods was selected for comparison.\n\nAdditional feedback:\nMultiple typos are present throughout the paper, these can be addressed to improve the readability, for example:  In section 3.3 “expect” should be “except” in the sentence: Note that it is similar to the message aggregation in graph neural networks, expect we do it in a Wasserstein space and introduce no parameters.\nIn section 4.1 “some entities of the feature matrix is missing” should be “some entities of the feature matrix are missing”. “90% attributes” should be “90% of attributes”. “Pumbed” should be “Pubmed” in “on Cora and Pumbed datasets.”", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The rationality of the proposed method, especially its implementation detail, is challenged by the reviewers. Additionally, the experimental part and the writing of the paper should be improved. According to the feedback of the reviewers, I don't think this work is qualified enough at its current status. 
Decision: Reject