Hypergraph Convolutional Networks via Equivalency  between  Hypergraphs and Undirected Graphs
Authors: Jiying Zhang
Fuyang Li
Xi Xiao
Tingyang Xu
Yu Rong
Junzhou Huang
Yatao Bian
Venue: ICLR 2022 Submitted (2022)
Keywords: hypergraph learning
equivalency of hypergraph
graph neural networks

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 long-range 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.

Under review as a conference paper at ICLR 2022
HYPERGRAPH CONVOLUTIONAL NETWORKS VIA EQUIVALENCY BETWEEN HYPERGRAPHS AND UNDI- RECTED GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
As a powerful tool for modeling the complex relationships, hypergraphs are gain- ing popularity from the graph learning community. However, commonly used algorithms in deep hypergraph learning were not specifically designed for hy- pergraphs with edge-dependent vertex weights (EDVWs). To fill this gap, we build the equivalency condition between hryerrypegsapphs and undirected sim- ple 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 unified random walk framework, under which present the equivalency condi- tion 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 long- range interactions and alleviate the over-smoohhing issue, we further propose the Simple Hypergraph Spectral Convolution (SHSC) model by constructing the Dis- counted Markov Diffusion Kernel from our random walk framework. Extensive experiments from various domains including social network analysis, visual ob- jective classification, and protein fold classification demonstrate that the proposed approaches outperform state-of-the-art spectral methods with large margin.
INTRODUCTION
Hypergraphs, whose edges link to the arbitrary number of vertices to model high-order relation- ships, attract much attention recently from researchers in the graph learning community (Feng al., 2019; Jiang et al., 2019; Zhang 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, edge- independent and cdge-dependent (Chitra & Raphael, 2019; Hayashi et al., 2020), depending on whether the vertex weights related to the incident hyperedges not (EDVWWhypergraphh implies that each vertex u is assigned a weight ge (v) E IR. for each incident hyperedge e). Many hypergraph neural networks have been proposed (Feng
al., 2019; Jiang 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-hypergraphh) is still lacked, though they enjoy stronger expressive power (Ding & Yilmaz, 2010; Huang et al., 2010: Li al., 2018a: 8a; Zhang et al.. 2018).
In this work, we are devoted 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 hhyerhhpesgspphs is equivalent to digraphs. Though digraph convolutional networks can be directly used for EDVW- hypergraphs, most existing convolutional algorithms for digraphs are more or less related to undi- rected 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 directed graph Laplacian. In addition, key theoretical analysis of digraph convolutional networks properties,
based methods, which are considered to be robust and to

---

Under review as a conference paper at ICLR 2022
Hyyorgraph
Undiratted Clique Graph
Q.
11
d de (8)
4 4
0
WC
16
10
Y64 -1
6 3
1
An example of hypergraph and its equivalent weighted undirected graph (w (WC)T) where q'()) = (i(,,), E (1, Here, Q = Q2 are both edge-dependent. The characteristics of the hypergraph are encoded the weighted incidence matrices (i.c. vertex weights) Q1 Q2. W Q2D, 'Q denotes the
Figure I:
matrix of the clique graph and can be viewed as the embedding of high-order relationships.
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 EDDVW-hypegnaad learning is to use undigraph convolutional networks. Compared with digraphs, the undígraph convolutional networks have been extensively studied and there exist various effective strategies for analyzing their properties, to name few (Kipf & Welling. 2017: Chen et al., 2020; Zhu & Koniusz, 2021). Furthermore, one can take established hyper-
techniques undigraphs graph learning in real-world scenarios. It remains unclear, however, whether EDV Whyyerrrggsss can be made equivalent to undigraphs in a principled way, thereby hindering this promising prospect.
subroutine for hypergraph learning, which would largely
In this paper, we focus on constructing the equivalency condition between hypergraphs and undi- graphs. This makes it possible 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 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 unified Laplacian from the equivalency conditions and propose two spectral con- volution models (GHCN, SHSC) for EDWW-hypergraphs learning. We analyze the over- wer-shnothing issues (Li al., 201 8b) based on their spectral properties deduced from equivalency conditions.
3) Extensive experiments across various domains (social network analysis, visual objective classi- fication and protein modeling) demonstrate the effectiveness of the proposed methods (GHCN and SHSC) for both EIV 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.
2 THE THEORY OF EQUIVALENCY
Notations. I E Rax= denotes the identity matrix, and E IR" represents the vector with ones in each component. We use boldface letter x E IR" to indicate an n-dimensional vector, where z(1) is the 1th entry x. We use a boldface capital letter A |Rmxx to denote an m by matrix and use A(i, (( to denote its i7th entry.
Co
Up
②
Let G(V, E,W) be a graph with vertex set V, edge set E, and edge weights w. Let H(V, W. Q) be the hypergraph with vertex set V. edge set E. Let wi(e) denote the weight of hyperedge e. W E [|E| is the edge-weights diagonal matrix with entries ((e, = w(e). Q denotes ddge-vertex-weigee
Figure Hypergraph Random Walk. ① denotes the first step and represents the second.
matrix with en- tries ((u,e) = (u) E R if u E e and 0 if u. & e. Q is said to be edge-independent if (u) q()) E R for e 3 u, and called edge-dependent otherwise (Chitra & Raphael, 2019). If (e()) equals to I for all linked u and .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 weighted incident matrix. Note that graph is a special case of a hypergraph with hyperedge degree |e] = 2. We say hypergraph is connected when its unweighted clique graph (Chitra & Raphael, 2019) is
2

---

any undigraph technique be used subroutine for Under review as a conference paper at ICLR 2022
connected and assume hypergraphs connected. Throughout this paper, equivalency refers to equivalency between hypergraphs and undigraphs if not otherwise specified.
2.1 UNIFIED RANDOM WALK AND GENERALIZED HYPERGRAPISS
Traditionally, hypergraph random walk is defined by two-step manner (Zhou et al., 2006; Ducour- nau & 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 EDVW- hypergraphs and digraphs. However, due to the limitation of their hypergraph definition, they fail to answer whether the EDDW-hypergrapph 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 generalized hypergraph.
Definition (Unified Random Walk on Hypergraphs)
The unified random walk on a hypergraph H is defined in a two-step manner: Given the current vertex
Step I: choose an arbitrary hyperedge e incident to u, with the probability
w(e) Evey Qz(u, e)plL Q2(v, Qz(v.e))Qi(u,e) ErEE w(e) EvEV Q2(u, e Qu(v.e))Qilu.e)
(1)
Step II: choose an arbitrary vertex v from e, with the probability
Q2(v,e)
P2 Evev Q2(v,e)'
where w(e) denotes the hyperedge weight; Qi e) denotes the contribution of vertex u to hyper- edge e in the first step while Q2(v,e) e) represents the contribution of verlex v to hyperedge e in the second step; and pl-) is real- fanction, for example, a power function (.)%.
Suppose 8(e) =
Evey Q2( is the degree of hyperedge, and d(v)
Eese ((()) (v,,e) the degree of vertex v. The transition probability of our unified random walk hypergraph from vertex to vertex is:
((,))Qi(u,e))ddl (u(1ee))(((
P(u,e) Σ
(3)
d(u)
.EE
where D.,. D. are diagonal matrices with entries (v, d(r) and (e(e,e) = 5(c), respectively. p(D.) represents the function p acting on each element of D.. Notably, the p 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 found Appendix B.2.
Here, P(u, v) can be written in a [V] | matrix form: P p= Q,
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 pl, 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, W W--hyerrgraphs and undigraphs follows.
Definition (Generalized hypergraph)
generalized hypergraph a hypergraph associated with the unified random walk in Definition 1, denoted as E W, W,Q1,00 Q2). Here, Q Q2 are vertex weights matrices, each of which can be edge-independent or edge-dependent
2.2 THE EQUIVALENCY BETWEEN HYPERGRAPHS AND UNDIGRAPHS
In this part, provide the condition under which the generalized hypergraph is equivalent to weighted undirected clique graph. By establishing the equivalency, we can view graphs as low- order encoders of EDV Wow-yyyrgggapphs hypergraph learning.
The clique graph of H(V,E, W, Q1, Q2) is denoted go, which is unweighted graph with vertices and edge set {u, v) u, v E e, E E}. Actually, go turns all hyperedges into cliques. We first present the definition of the equivalency in connection with Markov chains.
3

---

Under review as a conference paper at ICLR 2022
(Chitra & Raphael (2019)) Let M1, M2 be the Markov chains with the same finite state space, and let PM1 and MM2 be their probability transition matrices, respectively. M1, M2
Definition 3
equivalent if P = P for all states u and
The equivalency between digraph and hypergraph is straightforward and we defer to Appendix E. On the other hand, it is easy understand that any simple undigraph can be constructed as a special generalized hypergraph, while the converse is not necessarily true. We provide coun- terexample in Appendix G.4, This result implies that undi- graph convolutional networks can not trivially be extended to generalized hypergraphs. So, we give one of the implicit equations for formulating the equivalency problem to ex- plore the explicit equivalency conditions.
Edge-indeeendenn
Edge-independent n (Q; # kQ₂)
(Qq kQ22)
dependent
Edge dependent n nQ # kQ₂))
n n(Q = kQ₂)
Figure 3: The division Equivalency
Lemma Let H(V,&, W, W,Q,, Q2) denote the general- ized hypergraph in Definition 2. Let F(Qu.Q.)(u,)) ==
problem (undigraph). The blue box indi- cates condition (1) in Thm. 1 and red box indicates condition (2). The dark blue part is still open yet.
Eceg w(e) (((e)) (u, () and [(q)(u) =
Eecr ((ee)))())((()))() (e),.. When Q2, Q2 satisfies the following equation
(o.)(u)Tio,)()EF (,) =
(2) u), Vu,
(4)
there exists a weighted undirected clique graph G such that a random walk on H. is equivalent to random walk on G with edge weights w(u, v) 0 and 0 otherwise.
if (TQ +
The proof can be found in Appendix G.2. Next, derive the explicit condition under which random walks on hypergraphs are equivalent to undigraphs.
Theorem (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) Q and Q2 are both edge-independent; Condition (2) Q = k: kQ (k E IR),
there exists weighted undirected clique graph gC such that random walk H. is equivalent to a random walk on ge.
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 the unity of our random walk and the generalization of hypergraph defined (Figure 3). Notably, Chitra & Raphael (2019) shows that the cquivalency condition is: Q1 = and Q2 is edge-independent, which can be viewed lency 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 pro- portional. Furthermore, thanks to the introduced Q 2 in the generalized hypergraph, we can obtain the equivalency between HDDWW-hypeggrahh and undigraph (i.e. condition (2) ). filling important gap in the equivalency theory of EDV W-hypergrapphh. ii) Providing a theoretical basis for hyper- graph applications. The condition (2), containing both the edge-independent vertex weights and edge-dependent vertex weights cases which match different hypergraph applications (Ding & Yil- maz, 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 HDDV-hyyergrayp can be equivalent an undigraph, gives the theoretical guarantee for learning hypergraphs without losing edge-dependent vertex weights via undigraph neural networks. Next, provide the spectral theory for the generalized hypergraphs.
special case of the condition (I), while Theorem implics the equiva-
4

---

Under review as a conference paper at ICLR 2022
2.3 GENERALIZED HYPERGRAPH LAPLACIAN AND ITS SPECTRAL PROPERTIES
To build bridge between spectral convolution and equivalency, we derive the equivalent undirected weighted graph Laplacian based Lemma and Thm 1. Then the graph Laplacian can be consid- ered 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 Let H(V, E, W, Q1, Q2) be the generalized hypergraph in Definition 2. Let D, be [V] x [V] diagonal matrix with entries Dv(v, v) == d(v) == Lees ((()))()))(())))((()) e). No matter H. satisfies condition (1) or condition (2) in Thm. it obtains the unified explicit form of stationary distribution π and Laplacian matrix L as:
D.
and L I 1/2 W (P(())) D
(5)
D
There are two observations from Corollary 1: (i) This stationary distribution is different from the classical π (v) = d(u)/E, d(v) (Zhou et al., 2006), which depends on the vertex degree d(v). Our (v) is related to d((r). which means that we cannot trivially extend from classical theory. The de- tailed proof 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 * Q2) to construct a hypergraph. Meanwhile, L can be viewed as a normal- ization Laplacian led by the equivalent undigraph G with adjacency matrix Q2 Q2Wpl( DPD)) based spectral convolutions.
on which we can design the EDVW-hypergres
Corollary implies that matter Q1, Q2 are both edge-independent Q Q2. use the Laplacian matrix to analyze the spectral properties. The spectral properties of Lapla- cian (Chung & Graham, 1997) are vital in the research of graph neural networks to design 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)
directly
Corollary Let HOVEE, &, W, Q1, Q2) be the generalized hypergraph in Definition 1. When H satis- fies any of two conditions in Thm. 1, let L and a be the hypergraph Laplacian matrix and stationary distribution from Corollary
Let 2Ø denote the smallest nonzero eigenvalue of L. Assume an initial distribution f with f()
(f() 0, + i) which means the corresponding walk starts from vertex Us. Let ( fp* be the probability distribution after k steps unified random walk where P denotes the transition matrix, then p (j) denotes the probability of finding the walker in vertex Uj after i steps. We have:
(()) d(i) (1 (1-An)*
(6)
For hypergraph learning, Corollary 2 implies that the spectral convolution deduced from the Lapla- cian in Corollary might suffer from the over-smoothing issue (Zhu Koniusz, 2021). Appendix F.4 gives theoretical perspective for analyzing the over-smoothing issue based on this Corollary, which further inspires the design of convolutions Section to alleviate the issue.
TWO SPECTRAL CONVOLUTIONS FOR HYPERGRAPHS
Intuitively, there are two possible routes for designing EDVW-hypergrapp neural networks: 1. mes- sage 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 lack of theoretical guaran- tees (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 al., 2019), but also effectively inspires the design of message passing techniques (Xu al., 2019).
5

---

Under review as a conference paper at ICLR 2022
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 equiva- lency conditions, algorithms deduce by L would be adaptive to any generalized hypergraph satisfied Thm. I, including ElVW-hypergraph and EDVW-hypergraph.
3.1 GENERALIZED SPECTRAL HYPERGRAPH CONVOLUTION
We denote K as Q2W)(D.)Q for expression simplicity. Then the unified hypergraph Lapla- cian matrix L in Corollary 1 can be expressed as L I - D, KD, Similar to Defferrard al. (2016), we approximate the convolutional kemel with Chebyshev polynomial to avoid eigen- value decomposition of L. Finally, the following Generalized Hypergraph Convolutional Network (GHCN) is obtained by introducing the re-normalization technique (Kipf & Welling, 2017):
((+1) (Tx O)),
where : "D, and K = + can be regarded as the weighted adjacency matrix of the equivalent undigraph with self-loops, and D(u, v) = Eney K(u, 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 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 EIV Whyprrrpsgss and EDVW- hypergrpahs. Besides, the unity of random walk makes it possible to aggregate more fine-grained information. Note that HGNN (Feng al., 2019) can be viewed as a specific case of GHCN without the re-normalization trick (p(-) = (-) Q H).
However, Corollary indicates that initial signals or features intend to converge to certain vector, causing vertices hard to distinguish between each other. This implies that GHCN also suffers from over-smoothing issue (Iii et al., 201 8b), 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.
3.2 A SIMPLE SPECTRAL CONVOLUTION BASED ON MARKOV DIFFUSION KERNEL
In order to aggregate long-range information, we propose the discounted Markov Diffusion process aggregate the information of vertices and propose a new convolutional architecture for hyper- graphs.
Discounted Markov Diffusion Kernel for Hypergraphs. A diffusion process on generalized hypergraph can be understood as a process of information extracting among vertices. To generate the underlying feature map (t))), we first utilize the transition probabilities of the Markov chain in Definition to design a discounted average visiting rale: ūza (L) = Er= a" Pr(s(7) = k=|=(0=
i), where E Z++ Notably, we introduce discount factor a E (0, 1] to exponentially weaken the long-step transition probabilities from vertex i to vertex k. Specially, we set T.u (0) = 1 if and only i = k, otherwise 7. (0) = 0. Assume that vt) = (t)) ... (t))
T. Then, we adopt the diffusion distance de (t) = [[v (0) [ (t) - (0) proposed in Pons & Latapy (2005) to generate our discounted Markov diffusion kernel K (I) = Z()) (1). where Ztt)= = Σr ='pr can be viewed as the weighted sum of the transition matrix (derivation in Appendix F.2). The intuition behind this diffusion distance is that 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 the hypergraph is considered in similar manner.
Simple Hypergraph Spectral Convolution (SHSC). Inspired by the diffusion kernel-based GC- NNs from Zhu & Koniusz (2021), based on our discounted Markov diffusion kernel, we propose a Simple Hypergraph Spectral Convolution (SHSC) as follows:
((
K
Y =
T
+ (1
B)1
X@
(8)
K
k=
6

---

Under review as a conference paper at ICLR 2022
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 hyperparameter B [0. 1] to control the self-loops (T)o I. Through the discounted Markov Diffusion process, our SHSC could gain stronger local and weaker global information, thereby im- proving 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 spatial baasd model while we can analyze from a spectral-based perspective, as SHSC can be viewed as polynomial filter with specific coefficients (see Appendix F.3). Finally, we study why SHSC can relieve over-smoothing. Specifically, we utilize Corollary 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 multi-laye GHCNs (details in Appendix E.4).
Table I: Summary of classificaiton accuracy(%) results. We report the average test accuracy and its standard deviation over 10 train-test splits. The number in parentheses corresponds to the number of layers of the model. (OOM: our memory)
Cora (co-authorship)
DBLP (co-authorship)
Cora (co-citation)
Pubmed (co-citation)
Citeseer (co-citation)
Dataset
Architecture
MLP
52.02:11.7
78.72:10.6
52.02=1.7
69.86111.
55,03
HyperGCN
spectral-bused
60.66=10.8 10.8
84.8249.7
62.35-9.3
68. 12297.7
66.9426.3
HGNN
beaetral-based
69.23=#1.6
88.55=+0,18
55.60=1.8
46,41=0.7
38.98=1. 1.1
HNHN
message-passing 63.95.12.4
84.43-10.3
41.59=3.1
41.9414.7
33.6012.1
HGAT
ceessage-passing
65.42:11.5
0OM
52.21=3.5
46.28:10.53
38.32:1..5
UniGNN
message- passing
1..
88.80=0.2
70.10=14
74.40=1.0 1.0
63.60=1.3
SSGC
ppectralbbssdd
12.04:1.2
88.6110.116
68.79-2.1
1..49
60.5221.7
GHCN (ours)
ppeetral-based
74.79=0.91
89.04=0.119
69.45+2.00
75.37=1.2
62.67=1.2
SHSC (ours)
spectral-based
76.05=00.5(6)
09.17
70.64+1..8 (32)
7..08=
65.14=00.7(32)
4 EMPIRICAL STUDIES
In this section, we evaluate our proposed meth- ods four tasks: citation network classification, visual object classification, protein quality assess- ment (regression), and fold classification. For sim- plicity, we set p(-) to be a power function (-)o (a is syper-parameter) and additional experi- ments to compare the performance with different p deferred to Appendix I.10. The weight ma- trix of edges, we set, to be an identity matrix by default in our GHCN and SHSC models. No- tably, although GHCN and SHSC are designed for EDVW-hypergraph learning, they work for EIVW- hypergraph as well thanks to the unified Laplacian in Corollary 1. In our experiments, citation net- work classification belongs to EIVW-hypergraph learning tasks, and visual object classification and protein learning are EDVVWhhyergrrg learn- ing tasks. For baselines designed for hhyerrpgggg,,h, we replace Q1, Q2 with H.
Table 2: Classification accuracy (%) on Model-
Net40. The embedding means the output represen- tation MVCNN+GVCNN Extractor.
Methods
input
Accuracy
MVCNN (Feng ct al., 2018)
image
90.1
PointNet (Qi ct al., 201
point
89.2
PointNett++ (Qi al., 2017b)
point
90.1
DGCNN (Wang ct al., 2019)
point
92.2
InterpCNN (Mao et al., 2019)
point
93.0
View (Uy al., 2019)
image
93.6
pAConv (Xu et 2021)
point
93.9
HIAT (Ding et al., 2020)
embedding
96.4
UniGNN (Huang & Yang. 2021)
embedding
96.7
HGNN
embedding
97.2
GHCN((urs)
embedding
97.3
SHSC(ours)
embedding
97.7
Due to space limitations, we defer additional experimental results on Over-smoothing Analysis, Hyper-parameter Sensitivity Analysis, and Ablation Analysis Appendix 1.6, 1.7, 1.9, respectively. The insights are: 1) SHSC can efficiently alleviate over weo-shmothing: 2) The hyper-parameters or, B, are sensitive at a relatively large range but insensitive in small range of the performance optimum; 3) The re-nommalization trick and edge-dependent vertex weights are both effective. In addition, we provide the computational complexity analysis for our models Appendix 1.11.
4.1 CITATION NETWORK CLASSIFICATION
This is semi- supervsse 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: / / thtb.. com/ma 11 labi ssc HyperGCN) and train-test.
7

---

Under review as a conference paper at ICLR 2022
splits of Yadati 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, include Multi-layer perceptrom(MLPP) 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 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 new SOTA performance across all five datasets. No- tably, both GHCN and SHSC have average performance improvement of 4.88% and 5.83% over the previous spectral- methods, respectively. On the other hand, SHSC achieves the best result 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 O, 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.
Table Test accuracy visual object classification. Each model 10 random seeds and report the mean 1 standard deviation. BOTH means GVCNN+MVCNN, which represents combining the features or structures to gen- crate multi modal data.
Datasets
Peature
Structure
HGNN
UniGNN
HGAT
GHCN(ours)
(HSC(ours)
MVCNN MVCNN
80.11+0.338
75.25-00.17
80.40-0.47
81.37-0.63
0..5
NTU
GVCNN GVCNN
84.26.10.00 84,63 0.21
84.4510.12
85.1510.34
83.35.10.30
BOTH
BOTH
83.5440.50
84.45-0.44
84.05-0.36
84.45+0.40
85,12-+0.5
MVCNN MVCNN
91.2810.11 90.36-0.10
91.2910.15
91.9910.16
92.0110.088
Model-
GVCNN GVCNN
92.53-40006
92.88 0.10
92.44-0.111
92.66-00.10
92.69-10.06
Net40
BOTH
BOTH
97.15+0.14
96.69-0.07
96.44-0.15
97.28=0.15
97.78-10.03
4.2 VISUAL OBJECT CLASSIFICATION
This experiment is about semi-supervised learning. We employ two public benchmarks: Prince- ton 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 pre- process 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 hwt.noab//baaaeee HCNN). More details can be found in Appendix 1.4.
Results. Table 2 depicts that 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 modilimy compared with others. These results reveal that our SHSC has the advantage of combining such modai information through concatenating the weighted incidence matrices (Q) of hypergraphs, which means merging the multi-level hyperedges.
4.3 PROTEIN QUALITY ASSESSMENT (QA) AND FOLD CLASSIFICATION
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 (Bal- dassarre et al., 2020; Hermosilla et al., 2021) in the deep learning area. So we'd d like investigate whether hypergraphs are better than simple graphs for protein modeling, and the following results confirm this conjecture.
Protein hypergraphs. A protein 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 T consecutive amino acids (u, ". ((++) to form sequence hyperedge, and choose amino acids whose spatial Fuclidean distance is less than
8

---

Under review as a conference paper at ICLR 2022
the threshold 0 to form spatial hyperedge, where u2(2 1, , represents the i-th amino acids in the sequence. Appendix 1.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 Global Distance Test Score (Zemla, 2003), which is the global- level score, and the Local Distance Differ- ence Test (Mariani et al., 2013). an amino- acids-level score. The loss function of QA is defined as the Mean Squared Error (MSE): b. MSE(P, pred GDT_TS), Li E MSE(P) pred, LDDT,) where pa prea and 'Pi ppred denote predicted global and lo- cal score, respectively, We jointly learn node and graph embeddings and the losses are weighted as Liotal
Table 4: Comparison of our method to others on pro- tein Quality Assessment task (CASP12). At the residue level, we report Pearson correlation across all residues of all decoys of all targets (R) and Pearson correlation across all residues of per decoys and then average all de- coys (Raecay) with LDDT scores. At the global level, we report Pearson correlation across all decoys of all tar- gets (R) and Pearson correlation per target and then aver- age over all targets (Rearget) with GDT.TS scores.
GDT
LDDT R Racony
Methods
R
Rearget
Olechnovive & Venclovas (2017)
0.557
Zhang & Zhang (2010)
0,313
Derevyanko et al. (2018)
0.607
p.d,- + (1 1)) Lg)
Conover et al. (2019)
0.651
0.439
where a is a pyper-paramettr. We use the data from past years' editions of CASP, in-
HGNN GHCN (ours)
0.667
0.582
0.632
0.319
0.737
0.609
0.656
0.340
SHSC (ours)
0.760
0.554
0.678
0.449
cluding CASPIO-13. 1,, are used for training and validation, and CASP12 is used for testing. Results. Table 4 shows that our methods outperform most of SOTAs, which demon-
strates our methods can learn protein more efficiently. The outstanding performance of SHSC indi- cates 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 func- tion, 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 per- formance 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 wwoossno problem, which has large impact on the nove-level task, so our SHSC is more suitable for node-level tasks, while for the pure graph-level tasks, SHSC too simple to offer good performance.
Table 5: Comparison of our methods to others on fold classifica- tion. We report the mean accuracy (%) of all proteins.
Methods
Architecture ID ResNet
#params
Fold Super.
Fam.
Hou al. (2018)
41.7M
17.0
31.0
77.0
Rao et al. (2019)'
ID Transformer
38.4M
21.0
34.0
88.0
Bepler & Berger (2018)*
LSTM
31.7M
17.0
20.0
79.0
Strodthoff et al. (2020)*
LSTM
22.7M
14.9
21.5
83.6
Kipf & Welling (2017)
GCNN
1.0M
16.8
21.3
82,8
Dichl (2019)
GCNN
1.0
12.9
16.3
72.5
Gligorijevic al. (2020)*
LSTM&GCNN
6.2M
15.3
20.6
73.2
Baldassurre et al. (2020)
GCNN
1.3M
23.7
32.5
84.4
TIGNN
HIGCNN
2.1M
24.2
34,4
90.0
SHSC (ours)
HGCNN
0.75M
21.4
23.0
78.4
GHCN (nurs)
HGCNN
2.1 M
25.0
36.3
91.6
Pre-trained unsupervised on 10-31 million protein sequences.
5 DISCUSSIONS AND FUTURE WORK.
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 condi- tion 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 be- tween 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 hy- pergraphs 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 future work.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT AND BROADER IMPACT
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 undigraphs without some specific conditions. Mean- while, we lead to the Laplacian of our framework and analyze the spectral properties of it, especially focusing on the condition equivalent to undigraph. Furthermore, develop Generalized Hy- pergrpah Convolutional Network and a Simple Hypergraph Spectral Convolution for hypergraph learning, based the condition equivalent to undigraph.
Our research of the equivalency conditions between hypergraph and graph opens many more pos- sibilities in designing more comprehensive graph-based methods 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 high degree of trust in our model and obtain an incorrect inter- pretation of the results, etc. In addition, we should be vigilant about the potential unemployment issue due to reduced amount of the need of labeling by human beings.
REPRODUCIBILITY STATEMENT
All the datasets are publicly available described in the main text. Our efforts to ensure repro- ducibility include the following aspects: 1) A sampled code is provided the supplementary mate- rial. 2) The proofs and derivations provided in Appendix G, F. 3) More details of experimental configurations are provided in Appendix I.
REFERENCES
Proceedings of the 23rd international conference on Machine learning, pp. 17-24, 2006. Sameer Agarwal, Kristin Branson, and Serge Belongie. Higher order learning with graphs. In
Sinan G Aksoy, Cliff Joslyn, Carlos Ortiz Marrero, Brenda Praggastis, and Emilie Purvine. Hyper- network science via high-order hypergraph walks. EPJ Data Science, 9(1):16, 2020.
F Baldassarre, DM Hurtado, A Elofsson, and H Azizpour. Graphqa: Protein model quality assess- ment using graph convolutional networks. Bioinformatics (Oxford, England), 2020.
Tristan Bepler and Bonnie Berger. Learning protein sequence embeddings using information from structure. In International Conference Learning Representations, 2018.
Timoteo Carletti, Federico Battiston, Giulia Cencetti, and Duccio Fanelli. Random walks on hyper- graphs. Physical Review E, 101 2020.
Timoteo Carletti, Duccio Fanelli, and Renaud ambiottte Random walks and community detection in hypergraphs. Journal of Physics: Complexity, 2021.
T-H Hubert Chan and Zhibin Liang. Generalizing the hypergraph laplacian via diffusion process with mediators. Theoretical Computer Science, 806:416-428, 2020.
T-H Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, and Chenzi Zhang. Diffusion operator and spectral analysis for directed hypergraph laplacian. Theoretical Computer Science, 784:46-64, 2019.
Ding- Yun Chen, Xiao-Pei Tian, Yu-Te Shen, and Ming Ouhyoung. On visual similarity based 3d model retrieval. In Computer graphics forum, volume 22, pp. 223-232. Wiley Online Library, 2003.
10

---

Under review as a conference paper at ICLR 2022
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference on Machine Learning, pp. 1725-1735 PMLR, 2020.
Uthsav Chitra and Benjamin Raphael. Random walks on hypergraphs with edge-dependent vertex weights. In International Conference on Machine Learning, pp. 1172-1181. PMLR, 2019.
Fan Chung. The laplacian of a hypergraph. Expanding graphs (DIMACS series), pp- 21-36, 1993.
Fan Chung. Laplacians and the cheeger inequality for directed graphs. Annals of Combinatorics, (1):1-19, 2005.
Fan RK Chung and Fan Chung Graham, Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Matthew Conover, Max Staples, Dong Si, Miao Sun, and Renzhi Cao. Angularqa: protein model quality assessment with Istm networks. Computational and Mathematical Biophysics, 7(1):1-9, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. arXiv preprint
00367, 2016.
Georgy Derevyanko, Sergei Grudinin, Yoshua Bengio, and Guillaume Lamoureux. Deep convolu- tional networks for quality assessment of protein folds. Bioinformatics, 34(23):4046-0555 2018.
Frederik Dichl. Edge contraction pooling for graph neural networks. CoRR, 2019.
Kaize Ding, Jianling Wang, Jundong Li, Dingcheng Li, and Huan Liu. Be more with less: Hyper- graph attention networks for inductive text classification. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 4927-4936, 2020.
Lei Ding and Alper Yilmaz. Interactive image segmentation using probabilisticc hypergraphs. Pattern Recognition, 43( 183-)1833 2010.
Yihe Dong, Will Sawin, and Yoshua Bengio. Hnhn: Hypergraph networks with hyperedge neurons.
arXiv preprint arXiv:2006.12277 2020.
Aurélien Ducournau and Alain Bretto. Random walks in directed hypergraphs and application to semi-supervised image segmentation. Computer Vision and Image Understanding, 120:91-102, 2014.
Yifan Feng, Zizhao Zhang. Xibin Zhao, Rongrong Ji, and Yue Gao. Gvenn: Group-view convo- lutional neural networks for 3d shape recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 264-272, 2018
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3558-3565, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp- 1263-1272. PMIR, 2017.
Vladimir Gligorijevic, P Douglas Renfrew, Tomasz Kosciolek, Julia Koehler Leman, Daniel Beren- berg, Tommi Vatanen, Chris Chandler, Bryn Taylor, lan M Fisk. Hera Vlamakis, et al. Structure- based function prediction using graph convolutional networks. bioRxiv, pp. 786236, 2020.
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 3292)1129-150, 2011.
Koby Hayashi, Sinan G Aksoy, Cheong Hee Park, and Haesun Park. Hypergraph random walks, laplacians, and clustering. In Proceedings of the 29th ACM International Conference on Informa- fion & Knowledge Management, pp. 495-504, 2020.

---

Under review as a conference paper at ICLR 2022
Pedro Hermosilla, Marco Schäfer, Matej Lang, Gloria Fackelmann, Pere Pau Vázquez, Barbora Kozliková, Michael Krone, Tobias Ritschel, and Max Ropinski, Timo. Intrinsic extrriccexttinsic con- volution and pooling for learning 3d protein structures. In Proceedings of the International Conference on Learning Representations, 2021.
Roger A Horn. Topics in matrix analysis. 1986.
Jie Hou, Badri Adhikari, and Jianlin Cheng. Deepsf: deep convolutional neural network for mapping protein sequences to folds. Bioinformatics, 34(8):1295-133)) 1303, 2018.
Jing Huang and Jie Yang. Unignn: unified framework for graph and hypergraph neural networks. In Proceedings the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, 2021.
Yuchi Huang, Qingshan Liu, Shaoting Zhang, and Dimitris Metaxas. Image retrieval via proba- bilistic hypergraph ranking. In 2010 IEEE computer society conference computer vision and pattern recognition, pp. 3376-3388 IEEE, 2010.
Jianwen Jiang, Yuxuan Wei, Yifan Feng. Jingxuan Cao, and Yue Gao. Dynamic hypergraph neural networks. In IJCAI, pp. 2635-2641 2019.
Taisong Jin, Liujuan Cao, Baochang Zhang, Xiaoshuai Sun, Cheng Deng, and Rongrong Ji. Hyper- graph induced convolutional manifold networks. IJCAI, pp. 2670-2676, 2019.
Wolfgang Kabsch and Christian Sander. Dictionary of protein secondary structure: pattern recog-
nition of hydrogen-bonded and geometrical features. Biopolymers: Original Research Biomolecules, 22(1)))5577-263) 1983.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the International Conference on Learning Representations, 2017.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. arXiv preprint arXiv:1911.05485. 2019.
Chensheng Li, Xiaowei Qin, Xiaodong Xu, Dujia Yang, and Guo Wei. Scalable graph convolutional networks with fast localized spectral filter for directed graphs. IEEE Access, 8:100334-005644 2020.
Jianbo Li, Jingrui He, and Yada 7hu. E-tail product return prediction via hypergraph-based local graph cut. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 519-527, 2018a.
Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. arXiv preprint arXiv:1709.01244 2017.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018b.
Linyuan and Xing Peng. High-ordered random walks and generalized laplacians on hypergraphs. In International Workshop on Algorithms and Models for the Web-Graph, pp. 14-25. Springer, 2011.
Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. Spectral- based graph convolutional network for directed graphs. arXiv preprint arXiv: 9999000999) 2019.
Jiageng Mao, Xiaogang Wang, and Hongsheng Li. Interpolated convolutional networks for 3d point cloud understanding. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 1578-1587, 2019.
Valerio Mariani, Marco Biasini, Alessandro Barbato, and Torsten Schwede. Iddt: local superposition-free score for comparing protein structures and models using distance difference tests. Bioinformatics, 29(21):772-22788, 2013..
2013.
12

---

Under review as a conference paper at ICLR 2022
Osamu Maruyama, Takayoshi Shoudai, Emiko Furuichi, Satoru Kuhara, and Satoru Miyano. Learn- ing conformation rules. In International Conference on Discovery Science, pp. 243-257, Springer, 2001.
Naoki Masuda, Mason A Porter, and Renaud Lambiotte. Random walks and diffusion on networks. Physics reports, 716:1-58, 2017.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: motif-based graph convolu- tional network for directed graphs. 2018 IEEE Data Science Workshop (DSW), pp. 225-228. IEEE, 2018.
Alexey G Murzin, Steven E Brenner, Tim Hubbard, and Cyrus Chothia. Scop: structural classifi- cation of proteins database for the investigation of sequences and structures. Journal of molecular biology, (47(4):536-540) 1995.
Kliment Olechnovive and vCeslovas Venclovas. Voromqa: Assessment of protein structure quality using interatomic contact areas. Proteins: Structure, Function, and Bioinformatics, 85(6): 131- 1145, 2017.
Pascal Pons and Matthicu Latapy. Computing communities large networks using random walks. In International symposium computer and information sciences, pp. 284-293. Springer, 2005.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 652-660, 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. In NIPS, 2017b.
Roshan Rao, Nicholas Bhattacharya, Neil Thomas, Yan Duan, Xi Chen, John Canny, Pieter Abbeel, and Yun S Song. Evaluating protein transfer learning with tape. Advances in Neural Information Processing Systems, 32:9689, 2019.
Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Elassi-Rad. Collective classification in network data. Al magazine, 29(3):93-99 93, 2008.
Nils Strodthoff, Patrick Wagner, Markus Wenzel, and Wojeiech Samek. Udsmprot: universal deep sequence models for protein classification. Bioinformatics, 36(8):2401-2499, 2020.
Hang Su, Subhransu Maji, Evangelos Kalogerakis, and Erik Learned-Miller. Multi-view convo- lutional neural networks for 3d shape recognition. In Proceedings of the IEEE international conference on computer vision, pp. 943,953,100 2015.
Zekun Tong, Yuxuan Liang, Changsheng Sun, David S Rosenblum, and Andrew Lim. Directed graph convolutional network. arXiv preprint arXiv:2004. 13970, 2020.
Mikaela Angelina Uy, Quang-Hies Pham, Binh-Son Hua, Thanh Nguyen, and Sii-Kit Yeung. Revis- iting point cloud classification: A benchmark dataset and classification model real-world data. In 20/9 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 1588-1597. IEEE Computer Society, 2019.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael Bronstein, and Justin M Solomon. Dynamic graph cnn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5): 1-12, 2019.
Chris Wendler, Markus Püschel, and Dan Alistarh. Powerset convolutional neural networks. Ad- vances in Neural Information Processing Systems 32, 2:929-940, 2020.
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912-1920, 2015.
13

---

Under review as a conference paper at ICLR 2022
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-22) 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https: / //openzeview. Stte://ooumm..GxyGGooAAS.
Mutian Xu, Runyu Ding, Hengshuang Zhao, and Xiaojuan Qi. Paconv: Position adaptive convolu- tion with dynamic kernel assembling point clouds. arXiv preprint arXiv:2103. 14635, 2021.
Naganand Yadati. Neural message passing for multi-relattonal ordered and recursive hypergraphs. Advances in Neural Information Processing Systems, 33, 2020.
Nagamand Yadati, Madhav Nimishakavi, Prateck Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. In Advances in Neural Information Processing Systems, pp. 1511-1522, 2019.
Adam Zemla. Iga: method for finding 3d similarities in protein structures. Nucleic Acids Research, 31(13)33370, 2003.
Kaiman Zeng. Nansong Wu, Arman Sargolzaei, and Kang Yen. Learn to rank images: A unified probabilisttic hypergraph model for visual search. Mathematical Problems in Engineering, 2016, 2016.
Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, and TH Hubert Chan. Re-revisiting learning on hypergraphs: confidence interval and subgradient method. In International Conference on Machine Learning. pp. 6026-40344 PMLR, 2017.
Jian Zhang and Yang Zhang. A novel side-chain orientation dependent potential derived from random-walk reference state for protein fold selection and structure prediction. PloS one, 5(10): e15386, 2010.
Jiying Zhang, Yuzhao Chen, Xi Xiao, Runiu Lu, and Shu-Tao Xia. Learnable hypergraph laplacian for hypergraph learning. arXiv preprint arXiv:2106.0570,, 2021.
Ruochi Zhang, Yuesong Zou, and Jian Ma. Hyper-sagmn: self-attention based graph neural network for hypergraphs. arXiv preprint 1rXiv:1911.026:: 2019.
Yubo Zhang, Nan Wang, Yufeng Chen, Changqing Zou, Hai Wan, Xinbin Zhao and Yue Gao. Hypergraph label propagation network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1885-6892, 2020.
Zizhao Zhang, Haojie Lin, Yue Gao, and KLISS BNRist. Dynamic hypergraph structure learning. In IJCAI, pp. 3162-3169, 2018.
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19:1601- 1608, 2006.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2021.
14

---

Under review as a conference paper at ICLR 2022
Appendix
CONTENTS
Related Work
16
A.1 Simplified Related Work
16
A.2 Detailed Related Work
17
Relations with Previous Random Walks on Hypergraph
18
B.1 A Classical Random walk Hypergraph
18
B.2 Intuition and Analysis The Unified Random Walk on Hypergraph
18
B.3 Special Cases of The Unified Random Walk Framework and Laplacian
19
C Unified Non-lazy Random Walks on Hypergraph
19
Typical Hypergraph Convolution (HGNN) and Its Spectral Analysis
21
D.I
Typical Spectral Hypergraph Convolution
22
D.2 Spectral Analysis HGNN
22
The Relationship between Generalized Hypergraphs and Digraphs
23
F
Derivation and Analysis of GHCN and SHSC
23
F.1
Derivation of GHCN
23
F.2 Derivation of The Discounted Markov Diffusion Kernel
24
F3 Derivation of SHSC
24
F.4
Over-smoothing Analysis of GHCN and SHSC
25
Details of Theories and Proofs
26
G.I Proof of Theorem 3
26
G.2 Proof of Lemma
27
G.3 Proof of Theorem
28
................................
G.4 Nonequivalent Condition.
30
G.5 Failure Condition of Function p.
30
G.6 Proof of Corollary
32
G.7 Spectral Range of Laplacian Matrix
33
G.8 Proof of Corollary 2
34
Generalized Hypergraph Partition
35
Details of Experiments
35
L.1 Hyper-parameter Strategy
36
15

---

Under review as a conference paper at ICLR 2022
I.2
Baselines of Spectral Convolutions
37
1.3
Citation Network Classification
37
1.4
Visual Object Classification
1.5
Protein Quality Assessment and Fold Classification
39
16
Over-Smoothing Analysis.
1.7
Sensitivity Analysis
42
1.8
The Spectrum Analysis of SHSC
42
1.9
Ablation Analysis
L10
Examples of
43
L11
Running Time and Computational Complexity
L12
The edge-dependent vertex weights visualization
44
L13
Additional Experiments of Baselines.
45
A RELATED WORK
A.1 SIMPLIFIED RELATED WORK
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) 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-bass methods. Dong et (2020) propose message-passingg 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-inde iige-independent vertex weights, the best of our knowledge, we are the first to attempt 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 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 improved by Chitra & Raphael (2019) and Carletti al. (2020; 2021). On the other hand, Lu & Peng (2011) and Aksoy et al. (2020) define s-th Laplacian through random s-walks on hypergraphs. More recently, non-linear Laplacian, as an important tool represent hypergraphs, has been extended to several settings, including directed hypergraphs (Zhang et al., 2017; Chan al., 2019), submodular hypergraphs (Li & Milenkovic, 2017), etc.
Equivalency between hypergraphs and undigraphs. A fundamental problem in the spectral the- oretical 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 hy- pergraph learning. So far, equivalence is established from two perspectives: spectrum Lapla- cian (Agarwal et al., 2006; Hayashi et al., 2020) random walk (Chitra & Raphael, 2019).
Hypergraph with edge-dependent vertex weights (EDV Whhyyeygaggapph
DDyyerypesgsaphs have been widely adopted in machine learning applications. including 3D ob- ject 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 our knowledge, existing learning algorithms for processing EDVW. hypergraphs do not involve deep learning methods.
16

---

Under review as a conference paper at ICLR 2022
A.2 DETAILED RELATED WORK
Deep learning for hypergraphs Feng et al. (2019) introduce the first hypergraph architecture hypergraph neural neINor,(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 ineffi- cient (details can see Appendix D.I). Yadati et al. (2019) use the non-linear Laplacian opera- tors Chan & Liang (2020) to convert hypergraphs to simple graphs by reducing hyperedge subgraph with edge weights related only to its degree, which causes the information loss of hyper- graphs and limited the generalization. Jiang et al. (2019) proposed dynamic hypergraph neural networks to update hypergraph structure during training. Wendler et al. (2020) utilize signal pro- cessing 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 generalised- MPNN on hypergraph which unifies the existing MPNNs Gilmer et al. (2017) on simple graph and also raised MMMPNN-Recursie framework for recursvely-struutume poorly for other high-order relationships. Huang & Yang (2021) generalized the current graph mes- sage passing methods to hypergraphs and obtain a UniGCN with self-loop and a deepen hypergrpah network UnIGCNIL. However, it does not give reasons why self- 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
data processing, but it performs
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 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 hypergraph by taking into account the degree of hyperedges to measure the im- portance 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 Don-linarLaaplacaann, 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 ran- dom walk to develop 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 two- step random walk by involving the degree of hyperedges in the first step and lead linear Laplacian. In this work, design a unified two-step random walk framework to study the linear Laplacians.
Equivalency between hypergraphs and undigraphs. A core problem in the spectral theoreti- cal study of hypergraphs is the equivalency between hypergraphs and graphs. Once equipped with cquivalency, it is possible to represent hypergraphs with lower-order graphs, thus reducing the diffi- culty 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-
17

---

Under review as a conference paper at ICLR 2022
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 & Yil- maz, 2010; Zeng al., 2016; Zhang 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 fold- ing 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 al. (2019); Bepler & Berger (2018); Strodthoff et al. (2020); Conover et al. (2019), etc. Meanwhile, many 3D struc- ture based models are also raised for protein learning, such as Olechnovive Derevyanko et al. (2018); Baldassarre et al. (2020); Diehl (2019); Baldassarre et al. (2020); Gligori- jevic 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 al., 2001), there is still no related work to design the hhDWWhhypeggrahhhaaae protein learning algorithm.
Venclovas (2017);
B RELATIONS WITH PREVIOUS RANDOM WALKS ON HYPERGRAPH
B. A CLASSICAL RANDOM WALK ON HYPERGRAPH
It can be traced back to Zhou et al. (2006) in which they have given view of random-walk to analyze the hypergraph normalized cut. The transition probability Zhou et al. (2006) from current vertex u to next vertex v is denoted as:
H(u, e) H(v,e) d(u) 8(e)
P(u, v) Σ wree) eES
is easy to find P(u, v) means: (i choose arbitrary hyperedge incident with with probability w(e)/d(u) where d(u) = -Eef w(e) (u, e); (ii) Then choose an arbitrary vertex e E e with probability 1/8(e) where d(e) = Evey H(v,e) 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 developing the unified random walk framework in Definition from view of two-step random walk hypergraph. To generalize the notation of hypergraph random walk in the seminal paper Zhou et al. (2006), in this work, we tend explain the process from another perspective. The fact in Zhou al. (2006) that
(uu, (v,
w(e) 8(e)
d(u)) Σ nr(e) (())
=Σ w(e) 3EE VEV
Σ
Σ
(10)
8(e)
DEV eEVeE
and
Σ
w(e)
P(u, u0 = Σ
w(e) ((,)H((,,e) H(v,e)
Σ w(e)
CE ((F((
ō(e)
(11)
d(u) 6(c) d(u)
5(e)
Σ
Σ
m((e)
3EE
cEE(a,e)
o(c)
bEV.E
show that the probability P(u, v) also means a normalized weighted adjacency relationship between and (Here, E(u, v) denotes the hyperedges contained vertices u and v.). Furthermore, the relationship is actually measured by the sum of w(e) for all E concluding pair {u, v). which demonstrates that a hyperedge with larger degree (8(e)) linked to fu, e} contribute less to the transition probability between and
3ie)
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 p(.) (+)²), we further explain the intuition of our
18

---

Under review as a conference paper at ICLR 2022
purpose to design the P(u, v)) of our unified random walk. When Q1 Q2 H. P(u, in Eq. can be expressed as:
Σ w(e)p(((e))
eE.(u,v)
P(u, v)
Σ Σ w(e)p(((e)
bEVeEB(u.))
That is to say, the influence of hyperedge degree should not be limited to an inverse relationship by introducing the function p(-). Thus, by evolving more fine-grained vertexes weights (u,,e) e) and Q2(u, e) to replace H (v,e) e) and H Hu, e), we obtain the final transition probability of our unified hypergraph random walk in equation 3.
B.3 SPECIAL CASES OF THE UNIFIED RANDOM WALK FRAMEWORK AND LAPLACIAN
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 special case with specific pl, P2. It is easy to construct the relations of our framework previous works as follows:
Remark (Zhou al. (2006)) When we choose p(-) (-)-1 and Q Q2 H in our framework, the probabilities of unified random walk on hypergraph are reformulated as pt wle)H(u.e)
H(v.e) E.ee (a.) and p2 Evev H(z.ey" As the special case of ours satisfying Q1 Q2 H and p(.) =-)-1, Zhou al. (2006)'s random walk satisfies both condition (1) and condi-
tion (2) in Thm. So we obtain from Corollary 1 that Tzhou(U) = "Eee d(u) and Lshou
d(v)
I D 1/2 HIWD-'H
where Du(u, u) d(u) Ense w(e) e) and De(e,e) 8(e) Ever H(v, e). The forms of Tzoou and Lghou exactly the same in Zhou al. (2006).
Remark 2 (Carletti et al. (2020; 2021)) When select p(-) (-)" and Q
Q2
H. the probabilities of unified random walk on hypergraph are reduced to p w(e)H(u.e)( (Eee H(v,e))+42
H(v.e) Eoer (a.))( H(w.e))==x and D2- =Evev H(v,e) As the special case of ours satisfying Qi Q2 H and p(.) (.)%, Carletti al. (2021)'s random walk satisfies both condi- d(v))
Evev
tion (1) and condition (2) in Thm. 1. So we obtain from Corollary that Tear(U) Evey d(u)
and Lear - Do HWD;H D where Du(u, = d(uu) EcEE ((())(())++H(( and (e(e,e) ((e) Evse H(v,e), e). The forms of Tear and Lear 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 the and L are easy obtain from conclusions.
Carletti al. (2021) with
Remark (Chitra & Raphael (2019)) When we set p(.) = and Q1 = H. the probabilities Qaiv.e)
vo(c) of unified random walk on hypergraph become Pt = -cce (we)H(u.e) and P2 Evey Qatvee with an edge-dependent vertex weights Q2 in the second steps. Actually, as the special case of ours satisfying Qı = H and p(-) (-)-1 Chitra & Raphael (2019)'s random walk hypergraph generates the Laplacian Lekt which could build up a simple relation with our Lyw in equation 20 as
+P T
Lehi 2/2 1/2
2
which means that Lew denotes a form of symmetrization on Lehs- Further, as the vertex weights is in Chitra Raphael (2019) which means they satisfies condition( 1) in Thm. 1, the same as Chitra & Raphuel (2019) can be obtained from from Corollary 1, i.e. n(v) E.
d(v)
C UNIFIED NON-LAZY RANDOM WALKS ON HYPERGRAPH
The non- non-lazy version is nontrivial to factor and analyze. To ease the studies, we first give the following definition and lemma.
19

---

Under review as a conference paper at ICLR 2022
Definition 4 (Reversible Markov chain) Let M be Markov chain with state space X and tran- sition probabilities P(u, v). for u, v E X. We say M is reversible if there exists a probability distribution π over X such that
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, S. M is reversible if and only if there exists 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 T(u) o 0 due to the irreducibility of M. Let & be a graph with vertices S. Different from Chitra & Raphael (2019), we set the edge weights of G to be
w(u, v) = P(u,) v), Vu,uES
(13)
where c. > is a constant for normalizing т. With reversibility, 9 well-defined (i.e. w(u, w(, u)). In random walk on G, the transition probability from to v in one time-step is: w(u,)))
P(u, v), since Ewes 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]).
P(u,))
Eccy [[,,o Evey ((a))
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 d(e)
Evey Q2(U, e) is the degree of hyperedge, and dns(v) == Eees ((e)( - (()(())) Q2(v, e)) (w.e) e) is the degree of vertex v. The unified non-lazy random walk on a hypergraph H defined in two-step manner: Given the current vertex u,
Step I: choose a hyperedge e incident to u, with probability
((c)( Q2(u, e))p(((c) e)) (u)(u)
P1
(14)
Step II: choose an arbitrary vertex v + u from with probability
Q2(v,e)
p2
d(e) - e2(,,e)
(15)
Thus, the transition probability of our unified non-lazy random walk from vertex u to v is:
Pni(u, = Eoee (aa (w)
if +
(16)
uf
Thus, the transition matrix of unified non-lazy random walk be expressed as:
P... D QQ p(D.. WQ,
(17)
where Dnt. D. are diagonal matrices with entries DnI(v, v) = dnr(v) and Da(e, e) 5(e), respec- tively. denotes the Hadamard product and denotes |V| x | ones matrix(i.e. all elements equal to 1). p(1D, Q2)) represents the function acting on each element of (1D. Q2).
Following Chitra & Raphael (2019), the modified version of the elique graph without self-loops is defined below:
Definition 6 (Chitra & Raphael (2019)) Let H(V, E, Q) be a hypergraph associated with the uni- fied non-lazy random walk in Definition 5. The clique graph of H without self-loops, GC is weighted, undirected graph with vertex set V. and edges E' defined by
E' (v, w) E V x V v, e ffrrr some E E, and + w)
(18)
20

---

Under review as a conference paper at ICLR 2022
Different from the lazy random walk, unified non-lazy random walk hypergraph with dition (1) or condition (2) in Thm. not guaranteed to satisfy reversibility (see Definition 4).
However, if Q1 Q2 H. then reversibility holds, and obtain the result below.
Theorem Let H(VEE, Q) be a hypergraph associated with the unified non-lazy random walk in Desinition 5. Let Q = Q2 H. i.e. Qi(U,e) 1, E {1,2] for all vertices y incident hyperedges Then, there exist weights w(u, v) on the clique graph without self-loops I such that non-lazy random walk on H is equivalent to a random walk on G
Proof. We first prove that the unified non-lazy random walk H is reversible. It is easy to verify the stationary distribution of the unified non-lazy random walk on H with Q: = Q2 = H
dar(v) is T(V) Evev dniloy' Let P(u, v) be the probability of going from to in unified non-lazy random walk on H. where a + v. Then,
dne(u) Evev (u)(u)
w(e)p(((e) Q2(u, (ele)))))
(u))(uu,))
(n)(
CEE
Evev dni(u)
3Eg
1
Eney uu)(u)
cEE'
Evev dni(u)
3E0
So the unified non-lazy random walk is reversible. Thus, by Lemma 2, there exists graph G with vertex set V and edge weights
w(u, v) dni(u) ( v(,,v)
such that random walk G and the unified non-lazy random walk on H is equivalent. The equivalence of the random walks implies that P(u, v) >> if and only if w(u, v) > 0, so it follows that G is the clique graph of 7. without self-loops.
Hypagraph
CliqueGrahh
0
2: (1)
0
0
gie)
12
4
q(d)
Figure 4: An example of the disconnected hypergpraph and its equivalent weighted undirected graph. is an isolated vertex. The characteristies of hypergraph are encoded in the weight incidence matrix Q. The elements W QD,10
denotes the edge-weight matrix of the clique graph.
D TYPICAL HYPERGRAPH CONVOLUTION (HGNN) AND ITS SPECTRAL ANALYSIS
Recall Remark 1, the random walk and Laplaican proposed by Zhou et al. (2006) are special cases (p(-) = (1)-1, Q1 Q2 = H) of our unified random walk and unified Laplacian, respec- tively. Thus, now the degree of a vertex E V is d(v) = E.ee ((,e and for hyperedge E E, its degree is 5(e) = Evey H(v,)) e). The edge-degree matrix and vertex-degres matrix can be denoted diagonal matrices D. TR. Eix]e] and D, [ respectively.
21

---

Under review as a conference paper at ICLR 2022
D.1 TYPICAL SPECTRAL HYPERGRAPH CONVOLUTION
From the seminal paper Zhou et al. (2006), classical symmetrie normalized hypergraph Laplacian is defined from the perspective of spectral hypergraph partition: L
HH H D 1/2 Based on it, Feng et al. (2019) follow Kipf & Welling (2017) to deduce the Hypergraph Neural Network HGNN. Specifically, they first perform an eigenvalue decompo- sition of L: L UAUT, where A is a diagonal matrix of eigenvalues and U is consisted of the corresponding regularized eigenvectors. Combining the hypergraph Laplacian with Fourier Trans- form of graph signal processing, they derive the primary form of hypergraph spectral convolution: Ug(A)U where gAA) diag(g g()), .... g(Ax)) is a function of the cigenvalues of L. To avoid expensive computation of eigen decomposition (Def- ferrard al., 2016), they use the truncated Chebyshev polynomials (x(x:) to approximated g(A), which is recursively deduced by (z) = 2rTx-1 (z) - 2xx) with (x = 1 and Ti = x. g* kk= (A)ar, with scaled Laplacian À A 1 limiting the eigenvalues in [-1,1] Amez
9* U((U* 9) @ (U*x))
to guarantee requirement of the Chebyshev polynomial (Hammond et al., 2011). Since the parame- ters in the neural network could adapt to the scaled constant (Amax R3 2), the convolution operation
is further simplified to beg * z R3 for O HWDD-''D
However, in order to obtain the final convolutional layer similar to Kipf & Welling (2017) pro- posed, Feng et al. (2019) used a specific matrix to the scalar parameter Oo, causing flaw in the derivation, In the end, they have managed to obtain seemingly correct hypergraph spectral convolution (HGNN):
Y = D D H
(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.
D.2 SPECTRAL ANALYSIS OF HGNN
We give the definition of Rayleigh quotient to study the spectrum of Laplacian.
Lemma 3 ( Rayleigh Quotient (Horn, 1986)) Assume that M E Rux= is real symmetric matrix and x E IR' is an arbitrary nonzero vector. Let X1 S X2 S--.. ... S An denote the eigenvalues of M in order. Then the Rayleigh quotient satisfies the property:
x Mx
A1 S R(M.))
The equality holds that R(M, u:) = x and R(M, un) = An where u, is the eigenvector related to i E (1,
The Lemma 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 Xmin of L = I D HWDD T b is 0 and figure out the corresponding eigenvector umin is D
Specifically, let g denote arbitrary column vector which assigns to each vertex u V real value g(v). We demonstrate R(Lgg) as below in order to describe our conclusion distinctly:
Lg g
9 Lg g (I D. HWDD 'H TTT 2)
Amin
g g
(D D HWD, H D. ()D
(D& (D
(D, HWD H )
DDJ
E. E. E.
w(el (h(u.)) (f(pa//eee((f--aaaaa (f(u)-(())) 6(e)
2 2>, f())d(())
22

---

Under review as a conference paper at ICLR 2022
where g 2 and R It easy the fact: R(L,9) 0, and R(L, 0 if and only if f = (i.e. g= = D
20//1) 1). Then with lemma we get Amin = min R g) = R(L, D 1) =
and Umin D
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.
E THE RELATIONSHIP BETWEEN GENERALIZED HYPERGRAPHS AND DIGRAPHS
In this part, we would like to illustrate that our unified random walk on a hypergraph is always equivalent to random walk on the weighted directed clique graph, As long the equivalent condi- tions 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 hypergraphs.
Chitra & Raphael (2019), whose random walk is a special case of our framework with p(:) (1-1QQ Q H. claims that the hypergraph with edge-dependent weights (i.e. Q2 edge- dependent) is equivalent to a directed graph. Here we extend this conclusion to a more general version by the above definition.
Theorem (Equivalency between hypergraph and weighted digraph) Let H(V, E, W, Q1, Q2) denote the generalized hypergraph in Definition There exists a weighted directed clique graph G such that the random walk on H is equivalent to a random walk on g
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.
Adopting results of Thm. 3, we design the Laplacian for our unified random walk framework and explore its spectral properties. Thm. 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 (Random Walk-based Hypergraph Laplacian) Let H(VE E, Q1. .2) be the gener- alized hypergraph Let P be the transition matrix of random walk framework H with station- ary distribution a (suppose that exists). Let be a [V] x (V] diagonal matrix with (vv,v) v) = (v)). The unified random walk-based hypergraph Laplacian matrix Lew is defined as:
L 1/22pp 1/2 & p-1/2p" 2//2
(20)
Following Chung (2005), it is easy to study many properties based on Rayleigh quotient of Lyw- such as positive semi-definite Cheeger inequality, etc. The Laplacian Lyw has great expressive power thanks the comprehensive random walk, which unifies most of existing random walk- based 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, focus the case when hypergraph is cquivalent to undigraph (Thm. 1) and deduce the explicit expression of Lrw (Corollary l).
Based on equivalency Theorem and Lapalacian, can design directed graph neural networks for generalized hypergraph learning, which we will do as future work.
F DERIVATION AND ANALYSIS OF GHCN AND SHSC
F.1 DERIVATION OF GHCN
We define K as Q₂ PDD.P ( Then the unified hypergraph Laplacian matrix L in Thm. can be denoted as
L = I
D 1/2 1/2KD2 1/2
(21)
23

---

Under review as a conference paper at ICLR 2022
Similar to GCN (Kipf & Welling, 2017) and Appendix D.I, perform eigenvalue decomposition of L, then obtain the convolution kernel by using Fourier transform, and approximate with the truncated Chebyshev polynomial to get the convolution form:
g x Pbx 6,D,"//K,, 1/xx.
(22)
Then adopt the same method proposed by Kipf & Welling (2017) to set the parameter 0 = 0g - 0 and obtain the following expression:
gxx= 0 (I (1+D
x.
(23)
According to Theorem 5, it is easy to know the cigenvalues of I + D, KD 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 1D
"DD 1 T,
(24)
where K K + can be regarded as the weighted adjacency matrix of the equivalent weighted graph with self-loops, and D(r u) = Σ. K(v, u) [V] x |V] diagonal matrix. This self-loops makes the methods more robust to process disconnected hypergraphs datasets. Finally, we drive the generalized hypergraph convolutional netWo)k(GHCNN:
x = 1p T ())
(25)
+ is a learnable parameter and (-) denotes an activation function.
F.2 DERIVATION OF THE DISCOUNTED MARKOV DIFFUSION KERNEL
Discounted Markov Diffusion Kernel for hypergraph
Recall that the discounted average visit-
ing rate:
1 t (t) Σ a Pr((((T) k|s(0) = i) PP =Z(t)
Σ
(26)
i.e. 7(1) = Σt= o' P'P
Then, v,( (on(t),
Vin (t)) denotes
v.(1) = (e, (e] Z (f)
Recall the definition of (0) in subsection 3.2: 6x (0) if and only if = k. otherwise U. (0)
0. Then, the discounted Markov diffusion kernel KMD can be derived from the Iz-norm diffusion distance as follows:
(t [V:(() v,(0 ( (1)v.(()) 2,(0)))
= -V.(00) v2(0))
v,()))
(e:- e² KMD (e- -e) e,)
F.3 DERIVATION OF SHSC
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 hyper- graph convolution designed in our work is shown as below general form:
Y= vb
((É
Σ
K
a Tuk
X x+)
(27)
K
where the generalized transition matrix in equation 24, is the parameter matrix to be learned during training, and (-)) denotes an activation function. Since T can be viewed as a k-steps transition matrix, in order to weaken the neighbor vertices in long diffusion steps, introduce
24

---

Under review as a conference paper at ICLR 2022
a discounting factor fr for T 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 hyper-parameter 8 [0, 1] control the self-loop T I. Finally, we proposed Simple Hypergraph Spectral Convolution (SHSC) as:
Y Y= vp (1
a + +1 [1- (1-
Xe
(28)
Am
Actually, SHSC is a spatial-based model while we can analyze it from a spectral-based view. Let = I T denote the normalized Laplacian matrix. Then the SHSC can be viewed as a special spectral-basee -based polynomial filter through E/ E 0x T where f2 at can deduce the coefficients of the special polynomial filter as & = (-1)' Σ k=d
K. Finally,
a showing the
K strong relationships between SHSC and spectral-based model. The explicit form of & can be derived
as:
K
K
K
a K
0 T
-I)
0
(-1)
1-1)
L'
k=
1=
k=
O=
A=
F.4 OVER-SMOOTHEE ANALYSIS OF GHCN AND SHSC
For real-world datasets, we always use non-Euclidean graphs with finite-dimensional features of vertices. It is difficult to 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 /norm error between t-step transition probability p' and stationary distribution i as the measure of over-smoothing in arbitrary starting vertex. Formally, we name the measure by over-smoothing energy as follows:
eii
N (((i)) -T/11
where denotes the sign of starting vertex and 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 0, Vjj f i). It is easy to observe that if the limit of e(i, E) with respect to converges to infinity, it indicates the model based on P undergo severe ever-smoothing issue.
ii.e. f(i); 1 and f(i),
Recall Corollary 2, we get now-bounded quantity of e(i, t) as Clow (i,
N N a(i)
N
e(i,t) >
AH) (i,
(dg) vä(a)
Σj=1
AH)
where (HHH
d(j) can be seen constant associated with H which is independent with or t. Recall Corollary 2 that Ay is smallest nonzero eigenvalue of L.
f=1 V E N
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 K-laayers GHCN model with the form: ((+1) (eeUU(T(") To get a simple mathematical form from above incremental convolution formula (remove the activation layer), we could get approximated K-layers GHCN as:
( = T (0)
Intuitively, from the simple form we find the over-smoothing energy of GHCN in vertex i can be rep- resented by (i, K". It is easy to analyze that as K - co, Clow 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 quantitative perspective. HGNN (Feng al., 2019) also suffers from over-smoothing as shown in Table 14. Meanwhile, the theoretical analysis of weo-thnt on HGNNcan be covered by the analysis of GHCN due HGNN is special case of GHCN.
25

---

Under review as a conference paper at ICLR 2022
-mooshing analysis of SHSC. Similarly, from the form of SHSC, R Li=o a (o 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 compare the over-smoothing energy between muti-layers GHCN and SHSC follows: As K + 00:
Clow K) lim (sHsc(i,K) lim
$ E K cton (1,
000 eGHON(i,
k=000
(1- ) 2ek=0 I-AW )
lim
K+30
K
(1-AH) K+1 a k+1
lim
(suppose Ay a +0)
K-00
K(1 - Aω (x)
(29)
where the last equation depends on (0, 1] and AØ (0. proved Theorem If 1f
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 multi- layers 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 K0000
Σ
a
Clow
(i, k)
k=
K
N VV
= lim
1
Σ
500 K
((1l)
k=0
NV /di(i)
K
1- AH
a
lim
K(1-Am - Ar - aa) K(1 An - a) i A11
(30)
K+20
(H)
0, equation 30 (( Otherwise, equation 30 converges to infinity. Notably, this result shows that the over-smoothing property of SHSC is related to the magnitude of & and An Moreover, this analysis further reveals that the introduced hyperparameter meaningful for SHSC alleviate over-smoothing.
If < - Am and Au a + 0, equation 30 equals to 0; If AH
equals to N Nv
G DETAILS OF THEORIES AND PROOFS
G.1 PROOF OF THEOREM? 3
Theorem (Equivalency between hypergraph and weighted digraph) Let H(V, E, W, Q1, Q2) denote the generalized hypergraph in Defimition There exists a weighted directed clique graph g such that the random walk on H. is equivalent a random walk on go.
Proof. Let w(u, v) be the weight of edge (u, v) in g We set w(u, u) = d(u)) v) in Defini- tion then the weighted clique graph is a directed graph, where P(u, u) is the transition probabili- ties in Eq equation 3. The random walk on the directed weighted GC with transition probabilities
w(u, v)
d(u) v)
pC (u, v) Evey w(,
Evey d(u) P(u,v)
equivalent to H. with transition probabilities P(u, v). The matrix form of edge weight of gC is: Wc Q2 Wp(D)
Suppose W I and let p(.) = (-)-1, we can obtain the equivalent weighted clique graph showing in Figure 5.
26

---

Under review as a conference paper at ICLR 2022
Hypanraph
Directed Clique Capph
(/6)
02
Figure 5: An example hypergraph and its equivalent weighted directed graph, where q (-) = Q+(+,)) e), (1,2). Here, Q is edge-dependent and Q2 is edge-independent. The characteristics of the hypergraph are encoded in the weighted incidence matrices (i.e. vertex weights) Q1. Q2. w = Q.D QQ denotes edge-weight matrix of the clique graph and can viewed as the embedding high-order relationships.
G.2 PROOF OF LEMMA
Lemma Let H(VE,, Q2Q Q1.Q2) Q2) denote the gemeralized hypergraph in Defini- tion 2. Let Fig.,9)(u, = Ense w(e)p(((e))) ((2,)) and Tiqy(u)
EvEF ((())(c))ll(e)))((u.cc) When Q1 Q2 satisfies the following equation
Tiqa)(u) ( (Q), v) T(qn)(t)Tion) FlQ...2)( u), Vu,EE
there exists weighted undirected clique graph g such that a random walk H equivalent random walk on G with edge weights w w(u, v) O and 0 otherwise.
if T(q.)(u) +
And the symmetrical Laplacian of gc is
L(u. v) = (u=o) (ua 22 (0)))
(31)
where [(3) denotes the indicator finctiin..
Proof. Form Lemma 2, we just need prove Markov chain with state space V is reversible. The transition probabilities of the unified random walk on are:
(( Q2Q(v.)) (2()))
(u,
P(u, v) = Σ
d(u)
T(q))(u)
3EE
By equation 4, we have:
(u) ((en)e))u.u)) (v) ((Q)(1))
Fie (T):)())
i.e.
((),,)) (t)
Comparing with equation 12, normalize G(Q2) to define the stationary distribution of M:
T(u) = Σvev (()))(u)
Vu EV,
(32)
which can be easy to verify by Σ, P(u, v) (v). Thus, (()) (v) u), which suggests that M is reversible. By Lemma 2, the edge weight w(u, v) of g
(u)
w(u, v) eτ (u)) v) = Tio P(u, = (u) (.)(.))
To gain the Laplacian of ço, caleulate the sum of row of edge weights matrix.
Σ [((u,o) (u)
(u)) (w)
Tin)(u) NEV
NEV
Then get the symmetrical Laplacian of cC:
T(u, v) I(u=v) Tiq - (e)
(33)
27

---

Under review as a conference paper at ICLR 2022
G.3 PROOF OF THEOREM 1
Theorem (Equivalency between generalized hypergraph and weighted undigraph) Let H(V,& &, W. W Q2) denote the generalized hypergruph in Definition 2. When H satisfies any of the condition bellow:
Condition (1) Q1 and Q2 are both edge-independent: Condition Q1 = kQ (k E ER),
there exists weighted undirected clique graph go such that a random walk on H. equivalent to random walk on G
Proof.
1) Proof based on Lemma
For condition (1),
= (u))g((()) (u,
Σ (weeeddee)HHHuu.)HH...
oEE
AEE
Tiqu(u)= Σ ((e) (u)) Σ
w(())(e)oodtt)))((lee))) i= (1,2)
cEE
(34)
Substituting the above equations into equation 4, then equation 4 holds. For condition (2),
(u, = Σ (ute Σ
.EE
CEE
(u) = Σ (() = w(e))(cllp6le)))s(uu.cc (()
6E8
aEE
(35)
Similarly, substituting the above equations into equation 4, then equation 4 holds.
Proof based Lemma 2 1) For Condition (1):
Because QI and Q2 are both edge-independent, we set Qi, e) 2i (u) and Q2(v, e) = (2(v) for all hyperedge From Lemma the key is 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 Fortunately, by Kolmogorov's criterion, that equal to prove:
Puy Por.ogPugee " "P Ponss " Pe22.1
for arbitrary subset (ui...., ) C V. The transition probabilities of the generalized random walk on H are:
p(u,v) v) (1 Q2(,
(u)ca(()) d(u)
Σ (u.
d(u)
MEE
aEE
Φ1 (u)
Σ ((e)p(((e))
d(u)
eE
28

---

Under review as a conference paper at ICLR 2022
where E(u, v) {e E e, E e) to be the set of hyperedges incident to both v and Then we have:
Por,0 ... P0
( d(u,)
91 (1())12(122)
a(lenob(ee))
w(e)p(((e))
d(ur)
(EF(U1)"2)
DE (EF(NN))))
n (n(er)a((e)) d(vi)
II
II E
w(e))(((e))
where set en41 U1
(v()))ga(v)) d(vr)
(1((2))2((1)
w(e)o(((e))
w(t))(((e))
d(v2)
(1)
eEE(N))0))
Po
Pog
So the unified random walk on H. under condition (1) is reversible.
As matter of fact, we can succinetly obtain the reversibility via the stationary distribution. Specif- ically, we can verify the stationary distribution is
(()) = LeEe ((eeeeee)pp((()))2)u.... ((())(c)p(((e)0a(...))))
(36)
by E. (u) Then with (()) ((, 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 on H is equivalent to random walk undirected graph G with vertex set V. By equation 13, the edge weights of are:
w(u, v) cT(
Σ (ute)potee)@sssce0)0aa 3EE
(37)
where e = Ev Eees ((())(e))(8())))@((.ee) Note that P(u, v) 0 and only w(u, v) 0, so G is the clique graph of H.
II) For condition (2) that Q kQ2.
we have P = ID.," Q2 Wp(.) Thanks to the underlying symmetry adjacency matrix of P (i.e. Q2 (.p(D))a is symmetrical), we have: 1 D.P. = D.T Thus, the stationary distribu-
tion is
d(u) E.ss Wee
<uu)
(38)
Σ, d(v)
Evev Eeee ((e))
Further, we would prove that the unified random walk on H under current condition (2) is reversible.
d(u)
(()))((((e) (((,,)
T(u)p(u, u) En d(ee)
Σ
d(u)
d(v)
wtee)lbte))Qc =(v)p(u, d(v)
Σ
En d(o")
So the unified hypergraph random walk on under condition (2) reversible. Since H 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:
w(u,e) u) = cn P(u, = Σ w(e)p(tte)@Q(u.)001...
(39)
3EE
29

---

Under review as a conference paper at ICLR 2022
where = Ev = - EeEs w(c))(ce)(((c)))((...)) Note that P(u, 0 if and only if w(u v) > 0, so 9 is the clique graph of H.
On the whole, we get the specific equivalent weighted undigraphs under our condition (1) and con- dition (2). Note that they have the same edge weights expression ( (quuatinn 37, 37,equation 39):
WC Q2 Qp
which further suggests the connection between condition (1) and condition (2) stated Corollary and Thm. 1.
Remark:
Let p(-) = ())
and W I, we can get the undigraph shown in Figure 1.
Hypagraph
Directed Clique Craph
Q
WC=
7
(/6))
Vid
12
10 7
3
(
Figure 6: An example hypergraph and its equivalent weighted directed graph, where q (-) = @,(-e), (1,2). Here, Q is edge-independent and Qa is edge-dependent. The characteristics of the hypergraph are encoded in the weighted incidence matrices (i.e. vertex weights) Q Q2. w == Q Q= denotes edge-weight matrix of the clique graph and can viewed as the embedding high-order relationships.
G.4 NONEQUIVALENT CONDITION.
Theorem There least exists one generalized hypergraph H(V, W. Q1 Q2) (Definition 2) with degeedeennddnt weights and Q1 * lQ2,, such that a random walk on H. is not equivalent to random walk on its undirected clique graph g for any choice of edge weights on go.
Remark. Theorem 4 tells that the random walk on hypergraph can not be always equivalent to random walk on an undigraph, and open up the possibility to construct a hypergraph not equivalent to an undigraph, which may inspire researcher to further study for higher-order interactions and other insurmountable bottlenecks on hypergraphs.
When the vertex weights are edge-dependent, the reversibility not always satisfied in our unified random walk on a hypergraph. By Lemma 2, if the unified random walk is not time- reversible, could not equivalent random walks on digraphs for any choice of edge weights.
Proof.
A irreversible example can see Figure 6. The probability transition matrix of the unified random walk on the left hypergraph (with W p(-( (-)-1) given below:
P= D Q QDD.)) D Q
6
12
24
(40)
5
6
12
24
and the stationary distribution of the unified random walk on hypergraph with P is:
7 5
2
(41)
17 17'
17
We verify (1) - x 7
P(2, 1), which indicates that the Markov chain
represented by the unified random walk in Figure with transition probabilities P is irreversible.
G.5 FAILURE CONDITION OF FUNCTION p.
As matter of fact, the p in our random walk framework can not always work and we give its failure condition follows.
30

---

Under review as a conference paper at ICLR 2022
Proposition 1 Let H(V. &, W. Q) associated with the unified random walk in Definition 1. p(-) fails to work in our unified random walk if the hyperedge degrees are edge- ingeeendeeendentt (i.e. 5(e) = 8(e'). Ye' E).
Proof.
Given 8(e) are edge-indep,nndet,, let us suppose ö(e) = ki then
u(u, Σ w(e) e Q2((1))))
wle))i(tuee)QQ( Eeee ((e)ole)a(((c)))((0...
d(u)
3EE
(u, = E (4 Eees
Σ
3EE ((c))(c)p(())x((tee)
EEE p(k) Eck) ((e)
Σ 3EE
Eees w(e)0(e)Q
which indicates P(u, v) is independent to p(-). i,e. p(-) fails to work.
is obvious that the k-uniform hypergraph has adge-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 Qı = Q2 = H, then H is a k-uniform hypergraph(i.e. each hyperedge contains the same number of vertices) if and only P(u, v) in equation 3 independent with
Proof. For Q = =H, then 5(c) = Eve)=Eved
h(v,e)
So, for all u, U E V, have:
(u,) = Σ (eee
Σ [u(e)H(u,)HH(C..) aEE
(42)
CEE
Then get the entries of the transition matrix P
K Klo) (u,
k ""Ec ((e))l((,,))l(( Ever ko Ecee (())H(,
plo) r)
(43)
E. (u)(u,
wo(e (4,
(44)
Evev Eese (())H((,
It is easy to see that p(o) (u, v) is independent with The other direction, find when p(o) (u, v) in is independent with o,then:
(p,))
Od(a)
K ((o)(u, do P(u)
(u.)) d(u)) do
(45)
do
(n(((())(())))((())))))))))))))) (((e)))))
(46)
d(u)
= U,V
(47)
It is equal to 3k E z++ s.t.:
= =())=()))kk for all e E
i.. the hypergraph is k-uniform. With the condition that Q1 = Q2 H. our unified random walk hypergraph reduces to random walk hypergraph that leaving only incident relation- ships between hyperedges and vertices. Actually, the reduced random walk mentioned is common structure in real-world applications. The proposition is say when the hypergraph based on the reduced random walk is uniform, the function p(-) does not impact the importance between vertices any more.
31

---

Under review as a conference paper at ICLR 2022
G.6 PROOF OF COROLLARY 1.
Before proving the Corollary I, we further illustrate the fact that Lemma states.
Lemma Let H(V,& & W, Qı, Q2) be the generalized hypergraph in Definition 2. Given a H satisfying condition (1) in Thm. 1, there exists H' satisfying the condition (2) such that the random walk on H is equivalent to that on H'.
Proof of Lemma 4. When the condition (2) in Thm. holds (i.e. Q1 Q2). the transition probabilities of the unified random walk H.
p (u, = Eeee weel Eeee wieep(lcc)o(c)ss(u.e
(48)
Mcanwhile, if the condition (1) in Thm. holds (i.e. Q1 Q2 are both edge-independent) for all hyperedge e, we represent Qi(u,e) Q2(v,e) as (u)), (2) respectively, and the transition probabilities are
pel v) Ecce mtllplttce)@iuiuolleee (1()92(v) Eece ((w
Eese w(ee)((lcc)0(e)) (2())ga()) Eeer (ce)
(u Leee (le)p(6(e)d())(((...)))
Eeee (()))llee))@asseee00ee (49)
(2(u) Deee ((())(((0))()))(((.))
Eeef ((())l0((e)()))0a(..
It can be observed that pel (u, = P (u, v), Vu, v E V. By definition 3, the Lemma 4 holds.
Next, based on Lemma 4, we prove the following main conclusion.
Corollary Let H(V,E, W, Q1 Q2) be the generalized hypergraph in Definition 2. Let D, be [V] [V] diagonal matrix with entries Dv(v, v) = d(v) == Lege (((())())((())))))))) e). No matter H satisfies condition (1) condition (2) in Thm. it obtains the unified explicit form of stationary distribution x and Laplacian matrix L as:
D and L = I D. 1/2 Q2 D.
(5)
D
Proof of Corollary 1.
1) Proof based on Lemma When the generalized hypergraph satisfies Theorem 1, 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) condition (2) in Theorem 1, there exists a weighted undirected clique graph g equivalent to H. Recall Lemma 4, when H. satisfies any of the two conditions, the probability transition matrix P of H. can be denoted as:
P(u, v) Encr olee
Ence w(e)pl((e)d(())<((....
Then, we obtain the unified form of probability transition matrix P under any of the two conditions:
P D= D=D
(50)
where D, [V] x [V] diagonal matrix with entries (v u) = E.es ((())(e) e)
Remark the P is also the probability transition matrix of the equivalent undigraph in Theorem 1. Due the symmetric adjacency matrix underlying P (i.e. Q2 WP(DD. is symmetrical), it easy to derive the unified stationary distribution क by = Thus, the stationary distribution is:
D DTD.1
d(u)
Exsr ((eeeeeeeppp()))@sseee.
π
T(u)
(51)
Σ. d(v)
32

---

Under review as a conference paper at ICLR 2022
Substitute P and into equation 20, we finally get the unified hypergraph Laplacian L as:
= D 1 W (DD.) (
Remark. The stationary distribution with edge-indepenn ingeiindependent vertex weights in Chitra & Raphael (2019) can be seen as a special case in equation 51 by setting Q1 H. Q2(u, e) ((u) and p(-) (+)-
π (') 7(1) Ence w(c ((e)H(u,e) En 7(0) Enee (v,) En ((v)dcn())
((u)da(()
where dcn (1) EeEe w(e)h(u, e) is the definition of vertex degree in Chitra & Raphael (2019).
G.7 SPECTRAL RANGE OF LAPLACIAN MATRIX
The following Theorem proves the upper bound for eigenvalues of L which meets the requirement of Chebyshev polynomials enable the derivation for proposed GHCN in Appendix F.1 and leads to Corollary.. 2 in the paper.
Theorem Let L I D 1/2 122 WpWl (DD Q. D denote the unified hypergraph Laplacian matrix in Corollary and A1 I A2 S An denote the eigenvalues of L in order.
1) Amin =A1 and D 1(ee eigenvector associated with X1 )
2) For k 3, ... n, we have
A
inf
f_DAs E(((d)d((v)
here, Sg-1 is the subspace spanned by eigenvectors {u u where u, related to Xi and B(e, u, v) (aal
3) Amaz An 2
To analyze the generalized Laplacian proposed in work, the Rayleigh quotient mentioned in the Lemma to give out some conclusions about the eigenvalues and eigenvectors of the Laplacian.
Proof:
1) Deduce the Rayleigh quotient of L2:
g Lg
g (I
D. Q2 W2 D. D, )g
9
g
(D: DJ Q (...D.D
(D
[T QW,
DDD Σ. E.
f(u))²
2 2., f()
where g -D//2/ and f E RM easy to see the fact: R(L, g) 2 and R(L,g) =
and only if f (i.e. g D Then with Lemma we get \ Amin min R(L,
9
R(L, 1) = 0 and = D 2) From Fischer theorem (Horn, 1986), we have:
Lg
Ae inf R(L.9) inf giSc-1 g gTg
giSe-1
E. E. w(e wtte))ddddeeeec.oe S(u))²
inf
2 ((0
fiD? Sk-1
33

---

Under review as a conference paper at ICLR 2022
3) We have the fact:
((t))-fo))) (()
And from Lemma 3, we get:
An
Amar
R Umax)
= inf
((03d())
fID Su-1
E.t. E. E. E.ceeelddee)00000dee.. /
S inf
S1D Sn-1
2E, (())f())) =
< inf
f1D 9a-1 (()()(((
G.8 PROOF OF COROLLARY
Corollary Let H(V,& &, W, Q1. Q2) be the generalized hypergraph in Definition 1. When H satis- fies any of two conditions in Thm. let and π be the hypergraph Laplacian matrix and stationary distribution from Corollary 1. Let λи denote the smallest nonzero eigenvalue of L. Assume an initial distribution with f(i) (f(i) 0, # which means the corresponding walk starts from vertex V; Let ( fp* be the probability distribution after l steps unified random walk where P denotes the transition matrix, then p (j) denotes the probability of finding the walker in vertex Uj after steps. We have:
(d()) d(ii)
(1 AH)*
(6)
Proof: From equation 50:
P P= P= QW = D ( L
Then we have:
1 D = 1
Then the stationary distribution Ix of P can be denoted as:
π DD
(52)
where = d(v) the sum of 1 D Let A1 S d S S A, denote the
eigenvalues of L in order. Then assume that fD, Σ au RRXIM where u, RRV
denotes the 12- norm orthonormal eigenvector related with A, From Thm 5,, we know ú, u.lla
u
D²1 Then 01 can be computed as:
Vo
ū (AD, 2
ūf (FD, $) (D ( 75
0
Vc
Vc
34

---

Under review as a conference paper at ICLR 2022
with the fact that f RRXXV is a probability distribution(i... fl 1). Then,
(k) Tyl= = (fP*), ( -Tyy = (fP* D 1
[PP* - -ajuj D
(FD, } (I- - DE)
anu
a.u, (I L- - an a
au (1- D -iu
a.u. (1- X1) {))
1=1
2=
$ (1 Ah) (
[ (aū)) )
= =11 - An >n)" (FD,
(fD, 13
(1 A & V (d6)
va(1)
H GENERALIZED HYPERGRAPH PARTITION
For arbitrary vertex subset S C V. S denotes the compliment of S. We define the hyperedge boundary as as OS == {e E E lens & e * 0}. We will generalize the hypergraph par- tition problem in Zhou al. (2006) to our unified hypergraph framework. Hypergraph partition is to cut vertex set V into two parts S and S 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(aS) for directed graphs
vol(S) Σ T()), vol(OS)
Σ Σ x(u)
WES
And the objective function of the hypergraph partition can be expressed as:
argmin c(S) == vol as UASCV
(53)
vvol(S)
vol(S*)
As we need the explicit form of stationary distribution to formulate this problem, we set the unified random walk hypergraph that satisfies with the conditions in Thm. 1. Then we have:
vol(S) Enes d(uu)
vVl
(aS) vol(V) cEas weens veense
1
Σ Σ
1
Σ
w(e)p(((e))m((n (anpllee)mmlnsmmmenss). S)m(en
vol(V)
eEBS
where m(ens)= Eugens Q2 (tr, e) is measure on the subset of V which explicitly demonstrates the difference between Zhou et al. (2006) (where m(e n S) = Eueens H(u, e)) and our work. We considerate more fine- fine-grained information vertices when establish measure arbitrary subset of V and involve the degree of hyperedges to impact the corresponding hyperedge weights rather than use the priori hyperedge weights.
I DETAILS OF EXPERIMENTS
Note that our GHCN and SHSC are both based on the Laplacian led by the equivalent condition in Thm 11 which means the vertex weights we use in our experimental datasets should satisfy the condition (1) condition (2) in Thm.
35

---

Under review as a conference paper at ICLR 2022
1.1
STRATEGY
We grid search strategies to adjust the hyper- peeem-eetmeterss of our GHCN and SHSC. The range of hyper-parametor listed Table 6, Table 7, Table 8, and Table
Table 6: Hyper- parameter search range for citation network classification and visual object classification.
Methods
Hypar-parameter
Range
(22-1.00.500055...22
(Visual object classification)
{0.1. 0.2. 0.4, 0.5, 0.8.10]
Learinng
(0.001, 0.005, 0.013 (64,128)
Hidden dimension
GHCN
Weight decay
Layers
(le 4,5. 4, 1e:5)
{2.4}
Dropout
20.0..0..033, 0., 0.5) Adam
Optimizer
Epoch
1000
Early stopping patience GPU
GTX 2080Ti 100
(1.0.95.0.900.85..8888 0.75}
(Visual object classification)
{0.1. 0.2, 0.4, 0.5. 0.8,10)
Learning
(0.001, 0.005, 0.01))
Hidden dimension
(64,128)
SHSC
Weight decay
Layers
(2,46.8.66,22644
[Ie-3, lc-5)
Dropout rate
(0.1.....033 0.4, 0.5)
Oplimizer
Adam
Epochs
1000
Early stopping patience
100
GPU
GTX 2080TS
Table 7: Hyper- parameter search range for GHCN and SHSC model in fold classification.
Methods
Hyper-parameter
Range
best
Amino-acids type input size
(32,64,128)
Secondary-strune struccure input
(32.641288]
Readout layer input size
(256,512,1024)
1024
Layers I.
(2,3,4.5,6)
4
Batch size
(64.128.256)
128
Weight decay
(le-3,le-4, le-5)
le-3
Learning rate
(0.0001,0.001, 0.005, 0.01)
0.0001
GHCCN
Dropout rate
0.1.0.2.0330044400 (-1)
0.2
y
(0.1002.0440::08....0.
Optimizer
Adam
Epochs
Farly stopping patience
30
GPU
GTX 20801i
Amino-acids type input size
[32,64.128]
Bacondary-structum input size
[32,64,128]
Readout layer input size
12665512,1024)
512
Layers
12.16..8.12.116.2)
12
Batch size
(64,128.256)
Weight decay
[le-3,le-4, le-5)
le-5
Learning rate
00.0001,0.011.00 0.005,
0.0001
Dropout rate
(0.1.0.2.0.3304,,, (-1)
0.3
SHSC
-1
(01102.044:::08...))))
0.4
1.,977.95.9005550.055500000666
0.97
8
110.99...9000.85.0.38]
Optimizer
Adam
Epochs
300
Early stopping patience
30
GPU
GTX 2080Ti
Extra parameter settings for Visual Object Classification include k: = 6.
36

---

Under review as a conference paper at ICLR 2022
Table 8: Elyper-parameet search range for GHCN and SHSC model in protein Quality Assess- ment (CASPIO.CASPII.CAAPII for training. CASP12 testing).
Methods
Hyper-parameter
Range
best
Amino-acids type input size
(128,256.512)
512
Decondary-structurg input size
(22.64,128)
Readout layer input size
(25.551..024))
1024
Layers L
(2.3,4.5.6]
4
Batch size
[64.128,256)
64
Weight decay
(1e-3.le-4, 1c-5}
lc-5
Learning rate
(0.0001.0.001. 0.000.00000
0.0001
GHCN
Dropout
(0.1.0.2.0033044...5) (-1)
0.5
-1
(0.10.2.00400558.11.0000
0.1
Optimizer
Adam
Epuchs
200
Early stopping patience
20
GPU
Tesla Tes P40
Amino-acids type inpul size
[128,256,512)
512
Secondary struuccuee input size
[32.64.128]
128
Readout layer input size
225.5512.1224]
256
Layers L
12.46.8.12.11,,8.333)
18
Batch
(64.128,256)
128
Weight decay
[le-3,1e-4, le-5)
le-5
Learning rate
(0.0001.0.0110.0000 0.0000001...00,0000 0.005
0.0005
Dropout rate
(0.10.2...330440..5)) [-1]
0.3
SHSC
7
(0.102..0405088110))
0.2
1.097200..0.005500.00..00.060000
0.65
3
[1.0995.0..00008550088}]
0.95
Optimizer
Adam
Epochs
200
Early stopping patience
20
GPU
Tesla P40
1.2 BASELINES OF SPECTRAL CONVOLUTIONS
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 via running 1000 times with randomly split get the best 100 times, which not very common. Therefore, despite the HyperGCN is the SOTA method on Table 10, it can not achieve 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 0g). 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 use the same grid search strategy our method GHCN.
I.3 CITATION NETWORK CLASSIFICATION
Datasets. The datasets we use for citation network classification include co-authorship and co- citation 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 (2019), where hypergraphs created on these datasets by assigning each document as a node and each hyperedge represents (a) all documents co-au co-authored by an author co-authorship dataset and (b) all documents cited together by document in co-citation dataset. The initial features of each document (vertex) represented by bag-of-wot words features. The details about vertices, hyperedges and features are shown in Table 10.
37

---

can Under review as a conference paper at ICLR 2022
Table 9: Hyper- parameter search range for GHCN model in protein Quality Assessment (CASPIO-12 for train- ing, and CASPI3 for testing).
Methods Hyper- prrpee-prrmetter
Range
best
Amino-acids type input size
(128,256.512)
128
Sccondary-structtn input size
(32,641288)
64
Readout layer input size
(256.512.1024)
1024
Layers L
[2.3.4.5.6]
Batch size
(64.128,256)
1024
Weight decay
1e-3,, le-S)
le-S
Learning rate
(0.0001,0.011, 0,005, 0.01)
0.001
GHCN
Dropout rate
(0.1..2,00.3 0..20..,,00440,,,,...0... [-]
0.7
001.00..044055...000))
0.1
Optimizer
Adam
Epochs
200
Early stopping patience
20
GPU
Tesla
Amino-acids type input size
(128,266.512)
128
Sccondary-strine -enuuar--ttructure input size
(32,64,128)
64
Readout layer input size
(256,512.1024)
1024
Layers
(2.46..811211618..333
Batch
(24,128,)56)
1024
Weight decay
[1e-3,1e-4, le-5)
le-5
Learning rate
(0.0001.0.001, 0,000.0.001000005000001.
0.001
Dropout rale
0.1.0.2..03300,,,00 [1]
0.2
SHSC
(01.02.0040508..1000
0.2
1.997..5..0005500000.000..00.0.0
0.65
[10.99....9000855.088
0.95
Optimizer
Adam
Epochs
200
Early stopping patience
GPÚ
Tesla
Table Real-world hypergraph datasets used in our citation network classification
Dataset
# vertices
# Hyperedges
# Features
# Classes
# isolated vertices
Cora (co-authorship
2708
1072
1433
7
520(11.8%)
DBLP (co-authorship)
43413
22535
1425
6
0 (0.0%)
Pubmed (co-citation)
19717
7963
500
15877 (80.5%
Cora (co-citation)
2708
1579
1433
7
1274 (47.0%)
Citeseer (co-citation)
3312
1079
3703
1854 (55.9%)
Settings and baselines. We adopt the same dataset and train-test splits (10 splits) as provided by in their publically available implementation'. Note that this dataset just has the edge-independent vertex weights H, which also called the incidence matrix. So this experiment can be regarded as 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 struc- ture, current state-of-the-aa message-passing hypergraph framework UniGNN (Huang & Yang, 2021) and two recent spectral-based hypergraph convolutonal networks: Hypergraph neural net- works(HGNN) (Feng al., 2019) and HyperGGN (Yadati et al., 2019). For UniGNN, reuse the results UniGCN reported in (Huang & Yang, 2021), and for HGNN and HyperGCN, we reproduce them following Appendix 1.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 ppper-parametess, use the grid search strategy. It is worth noting that the layer number of our model is in equation 8. More details be found in Table 6.
38

---

Under review as a conference paper at ICLR 2022
Table II: summary the ModelNet40 and NTU datasets
Dataset
ModelNee40
NTU
Objects
12311
2012
MVCNN Feature
4096
4096
GVCNN Feature
2048
2048
Training node
9843
1639
Testing node
2468
373
Classes
40
67
1.4 VISUAL OBJECT CLASSIFICATION
Datasets and Settings. We employ two public benchmarks: Princcton 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 al., 2015) or Group- Group-View View Convolu- tional Neural Network (GVCNN) (Feng et al., 2018). The features generated by different methods be considered multi-modality features. The hypergraph structure 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 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 selected centroid and its nearest neighbors are used to generate one hyperedge including the centroid itself (in our experiment, we set l 10). Then, given the features data, the verihx-weight matrix Q is defined as
Q e) = exp( d(v.ve)) dd2 ) if Ee otherwise,
(54)
0,
where d(v, ve) is the euclidean distance of features between an object v and the centroid object Ue in the hyperedge and d is the average distance between objects. Y is 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 can be concate- nated build the multi-modand monti-moddlity hypergraph matrix Q = [Q11 Q12y]- The features generated by GVCNN or MVCNN can be singly used, or concatenated to multi-modal feature for constructing the hypergraphs.
For baselines, we just compare with HGNN method for multi-modality learning, following the set- tings of Appendix I.2. We also compare our methods using two-modality features to recent SOTA methods on ModelNet40 dataset. And 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. can be found in Table 6.
the datasets provided by its public Code ? We use
More details of
1.5 PROTEIN QUALITY ASSESSMENT AND FOLD CLASSIFICATION
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 simultaneously consider protein sequence and spatial structure information, we build sequence hyperedge and distance hyper- edge. Specifically, given protein with [S] amino acids, we choose 7 consecutive amino acids (V,, U1+1. ... 1(+r) to connect to form a sequence hyperedge and choose amino acids whose spa- tial Euclidean distance less than threshold
connect form spatial hyperedge, where va(i = 1, (81) represent the i-th amino acid in the sequence. Let &, and &, denote sequence hyperedge and spatial hyperedge, respectively. Then, we design an edge-dependent vertex -weiht matrix Q for capturing the more granular high-order relationships of proteins below (actually, our
'https//githhu.cco///. http:///ghhb..oommmmaallalll//ce Apache License http::///tthuh.co////ooooo al/HGNN MIT License
39

---

Under review as a conference paper at ICLR 2022
40-
80-
Diátance Hyperadges
Sequentia yppredges
120
160
Figure 7: An expample of ddge-dependent vertex weight matrix Q of protein.
models GHCN and SHSC allow one to design more comprehensive Q for learning proteins better):
if u E eand e E &
Q(v,e)= exp(
d(n.pe) yd
if v E eande E & otherwise
(55)
where d(v, ve) < é the euclidean distance between an amino acid and the centroid amino acid 2e in the hyperedge and d., the average distance between Ve and the other amino acids {u; le Y 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. (i.e. Q Q2 = Q). Note that this Q matrix
pays more attention to the information of the sequence (Figure 7).
Experimental settings In our experiment, we r and 8.A. The initial node features, following Baldassarre et al. (2020), are composed of amino acid types and 3D spatial features includ- ing 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 GHCN or SHSC.
Here, for the sake of simplicity, we adopt the permutation-invariee operator mean pooling and a single layer MLP as Readout layers to obtain global hypergraph embedding and add the softmax (classification) or sigmoid (regression) activation function before output.
Table 12: Comparison of our method to others on protein Quality Assessment tasks. At the residue level, We report Pearson correlation across all residues of all decoys of all targets (R) and Pearson correlation all residues of per decoys and then average all decoys (Rdecoy) with LDDT scores. At the global level, we report Pearson correlation across all decoys of all targets (R) and Pearson correlation per target and then average over targets (Rurgge) with GDT scores.
GDT-TS
LDDT
Test set
Methods
R
Buarget
R
Rimode!
HGNN
0.714
0.622
0.651
0.337
CASP13
GHCN
0.718
0.620
0.657
0.352
SHSC
0.628
0.565
0.654
0.435
VoroMQA
0.557
RWplus
0.313
3D CNN
0.607
AngularQA
0.651
0.439
CASP12
HGNN 0.667
0.582
0.632
0.319
GHCN (ours)
0.737
0.609
0.656
0.340
SHSC. (ours) 0.760
0.554
0.678
0.449
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 al. (2020), we train models on Global Dis- tance Test Score (Zemla, 2003), which the global-level score, and the Local Distance Difference Test (Mariani al., 2013), mnin--ecids-level score. The loss function of QA is defined as the
40

---

Under review as a conference paper at ICLR 2022
Mean Squared Error (MSE) losses:
SI
g MPE(PE pred GDT.TS)
4 Σ
MSE(P pred,
LDDT;)
(56)
where Pa pred and Pl pred denote predicted score of global and local respectively.
1.5.1 PROTEIN QUALITY ASSESSMENT (QA)
Table 13: summary of CASP datasets
Dataset
Targets
Decoys
Usage
CASP 10
103
26254
Train
CASP 11
85
12563
Train
CASP 12
40
6924
Test
CASP 13
12336
Train
Dataset and settings We use the data from past years' editions of CASP, including CASPIO- 13. We randomly split the CASP1O, CASPII, CASPI3 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 meth- ods: VOroMQA (Olechnovive & Venclovas, 2017), 3DCNN (Derevyanko et al., 2018). The results of these baselines we reused from Baldassarre et al. (2020) reports. Another baseline HGNN (Feng al., 2019) reproduced by us with same training strategy our methods.
Because our hypergraph based methods can jointly learn node and graph embeddings, the losses in equation 56 can be weighted Ltotal (1- and co-optimized by Adam Optimizer with L2 regularization, where μ 0.5 in our experiment. We use grid search to select hyper-parameten 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 hyper-parameters can see Table 9), and the results are shown in Table 12.
1.5.2 PROTEIN FOLD CLASSIFICATION
Datasets and settings The dataset that we used for training, validation and test is SCOPe 1.75 data of Hou al. (2018). This dataset includes 16,712 proteins covering 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 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 present in the training set.
For baselines, we include sequence-bard based methods pre-trained unsupervised on millions of protein sequences: Rao et al. (2019); Bepler & Berger (2018); Strodthoff al. (2020), 3D structure based model: Kipf& & Welling 2): Diehl (2019); Baldassarre et al. (2020) and Gligorijevic al. (2020), who process the sequence with LSTM first and then apply GCNN. The accuracy of the above base- lines 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 Table 7.
I.6 SHER-SMOOTHING ANALYSIS.
Table 14 shows that our proposed SHSC significantly alleviates the performance descending with the increase of layers. Given the same layers, can be observed that our SHSC almost outperforms the other methods for all cases, especially at deep layer, which demonstrates the benefits of deep model and the long-range information around hypergraph. Furthermore, should be noted that the optimal layer numbers K of our SHSC are generally larger than other models, due to the only one
41

---

Under review as a conference paper at ICLR 2022
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 neural network to capture high-order relationships.
Table 14:
Summary of classification accuracy (%) results with various depths. In our SHSC. the number of layers is equivalent to K in equation 8. We report mean test accuracy over 10 train-test splits.
Layers
Dataset
Method
32
HyperGCN
60.66
57.50
31.09
31.10
30.09
31.09
HGNN
69.23
67.23
60.17
29.28
27.15
26.62
Cora
GHCN (ours)
74.79
72.86
63.99
31.03
30.46
31.09
(co-authorship)
SHSC (ours)
74.60
75.78
75.70
75.04
75.26
74.79
HyperGCN
84.82
54.65
22.37
23.96
23.04
24.13
HGNN
88.55
88.28
85.38
27.64
27.62
27.56
DBLP
GHCN (ours)
89.04
88.90
85.15
27.61
27.61
27.62
(co-authorship)
SHSC (ours)
86.63
88.26
89.00
89.17
89.05
88.60
HyPerGCN
62.35
58.29
31.09
31.17
31.09
29.68
HGNN
55.60
55.72
42.10
16.16
24.40
24.43
Cora
GHCN (ours)
69.03
69.45
57.37
28.21
26.27
26.95
(co-citation)
SHSC (ours)
62,21
64.57
67.59
68.96
69.37
68.15
HyperGCN
68. 12
63.59
39.99
39.97
40.01
40.02
HGNN
46.41
47.16
40.93
40.24
40.30
40.29
Pubmed
GHCN (ours)
75.37
74.76
60.65
40.38
40.31
40.42
(co-citation)
SHSC (ours)
74.39
74.91
74.41
73.90
72.79
71.49
HyperGCN
56.94
36.75
20.72
20.41
20.16
18.95
HGNN
39.93
38.98
36.67
19.91
19.86
19.79
Citeseer
GHCN (ours)
62.67
61.50
49.94
21.95
21.84
21.93
(co-citation)
SHSC (ours)
61.63
62.75
63.86
64.62
65.14
65.10
1.7 SENSITIVITY ANALYSIS
The proposed SHSC model performance on co-authorship Cora, co-citation cora and co-citation Pubmed with different o, B and is reported in Figure 8. For σ,, 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 negative effect in most cases. For 3, with the growth of 8, the performance of SHSC stably increases, which means that the diffusion kernel useful for information aggregation. Moreover, the fact that the performance remains stable on cora (coauthorship) and pubmed (cocitation) when 3 is at 0.8-1.0 suggests we can only adjust this hyper-parameter range of large value. For a, the tendency of is similar to 3, so we can also adjust this haper-parameter range of large value to obtain a satisfying performance.
see that the best choice
cora (cocitation)
(cocitation)
(cocitation! pubmed (codiatiio)
(coctation) thoshiporship)
pubmod (cadiattio) (coauthership)
cara (csouthorship)
Figure 8: Test accuracy by varying the hyper- Syper-parameters (left), (middle) and (right) of SHSC.
1.8 THE SPECTRUM ANALYSIS OF SHSC
We calculate the eigenvalues (3 d + B)1 with various (a, B) on NTU2012
dataset (DV) 2012) and count the number of eigenvalues in different size ranges, which is shown
42

---

Under review as a conference paper at ICLR 2022
in the Table 15. The table suggests that SHSC is able to capture both low and high frequency information of the graph signal, depending on the selection the appropriate 9).
Table 15: The number of eigenvalues of SHSC in different size ranges
NTU2012 dataset.
0.8
2 0.0
2 0.1
A A20.2 0.2
2 0.3
2 0.4
A
0.5
2 0.6
A 2 0.7
À
0.8
À 0.9
(1.1)
2012
364
163
108
82
66
52
38
26
13
(1,0.8)
2012
327
140
90
71
51
33
19
1
(0.8,1)
2012
161
40
0
0
0
0
0
(0.8,0.8)
2012
139
8
0
0
0
1.9 ABLATION ANALYSIS
In order to verify the effectiveness of our proposed edge-dependent vertex weight Q and the neces- sity of re-normalization trick, we conduct an ablation analysis and report the results in Table 16. Specially, w/o Q is 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 mainly caused by the row in the adjacent isolated point is O (Figure 4), resulting in direct loss of its vertex in- formation (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.
matrix corresponding
Table 16: Test accuracy (%) of our methods for ablation analysis. We report mean +tanndard deviation. Cora and Pubmed the datasets that do contain Q we just report the w/o renormalization results. NTU and ModeINet4O constructed by Feng et al. (2019) are both connected hypergraph networks this work.
methods
Cora (co- authhothhr)hpp) Pubmed (co- soociitaioon
NTU
ModelNet40
with both
74.79:10.91
75.37
85.15110.3
97.28:10.15
w/o Q
84.93+0.31
97.18+0.20
GHCN
w/o renormalization
69.23+1.6
46.41-0.70
84.85+0.30
97.20+0.15
w/o both
84.2110.25
97.15:1.114
with both
75.91
74.60-1.4
83.3510,30
91.7410.05
w/o Q
82.84+0.40
97.65++0008
SHSC
w/o renormalization
75.76+:0.69
73.834-2.1
82.92-0.47
97.7410.05
w/o both
82.55+00.66
97.69+0.07
I.10 EXAMPLES OF p
We give many examples for p. including random, -1, sigmoid(a)) '220 expp - log(x) eerp(x) and exp(-x), and the experimental results citation networks can be seen the table 17. Regarding learnable A. we will as a future work.
Table 17: classifificaiton accuracy(standard deviation) with different p
dataset
model
random
sigmend((r)
Jin uxpl 277
loy(x)
exp(x)
cap( -xp(-x)
puhmed
GHCN
0.74(+0.01)
0.75(=
0.74(+0.02)
0.74(+0.01)
0.74(+-002)
0.73(+-002)
0.73(-0.01)
pubmed
SHSC
0.75(+0.01)
0.75(=0.0)
0.75(+0.01)
0.75(+0.01)
0.75(+0.01)
0.74(+0.01)
0.74(=0.01)
cora
GHCN
0.72(+0.02) 0.70(-
0.72(+0..0)
0.72(+0.01)
0.71(++0.02)
0.71(+0.01)
0.601 -0.02
cura
SUSC
0.72(10.01)
0.73(10.01)
0.72(10.01)
0.73(10.01)
0.72(10.01)
0.72(11.01)
0.64(10.01)
43

---

Under review as a conference paper at ICLR 2022
1.11 RUNNING TIME AND COMPUTATIONAL COMPLEXITY
Firstly, we analyze the theoretical computational complexity of our GHCN and SHSC: For GHCN, the computational cost is the ((E))) where | the total edge count in equivalent undigraph. Each sparse matrix multipiccation TX costs El.d. d. And the computational of HGNN the same as GHCN. For SHSC, the computational cost is the O E + K[Vd), which includes K sparse matrix multiplication and K summation over filters( (V]d d the cost of adding features X). 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 magnitude as SOTA'S approach UniGNN and outperform the HyperGCN and HGAT.
Table 18: The average training time epoch with different methods citation network classification task is shown below and timings measured in seconds. The float in parentheses is the standard deviation.
Methods
cora coauthorship
dhlp coauthoshhip
cora cocitation
puhmed cncitation
citescer cocitation
HlyperGCN
0.150C10.058)
1.181(10.07))
0.151(10.029)
1.203(10. 104)
0.130C10.0299
HGNN
0.005(+0.002)
0.0.1(+00.06)
0.005(=0.040)
0.008(+0.002)
0.005(+0.002)
UniGNN
0.014(+0.044)
0.042(++0.00)
0.014(=0.042)
0.023(+0.043)
0.0168(+0.043)
INNINN
0.001(_0.0066) 0,007(100014)
0.001(010.004)
0.009(10.006,
0.001(10.003)
ChehNet
0.027(+0.005)
0.063(#0.001)
0.073(=0.008)
0.050(+0.019)
0.067(=0.0198)
SSGC
0.055(+0.001)
0.291(+0.001)
0.205(+0.003)
0.135(+0.056)
0.193(+0.057)
HIGAT
0.381(10.080)
0.279(10.083)
1.329(10.011)
0.286(10.087)
GHCN(ours) SHSC(ourS)
0.005(+0.036)
0.020(+0.079)
0.005(=0.039)
0.011(+0.075)
0.081(+0.091)
0.016(+0.010)
0.072(+:0000)
0.038(+00005)
0.011(+00002)
0.027(+00001)
1.12
THE EDGE-DEPENDENT VERTEX WEIGHTS VISUALIZATION
1.12.1
VISUAL OBJECT
Figure The edge-dependent vertex weights of NTU2012 dataset (MVCNN feature MVCNN structure). The figure on the left represents the distance- vertex weights matrix Q used in our GHCN and SHSC. The middle (Q) and right (Q2) denote the node-level and edge-level attention coefficient matrix of HGAT (Ding al., 2020), respectively.
44

---

Under review as a conference paper at ICLR 2022
1.13 ADDITIONAL EXPERIMENTS OF BASELINES.
Table 19: Summary of classificaiton accuracy(% (%) results. We report the average test accuracy and its standard deviation over 10 train-test splits. The number in parentheses corresponds to the number of layers of the model. (OOM: our of memory)
Cora
DBLP (co-authorshipp
Cora (co-citation)
Pubmed (co-citation)
Citeseer
Dataset
Architecture
(co-authorship)
(co-citation)
MLP
$2.02+1.7
78.72-+0.6
52.02-1.7 1.7
69.86
55.03++1
HyperGCN
spectral-bused
10.8
82.89.99.7
9.3
68. 12:19.7
66,9411.3
HGNN
spectral based
69.23-+1.66
88.55++0.18
55.60=1.8
46.41+0.7
38.98+1.. 1.1
HNHN
message-pasee passing
84.43-+0.3
41.59-3.1
41.94+4.77
33.60+2.11
HGAT
message-pont passing
65.42.11.5
OOM
52.21=3.5
46.28.10.53
38.32.1..5
URiGNN
message passing
15.30
88 88.8010.2
70.10=1.4
74.4011.0
63.60
ChebNet
spectral-bused bused
42.27:12.2
85.81::5.22
45.35:12.37
6..73
48.44:10.91
APPNP
spectral-bused
68.25:11.9
86.99110.33
64.50=1.7
72.02+14
55.05=2..0
SSGC
spectral-based
72.04:1.2
88.6110.16
68.79-2.1
74,4941.3
60.5221.7
GHCN (ours)
spectral-bused spectral-bused
74.79=0.91 76.05=0.7506)
09.00411.19
75.37=1.22 75.08=1.1(4)
6..67:1.2
SHSC (ours)
89.1710.21(16)
70.641:1.8 (32)
65.14=0097(22)
Table 20: Test accuracy on visual object classification, Each model we ran 10 random seeds and report the + standard deviation. BOTH means GVCNN+MVCNN, which represents combining the features structures generate multi-modal data.
Datasets
Feature
Structure
HGNN
UniGNN
HGAT
ChebNet
SSGC
GHCN(ours)
SHSCtours)
MVCNN MVCNN
80.11=0.38
75.25=0.17
80.40-0.47
72.17+3.0
81.23:0.24
81.3740.63
82.56 0_39
NTU
GVCNN GVCNN
84.26=0.30 84.634
84.45=0.12
82.52=11.0
84.26:1.12
85.15:1.34
83.35=0.30
BOTH
BOTH
83.54=0.50 84:45-0:40
84.05=0.36
79.17+1..8
84.13:1.,34
84.45:0:40
85.12-0.25
MVCNN MVCNN
91.28=0011 90.36=0.10
91.29=0.15
85.8115.2
91.2110.11
91.9910.16
92.01=0.08
Model-
GVCNN GVCNN
92.53-00066 92.8
9244-0011
92.08-0.17
92.7411.04
92.66:10.10
92.69-0.06
Ner00
BOTH
BOTH
97.15=0.14 96.69=0.07
96.44=0.15
85.98+17
97.07=10.07
97.28+0.15
97.78 0.03
45


Reviews:
[{"review_id": "i0uuMpOZbDz", "reviewer": "Reviewer_NwNk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The theory for the equivalency between generalized hypergraph and undigraph is interesting, which allows using any GNNs designed for undigraphs to solve hypergraph problems in principle.\n2. The strong empirical performance.\n3. The introduction of two new tasks: protein quality assessment and protein fold classification for hypergraph GNNs.\n\nWeaknesses:\n1. The Notations part in Sec. 2 is not clear at first glance. For example, what is $q_e(u)$ and what is $q_(u)$? They are used without definitions.\n2. The Introduction contains many unfamiliar terms for people not working on hypergraphs, such as edge-dependent (independent)-vertex weights. I am confused on their meanings until reading into Sec 2.1\n3. The theory only shows that performing two-step random walk on weighted hypergraphs can be equivalent to performing random walk on a weighted graph under some conditions. However, it does not clearly tell whether the mapping from hypergraph to graph is injective, i.e., from the weighted graph you can perfectly recover the original hypergraph. Can the authors comment on that?", "summary_of_the_paper": "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.", "summary_of_the_review": "Though I am not familiar with the hypergraph field, this paper seems to provide some useful theory and techniques for hypergraph learning. I resort to other reviewers to evaluate the novelty and significance of the theory.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WAhToP5wZr1", "reviewer": "Reviewer_RmER", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### **Strengths**\n\n1. **Quality of Paper**\n\nThe paper is technically sound and claims are well supported by theoretical analysis. \nExtensive experimentation across different domains adds to the quality of the paper.\nThe paper also discusses limitations in addition to highlighting its strengths.\n\n\n2. **Clarity of Presentation**\n\nThe paper is clearly written and well organised. \nThe appendix is comprehensive with both theoretical proofs and empirical details (e.g., dataset construction, hyperparameters, etc.). \nThe authors have also released the source code as part of the supplementary material. \n\n\n### **Weaknesses**\n\n1. **Originality of Contributions**\n\nThe theory of equivalence between EDVW hypergraph and undirected graph is a small contribution of the paper in which vertex weights are added into the first step of the random walk. Empirically, however, edge-dependent vertex weights have been previously explored  in the form of attention mechanisms (node-level and edge-level attention mechanisms), e.g., the HGAT model proposed in (i) Be More with Less: Hypergraph Attention Networks for Inductive Text Classification, EMNLP'20, and (ii) Session-based Recommendation with Hypergraph Attention Networks, SDM'21. Another weakness of the paper is that once the Laplacian is defined, the proposed methods, viz., GHCN and SHSC are straightforward applications of existing spectral convolutional methods viz., ChebNet [Defferrard et al. NeurIPS'16] and SSGC [Zhu & Koniusz, ICLR'21] to hypergraphs.\n\n\n2. **Significance of Empirical Evaluation**\n\nThe paper can be significantly improved by comparing with the HGAT baseline, i.e., a baseline with node-level, edge-level attention mechanisms.\nMoreover, SSGC and ChebNet on the clique expansion are also important missing baselines in all the experiments. \nEmpirical insights (e.g., comparison of attention weights and weights in the proposed $Q$ matrix for visual and protein data) would improve the paper. ", "summary_of_the_paper": "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:\n1) Proposal of a generalised hypergraph capturing EDVWs with equivalence to undirected graphs,\n2) Proposal of a Laplacian based on the generalised EDVW and exploration of existing spectral convolutional methods, and\n3) Empirical evaluation on academic, protein, and visual object datasets.", "summary_of_the_review": "Overall the paper is clear and of good quality with claims being well supported by theoretical analysis. However, the novelty is incremental and experimental results are marginally significant. Positioning with important prior work and evaluation with missing baselines would significantly improve the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SzGQs5Bgu5y", "reviewer": "Reviewer_zaDF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n1. This paper provides some theoretical understanding of the equivalency of hypergraphs and undirected graphs.\n\nWeakness\n1. The paper is not very well written. The motivation is not clearly described.\n2. Some concepts and definitions are not clearly presented. \n3. Traditional GNN methods for undirected graphs should be included as baselines.\n\nMore comments\n\n1. It would be better if the authors could provide more motivation for transferring hypergraphs into undirected graphs. What are the benefits? Are the equivalency through random walks good enough for downstream tasks? Will there be information loss when transferring hypergraphs into undirected graphs?\n2. Definition 1 is not clearly presented. Specifically, why there are suddenly two Q matrices, what are their relation to the common definition of hypergraph, which only has a single matrix Q. Also, what is $\\rho$ for? \n3. What is the concept of ``oversmoothing issue'' for hypergraphs? Is it defined upon the corresponding undirected graphs? \n4. In Section 3, are these two spectral operations developed based on the Laplacian matrix for the corresponding undirected graphs? If so, how are they different from the existing methods for undirected graphs? Why not directly adopt existing operations for undirected graphs? Do they have any specialty corresponding to the hypergraphs? \n5. In Section 4.1, what are the benefits of modeling the citation datasets as hypergraphs? Also, other baselines for undirected graphs such as GCN and APPNP (the SHSC is a bit similar to APPNP) should be included. \n6. In Section 4.3, why is constructing such hypergraphs for the protein reasonable? It would be better if the authors could provide more explanations. \n\n", "summary_of_the_paper": "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. \bThey further proposed two spectral-based convolution operations for the undigraphs. \n", "summary_of_the_review": "Overall, the motivation for building such equivalency is not very clearly presented. The proposed convolution operations seem to be ``general'' for undirected graphs but not specifically related to the hypergraphs (except for the involved Laplacian is derived from the hypergraph). Also, it would be better if the authors could include existing GNN methods for undirected graphs for comparison to demonstrate the superiority of their proposed framework. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "M5ZFNeeccnA", "reviewer": "Reviewer_NQ7e", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main strengths of this paper are as follows:\n\n+ The paper is well-written and clearly explains both pros and cons of the methods. The technical contributions are sufficiently novel and deep. The experimental results justify the main claims made by the paper.\n\n+ There are a number of new ideas in the paper that may be useful independently.\n\n+ The considered problem of developing Hypergraph convolutional NN is practically relevant and useful in many applications (the paper already shows 4 such applications).\n\nThe main weakness of the paper are as follows:\n\nTo a large extent I did not find any significant weakness of this paper. The paper was very well-written and they already go in significant depth on the weakness of their methods.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall I am very positive about this paper.  AS mentioned above, I find the techniques and the evaluation to be solid with very little in terms of weakness.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Standard algorithms for deep hypergraph learning have not been designed for hypergraphs with edge-dependent vertex weights (EDVWs), where the weight of a vertex can depend on the edge of which it isa member. This paper develops a connection between EDVW-hypergraphs and undirected simple graphs, thus enabling the use of existing undirected-graph neural networks as subroutines. This is done via a unified random-walk framework.

(Two typos: ``equivalency" should be ``equivalence", and ``undigraphs" should be ``undirected graphs".) 

The theory of equivalence between EDVW-hypergraphs and undirected graphs via random walks is a good contribution. The experimentation across different domains is laudable. 

However, there are concerns over the lack of key baselines in the experiments. The author rebuttal has presented additional results with some baselines: sensitive hyperparameters (e.g., learning rate) are not tuned for the baselines. The clarity of the paper is mixed. The map from hypergraphs to graphs is not injective, so there could be ambiguity issues (different hypergraphs mapped to the same graph, thus having the same representations). 

Also, the contributions of Section 3 (designed for simple undirected graphs alone) do not appear significantly novel.
Decision: Reject