Graph Neural Networks for Soft Semi-Supervised Learning on Hypergraphs
Authors: Naganand Yadati
Tingran Gao
Shahab Asoodeh
Partha Talukdar
Anand Louis
Venue:  (2020)
Keywords: Graph Neural Networks
Soft Semi-supervised Learning
Hypergraphs

Abstract: Graph-based semi-supervised learning (SSL) assigns labels to initially unlabelled vertices in a graph.
Graph neural networks (GNNs), esp. graph convolutional networks (GCNs), inspired the current-state-of-the art models for graph-based SSL problems.
GCNs inherently assume that the labels of interest are numerical or categorical variables.
However, in many real-world applications such as co-authorship networks, recommendation networks, etc., vertex labels can be naturally represented by probability distributions or histograms.
Moreover, real-world network datasets have complex relationships going beyond pairwise associations.
These relationships can be modelled naturally and flexibly by hypergraphs.
In this paper, we explore GNNs for graph-based SSL of histograms.
Motivated by complex relationships (those going beyond pairwise) in real-world networks, we propose a novel method for directed hypergraphs.
Our work builds upon existing works on graph-based SSL of histograms derived from the theory of optimal transportation.
A key contribution of this paper is to establish generalisation error bounds for a one-layer GNN within the framework of algorithmic stability.
We also demonstrate our proposed methods' effectiveness through detailed experimentation on real-world data.
We have made the code available.

Under review as a conference paper at ICLR 2020
GRAPH NEURAL NETWORKS FOR SOFT SEMI- SUPERVISED LEARNING ON HYPERGRAPHS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph-based semi-super learning (SSL) assigns labels to initially unlabelled vertices graph. Graph neural networks (GNNs), esp. graph convolutional networks (GCNs), inspired the current-state-of-tle art models for graph-based SSI. problems. GCNs inherently assume that the labels of interest are numerical categorical variables. However, in many real-world applications such as co- authorship networks, recommendation networks, etc., vertex labels can be natu- rally represented by probability distributions histograms. Moreover, real-world network datasets have complex relationships going beyond pairwise associations. These relationships can be modelled naturally and flexibly by hypergraphs. In this paper, we explore GNNs for graph-based SSL of histograms. Motivated by complex relationships (those going beyond pairwise) in real-world networks, we propose a novel method for directed hypergraphs. Our work builds upon exist- ing works on graph- SSL of histograms derived from the theory of optimal transportation. A key contribution of this paper is to establish generalisation er- ror bounds for a one-layer GNN within the framework of algorithmic stability. We also demonstrate our proposed methods' effectiveness through detailed exper- imentation on real-world data. We have made the code available.
INTRODUCTION
In the last decade, deep learning models have been successfully embraced in many different fields and proved to achieve unprecedented performance on a vast range of applications Krizhevsky et al. ;012);/Goodfell
et al. (2014); Bahdanau al. (2015); LeCun al. (2015). Graph Convolutional Network (GCN) Kipf' & Welling (2017) was recently proposed as an adaptation of a particular deep learning model (i.e., convolutional neural networks Lecun al. (1998) to enable handling graph- sraph-structured data. GCN was shown to be, in particular, effective in semi semi-supervised learning on attributed graphs. GCNs have inspired the current state-of-the art models for graph- SSL Wu et al. (2019a); Veličković et al. (2018); Vashishth et al. (2019). GCNs inherently assume that the labels of interest are numerical or categorical variables.
However, in many real-world applications such co-authorship networks, recommendation net- works, etc., vertex labels can be naturally represented by probability distributions or histograms. Moreover, these real-world network datasets have complex relationships going beyond pairwise sociations. Such relationships can be modelled naturally and flexibly by hypergraphs. Moreover, hypergraphs encode additional relationships with directions as illustrated in Figure and these hypergraphs are directed hypergraphs Gallo et al. (1993..
Inspired by prior work Solomon et al. 2014] that generalised label propagation to graph- based soft SSL setting and motivated by the fact that GNNs have inspired state-of-the-an models for traditional graph-based SSL, we make the following contributions.
We explore GNNs for soft SSL in which vertex labels are probability distributions. Mo- tivated by real-world applications, we propose DHN (Directed Hypergraph Network), a novel method for directed hypergraphs. DHN can be applied for soft-SSL using existing tools from optimal transportation (Section 33)
We provide generalisation error bounds for a lne-layer GNN within the framework of algo- rithmic stability. We establish that such models, which use filters with bounded eigenvalues

---

Under review as a conference paper at ICLR 2020
co-authorship network
recommendation network
h
Figure 1: (Best in colour) Examples of real-world networks modelled directed hypergraphs in which labels on the vertices can be represented by probability distributions. To the left is co- authorship network in which vertices are authors, hyperedges are collaborations (documents), and directions are citations between documents. Research topic interests of authors can be naturally represented by probability distributions (labels are shown for a couple of authors in the figure). To the right is recommendation network in which vertices are products, hyperedges are users and contain all the products bought by them, and directions represent user similarity (two-way). Product ratings can be naturally represented by probability distributions (labels are shown for couple of products the figure). Please see Section for more details.
independent of graph size, satisfy the strong notion of uniform stability and thus is gen- eralisable. particular, the algorithmic stability of one-layer GNN depends on the largest absolute eigenvalue of the graph convolution filter (Section
We demonstrate DHN's effectiveness through detailed experimentation real-world data. In particular, we demonstrate superiority over state-of-the the--rre hypergraph- bassed neural net- works. We provide new empirical benchmarks for soft-SSL on directed hypergraphs and make the code available to foster reproducible research (Section
RELATED WORK
Graph-based deep learning: Geometric deep learning Bronstein et al. (0117) is an umbrella phrase for emerging techniques attempting to generalise (structured) deep neural networks non- Euclidean domains such graphs and manifolds. GCN Kipf & Welling (2017) and their various extensions are the current state-of-the art for graph-based SSL Wu et al. (019aa; Veličković et al. 2018);; Monti et al. (2018); Vashishth al. (2019); Ma et al. (2019); 9); Qu al. (2019) and graph- based unsupervised learning Hamilton et al. 2017a); Veličković et al. (0199 problems. GCNs have also been applied for semi-supervised graph classification
al. (2019).
The reader is referred to a comprehensive literature review Bronstein et al. 2017) ) and extensive surveys Hamilton et al. (2017b); Battaglia al. (2018): (Zhang et al., (2018); Wu al. (019b); (un
eet al. (2018); /hhou et al. (2018) on this topic. Recently, graph-based deep models (also message- passing neural networks Gilmer et al. (2017)) have been analysed theoretically Dehmamy al.
(2019) Ying et al. K el al. (2019); Chen et al. (2019b); Maron et al. (2019) Morris al. (2019) Xu al. (2019b): Chen et al. (2019a); Kawamoto (2018 8): Xu al. (2018); Chen al.
(2018). We note a work on stability and generalisation bounds of GCNs Verma & Zhang (2019).
Learning on hypergraphs: Hypergraph is combinatorial structure consisting of vertices and hyperedges, where each hyperedge allowed to connect any number vertices, thus generalizing graphs. This additional flexibility facilitates the capture of higher order interactions among objects; applications have been found in many fields such as computer vision Govindu (2005). network clustering Demir al. (2008), folksonomies Ghoshal al. (2099) cellular networks Klamt et al.
2009), and community detection Chien et al. (2018).
The seminal work hypergraphs Zhou et al. 2007) introduced the popular Agarwal et al. (2006);
Feng et al. 2018) 2019) clique expansion of hypergraph. Hypergraph neural networks (HGNN)
Feng et al. 2019) the clique expansion while HyperGCN| et al. (2019) uses the mediator-
2

---

Under review as a conference paper at ICLR 2020
based Laplacian to extend GCNs hypergraphs. Another line of work uses the mathematically appealing tensor methods Shashua et al. (2006); Buld & Pelillo (2009); Kolda & Bader (2009) but
they are limited to uniform hypergraphs. Recent developments work for arbitrary hypergraphs and fully exploit the hypergraph structure Hein et al. 2013); Zhang et al. 2017]; Chan & Liang (0018);
Wendler al. (2019). These developments are motivated from the spectral theory of hypergraphs
which is an active area of research Li & Milenkovic (017)); Chien et al. (2019); Chitra & Raphael
(2019 Li & Milenkovie (0018)) Li et al. (2018a); Li & Milenkovic (2018a)
Graph-based soft SSL: Researchers have shown that using unlabelled data during training can improve label prediction significantly Challyllaeplleeeeeeee et al. (2010);Zhu et al. (Sbraamayya & Taluk- dar (2014); Yang et al. (2016). While most methods assume that labels of interest are numerical or categorical variables, other works "soften" this assumption and handle "soft labels" such as his- tograms Corduneanu & Jaakkola (2005); [suuda (2005). One way of propagating histograms is to minimise the Kullback-Ieibler (KI.) divergence Subramanya & Bilmes (2011). Recent studies have replaced the metric-agnostic KL divergence with metric-aware Wasserstein distance (interactions between histogram bins) for graphs Solomon al. (2014) and hypergraphs Gao et al. (2019).
Embeddings in Wasserstein space: There exist at least a couple of recent works that embed Gaussian distributions in the Wasserstein space Muzellec & Cuturi (2018); Zhu et al. 2018 8). In- spired by a recent work Frogner et al. (2019). in this work, we focus on embedding input data as a discrete probability distrirbution require the solution a linear program Villani (2008) and are costly to compute Peyré & Cuturi (2019). A popular efficient approximation is the Sinkhorn divergence Cuturi (20T3) in which the underlying problem is regularised and is computed efficiently by a fixed-point iteration. Recent works have shown that it is suitable for gradient-based optimisation through automatic differentia- tion Frogner et al. (2015); Genevay et al. (2018); Frogner et al. (2019). A couple of recent works compute Wasserstein distance between graph pairs Xu al. (201 Vayer al. (2019).
fixed support set. The Wasserstein distance and its gradient
3 METHOD
In this section, we first describe soft SSL directed hypergraphs and then propose DHN (Directed Hypergraph Network) for the problem.
3.1 DIRECTED HYPERGRAPH A directed hypergraph Gallo al. 1993) an ordered pair H (V, Ea) where V {V1, (. vn is a set of n vertices and
Ea {(1,, hn), (Im, hm)) S 2 x 2
is a set of m directed hyperedges. Fach element in Eg is an ordered pair (t, h) where /. C V is the tail and h C V the head with of 0, + 0. Denote the set of all undirected hyperedges by
U (LUR).
E
(t.b)eFa
Denote E (0,1)) 1 be the incidence matrix of E i.e. I(v,e) 1 if o E e and otherwise.
3.2 SOFT SSL ON DIRECTED HYPERGRAPHS
We consider the problem of predicting probability distributions for the vertices in H = (V, Fa) given typically small subset V V of vertices with known distributions. In this work, we concerned with discrete distributions modelled on a metric space i.c. an ordered pair (M, C) in which M is a set and C is the cost function (metric) associated with the set. Furthermore, we assume that we are provided with a feature matrix, Xy E R Dv in which each vertex v E V is represented by -immensional feature vector x, (here = (V). We are also provided with hyperedge feature matrix X R DE with Ir, E E as D F dimensional feature representations (here m |Ea)).
Our objective is to learn a labelling function Z = (H,, Xy, that maps each vertex to proba- bility distribution in the space of discrete probability distributions (MM on F atoms (F is number of histogram bins) defined on the metric space (M, C). The cost function C' can be represented by a neg-nvgative symmetric matrix of size F x F. Note that each row Z E [0, 10 maps each vertex v E V probability distribution Z, E [0, 1].
3

---

Under review as a conference paper at ICLR 2020
The function h is going be trained on supervised loss, L ,wi.t to the vertices in Vi that the trained h can be used to predict distributions of all the vertices in \ Vg. We now give an example application and then the details of the labelling function h followed by the supervised loss L.
Example application: Predicting topic distributions of authors in co-authorship networks can be posed as a soft SSL problem on directed hypergraphs. V represents the set of authors, E' the set of all collaborations (documents), Eg the citation relationships among the documents, F the number of possible research interests of authors (Machine Learning, Theoretical Computer Science, etc.), Xy and X g any available features the authors and documents respectively (e.g. text attributes).
3.3 DHN (DIRECTED HYPERGRAPH NETWORK)
Hypergraphs contain hyperedges in which relationships can go beyond pairwise and hence chal- lenging to deal with. A flexible way to embed vertices of a hypergraph to "approximate" the hypergraph by suitable graph and then apply traditional graph-based methods on the vertices. Two notable candidates of are Hypergraph neural network (HGNN) Feng et al. (2019) and Hypergraph Convolutional Network (HyperGCN) Yadati et al. (2019). HGNN uses the clique expansion of the hypergraph Zhou et al.] (2007) while HyperGCN uses the mediator-bass (2018) to approximate the input hypergraph. However, they are restricted to undirected hyperedges and also cannot exploit the hyperedge feature matrix Xe.
Laplacian Chan & Liang
key idea of our approach to treat each hyperedge e E as a vertex of the graph G = (E, Ea). We then pass G through graph neural network to obtain HE = SGxx(G, XF) so that the initial features, E, are refined to HE. We then propose the layer-wise propagation rule of DHN N as:
H H++1) = -0(1 I - (.8..000)) t= t=
where [..]] denotes concatenation, is the time step. I is the incidence matrix, ((+1) σ [TT HT(()) for 1. I.... T 1, H SaNN Xx), and or non-linear activation (0) Xv. Note that the labelling function functions, and is the total number of time steps with 1 Z XvH,,v, Xx) = softmax (1T) where softmax is applied row-wise.
3.4 THE SUPERVISED LOSS L A crucial observation here is that because of the softmax layer, the output of h is (already) inherently a probability distribution. For each vertex v E Vv. the predicted distribution Z, and the (known) true distribution Y. must be "close" to each other. A natural way compare probability distributions is to use the KL-divergence between Y, and Z However, KL-divergence cannot exploit the metric space (M, C) and suffers from stability issues Chen al. (2016). In this work, use the more stable Wasserstein distance to exploit the metric space [ao et al. (2019).
/ C(a,, ( de(d) inf (Ell(Pa)) MXM
L Σ VEV.
Wp LZ.
where Wp(mn)= =
For discrete distributions, Wp is the solution of linear program. For practical purposes, we compute the regularised distance using the Sinkhorn algorithm. Please see Appendix A. for more details.
Optimisation: We call DHN optimised with the Wasserstein loss as Soft-DHN. All parameters are learned using stochastic gradient descent (SGD). Please see Appendix for time complexity.
THEORETICAL ANALYSIS: GENERALISATION ERROR BOUND
In this section, we establish generalisation error bounds for a one-layer GNN by extending the results of traditional GCN Verma & Zhang 2019) to the soft SSL setting with Wasserstein loss. The main novelty is to generalise the error bounds to the learning problem "valued in the Wasserstein space". The main challenge is that the Wasserstein space
abstract metric space without linear structure.
The section is organised as follows. We first introduce all the notations needed (ego-graph view, semi-supervised learning setting, etc.). We then give single layer and SGD bounds using the nota-
4

---

Under review as a conference paper at ICLR 2020
tions. We finally give the main result (Theorem 1) which states that GNN trained with Wasserstein loss has the same generalisation error bound as the traditional GCN (trained with cross entropy).
Let G (V, B) be connected graph with [V| vertices. We consider GNN of single layer
f (x,,)) (KX@)
where X Ruxd is the feature matrix (n is the number of vertices in graph, df is the dimension of the feature vectors), K = (Lc) is graph filter (typically symmetrically normalised adjacency with self loops, and LG E IRax the graph Laplacian), and é Rd* the set of parameters. We note that our proposed DHN falls under this formulation in special circumstances. Specifically if the non-linearity 0 in Equation is removed we get the kernel K II (also known as the clique expansion of the hypergraph Zhou et al. (2007).) The non non-linearity in Equation is the softmax function acting on each row of the product g (La) XO E RaxF, the output of dimension n x F, where each output row is discrete probability distribution, i.e.,
((X,0) 9) 2 and f (X, = 1n
where 1, (1, (I, 1) RF, and similarly for 1,, Without loss of generality, we assume d = 1. Note that in order for the output to be nontrivial probability distributions, we must assume > 1.
We adopt ego-graph view (Verma & ZZhang 2019 formula (2)) simplify our discussion for local behavior of the soft GCN at particular vertex. Whenever no confusion arises, we identify a vertices æ and X in the graph G with their respective D-ddmmensioal feature vectors. Thus the output of f at x E V is
Kax =o = (xN(x)
((I
Kxxx + .) (XEA(=)
(x, a
Σ
.)
where N (x) denotes for the one-hop neighborhood of x with respect to the adjacency relation defined by matrix K, and Kax E IR stands for the entry in K E IRnx= that describes the adjacency relation between vertices x and X. Let E, := ExEN(() KaxX E R so that f (x. θ) a (Eg θ).
We consider the supervised learning setting, and learn GNN from the training set {2; = (x;,
31), i -....... m} sampled i.i.d. from the product space V x Pp with respect to prob- ability distribution on this product space, where Pp is the space discrete probability distribu- tions on F atoms. The output of softmax lies in Pr, which is convex cone. For any new data z (x, v) ~ D, we evaluate the performance GNN f using Wasserstein cost
É Ef (s, ,) = (f (,, θ) (I. y)) = W (f (z, .),
Here the Wasserstein cost is defined with respect to a cost function penalizing moving masses across bins. Since we are working only with histograms in GNN, we shall use a cost function C e RFx that is defined for pairs of histogram bins. The transport problem is linear program with = (x, θ) as in Equation 10 Please see Appendix Sections A.3.1 and A.3.3 for the assumptions made and the notations used for Algorithmic stability. We now derive single layer and SGD bounds.
4.0.1 SINGLE LAYER BOUND
By the triangle inequality,
| (f (x, .)) Wi (f (z. Os:), ,w)1 S Wi (f (z, S )s: Theorem 6.13), recall that the diameter of the support is D, we have
By Villani 2008
W1 (f (x, Os) f (z, Os:)) < D IIf (z, Os) (z, Isy where ||- is the total variation distance, which by definition
1
1 Σ IIs (z. 0s)); [ (z, Os ),11 = ||o (Ez Os) - (F Os:)
II (z, Os) (x. Os 1v
2 1=1
where ||-||, the _ distance on FR Since the softmax function is Lipschitz continuous, we have
< La Ex ||0s Os
[1, (z, 0s) - (z, Os I
2
5

---

Under review as a conference paper at ICLR 2020
and thus
/tg.://eeeaaaaaaaoooooooooooooaa - 0 (4)
where we used notation gx supxev |Ea as defined in Verma & Zhang (2019), which is known to be upper bounded by G the spectrum of the graph Laplacian LG with largest absolute value.
4.0.2 SGD BOUND
now remains to bound E ||0s- - - resulting from the SGD iterations. The main technical challenge, as noted before, is to generalise the results the Wasserstein space which is an abstract metric space without linear structure. Specifically, we have to modify the "gradient" in the Wasser- stein space the straightforward version Verma & Zhang (2019) does not satisfy the Lipschitz condition required the algorithmic stability framework. To the best our knowledge this mod- ification is not seen in existing literature and be thought of generalisation of the "gradient clipping" operation Hardt et al. (2016). The entire proof is in the Appendix A.3.4 We state the main result here.
2nFgx D
T
3
EA [1OS.T
1
D
(5)
2
Combining equation and equation 23 gives us
FF D
3
(-1
|EA [W1 (f (z, Os), v) Wi (f(z
DnDLooR
(6)
m
Therefore, we actually have the uniform algorithmic stability equation
14
holds with
LE D2
[1+
Σ
T
Bm
2m
Note that here Bn = ) (needed to obtain a tight generalisation bound).
4.1 PUTTING EVERYTHING TOGETHER
Lemma Veerma Zhang 2019 Lemma 4): Let X be the maximum absolute eigenvalue of Le. Let G2 be the ego-graph of vertex x E V with corresponding maximum absolute eigenvalue maz Then the following eigenvalue (singular value) bound holds Vx E VV,
Xmax
Xmax
(8)
Theorem 2) A uniform stable randomised algorithm (As, Bm) with bounded loss function < ((s,y)) S B, satisfies the following generalisation bound with probability at least
Lemma Verma Zhang 2019
5, over the random draw of S.y with E 10,
log 1
EA R(As) Remp (As) < 28, + (4mBm + BYy
2m
where R(As) is the generalisation error/risk and Ramp(As) is the empirical error. Please Ap- pendix A.3.2 for definitions. Finally, by Equation 8 and Equation 9 our result i.e. Equation immediately gives the following theorem:
Theorem Let As be a one-layer GNN algorithu (of equipped with the graph convolutional dataset S for T iterations. Let the loss and activation functions
filter g(Ta) and trained be Lipschitz-contimuuus and smooth. Then the following expected generalisation gap holds with probability least 8. 10.
m ( + (o (1 + BBB +B)
log ! 2m
EsGD [(AAs) Remp (As) <
where the expectation ESGD is taken over the randomness inherent in SGD, m is the no. training samples, and B is constant which depends on the loss function. Our theorem states that GNN trained withe Wasserstein loss enjoys the same generalisation enror bound of the traditional GCN (trained with cross entropy). We discuss experiments.

---

The cost matrix C is an F F matrix (F is the number of histogram bins) with ones the diagonal and a hyperparameter v elsewhere. We could have used a matrix of all yss. But it is no different from matrix of all ones from the optimisation perspective and we used the above more general Under review as a conference paper at ICLR 2020
5 EXPERIMENTS
Table 1: Statistics of datasets used in the experiments. Please Section for the notations used.
Dataset
Type
[
E
Ea
F
Avg. edge size
Max. edge size
Cora
Co-authorship
2653
2591
12071
7
2.3 + 1.9
29
DBLP
Co-authorship
22535
43413
117215
4.7
143
Amazon
Recommendation
84893
166994
1081994
3.0
187
ACM
Co-authorship
67057
25511
59884
6
2.4
32
arXiv
Co-authorship
790790
1354752
6728683
7
4.0 +: 19.7
2832
To demonstrate the effectiveness of our proposed DHN, we conducted experiments on real-world directed hypergraphs. Four of them are Co-authorship datasets and one of them is recommendation dataset. Table [ shows the statistics of the datasets. For more details on the construction of the datasets, please see Appendix A.6
5.1 EXPERIMENTAL SETUP
Inspired by the experimental setups of prior related works Wiif Welling (2017); Liao (2019). we tune hyperparameters using the Cora citation network dataset alone and use the optimal hyper- parameters for all the other datasets. hyperparameterise the cost matrix (base metric of the Wasserstein distance) follows:
7
...
"
1
7
C
matrix. Details of hyperparameter tuning and optimal hyperparameters are in Appendix A.5
5.2 BASELINES
We used both Wasserstein distance and KL divergence to train different models. As already noted, we used the Sinkhorn algorithm to compute the (regularised) Wasserstein distance. Please see Ap- pendix A. for more details. We compared DHN with the following baselines:
KL-MLP: We used simple multi-layer perceptron (MLP) the features of the vertices and trained it using KL-divergence
OT-MLP: We trained another MLP with the Wasserstein distance as the loss function. Note
that this baseline and the previous baseline do not use the structure (graph hypergraph)
KLR-MLP: We regularised an MLP with explicit KL--divergence-basee regularisation that uses the structure (graph hypergraph) Subramanya & Bilmes (201).
OTR-ML.P We regularised MI.P with explicit
regularisa-
tion that uses the structure (graph/ / hypergraph) Sooomoon et al. (2014). For hypergraphs we used the clique expansion of the hypergraph Gao et al. (2019).
KL-HGNN KL.-ypeeGCCN: We trained the different GCN-based methods on hyper- graphs with KL divergence loss function on the labelled vertices.
Soft-HGNN Soft-HyperGCN: We trained the different GCN-based methods hyper- graphs with the Wasserstein distance as the loss function.
Metric for comparison: We use the mean squared error (MSE) between true and predicted distri- butions the test of vertices. Table shows MSEs the test split for all the three datasets.

---

Under review as a conference paper at ICLR 2020
Results real-world directed hypergraphs. We report 100x squared errors (lower is better) over 10 different train-test splits. Note that all the reported numbers need to be multiplied by 0.01 get the actual numbers. Please see section for more details.
Table 2:
Method
Cora
DBLP
ACM
Amazon Office Products
arXiv
KL-MLP
8.94 0.16
7.72 + 0.14
8.47 + 0.15
6.81 + 0.16 6.78 0.24
10.87 + 0.25
OT-MLP
7.45 0.35
7.53 + 0.18
7.85 0.26
10.01 + 0.23
KLR-MLP OTR-MLP
8.05 = 0.22
7.35 0.18
7.82 + 0.29
6.74 + 0.15
6.57 0.43
7.24 + 0.18
6.77 0.32
6.72 0.23
KL-HGNN
0.12
7.23 +
6.71 + 0.19
9.95 0.25
KL-HyperGGCN
7.95 0.27
7.15 0.17
7.53 1 0.21
6.69 4 0.17
9.99 1 0.23
Soft-HGNN
5.97 0.37
6.18 + 0.37
6.02
0.37
6.63 0.39
0.49
Soft-HyeeGGNN
6.02 + 0.32
6.21 + 0.35
6.04 + 0.32
6.61 + 0.30
8.60 + 0.47
KL-DHN (ours)
7.04 + 0.24
6.97 + 0.22
7.16 0.24
6.65 0.17
9.34 + 0.32
Soft-DHN (ours)
4.87 + 0.40
5.65 + 0.42
5.12 + 0.34
6.55 0.33
7.69 + 0.36
5.3 DISCUSSION
We used simple one-layer architecture for our proposed DHN and 2-hop simplified GCN Wu al. (219a) the GNN model on the graph G (F,, F.d) i.e.
Z softmar(I HE O1), HE A
where A is the symmetically normalised adjacency (with self loops) of the graph G. We demonstrate that this simple model is effective enough through an ablation study in Appendix Table Our results demonstrate strong performances across all the datasets esp. the co-authorships networks.
Specifically, we observe that Soft models (that use the Wasserstein loss) are almost always superior to their counterparts that use the KL divergence the loss function. This is because the Soft models can exploit the distance matrix C' while KL-divergence does not.
Moreover, proposed DHN outperforms two strong hypergraph baselines viz. HGNN Feng et al. (2019) and HyperGCN Yadati et al. (2019). We believe this is because they do not exploit the rich structural information in the directed hyperedges (connections among hyperedges) while proposed DHN does exploit them.
We also experimented standard graph benchmark node-classification datasets such as Cora, Cite- seer, and Pubmed by treating the class label as one-hot probability distribution. We used the Soft variants of GCN Kipf Welling (0017). Simple GCN Wu al. (2019a), and GAT GAT Veličkolé al. 20018). We achieved competitive results as shown in Appendix Table
6 CONCLUSION
We have proposed DHN, novel method for soft SSL on directed hypergraphs. DHN can effectively propagate histograms to unknown vertices by integrating vertex features, directed hyperedges and undirected hypergraph structure. As a key contribution, for DHN within the framework of algorithmic stability. We have also demonstrated DHN's effec- tiveness through detailed experimentation real-worke hypergraph datasets.
have established generalisation bounds
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Sameer Agarwal, Kristin Branson, and Serge Belongie. Higher order learning with graphs. In ICML, 2006. P
Jason Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. In NIPS. Curran Associates, Inc., 2017.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In (ICLR, 2015.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez, Vinícius Flo- res Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pas- canu. Relational inductive biases, deep learning, and graph networks. CoRR, 2018. B
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geo- metric deep learning: Going beyond euclidean data. IEEE Signal Process., 34(4):18-45 2017.
Samuel R. Bulò and Marcello Pelillo. A game-theoretic approach to hypergraph clustering, In NIPS. Curran Associates, Inc., 2009.
T.-H. Hubert Chan and Zhibin Liang. Generalizing the hypergraph laplacian via a diffusion process with mediators. In COCOON, 2018. -
Olivier Chapelle. Bernhard Scholkopf, and Alexander Zien. Semi-Supervised Learning. The MIT Press, 2010.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In ICML, 2018.
Yukun Chen, Jianbo Ye, and Jia Li. distance for hmms based on aggregated wasserstein metric and state registration. In ECCV, pp. 451-466, 2016. g
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks. In ICLR, 2019a. E
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In NeurIPS. Curran Associates, Inc., 2019b.
I Chien, Chung- Yi Lin, and I-Hsiang Wang. Community detection in hypergraphs: Optimal statisti- cal limit and efficient algorithms. In AISTATS, 2018.
I (Eli) Chien, Huozhi Zhou, and Pan Li. hs?: Active learning over hypergraphs with pointwise and pairwise queries. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2466-24622 2475,2245,220 2019. E
Uthsav Chitra and Benjamin J Raphael. Random walks on hypergraphs with edge-dependent vertex weights. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019. !
Colin B. Clement, Matthew Bierbaum, Kevin P. O'Keeffe, and Alexander A. Alemi. On the use of arxiv as a dataset. CoRR, abs/1905.00075, 2019. 20
Adrian Corduneanu and Tommi S. Jaakkola. Distributed information regularization on graphs. In NIPS, pp. 297-304. MIT Press, 2005.
Marco Cuturi. Sinkhom distances: Lightspeed computation of optimal transport. In NIPS. Curran Associates, Inc., 2013. and

---

Under review as a conference paper at ICLR 2020
Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks learning graph topology. In NeurIPS. Curran Associates, Inc., 2019. B
Engin Demir, Cevdet Aykanat, and Berkant Cambazoglu. Clustering spatial networks for aggregate
query processing: hypergraph approach. Information Systems, 2008. B
Fuli Feng, Xiangnan He, Yiqun Liu, Liqiang Nie, and Tat-Seng Chua. Learning partial-order
hypergraphs. In wwW, 2018.
2
Yifan Feng, Haoxuan You, Zizhao Zhang. Rongrong Ji, and Yue Gao. Hypergraph neural networks. In AAAI, 2019. m
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learn- ing with a wasserstein loss. In NIPS. pp. 2053-2003000 Curran Associates, Inc., 2015.
Charlie Frogner, Farzaneh Mirzazadeh, and Justin Solomon. Learning entropic wasserstein embed- dings. In ICLR, 2019.
Giorgio Gallo, Giustino Longo, Stefano Pallottino, and Sang Nguyen. Directed hypergraphs and applications. Discrete Appl. Math., 1993.
Tingran Gao, Shahab Asoodeh, Yi Huang, and James Evans. Wasserstein soft label propagation on hypergraphs: Algorithm and generalization error bounds. In AAAI, 2019. and
Aude Genevay, Gabriel Peyre, and Marco Cuturi. Learning generative models with sinkhorn diver- gences. In AISTATS, 2018.
Gourab Ghoshal, Vinko Zlatić, Guido Caldarelli, and M. E, J. Newman. Random hypergraphs and their applications. Phys. Rev. E, 2009. B
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, Curran Associates, Inc., 2014.
V. M. Govindu. A tensor decomposition for geometric grouping and segmentation. In CVPR, 2005.
H
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.
In NIPS. Curran Associates, Inc., 2017a. !
William L. Hamilton, Rex Ying, and Jure Leskovee. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52-74, 2017b. P
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In ICMI., 2016. Band
Ruining He and Julian McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In www, 2016.
Matthias Hein, Simon Setzer, Leonardo Jost, and Syama Sundar Rangapuram. The total variation on hypergraphs learning on hypergraphs revisited. In NIPS. Curran Associates, Inc., 2013, B
Tatsuro Kawamoto. Mean-field theory of graph neural networks in graph partitioning. In NIPS. Curran Associates, Inc., 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. Hypergraphs and cellular networks. PLOS Com- putational Biology, 2009.
10

---

Under review as a conference paper at ICLR 2020
Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention and general- ization in graph neural networks. In NewrIPS. Curran Associates, Inc., 2019.
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. SIAM Rev. 51(3): 455-500, 2009. F
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In NIPS. Curran Associates, Inc., 2012. D
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. Proceedings of the IEEE, 1998. 0
Yann LeCun, Yoshua Bengio, and Geoffey Hinton. Deep learning. Nature, pp. 436-444, 2015.
Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wenbing Huang, and Junzhou Huang. Semi-supervised graph classification: A hierarchical graph perspective. In WWW, 2019. E
Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. In Ad- vances Neural Information Processing Systems (NIPS) 30, pp. 2308-2318. Curran Associates,
Inc., 2017.
Pan Li and Olgica Milenkovic.
Revisiting decomposable submodular function minimization with incidence relations. Advances Neural Information Processing Systems (NeurIPS) 31, pp. 2237-2247. Curran Associates, Inc., 20.
Pan Li and Olgica Milenkovic. Submodular hypergraphs: p-laplacians, Cheeger inequalities and spectral clustering. Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 3014-3023, 2018b.
Pan Li, Niao He, and Olgica Milenkovic. Quadratic decomposable submodular function minimiza- tion. In Advances in Neural Information Processing Systems (NeurIPS) 31, pp. 1054-1064. Cur- Associates, Inc., 2018a.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the T'hirty-Sccond Conference on Association for the Advancement of Artificial Intelligence (AAAI), pp. 1538-3545, 2018b.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanezosnet: Multi-scale deep 1
graph convolutional networks. In ICLR, 2019.
Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu, Disentangled graph convolutional networks. In ICML, 2019.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurIPS. Curran Associates, Inc., 2019.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recom- mendations on styles and substitutes. In SIGIR, 2015.
Federico Monti, Oleksandr Shchur, Aleksandar Bojehevski, Or Litany, Stephan Günnemann, and Michael M. Bronstein. Dual-primal graph convolutional networks. CoRR, abs//806.0000 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019. E
Boris Muzellec and Marco Cuturi. Generalizing point embeddings using the wasserstein space of elliptical distributions. In NewrIPS. Curran Associates, Inc., 2018. B
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in
Machine Learning, 1 11(5-6)3355-666 2019. B
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph Markov neural networks. In Proceedings
of the 36th International Conference on Machine Learning (ICMI., pp. 5241-5250, 2019. P

---

Under review as a conference paper at ICLR 2020
Amnon Shashua, Ron Zass, and Tamir Hazan. Multi-way clustering using super-symmetric non- negative tensor factorization. In ECCV, 2006.
Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. Wasserstein propagation for semi-supervised learning. In ICML, 2014.
Amarnag Subramanya and Jeff Bilmes. Semi-supervised learning with measure propagation. J.
Mach. Learn. Res.,
2011. m
Amarnag Subramanya and Partha Pratim Talukdar. Graph- Based Semi-Supervised Learning. Mor- gan & Claypool Publishers, 2014.
Lichao Sun, Wang. Philip S. Yu, and Bo Li. Adversarial attack and defense on graph data: A
survey. CoRR, arXiv: 10528, 2018.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: Extraction and mining of academic social networks. In KDD, 2008. 19
Koji Tsuda. Propagating distributions on a hypergraph by dual information regularization, In JCML, 2005. 8
Shikhar Vashishth, Prateek Yadav, Manik Bhandari, and Partha Talukdar. Confidence-basse graph
convolutional networks for semi-supervised learning. In AISTA7S, 2019. I
Titouan Vayer, Nicolas Courty, Romain Tavenard, Chapel Laetitia, and Remi Flamary. Optimal transport for structured data with application on graphs. In ICML, 2019,
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua
Bengio. Graph attention networks. In ICLR, 2018. 1 ind
Petar Veličković, William Fedus, William L. Hamilton, Pietro Lió, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. In KDD, 2019.
20:3 and
C Villani. Topics in optimal transportation theory. 2003.
C Villani. Optimal transport - Old and new, volume 338. Springer- Verlag, 2008 B
Chris Wendler, Dan Alistarh, and Markus Püschel. Powerset convolutional neural networks. In NeurlPS. Curran Associates, Inc., 2019.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In ICML., 2019a. add
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. CoRR, arXiv:1901.00590 2019b.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. Gromov-wasserseein learning for graph matching and node embedding. ICML, 2019a. P
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
B
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019b.
Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. HyperGCN: A new method of training graph convolutional networks on hypergraphs. In NeurIPS. Curran Associates, Inc., 2019.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICMI., 2016. g
12

---

Under review as a conference paper at ICLR 2020
Rex Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnn explainer: A tool for post-hoc explanation of graph neural networks. NeurIPS. Curran Associates, Inc., 2019.
Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, and T-H. Hubert Chan. Re-revisiting learning hypergraphs: Confidence interval and subgradient method. In ICML, 2017.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning graphs: A survey. CoRR,
arXiv: /0/2.04.22442 2018.
Denny Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. In B. Schölkopf, J. C. Platt, and T. Hoffman (eds.), NIPS. MIT Press, 2007. S
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. CoRR, arXiv: 1812.08434, 2018. a
Dingyuan Zhu, Peng Cui, Daixin Wang, and Wenwu Zhu. Deep variational network embedding in wasserstein space. In KDD, 2018.
Xiaojin Zhu, Andrew B. Goldberg, Ronald Brachman, and Thomas Dietterich. Introduction to Semi-
Supervised Learning. Morgan and Claypool Publishers, 2009.
A APPENDIX
The appendix is organised as follows:
1. Regularised Wasserstein and the Sinkhorn algorithm
2. Time complexity of the proposed DHN
3. Proofs and more notations used for theoretical analysis
4. Additional experiments (Graph-base based soft SSL and Ablation Study)
5. Details of hyperparameters
6. Sources of real-world datasets
A.1 REGULARISED WASSERSTEIN AND THE SINKHIORN ALGORITIIM
For discrete distributions, W, of Equation
2 is the solution of a linear program:
F
Wp (2,8)² = min i=1 j=1
Tij
(10)
s.t. Mi 2 0,
Tty [=]
Σ マラj m===
AA
VSLÚSF
j=1
where for an arbitrary element y E Pr, [q], stands for the probability mass in the ith bin.
A.1.1 SINKHORN DIVERGENCE
The expensive linear program 10 can be efficiently solved by entropic regularisation Cuturi (2013):
W y)" = min
Tej + A Tr
T T[log -117)²
(11)
3
F
F
s.t.
0.
Jsj
[2],
Σ Túj = lul,
1=1
where log(.) is applied element-wise and À > a hyperparameter. The optimal solution x² for takes the following form.
CP
diag(r) exp
diag(c)
x
where diag(z) is diagonal matrix with the components of in the diagonal places.
13

---

Under review as a conference paper at ICLR 2020
Sinkhorn algorithm Cuturi ic., start with an initial K := exp( - and alternately ensure the marginal constraints are satisfied until convergence:
2013):
We optimise Equation I for and via matrix balancing,
r r (K))
ct c+v.((k²r)
where ./ is element-wise division. We the above efficient algorithm in experiments.
A.2 TIME COMPLEXITY OF DHN
We consider the problem of predicting probability distributions for the vertices in H. = (V, Ea) given typically small subset V₂ S V of vertices with known distributions. In this work. we are concerned with discrete distributions modelled on complete separable metric space (M, C). Furthermore, we assume that we are provided with a feature matrix, Xv "v which each vertex V is represented by D,-ddimensional feature vector 2. (here provided with hyperedge feature matrix X E Rm with Ze. 6 E' as Dgddimensional feature representations. Let T be the time taken for the Sinkhorn algorithm on all the vertices with known distributions. Note that T can be approximated in near-linear time Altschuler et al. (2017). Further, let T be the total number of epochs of training. Define
[V). We are also
N =
Σ leb BEB
No
Σ EEE
where hn is the number of hidden units of the GNN layer and hg the number of output channels.
The time complexity oa one-layer DHN is O (aad) DE h1 + | Dv.h2)
A.3 THEORETICAL ANALYSIS: PROOFS
This section is organised follows:
1. Assumptions/notations
2. Definitions generalisation and empirical errors
3. Framework of Algorithmic Stability
4. Proof of SGD Bound
A.3.1 ASSUMPTIONS/NOTAIIOSS
To avoid unnecessary technical complications, assume the histogram admits geometric realisation over the one-dimensional Euclidean space, such that the ith bin is placed at location by R, and set
Cjj lb: byl, AA F.
Without loss of generality, we assume bj < b2 ... S by. and write h4 == b,+1 b, 2 0 for all
i 1,....,, F- take the Wasserstein cost as the Wasserstein-1 distance: W (n, D) = Wi (1, v) In this particular one-dimensional setting, we have a particularly simple form for the cost function:
1. Denote the diameter of the support by D == maxi Sijjs bb - byl br bb. We
Wi (1, /''
F (s) (s)
F2 F, (t) dt
(12)
where F2 IR + [0, 1]. F, R 10 are the cumulative distribution functions of μ,, respec- tively; F-11 F-11 are the generalized inverses of F2 and F,, respectively, defined as (similar for F
(t) = inf (bER (b)
v [0. 1].
(13)
This characterisation is seen in any standard literature on optimal transport, e.g., (Villani Theorem 2. 28).).
2003
14

---

Under review as a conference paper at ICLR 2020
A.3.2 DEFINITIONS: GENERALISATION AND EMPIRICAL ERRROS
Let the learning algorithm As on a dataset be a function from nTh ()) where X' is the input Hilber space, y/ is the output Hilbert space, = X' x V. The training set of datapoints, labels is {21 (21: 11), 2A (Ik, y+)))- Let the loss function be & 5 R. Then the generalisation error or risk R As) is deined as
R(As) = E ((AA,) - -
where p(z) is the probability of seeing the sample E S. The empirical error, the other hand, is defined
Remp (As) = Σ (A): 2n)
5=1
A.3.3 ALGORITHMIC STABILITY
Denote S V Pr for arbitrary training data sampled with respect to distribution D. A learning algorithm for GNN, denoted as A, maps a training set S to a trained GNN / (- Os) + (z, Og). Let S' be another training data set that differs from S by exactly one data. Our goal in this section is to establish a uniform stability
sup SEVXPE PP
JEA (
(s,0s), (z, - EA (f (s Os;,, (z, x))]
sup SCYXPE (F
EA [W (J (z. 0s), ,w)] - EA (W1 (ʃ (Ic, Ost)
sup SCYXPE (xP)
EA W (f (z. θs), ,0) - W, (f (z. ) ,,,)),)))] < 2m3m
(14)
with 8.,. = O (1/m)) which in turn can be used to establish the generalisation error bound of the
form (Verma& Zhang 2019 Theorem 1), following the framework Hardt et al. (2016) for SGD- based learning algorithms. Following the arguments in Verma & Zhang (2019), this boils down to checking few Lipschitz properties for the cost function.
A.3.4
SGD BOUND: PROOF
Note that
/ FF (t) F, (+) dt
W1 (n, v)
|F (s)
F, (s)(s)/
(15)
and from the single-layer bound
(16)
Uniform stability:
E (f, EA (f (,)
sup SCVXPF
PP
sup SCVXPF (x
E W (z. (z. 0s) m)] EA [ (f (a, As:).v)l
sup SCVXPE (.Pe
E W (f (z. Os) 9) W, (f (z, 05)) #)]l 23...
(17)
now remains to bound EA ||eg 0 || resulting from the SGD iterations. Given training set S
applying SGD to GNN amounts to performing the updates
0, -s - VoVl (f, (),),, (Ii, v1.)) Os.t V (f (æi, Os.), v:.)
15

---

Under review as a conference paper at ICLR 2020
where 17 > is the learning rate and 2i, = (Z Vú.) are random data i..d. uniformly sampled from the training set. By the simple formulae equation 13 for mie-dimensiona optimal transport, we can explicitly write out for any parameter set è and data (z. v)
Wi (f (a, 0),
F(( (t) - Fy (t) dt Σ (x++1 m.)
Σ (If (),,,)), -lvl:)
F-1
h4 (lo (Eg 0)1 - (yle)
Σ
j=1
where again we used notation { 1, F. Thus
lyl: to denote the probability mass of y E Pp in the ith bin, for all
0
W1 (1 (x, .))
F-1
Σ
h4 sgn
Σ
1
(o (E2 0]1, - -w/b)
Σ j=1
a
lo (Ez 0)1
00
a
i=1
i=1
F-1
i
Σ
h4
sgn
[a (E2 -)) -)1,,-111) - | Ex > lo (Ex Q)l (8sx
lo (Ez O)1a)
5=1
} 1
his sgn Σ (Es. 0)] - (9]l-(Wbb)
- lo (Eix +)1
Ee-- -lo (Ex θ)l
j=í
-E,, 0),, Eis (E) -v), (11,)
(b];)
=-E,-lo(E, -),, W where sgn (.) is the sign function, and 5 is the Kronecker delta notation. The second equality used the specific form of the derivative of the softmax function. Unfortunately. this gradient is not Lipschitz continuous due to the sign function in the second term. Nevertheless, we use a "modified gradient" that drops the second term, i.e., choose to update the parameter O₂ in the direction
,)1, Σ h. ((( 1
W1 (f (x, v) = E lo (E, O)lx W1 (a (Eg O),
(18)
then obviously this new choice of "descent" direction is certainly Lipschitz continuous, as
0
Wi (f (x, 95)
W1 (f (z, .))
a9
0e,
EEzl
||o (Ez Os)l W1 (a (Ez Os), v) lo (E, 09: W1 (a (Ez Os),
E21-
|10 loo Os)le - (E. Ug | W1 (o (E. θs)
+ + (E.- (E2 )s) W (a (E. θs) v) - W, (a (Ez Os)) vi)
$ 5E (L, D Ex ||0s I1 + W1 (a (E, 0s), a (E, Os:)))
3 L. L. E21-1103 Os S L. o O0s Us
3
< Ezz
2
2
Therefore, if we define
T
Jowi (z, 1) =
Wi ( (z, ().)).
wi (f (z. (c..
(19)
ae,
d0
then the stochastic update algorithm
θ 0s = - v
W₁ (f (Zi, ,s.e) va.)
(20)
Note that this is not a stochastic gradient descent algorithm! the "gradient" involved is a "fake" gradient- this is the counter-intuitive part.
16

---

Under review as a conference paper at ICLR 2020
will still satisfy the generalization bound, due to the Lipschitz continuity
We (z,,, Os) VeWi(S(e ..))
w/]l -
2 2 100 -
3D
||
(21)
In fact, equation 21 is exactly the GNN analogy of (Verma Zhang 2019 Lemma which es- tablishes the stability for the "same sample loss" case. The "different sample loss" analogy, or the lemma in (Verma Zhang 2019 Lemma 2), can be trivially obtained by the definition equation 18 In fact, noting that
8
Wi (J (),)
= =1 la (Ez O)l Wi (a (Ex .0, $ gx
d
we easily obtain
8
Wi (ʃ (s))))
wi (ʃ (z', (z',0)),,1)
S 2g
a0
8
and it follows that
Ve (z, θs) w (z, . 2F
(22)
we obtain the following analogy of (Verma & Zhang 2019 Lemma 3): Starting with two training data sets S, S' that differs by exactly sample, after each iteration we have
Putting together equation 21 and equation 22
E 0 s4 11a -EA
|| Os. Voli (f (Iee Os,1) M10 Os e + V (f (2/2 O).))
Og .g.. Lf F ||
83 t
2mFgx
1+ 2
D EA [1|0s, θs
,, cll1]
m
Solving this first-order recursion gives the stability after T random update steps:
E [10 Os
EnFgxD
Σ
3 1+ 2
2
L
)-1
(23)
t=l
Combining equation 16 and equation 23 gives
FLogg D2
T
[-1
LA W (f (z, .2) W, (f Os.
1 2 SnDDogs
(24)
m
Therefore, we actually have the uniform algorithmic stability equation
17 holds with
Bm
Lo D
Σ
(I,
3
(-1
(25)
2m
A.4 ADDITIONAL. EXPERIMENTS
Dataset
GCN
Soft-GCN
GAT
Soft-GAT
Simple-GCN
Soft-Simple-GCN
Cora
81.5
81.7
82.8
82.5
81
81.6
Citeseer
70.3
70.1
70.6
70.6
71.8
71.6
Pubmed
79
78.6
78.7
78.4
78.8
78.8
Table 3: Accuracy on traditional graph- SSL datasets. The experimental setting is the same
in GCN Kipf & Welling (2017) and GAT Veličkovié et al. (2018). We used 10% of the labelled vertices as validation data to tune the hyperparameter 17.
A.4.1 ABLATION STUDY
In this section, we compared our proposed one-layer DHN against deeper layers and without ex- ploiting directed hyperedges.
17

---

Under review as a conference paper at ICLR 2020
Table 4: Ablation study of proposed Soft-DHN. Please see section for more details.
# DHN layers
GNN layers(hops)
Cora
DBLP
2
2
7.68 1 0.24
7.98 1 0.27
1.25
7.93 1 0.28
1 0.27
7.98
0.22
0
5.64 = 0.32
6.45 0.38
1
5.41 = 0.35
6.26 + 0.32
2
4.87 = 0.40
5.65 0.42
A.5 DETAILS OF HYPERPARAMETERS
Inspired by the experimental setups of prior related works Kipf & Welling (2017); Liao et al. 2019).
tune hyperparameters using the Cora co-authorship network dataset alone. The optimal hyperpa- rameters are fixed and then used for all the other datasets. Table [ shows the list of hyperparameters used in the datasets. Prior works Kipf & Welling (017); Liao et (2019) have extensively per- formed tuning of hyperparameters such as hidden size, learning rate, etc and we fixed their reported optimal hyperparameters. It should be noted that self training and co-training methods [Li et al.
(2018b) can also be used in case of absence of validation data. We hyperparameterise the cost matrix (base metric of the Wasserstein distance) as follows:
1
π n
7]
1
7
...
C
" " 9
1_
Table 6 shows the best results on the validation split of Cora (with optimal hyperaparameters) The training set had 140 vertices, the validation set 1000 vertices and the rest of the vertices used to test the models. The results reported are after 200 epochs of training with a seed value of 598.
Table 5: List of hyperparameters used in the experiments. A set of values indicates that the corre- sponding hyperparameter is tuned from the set (on the validation split).
Hyperparameter
Value(s)
Hyperparameter
Value(s)
hidden size
16
(Sinkhom)
0.1
learning rate
0.01
# Sinkhorn iterations
100
dropout
0.5
7
10..,
weight decay
5 10
À
(1,0.5 0.1, 0.05, 0.01,
10......55 ,5 10 10-7]
A.6 SOURCES OF THE REAL-WORLDD DATASETS
Co-authorship data: All authors co-authoring paper are one hyperedge. We used the author dateWoo get the co-authorship hypergraph for cora. We manually constructed the DBLP dataset from Arnetmine
htapss//pcoole.c..uuassscm mccallum/data.hie html http:///mmmneeoooyllllaaaasasaai
18

---

Under review as a conference paper at ICLR 2020
Table 6: Optimal hyperparameters the validation Cora Co-authorship network.
Method
Optimal hyperparameters
Best MSE validation set
KL-MLP OT-MLP
7.87
17 31
6.47
KLR-MLP OTR-MLP
7.39
1 = 25, 5 x 10
4.86
KL-HGNN
6.98
HL-HypeGGCN
7.03
7) = 20
3.24
Soft Soft-HyeeGGCN
= 17
4.02
KL-DHN Soft-DHN
6.34
= 19
2.67
A.6.1 CONSTRUCTION THE DBLP DATASET
We downloaded the entire dblp data from attps://aming citat Woon/DBBP-CC the dblp dataset used the paper are as follows:
oonoonna ttrrbb.. bz Tang et al. (2008). The steps for constructing
We defined a set of 5 conference categories (histograms for the SSL task) as "algorithms", "database", ''datamining,. "intelligence", and "vision"
For total of 4304 venues in the entire dbip dataset took papers from only sub- set of venues from httpt:t/tsee/ wi wikipedia of
celeencc_ccoffeenceeeeeeeeee corperrrenncesccrrressoonnnng corresponding to the above 5 conferences
From the venues of the above 5 conference categories, we got 22535 authors publishing at least two documents for a total of 43413
We took the abstracts of all these 43413 documents, constructed dictionary of the most frequent words (words with frequency more than 100) and this gave us dictionary size of 1425
We then extracted the 117215 citation links among these documents
A.6.2 CONSTRUCTION OF THE AMAZON OFFICE PRODUCT DATASET
We downloaded the entire Amazon data He & McAuley (016)) McAuley et al. (2015). The steps for constructing the dataset used in the paper are as follows:
We downloaded the office product ratings subset from the entire dataset
We constructed hypergraph of items with each hyperedge representing user connecting all the items that they bought
We removed hyperedges of size
We connected pair of hyperedges (biedirectiona) they had more than 1 item in common
A.6.3 CONSTRUCTION OF THE ACM DATASET
We downloaded the entire ACM data from https: aminer. wwwner. wwa.:eooo/labaaateseeeeeee http:///waamieeeeeeeeeaaaataaaaa
citation acm. v9. zip Tang et al. (2008). The steps for curating the dataset in the paper are
follows:
19

---

Under review as a conference paper at ICLR 2020
Based on the number of papers published, we identified the six most popular venues: "Jour- nal of Computational Physics". "IEEE Transactions on Pattemn Analysis and Machine In- telligence", "Automatica (Journal of IFACY", "IEEE Transactions Information Theory", "Expert Systems with Apllications: An International Journal", and "IEEE Transactions on Computers"
We then listed the set of all authors published in these venues (we got total of 67057 authors).
We finally obtained the citation relationships of all the documents co-authored by these authors (total number of documents is 25511 1 and total number of citations is 59884)
A.6.4 DETAILS OF THE ARXIV DATASET
We downloaded the entire arXiv dataset Clement et al. (2019) from htatttss:/ggghhi com/
mat mattbiirbbum/aan seexii--uuee walullippulllle attp-aaaaaaaatettlleeee//a/////a
The steps for cu-
rating the dataset in the paper are as follows:
We removed papers without any authors and got total of 13, 54, 752 edges
We extracted 67, 28, 683 citation edges among these papers
The total number of authors in these papers is 7, 70, 790
20


Reviews:
[{"review_id": "rkllgc3atH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 explores hypergraph-based SSL of histograms. DHN enables soft SSL learning based on the existing tools from optimal transportation. The idea of treating hyperedges as vertexes of another graph is novel and the theoretical analysis is sound.\n\nHowever, the paper has the following issues:\n\n1) The writing is poor, especially about the reference, and the description of how and why DHN works (section 3.3).\n\n2) The novelty is restricted. It seems that the only innovation is introducing the information from the hyperedges into $H_E^{(0)}$.\n\n3) Though the experiments on Cora and DBLP have revealed the superiority of DHN, the authors still need a more thorough empirical evaluation on some challenging benchmarks to draw the conclusion.\n\nI'm willing to increase my score if the concerns are addressed.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bygmcc07cB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 this paper, the authors propose a soft semi-supervised learning approach on a hypergraph. On the one hand, the vertex labels should be not only numerical or categorical variables but also probability distributions. On the other hand, hypergraphs provide a much more flexible mean to encode the real-world complicated relationship compared to the essential pairwise association. Specifically, the authors carefully obtain the generalization error bounds for a one-layer graph neural network. The experiments support the theory and provide the empirical verification of the proposed method. The appendix offers plenty of details that are helpful for the reader to understand both the theoretical and practical perspectives of this paper. Also, the code looks good to me. The structure of the provided codebase is clear and well documented.\n\nI have some questions and suggestions for the authors:\n1. In the method section 3.3, the authors said that “A key idea of our approach is to treat each hyperedge as a vertex of the graph” After this transformation, the graph could be super sparse. So I’d like to know more about the efficiency of the proposed method. Because the datasets in this paper could not be considered as a giant graph. The efficiency could be much more critical for large-scale applications. Besides, such conversion could be one of the most significant technical novelty in this paper, which makes me worry about the methodology contribution of this submission.\n\n2. In the theoretical analysis section 4, there are lots of references for the existing lemmas and theorems. It could be much better if the authors could briefly review and summarize these equations before applying them. By the way, I appreciate the detailed appendix at the same time. But such a summary could complete the paper in a more self-contained way. Also, the authors should improve the writing of paper at the same time.\n\n3. In the experiments section 5, I wonder if the authors would consider some more challenging datasets with the larger graph to evaluate the proposed method. Also, the theoretical analysis is about one-layer networks, which looks technical sound to me. However, in practice, we could not only use the one-layer network for graph classification, even for a small graph. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygAYy6y5H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Contributions:\n1. This paper proposes a semi-supervised graph neural network method for hypergraphs.\n2. A generalization error bound was proposed adapted to the semi-supervised setting with Wasserstein's loss.\n3. Empirical results demonstrate the effectiveness of the proposed method.\n\nThe algorithmic contribution of this paper is clear: it proposes a new network architecture that (1) initialize latent features H^{(0)}_E for hyperedges from a \"hyperedge graph\" and (2) learn latent features for each node and hyperedge using a GCN type network. Since the latent features are formulated as discrete distributions, a Wasserstein distance can be applied for training with the sinkhorn approximation algorithm.\n\nI think the weakness of this paper is two folds, which makes it not ready to publish. First, the paper claims that the performance gain results from the exploitation of directed hyperedges. This is reasonable if I barely see the results for Soft-DHN. However, I find the design of the hyperedge GNN to be fragile regarding the number of layers from the result in Table 4. Normally it is reasonable to use a two-layer GNN, but the result is very bad when doing so (see Soft-DHN 2 layers result in Sec. A.4.1). Also, the result of the proposed model is still good when not applying a hypergraph GNN. So I'm confused about where the performance gain comes from.\n\nAnother weakness is the paper writing. Below are a few comments:\n[Page 3, Sec. 3.1] By saying \"t\\neq\\Phi\", do you mean \"t\\neq\\emptyset\"?\n[Page 3, Sec. 3.2] Please introduce the notation (M, C) right after it first appears in the third line of Sec. 3.2.\n[Page 3, Sec. 3.2] The notation n,m are confusing. Do you mean m=|E|?\n[Page 3, Sec. 3.2] I cannot see how Z=h(\\mathcal{H},X_V,X_E) maps each vertex to a probability distribution. Do you mean each row of Z is a probability distribution for each vertex?\n[Page 4, Sec. 3.2] Please define E_D. Is E_D the same as E_d?\n[Page 4, Sec. 3.3] Be explicit by saying \"approximate the hypergraph by a suitable graph\", what do you mean by \"suitable graph\"? Does it mean use cliques in place of hyperedges?\n[Page 4, Sec. 3.3] t=0,...,\\tau-1\n\nSince the writing significantly affects the paper readability, and the core contribution of the paper seems incremental, I will vote for a reject to this paper.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes and evaluates using graph convolutional networks for semi-supervised learning of probability distributions (histograms). The paper was reviewed by three experts, all of whom gave a Weak Reject rating. The reviewers acknowledged the strengths of the paper, but also had several important concerns including quality of writing and significance of the contribution, in addition to several more specific technical questions. The authors submitted a response that addressed these concerns to some extent. However, in post-rebuttal discussions, the reviewers chose not to change their ratings, feeling that quality of writing still needed to be improved and that overall a significant revision and another round of peer review would be needed. In light of these reviews, we are not able to recommend accepting the paper, but hope the authors will find the suggestions of the reviewers helpful in preparing a revision for another venue. 
Decision: Reject