Title: GRAPH NEURAL NETWORKS FOR SOFT SEMI-SUPERVISED LEARNING ON 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 coauthorship 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.

1. 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. (2012) ; Goodfellow et al. (2014) ; Bahdanau et al. (2015) ; LeCun et 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 et al. (1998) ) to enable handling graph-structured data. GCN was shown to be, in particular, effective in semi-supervised learning on attributed graphs. GCNs have inspired the current state-of-the art models for graph-based 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 as co-authorship networks, recommendation networks, etc., vertex labels can be naturally represented by probability distributions or histograms. Moreover, these real-world network datasets have complex relationships going beyond pairwise associations. Such relationships can be modelled naturally and flexibly by hypergraphs. Moreover, hypergraphs can encode additional relationships with directions as illustrated in Figure 1 and these hypergraphs are directed hypergraphs Gallo et al. (1993) .

Inspired by a 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-art models for traditional graph-based SSL, we make the following contributions.

• We explore GNNs for soft SSL in which vertex labels are probability distributions. Motivated 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 3).

• We provide generalisation error bounds for a one-layer GNN within the framework of algorithmic stability. We establish that such models, which use filters with bounded eigenvalues independent of graph size, can satisfy the strong notion of uniform stability and thus is generalisable. In particular, the algorithmic stability of a one-layer GNN depends on the largest absolute eigenvalue of the graph convolution filter (Section 4).

• We demonstrate DHN's effectiveness through detailed experimentation on real-world data.

In particular, we demonstrate superiority over state-of-the-art hypergraph-based neural networks. We provide new empirical benchmarks for soft-SSL on directed hypergraphs and make the code available to foster reproducible research (Section 5). Learning on hypergraphs: Hypergraph is a combinatorial structure consisting of vertices and hyperedges, where each hyperedge is allowed to connect any number of 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) 

2. RELATED WORK:



Graph:



3. METHOD:

In this section, we first describe soft SSL on directed hypergraphs and then propose DHN (Directed Hypergraph Network) for the problem. 

E d = {(t 1 , h 1 ), • • • , (t m , h m )} ⊆ 2 V × 2 V

is a set of m directed hyperedges. Each element in E d is an ordered pair (t, h) where t ⊆ V is the tail and h ⊆ V is the head with t = ∅, h = ∅. Denote the set of all undirected hyperedges by E.

E = (t,h)∈E d t ∪ h .

Denote I ∈ {0, 1} |V |×|E| to be the incidence matrix of E i.e. I(v, e) = 1 if v ∈ e and 0 otherwise.

3.2. SOFT SSL ON DIRECTED HYPERGRAPHS:

We consider the problem of predicting probability distributions for the vertices in H = (V, E d ) given a typically small subset V k ⊆ V of vertices with known distributions. In this work, we are concerned with discrete distributions modelled on a metric space i.e. 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, X V ∈ R n×D V , in which each vertex v ∈ V is represented by a D V -dimensional feature vector x v (here n = |V |). We are also provided with a hyperedge feature matrix X E ∈ R m×D E with x e , e ∈ E as D E -dimensional feature representations (here

m = |E d |).

Our objective is to learn a labelling function Z = h H, X V , X E that maps each vertex to a probability distribution in the space of discrete probability distributions P F (M ) 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 non-negative symmetric matrix of size

F × F . Note that each row of Z ∈ [0, 1] n×F maps each vertex v ∈ V to a probability distribution Z v ∈ [0, 1] F .

The function h is going to be trained on a supervised loss, L ,w.r.t to the vertices in V k so that the trained h can be used to predict distributions of all the vertices in V \ V k . 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), E d the citation relationships among the documents, F the number of possible research interests of authors (Machine Learning, Theoretical Computer Science, etc.), X V and X E any available features on the authors and documents respectively (e.g. text attributes). A key idea of our approach is to treat each hyperedge e ∈ E as a vertex of the graph G = (E, E d ).

We then pass G through a graph neural network to obtain H E = f GN N (G, X E ) so that the initial features, X E , are refined to H E . We then propose the layer-wise propagation rule of DHN as:

EQUATION

where [•, •] denotes concatenation, t is the time step, I is the incidence matrix, H

EQUATION

EQUATION

), σ and σ 1 are non-linear activation functions, and τ is the total number of time steps with

H (0) V = X V . Note that the labelling function Z = h(H, X V , X E ) = softmax H τ V

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 ∈ V k , the predicted distribution Z v and the (known) true distribution Y v must be "close" to each other. A natural way to compare probability distributions is to use the KL-divergence between Y v and Z v . However, KL-divergence cannot exploit the metric space (M, C) and suffers from stability issues Chen et al. (2016) . In this work, we use the more stable Wasserstein distance to exploit the metric space Gao et al. (2019) .

EQUATION

For discrete distributions, W p is the solution of a linear program. For practical purposes, we compute the regularised distance using the Sinkhorn algorithm. Please see Appendix A.1 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.

4. THEORETICAL ANALYSIS: GENERALISATION ERROR BOUND:

In this section, we establish generalisation error bounds for a one-layer GNN by extending the results of a 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 is an 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-tions. We finally give the main result (Theorem 1) which states that a GNN trained with Wasserstein loss has the same generalisation error bound as the traditional GCN (trained with cross entropy).

Let G = (V, E) be a connected graph with |V | = n vertices. We consider GNN of a single layer

EQUATION

where X ∈ R n×d is the feature matrix (n is the number of vertices in a graph, d is the dimension of the feature vectors), K = g (L G ) is a graph filter (typically symmetrically normalised adjacency with self loops, and L G ∈ R n×n is the graph Laplacian), and Θ ∈ R d×F is the set of parameters. We note that our proposed DHN falls under this formulation in special circumstances. Specifically if the non-linearity σ 1 in Equation 1 is removed we get the kernel K = II T (also known as the clique expansion of the hypergraph Zhou et al. (2007) .) The non-linearity σ in Equation 3is the softmax function acting on each row of the product g (L G ) XΘ ∈ R n×F ; the output is of dimension n × F , where each output row is a discrete probability distribution, i.e., f (X, Θ) ≥ 0 and f (X, Θ)

1 F = 1 n

where 1 F = (1, . . . , 1) F ∈ R F , and similarly for 1 n . Without loss of generality, we assume d = 1. Note that in order for the output to be nontrivial probability distributions, we must assume F > 1.

We adopt an ego-graph view (Verma & Zhang, 2019, formula (2)) to simplify our discussion for local behavior of the soft GCN at a particular vertex. Whenever no confusion arises, we identify a vertices x and χ in the graph G with their respective D-dimensional feature vectors. Thus the output of

f at x ∈ V is f (x, Θ) = σ   χ∈N (x) K xχ χΘ   = σ     χ∈N (x) K xχ χ   • Θ  

where N (x) denotes for the one-hop neighborhood of x with respect to the adjacency relation defined by matrix K, and K xχ ∈ R stands for the entry in K ∈ R n×n that describes the adjacency relation between vertices x and χ. Let

E x := χ∈N (x) K xχ χ ∈ R so that f (x, Θ) = σ (E x • Θ) .

We consider the supervised learning setting, and learn GNN from the training set {z i = (x i , y i ) , i = 1, . . . , m} sampled i.i.d. from the product space V × P F with respect to probability distribution D on this product space, where P F is the space of discrete probability distributions on F atoms. The output of softmax lies in P F , which is a convex cone. For any new data z = (x, y) ∼ D, we evaluate the performance of GNN f using a Wasserstein cost

(f (•, Θ) , z) = (f (•, Θ) , (x, y)) = W (f (x, Θ) , y) .

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 ∈ R F ×F that is defined for pairs of histogram bins. The transport problem is a linear program with z = f (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,

|W 1 (f (x, Θ S ) , y) -W 1 (f (x, Θ S ) , y)| ≤ W 1 (f (x, Θ S ) , f (x, Θ S )) .

By (Villani, 2008 , Theorem 6.13), recall that the diameter of the support is D, we have

W 1 (f (x, Θ S ) , f (x, Θ S )) ≤ D f (x, Θ S ) -f (x, Θ S ) TV

where • TV is the total variation distance, which by definition is

f (x, Θ S ) -f (x, Θ S ) TV = 1 2 F i=1 |[f (x, Θ S )] i -[f (x, Θ S )] i | = 1 2 σ (E x • Θ S ) -σ (E x • Θ S ) 1

where • 1 is the L 1 -distance on R F . Since the softmax function is Lipschitz continuous, we have

f (x, Θ S ) -f (x, Θ S ) TV ≤ L σ 2 |E x | • Θ S -Θ S 1

and thus

|E A [W1(f (x,Θ S ),y)-W1(f (x,Θ S ),y)]|≤ Lσ D 2 sup x∈V |Ex|•E A Θ S -Θ S 1 = Lσ D 2 g λ E A Θ S -Θ S 1

(4) where we used notation g λ := sup x∈V |E x | as defined in Verma & Zhang (2019), which is known to be upper bounded by λ max G , the spectrum of the graph Laplacian L G with largest absolute value. 4.0.2 SGD BOUND It now remains to bound E A Θ S -Θ S 1 resulting from the SGD iterations. The main technical challenge, as noted before, is to generalise the results to the Wasserstein space which is an abstract metric space without linear structure. Specifically, we have to modify the "gradient" in the Wasserstein space as the straightforward version Verma & Zhang (2019) does not satisfy the Lipschitz condition required in the algorithmic stability framework. To the best of our knowledge this modification is not seen in existing literature and can be thought of as a 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.

EQUATION

Combining equation 4 and equation 23 gives us

EQUATION

Therefore, we actually have the uniform algorithmic stability equation 14 holds with

EQUATION

Note that here with a bounded loss function 0 ≤ (A S , y) ≤ B, satisfies the following generalisation bound with probability at least 1 -δ, over the random draw of S, y with δ ∈ (0, 1),

β m = O( 1 m ) (needed

EQUATION

where R(A S ) is the generalisation error/risk and R emp (A S ) is the empirical error. Please see Appendix A.3.2 for definitions. Finally, by Equation 8, and Equation 9, our result i.e. Equation 7immediately gives the following theorem:

Theorem 1 Let A S be a one-layer GNN algorithm (of 3) equipped with the graph convolutional filter g(L G ) and trained on a dataset S for T iterations. Let the loss and activation functions be Lipschitz-continuous and smooth. Then the following expected generalisation gap holds with probability at least 1 -δ, δ ∈ {0, 1}:

E SGD R(A S ) -R emp (A S ) ≤ 1 m O (λ max G ) 2T + O (λ max G ) 2T + B log 1 δ 2m

where the expectation E SGD is taken over the randomness inherent in SGD, m is the no. training samples, and B is a constant which depends on the loss function. Our theorem states that GNN trained withe Wasserstein loss enjoys the same generalisation error bound of the traditional GCN (trained with cross entropy). We now discuss experiments. To demonstrate the effectiveness of our proposed DHN, we conducted experiments on 5 real-world directed hypergraphs. Four of them are Co-authorship datasets and one of them is a recommendation dataset. Table 1 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 Kipf & Welling (2017); Liao et al. ( 2019), we tune hyperparameters using the Cora citation network dataset alone and use the optimal hyperparameters for all the other datasets. We hyperparameterise the cost matrix (base metric of the Wasserstein distance) as follows:

C =     1 η η . . . η η η 1 η . . . η η . . . . . . . . . . . . . . . . . . η η η . . . η 1    

The cost matrix C is an F × F matrix (F is the number of histogram bins) with ones on the diagonal and a hyperparameter η elsewhere. We could have used a matrix of all ηs. But it is no different from a matrix of all ones from the optimisation perspective and so we used the above more general 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 Appendix A.1 for more details. We compared DHN with the following baselines:

• KL-MLP: We used a simple multi-layer perceptron (MLP) on the features of the vertices and trained it using KL-divergence • KL-HGNN / KL-HyperGCN: We trained the different GCN-based methods on hypergraphs with KL divergence loss function on the labelled vertices.

•

• Soft-HGNN / Soft-HyperGCN: We trained the different GCN-based methods on hypergraphs with the Wasserstein distance as the loss function.

Metric for comparison::

We use the mean squared error (MSE) between true and predicted distributions on the test set of vertices. Table 2 shows MSEs on the test split for all the three datasets. 

Z = sof tmax(I • H E • Θ 1 ), H E = A 2 X E Θ 2

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 4 . Our results demonstrate strong performances across all the datasets esp. on 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 as the loss function. This is because the Soft models can exploit the distance matrix C while KL-divergence does not. (2018) . We achieved competitive results as shown in Appendix Table 3 6 CONCLUSION

We have proposed DHN, a 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, we have established generalisation bounds for DHN within the framework of algorithmic stability. We have also demonstrated DHN's effectiveness through detailed experimentation on real-world hypergraph datasets.

A APPENDIX:

The appendix is organised as follows:

1. Regularised Wasserstein and the Sinkhorn algorithm 

EQUATION

where for an arbitrary element q ∈ P F , [q] i 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 λ p (z, y) p = min F i=1 F j=1 C p ij π ij + λ • Tr π log π -11 T T (11) s.t. π ij ≥ 0, F j=1 π ij = [z] i , F i=1 π ij = [y] j ∀1 ≤ i, j ≤ F

where log(•) is applied element-wise and λ ≥ 0 is a hyperparameter. The optimal solution π * for λ > 0 takes the following form.

π * = diag(r) • exp - C p λ • diag(c)

where diag(z) is a diagonal matrix with the components of z in the diagonal places. The empirical error, on the other hand, is defined as 

R emp (A S ) := 1 k k j=1 (A S ,

EQUATION

EQUATION

and from the single-layer bound

EQUATION

Uniform stability:

EQUATION

It now remains to bound E A Θ S -Θ S 1 resulting from the SGD iterations. Given training set S, applying SGD to GNN amounts to performing the updates

Θ S,t+1 = Θ S,t -η∇ Θ (f (•, Θ) , (x it , y it )) = Θ S,t -η∇ Θ W 1 (f (x it , Θ S,t ) , y it )

where η > 0 is the learning rate and z it = (x it , y it ) are random data i.i.d. uniformly sampled from the training set. By the simple formulae equation 15 for one-dimensional optimal transport, we can explicitly write out for any parameter set Θ and data z = (x, y)

W 1 (f (x, Θ) , y) = ∞ -∞ F f (x,Θ) (t) -F y (t) dt = F -1 i=1 (x i+1 -x i ) i j=1 ([f (x, Θ)] i -[y] i ) = F -1 i=1 h i i j=1 ([σ (E x • Θ)] i -[y] i )

where again we used notation [y] i to denote the probability mass of y ∈ P F in the ith bin, for all i = 1, . . . , F . Thus

∂ ∂Θ k W 1 (f (x, Θ) , y) = F -1 i=1 h i • sgn    i j=1 [σ (E x • Θ)] j -[y] j    • i j=1 ∂ ∂Θ k [σ (E x • Θ)] j = F -1 i=1 h i • sgn    i j=1 [σ (E x • Θ)] j -[y] j    • E x i j=1 [σ (E x • Θ)] j (δ jk -[σ (E x • Θ)] k ) = E x • [σ (E x • Θ)] k F -1 i=1 h i • sgn    i j=1 [σ (E x • Θ)] j -[y] j      1 - j j=i [σ (E x • Θ)] j   =Ex•[σ(Ex•Θ)] k F -1 i=1 hi•sgn{ i j=1 ([σ(Ex•Θ)] j -[y]j )}( j j=i ([y]j-[σ(Ex•Θ)] j )+ F j=i+1 [y]j ) =-Ex•[σ(Ex•Θ)] k •W1(σ(Ex•Θ),y)+Ex•[σ(Ex•Θ)] k F -1 i=1 hi•sgn{ i j=1 ([σ(Ex•Θ)] j -[y]j )} F j=i+1 [y]j

where sgn {•} is the sign function, and δ ik 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, if we use a "modified gradient" that drops the second term, i.e., choose to update the parameter Θ k in the direction

EQUATION

then obviously this new choice of "descent" direction is certainly Lipschitz continuous, as

EQUATION

then the stochastic update algorithm1 

EQUATION

will still satisfy the generalization bound, due to the Lipschitz continuity

EQUATION

In fact, equation 21 is exactly the GNN analogy of (Verma & Zhang, 2019, Lemma 1) which establishes 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

∂ ∂Θ k W 1 (f (x, Θ) , y) = |E x • [σ (E x • Θ)] k • W 1 (σ (E x • Θ) , y)| ≤ g λ D,

we easily obtain

∂ ∂Θ k W 1 (f (x, Θ S ) , y) - ∂ ∂Θ k W 1 (f (x , Θ S ) , y ) ≤ 2g λ D

and it follows that

EQUATION

Putting together equation 21 and equation 22, we obtain the following analogy of (Verma & Zhang, 2019, Lemma 3): Starting with two training data sets S, S that differs by exactly one sample, after each iteration t we have

E A Θ S,t+1 -Θ S ,t+1 1 = E A Θ S,t -η ∇ Θ W 1 (f (x t , Θ S,t ) , y t ) -Θ S ,t + η ∇ Θ W 1 (f (x t , Θ S ,t ) , y t ) ≤E A [ Θ S,t+1 -Θ S ,t+1 1 ]+(1-1 m )•η• 3D 2 Lσg 2 λ E A [ Θ S,t -Θ S ,t 1 ]+ 1 m •η•2F g λ D ≤ 1 + 3 2 ηDL σ g 2 λ E A Θ S,t -Θ S ,t 1 + 2ηF g λ D m .

Solving this first-order recursion gives the stability after T random update steps: GAT Veličković et al. (2018) . We used 10% of the labelled vertices as validation data to tune the hyperparameter η.

EQUATION

A.4.1 ABLATION STUDY:

In this section, we compared our proposed one-layer DHN against deeper layers and without exploiting directed hyperedges. Co-authorship data: All authors co-authoring a paper are in one hyperedge. We used the author data2 to get the co-authorship hypergraph for cora. We manually constructed the DBLP dataset from Arnetminer3 .

:

Note that this is not even a stochastic gradient descent algorithm! the "gradient" involved is a "fake" gradient -this is the counter-intuitive part.

https://people.cs.umass.edu/ mccallum/data.html

https://aminer.org/lab-datasets/citation/DBLP-citation-Jan8.tar.bz

Figures and Tables:

Figure 1: (Best seen in colour) Examples of real-world networks modelled as directed hypergraphs in which labels on the vertices can be represented by probability distributions. To the left is a coauthorship 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 a 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 a couple of products in the figure). Please see Section 1 for more details.

-based deep learning: Geometric deep learning Bronstein et al. (2017) is an umbrella phrase for emerging techniques attempting to generalise (structured) deep neural networks to non-Euclidean domains such as 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. (2019a); Veličković et al. (2018); Monti et al. (2018); Vashishth et al. (2019); Ma et al. (2019); Qu et al. (2019) and graphbased unsupervised learning Hamilton et al. (2017a); Veličković et al. (2019) problems. GCNs have also been applied for semi-supervised graph classification Li et al. (2019). The reader is referred to a comprehensive literature review Bronstein et al. (2017) and extensive surveys Hamilton et al. (2017b); Battaglia et al. (2018); Zhang et al. (2018); Wu et al. (2019b); Sun et al. (2018); Zhou et al. (2018) on this topic. Recently, graph-based deep models (also messagepassing neural networks Gilmer et al. (2017)) have been analysed theoretically Dehmamy et al. (2019); Ying et al. (2019); Knyazev et al. (2019); Chen et al. (2019b); Maron et al. (2019); Morris et al. (2019); Xu et al. (2019b); Chen et al. (2019a); Kawamoto (2018); Xu et al. (2018); Chen et al. (2018). We note a work on stability and generalisation bounds of GCNs Verma & Zhang (2019).

DIRECTED HYPERGRAPH A directed hypergraph Gallo et al. (1993) is an ordered pair H = (V, E d ) where V = {v 1 , • • • , v n } is a set of n vertices and

DHN (DIRECTED HYPERGRAPH NETWORK) Hypergraphs contain hyperedges in which relationships can go beyond pairwise and hence are challenging to deal with. A flexible way to embed vertices of a hypergraph is to "approximate" the hypergraph by a suitable graph and then apply traditional graph-based methods on the vertices. Two notable candidates of h 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-based Laplacian Chan & Liang (2018) to approximate the input hypergraph. However, they are restricted to undirected hyperedges and also cannot exploit the hyperedge feature matrix X E .

to obtain a tight generalisation bound). 4.1 PUTTING EVERYTHING TOGETHER Lemma 1 (Verma & Zhang, 2019, Lemma 4): Let λ max G be the maximum absolute eigenvalue of L G . Let G x be the ego-graph of a vertex x ∈ V with corresponding maximum absolute eigenvalue λ max Gx . Then the following eigenvalue (singular value) bound holds ∀x ∈ V , λ max Gx ≤ λ max G Verma & Zhang, 2019, Theorem 2) A uniform stable randomised algorithm (A S , β m )

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-based regularisation that uses the structure (graph / hypergraph) Subramanya & Bilmes (2011). • OTR-MLP: We regularised an MLP with explicit Wasserestein-distance-based regularisation that uses the structure (graph / hypergraph) Solomon et al. (2014). For hypergraphs we used the clique expansion of the hypergraph Gao et al. (2019).

Moreover, our proposed DHN outperforms two strong hypergraph baselines viz.HGNN Feng et al.  (2019)  andHyperGCN 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 our proposed DHN does exploit them.We also experimented on standard graph benchmark node-classification datasets such as Cora, Citeseer, and Pubmed by treating the class label as one-hot probability distribution. We used the Soft variants of GCN Kipf & Welling (2017), SimpleGCN Wu et al. (2019a), and GAT Veličković et al.

Time complexity of the proposed DHN 3. Proofs and more notations used for theoretical analysis 4. Additional experiments (Graph-based soft SSL and Ablation Study) 5. Details of hyperparameters 6. Sources of real-world datasets A.1 REGULARISED WASSERSTEIN AND THE SINKHORN ALGORITHM For discrete distributions, W p of Equation 2 is the solution of a linear program:

DEFINITIONS: GENERALISATION AND EMPIRICAL ERRROS Let the learning algorithm A S on a dataset S be a function from ζ m to (Y) X . where X is the input Hilber space, Y is the output Hilbert space, ζ = X × Y. The training set of datapoints, labels is S = {z 1 = (x 1 , y 1 ), • • • , z k = (x k , y k ))}. Let the loss function be : ζ m × ζ → R. Then the generalisation error or risk R(A S ) is deined as R(A S ) := E (A S , z) = (A S , z)p(z)dz where p(z) is the probability of seeing the sample z ∈ S.

with β m = 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 SGDbased learning algorithms. Following the arguments in Verma & Zhang (2019), this boils down to checking a few Lipschitz properties for the cost function. A.3.4 SGD BOUND: PROOF Note that

Laplacian to extend GCNs to hypergraphs. Another line of work uses the mathematically appealing tensor methods Shashua et al. (2006); Bulò & 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 (2018); Wendler et al. (2019). These developments are motivated from the spectral theory of hypergraphs which is an active area of research Li & Milenkovic (2017); Chien et al.

Table content: <table><tr><td>(2019); Chitra &amp; Raphael</td></tr><tr><td>(2019); Li &amp; Milenkovic (2018b); Li et al. (2018a); Li &amp; Milenkovic (2018a)</td></tr><tr><td>Graph-based soft SSL: Researchers have shown that using unlabelled data during training can</td></tr><tr><td>improve label prediction significantly Chapelle et al. (2010); Zhu et al. (2009); Subramanya &amp; Taluk-</td></tr><tr><td>dar (2014); Yang et al. (2016). While most methods assume that labels of interest are numerical or</td></tr><tr><td>categorical variables, other works "soften" this assumption and handle "soft labels" such as his-</td></tr><tr><td>tograms Corduneanu &amp; Jaakkola (2005); Tsuda (2005). One way of propagating histograms is to</td></tr><tr><td>minimise the Kullback-Leibler (KL) divergence Subramanya &amp; Bilmes (2011). Recent studies have</td></tr><tr><td>replaced the metric-agnostic KL divergence with metric-aware Wasserstein distance (interactions</td></tr><tr><td>between histogram bins) for graphs Solomon et al. (2014) and hypergraphs Gao et al. (2019).</td></tr><tr><td>Embeddings in Wasserstein space: There exist at least a couple of recent works that embed</td></tr><tr><td>Gaussian distributions in the Wasserstein space Muzellec &amp; Cuturi (2018); Zhu et al. (2018). In-</td></tr><tr><td>spired by a recent work Frogner et al. (2019), in this work, we focus on embedding input data as a</td></tr><tr><td>discrete probability distrirbution on a fixed support set. The Wasserstein distance and its gradient</td></tr><tr><td>require the solution of a linear program Villani (2008) and are costly to compute Peyré &amp; Cuturi</td></tr><tr><td>(2019). A popular efficient approximation is the Sinkhorn divergence Cuturi (2013) in which the</td></tr><tr><td>underlying problem is regularised and is computed efficiently by a fixed-point iteration. Recent</td></tr><tr><td>works have shown that it is suitable for gradient-based optimisation through automatic differentia-</td></tr><tr><td>tion Frogner et al. (2015); Genevay et al. (2018); Frogner et al. (2019). A couple of recent works</td></tr><tr><td>compute Wasserstein distance between graph pairs Xu et al. (2019a); Vayer et al. (2019).</td></tr></table>

Statistics of datasets used in the experiments. Please see Section 3 for the notations used.

Table content: <table><tr><td>Dataset</td><td>Type</td><td>|V|</td><td>|E|</td><td>|E d |</td><td colspan="3">F Avg. edge size Max. edge size</td></tr><tr><td>Cora</td><td>Co-authorship</td><td>2653</td><td>2591</td><td>12071</td><td>7</td><td>2.3 ± 1.9</td><td>29</td></tr><tr><td>DBLP</td><td>Co-authorship</td><td>22535</td><td>43413</td><td>117215</td><td>5</td><td>4.7 ± 6.1</td><td>143</td></tr><tr><td colspan="2">Amazon Recommendation</td><td>84893</td><td>166994</td><td colspan="2">1081994 5</td><td>3.0 ± 3.0</td><td>187</td></tr><tr><td>ACM</td><td>Co-authorship</td><td>67057</td><td>25511</td><td>59884</td><td>6</td><td>2.4 ± 1.2</td><td>32</td></tr><tr><td>arXiv</td><td>Co-authorship</td><td colspan="4">790790 1354752 6728683 7</td><td>4.0 ± 19.7</td><td>2832</td></tr></table>

Results on real-world directed hypergraphs. We report 100× mean squared errors (lower is better) over 10 different train-test splits. Note that all the reported numbers need to be multiplied by 0.01 to get the actual numbers. Please see section 5 for more details.

Table content: <table><tr><td>Method</td><td>Cora</td><td>DBLP</td><td>ACM</td><td>Amazon Office Products</td><td>arXiv</td></tr><tr><td>KL-MLP</td><td>8.94 ± 0.16</td><td>7.72 ± 0.14</td><td>8.47 ± 0.15</td><td>6.81 ± 0.16</td><td>10.87 ± 0.25</td></tr><tr><td>OT-MLP</td><td>7.45 ± 0.35</td><td>7.53 ± 0.18</td><td>7.85 ± 0.26</td><td>6.78 ± 0.24</td><td>10.01 ± 0.23</td></tr><tr><td>KLR-MLP</td><td>8.05 ± 0.22</td><td>7.35 ± 0.18</td><td>7.82 ± 0.29</td><td>6.74 ± 0.15</td><td>-</td></tr><tr><td>OTR-MLP</td><td>6.57 ± 0.43</td><td>7.24 ± 0.18</td><td>6.77 ± 0.32</td><td>6.72 ± 0.23</td><td>-</td></tr><tr><td>KL-HGNN</td><td>7.86 ± 0.25</td><td>7.17 ± 0.12</td><td>7.23 ± 0.19</td><td>6.71 ± 0.19</td><td>9.95 ± 0.25</td></tr><tr><td>KL-HyperGCN</td><td>7.95 ± 0.27</td><td>7.15 ± 0.17</td><td>7.53 ± 0.21</td><td>6.69 ± 0.17</td><td>9.99 ± 0.23</td></tr><tr><td>Soft-HGNN</td><td>5.97 ± 0.37</td><td>6.18 ± 0.37</td><td>6.02 ± 0.37</td><td>6.63 ± 0.39</td><td>8.61 ± 0.49</td></tr><tr><td>Soft-HyperGCN</td><td>6.02 ± 0.32</td><td>6.21 ± 0.35</td><td>6.04 ± 0.32</td><td>6.61 ± 0.30</td><td>8.60 ± 0.47</td></tr><tr><td>KL-DHN (ours)</td><td>7.04 ± 0.24</td><td>6.97 ± 0.22</td><td>7.16 ± 0.24</td><td>6.65 ± 0.17</td><td>9.34 ± 0.32</td></tr><tr><td colspan="4">Soft-DHN (ours) 4.87 ± 0.40 5.65 ± 0.42 5.12 ± 0.34</td><td>6.55 ± 0.33</td><td>7.69 ± 0.36</td></tr><tr><td>5.3 DISCUSSION</td><td/><td/><td/><td/><td/></tr></table>

z j ) A.3.3 ALGORITHMIC STABILITY Denote S ⊂ V × P F for an arbitrary training data set sampled with respect to distribution D. A learning algorithm for GNN, denoted as A, maps a training set S to a trained GNN f (•, Θ S ) : x → f (x, Θ S ). 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

Table content: <table/>

Combining equation 16 and equation 23 gives us|E A [W 1 (f (x, Θ S ) , y) -W 1 (f (x, Θ S ) , y)]| ≤ ηF L σ g 2 λ D 2 m

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="2">T t=1</td><td>1 +</td><td>3 2</td><td>ηDL σ g 2 λ</td><td>t-1</td><td>. (24)</td></tr><tr><td colspan="10">Therefore, we actually have the uniform algorithmic stability equation 17 holds with</td></tr><tr><td/><td/><td>β m =</td><td colspan="2">ηF L σ g 2 λ D 2 2m</td><td>T t=1</td><td>1 +</td><td>3 2</td><td>ηDL σ g 2 λ</td><td>t-1</td><td>.</td><td>(25)</td></tr><tr><td colspan="4">A.4 ADDITIONAL EXPERIMENTS</td><td/><td/><td/><td/><td/></tr><tr><td>Dataset</td><td colspan="3">GCN Soft-GCN</td><td colspan="4">GAT Soft-GAT</td><td colspan="2">Simple-GCN Soft-Simple-GCN</td></tr><tr><td>Cora</td><td>81.5</td><td>81.7</td><td/><td>82.8</td><td/><td>82.5</td><td/><td colspan="2">81</td><td>81.6</td></tr><tr><td>Citeseer</td><td>70.3</td><td>70.1</td><td/><td>70.6</td><td/><td>70.6</td><td/><td colspan="2">71.8</td><td>71.6</td></tr><tr><td>Pubmed</td><td>79</td><td>78.6</td><td/><td>78.7</td><td/><td>78.4</td><td/><td colspan="2">78.8</td><td>78.8</td></tr></table>

Accuracy on traditional graph-based SSL datasets. The experimental setting is the same as in GCN Kipf & Welling (2017) and

Table content: <table/>

Ablation study of our proposed Soft-DHN. Please see section 5 for more details.Inspired by the experimental setups of prior related works Kipf & Welling (2017);Liao et al. (2019), we tune hyperparameters using the Cora co-authorship network dataset alone. The optimal hyperparameters are fixed and then used for all the other datasets. Table5shows the list of hyperparameters used in the datasets. Prior works Kipf & Welling (2017); Liao et al. (2019) have extensively performed 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 methodsLi 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:Table6shows 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 were used to test the models. The results reported are after 200 epochs of training with a seed value of 598.

Table content: <table><tr><td colspan="3"># DHN layers # GNN layers(hops)</td><td colspan="2">Cora</td><td>DBLP</td></tr><tr><td>2</td><td/><td>2</td><td colspan="2">7.68 ± 0.24</td><td>7.98 ± 0.27</td></tr><tr><td>2</td><td/><td>1</td><td colspan="2">7.64 ± 0.25</td><td>7.93 ± 0.28</td></tr><tr><td>2</td><td/><td>0</td><td colspan="2">7.69 ± 0.27</td><td>7.98 ± 0.22</td></tr><tr><td>1</td><td/><td>0</td><td colspan="2">5.64 ± 0.32</td><td>6.45 ± 0.38</td></tr><tr><td>1</td><td/><td>1</td><td colspan="2">5.41 ± 0.35</td><td>6.26 ± 0.32</td></tr><tr><td>1</td><td/><td>2</td><td colspan="2">4.87 ± 0.40 5.65 ± 0.42</td></tr><tr><td colspan="3">A.5 DETAILS OF HYPERPARAMETERS</td><td/></tr><tr><td/><td></td><td colspan="2">1 η η . . . η η</td><td></td></tr><tr><td>C =</td><td colspan="3">   η 1 η . . . η η . . . . . . . . . . . . . . . . . .</td><td>  </td></tr><tr><td/><td colspan="3">η η η . . . η 1</td></tr></table>

List of hyperparameters used in the experiments. A set of values indicates that the corresponding hyperparameter is tuned from the set (on the validation split).

Table content: <table><tr><td colspan="2">Hyperparameter Value(s)</td><td>Hyperparameter</td><td>Value(s)</td></tr><tr><td>hidden size</td><td>16</td><td>(Sinkhorn)</td><td>0.1</td></tr><tr><td>learning rate</td><td>0.01</td><td colspan="2"># Sinkhorn iterations 100</td></tr><tr><td>dropout</td><td>0.5</td><td>η</td><td>{0, 1, 2, • • • , 40}</td></tr><tr><td>weight decay</td><td colspan="2">5 × 10 -4 λ</td><td>{1, 0.5, 0.1, 0.05, 0.01, • • • , 5 × 10 -7 , 10 -7 }</td></tr><tr><td colspan="3">A.6 SOURCES OF THE REAL-WORLD DATASETS</td><td/></tr></table>

Peer review (iclr2020):
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. I have some questions and suggestions for the authors: 1. 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. 2. 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. 3. 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.