M. Sc. Alice Moallemy-Oureh

Graphs in Artificial Intelligence and Neural Networks (GAIN)

Telefon: +49 561 804-6363
Fax: +49 561 804-6022
E-Mail: amoallemy[at]uni-kassel[dot]de

Forschungsgruppe "Graphs in Artificial Intelligence and Neural Networks" (GAIN) (öffnet neues Fenster)

Publikationen

[ 2023 ]
[ 2022 ]
[ 2021 ]

2023[ to top ]

Graph Neural Networks Designed for Different Graph Types: A Survey. Thomas, Josephine; Moallemy-Oureh, Alice; Beddar-Wiesing, Silvia; Holzhüter, Clara. In Transactions on Machine Learning Research. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. For this purpose, they can be defined as many different types which suitably reflect the individual contexts of the represented problem. To address cutting-edge problems based on graph data, the research field of Graph Neural Networks (GNNs) has emerged. Despite the field’s youth and the speed at which new models are developed, many recent surveys have been published to keep track of them. Nevertheless, it has not yet been gathered which GNN can process what kind of graph types. In this survey, we give a detailed overview of already existing GNNs and, unlike previous surveys, categorize them according to their ability to handle different graph types and properties. We consider GNNs operating on static and dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover, we distinguish between GNN models for discrete-time or continuous-time dynamic graphs and group the models according to their architecture. We find that there are still graph types that are not or only rarely covered by existing GNN models. We point out where models are missing and give potential reasons for their absence.
@article{thomas2023graph, abstract = {Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. For this purpose, they can be defined as many different types which suitably reflect the individual contexts of the represented problem. To address cutting-edge problems based on graph data, the research field of Graph Neural Networks (GNNs) has emerged. Despite the field’s youth and the speed at which new models are developed, many recent surveys have been published to keep track of them. Nevertheless, it has not yet been gathered which GNN can process what kind of graph types. In this survey, we give a detailed overview of already existing GNNs and, unlike previous surveys, categorize them according to their ability to handle different graph types and properties. We consider GNNs operating on static and dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover, we distinguish between GNN models for discrete-time or continuous-time dynamic graphs and group the models according to their architecture. We find that there are still graph types that are not or only rarely covered by existing GNN models. We point out where models are missing and give potential reasons for their absence.}, author = {Thomas, Josephine and Moallemy-Oureh, Alice and Beddar-Wiesing, Silvia and Holzhüter, Clara}, journal = {Transactions on Machine Learning Research}, keywords = {itegpub}, title = {Graph Neural Networks Designed for Different Graph Types: A Survey}, year = 2023 }
%0 Journal Article %1 thomas2023graph %A Thomas, Josephine %A Moallemy-Oureh, Alice %A Beddar-Wiesing, Silvia %A Holzhüter, Clara %D 2023 %J Transactions on Machine Learning Research %T Graph Neural Networks Designed for Different Graph Types: A Survey %U https://openreview.net/pdf?id=h4BYtZ79uy %X Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. For this purpose, they can be defined as many different types which suitably reflect the individual contexts of the represented problem. To address cutting-edge problems based on graph data, the research field of Graph Neural Networks (GNNs) has emerged. Despite the field’s youth and the speed at which new models are developed, many recent surveys have been published to keep track of them. Nevertheless, it has not yet been gathered which GNN can process what kind of graph types. In this survey, we give a detailed overview of already existing GNNs and, unlike previous surveys, categorize them according to their ability to handle different graph types and properties. We consider GNNs operating on static and dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover, we distinguish between GNN models for discrete-time or continuous-time dynamic graphs and group the models according to their architecture. We find that there are still graph types that are not or only rarely covered by existing GNN models. We point out where models are missing and give potential reasons for their absence.

2022[ to top ]

Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs. Beddar-Wiesing, Silvia; D’Inverno, Giuseppe Alessio; Graziani, Caterina; Lachi, Veronica; Moallemy-Oureh, Alice; Scarselli, Franco; Thomas, Josephine. In arXiv e-prints, bl arXiv:2210.03990. 2022.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Undirected Homogeneous Graphs with node attributes. In contrast, real-life applications often involve a variety of graph properties, such as, e.g., dynamics or node and edge attributes. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for these two graph types that are particularly of interest. Dynamic graphs are widely used in modern applications, and its theoretical analysis requires new approaches. The attributed type acts as a standard form for all graph types since it has been shown that all graph types can be transformed without loss to Static Undirected Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study considers generic GNN models and proposes appropriate 1-WL tests for those domains. Then, the results on the expressive power of GNNs are extended by proving that GNNs have the same capability as the 1-WL test in distinguishing dynamic and attributed graphs, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence. Moreover, the proof of the approximation capability holds for SAUHGs, which include most of those used in practical applications, and it is constructive in nature allowing to deduce hints on the architecture of GNNs that can achieve the desired accuracy.
@article{beddarwiesing2022weisfeiler, abstract = {Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Undirected Homogeneous Graphs with node attributes. In contrast, real-life applications often involve a variety of graph properties, such as, e.g., dynamics or node and edge attributes. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for these two graph types that are particularly of interest. Dynamic graphs are widely used in modern applications, and its theoretical analysis requires new approaches. The attributed type acts as a standard form for all graph types since it has been shown that all graph types can be transformed without loss to Static Undirected Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study considers generic GNN models and proposes appropriate 1-WL tests for those domains. Then, the results on the expressive power of GNNs are extended by proving that GNNs have the same capability as the 1-WL test in distinguishing dynamic and attributed graphs, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence. Moreover, the proof of the approximation capability holds for SAUHGs, which include most of those used in practical applications, and it is constructive in nature allowing to deduce hints on the architecture of GNNs that can achieve the desired accuracy.}, author = {Beddar-Wiesing, Silvia and D'Inverno, Giuseppe Alessio and Graziani, Caterina and Lachi, Veronica and Moallemy-Oureh, Alice and Scarselli, Franco and Thomas, Josephine}, journal = {arXiv e-prints}, keywords = {itegpub}, pages = {arXiv:2210.03990}, title = {{W}eisfeiler-{L}ehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs}, year = 2022 }
%0 Journal Article %1 beddarwiesing2022weisfeiler %A Beddar-Wiesing, Silvia %A D'Inverno, Giuseppe Alessio %A Graziani, Caterina %A Lachi, Veronica %A Moallemy-Oureh, Alice %A Scarselli, Franco %A Thomas, Josephine %D 2022 %J arXiv e-prints %P arXiv:2210.03990 %T Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs %U https://arxiv.org/abs/2210.03990 %X Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Undirected Homogeneous Graphs with node attributes. In contrast, real-life applications often involve a variety of graph properties, such as, e.g., dynamics or node and edge attributes. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for these two graph types that are particularly of interest. Dynamic graphs are widely used in modern applications, and its theoretical analysis requires new approaches. The attributed type acts as a standard form for all graph types since it has been shown that all graph types can be transformed without loss to Static Undirected Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study considers generic GNN models and proposes appropriate 1-WL tests for those domains. Then, the results on the expressive power of GNNs are extended by proving that GNNs have the same capability as the 1-WL test in distinguishing dynamic and attributed graphs, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence. Moreover, the proof of the approximation capability holds for SAUHGs, which include most of those used in practical applications, and it is constructive in nature allowing to deduce hints on the architecture of GNNs that can achieve the desired accuracy.
Student Research Abstract: Continuous-Time Generative Graph Neural Network for Attributed Dynamic Graphs. Moallemy-Oureh, Alice. In ACM/SIGAPP Symposium on Applied Computing (SAC), bll 600–603. ACM, 2022.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
The history of neural networks dates back to the early 1940s and has not only evolved rapidly over time but they are now amongst one of the most popular and powerful machine learning techniques. In this area, graph representation learning (GRL) using graph neural networks (GNNs) has emerged during the early 90s and developed into an impactful approach for modeling graph-structured real-world data, such as social or biological networks. There are a variety of successful applications of GRL in computational neuroscience, chemistry, mathematics, and so on. While temporal changes (dynamics) play an essential role in many real-world applications, most of the literature on GNNs and GRL, deals with static graphs. Since the few GNN models on dynamic graphs only consider exceptional cases of dynamics (i.e., attribute-dynamic graphs in discrete-time representation or structure-dynamic graphs in continuous-time representation), we aim to present a novel GNN model that can handle attribute-dynamic graphs in continuous time. This model learns any kind of graph information embedding, performs node/edge attribute forecasts, and allows for attribute-dynamic graph generation in both discrete and continuous-time.
@inproceedings{moallemyoureh2022student, abstract = {The history of neural networks dates back to the early 1940s and has not only evolved rapidly over time but they are now amongst one of the most popular and powerful machine learning techniques. In this area, graph representation learning (GRL) using graph neural networks (GNNs) has emerged during the early 90s and developed into an impactful approach for modeling graph-structured real-world data, such as social or biological networks. There are a variety of successful applications of GRL in computational neuroscience, chemistry, mathematics, and so on. While temporal changes (dynamics) play an essential role in many real-world applications, most of the literature on GNNs and GRL, deals with static graphs. Since the few GNN models on dynamic graphs only consider exceptional cases of dynamics (i.e., attribute-dynamic graphs in discrete-time representation or structure-dynamic graphs in continuous-time representation), we aim to present a novel GNN model that can handle attribute-dynamic graphs in continuous time. This model learns any kind of graph information embedding, performs node/edge attribute forecasts, and allows for attribute-dynamic graph generation in both discrete and continuous-time.}, author = {Moallemy-Oureh, Alice}, booktitle = {ACM/SIGAPP Symposium on Applied Computing (SAC)}, keywords = {itegpub}, pages = {600–603}, publisher = {ACM}, title = {Student Research Abstract: Continuous-Time Generative Graph Neural Network for Attributed Dynamic Graphs}, year = 2022 }
%0 Conference Paper %1 moallemyoureh2022student %A Moallemy-Oureh, Alice %B ACM/SIGAPP Symposium on Applied Computing (SAC) %D 2022 %I ACM %P 600--603 %R 10.1145/3477314.3508018 %T Student Research Abstract: Continuous-Time Generative Graph Neural Network for Attributed Dynamic Graphs %U https://dl.acm.org/doi/abs/10.1145/3477314.3508018 %X The history of neural networks dates back to the early 1940s and has not only evolved rapidly over time but they are now amongst one of the most popular and powerful machine learning techniques. In this area, graph representation learning (GRL) using graph neural networks (GNNs) has emerged during the early 90s and developed into an impactful approach for modeling graph-structured real-world data, such as social or biological networks. There are a variety of successful applications of GRL in computational neuroscience, chemistry, mathematics, and so on. While temporal changes (dynamics) play an essential role in many real-world applications, most of the literature on GNNs and GRL, deals with static graphs. Since the few GNN models on dynamic graphs only consider exceptional cases of dynamics (i.e., attribute-dynamic graphs in discrete-time representation or structure-dynamic graphs in continuous-time representation), we aim to present a novel GNN model that can handle attribute-dynamic graphs in continuous time. This model learns any kind of graph information embedding, performs node/edge attribute forecasts, and allows for attribute-dynamic graph generation in both discrete and continuous-time.

2021[ to top ]

A Note on the Modeling Power of Different Graph Types. Thomas, Josephine M.; Beddar-Wiesing, Silvia; Moallemy-Oureh, Alice; Nather, Rüdiger. In arXiv e-prints, bl arXiv:2109.10708. 2021.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graphs can have different properties that lead to several graph types and may allow for a varying representation of diverse information. In order to clarify the modeling power of graphs, we introduce a partial order on the most common graph types based on an expressivity relation. The expressivity relation quantifies how many properties a graph type can encode compared to another type. Additionally, we show that all attributed graph types are equally expressive and have the same modeling power.
@article{thomas2021note, abstract = {Graphs can have different properties that lead to several graph types and may allow for a varying representation of diverse information. In order to clarify the modeling power of graphs, we introduce a partial order on the most common graph types based on an expressivity relation. The expressivity relation quantifies how many properties a graph type can encode compared to another type. Additionally, we show that all attributed graph types are equally expressive and have the same modeling power.}, author = {Thomas, Josephine M. and Beddar-Wiesing, Silvia and Moallemy-Oureh, Alice and Nather, Rüdiger}, journal = {arXiv e-prints}, keywords = {itegpub}, pages = {arXiv:2109.10708}, title = {A Note on the Modeling Power of Different Graph Types}, year = 2021 }
%0 Journal Article %1 thomas2021note %A Thomas, Josephine M. %A Beddar-Wiesing, Silvia %A Moallemy-Oureh, Alice %A Nather, Rüdiger %D 2021 %J arXiv e-prints %P arXiv:2109.10708 %T A Note on the Modeling Power of Different Graph Types %U https://arxiv.org/abs/2109.10708 %X Graphs can have different properties that lead to several graph types and may allow for a varying representation of diverse information. In order to clarify the modeling power of graphs, we introduce a partial order on the most common graph types based on an expressivity relation. The expressivity relation quantifies how many properties a graph type can encode compared to another type. Additionally, we show that all attributed graph types are equally expressive and have the same modeling power.