# Co-Representation Neural Hypergraph Diffusion
for Edge-Dependent Node Classification

Yijia Zheng Marcel Worring
University of Amsterdam, Amsterdam, the Netherlands
{y.zheng<EMAIL_ADDRESS>

###### Abstract

Hypergraphs are widely employed to represent complex higher-order
relationships in real-world applications. Most hypergraph learning research
focuses on node- or edge-level tasks. A practically relevant but more
challenging task, edge-dependent node classification (ENC), is only recently
proposed. In ENC, a node can have different labels across different
hyperedges, which requires the modeling of node-hyperedge pairs instead of
single nodes or hyperedges. Existing solutions for this task are based on
message passing and model within-edge and within-node interactions as multi-
input single-output functions. This brings three limitations: (1) non-adaptive
representation size, (2) node/edge agnostic messages, and (3) insufficient
interactions among nodes or hyperedges. To tackle these limitations, we
develop CoNHD, a new solution based on hypergraph diffusion. Specifically, we
first extend hypergraph diffusion using node-hyperedge co-representations.
This extension explicitly models both within-edge and within-node interactions
as multi-input multi-output functions using two equivariant diffusion
operators. To avoid handcrafted regularization functions, we propose a neural
implementation for the co-representation hypergraph diffusion process.
Extensive experiments demonstrate the effectiveness and efficiency of the
proposed CoNHD model.

###  1 Introduction

Real-world applications often involve intricate higher-order relationships
that cannot be represented by traditional graphs with pairwise connections [1,
2, 3, 4]. Hypergraphs, where an edge can connect more than two nodes, provide
a flexible structure to represent these relationships [5, 6, 7, 8]. Many
hypergraph learning methods are proposed to learn effective node or hyperedge
representations [9, 10, 11]. These methods, however, are insufficient for
predicting labels related to node-hyperedge pairs. For example, in a co-
authorship hypergraph, a researcher may contribute differently to various
academic papers, taking on distinct roles such as the first or last author. To
initiate the development of effective solutions for such scenarios, Choe et
al. [12] propose a new problem namely edge-dependent node classification
(ENC), where a node can have different labels across different hyperedges.
Addressing this problem requires modeling the node features unique to each
hyperedge, which is more complex and requires considering the hypergraph
structure. Despite its importance and usefulness in many real-world
applications [13, 14, 15, 16], the ENC problem is still under-explored.

Previous work on ENC only explores solutions using message passing-based
hypergraph neural networks (HGNNs) [17, 18]. To avoid confusion, in this
paper, message passing refers specifically to the HGNN architecture
illustrated in Fig. 1(b), which employs a two-stage aggregation process. The
first stage aggregates messages from nodes to update the hyperedge
representation, while the second stage aggregates messages from hyperedges to
update the node representation. The edge and node representations are then
concatenated and used to predict edge-dependent node labels [12]. Message
passing is simple and intuitive, but does it yield the most effective
solution?

To study the characteristics of message passing, we analyze its input-output
relations. The two-stage aggregation process in message passing essentially
models two key types of interactions: within-edge interactions (different
nodes connected by a hyperedge) and within-node interactions (different
hyperedges sharing a common node). Message passing models these interactions
as multi-input single-output aggregation functions, which brings three
limitations:

  * •

Non-adaptive representation size. Considering within-node interactions,
messages from numerous hyperedges are aggregated to a fixed-size node
representation vector. As indicated in [19], this can cause potential
information loss for large-degree nodes, which have more neighboring
hyperedges and should have larger representation size. Analogously, the edge
representations suffer from the same problem.

  * •

Node/Edge agnostic messages. As the aggregated node representation loses edge-
dependent information, the node can only pass the same message to different
hyperedges. However, different hyperedges may focus on different properties of
the node and should receive different messages. While some methods, as shown
in Fig. 1(c), attempt to extract edge-dependent information from one node
representation [19, 20, 12], this extraction process increases the learning
difficulty.

  * •

Insufficient interactions among nodes or hyperedges. The single-output design
cannot include direct nodes-to-nodes or edges-to-edges interactions, as this
requires multiple outputs for different elements. These direct interactions
are shown to be critical for hypergraph learning [21].

To tackle the limitations of message passing and to develop an effective ENC
solution, we should model the within-edge and within-node interactions as
multi-input multi-output functions.

Figure 1: Different HGNN architectures. (a) A hypergraph example with three
nodes and two hyperedges. (b) The message passing framework aggregates
messages from nodes to hyperedges and then from hyperedges back to nodes. (c)
Edge-dependent message passing methods extract edge(node)-dependent node(edge)
representations (dashed circle) before aggregation. (d) CoNHD learns a co-
representation, instead of separate node and hyperedge representations, for
each node-hyperedge pair. Two equivariant neural diffusion operators, _i.e._ ,
$\phi$ and $\varphi$, model the within-edge and within-node interactions as
multi-input multi-output functions, which can generate different diffusing
information for different node-hyperedge pairs. The within-edge and within-
node diffusing information is then utilized to update the co-representations.

We develop a new solution based on hypergraph diffusion [22, 23, 24, 25].
(Hyper)graph diffusion is inspired by physical diffusion processes, where
information on each node propagates to its neighboring nodes through diffusion
operators [26, 27]. As indicated in [20], an important characteristic of
hypergraph diffusion operators is the permutation equivariance property, which
means that reordering the inputs of the operator leads to corresponding
outputs in the same order. As the hyperedges and nodes are inherently
unordered, equivariance is necessary for modeling the multi-input multi-output
interactions, which ensures that the output for each element is unaffected by
the input ordering. Previous hypergraph diffusion models, however, only
consider nodes-to-nodes interactions without representations for the
hyperedges, which is not sufficient for ENC. In this paper, we extend the
concept of hypergraph diffusion to make it applicable to the ENC problem.

We propose CoNHD (Co-representation Neural Hypergraph Diffusion), an effective
hypergraph neural network based on hypergraph diffusion. We first extend
hypergraph diffusion to learn node-hyperedge co-representations, enabling its
application for ENC. This extension can model both within-edge and within-node
interactions as multi-input multi-output functions. Furthermore, we present a
neural implementation for co-representation hypergraph diffusion, which can
adaptively learn suitable diffusion operators from the data. The general
framework is shown in Fig. 1(d).

Our main contributions are summarized as follow:

  1. 1.

We define co-representation hypergraph diffusion, a new concept that
generalizes hypergraph diffusion using node-hyperedge co-representations. This
allows the extension of existing hypergraph diffusion methods to tackle the
ENC problem.

  2. 2.

We propose CoNHD, a neural implementation for the co-representation hypergraph
diffusion process. This naturally leads to a novel and effective HGNN
architecture that can easily adapt to different ENC datasets.

  3. 3.

We conduct extensive experiments to validate the effectiveness and efficiency
of CoNHD. The results demonstrate that CoNHD can achieve the best performance
on six real-world ENC datasets without sacrificing efficiency.

###  2 Related Work

Hypergraph Neural Networks. Inspired by the success of graph neural networks
(GNNs) [28, 29, 30], hypergraph neural networks (HGNNs) have been proposed for
modeling complex higher-order relationships [31, 32, 33]. HyperGNN [34, 35]
and HCHA [36] define hypergraph convolution based on the clique expansion
graph. HyperGCN [37] reduces the clique expansion graph into an incomplete
graph with mediators. To directly utilize higher-order structures, HNHN [38]
and HyperSAGE [17] model the convolution layer as a two-stage message passing
process, where messages are first aggregated from nodes to hyperedges and then
back to nodes. HyperGAT [39] incorporates an attention mechanism during
aggregation. UniGNN [18] and AllSet [40] show that most existing HGNNs can be
represented in this two-stage message passing framework. Recent research
investigates edge-dependent node information in the aggregation process of
message passing [19, 20, 12, 41].

While most HGNN research focuses on node- or hyperedge-level tasks, like node
classification [42, 43, 44], node regression [45, 46], and edge reconstruction
[47, 48], the ENC problem remains less explored. The first to explore the ENC
problem is [12], which proposes WHATsNet, a solution based on message passing.
Although message passing has become the dominant framework in existing HGNN
research, it suffers from the limitations as discussed in the introduction due
to the multi-input single-output design and cannot effectively address the ENC
problem.

Hypergraph Diffusion. (Hyper)graph diffusion, taking inspiration from physical
diffusion processes, describes the process of information propagating from
each node to its neighboring nodes [49, 27]. The diffusing information is
modeled as the gradients derived from the edge regularization functions, which
provide regularization to the node representations within the same hyperedge
[24]. These functions are handcrafted without training weights. The technique
was first introduced to achieve local and global consistency in the graph
domain [50, 51], and was then generalized to hypergraphs [52, 8]. Zhou et al.
[52] propose a regularization function by reducing the higher-order structure
using clique expansion. To directly utilize the higher-order structures, Hein
et al. [53] propose a regularization function based on the total variation of
the hypergraph. Other regularization functions are designed to improve
parallelization ability and introduce non-linearity [54, 55, 24, 22]. To
efficiently calculate the diffusion process when using complex regularization
functions, some advanced optimization techniques have been investigated [56,
57]. While hypergraph diffusion methods have shown effectiveness in various
tasks like ranking, motif clustering, and signal processing [58, 25, 59, 60],
they are all restricted to node representations and cannot address the ENC
problem.

In this paper, we extend hypergraph diffusion using node-hyperedge co-
representations and parameterize this process using neural networks, resulting
in a novel HGNN architecture. Most related to our work is ED-HNN [20], which
presents a neural implementation for the traditional hypergraph diffusion.
However, their method is based on message passing, which still suffers from
the three limitations discussed in the introduction. Instead, we introduce co-
representations and model both within-edge and within-node interactions as
multi-input multi-output functions, which effectively tackles these
limitations and demonstrates significant improvements in our experiments.

###  3 Preliminaries

Notations. Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ denote a hypergraph,
where $\mathcal{V}=\\{v_{1},v_{2},\ldots,v_{n}\\}$ represents a set of $n$
nodes, and $\mathcal{E}=\\{e_{1},e_{2},\ldots,e_{m}\\}$ represents a set of
$m$ hyperedges. Each hyperedge $e_{i}\in\mathcal{E}$ is a non-empty subset of
$\mathcal{V}$ and can contain an arbitrary number of nodes.
$\mathcal{E}_{v}=\\{e\in\mathcal{E}|v\in e\\}$ represents the set of
hyperedges that contain node $v$, and $d_{v}=\lvert\mathcal{E}_{v}\rvert$ and
$d_{e}=\lvert e\rvert$ are the degrees of node $v$ and hyperedge $e$,
respectively. We use $v^{e}_{i}$ and $e^{v}_{j}$ to denote the $i$-th node in
hyperedge $e$ and the $j$-th hyperedge in $\mathcal{E}_{v}$.
$\boldsymbol{X}^{(0)}=[\boldsymbol{x}^{(0)}_{v_{1}},\ldots,\boldsymbol{x}^{(0)}_{v_{n}}]^{\top}$
is the initial node feature matrix.

Message Passing-based HGNNs. The two-stage message passing framework [18, 40],
which can represent most existing HGNNs, is formulated as:

$\displaystyle\boldsymbol{z}^{(t+1)}_{e}=$ $\displaystyle
f_{\mathcal{V}\rightarrow\mathcal{E}}(\boldsymbol{X}^{(t)}_{e};\boldsymbol{z}^{(t)}_{e}),$
(1) $\displaystyle\tilde{\boldsymbol{x}}^{(t+1)}_{v}=$ $\displaystyle
f_{\mathcal{E}\rightarrow\mathcal{V}}(\boldsymbol{Z}^{(t+1)}_{v};\boldsymbol{x}^{(t)}_{v}),$
(2) $\displaystyle\boldsymbol{x}^{(t+1)}_{v}=$ $\displaystyle
f_{\mathrm{skip}}(\tilde{\boldsymbol{x}}^{(t+1)}_{v},\boldsymbol{x}^{(t)}_{v},\boldsymbol{x}^{(0)}_{v}).$
(3)

Here $\boldsymbol{x}^{(t)}_{v}$ and $\boldsymbol{z}^{(t)}_{e}$ are the node
and hyperedge representations in the $(t)$-th iteration.
$\boldsymbol{z}^{(0)}_{e}$ is typically initialized by a zero vector or the
mean vector of the node features. $\boldsymbol{X}^{(t)}_{e}$ denotes the
representations of nodes contained in hyperedge $e$, _i.e._ ,
$\boldsymbol{X}^{(t)}_{e}=[\boldsymbol{x}^{(t)}_{v^{e}_{1}},\ldots,\boldsymbol{x}^{(t)}_{v^{e}_{d_{e}}}]^{\top}$.
Similarly,
$\boldsymbol{Z}^{(t)}_{v}=[\boldsymbol{z}^{(t)}_{e^{v}_{1}},\ldots,\boldsymbol{z}^{(t)}_{e^{v}_{d_{v}}}]^{\top}$
denotes the representations of hyperedges containing node $v$.
$f_{\mathcal{V}\rightarrow\mathcal{E}}$ and
$f_{\mathcal{E}\rightarrow\mathcal{V}}$ take multiple representations from
neighboring nodes or hyperedges as inputs, and output a single hyperedge or
node representation. Eq. 3 represents the optional skip connection of the
original features, which can help mitigate the over-smoothing issue [18].

Hypergraph Diffusion. Hypergraph diffusion learns all node representations
$\boldsymbol{\mathcal{X}}=[\boldsymbol{x}_{v_{1}},\ldots,\boldsymbol{x}_{v_{n}}]^{\top}$,
where $\boldsymbol{x}_{v_{i}}\in\mathbb{R}^{d}$, by the gradients of some
regularization functions [24, 61]. These regularization functions are also
referred to as potential functions or energy functions [20, 62], which are
predefined without trainable weights. We use
$\boldsymbol{X}_{e}=[\boldsymbol{x}_{v^{e}_{1}},\ldots,\boldsymbol{x}_{v^{e}_{d_{e}}}]^{\top}$
to denote the representations of nodes contained in a hyperedge $e$.

######  Definition 1 (Node-Representation Hypergraph Diffusion).

Given non-structural regularization functions
$\mathcal{R}_{v}(\cdot;\boldsymbol{a}_{v}):\mathbb{R}^{d}\rightarrow\mathbb{R}$
and edge regularization functions $\Omega_{e}(\cdot):\mathbb{R}^{d_{e}\times
d}\rightarrow\mathbb{R}$, the node-representation hypergraph diffusion learns
representations by solving the following problem

$\boldsymbol{\mathcal{X}}^{*}=\operatorname*{arg\,min}_{\boldsymbol{\mathcal{X}}}\sum_{v\in\mathcal{V}}\mathcal{R}_{v}(\boldsymbol{x}_{v};\boldsymbol{a}_{v})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{X}_{e}).$
(4)

The non-structural regularization function
$\mathcal{R}_{v}(\cdot;\boldsymbol{a}_{v})$ is independent of the hypergraph
structure, which is commonly defined as the squared loss function [52, 61].
$\boldsymbol{a}_{v}$ is the node attribute vector (composed of node features
[25] or observed node labels [24]). Many structural regularization functions
are proposed to implement the edge regularization functions
$\Omega_{e}(\cdot)$ [52, 53, 54, 55]. For example, the clique expansion (CE)
regularization functions [52], defined as
$\Omega_{\mathrm{CE}}(\boldsymbol{X}_{e}):=\sum_{v,u\in
e}\lVert\boldsymbol{x}_{v}-\boldsymbol{x}_{u}\rVert_{2}^{2}$, tend to force
all the node representations in a hyperedge to become similar.

###  4 Methodology

####  4.1 Co-Representation Hypergraph Diffusion

In this section, we extend the current hypergraph diffusion concept using co-
representations of node-hyperedge pairs. This extension enables its
application in addressing the ENC problem [12].

######  Problem 1 (Edge-Dependent Node Classification (ENC)).

Given (1) a hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, (2) observed
edge-dependent node labels in $\mathcal{E}^{\prime}\subset\mathcal{E}$ (i.e.,
$y_{v,e},\forall v\in e,\forall e\in\mathcal{E}^{\prime}$), and (3) an initial
node feature matrix $\boldsymbol{X}^{(0)}$ (optional), the ENC problem is to
predict the unobserved edge-dependent node labels in
$\mathcal{E}\setminus\mathcal{E}^{\prime}$ (i.e., $y_{v,e},\forall v\in
e,\forall e\in\mathcal{E}\setminus\mathcal{E}^{\prime}$).

In ENC, the label $y_{v,e}$ is associated with both the node $v$ and the
hyperedge $e$. Therefore, we extend hypergraph diffusion to learn a co-
representation $\boldsymbol{h}_{v,e}\in\mathbb{R}^{d}$ for each node-hyperedge
pair $(v,e)$. We name this co-representation hypergraph diffusion. Let
$\boldsymbol{\mathcal{H}}=[\ldots,\boldsymbol{h}_{v,e},\ldots]^{\top}$ denote
the collection of all co-representation vectors. We use
$\boldsymbol{H}_{e}=[\boldsymbol{h}_{v^{e}_{1},e},\ldots,\boldsymbol{h}_{v^{e}_{d_{e}},e}]^{\top}$
and
$\boldsymbol{H}_{v}=[\boldsymbol{h}_{v,e^{v}_{1}},\ldots,\boldsymbol{h}_{v,e^{v}_{d_{v}}}]^{\top}$
to represent the co-representations associated with a hyperedge $e$ or a node
$v$, respectively.

######  Definition 2 (Co-Representation Hypergraph Diffusion).

Given non-structural regularization functions
$\mathcal{R}_{v,e}(\cdot;\boldsymbol{x}_{v}):\mathbb{R}^{d}\rightarrow\mathbb{R}$,
edge regularization functions $\Omega_{e}(\cdot):\mathbb{R}^{d_{e}\times
d}\rightarrow\mathbb{R}$, and node regularization functions
$\Omega_{v}(\cdot):\mathbb{R}^{d_{v}\times d}\rightarrow\mathbb{R}$, the co-
representation hypergraph diffusion learns representations by solving the
following optimization problem

$\boldsymbol{\mathcal{H}}^{*}=\operatorname*{arg\,min}_{\boldsymbol{\mathcal{H}}}\sum_{v\in\mathcal{V}}\sum_{e\in\mathcal{E}_{v}}\mathcal{R}_{v,e}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v,e})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{H}_{e})+\gamma\sum_{v\in\mathcal{V}}\Omega_{v}(\boldsymbol{H}_{v}).$
(5)

Here $\mathcal{R}_{v,e}(\cdot;\boldsymbol{a}_{v,e})$ is independent of the
hypergraph structure, where $\boldsymbol{a}_{v,e}$ can be any related
attributes of the node-hyperedge pair $(v,e)$ (_e.g._ , node features,
hyperedge features, or observed edge-dependent node labels).
$\Omega_{e}(\cdot)$ and $\Omega_{v}(\cdot)$ represents regularization for co-
representations associated with the same node or hyperedge, which can be
implemented using the structural regularization functions as in traditional
node-representation hypergraph diffusion [52, 53, 54, 55].

Depending on whether the regularization functions are differentiable, we can
solve Eq. 5 using one of two standard optimization methods: gradient descent
(GD) or alternating direction method of multipliers (ADMM) [63]. When the
regularization functions are differentiable, we first initialize
$\boldsymbol{h}_{v,e}^{(0)}=\boldsymbol{a}_{v,e}$, and then solve it using GD
with a step size $\alpha$:

$\boldsymbol{h}^{(t+1)}_{v,e}=\boldsymbol{h}^{(t)}_{v,e}-\alpha(\nabla\mathcal{R}_{v,e}(\boldsymbol{h}^{(t)}_{v,e};\boldsymbol{a}_{v,e})+\lambda[\nabla\Omega_{e}(\boldsymbol{H}^{(t)}_{e})]_{v}+\gamma[\nabla\Omega_{v}(\boldsymbol{H}^{(t)}_{v})]_{e}),$
(6)

where $\nabla$ is the gradient operator. $[\cdot]_{v}$ and $[\cdot]_{e}$
represent the gradient vector associated with node $v$ and hyperedge $e$,
respectively. For example, $[\nabla\Omega_{e}(\boldsymbol{H}^{(t)}_{e})]_{v}$
represents the gradient w.r.t. $\boldsymbol{h}^{(t)}_{v,e}$.

When the regularization functions are not all differentiable (_e.g._ , the
total variation (TV) regularization functions [53] or the Lovász extension
cardinality-based (LEC) regularization functions [54]), we can apply ADMM to
find the optimal solution. We first introduce auxiliary variables
$\boldsymbol{U}_{e}$ and $\boldsymbol{Z}_{v}$ for each hyperedge and node,
respectively. All variables are initialized as
$\boldsymbol{h}_{v,e}^{(0)}=\boldsymbol{a}_{v,e}$,
$\boldsymbol{U}^{(0)}_{e}=\boldsymbol{H}^{(0)}_{e}$, and
$\boldsymbol{Z}^{(0)}_{v}=\boldsymbol{H}^{(0)}_{v}$, and then updated
iteratively as follows:

$\displaystyle\boldsymbol{U}_{e}^{(t+1)}=$
$\displaystyle\mathbf{prox}_{\lambda\Omega_{e}/\rho}(2\boldsymbol{H}^{(t)}_{e}-\boldsymbol{U}^{(t)}_{e})+\boldsymbol{U}^{(t)}_{e}-\boldsymbol{H}^{(t)}_{e},$
(7) $\displaystyle\boldsymbol{Z}_{v}^{(t+1)}=$
$\displaystyle\mathbf{prox}_{\gamma\Omega_{v}/\rho}(2\boldsymbol{H}^{(t)}_{v}-\boldsymbol{Z}^{(t)}_{v})+\boldsymbol{Z}^{(t)}_{v}-\boldsymbol{H}^{(t)}_{v},$
(8) $\displaystyle\boldsymbol{h}_{v,e}^{(t+1)}=$
$\displaystyle\mathbf{prox}_{\mathcal{R}_{v,e}(\cdot;\boldsymbol{a}_{v,e})/2\rho}\Big{(}\frac{1}{2}\big{(}[\boldsymbol{U}^{(t+1)}_{e}]_{v}+[\boldsymbol{Z}_{v}^{(t+1)}]_{e}\big{)}\Big{)}.$
(9)

Here
$\mathbf{prox}_{g}(\boldsymbol{H}):=\operatorname*{arg\,min}_{\boldsymbol{H}^{\prime}}\left(g(\boldsymbol{H}^{\prime})+\frac{1}{2}\lVert\boldsymbol{H}^{\prime}-\boldsymbol{H}\rVert_{F}^{2}\right)$
is the proximity operator [63] in the ADMM method. The proximity operator of a
lower semi-continuous convex function is 1-Lipschitz continuous [64], enabling
its approximation by neural networks. $\rho$ is the scaling factor in the ADMM
method. We leave the derivation of Eq. 7-9 to Appendix D.1.

$\nabla\Omega_{e}(\cdot)$ or $\mathbf{prox}_{\lambda\Omega_{e}/\rho}(\cdot)$
in the GD or ADMM method are referred to as edge diffusion operators, which
generate within-edge information that should “diffuse” to each node-hyperedge
pair. In a similar way, $\nabla\Omega_{v}(\cdot)$ or
$\mathbf{prox}_{\gamma\Omega_{v}/\rho}(\cdot)$ are referred to as node
diffusion operators.

The hyperedges and nodes are inherently unordered, hence in designing
structural regularization functions it is important to ensure the outputs are
consistent regardless of the input ordering. We say a function
$g:\mathbb{R}^{n\times d}\rightarrow\mathbb{R}^{d^{\prime}}$ is permutation
invariant, if for any action $\pi$ from the row permutation group
$\mathbb{S}_{n}$, it holds that $g(\pi\cdot\boldsymbol{H})=g(\boldsymbol{H})$
for all $\boldsymbol{H}\in\mathbb{R}^{n\times d}$. Similarly, function
$g:\mathbb{R}^{n\times d}\rightarrow\mathbb{R}^{n\times d^{\prime}}$ is
permutation equivariant, if for any $\pi\in\mathbb{S}_{n}$, it holds that
$g(\pi\cdot\boldsymbol{H})=\pi\cdot g(\boldsymbol{H})$ for all
$\boldsymbol{H}\in\mathbb{R}^{n\times d}$. Existing structural regularization
functions are shown to be permutation invariant [20].

######  Proposition 1 (Wang et al. [20]).

With permutation invariant structural regularization functions, the diffusion
operators are permutation equivariant.

Proposition 1 shows that the edge and node diffusion operators are permutation
equivariant. This critical property enables the modeling of complex
interactions as multi-input multi-output functions while ensuring the outputs
can commute according to the input ordering.

Next, we show that the proposed co-representation hypergraph diffusion is a
more general concept than node-representation hypergraph diffusion.

######  Proposition 2.

The node-representation hypergraph diffusion is a special case of the co-
representation hypergraph diffusion.

We leave all the proofs to Appendix D. Node-representation hypergraph
diffusion is equivalent to imposing a strict constraint that all the co-
representations associated with the same node must be identical, resulting in
a single unified node representation. Instead, co-representation hypergraph
diffusion relaxes this constraint by introducing node regularization
functions, which enables multiple co-representations associated with the same
node to be different.

####  4.2 Co-representation Neural Hypergraph Diffusion

In this section, we propose CoNHD (Co-representation Neural Hypergraph
Diffusion), a neural implementation of the co-representation hypergraph
diffusion process, which can easily adapt to different ENC datasets. This
implementation naturally leads to the novel and effective HGNN architecture
illustrated in Fig. 1(d).

Equivariant Neural Diffusion Operators. Compared to the invariant aggregation
operators in message passing, the equivariant diffusion operators in
hypergraph diffusion can generate diverse diffusing information that is
specific to each node-hyperedge pair. Since nodes and hyperedges are
inherently unordered, the equivariance property of diffusion operators is
crucial for modeling multi-input multi-output interactions, which ensures that
the output for each node-hyperedge pair remains consistent regardless of the
input ordering. However, traditional diffusion operators rely on handcrafting
structural regularization functions, which is challenging and requires good
insights of the datasets. To mitigate this challenge, we use set-equivariant
neural networks to parameterize the edge and node diffusion operators, denoted
as $\phi(\cdot)$ and $\varphi(\cdot)$, which can be trained in a data-driven
manner while preserving the equivariance property. Apart from the unweighted
pooling-based implementation explored in [20], we also consider an
implementation based on self-attention, which has shown practical
effectiveness in many real-world applications [65, 12].

UNweighted Pooling (UNP). Unweighted pooling is widely investigated for
implementing set-equivariant neural networks [66, 67, 68]. Wang et al. [20]
provide an implementation and show its effectiveness in approximating the
node-representation hypergraph diffusion process. As it utilizes an unweighted
sum pooling to aggregate global set information, we refer to this
implementation as UNweighted Pooling. The UNP implementation can be
represented as follows:

$\texttt{UNP:}\quad[\textsc{Unp}(\boldsymbol{H})]_{i}=\textsc{Mlp}\Big{(}\Big{[}\boldsymbol{h}_{i},\sum_{\boldsymbol{h}_{j}\in\boldsymbol{H}}\textsc{Mlp}(\boldsymbol{h}_{j})\Big{]}\Big{)}.$
(10)

Here $\boldsymbol{H}\in\mathbb{R}^{n_{H}\times d}$ represents a matrix with
$n_{H}$ co-representation vectors, which can be replaced by
$\boldsymbol{H}_{e}$ or $\boldsymbol{H}_{v}$ according to the inputs of the
diffusion operators. $\textsc{Mlp}(\cdot)$ is a Multi-Layer Perceptron (MLP).
This simple implementation can approximate any continuous permutation
equivariant functions [20], leading to a universal approximator for our
diffusion operators. Besides, its time complexity is linear to the number of
the input co-representations.

Induced Set Attention Block (ISAB). The static unweighted sum pooling
operation ignores the importance of different elements, limiting its ability
to capture interactions in practice [69, 70, 71]. Therefore, we consider
another implementation using Set Transformer [69], which is based on self-
attention. Different from other HGNNs that employ the invariant aggregation
(single-output) module of Set Transformer [40, 12], our approach relies solely
on the permutation equivariant module ISAB to implement the multi-input multi-
output diffusion operators:

ISAB:
$\displaystyle\textsc{Isab}(\boldsymbol{H})=\textsc{Mab}(\boldsymbol{H},\textsc{Mab}(\boldsymbol{I},\boldsymbol{H})),$
(11) where
$\displaystyle\textsc{Mab}(\boldsymbol{Q},\boldsymbol{K})=\textsc{Ln}(\boldsymbol{M}+\textsc{Rff}(\boldsymbol{M})),\,\boldsymbol{M}=\textsc{Ln}(\boldsymbol{Q},\textsc{Multihead}(\boldsymbol{Q},\boldsymbol{K},\boldsymbol{K})),$
$\displaystyle\textsc{Multihead}(\boldsymbol{Q},\boldsymbol{K},\boldsymbol{V})=[\boldsymbol{O}_{1},\ldots,\boldsymbol{O}_{h}]\cdot\boldsymbol{W}^{O},\,$
$\displaystyle\boldsymbol{O}_{i}=\omega(\boldsymbol{Q}\boldsymbol{W}^{Q}_{i}(\boldsymbol{K}\boldsymbol{W}^{K}_{i})^{\top})\boldsymbol{V}\boldsymbol{W}^{V}_{i}.$

Here $\boldsymbol{I}$, $\boldsymbol{W}^{O}$, $\boldsymbol{W}^{Q}$,
$\boldsymbol{W}^{K}$, and $\boldsymbol{W}^{V}$ are all trainable weights.
$\textsc{Ln}(\cdot)$ denotes the layer normalization. $\textsc{Rff}(\cdot)$ is
a row-wise feed-forward layer. $\textsc{Multihead}(\cdot)$ is the multihead
attention mechanism and $\omega$ is the softmax function. ISAB utilizes a
fixed number of inducing points $\boldsymbol{I}\in\mathbb{R}^{k\times d}$ to
reduce the quadratic complexity in self attention to linear complexity [69],
which can increase the efficiency when modeling hypergraphs with larger node
and hyperedge degrees.

Co-representation Neural Hypergraph Diffusion. We build a neural
implementation for the co-representation hypergraph diffusion process using
two neural diffusion operators $\phi$ and $\varphi$. Following the update
rules of the GD or ADMM optimization in Eq. 6 or Eq. 7-9, we provide two
implementations of our model architecture. The $(t+1)$-th layer can be
represented as:

GD-based:
$\displaystyle\boldsymbol{M}^{(t+1)}_{e}=\phi(\boldsymbol{H}^{(t)}_{e}),\,\boldsymbol{M}^{\prime(t+1)}_{v}=\varphi(\boldsymbol{H}^{(t)}_{v}),$
(12)
$\displaystyle\boldsymbol{h}^{(t+1)}_{v,e}=\psi([\boldsymbol{h}^{(t)}_{v,e},\boldsymbol{m}^{(t+1)}_{v,e},\boldsymbol{m}^{\prime(t+1)}_{v,e},\boldsymbol{h}^{(0)}_{v,e}]),$
(13) ADMM-based:
$\displaystyle\boldsymbol{M}^{(t+1)}_{e}=\phi(2\boldsymbol{H}^{(t)}_{e}-\boldsymbol{M}^{(t)}_{e})+\boldsymbol{M}^{(t)}_{e}-\boldsymbol{H}^{(t)}_{e},$
(14)
$\displaystyle\boldsymbol{M}^{\prime(t+1)}_{v}=\varphi(2\boldsymbol{H}^{(t)}_{v}-\boldsymbol{M}^{\prime(t)}_{v})+\boldsymbol{M}^{\prime(t)}_{v}-\boldsymbol{H}^{(t)}_{v},$
(15)
$\displaystyle\boldsymbol{h}^{(t+1)}_{v,e}=\psi([\boldsymbol{m}^{(t+1)}_{v,e},\boldsymbol{m}^{\prime(t+1)}_{v,e},\boldsymbol{h}^{(0)}_{v,e}]).$
(16)

Here
$\boldsymbol{M}^{(t)}_{e}=[\boldsymbol{m}^{(t)}_{v^{e}_{1},e},\ldots,\boldsymbol{m}^{(t)}_{v^{e}_{d_{e}},e}]^{\top}$
and
$\boldsymbol{M}^{\prime(t)}_{v}=[\boldsymbol{m}^{\prime(t)}_{v,e^{v}_{1}},\ldots,\boldsymbol{m}^{\prime(t)}_{v,e^{v}_{d_{v}}}]$
are the within-edge and within-node diffusing information generated using the
neural diffusion operators $\phi$ and $\varphi$, which are implemented as
either UNP (Eq. 10) or ISAB (Eq. 11). $\psi(\cdot)$ collects the diffusing
information and updates the co-representation vectors. In our experiments, we
implement $\psi(\cdot)$ as a linear layer. $\boldsymbol{h}^{(0)}_{v,e}$ is the
initial feature vector, which corresponds to the non-structural regularization
term in Eq. 5. Due to the dependency of historical auxiliary variables, the
ADMM-based implementation needs to preserve the historical diffusing
information $\boldsymbol{M}^{(t)}_{e}$ and $\boldsymbol{M}^{\prime(t)}_{v}$
from the last step.

We compare the proposed CoNHD model to message passing-based HGNNs in Appendix
B. We show that CoNHD is expressive enough to represent any message passing-
based HGNNs. Besides, by modeling the within-edge and within-node interactions
as multi-input multi-output functions, CoNHD can effectively tackle the three
limitations of message passing as discussed in the introduction. Notably,
despite the increased expressiveness, CoNHD still maintains high efficiency.
We provide theoretical complexity analysis in Appendix F.1.

###  5 Experiments

####  5.1 Edge-Dependent Node Classification

Datasets. We conduct experiments on all six real-world ENC datasets in [12].
These datasets are Email (Email-Enron and Email-Eu), StackOverflow (Stack-
Biology and Stack-Physics), and Co-authorship networks (Coauth-DBLP and
Coauth-AMiner). The statistics are shown in Table 1. Notably, Email-Enron and
Email-Eu have relatively large node degrees, while Email-Enron has relatively
large hyperedge degrees as well. Further information can be found in Appendix
G.

Table 1: Statistics of six ENC datasets.

Dataset Num. of Nodes Num. of Edges Avg. $d_{v}$ Avg. $d_{e}$ Max. $d_{v}$
Max. $d_{e}$ Email-Enron 21,251 101,124 55.83 11.73 18,168 948 Email-Eu 986
209,508 549.54 2.59 8,659 59 Stack-Biology 15,490 26,823 3.63 2.10 1,318 12
Stack-Physics 80,936 200,811 5.93 2.39 6,332 48 Coauth-DBLP 108,484 91,266
2.96 3.52 236 36 Coauth-AMiner 1,712,433 2,037,605 3.03 2.55 752 115

Baselines. We compare the GD-based CoNHD model to 9 baseline models. For
CoNHD, we compare two variants with different neural diffusion operators, UNP
(Eq. 10) and ISAB (Eq. 11). The baselines include 6 models following the
traditional message passing framework (HNHN [38], HyperGNN [34], HCHA [36],
HAT [72], UniGCNII [18], and AllSetTransformer [40]) and 3 recent models that
utilize edge-dependent node information in message passing (HNN [19], ED-HNN
[20], and WHATsNet [12]). More details are provided in Appendix H.

Figure 2: Visualization of embeddings in the Email-Enron dataset using LDA.
The embeddings learned by CoNHD exhibit clearer distinctions based on the
edge-dependent labels compared to the embeddings learned by WHATsNet.

Effectiveness. As shown in Table 2, CoNHD consistently achieves the best
performance across all datasets in terms of both Micro-F1 and Macro-F1
metrics. Especially, CoNHD achieves significant improvements on Email-Enron
and Email-Eu datasets (with gains of approximately 10% on Email-Enron)
compared to the best baseline WHATsNet. As indicated before, the main
difference between these two datasets and the others is that they have
relatively large-degree nodes or hyperedges. All the baseline methods based on
node or hyperedge representations can easily cause potential information loss
for large degree nodes or hyperedges. In contrast, CoNHD can preserve specific
information for each node-hyperedge pair using co-representations. Besides,
compared to the aggregation operation in message passing, the two equivariant
neural diffusion operators in CoNHD can generate different diffusing
information to different node-hyperedge pairs, which is more expressive
especially when modeling interactions within a large-degree node or hyperedge.
This can explain why CoNHD can achieve more improvements on the two datasets
with larger node and hyperedge degrees.

The performance gap between the two neural diffusion operators in CoNHD is
minimal. While the UNP operator can theoretically approximate any equivariant
functions, the ISAB operator overall demonstrates better performance in our
experiments. This may be attributed to the practical effectiveness of the
attention mechanism, which is consistent with previous research [40].

Fig. 2 visualizes the learned embeddings of node-hyperedge pairs associated
with the largest-degree node in the Email-Enron dataset using LDA. CoNHD can
learn more separable embeddings than WHATsNet. We show more examples in
Appendix I.1.

Table 2: Performance of edge-dependent node classification. Bold numbers
indicate the best results. Underlined numbers indicate the second-best
results. “OOM” indicates “Out Of Memory”.

Email-Enron Email-Eu Stack-Biology Method Micro-F1 Macro-F1 Micro-F1 Macro-F1
Micro-F1 Macro-F1 HNHN [38] 0.738 $\pm$ 0.028 0.637 $\pm$ 0.023 0.643 $\pm$
0.004 0.552 $\pm$ 0.014 0.640 $\pm$ 0.005 0.592 $\pm$ 0.006 HyperGNN [34]
0.725 $\pm$ 0.004 0.674 $\pm$ 0.003 0.633 $\pm$ 0.001 0.533 $\pm$ 0.008 0.689
$\pm$ 0.002 0.624 $\pm$ 0.007 HCHA [36] 0.666 $\pm$ 0.010 0.464 $\pm$ 0.002
0.620 $\pm$ 0.000 0.497 $\pm$ 0.001 0.589 $\pm$ 0.007 0.465 $\pm$ 0.060 HAT
[72] 0.817 $\pm$ 0.001 0.753 $\pm$ 0.004 0.669 $\pm$ 0.001 0.638 $\pm$ 0.002
0.661 $\pm$ 0.005 0.606 $\pm$ 0.005 UniGCNII [18] 0.734 $\pm$ 0.010 0.656
$\pm$ 0.010 0.630 $\pm$ 0.005 0.565 $\pm$ 0.013 0.610 $\pm$ 0.004 0.433 $\pm$
0.007 AllSetTransformer [40] 0.796 $\pm$ 0.014 0.719 $\pm$ 0.020 0.666 $\pm$
0.005 0.624 $\pm$ 0.021 0.571 $\pm$ 0.054 0.446 $\pm$ 0.081 HNN [19] 0.763
$\pm$ 0.003 0.679 $\pm$ 0.007 OOM OOM 0.618 $\pm$ 0.015 0.568 $\pm$ 0.013 ED-
HNN [20] 0.778 $\pm$ 0.001 0.713 $\pm$ 0.004 0.648 $\pm$ 0.001 0.558 $\pm$
0.004 0.688 $\pm$ 0.005 0.506 $\pm$ 0.002 WHATsNet [12] 0.826 $\pm$ 0.001
0.760 $\pm$ 0.004 0.671 $\pm$ 0.000 0.646 $\pm$ 0.003 0.742 $\pm$ 0.003 0.686
$\pm$ 0.004 CoNHD (UNP) 0.905 $\pm$ 0.001 0.858 $\pm$ 0.004 0.708 $\pm$ 0.001
0.689 $\pm$ 0.001 0.748 $\pm$ 0.003 0.694 $\pm$ 0.005 CoNHD (ISAB) 0.911 $\pm$
0.001 0.871 $\pm$ 0.002 0.709 $\pm$ 0.001 0.690 $\pm$ 0.002 0.749 $\pm$ 0.002
0.695 $\pm$ 0.004 Stack-Physics Coauth-DBLP Coauth-AMiner Method Micro-F1
Macro-F1 Micro-F1 Macro-F1 Micro-F1 Macro-F1 HNHN [38] 0.506 $\pm$ 0.053 0.422
$\pm$ 0.043 0.486 $\pm$ 0.004 0.478 $\pm$ 0.008 0.520 $\pm$ 0.002 0.514 $\pm$
0.002 HyperGNN [34] 0.686 $\pm$ 0.004 0.630 $\pm$ 0.002 0.540 $\pm$ 0.004
0.519 $\pm$ 0.002 0.566 $\pm$ 0.002 0.551 $\pm$ 0.004 HCHA [36] 0.622 $\pm$
0.003 0.481 $\pm$ 0.007 0.451 $\pm$ 0.007 0.334 $\pm$ 0.048 0.468 $\pm$ 0.020
0.447 $\pm$ 0.040 HAT [72] 0.708 $\pm$ 0.005 0.643 $\pm$ 0.009 0.503 $\pm$
0.004 0.483 $\pm$ 0.006 0.543 $\pm$ 0.002 0.533 $\pm$ 0.003 UniGCNII [18]
0.671 $\pm$ 0.022 0.492 $\pm$ 0.016 0.497 $\pm$ 0.003 0.476 $\pm$ 0.002 0.520
$\pm$ 0.001 0.507 $\pm$ 0.001 AllSetTransformer [40] 0.728 $\pm$ 0.039 0.646
$\pm$ 0.046 0.495 $\pm$ 0.038 0.487 $\pm$ 0.040 0.577 $\pm$ 0.005 0.570 $\pm$
0.002 HNN [19] 0.683 $\pm$ 0.005 0.617 $\pm$ 0.005 0.488 $\pm$ 0.006 0.482
$\pm$ 0.006 0.543 $\pm$ 0.002 0.533 $\pm$ 0.002 ED-HNN [20] 0.726 $\pm$ 0.002
0.617 $\pm$ 0.006 0.514 $\pm$ 0.016 0.484 $\pm$ 0.024 0.503 $\pm$ 0.006 0.479
$\pm$ 0.008 WHATsNet [12] 0.770 $\pm$ 0.003 0.707 $\pm$ 0.004 0.605 $\pm$
0.002 0.595 $\pm$ 0.002 0.630 $\pm$ 0.005 0.623 $\pm$ 0.007 CoNHD (UNP) 0.776
$\pm$ 0.001 0.712 $\pm$ 0.005 0.609 $\pm$ 0.004 0.596 $\pm$ 0.003 0.630 $\pm$
0.002 0.626 $\pm$ 0.002 CoNHD (ISAB) 0.777 $\pm$ 0.001 0.710 $\pm$ 0.004 0.610
$\pm$ 0.002 0.595 $\pm$ 0.003 0.638 $\pm$ 0.002 0.632 $\pm$ 0.002

Figure 3: Comparison of the performance and training time (minutes). CoNHD
demonstrates significant improvements in terms of Micro-F1 while maintaining
good efficiency. The same conclusion holds for Marco-F1 (results not shown).

Efficiency. The performance and training time on Email-Enron and Email-Eu are
illustrated in Fig. 3. All experiments are conducted on a single NVIDIA A100
GPU. Only models using mini-batch training are considered in the comparison.
HCHA and HNN are excluded as their source code is based on full-batch
training, which is impractical when handling large real-world hypergraphs. The
best baseline, WHATsNet, sacrifices efficiency to improve performance. In
contrast, our proposed method, CoNHD, not only achieves the best performance
but also maintains high efficiency. In each layer, CoNHD only incorporates
direct neighbors of the node-hyperedge pairs, which can reduce the
computational costs compared to message passing. We provide more analysis in
Appendix F.2.

####  5.2 Approximation of Common Diffusion Operators

We conduct experiments to verify whether CoNHD, as a neural implementation of
co-representation hypergraph diffusion, can effectively approximate common
hypergraph diffusion operators.

Datasets. We use the Senate [73] dataset with the same 1-dimensional feature
initialization as in [20]. Although our proposed CoNHD model can accept any
input features related to the node-hyperedge pairs, we only utilize initial
node features to fit the input of other baseline HGNNs. To generate the
labels, we perform the co-representation hypergraph diffusion process using
three common diffusion operators: CE [52], TV [53], and LEC [54]. More details
can be found in Appendix G.

Baselines. We compare both ADMM-based (Eq. 14-16) and GD-based (Eq. 12-13)
implementations of the proposed CoNHD model (with ISAB operator) to two
baseline methods, ED-HNN [20] and WHATsNet [12]. ED-HNN is a universal
approximator for any node-representation hypergraph diffusion process, while
WHATsNet is the best baseline in the ENC experiments.

Table 3: MAE ($\downarrow$) results of approximating common diffusion
operators.

Method CE TV LEC ED-HNN [20] 0.0132 $\pm$ 0.0028 0.0394 $\pm$ 0.0011 0.2057
$\pm$ 0.0004 WHATsNet [12] 0.0065 $\pm$ 0.0019 0.0380 $\pm$ 0.0007 0.2056
$\pm$ 0.0014 CoNHD (ADMM) 0.0012 $\pm$ 0.0001 0.0293 $\pm$ 0.0000 0.0532 $\pm$
0.0031 CoNHD (GD) 0.0011 $\pm$ 0.0003 0.0292 $\pm$ 0.0001 0.0561 $\pm$ 0.0056

Results. The results in terms of Mean Absolute Error (MAE) are reported in
Table 3. All methods demonstrate superior performance in approximating the
invariant CE operator. Conversely, approximating the equivariant and non-
differentiable operators, TV and LEC, are more challenging. The proposed
method CoNHD can achieve the lowest MAE results compared to the baseline
methods in all settings. While the ADMM-based implementation is theoretically
more suitable for approximating non-differentiable diffusion operators, it
demonstrates minimal performance differences compared to the GD-based
implementation in practice.

####  5.3 Ablation Study

Table 4: Effectiveness of the equivariance in two diffusion operators $\phi$
and $\varphi$. ✓ and ✗ indicate whether the corresponding operator is
equivariant or invariant, respectively.

Email-Enron Email-Eu Method $\phi$ $\varphi$ Micro-F1 Macro-F1 Micro-F1
Macro-F1 CoNHD (UNP) ✗ ✗ 0.827 $\pm$ 0.000 0.769 $\pm$ 0.004 0.673 $\pm$ 0.000
0.645 $\pm$ 0.001 ✗ ✓ 0.876 $\pm$ 0.001 0.817 $\pm$ 0.006 0.698 $\pm$ 0.001
0.677 $\pm$ 0.002 ✓ ✗ 0.903 $\pm$ 0.001 0.855 $\pm$ 0.004 0.707 $\pm$ 0.000
0.688 $\pm$ 0.002 ✓ ✓ 0.905 $\pm$ 0.001 0.858 $\pm$ 0.004 0.708 $\pm$ 0.001
0.689 $\pm$ 0.001 CoNHD (ISAB) ✗ ✗ 0.829 $\pm$ 0.001 0.765 $\pm$ 0.007 0.673
$\pm$ 0.001 0.647 $\pm$ 0.002 ✗ ✓ 0.878 $\pm$ 0.001 0.823 $\pm$ 0.005 0.698
$\pm$ 0.001 0.678 $\pm$ 0.003 ✓ ✗ 0.910 $\pm$ 0.001 0.870 $\pm$ 0.003 0.707
$\pm$ 0.001 0.689 $\pm$ 0.001 ✓ ✓ 0.911 $\pm$ 0.001 0.871 $\pm$ 0.002 0.709
$\pm$ 0.001 0.690 $\pm$ 0.002

One critical design choice in the proposed CoNHD method is the use of
equivariant instead of invariant operators, which enable the modeling of
within-edge and within-node interactions as multi-input multi-output
functions. To investigate the effectiveness of this choice, we replace the
within-edge diffusion operator $\phi$ and the within-node diffusion operator
$\varphi$ with invariant diffusion operators. We implement the invariant
operator using the same architecture as the equivariant operator but with mean
aggregation applied to the final outputs, which generates the same output for
different node-hyperedge pairs. The mean aggregation is widely used in most
message passing-based HGNNs [18]. We conduct experiments on Email-Enron and
Email-Eu, the two datasets with the largest improvements in the ENC
experiments.

As shown in Table 4, CoNHD with two equivariant operators achieves the highest
performance, exhibiting significant improvements compared to the variant with
two invariant operators. Furthermore, variants with just one equivariant
operator still outperform the fully invariant model. This suggests that
equivariance benefits the modeling of both within-edge and within-node
interactions. We also notice that the performance gap between the full
equivariant model and the variant with only the equivariant within-edge
operator $\phi$ is not significant. This might imply that within-edge
interactions provide the most information for predicting the edge-dependent
node labels.

###  6 Conclusion

In this paper, we develop CoNHD, a novel HGNN based on hypergraph diffusion.
CoNHD explicitly models within-edge and within-node interactions among co-
representations as multi-input multi-output functions, which can effectively
address the ENC problem compared to message passing-based HGNNs. Our
experiments demonstrate: (1) CoNHD achieves best performance on six real-world
ENC datasets without sacrificing efficiency. (2) CoNHD can effectively
approximate the co-representation hypergraph diffusion process with common
diffusion operators. (3) As a critical design for implementing multi-output
functions, the equivariance property of two diffusion operators is essential
for performance improvements. We believe this work is a good exploration of
novel HGNN architectures that go beyond the dominant two-stage message passing
framework.

### References

  * Milo et al. [2002] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon.  Network motifs: simple building blocks of complex networks.  _Science_ , 2002.
  * Battiston et al. [2020] Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri.  Networks beyond pairwise interactions: Structure and dynamics.  _Physics Reports_ , 2020.
  * Lambiotte et al. [2019] Renaud Lambiotte, Martin Rosvall, and Ingo Scholtes.  From networks to optimal higher-order models of complex systems.  _Nature Physics_ , 2019.
  * Zhang et al. [2023] Yuanzhao Zhang, Maxime Lucas, and Federico Battiston.  Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes.  _Nature Communications_ , 2023.
  * Berge [1984] Claude Berge.  _Hypergraphs: combinatorics of finite sets_.  Elsevier, 1984.
  * Bretto [2013] Alain Bretto.  _Hypergraph theory_.  Springer, 2013.
  * Gao et al. [2020] Yue Gao, Zizhao Zhang, Haojie Lin, Xibin Zhao, Shaoyi Du, and Changqing Zou.  Hypergraph learning: Methods and practices.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2020.
  * Antelmi et al. [2023] Alessia Antelmi, Gennaro Cordasco, Mirko Polato, Vittorio Scarano, Carmine Spagnuolo, and Dingqi Yang.  A survey on hypergraph representation learning.  _ACM Computing Surveys_ , 2023.
  * Tu et al. [2018] Ke Tu, Peng Cui, Xiao Wang, Fei Wang, and Wenwu Zhu.  Structural deep embedding for hyper-networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2018.
  * Zhang et al. [2020] Ruochi Zhang, Yuesong Zou, and Jian Ma.  Hyper-sagnn: a self-attention based graph neural network for hypergraphs.  In _International Conference on Learning Representations_ , 2020.
  * Jo et al. [2021] Jaehyeong Jo, Jinheon Baek, Seul Lee, Dongki Kim, Minki Kang, and Sung Ju Hwang.  Edge representation learning with hypergraphs.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Choe et al. [2023] Minyoung Choe, Sunwoo Kim, Jaemin Yoo, and Kijung Shin.  Classification of edge-dependent labels of nodes in hypergraphs.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2023.
  * Li et al. [2018] Jianbo Li, Jingrui He, and Yada Zhu.  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_, 2018.
  * Chitra and Raphael [2019] Uthsav Chitra and Benjamin Raphael.  Random walks on hypergraphs with edge-dependent vertex weights.  In _International Conference on Machine Learning_ , 2019.
  * Hayashi et al. [2020] 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 Information & Knowledge Management_, 2020.
  * Lee et al. [2022] Geon Lee, Minyoung Choe, and Kijung Shin.  Hashnwalk: Hash and random walk based anomaly detection in hyperedge streams.  In _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence_ , 2022.
  * Arya et al. [2020] Devanshu Arya, Deepak K Gupta, Stevan Rudinac, and Marcel Worring.  Hypersage: Generalizing inductive representation learning on hypergraphs.  _arXiv preprint arXiv:2010.04558_ , 2020.
  * Huang and Yang [2021] Jing Huang and Jie Yang.  Unignn: a unified framework for graph and hypergraph neural networks.  In _Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence_ , 2021.
  * Aponte et al. [2022] Ryan Aponte, Ryan A Rossi, Shunan Guo, Jane Hoffswell, Nedim Lipka, Chang Xiao, Gromit Chan, Eunyee Koh, and Nesreen Ahmed.  A hypergraph neural network framework for learning hyperedge-dependent node embeddings.  _arXiv preprint arXiv:2212.14077_ , 2022.
  * Wang et al. [2023a] Peihao Wang, Shenghao Yang, Yunyu Liu, Zhangyang Wang, and Pan Li.  Equivariant hypergraph diffusion neural operators.  In _International Conference on Learning Representations_ , 2023a.
  * Pei et al. [2024] Xiaobing Pei, Rongping Ye, Haoran Yang, and Ruiqi Wang.  Hyperedge interaction-aware hypergraph neural network.  _arXiv preprint arXiv:2401.15587_ , 2024.
  * Liu et al. [2021] Meng Liu, Nate Veldt, Haoyu Song, Pan Li, and David F Gleich.  Strongly local hypergraph diffusions for clustering and semi-supervised learning.  In _Proceedings of the Web Conference_ , 2021.
  * Fountoulakis et al. [2021] Kimon Fountoulakis, Pan Li, and Shenghao Yang.  Local hyper-flow diffusion.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Tudisco et al. [2021a] Francesco Tudisco, Austin R Benson, and Konstantin Prokopchik.  Nonlinear higher-order label spreading.  In _Proceedings of the Web Conference_ , 2021a.
  * Takai et al. [2020] Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, and Yuichi Yoshida.  Hypergraph clustering based on pagerank.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020.
  * Kondor and Lafferty [2002] Risi Imre Kondor and John Lafferty.  Diffusion kernels on graphs and other discrete structures.  In _International Conference on Machine Learning_ , 2002.
  * Chamberlain et al. [2021] Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi.  Grand: Graph neural diffusion.  In _International Conference on Machine Learning_ , 2021.
  * Kipf and Welling [2017] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_ , 2017.
  * Wu et al. [2020] 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_ , 2020.
  * Wu et al. [2022] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui.  Graph neural networks in recommender systems: a survey.  _ACM Computing Surveys_ , 2022.
  * Kim et al. [2024] Sunwoo Kim, Soo Yong Lee, Yue Gao, Alessia Antelmi, Mirko Polato, and Kijung Shin.  A survey on hypergraph neural networks: an in-depth and step-by-step guide.  _arXiv preprint arXiv:2404.01039_ , 2024.
  * Duta et al. [2023] Iulia Duta, Giulia Cassarà, Fabrizio Silvestri, and Pietro Lio.  Sheaf hypergraph networks.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Yan et al. [2024] Jielong Yan, Yifan Feng, Shihui Ying, and Yue Gao.  Hypergraph dynamic system.  In _International Conference on Learning Representations_ , 2024.
  * Feng et al. [2019] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao.  Hypergraph neural networks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2019.
  * Gao et al. [2022] Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji.  Hgnn+: General hypergraph neural networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * Bai et al. [2021] Song Bai, Feihu Zhang, and Philip HS Torr.  Hypergraph convolution and hypergraph attention.  _Pattern Recognition_ , 2021.
  * Yadati et al. [2019] Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar.  Hypergcn: A new method for training graph convolutional networks on hypergraphs.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Dong et al. [2020] Yihe Dong, Will Sawin, and Yoshua Bengio.  Hnhn: Hypergraph networks with hyperedge neurons.  In _ICML Graph Representation Learning and Beyond Workshop_ , 2020.
  * Ding et al. [2020] Kaize Ding, Jianling Wang, Jundong Li, Dingcheng Li, and Huan Liu.  Be more with less: Hypergraph attention networks for inductive text classification.  In _Proceedings of the Conference on Empirical Methods in Natural Language Processing_ , 2020.
  * Chien et al. [2022] Eli Chien, Chao Pan, Jianhao Peng, and Olgica Milenkovic.  You are allset: A multiset function framework for hypergraph neural networks.  In _International Conference on Learning Representations_ , 2022.
  * Telyatnikov et al. [2023] Lev Telyatnikov, Maria Sofia Bucarelli, Guillermo Bernardez, Olga Zaghen, Simone Scardapane, and Pietro Lio.  Hypergraph neural networks through the lens of message passing: a common perspective to homophily and architecture design.  _arXiv preprint arXiv:2310.07684_ , 2023.
  * Liu et al. [2024] Zexi Liu, Bohan Tang, Ziyuan Ye, Xiaowen Dong, Siheng Chen, and Yanfeng Wang.  Hypergraph transformer for semi-supervised classification.  In _IEEE International Conference on Acoustics, Speech and Signal Processing_ , 2024.
  * Zou et al. [2024] Minhao Zou, Zhongxue Gan, Yutong Wang, Junheng Zhang, Dongyan Sui, Chun Guan, and Siyang Leng.  Unig-encoder: A universal feature encoder for graph and hypergraph node classification.  _Pattern Recognition_ , 2024.
  * Benko et al. [2024] Tatyana Benko, Martin Buck, Ilya Amburg, Stephen J Young, and Sinan G Aksoy.  Hypermagnet: A magnetic laplacian based hypergraph neural network.  _arXiv preprint arXiv:2402.09676_ , 2024.
  * Yi and Park [2020] Jaehyuk Yi and Jinkyoo Park.  Hypergraph convolutional recurrent neural network.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020.
  * Shang and Chen [2024] Zongjiang Shang and Ling Chen.  Mshyper: Multi-scale hypergraph transformer for long-range time series forecasting.  _arXiv preprint arXiv:2401.09261_ , 2024.
  * Chen et al. [2023] Can Chen, Chen Liao, and Yang-Yu Liu.  Teasing out missing reactions in genome-scale metabolic networks through hypergraph learning.  _Nature Communications_ , 2023.
  * Liu et al. [2022] Xuan Liu, Congzhi Song, Shichao Liu, Menglu Li, Xionghui Zhou, and Wen Zhang.  Multi-way relation-enhanced hypergraph representation learning for anti-cancer drug synergy prediction.  _Bioinformatics_ , 2022.
  * Gleich and Mahoney [2015] David F Gleich and Michael W Mahoney.  Using local spectral methods to robustify graph-based learning algorithms.  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2015.
  * Zhu et al. [2003] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty.  Semi-supervised learning using gaussian fields and harmonic functions.  In _International Conference on Machine learning_ , 2003.
  * Zhou et al. [2003] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf.  Learning with local and global consistency.  In _Advances in Neural Information Processing Systems_ , 2003.
  * Zhou et al. [2007] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf.  Learning with hypergraphs: Clustering, classification, and embedding.  In _Advances in Neural Information Processing Systems_ , 2007.
  * Hein et al. [2013] Matthias Hein, Simon Setzer, Leonardo Jost, and Syama Sundar Rangapuram.  The total variation on hypergraphs-learning on hypergraphs revisited.  In _Advances in Neural Information Processing Systems_ , 2013.
  * Jegelka et al. [2013] Stefanie Jegelka, Francis Bach, and Suvrit Sra.  Reflection methods for user-friendly submodular optimization.  In _Advances in Neural Information Processing Systems_ , 2013.
  * Tudisco et al. [2021b] Francesco Tudisco, Konstantin Prokopchik, and Austin R Benson.  A nonlinear diffusion method for semi-supervised learning on hypergraphs.  _arXiv preprint arXiv:2103.14867_ , 2021b.
  * Zhang et al. [2017] 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_ , 2017.
  * Li et al. [2020] Pan Li, Niao He, and Olgica Milenkovic.  Quadratic decomposable submodular function minimization: Theory and practice.  _The Journal of Machine Learning Research_ , 2020.
  * Li and Milenkovic [2017] Pan Li and Olgica Milenkovic.  Inhomogeneous hypergraph clustering with applications.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Zhang et al. [2019] Songyang Zhang, Zhi Ding, and Shuguang Cui.  Introducing hypergraph signal processing: Theoretical foundation and practical applications.  _IEEE Internet of Things Journal_ , 2019.
  * Schaub et al. [2021] Michael T Schaub, Yu Zhu, Jean-Baptiste Seby, T Mitchell Roddenberry, and Santiago Segarra.  Signal processing on higher-order networks: Livin’on the edge… and beyond.  _Signal Processing_ , 2021.
  * Prokopchik et al. [2022] Konstantin Prokopchik, Austin R Benson, and Francesco Tudisco.  Nonlinear feature diffusion on hypergraphs.  In _International Conference on Machine Learning_ , 2022.
  * Wang et al. [2023b] Yuxin Wang, Quan Gan, Xipeng Qiu, Xuanjing Huang, and David Wipf.  From hypergraph energy functions to hypergraph neural networks.  In _International Conference on Machine Learning_ , 2023b.
  * Boyd et al. [2011] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Foundations and Trends® in Machine learning_ , 2011.
  * Parikh et al. [2014] Neal Parikh, Stephen Boyd, et al.  Proximal algorithms.  _Foundations and trends® in Optimization_ , 2014.
  * Shahbazi et al. [2023] Ashkan Shahbazi, Abihith Kothapalli, Xinran Liu, Robert Sheng, and Soheil Kolouri.  Equivariant vs. invariant layers: A comparison of backbone and pooling for point cloud classification.  _arXiv preprint arXiv:2306.05553_ , 2023.
  * Zaheer et al. [2017] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Qi et al. [2017] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017.
  * Segol and Lipman [2020] Nimrod Segol and Yaron Lipman.  On universal equivariant set networks.  In _International Conference on Learning Representations_ , 2020.
  * Lee et al. [2019] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh.  Set transformer: A framework for attention-based permutation-invariant neural networks.  In _International Conference on Machine Learning_ , 2019.
  * Kim et al. [2021] Jinwoo Kim, Saeyoon Oh, and Seunghoon Hong.  Transformers generalize deepsets and can be extended to graphs & hypergraphs.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Kim et al. [2022] Jinwoo Kim, Saeyoon Oh, Sungjun Cho, and Seunghoon Hong.  Equivariant hypergraph neural networks.  In _European Conference on Computer Vision_ , 2022.
  * Hwang et al. [2021] Hyunjin Hwang, Seungwoo Lee, and Kijung Shin.  Hyfer: A framework for making hypergraph learning easy, scalable and benchmarkable.  In _WWW Workshop on Graph Learning Benchmarks_ , 2021.
  * Fowler [2006] James H Fowler.  Legislative cosponsorship networks in the us house and senate.  _Social networks_ , 2006.
  * Yuan et al. [2022] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji.  Explainability in graph neural networks: A taxonomic survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * Pope et al. [2019] Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann.  Explainability methods for graph convolutional neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019.
  * Jang et al. [2023] Hyosoon Jang, Seonghyun Park, Sangwoo Mo, and Sungsoo Ahn.  Diffusion probabilistic models for structured node classification.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Yang et al. [2022] Chaoqi Yang, Ruijie Wang, Shuochao Yao, and Tarek Abdelzaher.  Semi-supervised hypergraph node classification on hypergraph line expansion.  In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_, 2022.
  * Yeniay [2005] Özgür Yeniay.  Penalty function methods for constrained optimization with genetic algorithms.  _Mathematical and Computational Applications_ , 2005.
  * Paranjape et al. [2017] Ashwin Paranjape, Austin R Benson, and Jure Leskovec.  Motifs in temporal networks.  In _Proceedings of the tenth ACM international conference on web search and data mining_ , 2017.
  * Swati et al. [2017] Agarwal Swati, S Ashish, M Nitish, K Rohan, and C Denzil.  Dblp records and entries for key computer science conferences, 2017.

##  Appendix

###  Appendix A Broader Impacts and Limitations

Broader Impacts. This paper proposes a novel and effective hypergraph neural
network architecture based on hypergraph diffusion, which can effectively
address the edge-dependent node classification problem. As shown in previous
research [12], this problem is important and useful for a wide range of real-
world applications, including product-return prediction [13], anomaly
detection [16], ranking [14], and clustering [15]. The proposed method CoNHD
demonstrates theoretical advantages compared to existing message passing-based
solutions, and achieves significant improvements on real-world ENC datasets in
our experiments. We believe this work can make contributions to these
practical applications and bring positive social impacts.

This work is foundational research on hypergraph learning methods and is not
tied to particular practical applications. Due to the improved expressiveness,
one potential negative impact of this work is overfitting to biases present in
the training data. To mitigate this risk, we recommend combining explainable
graph techniques [74, 75] with the CoNHD method, which can help identify the
sources of bias in the model and improve the fairness of the model decisions.

Limitations & Future Work. One limitation lies in the ISAB operator, which,
unlike the UNP operator, lacks the universal property for approximating any
set-equivariant functions, despite its superior performance in our
experiments. Future investigations could explore more different universal set-
equivariant neural networks [68] in the proposed CoNHD method. Another
limitation is that CoNHD only leverages initial features without incorporating
the observed labels in the diffusion process. The observed edge-dependent
labels of a node can help predict its unobserved edge-dependent labels. For
example, an author frequently appears as the last author in many papers is
more likely to be the last author in other papers as well. It is good to
consider the label dependencies and extend this method for structured
classification [76].

###  Appendix B Comparison to Message Passing-based HGNNs

In this section, we theoretically compare the proposed CoNHD model to message
passing-based HGNNs, which can cover most existing hypergraph neural networks
[18, 40]. We first show that CoNHD is expressive enough to represent any HGNNs
following the message passing framework defined in Eq. 1-3. Subsequently, we
discuss how CoNHD effectively addresses the three limitations of message
passing as discussed in the introduction. We provide more discussion about
some other HGNN models that do not follow the message passing framework in
Appendix C.

####  B.1 Expressiveness of CoNHD

To demonstrate the expressiveness of CoNHD, we compare it with the message
passing framework defined in Eq. 1-3, which can cover most existing hypergraph
neural networks [18, 40].

To include more HGNN models in our comparison, we first show that some
advanced methods, apart from many traditional message passing-based HGNNs
discussed in [18, 40], can also be represented by the message passing
framework. It is argued that the traditional message passing framework
overlooks the importance of edge-dependent node information and passes the
same node representation to different hyperedges [19]. Some advanced methods
attempt to extract edge-dependent node representations before aggregation [20,
12]. Proposition 3 shows that these advanced methods with edge-dependent node
information are also special cases of the message passing framework defined in
Eq. 1-3.

######  Proposition 3.

ED-HNN [20], ED-HNNII [20], and WHATsNet [12] are special cases of the message
passing framework defined in Eq. 1-3.

The message passing framework can only generate separate representations for
nodes and hyperedges. Following [12], we regard the concatenation of node and
hyperedge representations as the co-representation, _i.e._ ,
$\boldsymbol{h}^{(t)}_{v,e}=[\boldsymbol{x}^{(t)}_{v},\boldsymbol{z}^{(t)}_{e}]$,
which can be used to predict edge-dependent node labels.

######  Proposition 4.

With the same co-representation dimension, CoNHD is expressive enough to
represent the message passing framework, while the opposite is not true.

Proposition 4 demonstrates that CoNHD is more expressive than all methods
following the message passing framework. Specifically, CoNHD models within-
edge and within-node interactions as multi-input multi-output functions
through two equivariant diffusion operators, which are more expressive than
the invariant aggregation operators in the message passing framework.

Notably, despite the increased expressiveness, CoNHD still maintains a similar
theoretical complexity compared to other HGNNs within the message passing
framework such as WHATsNet [12]. We leave the detailed analysis to Appendix
F.1.

####  B.2 Addressing the Limitations of Message Passing

Message passing models both within-edge and within-node interactions as multi-
input single-output functions, which brings three limitations as discussed in
the introduction. We show that CoNHD can effectively address these three
limitations.

  * •

Non-adaptive representation size.

In message passing, messages from numerous hyperedges/nodes are aggregated to
a fixed-size node/edge representation vector. As indicated in [19], this can
cause potential information loss for large-degree nodes or hyperedges. A
possible solution is to assign a high-dimensional representation for each node
or hyperedge. However, the high-dimensional representations increase the
computational costs and can lead to training difficulty.

In CoNHD, the co-representations are related to node-hyperedge pairs. For
larger-degree nodes or hyperedges, they are contained by more node-hyperedge
pairs and therefore are associated with more co-representations. The number of
co-representations adaptively scales with node or hyperedge degrees, which can
prevent potential information loss.

  * •

Node/Edge agnostic messages.

In message passing, since the aggregated node representation loses edge-
dependent information, the node can only pass the same message to different
hyperedges. However, different hyperedges may focus on different properties of
the node and should receive different messages. While some methods attempt to
extract edge-dependent information from one node representation [19, 20, 12],
this extraction process increases the learning difficulty.

In CoNHD, the co-representations inherently preserve specific information for
each node-hyperedge pair, which can serve as the edge-dependent node
representation or node-dependent edge representation. Without the aggregation
process, CoNHD avoids mixing different information into a single node or edge
representations, and thus obviates the necessity of extracting edge-/node-
dependent information, which can reduce the learning difficulty compared to
those edge-dependent message passing methods.

  * •

Insufficient interactions among nodes or hyperedges.

In message passing, the single-output design cannot include direct nodes-to-
nodes or edges-to-edges interactions, as this requires multiple outputs for
different elements. These interactions are shown to be critical for hypergraph
learning [21].

In CoNHD, the co-representations include both node and hyperedge information.
The interactions among co-representations naturally include not only
interactions between nodes and hyperedges, but also direct nodes-to-nodes and
edges-to-edges interactions.

Two critical designs of CoNHD are: (1) introducing the concept of co-
representations, and (2) modeling interactions using equivariant diffusion
operators. These two designs enable the modeling of both within-edge and
within-node interactions as multi-input multi-output functions, which are more
expressive than the single-output aggregation functions and can effectively
address the three limitations in message passing.

###  Appendix C Discussion on Other Hypergraph Neural Networks

LEGCN [77] and MultiSetMixer [41] are two approaches that do not follow the
message passing framework defined in Eq. 1-3 and can explicitly generate edge-
dependent node representations, which are similar to the concept of co-
representations in the proposed CoNHD model. Unfortunately, LEGCN transforms
the hypergraph structure into a traditional graph structure, which loses some
higher-order group information. Instead, MultiSetMixer preserves the
hypergraph structure but still models it as a two-stage message passing
process, where messages from nodes are aggregated to a single hyperedge
representation and then back to nodes. Both of these two methods model within-
edge and within-node interactions as multi-input single-output functions,
which can only generate the same output for different node-hyperedge pairs and
therefore limits their expressiveness.

LEGCN.  LEGCN converts a hypergraph into a traditional graph using line
expansion, and utilizes graph convolution [28] to learn representations of the
new nodes on the expanded graph. The $(t+1)$-th layer of LEGCN (without
normalization) can be formulated as:

$\begin{gathered}\boldsymbol{m}^{(t+1)}_{e}=\sum_{v_{i}\in
e}\boldsymbol{h}^{(t)}_{v_{i},e},\,\boldsymbol{m}^{\prime(t+1)}_{v}=\sum_{e_{j}\in\mathcal{E}_{v}}\boldsymbol{h}^{(t)}_{v,e_{j}},\\\
\boldsymbol{h}^{(t+1)}_{v,e}=\sigma(\lambda\boldsymbol{m}^{(t+1)}_{e}+\gamma\boldsymbol{m}^{\prime(t+1)}_{v})\boldsymbol{W}^{(t)},\end{gathered}$

where $\sigma(\cdot)$ denotes the non-linear activation function.
$\boldsymbol{m}^{(t)}_{e}$ and $\boldsymbol{m}^{(t)}_{v}$ are the within-edge
information and the within-node information, respectively.

Compared to CoNHD, LEGCN exhibits three main limitations. (1) Lack of
differentiation between within-edge and within-node interactions. In a line
expansion graph, the new vertices (node-hyperedge pairs) associated with the
same hyperedge or the same node are connected by homogeneous edges, which
overlooks the difference between these two kinds of relations. Although LEGCN
utilizes different scalar weights to balance within-edge or within-node
messages, this is still not expressive enough compared to two different neural
diffusion operators in CoNHD. (2) Node/Edge agnostic messages. LEGCN still
follows the single-output setting which only generates one shared within-edge
message $\boldsymbol{m}^{(t)}_{e}$ and one shared within-node message
$\boldsymbol{m}^{(t)}_{v}$ using sum pooling, instead of diverse messages for
different node-hyperedge pairs. (3) High computational complexity. The
motivation for LEGCN is to reduce the hypergraph structure to a graph
structure. This reduction loses the higher-order group information and
requires additional computation for different node-hyperedge pairs. For
example, the learning for representations of node-hyperedge pairs
$(v_{1},e_{1})$ and $(v_{1},e_{2})$ are calculated separately, although they
have the same within-node messages $\boldsymbol{m}^{\prime(t+1)}_{v_{1}}$
which only needs to be computed once. In contrast, our proposed CoNHD method
generates all diffusing information within the same node $v_{1}$ together
using the node diffusion operator with linear complexity.

MultiSetMixer.  MultiSetMixer replaces each node representation in the message
passing framework with several edge-dependent node representations. However,
it still follows the message passing framework and aggregates different node
representations into a single edge representation. This models the within-edge
interactions as multi-input single-output functions. The $(t+1)$-th layer of
MultiSetMixer can be formulated as:

$\begin{gathered}\boldsymbol{m}^{(t+1)}_{e}=\frac{1}{d_{e}}\sum_{v_{i}\in
e}\boldsymbol{h}^{(t)}_{v_{i},e}+\textsc{Mlp}(\textsc{Ln}(\frac{1}{d_{e}}\sum_{v_{i}\in
e}\boldsymbol{h}^{(t)}_{v_{i},e})),\\\
\boldsymbol{h}^{(t+1)}_{v,e}=\boldsymbol{h}^{(t)}_{v,e}+\textsc{Mlp}(\textsc{Ln}(\boldsymbol{h}^{(t)}_{v,e}))+\boldsymbol{m}^{(t+1)}_{e}.\end{gathered}$

MultiSetMixer also generates one shared within-edge message
$\boldsymbol{m}^{(t)}_{e}$, which loses specific messages for different node-
hyperedge pair. This formulation still suffers from the three main limitations
of the message passing framework. Besides, it does not incorporate within-node
interactions, which cannot model the relationships among different
representations associated with the same node.

###  Appendix D Derivations and Proofs

####  D.1 Derivation of Eq. 7-9

We use the ADMM method [63] to solve the optimization problem in Eq. 5 with
non-differentiable functions. We first introduce an auxiliary variable
$\boldsymbol{A}_{e}=\boldsymbol{H}_{e}$ for each hyperedge $e$, and an
auxiliary variable $\boldsymbol{B}_{v}=\boldsymbol{H}_{v}$ for each node $v$.
Then the problem in Eq. 5 can be

$\begin{split}\min_{\boldsymbol{\mathcal{H}}}\quad&\sum_{v\in\mathcal{V}}\sum_{e\in\mathcal{E}_{v}}\mathcal{R}_{v,e}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v,e})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{A}_{e})+\gamma\sum_{v\in\mathcal{V}}\Omega_{v}(\boldsymbol{B}_{v}),\\\
\mathrm{s.t.}\quad&\forall
e\in\mathcal{E}:\boldsymbol{A}_{e}=\boldsymbol{H}_{e},\\\ \quad&\forall
v\in\mathcal{V}:\boldsymbol{B}_{v}=\boldsymbol{H}_{v}.\end{split}$

Then the scaled form augmented Lagrangian function can be transformed as:

$\begin{split}L_{\rho}=&\sum_{v\in\mathcal{V}}\sum_{e\in\mathcal{E}_{v}}\mathcal{R}_{v,e}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v,e})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{A}_{e})+\gamma\sum_{v\in\mathcal{V}}\Omega_{v}(\boldsymbol{B}_{v})\\\
&+\sum_{e\in\mathcal{E}}\frac{\rho}{2}\left(\lVert\boldsymbol{A}_{e}-\boldsymbol{H}_{e}+\boldsymbol{P}_{e}\rVert^{2}_{F}-\lVert\boldsymbol{P}_{e}\rVert^{2}_{F}\right)\\\
&+\sum_{v\in\mathcal{V}}\frac{\rho}{2}\left(\lVert\boldsymbol{B}_{v}-\boldsymbol{H}_{v}+\boldsymbol{Q}_{v}\rVert^{2}_{F}-\lVert\boldsymbol{Q}_{v}\rVert^{2}_{F}\right),\end{split}$

where $\boldsymbol{P}_{e}$ and $\boldsymbol{Q}_{v}$ are the scaled dual
variables (with scaling factor $\frac{1}{\rho}$). Then we can use the primal-
dual algorithms in ADMM to find the optimal solutions [63].

The primal steps can be calculated as follows:

$\begin{split}\boldsymbol{A}_{e}^{(t+1)}:=&\operatorname*{arg\,min}_{\boldsymbol{A}_{e}}L_{\rho}\\\
=&\operatorname*{arg\,min}_{\boldsymbol{A}_{e}}\frac{\lambda}{\rho}\Omega_{e}(\boldsymbol{A}_{e})+\frac{1}{2}\lVert\boldsymbol{A}_{e}-\boldsymbol{H}^{(t)}_{e}+\boldsymbol{P}^{(t)}_{e}\rVert_{F}^{2}\\\
=&\mathbf{prox}_{\lambda\Omega_{e}/\rho}(\boldsymbol{H}^{(t)}_{e}-\boldsymbol{P}^{(t)}_{e}),\,\forall
e\in\mathcal{E},\end{split}$
$\begin{split}\boldsymbol{B}_{v}^{(t+1)}:=&\operatorname*{arg\,min}_{\boldsymbol{B}_{v}}L_{\rho}\\\
=&\operatorname*{arg\,min}_{\boldsymbol{B}_{v}}\frac{\gamma}{\rho}\Omega_{v}(\boldsymbol{B}_{v})+\frac{1}{2}\lVert\boldsymbol{B}_{v}-\boldsymbol{H}^{(t)}_{v}+\boldsymbol{Q}^{(t)}_{v}\rVert_{F}^{2}\\\
=&\mathbf{prox}_{\gamma\Omega_{v}/\rho}(\boldsymbol{H}^{(t)}_{v}-\boldsymbol{Q}^{(t)}_{v}),\,\forall
v\in\mathcal{V},\end{split}$
$\begin{split}\boldsymbol{h}_{v,e}^{(t+1)}:=&\operatorname*{arg\,min}_{\boldsymbol{h}_{v,e}}L_{\rho}\\\
=&\operatorname*{arg\,min}_{\boldsymbol{h}_{v,e}}\mathcal{R}_{v,e}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v,e})+\frac{\rho}{2}\lVert\boldsymbol{h}_{v,e}-[\boldsymbol{A}_{e}^{(t+1)}]_{v}-[\boldsymbol{P}_{e}^{(t)}]_{v}\rVert_{2}^{2}\\\
&+\frac{\rho}{2}\lVert\boldsymbol{h}_{v,e}-[\boldsymbol{B}_{v}^{(t+1)}]_{e}-[\boldsymbol{Q}_{v}^{(t)}]_{e}\rVert_{2}^{2}\\\
=&\operatorname*{arg\,min}_{\boldsymbol{h}_{v,e}}\frac{1}{2\rho}\mathcal{R}_{v,e}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v,e})\\\
&+\frac{1}{2}\Big{\lVert}\boldsymbol{h}_{v,e}-\frac{1}{2}\big{(}[\boldsymbol{A}_{e}^{(t+1)}]_{v}+[\boldsymbol{P}_{e}^{(t)}]_{v}+[\boldsymbol{B}_{v}^{(t+1)}]_{e}+[\boldsymbol{Q}_{v}^{(t)}]_{e}\big{)}\Big{\rVert}_{2}^{2}\\\
=&\mathbf{prox}_{\mathcal{R}_{v,e}(\cdot;\boldsymbol{a}_{v,e})/2\rho}\Big{(}\frac{1}{2}\big{(}[\boldsymbol{A}_{e}^{(t+1)}]_{v}+[\boldsymbol{P}_{e}^{(t)}]_{v}+[\boldsymbol{B}_{v}^{(t+1)}]_{e}+[\boldsymbol{Q}_{v}^{(t)}]_{e}\big{)}\Big{)},\,\forall
e\in\mathcal{E}_{v},\,\forall v\in\mathcal{V}.\end{split}$

The dual steps can be calculated as follows:

$\begin{gathered}\boldsymbol{P}_{e}^{(t+1)}:=\boldsymbol{P}_{e}^{(t)}+\boldsymbol{A}_{e}^{(t+1)}-\boldsymbol{H}_{e}^{(t+1)},\,\forall
e\in\mathcal{E},\\\
\boldsymbol{Q}_{v}^{(t+1)}:=\boldsymbol{Q}_{v}^{(t)}+\boldsymbol{B}_{v}^{(t+1)}-\boldsymbol{H}_{v}^{(t+1)},\,\forall
v\in\mathcal{V}.\end{gathered}$

By defining
$\boldsymbol{U}_{e}^{(t+1)}=\boldsymbol{A}_{e}^{(t+1)}+\boldsymbol{P}_{e}^{(t)}$
and
$\boldsymbol{Z}_{v}^{(t+1)}=\boldsymbol{B}_{v}^{(t+1)}+\boldsymbol{Q}_{v}^{(t)}$,
the update process can be simplified as follows:

$\begin{gathered}\boldsymbol{U}_{e}^{(t+1)}=\mathbf{prox}_{\lambda\Omega_{e}/\rho}(2\boldsymbol{H}^{(t)}_{e}-\boldsymbol{U}^{(t)}_{e})+\boldsymbol{U}^{(t)}_{e}-\boldsymbol{H}^{(t)}_{e},\,\forall
e\in\mathcal{E},\\\
\boldsymbol{Z}_{v}^{(t+1)}=\mathbf{prox}_{\gamma\Omega_{v}/\rho}(2\boldsymbol{H}^{(t)}_{v}-\boldsymbol{Z}^{(t)}_{v})+\boldsymbol{Z}^{(t)}_{v}-\boldsymbol{H}^{(t)}_{v},\,\forall
v\in\mathcal{V},\\\
\boldsymbol{h}_{v,e}^{(t+1)}=\mathbf{prox}_{\mathcal{R}_{v,e}(\cdot;\boldsymbol{a}_{v,e})/2\rho}\Big{(}\frac{1}{2}\big{(}[\boldsymbol{U}^{(t+1)}_{e}]_{v}+[\boldsymbol{Z}_{v}^{(t+1)}]_{e}\big{)}\Big{)},\,\forall
e\in\mathcal{E}_{v},\,\forall v\in\mathcal{V}.\end{gathered}$

####  D.2 Proof of Proposition 1

######  Proposition 1 (Wang et al. [20]).

With permutation invariant structural regularization functions, the diffusion
operators are permutation equivariant.

###### Proof.

Proved in Proposition 2 in [20]. ∎

####  D.3 Proof of Proposition 2

######  Proposition 2.

The node-representation hypergraph diffusion is a special case of the co-
representation hypergraph diffusion.

###### Proof.

We first rewrite the node-representation hypergraph diffusion defined in Eq. 4
as a constraint optimization problem, then show that it is a special case of
co-representation hypergraph diffusion defined in Eq. 5.

For each $v\in\mathcal{V}$, we introduce a set of new variable
$\\{\boldsymbol{h}_{v,e_{i}}|e_{i}\in\mathcal{E}_{v}\\}$, satisfying
$\boldsymbol{h}_{v,e_{1}}=\boldsymbol{x}_{v}$, and
$\boldsymbol{h}_{v,e_{i}}=\boldsymbol{h}_{v,e_{j}}$ for any
$e_{i},e_{j}\in\mathcal{E}_{v}$. Then the objective function in Eq. 4 becomes:

$\begin{split}\sum_{v\in\mathcal{V}}\mathcal{R}_{v}(\boldsymbol{x}_{v};\boldsymbol{a}_{v})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{X}_{e})=&\sum_{v\in\mathcal{V}}\sum_{e\in\mathcal{E}_{v}}\frac{1}{d_{v}}\mathcal{R}_{v}(\boldsymbol{x}_{v};\boldsymbol{a}_{v})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{X}_{e})\\\
=&\sum_{v\in\mathcal{V}}\sum_{e\in\mathcal{E}_{v}}\frac{1}{d_{v}}\mathcal{R}_{v}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{H}_{e}),\end{split}$

The original problem in Eq. 4 can be reformulated as a constraint optimization
problem:

$\begin{split}\operatorname*{arg\,min}_{\boldsymbol{\mathcal{H}}}\quad&\sum_{v\in\mathcal{V}}\sum_{e\in\mathcal{E}_{v}}\frac{1}{d_{v}}\mathcal{R}_{v}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{H}_{e}),\\\
\mathrm{s.t.}\quad&\forall v\in\mathcal{V},\forall
e_{i},e_{j}\in\mathcal{E}_{v}:\,\boldsymbol{h}_{v,e_{i}}=\boldsymbol{h}_{v,e_{j}},\end{split}$
(A1)

where the optimal solutions satisfy
$\boldsymbol{h}^{*}_{v,e}=\boldsymbol{x}^{*}_{v}$.

We now show that this constraint optimization is a special case of co-
representation hypergraph diffusion. We can set
$\mathcal{R}_{v,e}(\cdot;\boldsymbol{a}_{v,e})=\frac{1}{d_{v}}\mathcal{R}_{v}(\cdot;\boldsymbol{a}_{v})$,
and use the CE regularization functions [52] for the node regularization
functions in Eq. 5, _i.e._ ,
$\Omega_{\mathrm{CE}}(\boldsymbol{H}_{v}):=\sum_{e_{i},e_{j}\in\mathcal{E}_{v}}\lVert\boldsymbol{h}_{v,e_{i}}-\boldsymbol{h}_{v,e_{j}}\rVert_{2}^{2}$.
Then Eq. 5 can be reformulated as follows:

$\operatorname*{arg\,min}_{\boldsymbol{\mathcal{H}}}\sum_{v\in\mathcal{V}}\sum_{e\in\mathcal{E}_{v}}\frac{1}{d_{v}}\mathcal{R}_{v}(\boldsymbol{h}_{v,e};\boldsymbol{a}_{v})+\lambda\sum_{e\in\mathcal{E}}\Omega_{e}(\boldsymbol{H}_{e})+\gamma\sum_{v\in\mathcal{V}}\Omega_{\mathrm{CE}}(\boldsymbol{H}_{v}).$
(A2)

The node regularization term in A2 is exactly the exterior penalty function
[78] for the given equality constraints in Eq. A1. Thus when
$\gamma\rightarrow\infty$, Eq. A2 yields the same optimal solutions as Eq. A1.
∎

####  D.4 Proof of Proposition 3

######  Proposition 3.

ED-HNN [20], ED-HNNII [20], and WHATsNet [12] are special cases of the message
passing framework defined in Eq. 1-3.

###### Proof.

For ED-HNN [20], each layer can be represented as:

$\begin{gathered}\boldsymbol{z}^{(t+1)}_{e}=f_{\mathcal{V}\rightarrow\mathcal{E}}(\boldsymbol{X}^{(t)}_{e};\boldsymbol{z}^{(t)}_{e})=\frac{1}{d_{e}}\sum_{u\in
e}\textsc{Mlp}(\boldsymbol{x}^{(t)}_{u}),\\\
\tilde{\boldsymbol{x}}^{(t+1)}_{v}=f_{\mathcal{E}\rightarrow\mathcal{V}}(\boldsymbol{Z}^{(t+1)}_{v};\boldsymbol{x}^{(t)}_{v})=\frac{1}{d_{v}}\sum_{e:v\in
e}\textsc{Mlp}([\boldsymbol{z}^{(t+1)}_{e},\boldsymbol{x}^{(t)}_{v}]),\\\
\boldsymbol{x}^{(t+1)}_{v}=f_{\mathrm{skip}}(\tilde{\boldsymbol{x}}^{(t+1)}_{v},\boldsymbol{x}^{(t)}_{v},\boldsymbol{x}^{(0)}_{v})=\textsc{Mlp}(\tilde{\boldsymbol{x}}^{(t+1)}_{v},\boldsymbol{x}^{(t)}_{v},\boldsymbol{x}^{(0)}_{v}),\end{gathered}$

where $[\ldots]$ denotes concatenation in the last dimension. The degree of
hyperedge $e$ and node $v$, denoted as $d_{e}$ and $d_{v}$, can be obtained
from the number of rows in $\boldsymbol{X}^{(t)}_{e}$ and
$\boldsymbol{Z}^{(t+1)}_{v}$. ED-HNN ignores the hyperedge representation
$\boldsymbol{z}^{(t)}_{e}$ in the first aggregation function
$f_{\mathcal{V}\rightarrow\mathcal{E}}$.

For ED-HNNII, the only difference compared to ED-HNN is the function
$f_{\mathcal{V}\rightarrow\mathcal{E}}$, which concatenates the edge and node
features to generate node-dependent edge representation. The function
$f_{\mathcal{V}\rightarrow\mathcal{E}}$ can be represented as:

$\boldsymbol{z}^{(t+1)}_{e}=f_{\mathcal{V}\rightarrow\mathcal{E}}(\boldsymbol{X}^{(t)}_{e};\boldsymbol{z}^{(t)}_{e})=\frac{1}{d_{e}}\sum_{u\in
e}\textsc{Mlp}([\boldsymbol{x}^{(t)}_{u},\boldsymbol{z}^{(t)}_{e}]).\\\ $

For WHATsNet, we ignore the positional encoding part which can be combined
with the input, and focus on the HGNN architecture. Each layer of WHATsNet can
then be represented as:

$\begin{gathered}\boldsymbol{z}^{(t+1)}_{e}=f_{\mathcal{V}\rightarrow\mathcal{E}}(\boldsymbol{X}^{(t)}_{e};\boldsymbol{z}^{(t)}_{e})=\textsc{Mab}(\boldsymbol{z}^{(t)\top}_{e},\textsc{Isab}(\boldsymbol{X}^{(t)}_{e}))^{\top},\\\
\tilde{\boldsymbol{x}}^{(t+1)}_{v}=f_{\mathcal{E}\rightarrow\mathcal{V}}(\boldsymbol{Z}^{(t+1)}_{v};\boldsymbol{x}^{(t)}_{v})=\textsc{Mab}(\boldsymbol{x}^{(t)\top}_{v},\textsc{Isab}(\boldsymbol{Z}^{(t+1)}_{v}))^{\top},\\\
\boldsymbol{x}^{(t+1)}_{v}=f_{\mathrm{skip}}(\tilde{\boldsymbol{x}}^{(t+1)}_{v},\boldsymbol{x}^{(t)}_{v},\boldsymbol{x}^{(0)}_{v})=\tilde{\boldsymbol{x}}^{(t+1)}_{v},\end{gathered}$

where $\textsc{Mab}(\cdot)$ and $\textsc{Isab}(\cdot)$ denote the multihead
attention block and the induced set attention block in Set Transformer [69],
as described in the main paper. WHATsNet does not include skip connections and
therefore ignores the original node feature $\boldsymbol{x}^{(0)}_{v}$ in
$f_{\mathrm{skip}}$. ∎

####  D.5 Proof of Proposition 4

######  Proposition 4.

With the same co-representation dimension, CoNHD is expressive enough to
represent the message passing framework, while the opposite is not true.

###### Proof.

We prove the proposition using the GD-based implementation of CoNHD, which can
be easily extended to the ADMM-based implementation.

First, we prove that CoNHD is expressive enough to represent any model within
the message passing framework. We initialize the co-representations as
$\boldsymbol{h}^{(0)}_{v,e}=\big{[}\boldsymbol{x}^{(0)}_{v},\boldsymbol{z}^{(0)}_{e}\big{]}$.
For brevity, we assume $\boldsymbol{x}^{(0)}_{v}\in\mathbb{R}^{\frac{d}{2}}$
and $\boldsymbol{z}^{(0)}_{e}\in\mathbb{R}^{\frac{d}{2}}$. We will show that
given
$\boldsymbol{h}^{(2t)}_{v,e}=\big{[}\boldsymbol{x}^{(t)}_{v},\boldsymbol{z}^{(t)}_{e}\big{]}$,
two layers of CoNHD are expressive enough to generate
$\boldsymbol{h}^{(2(t+1))}_{v,e}=\big{[}\boldsymbol{x}^{(t+1)}_{v},\boldsymbol{z}^{(t+1)}_{e}\big{]}$,
where $\boldsymbol{x}^{(t)}_{v}$ and $\boldsymbol{z}^{(t)}_{e}$ are exactly
correspond to the node and hyperedge representations in the $t$-th layer of
the message passing framework defined in Eq. 1-3.

When $\phi$ and $\varphi$ are implemented by universal equivariant neural
diffusion operators like UNP, they are expressive enough to represent any
equivariant mapping. With the same co-representation dimension, we can use one
layer in CoNHD to represent the nodes-to-edge aggregation process in the
message passing framework. In this layer, we reduce $\phi$, $\varphi$, and
$\psi$ as follows:

$\begin{gathered}\begin{aligned}
\boldsymbol{M}^{(2t+1)}_{e}=\phi(\boldsymbol{H}^{(2t)}_{e})=&\big{[}\mathbf{0}_{d_{e}\times\frac{d}{2}},\mathbf{1}_{d_{e}}\cdot\big{(}f_{\mathcal{V}\rightarrow\mathcal{E}}(\boldsymbol{X}^{(t)}_{e};\boldsymbol{z}^{(t)}_{e})\big{)}^{\top}\big{]}\\\
=&\big{[}\mathbf{0}_{d_{e}\times\frac{d}{2}},\mathbf{1}_{d_{e}}\cdot\boldsymbol{z}^{(t+1)\top}_{e}\big{]},\end{aligned}\\\
\boldsymbol{M}^{\prime(2t+1)}_{v}=\varphi(\boldsymbol{H}^{(2t)}_{v})=\big{[}\mathbf{0}_{d_{v}\times\frac{d}{2}},\mathbf{0}_{d_{v}\times\frac{d}{2}}\big{]},\\\
\boldsymbol{h}^{(2t+1)}_{v,e}=\psi([\boldsymbol{h}^{(2t)}_{v,e},\boldsymbol{m}^{(2t+1)}_{v,e},\boldsymbol{m}^{\prime(2t+1)}_{v,e},\boldsymbol{h}^{(0)}_{v,e}])=\big{[}\boldsymbol{x}^{(t)}_{v},\boldsymbol{z}^{(t+1)}_{e}\big{]},\end{gathered}$

where $\mathbf{1}_{n}$ represents a $n$-dimensional all one vector, which is
used to construct a matrix with repeated row elements. $\mathbf{0}_{m\times
n}$ represents a $(m\times n)$-dimensional all zero matrix. In this layer, we
use $\phi$ to represent the aggregation process and ignore the output of
$\varphi$.

We use another layer to represent the edges-to-node aggregation process and
the skip connection. In this layer, we reduce $\phi$, $\varphi$, and $\psi$ as
follows:

$\begin{gathered}\boldsymbol{M}^{(2(t+1))}_{e}=\phi(\boldsymbol{H}^{(2t+1)}_{e})=\big{[}\mathbf{0}_{d_{e}\times\frac{d}{2}},\mathbf{0}_{d_{e}\times\frac{d}{2}}\big{]},\\\
\begin{aligned}
\boldsymbol{M}^{\prime(2(t+1))}_{v}=\varphi(\boldsymbol{H}^{(2t+1)}_{v})=&\big{[}\mathbf{1}_{d_{v}}\cdot\big{(}f_{\mathcal{E}\rightarrow\mathcal{V}}(\boldsymbol{Z}^{(t+1)}_{v};\boldsymbol{x}^{(t)}_{v})\big{)}^{\top},\mathbf{0}_{d_{e}\times\frac{d}{2}}\big{]}\\\
=&\big{[}\mathbf{1}_{d_{v}}\cdot\tilde{\boldsymbol{x}}^{(t+1)\top}_{v},\mathbf{0}_{d_{e}\times\frac{d}{2}}\big{]},\end{aligned}\\\
\begin{aligned}
\boldsymbol{h}^{(2(t+1))}_{v,e}=&\psi([\boldsymbol{h}^{(2t+1)}_{v,e},\boldsymbol{m}^{(2(t+1))}_{v,e},\boldsymbol{m}^{\prime(2(t+1))}_{v,e},\boldsymbol{h}^{(0)}_{v,e}])\\\
=&\big{[}f_{\mathrm{skip}}(\boldsymbol{x}^{(t)}_{v},\tilde{\boldsymbol{x}}^{(t+1)}_{v},\boldsymbol{x}^{(0)}_{v}),\boldsymbol{z}^{(t+1)}_{e}\big{]}\\\
=&\big{[}\boldsymbol{x}^{(t+1)}_{v},\boldsymbol{z}^{(t+1)}_{e}\big{]}.\end{aligned}\end{gathered}$

In this layer, we use $\varphi$ to represent the aggregation process and
ignore the output of $\phi$. Besides, we set the update function $\psi$ to
represent the skip connection part. The final output
$\boldsymbol{x}^{(t+1)}_{v}$ and $\boldsymbol{z}^{(t+1)}_{e}$ are the
$(t+1)$-th node and hyperedge representation in the message passing framework.
Therefore, CoNHD is expressive enough to represent any model within the
message passing framework.

To show that the opposite is not true, we only need to construct a counter-
example. Since $\phi$ is equivariant, it can generate different diffusing
information $\boldsymbol{m}^{(t)}_{v,e}$ for different node-hyperedge pair
$(v,e)$. We can simply set
$\boldsymbol{h}^{(t)}_{v,e}=\boldsymbol{m}^{(t)}_{v,e}$ in the update function
$\psi$, which lead to different representation for each node-hyperedge pair
$(v,e)$. However, the message passing framework can only generate the same
hyperedge representation for each hyperedge, which constraints that the first
$\frac{d}{2}$ dimension of the co-representations for different node-hyperedge
pairs are the same and cannot generate the same $\boldsymbol{h}^{(t)}_{v,e}$.
Therefore, any model within the message passing framework cannot represent
CoNHD. ∎

###  Appendix E Algorithms of CoNHD

Algorithm 1 and 2 describe the forward propagation of the CoNHD model for
edge-dependent node classification using GD-based and ADMM-based
implementations, respectively. $\phi$ and $\varphi$ are implemented as UNP
(Eq. 10) or ISAB (Eq. 11). Although the proposed CoNHD model can accept any
features related to the node-hyperedge pairs, we initialize the co-
representations using only the node features to follow the setup of the
original ENC problem [12].

Input : A hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, an initial node
feature matrix
$\boldsymbol{X}^{(0)}=[\boldsymbol{x}^{(0)}_{v_{1}},\ldots,\boldsymbol{x}^{(0)}_{v_{n}}]^{\top}$.

Output : Predicted edge-dependent node labels $\hat{y}_{v,e}$.

Initialize $\forall v\in\mathcal{V},\forall
e\in\mathcal{E}_{v}:\boldsymbol{h}^{(0)}_{v,e}=\boldsymbol{x}^{(0)}_{v}$;

for  _$\ell=1,\ldots,L$_ do

// within-edge interactions (Eq. 12).

$\forall
e\in\mathcal{E}:\boldsymbol{M}^{(\ell)}_{e}\leftarrow\phi(\boldsymbol{H}^{(\ell-1)}_{e})$;

// within-node interactions (Eq. 12).

$\forall
v\in\mathcal{V}:\boldsymbol{M}^{\prime(\ell)}_{v}\leftarrow\varphi(\boldsymbol{H}^{(\ell-1)}_{v})$;

// co-representation updates (Eq. 13).

$\forall v\in\mathcal{V},\forall
e\in\mathcal{E}_{v}:\boldsymbol{h}^{(\ell)}_{v,e}\leftarrow\psi([\boldsymbol{h}^{(\ell-1)}_{v,e},\boldsymbol{m}^{(\ell)}_{v,e},\boldsymbol{m}^{\prime(\ell)}_{v,e},\boldsymbol{h}^{(0)}_{v,e}])$;

end for

for  _$v\in\mathcal{V},e\in\mathcal{E}_{v}$_ do

Predict edge-dependent node label $\hat{y}_{v,e}$ using co-representation
$\boldsymbol{h}^{(L)}_{v,e}$.

end for

Algorithm 1 CoNHD-GD for edge-dependent node classification.

Input : A hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, an initial node
feature matrix
$\boldsymbol{X}^{(0)}=[\boldsymbol{x}^{(0)}_{v_{1}},\ldots,\boldsymbol{x}^{(0)}_{v_{n}}]^{\top}$.

Output : Predicted edge-dependent node labels $\hat{y}_{v,e}$.

Initialize $\forall v\in\mathcal{V},\forall
e\in\mathcal{E}_{v}:\boldsymbol{h}^{(0)}_{v,e}=\boldsymbol{x}^{(0)}_{v},\boldsymbol{m}^{(0)}_{v,e}=\boldsymbol{h}^{(0)}_{v,e},\boldsymbol{m}^{\prime(0)}_{v,e}=\boldsymbol{h}^{(0)}_{v,e}$;

for  _$\ell=1,\ldots,L$_ do

// within-edge interactions (Eq. 14).

$\forall
e\in\mathcal{E}:\boldsymbol{M}^{(\ell)}_{e}\leftarrow\phi(2\boldsymbol{H}^{(\ell-1)}_{e}-\boldsymbol{M}^{(\ell-1)}_{e})+\boldsymbol{M}^{(\ell-1)}_{e}-\boldsymbol{H}^{(\ell-1)}_{e}$;

// within-node interactions (Eq. 15).

$\forall
v\in\mathcal{V}:\boldsymbol{M}^{\prime(\ell)}_{v}\leftarrow\varphi(2\boldsymbol{H}^{(\ell-1)}_{v}-\boldsymbol{M}^{\prime(\ell-1)}_{v})+\boldsymbol{M}^{\prime(\ell-1)}_{v}-\boldsymbol{H}^{(\ell-1)}_{v}$;

// co-representation updates (Eq. 16).

$\forall v\in\mathcal{V},\forall
e\in\mathcal{E}_{v}:\boldsymbol{h}^{(\ell)}_{v,e}\leftarrow\psi([\boldsymbol{m}^{(\ell)}_{v,e},\boldsymbol{m}^{\prime(\ell)}_{v,e},\boldsymbol{h}^{(0)}_{v,e}])$;

end for

for  _$v\in\mathcal{V},e\in\mathcal{E}_{v}$_ do

Predict edge-dependent node label $\hat{y}_{v,e}$ using co-representation
$\boldsymbol{h}^{(L)}_{v,e}$.

end for

Algorithm 2 CoNHD-ADMM for edge-dependent node classification.

###  Appendix F Efficiency of CoNHD

####  F.1 Complexity Analysis

We discuss the complexity of two GD-based implementations using UNP or ISAB
operators, while the ADMM-based implementations have similar results.

Both the UNP and ISAB operators have linear complexity with the number of the
input co-representations. For the UNP implementation, the first MLP and the
sum pooling only calculate once for all elements in the set, and the second
MLP calculates in an element-wise manner. We set the same hidden size as the
co-representation size for MLPs. With co-representation dimension $d$, the
overall complexity for the within-edge and within-node interactions in each
layer is
$\mathcal{O}(\sum_{e\in\mathcal{E}}(d_{e}d^{2})+\sum_{v\in\mathcal{V}}(d_{v}d^{2}))=\mathcal{O}(d^{2}\sum_{e\in\mathcal{E}}d_{e})$.
This equation follows from the fact that the sum of node degrees is equal to
the sum of hyperedge degrees, _i.e._ ,
$\sum_{v\in\mathcal{V}}d_{v}=\sum_{e\in\mathcal{E}}d_{e}$. The ISAB
implementation requires dot products between the input co-representations and
$k$ inducing points. The overall complexity for the within-edge and within-
node interactions in each layer is
$\mathcal{O}(\sum_{e\in\mathcal{E}}(d_{e}kd+(d_{e}+k)d^{2})+\sum_{v\in\mathcal{V}}(d_{v}kd+(d_{v}+k)d^{2}))=\mathcal{O}((dk+d^{2})\sum_{e\in\mathcal{E}}d_{e}+\sum_{e\in\mathcal{E}}kd^{2}+\sum_{v\in\mathcal{V}}kd^{2})$.
When $k$ is small (in our experiments, $k=4$), this complexity can be
simplified as $\mathcal{O}(d^{2}\sum_{e\in\mathcal{E}}d_{e})$, which is
consistent with the UNP implementation. For the update function, the
complexity is $\mathcal{O}(d^{2}\sum_{e\in\mathcal{E}}d_{e})$. Therefore, the
overall complexity of CoNHD is
$\mathcal{O}(Ld^{2}\sum_{e\in\mathcal{E}}d_{e})$, where $L$ is the number of
layers.

The overall complexity is linear to the number of node-hyperedge pairs in the
input hypergraph, _i.e._ , $\sum_{e\in\mathcal{E}}d_{e}$. This is similar to
many HGNNs within the message passing framework, _e.g._ , the best baseline
method WHATsNet [12] in the ENC experiments.

####  F.2 Efficiency Advantages in Mini-batch Training

Despite the same theoretical computational complexity, CoNHD exhibits
additional efficiency advantages in mini-batch training as shown in Section
5.1. Compared to full-batch training, mini-batch training is a more common
setting for training on large real-world hypergraphs, which can reduce memory
consumption. In mini-batch training, the overlapping of the subgraphs across
different batches introduces additional computational overhead compared to
full-batch training. The computational load scales with the size of the
neighboring subgraph, _i.e._ , the number of neighboring hyperedges and nodes.

Figure A1: Learning the representation for a node-hyperedge pair in mini-batch
training. (a) An example hypergraph, where node $v_{1}$ and all hyperedges
have degree 3. We want to learn the representation for node-hyperedge pair
$(v_{1},e_{1})$. (b) In the message passing framework, each layer performs a
two-stage aggregation process: from nodes to hyperedges and from hyperedges
back to nodes. This process involves all nodes in the neighboring hyperedges
of node $v_{1}$. Some nodes (_e.g._ , $v_{4}$, $v_{5}$, $v_{6}$, and $v_{7}$)
are not direct neighbors for the node-hyperedge pair $(v_{1},e_{1})$. (c) In
contrast, CoNHD focuses solely on the direct neighbors in each layer,
including neighboring edges of $v_{1}$ (_i.e._ , $e_{1}$, $e_{2}$, and
$e_{3}$) and neighboring nodes of $e_{1}$ (_i.e._ , $v_{1}$, $v_{2}$, and
$v_{3}$). This not only ensures the diffusing information is from the most
related neighbors, but also reduces the subgraph size in each layer and
improves the efficiency.

For convenience, we assume all the node degrees and hyperedge degrees are
equal to $d_{n}$. To calculate the representation for each node-hyperedge
pair, in each layer, the message passing framework needs to calculate the two-
stage aggregation process $\mathcal{V}\rightarrow\mathcal{E}$ and
$\mathcal{E}\rightarrow\mathcal{V}$. This leads to a neighboring subgraph
containing $d_{n}$ hyperedges and $d_{n}^{2}$ nodes. As shown in Fig. A1(b),
this process not only increases the computational complexity but also includes
nodes that are not direct neighbors for the target node-hyperedge pair, which
may affect the learning results. In contrast, each layer of CoNHD only
contains direct neighboring hyperedges and nodes, as shown in Fig. A1(c),
resulting in a smaller subgraph with $d_{n}$ hyperedges and $d_{n}$ nodes.
This can greatly improve the efficiency when handling complex hypergraphs with
large node and hyperedge degrees.

###  Appendix G Additional Details of the Datasets

Table A1 provides a comprehensive overview of the datasets used in our
experiments.

We use all six real-world edge-dependent node classification datasets utilized
in [12]. These datasets are Email (Email-
Enron111https://www.cs.cmu.edu/~enron/ and Email-Eu [79]), StackOverflow
(Stack-Biology222https://archive.org/download/stackexchange and Stack-
Physics2), and Co-authorship networks (Coauth-DBLP [80] and Coauth-
AMiner333https://www.aminer.org/aminernetwork). In Email-Enron and Email-Eu,
nodes represent individuals, and emails act as hyperedges connecting them. The
edge-dependent node labels denote the role of a user within an email (sender,
receiver, or CC’ed). In Stack-Biology and Stack-Physics, nodes represent users
while posts on Stack Overflow are hyperedges. The edge-dependent node label
indicates the role of a user within a post (questioner, chosen answerer, or
other answerer). In Coauth-DBLP and Coauth-AMiner, publications serve as
hyperedges connecting authors (nodes) in these datasets. The edge-dependent
node label represents the order of an author within a publication (first,
last, or others).

For the diffusion operator approximation experiment, we generate semi-
synthetic diffusion data using the Senate [73] dataset with the same initial
features $\boldsymbol{\mathcal{X}}^{(0)}$ as the experiments in [20]. In
Senate, nodes represent individual US Senators, while each hyperedge connects
the sponsor and co-sponsors of a bill introduced in the Senate. Although our
proposed CoNHD model can accept any input features related to the node-
hyperedge pairs, we only utilize initial node features to fit the input of
most HGNNs. Following [20], we sample one-dimensional node feature by the
Gaussion distribution $\mathcal{N}(\mu,\sigma)$, where $\mu=0$ and $\sigma$
uniformly sampled from $[1,10]$. We initialize the features of node-hyperedges
using the node features, _i.e._ ,
$\boldsymbol{\mathcal{H}}^{(0)}=\\{\boldsymbol{x}^{(0)}_{v}|v\in\mathcal{V},e\in\mathcal{E}_{v}\\}$.
We then generate the labels $\boldsymbol{\mathcal{H}}^{(2)}$ by performing two
steps of the co-representation hypergraph diffusion process. We consider three
different diffusion operators: CE [52], TV ($p=2$) [53], and LEC ($p=2$) [54].
We apply gradient descent for the differential diffusion operator CE, and ADMM
for the non-differential diffusion operators TV and LEC. We set equal weights
for the node and edge regularization functions, _i.e._ , $\lambda=\gamma=1$.
We choose $\alpha$ and $\rho$ to make the variance ratio
$\mathrm{Var}(\boldsymbol{\mathcal{H}}^{(2)})/\mathrm{Var}(\boldsymbol{\mathcal{H}}^{(0)})$
in a similar scale. Specifically, we set the step size $\alpha=0.06$ for CE in
gradient descent, and set the scale factor $\rho=0.07$ for TV and $\rho=0.5$
for LEC in the ADMM optimization process. To avoid the node features exposed
in the training process, we generate $100$ pairs
$(\boldsymbol{\mathcal{H}}^{(0)},\boldsymbol{\mathcal{H}}^{(2)})$ using the
same hypergraph structure, where $20$ pairs are for the valid set and $20$
pairs are for the test set.

Table A1: Detailed statistics of the datasets.

Dataset Num. of Nodes Num. of Edges Avg. $d_{v}$ Avg. $d_{e}$ Med. $d_{v}$
Med. $d_{e}$ Max. $d_{v}$ Max. $d_{e}$ Min. $d_{v}$ Min. $d_{e}$ Email-Enron
21,251 101,124 55.83 11.73 8 6 18,168 948 1 3 Email-Eu 986 209,508 549.54 2.59
233 2 8,659 59 1 2 Stack-Biology 15,490 26,823 3.63 2.10 1 2 1,318 12 1 1
Stack-Physics 80,936 200,811 5.93 2.39 1 2 6,332 48 1 1 Coauth-DBLP 108,484
91,266 2.96 3.52 1 3 236 36 1 2 Coauth-AMiner 1,712,433 2,037,605 3.03 2.55 1
2 752 115 1 1 Senate 282 315 19.18 17.17 15 19 63 31 1 4

###  Appendix H Implementation Details

To ensure a fair comparison, we follow the experimental setup for edge-
dependent node classification in [12]. All models are tuned using grid search.
Specifically, the learning rate is chosen from $\\{0.0001,0.001\\}$ and the
number of layers is chosen from $\\{1,2\\}$. The batch size is set from
$\\{256,512\\}$ for the Coauth-AMiner dataset due to the large node number,
while for other datasets the batch size is chosen from $\\{64,128\\}$. To
maintain consistent computational cost across methods, we fix the embedding
dimension for node and hyperedge representations in baseline methods, and co-
representations in the proposed CoNHD method, to $128$. The dropout rate is
set to $0.7$. We run the models for $100$ epochs with early stopping. For the
implementation of the ISAB operator, we set the number of inducing points to
$4$ as WHATsNet, and use $2$ attention layers. During training, we sample $40$
neighboring hyperedges of a node, while we do not sample neighboring nodes of
a hyperedge since the final label is related to all nodes in a hyperedge. HCHA
[36] and HNN [19] are run in full-batch training with more epochs as in [12].
As different diffusion steps utilize the same diffusion operators in
hypergraph diffusion, we share the weights in different layers of the proposed
CoNHD model. We employ the same relative positional encoding as in the
experiments of WHATsNet [12], which has shown effectiveness in predicting
edge-dependent node labels.

For the diffusion operator approximation experiment, most hyperparameters
follow the same setting as the ENC experiment. To ensure the expressive power
of all models, we use a relatively large embedding dimension $256$. The number
of layers is fixed to $2$, which is consistent with the steps of the diffusion
process for generating the labels.

We conduct all experiments on a single NVIDIA A100 GPU with 40GB of GPU
memory. To ensure statistically significant results, we repeat each experiment
with $5$ different random seeds and report the mean performance along with the
standard deviation.

###  Appendix I Supplementary Experimental Results

####  I.1 More Visualization of the Learned Embeddings

We visualize the learned embeddings of node-hyperedge pairs in the Email-Enron
dataset using LDA. As the same node can have different labels in different
hyperedges, we choose the three largest-degree nodes and present the node-
hyperedge embeddings associated with each of them. For the small-degree nodes,
as these nodes are incident in fewer hyperedges, we visualize the node-
hyperedge embeddings of the total 300 smallest-degree nodes. As shown in Fig.
A2, CoNHD can learn more separable embeddings compared to the best baseline
method WHATsNet on large-degree nodes. For the small-degree nodes, the
embeddings from both methods can show clear distinction based on the edge-
dependent node labels. CoNHD implements the interactions as multi-input multi-
output functions, which can preserve specific information for each node-
hyperedge pair and avoid potential information loss. This leads to significant
performance improvements on the ENC task, especially for complex hypergraphs
with large-degree nodes and hyperedges.

Figure A2: More Visualization of embeddings in the Email-Enron dataset using
LDA. WHATsNet fails to learn separable embedding for node-hyperedge pairs
associated with large-degree nodes, while the embeddings learned by CoNHD
exhibit clearer distinctions. For small-degree nodes, both methods can learn
separable embeddings for node-hyperedge pairs.