DeepNT: Path-Centric Graph Neural Networks for Network Tomography

We really appreciate your thorough and constructive feedback. We are eager to respond to your questions and comments:

---

Response to W1:

How to collect the path sets $P_{uv}$ when the adjacent matrix is unknown or incomplete? How do we know which path has the optimal path performance?

• In line 145, $P_{uv}$ represents the set of all possible paths from $u$ to $v$, so it is constructed given the known topology. It is used to define the optimal path performance from $u$ to $v$, e.g., $y_{uv} = \{y_{uv}^n \mid y_{uv}^n \leq y_{uv}^k, ~\forall p_{uv}^k \neq p_{uv}^n \in P_{uv}\}$ for additive metrics. $P_{uv}$ does not need to be constructed in DeepNT.

• $y_{uv}$ represents the observed optimal path performance from $u$ to $v$. The specific optimal path information between $<u,v>$ is unknown due to the unknown or incomplete topology. DeepNT aims to predict the optimal path performance. Thus, to predict $\hat y_{uv}$, DeepNT collects $P_{uv}^L$ (line 200) using the observed network topology ($A$) and path performance collection ($S$) then aggregate their information.

How about the probing overhead? How to control the probes to traverse the specific routing paths is also a tough question since many networks do not support source routing?

Since DeepNT relies solely on observations of path performance, such as delay in the Internet, to serve as the training data, no probing is required during or prior to training.

---

Response to W2: As mentioned in W1, DeepNT aims to predict the "optimal path performance" between nodes. For additive metrics such as delay, "optimal" implies that smaller values are better. If the ground truth optimal path performance $y_{uz}$ and $y_{zv}$ is observed for $<u,z>, <z,v> \in S$, then $\hat y_{uv} \leq y_{uz} + y_{zv}$. If this triangle inequality is violated, the predicted path performance for $<u,v>$ is no longer "optimal," as it would be worse than the performance of the path $u \rightarrow z \rightarrow v$. The triangle inequality ensures that if the complete optimal path for $<u,v>$ is not observed, the predicted path performance between them $\hat y_{uv}$ will not be worse than the performance of any other observed path connecting $u$ and $v$.

• For static load balancing policies, the triangle inequality works for most of path performan metrics.

• For dynamic load balancing policies or social networks, the triangle inequality holds by continuously updating the observation set $S$ and retraining DeepNT when necessary.

---

Response to W3: We agree that low-rank approximation techniques, such as matrix completion and matrix factorization, can be applied to network tomography in certain scenarios. Matrix factorization, in particular, has been explored in network tomography due to the inherent low-rank properties of network performance metrics. While matrix factorization explicitly models this low-rank structure, making it well-suited for reconstructing missing or incomplete data—particularly in the context of sparse matrices—it is no longer a commonly used technique in network tomography. This is primarily because low-rank approximation techniques require a substantial amount of observed data to achieve robust performance.

Empirically, we compared DeepNT against two widely used matrix factorization techniques—Non-negative Matrix Factorization (NMF) [1] and Neural Matrix Factorization (NeuMF) [2]—for predicting additive metrics in terms of MAPE (%):

• DeepNT consistently and significantly outperforms matrix factorization techniques. Particularly, when $\frac{\|S\|}{\|T\|}$ = 10% (i.e., only 10% of node pairs' path performance is observed), the predictions by both NMF and NeuMF become unreliable.

• The performance of matrix factorization methods drop significantly as fewer path performances are available. The low-rank modeling relies heavily on observing a substantial amount of data (e.g., path performance between many node pairs) to ensure reliable predictions.

---

Response to W4: We conducted experiments with higher missing rates in the adjacency matrix. The main results are available at: https://anonymous.4open.science/r/DeepNT2-1D25/topology.png. DeepNT demonstrates promising performance even when the topology missing rate approaches 0.7.

---

Thank you for your valuable effort in evaluating our work! We are happy to provide further clarification and address any additional concerns that may influence your assessment of its suitability for acceptance.

---

References

[1] Lee, Daniel, and H. Sebastian Seung. "Algorithms for non-negative matrix factorization." Advances in neural information processing systems 13 (2000).

[2] He, Xiangnan, et al. "Neural collaborative filtering." Proceedings of the 26th international conference on world wide web. 2017.

Thank you for giving us the opportunity to provide further clarifications!

---

The effectiveness of the method described in this paper relies heavily on the training data, which may not necessarily align with the triangular optimality assumption mentioned in the main text.

Response: Actually, as long as one end-to-end path performance metric has a definition of "optimality," our method can be applied effectively, regardless of the type of the metrics. There may be some misunderstanding about the task we are addressing. To clarify, a specific example is provided in the response to your second question below.

---

Continuously updating data implies the need to recollect training data, yet, as mentioned in Response to W1, this paper does not provide a relevant solution. Moreover, in the context of social networks, how exactly does the triangular inequality come into play?

Response:

• On Continuously Updating Data and Recollecting Training Data: To clarify, the main contribution of our work is to enhance network tomography performance, reduce training costs, and adapt to any path performance metrics. It is important to highlight that the challenge of data collection is not unique to our method; it is a common issue faced by all network tomography approaches and does not diminish the significance of our contribution to the community.

• On the Role of Triangular Inequality in Social Networks: When there is a need to predict optimal end-to-end performance between users in social networks, DeepNT, leveraging the triangle inequality, is well-suited for this purpose. Below, we provide a simple example to illustrate its applicability (assume there are 3 users $A$, $B$, and $C$):

  • Suppose $A$ and $C$ have an optimal trust score of $T(A,C) = 0.8$, but the link between $<A,C>$ is not observed (i.e., incomplete topology). However, there are observed links between $<A, B>$ and $<B, C>$. The trust score between the two unlinked nodes is inferred through the nodes linking them, using a multiplicative form: $T(A,C) = T(A,B) \times T(B,C) = 0.7 \times 0.5 = 0.35$.
  • When predicting the optimal trust score for $<A, C>$, if the path $A \rightarrow B \rightarrow C$ is the observed optimal path, the predicted trust score will be constrained by the triangle inequality, ensuring it is no worse than $0.35$.
  • It might be assumed that $T(A,C) < 0.35$ such as 0.2, which would appear to violate the constraint. However, since we are predicting the "optimal" end-to-end performance, the triangle inequality still holds, as the optimal performance between $<A,C>$ now is 0.35 but not 0.2.

---

Which dataset does Response to W3 use? Are the experimental settings fair? To my knowledge, many methods can handle over 90% missing data.

Response:

• Dataset: The experiments were conducted on the synthetic dataset, including Erdős-Rényi, small-world, and power-law graphs.
• Performance: The comparison was performed under the condition that 10% of node pairs had observed end-to-end performances, ensuring a fair comparison.
  • Both prior studies, such as [1], and our experimental results demonstrate that low-rank approximation techniques, such as Matrix Factorization, fail to ensure satisfactory performance in network tomography when the observed data is sparse.
  • For instance, as highlighted in [1], the correlation of link metric predictions decreases as fewer end-to-end path performance is utilized, indicating reduced estimation accuracy due to the limited availability of data. It demonstrates good performance only when more than 70% of end-to-end performance data is observed.
  • Could you provide specific references where Matrix Factorization has been reported strong performance under conditions of sparse observations? We would be happy to reproduce their results and compare them with our DeepNT as soon as possible.

---

Thank you for your valuable feedback! We are happy to provide further clarification and address any additional concerns that may influence your assessment of its suitability for acceptance.

---

References:

[1] Raza, Muhammad H., et al. "Network tomography by non negative matrix factorization (NNMF)." Proceedings of the 2010 International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS'10). IEEE, 2010.

We sincerely thank the Reviewer XbAT for acknowledging our contributions to network tomography and providing insightful observations.

---

Response to W1: To clarify, DeepNT employs a path-centric aggregation layer that considers multiple promising paths rather than relying on a single pooling operation. This design effectively captures diverse contextual information and mitigates the loss of important details. Towards your specific concerns:

What if paths are long? As described in line 200, DeepNT samples paths with lengths not exceeding $L$. This ensures that the aggregation process retains as many local features as possible while avoiding the over-smoothing problem encountered in long path aggregation.

What if there is significant variation in node features? In network tomography, node features are typically derived from the topological structure, using methods such as one-hot encoding or deep walks. These approaches standardize the embedding spaces across different networks, minimizing the issue of varying node feature distributions. DeepNT has demonstrated state-of-the-art performance across networks with diverse structures, such as Internet and social networks.

---

Response to W2: To clarify, the primary goal of network tomography is to infer and predict network dynamics—such as traffic patterns and congestion—using end-to-end measurements. This inherently involves collecting and analyzing a significant amount of data. Below, we address your specific concerns:

How to deal with the dynamic addition or removal of nodes and edges?

• Nodes: The network tomography problem typically assumes that the set of nodes is fixed and known beforehand. This assumption is a standard limitation across traditional and modern approaches.
• Edges: For edge dynamics, DeepNT is capable of learning the network topology dynamically, given the set of nodes. This enables the model to infer missing edges effectively without impacting its performance.
• Our Improvement: Traditional network tomography methods assume both the set of nodes and the network topology are fully known. DeepNT relaxes this requirement by only needing knowledge of all nodes, which represents a significant step forward.

Inadequate ability to handle real-time or near-real-time network dynamics:

• Real-time scenarios: Gathering sufficient end-to-end measurements in real-time is inherently challenging. It often requires probing across multiple paths or waiting for traffic patterns to stabilize, which limits the applicability of network tomography to fully real-time scenarios.
• Near-real-time scenarios: DeepNT demonstrates strong potential for near-real-time analysis by significantly reducing the training complexity from $O(|V|^3)$, as seen in traditional network tomography methods, to $O(|E|)$. This not only enhances DeepNT's scalability but also enables it to quickly update training data and retrain the model, making near-real-time class prediction feasible—a task that is impractical for traditional methods due to their high computational cost.

---

Response to W3: DeepNT does not prioritize sequentiality, as its primary focus is on capturing and utilizing potential nodes that contribute to forming the optimal path between two nodes from multiple promising paths, rather than strictly adhering to the order of nodes within each path. This design aligns with the core objective of network tomography: to infer performance metrics by leveraging patterns in the graph structure rather than the specific traversal order of nodes in individual paths.

---

Response to W4: We agree that generalization is a critical aspect of network tomography. To clarify, DeepNT is specifically designed to address the challenges of learning from incomplete graph information, as partial observability is a defining characteristic of real-world network tomography scenarios.

To ensure the generalization of DeepNT, we have incorporated the following key designs:

• Path-Centric Aggregation: DeepNT aggregates information from multiple promising paths. By sampling multiple loopless paths of limited length, DeepNT incorporates both local and global structural information, enhancing its generalization .
• Learning Topology Dynamically: DeepNT dynamically infers the missing topology during training, allowing the model to effectively reconstruct the network structure and improve generalization.
• Triangle Inequality Constraint: The triangle inequality constraint introduces a critical inductive bias that helps the model make logical and consistent predictions. By enforcing that path performance predictions respect inherent relationships between nodes and paths, this constraint ensures more reliable generalization.

---

Thank you for your valuable effort in evaluating our work! We are happy to provide further clarification and address any additional concerns that may influence your assessment of its suitability for a clear acceptance.

Thank you for your thoughtful and constructive feedback. We are committed to incorporating the suggested changes by all reviewers in our revisions to further enhance the manuscript.

As suggested by other reviewers, We have extended our ablation study to evaluate alternative aggregation layers and graph structure learning methods and provided detailed analysis of the expressive power of our model. We would appreciate it if you could let us know before closing the discussion whether there are still concerns that may influence your assessment of its suitability for a clear acceptance!

We really appreciate your thorough and constructive feedback. We have taken your suggestions to heart and made changes to the best of our abilities.

---

Response to W1: To clarify, we tested various encoding methods for node embedding initialization, such as one-hot encoding, Node2Vec, and random walks since graphs are often featureless in typical network tomography scenarios. They are only used for node embedding initialization. Our proposed framework, DeepNT, already integrates a path-centric graph neural network to further learn node embeddings dynamically during training. This allows us to leverage both the initialization and the flexibility of GNN architectures. Additionally, the framework is adaptable to different types of GNN backbones, including attention-based (e.g., GAT, GraphTransformer) and spectral-based (e.g., GCN) approaches.

We acknowledge that showing the performance of using different GNN models can help demonstrate the robustness of DeepNT to GNNs. The MSE results for additive metrics when $\frac{|S|}{|T|}$=30% using different GNN as the backbone, including GAT, GraphTransformer, and GCN are summarized in the following Table.

---

Response to W2: Thank you for your valuable comment! Below, we provide a detailed complexity analysis of DeepNT, emphasizing its scalability in sparse large-scale graph scenarios, which are typical in network tomography applications.

Due to the sparsity of real-world networks, we have $|E| << |V|^2$, which makes sparse matrix multiplications during GNN operations have a complexity of $O(|E| \cdot d)$, not $O(|V|^2 \cdot d)$, where $d$ is the embedding dimension. For the triangle inequality constraint, instead of processing all possible triplets $O(|V|^3$, we sample a subset of triplets proportional to $|E|$. This reduces the complexity to $O(t\cdot k\cdot |E|)$, where $k$ is the sampling ratio and $t$ is the number of training iterations.

There are no $|V|^2$ or $|V|^3$ terms in the complexity, providing a theoretical guarantee of DeepNT’s scalability on large-scale sparse graphs.

---

Response to Q1:

Training Complexity: Given that $|E| << |V|^2$ and the complexity of key components above, the GNN training complexity and the adjacency matrix update complexity are both dominated by $O(|E|)$.

Convergence Analysis: The proof of convergence for our optimization algorithm is available at: https://anonymous.4open.science/r/DeepNT2-1D25/Convergence.pdf.

Computational Efficiency: Classical network tomography approaches rely on solving linear systems has the complexities of $O(|V|^3)$ or higher. Deep Learning-Based Methods such as NeuTomography avoid direct adjacency matrix updates but require dense path sampling and augmentation, leading to the complexity of $O(|V|^2)$. In contrast, DeepNT achieves a significantly lower complexity of $O(|E|)$.

---

Response to Q2: We have now incorporated experiments on other types of synthetic graphs, including small-world and power-law graphs. Specifically, we use the Watts-Strogatz model to generate small-world graphs and the Barabási-Albert model to generate power-law graphs. We have gathered our results in Table 2, 3, 4, 5:

• DeepNT consistently outperforms all other comparison methods.

• The results indicate that DeepNT performs better on small-world graphs and Erdős-Rényi graphs compared to power-law graphs. This may be because, in power-law graphs, paths often pass through the same hubs, and missing observations from these critical hubs can disrupt predictions.

---

Thank you for your valuable effort in evaluating our work! We are happy to provide further clarification and address any additional concerns that may influence your assessment of its suitability for acceptance.

Dear Reviewer MzbY,

We recognize that the timing of this discussion period may not align perfectly with your schedule, yet we would greatly value the opportunity to continue our dialogue before the deadline approaches.

We hope that our responses and additional experiments have effectively addressed your concerns. We truly appreciate all the valuable advice we have received. Could you let us know if your concerns have been adequately addressed? If you find that your concerns have been resolved, we would appreciate it if you could reconsider the review score.

Thanks!

We would like to thank you for your thorough review and interesting thoughts. In the following, we attempt to answer your questions and comments:

---

Response to W1 & Q1: While we acknowledge that graph learning and Graph Neural Networks (GNNs) are well-established, our work distinguishes itself by addressing critical challenges specific to the network tomography domain through the following novel contributions:

• Towards the graph learning: We first highlight and summarize our contributions to graph learning as follows:

  • Introducing a unified optimization framework: We propose a novel method that simultaneously learns both the metric prediction model and the graph structure, integrating additonal unlabeled supervision by the triangle inequality. In the subsequent responses to W2 and W3, we will prove that our optimization algorithm has good efficiency and theoretically guaranteed convergence.
  • Adapting graph learning to more challenging scenarios: DeepNT is specifically designed for network tomography, where less structural information and training data are available compared to standard graph learning tasks such as node classification.

• Most graph structure learning methods assume that the adjacency matrix is either complete with noise or partially observed. These approaches primarily focus on refining or denoising the graph structure rather than reconstructing it entirely. In contrast, DeepNT addresses the challenging setting of network tomography, where the graph topology may be entirely unknown, and only a small fraction of pairwise metrics is observed (e.g., when only 10% of end-to-end path performance metrics are available). This scenario necessitates a fundamentally different approach, including the joint learning of the adjacency matrix and path-centric metrics, guided by additional supervision through constraints, i.e., the proposed triangle inequality.

• Towards the path aggregation layer: The proposed path aggregation layer is a key component tailored to the network tomography setting. Standard GNN aggregation methods (e.g., sum, mean, attention) operate on local neighborhoods and cannot capture dependencies between nodes connected by longer paths. In contrast, the path aggregation layer explicitly aggregates embeddings across multiple candidate paths, effectively capturing promising nodes that may constitute the optimal path between node pairs, specifically addressing the path-centric demands of network tomography.

---

Response to W2 & Q2: Thanks a lot for you helpful comment!

How about other GNN aggregation methods such as the subgraph aggregation like SEAL?

SEAL's framework is specifically designed for link prediction tasks [1], which focus on predicting whether a specific edge exists between two nodes. While SEAL is highly effective in capturing the local structure around links, its direct applicability to network tomography is limited. In network tomography, understanding path interactions across the network is critical, which SEAL does not inherently support. If the hop number is small, SEAL cannot capture sufficient path information, while increasing the hop number introduces more irrelevant nodes, adversely impacting the prediction of path performance. Empirically, we replaced our path aggregation with SEAL's subgraph aggregation for predicting additive metrics. The results of MSE for predicting addtive metrics when $\frac{|S|}{|T|}$ = 30% are shown as follows,

Although the original SEAL paper only sets the hop number $h$ as 1 or 2, we extended our evaluation to test $h$ up to 10 and selected the best-performing value. This adjustment accounts for the longer possible path lengths between nodes, ensuring a fair comparison.

How about other graph learning approaches such as bilevel optimization?

We compared our unified optimization framework with the bilevel optimization approach [2]. In the bilevel framework, constraints of connectivity and sparsity are applied to the outer objective, while the GNN loss serves as the inner objective. The MAPE results (in %) for predicting additive metrics when $\frac{|S|}{|T|}$ = 30% are presented as follows:

Our unified optimization approach outperforms the bilevel optimization framework in DeepNT. Notably, our unified optimization is significantly more efficient in achieving convergence, as it combines all objectives into a single unified framework.

Response to W3 & Q3: Thank you for your constructive comment. While the empirical results demonstrate the effectiveness of DeepNT, we are pleased to provide additional theoretical guarantees to further substantiate why DeepNT is a promising approach:

• Complexity: Due to the sparsity of real-world networks, we have $|E| << |V|^2$, which makes sparse matrix multiplications during GNN operations have a complexity of $O(|E| \cdot d)$, not $O(|V|^2 \cdot d)$, where $d$ is the embedding dimension. For the triangle inequality constraint, instead of processing all possible triplets $O(|V|^3$, we sample a subset of triplets proportional to $|E|$. This reduces the complexity to $O(t\cdot k\cdot |E|)$, where $k$ is the sampling ratio and $t$ is the number of training iterations. As summarized below, the complexity does not include $|V|^2$ or $|V|^3$ terms, as seen in traditional approaches, providing a theoretical guarantee of DeepNT's scalability on large-scale sparse graphs.

• Proof of Convergence for the Unified Optimization Framework: The proof of convergence for our optimization algorithm is available at: https://anonymous.4open.science/r/DeepNT2-1D25/Convergence.pdf.

---

We have taken your suggestions to heart and made changes to the best of our abilities. We are happy to provide further clarification and address any additional concerns that may influence your assessment of its suitability for acceptance.

---

References

[1] Zhang, Muhan, and Yixin Chen. "Link prediction based on graph neural networks." Advances in neural information processing systems 31 (2018).

[2] Franceschi, Luca, et al. "Learning discrete structures for graph neural networks." International conference on machine learning. PMLR, 2019.

Thanks a lot for your valuable and constructive feedback. Your suggestions are very helpful in further improving the work, and we are refining the manuscript accordingly. We have extended our formal ablation study and added the analysis of the expressiveness of DeepNT model.

---

It is not clear what "unified approach" means.

Response:

The "unified approach" means the optimization framework proposed in our paper, integrating topology inference, path-metric prediction, and handling of partial data into a single, cohesive framework. This contrasts with disjointed methods that solve these problems independently like bilevel optimization.

---

More specifically, an ablation study replacing the graph learning and the path aggregation schemes with existing solutions is needed. For the bilevel optimization (BO) results, it is not clear what "unified approach" means, BO is an alternative (there are others) to the graph learning approach (one can replace the other). Similarly, SEAL and other GNN aggregation methods are possible replacements for the path aggregation model.

Response: We have extended the ablation study by replacing the path aggregation layer with currently widely used aggregation layers and substituting our optimization algorithm with existing optimization techniques commonly employed in graph structure learning.

• Ablation Study on Aggregation Layer: We compared the proposed path aggregation layer with aggregation operations in SEAL [1], LESSR [2], PNA [3], and OSAN [4].
  • To provide a clearer explanation, we present the details of the aggregation layers along with their formulas and descriptions. The detailed descriptions are as follows: | Model | Formula | Description | |----|---|---| | DeepNT | $\hat h_v^{(n)} = h_v + \sigma(\sum_{z \in p_{uv}^{(n)}} \alpha_{vz}^{(n)} \cdot h_z^{(n)}))$ $\alpha_{vz}^{(n)} = \text{softmax}(r^\top [h_v, h_z^{(n)}])$ $h_v = \text{READOUT}(\hat h_v^{(n)}: p^{(n)}_{uv} \in \mathcal{P}^L_u)$ | Path aggregation: Aggregates over sampled optimal paths using attention and combines node representations. | | SEAL | $h_s = \text{AGG}(\{h_v : v \in G_h^{x, y}\})$ $h_{uv} = \text{READOUT}(\{h_s : G_h^{x, y} \in \text{enclosing subgraphs}\})$ | Subgraph aggregation: Aggregates node features within enclosing subgraphs extracted for target links. | | LESSR| $h_v = \text{GRU}(h_v, \{h_z : z \in \mathcal{N}(v)\})$ $h_{uv} = \text{Attention}(h_u, h_v, \text{shortcut connections})$ $h_v = \text{READOUT}(\{\text{EOPA}(h_v), \text{SGAT}(h_v)\})$ | Edge-order preserving aggregation: Combines GRU-based local aggregation with global attention from shortcut paths. | | PNA | $h_{\text{agg}} = \text{AGG}(\{h_u : u \in \mathcal{N}(v)\})$ $h_{\text{scaled}} = \text{Scaler}(\deg(v)) \cdot h_{\text{agg}}$ $h_v = \text{Combine}(h_{\text{scaled}})$ | Principal neighbourhood aggregation: Combines mean, max, min, and std aggregators with degree-based scaling. | | OSAN | $h_s = \text{AGG}\left(\{f_{\text{WL}}(v) : v \in s\}\right)$ $h_v = \text{READOUT}\left(\{h_s : v \in s, s \in \mathcal{S}\}\right)$ | Ordered subgraph aggregation: Aggregates features from WL-labeled subgraphs containing the node. |
  • We replaced our path aggregation layer with widely used aggregation methods to predict additive metrics. The Mean Squared Error (MSE) results for predicting additive metrics when $\frac{|S|}{|T|}$ = 30% are shown as follows, | DeepNT | Internet | Social Network | Transportation | Synthetic | | ---| ---| ---| ---| --- | | w/ path aggregation (ours) | 71.08 | 10.81 | 18.66 | 59.04 | | w/ subgraph aggregation [1] | 117.65 | 22.90 | 21.77 | 77.93 | | w/ edge-order preserving aggregation [2] | 84.25 | 14.19 | 17.11 | 62.65 | | w/ principal neighbourhood aggregation [3] | 94.43 | 20.01 | 22.89 | 84.07 | | w/ ordered subgraph aggregation [4] | 101.73 | 17.26 | 20.57 | 71.14 |
  • DeepNT with our path aggregation layer outperforms other DeepNT variants utilizing alternative aggregation layers across most datasets. This is because the path aggregation leverages path-specific attention on the most probable paths with optimal performance, enabling finer-grained and more accurate network tomography.

• Ablation Study on Structure Learning Algorithm: We compared our structure learning method with other currently widely used structure learning algorithms, including Continuous Optimization [5], Bilevel Optimization [6], and Iterative Optimization [7, 8].
  • The MAPE results (in %) for predicting additive metrics with $\frac{|S|}{|T|}$ = 30% and a topology error rate of $\delta$ = 20% are presented below: | DeepNT | Transportation | Synthetic | | -- | -- | -- | | w/ unified optimization (ours) | 37.94 | 19.35 | | w/ continuous optimization [5] | 46.26 | 23.88 |
    | w/ bilevel optimization [6] | 44.91 | 22.97 |
    | w/ iterative optimization [8] | 41.17 | 21.53 |
  • DeepNT with our proposed structure learning algorithm outperforms its variants employing other structure learning methods, demonstrating the effectiveness of the triangle inequality constraint and the unified optimization framework.

---

In the graph learning community, we compare models using notions such as expressive power to say what a model can or cannot learn.

Response:

Thank you for your clarification! We have rigorously proved the expressive power of the proposed DeepNT model. The detailed proof is available at: https://anonymous.4open.science/r/DeepNT2-1D25/Expressiveness%20Study.pdf. Below is a summary of the key results:

• DeepNT Expressiveness Beyond 1-WL.
  • Proof sketch: We begin by introducing the concept of WL-trees, which are constructed by the 1-WL algorithm, and Path-trees, which are rooted at a node and constructed based on paths. We show that even when WL-trees are identical for two nodes, their corresponding Path-trees can still differ. Since DeepNT with the proposed path aggregation operates on Path-trees, it can distinguish nodes that 1-WL cannot, thereby completing the proof.
• DeepNT Distinguishes Node Pairs Beyond 1-WL.
  • Proof sketch: Consider two node pairs $(u, v)$ and $(u', v')$ with identical local neighborhoods up to 1-WL. If their path sets differ, i.e., $P^L_{uv} \neq P^L_{u'v'}$, DeepNT assigns distinct embeddings: $f_{\text{DeepNT}}(u, v) \neq f_{\text{DeepNT}}(u', v')$. This distinctiveness is guaranteed by DeepNT’s path-centric aggregation, which encodes differences in path structures. Consequently, DeepNT surpasses the expressiveness of 1-WL in distinguishing node pairs.
• Convergence of DeepNT Predictions to True Pairwise Metrics.
  • Proof sketch: Leveraging the theorems on the expressiveness of DeepNT, all node pairs are uniquely identified and distinguished. Furthermore, the convergence of the optimization algorithm ensures that the training error diminishes and the generalization error diminishes as the sampled paths approach completeness. Consequently, DeepNT’s predictions converge to the true metrics in expectation with sufficient data and path sampling.

---

If there are other papers you believe could provide alternative solutions, we would be happy to include a comparison with them. We are more than happy to address any additional concerns or questions that might impact your evaluation of the work's suitability for acceptance.

---

References:

[1] Zhang, Muhan, and Yixin Chen. "Link prediction based on graph neural networks." Advances in neural information processing systems 31 (2018).

[2] Chen, Tianwen, and Raymond Chi-Wing Wong. "Handling information loss of graph neural networks for session-based recommendation." Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.

[3] Corso, Gabriele, et al. "Principal neighbourhood aggregation for graph nets." Advances in Neural Information Processing Systems 33 (2020): 13260-13271.

[4] Qian, Chendi, et al. "Ordered subgraph aggregation networks." Advances in Neural Information Processing Systems 35 (2022): 21030-21045.

[5] Zheng, Xun, et al. "Dags with no tears: Continuous optimization for structure learning." Advances in neural information processing systems 31 (2018).

[6] Franceschi, Luca, et al. "Learning discrete structures for graph neural networks." International conference on machine learning. PMLR, 2019.

[7] Chen, Yu, Lingfei Wu, and Mohammed Zaki. "Iterative deep graph learning for graph neural networks: Better and robust node embeddings." Advances in neural information processing systems 33 (2020): 19314-19326.

[8] Jin, Wei, et al. "Graph structure learning for robust graph neural networks." Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.