Year: 2021

Abstract:
As a powerful tool for modeling the complex relationships, hypergraphs are gaining popularity from the graph learning community. However, commonly used algorithms in deep hypergraph learning were not specifically designed for hypergraphs with edge-dependent vertex weights (EDVWs). To fill this gap, we build the equivalency condition between EDVW-hypergraphs and undirected simple graphs, which enables utilizing existing undirected graph neural networks as subroutines to learn high-order interactions induced by EDVWs of hypergraphs. Specifically, we define a generalized hypergraph with vertex weights by proposing a unified random walk framework, under which we present the equivalency condition between generalized hypergraphs and undigraphs. Guided by the equivalency results, we propose a Generalized Hypergraph Convolutional Network (GHCN) architecture for deep hypergraph learning. Furthermore, to improve the longrange interactions and alleviate the over-smoothing issue, we further propose the Simple Hypergraph Spectral Convolution (SHSC) model by constructing the Discounted Markov Diffusion Kernel from our random walk framework. Extensive experiments from various domains including social network analysis, visual objective classification, and protein fold classification demonstrate that the proposed approaches outperform state-of-the-art spectral methods with a large margin.

text: As a powerful tool for modeling the complex relationships, hypergraphs are gaining popularity from the graph learning community. However, commonly used algorithms in deep hypergraph learning were not specifically designed for hypergraphs with edge-dependent vertex weights (EDVWs). To fill this gap, we build the equivalency condition between EDVW-hypergraphs and undirected simple graphs, which enables utilizing existing undirected graph neural networks as subroutines to learn high-order interactions induced by EDVWs of hypergraphs. Specifically, we define a generalized hypergraph with vertex weights by proposing a unified random walk framework, under which we present the equivalency condition between generalized hypergraphs and undigraphs. Guided by the equivalency results, we propose a Generalized Hypergraph Convolutional Network (GHCN) architecture for deep hypergraph learning. Furthermore, to improve the longrange interactions and alleviate the over-smoothing issue, we further propose the Simple Hypergraph Spectral Convolution (SHSC) model by constructing the Discounted Markov Diffusion Kernel from our random walk framework. Extensive experiments from various domains including social network analysis, visual objective classification, and protein fold classification demonstrate that the proposed approaches outperform state-of-the-art spectral methods with a large margin.

heading: 1 INTRODUCTION
text: Hypergraphs, whose edges link to the arbitrary number of vertices to model high-order relationships, attract much attention recently from researchers in the graph learning community (Feng et al., 2019; Jiang et al., 2019; Zhang et al., 2021). The topology of hypergraph can be considered to be embedded in vertex weights, which represents the connection strength between hyperedges and vertices (Chitra & Raphael, 2019). The vertex weights can be divided into two categories, edgeindependent and edge-dependent (Chitra & Raphael, 2019; Hayashi et al., 2020), depending on whether the vertex weights are related to the incident hyperedges or not (EDVW-hypergraph implies that each vertex v is assigned a weight qe(v) ∈ R for each incident hyperedge e). Many hypergraph neural networks have been proposed (Feng et al., 2019; Jiang et al., 2019; Yadati, 2020; Huang & Yang, 2021) to handle hypergraphs with edge-independent vertex weights (EIVW-hypergraph). However, rigorous study for hypergraphs with edge-dependent vertex weights (EDVW-hypergraph) is still lacked, though they enjoy stronger expressive power (Ding & Yilmaz, 2010; Huang et al., 2010; Li et al., 2018a; Zhang et al., 2018).
In this work, we are devoted to spectral-based methods, which are considered to be robust and to allow for simple model property analysis (Wu et al., 2020). Unfortunately, the spectral theory of EDVW-hypergraph has not been well established. A recent work (Chitra & Raphael, 2019) provides the spectral theory for EDVW-hypergraphs, and indicates that the defined EDVW-hypergraphs is equivalent to digraphs. Though digraph convolutional networks can be directly used for EDVWhypergraphs, most existing convolutional algorithms for digraphs are more or less related to undirected graphs, e.g., (Monti et al., 2018; Li et al., 2020; Ma et al., 2019; Tong et al., 2020). Essentially, they transform digraphs to undigraphs with various techniques due to the challenges of directed graph Laplacian. In addition, key theoretical analysis of digraph convolutional networks properties,
such as expressive power (Xu et al., 2019) or the performance of models in deep layers (Li et al., 2018b), yet remains open.
An arguably more succinct way for EDVW-hypergraph learning is to use undigraph convolutional networks. Compared with digraphs, the undigraph convolutional networks have been extensively studied and there exist various effective strategies for analyzing their properties, to name a few (Kipf & Welling, 2017; Chen et al., 2020; Zhu & Koniusz, 2021). Furthermore, one can take established techniques on undigraphs as a subroutine for hypergraph learning, which would largely ease hypergraph learning in real-world scenarios. It remains unclear, however, whether EDVW-hypergraphs can be made equivalent to undigraphs in a principled way, thereby hindering this promising prospect.
In this paper, we focus on constructing the equivalency condition between hypergraphs and undigraphs. This makes it possible to utilize undigraphs as low-order encoders of hypergraphs, and thus enabling hypergraph learning directly from the equivalent undirected graphs by means of undigraph convolutional networks. Along this route, we have made the following contributions:
1) We define a generalized hypergraph capturing EDVWs via designing a two-step unified random walk framework. In addition, we construct the equivalency conditions to fill the gap between the generalized hypergraph and corresponding undigraph.
2) We present a unified Laplacian from the equivalency conditions and propose two spectral convolution models (GHCN, SHSC) for EDVW-hypergraphs learning. We analyze the over-smoothing issues (Li et al., 2018b) based on their spectral properties deduced from equivalency conditions.
3) Extensive experiments across various domains (social network analysis, visual objective classification and protein modeling) demonstrate the effectiveness of the proposed methods (GHCN and SHSC) for both EIVW-hypergraph and EDVW-hypergraph learning tasks. Notably, we are first to adopt EDVW-hypergraphs for protein structures and obtain significant performance boost.
Due to space limit, more discussions on related works are deferred to Appendix A.

heading: 2 THE THEORY OF EQUIVALENCY
text: edge-dependent otherwise (Chitra & Raphael, 2019). If qe(u) equals to 1 for all linked u and e ,Q would reduce to the binary incident matrix H, which is widely used to represent the structure of hypergraph (Zhou et al., 2006; Carletti et al., 2021). The matrix Q can also be viewed as a weighted incident matrix. Note that a graph is a special case of a hypergraph with hyperedge degree |e| = 2. We say a hypergraph is connected when its unweighted clique graph (Chitra & Raphael, 2019) is
connected and we assume hypergraphs are connected. Throughout this paper, equivalency refers to equivalency between hypergraphs and undigraphs if not otherwise specified.

heading: 2.1 UNIFIED RANDOM WALK AND GENERALIZED HYPERGRAPHS
text: Traditionally, hypergraph random walk is defined by a two-step manner (Zhou et al., 2006; Ducournau & Bretto, 2014) (Fig. 2). Then, Chitra & Raphael (2019) raise a new random walk involving the edge-dependent vertex weights into the second step and build the equivalency between EDVWhypergraphs and digraphs. However, due to the limitation of their hypergraph definition, they fail to answer whether the EDVW-hypergraphs can be equal to undigraphs. So in this part, we integrate the existing two-step random walk methods (Chitra & Raphael, 2019; Carletti et al., 2020; 2021) to obtain a comprehensive unified random walk framework with the vertex weights added into the first step, based on which we further define a generalized hypergraph.
Definition 1 (Unified Random Walk on Hypergraphs) The unified random walk on a hypergraph H is defined in a two-step manner: Given the current vertex u, Step I: choose an arbitrary hyperedge e incident to u, with the probability
p1 = w(e)
∑ v∈V Q2(v, e)ρ( ∑ v∈V Q2(v, e))Q1(u, e)∑
e∈E w(e) ∑ v∈V Q2(v, e)ρ( ∑ v∈V Q2(v, e))Q1(u, e) ; (1)
Step II: choose an arbitrary vertex v from e, with the probability
p2 = Q2(v, e)∑ v∈V Q2(v, e) , (2)
where w(e) denotes the hyperedge weight; Q1(u, e) denotes the contribution of vertex u to hyperedge e in the first step while Q2(v, e) represents the contribution of vertex v to hyperedge e in the second step; and ρ(·) is a real-valued function, for example, a power function (·)σ .
Suppose δ(e) := ∑ v∈V Q2(v, e) is the degree of hyperedge, and d(v) :=∑
e∈E w(e)δ(e)ρ(δ(e))Q1(v, e) is the degree of vertex v. The transition probability of our unified random walk on a hypergraph from vertex u to vertex v is:
P (u, v) = ∑ e∈E w(e)Q1(u, e)Q2(v, e)ρ(δ(e)) d(u) . (3)
Here, P (u, v) can be written in a |V| × |V| matrix form: P = D−1v Q1Wρ(De)Q>2 , where Dv , De are diagonal matrices with entries Dv(v, v) = d(v) and De(e, e) = δ(e), respectively. ρ(De) represents the function ρ acting on each element of De. Notably, the ρ does not always work properly. We present the failure conditions in the Appendix G.4. More detailed intuition of our purpose to design P (u, v) can be found in Appendix B.2.
Under our framework, the existing hypergraph random walk (Zhou et al., 2006; Chitra & Raphael, 2019; Carletti et al., 2020; 2021) can be seen as special cases with specific p1, p2 (see Appendix B.3). The definition of our framework is lazy since it allows self-loops (P (v, v) > 0). The non-lazy version is provided in Appendix C. Based on the framework, we define the generalized hypergraph for constructing equivalency between EDVW-hypergraphs and undigraphs as follows.
Definition 2 (Generalized hypergraph) A generalized hypergraph is a hypergraph associated with the unified random walk in Definition 1, denoted as H(V, E ,W,Q1,Q2). Here, Q1, Q2 are vertex weights matrices, each of which can be edge-independent or edge-dependent.

heading: 2.2 THE EQUIVALENCY BETWEEN HYPERGRAPHS AND UNDIGRAPHS
text: In this part, we provide the condition under which the generalized hypergraph is equivalent to weighted undirected clique graph. By establishing the equivalency, we can view graphs as loworder encoders of EDVW-hypergraphs, so any undigraph technique can be used as a subroutine for hypergraph learning.
The clique graph of H(V, E ,W,Q1,Q2) is denoted as GC , which is a unweighted graph with vertices V and edge set {(u, v) : u, v ∈ e, e ∈ E}. Actually, GC turns all hyperedges into cliques. We first present the definition of the equivalency in connection with Markov chains.
Definition 3 (Chitra & Raphael (2019)) Let M1,M2 be the Markov chains with the same finite state space, and let PM1 and PM2 be their probability transition matrices, respectively. M1,M2 are equivalent if PM1u,v = P M2 u,v for all states u and v.
The equivalency between digraph and hypergraph is straightforward and we defer to Appendix E. On the other hand, it is easy to understand that any simple undigraph can be constructed as a special generalized hypergraph, while the converse is not necessarily true. We provide a counterexample in Appendix G.4. This result implies that undigraph convolutional networks can not trivially be extended to generalized hypergraphs. So, we give one of the implicit equations for formulating the equivalency problem to explore the explicit equivalency conditions.
Lemma 1 Let H(V, E ,W,Q1,Q2) denote the generalized hypergraph in Definition 2. Let F(Q1,Q2)(u, v) :=∑ e∈E w(e)ρ(δ(e))Q1(u, e)Q2(v, e) and T(Q)(u) :=∑ e∈E w(e)δ(e)ρ(δ(e))Q(u, e). When Q1,Q2 satisfies the following equation
T(Q2)(u)T(Q1)(v)F(Q1,Q2)(u, v) = T(Q2)(v)T(Q1)(u)F(Q1,Q2)(v, u),∀u, v ∈ V (4)
there exists a weighted undirected clique graph GC such that a random walk onH is equivalent to a random walk on GC with edge weights ω(u, v) = T(Q2)(u)F(Q1,Q2)(u, v)/T(Q1)(u) if T(Q1)(u) 6= 0 and 0 otherwise.
The proof can be found in Appendix G.2. Next, we derive the explicit condition under which random walks on hypergraphs are equivalent to undigraphs.
Theorem 1 (Equivalency between generalized hypergraph and weighted undigraph) Let H(V, E ,W,Q1,Q2) denote the generalized hypergraph in Definition 2. When H satisfies any of the condition bellow:
Condition (1) Q1 and Q2 are both edge-independent; Condition (2) Q1 = kQ2 (k ∈ R), there exists a weighted undirected clique graph GC such that a random walk on H is equivalent to a random walk on GC .
It is easy to verify that conditions (1) and (2) satisfy equation 4 (proof in Appendix G.3). This theorem brings insights from three aspects: i) Hypergraph foundation. The equivalency itself is a fundamental problem and remains open before this work (Agarwal et al., 2006; Chitra & Raphael, 2019). Our conclusion provides more adaptive and explores more essential conditions thanks to the unity of our random walk and the generalization of hypergraph defined (Figure 3). Notably, Chitra & Raphael (2019) shows that the equivalency condition is: Q1 = H and Q2 is edge-independent, which can be viewed as a special case of the condition (1), while Theorem 1 implies the equivalency is not only related to the dependent relationships between vertex weights and edges, but also to whether the vertex weights used in the first and second step of the unified random walk are proportional. Furthermore, thanks to the introduced Q1 in the generalized hypergraph, we can obtain the equivalency between EDVW-hypergraph and undigraph (i.e. condition (2) ), filling an important gap in the equivalency theory of EDVW-hypergraph. ii) Providing a theoretical basis for hypergraph applications. The condition (2), containing both the edge-independent vertex weights and edge-dependent vertex weights cases which match different hypergraph applications (Ding & Yilmaz, 2010; Zeng et al., 2016; Zhang et al., 2018), provides those with theoretical explanations. The condition (2) also reveals that the existing random walks (Carletti et al., 2020; 2021) on hypergraphs are equivalent to undigraph. iii) Hypergraph learning. The equivalent undigraphs can be viewed as the lower-order encoders of hypergraphs. Thus, one can obtain hypergraph representations directly by exploiting the undigraph learning methods. Especially, the condition (2), which implies that an EDVW-hypergraph can be equivalent to an undigraph, gives the theoretical guarantee for learning hypergraphs without losing edge-dependent vertex weights via undigraph neural networks. Next, we provide the spectral theory for the generalized hypergraphs.

heading: 2.3 GENERALIZED HYPERGRAPH LAPLACIAN AND ITS SPECTRAL PROPERTIES
text: To build a bridge between spectral convolution and equivalency, we derive the equivalent undirected weighted graph Laplacian based on Lemma 1 and Thm 1. Then the graph Laplacian can be considered as the Laplacian of generalized hypergraph. Starting from the deduced Laplacian, it is direct and convenient to construct the spectral convolution for hypergraphs. Formally, we have
Corollary 1 Let H(V, E ,W,Q1,Q2) be the generalized hypergraph in Definition 2. Let D̂v be a |V| × |V| diagonal matrix with entries D̂v(v, v) := d̂(v) := ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(v, e). No matter H satisfies condition (1) or condition (2) in Thm. 1, it obtains the unified explicit form of stationary distribution π and Laplacian matrix L as:
π = 1>D̂v
1>D̂v1 and L = I− D̂−1/2v Q2Wρ(De)Q>2 D̂−1/2v . (5)
There are two observations from Corollary 1: (i) This stationary distribution is different from the classical π(v) = d(v)/ ∑ v d(v) (Zhou et al., 2006), which depends on the vertex degree d(v). Our π(v) is related to d̂(v), which means that we cannot trivially extend from classical theory. The detailed proof is deferred to Appendix G.6; (ii) Both π and L are only related to Q2, independent of Q1, implying possible information loss of Q1 under the setting required an asymmetrical two-steps random walk(i.e. Q1 6= Q2) to construct a hypergraph. Meanwhile, L can be viewed as a normalization Laplacian led by the equivalent undigraph GC with adjacency matrix Q2Wρ(De)Q>2 , based on which we can design the EDVW-hypergraph spectral convolutions.
Corollary 1 implies that no matter Q1, Q2 are both edge-independent or Q1 = Q2, we can directly use the Laplacian matrix L to analyze the spectral properties. The spectral properties of Laplacian (Chung & Graham, 1997) are vital in the research of graph neural networks to design a stable and effective convolution operator. Therefore, we deduce two important conclusions concerning eigenvalues of L as the basic theory of Laplacian application under the equivalency conditions in Thm. 1. One claims the eigenvalues range of L is [0, 2] (details in Appendix G.7), and the other describes the rate of convergence of our unified random walk listed bellow (see Appendix G.8)
Corollary 2 LetH(V, E ,W,Q1,Q2) be the generalized hypergraph in Definition 1. WhenH satisfies any of two conditions in Thm. 1, let L and π be the hypergraph Laplacian matrix and stationary distribution from Corollary 1. Let λH denote the smallest nonzero eigenvalue of L. Assume an initial distribution f with f(i) = 1 (f(j) = 0,∀ j 6= i) which means the corresponding walk starts from vertex vi. Let p(k) = fPk be the probability distribution after k steps unified random walk where P denotes the transition matrix, then p(k)(j) denotes the probability of finding the walker in vertex vj after k steps. We have:∣∣∣p(k)(j)− π(j)∣∣∣ ≤ √ d̂(j)
d̂(i) (1− λH)k. (6)
For hypergraph learning, Corollary 2 implies that the spectral convolution deduced from the Laplacian in Corollary 1 might suffer from the over-smoothing issue (Zhu & Koniusz, 2021). Appendix F.4 gives a theoretical perspective for analyzing the over-smoothing issue based on this Corollary, which further inspires the design of convolutions in Section 3 to alleviate the issue.

heading: 3 TWO SPECTRAL CONVOLUTIONS FOR HYPERGRAPHS
text: Intuitively, there are two possible routes for designing EDVW-hypergraph neural networks: 1. message passing; 2. spectral-based methods. Message passing has proved to be a powerful tool for extracting information from hypergraphs or graphs. However, on the one hand, researchers usually adopt heuristic ideas to design message-passing models, leading to a lack of theoretical guarantees (Huang & Yang, 2021). This makes it difficult to analyze properties of corresponding neural networks directly, such as over-smoothing issue (Li et al., 2018b). On the other hand, spectral-based methods not only have a solid foundation in graph signal processing (Kipf & Welling, 2017; Feng et al., 2019), but also effectively inspires the design of message passing techniques (Xu et al., 2019).
Here, we design two hypergraph spectral convolutions for hypergraph learning based on equivalency conditions in Thm. 1. As the Laplacian L enjoys the same formula under any of the two equivalency conditions, algorithms deduce by L would be adaptive to any generalized hypergraph satisfied Thm. 1, including EIVW-hypergraph and EDVW-hypergraph.

heading: 3.1 GENERALIZED SPECTRAL HYPERGRAPH CONVOLUTION
text: We denote K as Q2Wρ(De)Q>2 for expression simplicity. Then the unified hypergraph Laplacian matrix L in Corollary 1 can be expressed as L = I − D̂−1/2v KD̂−1/2v . Similar to Defferrard et al. (2016), we approximate the convolutional kernel with Chebyshev polynomial to avoid eigenvalue decomposition of L. Finally, the following Generalized Hypergraph Convolutional Network (GHCN) is obtained by introducing the re-normalization technique (Kipf & Welling, 2017):
X(l+1) = ψ(T̃X(l)Θ), (7)
where T̃ := D̃−1/2v K̃D̃ −1/2 v , and K̃ = K + I can be regarded as the weighted adjacency matrix of the equivalent undigraph with self-loops, and D̃(v, v) = ∑ u∈V K̃(v, u). Θ is a learnable parameter matrix and ψ(·) denotes an activation function. More details of derivation can be found in Appendix F.1. Most of existing hypergraph Laplacians (Zhou et al., 2006; Carletti et al., 2020; 2021) can be viewed as special forms of the Laplacian matrix L and can be derived the special convolutions of GHCN. The biggest advantage of GHCN is that it can handle both EIVW-hypergraphs and EDVWhypergrpahs. Besides, the unity of random walk makes it possible to aggregate more fine-grained information. Note that HGNN (Feng et al., 2019) can be viewed as a specific case of GHCN without the re-normalization trick (ρ(·) = (·)−1, Q = H). However, Corollary 2 indicates that initial signals or features intend to converge to a certain vector, causing vertices hard to distinguish between each other. This implies that GHCN also suffers from over-smoothing issue (Li et al., 2018b), which limits the depth of the convolution model and hinders the aggregation of long-range information. In fact, the analysis also suggests that HGNN (Feng et al., 2019) suffers from the over-smoothing issue. Next, we would propose a new spectral convolution to alleviate this issue.

heading: 3.2 A SIMPLE SPECTRAL CONVOLUTION BASED ON MARKOV DIFFUSION KERNEL
text: In order to aggregate long-range information, we propose the discounted Markov Diffusion process to aggregate the information of vertices and propose a new convolutional architecture for hypergraphs.
Discounted Markov Diffusion Kernel for Hypergraphs. A diffusion process on a generalized hypergraph can be understood as a process of information extracting among vertices. To generate the underlying feature map (Z(t)), we first utilize the transition probabilities of the Markov chain in Definition 1 to design a discounted average visiting rate: v̄ik(t) = 1t ∑t τ=1 α
τ Pr(s(τ) = k|s(0) = i), where t ∈ Z++. Notably, we introduce a discount factor α ∈ (0, 1] to exponentially weaken the long-step transition probabilities from vertex i to vertex k. Specially, we set v̄ik(0) = 1 if and only if i = k, otherwise v̄ik(0) = 0. Assume that v̄i(t) = (v̄i1(t), · · · , v̄i|V|(t))>. Then, we adopt the diffusion distance dij(t) = ‖v̄i(t)− v̄j(t)‖22 =
∥∥Z>(t)(v̄i(0)− v̄j(0))∥∥22 proposed in Pons & Latapy (2005) to generate our discounted Markov diffusion kernel KMD(t) = Z(t)Z>(t), where Z(t) = ∑t τ=1 ατ t P τ can be viewed as the weighted sum of the transition matrix (derivation in Appendix F.2). The intuition behind this diffusion distance is that if two vertices diffuse similarly based on hypergraph random walk, we are supposed to take them similar. Then, the influence of the two vertices to other vertices in the hypergraph is considered in a similar manner.
Simple Hypergraph Spectral Convolution (SHSC). Inspired by the diffusion kernel-based GCNNs from Zhu & Koniusz (2021), based on our discounted Markov diffusion kernel, we propose a Simple Hypergraph Spectral Convolution (SHSC) as follows:
Y = ψ (( β
K∑ k=1 αk K T̃k + (1− β)I
) XΘ ) . (8)
Recall T̃ is the transition matrix we used in equation 7, ψ(·) is the activation function to map the node representation of output, and Θ is the parameter of filter to be learned during training. SHSC is able to balance the global information aggregation and the vertex’s own information by introducing a hyperparameter β ∈ [0, 1] to control the self-loops (T̃)0 = I. Through the discounted Markov Diffusion process, our SHSC could gain stronger local and weaker global information, thereby improving the expressive power in the deep layers. On the other hand, SHSC uses only one linear layer, which greatly improves the computational efficiency and effectively alleviates the overfitting problem. Actually, SHSC is a spatial-based model while we can analyze it from a spectral-based perspective, as SHSC can be viewed as a polynomial filter with specific coefficients (see Appendix F.3). Finally, we study why SHSC can relieve over-smoothing. Specifically, we utilize Corollary 2 to generate a lower-bounded quantity of the defined over-smoothing energy, based on which we show that SHSC can relieve the over-smoothing issue compared to multi-layer GHCNs (details in Appendix F.4).
4 EMPIRICAL STUDIES
In this section, we evaluate our proposed methods on four tasks: citation network classification, visual object classification, protein quality assessment (regression), and fold classification. For simplicity, we set ρ(·) to be a power function (·)σ (σ is a hyper-parameter) and additional experiments to compare the performance with different ρ is deferred to Appendix I.10. The weight matrix of edges, we set, to be an identity matrix by default in our GHCN and SHSC models. Notably, although GHCN and SHSC are designed for EDVW-hypergraph learning, they work for EIVWhypergraph as well thanks to the unified Laplacian in Corollary 1. In our experiments, citation network classification belongs to EIVW-hypergraph
learning tasks, and visual object classification and protein learning are EDVW-hypergraph learning tasks. For baselines designed for EIVW-hypergraph, we replace Q1,Q2 with H.
Due to space limitations, we defer additional experimental results on Over-smoothing Analysis, Hyper-parameter Sensitivity Analysis, and Ablation Analysis to Appendix I.6, I.7, I.9, respectively. The insights are: 1) SHSC can efficiently alleviate over-smoothing; 2) The hyper-parameters σ, β, α are sensitive at a relatively large range but insensitive in a small range of the performance optimum; 3) The re-normalization trick and edge-dependent vertex weights are both effective. In addition, we provide the computational complexity analysis for our models in Appendix I.11.

heading: 4.1 CITATION NETWORK CLASSIFICATION
text: This is a semi-supervised node classification task. The datasets include co-authorship and co-citation datasets: PubMed, Citeseer, Cora (Sen et al., 2008), and DBLP (Rossi & Ahmed, 2015). We adopt the same public datasets (https://github.com/malllabiisc/HyperGCN) and train-test
splits of Yadati et al. (2019). Note these datasets satisfy the condition that Q1 = Q2 = H. So this experiment can be regarded as a special case of the applications of our models. For baselines, we include Multi-layer perceptron(MLP), HNHN (Dong et al., 2020), HGAT (Ding et al., 2020), UniGNN (Huang & Yang, 2021), and two recent spectral-based hypergraph convolutional neural networks (HGCNNs): HGNN (Feng et al., 2019) and HyperGCN (Yadati et al., 2019).
Comparison with SOTAs. As shown in Table 19, the results successfully verify the effectiveness of our models and achieve a new SOTA performance across all five datasets. Notably, both GHCN and SHSC have an
average performance improvement of 4.88% and 5.83% over the previous spectral-based methods, respectively. On the other hand, SHSC achieves the best result at a deep layer and gains better performance than GHCN on most datasets, which demonstrates the benefits of deep model and the long-range information in hypergraphs. It’s worth noting that our methods gain superior performance on disconnected datasets compared to HGNN. HGNN shows poor performance on disconnected datasets, mainly due to the row in the adjacency matrix of equivalent undigraph corresponding to an isolated point is 0, resulting direct loss of its vertex information (an example can see Fig. 4 in appendix). And our methods utilize the renormalization trick, which can maintain the features of isolated vertices during aggregation. Another important observation is that HyperGCN has a high standard deviation, revealing its poor generalization. Conversely, SHSC has lower bias and standard deviation than others, showing better generalization.

heading: 4.2 VISUAL OBJECT CLASSIFICATION
text: This experiment is about semi-supervised learning. We employ two public benchmarks: Princeton ModelNet40 dataset (Wu et al., 2015) and the National Taiwan University (NTU) 3D model dataset (Chen et al., 2003) to evaluate our methods. We follow HGNN (Feng et al., 2019) to preprocess the data by MVCNN (Su et al., 2015) and GVCNN (Feng et al., 2018). Finally, we use the datasets provided by its public Code (https://github.com/iMoonLab/HGNN). More details can be found in Appendix I.4.
Results. Table 2 depicts that our methods significantly outperform the image-input or point-input methods. These results demonstrate that our methods can capture the similarity of objects in the feature space to improve the performance of the classification task. Table 20 compares our methods with HGNN and uniGNN on NTU and ModelNet40. From the results, we can see that our methods outperform HGNN on both single modality and multi-modality (BOTH) datasets and SHSC achieves much better performance on multi-modality compared with others. These results reveal that our SHSC has the advantage of combining such multi-modal information through concatenating the weighted incidence matrices (Q) of hypergraphs, which means merging the multi-level hyperedges.

heading: 4.3 PROTEIN QUALITY ASSESSMENT (QA) AND FOLD CLASSIFICATION
text: Protein QA and fold classification are vital for mining the property of proteins. However, to the best of our knowledge, most researchers represented a protein as a sequence or a simple graph (Baldassarre et al., 2020; Hermosilla et al., 2021) in the deep learning area. So we’d like to investigate whether hypergraphs are better than simple graphs for protein modeling, and the following results confirm this conjecture.
Protein hypergraphs. A protein is a chain of amino acids (residues) that will fold to a 3D structure. To simultaneously model protein sequence and spatial structure information, we build sequence hyperedges and distance hyperedges: we choose τ consecutive amino acids (vi, vi+1, · · · , vi+τ ) to form a sequence hyperedge, and choose amino acids whose spatial Euclidean distance is less than
the threshold > 0 to form a spatial hyperedge, where vi(i = 1, · · · , |S|) represents the i-th amino acids in the sequence. Appendix I.5 contains more details.
Protein Quality Assessment (QA). Protein QA is used to estimate the quality of computational protein models in terms of divergence from their native structure. It is a regression task to predict how close the decoy is to the unknown, native structure.
Inspired by Baldassarre et al. (2020), we train our models on Global Distance Test Score (Zemla, 2003), which is the globallevel score, and the Local Distance Difference Test (Mariani et al., 2013), an aminoacids-level score. The loss function of QA is defined as the Mean Squared Error (MSE): Lg = MSE(Pgpred − GDT TS),Ll =∑|S| i=1MSE(P lpredi −LDDTi) where P g pred and P lpred denote predicted global and local score, respectively.We jointly learn node and graph embeddings and the losses are weighted as Ltotal = µLl + (1 − µ)Lg , where µ is a hyper-parameter. We use the data from past years’ editions of CASP, including CASP10-13. CASP10,11,13 are used for training and validation, and CASP12 is
used for testing. Results. Table 4 shows that our methods outperform most of SOTAs, which demonstrates our methods can learn protein more efficiently. The outstanding performance of SHSC indicates that it is able to jointly learn better the node and graph level representation. But SHSC trained to predict only global scores obtains R = 0.712, which suggests that the local information can help the assessment of the global quality.
Protein Fold Classification. This task is critical for studying the relationship between protein structure and function, and protein evolution. We use the well-known SCOPe 1.75 dataset (Hou et al., 2018) and the cross-entropy loss. Results. Table 5 depicts that our proposed GHCN outperforms all others. It is manifest in the table that HGCNN-based methods GHCN and HGNN achieve much better performance compared to GCNN-based. However, it is worth noting that our proposed SHSC, does not seem to of-
fer significant advantages over GHCN and HGNN. This can be understood in the following lens: SGHC is used to alleviate the over-smoothing problem, which has a large impact on the node-level task, so our SHSC is more suitable for node-level tasks, while for the pure graph-level tasks, SHSC is too simple to offer good performance.

heading: 5 DISCUSSIONS AND FUTURE WORK.
text: Despite the good results, there are some limitations which worth further explorations in the future: 1) We just provide sufficient conditions for the equivalency to undigraphs, but the necessary condition is still unclear. 2) With the equivalency between hypergraphs and undigraphs, we have extended the undigraph-based GCNNs to hypergraph learning in this paper. Meanwhile, the equivalency between hypergraphs and digraphs would allow one to extend digraph-based GCNNs to potentially learn richer information in hypergraphs. 3) One could use the proposed unified random walk on hypergraphs to devise new clustering algorithms for hypergraph partitioning. 4) We make every effort to include a thorough experimental study. Further results on other possible datasets and baselines will be added as a future work.

heading: ETHICS STATEMENT AND BROADER IMPACT
text: In the work, we proposed a unified random walk framework on hypergraphs, based on which we study the equivalence between hypergraphs and graphs, and show that the unified random walk on EDVW-hypergraphs can not be equivalent to undigraphs without some specific conditions. Meanwhile, we lead to the Laplacian of our framework and analyze the spectral properties of it, especially focusing on the condition equivalent to an undigraph. Furthermore, we develop a Generalized Hypergrpah Convolutional Network and a Simple Hypergraph Spectral Convolution for hypergraph learning, based on the condition equivalent to undigraph.
Our research of the equivalency conditions between hypergraph and graph opens up many more possibilities in designing more comprehensive graph-based methods to solve the hypergraph problem. The experimental tasks used in our work including social networks and academic networks analysis, visual object classification, and protein learning, suggest that GHCN and SHSC can be applied for beneficial purposes, such as Rumour Detection, Crime Identification, Protein Function Prediction, etc.
Meanwhile, we have to be aware of possible negative impacts, such as using our model for telecom fraud on social networks, placing a high degree of trust in our model and obtain an incorrect interpretation of the results, etc. In addition, we should be vigilant about the potential unemployment issue due to the reduced amount of the need of labeling by human beings.

heading: REPRODUCIBILITY STATEMENT
text: All the datasets are publicly available as described in the main text. Our efforts to ensure reproducibility include the following aspects: 1) A sampled code is provided in the supplementary material. 2) The proofs and derivations are provided in Appendix G, F. 3) More details of experimental configurations are provided in Appendix I.

heading: CONTENTS

heading: A Related Work 16
text: A.1 Simplified Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.2 Detailed Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

heading: B Relations with Previous Random Walks on Hypergraph 18
text: B.1 A Classical Random walk on Hypergraph . . . . . . . . . . . . . . . . . . . . . . 18
B.2 Intuition and Analysis of The Unified Random Walk on Hypergraph . . . . . . . . 18
B.3 Special Cases of The Unified Random Walk Framework and Laplacian . . . . . . . 19

heading: C Unified Non-lazy Random Walks on Hypergraph 19

heading: D Typical Hypergraph Convolution (HGNN) and Its Spectral Analysis 21
text: D.1 Typical Spectral Hypergraph Convolution . . . . . . . . . . . . . . . . . . . . . . 22
D.2 Spectral Analysis of HGNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

heading: E The Relationship between Generalized Hypergraphs and Digraphs 23

heading: F Derivation and Analysis of GHCN and SHSC 23
text: F.1 Derivation of GHCN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
F.2 Derivation of The Discounted Markov Diffusion Kernel . . . . . . . . . . . . . . . 24
F.3 Derivation of SHSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
F.4 Over-smoothing Analysis of GHCN and SHSC . . . . . . . . . . . . . . . . . . . 25

heading: G Details of Theories and Proofs 26
text: G.1 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
G.2 Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
G.3 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
G.4 Nonequivalent Condition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
G.5 Failure Condition of Function ρ. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
G.6 Proof of Corollary 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
G.7 Spectral Range of Laplacian Matrix . . . . . . . . . . . . . . . . . . . . . . . . . 33
G.8 Proof of Corollary 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

heading: H Generalized Hypergraph Partition 35

heading: I Details of Experiments 35
text: I.1 Hyper-parameter Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
I.2 Baselines of Spectral Convolutions . . . . . . . . . . . . . . . . . . . . . . . . . . 37
I.3 Citation Network Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
I.4 Visual Object Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
I.5 Protein Quality Assessment and Fold Classification . . . . . . . . . . . . . . . . . 39
I.6 Over-Smoothing Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
I.7 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
I.8 The Spectrum Analysis of SHSC . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
I.9 Ablation Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
I.10 Examples of ρ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
I.11 Running Time and Computational Complexity . . . . . . . . . . . . . . . . . . . . 44
I.12 The edge-dependent vertex weights visualization . . . . . . . . . . . . . . . . . . 44
I.13 Additional Experiments of Baselines. . . . . . . . . . . . . . . . . . . . . . . . . 45

heading: A RELATED WORK

heading: A.1 SIMPLIFIED RELATED WORK
text: Deep learning for hypergraphs. For spectral-based methods, Feng et al. (2019) introduce the first hypergraph spectral convolution architecture HGNN, based on the hypergraph Laplacian proposed by Zhou et al. (2006). Yadati et al. (2019) use a non-linear Laplacian operator (Chan & Liang, 2020) to convert hypergraphs to simple graphs by reducing hyperedges into simple edges with mediators, and take advantage of graph neural networks to learning hypergraphs. Meanwhile, for spatial-based methods. Dong et al. (2020) propose a message-passing method that is divided into two processes from vertices to edges and from edges to vertices. Wendler et al. (2020) utilize signal processing theory to define the convolutional neural network on set functions. Yadati (2020) and Huang & Yang (2021) generalize the current graph message passing methods to hypergraphs and obtain several generalized models. Even though hypergraph neural networks have been well studied to process the the edge-independent vertex weights, to the best of our knowledge, we are the first to attempt on edge-dependent vertex weights.
Hypergraph random walk and spectral theory. In machine learning applications, Laplacian is an important tool to represent graphs or hypergraphs. While random walk-based graph Laplacian has a well-studied spectral theory, the spectral methods of hypergraphs are surprisingly lagged. A two-step random walk Laplaciain was proposed by Zhou et al. (2006) for the general hypergraph, and was improved by Chitra & Raphael (2019) and Carletti et al. (2020; 2021). On the other hand, Lu & Peng (2011) and Aksoy et al. (2020) define a s-th Laplacian through random s-walks on hypergraphs. More recently, non-linear Laplacian, as an important tool to represent hypergraphs, has been extended to several settings, including directed hypergraphs (Zhang et al., 2017; Chan et al., 2019), submodular hypergraphs (Li & Milenkovic, 2017), etc.
Equivalency between hypergraphs and undigraphs. A fundamental problem in the spectral theoretical study of hypergraphs is the equivalency with undigraphs. Once equipped with equivalency, it is possible to represent hypergraphs with lower-order graphs, thus reducing the difficulty of hypergraph learning. So far, equivalence is established from two perspectives: spectrum of Laplacian (Agarwal et al., 2006; Hayashi et al., 2020) or random walk (Chitra & Raphael, 2019).
Hypergraph with edge-dependent vertex weights (EDVW-hypergraph)
EDVW-hypergraphs have been widely adopted in machine learning applications, including 3D object classification (Zhang et al., 2018), image segmentation (Ding & Yilmaz, 2010), e-commerce (Li et al., 2018a), image search (Huang et al., 2010), hypergraph clustering (Hayashi et al., 2020) etc. Unfortunately, to the best of our knowledge, existing learning algorithms for processing EDVWhypergraphs do not involve deep learning methods.

heading: A.2 DETAILED RELATED WORK
text: Deep learning for hypergraphs Feng et al. (2019) introduce the first hypergraph architecture hypergraph neural network(HGNN), based on the hypergraph Laplacian proposed by Zhou et al. (2006), however, a flaw in the theory makes the learning of unconnected networks very inefficient (details can see Appendix D.1). Yadati et al. (2019) use the non-linear Laplacian operators Chan & Liang (2020) to convert hypergraphs to simple graphs by reducing a hyperedge to a subgraph with edge weights related only to its degree, which causes the information loss of hypergraphs and limited the generalization. Jiang et al. (2019) proposed a dynamic hypergraph neural networks to update hypergraph structure during training. Wendler et al. (2020) utilize signal processing theory to define the convolutional neural network on set functions. Zhang et al. (2020) combined hypergraph label propagation with deep learning and introduced a Hypergraph Label Propagation Network to optimize the hypegraph learning. Yadati (2020) proposed a generalisedMPNN on hypergraph which unifies the existing MPNNs Gilmer et al. (2017) on simple graph and also raised a MPNN-Recursive framework for recursively-structured data processing, but it performs poorly for other high-order relationships. Huang & Yang (2021) generalized the current graph message passing methods to hypergraphs and obtain a UniGCN with self-loop and a deepen hypergrpah network UniGCNII. However, it does not give reasons why self-loop can assist UniGCN to gain the improvement of performance in the citation network benchmark. Moreover, its experimental results with various depths may show that the HGCNNs have over-smoothing issue, but theoretical analysis to explain this phenomenon is lacked. Hypergraph deep learning has also been applied to many areas, such as NLP (Ding et al., 2020), computer vision (Jin et al., 2019), recommendation system (Zhang et al., 2019), etc
Hypergraph random walk and spectral theory. In machine learning applications, Laplacian is an important tool to represent graphs or hypergraphs. While random walk-based graph Laplacian has a well-studied spectral theory, the spectral methods of hypergraphs are surprisingly lagged. The research of hypergraph Laplacian can probably be traced back to Chung (1993), which defines the Laplacian of k-uniform hypergraph (each hyperedge contains the same number of vertices). Then Zhou et al. (2006) defined a two-step random walk-based Laplacian for general hypergraphs. Based on it, many works try to design a more comprehensive random walk on hypergraphs. Chitra & Raphael (2019) designed a random walk which considered edge-dependent vertex weights of hypergraphs in the second step to replace the edge-independent weights in Zhou et al. (2006). Actually, the edge-dependent vertex weights could model the contribution of vertex v to hyperedge e and were widely used in machine learning such as 3D object classification (Zhang et al., 2018; Feng et al., 2019) and image segmentation (Ding & Yilmaz, 2010) etc., but without spectral guarantees.
On the other hand, Carletti et al. (2020; 2021) takes another perspective to gain more fine-grained information from a hypergraph by taking into account the degree of hyperedges to measure the importance between vertices in the first step. However, a comprehensive random walk should consider the above two aspects at the same time. Furthermore, different from the two-step random walk Laplacian of Zhou et al. (2006), Lu & Peng (2011) and Aksoy et al. (2020) define a s-th Laplacian through random s-walk on hypergraphs. More recently, non-linear Laplacian, as an important tool to represent hypergraphs, has been extended to several settings, including directed hypergraphs (Zhang et al., 2017; Chan et al., 2019), submodular hypergraph (Li & Milenkovic, 2017) etc. Meanwhile, liner Laplacian has also been developed. For example, Chitra & Raphael (2019) use a two-step random walk to develop a spectral theory for hypergraphs with edge-dependent vertex weights, and a two-step random walk on hypergraph proposed by Carletti et al. (2020; 2021) also designed a twostep random walk by involving the degree of hyperedges in the first step and lead a linear Laplacian. In this work, we design a unified two-step random walk framework to study the linear Laplacians.
Equivalency between hypergraphs and undigraphs. A core problem in the spectral theoretical study of hypergraphs is the equivalency between hypergraphs and graphs. Once equipped with equivalency, it is possible to represent hypergraphs with lower-order graphs, thus reducing the difficulty of hypergraph learning. So far, equivalence can be established from two perspectives: spectrum of Laplacian or random walks. For the aspect of Laplacian spectrum, Agarwal et al. (2006) firstly showed the Laplacian of Zhou et al. (2006) is equivalent to the Laplacian of the corresponding star expansion graph (having the same eigenvalue problem). Next, Hayashi et al. (2020) claims that the Laplacian defined by Chitra & Raphael (2019) is equal to an undigraph Laplacian, but the undi-
graph Laplacian needs to be constructed by invoking the stationary distribution, which restricts its application. Meanwhile, from the random walk perspective, Chitra & Raphael (2019) claims that hypergraph is equivalent to its clique graph (undirected) when the vertex weight of hypergraph is edge-independent. However, despite the edge-dependent weights were widely used (Ding & Yilmaz, 2010; Zeng et al., 2016; Zhang et al., 2018), the equivalency problem remains open when the vertex weight is edge-dependent.
Protein learning. Proteins are biological macromolecules with spatial structures formed by folding chains of amino acids, which have an important role in biology. A protein has a three-level structure: primary, secondary, and tertiary, where primary (sequence of amino acids) and tertiary (3D spatial) structures are often used to model proteins for representation learning. Based on amino acids sequence, there exist many related works of protein learning, such as Rao et al. (2019); Bepler & Berger (2018); Strodthoff et al. (2020); Conover et al. (2019), etc. Meanwhile, many 3D structure based models are also raised for protein learning, such as Olechnovivc & Venclovas (2017); Derevyanko et al. (2018); Baldassarre et al. (2020); Diehl (2019); Baldassarre et al. (2020); Gligorijevic et al. (2020); Hermosilla et al. (2021), etc. However, to the best of our knowledge, despite the hypergraphs have been developed to model proteins (Maruyama et al., 2001), there is still no related work to design the EDVW-hypergraph-based protein learning algorithm.

heading: B RELATIONS WITH PREVIOUS RANDOM WALKS ON HYPERGRAPH

heading: B.1 A CLASSICAL RANDOM WALK ON HYPERGRAPH
text: It can be traced back to Zhou et al. (2006) in which they have given a view of random-walk to analyze the hypergraph normalized cut. The transition probability of Zhou et al. (2006) from current vertex u to next vertex v is denoted as:
P (u, v) = ∑ e∈E w(e) H(u, e) d(u) H(v, e) δ(e) . (9)
It is easy to find P (u, v) means: (i) choose an arbitrary hyperedge e incident with u with probability w(e)/d(u) where d(u) = ∑ e∈E w(e)H(u, e); (ii) Then choose an arbitrary vertex v ∈ e with
probability 1/δ(e) where δ(e) = ∑ v∈V H(v, e), which means to select vertex randomly in the hyperedge.
B.2 INTUITION AND ANALYSIS OF THE UNIFIED RANDOM WALK ON HYPERGRAPH
In this subsection, we would like to explain our intuition of developing the unified random walk framework in Definition 1 from a view of two-step random walk on a hypergraph. To generalize the notation of hypergraph random walk in the seminal paper Zhou et al. (2006), in this work, we tend to explain the process from another perspective. The fact in Zhou et al. (2006) that
d(u) = ∑ e∈E w(e)H(u, e) = ∑ e∈E ∑ v∈V w(e) H(u, e)H(v, e) δ(e) = ∑ v∈V ∑ e∈E(u,v) w(e) δ(e) (10)
and
P (u, v) = ∑ e∈E w(e)H(u, e) d(u) · H(v, e) δ(e) = 1 d(u) ∑ e∈E(u,v) w(e) δ(e) =
∑ e∈E(u,v)
w(e) δ(e)∑
b∈V ∑ e∈E(u,b) w(e) δ(e)
(11)
show that the probability P (u, v) also means a normalized weighted adjacency relationship between u and v (Here, E(u, v) denotes the hyperedges contained vertices u and v.). Furthermore, the relationship is actually measured by the sum of w(e)δ(e) for all e ∈ E concluding pair {u, v}, which demonstrates that a hyperedge e with larger degree (δ(e)) linked to {u, v} contribute less to the transition probability between u and v.
From Carletti et al. (2021), which proposed a random walk on hypergraphs (a specital case of our unified random walk with Q1 = Q2 = H and ρ(·) = (·)σ), we further explain the intuition of our
purpose to design the P (u, v) of our unified random walk. When Q1 = Q2 = H, P (u, v) in Eq. 3 can be expressed as:
P (u, v) =
∑ e∈E(u,v)
w(e)ρ(δ(e))∑ b∈V ∑ e∈E(u,b) w(e)ρ(δ(e))
That is to say, the influence of hyperedge degree should not be limited to an inverse relationship by introducing the function ρ(·). Thus, by evolving more fine-grained vertexes weights Q1(u, e) and Q2(v, e) to replace H(v, e) and H(u, e), we obtain the final transition probability of our unified hypergraph random walk in equation 3.

heading: B.3 SPECIAL CASES OF THE UNIFIED RANDOM WALK FRAMEWORK AND LAPLACIAN
text: We show the existing random walks and Laplacians are the special cases of our unified random walks and our unified Laplacians, respectively. Under our framework, the existing random walk models can be seen as a special case with specific p1, p2. It is easy to construct the relations of our framework to previous works as follows:
Remark 1 (Zhou et al. (2006)) When we choose ρ(·) = (·)−1 and Q1 = Q2 = H in our framework, the probabilities of unified random walk on hypergraph are reformulated as p1 = w(e)H(u,e)∑ e∈E w(e)H(u,e) and p2 = H(v,e)∑ v∈V H(v,e) . As the special case of ours satisfying Q1 = Q2 = H and ρ(·) = (·)−1, Zhou et al. (2006)’s random walk satisfies both condition (1) and condition (2) in Thm. 1. So we obtain from Corollary 1 that πzhou(v) =
d(v)∑ u∈V d(u) and Lzhou =
I − D−1/2v HWD−1e H>D −1/2 v where Dv(u, u) = d(u) = ∑ e∈E w(e)H(u, e) and De(e, e) =
δ(e) = ∑ v∈eH(v, e). The forms of πzhou and Lzhou are exactly the same in Zhou et al. (2006).
Remark 2 (Carletti et al. (2020; 2021)) When we select ρ(·) = (·)σ and Q1 = Q2 = H, the probabilities of unified random walk on hypergraph are reduced to p1 =
w(e)H(u,e)( ∑ v∈V H(v,e))
σ+1∑ e∈E w(e)H(u,e)( ∑ v∈V H(v,e)) σ+1 and p2 = H(v,e)∑ v∈V H(v,e)
. As the special case of ours satisfying Q1 = Q2 = H and ρ(·) = (·)σ , Carletti et al. (2021)’s random walk satisfies both condition (1) and condition (2) in Thm. 1. So we obtain from Corollary 1 that πcar(v) =
d(v)∑ u∈V d(u)
and Lcar = I −D−1/2v HWDσeH>D −1/2 v where Dv(u, u) = d(u) = ∑ e∈E w(e)δ(e)
σ+1H(u, e) and De(e, e) = δ(e) = ∑ v∈eH(v, e). The forms of πcar and Lcar are exactly the same in Carletti et al. (2021). Note that the random walk proposed by Carletti et al. (2020) is a special case of Carletti et al. (2021) with σ = 1, the π and L are easy to obtain from our conclusions.
Remark 3 (Chitra & Raphael (2019)) When we set ρ(·) = (·)−1 and Q1 = H, the probabilities of unified random walk on hypergraph become p1 =
w(e)H(u,e)∑ e∈E w(e)H(u,e) and p2 = Q2(v,e)∑ v∈V Q2(v,e)
with an edge-dependent vertex weights Q2 in the second steps. Actually, as the special case of ours satisfying Q1 = H and ρ(·) = (·)−1, Chitra & Raphael (2019)’s random walk on hypergraph generates the Laplacian Lchi which could build up a simple relation with our Lrw in equation 20 as
Lchi = Φ 1/2LrwΦ 1/2 = Φ− ΦP + P >Φ
2
which means that Lrw denotes a form of symmetrization on Lchi. Further, as the vertex weights is edge-independent in Chitra & Raphael (2019) which means they satisfies condition(1) in Thm. 1, the same π as Chitra & Raphael (2019) can be obtained from Corollary 1, i.e. π(v) = d̂(v)∑
v d̂(v) .

heading: C UNIFIED NON-LAZY RANDOM WALKS ON HYPERGRAPH
text: The non-lazy version is nontrivial to factor and analyze. To ease the studies, we first give the following definition and lemma.
Definition 4 (Reversible Markov chain) Let M be a Markov chain with state space X and transition probabilities P (u, v), for u, v ∈ X . We say M is reversible if there exists a probability distribution π over X such that
π(u)P (u, v) = π(v)P (v, u). (12)
Lemma 2 (Chitra & Raphael (2019)) Let M be an irreducible Markov chain with finite state space S and transition probabilities P (u, v) for u, v ∈ S. M is reversible if and only if there exists a weighted, undirected graph G with vertex set S such that a random walk on G and M are equivalent.
Proof. Let π be the stationary distribution of M (suppose that is irreducible). Note that π(u) 6= 0 due to the irreducibility of M . Let G be a graph with vertices S. Different from Chitra & Raphael (2019), we set the edge weights of G to be
ω(u, v) = cπ(u)P (u, v), ∀ u, v ∈ S (13)
where c > 0 is a constant for normalizing π. With reversibility, G is well-defined (i.e. ω(u, v) = ω(v, u)). In a random walk on G, the transition probability from u to v in one time-step is: ω(u,v)∑ v∈V ω(u,v) = cπ(u)P (u,v)∑ v∈V cπ(u)P (u,v) = P (u, v), since ∑ w∈S P (u,w) = 1. Thus, if M is reversible, recall Definition 3, the stated claim holds. The other direction follows from the fact that a random walk on an undirected graph is always reversible (Aldous & Fill,[70]).
Next, we generalize the non-lazy random walk of Carletti et al. (2021) to our unified non-lazy random walk with vertex weights Q1,Q2. Definition 5 (Unified Non-lazy Random Walk on Hypergraphs) Suppose δ(e) :=∑ v∈V Q2(v, e) is the degree of hyperedge, and dnl(v) := ∑ e∈E w(e)(δ(e) − Q2(v, e))ρ(δ(e) − Q2(v, e))Q1(v, e) is the degree of vertex v. The unified non-lazy random walk on a hypergraph H is defined in a two-step manner: Given the current vertex u,
Step I: choose a hyperedge e incident to u, with probability
p1 = w(e)(δ(e)−Q2(u, e))ρ(δ(e)−Q2(u, e))Q1(u, e)
dnl(u) ; (14)
Step II: choose an arbitrary vertex v 6= u from e, with probability
p2 = Q2(v, e)
δ(e)−Q2(u, e) , (15)
Thus, the transition probability of our unified non-lazy random walk from vertex u to v is:
Pnl(u, v) =
{ ∑ e∈E w(e)ρ(δ(e)−Q2(u,e))Q1(u,e)Q2(v,e) dnl(u)
if u 6= v, 0 if u = v
(16)
Thus, the transition matrix of unified non-lazy random walk can be expressed as:
Pnl = D −1 nl (Q1 ρ(1De −Q2))WQ > 2 , (17)
where Dnl, De are diagonal matrices with entries Dnl(v, v) = dnl(v) and De(e, e) = δ(e), respectively. denotes the Hadamard product and 1 denotes a |V|×|E| ones matrix(i.e. all elements equal to 1). ρ(1De −Q2)) represents the function ρ acting on each element of (1De −Q2). Following Chitra & Raphael (2019), the modified version of the clique graph without self-loops is defined below:
Definition 6 (Chitra & Raphael (2019)) LetH(V, E ,Q) be a hypergraph associated with the unified non-lazy random walk in Definition 5. The clique graph of H without self-loops, GCnl, is a weighted, undirected graph with vertex set V , and edges E ′ defined by
E ′ = {(v, w) ∈ V × V : v, w ∈ e for some e ∈ E , and v 6= w} (18)
Different from the lazy random walk, a unified non-lazy random walk on a hypergraph with condition (1) or condition (2) in Thm. 1 is not guaranteed to satisfy reversibility (see Definition 4). However, if Q1 = Q2 = H, then reversibility holds, and we obtain the result below.
Theorem 2 Let H(V, E ,Q) be a hypergraph associated with the unified non-lazy random walk in Definition 5. Let Q1 = Q2 = H, i.e. Qi(v, e) = 1, i ∈ {1, 2} for all vertices v incident hyperedges e. Then, there exist weights ω(u, v) on the clique graph without self-loops GCnl such that a non-lazy random walk onH is equivalent to a random walk on GCnl.
Proof. We first prove that the unified non-lazy random walk on H is reversible. It is easy to verify the stationary distribution of the unified non-lazy random walk on H with Q1 = Q2 = H is π(v) = dnl(v)∑
v∈V dnl(v) . Let P (u, v) be the probability of going from u to v in a unified non-lazy
random walk onH, where u 6= v. Then,
π(u)P (u, v) = dnl(u)∑ u∈V dnl(u) ∑ e∈E w(e)ρ(δ(e)−Q2(u, e))Q1(u, e)Q2(v, e) dnl(u)
= 1∑
u∈V dnl(u) ∑ e∈E (w(e)ρ(δ(e)−Q2(u, e))Q1(u, e)Q2(v, e))
= 1∑
u∈V dnl(u) ∑ e∈E (w(e)ρ(δ(e)−H(u, e))H(u, e)H(v, e))
= 1∑
u∈V dnl(u) ∑ e∈E (w(e)ρ(δ(e)−H(v, e))H(v, e)H(u, e))
= π(v)P (v, u)
So the unified non-lazy random walk is reversible. Thus, by Lemma 2, there exists a graph G with vertex set V and edge weights
ω(u, v) = dnl(u)P (u, v)
such that a random walk on G and the unified non-lazy random walk on H is equivalent. The equivalence of the random walks implies that P (u, v) > 0 if and only if ω(u, v) > 0, so it follows that G is the clique graph ofH without self-loops.

heading: Hypergraph Clique Graph

heading: D TYPICAL HYPERGRAPH CONVOLUTION (HGNN) AND ITS SPECTRAL ANALYSIS
text: Recall Remark 1, the random walk and Laplaican proposed by Zhou et al. (2006) are special cases (ρ(·) = (·)−1,Q1 = Q2 = H) of our unified random walk and unified Laplacian, respectively. Thus, now the degree of a vertex v ∈ V is d(v) = ∑ e∈E w(e)H(v, e) and for a hyperedge
e ∈ E , its degree is δ(e) = ∑ v∈V H(v, e). The edge-degree matrix and vertex-degree matrix can be denoted as diagonal matrices De ∈ R|E|×|E| and Dv ∈ R|V|×|V| respectively.

heading: D.1 TYPICAL SPECTRAL HYPERGRAPH CONVOLUTION
text: From the seminal paper Zhou et al. (2006), a classical symmetric normalized hypergraph Laplacian is defined from the perspective of spectral hypergraph partition: L = I − D −1/2 v HWD−1e H >D −1/2 v . Based on it, Feng et al. (2019) follow Kipf & Welling (2017) to deduce the Hypergraph Neural Network HGNN. Specifically, they first perform an eigenvalue decomposition of L: L = UΛU>, where Λ is a diagonal matrix of eigenvalues and U is consisted of the corresponding regularized eigenvectors. Combining the hypergraph Laplacian with Fourier Transform of graph signal processing, they derive the primary form of hypergraph spectral convolution: g ∗ x = U((U>g) (U>x)) = Ug(Λ)U>x where g(Λ) = diag(g(λ1), g(λ2), · · · , g(λN )) is a function of the eigenvalues of L. To avoid expensive computation of eigen decomposition (Defferrard et al., 2016), they use the truncated Chebyshev polynomials Tk(x) to approximated g(Λ), which is recursively deduced by Tk(x) = 2xTk−1(x) − Tk−2(x) with T0(x) = 1 and T1(x) = x. g ∗x ≈ ∑K−1 k=0 θkTk(Λ̂)x, with scaled Laplacian Λ̂ = 2 λmax
Λ−I limiting the eigenvalues in [−1, 1] to guarantee requirement of the Chebyshev polynomial (Hammond et al., 2011). Since the parameters in the neural network could adapt to the scaled constant (λmax ≈ 2), the convolution operation is further simplified to beg ∗ x ≈ θ0x− θ1D − 12 v HWD−1e H >D − 12 v x.
However, in order to obtain the final convolutional layer similar to Kipf & Welling (2017) proposed, Feng et al. (2019) used a specific matrix to fit the scalar parameter θ0, causing a flaw in the derivation. In the end, they have managed to obtain a seemingly correct hypergraph spectral convolution (HGNN):
Y = D−1/2HWD−1e H >D−1/2v XΘ, (19)
where Θ is the parameter to be learned during the training process. There is no doubt that HGNN can work properly, but it could have low efficiency when the hypergraph of the datasets is disconnected. Our experiments in subsection 4.1 and Figure 4 verify our conclusion.

heading: D.2 SPECTRAL ANALYSIS OF HGNN
text: We give the definition of Rayleigh quotient to study the spectrum of Laplacian.
Lemma 3 ( Rayleigh Quotient (Horn, 1986)) Assume that M ∈ Rn×n is a real symmetric matrix and x ∈ Rn is an arbitrary nonzero vector. Let λ1 ≤ λ2 ≤ · · · ≤ λn denote the eigenvalues of M in order. Then the Rayleigh quotient satisfies the property:
λ1 ≤ R(M,x) := x>Mx
x>x ≤ λn.
The equality holds that R(M,u1) = λ1 and R(M,un) = λn where ui is the eigenvector related to λi, i ∈ {1, n}.
The Lemma 3 is mainly used to get all exact or approximated eigenvalues and eigenvectors of M.
In this part, we utilize it to prove that the smallest eigenvalue λmin of L = I − D − 12 v HWD−1e H >D − 12 v is 0 and figure out the corresponding eigenvector umin is D 1 2 v 1.
Specifically, let g denote an arbitrary column vector which assigns to each vertex v ∈ V a real value g(v). We demonstrate R(L, g) as below in order to describe our conclusion distinctly:
λmin ≤ g>Lg g>g = g>(I−D− 1 2 v HWD−1e H >D − 12 v )g g>g
= (D
1 2 v f)>(I−D − 12 v HWD−1e H >D − 12 v )(D 1 2 v f)
(D 1 2 v f)>(D 1 2 v f)
= f>(Dv −HWD−1e H>)f
f>Dvf
=
∑ e ∑ v ∑ u w(e)h(v,e)h(u,e) δ(e) (f(u)− f(v)) 2
2 ∑ v f(v) 2d(v)
where g = D1/2v f and f ∈ R|V|×1. It is easy to see the fact: R(L, g) ≥ 0, and R(L, g) = 0 if and only if f = 1 (i.e. g = D1/2v 1). Then with lemma 3 we get λmin = min
g R(L, g) = R(L,D
1/2 v 1) =
0 and umin = D 1 2 v 1.
Actually, since the Laplacian of Zhou et al. (2006) is our unified Laplacian in Corollary 1, the property above can be directly led by Thm. 5.

heading: E THE RELATIONSHIP BETWEEN GENERALIZED HYPERGRAPHS AND DIGRAPHS
text: In this part, we would like to illustrate that our unified random walk on a hypergraph is always equivalent to a random walk on the weighted directed clique graph, As long as the equivalent conditions are established, the graphs can be viewed as the low-order encoders of hypergraphs, and many machine learning methods of digraphs could be easily generalized to hypergraphs.
Chitra & Raphael (2019), whose random walk is a special case of our framework with ρ(·) = (·)−1,Q1 = H, claims that the hypergraph with edge-dependent weights (i.e. Q2 is edgedependent) is equivalent to a directed graph. Here we extend this conclusion to a more general version by the above definition.
Theorem 3 (Equivalency between hypergraph and weighted digraph) Let H(V, E ,W,Q1,Q2) denote the generalized hypergraph in Definition 2. There exists a weighted directed clique graph GC such that the random walk onH is equivalent to a random walk on GC .
Thm. 3 indicates that any hypergraph is equivalent to a digraph under our framework (Fig. 1) and implies that the existing hypergraph random walks are modeling pairwise relationships (proof in Appendix G.1 ).
Adopting results of Thm. 3, we design the Laplacian for our unified random walk framework and explore its spectral properties. Thm. 3 says that the unified random walk framework is equivalent to directed graph, so we extend the definition of directed graph Laplacian (Chung, 2005) to obtain the normalized Laplacian matrix as follows.
Corollary 3 (Random Walk-based Hypergraph Laplacian) LetH(V, E ,W,Q1,Q2) be the generalized hypergraph Let P be the transition matrix of our random walk framework onH with stationary distribution π (suppose that exists). Let Φ be a |V| × |V| diagonal matrix with Φ(v, v) = π(v). The unified random walk-based hypergraph Laplacian matrix Lrw is defined as:
Lrw = I− Φ1/2PΦ−1/2 + Φ−1/2P>Φ1/2
2 . (20)
Following Chung (2005), it is easy to study many properties based on Rayleigh quotient of Lrw, such as positive semi-definite, Cheeger inequality, etc. The Laplacian Lrw has a great expressive power thanks to the comprehensive random walk, which unifies most of existing random walkbased Laplacian variants due to the generalization ability of the framework (see Appendix B.3). Note that the distribution π is not easy to obtain and do not admit a unitized expression that limits the application of Lrw in equation 20. In this paper, we focus on the case when hypergraph is equivalent to undigraph (Thm. 1) and deduce the explicit expression of Lrw (Corollary 1).
Based on our equivalency Theorem and Lapalacian, we can design directed graph neural networks for generalized hypergraph learning, which we will do as a future work.

heading: F DERIVATION AND ANALYSIS OF GHCN AND SHSC

heading: F.1 DERIVATION OF GHCN
text: We define K as Q2Wρ(De)Q>2 . Then the unified hypergraph Laplacian matrix L in Thm. 1 can be denoted as
L = I− D̂−1/2v KD̂−1/2v , (21)
Similar to GCN (Kipf & Welling, 2017) and Appendix D.1, we perform eigenvalue decomposition of L, then obtain the convolution kernel by using Fourier transform, and approximate it with the truncated Chebyshev polynomial to get the convolution form:
g ? x = θ0x− θ1D̂−1/2v KD̂−1/2v x. (22)
Then we adopt the same method proposed by Kipf & Welling (2017) to set the parameter θ = θ0 = −θ1 and obtain the following expression:
g ? x = θ ( I + D̂−1/2v KD̂ −1/2 v ) x. (23)
According to Theorem 5, it is easy to know the eigenvalues of I + D̂−1/2v KD̂ −1/2 v range in [0, 2], which may cause the unstable numerical instabilities and gradient explosion problem. So we use the renormalization trick (Kipf & Welling, 2017):
I + D̂−1/2v KD̂ −1/2 v → D̃−1/2v K̃D̃−1/2v , T̃, (24)
where K̃ = K + I can be regarded as the weighted adjacency matrix of the equivalent weighted graph with self-loops, and D̃(v, v) = ∑ u K̃(v, u) is a |V| × |V| diagonal matrix. This self-loops makes the methods more robust to process disconnected hypergraphs datasets. Finally, we drive the generalized hypergraph convolutional network(GHCN):
X(l+1) = ψ(T̃X(l)Θ) (25)
Θ is a learnable parameter and ψ(·) denotes an activation function.

heading: F.2 DERIVATION OF THE DISCOUNTED MARKOV DIFFUSION KERNEL
text: Discounted Markov Diffusion Kernel for hypergraph Recall that the discounted average visiting rate:
v̄ik(t) = 1
t t∑ τ=1 ατ Pr(s(τ) = k|s(0) = i) = 1 t t∑ τ=1 ατ (Pτ )ik = Z(t)ik (26)
i.e. Z(t) = ∑t τ=1 ατ t P τ . Then, v̄i(t) = (v̄i1(t), · · · , v̄in(t))> denotes as:
v̄i(t) = (e > i Z(t)) > = Z>(t)v̄i(0)
Recall the definition of v̄i(0) in subsection 3.2: v̄ik(0) = 1 if and only if i = k, otherwise v̄ik(0) = 0. Then, the discounted Markov diffusion kernel KMD can be derived from the l2-norm diffusion distance as follows:
dij(t) = ‖v̄i(t)− v̄j(t)‖22 = ∥∥Z>(t)(v̄i(0)− v̄j(0))∥∥22
= (v̄i(0)− v̄j(0))>Z(t)Z>(t)(v̄i(0)− v̄j(0))
= (ei − ej)T KMD (ei − ej)

heading: F.3 DERIVATION OF SHSC
text: Inspired by the diffusion kernel-based methods from Zhu & Koniusz (2021) and Klicpera et al. (2019), and based on the discounted Markov diffusion kernel defined in subsection 3.2, the hypergraph convolution designed in our work is shown as below general form:
Y = ψ (( K∑ k=1 αk K T̃k ) XΘ ) , (27)
where T̃ is the generalized transition matrix in equation 24, Θ is the parameter matrix to be learned during training, and ψ(·) denotes an activation function. Since T̃k can be viewed as a k-steps transition matrix, in order to weaken the neighbor vertices in long diffusion steps, we introduce
a discounting factor α k
K for T̃ k, which can be deduced from the underlying feature map Z(t) of
discounted Markov diffusion kernel defined in subsection 3.2. We use a well-known trick (Zhu & Koniusz, 2021; Chen et al., 2020) to balance the global information aggregation and the vertex’s own information by introducing a hyper-parameter β ∈ [0, 1] to control the self-loop T̃0 = I. Finally, we proposed a Simple Hypergraph Spectral Convolution (SHSC) as:
Y = ψ (( β
K∑ k=1 αk K T̃k + (1− β)I
) XΘ ) (28)
Actually, SHSC is a spatial-based model while we can analyze it from a spectral-based view. Let L = I − T̃ denote the normalized Laplacian matrix. Then the SHSC can be viewed as a special spectral-based polynomial filter through ∑I i=0 ξiL i = ∑K k=0 θkT̃ k where θk = α k
K . Finally, we can deduce the coefficients of the special polynomial filter as ξi = (−1)i ∑K k=i ( k i ) αk
K showing the strong relationships between SHSC and spectral-based model. The explicit form of ξi can be derived as:
K∑ k=0 θkT̃ k = K∑ k=0 θk(I− L)k = K∑ k=0 θk k∑ i=0 ( k i ) (−1)iLi = K∑ i=0 ( K∑ k=i (−1)i ( k i ) αk K ) Li

heading: F.4 OVER-SMOOTHING ANALYSIS OF GHCN AND SHSC
text: For real-world datasets, we always use non-Euclidean graphs with finite-dimensional features of vertices. It is difficult to use the absolute diffusion distance (Masuda et al., 2017) which measures the distance walked from starting vertex in the diffusion process. Therefore, we use the reciprocal of the mean l1-norm error between t-step transition probability Pt and stationary distribution π as the measure of over-smoothing in arbitrary starting vertex. Formally, we name the measure by over-smoothing energy as follows:
e(i, t) = 1
1 N ‖f(i)Pt − π‖1
where i denotes the sign of starting vertex i and t denotes the number of diffusion step. As mentioned in Corollary. 2, f(i) is an initial distribution which means the walker diffuse starting from vertex i(i.e. f(i)i = 1 and f(i)j = 0,∀j 6= i ). It is easy to observe that if the limit of e(i, t) with respect to t converges to infinity, it indicates the model based on P undergo severe over-smoothing issue. Recall Corollary 2, we get a low-bounded quantity of e(i, t) as elow(i, t):
e(i, t) ≥ N∑N j=1(1− λH)t √ d̂(j)√ d̂(i) = N
√ d̂(i)
(1− λH)tϕ(H) = elow(i, t)
where ϕ(H) = ∑N j=1 √ d̂(j) can be seen as a constant associated with H which is independent with i or t. Recall Corollary 2 that λH is smallest nonzero eigenvalue of L.
Over-smoothing analysis of GHCN. As shown in Table 14, we can see our proposed GHCN model also face with the over-smoothing phenomenon. Assume that we get a K-layers GHCN model with the form: X(l+1) = ReLU(T̃X(l)Θ). To get a simple mathematical form from above incremental convolution formula (remove the activation layer), we could get approximatedK-layers GHCN as:
X̃(K) = T̃KX(0)Θ
Intuitively, from the simple form we find the over-smoothing energy of GHCN in vertex i can be represented by elow(i,K). It is easy to analyze that as K →∞, elow(i,K) converge to infinity which implies that the over-smoothing energy e(i, t) converge to infinity. Furthermore, the convergence of over-smoothing energy to infinity means the error between initial signal and π converge to 0 as the number of layers increasing, which describes the reason of over-smoothing underwent by GHCN from a quantitative perspective. HGNN (Feng et al., 2019) also suffers from over-smoothing as shown in Table 14. Meanwhile, the theoretical analysis of over-smoothing on HGNNcan be covered by the analysis of GHCN due to HGNN is a special case of GHCN.
Over-smoothing analysis of SHSC. Similarly, from the form of SHSC, we use 1 K ∑K k=0 α
kelow(i, k) to represent SHSC’s over-smoothing energy. In order to explain the reason why SHSC could relieve over-smoothing, we provide the idea of equivalent infinitesimals to compare the over-smoothing energy between muti-layers GHCN and SHSC as follows: As K →∞:
lim K→∞
eSHSC(i,K) eGHCN (i,K) = lim K→∞
1 K ∑K k=0 α kelow(i, k)
elow(i,K)
= lim K→∞
(1− λH)K ∑K k=0( α 1−λH ) k
K
= lim K→∞
(1− λH)K+1 − αK+1
K(1− λH − α) ( suppose 1− λH − α 6= 0)
= 0 (29)
where the last equation depends on α ∈ (0, 1] and λH ∈ (0, 2] proved by Theorem 5. If 1−λH−α = 0, 1 − λH = α < 1. Thus, the equation 29 also holds. The result describes why SHSC can relieve over-smoothing compared to multi-layer GHCN that the over-smoothing energy of multilayers GHCN has been sparse by the designed diffusion kernel of SHSC as K growing.
Actually, we can directly analyse the over-smoothing energy of SHSC:
lim K→∞
1
K K∑ k=0 αkelow(i, k)
= lim K→∞
1
K K∑ k=0 αk N
√ d̂(i)
(1− λH)kϕ(H)
= lim K→∞
N √ d̂(i)
ϕ(H)
( 1− λH
K(1− λH − α) − α K(1− λH − α)
( α
1− λH
)K) (30)
If α ≤ |1 − λH | and 1 − λH − α 6= 0, equation 30 equals to 0; If 1 − λH − α = 0, equation 30 equals to N √ d̂(i)
ϕ(H) ; Otherwise, equation 30 converges to infinity. Notably, this result shows that the over-smoothing property of SHSC is related to the magnitude of α and λH . Moreover, this analysis further reveals that the introduced hyperparameter α is meaningful for SHSC to alleviate over-smoothing.

heading: G DETAILS OF THEORIES AND PROOFS

heading: G.1 PROOF OF THEOREM 3
text: Theorem 3 (Equivalency between hypergraph and weighted digraph) Let H(V, E ,W,Q1,Q2) denote the generalized hypergraph in Definition 2. There exists a weighted directed clique graph GC such that the random walk onH is equivalent to a random walk on GC .
Proof. Let ω(u, v) be the weight of edge (u, v) in GC . We set ω(u, v) = d(u)P (u, v) in Definition 1, then the weighted clique graph is a directed graph, where P (u, v) is the transition probabilities in Eq equation 3. The random walk on the directed weighted GC with transition probabilities
PC(u, v) = ω(u, v)∑ v∈V ω(u, v) = d(u)P (u, v)∑ v∈V d(u)P (u, v) = P (u, v)
is equivalent toH with transition probabilities P(u, v). The matrix form of edge weight of GC is :
WC = Q1Wρ(De)Q > 2
Suppose W = I and let ρ(·) = (·)−1, we can obtain the equivalent weighted clique graph showing in Figure 5.

heading: G.2 PROOF OF LEMMA 1
text: Lemma 1 Let H(V, E ,W,Q1,Q2) denote the generalized hypergraph in Definition 2. Let F(Q1,Q2)(u, v) := ∑ e∈E w(e)ρ(δ(e))Q1(u, e)Q2(v, e) and T(Q)(u) :=∑
e∈E w(e)δ(e)ρ(δ(e))Q(u, e). When Q1,Q2 satisfies the following equation
T(Q2)(u)T(Q1)(v)F(Q1,Q2)(u, v) = T(Q2)(v)T(Q1)(u)F(Q1,Q2)(v, u),∀u, v ∈ V (4)
there exists a weighted undirected clique graph GC such that a random walk onH is equivalent to a random walk on GC with edge weights ω(u, v) = T(Q2)(u)F(Q1,Q2)(u, v)/T(Q1)(u) if T(Q1)(u) 6= 0 and 0 otherwise.
And the symmetrical Laplacian of GC is
L(u, v) = I{u=v} − T(Q2)(u) −1/2ω(u, v)T(Q2)(v) −1/2 (31)
where I{·} denotes the indicator function.
Proof. Form Lemma 2, we just need to prove Markov chain with state space V is reversible. The transition probabilities of the unified random walk on H are:
P (u, v) = ∑ e∈E w(e)ρ(δ(e))Q1(u, e)Q2(v, e) d(u) = F(Q1,Q2)(u, v) T(Q1)(u)
By equation 4, we have:
T(Q2)(u) F(Q1,Q2)(u, v) T(Q1)(u) = T(Q2)(v) F(Q1,Q2)(v, u) T(Q1)(v) ,
i.e.
T(Q2)(u)P (u, v) = T(Q2)(v)P (v, u),
Comparing with equation 12, we normalize G(Q2) to define the stationary distribution of M :
π(u) := T(Q2)(u)∑ u∈V T(Q2)(u) ,∀u ∈ V, (32)
which can be easy to verify by ∑ u π(u)P (u, v) = π(v). Thus, π(u)P (u, v) = π(v)P (v, u), which suggests that M is reversible. By Lemma 2, the edge weight ω(u, v) of GC is
ω(u, v) = cπ(u)P (u, v) = T(Q2)(u)P (u, v) = T(Q2)(u) T(Q1)(u) F(Q1,Q2)(u, v)
To gain the Laplacian of GC , we calculate the sum of row of edge weights matrix,∑ v∈V ω(u, v) = T(Q2)(u) T(Q1)(u) ∑ v∈V F(Q1,Q2)(u, v) = T(Q2)(u)
Then we get the symmetrical Laplacian of GC :
L(u, v) = I{u=v} − T(Q2)(u) − 12ω(u, v)T(Q2)(v) − 12 (33)

heading: G.3 PROOF OF THEOREM 1
text: Theorem 1 (Equivalency between generalized hypergraph and weighted undigraph) Let H(V, E ,W,Q1,Q2) denote the generalized hypergraph in Definition 2. When H satisfies any of the condition bellow:
Condition (1) Q1 and Q2 are both edge-independent; Condition (2) Q1 = kQ2 (k ∈ R), there exists a weighted undirected clique graph GC such that a random walk on H is equivalent to a random walk on GC .

heading: Proof.
text: 1) Proof based on Lemma 1 For condition (1), F(Q1,Q2)(u, v) = ∑ e∈E w(e)ρ(δ(e))Q1(u, e)Q2(v, e) = q1(u)q2(v) ∑ e∈E w(e)ρ(δ(e))H(u, e)H(v, e)
T(Qi)(u) = ∑ e∈E w(e)δ(e)ρ(δ(e))Qi(u, e) = qi(u) ∑ e∈E w(e)δ(e)ρ(δ(e))H(u, e), i = {1, 2}
(34)
Substituting the above equations into equation 4, then equation 4 holds.
For condition (2),
F(Q1,Q2)(u, v) = ∑ e∈E w(e)ρ(δ(e))Q1(u, e)Q2(v, e) = k ∑ e∈E w(e)ρ(δ(e))Q2(u, e)Q2(v, e)
T(Q1)(u) = ∑ e∈E w(e)δ(e)ρ(δ(e))Q1(u, e) = k ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(u, e) = kT(Q2)(u)
(35)
Similarly, substituting the above equations into equation 4, then equation 4 holds.
2 ) Proof based on Lemma 2 I) For Condition (1): Because Q1 and Q2 are both edge-independent, we set Q1(u, e) = q1(u) and Q2(v, e) = q2(v) for all hyperedge e. From Lemma 2, the key is to prove the unified hypergraph random walk on H under condition (1) is reversible (see Definition 4). It is hard to find the explicit form of π before we get Corollary 4. Fortunately, by Kolmogorov’s criterion, that is equal to prove:
pv1,v2pv2,v3 · · · pvn,v1 = pv1,vnpvn,vn−1 · · · pv2,v1
for arbitrary subset {v1, · · · , vn} ⊆ V . The transition probabilities of the generalized random walk on H are:
p(u, v) = ∑ e∈E w(e)ρ(δ(e))Q1(u, e)Q2(v, e) d(u) = q1(u)q2(v) d(u) ∑ e∈E w(e)ρ(δ(e))H(u, e)H(v, e)
= q1(u)q2(v)
d(u)
∑ e∈E(u,v) w(e)ρ(δ(e))
where E(u, v) = {e ∈ E : u ∈ e, v ∈ e} to be the set of hyperedges incident to both v and u. Then we have:
pv1,v2 · · · pvn,v1
= q1(v1)q2(v2) d(v1) ∑ e∈E(v1,v2) w(e)ρ(δ(e))  · · · q1(vn)q2(v1) d(vn) ∑ e∈E(vn,v1) w(e)ρ(δ(e))  =
( n∏ i=1 q1(vi)q2(vi) d(vi) ) ·  n∏ i=1 ∑ e∈E(vi,vi+1) w(e)ρ(δ(e))  , where set vn+1 = v1 = q1(v1)q2(vn) d(v1) ∑ e∈E(vn,v1) w(e)ρ(δ(e))  · · · q1(v2)q2(v1) d(v2) ∑ e∈E(v1,v2) w(e)ρ(δ(e))
 = pv1,vn · · · pv2,v1
So the unified random walk onH under condition (1) is reversible. As a matter of fact, we can succinctly obtain the reversibility via the stationary distribution. Specifically, we can verify the stationary distribution is
π(u) = ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(u, e)∑
v∈V ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(v, e)
(36)
by ∑ u π(u)P (u, v) = π(v). Then with π(u)P (u, v) = π(v)P (v, u) holding, we know our unified random walk on H under condition (1) is reversible. Since H is connected, the unified random on H is irreducible. From Lemma.2, We know that the current unified random walk onH is equivalent to a random walk on an undirected graph G with vertex set V . By equation 13, the edge weights of G are:
ω(u, v) = cπ(u)P (u, v) = ∑ e∈E w(e)ρ(δ(e))Q2(u, e)Q2(v, e) (37)
where c = ∑ v∈V ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(v, e). Note that P (u, v) > 0 if and only if ω(u, v) > 0, so G is the clique graph ofH. II) For condition (2) that Q1 = kQ2, we have P = kD−1v Q2Wρ(De)Q > 2 . Thanks to the underlying symmetry adjacency matrix of P (i.e. Q2Wρ(De)Q2 is symmetrical), we have: 1>D̂vP = 1>D̂>v . Thus, the stationary distribution is
π(u) = d̂(u)∑ v d̂(v) =
∑ e∈E w(e)δ(e)ρ(δ(e))Q(u, e)∑
v∈V ∑ e∈E w(e)δ(e)ρ(δ(e))Q(v, e)
(38)
Further, we would prove that the unified random walk onH under current condition (2) is reversible.
π(u)p(u, v) = d̂(u)∑ v′ d̂(v ′) ∑ e∈E w(e)ρ(δ(e))Q(u, e)Q(v, e) d(u)
= d(v)∑ v′ d(v ′) ∑ e∈E w(e)ρ(δ(e))Q(v, e)Q(u, e) d(v) = π(v)p(v, u)
So the unified hypergraph random walk onH under condition (2) is reversible. SinceH is connected, the unified random on H is irreducible. From Lemma.2, We know that the current unified random walk is equivalent to a random walk on a weighted, undirected graph G with vertex set V . By equation 13, the edge weights of G are:
ω(u, v) = cπ(u)P (u, v) = ∑ e∈E w(e)ρ(δ(e))Q(u, e)Q(v, e) (39)
where c = ∑ v′ d(v ′) = ∑ v∈V ∑ e∈E w(e)δ(e)ρ(δ(e))Q(v, e). Note that P (u, v) > 0 if and only if ω(u, v) > 0, so G is the clique graph ofH. On the whole, we get the specific equivalent weighted undigraphs under our condition (1) and condition (2). Note that they have the same edge weights expression ( equation 37,equation 39):
WC = Q2Wρ(De)Q > 2
which further suggests the connection between condition (1) and condition (2) stated in Corollary 4 and Thm. 1.
Remark: Let ρ(·) = (·)−1 and W = I, we can get the undigraph shown in Figure 1.

heading: G.4 NONEQUIVALENT CONDITION.
text: Theorem 4 There at least exists one generalized hypergraph H(V, E ,W,Q1,Q2) (Definition 2) with edge-dependent weights and Q1 6= kQ2, such that a random walk on H is not equivalent to a random walk on its undirected clique graph GC for any choice of edge weights on GC .
Remark. Theorem 4 tells that the random walk on a hypergraph can not be always equivalent to a random walk on an undigraph, and open up the possibility to construct a hypergraph is not equivalent to an undigraph, which may inspire researcher to further study for higher-order interactions and other insurmountable bottlenecks on hypergraphs.
Proof. When the vertex weights are edge-dependent, the reversibility is not always satisfied in our unified random walk on a hypergraph. By Lemma 2, if the unified random walk is not timereversible, it could not equivalent to random walks on digraphs for any choice of edge weights.
A irreversible example can see Figure 6. The probability transition matrix of the unified random walk on the left hypergraph (with W = I, ρ(·) = (·)−1) is given below:
P = D−1v Q1Wρ(De)Q > 2 = D −1 v Q1D −1 e Q > 2 =  1 3 1 3
1 3 0
1 6 5 12 7 24 1 8 1 6 5 12 7 24 1 8 0 12 1 3 1 3  , (40) and the stationary distribution of the unified random walk on hypergraph with P is:
π = [ 3
17 ,
7
17 ,
5
17 ,
2
17 ] (41)
We verify π(1)P ′(1, 2) = 317 × 1 3 6= 7 17 × 1 6 = π(2)P (2, 1), which indicates that the Markov chain represented by the unified random walk in Figure 6 with transition probabilities P is irreversible.
G.5 FAILURE CONDITION OF FUNCTION ρ.
As a matter of fact, the ρ in our random walk framework can not always work and we give its failure condition as follows.
Proposition 1 Let H(V, E ,W,Q) associated with the unified random walk in Definition 1. ρ(·) fails to work in our unified random walk if the hyperedge degrees are edge-independent (i.e. δ(e) = δ(e′),∀e′ ∈ E).
Proof. Given δ(e) are edge-independent, let us suppose δ(e) = k, then
P (u, v) = ∑ e∈E w(e)Q1(u, e)Q2(v, e)ρ(δ(e)) d(u) = ∑ e∈E w(e)Q1(u, e)Q2(v, e)ρ(δ(e))∑ e∈E w(e)δ(e)ρ(δ(e))Q1(v, e)
= ∑ e∈E w(e)Q1(u, e)Q2(v, e)ρ(k)∑ e∈E w(e)δ(e)ρ(k)Q1(v, e) = ∑ e∈E ρ(k)w(e)Q1(u, e)Q2(v, e) ρ(k) ∑ e∈E w(e)δ(e)Q1(v, e)
= ∑ e∈E w(e)Q1(u, e)Q2(v, e)∑ e∈E w(e)δ(e)Q1(v, e)
which indicates P (u, v) is independent to ρ(·), i,e. ρ(·) fails to work. It is obvious that the k-uniform hypergraph has edge-independent hyperedge degrees. Formally, we have the following proposition.
Proposition 2 Let H(V, E ,W,Q1,Q2) denote the generalized hypergraph in Definition 2 with ρ(·) = (·)σ and Q1 = Q2 = H , thenH is a k-uniform hypergraph(i.e each hyperedge contains the same number of vertices) if and only if P (u, v) in equation 3 is independent with σ. Proof. For Q = H, then δ(e) = ∑ v∈e h(v, e) = k. So, for all u, v ∈ V , we have:
K(σ)(u, v) := ∑ e∈E w(e)(δ(e))σqe(u)qe(v) = k σ ∑ e∈E w(e)H(u, e)H(v, e) (42)
Then we get the entries of the transition matrix P(σ):
P (σ)(u, v) := K(σ)(u, v)∑ bK (σ)(u, b) =
kσ ∑ e∈E w(e)H(u, e)H(v, e)∑
b∈V k σ ∑ e∈E w(e)H(u, e)H(b, e)
(43)
= ∑ e∈E w(e)H(u, e)H(v, e)∑
b∈V ∑ e∈E w(e)H(u, e)H(b, e)
(44)
It is easy to see that P (σ)(u, v) is independent with σ. The other direction, we find when P (σ)(u, v) in is independent with σ,then:
∂P (σ)(u, v)
∂σ =
∂d(u) ∂σ K (σ)(u, v)− ∂K (σ)(u,v) ∂σ d(u)
d2(u) (45)
=
∑ b ∑ e ∑ e′ w(e)w(e
′)h(u, e)h(u, e′)h(v, e′)h(b, e)δ(e)σδ(e′)σ(ln(δ(e))− ln(δ(e′))) d2(u) (46)
= 0,∀ u, v ∈ V (47)
It is equal to ∃k ∈ Z++ s.t.: δ(e) = δ(e′) = k for all e ∈ E
.i.e. the hypergraph is k-uniform. With the condition that Q1 = Q2 = H, our unified random walk on hypergraph reduces to a random walk on hypergraph that leaving only incident relationships between hyperedges and vertices. Actually, the reduced random walk mentioned is a common structure in real-world applications. The proposition is to say when the hypergraph based on the reduced random walk is uniform, the function ρ(·) does not impact the importance between vertices any more.

heading: G.6 PROOF OF COROLLARY 1.
text: Before proving the Corollary 1, we further illustrate the fact that Lemma 4 states.
Lemma 4 Let H(V, E ,W,Q1,Q2) be the generalized hypergraph in Definition 2. Given a H satisfying condition (1) in Thm. 1, there exists aH′ satisfying the condition (2) such that the random walk onH is equivalent to that onH′.
Proof of Lemma 4. When the condition (2) in Thm. 1 holds (i.e. Q1 = Q2), the transition probabilities of the unified random walk onH are
P c2(u, v) = ∑ e∈E w(e)ρ(δ(e))Q2(u, e)Q2(v, e)∑
e∈E w(e)ρ(δ(e)δ(e)Q2(u, e) (48)
Meanwhile, if the condition (1) in Thm. 1 holds (i.e. Q1,Q2 are both edge-independent), for all hyperedge e, we represent Q1(u, e), Q2(v, e) as q1(u), q2(v) respectively, and the transition probabilities are
P c1(u, v) = ∑ e∈E w(e)ρ(δ(e))Q1(u, e)Q2(v, e)∑
e∈E w(e)ρ(δ(e)δ(e)Q1(u, e) = q1(u)q2(v)
∑ e∈E w(e)ρ(δ(e))H(u, e)H(v, e)
q1(u) ∑
e∈E w(e)ρ(δ(e)δ(e)H(u, e)
= q2(u)q2(v)
∑ e∈E w(e)ρ(δ(e))H(u, e)H(v, e)
q2(u) ∑ e∈E w(e)ρ(δ(e)δ(e)H(u, e) =
∑ e∈E w(e)ρ(δ(e))Q2(u, e)Q2(v, e)∑
e∈E w(e)ρ(δ(e)δ(e)Q2(u, e) (49)
It can be observed that P c1(u, v) = P c2(u, v),∀u, v ∈ V . By definition 3, the Lemma 4 holds. Next, based on Lemma 4, we prove the following main conclusion.
Corollary 1 Let H(V, E ,W,Q1,Q2) be the generalized hypergraph in Definition 2. Let D̂v be a |V| × |V| diagonal matrix with entries D̂v(v, v) := d̂(v) := ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(v, e). No matter H satisfies condition (1) or condition (2) in Thm. 1, it obtains the unified explicit form of stationary distribution π and Laplacian matrix L as:
π = 1>D̂v
1>D̂v1 and L = I− D̂−1/2v Q2Wρ(De)Q>2 D̂−1/2v . (5)

heading: Proof of Corollary 1.
text: 1) Proof based on Lemma 1 When the generalized hypergraph satisfies Theorem 1, we obtain the equation 34 and equation 35 in Appendix G.2. substituting the equations into equation 33 and equation 32, we can obtain the Corollary 1.
2) Proof based on Lemma 4 We know whether H satisfying condition (1) or condition (2) in Theorem 1, there exists a weighted undirected clique graph GC equivalent to H. Recall Lemma 4, whenH satisfies any of the two conditions, the probability transition matrix P ofH can be denoted as:
P (u, v) = ∑ e∈E w(e)ρ(δ(e))Q2(u, e)Q2(v, e)∑ e∈E w(e)ρ(δ(e)δ(e)Q2(u, e)
Then, we obtain the unified form of probability transition matrix P under any of the two conditions:
P = D̂−1v Q2Wρ(De)Q > 2 (50)
where D̂v is a |V| × |V| diagonal matrix with entries D̂v(v, v) = ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(v, e) Remark the P is also the probability transition matrix of the equivalent undigraph in Theorem 1. Due to the symmetric adjacency matrix underlying P (i.e. Q2Wρ(De)Q>2 is symmetrical), it is easy to derive the unified stationary distribution π by 1>D̂vP = 1>D̂v . Thus, the stationary distribution is:
π = 1>D̂v
1>D̂v1
( π(u) =
d̂(u)∑ v d̂(v) =
∑ e∈E w(e)δ(e)ρ(δ(e))Q2(u, e)∑
v ∑ e∈E w(e)δ(e)ρ(δ(e))Q2(v, e)
) (51)
Substitute P and π into equation 20, we finally get the unified hypergraph Laplacian L as:
L = I− D̂−1/2v Q2Wρ(De)Q>2 D̂−1/2v Remark. The stationary distribution with edge-independent vertex weights in Chitra & Raphael (2019) can be seen as a special case of π in equation 51 by setting Q1 = H, Q2(u, e) = γ(u) and ρ(·) = (·)−1:
πCh(u) = γ(u) ∑ e∈E w(e)H(u, e)∑
v γ(v) ∑ e∈E w(e)H(v, e) = γ(u)dCh(u)∑ v γ(v)dCh(v)
where dCh(u) = ∑ e∈E w(e)h(u, e) is the definition of vertex degree in Chitra & Raphael (2019).

heading: G.7 SPECTRAL RANGE OF LAPLACIAN MATRIX
text: The following Theorem proves the upper bound for eigenvalues of L which meets the requirement of Chebyshev polynomials to enable the derivation for our proposed GHCN in Appendix F.1 and leads to Corollary . 2 in the paper.
Theorem 5 Let L = I − D̂−1/2v Q2Wρ(De)Q>2 D̂ −1/2 v denote the unified hypergraph Laplacian matrix in Corollary 1 and λ1 ≤ λ2 ≤ · · · ≤ λn denote the eigenvalues of L in order.
1) λmin = λ1 = 0 and u1 = D̂ 1 2 v 1(the eigenvector associated with λ1 )
2) For k = 2, 3, · · · , n, we have
λk = inf f⊥D̂ 1 2 v Sk−1
∑ e,u,v β(e, u, v)(f(u)− f(v))2∑
v f(v) 2d(v)
,
here, Sk−1 is the subspace spanned by eigenvectors {u1, · · · ,uk−1} where ui related to λi and β(e, u, v) = w(e)ρ(δ(e))Q2(v, e)Q2(u, e).
3) λmax = λn ≤ 2
Proof: To analyze the generalized Laplacian proposed in our work, we use the Rayleigh quotient mentioned in the Lemma 3 to give out some conclusions about the eigenvalues and eigenvectors of the Laplacian. 1) Deduce the Rayleigh quotient of L2:
g>Lg g>g = g>(I− D̂− 1 2 v Q2Wρ(De)Q > 2 D̂ − 12 v )g g>g
= (D̂
1 2 v f)>(I− D̂ − 12 v Q2Wρ(De)Q > 2 D̂ − 12 v )(D̂ 1 2 v f)
(D̂ 1 2 v f)>(D̂ 1 2 v f)
= f>(D̂v −QWρ(De)Q>)f
f>D̂vf
=
∑ u ∑ v ∑ e w(e)ρ(δ(e))Q2(v, e)Q2(u, e)(f(u)− f(v))2
2 ∑ v f(v) 2d̂(v)
where g = D̂1/2v f and f ∈ R|V|×1. It is easy to see the fact: R(L, g) ≥ 0 and R(L, g) = 0 if and only if f = 1 (i.e. g = D̂1/2v 1), Then with Lemma 3 we get λ1 = λmin = min
g R(L, g) =
R(L, D̂ 1/2 v 1) = 0 and u1 = D̂ 1 2 v 1. 2) From Courant–Fischer theorem (Horn, 1986), we have:
λk = inf g⊥Sk−1 R(L, g) = inf g⊥Sk−1
g>Lg
g>g
= inf f⊥D̂ 1 2 v Sk−1
∑ u ∑ v ∑ e w(e)ρ(δ(e))Q2(v, e)Q2(u, e)(f(u)− f(v))2
2 ∑ v f(v) 2d̂(v)
3) We have the fact:
(f(u)− f(v))2 ≤ 2(f2(u) + f2(v))
And from Lemma 3, we get:
λn = λmax = R(L,umax)
= inf f⊥D̂ 1 2 v Sn−1
∑ u ∑ v ∑ e w(e)ρ(δ(e))Q2(u, e)Q2(v, e)(f(u)− f(v))2
2 ∑ v f(v) 2d̂(v)
≤ inf f⊥D̂ 1 2 v Sn−1
∑ u ∑ e w(e)ρ(δ(e))δ(e)Q2(u, e)f(u) 2 + ∑ v ∑ e w(e)ρ(δ(e))δ(e)Q2(v, e)f(v) 2
2 ∑ v f(v) 2d̂(v)
≤ inf f⊥D̂ 1 2 v Sn−1
2 ∑ u d̂(u)f
2(u)∑ v d̂(v)f 2(v) = 2

heading: G.8 PROOF OF COROLLARY 2
text: Corollary 2 LetH(V, E ,W,Q1,Q2) be the generalized hypergraph in Definition 1. WhenH satisfies any of two conditions in Thm. 1, let L and π be the hypergraph Laplacian matrix and stationary distribution from Corollary 1. Let λH denote the smallest nonzero eigenvalue of L. Assume an initial distribution f with f(i) = 1 (f(j) = 0,∀ j 6= i) which means the corresponding walk starts from vertex vi. Let p(k) = fPk be the probability distribution after k steps unified random walk where P denotes the transition matrix, then p(k)(j) denotes the probability of finding the walker in vertex vj after k steps. We have:
∣∣∣p(k)(j)− π(j)∣∣∣ ≤ √ d̂(j)
d̂(i) (1− λH)k. (6)
Proof: From equation 50:
P = D̂−1v QWρ(De)Q > = D̂ − 12 v (I− L)D̂ 1 2 v
Then we have:
1>D̂vP = 1 >D̂v
Then the stationary distribution π ∈ R1×|V| of P can be denoted as:
π = 1>D̂v c
(52)
, where c = 1>D̂v1 = ∑ v∈V d̂(v) > 0 is the sum of 1 >D̂v . Let λ1 ≤ λ2 ≤ · · · ≤ λn denote the eigenvalues of L in order. Then we assume that fD̂− 1 2
v = n∑ i=1 aiũ > i ∈ R1×|V|, where ũi ∈ R|V|×1
denotes the l2-norm orthonormal eigenvector related with λi. From Thm .5, we know ũ1 = u1‖u1‖2 = D̂ 1 2 v 1√ c . Then a1 can be computed as:
a1 = ũ>1 (fD̂
− 12 v )>
ũ>1 · ũ1 = ũ>1 (fD̂ − 12 ) v ) > = (D̂
1 2 v 1)>(fD̂ − 12 v )>√
c = 1√ c
with the fact that f ∈ R1×|V| is a probability distribution(i.e. f1 = 1). Then,
|pj(k)− πj | = ∣∣(fPk)j − πj∣∣ = ∣∣∣∣∣(fPk − 1>D̂vc )j ∣∣∣∣∣ = ∣∣∣(fPk − a1ũ>1 D̂ 12v )j∣∣∣
= ∣∣∣(fD̂− 12v (I− L)kD̂ 12v − a1ũ>1 D̂ 12v )j∣∣∣ = ∣∣∣∣∣( n∑ i=1 aiũ > i (I− L)kD̂ 1 2 v − a1ũ>1 D̂ 1 2 v )j ∣∣∣∣∣ =
∣∣∣∣∣( n∑ i=1 aiũ > i (1− λi)kD̂ 1 2 v − a1ũ>1 D̂ 1 2 v )j ∣∣∣∣∣ = ∣∣∣∣∣( n∑ i=2 aiũ > i (1− λi)kD̂ 1 2 v )j ∣∣∣∣∣ ≤ (1− λH)k √ d̂(j)
∣∣∣∣∣( n∑ i=1 aiũ > i )j ∣∣∣∣∣ = (1− λH)k √ d̂(j) ∣∣∣(fD̂−1/2v )j∣∣∣ ≤ (1− λH)k
√ d̂(j)√ d̂(i)

heading: H GENERALIZED HYPERGRAPH PARTITION
text: For arbitrary vertex subset S ⊂ V , Sc denotes the compliment of S. We define the hyperedge boundary ∂S as ∂S := {e ∈ E | e ∩ S 6= ∅, e ∩ Sc 6= ∅}. We will generalize the hypergraph partition problem in Zhou et al. (2006) to our unified hypergraph framework. Hypergraph partition is to cut vertex set V into two parts S and Sc. As shown in Theorem 3, we are inspired to adopt the custom of directed graph normalized cut to formulate the hypergraph partition in a mathematical expression. We need to reuse the definition of vol(S) and vol(∂S) for directed graphs as:
vol(S) = ∑ u∈S π(u), vol(∂S) = ∑ u∈S ∑ v∈Sc π(u)P (u, v)
And the objective function of the hypergraph partition can be expressed as:
argmin ∅6=S⊂V c(S) := vol ∂S
( 1
vol(S) +
1
vol(Sc)
) . (53)
As we need the explicit form of stationary distribution to formulate this problem, we set the unified random walk on a hypergraph that satisfies with the conditions in Thm. 1. Then we have:
vol(S) =
∑ u∈S d̂(u)
vol(V) ,
vol(∂S) = 1 vol(V) ∑ e∈∂S ∑ u∈e∩S ∑ v∈e∩Sc w(e)ρ(δ(e))Q2(u, e)Q2(v, e)
= 1 vol(V) ∑ e∈∂S w(e)ρ(δ(e))m(e ∩ S)m(e ∩ Sc)
where m(e∩S) = ∑ u∈e∩S Q2(u, e) is a measure on the subset of V which explicitly demonstrates
the difference between Zhou et al. (2006) (where m(e ∩ S) = ∑ u∈e∩S H(u, e)) and our work. We considerate more fine-grained information on vertices when we establish a measure on arbitrary subset of V and involve the degree of hyperedges to impact the corresponding hyperedge weights rather than use the a priori hyperedge weights.

heading: I DETAILS OF EXPERIMENTS
text: Note that our GHCN and SHSC are both based on the Laplacian led by the equivalent condition in Thm .1, which means the vertex weights we use in our experimental datasets should satisfy the condition (1) or condition (2) in Thm. 1.

heading: I.1 HYPER-PARAMETER STRATEGY
text: We use grid search strategies to adjust the hyper-parameters of our GHCN and SHSC. The range of hyper-parameters listed in Table 6, Table 7, Table 8, and Table 9.
Extra parameter settings for Visual Object Classification include k = 6.

heading: I.2 BASELINES OF SPECTRAL CONVOLUTIONS
text: For HyperGCN (Yadati et al., 2019), we reproduce it by public code with the data already split (10 splits). But the result in its original paper is via running 1000 times with randomly split to get the best 100 times, which is not very common. Therefore, despite the HyperGCN is the SOTA method on Table 10, it can not achieve a competitive performance under the 10-splits.
For HGNN (Feng et al., 2019), in addition to the flaw during the derivation (i.e. use a specific matrix to fit the scalar parameter θ0), when doing the Visual Object Classification experiment in their public code, it also takes Gaussian kernel as the incidence matrix for hypergraph learning, which lacks theoretical guarantee. So in our experiment, we just use the incidence matrix H which only consists of elements {0, 1} as the incidence matrix using in HGNN. HGNN and HyperGCN we use the same grid search strategy as our method GHCN.

heading: I.3 CITATION NETWORK CLASSIFICATION
text: Datasets. The datasets we use for citation network classification include co-authorship and cocitation datasets: PubMed, Citeseer, Cora (Sen et al., 2008) and DBLP (Rossi & Ahmed, 2015). We adopt the hypergraph version of those datasets directly from Yadati et al. (2019), where hypergraphs are created on these datasets by assigning each document as a node and each hyperedge represents (a) all documents co-authored by an author in co-authorship dataset and (b) all documents cited together by a document in co-citation dataset. The initial features of each document (vertex) are represented by bag-of-words features. The details about vertices, hyperedges and features are shown in Table 10.
Settings and baselines. We adopt the same dataset and train-test splits (10 splits) as provided by in their publically available implementation1. Note that this dataset just has the edge-independent vertex weights H, which is also called the incidence matrix. So this experiment can be regarded as a special case of the specific application of our model (i.e. Q = H). For baselines, we include Multi-layer perceptron (MLP) which can be considered as the model without hypergraph structure, current state-of-the-art message-passing hypergraph framework UniGNN (Huang & Yang, 2021) and two recent spectral-based hypergraph convolutonal networks: Hypergraph neural networks(HGNN) (Feng et al., 2019) and HyperGCN (Yadati et al., 2019). For UniGNN, we reuse the results of UniGCN reported in (Huang & Yang, 2021), and for HGNN and HyperGCN, we reproduce them following Appendix I.2.
We use cross-entropy loss and Adam SGD optimizer with early stopping with patience of 100 epochs to train GHCN and SHSC. For other hyper-parameters, we use the grid search strategy. It is worth noting that the layer number of our model is K in equation 8. More details of hyper-parameters can be found in Table 6.
I.4 VISUAL OBJECT CLASSIFICATION
Datasets and Settings. We employ two public benchmarks: Princeton ModelNet40 dataset (Wu et al., 2015) and the National Taiwan University (NTU) 3D model dataset (Chen et al., 2003), as shown in Table 11.
In this experiment, each 3D object is represented by the feature vectors which are extracted by Multi-view Convolutional Neural Network (MVCNN) (Su et al., 2015) or Group-View Convolutional Neural Network (GVCNN) (Feng et al., 2018). The features generated by different methods can be considered as multi-modality features. The hypergraph structure we designed is similar to Zhang et al. (2018)( but they did not give spectral guarantees for supporting the rationality of their practices). We represent the hypergraph structure as a edge-dependent vertex weight Q to satisfy the condition (2) in Thm. 1 (i.e. Q1 = Q2 = Q). Specifically, we firstly generate hyperedges by k-NN approach, i.e. each time one object can be selected as centroid and its k nearest neighbors are used to generate one hyperedge including the centroid itself (in our experiment, we set k = 10). Then, given the features of data, the vertex-weight matrix Q is defined as
Q(v, e) =
{ exp(−d(v,vc)
γd̂2 ), if v ∈ e
0, otherwise, (54)
where d(v, vc) is the euclidean distance of features between an object v and the centroid object vc in the hyperedge and d̂ is the average distance between objects. γ is a hyper-parameter to control the flatness. Because we have two-modality features generated by MVCNN and GVCNN, we can obtain the matrix Q{i} which corresponds to the data of the i-th modality (i ∈ {1, 2}). After all the hypergraphs from different features have been generated, these matrices Q{i} can be concatenated to build the multi-modality hypergraph matrix Q = [Q{1},Q{2}]. The features generated by GVCNN or MVCNN can be singly used, or concatenated to a multi-modal feature for constructing the hypergraphs.
For baselines, we just compare with HGNN method for multi-modality learning, following the settings of Appendix I.2. We also compare our methods using two-modality features to recent SOTA methods on ModelNet40 dataset. And we use the datasets provided by its public Code 2. We use cross-entropy loss and Adam SGD optimizer with early stopping with patience of 100 epochs to train GHCN and SHSC. It is worth noting that the layer number of our model is K in equation 8. More details of hyper-parameters can be found in Table 6.

heading: I.5 PROTEIN QUALITY ASSESSMENT AND FOLD CLASSIFICATION
text: Protein hypergraph modeling. At the high level, a protein is a chain of amino acids (residues) that will form 3D structure by spatial folding. In order to simultaneously consider protein sequence and spatial structure information, we build sequence hyperedge and distance hyperedge. Specifically, given a protein with |S| amino acids, we choose τ consecutive amino acids (vi, vi+1, · · · , vi+τ ) to connect to form a sequence hyperedge and choose amino acids whose spatial Euclidean distance is less than a threshold > 0 to connect to form a spatial hyperedge, where vi(i = 1, · · · , |S|) represent the i-th amino acid in the sequence. Let Es and Ee denote sequence hyperedge and spatial hyperedge, respectively. Then, we design an edge-dependent vertex-weight matrix Q for capturing the more granular high-order relationships of proteins below (actually, our
1https://github.com/malllabiisc/HyperGCN, Apache License 2https://github.com/iMoonLab/HGNN, MIT License
models GHCN and SHSC allow one to design a more comprehensive Q for learning proteins better):
Q(v, e) =  1, if v ∈ e and e ∈ Es exp(−d(v,vc) γd̂2vc
), if v ∈ e and e ∈ Ee 0, otherwise
(55)
where d(v, vc) < is the euclidean distance between an amino acid v and the centroid amino acid vc in the hyperedge and d̂vc is the average distance between vc and the other amino acids {vi}i 6=c. γ is a hyper-parameter to control the flatness. Here we just design an edge-dependent vertex-weights matrix Q for satisfying the condition (2) in Thm. 1 (i.e. Q1 = Q2 = Q). Note that this Q matrix pays more attention to the information of the sequence (Figure 7).
Experimental settings In our experiment, we set τ = 6 and = 8Å. The initial node features, following Baldassarre et al. (2020), are composed of amino acid types and 3D spatial features including dihedral angles, surface accessibility and secondary structure type generated by DSSP (Kabsch & Sander, 1983). Note that both Quality Assessment and Fold Classification include graph-level tasks, which means we should add global pooling layers to readout the node representations from our GHCN or SHSC.
Here, for the sake of simplicity, we adopt the permutation-invariant operator mean pooling and a single layer MLP as Readout layers to obtain a global hypergraph embedding and add the softmax (classification) or sigmoid (regression) activation function before output.
Protein QA is used to estimate the quality of computational protein models in terms of divergence from their native structure. It is a regression task aiming to predict how close the decoys to the unknown, native structure. Inspired by Baldassarre et al. (2020), we train our models on Global Distance Test Score (Zemla, 2003), which is the global-level score, and the Local Distance Difference Test (Mariani et al., 2013), an amino-acids-level score. The loss function of QA is defined as the
Mean Squared Error (MSE) losses:
Lg = MSE(Pgpred −GDT TS) Ll = |S|∑ i=1 MSE(P lpredi − LDDTi) (56)
where Pgpred and P lpred denote predicted score of global and local respectively.

heading: I.5.1 PROTEIN QUALITY ASSESSMENT (QA)
text: Dataset and settings We use the data from past years’ editions of CASP, including CASP1013. We randomly split the CASP10, CASP11, CASP13 for training and validation, with ratio training: validation = 9:1. CASP 12 is set aside for testing against other methods. More details about the datasets can be found in Table 13. For the baseline, we compare our methods with other start-of-the-art methods, including random walk-based methods : RWplus (Zhang & Zhang, 2010), sequence-based methods: AngularQA (Conover et al., 2019), and 3D structrue-based methods: VOroMQA (Olechnovivc & Venclovas, 2017), 3DCNN (Derevyanko et al., 2018). The results of these baselines we reused from Baldassarre et al. (2020) reports. Another baseline HGNN (Feng et al., 2019) is reproduced by us with same training strategy as our methods.
Because our hypergraph based methods can jointly learn node and graph embeddings, the losses in equation 56 can be weighted asLtotal = µLl+(1−µ)Lg and co-optimized by Adam Optimizer with L2 regularization, where µ = 0.5 in our experiment. We use grid search to select hyper-parameters and more details can be found in Table 8.
In addition, we use CASP10-12 for training and valuation, CASP 13 for testing to further evaluate the efficiency of our methods (the range of hyper-parameters can see Table 9), and the results are shown in Table 12.

heading: I.5.2 PROTEIN FOLD CLASSIFICATION
text: Datasets and settings The dataset that we used for training, validation and test is SCOPe 1.75 data set of Hou et al. (2018). This dataset includes 16,712 proteins covering 7 structural classes with total of 1195 folds. The 3D structures of proteins are obtained from SCOpe 1.75 database (Murzin et al., 1995), in which each protein save in a PDB file. The datasets have three test sets: 1) Fold, where proteins from the same superfamily do not appear in the training set; 2) Family, in which proteins from the same family are not present in the training set; 3) Family, where proteins from the same family that are present in the training set.
For baselines, we include sequence-based methods pre-trained unsupervised on millions of protein sequences: Rao et al. (2019); Bepler & Berger (2018); Strodthoff et al. (2020), 3D structure based model: Kipf & Welling (2017); Diehl (2019); Baldassarre et al. (2020) and Gligorijevic et al. (2020), who process the sequence with LSTM first and then apply GCNN. The accuracy of the above baselines is reused from Hermosilla et al. (2021) reported. We adopt Adam optimizer to minimize the cross-entropy loss of our methods. Hyper-parameters search range can see Table 7.

heading: I.6 OVER-SMOOTHING ANALYSIS.
text: Table 14 shows that our proposed SHSC significantly alleviates the performance descending with the increase of layers. Given the same layers, it can be observed that our SHSC almost outperforms the other methods for all cases, especially at a deep layer, which demonstrates the benefits of deep model and the long-range information around hypergraph. Furthermore, It should be noted that the optimal layer numbers K of our SHSC are generally larger than other models, due to the only one
linear layer avoids the over-fitting problem. These results also reveal that HyperGCN, HGNN and our GHCN all suffer from severe over-smoothing issue, limiting the power of neural network to capture high-order relationships.

heading: I.7 SENSITIVITY ANALYSIS
text: The proposed SHSC model performance on co-authorship Cora, co-citation cora and co-citation Pubmed with different σ, β and α is reported in Figure 8. For σ, we can see that the best choice will vary depending on the data set but mainly concentrated around −0.5, which verify that the effect of hyperedges degree is various and it has a negative effect in most cases. For β, with the growth of β, the performance of SHSC stably increases, which means that the diffusion kernel is useful for information aggregation. Moreover, the fact that the performance remains stable on cora (coauthorship) and pubmed (cocitation) when β is at 0.8-1.0 suggests we can only adjust this hyper-parameter at a range of large value. For α, the tendency of it is similar to β, so we can also adjust this hyper-parameter at a range of large value to obtain a satisfying performance.

heading: I.8 THE SPECTRUM ANALYSIS OF SHSC
text: We calculate the eigenvalues of ( β ∑K k=1 αk K T̃ k + (1− β)I ) with various (α, β) on NTU2012 dataset (|V| = 2012) and count the number of eigenvalues in different size ranges, which is shown
in the Table 15. The table suggests that our SHSC is able to capture both low and high frequency information of the graph signal, depending on the selection of the appropriate hyper-parameters (α, β).

heading: I.9 ABLATION ANALYSIS
text: In order to verify the effectiveness of our proposed edge-dependent vertex weight Q and the necessity of re-normalization trick, we conduct an ablation analysis and report the results in Table 16. Specially, w/o Q is a variant of our methods that replaces the edge-dependent vertex weight Q with the edge-independent vertex weight matrix H. w/o renormalization represents the variants without re-normalization trick. Form the reported results we can learn that both Q and renormalization are efficient for hypergpraph learning, respectively. Moreover, on Cora and Pubmed, the performance gap between w/o renormalization and with both GHCN reveals the advantage of renormalization on disconnected hypergraph dataset. This phenomenon is mainly caused by the row in the adjacent matrix corresponding to an isolated point is 0 (Figure 4), resulting in a direct loss of its vertex information (Figure 4). And the renormalization trick adding the self-loop to matrix K can maintain the features of isolated vertices during aggregation. Compared with GHCN, the performance impact of renormalization on SHSC seems to be smaller. This is because we add initial features to the information gathered by the neighbors, which reduces the information loss of isolated vertices.
I.10 EXAMPLES OF ρ
We give many examples for ρ, including random, x−1, sigmoid(x) , 1√ 2σ exp(− (x−x̄)
2
2σ2 ), log(x) ,exp(x) and exp(−x), and the experimental results on citation networks can be seen the table 17 . Regarding learnable ρ, we will do as a future work.

heading: I.11 RUNNING TIME AND COMPUTATIONAL COMPLEXITY
text: Firstly, we analyze the theoretical computational complexity of our GHCN and SHSC: For GHCN, the computational cost is the O(|E|d), where |E| is the total edge count in equivalent undigraph. Each sparse matrix multiplication T̃X costs |E|d. And the computational of HGNN is the same as GHCN. For SHSC, the computational cost is the O(K|E|d + K|V|d), which includes K sparse matrix multiplication andK summation over filters(|V|d is the cost of adding featuresX). Then, we compare the running time between our GHCN and SHSC with existing models in Table 18 and the results illustrate that our methods are of the same order of magnitude as SOTA’s approach UniGNN and outperform the HyperGCN and HGAT.

heading: I.12 THE EDGE-DEPENDENT VERTEX WEIGHTS VISUALIZATION
text: I.12.1 VISUAL OBJECT.

heading: I.13 ADDITIONAL EXPERIMENTS OF BASELINES.

Review summaries:
In this paper, the authors aim at building the equivalency between hypergraphs and undirected graphs. They introduce the concept of generalized hypergraphs and demonstrate their equivalency with undirgraphs in terms of random walk. They further proposed two spectral-based convolution operations for the undigraphs.  

This paper considers the problem of showing equivalency of Generalized Hypergraphs to undirected graphs (in the sense that a natural random walk on the hypergraph is equivalent to the natural random walk on a weighted undirected clique graph). They do so via establishing a Hypergraph Laplacian and identifying its properties that help prove this equivalence. They leverage this equivalency to build a Hypergraph  convolution neural network by viewing the weighted undirected graph as a lower-order encoder of hypergraphs. They use empirical studies to show that the constructed Hypergraph Convolution NN on four different network based classification task, where the underlying network structure forms a hypergraph.

This paper proves under what conditions the equivalency between a generalized hypergraph (a hypergraph with node weights $Q_1$ and $Q_2$ for two-step random walk) and an undirected graph holds. The theory applies to ordinary hypergraphs as a special case with $Q_1=Q_2=H$. Then, the authors derive the stationary random walk distribution, the hypergraph Laplacian, as well as the generalized spectral hypergraph convolution form leveraging the Laplacian. To alleviate oversmoothing, they further propose to use a diffusion kernel to build a simple hypergraph spectral convolution. Experiments on four tasks show better performance than state-of-the-art methods.

Real-world relational datasets (e.g., academic data, protein data) contain group relationships and can be modelled via hypergraphs.  One way to capture group higher-order relationships is to define a hypergraph with edge-dependent vertex weights (EDVWs) and such a hypergraph has been shown to be equivalent to directed graphs [Chitra et al., ICML'19]. The main contributions of this paper are: 1) Proposal of a generalised hypergraph capturing EDVWs with equivalence to undirected graphs, 2) Proposal of a Laplacian based on the generalised EDVW and exploration of existing spectral convolutional methods, and 3) Empirical evaluation on academic, protein, and visual object datasets.