Dr. Josephine Thomas

Team Leader: Graphs in Artificial Intelligence and Neural Networks (GAIN)

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

Website: Josephine Thomas

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

Publications

[ 2024 ]
[ 2023 ]
[ 2022 ]
[ 2021 ]
[ 2017 ]
[ 2015 ]

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 ]

Power flow forecasts at transmission grid nodes using Graph Neural Networks. Beinert, Dominik; Holzhüter, Clara; Thomas, Josephine; Vogt, Stephan. In Energy and AI, 14(1), bl 100262. Elsevier, 2023.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
The increasing share of renewable energy in the electricity grid and progressing changes in power consumption have led to fluctuating, and weather-dependent power flows. To ensure grid stability, grid operators rely on power forecasts which are crucial for grid calculations and planning. In this paper, a Multi-Task Learning approach is combined with a Graph Neural Network (GNN) to predict vertical power flows at transformers connecting high and extra-high voltage levels. The proposed method accounts for local differences in power flow characteristics by using an Embedding Multi-Task Learning approach. The use of a Bayesian embedding to capture the latent node characteristics allows to share the weights across all transformers in the subsequent node-invariant GNN while still allowing the individual behavioral patterns of the transformers to be distinguished. At the same time, dependencies between transformers are considered by the GNN architecture which can learn relationships between different transformers and thus take into account that power flows in an electricity network are not independent from each other. The effectiveness of the proposed method is demonstrated through evaluation on two real-world data sets provided by two of four German Transmission System Operators, comprising large portions of the operated German transmission grid. The results show that the proposed Multi-Task Graph Neural Network is a suitable representation learner for electricity networks with a clear advantage provided by the preceding embedding layer. It is able to capture interconnections between correlated transformers and indeed improves the performance in power flow prediction compared to standard Neural Networks. A sign test shows that the proposed model reduces the test RMSE on both data sets compared to the benchmark models significantly.
@article{beinert2023power, abstract = {The increasing share of renewable energy in the electricity grid and progressing changes in power consumption have led to fluctuating, and weather-dependent power flows. To ensure grid stability, grid operators rely on power forecasts which are crucial for grid calculations and planning. In this paper, a Multi-Task Learning approach is combined with a Graph Neural Network (GNN) to predict vertical power flows at transformers connecting high and extra-high voltage levels. The proposed method accounts for local differences in power flow characteristics by using an Embedding Multi-Task Learning approach. The use of a Bayesian embedding to capture the latent node characteristics allows to share the weights across all transformers in the subsequent node-invariant GNN while still allowing the individual behavioral patterns of the transformers to be distinguished. At the same time, dependencies between transformers are considered by the GNN architecture which can learn relationships between different transformers and thus take into account that power flows in an electricity network are not independent from each other. The effectiveness of the proposed method is demonstrated through evaluation on two real-world data sets provided by two of four German Transmission System Operators, comprising large portions of the operated German transmission grid. The results show that the proposed Multi-Task Graph Neural Network is a suitable representation learner for electricity networks with a clear advantage provided by the preceding embedding layer. It is able to capture interconnections between correlated transformers and indeed improves the performance in power flow prediction compared to standard Neural Networks. A sign test shows that the proposed model reduces the test RMSE on both data sets compared to the benchmark models significantly.}, author = {Beinert, Dominik and Holzhüter, Clara and Thomas, Josephine and Vogt, Stephan}, journal = {Energy and AI}, keywords = {itegpub}, number = 1, pages = 100262, publisher = {Elsevier}, title = {Power flow forecasts at transmission grid nodes using Graph Neural Networks}, volume = 14, year = 2023 }
%0 Journal Article %1 beinert2023power %A Beinert, Dominik %A Holzhüter, Clara %A Thomas, Josephine %A Vogt, Stephan %D 2023 %I Elsevier %J Energy and AI %N 1 %P 100262 %R 10.1016/j.egyai.2023.100262 %T Power flow forecasts at transmission grid nodes using Graph Neural Networks %U https://www.sciencedirect.com/science/article/pii/S2666546823000344?via%3Dihub %V 14 %X The increasing share of renewable energy in the electricity grid and progressing changes in power consumption have led to fluctuating, and weather-dependent power flows. To ensure grid stability, grid operators rely on power forecasts which are crucial for grid calculations and planning. In this paper, a Multi-Task Learning approach is combined with a Graph Neural Network (GNN) to predict vertical power flows at transformers connecting high and extra-high voltage levels. The proposed method accounts for local differences in power flow characteristics by using an Embedding Multi-Task Learning approach. The use of a Bayesian embedding to capture the latent node characteristics allows to share the weights across all transformers in the subsequent node-invariant GNN while still allowing the individual behavioral patterns of the transformers to be distinguished. At the same time, dependencies between transformers are considered by the GNN architecture which can learn relationships between different transformers and thus take into account that power flows in an electricity network are not independent from each other. The effectiveness of the proposed method is demonstrated through evaluation on two real-world data sets provided by two of four German Transmission System Operators, comprising large portions of the operated German transmission grid. The results show that the proposed Multi-Task Graph Neural Network is a suitable representation learner for electricity networks with a clear advantage provided by the preceding embedding layer. It is able to capture interconnections between correlated transformers and indeed improves the performance in power flow prediction compared to standard Neural Networks. A sign test shows that the proposed model reduces the test RMSE on both data sets compared to the benchmark models significantly.
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.
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.

2017[ to top ]

Pioneering topological methods for network-based drug–target prediction by exploiting a brain-network self-organization theory. Durán, Claudio; Daminelli, Simone; M., Thomas Josephine; Haupt, V. Joachim; Schroeder, Michael; Cannistraci, Carlo Vittorio. In Briefings in Bioinformatics, 19(6), bll 1183–1202. 2017.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
The bipartite network representation of the drug–target interactions (DTIs) in a biosystem enhances understanding of the drugs’ multifaceted action modes, suggests therapeutic switching for approved drugs and unveils possible side effects. As experimental testing of DTIs is costly and time-consuming, computational predictors are of great aid. Here, for the first time, state-of-the-art DTI supervised predictors custom-made in network biology were compared—using standard and innovative validation frameworks—with unsupervised pure topological-based models designed for general-purpose link prediction in bipartite networks. Surprisingly, our results show that the bipartite topology alone, if adequately exploited by means of the recently proposed local-community-paradigm (LCP) theory—initially detected in brain-network topological self-organization and afterwards generalized to any complex network—is able to suggest highly reliable predictions, with comparable performance with the state-of-the-art-supervised methods that exploit additional (non-topological, for instance biochemical) DTI knowledge. Furthermore, a detailed analysis of the novel predictions revealed that each class of methods prioritizes distinct true interactions; hence, combining methodologies based on diverse principles represents a promising strategy to improve drug–target discovery. To conclude, this study promotes the power of bio-inspired computing, demonstrating that simple unsupervised rules inspired by principles of topological self-organization and adaptiveness arising during learning in living intelligent systems (like the brain) can efficiently equal perform complicated algorithms based on advanced, supervised and knowledge-based engineering.
@article{duran2017pioneering, abstract = {The bipartite network representation of the drug–target interactions (DTIs) in a biosystem enhances understanding of the drugs’ multifaceted action modes, suggests therapeutic switching for approved drugs and unveils possible side effects. As experimental testing of DTIs is costly and time-consuming, computational predictors are of great aid. Here, for the first time, state-of-the-art DTI supervised predictors custom-made in network biology were compared—using standard and innovative validation frameworks—with unsupervised pure topological-based models designed for general-purpose link prediction in bipartite networks. Surprisingly, our results show that the bipartite topology alone, if adequately exploited by means of the recently proposed local-community-paradigm (LCP) theory—initially detected in brain-network topological self-organization and afterwards generalized to any complex network—is able to suggest highly reliable predictions, with comparable performance with the state-of-the-art-supervised methods that exploit additional (non-topological, for instance biochemical) DTI knowledge. Furthermore, a detailed analysis of the novel predictions revealed that each class of methods prioritizes distinct true interactions; hence, combining methodologies based on diverse principles represents a promising strategy to improve drug–target discovery. To conclude, this study promotes the power of bio-inspired computing, demonstrating that simple unsupervised rules inspired by principles of topological self-organization and adaptiveness arising during learning in living intelligent systems (like the brain) can efficiently equal perform complicated algorithms based on advanced, supervised and knowledge-based engineering.}, author = {Durán, Claudio and Daminelli, Simone and M., Thomas Josephine and Haupt, V. Joachim and Schroeder, Michael and Cannistraci, Carlo Vittorio}, journal = {Briefings in Bioinformatics}, keywords = {link-prediction}, number = 6, pages = {1183–1202}, title = {Pioneering topological methods for network-based drug–target prediction by exploiting a brain-network self-organization theory}, volume = 19, year = 2017 }
%0 Journal Article %1 duran2017pioneering %A Durán, Claudio %A Daminelli, Simone %A M., Thomas Josephine %A Haupt, V. Joachim %A Schroeder, Michael %A Cannistraci, Carlo Vittorio %D 2017 %J Briefings in Bioinformatics %N 6 %P 1183--1202 %R 10.1093/bib/bbx041 %T Pioneering topological methods for network-based drug–target prediction by exploiting a brain-network self-organization theory %U https://academic.oup.com/bib/article/19/6/1183/3769276 %V 19 %X The bipartite network representation of the drug–target interactions (DTIs) in a biosystem enhances understanding of the drugs’ multifaceted action modes, suggests therapeutic switching for approved drugs and unveils possible side effects. As experimental testing of DTIs is costly and time-consuming, computational predictors are of great aid. Here, for the first time, state-of-the-art DTI supervised predictors custom-made in network biology were compared—using standard and innovative validation frameworks—with unsupervised pure topological-based models designed for general-purpose link prediction in bipartite networks. Surprisingly, our results show that the bipartite topology alone, if adequately exploited by means of the recently proposed local-community-paradigm (LCP) theory—initially detected in brain-network topological self-organization and afterwards generalized to any complex network—is able to suggest highly reliable predictions, with comparable performance with the state-of-the-art-supervised methods that exploit additional (non-topological, for instance biochemical) DTI knowledge. Furthermore, a detailed analysis of the novel predictions revealed that each class of methods prioritizes distinct true interactions; hence, combining methodologies based on diverse principles represents a promising strategy to improve drug–target discovery. To conclude, this study promotes the power of bio-inspired computing, demonstrating that simple unsupervised rules inspired by principles of topological self-organization and adaptiveness arising during learning in living intelligent systems (like the brain) can efficiently equal perform complicated algorithms based on advanced, supervised and knowledge-based engineering.
Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Muscoloni, Alessandro; Thomas, Josephine Maria; Ciucci, Sara; Bianconi, Ginestra; Cannistraci, Carlo Vittorio. In Nature Communications, 8(1), bl 1615. Springer, 2017.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Physicists recently observed that realistic complex networks emerge as discrete samples from a continuous hyperbolic geometry enclosed in a circle: the radius represents the node centrality and the angular displacement between two nodes resembles their topological proximity. The hyperbolic circle aims to become a universal space of representation and analysis of many real networks. Yet, inferring the angular coordinates to map a real network back to its latent geometry remains a challenging inverse problem. Here, we show that intelligent machines for unsupervised recognition and visualization of similarities in big data can also infer the network angular coordinates of the hyperbolic model according to a geometrical organization that we term "angular coalescence." Based on this phenomenon, we propose a class of algorithms that offers fast and accurate "coalescent embedding" in the hyperbolic circle even for large networks. This computational solution to an inverse problem in physics of complex systems favors the application of network latent geometry techniques in disciplines dealing with big network data analysis including biology, medicine, and social science.
@article{muscoloni2017machine, abstract = {Physicists recently observed that realistic complex networks emerge as discrete samples from a continuous hyperbolic geometry enclosed in a circle: the radius represents the node centrality and the angular displacement between two nodes resembles their topological proximity. The hyperbolic circle aims to become a universal space of representation and analysis of many real networks. Yet, inferring the angular coordinates to map a real network back to its latent geometry remains a challenging inverse problem. Here, we show that intelligent machines for unsupervised recognition and visualization of similarities in big data can also infer the network angular coordinates of the hyperbolic model according to a geometrical organization that we term "angular coalescence." Based on this phenomenon, we propose a class of algorithms that offers fast and accurate "coalescent embedding" in the hyperbolic circle even for large networks. This computational solution to an inverse problem in physics of complex systems favors the application of network latent geometry techniques in disciplines dealing with big network data analysis including biology, medicine, and social science.}, author = {Muscoloni, Alessandro and Thomas, Josephine Maria and Ciucci, Sara and Bianconi, Ginestra and Cannistraci, Carlo Vittorio}, journal = {Nature Communications}, keywords = {not_ies}, number = 1, pages = 1615, publisher = {Springer}, title = {Machine learning meets complex networks via coalescent embedding in the hyperbolic space}, volume = 8, year = 2017 }
%0 Journal Article %1 muscoloni2017machine %A Muscoloni, Alessandro %A Thomas, Josephine Maria %A Ciucci, Sara %A Bianconi, Ginestra %A Cannistraci, Carlo Vittorio %D 2017 %I Springer %J Nature Communications %N 1 %P 1615 %R 10.1038/s41467-017-01825-5 %T Machine learning meets complex networks via coalescent embedding in the hyperbolic space %U https://doi.org/10.1038/s41467-017-01825-5 %V 8 %X Physicists recently observed that realistic complex networks emerge as discrete samples from a continuous hyperbolic geometry enclosed in a circle: the radius represents the node centrality and the angular displacement between two nodes resembles their topological proximity. The hyperbolic circle aims to become a universal space of representation and analysis of many real networks. Yet, inferring the angular coordinates to map a real network back to its latent geometry remains a challenging inverse problem. Here, we show that intelligent machines for unsupervised recognition and visualization of similarities in big data can also infer the network angular coordinates of the hyperbolic model according to a geometrical organization that we term "angular coalescence." Based on this phenomenon, we propose a class of algorithms that offers fast and accurate "coalescent embedding" in the hyperbolic circle even for large networks. This computational solution to an inverse problem in physics of complex systems favors the application of network latent geometry techniques in disciplines dealing with big network data analysis including biology, medicine, and social science.

2015[ to top ]

Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks. Daminelli, Simone; Thomas, Josephine Maria; Durán, Claudio; Cannistraci, Carlo Vittorio. In New Journal of Physics, 17(11), bl 113037. IOP Publishing, 2015.
- [ Abstract ]
- [ BibTeX ]
- [ EndNote ]
- [ URL ]
Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Unveiling physical principles, building theories and suggesting physical models to predict bipartite links such as product-consumer connections in recommendation systems or drug–target interactions in molecular networks can provide priceless information to improve e-commerce or to accelerate pharmaceutical research. The prediction of nonobserved connections starting from those already present in the topology of a network is known as the link-prediction problem. It represents an important subject both in many-body interaction theory in physics and in new algorithms for applied tools in computer science. The rationale is that the existing connectivity structure of a network can suggest where new connections can appear with higher likelihood in an evolving network, or where nonobserved connections are missing in a partially known network. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.
@article{daminelli2015common, abstract = {Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Unveiling physical principles, building theories and suggesting physical models to predict bipartite links such as product-consumer connections in recommendation systems or drug–target interactions in molecular networks can provide priceless information to improve e-commerce or to accelerate pharmaceutical research. The prediction of nonobserved connections starting from those already present in the topology of a network is known as the link-prediction problem. It represents an important subject both in many-body interaction theory in physics and in new algorithms for applied tools in computer science. The rationale is that the existing connectivity structure of a network can suggest where new connections can appear with higher likelihood in an evolving network, or where nonobserved connections are missing in a partially known network. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.}, author = {Daminelli, Simone and Thomas, Josephine Maria and Durán, Claudio and Cannistraci, Carlo Vittorio}, journal = {New Journal of Physics}, keywords = {not_ies}, number = 11, pages = 113037, publisher = {IOP Publishing}, title = {Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks}, volume = 17, year = 2015 }
%0 Journal Article %1 daminelli2015common %A Daminelli, Simone %A Thomas, Josephine Maria %A Durán, Claudio %A Cannistraci, Carlo Vittorio %D 2015 %I IOP Publishing %J New Journal of Physics %N 11 %P 113037 %R 10.1088/1367-2630/17/11/113037 %T Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks %U https://iopscience.iop.org/article/10.1088/1367-2630/17/11/113037 %V 17 %X Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Unveiling physical principles, building theories and suggesting physical models to predict bipartite links such as product-consumer connections in recommendation systems or drug–target interactions in molecular networks can provide priceless information to improve e-commerce or to accelerate pharmaceutical research. The prediction of nonobserved connections starting from those already present in the topology of a network is known as the link-prediction problem. It represents an important subject both in many-body interaction theory in physics and in new algorithms for applied tools in computer science. The rationale is that the existing connectivity structure of a network can suggest where new connections can appear with higher likelihood in an evolving network, or where nonobserved connections are missing in a partially known network. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.