Maximale-Entropie-gewichtete unabhängige Mengen-Pooling für Graph Neural Networks

In diesem Paper stellen wir eine neuartige Pooling-Schicht für Graph Neural Networks vor, die darauf basiert, die gegenseitige Information zwischen dem gepoolten Graphen und dem Eingabegraphen zu maximieren. Da die maximale gegenseitige Information schwer zu berechnen ist, nutzen wir die Shannon-Kapazität eines Graphen als induktiven Vorsatz für unsere Pooling-Methode. Genauer zeigen wir, dass der Eingabegraph der Pooling-Schicht als Darstellung eines verrauschten Kommunikationskanals interpretiert werden kann. Für einen solchen Kanal ermöglicht die Übertragung von Symbolen, die einer unabhängigen Menge des Graphen entstammen, eine zuverlässige und fehlerfreie Informationsübertragung. Wir zeigen, dass die Maximierung der gegenseitigen Information äquivalent dazu ist, eine unabhängige Menge mit maximalem Gewicht zu finden, wobei die Gewichte die Entropieinhalte repräsentieren. Von dieser informationstheoretischen Perspektive aus geben wir eine neue Sichtweise auf das Problem des Graph-Poolings, indem wir es als Maximierung der Informationsübertragungsrate über einen verrauschten Kommunikationskanal formulieren, der durch ein Graph Neural Network realisiert wird. Wir evaluieren unsere Methode, die als Maximum Entropy Weighted Independent Set Pooling (MEWISPool) bezeichnet wird, auf Aufgaben der Graphklassifikation sowie auf dem kombinatorischen Optimierungsproblem des maximalen unabhängigen Sets. Empirische Ergebnisse zeigen, dass unsere Methode auf mehreren Benchmark-Datensätzen sowohl bei der Graphklassifikation als auch beim Problem des maximalen unabhängigen Sets Ergebnisse auf State-of-the-Art-Niveau und mit hoher Wettbewerbsfähigkeit erzielt.