Bipartite graph

As explained in Graph Neural Networks in Action

A bipartite graph is a graph whose nodes are partitioned into subsets and whose edges connect nodes in different subsets rather than within the same subset.

Use a bipartite graph when relationships run between two sets of nodes, but not within either set. Each edge connects a node in one set to a node in the other. A bipartite graph can also be heterogeneous: its two sets may represent different kinds of things. section 1.2.2

Pins and boards

In a Pinterest-style recommendation graph, pins form one set and boards the other. A pin can belong to multiple boards, but pin-to-pin and board-to-board edges are absent. These connections provide recommendation signals alongside image data and user tags. PinSage, a graph convolutional network, used this kind of graph in a large-scale recommendation system. section 1.3.1

When designing the graph dataset, make the structural rule explicit:

• Identify the two node sets and the relationship an edge represents. section 8.2.2
• Check that edges cross between sets; an edge within a set violates the bipartite structure. section 8.2.2
• Record the rule in the schema so data integrity can be tested and graph structures compared systematically. section 8.2.2

Figure 1.3 A bipartite graph. There are two types of nodes (two shades of circles). In a bipartite graph, nodes can’t be connected to nodes of the same type. This is also an example of a heterogeneous graph.

The two shades of nodes show the sets; every depicted edge crosses between them. section 1.2.2

How Graph Neural Networks in Action covers it

How deep it goes

Defines the two-set edge rule and illustrates an application, but does not give a bipartite-graph implementation.

Examples

Uses pins and boards, including pins shared across boards, to illustrate permitted edges.

What it assumes

Introduces the rule through nodes, edges, and node types without requiring graph-learning implementation knowledge.

What you can do after

Evaluate/understand whether a two-set dataset satisfies the bipartite edge constraint before using it in a graph pipeline.

How it connects

Connects bipartite graphs to heterogeneous graphs, graph schemas, recommendation systems, and graph convolutional networks.

liveBookmanning.com

Read Graph Neural Networks in Action on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Graph Algorithms for Data ScienceA bipartite graph is a graph whose nodes are divided into two types, with edges connecting nodes across the two types rather than within the same type.
• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresA bipartite graph is a graph whose vertices can be partitioned into two groups with edges only between the groups; in this section the graph is also required to be connected.

Compare how 3 books explain bipartite graph →

Related concepts

• graphkind of · A graph is a mathematical structure consisting of vertices connected by edges that represent relationships or connections.
• network projectionused by · Network projection is the transformation of a multipartite graph into a graph containing one selected node type by inferring connections through shared neighbors.
• graph coloringequivalent to · Graph coloring is the assignment of colors to graph elements subject to constraints, such as requiring adjacent vertices to have different colors.
• co-occurrence networkproduces · A co-occurrence network is a graph whose entities are connected when they appear together in a shared context.

This explainer was generated by Manning's knowledge graph from the text of Graph Neural Networks in Action. The section links point to the parts of the book it draws on.