Hypergraph Embedding Based on Random Walk
with Adjusted Transition Probabilities
Kazuya Nagasato1 , Satoshi Takabe1 , and Kazuyuki Shudo2
1

Tokyo Institute of Technology, Japan
2
Kyoto University, Japan

Abstract. In this paper, we consider embedding hypergraphs using random walks. By executing a random walk on a hypergraph and inputting
the resulting node sequence into a skip-gram used in natural language
processing, a vector representation that captures the graph structure canbe obtained. We propose a random walk method with adjustable transition probabilities for hypergraphs. As a result, we argue that it is possible
to embed graph features more appropriately. Experimental results showthat by tuning the parameters of the proposed method appropriately,
highly accurate results can be obtained even for large hypergraphs formachine learning tasks such as node label classiﬁcation.
Keywords: Hypergraph · Random walk · Embedding.

1

Introduction

Graphs are powerful mathematical models for quantitatively dealing with therelationships between people and things. For example, hyperlinks on the World
Wide Web, friend networks on social networking services, and the structureof chemical compounds are often represented mathematically by graphs, whichhave been studied actively in recent years. Among these, recent developments
in machine learning methods have attracted attention to embedding methods
that represent entire graphs or graph nodes as low-order vectors for graphs,
which are unstructured data, and have been applied to graph classiﬁcation, nodeclassiﬁcation, and prediction of edges acquired by new nodes.
On the other hand, there are relationships in real networks that interact asa group, and these relationships cannot be represented by ordinary graphs inwhich an edge connects two nodes. Therefore, a mathematical model called a
hypergraph, which is a generalization of graphs, is the target of research. Edges
in a hypergraph can contain an arbitrary number of nodes, and higher-orderrelationships between nodes can be captured. The problem of node embedding
for hypergraphs is important issue, and it is applied to recommendation systems,
etc.
And random walks are useful as a means of capturing node characteristics
of graphs and hypergraphs. A random walk on a graph transitions through thenodes that are connected to each other, and thus provides information on thesubgraphs of a node’s neighbors as a sequence of nodes.

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

2

Kazuya Nagasato, Satoshi Takabe, and Kazuyuki Shudo

In this paper, we propose a random walk method with adjustable transition
probabilities for hypergraphs and apply it to node embedding. Experimental
results on node label estimation show that the proposed method can achieve
similar estimation results to existing methods and reduce spatial computational
complexity.
The remainder of this paper is organized as follows. Section 2 describes related work on node embedding in graphs using random walks and related workon random walks on hypergraphs. Section 3 describes the prior knowledge in thispaper, and Section 4 describes the proposed method. In Section 5, we conduct
experiments on a real data set and conclude in Section 6.

2

Related work

In recent years, there has been much research on graph embedding. Spectral
embedding [5] is a method based on graph signal processing that produces avector representation so that the distance of vectors between neighboring nodes
is close. There have been many studies on graph neural networks [6], which arederived from this method. However, these methods use n × n adjacency matrices
as input, which are computationally expensive and not suitable for large data
sets.
DeepWalk [1] and node2vec [2] are methods for embedding graphs using
random walks. These methods obtain a vector representation of each node by
inputting a sequence of nodes obtained from a random walk into a skip-gram[4]. These methods are scalable and can perform embedding on large graphs,
especially when executed in parallel.
Carletti et al. [3] show that selecting adjacent nodes with equal probability
is not a wise decision for random walk transitions in hypergraphs because theconnections between nodes belonging to a hyperedge are often stronger than theconnections between consecutive individuals. Carletti et al. Therefore, Carletti etal. deﬁned transition probabilities for neighboring nodes based on their weights,
which are the number of nodes in the hyper-edge to which they belong minus
themselves. Random walks based on this deﬁnition can visit many high-order
hyperedges [3].
Chitra et al. deﬁned transition probabilities and formulated random walks
for hypergraphs with edge-dependent node weights [7]. Chitra et al. show thatwhen node weights are independent of edges in a hypergraph, a random walkon a hypergraph is equivalent to a random walk on a general weighted graphprojected onto a clique representation.
Gatta et al. proposed a hypergraph embedding method speciﬁcally for music
recommendation [19]. They deﬁned a hypergraph data model speciﬁc to music
recommendation, performs a random walk on the hypergraph, and then inputs
the resulting node sequence into a skip-gram to obtain a vector representation of
the nodes. The results show that their technique signiﬁcantly outperforms otherstate-of-the-art techniques, especially in scenarios where the cold-start problem
arise.

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

Title Suppressed Due to Excessive Length3

Preliminaries

3.1

Notation3

In this paper, for a undirected hypergraph H(V, E), let V = {1, ..., n} be the setof nodes and E = {E1 , ..., Em } be the set of hyperedges, where n is the numberof nodes and m is the number of hyperedges. Each Eα is a subset of V and isequivalent to a general graph, especially when |Eα | = 2 holds for any α.
let{
1 for i ∈ Eαeiα =0 otherwise(1)

be a hypergraph incidence matrix, the adjacency matrix A of a hypergraphis denoted by A = eeT and the hyperedge matrix C by C = eT e where e is amatrix representing the inclusion relationship between hyperedges and nodes,
Aij is the number of hyperedges shared by node i and node j, and Cαβ is thenumber of nodes included in Eα ∩ Eβ .
3.2Hypergraph projection

In a hypergraph, a hyperedge can contain any number of nodes, and thus has ahigh degree of freedom, making it diﬃcult to treat the hypergraph as it is. Therefore, there has been a lot of research using a method called Clique expansion,
which treats hypergraphs as general unweighted undirected graphs by representing hyperedges as complete graphs (cliques) in which all nodes have edges witheach other. However, a clique expansion is an irreversible transformation, which
results in a considerable loss of information as a hypergraph. Therefore, in thispaper, a random walk on an unweighted undirected graph, which is a cliqueexpansion of a hypergraph, is used as a comparison target.
3.3

Random walk and stationary distribution

In general, if we deﬁne a node in a graph as a state and deﬁne the transition
probability Tij from node i to node j, the transition of a node in the graphcan be regarded as a random walk. A stochastic process in which the next stateis determined only by the current state is called a Markov chain. An ergodic
Markov chain has a stationary distribution p and is obtained by solving
p = pT.

(2)

Equation (2) shows that the stationary distribution of the random walk isa right eigenvector corresponding to eigenvalue 1 of the transition probability
matrix T .

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

4

Kazuya Nagasato, Satoshi Takabe, and Kazuyuki Shudo

3.4

Skip-gram

We employ skip-gram as a node embedding method [4]. Skip-gram is a neural network that learns a function f : V → Rd to obtain a d-dimensional vector
representation of nodes, and was designed to maximize word co-occurrence probability in natural language processing. In this study, we perform a random walkon a hypergraph and use the resulting node sequence as input to obtain a vector
representation of the nodes that captures the relationships among the nodes.

4

Proposed method

In this chapter, we propose a random walk whose behavior can be controlled
by parameters. By setting parameters that match the dataset and executing arandom walk, a set of nodes that capture the graph structure can be obtained.
Then, by inputting the obtained nodes into a skip-gram, a vector representationof each node can be obtained.
4.1

Random walkH
If the current node is i, then the adjacent node j is assigned the weight kij(β)
expressed in Equation(3).
H
kij
(β) =

∑

(Cαα − 1)β eiα ejα(3)αThis deﬁnition is an extension of the previous study [3] by adding the parameter β as a power.
By normalizing so as to impose a uniform choice among the connected hyperedges, we get the expression for the transition probabilities
Tij = ∑

H
kij
(β)
.
H
l̸=i kil (β)(4)

Equation(4) is a function of β. Depending on the value of β, a random walkwith various behaviors is realized. β = 1 is equivalent to the previous study [3],and a behavior of visiting more high-order hyperedges is expected when β islarger than 1. When β is smaller, it is expected to visit more low-order hyperedges. When β = 0, adjacent nodes are visited with equal probability, which isequivalent to a random walk in a graph with a hyper-edge clique expansion.
From the above, our hypothesis in the proposed random walk can be summarized as follows.
– β > 1 Extracts many high-order hyperedge structures– β = 1 Equivalent to previous studies [3]– β < 1 Extracts many low-order hyperedge structures– β = 0 Equivalent to a hypergraph with clique expansion

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

Title Suppressed Due to Excessive Length

5

1

2

8~12
0

3

7
6
4

5

Fig. 1. Artiﬁcial hypergraphs. Each number represents a node number.

Also, when the hypergraph is ergodic for a given β, the random walk has astationary distribution
dH
j (β)
∑
p∞
=
j
H
j dj (β)
H
for all j = 1, ..., n, where dH
j (β) is deﬁned as dj (β) =

5

(5)
∑

H
l̸=j kjl (β).

ExperimentFirst, a simple artiﬁcial hypergraph is used to verify the behavior of the proposed
random walk. Then, we check the accuracy in the label estimation task when
the parameters are changed for the three datasets.

5.1

Transition probabilities in steady state

For the artiﬁcial hypergraph (Fig.1), the stationary distribution given by equation (5) was computed to verify the random walk behavior.
As a result, when β = −1, the probability of staying at high-order hyperedges
was lower and the probability of staying at hubs included in low-order hyperedges
was higher than in the random walk in the clique-expanded hypergraph. On theother hand, when β = 2, the probability of staying at a node included in ahigh-order hyperedge was higher than β = 1 in the previous study [3], and theprobability of staying at a hub included in a low-order hyperedge was lower(Fig.2).
Also, examining the probability of staying at each node, higher β induced
higher latent probabilities to higher order hyperedges, and vice versa (Fig.2).
These results indicate that our hypothesis is correct and that we can control
the random walk behavior by changing the parameter β.

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

6

Kazuya Nagasato, Satoshi Takabe, and Kazuyuki Shudo

Fig. 2. The left column shows the stationary transition probabilities for node 0 and
node 7 when the order of the hub is varied. ph and qh represent the stationary transition
probabilities for each β at node 0 and node 7, respectively. pc and qc represent thestationary transition probabilities for β = 0 (clique expansion) at node 0 and node 7,
respectively. The right column represents the stationary distribution when the degreeof node 0 is ﬁxed to 7. The red histograms are for each β, and the gray histograms
correspond to β = 0.

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

Title Suppressed Due to Excessive Length

7

Table 1. Hypergraphs used in our experiments.
datasetnm avg|Ei | max|Ei | labels
senate-bills
294 29,157 8.0
992
contact-primary-school 242 12,704 2.4
5
11
mathoverﬂow-answers 73,851 5,446 24.2
1,784 1,456

5.2

Node label estimation

In this section, we perform the label estimation task on real data. First, we
input the sequence of nodes obtained from the proposed random walk into askip-gram to obtain a vector representation of each node. Then, we performthe task of estimating labels from the vector representation of the nodes using
logistic regression. When executing the random walk, the transition probabilities
are calculated for each state sequentially, and the walk is performed without
explicitly describing the transition probability matrix. This signiﬁcantly reduces
the amount of spatial computation and allows experiments to be performed onlarge data sets.
The experimental procedure is as follows.
1. A sequence of nodes is obtained from each node in the hypergraph γ times,
each with a walk length t, by the proposed random walk.
2. The obtained node sequence is input into a skip-gram to obtain a d-dimensional
vector representation for each node.
3. The percentage of supervised data is set to 80% of the number of nodes, andlogistic regression is used to estimate the labels of the remaining nodes.
4. (1)∼(3) is repeated s times for each β to obtain the mean and standard errorof the F1 score.
We use the datasets [8]-[12] shown in Table 2. The senate-bills dataset is a hypergraph, where nodes are US Congresspersons and hyperedges are comprised of
the sponsor and co-sponsors of bills put forth in the Senate. The contact-priaryschool dataset represents students in proximity. Each hyperedge corresponds toa group of people that were all in proximity of one another at a given time,
based on data from sensors worn by students and teachers. Each node is labeled
as a teacher or the classroom to which the student belongs. The mathoverﬂowanswers dataset is a hypergraph where hyperedges are sets of questions answeredby users on Math Overﬂow. Nodes are labeled by the tags used in the questions,and nodes often have multiple labels.
We set γ ∈ {8, 16, 32, 64}, t = 20, d = 64, β ∈ {−1, 0, 1}, s = 20 for senatebills and contact-private-school datasets. For mathoverﬂow-answers we set γ ∈{8, 16}, t = 20, d = 128, β ∈ {−1, 0, 1}, s = 1. When β = 0, the embedding
technique is equal to the deepwalk in the clique expansion graph, and when
β = 1, the random walk is equal to the [3] in the previous study.
Fig.3 shows the experimental results for the three data sets. Fig.3 showsthat the F1 score varies depending on the value of β. In particular, for the
senate-bills dataset, setting β = −1 yields a high F1 score even with a small

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

Kazuya Nagasato, Satoshi Takabe, and Kazuyuki Shudo

senate-bills

micro F1 score

0.9

contact-primary-school

0.8
0.7
0.6
8

16 32
walks per node
micro F1 score

0.484

=-1
=0
=1
64

micro F1 score

8

0.96
0.95
0.94
8

16 32
walks per node

=-1
=0
=1
64

mathoverflow-answers
=-1
=0
=1

0.482
0.480
8

walks per node

16

Fig. 3. Experimental results with label estimation for each dataset. Error bars in theﬁgure represent standard errors.

number of samples, which is signiﬁcantly higher than that of the existing method
β = 0. The proposed method is also able to obtain results on the mathoverﬂowanswers dataset, which is a large dataset, due to its ability to reduce the spatial
computational complexity, and it correctly answers nearly half of the labels on
the 1, 456 label count.

5.3

Parameter dependence of F1 score

In this subsection, we show how the F1 score varies with the parameter β. For
two datasets, senate-bills and contact-primary-school, we conducted experiments
by moving the value of β from −3 to 3 and from −3 to 4 in 0.5 increments,
respectively (Fig.4). The range of values of β was kept around 0 based on the
hypothesis that random walks would not be able to extract relationships between
nodes in these cases because random walks would not be able to escape fromhigh-order hyperedges if β is too large or from low-order hyperedges if β is
too small. Fig.4 shows that senate-bills and contact-primary-school are convex
functions with maximum values around β = −0.5 and β = 1.5, respectively.
Therefore, it may be possible to optimize the results using the proposed method
by appropriately searching for the parameter β according to the data set.

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

0.90
0.85
0.80
0.75
0.70

senate-bills

2

0

9

contact-primary-school
micro F1 scoremicro F1 score

Title Suppressed Due to Excessive Length

2

0.96
0.95
2

0

2

4

Fig. 4. Dependence of β on F1 score. Error bars in the ﬁgure represent standard error.

6

Conclusion

In this paper, we propose a random walk with tunable transition probabilities
for hypergraphs and apply it to embedding.
By using an artiﬁcial hypergraph, we have conﬁrmed that the proposed random walk can freely exhibit behavior by changing the parameters according toour hypothesis. The proposed random walk can embed even large datasets by executing the random walk on the hypergraph, and it shows higher accuracy thanexisting methods in the label estimation task using real data. The parameters of
the proposed method may be optimized for each dataset, and more appropriate
embedding can be achieved by optimizing the parameters.

References
1. B. Perozzi, R. AI-Rfou, and S. Skiena “DeepWalk: Online learning of social representations”, In KDD, 2014, p. 701-710.
2. A. Grover and J. Leskovec “node2vec: Scalable feature learning for networks”, In
KDD. New York: ACM; 2016. p. 855–64
3. T. Carletti, F. Battiston, G. Cencetti and D. Fanelli “Random walks on hypergraphs”, Physical Review E, 101 ,2020 , p. 022308.
4. T. Mikolov, K. Chen, G. Corrado, and J. Dean. “Eﬃcient estimation of word representations in vector space”, In ICLR, 2013.
5. L. Tang and H. Liu. “Leveraging social media networks for classiﬁcation”, Data
Mining and Knowledge Discovery, 23(3):447–478, 2011.
6. Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, P.S. Yu. “A Comprehensive Survey
on Graph Neural Networks” , IEEE Trans. Neural Netw. Learn. Syst. 32 (1), 4–24.
7. U. Chitra and B. J Raphael. “Random walks on hypergraphs with edge-dependent
vertex weights”, In Proceedings of the 36th International Conference on Machine
Learning (ICML), 2019.
8. P S. Chodrow, N. Veldt and A R. Benson. “Generative hypergraph clustering: fromblockmodels to modularity” ,Science Advances, 2021.
9. J H. Fowler. “Connecting the Congress: A Study of Cosponsorship Networks” ,James H. Fowler.

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023

10Kazuya Nagasato, Satoshi Takabe, and Kazuyuki Shudo

10. J H. Fowler. “Legislative Cosponsorship Networks in the U.S. House and Senate” ,Social Networks, 2006.
11. J. Stehle, N. Voirin, A. Barrat, V. Vattuto, L. Isella, J. Pinton, M. Quaggiotto, W
V. Broeck, C. Regis, B. Lina and P. Vanhems. “High-Resolution Measurements ofFace-to-Face Contact Patterns in a Primary School” , PLOS ONE, 2011.
12. N. Veldt, A R. Benson and J. Kleinberg. “Minimizing Localized Ratio Cut Objectives in Hypergraphs” , Proceedings of the ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining (KDD), 2020.
13. M. Gjoka, M. Kurant, C. T. Butts, A. Markopoulou. “Walking in Facebook: A Case
Study of Unbiased Sampling of OSNs” , InProc. IEEE INFOCOM, 1–9.
14. K. Hayashi, S. G. Aksoy, C. H. Park and H. Park. “Hypergraph Random Walks,
Laplacians, and Clustering” , CIKM ’20, October 19–23, 2020, Virtual Event, Ireland.
15. D. Zhou, J. Huang, and B.Scholkopf. “Learning with Hypergraphs: Clustering,
Classiﬁcation, and Embedding” , In NIPS, 2007, 1601–1608.
16. Y. Feng, H. You, Z. Zhang, R. Ji, and Y. Gao. “Hypergraph neural networks” , In
AAAI, 2019, 3558–3565.
17. M. Belkin and P. Niyogi. “Laplacian eigenmaps for dimensionality reduction anddata representation” , Neural computation, 15(6):1373–1396, 2003.
18. P. Goyal and E. Ferrara. “Graph embedding techniques, applications, and performance: A survey” , Knowledge-Based Systems, vol. 151, pp.78–94, 2018.
19. V. L. Gatta, V.Moscato, M.Pennone, M.Postiglione, and G.Sperli. “Music recommendation via hypergraph embedding” , IEEE Transactions on Neural Networks
and Learning Systems, 2022.

Proc. 25th Int'l Conf. on Big Data Analytics and Knowledge Discovery(DaWaK 2023), August 2023