Hypergraph Neural Networks through the Lens of Message Passing: A Common
  Perspective to Homophily and Architecture Design
Most of the current hypergraph learning methodologies and benchmarking
datasets in the hypergraph realm are obtained by lifting procedures from their
graph analogs, leading to overshadowing specific characteristics of
hypergraphs. This paper attempts to confront some pending questions in that
regard: Q1 Can the concept of homophily play a crucial role in Hypergraph
Neural Networks (HNNs)? Q2 Is there room for improving current HNN
architectures by carefully addressing specific characteristics of higher-order
networks? Q3 Do existing datasets provide a meaningful benchmark for HNNs? To
address them, we first introduce a novel conceptualization of homophily in
higher-order networks based on a Message Passing (MP) scheme, unifying both the
analytical examination and the modeling of higher-order networks. Further, we
investigate some natural, yet mostly unexplored, strategies for processing
higher-order structures within HNNs such as keeping hyperedge-dependent node
representations, or performing node/hyperedge stochastic samplings, leading us
to the most general MP formulation up to date -MultiSet-, as well as to an
original architecture design, MultiSetMixer. Finally, we conduct an extensive
set of experiments that contextualize our proposals and successfully provide
insights about our inquiries.
Lev Telyatnikov, Maria Sofia Bucarelli, Guillermo Bernardez, Olga Zaghen, Simone Scardapane, Pietro Lio
Hypergraph Neural Networks through the Lens of message passing: A Common Perspective to Homophily and Architecture Design

###### Abstract

Most of the current hypergraph learning methodologies and benchmarking datasets in the hypergraph realm are obtained by _lifting_ procedures from their graph analogs, simultaneously leading to overshadowing hypergraph network foundations. This paper attempts to confront some pending questions in that regard: Can the concept of homophily play a crucial role in Hypergraph Neural Networks (HGNNs), similar to its significance in graph-based research? Is there room for improving current hypergraph architectures and methodologies? (e.g. by carefully addressing the specific characteristics of higher-order networks) Do existing datasets provide a meaningful benchmark for HGNNs? Diving into the details, this paper proposes a novel conceptualization of homophily in higher-order networks based on a message passing scheme; this approach harmonizes the analytical frameworks of datasets and architectures, offering a unified perspective for exploring and interpreting complex, higher-order network structures and dynamics. Further, we propose MultiSet, a novel message passing framework that redefines HGNNs by allowing hyperedge-dependent node representations, as well as introduce a novel architecture -MultiSetMixer- that leverages a new hyperedge sampling strategy. Finally, we provide an extensive set of experiments that contextualize our proposals and lead to valuable insights in hypergraph representation learning.

## 1 Introduction

Hypergraph learning techniques have rapidly grown in recent years, demonstrating their effectiveness in processing higher-order interactions in numerous fields, spanning from recommender systems (Yu et al., 2021; Zheng et al., 2018; La Gatta et al., 2022), to bioinformatics (Zhang et al., 2018; Yadati et al., 2020; Klamt et al., 2009) and computer vision (Li et al., 2022; Xu et al., 2022; Gao et al., 2012; Yin et al., 2017; Kim et al., 2011). However, so far, the development of HyperGraph Neural Networks (HGNNs) has been largely influenced by the well-established Graph Neural Network (GNN) field. In fact, most of the current methodologies and benchmarking datasets in the hypergraph realm are obtained by _lifting_ procedures from their graph counterparts.

Drawing inspiration from graph-based models has significantly propelled the advancement of hypergraph research (Feng et al., 2019; Yadati et al., 2019; Chien et al., 2022), and it has simultaneously led to overshadowing hypergraph network foundations. We argue that it is now the time to address fundamental questions in order to pave the way for further innovative ideas in the field. In that regard, this study explores some of these open questions to understand better current HGNN architectures and benchmarking datasets. Can the concept of homophily play a crucial role in HGNNs, similar to its significance in graph-based research? Given that current HGNNs are predominantly extensions of GNN architectures adapted to the hypergraph domain, are these extended methodologies suitable, or should we explore new strategies tailored specifically for handling hypergraph-based data? Are the existing hypergraph benchmarking datasets truly _meaningful_ and representative enough to draw robust and valid conclusions?
To begin with, we explore how the concept of homophily can be characterized in complex, higher-order networks. Notably, there are many ways of characterizing homophily in hypergraphs -such as the distribution of node features, the analogous distribution of the labels, or the group connectivity similarity (as already discussed in (Veldt et al., 2023)). In particular, this work places the _node class distribution_ at the core of the analysis, and introduces a novel definition of homophily that relies on a message passing scheme. Interestingly, this enables us to analyze both hypergraph datasets and architecture designs from the same perspective. In fact, we reckon that this unified message passing framework has the potential to inspire the development of meaningful contributions for processing higher-order relationships more effectively.

Next, we study state-of-the-art HGNN architectures and introduce a new framework called MultiSet. We demonstrate that MultiSet generalizes most existing frameworks for HGNNs, including AllSet (Chien et al., 2022) and UniGCNII (Huang and Yang, 2021). Our framework presents an innovative approach to message passing, where multiple hyperedge-dependent representations of nodes are enabled. Then, we introduce novel methodologies to process hypergraphs -including MultiSetMixer, a new HGNN architecture based on a particular implementation of a MultiSet layer. In these implementations, we introduce a novel connectivity-based mini-batching strategy capable of processing large hyperedges and discuss the intriguing property of natural connectivity-based distribution shifts.

Last, but not least, we provide an extensive set of experiments that, driven by the general questions stated above, aim to gain a better understanding on fundamental aspects of hypergraph representation learning. In fact, the obtained results not only help us contextualize the proposals introduced in this work, but indeed offer valuable insights that might help improve future hypergraph approaches.

## 2 Related Works

Homophily in hypergraphs.Homophily measures are typically defined for graph models and consider only pairwise relationships. In the context of Graph Neural Networks (GNNs), many of the current models implicitly use the homophily assumption, which is shown to be crucial for achieving a robust performance with relational data (Zhou et al., 2020; Chien et al., 2020; Halcrow et al., 2020). Nevertheless, despite the pivotal role that homophily plays in graph representation learning, its hypergraph counterpart mainly remains unexplored. In fact, to the best of our knowledge, Veldt et al. (2023) is the only work that faces the challenge of defining homophily in higher-order networks. Veldt et al. (2023) introduces a framework in which hypergraphs are used to quantify homophily from group interactions; however, the definition of homophily is restricted to uniform hypergraphs -i.e. where all hyperedges have exactly the same size (more details in Section 3). This represents a hard assumption that complicates its applicability to most of the current hypergraph datasets.

Hypergraph Neural Networks.The work of Chien et al. (2022) introduced AllSet, a general framework to describe HGNNs through a two-step message passing based mechanism, and demonstrated that most of the current hypergraph models are special instances of their formulation, based on the composition of two learnable permutation invariant functions that transmit information from nodes to hyperedges, and back from hyperedges to nodes. In particular, AllSet can be seen as a generalization of the most commonly used HGNNs, including all clique expansion based (CE) methods, HGNN (Feng et al., 2019), HNHN (Dong et al., 2020), HCHA (Bai et al., 2021), HyperSAGE (Arya et al., 2020) and HyperGCN(Yadati et al., 2019). Chien et al. (2022) also proposes two novel AllSet-like learnable layers: the first one -AllDeepSet- exploits Deep Set (Zaheer et al., 2017), and the second one -AllSetTransformer- Set Transformer (Lee et al., 2019), both of them achieving state-of-the-art results in the most common hypergraph benchmarking datasets. Concurrent to AllSet, the work of Huang and Yang (2021) also aimed at designing a common framework for graph and hypergraph NNs, and its more advanced UniGCNII method leverages initial residual connections and identity mappings in the hyperedge-to-node propagation to address over-smoothing issues; notably, UniGCNII do not fall under AllSet notation due to these residual connections. With Chien et al. (2022) and Huang and Yang (2021) being the most relevant ones to our work, we extend this review in Appendix A.
**Notation.** A hypergraph is an ordered pair of sets \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) is the set of nodes and \(\mathcal{E}\) is the set of hyperedges. Each hyperedge \(e\in\mathcal{E}\) is a subset of \(\mathcal{V}\), i.e., \(e\subseteq\mathcal{V}\). A hypergraph is a generalization of the concept of a graph where (hyper)edges can connect more than two nodes. A vertex \(v\) and a hyperedge \(e\) are said to be incident if \(v\in e\). For each node \(v\), we denote its class by \(y_{v}\), and by \(\mathcal{E}_{v}=\{e\in\mathcal{E}:v\in e\}\) the subset of hyperedges in which it is contained, with \(d_{v}=|\mathcal{E}_{v}|\) depicting the node degree. The set of classes of the hypergraph is represented by \(\mathcal{C}=\{c_{i}\}_{i=1}^{|\mathcal{C}|}\).

## 3 Defining and measuring homophily in hypergraphs

Homophily is a graph property that describes the tendency for edges to connect nodes that are similar (Moody, 2001; Shrum et al., 1988; Verbrugge, 1983). Currently, the most common measure of graph homophily is the proportion of edges that connect nodes of the same class. In pairwise relationships, a high degree of network homophily tends to create a network with communities, based on nodes' class, that are highly connected within each other and poorly connected to the outside. Extending the concept of homophily to higher-order interactions is not straightforward, but it becomes crucial in order to avoid discarding valuable information about the composition of groups in which individuals participate. In this Section, we recap the general notion of higher-order homophily for \(k\)-uniform hypergraphs introduced in (Veldt et al., 2023) and present a novel propagation-based homophily measure which is applicable for general, non-uniform hypergraphs. In essence, the score proposed in Veldt et al. (2023) tends to primarily assess the composition of hyperedges within the graph by quantifying the distribution of classes among hyperedges. In contrast, our definition places a greater emphasis on capturing the interconnections between different hyperedges by the exchange of information between nodes following the message passing scheme.

\(k\)-uniform HomophilyVeldt et al. (2023) defines general higher-order homophily for \(k\)-uniform hypergraphs \(G_{k}=(\mathcal{V},\mathcal{E}_{k})\) which we refer to as _\(k\)-uniform homophily_. The type \(t\)-affinity score for each \(t\in\{1,\ldots,k\}\), indicates the likelihood of a node belonging to class \(c\) participating in hyperedges in which exactly \(t\) group members belong to class \(c\). The authors introduce a _baseline score_ that measures the probability that a class-\(c\) node is in a hyperedge where \(t\) members are from class \(c\), given that the other \(k-1\) nodes were chosen uniformly at random. The \(k\)-uniform hypergraph homophily measure can be expressed as a ratio of affinity and baseline scores, with a ratio value of 1 indicating that the group is formed uniformly at random, while any other number indicates that group interactions are either overexpressed or underexpressed for class \(c\). Note that non-uniform hypergraphs cannot directly be evaluated with \(k\)-uniform homophily scores; instead, the corresponding initial hyperedge set \(\mathcal{E}\) has to be restricted to particular \(k\)-uniform hyperedges, and for each \(k\) values they are processed separately. The detailed formulation of homophily measures and corresponding plots for each dataset can be found in Appendix J.

Message Passing HomophilyWe present a novel two-step message passing homophily measure that, unlike the one proposed by Veldt et al. (2023), does not assume a \(k\)-uniform hypergraph structure. Furthermore, the proposed measure enables the definition of a score for each node and hyperedge for any neighborhood resolution, i.e., the connectivity of the hypergraph can be explicitly investigated. Our homophily definition follows the two-step message passing mechanism starting from the hyperedges of the hypergraph. Thus, given an edge \(e\), we define the 0-level hyperedge homophily \(h_{e}^{0}(c)\) as the fraction of nodes within each hyperedge that belong to class \(c\), i.e.

\[h_{e}^{0}(c)=\frac{1}{|e|}\sum_{v\in e}\mathds{1}_{y_{v}=c}. \tag{1}\]

This score describes how homophilic the initial connectivity is with respect to class \(c\). By computing the score for every class \(c_{i}\in\mathcal{C}\) we obtain a categorical distribution for each hyperedge \(e\in\mathcal{E}\), i.e. \(h_{e}^{0}=(h_{e}^{0}(c_{0}),\ldots,h_{e}^{0}(c_{|\mathcal{C}|}))\). We can then use this 0-level homophily information as a starting point to calculate higher-level homophily measurements for both nodes and hyperedges through the two-step message passing approach. Formally, we define the \(t\)-level homophily score as

\[h_{v}^{t}(y_{v})=\texttt{AGG}_{\mathcal{E}}\left(\{h_{e}^{t-1}(y_{v})\}_{e\in \mathcal{E}_{v}}\right), \tag{2}\]
where \(\texttt{AGG}_{\mathcal{E}}\) and \(\texttt{AGG}_{\mathcal{V}}\) are functions that aggregate edge and node homophily scores, respectively. In our implementation, we considered the mean operation for both aggregations.

Qualitative AnalysisIn this paragraph, we are taking a closer look at the qualitative analysis of the node homophily measure we introduced. One of the most straightforward ways to make use of the message passing homophily measure is to visualize how the node homophily score, as described in Eq. 2, changes dynamically. We've depicted this process in Figure 1, focusing on the CORA-CA and 20NewsGroup datasets. Please note that in the figure, we are only showing non-isolated nodes. Looking at Figure 1 (a), we can observe several notable trends. First, in the initial node distribution (\(t=0\)), every class, except class 6, has a significant number of fully homophilic nodes. As we move to the 1-hop neighborhood (\(t=1\)), the corresponding classes either exhibit a moderate decrease in homophily or show no decrease at all. It's worth noting that at \(t=0,1,\) and \(10\), class 2 maintains a stable homophily distribution, hinting at an isolated subnetwork within. Furthermore, at \(t=10\), some points still maintain a node homophily score of 1, indicating the presence of multiple small subnetworks. Class 6 consistently displays the lowest average homophily measure at every step, with an average score of approximately 38% at \(t=10\). The node homophily distribution for the 20Newsgroups dataset is visualized in Figure 1 (b). At time step \(t=0\), we observe a wide range of homophily scores from 0 to 1 for each class. This suggests that the network is highly irregular with respect to connectivity. Moving to time step \(t=1\), there is a significant decrease in the homophily scores for every class, indicating a high degree of heterophily within the 1-hop neighborhood, which is not surprising considering step zero node homophily distribution. Finally, at time step \(t=10\), we can observe that all the classes converge to approximately the same homophily values within each class. This convergence suggests that the network is highly interconnected. More insights regarding node homophily measure and related HGNNs performances are described in Section 5 while the rest of the plots for the datasets can be found in Appendix I.

## 4 Methods

Current HGNNs aim to generalize GNN concepts to the hypergraph domain, and are specially focused on redefining graph-based propagation rules to accommodate higher-order structures. In this regard, the work of Chien et al. (2022) introduced a general notation framework, called AllSet, that encompasses most of the currently available HGNN layers, including CEGCN/CEGAT, HGNN (Feng et al., 2019), HNHN (Dong et al., 2020), HCHA (Bai et al., 2021), HyperGCN (Yadati et al., 2019), and the AllDeepSet and AllSetTransformer presented in the same work (Chien et al., 2022).

The first part of this Section revisits the original AllSet formulation. Then, we introduce a new framework -termed MultiSet- which extends AllSet by allowing multiple hyperedge-dependent

Figure 1: Node Homophily Distribution Scores for CORA-CA (a) and 20Newsgroups (b) using Equation 2 at \(t=0,1,\) and \(10\) (left, middle, and right plots correspondingly). Horizontal lines depict class mean homophily, with numbers above indicating the number of visualized points per class.
representations of nodes. Finally, we present some novel methodologies to process hypergraphs -including MultiSetMixer, a new HGNN architecture within the MultiSet framework.

### AllSet Propagation Setting

For a given node \(v\in\mathcal{V}\) and hyperedge \(e\in\mathcal{E}\) in a hypergraph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), let \(\mathbf{x}_{v}^{(t)}\in\mathbb{R}^{f}\) and \(\mathbf{z}_{e}^{(t)}\in\mathbb{R}^{d}\) denote their vector representations at propagation step \(t\). We say that a function \(f\) is a multiset function if it is permutation invariant w.r.t. each of its arguments in turn. Typically, \(\mathbf{x}_{v}^{(0)}\) and \(\mathbf{z}_{e}^{(0)}\) are initialized based on the corresponding node and hyperedge original features, if available. The vectors \(\mathbf{x}_{v}^{(0)}\) and \(\mathbf{z}_{e}^{(0)}\) represent the initial node and hyperedge features, respectively. In this context, the AllSet framework (Chien et al., 2022) consists in the following two-step update rule:

\[\mathbf{z}_{e}^{(t+1)}=f_{\mathcal{V}\to\mathcal{E}}(\{\mathbf{x}_{u}^{(t)}\}_{u:u\in \mathcal{E}};\mathbf{z}_{e}^{(t)}), \tag{4}\]

\[\mathbf{x}_{v}^{(t+1)}=f_{\mathcal{E}\to\mathcal{V}}(\{\mathbf{z}_{e}^{(t+1)}\}_{e\in \mathcal{E}_{v}};\mathbf{x}_{v}^{(t)}), \tag{5}\]

where \(f_{\mathcal{V}\to\mathcal{E}}\) and \(f_{\mathcal{E}\to\mathcal{V}}\) are two permutation invariant functions with respect to their first input. Equations 4 and 5 describe the propagation from nodes to hyperedges and from hyperedges to nodes, respectively. We extend the original AllSet formulation to accommodate UniGCNII (Huang and Yang, 2021), a concurrent work to AllSet, by modifying the node update rule (Eq. 5) in order to allow residual connections, i.e.:

\[\mathbf{x}_{v}^{(t+1)}=f_{\mathcal{E}\to\mathcal{V}}(\{\mathbf{z}_{e}^{(t+1)}\}_{e\in \mathcal{E}_{v}};\{\mathbf{x}_{v}^{(k)}\}_{k=0}^{t}). \tag{6}\]

There is no requirement for the function to be permutation invariant with respect to this second set.

**Proposition 1**.: _UniGCNII Huang and Yang, 2021 is a special case of AllSet considering 4 and 6._

In the practical implementation of a model, \(f_{\mathcal{V}\to\mathcal{E}}\) and \(f_{\mathcal{E}\to\mathcal{V}}\) are parametrized and learnt for each dataset and task, and particular choices of these functions give rise to the different HGNN layer architectures considered in this paper; more details in Appendix B.

### MultiSet Framework

In this Section, we introduce our proposed MultiSet framework, which can be seen as an extension of AllSet where nodes can have multiple co-existing hyperedge-based representations. For a given hyperedge \(e\in\mathcal{E}\) in a hypergraph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), we denote by \(\mathbf{z}_{e}^{(t)}\in\mathbb{R}^{d}\) its vector representation at step \(t\). However, for a node \(v\in\mathcal{V}\), MultiSet allows for as many representations of the node as the number of hyperedges it belongs to. We denote by \(\mathbf{x}_{v,e}^{(t)}\in\mathbb{R}^{f}\) the vector representation of node \(v\) in a hyperedge \(e\in\mathcal{E}_{v}\) at propagation time \(t\), and by \(\mathbb{X}_{v}^{(t)}=\{\mathbf{x}_{v,e}^{(t)}\}_{e\in\mathcal{E}_{v}}\), the set of all \(d_{v}\) hidden states of that node in the specified time-step. Accordingly, the hyperedge and node update rules of Multiset are formulated to accommodate hyperedge-dependent node representations:

\[\mathbf{z}_{e}^{(t+1)}=f_{\mathcal{V}\to\mathcal{E}}(\{\mathbb{X}_{u}^{(t)}\}_{u:u \in e};\mathbf{z}_{e}^{(t)}), \tag{7}\]

\[\mathbf{x}_{v,e}^{(t+1)}=f_{\mathcal{E}\to\mathcal{V}}(\{\mathbf{z}_{e}^{(t+1)}\}_{e \in\mathcal{E}_{v}};\{\mathbb{X}_{v}^{(k)}\}_{k=0}^{t}), \tag{8}\]

where \(f_{\mathcal{V}\to\mathcal{E}}\) and \(f_{\mathcal{E}\to\mathcal{V}}\) are two multiset functions with respect to their first input. After \(T\) iterations of message passing, MultiSet also considers a last readout-based step with the idea of obtaining a unique final representation \(x_{v}^{T}\in\mathbb{R}^{f^{\prime}}\) for each node from the set of its hyperedge-based representations:

\[\mathbf{x}_{v}^{(T)}=f_{\mathcal{V}\to\mathcal{V}}(\{\mathbb{X}_{v}^{(k)}\}_{k=0} ^{T}) \tag{9}\]

where \(f_{\mathcal{V}\to\mathcal{V}}\) is also a multiset function.

**Proposition 2**.: _AllSet 4-5, as well as its extension 4-6, are special cases of MultiSet 7-8-9._

Figure 3: MultiSet layout

Figure 2: AllSet layout
### Training MultiSet networks

This Section describes the main characteristics of our MultiSet layer implementation, termed MultiSetMixer, and presents a novel sampling procedure that our model incorporates.

Learning MultiSet LayersFollowing the mixer-style block designs (Tolstikhin et al., 2021) and standard practice, we propose the following MultiSet layer implementation for HGNNs:

\[\mathbf{z}_{e}^{(t+1)}=f_{\mathcal{V}\rightarrow\mathcal{E}}(\{\mathbf{x}_{u,e}^{(t)} \}_{w:u\in e};\mathbf{z}_{e}^{(t)}):=\frac{1}{|e|}\sum_{v\in e}\mathbf{x}_{u,e}^{(t)}+ \text{MLP}\left(\text{LN}\left(\frac{1}{|e|}\sum_{v\in e}\mathbf{x}_{u,e}^{(t)} \right)\right), \tag{10}\]

\[\mathbf{x}_{v,e}^{(t+1)}=f_{\mathcal{E}\rightarrow\mathcal{V}}(\mathbf{z}_{e}^{(t+1)} ;\mathbf{x}_{v,e}^{(t)}):=\mathbf{x}_{v,e}^{(t)}+\text{MLP}\left(\text{LN}(\mathbf{x}_{v,e }^{(t)})\right)+\mathbf{z}_{e}^{(t+1)}, \tag{11}\]

\[\mathbf{x}_{v}^{(T)}=f_{\mathcal{V}\rightarrow\mathcal{V}}(\mathbb{X}_{v}^{(T)}): =\frac{1}{d_{v}}\sum_{e\in\mathcal{E}_{v}}\mathbf{x}_{v,e}^{(t)} \tag{12}\]

where MLPs are composed of two fully-connected layers, and LN stands for layer normalisation. This novel architecture, which we call MultiSetMixer, is based on a mixer-based pooling operation for _(i)_ updating hyperedges from its node's representations, and _(ii)_ generate and update hyperedge-dependent representations of the nodes.

**Proposition 3**.: _The functions \(f_{\mathcal{V}\rightarrow\mathcal{E}}\), \(f_{\mathcal{E}\rightarrow\mathcal{V}}\) and \(f_{\mathcal{V}\rightarrow\mathcal{V}}\) defined in MultiSetMixer are permutation invariant. Furthermore, these functions are universal approximators of multiset functions when the size of the input multiset is finite._

Mini-batchingThe motivation for introducing a new strategy to iterate over hypergraph datasets is twofold. On the one hand, current HGNN pipelines suffer from scalability issues to process large datasets and very large hyperedges. On the other, pooling operations over relatively large sets can also lead to over-squashing the signal. To help in these directions, we propose sampling \(X\) mini-batches of a certain size \(B\) at each iteration. At _step 1_, it samples \(B\) hyperedges from \(\mathcal{E}\). The hyperedge sampling over \(\mathcal{E}\) can be either uniform or weighted (e.g. by taking into account hyperedge cardinalities). Then in _step 2_\(L\) nodes are in turn sampled from each sampled hyperedge \(e\), padding the hyperedge with \(L-|e|\) special padding tokens if \(|e|>L\). Overall, the shape of the obtained mini-batch \(X\) has fixed size \(B\times L\). See Appendix H for additional analysis of the sampling procedure.

## 5 Experimental Results

The questions that we introduced in the Introduction have shaped our research, leading to a new definition of higher-order homophily and novel architectural designs and sampling strategies that can potentially fit better the properties of hypergraph networks. In subsequent subsections, we set again three main questions that follow up from these fundamental inquiries and can help contextualize the technical contributions introduced in this paper.

Dataset and ModelsWe use the same datasets used in Chien et al. (2022), which includes Cora, Citeseer, Pubmed, ModelNet40, NTU2012, 20Newsgroups, Mushrorom, ZOO, CORA-CA, and DBLP-CA. More information about datasets and corresponding statistics can be found in Appendix F.2. We also utilize the benchmark implementation provided by Chien et al. (2022) to conduct the experiments with several models, including AllDeepSets, AllSetTransformer, UniGCNII, CEGAT, CEGCN, HCHA, HGNN, HNPN, HyperGCN, HAN, and HAN (mini-batching). Additionally, we consider vanilla MLP applied to node features and a transformer architecture and introduce three new models: MultiSetMixer, MLP Connectivity Batching (MLP CB), and Multiple MLP CB (MMLP CB). The MLP CB and MMLP CB models use connectivity information to form and process batches. Specifically, the MMLP CB model processes the top three most frequent connectivities using separate MLP encoders, while the fourth encoder is used to process the remaining connectivities. We refer to Section 4.3 for further details about all these architectures. All models are optimized using 15 splits with 2 model initializations, resulting in a total of 30 runs; see Appendix F.1 for further details.
### How does MultiSetMixer perform?

Our first experiment aims to assess the performance of our proposed model, MultiSetMixer, as well as the two introduced baselines, MLP CB and MMLP CB. Figure 4 shows the average rankings -across all models and datasets- of the top-3 best performing models for the considered training splits, exhibiting that those splits can impact the relative performance among models.

However, due to space limitations, we restrict our analysis to the \(50\%\) split results shown in Table 1,1 and relegate to Appendix G.1 the corresponding tables for the other scenarios. Table 1 emphasizes the MultiSetMixer model's relatively solid performance, being the best-performing model on the NTU2012, ModelNet40, and 20Newsgroups datasets. Its performance on the 20Newsgroups dataset is especially noteworthy, significantly outperforming the other models. Moreover, it is notable that MLP CB and MMLP CB exhibit similar behaviour on this dataset. In contrast, the performance of all other models achieves roughly the same performance as the MLP. This observation suggests that these models can not account for dataset connectivity; in particular, as we demonstrated in Section 3, the dispersion of the node homophily measure, with a subsequent convergence to a similar value within each class, indicates that the dataset's connectivity is notably non-homophilic and presents a challenge. In contrast, CORA-CA exhibits a high degree of homophily within its hyperedges and shows the most significant performance gap between the best-performing model, AllSetTransformer, and the basic MLP. A similar trend is observed for DBLP-CA (see node homophily plot in Appendix I). Please refer to Section 5.3 for additional experiments analyzing the impact of connectivity on the models.

Footnote 1: Unless otherwise specified, all tables in the main body of the paper use a \(50\%/25\%/25\%\) split between training and testing. The results are shown as Mean Accuracy Standard Deviation, with the best result highlighted in bold and shaded in grey, and results within one standard deviation of the best result are displayed in blue-shaded boxes.

On the other hand, we can notice that CEGAT, CEGON and our proposed model don't perform well on the Mushroom dataset. This is noteworthy because the Mushroom dataset's features are highly representative, as demonstrated by the near-perfect performance of the MLP classifier. This suggests that, in this particular case, connectivity may not play a crucial role in achieving high performance.

### What is the impact of the introduced mini-batch sampling strategy?

Next, we examine the role that our proposed mini-batching sampling can play _(i)_ in explaining previous results and _(ii)_ in influencing other model's performance.

Class distribution analysisTo evaluate and motivate the potential of the proposed mini-batching sampling, we investigate the reason behind both the superior performance of MultiSetMixer, MLP CB and MMLP CB on 20NewsGroup and their poor performance on Mushroom. Framing mini-batching from the connectivity perspective presents a nuanced challenge that conceals significant potential for improvement (Teney et al., 2023). It is important to note that connectivity, by definition,

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c} \hline \hline Model & Case & Case & Case & Case & Case & Case & Case & Case & Case & Case & Case \\ \hline Mushroom & 77.1 & 77.1 & 77.2 & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** \\ \hline Mushroom & 77.1 & 77.1 & 77.2 & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** & **77.2** \\ \hline Mushroom & 77.1 & 77.
describes relationships among the nodes, implying that some parts of the dataset might interconnect much more densely, creating some sort of hubs within the network. Thus, mini-batching might introduce unexpected skew in training distribution. In particular, in Figure 5, we depict the class distribution of the original dataset, referred to as _Node_, while _'Step 1 and 2'_ and _'Step 1'_ shows the distribution after each step in our mini-batching procedure. The sampling procedure tends to rebalance class distributions in certain cases, such as the 20NewsGroup dataset, while in contrast, it introduces an imbalance that was not present in the original labels in the Mushroom dataset, where our model demonstrated suboptimal performance. This observation leads to the hypothesis that, in some cases, the sampling procedure produces a shift distribution that rebalances the class distributions and conducts our model to outperform the comparison models.

Application to Other ModelsFurthermore, we explore the proposed mini-batch sampling procedure with the AllSetTransformer and UniGCNII models by implementing Step 1 of the mini-batch procedure without additional hyperparameter optimization. From Table 2, we can observe a drop in performance for most of the datasets both for AllSetTransformer and for UniGCNII; both models, on average, outperform the HAN (mini-batching) model. This suggests the substantial potential of the proposed sampling procedure. More in detail, AllSetTransformer has a substantial decrease in accuracy for the CORA-CA dataset, in contrast to the UniGCNII, which registers only marginal decreases. A parallel pattern emerges with the DBLP-CA dataset.

### How do connectivity changes affect performance?

To shine a light on this, we design two different experimental approaches aiming at modifying the original connectivity of datasets in a systematic manner. The first experiment tests the performance when some hyperedges are removed following different _drop connectivity_ strategies. Then, a second experiment examines the model's performance with the introduction of two preprocessing strategies applied to the given hypergraph connectivity.

Reducing ConnectivityThis experiment aims to investigate the significance of connectivity in datasets and the extent to which it influences the performances of the models. We divide this experiment into two parts: (i) drop connectivity and (ii) connectivity rewiring. In the first part of the experiment, we employ three strategies to introduce variations in the initial dataset's connectivity. The first two strategies involve ordering hyperedges based on their lengths in **ascending order**. In the first approach, referred to as _trimming_, we remove the initial \(x\%\) of ordered hyperedges. The second approach, referred to as _retention_, involves keeping the first \(x\%\) of hyperedges and discarding the remaining \(100-x\%\). Finally, the last strategy involves randomly dropping \(x\%\) of hyperedges from the dataset, referred to as _random drop_. Results shown in Table 3 also indicate that connectivity minimally impacts CEGCN, and AllSetTransformer for the Citeseer and Pubmed datasets. On the other hand, MultiSetMixer performs better at the _trimming 25%_ setting, although the achieved performance is on par with MLP reported in Table 1. This suggests that the proposed model was negatively affected by the distribution shift. Conversely, we observe a similar but opposite trend for the Mushroom dataset, where MultiSetMixer's performance improves due to the reduced impact of the distribution shift. Another interesting observation is that the CEGCN model gains improvement in 6 out of 9 datasets, with a doubled increase for the ZOO dataset. In the case of Cora, CORA-CA, and DBLP-CA datasets, another interesting pattern emerges: retaining only 25% of the highest relationships (_retention 25%_) consistently results in better performance compared to retaining 50% or 75%. This is intriguing because, at the 25% level, we are preserving only a small fraction of the higher-order relationships. The opposite pattern holds for the _trimming_ strategy. For the

\begin{table}
\begin{tabular}{c|c c c c c c c c c c c c} \hline Model & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} & \multicolumn{2}{c|}{CIM} \\ \hline AllSetTransformer & Mobile & 71.34 & 1.08 & 69.51 & 1.46 & **0.55** & **0.55** & **0.55** & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 \\ UniGCNI (DBLP) & **0.55** & **0.55** & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 \\ UniGCNI (DBLP) & **0.55** & **0.55** & **0.55** & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 \\ UniGCNI (DBLP) & **0.55** & **0.55** & **0.55** & **0.55** & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 & 0.55 \\ UniGCNI (DBLP) & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & 0.55 & 0.55 & 0.55 \\ UniGCNI & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** & **0.55** \\ \hline \end{tabular}
\end{table}
Table 2: Mini-batching experiment. Test accuracy in % averaged over 15 splits
datasets mentioned above, this phenomenon remained consistent across all models. Notice that this phenomenon doesn't appear when we remove hyperedges randomly, in this case, as expected, the more hyperedges we remove, the more the performances decrease.

Rewiring ConnectivityIn this experiment, we preserve the original connectivity and investigate the influence of homophilic hyperedges on performance. To do so, we adjust the given connectivity in two different ways. The first strategy aims to unveil the full potential of homophily for each dataset by dividing the given hyperedges into fully homophilic ones based on the _node labels_. In contrast, the second strategy explores the possibility of splitting hyperedges based on their _initial node features_. More in detail, the hyperedge division results from applying multiple times \(k\)-means for each hyperedge \(e\), varying at each iteration the number of centroids \(m\) from \(2\) to \(\min(C,|e|)\); the elbow method is then used to determine the optimal hyperedge partitioning. It's not surprising that the "Label Based" strategy improves the performance for all datasets and models, as evident from Table 4. However, it's worth highlighting that the graph-based method CEGCN achieves results similar to HGNNs in this strategy. Additionally, only CEGCN, on average, performs better with the "k-means" strategy. These observations collectively suggest that connectivity preprocessing plays a crucial role, particularly for graph-based models. Applying "k-means" diminishes the distribution shift for MultiSetMixer.

## 6 Discussion

This section summarizes some key findings from our extensive evaluation and proposed homophily measure. Firstly, we showed that the proposed message passing formalization of the homophily measure enables the discovery of patterns and provides valuable insights into the dynamics of hypernetworks. Importantly, this approach can be extended to other definitions of homophily beyond labels. Furthermore, we showed that our MultiSetMixer model outperforms existing architectures in several scenarios. We also identified some common failure modes, which we attribute to the distribution shift introduced by the proposed mini-batching sampling scheme and the way message-passing propagates information. The experimental results demonstrate that certain benchmark datasets (Citeseer, Pubmed, 20Newsgroups) for hypergraph learning contain connectivity patterns that are not

\begin{table}
\begin{tabular}{c|c|c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{Method} & Topic & \multicolumn{1}{c|}{City} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c|}{Combined} & \multicolumn{1}{c}{Combined} & \multicolumn{1}{c}{Combined} \\ \cline{2-13}  & \(\Delta\)LeLeNet & **0.20\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** & **0.00\(\pm\)0.03** \\ \hline \multirow{2}{*}{AllGraphGraph} & \(\Delta\)LeNet & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** \\ \hline \multirow{2}{*}{AllGraphGraph} & \(\Delta\)LeNet & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** \\ \hline \multirow{2}{*}{AllGraph} & \(\Delta\)LeNet & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** \\ \hline \multirow{2}{*}{AllGraph} & \(\Delta\)LeNet & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** \\ \hline \multirow{2}{*}{AllGraph} & \(\Delta\)LeNet & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** \\ \hline \multirow{2}{*}{AllGraph} & \(\Delta\)LeNet & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.20\(\pm\)0.03** & **0.
effectively captured by HGNNs and are often overlooked. We show that the substantial performance gap between HGNNs and MLP for Cora, CORA-CA, and DBLP-CA is primarily attributed to patterns within a particular subset of connectivity, i.e., the largest hyperedge cardinalities have a stronger influence on performance. Finally, there is compelling evidence that connectivity can serve purposes beyond message propagation, such as acting as a tool for intentional distribution shift with mini-batching. We believe that the provided set of experiments and dynamic homophily figures are valuable tools to shape novel ideas for the hypergraph modeling research field.

## 7 Reproducibility

We include all the details about our experimental setting, including the choice of hyperparameters, the specifications of our machine and environment, the training/validation/test split, in Appendix F.1 and in Section 5. To ensure the reproducibility of our results, we will provide the source code along with the camera-ready version.
