s2fieldsofstudy:
Computer Science
Physics

text:
The making of microscope camera standards

Cameras are a crucial part of microscopes and are also built into many kinds of instruments. To make their output comparable takes standards.

The making of microscope camera standards Cameras are a crucial part of microscopes and are also built into many kinds of instruments. To make their output comparable takes standards.

Vivien Marx
T he academics and company scientists in the group Quality Assessment and Reproducibility for Instruments & Images in Light Microscopy (QUAREP-LiMi) are developing standards for microscopy camera output.
As in other areas of standards development, working with companies is crucial; "after all they are the expert of the hardware they are producing, " says Caterina Strambio-de-Castillia, a researcher at the University of Massachusetts Medical School's Program in Molecular Medicine and a Chan Zuckerberg Imaging Scientist, who spearheads this effort within QUAREP-LiMi. A separate story in this issue of Nature Methods about emerging standards in microscopy can be found in this issue.
Part of the work in developing standards for cameras in microscopy and imaging is about creating common definitions as a public resource. "The QUAREP-ers are moving on all that quite well, " says Jason Swedlow of the University of Dundee, who is a co-founder of the Open Microscopy Environment. It "would be great, " he says, to have definitions as public resources for the detector and the chip, the gain, offset, read noise, readout speed, analog-to-digital conversion and full well capacity, which refers to the charge an individual pixel can hold before it is saturated.

Quantitative, standardized output
They make "precision scientific instruments, " which is why taking part in QUAREP-LiMi matters to her company, says Stephanie Fullerton, life science marketing manager at Hamamatsu, which manufactures cameras, light sources, optical sensors and other optical instruments. Her Hamamatsu colleague Sebastian Beer takes part in QUAREP. What motivates them is helping to make sure customers can get reproducible and reliable data.
Given that images are now thought of "as quantitative data rather than qualitative pictures, " it's a necessity to categorize and capture the details of the entire imaging system, says Fullerton. "It's just good scientific practice. " Such metadata from an experiment are an important aspect of experiments. But as Strambio-de-Castillia and others have pointed out, ways to record metadata well have not stayed abreast with technical advancements. She and colleagues presented Cameras are a crucial part of microscopes and imaging systems. Agreeing on standards to provide defined descriptions for aspects such as gain or readout speed is tricky. Credit: W. Bulgar/Science Photo Library tiered specifications to extend the Open Microscopy Environment data model to include the needs of the 4D Nucleome Initiative Imaging Standards Working Group, BioImaging North America (BINA) and QUAREP-LiMi.
Imaging systems, with their many components and specifications, make it "daunting to conceptualize a way to organize all this metadata, " says Fullerton. The proposal's tiered structure is an approachable way to get started. As with any new process, making it easy and intuitive for researchers to use will help with its acceptance. "I suspect there will be unexpected glitches along the way that will require iterative revisions but that is the nature of research anyway, " she says. "It's important that we get started. " At the company Phi Optics, originally a University of Illinois Beckman Institute of Advanced Technology spinout that he co-founded, Catalin Chiritescu wears many hats. He reaches out to users and is involved with standards organizations. The company sells platforms for quantitative phase imaging, an imaging modality like fluorescence or brightfield. Phi Optics modules can be added to microscopes, including those made by any of the 'Big Four' , as the companies Leica, Nikon, Olympus and Zeiss are sometimes called.
Data from the company's module include the 3D shape of a specimen, refractive index, dry mass and other quantitative measures, which all need to be reproducible. A live specimen such as a bacterial culture can have different orientations, which change the readout. He recommends making a baseline measurement with standardized samples such as plastic or glass beads of known dimensions and properties.
Software is generally increasingly important in microscopy, says Chiritescu. He and his colleagues integrate the Phi Optics module with individual microscope types. "That's where the magic behind the curtain works, " he says. He and his team adjust the Phi Optics module to work in tandem with the microscope's electronics and the optics so that the phase-imaging module delivers consistent measurements. All of today's biology, chemistry, physics and materials science focuses on generating reproducible measurements, says Chiritescu. Standards, he says, help to weed out science that lacks proper follow-through with a scientific method.
"You can't really punish the users for being curious," says Catalin Chiritescu.
Sometimes, users modify instruments, which Phi Optics sees as a "two-way street, " he says. "You can't really punish the users for being curious. " The modifications can lead to instrument improvements, and the company gladly offers to help a lab make modifications.
Standards organizations such as QUAREP are useful to Phi Optics, he says, to interact with researchers and learn about their needs and those of imaging facility managers. Those needs shape what Chiritescu and others in the industry do. "This is where they start, " he says. Standards and procedures developed in academia often later become established in the commercial world.
Like any human endeavor, QUAREP and others are right to present companies with "a big ask, " he says. Academics might not get all they want, and some things might not be practicable or there may be proprietary aspects to consider.

Committed to open file formats
From its founding, Phi Optics committed itself to open file formats. Data from its instruments can be opened with ImageJ or with Fiji tools, or any software that can handle TIFF files, says Chiritescu. The files contain the image properties and the associated metadata, such as date and time of image acquisition, software used for data acquisition, type of microscope to which the Phi Optics module is attached, magnification, sample temperature and other details. "The camera itself, it's a microcosm of metadata in itself, " he says.
Scientists want to document everything about the camera output that a user can modify, such as exposure, how long the sensor's iris stays open and anything else that another lab needs to reproduce the work, he says. Slightly different conditions, such as an iris open for one versus two seconds, might lead to different observations. Labs want to be sure that what's causing the shift is biology: are the bacteria changing their state, or is a different result due to a different fluorescence filter? As a scientist, he understands that academics need as much metadata as possible. As an industry person, he finds that "there's only so much metadata that can be crammed into a file" before the effort to do so delivers diminishing returns.
Working on standards means getting precise definitions across camera types. He recalls one discussion about 'camera gain' , which might seem straightforward. Yet, though he can explain what that means from the Phi Optics perspective, another company might define it differently. Talking such matters through in groups such as QUAREP is a way to agree on the most accurate way to describe a parameter. And camera gain may just be "one single line item in the pile of metadata, " he says.
To reach agreement on standards involves synching these definitions. Therefore, it's in everyone's interest to take part in such discussions. To collaborate and reach reproductible science, scientists want to compare data across modalities and instruments from different manufacturers. "We as industry would like to support that effort, " says Chiritescu.
"The camera itself, it's a microcosm of metadata in itself," says Catalin Chiritescu.

Cameras: CCd, CMoS, sCMoS
At PCO, Gerhard Holst has long directed the research department, where he also ran grant-funded research projects with which the company explored new approaches for its cameras. Those include complementary metal-oxide semiconductor (CMOS), charge-coupled device (CCD)-based cameras and high-speed cameras. In 2021, Excelitas Technologies acquired PCO. Excelitas works in photonics and sells detectors, light sources and optics supplies for the life sciences, materials sciences and avionics.
PCO's cameras can be used on microscopes, and some cameras are built into instruments, such as a PCR instrument from a manufacturer he prefers not to name. The manufacturer approached PCO with a need for a camera with low drift, which is the term for when a camera begins to pan in one direction or another. Demand for the product was likely going to be a niche market. The instrument was launched, says Holst, right as a swine flu outbreak emerged that made PCR-based virus identification critical. Other public health emergencies, such as COVID-19, have taken PCR instruments far beyond a niche market, he says.
To take good measurements, a scientific camera needs low noise and wide dynamic range, says Holst. The majority of scientific cameras are monochrome. Some labs use smart phones for their work and, in his view, "it's nice for the effect or proof of principle, but not for measuring. " Those cameras have small pixels and tend to use much software to make up for the low light capture, but that image processing gives scientists too little control, he says.
Developing standards means collaborating against the backdrop of competitive contexts. In 2010, says Holst, the camera world changed when an advance in transistor design-scientific complementary metal-oxide semiconductor (sCMOS) technology-led to a new type of camera. Three companies-Fairchild Imaging, later bought by BAE Systems; Andor Technology, now part of Oxford Instruments; and PCO, now part of Excelitas-developed and presented such cameras. They had different options for pixel structure, which the companies discussed with one another. Each chose a slightly different tack and began selling sCMOS cameras.
A bit later, Hamamatsu released a sCMOS camera with, to Holst's knowledge, a different sensor. And, to his knowledge, Fairchild later sold some of its technology to Hamamatsu. Some back and forth between the companies ensued, he says, and in his recollection, Andor and PCO were given access to the image sensor from the Fairchild-Hamamatsu deal. Speaking more generally, he says, the interest in scientific CMOS-sensor-based cameras came because they have lower noise than CCD cameras and are faster.
Hamamatsu's Fullerton says she cannot speak in detail about its partners for its sCMOS technology. Overall, she says, in the past few years, advances have led to lower CMOS noise and to uniformity across the sensor. The company's latest camera, the ORCA-Quest, "has low enough read noise to permit resolving of individual photons. " Standards have long been part of the scientific camera world. According to the CMOS Data Book, a 1977 Fairchild Camera and Instrument Corporation publication, when the active pixel technology using CMOS was introduced in the early 1970s and "as each new generation of designs was developed, a large variety of functional and performance parameters were generated by the industry creating a great deal of customer confusion. " In late 1976, the authors continue, "the CMOS vendor community accepted the formidable task of clearing this confusion via industry-wide standardization." This led to the Jedec Industry Standard 'B' Series CMOS specification. JEDEC is a microelectronics organization with more than 300 company members that connects suppliers and manufacturers to develop standards.
JEDEC grew out of the Joint Electron Tube Engineering Council, established in 1944. It later began to include solid state devices. In 1958, it renamed itself Joint Electronic Device Engineering Council (JEDEC), with a council for tubes and one for semiconductors. Many standards in the electronics industry, such as those for RAM chips, have been worked out by JEDEC.

Compare and contrast
"In the end, it's always the application that defines what the best camera is, " says Holst. A scientist wants to trust the right tool for the questions he or she has. PCO has, for example, supported the standard for machine vision cameras. Machine vision describes cameras used, for instance, in manufacturing for quality control. These are usually non-cooled, smaller cameras, which PCO also sells, says Holst.
The first module of this machine vision standard took time to develop and was launched in 2005. There have been new releases since then. Development is and was led by the European Machine Vision Association (EMVA), a nonprofit that brings together the machine vision industry in Europe.
One EMVA standard is EMVA 1288, for the specification and measurement of machine vision sensors and cameras. It defines "reliable and exact measurement procedures. " Although this standard originated with the EMVA, which is not specifically focused on science applications, EMVA 1288 can be and is used for scientific cameras, says Holst. The standard defines how specs should be measured and presented but not which specs themselves have to be achieved. "The specs to be achieved are defined solely by the application, " he says. Another EMVA standard, GeniCam, is for programming interfaces for cameras and devices.
Hamamatsu follows EMVA 1288 to measure camera specs, says Fullerton, and "this has been especially useful for clarifying how we arrive at more subtle specs such as linearity. " With calibration measurements, it is often not feasible in practice for researchers to replicate them, "and in fact, we've seen noise introduced into analyses done with improper calibrations. " By following EMVA standards, she and her colleagues hope "we build trust with our users so they know they can rely on our cameras to be quantitative. " Within standards organizations, PCO's Holst has experienced intense discussion about how quality parameters of image sensors and cameras should be measured and presented. He also takes part in the discussions related to microscopy, including QUAREP.
Holst knows how much it matters to labs to describe the parameters of a microscope setup, and that what is captured has to be stored so that experiments can be repeated and the data can be trusted. When he joined QUAREP, he thought his experience in describing camera quality parameters would come in handy, "and they don't need to invent the wheel a second time, " he says. He is happy to take part in the discussions for that reason and also to learn about customer needs and wants.
Some researchers develop new tools and are keen on all of a camera's parameters, and want it made to exactly match their requirements, say, in terms of speed, noise or linearity. Others, he says, buy an instrument, such as from Horiba or Perkin Elmer, with a built-in camera, and those scientists are less preoccupied with the camera's parameters.
When a PCO camera is built into a microscope, such as for total internal reflection microscopy, super-resolution or light-sheet microscopy, Holst and his colleagues are involved with the manufacturer.
For example, Zeiss's Z7 light-sheet microscope, the Elyra Lattice SIM system, uses PCO cameras. Microscopes from other manufacturers use PCO cameras, too, but Holst says he is contractually not permitted to name them. PCO also helps labs build tailored systems. Overall, standards are "for us, it's not a big deal, " he says. "We are doing 1288 measurements for all of our cameras" to assure the cameras meet the EMVA 1288 specifications. PCO gives these data to customers. "In the end, it's always the application that defines what the best camera is," says Gerhard Holst.
Given the large amount of data that microscope experiments produce, he sees some companies developing data-compression algorithms. He works with these companies to make sure the readout from the PCO camera remains As working scientists look around for a camera to later compare data, says PCO's Gerhard Holst, "it makes a lot of sense" that scientific cameras make measurements similarly. Credit: PCO intact. In some cases, the algorithms are integrated into PCO firmware. How the information that the camera captures is transferred within a microscope system is not something PCO controls.
Software packages from microscope manufacturers have become huge, says Holst. Overall, the captured metadata have increased. "For them, the large amount of metadata is more work, " he says.
Some software packages look like they were "developed by biophysicists for biophysicists, " he says. He sympathizes with a desire for control over many software parameters. "As an engineer, I would like to control everything, " he says. But during his seven years at the Max Planck Institute of Marine Microbiology, where he developed optochemical microsensors and imaging systems, he learned that not every user needs to turn every knob. It would have sent many of his biology and geology colleagues "running out of the lab crying" if he had developed large, complex software packages with too many controls.
Scientists in core facilities want systems to perform reliably every day and need different kinds of cameras, perhaps a cooled camera or a non-cooled one, one with larger or smaller pixels, or they may have an application in which slightly higher readout noise is acceptable, says Holst.
Some technical details are ones that working scientists might like to remain aware of. Different voltages to a camera sensor will change the output signal in ways that might, to some, be surprising, says Holst. Comparing cameras thus takes careful thought. A small pixel size might seem to deliver a less sensitivity, but "it's simply geometry, " he says. Scientists can fall into a trap when they compare cameras in terms of sensitivity but only look at the number of pixels and omit pixel pitch, which is the size of the pixel itself. With more pixels, each pixel gets less signal, says Holst. Thus, comparison involves taking into account the number of photons that reach each pixel.
Sometimes he has to console scientists whose data seem to have gone entirely missing. They forget, he says, about dynamic range, which leads a 16-bit image rendered on an 8-bit screen to be entirely black.
Standards need clear definitions, says Fullerton. Specs such as pixel number and size are straightforward. Pixel gain, however, is an example of a critically important spec with a variety of definitions and is often a source of confusion, she says. Hamamatsu reports gain in units of electrons per analog-to-digital unit, and this value enables gray level intensity in a pixel to be converted to a non-arbitrary unit of photoelectrons. In her view, defining intensity in photoelectrons allows meaningful comparisons between images taken from different cameras. And, with knowledge of the quantum efficiency at the wavelength of interest, one can approximate pixel intensity in photons. She and her colleagues share with customers the, as she says, "importance and value of 'thinking in photons' . "

Standards need clear definitions, says Stephanie Fullerton.
Each Hamamatsu sCMOS and qCMOS camera reaches a scientist with a quality-control document that provides the factory-measured gain value for that camera. "However, not every camera manufacturer does this and there are other types of gain, such as analog and EMCCD gain, that confound the issue, " she says, referring to electron-multiplying CCD gain.
Another example in defining specs is read noise, she says. For CCDs, read noise was always indicated as "electrons RMS, " or root mean square. With the advent of CMOS cameras, some manufacturers chose to specify read noise as the "median. " The median is generally a lower number than the RMS, which can lead to false expectations.
Subtleties beyond data sheets are involved when comparing different cameras. Even live, head-to-head demos can lead to erroneous interpretations without an understanding of sensors, says Fullerton. Echoing Holst, she says pixel size is an often-overlooked issue in cameras. Bigger pixels will collect more photons in a given time. By adjusting the optics, scientists can let the same photon density fall on pixels of different sizes. Or they can address differences due to pixel size and optics in post-processing. "We' d rather see optical methods, " she says. Otherwise "a camera with a larger pixel can appear to be more sensitive when all you've really got is a bigger 'photon' bucket, " she says.
Holst says that with the QUAREP camera standard in the works, "my hope is that we can help to make it a good standard. " It can be one that pertains to all the needed parameters, such as photon count and resolution, readout noise and pixel size, that are stored on the camera and more generally on the detection side of the microscope. Holst knows his colleagues at Hamamatsu, Andor and Photometrics and says relations between colleagues in the industry are cordial. He is happy that organizations such as QUAREP and others have set up a way for manufacturers and academics to work together.
Holst enjoys the QUAREP discussions and, he says, Strambio-de-Castillia does a "tremendous job" in the camera standards working group. "It's a huge task, " he says, but a good one. All microscope users, he says, need ways to draw the best conclusions from their data without being a camera expert. QuAREP-LiMi fosters a standards dialog between academics and companies. Among other projects, the group is working on standards for cameras in microscopy, says Caterina Strambio-De-Castillia . Credit: uMass Chan Medical School


Complex Hyperbolic Knowledge Graph Embeddings with Fast Fourier Transform

The choice of geometric space for knowledge graph (KG) embeddings can have significant effects on the performance of KG completion tasks. The hyperbolic geometry has been shown to capture the hierarchical patterns due to its tree-like metrics, which addressed the limitations of the Euclidean embedding models. Recent explorations of the complex hyperbolic geometry further improved the hyperbolic embeddings for capturing a variety of hierarchical structures. However, the performance of the hyperbolic KG embedding models for non-transitive relations is still unpromising, while the complex hyperbolic embeddings do not deal with multi-relations. This paper aims to utilize the representation capacity of the complex hyperbolic geometry in multi-relational KG embeddings. To apply the geometric transformations which account for different relations and the attention mechanism in the complex hyperbolic space, we propose to use the fast Fourier transform (FFT) as the conversion between the real and complex hyperbolic space. Constructing the attention-based transformations in the complex space is very challenging, while the proposed Fourier transform-based complex hyperbolic approaches provide a simple and effective solution. Experimental results show that our methods outperform the baselines, including the Euclidean and the real hyperbolic embedding models.

The choice of geometric space for knowledge graph (KG) embeddings can have significant effects on the performance of KG completion tasks. The hyperbolic geometry has been shown to capture the hierarchical patterns due to its tree-like metrics, which addressed the limitations of the Euclidean embedding models. Recent explorations of the complex hyperbolic geometry further improved the hyperbolic embeddings for capturing a variety of hierarchical structures. However, the performance of the hyperbolic KG embedding models for non-transitive relations is still unpromising, while the complex hyperbolic embeddings do not deal with multi-relations. This paper aims to utilize the representation capacity of the complex hyperbolic geometry in multi-relational KG embeddings. To apply the geometric transformations which account for different relations and the attention mechanism in the complex hyperbolic space, we propose to use the fast Fourier transform (FFT) as the conversion between the real and complex hyperbolic space. Constructing the attention-based transformations in the complex space is very challenging, while the proposed Fourier transform-based complex hyperbolic approaches provide a simple and effective solution. Experimental results show that our methods outperform the baselines, including the Euclidean and the real hyperbolic embedding models.

Introduction
Knowledge graph (KG) representation learning is important to the KG inference as well as the downstream tasks (Nickel et al., 2016). It has been noticed that the embedding space has significant effects on the performance of KG completion tasks. Previous works have proposed the KG embedding models in Euclidean space (Bordes et al., 2013;Nickel et al., 2011;, complex Euclidean space (Trouillon et al., 2016;   2019), hyperbolic space (Balazevic et al., 2019;Chami et al., 2020). 1 These models learn the embeddings of the KG entities in the selected geometric spaces and parameterize the relation representations as the geometric transformations, such as translation, rotation, matrix multiplication, etc.
The Euclidean and complex Euclidean embedding models can capture relation properties including symmetry/anti-symmetry, inversion, and composition, but they cannot handle the transitive relations such as hypernymy. Generally, the transitive relation forms a tree-like structure, for which hyperbolic geometry has a more powerful representation capacity than Euclidean geometry because the hyperbolic space can be regarded as a continuous approximation to trees (Krioukov et al., 2010).
However, most real-world graphs with transitivity do not necessarily form exact tree structures since the transitive relations can lead to a globally hierarchical structure with varying local structures, such as multitree structures (Griggs et al., 2012) and taxonomies (Suchanek et al., 2007). Thus, the hyperbolic geometry which resembles tree metrics still has limitations on capturing various and flexible hierarchical structures. To tackle the limitation of hyperbolic embeddings, a recent work (Xiao et al., 2021) proposed to explore the complex hyperbolic geometry to learn the embeddings of hierarchical graphs. Due to the variable negative curvature (Goldman, 1999), the complex hyperbolic space is more flexible in handling varying structures while the tree-like properties are still retained. Despite the remarkable improvements in single transitive relation inference, the complex hyperbolic geometry has not been utilized for multirelational embeddings.
In this paper, we are motivated to make use of the complex hyperbolic geometry's representation superiority in KGs. There are two main challenges in extending the complex hyperbolic embeddings to multiple relations. First, the geometric transformations in complex hyperbolic geometry are complicated and challenging to optimize due to the numerical instabilities, making it difficult to apply the complex geometric transformations for different relations. Second, it is hard to build the neural network unit or layer in the complex domain. Missing the complex attention mechanism would restrict the parameterization capability and make the complex domain-based model difficult to generalize to further downstream tasks.
To address the above problems, we propose a complex hyperbolic KG embedding approach with the fast Fourier transform. Our approach can utilize the representation capacity of the complex hyperbolic geometry as well as the well-developed attention-based geometric transformations as relation parameterization, while we borrow the fast Fourier transform (FFT) and inverse fast Fourier transform (IFFT) to provide the conversion between the real and complex hyperbolic space. We regard the complex hyperbolic embeddings in the unit ball model (a projective geometry-based model to identify the complex hyperbolic space) (Goldman, 1999) and the hyperbolic embeddings in the Poincaré ball model (a model of the real hyperbolic space) (Cannon et al., 1997) as frequency domain and spatial domain respectively. Then FFT and IFFT enable us to convert the embeddings between the two geometric spaces, accomplishing the leverage of real hyperbolic transformations to the complex hyperbolic model. The framework is simple and effective in learning the complex hyperbolic KG representations. Figure 1 summarizes the comparison among embedding spaces for hierarchical patterns and multi-relation properties. In experiments, we evaluate our approach on the KG link prediction task with two popular benchmarks-WN18RR (Bordes et al., 2013) and FB15k-237 (Toutanova and Chen, 2015). Empirical results show that our Fourier transform-based complex hyperbolic KG embedding approach outperforms the baseline models in other geometric spaces.
The code and data of our work are available at https://github.com/HKUST-KnowComp/ ComplexHyperbolicKGE.

Related Work
Euclidean KG embeddings. The traditional KG embedding models first started with the Euclidean geometry because of its convenient vectorial structure and closed-form computations such as distance formula and inner-product. After the occurrence of the translation-based models (Bordes et al., 2013) and bilinear models (Nickel et al., 2011;, several extensions (Wang et al., 2014;Lin et al., 2015;Ji et al., 2015) have been made to further develop the Euclidean methods.
Complex Euclidean KG embeddings. The follow-up works (Trouillon et al., 2016;Hayashi and Shimbo, 2017;Sun et al., 2019) extended the traditional Euclidean models to complex hyperbolic geometry. Specifically, ComplEx (Trouillon et al., 2016) found that the Hermitian dot product can effectively capture anti-symmetric relations while retaining the efficiency benefits of the dot product. RotatE (Sun et al., 2019) defined each relation as a rotation in the complex vector space to infer various relation patterns (symmetry/antisymmetry, inversion, composition). The effectiveness of these models revealed the potential of the complex geometry.
Hyperbolic embeddings. In recent years, the hyperbolic space attracted much attention for representation learning since it can naturally characterize tree structures. The hyperbolic embedding methods have developed from the single transitive relation graphs Kiela, 2017, 2018;Sonthalia and Gilbert, 2020) to multi-relational KGs (Balazevic et al., 2019;Chami et al., 2020). MurP (Balazevic et al., 2019) embedded the hier-archical multi-relational data in the Poincaré ball model and learned relation-specific parameters by Möbius operations. The state-of-the-art hyperbolic KG embedding models are a series of hyperbolic transformation-based models RefH, RotH, and AttH (Chami et al., 2020), which utilize the geometric tree-like property to capture the hierarchical structure naturally while using different geometric transformations as well as attention mechanism to parameterize other relation properties.
Lightweight Euclidean-based models. Based on the hyperbolic embedding model RotH (Chami et al., 2020), Wang et al. (2021) developed two lightweight Euclidean-based models RotL and Rot2L, which simplified the hyperbolic operations while keeping the flexible normalization effect.
Complex hyperbolic embeddings. Since many real-world hierarchically structured data such as taxonomies (Miller, 1995;Suchanek et al., 2007) and multitree networks (Griggs et al., 2012) have varying local structures, they do not ubiquitously match the hyperbolic geometry. Therefore, Xiao et al. (2021) explored the complex hyperbolic space to embed a variety of hierarchical structures. The complex hyperbolic embedding approach improved over the hyperbolic embedding models, but it only focused on the representation of single-relational graphs instead of multi-relational KGs.
Fourier Transform. Fourier transform (Heideman et al., 1984) converts a finite-sequence signal from its temporal or spatial domain to the frequency domain. FFT (Cooley et al., 1969) is a practical algorithm that computes the discrete Fourier transform (DFT) of a sequence. FFT and inverse FFT are widely used for many applications (Rockmore, 2000;Burgess, 2014) for their usefulness in signal processing as well as computation efficiency. They are also used to efficiently perform operations such as convolutions (Smith et al., 1997;Kipf and Welling, 2017) and cross-correlations (Bracewell and Bracewell, 1986;Wang et al., 2018). Hayashi and Shimbo (2019) also introduced the Fourier transform in KGE, where the main idea was to use the block circulant matrices to parameterize relations. While in our work, the Fourier transform is used to transform the entity embeddings between different geometric spaces.

Hyperbolic Geometry
The hyperbolic space is a homogeneous space with constant negative curvature (Cannon et al., 1997). In the hyperbolic space, the volume of a ball grows exponentially with its radius. Contrastively, in the Euclidean space, the curvature is constantly 0, and the volume of a ball grows polynomially with its radius. The exponential volume growth rate enables the hyperbolic space to have powerful representation capability for tree structures since the number of nodes grows exponentially with the depth in a tree, while the Euclidean space is too flat and narrow to embed trees.
The Poincaré Ball Model. To describe the hyperbolic space in mathematical language, there are several models, among which the Poincaré ball model is popular for graph representation (Nickel and Kiela, 2017;Chami et al., 2020) due to the relatively convenient computations.
Denote the Poincaré ball model with con- which represents the open N -dimension ball in the ambient Euclidean space ( · is the Euclidean L 2 norm). By the framework of gyrovector space (Ungar, 2008), the hyperbolic space can be formalized as an approximated vectorial structure, where the Möbius addition (Ganea et al., 2018) is used as the vector addition in P N R : Then the distance function in P N R is given by The practical computations in the hyperbolic space are often implemented using the tangent space. For x ∈ P N R , the associated tangent space T x P N R is an N -dimension Euclidean space containing all tangent vectors passing through x (do Carmo, 1976). The manifold of the Poincaré ball model and the tangent space have closed-form maps to each other, which are defined as the exponential map exp c 0 (v) : T 0 P N R → P N R and the logarithmic map log c 0 (y) :

Complex Hyperbolic Geometry
The complex hyperbolic space is a homogeneous space of variable negative curvature (Goldman, 1999). The complex hyperbolic space also maintains the tree-like exponential volume growth property. From the properties of the complex hyperbolic geometry, we see that the complex hyperbolic space can naturally handle data with diverse local structures because of the non-constant curvature while preserving the tree-like properties to better capture the transitivity (Xiao et al., 2021).
The Unit Ball Model. The complex hyperbolic space's ambient Hermitian vector space C n,1 is the complex Euclidean space C n+1 endowed with some Hermitian form z, w , where z, w ∈ C n+1 . Different choices of the Hermitian form z, w correspond to different models of complex hyperbolic geometry, such as the unit ball model and the Siegel domain model (Parker, 2003). Here we choose the standard Hermitian form which derives the unit ball model: where w denotes the complex conjugate of w.
Then via the projective geometry (Goldman, 1999), the formula of the unit ball model is: 2 B n C = {(z 1 , · · · , z n , 1)||z 1 | 2 + · · · + |z n | 2 < 1}. (6) The metric on B n C is Bergman metric, which takes the formula below in 2-d case: Then the distance function on B n C can be derived from the metric tensor: Although the unit ball model and the Poincaé ball model look similar in mathematical formulae, they have many differences in properties since the complex hyperbolic geometry and hyperbolic geometry are intrinsically different geometries. Not only the variable/constant negative curvature but also their distance functions and the geometric computations vary with each other. 2 Here we denote the dimension as n instead of N as in Section 3.1 since the dimensions of the two models can differ in Fourier transform, which we will see in Section 4.2.

Approach
Given the KG with entity set V = {e j } m j=1 , relation set R = {r j } k j=1 , and triplet set F = {(h, r, t)|h, t ∈ V, r ∈ R}, the link prediction task aims to predict the tail entity t for each test query (h, r). To train the models for a higher-quality inference, we learn the entity embeddings {e j } m j=1 in the unit ball model, while parameterizing the relations by the hyperbolic transformations RotH, RefH, and the hyperbolic attention-based model AttH (Chami et al., 2020). We construct the conversion between the two geometries through Fourier transform. Figure 2 presents the overview of our framework. In this section, we first present the attention-based hyperbolic transformations as relation parameterization, then introduce the Fourier transform as the conversion between complex hyperbolic domain and hyperbolic domain, followed by the details of our framework.

Relation Parameterization by Hyperbolic Transformations and Attention
In our work, we adopt the attention-based hyperbolic transformations developed by Chami et al. (2020) as the relation parameterization in the Poincaré ball model. Here we present the models RotH, RefH, and AttH. RotH and RefH represent rotations and reflections in the hyperbolic space respectively. They can be modeled using the Givens transformation matrices, which take the following formula: Let Θ r ≡ (θ r,j ) j∈{1,..., N 2 } and Φ r ≡ (φ r,j ) j∈{1,..., N 2 } be the relation parameters, where N denotes the dimension of the embedding space, then the hyperbolic rotation and reflection are parameterized by the block-diagonal Givens matrices: ). (11) Thus, given a query (h, r), RotH and RefH apply hyperbolic rotation and reflection with relationspecific parameters r to the head embeddings h ∈ P N R , and then get the query embeddings: In order to handle multiple relation properties, h ∈ ℬ n ℂh ∈ 2(n−1) ℝq ∈ 2(n−1) Figure 2: The inference process for a query (h, r) in our proposed complex hyperbolic KG embedding framework. h andh are the head entity embeddings in different spaces. q andq are the query embeddings in different spaces. B n C denotes the n-dimension unit ball model in the complex hyperbolic space while P 2(n−1) R denotes the 2(n − 1)dimension Poincaré ball model in the hyperbolic space.
AttH combines the above two representations using the hyperbolic attention and adding a hyperbolic translation r r by Möbius addition (Eq. (1)): AttH(h, r) = Att(RotH(h, r), RefH(h, r); a r )⊕ cr r r , (13) where c r is the curvature parameter of r. RotH, RefH, and AttH leverage the trainable curvature so that each relation has its own curvature parameterization. The hyperbolic attention is constructed from the exponential map (Eq. (3)) of the average in the tangent space (Chami et al., 2019;Liu et al., 2019). More details about the hyperbolic attention mechanism can be referred to (Chami et al., 2020).

Conversion by Fourier Transform
The orthonormal Discrete Fourier Transform (DFT) F and its inverse (IDFT) F −1 between two finite complex-valued sequences {x p } N −1 p=0 and {z q } N −1 q=0 take the following formulae: x In our models, we transform the unit ball embeddings z ∈ B n C to the Poincaré ball embeddings x ∈ P N R back and forth. Note that the Poincaré ball embeddings x = {x 0 , . . . , x N −1 } are all real numbers, then F{x} is symmetric: z q = z −q mod N , ∀q ∈ {0, . . . , N − 1}. The dimension N is even because of the construction of diagonal Givens transformations (Eqs. (10) and (11)). Then it follows that z 0 and z N 2 are realvalued, and the remainder of F{x} is completely specified by just N 2 − 1 complex numbers. Therefore, in practical algorithms, we set N = 2(n − 1), i.e., we use the first N 2 + 1 elements {z 0 , . . . , z N 2 } as the transformed unit ball embeddings.
We notice that the Fourier transform is not simply a conversion technique between complex and real domains. Performing circular convolutions in one domain equals the multiplication in another domain (Rader, 1972;Smith et al., 1997): Its effectiveness provides useful transforms, while its practicability is guaranteed by FFT and IFFT, where the fast Fourier algorithms can reduce the computing complexity from O(N 2 ) to O(N log N ) (Cooley and Tukey, 1965).

Complex Hyperbolic Embeddings with Fourier Transform
For a query (h, r), Figure 2 briefly describes the inference process in our framework. The head embedding h ∈ B n C is in the n-dimension unit ball model. We apply inverse Fourier transform (Eq. (15)) to h and get the transformed head embeddings in the 2(n − 1)-dimension Poincaré ball modelh ∈ P 2(n−1) R :h = F −1 {h}. Then we can apply RotH, RefH (Eq. (12)), and AttH (Eq. (13)) to get the query embeddingq: where ModelH = {RotH, RefH, AttH} represents the corresponding hyperbolic embedding model. The query embeddingq then gets transformed back to the unit ball model by Fourier transform (Eq. (14)): q = F{q}.
Finally, we use the following score function (Balazevic et al., 2019) to measure the likelihood of a triplet (h, r, t): where d B (q, t) is the unit ball model distance (Eq. (8)) between the tail embeddings t and the query embeddings q computed by the above procedures. b h and b t are bias terms of the head and tail entity. The model learns the embeddings by maximizing the score functions of the training triplets, i.e., making the query embeddings of (h, r) close with its ground truth tail embeddings. The score function is also used to predict the test data.
In summary, our model parameters include the entity parameters: {e j } m j=1 ∈ B n C (embeddings), {b j } m j=1 (biases); and the relation parameters: Θ r (rotations), Φ r (reflections), r r (translations), a r (attention), c r (curvature). The FFT and IFFT can be computed very efficiently, so our models have almost the same computation cost with the base models RotH, RefH, and AttH, while we utilize a more powerful representation geometry to improve the embedding quality.

Experiments
In this section, we evaluate our approaches on the KG link prediction task. We show that our complex hyperbolic embedding models outperform the baseline methods based on other geometric spaces.

Data
We use two widely-used KG benchmarks to evaluate the embedding models. The data statistics are provided in Table 1. The global graph curvature ξ G (Gu et al., 2019) is provided in (Chami et al., 2020), which is a distance-based measure to estimate the tree-likeness of graphs. A lower ξ G corresponds to a more tree-like graph.
WN18RR. WN18RR (Bordes et al., 2013) is a knowledge graph dataset created from WN18, which is a subset of WordNet (Miller, 1995). Word-Net is a large lexical database with hypernymy relation, so WN18RR inherits the underlying hierarchical structure.
FB15k-237. FB15k-237 (Toutanova and Chen, 2015) is a knowledge graph dataset created from FB15k, which is derived from Freebase. Compared with WN18RR, FB15k-237 has much more relations and various relation properties, resulting in a more flexible structure, which can be reflected by the larger ξ G .
We follow the train-valid-test data splitting of previous works (Chami et al., 2020;Wang et al., 2021), where # train-valid-test triplets are 86, 134 for WN18RR and 272,466 for FB15k-237. The data can be obtained in the public repository of (Chami et al., 2020). 3

Training and Evaluation
For the baselines, we either take the results from the original papers (Chami et al., 2020;Wang et al., 2021) (Table 2) or use their released best hyperparameters as well as their open-source codes to train their models (Table 3, 4, and 5). For our approaches, we tune the hyperparameters by grid search on each validation set in 32-dimension complex hyperbolic space, which are given in Appendix A. Our embedding models are trained by optimizing the full cross-entropy loss with uniform negative sampling. We conduct all the experiments on four NVIDIA GTX 1080Ti GPUs with 11GB memory each.
We use the mean reciprocal rank (MRR) and the proportion of correct types that rank no larger than N (Hits@N) as our evaluation metrics, which are widely used for evaluating link prediction. We follow the filtered evaluation setting (Bordes et al., 2013) to filter out the true triplets during evaluation. In all experiments, each running is executed five times and the mean values of results are reported. Table 2 presents the results in 32-dimension embedding spaces. We strictly follow the experimental setting and data splitting of the previous works (Chami et al., 2020;Wang et al., 2021). The results of the baselines are taken from the original papers, where RotL and Rot2L do not report the Hits@3 scores, thus we leave them blank.   The results show that our Fourier transformbased complex hyperbolic approaches have the best performance on the link prediction task, demonstrating the powerful representation capacity of the complex hyperbolic geometry and the effectiveness of Fourier transform. Specifically, FFTRotH achieves the best results on WN18RR, while FF-TAttH outperforms other methods on FB15k-237. The relations in WN18RR typically have transitivity property, in which case the hyperbolic rotation takes more advantages. FB15k-237 is a more challenging link prediction dataset since it has more relations and varying structures as well as a larger scale of triplets. Therefore, the attention mechanism helps to generalize the hyperbolic transformations to multiple relation properties.

Overall Results
From Table 2, we see that the traditional complex Euclidean models  do not have competitive performance with the hyperbolic KG embedding models or their Euclidean analogues. The hyperbolic methods (MuRP, RefH, RotH, and AttH) have better results than their Euclidean analogues (MuRE, RefE, RotE, and AttE), revealing the improvements of the hyperbolic geometry over Euclidean geometry in lowdimensional KG representation. RotL replaced the Möbius addition of RotH with a new flexible addition operation, while Rot2L further utilizes two stacked rotation-translation layers in the Euclidean space. The two Euclidean-based methods outperform their base model RotH by adapting a lightweight architecture. However, they still cannot achieve as promising results as the complex hyperbolic embedding approaches.

Exploring the Relations
In Section 5.2, we see that the overall results of Fourier transform-based complex hyperbolic methods surpass their corresponding hyperbolic methods. Here we explore their performance on each relation of WN18RR. For each relation, we give their statistics of Krackhardt hierarchy score (Khs G ) (Balazevic et al., 2019) and estimated graph curvature ξ G (Chami et al., 2019). Higher Khs G and lower ξ G mean more tree-like, i.e., the relation is more transitive. We report the Hits@10 scores in Table 3.
We find that for most relations, FFT complex hyperbolic methods outperform hyperbolic methods significantly. For the transitive relations such as member meronym, hypernym, has part, etc, rotation has much better results than reflection. This phenomenon is consistent with the analysis of previous work (Chami et al., 2020), where they found hyperbolic rotations work better on anti-symmetric relations while hyperbolic reflections encode symmetric relations better. Transitivity fulfills anti-symmetry naturally, so rotation gains higher scores (RotH>RefH, FFTRotH>FFTRefH). For the symmetric relation such as also see, reflection outperforms rotation (RefH>RotH, FFTRefH>FFTRotH). Since most relations in WN18RR exhibit transitivity, the rota-tion models have better performance than the reflection models in overall results ( Table 2). Regardless of the relation properties, our approaches improve the corresponding hyperbolic methods largely, except for the relations with few test triplets such as similar to and verb group, where they all have close-to-1 Hits@10 results.

Exploring the Embedding Dimensions
In this section, we explore the performance of Fourier transform-based complex hyperbolic approaches and the corresponding hyperbolic methods in various embedding dimensions. The results are presented in Table 4 and 5. We find that when the embedding dimension is small, the complex hyperbolic approaches outperform the hyperbolic base models by a large margin. Remarkably, FFTRotH improves over RotH by around 100% in 8-dimension on WN18RR. With the increase of the embedding dimension, their predictions get more and more similar and gradually converge. The results reveal the effectiveness of our approaches especially in small dimensions, demonstrating the strong representation capacity of complex hyperbolic geometry.

Conclusion and Future Work
In this work, we explore the complex hyperbolic geometry for multi-relational KG embeddings. The whole framework utilizes the Fourier transform as the efficient conversion between geometric spaces. With the aid of the Fourier transform, the complex hyperbolic embeddings can be transformed into the real domain and be capable of applying real hyperbolic transformations, which enables our approach to take the advantages of both the powerful complex hyperbolic geometry and the attention-based real hyperbolic transformations. Experiments show that the Fourier transform-based complex hyperbolic embedding models can effectively learn the KG embeddings and outperform the baseline models of other spaces in the link prediction task. We believe our proposed approach not only provides a novel and interesting representation learning framework for KGs but also potentially inspires the learning algorithms for more general multi-relational data and contributes to improvements on more downstream tasks.

Limitations
Limited improvements in high dimensions. Although our approaches can significantly outperform the baselines in low-dimensional KG embedding setting, we find that our approaches would get converge and have close results with the hyperbolic base models in sufficiently high dimensions. For example, in Table 4, FFTRotH and RotH have the same results in 64-dimension embedding spaces on WN18RR.
This issue has been observed previously (Nickel and Kiela, 2017;Chami et al., 2020), though their comparisons are established between hyperbolic space and Euclidean space. The representation capacity gap between geometric spaces is distinctly revealed in low dimensions. The gap may get eliminated to some extent by increasing the dimension. The complex hyperbolic geometry and hyperbolic geometry usually converge their results in much lower dimensions than Euclidean geometry because of the exponential growth property, resulting in the limited improvements in high dimensions.


Multi-Graph Fusion Networks for Urban Region Embedding

Learning the embeddings for urban regions from human mobility data can reveal the functionality of regions, and then enables the correlated but distinct tasks such as crime prediction. Human mobility data contains rich but abundant information, which yields to the comprehensive region embeddings for cross domain tasks. In this paper, we propose multi-graph fusion networks (MGFN) to enable the cross domain prediction tasks. First, we integrate the graphs with spatio-temporal similarity as mobility patterns through a mobility graph fusion module. Then, in the mobility pattern joint learning module, we design the multi-level cross-attention mechanism to learn the comprehensive embeddings from multiple mobility patterns based on intra-pattern and inter-pattern messages. Finally, we conduct extensive experiments on real-world urban datasets. Experimental results demonstrate that the proposed MGFN outperforms the state-of-the-art methods by up to 12.35% improvement.

Introduction
Revealing urban region embedding aims to learn quantitative representations of regions from multi-sourced data, such as Point-of-Interests (POI), check-in, and human mobility [Wang and Li, 2017]. Human mobility data reflects the human interactions and cooperation, and thus can be used to conduct distinct tasks such as epidemic [Wu et al., 2021], economics [Xu et al., 2020], crime [Xia et al., 2021] prediction, etc.
The cross-domain downstream tasks such as crime prediction and check-in prediction, are used to verify the effectiveness of region embeddings. Existing studies Wang and Li, 2017;Yao et al., 2018] taking all detailed timeseries mobility records as input, could merely learn a specific representation (e.g., change of traffic flows), rather than generalized urban region embeddings. * These authors contributed equally to this work † Corresponding author: fanxiaoliang@xmu.edu.cn  Figure 1: A motivating example. The complexity of mobility patterns depends on both urban periodicity and regional functionality distribution. For two regions (A is a residential area, and B is a office area), there could be two distinct patterns (i.e., variation, similarity).
Human mobility data contains both abundant information and complex patterns [Dang et al., 2022], which yields to the comprehensive region embeddings for cross domain tasks. For example, Figure 1 (left) shows two repeated patterns, which can be integrated as Pattern 1 (morning peak) and Pattern 2 (weekend) respectively. Figure 1 (right) shows the complexity of mobility patterns that there are two distinct patterns (i.e., variation and similarity). Measuring a generalized region embeddings from abundant human mobility data is challenging: Challenge 1: How to process the fine-grained mobility data to learn a generalized embedding? In our considered scenario, learning from abundant human mobility data may only attain the change of mobility flows, rather than a generalized embedding.
Solution 1: Mobility graph fusion. To attain an effective and generalized embedding from abundant human mobility data, we first approach regions as interactive and interdependent nodes by constructing the human mobility data as mobility multi-graph. Then, we aggregate mobility graphs as selected mobility patterns according to the spatio-temporal distance between any two mobility graphs.
Challenge 2: How to jointly learn from mobility patterns? Training a separate pattern mining model on each of them may not capture comprehensive representation of regional characteristics.
Solution 2: Mobility Pattern Joint Learning. The constructed mobility graphs possess regularized characteristics, which are fully connected, directed, and weighted with multiple edges (i.e., multi-graph). Different from previous graph representation models [Zhang et al., 2020], we take advantage of above characteristics by designing two modules: (1) Intra-pattern message passing, which utilizes structural information inside each graph to learn a local embedding; and (2) Inter-pattern message cross attention, which conducts attention mechanism among different graphs to jointly learn comprehensive region embeddings.
The major contributions of this paper are: • We study the urban region representation problem on fine-grained human mobility data, and propose a mobility graph fusion module with spatio-temporal dependencies where redundant graphs are integrated as patterns. • We propose a mobility pattern joint learning module, which learns the region embedding from intra-pattern message and inter-pattern message simultaneously in a new manner, with the hope that the cross-graph information can mutually enhance each other. • Extensive experimental results show that our mobility graph fusion method can effectively uncover the complex mobility patterns. And our method outperforms state-of-the-art baselines up to 13.11% in crime and check-in prediction tasks in terms of various metrics.

Problem Statement
We provide necessary preliminary concepts in this work, and formalize the problem of urban region embedding. Definition 1 (Mobility Graph). The mobility graph at the time step t is defined as a directed and weighted graph G t = (V, E t ), where V denotes the node set with node v i ∈ V representing region v i , and E t denotes the edge set with edge e t ij = (v i , v j , ω t ij ) ∈ E t representing the number of people ω ij move from urban region v i to v j at time t. Definition 2 (Mobility Multi-graph). It is defined as a directed and weighted multi-graph G = ∪ T −1 t=0 {G t = (V, E t )}, where G t is a mobility graph at time t, and V denotes the node set that corresponds to regions, and E t denotes the edge set that corresponds to mobility condition at time t. Definition 3 (Mobility Pattern). The mobility patterns G = {G 0 , G 1 , ..., G N −1 } are the result of fusing similar mobility multi-graph. A pattern G k is also a directed and weighted graph with the same node set V as mobility multi-graph. Definition 4 (Urban Region Embedding). Given mobility multi-graph G, the goal of urban region embedding is to learn a mapping function φ : v i → R d to generate low dimensional embeddingĤ ∈ R |V |×d of each region v i ∈ V , where d represents the dimension of urban region embeddings.

Methodology
In this section, we first introduce the mobility graph fusion module, in which we propose a novel mobility graph distance to measure the similarity between different mobility graphs. Then, we present an effective mobility pattern joint learning module, which contains intra-pattern message passing and inter-pattern message cross attention to capture comprehensive regional characterise by mobility patterns.

MGD Calculation
Agglomerative Clustering Figure 2: MGFN Framework. The architecture transforms human mobility patterns into representation abilities for downstream tasks (e.g., crime, check-in prediction). Our framework consists of two modules: 1) Mobility Graph Fusion module where time-series multi-graph are fused by a Mobility Graph Distance (MGD) measurement method; and 2) Mobility Pattern Joint Learning module (detailed in Figure 3) which learns the region embedding by both intra-pattern message and inter-pattern message.

Mobility Graph Fusion
Human mobility reveals the functions and properties of urban regions [Wang and Li, 2017]. Our intuition is that mobility patterns are able to describe the urban region functionality thus in favour of learning the generalized representation. For example, estimate whether a region is work area or residential area according to the human mobility direction during the morning peak hours (i.e., 7-9 a.m.). Therefore, instead of learning how human mobility changes, we model the problem as time-series mobility multi-graph fusion (MGF) to extract the mobility patterns. First, we define mobility graph distance (MGD) to calculate the distance between mobility graphs, and apply clustering methods with MGD to cluster similar mobility graphs. Second, in each cluster, we aggregate edges in all mobility graphs to form a mobility pattern.

Spatial Structure Distance on Mobility Graph
Data with similar mean and variance may have higher similarity. Specifically, for a mobility graph G, we assume that the weight w of edge e = (u, v, w) is sampled from a Gaussian distribution, and calculate its mean µ G and variance σ G : Then, the mean distance and variance distance between the mobility graph G a and G b are expressed as: It is not sufficient to only compare the mean and variance. For example, The mean and variance of the morning and evening peak hours are similar, but their destinations are different (working and residential areas, respectively). Specifically, to pay attention to flow imbalance of two regions, we first propose the unidirectional flow distance: where U niF Then, to highlight the high-weight edges in mobility graph G t , we encode G t as a spatial structure label matrix E t , where each element E t ij represents whether the weight ω t ij of edge e t ij in G t is large enough: where µ ij = 1 T T t=1 µ t ij represents the mean value of edge weight between node v i and v j over the time series.
Afterwards, the spatial structure encoding distance between mobility graphs G a and G b is defined as follows: where ⊕ is the xor operation.

Temporal Aggregation with Mobility Graph Distance
After calculating the distances between mobility graphs, considering mobility graphs with close temporal distance are similar, we take temporal similarity into account. We define mobility graph distance (MGD) between mobility graphs G a and G b as the sum of above distance weighted by the temporal similarity with non-linearity, given as follows: where c i is the weight of i-th distance, D i could be D mean , D var , D unif , D ss , M(·) denotes the normalization function such as MinMaxScaler, Z(·) is an activation function. ∆t denotes the time interval between G a and G b . Finally, we calculate the distance between mobility graphs through MGD, and use the clustering method (i.e., hierarchical cluster) to aggregate mobility graphs with different patterns thus to generate mobility patterns G.

Mobility Pattern Joint Learning
In order to learn the underlying information of urban regions from mobility patterns, we present a mobility pattern joint learning module as shown in Figure 3. The framework mainly consists of two parts: intra-pattern message passing and interpattern message cross attention. In the first part, the region hidden representations are updated by intra-pattern message propagating and aggregating in each mobility pattern thus extracting the spatial correlations between regions. In the second part, the cross-attention mechanism is used to integrate the inter-pattern message between the different mobility patterns for each region. Comprehensive embeddings output by two parts with residual connections [He et al., 2016] are integrated by a fully connected layer to generate the final region embeddings.

Inter-Pattern Message Cross Attention
Inter-pattern message

Mobility Patterns
Figure 3: The architecture of mobility pattern joint learning module (left) mainly consists: 1) intra-pattern massage passing (upper right), 2) inter-pattern message cross attention (down right). The former aggregates intra-pattern message to generate region embeddings in N patterns. The latter obtains a fused region embeddings by attention mechanism using inter-pattern message.

Intra-Pattern Message Passing
The property of an urban region is affected by other regions with different impacts due to the spatial correlations. We assume that such impact is highly correlated to the human mobility condition of a region. To capture the spatial correlations, inspired by [Gilmer et al., 2017], we design a intrapattern message passing layer to propagate the inner flow messages between different regions in each mobility pattern.
This part takes mobility patterns G as input. We initialize the 0 th -layer hidden representations of regions v i in mobility pattern G k as input region features x k vi , i.e.: (0) h k vi = x k vi . Considering the mobility flow from region v j to region v i , inspired by [Veličković et al., 2017], we compute the message sent along the mobility flow edge v j → v i by self-attention mechanism. The message function is defined as follows: where ·, · is inner product, W q p and W k p are two trainable projection matrices, and N (v i ) is neighbor region set of v i . Here, the message from region v j to v i is also attention score. Afterwards, region v i aggregates the messages sent by its neighbor regions N (v i ), and updates its hidden representation by a weighed sum from N (v i ), given as follows.
where (l) W v p is a learnable projection matrix in l th layer.
Here, as the mobility pattern is a directed complete graph, the neighbors of each region are all the regions.
To stabilize the learning process and learn information at different conceptual levels, we extend the self-attention mechanism to be multi-head ones [Vaswani et al., 2017]. Specifically, we concatenate F parallel attention message functions with different learnable projections: where || represents concatenation operation, and (f ) m k vivj represents the attention score calculated by the message function in the f th head attention.
Taking the importance of mobility directions and the difference between in-flow and out-flow mobility for a region into account, we divide each mobility pattern G k into two parts: source mobility pattern G s k and target mobility pattern G t k . Here, we regard the out-flow and in-flow mobility as node features of source intra-pattern X s k and target intra-pattern X t k , and apply intra-message passing layer in these two type of patterns, respectively, where X s k = X t k . To fuse these two region representations, we project the concatenation of them to generate hidden representation of v i : } extracting spatial dependency of N mobility patterns are generated by stacking L intra-pattern message passing layers.

Inter-Pattern Message Cross Attention
Intra-pattern message passing provides a robust mechanism for capturing the spatial correlations between regions in each mobility pattern. For learning the cross interactions between different mobility patterns for a region, we allow region to interact across mobility patterns via a self-attention mechanism [Vaswani et al., 2017].
Considering the region v i in mobility pattern G a and G b , let the node features in G a and G b are h a vi and h b vi , respectively. Then, for every such pair, we compute the correlation between G a and G b using attention as follows: where W q c and W k c are two trainable projection matrices, and the attention score α vi ab reveals how G a attends to the features of region v i of G b . Afterwards, we compute an interpattern message for the region v i of mobility pattern G a by a weighed sum, where the multi-head attention is applied again: where W v c is a learnable projection matrix. Finally, the fused region embedding of v i is updated by aggregating the inter-pattern message with mean aggregator: Objective Function With the residual connection of intra-pattern message passing, we use a fully connected layer as an output layer to obtain the final region embeddingsĥ vi : Following [Wang and Li, 2017], we use region embeddings to estimate the distribution of mobility, and learn the embedding by minimizing the difference between the true distribution and the estimated distribution. Given the source v i , we calculate the transition probability of destination v j : Then, given the region embeddingĥ vi ,ĥ vj for region v i , v j , we estimate the transition probability: Finally, the objective function can expressed as:

Evaluation
This section aims to answer the following research questions: RQ1 How is the performance of out MGFN as compared to various state-of-the-art methods? RQ2 How do different components (e.g., mobility graph fusion, mobility pattern joint learning) affect the results? RQ3 Can the proposed mobility graph fusion module really discover mobility patterns? What are its advantages compared with other methods? RQ4 Why did other models perform worse than ours? Is it true that the other methods learned how traffic flow changes? (as we assume in Section 1)  Parameter Settings Following [Zhang et al., 2020], the dimension of region embeddings d is 96. In mobility graph fusion module, the weight c i in MGD is set as 1, and the number of mobility patterns N is set as 7. In mobility pattern joint learning module, the number of layers L is set as 1.

Performance Comparison (RQ1)
For regression tasks (i.e., crime, check-in), we apply the Lasso regression [Tibshirani, 1996] with metrics of Mean Absolute Error (MAE), Root Mean Square Error (RMSE) and coefficient of determination (R 2 ). For the clustering task (i.e., land usage classification), we use K-means to cluster region embeddings with Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI) with settings in [Yao et al., 2018]. Table 1 shows the results of crime prediction, land usage classification and check-in count prediction. We observe that: (1) urban region embedding approaches outperform traditional graph embedding methods, and graph modeling methods (i.e., MG-FN, MVURE) generally perform better than HDGE, ZE-Mob and MV-PN, indicating the spatial dependency between regions is a necessity for urban region embedding; and (2) our MGFN with only human mobility data outperforms the second best model MVURE with multisourced data (POI, check-in, mobility, etc.) and achieves up to 13.11% improvement in terms of R 2 in the check-in prediction task. It is noted that multi-sourced data used in MVURE is always unreachable or accompanied by many noise data in real urban application.   Figure 5: Comparison of clustering results using different distances. The x-axis represents hour of a day, and the y-axis is the day of a month. Each sub-figure represents the result of a measurement, respectively. Each color represents a certain pattern corresponding to the law of human mobility. Compared with other measurements, only MGD could effectively identify important patterns such as morning peaks (red block, from 7 to 9 am for week-days), weekends late night (purple block from 12 pm to 2 am for week-ends), etc.

Model Ablation Study (RQ2)
To further investigate the effect of each component in our model, we compare MGFN with its three variants by removing multi graph fusion module, intra-pattern message passing and inter-pattern message cross attention in mobility pattern joint learning module from our method, which are named as MGFN-NF, respectively. Figure 4 shows the MAE, ARI and RMSE results of MGFN and its variants in crime prediction, land usage classification and check-in prediction tasks respectively. We observe that MGFN performs better than MGFN-NF, demonstrating that the MGF module effectively eases the redundant temporal information for learning more general representations of urban regions. Moreover, MGFN consistently outperforms MGFN-NP and MGFN-NC, which indicates the effectiveness of intra message passing and aggregating between nodes in each mobility pattern and inter messages fusion between mobility patterns in modeling the complex spatial correlations.

Graph Similarity Measurement (RQ3)
To intuitively evaluate the performance of the proposed Mobility Graph Fusion module (Section 3.1), we visualize the mobility patterns extracted by our multi-graph distance (MGD) measurement compared with three measures in Section 3.1 including Mean, Std, and Uniflow using hierarchical  clustering. Specifically, in Figure 5, a certain color represents a specific pattern corresponding to the law of human mobility. We observe that different from other measures, our MGD ( Figure 5.d) is able to distinguish patterns of both morning/evening peaks and working days/weekends effectively, due to our integrated considerations with spatio-temporal information. We argue that this improvement is beneficial to enabling the cross-domain prediction (i.e., from traffic prediction to crime prediction) by uncovering the dynamic correlations contained in urban regional functionality.

Generalization Ability of MGFN (RQ4)
To show the generalization ability of our method, we compare our MGFN with other three methods on both supervised task (i.e., mobility prediction) and cross-domain task (i.e., crime prediction) in Figure 6. Other methods perform poorly on cross-domain tasks because they learn how traffic changes rather than a generalized region representation. Moreover, after removed MGF, the generalization performance is reduced by about 20%, which shows the importance of MGF.

Related Works
Graph Representation Learning Graph embedding aims to learn a low-dimensional vector by mapping the characteristics of nodes to a low-dimensional vector space so that the proximities of nodes can be well preserved [Cui et al., 2018]. Early works devote to learn the shallow representations by graph factorization approaches [Belkin and Niyogi, 2001] relying on spectral embedding from graph Laplacian and skip-gram based methods [Perozzi et al., 2014;Grover and Leskovec, 2016;Tang et al., 2015] learned by random walk objectives. More recently, graph neural networks (GNNs) have become a widely used tool for graph embedding [Veličković et al., 2017;Gilmer et al., 2017].
Region Representation Learning Several strategies have been studied to learn the representation of regions. The first strategy learns embeddings from time-series human mobility data. HDGE [Wang and Li, 2017] uses fine-grained human mobility to construct flow graph, and learn the region embedding at different times. ZE-mob [Yao et al., 2018] regards the region as a word and the mobility event as context, and learn the embedding via a word embedding method. The second strategy learns embeddings from multi-view cross-geotype(region and other spatio-temporal items) correlations.  take into account both intra-region structural information and inter-region spatial auto-correlations. Zhang et al.
[2020] use a cross-view information sharing method to learn comprehensive region embeddings.

Conclusion
In this paper, we focus on learning generalized embeddings to enable cross domain urban computing tasks. We proposed: (1) a novel mobility graph fusion method where redundant graphs are integrated as patterns; and (2) a novel mobility pattern joint learning method to enable the cross graph embeddings that mutually enhance each other and provide more effective representation for downstream tasks. Extensive experiments on real-world mobility data show the proposed MGFN outperforms all baseline methods. Besides, in-depth analysis reveals insightful observations, e.g., Late nights and evenings on weekends show a different pattern from workdays. In future, we will extend our framework to other downstream tasks (e.g., house price prediction).