Engineering Graph Features via Network Functional Blocks

Vincent W. ZhengIJCAI 2018 · DOI

TL;DR

This paper introduces "network functional blocks" – richer graph structures beyond simple nodes and edges – to improve predictive tasks on graphs. The authors propose and evaluate three methods (ProxEmbed, SPE, D2AGE) that leverage paths, subgraphs, and directed acyclic graphs (DAGs) to capture complex semantic relationships, outperforming existing methods on semantic proximity search tasks.

What Problem Does This Paper Address?

Graphs are ubiquitous in representing relationships, from social networks to e-commerce platforms. Many predictive tasks, like classifying nodes or predicting links, rely on effectively extracting features from these graphs. Traditional methods often focus on individual nodes or simple edge connections, which can miss crucial higher-order structural information. This paper addresses the challenge of engineering more powerful graph features by exploring "network functional blocks" – more complex substructures like paths, subgraphs, and DAGs – that can better capture the nuanced semantic relationships present in real-world graphs. The authors aim to move beyond node-level representations to exploit these richer building blocks for improved predictive performance.

Methods

The paper proposes three main approaches to engineer graph features using network functional blocks:

  • ProxEmbed: This method uses paths as network functional blocks. It addresses the challenge of modeling complex path structures by employing a recurrent neural network with discounted path pooling to embed multiple paths between a query node and a target node. This allows for differentiating the contribution of each node and path, and the model is supervised to learn semantic proximity.
  • SPE (Subgraph-augmented Path Embedding): This approach extends paths by incorporating subgraphs. It augments paths with frequent subgraph patterns to capture richer semantic information. A hierarchical attention mechanism is introduced to weigh the importance of subgraphs, nodes within subgraphs, and the paths themselves, allowing for more nuanced feature representation.
  • D2AGE (Distance-aware DAG Embedding): This method utilizes Directed Acyclic Graphs (DAGs) as network functional blocks. DAGs are chosen for their directional nature and richer expressiveness compared to paths. The key innovation here is a "distance-aware" embedding that accounts for the varying distances of predecessors from the start node when constructing the DAG embedding, reflecting that closer connections are often more significant.

All three methods involve offline preprocessing (path sampling, subgraph mining, DAG generation) and online prediction to ensure efficiency.

Datasets

The authors evaluate their proposed methods on three heterogeneous graphs:

  • LinkedIn: A professional network.
  • Facebook: A social network.
  • DBLP: A bibliography network.

They consider various semantic relations on these datasets, including "schoolmate," "colleague," "family," "classmate," "advisor," and "advisee." The paper notes that "advisor" and "advisee" represent asymmetric relations, while others are symmetric.

Key Insights and Ideas

  • Beyond Nodes: The core idea is that individual nodes are insufficient for capturing complex graph semantics. Richer substructures ("network functional blocks") are necessary for better predictive performance.
  • Hierarchical Importance: In SPE, the hierarchical attention mechanism highlights that not all parts of a subgraph or path contribute equally to a semantic relation, allowing the model to learn which components are most informative.
  • Distance Matters: D2AGE demonstrates that the distance of nodes within a DAG from the starting node is a crucial factor in determining the strength of a semantic connection, leading to more accurate representations.
  • Efficiency is Key: The authors emphasize the importance of offline processing and indexing to enable efficient generation and use of these complex functional blocks, especially for large-scale graphs.

Key Results

The paper presents quantitative results in Table 1, comparing ProxEmbed, SPE, and D2AGE against baselines like DeepWalk, MGP, and Metapath2vec on semantic proximity search tasks using NDCG@10 and MAP@10 metrics.

  • Outperformance: The proposed methods (ProxEmbed, SPE, D2AGE) consistently outperform the baselines across all datasets and semantic relations.
  • SPE's Strength: SPE generally performs very well, demonstrating the effectiveness of explicit subgraph patterns.
  • D2AGE's Efficiency: D2AGE achieves comparable or even better performance than SPE, with the added benefit of more efficient network functional block generation, suggesting DAGs are a powerful and practical choice.
  • Baseline Limitations: Baselines like DeepWalk are noted for focusing on node-level features, while MGP, though using subgraphs, requires manual mining and struggles with implicit graph features. Metapath2vec's performance is surprisingly limited by its manually designed meta-path patterns.

Limitations and Future Work

  • Subgraph Mining Complexity: The paper acknowledges that mining frequent subgraph patterns (as in SPE) can be NP-hard, necessitating constraints on pattern size and symmetry-based matching for efficiency.
  • Implicit Structures: The authors suggest future work should explore more implicit network functional blocks, such as community structures or graph convolutions that capture implicit higher-order patterns.
  • Large-Scale and Dynamic Graphs: A significant future direction is developing methods to efficiently generate and update network functional blocks for massive, evolving graphs in distributed settings.
  • Incremental Updates: Enabling incremental updates for network functional block generation and model training remains an open research question.

Summary updated

BibTeX
@inproceedings{zheng2018engineering,
  author = {Vincent W. Zheng},
  title = {{Engineering Graph Features via Network Functional Blocks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/822},
}
Figure