Pathfinder Discovery Networks for Neural Message Passing

Benedek Rozemberczki, Peter Englert, Amol Kapoor, Martin Blais, Bryan PerozziWWW 2020 · OpenReview

Abstract

In this work we propose Pathfinder Discovery Networks (PDNs), a method for jointly learning a message passing graph over a multiplex network with a downstream semi-supervised model. PDNs inductively learn an aggregated weight for each edge, optimized to produce the best outcome for the downstream learning task. PDNs are a generalization of attention mechanisms on graphs which allow flexible construction of similarity functions between nodes, edge convolutions, and cheap multiscale mixing layers. We show that PDNs overcome weaknesses of existing methods for graph attention (e.g. Graph Attention Networks), such as the diminishing weight problem. Our experimental results demonstrate competitive predictive performance on academic node classification tasks. Additional results from a challenging suite of node classification experiments show how PDNs can learn a wider class of functions than existing baselines. We analyze the relative computational complexity of PDNs, and show that PDN runtime is not considerably higher than static-graph models. Finally, we discuss how PDNs can be used to construct an easily interpretable attention mechanism that allows users to understand information propagation in the graph.

Introduction: The Static Graph Assumption

Most Graph Neural Networks (GNNs) assume the input graph is a "ground truth" static parameter. However, in the real world, relationships between entities are often multi-faceted or multiplex. For example, two videos might be related by visual similarity, audio similarity, or shared tags. Standard GNNs either force these into a single weight or struggle to learn which relationship matters most for a specific task.

Visualizing the distillation of a complex multiplex graph into a learned pathfinder graph optimized for a specific task.

Existing solutions like Graph Attention Networks (GATs) attempt to re-weight edges, but they suffer from the "diminishing weight problem": as a node's degree increases, the softmax-based attention mechanism drives individual edge weights toward zero, washing out important information. Furthermore, GATs have limited expressivity, making it difficult to learn complex logical relationships (like XOR operations) between different edge types.

Methods: The Pathfinder Neuron

The core building block of this architecture is the Pathfinder Neuron. Instead of just attending to node features, a Pathfinder Neuron takes multiple adjacency matrices (representing different types of similarities or relationships) and learns a weighted combination of them:

$$\tilde{G} = \sigma\left(\sum_{i=1}^{D} \beta_i \cdot \tilde{A}_i\right)$$

where $\beta_i$ are trainable weights and $\sigma$ is a non-linearity. This approach allows the model to score edges independently rather than using a global softmax over a neighborhood, making it resilient to skewed degree distributions.

The architecture of a simple pathfinder neuron, showing how multiple adjacency matrices are weighted and combined.

The paper details three main architectural variations:

  • Basic PDN: Learns weights for pre-computed similarity matrices (e.g., Jaccard similarity, Adamic-Adar).
  • PDN EdgeConv: Uses node features to dynamically learn the similarity scores for each edge.
  • PDN Multi-Scale: Uses powers of the adjacency matrix to learn how to mix information from different neighborhood distances (hops).

Experimental Evaluation

The authors evaluated PDNs across several categories, including synthetic scenarios designed to test "XOR" edge logic and high noise, multiplex web graphs (IMDB, ACM), and standard citation benchmarks (Cora, Citeseer, Pubmed).

Key Results

  • Performance Boost: PDNs achieved a 0.8% to 3.5% accuracy advantage over state-of-the-art models like GCN, GAT, and GraphSAGE on real-world benchmarks.
  • Multiplex Superiority: On datasets like IMDB and ACM, PDNs significantly outperformed specialized multiplex models such as DMGI and MGCN.
  • Robustness to Noise: In synthetic tests, PDNs were far more resilient to feature corruption than traditional GNNs, as they could learn to ignore noisy edge types.

Key Insights

  • Learning "XOR" Logic: PDNs can learn logical operations across edge types, identifying connections that are only important if they exist in one specific graph but not another—a task where GCNs and GATs typically fail.
  • Solving High-Degree Bias: By avoiding neighborhood-wide softmax, PDNs maintain strong signal propagation even for "hub" nodes with high connectivity.
  • Interpretability: The learned $\beta$ weights act as a form of global attention. By analyzing which similarity metrics the model weights most heavily, researchers can gain insights into the underlying structure of the data.
  • Efficiency: Calculating edge weights in a shallow PDN is $O(1)$ per edge, making it computationally competitive with static-graph models.

Conclusion and Future Work

While PDNs are efficient, runtime increases linearly with the number of input edge features. Future work involves "stacking" PDNs to learn hierarchical graph representations and exploring transfer learning, where a PDN learned on one task could provide a refined graph for a different application.

Summary updated

Abstract

In this work we propose Pathfinder Discovery Networks (PDNs), a method for jointly learning a message passing graph over a multiplex network with a downstream semi-supervised model. PDNs inductively learn an aggregated weight for each edge, optimized to produce the best outcome for the downstream learning task. PDNs are a generalization of attention mechanisms on graphs which allow flexible construction of similarity functions between nodes. They also support edge convolutions and cheap multiscale mixing layers. We show that PDNs overcome weaknesses of existing methods for graph attention (e.g. Graph Attention Networks), such as the diminishing weight problem. Our experimental results demonstrate competitive predictive performance on academic node classification tasks. Additional results from a challenging suite of node classification experiments show how PDNs can learn a wider class of functions than existing baselines. We analyze the relative computational complexity of PDNs, and show that PDN runtime is not considerably higher than static-graph models. Finally, we discuss how PDNs can be used to construct an easily interpretable attention mechanism that allows users to understand information propagation in the graph.
BibTeX
@inproceedings{rozemberczki2020pathfinder,
  author = {Benedek Rozemberczki and Peter Englert and Amol Kapoor and Martin Blais and Bryan Perozzi},
  title = {{Pathfinder Discovery Networks for Neural Message Passing}},
  booktitle = {The Web Conference},
  year = {2020},
  url = {https://openreview.net/forum?id=OxdBKMNqnDs},
}
Figure