M. Sc. Silvia Beddar-Wiesing

Graphs in Artificial Intelligence and Neural Networks (GAIN)

Telefon: +49 561 804-6454
E-Mail: s.beddarwiesing[at]uni-kassel[dot]de

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

Publikationen

[ 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 ]

Time-aware Robustness of Temporal Graph Neural Networks for Link Prediction. Sälzer, Marco; Beddar-Wiesing, Silvia. In International Symposium on Temporal Representation and Reasoning (TIME), bll 19:1–19:3. 2023.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
Graph Neural Networks (GNNs) provide a framework for computing functions over graphs based on learnable parameters, which gained much attention in recent years. The most popular GNN models, so-called convolutional GNN or message-passing GNN apply a neighborhood aggregation procedure to each node in a graph to compute its output. Usually, such GNNs are used for classification or prediction tasks over static graphs. However, this limits their applicability in contexts like social networks or knowledge graphs, where underlying graphs change stepwise or time-continuously. Temporal Graph Neural Networks (TGNN) try to close this gap. The general idea of TGNN is to generalize the neighborhood aggregation procedure mentioned above to temporal graphs, usually represented as a tuple of a base graph with a series of time-stamped observed changes. In most applications involving Neural Network based models, giving reliable safety certificates are highly desirable but also a significant challenge, especially because of the blackbox nature of neural models. In this extended abstract, we address the topic of verifying TGNN, which is an unexplored area of research. We present a first notion of a time-aware robustness property for TGNN used for link prediction tasks, motivated by recent work on similar time-aware attacks. Furthermore, we discuss our ongoing work regarding promising verification approaches for the presented or similar safety properties and possible next steps in this research direction.
@inproceedings{salzer2023time, abstract = {Graph Neural Networks (GNNs) provide a framework for computing functions over graphs based on learnable parameters, which gained much attention in recent years. The most popular GNN models, so-called convolutional GNN or message-passing GNN apply a neighborhood aggregation procedure to each node in a graph to compute its output. Usually, such GNNs are used for classification or prediction tasks over static graphs. However, this limits their applicability in contexts like social networks or knowledge graphs, where underlying graphs change stepwise or time-continuously. Temporal Graph Neural Networks (TGNN) try to close this gap. The general idea of TGNN is to generalize the neighborhood aggregation procedure mentioned above to temporal graphs, usually represented as a tuple of a base graph with a series of time-stamped observed changes. In most applications involving Neural Network based models, giving reliable safety certificates are highly desirable but also a significant challenge, especially because of the blackbox nature of neural models. In this extended abstract, we address the topic of verifying TGNN, which is an unexplored area of research. We present a first notion of a time-aware robustness property for TGNN used for link prediction tasks, motivated by recent work on similar time-aware attacks. Furthermore, we discuss our ongoing work regarding promising verification approaches for the presented or similar safety properties and possible next steps in this research direction.}, author = {Sälzer, Marco and Beddar-Wiesing, Silvia}, booktitle = {International Symposium on Temporal Representation and Reasoning (TIME)}, keywords = {itegpub}, pages = {19:1–19:3}, title = {Time-aware Robustness of Temporal Graph Neural Networks for Link Prediction}, year = 2023 }
%0 Conference Paper %1 salzer2023time %A Sälzer, Marco %A Beddar-Wiesing, Silvia %B International Symposium on Temporal Representation and Reasoning (TIME) %D 2023 %P 19:1--19:3 %R 10.4230/LIPIcs.TIME.2023.19 %T Time-aware Robustness of Temporal Graph Neural Networks for Link Prediction %X Graph Neural Networks (GNNs) provide a framework for computing functions over graphs based on learnable parameters, which gained much attention in recent years. The most popular GNN models, so-called convolutional GNN or message-passing GNN apply a neighborhood aggregation procedure to each node in a graph to compute its output. Usually, such GNNs are used for classification or prediction tasks over static graphs. However, this limits their applicability in contexts like social networks or knowledge graphs, where underlying graphs change stepwise or time-continuously. Temporal Graph Neural Networks (TGNN) try to close this gap. The general idea of TGNN is to generalize the neighborhood aggregation procedure mentioned above to temporal graphs, usually represented as a tuple of a base graph with a series of time-stamped observed changes. In most applications involving Neural Network based models, giving reliable safety certificates are highly desirable but also a significant challenge, especially because of the blackbox nature of neural models. In this extended abstract, we address the topic of verifying TGNN, which is an unexplored area of research. We present a first notion of a time-aware robustness property for TGNN used for link prediction tasks, motivated by recent work on similar time-aware attacks. Furthermore, we discuss our ongoing work regarding promising verification approaches for the presented or similar safety properties and possible next steps in this research direction.
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 ]
Temporal Point Processes (TPPs) have recently become increasingly interesting for learning dynamics in graph data. A reason for this is that learning on dynamic graph data is becoming more relevant, since data from many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, is naturally related and inherently dynamic. In addition, TPPs provide a meaningful characterization of event streams and a prediction mechanism for future events. Therefore, (semi-)parameterized Neural TPPs have been introduced whose characterization can be (partially) learned and, thus, enable the representation of more complex phenomena. However, the research on modeling dynamic graphs with TPPs is relatively young, and only a few models for node attribute changes or evolving edges have been proposed yet. To allow for learning on fully dynamic graph streams, i.e., graphs that can change in their structure (addition/deletion of nodes/edge) and in their node/edge attributes, we propose a Marked Neural Spatio-Temporal Point Process (MNSTPP). It leverages a Dynamic Graph Neural Network to learn a Marked TPP that handles attributes and spatial data to model and predict any event in a graph stream.
@inproceedings{moallemyoureh2023marked, abstract = {Temporal Point Processes (TPPs) have recently become increasingly interesting for learning dynamics in graph data. A reason for this is that learning on dynamic graph data is becoming more relevant, since data from many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, is naturally related and inherently dynamic. In addition, TPPs provide a meaningful characterization of event streams and a prediction mechanism for future events. Therefore, (semi-)parameterized Neural TPPs have been introduced whose characterization can be (partially) learned and, thus, enable the representation of more complex phenomena. However, the research on modeling dynamic graphs with TPPs is relatively young, and only a few models for node attribute changes or evolving edges have been proposed yet. To allow for learning on fully dynamic graph streams, i.e., graphs that can change in their structure (addition/deletion of nodes/edge) and in their node/edge attributes, we propose a Marked Neural Spatio-Temporal Point Process (MNSTPP). It leverages a Dynamic Graph Neural Network to learn a Marked TPP that handles attributes and spatial data to model and predict any event in a graph stream.}, 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 Temporal Point Processes (TPPs) have recently become increasingly interesting for learning dynamics in graph data. A reason for this is that learning on dynamic graph data is becoming more relevant, since data from many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, is naturally related and inherently dynamic. In addition, TPPs provide a meaningful characterization of event streams and a prediction mechanism for future events. Therefore, (semi-)parameterized Neural TPPs have been introduced whose characterization can be (partially) learned and, thus, enable the representation of more complex phenomena. However, the research on modeling dynamic graphs with TPPs is relatively young, and only a few models for node attribute changes or evolving edges have been proposed yet. To allow for learning on fully dynamic graph streams, i.e., graphs that can change in their structure (addition/deletion of nodes/edge) and in their node/edge attributes, we propose a Marked Neural Spatio-Temporal Point Process (MNSTPP). It leverages a Dynamic Graph Neural Network to learn a Marked TPP that handles attributes and spatial data to model and predict any event in a graph stream.
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: Using Local Activity Encoding for Dynamic Graph Pooling in Stuctural-Dynamic Graphs. Beddar-Wiesing, Silvia. In ACM/SIGAPP Symposium on Applied Computing (SAC), bll 604–609. ACM, 2022.
- [ 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.
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.