Distributed-Order Fractional Graph Operating Network

We introduce the Distributed-order fRActional Graph Operating Network (DRAGON), a novel continuous Graph Neural Network (GNN) framework that incorporates distributed-order fractional calculus. Unlike traditional continuous GNNs that utilize integer-order or single fractional-order differential equations, DRAGON uses a learnable probability distribution over a range of real numbers for the derivative orders. By allowing a flexible and learnable superposition of multiple derivative orders, our framework captures complex graph feature updating dynamics beyond the reach of conventional models. We provide a comprehensive interpretation of our framework's capability to capture intricate dynamics through the lens of a non-Markovian graph random walk with node feature updating driven by an anomalous diffusion process over the graph. Furthermore, to highlight the versatility of the DRAGON framework, we conduct empirical evaluations across a range of graph learning tasks. The results consistently demonstrate superior performance when compared to traditional continuous GNN models. The implementation code is available at \url{https://github.com/zknus/NeurIPS-2024-DRAGON}.

Paper

References (82)

Scroll for more · 38 remaining

Similar papers

Peer review

Reviewer smsh5/10 · confidence 3/52024-07-12

Summary

This paper introduces a continuous Graph Neural Network (GNN) framework DRAGON that leverages distributed-order fractional calculus. Unlike traditional continuous GNNs that utilize integer-order or single fractional-order differential equations, DRAGON employs a learnable probability distribution over a range of real numbers for the derivative orders. This approach allows for a flexible superposition of multiple derivative orders, enabling the model to capture complex graph feature updating dynamics. provide a non-Markovian graph random walk interpretation under a specific anomalous diffusion setting. The authors conduct extensive experiments across various graph learning tasks and achieve competitive results.

Strengths

The use of distributed-order fractional calculus in GNNs is novel to me, and expands the capabilities of continuous GNN models. They extend previous dynamical systems to operate under DRAGON framework and generalizes the scenarios to involve distributed-order fractional derivatives The authors conduct experiments on different tasks and plenty o datasets and conduct sensitivity analysis to better evaluate their proposed framework

Weaknesses

1. Can you provide more visualizations and explanations for non-Markovian graph random walk interpretation? 2. lack of code for reviewing and reproducibility 3. The paper does not thoroughly address the scalability of the proposed framework in real-world applications with very large graphs.

Questions

1. How does the computational complexity and memory usage of DRAGON compare to other continuous GNN models in practice, especially for very large graphs? I have seen the time complexity comparison on Cora, but are there more experiments on a larger dataset since cora is small. 2. Can the authors provide their code in order for better reviewing? 3. in table 4, the performance of D-CDE is comparable to F-CDE. the improvements are not obvious. 4. Can the authors provide more explanations for the intrinsic property 'its ability to capture flexible memory effects' mentioned in the paper?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors discuss limitations in the Appendix I, like limitation to continuous GNNs. However, it is better that the authors have a discussion in the main context. Besides, the scalability and computational efficiency of the proposed framework in large-scale applications may need further discussion.

Reviewer mRZs7/10 · confidence 4/52024-07-15

Summary

The paper proposes the a novel framework called DRAGON, which uses a learnable probability distribution over a range of real numbers for the fractional order in graph dynamics, generalizing previous continuous GNN models. The paper provides a non-Markovian graph random walk interpretation for the DRAGON framework, assuming the feature updating dynamics adheres to a diffusion principle. It also proves that the DRAGON framework can approximate any waiting time distribution for graph random walks. The paper integrates DRAGON into several existing continuous GNN models and conducts experiments on various graph benchmarks. The results show that the DRAGON framework outperforms other methods on long-range graph datasets and improves the performance of continuous backbones on homophilic and heterophilic datasets.

Strengths

1. The paper introduces the DRAGON framework, which incorporates distributed-order fractional calculus into continuous GNNs, a novel approach that goes beyond the traditional integer-order or single fractional-order differential equations used in previous GNN models. The use of a learnable measure over a range of real numbers for the fractional order is a unique feature of DRAGON, which allows for a flexible superposition of multiple derivative orders and captures complex graph feature updating dynamics beyond the reach of conventional models. 2. The paper is clearly written and well-structured. The paper provides a non-Markovian graph random walk interpretation for DRAGON, which is a new perspective in understanding the dynamics of graph neural networks. The experimental results are presented in a clear and organized way, with tables and figures that help readers easily understand the performance of the DRAGON framework compared to other methods.

Weaknesses

1. The DRAGON framework involves distributed-order fractional calculus and a learnable measure, which may increase the complexity of the model and make it more difficult to understand and implement. This complexity could potentially limit its adoption in practical applications. 2. The paper mainly focuses on a few datasets for evaluation, and the experiments could be further expanded to include more diverse and challenging datasets.

Questions

see the above weaknesses

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

the author has adequately addressed the limitations in this paper.

Authorsrebuttal2024-08-12

Dear Reviewer mRZs, We sincerely appreciate the time and expertise you have dedicated to reviewing our paper. We deeply value your support. May we kindly ask for your confirmation on whether our rebuttal has adequately addressed your concerns? Your feedback is crucial to us. Thank you once again for your invaluable contributions and for sharing your expertise. With sincere gratitude, The Authors

Reviewer uHnh6/10 · confidence 3/52024-07-17

Summary

This paper presented a new type of continuous GNN that extends and unified many continuous GNN variants. The paper mainly generalize the distributed-order fractional derivatives to continuous GNN dynamics, and it now supports a mixing of fractional derivatives within a range of continuous orders. The author also presents many explanations for the presented generalization of continuous GNNs, with theoretical support and connections to non-markov random walk. Extensive experiments that coverage node-level and graph-level tasks are conducted, showing consistent improvement over existing baselines.

Strengths

1. The presented framework that relies on distributed-order fractional derivatives generalizes many existing methods in the continuous GNN area, providing good theoretical support and insight for future research. 2. While some terms and math are not familiar to me, the author present the framework and main designs greatly and easy to follow. Motivations and theorem conclusions are good to understand. 3. Extensive experiments are conducted, and the performance improvement is notable and consistent.

Weaknesses

1. While the author has conducted extensive experiments covering various domains, the hyperparameter selection strategy is not mentioned. Given the framework introduces many additional hyperparameters, the author should clearly state how they choose all hyperparameters, whether it is solely based on validation dataset. 2. The author mentioned how to solve DRAGON that contains the distributed-order fractional differential equation. It seems that the final computation equation is just the equation 36 mentioned in appendix. As the equation contains approximations, can the author clearly state the approximation error to the true solution? It seems that the equation 36 is a simple iterative based equation, and I'm not sure whether solving the distributed-order differential equation is that simple. 3. The complexity analysis is not very detailed. C and E is kind of vague.

Questions

Except the questions listed above, can the author provide more computational complexity report? Table 8 and 9 only studies cora, I would like to see the report on large datasets. (large graph & large number of graphs)

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The author has clearly stated.

Authorsrebuttal2024-08-12

Thank you for the new feedback! We would first like to clarify potential ambiguities surrounding the term "error" by distinguishing between "performance error" and "numerical error": > Performance error refers to the efficacy of GNNs in tasks such as node classification, where the focus is on the model's ability to correctly predict outcomes. > Numerical error, on the other hand, concerns the accuracy of numerical solutions to fractional differential equations compared to the "true" solution trajectory, which is a key issue in computational mathematics. The two errors are related, but not fully equivalent to each other. The approximation error in (S2) and (S3) refers specifically to the "numerical error." For further clarity, we then conducted ablation studies on the Cora dataset to observe how errors change with respect to the step size $h$. > (1). In the first ablation study, we fixed all other parameters and varied the step size $h$ used in each experiment. We trained the model using different step sizes $h$ during the training phase and tested it with the corresponding step sizes during the test phase. The results are presented in **Table R5**. According to (S2) and (S3), the numerical approximation error should be large when $h$ is large. However, the results from Table R5 indicate that while classification performance deteriorates with larger step size $h$, it does not degrade to an unreasonable level and still maintains adequate classification performance. This occurs because both the training and testing phases follow the same discretization procedure, and although both are far from the true FDE solution, the loss function is designed to minimize the final classification error, resulting in satisfactory performance. > (2). In the second ablation study, we maintained fixed parameters as in the first study but changed our approach by training the model exclusively with a small step size $h=0.1$. During the testing phase, we varied the step size $h$. The results are presented in **Table R6**. According to (S2) and (S3), the numerical approximation error should be minimal when $h$ is small, and the solution with $h=0.1$ can be presumed close to the "true" solution trajectory of the FDE. We noted that when $h < 1$ and remains relatively small, the model still achieves good classification performance. This occurs because the "numerical error" is still minimal, keeping the numerical solution close to the "true" solution trajectory. However, as $h$ increases beyond this range, the "numerical error" grows significantly, diverging from both the "true" solution trajectory and the approximate solution with $h=0.1$. Consequently, classification performance deteriorates substantially. **Table R5: Step size and classification accuracy(\%) (training and test)** | Step size | 5 | 2 | 1 | 0.5 | 0.2 | 0.1 | |-------------|-------|-------|-------|-------|-------|-------| | Solver Eq.(28) | 80.24 | 82.98 | 83.11 | 83.18 | 83.15 | 83.11 | | Solver Eq.(36) | 80.03 | 82.33 | 82.57 | 82.91 | 83.11 | 83.19 | **Table R6: Step size and classification accuracy(\%) (test phase)** | Step size | 5 | 2 | 1 | 0.5 | 0.2 | 0.1 | |------------|-------|-------|-------|-------|-------|-------| | Solver Eq.(28) | 35.23 | 65.48 | 74.42 | 80.91 | 81.02 | 83.11 | | Solver Eq.(36) | 39.80 | 61.62 | 73.91 | 76.14 | 80.41 | 83.19 |

Reviewer uHnh2024-08-10

Thank you for these detailed response and additional measurement. Your algorithm seems to be well designed: with both theoretical support and limited computational overhead. Based on (s2) and (s3), can you give some insight to the measurement of the real error in experiments? Like how the error changes and affect the performance with respect to h in real experiments.

Authorsrebuttal2024-08-13

Dear Reviewer uHnh, Thank you for your insightful questions, which have contributed to the enhancement of our paper. Could you please let us know if our responses have addressed your concerns adequately? We appreciate your guidance and look forward to your feedback. With sincere gratitude, The Authors

Authorsrebuttal2024-08-14

Dear Reviewer uHnh, Thank you for your insightful questions, which have contributed to improving our manuscript. As the rebuttal period is drawing to a close, we kindly request your feedback on whether our responses have sufficiently addressed your concerns. We value your guidance and look forward to your further comments. Sincerely, The Authors

Reviewer smsh2024-08-11

Thank you for your code, responses and additional experiments. I have raised the contribution score from 2 to 3.

Authorsrebuttal2024-08-11

Thank you for increasing the contribution score. We appreciate this positive change! However, for clarification, we would like to note that in typical NeurIPS review processes, reviewers often adjust the overall rating rather than the contribution score alone.

Authorsrebuttal2024-08-14

Dear Reviewer smsh, May we kindly ask if you would consider revising the overall rating based on our responses? Sincerely, The Authors

Program Chairsdecision2024-09-25

Decision

Accept (spotlight)

© 2026 NYSGPT2525 LLC