Diffusion Representation for Asymmetric Kernels via Magnetic Transform
Authors: Mingzhen He
FAN He
Ruikai Yang
Xiaolin Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: Asymmetric kernels
diffusion maps
magnetic transform
dimension reduction

Abstract: As a nonlinear dimension reduction technique, the diffusion map (DM) has been widely used. 
In DM, kernels play an important role for capturing the nonlinear relationship of data. However, only symmetric kernels can be used now, which prevents the use of DM in directed graphs, trophic networks, and other real-world scenarios where the intrinsic and extrinsic geometries in data are asymmetric. A promising technique is the magnetic transform which  converts an asymmetric matrix to a Hermitian one. However, we are facing essential problems, including how diffusion distance could be preserved and how divergence could be avoided during diffusion process. Via theoretical proof, we successfully establish a diffusion representation framework with the magnetic transform, named MagDM. The effectiveness and robustness for dealing data endowed with asymmetric proximity are demonstrated on three synthetic datasets and two trophic networks.

Diffusion Representation for Asymmetric Kernels via Magnetic Transform
Mingzhen He
Institute of Image Processing and Pattern Recognition Shanghai Jiao Tong University, Shanghai, China mingzhen mingzhen_he@sstuu. edu. cn
Fan He
Department of Electrical Engineering (ESAT-STADIUS) KU Leuven, Leuven, Belgium fan hwwesetttttt.... kuleuven. be
Ruikai Yang, Xiaolin Huang Institute of Image Processing and Pattern Recognition Shanghai Jiao Tong University, Shanghai, China {ruikai, yang, xiaolinhuang) edu, cn
Abstract
As a nonlinear dimension reduction technique, the diffusion map (DM) has been widely used. In DM, kernels play an important role for capturing the nonlinear rela- tionship of data. However, only symmetric kernels can be used now, which prevents the use of DM in directed graphs, trophic networks, and other real-world scenarios where the intrinsic and extrinsic geometries data are asymmetric. promising technique is the magnetic transform which converts an asymmetric matrix to a Hermitian one. However, we are facing essential problems, including how diffusion distance could be preserved and how divergence could be avoided during diffusion process. Via theoretical proof, we successfully establish a diffusion representation framework with the magnetic transform, named MagDM. The effectiveness and robustness for dealing data endowed with asymmetric proximity are demonstrated three synthetic datasets and two trophic networks.
Introduction
The diffusion map (DM) 1 2 3
and its variations 5 6, 7 are typical dimension reduction (DR) techniques that has been widely used in the signal processing [8], computer vision [9, and textual network embedding [TO]. DM a powerful method that embeds high-dimensional data into low-dimensional manifold while preserving diffusion distance, which helps describe meaningful geometric structures in data.
Kernels play significant role in DM and strongly impact the quality of DR, as they allow for the identification of nonlinear relationships and underlying structures data. real-world scenarios such directed graphs, trophic and social networks, the intrinsic and extrinsic geometries in data may be asymmetric, and asymmetric kernels [2] [3] are more suitable to depict asymmetric geometric structures. The advantages of integrating diffusion geometry and asymmetric kernels have been acknowledged by several researchers. [15] developed a framework to study function extension and approximation problems in the context of changing data and functions directed graphs.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, the diffusion distance and diffusion maps for vertices on directed graphs were unclear. [66] proposed the diffusion map for asymmetric kernels using the singular value decomposition, while the diffusion distance was calculated using only left singular vectors and right singular vectors were neglected, resulting the underutilization of asymmetric information.
The magnetic transform (MT) [17] is promising technique that transforms an asymmetric matrix into a Hermitian one, making suitable for working with asymmetry. MT has been successfully applied in DR techniques based on asymmetric adjacency matrices on directed graphs, such as Laplacian eigenmaps [8 Nevertheless, connecting DM and MT still faces essential problems. Previous works have analyzed MT based on finite adjacency matrices of directed graphs, while the studies of applying MT on asymmetric kernel functions, the corresponding integral operators. and diffusion geometry have not been explored, which obstructs the application of MT to DM. Additionally, MT transforms real-valued asymmetric kernels that describe the connectivity between data into complex-values function spaces, raising the question of how to define the diffusion distance and diffusion maps in those complex-valle -valudd function spaces. is also crucial to investigate how to prevent divergence during the diffusion process when are working in complex field. To address these challenges, we propose a novel diffusion representation framework with the magnetic transform, named MagDM, that enables the use of asymmetric kernels.
The contributions of this paper are as follows:
We develop diffusion representation framework for data endowed with asymmetric kernels using the magnetic transform, where the corresponding diffusion distance and diffusion maps are defined.
We explore integral operators of MT, whose compactness is established if the asymmetric kernels are Hilbert-Schmidt kernels, helping us determine the range of usable asymmetric kernels.
We prove an important property that the spectral radius of the proposed integral operator is 1, which ensures that MagDM will not diverge during the diffusion process.
We present experiments that demonstrate the effectiveness and robustness of the MagDM algorithm on three synthetic datasets and two real-world trophic networks.
2 Related works
Dimension reduction techniques [20) 21 22 have been extensively studied over the past few decades. Previous research has focused mainly on symmetric and positive semi-definite proximity. However, in recent years, researchers have become aware of benefits of asymmetric proximity and have proposed several insightful theories and algorithms. These methods fall into one of the following families.
Singular value decomposition. [5] presented a polar decomposition for the construction of kernels to embed directed graphs into manifolds study harmonic analysis of functions on directed graphs However, the diffusion representation for asymmetric kernels under this framework was not discussed. [6 utilized the singular value decomposition (SVD) for asymmetric kernels, and defined the diffusion distance for asymmetric kernels. There was theoretical shortcoming in which diffusion distance was calculated using only left singular vectors and right singular vectors were neglected, meaning that only out-going proximity was considered, which resulted in the underutilization of asymmetric information. Although SVD embeds asymmetric kernels as an inner product of two feature mappings, it does not directly reflect the directional information, i.e., the skew-symmetric part, which is more important in asymmetric scenarios, in the feature mappings.
Magnetic Laplacian. The magnetic Laplacian [17] was originally derived from a quantum mechani- cal Hamiltonian of a particle under magnetic flux. [8 19 23 utilized magnetic Laplacian to embed asymmetric proximity as a complex-valuee feature mapping, where symmetric and -kew-symmetric parts were successfully separated into modules and phases, respectively. Magnetic Laplacian trans- formed an asymmetric matrix to a normalized Hermitian matrix H whose eigenvalues are contained within the interval [-1, 1] 24). In Laplacian-typed methods, the feature spaces turned to be the (numerical) null spaces of I H 25). in which only the positive part of the spectrum of H was used. However, the negative part of the spectrum also contains meaningful information which was ignored in previous works [18 19, resulting in inadequate use of asymmetric information.
2

---

3 Diffusion representation and diffusion distance
In this section, we briefly review the diffusion map. Assume (X, (1) is o-finite measure space where X C RM is dataset and is an associated measure which is non-degenerate on X. Let K. X x X + R+ be non-negative symmetric kemel which measures the local connectivity between two samples æ, E X. And the Markov kernel is defined as follows,
K(x, y)
p( = vv(x) /v(y)
where v(x) is the volume form defined as v(x) - Jx K(x, y)du(y). Assuming that the volume form does not vanish and ( x X, @ μ1) is a square integrable measurable function, then the operator A (2,, + L2 p)) given by (())(x)
Jx p(x, () is compact and self-adjoint. We can write p(æ. v) EnEn An (z) (3) according to the spectral theorem, where {)n, Φn } is the spectral decomposition of the operator A. For any positive natural number t 4. the diffusion distance at time between two samples æ, y can be defined as follows,
(x, 3) llp( (y. (L
where p' the kernel of the powers of the integral operator A. Note that the diffusion distance D is an average over all paths in time t connecting x to resulting in diffusion distance that is robust noise perturbation. The diffusion distance can be reformulated as follows.
D' y)
Σ X (on -n(())²
The expression above enables dimension reduction in diffusion geometry, which is also known as diffusion maps. The dataset with the kernel structure p can be embedded into a lower dimensional space e X + R& as follows.
(x)) = (1)), (a))(()),
{,da(x))
Diffusion representation for asymmetric kernels
The definition 2 of the diffusion distance assumes symmetry, making it unsuitable for with asymmetric kernels. To overcome this limitation, we introduce the magnetic transform in this section. With this transformation, we propose the MagDM algorithm for asymmetric kernels.
4.1 Magnetic transform
Assume that we have set data X C RM, and a non-negative distribution μ defined on this set. Let K. X X + R. be non-negative kernel that measures the directed connectivity between samples in X. Note that X. does not need to be symmetric. The classical diffusion distance (2) fails to measure asymmetric distance from both samples as sources. To handle asymmetry, the magnetic transform is defined to transform an asymmetric kernel new kernel with conjugate symmetry.
y because it only uses half of asymmetric information, treating
Suppose an asymmetric kernel IC: X x X + IR,, a Hilbert-Schmidt kernel, K E L'((XXX,88)) The Magnetic transform kernel 7/44) of K. is defined by
H (x. y) K( y) K(y,
exp (i2mq (K(y, {(x,)))
where E R is a scaling parameter and i V-T. The kernel H(6) is conjugate symmetric, meaning that (((0) (x. y) (v, The modulus and phase terms of H((0) capture the symmetric and skew-symmetric parts of information in K, respectively.
Proposition 1. Suppose a real-valued asymmetric kernel K: + R4 is Hillert-Schhiid kernel K. E (2 x X, @ u) where (X, p)) is a-finite measure space and X C R Then, the magnetic transform kernel H X x X C is Filbeet-Schhidt kernel.

---

The proof is shown in Appendix A The aforementioned proposition allows to define a Hilber- Schmidt kernel H()), which enables us to identify the range of usable asymmetric kemelss Then, we can define the corresponding Hilber-Schmidt operator that is also compact operator [26 in the diffusion process.
4.2 Diffusion maps and diffusion distance
The Markov kernel p(a, v. E (2 X, (1 (1) for the magnetic transform kernel H(91 is defined
by
y.9) = H y) where m(x) = 1/2 fx (K(x,, y) Kly x) duy( is the volume form of the symmetric term of K. Assuming that m does not vanish on X, the operator T(4) p2), + L²(X, (1) given by
(4)
Vm(x) mmly)
T()) J pl.r, y ())(()))))))
(5)
compact and self-adjoint. We can decompose p(ar, y. 9) EnEN X Sh (z)) (y) according to the spectral theorem, where (119) ( is the spectral decomposition of the operator T(a), Next, we analyze the spectrum of the integral operator (5).
Proposition 2. Given asymmetric kernel satisfying Proposition the eigenvalues (x of the
Hillerr--Shmiitt operator defined by (5) are real and bounded by X E [-1,1]]
The proof is provided in Appendix B Because the operator is self-adjoint, its eigenvalues real
numbers and eigenfunctions are complex functions. According Proposition as diffusion time E N
increases, small eigenvalues converge to zero, which avoids divergence of MagDM during diffusion process. For any time t, MagDM defines the diffusion distance for the asymmetric kernel by
(' y) ||p" (z, p' (og.:,4)llaar .))
(6)
Running along the diffusion process for asymmetric kernels is equivalent to computing the powers of the operator T(4), The diffusion distance (6) is functional weighted 1,2 distance between complex- valued proximities of two samples, thus it is also robust to noise perturbation. Both symmetry and skew-symmetry are embedded into the diffusion distance, which reflects the asymmetric geometry in data. (6) can be rewritten as the following,
D' D' v)
(4) (An
2
p0 (xz) - 2a (y)
(n)
BEN
Denote the eigenvalues in descending order as: 1 approximated by (x y) with a preset accuracy E (0, 1) and finite terms as follows,
11 > |2 ... 2 0. (1 y) can be
Σ
(Al
2t (g) on (x) 0 (n) (w)
+S$(AA))
where (o, = max E N, : | > ()) We define the diffusion map for asymmetric kernels which embeds data endowed with asymmetric kernels lower dimensional space follows,
(0) (x) = (A (10) (x),
(A
s(8,1) (x)
Proposition 3. The diffusion map vi-(() embeds the data endowed with an asymmetric kernel into lower dimensional space (36.,)) then the Euclidean distance in this space is equal the diffusion distance D/ y).
(())))(()) - -54.1)))))))))))))))) (z) = (x y)
When the fed kernel function is symmetric, the proposed method reverts back the classical diffusion map. This is because exp (12mq (XC(x, y) K(y, =))) becomes exp (i2mq- - 0) = 1, and H(1) (x. y) K(x y). The implementation details of this algorithm can be found in Appendix D

---

4.3 Selection of the scaling parameter 4-
The sealing parameter q is a key parameter for embedding the kkew-symmetric part of an asymmetric kernel, which directly affects the representation ability. The selection of q has been previously discussed for unweighted directed graphs [8] 23] and in the context of graph signal processing 27 However, the selection of y for asymmetric kernel functions has not been addressed so far. Here, we propose a simple and practical method for selecting q for asymmetric kernels. In (3), the skew-symmetry is embedded in the phase, which is periodic function controlled by q. To select suitable value for g, we recommend selecting a period that covers the extent of the skew-symmetric component, which means that 7 should be less than where ā := yu [K(x,, y) K(y, then we have q 0.5/T. In practice, the size of the data. Then @ is given by ā = max,
have access the Gram matrix K RNXN where N is N ==1 K Kjg,, and the selection of q is
0. 9 max N (== Kij - K
Experiments
In this section, we demonstrate the capability of the MagDM method to extract asymmetric in- formation on three synthetic and two real-world trophic datasets. Additionally, we compare our method with five other methods: diffusion maps (DM) (1, kernel principal component analysis (KPCA) (28] asymmetric diffusion maps (ADM) [16), magnetic eigenmaps (ME) [88, and Markov normalized magnetic eigenmaps (MME) [1]]. The experiments were conducted using MATLAB
on PC with an Intel 17-10700K CPU (3.8GHz) and 32GB of memory. Codes are available at
https://gitte com wtt.bb..cco///exeeee21l21 Aww.:eeeeeeeeeeeellel
5.1 Artificial networks
We begin by assessing the ability extract asymmetric information. In this experiment, we create an artificial network following (29). The network consists of three groups (A, B, and C), and we establish two types of flows (forward and backward) between them, which helps us construct an adjacency matrix to represent connections among nodes. Each node has 50% chance of being connected node in own group. Furthermore, each node has a 50% chance being connected to node in another group in the direction of the forward flow (i.e., interconnections from A to B, from to C, and from C to A). Additionally, there is another type of interconnection in the direction of the backward flow with a probability of P. By adjusting the backward probability P. we can control the running flow. An illustration of this artificial network shown in Appendix F.
In this experiment, we choose 5 probabilities for the backward running flow, P & (0, 0.2, 0.5, 0.8, 1). As P increases, the level of asymmetric information first decreases and then increases. Due to the fact that phases of cigenvectors contain most of asymmetric information [88 19.. Fig. reports phases of the ME, MME and MagDM methods, and shows their capability of extracting asymmetric information. All the three methods distinguish three groups when the probability of backward flow P O. As we increase the value of P. the level of asymmetric information decreases. This is reflected in the fact that the distance between samples in the same group becomes larger, as seen in the second row of Fig. ! When P 0.5, the contribution of the forward and backward flows to adjacency connections is statistically the same, resulting in the disappearance of asymmetric information and the mixing of samples from different groups. As P continues to increase, asymmetric information gradually strengthens again, forming a scenario where the backward flow is stronger than the forward flow. The last two rows of Figure demonstrate that the MagDM algorithm effectively distinguishes between the three groups, whereas the ME and MME algorithms are currently unable to differentiate between them, which illustrates the stronger robustness of our method.
The running flow of the second artificial network comprises four groups (A, B, C, and D) following 30 The visualization of this directed graph can be seen in Appendix F22 The structure of the flow is apparent, with Groups A and D serving as out-come and in-come flows, while Groups B and C function as intermediaries. For instance, Group A predominantly generates out-coming links with a high probability (strong flow), and only a few in-coming links from Group D are produced by weak flow with a low probability. Besides, each node has a high probability of being connected to node in the same group.
5

---

phase d'
MME phase (
0.000
MagDM phase e*>
m22
m/2
P=0
0
-x/2
xx/2
-r/2
m/2
-2/2
0
s/2
-s12
m22
ME phase 11
phase d1
MagDM phase o
phase (0)
MME phase (
CECD 0300
MagDM phase e
m2
P=0.2
m/2
x2/
-x/2
s/2
-x/2
0
x/2
-e12
m22
phase o1
phase of
MagDM phase o
MagDM phase fol
phase (0)
MME phase (c)
x/2
P=0.5
0
mm/2
-0.06
-0.04
-0.02
m2
ME phase [q]l
MME phase 11
MagDM phase (9)
MagDM phase fal
phase 10
MME phase 07
m/2
000
P=0.8
-m/2
mm/
m2
-0.5
0.5
xx/2
x/2
2x/2
ME phase 41
phase o
MagDM phase (9)
MagDM phase 2
ME phase 10
MME phase
m/2
x/2
P=1
0-
-m/2
m//
x2
2
2
-0.6
-0.4
-.2
-0.01
-0.005
0
0.005
0.01
m22
ME phase (q]
MME phase o1
MagDM phase (9)
Figure 1: The capability of three methods (left: ME, middle: MME, right: MagDM) to extract asym- metric information on the three groups colored by red, green, and blue, with q == 1/4. Asymmetry in the data is generated by the asymmetric interconnection among the groups, and phases of the three methods are reported to distinguish them. The forward flow probability fixed at 0.5, while the backward flow probability is chosen from the {0, 0.2, 0.5, 0.8, 1}.
Fig. 2 presents the visualization results of six different methods. The DM and KPCA methods yield poor clustering performance as they do not consider asymmetric information. In contrast, the
ADM method distinguishes four groups, although it does illustrate directed information. The ME method distinguishes groups along the phase axes, but is unable to differentiate between the four groups when considering the real and imaginary parts of the second eigenvector. The MME method has an overlap between Groups A and B along the phase axes, and the second eigenvector embeds Group within the other groups, making difficult to distinguish from the rest. MagDM produces a compact and almost linearly separable clustering not only along the phase axes but also in the first and second eigenvectors, shown in the bottom row of Fig. 2
5.2 Synthetic data using asymmetric kernel
Next, we assume that the dataset is a set of 300 points distributed along the Möbius strip. The parametrie form of the Möbius strip is defined by
U " zuu, v) (1 cos
cos u, y(u, v) (1 + V cos u sin u. 2(u,u) sin 2
2 2

---

2.
0.05
ADM de
KPCA
DM
0.14
0.13
0.12
0.11
2
2
61
d
KPCA 0
phase d
x/2
ME 1m
0.1
e
2/2
-0.1
-0.2
phase (
61
MME phase 00
x/2
0.2
0.1
MME Im
-0.02
MME lm
m/2
.0.03
-015 -011
0.16
-0.1
0.2
MME phase (i)
MME Re (6
MME Re (n]
Magpи phase al
MagDM Im 00
MagDM Im 6
0.1
x/2
0.05
0-
-2
x2
00.1
-0.05
0
0.05
0.1
-0.05
0.05
0.1
MagDM phase of
MagDM Re o
MagDM Re a
Figure 2: The capability of six methods to extract asymmetric geometry on the four groups colored by
red, green, blue, and orange, with g 1/3. The first row shows the results of DM, ADM, and KPCA, while the remaining rows show the results of ME, MME, and MagDM. For better illustration, the real and imaginary parts of first non-trivial eigenvectors are reported, in addition to the phases.
where 0 S u < 2 and -0.5 < < 0.5. The dataset is with color drift in the counterelockwise We define an asymmetric kernel follows,
direction on the x-y plane, please see in Appendix F3
max ||
y 0},
Lay 2 0 Lxy <
K(x, y)
max(0.2p - || 311,,00
where Lay is the angle between æt y on the x-y plane. The asymmetric kernel is composed of two truncated & kernels 31,, which measures asymmetric similarity based on angles between æ and y.
0.02
20
0.01
10
COC
ADM
KPCA
C0D
00.01
-10
-20
00.02
-0.05
-0. 1.058
-0.056
-60
40
-20
-10
DM d
ADM
6
KPCA d
d0)
x/
MagDM phasa
x/2
-2/2
mn/2
x/2
-10
-14
0
1/4
3nid phase g(8)
n/2
ME phase
MME phase
x10
MagDM
Figure 3: Dimension reduction results of six methods (DM, ADM. KPCA, ME, MME, and MagDM) on the Möbius strip which is endowed with the asymmetric kernel (9) and colored by the angle. 5 and g 0.09.
7

---

The dimension reduction results are illustrated in Fig. DM and KPCA fail to distinguish the asymmetric geometry. as they only learn the symmetric part of ( Although the ADM method contains the color drift after reducing the dimension of data, there is still sharp turn on the green part of the data, which is not desired. The ME method distinguishes the color drift only on the phase of the first eigenvector, while the MME method fails to provide clear directed information. Notably, the MagDM method provides a clear and smooth result along both two phase axes.
5.3 Trophic networks
0.2
DM d7
ADM 02
oz
KPCA
-0.2
00
5
0,2
0.4
-10
-5
0
6
DM 11
ADM 01
KPCA 1
ME phase (9)
ME Im (0
x/2
0.2
ME Im
-0.1
-x/2
xx/2
-0.2
0.2
-0.2
0.2
ME phase (e]
Re
[a]
42
MME phase # (0)
0.02
0.04
MME Im (9)
MME Im 6q/
x/2
0.02
x2/2
-0.02
-0.02
0.5
MME phase $1
[q)
MME Re ((9)
MME Re (49)
MagDM phase (t)
22
MagDM Im (4)
0.2
MM Im
22/2
-0.2
m2
n/2
-0.3
-0.2
0.1
0 0.1
-0.2
0.2
MagDM phase (
MagDM Re (q)
MagDM Re 02
(q)
Figure 4: The dimension reduction of the Florida network is shown using six methods (DM, ADM, KPCA, ME, MME, and MagDM), with q 0.045. Florida is composed of four categories consisting of different elements: Producers (green nodes), Consumers (red and brown nodes), Organic Matters (blue and turquoise blue nodes), and one Decomposer (purple node). The fow-dimensional embed- dings using the different methods are visually compared.
To further illustrate the concept, we have chosen two specific real-world trophic networks from the Pajek dataset="] the Mondego network [32, which records trophic exchanges at the Mondego estuary, and the Florida network [33] which records trophic exchanges Florida Bay during the wet season.
Based on the roles of the nodes in ecosystems, we classify them into different categories, as depicted in Appendix F.4, The different categories in the trophic networks consist of Producers, which generate their own food through photosynthesis or chemosynthesis (green nodes); Consumers, consisting of both low-level consumers (brown nodes) and high-level consumers (red nodes) that feed on other organisms for energy; and Organic Matters (blue and turquoise blue nodes). As for the Florida network, there is also Decomposer that break down dead or decaying organic matter (purple node). The adjacency matrix W denotes the intensity of trophic exchanges and the asymmetric kernel matrix
http:///aaaaaootttttoo//a//aaaee uni htw.aa/www.......aaaaaaaaooooooa

---

for the trophic networks are defined by,
Ki log2 W1) 1).
The dimension reduction results for two trophic networks are presented in Figs. and 5 For the Florida network, MagDM outperforms other methods, shown in Fig. All DM, ADM, and KPCA methods fail to differentiate between different categories. On the phases results of the remaining three methods, ME and MME are unable extract clear asymmetric information, while MagDM almost distinguishes between producers and consumers. For better illustration, the real and imaginary parts of the first two non-trivial eigenvectors of ME, MME, and MagDM are visually compared. It is observed that all three methods fail to distinguish categories on the first eigenvector axis, but on the second eigenvector axis, MagDM not only differentiates the categories but also tightly clusters high-level consumers together, resulting in clear classification structure. Similar results are obtained for the Mondego network. These findings demonstrate that MagDM is promising approach for dealing with asymmetric proximity in trophic networks.
0
KPCA 02
0.2
DM
ADM
-10
22
-0.2
-20
0.2
0.4
-15
-10
-5
2
DM
d
ADM
KPCA $
ME phose 62
m/
ME Im d
0.2
%
-0.1
00
m2/2
00
ME
-0.2
-0.2
-0.3
x/2
0.2
0.4
-0.5
0.5
ME phase [4/
ME Re (4)
ME Re (4)
MME phase (0)
0.04
MME im (0)
x/2
MME Im of
G
0.02
-0.05
-x/2
06
-0.1
3.2
-0.6
-0.4
-0.2
0.4
MME phase (
MME Re
91
MME Re 02
MagDM phase 22
MagDM Im (0)
0.2
MagDM Im (0)
m/2
0-
xx/2
-0.2
-0.2g
mm/2
x/2
-0.4
-0.2
-0.4
-0.2
0.2
MagDM phase (g)
MagDM Re s(1))
MagDM Re (g)
Figure 5: The dimension reduction of the Mondego network is shown using six methods (DM, ADM, KPCA, ME, MME, and MagDM), with q = 0.04. Mondego is composed of three categories consisting of different elements: Producers (green nodes), Consumers (red and brown nodes), and Organic Matters (blue and turquoise blue nodes). The low-dimensional embeddings using the different methods are visually compared.
Conclusion
In this paper, we have presented novel framework named MagDM for representing data endowed with asymmetric kernels using the magnetic transform within the context of diffusion maps. We introduced the integral operator with the proposed magnetic transform kernel and investigated several

---

of its properties, including compactness, spectral decomposition, and spectral radius. Moreover, we proposed a diffusion distance that embeds asymmetric kemelss into the diffusion map complex- valued function spaces, allowing the identification and analysis of asymmetric geometries and patterns in data. This could lead to new insights into the structure and properties of asymmetric kernels, potentially leading to new applications or algorithmic improvements. Experiments demonstrated the effectiveness and robustness of MagDM on three synthetic datasets and two trophic networks.
There are several interesting avenues for future work in the study of asymmetric kernels. In terms of methodology, exploring variants of other dimension reduction schemes for asymmetric kernels such as MDS [34] and Isomap [35] would be appealing. In terms of theory, studying geometrie harmonics of functions with magnetic transform kernels could provide deeper understanding of the intrinsic and extrinsic geometries in data. In terms of applications, using MagDM as feature mappings for classification and regression tasks could be particularly useful for problems involving asymmetric proximity, such social networks and commodity trading between economies.
Broader impacts. The proposed MagDM method described in this paper is expected to have significantly different impacts on society compared to other dimension reduction techniques.
Acknowledgmentt
This work was partially supported by National Natural Science Foundation of China (62376155), Research Program of Shanghai Municipal Science and Technology Committee (22511 105600), and Shanghai Municipal Science and Technology Major Project (2021SHZDZZ01022)
References
[1] Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
[2] Ronald R Coifman and Matthew J Him. Diffusion maps for changing data. Applied and computational harmonic analysis, 36(1):79-107, 2014.
[3] Stéphane S Lafon. Diffusion maps and geometric harmonics. Yale University, 2004.
[4] Amit Singer and H-T Wu. Vector diffusion maps and the connection laplacian. Communications on pure and applied mathematies, 656)):1067-1144, 2012.
[5] Yifeng Fan and Zhizhen Zhao. Multi-frequency vector diffusion maps. In International Conference on Muchine Leurning, pages 1843-1852. PMLR, 2019.
[6] Gabriele Cesa, Arash Behboodi, Taco Cohen, and Max Welling. On the symmetries of the synchronization problem in cryo-em: Multi Multi-frequency vector diffusion maps on the projective plane. In Advances Neural Information Processing Systems, volume 35, pages 5446 54588, 2022.
[7] Harbir Antil, Tyrus Berry, and John Harlim. Fractional diffusion maps. Applied and Computa- tional Harmonic Analysis. 54:145-175. 2021.
[8] Ronen Talmon, Israel Cohen, Sharon Gannot, and Ronald R Coifman. Diffusion maps for signal processing: A deeper look at manifold-learning techniques based on kernels and graphs. IEEE signal processing magazine, 30(4):75-86, 2013.
[9] Deepti Pachauri, Risi Kondor, Gautam Sargur, and Vikas Singh. Permutation diffusion maps (pdm) with application to the image association problem in computer vision. In Proceedings of the 27th International Conference Neural Information Processing Systems Volume 1, page 541-549. MIT Press, 2014.
[10] Xinyuan Zhang, Yitong Li, Dinghan Shen, and Lawrence Carin. Diffusson maps for textual network embedding. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 7598-7608, 2018.
[11] Mark Mackenzie and A Kiet Tieu. Asymmetric kernel regression. IEEE Transactions on Neural Networks, 15(2):276-22) 282, 2004.
10

---

[12] Silvia L Pintea, Jan C van Gemert, and Amold WM Smeulders, Asymmetric kemel in Gaussian processes for learning target variance. Pattern Recognition Letters, 108:70-77, 2018.
[13] Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. FL-NTK: neural tangent kernel-based framework for federated learning analysis. In International Conference Machine Learning, pages 4423 4434. PMLR, 2021.
[14] Mingzhen He, Fan He, Lei Shi, Xiaolin Huang, and Johan A.K. Suykens. Learning with asymmetric kernels: Least squares and feature interpretation. IEEE Transactions on Puttern Analysis and Machine Intelligence, pages 1-12, 2023.
[15] Hrushikesh N Mhaskar. A unified framework for harmonic analysis of functions directed graphs and changing data. Applied and Computational Harmonic Analysis, 14(3):611-644 2018.
[16] Alvaro Almeida Gomez, António Silva Neto, and Jorge P Zubelli. Diffusion representation for asymmetric kernels. Applied Numerical Mathematics, 166:208-226, 2021.
[17] Elliott H. Lieb and Michael Loss. Fluxes, laplacians, and kasteleyn's 's theorem. Duke Mathemat- ical Journal, 712233377-63, 1993.
[18] Michaël Fanuel, Carlos M Alaíz, Ángela Fernández, and Johan A. K. Suykens. Magnetic eigenmaps for the visualization of directed networks. Applied and Computational Harmonic Analysis, (4(1):189-199) 2018.
[19] Alexander Cloninger. A note on markov normalized magnetic eigenmaps. Applied and Computational Harmonic Analysis, 43(2):370-38., 2017.
[20] Hervé Abdi and Lynne J Williams. Principal component analysis. Wiley interdisciplinary reviews: compulational statistics, 2(4))433-459, 2010.
[21] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2333-255 23222 2000.
[22] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001.
[23] Michaël Fanuel, Carlos M Alaiz, and Johan A. K. Suykens. Magnetic eigenmaps for community detection in directed networks. Physical Review E, (5(2))022302, 2017.
[24] X Zhang, Y He, N Brugnone, M Perlmutter, and M Him. Magnet: A neural network for directed graphs. Advances in Neural Information Processing Systems. 34:27003-27015, 2021.
[25] Jianzhong Wang. Mathematical analysis on out-of-sample extensions. International Journal of Wavelets, Multiresolution and Information Processing, 16(05): 2018.
[26] John B Conway. A course in functional analysis, volume 96. Springer, 2019.
[27] Satoshi Furutani, Toshiki Shibahara, Mitsuaki Akiyama. Kunio Hato, and Masaki Aida. Graph signal processing for directed graphs based on the hermitian laplacian. In Machine Learning and Knowledge Discovery Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16-20, 2019, Proceedings, Part I, pages 447-463. Springer, 2020.
[28] Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Kernel principal component analysis. In Artificial Neural Networks-ICANN' 7th International Conference Lausanne, Switzerland, October 8-10, 1997 Proceeedings, pages 583-588, Springer, 2005.
[29] Andrea Lancichinetti and Santo Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1):016118, 2009.
[30] Elizabeth Leicht and Mark Newman. Community structure in directed networks. Physical review letters, 100(11):118700 2008.

---

[31] Xiaolin Huang, Johan A. K. Suykens, Shuning Wang. Joachim Hornegger and Andreas Maier. Classification with truncated & distance kernel. IEEE transactions on neural networks and learning systems, (9(5):2025-2033) 2017.
[32] R Pinto, J Patrício, F Salas, JM Neto, and JC Marques. Mondego catchment goods and services assessment under the millennium ecosystem assessment scope. Felicita Scapini. Jean-Mare Boffa, Louis F. Cassar, page 279, 2009.
[33] Robert E Ulanowicz and Donald L DeAngelis. Network analysis of trophic dynamics in south florida ecosystems. US Geological Survey Program on the South Florida Ecosystem, page 1 11, 1999.
[34] J Douglas Carroll and Phipps Arabie. Multidimensional scaling. Measurement, judgment and decision making, pages 179-250, 1998.
[35] Mukund Balasubramanian and Eric I. Schwartz. The isomap algorithm and topological stability, Science, 295(5552);7-7,003 2002.
[36] Kösaku Yosida. Functional analysis. Springer Science & Business Media, 2012.
[37] Jihun Hamm and Daniel D Lee. Grassmann discriminant analysis: a unifying view on subspace- based learning. In Proceedings of the 25th international conference on Machine learning, pages 376-383, 2008.
12

---

A The proof of Proposition [
Proof. Because a Hilbert-Schmidt kernel, we have Jfxxx [K(,, أ) dd(())d(()) <c. Then,
Ilxx H (x. du(z)d))))
K(x, 3) + ((y ?dp(z)dp(u)
2
$ / f 2 (IK(z, v) KKy. du)x)())))
1
/ / K(x,, ()) du(ar)dp(() <0.
It holds that the symbol " <" in the third row of the above equation because of the Cauchy-Schware in- equality. The Cauchy-Schware inequality states that Va,, by E R. i = L, k. then (Ein axb;) < (E ( (Ein 62). Then, we have (((.)) + K(g.a) I (1 + #)- (1AC(z y) + [K(y,
2
and measure j is non-negative. Thus, symbol " s" the third row holds. We finish the proof.
B The proof of Proposition 2
Proof. The associated kernel μ(x, y. of the operator 5 is a Hermitian kernel, i.e., ,l( y.9) = uly, q). then the eigenvalues of (5) are real and the spectral radius is equal to the operator norm R(p) = [())) 36 Let S E 1.2 (X, nd), we have
(T(() f. / (ll....oll(/l)/mmddmdodll
| (Z) v) Vmly) /m(x)
f(y) f(z)
dr(2)dd(u)-
If we apply the Cauchy-Schwarz inequality as follows,
1 H(0) (xx, y)
f(y) du(v)) s (((0) (2 (x.,
$ ( (7(6)) (2, v) w))ddddll (ulue))
f(y)
Panlu))
mmly)
/m(y)
(7(09) (2. v) (plaulee)
$ ( | (x, 8)
|f()) du(v)
1
<
m(y)
S(x, m)dn(())
(J S(æ, v)
(f(e)) du(ي)) mly)
where S(x,y) |7(9) (x. v) = [ y) + K(y, ) The asymmetric kernel IC is non-negative, thus 5(x. v) 1/2 (K((x, 8) + K(y,x)) x)) Then have
1/ (1,) y) f(y) )m(e)) S (Jx s(o. 1 (J S(x, y) m
[5(1)1 m(y)
du(v)) 1/2
=Vm(z) ( S(xr v) ((())12
$
du(s))
m(y)
Consequently,
f.f) 5 / |s(0)) (fx S(x, 8) |f(2)12
1 du(z) du(x).
mly)
13

---

We can apply the Cauchy-Schward inequality again,
(T = 11/11 Jx.. S(a, v) m(y)
((()) du(r)du((r) $
=I1fI| (f
If(e))?
(Jx S(x, ((xx))) du(r)) m())
-ISI (Sx
[S())l
m(v)dd(()) $ 1f
m(y)
can be noticed that the operator norm finish the proof.
|| = 1. Therefore, the spectral radius R(p) = 1. We
C Selection of the scaling parameter q.
As illustrated in Fig. Ape. suggest choosing period that encompasses the range of the skew-symmetric component, I.e., a should be less than π, where is defined as follows,
sup [K(ar, y) K(y, .>)
m.yEX
and the period of the phase function is T 2mq
1/g. Thus, we have
27
+
<<
20
Im
28
2m
-
Figure Ape.1: simple illustration for selecting q-
14

---

D Algorithm
To apply MagDM, we require a dataset and an asymmetric kernel or an asymmetric Gram matrix, as well as the scaling parameter and the desired accuracy. Algorithm ouullines the MagDM procedure.
Algorithm 1 MagDM for asymmetric kernels
Input: The Gram matrix K of dataset X endowed with an asymmetric kernel K, the scaling parameter and a preset accuracy 8.
Output: The diffusion map gi-((a) of X.
1: Calculate the Hermitian Gram matrix of the asymmetric Gram matrix K by 3 and (4)
2: Calculate the t-powers kernel matrix H
3: Run eigen-decomposition of H' and denote its eigen- as {ARl on
4: s(,,t) +- nn N: (A! 8'A
5: Return the diffusion map z by (8)
Limitations, Researchers should note that the MagDM method proposed in this paper has some limitations. One such limitation is its dependence on the choice of asymmetric kernel functions, which can impact its performance, Additionally, MagDM may be computationally expensive for large datasets, it requires ((N2) memory and ((N3) computational complexity to derive the spectral decomposition. However, this limitation can be addressed through the use of out-of-sampp extensions, which are discussed Appendix
E
Out-of-sample extensions.
Out-of-sample extensions are usefuul in many applications where low-dimensional embeddings computed on the original dataset are extended to new data. The Nyström extension is well-known technique used in the machine learning community to approximate the Gram matrix by low-rank embedding. However, the out-of-sample extension of duffision maps for asymmetric kernels has not been studied before. Here, present the corresponding Nyström-based extension for out-of-sample cases. As discussed earlier, the integral operator
(5) is compact and self-adjoint, whose spectral decomposition is (XO) (9) If X f O, the following identity holds for æ E X:
T(4)
( (x) / (
pl v.9)
( x
d (y)dd)))
The Nyström extension extends the equation above to new data Z such that X C Z as follows,
p(z, y. 4)
(14)
(z)
dl (y)dp(y)
(al)
(g)
where z E and on (9)
(z)
Σ
Alz.y.g)
(y) the empirical form of (al for X. This allows
Nx.o
VEX
the eigenfunctions to be extended for new data, enabling the extension of MagDM 8 as follows,
Σ
p(z. y. 9) (0) (y),
plz, y. 9) 22 (z).
(4)
p(z, 3 q)
(6.1) (v)
N
BEX
Descriptions and figures of datasetss
In this section, visualize the datasets using either expert knowledge force-directed layout. We hope that these visualizations will help readers gain a better understanding the data.
F.1 The first artificial network
Fig. 2pe.2 a) provides the running flow of the first artificial network and Fig. Ape.2 () shows an example the directed graphs generated with O, where the asymmetric adjacency connection can be considered asymmetric kernel.
15

---

Forward flow
Backward flow
B
(a) The running flow of three groups
(b) Graph using the expert knowledge positions.
Figure 2pe.2: 2: An illustration of the first artificial network. (a) The running flow of three groups A, and The directed/asymmetric information is nested the running flow. (b) An instance of directed graph generated by the running flow with backward flow probability P = 0.
F.2 The second artificial network
The running flow of the second artificial network comprises four groups (A, and D). The structure of the flow is apparent, with groups A and D serving as out-come and in-come nodes, respectively, while groups B and function as communicators. Groups and C are two dense sets containing 20 nodes and Group A and D are pair of datasets whose interconnections are much more than Group B and C.
Strong flow Fow
The running flow of four groups.
Graph using force-directed layout.
Figure Ape.3: An illustration of the second artificial network. (a) The running flow of three groups A, B. C and D. The directed/asymmetticc information is nested in the running flow. (b) An instance of directed graph generated by the running flow with Groups and D playing particular role (green and orange nodes) and Groups B and C playing a role of a communicator (red and blue nodes).
F.3 The Möbius strip
The Möbius strip dataset is a of 300 points randomly distributed along the Möbius strip. The parametric form of the Möbius strip is defined by,
æ(u, v) (1 +
" sin u, z(u,v) sin " ") cos u, v(u,o) v) (1 V cos ?
where 0 S u < and 0.5 S S 0.5. The dataset is with color drift the counterelockwise direction the x-y plane in Fig. Ape.4
16

---

0.3
0.2
(00 a dnD
ardoacol 3000
proe ad roooooo0
0.1
-0.2
9
0
0.5
-1
-0.5
Figure Ape.4: Dataset with 300 random points in the Möbius strip.
E,4 Two trophic networks
We have chosen two specific trophic networks: the Mondego 33 and Florida 33 networks, which part of the Pajek datasets. These networks have recorded the trophic exchanges Mondego estuary and Florida bay during the wet season, respectively. Based on the roles of the nodes in these ecosystems, we have classified them into different categories, shown in Appendix Ape.5] The green nodes, such as 2um Spherical Phytoplankt and Phytoplankton, are producers that generate their own food through photosynthesis chemosynthesis. The brown and red nodes are low-level consumers like littorina and high-level consumers like bonefish and crocodiles that feed on other organisms for energy. Additionally, the purple node in the Florida network represents decomposers that break down dead or decaying organic matter. Finally, the blue and turquoise blue nodes correspond to the input, output, and organic matter of the ecosystem, respectively.
(a) Mondego.
(b) Florida.
Figure Ape.5: The trophic networks using force-direct layout. Nodes among this network are classified into several categories, The green nodes are producers that generate their own food through photosynthesis chemosynthesis. The brown and red nodes are low-level consumers and high-level consumers that feed on other organisms for energy. Additionally, the purple node the Florida network represents decomposers that break down dead or decaying organic matter. The blue and turquoise blue nodes correspond to the input, output, and organic matter the ecosystem.
17

---

G Quantitative experiments
We have incorporated quantitative experiments measure the performance of the proposed method (MagDM) in comparison to two other methods (ME and MME). In the first network, we set the forward flow probability to 0.5 and the backward flow probability the fow-dimensional embeddings of the three methods using the k-means algorithm with k=3. To evaluate performance for the clustering results, we consider two internal evaluation metries: the silhouette coefficient (SC) and the Brriiiin index (DB), well as two external evaluation metrics: the adjusted Rand index (ARI) and the normalized mutual information (NMI). These metries assess the quality of clustering.
P=0/0.2/1. We then cluster
The results of the quantitative experiments evaluating the performance of the proposed MagDM are presented in Tab. Tf the attached PDF file. It can be seen that MagDM achieves higher scores in the metrics. Particularly when P=1, where interconnections significantly outperforms other methods, which highlights the superior effectiveness and robustness of MagDM compared other methods.
complicated, MagDM
Table Ape. 1: Quantitative experiments on the first network in Section 5.1. The symbol 1V indicates that higher/lower scores correspond better clustering results.
Evaluation metrics
MagDM
ME
MME
SCt
0.8583=0.0461
0.855
0.86162000094
DBL
0.3647=0.0610 0.3918=0.0709
0.3525:0.0587
P=0
ARI
0.9365=0.0581
0.9085=0. 1051
0.9285#0.00 0586
NMI
0,9617=0.0624
0.9227=0.0529
0.9548+0.044 0488
SCT
0.883920.04400
0.8701 #0,0168
0.8788$000447
DBL
0.3277=0.071
0.3343#0 0625
0.3012+0.0805
P=0.2
ARI
0.8940=0.0711
0. 0.8863#0.0FF 0,056
0,86770.0626
NMI
0.9106=0.11 1115
0.8608=0.0762
0,8259#0.08 0.771
SCT
0.820620.0422.
0.7987=0.0342
0.797950.0354
DBL
0.3924+0.0399
0.4311=0.0848
0.4269
P=1
ARIT
0.926620.0883
0.2555=0.188 1818
-0.0030+0.0091
NMI
0.9484=0.0667
0.2124=0.1716
0.0074+0.0061
H Experiments regarding the importance of the parameter t
We have conducted additional experiments on MagDM, focusing on diffusion time E {1. 3, 5, 10). The results are presented in Fig. Ape.6 which can be found in the attached PDF file under the General Response section.
In Fig. Ape.6 we illustrate the clusters that evolve from different values of / (1 E 2, 4,5, 5, 10)).
At I, the local geometry becomes apparent with four clusters visible on the real and imaginary axes. Due to the presence of asymmetric connections, the diffusion distance between samples within the same group small, while the diffusion distance between samples in different groups large. Consequently, even with reduced dimensions, we can clearly distinguish the four clusters in the diffusion space. the diffusion process progresses, the diffusion distance between different groups decreases. At = 4, the groups start to connect with each other, forming a single structure. Finally, 10, the four groups merge to create a single super-cluster structure, with very small diffusion distances between points. Interestingly, the clustering on the phase axes remains clear and preserved throughout the diffusion time. This observation demonstrates the strong ability of MagDM to capture asymmetric information during the diffusion process. The dynamic behavior we observe underscores the effectiveness of representing and visualizing the data.
I Discussion of the diffusion framework
The MagDM framework, proposed for asymmetric scenarios, employs a mathematical technique to transform a pair of real-valued asymmetric similarities into complex-valued and conjugate symmetric similarities. By leveraging the concept of random walks graphs, the framework computes the diffusion distance D'(x, y). This distance a functional weighted I,² distance between complex- valued proximities, enabling more flexible and adaptive measure of similarity. D'xx, y) will be
18

---

MagDM phase (0) MagDM phase o MagDM phase (00 Mag phase (00 MagDM phase (e) Mag phose o2
MagDM Re %%
MagDM im (c)
0.04
0.02
0.02
T=1
0- *
0.01
-002
-x/2
x12
-0.02
0.02
-0.02
0.02
MagDM phase
(9)
MagDM Re
MM Im a
MagDM Im (0)
0.03
n/2
MagDM Re
0.02
0.02
T=2
0-
-0.02
-0.02
0.02
-0.02
0.02
MagDM phase of1)
MagDM Re s
MagDM Im
MagDM Re 4
MagDM Im (
0.04
0.03
n/2
0.02
T=3
0.01
-000
-m/2
m/2
-0.02
0.02
-0.02
0.02
MagDM phase (9)
MagDM Re #1
MM Im (
2
MagDM Im (c)
0.04
T=4
m/
MM Re
0.02
0.02
ago
-0.02
-x/2
-0.02
0.02
-0.02
0.02
MagDM phase ((4)
MM Re $1
(c)
MM Im a
MagDM Re (s)
MagDM Im (9)
0.03
T=5
m/
0.01
0.00
-n/2
n/2
-0.02
0.02
-0.02
0,02
MagDM phase (()
MagDM Re o
MagDM of
MagDM Re 4%
MM Im (q)
0.04
0.03
T=10
n/2
0.02
0.02
0.01
-0.02
m2/2
m/2
-0.02
0.02
-0.02
0
0.02
MagDM phase (()
MagDM Re s(()
MMgDM Im s
Figure Ape.6: Clusters evolving from t E blue, and orange, with g 1/3. For better illustration. the real and imaginary parts of the first two non-trivial eigenvectors are reported, in addition to the phases.
10) on the four groups colored by red, green,
small if two samples are similar in the complex-valle valued plane and vice versa. Consequently, it becomes capable of capturing both local and global patterns within the data.
In this framework, the diffusion kernel, denoted p(z:, y). represents the transition probabilities of the random walks. signifies the likelihood of transitioning from one data point to another within the network. In summary, the proposed diffusion distance within the MagDM framework facilitates geometric interpretation of asymmetric similarity. It encompasses the network structure and takes into account the asymmetric relationships between data points.
J The comparison with
The MagDM is not a simple derivation of diffusion map for ((1)-comnection graphs because there three key differences between MagDM and the graph connection Laplacian (GCL) approach.
Definition of the similarity matrices. MagDM focuses on asymmetric similarity between samples and calculates the (1) transporter for all pairs of samples. On the other hand, GCL focuses on symmetric cases and calculates the orthogonal (d) transporter for graph edges. While there an isomorphism between (1) and SO(2), they differ in implementation. MagDM measures scalar
19

---

similarity between two samples, denoted as x and y. while the similarity between x and y in GCL is d d block. The corresponding Gram matrix MagDM, denoted by p. has a size of N * N, while the corresponding Gram matrix in GCI, denoted by S, is Nd * Nd.
Definition of diffusion distance. In MagDM, the diffusion distance is defined as [D (x; y)} Ix (e"(z, u) (y, u)) u(dd). It measures the number of paths of length connecting x and y the complex-valued plane. The diffusion distance is calculated by the sum of squares of the difference between o² (I, o) and p² (y, In GCL, diffusion distance has a different form: [D' y)]² = Tr(SS (z. S) (x, ()), which measures the agreement between transporters and the number of paths of length connecting and y. Based these two definitions, it can be observed that (11) ((())-nonection graphs exhibit different diffusion distances in MagDM and GCL.
Definition of the diffusion map. Due to the differences in diffusion distances, the dif- fusion maps of the two methods also differ. In MagDM, eigenvalues and eigenvectors are defined as {>i , { respectively. The diffusion map is defined as 0'(x)) = (M (x) Naebe (.)..... (x))(())) For vector diffusion map, its eigenvalues and eigenvectors are defined as ] : ] respectively. Its diffusion map is defined by ('(x) = ((nen)) < (x()), (x) >> These two diffusion maps have different forms from each other. Overall, MagDM is not a derivation to a notion of diffusion map for U(())-conectiion graphs.
K Eigenvalues and robustness
Indeed, H and 1 H can be transferred each other when considering both positive and negative cigenvalues. However, it should be noted that in [88 19] the negative eigenvalues are truncated, which means that and I H are not identical in this regard. We focus on the k eigenvalues that include both positive and negative eigenvalues with the largest absolute magnitudes. These top k eigenvalues correspond to the slowest diffusion processes or the global structures in the data. It is also believed that the larger magnitude of cigenvalues corresponds to better discriminative information, as discussed in [37] One notable advantage of this approach is robustness when confronted with perturbed asymmetric similarity. Even if the similarity measure is distorted, we can still obtain the principal components using this method. However, there is no specific reference to a related study because most previous work has mainly focused on positive semi-definite matrices. When dealing with asymmetry, it becomes necessary to consider negative eigenvalues. This aspect is worth exploring in future research. Currently, we can observe this phenomenon experimentally in Fig. I of the manuscript. In the case where P=0, it represents a situation where there are only links in one direction, making it asymmetric but relatively easy scenario. When P=1/0.8, the situation becomes more complicated and backward flow is perturbed by the forward, MagDM effectively distinguishes between the three groups while ME/MME struggles to capture the information, highlighting stronger robustness and effectiveness of MagDM.
In the experiments involving asymmetric similarity, it is indeed possible for the largest eigenvalues to have different signs. Here, we present the counts of eigenvalues for Φ1 and ø2 that exhibit both positive signs (++) and opposite signs (+-) among 100 trials for the network generated by the forward and backward flows (Experiment 1). The forward flow probability is fixed at 0.5, while the backward flow probability P is selected from the following set: {0, 0.3, 0.4, 0.5, 0.6, 0.65, 0.675, 0.7, 0.8, 1).
Table Ape.2: 2: The counts of signs for different P.
P
0
0.3
0.4
0.5
0.6
0.65
0.675
0.7
0.8
++ 100
100
96
90
81
57
16
2
0
0
+- 0 0
4
10
19
43
84
98
100
100
it can be observed that as P increases, the number of opposite signs also increases. Particularly, when is larger than 0.675, opposite signs occur more frequently. We have discovered that the principal components align with both positive and negative eigenvalues, highlighting the superior performance of MagDM. These results further substantiate the robustness of MagDM.
In Tab. Ape.2 2
20


Reviews:
[{"review_id": "prru6fih2n", "reviewer": "Reviewer_SsqM", "summary": "The paper proposes proposes a new method called MagDM in which it connects Diffusion maps (DM) and the Magnetic transform (MT). DM is a nonlinear dimension reduction technique obtains a lower dimensional embedding by using the information of the diffusion distances that assume symmetry. However, in practice the intrinsic and extrinsic geometries of data can be asymmetric. MT is a promising technique that converts an asymmetric matrix to a Hermitian one, make it suitable for working with asymmetry, but the connection between DM and MT haven’t been explored much. Hence, the main contribution of the paper is to make such connections between DM and MT. Specifically, they developed a diffusion framework endowed with asymmetric kernels using MT. Also, the integral operators of MT, whose compactness is established if the asymmetric kernels are Hilbert-Schmidt kernels have been explored. They’ve also proven an important property that the spectral radius of the proposed integral operator is 1, which ensures that MagDM will not diverge during the diffusion process.", "questions": "1. Can the authors use quantitative measures of how well the methods perform?\n\n2. In Figure 1, it is shown that MagDM has better results compared to ME & MME when P has large values (greater than 0.5). On the other hand, when P is less than 0.5, specifically when P = 0, P = 0.2, all three methods are doing well to separate the groups. So if P = 0 and P = 0.2 are also considered to have high level of asymmetry information, how does MagDM outperform others? \n\n3. In Figure 3, from the perspective of dimension reduction, I would like to compare the result to the original structure . Since the original structure is connected for a M¨obius strip, I would expect the lower dimensional embedding to be connected in a loop as well. However you’ve mentioned in line 210 that you focus on the asymmetric geometry of the data but I am not sure how does the ”asymmetric structure” look like in the original space colored by the rainbow map. So I think you should add the additional subplots to your figures to show us how the original data looks like.", "limitations": "Addressed", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The ideas presented here are original. The paper is generally well-written. There are numerous qualitative experiments. Since asymmetric data is common, the proposed approach could have a high significance and impact and could be useful in other methods that use the diffusion framework.", "weaknesses": "The paper is missing quantitative experiments. While the qualitative experiments in the paper do suggest that MagDM is capturing the asymmetric geometry better than other approaches, the scatter plots are difficult to interpret without expert knowledge of the underlying data. It would be better to have some numerical evaluation of this. I recommend the authors come up with some metric that measures this performance for comparing the different methods.\n\nOther comments\nThe diffusion framework could be clarified further. For example, what is the geometric interpretation of the diffusion distances and how do they relate to $\\rho(x,y)$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and appreciation of the novelty. We address your concerns as below:\n\n**R1.1 Quantitative experiments are needed.**\n\nWe sincerely appreciate your insightful comments. In response, we have conducted the quantitative experiments as suggested. For further details, please refer to **R0.1** in the Author Rebuttal.\n\n**R1.2 Discussions of the diffusion framework.**\n\nThe MagDM framework, proposed for asymmetric scenarios, employs a mathematical technique to transform a pair of real-valued asymmetric similarities into complex-valued and conjugate symmetric similarities. By leveraging the concept of random walks on graphs, the framework computes the diffusion distance $D^t(x,y)$. This distance is a functional weighted $L^2$ distance between complex-valued proximities, enabling a more flexible and adaptive measure of similarity. $D^t(x,y)$ will be small if two samples are similar in the complex-valued plane and vice versa.\nConsequently, it becomes capable of capturing both local and global patterns within the data.\n\nIn this framework, the diffusion kernel, denoted as $\\rho(x,y)$, represents the transition probabilities of the random walks. It signifies the likelihood of transitioning from one data point to another within the network. In summary, the proposed diffusion distance within the MagDM framework facilitates a geometric interpretation of asymmetric similarity. It encompasses the network structure and takes into account the asymmetric relationships between data points. We will ensure to include these clarifications in our research.\n\n**R1.3 How does MagDM outperform others in Figure 1?**\n\nThank you for your insightful observations. Both ME and MME are designed to extract asymmetric geometric information. When P=0, it represents a situation where there are only links in one direction, making it an asymmetric but relatively easy scenario. When P=1/0.8, the situation becomes more complicated, and ME/MME may struggle to capture the information. In contrast, MagDM effectively distinguishes between the three groups in both scenarios, highlighting its stronger robustness and effectiveness. The reason could be intuitively explained as follows: ME/MME focuses solely on the positive part of the eigenvalues of the Hermitian kernel function (Eq.3) but as Proposition 2 demonstrates that the eigenvalues are not necessarily all positive. In the proposed method, regardless of their sign, we take into account all the eigenvalues and the advantages are more obvious for hard tasks, i.e., P=1/0.8.\n\n**R1.4 Results about the M\\\"obius strip**\n\nYour intuition and suggestions are appreciated. We put the original structure of the M\\\"obius strip in Appendix F.3 of the supplementary material, which is indeed a loop as you expected. In the main body, we demonstrate the result in another view: color is drifted in counterclockwise direction on the x-y plane from $\\angle xy=0$ to $\\angle xy=2\\pi$, so the embedding performance is more likely a line. In the final version, we will add the figures in the main body.\n\n\n\n"}, {"review_id": "JsdrMoxGk1", "reviewer": "Reviewer_sG91", "summary": "This paper studies the asymmetric kernel case for the diffusion map. The authors utilize the magnetic transform technique to develop a diffusion representation framework for the asymmetric kernel case. They investigate several properties of the proposed magnetic transform kernel. The challenge lies in defining the corresponding integral operators and diffusion geometry. In their experiments, the authors show their proposed MagDM framework competitive and even superior to existing dimension reduction techniques like DM, KPCA, etc. ", "questions": "I am not familiar with the topic and feel quite confused about Proposition 1: why do we want to assume a Hilbert-Schmidt kernel $X$ and define another Hilbert-Schmidt kernel $H^{(q)}$? The goal seems to define a kernel with conjugate symmetry.", "limitations": "The authors have mentioned some limitations of the proposed MagDM framework in appendix. For example, different choices of asymmetric kernel functions would impact the performance of the framework. Currently, there is no clue about how to handle it.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work combine the magnetic transform and the diffusion map techniques to handle the asymmetric kernel case of the diffusion map. It seems to be a pioneer research work by defining new concepts.", "weaknesses": "All the experiments present only qualitative results and some quantitative results would help figure out the advantages of the proposed MagDM framework over other existing techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for appreciating the novelty of our work and for providing insightful comments. We address your concerns as below:\n\n**R2.1 Some quantitative results would help figure out the advantages of the proposed method.**\n\nWe sincerely appreciate your insightful comments. In response, we have conducted the quantitative experiments as suggested. For further details, please refer to **R0.1** in the Author Rebuttal.\n\n**R2.2 The goal of defining another Hilbert-Schmidt kernel.**\n\nDefining the Hilbert-Schmidt kernel is a preparatory step for MagDM. The goal is to define the Hermitian kernel function whose spectral decomposition is utilized to support the proposed diffusion maps (Eq.8).  The existence of the spectral decomposition requires the corresponding kernels to be both conjugate symmetric and Hilbert-Schmidt kernels. Therefore, it is necessary to define the Hilbert-Schmidt kernel $H^{(q)}$ based on Proposition 1.\n\n\n\n\n\n\n\n\n\n\n\n\n\n"}, {"review_id": "ae75CrhUxZ", "reviewer": "Reviewer_E65Y", "summary": "The paper introduces the concept of the magnetic transform to define diffusion representation and diffusion distance for asymmetric kernels. The key idea is to transform an asymmetric kernel into a Hermitian one, enabling the application of standard techniques such as eigen-decomposition.\n\nBy leveraging this magnetic transform approach, the authors conduct experimental validations to assess the effectiveness of their proposed method. The results demonstrate that their method outperforms other dimension reduction methods in terms of separating clusters in asymmetric data.", "questions": "- line 86: why do you choose $t$ to be an integer instead of a real number?\n- What is the kernel involved in the experiments in Section 5.1?", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The presentation of the paper is clear and the paper is easy to follow.\n- A proper discussion on the selection of the scaling parameter in included which is helpful for people to implement the method.\n- The experimental results support the effectiveness of the proposed method.", "weaknesses": "A major concern regarding the paper relates to its novelty and theoretical justification. Several points raise doubts regarding the originality and uniqueness of the proposed approach:\n  - The Magnetic transform, as presented in the paper, may not be considered entirely novel. Previous works, specifically [18] and [19], have already studied similar forms of the Magnetic transform, particularly when the kernel represents the adjacency matrix of a directed graph. This raises questions about the extent to which the proposed approach differs from previous research. While the paper focuses on a different matrix form ($H$ instead of $D-H$ or $I-H$), more theoretical justification is needed to demonstrate the significance and appropriateness of this choice.\n  - Besides, I would like to bring the authors' attention to the following paper: ```VECTOR DIFFUSION MAPS AND THE CONNECTION LAPLACIAN``` by Singer and Wu. It is well known that magnetic laplacian is the same as the connection laplacian when considering $SO(2)$ signatures. In this reference, Singer and Wu have already considered diffusion maps and diffusion distances for connection graphs which could well be a generalization already for what the authors are proposing. I think a comparison with this reference is needed.\n  \nAdditionally, there is a lack of clarity in the experiments regarding the importance of the parameter $t$ and the role of diffusion in the proposed method. The paper does not explicitly demonstrate how the choice of $t$ influences the results or why diffusion is significant. In fact, the current experiments only show that the eigenvectors of the normalized kernel is useful. This ambiguity hampers a thorough understanding of the method and its underlying principles.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reviewing and insightful suggestions. We address your concerns as below:\n\n**R3.1 Contributions of (Eq.3).**\n\nThank you for your insightful thoughts on the difference from existing works. The contribution of our work lies in the development of a diffusion representation framework designed for asymmetric kernels. In contrast, existing works [1,2] primarily focus on asymmetric matrices. It is crucial to note that these two approaches are fundamentally distinct: our framework naturally produces a diffusion representation and function decomposition customized to a matrix derived from a kernel function, whereas the reverse may not hold true. This development was facilitated by exploring integral operators of magnetic transform kernels, and Proposition 1 provides the condition for the existence of spectral decomposition.\n\nThe magnetic transform is designed for asymmetric kernel cases. It is built upon the observation made in our manuscript, supported by Proposition 2, that the eigenvalues of the kernel function H are not uniformly positive, serving as the basis for our design of MagDM. Based on the observation, it is apparent that asymmetric information is embedded not only in positive eigenvalues but also in negative eigenvalues, along with their corresponding eigenfunctions. By incorporating both positive and negative eigenvalues of H, we achieve enhanced robustness and effectiveness. In contrast, [1,2] (I-H) only focused on positive eigenvalues, neglecting the importance of this phenomenon. As a consequence, their approach suffered from limited robustness. The experimental results support the effectiveness of MagDM.\n\n**R3.2 The comparison with Singer and Wu's work [3].**\n\nWe appreciate your insightful comment regarding Singer and Wu's work [3] which indeed provides a valuable foundation in the field. However, it is important to clarify that MagDM and [3] are not generalizations of each other.\n\nThe proposed methods have three fundamental differences with [3]. Firstly, the addressed problems of them are different. The proposed method addresses the challenge of dealing with asymmetric kernels while [3] focuses on symmetric kernels. Secondly, the unitary transporter defined in (Eq. 3) is utilized for all pairs of samples which reflects asymmetric geometries of the data. In contrast, the SO(2) signatures in [3] are optimized only for nearby samples as best rotational alignments. [3] suggests that these samples, denoted as $x$ and $y$, should satisfy the condition $0 < \\\\| x - y \\\\|_{\\mathbb{R}^p} < \\sqrt{\\epsilon}$, where $\\epsilon$ is the scaling parameter. And the connection Laplacian is the convergence in the limit of $N \\rightarrow \\infty$ and $\\epsilon \\rightarrow 0$ of the Vector Diffusion Map (VDM). In this scenario, SO(2) signatures are optimized only for pairs of samples that are very close to each other in Euclidean space. Thirdly, We employ a complex and unitary transporter in U(1), which is controlled by q. In [3], the SO(2) transporter is determined through local PCA. Additionally, the diffusion distance (Eq.6) in MagDM represents a functional weighted distance between complex-valued proximity of two samples, and the corresponding diffusion map is also complex-valued. In contrast, [3] operates in real-valued working spaces. A similar discussion is also reported in Section 3.3 of the paper [1] which explains the connection between ME and VDM.\n\nThese distinctions limit the applicability of [3] to the problem addressed in this paper. However, MagDM offers a viable approach to handling asymmetric kernels. We appreciate you highlighting this point, and we will ensure to include these clarifications in our research.\n\n**R3.3 The lack of clarity of the parameter in the experiments.**\n\nThank you for your insightful comments. We have conducted additional experiments on MagDM, focusing on diffusion time $t$. The results are presented in Fig. R1 of the attached PDF file under Author Rebuttal.\n\nIn Fig. R1, we illustrate the clusters that evolve from different values of $t\\in\\\\{1,2,3,4,5,10\\\\}$. At $t=1$, the local geometry becomes apparent with four clusters visible on the real and imaginary axes. The diffusion distance between samples within the same group is small, while the diffusion distance between samples in different groups is large. As the diffusion process progresses, the diffusion distance between different groups decreases. At $t=4$, the groups start to connect with each other, forming a single structure. Finally, at $t=10$, the four groups merge to create a single super-cluster structure, with very small diffusion distances between points. Interestingly, the clustering on phase axes remains clear and preserved throughout $t$. This observation shows the strong ability of MagDM to capture asymmetric information during the diffusion process. The dynamic behavior we observe underscores the effectiveness of representing and visualizing the data. We will ensure to include the experiments in Appendix of the manuscript due to the space limitation.\n\n**R3.4 Discussion about diffusion time $t$.**\n\nThanks for your careful reading. We acknowledge that there is a typo and $t$ is chosen to be a positive real number. We assure you that it will be rectified in the revised version.\n\n**R3.5 Kernels in Section 5.1**\n\nWe utilize the adjacency matrices as Gram matrices of the data. The adjacency matrices are generated by the running flow probability. $K_{ij}=1$ if sample $x_i$ is to connect sample $x_j$ and $K_{ij}=0$ if not.\n\n**Referneces**\n\n[1] Fanuel M, et al. Magnetic eigenmaps for the visualization of directed networks[J]. ACHA, 2018, 44(1): 189-199.\n\n[2] Cloninger A. A note on markov normalized magnetic eigenmaps[J]. ACHA, 2017, 43(2): 370-380.\n\n[3] Singer A, Wu H T. Vector diffusion maps and the connection Laplacian[J]. Commun Pure Appl Math, 2012, 65(8): 1067-1144.\n"}]

Author rebuttal:
Dear Program Chairs, Area Chairs, and Reviewers,

First of all, we would like to thank you for your time, constructive critiques, and valuable suggestions, which greatly help us improve the work. We are grateful to reviewers SsqM and sG91 for recognizing the novelty and significance of our work. They acknowledge its potential to have a high impact in addressing asymmetric kernel cases. And we also grateful that reviewers unanimously agree that our qualitative experimental results support the effectiveness of the proposed method. We will address the concern about quantitative experiments as below:

**R0.1 Reviewers SsqM and sG91 think quantitative experiments are needed.**

Thanks for your insightful suggestions. We agree with you that quantitative results can better show the advantages. However, for unsupervised learning, this is always a problem. And thus, specifically to the dimension reduction, there is no well-accepted quantitative criteria. So, the recent papers [1,2] also lack quantitative experiments. Following your suggestions, we have employed four evaluation metrics commonly used for clustering. Given that the original data is clustered in a high-dimensional space, our expectation is that the embedded data will also exhibit clustering patterns after dimension reduction.   

We have incorporated quantitative experiments to measure the performance of the proposed method (MagDM) in comparison to two other methods (ME and MME). In the first network, we set the forward flow probability to 0.5 and the backward flow probability to P=0/0.2/1. 
We then cluster the low-dimensional embeddings of the three methods using the k-means algorithm with k=3.  To evaluate performance for the clustering results, we consider two internal evaluation metrics: the silhouette coefficient (SC) and the Davies-Bouldin index (DB), as well as two external evaluation metrics: the adjusted Rand index (ARI) and the normalized mutual information (NMI). These metrics assess the quality of clustering. If you are interesting about these indexes, we are willing to discuss with you.

The results of the quantitative experiments evaluating the performance of the proposed MagDM are presented in Table 1 of the attached PDF file. It can be seen that MagDM achieves higher scores in the metrics. Particularly when P=1, where interconnections are more complicated, MagDM significantly outperforms other methods, which highlights the superior effectiveness and robustness of MagDM compared to other methods. 

We will ensure to include the experiments in Appendix of the manuscript due to the space limitation. We sincerely look forward to further discussions with the reviewers.

Best wishes,

Anonymous author(s) of Paper6885

**References**

[1] Fanuel M, Alaíz C M, Fernández Á, et al. Magnetic eigenmaps for the visualization of directed networks[J]. Applied and Computational Harmonic Analysis, 2018, 44(1): 189-199.

[2] Gomez A A, Neto A J S, Zubelli J P. Diffusion representation for asymmetric kernels[J]. Applied Numerical Mathematics, 2021, 166: 208-226.






Meta-review: The paper discusses asymmetric kernels for diffusion models. Three reviewers voted to accept the paper, with two significantly raising their scores following the discussion. The use of the magnetic transform was judged to be novel and the quantitative evaluations lent some support for its usefulness. The reviewers commented on the lack of quantitative evaluation.
Decision: Accept (poster)