Hiểu các phép biến đổi trên đồ thị

Hiểu các phép biến đổi trên đồ thị Hiểu các phép biến đổi trên đồ thị Chưng cất Giới thiệu giải thưởng Gửi Hiểu các phép biến đổi trên đồ thị Hiểu các khối xây dựng và lựa chọn thiết kế của mạng lưới thần kinh đồ thị. tác giả Liên kết Ameya Daigavane Nghiên cứu của Google Balaraman Ravindran Nghiên cứu của Google Gaurav Aggarwal Nghiên cứu của Google Đã xuất bản Ngày 2 tháng 9 năm 2021 DOI 10.23915/chưng cất.00032 Nội dung Giới thiệu Những thách thức của tính toán trên đồ thị Thiếu cấu trúc nhất quán Tương đương thứ tự nút Khả năng mở rộng Đặt vấn đề và ký hiệu Mở rộng các kết cấu thành đồ thị Bộ lọc đa thức trên đồ thị Mạng thần kinh đồ thị hiện đại Mạng nơ-ron đồ thị tương tác Từ kết hợp cục bộ đến toàn cầu Tích chập quang phổ Tuyên truyền toàn cầu thông qua nhúng đồ thị Học các tham số GNN GNN có tốt hơn CNN không? --> Kết luận và đọc thêm GNN trong thực tế Các loại đồ thị khác nhau Tổng hợp Tài liệu bổ sung Tái tạo thí nghiệm Tái tạo trực quan Bài viết này là một trong hai ấn phẩm của Distill về mạng lưới thần kinh đồ thị. Hãy nhìn vào Giới thiệu nhẹ nhàng về Mạng nơ-ron đồ thị để có cái nhìn đồng hành về nhiều thứ liên quan đến biểu đồ và mạng lưới thần kinh. Nhiều hệ thống và tương tác - mạng xã hội, phân tử, tổ chức, trích dẫn, mô hình vật lý, giao dịch - có thể được biểu diễn khá tự nhiên dưới dạng biểu đồ. Làm thế nào chúng ta có thể suy luận và đưa ra dự đoán trong các hệ thống này? Một ý tưởng là xem xét các công cụ hoạt động tốt trong các lĩnh vực khác: mạng lưới thần kinh đã thể hiện khả năng dự đoán to lớn trong nhiều nhiệm vụ học tập khác nhau. Tuy nhiên, mạng lưới thần kinh theo truyền thống được sử dụng để hoạt động trên các đầu vào có kích thước cố định và/hoặc có cấu trúc thông thường (chẳng hạn như câu, hình ảnh và video). Điều này khiến họ không thể xử lý dữ liệu có cấu trúc biểu đồ một cách tinh tế. Mạng thần kinh đồ thị (GNN) là một họ mạng thần kinh có thể hoạt động tự nhiên trên dữ liệu có cấu trúc biểu đồ. Bằng cách trích xuất và sử dụng các tính năng từ biểu đồ cơ bản, GNN có thể đưa ra những dự đoán sáng suốt hơn về các thực thể trong các tương tác này, so với các mô hình xem xét các thực thể riêng lẻ một cách biệt lập. GNN không phải là công cụ duy nhất có sẵn để mô hình hóa dữ liệu có cấu trúc biểu đồ: hạt đồ thị và phương pháp bước đi ngẫu nhiên là một trong những cái phổ biến nhất. Tuy nhiên, ngày nay GNN đã thay thế phần lớn các kỹ thuật này vì tính linh hoạt vốn có của chúng để mô hình hóa các hệ thống cơ bản tốt hơn. Trong bài viết này, chúng tôi sẽ minh họa những thách thức của việc tính toán trên đồ thị, mô tả nguồn gốc và thiết kế của mạng lưới thần kinh đồ thị, và khám phá các biến thể GNN phổ biến nhất trong thời gian gần đây. Đặc biệt, chúng ta sẽ thấy rằng nhiều biến thể này được tạo thành từ các khối xây dựng tương tự. Trước tiên, hãy thảo luận về một số vấn đề phức tạp mà đồ thị gặp phải. Những thách thức của tính toán trên đồ thị Thiếu cấu trúc nhất quán Đồ thị là mô hình toán học cực kỳ linh hoạt; nhưng điều này có nghĩa là chúng thiếu cấu trúc nhất quán giữa các phiên bản. Hãy xem xét nhiệm vụ dự đoán liệu một phân tử hóa học nhất định có độc hại hay không: Bên trái: Một phân tử 1,2,6-trigalloyl-glucose không độc hại. Phải: Một phân tử caramboxin độc hại. Nhìn vào một vài ví dụ, các vấn đề sau sẽ nhanh chóng trở nên rõ ràng: Các phân tử có thể có số lượng nguyên tử khác nhau. Các nguyên tử trong phân tử có thể có nhiều loại khác nhau. Mỗi nguyên tử này có thể có số lượng kết nối khác nhau. Những kết nối này có thể có sức mạnh khác nhau. Việc biểu diễn đồ thị ở định dạng có thể tính toán được là không hề đơn giản, và cách biểu diễn cuối cùng được chọn thường phụ thuộc đáng kể vào bài toán thực tế. Tương đương thứ tự nút Mở rộng điểm trên: biểu đồ thường không có thứ tự vốn có giữa các nút. Hãy so sánh điều này với hình ảnh, trong đó mỗi pixel được xác định duy nhất bởi vị trí tuyệt đối của nó trong hình ảnh! Việc biểu diễn đồ thị dưới dạng một vectơ yêu cầu chúng ta phải cố định thứ tự trên các nút. Nhưng chúng ta phải làm gì khi các nút không có trật tự cố hữu? Ở trên: Cùng một biểu đồ được dán nhãn theo hai cách khác nhau. Các bảng chữ cái cho biết thứ tự của các nút. Do đó, chúng tôi muốn các thuật toán của mình tương đương với thứ tự nút: chúng không nên phụ thuộc vào thứ tự của các nút của đồ thị. Nếu chúng ta hoán vị các nút theo một cách nào đó, thì kết quả biểu diễn của các nút được tính toán bằng thuật toán của chúng tôi cũng phải được hoán vị theo cách tương tự. Khả năng mở rộng Đồ thị có thể rất lớn! Hãy nghĩ về các mạng xã hội như Facebook và Twitter, những mạng có hơn một tỷ người dùng. Hoạt động trên dữ liệu lớn này không phải là điều dễ dàng. May mắn thay, hầu hết các đồ thị xuất hiện tự nhiên đều 'thưa thớt': chúng có xu hướng có số cạnh tuyến tính theo số đỉnh của chúng. Chúng ta sẽ thấy rằng điều này cho phép sử dụng các phương pháp thông minh để tính toán hiệu quả các biểu diễn của các nút trong biểu đồ. Hơn nữa, các phương pháp mà chúng ta xem xét ở đây sẽ có ít tham số hơn đáng kể so với kích thước của đồ thị mà chúng hoạt động trên đó. Đặt vấn đề và ký hiệu Có nhiều bài toán hữu ích có thể được giải bằng đồ thị: Phân loại nút: Phân loại các nút riêng lẻ. Phân loại đồ thị: Phân loại toàn bộ đồ thị. Phân cụm nút: Nhóm các nút tương tự lại với nhau dựa trên khả năng kết nối. Dự đoán liên kết: Dự đoán các liên kết bị thiếu. Tối đa hóa ảnh hưởng: Xác định các nút có ảnh hưởng. Ví dụ về các vấn đề có thể được xác định trên đồ thị. Danh sách này không đầy đủ! Một tiền thân phổ biến trong việc giải quyết nhiều vấn đề này