Sign In

Exact Verification of Graph Neural Networks with Incremental Constraint Solving

μž‘μ„±μž
  • Haebom
μΉ΄ν…Œκ³ λ¦¬
Empty

μ €μž

Minghao Liu, Chia-Hsuan Lu, Marta Kwiatkowska

πŸ’‘ κ°œμš”

이 논문은 κ³ μœ„ν—˜ μ• ν”Œλ¦¬μΌ€μ΄μ…˜μ— 널리 μ‚¬μš©λ˜λŠ” κ·Έλž˜ν”„ 신경망(GNN)의 μ λŒ€μ  곡격에 λŒ€ν•œ μ •ν™•ν•œ(sound and complete) 검증 방법을 μ œμ•ˆν•©λ‹ˆλ‹€. 특히, 엣지 μΆ”κ°€/μ‚­μ œλ₯Ό ν¬ν•¨ν•˜λŠ” 속성 및 ꡬ쑰적 κ΅λž€μ— λŒ€ν•΄ GNN의 견고성을 μ˜ˆμ‚° μ œμ•½ ν•˜μ— κ²€μ¦ν•˜λŠ” 방법을 κ°œλ°œν–ˆμŠ΅λ‹ˆλ‹€. λ³Έ μ—°κ΅¬λŠ” λ°”μš΄λ“œ νƒ€μ΄νŠΈλ‹ 기법을 ν™œμš©ν•œ μ œμ•½ 만쑱 문제 ν•΄κ²°κ³Ό 점진적 ν•΄κ²°(incremental solving) κΈ°λŠ₯을 톡해 νš¨μœ¨μ„±μ„ λ†’μ˜€μŠ΅λ‹ˆλ‹€.

πŸ”‘ μ‹œμ‚¬μ  및 ν•œκ³„

β€’
λ©”μ‹œμ§€ 전달 GNN에 λŒ€ν•œ 졜초의 μ •ν™•ν•œ 검증 방법 μ œμ‹œ: Sum 외에 Max, Meanκ³Ό 같은 일반적인 집계 ν•¨μˆ˜κΉŒμ§€ ν¬ν•¨ν•˜μ—¬ GNN의 μ•ˆμ „μ„±μ„ μ—„κ²©ν•˜κ²Œ 보μž₯ν•˜λŠ” 기술적 ν† λŒ€λ₯Ό λ§ˆλ ¨ν–ˆμŠ΅λ‹ˆλ‹€.
β€’
효율적인 검증을 μœ„ν•œ ν˜μ‹ μ μΈ μ ‘κ·Ό 방식: 점진적 μ œμ•½ 문제 해결을 톡해 κΈ°μ‘΄ 방식보닀 효율적인 검증이 κ°€λŠ₯함을 μ‹€ν—˜μ μœΌλ‘œ μž…μ¦ν–ˆμŠ΅λ‹ˆλ‹€.
β€’
λŒ€κ·œλͺ¨ μ‹€μ œ λ°μ΄ν„°μ…‹μ—μ„œμ˜ μœ νš¨μ„± 확인: Amazon, Yelp, MUTAG, ENZYMES λ“± λ‹€μ–‘ν•œ μ‹€μ œ λ°μ΄ν„°μ…‹μ—μ„œ μ œμ•ˆλœ λ°©λ²•λ‘ μ˜ μ‹€μš©μ„±κ³Ό νš¨κ³Όμ„±μ„ μž…μ¦ν–ˆμŠ΅λ‹ˆλ‹€.
β€’
κΈ°μ‘΄ 검증 도ꡬ λŒ€λΉ„ μš°μˆ˜ν•œ μ„±λŠ₯: Sum 집계 GNN의 경우, κΈ°μ‘΄ μ •ν™• 검증 도ꡬ듀과 λΉ„κ΅ν•˜μ—¬ λ…Έλ“œ λΆ„λ₯˜μ—μ„œ μš°μˆ˜ν•œ μ„±λŠ₯을 λ³΄μ˜€μœΌλ©°, κ·Έλž˜ν”„ λΆ„λ₯˜μ—μ„œλ„ 경쟁λ ₯ μžˆλŠ” κ²°κ³Όλ₯Ό μ–»μ—ˆμŠ΅λ‹ˆλ‹€.
πŸ‘
Made with Slashpage