Deep Graph Predictions using Dirac-Bianconi Graph Neural Networks

The alternating procedure of DB and linear layers could be more clearly explained. What does a linear layer mean in this context and why are they needed

Linear layer simply refers to a learnable linear weight matrix of an appropriate dimension. We use them here for skip connections, that is, after running the DB dynamics for some time we allow the DBGNN to mix the features into the hidden dimensions again. This is expected to improve the ability of the system to go deep. We will expand on this feature further in the manuscript.

Does this address the reviewers concerns, or were they also asking for clarification of other aspects of the DBGNN?

Neither of the datasets considered inlcude non-trivial edge features. Perhaps you could have flux along an edge in a powergrid or something?

We experimented with using the power flow on the edges as additional input features, but it did not improve the performance. See Reply to all Reviewers - Further Datasets.

Not clear how the baseline methods where chosen? Are these also methods meant to address oversmoothing and long range dependencies? Are they at or near s-o-t-a?

We have chosen the best performing models on the datasets as baselines, so we consider them state of the art. ARMANet and TAGNet, which perform best for the power grid task, share some features with architectures designed specifically to avoid oversmoothing, and are iterated quite deeply to achieve their performance. The DBGNN layer that beats them here is comparatively simpler, at least from a dynamics point of view.

x' and e'{i,j} are not defined in equations 6 and 7. I am assuming they mean the output of delta{DB}(x, e), but this should be made more clear

Thank you for pointing this out, you are right, we will clarify this point.

Is there any connection by the DB equation and the wave equation?

This is an excellent question. The Dirac equation is a wave equation, however, it includes an overall factor $i$ in front of the right hand side. As we omit this factor, the equation we use is not directly a wave equation. Instead, we have exponentially growing and shrinking modes. We will clarify this point in the manuscript.

The leap from 8 to 9 should be made more clear. This appears to solving \partial_t - \partial_{DB} \pm \beta =0, or something but this should be made explicit.

Equations 8 and 9 together are the Bianconi's topological Dirac equation written out explicitly in coordinates. We are not solving anything, edges and nodes evolve at the same time. We will clarify this point.

Table 2 is interesting, that one DBGNN layer = 3 GCN layers, but it would be more convincing if you also showed results with DBGNN outpeforming GCN in addition to other baselines

The 3 layer GCN is the state of the art for this task, see Reply to all Reviewers - Baselines for binding affinity. We are investigating further Datasets to strengthen the results of the paper, see Reply to all Reviewers - Further Datasets.

Is there any way to use the DB operator to define Riesz transforms (in the Euclidean setting)? 

This is an interesting question, we do not know. Generally speaking, Dirac operators tend to require internal spaces and do not directly operate on real valued functions. We expect that any connection would be subtle.

Where does the network include non-linearitiees? Why do these not induce loss of energy?

We include a ReLu after every step of the dynamics. It is unclear to us why a non-linearity should be expected to induce a loss of Dirichlet energy. We will update the section on Dirichlet energy to better represent typical conditions in the layer, in which case we do see a gradual decline, see Reply to all Reviewers - Dirichlet Energy.

What is the computational complexity of DBGNN vs other methods?

The time complexity of the forward pass is the same as that of Message Passing Neural Networks. The main difference to these, is the fact that we have the edges as full updating states of the layer iteration. This does not increase the computational complexity. We will include a small note in the manuscript to this effect.

Paper could be improved via more thorough experimentation and also analysis of / references too the theoretical properties of the DB operator.

i) Limited ablation studies. It can be made further clear for how much performance gain comes from Dirac structure vs other enhancements.

It is unclear to us what the reviewer views as important other enhancements. DBGNN is a relatively simple layer. It is the iterated application of equations (11) and (12), which are the direct analogies of the Dirac Bianconi equation, followed by a skip connection. We have added a direct comparison to a simple MPNN to clarify this, and we now show that the equivalent MPNN does not have comparable dynamics or long range feature propagation (Reply to all Reviewers - Evidence for long range Capabilities).

A more detailed study on how performance varies with various hyperparameters would, of course, be highly interesting. We also believe the layer to be highly compatible with the vast array of architectural enhancements that have been explored for MPNNs and GCNs. We think such broad questions are beyond the scope of this initial paper, though, and we decided to focus our experimental resources elsewhere.

ii) the paper does not exploit edge features on binding affinity task. It may be unsure if Dirac structure helps here.

It is important to note that in the absence of edge input features, we still have a non-trivial hidden edge dynamics. Thus, the way the nodal information propagates is shaped by the Dirac structure in this case, too. We will clarify this point in the paper.

Thus we consider the competitive performance on this task a strength of the layer. It shows that the underlying dynamics is interesting. We assume that useful edge features can only help to get higher performances. We are also exploring further datasets, see Reply to all Reviewers.

iii) although one of the experimental task is related to long range dependency, it is not sure for the second task. A robust study on some long range dataset benchmark would be required to verify holistically the claims of the model on long range tasks as is mentioned in multiple instances in the paper. The paper would be strengthened by a more in-depth analysis of what long-range effects the model is capturing in this domain.

We agree that a much broader study would be needed. We have extended the analysis beyond the Dirichlet energy by including example trajectories of a randomly initialized layer. See Reply to all Reviewers - Evidence for long-range capabilities.

We also would like to point out that the power grid task is known to require long-range capabilities (Ringsquandl et al. (doi: 10.1145/3459637.3482464)), and that the state-of-the-art models (ARMANet and TAGNet) are quite deep. Together with the evidence from randomly initialized layers, we consider the conclusion reasonable that DBGNNs are good for long-range dependencies.

At the same time, we agree that a study of DBGNN on a long-range dataset benchmark would strengthen the paper considerably, and we are working towards that goal. See also Reply to all Reviewers - Further Datasets.

iv) For binding affinity task, did you try using edge features? Does the Dirac structure help in that case?

See Reply to all reviewers (Baselines for binding affinity).

[The paper] does not elaborate on the theoretical foundation for its fusion with GNNs.

Many GCN methods are equivalent to dynamical systems on networks. This has been elaborated in the literature we cite in the introduction. Given this close equivalence it is unclear to us what theoretical foundation for the fusion the Reviewer had in mind. We are happy to elaborate if the question is clarified.

The theoretical part of this paper lacks an analysis of the time complexity of the Dirac-Bianconi Equation.

The time complexity of the forward pass is the same as that of Message Passing Neural Networks. The main difference to these is the fact that we have the edges as full updating states of the layer iteration. This does not increase the computational complexity. We have included a small note in the manuscript to this effect.

The paper applies the DBGNN model to two vastly different tasks, power grid analysis and molecular property prediction, without tailoring the model for the specifics of each task. This lack of task-specific optimization could limit the model's performance and applicability.

We agree that the performance of DBGNN could be further improved, but it already shows competitive and superior performance in comparison to the baselines. We consider it as a strength that the layer as presented is relatively simple but already exhibits interesting performance. Adding optimizations should therefore be possible, but we consider it beyond the scope of this paper, which focuses on the properties and performance of the core layer.

The experimental setup in section 4.1.2 appears to have some shortcomings in terms of training parameters and code implementation.

Could more detailed experimental settings and parameter choices be provided to ensure experiment reproducibility while also considering the robustness of the model?

Details of the hyperparameters and used software are provided in the appendix. Furthermore, we will provide all code to make the results fully reproducible. We would be glad to add more details if Reviewer VKy2 elaborates on the type of missing information.

We also tried different hyperparameters and show some examplary results of different configurations below:

If I understand correctly, the Dirac-Bianci operator is called the boundary and co-boundary operators in the simplicial complex theory on graphs. Existing studies propose GNNs that use or extend them (e.g., [1--4]. Also, [5] does not use (co-)boundary operators but extends GNNs on simplicial complexes.) Therefore, it is debatable whether the proposed method has (theoretical and experimental) novelty and significance in terms of using the Dirac-Bianci operator.

We thank the reviewer for highlighting the connection to this part of the literature. The comment was extremely helpful. We agree that the boundary operator in itself is not new, and we cite Loyd et al. as an early work on using the boundary operator in the context of topological data analysis on simplicial complexes.

The key point of Bianconi's Dirac equation is the combination of the boundary operator, and having the edge degree of freedoms as full participants in the dynamics with an appropriate mass term. This causes a spectral gap, and interesting propagation on the network. The work $1$ on sheaf diffusion for example, while considering a very similar topological set up as we do, does not treat the edge space as possessing its own dynamics, and thus cannot induce analogous dynamics.

The topological set up is of the general form considered in $2$ , which we will note in the manuscript. However, in $2$ the focus is on simplicial complexes, and in their applications to graphs, the set up we use is not considered (we have boundary and coboundary at the same time, but no up/down/Hodge Laplacians. The set ups of $2$ did not feature the combination of a boundary/coboundary operator). In a further literature review based on the input of the Referee we identified ( arxiv.org/abs/2012.06010 ) as one example where a similar set up appears, and we will cite this as a predecessor.

Overall we believe our approach is closer to, e.g. the use of Kuramoto oscillators and other physically inspired dynamical equations that are not diffusive, rather than approaches inspired from algebraic topology. The close relationship to these works is of course highly relevant and of great theoretical interest. We will rework the theory section to make this clear.

This paper claimed that one of the advantages of the proposed method is that it solves over-smoothing. However, since there exist models that tackle over-smoothing, such as GCNII [6] and DRew [7], I have a question about whether the proposed method is superior to them.

The motivation to explore the use of the DB equation was twofold, we wanted to be able to deal with edge features and to use a non-diffusive dynamical equation that would enable the deep predictions needed for power grid analysis. In our view, it is highly interesting that the DB equation possesses these qualities without having to be specifically engineered for it.

We agree that it would be interesting to understand in more detail how it compares to other approaches that were designed to handle oversmoothing. In the power grid context, deep GNNs such as ARMANets and TAGNets are known to have the best performance. These share some characteristics with GCNII. DBGNN is a relatively simple layer, that does not make use of these strategies, yet has competitive performance in this dataset at least.

It would be highly interesting to see whether these strategies, as well as those used in DRew, can be used to further improve the performance of DBGNN. We will add this as a research question to the outlook, but consider it out of scope for this paper.

this paper argues that the proposed method with ten steps is comparable with 3-layer GCN [...] to be comparable in performance to a shallow GNN.

One of the advantages of the proposed method is that both node and edge features can be used equally. However, in the numerical experiments on real data, only node features are available to GNNs (in the binding affinity prediction task, edge features are used for graph construction but not as features). Therefore, it is unclear whether the proposed method can take advantage of this feature in real data.

We have expanded on the baseline comparison, and agree that more diverse datasets would be desirable, see the reply to all reviewers.

How were the hyperparameters chosen? In particular, the numerical experiments use networks with 48 and 10 steps in total, respectively. However, it is yet to be known whether these hyperparameters are optimal. That is, a model with fewer steps might be sufficient. I suggest conducting ablation studies to see the sensitivity of performances to the number of steps.

We conducted unstructured hyperparameter studies testing different number of steps. We believe that there is more potential when conducting more hyperparameter studies, but even with our small studies, we could already outperform current baselines.

In Figure 5(a), the Dirichlet energy of untrained DBGNN is almost constant regardless of the number of steps. Is this expected from the theory?

However, the datasets used in the evaluation do not consider any useful edge information. 

We agree. See also Reply to All Reviewers - Further Datasets. We will clarify that even in the absence of edge features, the DB equations lead to a very different behavior than standard MPNNs, see Reply to All Reviewers - Evidence for long-range capabilities of DBGNN.

 it is shown that only 1 layer of DBGNN suffices

This is probably a property of the dataset. If 1 layer with 12 steps already considers sufficiently large subgraphs, more layer will not be necessary.

Why do we need at least 13 layer GNNs for power grids? Is it true for all type of GNNs? Some powerful GNNs might need fewer than 13 layers.

Ringsquandl et al. (doi: 10.1145/3459637.3482464) state that the unique structure of power grids leads to the need at least 13 layers for GNNs. Even that might not be sufficient for all tasks: the behavior of power grids shows profound non-locality. A failure in one part of the grid can cause a subsequent failure at a distance comparable to the system size (see e.g. https://www.science.org/doi/10.1126/science.aan3184). For example, large system splits and blackouts in Southern Europe have been caused by line failures in Northern Germany. The specific task we investigate is not known to be quite so non-local, but features the same physics.

Please clarify using the notation e_ij = - e_ji .

See reply to all Reviewers - Edge notation.

What is the performance of the proposed method on node classification tasks on citation networks such as Cora, Pubmed, etc?

We do not expect that DBGNN has an advantage over existing methods on citation networks. Large topological patterns are not known to be relevant in this case, while close neighborhoods play a more significant role. See also Reply to All Reviewers - Further Datasets.

The Dirichlet energy is constant over 500 steps in Figure 5? Why? Is it just for this experiment? It does not seem to change a t all..

See Reply to all reviewers - Constant Dirichlet energy.

I am willing to raise my score significantly if the story of the paper is in line with the findings and more insights with toy examples are presented.

We are more than happy to provide further support for the story line of the paper. We will add a visualization of the long range response of the layer to a localized signal. See Reply to all Reviewers. If the reviewer has further toy examples that they would find informative, we would be more than happy to implement them.

As the revision of the manuscript will still take some days we have already included the new visualization in a supplementary note.

Edge notation

Reviewers YvSy and 3z7c raised questions regarding the edge notation:

The setup assumes a symmetry on the edge features e_{j,i} = e_{i,j}

Please clarify using the notation e_ij = - e_ji .

The Dirac Bianconi equation assumes an undirected graph, and a fiducial orientation on the edges. The signs in the incidence matrix $B$ depend on this choice. The edge values for an edge are associated with the fiducial orientation $e\_{ij}$. The values associated to the opposite of the fiducial orientation are $-e\_{ji}$. These conventions result in the usual definition of the graph Laplacian of an undirected graph.

In the present context it is clearly more appropriate to treat $e\_{ij}$ and $e\_{ji}$ separately, as is typically done in the context of MPNNs. We will adjust the theoretical presentation accordingly to remove the fiducial orientation.