Neural Trees for Learning on Graphs

2 min read

A Neural Tree runs message passing on a tree built from the input graph. The tree (an “H-tree”) comes from a tree decomposition: each node of the H-tree is a subgraph of the input, parents are larger subgraphs than their children, and the leaves are the original nodes. Any standard aggregation (GCN, GraphSAGE, GAT, GIN) can run on the H-tree. The theory says this architecture can approximate any smooth probability distribution over an undirected graph, with a parameter count exponential in the treewidth but only linear in the number of nodes, so graphs with small treewidth are cheap.

Findings

  • Semi-supervised node classification on room-object graphs taken from Stanford’s 3D scene graph dataset: 482 graphs, 482 room nodes with 15 labels and 2338 object nodes with 35 labels. Node features are only centroid and bounding-box size.
  • Test accuracy, plain GNN versus the same aggregation on the H-tree: GCN 40.88% to 50.63%, GraphSAGE 59.54% to 63.57%, GAT 46.56% to 62.16%, GIN 49.25% to 63.53%.
  • The best number of message-passing iterations is close to the average H-tree diameter, which matches the intuition that a message has to cross the tree once.
  • On citation networks (PubMed, CiteSeer, Cora), which have large treewidth, the graph is first sub-sampled to a treewidth bound . Accuracy barely changes with on PubMed and improves with larger on Cora.

Limits

  • Cost grows exponentially with treewidth, so dense graphs must be sub-sampled, which throws edges away.
  • Finding a minimum-treewidth decomposition is NP-hard, so the method uses existing algorithms that give decompositions with “small enough” treewidth, and the bound depends on what they return.
  • The scene-graph test uses tiny features (geometry only), and on CiteSeer and Cora the authors note too few labelled nodes per class to reach high accuracy.
  • Nothing here addresses noisy or adversarial nodes and edges. The guarantee is about expressivity.

Relevance

The hierarchy in a 3D scene graph (building, room, object) is close to a tree already, which is why this works on the Stanford 3DSG data. For robust robotics, the interesting direction is the same group’s later move from “can the network represent this” to “can we certify what it outputs”, see C-3PO. It is also relevant to multi-robot perception, where merged scene graphs from several robots grow in size but not necessarily in treewidth.