Flow Graph Neural Networks

• The writing of this paper could be improved. For instance, the introduction is overly long (about 2 pages) and lacks clarity, which makes it difficult for readers to understand the key motivations of the work.

• The theoritical analysis of FlowGNN is limited. This paper can not provide a comprehensive exploration of the expressiveness and computational complexity of FlowGNN compared to standard GNNs. Although the practical effectiveness of FlowGNN are demonstrated through experiments, a deeper theoretical understanding of how the proposed flow attention mechanism help FlowGNN handle resource conservation and distinguish non-isomorphic flow graphs is needed.

• The novelty of FlowGNN is limited. This paper primarily focuses on modifying the attention mechanism by normalizing across outgoing neighbors instead of incoming ones. However, this adjustment does not introduce new architectures or theoretical innovations beyond those found in existing methods. Additionally, the extension of FlowGNN to DAGs represents only an incremental advancement.

• The experimental results are not convincing, and the baseline methods are not strong enough. Although the authors compare FlowGNN method with some widely used baseline methods like GCN, GAT, GIN, GT and PACE, these are neither the latest nor the most competitive, which undermines the significance of the reported performance.

It appears that the paper mentions several times the concept of “conservation of flow”, e.g., Korchhoff’s law, but my understanding is that there is no guarantee or mention that the flow is conserved at all: nodes will receive a certain amount of message information (greater or smaller of a “full single message”) and will always output a “single” message to its outgoing edges, that is without duplicating information. There might be something I am missing, but if this is really the case then the impact of the paper would be greatly reduced. As a matter of fact, if flow is not conserved then it is not surprising at all that the GIN method has similar performances to FlowGAT on the PowerGraph benchmark, as both the sum aggregator and the flow attention weights are susceptible to degree changes (while GCN for instance would be susceptible to distributional changes in the neighborhood).

Similarly, the claims that the authors need to distinguish “all” non-isomoprhic DAGs (lines 265-266) might be misleading. For instance, let us focus on flow attention weights and not on DAFlowGNN. What happens if you take the circuit in Fig 1.b left and you compare it with “in” -> branch into R1 x2 -> merge into R2 --> out? If you do not take into account normalization for incoming edges, you might end up with the same result also with FlowGAT. In any case, despite the claim made in said lines, the authors only (partially) showed that DAFlowGNN could distinguish a particular pair of DAGs, not that it is universal with respect to all DAGs. To summarize, some claims should be clarified/adapted to reflect the real contributions of the paper and avoid general statements.

Despite its novelty, the paper fails to acknowledge and position itself compared to a whole line of less recent works on recursive and contextual architectures that are relevant because they often incorporate the same architectural bias than recent works. Before GNNs were applied to DAGs -- in reverse order compared to historical developments -- (contextual) recursive neural networks for DAGs [1,2] and their expressive power were completely characterized [3], and later the causality assumptions were relaxed to allow cycles in the computation [4, Scarselli et al. 2009].

Finally, there are some concerns on empirical results. The authors have correctly split the dataset into training/validation/test. The validation set should be used to select the best hyper-parameters for a specific model on a specific dataset (a process called “model selection”). Then, once the best hyper-parameter configuration has been found on the validation set, the model should be (possibly after retraining) evaluated on the unseen test set. Given the specific hold-out strategy adopted in the paper, it makes no sense to show results for all models with a certain number of layers, e.g., DAGNN-2/4 or DAFlowGNN-1/2. What the authors should show is the estimate of the risk using the best configuration attained by each model and dataset. Arguments like the ones made at lines 415-417 cannot stand against the correct process for risk estimation. In this regard, the authors are recommended to show results attained by each model using only the best configuration found on the validation set. This would allow a fair comparison of different classes of models rather than a comparison of simple point estimates that will likely be misleading. The authors can refer to slides 23-33 of Samy Bengio’s lecture: https://bengio.abracadoudou.com/lectures/theory.pdf.

[1] Sperduti, Alessandro, and Antonina Starita. "Supervised neural networks for the classification of structures." IEEE transactions on neural networks 8.3 (1997): 714-735.

[2] Frasconi, Paolo, Marco Gori, and Alessandro Sperduti. "A general framework for adaptive processing of data structures." IEEE transactions on Neural Networks 9.5 (1998): 768-786.

[3] Hammer, Barbara, Alessio Micheli, and Alessandro Sperduti. "Universal approximation capability of cascade correlation for structures." Neural Computation 17.5 (2005): 1109-1159.

[4] Micheli, Alessio. "Neural network for graphs: A contextual constructive approach." IEEE Transactions on Neural Networks 20.3 (2009): 498-511.

1. The novelty of this paper seems limited, as author just normalize the attention scores across outgoing neighbors instead of across incoming neighbors. The novelty of this paper needs to illustrate better. Specifically, for non-expert readers, it is unclear how significant impact such change leads to.

2. The relationship between FlowGNN and DAFlowGNN is unclear. While DAFlowGNN is a DAG version of FlowGNN, it is unclear what the differences of two GNNs in terms of applicability, e.g. Are they both applicable to flow graphs? For their architectures, it is unclear what are the main differences.

3. In Section 3.3, it is better to illustrate in terms of rigor theorems that DAFlowGNN is more expressive than any DAGNN, as the current version is not easy to follow.

4. For the experiment section, electronic circuits and power grids both belong to electrical domain, which makes it doubtful that the proposed GNNs may have narrow applications limited by resource conservations. Can authors show more applications and compare results? Another concern is the computational expenses. As author admit in the paper, DAFlowGNN is twice as computationally expensive as DAGNN, but the efficiency experiments are missing, and it is necessary to discuss what techniques can be used to reduce computational time.

Please find further details on my listed weaknesses in my questions below.

• The empirical evidence in favour of your model is not very strong, in the sense that you are sometimes outperformed by the Graph Isomorphism Network (published in 2019) and some improvements are marginal.
• The proposed model is not described in sufficient detail, i.e., not all aspects of your proposed model are well-motivated, the notation is not always clearly defined and certain models such as the FlowGT are not discussed at all.
• The theoretical component of this work is not formal and rather small. This would be fine if there was overwhelming empirical evidence in favour of the proposed method, which does not seem to be the case either. So, I want to suggest to the authors to formalise and to further extend their theoretical study.

• Performance results in some cases for FlowGNNs are mixed and the benefits of the approach are not directly realized in the experiments (Table 3). In other cases, a simple GNN like GIN can be more performant (Table 1). So there is room for improvement in the consistency of the gains reported.

• Typically the notation (u, v) for a directed edge is assumed to denote a connection from node u to node v, not the other way around as in here.