Adobe Inc.
Higher-order graph clustering

Abstract:

In implementations of higher-order graph clustering and embedding, a computing device receives a heterogeneous graph representing a network. The heterogeneous graph includes nodes that each represent a network entity and edges that each represent an association between two of the nodes in the heterogeneous graph. To preserve node-type and edge-type information, a typed graphlet is implemented to capture a connectivity pattern and the types of the nodes and edges. The computing device determines a frequency of the typed graphlet in the graph and derives a weighted typed graphlet matrix to sort graph nodes. Sorted nodes are subsequently analyzed to identify node clusters having a minimum typed graphlet conductance score. The computing device is further implemented to determine a higher-order network embedding for each of the nodes in the graph using the typed graphlet matrix, which can then be concatenated into a matrix representation of the network.