M. Sc. Alice Moallemy-Oureh

Graphs in Artificial Intelligence and Neural Networks (GAIN)

Telephone: +49 561 804-6363
Fax: +49 561 804-6022
Email: amoallemy[at]uni-kassel[dot]de

Research group "Graphs in Artificial Intelligence and Neural Networks" (GAIN) (opens in a new window)

Publications

[ 2024 ]
[ 2023 ]
[ 2022 ]
[ 2021 ]

2024[ 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, Alessio; Graziani, Caterina; Lachi, Veronica; Moallemy-Oureh, Alice; Scarselli, Franco; Thomas, Josephine. In Neural Networks, 173, bl 106213. Elsevier, 2024.
- [ 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 Attributed Undirected Homogeneous Graphs (SAUHG) with node attributes. In contrast, real-life applications often involve a much larger variety of graph types. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for two other graph domains that are particularly interesting in practical applications, namely dynamic graphs and SAUGHs with edge attributes. Dynamic graphs are widely used in modern applications; hence, the study of the expressive capability of GNNs in this domain is essential for practical reasons and, in addition, it requires a new analyzing approach due to the difference in the architecture of dynamic GNNs compared to static ones. On the other hand, the examination of SAUHGs is of particular relevance since they act as a standard form for all graph types: it has been shown that all graph types can be transformed without loss of information to SAUHGs with both attributes on nodes and edges. This paper considers generic GNN models and appropriate 1-WL tests for those domains. Then, the known results on the expressive power of GNNs are extended to the mentioned domains: it is proven that GNNs have the same capability as the 1-WL test, 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 is mostly constructive and allows us to deduce hints on the architecture of GNNs that can achieve the desired approximation.
@article{beddarwiesing2024weisfeiler, 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 Attributed Undirected Homogeneous Graphs (SAUHG) with node attributes. In contrast, real-life applications often involve a much larger variety of graph types. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for two other graph domains that are particularly interesting in practical applications, namely dynamic graphs and SAUGHs with edge attributes. Dynamic graphs are widely used in modern applications; hence, the study of the expressive capability of GNNs in this domain is essential for practical reasons and, in addition, it requires a new analyzing approach due to the difference in the architecture of dynamic GNNs compared to static ones. On the other hand, the examination of SAUHGs is of particular relevance since they act as a standard form for all graph types: it has been shown that all graph types can be transformed without loss of information to SAUHGs with both attributes on nodes and edges. This paper considers generic GNN models and appropriate 1-WL tests for those domains. Then, the known results on the expressive power of GNNs are extended to the mentioned domains: it is proven that GNNs have the same capability as the 1-WL test, 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 is mostly constructive and allows us to deduce hints on the architecture of GNNs that can achieve the desired approximation.}, author = {Beddar-Wiesing, Silvia and D'Inverno, Alessio and Graziani, Caterina and Lachi, Veronica and Moallemy-Oureh, Alice and Scarselli, Franco and Thomas, Josephine}, journal = {Neural Networks}, keywords = {Graph_Neural_Network}, pages = 106213, publisher = {Elsevier}, title = {Weisfeiler–Lehman goes dynamic: An analysis of the expressive power of Graph Neural Networks for attributed and dynamic graphs}, volume = 173, year = 2024 }
%0 Journal Article %1 beddarwiesing2024weisfeiler %A Beddar-Wiesing, Silvia %A D'Inverno, Alessio %A Graziani, Caterina %A Lachi, Veronica %A Moallemy-Oureh, Alice %A Scarselli, Franco %A Thomas, Josephine %D 2024 %I Elsevier %J Neural Networks %P 106213 %R 10.1016/j.neunet.2024.106213 %T Weisfeiler–Lehman goes dynamic: An analysis of the expressive power of Graph Neural Networks for attributed and dynamic graphs %U https://www.sciencedirect.com/science/article/pii/S0893608024001370 %V 173 %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 Attributed Undirected Homogeneous Graphs (SAUHG) with node attributes. In contrast, real-life applications often involve a much larger variety of graph types. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for two other graph domains that are particularly interesting in practical applications, namely dynamic graphs and SAUGHs with edge attributes. Dynamic graphs are widely used in modern applications; hence, the study of the expressive capability of GNNs in this domain is essential for practical reasons and, in addition, it requires a new analyzing approach due to the difference in the architecture of dynamic GNNs compared to static ones. On the other hand, the examination of SAUHGs is of particular relevance since they act as a standard form for all graph types: it has been shown that all graph types can be transformed without loss of information to SAUHGs with both attributes on nodes and edges. This paper considers generic GNN models and appropriate 1-WL tests for those domains. Then, the known results on the expressive power of GNNs are extended to the mentioned domains: it is proven that GNNs have the same capability as the 1-WL test, 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 is mostly constructive and allows us to deduce hints on the architecture of GNNs that can achieve the desired approximation.

2023[ to top ]

Marked Neural Spatio-Temporal Point Process Involving a Dynamic Graph Neural Network. Moallemy-Oureh, Alice; Beddar-Wiesing, Silvia; Nather, Rüdiger; Thomas, Josephine. In Workshop on Temporal Graph Learning (TGL), NeurIPS, bll 1–7. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Spatio-Temporal Point Processes (STPPs) have recently become increasingly interesting for learning dynamic graph data since many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, are naturally related and dynamic. While training Recurrent Neural Networks and solving PDEs for representing temporal data is expensive, TPPs were a good alternative. The drawback is that constructing an appropriate TPP for modeling temporal data requires the assumption of a particular temporal behavior of the data. To overcome this problem, Neural TPPs have been developed that enable learning of the parameters of the TPP. However, the research is relatively young for modeling dynamic graphs, and only a few TPPs have been proposed to handle edge-dynamic graphs. To allow for learning on a fully dynamic graph, we propose the first Marked Neural Spatio-Temporal Point Process (MNSTPP) that leverages a Dynamic Graph Neural Network to learn Spatio-TPPs to model and predict any event in a graph stream. In addition, our model can be updated efficiently by considering single events for local retraining.
@inproceedings{moallemyoureh2023marked, abstract = {Spatio-Temporal Point Processes (STPPs) have recently become increasingly interesting for learning dynamic graph data since many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, are naturally related and dynamic. While training Recurrent Neural Networks and solving PDEs for representing temporal data is expensive, TPPs were a good alternative. The drawback is that constructing an appropriate TPP for modeling temporal data requires the assumption of a particular temporal behavior of the data. To overcome this problem, Neural TPPs have been developed that enable learning of the parameters of the TPP. However, the research is relatively young for modeling dynamic graphs, and only a few TPPs have been proposed to handle edge-dynamic graphs. To allow for learning on a fully dynamic graph, we propose the first Marked Neural Spatio-Temporal Point Process (MNSTPP) that leverages a Dynamic Graph Neural Network to learn Spatio-TPPs to model and predict any event in a graph stream. In addition, our model can be updated efficiently by considering single events for local retraining.}, author = {Moallemy-Oureh, Alice and Beddar-Wiesing, Silvia and Nather, Rüdiger and Thomas, Josephine}, booktitle = {Workshop on Temporal Graph Learning (TGL), NeurIPS}, keywords = {itegpub}, pages = {1–7}, title = {Marked Neural Spatio-Temporal Point Process Involving a Dynamic Graph Neural Network}, year = 2023 }
%0 Conference Paper %1 moallemyoureh2023marked %A Moallemy-Oureh, Alice %A Beddar-Wiesing, Silvia %A Nather, Rüdiger %A Thomas, Josephine %B Workshop on Temporal Graph Learning (TGL), NeurIPS %D 2023 %P 1--7 %T Marked Neural Spatio-Temporal Point Process Involving a Dynamic Graph Neural Network %U https://openreview.net/forum?id=QJx3Cmddsy %X Spatio-Temporal Point Processes (STPPs) have recently become increasingly interesting for learning dynamic graph data since many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, are naturally related and dynamic. While training Recurrent Neural Networks and solving PDEs for representing temporal data is expensive, TPPs were a good alternative. The drawback is that constructing an appropriate TPP for modeling temporal data requires the assumption of a particular temporal behavior of the data. To overcome this problem, Neural TPPs have been developed that enable learning of the parameters of the TPP. However, the research is relatively young for modeling dynamic graphs, and only a few TPPs have been proposed to handle edge-dynamic graphs. To allow for learning on a fully dynamic graph, we propose the first Marked Neural Spatio-Temporal Point Process (MNSTPP) that leverages a Dynamic Graph Neural Network to learn Spatio-TPPs to model and predict any event in a graph stream. In addition, our model can be updated efficiently by considering single events for local retraining.
Graph Pooling Provably Improves Expressivity. Lachi, Veronica; Moallemy-Oureh, Alice; Roth, Andreas; Welke, Pascal. In Workshop on New Frontiers in Graph Learning, NeurIPS, bll 1–7. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
In the domain of graph neural networks (GNNs), pooling operators are fundamental to reduce the size of the graph by simplifying graph structures and vertex features. Recent advances have shown that well-designed pooling operators, coupled with message-passing layers, can endow hierarchical GNNs with an expressive power regarding the graph isomorphism test that is equal to the Weisfeiler-Leman test. However, the ability of hierarchical GNNs to increase expressive power by utilizing graph coarsening was not yet explored. This results in uncertainties about the benefits of pooling operators and a lack of sufficient properties to guide their design. In this work, we identify conditions for pooling operators to generate WL-distinguishable coarsened graphs from originally WL-indistinguishable but non-isomorphic graphs. Our conditions are versatile and can be tailored to specific tasks and data characteristics, offering a promising avenue for further research.
@inproceedings{lachi2023graph, abstract = {In the domain of graph neural networks (GNNs), pooling operators are fundamental to reduce the size of the graph by simplifying graph structures and vertex features. Recent advances have shown that well-designed pooling operators, coupled with message-passing layers, can endow hierarchical GNNs with an expressive power regarding the graph isomorphism test that is equal to the Weisfeiler-Leman test. However, the ability of hierarchical GNNs to increase expressive power by utilizing graph coarsening was not yet explored. This results in uncertainties about the benefits of pooling operators and a lack of sufficient properties to guide their design. In this work, we identify conditions for pooling operators to generate WL-distinguishable coarsened graphs from originally WL-indistinguishable but non-isomorphic graphs. Our conditions are versatile and can be tailored to specific tasks and data characteristics, offering a promising avenue for further research.}, author = {Lachi, Veronica and Moallemy-Oureh, Alice and Roth, Andreas and Welke, Pascal}, booktitle = {Workshop on New Frontiers in Graph Learning, NeurIPS}, keywords = {itegpub}, pages = {1–7}, title = {Graph Pooling Provably Improves Expressivity}, year = 2023 }
%0 Conference Paper %1 lachi2023graph %A Lachi, Veronica %A Moallemy-Oureh, Alice %A Roth, Andreas %A Welke, Pascal %B Workshop on New Frontiers in Graph Learning, NeurIPS %D 2023 %P 1--7 %T Graph Pooling Provably Improves Expressivity %U https://openreview.net/forum?id=lR5NYB9zrv %X In the domain of graph neural networks (GNNs), pooling operators are fundamental to reduce the size of the graph by simplifying graph structures and vertex features. Recent advances have shown that well-designed pooling operators, coupled with message-passing layers, can endow hierarchical GNNs with an expressive power regarding the graph isomorphism test that is equal to the Weisfeiler-Leman test. However, the ability of hierarchical GNNs to increase expressive power by utilizing graph coarsening was not yet explored. This results in uncertainties about the benefits of pooling operators and a lack of sufficient properties to guide their design. In this work, we identify conditions for pooling operators to generate WL-distinguishable coarsened graphs from originally WL-indistinguishable but non-isomorphic graphs. Our conditions are versatile and can be tailored to specific tasks and data characteristics, offering a promising avenue for further research.
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.
On the Extension of the Weisfeiler-Lehman Hierarchy by WL Tests for Arbitrary Graphs. Beddar-Wiesing, Silvia; D’Inverno, Giuseppe Alessio; Graziani, Caterina; Lachi, Veronica; Moallemy-Oureh, Alice; Scarselli, Franco. In Workshp on Mining and Learning on Graphs (MLG), ECML PKDD, bll 1–13. 2022.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graph isomorphism (GI) has occupied both theoreticians and applied scientists since the early 1950s. Over the years, several approaches and algorithms with which an isomorphism between two graphs can be tested have been developed. A general approach is the Weisfeiler–Lehman (WL) test, which is based on a coloring algorithm and provides a necessary criterion for graph isomorphism. However, the WL test is restricted to examining graphs with only node attributes. Therefore, this paper presents two extensions of the WL algorithm to allow for testing on arbitrary graphs. One considers edge attributes, and the other tests the isomorphism on dynamic graphs. Additionally, we extend the WL-hierarchy by the attributed and dynamic WL tests and show that it is a partial order, which induces a lattice. In the future, this may allow for practical implications coming from lattice theory.
@inproceedings{beddarwiesing2022extension, abstract = {Graph isomorphism (GI) has occupied both theoreticians and applied scientists since the early 1950s. Over the years, several approaches and algorithms with which an isomorphism between two graphs can be tested have been developed. A general approach is the Weisfeiler–Lehman (WL) test, which is based on a coloring algorithm and provides a necessary criterion for graph isomorphism. However, the WL test is restricted to examining graphs with only node attributes. Therefore, this paper presents two extensions of the WL algorithm to allow for testing on arbitrary graphs. One considers edge attributes, and the other tests the isomorphism on dynamic graphs. Additionally, we extend the WL-hierarchy by the attributed and dynamic WL tests and show that it is a partial order, which induces a lattice. In the future, this may allow for practical implications coming from lattice theory.}, author = {Beddar-Wiesing, Silvia and D'Inverno, Giuseppe Alessio and Graziani, Caterina and Lachi, Veronica and Moallemy-Oureh, Alice and Scarselli, Franco}, booktitle = {Workshp on Mining and Learning on Graphs (MLG), ECML PKDD}, keywords = {itegpub}, pages = {1–13}, title = {On the Extension of the {W}eisfeiler-{L}ehman Hierarchy by WL Tests for Arbitrary Graphs}, year = 2022 }
%0 Conference Paper %1 beddarwiesing2022extension %A Beddar-Wiesing, Silvia %A D'Inverno, Giuseppe Alessio %A Graziani, Caterina %A Lachi, Veronica %A Moallemy-Oureh, Alice %A Scarselli, Franco %B Workshp on Mining and Learning on Graphs (MLG), ECML PKDD %D 2022 %P 1--13 %T On the Extension of the Weisfeiler-Lehman Hierarchy by WL Tests for Arbitrary Graphs %U https://openreview.net/forum?id=Qt6GrgDz2y5 %X Graph isomorphism (GI) has occupied both theoreticians and applied scientists since the early 1950s. Over the years, several approaches and algorithms with which an isomorphism between two graphs can be tested have been developed. A general approach is the Weisfeiler–Lehman (WL) test, which is based on a coloring algorithm and provides a necessary criterion for graph isomorphism. However, the WL test is restricted to examining graphs with only node attributes. Therefore, this paper presents two extensions of the WL algorithm to allow for testing on arbitrary graphs. One considers edge attributes, and the other tests the isomorphism on dynamic graphs. Additionally, we extend the WL-hierarchy by the attributed and dynamic WL tests and show that it is a partial order, which induces a lattice. In the future, this may allow for practical implications coming from lattice theory.
Graph Neural Networks Designed for Different Graph Types: A Survey. Thomas, Josephine M.; Moallemy-Oureh, Alice; Beddar-Wiesing, Silvia; Holzhüter, Clara. In arXiv e-prints, bl arXiv:2204.03080. 2022.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. Based on this, the young research field of Graph Neural Networks (GNNs) has emerged. Despite the youth of the field and the speed in which new models are developed, many good surveys have been published in the last years. Nevertheless, an overview on which graph types can be modeled by GNNs is missing. 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 as well as on dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover in the dynamic case, we separate the models in discrete-time and continuous-time dynamic graphs based on their architecture. While ordering the existing GNN models, 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{thomas2022graph, abstract = {Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. Based on this, the young research field of Graph Neural Networks (GNNs) has emerged. Despite the youth of the field and the speed in which new models are developed, many good surveys have been published in the last years. Nevertheless, an overview on which graph types can be modeled by GNNs is missing. 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 as well as on dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover in the dynamic case, we separate the models in discrete-time and continuous-time dynamic graphs based on their architecture. While ordering the existing GNN models, 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 M. and Moallemy-Oureh, Alice and Beddar-Wiesing, Silvia and Holzhüter, Clara}, journal = {arXiv e-prints}, keywords = {itegpub}, pages = {arXiv:2204.03080}, title = {Graph Neural Networks Designed for Different Graph Types: A Survey}, year = 2022 }
%0 Journal Article %1 thomas2022graph %A Thomas, Josephine M. %A Moallemy-Oureh, Alice %A Beddar-Wiesing, Silvia %A Holzhüter, Clara %D 2022 %J arXiv e-prints %P arXiv:2204.03080 %T Graph Neural Networks Designed for Different Graph Types: A Survey %U https://arxiv.org/abs/2204.03080 %X Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. Based on this, the young research field of Graph Neural Networks (GNNs) has emerged. Despite the youth of the field and the speed in which new models are developed, many good surveys have been published in the last years. Nevertheless, an overview on which graph types can be modeled by GNNs is missing. 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 as well as on dynamic graphs of different structural constitutions, with or without node or edge attributes. Moreover in the dynamic case, we separate the models in discrete-time and continuous-time dynamic graphs based on their architecture. While ordering the existing GNN models, 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.
FDGNN: Fully Dynamic Graph Neural Network. Moallemy-Oureh, Alice; Beddar-Wiesing, Silcia; Nather, Rüdiger; Thomas, Josephine M. In arXiv e-prints, bl arXiv:2206.03469. 2022.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Dynamic Graph Neural Networks recently became more and more important as graphs from many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, are dynamic by nature. While temporal changes (dynamics) play an essential role in many real-world applications, most of the models in the literature on Graph Neural Networks (GNN) process static graphs. The few GNN models on dynamic graphs only consider exceptional cases of dynamics, e.g., node attribute-dynamic graphs or structure-dynamic graphs limited to additions or changes to the graph's edges, etc. Therefore, we present a novel Fully Dynamic Graph Neural Network (FDGNN) that can handle fully-dynamic graphs in continuous time. The proposed method provides a node and an edge embedding that includes their activity to address added and deleted nodes or edges, and possible attributes. Furthermore, the embeddings specify Temporal Point Processes for each event to encode the distributions of the structure- and attribute-related incoming graph events. In addition, our model can be updated efficiently by considering single events for local retraining.
@article{moallemyoureh2022fdgnn, abstract = {Dynamic Graph Neural Networks recently became more and more important as graphs from many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, are dynamic by nature. While temporal changes (dynamics) play an essential role in many real-world applications, most of the models in the literature on Graph Neural Networks (GNN) process static graphs. The few GNN models on dynamic graphs only consider exceptional cases of dynamics, e.g., node attribute-dynamic graphs or structure-dynamic graphs limited to additions or changes to the graph's edges, etc. Therefore, we present a novel Fully Dynamic Graph Neural Network (FDGNN) that can handle fully-dynamic graphs in continuous time. The proposed method provides a node and an edge embedding that includes their activity to address added and deleted nodes or edges, and possible attributes. Furthermore, the embeddings specify Temporal Point Processes for each event to encode the distributions of the structure- and attribute-related incoming graph events. In addition, our model can be updated efficiently by considering single events for local retraining.}, author = {Moallemy-Oureh, Alice and Beddar-Wiesing, Silcia and Nather, Rüdiger and Thomas, Josephine M.}, journal = {arXiv e-prints}, keywords = {itegpub}, pages = {arXiv:2206.03469}, title = {FDGNN: Fully Dynamic Graph Neural Network}, year = 2022 }
%0 Journal Article %1 moallemyoureh2022fdgnn %A Moallemy-Oureh, Alice %A Beddar-Wiesing, Silcia %A Nather, Rüdiger %A Thomas, Josephine M. %D 2022 %J arXiv e-prints %P arXiv:2206.03469 %T FDGNN: Fully Dynamic Graph Neural Network %U https://arxiv.org/abs/2206.03469 %X Dynamic Graph Neural Networks recently became more and more important as graphs from many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, are dynamic by nature. While temporal changes (dynamics) play an essential role in many real-world applications, most of the models in the literature on Graph Neural Networks (GNN) process static graphs. The few GNN models on dynamic graphs only consider exceptional cases of dynamics, e.g., node attribute-dynamic graphs or structure-dynamic graphs limited to additions or changes to the graph's edges, etc. Therefore, we present a novel Fully Dynamic Graph Neural Network (FDGNN) that can handle fully-dynamic graphs in continuous time. The proposed method provides a node and an edge embedding that includes their activity to address added and deleted nodes or edges, and possible attributes. Furthermore, the embeddings specify Temporal Point Processes for each event to encode the distributions of the structure- and attribute-related incoming graph events. In addition, our model can be updated efficiently by considering single events for local retraining.

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.