Heterogeneous Hypergraph Embedding for Graph Classification

For each snapshot $\mathcal{G}_{e}=\{\mathcal{V}_{e},\mathcal{E}_{e},\mathbf{W}\}$ extracted from the original heterogeneous hypergraph, the laplacian matrix is computed as $\mathbf{\Delta}^{\mathcal{G}_{e}}=\mathbf{I}-\mathbf{\Theta}^{\mathcal{G}_{e}}$, where $\mathbf{\Theta}^{\mathcal{G}_{e}}=(\mathbf{D}_{v}^{\mathcal{G}_{e}})^{-\frac{1}{2}}\mathbf{H}^{\mathcal{G}_{e}}\mathbf{W}(\mathbf{D}_{e}^{\mathcal{G}_{e}})^{-1}(\mathbf{H}^{\mathcal{G}_{e}})^{T}(\mathbf{D}_{v}^{\mathcal{G}_{e}})^{-\frac{1}{2}}$. Let $\mathbf{x}^{\mathcal{G}_{e}}_{t}(v_{i})=\mathbf{v}_{i}^{t_{e}}(t)$. where $t$ is the index of elements in $\mathbf{v}_{i}^{t_{e}}$, $t=1,\cdots,C$, then $\mathbf{x}_{t}^{\mathcal{G}_{e}}=[\mathbf{v}_{1}^{\mathcal{G}_{e}}(t),\cdots,\mathbf{v}_{|\mathcal{V}|}^{\mathcal{G}_{e}}(t)]^{T}$. According to (Donnat et al., 2018), the hypergraph Laplacian $\mathbf{\Delta}^{\mathcal{G}_{e}}$ is a $|\mathcal{V}|\times|\mathcal{V}|$ positive semi-definite matrix, it can be diagonalized as:

where $\mathbf{U}^{\mathcal{G}_{e}}$ is the Fourier basis, which contains the complete set of orthonormal eigenvectors ordered by its non-negative eigenvalues $\mathbf{\Lambda}^{\mathcal{G}_{e}}=\mathbf{diag}(\lambda_{0},\cdots,\lambda_{n-1})$. According to the convolution theorem, the convolution operation $*_{hG}$ of $\mathbf{x}_{t}^{\mathcal{G}_{e}}$ and a filter $\mathbf{y}$ can be written as the Fourier inverse transform after the element-wise Hadamard product of their Fourier transforms:

Here $(\mathbf{U}^{\mathcal{G}_{e}})^{T}\mathbf{y}=[\theta_{0},\cdots,\theta_{n-1}]^{T}$ is the Fourier transform of the filter, and $\mathbf{\Lambda}_{\theta}^{\mathcal{G}_{e}}=\mathbf{diag}(\theta_{0},\cdots,\theta_{n-1})$.

However, the above operation has the following two major issues. First, it is not localized in the vertex domain (Xu et al., 2019), which cannot fully empower the convolutional operation. Secondly, eigenvectors are explicitly used in convolutions, requiring the eigen-decomposition of the Laplacian matrix for each snapshot in $G$. To address these issues, we propose to replace the Fourier basis with a Wavelet basis.

The rationale of choosing wavelet basis instead of original Fourier basis is as follows. First of all, the Wavelet basis is much sparser than the Fourier basis and most suitable for modern GPU architectures for efficient training (Neelima and Raghavendra, 2012). Moreover, by the nature of wavelet basis, the efficient polynomial approximation can be achieved more easily. Based on this feature, we thus able to further propose a polynomial approximate to the graph wavelets so that the eigen-decomposition of the Laplacian matrix is not needed anymore. Last but not least wavelets represent information diffusion process, which are very suitable for implementation of localized convolutions in the vertex domain, which has been theoretically proved and empirically validated in the recent studies (Xu et al., 2019; Donnat et al., 2018). Next, we introduce the details of altering this basis.

With the above discussion, let $\mathbf{\psi}_{s}^{\mathcal{G}_{e}}=\mathbf{U}^{\mathcal{G}_{e}}\mathbf{\Lambda}^{\mathcal{G}_{e}}_{s}(\mathbf{U}^{\mathcal{G}_{e}})^{T}$ be a set of wavelets with scaling parameter $-s$. Here $\mathbf{\Lambda}^{\mathcal{G}_{e}}_{s}=\mathbf{diag}(e^{-\lambda_{0}s},\cdots,e^{-\lambda_{n-1}s})$ is the heat kernel matrix, and $\lambda_{0}\leq\lambda_{1}\leq\cdots\leq\lambda_{n-1}$ are eigenvalues of hypergraph laplacian $\Delta^{\mathcal{G}_{e}}$. Then, the hypergraph convolution based on the Wavelet basis can be obtained from Equation (2) after replacing the Fourier basis with $\mathbf{\psi}_{s}^{\mathcal{G}_{e}}$:

where $(\mathbf{\psi}_{s}^{\mathcal{G}_{e}})^{-1}\mathbf{y}$ is the spectral transform of the filter, and $\mathbf{\Lambda}_{\beta}^{\mathcal{G}_{e}}=\mathbf{diag}(\beta_{0},\cdots,\beta_{n-1})$. In the following, we further introduce the Stone-Weierstrass theorem (Donnat et al., 2018) to approximate graph wavelets without requiring the eigen-decomposition of the Laplacian matrix, making our method much more efficient.

Note that Equation (3) still needs the eigen-decomposition of the hypergraph Laplacian matrix. As the wavelet matrix is much sparser than Fourier basis, we can easily achieve an efficient polynomial approximation according to the Stone-Weierstrass theorem (Donnat et al., 2018), which states that the heat kernel matrix $\mathbf{\Lambda}^{\mathcal{G}_{e}}_{s}$ restricted to $\left[0,\lambda_{n-1}\right]$ can be approximated by:

where $K$ is the polynomial order. $\mathbf{\Lambda}^{\mathcal{G}_{e}}=\mathbf{diag}(\lambda_{0},\cdots,\lambda_{n-1})$ contains the eigenvalues of hypergraph Laplacian $\Delta^{\mathcal{G}_{e}}$, and $r(\mathbf{\Lambda}^{\mathcal{G}_{e}})$ is the residual where each entry has an upper bound:

Then, the graph wavelet is polynomially approximated by:

Since $\mathbf{\Delta}^{\mathcal{G}_{e}}$ can be seen as a first-order polynomial of $\mathbf{\Theta}^{\mathcal{G}_{e}}$, Equation (6) can be rewritten as:

Obviously, we can replace $-s$ in $\mathbf{\Lambda}^{\mathcal{G}_{e}}_{s}$ with $s$ so that $(\mathbf{\psi}_{s}^{\mathcal{G}_{e}})^{-1}$ can be simultaneously obtained. However, Equation (7) places the parameter $s$ into the residual item, which can be ignored if we take $s$ as a small value. Therefore, we use a set of parallel parameters to approximate $(\mathbf{\psi}_{s}^{\mathcal{G}_{e}})^{-1}$ as:

With the above transform, Equation (3) can be deduced as:

When we have a hypergraph signal $\mathbf{X}^{\mathcal{G}_{e}}=[\mathbf{x}_{1}^{\mathcal{G}_{e}},\cdots,\mathbf{x}_{C}^{\mathcal{G}_{e}}]$ with $|\mathcal{V}|$ nodes and $C$ dimensional features, our hyperedge convolution neural networks can be formulated as:

where $\boldsymbol{\Lambda}_{i,j}^{m}$ is a diagonal filter matrix, and $(\boldsymbol{X}^{\mathcal{G}_{e}})^{m}\in\mathbb{R}^{|\mathcal{V}|\times C_{m}}$ is the input of the m-th convolution layer. We can further reduce the number of filters by detaching the feature transform from the convolution, and Equation (10) can be simplified as:

Where $\mathbf{W}$ is a feature project matrix. Let $\mathbf{Z}^{\mathcal{G}_{e}}\in\mathbb{R}^{|\mathcal{V}|\times C_{m+1}}$ be the output of the last layer $\mathbf{Z}^{\mathcal{G}_{e}}=(\boldsymbol{X}^{\mathcal{G}_{e}})^{m+1}$, then for all snapshots of $G=\{\mathcal{G}_{1},\cdots,\mathcal{G}_{|\mathcal{T}_{e}|}\}$, we have graph representations as:

Here $\oplus$ is the concatenation operation, and $\mathbf{Z}$ is the concatenation of $\mathbf{Z}^{\mathcal{G}_{i}},i=1,\cdots,|\mathcal{T}_{e}|$. Finally, the representation of the heterogeneous hypergraph $\mathcal{G}$ can be calculated by the summation over all its snapshots as:

where $f$ is a multilayer perceptron, and $\mathbf{Z}^{\mathcal{G}}\in\mathbb{R}^{|\mathcal{V}|\times C_{m+1}}$. In the task of node classification, $C_{m+1}$ should be equal to the number of classes. The loss function can be combined with the cross-entropy error over all labeled examples and the regularizer on projection matrices:

where $\mathcal{V}_{l}$ is the set of labeled nodes, $\mathbf{Y}_{v,i}$ is the label value of node $v$ in terms of the category $i$. If node $v$ belongs to category $i$, $\mathbf{Y}_{v,i}=1$, otherwise, 0. $\eta$ is a trade-off parameter of the regularizer. Here, we follow (Zhao et al., 2018) and use the trace of $\mathbf{M}_{t_{e}}^{T}\mathbf{M}_{t_{e}}$ as the regular term, which can be also replaced by the $L2$ regularization.

Our method can achieve more profound learning results because we leverage the power of $\mathbf{\Theta}^{\mathcal{G}_{e}}$ for higher-order relations in hypergraphs, and $\mathbf{\Theta}^{\mathcal{G}_{e}}$ can be treated as an adjacency matrix of the hypergraph.

As previously mentioned, we use $\mathbf{H}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{E}|}$ to denote the presence of nodes in different hyperedges. If $v\in e$, we have $\mathbf{H}(v,e)=1$, and otherwise, the corresponding entries are set as $0$. In nature, $\mathbf{H}$ indicates the relations between nodes and hyperedges, then we can use $\mathbf{H}\mathbf{H}^{T}$ to describe connections between nodes. A normalized version can be written like: $\mathbf{H}\mathbf{W}\mathbf{D}_{e}^{-1}\mathbf{H}^{T}$. In order to remove self-loops in hypergraphs, we change the above formula by:

Then a normalized version of Equation (15) can be rewritten by:

From the above formula, we can find $\mathbf{\Theta}$ has the similar meaning as the adjacency matrix.

In order to elaborate on the advantages of our method, we first introduce a prior work (Chen et al., 2020b) on hypergraph neutral network, and then we discuss the relationships between our work and prior work. A simplified hypergraph convolution can be generated via extending simple graph convolution to the hypergraph. Recall that the typical GCN framework in simple graphs is defined as:

Here $\mathbf{D}$ contains all nodes’ degree of the graph. $\mathbf{A}$ is the adjacency matrix. Following Observation 2, we can effectively model hypergraph convolution in a similar way:

Here $\mathbf{X}^{l}$ is the signal at the $l$-th layer, and $\mathbf{W}$ is a feature projection matrix. The traditional convolutional neural network for simple graphs is a special case of this work because the Laplacian $\Delta$ can be degenerated as the simple graph Laplacian.

When the filter $\mathbf{\Lambda}$ in Equation (11) is initialized from value $1$, it is close to an identity matrix $\mathbf{I}$. Let $K=1$ and $K^{{}^{\prime}}=0$ for Equation (7) and Equation (8) respectively, then Equation (11) degenerates to Equation (18). That means we employ the polynomial of $\mathbf{\Theta}$ to extend prior works based on the hypergraph theory only, and this extension makes our method more profound for node representation learning. Since $\mathbf{\Theta}$ actually serves a similar role as an adjacency matrix, the power of $\mathbf{\Theta}$ can learn higher-order relations for hypergraphs. Furthermore, the filter $\mathbf{\Lambda}$ improves the performance in one more step via suppressing trivial components and magnifying rewarding components.

The complexity of Equation (11) is $\mathcal{O}(N+pq)$ where $N$ is the number of nodes, $p$ and $q$ are input dimensions and output dimensions respectively. Inspired by the formula (18) and (11), the complexity of our model can be further reduced to $\mathcal{O}(pq)$ with a simplified version:

where $K$ is the polynomial approximation order, $\mathbf{W}\in\mathbb{R}^{p\times q}$ is feature transformation matrix.

• •

  Pubmed¹¹1 https://github.com/jcatw/scnn/tree/master/scnn/data/Pubmed-Diabetes : The Pubmed dataset (Sen et al., 2008) contains 19, 717 academic publications with 500 features. These publications are treated as nodes and their citation relationships are treated as 44,338 links. Each node falls into one of three classes (three kinds of Diabetes Mellitus).

• •

  Cora²²2https://relational.fit.cvut.cz/dataset/CORA : The Cora dataset (McCallum et al., 2000) contains 2,708 published papers in the area of machine learning, which are divided into 7 categories (case based, genetic algorithms, neural networks, probabilistic methods, reinforcement learning, rule learning, and theory). There are 5,429 citation links in total. The paper nodes have 1,443 features.

• •

  DBLP³³3http://web.cs.ucla.edu/ yzsun/Publications.html: The DBLP dataset (Sun et al., 2011) is an academic network from four research areas. There are 14,475 authors, 14,376 papers, and 20 conferences, among which 4,057 authors, 20 conference and 100 papers are labeled with one of the four research areas (database, data mining, machine learning, and information retrieval). We use this dataset to predict the research areas of authors.

Note that the above four datasets cover all kinds of hypergraph heterogeneities we have mentioned: homogeneous simple graph with heterogeneous hypergraphs (Pubmed and Cora), and heterogeneous simple graph with heterogeneous hypergraphs (DBLP).

We choose six state-of-the-art graph and hypergraph embedding methods as baselines:

• •

  Hypergraph Embedding Methods

  • –

    HyperEmbedding (Zhou et al., 2007). This method selects the top-$k$ eigenvectors derived from the Laplacian matrix of the hypergraph as the representation of the hypergraph.

  • –

    HGNN (Feng et al., 2019). It is a convolution network for hypergraphs based on the Fourier basis. The reason why we choose it as our baseline is that their reported performance exceeds a variety of hot methods such as GCN (Kipf and Welling, 2016), Chebyshev-GCN (Defferrard et al., 2016), and Deepwalk (Perozzi et al., 2014).

• •

  Simple Embedding Methods

  • –

    PME (Chen et al., 2018). It is a heterogenous graph embedding model based on the metric learning to capture both first-order and second-order proximities in a unified way. It learns embeddings by firstly projecting vertices from object space to corresponding relation space and then calculates the proximity between projected vertices.

  • –

    HHNE (Wang et al., 2019). This method learns node embeddings in Hyperbolic space instead of Euclidean space. It follows the idea of word2vec (Mikolov et al., 2013) and generates the corpus via bias random walk on the networks.

  • –

    metapath2vec (Dong et al., [n.d.]). It extends the Deepwalk model to learn representations on heterogeneous networks through meta path guided random walks.

  • –

    GWNN (Xu et al., 2019). It is a graph convolution network based on the Wavelet basis, but it is designed for simple homogeneous graphs. It was reported to beat GCN, Spectral CNN (Bruna et al., 2014), MoNet (Monti et al., 2017), and achieved the best results on homogeneous simple graphs.

The optimal hyper-parameters in all the models are selected by the grid search method on the validation set. Our model achieves its best performance with the following setup. There are two convolution layers. The activation function of the first layer is ReLU, and the second layer is Softmax. The feature dimension of the hidden layer is set as 64, with a drop rate of 0.5. We use Adam optimizer with learning rate 0.001, regularization coefficient 0.0001, and 400 epochs. For PME, metapath2vec, and HHNE, we choose three meta-paths on DBLP dataset: P-C (paper-conference), P-A (paper-author), and A-P-A. (paper-conference-author). Other datasets have homogeneous simple graphs so we just use V-V (vertex-vertex) as the meta-path. For PME, we set $m=100$, and the number of negative samples for each positive edge is set $K=10$. The initial nodes features are generated from nodes’ attributes provided by these datasets.

We define the following four types of hyperedges to construct the corresponding heterogeneous hypergraphs for the datasets:

• •

  Neighbor-based hyperedges. We first obtain each node’s $\phi$-hop neighbors and connect them in one hyperedge. $\phi$ is set as 3 in our experiments. All these hyperedges belong to the same hyperedge type if the simple graph is homogeneous. If the simple graph is heterogeneous, a node has different types of neighbors following different meta-paths, and thus we can generate different types of hyperedges.

• •

  Attribute-based hyperedges. Let $\mathcal{A}$ denote all the discrete attributes. For each attribute $a\in\mathcal{A}$, it has $c_{a}$ values. Then, we build a type of hyperedges for each attribute $a$, and each hyperedge connects the nodes sharing the same attribute value. So there are $c_{a}$ hyperedges generated for attribute $a$. Each hyperedge type is treated as a hypergraph snapshot, and we finally generate $|\mathcal{A}|$ hypergraph snapshots accordingly.

• •

  Cluster-based hyperedges. Given each node’s feature vectors, we first calculate the cosine similarity between each pair of nodes and obtain several clusters by K-means. Then each cluster serves as a hyperedge. All the hyperedges belong to the same hyperedge type.

• •

  Community-based hyperedges. We use the Louvain algorithm (Blondel et al., 2008) to discover communities in the corresponding simple graph via modularity maximization. Then each community is treated as a hyperedge. All these hyperedges belong to the same hyperedge type.