M. Sc. Silvia Beddar-Wiesing

Graphs in Artificial Intelligence and Neural Networks (GAIN)

Telephone: +49 561 804-6454
Email: s.beddarwiesing[at]uni-kassel[dot]de

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

Publications

[ 2023 ]
[ 2022 ]
[ 2021 ]

2023[ to top ]

Thomas, J., Moallemy-Oureh, A., Beddar-Wiesing, S., Holzhüter, C.: Graph Neural Networks Designed for Different Graph Types: A Survey 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 ]

Beddar-Wiesing, S., D’Inverno, G.A., Graziani, C., Lachi, V., Moallemy-Oureh, A., Scarselli, F., Thomas, J.: Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs arXiv e-prints. 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.
Beddar-Wiesing, S.: Student Research Abstract: Using Local Activity Encoding for Dynamic Graph Pooling in Stuctural-Dynamic Graphs In: ACM/SIGAPP Symposium on Applied Computing (SAC). bll 604–609. ACM (2022). https://doi.org/10.1145/3477314.3506969.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Graphs have recently become more popular for modeling real-world as well as theoretical problems, and several Machine Learning algorithms for learning on them have developed. For graphs that change over time, however, research is still at an early stage. This article proposes a framework DynHeatmaP that generates a constant-size graph sequence representation of graphs whose structure changes over time (structural-dynamic, SDG) in linear time. The framework uses a representation of additions and deletions of nodes and edges (events) to perform dynamic graph pooling. Our algorithm translates the dynamic changes of the nodes and edges to a heatmap representation of the current node activity, regarding additions and deletions in the neighborhood, respectively. The created activity heatmap is utilized as probabilities of the nodes to be sampled in the subsequent pooling step. In addition, the neighborhood of selected nodes has been sampled such that the ratio of additions and deletions is represented accordingly. The obtained downsampled graph sequence can then be used representatively as input to a GNN for learning on the original stream. Focussing on the active regions in a graph, the fast pooling process can reduce the training time significantly and addresses the problem of unbalanced datasets in real-world applications modeled as sparse graphs.
@inproceedings{beddarwiesing2022student, abstract = {Graphs have recently become more popular for modeling real-world as well as theoretical problems, and several Machine Learning algorithms for learning on them have developed. For graphs that change over time, however, research is still at an early stage. This article proposes a framework DynHeatmaP that generates a constant-size graph sequence representation of graphs whose structure changes over time (structural-dynamic, SDG) in linear time. The framework uses a representation of additions and deletions of nodes and edges (events) to perform dynamic graph pooling. Our algorithm translates the dynamic changes of the nodes and edges to a heatmap representation of the current node activity, regarding additions and deletions in the neighborhood, respectively. The created activity heatmap is utilized as probabilities of the nodes to be sampled in the subsequent pooling step. In addition, the neighborhood of selected nodes has been sampled such that the ratio of additions and deletions is represented accordingly. The obtained downsampled graph sequence can then be used representatively as input to a GNN for learning on the original stream. Focussing on the active regions in a graph, the fast pooling process can reduce the training time significantly and addresses the problem of unbalanced datasets in real-world applications modeled as sparse graphs.}, author = {Beddar-Wiesing, Silvia}, booktitle = {ACM/SIGAPP Symposium on Applied Computing (SAC)}, keywords = {itegpub}, pages = {604–609}, publisher = {ACM}, title = {Student Research Abstract: Using Local Activity Encoding for Dynamic Graph Pooling in Stuctural-Dynamic Graphs}, year = 2022 }
%0 Conference Paper %1 beddarwiesing2022student %A Beddar-Wiesing, Silvia %B ACM/SIGAPP Symposium on Applied Computing (SAC) %D 2022 %I ACM %P 604--609 %R 10.1145/3477314.3506969 %T Student Research Abstract: Using Local Activity Encoding for Dynamic Graph Pooling in Stuctural-Dynamic Graphs %U https://dl.acm.org/doi/abs/10.1145/3477314.3506969 %X Graphs have recently become more popular for modeling real-world as well as theoretical problems, and several Machine Learning algorithms for learning on them have developed. For graphs that change over time, however, research is still at an early stage. This article proposes a framework DynHeatmaP that generates a constant-size graph sequence representation of graphs whose structure changes over time (structural-dynamic, SDG) in linear time. The framework uses a representation of additions and deletions of nodes and edges (events) to perform dynamic graph pooling. Our algorithm translates the dynamic changes of the nodes and edges to a heatmap representation of the current node activity, regarding additions and deletions in the neighborhood, respectively. The created activity heatmap is utilized as probabilities of the nodes to be sampled in the subsequent pooling step. In addition, the neighborhood of selected nodes has been sampled such that the ratio of additions and deletions is represented accordingly. The obtained downsampled graph sequence can then be used representatively as input to a GNN for learning on the original stream. Focussing on the active regions in a graph, the fast pooling process can reduce the training time significantly and addresses the problem of unbalanced datasets in real-world applications modeled as sparse graphs.

2021[ to top ]

Thomas, J.M., Beddar-Wiesing, S., Moallemy-Oureh, A., Nather, R.: A Note on the Modeling Power of Different Graph Types arXiv e-prints. 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.