#  EduChat: A Large-Scale Language Model-based Chatbot System
for Intelligent Education

Yuhao Dan1∗, Zhikai Lei1∗, Yiyang Gu1, Yong Li1, Jianghao Yin1,
Jiaju Lin1, Linhao Ye1, Zhiyan Tie1, Yougen Zhou1, Yilei Wang2, Aimin Zhou1,2,
Ze Zhou4 Qin Chen1† , Jie Zhou1 , Liang He1 , Xipeng Qiu3
1 School of Computer Science and Technology, East China Normal University,
Shanghai, China
2 Institute of AI for Education, ECNU, Shanghai, China
3 School of Computer Science, Fudan University, Shanghai, China
4 ZhuQingTing Data Technology (Zhejiang) Co., Ltd., Zhejiang, China
∗ Equal contribution.† Corresponding author.

###### Abstract

EduChat111https://www.educhat.top/ is a large-scale language model (LLM)-based
chatbot system in the education domain. Its goal is to support personalized,
fair, and compassionate intelligent education, serving teachers, students, and
parents. Guided by theories from psychology and education, it further
strengthens educational functions such as open question answering, essay
assessment, Socratic teaching, and emotional support based on the existing
basic LLMs. Particularly, we learn domain-specific knowledge by pre-training
on the educational corpus and stimulate various skills with tool use by fine-
tuning on designed system prompts and instructions. Currently, EduChat is
available online as an open-source project, with its code, data, and model
parameters available on platforms (e.g., GitHub222https://github.com/icalk-
nlp/EduChat, Hugging Face333https://huggingface.co/ecnu-icalk). We also
prepare a demonstration of its capabilities
online444https://vimeo.com/851004454?share=copy. This initiative aims to
promote research and applications of LLMs for intelligent education.

##  1 Introduction

Recently, large-scale language models (LLMs), such as ChatGPT Schulman et al.
(2022), LLaMa Touvron et al. (2023a), have achieved great success in the field
of natural language processing Zhou et al. (2023b). LLMs obtained the ability
of reasoning, long-range context modeling, and task generalization by training
on large-scale textual corpus with some strategies, such as code pre-training
(Chen et al., 2021), instruction tuning (Wei et al., 2022), and reinforcement
learning from human feedback (RLHF) (Stiennon et al., 2020). With the advent
of LLMs, they have the potential to revolutionize intelligent education by
providing personalized, comprehensive, and timely support to teachers,
students, and parents.

However, there are several challenges of applying LLMs into education domain.
One challenge (C1) is that there is still a gap between the LLMs and the
educational expert since LLMs are pre-trained on the general corpus, which
lack sufficient educational knowledge and can not align well with real
scenarios (e.g., essay assessment). The other challenge (C2) is that the
knowledge in the field of education is updating, while LLMs can not learn up-
to-date knowledge due to the training mechanism. Moreover, LLMs suffer from
the hallucination problem, and may generate responses that are not truthful.

To address these problems, we propose EduChat, an LLM-based chatbot system for
intelligent education. For C1, we pre-train LLMs on a large number of
educational books (e.g., psychology, ancient poetry) and 4 million cleaned
diverse instructions to learn the fundamental knowledge. Then, we fine-tune
the model on 500 thousand high-quality customized instructions to activate
education-specific functions (e.g., essay assessment, Socratic teaching and
emotional support), by aligning with the feedbacks from psychology experts and
frontline teachers. For C2, we explore a retrieval-augmented technology, which
enables LLMs to automatically judge the helpfulness of the retrieved
information, and generate the response based on the relevant information and
knowledge stored in LLMs. In this way, our EduChat can access the latest
information from the internet, ensuring that the responses are accurate and
credible. As an open-source project, EduChat improves the performance of
education-specific functions while maintaining comparable foundational
capabilities to other large-scale models with equivalent parameter size. The
main contributions are as follows:

  * •

We explore the potential of incorporating theories of psychology and education
into LLMs, which sheds light on how to adapt general LLMs to specific domains;

  * •

Diverse system prompts and instructions are designed to control the tool use
and stimulate different skills, which alleviates the problem of hallucination
and is more applicable in real education scenarios;

  * •

We develop and release the EduChat system with various educational functions,
thus developers and researchers can help speed up the research and
applications of intelligent education.

##  2 Related Work

Recently, LLMs like ChatGPT Schulman et al. (2022), ChatGLM Du et al. (2022),
and LLaMA2-Chat Touvron et al. (2023b) have emerged as a breakthrough
technology in natural language processing, achieving strong performance on
language generation and understanding through pre-training on massive text and
instruction tuning.

While LLMs demonstrate impressive capabilities in general domains, their lack
of subject-matter expertise becomes apparent when applied to specialized
verticals. For instance, we can find specialized language models catering to
various domains, such as ChatDoctor Li et al. (2023) and HuaTuoGPT Zhang et
al. (2023b) in healthcare, FinGPT Yang et al. (2023) in finance, and ChatLaw
Cui et al. (2023) in the legal domain. These niche fields inherently
necessitate models to possess comprehensive domain knowledge to address
relevant queries, especially when assisting real users in practical scenarios.
In education, Baladn et al. (2023) tune open-source LLMs for generating better
teacher responses in BEA 2023 Shared Task Tack et al. (2023). But challenges
still exist, such as the lack of domain knowledge in general LLMs and the
necessity for them to align with educational abilities (e.g., essay
assessment, emotional support, and Socratic teaching). EduChat is pre-trained
on a diverse education corpus to ensure the alignment of EduChat with
educational abilities.

##  3 Core Functions of EduChat

#### Retrieval-Augmented Open Question Answering (QA)

The education domain demands high accuracy and real-time updates regarding
knowledge and related policies. However, existing generative LLMs suffer from
issues like fabricating information and lagging behind in knowledge updates.
To address this, we explore retrieval-augmented open QA methods. By utilizing
real-time updated corpora from the internet as an external knowledge source,
we enable LLMs to autonomously assess the relevance of retrieved information
to answer a given question and decide which information to incorporate for
generating responses. Through extensive experimental analysis, we discover
that our model exhibits significant advantages over general LLMs in terms of
eliminating fabrications and maintaining up-to-date knowledge.

#### Fine-grained Essay Assessment

In essay assessment, teachers meticulously annotate grammar errors, provide
scores, and offer feedback on standout sentences. Existing language models
often have coarse granularity in grading, limiting students’ writing skill
improvement. Our research focuses on more fine-grained and comprehensive essay
assessment. Combining frontline teaching professionals’ expertise, we provide
overall scores, aspect-level ratings, and detailed comments on content,
expression, paragraph, and overall evaluation. Our model can identify standout
sentences, highlighting strengths and areas for improvement, enabling
personalized guidance for students’ essay writing skills. This ensures timely
and professional support in all aspects of writing.

#### Socratic Teaching

We focus on developing Socratic teaching capabilities in LLMs rather than
providing direct answers to students. We adopt the Socratic dialogue method,
engaging in multi-step question-and-answer interactions to encourage
independent thinking. By stimulating discussions, debates, evaluations, and
analyses, we aim to foster advanced cognitive skills and cultivate students’
autonomy in learning. Our ultimate goal is to enhance critical thinking and
innovation abilities to their fullest extent.

#### Psychology-based Emotional Support

Adolescents and children face more severe psychological pressures due to their
immature cognitive development. Whereas, current LLMs usually provide generic
advice, which can not well fit the specific emotional problem. To address
this, we develop a psychological inquiry framework based on emotion
psychology, such as Rational Emotive Behavior Therapy (REBT) and the ABC
theory Ellis (1991). Our fine-tuned model can simulate a psychological
counselor, providing personalized diagnoses and emotional support for users.
EduChat fosters a deeper understanding of users’ emotional states and offers
accurate and professional assistance.

##  4 Data Construction

###  4.1 Pre-training Data

#### Textbooks Data

In our research, we gather a vast amount of educational textbook and online
question bank data from Chinese middle and high school exams for pre-training.
Additionally, we enrich our model with over 70,000 Chinese poetries, providing
detailed information on authors, backgrounds, and poetry appreciation to
enhance its poetry creation and appreciation capabilities. To facilitate
empathetic emotional support dialogues, we carefully select 60 famous works
from hundreds of psychology books. These selected books belong to two main
categories. The first category consists of 15 branches of psychological
theory, including developmental and educational psychology, social psychology,
behavioral psychology, counseling psychology and others. The second category
contains various psychological practices, which offer practical cases of
psychological consultation and emotional support dialogues. By incorporating
the diverse fundamental data into pre-training, our model gains a deeper
understanding of education and psychology, enabling it to generate more
helpful responses.

#### Fundamental Instruction Data

To achieve a more natural human-computer interaction, we collect a large
volume of bilingual instruct tuning data from reputable open-source
repositories like Alpaca555https://github.com/tatsu-lab/stanford_alpaca, BELLE
Ji et al. (2023), GPT4All666https://github.com/nomic-ai/gpt4all, Open-
Assistant777https://github.com/LAION-AI/Open-Assistant,
FLANCoT888https://huggingface.co/datasets/lucasmccabe-
lmi/FLAN_CoT_alpaca_style, and
Firefly999https://github.com/yangjianxin1/Firefly. The data spans various task
types, enabling our models to acquire foundational instruction following
capabilities for diverse instruction types. In addition, we source high-
quality multi-turn dialogue data from MOSS Sun et al. (2023), BELLE Ji et al.
(2023), COIG Zhang et al. (2023a), LIMA Zhou et al. (2023a), and
ShareGPT101010https://huggingface.co/datasets/gozfarb/ShareGPT_
Vicuna_unfiltered. This data covers various dialogue contexts, including role-
playing, creative writing, and code-related discussions, ensuring our models’
competence in engaging and sustaining meaningful multi-turn conversations.

Figure 1: Distribution of educational data.

###  4.2 Fine-tuning Data

To enhance the capability of education, we construct the Educational
Instruction Data for fine-tuning, which covers retrieval-augmented open QA,
emotional support, Socratic teaching and essay assessment. The distribution is
shown in Figure 1.

#### Retrieval-Augmented Open QA Data

To address hallucination and timely knowledge issues in Open QA, we design a
retrieval-augmented open QA technique. We sample high-quality data through
ChatGPT scoring in relevant Open QA and Subject QA datasets. To tackle
irrelevant retrieved content, we introduce self-checking. ChatGPT assesses
whether the retrieval content helps answer the question and then generates the
answer using an self-check, incorporating the useful retrieval content and
questions. To maintain data quality, we manually verify the data during this
process.

Figure 2: The overall framework of EduChat.

#### Emotional Support Data

To overcome the scarcity of Chinese emotional support dialogue data, we adopt
a translation and expansion approach. We translate the widely-used English
emotional support dataset, ESConv Liu et al. (2021), into Chinese as ESConv-
zh. After manual review and cleaning, we simulate multi-agent dialogues based
on various patient scenarios within ESConv-zh and also collect real-life
Chinese psychological counseling consultation data, incorporating patient
information and diagnosis results. By training our models on diverse datasets,
we empower them to provide robust emotional support and act as compassionate
counselors during consultations.

#### Socratic Teaching Data

Teachers play a key role in guiding and encouraging heuristic exploration
rather than just providing answers. To support this, we generate dialogues
simulating the Socratic teaching method by incorporating multi-step Q&A
involving counter-questions, challenges, and inquiries. These dialogues are
manually evaluated for accuracy, fluency, and progression from easy to complex
questions. Integrating this dataset into training equips our model with a
strong capability in Socratic teaching, distinguishing it from other LLMs that
only offer direct answers.

#### Essay Assessment Data

The lack of timely and detailed feedback often hinders students’ writing
improvement. To tackle this issue, we create a high-quality essay assessment
dataset. Initially, we collect essays and employ ChatGPT to evaluate them in
terms of content, expression, and overall quality. To ensure data quality, we
invite pedagogical experts to manually curate the comments. This dataset
empowers EduChat with the ability to provide students with high-quality
feedback, aiding in the enhancement of their writing skills.

###  4.3 Data Preprocessing

To enhance data quality, we conduct semantic-level deduplication on the
dataset. Using the sentence-transformers model (Reimers and Gurevych, 2019),
we obtain sentence embeddings for each data point and calculate cosine
similarity between all pairs of embeddings. For similarities exceeding a
threshold of 0.7, we remove one of the duplicates. We implement the similarity
calculation using CUDA for GPU acceleration, speeding up the process.

Figure 3: Demo of EduChat.

##  5 EduChat

EduChat is an LLM designed for the education domain (Figure 2). We first pre-
train on large-scale education corpus (e.g., textbooks, instructions for
foundational tasks) to learn the domain-specific and foundational knowledge.
We then learn the pedagogical skills by fine-tuning EduChat on task-specific
instruction datasets. Moreover, we leverage online retrieval to enhance the
accuracy and timeliness of knowledge in its responses. To control skills, we
design various system prompts to unlock different scenes with tool usage.

###  5.1 Training Procedure of EduChat

The training of EduChat is mainly divided into two stages: fundamental
capabilities acquisition and educational skills acquisition. In the first
stage, we pre-train the model on educational books and Q&A pairs (detailed in
Section 4.1) to equip it with foundational knowledge across disciplines.
Besides, large-scale instruction tuning and open-domain dialogue datasets are
also incorporated to enable basic instruction following ability and dialogue
ability (detailed in Section 4.2). In the second stage, we develop EduChat’s
pedagogical skills by fine-tuning the model on our carefully curated data,
including retrieval-augmented open QA, emotional support, Socratic teaching
and essay assessment datasets mentioned in Section 4.2.

###  5.2 Online Knowledge Retrieval

Existing generative LLMs all suffer from the issues of generating
hallucinations and outdated information, which is detrimental to an
educational model. To mitigate this problem, we introduce self-check as shown
in Figure 2. Specifically, when online knowledge retrieval is enabled, the
model picks useful retrieval results by asking itself ”Is this helpful for
answering the question?” and append filtered snippets before the dialogue
history.

###  5.3 System Prompt Design

Teachers always utilize various tools with different skills to enhance their
teaching across different subjects. To enable EduChat to emulate an authentic
teacher-student interaction, we carefully craft the system prompt that
consists of personal profile, tool usage and skill selection (see Figure 2).
Detailed settings can be found in Table 2.

1) Personal Profile: To remind the model of its own identity, the system
prompt begins with: ”EduChat is a conversational language model developed by
East China Normal University.”; 2) Tool Usage: To regulate tool availability,
the second part of the system prompt commences with ”EduChat’s tools:”,
listing all tool names and their respective accessibility. For instance, ”Web
search: Enable” indicates the model’s ability to use retrieval, while
”Calculator: Disable” signifies the model’s inability to utilize a calculator;
3) Skill Selection: Teachers in various settings possess unique communication
skills, such as Socratic Teaching or Psychology-based Emotional Support. To
cater to specific scenarios, we include function names at the end of the
system prompt, which activates corresponding abilities based on the scene’s
requirements.

###  5.4 Demonstration

We also develop a user-friendly demo system for EduChat (see Figure 3). Upon
logging in, users can select from various functions, such as Open QA and
Emotional Support, each offering a scene-specific system prompt to activate
the corresponding ability. With this intuitive interface, users can easily
engage in interactive conversations with EduChat to assist students, teachers
and parents. Additionally, the system is designed to be adaptive, continuously
learning from user interactions to further improve its capabilities and
provide more personalized and effective assistance over time.

Figure 4: Cases of retrieval-augmented open QA and socratic teaching.

##  6 Experimental Results

###  6.1 Resutls of C-Eval

Table 1 presents the results of our model on the C-Eval benchmark Huang et al.
(2023), a comprehensive Chinese evaluation suite for foundation models. The
dataset consists of 13,948 multi-choice questions, spanning 52 diverse
disciplines and categorized into four difficulty levels. Analyzing the table,
we observe that our model achieves commendable performance compared to models
with similar parameter scales, such as Chinese Alpaca-13B and WastlackLM.
Notably, both EduChat and Chinese Alpaca-13B are built on the LLaMa-13B base
model. However, EduChat outperforms Chinese Alpaca-13B by over seven points.
Furthermore, our integration of retrieval into LLMs proves to be highly
effective, demonstrating the power of our retrieval-augmented open QA
technique in enhancing model performance.

4 | STEM | Social Science | Humanities | Others | Avg(hard) | Avg
---|---|---|---|---|---|---
GPT-4 | 67.1 | 77.6 | 64.5 | 67.8 | 54.9 | 68.7
ChatGPT | 52.9 | 61.8 | 50.9 | 53.6 | 41.4 | 54.4
Baichuan-13B | 47.0 | 66.8 | 57.3 | 49.8 | 36.7 | 53.6
InternLM-7B | 48.0 | 67.4 | 55.4 | 45.8 | 37.1 | 52.8
ChatGLM2-6B | 48.6 | 60.5 | 51.3 | 49.8 | 37.1 | 51.7
WestlakeLM-19B | 41.6 | 51.0 | 44.3 | 44.5 | 34.9 | 44.6
Baichuan-7B | 38.2 | 52.0 | 46.2 | 39.3 | 31.5 | 42.8
Chinese-Alpaca-33B | 37.0 | 51.6 | 42.3 | 40.3 | 30.3 | 41.6
Chinese-Alpaca-13B | 31.6 | 37.2 | 33.6 | 32.8 | 27.3 | 33.3
EduChat | 36.2 | 50.7 | 42.9 | 37.7 | 28.3 | 40.7
EduChat (w Retrieval) | 43.5 | 59.3 | 53.7 | 46.6 | 33.1 | 49.3
4 |  |  |  |  |  |
Table 1: Results of C-Eval.

###  6.2 Case Studies

Figure 4 shows the cases of our EduChat on retrieval-augmented open QA and
socratic teaching. EduChat can provide precise answer with retrieved relevant
information, and learn to guide the student to solve the problems like a
teacher step by step. For emotional support, EduChat can interact like a
psychological counselor rather than giving the general advice. For space
limitation, we provide more cases of psychology-based emotional support and
fine-grained essay assessment in the Appendix (Figure 5).

##  7 Conclusion

In this paper, we introduce EduChat, an LLM-based chatbot system for
intelligent education. Our goal is to provide personalized, fair, and
compassionate support to teachers, students, and parents. By leveraging
psychology and education theories, we enhance educational functions like open
QA, essay assessment, Socratic teaching, and emotional support. Through pre-
training on educational corpus and fine-tuning with task-specific
instructions, EduChat demonstrates great performance on the C-Eval benchmark.
Overall, EduChat exhibits great potential towards revolutionizing intelligent
education. In future work, we aim to expand EduChat on more functions, such as
career planning, course guidance, question generation and so on.

## References

  * Baladn et al. (2023) Alexis Baladn, Ignacio Sastre, Luis Chiruzzo, and Aiala Ros. 2023.  RETUYT-InCo at BEA 2023 shared task: Tuning open-source LLMs for generating teacher responses.  In _Proceedings of the 18th Workshop on Innovative Use of NLP for Building Educational Applications (BEA 2023)_ , pages 756–765, Toronto, Canada. Association for Computational Linguistics.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_.
  * Cui et al. (2023) Jiaxi Cui, Zongjia Li, Yang Yan, Bohua Chen, and Li Yuan. 2023.  Chatlaw: Open-source legal large language model with integrated external knowledge bases.  _ArXiv_ , abs/2306.16092.
  * Du et al. (2022) Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang. 2022.  Glm: General language model pretraining with autoregressive blank infilling.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 320–335.
  * Ellis (1991) Albert Ellis. 1991.  The revised ABC’s of rational-emotive therapy (RET).  _Journal of Rational-Emotive and Cognitive-Behavior Therapy_ , 9(3):139–172.
  * Huang et al. (2023) Yuzhen Huang, Yuzhuo Bai, Zhihao Zhu, Junlei Zhang, Jinghan Zhang, Tangjun Su, Junteng Liu, Chuancheng Lv, Yikai Zhang, Jiayi Lei, Yao Fu, Maosong Sun, and Junxian He. 2023.  C-eval: A multi-level multi-discipline chinese evaluation suite for foundation models.  _arXiv preprint arXiv:2305.08322_.
  * Ji et al. (2023) Yunjie Ji, Yong Deng, Yan Gong, Yiping Peng, Qiang Niu, Lei Zhang, Baochang Ma, and Xiangang Li. 2023.  Exploring the impact of instruction data scaling on large language models: An empirical study on real-world use cases.  _arXiv preprint arXiv:2303.14742_.
  * Li et al. (2023) Yunxiang Li, Zihan Li, Kai Zhang, Ruilong Dan, Steve Jiang, and You Zhang. 2023\.  Chatdoctor: A medical chat model fine-tuned on a large language model meta-ai (llama) using medical domain knowledge.  _Cureus_ , 15(6).
  * Liu et al. (2021) Siyang Liu, Chujie Zheng, Orianna Demasi, Sahand Sabour, Yu Li, Zhou Yu, Yong Jiang, and Minlie Huang. 2021.  Towards emotional support dialog systems.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3469–3483, Online. Association for Computational Linguistics.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  _arXiv preprint arXiv:1908.10084_.
  * Schulman et al. (2022) John Schulman, B Zoph, C Kim, J Hilton, J Menick, J Weng, JFC Uribe, L Fedus, L Metz, M Pokorny, et al. 2022.  ChatGPT: Optimizing language models for dialogue.  In _OpenAI blog_.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. 2020.  Learning to summarize with human feedback.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 3008–3021.
  * Sun et al. (2023) Tianxiang Sun, Xiaotian Zhang, Zhengfu He, Peng Li, Qinyuan Cheng, Hang Yan, Xiangyang Liu, Yunfan Shao, Qiong Tang, Xingjian Zhao, Ke Chen, Yining Zheng, Zhejian Zhou, Ruixiao Li, Jun Zhan, Yunhua Zhou, Linyang Li, Xiaogui Yang, Lingling Wu, Zhangyue Yin, Xuanjing Huang, and Xipeng Qiu. 2023.  Moss: Training conversational language models from synthetic data.
  * Tack et al. (2023) Anaïs Tack, Ekaterina Kochmar, Zheng Yuan, Serge Bibauw, and Chris Piech. 2023\.  The BEA 2023 shared task on generating AI teacher responses in educational dialogues.  In _Proceedings of the 18th Workshop on Innovative Use of NLP for Building Educational Applications (BEA 2023)_ , pages 785–795, Toronto, Canada. Association for Computational Linguistics.
  * Touvron et al. (2023a) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023a.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Touvron et al. (2023b) Hugo Touvron, Louis Martin, Kevin R. Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Daniel M. Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony S. Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel M. Kloumann, A. V. Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, R. Subramanian, Xia Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zhengxu Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. 2023b.  Llama 2: Open foundation and fine-tuned chat models.  _ArXiv_ , abs/2307.09288.
  * Wei et al. (2022) Jason Wei, Maarten Bosma, Vincent Y. Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M. Dai, and Quoc V. Le. 2022.  Finetuned language models are zero-shot learners.  In _The Tenth International Conference on Learning Representations_.
  * Yang et al. (2023) Hongyang Yang, Xiao-Yang Liu, and Chris Wang. 2023.  Fingpt: Open-source financial large language models.  _ArXiv_ , abs/2306.06031.
  * Zhang et al. (2023a) Ge Zhang, Yemin Shi, Ruibo Liu, Ruibin Yuan, Yizhi Li, Siwei Dong, Yu Shu, Zhaoqun Li, Zekun Wang, Chenghua Lin, Wenhao Huang, and Jie Fu. 2023a.  Chinese open instruction generalist: A preliminary release.
  * Zhang et al. (2023b) Hongbo Zhang, Junying Chen, Feng Jiang, Fei Yu, Zhihong Chen, Jianquan Li, Guimin Chen, Xiangbo Wu, Zhiyi Zhang, Qingying Xiao, Xiang Wan, Benyou Wang, and Haizhou Li. 2023b.  Huatuogpt, towards taming language model to be a doctor.  _ArXiv_ , abs/2305.15075.
  * Zhou et al. (2023a) Chunting Zhou, Pengfei Liu, Puxin Xu, Srini Iyer, Jiao Sun, Yuning Mao, Xuezhe Ma, Avia Efrat, Ping Yu, Lili Yu, Susan Zhang, Gargi Ghosh, Mike Lewis, Luke Zettlemoyer, and Omer Levy. 2023a.  Lima: Less is more for alignment.
  * Zhou et al. (2023b) Jie Zhou, Pei Ke, Xipeng Qiu, Minlie Huang, and Junping Zhang. 2023b.  Chatgpt: Potential, prospects, and limitations.  _Frontiers of Information Technology & Electronic Engineering_, pages 1–6.

| Tool | Skill
---|---|---
| Retrieval | Self-check | General | Psychology | Socrates
Retrieval-Augmented Open QA | True | True | True | False | False
Fine-grained Essay Assessment | True/False | True/False | True | False | False
Psychology-based Emotional Support | False | False | False | True | False
Socratic Teaching | False | False | False | False | True
Table 2: Illustration of system prompt design.  Figure 5: Cases of psychology-
based emotional support and fine-grained essay assessment.


# A Unification Framework for Euclidean and Hyperbolic Graph Neural Networks

Mehrdad Khatir1, Nurendra Choudhary 1,
Sutanay Choudhury2, Khushbu Agarwal2,
1Department of Computer Science, Virginia Tech, Arlington, VA, USA
2Pacific Northwest National Laboratory, Richland, WA, USA
{khatir<EMAIL_ADDRESS>
{sutanay.choudhury<EMAIL_ADDRESS><EMAIL_ADDRESS>Mehrdad Khatir1
Nurendra Choudhary1 Sutanay Choudhury2 Khushbu Agarwal2 Chandan K. Reddy1
1Department of Computer Science, Virginia Tech, Arlington, VA, USA
2Pacific Northwest National Laboratory, Richland, WA, USA
{khatir<EMAIL_ADDRESS>{sutanay.choudhury<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Hyperbolic neural networks are able to capture the inherent hierarchy of graph
datasets, and consequently a powerful choice of GNNs. However, they entangle
multiple incongruent (gyro-)vector spaces within a layer, which makes them
limited in terms of generalization and scalability. In this work, we propose
to use Poincaré disk model as our search space, and apply all approximations
on the disk (as if the disk is a tangent space derived from the origin), and
thus getting rid of all inter-space transformations. Such an approach enables
us to propose a hyperbolic normalization layer, and to further simplify the
entire hyperbolic model to a Euclidean model cascaded with our hyperbolic
normalization layer. We applied our proposed nonlinear hyperbolic
normalization to the current state-of-the-art homogeneous and multi-relational
graph networks. We demonstrate that not only does the model leverage the power
of Euclidean networks such as interpretability and efficient execution of
various model components, but also it outperforms both Euclidean and
hyperbolic counterparts in our benchmarks.

##  1 Introduction

Graph data structures are ubiquitous. There have been several advancements in
graph processing techniques across several domains such as citation networks
Sen et al. (2008), medicine Anderson and May (1992), and e-commerce Choudhary
et al. (2021). Recently, non-Euclidean geometries such as hyperbolic spaces
have shown significant potential in representation learning and graph
prediction Chami et al. (2019). Due to their exponential growth in volume with
respect to radius Krioukov et al. (2010), hyperbolic spaces are able to embed
hierarchical structures with low distortion, i.e., increase in the number of
nodes in a tree with increasing depth is analogous to moving outwards from the
origin in a Poincaré ball (since both grow exponentially). This similarity
enables the hyperbolic space to project the child nodes exponentially further
away from the origin compared to their parents (as shown in Figure 1.a) which
captures hierarchy in the embedding space. There are certain fundamental
questions about hyperbolic models which are yet to be studied. For example,
hyperbolic models operate on completely new manifolds with their own
gyrovector space Ungar (2009) (to be differentiated from the Euclidean vector
space). Because they operate in different manifold, techniques such as dropout
or L1/2 regularization does not guarantee similar behavior. Moreover, while
existing hyperbolic operations Ganea et al. (2018) provide a fair support for
basic sequential neural networks, a correct translation of more complex
Euclidean architectures (such as multi-headed attention networks Vaswani et
al. (2017)) is non-trivial and counter-intuitive, due to the special
properties of Riemannian manifold Shimizu et al. (2021). Finally, hyperbolic
operators are computationally expensive i.e., the number of complex
mathematical operations for each primitive operator limits their scalability
compared to the Euclidean graph neural networks.

(a)

(b)

Figure 1:  (a) Mapping hierarchical data onto a Poincaré ball. Starting with
the root as origin (red), the children are continuously embedded with
exponentially increasing distances. (b) Aggregation of vectors in Euclidean,
Poincaré Ball, and pseudo-Poincaré space (hyperbolic vectors in Euclidean
space). Red points are the aggregation of blue points. Pseudo-Poincaré
paradigm reformulates hyperbolic operations to capture hierarchy in the
Euclidean space.

Traditionally, hyperbolic models use a mixture of hyperbolic geodesics, gyro-
vector space mathematics (e.g. Poincaré disc model combined with Möbius
operations), and tangent space approximations at various points. Instead of
switching between multiple frameworks with potentially incongruent operations,
in this work, we let the Poincaré disk model be our search space and propose
to apply all approximations inplace on the Poincaré disk (i.e. to apply all
tangent space approximations on the disk as if the disk is a tangent space
derived from the origin). This enables us to replace non-scalable gyro-
vector/Möbius operations with a Euclidean approximation, and then simplify the
whole hyperbolic model as a Euclidean model cascaded with a hyperbolic
normalization function. In our approach, we replace all Möbius operations with
Euclidean operations, yet we still work in Riemannian manifold (by using our
proposed hyperbolic normalization layer along with using Riemannian
optimizer), thus, we call it Pseudo-Poincaré framework (figure 1.b).

With our formulations, the trainable parameters lie in the Euclidean space,
hence we can re-use the architectures that already exist for Euclidean
solution space. This leads to the use of inexpensive operators. It also
enables the use of existing well-optimized Euclidean models along with their
hyper-parameter settings tuned for specific tasks. Having the aforementioned
two capabilities, our framework brings the best of two worlds together. For
further evidence, we have applied our formulation to construct new pseudo-
Poincaré variants of $GCN$ Kipf and Welling (2017), $GAT$ Veličković et al.
(2018), and multi-relational graph embedding model $MuR$ Balažević et al.
(2019), $RGCN$ Schlichtkrull et al. (2018) and $GCNII$ Chen et al. (2020) (we
call our variants as $NGCN$, $NGAT$, $NMuR$, $NRGCN$, and $NGCNII$
respectively). We demonstrate that the reformulated variants outperform
several state-of-the-art graph networks on standard graph tasks. Furthermore,
our experiments indicate our pseudo-Poincaré variants benefits from using
regularization methods used in Euclidean counterparts (unlike the traditional
hyperbolic counterparts). We also show the execution speed of our proposed
model to be comparable to that of the Euclidean counterparts, and hence
provides insights for building deeper hyperbolic (pseudo-Poincaré) models.

##  2 Related Work

Research into graph representation learning can be broadly classified into two
categories based on the nature of the underlying graph dataset: (i)
Homogeneous graphs - where the edges connect the nodes but do not have any
underlying information and (ii) Heterogeneous or multi-relational graphs -
where the edges contain information regarding the type of connection or a
complex relation definition. Early research in this area relied on capturing
information from the adjacency matrix through factorization and random walks.
In matrix factorization based approaches Cao et al. (2015), the adjacency
matrix $A$ is factorized into low-dimensional dense matrices $L$ such that
$\|L^{T}L-A\|$ is minimized. In random walk based approaches Grover and
Leskovec (2016); Narayanan et al. (2017), the nodes’ information is aggregated
through message passing over its neighbors through random or metapath
traversal Fu et al. (2020). More recently, the focus has shifted towards
neighborhood aggregation through neural networks, specifically, Graph Neural
Networks (GNNs) Scarselli et al. (2008). In this line of work, several
architectures such as GraphSage Hamilton et al. (2017), GCN Kipf and Welling
(2017), and GAT Veličković et al. (2018) have utilized popular deep learning
frameworks to aggregate information from the nodes’ neighborhood. Concurrently
multi-relational graph neural networks have been developed focusing on
representation learning in knowledge graphs in which the nodes/entities can
have edges/relations of different types. TransE Bordes et al. (2013), DistMult
Yang et al. (2015), RotatE Sun et al. (2019), MuRE Balažević et al. (2019),
RGCN Schlichtkrull et al. (2018) are examples of multi-relational GNNs.

Figure 2:  The top row labeled “Unrolled Deep Hyperbolic Network” presents the
general idea of stacking deep hyperbolic network with $L$ layers. The input to
each layer is passed through a logarithmic map to project onto a Euclidean
space, and following the Euclidean layer computation, the output is projected
back onto the hyperbolic space. The section “Hyperbolic Layers” shows the
operator and function chaining technique. Our methodology shown in the lowest
layer completely avoids the repeated application of these subspace
transformations.

##  3 Hyperbolic Networks

Manifold hypothesis Cayton (2005) suggests that high dimensional data tends to
lie in the vicinity of a low dimensional manifold Fefferman et al. (2016). For
such data, the model in fact learns the manifold to better learn the relation
between the data points. In graph datasets, hierarchical structures are
common, which tend to better align in hyperbolic manifolds. Using the
aforementioned concept, Ganea, et al. Ganea et al. (2018) proposed a
hyperbolic neural networks. Such a network operates in hyperbolic manifolds,
simplifies the search space by omitting the manifold learning process, and
thus, results in more efficient models for graph applications. That work led
to several architectures for representation learning in both homogeneous (HGCN
Chami et al. (2019), HAT Zhang et al. (2021)) and heterogeneous (MuRP
Balažević et al. (2019), HypE Choudhary et al. (2021)) graph datasets. These
architectures primarily utilize the gyrovector space model to formulate the
neural network operations.

###  3.1 Hyperbolic Space

Hyperbolic space is a Riemannian manifold with constant negative curvature.
The coordinates in the hyperbolic space can be represented in several
isometric models such as Beltrami-Klein Model $\mathbb{K}^{n}_{c}$ and
Poincaré Ball $\mathbb{B}^{n}_{c}$. In this paper, we consider the Poincaré
Ball model because it is the most widely used one for hyperbolic networks. In
a Poincaré ball of curvature $c$, simple operations such as vector addition
and scaling are done using Möbius operation (addition $\oplus_{c}$, scalar
multiplication $\otimes_{c}$). More complex operations such as aggregation,
convolution and attention are done in local tangent spaces which requires
transformation between Euclidean and hyperbolic space. For an embedding vector
$x\in\mathbb{R}^{n}$ from point $v$, its corresponding hyperbolic embedding in
the Poincaré ball of curvature $c$, $p\in\mathbb{B}^{n}_{c}$ is calculated
with the exponential map as:

$p=\exp_{v}^{c}(x)=v\oplus_{c}({tanh(\frac{\lambda_{v}||x||}{2})}\frac{x}{||x||}).$
(1)

Where $\lambda$ is the conformal factor at point $v$. Conversely, logarithmic
map is used to transform a hyperbolic embedding $p\in\mathbb{B}^{n}_{c}$ to a
Euclidean vector $x\in\mathbb{R}^{n}$ is formulated as:

$x=\log_{v}^{c}(p)=\frac{2}{\lambda_{v}}tanh^{-1}(||-p\oplus_{c}v||)\frac{-p\oplus_{c}v}{||-p\oplus_{c}v||}.$
(2)

Note that the tangent space approximation relies on the assumption of spatial
locality (i.e. small vectors starting from point $v$). For transporting a
local vector from a point in Hyperbolic manifold to another point, one can use
parallel transport Lee (2018). Parallel transport is specifically used in bias
addition in Hyperbolic linear layers Chami et al. (2019). For the detailed
discussion on parallel transport please refer to Lee (2018).

###  3.2 Hyperbolic Layers

Hyperbolic Feed-forward layer. For the Euclidean function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, its equivalent Möbius version
$f^{\otimes_{c}}:\mathbb{B}^{n}_{c}\rightarrow\mathbb{B}^{m}_{c}$ for the
Poincaré ball is defined as
$f^{\otimes_{c}}(p)\coloneqq\exp_{0}^{c}\left(f\left(\log_{0}^{c}(p)\right)\right)$.
Extending this, the hyperbolic equivalent $h^{\mathbb{B}}(p)$ of the Euclidean
linear layer $h^{\mathbb{R}}(x)=Wx$ with weight matrix
$W\in\mathbb{R}^{n\times m}$ is formulated as:

$\displaystyle h^{\mathbb{B}}(p)$
$\displaystyle=\frac{tanh\left(\frac{|Wp|}{|p|}tanh^{-1}\left(\sqrt{c}|p|\right)\right)}{\sqrt{c}|Wp|}Wp$
(3)

Hyperbolic Convolution. For a hyperbolic graph node representation
$p_{0}\in\mathbb{B}^{n}_{c}$ with neighbors $\\{p_{i}\\}_{i=1}^{k}$. As given
in Chami et al. (2019), the hyperbolic convolution layer
$GCN^{\otimes_{c}}:\mathbb{B}^{n}_{c}\rightarrow\mathbb{B}^{m}_{c}$
constitutes of a linear transform, followed by neighborhood aggregation111The
aggregation occurs in the tangent space as concatenation is not well-defined
for hyperbolic space. which is computed as:

$\displaystyle h^{\mathbb{B}}(p_{i})$
$\displaystyle=W_{i}\otimes_{c}p_{i}\oplus_{c}b_{i}$

$\displaystyle
h^{\mathbb{B}}_{agg}(p_{0})=exp^{c}_{p_{0}}\left(\Sigma_{i=0}^{k}w_{ij}\log^{c}_{p_{0}}\left(h^{\mathbb{B}}(p_{i})\right)\right)$

$\displaystyle GCN^{\otimes_{c}}(p_{0})$
$\displaystyle=exp^{c}_{0}\left(\sigma(\log^{c}_{0}(h^{\mathbb{B}}_{agg}(p_{0}))\right)$
(4)

where $w_{ij}=softmax_{i=1}^{k}(MLP(log^{c}_{0}(p_{0})||log^{c}_{0}(p_{i})))$
is an aggregation weight for neighbors.

Multi-relational Hyperbolic Representation. The multi-relational
representations for knowledge graph $KG$ are modeled using a scoring function.
For a triplet $(h,r,t)\in KG$, where relation $x_{r}\in\mathbb{R}^{n}$
connects the head entity $x_{h}\in\mathbb{R}^{n}$ to the tail entity
$x_{t}\in\mathbb{R}^{n}$ and $R\in\mathbb{R}^{n\times n}$ is the diagonal
relation matrix, the hyperbolic equivalent
$\phi^{\mathbb{B}}(p_{h},p_{r},p_{t})$ of the Euclidean scoring
$\phi(x_{h},x_{r},x_{t})=-\|Rx_{h}-(x_{t}+x_{r})\|^{2}$ function is computed
using the hyperbolic distance $d^{\mathbb{B}}$ as:

$\displaystyle d^{\mathbb{B}}(p_{1},p_{2})$
$\displaystyle=\frac{2}{\sqrt{c}}\tanh^{-1}\left(\sqrt{c}\|-p_{1}\oplus_{c}p_{2}\|\right)$
(5)

##  4 Pseudo-Poincaré Hyperbolic Networks

While hyperbolic networks show promising results, switching back and forth
between Möbius gyro-vector operations and Euclidean tangent approximations (at
various points) makes them computationally expensive, limits their
extensibility, and makes them less predictable when applying L1/2
regularization and dropout. Furthermore, such back and forth between the
manifolds (at variable points) comes with an implicit assumption that the
embeddings have spatial locality in all dimensions for the models to be
performant. We argue approximating on tangent space at a variable point does
not necessarily increase the approximation accuracy because the spatial
locality of the embeddings are not guaranteed in general. Therefore, fixating
tangent space to be at the origin can bring both simplicity to the model and
performance in general cases (refer Appendix A for more details). Moreover,
only tangent space at origin has a one-to-one mapping with all points on the
Poincaré (hyperbolic) half-plane model. This enables us to combine the tangent
space approximation with Poincaré half-plane model and apply all
approximations in the half-plane. This makes the pseudo-Poincaré networks much
easier to understand, develop, and optimize.

Fixating the tangent space to the point of origin simplifies the exponential
maps (eq. 1) as:

$p=\exp_{0}^{c}(x)=\frac{tanh(\sqrt{c}|x|)}{\sqrt{c}|x|}x$ (6)

Conversely, the logarithmic map (eq. 2) is simplified as:

$x=\log_{0}^{c}(p)=\frac{tanh^{-1}(\sqrt{c}|p|)}{\sqrt{c}|p|}p$ (7)

Using Eq.(6,7), we reformulate the hyperbolic feed-forward layer. In this
section, we only discuss the re-formulation for Pseudo-Poincaré Feed-forward
Layer. The convolution, attention, and multi-relation layer can be similarly
reformulated for the Pseudo-Poincaré paradigm.

Pseudo-Poincaré Feed-forward Layer. We state that cascading hyperbolic feed-
forward layers (including linear layers) is equivalent to cascading their
Euclidean counterparts and then applying a hyperbolic normalization to the
result.

######  Lemma 1.

For a point in the tangent space at origin
$x\in\mathcal{T}_{0_{n}}\mathbb{B}^{n}_{c}$, the exponential map to the
hyperbolic space $\mathbb{B}^{n}_{c}$,
$\exp_{0}^{c}:\mathcal{T}_{0_{n}}\mathbb{B}^{n}_{c}\rightarrow\mathbb{B}^{n}_{c}$
$\exp_{0}^{c}(x)$, is equivalent to the input scaled by a non-linear scalar
function $\omega:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, i.e.,

$p=\exp_{0}^{c}(x)=\omega(x)x;\quad\omega(x)=\frac{tanh(\sqrt{c}|x|)}{\sqrt{c}|x|}$
(8)

where $\omega(x)$ is the hyperbolic normalization for exponential maps. This
follows from equation (1).

######  Lemma 2.

Approximating on tangent space at origin for all stages causes the cascade of
$n$ hyperbolic feed-forward layers
$F_{n}^{\otimes_{c}}=\\{f^{\otimes_{c}}_{i}\\}_{i=1}^{n}$ to be equivalent to
cascading $n$ of their Euclidean counterparts $F_{n}=\\{f_{i}\\}_{i=1}^{n}$
encapsulated in $\log_{0}^{c}$ and $\exp_{0}^{c}$ functions, i.e.,

$\displaystyle F_{n}(x)$ $\displaystyle=f_{n}\left(f_{n-1}\left(\cdots
f_{1}\left(x\right)\right)\right)$ (9) $\displaystyle F_{n}^{\otimes_{c}}(p)$
$\displaystyle=f_{n}^{\otimes_{c}}(f^{\otimes_{c}}_{n-1}(\cdots
f_{1}^{\otimes_{c}}(p))=exp_{0}^{c}\left(F_{n}(log^{c}_{0}(p))\right)$

Proposition Lemma 2 implies that the hyperbolic transformations $\exp_{0}^{c}$
and $\log_{0}^{c}$ are only needed at the initial and final stages to capture
hierarchy in Euclidean networks.

######  Lemma 3.

For given input features $x=log_{0}^{c}(p)\in\mathbb{R}^{n}$, a given
hyperbolic feed forward layer can be rewritten as
$f^{\otimes_{c}}(x)\coloneqq\omega(f(x))f(x)$.

From lemmas 2 and 3, we arrive at the following theorem for cascaded
hyperbolic layers.

######  Theorem 4.

Fixating the tangent space to be always at origin, cascaded hyperbolic feed-
forward layers $F_{n}^{\otimes_{c}}$ for Euclidean input $x\in\mathbb{R}^{n}$
can be reformulated as
$F_{n}^{\otimes_{c}}(x)\coloneqq\Omega(F_{n}(x))F_{n}(x)$, where
$\Omega(F_{n}(x))$ is the hyperbolic normalization for a cascaded hyperbolic
feed-forward network.

##  5 Pseudo-Poincaré Layers

Pseudo-Poincaré Graph Convolution. The individual components of the Hyperbolic
Graph Convolution, as defined in Eq. (4), can be reformulated as a cascaded
hyperbolic feed-forward layer. Thus, we approximate both the aggregation
weights and the aggregation function in $\mathcal{T}_{0}\mathbb{B}^{n}_{c}$
as:

$\displaystyle h^{\mathbb{B}}_{agg}(p_{i})$
$\displaystyle=exp^{c}_{0}\left(\Sigma_{i=0}^{k}w_{ij}\log^{c}_{0}\left(h^{\mathbb{B}}(p_{i})\right)\right)$
(10)

With this approximation, we apply Theorem 4 to reformulate reformulate the
$GCN^{\otimes_{c}}:\mathbb{B}^{n}_{c}\rightarrow\mathbb{B}^{m}_{c}$ layers as
Normalized GCN $NGCN^{\otimes_{c}}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$
over Euclidean inputs $x_{0}\in\mathbb{R}^{n}$ with neighbors
$\\{x_{i}\\}_{i=1}^{k}$. This is computed as
$NGCN^{\otimes_{c}}\coloneqq\Omega(GCN(x_{0}))GCN(x_{0})$, where $GCN(x_{0})$
is the Euclidean Graph Convolution layer Kipf and Welling (2017).

Note that the cascaded feed-forward functions of HGCN Chami et al. (2019)
operate on different tangent spaces, i.e., aggregation weights are calculated
at the linear tangent space at origin $\mathcal{T}_{0}\mathbb{B}^{n}_{c}$
whereas the aggregation function as given in Eq. (10) is driven from a linear
tangent space at the root node $\mathcal{T}_{p_{0}}\mathbb{B}^{n}_{c}$. An
argument to use different tangent spaces for different function is based on
the fact that Euclidean approximation is most accurate when the tangent space
is close to the true resulting point. For aggregation, using tangent space at
$p_{0}$ requires an implicit assumption that all aggregated hyperbolic points
preserve a form of spatial locality, which implies similarity and not exactly
the notion of hierarchy. However, we can still argue that hierarchical
structures have a loose form of spatial locality, and hence using
$log^{c}_{0}(p)$ will add some noise to the embedding compared to when
$log^{c}_{p_{0}}(p)$ is used.

Pseudo-Poincaré Graph Attention Layer. Here, our goal is to project the
Euclidean GAT layer onto the hyperbolic space by applying the hyperbolic
normalization (e.g., Eq. (8)), then, investigate its approximation in relation
to the existing hyperbolic graph attention layers as well as with a true
hyperbolic graph attention mechanism.

Hyperbolic attention is formulated as a two-step process (as defined in
Gulcehre et al. (2019)); (1) matching, which computes attention weights, and
(2) the aggregation, which takes a weighted average of the values (attention
coefficients as weights). Hence, the attention layer can be seen as two
cascaded layers, in which the first calculates the attention weights, while
the second layer aggregates the weighted vectors. Existing hyperbolic graph
attention method Zhang et al. (2021)
$GAT^{\otimes_{c}}:\mathbb{B}^{n}_{c}\rightarrow\mathbb{B}^{m}_{c}$ views the
hyperbolic aggregation as a hyperbolic feed forward layer with a Euclidean
weighted average as its function. Similarly
$GAT:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ Veličković et al. (2018) also
uses weighted-average for the aggregation.

Since we are using Euclidean weighted average over cascaded feed-forward
layers, we can apply Theorem 4 to hyperbolic GAT and approximate it in the
hyperbolic space with a hyperbolic normalization function and Euclidean GAT as
$NGAT^{\otimes_{c}}(x)\coloneqq\Omega(GAT(x))GAT(x)$.

Pseudo-Poincaré Multi-relational Representation. For Euclidean inputs
$x_{1},x_{2}\in\mathbb{R}^{n}$ and L1-norm $d^{\mathbb{R}}(x_{1},x_{2})$, the
hyperbolic formulation of the multi-relational hyperbolic distance
$d^{\mathbb{B}}(x,y)$, given in Eq. (5) can alternatively be reformulated as
$d^{\mathbb{B}}(x_{1},x_{2})=\omega(x)d^{\mathbb{R}}(x_{1},x_{2})$. Similarly,
for Euclidean triplet $(x_{h},x_{r},x_{t})\in\mathbb{R}^{n}$, the scoring
function $\phi^{\mathbb{B}}(p_{h},p_{r},p_{t})$ can also be approximated to
$NMuR^{\mathbb{B}}(x_{h},x_{r},x_{t})$ as:

$\displaystyle\phi^{\mathbb{R}}(x_{h},x_{r},x_{t})$
$\displaystyle=-d^{\mathbb{R}}\left(Rx_{h},x_{t}+x_{r}\right)^{2}$ (11)
$\displaystyle\scriptstyle NMuR^{\mathbb{B}}(x_{h},x_{r},x_{t})$
$\displaystyle=\Omega(\phi^{\mathbb{R}}(x_{h},x_{r},x_{t}))\phi^{\mathbb{R}}(x_{h},x_{r},x_{t})$
(12)

Hyperbolic Normalization. Theorem 4 allows the cascaded hyperbolic layers to
be reformulated in the Euclidean space using a hyperbolic normalization
($\Omega$) function. Our normalization layer resembles the technique proposed
in Salimans and Kingma (2016) to normalize the weights, which uses the
equation; $w=\frac{e^{s}}{\|v\|}v$, where $v$ is an $n$-dimensional vector
used to learn the direction and $s$ is a trainable parameter. However, unlike
weight normalization, hyperbolic normalization happens on the features (and
not the weights). Furthermore, hyperbolic normalization uses the $tanh$
scaling function instead of $e^{s}$. However, both are similar in terms of
using the feature vector magnitude as the denominator and hence removing the
orthogonality of the dimensions. The “unrolled deep hyperbolic network” (shown
in Figure 2) presents the general idea of stacking multiple hyperbolic layers
together. The input into each layer is passed through a logarithmic map to
project into Euclidean space and its output is projected back onto the
hyperbolic space after applying the computations.

Batch-Norm, Layer-Norm vs. Hyperbolic Norm. Batch-Norm tries to reduce the
covariant shift and noise Ioffe and Szegedy (2015) which means the result of
the batch-norm is in Euclidean space. On the other hand, Layer-Norm, and
Hyperbolic Norm take vectors to another manifold for better latent space
representation Lei Ba et al. (2016). Thus, we recommend using Riemannian
optimizers when applying our method at least for shallow GNNs (we provided
empirical results in experiment section). Note that, in order to apply the
batch normalization in hyperbolic space, one needs to change its mathematical
operations to use Frechet mean Peng et al. (2021). The detailed analysis of
the effect of hyperbolic batch normalization methods is outside the scope of
this work.

Optimization. The scaling function in Eq. (8) uses the vector norm in the
denominator and hence, each dimension depends on the value of other dimensions
(i.e., non-orthogonal). Due to this, optimizers that are developed based on
the orthogonality assumptions of the dimensions such as ADAM are not expected
to produce the most optimal weights. Thus, we choose Riemannian optimizers
such as RiemannianADAM Becigneul and Ganea (2019) for our model training. For
traditional hyperbolic models, regularization techniques such as
L2-regularization do not work as expected since the weights are in hyperbolic
space. However, the trainable parameters in our formulation are in the
Euclidean space. Hence, we can additionally apply regularization techniques
that are applied to Euclidean networks.

Algorithm 1 provides the generalized algorithm for our proposed hyperbolic
model.

Input: Input Euclidean model $F_{L}$, sample node $x\in\mathbb{R}^{n}$

Output: Output of Normalized hyperbolic model $F_{L}^{\otimes_{c}}(x)$;

1 $f_{0}^{\otimes_{c}}(x)=x;$

2 for  _layer $l:1\rightarrow L$_ do

3 $x\leftarrow f^{\otimes_{c}}_{l-1}(x);$

4 # Layer $l$ of the Euclidean model is $f_{l}(x)$

5 $\omega(f_{l}(x))=\frac{tanh(\sqrt{c}|f_{l}(x)|)}{\sqrt{c}|f_{l}(x)|}$;
using Eq. (8) $f^{\otimes_{c}}_{l}(x)=\omega(f_{l}(x))f_{l}(x)$; using Lemma 3

6

7 end for

8$F_{n}^{\otimes_{c}}(x)=f^{\otimes_{c}}_{L}(x);$

return _$F_{L}^{\otimes_{c}}(x)$_

Algorithm 1 Normalized hyperbolic model.

##  6 Experimental Results

In this section, we aim to answer following research questions (RQs) through
our experiments:

  * RQ1: How do the pseudo-Poincaré variants compare to their Euclidean and hyperbolic counterparts on on node classification and link prediction?

  * RQ2: How does the pseudo-Poincaré variant, NMuR, compare to its Euclidean and hyperbolic counterparts on reasoning over knowledge graphs?

  * RQ3: How do pseudo-Poincaré variants react to the choice of optimizers, and what are the effects on their execution time? How does the hyperbolic normalization compare to its counterparts?

  * RQ4: How does pseudo-Poincaré variant perform when used in deep GNN archictures e.g. GCNII?

  * RQ5: What is the difference in the representations obtained through hyperbolic and pseudo-Poincaré projections?

###  6.1 Experimental Setup

For comparison of hyperbolic normalization with other methods, we conduct our
experiments on the following tasks: (i) graph prediction (node classification
and link prediction) and (ii) reasoning over knowledge graphs, which are
described below:

Table 1:  Performance comparison results between hyperbolic normalization (ours) and the baseline methods on the graph prediction tasks of node classification and link prediction. The columns present the evaluation metrics, which are Accuracy (for node classification) and Area under ROC (ROC) (for link prediction), along with their corresponding 95% confidence intervals. The cells with the best performance are highlighted in bold and the second-best performance are underlined. Repr. | Datasets | Node Classification (Accuracy in %) | Link Prediction (ROC in %)
---|---|---|---
Space | Models | CORA | Pubmed | Citeseer | Cora | Pubmed | Citeseer
Euclidean | GCN |  80.1$\pm$0.3 |  78.5$\pm$0.3 |  71.4$\pm$0.3 |  90.2$\pm$0.2 |  92.6$\pm$0.2 |  91.3$\pm$0.2
| GAT | 82.7$\pm$0.2 |  79.0$\pm$0.3 |  71.6$\pm$0.3 |  89.6$\pm$0.2 |  92.4$\pm$0.2 | 93.6$\pm$0.2
Hyperbolic | HGCN |  77.9$\pm$0.3 |  78.9$\pm$0.3 |  69.6$\pm$0.3 | 91.4$\pm$0.2 | 95.0$\pm$0.1 | 92.8$\pm$0.3
| HGAT |  79.6$\pm$0.3 | 79.2$\pm$0.3 |  68.1$\pm$0.3 |  90.8$\pm$0.2 |  93.9$\pm$0.2 |  92.2$\pm$0.2
Pseudo- | NGCN |  82.4$\pm$0.2 |  78.8$\pm$0.3 | 71.9$\pm$0.3 | 91.3$\pm$0.2 | 94.7$\pm$0.1 | 92.8$\pm$0.2
Poincaré | NGAT | 83.1$\pm$0.2 | 79.1$\pm$0.3 | 73.8$\pm$0.3 |  90.5$\pm$0.2 |  93.9$\pm$0.2 | 92.8$\pm$0.2

Graph Prediction. Given a graph $\mathcal{G}=(V\times E)$, where
$v_{i}\in\mathbb{R}^{n},\\{v_{i}\\}_{i=1}^{|V|}\in V$ is the set of all nodes
and $E\in\\{0,1\\}^{|V|\times|V|}$ is the Boolean adjacency matrix, where
$|V|$ is the number of nodes in the graph and $e_{ij}=1$, if link exists
between node $i$ and $j$, and $e_{ij}=0$, otherwise. Each node $v_{i}\in V$ is
also labeled with a class $y_{i}$. In the task of node classification, the
primary aim is to estimate a predictor model $P_{\theta}$ with parameters
$\theta$ such that for an input node $v_{i}$; $P_{\theta}(v_{i}|E)=y_{i}$. In
the task of link prediction, the primary aim is to estimate a predictor model
$P_{\theta}$ with parameters $\theta$ such that for an input node-pair
$v_{i},v_{j}$ and an incomplete adjacency matrix $\hat{E}$;
$P_{\theta}(v_{i},v_{j}|\hat{E})=e_{ij}$, where $e_{ij}\in E$ is an element in
the complete adjacency matrix.

Reasoning over Knowledge Graphs. Let us say that a set of triplets constitutes
a knowledge graph
$\mathcal{KG}=\\{(h_{i},r_{i},t_{i})\\}_{i=1}^{|\mathcal{KG}|}$, where
$h_{i}\in\mathbb{R}^{n}$ and $t_{i}\in\mathbb{R}^{n}$ are the head and tail
entity, respectively connected by a relation $r_{i}\in\mathbb{R}^{n}$. In the
task of reasoning Balažević et al. (2019), our goal is to learn
representations for the entities and relations using a scoring function that
minimizes the distance between heads and tails using the relation as a
transformation. The scoring function for Euclidean $MuRE$, hyperbolic $MuRP$
and pseudo-Poincaré $NMuR$ are presented in Eq. (11), and Eq. (12),
respectively.

###  6.2 Datasets and Baselines

Datasets. For comparing our model with the baselines, we chose the following
standard benchmark datasets;

  * •

Cora Rossi and Ahmed (2015) contains 2708 publications with paper and author
information connected by citation links and classified into 7 classes based on
their research areas.

  * •

Pubmed Sen et al. (2008) contains medical publications pertaining to diabetes
labeled into 3 classes. The dataset is collected from the Pubmed database.

  * •

Citeseer Sen et al. (2008) contains 3312 annotated scientific publications
connected by citation links and classified into 6 classes of research areas.

  * •

WN18RR Dettmers et al. (2018) is a subset of the hierarchical WordNet
relational graph that connects words with different types of semantic
relations. WN18RR consists of 40,943 entities connected by 11 different
semantic relations.

  * •

FB15k-237 Bordes et al. (2013) Toutanova et al. (2015) contains triple
relations of the knowledge graph and textual mentions from the Freebase entity
pairs, with all simple invertible relations are removed for better comparison.
The dataset contains 14,541 entities connected by 237 relations.

  * •

Protein-Protein Interaction (PPI) network dataset Hamilton et al. (2017)
contains 12M+ triples with 15 relations (preserving the original ratio of the
relations in the dataset, we randomly sampled the dataset, and trained on the
sampled subset).

We use Cora, Pubmed, and Citeseer for our experiments on homogeneous graph
prediction, i.e., node classification and link prediction. For comparing the
multi-relational networks on the task of reasoning, we utilize the FB15k-237
and WN18RR datasets. For a fair comparison of evaluation metrics, we use the
same training, validation, and test splits as used in the previous methods,
i.e., the splits for Cora, Pubmed, and Citeseer are as given in Chami et al.
(2019) and for FB15k-237 and WN18RR, the splits are in accordance with
Balažević et al. (2019).

Baselines. For comparing the performance of our Pseudo-Poincaré models, we
utilize the Euclidean and hyperbolic variants of the architecture as our
baselines;

  * •

Graph Convolution (GCN) Kipf and Welling (2017) aggregates the message of a
node’s k-hop neighborhood using a convolution filter to compute the neighbor’s
significance to the root.

  * •

Graph Attention (GAT) Veličković et al. (2018) aggregates the messages from
the neighborhood using learnable attention weights.

  * •

Hyperbolic Graph Convolution (HGCN) Chami et al. (2019) is a hyperbolic
formulation of the GCN network that utilizes the hyperbolic space and
consequently, Möbius operations to aggregate hierarchical features from the
neighborhood,

  * •

Hyperbolic Graph Attention (HGAT) Yang et al. (2021) is a hyperbolic
formulation of the GAT networks to capture hierarchical features in the
attention weights.

  * •

Multi-relational Embeddings (MuRE) Balažević et al. (2019) transforms the head
entity by a relation matrix and then learns representation by minimizing
L1-norm between head and tail entities translated by the relation embedding.

  * •

Multi-relational Poincaré (MuRP) Balažević et al. (2019) is a hyperbolic
equivalent of MuRE that transforms the head entity by a relation matrix in the
Poincaré ball and then learns representation by minimizing the hyperbolic
distance between the head and tail entities translated by the relation
embedding.

  * •

Relational Graph Convolution Network (RGCN) Schlichtkrull et al. (2018) is
graph convolutional networks applied in heterogeneous graph.

  * •

Deep Graph Convolutional Networks (GCNII) Li et al. (2018) is an extension of
a Graph Convolution Networks with two new techniques, initial residual and
identify mapping, to be used in deep GNN settings.

Table 2:  Performance comparison results between Pseudo-Poincaré (ours) and
the baseline methods on the task of multi-relational graph reasoning. The
columns present the evaluation metrics of Hits@K (H@K) (%) and Mean Reciprocal
Rank (MRR) (%) along with their corresponding 95% confidence intervals. The
best results are highlighted in bold.

|  | WN18RR | FB15K-237 | PPI
---|---|---|---|---
Dim |  Models | MRR | H@10 | H@3 | MRR | H@10 | H@3 | MRR | H@10 | H@3
40 |  MuRE | 40.9$\pm$0.3 | 49.7$\pm$0.3 | 44.5$\pm$0.3 | 29.0$\pm$0.3 | 46.2$\pm$0.3 | 31.9$\pm$0.3 | 2.81$\pm$0.3 | 9.24$\pm$0.3 | 4.11$\pm$0.3
|  MuRP | 42.5$\pm$0.3 | 52.2$\pm$0.3 | 45.9$\pm$0.3 | 29.8$\pm$0.3 | 47.4$\pm$0.3 | 32.8$\pm$0.3 | 5.55$\pm$0.3 | 10.21$\pm$0.3 | 4.43$\pm$0.3
|  NMuR | 43.6$\pm$0.3 | 57.5$\pm$0.3 | 47.4$\pm$0.3 | 31.5$\pm$0.3 | 49.7$\pm$0.3 | 34.7$\pm$0.3 | 8.21$\pm$0.3 | 14.3$\pm$0.3 | 11.7$\pm$0.3
200 |  MuRE | 44$\pm$0.3 | 51.3$\pm$0.3 | 45.5$\pm$0.3 | 31.4$\pm$0.3 | 49.5$\pm$0.3 | 34.5$\pm$0.3 | 10.68$\pm$0.3 | 14.55$\pm$0.3 | 11.90$\pm$0.3
|  MuRP | 44.6$\pm$0.3 | 52.4$\pm$0.3 | 46.2$\pm$0.3 | 31.5$\pm$0.3 | 49.8$\pm$0.3 | 34.8$\pm$0.3 | 8.23$\pm$0.3 | 15.09$\pm$0.3 | 9.98$\pm$0.3
|  NMuR | 44.7$\pm$0.3 | 57.9$\pm$0.3 | 48.1$\pm$0.3 | 32.2$\pm$0.3 | 50.6$\pm$0.3 | 35.5$\pm$0.3 | 12.68$\pm$0.3 | 15.07$\pm$0.3 | 13.82$\pm$0.3

Table 3:  Node-Classification results for RGCN model on AIFB, AM, BGS, and MUTAG datasets. Note that we used the same implementation and dataset in Thanapalasingam et al. (2021) to show that our method can be applied incrementally and effectively to the existing code-bases. Dataset | AIFB | AM | BGS | MUTAG
---|---|---|---|---
RGCN | 97.22 | 89.39 | 82.76 | 67.65
NRGCN | 97.22 | 89.9 | 89.66 | 73.53
E-RGCN | 88.89 | 90.4 | 82.76 | 75.00
NE-RGCN | 94.44 | 90.91 | 86.21 | 76.47
Table 4: Link-Prediction results for RGCN model on WN18 and FB-Toy datasets. Note that we used the same implementation and dataset in Thanapalasingam et al. (2021) to show that our method can be applied incrementally and effectively to the existing code-bases. | MPR | Hits@1 | Hits3 | Hits@10
---|---|---|---|---
Dataset | FB-Toy
RGCN | 47.0 | 30.9 | 55.3 | 83.2
N-RGCN | 51.8 | 35.2 | 60.9 | 86.5
Dataset | WN18
RGCN | 65.9 | 43.2 | 89.0 | 93.7
N-RGCN | 75.2 | 59.8 | 90.2 | 93.9

###  6.3 Implementation Details

We run our experiments on an Nvidia T4 GPU with 16 GB of VRAM. Our models are
implemented on the Pytorch framework Paszke et al. (2019) and the baselines
are adopted from Chami et al. (2019) for GAT, GCN, and HGCN, and from
Balažević et al. (2019) for MuRE and MuRP. Due to the unavailability of a
public implementation, we use our own implementation of HGAT based on Yang et
al. (2021). The implementations have been thoroughly tuned with different
hyper-parameter settings for the best performance.

For GAT baseline, we used 64 dimensions with 4 and 8 attention heads (we found
4 heads perform better and hence we only present that result in our tables),
with dropout rate of 0.6 and L2 regularization of $\lambda=0.0005$ (for Pubmed
and Cora), and $\lambda=0.001$ (for CiteSeer) to be inline with the hyper-
parameters reported in Veličković et al. (2018). We used same number of
dimensions and hyper-parameters for our NGAT model. For GCN baseline,
Veličković et al. (2018) used 64 dimensions. we used the same number of
dimensions and hyperparameter setting as GAT baseline. It should be noted
that, we observed poor performance when we applied regularization techniques
(that GAT baseline used) to the hyperbolic models. For HGCN, the original
paper used 16 hidden dimension, however, we tried 64, 32, and 16 for the
hidden dimensions, we found 64 dimensions produces a better results. For the
curvature choice, we used different curvatures for different tasks. For the
task of node classification, we used $c=0.3$ (for Cora), and $c=1$ (for Pubmed
and Citeseer) as they produced the best results, while for the link prediction
task, $c=1.5$ produced the best results. at the end, we empirically found that
scaling the output of the hyperbolic normalization layer by the factor of 5
produces the best results when $c=0.3-0.5$ (and for $c=1.5$, we set the
scaling factor to 3).

###  6.4 RQ1: Performance on Graph Prediction

To evaluate the performance of hyperbolic normalization with respect to
Euclidean and hyperbolic alternatives, we compare the $NGCN$ and $NGAT$ models
against the baselines on the tasks of node classification and link prediction.
We utilize the standard evaluation metrics of accuracy and ROC-AUC for the
tasks of node classification and link prediction, respectively (Table 1).

From the results, in all cases (except link-prediction on Citeseer), pseudo-
Poincaré variants outperform the Euclidean model. Pseudo-Poincaré variants
perform better than their hyperbolic counterparts in node classification, but
marginally lower in link-prediction. This is inline with our expectations as
embeddings of adjacent points in link-prediction on homogeneous graphs tend to
have spatial locality. However, spatial locality is less likely for node-
classification (as far away nodes still can belong to the same class). It is
also worth noting that Pseudo-Poincaré outperforms Euclidean in all node-
classification datasets regardless of the hyperbolicity of the dataset (e.g.,
Cora has low hyperbolicity Chami et al. (2019) which were previously suggested
as a reason that inferior Hyperbolic networks over Euclidean counterparts).
This observation suggests that Pseudo-Poincaré is more general purpose
framework (i.e., it is performant in a wider variety of tasks/datasets
compared to pure-Hyperbolic model). It should be noted that pseudo-Poincaré
variants are consistently at least the second-best performing methods, closely
following the top performer which makes it appealing given the low-complexity,
and speedup of the model (Table 7).

###  6.5 RQ2: Multi-relational Reasoning

To compare the performance of hyperbolic normalization against the baselines
for multi-relational graphs, we compare the $NMuR$ model against $MuRE$ and
$MuRP$ on the task of reasoning. We consider the standard evaluation metrics
of Hits@K and Mean Reciprocal Rank (MRR) to compare our methods on the
reasoning task. Let us say that the set of results for a head-relation query
$(h,r)$ is denoted by $R_{(h,k)}$, then the metrics are computed by
$MRR=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{rank(i)}$ and
$Hits@K=\frac{1}{K}\sum_{k=1}^{K}e_{k}$, where $e_{k}=1$, if $e_{k}\in
R_{(h,r)}$ and $0$, otherwise. Here $rank(i)$ is the rank of the $i^{th}$
retrieved sample in the ground truth. To study the effect of dimensionality,
we evaluate the models with two values of the embedding dimensions: $n=40$ and
$n=200$. The results from our comparison are given in Table 2.

From the results, note that $NMuR$ outperforms the hyperbolic model $MuRP$, on
an average, by $\approx 5\%$ with 40 dimensions and $\approx 3\%$ with 200
dimensions across various metrics and datasets. This shows that $NMuR$ is able
to effectively learn better representations at lower number of dimensions.
Also, note that the difference in performance by increasing the number of
dimensions is $<1\%$ for most cases, implying that NMuR is already able to
capture the hierarchical space of the knowledge graphs at lower dimensions.
This should limit the memory needed for reasoning without a significant loss
in performance.

#### Applying Pseudo-Poincare to RGCN

In order to further show (1) the effectiveness our method, as well as (2) how
easy it is to apply our method to an existing model (i.e. adoptability), we
took the pytorch models implemented by Thanapalasingam et al. (2021), and
added our hyperbolic normalizatoin layer as the last layer of the model. We
also trained the model using Riemannian Adam. Table 3 shows the comparative
results for the Node Classification tasks on AIFB, AM, BGS, and MUTAG datasets
(further details about the datasets can be found in Thanapalasingam et al.
(2021)). We used curvature $c=1.5$, and scaling factor $s=3$ for N-RGCN and
$c=0.5$, and $s=5$ for NE-RGCN (except for MUTAG NE-RGCN that we used $c=1.5$,
and $s=3$). We trained the models 10 time and picked the best checkpoint for
both Euclidean and our variant. We observed significant improvements in across
all metrics when we applied our Hyperbolic normalization method. The fact the
applying our method to the existing models is almost seemless increases the
ability to explore/adopt hyperbolic models for variety of
tasks/models/applications.

Table 4 shows the results of Link Prediction over WN18 and FB-Toy datasets (we
stuck to the same implementation and the datasets to have apple-to-apple
comparison). We only trained RGCN (the pytorch implementation they had in 4).
We used curvature $c=1.5$, and scaling factor $s=3$ for FB-Toy, and $c=0.5$,
and $s=5$ for WN18 dataset. We trained the model on WN18 for 7k epochs, and on
FB-toy for 12K (to replicate the experiments in Thanapalasingam et al.
(2021)).

###  6.6 RQ3: Model Analysis

Hyperbolic Normalization vs. Layer Normalization. In this experiment, we study
the difference between our hyperbolic normalization compared to other existing
normalization approaches. For this, we select Layer-norm Lei Ba et al. (2016)
as it is the closest in terms of input/output. Also, in order to study the
effect of hyperbolic scaling in our normalization layer, we added constant-
norm which is computed as follows: $norm(x)=x/\|x\|$. In order to compare the
effect of normalization layers, we did not use any extra hyper-parameter
rtuning and regularization. We set the embedding size to 64 for both GAT and
GCN, and used 4 heads for GAT-models. Table 5 shows the comparison of
different normalization methods on Cora, Pubmed, and Citeseer datasets, and
confirms the outperformance of hyperbolic normalization. Since Layer-norm
keeps the GAT model in the Euclidean space, we used ADAM optimizer. However,
since both hyperbolic normalization and constant normalization have $\|x\|$ as
their denominator, we used RiemannianAdam.

Table 5:  Comparison of normalization methods. (Layer-Norm, Hyperbolic Norm, and Constant magnitude). The columns present results on Cora (CR), Pubmed (PM), and Citeseer (CS) datasets using GAT and GCN models. Note that the provided results are without any hyper-parameter tuning, thus the comparison is only valid column-wise. Base Model |  | CR | PM | CS
---|---|---|---|---
GCN | Constant | 67.9 | 76.7 | 68.3
| Layer-Norm | 78.3 | 75.0 | 63.6
| Hyp-Norm | 80.9 | 78.0 | 72.1
GAT | Constant | 75.3 | 73.0 | 61.2
| Layer-Norm | 75.6 | 74.9 | 65.3
| Hyp-Norm | 76.7 | 76.3 | 68.6

Optimizer Choice. In this study, we experimentally validate our observations
regarding the choice of optimizers. Table 6 shows that NGAT works better when
RiemannianAdam is used as an optimizer. This shows that, although the
parameters are in the Euclidean space, their gradient updates occur in
accordance with hyperbolic gradients. Thus, NGAT leverages the architecture of
GAT, but behaves more closely to HGAT when it comes to parameter optimization.

Table 6: Performance of NGAT, GAT, and HGAT on node classification with RAdam
and Adam optimizers.

Models | Optimizers | Cora | Pubmed | Citeseer
---|---|---|---|---
GAT | Adam | 82.7$\pm$0.2 | 78.7$\pm$0.2 | 71.6$\pm$0.3
| RAdam | 78.4$\pm$0.3 | 79.0$\pm$0.3 | 71.1$\pm$0.3
HGAT | Adam | 76.8$\pm$0.3 | 76.0$\pm$0.3 | 68.1$\pm$0.3
| RAdam | 79.6$\pm$0.3 | 78.9$\pm$0.3 | 68.1$\pm$0.3
NGAT | Adam | 78.8$\pm$0.3 | 77.7$\pm$0.3 | 69.7$\pm$0.3
| RAdam | 83.9$\pm$0.2 | 79.1$\pm$0.3 | 73.8$\pm$0.3

Execution Time Comparison. In this analysis, we demonstrate the impact of
hyperbolic normalization in improving the scalability of hyperbolic networks.
We study the computational cost to train our model versus the hyperbolic and
Euclidean counterparts. We ran all the experiments on Quadro RTX 8000 with
48GB memory, and reported the mean of $epoch/second$ for each training
experiment for link prediction task in Table 7. Our model NGCN is 3 times
faster than the HGCN on average over the entire training, while NGAT is 5
times faster than its own hyperbolic counterpart (HGAT). NGCN and NGAT are
$25\%$ and $12\%$ slower compared to their Euclidean counterparts,
respectively. We observed the smallest speedup for Pubmed which is due to the
large dataset memory footprint. Even in this case, our NGCN model is still
more than 2 times faster than HGCN and NGAT is more than 3.5 times faster than
HGAT.

Table 7:  Comparison of execution times. The training epoch times (in seconds - lower is better) for Euclidean, hyperbolic, and Pseudo-Poincaré models. Model |  | CR | PM | CS
---|---|---|---|---
Convolution | GCN | 0.07 | 0.13 | 0.04
| HGCN | 0.29 | 0.33 | 0.21
| NGCN | 0.08 | 0.14 | 0.06
Attention | GAT | 0.16 | 0.38 | 0.09
| HGAT | 1.10 | 1.34 | 0.81
| NGAT | 0.19 | 0.37 | 0.12

Figure 3:  Embedding visualizations of the Cora citation graph for Euclidean
(GAT), hyperbolic (HGAT), and our proposed Pseudo-Poincaré (NGAT) methods.
NGAT achieves better separation between the node classes than the
corresponding Euclidean and hyperbolic counterparts.

###  6.7 RQ4: Hyperbolic Norm on Deep GNNs

Li et al. (2018) indicates the traditional GNNs such as GCN and GAT achieve
their best performance with 2-layer models. Stacking more layers and adding
non-linearity tends to degrade the performance of these models. Such a
phenomenon is called over-smoothing. So far, in our experiment, we showed that
adding our hyperbolic normalization layer (plus riemannian Adam optimizer)
increases the model performance. In order to understand the behavior of our
layer on deep GNNs, we experimented on GCNII with 2, 4, 8, 16, 32, and 64
layers. Please note that since our hyperbolic normalization layer contains
tanh, adding the normalization layer to all GCNII causes vanishing gradient
descent problem. Thus, we only used our hyperbolic normalization layer in the
middle of the model to form and encoder-decoder model (in which the encoder
creates a hyperbolic latent space, and a normal decoder interprets the latent
space). We picked the same Euclidean hyper-parameters as the original GCNII
work Chen et al. (2020) but did grid search on curvature and scale. Table 8
shows the results for Cora, Citeseer, Pubmed node classification tasks. As a
general observation, the best pick (across models with different layers) of
our normalized N-GCNII is either on par or outperforms the best pick of
Euclidean GCNII. However, when we look more granular, we observe our model
(N-GCNII), outperform the Euclidean counterpart with bugger margin in the
shallow models. As the number of layers increases, the performance gap reduces
as well. We believe this is due to the fact that deeper model are better at
learning smooth manifolds which is consistent with studies on NLP indicating
the latent space of deep models shows a degree of hyperbolicity Chen et al.
(2021). Moreover, we observed that as the model gets deeper, applying
Riemannian Adam is less effective (for models deeper than 8 layers, ADAM
performs better even on our models).

Table 8:  The behavior of hyperbolic normalization on deep GNNs.

| Models | 2 | 4 | 8 | 16 | 32 | 64
---|---|---|---|---|---|---|---
Cora | GCNII | 83.1 | 83.6 | 84.6 | 85.6 | 86.4 | 86.1
| NGCNII | 83.6 | 84.5 | 85.4 | 85.8 | 86.3 | 86.1
Citeseer | GCNII | 68.7 | 69.1 | 71.3 | 73.4 | 73 | 73.2
| NGCNII | 69.8 | 70.2 | 68.8 | 73.6 | 74.1 | 73.1
Pubmed | GCNII | 78.6 | 78.5 | 79 | 80.8 | 80.2 | 80.4
| NGCNII | 79.4 | 79.2 | 80 | 80.5 | 80.9 | 80.5

###  6.8 RQ5: Embedding Visualizations

We visually demonstrate that our approach of learning in Euclidean space,
indeed preserves the hierarchical characteristics of hyperbolic space. Towards
this goal, we present the visualization of node embeddings from the Cora
citation graph. We choose Cora, since it is a citation-based graph and does
not contain explicit hierarchical (is-a) relations. We contrast the embeddings
learned by GAT (a method based on Euclidean space), with HGAT (learning in
hyperbolic space) with the proposed NGAT approach. Figure 3 shows that NGAT
ensures clearer separation between node classes in comparison to its Euclidean
and hyperbolic counterparts.

##  7 Conclusion

In this paper, we showed that a Euclidean model can be converted to behave as
a hyperbolic model by simply (1) connecting it to the hyperbolic normalization
layer and (2) using a Riemannian optimizer. From the training perspective,
this approach allows the trainable parameters to interact in the Euclidean
vector space, consequently enabling the use of Euclidean regularization
techniques for the model training. Furthermore, the training of our proposed
approach is significantly faster compared to the existing hyperbolic methods.
This allows the hyperbolic networks to be more flexible in practice to a wider
variety of graph problems. From task/application perspective, we removed the
implicit assumption of having spatial locality of the adjacent nodes (in all
dimensions), to be a prerequisite of the hyperbolic model training. This
allows the framework to be applied in a wider range of tasks.

## References

  * Anderson and May [1992] Roy M Anderson and Robert M May.  Infectious diseases of humans: dynamics and control.  Oxford university press, 1992.
  * Balažević et al. [2019] Ivana Balažević, Carl Allen, and Timothy Hospedales.  Multi-relational poincaré graph embeddings.  In Advances in Neural Information Processing Systems, 2019.
  * Becigneul and Ganea [2019] Gary Becigneul and Octavian-Eugen Ganea.  Riemannian adaptive optimization methods.  In International Conference on Learning Representations, 2019.
  * Bordes et al. [2013] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko.  Translating embeddings for modeling multi-relational data.  Advances in neural information processing systems, 26, 2013.
  * Cao et al. [2015] Shaosheng Cao, Wei Lu, and Qiongkai Xu.  Grarep: Learning graph representations with global structural information.  In Proceedings of the 24th ACM international on conference on information and knowledge management, pages 891–900, 2015.
  * Cayton [2005] Lawrence Cayton.  Algorithms for manifold learning.  Univ. of California at San Diego Tech. Rep, 12(1-17):1, 2005.
  * Chami et al. [2019] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec.  Hyperbolic graph convolutional neural networks.  In Advances in Neural Information Processing Systems, pages 4869–4880, 2019.
  * Chen et al. [2020] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li.  Simple and deep graph convolutional networks.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1725–1735. PMLR, 13–18 Jul 2020\.
  * Chen et al. [2021] Boli Chen, Yao Fu, Guangwei Xu, Pengjun Xie, Chuanqi Tan, Mosha Chen, and Liping Jing.  Probing bert in hyperbolic spaces.  arXiv preprint arXiv:2104.03869, 2021.
  * Choudhary et al. [2021] Nurendra Choudhary, Nikhil Rao, Sumeet Katariya, Karthik Subbian, and Chandan K. Reddy.  Self-supervised hyperboloid representations from logical queries over knowledge graphs.  In Proceedings of the Web Conference 2021, WWW ’21, page 1373–1384, 2021.
  * Dettmers et al. [2018] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel.  Convolutional 2d knowledge graph embeddings.  In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
  * Fefferman et al. [2016] Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan.  Testing the manifold hypothesis.  Journal of the American Mathematical Society, 29(4):983–1049, 2016\.
  * Fu et al. [2020] Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King.  Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding.  In WWW, 2020.
  * Ganea et al. [2018] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann.  Hyperbolic neural networks.  In Advances in neural information processing systems, pages 5345–5355, 2018.
  * Grover and Leskovec [2016] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864, 2016.
  * Gulcehre et al. [2019] Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, and Nando de Freitas.  Hyperbolic attention networks.  In International Conference on Learning Representations, 2019.
  * Hamilton et al. [2017] William L. Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In NIPS’17, 2017.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In International conference on machine learning, pages 448–456. PMLR, 2015.
  * Kipf and Welling [2017] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * Krioukov et al. [2010] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná.  Hyperbolic geometry of complex networks.  Physical Review E, 82(3):036106, 2010.
  * Lee [2018] John M Lee.  Introduction to Riemannian manifolds, volume 176.  Springer, 2018.
  * Lee [2019] J.M. Lee.  Introduction to Riemannian Manifolds.  Graduate Texts in Mathematics. Springer International Publishing, 2019\.
  * Lei Ba et al. [2016] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton.  Layer Normalization.  arXiv e-prints, page arXiv:1607.06450, July 2016.
  * Li et al. [2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper insights into graph convolutional networks for semi-supervised learning.  In Thirty-Second AAAI conference on artificial intelligence, 2018\.
  * Narayanan et al. [2017] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal.  graph2vec: Learning distributed representations of graphs.  arXiv preprint arXiv:1707.05005, 2017.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32:8026–8037, 2019.
  * Peng et al. [2021] Wei Peng, Tuomas Varanka, Abdelrahman Mostafa, Henglin Shi, and Guoying Zhao.  Hyperbolic deep neural networks: A survey.  arXiv preprint arXiv:2101.04562, 2021.
  * Rossi and Ahmed [2015] Ryan A. Rossi and Nesreen K. Ahmed.  The network data repository with interactive graph analytics and visualization.  In AAAI, 2015.
  * Salimans and Kingma [2016] Tim Salimans and Diederik P. Kingma.  Weight normalization: A simple reparameterization to accelerate training of deep neural networks.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 901–909, Red Hook, NY, USA, 2016\. Curran Associates Inc.
  * Scarselli et al. [2008] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  IEEE transactions on neural networks, 20(1):61–80, 2008.
  * Schlichtkrull et al. [2018] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling.  Modeling relational data with graph convolutional networks.  In European semantic web conference, pages 593–607. Springer, 2018\.
  * Sen et al. [2008] Prithviraj Sen, Galileo Mark Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad.  Collective classification in network data.  AI Magazine, 29(3):93–106, 2008.
  * Shimizu et al. [2021] Ryohei Shimizu, YUSUKE Mukuta, and Tatsuya Harada.  Hyperbolic neural networks++.  In International Conference on Learning Representations, 2021.
  * Sun et al. [2019] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang.  Rotate: Knowledge graph embedding by relational rotation in complex space.  In International Conference on Learning Representations, 2019.
  * Thanapalasingam et al. [2021] Thiviyan Thanapalasingam, Lucas van Berkel, Peter Bloem, and Paul Groth.  Relational graph convolutional networks: A closer look, 2021.
  * Toutanova et al. [2015] Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon.  Representing text for joint embedding of text and knowledge bases.  In Proceedings of the 2015 conference on empirical methods in natural language processing, pages 1499–1509, 2015.
  * Ungar [2009] Abraham Albert Ungar.  A Gyrovector Space Approach to Hyperbolic Geometry.  Synthesis Lectures on Mathematics & Statistics. Morgan & Claypool Publishers, 2009.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, pages 5998–6008, 2017.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  International Conference on Learning Representations, 2018.  accepted as poster.
  * Yang et al. [2015] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng.  Embedding entities and relations for learning and inference in knowledge bases.  In 3rd International Conference on Learning Representations, ICLR, 2015.
  * Yang et al. [2021] Tianchi Yang, Linmei Hu, Chuan Shi, Houye Ji, Xiaoli Li, and Liqiang Nie.  Hgat: Heterogeneous graph attention networks for semi-supervised short text classification.  ACM Transactions on Information Systems (TOIS), 39(3):1–29, 2021\.
  * Zhang et al. [2021] Yiding Zhang, Xiao Wang, Chuan Shi, Xunqiang Jiang, and Yanfang Fanny Ye.  Hyperbolic graph attention network.  IEEE Transactions on Big Data, pages 1–1, 2021.

## Appendices

Figure 4: (a) Calculating midpoint using the ideal tangent line. (b)
Calculating the midpoint using tangent line that is passing from point $y$.
$\alpha$ is the angle between the tangent line (from point $y$) and the ideal
tangent line. (c) Calculating the midpoint that uses a tangent line at
arbitrary point $p$.

##  Appendix A Fixating tangent space

We argued in the section “Pseudo-Poincaré Hyperbolic Networks”, we stated that
fixating tangent space does not necessarily increase the approximation error
where the adjacent embeddings do not show strong spatial locality property. In
this section, we want to dive a bit more details.

Embedding aggregations is the key operation in neural networks, and is done in
tangent space (in hyperbolic models). One can select one of the to-be-
aggregated points as the tangent space origin. Another way is to approximate
the mid-point and then derive the tangent space from that point, then to apply
the approximation222this is done usually by heuristics, empirically we did not
find the improvements generalizable.

Since the notion of curvature becomes more complicated in high-dimensional
space since the manifold can curve in many different directions, inline with
the literature Lee [2019], we focus our arguments on a sub-space of the
manifold (specifically, 2-D sub-space). The arguments can be generalized to
higher dimensions. Given 2 points in a 2D Riemannian manifold with constant
curvature (i.e., a ball or a hyperbolic-plan in the ambient space), there are
infinite planes that cross-section the manifold and passes from these two
points. The distance between these two points is equal to the shortest curve
(which lies in the optimal plane-sections), and the midpoint is a point with
identical distance between these points.

######  Lemma 5.

For a tangent line from any point in the curve (with fix curvature), the
midpoint approximation error is relative to the angle between the x-y chord
and the tangent line.

  * •

The ideal tangent line is the line that is derived from the mid-point.
Explanation. Note that curve with a contant curvature is a part of a circle,
hence, the diameter from the midpoint ($m$) is the bisector of an $xy$ arc.
based on the diameter-chord theorem, it is also the bisector of the isosceles
triangle formed by $xy$ chord and half-circle radius ($xoy$ in 4.a). This
means m-diameter is perpendicular to both ideal tangent line as well as the
$xy$ chords ($xy$ chord is parallel to the ideal tangent line). this implies
that one can calculate the mid-point of the x-y line ( $\overline{m}$ in 4.a)
and project it to the curve (perpendicular projection) and get the ideal
midpoint. Now on, we use $xy$ chord instead of the ideal tangent line.

  * •

Then we try to find the mid-point approximation behavior with respect to other
projections. Let’s start with the mid-point approximation of x,y on the curve
on the tangent line derived from y (Figure 4 (b)). let us refer to the
projection of $x$ on the $\mathcal{T}_{y}$ (tangent line) as $xy$. Also let us
project the $\overline{m}$ on the $\mathcal{T}_{y}$ and call it
$\overline{mp}$. $x.x_{y}.y$ and $\overline{m}.\overline{m_{y}}.y$ are
orthogonal triangles and $\overline{m}$ is mid-point of the hypotenuse $xy$.
Based on the mid-segment theorem, we can infer that $m_{y}$ is a mid-point of
$y.x_{y}$, and hence its perpendicular projection on the curve gives us the
approximate mid-point on the curve. Also, based on the properties of the
orthogonal triangles, we can infer the ideal projection line and the
approximated projected line form an angle $\alpha$ equal to the angle between
ideal tangent line and the tangent line from $y$.

  * •

Note that, so far, the argument was scoped to the tangent line from one of the
aggregated points ($y$ in our case). However, we can easily generalize it for
approximation on any tangent line, by drawing its parallel line that crosses
the point $y$ and apply the same trigonometry on the approximated point (Fig 4
(c)).

Thus, if the approximation happens on a tangent line of point $p$, where $p$
is between the $x$, $y$, the approximation error is smaller than the one
obtained using tangent lines at any of the points that are being aggregated.
Now, on a half-circle, if we fixate $p$ to be the origin ($p_{0}$), assuming
the given points’ coordinates have a uniform distribution there is a $50\%$
chance that $p$ lies between the aggregated points.

It should be noted as the model gets deeper, the intermediate embeddings of
the adjacent nodes/edges tend to show stronger spatial locality properties.
Thus, for last layers of a deep neural network, a mix Hyperbolic/Pseudo-
Poincaré layer is recommended. we are investigating the optimal strategy in
our future work.

##  Appendix B Proof of Lemma 2

Given $x\in\mathbb{R}^{n}$ is a Euclidean equivalent of Poincaré ball’s point
$p\in\mathbb{B}^{n}_{c}$ in the tangent space at origin
$\mathcal{T}_{0^{n}}\mathbb{B}_{c}^{n}$. The relation between $x$ and $p$, as
defined by Ganea et al. [2018] as;

$\displaystyle p=exp_{0}^{c}(x)$
$\displaystyle=\tanh(\sqrt{c}\|x\|)\frac{x}{\sqrt{c}\|x\|},$ $\displaystyle
x=log_{0}^{c}(p)=\tanh^{-1}(\sqrt{c}\|p\|)\frac{p}{\sqrt{c}\|p\|},$

Simplifying with $\omega(x)=\frac{\tanh(\sqrt{c}\|x\|)}{\sqrt{c}\|x\|}$ and
$\omega_{\mathbb{B}_{c}^{n}}(p)=\frac{\tanh^{-1}(\sqrt{c}\|p\|)}{\sqrt{c}\|p\|}$
results in:

$\displaystyle p=\omega(x)x\text{ and }x=\omega_{\mathbb{B}_{c}^{n}}(p)p$ (13)

##  Appendix C Proof of Lemma 3 and Theorem 1

Let us first look at the case of n = 1, i.e., a single hyperbolic feed-forward
layer. This is defined by Ganea et al. [2018] as;

$F_{1}^{\otimes_{c}}(p)=f_{1}^{\otimes_{c}}(p)=exp_{0}^{c}(f_{1}(log_{0}^{c}(p)))$
(14)

Reformulating this with Lemma 1,

$\displaystyle F_{1}^{\otimes_{c}}(p)$
$\displaystyle=\omega(f_{1}(log_{0}^{c}(p)))f_{1}(log_{0}^{c}(p));$
$\displaystyle\text{Substituting,
}x=log_{0}^{c}(p);~{}~{}F_{1}^{\otimes_{c}}(p)$
$\displaystyle=\omega(f_{1}(x))f_{1}(x);$ (15)

Extending this to $n=2$,

$\displaystyle F_{2}^{\otimes_{c}}(p)$
$\displaystyle=f_{2}^{\otimes_{c}}(f_{1}^{\otimes_{c}}(x))=f_{2}^{\otimes_{c}}(\omega(f_{1}(x))f_{1}(x))$
Given that $f_{1}(x)$ is a linear function; $\displaystyle f(ax)$
$\displaystyle=af(x);$ (16) $\displaystyle F_{2}^{\otimes_{c}}(p)$
$\displaystyle=\omega(f_{1}(x))f_{2}^{\otimes_{c}}(f_{1}(x));$ $\displaystyle
F_{2}^{\otimes_{c}}(p)$
$\displaystyle=\omega(f_{1}(x))\omega(f_{2}(x))f_{2}(f_{1}(x));$
$\displaystyle F_{2}^{\otimes_{c}}(p)$
$\displaystyle=\omega(f_{2}(x))\omega(f_{1}(x))F_{2}(x);$ Substituting;
$\displaystyle\Omega(F_{2}(x))$
$\displaystyle=\omega(f_{1}(x))\omega(f_{2}(x));$ (17) $\displaystyle
F_{2}^{\otimes_{c}}(p)$ $\displaystyle=\Omega(F_{2}(x))F_{2}(x);$ (18)

Extending the above formulation to arbitrary $n$,

$\displaystyle F_{n}^{\otimes_{c}}(p)$
$\displaystyle=\omega(f_{n}(x))...\omega(f_{2}(x))\omega(f_{1}(x))F_{n}(x);$

Reformulating this with Lemma 1, we get the conclusion of Lemma 2;

$\displaystyle F_{n}^{\otimes_{c}}(p)$
$\displaystyle=\exp_{0}^{c}(F_{n}(log_{0}^{c}(p)));$ (19) Substituting;
$\displaystyle\Omega(F_{n}(x))$
$\displaystyle=\omega(f_{n}(x))...\omega(f_{2}(x))\omega(f_{1}(x));$ (20) We
get the conclusion of Theorem 1; $\displaystyle F_{n}^{\otimes_{c}}(p)$
$\displaystyle=\Omega(F_{n}(x))F_{n}(x);$